注册    登录
关注
Py学习  »  机器学习算法

脚摸脚带你深度学习（九）——凸优化

水煮不是清真 • 4 年前 • 314 次点击  
阅读 4

脚摸脚带你深度学习（九）——凸优化

一句话描述：凸优化问题（OPT，convex optimization problem）指定义在凸集中的凸函数最优化的问题

凸优化问题的优势

  1. 凸优化问题的局部最优解就是全局最优解
  2. 很多非凸问题都可以被等价转化为凸优化问题或者被近似为凸优化问题（例如拉格朗日对偶问题）
  3. 凸优化问题的研究较为成熟，当一个具体被归为一个凸优化问题，基本可以确定该问题
\mathbb{R}^n \rightarrow \mathbb{R}

优化在深度学习中的挑战

  1. 局部最小值
  2. 鞍点
  3. 梯度消失

局部最小值

f(x) = x\cos \pi x

鞍点

f(x) = x^3

梯度消失

凸函数

满足以下条件的函数：

几何意义：

凸函数与二阶导数

f^{''}(x) \ge 0 \Longleftrightarrow f(x) 是凸函数

必要性 (\Leftarrow):

对于凸函数：

\frac{1}{2} f(x+\epsilon)+\frac{1}{2} f(x-\epsilon) \geq f\left(\frac{x+\epsilon}{2}+\frac{x-\epsilon}{2}\right)=f(x)

故:

f^{\prime \prime}(x)=\lim _{\varepsilon \rightarrow 0} \frac{\frac{f(x+\epsilon) - f(x)}{\epsilon}-\frac{f(x) - f(x-\epsilon)}{\epsilon}}{\epsilon}
f^{\prime \prime}(x)=\lim _{\varepsilon \rightarrow 0} \frac{f(x+\epsilon)+f(x-\epsilon)-2 f(x)}{\epsilon^{2}} \geq 0

充分性 (\Rightarrow):

令 a < x < b 为 f(x) 上的三个点，由拉格朗日中值定理:

\begin{array}{l}{f(x)-f(a)=(x-a) f^{\prime}(\alpha) \text { for some } \alpha \in[a, x] \text { and }} \\ {f(b)-f(x)=(b-x) f^{\prime}(\beta) \text { for some } \beta \in[x, b]}\end{array}

根据单调性，有 f^{\prime}(\beta) \geq f^{\prime}(\alpha), 故:

\begin{aligned} f(b)-f(a) &=f(b)-f(x)+f(x)-f(a) \\ &=(b-x) f^{\prime}(\beta)+(x-a) f^{\prime}(\alpha) \\ & \geq(b-a) f^{\prime}(\alpha) \end{aligned}

限制条件

\begin{array}{l}{\underset{\mathbf{x}}{\operatorname{minimize}} f(\mathbf{x})} \\ {\text { subject to } c_{i}(\mathbf{x}) \leq 0 \text { for all } i \in\{1, \ldots, N\}}\end{array}

拉格朗日乘子法

Boyd & Vandenberghe, 2004

L(\mathbf{x}, \alpha)=f(\mathbf{x})+\sum_{i} \alpha_{i} c_{i}(\mathbf{x}) \text { where } \alpha_{i} \geq 0

惩罚项 欲使 c_i(x) \leq 0, 将项 \alpha_ic_i(x) 加入目标函数，如多层感知机章节中的 \frac{\lambda}{2} ||w||^2

投影

\operatorname{Proj}_{X}(\mathbf{x})=\underset{\mathbf{x}^{\prime} \in X}{\operatorname{argmin}}\left\|\mathbf{x}-\mathbf{x}^{\prime}\right\|_{2}

Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/55250
Reply
 
314 次点击  
登录后回复
关于   移动版   ·   三行代码   ·   今天看啥   ·   Code   ·   link之家   ·   卧龙搜索   ·   藏经阁   ·   小百科
Py学习 - 专注于Python技术发展的社区(原Django社区)
沪ICP备11025650号