Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration

DOI10.1007/978-3-642-40328-6_24zbMATH Open1383.68057arXiv1305.4274OpenAlexW4230202445MaRDI QIDQ2851867FDOQ2851867

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)

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.

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

Recommendations

• Conditional random fields, planted constraint satisfaction, and entropy concentration
• Relational probabilistic conditional reasoning at maximum entropy
• scientific article
• 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

zbMATH Keywords

entropygraphical modelsconcentrationconstraint satisfaction problemsinterpolation methodparity-check codescommunity clusteringplanted models

Mathematics Subject Classification ID

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

Cited In (6)

• Asymptotic mutual information for the balanced binary stochastic block model
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Conditional random fields, planted constraint satisfaction, and entropy concentration
• Replica bounds by combinatorial interpolation for diluted spin systems
• 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)