2017年12月

《统计学习方法》读书笔记7:支持向量机

支持向量机是工业界很常用的分类算法(另一个是LR),目前比神经网络更为常用,面试中也经常考到。SVM的数学逻辑很完备,不像神经网络那样难以解释,分类也只依赖样本点(支持向量),所以非常鲁棒。但是,它的数学证明可能会稍稍复杂,需要好好做一下笔记了。

  1. 首先是最简单的一类支持向量机:线性可分支持向量机。给定线性可分的训练数据及,通过间隔最大化方法得到分离超平面
    $$
    \tilde w \cdot x + \tilde b = 0
    $$
    以及相应的分类决策函数
    $$
    f(x) = sign(\tilde x \cdot x + \tilde b)
    $$
    称为线性可分支持向量机。它的解是唯一的。
  2. 函数间隔与几何间隔。函数间隔的定义是
    $$
    \hat \gamma_i = y_i(w \cdot x_i + b)
    $$
    函数间隔定义了分类预测的正确性。
    几何间隔是将函数间隔做规范化
    $$
    \gamma_i = \frac{w}{||w||} \cdot x_i + \frac{b}{||w||}
    $$
    为什么要引入两种间隔呢?因为我们要找到的是一个超平面$ \tilde w \cdot x + \tilde b = 0 $,可是这一个超平面有无数种表示方法:只要对$ w $ 和 $ b $ 乘上一个因子 $ \lambda $,表示的还是同一个超平面。可是对于不同的$ w $和$ b $,它的函数间隔却不一样。那么直接使用几何间隔不就行了?为什么还要提函数间隔?因为可以将用几何间隔表述的问题转化为求函数间隔的问题,更加便于求解。
  3. 间隔最大化。间隔最大化的直观意义就是:不仅要用一个超平面分开样本点,还要让离超平面最近的点距超平面尽可能的远。这样的分割方式具有比较好的泛化能力。
    1. 最大间隔分离超平面。这个问题可以表述为
      $$
      \begin{align}
      & \max_{w, b} \gamma \newline
      & s.t.\quad y_i(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||}) \geqslant \gamma,\quad i=1,2,\cdots,N
      \end{align}
      $$
      直接求解这个问题比较困难,可以转换为关于函数间隔的表达式
      $$
      \begin{align}
      & \max_{w,b} \frac{\hat \gamma}{||w||} \newline
      & s.t. \quad y_i(w \cdot x_i + b) \geqslant \hat \gamma, \quad i=1,2,\dots,N
      \end{align}
      $$
      因为我们要求解的只是这个超平面,所以可以解出任意一个$\lambda w$与$\lambda b$。所以,直接另$ \hat \gamma = 1 $即可。于是就得到了下面的线性可分支持向量机学习的最优化问题
      $$
      \begin{align}
      & \min_{w, b} \frac{1}{2}||w||^2 \newline
      & s.t.\quad y_i(w \cdot x_i + b) - 1 \geqslant 0, \quad i=1,2,\dots,N
      \end{align}
      $$
      最终,问题变成了一个凸二次规划问题。
    2. 决定分离超平面时只有支持向量起作用,其他实例点并不起作用。
    3. 为了方便求解和后面引入核技巧,通常使用拉格朗日乘子法求解其对偶问题:
      $$
      \min_\alpha \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^n \alpha_i
      $$
  4. SVM的最优化问题可以等价成合页损失函数(hinge loss function)
    $$
    \min_{w,b} \sum_{i=1}^N [1-y_i(w \cdot x_i + b)]_+ = \xi_i
    $$
  5. 通过核技巧可以让SVM解决非线性分类问题。为了解决非线性分类问题,通常的做法是找一个非线性变换。但是,直接找出变换往往并不容易。核技巧的想法是,只用核函数来完成。核函数指的是
    $$
    K(x,z) = \phi(x) \cdot \phi(z)
    $$
    其中$\phi(x)$为变换,$K(x,z)$为核函数。可以结合SVM优化问题的对偶形式考虑为什么不需要知道$\phi(x)$只知道核函数就可以:因为对偶问题中只涉及到了内积,而核函数可以直接算出变换后的内积。
  6. 对偶问题中,使用了核技巧的目标函数变为:
    $$
    W(\alpha) = \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i
    $$
    同样,分类决策函数变为
    $$
    f(x) = \textrm{sign}(\sum_{i=1}^{N_s}a_i y_i K(x_i, x) + b)
    $$

拉格朗日对偶性

导言

拉格朗日对偶性尝尝用于带约束的最优化问题。这个原理的简化版本在高中数学中就出现过,当时称作拉格朗日乘数法。先回顾一下拉格朗日乘数法的基本形式:
$$
\min\limits_{x}f(x)=0\quad s.t.\quad g(x)=0
$$
找到$x$使得$f(x)$最小,且满足$g(x)=0$。我们引入拉格朗日乘子构造新的函数:
$$
L(x,\lambda) = f(x) + \lambda g(x)
$$
接着令两个偏导数为0
$$
\left\lbrace
\begin{align}
\frac{\partial L}{\partial x} &=0 \newline
\frac{\partial L}{\partial \lambda} &= 0
\end{align}
\right.
$$
求解出$x$和$\lambda$即可。
事实上,最后这一步求导然后另其等于0叫做KKT(Karush-Kuhn-Tucker)条件,当然完整的版本更加复杂一些。在本文中依然不会证明KKT条件,所以想要了解这样做的依据是什么的小伙伴们可能要失望了。不过接下来,我将展开说明更为普适的拉格朗日对偶性。

拉格朗日对偶性

原始问题

$$
\begin{align}
\min\limits_{x \in \textbf{R^n}} f(x) & \newline
s.t. c_i(x) & \leqslant 0, i=1,2,\ldots,k\newline
h_j(x) & =0, j=1,2,\ldots,l
\end{align}
$$

广义拉格朗日函数

$$
L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)
$$
$\alpha_i$和$\beta_j$是拉格朗日乘子,规定$\alpha_i \geqslant 0$(为什么会这样规定,下面会解释)。
构造一个函数
$$
\theta_P(x) = \max\limits_{\alpha,\beta:\alpha_i \geqslant 0}L(x,\alpha,\beta)
$$
下标$P$表示原始问题。
可以看出,如果$x$违反原始问题的某个约束条件,即存在某个$i$使得$c_i(w)>0$或者存在某个$j$使得$h_j(w) \neq 0$,那么就有
$$
\theta_P(x) = + \infty
$$
因为存在$c_i(x)>0$的话,可另对应的$\alpha_i \rightarrow +\infty$(这里就说明了为什么规定$\alpha_i \geqslant 0$,因为不作此规定的话,即使满足$c_i(x)<0$的条件,也可以取$\alpha_i \rightarrow -\infty$从而让整个$\theta_P = +\infty$);存在$h_j(x) \neq 0$的话,可令对应的$\beta_jh_j(x)->+\infty$,最后让其余所有$\alpha_i$,$\beta_j$取0。
如果满足所有约束,则$\theta_P(x)=f(x)$
所以有
$$
\theta_P(x)=
\begin{cases}
f(x), & x满足原始问题约束 \newline
+\infty, & 其他
\end{cases}
$$
与最初的原始问题等价的形式就是:
$$
\min\limits_x \theta_P(x) = \min\limits_x \max\limits_{\alpha, \beta: \alpha_i \geqslant 0}L(x, \alpha, \beta)
$$

$$
p^* = \min\limits_x\theta_P(x)
$$
称为原始问题的值。

对偶问题

定义
$$
\theta_D(\alpha, \beta) = \min\limits_xL(x, \alpha, \beta)
$$
定义对偶问题的最优值
$$
d^* = \max\limits_{\alpha, \beta: \alpha_i \geqslant 0} \theta_D(\alpha, \beta)
$$

原始问题与对偶问题的关系

$$
d^* \leqslant p^* $$

KKT条件

$$
\begin{align}
\nabla_xL(x, \alpha, \beta) & = 0 \newline
\nabla_\alpha L(x, \alpha, \beta) & = 0 \newline
\nabla_\alpha L(x, \alpha, \beta) & = 0 \newline
\alpha_i c_i(x) &= 0, i=1,2,\ldots,k \newline
c_i(x) & \leqslant 0, i=1,2,\ldots,k \newline
\alpha_i & \geqslant 0, i=1,2,\ldots,k \newline
h_j(x) &= 0, j=1,2,\ldots,l
\end{align}
$$

KKT条件给出了求解的方法。其中,上面第4条式子称为KKT的对偶互补条件。由此条件克制:若$\alpha_i$>0,则$c_i(x)=0$。

《统计学习方法》读书笔记6:logistic回归与最大熵模型

  1. logistic分布:X服从logistic分布是只X具有下面的分布函数与密度函数:
    $$
    F(x) = P(X \leqslant x) = \frac{1}{1+e^{-(x-\mu)/\gamma}}
    $$
    $$
    f(x) = F'(x) = \frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})}
    $$
  2. 二项logistic回归模型条件概率分布
    $$
    P(Y=1|x) = \frac{exp(w \cdot x + b)}{1 + exp(w \cdot x + b)}
    $$
  3. 考虑对输入的x进行分类的线性函数$w \cdot x$,其值域为实数域。对于概率
    $$
    P(Y=1 | x) = \frac{exp(w \cdot x)}{1+exp(w \cdot x)}
    $$
    线性函数的值越接近正无穷,概率值就越接近与1。这样的模型就是logistic模型。
  4. 模型参数可以使用最大似然估计。
    设:$ P(Y=1|x)=\pi(x), P(Y=0 |x)=1-\pi(x) $
    似然函数为:
    $$
    \prod_{i=1}^N[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}
    $$
    对数似然函数为:
    $$
    \begin{align}
    L(w) &= \sum_{i=1}^N[y_i\log\pi(x_i) + (1-y_i)\log(1-\pi(x_i))] \newline
    &= \sum_{i=1}^N[y_i\log\frac{\pi(x_i)}{1-\pi(x_i)}+\log(1-\pi(x_i))] \newline
    &= \sum_{i=1}^N[y_i(w\cdot x_i) - \log (1+exp(w \cdot x_i)]
    \end{align}
    $$
    对 $ L(w) $ 求极大值,得到$w$的估计值。
  5. 最大熵原理:最大熵原理认为,学习概率模型时,在所有可能的模型中熵最大的模型是最好的模型。也就是“不要把鸡蛋装在同一个篮子里”。
  6. 熵满足下列不等式
    $$
    0 \leq H(P) \leq \log|X|
    $$
    也就是说,当X服从均匀分布时,熵最大。
  7. 最大熵模型
    假设满足所有约束条件的模型集合为
    $$
    \mathcal{C} \equiv \lbrace P \in \mathcal{P} | E_P(f_i),\ i=1,2,\ldots,n \rbrace
    $$
    它定义在条件概率分布 $ P(Y|X) $上的条件熵为
    $$
    H(P)=-\sum_{x,y} \tilde P(x)P(y|x)\log P(y|x)
    $$
    则模型集合 $ \mathcal{C} $中条件熵 $ H(P) $最大的模型称为最大熵模型。
  8. 求解最大熵模型使用拉格朗日法。
  9. 最大熵函数对偶函数的极大化等价于最大熵模型的极大似然估计。
  10. 模型学习的方法有改进的迭代尺度算法(improved iterative scaling, IIS)和拟牛顿法。

《统计学习方法》读书笔记5:决策树

  1. 决策树像是if-then的规则集合。
  2. 决策树很可能发生过拟合现象,这时需要自下而上的剪枝。决策树的生成只考虑局部最优,而剪枝考虑全局最优。
  3. 特征选择时需要选取具有分类能力的特征,如果利用一个特征进行分类与随机分类的结果没有区别,则称这个特征没有分类能力。通常特征选择的标准是信息增益或信息增益比。
  4. 信息增益
    1. 熵(entropy)表示的是一个随机变量不确定的程度。设$X$是一个取有限值的离散随机变量,它的熵定义为
      $$ H(X)=-\sum_{i=1}^Np_i \log p_i $$
      如果与 $X$ 取值无关,只与其分布有关,还可以记作 $H(p)$。对数以2为底时,熵的单位为比特(bit);以 $e$ 为底时,单位为奈特(nat)。
    2. 条件熵 $H(Y|X)$ 表示已知 $X$ 的条件下,随机变量 $Y$ 的不确定程度
      $$
      H(Y|X)=\sum_{i=1}^Np_iH(Y|X=x_i)
      $$
    3. 信息增益:指给定特征 $A$ 的情况下,训练数据集 $D$ 的不确定性的减少量
      $$
      g(D, A) = H(D) - H(D|A)
      $$
      在信息论中称为互信息。$H(D)$ 是由训练集的经验概率得到的,所以称为经验熵
    4. 在实际选取过程中,根据信息增益大小选择特征
    5. 为了解决偏向于选择取值较多的特征的问题,可以用信息增益比:
      $$
      g_R(D,A) = \frac{g(D,A)}{H_A(D)}
      $$
      其中,$ H_A(D) = -\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|} $
  5. 决策树的生成
    1. ID3算法:每次挑选信息增益最大的特征分裂数据集,直到信息增益小于某一阈值。
    2. C4.5算法:改进了ID3算法,使用信息增益比
  6. 决策树的剪枝
    1. 决策树的剪枝通过极小化决策树的损失函数完成。
    2. 决策树的损失函数定义为
      $$
      C_\alpha(T)=\sum_{i=1}^{|T|}N_tH_t(T)+\alpha|T|
      $$
      其中,经验熵为
      $$
      H_t(T)=-\sum_k\frac{H_{tk}}{N_t}\log\frac{N_{tk}}{N_t}
      $$
      通常,记
      $$
      C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}
      $$
      这时有
      $$
      C_\alpha(T)=C(T)+\alpha|T|
      $$
    3. 设一组节点回缩到其父节点之前与之后的整体树分别为$T_B$与$T_A$,其对应的损失函数分别为$C_\alpha(T_B)$与$C_\alpha(T_A)$,如果
      $$
      C_\alpha(T_A)\leq C_\alpha(T_B)
      $$
      则进行剪枝,即将父节点变为新的叶节点。重复这一过程,直至不能进行为止。
  7. CART算法
    1. CART(classification and regression tree)
    2. 回归树:X和Y分别为输入变量与输出变量,且Y为连续变量
    3. 分类树
      1. 基尼系数
      2. 根据基尼系数生成回归树

《统计学习方法》学习笔记4:朴素贝叶斯法

  1. 朴素贝叶斯方法是基于贝叶斯定律的方法。它做出了条件独立这个强条件假设,在损失一定分类准确性的情况下使算法可行。
  2. 推导过程使用贝叶斯定理,最终的结果为
    $$
    y = \arg\max_{c_k}P(Y=c_k)\prod\nolimits_jP(X^{(j)}=x^{(j)}|Y=c_k)
    $$
  3. 朴素贝叶斯实际上是另后验概率最大化。这等价于期望风险最小化。
  4. 计算朴素贝叶斯参数的方法是极大似然估计。
  5. 考虑出现概率0的情况,这会影响极大似然估计的结果。解决这一问题的方法是采用贝叶斯估计。条件概率的贝叶斯估计是
    $$
    P_\lambda (X^{(j)} = a_{jl} | Y = c_k) = \frac{\sum_{i=1}^N I(x_i^{(j)} = a_{jl}, y_i = c_k) + \lambda}{\sum_{i=1}^N I(y_i = c_k) + S_j\lambda}
    $$
    式中 $ \lambda \geqslant 0 $。当 $ \lambda = 0 $ 时就是极大似然估计。常取 $ \lambda = 1 $,这时称为拉普拉斯平滑(Laplace smoothing)。
  6. 先验概率的贝叶斯估计是
    $$
    P_\lambda (Y = c_k) = \frac{\sum_{i=1}^NI(y_i = c_k) + \lambda}{N+K\lambda}
    $$