机器学习优化模型——随机抽样的一般优化模型

4.1 随机抽样的一般优化模型

假设我们的模型的在样本i上面的损失函数是$\ell\left(\mathrm{h}\left(\mathrm{x}_{\mathrm{i}}, \mathrm{w}\right), \mathrm{Y}_{\mathrm{i}}\right)$ℓ(h(xi​,w),Yi​)，则平均经验风险：$\mathrm{R}_{\mathrm{n}}(\mathrm{w})=\frac{1}{\mathrm{n}} \sum_{\mathrm{i}=1}^{\mathrm{n}} \ell\left(\mathrm{h}\left(\mathrm{x}_{\mathrm{i}}, \mathrm{w}\right), \mathrm{Y}_{\mathrm{i}}\right)$Rn​(w)=n1​∑i=1n​ℓ(h(xi​,w),Yi​)。在个数为N的训练集上有：
$\min _{w \in \mathbb{R}^{d}} R_{n}(w)=\frac{1}{n} \sum_{i=1}^{n} \ell\left(h\left(x_{i}, w\right), Y_{i}\right)$w∈Rdmin​Rn​(w)=n1​i=1∑n​ℓ(h(xi​,w),Yi​)

但是呢，n一般是很大的，计算上面的和式都不现实，更不用说再对它计算导数，然后迭代求解了。因此一般是通过多样本进行随机抽样，来进行梯度更新和模型优化。设第 k 次迭代时由随机变量$\zeta^{k}$ζk 从全样本中随机产生一个子集合 $S_{k} \subseteq \mathbb{Q}$Sk​⊆Q
,相应的目标
函数变为:
$\mathrm{F}_{\mathrm{k}}(\mathrm{w})=\mathrm{F}_{\mathrm{k}}\left(\mathrm{w}: \xi^{\mathrm{k}}\right) \triangleq \mathrm{F}\left(\mathrm{w} ; \mathrm{S}_{\mathrm{k}}\right)=\frac{1}{\left|\mathrm{S}_{\mathrm{k}}\right|} \sum_{\mathrm{i} \in \mathrm{S}_{\mathrm{k}}} \mathrm{f}_{\mathrm{i}}\left(\mathrm{w} ; \mathrm{x}_{\mathrm{i}}, \mathrm{Y}_{\mathrm{i}}\right)$Fk​(w)=Fk​(w:ξk)≜F(w;Sk​)=∣Sk​∣1​i∈Sk​∑​fi​(w;xi​,Yi​)

4.1.1随机梯度优化算法（SG）

每次随机选取一个样本点，根据这个样本点决定优化的方向$d_k$dk​

在实际应用中,如果我们把每个样本都被计算梯度称做一个周期。那么批处理方法每个
周期只能迭代一次,而 SG 可以迭代 n 次。但是 SG 也有一些缺点,如其每次迭代的方向并
不一定是下降方向,步长需要调节,无法利用现有线搜索技术等。

4.1.2批量样本优化算法

$\mathrm{g}\left(\mathrm{w}^{\mathrm{k}}, \xi^{\mathrm{k}}\right)=\left\{\begin{array}{l} \nabla \mathrm{f}\left(\mathrm{w}^{\mathrm{k}} ; \xi^{\mathrm{k}}\right) 简单的随机梯度法\\ \frac{1}{\left|\mathrm{S}_{\mathrm{k}}\right|_{\mathrm{i} \in \mathrm{S}_{\mathrm{k}}}} \nabla \mathrm{f}_{\mathrm{i}}\left(\mathrm{w}^{\mathrm{k}} ; \mathrm{x}_{\mathrm{i}}, \mathrm{Y}_{\mathrm{i}}\right) 简单的随机梯度法\\ \mathrm{H}_{\mathrm{k}} \frac{1}{\left|\mathrm{S}_{\mathrm{k}}\right|} \sum_{\mathrm{i} \in \mathrm{S}_{\mathrm{k}}} \nabla \mathrm{f}_{\mathrm{i}}\left(\mathrm{w}^{\mathrm{k}} ; \mathrm{x}_{\mathrm{i}}, \mathrm{Y}_{\mathrm{i}}\right)批量二阶方法 \end{array}\right.$g(wk,ξk)=⎩⎪⎨⎪⎧​∇f(wk;ξk)简单的随机梯度法∣Sk​∣i∈Sk​​1​∇fi​(wk;xi​,Yi​)简单的随机梯度法Hk​∣Sk​∣1​∑i∈Sk​​∇fi​(wk;xi​,Yi​)批量二阶方法​

• 小批量样本法：用小批量随机样本进行随机梯度的计算
• 动态样本法
• 聚合梯度法
• 水平方向的改进:不是简单的随机方法(SG)或者简单的批方法,而是将二者结合在一起。
• 垂直方向的改进:二阶方法

4.3 一阶优化算法及其理论分析

对于机器学习而言，设计优化算法要解决三个问题：

• 随机抽样集合中的元素个数$|S_k|$∣Sk​∣的确定方法
• 迭代方向$d(w^k;S_k)$d(wk;Sk​)的确定方向
• 步长$a_k>0$ak​>0的确定方法.

4.3.1 引理

• 李普希兹条件：比连续的条件更强，要求导数绝对值小于一个常数。限制了斜率变化的快慢，要求函数在无限的区间上不能够有超过线性的增长。
  $\forall \mathrm{x}, \mathrm{y} \in \mathrm{D},|\mathrm{f}(\mathrm{y})-\mathrm{f}(\mathrm{x})|<\mathrm{K} | \mathrm{y}-\mathrm{x}) |$∀x,y∈D,∣f(y)−f(x)∣<K∣y−x)∣
  $\left\|\nabla^{2} F(w)\right\|_{2} \leq L, \quad \forall w \in \mathbb{R}^{d}$∥∥​∇2F(w)∥∥​2​≤L,∀w∈Rd
• 基本假设： 目标函数梯度的Lipschitz-连续性). 目标函数$\mathrm{F}: \mathbb{R}^{\mathrm{d}} \rightarrow \mathbb{R}$F:Rd→R是连续可微的，F的梯度$\nabla \mathrm{F}: \mathbb{R}^{\mathrm{d}} \rightarrow \mathbb{R}^{\mathrm{d}}$∇F:Rd→Rd是Lipschitz-连续的,Lipschitz常数为 L :

$\left\|\nabla F\left(w^{1}\right)-\nabla F\left(w^{2}\right)\right\|_{2} \leq L\left\|w^{1}-w^{2}\right\|_{2}, \quad x_{1} f \mp \forall w^{1}, w^{2} \in \mathbb{R}^{d} \quad(4.3 .1)$∥∥​∇F(w1)−∇F(w2)∥∥​2​≤L∥∥​w1−w2∥∥​2​,x1​f∓∀w1,w2∈Rd(4.3.1)

• 目标函数的梯度符合李普希兹连续。也就是要求目标函数的梯度对于自变量，不能改变的任意快.
• 假设 4.3.1 是要求目标函数的梯度对于自变量,不能改变的任意快。对于绝大多数
  梯度类算法的收敛性,这个假设是基本的。如果没有这个假设,梯度就不能提供一个好的指
  向,使得目标函数 F 快速下降

• 引理1：
  $f(w^2)\leq f(w^1)+\bigtriangledown f(w^1)(w^2-w^1)^T+\frac{1}{2}L||w^2-w^1||^2_2,\forall \mathrm{w}^{1}, \mathrm{w}^{2} \in \mathbb{R}^{\mathrm{d}}$f(w2)≤f(w1)+▽f(w1)(w2−w1)T+21​L∣∣w2−w1∣∣22​,∀w1,w2∈Rd
  证明：
  $\begin{aligned} \mathrm{F}\left(\mathrm{w}^{2}\right) &=\mathrm{F}\left(\mathrm{w}^{1}\right)+\int_{0}^{1} \frac{\partial \mathrm{F}\left(\mathrm{w}^{1}+\mathrm{t}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right)\right)}{\partial \mathrm{t}} \mathrm{d} \mathrm{t} \\ &=\mathrm{F}\left(\mathrm{w}^{1}\right)+\int_{0}^{1} \nabla \mathrm{F}\left(\mathrm{w}^{1}+\mathrm{t}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right)\right)^{\mathrm{T}}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right) \mathrm{d} \mathrm{t} \\ &=\mathrm{F}\left(\mathrm{w}^{1}\right)+\nabla \mathrm{F}\left(\mathrm{w}^{1}\right)^{\mathrm{T}}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right)+\int_{0}^{1}\left[\mathrm{PF}\left(\mathrm{w}^{1}+\mathrm{t}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right)\right)-\nabla \mathrm{F}\left(\mathrm{w}^{1}\right)\right]^{\mathrm{T}}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right) \mathrm{dt} \\ & \leq \mathrm{F}\left(\mathrm{w}^{1}\right)+\nabla \mathrm{F}\left(\mathrm{w}^{1}\right)^{\mathrm{T}}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right)+\int_{0}^{1} \mathrm{L}\left\|\mathrm{t}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right)\right\|_{2}\left\|\mathrm{w}^{2}-\mathrm{w}^{1}\right\| \mathrm{dt} \\ &=\mathrm{F}\left(\mathrm{w}^{1}\right)+\nabla \mathrm{F}\left(\mathrm{w}^{1}\right)^{\mathrm{T}}\left(\mathrm{w}^{2}-\mathrm{w}^{1}\right)+\frac{1}{2} \mathrm{L}\left\|\mathrm{w}^{2}-\mathrm{W}^{1}\right\|_{2}^{2} \end{aligned}$F(w2)​=F(w1)+∫01​∂t∂F(w1+t(w2−w1))​dt=F(w1)+∫01​∇F(w1+t(w2−w1))T(w2−w1)dt=F(w1)+∇F(w1)T(w2−w1)+∫01​[PF(w1+t(w2−w1))−∇F(w1)]T(w2−w1)dt≤F(w1)+∇F(w1)T(w2−w1)+∫01​L∥∥​t(w2−w1)∥∥​2​∥∥​w2−w1∥∥​dt=F(w1)+∇F(w1)T(w2−w1)+21​L∥∥​w2−W1∥∥​22​​
  引理2：若$\left\{w_{k}\right\}${wk​}是算法4.1.1 产生的序列，对于一切$\mathrm{K} \in \mathrm{N}$K∈N，下式成立：
  $\mathrm{E}_{\xi_{\mathrm{k}}}\left[\mathrm{F}\left(\mathrm{w}_{\mathrm{k}+1}\right)\right]-\mathrm{F}\left(\mathrm{w}_{\mathrm{k}}\right) \leq-\alpha_{\mathrm{k}} \nabla \mathrm{F}\left(\mathrm{w}_{\mathrm{k}}\right)^{\mathrm{T}} \mathrm{E}_{\xi_{\mathrm{k}}}\left[\mathrm{g}\left(\mathrm{w}_{\mathrm{k}}, \xi_{\mathrm{k}}\right)\right]+\frac{1}{2} \mathrm{L} \alpha_{\mathrm{k}}^{2} \mathrm{E}_{\xi_{\mathrm{k}}}\left[\left\|\mathrm{g}\left(\mathrm{w}_{\mathrm{k}}, \xi_{\mathrm{k}}\right)\right\|_{2}^{2}\right]$Eξk​​[F(wk+1​)]−F(wk​)≤−αk​∇F(wk​)TEξk​​[g(wk​,ξk​)]+21​Lαk2​Eξk​​[∥g(wk​,ξk​)∥22​]

$\underset{w \in \mathbb{R}^{d}}{\min } R_{n}(w)=\frac{1}{n} \sum_{i=1}^{n} \ell\left(h\left(x_{i}, w\right), Y_{i}\right)\tag{4.1.1}$w∈Rdmin​Rn​(w)=n1​i=1∑n​ℓ(h(xi​,w),Yi​)(4.1.1)

证明：
$\begin{aligned} \mathrm{F}\left(\mathrm{w}_{\mathrm{k}+1}\right)-\mathrm{F}\left(\mathrm{w}_{\mathrm{k}}\right) & \leq \nabla \mathrm{F}\left(\mathrm{w}_{\mathrm{k}}\right)^{\mathrm{T}}\left(\mathrm{w}_{\mathrm{k}+1}-\mathrm{w}_{\mathrm{k}}\right)+\frac{1}{2} \mathrm{L}\left\|\mathrm{w}_{\mathrm{k}+1}-\mathrm{w}_{\mathrm{k}}\right\|_{2}^{2} \\ & \leq-\alpha_{\mathrm{k}} \nabla \mathrm{F}\left(\mathrm{w}_{\mathrm{k}}\right)^{\mathrm{T}} \mathrm{g}\left(\mathrm{w}_{\mathrm{k}}, \xi_{\mathrm{k}}\right)+\frac{1}{2} \mathrm{L} \alpha_{\mathrm{k}}^{2}\left\|\mathrm{g}\left(\mathrm{w}_{\mathrm{k}}, \xi_{\mathrm{k}}\right)\right\|_{2}^{2} \end{aligned}$F(wk+1​)−F(wk​)​≤∇F(wk​)T(wk+1​−wk​)+21​L∥wk+1​−wk​∥22​≤−αk​∇F(wk​)Tg(wk​,ξk​)+21​Lαk2​∥g(wk​,ξk​)∥22​​

当到达极值点时，应该有$EF(w_{k+1]})-F(w_k)=0$EF(wk+1]​)−F(wk​)=0,因此我们应该让$
\mathrm{E}{\xi{\mathrm{k}}}\left[\mathrm{F}\left(\mathrm{w}{\mathrm{k}+1}\right)\right]-\mathrm{F}\left(\mathrm{w}{\mathrm{k}}\right)$尽量小。而引理2表明这二者之差是存在上界 的。我们需要做的，就是尽量缩小上界。

• 缩小方法1：当下降方向与梯度重合度越高,则这个上界会越小
• 缩小方法2：随机梯度的二阶矩$\left\|\mathrm{g}\left(\mathrm{w}_{\mathrm{k}}, \xi_{\mathrm{k}}\right)\right\|_{2}^{2}$∥g(wk​,ξk​)∥22​越小，则上界越小
• 若要对收敛性及进行分析,就需要对这两个影响进行量化