Theoretical study of two prediction-centric problems : graphical model learning and recommendations
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/114030 |
| _version_ | 1811074615203594240 |
|---|---|
| author | Karzand, Mina |
| author2 | Lizhong Zheng and Guy Bresler. |
| author_facet | Lizhong Zheng and Guy Bresler. Karzand, Mina |
| author_sort | Karzand, Mina |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017. |
| first_indexed | 2024-09-23T09:52:38Z |
| format | Thesis |
| id | mit-1721.1/114030 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:52:38Z |
| publishDate | 2018 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1140302019-04-11T07:52:03Z Theoretical study of two prediction-centric problems : graphical model learning and recommendations Karzand, Mina Lizhong Zheng and Guy Bresler. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 177-184). 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. by Mina Karzand. Ph. D. 2018-03-06T21:34:46Z 2018-03-06T21:34:46Z 2017 2017 Thesis http://hdl.handle.net/1721.1/114030 1023811505 eng 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. http://dspace.mit.edu/handle/1721.1/7582 184 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Karzand, Mina Theoretical study of two prediction-centric problems : graphical model learning and recommendations |
| title | Theoretical study of two prediction-centric problems : graphical model learning and recommendations |
| title_full | Theoretical study of two prediction-centric problems : graphical model learning and recommendations |
| title_fullStr | Theoretical study of two prediction-centric problems : graphical model learning and recommendations |
| title_full_unstemmed | Theoretical study of two prediction-centric problems : graphical model learning and recommendations |
| title_short | Theoretical study of two prediction-centric problems : graphical model learning and recommendations |
| title_sort | theoretical study of two prediction centric problems graphical model learning and recommendations |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/114030 |
| work_keys_str_mv | AT karzandmina theoreticalstudyoftwopredictioncentricproblemsgraphicalmodellearningandrecommendations |