Mode Estimation for High Dimensional Discrete Tree Graphical Models
This paper studies the following problem: given samples from a high dimensional discrete distribution, we want to estimate the leading (δ, ρ)-modes of the underlying distributions. A point is defined to be a (δ, ρ)-mode if it is a local optimum of the density within a δ-neighborhood under metric ρ. As we increase the "scale" parameter δ, the neighborhood size increases and the total number of modes monotonically decreases. The sequence of the (δ, ρ)-modes reveal intrinsic topographical information of the underlying distributions. Though the mode finding problem is generally intractable in high dimensions, this paper unveils that, if the distribution can be approximated well by a tree graphical model, mode characterization is significantly easier. An efficient algorithm with provable theoretical guarantees is proposed and is applied to applications like data analysis and multiple predictions.
Description:The paper presents an efficient algorithm to compute modes of theprobability distribution over many discrete variables defined by atree-structured graphical model. More precisely, given a (eg Hamming)metric and a constant delta, a labeling is a delta-mode if it hasgreater probability than all other labelings within distancedelta. The proposed algorithm computes M best modes for each scaledelta. The complexity of the algorithm is exponential in theory butreasonable empirically.The algorithm uses a newly derived relation between local and globalmodes. A local delta-mode is a labeling on a subgraph whch has higherprobability than all other labelings on the subgraph within distancedelta and with the same labeling on the boundary. Given a rich enoughcollection of subgraphs of the original graph, a labeling is a globaldelta-mode iff its restrictions to subgraphs are localdelta-modes. This implies that local delta-modes that are consistent(agree on overlapping variables) define a global mode.For a tree-structured model, the collection of subgraphs has apolynomial size (they are delta-balls). The algorithm first finds alllocal delta-modes for each subgraph. This is done by enumerating allboundary labelings and then finding the maximum probability for eachsuch labeling (there is a non-trivial insight in this algorithm,though). Then, the algorithm constructs a junction tree graphicalmodel whose nodes are the subgraphs, labels are the local modes, andwhose probability is the probability of the global mode if the localmodes are consistent and zero otherwise. Now, M best labelings(computed by the existing algorithm [16]) in this junction tree modelcorresponds to M best delta-modes in the original tree. Thus, theproblem of finding M best modes has been reduced to the known problemof finding M best labelings.When increasing delta, a mode can only disappear but neverappear. Modes for various delta thus form somethng like a scale space.When we want to compute the modes for all scales delta, the modes forsome delta can be computed efficiently from already computed modes fordelta-1. Thus, the above costly enumeration must be done only fordelta=1.Besides the algorithm, the paper presents theoretical guarantees thatdelta-modes are stable under errors in estimating the tree fromsamples, using the method from [1].The algorithm is verified in several experiments. One uses syntheticdata, the other real biological data, and the third (in thesupplement) image segmentation from superpixels by CRF. Theexperiments suggest that the number of local as well as global modesis managable in practice. The runtime is tens of seconds for treeswith 2000 nodes. On image segmentation, the method almost always yields better results than the M-best diverse labeling method by [Batra et al, ECCV'12].Comments:This is very good paper with a lot of work behind it. It is a goodstep towards practical algorithms for finding multiple modes of agraphical model. I have no major objections. Minor objections are asfollows.In Figure 3a, the uncertainty bars are wrong because runtime cannot benegative.To my understanding, for a fixed delta the algorithm finds not alldelta-modes but only M best delta-modes. But you never state what M wasin your experiments.The text contains a number of very minor language mistakes, such as"it is a local optima" (l.17), "inversely logarithm proportional"(l.107).On l.247: Why don't you write y_c\in L istead of y_c=\ell, \ell\in L.