IIT Madras — Yahoo — BTech, IIIT Hyderabad.

Abstract: Estimating a distribution over a vector random variable, given a source of independent random instances drawn from the distribution, is a standard problem in statistics. Frequently, the components have limited dependency between each other, and this can be exploited for estimation with fewer samples. We propose a novel technique that estimates the distribution efficiently, using one-dimensional marginals. Like naive bayes, our technique is suited to incremental estimation. Compared to the naive bayes assumption, our technique provides better accuracy, but only at higher dimensionality. Experiments on datasets of different dimensionality support our claims.

Abstract:
Markov random field (MRF) learning is intractable, and its approximation
algorithms are computationally expensive. We target a small subset of MRF that
is used frequently in computer vision. We characterize this subset with three
concepts: Lattice, Homogeneity, and Inertia; and design a non-markov model as
an alternative. Our goal is robust learning from small datasets. Our learning
algorithm uses vector quantization and, at time complexity *O(u log(u))* for a
dataset of *u* pixels, is much faster than that of general-purpose MRF.

Abstract:
The *Markov decision process* is the standard model for sequential
decision problems. Identification of MDP isomorphisms allows us to minimize it,
speeding up the solution process. To minimize the MDP, we reduce it to a Markov
chain using the uniform random walk policy. Markov chain isomorphism is
essentially *directed weighted graph matching*. Ours is the first attempt
at using the laplacian to compute MDP isomorphisms. We introduce the problem,
formulate it, and propose a solution using the graph laplacian.
Eigendecomposition of the adjacency matrix and other laplacian matrices
provides descriptive graph invariants (Graph invariant: A property of
the graph that is unchanged under relabeling of the vertices.). We use the
eigendecompositions of the symmetrized adjacency matrices to find all matching
close to the optimal one. The proposed method is *analytic*, as opposed to
combinatorial or iterative. We use the solution to weighted graph matching to
construct the minimized MDP. Experiments show that this method is indeed
resistant to noise.