Relevant Textbook Sections: 3.1 - 3.5
Cube: Supervised, Discrete, Nonprobabilistic
Lecture 4 Summary
Relevant Videos
Introduction
The previous lecture, we covered probabilistic regression. As a recap, in probabilistic regression, a generative model
allows us to perform different types of inference such as posterior inference for weight parameters as well as
posterior predictive for new data.
This lecture, we covered linear classification. The goal of classification is to identify a category $y$ given $\mathbf{x}$,
rather than continuous $y$.
Classification vs Regression
Conceptually classification is not too different from regression. We follow the same general forms:
- Choose a model (linear vs non-linear boundary)
- Choose a loss function
We will write out $\hat{y} \in C_1,\cdots,C_K$.
Depending on the problem, we encode $\hat{y}$ as $0/1$, $+/-$ or
one-hot vectors $\begin{pmatrix} 0 & 0 & 1 & 0 \end{pmatrix}$
Today's problem involves predicting $\hat{y}$ for a new example $x$. We are given the dataset $D = \{(x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_n, y_n) \}$, where $x_i \in \mathbb{R}$ and $y_i \in \{-1, 1\}$.
Method 1 (Review): Non-Parametric Models
We can still use KNN for classification by returning the majority vote of the neighbors of $\mathbf{x}$. We can also use kernel methods. The advantage of using kernel methods is that it is super flexible. However, it can also be very slow on large datasets (which happens at prediction time) and it can be difficult to interpret.
Method 2: Linear Classification
Choose a Model : Linear Boundary
We introduce a new parametric model. It is simple but we can use a basis $\phi$ to obtain complex boundaries of separation.
$$\hat{y} = \text{sign}(\mathbf{w}^T\mathbf{x} + w_0)$$
Before deciding on a loss, let's just understand this model and what it does:
We introduce a discriminant function: $h(x,w) = \mathbf{w}^T \mathbf{x} + w_0$. We predict:
\begin{equation}
\hat{y}=\left\{
\begin{array}{@{}ll@{}}
+1, & \text{if}\ h(\mathbf{x}, \mathbf{w}) > 0 \\
-1, & \text{otherwise}
\end{array}\right.
\end{equation}
and we take the sign of the discriminant function for any particular point to predict the associated classification of $y$.
The decision boundary between the two sets of training data is where the discriminant is equal to 0, and our goal is to optimize the discriminant.
Consider the decision boundary $\mathbf{w}^T\mathbf{x} + w_0 = 0$:
In the 2D case:
$$\begin{align*}
w_1x_1 + w_2x_2 + w_0 &= 0 \\
x_2 &= -\frac{w_1}{w_2}x_1 - \frac{w_0}{w_2}
\end{align*}$$
This is the equation of a line, so we have a linear boundary!
Generalizing: Consider a vector $\mathbf{s}$ connecting two points $\mathbf{x_1}$ and $\mathbf{x_2}$ on the boundary (
$\mathbf{s} = \mathbf{x_2} - \mathbf{x_1}$)
$$\begin{align*}
\mathbf{s}\cdot \mathbf{w} &= \mathbf{x_2}\cdot \mathbf{w} - \mathbf{x_1} \cdot \mathbf{w} \\
&= \mathbf{x_2}\cdot \mathbf{w} + w_0 - \mathbf{x_1} \cdot \mathbf{w} - w_0\\
&= 0 - 0 = 0
\end{align*}
$$
$\mathbf{s}$ is orthogonal to $\mathbf{w}$.
This implies that $\mathbf{w}$ is orthogonal to the boundary. $w_0$ gives the offset.
Choose a Loss Function : Hinge Loss
Let's consider the the $0/1$ function:
$$
\ell_{0/1}(z) =
\left\{ \begin{array}{cc}
1 \quad& z > 0 \\
0 \quad& \text{else}
\end{array} \right.
$$
and the loss function
$$\mathcal{L}(\textbf{w}) = \sum_{n=1}^N \ell_{0/1}\left(-y_n(\mathbf{w}^T\mathbf{x}_n + w_0)\right)$$
that penalizes if the signs of $y_n$ and $\mathbf{w}^T\mathbf{x}_n + w_0$ do not match.
At first blush, this loss function makes sense. It scales with the number of misclassified points, an intuitive metric for understanding the loss of a classifier. There is however an issue with this loss. It has uninformative gradient. We are either right or wrong. Taking the gradient will yield 0 at all points (except for the origin), regardless of whether a point was correctly classified. As such, we look for a new loss function that has a more informative gradient.
Student question: How do you initialize the weight matrix, $\mathbf{w}$? Answer: you can choose any initial weight matrix. In the next section, we show how to reduce the loss by tuning the weight matrix.
Let us now consider hinge loss or linear rectifier function. Let us define $z = \mathbf{w}^T \mathbf{x} + w_0$.
$$
\ell_{\text{hinge}}(z) =
\left\{ \begin{array}{cc}
z \quad& z > 0 \\
0 \quad& \text{else}
\end{array} \right. = \max(0,z)
$$
and the loss function
$$\begin{align*}
\mathcal{L}(\textbf{w}) &= \sum_{n=1}^N \ell_{\text{hinge}}\left(-y_n(\mathbf{w}^T\mathbf{x}_n + w_0)\right) \\
&= -\sum_{m \in S}y_m(\mathbf{w}^T\mathbf{x}_m + w_0)
\end{align*}
$$
where the set $S$ consists of all $n$ such that $\text{sign}(y_n) \neq \text{sign}(\mathbf{w}^T\mathbf{x}_n + w_0)$
Now, we can take gradients!
$$\frac{\partial}{\partial \mathbf{w}}\mathcal{L}(\textbf{w}) = -\sum_{m \in S}y_m\mathbf{x}_m$$
Note: We have absorbed the bias term into $\mathbf{w}$ here. Also, our loss function is convex. For each data point we try to optimize, we are trying to improve the loss. By improving the loss on individual data points (which can each be thought of as a separate optimization problem), we are improving the loss over the entire dataset.
Student Question: If the data is separable, does this algorithm choose the decision boundary that best separates the data? Because the gradient of the loss is only non-zero when the point is mis-classified, any decision boundary that separates the points will have zero loss. The algorithm here does not discern between the decision boundaries that all have zero loss (even if we can visually see that the decision boundary works but is not optimal).
Comments:
- Convex and differentiable function can be minimized via gradient descent
- Convex optimization is polynomially solvable
How to solve for $\mathbf{w}^*$
We can use
stochastic gradient descent to optimize $\mathbf{w}$ : Use a
mini-batch of
our data (good if datatset is larger; noisier gradient though!). Using SGD requires using a variable step size for gradient descent!
What if we took just
one (incorrectly classified) datum:
$$\mathcal{L}^{(i)}(\mathbf{w}) = -y_i\mathbf{w}^T\mathbf{x}_i$$ and
$$\mathbf{w} \leftarrow \mathbf{w} + \eta y_i \mathbf{x}_i$$
This is the 1958
Perceptron algorithm : if $\hat{y} = y_n$, do nothing; else do above, until no error.
This converges if and only if the data are linearly separable in the feature space.
Extensions:
- We can also think about multi-class classifications, where $y_k \in {C_1, \dots, C_k}$ (ie. the output variable can be classified into multiple different groups). You can perform "all vs one" training by training $k$ different binary classifiers, before taking $\textbf{argmax}_k h_(\mathbf{x}, \textbf{w})$.
- You can perform basis transforms to solve classification problems that don't have a linear decision boundary.
Metrics
There are four error metrics
| Metric | y | y-hat |
|---|
| True Positive | 1 | 1 |
| False Positive | 0 | 1 |
| True Negative | 0 | 0 |
| False Negative | 1 | 0 |
These metrics can be combined to determine different kinds of rates such as
$$\begin{align*}
\text{precision} &= \frac{\text{TP}}{\text{TP} + \text{FP}} \\ \\
\text{accuracy} &= \frac{\text{TP} + \text{TN}}{\text{TP} + \text{TN} + \text{FP} + \text{FN}}\\ \\
\text{true positive rate} &= \frac{\text{TP}}{\text{TP} + \text{FN}} \\ \\
\text{false positive rate} &= \frac{\text{FP}}{\text{FP} + \text{TN}} \\ \\
\text{recall} &= \frac{\text{TP}}{\text{TP} + \text{FN}} \\ \\
\text{F1} &= \frac{2\cdot \text{precision}\cdot\text{recall}}{\text{precision}+\text{recall}}
\end{align*}
$$