A Q'tron Neural-Network Approach to Solve the Graph Coloring Problems
Published 1 October 2007
Tai-Wen Yue, Z. Lee
Citations59
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A novel methodology to solve the graph coloring problem (GCP) using the Q'tron neural- network (NN) model, which can make the NN local- minima-free and perform the so-called goal-directed search.
Abstract
This paper proposes a novel methodology to solve the graph coloring problem (GCP) using the Q'tron neural- network (NN) model. The Q'tron NN for GCP will be built as a known-energy system. This can make the NN local- minima-free and perform the so-called goal-directed search. Consider k-GCP as a goal to solve a GCP using at most k different colors. By continuously refining our goal, i.e., decreasing the value k, we can then 'demand' the NN to fulfill better and better goals progressively. Experiments using DI-MACS benchmarks were done using such an approach, and comparison was made with the DSATUR algorithm. The result supports the soundness of our approach.
Keywords
Computer ScienceDecision SciencesEngineering
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
Journal of Machine Learning ResearchLatent dirichlet allocation
27,049 Citations2003David M. Blei, Andrew Y. Ng +1 more
Lecture notes in computer scienceText categorization with Support Vector Machines: Learning with many relevant features
7,925 Citations1998Thorsten Joachims
SVMs achieve substantial improvements over the currently best performing methods and behave robustly over a variety of di-erent learning tasks, eliminating the need for manual parameter tuning.
A comparison of event models for naive bayes text classification
3,224 Citations1998Andrew McCallum, Kamal Nigam
It is found that the multi-variate Bernoulli performs well with small vocabulary sizes, but that the multinomial performs usually performs even better at larger vocabulary sizes--providing on average a 27% reduction in error over the multi -variateBernoulli model at any vocabulary size.
Machine LearningText Classification from Labeled and Unlabeled Documents using EM
2,749 Citations2000Kamal Nigam, Andrew Kachites McCallum +2 more
This paper shows that the accuracy of learned text classifiers can be improved by augmenting a small number of labeled training documents with a large pool of unlabeled documents, and presents two extensions to the algorithm that improve classification accuracy under these conditions.
A re-examination of text categorization methods
2,660 Citations1999Yiming Yang, Xin Liu
The results show that SVM, kNN and LLSF signi cantly outperform NNet and NB when the number of positive training instances per category are small, and that all the methods perform comparably when the categories are over 300 instances.
Text REtrieval ConferenceOkapi at TREC
2,229 Citations1994Stephen Robertson, Steve Walker +3 more
Much of the work involved investigating plausible methods of applying Okapi-style weighting to phrases, and expansion using terms from the top documents retrieved by a pilot search on topic terms was used.
ACM SIGIR ForumA Study of Smoothing Methods for Language Models Applied to Ad Hoc Information Retrieval
1,571 Citations2017ChengXiang Zhai, John Lafferty
This paper examines the sensitivity of retrieval performance to the smoothing parameters and compares several popular smoothing methods on different test collection.
Machine LearningConcept Decompositions for Large Sparse Text Data Using Clustering
1,297 Citations2001Inderjit S. Dhillon, Dharmendra S. Modha
The concept vectors produced by the spherical k-means algorithm constitute a powerful sparse and localized “basis” for text data sets and are localized in the word space, are sparse, and tend towards orthonormality.
LDA-based document models for ad-hoc retrieval
1,086 Citations2006Xing Wei, W. Bruce Croft
This paper proposes an LDA-based document model within the language modeling framework, and evaluates it on several TREC collections, and shows that improvements over retrieval using cluster-based models can be obtained with reasonable efficiency.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
844 Citations1991David S. Johnson, C. Aragon +2 more
This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization.
Retrieving collocations from text: Xtract
799 Citations1993Frank Smadja
A set of techniques based on statistical methods for retrieving and identifying collocations from large textual corpora, based on some original filtering methods that allow the production of richer and higher-precision output are described.
ComputingUsing tabu search techniques for graph coloring
660 Citations1987Alain Hertz, D. de Werra
It is shown that tabu search techniques provide almost optimal colorings of graphs having up to 1000 nodes and their efficiency is shown to be significantly superior to the famous simulated annealing.
ACM SIGIR ForumInformation Retrieval as Statistical Translation
631 Citations2017Adam Berger, John Lafferty
A simple, well motivated model of the document-to-query translation process is proposed, and an algorithm for learning the parameters of this model in an unsupervised manner from a collection of documents is described.
Knowledge and Information SystemsGenerative model-based document clustering: a comparative study
247 Citations2005Shi Zhong, Joydeep Ghosh
This paper presents a detailed empirical study of 12 generative approaches to text clustering, obtained by applying four types of document-to-cluster assignment strategies to each of three base models, namely mixtures of multivariate Bernoulli, multinomial, and von Mises-Fisher distributions.
Computational LinguisticsRetrieving collocations from text
211 Citations1993SmadjaFrank
Natural languages are full of collocations, recurrent combinations of words that co-occur more often than expected by chance and that correspond to arbitrary word usages.
Two-stage language models for information retrieval
193 Citations2002ChengXiang Zhai, John Lafferty
Evaluation on five different databases and four types of queries indicates that the two-stage smoothing method with the proposed parameter estimation methods consistently gives retrieval performance that is close to---or better than---the best results achieved using a single smoothed method and exhaustive parameter search on the test data.
Text categorization by boosting automatically extracted concepts
117 Citations2003Lijuan Cai, Thomas Hofmann
This paper investigates the use of concept-based document representations to supplement word- or phrase-based features, and proposes to use AdaBoost to optimally combine weak hypotheses based on both types of features.
Discrete Applied MathematicsAn ant-based algorithm for coloring graphs
84 Citations2007Thang Nguyen Bui, ThanhVu Nguyen +2 more
This paper presents an ant-based algorithm for the graph coloring problem, and despite the lack of pheromone laying capacity by the ants, the algorithm performed well on a set of 119 benchmark graphs.
Lecture notes in computer scienceA Comparative Study of Ontology Based Term Similarity Measures on PubMed Document Clustering
79 Citations2007Xiaodan Zhang, Liping Jing +3 more
This paper evaluates term re-weighting as an important method to integrate domain ontology to clustering process and results on 8 different semantic measures show there is no a certain type of similarity measures that significantly outperforms the others.
Word sense disambiguation in queries
70 Citations2005Shuang Liu, Clement Yu +1 more
A new approach to determine the senses of words in queries by using WordNet is presented, which has 100% applicability and 90% accuracy on the most recent robust track of TREC collection of 250 queries and the retrieval effectiveness is 7% better than the best reported result in the literature.
Lecture notes in computer scienceMaxMatcher: Biological Concept Extraction Using Approximate Dictionary Lookup
67 Citations2006Xiaohua Zhou, Xiaodan Zhang +1 more
An ACO Algorithm for Graph Coloring Problem
52 Citations2006Ehsan Salari, Kourosh Eshghi
An ACO algorithm is presented for the graph coloring problem that conforms to max-min ant system structure and exploits a local search heuristic to improve its performance.
Context-sensitive semantic smoothing for the language modeling approach to genomic IR
48 Citations2006Xiaohua Zhou, Xiaohua Hu +3 more
This work proposes a novel context-sensitive semantic smoothing method that decomposes a document or a query into a set of weighted context- sensitive topic signatures and then translates those topic signatures into query terms.
Frequency sensitive competitive learning for clustering on high-dimensional hyperspheres
46 Citations2003Arindam Banerjee, Joydeep Ghosh
Three competitive learning mechanisms from first principles are derives to obtain clusters of comparable sizes when both inputs and representatives are normalized to achieve balanced grouping of inputs in high dimensional spaces.
Ant Colony System for Graph Coloring Problem
21 Citations2006Malika Bessedik, R. Laib +2 more
A comparison between the different algorithms shows that the algorithm called ACS1_R (construction strategy, construction done by RLF) gives best results, which approaches the best colouring algorithms and outperforms some hybrid algorithms on some large instances of the famous Dimacs benchmarks.
Semantic smoothing of document models for agglomerative clustering
21 Citations2007Xiao‐Hua Zhou, Xiaodan Zhang +1 more
A novel context-sensitive semantic smoothing method is proposed that can automatically identifies multiword phrases in a document and then statistically map phrases to individual document terms and significantly improves the clustering quality over the traditional vector cosine measure.
A complete neural network approach to solving a class of combinatorial problems
6 Citations1991Tai Yue, Li‐Chen Fu
The concept of the Hopfield neural network has been generalized where discrete neurons, called quantrons (Q'trons, a shorthand for quantum neurons), are exploited and a system energy, referred to as Lyapunov energy, is embedded in the NN and is shown to possess monotonically decreasing property.
Graph coloring in J
2 Citations2000Howard A. Peelle
Fundamentals of graph coloring are introduced, and four basic alternative algorithms for coloring undirected graphs are described in J, along with programs for generating, adjacency matrices and testing them.