[人工智慧導論](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=0 找極值，但很多問題沒有 closed form 解——深度學習的幾百萬個參數也是用這套邏輯在找解。
- 沒有 closed form 解時，用「最陡上升」規則 x ← x + α∇f 一步步更新：梯度決定往哪個方向走海拔上升最快，α（step size）決定一次走多遠。α 太小要走很多步、太大會衝過山頂，兩者都不好；找最好的 α 又是另一個最佳化問題，可以用 line search 解決，牛頓法是其中有名的一種做法。
## Exam-ready
- **Objective function (airport placement)**: "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." (Ch4 p.16)
- **Six-dimensional state space**: "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 function definition (Ci)**: "Let Ci be the set of cities whose closest airport (in the current state) is airport i. The objective function is" (Ch4 p.17)
- **Discretized neighbors**: "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)
- **Steepest-ascent hill climbing**: "Given a locally correct expression for the gradient, we can perform steepest-ascent hill climbing by updating the current state according to the formula where α is a small constant often called the step size." (Ch4 p.19)
- **Step size α trade-off / line search**: "If α is too small, too many steps are needed; if α is too large, the search could overshoot the maximum. 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 method**: "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. It works by computing a new estimate for the root x according to Newton's formula" (Ch4 p.20)
## [1:21:32](https://www.youtube.com/watch?v=S1km7opW6rw&t=4892s) 從離散到連續：蓋三座機場
前面教的八皇后、遺傳演算法，解都是離散的（皇后位置只能是固定格子之一）。連續空間的問題其實可以有更有效率的做法，不用只靠隨機碰運氣挑鄰居。例子：在羅馬尼亞地圖上要蓋三座新機場，一個解就是三座機場的座標 (x1,y1)、(x2,y2)、(x3,y3)，這是一個六維向量，問題變成要在六維空間裡找到最好的一組座標。
## [1:24:13](https://www.youtube.com/watch?v=S1km7opW6rw&t=5053s) 目標函數：距離平方和
目標函數的意思是：把每個城市到「離它最近的那座機場」的距離平方，全部加起來，這個總和要越小越好。Ci 代表離第 i 座機場最近的那群城市，所以目標函數就是對每座機場、加總它負責的城市距離平方。這座機場負責的城市越多、離得越遠，對總和的貢獻就越大，所以機場位置要選在能讓大家都近的地方。
它到底怎麼運作？（手算一個小例子）
假設只有一座機場，離它最近的城市有兩個：城市 A 距離 3、城市 B 距離 4。這座機場對目標函數的貢獻就是 3²+4²=9+16=25。如果還有第二座機場，負責另外三個城市，分別距離 2、1、2，貢獻是 2²+1²+2²=4+1+4=9。兩座機場加起來，目標函數值是 25+9=34。這個 34 就是我們要讓它越小越好的數字。
## [1:25:38](https://www.youtube.com/watch?v=S1km7opW6rw&t=5138s) 最大化改寫成最小化
最佳化問題原則上可以寫成「要最大化目標函數」，也可以寫成「要最小化目標函數」，兩種寫法都成立。但業界習慣統一改寫成「最小化 cost 或 loss」，因為在數學上，數字一路變大容易讓數值爆掉（overflow），而 loss 的最小值通常就是 0，不會有這個問題。所以就算某個問題概念上是「要最大化」，實際操作時也會把數學式子改寫成「最小化某個 cost」。【老師強調】(1:25:38)
老師原話是什麼？（已改正 ASR 錯字）
「那請大家記得，當我們在找所謂的最佳解，我們在找，我們在做最佳化的時候，剛剛我們前面舉的例子，都是說我們要最大化，那個 objective function value，這 OK 沒問題，那我們有的時候呢，我們是要去最小化，那個 objective function value，也 OK，只不過普遍來講，在整體而言各式各樣不同的，最佳化的這個工作裡面，我們傾向於，把問題都轉成，我們要去最小化這個 cost，我們稱呼它叫做 cost，或者叫做 loss，因為在數學上，你要去最大化一個東西，容易造成那個數字會爆掉，那如果是最小化那個 loss，因為 loss 會，一般來講，一般正常的情況下，loss 最小等於 0，所以我們去 minimize 這個 loss，或 minimize 這個 cost，我們一路就會，最小化到接近 0，它不會產生出，那個數值的 overflow。」(1:25:38)「即使在概念上我們要去最大化某一個 objective function value，我們也會把數學改寫一下，變成是我們要去最小化那個 cost。」(1:26:44)
## [1:27:01](https://www.youtube.com/watch?v=S1km7opW6rw&t=5221s) 離散化：12 個鄰居
連續空間裡，x 跟 y 座標有無限多種可能變化，不能像八皇后一樣直接列出所有鄰居。老師的妥協做法是：每次只挑一座機場的 x 或 y 來動，而且每次一定是加 δ 或減 δ，不做其他變動。3 座機場、每座機場有 x 跟 y 兩個變數、每個變數又能加或減，所以每個狀態剛好有 12 個鄰居，就能直接套用前面教過的局部搜尋。
它到底怎麼運作？（手算 12 個鄰居）
| 機場 | 可變動的變數 | 變動方式 |
|---|---|---|
| 1 | x1 | +δ 或 −δ |
| 1 | y1 | +δ 或 −δ |
| 2 | x2 | +δ 或 −δ |
| 2 | y2 | +δ 或 −δ |
| 3 | x3 | +δ 或 −δ |
| 3 | y3 | +δ 或 −δ |
6 個「變數」×每個變數 2 種變動方向（加 δ 或減 δ）= 12 個鄰居。也可以想成：3 座機場 ×（x 或 y，2 種選擇）×（加或減 δ，2 種選擇）= 3×2×2 = 12。
## [1:29:02](https://www.youtube.com/watch?v=S1km7opW6rw&t=5342s) 微分等於零求極值
如果從數學上正面解這個問題，可以直接在連續空間裡求極值：對六個變數各自做偏微分，把六個偏微分式都令它等於 0，解出來的那組 (x1,y1,...,x3,y3) 就是極值所在。這就是高中微積分教的口訣：對函數微分、令它等於 0、求解。老師特別提到深度學習裡幾百萬、幾億個參數，原則上也是用同一套邏輯在找最好的參數組合。但很多問題的偏微分式子太複雜，解不出一個 closed form（可以直接代入求解的數學式），這時候就沒辦法用這個方法。
要先懂什麼？（∇f = 0 是什麼意思）
一個函數如果有極大值或極小值，在那個點的切線斜率（也就是一次微分）一定是 0——因為切線斜率若不是 0，函數在那個點附近還在上升或下降，還不是極值。這裡的函數是六個變數 (x1,y1,x2,y2,x3,y3)，所以「對它微分」其實是對六個變數各自做偏微分，得到六條式子，再把六條式子同時令它們等於 0、聯立求解。這一組解出來的六個數字，就是讓目標函數有極值的機場位置。
老師原話是什麼？（1:30:17，不確定是否為考試範圍）
「我們在這門課裡面，不會告訴你為什麼。因為你有興趣的話，你可以去修最佳化導論，那是一門博大精深的課，我們這裡沒辦法跟大家講為什麼。」(1:30:17) 注意：老師只說「不會告訴你」，沒有明說「不考」，但這學期不會解釋「一次微分令它等於 0 為什麼能找到極值」的數學原理。
## [1:33:09](https://www.youtube.com/watch?v=S1km7opW6rw&t=5589s) 最陡上升的更新式
沒有 closed form 解的時候，就沒辦法一步解出答案，只能用「最陡上升」（steepest-ascent hill climbing）一步一步逼近：x ← x + α∇f，也就是拿目前的 x，加上 α 倍的梯度，得到新的 x。梯度 ∇f 負責決定往哪個方向走、目標函數上升最快，α 則負責決定一次走多遠。這其實跟山坡爬山的比喻一樣：海拔高度就是目標函數值，對 x 方向做偏微分，就是問「往右走一步，海拔會上升還是下降、上升多少」。
用生活例子講，梯度在做什麼？（老師的爬山比喻）
想像你站在一個山坡上，海拔高度就是目標函數值。往右邊走的方向叫 X 軸，往前走的方向叫 Y 軸。「對 X 做偏微分」的意思就是：如果我往右邊走一個單位，海拔高度會怎麼變——上升 1 公尺，還是下降 0.5 公尺？這個變化量就叫做「X 方向上的梯度」。同理也可以在 Y 方向做偏微分，得到「Y 方向上的梯度」。把兩個方向的梯度合在一起，就是一個向量，告訴你往哪個方向走、海拔上升最快。這就是梯度（∇f）真正的意思；至於 α，則是決定「照著這個方向，要走多遠」。
## [1:36:45](https://www.youtube.com/watch?v=S1km7opW6rw&t=5805s) 步長 α 太大太小都不好
決定好往哪個方向走之後（梯度負責這件事），還要決定一次走多遠，這就是 α（step size）的工作。α 太小，雖然方向是對的，但每次只走一小步，要走非常多步才能爬到最高點。α 太大，可能一次就衝過山頂、跑到山的另一頭，海拔高度反而下降，等於白走。
它到底怎麼運作？（老師舉的 150 公尺例子）
老師舉例：假設往右邊走 150 公尺，海拔提升量最大，是最好的 α 對應的距離。如果 α 太小，每次只走一小碎步，要走很多次才會累積到 150 公尺，很慢。如果 α 太大，例如一次直接衝兩公里，那就遠遠超過 150 公尺這個最佳點，可能已經翻過山頭、開始往下坡走，海拔反而降低了。
## [1:38:48](https://www.youtube.com/watch?v=S1km7opW6rw&t=5928s) Line search 與牛頓法
「α 要走多遠」本身又是一個最佳化問題，line search 的做法就是沿著目前的梯度方向一路走，直到目標函數開始下降為止，藉此找出最好的 α。老師接著提到牛頓法（Newton–Raphson），原本是用來解 g(x)=0（求函數的根）：先隨便猜一個 x，再用 x ← x − g(x)/g′(x) 不斷修正。注意：老師口頭把牛頓法說成是 line search 的一種做法，但投影片是把它當成另一種更有效的方法，直接解 ∇f(x)=0。
老師原話跟投影片不同在哪裡？
投影片（Ch4 p.20）寫的是：「For many problems, the most effective algorithm is the Newton–Raphson method... solving equations of the form g(x)=0... computing a new estimate for the root x according to Newton's formula.」老師口頭（1:38:54、1:44:29、1:47:11）把牛頓法講成是「line search 裡面很有名的一種做法」，用來找最好的 α；但課本與投影片 p.20、p.23 是把 Newton–Raphson 當成另一種比 line search 更有效的方法，直接解 ∇f(x)=0，更新式是 x ← x − H⁻¹∇f（H⁻¹ 是 Hessian 矩陣的反矩陣）。這兩種說法核心概念相通（都是不斷修正一個估計值，讓它逼近某個方程式的解），但用途上老師講得比投影片更窄。寫筆記時照投影片寫，並註明「注意：老師口頭說的是把牛頓法當成 line search 的一種做法」。
## Self-check
1. In the airport-placement problem, why is the state space six-dimensional, and what quantity is the objective function trying to minimize?
Answer
Each solution is defined by the coordinates of three airports: (x1,y1), (x2,y2), (x3,y3) — six real-valued variables, so the state space has six dimensions. The objective function sums, over every city, the squared distance from that city to its nearest airport, and the search tries to minimize that total sum.
中文重點：解是三座機場的六個座標值，構成六維空間；目標函數是所有城市到最近機場距離平方的總和，要最小化它。
2. Optimization problems are usually rewritten as "minimize cost/loss" rather than "maximize the objective." Why?
Answer
Maximizing a value mathematically tends to let numbers grow without bound, which can cause numerical overflow. A loss/cost function's minimum is typically 0, so minimizing it keeps values bounded and avoids overflow — even when the underlying goal is conceptually a maximization, it gets rewritten as minimizing some cost.
中文重點：最大化容易讓數值爆掉，loss 最小是 0 比較安全，所以習慣把問題改寫成最小化 cost。
3. Write the steepest-ascent hill climbing update rule. What role does ∇f play, and what role does α play? What happens if α is set too large or too small?
Answer
The update rule is x ← x + α∇f. The gradient ∇f determines the direction of steepest increase (which way to move). The step size α determines how far to move in that direction. If α is too small, the search needs many steps to reach the maximum; if α is too large, the search can overshoot the maximum and the objective value may actually decrease.
中文重點：x←x+α∇f，梯度決定方向，α 決定走多遠；α 太小走太慢，太大會衝過頭讓高度下降。
4. What was Newton–Raphson's original purpose, and how does the lecturer's description of it differ from what the slides say?
Answer
Newton–Raphson is originally a general technique for finding roots of a function — i.e., solving g(x)=0 — by iterating x ← x − g(x)/g'(x). The lecturer described it as one particular way of doing line search to find a good step size α. The slides, however, present Newton–Raphson as a separate, often more effective alternative to line search that solves ∇f(x)=0 directly, with the update x ← x − H⁻¹∇f.
中文重點：牛頓法原本是求根 g(x)=0 的方法；老師說它是 line search 的一種，投影片則說它是取代 line search、直接解 ∇f=0 的另一種方法，寫筆記以投影片為準。