Maximum Likelihood Bounded Tree-Width Markov Networks
- Nathan Srebro, Maximum Likelihood Markov Networks: An
Algorithmic Approach, MSc Thesis, Massachusetts Institute of
Technology, October 2000. [PDF]
- Contains most of the results of the SODA and UAI papers, as well
as several additional proofs and constructions. In particular,
includes the reduction of 3SAT to Max-Hypertree. Also
provides tutorials on Markov networks and on tree-width, and a survey
on various equivalent characterizations of tree-width.
- David Karger and Nathan Srebro, Learning
Markov Networks: Maximum Bounded Tree-width Graphs, In
Proceedings of the 12th ACM-SIAM Symposium on Discrete
Algorithms, January 2001. [PDF]
- Defines the maximum-hypertree problem and provides a constant
factor approximation algorithm for it.
- Nathan Srebro, Maximum Likelihood Bounded Tree-Width Markov
Networks, in The 17th Conference on Uncertainty in
Artificial Intelligence, August 2001 (Best Student
Paper). [PDF]
(presentation slides and poster)
-
We study the problem of projecting a distribution onto (or finding a
maximum likelihood distribution among) Markov networks of bounded
tree-width. By casting it as the combinatorial optimization problem of
finding a maximum weight hypertree, we prove that it is NP-hard to
solve exactly and provide an approximation algorithm with a provable
performance guarantee.
Nathan Srebro, Maximum Likelihood Bounded Tree-Width Markov
Networks, in
Artificial Intelligence . [PDF]
An expanded version of the UAI paper, including more details and a
discussion of PAC learning of bounded tree-width Markov networks.
Percy Liang and Nathan Srebro, A Dynamic Data Structure for Checking Hyperacyclicity. [PDF]
We present a dynamic data structure that keeps track of of an acylic hypergraph and enables
verifying that adding a candidate hyperedge will not break the acyclicity of
the augmented hypergraph. This is a generalization of the use of Tarjan's
Union-Find data structure for maintaining acyclicity when augmenting forests,
and the amortized time per operation has a similar almost-constant dependence
on the size of the hypergraph.
Percy Liang and Nathan Srebro, How Much of a Hypertree Can Be Captured by Windmills?. [PDF]
Current approximation algorithms for maximum weight hypertrees
find heavy windmill farms, and are based on the fact that a
constant ratio (for constant width k) of the weight of a k-hypertree
can be captured by a k-windmill farm. However, the exact worst case
ratio is not known and is only bounded to be between 1/(k+1)! and
1/(k+1). We investigate this worst case ratio by searching for
weighted hypertrees that minimize the ratio of their weight that can
be captured with a windmill farm. To do so, we use a novel approach in
which a linear program is used to find "bad" inputs to a dynamic
program.
Percy Liang and Nathan Srebro, Methods and Experiments With Bounded Tree-width Markov Networks. [PDF]
Markov trees generalize naturally to bounded tree-width Markov
networks, on which exact computations can still be done
efficiently. However, learning the maximum likelihood Markov network
with tree-width greater than 1 is NP-hard, so we discuss a few
algorithms for approximating the optimal Markov network. We present a
set of methods for training a density estimator. Each method is
specified by three arguments: tree-width, model scoring metric
(maximum likelihood or minimum description length), and model
representation (using one joint distribution or several
class-conditional distributions). On these methods, we give empirical
results on density estimation and classification tasks and explore the
implications of these arguments.
Percy Liang and Nathan Srebro, Linear Programming in Bounded Tree-width Markov Networks. [Percy's slides]
A presentation given by Percy Liang at the 2005 Mathematical Programing for Data Mining and Machine Learning Workshop at McMaster University.
Nati Srebro
Last modified: Thu Sep 01 10:08:56 Eastern Daylight Time 2005