10.2 凸性

2 凸性

• 如果算法在凸性条件设定下的效果很差，那通常我们很难在其他条件下看到好的结果。

%matplotlib inline
import numpy as np
import torch
from mpl_toolkits import mplot3d
from d2l import torch as d2l

2.1 定义

2.1.1 凸集

• 对于任何 $a,b\in X$ ，连接a和b的线段也位于X中，则向量空间中的一个集合X是凸（convex）的。

• 假设X和Y是凸集，那么 $X\bigcap Y$ 也是凸集的

• 通常，深度学习中的问题是在凸集上定义的。

2.1.2 凸函数

• 给定一个凸集X，如果对于所有 $x,x^{\prime }\in X$ 和所有 $\lambda \in [0,1]$ ，函数f是凸的，则：

$$\lambda f(x)+(1-\lambda )f(x^{\prime })\ge f(\lambda x+(1-\lambda )x^{\prime })$$

f = lambda x: 0.5 * x**2 # 凸函数
g = lambda x: torch.cos(np.pi * x) # 非凸函数
h = lambda x: torch.exp(0.5 * x) # 凸函数
x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
    d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

![[blog/source/_posts/deeplearning/code/pytorch/10_optimize/2_Convexity_files/2_Convexity_3_0.svg|svg]]

2.1.3 詹森不等式

• 凸性定义的一种推广：

$$\sum _i{\alpha }_{i}f(x_i)\ge f\left(\sum _i{\alpha }_i{x}_i\right)\text{and}{E}_X[f(X)]\ge f(E_X[X])$$

• 其中 ${\alpha }_i$ 是满足 $\sum _i{\alpha }_i=1$ 的非负实数，X是随机变量。

• 凸函数的期望不小于期望的凸函数

• 詹森不等式的一个常见应用：用一个较简单的表达式约束一个较复杂的表达式。例如，它可以应用于部分观察到的随机变量的对数似然。具体地说，由于 $\int P(Y)P(X|Y)dY=P(X)$ ，所以

  $$E_{Y\sim P(Y)}[-logP(X|Y)]\ge -logP(X)$$
  • Y 是典型的未观察到的随机变量，P(Y )是它可能如何分布的最佳猜测，P(X)是将Y 积分后的分布。例如，在聚类中Y 可能是簇标签，而在应用簇标签时，P(X | Y )是生成模型。

2.2 性质

• 局部极小值是全局极小值

• 凸函数的下水平集是凸的

• 凸性和二阶导数

  • 当一个函数的二阶导数存在时，我们很容易检查这个函数的凸性。只需 $\mathrm{\nabla }{f}^2\ge 0$ ，即$ \mathbf{ x }^ T \mathbf{H} \mathbf{ x } \geq 0$

2.3 约束

• 凸优化的一个很好的特性是能够让我们有效地处理约束。它使我们能够解决以下形式的约束优化问题：

  $$\begin{array}{rl}& minimizef(x)\\ \\ & subjectto{c}_i(x)\le 0foralli\in \{1,...,N\}\end{array}$$
  • 其中 $c_i$ 是约束函数

2.3.1 拉格朗日函数

• 通常，求解一个有约束的优化问题是困难的，解决这个问题的一种方法来自物理中相当简单的直觉。想象一个球在一个盒子里，球会滚到最低的地方，重力将与盒子两侧对球施加的力平衡。简而言之，目标函数（即重力）的梯度将被约束函数的梯度所抵消（由于墙壁的“推回”作用，需要保持在盒子内）。请注意，任何不起作用的约束（即球不接触壁）都将无法对球施加任何力。

• 上述推理可以通过以下鞍点优化问题来表示：

  $$L(\mathbf{x},{\alpha }_1,...,{\alpha }_n)=f(\mathbf{x})+\sum _{i=1}^n{\alpha }_i{c}_i(\mathbf{x})where{\alpha }_i\ge 0$$

  • $\alpha$ 是拉格朗日乘数，它确保约束被正确地执行。选择它们的大小足以确保所有i的 $c_i(\mathbf{x})\le 0$

  • L的鞍点是原始约束优化问题的最优解

2.3.2 惩罚

• 通常，添加惩罚是确保近似满足约束的一种好方法。在实践中，这被证明比精确的满意度更可靠。此外，对于非凸问题，许多使精确方法在凸情况下的性质（例如，可求最优解）不再成立。

2.3.3 投影

• 满足约束条件的另一种策略是投影。例如在处理梯度截断时，我们通过$ \mathbf{ g } \leftarrow \mathbf{ g } \cdot min ( 1, \frac{\theta}{||\mathbf{ g }||}) $\mathrm{确}\mathrm{保}\mathrm{梯}\mathrm{度}\mathrm{的}\mathrm{长}\mathrm{度}\mathrm{以}$ \theta $\mathrm{为}\mathrm{界}\mathrm{限}。\mathrm{这}\mathrm{就}\mathrm{是}g\mathrm{在}\mathrm{半}\mathrm{径}\mathrm{为}$ \theta$的球上的投影。

• 在凸集 $\mathbf{C}$ 上的投影是

$$Pro{j}_{\mathbf{C}}(\mathbf{x})=argmi{n}_{{\mathbf{c}}^{\prime }\in \mathbf{C}}||\mathbf{x}-{\mathbf{c}}^{\prime }||$$

• 它是凸集中离x最近的点。

赏

谢谢你请我吃糖果