爬山演算法

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

爬山演算法（粵音：paa4 saan1 jin2 syun3 faat3 | 英文：hill climbing algorithm / hill climbing）係機械學習（ML）上一種常用嚟做最佳化嘅演算法。

基本做法

睇埋：最佳化

想像一個 ML 模型，有兩個參數，$x$ 同 $y$，而家用某個指標 $z$ 量度個 ML 模型嘅表現，而呢個指標係數值愈細代表個模型愈理想嘅，例如係個模型嘅犯錯率。

家陣 $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$ 值，但呢個演算法唔會能夠保證將個模型帶到去嗰個數值－所以係一個近似演算法。

相關概念

• 動量（momentum）：同力學上所講嘅動量唔同，機械學習上所講嘅動量指個演算法喺最佳化每一步更新模型參數嗰陣，會記住之前嗰幾次更新嘅改變數值（$\Delta w_{before}$），而今次嘅更新嘅改變值 $\Delta w$ 會係 $\Delta w_{before}$ 嘅函數，$\Delta w=f(\Delta w_{before})$，即係例如：

  $w:=w-\eta \nabla Q_{i}(w)+\alpha \Delta w_{before}$，當中 $Q_{i}(w)$ 係估計嘅梯度，$\alpha$ 係一個 0 至 1 之間嘅數值，決定打前嘅改變數值對而家呢次更新有幾大影響。

• 平均法（averaging）：喺做完若干步（經過嘅總步數係 $t$）最佳化之後，將個參數變成最佳化中途得到嘅數值嘅平均值，即係話：

  ${\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}$

• 地區性最細（local minimum）同地區性最大（local maximum）：用爬山演算法成日要面對嘅問題；想像好似下圖噉，個模型有一個參數 $p$，而指標 $z$ 係數值愈低愈好嘅，例如犯錯率；而家陣個演算法係按簡單嘅法則「試吓改變 $p$ 嘅數值，然後將 $p$ 移去 $z$ 比較低嗰邊，如果兩邊嘅 $z$ 都高過而家嘅，就用而家個 $p$ 值做模型參數嘅最後數值」，if (z(p - 1) > z(p)) AND (z(p + 1) > z(p)), then output p，噉一個可能嘅結果係，個演算法會俾出一個地區性最細做 output，呢個 output 值喺佢周圍範圍內係最細值，但查實仲有更細嘅可能數值。睇埋函數最高點與最低點。
• 步（step）：喺爬山演算法上，一「步」係指個演算法會一嘢將參數數值變幾多，例如一個爬山演算法可能每次都將 $p$ 數值 ±1（步數係 1），而另一個爬山演算法每次都將 $p$ 數值 ±5（步數係 5）。又有啲爬山演算法會選擇中途改變步數，例如喺頭 10 步都每步 ±5 而喺跟住嗰 10 步每步 ±4... 如此類推。喺實用上，將步數設做大嘅數值或者中途改變步數可以一定程度上幫手應付地區性最細同地區性最大嘅問題。

睇埋

• 拉曲線
• 機械學習
• 人工智能