|
|
机器学习与优化
引用大佬Pedro Domingos的说法：机器学习其实就是由模型的表示，优化和模型评估三部分组成。将一个实际问题转化为待求解的模型，利用优化算法求解模型，利用验证或测试数据评估模型，循环这三个步骤直到得到满意的模型。
因此，优化算法在机器学习中起着一个承上启下的作用！
一般机器学习中涉及的优化命题可以表示为：
\min_{x\in \mathbb{R}^n} \frac{1}{m}\sum_{i=1}^mf_i(x)+\lambda R(x)
比如：
f_i(x)=(x^Tw_i-y_i)^2,R(x)=0
f_i(x)=(x^Tw_i-y_i)^2,R(x)=||x||^2
f_i(x)=(x^Tw_i-y_i)^2,R(x)=||x||_1
f_i(x)=max(0,1-y_ix^Tw_i),R(x)=||x||^2
f_i(x)=\log(1+exp(-y_ix^Tw_i)),R(x)=||x||^2
还有等等等等机器学习算法也是类似的。
优化算法基础
优化算法的阶次
所谓优化算法的阶次其实指的是优化过程利用的是
- 目标函数本身（零阶） f(x_k)
- 梯度信息（一阶） \nabla f(x_k)
- hessian信息（二阶） \nabla^2 f(x_k)
中的哪些信息。
如果函数形式未知、梯度难以求或不存在的时候常常采用零阶优化算法；在机器学习领域中一般一阶算法使用较多，二阶算法可能收敛更快但计算花费也更大。 优化算法的常见组成
在理解梯度下降法之前，再给大家复习一下几个非常容易混淆的概念：导数是一元函数的变化率（斜率）。如果是多元函数呢？则为偏导数。偏导数是多元函数“退化”成一元函数时的导数，这里“退化”的意思是固定其他变量的值，只保留一个变量，依次保留每个变量，则 N 元函数有 N 个偏导数。如果是方向不是沿着坐标轴方向，而是任意方向呢？则为方向导数。换句话说，偏导数为坐标轴方向上的方向导数，其他方向的方向导数为偏导数的合成。而偏导数构成的向量就称为梯度。
梯度方向是函数增长速度最快的方向，那么梯度的反方向就是函数减小最快的方向。因此，如果想要计算函数的最小值，就可以用梯度下降的思想来做。假设目标函数的梯度为 \nabla f(x) ，当前点的位置为 x_k ，则下一个点的选择与当前点的位置和它的梯度相关
x_{k+1}=x_k-\alpha_k \times \nabla f(x_k)
其中 \alpha_k 为学习率，可以随着每次迭代改变。（就拓展出了许多相关的算法AdaGrad、RMSProp、Adam等）
当目标函数存在不可微部分，常会采用近端梯度下降法。比如 f(x)=g(x)+h(x) ，其中 g(x) 是凸的且可微， h(x) 是凸的但是不可微或者局部不可微。由于 h(x) 不可微，我们不能直接用梯度下降法来寻优（PS：次梯度算法可以，就是慢了点），因此近端算法考虑的是将 h(x) 进行近端映射。
函数 h(x) 的近端映射可以定义为
prox_h(x)=\arg\min_{u} (h(u)+\frac{1}{2}||u-x||_2^2)
拿个机器学习中常见的 l_1 范数给大家举个例子， h(x)=||x||_1=\sum_i |x_{i}| （一范数就是各元素绝对值之和），对应的近端映射表示为
prox_h(x)=\arg\min_{u} (||u||_1+\frac{1}{2}||u-x||_2^2)=\arg\min_{u} (\sum_{i} |u_i| +\frac{1}{2} \sum_i (u_i-x_i)^2)
这个优化问题是可分解的！也就是对每一个维度求最小值
\min_{u_i} (|u_i|+\frac{1}{2}(u_i-x_i)^2)
对 u_i 的正负进行分类讨论，然后利用一阶最优条件（求导令导数为零）可得
prox_f(x)_i=\left\{\begin{array}{ll} x_{i}-1 & \text { if } x_{i} \geq 1 \\ 0 & \text { if }\left|x_{i}\right| \leq 1 \\ x_{i}+1 & \text { if } x_{i} \leq-1 \end{array}\right.
这通常也被称作软阈值（soft thresholding）。
因此近端梯度算法也就是
x_{k+1}=prox_{\alpha_k h} (x_k - \alpha_k \nabla g(x_k))
在求解一个优化命题时，如果其对偶形式便于求解，常常可以通过求解对偶问题来避免直接对原问题进行求解。比如机器学习中典型的SVM就涉及到对偶理论，以及拉格朗日乘子法、KKT条件等概念。首先简单通俗地说说这几个概念是干嘛的
- 对偶理论：对偶也就是孪生双胞胎，一个优化命题也就有其对应的兄弟优化命题。
- 拉格朗日函数：将原本优化命题的目标函数和约束整合成一个函数。
- KKT条件：函数的最优值满足的性质。
如果原问题是凸问题，则KKT条件为充要条件，也就是说满足KKT条件的点也就是原问题和对偶问题的最优解，那就能够在满足KKT条件下用求解对偶问题来替代求解原问题。（具体推导和细节就不展开了，下次可以单独写一篇）
当遇到大规模问题时，如果使用梯度下降法(批量梯度下降法)，那么每次迭代过程中都要对n个样本进行求梯度，所以开销非常大，随机梯度下降的思想就是随机采样一个样本来更新参数，那么计算开销就从\mathcal{O}{(n)}下降到\mathcal{O}{(1)}。
无约束问题的典型算法
上面提到过了就不重复了。 x_{k+1}=x_k-\alpha_k \times \nabla f(x_k) \tag{1}
梯度下降法可能存在的一个问题是为了收敛到解附近,同样的迭代方向可能走了不止一次（导致收敛慢）。共轭梯度就可以理解为选择一系列线性无关的方向去求得最优解。因此共轭梯度法把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜素，求出目标函数的极小点。
方向的构造方法为：
d_{k+1}=-\nabla f(x_{k+1}) + \beta_k d_k
其中当初始化的时候相当于梯度下降法（因为初始时刻只有梯度方向）。这里未知项是这个系数 \beta_k ，它的计算公式为
\beta_k = \frac{||\nabla f(x_{k+1})||^2}{||\nabla f(x_{k})||^2}
有了搜索方向，那么每次次迭代为
x_{k+1}=x_k + \alpha_k \times d_k\tag{2}
在说拟牛顿法前先简单介绍一下牛顿法，牛顿法最初是为了求解方程的根而推导出来的公式。它的主要思想是基于当前位置的切线来确定下一次的位置。比如要求 f(x)=0 的解，可以迭代求解
x_{k+1}=x_k - \frac{f(x_k)}{\nabla f(x_k)} \tag{3}
如果对应到求解优化命题，我们要使得 f(x) 取最小值，也就是函数的一阶导数为零 f'(x)=0 ，带入牛顿法求根公式就是
x_{k+1}=x_k - \frac{ \nabla f(x_k)}{\nabla^2 f(x_k)} \tag{4}
由于牛顿法每次都要计算二阶导数（Hessian矩阵）的逆，计算量太大了，因此有了拟牛顿法。简单的说，拟牛顿法其实就是用近似Hessian矩阵来进行迭代。
比如说令 H_k =[\nabla^2 f(x_k)]^{-1} ，再利用拟牛顿条件（对一阶导数进行泰勒展开）对近似矩阵进行修正就可以避免Hessian矩阵的求逆了。因此每次迭代为
x_{k+1}= x_k - \alpha_k H_k \nabla f(x_k) \tag{5}
在实际应用当中，使用最为广泛的拟牛顿法应该是L-BFGS算法了。
上面提到过了就不重复了。 x_{k+1}=prox_{\alpha_k h} (x_k - \alpha_k \nabla g(x_k)) \tag{6}
约束问题的经典算法
- 投影梯度下降法（Projected gradient descent）
看名字可以知道这个方法的思想其实就是梯度下降再加上投影操作来满足约束。可以理解为是一个两阶段的算法，
第一阶段先进行梯度下降
\hat{x}_{k+1}=x_k-\alpha_k \times \nabla f(x_k) \tag{7}
第二阶段进行投影
x_{k+1} = \arg\min_{x \in \mathcal{X}}||x-\hat{x}_{k+1}||^2 \tag{8}
也就是说在约束范围内找一个与无约束条件下最近的解，或者说将无约束解投影到约束范围内。
罚函数法的思想也可以从它的名字进行解释，其实就是将违反约束的代价放入目标函数中，从而把约束问题转化为无约束问题。转化后的无约束问题为
\min_x f(x)+\lambda P(x) \tag{9}
其中 P 是连续函数，且对于任意 x\in \mathbb{R}^n 罚函数非负，当 x 满足约束，即 x\in \mathcal{X} 时 P(x)=0 。
这个算法的思想和它的名字就不好联系上了，基本思想是将目标函数作线性近似，
f(x)=f(x_k) + \nabla f(x_k) (x-x_k) \tag{10}
通过求解线性规划
g_k = \arg\min_{g\in \mathcal{X}} \nabla f(x_k)^Tg \tag{11}
求得可行下降方向
d_k = g_k - x_k \tag{12}
因此每次迭代的公式为
x_{k+1}=x_k + \alpha_k d_k = (1-\alpha_k)x_k + \alpha_k g_k \tag{13}
ADMM的思想是以先分解再结合的形式求解问题，即先把原问题分解成若干个相对原问题较简单的子问题，再把子问题的解结合起来得到原问题的全局解。主要针对的问题是可分块优化命题，如
\min_{x,y} f(x) + g(y), \quad s.t.\quad A(x)+B(y)=c \tag{14}
写出其增广拉格朗日函数
\mathcal{L}(x,y,\lambda) = f(x) + g(y)+<\lambda,A(x)+B(y)-c>+\frac{\beta}{2}||A(x)+B(y)-c||^2 \tag{15}
用交替方法（只优化一个变量，固定其他变量）的方式进行优化，即
x_{k+1}=\arg\min_x \mathcal{L}(x,y_k,\lambda_k) \\ y_{k+1}=\arg\min_y \mathcal{L}(x_{k+1},y,\lambda_k) \\ \lambda_{k+1}= \lambda_k +\beta(A(x_{k+1})+B(y_{k+1})-c) \tag{16}
坐标上升法的思想和ADMM有点点类似的地方，就是在每次优化时只优化一个或者一部分变量，然后固定其他变量，即
x_i^{k+1}=\arg\min_{x\in \mathcal{X}_i} f(x_1^{k+1},...,x_{i-1}^{k+1},x,x_{i+1}^{k},...,x_{m}^{k}), i=1,...,m \tag{17}
这就有点像一个高维坐标系，你一个维度一个维度按顺序优化。
当优化问题遇到大数据
当数据量较大的时候，简单的处理办法就是利用随机化的思想，比如梯度下降法就可以改为随机梯度下降，坐标上升法就可以改为随机坐标上升。
加速优化与展望
所谓的加速优化研究的是在不作出更强假设的情况下改进算法提高收敛速度。常见的比如有重球法（Heavy-Ball method）、Nesterov的加速梯度下降法、加速近端梯度法（APG）、随机方差减小梯度法等等。这些算法可能有点超纲了，感兴趣或者专门研究这类问题的可以参考林宙辰老师的新书（参考书籍4）。
对于大规模优化的一些研究可以从以下几个角度展开：随机优化、分布式优化、异步优化、基于学习的优化等等。
参考书籍推荐
[1] Nesterov Y. Introductory lectures on convex optimization: A basic course[M]. Springer Science & Business Media, 2013.
[2] Optimization for machine learning[M]. Mit Press, 2012.
[3] Nocedal J, Wright S. Numerical optimization[M]. Springer Science & Business Media, 2006.
[4] Zhouchen Lin. Accelerated Optimization for Machine Learning[M]. Springer, 2020.
博客内容主要根据林宙辰老师的讲座内容进行梳理，在此表示感谢。 最后也给大家推荐一个优化相关的课程呀，感兴趣的可以了解下https://www.shenlanxueyuan.com/channel/nchZh0umuA/detail |
|
窥视卡
雷达卡
发表于 2023-4-3 13:19
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡