Lecture 33: Neural Nets and the Learning Function

What this lecture covers

This lecture refines how the course describes a neural network's learning function f, separating the weights being optimized (the matrices and bias vectors) from the feature vectors that come from the training data. It reviews common loss functions used to train networks, then switches to a different topic: given only the pairwise distances between a set of points, how do you recover the points' positions? This distance matrix problem connects back to dimensionality reduction ideas relevant to machine learning.

After watching, you can describe the structure of a neural network as an alternating sequence of affine steps and nonlinear steps applied to a sample vector, list several standard loss functions and when each is used, and explain how a distance matrix can be converted into a dot product (Gram) matrix and then factored to recover point positions.

Key ideas

• Weights (X) vs. features (V): the learning function f depends on two separate kinds of variables: the weights X (the matrices A_k and bias vectors b_k, which are optimized) and the feature vectors V (which come from the training data and are not optimized).
• Layer structure: each layer computes an affine step A_k * V_(k-1) + b_k followed by a nonlinear step (ReLU), except the last layer, which is typically affine only.
• Underdetermined weights: in practice the number of weights often far exceeds the number of features in the training samples, meaning the optimization problem for X is underdetermined.
• Loss functions: the lecture lists square loss (L2, for regression), L1 loss (less common in deep learning but used in problems like LASSO), hinge loss (for -1/+1 classification), and cross-entropy loss (the most common choice for training neural networks).
• Distance matrix problem: given only pairwise squared distances D_ij between a set of unknown points, the goal is to recover the points' positions X, up to rigid motions (translation and rotation), which cannot be determined from distances alone.
• Gram matrix: the squared distance D_ij = |x_i|^2 - 2*(x_i . x_j) + |x_j|^2 can be rearranged to express the dot product matrix G = X^T X in terms of D and simple rank-one corrections, since G (not X itself) is what distances directly determine.
• Recovering X from G: once G = X^T X is known, X can be recovered (up to an orthogonal transformation) either via an eigenvalue decomposition (G = Q * Lambda * Q^T, then X = sqrt(Lambda) * Q^T) or via Cholesky factorization (G = L * D * L^T, then X = sqrt(D) * L^T), with Cholesky being computationally cheaper.

Walkthrough

Revised structure of the neural net learning function (0:44)

The lecture presents a cleaner way to think about the network's learning function f(X, V), separating the weights X (matrices A_k and biases b_k, which are being optimized) from the feature vectors V (given by the training data, one sample, a mini-batch, or a full epoch at a time). It walks through the layer-by-layer computation: an affine step A_k * V_(k-1) + b_k followed by ReLU, repeated across layers, with the final layer typically skipping the nonlinearity.

Weights often outnumber features (8:32)

The lecture points out that in practice, the total number of weights (entries in all the A_k and b_k) often exceeds the number of features in the training data, making the optimization of X underdetermined, an important and somewhat unexpected characteristic of deep networks.

The Loss Function (12:21)

Connecting back to the finite-sum optimization framework from the SGD guest lecture, the loss L(X) is written as a sum over training samples of a per-sample loss f(X, v_i) compared to the true label. The lecture notes that gradient descent, stochastic gradient descent, and mini-batch methods differ in how many terms of this sum are evaluated per iteration.

Loss Functions (15:27)

The lecture surveys common loss functions: square loss (L2 norm of errors, for regression), L1 loss (used in problems like LASSO but not typically in deep learning), hinge loss (for -1/+1 classification problems), and cross-entropy loss (the standard choice for training neural networks).

Setting up the distance matrix problem (18:55)

Switching topics, the lecture introduces the problem of recovering point positions from known pairwise distances, motivated by applications such as wireless sensor networks (distances from signal travel times) and molecular structure (distances from NMR measurements). It notes that positions can only be recovered up to translation and rotation, and connects this to the broader machine learning idea of data lying near a lower-dimensional manifold in high-dimensional feature space.

From distances to dot products (the Gram matrix) (28:25)

Expanding D_ij = |x_i - x_j|^2, the lecture shows that the distance matrix decomposes into the unknown dot product (Gram) matrix G = X^T X plus two rank-one correction terms built from the diagonal entries of G. Rearranging gives a formula for G purely in terms of the known distance matrix D.

Recovering positions from the Gram matrix (48:06)

With G = X^T X known, the lecture presents two ways to recover X: an eigenvalue decomposition G = Q * Lambda * Q^T, giving X = sqrt(Lambda) * Q^T, or a Cholesky factorization G = L * D * L^T, giving X = sqrt(D) * L^T, noting that Cholesky is faster to compute than an eigenvalue decomposition.

Before you watch

• Watch the earlier lecture on the structure of neural nets, since this lecture revises and refines that material.
• Review the finite-sum optimization setup from the stochastic gradient descent guest lecture.
• Be comfortable with symmetric positive semi-definite matrices, eigenvalue decomposition, and Cholesky factorization.

Check your understanding

1. In the revised notation, what is the difference between the role of X and the role of V in the learning function f(X, V)?
2. Why can the number of weights in a neural network exceed the number of features in the training data, and what does that imply about the optimization problem?
3. Which loss function is most commonly used for training neural networks, and which is typically used for -1/+1 classification?
4. Why can positions be recovered from a distance matrix only up to a rigid motion?
5. How does the Gram matrix G = X^T X bridge the gap between the known distance matrix D and the unknown positions X, and what are two ways to factor G to recover X?