Machine Learning: Clustering & Retrieval

About this course: Case Studies: Finding Similar Documents A reader is interested in a specific news article and you want to find similar articles to recommend. What is the right notion of similarity? Moreover, what if there are millions of other documents? Each time you want to a retrieve a new document, do you need to search through all other documents? How do you group similar documents together? How do you discover new, emerging topics that the documents cover? In this third case study, finding similar documents, you will examine similarity-based algorithms for retrieval. In this course, you will also examine structured representations for describing the documents in the corpus, including clustering and mixed membership models, such as latent Dirichlet allocation (LDA). You will implement expectation maximization (EM) to learn the document clusterings, and see how to scale the methods using MapReduce. Learning Outcomes: By the end of this course, you will be able to: -Create a document retrieval system using k-nearest neighbors. -Identify various similarity metrics for text data. -Reduce computations in k-nearest neighbor search by using KD-trees. -Produce approximate nearest neighbors using locality sensitive hashing. -Compare and contrast supervised and unsupervised learning tasks. -Cluster documents by topic using k-means. -Describe how to parallelize k-means using MapReduce. -Examine probabilistic clustering approaches using mixtures models. -Fit a mixture of Gaussian model using expectation maximization (EM). -Perform mixed membership modeling using latent Dirichlet allocation (LDA). -Describe the steps of a Gibbs sampler and how to use its output to draw inferences. -Compare and contrast initialization techniques for non-convex optimization objectives. -Implement these techniques in Python.

Created by:  University of Washington

• Taught by:  Emily Fox, Amazon Professor of Machine Learning

  Statistics

• Taught by:  Carlos Guestrin, Amazon Professor of Machine Learning

  Computer Science and Engineering

Basic Info Course 4 of 4 in the Machine Learning Specialization Commitment 6 weeks of study, 5-8 hours/week Language English How To Pass Pass all graded assignments to complete the course. User Ratings 4.6 stars Average User Rating 4.6See what learners said Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from your peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

University of Washington Founded in 1861, the University of Washington is one of the oldest state-supported institutions of higher education on the West Coast and is one of the preeminent research universities in the world.

Syllabus


WEEK 1


Welcome



Clustering and retrieval are some of the most high-impact machine learning tools out there. Retrieval is used in almost every applications and device we interact with, like in providing a set of products related to one a shopper is currently considering, or a list of people you might want to connect with on a social media platform. Clustering can be used to aid retrieval, but is a more broadly useful tool for automatically discovering structure in data, like uncovering groups of similar patients.<p>This introduction to the course provides you with an overview of the topics we will cover and the background knowledge and resources we assume you have.


4 videos, 3 readings expand

1. Reading: Slides presented in this module
2. Video: Welcome and introduction to clustering and retrieval tasks
3. Video: Course overview
4. Video: Module-by-module topics covered
5. Video: Assumed background
6. Reading: Software tools you'll need for this course
7. Reading: A big week ahead!

WEEK 2


Nearest Neighbor Search



We start the course by considering a retrieval task of fetching a document similar to one someone is currently reading. We cast this problem as one of nearest neighbor search, which is a concept we have seen in the Foundations and Regression courses. However, here, you will take a deep dive into two critical components of the algorithms: the data representation and metric for measuring similarity between pairs of datapoints. You will examine the computational burden of the naive nearest neighbor search algorithm, and instead implement scalable alternatives using KD-trees for handling large datasets and locality sensitive hashing (LSH) for providing approximate nearest neighbors, even in high-dimensional spaces. You will explore all of these ideas on a Wikipedia dataset, comparing and contrasting the impact of the various choices you can make on the nearest neighbor results produced.


22 videos, 4 readings expand

1. Reading: Slides presented in this module
2. Video: Retrieval as k-nearest neighbor search
3. Video: 1-NN algorithm
4. Video: k-NN algorithm
5. Video: Document representation
6. Video: Distance metrics: Euclidean and scaled Euclidean
7. Video: Writing (scaled) Euclidean distance using (weighted) inner products
8. Video: Distance metrics: Cosine similarity
9. Video: To normalize or not and other distance considerations
10. Reading: Choosing features and metrics for nearest neighbor search
11. Video: Complexity of brute force search
12. Video: KD-tree representation
13. Video: NN search with KD-trees
14. Video: Complexity of NN search with KD-trees
15. Video: Visualizing scaling behavior of KD-trees
16. Video: Approximate k-NN search using KD-trees
17. Reading: (OPTIONAL) A worked-out example for KD-trees
18. Video: Limitations of KD-trees
19. Video: LSH as an alternative to KD-trees
20. Video: Using random lines to partition points
21. Video: Defining more bins
22. Video: Searching neighboring bins
23. Video: LSH in higher dimensions
24. Video: (OPTIONAL) Improving efficiency through multiple tables
25. Reading: Implementing Locality Sensitive Hashing from scratch
26. Video: A brief recap

Graded: Representations and metrics
Graded: Choosing features and metrics for nearest neighbor search
Graded: KD-trees
Graded: Locality Sensitive Hashing
Graded: Implementing Locality Sensitive Hashing from scratch

WEEK 3


Clustering with k-means



In clustering, our goal is to group the datapoints in our dataset into disjoint sets. Motivated by our document analysis case study, you will use clustering to discover thematic groups of articles by "topic". These topics are not provided in this unsupervised learning task; rather, the idea is to output such cluster labels that can be post-facto associated with known topics like "Science", "World News", etc. Even without such post-facto labels, you will examine how the clustering output can provide insights into the relationships between datapoints in the dataset. The first clustering algorithm you will implement is k-means, which is the most widely used clustering algorithm out there. To scale up k-means, you will learn about the general MapReduce framework for parallelizing and distributing computations, and then how the iterates of k-means can utilize this framework. You will show that k-means can provide an interpretable grouping of Wikipedia articles when appropriately tuned.


13 videos, 2 readings expand

1. Reading: Slides presented in this module
2. Video: The goal of clustering
3. Video: An unsupervised task
4. Video: Hope for unsupervised learning, and some challenge cases
5. Video: The k-means algorithm
6. Video: k-means as coordinate descent
7. Video: Smart initialization via k-means++
8. Video: Assessing the quality and choosing the number of clusters
9. Reading: Clustering text data with k-means
10. Video: Motivating MapReduce
11. Video: The general MapReduce abstraction
12. Video: MapReduce execution overview and combiners
13. Video: MapReduce for k-means
14. Video: Other applications of clustering
15. Video: A brief recap

Graded: k-means
Graded: Clustering text data with K-means
Graded: MapReduce for k-means

WEEK 4


Mixture Models



In k-means, observations are each hard-assigned to a single cluster, and these assignments are based just on the cluster centers, rather than also incorporating shape information. In our second module on clustering, you will perform probabilistic model-based clustering that provides (1) a more descriptive notion of a "cluster" and (2) accounts for uncertainty in assignments of datapoints to clusters via "soft assignments". You will explore and implement a broadly useful algorithm called expectation maximization (EM) for inferring these soft assignments, as well as the model parameters. To gain intuition, you will first consider a visually appealing image clustering task. You will then cluster Wikipedia articles, handling the high-dimensionality of the tf-idf document representation considered.


15 videos, 4 readings expand

1. Reading: Slides presented in this module
2. Video: Motiving probabilistic clustering models
3. Video: Aggregating over unknown classes in an image dataset
4. Video: Univariate Gaussian distributions
5. Video: Bivariate and multivariate Gaussians
6. Video: Mixture of Gaussians
7. Video: Interpreting the mixture of Gaussian terms
8. Video: Scaling mixtures of Gaussians for document clustering
9. Video: Computing soft assignments from known cluster parameters
10. Video: (OPTIONAL) Responsibilities as Bayes' rule
11. Video: Estimating cluster parameters from known cluster assignments
12. Video: Estimating cluster parameters from soft assignments
13. Video: EM iterates in equations and pictures
14. Video: Convergence, initialization, and overfitting of EM
15. Video: Relationship to k-means
16. Reading: (OPTIONAL) A worked-out example for EM
17. Video: A brief recap
18. Reading: Implementing EM for Gaussian mixtures
19. Reading: Clustering text data with Gaussian mixtures

Graded: EM for Gaussian mixtures
Graded: Implementing EM for Gaussian mixtures
Graded: Clustering text data with Gaussian mixtures

WEEK 5


Mixed Membership Modeling via Latent Dirichlet Allocation



The clustering model inherently assumes that data divide into disjoint sets, e.g., documents by topic. But, often our data objects are better described via memberships in a collection of sets, e.g., multiple topics. In our fourth module, you will explore latent Dirichlet allocation (LDA) as an example of such a mixed membership model particularly useful in document analysis. You will interpret the output of LDA, and various ways the output can be utilized, like as a set of learned document features. The mixed membership modeling ideas you learn about through LDA for document analysis carry over to many other interesting models and applications, like social network models where people have multiple affiliations.<p>Throughout this module, we introduce aspects of Bayesian modeling and a Bayesian inference algorithm called Gibbs sampling. You will be able to implement a Gibbs sampler for LDA by the end of the module.


12 videos, 2 readings expand

1. Reading: Slides presented in this module
2. Video: Mixed membership models for documents
3. Video: An alternative document clustering model
4. Video: Components of latent Dirichlet allocation model
5. Video: Goal of LDA inference
6. Video: The need for Bayesian inference
7. Video: Gibbs sampling from 10,000 feet
8. Video: A standard Gibbs sampler for LDA
9. Video: What is collapsed Gibbs sampling?
10. Video: A worked example for LDA: Initial setup
11. Video: A worked example for LDA: Deriving the resampling distribution
12. Video: Using the output of collapsed Gibbs sampling
13. Video: A brief recap
14. Reading: Modeling text topics with Latent Dirichlet Allocation

Graded: Latent Dirichlet Allocation
Graded: Learning LDA model via Gibbs sampling
Graded: Modeling text topics with Latent Dirichlet Allocation

WEEK 6


Hierarchical Clustering & Closing Remarks



In the conclusion of the course, we will recap what we have covered. This represents both techniques specific to clustering and retrieval, as well as foundational machine learning concepts that are more broadly useful.<p>We provide a quick tour into an alternative clustering approach called hierarchical clustering, which you will experiment with on the Wikipedia dataset. Following this exploration, we discuss how clustering-type ideas can be applied in other areas like segmenting time series. We then briefly outline some important clustering and retrieval ideas that we did not cover in this course.<p> We conclude with an overview of what's in store for you in the rest of the specialization.


12 videos, 2 readings expand

1. Reading: Slides presented in this module
2. Video: Module 1 recap
3. Video: Module 2 recap
4. Video: Module 3 recap
5. Video: Module 4 recap
6. Video: Why hierarchical clustering?
7. Video: Divisive clustering
8. Video: Agglomerative clustering
9. Video: The dendrogram
10. Video: Agglomerative clustering details
11. Video: Hidden Markov models
12. Reading: Modeling text data with a hierarchy of clusters
13. Video: What we didn't cover
14. Video: Thank you!

Graded: Modeling text data with a hierarchy of clusters