1、結構風險最小化

我們想要在未知的數據上得到低的錯誤率，這叫做structural risk minimization;相對的，訓練誤差叫做empirical risk minimization

要是我們能有這樣一個式子就好了：
$$\text{?Test?error?rate?}<=\text{?train?error?rate?}+f(N,h,p)$$
其中，
$\mathrm{N}=$ size of training set,
$\mathrm{h}=$ measure of the model complexity,
$p=$ the probability that this bound fails

我們需要一個$p$來限制最差的測試集的情況。然后我們就能通過選擇模型復雜度$h$來最小化測試誤差率的上界。

2、VC維（Vapnik-Chervonenkis dimension）

VC維就是衡量模型復雜度的一個重要概念

選擇$n$個樣本點，我們隨機的給它們分配標簽，如果我們的模型都能將它們分開，則樣本的VC維$>=n$,我們不斷地增大$n$，直到模型不能分開為止。模型能分開的最大的$n$值就是模型的VC維。

考慮一條二維空間的一條直線的復雜度。如上圖所示，對于三個數據點，無論我們如何分配標簽，直線都能很好的將樣本正確分類。但是對于四個數據點，直線無法處理異或問題。因此，二維空間中一條直線的VC維是3.

二維空間中的超平面的VC維是3。更一般的，k維空間的超平面的VC維是k+1。

超平面的VC維與參數的數目相等。但這只是個巧合，事實上，模型的參數和模型的復雜度并沒有必然的聯系。例如，一個正弦曲線的VC維是正無窮大，但是它的參數只有3個。
$$f(x)=a\sin (bx+c)$$

最近鄰分類器的VC維是無窮大的，因為無論你有多少數據點，你都能在訓練集上得到完美的分類器。而當$\text{?1-NN?}\to \text{?K-NN?}$,相當于減小了VC維。

一般來說，VC維越高，模型的分類能力更強，更flexible。但是VC維更多的是作為一個概念，實際上很難去計算一個模型的VC維。

---

---

回到剛才，經過前人推導，我們得到了一個測試集誤差的上界如下：
$$E_{\text{test?}}\le E_{\text{train?}}+{\left(\frac{h+h\log (2N/h)?\log (p/4)}{N}\right)}^{\frac{1}{2}}$$
$\mathrm{N}=$ size of training set
$h=VC$ dimension of the model class
$p=$ upper bound on probability that this bound fails

從上式看，$$\text{?Good?generalization?}\to \text{?large?}N\text{?and?small?}h$$
這是符合我們的直覺的。上面這個式子的推導很復雜，但是在實際中也沒啥用，因為它給的上界太松了，一個很松的上界又有什么意義呢。

3、Hard-Margin SVM

對于上面這個兩類分類問題，我們用直線進行分類，會發現有好多種分類方法。而SVM所選擇的那條直線，是將Margin 最大化的直線。

為什么要最大化Margin?

1. 直覺上感覺這最安全
2. 實際工作中確實不錯
3. 當數據有小波動時錯分的概率小一些
4. 模型只與support vector有關
   
   點到直線的距離：
   $$d(\mathbf{x})=\frac{|\mathbf{x}?\mathbf{w}+b|}{\sqrt{\Vert \mathbf{w}{\Vert }_2^2}}=\frac{|\mathbf{x}?\mathbf{w}+b|}{\sqrt{{\sum }_{i=1}^d{w}_i^2}}$$
   定義Margin:
   $$\mathrm{margin}\equiv \underset{\mathbf{x}\in D}{\mathrm{argmin}}d(\mathbf{x})=\underset{\mathbf{x}\in D}{\mathrm{argmin}}\frac{|\mathbf{x}?\mathbf{w}+b|}{\sqrt{{\sum }_{i=1}^d{w}_i^2}}$$
   所以我們就要考慮如何來最大化這個Margin了。

那么我們的問題就可以建模為：
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\mathrm{argmax}}\mathrm{margin}(\mathbf{w},b,D)\\ & =\underset{\mathbf{w},b}{\mathrm{argmax}}\underset{{\mathbf{x}}_i\in D}{\mathrm{argmin}}d\left({\mathbf{x}}_i\right)\\ & =\underset{\mathbf{w},b}{\mathrm{argmax}}\underset{{\mathbf{x}}_i\in D}{\mathrm{argmin}}\frac{\left|b+{\mathbf{x}}_i?\mathbf{w}\right|}{\sqrt{{\sum }_{i=1}^d{w}_i^2}}\end{array}$$
如果只是這樣的話，肯定是不行的，想像一下，一條直線離兩類都非常遠，也是符合上式的，因此需要附加條件，也就是直線能正確分類。
$$\begin{array}{c}\mathbf{W}{\mathbf{X}}_{\mathbf{i}}+b\ge 0\text{?iff?}{y}_i=1\\ \mathbf{W}{\mathbf{X}}_{\mathbf{i}}+b\le 0\text{?iff?}{y}_i=?1\\ y_i\left(\mathbf{W}{\mathbf{X}}_{\mathbf{i}}+b\right)\ge 0\end{array}$$
也就是
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\mathrm{argmax}}\underset{{\mathbf{x}}_i\in D}{\mathrm{argmin}}\frac{\left|b+{\mathbf{x}}_i?\mathbf{w}\right|}{\sqrt{{\sum }_{i=1}^d{w}_i^2}}\\ & \text{?subject?to?}?{\mathbf{x}}_i\in D:y_i\left({\mathbf{x}}_i?\mathbf{w}+b\right)\ge 0\end{array}$$
這邊對一個限制條件進行強化，假設
$$?{\mathbf{x}}_i\in D:\left|b+{\mathbf{x}}_i?\mathbf{w}\right|\ge 1$$
因為咱們是對w進行優化，所以本質上其實是一樣的，就是一個縮放的問題。

那么對里層的優化，有：
$$\underset{{\mathbf{x}}_i\in D}{\mathrm{argmin}}\frac{\left|b+{\mathbf{x}}_i?\mathbf{w}\right|}{\sqrt{{\sum }_{i=1}^d{w}_i^2}}\ge \underset{{\mathbf{x}}_i\in D}{\mathrm{argmin}}\frac{1}{\sqrt{{\sum }_{i=1}^d{w}_i^2}}=\frac{1}{\sqrt{{\sum }_{i=1}^d{w}_i^2}}$$

對于外層優化，只需最大化里層的下界就行，于是問題化為：
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\mathrm{argmin}}\sum _{i=1}^d{w}_i^2\\ & \text{?subject?to?}?{\mathbf{x}}_i\in D:y_i\left({\mathbf{x}}_i?\mathbf{w}+b\right)\ge 1\end{array}$$