Masatran, Rajasekaran

IIT MadrasYahooBTech, IIIT Hyderabad.

A Marginal-Based Technique for Distribution Estimation

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.

A Latent-Variable Lattice Model

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.

Algebraic MDP Minimization Using the Graph Laplacian

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.