台大机器学习技法学习笔记

机器学习

---

Lecture 1: Linear hard-margin SVM

1.Large-Margin Separating Hyperplane

--

   之前我们介绍过PLA算法，即在线性可分的数据中，找到一条线，能够区分开正负样本.但是PLA的解具有随机性的特点，不同的解具有对噪声不同的容忍度，即点向分类超平面扩展的区域大小对应对于噪声的容忍度。这个边界越大，代表对噪声的容忍度也越大，而从边界线的角度来讲，即从边界线向两侧延伸直到遇到点的这个所谓的“垫子”——我们称之为margin，margin越大，也代表此分类超平面具有最大的鲁棒性，对噪声的容忍度最强。
  线性可分支持向量机：
给定线性可分训练数据集，通过间隔最大化或等价求解相应的凸二次规划问题学习得到的分离超平面为

$$w^Tx + b = 0$$
以及相应的分类决策函数
$$f(x) = sign(w^Tx + b )$$
称之为线性可分支持向量机。
  当训练数据集线性可分时，对于PLA来说存在无数多个超平面可以将其正确分开，而linear SVM利用间隔最大化求得唯一的最优分离超平面。

2.Standard Large-Margin Problem

  有了linear SVM的定义和要解决的问题之后，我们试图用数学语言来对其进行描述。我们先来看点到分离超平面的距离:
假设分离超平面外有点$x$，其对分离超平面投影和到超平面距离分别为$x_0$和$\gamma$，超平面法向量为$w$，则

$$x = x_0 + \gamma \cdot \frac{w}{||w||}$$
又$x_0$在分离超平面上
$$w^Tx_0 + b = 0$$
可得
$$\gamma = \frac{w^Tx + b}{||w||}$$
综合考虑两种分类结果，对$\gamma$绝对值化
$$\tilde{\gamma} = \frac{w^Tx + b}{||w||}$$
至此，我们的问题可以简述成：
$$\begin{matrix} \mathop{max}\limits_{w,b}&\tilde{\gamma}\\s.t. & y_i \left( \frac{w^Tx_i + b}{||w||} \right) \ge \tilde{\gamma},\quad i=1,2,...,N \end{matrix}$$
将式中的$\tilde{\gamma}$写成
$$\tilde{\gamma} = \frac{\hat{\gamma}}{||w||}$$
最优化问题变换为
$$\begin{matrix} \mathop{max}\limits_{w,b}& \frac{\hat{\gamma}}{||w||}\\s.t. & y_i ( w^Tx_i + b ) \ge \hat{\gamma}, \quad i=1,2,...,N \end{matrix}$$
式中$\hat{\gamma}$的取值不影响最优化问题的解。可以这样考虑：假设将$w$和$b$按比例更改为$\lambda w$和$\lambda b$，这时$\hat{\gamma}$也放大为$\lambda\hat{\gamma}$，但是这些改变对于最优化问题的目标函数和不等式约束都没有影响，产生的是一个等价的最优化问题。即我们可以任意缩放$\hat{\gamma}$而不影响y最优化问题的求解，于是将$\hat{\gamma}$取为1，并且注意到最大化$\frac{1}{||w||}$与最小化$\frac{1}{2}||w||^2$是等价的，于是得到如下的linear SVM学习的最优化问题
$$\begin{matrix} \mathop{min}\limits_{w,b}&\frac{1}{2}||w||^2\\s.t. & y_i ( w^Tx_i + b ) - 1 \ge 0, \quad i=1,2,...,N \end{matrix}$$

3.Support Vector Machine

  上面得到的问题形式和二次规划QP一致，所以可以使用二次规划的方法求解。二次规划的一般形式如下：

$$\begin{matrix} optimal \ u \ \leftarrow&QP(Q,p,A,c)\\ \mathop{\min}\limits_{u}&\frac{1}{2}u^TQu + p^Tu\\ s.t.& a_m^Tu \ge c_m,\ for \ m = 1,2,...,M \end{matrix}$$
  将linear hard SVM的求解公式套用QP一般形式，接下来就可以通过任何实现QP解法的工具计算求解，对于非线性问题，可以通过对x做二次转化或其他转化，然后求解。

4.Reasons behind Large-Margin Hyperplane

  相比较PLA的平面，linear hard SVM得到的平面结果更苛刻，由于有"厚垫子"，linear hard SVM不能shatter任意3个inputs，这说明有更少的dichotomie，更小的VC维度，也就有更好的泛化效果。同时，如果使用特征转换，可以使linear hard SVM进行一些更精细的分类。
  Linear hard SVM的解法中需要训练数据线性可分，然后通过缩放平面和等价转换，将原始问题转成QP问题求解。数据线性可分在实际情况中很难出现，所以linear hard SVM的应用价值比较有限。同时，在特征转换时，将原始数据映射到其他空间的计算无法省略。接下来课程中，会使用一些方法解决这两个问题，。

---

Lecture 2: Dual Support Vector Machine

  上一篇文章总结了linear hard SVM，解法很直观，直接从SVM的定义出发，经过等价变换，转成QP问题求解。这一讲，从另一个角度描述hard SVM的解法，不那么直观，但是可以避免feature转换时的数据计算，这样就可以利用一些很高维度（甚至是无限维度）的feature转换，得到一些更精细的解。

1.Motivation of Dual SVM

  上一节我们讲到SVM问题的定义，如下：

$$\mathop {\min }\limits_{b,W}\frac{1}{2}W^TW\\s.t.\quad y_n(W^TZ_n+b)\ge1,\quad for\ n=1,2,...,N$$

  这是一个线性约束问题，不方便优化，是否有一种方法可以将线性约束放到优化问题本身，这样就可以无拘无束的优化，而不用考虑线性约束了。拉格朗日提供了一种方法，可以达到这个目的，称之为拉格朗日乘子式，形式如下（式中，右边的是约束条件）：

$$\mathcal{L}(b,W,\alpha)=\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n(1-y_n(W^TZ_n+b))$$
  通过拉格朗日算子，我们可以把SVM问题转化为下式：
$$SVM\equiv\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\right)$$
  这是如何做到的呢？解释如下：
+
  对于大括号内的式子，我们是固定$\alpha$，变动$W$和$b$的值，我们考虑之前的约束条件$y_n(W^TZ_n+b)\ge1$，总体来讲会出现两种情况下的$W$和$b$，其中一种满足约束条件一种不满足约束条件，则$1-y_n(W^TZ_n+b)$在这两种情况下分别是负数和正数，而对于大括号里的式子 $$\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)=\mathop{\max}\limits_{\alpha_n\ge0}\left(\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n(1-y_n(W^TZ_n+b))\right)$$ 而言，既是此式分别趋向$\frac{1}{2}W^TW$和$+\infty$的过程，再带入SVM的式子，我们得到
$$\begin{split} SVM&\equiv\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\right)\\&=\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\left(\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n(1-y_n(W^TZ_n+b))\right)\right)\\&=\mathop{\min}\limits_{W,b}\left(\frac{1}{2}W^TW,+\infty\right) \end{split}$$
  所以，综上所述，SVM问题与此min max变换公式等价。 $$SVM\equiv\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\right)$$
  到这里做一个总结：通过拉格朗日乘子，我们重新定义一个无约束问题，这个无约束问题等价于原来的约束优化问题，从而将约束问题无约束化。

2.Lagrange Dual SVM

  上面的问题中先max后min的形式不方便求解，不过可以通过一番变化，导出max min的形式，这样就可以从内到外，先计算里面的min，然后计算外面的max。这种变化叫对偶变化。
  首先，对于一个固定的$\alpha'(\text{With all $\alpha'\gt0$})$有：

$$\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\ge\mathcal{L}(W,b,\alpha')$$
  则有
$$\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\right)\ge\mathop{\min}\limits_{W,b}\mathcal{L}(W,b,\alpha')$$
  的$\alpha'$有多重选择，但是上面的不等式一致成立，所以在众多的选择一个最大的，上面的等式变形为，
$$\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\right)\ge\mathop{\max}\limits_{\alpha_n\ge0}\left(\mathop{\min}\limits_{W,b}\mathcal{L}(W,b,\alpha')\right)$$
  上式右边的$\alpha'$和$\alpha$没有区别，故上式可变为：
$$\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\right)\ge\mathop{\max}\limits_{\alpha_n\ge0}\left(\mathop{\min}\limits_{W,b}\mathcal{L}(W,b,\alpha)\right)$$
  这样min max就和max min建立了联系，前者$\ge$后者，这种成为弱对偶，若是两者相等，就称为强对偶。而强对偶如何才能成立呢，需要满足如下的条件：

• 原始问题是凸形状的
• 原始问题线性可分（如转换到z域线性可分）
• 具有线性约束条件

  而SVM问题满足上述条件，即存在解$(b,W,\alpha)$对于等式两边都是最优解，即我们现在可以通过解相对简单的对偶问题来间接求解原始问题。

3.Solving Dual SVM

  经过之前的对偶变换，我们可以得到：

$$SVM\equiv\mathop{\min}\limits_{W,b}\left(\mathop{\max}\limits_{\alpha_n\ge0}\mathcal{L}(W,b,\alpha)\right)=\mathop{\max}\limits_{\alpha_n\ge0}\mathop{\min}\limits_{W,b}\left(\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n(1-y_n(W^TZ_n+b))\right)$$
max括号之内的部分已经没有约束，为求其最优解，先对b求偏导，可以得到：
$$\frac{\partial\mathcal{L}(b,W,\alpha)}{\partial{b}}= -\sum_{n=1}^N\alpha_ny_n=0$$
这个结果代入上面的式子：
$$\begin{split} SVM&=\mathop{\max}\limits_{\alpha_n\ge0}\mathop{\min}\limits_{W,b}\left(\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n(1-y_nW^TZ_n)-b\sum_{n=1}^N\alpha_ny_n\right)\\&=\mathop{\max}\limits_{\alpha_n\ge0}\mathop{\min}\limits_{W,b}\left(\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n(1-y_nW^TZ_n)\right)\\&=\mathop{max}\limits_{\alpha_n\ge0,\sum_{n=1}^N\alpha_ny_n=0}\mathop{\min}\limits_{W}\left(\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n(1-y_nW^TZ_n)\right)\text{（此时min式子中已没有b）}\\ \end{split}$$
继续对$W_i$求导：
$$\frac{\partial\mathcal{L}(b,W,\alpha)}{\partial{W_i}}=W_i -\sum_{n=1}^N\alpha_ny_nz_{n,i}=0$$
得到：
$$W= \sum_{n=1}^{N}\alpha_ny_nz_{n}$$
继续代入上面的式子，
$$\begin{split} SVM&=\mathop{\max} \limits_{all\ \alpha_n\ge0,\sum_{n=1}^N\alpha_ny_n=0,W= \sum_{n=1}^{N}\alpha_ny_nz_{n}}\left(\frac{1}{2}W^TW+\sum_{n=1}^N\alpha_n-W^TW\right)\\&=\mathop{\max} \limits_{all\ \alpha_n\ge0,\sum_{n=1}^N\alpha_ny_n=0,W= \sum_{n=1}^{N}\alpha_ny_nz_{n}}\left(\sum_{n=1}^N\alpha_n-\frac{1}{2}||\sum_{n=1}^N\alpha_ny_nz_n||^2\right)\text{(min式子已经消失)}\\ \end{split}$$

  现在对式子做几步变换，首先通过整体取负号的方式转化为min，接着把w代入，并将其他的约束条件写下：

$$\begin{matrix}\mathop{\min}\limits_{\alpha}&\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\alpha_n\alpha_my_ny_mz_n^Tz_m-\sum_{n=1}^N\alpha_n\\ s.t.&\sum_{n=1}^Ny_n\alpha_n=0\\&\alpha_n\ge0,for\ n=1,2,...,N \end{matrix}$$
到这里，现在的目标函数只与$\alpha$有关，形式满足二次规划（QP），容易能得到结果$\alpha$，继而通过之前的式子得到W：
$$W= \sum_{n=1}^{N}\alpha_ny_nz_{n}$$
  现在只剩下最后一个问题，如何计算b?在之前的简化过程中消去了b，上面的QP解与b无关。KKT条件帮助我们解决这个问题。如果原始问题和对偶问题都有最优解，且解相同，那么会满足KKT条件。这也是一个充分必要条件，其中很重要的一点是complementary slackness(互补松弛性)，该条件有下面等式成立，
$$\alpha_n(1-y_n(W^TZ_n+b))=0\\if\quad one\quad\alpha_n\gt0\Rightarrow b=y_n-W^Tz_n$$
理论上，我们只需要一个点就可以，但是实际上由于误差，可能会计算所有的b，然后求平均。而且由于这些点满足：
$$1-y_n(W^TZ_n+b)=0$$
即这些点就是支持向量。但是我们只用$\alpha_n\gt0$的点：
$$SV(a_i\gt0)\subseteq SV\ condidates(on\ boundary)$$
并且我们可以在计算$w$和$b$的时候，只计算SV的点，因为其他点$\alpha$为0：
$$W= \sum_{n=1}^{N}\alpha_ny_nz_{n}=\sum_{SV}^{N}\alpha_ny_nz_{n}\\b=y_n-W^Tz_n\ with\ any\ SV(z_n,y_n)$$
  由此我们可以得到，只有支持向量对于$w$和$b$的计算是有帮助的，其他的点统统无用。我们也可以得到：

SVM的定义

通过对偶最优解，确定支持向量，从而找到最粗的超平面。

4.Messages behind Dual SVM

  通过上面的计算，其实最后$w$是$（y_n,z_n）$的线性组合，同样，PLA中的$w$也是$（y_n,z_n）$的线性组合，只是SVM利用支持向量求解线性组合，PLA使用错误的向量求解。同理，逻辑回归、线性回归也有类似规律，这种现象c被称为"w represented by data"。
  本节使用对偶问题，从另外一个侧面求解了SVM，并且数学推导相对复杂，计算量也增加了许多，因为需要求解一个N*N维度的矩阵Q。但是，为什么要做这些事情呢，hard linear SVM要简单许多呢？其实换成对偶问题是为了利用kernel做铺垫，改kernel可以将维度转化的计算省略，从而可以计算很复杂的转化。

---

Lecture 3: Kernel Support Vector Machine

标签（空格分隔）： 机器学习

---

1.Kernel Trick

  上一次我们已经阐述了SVM的最佳解可以通过对偶问题来求得，而最终就是为了应用核技巧在其之上。
  核函数：设$\mathcal{X}$是输入空间，又称$\mathcal{H}$为特征空间，如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射：

$$\phi(x):\mathcal{X}\rightarrow\mathcal{H}$$
使得对所有的x，x'属于x，函数k（x，x'）满足条件
$$K(x,x') = \phi(x)\phi(x')$$
则称$K(x,x')$为核函数，$\phi(x)$为映射函数，式中$\phi(x)\phi(x')$为$\phi(x)$和$\phi(x')$的内积。

  核技巧的思想是，在学习与预测中只定义核函数$K(x,x')$，而不显式地定义映射函数$phi$。通常，直接计算$K(x,x')$比较容易，而通过计算$\phi(x)$和$\phi(x')$计算$K(x,x')$并不容易。而值得注意是，$\phi$是输入空间$\mathbf{R}^n$到特征空间h的映射，特征空间$\mathcal{X}$一般是高维的甚至是无穷维的（维度爆炸)。Kernel的本质是将向量feature转换与点积运算合并后的运算。

  常见kernel有线性、多项式线性高斯，各有利弊。

• 线性kernel
  不做feature转换，直接使用。不需要使用对偶技巧，直接使用linear hard SVM解。

  优点：计算效率高；结果解释性好。
  缺点：需要数据线性可分

2.Polynomial Kernel

• 多项式kernel
  对x进行多项式展开，一般的形式为：
  $$K_Q(x, x') = (\zeta + \gamma x^Tx')^Q$$
  其中a，b，Q为常量。

优点：相比线性kernel，对数据要求没有那么严格
缺点：需要选择的系数较多；Q太大会超出一些计算机的精度，一般Q<=3。

3.Gaussian Kernel

• 高斯Kernel

有些资料也称为RBF(Radial Base Function)，一般形式为:

$$K(x, x') = \exp (- \gamma ||x^Tx'||^2)^Q$$
其中a(>0)是常量。高斯kernel独到的地方是可以将原始数据x映射到无限维度空间中，x下面取$\gamma=1$的例子：
$$\begin{split} K(x, x') &= \exp (- \gamma ||x^Tx'||^2)^Q \\ &= \exp(- (x)^2) \exp(- (x')^2) \exp(2xx')\\ &= \exp(- (x)^2) \exp(- (x')^2) \left(\sum_{i=0}^{\infty}\frac{(2xx')^i}{i!}\right)\\&= \sum_{i=0}^{\infty}\left(\exp(- (x)^2) \exp(- (x')^2) \sqrt{\frac{2^i}{i!}}\sqrt{\frac{2^i}{i!}} (x)^i (x')^i\right)\\&= \sum_{i=0}^{\infty}\left(\left(\exp(- (x)^2) \sqrt{\frac{2^i}{i!}} (x)^i \right)\left( \exp(- (x')^2) \sqrt{\frac{2^i}{i!}} (x')^i\right)\right)\\ &= \phi(x)^T\phi(x') \end{split}$$
其中特征转化为：
$$\phi(x) = \exp(-x^2) \cdot\left(1, \sqrt{\frac{2}{1!}}x, \sqrt{\frac{2^2}{2!}}x^2,...\right)$$
这样，就完成了向无线维度转换。

优点：调试的系数较少；比线性和多项式更强大，几乎可以适应所有数据；不容易出现计算精度问题
缺点：无线维度无法解释；太强大，容易过拟合；计算开销大。

4.Comparison of Kernels

  核函数是SVM画龙点睛之笔，真的很佩服发现kernel的科学家。在实际使用SVM的过程中，很大一部分精力可能就是选择kernel和相关系数。Kernel还可以自定义，但是需要满足一些条件，具体可以参考讲义相关部分。

---

Lecture 4: Soft-margin SVM

1.Motivation and Primal Problem

  之前所讨论的SVM都是非常严格的hard版本，必须要求每个点都被正确的区分开。但是，实际情况时很少出现这种情况的，因为噪声数据时无法避免的。所以，需要在Hard-Margin SVM上添加容错机制，使得可以容忍少量噪声数据。

  软化SVM的思路类似正规化，在目标函数添加错误累加项，然后加一个系数，控制对错误的容忍度，并且在约束中添加错误容忍度的约束，形式如下：

$$\begin{matrix} \mathop{\min}\limits_{b,w,\xi}& \frac{1}{2}w^Tw + C \cdot \sum_{n=1}^{N} \xi_n\\ s.t.&y_n(W^Tz_n + b) \ge 1 - \xi_n \ \text{and} \ \xi_n \ge 0 \ \text{for all n} \end{matrix}$$
  现在问题就变成了（d+1+N）个变量和2N个约束。ξ用来描述错误的容忍度。C是常量，用来控制容忍度。C越大，由于min的作用，ξ错误就会变小，也就是对错误的容忍度变小，约束变苛刻，边界变窄；反之，容忍度越大，约束变宽松，边界变宽。

2.Dual Problem

  现在，将上面软化后的SVM问题进行对偶转化和简化，得到的结果和之前hard版本十分类似，好像遇到了老熟人：

$$\begin{split} SVM&=\mathop{\min} \limits_{0 \le \ \alpha_n\le C,\sum_{n=1}^N\alpha_ny_n=0,W= \sum_{n=1}^{N}\alpha_ny_nz_{n}}\left(\frac{1}{2}||\sum_{n=1}^N\alpha_ny_nz_n||^2 - \sum_{n=1}^N\alpha_n\right)\\ \end{split}$$
与hard-margin SVM相比，只多了N个约束。

3.Messages behind Soft-Margin SVM

α仍然可以使用QP方法计算得到，b的求解也是通过complementary slackness，但是在求解b的过程，可以将向量分为三类，很有参考意义，可用于数据分析。

首先看看complementary slackness条件：

$$\alpha(1 - \xi_n - y_n(w^Tz_n + b)) = 0\\ (C - \alpha_n)\xi_n = 0$$

• 当$\alpha = 0$时，$\xi =0$，表明其没有犯错，样本点被正确分类，远离边界或者在边界上
• 当$0 \lt \alpha \lt C$时，$\xi = 0$，向量在边界上, 称之为free SV
• 当$\alpha = C$时，向量在边界上（$\xi =0$），或者违反边界（$\xi \gt0$）。

4.Model Selection

  对于Gaussian SVM的参数$(C, \gamma)$通常通过validation来选择。而通过cross validation优化过的问题在于它优化的只是一个upper bound，于是通常被用于初步的检验。

---

Lecture 5: Kernel Logistic Regression

1.Soft-Margin SVM as Regularized Model

  我们现在来讲Kernel Logistic Regression，也就是把Kernel的技巧融合到逻辑回归里面。首先我们对比一下Hard-Marin Dual SVM和Soft-Margin Dual：

$$\text{Hard-Margin Dual}：\\ \begin{matrix} \mathop{\min}\limits_{\alpha} & \frac{1}{2} \alpha^T Q \alpha - 1^T \alpha \\ \text{s.t.} & y^T \alpha = 0 \\ & 0 \le \alpha_n \end{matrix} \\ \text{Soft-Margin Dual}：\\ \begin{matrix} \mathop{\min}\limits_{\alpha} & \frac{1}{2} \alpha^T Q \alpha - 1^T \alpha \\ \text{s.t.} & y^T \alpha = 0 \\ & 0 \le \alpha_n \le \color{red}{C} \end{matrix}$$
观察两者表达式我们可以得到Soft与Hard的区别只是在于$\alpha_n$有了上限$C$。而也因为如此，在实际上应用时，通常使用的还是Soft-Margin SVM为多。
  Soft-Margin SVM使用$\xi_n$充当松弛变量，它代表了犯错误的程度。
$$\begin{matrix} \mathop{\min}\limits_{b, w, \xi} & \frac{1}{2} w^Tw + C \cdot \sum_{n = 1}^{N} \xi_n \\ \text{s.t.} & y_n(w^Tz_n + b) \ge 1 - \xi_n \ \text{and} \ \xi_n \ge 0 \ \text{for all} \ n \\ \end{matrix}$$
对于松弛变量$\xi_n$有：
$$\xi_n = \mathop{\max} \left( 1 - y_n(w^Tz_n + b), 0 \right)\\ = \left[ 1 - y_n(w^Tz_n + b) \right]_+$$
其中，$\left[ 1 - y_n(w^Tz_n + b) \right]_+$因为形状的关系，被称为合页损失函数。
把$\xi_n$替换掉，形成无约束式：
$$\mathop{\min}\limits_{b, w} \quad \frac{1}{2} w^Tw + C \sum_{n = 1}^{N} \left[ 1 - y_n(w^Tz_n + b) \right]_+$$
把上式归纳浓缩一下：
$$\mathop{\min} \quad \frac{1}{2} w^Tw + C \sum \hat{\text{err}}$$
对比我们之前学过的L2 regularization：
$$\mathop{\min} \quad \frac{\lambda}{N} w^Tw + \frac{1}{N} \sum \text{err}$$
两者颇为相似，但是却不易直接使用regularization方法解SVM，因为它不是QP问题，不可以使用Kernel，而且合页损失函数并非处处可微，所以无法用于解SVM。
通过分析我们可以得到这样的结论：Soft-Margin SVM中的$C$和L2 regularization中的$\lambda$的作用是类似的，但是两者作用相反，我们可以假设$\lambda$变大，则对于错误的惩罚变大，那学习的时候更倾向于选择更小的$w$，而$w^Tw \le C$，于是$C$变小。

2.SVM versus Logistic Regression

  我们定义线性模型中的线性得分：
$s = w^Tz_n + b$
可以比较PLA、SVM和Logistic Regression的Error Function：

• $\text{err}_{0/1} (s, y)= [\![ys \le 0]\!]$
• $\hat{\text{err}}_{SVM} (s, y)= [ 1 - ys]_+$
• $\text{err}_{SCE} (s, y)= \log_2 (1 + \exp(-ys))$

从图像上可以看出，$\hat{\text{err}}_{SVM}$和$\text{err}_{SCE}$的曲线非常相似。而对比我们现在接触过的二元分类线性模型，发现SVM和LogReg在以优化的优点，以及都是$0/1$分部的宽松上限的缺点上来看，SVM和LogReg是很相似的。

3.SVM for Soft Binary Classification

  接下来我们讨论用Soft-Margin SVM用于LogReg的可能性。不管是把SVM的结果直接传到s函数当成LogReg还是把SVM的结果当做LogReg的初值，都是有一些不足。
  另外一种想法是，把SVM的结果再对应加上两个自由度再做LogReg，这样能充分发挥两者的优点：

$$\mathop{\min}\limits_{A, B} \quad \frac{1}{N} \sum_{n = 1}^{N} \log \left(1 + \exp \left(-y_n\left(A \cdot (W_{\text{SVM}}^T \Phi(x_n + b_{\text{SVM}})) + B\right) \right) \right)$$
也就是分别把LogReg和SVM-transform当做两阶段的学习。

4.Kernel Logistic Regression

  上面介绍的方法实际上并不是在$Z$空间做LogReg，只是把SVM在$Z$空间里面求解，再在$Z$空间用$A$和$B$微调，这只是一种近似解。
  如果我们真的想在$Z$空间做LogReg，这其中的关键在于$w$的最优解是否能被$z$线性表示。而这里我们有个结论就是任何L2-regularized linear model的最优解$w$都可以被$z$线性表示。这个结论可以用反证法证明。
  于是我们的问题变为L2-regularized logistic regression：

$$\mathop{\min}\limits_{w} \quad \frac{\lambda}{N}w^Tw + \frac{1}{N} \sum_{n = 1}^{N} \log \left(1 + \exp (-y_nw^Tz_n)\right) \\ $$
因为$w_* = \sum_{n = 1}^{N} \beta_nz_n$，于是：
$$\mathop{\min}\limits_{\beta} \quad \frac{\lambda}{N} \sum_{n = 1}^{N} \sum_{m = 1}^{N} \beta_n \beta_m K(x_n, x_m) + \frac{1}{N} \sum_{n = 1}^{N} \log \left(1 + \exp (-y_n\sum_{m = 1}^{N} \beta_m K(x_n, x_m))\right) \\ $$
因为这是一个$\beta$的无约束问题，可以许多最佳化问题的解法来求解。
  因为这里已经我们的问题变成了一个只含有$\beta$的最佳化问题，于是我们既可以把Kernel Logistic Regression看成是$\beta$的线性模型也可以看成是$w$的线性模型。

---

Lecture 6: Support Vector Regression

1.Kernel Ridge Regression

  上次我们讲到Representer Theorem，也就是对于任何L2-regularized线性模型：

$$\mathop{\min}\limits_{w} \quad \frac{\lambda}{N}w^Tw + \frac{1}{N} \sum_{n = 1}^{N} \text{err} \left( y_n,w^Tz_n \right) \\ $$
其最佳解为$w_* = \sum_{n = 1}^{N} \beta_nz_n$，于是对于所有的L2-regularized线性模型，都可以运用Kernel。那么有 regularized 的 regression（ridge regression）如何加入 kernel?
ridge regression problem：
$$\mathop{\min}\limits_{w} \quad \frac{\lambda}{N}w^Tw + \frac{1}{N} \sum_{n = 1}^{N} \left( y_n - w^Tz_n \right)^2 \\ $$
既然最佳解有$w_* = \sum_{n = 1}^{N} \beta_nz_n$，我们将它代入上面的式子：
$$\mathop{\min}\limits_{\beta} \quad \frac{\lambda}{N} \sum_{n = 1}^{N}\sum_{m = 1}^{M} \beta_n\beta_m K(x_n,x_m)+ \frac{1}{N} \sum_{n = 1}^{N} \left( y_n - \sum_{m = 1}^{M} \beta_m K(x_n,x_m) \right)^2 \\ $$
转化成了$\beta$的问题，我们可以使用Kernel trick。
上式转化为矩阵运算：
$$E_{aug}(\beta) = \frac{\lambda}{N} \beta^TK\beta + \frac{1}{N} \left(\beta^TK^TK\beta - 2\beta^TK^T\beta + y^Ty \right)$$
  这就是Kernel Ridge Regression。如何解除$\beta$的最佳解呢？这是一个无条件的最佳化问题。我们容易想到用梯度。
首先求$\beta$得梯度：
$$\begin{split} \nabla E_{aug}(\beta) &= \frac{2}{N} \left(\lambda K^TI\beta + K^TK\beta - K^Ty \right) \\ &= \frac{2}{N} K^T \left((\lambda I + K)\beta - y \right) \\ \end{split}$$
对$\beta$梯度取零我们得：
$$\beta = (\lambda I + K)^{-1}y$$
其中$\lambda I + K$由于$K$的半正定的性质此矩阵一定是可逆的。而对于矩阵求逆的运算，时间复杂度为$O(N^3)$，所以理论上我们解决了此问题。
  对比linear ridge regression和kernel ridge regression，我们可以得到，前者具有简单模型的效率高的优点的同时也有着拟合能力低的问题，而后者模型更加复杂，因为$K$的存在，曲线更加灵活多变，但是计算复杂度也比较大。

2.Support Vector Regression Primal

  如果把Kernel Ridge Regression用于分类，有个特别的名称叫做least-squares SVM (LSSVM)。 用同样的资料分别跑soft-margin Gaussian SVM和Gaussian LSSVM的结果，可以看出后者的SV的数量非常多，这是由于$\beta$矩阵的不稀疏造成的，这导致LSSVM在预测时的计算量过大。
  那么我们如何解决$\beta$矩阵不稀疏的问题呢？我们提出一种叫做Tube Regression的方法，核心思想是我们在分类超平面两侧造出两个类似“隧道”的分界面，样本点在隧道内我们认为这是小错误，忽略不计，如果在隧道外才算是错误，而错误的大小以与隧道的距离来计算。也就是：

$$\text{err}(y, s) = (0, \vert s - y \vert - \epsilon)_+$$
其中$\epsilon$作为我们对于错误的容忍度，只有超出$\epsilon$的那部分才算是错误。于是我们把问题转化成了
L2-regularized tube regression。我们先来比较一下
tube error和squared err的区别：
$$\text{err}_{tube}(y, s) = (0, \vert s - y \vert - \epsilon)_+ \\ \text{err}_{squared}(y, s) = (s - y )^2$$
通过观察两者图像我们可以发现，在$s$绝对值比较小的时候，两者基本类似，但是随着$s$绝对值的增大，tube的err没有squared的err增加得快，也就是说明tube的对于噪音的容忍度较高。
  我们来解L2-regularized tube regression的问题:
$$\mathop{\min}\limits_{w} \quad \frac{\lambda}{N}w^Tw + \frac{1}{N} \sum_{n = 1}^{N} (0, \vert w^Tz_n - y \vert - \epsilon)_+ \\ $$
模仿之前SVM的解法，引入新的参数：
$$\mathop{\min}\limits_{b, w} \quad \frac{1}{2}w^Tw + C \sum_{n = 1}^{N} (0, \vert w^Tz_n + b - y \vert - \epsilon)_+ \\ $$
之前我们处理如含有$()_+$这样形式的最佳化问题的时候的方法是引进新的参数，这里也一样吗，只不过这里由于绝对值得存在，参数变为两个，即：
$$\begin{matrix} \mathop{\min}\limits_{b, w, \xi^{\vee},\xi^{\wedge}} & \frac{1}{2}w^Tw + C \sum_{n = 1}^{N} (\xi^{\vee} + \xi^{\wedge}) \\ s.t. & -\epsilon - \xi^{\vee} \le y_n - w^Tz_n - b \le \epsilon + \xi^{\wedge} \end{matrix}$$
直接用上式做最佳化，和最初的SVM里的情形一样，由于维度的关系不易计算，于是我们先转化为对偶问题再使用Kernel trick。

3.Support Vector Regression Dual

  如何把上面的问题转化为对偶问题呢？当然是拉格朗日乘子了，只是这里需要两个乘子，分别是$\alpha^{\vee},\alpha^{\wedge}$。接下来通过与之前SVM里面讲的几乎完全一样，利用KKT条件得到：

$$\frac{\partial{\mathcal{L}}}{\partial{w_i}} = 0: w = \sum_{n = 1}^{N}(\alpha^{\wedge} - \alpha^{\vee})z_n \\ \frac{\partial{\mathcal{L}}}{\partial{b}} = 0: \sum_{n = 1}^{N}(\alpha^{\wedge} - \alpha^{\vee})z_n = 0 \\ \text{complementary slackness}: \\ \alpha^{\wedge}(\epsilon + \xi^{\wedge} - y_n + w^Tz_n + b) = 0 \\ \alpha^{\vee}(\epsilon + \xi^{\vee} - y_n + w^Tz_n + b) = 0$$
SVR 的对偶问题的形式也与SVM的对偶问题类似：
$$\begin{matrix} \mathop{\min} & \frac{1}{2} \sum_{n = 1}^{N}\sum_{m = 1}^{M} (\alpha_n^{\wedge} - \alpha_n^{\vee})(\alpha_m^{\wedge} - \alpha_m^{\vee})K_{n, m} + \sum_{n = 1}^{N}\left( (\epsilon - y_n) \cdot \alpha^{\wedge} + (\epsilon - y_n) \cdot \alpha^{\vee} \right) \\ s.t. & \sum_{n = 1}^{N}（\alpha^{\wedge} - \alpha^{\vee}） = 0 \\ & 0 \le \alpha^{\wedge} \le C , 0 \le \alpha^{\vee} \le C \end{matrix}$$
  通过对complementary slackness条件的分析，我们可以得到在tube里面的样本点的$\beta_n = 0$，而对于$\beta_n \ne 0$的样本点也就是在tube外面的样本点，其都是支持向量。这里我们也可以得到，tube并没有彻底解决$\beta$不稀疏的问题。

4.Summary of Kernel Models

  这里回顾我们之前讲过的Kernel模型。我们从开始到现在学了三种基本的线性模型，分别是PLA/pocket，linear ridge
regression和regularized logistic regression。而之前我么也讲过linear soft-margin SVM，也适用于解决线性分类问题。linear SVR，也是解决线性分类问题的一种选择。这些都是线性的模型，而我们也讲过，对于这些线性模型，如果我们加入regularization的部分，都可以转化为可以使用Kernel trick的模型，如linear soft-margin SVM延伸到SVM对偶问题，linear SVR延伸到SVR的对偶问题，而linear ridge regression也可以转化为kernel ridge regression。而regularized logistic regression也可以推导转化为kernel logistic regression，其中也有另外的一种两阶段训练的probabilistic SVM。
  在实际使用中，PLA/pocket和linear SVR因为对比其他模型没有什么显著地优势，使用的较少。那么kernel ridge
regression和kernel logistic由于$\beta$的不稀疏而导致的预测时候计算的困难而也是实际中不常被使用。
  剩余的这些模型，如kernel ridge regression、kernel logistic regression、SVM、SVR、probabilistic SVM等等，都是实际中很常用的模型，Kernel给这些模型带来几乎是无限的power的表现力的同时，我们同时也要注意Kernel也不是万能的，过大的powerful也会带来overfit听的危险，于是实际使用当中我要谨慎小心选择参数。

---

Lecture 7: Blending and Bagging

1.Motivation of Aggregation（动机）

   假设有T个朋友告诉你将来几天股市的假设，那我们到底选哪一个人的模型好呢？

• 你可以选择你最信任的朋友的假设，或者说选择你认为炒股最厉害的朋友；
• 你可以综合所有的朋友的建议，每个人投一票；
• 你可以选择一些朋友的票数占的更多，一些朋友的票数更少，即权重不一样；
• 你可以在不同的条件下听取不同朋友的意见；
  后面三个模型对应的数学表达式分分别为：
• $$G(X)=sign(\sum_{t=1}^{T}1*g_t(x))$$
• $$G(X)=sign(\sum_{t=1}^{T}\alpha _t*g_t(x))$$
• $$G(X)=sign(\sum_{t=1}^{T}q_t(x)*g_t(x))$$

   所以我们得到的混合模型(AggregationModel):把全部的假设进行混合或者结合，这样可以得出更好的假设。于是我们就得出了Aggregation Model（混合模型）的概念。
   为什么Aggregation(混合模型)可以工作？他有什么好处呢？作者用了一个二元分类的例子证明了混合模型确实要比单个模型做的更好。
  如果单个模型都不强，那我们在这些单个模型当中选择一个最好的也没用，但是我们把这些当模型组合起来的话就会得到很好的效果。Aggregation在这里既当油门又当刹车。
1）可以把不同的weakhypotheses混合，把模型变得更更好。就有点像feature transform
2）选择最好的Hypotheses，就像正则化。

2.Uniform Blending

1.Uniform Blending(Voting) for Classification(均匀混合（投票）的分类)
混合模型分类的数学表示是：

$$G(X)=sign(\sum_{t=1}^{T}1*g_t(x))$$
从这个式子可以看出，如果 $g_t$ 都一样的话，就和单个模型做分类没有什么区别，所以 $g_t$ 不一样的话，实际结果是少数服从多数。
2.Uniform Blending(Voting) for regression（均匀混合(投票)的回归）
混合模型回归的数学表示是： $$G(X)=\frac{1}{T}\sum_{t=1}^{T}g_t(x)$$
从这个式子可以看出，有一些会高估，有一些会低估，平均一下的话刚好差不多。
3.Theoretical Analysis of Uniform Blending（均匀混合模型的原理分析）
$$avg((g_t(x)-f(x))^2)=avg((g_t(x)-G)^2)+(G-f)^2$$
从这个式子可以看出，G 的表现要比随便的一个$g_t$ 的表现要好，错误更低。

3. Linear and Any Blending

我们根据第一小节，我们知道linear Blending的一般表达式：

$$G(X)=sign\left( \sum_{t=1}^{T}\alpha _t*g_t(x)\right)$$ 根据G(x)，那我们怎么计算 $α_t$？我们通过：
$$\min_ {\alpha _t\geq 0}\frac{1}{N}\sum_{n=1}^{N}\left( y_n-\sum_{t=1}^{T}\alpha _t*g_t(x)\right)^2$$ 来得到。
   Linear and Any Blending的具体实现过程是：
  我们可以先从训练数据得到各种hypothesis, blending则可以在Cross Validation数据上完成：现将这些h作用在x上得到各种z, 然后利用(z, y)作为输入数据，求解出一个线性(linear-blending)/非线性(any-blending, 也称为stacking)系数。这个线性/非线性稀疏就是各个h的组合系数。注意any-blending方式容易过拟合。

4. Bagging (Bootstrap Aggregation)

为了设计出不同的h, 我们通常会使用下面这几种方法：
1）diversity by different models # 不同模型
2）diversity by different parameters # 不同参数
3）diversity by algorithmic randomness # 算法随机性
4）diversity by data randomness # 数据随机性，这个分为两种：一种是随机进行划分训练和CV，另外一种则是从已有数据利用重新抽样的方式生成新的数据集合(bootstrapping).
  bootstrapping操作是这样的：在大小为N的数据集合上，随机并且可以有放回地取N'次，取出的数据集合大小为N'。 bagging是利用bootstrapping重新生成一些新的数据集合，在这些新的数据集合上训练出H，然后将这些h平均组合起来。
  bagging：bootstrap aggregating的缩写。让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练样本组成，某个初始训练样本在某轮训练集中可以出现多次或根本不出现，训练之后可得到一个预测函数序列 $h_1，⋯ ⋯h_n$，最终的预测函数H对分类问题采用投票方式，对回归问题采用简单平均方法对新示例进行判别。

---

Lecture 8: Adaptive Boosting

1.Diversity by Re-weighting

  在上一讲当中我们知道：为了设计出不同的h,我们通常的做法是diversity by data randomness，即bootstrapping方法。操作是这样的：在大小为N的数据集合上，随机并且可以有放回地取N'次，取出的数据集合大小为N'。这样，数据就更多样化，实例证明，得到的效果就会更好。
  那在本小节要解决的只有一个问题：how to re-weight for more diverse hypotheses?请看下面的推导过程：

$$E_{in}^u(h)=\frac {1}{N}\sum_{n=1}^{N}u_n\cdot \text{err}\left( y_n,h(x_n)\right)$$
这是经过一轮 bootstrap 之后的 error ,那我们最小化这个错误就得到我们需要的 $g_t$ .
$$g_t\quad \leftarrow \quad \mathop{argmin}_{h\in\mathcal{H}}\left( \sum_{n=1}^{N}u_n^{(t)}[\![y_n\neq h(x_n) ]\!]\right)$$ $$g_{t+1}\quad \leftarrow \quad \mathop{argmin}_{h\in\mathcal{H}}\left( \sum_{n=1}^{N}u_n^{(t+1)}[\![y_n\neq h(x_n) ]\!]\right)$$
  $u_n^{(t)}$表示的意思是经过每一轮bagging之后得到的权重，我们现在就是要最小化经过bagging之后的error,从而选择 $g_t$，如果 $g_t$ 做得不好，那在下一轮当中就不应该被选到 .
  那我们怎么让$g_{t+1}$ 和 $g_t$ 不一样呢？对于二元分类问题，$g_t$ 做得不好的一种情况是就像丢硬币一样，出现正面的概率和反面概率都是二分之一，那我们可以借鉴这一点，让 $g_t$ 这一轮的错误率为二分之一。所以有： $$\frac{\sum_{n=1}^{N}u_n^{(t+1)}[\![y_n\neq g_t(x_n) ]\!]}{\sum_{n=1}^{N}u_n^{(t+1)}}=\frac{1}{2}$$
  那下面我们举一个例子：假设总的有 7337 个，错误的 $u_n^{(t)}=$ 1126 个，正确的 $u_n^{(t)}=$ 6211 个。那 $$\text{incorrect:}\quad u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot 6211$$ $$\text{correct:}\quad u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot 1126$$   这样处理之后概率就会为二分之一。在下一轮中就不会被选到。

2.Adaptive Boosting Algorithm

  令：

$$\epsilon _t=\frac{\sum_{n=1}^{N}u_n^{(t+1)}[\![y_n\neq g_t(x_n) ]\!]}{\sum_{n=1}^{N}u_n^{(t+1)}}$$
  令放缩因子：
$$\beta = \sqrt \frac{1-\epsilon _t}{\epsilon _t}$$
  那我们就可以有： $$\text{incorrect:}\quad \leftarrow \quad \text{incorrect}\quad\cdot \quad\beta$$ $$\text{correct:}\quad \leftarrow \quad \text{correct}\quad / \quad \beta$$
  当 $\epsilon _t\leq \frac{1}{2}$ ,则有 $\alpha \geq 1$，它的物理意义就是 scale up incorrect，scale down correct；对训练失败的训练例赋以较大的权重，对训练正确的赋予较小的权重。
  Adaptive Boosting算法的具体过程如下：
  首先，给定 $N$ 个资料，每一轮赋予每个资料的初始权重是 $\frac{1}{N}$ ;

• obtain $g_t$ by $\mathcal{A}\left(\mathcal{D} ,u_n^{(t)}\right)$,
  where $\mathcal{A}$ tries to minimize $u_n^{(t)}$ )-weighted 0/1 error
• update $u_n^{(t)}$ to $u_n^{(t+1)}$ by

$$\text{incorrect:}\quad \leftarrow \quad \text{incorrect}\quad\cdot \quad\beta$$ $$\text{correct:}\quad \leftarrow \quad \text{correct}\quad / \quad \beta$$

其中

$$\beta = \sqrt \frac{1-\epsilon _t}{\epsilon _t}$$ 和 $$\epsilon _t=\frac{\sum_{n=1}^{N}u_n^{(t+1)}[\![y_n\neq g_t(x_n) ]\!]}{\sum_{n=1}^{N}u_n^{(t+1)}}$$

• 计算 $$\alpha _t=\ln \beta$$
• 返回： $$G(X)=sign\left( \sum_{t=1}^{T}\alpha _t*g_t(x)\right)$$

  这就是整个算法的过程！

---

Lecture 9: Decision Tree

1.Decision Tree Hypothesis

  上面这个就是决策树。那用语言来定义决策树的话就是，林老师是这样定义的：a traditional learning model that realizes conditional aggregation。
  一颗大树可以分为很多小树（sub-tree）,分为树的节点（node）,树的叶子（leaf）。节点在这里就是条件 $q_t(x)$,如上图的 has a date?deadline? 叶子在这里就是 $g_t(x)$, 那在上面这棵树是常数。所以整棵树的数学表达式为：

$$G(x)=\sum_{t=1}^{T}q_t(x)*g_t(x)$$   也即： $$G(x)=\sum_{c=1}^{C}[\![ b(x=c)]\!]G_c(x)$$

• $G(x)$:full tree hypothesis
• $b(x)$:branching criteria
• $G_c(x)$:sub-tree hypothesis at the c-th branch

2.Decision Tree Algorithm

  首先，让我们来看一下一个基本的决策树算法的具体流程：

$$G(x)=\sum_{c=1}^{C}[\![ b(x=c)]\!]G_c(x)$$
$\left( I\right)$ 学习得分支条件 $b(x)$ ，也即是怎么做分支
$\left( II\right)$ 根据分支把资料 $D$ 分开成相应的几个部分，$\mathcal{D}=\{(x_n,y_n):b(x_n)=c\}$
$\left( III\right)$ 然后得到一颗小树（sub-tree）,$G_c\quad\leftarrow \quad \text{Decision tree}\quad \mathcal{D_c(x)}$
$\left( IV\right)$ 最后把这些小树组合就成了大树，$G(x)=\sum_{c=1}^{C}[\![ b(x=c)]\!]G_c(x)$
  那什么时候停止呢？ 如果终止条件（termination criteria）到了,就回传叶子 $g_t(x)$
  然后，下面介绍Classification and Regression Tree (C&RT)。
  C&RT演算法的特点是：
  每次分支一刀两断，即分成二元树 $C=2$ ,那在做分支的时候是根据什么做分支呢？我们可以根据 decision stump,看一个feature ,看完后决定切哪里，一边是+1，一边是-1，在C&RT演算法一半切为左边的子树，一半是右边的子树，那切完之后两边的资料是纯还是不纯（purifying）,所以要综合两边的纯度，加权起来，看一下哪个更纯。切完之后把不纯度最小化，就是我们想要的。
  $E_{in}$ 很高，就是不纯度很高， $E_{in}$ 很低，就是不纯度更低下面是怎么做分支的数学表达式。 $$b(x)=\mathop{argmin}_{\text{decision stumps h(x)}}\sum_{c=1}^{2}|\mathcal{D_c}\text {with h}|\cdot \text{impurity}(\mathcal{D_c}\text {with h})$$
  那不纯度是怎么计算的 ：
$\left( I\right)$ regression error: $$\text{impurity}(\mathcal{D})=\frac{1}{N}\sum_{n=1}^{N}(y_n-\mathop{y}^-)^2$$
$\left( II\right)$ classification error: $$\text{impurity}(\mathcal{D})=\frac{1}{N}\sum_{n=1}^{N}[\![ y_n\neq y^*]\!]$$ 其中，$y^*=\text{majority of } \{y_n\}$
$\left( III\right)$ classification error: $$1-\max_{1\leq k\leq K}\frac{\sum_{n=1}^{N}[\![ y_n= k]\!]}{N}$$ 其中，后面最大化的是纯度，1减去纯度就是不纯度。但是这里只考虑了一个 k ,只有当 $k=y^*$,最大化才会成立。
$\left( IV\right)$如果考虑所有的 k 呢？用下面的式子进行计算,即 Gini index: $$1-\sum_{k=1}^{K}\left(\frac{\sum_{n=1}^{N}[\![ y_n= k]\!]}{N} \right)^2$$
  所以我们一般用 Gini index for classification ,用regression error for regression。这就是本讲的重点内容。
  下面介绍C&RT停止时的条件：
$\left( I\right)$ 当所有的 $y_n$ 都一样的话，不纯度会为0，所以$g_t(x)=y_n$
$\left( II\right)$当所有的 $x_n$ 都一样的话，就没有 decision stump,就不能再分了。

---

Lecture 10: Random Forest

1.Random Forest Algorithm

  首先，对随机森林做总的概括：随机森林由许多的决策树组成，因为这些决策树的形成采用了随机的方法，因此也叫做随机决策树。随机森林中的树之间是没有关联的。当测试数据进入随机森林时，其实就是让每一颗决策树进行分类，最后取所有决策树中分类结果最多的那类为最终的结果。因此随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。
  随机森林由决策树组成，决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将当前的空间一分为二。
  下面具体介绍过程：其实随机森林就是用bagging的方式把一堆 decision tree 合起来，即，
$\left( I\right)$ 每一轮用bootstrapping的方式得到不同的资料，$\mathcal{D}\rightarrow \mathop{\mathcal{D_t}}^\sim$
$\left( II\right)$ 把这些得到的资料送到每一棵树（decision tree），经过树之后，我们会得到 $g_t$
$\left( III\right)$ 再把每一棵树的 $g_t$ 进行投票，即返回到bagging的方法。得到

$$G=\text{Uniform}\left(\{g_t\} \right)$$
  这就是 Random Forest。所以，我们可以把Random Forest写成一个等式： $$\text{Random Forest}=\text{bagging}+\text{fully-grown C&RT decision tree}$$
  我们在做bagging 的抽取资料过程当中，已经体现了随机性，那我们是否还有别的方法更好的体现随机性呢？我们知道 C&RT decision tree 只是看一个特征，然后进行切分。那如果我们随机地从资料的 d 个特征当中随机地选取 $d'$ 个特征，即：

• randomly sample $d'$ features from x

  技术上来说，我们做的事情是从100个维度里面随机选择10个维度，也就是做了一个投影的动作，所以我们会得到 $d'$ 个特征的子空间，也即：

• $\mathcal{X}\in R^d$, 转换的子空间 $\mathcal{Z}\in R^{d'}$;

  每一次做branch的时候，都做一次这样的投影，那么，随机森林的等式又可以进一步表示为:

$$\text{R F}=\text{bagging}+\text{random-subspace C&RT }$$
  如果我们把原来的特征乘上一个投影的矩阵，$\Phi(x)=P\cdot x$ ，如果我们把这些feature投影到任意的方向，而不是固定的方向，如原来方向的（固定方向）第一个方向和第三个方向的向量相加就会组合（combination)）成一个新的向量，那么，在做切割的时候方向就不固定了。在后面老师演示的例子当中我们可以很清楚的看到。那么，随机深林的等式又可以进一步表示为: $$\text{R F}=\text{bagging}+\text{random-combination C&RT }$$
  可见，随机森林的随机性无处不在！

2.Out-Of-Bag Estimate

  让我们再次回顾 bagging 和 bootstrapping 的过程，就像上面的这个表格，例如，我们在做 $g_1$ 的时候，我们选到了第一个资料和第 $N$ 个资料，而其他的资料没有被选到。上面的打星号的就是没有被选到的资料，我们称这些没有被选到的资料为 out-of-bag(OOB).
  那有多少资料没有被选到呢？如果 $N$ 足够大的话，我们可以这样计算：

$$\left( 1-\frac{1}{N}\right)^N=\frac{1}{\left( \frac{N}{N-1}\right)^N}=\frac{1}{\left(1+ \frac{1}{N-1}\right)^N}\approx \frac{1}{e}$$   即如果 $N$ 足够大的话，大概有三分之一的的资料没有被选到。

  根据上面这个表格，就是我们所学过的 validation ，蓝色的资料我们用来训练，红色的资料我们用来验证，那我们可以从这里得到的启发是：我们可以用 OOB 资料来做验证，那我们用 OOB 资料来验证 $g_t$ 还是 G 呢？当然是 G 。根据我们在基石课程当中所学的知识，我们可以求得：

$$E_{oob}(G)=\frac{1}{N}\sum_{n=1}^{N}\text{err}(y_n,G_n^-(x_n))$$
  由上面求得的结果我们马上就可以知道 G 的表现好不好，这体现了它能够自我验证的能力。

3.Feature Selection

  在我们进行特征选择的时候，在10000个维度当中，可能相关的就300个，所以我们要去掉一些冗余的资料，去掉我们不需要的特征或杂序。
  但是我们应该怎么选呢？可能在选择的过程当中，你可能从10000选300没做好的话，就可能会发生overfit 。其实我们之前在选择 $b(x)$ 的时候，已经在做选择，即到底切哪里。
  我们可以给每一个 feature 打一个分数，然后分数从高到低排序：

$$\text{score}=W^TX=\sum_{i=1}^{d}w^Tx$$   我们会发现，每个特征的重要程度有 $|w|$ 决定， $|w|$ 越大，重要性越大。即： $$\text{importance}(i)=|w_i|$$   我们可以送到一个线性模型当中来得到 w。但是 randmn forest 是非线性的。那怎么办呢？
  如果我们加入一些高斯噪声或其他噪声，比较重要的特征表现就会变差，就知道他的重要性。但是加入高斯噪声后改变了它原来的分布。所以我们可以进行 permutation test 。 $$\text{importance}(i)=\text{performance}(\mathcal{D})-\text{performance}(\mathcal{D^{(p)}})$$
   permutation的过程就是对数据重新随机排序，重新洗牌，打乱。上面这个等式的含义就是原来没有经过污染的资料的表现减去进过 permutation 之后之后的资料，得到的就是第 $i$ 个feature 的重要性。
  那我们怎么得到 performance 呢？那就是做 validation 。 $$\text{importance}(i)=E_{oob}(G)-E_{oob}^{p}(G)$$

---

Lecture 11: Gradient Boosted Decision Tree

１．Adaptive Boosted Decision Tree

  这一小节就是把　Decision Tree　搭配　AdaBoost，我们在前面都学过，只是把它们结合起来。结合后，就成了有权重的树，那我们可以不改变原来的演算法，只是在抽取资料的过程当中要适当改变，如果权重是３，那代表我们取到３份，我们可以根据权重进行sample。然后送到 decision tree算法当中，得到 $g_t$。
  第二步就是 $g_t$ 得到多少票，我们在学习 adaboost 过程当中知道，权重是：

$$\alpha _t =\ln \sqrt \frac{1-\epsilon _t}{\epsilon _t}$$   如果所有的 $x_n$都不同的话，decision tree 都可以把每一笔资料都切对，所以 $E_{in}$ 会为0； $$E_{in}=0 \Rightarrow \epsilon _t=0 \Rightarrow \alpha _t=\infty$$
  这样的话，一棵树的权重为无限大，只有这一棵树起作用，这不是我们想要的，那我们可以通过限制树的高度（pruned）来避免这种情况。

2.Optimization View of AdaBoost

  上面是 AdaBoost 权重迭代的过程，我们在第8讲当中有介绍，如果是正确的话，就是 $y_n$ 和 $g_t$ 是同号，所以相乘为+1，错误则相反。所以上面的式子会成立。把连乘转化为连加：

$$u_n^{(T+1)}=u_n^{(1)}\cdot \prod_{t=1}^{T}exp\left(-y_n\alpha _t g_t(x_n) \right)=\frac{1}{N}\cdot exp\left(-y_n\sum_{t=1}^{T}\alpha _t g_t(x_n) \right)$$   我们对 $g_t$ 进行投票，看看+1 的多还是-1的多,得到： $$G(X)=sign\left( \sum_{t=1}^{T}\alpha _t*g_t(x)\right)$$   下面我们介绍上面这个式子和 SVM 的 margin 的关系。如果把 $\alpha _t$ 换成 $w_i$ ,把 $g_t(x)$ 换成 $\phi(x)$,而 $$\text{margin}=y_i \left( \frac{w^T\phi(x_i) + b}{||w||} \right)$$   我们会发现，$\alpha _t*g_t(x)$ 这个分数（voting score）会和 margin 成正比。所以我们希望 $\left(y_n\sum_{t=1}^{T}\alpha _t g_t(x_n) \right)$ 越大越好，越大margin 才会越大，所以 $exp\left(-y_n\sum_{t=1}^{T}\alpha _t g_t(x_n) \right)$越小越好，所以 $u_n^{(T+1)}$ 越小越好。即每个点的权重越来越小，这个点的margin 就越来越大，所以，结论是：adaboost 可以达到 large margin 的效果。

  也即，让下面这个求和越来越小：

$$\sum_{n=1}^{N}u_n^{(T+1)}=\frac{1}{N}\sum_{n=1}^{N}exp\left(-y_n\sum_{t=1}^{T}\alpha _t g_t(x_n) \right)$$   AdaBoost 的错误函数就是： $$\hat{\text{err}}_{ADA}=\text{exp}(-ys)$$ $$s=\sum_{t=1}^{T}\alpha _t g_t(x_n)$$   它也是0/1错误的上限。那么，Adaboost 真的可以把0/1错误做的好吗？我们在基石课程当中有学到用梯度下降法来找到一个最好的 $w_t$ 使得 $E_{in}$最小化，那在这里同样可以适用，进行对比，可以得到下面的两个式子：

   经过上面的泰勒展开以及化简，第二个等式和第一个等式长得差不多，所以AdaBoost的错误函数就可以用我们以前学过的梯度下降法来处理，也就是我们要找到一个好的 $h$ ,最小化

$$\sum_{n=1}^{N}u_n^{(t)}\left( -y_nh(x_n)\right)$$    因为 $y_n$ 和 $h(x_n) \in\{-1,+1\}$ ,所以有：

  那是谁在最小化 $E_{in}^{u(t)}(h)$ 呢？从第8讲中我们知道是AdaBoost 里面的算法 $\mathcal{A}$ 。那具体的过程是，第一步，通过下面的最优化：

$$\min _{h} \hat E_{ADA}=\sum_{n=1}^{N}u_n^{(t)}exp\left( -y_n\eta h(x_n)\right)$$ 找到一个好的方向 $g_t$，然后看一下走多大步，即进行下面的优化： $$\min _{\eta} \hat E_{ADA}=\sum_{n=1}^{N}u_n^{(t)}exp\left( -y_n\eta g_t(x_n)\right)$$   然后，在 summation 当中又存在两种情况：

• $y_n= g_t(x_n)$的时候，即正确的， summation 里面会得到：$u_n^{(t)}exp(-\eta)$
• $y_n\neq g_t(x_n)$的时候，即错误的， summation 里面会得到：$u_n^{(t)}exp(\eta)$

由第8讲中：

$$\epsilon _t=\frac{\sum_{n=1}^{N}u_n^{(t+1)}[\![y_n\neq g_t(x_n) ]\!]}{\sum_{n=1}^{N}u_n^{(t+1)}}$$ 所以有： $$\hat E_{ADA}=\left(\sum_{n=1}^{N}u_n^{(t)} \right)\cdot \left((1-\epsilon _t)exp(-\eta)+ \epsilon_t exp(+\eta)\right)$$ 对上式求偏微分：
$$\frac{\partial \hat E_{ADA}}{\partial \eta}=0 \Rightarrow$$ $$\eta =\ln \sqrt \frac{1-\epsilon _t}{\epsilon _t}=\alpha _t$$ 和我们在第8讲中的权重是一样的。

３．Gradient Boosting

  在上一小节当中，我们已经知道 AdaBoost 的整个错误函数优化对应的数学表达式如下：

$$\min _{\eta}\min _{h} \frac{1}{N}\sum_{n=1}^{N}exp\left(-y_n\left(\sum_{\tau =1}^{t-1}\alpha _\tau g_\tau(x_n) +\eta h(x_n)\right)\right)$$
对于 exponential error with binary-output hypothesis h而言。
  如果对于任何的 error function呢？那 GradientBoost 就是：
$$\min _{\eta}\min _{h} \frac{1}{N}\sum_{n=1}^{N}\text{err}\left(-y_n\sum_{\tau =1}^{t-1}\alpha _\tau g_\tau(x_n) +\eta h(x_n),y_n\right)\tag{a}$$
所以，GradientBoost 比 AdaBoost 更多元化。下面介绍GradientBoost for Regression，同样可以用梯度下降法和求导进行优化，由： $$s_n=\sum_{\tau =1}^{t-1}\alpha _\tau g_\tau(x_n) \tag{b}$$ $$\text{err}(s,y)=(s-y)^2 \tag{c}$$ 先对（a）中的 $h$ 最小化进行泰勒展开，得到：

然后，我们继续优化，到了这一步，我们要最小化的 $h$ 只是一个方向，我们可以在后面的 $\eta$ 来控制它的步长。所以我们要最小化的是：

$$\min _h\text{constants}+\frac{\eta}{N}\sum_{n=1}^{N}2h(x_n)(s_n-y_n)$$
进一步优化， 那相当于最小化下面： $$\min _h\text{constants}+\frac{\eta}{N}\sum_{n=1}^{N}\left(2h(x_n)(s_n-y_n)+(h(x_n))^2\right)$$ $$=\text{constants}+\frac{\eta}{N}\sum_{n=1}^{N}\left(\text{constant}+ \left(h(x_n)- (y_n-s_n)\right)^2\right)$$ 其中，$y_n-s_n$称为 residual ,即目标分数减去当前做到的分数，那如果要最小化上面的等式，就可以用squared-error regression 的方法去做，然后得到 $g_t=h$ ,那下一步就是算步长：
$$\min _{\eta}\frac{1}{N}\sum_{n=1}^{N}(s_n+\eta g_t(x_n)-y_n)^2=\frac{1}{N}\sum_{n=1}^{N}((y_n-s_n)-\eta g_t(x_n))^2$$
这是一个单变数的最佳化问题。所以求解简单。这就是Gradient Boosting，那把它和 decision tree 结合起来的话，下面就是 GBDT 的整个流程：

GBDT在实际应用中比较流行的，可用于资讯检索以及网页排序。

---

Lecture 12: Neural Network

1.Motivation

我们这次讲神经网络，之前我们学过感知机，那么如果我们把感知机做Linear Aggregation，会发生什么样的变化呢？
例如：

$$G(x) = \text{sign} \left( \sum_{t=1}^{T} \alpha_t \underbrace{ \text{sign}(w_t^T x)}_{g_t(x)} \right)$$
其中含有两层权重$w_t$和$\alpha$和两层$sign$函数$g_t$和$G$。那么G能实现怎样的边界呢？我们来举个例子，例如我们有相互垂直的两个感知机$g_1$和$g_2$，并且通过：
$$G(x) = \text{sign} (-1 + g_1(x) + g_2(x))$$
可以通过真值表验证$G(x)$实现了布尔和运算：
$$G \equiv \text{AND}（g_1, g_2）$$
类似，用一层感知机也可以做到逻辑运算OR和NOT，从而我们可以得到一些复杂的边界。
  进一步增加感知机的数目，我们甚至能得到凸多边形的边界，边界也随着感知机增加而变得更加平滑，且：
$$d_{VC} \rightarrow \infty$$
可以验证一层的感知机的Linear Aggregation无法做到异或运算$XOR$，类似之前无法shatter的情况，那么如何才能实现$XOR$运算呢？
我们知道：
$$\text{XOR}（g_1, g_2）= \text{OR} \left( \text{AND}（-g_1, g_2）+ \text{AND}（g_1, -g_2）\right)$$
也即是我们把$AND$和$OR$组合起来就成了$XOR$，也就是使用两层的感知机的Linear Aggregation实现了我们想要的运算。
  综上，我们在一层里面使用多个感知机（aggregation of perceptrons）是模型变得powerful，而再在上面的基础上增加多层的感知机（multi-layer perceptrons），模型变得非常的powerful。这就是我们今天要讲的神经网络，它是一种从生物体内的神经元而启发来的模型。

2.Neural Network Hypothesis

  Neural Network Hypothesis的输出只是一个线性模型，即把上一层的输入做线性组合再通过决策函数，这个线性模型是任意的。我们在这里只考虑用平方函数当做错误函数的回归。
  神经网络里的每一个神经元里都有一个转换函数，那么我们应该使用哪种转换函数呢？ 其实不管是线性转换函数或者阶梯状转换函数都是有各自的缺点的：比如线性转换函数让整个模型都是线性函数而缺乏意义，阶梯函数是离散的并且难以优化。较流行的一种选择是使用双曲函数$\tanh(x)$，它更加容易优化，它与我们之前讲过的s型函数有这样的关系：

$$\tanh(s) = 2 \theta(2s) - 1$$
两者形状类似，只不过值域分别是$[-1, +1]$和$[0, +1]$
  神经网络的结构，其中：
$$\begin{matrix} \text{权重} W_{ij}^{(l)}： \left \{ \begin{matrix} 1 \le l \le L & 层\\ 0 \le i \le d^{(l - 1)} & 输入\\ 1 \le j \le d^{(l)} & 输出\\ \end{matrix}\right. \end{matrix}$$
$$\text{输入}s_j^{(l)} = \sum_{i = 0}^{d^{(l -1)}} W_{ij}^{(l)}x_i^{(l - 1)}$$

$$\begin{matrix} \text{输出} x_{j}^{(l)}： \left \{ \begin{matrix} \tanh(s_j^{(l)}) & l \lt L\\ s_j^{(l)} & l = L\\ \end{matrix}\right. \end{matrix}$$
  我们默认将输入$X$当第一层也就是输入层$X_0$，通过隐藏层得到$X^{(l)}$，而在输出层（最后一层）输出我们的决策结果$x_1^{(L)}$。
  在神经网络中的每一层我们都在做转化，而：
$$\phi^{(l)}(X) = \tanh \left( \left[\ \begin{matrix} \sum_{i = 0}^{d^{(l -1)}} w_{ij}^{(l)}x_i^{(l - 1)}\\ \vdots\\ \end{matrix}\right]\right)$$
是第$l$层的转化。而转化$\phi$代表了$X$匹配权重的多少，也是两者的“模式”的接近与否。所以我们可以把神经网络看成是一层一层在做模式的抽取。

3.Neural Network Learning

  如何决定神经网络好的权重呢？换一句话说，如何决定让神经网络的$E_{in}$降低的权重呢？如果神经网络只有一层的话，那么这个神经网络基本上就是感知机的aggregation，那么我们可以用以前学过的gradient boosting，也就是一个一个地决定隐藏的神经元。
  如果是多层的的情况呢？或许不能这样做。我们考虑一个关系，如果我们定义神经网络最后的输出与$y_n$的差别：

$$e_n = \left(y_n - \text{NNet} (x_n) \right)^2$$
如果我们讨论$e_n$与每一个权重的关系$\frac{\partial{e_n}}{\partial{w_{ij}^{(l)}}}$的话，我们是不是就可以用GD或者SGD来对这个问题做最佳化呢？答案是肯定的。
  如何计算错误与每一个权重的偏微分呢？直接考虑全部情况可能比较复杂，我们先讨论最后一层也就是输出层的关系式，也就是$\frac{\partial{e_n}}{\partial{w_{i1}^{(L)}}}$：
$$\begin{split} e_n &= \left(y_n - \text{NNet} (x_n) \right)^2 \\ &= (y_n - s_1^{(L)})^2 \\ &= \left( y_n - \sum_{d^{(L - 1)}}^{i = 0}w_{i1}^{(L)}x_{i}^{(L - 1)}\right)^2 \end{split}$$
于是有：
$$\begin{split} &\frac {\partial{e_n}} {\partial{w_{i1}^{(L)}}} \\ = &\frac {\partial{e_n}} {\partial{s_1^{(L)}}} \frac{\partial{s_1^{(L)}}}{\partial{w_{i1}^{(L)}}} \\ = & -2 \left( y_n - s_1^{(L)} \right) \cdot \left(x_{i}^{(L - 1)} \right) \end{split}$$
这是最后一层的关系，那不是最后一层呢？
$$\begin{split} &\frac {\partial{e_n}} {\partial{w_{ij}^{(l)}}} \\ = &\frac {\partial{e_n}} {\partial{s_j^{(l)}}} \frac{\partial{s_j^{(l)}}}{\partial{w_{ij}^{(l)}}} \\ = & \delta_j^{(l)} \cdot \left(x_{i}^{(l - 1)} \right) \end{split}$$
其中我们命名：
$$\delta_j^{(l)} = \frac {\partial{e_n}} {\partial{s_j^{(l)}}}$$
于是根据之前对于最后一层的推导，我们有：
$$\delta_1^{(L)} = -2 \left( y_n - s_1^{(L)} \right)$$
于是我们得到了最后一层的$\delta_1^{(L)}$，那前面几层的$\delta$如何计算？我们从式子可以看到，$\delta$反映的是错误与某一个神经元的输入的关系，而这个关系我们可以这样表示：
$$s_j^{(l)} \stackrel{\text{tanh}}{\Longrightarrow} x_j^{(l)} \stackrel{w_{jk}^{(l + 1)}}{\Longrightarrow} \begin{bmatrix} s_{1}^{(l + 1)}\\ \vdots\\ s_{k}^{(l + 1)}\\ \vdots\\ \end{bmatrix} \Longrightarrow \cdots \Longrightarrow e_n$$
  我们来解释一下这个流程：$s_j^{(l)}$是第$l$层第$j$个神经元的输入，输入经过双曲函数得到第$l$层第$j$个神经元的输出$x_j^{(l)}$，这一层的全部神经元的输出结果下一层的权重$w_{jk}^{(l + 1)}$，得到了下一层的各个神经元的输入，于是循环往复最后到达最后一层（输出层），它只有一个神经元，通过它的输出我们计算得到$e_n$。
通过这些连锁的关系我们可以计算：
$$\begin{split} \delta_j^{(l)} &= \frac {\partial{e_n}} {\partial{s_j^{(l)}}} \\ &= \sum_{k = 1}^{d^{(l + 1)}} \frac {\partial{e_n}} {\partial{s_k^{(l + 1)}}} \frac {\partial{s_k^{(l + 1)}}} {\partial{x_{j}^{(l)}}} \frac {\partial{x_{j}^{(l)}}} {\partial{s_{j}^{(l)}}} \\ &= \sum_{k} \left( \delta_{k}^{(l + 1)} \right) \left( w_{jk}^{(l + 1)}\right) \left( \tanh' \left( s_j^{(l)}\right)\right) \end{split}$$
从上式我们可以看出：由于$\delta_j^{(l)}$可以由$\delta_{k}^{(l + 1)}$表示，也就是说，$\delta$可以从后向前计算得到。
  综上，我们可以得到从后往前计算的方法（BP）算法：

初始化权重，for t = 0,1,...,T
1.stochastic：在$n \in \{ 1,2,...,N\}$随机选取一个点
2.向前计算出所有的$x_i^{(l)}$
3.向后计算出所有的$\delta_j^{(l)}$
4.更新梯度：$w_{ij}^{(l)} \leftarrow w_{ij}^{(l)} - \eta x_i^{(l - 1)} \delta_j^{(l)}$
return $g_{\text{NNET}}(X) = \\ \left( \cdots \tanh \left( \sum_j w_{jk}^{(2)} \cdot \tanh \left( \sum_i w_{ij}^{(1)} x_i \right)\right)\right)$

  实际使用算法的时候我们可能选取的既不是SGD也不是GD而是针对第一到第三步选取许多点来做，再一起更新，称为mini-banch，这样效果会比较好。
  以上就是基本的神经网络算法，其通过反向来计算梯度再更新的方式对权重做最佳化。

4.Optimization and Regularization

  神经网络的Error Function：

$$E_{in}(W) = \\ \frac{1}{N} \sum_{n = 1}^{N} \text{err} \left(\left( \cdots \tanh \left( \sum_j w_{jk}^{(2)} \cdot \tanh \left( \sum_i w_{ij}^{(1)} x_i \right)\right)\right), y_n \right)$$
这个$E_{in}$常常是非凸的，于是带来一些问题，如不易得到全局最优解，例如用GD/SGD来做BP算法常常陷入局部最优解，而我们从不同的起始权重也会得到不同的局部最优解。
  那我们应该如何选取起始点呢？如果我们选取比较大的权重，我们可能很容易卡在一些梯度只能下降有限的平面上，于是我们在训练神经网络的时候，随机的选取一些比较小的起始权重是更加有帮助的。
  我们来看看神经网络的复杂度，如果用$\tanh$函数来做转换的话，模型的VC维度有这样的关系：
$$d_{VC} = O(VD)$$
其中，$V$和$D$分别是神经元的数量以及权重的数量，于是神经网络的优点就是如果我们使用足够多的神经元（$V$足够大），我们的模型会非常powerful，因此也带来一些问题，例如会Overfit。
  为了对抗Overfit，我们会使用Regularization。例如使用L2 regularizer。但是L2 regularizer对权重的影响是等比例缩小的效果，这和我们希望的不一样，通常我们会使用放缩之后的L2 regularizer：
$$\sum \frac{\left( w_{ij}^{(l)} \right)^2}{1 + \left( w_{ij}^{(l)} \right)^2}$$
这样能规避L2 regularizer的缺点，达到我们要让权重比较稀疏的目的。
  除了使用Regularization的方法，还有一种Early Stopping的方法也很常用。这个方法的意义在于，我们如果让模型最佳化的时间越多，有效的$d_{VC}$就越大，就如同我们越放任模型的power，结果是越有可能Overfit。于是，我们在做最佳化的时候，我们倾向于让这个时间合适不需要太长，这样能有效的降低Overfit出现的可能性。而如何去掌握这个最佳化停下来的时机呢？一般我们会用validation。

---

Lecture 13: Deep Learning

1.Deep Neural Network

  之前我们讲到Neural Network，那么对于Neural Network的结构我们该如何来决定呢？而决定Neural Network的结构就是深度学习的一个核心问题。
  我们先来对比一下浅层神经网络和深层神经网络：

$$\begin{matrix}{} Shallow & Deep \\ 效率高&难以训练\\易于排布&难以排布\\理论上powerful&非常powerful\\ \end{matrix}$$
  近年来，DNN（Deep Neural Network）非常火热，特别是在图像识别和NLP等领域，其特点在于DNN能有效萃取图片或者声波等信息的特征。
  那么DNN是如何提取特征的呢？我们用手写数字识别来举例，从图中我们可以看出，第一层网络对数字中是否含有一些细小笔画的精细特征进行了识别分类，而第二层通过对第一层的结果乘上各自权重进行综合，从而做出决定。
  从这里我们可以看出DNN的一些特点：

1.每一层承担简单任务，从后向前逐渐变得复杂
2.擅长求解对拥有原始特征的困难问题

  深度学习拥有很多应用之处，也有许多的困难和challenge，例如：

• 难以决定架构
• 模型复杂度很高
• 难以最优化
• 计算复杂度很高

  那现在研究者主要用那些方法应对以上这些困难呢？

• 难以决定架构：具体问题具体调整，如卷积神经网络
• 模型复杂度很高：大数据领域这不是问题，而且可以使用regularization
• 难以最优化: 谨慎选取起始点，做pre-training
• 计算复杂度很高: GPU并行计算使得计算更加快捷

  我们现在简要介绍如何做深度学习，第一步当然是决定权重的初始值了，那么怎么决定呢？一个比较可能的想法是一层一层来决定，而且是先决定第一层， 继而决定第二层，每次一层，直到完成所有层的初始化（pre-training）。

2.Autoencoder

  如何做pre-training呢？也即是：如何决定pre-training的weight呢？我们回头想一想weight的物理意义我们可以发现，实际上，weight就代表了把上一层的输出的信息做一个转换，亦或者说做一个编码，然后传输给下一层。如果我们能够让下一层接收到编码之后的信息所代表的信息是和上一层是基本一样的话，我们认为这就是好的weight，也就是完成了information-preserving encoding的过程，也就是编码之后准确的解码的过程。
  那么如何搭建Information-Preserving Neural Network呢？我们可以试着构建一个这样的网络：它的第一层将输入编码到第二层，第二层又将输出解码到第三层，而第三层的输出与第一层的输入类似，我们把这种网络叫做autoencoder：

$$d- \tilde{d}-d \ \text{NNet with goal} \ g_i(x) \approx X_i$$
  autoencoder学习的结果就是在逼近一个identity function，也就是$g(x) = x$，而$W_{ij}^{(1)}$和$W_{ij}^{(1)}$分别称为encoding weights和decoding weights。
  autoencoder逼近identity function的作用是什么？
通过观察Approximating Identity Function的表现：

• 对于监督学习来说：可以通过编码的过程得到输入的一些隐藏的结构，从而将它们用于特征转换。
• 对于非监督学习来说：既可以对资料的密度做一个对应；从也可以用来探测离群点。

  我们通过Approximating Identity Function，得到了中间的这一层，我们可以得到资料的表现方式，继而作进一步的处理。

  那么对于基本的autoencoder，我们如何得到呢？其实autoencoder是一个很简单的浅层的神经网络，而且它的输出等于输入，用BP算法比较容易训练，而且从后层向前我们会做一个压缩的动作，也就是逐渐减少前面层神经元的数目。 通常我们会将$W_{ij}^{(1)} = W_{ij}^{(1)}$作为regularization。这也就是我们所讲的pre-training的一个基本的思想。
  综上，用autoencoder来做DL的基本过程就是：

1.从第一层开始，用autoencoder逐层训练直到最后一层，完成pre-training。
2.BP算法微调完毕所有的$\{ W_{ij}^{(l)} \}$。

  大多数目前的pre-training的方法都是以以上的过程作为基础的。

3.Denoising Autoencoder

  因为DL结构如此复杂，所以regularization是必须的，我们所讲的：

1. 结构化的约束
2. 用weight decay or weight elimination来做regularizers
3. 在合适的时机停止学习：early stopping

这些方法实际中都是有用的。
  这里我们引入引入一种在DL中很有用的regularization方法。将这个之前我们先来复习一下overfitting的原因，我们知道，以下的原因都可能导致overfitting：

1. 数据量过少
2. noise过大
3. 模型太复杂太powerful

  其中noise也是一个我们必须着力解决的问题，通常来讲我们会对数据做处理以削弱数据中的噪声，如data cleaning/pruning都是通常会使用的手段。
  这里我们讲一个新思路：如果我们在autoencoder的输入里面人为加入噪声，再让autoencoder学习带有noise的data，这样是不是能让autoencoder学习到处理带有noise的数据的能力呢？！答案是肯定的。这就是DL中一个非常强力的做regularization的方法，途径是在数据里面人为的加入noise，这样反而能让NNet在未来的预测之中拥有处理noise的能力，从而表现更好。

4.Principal Component Analysis

  由于模型中存在双曲函数$\tanh(W^TX)$， 所以我们之前讲的autoencoder实际上是非线性模型。
  那么线性的autoencoder是怎么样的结构呢？其实我们先看看非线性autoencoder的hypothesis：

$$h_k(X) = \sum_{j = 0}^{\tilde{d}} W_{jk}^{(2)} \tanh \left(\sum_{i = 0}^d W_{ij}^{(1)} X_i \right)$$

  其中我们做一点变化：

1.为简便丢掉$x_o$
2.加入约束项$W_{ij}^{(1)} = W_{ij}^{(2)} = W_{ij}$作为regularization
3.为防止产生意义不大的解，假设输出的维度小于输入的维度$\tilde(d) \lt d$

  这样linear autoencoder的hypothesis：

$$h_k(X) = \sum_{j = 0}^{\tilde{d}} W_{kj} \left(\sum_{i = 1}^d W_{ij} X_i \right)$$

实际上就是矩阵形式：

$$h(X) = WW^TX$$
对其做最优化，error function：
$$E_{in}(h) = E_{in}(W) = \frac{1}{N} \sum_{n = 1}^N \Vert{X_n - WW^TX_n}\Vert^2$$

这是一个四次多项式，不易优化，继续推导，对$WW^T$做特征分解：

$$WW^T = V \Gamma V^T$$
其中$Ｖ$是正交矩阵，$\Gamma$是rank小于$\tilde{d}$的对角矩阵。
  于是有：
$$WW^TX_n = V \Gamma V^T X_n$$
其中：
$$V^T (X_n)$$ 即是对输入矩阵做坐标旋转或者镜射， 上式的结果再乘以$\Gamma$则是将上式得到的矩阵中，超出$d - \tilde{d}$的维度的元素全部置零，并把其余元素做一个放缩，接下来矩阵再乘以$V$，物理意义是将此矩阵做旋转或者镜射的反动作。
  按照这个思路，我们对输入矩阵$X_n$做同样的变换：
$$X_n = V I V^T X_n$$
这样的动作对于$X_n$没有变化。
这样我们成功地把$W$的最佳化问题转化为了$V$和$\Gamma$的最佳化问题，即：
$$\mathop{\min}\limits_{V} \mathop{\min}\limits_{\Gamma} \sum_{n = 1}^N \lVert V I V^T X_n - V \Gamma V^T X_n \rVert^2$$
先对固定$V$对$\Gamma$做最佳化，易得当
$$\Gamma = \begin{bmatrix} I_{\tilde{d}} & 0 \\ 0 & 0 \\ \end{bmatrix}$$
时，也即是$\Gamma$最接近单位矩阵时，就是$\Gamma$的最佳解。
  于是固定$\Gamma$对$V$做最佳化：
$$\mathop{\min}\limits_{V} \sum_{n = 1}^N \lVert \begin{bmatrix} 0 & 0 \\ 0 & I_{d - \tilde{d}}\\ \end{bmatrix}V^T X_n \rVert^2$$
继续转化，为让问题直观，将最小化问题转化为最大化问题：
$$\mathop{\min}\limits_{V} \sum_{n = 1}^N \lVert \begin{bmatrix} 0 & 0 \\ 0 & I_{d - \tilde{d}}\\ \end{bmatrix}V^T X_n \rVert^2 \equiv \mathop{\max}\limits_{V} \sum_{n = 1}^N \lVert \begin{bmatrix} I_{\tilde{d}} & 0 \\ 0 & 0 \\ \end{bmatrix}V^T X_n \rVert^2$$
  直观来讲，即是把让留下的部分最大化，转化成了去掉最多的部分的过程。
  接下来，从简单开始，我们先来看$\tilde{d} = 1$的时候的情况此时，$V^T$只有第一行$v$起作用：

$$\mathop{\max}\limits_{v} \sum_{n = 1}^Nv^Tx_nx_n^Tv \\ s.t. v^Tv = 1$$
之前我们在拉格朗日乘子的计算推导中有如下规律，二次优化问题的微分和约束条件的微分平行：
$$\sum_{n = 1}^Nx_nx_n^Tv = \lambda v$$
也就是最优化的$v$是$X^TX$的特征向量，而且是最大的特征向量，因为我们求解的是最大化的最优化问题。
  那么$\tilde{d}$是通常情况也就是大于一的时候呢？类似上面的情况，也是找到$X^TX$最大的特征向量，只不过是数量会更多：
$$\{v_j\}_{j = 1}^{\tilde{d}}$$
既然得到了$v$， 那么：
$$optimal \ \{ w_j \} = \{ v_j \ with \ \gamma_j = 1 \}$$
  综上，linear autoencoder的过程就是，把资料矩阵的特征向量求出，把其中最符合原来资料的特征向量的方向，就是我们应该投影，也就是做特征转换的方向。
linear autoencoder的算法：

1. 从$X^TX$计算top eigenvectors
2. 返回特征转换 $\Phi(x) = W(x)$

  linear autoencoder要最大化的是资料投影到$W$上的信号强度的平方最大，在统计上有个类似的概念叫做PCA，不过它做的最大化是资料投影到$W$上的信号强度变化率，算法类似autoencoder：

1. $x_n \leftarrow x_n - \overline{x} (去均值化)$
2. 从$X^TX$计算top eigenvectors
3. 返回特征转换 $\Phi(x) = W(x - \overline{x})$

  与autoencoder相比，PCA只是多了一个去均值的动作，这样得到的自然是变化率了。
PCA和linear autoencoder在实际中主要用于线性降维，比如将一个10000维度的资料降维成400维以便学习，也是属于预处理的范畴。

---

Lecture 14: Radial Basis Function Network

1.RBF Network Hypothesis

  我们介绍RBF（Radial Basis Function） Network，它属于Neural Network的一个分支。之前我们讲过的Gaussian kernel实际上就是RBF kernel：

$$g_{SVM} (x) = sign \left( \sum_{SV} \alpha_n y_n \exp(- \gamma \Vert x - x_n\Vert^2) + b\right)$$
  从另一个角度看待Gaussian SVM输出的函数，若定义：
$$g_{n} (x) = y_n \exp(- \gamma \Vert x - x_n\Vert^2)$$
则：
$$g_{n} (x) = sign \left( \sum_{SV} \alpha_n g_{n} (x) + b\right)$$
这代表我们用$g_{n} (x)$做线性组合，而每一个$g_{n} (x)$都是一个radial hypothesis（关注与中心点的半径距离的函数）。把这个概念延伸，也就是今天我们要讲的Radial Basis Function Network。RBF Network和Neural Network的输出层都是一个线性模型， 不同于Neural Network的第一层的算权重再通过s型函数， RBF Network的第一层做的是算出与中心点的距离再通过高斯等函数的转化。
  综合以上多层我们可以得到RBF Network Hypothesis：
$$h (x) = \text{Output} \left( \sum_{m = 1}^{M} \beta_m \text{RBF} (x,\mu_m) + b\right)$$
其中：

$\ \ \ \mu$：中心点，相当于Gaussian-SVM中的各个SV$x_n$
$\beta_m$：投票权重，相当于SVM对偶问题中的$\alpha_my_m$

  从而RBF Network要学习的过程就是给定RBF和要求的输出， 通过学习决定$\mu$和$\beta_m$。
  以前我们讲过kernel实际上相当于在Z空间计算两个向量的相似性，而RBF就相当于在X空间计算两个向量的距离的相似性。而RBF Network就是用这个对中心距离的相似程度来定义特征转换。

2.RBF Network Learning

  如何求解RBF Network呢？也就是如何求解$\mu$和$\beta_m$?首先我们考虑比较简单的想法：如将所有的点都当做中心，而$\beta_m$在物理意义上就相当于这些中心点对周边的相似的点的影响。我们考虑一个更简单的情况，假设：
$\beta_m = 1 \cdot y_m$
这样

$$g_{\text{uniform}} (x) = sign \left( \sum_{m = 1}^{N} y_m \exp(- \gamma \Vert x - x_n\Vert^2) \right)$$
这样代表我们每个看过的样本点都可以对我们新看到的点做投票，这种网络叫做full RBF Network。
  full RBF Network的方法和机器学习中的Nearest Neighbor方法有相关之处，之前我们说的 $$g_{\text{uniform}} (x) = sign \left( \sum_{m = 1}^{N} y_m \exp(- \gamma \Vert x - x_n\Vert^2) \right)$$
其中的 $$\exp(- \gamma \Vert x - x_n\Vert^2)$$
这个高斯函数随着两个向量的距离变大而衰减的很快，之前我们对每一个点的得分都进行累加，实际上最近的点对高斯函数的值有决定性的影响，于是我们可以转而求取最近的点也就是是高斯函数最大的点而不是求累加和，从而用这个点的$y_m$而不是所有的$y_m$，这是一个用selection 代替aggregation的想法。这样算法变为：
$$g_{\text{nbor}}(x) = y_m \ \text{such that} x \text{closest to} \ x_m$$
把这个方法引申到用采取多个邻近点的意见，就成为了k近邻法。
  我们再来看看使用full RBF Network的好处。如果我们用full RBF Network做squared error regression，即把得分直接作为输出，那么我们实际上在对RBF转换过的数据做线性回归：
$$z_n = [\text{RBF}(x_n, x_1),\text{RBF}(x_n, x_2),...,\text{RBF}(x_n, x_N)]$$
根据我们以前学过的知识，其最优解：
$$\beta = (Z^TZ)^{-1}Z^Ty$$
而由$z_n$构成的$Z$是一个N维对称方阵，且可以证明当$X_n$都是不同的时候，$Z$是可逆的，从而得到：
$$\beta = Z^{-1}y$$
  既然得到了$\beta$，可以得到：
$$g_{\text{RBF}}(x_n) = y_n$$
从而RBF的$E_{in} = 0$！从以前我们学过的知识来看，这一点并不好，因为可能会overfitting。一个改良方法是加入regularization，如：
$$\beta = (Z^TZ + \lambda I)^{-1}Z^Ty$$
我们将此式称为regularized full RBFNet，联系我们之前学过的kernel ridge regression：
$$\beta = (K + \lambda I)^{-1}y$$
样子很相近，但是kernel是在z空间无线多维的转换做regularization，RBF则是在原始空间有限多维的转换做regularization。
  如果我们坚持所有资料都当做中心，我们很可能会overfitting，容易了联想到，之前我们做SVM的时候，我们并没有使用全部的样本点而是只使用SV，那我们是不是也可以使用比较少的center的数量呢？答案是肯定的，而且这样做，减少了center的数量，同时第二层的权重变少了，其实相当于在做regularization，而减少了center，在物理意义上，相当于在样本点中选取了更加具有代表性的样本点。

3.k-Means Algorithm

  如好找到好的代表点呢？可以考虑，如果两个样本点非常接近，或许我们不需要两个点同时在RBFNet里起作用，也就是这两个点可以选取同一个代表就可以。进一步讲， 我们把资料分成若干个群，在每一个群里产生一个代表点就可以了。那么怎么解决分群问题呢？这在机器学习里面就是一个典型的非监督而学习的过程，定义$E_{in}$：

$$E_{in}(S_1,...,S_M;\mu_1,...,\mu_M) = \frac{1}{N} \sum_{n=1}^{N}\sum_{m=1}^{M}[\![x_n \in S_m]\!]\Vert x_n - \mu_m\Vert^2$$
分群学习的目标当然就是：
$$\mathop{\min}\limits_{\{S_1,...,S_M;\mu_1,...,\mu_M\}}E_{in}(S_1,...,S_M;\mu_1,...,\mu_M)$$
也就是：
$$\mathop{\min}\limits_{\{S_1,...,S_M;\mu_1,...,\mu_M\}}\sum_{n=1}^{N}\sum_{m=1}^{M}[\![x_n \in S_m]\!]\Vert x_n - \mu_m\Vert^2$$
这是一个很难优化的组合问题，因为既有求出代表点又有分群的动作。于是我们自然想到对它们分别进行最佳化，首先固定中心点，那么每个点加入那个群取决于：
$$\mathop{\min}\Vert x_n - \mu_m\Vert^2$$
那么既然已经决定如何分群，对于中心点我们可以再做最佳化，这是一个无约束问题：
$$\begin{split} \nabla E_{in} &= -2 \sum_{n=1}^{N}[\![x_n \in S_m]\!]\Vert x_n - \mu_m\Vert^2 &= -2 \left(\left( \sum_{x_n \in S_m} x_n \right) - \vert S_m\vert \mu_m\right) \end{split}$$
于是得到最佳的$\mu_m$就是$S_m$中$X_n$的平均，也就是固定了$S_m$，一步一步就可求得\mu_m$。
而这就是很有名的的k-Means算法：

1.随机选取$k$个点当做起始点
2.对$E_{in}$做最佳化：

1.最佳化$S_k$：把每个点归类到最接近的中心
2.最佳化$\mu_k$：在每个群里重新决定中心点
...直到收敛

  那么我们如何确定这个算法一定会收敛呢？其实是可以保证的：因为算法的每个循环都在让$E_{in}$最小，而$E_{in}$的下限就是$0$，于是算法一定会收敛，一定会停下来。
  有了k-Means算法的概念，我们把它用于RBF Network里面就很自然而然了：

1.用k-Means算法得到$\{\mu_m\}$，其中$K = M$
2.构建特征转换：

$$\Phi(x) = [\text{RBF}(x_n, x_1),\text{RBF}(x_n, x_2),...,\text{RBF}(x_n, x_M)]$$
3.把$\{(\Phi(x), y_n)\}$用线性模型得到$\beta$

这也是一种非监督学习的方法帮助得到特征转换的应用，如同我们之前讲过的autoencoder。在实际应用中我们通常用validation来调节$M$（代表点的个数）和$\gamma$（高斯函数）参数。

4.k-Means and RBF Network in Action

  从k-Means算法的实际表现来看，通常我们对于$k$的数量选取合适的话，通常能得到较好的分群结果，而若$k$的数量选取不合适亦或者初始点选的不好，可能对结果有较大的影响。从实际应用中我们也可以看到如果k-Means得到的中心点比较合理的话，接下来用于RBF Network里面的分类也会做的更加好。
  从算法表现上我们也可以看到，Full RBF Network和nearest neighbor算法都做得不错，但是实际应用中它们都因为计算复杂度而很少被使用。

---

Lecture 15: Matrix Factorization

1.Linear Network Hypothesis

  如果机器拿到的资料是抽象的特征，该如何学习呢？比如由Netflix在2006年举办的大赛里面涉及的数据，这些数据包含许多观众对于很多电影的评分，但是除此之外只包含对于观众本身的一些
数据，也就是只有abstract feature，那么又该如何学习呢？
  首先我们来进一步看一看抽象的特征，比如一个观众的数据包含的大都是分类的特征，比如ID、血型等。而我们之前见讲过的许多模型都是善于处理数值特征的，如线性模型或者扩展的线性模型如NNet等。目前我们讲过的模型里面只有决策树可以处理分类的特征。
  容易想到，如果要让资料易于学习，那么第一步我们可能要做的就是将分类特征转换为数值特征（encoding）。如何转换呢？通常我们用$0/1$来表示二元向量编码：

$$A = [1 \ 0\ \ 0\ 0]^T \\ B = [0 \ 1\ \ 0\ 0]^T\\ \cdots$$
  用这种编码地概念，我们可以将电影资料库这样表示：
$$\{(x_n = BinaryVectorEncoding(n),y_n = r_{nm}):代表用户n对电影m打分\}$$
或者：
$$\{(x_n = BinaryVectorEncoding(n),y_n = [r_{n1}\ ? \ ?\ r_{n4} \ r_{n5} \ ... \ r_{nM}]^T):代表用户n对许多电影的打分\}$$
  接下来我们可以试着用$N-\tilde{d}-M$的NNet来做特征的萃取。由于$x$是稀疏的，所以中间的双曲函数变化不是必要的，所以在中间层用线性函数，于是NNet变为‘Linear Network’，将第一层和第二层的权重矩阵分别命名为$V^T$和$W$，于是：
$$h(x) = W V^T x \\ h(x_n) = W^TV_n$$
  于是我们用Linear Network来做推荐系统，目标就是学习到$W$和$V$。

2.Basic Matrix Factorization

  接着上面，式中的$Vx$我们把它命名为$\Phi(x)$，它代表了特征转换函数，而对于某一部特别的电影，我们可以得到线性模型：

$$h_m(x) = w_m^T \Phi(x)$$
  最后我们想看到的是：
$$r_{nm} = y_n \approx w_m^T v_n$$
也就是，我们学习到的模型对于用户对电影的评分预测要与用户真实评分接近。
  定义Error Function：
$$E_{in}(\{w_m\}, \{v_n\}) = \frac{1}{\sum_{m = 1}^M \vert \mathcal{D_m}\vert} \sum_{\text{user n rated movie m}}\left( r_{nm} - w_m^T v_n \right)^2$$
  用户和电影评分的表格关系可以用矩阵来描述：
$$r_{nm} = y_n \approx w_m^T v_n \Leftrightarrow R \approx V^TW$$
而我们做的学习就是相当于把现有的评分矩阵拆分成用户的矩阵和电影的矩阵，它们分别描述了用户的特征和电影的特征。
$$\begin{split} \mathop{\min}\limits_{W,V}E_{in}(\{w_m\}, \{v_n\}) &\propto \sum_{\text{user n rated movie m}}\left( r_{nm} - w_m^T v_n \right)^2\\ &= \sum_{m = 1}^{M} \left( \sum_{(x_n, r_{nm}) \in \mathcal{D_m} }\left( r_{nm} - w_m^T v_n \right)^2\right) \end{split}$$
  这个最优化问题也是具有两个变量，老方法固定一个优化另一个：例如固定$v_n$最小化$w_m$，这样的话，内层就转化成了对于每部电影的做线性回归；而固定$w_m$的话，求$v_n$的最佳解的话，我们观察可以看到，其实$w_m$和$v_n$是一个对称的关系，若把$E_{in}$的矩阵做一个转置，则内层转化为了每位用户的线性回归。
  这个算法因此叫做叫做alternating least squares algorithm：

1.初始化$\{w_m\}$$\{v_n\}$

2.对$E_{in}$交互的做最佳化：重复

1.最优化$w_m$:在$\{(v_n, r_{nm})\}$的第m部电影做线性回归
2.最优化$v_n$:在$\{( w_m, r_{nm})\}$的第n位用户做线性回归
...直到收敛
  我们要注意初始化值是随机选取的，而和上一讲一样，$E_{in}$的bound保证了算法最终的收敛。

  Linear Autoencoder和Matrix Factorization对比的话，我们可以发现许多相似之处：

对比	Linear Autoencoder	Matrix Factorization
形式	$X \approx W(W^TX)$	$R \approx V^TW$
构成	$d-\tilde{d}-d$	$N-\tilde{d}-M$
错误函数	所有的$x_{ni}$的均方误差	已知的$r_{nm}$的均方误差
解决方法	$X^TX$整体的最佳解	交互矩阵的局部最佳解
作用	特征的降维	提取隐藏特征

3.Stochastic Gradient Descent

  Stochastic Gradient Descent也可以被用于前面问题的求解。SGD也就是每次选取 一笔资料，在这笔资料上用梯度下降做最优化。它的好处是，每一次的最优化很有效率，容易实现，而且容易延伸到其他的错误衡量方式。
  那我们如何用SGD求解我们Matrix Factorization呢？首先定义Error Function：
$\text{err}(n, m, r_{nm}) = (r_{nm} - w_m^T v_n)^2$
也就是用平方错误来衡量预测与真实值之间的误差。
  分别用Error Function对$v_n$和$w_m$做偏微分：

$$\nabla_{v_n}\text{err}(n, m, r_{nm}) = - 2(r_{nm} - w_m^T v_n)w_m\\ \nabla_{w_m}\text{err}(n, m, r_{nm}) = - 2(r_{nm} - w_m^T v_n)v_n$$
从上式我们可以观察到：每笔资料的梯度就相当于余数乘以另外一个特征向量。
SGD for Matrix Factorization：

随机选取特征向量：初始化$\{w_m\}$$\{v_n\}$

for t = 0,1,...,T

1.随机选取某个点$(n, m)$
2.计算余数$\tilde{r}_{nm} = (r_{nm} - w_m^T v_n)$
3.更新SGD：
$v_n^{new} \leftarrow v_n^{old} + \eta \cdot \tilde{r}_{nm} w_{m}^{old}$
$w_n^{new} \leftarrow w_n^{old} + \eta \cdot \tilde{r}_{nm}$

  SGD因为计算方便，是最常用的大型矩阵分解的中的方法。

4.Summary of Extraction Models

  到这里我们对我们这几讲所提到的这些模型做一个定义：Extraction Models，为什么叫做Extraction Models呢？因为这些模型用特征转换表示了从资料里面学习到的隐藏的可能性，它们是线性模型的延伸。

例如Neural Network/Deep Learning：前面的几层在做特征转换， 最后一层是线性模型，我们所做的是同时做成了隐藏的变数的转换和线性模型。

在RBF Network里呢：
隐藏的变数就是RBF的中心点，后面也是用权重做线性模型。

在Matrix Factorization里：
使用者的特征和电影的特征都承担了这两个角色，因为它们是对称的。

在Adaptive/Gradient Boosting：
它找出的特征转换就是许多的$g_t$，再做线性模型。

在k Nearest Neighbor里：
每一个看过的点的附近的邻居的范围当做特征转换，再结合权重（每一个点作投票，就是原本点的label）。

这些模型蕴含各自从资料里面萃取（Extraction）出特征的技巧.

在Adaptive/Gradient Boosting：用函数的梯度下降来萃取$g_t$， 还有autoencoder得到初步的特征转换。

在Neural Network/Deep Learning里：用SGD（BP）计算梯度的值

在RBF Network里呢：我们使用的是k-means clustering，这里我们可以看出非监督式学习对于学习资料的表现方式上是很有效的。

在Matrix Factorization里面：
用基本的SGD或者看成交互的线性回归的话，还可以用alternating leastSQR来解决。

而k Nearest Neighbor：
通常被称为lazy learning，因为在学习上不花功夫，在测试的时候做一些推论的动作。

  这些Extraction Models都有哪些优缺点呢？

Pros	Cons
电脑自动完成特征转换：减少了人类的负担	这些最佳化问题通常是非凸的：可能伴随各种问题
如果隐藏变量足够多，模型非常强力	模型复杂带来Overfitting：需要regularization或者validation

---

Lecture 16: Finale

1.Feature Exploitation Techniques

  我们来讲Exploiting Numerous Features的技术，首先是Kernel，利用Kernel我们可以把一些数值特征非常多的特征转换$\Phi$以及内积转化到Kernel里。

段落引用
1. Polynomial Kernel：放缩的多项式转换
2. Gaussian Kernel：无限多维的转换
3. 作业里提到的Stump Kernel：把许多decision-stumps作为转换
4. Sum of Kernels：Kernel相加，代表把不同的转换混合起来
5. Product of Kernels：Kernel相乘，代表把两个Kernel里面埋藏的特征转换组合形成一个新的复杂的转换
6. Mercer Kernels：Kernel需要符合的条件是Mercer's Condition，我们可以说任何符合这个条件的函数里面都埋藏了一些特征转换

  继而Kernel可以搭配各种模型，如SVM、SVR、 probabilistic SVM、kernel ridge regression、kernel logistic regression等，使得原来的模型能做非常广泛的延伸。而我们之后讲的PCA,k-Means等里面有线性或者内积运算的模型都可以加上Kernel形成新的版本。

  我们运用特征转换的第二种方法是Aggregation：也就是用许多的$\Phi$也就是许多的$g_t$来预测特征。其中Decision Stump可以看成是最简单的perceptron，也可以看成是最简单的simplest DecTree。而复杂的Decision Tree可以看成是把资料切分再组合。(Gaussian) RBF通过许多个代表$g_t$也就是每个中心点以及中心点的影响力来预测某些点。
  上面讲的这三者都是我们可以用来组合的单独的$g_t$，运用这些许多$g_t$，我们可以用它们来投票再平均， 或者把它们做线性组合、有条件的组合亦或者是非线性组合。
  除了上面的方法我们还可以用其他的方法得到$g_t$：
如Bagging来得到许多$g_t$，再组合起来，如果再配合Decision Tree就会形成Random Forest。如果是一步一步找出$g_t$，我们可以用AdaBoost或者GradientBoost。而DecisionTree本身就是找出不一样的$g_t$的方法，之前讲过的Nearest Neighbor中的投票也是一种把$g_t$的预测合起来的方法。而probabilisticSVM中的微调也是类似Aggregation的方法。机器学习许多不同的模型都是有互相关联的地方的。
  我们要讲的第三个面向特征方向就是把一些潜藏的特征找出来，而这个潜藏的特征也是要做最佳化的变数，我们可以把这些潜藏的特征和权重，一起做最佳化，这里面常用到非监督式学习的方法。
  例如Neural Network;Deep Learning neuron weights代表了我们要做的特征转换；或者RBF Network中的RBF centers也代表了特征转换；或者Matrix Factorization中的user/movie factors也是特征转换。
  使用的非监督学习方法有：
在RBF里是k-Means方法，来找到群的中心；在矩阵分解里面，我们常用Autoencoder或者PCA，它们所萃取出的是投影过去的最好的方向；而我们在AdaBoost和GradientBoost所要找出的一步一步$g_t$，也是在萃取参数。
  这些方法也是可能有机会融合起来使用的，比如在Neural Network里面使用GradientBoost找出神经元，亦或者在萃取出来的特征用于神经网络做最佳化。

  第四个和特征转换相关的方面就是降维，也就是原有维度的压缩。例如Decision Stump或者DecTree Branching，我们可以把它的分支看出都是在对低维度做投影；而在Random Forest或者Tree Branching里面通常是先做投影，再在上面切stump；在Autoencoder或者PCA里面也是想对低维度做投影，并且保持资料含有的信息；在Matrix Factorization中，我们做的也是想把一个非常高维度的向量投影到一个低维度的具体的向量上面。
  而之前在随机森林里面讲的特征选择Feature Selection也是一种降维的方式，而很多其他的降维方式也可能被运用。

2.Error Optimization Techniques

  现在我们讲数值优化方法，我们第一常用的就是梯度下降法，每次梯度下降都是相当于错误函数的一次逼近：

$$\text{new} = \text{old} - \eta \nabla E$$
其中常用的有SGD/Minibatch/GD：

1. 如(Kernel) LogReg
2. Neural Network（配合[backprop]）
3. Matrix Factorization以及Linear SVM(本节课没有讲，实际上SGD常用)。

  而在AdaBoost或者GradientBoost我们用的是Functional GD，也就是我们下降的是函数而不是方向，而且Steepest Descent，也就是每一步下降的很多。梯度下降法也会配合二次逼近或者加上约束来操作。
  当我们遇到一些困难的原始问题，我们通常经过数学推导或者加上我们对这个问题了解的知识来让这个问题做一些变形，如：

1. Dual SVM，通过凸二次规划来转化Kernel LogReg或Kernel RidgeReg，通过representer理论来转化
2. PCA：转化为eigenproblem来解决
   其中线性代数，或者最佳化理论都有涉及。

  其他的一些boosting模型或者Kernel模型的解法里面都有用到这种转化的思想和技术。

还有那些最佳化的方法呢？ 比如我们遇到了难以解决的问题，有时候我们需要把这些困难的问题拆分成多层问题来求解。如：

Multi-Stage
probabilistic SVM;
linear blending;
stacking;
RBF Network;
DeepNet pre-training

或者我们对于有两组变数交织在一起的时候我们可以交互的做最佳化，如：

k-Means;
alternating LeastSqr;
(steepest descent)

或者我们可以把问题分而治之，如：

decision tree;

这些手段实际中都是常用到的。

3.Overfitting Elimination Techniques

在机器学习里面我们也常常需要通过Regularization来对付Overfitting Elimination，手段也有许多，如：

1. large-margin：SVM和AdaBoost (indirectly)
2. L2：SVR;kernel models;NNet [weight-decay]
3. voting/averaging(投票取平均)uniform
4. blending;Bagging;Random Forest
5. denoising：在autoencoder人工加入杂讯以对抗杂
6. pruning：在decision tree里面cutting trees，让模型复杂度减小
7. weight-elimination：在NNet里想办法让weight变小一点
8. early stopping：NNet (any GD-like)
9. constraining：
   autoencoder里的对权重的约束;
   RBF里面对于中心的约束;

  以上这些都是Regularization的方法，就是在设计模型的时候就减少参数的使用或者加上一些条件或限制，也就是相当于开车时踩刹车的动作。
  我们也可以通过Validation来对抗Overfitting，如
Random Forest里面的OOB（out of bag）方法，或者SVM/SVR里的SV就可以用来检查复杂度，有一些内部的操作里面也包含了Validation的动作：如blending或DecTree pruning。

4.Machine Learning in Practice

  KDDCup 2010使用的是线性融合模型，其中一个部分对原始资料做编码以后再做逻辑回归，另外一个部分随机森林里使用的是人为设计的特征。
  KDDCup 2011使用了有NNet、决策树以及线性融合模型，其中包括了：
矩阵分解、限制波兹曼机、k近邻以及Probabilistic Latent Semantic Analysis。
  KDDCup 2012使用了NNet, GBDT-like, 然后是线性融合模型，包括线性回归、逻辑回归等。
成功的秘诀是系统的做好blending的动作。
  KDDCup 2013使用了Random Forest, GBDT以及人为设计特征，而人类学习和机器学习做配合也是成功的一大秘诀。

ICDM 2006 Top 10 Data Mining Algorithms：

1. C4.5: 是决策树的一种
2. k-Means：学过
3. SVM：学过
4. Apriori: 数据挖掘方法，找出数据里面经常出现的部分
5. EM: 最佳化技巧里面的‘alternating
   optimization’ 用于几率模型的一个特例
6. PageRank: 谷歌的网页排名技术类似
   matrix factorization矩阵分解
7. AdaBoost 学过
8. k Nearest Neighbor 学过
9. Naive Bayes: 通过资料的统计特性来决定的线性模型
10. C&RT：学过，决策树

还有没有列上去但是足够重要也应该被列上去的的方法如：

• 线性回归
• 逻辑回归
• 随机森林
• Gradient Boosting Decision Tree
• NNet。

通过学习本课程我们希望从课程延伸到更广泛的地方，希望大家机器学习的丛林不会迷路。