Entropy, Optimization and Counting Abstract
In this talk I will discuss the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. For instance, given a bipartite graph and a positive number for every edge, can we compute a probability distribution that maximizes entropy over the set of perfect matching in the graph whose marginals are the given numbers for the edges?
There has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms. However, a rigorous and systematic study of how to compute such distributions has been lacking. Since the underlying set of discrete objects can be exponential in the input size, the first question is whether max-entropy distributions have polynomially-sized descriptions. We start by giving a structural result which shows that such succinct descriptions exist under very general conditions. Subsequently, we use techniques from convex programming to give a meta-algorithm that can efficiently (approximately) compute max-entropy distributions provided one can efficiently (approximately) count the underlying discrete set. Thus, we can translate a host of existing counting algorithms, developed in an unrelated context, into algorithms that compute max-entropy distributions.
Conversely, we prove that counting oracles are necessary for computing max-entropy distributions: namely, we show how algorithms that compute max-entropy distributions can be converted into counting algorithms.
Reference and Copyrights:
Nisheeth Vishnoi
Microsoft Research, India
Entropy, Optimization and Counting, from IIT Kanpur
We prepared and published this seminar abstract for final year engineering students seminar research. You should do your own research additional to this information before presenting your seminar.
Please include "Reference: Collegelib.com" and link back to this page in your work.
Subscribe via email for more Latest topics
12 Steps to boost your innovative project ideas
In this talk I will discuss the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. For instance, given a bipartite graph and a positive number for every edge, can we compute a probability distribution that maximizes entropy over the set of perfect matching in the graph whose marginals are the given numbers for the edges?
There has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms. However, a rigorous and systematic study of how to compute such distributions has been lacking. Since the underlying set of discrete objects can be exponential in the input size, the first question is whether max-entropy distributions have polynomially-sized descriptions. We start by giving a structural result which shows that such succinct descriptions exist under very general conditions. Subsequently, we use techniques from convex programming to give a meta-algorithm that can efficiently (approximately) compute max-entropy distributions provided one can efficiently (approximately) count the underlying discrete set. Thus, we can translate a host of existing counting algorithms, developed in an unrelated context, into algorithms that compute max-entropy distributions.
Conversely, we prove that counting oracles are necessary for computing max-entropy distributions: namely, we show how algorithms that compute max-entropy distributions can be converted into counting algorithms.
Reference and Copyrights:
Nisheeth Vishnoi
Microsoft Research, India
Entropy, Optimization and Counting, from IIT Kanpur
We prepared and published this seminar abstract for final year engineering students seminar research. You should do your own research additional to this information before presenting your seminar.
Please include "Reference: Collegelib.com" and link back to this page in your work.
Subscribe via email for more Latest topics
12 Steps to boost your innovative project ideas