Entropy, optimization and counting

摘要: We study the problem of computing max-entropy distributions over a discrete set objects subject to observed marginals. There has been tremendous amount interest in such due their applicability areas as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms. However, rigorous systematic how compute lacking. Since underlying can be exponential input size, first question is if have polynomially-sized descriptions. start by giving structural result which shows that succinct descriptions exist under very general conditions. Subsequently, we use techniques from convex programming give meta-algorithm efficiently (approximately) provided one count set. Thus, translate host existing counting algorithms, developed an unrelated context, into algorithms distributions. Conversely, prove oracles are necessary for distributions: show converted