逻辑斯蒂回归

逻辑斯蒂分布

$$\begin{align*} F(x) & = P(X \leq x) = \frac 1 {1 + e^{-(x-\mu)/\gamma}} \\ f(x) & = F^{'}(x) = \frac {e^{-(x-\mu)/\gamma}} {\gamma(1+e^{-(x-\mu)/\gamma})^2} \end{align*}$$

• $\mu$：位置参数
• $\gamma$：形状参数

• 分布函数属于逻辑斯蒂函数

• 分布函数图像为sigmoid curve

  • 关于的$(\mu, \frac 1 2)$中心对称 $$F(-x+\mu) - \frac 1 2 = -F(x+\mu) + \frac 1 2$$
  • 曲线在靠近$\mu$中心附近增长速度快，两端速度增长慢
  • 形状参数$\gamma$越小，曲线在中心附近增加越快

• 模型优点

  • 模型输出值位于0、1之间，天然具有概率意义，方便观测 样本概率分数
  • 可以结合$l-norm$正则化解决过拟合、共线性问题
  • 实现简单，广泛用于工业问题
  • 分类时计算量比较小、速度快、消耗资源少

• 模型缺点

  • 特征空间很大时，性能不是很好，容易欠拟合，准确率一般
  • 对非线性特征需要进行转换

Binomial Logistic Regression Model

二项逻辑斯蒂回归模型：形式为参数化逻辑斯蒂分布的二分类 生成模型

$$\begin{align*} P(Y=1|x) & = \frac {exp(wx + b)} {1 + exp (wx + b)} \\ P(Y=0|x) & = \frac 1 {1 + exp(wx + b)} \\ P(Y=1|\hat x) & = \frac {exp(\hat w \hat x)} {1 + exp (\hat w \hat x)} \\ P(Y=0|\hat x) & = \frac 1 {1+exp(\hat w \hat x)} \end{align*}$$

• $w, b$：权值向量、偏置
• $\hat x = (x^T|1)^T$
• $\hat w = (w^T|b)^T$

• 逻辑回归比较两个条件概率值，将实例$x$归于条件概率较大类

• 通过逻辑回归模型，可以将线性函数$wx$转换为概率

  • 线性函数值越接近正无穷，概率值越接近1
  • 线性函数值越接近负无穷，概率值越接近0

Odds/Odds Ratio

• 在逻辑回归模型中，输出$Y=1$的对数几率是输入x的线性函数

  $$log \frac {P(Y=1|x)} {1-P(Y=1|x)} = \hat w \hat x$$

• OR在逻辑回归中意义：$x_i$每增加一个单位，odds将变为原来 的$e^{w_i}$倍

  $$\begin{align*} odd &= \frac {P(Y=1|x)} {1-P(Y=1|x)} = e^{\hat w \hat x} \\ OR_{x_i+1 / x_i} &= e^{w_i} \end{align*}$$

  • 对数值型变量

    • 多元LR中，变量对应的系数可以计算相应 Conditional OR
    • 可以建立单变量LR，得到变量系数及相应 Marginal OR

  • 对分类型变量

    • 可以直接计算变量各取值间对应的OR
    • 变量数值化编码建立模型，得到变量对应OR

    • 根据变量编码方式不同，变量对应OR的含义不同，其中 符合数值变量变动模式的是WOE线性编码

策略

极大似然：极小对数损失（交叉熵损失）

$$\begin{align*} L(w) & = log \prod_{i=1}^N [\pi(x_i)]^{y_i} [1-\pi(x_i)]^{1-y_i} \\ & = \sum_{i=1}^N [y_i log \pi(x_i) + (1-y_i)log(1-\pi(x_i))] \\ & = \sum_{i=1}^N [y_i log \frac {\pi(x_i)} {1-\pi(x_i)} log(1-\pi(x_i))] \\ & = \sum_{i=1}^N [y_i(\hat w \hat x_i) - log(1+exp(\hat w \hat x_i))] \end{align*}$$

• $\pi(x) = P(Y=1|x)$

算法

• 通常采用梯度下降、拟牛顿法求解有以上最优化问题

Multi-Nominal Logistic Regression Model

多项逻辑斯蒂回归：二项逻辑回归模型推广

$$\begin{align*} P(Y=j|x) & = \frac {exp(\hat w_j \hat x)} {1+\sum_{k=1}^{K-1} exp(\hat w_k \hat x)}, k=1,2,\cdots,K-1 \\ P(Y=K|x) & = \frac 1 {1+\sum_{k=1}^{K-1} exp(\hat w_k \hat x)} \end{align*}$$

• 策略、算法类似二项逻辑回归模型

Generalized Linear Model

todo

Maximum Entropy Model

最大熵原理

最大熵原理：学习概率模型时，在所有可能的概率模型（分布）中， 熵最大的模型是最好的模型

• 使用约束条件确定概率模型的集合，则最大熵原理也可以表述为 在满足约束条件的模型中选取熵最大的模型

• 直观的，最大熵原理认为

  • 概率模型要满足已有事实（约束条件）
  • 没有更多信息的情况下，不确定部分是等可能的
  • 等可能不容易操作，所有考虑使用可优化的熵最大化 表示等可能性

最大熵模型

最大熵模型为生成模型

• 对给定数据集$T={(x_1,y_1),\cdots,(x_N,y_N)}$，联合分布 P(X,Y)、边缘分布P(X)的经验分布如下

  $$\begin{align*} \tilde P(X=x, Y=y) & = \frac {v(X=x, Y=y)} N \\ \tilde P(X=x) & = \frac {v(X=x)} N \end{align*}$$

  • $v(X=x,Y=y)$：训练集中样本$(x,y)$出频数

• 用如下feature function $f(x, y)$描述输入x、输出y之间 某个事实

  $$f(x, y) = \left \{ \begin{array}{l} 1, & x、y满足某一事实 \\ 0, & 否则 \end{array} \right.$$

  • 特征函数关于经验分布$\tilde P(X, Y)$的期望

    $$E_{\tilde P} = \sum_{x,y} \tilde P(x,y)f(x,y)$$

  • 特征函数关于生成模型$P(Y|X)$、经验分布$\tilde P(X)$ 期望

    $$E_P(f(x)) = \sum_{x,y} \tilde P(x)P(y|x)f(x,y)$$

• 期望模型$P(Y|X)$能够获取数据中信息，则两个期望值应该相等

  $$\begin{align*} E_P(f) & = E_{\tilde P}(f) \\ \sum_{x,y} \tilde P(x)P(y|x)f(x,y) & = \sum_{x,y} \tilde P(x,y)f(x,y) \end{align*}$$

  此即作为模型学习的约束条件

  • 此约束是纯粹的关于$P(Y|X)$的约束，只是约束形式特殊， 需要通过期望关联熵

  • 若有其他表述形式、可以直接带入的、关于$P(Y|X)$约束， 可以直接使用

• 满足所有约束条件的模型集合为 $$\mathcal{C} = \{P | E_{P(f_i)} = E_{\tilde P (f_i)}, i=1,2,\cdots,n \}$$ 定义在条件概率分布$P(Y|X)$上的条件熵为 $$H(P) = -\sum_{x,y} \tilde P(x) P(y|x) logP(y|x)$$ 则模型集合$\mathcal{C}$中条件熵最大者即为最大是模型

策略

最大熵模型的策略为以下约束最优化问题

$$\begin{array}{l} \max_{P \in \mathcal{C}} & -H(P)=\sum_{x,y} \tilde P(x) P(y|x) logP(y|x) \\ s.t. & E_P(f_i) - E_{\tilde P}(f_i) = 0, i=1,2,\cdots,M \\ & \sum_{y} P(y|x) = 1 \end{array}$$

• 引入拉格朗日函数

  $$\begin{align*} L(P, w) & = -H(P) - w_0(1-\sum_y P(y|x)) + \sum_{m=1}^M w_m(E_{\tilde P}(f_i) - E_P(f_i)) \\ & = \sum_{x,y} \tilde P(x) P(y|x) logP(y|x) + w_0 (1-\sum_y P(y|x)) + \sum_{m=1}^M w_m (\sum_{x,y} \tilde P(x,y)f_i(x, y) - \tilde P(x)P(y|x)f_i(x,y)) \end{align*}$$

  • 原始问题为

    $$\min_{P \in \mathcal{C}} \max_{w} L(P, w)$$

  • 对偶问题为

    $$\max_{w} \min_{P \in \mathcal{C}} L(P, w)$$

  • 考虑拉格朗日函数$L(P, w)$是P的凸函数，则原始问题、 对偶问题解相同

• 记

  $$\begin{align*} \Psi(w) & = \min_{P \in \mathcal{C}} L(P, w) = L(P_w, w) \\ P_w & = \arg\min_{P \in \mathcal{C}} L(P, w) = P_w(Y|X) \end{align*}$$

• 求$L(P, w)$对$P(Y|X)$偏导

  $$\begin{align*} \frac {\partial L(P, w)} {\partial P(Y|X)} & = \sum_{x,y} \tilde P(x)(logP(y|x)+1) - \sum_y w_0 - \sum_{x,y}(\tilde P(x) \sum_{i=1}^N w_i f_i(x,y)) \\ & = \sum_{x,y} \tilde P(x)(log P(y|x) + 1 - w_0 - \sum_{i=1}^N w_i f_i(x, y)) \end{align*}$$

  偏导置0，考虑到$\tilde P(x) > 0$，其系数必始终为0，有

  $$\begin{align*} P(Y|X) & = \exp(\sum_{i=1}^N w_i f_i(x,y) + w_0 - 1) \\ & = \frac {exp(\sum_{i=1}^N w_i f_i(x,y))} {exp(1-w_0)} \end{align*}$$

• 考虑到约束$\sum_y P(y|x) = 1$，有

  $$\begin{align*} P_w(y|x) & = \frac 1 {Z_w(x)} exp(\sum_{i=1}^N w_i f_i(x,y)) \\ Z_w(x) & = \sum_y exp(\sum_{i=1}^N w_i f_i(x,y)) \\ & = exp(1 - w_0) \end{align*}$$

  • $Z_w(x)$：规范化因子
  • $f(x, y)$：特征
  • $w_i$：特征权值

• 原最优化问题等价于求解偶问题极大化问题$\max_w \Psi(w)$

  $$\begin{align*} \Psi(w) & = \sum_{x,y} \tilde P(x) P_w(y|x) logP_w(y|x) + \sum_{i=1}^N w_i(\sum_{x,y} \tilde P(x,y) f_i(x,y) - \sum_{x,y} \tilde P(x) P_w(y|x) f_i(x,y)) \\ & = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^N w_i f_i(x,y) + \sum_{x,y} \tilde P(x,y) P_w(y|x)(log P_w(y|x) - \sum_{i=1}^N w_i f_i(x,y)) \\ & = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^N w_i f_i(x,y) - \sum_{x,y} \tilde P(x,y) P_w(y|x) log Z_w(x) \\ & = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^N w_i f_i(x,y) - \sum_x \tilde P(x) log Z_w(x) \end{align*}$$

  记其解为

  $$w^{*} = \arg\max_w \Psi(w)$$

  带入即可得到最优（最大熵）模型$P_{w^{*}}(Y|X)$

策略性质

• 已知训练数据的经验概率分布为$\tilde P(X,Y)$，则条件概率 分布$P(Y|X)$的对数似然函数为

  $$\begin{align*} L_{\tilde P}(P_w) & = N log \prod_{x,y} P(y|x)^{\tilde P(x,y)} \\ & = \sum_{x,y} N * \tilde P(x,y) log P(y|x) \end{align*}$$

  • 这里省略了系数样本数量$N$

• 将最大熵模型带入，可得

  $$\begin{align*} L_{\tilde P_w} & = \sum_{x,y} \tilde P(y|x) logP(y|x) \\ & = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^N w_i f_i(x,y) - \sum_{x,y} \tilde P(x,y)log Z_w(x) \\ & = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^N w_i f_i(x,y) - \sum_x \tilde P(x) log Z_w(x) \\ & = \Psi(w) \end{align*}$$

  对偶函数$\Psi(w)$等价于对数似然函数$L_{\tilde P}(P_w)$， 即最大熵模型中，对偶函数极大等价于模型极大似然估计

改进的迭代尺度法

• 思想

  • 假设最大熵模型当前参数向量$w=(w_1,w_2,\cdots,w_M)^T$
  • 希望能找到新的参数向量（参数向量更新） $w+\sigma=(w_1+\sigma_1,\cdots,w_M+\sigma_M)$ 使得模型对数似然函数/对偶函数值增加
  • 不断对似然函数值进行更新，直到找到对数似然函数极大值

• 对给定经验分布$\tilde P(x,y)$，参数向量更新至$w+\sigma$ 时，对数似然函数值变化为

  $$\begin{align*} L(w+\sigma) - L(w) & = \sum_{x,y} \tilde P(x,y) log P_{w+\sigma}(y|x) - \sum_{x,y} \tilde P(x,y) log P_w(y|x) \\ & = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^M \sigma_i f_i(x,y) - \sum_x \tilde P(x) log \frac {Z_{w+\sigma}(x)} {Z_w(x)} \\ & \geq \sum_{x,y} \tilde P(x,y) \sum_{i=1}^M \sigma_i f_i(x,y) + 1 - \sum_x \tilde P(x) \frac {Z_{w+\sigma}(x)} {Z_w(x)} \\ & = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^M \sigma_i f_i(x,y) + 1 - \sum_x \tilde P(x) \sum_y P_y(y|x) exp(\sum_{i=1}^M \sigma_i f_i(x,y)) \end{align*}$$

  • 不等式步利用$a - 1 \geq log a, a \geq 1$

  • 最后一步利用

    $$\begin{align*} \frac {Z_{w+\sigma}(x)} {Z_w(x)} & = \frac 1 {Z_w(x)} \sum_y exp(\sum_{i=1}^M (w_i + \sigma_i) f_i(x, y)) \\ & = \frac 1 {Z_w(x)} \sum_y exp(\sum_{i=1}^M w_i f_i(x,y) + \sigma_i f_i(x,y)) \\ & = \sum_y P_w(y|x) exp(\sum_{i=1}^n \sigma_i f_i(x,y)) \end{align*}$$

• 记上式右端为$A(\sigma|w)$，则其为对数似然函数改变量的 一个下界

  $$L(w+\sigma) - L(w) \geq A(\sigma|w)$$
  • 若适当的$\sigma$能增加其值，则对数似然函数值也应该 增加
  • 函数$A(\sigma|w)$中因变量$\sigma$为向量，难以同时 优化，尝试每次只优化一个变量$\sigma_i$，固定其他变量 $\sigma_j$

• 记

  $$f^{**} (x,y) = \sum_i f_i(x,y)$$

  考虑到$f_i(x,y)$为二值函数，则$f^{**}(x,y)$表示所有特征 在$(x,y)$出现的次数，且有

  $$A(\sigma|w) = \sum_{x,y} \tilde P(x,y) \sum_{i=1}^M \sigma_i f_i(x,y) + 1 - \sum_x \tilde P(x) \sum_y P_w(y|x) exp(f^{**}(x,y) \sum_{i=1}^M \frac {\sigma_i f_i(x,y)} {f^{**}(x,y)})$$

• 考虑到$\sum_{i=1}^M \frac {f_i(x,y)} {f^{**}(x,y)} = 1$， 由指数函数凸性、Jensen不等式有

  $$exp(\sum_{i=1}^M \frac {f_i(x,y)} {f^{**}(x,y)} \sigma_i f^{**}(x,y)) \leq \sum_{i=1}^M \frac {f_i(x,y)} {f^{**}(x,y)} exp(\sigma_i f^{**}(x,y))$$

  则

  $$A(\sigma|w) \geq \sum_{x,y} \tilde P(x,y) \sum_{i=1}^M \sigma_i f_i(x,y) + 1 - \sum_x \tilde P(x) \sum_y P_w(y|x) \sum_{i=1}^M \frac {f_i(x,y)} {f^{**}(x,y)} exp(\sigma_i f^{**}(x,y))$$

• 记上述不等式右端为$B(\sigma|w)$，则有

  $$L(w+\sigma) - L(w) \geq B(\sigma|w)$$

  其为对数似然函数改变量的一个新、相对不紧的下界

• 求$B(\sigma|w)$对$\sigma_i$的偏导

  $$\frac {\partial B(\sigma|w)} {\partial \sigma_i} = \sum_{x,y} \tilde P(x,y) f_i(x,y) - \sum_x \tilde P(x) \sum_y P_w(y|x) f_i(x,y) exp(\sigma_i f^{**}(x,y))$$

  置偏导为0，可得

  $$\sum_x \tilde P(x) \sum_y P_w(y|x) f_i(x,y) exp(\sigma_i f^{**}(x,y)) = \sum_{x,y} \tilde P(x,y) f_i(x,y) = E_{\tilde P}(f_i)$$

  其中仅含变量$\sigma_i$，则依次求解以上方程即可得到 $\sigma$

算法

• 输入：特征函数$f_1, f_2, \cdots, f_M$、经验分布 $\tilde P(x)$、最大熵模型$P_w(x)$
• 输出：最优参数值$wi^{*}$、最优模型$P{w^{*}}$

1. 对所有$i \in {1,2,\cdots,M}$，取初值$w_i = 0$

2. 对每个$i \in {1,2,\cdots,M}$，求解以上方程得$\sigma_i$

   • 若$f^{**}(x,y)=C$为常数，则$\sigma_i$有解析解

     $$\sigma_i = \frac 1 C log \frac {E_{\tilde P}(f_i)} {E_P(f_i)}$$

   • 若$f^{**}(x,y)$不是常数，则可以通过牛顿法迭代求解

     $$\sigma_i^{(k+1)} = \sigma_i^{(k)} - \frac {g(\sigma_i^{(k)})} {g^{'}(\sigma_i^{(k)})}$$

     • $g(\sigma_i)$：上述方程对应函数

     • 上述方程有单根，选择适当初值则牛顿法恒收敛

3. 更新$w_i$，$w_i \leftarrow w_i + \sigma_i$，若不是所有 $w_i$均收敛，重复2

BFGS算法

对最大熵模型

• 为方便，目标函数改为求极小

  $$\begin{array}{l} \min_{w \in R^M} f(w) = \sum_x \tilde P(x) log \sum_{y} exp(\sum_{i=1}^M w_i f_i(x,y)) - \sum_{x,y} \tilde P(x,y) \sum_{i=1}^M w_i f_i(x,y) \end{array}$$

• 梯度为

  $$\begin{align*} g(w) & = (\frac {\partial f(w)} {\partial w_i}, \cdots, \frac {\partial f(w)} {\partial w_M})^T \\ \frac {\partial f(w)} {\partial w_M} & = \sum_{x,y} \tilde P(x) P_w(y|x) f_i(x,y) - E_{\tilde P}(f_i) \end{align*}$$

算法

将目标函数带入BFGS算法即可

• 输入：特征函数$f_1, f_2, \cdots, f_M$、经验分布 $\tilde P(x)$、最大熵模型$P_w(x)$
• 输出：最优参数值$wi^{*}$、最优模型$P{w^{*}}$

1. 取初值$w^{(0)}$、正定对称矩阵$B^{(0)}$，置k=0

2. 计算$g^{(k)} = g(w^{(k)})$，若$|g^{(k)}| < \epsilon$， 停止计算，得到解$w^{*} = w^{(k)}$

3. 由拟牛顿公式$B^{(k)}p^{(k)} = -g^{(k)}$求解$p^{(k)}$

4. 一维搜索，求解

   $$\lambda^{(k)} = \arg\min_{\lambda} f(w^{(k)} + \lambda p_k)$$

5. 置$w^{(k+1)} = w^{(k)} + \lambda^{(k)} p_k$

6. 计算$g^{(k+1)} = g(w^{(k+1)})$，若 $|g^{(k+1)}| < \epsilon$，停止计算，得到解 $w^{*} = w^{(k+1)}$，否则求

   $$B^{(k+1)} = B^{(k)} - \frac {B^{(k)} s^{(k)} (s^{(k)})^T B^{(k)}} {(s^{(k)})^T B^{(k)} s^{(k)}} + \frac {y^{(k)} (y^{(k)})^T} {(y^{(k)})^T s^{(k)}}$$

   • $s^{(k)} = w^{(k+1)} - w^{(k)}$
   • $y^{(k)} = g^{(k+1)} - g^{(k)}$

7. 置k=k+1，转3

因子分解机

因子分解机：将变量交互影响因子化 （每个变量用隐向量代表、衡量其交叉影响）

$$\hat y(x) := w_0 + \sum_{i=1}^m w_i x_i + \sum_{i=1}^m \sum_{j=i+1}^m <v_i, v_j> x_i x_j$$

• $w_0$：全局偏置
• $w_i$：变量$i$权重
• $w_{i,j} := $：变量$i$、$j$之间交互项权重
• $v_i$：$k$维向量，变量交叉影响因子

• FM通过因子化交互影响解耦交互项参数

  • 即使没有足够数据也能较好估计高维稀疏特征交互影响参数

    • 无需大量有交互影响（交互特征取值同时非0）样本
    • 包含某交互影响数据也能帮助估计相关的交互影响
    • 可以学习数据不存在的模式

  • 可以视为embedding，特征之间关联性用embedding向量 （隐向量）內积表示

• 参数数量、模型复杂度均为线性

  • 可以方便使用SGD等算法对各种损失函数进行优化
  • 无需像SVM需要支持向量，可以扩展到大量数据集

• 适合任何实值特征向量，对某些输入特征向量即类似 biased MF、SVD++、PITF、FPMC

• 另外还有d-way因子分解机，交互作用以PARAFAC模型因子化 $$\hat y(x) := w_0 + \sum_{i=1}^n w_i x_i + \sum_{l=2}^d \sum_{i_1=1} \cdots \sum_{i_l=i_{l-1}+1}(\prod_{j=1}^l x_{i_j}) (\sum_{f=1} \prod_{j=1}^l v_{i_j,f}^{(l)}) \\$$

  • $V^{(l)} \in R^{n * k_l}, k_l \in N_0^{+}$

模型表达能力

• 考虑任何正定矩阵$W$总可以被分解为$W=V V^T$，则$k$足够大 时，FM总可以表达（还原）交叉项权重矩阵$W$

  • FM是MF降维的推广，在用户-物品评分矩阵基础上集成其他 特征
  • 特征组合发生所有变量之间

• 实际应该选取较小的$k$

  • 对较大$k$，稀疏特征没有足够数据估计复杂交叉项权重 矩阵$W$
  • 限制FM的表达能力，模型有更好的泛化能力、交互权重矩阵

模型求解

$$\begin{align*} \sum_{i=1}^m \sum_{j=i+1}^m <v_i, v_j> x_i x_j & = \frac 1 2 \sum_{i=1}^m \sum_{j=i}^m <v_i, v_j> x_i x_j - \frac 1 2 \sum_{i=1}^m <v_i, v_i> x_i^2 \\ & = \frac 1 2 (x^T V^T V x - x^T diag(V^T V) x) \\ & = \frac 1 2 (\|Vx\|_2^2 - x^T diag(V^T V) x) \\ & = \frac 1 2 \sum_{f=1}^k ((\sum_{i=1}^m v_{i,f} x_i)^ 2 - \sum_{i=1}^m v_{i,f}^2 x_i^2) \\ \end{align*}$$

• $V = (v_1, v_2, \cdots, v_m)$
• $x = (x_1, x_2, \cdots, x_m)^T$

• 模型计算复杂度为线性$\in O(kn)$

• 模型可以使用梯度下降类方法高效学习

  $$\begin{align*} \frac {\partial \hat y(x)} {\partial \theta} & = \left \{ \begin{array}{l} 1, & \theta := w_0 \\ x_i, & \theta := w_i \\ x_i Vx - v_i x_i^2& \theta := v_i \end{array} \right. \\ & = \left \{ \begin{array}{l} 1, & \theta := w_0 \\ x_i, & \theta := w_i \\ x_i \sum_{j=1}^m v_{j,f} x_j - v_{i,f} x_i^2, & \theta := v_{i,f} \end{array} \right. \end{align*}$$

• 考虑到稀疏特征，內积只需计算非零值

模型适用

• 回归：直接用$\hat y(x)$作为回归预测值
• 二分类：结合logit损失、hinge损失优化
• ranking：$\hat y(x)$作为得分排序，使用成对分类损失优化

Field-aware Factorization Machines

域感知因子分解机：在FM基础上考虑对特征分类，特征对其他类别 特征训练分别训练隐向量

$$\begin{align*} \hat y(x) & = w_0 + \sum_{i=0}^m w_i x_i + \sum_{a=1}^m \sum_{b=a+1}^m <V_{a, f_b}, V_{b, f_a}> x_a x_b \\ & = w_0 + \sum_{i=1}^M \sum_{j=1}^{M_i} w_{i,j} x_{i,j} + \sum_{i=1}^M \sum_{j=1}^{M_i} \sum_{a=i}^M \sum_{b=1}^{M_i} <V_{i,j,a}, V_{a,b,i}> x_{i,j} x_{a,b} \end{align*}$$

• $m$：特征数量
• $M, M_i$：特征域数量、各特征域中特征数量
• $V_{i,j,a}$：特征域$i$中$j$特征对特征与$a$的隐向量
• $V_{a, f_b}$：特征$x_a$对特征$b$所属域$f_b$的隐向量

• FFM中特征都属于特定域，相同特征域中特征性质应该相同， 一般的

  • 连续特征自己单独成域
  • 离散0/1特征按照性质划分，归于不同特征域

• 特征对其他域分别有隐向量表示和其他域的隐含关系

  • 考虑交互作用时，对不同域使用不同隐向量计算交互作用
  • FFM中隐变量维度也远远小于FM中隐向量维度

算法

模型特点

• 模型总体类似FM，仅通过多样化隐向量实现细化因子分解
• 模型总体较FM复杂度大、参数数量多
  • 无法抽取公因子化简为线性
  • 数据量较小时可能无法有效训练隐向量

Naive Bayes Classifier

朴素贝叶斯：在训练数据集上学习联合概率分布$P(X,Y)$，利用后验 分布作为结果

• 朴素：条件概率分布有条件独立性假设，即特征在类别确定 下条件独立

模型

• 输出Y的先验概率分布为

  $$P(Y = c_k), k = 1,2,\cdots,K$$

  • 先验概率是指输出变量，即待预测变量的先验概率分布， 反映其在无条件下的各取值可能性
  • 同理所有的条件概率中也是以输出变量取值作为条件

• 条件概率分布为

  $$P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)}| Y=c_k)$$

  • $D$：用于分类特征数量

  其中有指数数量级的参数（每个参数的每个取值都需要参数）

• 因此对条件概率分布做条件独立性假设，即分类特征在类别 确定条件下是独立的

  $$\begin{align*} P(X=x|Y=c_k) & = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)} |Y=c_k) \\ & = \prod_{j=1}^D P(X^{(j)}=x^{(j)}|Y=c_k) \end{align*}$$
  • 条件独立性假设是比较强的假设，也是朴素的由来

  • 其使得朴素贝叶斯方法变得简单，但有时也会牺牲准确率

  • 以上即可得到联合概率分布$P(X,Y)$

  • 朴素贝叶斯学习到的联合概率分布$P(X,Y)$是数据生成的 机制，即其为生成模型

策略

策略：选择使得后验概率最大化的类$c_k$作为最终分类结果

$$P(Y=c_k|X=x) = \frac {P(Y=c_k, X=x)} {\sum_{i=1}^K P(Y=c_k, X=x)}$$

• $K$：输出类别数量

• 后验概率根计算根据贝叶斯定理计算

  $$\begin{align*} P(Y=c_k|X=x) & = \frac {P(X=x|Y=c_k)P(Y=c_k)} {\sum_{k=1}^K P(X=x|Y=c_k) P(Y=c_k)} \\ & = \frac {P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} {\sum_{k=1}^K P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} \end{align*}$$

• 考虑上式中分母对所有$c_k$取值均相等，则最终分类器为

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 即分类时，对给定输入$x$，将其归类为后验概率最大的类

策略性质

后验概率最大化等价于0-1损失的经验风险最小化

• 经验风险为

  $$\begin{align*} R_{emp}(f) & = E[L(Y, f(X))] \\ & = E_x \sum_{k=1}^K L(y, c_k) P(c_k | X) \end{align*}$$

• 为使经验风险最小化，对训练集中每个$X=x$取极小化，对每个 个体$(x,y)$有

  $$\begin{align*} f(x) & = \arg\min_{c_k} \sum_{k=1}^K L(y, c_k) P(c_k|X=x) \\ & = \arg\min_{c_k} \sum_{k=1}^K P(y \neq c_k|X=x) \\ & = \arg\min_{c_k} (1-P(y=c_k|X=x)) \\ & = \arg\max_{c_k} P(y=c_k|X=x) \end{align*}$$

  即后验概率最大化

算法

极大似然估计

• 先验概率的极大似然估计为

  $$P(Y=c_k) = \frac {\sum_{i=1}^N I(y_i = c_k)} N, k=1,2,\cdots,K$$

• 条件概率的极大似然估计为

  $$P(X^{(j)}=a_{j,l}|Y=c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)}=a_{j,l}, y_i=c_k)} {\sum_{i=1}^N I(y_i=c_k)} \\ j=1,2,\cdots,N;l=1,2,\cdots,S_j;k=1,2,\cdots,K$$

  • $a_{j,l}$；第j个特征的第l个可能取值
  • $S_j$：第j个特征的可能取值数量
  • $I$：特征函数，满足条件取1、否则取0

算法

• 输入：训练数据T
• 输出：朴素贝叶斯分类器

1. 依据以上公式计算先验概率、条件概率

2. 将先验概率、条件概率带入，得到朴素贝叶斯分类器

   $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$

贝叶斯估计

• 条件概率贝叶斯估计

  $$P(X^{(j)}=a_{j,l}|Y=c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)}=a_{j,l}, y_i=c_k) + \lambda} {\sum_{i=1}^N I(y_i=c_k) + S_j \lambda} \\ j=1,2,\cdots,N;l=1,2,\cdots,S_j;k=1,2,\cdots,K$$

  • $\lambda \geq 0$

  • $\lambda=0$时就是极大似然估计
  • 常取$\lambda=1$，此时称为Laplace Smoothing
  • 以上设计满足概率分布性质 $$\begin{align*} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) \geq 0 \\ \sum_{l=1}^{S_j} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) = 1 \end{align*}$$

• 先验概率贝叶斯估计

  $$P_{\lambda}(Y=c_k) = \frac {\sum_{i=1}^N I(y_i = c_i) + \lambda} {N + K\lambda}$$

• 极大似然估计可能出现所需估计概率值为0，影响后验概率计算 结果，贝叶斯估计能够避免这点

Semi-Naive Bayes Classifier

半朴素贝叶斯分类器：适当考虑部分特征之间的相互依赖信息

• Semi-Naive Bayes可以视为是利用规则对变量加权，以 此来体现相关变量的协同影响

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D \beta_j P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 特别的：权值为0/1即为变量筛选

One-Depentdent Estimator

独依赖估计：假设特征在类别之外最多依赖一个其他特征，这是半 朴素贝叶斯分类器中最常用的一种策略

$$P(X=x|Y=c_k) = \prod_{j=1}^D P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$$

• $pa_j$：特征$X^{(j)}$依赖的父特征

• 若父特征已知，同样可以使用条件概率计算 $P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$

  $$P(X^{(j)}=x^{(j)} | Y=c_k, pa_j) = \frac {P(X^{(j)}=x^{(j)}, Y=c_k, pa_j)} {P(Y=c_k, pa_j)}$$

• ODE形式半朴素贝叶斯分类器相应的策略为

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa_j)$$

• 根据确定各特征父特征的不同做法，可以分为不同类型的独依赖 分类器

  • Super-Parent ODE：假设所有特征都依赖同一父特征
  • Averaged ODE：类似随机森林方法，尝试将每个属性作为 超父特征构建SPODE
  • Tree Augmented Naive Bayes：基于最大带权生成树发展

SPODE

SPODE：每个特征只与其他唯一一个特征有依赖关系

$$y = \arg\max_{c_k} P(Y=c_k, pa) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa)$$

• $pa$：所有特征共有的依赖父特征

AODE

AODE：以所有特征依次作为超父特征构建SPODE，以具有足够训练 数据支撑的SPODE集群起来作为最终结果

$$y = \arg\max_{c_k} (\sum_{i=1}^D P(Y=c_k, X^{(i)}) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, X^{(i)}))$$

• 这里只选取训练数据足够，即取特征$X^{(i)}$某个取值的样本 数量大于某阈值的SPODE加入结果

TAN

TAN步骤

• 计算任意特征之间的互信息

  $$g(X^{(i)}, X^{(j)}| Y) = \sum P(X^{(i)}, X^{(j)} | Y=c_k) log \frac {P(X^{(i)}, X^{(j)} | Y=c_k)} {P(X^{(i)} | Y=c_k) P(X^{(j)} | Y=c_k)}$$

• 以特征为节点构建完全图，节点边权重设为相应互信息

• 构建此完全图的最大带权生成树

  • 挑选根变量
  • 将边设置为有向

• 加入预测节点$Y$，增加从$Y$到每个属性的有向边

特点

• 条件互信息$g(X^{(i)}, X^{(j)}| Y)$刻画了特征在已知类别 情况下的相关性

• 通过最大生成树算法，TAN仅保留了强相关属性之间的依赖性

子集回归

• 特征子集选择独立于回归模型拟合，属于封装器特征选择

最优子集

• 特点
  • 可以得到稀疏的模型
  • 但搜索空间离散，可变性大，稳定性差

Forward Feature Elimination

前向变量选择

步骤

• 初始变量集合$S_0 = \varnothing$
• 选择具有某种最优特性的变量进入变量集合，得到$S_1$
• 第j步时，从剩余变量中选择最优变量进入集合，得到$S_{j+1}$
• 若满足终止条件，则结束，否则重复上步添加变量
  • j达到上限
  • 添加剩余变量均无法满足要求

Backward Feature Elimination

后向变量选择

步骤

• 初始变量集合$S_0$包含全部变量
• 从变量集合中剔除具有某种最差特性变量，得到$S_1$
• 第j步时，从剩余变量中剔除最差变量，得到$S_{j+1}$
• 若满足终止条件，则结束，否则重复上步添加变量
  • j达到上限
  • 剔除剩余变量均无法满足要求

范数正则化约束

• 回归过程中自动选择特征，属于集成特征选择

Ridge Regression

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda ||\beta||_2^2 \right\}$$

• 在L2范数约束下最小化残差平方
• 作为连续收缩方法
  • 通过bias-variance trade-off，岭回归较普通最小二乘 预测表现更好
  • 倾向于保留所有特征，无法产生疏系数模型

LASSO

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda||\beta||_1 \right\}$$

能够选择部分特征，产生疏系数模型

• p > n时，即使所有特征都有用，LASSO也只能从中挑选n个
• 如果存在相关性非常高的特征，LASSO倾向于只从该组中选择 一个特征，而且是随便挑选的
  • 极端条件下，两个完全相同的特征函数，严格凸的罚函数 （如Ridge）可以保证最优解在两个特征的系数相等，而 LASSO的最优解甚至不唯一

Elastic Net

Naive Elastic Net

$$\begin{align*} & \min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda_1||\beta||_1 + \lambda_2||\beta||_2^2 \right\} \\ \Rightarrow & \min_{\beta^* \in R^p} \left\{ ||y - X^*\beta^*||_2^2 + \lambda^*||\beta^*||_1 \right\} \\ where: & y^* = \begin{pmatrix} y \\ \vec 0_p \end{pmatrix} \\ & X^* = \frac 1 {\sqrt {1+\lambda^2}} \begin{pmatrix} X \\ \sqrt {\lambda_2} I_p \end{pmatrix} \\ & \beta^* = \sqrt {1+\lambda_2} \beta \\ & \lambda^* = \frac {\lambda_1} {1+\lambda_2} \\ \end{align*}$$

• 弹性网在Lasso的基础上添加系数的二阶范数

  • 能同时做变量选择和连续收缩
  • 并且可以选择一组变量

• 传统的估计方法通过二阶段估计找到参数

  • 首先设置ridge系数$\lambda_2$求出待估参数$\beta$， 然后做lasso的收缩
  • 这种方法有两次收缩，会导致估计偏差过大，估计不准

• 弹性网可以变换为LASSO，因而lasso的求解方法都可以用于 elastic net

elastic_net

Least Angle Regression

• 线性回归即找的一组系数能够用自变量的线性组合表示 因变量

Forward Selection/Forward Stepwise Regression

• 从所有给定predictors中选择和y相关系数绝对值最大的变量 $x_{j1}$，做线性回归

  • 对于标准化后的变量，相关系数即为变量之间的内积
  • 变量之间相关性越大，变量的之间的夹角越小，单个变量 能解释得效果越好
  • 此时残差同解释变量正交

• 将上一步剩余的残差作为reponse，将剩余变量投影到残差上 重复选择步骤

  • k步之后即可选出一组变量，然后用于建立普通线性模型

• 前向选择算法非常贪心，可能会漏掉一些有效的解释变量，只是 因为同之前选出向量相关

Forward Stagewise

前向选择的catious版本

• 和前向选择一样选择和y夹角最小的变量，但是每次只更新较小 步长，每次更新完确认和y夹角最小的变量，使用新变量进行 更新

  • 同一个变量可能会被多次更新，即系数会逐渐增加
  • 每次更新一小步，避免了前向选择的可能会忽略关键变量

• 输入：实例的特征向量
• 输出：实例类别+1、-1

感知机模型

感知机：线性二分类模型（判别模型）

$$f(x) = sign(wx + b)$$

• $x \in \chi \subseteq R^n$：输入空间
• $y \in \gamma \subseteq R^n$：输出空间
• $w \in R^n, b \in R$：weight vector、bias
• 也常有$\hat w = (w^T, b^T)^T, \hat x = (x^T + 1)^T$， 则有$\hat w \hat x = wx + b$

• 感知机模型的假设空间是定义在特征空间的所有 linear classification model/linear classifier，即函数 集合${f|f(x)=wx+b}$

• 线性方程$wx+b=0$：对应特征空间$R^n$中一个hyperplane

  • $w$：超平面法向量
  • $b$：超平面截距

  • 超平面将特征空间划分为两个部分，其中分别被分为正、负 两类

  • 也被称为separating hyperplane

Linearly Separable Data Set

• 对数据集$T={(x_1,y_1),\cdots,(x_N,y_N)}$，若存在超平面 $S: wx + b=0$能够将正、负实例点，完全正确划分到超平面 两侧，即 $$\begin{align*} wx_i + b > 0, & \forall y_i > 0 \\ wx_i + b < 0, & \forall y_i < 0 \end{align*}$$ 则称数据集T为线性可分数据集

感知机学习策略

感知机学习策略：定义适当损失函数，并将经验风险极小化，确定 参数$w, b$

0-1损失

经验风险：误分率（误分点总数）

• 不是参数$w, b$的连续可导函数，不易优化

绝对值损失

经验风险：误分类点到超平面距离

• 对误分类数据$(x_i, y_i)$，有$-y_i(wx_i + b) > 0$

• 则误分类点$(x_i, y_i)$到超平面S距离

  $$\begin{align*} d_i & = \frac 1 {\|w\|} |wx_i + b| \\ & =-\frac 1 {\|w\|} y_i(wx_i + b) \end{align*}$$

• 则感知机损失函数可定义为 $L(w,b) = -\sum_{x_i \in M} y_i(wx_i + b)$

  • $M$：误分类点集合
  • 损失函数是$w, b$的连续可导函数：使用$y_i$替代绝对值

• 损失函数$L(w,b)$梯度有

  $$\begin{align*} \bigtriangledown_wL(w, b) & = -\sum_{x_i \in M} y_ix_i \\ \bigtriangledown_bL(w, b) & = -\sum_{x_i \in M} y_i \end{align*}$$

学习算法

Stochastic Gradient Descent

随机梯度下降法

• 输入：数据集$T$、学习率$\eta, 0 \leq \eta \leq 1$
• 输出：$w,b$、感知模型$f(x)=sgn(wx+b)$

1. 选取初值$w_0, b_0$

2. 随机选取一个误分类点$(x_i, y_i)$，即$y_i(wx_i+b) \leq 0$ ，对$w, b$进行更新

   $$\begin{align*} w^{(n+1)} & \leftarrow w^{(n)} + \eta y_ix_i \\ b^{(n+1)} & \leftarrow b^{(n)} + \eta y_i \end{align*}$$

   • $0 < \eta \leq 1$：learning rate，学习率，步长

3. 转2，直至训练集中无误分类点

• 不同初值、随机取点顺序可能得到不同的解
• 训练数据线性可分时，算法迭代是收敛的
• 训练数据不线性可分时，学习算法不收敛，迭代结果发生震荡
• 直观解释：当实例点被误分类，应该调整$w, b$值，使得分离 超平面向误分类点方向移动，减少误分类点与超平面距离， 直至被正确分类

学习算法对偶形式

todo

算法收敛性

为方便做如下记号

• $\hat w = (w^T, b^T)^T, \hat w \in R^{n+1}$
• $\hat x = (x^T, 1)^T, \hat x \in R^{n+1}$

此时，感知模型可以表示为

$$xw + b = \hat w \hat x = 0$$

• 数据集$T={(x_1, y_1), (x_2, y_2),…}$线性可分，其中： $x_i \in \mathcal{X = R^n}$， $y_i \in \mathcal{Y = {-1, +1}}$，则

• 存在满足条件$|\hat w{opt}|=1$超平面 $\hat w{opt} \hat x = 0$将训练数据完全正确分开，且 $\exists \gamma > 0, yi(\hat w{opt} x_i) \geq \gamma$

• 令$R = \arg\max_{1\leq i \leq N} |\hat x_i|$，则 随机梯度感知机误分类次数$k \leq (\frac R \gamma)^2$

超平面存在性

• 训练集线性可分，存在超平面将训练数据集完全正确分开，可以 取超平面为$\hat w_{opt} \hat x = 0$

• 令$|\hat w_{opt}| = 1$，有

  $$\forall i, y_i(\hat w_{opt} \hat x_i) > 0$$

  可取

  $$\gamma = \min_i \{ y_i (\hat w_{opt} \hat x) \}$$

  满足条件

感知机算法收敛性

• 给定学习率$\eta$，随机梯度下降法第k步更新为 $\hat wk = \hat w{k-1} + \eta y_i \hat x_i$

• 可以证明

  • $\hat wk \hat w{opt} \geq k\eta\gamma$

    $$\begin{align*} \hat w_k \hat w_{opt} & = \hat w_{k-1} \hat w_{opt} + \eta y_i \hat w_{opt} \hat x_i \\ & \geq \hat w_{k-1} \hat w_{opt} + \eta\gamma \\ & \geq k\eta\gamma \end{align*}$$

  • $|\hat w_k|^2 \leq k \eta^2 R^2$

    $$\begin{align*} \|\hat w_k\|^2 & = \|\hat w_{k-1} + \eta y_i x_i \|^2 \\ & = \|\hat w_{k-1}\|^2 + 2\eta y_i \hat w_{k-1} \hat x_i + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 R^2 \\ & \leq k\eta^2 R^2 \end{align*}$$

• 则有

  $$\begin{align*} k \eta \gamma & \leq \hat w_k \hat w_{opt} \leq \|\hat w\| \|\hat w_{opt}\| = \|\hat w\| \leq \sqrt k \eta R \\ k^2 \gamma^2 & \leq k R^2 \end{align*}$$

• 直观理解就是超平面最大移动次数不大于最大移动距离 除以最小移动步长

  • $\eta \gamma^2$：超平面法向量最小增加量（移动步长）
  • $\eta R^2$：超平面法向最大增加量（移动距离）
  • 但是超平面不可能将所有点都归为同一侧

• 误分类次数有上界，经过有限次搜索可以找到将训练数据完全 正确分开的分离超平面，即训练数据集线性可分时，算法的迭代 形式是收敛的

总述

支持向量机是二分类模型

学习要素

• 基本模型：定义在特征空间上的间隔最大线性分类器

• 学习策略：间隔最大化

  • 可形式化为求解凸二次规划问题，也等价于正则化的合页 损失函数最小化问题

  • 间隔最大使其有别于感知机，训练数据线性可分时分离 超平面唯一

    • 误分类最小策略（0-1损失）得到分离超平面的解无穷 多个
    • 距离和最小策略（平方损失）得到分离超平面唯一， 但与此不同

• 学习算法：求解凸二次规划的最优化算法

数据

在给定特征空间上的训练数据集 $T={(x_1,y_1), (x_2,y_2),\cdots,(x_N,y_N)}$，其中 $x_i \in \mathcal{X} = R^n, y_i \in {-1, +1}, i=1,2,…,N$

• 输入空间：欧氏空间或离散集合
• 特征空间：希尔伯特空间
• 输出空间：离散集合

• SVM假设输入空间、特征空间为两个不同空间，SVM在特征空间 上进行学习

• 线性（可分）支持向量机假设两个空间元素一一对应，并将 输入空间中的输入映射为特征空间中特征向量

• 非线性支持向量机利用，输入空间到特征空间的非线性映射 （核函数）将输入映射为特征向量

概念

Linear Support Vector Machine in Linearly Separable Case

线性可分支持向量机：硬间隔支持向量机，训练数据线性可分时， 通过硬间隔最大化策略学习

• 直观含义：不仅将正负实例分开，而且对于最难分的实例点 （离超平面最近的点），也有足够大的确信度将其分开，这样的 超平面对新实例预测能力较好

• Hard-margin Maximization：硬间隔最大化，最大化超平面 $(w,b)$关于线性可分训练数据集的两类样本集几何间隔

原始问题策略

• 约束最优化问题表述

  $$\begin{align} \max_{w,b} & \gamma & \\ s.t. & \frac {y_i} {\|w\|} (wx + b) \geq \gamma, i=1,2,\cdots,N \end{align}$$

• 考虑函数间隔、几何间隔关系得到问题

  • 目标、约束中使用函数间隔表示几何间隔
  • 就是普通等比缩放、分母移位，不用考虑太多
  $$\begin{align*} \max_{w,b} & \frac {\hat{\gamma}} {\|w\|} \\ s.t. & y_i(wx_i + b) \geq \hat{\gamma}, i=1,2,\cdots,N \end{align*}$$

• 而函数间隔$\hat{\gamma}$大小会随着超平面参数变化 成比例变化，其取值对问题求解无影响，所以可取 $\hat{\gamma}=1$带入，得到最优化问题

  $$\begin{align*} \min_{w,b} & \frac 1 2 {\|w\|}^2 \\ s.t. & y_i(wx_i + b) - 1 \geq 0, i=1,2,\cdots,N \end{align*}$$

  • $\max \frac 1 {|w|}$和 $\min \frac 1 2 {|w|}^2$等价

  • 这里确实没有通用变换技巧，因为这里的$\hat \gamma$ 是特殊的值，其取值与$w,b$相关，这是问题自然蕴含 ，可以视为还有以下一个依赖

  • 当然也可以直接证明两个问题等价：先证明最优解在等式 成立时取到，然后目标函数中1替换为等式左边

最大间隔分离平面存在性

• 若训练数据集T线性可分，则可将训练数据集中样本点完全 正确分开的最大间隔分离超平面存在且唯一

存在性

• 训练数据集线性可分，所以以上中最优化问题一定存在可行解
• 又目标函数又下界，则最优化问题必有解

  todo

• 又训练数据集中正、负类点都有，所以$(0,b)$必不是最优化 可行解

唯一性

• 若以上最优化问题存在两个最优解$(w_1^{},b_1^{})$、 $w_2^{},b_2^{}$

• 显然$|w_1^{}| = |w_2^{}| = c$， $(w=\frac {w_1^{}+w_2^{}} 2,b=\frac {b_1^{}+b_2^{}} 2)$ 使最优化问题的一个可行解，则有

  $$c \leq \|w\| \leq \frac 1 2 \|w_1^{*}\| + \frac 1 2 \|w_2^{*} = c$$

• 则有$|w|=\frac 1 2 |w_1^{}|+\frac 1 2 |w_2^{}|$ ，有$w_1^{} = \lambda w_2^{}, |\lambda|=1$

  • $\lambda = -1$，不是可行解，矛盾
  • $\lambda = 1$，则$w_1^{()} = w_2^{}$，两个最优解 写为$(w^{}, b_1^{})$、$(w^{}, b_2^{})$

• 设$x_1^{+}, x_1^{-}, x_2^{+}, x_2^{-}$分别为对应以上两组 超平面，使得约束取等号、正/负类别的样本点，则有

  $$\begin{align*} b_1^{*} & = -\frac 1 2 (w^{*} x_1^{+} + w^{*} x_1^{-}) \\ b_2^{*} & = -\frac 1 2 (w^{*} x_2^{+} + w^{*} x_2^{-}) \\ \end{align*}$$

  则有

  $$b_1^{*} - b_2^{*} = -\frac 1 2 [w^{*}(x_1^{+} - x_2^{+}) + w^{*} (x_1^{-} - x_2^{-})]$$

• 又因为以上支持向量的性质可得

  $$\begin{align*} w^{*}x_2^{+} + b_1^{*} & \geq 1 = w^{*}x_1^{+} + b_1^{*} \\ w^{*}x_1^{+} + b_2^{*} & \geq 1 = w^{*}x_2^{+} + b_2^{*} \end{align*}$$

  则有$w^{}(x_1^{+} - x_2^{+})=0$，同理有 $w^{}(x_1^{-} - x_2^{-})=0$

• 则$b_1^{} - b_2^{} = 0$

概念

Support Vector

支持向量：训练数据集中与超平面距离最近的样本点实例

• 在线性可分支持向量机中即为使得约束条件取等号成立的点
• 在决定分离超平面时，只有支持向量起作用，其他实例点不起 作用
• 支持向量一般很少，所以支持向量机由很少的“重要”训练样本 决定

间隔边界

间隔边界：超平面$wx + b = +/-1$

• 支持向量位于其上
• 两个间隔边界之间距离称为间隔$=\frac 2 {|w|}$

算法

• 输入：线性可分训练数据集T
• 输出：最大间隔分离超平面、分类决策函数

1. 构造并求解约束最优化问题

   $$\begin{align*} \min_{w,b} & \frac 1 2 {\|w\|}^2 \\ s.t. & y_i(wx_i + b) - 1 \geq 0, i=1,2,\cdots,N \end{align*}$$

   得到最优解$w^{}, b^{}$

2. 得到分离超平面

   $$w^{*}x + b^{*} = 0$$

   分类决策函数

   $$f(x) = sign(w^{*}x + b^{*})$$

多分类

• 1 vs n-1：对类$k=1,…,n$分别训练当前类对剩余类分类器

  • 分类器数据量有偏，可以在负类样本中进行抽样
  • 训练n个分类器

• 1 vs 1：对$k=1,…,n$类别两两训练分类器，预测时取各 分类器投票多数

  • 需要训练$\frac {n(n-1)} 2$给分类器

• DAG：对$k=1,…,n$类别两两训练分类器，根据预先设计的、 可以使用DAG表示的分类器预测顺序依次预测

  • 即排除法排除较为不可能类别
  • 一旦某次预测失误，之后分类器无法弥补
    • 但是错误率可控
    • 设计DAG时可以每次选择相差最大的类别优先判别

Dual Algorithm

对偶算法：求解对偶问题得到原始问题的最优解

• 对偶问题往往更容易求解
• 自然引入核函数，进而推广到非线性分类问题

对偶问题策略

• Lagrange函数如下

  $$L(w,b,\alpha) = \frac 1 2 \|w\|^2 - \sum_{i=1}^N \alpha_i y_i (wx_i + b) + \sum_{i=1}^N \alpha_i$$

  • $\alpha_i > 0$：Lagrange multiplier

• 根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题

  $$\max_{\alpha} \min_{w,b} L(w,b,\alpha)$$

• 求$\min_{w,b} L(w,b,\alpha)$，对拉格朗日函数求偏导置0

  $$\begin{align*} \triangledown_w L(w,b,\alpha) & = w - \sum_{i=1}^N \alpha_i y_i x_i = 0 \\ \triangledown_b L(w,b,\alpha) & = -\sum_{i=1}^N \alpha_i y_i = 0 \end{align*}$$

  解得

  $$\begin{align*} w = \sum_{i=1}^N \alpha_i y_i x_i \\ \sum_{i=1}^N \alpha_i y_i = 0 \end{align*}$$

• 将以上结果代理拉格朗日函数可得

  $$\begin{align*} L(w,b,\alpha) & = \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i x_j) - \sum_{i=1}^N \alpha_i y_i ((\sum_{j=1}^N \alpha_j y_j x_j)x_i + b) + \sum_{i=1}^N \alpha_i \\ & = -\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_i (x_i x_j) + \sum_{i=1}^N \alpha_i \end{align*}$$

• 以上函数对$\alpha$极大即为对偶问题，为方便改成极小

  $$\begin{align*} \min_{\alpha} & \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i x_j) - \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N \alpha_i y_i = 0, \\ & \alpha_i > 0, i = 1,2,\cdots,N \end{align*}$$

原始问题解

• 设$\alpha^{} = (\alpha_1^{}, \cdots, \alpha_N^{})$是 上述对偶优化问题的解，则存在$j \in [1, N]$使得 $\alpha_j^{} > 0$，且原始最优化问题解如下 $$\begin{align*} w^{*} & = \sum_{i=1}^N \alpha_i^{*} y_i x_i \\ b^{*} & = y_j - \sum_{i=1}^N \alpha_i^{*} y_i (x_i x_j) \end{align*}$$

• 由KKT条件成立有

  $$\begin{align*} & \triangledown_w L(w^{*}, b^{*}, \alpha^{*}) = w^{*} - \sum_{i=1}^N \alpha_i{*} y_i x_i = 0 \\ & \triangledown_b L(w^{*}, b^{*}, \alpha^{*}) = -\sum_{i=1}^N \alpha_i^{*} y_i = 0 \\ & \alpha^{*}(y_i (w^{*} x_i + b^{*}) - 1) = 0, i = 1,2,\cdots,N \\ & y_i(w^{*} x_i + b) - 1 \geq 0, i = 1,2,\cdots,N \\ & \alpha_i^{*} \geq 0, i = 1,2,\cdots,N \\ \end{align*}$$

• 可得

  $$w^{*} = \sum_i \alpha_i^{*} y_i x_i$$

• 其中至少有一个$\alpha_j > 0$，否则$w^{*}=0$不是原问题解 ，且有

  $$\begin{align*} y_j(w^{*} x_j + b^{*}) - 1 = 0 \end{align*}$$

  注意到$y_j \in {-1, +1}$，则有

  $$b^{*} = y_j - \sum_{i=1}^N \alpha_i^{*} y_i (x_i x_j)$$

分离超平面

• 则分离超平面为

  $$\sum_{i=1}^N \alpha_i^{*} y_i (x x_i) + b^{*} = 0$$

• 分类决策函数为

  $$f(x) = sgn(\sum_{i=1}^N \alpha_i^{*} y_i (x x_i) + b^{*})$$

  即分类决策函数只依赖输入$x$和训练样本的内积

支持向量

• 将对偶最优化问题中，训练数据集中对应$\alpha_i^{*} > 0$ 的样本点$(x_i, y_i)$称为支持向量

• 由KKT互补条件可知，对应$\alpha_i^{*} > 0$的实例$x_i$有 $$y_i(w^{*} x_i + b^{*}) - 1 = 0$$ 即$(x_i, y_i)$在间隔边界上，同原始问题中支持向量定义一致

算法

• 输入：线性可分数据集$T$
• 输出：分离超平面、分类决策函数

1. 构造并求解以上对偶约束最优化问题，求得最优解 $\alpha^{} = (\alpha_1^{},…,\alpha_N^{*})^T$

2. 依据以上公式求$w^{}$，选取$\alpha^{}$正分量 $\alpha_j^{} > 0$计算$b^{}$

3. 求出分类超平面、分类决策函数

Linear Support Vector Machine

线性支持向量机：训练数据线性不可分时，通过软间隔最大化策略 学习

• 训练集线性不可分通常是由于存在一些outlier

  • 这些特异点不能满足函数间隔大于等于1的约束条件
  • 将这些特异点除去后，剩下大部分样本点组成的集合是 线性可分的

• 对每个样本点$(x_i,y_i)$引入松弛变量$\xi_i \geq 0$

  • 使得函数间隔加上松弛变量大于等于1
  • 对每个松弛变量$\xi_i$，支付一个代价$\xi_i$

• soft-margin maximization：软间隔最大化，最大化样本点 几何间隔时，尽量减少误分类点数量

策略

线性不可分的线性支持向量机的学习变成如下凸二次规划，即 软间隔最大化

$$\begin{align*} \min_{w,b,\xi} & \frac 1 2 \|w\|^2 + C \sum_{i=1}^N \xi_i \\ s.t. & y_i(w x_i + b) \geq 1 - \xi_i, i=1,2,\cdots,N \\ & \xi_i \geq 0, i=1,2,\cdots,N \end{align*}$$

• $\xi_i$：松弛变量
• $C > 0$：惩罚参数，由应用问题决定，C越大对误分类惩罚越大

• 最小化目标函数包含两层含义

  • $\frac 1 2 |w|^2$尽量小，间隔尽量大
  • 误分类点个数尽量小

• 以上问题是凸二次规划问题，所以$(w,b,\xi)$的解是存在的

  • $w$解唯一
  • $b$解可能不唯一，存在一个区间

• 对给定的线性不可分训练数据集，通过求解以上凸二次规划问题 得到的分类超平面 $$w^{*} x + b^{*} = 0$$ 以及相应的分类决策函数 $$f(x) = sgn(w^{*} x + b^{*})$$ 称为线性支持向量机

• 线性支持向量包括线性可分支持向量机
• 现实中训练数据集往往线性不可分，线性支持向量机适用性更广

对偶问题策略

原始问题的对偶问题

$$\begin{align*} \min_\alpha & \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i x_j) - \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\ & 0 \leq \alpha_i \leq C, i=1,2,\cdots,N \end{align*}$$

• 类似线性可分支持向量机利用Lagrange对偶即可得

原始问题解

• 设$\alpha^{} = (\alpha_1^{}, \cdots, \alpha_N^{})$是 上述对偶优化问题的解，则存在$j \in [1, N]$使得 $0 < \alpha_j^{} < C$，且原始最优化问题解如下 $$\begin{align*} w^{*} & = \sum_{i=1}^N \alpha_i^{*} y_i x_i \\ b^{*} & = y_j - \sum_{i=1}^N \alpha_i^{*} y_i (x_i x_j) \end{align*}$$

• 类似线性可分支持向量机利用KKT条件即可得

分离超平面

• 则分离超平面为

  $$\sum_{i=1}^N \alpha_i^{*} y_i (x x_i) + b^{*} = 0$$

• 分类决策函数/线性支持向量机对偶形式

  $$f(x) = sgn(\sum_{i=1}^N \alpha_i^{*} y_i (x x_i) + b^{*})$$

  即分类决策函数只依赖输入$x$和训练样本的内积

支持向量

• 将对偶最优化问题中，训练数据集中对应$\alpha_i^{*} > 0$ 的样本点$x_i$称为（软间隔）支持向量

• $\alpha_i^{*} < C$：则$\xi_i = 0$，恰好落在间隔边界上
• $\alpha_i^{*} = C, 0 < \xi_i < 1$：间隔边界与分离超平面 之间
• $\alpha_i^{*} = C, \xi=1$：分离超平面上
• $\alpha_i^{*} = C, \xi>1$：分离超平面误分一侧

Hinge Loss

线性支持向量机策略还可以视为最小化以下目标函数

$$\sum_{i=1}^N [1-y_i(w x_i + b)]_{+} + \lambda \|w\|^2$$

• 第一项：经验风险，合页损失函数
• 第二项：正则化项

• $w$模越大，间隔越小，合页损失越小，所以用这个作为 正则化项是合理的

• 参见data_science/loss

等价证明

令

$$\xi_i = [1 - y_i(w x_i + b)]_{+}$$

• 则有$\xi_i \geq 0$

• 且

  $$\left \{ \begin{align*} & y_i(w x_i + b) = 1 - \xi_i, & y_i(w x_i + b) \leq 1 \\ & y_i(w x_i + b) > 1 - \xi_i = 1, & y_i(w x_i + b) > 1 \end{align*} \right.$$

  所以有

  $$y_i(w x_i + b) \geq 1 - \xi_i$$

• 则原问题两个约束条件均得到满足，此问题可写成

  $$\min_{w,b} \sum_{i=1}^N \xi_i + \lambda \|w\|^2$$

  取$\lambda = \frac 1 {2C}$，即同原问题

Non-Linear Support Vector Machine

非线性支持向量机

• 非线性问题：通过非线性模型才能很好进行分类的问题

  • 通过非线性变换$\phi(x)$，将输入空间映射到特征 空间（维数可能非常高）
  • 原空间中非线性可分问题在特征空间可能变得线性可分， 在特征空间中学习分类模型

• SVM求解非线性问题时

  • kernel trick：通过非线性变换将输入空间对应一个特征 空间，使得输入空间中超曲面对应于特征空间的超平面模型
  • 软间隔最大化策略：在特征空间中求解线性支持向量机

Kernal Trick

核技巧：线性SVM的对偶问题中，目标函数、决策函数均只涉及输入 实例、实例之间的内积

• 将内积使用核函数代替，等价进行复杂的非线性变换

• 映射函数是非线性函数时，学习的含有核函数的支持向量机 是非线性模型

• • 学习是隐式地在特征空间中进行的，不需要显式定义特征 空间、映射函数

• 参见data_science/ref/functions

对偶问题目标函数

$$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$$

原始问题解

分类决策函数

$$\begin{align*} f(x) & = sgn(\sum_{i=1}^{N_s} \alpha_i^{*} y_i \phi(x_i) \phi(x) + b^{*}) \\ & = sgn(\sum_{i=1}^{N_s} \alpha_i^{*} y_i K(x_i, x) + b^{*}) \end{align*}$$

算法

• 输入：训练数据集$T$
• 输出：分类决策函数

1. 选取适当的核函数$K(x,z)$、适当参数C，构造求解最优化问题

   $$\begin{align*} \min_\alpha & \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_1 \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\ & 0 \leq \alpha_i \leq C, i=1,2,...,N \end{align*}$$

   求得最优解 $\alpha^{} = (\alpha_1^{},\alpha_2^{},\cdots,\alpha_N^{})$

2. 选择$\alpha^{}$的一个正分量$0 < \alpha_j^{} < C$，计算

   $$b^{*} = y_j - \sum_{i=1}^N \alpha_i^{*} y_i K(x_i x_j)$$

3. 构造决策函数

• $K(x,z)$是正定核函数时，最优化问题是凸二次规划，有解

Sequential Minimal Optimization

序列最小最优化算法，主要解如下凸二次规划的对偶问题

$$\begin{align*} \min_\alpha & \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_1 \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\ & 0 \leq \alpha_i \leq C, i=1,2,...,N \end{align*}$$

• 凸二次规划有很多算法可以求得全局最优解，但是在训练样本 容量较大时，算法会很低效

思想

将原问题不断分解为子问题求解，进而求解原问题

• 如果所有变量的解都满足此优化问题的KKT条件，得到此最优化 问题的一个可能解

  • 对凸二次规划就是最优解，因为凸二次规划只有一个稳定点

• 否则选择两个变量，固定其他变量，构建一个二次规划

  • 目标是使得解符合KKT条件，但是因为等式约束的存在， 不可能单独改变一个变量而保持等式约束

  • 子问题有解析解，求解速度快

  • 二次规划问题关于两个变量的解会使得原始二次规划的目标 函数值变得更小，更接近原始二次规划的解 （这里SMO原始论文有证明，违反KKT条件的变量可以做到）

• 不失一般性，假设选择两个变量$\alpha_1, \alpha_2$，其他 变量$\alpha_i(i=3,4,…,N)$是固定的，则SMO最优化子问题

  $$\begin{align*} \min_{\alpha_1, \alpha_2} & W(\alpha_1, \alpha_2) = \frac 1 2 K_{11} \alpha_1^2 + \frac 1 2 K_{22} \alpha_2^2 + y_1 y_2 K_{12} \alpha_1 \alpha_2 - (\alpha_1 + \alpha_2) + y_1 \alpha_1 \sum_{i=3}^N y_i \alpha_i K_{i1} + y_2 \alpha_2 \sum_{i=1}^N y_i \alpha_i K{i2} \\ s.t. & \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^N y_i \alpha_i = \zeta \\ & 0 \leq \alpha_i \leq C, i=1,2 \end{align*}$$

  • $K_{ij} = K(x_i, x_j), i,j=1,2,\cdots,N$
  • $\zeta$：常数

两变量二次规划取值范围

• 由等式约束，$\alpha_1, \alpha_2$中仅一个自由变量， 不妨设为$\alpha_2$

  • 设初始可行解为$\alpha_1, \alpha_2$

  • 设最优解为$\alpha_1^{}, \alpha_2^{}$

  • 未经剪辑（不考虑约束条件而来得取值范围）最优解为 $\alpha_2^{**}$

• 由不等式约束，可以得到$\alpha_2$取值范围$[L, H]$

  • $y_1 = y_2 = +/-1$时

    $$\begin{align*} H & = \min \{C, \alpha_1 + \alpha_2 \} \\ L & = \max \{0, \alpha_2 + \alpha_1 - C \} \end{align*}$$

  • $y_1 \neq y_2$时

    $$\begin{align*} L & = \max \{0, \alpha_2 - \alpha_1 \} \\ L & = \min \{C, C + \alpha_2 - \alpha_1 \} \end{align*}$$

  • 以上取值范围第二项都是应用等式约束情况下，考虑 不等式约束

两变量二次规划求解

为叙述，记

$$\begin{align*} g(x) & = \sum_{i=1}^N \alpha_i y_i K(x_i, x) + b \\ E_j & = g(x_j) - y_j \\ & = (\sum_{i=1}^N \alpha_i y_i K(x_i, x_j)) - y_j \end{align*}$$

• $g(x)$：SVM预测函数（比分类器少了符号函数）（函数间隔）
• $E_j$：SVM对样本预测与真实值偏差

• 以上两变量二次规划问题，沿约束方向未经剪辑解是 $$\begin{align*} \alpha_2^{**} & = \alpha_2 + \frac {y_2 (E_1 - E_2)} \eta \\ \eta & = K_{11} + K_{22} - 2K_{12} \\ & = \|\phi(x_1) - \phi_(x_2)\|^2 \end{align*}$$ 剪辑后的最优解是 $$\begin{align*} \alpha_2^{*} & = \left \{ \begin{array}{l} H, & \alpha_2^{**} > H \\ \alpha_2^{**}, & L \leq \alpha_2^{**} \leq H \\ L, & \alpha_2^{*} < L \end{array} \right. \\ \alpha_1^{*} & = \alpha_1 + y_1 y_2 (\alpha_2 - \alpha_2^{*}) \end{align*}$$

• 记

  $$\begin{align*} v_i & = \sum_{j=3}^N \alpha_j y_j K(x_i, x_j) \\ & = g(x_i) - \sum_{j=1}^2 \alpha_j y_j K(x_i, x_j) - b i=1,2 \end{align*}$$

  由等式约束$\alpha_1 = (\zeta - y_2 \alpha_2) y_1$，均 带入目标函数有

  $$\begin{align*} W(\alpha_1, \alpha_2) = & \frac 1 2 K_{11} (\zeta - y_2 \alpha_2)^2 + \frac 1 2 K_{22} \alpha_2^2 + y_2 K_{12} (\zeta - y_2 \alpha_2) \alpha_2 - \\ & y_1 (\zeta - \alpha_2 y_2) - \alpha_2 + v_1 (\zeta - \alpha_2 y_2) + y_2 v_2 \alpha_2 \end{align*}$$

• 对$\alpha_2$求导置0可得

  $$\begin{align*} (K_{11} + K_{22} - 2K_{12}) \alpha_2 & = y_2 (y_2 - y_1 + \zeta K_{11} - \zeta K_{12} + v_1 + v_2) \\ & = y_2 [y_2 - y_1 + \zeta K_{11} - \zeta K_{12} + (g(x_1) - \sum_{j=1}^2 y_j \alpha_j K_{1j} - b) - (g(x_2) - \sum_{j=1}^2 y_j \alpha_j K_{2j} -b )] \end{align*}$$

  带入$\zeta = \alpha_1 y_1 + \alpha_2 y2$，可得

  $$\begin{align*} (K_11 + K_22 - 2K_{12}) \alpha_2^{**} & = y_2((K_{11} + K_{22} - 2K_{12}) \alpha_2 y_2 + y_2 - y_1 + g(x_1) - g(x_1)) \\ & = (K_11 + K_{22} - 2K_{12}) \alpha_2 + y_2 (E_1 - E_2) \end{align*}$$

变量选择

SMO算法每个子问题的两个优化变量，其中至少一个违反KKT条件

外层循环—首个变量选择

在训练样本中选择违反KKT条件最严重的样本点，将对应的变量作为 第一个变量$\alpha_1$

• 检查样本点是否满足KKT条件

  $$\begin{align*} \alpha_i = 0 \Leftrightarrow y_i g(x_i) \geq 1 \\ 0 < \alpha_i < C \Leftrightarrow y_i g(x_i) = 1 \\ \alpha_i = C \Leftrightarrow y_i g(x_i) \leq 1 \end{align*}$$

• 检验过程中

  • 首先遍历所有满足条件的$0 < \alpha_i < C$样本点，即 在间隔边界上的支持向量点

  • 若没有找到违背KKT条件的样本点，则遍历整个训练集

内层循环

第二个变量$\alpha_2$选择标准是其自身有足够大的变化，以加快 计算速度

• 由以上推导知，$\alpha_2^{*}$取值依赖于$|E_1 - E_2|$， 所以可以选择$\alpha_2$使其对应的$|E_1 - E_2|$最大

  • $\alpha_1$已经确定，$E_1$已经确定
  • $E_1 > 0$：选最小的$E_2$
  • $E_1 < 0$：选最大的$E_2$

• 但以上方法可能不能使得目标函数值有足够下降，采用以下 启发式规则继续选择$\alpha_2$

  • 遍历间隔边界上的点
  • 遍历整个训练数据集
  • 放弃$\alpha_1$

更新阈值

• $0< \alpha_1^{*} < C$时，由KKT条件可知

  $$\sum_{i=1}^N \alpha_i y_i K_{i1} + b = y_1$$

  • 则有

    $$b_1^{*} = y_1 - \sum_{i=3}^N \alpha_i y_i K_{i1} - \alpha_1^{*} y_1 K_{11} - \alpha_2^{*} y_2 K_{21}$$

  • 将$E_1$定义式带入有

    $$b_1^{*} = -E_1 - y_1 K_{11} (\alpha_1^{*} - \alpha_1) - y_2 K_{21} (\alpha_2^{*} - \alpha_2) + b$$

• 类似的$0 < \alpha_2^{*} < C$时

  $$b_2^{*} = -E_2 - y_2 K_{22} (\alpha_2^{*} - \alpha_2) - y_1 K_{12} (\alpha_1^{*} - \alpha_1) + b$$

• 若

  • $0 < \alpha_1^{}, \alpha_2^{} < C$，则 $b_1{} = b_2^{}$

  • $\alpha_1^{}, $\alpha_2^{}$均为0、C，则 $[b_1^{}, b_2^{}]$中均为符合KKT条件的阈值，选择 中点作为新阈值$b^{*}$

• 同时使用新阈值更新所有的$E_i$值

  $$E_i^{*} = \sum_S y_j \alpha_j K(x_i, x_j) + b^{*} - y_i$$

  • $S$：所有支持向量的集合

算法

• 输入：训练数据集$T$，精度$\epsilon$
• 输出：近似解$\hat \alpha$

1. 初值$\alpha^{(0)}$，置k=0

2. 选取优化变量$\alpha_1^{(k)}, \alpha_2^{(k)}$，解析求解 两变量最优化问题得$\alpha_1^{(k+1)}, \alpha_2^{(k+2)}$， 更新$\alpha^{(k+1)}$

3. 若在精度范围内满足停机条件（KKT条件）

   $$\begin{align*} & \sum_{i=1}^N \alpha_i y_i = 0 \\ & 0 \leq \alpha_i \leq C, i=1,2,\cdots,N \\ & y_i g(x_i) = \left \{ \begin{array}{l} \geq 1, & \{x_i | \alpha_i = 0\} \\ = 1, & \{x_i | 0 < \alpha_i < C\} \\ \leq 1, & \{x_i | \alpha_i = C\} \end{array} \right. \\ & g(x_i) = \sum_{j=1}^N \alpha_j y_j K(x_j, x_i) + b \end{align*}$$

   则转4，否则置k=k+1，转2

4. 取$\hat \alpha = \alpha^{(k+1)}$