Machine Learning Lecture 06 Support Vector Machines

2022/02/20 21:12 PM posted in  Stanford CS229   comments
Tags:  #Stanford CS229

Naive Bayes

\(x_j = 1\{\text{word k appears in email}\}\)

Now build a generative model for this,
Gaussian model for p(x|y) and Bernoulli for p(y).

\[ \begin{aligned} p(x|y) =\prod ^d_{j=1}p(x_j|y) \end{aligned} \]

So the parameters for Naive Bayes model are,

  1. \(\phi_y = P(y=1)\) is the class prior, what is the chance that y is equal to 1.
  2. \(P(x_j=1|y=0) = \phi_{j|y=0}\)
  3. \(P(x_j=1|y=1) = \phi_{j|y=1}\)
\[\begin{aligned} \phi &=\frac{1}{n} \sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\} \\ \mu_{0} &=\frac{\sum_{i= 1}^{n} 1\left\{y^{(i)}=0\right\} x^{(i)}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=0\right\}} \\ \mu_{1} &=\frac{\sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\} x^{(i)}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\}} \\ \Sigma &=\frac{1}{n} \sum_{i=1}^{n}\left(x^{(i)}-\mu_{y^{(i)}}\right)\left(x^{(i)}-\mu_{y^{(i)}}\right)^{T} . \end{aligned} \] \[\begin{aligned} \phi_{j \mid y=1} &=\frac{\sum_{i=1}^{n} 1\left\{x_{j}^{(i)}=1 \wedge y^{(i)}=1\right\}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\}} \\ \phi_{j \mid y=0} &=\frac{\sum_{i=1}^{n} 1\left\{x_{j}^{(i)}=1 \wedge y^{(i)}=0\right\}}{\sum_{i=1}^{n} 1\left\{y^{(i)}=0\right\}} \\ \phi_{y} &=\frac{\sum_{i=1}^{n} 1\left\{y^{(i)}=1\right\}}{n} \end{aligned} \]

Than in prediction time, we use Bayes rule:

\[P(y=1|x) = \frac {P(x|y=1)\cdot P(y=1)}{P(x)} \]


\[P(x) = P(x|y=1)P(y=1) +P(x|y=0)P(y=0) \]

This algorithm will almost work, but here is where it breaks down.

NIPS, whose position is j = 6017.
\(P(x_{6017} = 1|y=1) = \frac{0}{\#\{y=1\}}\)
\(P(x_{6017} = 1|y=0) = \frac{0}{\#\{y=0\}}\)
Here we see the probability is zero. However, we cannot say the probability is zero just because we haven't seen it.

So Laplace Smoothing is used to describe to address this 0 divided by 0 problem.

Laplace Smoothing

The game Standard football team played and we are going to predict the game on 12/31.

So the win or not is our x.
So \(P(x=1) = \frac{\#'1's}{\#'1's + \#'0's} = \frac{0}{0+4} = 0\)
This is kind of mean, we cannot say they cannot win the last game just because they lost the first 4 games.

So what Laplace Smoothing did is add 1 on the number of 1s and the number of 0s

So \(P(x=1) = \frac{\#'1's}{\#'1's + \#'0's} = \frac{1}{1+5} = 1/6 \)

More generally, for \(x\in\{1,...k\}\)
We estimate

\[P(x=j)=\frac{\sum_{j=1}^{M} 1\left\{x^{(i)}=j\right\}+1}{M + k} \] \[\begin{aligned} \phi_{j \mid y=0} &=\frac{\sum_{i=1}^{n} 1\left\{x_{j}^{(i)}=1 , y^{(i)}=0\right\}+1}{\sum_{i=1}^{n} 1\left\{y^{(i)}=0\right\}+2} \end{aligned} \]

Now we can discretize a continuous valued feature to a discrete value feature.
\(P(x|y) = \prod^m_{j=1}P(x_j|y)\) This is a multinomial probability.

In practice, we often divide the value into 10 buckets, it works well enough.

Multivirate Bernoulli Event Model and Multinomial Event Model

Multivirate Bernoulli Event Model

“Drugs! Buy drugs now!”

Multinomial Event Model


With the Multinomial Event Model, we have \(P(x,y) = P(x|y)P(y)\)

\[\begin{aligned} P(x,y) &= P(x|y)P(y) \\ &= \prod^n_{j=1}P(x_j|y) P(y) \end{aligned} \]

Event Models

Comments on apply ML

SVM intros

Sometimes we want to find non-linear boundary.

We just map the \(x_1, x_2\) to high dimension vector \(\phi(x) = [x_1,x_2,x_1^2,x_2^2,x_1x_2,...]\). If we send this vector to logistic regression, logistic regression can learn non-linear decision boundaries.

Randomly choosing these features is a little bit of pain.

SVM now has very robust tool package for us, we can just run and chooese.
SVM does not need so many parameters.

  • Optimal margin classifier(separable case)
  • Kernels
    - When we map x to \(\phi(x)\) from \(\mathbb{R}^2\rightarrow\mathbb{R}^{10000}\). Kernels will help us with such mapping.
  • Ineperable case.

Optimal Margin Classifier

Functional Margin

The functional margin of the classifier is how confidently and accurately do you classify an example.

\[h_\theta(x) = g(\theta^Tx) \]

We get "1" if \(\theta^Tx > 0\)(\(h_\theta(x) = g(\theta^Tx) > 0.5\) ), get "0" if \(\theta^Tx < 0\).

If \(y^{(i)} = 1\), hope that \(\theta^Tx^{(i)} >> 0\);
If \(y^{(i)} = 0\), hope that \(\theta^Tx^{(i)} << 0\)

Geometric Margin

The green line looks much better than the red line.
We call the gree line the geometric margin.


  1. Labels: \(y\in\{-1,+1\}\). We will have h output values in \(\{-1,+1\}\) \[g(z)=\left\{\begin{aligned} 1 & \text { if } z \geqslant 0 \\ -1 & \text { otherise } \end{aligned}\right. \]
  2. The parameters of SVM will be w and b. \[h_{w,b}(x) = g(w^Tx + b) \] \(x\in\mathbb{R}^n, b \in \mathbb{R}\)

    \(W^TX = \sum^n_{i=1} w_ix_i + b\) Since we get rid of \(x_0\)

Functional Margin

Single Training Example

functional margin of hyperplane(just a staight line, a linear classifier) defined by (w,b) with respect to \((x^{(i)},y^{(i)})\):

\[\hat\gamma^{(i)} = y^{(i)}(w^Tx^{(i)} + b) \]
  • If \(y^{(i)} = 1\), want \(w^Tx^{(i)} + b >> 0\)
  • If \(y^{(i)} = -1\), want \(w^Tx^{(i)} + b << 0\)
  • So we want \(\hat\gamma^{(i)}>>0\)
  • If \(\hat\gamma^{(i)}>0\), that means \(h(x^{(i)}) = y^{(i)}\). That at least prove this logistic example is correct. At least the prediction is above 0.5.

The whole training sets(how well are you doing on the worst example in your traning set)

Functional margin wrt training set:

\[\hat\gamma = \min_i \hat\gamma^{(i)} \]

we assume the training set is linearly separable

One thing the functional margin has is it can be treated by just scaling the parameters.
In \(\hat\gamma^{(i)} = y^{(i)}(w^Tx^{(i)} + b)\), we can just simply scale w and b to get the functional margin scale same times. But it doesn't change any decision boundary. Doesn't do any better in classification.

So we can do

\[\begin{aligned} &\|\omega\| =1 \\ &(\omega, b) \rightarrow\left(\frac{\omega}{\| \omega||} \frac{b}{\lfloor\omega \|}\right) \end{aligned} \]

to prevent such cheating.

Geometric Margin

To find the functional margin, let's define the geometric margin.

Geometric margin is defined as the Euclidean distance from the point we classifying to the line.

Geometric margin of hyperplane (w,b) with respect to \((x^{(i)}, y^{(i )})\)

\[y^{(i)}=\frac{\omega^{\top} x^{(i)}+b}{\|\omega\|} \]

The relation between geometric(\(\gamma^{(i)}\)) & functional margin(\(\gamma^{(i)}/||w||\))

\[\gamma = \min_i \gamma^{(i)} \]

Optimal Margin Classifier

Choose w,b to maximize the \gamma

The optimal margin classifier is the baby SVM.

We want to have

\[\max_{\gamma,w,b} \gamma \] \[s.t. \frac{y^{(i)}\left(\omega^{\top} x^{(1)}+b\right)}{\|\omega\|} \geq \gamma \quad i=1, \ldots, m \]

We want to set Gamma as big as possible, which means we are maximizing the worst-case geometric margin.
Such problem is a convex optimization problem, it is difficult to solve it without gradient descent and initially known local optima and so on.

After several steps, we can rewrite the formula to the following:

\[\min_{w,b} ||w||^2 \] \[s.t. y^{(i)}(w^Tx^{(i)} + b) \geq 1 \]

s.t.: subject to