MIT 6.790 — Lecture 1

Introduction to Machine Learning

§ Setting Up

Here's the classic machine learning setup.

There is an input space $\mathcal{X}$ and an output space $\mathcal{Y}$ .

The input space is often $\mathbb{R}^D$ , where $D$ is the feature dimension.
The output space can be, say, $\{0, 1\}$ for a classification problem, or $\mathbb{R}$ for a regression problem.
There is a training set $\{(x^{(n)}, y^{(n)})\}_{n = 1}^N$ , where $x^{(n)} \in \mathcal{X}$ is the $n^{\text{th}}$ input, and $y^{(n)}$ is its output.
There is a decision rule or hypothesis $h: \mathcal{X} \to \mathcal{Y}$ inferred from the training set.
There is a loss function $L: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}$ , where $L(a, g)$ is the penalty for guessing $g$ when the answer is $a$ .

Remark. The loss function may be asymmetric; consider, say, email spam detection.

§ The Optimal Hypothesis (Given the Distribution!)

Definition (Risk). A decision rule $h$ has risk defined by $\mathrm{risk}(h) := \mathbb{E}[L(Y, h(X))]$ .

Assume that all data $(x^{(n)}, y^{(n)})$ (training or not) is drawn i.i.d. from the same distribution. Unsurprisingly, if we know this distribution $p(x, y)$ exactly, finding the best $h$ is not hard.

Theorem. (Optimal Hypothesis) Suppose $\mathcal{X}$ is discrete and $\mathcal{Y} = \{1, \dots, K\}$ . Then the following minimizes risk:

h(x) = \argmin_k \sum_{j = 1}^K \underbrace{L(j, k)}_{\text{cost}} \cdot \underbrace{p(y = j \mid x)}_{\text{probability}}.

Proof: Immediate from the definition of risk. You can generalize this to the continuous case if you'd like, too. $\blacksquare$

The optimal $h$ takes a pretty nice form when we consider regression problems with a particular choice of loss. (Refer to Lecture 24 from 18.650 for additional context on why the loss function is what it is.)

Theorem. (Optimal Regression Hypothesis) Assume $\mathcal{X} = \mathbb{R}^D$ , $\mathcal{Y} = \mathbb{R}$ , and $L(a, g) = (a - g)^2$ . Then an optimal decision rule is $h(x) = \mathbb{E}[Y \mid X = x]$ .

Proof: For a particular $x$ , we seek to find the $k \in \mathbb{R}$ that minimizes the following “expected cost”:

C(k) := \int_{y \in \mathbb{R}} (y - k)^2 \cdot p(y \mid x) \, \mathrm{d}y.

Any minimizing $k$ must satisfy $C'(k) = 0$ , or:

C'(k) = \int_{y \in \mathbb{R}} -2(y - k) \cdot p(y \mid x) \, \mathrm{d}y = 0 ~ \implies ~ \underbrace{\left(\int_{y \in \mathbb{R}} y \cdot p(y \mid x) \, \mathrm{d}y\right)}_{\mathbb{E}[Y \mid X = x]} = \underbrace{\left(\int_{y \in \mathbb{R}} k \cdot p(y \mid x) \, \mathrm{d}y\right)}_{k}

Thus $k = \mathbb{E}[Y \mid X = x]$ is a critical point. Furthermore, $C''(k) > 0$ for all $k \in \mathbb{R}$ , as shown below.

C''(k) = \int_{y \in \mathbb{R}} 2 \cdot p(y \mid x) \, \mathrm{d}y = 2

Thus $k = \mathbb{E}[Y \mid X = x]$ must be the unique minimizing value. $\blacksquare$

Of course, the challenge of ML is that we don't know what $p$ is…