Unsupervised Learning

Question 1

Too much data?
* Reduce it

Answer 1

• by number of examples – clustering
• by number of dimensions – dimensionality reduction

Question 2

Clustering:

Answer 2

Find meaningful groupings in data

Question 3

Topic modeling:

Answer 3

Discover topics/groups with which we can tag data points

Question 4

Dimensionality reduction/compression:

Answer 4

Compress data set by removing redundancy and retaining only useful information

Question 5

K-means

Answer 5

Unsupervised method for clustering
* Partition of data into k clusters based on features (k must be given)
* A cluster is represented by its centroid
* Each point is assigned to its nearest centroid/cluster

Question 6

K-means Goal

Answer 6

To minimize intra-cluster distance – measure of distance between data and the correspondent cluster centroid

Question 7

K-means: Iterative

Answer 7

Pick k random points as centroids
Repeat until no further reassignment:

• Assign points to its nearest centroid
• Change each cluster centroid to the average of points assigned to it

Question 8

A good clustering is one that achieves

Answer 8

• High within-cluster similarity
• Low inter-cluster similarity

Question 9

K-means Clustering fast and working well if. . . clusters:

Answer 9

• are spherically shaped
• are well separated
• have similar volumes
• a similar number of points (densities)

Question 10

K-means Issues

Answer 10

clusters of very different sizes

clusters with different densities

non spherical clusters

Question 11

Expectation Maximization (EM)
Algorithm

Answer 11

• Generate k random probability distributions [1]
  Iterate until convergence:
• Find which points are more probable to be generated by each probability distribution (E-step) [2]
• Re-calculate distributions parameters (M-step) [3]

Question 12

EM Algorithm

Answer 12

Learning mixtures of Gaussians

Question 13

Hierarchical Unsupervised
Learning

Answer 13

Find successive clusters using previously established ones (organized as an hierarchical tree)

• Agglomerative (bottom-up)
• Divisive (top-down)

Question 14

Non Parametric Clustering –
DBSCAN

Answer 14

1. Find the points in the ε-distance
   neighbourhood of every point, and
   identify the core points with more
   than the minimum number of
   points to form a dense region
2. Find the connected components of
   the core points on the neighbours
   graph, ignoring all non-core points
3. Assign each non-core point to a
   nearby cluster if the cluster is an
   ε-distance neighbour, otherwise
   assign it to noise

Question 15

SOM (Self-organizing Maps)

Answer 15

Similar to K-means, but . . .
* Representatives are organized (have neighbours) in a 1D or 2D mesh
* When a representative is selected to be adapted, neighbours are also updated (with a lower rate)

Question 16

Dimensionality Reduction

Answer 16

• When you represent data using fewer dimensions, makes it easier to learn (fewer parameters)
• Discover intrinsic dimensionality of data
• High dimensional data that is really lower dimensional
• Noise reduction

Question 17

Dimensionality Reduction: Feature selection

Answer 17

Choose a (the best) subset of all the features

Question 18

Dimensionality Reduction: Feature extraction

Answer 18

Create new features by combining existing ones

Question 19

Features reduction: lower dimensional projections

Answer 19

Instead of picking a subset of the features, consider ‘new’ ones by combining some of the existing features

Question 20

Lower Dimensional Projections

Answer 20

Project n-dimensional data into k-dimensional space preserving
* information
* maximizing variance
* with minimum reconstruction error

Question 21

Principal Component Analysis (PCA)

Answer 21

Projection that best represents the data in
the least-squares sense

Question 22

Smaller projection errors;

Answer 22

smaller overall sum of squares

Question 23

Principal Component Analysis: Algorithm

Answer 23

Considering a Xm×n data matrix,

• Re-center: subtract mean from X,
  XC ← X − µ
• Compute covariance matrix: C ← 1/m · XTC · XC
• Compute the k largest eigenvectors in C: the Principal Components
• y = ETXC is the closest PCA approximation to X

Question 24

Difficulties Principal Component Analysis

Answer 24

• Covariance matrix can (still) be huge!
• Finding eigenvectors can be a slow process

Question 25

Topic Models

Answer 25

• Used in Natural Language Processing
• Use different mathematical frameworks:
  Linear algebra vs. probabilistic modeling

Question 26

Topic Models share 3 fundamental assumptions

Answer 26

• Documents have a latent semantic structure (“topics”)
• Can infer topics from word-document co-occurrences
• Words are related to topics, topics to documents

Question 27

Latent Semantic Analysis (linear algebra-based topic model)

Answer 27

Extension of the Vector Space Model (words × documents)

• Reduces the high-dimensional vector space into a smaller space by collapsing the original representation into a smaller set of latent dimensions (“topics”) that aggregates words and
  documents with similar context vectors
• Based on the Singular Value Decomposition (SVD)
• Entropy-based term weighting

Question 28

Latent Dirichlet Allocation: probabilistic topic model

Answer 28

Documents are represented as random mixtures over latent topics

Topics are characterized by a distribution over words

Words can belong to multiple topics
* z is the topic of a word in the document
* β is the word probability distribution of each topic

A document can have multiple topics:
* θ is the topic distribution of a document
* α is the distribution of distribution of topics