Linear Regression

Imagine estimating a baby's weight from explanatory information such as her age and weight at birth. A prediction of 3.00001 kg and a prediction of 4 kg are both different from an actual value of 3 kg, but they are not equally bad. Regression therefore needs more than a yes-or-no judgment about correctness. It needs a loss function that converts the discrepancy between a prediction and the actual value into a numerical penalty.

A loss function evaluates one prediction against its target. It measures how large the discrepancy is and applies a rule for turning that discrepancy into a penalty. Choosing the loss function is part of choosing the model: it determines what the learning procedure treats as a small error and what it treats as a large error.

Squared loss starts with the prediction error and squares it. Absolute value loss starts with the same error and takes its absolute value. Both begin from the same discrepancy, but they apply different penalty rules. The difference matters because the resulting numerical penalties can be different even when the prediction and actual value are unchanged.

A loss function evaluates one example at a time. When squared loss is used across a data set, the resulting empirical risk function is called Mean Squared Error. The individual squared-loss expression is the penalty for one prediction; Mean Squared Error is the data-set-level empirical risk associated with using squared loss.

Absolute value loss also has an empirical risk minimization rule, and that rule can be implemented using linear programming. The central distinction remains the same: first define how one example is penalized, then use the chosen loss across the data set when evaluating a predictor.

When viewed as a learning problem, the input domain X is a subset of R^{^d} for some d. The label set Y is the set of real numbers. The learning goal is to learn a linear function h that maps an input from R^{^d} to a real number and best approximates the relationship between the explanatory variables and the outcome.

The direction of the problem matters. Explanatory variables are the inputs; the real-valued outcome is the target. A learned predictor uses the input to produce an estimated outcome. Linear regression is therefore not only a way to describe a relationship in data. It is also a way to learn a predictor that approximates that relationship.

A hypothesis class is the collection of candidate functions that the learning problem is allowed to consider. In linear regression, the hypothesis class is restricted to linear functions. Learning therefore means selecting or learning a suitable linear function h for approximating the relationship in the data.

A linear function combines input variables with coefficients and an intercept to produce a real-valued prediction. The coefficients determine how the input variables participate in the prediction, while the intercept is the constant part of the function. The important point for the learning setup is that the predictor must come from the permitted class of linear functions.

Linear regression is not a binary prediction task, so its sample complexity cannot be analyzed using the VC-dimension in the same way described for binary classification. One possible route is the discretization trick. Continuous parameter values can be replaced by a finite collection of permitted values. The resulting collection of candidate linear functions is finite, which makes finite-class sample-complexity analysis possible.