event thumbnail image
The 13th International Conference on Knowledge Discovery and Data Mining

Hierarchical Mixture Models: a Probabilistic Analysis

author: Mark Sandler, Google

Description

Mixture models form one of the most widely used classes of generative models for describing structured and clustered data. In this paper we develop a new approach for the analysis of hierarchical mixture models. More specifically, using a text clustering problem as a motivation, we describe a natural generative process that creates a hierarchical mixture model for the data. In this process, an adversary starts with an arbitrary base distribution and then builds a topic hierarchy via some evolutionary process, where he controls the parameters of the process. We prove that under our assumptions, given a subset of topics that represent generalizations of one another (such as baseball - sports - base), for any document which was produced via some topic in this hierarchy, we can efficiently determine the most specialized topic in this subset, it still belongs to. The quality of the classification is independent of the total number of topics in the hierarchy and our algorithm does not need to know the total number of topics in advance. Our approach also yields an algorithm for clustering and unsupervised topical tree reconstruction. We validate our model by showing that properties predicted by our theoretical results carry over to real data. We then apply our clustering algorithm to two different datasets: (i) “20 newsgroups” [19] and (ii) a snapshot of abstracts of arXiv [2] (15 categories, 240,000 abstracts). In both cases our algorithm performs extremely well.

You might be experiencing some problems with Your Video player.
Slides
0:00 Hierarchical Mixture Models
0:12 Mixture models: quick overview
1:39 Topical Hierarchy
2:55 Our results
4:25 Generative model for the topical hierarchy
5:10 Generative model for the hierarchy
6:07 Distributions satisfy a few conditions
7:13 Related work: reconstructing hierarchies
8:02 Our results
8:13 Classification along the path in the tree
8:43 Algorithm when a path in the hierarchy is known
9:43 Why does it work? Part 1: back to plain mixtures
10:49 Generalized pseudoinverse
11:28 Part II –still, why does it work?
12:47 Reconstructing hierarchy from unlabeled data
13:56 Overview of the rest of the talk
14:04 Experiments: abstracts from ArXiV
14:31 Experiments: ArXiV
15:35 Newsgroup 20
16:04 Experiments: Newsgroups
16:59 Conclusions

Lecture rating

People found this lecture:
Worth seeing
because it is:
 Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment: