Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration

DOI10.1007/978-3-642-40328-6_24MaRDI QIDQ2851867zbMATH OpenOpenAlexFDO

Authors Emmanuel Abbe, Andrea Montanari

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.4274

zbMATH Keywords

community clusteringconcentrationconstraint satisfaction problemsentropygraphical modelsinterpolation methodparity-check codesplanted models

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random fields (60G60) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Measures of information, entropy (94A17)

Abstract: This paper studies a class of probabilistic models on graphs, where edge variables depend on incident node variables through a fixed probability kernel. The class includes planted con- straint satisfaction problems (CSPs), as well as more general structures motivated by coding and community clustering problems. It is shown that under mild assumptions on the kernel and for sparse random graphs, the conditional entropy of the node variables given the edge variables concentrates around a deterministic threshold. This implies in particular the concentration of the number of solutions in a broad class of planted CSPs, the existence of a threshold function for the disassortative stochastic block model, and the proof of a conjecture on parity check codes. It also establishes new connections among coding, clustering and satisfiability.

Recommendations

• Conditional random fields, planted constraint satisfaction, and entropy concentration
• Relational probabilistic conditional reasoning at maximum entropy
• scientific article; zbMATH DE number 5547880
• An introduction to conditional random fields
• Discriminative training of conditional random fields with probably submodular constraints
• Efficient approximation of the conditional relative entropy with applications to discriminative learning of Bayesian network classifiers
• Models for Random Constraint Satisfaction Problems
• Principles and Practice of Constraint Programming – CP 2004
• Exploiting entropy in constraint programming

Cited in

(6)

• Replica bounds by combinatorial interpolation for diluted spin systems
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Conditional random fields, planted constraint satisfaction, and entropy concentration
• Asymptotic mutual information for the balanced binary stochastic block model
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Finding one community in a sparse graph

This page was built for publication: Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851867)