主要是最近讀的 paper 裡提到的一些數學小技巧，記錄一下幫助自己以後忘記了的時候快速拉回思路用的，所以論述可能不會很有邏輯性，請讀者多多包涵囉。
Deep Learning 與 Convex Optimization
工程上來說，常常可以碰到一些最佳化問題。原因無他，最佳化問題的設定可以非常自然地去摻入一些我們對於解空間的限制，進而加入我們對於解空間的理解與可解釋性。如果用 Elastic Net Regression 為例來說，我們可以使用 L1 norm 去對回歸參數進行 Regularization ，達到 feature selection 的效果: 不重要的 feature 通常在 L1 下會使參數變得極小或 0 。
以工程上來說，我們可以用各式各樣的求解器 (Solver) 去求解最佳化問題。這裡我們可以看看這些 Solver 的行為大致上是這樣: 給定一組參數向量，求出一個最佳的解向量。從另一個方面來說，基本上可以看成這些 Solver 就像一個非線性函數一樣，輸入一個向量得到另一個向量，其中的轉換是非線性的。看到這裡，不難想像 Solver 就行為上，與一般的 Deep Learning 常用的轉換層其實非常相似，諸如 Fully Connection Layer、Convolution Layer、LSTM/GRU 等。
如果我們考慮:
在這個設定下，給定一組參數 theta ，我們可以得到一個解向量 x ，因此我們也可以把它看成一個把 theta 轉換成 x 的 layer 。所以說，如果我們要在 Deep Learning 中使用這樣的 layer 的話，最重要的問題就是該如何對這樣的 layer 做 back propagation 呢？
Meta-Learning with SVM
用空想的可能沒有感覺，所以我們來看一篇 paper 吧! 在 Meta-Learning with Differentiable Convex Optimization 一文中，主要就是結合 meta learning 中的 few shots learning 跟 SVM。其中的 base learner 選用 SVM ，而 meta-parameter 就是 embedding model 的參數。用 SVM 的術語來說，就是 kernel function 的參數，所以整篇文章的精神可以用一句話概括: 我們想要學到一個 kernel function，可以在不同的分類問題上都可以用 SVM 得到很好的結果。
這邊就不贅述 Meta Learning 的基本術語，諸如 Meta Loss、Meta Training、Outer Loop、Inner Loop 等。建議想快速學習這方面術語的讀者參考 ICML 2019 Tutorial。
因此我們可以這樣想這個問題:
所以說 Meta-Learning with Differentiable Convex Optimization 文中的
就是我們的 SVMSolver 。
所以說我們的 Meta Loss 的最佳化問題:
其實可以改寫成:
由於還是需要對 meta parameter 求 gradient 去最佳化 meta loss ，所以 SVMSolver 必須是可微分這件事就變得很明顯了。也就是說，meta-training loss 對 phi 的 gradient 就可以寫成:
所以說到底該怎麼對 SVMSolver 作微分呢？
SVMSolver 的 backward mode
所以我們到底該如何得到 SVMSolver 對 phi 的微分是多少呢？關於這個問題，我們可以在 Barratt 2019 [2] 這篇文章找到方法。思路上來說，在 strong duality 的假設下，我們利用 KKT condition 把最佳化問題變成 KKT condition 求解問題，而得到的解就是 forward mode 的 output ，最後利用隱函數定理 (implicit function theorem) 跟得到的解求出微分值。
先來看看怎麼對一般的 convex optimization solver 做 back propagation，這邊我會沿用 [2] 裡所用的符號，方便大家比對，最後我會再整理成 SVM 的樣子。
考慮一個一般的最佳化問題如下:
其中 x 是我們的解， theta 會是一個給定的參數。以本文的角度來說，這個 theta 就會是我們 SVM 的 kernel function (一個神經網路) 的參數。
而這樣的最佳化問題，可以寫成 Lagrange 來求解:
KKT Condition and Implicit Function Theorem
這就是這篇論文精彩的地方了: 利用 KKT condition 跟 implicit function theorem 為最佳化問題提供梯度的解析解。
但除了 KKT condition 跟 implicit function theorem 之外，這篇 paper 還有以下三個重要假設:
- Strong Duality: 也就是 duality gap 為 0 ，一個方式是假設 Slater’s condition 成立。另外在 [6] 中也有提到，對 Convex Optimization 來說，strong duality 是會成立的。
- 用做限制式的
f跟h夠平滑: paper 中有比較細的敘述，但直觀的想法就是這些限制式本身微分性質很好，也就是函數本身夠平滑 (smooth) 。這個假設我覺得就相對單純，畢竟我們想對 solver 作微分，這個假設可以讓我們少考慮一些奇異點的問題，實務上也不算難達成。 f跟其 Lagrange 乘數不會同時為 0。主要是為了配合等等求微分用上 implicit function theorem 時可以去除掉一些不好處理的不等式，作者宣稱這在實務上是很常見的，所以….這邊我就單純當作給定囉。
所以說上面提到的 Lagrange 函數它的 KKT condition 是這樣的:
其中加了波浪頭的變數為 Lagrange 函數的最佳解。
這時我們就可以用上面提到的第三個假設把不等式去掉 (這邊我有點兒想不通，但 paper 是這麼說的….?)。
接者，我們定義一個 g 如下:
令 D 為 Jacobian 算子的話，我們可以有:
則根據 KKT 我們可以知道:
再因為 implicit function theorem 成立下，我們就可以在最佳解的鄰域找到一個 x(theta) 而它的 Jacobian 可以表示為:
也就是說， x 對 theta 的微分我們就都知道了。
由於我們考慮的 SVM 實作屬於 QP 最佳化問題 (Quadratic Problem) ，所以這邊我們考慮一般的 QP 問題的話:
所以說，我們有興趣的 x 對 theta 的微分就變成:
其中 d 表示對 theta 的全微分 (total differential)。
Multi-Class Kernel-based SVM
最後，講到我們所使用的 SVM 實作 [5] ， 它的最佳化問題是長這樣的:
為了效率問題，改解它的 dual problem:
可以練習一下，這兩個問題都可以表示成 QP 最佳化問題，所以可以沿用上面求到的公式得到它們的微分。從 dual form 也比較容易看出為什麼會被歸類在 SVM ，因為線性分類器的權重 ( omega ) 被表示成 activated feature vector 的線性組合，也就是 support vector 的線性組合，所以是 SVM 的一種。
最後提醒一下，我們有興趣的是 d(alpha)/d(phi) ，對應到前面的公式， alpha 就是前面的 x ，而 phi 就是前面的 theta 。
References
- Meta-Learning with Differentiable Convex Optimization
- On the Differentiability of the Solution to Convex Optimization Problems
- Differentiable Optimization-Based Modeling for Machine Learning
- ICML 2019 Tutorial
- On the Algorithmic Implementation of Multi-Class Kernel-based Vector Machines
- EE 227A: Convex Optimization and Applications