最佳化

• 損失函數（loss function），又有叫成本函數（cost function）：指一個能夠「攞一件事件或者若干個變數嘅數值、並且計出代表呢件事件會造成幾大損失或者成本」嘅函數，喺最佳化上指一個表示「如果模型參數係噉嘅數值，做預測嗰陣嘅誤差會係咁多咁多」等資訊嘅函數。
• 正則化（regularization）：指喺一個要做最佳化嘅函數裏面加多個數值，令到個最佳化過程進行得順利啲，唔會出現過適等嘅問題。

爬山演算法

爬山演算法係一種常用嚟做最佳化嘅演算法：想像一個統計模型，有兩個參數，${\displaystyle x}$  同 ${\displaystyle y}$ ，而家用某個指標 ${\displaystyle z}$  量度個統計模型嘅表現，而呢個指標係數值愈細代表個模型愈理想嘅，例如係個模型嘅犯錯率（睇下圖）。家陣 ${\displaystyle x}$  同 ${\displaystyle y}$  經已有咗數值，所以個模型喺上圖入面有個座標位置，而個爬山演算法可以喺每一步噉做：

1. 加減 ${\displaystyle x}$  同 ${\displaystyle y}$  嘅數值嚟改變個模型，即係個模型有 4（${\displaystyle +x,-x,+y,-y}$ ）個前進方向；
2. 計四個數值 ${\displaystyle z_{1},z_{2},z_{3},z_{4}}$ ，當中 ${\displaystyle z_{i}}$  係移去第 ${\displaystyle i}$  個方向會得到嘅 ${\displaystyle z}$  值；
3. 按「揀 ${\displaystyle z}$  值最小化嘅方向」呢條法則嚟改變 ${\displaystyle x}$  同 ${\displaystyle y}$  嘅數值；
4. 重複，直至結束條件達到為止。

如果順利，個模型嘅 ${\displaystyle z}$  值會慢慢變到愈嚟愈細（接近理想數值），不過原則上，呢個最後嘅答案值唔保證會係理想數值－可能喺睇到嘅空間外有更低嘅可能 ${\displaystyle z}$  值，但呢個演算法唔會能夠保證將個模型帶到去嗰個數值－所以係一個近似演算法。多個兩個參數嘅情況可以用同一道理想像。

 

梯度下降法

梯度下降法係另一種常用嚟做最佳化嘅演算法。梯度下降法同爬山演算法相似，分別在於梯度下降法用嘅係斜率：喺每一步當中，一個梯度下降法啲參數移去邊一面唔係最決於邊一面嘅 ${\displaystyle z}$  數值低啲，而係取決於邊一面嘅 ${\displaystyle z}$  值嘅斜率高啲，諗住如果某一面嘅 ${\displaystyle z}$  數值跌得快，移去過一面就會最快噉令 ${\displaystyle z}$  數值下降。梯度上升法（gradient ascent）係指用同樣嘅手法搵最大值。以下係用 Python 寫嘅一段梯度下降法碼：

next_x = 6  # We start the search at x=6 gamma = 0.01  # Step size multiplier precision = 0.00001  # Desired precision of result max_iters = 10000  # Maximum number of iterations  # Derivative function def df(x):     return 4 * x ** 3 - 9 * x ** 2   for _ in range(max_iters):     current_x = next_x     next_x = current_x - gamma * df(current_x) # 睇吓個斜率係點。      step = next_x - current_x     if abs(step) <= precision:         break  print("Minimum at ", next_x)  # The output for the above will be something like # "Minimum at 2.2499646074278457" 

隨機梯度下降法（SGD）：指個梯度下降法演算法唔係靠睇嗮成個數據庫嘅數據計出現時嗰點周圍嘅斜率（梯度），而係靠由數據庫嗰度抽一個樣本出嚟，用個樣本嘅數據計梯度；呢種做法喺個數據庫好大嗰陣可以用嚟減低部電腦所受嘅負荷。

 

p

Error rate

ideal value

local minimum

 

 

X 軸表示個模型嘅參數，而 Y 軸表示量度個模型「有幾好」嘅指標 ${\displaystyle z}$ ；一個理想嘅學習演算法會將啲參數變成 ideal value（指標數值最低化）嘅數值。

模擬退火

模擬退火：爬山演算法嘅一個變種；喺每步當中，最簡單嘅模擬退火演算法會考慮周圍嘅可能 ${\displaystyle p}$  值嘅 ${\displaystyle z}$  值，foreach 呢啲 ${\displaystyle p}$  值，將佢個 ${\displaystyle z}$  值 ±s，當中 s 係一個隨機俾嘅數值（溫度值），然後個演算法會再按邊個 ${\displaystyle p}$  嘅（±s 後）${\displaystyle z}$  數值比較接近理想數值，決定參數要變成邊個可能 ${\displaystyle p}$  值－噉做嘅話，個演算法唔會咁易企喺一個地區性最細或者地區性最大嗰度唔郁，但因為 ${\displaystyle z}$  比較近理想數值嘅 ${\displaystyle p}$  會比較大機會被選中，所以經過好多步之後，個演算法最後得出嗰個 ${\displaystyle p}$  值好有可能會係 ${\displaystyle z}$  值理想嘅。一段用模擬退火嘅虛擬碼如下：

 Input:    ProblemSize,    iteration, // 重複幾多次    max_temp, // 最大溫度值  Output:    S_best // 最佳嘅參數值    Initialize:    S_current = CreateInitialSolution(ProblemSize); // 將現時參數值設做隨機數值。    S_best = S_current; // 暫時當最佳參數值係現時數值。    for (i = 1 to iteration)    S_i = CreateNeighborSolution(S_current); // 搵 S_current 周圍嘅參數值。    current_temp = CalculateTemperature(i, max_temp); //「現時溫度」由 i 同 max_temp 話事。    if Cost(S_i) < Cost(S_current) // 如果 S_i 嘅指標值靚過 S_current 嘅...      S_current = S_i;      if Cost(S_i) < Cost(S_best) // 如果 S_i 嘅指標值靚過 S_best 嘅...        S_best = S_i;      end    else if (Exp[((Cost(S_current) - Cost(S_i)) / current_temp]) > rand()    // 當中 rand() 係一個隨機產生嘅數值；隨住 current_temp 變細，呢個 elseif 發生嘅機會率會愈嚟愈細。      S_current = S_i;  end    return S_best; // 最後就將 S_best 俾出嚟做輸出。 

 

• 機械學習
• 統計模型
• 複雜系統
• 決策
• 金髮妹原則

 

維基同享有多媒體嘅嘢：
數學最佳化

• "Decision Tree for Optimization Software". Links to optimization source codes
• "Global optimization".
• "EE364a: Convex Optimization I". Course from Stanford University.
• Varoquaux, Gaël. "Mathematical Optimization: Finding Minima of Functions".