最佳化

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

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

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

概念

睇埋：函數同數學模型

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

局部搜尋

内文：局部搜尋

爬山演算法

内文：爬山演算法

爬山演算法係一種常用嚟做最佳化嘅演算法：想像一個統計模型，有兩個參數，${\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}$ 值，但呢個演算法唔會能夠保證將個模型帶到去嗰個數值－所以係一個近似演算法^[4]。多個兩個參數嘅情況可以用同一道理想像。

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

梯度下降法

内文：梯度下降法

梯度下降法係另一種常用嚟做最佳化嘅演算法。梯度下降法同爬山演算法相似，分別在於梯度下降法用嘅係斜率：喺每一步當中，一個梯度下降法啲參數移去邊一面唔係最決於邊一面嘅 ${\displaystyle z}$ 數值低啲，而係取決於邊一面嘅 ${\displaystyle z}$ 值嘅斜率高啲，諗住如果某一面嘅 ${\displaystyle z}$ 數值跌得快，移去過一面就會最快噉令 ${\displaystyle z}$ 數值下降^[5]。梯度上升法（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）：指個梯度下降法演算法唔係靠睇嗮成個數據庫嘅數據計出現時嗰點周圍嘅斜率（梯度），而係靠由數據庫嗰度抽一個樣本出嚟，用個樣本嘅數據計梯度；呢種做法喺個數據庫好大嗰陣可以用嚟減低部電腦所受嘅負荷^[6]。

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}$ 值理想嘅^[7]。一段用模擬退火嘅虛擬碼如下^[8]：

 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 俾出嚟做輸出。

模擬退火嘅一個示範；Y 軸係需要最大化嗰個指標，X 軸係參數，隨住溫度值慢慢下降，參數值漸趨穩定。幅圖有好多地區性最大，所以用單純嘅爬山演算法好可能會搞唔掂。

睇埋

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

參攷文獻

1. Gill, P. E.; Murray, W.; Wright, M. H. (1982). Practical Optimization. London: Academic Press.
2. Horowitz, Ann R. (1987). "Loss functions and public policy". Journal of Macroeconomics. 9 (4): 489–504.
3. Neumaier, A. (1998). "Solving ill-conditioned and singular linear systems: A tutorial on regularization" (PDF). SIAM Review. 40 (3): 636–666.
4. Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 111–114.
5. Hill Climbing Algorithms (and gradient descent variants) IRL 互聯網檔案館嘅歸檔，歸檔日期2020年3月27號，..
6. addy, Matt (2019). "Stochastic Gradient Descent". Business Data Science: Combining Machine Learning and Economics to Optimize, Automate, and Accelerate Business Decisions. New York: McGraw-Hill. pp. 303–307.
7. Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680.
8. Simulated Annealing 互聯網檔案館嘅歸檔，歸檔日期2019年10月30號，.. Clever Algorithms: Nature-Inspired Programming Recipes.

出面網頁

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