[人工智慧導論](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)
## 重點
- 連續空間也能做局部搜尋：蓋三座機場的解是六維向量 (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
- **State space (three airports)**: "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）
- **Ci (closest-airport set)**: "Let Ci be the set of cities whose closest airport (in the current state) is airport i."（Ch4 p.17）
- **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）
- **Gradient ∇f**: "The gradient of the objective function is a vector ∇f that gives the magnitude and direction of the steepest slope."（Ch4 p.18）
- **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）
- **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）
- **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）
- **Step size α**: "If α is too small, too many steps are needed; if α is too large, the search could overshoot the maximum."（Ch4 p.20）
- **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）
- **Newton–Raphson x ← x − g(x)/g′(x)**: "This is a general technique for finding roots of functions—that is, solving equations of the form g(x)=0."（Ch4 p.20）
## [1:21:32](https://www.youtube.com/watch?v=S1km7opW6rw&t=4892s) 從離散到連續：蓋三座機場
前面的八皇后、爬山法、模擬退火、基因演算法，處理的大多是離散問題：皇后只能放在固定的格子上。這些方法都有一種「隨機試試看，鄰居比較好就換過去」的味道。如果問題本身在連續空間裡，其實有更有效率的做法。老師的例子：在羅馬尼亞地圖上蓋三座新機場，一個解就是三座機場的座標 (x1, y1, x2, y2, x3, y3)，也就是六維空間裡的一個點。
用生活例子講，「在六維空間找最佳解」是什麼意思？
想像你手上有三根圖釘，要釘在地圖上當機場。每根圖釘要兩個數字（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 會跟著機場位置變：機場一移動，某個城市可能改成離另一座機場比較近。
[[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\chapter_4_search_in_complex_environments_p017.png | 投影片 p.17：上半是目標函數 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 個鄰居。鄰居變成有限個之後，前面學過的爬山法、模擬退火等局部搜尋都能直接套用。
| 動哪座機場 | 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 是同一件事。
它到底怎麼運作？用上一段的例子爬一次
接上一段：機場 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）。
要先懂什麼？偏微分和梯度是什麼？
偏微分 ∂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)。上面的小例子在 (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 方向，前後是 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，之後越跳越遠 |
它到底怎麼運作？為什麼 α = 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:14)
## [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 寫成另一種「對很多問題最有效」的方法。考試照投影片寫。牛頓法怎麼拿來找最佳解，下一章接著講。
要先懂什麼？牛頓法的更新式為什麼長這樣？
在目前猜的 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. In the three-airports problem, the neighborhood is discretized with a fixed step ±δ. How many successors does each state have, and why?
答案是什麼？
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.
中文重點：一次只動一座機場的 x 或 y、加或減 δ，6 × 2 = 12 個鄰居。
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?
答案是什麼？
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.
中文重點：梯度管方向、α 管距離；太小走太久，太大衝過頭。
3. Why can't we simply solve ∇f = 0 to place the three airports in one shot?
答案是什麼？
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. For fixed Ci, setting it to 0 puts each airport at the mean position of its cities.
中文重點：Ci 會隨機場位置改變，梯度只在局部成立，沒有一次算完的封閉解。
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.
答案是什麼？
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 的根，一步從 1 跳到 1.5。