Unit 6 - Practice Quiz

Bias is the error introduced by approximating a real-world problem, which may be complex, by a much simpler model. High bias can cause an algorithm to miss the relevant relations between features and target outputs (underfitting).

High variance indicates that the model is too complex and has learned the noise in the training data, a condition known as overfitting. This makes it perform poorly when generalizing to new, unseen data.

Underfitting occurs when a model is too simple to capture the underlying pattern of the data. As a result, it performs poorly not only on the test data but also on the data it was trained on.

An overfitted model is very flexible (low bias) and captures the noise in the training data, making it sensitive to small changes (high variance). This harms its ability to generalize.

Regularization techniques add a penalty term to the loss function for large coefficient values, which discourages the model from becoming overly complex and fitting the noise in the training data.

L2 regularization, or Ridge regression, adds a penalty term of the form , where are the model weights. This penalizes large weights, encouraging them to be small and distributed.

The L1 penalty term, , has the effect of forcing some coefficient estimates to be exactly zero, which makes it useful for feature selection.

A more complex model can better fit the training data, reducing bias. However, this increased flexibility makes it more sensitive to the training data's noise, thus increasing variance.

The L1 norm, also known as the Manhattan distance or Taxicab norm, is the sum of the absolute values of the components of the vector. It is represented as .

The L1 constraint defines a region whose shape is a hyperdiamond (or orthoplex). The sharp corners of this shape are why the optimization is likely to find solutions where some weights are exactly zero.

The hyperparameter controls the strength of the regularization. If , the penalty term becomes zero, and the loss function reduces to the standard empirical risk, meaning no regularization is applied.

Empirical risk is the error that the model makes on the training data. Simply minimizing this risk can lead to overfitting, which is why we also consider the model's complexity.

SRM aims to minimize a bound on the true generalization error. This bound is a sum of two terms: the empirical risk (training error) and a term that depends on the model's complexity (like its VC dimension).

The VC dimension is a measure of a model's complexity. It is defined as the maximum number of points that the model can 'shatter,' meaning it can perfectly classify them no matter how they are labeled.

An infinite VC dimension means the model has unlimited capacity. It can shatter any number of points, allowing it to perfectly memorize the training data, including noise, which leads to poor generalization.

A line can separate any 3 non-collinear points in all possible ways. However, it cannot shatter 4 points; for example, it's impossible to separate points of a square where opposite corners have the same label. Thus, its VC dimension is 3.

To make a high-degree polynomial pass through all the training points, the model often develops extremely large coefficients. This makes the function very 'wiggly' and sensitive to small changes in input, which is a hallmark of overfitting.

Ridge Regression is the specific name for a linear regression model that is regularized using the L2 norm of the coefficients.

High bias means the model makes strong, potentially incorrect assumptions about the data. This leads to underfitting, where the model is too simple to capture the true underlying patterns.

LASSO stands for Least Absolute Shrinkage and Selection Operator. Its use of the L1 penalty inherently performs feature selection by shrinking the coefficients of less important features to exactly zero.

The irreducible error, , represents the inherent noise in the data itself. Even with a perfect model and infinite data, this randomness cannot be eliminated. Bias and variance are properties of the model and would approach zero under these ideal conditions.

Overfitting occurs when a model learns the training data too well, including its noise and specific quirks. This results in excellent performance on the training set (low error) but poor performance on unseen data (high validation error), indicating a failure to generalize.

L1 regularization adds a penalty term proportional to . Due to the geometry of the L1 norm (a diamond shape), it tends to produce sparse solutions where many model weights are exactly zero, effectively performing feature selection. L2's penalty, , shrinks weights towards zero but rarely sets them to exactly zero.

A smaller makes the k-NN model more flexible and sensitive to local noise in the training data. This reduces the model's bias (it can fit complex patterns) but increases its variance (it is highly dependent on the specific training points). A classifier, for example, has very high variance.

SRM aims to minimize an upper bound on the true risk (generalization error). This bound is expressed as the sum of the empirical risk (the error on the training data) and a complexity term (which depends on the model's capacity, like its VC dimension). Regularization is a practical implementation of SRM.

The Lagrangian formulation of adding a penalty term is equivalent to a constrained optimization problem. Ridge regression minimizes the Mean Squared Error (MSE) while keeping the squared L2 norm of the weight vector below a certain threshold . The value of is inversely related to the regularization parameter .

VC dimension is a measure of a model class's capacity or complexity. A higher VC dimension means the model can shatter a larger set of points, allowing it to fit more complex patterns. This increased flexibility makes it more prone to fitting the noise in the training data (overfitting), especially with a limited dataset.

When the number of parameters () exceeds the number of data points (), the model has enough flexibility to perfectly memorize the training data, including its noise. This is a classic recipe for overfitting, leading to very low training error but poor generalization to new data.

The Ridge cost function is . As , the penalty term dominates the loss function. To minimize this term, the optimizer must force all weights to be as close to zero as possible.

Poor performance on both training and test sets suggests the model is too simple to capture the underlying structure of the data (underfitting). This is characteristic of high bias. The errors being similar suggests the model's predictions do not change much with different training sets, which implies low variance.

In two dimensions, the L1 constraint forms a diamond. The unregularized loss function forms elliptical contours. The optimal solution is the point where an ellipse first touches the diamond. Due to the sharp corners of the diamond lying on the axes, this contact point is very likely to be at a corner, where one of the weights is exactly zero.

When dealing with high-dimensional data where many features are expected to be irrelevant, L1 regularization is highly advantageous. Its tendency to produce sparse models (setting many weights to zero) acts as an embedded feature selection method, simplifying the model and potentially improving its interpretability and performance.

Generalization bounds, such as the one derived from VC theory, typically show that the gap between true risk and empirical risk is bounded by a term that is proportional to . As the number of samples increases, this bound becomes tighter, suggesting that with more data, the model's performance on the training set becomes a more reliable estimate of its performance on unseen data.

Overfitting is a high-variance problem. Providing more data helps the model learn the true underlying pattern instead of memorizing noise. This reduces the model's sensitivity to the specific training sample, thereby decreasing its variance and improving its ability to generalize, which is reflected in a lower validation error.

SRM balances empirical risk (loss on training data) with a penalty for model complexity. L2 regularization operationalizes this by adding a penalty term, , to the loss. This term penalizes models with large weights, which are considered more complex. The optimizer must therefore find a solution that fits the data well (low empirical risk) without making the weights too large (low complexity penalty).

The non-differentiability of the L1 norm at zero means that the gradient is not defined for any weight that is exactly zero. Therefore, standard gradient-based optimization methods cannot be applied without modification. Algorithms like Proximal Gradient Descent, Coordinate Descent, or those using subgradients are employed to handle this issue.

A large gap between training and test performance is the hallmark of overfitting. Mathematically, overfitting corresponds to a model with high variance. The model is so complex that it has learned the specific noise and artifacts of the small training set, and its predictions vary drastically when presented with new, unseen data.

Consider two weight vectors: and . and . However, while . The L2 penalty for the single large weight is much higher. This shows that the L2 norm prefers to distribute weight values more evenly, while being very averse to individual large weights.

Bias, in the context of the bias-variance decomposition, measures the difference between the average prediction of our model and the correct value which we are trying to predict. High bias means that, on average, the model's predictions are systematically incorrect because its assumptions are too simplistic to approximate the true function.

Ridge regression is known to handle multicollinearity by distributing the weight among correlated features. It will shrink their coefficients towards each other (and towards zero). Lasso, on the other hand, is unstable in the presence of high correlation; it will often arbitrarily pick one feature from a correlated group and assign it a non-zero weight, while setting the others to zero.

The clean, additive bias-variance-noise decomposition is a special property derived from the linearity of expectations and the properties of variance, which are inherently tied to the squared error loss. For other loss functions like absolute error, the cross-terms in the expansion do not conveniently cancel out. The decomposition is not as straightforward and typically results in an inequality, such as , rather than a strict equality.

With correlated features, the loss function surface has a long, flat valley. Ridge's circular L2 constraint will intersect this valley where , so it shrinks them together towards zero. Lasso's diamond-shaped L1 constraint is likely to intersect the valley at a corner, which lies on an axis. This means one coefficient becomes exactly zero while the other takes on the shared effect, thus performing feature selection.

A single interval can shatter 2 points (VCdim=2). A union of intervals can label points within them as positive and points outside as negative. To shatter a set of points, we need to realize all possible dichotomies. For points arranged alternatingly on a line, we can choose our intervals to enclose any subset of the odd-indexed points (or even-indexed), thus shattering them. However, points arranged this way cannot be shattered. For example, to label them alternatingly (+, -, +, -, ..., +) requires positive intervals, which is not allowed by the hypothesis class. Therefore, the VC dimension is .

SRM seeks to minimize the upper bound on the true risk, which is a sum of empirical risk and a complexity penalty term . The penalty term is an increasing function of the VC dimension . Model B has lower empirical risk but a higher penalty. Model A has higher empirical risk but a lower penalty. The optimal choice depends on this trade-off, which is dictated by the specific form of the bound and the sample size . A small would favor the simpler Model A, while a very large would favor the model with lower empirical risk, Model B. Without this information, no definitive choice can be made.

Multicollinearity means that columns of are nearly linearly dependent. This causes the matrix to be near-singular, and its inverse to have very large diagonal entries. This directly translates to a very high variance in the coefficient estimates . However, the OLS estimator remains unbiased () as long as is invertible. Therefore, multicollinearity inflates the variance component of the error significantly while leaving the bias unchanged (at zero).

Overfitting is characterized by a model that learns the training data, including its noise, almost perfectly but fails to generalize to new, unseen data. Mathematically, this is captured by a very low training error () combined with a much higher generalization error (). Option B describes underfitting. Option C () is a condition that often leads to overfitting but is not a direct measure of it. Option D is a qualitative description of the same phenomenon as A, but A provides the direct mathematical condition on the error values themselves.

As , the term dominates the matrix . So, . Therefore, . As , the term , causing the entire vector to approach the zero vector. Consequently, its L2 norm also approaches 0.

This is a fundamental result from optimization theory, related to Lagrangian duality. The regularized form (often called the penalized form) is the Lagrangian relaxation of the constrained problem. For convex problems like these, there is a one-to-one correspondence between the constraint budget and the regularization parameter . A smaller (tighter constraint) corresponds to a larger (stronger penalty), and vice-versa. They are essentially two ways of formulating the same underlying trade-off.

You can shatter 3 points (e.g., the vertices of a non-degenerate triangle). For any labeling of these 3 points, you can find a circle that contains the positive points but not the negative ones. However, you cannot shatter 4 points. Consider 4 points on the boundary of a circle. If their labels are alternating (+, -, +, -), no single circle can contain the two positive points without also containing one of the negative points. Therefore, the VC dimension is 3.

When a high-degree polynomial overfits, it tries to pass exactly through or very close to each training data point. To create the necessary "wiggles" and sharp turns to interpolate the data (including noise), the function requires large positive and negative coefficients that largely cancel each other out except in the vicinity of the data points. This interplay of large, alternating-sign coefficients leads to a large overall norm of the weight vector.

The derivative of with respect to is , which is -1 for and +1 for . At , the left-hand and right-hand derivatives do not match, so the function is not differentiable. This point is crucial for sparsity. Optimization algorithms must handle this. Subgradient descent replaces the gradient with a subgradient (any value in [-1, 1] at ). Other popular methods include coordinate descent and proximal gradient methods.

When , the model is very flexible and captures local noise, resulting in low bias but high variance. As increases, the model averages over more neighbors, smoothing its predictions. This makes it less sensitive to the specific training data (lower variance). However, by averaging over a larger, less local neighborhood, the model becomes less flexible and may fail to capture the true underlying function (higher bias). When , the model predicts the global average for any input, resulting in maximum bias and minimum variance.

The complexity term, or "VC confidence," is the penalty for model complexity. The sample size appears in its denominator. This means that as the amount of training data increases towards infinity, the complexity penalty term goes to zero. In this asymptotic scenario, minimizing the upper bound (SRM) becomes equivalent to minimizing just the empirical risk (ERM). This provides the theoretical justification for why ERM is often a reasonable approach with a very large amount of data.

Both L1 and L2 regularization add a penalty based on the magnitude of the coefficients. If features are on different scales, the penalty is applied inequitably. For example, if feature has a range of 1000 and has a range of 1, its corresponding coefficient would be much smaller than for a similar effect. The regularization penalty would then unfairly penalize more than . Standardizing features puts them on a common scale, ensuring the penalty is applied fairly and is not biased by arbitrary units.

While the number of parameters is often a rough heuristic for model complexity, there is no strict relationship with VC dimension. For linear classifiers in , VCdim is (parameters). However, a model with just one parameter, like , has infinite VC dimension because it can be made to oscillate arbitrarily fast to shatter any number of points. Conversely, models can be constructed with many constrained parameters, leading to a VC dimension much smaller than the parameter count.

The optimal solution is the point where the expanding level set of the loss function first touches the constraint region. The L2-ball (circle/sphere) is uniformly round, so the point of tangency can be anywhere on its surface. The L1-ball (diamond/polytope) has sharp corners that protrude along the axes. It is geometrically much more probable that the expanding ellipse will touch one of these corners before it touches any other part of the diamond's boundary. This contact at a corner corresponds to a sparse solution where one or more coefficients are exactly zero.

A model with high variance overfits the training data. With a small training set, it can fit it almost perfectly, so training error is near zero, but it generalizes poorly, so validation error is high. As the training set size increases, it becomes harder for the complex model to perfectly fit all the data, so the training error increases. At the same time, more data provides a better signal of the underlying pattern, so the model begins to generalize better, and the validation error decreases. The gap between the two curves narrows, indicating that more data can help mitigate high variance.

The Bias term measures how far the average model prediction is from the true function. With a sufficiently flexible model class (e.g., one that contains the true function), the bias can be reduced to zero. The Variance term measures the model's sensitivity to the specific training set. As the amount of training data approaches infinity, the model's prediction becomes stable and independent of the specific sample, thus the variance approaches zero. The Noise term (), or irreducible error, is a property of the data generating process itself and cannot be reduced by any model.

In a situation with a group of highly correlated features, Lasso tends to arbitrarily select only one feature from the group. The Ridge penalty component in Elastic Net encourages the coefficients of correlated features to be similar. The combination, known as the 'grouping effect', means the Elastic Net will often select or discard the entire group of correlated features together, which is often a desirable property. The L1 component ensures that the overall solution remains sparse by setting the coefficients of irrelevant features (or groups) to zero.

The 1-NN classifier's decision boundary is determined entirely by the training data. If we want to test if the classifier can shatter its own training set of size , we can. For any of the possible labelings of the points in , we can simply assign those labels to the points. When we then classify each point , its nearest neighbor is itself, so it is assigned its own label. Thus, 1-NN can perfectly realize any dichotomy on its own training set. Therefore, its VC dimension is at least . It cannot shatter any set of size because it only has 'parameters' (the training points). This highlights how the complexity of non-parametric models can grow with the data.