[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62) › 04｜影片 [1:21:32–1:40:36](https://www.youtube.com/watch?v=S1km7opW6rw&t=4892s)｜投影片 Ch4 p.16–20｜上一章 [03 局部束搜尋與基因演算法（0:42–1:10）](https://app.notion.com/p/3e6fc631b0308105a674c6e43a405835)｜下一章 [05 牛頓法與線性規劃（1:40–2:04）](https://app.notion.com/p/3e6fc631b03081f79e51ec7d5af80d42)
跳過提示：(1:23:02–1:26:03) 老師在寫機場座標問題的數學目標函數(六個變數的平方距離加總)，聽不懂可以直接跳到 [1:26:03](https://www.youtube.com/watch?v=S1km7opW6rw&t=5163s)，接著講「為什麼把最大化問題改寫成最小化」。
跳過的這段在做什麼：老師把「機場放得好不好」寫成一條算式，意思是「每個城市到最近機場的距離，平方後全部加起來」，數字越小越好。下面「目標函數」那段有白話說明。
跳過提示：(1:29:04–1:33:40) 老師在用微積分對六個變數做偏微分求極值，聽不懂可以直接跳到 [1:33:40](https://www.youtube.com/watch?v=S1km7opW6rw&t=5620s)，接著講「站在山坡上」的比喻，說明梯度方向的意思。
跳過的這段在做什麼：老師用微積分找「坡度剛好等於 0」的位置，也就是最高點或最低點；結論是每座機場最好放在它負責那群城市的正中間。下面「微分等於零求極值」那段有白話說明。
跳過提示：(1:38:06–1:40:36) 老師開始推導牛頓法(解方程式 g(x)=0 的公式)，聽不懂可以直接跳到 [1:40:36](https://www.youtube.com/watch?v=S1km7opW6rw&t=6036s)，本章到這裡結束，下一章會接著把公式推完。
跳過的這段在做什麼：老師在介紹牛頓法，一種「沿著切線一步步逼近答案」的解方程式方法。下面「Line search 與牛頓法」那段和下一章都有白話說明。
## 重點
- 連續空間也能做局部搜尋：蓋三座機場的解是六維向量 (x1, y1, x2, y2, x3, y3)，目標是讓「每個城市到最近機場的距離平方和」最小。最佳化問題習慣改寫成最小化 cost／loss。
- 兩條路：離散化（每次只把一座機場的 x 或 y 挪 ±δ，每個狀態只有 12 個鄰居，直接套爬山法），或用梯度 ∇f：解得出 ∇f = 0 就直接算，解不出來就用 x ← x + α∇f(x) 一步一步走。
- 梯度決定方向，步長 α 決定走多遠：太小要走很多步，太大會衝過頭。Line search 沿梯度方向延伸到 f 開始變差為止；Newton–Raphson 用 x ← x − g(x)/g′(x) 求 g(x) = 0 的根。
## Exam-ready
- **Three-airports problem (6-D state space)**: "Suppose we want to place three new airports anywhere in Romania, such that the sum of squared distances from each city on the map to its nearest airport is minimized." "The state space is then defined by the coordinates of the airports: (x1,y1), (x2,y2), and (x3,y3). This is a six-dimensional space; we also say that states are defined by six variables."（Ch4 p.16）
- 中文：假設要在羅馬尼亞地圖上任意位置蓋三座新機場，讓每個城市到最近機場的距離平方和最小。狀態空間就是三座機場的座標 (x1,y1)、(x2,y2)、(x3,y3)，這是六維空間，也就是用六個數字描述一個狀態。白話：把「機場放哪裡」想成在六維空間裡找一個點，這個點就是三座機場座標的組合。
- **Objective f(x1,y1,x2,y2,x3,y3) = Σ(i=1..3) Σ(c∈Ci) (xi − xc)² + (yi − yc)²**: "Let Ci be the set of cities whose closest airport (in the current state) is airport i. The objective function is"（Ch4 p.17）
- 中文：Ci 是「目前狀態下，離第 i 座機場最近的城市」集合，目標函數就是把每座機場負責的城市的距離平方加總起來。白話：這個式子在算「所有城市到自己最近機場的距離平方」，全部加起來，數字越小代表機場位置越好。
- **Discretize**: "To avoid continuous problems: discretize the neighborhood of each state. We can move only one airport at a time in either the x or y direction by a fixed amount ±δ. With 6 variables, this gives 12 possible successors for each state."（Ch4 p.17）
- 中文：為了避免連續空間鄰居列不完，把每個狀態的鄰域離散化（discretize，切成固定大小的一格一格）：一次只挪一座機場，只往 x 或 y 方向移動固定量 ±δ。六個變數就有 12 種可能的後繼狀態。白話：規定每次只能挪一小步，鄰居就從無限多變成固定的 12 個，這樣就能直接套用爬山法。
- **Gradient ∇f**: "Many methods attempt to use the gradient of the landscape to find a maximum. The gradient of the objective function is a vector ∇f that gives the magnitude and direction of the steepest slope."（Ch4 p.18）
- 中文：很多方法會用地形的梯度（gradient，坡度的方向與陡度）來找最大值。目標函數的梯度是一個向量 ∇f，同時給出最陡坡度的大小和方向。白話：梯度就像指南針，同時告訴你「往哪個方向走」和「這個方向有多陡」。
- **Closed form**: "In some cases, we can find a maximum by solving the equation ∇f = 0. In many cases, however, this equation cannot be solved in closed form."（Ch4 p.18）
- 中文：有些情況可以直接解 ∇f = 0 找到最大值，但很多情況這個方程式沒辦法寫成封閉解（closed form，一條可以直接代入就算出答案的公式）。白話：closed form 就是「有現成公式可以套」；很多真實問題沒有這種公式，只能一步一步逼近答案。
- **Local gradient ∂f/∂x1 = 2Σ(x1 − xc)**: "the expression for the gradient depends on what cities are closest to each airport in the current state. This means we can compute the gradient locally"（Ch4 p.19）
- 中文：梯度的表達式取決於目前狀態下哪些城市離哪座機場最近，所以梯度只能局部（locally，只在目前這個位置附近）計算。白話：因為「誰負責哪些城市」會隨機場位置改變，這條梯度公式只在目前位置附近算得出來，換個位置就要重新算。
- **Steepest-ascent update x ← x + α∇f(x)**: "Given a locally correct expression for the gradient, we can perform steepest-ascent hill climbing by updating the current state according to the formula"（Ch4 p.19）
- 中文：只要有目前狀態下正確的梯度表達式，就能用這個公式更新目前狀態，做最陡上升爬山法（steepest-ascent hill climbing）。白話：每一步都照梯度指的方向往上爬一段，這段距離的長短由 α 決定。
- **Step size α**: "where α is a small constant often called the step size."（Ch4 p.19）"If α is too small, too many steps are needed; if α is too large, the search could overshoot the maximum."（Ch4 p.20）
- 中文：α 是一個小常數，叫做步長（step size）。α 太小，需要走很多步才會到；α 太大，搜尋可能會衝過頭（overshoot），越過最大值。白話：步長太小走很久才到終點，太大反而會跳過終點、越跳越遠。
- **Line search**: "The technique of line search tries to overcome this dilemma by extending the current gradient direction until f starts to decrease again."（Ch4 p.20）
- 中文：線搜尋（line search）技巧是沿著目前的梯度方向一直延伸，直到 f 開始變差為止，用來解決步長不好抓的問題。白話：不用自己猜步長，而是沿著同一個方向一直走，走到「開始變差」那一刻才停下來。
- **Newton–Raphson x ← x − g(x)/g′(x)**: "For many problems, the most effective algorithm is the Newton–Raphson method. This is a general technique for finding roots of functions—that is, solving equations of the form g(x)=0."（Ch4 p.20）
- 中文：對很多問題來說，最有效的演算法是牛頓法（Newton–Raphson method）。這是求函數的根（root，讓函數等於 0 的那個 x）的通用技巧，也就是解 g(x)=0 這種方程式。白話：牛頓法是用切線一步步逼近「等於 0」的那個答案，通常收斂很快。
## [1:21:32](https://www.youtube.com/watch?v=S1km7opW6rw&t=4892s) 從離散到連續：蓋三座機場
前面的八皇后、爬山法、模擬退火、基因演算法，處理的大多是離散問題：皇后只能放在固定的格子上。這些方法都有一種「隨機試試看，鄰居比較好就換過去」的味道。如果問題本身在連續空間裡，其實有更有效率的做法。老師的例子：在羅馬尼亞地圖上蓋三座新機場，一個解就是三座機場的座標 (x1, y1, x2, y2, x3, y3)，也就是六維空間裡的一個點。
（第 2 週和本週第 02 章學過：爬山法就是「每一步都換到周圍分數最好的鄰居，沒有更好的鄰居就停」；鄰居是「從目前的解只改一點點就能到的解」；八皇后是在棋盤上放 8 個皇后、讓它們互不攻擊的練習題；模擬退火是一開始敢接受變差的一步、越後面越保守的爬山法。見 [02 爬山法複習與模擬退火](https://app.notion.com/p/3e6fc631b03081a79865f701c688c1c4)。本週第 03 章學過：基因演算法是讓好的解互相交配、突變，一代一代變好，見 [03 局部束搜尋與基因演算法](https://app.notion.com/p/3e6fc631b0308105a674c6e43a405835)。）
用生活例子講，「在六維空間找最佳解」是什麼意思？
想像你手上有三根圖釘，要釘在地圖上當機場。每根圖釘要兩個數字（x、y）才能定位，三根就是六個數字。「在六維空間找最佳解」只是換個說法：在所有可能的六個數字組合裡，找出最好的那一組。
離散和連續的差別在「選項數得完嗎」。八皇后每個皇后只有 8 格可選，鄰居可以一個一個列出來比較。圖釘可以釘在任何地方，x 可以是 3.1、3.14、3.141……，選擇有無限多種，鄰居列不完。這一章的兩個解法，都是在處理這個「無限多」。
## [1:24:13](https://www.youtube.com/watch?v=S1km7opW6rw&t=5053s) 目標函數：距離平方和
先把「好不好」寫成一個數字。Ci 是「在目前狀態下，離第 i 座機場最近的城市」集合。每座機場把自己負責的城市的距離平方加起來，三座再加總，就是目標函數：
f(x1, y1, x2, y2, x3, y3) = Σ(i = 1 到 3) Σ(c ∈ Ci) [(xi − xc)² + (yi − yc)²]
f 越小，大家到機場越方便。要留意 Ci 會跟著機場位置變：機場一移動，某個城市可能改成離另一座機場比較近。
看不懂符號沒關係：Σ（讀作 sigma）的意思就是「全部加起來」；c ∈ Ci 讀作「c 屬於 Ci」，也就是「Ci 裡的每一個城市 c」；(xi − xc)² + (yi − yc)² 是機場和城市之間直線距離的平方（畢氏定理少了開根號那一步）。用平方的好處是結果一定是正數，而且離很遠的城市會被罰得特別重。（我補充）
[[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\chapter_4_search_in_complex_environments_p017.png | 投影片 p.17：上半是目標函數 f 的雙重加總，下半是離散化的做法]]
圖上重點：
- Local Search in Continuous Spaces：連續空間裡的局部搜尋（這幾頁投影片的標題）。
- Let Ci be the set of cities whose closest airport is airport i：Ci 是「最近的機場是第 i 座」的那群城市。
- The objective function is：接著的那條式子就是目標函數 f，兩個 Σ 的意思是「先把每座機場負責的城市加起來，再把三座機場加起來」。
- discretize the neighborhood ... ±δ ... 12 possible successors：把鄰居離散化，一次只挪一座機場的 x 或 y 一小步 ±δ，所以每個狀態有 12 個鄰居。
- We can then apply any of the local search algorithms：這樣就能套用前面學過的任何局部搜尋方法。
這張圖在講：先把「機場放得好不好」變成一個分數 f，再用「每次只挪一小步」的方式，讓爬山法可以用在連續空間。
下面的摺疊用一個小例子把 f 算一次，想讓你看到的是：機場挪到更靠近自己負責的城市，f 就變小；f 就是用來比較兩種擺法誰比較好的分數。
它到底怎麼運作？用四個城市手算一次 f
為了好算，改成兩座機場、四個城市（我自己的例子）：A(0, 0)、B(2, 0)、C(10, 0)、D(10, 4)。機場 1 在 (1, 1)，機場 2 在 (9, 2)。
第一步，分組：A 到機場 1 的距離平方是 1² + 1² = 2，到機場 2 是 9² + 2² = 85，所以 A 屬於 C1。同理 B 屬於 C1（2 對 53），C 和 D 屬於 C2（C 是 82 對 5，D 是 90 對 5）。
第二步，加總：C1 貢獻 2 + 2 = 4，C2 貢獻 5 + 5 = 10，f = 14。
如果把機場 1 挪到 (1, 0)、機場 2 挪到 (10, 2)，A、B 各變 1，C、D 各變 4，f 降到 10。後面會看到，10 就是這個例子的最小值。
## [1:25:38](https://www.youtube.com/watch?v=S1km7opW6rw&t=5138s) 最大化改寫成最小化
老師特別要大家記得這件事（1:25:38）：前面的例子都在「最大化」目標值，這沒問題；但在各種最佳化工作裡，大家傾向把問題改寫成「最小化 cost（成本）或 loss（損失）」。理由是最大化容易讓數字一路變大到爆掉（overflow，超出電腦能存的範圍）；loss 一般最小就是 0，一路往 0 壓不會爆。所以即使概念上要最大化，也會把式子改寫成最小化 cost。機場問題本身就是最小化，剛好符合這個習慣。
下面第一個摺疊講兩種改寫的小技巧：加一個負號，或改數一個「越少越好」的量；兩種改法找到的最佳解都跟原本一樣。
它到底怎麼運作？最大化要怎麼改寫成最小化？
最直接的做法是加負號：「讓 f 最大」和「讓 −f 最小」是同一件事，找到的解一模一樣。
更常見的是換一個「越少越好」的量來數。以前面的八皇后為例：「互不攻擊的皇后對數」越大越好（最多 28 對）；改數「互相攻擊的皇后對數」，就變成越小越好，最小是 0，而且 0 就代表解出來了。兩者加起來永遠是 28，所以最佳解相同。
深度學習訓練模型也是這樣：想要「預測越準越好」，實際上寫成「loss 越小越好」再去最小化。
老師原話是什麼？
「我們傾向於把問題都轉成我們要去最小化這個 cost，我們稱呼它叫做 cost 或者叫做 loss」(1:26:07)
「因為在數學上你要去最大化一個東西，容易造成那個數字會爆掉」(1:26:18)
「即使在概念上我們要去最大化某一個 objective function value，我們也會把數學改寫一下，變成是我們要去最小化那個 cost」(1:26:44)
## [1:27:01](https://www.youtube.com/watch?v=S1km7opW6rw&t=5221s) 離散化：12 個鄰居
在連續空間裡，xi、yi 有無限多種取值，鄰居列不完。妥協的做法是離散化（discretize，把連續的選擇切成固定大小的一格一格）：每次只挑一座機場，只動它的 x 或 y，而且只能加 δ 或減 δ。每座機場有 2（x 或 y）× 2（+δ 或 −δ）= 4 種動法，三座機場共 12 種，所以每個狀態只有 12 個鄰居。鄰居變成有限個之後，前面學過的爬山法、模擬退火等局部搜尋都能直接套用。
δ（讀作 delta）在這裡就是「一小步」的固定長度，例如 1 公里；由你自己決定。
| 動哪座機場 | x 加 δ | x 減 δ | y 加 δ | y 減 δ |
|---|---|---|---|---|
| 機場 1 | x1 + δ | x1 − δ | y1 + δ | y1 − δ |
| 機場 2 | x2 + δ | x2 − δ | y2 + δ | y2 − δ |
| 機場 3 | x3 + δ | x3 − δ | y3 + δ | y3 − δ |
表中每一格是一個鄰居：只改那一個變數，其他五個不動。投影片的算法是「6 個變數 × 2 個方向 = 12」，跟老師的 2 × 2 × 3 是同一件事。
下面的摺疊用前面四個城市的例子真的爬一次：每一輪把所有鄰居的 f 都算出來，挑最小的走過去；走兩步後 f 從 14 降到 10，周圍沒有更好的鄰居就停下。
它到底怎麼運作？用上一段的例子爬一次
接上一段：機場 1 在 (1, 1)、機場 2 在 (9, 2)，f = 14。取 δ = 1。這個例子只有兩座機場，所以是 8 個鄰居。這裡要讓 f 變小，所以「爬山」是往 f 小的方向爬。
機場 1 的四個鄰居：(2, 1) 得 f = 16；(0, 1) 得 16；(1, 2) 得 20；(1, 0) 得 12。
機場 2 的四個鄰居：(10, 2) 得 12；(8, 2) 得 20；(9, 3) 得 16；(9, 1) 得 16。
最好的鄰居是 f = 12（兩個平手，挑一個）。先把機場 1 挪到 (1, 0)，下一輪再把機場 2 挪到 (10, 2)，f = 10。這時 8 個鄰居的 f 都是 12，比 10 差，爬山法停下來。
## [1:29:02](https://www.youtube.com/watch?v=S1km7opW6rw&t=5342s) 微分等於零求極值
比較「正規」的做法是直接在連續空間找極值。口訣是高中、微積分教過的：一次微分、令它等於 0、求解。f 有六個變數，所以要對 x1、y1、x2、y2、x3、y3 各做一次偏微分，六個式子都令為 0，合起來寫成 ∇f = 0。問題是很多函數太複雜，整理不出 closed form（封閉解：一條可以直接代入算出答案的公式）。老師提到，深度學習動輒幾百萬、幾億個參數，找最佳參數的做法原則上跟接下來這套一樣。
注意：本課不講為什麼「一次微分令它等於 0」就能找到極值，老師說有興趣可以去修最佳化導論（1:30:17）。
（我補充）直覺版的理由：山頂和谷底那一點，地面是平的，往任何方向的坡度都是 0；所以「找坡度等於 0 的地方」就是在找極值（最高點或最低點）。微分就是在算坡度：x 動一點點，f 跟著變多少。
下面兩個摺疊：第一個解釋偏微分和梯度是什麼；第二個把機場問題的 ∇f = 0 真的解出來，結論很好懂：只要每座機場負責哪些城市先固定，它最好的位置就是那群城市的正中間（平均位置）。
要先懂什麼？偏微分和梯度是什麼？
偏微分 ∂f/∂x1：把其他變數都當成常數，只看 x1 動一點點時 f 會變多少。例如 f(x, y) = x² + 3y，∂f/∂x = 2x，∂f/∂y = 3。
梯度 ∇f：把所有偏微分排成一個向量。機場問題是 ∇f = (∂f/∂x1, ∂f/∂y1, ∂f/∂x2, ∂f/∂y2, ∂f/∂x3, ∂f/∂y3)。上面的 f(x, y) = x² + 3y 在 (1, 0) 這一點，∇f = (2, 3)。
投影片 p.18 的定義：梯度是一個向量，同時告訴你最陡的坡朝哪個方向（direction）、有多陡（magnitude）。
它到底怎麼運作？機場問題的 ∇f = 0 長什麼樣？
投影片 p.19 給了其中一個偏微分：∂f/∂x1 = 2 Σ(c ∈ C1) (x1 − xc)。只有 C1 裡的城市跟 x1 有關，其他項微分後都是 0。（投影片印成 (xi − xc)，這裡的 i 就是 1。）
令它等於 0：Σ(x1 − xc) = 0，也就是 x1 = C1 裡所有城市 x 座標的平均。y1 同理。所以只要 Ci 固定，每座機場最好的位置就是它負責那群城市的平均位置（重心）。拿前面的例子驗算：C1 = {A(0, 0), B(2, 0)}，重心 (1, 0)；C2 = {C(10, 0), D(10, 4)}，重心 (10, 2)。跟離散化爬出來的答案一樣，f = 10。
麻煩在於 Ci 會跟著機場位置變，所以這條式子只在目前狀態附近成立，投影片的說法是 "we can compute the gradient locally"。整個問題找不到一條公式一次算完。
（我補充）「分組 → 機場移到重心 → 重新分組」反覆做，就是機器學習裡的 k-means 分群。
老師原話是什麼？
「我們在這門課裡面不會告訴你為什麼，因為你有興趣的話，你可以去修最佳化導論」(1:30:17)
「現在我們在畫面上看到的這個例子只有六個參數，但是在 neural network 裡面有幾百萬個」(1:32:31)
## [1:33:09](https://www.youtube.com/watch?v=S1km7opW6rw&t=5589s) 最陡上升的更新式
沒有 closed form 時，就一步一步更新：x ← x + α∇f(x)。這叫 steepest-ascent hill climbing（最陡上升爬山法）：每一步都往目標值上升最快的方向走。這裡的 x 是六個變數組成的向量，∇f(x) 負責決定方向，α 負責決定走多遠。用爬山想最清楚：海拔就是目標函數值，梯度指向海拔上升最快的方向。老師的講法：爬山法如果每次都挑周圍最好的那個鄰居走過去，目標值就以最陡的方式往上升，用最快的速度爬到眼前看得到的最高點；連續空間裡，這個「最好的方向」就由梯度直接算出來。
注意：這條式子是「往上爬」，用在最大化。機場問題要最小化，要往反方向走：x ← x − α∇f(x)，也就是深度學習常說的 gradient descent（梯度下降）。（我補充）
符號說明：「←」讀作「更新成」，x ← x + α∇f(x) 就是「新的位置＝舊的位置＋α 倍的梯度」。向量就是一排數字，這裡是六個座標排在一起。
下面第二個摺疊用一個一維小例子實際走三步，看到的是：x 每一步都更接近谷底，而且越靠近谷底步伐越小，因為坡變緩了。
用生活例子講，梯度在說什麼？
這是老師的比喻。你站在山坡上，左右是 x 方向，前後是 y 方向，腳下的海拔就是目標函數值。
對 x 偏微分：往右走一步，海拔會怎麼變？升 1 公尺，還是降 0.5 公尺？
對 y 偏微分：往前走一步，海拔會怎麼變？
兩個數字合起來就是梯度。假設往右一步升 1 公尺、往前一步升 0.5 公尺，梯度就是 (1, 0.5)：最陡的上坡在右前方、偏右。更新式就是「朝這個方向跨出 α 倍的一步」。
它到底怎麼運作？一維的小例子手算三步
（我自己的例子）一座機場、三個城市，都在一條直線上：0、2、4。
f(x) = x² + (x − 2)² + (x − 4)²，f′(x) = 6x − 12。
要最小化，所以用 x ← x − α f′(x)。取 α = 0.1，從 x = 5 出發（f = 35）：
第 1 步：f′(5) = 18，x = 5 − 1.8 = 3.2，f = 12.32
第 2 步：f′(3.2) = 7.2，x = 3.2 − 0.72 = 2.48，f ≈ 8.69
第 3 步：f′(2.48) = 2.88，x = 2.48 − 0.288 = 2.192，f ≈ 8.11
x 一路逼近 2（f = 8），正好是三個城市的平均。步伐會自己變小：越接近谷底，坡越緩，梯度越小。
## [1:36:45](https://www.youtube.com/watch?v=S1km7opW6rw&t=5805s) 步長 α 太大太小都不好
α 叫 step size（步長），是要自己決定的參數，沒有標準答案。α 太小：方向對了，但每次都小碎步，要走很多步才到最高點。α 太大：決定往右走，一口氣衝兩公里，越過山頂跑到另一頭，高度反而下降，這叫 overshoot（衝過頭）。老師的結論是過猶不及：梯度決定方向，α 決定距離，兩個都要對。
下表用上一段的一維例子（從 x = 5 往谷底 x = 2 走，用梯度下降），看不同 α 的差別（我自己算的）：
| α | 第一步走到 | 結果 |
|---|---|---|
| 0.01 | 4.82 | 每步只縮短 6% 的距離，要 93 步才進入 2 ± 0.01 |
| 0.1 | 3.2 | 每步剩 40% 的距離，7 步進入 2 ± 0.01 |
| 1/6 | 2 | 一步到位（這題剛好） |
| 0.5 | −4 | 衝過頭，f 從 35 變成 116，之後越跳越遠 |
表下面的摺疊解釋 α 太大為什麼會爆掉：每走一步，「離谷底的距離」會乘上一個固定倍數；倍數在 −1 和 1 之間就會越走越近，超出這個範圍（例如 α = 0.5 時是 −2）就會在谷底兩側來回跳、越跳越遠。
它到底怎麼運作？為什麼 α = 0.5 會越跳越遠？
把更新式整理一下：x − 2 ← (1 − 6α)(x − 2)。也就是說，每走一步，「離谷底的距離」會乘上 (1 − 6α)。
α = 0.1：乘 0.4，距離越來越短。α = 1/6：乘 0，一步到底。α = 0.5：乘 −2，每步都跳到谷底另一側、距離還變兩倍：5 → −4 → 14 → ……，永遠回不來。
所以這個例子只有 0 < α < 1/3 才會收斂。這個範圍是這題專屬的，換個函數就不同，所以實務上才需要 line search 或反覆試。
老師原話是什麼？
「越過山丘，又跑到山的另外一頭，你的高度搞不好還會下降」(1:37:50)
「所以過猶不及」(1:37:58)
「你做梯度是決定你要走的方向」(1:38:18)
## [1:38:48](https://www.youtube.com/watch?v=S1km7opW6rw&t=5928s) Line search 與牛頓法
梯度決定方向；「沿這個方向到底要走多遠」本身又是另一個最佳化問題。投影片 p.20 的 line search（線搜尋）：沿著目前的梯度方向一直往前延伸，直到 f 開始下降就停。投影片接著介紹 Newton–Raphson method（牛頓法）：一個求函數根的通用技巧，也就是解 g(x) = 0，更新式是 x ← x − g(x)/g′(x)，其中 g′(x) 是 g 的一次微分。老師說大家以前學過只是忘了，可以回去翻以前的數學書。
注意：老師口頭說牛頓法是 line search 裡很有名的一種做法（1:39:08）；投影片則把 Newton–Raphson 寫成另一種「對很多問題最有效」的方法，以投影片的說法為準。牛頓法怎麼拿來找最佳解，下一章接著講。
名詞說明：函數的根（root）就是「讓函數等於 0 的那個 x」，例如 x² − 2 = 0 的根是 √2。g(x) 只是另一個函數的名字，跟前面的 f 分開。切線就是在曲線上某一點、剛好貼著曲線的那條直線。
下面兩個摺疊：第一個用切線解釋牛頓法的公式從哪來；第二個實際算一次 √2，三步就準到小數點後五位，再示範拿它解「微分等於 0」時，一維機場例子一步就到谷底。
要先懂什麼？牛頓法的更新式為什麼長這樣？
在目前猜的 x 那一點，畫出 g 的切線，切線斜率是 g′(x)。沿著切線從高度 g(x) 走到高度 0，需要橫移 g(x)/g′(x)。那個交點就是下一個猜測：x − g(x)/g′(x)。
換句話說，牛頓法假設 g 在附近近似一條直線，直接跳到那條直線的根；g 越像直線，跳得越準。
它到底怎麼運作？手算一次牛頓法
求 √2，也就是解 g(x) = x² − 2 = 0，g′(x) = 2x。從 x = 1 開始：
第 1 步：x = 1 − (−1)/2 = 1.5
第 2 步：x = 1.5 − 0.25/3 ≈ 1.41667
第 3 步：x ≈ 1.41667 − 0.00694/2.83333 ≈ 1.41422（真值 1.41421……）
三步誤差就只剩約 0.000002。
拿來做最佳化時，把 g 換成 f 的一次微分，去解「微分等於 0」。一維機場例子：g(x) = f′(x) = 6x − 12，g′(x) = 6，x ← x − (6x − 12)/6 = 2，不管從哪裡出發都一步到谷底。
## Self-check
1. The three-airports problem has a continuous state space. (a) If the neighborhood is discretized with a fixed step ±δ, how many successors does each state have, and why? (b) Why can't we simply solve ∇f = 0 to place the airports in one shot?
Q1. The three-airports problem has a continuous state space. (a) If the neighborhood is discretized with a fixed step ±δ, how many successors does each state have, and why? (b) Why can't we simply solve ∇f = 0 to place the airports in one shot?（中文：三機場問題的狀態空間是連續的。(a) 如果用固定步長 ±δ 把鄰域離散化，每個狀態有幾個後繼狀態，為什麼？(b) 為什麼不能直接解 ∇f = 0 一次把機場位置算出來？）
**Answer**: (a) 12. There are 6 variables (x1, y1, x2, y2, x3, y3). We move only one variable at a time, by +δ or −δ, so 6 × 2 = 12 successors. Any local search algorithm (e.g., hill climbing) can then be applied.
(b) In many cases ∇f = 0 cannot be solved in closed form. Here the gradient depends on which cities are closest to each airport in the current state (the sets Ci), e.g., ∂f/∂x1 = 2Σ(c ∈ C1)(x1 − xc). The sets Ci change as the airports move, so the expression is only locally correct, and we update step by step instead. For fixed Ci, setting it to 0 puts each airport at the mean position of its cities.
中文：離散化是一次只挑一個變數（x1、y1、x2、y2、x3、y3 之一），只能加 δ 或減 δ，所以 6 個變數 × 2 個方向 = 12 個鄰居；有了固定數量的鄰居，就能直接套用爬山法之類的局部搜尋演算法。至於梯度那條路，因為「哪些城市屬於哪座機場」（也就是 Ci）會隨機場位置改變，梯度公式只在目前位置附近正確，沒辦法寫成一條公式一次解出答案，只能一步一步更新；如果 Ci 固定不變，解 ∇f=0 的結果會是每座機場移到它負責城市的平均位置（重心）。
2. Write the steepest-ascent hill climbing update rule for a continuous state space. What do ∇f(x) and α control, and what happens if α is too small or too large?
Q2. Write the steepest-ascent hill climbing update rule for a continuous state space. What do ∇f(x) and α control, and what happens if α is too small or too large?（中文：寫出連續狀態空間裡最陡上升爬山法的更新式。∇f(x) 和 α 各控制什麼？如果 α 太小或太大會發生什麼事？）
**Answer**: x ← x + α∇f(x). The gradient ∇f gives the magnitude and direction of the steepest slope, so it decides the direction; the step size α decides how far to move. If α is too small, too many steps are needed; if α is too large, the search could overshoot the maximum. Line search addresses this by extending the current gradient direction until f starts to decrease again.
中文：更新式是 x ← x + α∇f(x)。梯度 ∇f 決定往哪個方向走（因為它同時給出最陡坡度的方向和大小），步長 α 決定這一步走多遠。α 太小，會需要走很多小碎步才能到達最高點；α 太大，可能會一步跨過最高點，反而讓數值變差，這叫衝過頭（overshoot）。line search（線搜尋）就是用來解決「α 該抓多少」的辦法：沿著梯度方向一直延伸，直到函數值開始變差才停。
3. Optimization problems are usually rewritten as minimizing a cost or loss. Why is this preferred, how do you turn "maximize f" into a minimization problem, and how does the update rule change?
Q3. Optimization problems are usually rewritten as minimizing a cost or loss. Why is this preferred, how do you turn "maximize f" into a minimization problem, and how does the update rule change?（中文：最佳化問題通常會改寫成最小化 cost 或 loss。為什麼要這樣做？要怎麼把「最大化 f」改寫成最小化問題？更新式會怎麼變？）
**Answer**: Maximizing can make the numbers grow without bound (overflow), while a loss is normally bounded below by 0, so minimizing drives it toward 0 safely. Maximizing f is the same as minimizing −f, or you can count something that should be small (e.g., the number of attacking queen pairs, where 0 means solved). To minimize, move against the gradient: x ← x − α∇f(x) (gradient descent).
中文：最大化容易讓數字一路變大甚至爆掉（overflow，超出電腦能存的範圍），而 loss（損失）通常最小是 0，不會有這個問題，所以大家習慣把問題改寫成最小化 cost 或 loss。把「最大化 f」變成最小化，最直接是加負號：最大化 f 等於最小化 −f，答案一樣；也可以換算一個「越小越好」的量，例如原本數「互不攻擊的皇后對數」越大越好，改成數「互相攻擊的皇后對數」就變成越小越好、最小是 0。改成最小化之後，更新式的方向要反過來，從「往梯度方向加」變成「往梯度反方向減」：x ← x − α∇f(x)，也就是梯度下降（gradient descent）。
4. What does the Newton–Raphson method solve? Give its update formula and apply one step to g(x) = x² − 2 starting from x = 1.
Q4. What does the Newton–Raphson method solve? Give its update formula and apply one step to g(x) = x² − 2 starting from x = 1.（中文：牛頓法是用來解什麼問題的？寫出它的更新公式，並從 x = 1 出發，對 g(x) = x² − 2 算一步。）
**Answer**: It finds roots of a function, i.e., it solves g(x) = 0. Update: x ← x − g(x)/g′(x). Here g′(x) = 2x, so x = 1 − (−1)/2 = 1.5.
中文：牛頓法是用來找一個函數的根，也就是解 g(x) = 0 這種方程式。更新公式是 x ← x − g(x)/g′(x)。代入 g(x) = x² − 2，g′(x) = 2x，從 x = 1 開始：g(1) = 1 − 2 = −1，g′(1) = 2，所以下一步是 x = 1 − (−1)/2 = 1.5。這一步就是沿著 x=1 那個點的切線，找切線跟 0 的交點，當作新的猜測值。
讀完了嗎？下一章：[05 牛頓法與線性規劃（1:40–2:04）](https://app.notion.com/p/3e6fc631b03081f79e51ec7d5af80d42)｜回到週頁：[W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62)