文章目录
1. 优化
模型：DL、LR、SVM、XGboost、NN等
优化：GD/SGD、Adamw、L-BFGS、Coordinate Descent、EM等
任何一个优化问题，都可以写成如下形式：Minimize
f
0
(
x
)
f_0(x)
f0(x)
s.t.
f
i
(
x
)
≤
0
,
i
=
{
1
,
…
,
K
}
g
j
(
x
)
=
0
,
j
=
{
1
,
…
,
L
}
\begin{aligned} \text { s.t. } & f_{i}(x) \leq 0, & & i=\{1, \ldots, K\} \\ & g_{j}(x)=0, & & j=\{1, \ldots, L\} \end{aligned}
s.t. fi(x)≤0,gj(x)=0,i={1,…,K}j={1,…,L}
1.1 机器学习中优化函数
| 机器学习算法 | 优化函数 |
|---|---|
线性回归 Linear Regression
|
∑ i = 1 n ( w T x i − y i ) 2 + ∥ w ∥ 2 2 \sum_{i=1}^{n}\left(w^{T} x_{i}-y_{i}\right)^{2}+\|w\|_{2}^{2} ∑i=1n(wTxi−yi)2+∥w∥22 |
逻辑回归 Logistic Regression
|
∑ i = 1 n y i log σ ( w T x i + b ) + ( 1 − y i ) log [ 1 − σ ( w T x i + b ) ] \sum_{i=1}^{n} y_{i} \log \sigma^{\left(w^{T} x_{i}+b\right)}+\left(1-y_{i}\right) \log \left[1-\sigma^{\left(w^{T} x_{i}+b\right)}\right] ∑i=1nyilogσ(wTxi+b)+(1−yi)log[1−σ(wTxi+b)] |
SVM Support Vector Machine
|
∥
w
∥
2
2
+
λ
∑
i
=
1
n
ϵ
i
\|w\|_{2}^{2}+\lambda \sum_{i=1}^{n} \epsilon_{i}
∥w∥22+λ∑i=1nϵi s.t.
ϵ
i
≥
1
−
y
i
(
w
T
x
i
+
b
)
\epsilon_{i} \geq 1-y_{i}\left(w^{T} x_{i}+b\right)
ϵi≥1−yi(wTxi+b) |
协同过滤 Collaborative Filtering
|
∑ ( i , j ) ∈ Ω ( μ i T v j − γ i j ) 2 + λ ∥ μ ∥ F 2 + γ ∥ μ ∥ F 2 \sum_{(i, j) \in \Omega}\left(\mu_{i}^{T} v_{j}-\gamma_{i j}\right)^{2}+\lambda\|\mu\|_{F}^{2}+\gamma\|\mu\|_{F}^{2} ∑(i,j)∈Ω(μiTvj−γij)2+λ∥μ∥F2+γ∥μ∥F2 |
K均值 K-means
|
min
∑
i
=
1
n
∑
k
=
1
n
γ
i
k
∥
x
i
−
μ
E
∥
2
2
\sum_{i=1}^{n} \sum_{k=1}^{n} \gamma_{i k}\left\|x_{i}-\mu_{E}\right\|_{2}^{2}
∑i=1n∑k=1nγik∥xi−μE∥22 γ i k = { 1 , 当样本i属于第k类 0 , others \gamma_{i k}=\left\{\begin{array}{ll}1, & \text { 当样本i属于第k类} \\ 0, & \text { others }\end{array}\right. γik={1,0, 当样本i属于第k类 others |
1.2 优化分类 Optimization Categories
根据优化的标准化形式 f 0 ( x ) f_0(x) f0(x)，接下来判断这个标准化形式是属于哪一个类别，从以下四个方面进行对优化进行分类
- 是否是
convex或non-convex - 是
continuous还是discrete - 是
constrained(受约束) 还是unconstrained -
smooth还是non-smooth
对convex可以找到 Global optimal， 对non-convex只能找到 Local optimal，对于非凸问题，最好去找到 Better Local Optimal。在深度学习里面，初始化影响Local optimal，这也是为什么在深度学习领域花大量时间做预训练的过程。在图像识别领域，会做 ImageNet pre-training，用在后续的图像识别的任务里面，核心为了去找到更好的初始化的解。在 NLP领域，会使用像 word2vec词向量，词向量也是一种初始化的方式，把已经训练好的东西拿过来用，就意味着想在开始算法之前先找到一个初始解。在深度学习领域，会面对复杂的non-convex，这种算法里面，优化器也是非常重要的。
遇到一个non-convex问题，一般三种做法
- 硬解，这个问题本身比较简单
- 问题本身比较难，转化成convex问题来解决，再优化
- 通过常规算法来解，带来的通常都是local optimal
1.3 凸集 Convex Set
Convex Optimization - cvxbook link
实数域R上（或复数C上）的向量空间中，如果集合S中任意两点的连线上的点都在S内，则称集合S为凸集，如下图所示
数学定义为：设集合
D
⊂
R
n
D\subset R^n
D⊂Rn，若对于任意两点
x
,
y
∈
D
x, y \in D
x,y∈D，及实数
λ
(
0
≤
λ
≤
1
)
\lambda (0 \leq \lambda \leq 1)
λ(0≤λ≤1)都有：
λ
x
+
(
1
−
λ
)
y
∈
D
\lambda x+(1-\lambda)y \in D
λx+(1−λ)y∈D则称集合
D
D
D为凸集。
凸集的例子：
- 所有的 R n R^n Rn
- 所有正整数集合 R + n R_+^n R+n
- 范数
∥
x
∥
≤
1
\|x\| \leq 1
∥x∥≤1
- ∀ x , y ∥ x ∥ ≤ 1 , ∥ y ∥ ≤ 1 , ∥ λ x + ( 1 − λ ) y ∥ ≤ ∥ λ x ∥ + ∥ ( 1 − λ ) y ∥ = λ ∥ x ∥ + ( 1 − λ ) ∥ y ∥ ≤ λ + ( 1 − λ ) = 1 \forall x,y \quad \|x\| \leq 1, \|y\| \leq 1, \quad \|\lambda x+(1-\lambda)y\| \leq \|\lambda x\| +\|(1-\lambda)y\|=\lambda \|x\| +(1-\lambda)\|y\| \leq \lambda + (1-\lambda)=1 ∀x,y∥x∥≤1,∥y∥≤1,∥λx+(1−λ)y∥≤∥λx∥+∥(1−λ)y∥=λ∥x∥+(1−λ)∥y∥≤λ+(1−λ)=1
- Affine set：线性方程组是所有的解 A x = b Ax = b Ax=b
- Halfsapce：不等式所有的解： A x ≤ b Ax \leq b Ax≤b
- 两个凸集的交集也是凸集
凸集分离定理
所谓两个凸集分离，直观地看是指两个凸集没有交叉和重合的部分，因此可以用一张超平面将两者隔在两边，如下图所示
1.4 凸函数 Convex Function
凸函数是一个定义在某个向量空间的凸子集
C
C
C（区间）上的实值函数
f
f
f，如果在其定义域
C
C
C上的任意两点
x
,
y
x, y
x,y，以及
t
∈
[
0
,
1
]
t \in [0,1]
t∈[0,1]，有
f
(
t
x
+
(
1
−
t
)
y
)
≤
t
f
(
x
)
+
(
1
−
t
)
f
(
y
)
f(tx + (1-t)y) \leq t f(x)+(1-t)f(y)
f(tx+(1−t)y)≤tf(x)+(1−t)f(y)也就是说，一个函数是凸的当且仅当其上镜图（在函数图像上的点集）为一个凸集。
如果一个函数是凸函数，则其仅有一个全局最优解，没有局部最优解。这个性质在机器学习算法优化中有很重要的应用，因为机器学习模型最后就是在求某个函数的全局最优解，一旦证明该函数（机器学习里面叫损失函数）是凸函数，那相当于我们一定能找到它的全局最优解。 凸函数的例子
- 线性函数为凸/凹函数
-
f
(
x
)
=
b
T
x
+
c
⇒
f(x)=b^Tx+c \Rightarrow
f(x)=bTx+c⇒凸函数，证明
∀
x
1
,
x
2
⇒
f
(
x
1
)
=
b
T
x
1
+
c
,
f
(
x
2
)
=
b
T
x
2
+
c
\forall x_1,x_2 \Rightarrow f(x_1)=b^Tx_1+c,\quad f(x_2)=b^Tx_2+c
∀x1,x2⇒f(x1)=bTx1+c,f(x2)=bTx2+c
b T ( t x 1 + ( 1 − t ) x 2 ) + c ≤ t ( b T x 1 + c ) + ( 1 − t ) ( b T x 2 + c ) b^T(tx_1+(1-t)x_2)+c \leq t(b^Tx_1+c)+(1-t)(b^Tx_2+c) bT(tx1+(1−t)x2)+c≤t(bTx1+c)+(1−t)(bTx2+c)
t b T x 1 + ( 1 − t ) b T x 2 + c ≤ t b T x 1 + t c + ( 1 − t ) b T x 2 + ( 1 − t ) c tb^Tx_1 + (1-t)b^Tx_2+c \leq tb^Tx_1+tc +(1-t)b^Tx_2+(1-t)c tbTx1+(1−t)bTx2+c≤tbTx1+tc+(1−t)bTx2+(1−t)c
c ≤ c c \leq c c≤c
-
f
(
x
)
=
b
T
x
+
c
⇒
f(x)=b^Tx+c \Rightarrow
f(x)=bTx+c⇒凸函数，证明
∀
x
1
,
x
2
⇒
f
(
x
1
)
=
b
T
x
1
+
c
,
f
(
x
2
)
=
b
T
x
2
+
c
\forall x_1,x_2 \Rightarrow f(x_1)=b^Tx_1+c,\quad f(x_2)=b^Tx_2+c
∀x1,x2⇒f(x1)=bTx1+c,f(x2)=bTx2+c
- e x e^x ex， − l o g x -logx −logx， x l o n g x xlongx xlongx是凸函数
- 范数为凸函数
- x T x t \cfrac {x^Tx}t txTx为凸函数 ( x > 0 ) (x>0) (x>0)
First order Convexity Condition：假设
f
:
R
n
→
R
f:R^n\rightarrow R
f:Rn→R是可导的differentiable，则
f
f
f为凸函数，当且仅当：
f
(
y
)
≥
f
(
x
)
+
∇
(
x
)
T
(
y
−
x
)
f(y) \geq f(x)+\nabla(x)^{T}(y-x)
f(y)≥f(x)+∇(x)T(y−x)，对于任意的
x
,
y
∈
d
o
m
f
x,y \in domf
x,y∈domf。 Second order Convexity Condition：假设
f
:
R
n
→
R
f:R^n\rightarrow R
f:Rn→R是两次可导的
twice differentiable，则
f
f
f为凸函数，当且仅当：
∇
2
f
(
x
)
≥
0
\nabla^2 f(x) \ge 0
∇2f(x)≥0，对于任意的
x
,
y
∈
d
o
m
f
x,y \in domf
x,y∈domf。
1.5 优化-运输问题
对于线性规划问题解法，可以参考这个例子解法
1.6 股票/投资 组合优化 portfolio optimization
有一定金额钱，分别买
1
,
2...
m
{1,2...m}
1,2...m只不同类型的股票，使收益最大。
思路流程：
-
设定决策变量
Decision Variable： w 1 , w 2 , . . . , w n w_1,w_2,...,w_n w1,w2,...,wn
w i w_i wi表示总金额钱数投放到第 i 只股票的百分占比（权重） -
优化目标函数
Objective： 最大化收益 + 最小化风险
假设每只股票的收益服从正态分布， S i S_i Si表示第 i 只股票的收益，属于随机变量。 S 1 ∼ N ( γ 1 , σ 1 2 ) S_1\sim N(\gamma_1, \sigma_1^2) S1∼N(γ1,σ12)，…， S m ∼ N ( γ m , σ m 2 ) S_m\sim N(\gamma_m, \sigma_m^2) Sm∼N(γm,σm2)
对其中某一只股票，可以看出它过去一年变化波形图，可以假设将其划分成12个部分（月份），分别计算每个小区间的涨幅 γ i 1 , γ i 2 . . . , γ i 12 \gamma_{i1},\gamma_{i2}...,\gamma_{i12} γi1,γi2...,γi12（平均值），则 γ i = γ i 1 + γ i 2 + . . . + γ i 12 12 \gamma_i = \frac{\gamma_{i1}+ \gamma_{i2}+...+ \gamma_{i12}}{12} γi=12γi1+γi2+...+γi12。标准差 σ \sigma σ也可以计算出来。这里就可以得出 ∀ γ i , σ 2 \forall \gamma_i, \sigma^2 ∀γi,σ2是已知的条件 ( i = 1 , . . . , m ) (i=1,...,m) (i=1,...,m)。
S 1 w 1 + S 2 w 2 + . . . + S m w m ∼ N ( w 1 γ 1 + w 2 γ 2 + . . . + w m γ m , ∑ j ∑ i ≠ j w i w j σ i j ) S_1w_1+S_2w_2+... +S_mw_m \sim N(w_1\gamma_1+w_2\gamma_2+...+w_m\gamma_m , \quad \sum_j\sum_{i\neq j}w_iw_j\sigma_{ij}) S1w1+S2w2+...+Smwm∼N(w1γ1+w2γ2+...+wmγm,∑j∑i=jwiwjσij)， S i S_i Si服从正太分布，所以它们的加权平均也服从正太分布。 w 1 γ 1 + w 2 γ 2 + . . . + w m γ m w_1\gamma_1+w_2\gamma_2+...+w_m\gamma_m w1γ1+w2γ2+...+wmγm均值，代表投资组合的收益， ∑ j ∑ i ≠ j w i w j σ i j \sum_j\sum_{i\neq j}w_iw_j\sigma_{ij} ∑j∑i=jwiwjσij方差，代表投资组合的风险。
min− ∑ i = 1 m w i γ i + λ ∑ j ∑ i ≠ j w i w j σ i j -\sum_{i=1}^mw_i\gamma_i+\lambda\sum_j\sum_{i\neq j}w_iw_j\sigma_{ij} −∑i=1mwiγi+λ∑j∑i=jwiwjσij， λ \lambda λ指两个trade-off， λ \lambda λ偏大，指风险偏大， λ \lambda λ偏小，收益就偏大。将目标函数向量化形式简写，见步骤3。 -
约束条件
constraint
min− R T w + λ w T ∑ w -R^Tw+\lambda w^T\sum w −RTw+λwT∑ws.t.∑ i = 1 m w i = 1 \sum_{i=1}^mw_i=1 ∑i=1mwi=1
R = ( γ 1 γ 2 ⋯ γ m ) R=\left(\begin{array}{c}\gamma_{1} \\ \gamma_{2} \\ \cdots \\ \gamma_{m}\end{array}\right) R=⎝⎜⎜⎛γ1γ2⋯γm⎠⎟⎟⎞， Σ = ( σ 1 2 , σ 1 σ 2 , ⋯ σ 1 σ m ⋯ σ m 2 ) \Sigma=\left(\begin{array}{ccc}\sigma_{1}^{2}, \sigma_{1} \sigma_{2}, & \cdots & \sigma_{1} \sigma_{m} \\ & \cdots & \\ & & \sigma_{m}^{2}\end{array}\right) Σ=⎝⎛σ12,σ1σ2,⋯⋯σ1σmσm2⎠⎞ -
判断问题类型， convex Quadratic Programming，详细描述可以查看这个链接
-
设计、使用
solver
实际问题中，还要考虑到
- 成本
- 买不进去情况（不确定性）
- sparse （从3000只股票中如何挑出最好50只），可尝试加 ∥ w ∥ 1 \|w\|_1 ∥w∥1， w 1 w_1 w1正则
Set Cover Problem
假设有个全集U (Universal Set)，以及m个子集合
S
1
,
S
2
,
.
.
.
,
S
m
S_1,S_2,...,S_m
S1,S2,...,Sm，目标是寻找最少的集合，使得集合的union等于U。
例子：
U
=
{
1
,
2
,
3
,
4
,
5
}
U=\{1,2,3,4,5\}
U={1,2,3,4,5}，
S
:
{
S
1
=
{
1
,
2
,
3
}
,
S
2
=
{
2
,
4
}
,
S
3
=
{
1
,
3
}
,
S
4
=
{
4
}
,
S
5
=
{
3
,
4
}
,
S
6
=
{
4
,
5
}
}
S: \{S_1=\{1,2,3\}, S_2=\{2,4\},S_3=\{1,3\},S_4=\{4\},S_5=\{3,4\},S_6=\{4,5\}\}
S:{S1={1,2,3},S2={2,4},S3={1,3},S4={4},S5={3,4},S6={4,5}}，最少的集合为：
{
1
,
2
,
3
}
,
{
4
,
5
}
\{1,2,3\}, \{4,5\}
{1,2,3},{4,5}，集合个数为2。
数学公式描述:
-
设定决策变量
Decision Variable： x i x_i xi，集合 x i x_i xi是否被选择， x i ∈ { 0 , 1 } x_i \in \{0,1\} xi∈{0,1} -
优化目标函数
Objective： ∑ i = 1 m x i \sum_{i=1}^mx_i ∑i=1mxi -
约束条件
constraint:
对每个元素e都必须出现在大集合U中，如e=1时，包含1的集合为{ s 1 , s 3 s_1, s_3 s1,s3}，则 s 1 , s 3 s_1, s_3 s1,s3中必须要包含一个，类推可得 ∑ i : e ∈ S i x i ≥ 1 \sum_{i:e \in S_i}x_i \ge 1 ∑i:e∈Sixi≥1
minimize ∑ i = 1 m x i s.t. ∑ i : e ∈ s i x i ≥ 1 x i ∈ { 0 , 1 } i = 1 , … , m \begin{array}{l} \text { minimize } \sum_{i=1}^{m} x_{i} \\ \text { s.t. } \sum_{i: e \in s_{i}} x_{i} \geq 1 \\ x_{i} \in\{0,1\} \quad i=1, \ldots, m \end{array} minimize ∑i=1mxi s.t. ∑i:e∈sixi≥1xi∈{0,1}i=1,…,m -
判断问题类型：非凸函数
x i x_i xi只能选择0或1，不是一个凸集。 -
设计、使用
solverInteger Linear Programming (ILP)
对于上述步骤4，可以对 x i ∈ { 0 , 1 } x_i \in \{0,1\} xi∈{0,1}进行松弛化relaxation，使之为 0 ≤ x i ≤ 1 0 \leq x_i \leq 1 0≤xi≤1，再进行处理，可设置 x i ≥ 0.5 ⇒ x i = 1 x_i \ge 0.5 \Rightarrow x_i=1 xi≥0.5⇒xi=1， x i < 0.5 ⇒ x i = 0 x_i \lt 0.5 \Rightarrow x_i=0 xi<0.5⇒xi=0，之后再进一步处理。