0%

A short introduction to SVM

# Empirical Risk and the true Risk

We can try to learn $$f(x,\alpha)$$ by choosing a function that performs well on training data:

$$R_{emp}\left(\alpha\right)=\frac{1}{m}\sum_{i=1}^{m}{l\left(f\left(x_i,\alpha\right),y_i\right)}$$

where $$l$$ is the zero-one loss function.
Vapnik and Chervonenkis showed that an upper bound on the true
risk
can be given by the empirical risk + and additional term:

$$R\left(\alpha\right) \leq R_{emp}\left(\alpha\right)+\sqrt{\frac{h\left(\log\left(\frac{2m}{n}+1\right)\right)-\log \left(\frac{n}{4} \right)}{m}}$$

where $$h$$ is the VC dimension of the set of functions parameterized by$$\alpha$$

1. The VC dimension of a set of functions is a measure of their capacity or complexity

2. If you can describe a lot of different phenomena with a set of functions then the value of h is large.

VC dim = the maximum number of points that can be separated in all
possible ways by that set of fuctions.

# VC dimension and capacity of functions

Simplification of bound:
Test Error $$\leq$$ Training Error + Complexity of set of Models

# Capacity of hyperplans

Vapnik and Chevrvonenkis also showed the following:
Consider hyperplans $$(wx=0)$$where $$w$$ is normalized w.r.t. a set of points $$X^{\star}$$ such that: $$min_i|wx_i|=1$$

the set of decision functions $$f_w(x)=sign(wx)$$ defined on $$X^{\star}$$ such that $$||w|| \leq A$$ has a VC dimension satisfying

$$h \leq R^2A^2$$

where $$R$$ is the radius of the smallest sphere around the origin containing $$X^{\star}$$. So we would like to find the function which minimizes an objective like:
Training Error + Complexity term
We write that as:

$$\frac{1}{n}\sum_{i=1}^{n}l\left(f\left(x_i,\alpha\right),y_i\right)+ \text{ Complexity term}$$

For now we will choose the set of hyperplans, so $$f(x)=wx+b$$:

$$\frac{1}{n}\sum_{i=1}^{n}l\left(f\left(x_i,\alpha\right),y_i\right)+{\|w\|}^2$$

subject to $$min_i|wx_i|=1$$. That function before was a little fifficult to minimize because of the step function in $$l(y,\hat{y})$$. Let’s assume we can seperate the data perfectly. Then we can optimize the following: minimize $${\|w\|}^2$$, subject to:

\begin{align} (wx_i+b) & \geq 1, if \quad y_i=1 \\ (wx_i+b) & \leq -1, if \quad y_i=-1 \end{align}

the last two constraints can be compacted to:

$$y_i(wx_i+b)\geq1$$