分类 默认分类 下的文章

迭代优化算法

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

这些算法本身是用来求解方程解的,不过不难想到可以用他们来计算极值:求解导数为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类拟牛顿法。

拉格朗日对偶性

导言

拉格朗日对偶性尝尝用于带约束的最优化问题。这个原理的简化版本在高中数学中就出现过,当时称作拉格朗日乘数法。先回顾一下拉格朗日乘数法的基本形式:
$$
\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$。

《统计学习方法》读书笔记2:感知机

  1. 感知机(perceptron)的输入空间是$ \mathcal{X}\subseteq\mathbf{R}^n $,输出空间是 $ \mathcal{Y} = \lbrace +1, -1 \rbrace $,输入空间到输出空间的函数是 $$ f(x) = \rm{sign}(w \cdot x + b) $$ 其中,sign是符号函数

$$ \rm{sign}(x) =
\begin{cases}
+1, & x \geqslant 0\newline
-1, & x < 0
\end{cases}
$$

  1. 如果存在一个超平面可以将数据的正类负类分开,那么数据被称为线性可分的。
  2. 感知机只能处理线性可分的数据。
  3. 感知机的损失函数,是所有错误分类的点到超平面的距离之和
    $$
    -\frac{1}{\Vert w \Vert}\sum_{x_i \in M}y_i(w \cdot x_i + b)
    $$
    因为 $ \frac{1}{\Vert w \Vert} $ 是常数,所以可以忽略掉它得到最终的损失函数
    $$
    L(w,b) = - \sum_{ x \in M }y_i(w \cdot x_i + b)
    $$
    使用此函数而不是误分类数作为代价函数的好处是,这个函数可导,便于计算。
  4. 感知机学习算法的原始形式
    1. 选取初值 $ w_0 $, $ b_0 $
    2. 在训练集中选取数据 $ ( x_i , y_i) $
    3. 如果 $ y_i(w \cdot x_i + b) \leqslant 0 $
      $ w \leftarrow w + \eta y_i x_i $
      $ b \leftarrow b + \eta y_i $
    4. 转至2,直至训练集中没有误分类点
  5. 可以证明,算法是收敛的,也就是经过有限次,一定能将线性可分的数据完全正确分类。但是解唯一。证明方法留待以后看。
  6. 感知机存在一个对偶解法,使用对偶解法的原因可以查看这个知乎帖子
  7. 感知机模型的对偶解法还需要仔细理解,以后补充。

Debug手记:VIM在mac OS High Sierra上出现“Image not found”问题

问题描述

将macOS更新至High Sierra之后,VIM出现故障,启动时缺少必要动态链接库(Image not found)。

解决方案

第一时间想到的解决方案是,使用brew upgrade更新。然而却出现了找不到Python.h的问题。
接下来使用brew doctor命令,检查报出的所有Warning。发现有一条提示至关重要,大意是如果环境变量$PATH包含了Anaconda的路径,有可能导致某些包编译时break。那么解决问题的方案就变得非常明朗:将$PATH中Anaconda相关的内容暂时移除。再一次使用brew upgrade后,所有问题成功解决。

LANG="C"?

不知道为什么,安装好neovim之后,UI显示的都是日文。。。
nvim_error.png
经过一番查找,在看到了github上贴的一个issue
打开自己系统查看了一下:

$ locale
LANG=
LC_COLLATE="C"
LC_CTYPE="UTF-8"
LC_MESSAGES="C"
LC_MONETARY="C"
LC_NUMERIC="C"
LC_TIME="C"
LC_ALL=

试着加了一句:

$ export LANG=C
$ locale
LANG="C"
LC_COLLATE="C"
LC_CTYPE="UTF-8"
LC_MESSAGES="C"
LC_MONETARY="C"
LC_NUMERIC="C"
LC_TIME="C"
LC_ALL=

再次启动neovim
nvim.png
居然真的好了。。。
所以LANG=C究竟是个啥。。。

LANG=C是指定系统编码,C的意思是C语言,也就是最基本的ASCII编码。