Table of Contents

🎓 Intended learning outcomes

At the end of this lesson, students are expected to:

• Understand and be able to explain unsupervised learning
• Formulate and describe a clustering problem
• Derive $k$-medoids from first principles
• Implement and solve $k$-medoids
• Understand and motivate the alternating assignment/update steps
• Identify connections to Expectation Maximization (EM) and $k$-means
• Understand and be able to explain what discrete optimization is. Name and briefly summarize other discrete optimization problems.
• Identify and optimally sort delicates, colors, and whites.

🪣 Unsupervised learning ★★★

Until now, we have seen regression and classification problems. In these problems, you were provided some kind of labels with the data — each temperature point came with a location or biodiversity value, and each location on the cat came with a label pet/do not pet. These types of problems are called supervised learning because these labels in the training dataset serve as a kind of teacher, supervising the learning process by giving us the answers that we are supposed to learn to produce. What happens if we are given data without supervision — examples without the desired answers?

Oh no! Who left all this dirty laundry around the house? Your flatmate, again! And your parents are coming over in a few hours — what are you going to do?

By your calculations, there is time to run $K = 3$ loads of laundry before your parents arrive. We need to sort these clothes into groups so we can clean them! We will denote the loads $k = \{1,2,3\}$, and our goal is to assign each article of clothing one of these $k$ values, as labels. Notice that I haven’t given you the labels (most people, including your flatmate, have their own system for sorting laundry — maybe it is color based, or maybe it is based on the fabric or outdoors vs. indoors). As such, this is an unsupervised learning problem.