ML-凸優化初識

凸優化的入門

ML問題 = 模型 + 優化

• 類似于, 程式 = 資料結構 + 算法
• 模型(objective): DL, LR, SCV, Tree, XGBoost.....
• 優化(train): GD/SGD, Adagrand/ Adam, Coordinate Descent, EM ....

确定問題的性質, 是否為凸優化問題, 然後再确定相應的優化方式和算法去解決.

優化-标準寫法

\(Minimize \ f_0 = (x) \\ s.t. \\ f_i(x) <= 0, \ i = (1,2,...k) \\ g_j(x) = 0, \ j = (1,2,....l)\)

• 一般都是min的, 如果是max的, 即 -min = max , 大于/小于亦如此
• \(f_0(x)\)
• s.t. 部分表示限制條件(subject to), 滿足限制條件的 x 稱為可行解.

常見ML的目标函數

• 線性回歸: \(\sum_{i=1}^{n}(w^tx_i - y_i)^2 + ||w||^2_2\) 或矩陣形式 \(||Xw-y||^2_2 + ||w||^2_2\)
• 邏輯回歸: \(\sum _{i=1}^{n}y_i \ log(\sigma(w^tx+b)) + (1-y_i)log(1-\sigma(w^tx-b))\)
• 支援向量機: \(min_{w,b} = \frac {1}{2} ||w||^2_2,\ s.t \ \ y_i(w^tx+b)>=1, \ i=1,2,...\)
• 協同過濾: \(\sum _{i,j->\Omega} (u_i^tv_j-r_ij)^2 + \lambda||u||^2_F + \gamma ||v||_F^2\)
• k-means: \(min \sum _{i=1} ^n \sum _{k=1}^k \gamma_{i,k} ||x_i -\mu_k||^2 \ ,s.t. \, \gamma_{i,k} = 1 \ if 樣本屬于k-cluster, otherwise 0\)

優化分類

将優化問題劃分為标準型後, 緊接着需要判斷是屬于哪個類型的優化問題.

• convex or non-convex 是否為凸函數?
• continuous or discrete 連續還是離散?
• constraint or non-constraint 是否有限制?
• smooth or non-smooth 是否為平滑函數?

首先對于convex (凸函數 "U" 這個形狀的, 當然其實我們最希望的是構造的目标函數是convex, 就是咱平時見到的"U"形狀的(ps, 即二階導的Hessian Matrix 是半正定), 這樣的好處是它有一個Global optimum (全局最優解), 比如邏輯回歸就是一個典型的例子. 而與之對一的是non-convex 最經典的例子是神經網絡, 它的目标函數一般是"unuu.." 這樣形狀的, 求解時隻是通過不斷疊代求 Local optimum. 對于非凸函數我們追求的是Better local optimum. 尤其在深度學習中, 做預訓練時非常重要的, 目的也是為了找到到更好的初始化的解. 在NLP領域, 也是會通過詞向量的方式, 用别人訓練好的資料來進行更好的初始化過程.同時在深度學習領域,也是比較注重優化器的調整. 當然, 最為重要的還是關注convex了呀.

就我自己而言, 工作涉及的大都是convex, 基本上我是不會用深度學習的, 原因在于,

• 我自己都不知道裡面有多少function及其運作機制 (不可控制)
• 很難跟老闆解釋參數的實際意義 (很難解釋)

第二是關于函數是離散還是連續. 當然絕大多數都是假設是連續, 可微可導, 當然也有離散, 離散處理起來有些麻煩了.

第三 是關于目标函數是否有限制條件, 沒有限制條件,像線性回歸這種, 就可以直接通過梯度下降或最小二乘的方式就可輕易求解了. 然而對于帶限制條件的, 比如smv這類, 處理方式通常是将限制條件"帶入"目标函數, 比如通過拉格朗日乘子等方式.然後用到的底層知識其實是duality(對偶), 如KKT conditon

第四是關于函數smooth. 對于smooth的函數, 我們可以求出在每個點的梯度(偏導數的函數值組成的向量), 而對于non-smooth, 有可能存在不可微的情況哦, 最常見的應該是L1正則了吧.

Convex Set (凸集)

定義假設對任意的 \(x,y \in C\) 且任意參數 \(\alpha \in [0,1], 滿足 \alpha x + (1-\alpha)y \in C\), 則該集合為凸集.

通俗了解就是定義域形狀是"連續封閉且外張"的呗.

哎呀,其實數學的東西有些很難"形象", 超出3維就在幾何上就畫不出來了, 而了解的關鍵并不是"想象力" 而是從"定義和規則", 比如了解"次元", "對加法和數乘封閉"...這樣的, 了解定義和規則, 而非"舉個栗子", 很多是不太能"舉個栗子的".

常見的凸集

• 所有的\(R^n\)

• 證明by定義: $\forall x, y \in R^n, ax + (1-a)y \in R^n $

• 範數\(||x||<=1\)

• \(\forall x, y, ||x||<=1, ||y||<=1\),
• \(||ax + (1-a)y|| <= ||ax|| + ||(1-a)y|| = ||x|| + (1-a)||y|| <= a + (1-a) = 1\)

• 線性方程組\(Ax=b\)的所有解

• \(Ax=b, Ay=b \rightarrow A(ax+(1-a)y) = b\)

• 不等式\(Ax <= b\)的所有解

有個很明顯的定理: 兩個凸集的交集也是凸集

凸函數(convex function)

定義 函數的定義域dom為凸集, 對于定義域内任意\(x,y\), 滿足\(f(\theta x + (1-\theta)y) <= \theta f(x) + (1-\theta)f(y), \theta \in [0,1]\)

畫一個二維的"U" 就可以比較直覺認識了, 但還是覺得逐漸去了解定義吧

• 取一段區間 [x, \(\theta x + (1-\theta)y, y\)] .. 當時比較直覺

範數 Norm: 用來類似衡量向量/矩陣的"大小"的一個量

• L1-norm: \(||w|| = w_1+w_2+w_3+...w_n\)
• L2-norm: \(||w||^2_2 = w_1 ^2 + w_2 ^2 + ...w_n ^2\)
• \(||w||_p = (w_1^p + w_2 ^p + w_3 ^p + ...w_n ^p) ^{\frac {1}{p}}\)
• 常用來看, L1範數表示向量各分量之和; L2範數表示向量的歐式距離的平方..

convex 一階導

假設\(f: R^n \rightarrow R\) 是可微的(differentiable), f 為凸函數, 當且僅當 \(f(y) >= f(x) +\nabla (x)^T (y-x)\), 對于任意的\(x,y\).

在寫代碼會用, 如在編寫梯度下降的code時會作為循環的break條件

convex 二階導

假設\(f: R^n \rightarrow R\)

\(\nabla ^2 (x) \succ 0, 對于任意的x \in domf\)

就是二階導數值"大于0", 需要回顧一波大一的内容. 主要用來證明吧, 比如證明邏輯回歸的sujective function是凸函數等.

• 一進制函數求二階導, 得到一個變量, 即是一個值
• 二進制函數求二階導, 得到一個偏導混合的2x2 海塞矩陣
• n元函數求二階導, 也是得到一個偏導混合 海塞矩陣
• 對于多元" \(\succ 0\)" 表示該 Hessian Matrix 是一個半正定矩陣(PSD)

凸函數案例

case 1: 線性函數: \(f(x) = b^Tx + c\)

\(\forall x_1,x_2, \\ f(x_1) = b^Tx_1+c \\ f(x_2)=b^Tx_2 +c\)

用定義做判斷證明:

\(b^T(\theta x_1 + (1- \theta)x2 + c <= \theta (b^Tx_1) + (1-\theta)(b^Tx_2+c)\)

\(b^T \theta x_1 +(1-\theta) b^Tx_2 + c <= \theta b^Tx_1 + (1-\theta)(b^Tx_2) + (1-c)\theta\)

\(c <= c, 證畢\)

case 2: 二次方函數\(f(x) = \frac {1}{2}x^tAx + b^tx +c\), A是半正定矩陣

這裡用二階導來證明即可

$\frac {\partial f(x)} {f(x)} = Ax + b $

\(\frac {\partial ^2 x}{f(x)} = A \\ 由條件A \succ 0, 證畢\)

矩陣求導: ​​http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=3274​​