迭代优化算法

机器学习训练过程和各种迭代优化算法密不可分,像梯度下降法、牛顿法等迭代式子随手都能写出来。但是对它们背后的数学原理却渐渐淡忘了。所以写一篇学习笔记,重新整理一下。

这些算法本身是用来求解方程解的,不过不难想到可以用他们来计算极值:求解导数为0的点。下面的内容首先从求解方程
$$ f(x)=0 $$开始说起。

基础

不动点迭代法

由于我本科学习的是计算数学,其中有数值计算这门课,所以在接触到机器学习之前就对牛顿法之类不陌生。为了将逻辑衔接的更紧密,首先就从不动点迭代法开始说起吧。
不动点迭代过程:

  1. 首先将方程改写成
    $$
    x = \phi(x)
    $$
    如果 $ \dot x $满足 $ f(\dot x)=0 $,那么显然有 $ \dot x = \phi(\dot x) $,这个 $ \dot x $就称作不动点,同时也可以看出,不动点就是方程的解。

  2. 选取一个解附近的点 $ x_0 $ 带入
    $$
    x_1 = \phi(x_0)
    $$

  3. 执行迭代过程
    $$
    x_{k+1} = \phi(x_{k})
    $$

  4. 当 $ x_{k+1} - x_{k} < \epsilon $时停止迭代,其中 $ \epsilon $ 为定义的精度阈值。

Newton-Raphson方法(牛顿法、牛顿切线法)

用一阶泰勒展开式近似 $ f(x) $,有
$$
f(x) \approx f(x_0) + f'(x_0)(x-x_0)
$$
方程 $ f(x) $ 在点 $ x_0 $附近可以近似表示为
$$
f(x_0) + f'(x_0)(x-x_0) = 0
$$
然后进行迭代
1.令
$$
x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}
$$
2.迭代
$$
x_{k+1} = x_0 - \frac{f(x_k)}{f'(x_k)}
$$
3.当 $ x_{k+1} - x_k < \epsilon $时终止,其中 $\epsilon$ 为定义的精度阈值。
个人理解,其实无论是梯度下降法还是牛顿法,本质思想都是不动点迭代,不同的是这个不动点针对的是函数本身还是函数的导数。

引申

用牛顿法求解函数极值点

有了上面的基础内容支撑,不难想出一个求解函数极值的方法。因为导数为0是函数极值的必要条件,所以,我们可以用牛顿法求解$ f'(x) $的零点。
首先考虑 $ f(x) $在 $ x_k $点的二阶泰勒展开式
$$
f(x) = f(x_k) + f'(x_k)(x-x_k) + \frac{1}{2}f''(x_0)(x-x_0)^2
$$
两边取导数,这一步计算要细心,记住$f(x)$是函数,$f(x_0)$是数,求导的时候不要乱套。
$$
f'(x) = f'(x_k) + f''(x_k)(x-x_k)
$$
假如在$x_{k+1}$点可以取得极小值,那么有$f'(x_{k+1}) = 0$。对于上式,两边带入$x_{k+1}$,有
$$
f'(x_{k+1}) = 0 = f'(x_k) + f''(x_k)(x_{k+1} - x_k)
$$
整理一下得到递推式
$$
x_{k+1} = x_k - \frac{f'(x_{k+1})}{f''(x_k)}
$$

推广

在机器学习中,我们的输入往往不是标量,而是多组特征组成的向量。在这一节,我们将上面的内容推广到多元函数上。

牛顿法

仿照着一元函数的牛顿法推导过程,先在 $ x_k $上进行泰勒展开。其中,$ g_k $是在$ x_k $点的梯度向量,$ H_k $是在 $ x_k $点的海塞矩阵。
$$
f(x) = f(x_k) + g_k^T(x - x_k) + \frac{1}{2}(x - x_k)^T H_k (x - x_k)
$$
两边求梯度
$$
\nabla f(x) = g_k + H_k(x - x_k)
$$
若在 $ x_{k+1} $ 点取极值,两边带入 $ x_{k+1} $得到
$$
\nabla f(x_{k+1}) = g_{k+1} = 0 = g_k + H_k(x_{k+1} - x_k)
$$
整理一下就得到了迭代共识
$$
x_{k+1} = x_k - H_k^{-1}g_k
$$
在这里可以看出牛顿法推广到多元函数之后的一个缺陷:求解海塞矩阵的逆矩阵很复杂。为了解决这个问题,拟牛顿法被提出了。

拟牛顿法

拟牛顿法的核心思路就是用一个矩阵 $ G_k $ 替代海塞矩阵的逆 $ H_k^{-1} $
在 $ x_{k+1} $ 不为极值点的时候,满足等式
$$
g_{k+1} = g_k + H_k(x_{k+1} - x_k)
$$
记 $ y_k = g_{k+1} - g_k $,$ \delta_k = x_{k+1} - x_k $
那么有
$$
y_k = H_k \delta_k
$$

$$
H_k^{-1}y_k = \delta_k
$$
这两个式子称作拟牛顿条件
简而言之,只要保证拟牛顿条件成立,算法依然是“正确”的(具体来说,可以保证牛顿法的搜索方向正确,证明略去)。
进一步地,拟牛顿条件可以记作
$$
G_{k+1}y_k = \delta_k
$$
而更新 $ G_k $ 的形式是
$$
G_{k+1} = G_k + \Delta G_k
$$
最后,问题就只剩下一个:如何构造符合拟牛顿条件的 $ G_k $。对于这一步有很多种具体实现方法,常用的就是Broyden类拟牛顿法。

《统计学习方法》读书笔记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)和拟牛顿法。