[论文阅读] | 机器学习中的双层规划问题(Bilevel Programming)
1. 引言 最近看的论文涉及到了双层规划问题的求解，双层规划问题其实是一种特殊的优化问题。考虑这样一个场景，我们国家建设了很多铁路，站在国家的角度，一定程度是要最大化铁路的收益；而铁路的收益离不开使用者的消费，也就是我们普通人在出行时需要买票，那么站在个人的角度，一般情况下我们是会选择费用最低的出行方案。那么如何在保证普通人消费最低的情况下实现总体铁路收益最大化呢？ 双层规划问题就是指这种
1. 引言
最近看的论文涉及到了双层规划问题的求解，双层规划问题其实是一种特殊的优化问题。考虑这样一个场景，我们国家建设了很多铁路，站在国家的角度，一定程度是要最大化铁路的收益；而铁路的收益离不开使用者的消费，也就是我们普通人在出行时需要买票，那么站在个人的角度，一般情况下我们是会选择费用最低的出行方案。那么如何在保证普通人消费最低的情况下实现总体铁路收益最大化呢？
双层规划问题就是指这种优化问题：目标函数中的一组变量被约束为另一优化问题的最优解；更简单来说，就是一个优化问题的参数受限于另外一个优化问题，这两个问题相互影响。
因为我最近使用双层规划问题的场景是在机器学习中，具体讲是训练网络的过程中优化超参数(例如学习率、正则项的系数)，因此本文的内容限于机器学习中的双层规划。
2. 数学定义
m i n θ , w θ F ( w θ , θ ) s u c h t h a t w θ ∈ m i n w L ( w , θ ) ( 1 ) min_{\theta, w_{\theta}} F(w_{\theta},\theta) \quad such \ that \quad w_{\theta}\in min_{w}L(w, \theta) \quad(1) minθ,wθF(wθ,θ)such thatwθ∈minwL(w,θ)(1)
其中：
- F ( w θ , θ ) F(w_{\theta},\theta) F(wθ,θ) ：外部优化问题的目标函数(outer objective function)
- L ( w , θ ) L(w, \theta) L(w,θ)：内部优化问题的目标函数(inner objection function)
- θ \theta θ：外部变量/超参数(outer variable/hyper parameter)
- w w w：内部变量(inner variable)
解释：
- 针对上述公式，我们的最终目的其实是求 F ( w θ , θ ) F(w_{\theta},\theta) F(wθ,θ) 的最小值，但它其中的一个参数( w θ w_{\theta} wθ)是关于另外一个问题 L ( w , θ ) L(w, \theta) L(w,θ)解的函数；
- 上面的目标函数F和L可以通俗理解为训练网络的时候使用的损失函数，比如说网络预测值与真实值差值的平方和；
- 在机器学习中有一类应用是通过双层规划问题来优化超参数，超参数优化问题的基本思想是在给定一个度量标准的情况下，使用验证集构建一个超参数的响应函数(eg:验证集上的平均损失)，然后在超参数空间寻找最优解；
- 在2的这种情况下，一般外部目标函数 F ( w θ , θ ) F(w_{\theta},\theta) F(wθ,θ)是基于验证集的，而内部目标函数 L ( w , θ ) L(w, \theta) L(w,θ)是基于训练集的。这样设置的一个直观的解释是：内部目标函数通过采用训练集样本不断优化内部变量，也就是不断优化网络各层的参数 w w w；而外部目标函数则通过采用验证集样本不断优化外部变量，也就是优化超参数。(这里先不用纠结如何进行优化，后续会详细介绍)；
3. 一种求解思路
求解双层规划问题是比较困难的，因为内部优化问题一般很难找到其闭和解(也称为解析解–>存在严格的公式，给定x就能求出y)。
一种求解双层规划问题的思路是：
- 固定外层超参数，优化内层参数：将内部优化问题的求解看做是一个迭代优化的过程，使用梯度下降或者其各类变体算法近似求解内层目标函数的解，即使用公式(2)进行多次梯度下降优
w
w
w，假设经过T次梯度下降后，得到内层优化问题的一个近似解
w
θ
,
T
w_{\theta, T}
wθ,T。
w t = Φ ( w t − 1 , θ ) = w t − 1 − η ∇ L ( w t − 1 , θ ) , t = 1 , 2 … … T ( 2 ) w_t = \Phi(w_{t-1}, \theta)=w_{t-1} - \eta\nabla L(w_{t-1}, \theta), t=1,2……T \quad(2) wt=Φ(wt−1,θ)=wt−1−η∇L(wt−1,θ),t=1,2……T(2) - 固定内层参数，优化外层超参数：在获得内层近似解之后，针对外层，也采用梯度下降优化超参数：计算外层目标函数对超参数
θ
\theta
θ的导数(称之为超梯度)，如公式(3)；然后更新超参数,如公式(4)。
∇ θ F ( w θ , T , θ ) = ∂ w F ( w θ , T , θ ) ∇ θ w θ , T + ∂ θ F ( w θ , T , θ ) ( 3 ) \nabla_{\theta}F(w_{\theta, T}, \theta)=\partial_{w}F(w_{\theta, T}, \theta)\nabla_{\theta}w_{\theta, T} + \partial_{\theta}F(w_{\theta, T}, \theta) \quad(3) ∇θF(wθ,T,θ)=∂wF(wθ,T,θ)∇θwθ,T+∂θF(wθ,T,θ)(3)
θ = θ − η o u t e r ∇ θ F ( w θ , T , θ ) ( 4 ) \theta = \theta - \eta_{outer}\nabla_{\theta}F(w_{\theta, T}, \theta) \quad(4) θ=θ−ηouter∇θF(wθ,T,θ)(4) - 上述两个过程一般会进行多次迭代，具体在不同的应用中可以设置不同的循环停止条件，例如根据early stoping，或者根据训练误差和验证误差的关系。
4. 具体计算过程示例
[1]Franceschi, L., Donini, M., Frasconi, P., & Pontil, M. (2017). Forward and reverse gradient-based hyperparameter optimization. arXiv preprint arXiv:1703.01785.
双层规划问题有多种不同的求解方法，即使是根据本文第3部分描述的求解思路，也有具体不同的实现方式，这里呈现的计算过程是根据上述引用的论文[1]进行整理的，其整体思路是基于反向自动微分。
为了与上文进行符号统一，我修改了[1]中的符号表示，这其实并不影响对算法的理解；此外，论文[1]中针对内部优化使用的是带动量的梯度下降，为了简化理解，我采用了最简单的梯度下降。
注意： (1)根据论文[1]，这里的超参数
θ
\theta
θ就等于内部梯度下降过程中的学习率
θ
\theta
θ；在论文[1]中，作者使用的是带动量的梯度下降，因此它的超参数包括两个，当我简化为最基本的梯度下降后，超参数就变成了学习率；(2)也就是在下面4.1和4.2中，
θ
=
η
\theta = \eta
θ=η。
4.1 先给出算法：
其中：
- α t = { ∇ F ( w t ) if t=T ∇ F ( w t ) A T … A t − 1 if t=1,2 … T-1 ( 5 ) \alpha_t=\begin{cases}\nabla F(w_{t})& \text{if t=T}\\\nabla F(w_{t})A_{T}…A_{t-1}& \text{if t=1,2…T-1}\end{cases} \quad(5) αt={∇F(wt)∇F(wt)AT…At−1if t=Tif t=1,2…T-1(5)
- A t = ∂ Φ t ( w t − 1 , θ ) ∂ w t − 1 ( 6 ) A_t = \frac{\partial { \Phi_t(w_{t-1}, \theta)}}{\partial{w_{t-1}}} \quad(6) At=∂wt−1∂Φt(wt−1,θ)(6)
- B t = ∂ Φ t ( w t − 1 , θ ) ∂ θ ( 7 ) B_t = \frac{\partial {\Phi_t(w_{t-1}, \theta)}}{\partial \theta} \quad(7) Bt=∂θ∂Φt(wt−1,θ)(7)
最后计算出：
- ∇ θ F ( w θ , θ ) = ∇ F ( w T ) ∑ t = 1 T ( ∏ s = t + 1 T A s ) B t ( 8 ) \nabla_{\theta}F(w_{\theta}, \theta) = \nabla F(w_T) \sum _{t=1} ^{T}(\prod_{s=t+1} ^{T}A_s)B_t \quad(8) ∇θF(wθ,θ)=∇F(wT)∑t=1T(∏s=t+1TAs)Bt(8)
4.2 推导细节
1.给定初始的内部梯度下降参数的初始值： w 0 w_{0} w0 和初始超参数值 θ \theta θ(在这里也等于 η \eta η)
2.固定外层超参数
θ
\theta
θ，优化内层
w
w
w ：
{
t
=
1
:
w
1
=
Φ
(
w
0
,
θ
)
=
w
0
−
θ
∇
L
(
w
0
)
t
=
2
:
w
2
=
Φ
(
w
1
,
θ
)
=
w
1
−
θ
∇
L
(
w
1
)
t
=
3
:
w
3
=
Φ
(
w
2
,
θ
)
=
w
2
−
θ
∇
L
(
w
2
)
…
…
t
=
T
−
1
:
w
T
−
1
=
Φ
(
w
T
−
2
,
θ
)
=
w
T
−
2
−
θ
∇
L
(
w
T
−
2
)
t
=
T
:
w
T
=
Φ
(
w
T
−
1
,
θ
)
=
w
T
−
1
−
θ
∇
L
(
w
T
−
1
)
(
9
)
\begin{cases} t=1:w_{1} = \Phi(w_{0}, \theta) = w_{0} - \theta \nabla L(w_{0}) \\ t=2:w_{2} = \Phi(w_{1}, \theta)= w_{1} -\theta \nabla L(w_{1}) \\ t=3:w_{3} = \Phi(w_{2}, \theta)= w_{2} - \theta \nabla L(w_{2}) \\ …… \\ t=T-1:w_{T-1} = \Phi(w_{T-2}, \theta) = w_{T-2} - \theta\nabla L(w_{T-2}) \\ t=T:w_{T} = \Phi(w_{T-1}, \theta)= w_{T-1} -\theta \nabla L(w_{T-1}) \\ \end{cases} \quad(9)
⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧t=1:w1=Φ(w0,θ)=w0−θ∇L(w0)t=2:w2=Φ(w1,θ)=w1−θ∇L(w1)t=3:w3=Φ(w2,θ)=w2−θ∇L(w2)……t=T−1:wT−1=Φ(wT−2,θ)=wT−2−θ∇L(wT−2)t=T:wT=Φ(wT−1,θ)=wT−1−θ∇L(wT−1)(9)
3.得到
w
T
w_{T}
wT 后，我们认为内层优化问题已经找到了近似解，然后将固定内层参数，优化外层超参数：
(1) 优化外层超参数的第一步是求外层目标函数对超参数的超梯度：
我们先考虑一般的情况：
∇
θ
F
(
w
θ
,
T
,
θ
)
=
∂
w
F
(
w
θ
,
T
,
θ
)
∇
θ
w
θ
,
T
+
∂
θ
F
(
w
θ
,
T
,
θ
)
=
∂
w
F
(
w
θ
,
T
,
θ
)
∂
w
θ
,
T
d
w
θ
,
T
d
θ
+
∂
w
F
(
w
θ
,
T
,
θ
)
∂
θ
(
10
)
\begin{aligned} \nabla_{\theta}F(w_{\theta, T}, \theta) &= \partial_{w}F(w_{\theta, T}, \theta)\nabla_{\theta}w_{\theta, T} + \partial_{\theta}F(w_{\theta, T}, \theta) \\ & = \frac{\partial_w F(w_{\theta, T}, \theta)}{\partial w_{\theta, T} }\frac{\mathrm{d} w_{\theta, T}}{\mathrm{d} \theta} + \frac{\partial_w F(w_{\theta, T}, \theta)}{\partial \theta} \end{aligned} \quad (10)
∇θF(wθ,T,θ)=∂wF(wθ,T,θ)∇θwθ,T+∂θF(wθ,T,θ)=∂wθ,T∂wF(wθ,T,θ)dθdwθ,T+∂θ∂wF(wθ,T,θ)(10)
然后由于我简化了论文[1]，也就是超参数
θ
=
η
\theta = \eta
θ=η ，因此公式(10)将简化为：
∇
θ
F
(
w
T
)
=
∇
w
T
F
(
w
T
)
∇
θ
w
T
=
d
F
(
w
T
)
d
w
T
d
w
T
d
θ
(
11
)
\nabla_{\theta}F(w_{T}) = \nabla_{w_T}F(w_{T})\nabla_{\theta}w_{T} = \frac{\mathrm{d} F(w_{T})}{\mathrm{d} w_T}\frac{\mathrm{d} w_{T}}{\mathrm{d} \theta} \quad (11)
∇θF(wT)=∇wTF(wT)∇θwT=dwTdF(wT)dθdwT(11)
这里，在公式(11)中，
d
w
T
d
θ
\frac{\mathrm{d} w_{T}}{\mathrm{d} \theta}
dθdwT的计算是比较复杂的，因为
w
T
w_T
wT是
w
T
−
1
w_{T-1}
wT−1和
θ
\theta
θ的函数，而
w
T
−
1
w_{T-1}
wT−1又是
w
T
−
2
w_{T-2}
wT−2和
θ
\theta
θ的函数，以此类推，直到
w
0
w_0
w0，因此求
d
w
T
d
θ
\frac{\mathrm{d} w_{T}}{\mathrm{d} \theta}
dθdwT是一个嵌套的过程，因此根据链式法则，考虑
t
∈
1
,
2
…
…
T
t \in{1,2……T}
t∈1,2……T
d
w
t
d
θ
=
∂
Φ
(
w
t
−
1
,
θ
)
∂
w
t
−
1
d
w
t
−
1
d
θ
+
∂
Φ
(
w
t
−
1
,
θ
)
∂
θ
(
12
)
\begin{aligned} \frac{\mathrm{d} w_{t}}{\mathrm{d} \theta} & = \frac{\partial{ \Phi(w_{t-1}, \theta)}}{\partial{w_{t-1}}}\frac{\mathrm{d} w_{t-1}}{\mathrm{d}\theta} + \frac{\partial{ \Phi(w_{t-1}, \theta)}}{\partial{\theta}} \end{aligned} \quad (12)
dθdwt=∂wt−1∂Φ(wt−1,θ)dθdwt−1+∂θ∂Φ(wt−1,θ)(12)
令
Z
t
=
d
w
t
d
θ
Z_t =\frac{\mathrm{d} w_{t}}{\mathrm{d} \theta}
Zt=dθdwt，则公式(12)可以进一步表示为：
Z
t
=
A
t
Z
t
−
1
+
B
t
(
13
)
Z_t =A_t Z_{t-1} + B_t \quad(13)
Zt=AtZt−1+Bt(13)
所以，公式(11)可以根据公式(13)进一步展开：
∇
θ
F
(
w
T
)
=
∇
w
T
F
(
w
T
)
∇
θ
w
T
=
d
F
(
w
T
)
d
w
T
(
A
T
Z
T
−
1
+
B
T
)
=
d
F
(
w
T
)
d
w
T
(
A
T
A
T
−
1
Z
T
−
2
+
A
T
B
T
−
1
+
B
T
)
=
.
.
.
=
d
F
(
w
T
)
d
w
T
∑
t
=
1
T
(
∏
s
=
t
+
1
T
A
s
)
B
t
(
14
)
\begin{aligned} \nabla_{\theta}F(w_{T}) &= \nabla_{w_T}F(w_{T})\nabla_{\theta}w_{T} \\ &= \frac{\mathrm{d} F(w_{T})}{\mathrm{d} w_T}(A_T Z_{T-1} + B_T) \\ & = \frac{\mathrm{d} F(w_{T})}{\mathrm{d} w_T}(A_T A_{T−1} Z_{T−2 } + A_T B_{T−1} + B_{T}) \\ & = ... \\ & = \frac{\mathrm{d} F(w_{T})}{\mathrm{d} w_T} \sum _{t=1} ^{T}(\prod_{s=t+1} ^{T}A_s)B_t \end{aligned} \quad (14)
∇θF(wT)=∇wTF(wT)∇θwT=dwTdF(wT)(ATZT−1+BT)=dwTdF(wT)(ATAT−1ZT−2+ATBT−1+BT)=...=dwTdF(wT)t=1∑T(s=t+1∏TAs)Bt(14)
其中
A
A
A和
B
B
B的定义见公式(6)和(7)；在公式(14)的每一步展开中，含有
Z
Z
Z的一项是不确定的，因为
Z
t
Z_t
Zt总是依赖于
Z
t
−
1
Z_{t-1}
Zt−1，这一项直到
t
=
1
t=1
t=1才算展开结束；不过含有
B
B
B的一项是可以确定的；因此在4.1节展示的算法中，每次都是在总的梯度
g
g
g中加上公式(14)中含有
B
B
B的项，然后利用
A
A
A不断展开
Z
Z
Z，直到当
t
=
1
t=1
t=1时计算出总的梯度。
(2)优化外层超参数的第二步是根据计算出的超梯度更新超参数，如公式(4)所示；
4.经过上述2和3，内层和外层参数都经过了一轮更新，是否需要循环进行2和3以及其停止条件需要根据具体应用进行设置。比如在我近期学习的论文中，作者根据early stopping决定外部优化的停止条件，根据训练误差和泛化误差的关系决定内部优化的停止条件。
5. 其他参考资料
关于反向自动微分：
https://stats.stackexchange.com/questions/224140/step-by-step-example-of-reverse-mode-automatic-differentiation
小结
1.被双层规划以及超参数优化“折磨”了好久，终于能自己比较清晰的整理出一个思路。不过感觉写的还不是很好，还达不到让没接触过的人看起来不费劲的效果。下次要尝试怎么整理的更简单一些~
2.发现越是自己觉得简单的知识点越是弄不明白，在推导公式(14)的时候有好几次分不清梯度和偏导数，还翻出了微积分的课本，被自己傻到~数学太差啦，是时候把机器学习老师推荐的书翻出来啦hhh
要继续加油哇~
CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！
更多推荐
40
0- 0
已为社区贡献4条内容
所有评论(0)