Regularization and Under-Constrained Problems

When the answer is not unique

Imagine a recipe that says you need 3 units of flavour from two spices, one of which gives 1 unit per spoon and the other 2 units per spoon. Many mixtures give exactly 3 units. Which one do you choose? A rule such as "use as little as possible" picks one of them. In machine learning, a problem with fewer equations than unknowns is called underdetermined, and it has the same kind of many-answer situation.

The book makes the point with linear equations. Regularization is needed for some problems to be defined at all. Many linear models, such as linear regression and PCA, depend on inverting the matrix . That inverse does not exist when the matrix is singular, and it can be singular when there are fewer examples than features.

Here is the design matrix, with one row per example, and holds the targets. The demo uses one example with two features, so is the row (1, 2) and the target is 3. Every weight vector with fits the example exactly.

Predict first. The ridge strength grows from 0. What happens to the weights that the ridge solution finds?

Choose an answer, then move the ridge strength.

The line is every weight vector that fits the example exactly. The teal point is the ridge solution, from Equation 7.17 with the single row of data. This closed form is added here and is not printed in the book. For this example it is , so the weights shrink as grows and the fit drifts below 3.

At the point is the shortest weight vector that fits, . It is the point of the line closest to the origin, and it is the pseudoinverse solution that Section 3 reaches as a limit.

When the matrix has no inverse

A matrix such as is singular when one of its directions has no variance at all. Then its inverse does not exist, and the normal equations give no single answer. The book states the cause in two ways: the data truly has no variance in some direction, or there are fewer examples than features, so the data cannot show variance in every direction.

Think of a choir with two singers and only one song sung by both. You can hear the total volume, but you cannot tell how the two voices split it. Without a second song you cannot separate the voices, however carefully you listen.

The matrix is the same matrix with times the identity added. The book says that many forms of regularization invert this matrix instead, and that the regularized matrix is guaranteed to be invertible. The demo uses a two-direction example with its own eigenvalues, not the matrix of Section 1. The first is fixed at 2, the second is set by a slider, and the ridge is added to both.

The first eigenvalue is fixed at 2, which is the variance in the direction the data shows. The choice removes the variance in the second direction, and the matrix then has no inverse. The ridge adds to both eigenvalues, so the smallest one can no longer reach zero while is positive.

Predict first. A design matrix has two rows and five columns, so there are fewer examples than features. Is invertible?

Choose an answer, then check the demo.

Checkpoint. If the second eigenvalue is 0 and , what is the condition number?

Answer, then check the readout.

The pseudoinverse as a limit

The book recalls that one definition of the Moore-Penrose pseudoinverse is a limit of ridge regression. Equation 7.29 takes the ridge solution of Equation 7.17 and lets the penalty shrink to zero:

Equation 7.29 is the limit of Equation 7.17 as the regularization coefficient shrinks to zero. So the pseudoinverse is ridge regression with the penalty removed in the limit. The book reads this as stabilizing an underdetermined problem with regularization. The point that the limit picks out the shortest exact fit is added here and is not printed in the book.

Think of a garden hose. A small ridge is a light squeeze on the hose: water still flows, and the flow is steady. The limit is the hose with no squeeze at all, and the flow goes to the shortest route.

The demo measures how far the ridge solution is from the pseudoinverse solution. The distance formula is added here and is not printed in the book. For this example it is , which goes to zero as does. The slider is on a logarithmic scale.

Predict first. As shrinks to zero, what do the ridge weights approach?

Choose an answer, then move the slider towards minus four.

Checkpoint. Which expression is the pseudoinverse for a matrix with full column rank, as goes to zero?

Answer, then check the formula in Equation 7.29.

Separable data and weight decay

The second kind of underdetermined problem is not linear. The book gives logistic regression on data that is linearly separable, meaning a line exists that classifies every example correctly. If a weight vector classifies everything correctly, then does too, and it has a higher likelihood. An iterative method keeps increasing the size of the weights, and in theory it never stops.

Think of a tug of war with a rope that is never quite taut. The data keeps pulling the weights outwards, but each step outward helps less and less. Weight decay adds a pull back towards zero. The book states that weight decay makes gradient descent stop increasing the weights once the slope of the likelihood equals the weight decay coefficient.

The demo uses one weight and two points, with labels , so the data is separable. The one-weight loss and its equilibrium equation are added here and are not printed in the book. The loss is , and the weight stops changing where .

The dashed line is the equilibrium, the weight where the pull of the data equals the pull of the decay. With there is no equilibrium, and the weight keeps growing, slowly. With a positive the weight levels off at a finite value.

Predict first. The decay is zero. Does the weight stop?

Choose an answer, then set the decay to zero.

• Ridge regression gives a unique answer even when the data does not determine the weights, because is invertible.
• A singular matrix has an eigenvalue of zero, and the ridge adds to every eigenvalue, so the inverse exists whenever is positive.
• Equation 7.29 writes the pseudoinverse as the limit of ridge regression as the penalty goes to zero.
• Weight decay stops the growth of weights on separable data, at the point where the pull of the data balances the decay.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 7.3 (pages 239–240), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.