Paragraphs 5.1 - 5.7

What does it mean to learn according to Mitchell's definition?

To improve performance P on tasks T through experience E.

What does T denote in the definition of learning?

The class of tasks the program must perform.

What does P denote in the definition of learning?

A quantitative measure of task performance.

What does E denote in the definition of learning?

Experience, such as examples in a dataset.

For a robot learning to walk, what is the task?

Walking; learning is the means of acquiring that ability.

What is an example in machine learning?

A collection of measured features of an object or event.

How is an example usually represented?

As a vector x in R^n, with one feature per component.

What does a k-class classifier produce?

A label from k categories, possibly along with class probabilities.

What makes classification with missing inputs distinctive?

It must work even when some input features are not observed.

What does a regression model produce?

A continuous numerical value or vector of such values.

What is transcription as an ML task?

Turning an unstructured input into a discrete sequence of symbols.

How do transcription and machine translation differ?

Transcription extracts symbols from a signal; translation converts a symbol sequence into another language.

What is a structured-output task?

A task whose output components have relationships, such as a sequence or tree.

What is anomaly detection?

Identifying inputs or events that are unusual relative to normal data.

What are synthesis and sampling?

Generating new examples resembling those from the learned distribution.

What is imputation of missing values?

Predicting unobserved parts of an example from the parts that are available.

What is denoising?

Reconstructing a clean example from a corrupted, noisy version.

What is learned in density estimation?

A function assigning probabilities or densities to inputs.

Why does the performance measure P depend on the task?

Different tasks call for different quantitative criteria of success.

What is accuracy?

The fraction of examples classified correctly.

What is the error rate?

The fraction of examples classified incorrectly.

What is 0-1 loss on an individual example?

Zero for a correct prediction and one for an incorrect prediction.

What is a common performance measure for density estimation?

The average log probability assigned to evaluation examples.

Why use a separate test set?

To estimate performance on data unseen during training.

Why can selecting P be difficult?

A metric may not reflect the desired behavior or may be impractical to compute.

What does a dataset contain?

Many examples, each with features and sometimes a target.

What does an unsupervised algorithm typically learn?

The structure of p(x) or its properties without assigned targets.

What does a supervised algorithm typically learn?

To predict y from x, often by modeling p(y given x).

What is a label or target?

The desired output associated with a supervised example.

What is clustering?

Grouping similar examples into clusters.

Why are supervised and unsupervised learning not rigid categories?

A problem can sometimes be reformulated using methods from the other category.

How does the chain rule factorize p(x)?

p(x) = product from i=1 to n of p(x_i given x_1,...,x_(i-1)).

How can p(y given x) be obtained from p(x,y)?

Normalize the joint distribution: p(y given x) = p(x,y) / sum over y' of p(x,y').

What is semi-supervised learning?

Training with some labeled examples and some unlabeled examples.

What is multi-instance learning?

A collection is labeled, but its individual members are not.

How does reinforcement learning differ from learning from a fixed dataset?

The agent interacts with an environment and affects its later experiences.

What is a design matrix X?

A matrix with one example per row and one feature per column.

What are the dimensions of the Iris design matrix described in the text?

150 rows and 4 features: X in R^(150×4).

When is a design matrix unsuitable?

When examples cannot all be represented by vectors of the same length.

What does y_i represent in a supervised dataset?

The target for example i.

What is the task of linear regression?

Predicting a scalar target y from an input vector x.

What is the prediction of linear regression without an intercept?

ŷ = w^T x.

What does w represent in linear regression?

The vector of parameters or feature weights.

What is the effect of a positive weight w_i?

Increasing x_i raises the prediction if other features stay fixed.

What is the effect of a negative weight w_i?

Increasing x_i lowers the prediction if other features stay fixed.

What does w_i = 0 mean?

Feature x_i makes no direct contribution to the prediction.

What is MSE over m examples?

The mean (1/m) sum_i (ŷ_i − y_i)^2.

How can MSE be expressed in vector form?

MSE = (1/m) ||ŷ − y||_2^2.

What does ordinary linear regression minimize during training?

Mean squared error on the training set.

What is the stationarity condition for the least-squares minimum?

The gradient of MSE with respect to w equals zero.

What are the normal equations for linear regression?

X^T X w = X^T y.

What is the closed-form solution if X^T X is invertible?

w = (X^T X)^(-1) X^T y.

What is linear regression with an intercept?

ŷ = w^T x + b.

How can the intercept b be incorporated into the weight vector?

Add an input feature that is always 1.

What is an affine function in this context?

ŷ = w^T x + b; it need not pass through the origin.

Is intercept b the same as statistical bias?

No. b is an intercept; statistical bias is the expected estimation error relative to the true value.

What is generalization?

The ability to perform well on new inputs not seen during training.

What is training error?

Error measured on the examples used to fit the model.

What is generalization error?

Expected error on a new input from the distribution of interest.

How is generalization error usually estimated?

By measuring error on a separately collected test set.

What does i.i.d. stand for?

Independent and identically distributed examples.

What key assumption about train and test sets does the text make?

They are sampled from the same data-generating distribution p_data.

For a model fixed before sampling, how do expected train and test errors compare?

They are equal when the sets come from the same distribution.

Why is training error generally lower than test error after fitting?

Parameters were selected specifically to reduce training error.

What are the two main challenges for generalization?

Keeping training error low and keeping the train-test gap small.

What is underfitting?

Failure to achieve sufficiently low training error.

What is overfitting?

An excessively large gap between training and test error.

What is a model's capacity?

Its ability to fit a wide variety of functions.

What is the risk of insufficient capacity?

Underfitting because the model cannot represent the required pattern.

What is the risk of excessive capacity relative to the data?

Overfitting by adapting to peculiarities of the training sample.

What is a hypothesis space?

The set of functions the algorithm may select.

How can polynomial regression capacity be increased?

Add higher powers of the input as new features.

Why is quadratic regression still linear in its parameters?

b + w_1 x + w_2 x² is linear in coefficients w_1 and w_2.

What happens when a degree-one polynomial fits truly quadratic data?

It underfits because it cannot represent the curvature.

What may happen when a degree-nine polynomial fits a few quadratic data points?

It may pass through training points but behave poorly between them and on new data.

What is representational capacity?

The range of functions a model family can express.

What is effective capacity?

The range of solutions the full algorithm can actually find given optimization limits.

Why can effective and representational capacity differ?

Optimization may fail to find the best available function in the family.

What is Occam's razor?

Prefer a simpler hypothesis among those that explain observations equally well.

What does VC dimension measure?

The largest number of points in some configuration that a binary classifier can label arbitrarily.

How do generalization-gap bounds change?

They grow with model capacity and shrink as the training sample grows.

How does training error typically change with capacity?

It tends to decrease as capacity increases.

How does generalization error typically change with capacity?

It tends to trace a U-shaped curve with a minimum at intermediate capacity.

What is a parametric model?

A model with a finite number of parameters fixed before observing data.

What is a nonparametric model?

A model whose complexity is not limited to a fixed parameter count.

Why is nearest neighbor nonparametric?

It stores training data, and its complexity grows with the dataset.

How does nearest-neighbor regression predict?

It returns the target of the nearest training example.

What is Bayes error?

The irreducible error of a predictor that knows the true data distribution.

Why can even an oracle make errors?

Targets can be noisy, stochastic, or dependent on unobserved variables.

What can more training data do to the train-test gap?

It can reduce the gap and improve generalization.

What does the no-free-lunch theorem say when averaged over all distributions?

No classification algorithm is universally better on unseen inputs.

Why does no free lunch not prevent useful learning algorithms?

We can choose assumptions suited to the real-world distributions of interest.

What is regularization?

A change to a learning algorithm intended to lower generalization error.

How can preferences among functions be expressed?

Add an objective penalty or constrain the eligible solutions.

What is the L2 weight-decay objective?

J(w) = MSE_train + λ w^T w.

What does λ control in weight decay?

How strongly small weights are preferred.

What happens when λ = 0?

No L2 penalty is applied to the weights.

What can happen if λ is excessively large?

Weights shrink too much and the model may underfit.

What can happen if λ is too small?

Regularization may fail to prevent overfitting.

What is the regularizer Ω(w) in weight decay?

Ω(w) = w^T w, the squared L2 norm of the weights.