[人工智慧導論](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) ## 重點 - 變數可以是任何實數時（連續空間），每個狀態旁邊有無限多個鄰居。課本的例子是「在羅馬尼亞蓋三座機場」：決定六個座標，讓每個城市到最近機場的距離平方加總最小。 - 兩條路：一是離散化（每次只把一座機場往 x 或 y 挪 ±δ，每個狀態只有 12 個鄰居，再套前面的爬山法）；二是用梯度（gradient，往哪個方向上升最快）直接算：解 ∇f = 0，解不出來就一步一步走 x ← x + α∇f(x)。 - 梯度決定方向，步長 α 決定走多遠：太小走太久，太大會衝過頭。挑 α 本身又是一個最佳化問題，可以用 line search；投影片最後帶出求根用的牛頓法 x ← x − g(x)/g′(x)。 ## Exam-ready - **Continuous 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."（Ch4 p.16） - **Six variables**: "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**: "Let Ci be the set of cities whose closest airport (in the current state) is airport i. The objective function is" f(x1, y1, x2, y2, x3, y3) = Σᵢ₌₁³ Σ(c∈Ci) (xi − xc)² + (yi − yc)²（Ch4 p.17，公式從投影片圖讀出） - **Discretization**: "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**: "The gradient of the objective function is a vector ∇f that gives the magnitude and direction of the steepest slope." ∇f = (∂f/∂x1, ∂f/∂y1, ∂f/∂x2, ∂f/∂y2, ∂f/∂x3, ∂f/∂y3)（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**: "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; for example," ∂f/∂x1 = 2 Σ(c∈C1) (xi − xc)（Ch4 p.19；式中的 xi 就是 x1） - **Steepest-ascent update**: "Given a locally correct expression for the gradient, we can perform steepest-ascent hill climbing by updating the current state according to the formula x ← x + α∇f(x) where α is a small constant often called the step size."（Ch4 p.19） - **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**: "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" x ← x − g(x)/g′(x)（Ch4 p.20） ## [1:21:32](https://www.youtube.com/watch?v=S1km7opW6rw&t=4892s) 從離散到連續：蓋三座機場 前面的八皇后是離散（discrete，只能從有限個選項裡挑）問題：皇后只能放在某一格。老師說爬山法、模擬退火、基因演算法都帶一種「試試看」的隨機感；如果問題在連續（continuous，可以是任何實數）空間，有更有效率的做法。課本的例子：在羅馬尼亞蓋三座新機場，要決定 (x1, y1)、(x2, y2)、(x3, y3) 六個數字，所以一個解就是六維空間裡的一個點，也可以說「狀態由六個變數（variables）定義」。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\ai_ch3_p004.png | 羅馬尼亞地圖（Ch3 p.4，上週找路用的那張）。這一章的問題：在這張圖上放三座機場]]
用生活例子講，離散和連續差在哪？ 離散像電梯：只能停 1 樓、2 樓、3 樓，鄰居數得出來。連續像溜滑梯：任何高度都可能，1.5 樓、1.4999 樓都算。 八皇后每欄 8 格挑一格，總共 8⁸ = 16,777,216 種盤面，很多但數得完。機場座標可以是 23.517… 這種任何實數，一個狀態旁邊有無限多個鄰居，沒辦法像爬山法那樣「看一圈鄰居、挑最好的」。 「六維」不用畫出來：一個狀態就是六個數字一組，例如 (2, 3, 5, 1, 7, 4) 代表機場 1 在 (2, 3)、機場 2 在 (5, 1)、機場 3 在 (7, 4)。 所以對你的影響是：這一章每個方法都在回答同一個問題——鄰居數不完時，下一步要往哪走。
老師原話是什麼？ 「但在某一些問題呢，其實我們是可以有更有效率的解法的」(1:22:34) 「我們要決定一個六維的向量，代表這三座機場的位置」(1:24:00)
## [1:24:13](https://www.youtube.com/watch?v=S1km7opW6rw&t=5053s) 目標函數：距離平方和 目標：每個城市找離它最近的機場，量距離、平方，全部加起來，越小越好。投影片先定義 Ci：「目前離第 i 座機場最近的城市」的集合。目標函數是 f(x1, y1, x2, y2, x3, y3) = Σᵢ₌₁³ Σ(c∈Ci) [(xi − xc)² + (yi − yc)²]。外層 Σ 跑三座機場，內層 Σ 跑分給這座機場的城市，括號裡是城市 c 到機場 i 的距離平方。
兩座機場、三個城市時，f 怎麼算？ 城市 A(0, 0)、B(4, 0)、C(2, 6)。機場 1 在 (0, 0)，機場 2 在 (3, 5)。 1. 先分組。A：到機場 1 是 0，到機場 2 是 9 + 25 = 34，歸機場 1。B：到機場 1 是 16，到機場 2 是 1 + 25 = 26，歸機場 1。C：到機場 1 是 4 + 36 = 40，到機場 2 是 1 + 1 = 2，歸機場 2。所以 C1 是 A、B，C2 是 C。 2. 加總：f = (0 + 16) + 2 = 18。 重點：機場一動，分組可能跟著變（例如機場 2 往下移，B 可能改歸它）。所以 Ci 只在「目前狀態」下成立，這一點後面會用到。
要先懂什麼？Σ 符號怎麼讀？ Σ(c∈C1) (x1 − xc) 讀成「把 C1 裡每個城市 c 的 (x1 − xc) 加起來」，∈ 是「屬於」。兩個 Σ 疊在一起就是兩層迴圈：外層跑機場，內層跑這座機場負責的城市。
## [1:25:38](https://www.youtube.com/watch?v=S1km7opW6rw&t=5138s) 最大化改寫成最小化 【老師強調】(1:25:38) 八皇后是「最大化」fitness，機場是「最小化」距離，兩種都可以。但老師提醒：最佳化問題普遍習慣改寫成最小化 cost（成本）或 loss（損失）。他的理由：最大化容易讓數字爆掉；loss 一般最小是 0，一路最小化到接近 0，不會 overflow（數值超出電腦能表示的範圍）。所以就算概念上是最大化，也會把數學改寫成最小化 cost。
最大化要怎麼改寫成最小化？ 最通用的方法：max f 和 min (−f) 找到的 x 一樣。 更自然的方法：改問「離完美還差多少」。八皇后一共有 28 對皇后（8 個挑 2 個）。上一章的 fitness 是「互不攻擊的對數」，要最大化，最好是 28；改寫成 cost h = 28 − fitness，也就是「互相攻擊的對數」，要最小化，最好是 0。例：fitness 24 的盤面，h = 4。 所以對你的影響是：之後看到 loss、cost、error，一律是「越小越好、最好是 0」，深度學習的訓練也是這樣寫。
老師原話是什麼？ 「那請大家記得，當我們在找所謂的最佳解」(1:25:38) 「因為在數學上你要去最大化一個東西，容易造成那個數字會爆掉」(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 個鄰居（successors）；投影片的算法是 6 個變數 × 2 個方向 = 12。這樣就能直接套用前面的爬山法、模擬退火等局部搜尋。
δ = 1 的爬山法實際跑起來長怎樣？ 為了好算，只放一座機場（2 個變數，4 個鄰居）。城市 A(0, 0)、B(4, 0)、C(2, 6)，機場從 (0, 0) 出發，每次看 x ± 1、y ± 1 四個鄰居，走到 f 最小的那個。
步目前位置f四個鄰居的 f走到
0(0, 0)56(1,0)=47、(−1,0)=71、(0,1)=47、(0,−1)=71(1, 0)（平手挑一個）
1(1, 0)47(2,0)=44、(0,0)=56、(1,1)=38、(1,−1)=62(1, 1)
2(1, 1)38(2,1)=35、(0,1)=47、(1,2)=35、(1,0)=47(2, 1)（平手挑一個）
3(2, 1)35(3,1)=38、(1,1)=38、(2,2)=32、(2,0)=44(2, 2)
4(2, 2)32四個都是 35停，沒有更好的鄰居
最佳解 (2, 2) 剛好在整數格上。如果最佳解在 (2.3, 1.7)，δ = 1 只能停在它附近的格點，這就是「妥協」：δ 越小越準，但要走越多步。
老師原話是什麼？ 「這是一個妥協的方案」(1:27:32) 「所以整體而言呢，我一定只會有 12 個鄰居」(1:28:26)
## [1:29:02](https://www.youtube.com/watch?v=S1km7opW6rw&t=5342s) 微分等於零求極值 更好的做法是直接在連續空間找極值。老師提到的高中口訣是「對它進行一次微分，令它等於 0，然後求解」(1:29:41)。這裡有六個變數，所以要對 x1、y1、x2、y2、x3、y3 各做一次偏微分（partial derivative，只讓一個變數動、其他固定時的變化率），六個全部令為 0。六個偏微分排成一個向量就是梯度 ∇f，所以條件寫成 ∇f = 0。問題是很多函數解不出 closed form（封閉解：整理成一條公式，代進去就得到答案）。老師說深度學習動輒幾百萬、幾億個參數，找最好那組參數的原則跟這裡一樣。 **注意：為什麼「一次微分令它等於 0」就找得到極值，老師說這門課不講，有興趣去修最佳化導論 (1:30:17)。**
要先懂什麼？偏微分和梯度是什麼？ 偏微分：多變數函數裡只讓一個變數動，其他當常數，算變化率。 例：f(x, y) = x² + 3xy。對 x 偏微分（y 當常數）得 2x + 3y；對 y 偏微分（x 當常數）得 3x。 在 (1, 2)：∂f/∂x = 2 + 6 = 8，∂f/∂y = 3，所以 ∇f(1, 2) = (8, 3)。意思是往 x 方向走 0.01，f 大約多 0.08；往 y 方向走 0.01，f 大約多 0.03。 梯度就是把所有偏微分排成一個向量。它指向上升最快的方向，長度代表有多陡，也就是投影片說的 magnitude and direction of the steepest slope。
為什麼山頂的斜率會是 0？ 直覺版：站在山頂，腳下是平的，往任何方向踏一小步都不會更高，所以每個方向的斜率都是 0。 反過來不一定成立：谷底、馬鞍形的點斜率也是 0，而且找到的可能只是小山頭（local maximum）。所以 ∇f = 0 是「候選點」，不保證是最好的解。
機場問題的 ∇f = 0 長什麼樣？為什麼還是解不出來？ 投影片 p.19 給了其中一個分量：∂f/∂x1 = 2 Σ(c∈C1) (xi − xc)。投影片寫 xi，這裡的 i 就是 1，也就是 (x1 − xc)。 令它等於 0：Σ(c∈C1) (x1 − xc) = 0，得到 x1 = C1 裡城市 x 座標的平均；y1 同理。也就是說，分組固定時，最佳機場位置就是那組城市的重心（平均座標）。 例：C1 是 A(0,0)、B(4,0)、C(2,6)，最佳位置 = ((0+4+2)/3, (0+0+6)/3) = (2, 2)，f = 32，跟上一段爬山法停下來的地方一樣。 那為什麼整體還是解不出 closed form？因為分組 Ci 取決於機場在哪：機場一動，有些城市會換到別的機場，式子就換了一條。所以投影片說梯度只能 locally（在目前狀態附近）算。
老師原話是什麼？ 「我們在這門課裡面不會告訴你為什麼」(1:30:17) 「Deep Learning 裡面隨隨便便就是幾百萬個參數，幾億個參數」(1:32:25) 「找到這最好的那一組幾百萬個參數的做法，跟我們現在在這裡在講的是一樣的做法」(1:32:39)
## [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) 決定往哪走（海拔上升最多的方向），α 決定走多遠（step size，步長）。老師的比喻：站在山坡上，海拔就是目標函數值；對 x 偏微分就是往右走一步海拔會變多少，對 y 偏微分就是往前走一步海拔會變多少。 **注意：投影片的式子是往上爬（找最大值）。機場問題要最小化，就把加號換成減號：x ← x − α∇f(x)，往梯度的反方向走，這叫 gradient descent（梯度下降），深度學習訓練用的就是它。**
梯度下降實際走一步是怎麼算的？ 同一組城市 A(0,0)、B(4,0)、C(2,6)，一座機場從 (0, 0) 出發，α = 0.1。 1. 算梯度：∂f/∂x = 2[(0−0) + (0−4) + (0−2)] = −12；∂f/∂y = 2[(0−0) + (0−0) + (0−6)] = −12。所以 ∇f = (−12, −12)。 2. 要最小化，用減號：新位置 = (0, 0) − 0.1 × (−12, −12) = (1.2, 1.2)。 3. f 從 56 降到 35.84。 再走兩步：(1.68, 1.68)，f = 32.61；(1.872, 1.872)，f = 32.10，逐漸逼近最佳的 (2, 2)、f = 32。
用生活例子講，最陡上升在做什麼？ 起霧的山上看不到山頂。你能做的只有：用腳感覺哪個方向往上最陡（梯度），朝那邊走幾步（α），再重新感覺一次。每一步都挑最陡的方向，所以叫「最陡上升」。
老師原話是什麼？ 「我如果往右邊走一個單位的話，我的海拔高度會怎麼變動」(1:35:19) 「我這裡是決定方向」(1:36:31)
別人怎麼教這個？ - [Khan Academy：Partial derivatives, introduction](https://www.youtube.com/watch?v=AXqhWeUEtQU) - [Khan Academy：Gradient](https://www.youtube.com/watch?v=tIpKfDc295M) - [3Blue1Brown：Gradient descent, how neural networks learn](https://www.youtube.com/watch?v=IHZwWFHWa-w)
## [1:36:45](https://www.youtube.com/watch?v=S1km7opW6rw&t=5805s) 步長 α 太大太小都不好 α 是要自己決定的參數。太小：每次小碎步，要走很多步才到山頂。太大：方向對了卻一口氣衝太遠，越過山頂跑到另一頭，高度反而下降（overshoot）。老師的總結是「過猶不及」。
同一個起點換不同 α，第一步會走到哪？ 沿用上一段：起點 (0, 0)，f = 56，∇f = (−12, −12)，最佳值是 32。
α第一步走到f結果
0.01(0.12, 0.12)53.21太小：約 45 步才降到 32.1 以內
0.1(1.2, 1.2)35.84不錯：3 步就到 32.10
1/6 ≈ 0.167(2, 2)32一步到位，這題剛好的完美步長
0.25(3, 3)38衝過頭，但還比起點好
0.5(6, 6)128太大：比起點還糟，再走是 416、1568，越跳越遠
老師原話是什麼？ 「一口氣就衝兩公里」(1:37:46) 「越過山丘，又跑到山的另外一頭，你的高度搞不好還會下降」(1:37:50) 「所以過猶不及」(1:37:58)
## [1:38:48](https://www.youtube.com/watch?v=S1km7opW6rw&t=5928s) Line search 與牛頓法 梯度決定方向，但走多遠最好，又是另一個最佳化問題。投影片的解法是 line search（線搜尋）：方向固定成目前的梯度方向，沿著這條線一直往前延伸，直到 f 開始變差（找最大值時就是開始下降）才停。接著投影片介紹 Newton–Raphson method（牛頓法）：通用的求根方法，用來解 g(x) = 0。做法是先亂猜一個 x，再用 x ← x − g(x)/g′(x) 反覆更新（g′ 是 g 的一次微分）。找極值就是找 ∇f = 0 的根，所以牛頓法也能拿來找極值；下一章會把 g 換成 ∇f、g′ 換成 Hessian 矩陣（所有二次偏微分排成的矩陣）。 **注意：老師口頭說的是「line search 有很多種做法，那其中很有名的呢就是牛頓法」(1:39:04)；投影片 p.20 則是 "For many problems, the most effective algorithm is the Newton–Raphson method"，把牛頓法當成另一個（通常最有效的）方法，直接拿來解方程式。考試寫投影片的版本。**
Line search 實際怎麼挑 α？ 沿用上一段：起點 (0, 0)，要最小化，所以沿著 −∇f = (12, 12) 的方向走，位置是 (12α, 12α)。α 每次加 0.05 試一次： - α = 0.05，f = 43.76 - α = 0.10，f = 35.84 - α = 0.15，f = 32.24 - α = 0.20，f = 32.96，開始變差，停 所以這一步取 α = 0.15，走到 (1.8, 1.8)。真正最好的 α 是 1/6，差一點點；想更準就把試的間隔縮小。
牛頓法怎麼算出 √2？ 求 √2 就是解 g(x) = x² − 2 = 0，g′(x) = 2x。從 x = 1 開始猜： - 第 1 次：1 − (1 − 2)/(2 × 1) = 1.5 - 第 2 次：1.5 − (2.25 − 2)/3 = 1.41667 - 第 3 次：1.41667 − 0.00694/2.83333 = 1.414216 真正的 √2 = 1.414214，三步就對到小數第五位。
老師說牛頓法是 line search 的一種，哪裡講得通？ 牛頓法本質是解方程式。line search 要找最好的 α，等於找一維函數 φ(α) = f(x + α∇f(x)) 的極值，也就是解 φ′(α) = 0，這確實可以用牛頓法解，所以老師的說法講得通。但投影片的定位是：牛頓法本身就是找極值的演算法，直接解 ∇f = 0。考試照投影片寫。
老師原話是什麼？ 「你要走多遠，其實這又是另外一個最佳化的問題」(1:38:26) 「牛頓法用來找，求一個 function 的 root」(1:39:22) 「我先隨便亂猜一個 x，然後我再去 update 這個 x」(1:40:08) 「或者是你可以回去翻一下你以前的數學書」(1:39:48)
## Self-check
Q1. In the airport-placement problem, define the state space and the objective function. After discretization, how many successors does each state have, and why? **Answer**: A state is (x1, y1, x2, y2, x3, y3), a six-dimensional space. With Ci the set of cities whose closest airport is airport i, we minimize f = Σᵢ₌₁³ Σ(c∈Ci) [(xi − xc)² + (yi − yc)²]. Moving one airport at a time in x or y by ±δ gives 6 variables × 2 = 12 successors, so any earlier local search algorithm applies. 中文重點：六維狀態、距離平方和、6 個變數 × ±δ = 12 個鄰居。
Q2. Write the steepest-ascent update rule for continuous spaces. What do ∇f and α each control, and what goes wrong if α is too small or too large? **Answer**: x ← x + α∇f(x). ∇f gives the direction (and magnitude) of the steepest slope, so it decides where to move; the step size α decides how far. If α is too small, too many steps are needed; if α is too large, the search could overshoot the maximum. Line search extends the current gradient direction until f starts to decrease again. 中文重點：梯度管方向、α 管距離；太小太慢、太大衝過頭；line search 沿梯度方向延伸到 f 開始下降。
Q3. Why can the airport problem not simply be solved by setting ∇f = 0? What does it mean that the gradient is computed "locally"? **Answer**: The gradient depends on which cities are closest to each airport in the current state (the sets Ci). With Ci fixed, ∂f/∂x1 = 2 Σ(c∈C1) (x1 − xc) = 0 gives the centroid of C1, but moving an airport changes the Ci, so ∇f = 0 has no closed-form solution overall. The gradient is only correct near the current state, so we compute it locally and take small steps. 中文重點：Ci 會隨機場位置改變，梯度式子只在目前狀態附近成立，所以只能一步一步走。
Q4. What does the Newton–Raphson method solve, what is its update formula, and how does it relate to finding a maximum of f? **Answer**: It is a general technique for finding roots of functions, i.e., solving g(x) = 0, by repeatedly updating the estimate with x ← x − g(x)/g′(x). A maximum or minimum of f is where ∇f(x) = 0, so we set g(x) = ∇f(x) and apply Newton's method (in many dimensions this uses the Hessian matrix). 中文重點：牛頓法求根；找極值 = 求 ∇f = 0 的根。