Theoretical study of two prediction-centric problems : graphical model learning and recommendations

Motivated by prediction-centric learning problems, two problems are discussed in this thesis. PART I. Learning a tree-structured Ising model: We study the problem of learning a tree Ising model from samples such that subsequent predictions based on partial observations are accurate. Virtually all previous work on graphical model learning has focused on recovering the true underlying graph. We dene a distance ("small set TV" or ssTV) between distributions P and Q by taking the maximum, over all subsets S of a given size, of the total variation between the marginals of P and Q on S; this distance captures the accuracy of the prediction task of interest. We derive non-asymptotic bounds on the number of samples needed to get a distribution (from the same class) with small ssTV relative to the one generating the samples. An implication is that far fewer samples are needed for accurate predictions than for recovering the underlying tree. PART II. Optimal online algorithms for a latent variable model of recommendation systems: We consider an online model for recommendation systems, with each user being recommended an item at each time-step and providing 'like' or 'dislike' feedback. The user preferences are specified via a latent variable model: both users and items are clustered into types. The model captures structure in both the item and user spaces, and our focus is on simultaneous use of both structures. In the case when the type preference matrix is randomly generated, we provide a sharp analysis of the best possible regret obtainable by any algorithm.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2017

Author dc:creator

• Karzand, Mina

Advisor dc:contributor.advisor

• Lizhong Zheng and Guy Bresler.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/114030

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/114030