分类 机器学习 下的文章

《统计学习方法》读书笔记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)
    $$

《统计学习方法》读书笔记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}
    $$

《统计学习方法》学习笔记3:k近邻法

  1. k近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法。这里只讨论分类问题的kNN。
  2. k近邻法的算法
    1. 输入
      训练集 $$ T = \lbrace(x_1, y_1), (x_2, y_2), \cdots , (x_N, y_N)\rbrace $$
      其中,$ x_i \in \mathcal{X} \subseteq \mathbf{R}^n $为实例的特征向量,$ y_i \in \mathcal{Y} = {c_1, c_2, \cdots ,c_K} $ 为实例的类别,$ i=1,2, \cdots , N $;实例特征向量 $ x $;
    2. 输出实例$ x $所属的类 $ y $。
    3. 过程
      1. 根据给定的距离度量,找出与$x$最邻近的$k$个点,这个邻域记作$N_k(x)$
      2. 在$N_k(x)$中根据分类决策规则(如多数表决)决定$x$的类别$y$:
        $$ \arg\max_{c_j}\sum_{x_i \in N_k(x)}I(y_i=c_j), i=1,2,\cdots,N;\ j=1,2,\cdots,K $$
        其中,$I$为指示函数,即当$y_i=c_i$时$I$为1,否则$I$为0
  3. $k=1$是一种特殊情况,称为最邻近算法。
  4. k近邻法的模型三要素是距离度量$k$值分类决策规则
    1. 基本概念
      1. 单元(cell):距离该点比其他点更近的所有点组成的一个区域。每个训练实例拥有一个单元。
      2. 类标记(class label):每个单元的类别。最邻近法将实例$x_i$的类$y_i$作为其单元中所有点的类标记。
    2. 距离度量
      1. $L_p$距离定义为
        $$ L_p(x_i, x_j) = \left(\sum_{l=1}^n|x_i^{(l)}| - x_j^{(l)}|^p\right)^\frac{1}{p} $$
      2. 当$L_p$距离中$p$取2时,称为欧氏距离(Euclidean distance)
      3. 当$L_p$距离中$p$取1时,称为曼哈顿距离(Manhattan distance)
      4. 当$L_p$距离中$p$取$\infty$时,它是各个坐标距离的最大值,即
        $$ L_\infty(x_i, y_i) = \max_l|x_i^{(l)}-x_j^{(l)}| $$
      5. 此外还有Minkowski距离
      6. 距离度量不同,最邻近点不同
    3. $k$值越小意味着模型越复杂,更容易过拟合。通常$k$取一个较小的值。通常采用交叉验证法确定$k$值。
    4. 分类决策规则:$k$近邻法的分类决策往往是多数表决。分类函数为
      $$ f: \mathbf{R}^n \rightarrow \lbrace c_1, c_2, \cdots , c_K \rbrace $$
      误分类的概率是
      $$ P(Y \neq f(X)) = 1 - P(Y=f(X)) $$
      对给定的实例$x \in \mathcal{X}$,其最邻近的$k$个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域类别是$c_j$,那么误分类率是
      $$ \frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i \neq c_j) = 1-\frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i=c_j) $$
      要使误分类最小即经验风险最小,就要使$ \sum_{x_i \in N_k(k)}I(y_i = c_j) $最大,所以多数表决规则等价于经验风险最小化。
  5. 计算kNN的算法是kd树。kd树是一种对$k$维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。注意这里的$k$与$k$近邻的$k$并不是一个含义。它等于特征向量的维数。