最佳化

  提示：呢篇文講嘅唔係軟件最佳化。

  提示：呢篇文講嘅唔係理想化。

最佳化（粵拼：zeoi3 gaai1 faa3），全名數學最佳化，係應用數學嘅一個分支，研究點樣喺特定情況下將一個特定嘅函數嘅輸出或者變數有咁大得咁大（最大化）或者有咁細得咁細（最小化）。

概念

睇埋：函數同數學模型

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

局部搜尋

内文：局部搜尋

爬山演算法

内文：爬山演算法

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

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

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

爬山演算法嘅圖解；X 軸同 Y 軸係個模型嗰兩個參數，Z 軸（上下）表示一個量度模型表現嘅指標；演算法嘅目標係要將 $z$ 最小化。

梯度下降法

内文：梯度下降法

梯度下降法係另一種常用嚟做最佳化嘅演算法。梯度下降法同爬山演算法相似，分別在於梯度下降法用嘅係斜率：喺每一步當中，一個梯度下降法啲參數移去邊一面唔係最決於邊一面嘅 $z$ 數值低啲，而係取決於邊一面嘅 $z$ 值嘅斜率高啲，諗住如果某一面嘅 $z$ 數值跌得快，移去過一面就會最快噉令 $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 軸表示量度個模型「有幾好」嘅指標 $z$；一個理想嘅學習演算法會將啲參數變成 ideal value（指標數值最低化）嘅數值。

模擬退火

内文：模擬退火

睇埋

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

出面網頁

• "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".