Machine Learning笔记(4)

Geometric margin and functional margin

Functional margin

一个超平面 $w^T x + b = 0$ 关于点 $(x^i, y^i)$ 的函数间隔是
$\hat\delta^i = y^i (w^T x^i + b)$
关于训练集S的函数间隔是
$\delta = \underset{i}{\mathrm{min}}\; \hat\delta^i$

Geometric margin

一个超平面 $w^T x + b = 0$ 关于点 $(x^i, y^i)$ 的几何间隔是
$\delta^i = y^i \left[\left(\frac{w}{\lVert w \rVert} \right)^T x^i + \frac{b}{\lVert w \rVert}\right]$
$w^T (x^i - \lVert \delta^i \rVert \frac{w}{\lVert w \rVert}) + b = 0$
关于集合S的几何间隔是
$\delta = \underset{i}{\mathrm{min}}\;\delta^i$
也就是说 $\delta^i = \frac{\hat\delta^i}{\lVert w \rVert}$
几何间隔不随着 $\lVert w \rVert$ 的变化而变化

Max Margin Classifier

目标:
假设数据线性可分，选取适当的线性分类面的原则：最大化几何间隔(当 $\lVert w \rVert$ 为1时，等于函数间隔)
$\underset{\delta,w,b}{\mathrm{max}}\;\delta$
s.t. $y^i(w^T x^i + b) \ge \delta \quad \lVert w \rVert = 1$
or
$\underset{\hat\delta,w,b}{\mathrm{max}}\;\frac{\hat\delta}{\lVert w \rVert}$
s.t. $y^i(w^T x^i + b) \ge \hat\delta$
or令函数间隔放缩到1(要求线性可分)，那么所求即为
$\underset{w,b}{\mathrm{min}}\;{\lVert w \rVert}^2$
s.t. $y^i(w^T x^i + b) \ge 1$
求解这个问题令
$g_i(w,b) = - y^i(w^T x^i + b) + 1 \le 0$
由KKT对偶互补条件得
$\alpha_i \gt 0 \Rightarrow g_i(w^* ,b) = 0 \Rightarrow \hat\delta^i = 1$
此时 $g_i(w,b)$ 是被激活的constrains, 对应的向量为support vectors
对应的拉格朗日函数为
$L(w,b,\alpha) = \frac{1}{2} {\lVert w \rVert}^2 - \sum_{i=1}^m \alpha_i(y^i(w^T x^i + b) - 1)$
dual problem
$\underset{\alpha \; s.t. \alpha_i \ge 0}{\mathrm{max}}\;O_D(\alpha)$
$O_D(\alpha) = \underset{w,b}{\mathrm{min}}\;L(w, b, \alpha)$
$\nabla_w L(w,b,\alpha) = w - \sum_{i=1}^m \alpha_i y^i x^i = 0$
$\nabla_b L(w,b,\alpha) = - \sum_{i=1}^m y^i \alpha_i = 0$
把w代入L得到
$W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i,j=1}^m y^i y^j \alpha_i \alpha_j \langle x^i,x^j \rangle - \sum_{i=1}^m \alpha_i y^i b \\ = \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i,j=1}^m y^i y^j \alpha_i \alpha_j \langle x^i,x^j \rangle$
那么对偶问题即为
$\underset{\alpha}{\mathrm{max}}\;W(\alpha)$
s.t.
$\alpha_i \ge 0 \\ \sum_{i}y^i \alpha_i = 0$
也就是说为了最大化 $\Theta_D(\alpha) (\alpha \ge 0)$ , 如果 $\sum_{i} y^i \alpha_i = 0$ ,那么 $\Theta_D(\alpha) = W(\alpha)$ ,否则 $\Theta_D(\alpha) = -\infty$ 由对偶问题求出 $\alpha$ ,进一步求出 $w$ 和 $b$
其hypothese
$h_{w,b} = g(w^T x + b) = g(\sum_{i=1}^m \alpha_i y^i \langle x^i, x \rangle + b)$

Kernel Trick

由上我们只需知道 $\langle x^i,x^j \rangle$ 和 $\langle x^i, x \rangle$ 就能得到一个最优几何间隔分类器并进行预测
当数据线性不可分，把数据用 $\phi$ 变换到高维空间使其在高维空间中线性可分，那么只需代换为 $\langle \phi(x^i),\; \phi(x^j)\rangle$
定义核函数 $K(x^i, x^j) = \langle \phi(x^i),\; \phi(x^j)\rangle$

常见的核函数

$K(x,z) = (x^Tz + c)^d$
$K(x,z) = exp(- \frac{\lVert x-z \rVert}{2 \sigma^2})$

Mercer定理

合法核函数的充要条件
假设 $k$ 是核函数, 给定集合 $\{x^1, x^2, \ldots, x^m\}$ 令 $K = \mathbb{R}^{m \times m} \quad K_{ij} = k(x^i, x^j)$ ,那么对于任意 $z \in \mathbb{R}^m$ ,有 $z^T K z = \sum_{i}\sum_{j} z_i \phi(x^i)^T \phi(x^j) z_j \\ = \sum_{i}\sum_{j} z_i \sum_{l}{(\phi(x^i))}_l {(\phi(x^j))}_l \;z_j \\ = \sum_{l}\sum_{i}\sum_{j}z_i{(\phi(x^i))}_l {(\phi(x^j))}_l \;z_j \\ = \sum_{l}(\sum_{i}\;z_i {\phi(x^i)}_l)^2 \ge 0$
即 $K$ 是对称半正定矩阵

软间隔分类器

当

数据线性不可分或者映射到高维依然线性不可分
数据中线性可分，但因为噪声点使得最大间隔分类器的结果不合理

我们引入软间隔分类器，对分类错误的点加入惩罚，问题变为:
$\underset{w,b,\xi}{\mathrm{min}}\;\frac{1}{2} {\lVert w \rVert}^2 + C \sum_{i=1}^m \xi_i$
s.t.
$y^i(w^T x^i + b) \ge 1 - \xi_i \\ \xi_i \ge 0$
Larangian:
$L(w,b,\xi,\alpha,r) = \frac{1}{2}{\lVert w \rVert}^2 + C\sum_{i=1}^m \xi_i - \sum_{i=1}^m \alpha_i(y^i(w^T x^i + b) - 1 + \xi_i) - \sum_{i=1}^m r_i\xi_i$
dual problem:
$\underset{\alpha_i \ge 0 \; r_i \ge 0}{\mathrm{max}}\underset{w,b,\xi}{min}\;L(w,b,\xi,\alpha,r)$
由KKT条件得
$\nabla_w L = 0 \Rightarrow w = \sum_{i}\alpha_i y^i x^i$
$\nabla_b L = 0 \Rightarrow \sum_{i} y^i \alpha_i = 0$
$\nabla_{\xi_i} L = 0 \Rightarrow \alpha_i + r_i = C$
代入整理得
$\underset{C \ge \alpha_i \ge 0 \; \sum y^i \alpha_i = 0}{\mathrm{max}}\;W(\alpha) \\ W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i}\sum_{j}y^i y^j \alpha_i \alpha_j \langle x^i,x^j \rangle$
由KKT对偶互补条件得
$\alpha_i (1-\xi_i-y^i (w^Tx^i + b)) = 0 \\ r_i \xi_i = (C - \alpha_i) \xi_i = 0$ 那么根据 $\alpha_i$ 的取值我们可以将数据点分为三种:

non-SV: $\alpha_i = 0 \Rightarrow \xi_i = 0 \Rightarrow y^i(w^T x^i + b) \ge 1$ 没有违反边界
bounded-SV: $\alpha_i = C \Rightarrow y^i(w^T x^i + b) = 1-\xi_i \Rightarrow y^i(w^T x^i + b) \le 1$ 在边界上或者边界内或者违反了边界
free-SV: $C \gt \alpha_i \gt 0 \Rightarrow y^i(w^T x^i + b) = 1$ 在边界上

SMO

为了求解对偶问题，采用固定其他参数，在约束条件下优化剩下两个参数，迭代求解。

Larangian Duality

Dual problem

假设原始问题p是
$\underset{w}{\mathrm{min}}\;f(w)$
s.t.
$g_i(w) \le 0 \qquad i = 1, \ldots, k \\ h_i(w) = 0 \qquad i = 1, \ldots, l$
其目标函数最优值为 $p^*$
Larangian:
$L(\omega, \alpha, \beta) = f(w) + \sum_{i=1}^k \alpha_i g_i(w) + \sum_{i=1}^l \beta_i h_i(w)$
我们定义
$\Theta_p(\omega) = \underset{\alpha, \beta \; s.t.\alpha_i \ge 0}{\mathrm{max}}\;L(\omega, \alpha, \beta)$
那么
$p^* = \underset{w}{\mathrm{min}}\underset{\alpha,\beta\;s.t.\alpha_i \ge 0}{\mathrm{max}}\;L(\omega, \alpha, \beta)$

定义
$\Theta_D (\alpha, \beta) = \underset{w}{\mathrm{min}}\;L(\omega, \alpha, \beta)$
那么原始问题p的对偶问题d为
$\underset{\alpha, \beta \; s.t.\alpha_i \ge 0}{\mathrm{max}}\;\Theta_D (\alpha, \beta)$
目标函数最优值为 $d^*$
$d^* = \underset{\alpha, \beta \; s.t.\alpha_i \ge 0}{\mathrm{max}}\underset{w}{\mathrm{min}}\;L(\omega, \alpha, \beta)$
定理: 若原始问题和对偶问题都有最优值，那么 $d^* \le p^*$
推论: 设 $\omega^*$ 和 $\alpha^* \; \beta^*$ 分别是原始问题和对偶问题的可行解，如果 $d^* = p^*$ ，那么 $\omega^*$ 和 $\alpha^* \; \beta^*$ 都是原始问题和对偶问题的最优解。

KKT condition

假设 $f \;$ 为convex函数， $h_i$ 是仿射函数( $h_i(w) = a_i^T w + b$ )， $g_i$ 严格feasible?，那么存在 $w^* \; \alpha^* \; \beta^*$ 使得 $w^*$ 和 $\alpha^* \; \beta^*$ 分别是原始问题和对偶问题的最优解的充要条件为
$\nabla_{\omega}L(\omega^* ,\alpha^*,\beta^* ) = 0$
$\nabla_{\alpha}L(\omega^* ,\alpha^*,\beta^* ) = 0$
$\nabla_{\beta}L(\omega^* ,\alpha^*,\beta^* ) = 0$
$\alpha_i ^* g_i(w^* ) = 0$
$\alpha_i ^* \ge 0$
$g_i(w^* ) \le 0$
$h_i(w^* ) = 0$

Classifier