CiteULike: yaroslavvb's library [672 articles]

Pattern Classification (2nd Edition)

Richard Duda — 2005-04-22T17:32:18-00:00

(21 November 2000)

Multiclass Linear Dimension Reduction by Weighted Pairwise Fisher Criteria

Marco Loog — 2008-05-01T21:54:02-00:00

IEEE Trans. Pattern Anal. Mach. Intell., Vol. 23, No. 7. (July 2001), pp. 762-766.

Foundations of Statistical Natural Language Processing

Christopher Manning — 2005-02-27T13:16:32-00:00

(18 June 1999)

"Statistical natural-language processing is, in my estimation, one of the most fast-moving and exciting areas of computer science these days. Anyone who wants to learn this field would be well advised to get this book. For that matter, the same goes for anyone who is already in the field. I know that it is going to be one of the most well-thumbed books on my bookshelf." -- Eugene Charniak, Department of Computer Science, Brown University Statistical approaches to processing natural language text have become dominant in recent years. This foundational text is the first comprehensive introduction to statistical natural language processing (NLP) to appear. The book contains all the theory and algorithms needed for building NLP tools. It provides broad but rigorous coverage of mathematical and linguistic foundations, as well as detailed discussion of statistical methods, allowing students and researchers to construct their own implementations. The book covers collocation finding, word sense disambiguation, probabilistic parsing, information retrieval, and other applications. More on this book

An Evaluation of Statistical Approaches to Text Categorization

Yiming Yang — 2006-04-03T05:47:49-00:00

Information Retrieval, Vol. 1, No. 1/2. (1999), pp. 69-90.

This paper is a comparative study of text categorization methods. Fourteen methods are investigated, based on previously published results and newly obtained results from additional experiments. Corpus biases in commonly used document collections are examined using the performance of three classifiers. Problems in previously published experiments are analyzed, and the results of flawed experiments are excluded from the cross-method evaluation. As a result, eleven out of the fourteen methods are ...

A comparative study on feature selection in text categorization

Yiming Yang — 2007-03-17T07:50:40-00:00

(1997), pp. 412-420.

This paper is a comparative study of feature selection methods in statistical learning of text categorization. The focus is on aggressive dimensionality reduction. Five methods were evaluated, including term selection based on document frequency (DF), information gain (IG), mutual information (MI), a Ø 2 -test (CHI), and term strength (TS). We found IG and CHI most effective in our experiments. Using IG thresholding with a knearest neighbor classifier on the Reuters corpus, removal of up to...

Machine learning in automated text categorization

Fabrizio Sebastiani — 2005-01-26T09:29:47-00:00

ACM Comput. Surv., Vol. 34, No. 1. (March 2002), pp. 1-47.

The relationship between Precision-Recall and ROC curves

Jesse Davis — 2008-01-20T14:54:47-00:00

(2006), pp. 233-240.

AUC optimization vs. error rate minimization

C Cortes — 2007-07-10T20:28:49-00:00

(2004)

The area under an ROC curve (AUC) is a criterion used in many applications to measure the quality of a classification algorithm. However, the objective function optimized in most of these algorithms is the error rate and not the AUC value. We give a detailed statistical analysis of the relationship between the AUC and the error rate, including the first exact expression of the expected value and the variance of the AUC for a fixed error rate. Our results show that the average AUC is...

Learning to Rank by Maximizing AUC with Linear Programming

K Ataman — 2008-04-16T21:23:38-00:00

Neural Networks, 2006. IJCNN '06. International Joint Conference on (2006), pp. 123-129.

Area Under the ROC Curve (AUC) is often used to evaluate ranking performance in binary classification problems. Several researchers have approached AUC optimization by approximating the equivalent Wicoxon-Mann-Whitney (WMW) statistic. We present a linear programming approach similar to 1-norm Support Vector Machines (SVMs) for instance ranking by an approximation to the WMW statistic. Our formulation can be applied to nonlinear problems by using a kernel function. Our ranking algorithm outperforms SVMs in both AUC and classification performance when using RBF kernels, but curiously not with polynomial kernels. We experiment with variations of chunking to handle the quadratic growth of the number of constraints in our formulation.

Collective multi-label classification

Nadia Ghamrawi — 2007-03-01T23:39:36-00:00

(2005), pp. 195-200.

Large-Scale Bayesian Logistic Regression for Text Categorization

Genkin — 2007-07-21T23:50:35-00:00

Technometrics, Vol. 49, No. 3. (August 2007), pp. 291-304.

Trust region Newton methods for large-scale logistic regression

Chih-Jen Lin — 2008-03-24T17:00:11-00:00

(2007), pp. 561-568.

Semisupervised Learning for a Hybrid Generative/Discriminative Classifier based on the Maximum Entropy Principle

Akinori Fujino — 2008-03-23T23:48:12-00:00

Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 30, No. 3. (2008), pp. 424-437.

This paper presents a method for designing semi-supervised classifiers trained on labeled and unlabeled samples. We focus on probabilistic semi-supervised classifier design for multi-class and singlelabeled classification problems, and propose a hybrid approach that takes advantage of generative and discriminative approaches. In our approach, we first consider a generative model trained by using labeled samples and introduce a bias correction model, where these models belong to the same model family, but have different parameters. Then, we construct a hybrid classifier by combining these models based on the maximum entropy principle. To enable us to apply our hybrid approach to text classification problems, we employed naive Bayes models as the generative and bias correction models. Our experimental results for four text data sets confirmed that the generalization ability of our hybrid classifier was much improved by using a large number of unlabeled samples for training when there were too few labeled samples to obtain good performance. We also confirmed that our hybrid approach significantly outperformed generative and discriminative approaches when the performance of the generative and discriminative approaches was comparable. Moreover, we examined the performance of our hybrid classifier when the labeled and unlabeled data distributions were different.

Square Lattice Self-Avoiding Walks and Polygons

AJ Guttmann — 2008-03-19T00:07:59-00:00

Annals of Combinatorics, Vol. 5, No. 3. (1 December 2001), pp. 319-345.

Comparison of Spectral Methods Through the Adjacency Matrix and the Laplacian of a Graph

Zumstein — 2008-02-27T21:31:13-00:00

(2005)

Generatingfunctionology

Herbert Wilf — 2005-11-29T15:03:17-00:00

This is the Second Edition of the highly successful introduction to the use of generating functions and series in combinatorial mathematics. This new edition includes several new areas of application, including the cycle index of the symmetric group, permutations and square roots, counting polyominoes, and exact covering sequences. An appendix on using the computer algebra programs MAPLE(r) and Mathematica(r) to generate functions is also included. The book provides a clear, unified introduction to the basic enumerative applications of generating functions, and includes exercises and solutions, many new, at the end of each chapter. Key Features * Provides new applications on the cycle index of the symmetric group, permutations and square roots, counting polyominoes, and exact covering sequences * Features an Appendix on using MAPLE(r) and Mathematica (r) to generate functions * Includes many new exercises with complete solutions at the end of each chapter

The largest eigenvalue of a graph: A survey

D Cvetkovi&cacute; — 2008-02-17T23:52:07-00:00

Linear and Multilinear Algebra, Vol. 28, No. 1. (1990), pp. 3-33.

This article is a survey of results concerning the largest eigenvalue (or index) of a grapn, catcgoiizeu as follows (1) inequalities lor the index, (2) graph with bounded index, (3) ordering graphs by their indices, (4) graph operations and modifications, (5) random graphs, (6) applications.

Tensor Decompositions and Applications

Kolda — 2008-02-17T21:16:16-00:00

(2007)

Tensor rank and the ill-posedness of the best low-rank approximation problem

Vin de Silva — 2008-02-17T21:06:33-00:00

(26 Jul 2006)

There has been continued interest in seeking a theorem describing optimal low-rank approximations to tensors of order 3 or higher, that parallels the Eckart-Young theorem for matrices. In this paper, we argue that the naive approach to this problem is doomed to failure because, unlike matrices, tensors of order 3 or higher can fail to have best rank-r approximations. The phenomenon is much more widespread than one might suspect: examples of this failure can be constructed over a wide range of dimensions, orders and ranks, regardless of the choice of norm (or even Bregman divergence). Moreover, we show that in many instances these counterexamples have positive volume: they cannot be regarded as isolated phenomena. In one extreme case, we exhibit a tensor space in which no rank-3 tensor has an optimal rank-2 approximation. The notable exceptions to this misbehavior are rank-1 tensors and order-2 tensors. In a more positive spirit, we propose a natural way of overcoming the ill-posedness of the low-rank approximation problem, by using weak solutions when true solutions do not exist. In our work we emphasize the importance of closely studying concrete low-dimensional examples as a first step towards more general results. To this end, we present a detailed analysis of equivalence classes of 2-by-2-by-2 tensors, and we develop methods for extending results upwards to higher orders and dimensions. Finally, we link our work to existing studies of tensors from an algebraic geometric point of view. The rank of a tensor can in theory be given a semialgebraic description; i.e., can be determined by a system of polynomial inequalities. In particular we make extensive use of the 2-by-2-by-2 hyperdeterminant.

Walks and the spectral radius of graphs

Vladimir Nikiforov — 2008-02-16T23:24:13-00:00

(2 May 2006)

We give upper and lower bounds on the spectral radius of a graph in terms of the number of walks. We generalize a number of known results.

Graphs determined by polynomial invariants

Marc Noy — 2005-12-01T07:08:52-00:00

Theoretical Computer Science, Vol. 307, No. 2. (7 October 2003), pp. 365-384.

Many polynomials have been defined associated to graphs, like the characteristic, matchings, chromatic and Tutte polynomials. Besides their intrinsic interest, they encode useful combinatorial information about the given graph. It is natural then to ask to what extent any of these polynomials determines a graph and, in particular, whether one can find graphs that can be uniquely determined by a given polynomial. In this paper we survey known results in this area and, at the same time, we present some new results.

Impact of different macronutrient definitions and energy conversion factors on energy supply estimations

UR Charrondiere — 2008-02-14T07:40:43-00:00

Journal of Food Composition and Analysis, Vol. 17, No. 3-4. ( 2004), pp. 339-360.

The magnitude of differences in energy supply using different definitions for carbohydrates and protein as well as different energy conversion factors was investigated. Food supply data for 1999-2001 from FAOSTAT were used for nine countries with different types of diets. Nutrient values were derived from USDA and the British food composition tables for three definitions of carbohydrate (total, available by difference, available as monosaccharide equivalents), three protein definitions (nitrogen (N)xJones factors, Nx6.25, sum of amino acids), fat, and two dietary fibre definitions (AOAC, non-starch polysaccharide). Then three sets of energy conversion factors were applied (Merrill & Watt, general Atwater with/without energy value for fibre, and gross energy--GE). Using the same nutrient definitions, differences between general and specific Atwater factors accounted for 50-320 kJ/capita/day (10-75 kcal/capita/day) and for 290-1500 kJ/capita/day (70-360 kcal/capita/day) between GE and metabolizable energy supply calculations. Protein definitions have a minor impact on per capita energy supply values. They generate differences of less than 1%, or 4-105 kJ (1-25 kcal), with Nx6.25 values providing the highest values, followed by Jones factors and the sum of amino acids. The largest differences observed in per capita energy supply calculations are due to carbohydrate definitions. Differences of 3.5-8% or 330-780 kJ/capita/day (80-190 kcal/capita/day) are observed between total and available carbohydrates as monosaccharide equivalents within the general Atwater system. Differences in energy supply between total and available carbohydrates could be minimized by applying an energy factor of 8 kJ/g (2 kcal/g) for dietary fibre, resulting in a higher energy supply of 100-250 kJ/capita/day (25-60 kcal/capita/day) or 1-2%. Differences in energy supply are less influenced by the energy factors as such than by the nutrient definition used, especially for carbohydrates. Differences in energy supply of up to 780 kJ/capita/day (160 kcal/capita/day) or 8% may be statistically relevant and might change research results, estimates of the dietary energy supply and consequently the estimation of the prevalence of undernourishment which may affect nutrition program and policies. Global harmonization of macronutrient definitions and energy factors is important to achieve unambiguous and comparable macronutrient and energy values among countries.

Doubly stochastic graph matrices

Merris — 2008-02-14T00:54:12-00:00

Publ. Elektrotech. Fak. Univ. Beograd (1997)

Graph Theory

Frank Harary — 2005-11-30T17:15:17-00:00

An effort has been made to present the various topics in the theory of graphs in a logical order, to indicate the historical background, and to clarify the exposition by including figures to illustrate concepts and results. In addition, there are three appendices which provide diagrams of graphs, directed graphs, and trees. The emphasis throughout is on theorems rather than algorithms or applications, which however are occaisionally mentioned.

Generalized matrix tree theorem for mixed graphs

Ravindra Bapat — 2008-02-13T09:54:57-00:00

Linear and Multilinear Algebra, Vol. 46, No. 4. (1999), pp. 299-312.

In this article we provide a combinatorial description of an arbitrary minor of the Laplacian matrix (L) of a mixed graph (a graph with some oriented and some unoriented edges). This is a generalized Matrix Tree Theorem. We also characterize the non-singular substructures of a mixed graph. The sign attached to a nonsingular substructure is described in terms of labeling and the number of unoriented edges included in certain paths. Nonsingular substructures may be viewed as generalized matchings, because in the case of disjoint vertex sets corresponding to the rows and columns of a minor of L, our generalized Matrix Tree Theorem provides a signed count over matchings between those vertex sets. A mixed graph is called quasi bipartite if it does not contain a non singular cycle (a cycle containing an odd number of un-oriented edges). We give several characterizations of quasi-bipartite graphs.

A Combinatorial Proof of the All Minors Matrix Tree Theorem

Seth Chaiken — 2008-02-13T09:46:02-00:00

SIAM Journal on Algebraic and Discrete Methods, Vol. 3, No. 3. (1982), pp. 319-329.

Generating functions of abstract graphs with systems applications

Ramamoorthy — 2008-02-13T09:37:16-00:00

(1964)

The Bethe lattice spin glass revisited

Marc Mezard — 2008-02-13T00:04:48-00:00

(27 Sep 2000)

So far the problem of a spin glass on a Bethe lattice has been solved only at the replica symmetric level, which is wrong in the spin glass phase. Because of some technical difficulties, attempts at deriving a replica symmetry breaking solution have been confined to some perturbative regimes, high connectivity lattices or temperature close to the critical temperature. Using the cavity method, we propose a general non perturbative solution of the Bethe lattice spin glass problem at a level of approximation which is equivalent to a one step replica symmetry breaking solution. The results compare well with numerical simulations. The method can be used for many finite connectivity problems appearing in combinatorial optimization.

Discrete and Combinatorial Mathematics, Fifth Edition

Ralph Grimaldi — 2005-12-19T07:50:50-00:00

(17 July 2003)

Graph Theory (Graduate Texts in Mathematics)

Reinhard Diestel — 2005-11-15T21:49:00-00:00

(22 August 2005)

The third edition of this highly successful textbook has been carefully revised and updated, and includes a new chapter on infinite graphs. The book covers all major, recent developments, and can be used both as a reliable textbook for an introductory course and as a graduate text: on each topic it covers all the basic material in full detail, and adds one or two deeper results (again with detailed proofs) to illustrate the more advanced methods of that field. From the reviews of the first two editions (1997, 2000): "This outstanding book cannot be substituted with any other book on the present textbook market. It has every chance of becoming the standard textbook for graph theory." Acta Scientiarum Mathematicarum "The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theory." Bulletin of the Institute of Combinatorics and its Applications "A highlight of the book is what is by far the best account in print of the Seymour-Robertson theory of graph minors." Mathematika ". . . like listening to someone explain mathematics." Bulletin of the AMS

Counting without sampling. New algorithms for enumeration problems using statistical physics

Antar Bandyopadhyay — 2005-10-25T05:06:39-00:00

(21 Oct 2005)

We propose a new type of approximate counting algorithms for the problems of enumerating the number of independent sets and proper colorings in low degree graphs with large girth. Our algorithms are not based on a commonly used Markov chain technique, but rather are inspired by developments in statistical physics in connection with correlation decay properties of Gibbs measures and its implications to uniqueness of Gibbs measures on infinite trees, reconstruction problems and local weak convergence methods. On a negative side, our algorithms provide $ε$-approximations only to the logarithms of the size of a feasible set (also known as free energy in statistical physics). But on the positive side, our approach provides deterministic as opposed to probabilistic guarantee on approximations. Moreover, for some regular graphs we obtain explicit values for the counting problem. For example, we show that every 4-regular $n$-node graph with large girth has approximately $(1.494...)^n$ independent sets, and in every $r$-regular graph with $n$ nodes and large girth the number of $q≥ r+1$-proper colorings is approximately $[q(1-1over q)^rover 2]^n$, for large $n$. In statistical physics terminology, we compute explicitly the limit of the log-partition function. We extend our results to random regular graphs. Our explicit results would be hard to derive via the Markov chain method.

Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics

Graham Brightwell — 2008-02-11T22:40:03-00:00

(28 Apr 2003)

Statistical physics models with hard constraints, such as the discrete hard-core gas model (random independent sets in a graph), are inherently combinatorial and present the discrete mathematician with a relatively comfortable setting for the study of phase transition. In this paper we survey recent work (concentrating on joint work of the authors) in which hard-constraint systems are modeled by the space $\hom(G,H)$ of homomorphisms from an infinite graph $G$ to a fixed finite constraint graph $H$. These spaces become sufficiently tractable when $G$ is a regular tree (often called a Cayley tree or Bethe lattice) to permit characterization of the constraint graphs $H$ which admit multiple invariant Gibbs measures. Applications to a physics problem (multiple critical points for symmetry-breaking) and a combinatorics problem (random coloring), as well as some new combinatorial notions, will be presented.

The independence polynomial of a graph - a survey

Levit — 2008-02-11T22:29:10-00:00

(2005)

A stable (or independent) set in a graph is a set of pairwise non-adjacent vertices. The stability number ®(G) is the size of a maximum stable set in the graph G. There are three different kinds of structures that one can see observing behavior of stable sets of a graph: the enumerative structure, the intersection structure, and the exchange structure. The independence polynomial of G I(G; x) = ®(G) Xk=0 skxk = s0 + s1x + s2x2 + ::: + s®(G)x®(G); defined by Gutman and Harary (1983), is a good representative of the enumerative structure (sk is the number of stable sets of cardinality k in a graph G). One of the most general approaches to graph polynomials was proposed by Farrell (1979) in his theory of F-polynomials of a graph. According to Farrell, any such polynomial corresponds to a strictly prescribed family of connected subgraphs of the respective graph. For the matching polynomial of a graph G, this family consists of all the edges of G, for the independence polynomial of G, this family includes all the stable sets of G. In fact, various aspects of combinatorial information concerning a graph is stored in the coefficients of a specific graph polynomial. In this paper, we survey the most important results referring the independence polynomial of a graph.

Percolation and the hard-core lattice gas model

J van den Berg — 2007-06-03T20:38:17-00:00

Stochastic Processes and their Applications, Vol. 49, No. 2. (February 1994), pp. 179-197.

Recently a uniqueness condition for Gibbs measures in terms of disagreement percolation (a type of dependent percolation involving two realizations) has been obtained. In general this condition is sufficient but not necessary for uniqueness. In the present paper we study the hard-core lattice gas model which we abbreviate as hard-core model. This model is not only relevant in Statistical Physics, but was recently rediscovered in Operations Research in the context of certain communication networks. First we show that the uniqueness result mentioned above implies that the critical activity for the hard-core model on a graph is at least Pc/(1 - Pc), where Pc is the critical probability for site percolation on that graph. Then, for the hard-core model on bi-partite graphs, we study the probability that a given vertex v is occupied under the two extreme boundary conditions, and show that the difference can be written in terms of the probability of having a `path of disagreement' from v to the boundary. This is the key to a proof that, for this case, the uniqueness condition mentioned above is also necessary, i.e. roughly speaking, phase transition is equivalent with disagreement percolation in the product space. Finally, we discuss the hard-core model on d with two different values of the activity, one for the even, and one for the odd vertices. It appears that the question whether this model has a unique Gibbs measure, can, in analogy with the standard ferromagnetic Ising model, be reduced to the question whether the third central moment of the surplus of odd occupied vertices for a certain class of finite boxes is negative.

Algorithms for Random Generation and Counting: A Markov Chain Approach (Progress in Theoretical Computer Science)

A Sinclair — 2008-02-11T21:44:45-00:00

(01 February 1993)

This monograph studies two classical computational problems: counting the elements of a finite set of combinatorial structures, and generating them at random from some probability distribution. Apart from their intrinsic interest, these problems arise naturally in many branches of mathematics and the natural sciences. The author aims to classify the computational difficulty of these problems for various naturally occurring structures: the emphasis is on positive results that demonstrate the existence of efficient algorithms. At the heart of the monograph is a single algorithmic paradigm; simulate a Markov chain whose states are combinatorial structures. A major portion of the monograph is devoted to developing new mathematical tools for the analysis of algorithms of this kind. Among the applications presented are the first provably efficient algorithms for several important counting and generation problems. Further applications are summarized in an appendix. This book will be of interest to researchers and graduate students in theoretical computer science, probability and statistics and theoretical physicists with an interest in Monte Carlo methods. It is a timely contribution to a fast moving field, with the immediacy and freshness of a new discovery.

A second threshold for the hard-core model on a Bethe lattice

Graham Brightwell — 2008-02-11T08:56:08-00:00

Random Structures and Algorithms, Vol. 24, No. 3. (2004), pp. 303-314.

We determine the approximate value of a critical activity for the hard-core model on the Bethe lattice, which determines whether the unique simple invariant Gibbs measure is extremal. This ?recovery threshold? turns out to be different both from the threshold for unique Gibbs measure and (in contrast to the Ising model) from the threshold for recovery of root information using only statistical information about distant sites. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004

Modeling and Estimation in Gaussian Graphical Models: Maximum-Entropy Methods and Walk-Sum Analysis

Venkat Chandrasekaran — 2008-02-08T17:45:11-00:00

(2007)

Graphical models provide a powerful formalism for statistical signal processing. Due to their sophisticated modeling capabilities, they have found applications in a variety of fields such as computer vision, image processing, and distributed sensor networks. In this thesis we study two central signal processing problems involving Gaussian graphical models, namely modeling and estimation. The modeling problem involves learning a sparse graphical model approximation to a specified distribution. The estimation problem in turn exploits this graph structure to solve high-dimensional estimation problems very efficiently. We propose a new approach for learning a thin graphical model approximation to a specified multivariate probability distribution (e.g., the empirical distribution from sample data). The selection of sparse graph structure arises naturally in our approach through the solution of a convex optimization problem, which differentiates our procedure from standard combinatorial methods. In our approach, we seek the maximum entropy relaxation (MER) within an exponential family, which maximizes entropy subject to constraints that marginal distributions on small subsets of variables are close to the prescribed marginals in relative entropy. We also present a primal-dual interior point method that is scalable and tractable provided the level of relaxation is sufficient to obtain a thin graph. A crucial element of this algorithm is that we exploit sparsity of the Fisher information matrix in models defined on chordal graphs. The merits of this approach are investigated by recovering the graphical structure of some simple graphical models from sample data. Next, we present a general class of algorithms for estimation in Gaussian graphical models with arbitrary structure. These algorithms involve a sequence of inference problems on tractable subgraphs over subsets of variables. This framework includes parallel

Covariance decomposition in undirected Gaussian graphical models

Beatrix Jones — 2005-11-16T16:36:41-00:00

Biometrika, Vol. 92, No. 4. (December 2005), pp. 779-786.

Walk-Sums and Belief Propagation in Gaussian Graphical Models

Dmitry Malioutov — 2007-12-16T10:05:22-00:00

Journal of Machine Learning Research, Vol. 7 (October 2006)

We present a new framework based on walks in a graph for analysis and inference in Gaussian graphical models. The key idea is to decompose the correlation between each pair of variables as a sum over all walks between those variables in the graph. The weight of each walk is given by a product of edge-wise partial correlation coefficients. This representation holds for a large class of Gaussian graphical models which we call walk-summable. We give a precise characterization of this class of...

How to Compute Loop Corrections to Bethe Approximation

Andrea Montanari — 2008-02-07T04:28:28-00:00

(29 Jun 2005)

We introduce a method for computing corrections to Bethe approximation for spin models on arbitrary lattices. Unlike cluster variational methods, the new approach takes into account fluctuations on all length scales. The derivation of the leading correction is explained and applied to two simple examples: the ferromagnetic Ising model on d-dimensional lattices, and the spin glass on random graphs (both in their high-temperature phases). In the first case we rederive the well-known Ginzburg criterion and the upper critical dimension. In the second, we compute finite-size corrections to the free energy.

Graph Walks and Graphical Models

William Cohen — 2008-02-07T01:24:26-00:00

(2007)

Inference in Markov random fields, and development and evaluation of similarity measures for nodes in graphs, are both active areas of data-mining research. In this paper, we demonstrate a formal connection between inference in tree-structured Markov random fields and personalized PageRank, a widely-used similarity measure for graph nodes based on graphwalks. In particular we show a connection between computation of marginal probabilities in tree-structured discrete-variable pairwise MRFs, and computation of similarity between vertices of a graph using the personalized PageRank measure: roughly speaking, for these MRFs, computing a marginal probability Pr(Xi = j) can be reduced to computing a small set of personalized-PageRank similarity vectors, followed by a very limited postprocessing stage.

Excluded-Volume Problem and the Ising Model of Ferromagnetism

Michael Fisher — 2008-02-07T00:08:38-00:00

Physical Review, Vol. 114, No. 1. (1 April 1959), 45.

The relationship between the excluded-volume problem for a discrete random walk on a lattice and the corresponding Ising model of ferromagnetism is investigated. Systematic methods are presented for the construction of rigorous lower bounds to the limit μ=lim n →∞ ( c n +1 / c n ); where c n is the number of n -step self-avoiding walks on a given lattice. In this way Temperley's conjecture that μ=coth( J / k T C ); where T C is the Curie temperature of the corresponding Ising-model ferromagnet; is disproved. The series c n for various two- and three-dimensional lattices have been enumerated exactly for values of n from ten to twenty. Extrapolation of these series; by procedures known to be valid from exact Ising-model results; yields more accurate values of μ than Wall's statistical calculations and also shows that c n ∼ n α μ n where α≃1 / 3 for plane lattices and α≃1 / 7 for three-dimensional lattices. This means that the entropy of the n th "link" of a polymer molecule in solution should vary as δ S n = k lnμ+ k α / n . The relevance of these results to the interpretation of the boundary tension of the Ising model; to the critical behavior of gases; and to the mean square size of a polymer molecule is discussed briefly.

On some extremal problems in graph theory

Dmitry Jakobson — 2008-02-06T23:58:42-00:00

(8 Jul 1999)

In this paper we are concerned with various graph invariants (girth, diameter, expansion constants, eigenvalues of the Laplacian, tree number) and their analogs for weighted graphs -- weighing the graph changes a combinatorial problem to one in analysis. We study both weighted and unweighted graphs which are extremal for these invariants. In the unweighted case we concentrate on finding extrema among all (usually) regular graphs with the same number of vertices; we also study the relationships between such graphs.

On Connected Diagrams and Cumulants of Erdos-Renyi Matrix Models

O Khorunzhiy — 2008-02-06T23:56:01-00:00

(10 Jul 2007)

Regarding the adjacency matrices of n-vertex graphs and related graph Laplacian, we introduce two families of discrete matrix models constructed both with the help of the Erdos-Renyi ensemble of random graphs. Corresponding matrix sums represent the characteristic functions of the average number of walks and closed walks over the random graph. These sums can be considered as discrete analogs of the matrix integrals of random matrix theory. We study the diagram structure of the cumulant expansions of logarithms of these matrix sums and analyze the limiting expressions in the cases of constant and vanishing edge probabilities as n tends to infinity.

Algebraic Graph Theory (Cambridge Mathematical Library)

Norman Biggs — 2005-11-21T23:59:06-00:00

(03 February 1994)

A revision of an important textbook: essential reading for all combinatorialists.

Inference in Binary Pair-wise Markov Random Fields through Self-Avoiding Walks

Kyomin Jung — 2008-02-06T21:12:56-00:00

(3 Oct 2007)

In a recent result, Weitz \citeWei06 established equivalence between the marginal distribution of a node, say $v$, in any binary pair-wise Markov Random Field (MRF), say $G$, with the marginal distribution of the root node in the self-avoid walk tree of the $G$ starting at $v$. In this paper, we exploit this remarkable connection to obtain insights in the performance of the widely popular Belief Propagation heuristic for computing marginal distribution (sum-product) and max-marginal distribution (max-product). We obtain a tight characterization of the size of self-avoiding walk tree for any connected graph as a function of number of edges. This may be of interest in its own right.

TP Decoding

Yi Lu — 2008-02-06T21:05:30-00:00

(2 Oct 2007)

`Tree pruning' (TP) is an algorithm for probabilistic inference on binary Markov random fields. It has been recently derived by Dror Weitz and used to construct the first fully polynomial approximation scheme for counting independent sets up to the `tree uniqueness threshold.' It can be regarded as a clever method for pruning the belief propagation computation tree, in such a way to exactly account for the effect of loops. In this paper we generalize the original algorithm to make it suitable for decoding linear codes, and discuss various schemes for pruning the computation tree. Further, we present the outcomes of numerical simulations on several linear codes, showing that tree pruning allows to interpolate continuously between belief propagation and maximum a posteriori decoding. Finally, we discuss theoretical implications of the new method.

The electrical resistance of a graph captures its commute and cover times

AK Chandra — 2007-11-21T13:30:39-00:00

(1989), pp. 574-586.

. View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance R st between s and t: commute time =...

Electric currents in infinite networks

Peter Doyle — 2008-02-06T08:16:26-00:00

(29 Mar 2007)

In this survey, we present the basic facts about conduction in infinite networks. This survey is based on the work of Flanders, Zemanian, and Thomassen, who developed the theory of infinite networks from scratch. Here we show how to get a more complete theory by paralleling the well-developed theory of conduction on open Riemann surfaces. Like Flanders and Thomassen, we take as a test case for the theory the problem of determining the resistance across an edge of a d-dimensional grid of 1-ohm resistors.

Broadcasting on Trees and the Ising Model

William Evans — 2008-02-05T01:44:27-00:00

The Annals of Applied Probability, Vol. 10, No. 2. (2000), pp. 410-433.