[人工智慧導論](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
- **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）
- **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）
- **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**: "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）
- **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 α**: "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）
- **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)**: "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）
## [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 會跟著機場位置變：機場一移動，某個城市可能改成離另一座機場比較近。
它到底怎麼運作？用四個城市手算一次 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)。上面的 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 方向，前後是 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: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 寫成另一種「對很多問題最有效」的方法，以投影片的說法為準。牛頓法怎麼拿來找最佳解，下一章接著講。
要先懂什麼？牛頓法的更新式為什麼長這樣？
在目前猜的 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?
答案是什麼？
(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.
中文重點：離散化是一次只動一個變數 ±δ，6 × 2 = 12 個鄰居；梯度那條路因為 Ci 會變，只能局部算、一步一步走。
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. 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?
答案是什麼？
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).
中文重點：最大化容易數值爆掉，loss 最小是 0；改成最小化後，更新式的加號變減號。
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。