CS 6375: Introduction to Machine Learning - Lecture 2

Flashcards covering machine learning paradigms, formal supervised learning components, feature spaces, empirical risk minimization, and instance-based nearest neighbor algorithms from CS 6375 Lecture 2.

How does Tom Mitchell formally define Machine Learning?

A computer program is said to learn from experience $E$ with respect to some task $T$ and some performance measure $P$, if its performance on $T$, as measured by $P$, improves with experience $E$.

What are the core differences between Supervised Learning, Unsupervised Learning, and Reinforcement Learning?

Supervised Learning trains on labeled examples with known answers to predict unseen data. Unsupervised Learning finds hidden structure or patterns in data without known answers. Reinforcement Learning trains an agent interacting with an environment to learn policies that maximize cumulative rewards.

In Tom Mitchell's framework, what are the Task ($T$), Performance measure ($P$), and Experience ($E$) for the indoor vs. outdoor image classification problem?

Task ($T$): Distinguish indoor vs. outdoor images; Performance measure ($P$): Probability of misclassifying; Experience ($E$): Labeled examples of indoor and outdoor images.

In unsupervised language modeling, what are the Task ($T$), Performance measure ($P$), and Experience ($E$)?

Task ($T$): Next token (word) prediction; Performance measure ($P$): Perplexity (uncertainty or "confusion" of predicting the next word in a sequence); Experience ($E$): Large and diverse text datasets.

How are Task ($T$), Performance measure ($P$), and Experience ($E$) defined for an agent learning to play Atari arcade games via reinforcement learning?

Task ($T$): Play Atari arcade games; Performance measure ($P$): Winning or advancing; Experience ($E$): State, action, and reward sequences from previous gameplay episodes.

Why is eigenvalue calculation generally not considered a supervised learning task?

Eigenvalue calculation is a purely mathematical problem that has no labels or training data from which to learn.

What do the mathematical symbols $\mathcal{X}$, $\mathcal{Y}$, $f$, and $\mathcal{H}$ represent in the formal supervised learning framework?

$\mathcal{X}$ is the input space (set of possible instances), $\mathcal{Y}$ is the output space, $f: \mathcal{X} \rightarrow \mathcal{Y}$ is the unknown target function, and $\mathcal{H} = \{h \mid h: \mathcal{X} \rightarrow \mathcal{Y}\}$ is the hypothesis class (set of candidate models). The goal is to find $h \in \mathcal{H}$ that best approximates $f$.

What are the four feature types categorized in the lecture, and what defines each?

1. Nominal (including Boolean): Categorical values with no ordering among them; 2. Ordinal: Values with a total ordering; 3. Numeric (continuous): Real-valued measurements; 4. Hierarchical: Values partially ordered within a tree or hierarchy.

What is the dimension of the feature space for an image from the CIFAR-10 dataset, consisting of $32 \times 32$ color images across $10$ classes?

The dimension is $3072$, because each color image has $3$ color channels (RGB) and $32 \times 32$ pixels ($3 \times 32 \times 32 = 3072$).

How does the output space $\mathcal{Y}$ distinguish classification from regression?

In classification, the output space $\mathcal{Y}$ is discrete (elements are categorical classes, either binary or multi-class). In regression, the output space $\mathcal{Y}$ is continuous (real-valued numbers).

What is the objective of Empirical Risk Minimization (ERM) in supervised learning?

To select a hypothesis $\hat{f} \in \mathcal{H}$ that minimizes the average loss over the training instances: $\hat{f} = \arg\min_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \ell(h(x^{(i)}), y^{(i)})$, where $\ell$ is the loss function.

What is the key difference between batch learning and online learning?

Batch learning receives all training instances at once to train the model, whereas online learning receives instances sequentially and updates the model incrementally.

Why do time-series instances violate the common theoretical assumption that training instances are independent and identically distributed (i.i.d.)?

Instances from time series usually have temporal dependencies on previous instances rather than being mutually independent.

What geometric diagram, shown below, defines the decision regions of a 1-Nearest Neighbor (1NN) classifier?

A Voronoi diagram, where each convex polygonal cell contains all points in the space that are closer to a particular training point than to any other training point.

What is the classification decision rule for a $k$-Nearest Neighbors ($k\text{NN}$) algorithm?

It finds the $k$ most similar training points to a test point and assigns the plurality class (the most popular class among the $k$ neighbors): $\hat{y} = \arg\max_{y \in \mathcal{Y}} \sum_{i=1}^k \mathbb{1}(y = y^{(i)})$.

How are Hamming distance, Euclidean distance, and Manhattan ($L_1$) distance defined between instances $x^{(i)}$ and $x^{(j)}$?

Hamming distance (discrete): $d_H(x^{(i)}, x^{(j)}) = \sum_{a=1}^d \mathbb{1}\{x^{(i)}_a \neq x^{(j)}_a\}$; Euclidean distance (continuous): $d(x^{(i)}, x^{(j)}) = \sqrt{\sum_{a=1}^d (x^{(i)}_a - x^{(j)}_a)^2}$ ; Manhattan distance: $d(x^{(i)}, x^{(j)}) = \sum_{a=1}^d |x^{(i)}_a - x^{(j)}_a|$.

What is the standardization procedure for features in $k\text{NN}$, and why is it applied?

Empirical mean $\mu$ and standard deviation $\sigma$ are computed from the training set, and features are transformed via $\frac{x - \mu}{\sigma}$ (applied identically to test points) to prevent features with larger scales from disproportionately dominating distance metrics.

What is the prediction formula for $k$-Nearest Neighbors ($k\text{NN}$) regression?

It finds the $k$ most similar training points to the test instance and outputs the mean label: $\hat{y} = \frac{1}{k} \sum_{i=1}^k y^{(i)}$.

Why is the weight function $w_i = (d(p, x_i))^{1/2}$ inappropriate for distance-weighted nearest neighbor algorithms?

Distance-weighted nearest neighbor requires weights to decrease as distance increases to give closer neighbors more influence; $w_i = (d(p, x_i))^{1/2}$ increases with distance, improperly giving higher weight to farther points.

What are the primary strengths and weaknesses of Instance-Based Learning methods like $k\text{NN}$?

Strengths: Easy to explain predictions, simple to implement and conceptualize, requires no explicit training phase, and often performs well in practice. Weaknesses: Sensitive to irrelevant and correlated features, computationally expensive at test/prediction time, and produces no interpretable model.

Given the 2D training dataset with points $(0,0):+$, $(1,0):+$, $(2,0):+$, $(2,2):+$, $(0,1):-$, $(0,2):-$, $(1,2):-$, and $(3,1):-$, what labels are predicted for $A(1,1)$ and $B(2,1)$ using a 3NN classifier with Euclidean distance?

Point $A$ is labeled $-$ (its 3 nearest neighbors are $(0,1)[-]$, $(1,0)[+]$, and $(1,2)[-]$). Point $B$ is labeled $+$ (its 3 nearest neighbors are $(2,0)[+]$, $(2,2)[+]$, and $(3,1)[-]$).