Unlabeled Learning Depends on Assumptions About Hidden Structure

? chris-re frames unsupervised learning as a qualitatively different problem from supervised prediction. In supervised learning, labels specify what must be separated or predicted: positive and negative examples make the target explicit. Once those labels disappear, the task is no longer simply to fit a boundary. The learner must decide what regularity in the observed points is worth treating as structure in the first place.

That is why unsupervised learning requires stronger assumptions while offering weaker guarantees. A clustering method can return an answer for any cloud of points, but the answer is meaningful only if the data have a structure the method is designed to recover. If points are simply a random spray with no latent organization, k-means will still divide them into groups; it will not thereby have discovered anything useful.

Ré’s examples are data with latent groups that are meaningful independently of the algorithm: gene-expression types believed to correspond to biological categories, or astronomical observations generated by distinct kinds of sources. In such cases, clustering is not supposed to conjure categories out of nothing. It is a way to recover a hypothesized organization from unlabeled observations, then examine that organization using other knowledge.

The important question is therefore not merely whether an algorithm runs. It is what the algorithm assumes about the world. Choosing two clusters rather than four, deciding that groups should be compact in Euclidean space, or assuming that observations arise from Gaussian-shaped sources are all modeling commitments. Supervised methods have assumptions too, Ré notes, but unlabeled problems make those commitments harder to ignore because the data do not provide an externally given target.

This also gives “harder” two meanings. Qualitatively, removing labels removes crucial structure. Formally, some unsupervised objectives are computationally hard: finding the global optimum of the k-means objective is NP-hard. That does not mean every practical instance will take exponential time, but it does mean a simple iterative procedure should not be presumed to find the best possible clustering.

Given an integer k, the number of clusters, and observations x^(1), …, x^(n) in R^d, k-means seeks an assignment for every point. Write that assignment as C^(i) = j: point i belongs to cluster j.

The cluster identifiers themselves do not carry meaning. A solution in which the centers called μ₁ and μ₂ swap names is the same solution. With no labels, there is no intrinsic “cluster one” or “cluster two.”

The algorithm introduces a center μ_j for each cluster and repeats two steps: assign each point to its nearest current center, then replace each center with the arithmetic mean of the points currently assigned to it.

The assignment step chooses the cluster index that minimizes squared Euclidean distance:

C^(i) = argmin_j ||μ^(j) − x^(i)||².

If Ω_j is the set of points assigned to cluster j, the update is simply its average:

μ^(j) = (1 / |Ω_j|) Σ_(i in Ω_j) x^(i).

The squared distance does not change which center is closest. It is useful because it produces the least-squares objective that underlies the algorithm. Operationally, k-means starts from randomly initialized centers, assigns each observation according to its closest center, takes the average location of each resulting group, and repeats. The procedure can stop when assignments no longer change; Ré also notes that a practical implementation may instead run for a chosen number of iterations.

The objective being reduced is the within-cluster sum of squared distances:

J(C, μ) = Σ_i ||x^(i) − μ^(C^(i))||².

Each assignment-and-update cycle decreases J monotonically. That supplies the reason the procedure does not endlessly oscillate among assignments: it is making progress under this least-squares criterion. But monotonic decrease says nothing useful about how quickly it progresses. On difficult data, the objective may improve extremely slowly, particularly where a large mass of points and ambiguous peripheral points pull the centers in competing directions.

The criterion also clarifies what k-means means by a good cluster: points should be near the center assigned to them. That is a particular geometric preference, not a general definition of meaningful categories. It favors compact, center-based groups. A problem whose relevant groups are defined by another shape, relation, or external property may not fit it.

Monotonic descent of J establishes that the iteration makes progress under its objective, not that it finds the best possible clustering. Since optimizing k-means globally is NP-hard, a fast deterministic iteration from arbitrary initialization should not be expected to return the best clustering in all cases. K-means can converge to different local minima from different starting centers.

Random initialization is therefore not incidental. Once starting centers are fixed, the assignment and mean-update steps are deterministic. Different results arise because different initial centers can lead the method into different local minima. Random restarts address that dependence by trying the procedure from different starting points.

Ré highlights k-means++ as a more deliberate alternative to naïve random initialization. Its initialization scheme weights where new centers are placed and offers an approximation guarantee rather than an assurance of an optimal solution. The qualitative point matters more than the exact bound: initialization is part of the algorithmic design, not a disposable prelude. Ré notes that k-means++ is the default initialization in scikit-learn.

The harder issue is choosing k. There is no universal answer embedded in the objective. Different values encode different claims about the data: perhaps there are two broad kinds of events, perhaps five known sources, or perhaps several plausible levels of organization worth inspecting.

The lecture mentions an elbow as a familiar heuristic, but only in passing. Its substantive discussion is more cautious: raw cost comparisons across values of k are difficult to interpret because adding clusters naturally reduces within-cluster distance. A bend in such a curve may be suggestive, but it does not by itself establish that a particular partition reflects the world.

Useful validation generally requires some additional structure. One may know there are five sources, run clustering descriptively at several values of k, or bring independent knowledge of what valid groups should look like. Ré’s example is spatial structure: if external knowledge says a plausible cluster should have a particular form, that information can help assess a clustering in a way the k-means objective alone cannot.

A point cloud can plausibly support multiple descriptions. A visible arrangement might reasonably be called two broad clusters or four finer ones; an intermediate partition may look arbitrary. The choice is not resolved by geometry alone. It depends on the question being asked.

A Gaussian mixture model keeps k-means’ central intuition—observations are associated with latent sources—but replaces hard cluster assignment with probabilistic membership. K-means puts every point in exactly one cluster; a GMM assigns each point a distribution over possible sources.

Ré uses a toy astronomy setting. Observed photons land at spatial coordinates on an image, while the sources that generated them are unknown. Some sources may produce tight, intense bundles of observations; others may have broader or elongated spatial patterns. A point near the middle of a dense bundle may have near-certain membership in one source. A point in an overlapping region should not have to be assigned with false certainty.

The model expresses this uncertainty through P(z^(i) = j), the probability that source j generated observation x^(i). The source label z^(i) is a latent variable: the model assumes it exists and uses it to explain the data, but it is not directly observed.

The GMM’s forward-generating story has two stages. For each observation, the model draws a latent source z^(i) from a multinomial distribution with mixture proportions φ. Conditional on that source being j, it draws x^(i) from a Gaussian with parameters μ_j and σ_j² in one dimension, or a covariance matrix in higher dimensions.

In compact form, the model is:

z^(i) ~ Multinomial(φ)

x^(i) | z^(i) = j ~ N(μ_j, σ_j²).

The mixture proportions matter because sources need not produce equal numbers of observations. If two Gaussian densities give similar support to a point near their crossing, but one source emits a hundred times as many observations as the other, that point should be more likely to have come from the more prolific source. Ré characterizes that inference as Bayes’ rule in action.

The model still assumes that the number of sources k is known for a given run. It also assumes source shapes are Gaussian, while allowing different means, variances, and mixture weights. In higher dimensions, the covariance structure determines which shapes are available:

These are expressive modeling choices, but they remain assumptions. A GMM does not discover arbitrary kinds of groups. It looks for data that can be described as a mixture of Gaussian-generated sources.

If the latent source labels were known, fitting a GMM would reduce to a familiar labeled estimation problem: estimate a Gaussian for each known class, much as in Gaussian discriminant analysis. The difficulty is precisely that the labels are missing.

? chris-re describes Expectation Maximization as the iterative answer: first estimate the missing labels probabilistically, then update the model parameters using those estimates.

In the E-step, the algorithm calculates the responsibility of source j for point i:

w_j^(i) = P(z^(i) = j | x^(i), φ, μ, σ).

Bayes’ rule turns this inverse question—given an observed point, which source likely generated it?—into quantities supplied by the forward model. The responsibility is proportional to two terms: the Gaussian density of the point under source j, and the mixture weight φ_j of that source. It is normalized by summing the equivalent quantity over every possible source.

Written out, the responsibility is:

w_j^(i) = [P(x^(i) | z^(i) = j; μ, σ) P(z^(i) = j; φ)] / [Σ_(l=1)^k P(x^(i) | z^(i) = l; μ, σ) P(z^(i) = l; φ)].

Given current values for the means, variances, and mixture weights, every term can be computed. The E-step therefore does not observe the hidden labels; it produces a probability distribution over them.

The M-step then treats these responsibilities as fractional memberships. The new mixture weight is the average responsibility held by source j:

φ_j = (1 / n) Σ_i w_j^(i).

Its mean is the responsibility-weighted average of the observations:

μ_j = [Σ_i w_j^(i) x^(i)] / [Σ_i w_j^(i)].

Variances or covariance matrices are updated in the same weighted empirical fashion. A source’s effective observations are not merely the points assigned to it, but all points weighted by how much responsibility that source has for each one.

When responsibilities are only zeros and ones, this mean update becomes the k-means centroid update. That is the concrete connection between the methods: GMMs replace k-means’ all-or-nothing assignment with fractional attribution, then use weighted versions of the same estimation logic.

On each iteration, the E-step uses the current Gaussian shapes, locations, and mixture proportions to rescore the observations. The M-step uses those scores to change the source shapes, locations, and proportions. A point that initially had mixed membership can shift sharply toward another source after the model learns that one Gaussian is narrow in a direction where the point lies far away. The next round then recalculates the source parameters in light of that shift.

EM is also a general maximum-likelihood method for latent-variable models, not merely a GMM routine. Bundle the model parameters into θ, and the log-likelihood of IID observations is:

ℓ(θ) = Σ_(i=1)^n log P(x^(i); θ).

The complication is that the observed-data distribution marginalizes over latent values:

P(x; θ) = Σ_z P(x, z; θ).

The latent variable makes direct likelihood optimization harder because the logarithm applies to a sum over unobserved possibilities. Starting from current parameters θ_t, EM constructs a surrogate objective ℓ_t(θ) with two defining properties:

ℓ_t(θ) ≤ ℓ(θ)

and

ℓ_t(θ_t) = ℓ(θ_t).

The surrogate is a lower bound on the true likelihood everywhere, but it touches the true likelihood at the current parameter estimate. The E-step, given θ_t, supplies the information needed to form that particular bound. The M-step optimizes the easier surrogate to obtain the next estimate θ_(t+1). At that new estimate, EM reforms a new lower bound that again touches the likelihood there, then repeats.

This picture explains both the appeal and the limitation of the method. The procedure moves through a sequence of tractable optimization problems while maintaining a relationship to the original likelihood. It does not imply that the result is a global maximum. As with k-means, local optimization combined with initialization makes multiple optima unsurprising.

Jensen’s inequality is the tool behind the lower-bound construction. For a convex function f:

E[f(X)] ≥ f(E[X]).

For a concave function such as log x, the direction reverses:

E[log X] ≤ log E[X].

Ré treats Jensen’s inequality as convexity expressed in expectation form rather than as a separate trick. A convex function lies below the chord connecting two points on its graph: applying the function after averaging is no greater than averaging the function values. Since logarithms are concave, the reversed inequality supplies the slack used to replace the difficult observed-data likelihood with a lower-bound objective.

The analogy to k-means remains useful but incomplete. Both methods alternate between an assignment-like operation and parameter estimation. But the GMM setting makes explicit what k-means leaves implicit: the data are assumed to have been generated through hidden source assignments, and those assignments are estimated probabilistically rather than fixed as hard labels.