机器学习中的优化问题描述

参考

• 李沐-优化算法

  https://www.bilibili.com/video/BV1bP4y1p7Gq?vd_source=7937b7ae341caaf55cd0ac02b03193a1

• b站

  https://www.bilibili.com/video/BV1t47TzfE8R?vd_source=7937b7ae341caaf55cd0ac02b03193a1

机器学习中的优化问题描述

• 一般形式
  $$\mathbf{minimize}f(x)subjectto\mathbf{x}\in C$$

• 目标函数 $f:{\mathbb{R}}^n\to \mathbb{R}$
• 限制集合例子

C = { x ∣ h 1 ( x ) = 0 , … , h m ( x ) = 0 , g 1 ( x ) ≤ 0 , … , g r ( x ) ≤ 0 } C=\left\{\mathbf{x} \mid h_1(\mathbf{x})=0, \ldots, h_m(\mathbf{x})=0, g_1(\mathbf{x}) \leq 0, \ldots, g_r(\mathbf{x}) \leq 0\right\} C={x∣h1​(x)=0,…,hm​(x)=0,g1​(x)≤0,…,gr​(x)≤0}

• 如果 $C={\mathbb{R}}^n$ 那就是不受限

局部最小vs全局最小

• 全局最小 ${\mathbf{x}}^{\ast }:f\left({\mathbf{x}}^{\ast }\right)\le f(\mathbf{x})\forall \mathbf{x}\in C$

• 局部最小 ${\mathbf{x}}^{\ast }$ ：存在 $\epsilon$ ，使得 $f\left({\mathbf{x}}^{\ast }\right)\le f(\mathbf{x})\forall \mathbf{x}:\Vert \mathbf{x}-{\mathbf{x}}^{\ast }\Vert \le \epsilon$

• 使用迭代优化算法来求解，一般只能保证找到局部最小

凸集

• 一个 ${\mathbb{R}}^n$ 的子集 $C$ 是凸当且仅当
  $$\begin{array}{c}\alpha \mathbf{x}+(1-\alpha )\mathbf{y}\in C\\ \forall \alpha \in [0,1]\forall \mathbf{x},\mathbf{y}\in C\end{array}$$

• 第一个是非凸的，后面两个是凸的

• 两个凸集的交集是凸的

• 两个凸集的并集不一定是凸的

凸函数

• 函数 $f:C\to \mathbb{R}$ 是凸当且仅当

  $$\begin{array}{rl}& f\left(\alpha \mathbf{x}+\left(1_0-\alpha \right)\mathbf{y}\right)\le \alpha f(\mathbf{x})+(1-\alpha )f(\mathbf{y})\\ & \forall \alpha \in [0,1]\forall \mathbf{x},\mathbf{y}\in C\end{array}$$

• 如果 $\mathbf{x}\ne \mathbf{y},\alpha \in (0,1)$ 时不等式严格成立那么叫严格凸函数

凸函数优化

• 如果代价函数 $f$ 是凸的，且限制集合 $C$ 是凸的，那么就是凸优化问题，那么局部最小一定是全局最小

• 严格凸优化问题有唯一的全局最小

• 凸函数和非凸函数的例子

  凸函数

  • 线性回归$f(x)=||Wx-b|{|}_2^2$
  • Softmax回归

  非凸函数：其他

  • MLP、CNN、RNN、attention