90分鐘 · 100分 · 7道大題。原創自主練習，不是官方考試規格或權重預測。回答所有小問，寫清計算與證明，盡量保留精確值；需要小數答案時說明捨入方法；特徵向量及配對奇異向量一致反號可接受。以題面分母、定義域及平局規則為準，不可無條件求逆。本練習使用Casio fx-50FH II，可用一張雙面A4參考紙；這是練習安排，不是新增官方考試規定。
配套題本 · Revision
評分用於自評；等價正確方法同分。單一算術錯誤後若方法正確，應保留相應方法分，不反覆扣同一錯誤。請先讀題本；以下說明條件與核對，不只列答案。
Q1. 最小二乘與反應變換 (16)
配套題本 Q1
(a) [6]
未知向量含截距與斜率；對殘差平方範數求導。逐項匯總後得到矩陣，再消元求參數。正行列式證明滿欄秩，不能只用樣本數多於參數數作理由。
未知量只有兩個實數係數，所以c屬於二維實向量空間；四個觀測貢獻四行，而不是四個待估係數。第一欄全為1，是為了讓每行都包含同一個截距。目標是殘差平方和最小，不要求四條觀測方程全部精確成立。最後一個乘積先把每個x與自己的反應相乘，再相加：−1+0+2+10=11。把第一條正規方程除以2，再將所得b代入第二條即可消元。最後應寫出對新x返回反應的擬合函數，不能只列兩個係數。
M = ( 1 − 1 1 0 1 1 1 2 ) , y = ( 1 2 2 5 ) , c = ( a b ) . ∇ c ∥ y − M c ∥ 2 = 2 M T ( M c − y ) = 0. ∑ x i = 2 , ∑ x i 2 = 6 , ∑ y i = 10 , ∑ x i y i = 11. ( 4 2 2 6 ) ( a b ) = ( 10 11 ) , 2 a + b = 5 , 10 b = 12. a ^ = 19 10 , b ^ = 6 5 , det ( M T M ) = 20 > 0. c ∈ R 2 , M ∈ R 4 × 2 , y ^ ( x ) = 19 10 + 6 5 x . \begin{gathered}
M=\begin{pmatrix}1&-1\\1&0\\1&1\\1&2\end{pmatrix},\quad y=\begin{pmatrix}1\\2\\2\\5\end{pmatrix},\quad c=\binom ab.
\\ \nabla_c\|y-Mc\|^2=2M^T(Mc-y)=0.
\\ \sum x_i=2,\quad\sum x_i^2=6,\quad\sum y_i=10,\quad\sum x_iy_i=11.
\\ \begin{pmatrix}4&2\\2&6\end{pmatrix}\binom ab=\binom{10}{11},\quad 2a+b=5,\quad 10b=12.
\\ \widehat a=\frac{19}{10},\quad\widehat b=\frac65,\quad\det(M^TM)=20>0.
\\ c\in\mathbb R^2,\quad M\in\mathbb R^{4\times2},\quad \widehat y(x)=\frac{19}{10}+\frac65x.
\end{gathered} M = 1 1 1 1 − 1 0 1 2 , y = 1 2 2 5 , c = ( b a ) . ∇ c ∥ y − M c ∥ 2 = 2 M T ( M c − y ) = 0. ∑ x i = 2 , ∑ x i 2 = 6 , ∑ y i = 10 , ∑ x i y i = 11. ( 4 2 2 6 ) ( b a ) = ( 11 10 ) , 2 a + b = 5 , 10 b = 12. a = 10 19 , b = 5 6 , det ( M T M ) = 20 > 0. c ∈ R 2 , M ∈ R 4 × 2 , y ( x ) = 10 19 + 5 6 x . 評分： 設計與目標2；方程及乘積2；係數1；唯一性1。
配套題本 Q1(a)
(b) [6]
逐點代入再以觀測減預測。兩條內積為零不代表每個殘差為零。自由截距使訓練均值常數模型可行；OLS最小化同一訓練RSS，故不差於該基線。亦可用殘差與中心化預測正交證明；不能直接推廣到測試集、無截距或變換反應目標。
TSS圍繞觀測均值計算，不是圍繞擬合值。先從1、2、2、5逐個減去5/2，再平方，四項如下。幾何核對時，在中心化反應中加減擬合向量。殘差既垂直於常數欄，也垂直於任何擬合向量Mc，因此亦垂直於中心化擬合向量；這樣才能對兩個向量用勾股定理。TSS為正也不能省略：若所有反應相同，這個R²定義會除以零。此處訓練R²非負，來自均值基線可行以及實際最小化的目標，而不是只要叫「回歸」就成立。
y ^ = 1 10 ( 7 , 19 , 31 , 43 ) T , r = 1 10 ( 3 , 1 , − 11 , 7 ) T . 1 T r = 3 + 1 − 11 + 7 10 = 0 , x T r = − 3 − 11 + 14 10 = 0. R S S = 9 + 1 + 121 + 49 100 = 9 5 , y ˉ = 5 2 , T S S = 9 , R 2 = 1 − 9 / 5 9 = 4 5 . 0 ≤ R S S O L S ≤ R S S ( y ˉ , 0 ) = T S S , T S S = R S S + ∥ y ^ − y ˉ 1 ∥ 2 = 9 5 + 36 5 . T S S = ( − 3 / 2 ) 2 + ( − 1 / 2 ) 2 + ( − 1 / 2 ) 2 + ( 5 / 2 ) 2 = 9 + 1 + 1 + 25 4 = 9. y − y ˉ 1 = r + ( y ^ − y ˉ 1 ) , r T ( y ^ − y ˉ 1 ) = r T M c ^ − y ˉ r T 1 = 0. \begin{gathered}
\widehat y=\frac1{10}(7,19,31,43)^T,\quad r=\frac1{10}(3,1,-11,7)^T.
\\ \mathbf1^Tr=\frac{3+1-11+7}{10}=0,\quad x^Tr=\frac{-3-11+14}{10}=0.
\\ \mathrm{RSS}=\frac{9+1+121+49}{100}=\frac95,\quad\bar y=\frac52,\quad\mathrm{TSS}=9,\quad R^2=1-\frac{9/5}{9}=\frac45.
\\ 0\le\mathrm{RSS}_{\mathrm{OLS}}\le\mathrm{RSS}(\bar y,0)=\mathrm{TSS},\qquad
\mathrm{TSS}=\mathrm{RSS}+\|\widehat y-\bar y\mathbf1\|^2=\frac95+\frac{36}5.
\\ \mathrm{TSS}=(-3/2)^2+(-1/2)^2+(-1/2)^2+(5/2)^2=\frac{9+1+1+25}{4}=9.\\y-\bar y\mathbf1=r+(\widehat y-\bar y\mathbf1),\quad r^T(\widehat y-\bar y\mathbf1)=r^TM\widehat c-\bar y r^T\mathbf1=0.
\end{gathered} y = 10 1 ( 7 , 19 , 31 , 43 ) T , r = 10 1 ( 3 , 1 , − 11 , 7 ) T . 1 T r = 10 3 + 1 − 11 + 7 = 0 , x T r = 10 − 3 − 11 + 14 = 0. RSS = 100 9 + 1 + 121 + 49 = 5 9 , y ˉ = 2 5 , TSS = 9 , R 2 = 1 − 9 9/5 = 5 4 . 0 ≤ RSS OLS ≤ RSS ( y ˉ , 0 ) = TSS , TSS = RSS + ∥ y − y ˉ 1 ∥ 2 = 5 9 + 5 36 . TSS = ( − 3/2 ) 2 + ( − 1/2 ) 2 + ( − 1/2 ) 2 + ( 5/2 ) 2 = 4 9 + 1 + 1 + 25 = 9. y − y ˉ 1 = r + ( y − y ˉ 1 ) , r T ( y − y ˉ 1 ) = r T M c − y ˉ r T 1 = 0. 評分： 殘差1；RSS1；TSS及R²2；正交1；基線或分解證明1。
配套題本 Q1(b)
(c) [4]
指數模型使用實對數，觀測及A、B必須為正；擬合截距與斜率取指數還原。倒數模型要求觀測非零，預測分母亦須非零；其係數無須反變換。兩者一般均不保證原尺度RSS最小；精確插值可能兩者一致，但不是普遍保證。
指數模型中，輸入x和設計矩陣的欄不變；改變的是反應向量，變成(0,log2,log2,log5)。指數逆變換還原A與B，但不能把已經優化的對數誤差自動改稱原尺度誤差。倒數模型中α、β本來就是原參數，無需再指數化；只在輸出預測時取倒數。最小二乘本身不負責保證未來分母遠離零。特殊的精確插值情形下，兩種尺度的最優解可能重合；一次重合不能證明一般等價。
z i = log y i , θ 0 = log A , θ 1 = log B , min θ ∑ i ( log y i − θ 0 − θ 1 x i ) 2 , A = e θ 0 , B = e θ 1 . z = ( 0 , log 2 , log 2 , log 5 ) T , M = ( 1 − 1 1 0 1 1 1 2 ) . t i = 1 / y i , N = ( 1 e 1 1 1 e − 1 1 e − 2 ) , t = ( 1 , 1 / 2 , 1 / 2 , 1 / 5 ) T , min α , β ∑ i ( 1 / y i − α − β e − x i ) 2 , y ^ ( x ) = 1 α + β e − x . \begin{gathered}
z_i=\log y_i,\quad\theta_0=\log A,\quad\theta_1=\log B,\quad
\min_\theta\sum_i(\log y_i-\theta_0-\theta_1x_i)^2,\quad A=e^{\theta_0},\ B=e^{\theta_1}.
\\ z=(0,\log2,\log2,\log5)^T,\quad M=\begin{pmatrix}1&-1\\1&0\\1&1\\1&2\end{pmatrix}.
\\ t_i=1/y_i,\quad N=\begin{pmatrix}1&e\\1&1\\1&e^{-1}\\1&e^{-2}\end{pmatrix},\quad t=(1,1/2,1/2,1/5)^T,
\\ \min_{\alpha,\beta}\sum_i(1/y_i-\alpha-\beta e^{-x_i})^2,\qquad \widehat y(x)=\frac1{\alpha+\beta e^{-x}}.
\end{gathered} z i = log y i , θ 0 = log A , θ 1 = log B , θ min i ∑ ( log y i − θ 0 − θ 1 x i ) 2 , A = e θ 0 , B = e θ 1 . z = ( 0 , log 2 , log 2 , log 5 ) T , M = 1 1 1 1 − 1 0 1 2 . t i = 1/ y i , N = 1 1 1 1 e 1 e − 1 e − 2 , t = ( 1 , 1/2 , 1/2 , 1/5 ) T , α , β min i ∑ ( 1/ y i − α − β e − x i ) 2 , y ( x ) = α + β e − x 1 . 評分： 每模型2分，須含變換與矩陣、實際目標、定義域及還原。
配套題本 Q1(c)
Q2. 標準化、ridge與LASSO (18)
配套題本 Q2
(a) [4]
先取四數均值，偏差平方和除4再開平方。三欄兩兩正交，平方範數都是4；總體方差為1不等於欄範數為1。
均值要把各特徵的四個觀測相加後除以4。兩個特徵的偏差都包含兩個−2和兩個+2，因此總體方差為16/4=4，標準差是2。每個中心化觀測除以2，才得到所列±1欄。方差為1的欄，其平方範數是樣本數n，而不是1。不同設計欄的內積因正負貢獻抵消而為零。Mᵀy第二個分量是−1−3+5+11=12，可同時檢查行序與乘法是否正確。
μ u = 4 , μ v = 12 , s u = s v = ( 4 + 4 + 4 + 4 ) / 4 = 2. M = ( 1 − 1 − 1 1 − 1 1 1 1 − 1 1 1 1 ) , M T M = 4 I 3 , M T y = ( 20 , 12 , 8 ) T . μ u = 2 + 2 + 6 + 6 4 = 4 , μ v = 10 + 14 + 10 + 14 4 = 12 , s u = ( − 2 ) 2 + ( − 2 ) 2 + 2 2 + 2 2 4 = 2 = s v . \begin{gathered}
\mu_u=4,\quad\mu_v=12,\quad s_u=s_v=\sqrt{(4+4+4+4)/4}=2.
\\ M=\begin{pmatrix}1&-1&-1\\1&-1&1\\1&1&-1\\1&1&1\end{pmatrix},\quad M^TM=4I_3,\quad M^Ty=(20,12,8)^T.
\\ \mu_u=\frac{2+2+6+6}{4}=4,\quad\mu_v=\frac{10+14+10+14}{4}=12,\quad s_u=\sqrt{\frac{(-2)^2+(-2)^2+2^2+2^2}{4}}=2=s_v.
\end{gathered} μ u = 4 , μ v = 12 , s u = s v = ( 4 + 4 + 4 + 4 ) /4 = 2. M = 1 1 1 1 − 1 − 1 1 1 − 1 1 − 1 1 , M T M = 4 I 3 , M T y = ( 20 , 12 , 8 ) T . μ u = 4 2 + 2 + 6 + 6 = 4 , μ v = 4 10 + 14 + 10 + 14 = 12 , s u = 4 ( − 2 ) 2 + ( − 2 ) 2 + 2 2 + 2 2 = 2 = s v . 評分： 統計量1；矩陣1；兩個乘積各1。
配套題本 Q2(a)
(b) [6]
懲罰矩陣截距位置必須為零；求導兩項各帶2。所得對角系統正定，解唯一。代入標準化定義還原截距，不能保留標準化截距。在(6,14)兩式均得15/2。此處共同縮小一半依賴正交欄且範數相同。
D的截距位置為0，兩個斜率位置才為1。平方損失求導帶因子2，4βᵀDβ求導為8Dβ；必須把整條方程除以2，不能只除損失項。最後對角係數4、8、8均為正，目標嚴格凸，解唯一。還原單位時，把兩條標準化定義代入整個仿射表達式，再合併常數；兩個中心化特徵都會貢獻常數，所以原截距不再是5。可選一個點在兩套座標下獨立驗算。此處斜率恰縮為一半，只因兩欄正交且平方範數都為4；相關特徵不能逐座標套用這個捷徑。
D = diag ( 0 , 1 , 1 ) , 2 M T ( M β − y ) + 8 D β = 0 , ( M T M + 4 D ) β ^ = M T y , diag ( 4 , 8 , 8 ) β ^ = ( 20 , 12 , 8 ) T , β ^ = ( 5 , 3 / 2 , 1 ) T , y ^ = 5 + 3 2 u − 4 2 + v − 12 2 = − 4 + 3 4 u + 1 2 v . y ^ = 5 + 3 2 u − 4 2 + v − 12 2 = 5 − 3 − 6 + 3 4 u + 1 2 v = − 4 + 3 4 u + 1 2 v . ( u , v ) = ( 6 , 14 ) : 5 + 3 2 + 1 = 15 2 = − 4 + 9 2 + 7. 4 4 + 4 = 1 2 . \begin{gathered}
D=\operatorname{diag}(0,1,1),\quad2M^T(M\beta-y)+8D\beta=0,
\\(M^TM+4D)\widehat\beta=M^Ty,\quad\operatorname{diag}(4,8,8)\widehat\beta=(20,12,8)^T,
\\\widehat\beta=(5,3/2,1)^T,\qquad\widehat y=5+\frac32\frac{u-4}{2}+\frac{v-12}{2}=-4+\frac34u+\frac12v.
\\ \widehat y=5+\frac32\frac{u-4}{2}+\frac{v-12}{2}=5-3-6+\frac34u+\frac12v=-4+\frac34u+\frac12v.\\(u,v)=(6,14):\quad 5+\frac32+1=\frac{15}{2}=-4+\frac92+7.\\\frac{4}{4+4}=\frac12.
\end{gathered} D = diag ( 0 , 1 , 1 ) , 2 M T ( Mβ − y ) + 8 D β = 0 , ( M T M + 4 D ) β = M T y , diag ( 4 , 8 , 8 ) β = ( 20 , 12 , 8 ) T , β = ( 5 , 3/2 , 1 ) T , y = 5 + 2 3 2 u − 4 + 2 v − 12 = − 4 + 4 3 u + 2 1 v . y = 5 + 2 3 2 u − 4 + 2 v − 12 = 5 − 3 − 6 + 4 3 u + 2 1 v = − 4 + 4 3 u + 2 1 v . ( u , v ) = ( 6 , 14 ) : 5 + 2 3 + 1 = 2 15 = − 4 + 2 9 + 7. 4 + 4 4 = 2 1 . 評分： D與求導2；方程係數2；完整還原2。
配套題本 Q2(b)
(c) [5]
中心化特徵令未罰截距等於反應均值；正交性消去斜率交叉項。正分支要求h>τ，負分支要求h<−τ；零點左導數非正、右導數非負，故邊界亦歸零。第二斜率精確為零；整體目標乘2才保持解。殘差相關性核對：正係數達閾值，零係數未越閾值。
特徵欄中心化後，不受懲罰的截距方程不再含斜率，因此截距等於反應均值。欄正交又消去兩斜率的交叉項；若不正交，就不能分別求兩個一維最優解。零分支不能靠在零點對絕對值普通求導得到，而應要求左導數不正、右導數不負。正係數的特徵與殘差相關量應等於正閾值；零係數的相關量可處在閾值區間內任一點。殘差核對因此同時檢查了尖點條件與普通導數條件。整個目標乘正數才保持最小點不變；只改變平方損失係數會改變相對懲罰。
d = m T m > 0 , h = m T r , 1 2 ∥ r − m t ∥ 2 + τ ∣ t ∣ = d 2 t 2 − h t + τ ∣ t ∣ + constant . t > 0 : d t − h + τ = 0 ⟹ t = ( h − τ ) / d ( h > τ ) . t < 0 : d t − h − τ = 0 ⟹ t = ( h + τ ) / d ( h < − τ ) . t ∗ = S ( h , τ ) d , S ( h , τ ) = { h − τ h > τ , 0 ∣ h ∣ ≤ τ , h + τ h < − τ . − h − τ ≤ 0 ≤ − h + τ ⟺ ∣ h ∣ ≤ τ . β ^ 0 = 5 , β ^ 1 = S ( 12 , 10 ) 4 = 1 2 , β ^ 2 = S ( 8 , 10 ) 4 = 0. 1 2 R S S + 10 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) ⟷ R S S + 20 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) . r = ( − 7 / 2 , − 3 / 2 , − 1 / 2 , 11 / 2 ) T , 1 T r = 0 , z 1 T r = 10 , z 2 T r = 8. \begin{gathered}
d=m^Tm>0,\quad h=m^Tr,\quad\tfrac12\|r-mt\|^2+\tau|t|=\tfrac d2t^2-ht+\tau|t|+\text{constant}.
\\t>0:\quad dt-h+\tau=0\Longrightarrow t=(h-\tau)/d\quad(h>\tau).
\\t<0:\quad dt-h-\tau=0\Longrightarrow t=(h+\tau)/d\quad(h<-\tau).
\\ t^*=\frac{S(h,\tau)}d,\qquad S(h,\tau)=\begin{cases}h-\tau&h>\tau,\\0&|h|\le\tau,\\h+\tau&h<-\tau.\end{cases}
\\ -h-\tau\le0\le-h+\tau\ \Longleftrightarrow\ |h|\le\tau.
\\ \widehat\beta_0=5,\quad\widehat\beta_1=\frac{S(12,10)}4=\frac12,\quad\widehat\beta_2=\frac{S(8,10)}4=0.
\\ \tfrac12\mathrm{RSS}+10(|\beta_1|+|\beta_2|)\ \longleftrightarrow\ \mathrm{RSS}+20(|\beta_1|+|\beta_2|).
\\r=(-7/2,-3/2,-1/2,11/2)^T,\quad\mathbf1^Tr=0,\ z_1^Tr=10,\ z_2^Tr=8.
\end{gathered} d = m T m > 0 , h = m T r , 2 1 ∥ r − m t ∥ 2 + τ ∣ t ∣ = 2 d t 2 − h t + τ ∣ t ∣ + constant . t > 0 : d t − h + τ = 0 ⟹ t = ( h − τ ) / d ( h > τ ) . t < 0 : d t − h − τ = 0 ⟹ t = ( h + τ ) / d ( h < − τ ) . t ∗ = d S ( h , τ ) , S ( h , τ ) = ⎩ ⎨ ⎧ h − τ 0 h + τ h > τ , ∣ h ∣ ≤ τ , h < − τ . − h − τ ≤ 0 ≤ − h + τ ⟺ ∣ h ∣ ≤ τ . β 0 = 5 , β 1 = 4 S ( 12 , 10 ) = 2 1 , β 2 = 4 S ( 8 , 10 ) = 0. 2 1 RSS + 10 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) ⟷ RSS + 20 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) . r = ( − 7/2 , − 3/2 , − 1/2 , 11/2 ) T , 1 T r = 0 , z 1 T r = 10 , z 2 T r = 8. 評分： 截距與正交1；含零分支推導2；係數1；懲罰20及理由1。
配套題本 Q2(c)
(d) [3]
全數據預處理讓留出特徵分布影響擬合。先劃分，再只用訓練子集估計尺度；同一變換用於訓練及驗證；只在訓練子集擬合候選，最後評分驗證。匯總選參數，再全開發數據重新擬合預處理及係數；最終測試集始終不參與。個別OLS的縮放不變性不能證明ridge洩漏流程正確。
驗證折應模擬未見觀測，所以即使沒有看其反應，也不能讓其特徵分佈參與均值和標準差的估計。順序必須是先劃分；在本折訓練子集估計預處理；固定該變換用於兩子集；在變換後的訓練資料上擬合各候選懲罰；最後評估留出折。彙總驗證誤差選定懲罰後，再用整個開發訓練集重新估計預處理與係數。最終測試集不參與以上任何選擇。有些無懲罰OLS預測恰好對可逆縮放不變，但ridge的係數懲罰會隨尺度改變；不能用一個不變的特例為洩漏流程辯護。
評分： 洩漏來源1；訓練統計1；變換擬合評分次序1。
配套題本 Q2(d)
Q3. 矩形SVD與最小範數 (18)
配套題本 Q3
(a) [6]
先算較小的AAᵀ，特徵值8、4須開非負平方根，不能直接當奇異值。右向量由Aᵀu/σ配對，再補單位零空間向量。檢查正交及兩個外積貢獻；左向量反號時配對右向量亦須反號。
A有兩行三欄，先算AAᵀ可把問題化為較小的二階特徵值問題，而非三階AᵀA。由(6−λ)²−4=0得到8和4，取非負平方根後才是奇異值。每個左特徵向量先歸一化，再用Aᵀu/σ構造配對右向量。完整分解雖只有兩個正奇異值，仍需第三個右向量，它張成零空間。逐一檢查尺寸：U為2×2、Σ為2×3、V為3×3。欄正交還不夠，要重建兩個外積項，確認和為A。翻轉一個左向量時必須同時翻轉其配對右向量，才不會改變外積。
A A T = ( 6 2 2 6 ) , ( 6 − λ ) 2 − 4 = 0 , λ = 8 , 4. u 1 = 1 2 ( 1 1 ) , u 2 = 1 2 ( 1 − 1 ) , σ 1 = 2 2 , σ 2 = 2. v 1 = A T u 1 σ 1 = ( 1 , 0 , 0 ) T , v 2 = A T u 2 σ 2 = 1 2 ( 0 , 1 , 1 ) T , v 3 = 1 2 ( 0 , 1 , − 1 ) T . U = 1 2 ( 1 1 1 − 1 ) , Σ = ( 2 2 0 0 0 2 0 ) , V = ( 1 0 0 0 1 / 2 1 / 2 0 1 / 2 − 1 / 2 ) . U T U = I 2 , V T V = I 3 , A = ( 2 0 0 2 0 0 ) + ( 0 1 1 0 − 1 − 1 ) . det ( A A T − λ I ) = ( 6 − λ ) 2 − 4 = 0. σ 1 u 1 v 1 T = ( 2 0 0 2 0 0 ) , σ 2 u 2 v 2 T = ( 0 1 1 0 − 1 − 1 ) , A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T . \begin{gathered}
AA^T=\begin{pmatrix}6&2\\2&6\end{pmatrix},\quad(6-\lambda)^2-4=0,\quad \lambda=8,4.
\\u_1=\frac1{\sqrt2}\binom11,\ u_2=\frac1{\sqrt2}\binom1{-1},\quad\sigma_1=2\sqrt2,\ \sigma_2=2.
\\v_1=\frac{A^Tu_1}{\sigma_1}=(1,0,0)^T,\quad v_2=\frac{A^Tu_2}{\sigma_2}=\frac1{\sqrt2}(0,1,1)^T,\quad v_3=\frac1{\sqrt2}(0,1,-1)^T.
\\U=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\quad\Sigma=\begin{pmatrix}2\sqrt2&0&0\\0&2&0\end{pmatrix},\quad V=\begin{pmatrix}1&0&0\\0&1/\sqrt2&1/\sqrt2\\0&1/\sqrt2&-1/\sqrt2\end{pmatrix}.
\\U^TU=I_2,\quad V^TV=I_3,\quad A=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix}+\begin{pmatrix}0&1&1\\0&-1&-1\end{pmatrix}.
\\ \det(AA^T-\lambda I)=(6-\lambda)^2-4=0.\\\sigma_1u_1v_1^T=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix},\quad\sigma_2u_2v_2^T=\begin{pmatrix}0&1&1\\0&-1&-1\end{pmatrix},\quad A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T.
\end{gathered} A A T = ( 6 2 2 6 ) , ( 6 − λ ) 2 − 4 = 0 , λ = 8 , 4. u 1 = 2 1 ( 1 1 ) , u 2 = 2 1 ( − 1 1 ) , σ 1 = 2 2 , σ 2 = 2. v 1 = σ 1 A T u 1 = ( 1 , 0 , 0 ) T , v 2 = σ 2 A T u 2 = 2 1 ( 0 , 1 , 1 ) T , v 3 = 2 1 ( 0 , 1 , − 1 ) T . U = 2 1 ( 1 1 1 − 1 ) , Σ = ( 2 2 0 0 2 0 0 ) , V = 1 0 0 0 1/ 2 1/ 2 0 1/ 2 − 1/ 2 . U T U = I 2 , V T V = I 3 , A = ( 2 2 0 0 0 0 ) + ( 0 0 1 − 1 1 − 1 ) . det ( A A T − λ I ) = ( 6 − λ ) 2 − 4 = 0. σ 1 u 1 v 1 T = ( 2 2 0 0 0 0 ) , σ 2 u 2 v 2 T = ( 0 0 1 − 1 1 − 1 ) , A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T . 評分： Gram及特徵對2；奇異值配對2；零空間與完整尺寸2。
配套題本 Q3(a)
(b) [4]
偽逆交換尺寸，只倒數非零奇異值。此處滿行秩使任意右端相容，因此最小二乘解也是精確解；一般偽逆問題未必如此。
偽逆交換原矩陣的行列數，所以Σ⁺是三行兩欄；只對兩個正奇異值取倒數，絕不能對零取倒數。按VΣ⁺Uᵀ的次序相乘。A⁺乘b得到三個座標，再代回原來兩條方程，是獨立的相容性檢查。這裏A滿行秩，AA⁺是二階單位矩陣，任何二維右端都能達到。一般矩陣的A⁺b只保證殘差範數最小；要稱它為精確解，必須另外確認相容性，本題確實完成了這一步。
Σ + = ( 1 / ( 2 2 ) 0 0 1 / 2 0 0 ) , A + = V Σ + U T = 1 4 ( 1 1 1 − 1 1 − 1 ) . x ∗ = 1 4 ( 6 + 2 , 6 − 2 , 6 − 2 ) T = ( 2 , 1 , 1 ) T , A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = b , A A + = I 2 . A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = ( 6 , 2 ) T = b , A A + = I 2 . \begin{gathered}
\Sigma^+=\begin{pmatrix}1/(2\sqrt2)&0\\0&1/2\\0&0\end{pmatrix},\quad A^+=V\Sigma^+U^T=\frac14\begin{pmatrix}1&1\\1&-1\\1&-1\end{pmatrix}.
\\x_*=\frac14(6+2,6-2,6-2)^T=(2,1,1)^T,\quad Ax_*=(4+1+1,4-1-1)^T=b,\quad AA^+=I_2.
\\ Ax_*=(4+1+1,\ 4-1-1)^T=(6,2)^T=b,\quad AA^+=I_2.
\end{gathered} Σ + = 1/ ( 2 2 ) 0 0 0 1/2 0 , A + = V Σ + U T = 4 1 1 1 1 1 − 1 − 1 . x ∗ = 4 1 ( 6 + 2 , 6 − 2 , 6 − 2 ) T = ( 2 , 1 , 1 ) T , A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = b , A A + = I 2 . A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = ( 6 , 2 ) T = b , A A + = I 2 . 評分： 偽逆2；解1；代回1。
配套題本 Q3(b)
(c) [5]
原方程相加相減確定x₁與後兩坐標之和。剩餘變化屬於零空間且與x*正交。展開範數得非負附加項，只有零變化取等號，同時證明最小及唯一；精確解不唯一不妨礙最小範數解唯一。
把原來兩條方程相加，得到4x₁=8；相減，得到2x₂+2x₃=4。因此x₁=2，其餘兩個座標之和為2，可用一個自由實數t參數化。這個表示覆蓋全部精確解，而不是只列幾個例子。與x∗之差h屬於零空間，且與x∗的內積為2·0+t−t=0。先展開範數平方，再消去交叉項；非負剩餘項證明最小，等號只能在t=0成立才證明唯一。幾何上，偽逆解在行空間，而所有允許的位移在其正交補零空間。精確解無限多，不妨礙存在唯一的最短解。
2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 ⟹ x 1 = 2 , x 2 + x 3 = 2. x = ( 2 , 1 + t , 1 − t ) T = x ∗ + h , h = ( 0 , t , − t ) T ∈ ker A , x ∗ T h = 0. ∥ x ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 = 6 + 2 t 2 ≥ 6 , equality iff t = 0. 2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 , x 1 = 2 , x 2 + x 3 = 2. ∥ x ∗ + h ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 , x ∗ T h = 2 ⋅ 0 + t − t = 0. \begin{gathered}
2x_1+x_2+x_3=6,\quad2x_1-x_2-x_3=2\quad\Longrightarrow\quad x_1=2,\ x_2+x_3=2.
\\x=(2,1+t,1-t)^T=x_*+h,\quad h=(0,t,-t)^T\in\ker A,\quad x_*^Th=0.
\\\|x\|^2=\|x_*\|^2+2x_*^Th+\|h\|^2=6+2t^2\ge6,\qquad \text{equality iff }t=0.
\\ 2x_1+x_2+x_3=6,\quad2x_1-x_2-x_3=2,\quad x_1=2,\quad x_2+x_3=2.\\\|x_*+h\|^2=\|x_*\|^2+2x_*^Th+\|h\|^2,\quad x_*^Th=2\cdot0+t-t=0.
\end{gathered} 2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 ⟹ x 1 = 2 , x 2 + x 3 = 2. x = ( 2 , 1 + t , 1 − t ) T = x ∗ + h , h = ( 0 , t , − t ) T ∈ ker A , x ∗ T h = 0. ∥ x ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 = 6 + 2 t 2 ≥ 6 , equality iff t = 0. 2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 , x 1 = 2 , x 2 + x 3 = 2. ∥ x ∗ + h ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 , x ∗ T h = 2 ⋅ 0 + t − t = 0. 評分： 全部解2；正交1；範數1；取等唯一性1。
配套題本 Q3(c)
(d) [3]
保留最大奇異值項。殘差只有一個非零奇異值，因此兩範數恰好相同。四個非零條目平方和為4，但題求範數2，不是4；一般Frobenius匯總所有捨棄值平方，譜範數只取最大。
截斷到秩一，是保留最大奇異值的整個外積項，不是隨便保留A中的一個元素或一行。亦可直接檢查被捨棄矩陣：四個非零元素為±1，平方和為4，開平方才得到Frobenius範數2。譜範數是殘差的最大奇異值，也為2。兩者相同是因為僅餘一個奇異方向；若捨棄多個方向，Frobenius合併各奇異值平方，而譜範數只取最大者，通常不同。
A 1 = σ 1 u 1 v 1 T = ( 2 0 0 2 0 0 ) , ∥ A − A 1 ∥ F = σ 2 2 = 2 , ∥ A − A 1 ∥ 2 = σ 2 = 2. \begin{gathered}
A_1=\sigma_1u_1v_1^T=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix},\quad\|A-A_1\|_F=\sqrt{\sigma_2^2}=2,\quad\|A-A_1\|_2=\sigma_2=2.
\end{gathered} A 1 = σ 1 u 1 v 1 T = ( 2 2 0 0 0 0 ) , ∥ A − A 1 ∥ F = σ 2 2 = 2 , ∥ A − A 1 ∥ 2 = σ 2 = 2. 評分： 近似1；各範數1。
配套題本 Q3(d)
Q4. 中心化PCA與重建 (15)
配套題本 Q4
(a) [4]
每行減同一均值，中心化後各欄和為零。此題分母3，不沿用前題總體分母4。
兩個座標分別求均值：第一座標和為12，第二座標和為4。樣本按行存放，故從每行減去行向量μᵀ。中心化後兩欄的和都應為零，應先檢查再算協方差。XcᵀXc的對角元素是各欄平方和，非對角元素是逐行配對乘積之和。本題指定樣本協方差，分母n−1=3；第2題的總體標準差分母卻是n=4，不能因為都出現「方差」便擅自統一。
μ = ( 3 , 1 ) T , X c = X − 1 μ T = ( 2 2 − 2 − 2 1 − 1 − 1 1 ) , X c T X c = ( 10 6 6 10 ) , S = 1 3 ( 10 6 6 10 ) . μ = ( 5 + 1 + 4 + 2 4 , 3 − 1 + 0 + 2 4 ) T = ( 3 , 1 ) T . 2 2 + ( − 2 ) 2 + 1 2 + ( − 1 ) 2 = 10 , 2 ⋅ 2 + ( − 2 ) ( − 2 ) + 1 ( − 1 ) + ( − 1 ) 1 = 6. \begin{gathered}
\mu=(3,1)^T,\quad X_c=X-\mathbf1\mu^T=\begin{pmatrix}2&2\\-2&-2\\1&-1\\-1&1\end{pmatrix},\quad X_c^TX_c=\begin{pmatrix}10&6\\6&10\end{pmatrix},\quad S=\frac13\begin{pmatrix}10&6\\6&10\end{pmatrix}.
\\ \mu=\left(\frac{5+1+4+2}{4},\frac{3-1+0+2}{4}\right)^T=(3,1)^T.\\ 2^2+(-2)^2+1^2+(-1)^2=10,\quad2\cdot2+(-2)(-2)+1(-1)+(-1)1=6.
\end{gathered} μ = ( 3 , 1 ) T , X c = X − 1 μ T = 2 − 2 1 − 1 2 − 2 − 1 1 , X c T X c = ( 10 6 6 10 ) , S = 3 1 ( 10 6 6 10 ) . μ = ( 4 5 + 1 + 4 + 2 , 4 3 − 1 + 0 + 2 ) T = ( 3 , 1 ) T . 2 2 + ( − 2 ) 2 + 1 2 + ( − 1 ) 2 = 10 , 2 ⋅ 2 + ( − 2 ) ( − 2 ) + 1 ( − 1 ) + ( − 1 ) 1 = 6. 評分： 均值1；中心化1；乘積1；分母及協方差1。
配套題本 Q4(a)
(b) [6]
較大且嚴格不等的特徵值確定主軸，符號條件確定代表向量。得分是四個標量，不是二維重建；先乘方向行向量再加均值。前兩點在主軸上，後兩點投影到均值。
S的對稱結構提示先試(1,1)與(1,−1)兩個特徵方向，再歸一化並比較特徵值。較大特徵值對應主軸；兩個特徵值不同，所以主軸唯一，但方向仍有正負兩種，題目首座標為正的約定才固定符號。得分向量為4×1，每項是沿主軸的一個標量座標，不是二維重建點。把這個座標乘回wᵀ才重建一行，再加均值行才恢復原座標。前兩個中心化點已在主軸上，完全保留；後兩個與主軸垂直，得分為零，因此回到原座標中的均值(3,1)，不是原點。
λ 1 = 16 / 3 , v 1 = 1 2 ( 1 , 1 ) T , λ 2 = 4 / 3 , v 2 = 1 2 ( 1 , − 1 ) T . w = v 1 , z = X c w = ( 2 2 , − 2 2 , 0 , 0 ) T , X ^ c = z w T = ( 2 2 − 2 − 2 0 0 0 0 ) , X ^ = ( 5 3 1 − 1 3 1 3 1 ) . \begin{gathered}
\lambda_1=16/3,\quad v_1=\frac1{\sqrt2}(1,1)^T,\quad\lambda_2=4/3,\quad v_2=\frac1{\sqrt2}(1,-1)^T.
\\w=v_1,\quad z=X_cw=(2\sqrt2,-2\sqrt2,0,0)^T,\quad\widehat X_c=zw^T=\begin{pmatrix}2&2\\-2&-2\\0&0\\0&0\end{pmatrix},\quad\widehat X=\begin{pmatrix}5&3\\1&-1\\3&1\\3&1\end{pmatrix}.
\end{gathered} λ 1 = 16/3 , v 1 = 2 1 ( 1 , 1 ) T , λ 2 = 4/3 , v 2 = 2 1 ( 1 , − 1 ) T . w = v 1 , z = X c w = ( 2 2 , − 2 2 , 0 , 0 ) T , X c = z w T = 2 − 2 0 0 2 − 2 0 0 , X = 5 1 3 3 3 − 1 1 1 . 評分： 特徵對2；得分2；重建加均值2。
配套題本 Q4(b)
(c) [5]
每個中心化樣本分為q方向投影與正交殘差，逐行用勾股並求和，利用q單位範數得到恆等式。總能量固定，等價最大化Rayleigh商；在特徵基展開證明最大值及等號條件。所求是總平方誤差，不是開方或按樣本平均。
總方差是S的跡，因此用保留特徵值除以兩個特徵值之和。重建殘差前兩行為零，後兩行為(1,−1)與(−1,1)，長度平方相加為4。這是總平方誤差，不是平均後的1，也不是開平方後的2。用捨棄特徵值核對時，要乘n−1，因為S採用了這個分母。一般恆等式先把每個中心化樣本投影到單位向量q；由qᵀq=1，減去投影後的殘差與q正交。勾股定理把每點長度平方拆成投影能量與殘差能量；q為單位向量又保證投影向量長度平方等於其標量得分平方。對樣本求和，用(n−1)S替換XcᵀXc，再移項。中心化總能量固定，所以最小殘差等價於最大qᵀSq。最後在正交特徵基展開q，才能證明最大值為λ₁，且特徵值不同時等號只在±v₁成立。中心化和單位長度約束都不能刪去。
λ 1 λ 1 + λ 2 = 4 5 , ∥ X − X ^ ∥ F 2 = 0 + 0 + 2 + 2 = 4 = ( n − 1 ) λ 2 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i ) ] , q T [ x c , i − q ( q T x c , i ) ] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 = ( n − 1 ) q T S q . q = a v 1 + b v 2 , a 2 + b 2 = 1 ⟹ q T S q = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 , equality iff q = ± v 1 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i ) ] , q T [ x c , i − q ( q T x c , i ) ] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 . q = a v 1 + b v 2 , a 2 + b 2 = 1 , q T S q = λ 1 a 2 + λ 2 b 2 = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 . \begin{gathered}
\frac{\lambda_1}{\lambda_1+\lambda_2}=\frac45,\quad\|X-\widehat X\|_F^2=0+0+2+2=4=(n-1)\lambda_2.
\\x_{c,i}=q(q^Tx_{c,i})+[x_{c,i}-q(q^Tx_{c,i})],\quad q^T[x_{c,i}-q(q^Tx_{c,i})]=0.
\\\|X_c\|_F^2=\|X_cqq^T\|_F^2+\|X_c-X_cqq^T\|_F^2,\quad \|X_cqq^T\|_F^2=\|X_cq\|^2=(n-1)q^TSq.
\\ q=av_1+bv_2,\ a^2+b^2=1\quad\Longrightarrow\quad q^TSq=\lambda_1-(\lambda_1-\lambda_2)b^2\le\lambda_1,
\quad\text{equality iff }q=\pm v_1.
\\ x_{c,i}=q(q^Tx_{c,i})+[x_{c,i}-q(q^Tx_{c,i})],\quad q^T[x_{c,i}-q(q^Tx_{c,i})]=0.\\\|X_c\|_F^2=\|X_cqq^T\|_F^2+\|X_c-X_cqq^T\|_F^2,\quad\|X_cqq^T\|_F^2=\|X_cq\|^2.\\q=av_1+bv_2,\quad a^2+b^2=1,\quad q^TSq=\lambda_1a^2+\lambda_2b^2=\lambda_1-(\lambda_1-\lambda_2)b^2\le\lambda_1.
\end{gathered} λ 1 + λ 2 λ 1 = 5 4 , ∥ X − X ∥ F 2 = 0 + 0 + 2 + 2 = 4 = ( n − 1 ) λ 2 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i )] , q T [ x c , i − q ( q T x c , i )] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 = ( n − 1 ) q T Sq . q = a v 1 + b v 2 , a 2 + b 2 = 1 ⟹ q T Sq = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 , equality iff q = ± v 1 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i )] , q T [ x c , i − q ( q T x c , i )] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 . q = a v 1 + b v 2 , a 2 + b 2 = 1 , q T Sq = λ 1 a 2 + λ 2 b 2 = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 . 評分： 比例1；總誤差1；正交恆等式2；特徵值論證1。
配套題本 Q4(c)
Q5. Gonzalez最遠優先與近似保證 (12)
配套題本 Q5
(a) [4]
只有中心0時最遠點為12。每點先取到兩個中心距離的較小者，再對樣本取最大；不能交換最小與最大。最差服務距離來自點7。
只有中心0時，各點非負，到中心的距離恰為其座標，所以選12；不能改成相對於其他任意參照點最遠。加上12後，最近中心分組為{0,2,3}與{7,10,12}。點7到兩中心的距離為7與5，取較小的5；六個最近距離中的最大者於是為5。這是k-center最大服務半徑，不是距離和或平方誤差和。
c 2 = 12 , x 0 2 3 7 10 12 ∣ x ∣ 0 2 3 7 10 12 ∣ x − 12 ∣ 12 10 9 5 2 0 d ( x , C ) 0 2 3 5 2 0 , R G = 5. \begin{gathered}
c_2=12,\qquad\begin{array}{c|rrrrrr}x&0&2&3&7&10&12\\|x|&0&2&3&7&10&12\\|x-12|&12&10&9&5&2&0\\d(x,C)&0&2&3&5&2&0\end{array},\quad R_G=5.
\end{gathered} c 2 = 12 , x ∣ x ∣ ∣ x − 12∣ d ( x , C ) 0 0 12 0 2 2 10 2 3 3 9 3 7 7 5 5 10 10 2 2 12 12 0 0 , R G = 5. 評分： 中心1；距離表2；半徑1。
配套題本 Q5(a)
(b) [3]
所選中心覆蓋兩個區間。下界只看0、7、12，兩兩至少相距5；兩個覆蓋球必有一球容納其中兩點，三角不等式迫使半徑至少5/2，與構造相同。若限制比較中心為樣本點，就是另一問題。
可行構造只給未知最優值的上界，本身還不證明最優。區間[0,3]以3/2為中心只需半徑3/2；區間[7,12]以19/2為中心需半徑5/2。兩簇共同半徑可取5/2，不要求第一簇也達到它。下界所用三點0、7、12的兩兩距離為7、12、5。兩個球覆蓋三點，必有一對同球；若半徑小於5/2，三角不等式會使同球兩點間距小於5，矛盾。下界與構造上界相等才證明最優；5/(5/2)=2則說明近似界確實可以達到。
c 1 ∗ = 3 / 2 , c 2 ∗ = 19 / 2 , [ 0 , 3 ] ⊆ B ( 3 / 2 , 5 / 2 ) , [ 7 , 12 ] ⊆ B ( 19 / 2 , 5 / 2 ) . R ∗ ≤ 5 / 2 , 5 ≤ d ( u , v ) ≤ d ( u , c ) + d ( c , v ) ≤ 2 r ⟹ R ∗ ≥ 5 / 2. R ∗ = 5 / 2 , R G / R ∗ = 2. \begin{gathered}
c_1^*=3/2,\quad c_2^*=19/2,\quad [0,3]\subseteq B(3/2,5/2),\quad[7,12]\subseteq B(19/2,5/2).
\\R^*\le5/2,\qquad5\le d(u,v)\le d(u,c)+d(c,v)\le2r\ \Longrightarrow\ R^*\ge5/2.
\\R^*=5/2,\qquad R_G/R^*=2.
\end{gathered} c 1 ∗ = 3/2 , c 2 ∗ = 19/2 , [ 0 , 3 ] ⊆ B ( 3/2 , 5/2 ) , [ 7 , 12 ] ⊆ B ( 19/2 , 5/2 ) . R ∗ ≤ 5/2 , 5 ≤ d ( u , v ) ≤ d ( u , c ) + d ( c , v ) ≤ 2 r ⟹ R ∗ ≥ 5/2. R ∗ = 5/2 , R G / R ∗ = 2. 評分： 可行中心1；三點兩球下界1；最優及比值1。
配套題本 Q5(b)
(c) [5]
若最終半徑為零立即成立；否則在k個中心外加一個最終最遠樣本p，只用於證明。選每個中心時，它離任一舊中心至少為當輪覆蓋半徑，後者不小於最終半徑；p亦離每個最終中心至少該半徑。將k+1點分給k個最優覆蓋球，必有兩點同球，再用三角不等式。若最優只為下確界，對任意近最優覆蓋證明後令多餘半徑趨零。證明要求度量，不適用於平方歐氏距離，亦不是k-means平方和保證。
證明有兩個不同任務。首先必須構造k+1個充分分離的輸入點；沒有分離下界，直接說鴿巢原理還不夠。增加中心不會增加任何點到最近中心的距離，所以覆蓋半徑單調不增。選中cj時，它到舊中心集合的距離是對各舊中心距離取最小值；最小值已不小於最終半徑，每個單獨距離自然也不小於最終半徑。額外最遠點同理。其次才與最優覆蓋比較，即使一個點被多個球覆蓋，也任選其中一個球歸屬。必有同球一對，它既有此前的距離下界，又有2R∗的距離上界。額外點只是證明工具，不是要求演算法輸出k+1個中心。
d ( p , { c 1 , … , c k } ) = R G , i < j ⟹ d ( c j , c i ) ≥ R j − 1 ≥ R G . d ( p , c i ) ≥ R G ⟹ { c 1 , … , c k , p } pairwise separated by at least R G . R G ≤ d ( u , v ) ≤ d ( u , c ∗ ) + d ( c ∗ , v ) ≤ 2 R ∗ . R G ≤ 2 ( R ∗ + ε ) ( ε > 0 ) ⟹ R G ≤ 2 R ∗ . ∣ 0 − 2 ∣ 2 = 4 > ∣ 0 − 1 ∣ 2 + ∣ 1 − 2 ∣ 2 = 2. \begin{gathered}
d(p,\{c_1,\ldots,c_k\})=R_G,\qquad i<j\Longrightarrow d(c_j,c_i)\ge R_{j-1}\ge R_G.
\\d(p,c_i)\ge R_G\quad\Longrightarrow\quad\{c_1,\ldots,c_k,p\}\text{ pairwise separated by at least }R_G.
\\ R_G\le d(u,v)\le d(u,c^*)+d(c^*,v)\le2R^*.
\\R_G\le2(R^*+\varepsilon)\quad(\varepsilon>0)\Longrightarrow R_G\le2R^*.
\\|0-2|^2=4> |0-1|^2+|1-2|^2=2.
\end{gathered} d ( p , { c 1 , … , c k }) = R G , i < j ⟹ d ( c j , c i ) ≥ R j − 1 ≥ R G . d ( p , c i ) ≥ R G ⟹ { c 1 , … , c k , p } pairwise separated by at least R G . R G ≤ d ( u , v ) ≤ d ( u , c ∗ ) + d ( c ∗ , v ) ≤ 2 R ∗ . R G ≤ 2 ( R ∗ + ε ) ( ε > 0 ) ⟹ R G ≤ 2 R ∗ . ∣0 − 2 ∣ 2 = 4 > ∣0 − 1 ∣ 2 + ∣1 − 2 ∣ 2 = 2. 評分： 額外最遠點1；分離2；鴿巢1；三角結論1。
配套題本 Q5(c)
Q6. Lloyd迭代與次優固定點 (12)
配套題本 Q6
(a) [6]
一維有序中心以中點分界。第一次更新後必須重分配，不能立即說收斂。第三次分配與第二次相同，按題意停；沒有樣本落在這些分界。以下四個代價依次對應初始分配、第一輪均值更新、第二輪重新分配、第二輪均值更新，核對兩類步驟均不增。
一維中兩個有序中心的中點就是最近中心分界。初始(0,1)給出分界1/2，只有0進第一簇；第二簇均值為(1+4+6+7+12)/5=6。算完均值不等於收斂：中心(0,6)須以分界3重新分配，點1於是移動。新均值分別為(0+1)/2=1/2與(4+6+7+12)/4=29/4。再算中點31/8=3.875，仍在1與4之間，下一次分配才確認兩簇不變，這時才滿足題定停止條件。沒有觀測等於這些邊界，所以從未觸發平局規則。檢查下降時應註明代價是在分配後還是中心更新後，否則正確數字也可能對應錯誤狀態。
assignment boundary C 1 , C 2 updated centers 1 1 / 2 { 0 } , { 1 , 4 , 6 , 7 , 12 } 0 , 6 2 3 { 0 , 1 } , { 4 , 6 , 7 , 12 } 1 / 2 , 29 / 4 3 31 / 8 { 0 , 1 } , { 4 , 6 , 7 , 12 } 1 / 2 , 29 / 4 191 ≥ 66 ≥ 42 ≥ 141 / 4. c 1 + c 2 2 = 1 / 2 + 29 / 4 2 = 31 8 = 3.875. \begin{gathered}
\begin{array}{c|c|c|c} \text{assignment}&\text{boundary}&C_1,C_2&\text{updated centers}\\1&1/2&\{0\},\{1,4,6,7,12\}&0,6\\2&3&\{0,1\},\{4,6,7,12\}&1/2,29/4\\3&31/8&\{0,1\},\{4,6,7,12\}&1/2,29/4\end{array}
\\191\ \ge\ 66\ \ge\ 42\ \ge\ 141/4.
\\\frac{c_1+c_2}{2}=\frac{1/2+29/4}{2}=\frac{31}8=3.875.
\end{gathered} assignment 1 2 3 boundary 1/2 3 31/8 C 1 , C 2 { 0 } , { 1 , 4 , 6 , 7 , 12 } { 0 , 1 } , { 4 , 6 , 7 , 12 } { 0 , 1 } , { 4 , 6 , 7 , 12 } updated centers 0 , 6 1/2 , 29/4 1/2 , 29/4 191 ≥ 66 ≥ 42 ≥ 141/4. 2 c 1 + c 2 = 2 1/2 + 29/4 = 8 31 = 3.875. 評分： 第一輪2；第二輪2；最終檢查與停止2。
配套題本 Q6(a)
(b) [3]
分別計算每簇相對自身均值的偏差。一個更好的可行分組已足以否定全局最優，不必證明替代分組本身全局最優；精確正差不是捨入誤差。
終點代價按簇分別算，必須用最終均值。第一簇有兩個絕對值為1/2的偏差；第二簇從4、6、7、12減去29/4，得到−13/4、−5/4、−1/4、19/4，逐項平方後再相加。替代分組要重新求自己的均值，不能沿用Lloyd中心；其兩部分平方和為26/3與62/3，總計88/3。只需一個目標嚴格更小的可行解，就能否定Lloyd終點全局最優，無須進一步證明替代解本身全局最優。精確差71/12為正，不是捨入造成的差異。
S S E L l o y d = 1 2 + 169 + 25 + 1 + 361 16 = 141 4 . x ˉ A = 5 / 3 , x ˉ B = 25 / 3 , S S E A = 25 + 4 + 49 9 = 26 3 , S S E B = 49 + 16 + 121 9 = 62 3 . S S E a l t e r n a t i v e = 88 3 < 141 4 , 141 4 − 88 3 = 71 12 > 0. S S E 1 = ( 0 − 1 / 2 ) 2 + ( 1 − 1 / 2 ) 2 = 1 2 , S S E 2 = 169 + 25 + 1 + 361 16 = 139 4 . S S E A = 25 + 4 + 49 9 = 26 3 , S S E B = 49 + 16 + 121 9 = 62 3 , 141 4 − 88 3 = 71 12 > 0. \begin{gathered}
\mathrm{SSE}_{\mathrm{Lloyd}}=\frac12+\frac{169+25+1+361}{16}=\frac{141}4.
\\\bar x_A=5/3,\quad\bar x_B=25/3,\quad\mathrm{SSE}_A=\frac{25+4+49}{9}=\frac{26}3,\quad\mathrm{SSE}_B=\frac{49+16+121}{9}=\frac{62}3.
\\\mathrm{SSE}_{\mathrm{alternative}}=\frac{88}3<\frac{141}4,\qquad\frac{141}4-\frac{88}3=\frac{71}{12}>0.
\\ \mathrm{SSE}_1=(0-1/2)^2+(1-1/2)^2=\frac12,\quad\mathrm{SSE}_2=\frac{169+25+1+361}{16}=\frac{139}{4}.\\\mathrm{SSE}_A=\frac{25+4+49}{9}=\frac{26}{3},\quad\mathrm{SSE}_B=\frac{49+16+121}{9}=\frac{62}{3},\quad\frac{141}{4}-\frac{88}{3}=\frac{71}{12}>0.
\end{gathered} SSE Lloyd = 2 1 + 16 169 + 25 + 1 + 361 = 4 141 . x ˉ A = 5/3 , x ˉ B = 25/3 , SSE A = 9 25 + 4 + 49 = 3 26 , SSE B = 9 49 + 16 + 121 = 3 62 . SSE alternative = 3 88 < 4 141 , 4 141 − 3 88 = 12 71 > 0. SSE 1 = ( 0 − 1/2 ) 2 + ( 1 − 1/2 ) 2 = 2 1 , SSE 2 = 16 169 + 25 + 1 + 361 = 4 139 . SSE A = 9 25 + 4 + 49 = 3 26 , SSE B = 9 49 + 16 + 121 = 3 62 , 4 141 − 3 88 = 12 71 > 0. 評分： 終點1；替代中心代價1；非全局結論1。
配套題本 Q6(b)
(c) [3]
圍繞均值展開；中心化樣本之和為零，交叉項消失。附加項非負且只有中心等於均值時為零。Lloyd只是固定另一部分時各自優化，聯合問題非凸，更好分組可能須同時改變多個點及中心；前問正是反例。
證明均值公式時要固定簇成員。每個x−c中加減μ，展開平方長度，先保留交叉項再求和。按均值定義，中心化樣本之和為零，交叉項才消失。剩下m‖μ−c‖²非負，而且m>0時僅在c=μ為零，證明的是固定這個簇時中心唯一最優。Lloyd交替優化兩個條件子問題：中心固定時選最好分配，分配固定時選最好中心；這並不使聯合問題成為凸問題，下降也不等於考慮過所有可能分組。更好的分組可能要同時改變若干分配與中心，(b)正是全局最優主張的具體反例。
m = ∣ C ∣ > 0 , μ = 1 m ∑ x ∈ C x , ∑ x ∈ C ( x − μ ) = 0. ∑ x ∈ C ∥ x − c ∥ 2 = ∑ x ∈ C ∥ ( x − μ ) + ( μ − c ) ∥ 2 = ∑ x ∈ C ∥ x − μ ∥ 2 + 2 ( ∑ x ∈ C ( x − μ ) ) T ( μ − c ) + m ∥ μ − c ∥ 2 = ∑ x ∈ C ∥ x − μ ∥ 2 + m ∥ μ − c ∥ 2 ≥ ∑ x ∈ C ∥ x − μ ∥ 2 . \begin{gathered}
m=|C|>0,\quad\mu=\frac1m\sum_{x\in C}x,\quad\sum_{x\in C}(x-\mu)=0.
\\\sum_{x\in C}\|x-c\|^2=\sum_{x\in C}\|(x-\mu)+(\mu-c)\|^2
\\=\sum_{x\in C}\|x-\mu\|^2+2\left(\sum_{x\in C}(x-\mu)\right)^T(\mu-c)+m\|\mu-c\|^2
\\=\sum_{x\in C}\|x-\mu\|^2+m\|\mu-c\|^2\ge\sum_{x\in C}\|x-\mu\|^2.
\end{gathered} m = ∣ C ∣ > 0 , μ = m 1 x ∈ C ∑ x , x ∈ C ∑ ( x − μ ) = 0. x ∈ C ∑ ∥ x − c ∥ 2 = x ∈ C ∑ ∥ ( x − μ ) + ( μ − c ) ∥ 2 = x ∈ C ∑ ∥ x − μ ∥ 2 + 2 ( x ∈ C ∑ ( x − μ ) ) T ( μ − c ) + m ∥ μ − c ∥ 2 = x ∈ C ∑ ∥ x − μ ∥ 2 + m ∥ μ − c ∥ 2 ≥ x ∈ C ∑ ∥ x − μ ∥ 2 . 評分： 分解與交叉項2；分塊與全局區別1。
配套題本 Q6(c)
Q7. Voronoi單元與中心位置 (9)
配套題本 Q7
(a) [3]
非負距離平方後消去共同二次項；前兩比較給垂直及水平平分線，第三給斜線。公共頂點到三個站點距離都為√13。閉單元容許共享邊界；若唯一分配還須平局規則。
先將s₁分別與另外兩站比較，得到它的兩條不等式。求s₂與s₃之間邊界時，把兩邊距離平方展開，消去x²+y²，再移項得到線性條件。不等號方向取決於正在描述哪個站的單元，換另一單元就要反向。三單元共有點必須同時滿足x≤2與x≥2，以及y≤3與y≥3，所以只能是(2,3)；再檢查第三條邊界及三條距離確實相同。閉Voronoi單元允許邊界重合，要在邊界賦予唯一簇標籤才另外需要平局規則，這不是單元定義出錯。
x 2 + y 2 ≤ ( x − 4 ) 2 + y 2 ⟺ x ≤ 2 , x 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ y ≤ 3. ( x − 4 ) 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ 3 y − 2 x ≤ 5. R 1 = { ( x , y ) : x ≤ 2 , y ≤ 3 } , R 2 = { ( x , y ) : x ≥ 2 , 3 y − 2 x ≤ 5 } , R 3 = { ( x , y ) : y ≥ 3 , 3 y − 2 x ≥ 5 } , R 1 ∩ R 2 ∩ R 3 = { ( 2 , 3 ) } , 3 ( 3 ) − 2 ( 2 ) = 5. − 8 x + 16 ≤ − 12 y + 36 ⟺ 3 y − 2 x ≤ 5 , ∥ ( 2 , 3 ) − s i ∥ = 13 ( i = 1 , 2 , 3 ) . \begin{gathered}
x^2+y^2\le(x-4)^2+y^2\Longleftrightarrow x\le2,
\qquad x^2+y^2\le x^2+(y-6)^2\Longleftrightarrow y\le3.
\\(x-4)^2+y^2\le x^2+(y-6)^2\Longleftrightarrow3y-2x\le5.
\\R_1=\{(x,y):x\le2,y\le3\},\quad R_2=\{(x,y):x\ge2,3y-2x\le5\},
\\R_3=\{(x,y):y\ge3,3y-2x\ge5\},\quad R_1\cap R_2\cap R_3=\{(2,3)\},\quad3(3)-2(2)=5.
\\ -8x+16\le-12y+36\ \Longleftrightarrow\ 3y-2x\le5,\quad\|(2,3)-s_i\|=\sqrt{13}\quad(i=1,2,3).
\end{gathered} x 2 + y 2 ≤ ( x − 4 ) 2 + y 2 ⟺ x ≤ 2 , x 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ y ≤ 3. ( x − 4 ) 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ 3 y − 2 x ≤ 5. R 1 = {( x , y ) : x ≤ 2 , y ≤ 3 } , R 2 = {( x , y ) : x ≥ 2 , 3 y − 2 x ≤ 5 } , R 3 = {( x , y ) : y ≥ 3 , 3 y − 2 x ≥ 5 } , R 1 ∩ R 2 ∩ R 3 = {( 2 , 3 )} , 3 ( 3 ) − 2 ( 2 ) = 5. − 8 x + 16 ≤ − 12 y + 36 ⟺ 3 y − 2 x ≤ 5 , ∥ ( 2 , 3 ) − s i ∥ = 13 ( i = 1 , 2 , 3 ) . 評分： 各單元0.75；公共點及核對0.75。
配套題本 Q7(a)
(b) [3]
長度非負，平方保序；展開後是線性不等式。半空間內兩點的凸組合由線性性仍在其中；若兩點同屬全部半空間，線段亦同屬全部，故交集凸。任意維成立，不依賴圖形。
兩邊都是非負距離，所以平方保持大小關係。展開後共同二次項抵消，留下關於x的線性不等式，右端是常數；因此即使在無法畫出的高維中，它仍是半空間。證明凸性時，取滿足不等式的任意兩點，用非負且和為1的權重1−t與t組合，線段每點仍滿足該不等式。若兩個端點屬於所有半空間，線段每點也同時屬於所有半空間，故屬於交集。僅憑圖形看起來凸，並不構成證明。
∥ x − s i ∥ ≤ ∥ x − s j ∥ ⟺ x T x − 2 x T s i + ∥ s i ∥ 2 ≤ x T x − 2 x T s j + ∥ s j ∥ 2 ⟺ x T ( s j − s i ) ≤ ∥ s j ∥ 2 − ∥ s i ∥ 2 2 , R i = ⋂ j ≠ i { x : x T ( s j − s i ) ≤ ∥ s j ∥ 2 − ∥ s i ∥ 2 2 } . u , v ∈ H = { x : a T x ≤ b } , t ∈ [ 0 , 1 ] ⟹ a T [ ( 1 − t ) u + t v ] ≤ ( 1 − t ) b + t b = b . \begin{gathered}
\|x-s_i\|\le\|x-s_j\|\Longleftrightarrow x^Tx-2x^Ts_i+\|s_i\|^2\le x^Tx-2x^Ts_j+\|s_j\|^2
\\\Longleftrightarrow x^T(s_j-s_i)\le\frac{\|s_j\|^2-\|s_i\|^2}{2},\quad R_i=\bigcap_{j\ne i}\left\{x:x^T(s_j-s_i)\le\frac{\|s_j\|^2-\|s_i\|^2}{2}\right\}.
\\u,v\in H=\{x:a^Tx\le b\},\quad t\in[0,1]\Longrightarrow a^T[(1-t)u+tv]\le(1-t)b+tb=b.
\end{gathered} ∥ x − s i ∥ ≤ ∥ x − s j ∥ ⟺ x T x − 2 x T s i + ∥ s i ∥ 2 ≤ x T x − 2 x T s j + ∥ s j ∥ 2 ⟺ x T ( s j − s i ) ≤ 2 ∥ s j ∥ 2 − ∥ s i ∥ 2 , R i = j = i ⋂ { x : x T ( s j − s i ) ≤ 2 ∥ s j ∥ 2 − ∥ s i ∥ 2 } . u , v ∈ H = { x : a T x ≤ b } , t ∈ [ 0 , 1 ] ⟹ a T [( 1 − t ) u + t v ] ≤ ( 1 − t ) b + t b = b . 評分： 半空間推導1；半空間凸1；交集論證1。
配套題本 Q7(b)
(c) [3]
均值是凸組合：等權非負且和為1。未必是樣本，如{0,2}均值1。Medoid限於實際觀測，此例0與2均可而1不合法。非空不可省，空簇沒有該均值及權重。
第6題已證明固定非空簇的最佳中心為均值。接着按凸組合定義檢查：每個係數1/m非負，所有係數和為1，故均值在凸包中。在凸包內比「就是某個觀測點」弱；{0,2}的凸包是整個區間[0,2]，所以1在凸包內卻未被觀測。固定簇的medoid則從觀測中挑選使距離總和最小者，並非取任意位置的算術平均。本例兩端點均可作medoid。若m=0，除以m和上述凸組合都未定義，空簇必須另外處理。
C = { x 1 , … , x m } , m > 0 , μ = ∑ i = 1 m 1 m x i , 1 m ≥ 0 , ∑ i = 1 m 1 m = 1 , μ ∈ conv ( C ) . \begin{gathered}
C=\{x_1,\ldots,x_m\},\quad m>0,\quad\mu=\sum_{i=1}^m\frac1m x_i,\quad\frac1m\ge0,\quad\sum_{i=1}^m\frac1m=1,
\qquad\mu\in\operatorname{conv}(C).
\end{gathered} C = { x 1 , … , x m } , m > 0 , μ = i = 1 ∑ m m 1 x i , m 1 ≥ 0 , i = 1 ∑ m m 1 = 1 , μ ∈ conv ( C ) . 評分： 凸組合1；反例1；medoid限制1。
配套題本 Q7(c)
