90分鐘 · 100分 · 7道大題 · 27小問。

這是原創自學模擬卷，不是官方考試規格。題數、主題權重、計算機練習說明與評分建議均不預測官方要求。

先在獨立答題紙完成全部題目，再打開解答。寫出必要計算、條件與證明。可行時使用精確值，使用小數須註明捨入。特徵向量或奇異向量的符號若一致配對，等價選擇均可。以題目定義、正規化因子及破平局規則為準，不得無理由假定逆矩陣存在。

本次練習使用Casio fx-50FH II，可用一張雙面A4速查紙；這些是練習約定，不是對當前官方考試許可的聲明。先寫數學目標再做標量運算，普通REG輸出不代替加權、多元或正則化推導。不假定CAS或完整矩陣功能。

以下是自評評分建議，不是官方評分細則。等價正確推導應得同等分數；單一算術錯誤傳遞時保留方法分。解答區分目標、條件、計算與檢查，不能只憑最後數字相同給滿分。

題本 · MATH3320

Q1. 穩健損失與驗證 (16)

題本 Q1

(a) [4]

先弄清正在優化什麼。 四個觀測是固定數字，$a\in\mathbb R$才是我們要選的一個參數；同一個$a$用於預測全部觀測。殘差$r_i=y_i-a$也是標量，$F(a)=\sum_i\rho(r_i)$把四次預測的代價相加。平方分支$\rho(r)=r^2/2$的導數為$r$；尾部分支$|r|-1/2$在正半軸等於$r-1/2$，在負半軸等於$-r-1/2$，故導數分別為1、−1。不能因為有絕對值就説整個函數在0不可導：0附近實際使用的是平方分支。凸表示任意兩點之間的函數圖像不高於連接線，並不表示處處嚴格凸；尾部直線正是反例。

這裏的自變數是殘差$r=y_i-a$，不是係數懲罰。令$\psi=\rho^{\prime}$，分段求導：

$$\psi(r)=\begin{cases}-1,&r<-1,\\r,&-1\le r\le1,\\1,&r>1.\end{cases}$$

在r=1處兩側導數都為1；在r=−1處兩側都為−1，兩個連接點均可導，毋須任選一側。導數整體單調不減，所以$\rho$凸。與仿射函數$y_i-a$複合仍凸，四項求和的F也凸。

評分: 分段導數2分；兩個連接點1分；凸性及傳遞到F的理由1分。

題本 Q1(a)

(b) [6]

為什麼先試區間$[0,1]$？ 三個觀測都為0，只有一個為8；先檢查靠近多數觀測的位置，能讓三個殘差落在容易求導的平方區間。這只是候選區間，不是先假定答案；求出後還要驗區間及全局性。逐項看鏈式法則，$d\rho(-a)/da=-\psi(-a)=\psi(a)$，三項給$3\psi(a)$；第四項給$-\psi(8-a)=\psi(a-8)$。在候選解處，三個小殘差各產生大小$1/3$的拉力，剛好平衡異常點飽和為1的拉力。OLS則每個殘差的拉力隨大小線性增加，所以大異常點會把均值明顯拉走。

對殘差求導帶來因子−1，利用$\psi$為奇函數：

$$F^{\prime}(a)=-\sum_{i=1}^4\psi(y_i-a)=3\psi(a)+\psi(a-8).$$

在$0\le a\le1$上，$\psi(a)=a$且$\psi(a-8)=-1$，故$F^{\prime}(a)=3a-1$給$a_H=1/3$，確實在假設區間內。凸性保證零導數是全局最優。唯一性還要檢查：a小於0時導數為負；[0,1]內嚴格遞增且只過零一次；a大於1時，由單調性及$F^{\prime}(1)=2$可知導數為正。

$$G(a)=3a^2+(8-a)^2,\qquad G^{\prime}(a)=8a-16,\qquad a_{OLS}=2.$$

兩個估計優化不同目標。直接檢查：

$$F(1/3)=3\frac{(1/3)^2}{2}+\left(\frac{23}{3}-\frac12\right)=\frac{22}{3},\quad F(2)=10;\qquad G(2)=48,\quad G(1/3)=\frac{532}{9}>48.$$

把8改為80，在[0,1]仍有$\psi(a-80)=-1$，同一導數與唯一性論證仍給$a_H=1/3$；OLS常數則變為20。更一般，異常值B滿足$B-1/3\ge1$即$B\ge4/3$時，此Huber解保持不變。這是殘差導數飽和帶來的受限影響，不是說損失忽略異常值或最小化RSS。

評分: 正確導數及適用區間2分；解與唯一全局最優性2分；OLS答案1分；80時不變及理由1分。

題本 Q1(b)

(c) [3]

把求導拆成兩層。 對$\sqrt{1+r^2}=(1+r^2)^{1/2}$，外層導數為$\tfrac12(1+r^2)^{-1/2}$，內層導數為$2r$；相乘後才得到下面的一階導數。尾部極限可把分子分母同除以$|r|$：$r/\sqrt{1+r^2}=\operatorname{sign}(r)/\sqrt{1+1/r^2}$。因此兩端符號相反，不能兩端都寫1。“有界”指斜率，不是損失值；損失本身仍隨$|r|$增長。

$$\widetilde\rho^{\prime}(r)=\frac r{\sqrt{1+r^2}},\qquad\lim_{r\to+\infty}\widetilde\rho^{\prime}(r)=1,\qquad\lim_{r\to-\infty}\widetilde\rho^{\prime}(r)=-1.$$ $$\widetilde\rho^{\prime\prime}(r)=\frac1{(1+r^2)^{3/2}}>0.$$

相比之下，$(r^2/2)^{\prime}=r$無界。因此大殘差在偽Huber下貢獻有界斜率，而平方損失下可貢獻任意大斜率。偽Huber沒有分段連接的拐接，但最小點不一定與Huber完全相同。

評分: 導數1分；尾部極限及平方損失比較1分；大殘差意義1分。

題本 Q1(c)

(d) [3]

將“學習參數”和“應用參數”分開。 例如訓練折算出均值$m_{train}$及非零標準差$s_{train}$後，驗證觀測$x$應變成$(x-m_{train})/s_{train}$；不能重新用驗證折自己的均值，也不能預先用全體數據的均值。驗證折本來用於模擬未來沒見過的數據。另一方面，在多種損失中取最小CV值，相當於挑中了對這批驗證數據表現最好的候選，可能也挑中了隨機好運；這就是還要保留最終獨立測試集的原因。

第一，全數據標準化使每個驗證折參與訓練預處理，即使沒有用標籤也會洩漏。第二，最小CV分數已用於選損失，是經過選擇的驗證結果，不是獨立測試誤差。應先留獨立測試集；在開發數據做五折CV，每折僅用訓練子集學習標準化及模型，再用固定變換評驗證折。選定損失和超參數後，在全部開發數據重新擬合整條流程，最後在未參與選擇的測試集評一次。僅改名「測試集」不會改變它參與選擇的事實。

評分: 預處理洩漏1分；選擇偏差及驗證與獨立測試區別1分；修正順序1分。

題本 Q1(d)

Q2. 貪心擬合、重新擬合與嵌套模型 (18)

題本 Q2

(a) [2]

相關性是在比較哪兩個對象？ $D$是$3\times3$矩陣，每列$d_j\in\mathbb R^3$是一種可加入預測的方向；$y,r\in\mathbb R^3$分別是觀測和尚未解釋的部分，$c\in\mathbb R^3$是係數。初始$c=0$，所以$r=y$。選列用$|d_j^Tr|$，取絕對值是因為正負方向都可以改善擬合。更新大小來自展開$\|r-\gamma d_j\|^2=\|r\|^2-2\gamma d_j^Tr+\gamma^2\|d_j\|^2$，對$\gamma$求導置零，才得$\gamma=d_j^Tr/\|d_j\|^2$。本題列長為1，分母才消失。

$$\|d_1\|_2^2=1,\quad\|d_2\|_2^2=(3/5)^2+(4/5)^2=1,\quad\|d_3\|_2^2=1,\qquad D^Ty=(2,2,1/5)^T.$$

前兩欄絕對相關性並列最大，按編號規則選$d_1$。單位範數使題設增量$d_j^Tr$適用；一般非單位欄的一維最小二乘增量還需除以$\|d_j\|_2^2$。

評分: 範數及相關性1分；破平局1分。

題本 Q2(a)

(b) [5]

每輪都守住同一個賬目：預測加殘差等於$y$。 第一輪預測$2d_1=(2,0,0)^T$，從$y=(2,1,1/5)^T$相減得到新殘差。第二輪添加的是$(4/5)d_2=(12/25,16/25,0)^T$，不是把預測替換為這一向量。所以新預測為$(62/25,16/25,0)^T$，逐座標相減得下面殘差：第一座標$2-62/25=-12/25$，第二座標$1-16/25=9/25$。RSS是三個殘差平方之和，不是它們的和，也不是除以3後的MSE。

第一輪增量為2。第二次選擇前，必須針對新殘差重算相關性：

$$c^{(1)}=(2,0,0)^T,\quad r^{(1)}=(0,1,1/5)^T,\quad D^Tr^{(1)}=(0,4/5,1/5)^T.$$

因此選擇$d_2$，增量$4/5$。第一個係數保持2；MP沒有聯合重新擬合它。

$$c_{MP}=(2,4/5,0)^T,\quad r_{MP}=r^{(1)}-\frac45d_2=\begin{pmatrix}-12/25\\9/25\\1/5\end{pmatrix},\quad\mathrm{RSS}_{MP}=\frac{144+81}{625}+\frac1{25}=\frac25.$$

評分: 第一步1分；第二步相關性與選擇1分；增量及最後係數1分；殘差1分；RSS1分。

題本 Q2(b)

(c) [5]

OMP多做的一步是什麼？ 選中兩列後，允許兩個係數一起調整，所以未知數是$b=(b_1,b_2)^T\in\mathbb R^2$，$D_A$為$3\times2$。對目標求梯度得$2D_A^T(D_Ab-y)=0$，移項就是$2\times2$正規方程。右端$D_A^Ty=(2,2)^T$不是上一輪殘差的相關性；相關性用於選列，原始$y$用於重新擬合，二者職能不同。兩式相減實際給$(2/5)(b_1-b_2)=0$，再代回任一式得到共同係數。舊係數從2降為5/4並非“退步”，因為新列也在解釋第一座標。

第一輪OMP與MP相同，第二次仍選$d_2$。活躍矩陣及正規方程為：

$$D_A=\begin{pmatrix}1&3/5\\0&4/5\\0&0\end{pmatrix},\qquad\begin{pmatrix}1&3/5\\3/5&1\end{pmatrix}\begin{pmatrix}b_1\\b_2\end{pmatrix}=\begin{pmatrix}2\\2\end{pmatrix}.$$

目標仍為原始y，即$\min_b\|D_Ab-y\|_2^2$，不是凍結舊係數。行列式$1-9/25=16/25>0$保證唯一。兩式相減得$b_1=b_2$，再代入$(8/5)b_1=2$，兩者都為5/4。

$$c_{OMP}=(5/4,5/4,0)^T,\quad r_{OMP}=(0,0,1/5)^T,\quad\mathrm{RSS}_{OMP}=1/25.$$

檢查前兩項預測：$5/4+(3/5)(5/4)=2$，$(4/5)(5/4)=1$，恰好等於相應觀測。

評分: 活躍集及正規方程2分；兩個係數1分；殘差1分；RSS1分。

題本 Q2(c)

(d) [3]

正交不是“看起來方向不同”，而是內積為0。 一維最小二乘更新後，$d_j^T(r-\gamma d_j)=d_j^Tr-\gamma\|d_j\|^2=0$；它只保證當前選列。再沿另一個不正交方向移動，舊內積會變為$0-\gamma_2d_1^Td_2$，本例為$-(4/5)(3/5)=-12/25$。OMP的正規方程則一次令所有活躍方向的內積為0。比較的是相同活躍列上的擬合，不能由此推出對所有未來樣本或所有稀疏支持集都更優。

$$d_1^Tr_{MP}=-12/25,\qquad d_2^Tr_{MP}=\frac35\!\left(-\frac{12}{25}\right)+\frac45\frac9{25}=0,\qquad D_A^Tr_{OMP}=0.$$

MP殘差只與最近更新欄正交，不再與先前欄正交。因為$d_1^Td_2=3/5\ne0$，沿第二欄更新會改變第一坐標，破壞舊正交關係。OMP重新優化全部活躍係數，殘差同時正交於兩欄，本例RSS因此較小。這不證明OMP總能找到稀疏問題的全局最優支持集。

評分: MP內積1分；OMP正交性1分；非正交欄及聯合重新擬合解釋1分。

題本 Q2(d)

(e) [3]

證明的關鍵不是“大模型通常更好”，而是舊答案沒有被禁止。 $V_1,V_2$是允許的預測向量集合；擴大集合後，至少仍可以選擇舊預測，因此新的最小值不可能更大。若新增方向與舊殘差正交，舊預測可能仍最優，所以可以等號。在下方反例中，第二模型只能預測$(t,t,t)^T$；目標$(1-t)^2+2t^2$求導得$6t-2=0$，故$t=1/3$。MAE直接算為$((2/3)+(1/3)+(1/3))/3=4/9$，展示為何不能把RSS的結論換成另一個指標。

令$\widehat y_1\in V_1$為第一模型最優預測。由於$V_1\subseteq V_2$，它也在第二優化中可行：

$$\mathrm{RSS}_2=\min_{v\in V_2}\|y-v\|_2^2\le\|y-\widehat y_1\|_2^2=\mathrm{RSS}_1.$$

這裏只保證不增，不保證嚴格下降，亦不涉及測試誤差。MAE不是所優化目標，沒有相同保證。反例：$y=(1,0,0)^T$，$V_1=\{0\}$，$V_2=\operatorname{span}\{(1,1,1)^T\}$。最小二乘預測分別為0及$(1/3,1/3,1/3)^T$：

$$\mathrm{RSS}_1=1,\quad\mathrm{RSS}_2=2/3,\quad\mathrm{MAE}_1=1/3,\quad\mathrm{MAE}_2=4/9.$$

所以RSS下降而MAE上升。數值反例幫助理解，並非正確解釋以外的額外作答要求。

評分: 可行集包含的完整證明2分；MAE無保證及正確解釋1分。

題本 Q2(e)

Q3. 核PCA及其正規化 (17)

題本 Q3

(a) [5]

先畫清三個空間。 輸入$t_i$是標量，但映射$\phi(t)=(t,t^2)^T$把它變為二維向量；三個樣本逐行排列，所以$\Phi,\Phi_c$均為$3\times2$。均值$\overline\phi$是$2\times1$，中心化公式為$\Phi_c=\Phi-\mathbf1\overline\phi^T$，其中$\mathbf1$是$3\times1$。例如第一行$(-1,1)-(0,2/3)=(-1,1/3)$。$K$為$3\times3$，元素$K_{ij}=\phi(t_i)^T\phi(t_j)$比較樣本而不是比較特徵；例如$K_{13}=(-1)(1)+(1)(1)=0$。

為什麼核矩陣要左右各中心化一次？ $C=I_3-\mathbf1\mathbf1^T/3$左乘$\Phi$從每個樣本減去均值；因此$(C\Phi)(C\Phi)^T=C\Phi\Phi^TC=CKC$。逐元素公式是$(K_c)_{ij}=K_{ij}-\overline K_{i\cdot}-\overline K_{\cdot j}+\overline K_{\cdot\cdot}$，最後加總均值是補回被減了兩次的部分。本題行均值為$(2/3,0,2/3)$，總均值$4/9$，故$(K_c)_{11}=2-2/3-2/3+4/9=10/9$，$(K_c)_{12}=0-2/3-0+4/9=-2/9$。

先構造特徵矩陣再中心化。原標量輸入均值為0，不代表非線性平方特徵均值為0；後者是2/3：

$$\Phi=\begin{pmatrix}-1&1\\0&0\\1&1\end{pmatrix},\quad\overline\phi=\begin{pmatrix}0\\2/3\end{pmatrix},\quad\Phi_c=\begin{pmatrix}-1&1/3\\0&-2/3\\1&1/3\end{pmatrix}.$$

每行減去同一均值行。因為$C=C^T=C^2$，Gram矩陣雙中心化等於中心化特徵的Gram矩陣：

$$K=\Phi\Phi^T=\begin{pmatrix}2&0&0\\0&0&0\\0&0&2\end{pmatrix},\quad K_c=CKC=\Phi_c\Phi_c^T=\frac19\begin{pmatrix}10&-2&-8\\-2&4&-2\\-8&-2&10\end{pmatrix}.$$

三行和分別為$(10-2-8)/9$、$(-2+4-2)/9$及$(-8-2+10)/9$，全為0，所以$K_c\mathbf1=0$。若不成立，先查是否只減行均值而沒有完成雙中心化。

評分: 特徵均值與中心化矩陣2分；K1分；中心化K1分；零行和檢查1分。

題本 Q3(a)

(b) [4]

這些向量不是憑空猜的。 中心化已給出$K_c\mathbf1=0$，所以常數向量是零特徵方向。第一、第三個樣本關於0對稱，先試反對稱向量$(-1,0,1)^T$；矩陣乘法給$(-18,0,18)^T/9=2(-1,0,1)^T$。再找既垂直於常數向量、又垂直於該反對稱向量的向量：兩端應相等且三項和為0，可取$(1,-2,1)^T$；相乘給$(6,-12,6)^T/9=(2/3)(1,-2,1)^T$。最後分別除以原長度$\sqrt2,\sqrt6,\sqrt3$，才得到單位向量。特徵值衡量方向大小，單位化只改向量長度，不改特徵值。

取三個兩兩正交的單位向量，逐個驗證矩陣乘積：

$$q_1=\frac1{\sqrt2}(-1,0,1)^T,\quad q_2=\frac1{\sqrt6}(1,-2,1)^T,\quad q_3=\frac1{\sqrt3}(1,1,1)^T;$$ $$K_cq_1=2q_1,\qquad K_cq_2=\frac23q_2,\qquad K_cq_3=0.$$

它們構成$\mathbb R^3$的標準正交基，沒有遺漏特徵值，譜為$2,2/3,0$。最大特徵值嚴格較大，僅剩整體符號歧義。第三分量要求為正，因此$q=q_1$、$\lambda=2$。跡檢查：$\operatorname{tr}(K_c)=24/9=8/3=2+2/3+0$。

評分: 三個特徵值2分；單位主特徵向量1分；驗證與符號1分。

題本 Q3(b)

(c) [4]

先做維數檢查，再做正規化。 $q\in\mathbb R^3$的三個數給三個樣本加權，不是二維特徵空間中的軸；$\Phi_c^T$為$2\times3$，故$\Phi_c^Tq\in\mathbb R^2$才有正確的方向維數。其第一座標為$(-1)(-1/\sqrt2)+0+(1)(1/\sqrt2)=\sqrt2$；第二座標為$(1/3)(-1/\sqrt2)+0+(1/3)(1/\sqrt2)=0$。但“維數正確”不等於“長度為1”，所以還需$w=\Phi_c^Tq/\sqrt\lambda$。

投影得分$z_i$是第$i$行中心化特徵與$w$的內積，一個樣本得到一個標量，全部疊成$z\in\mathbb R^3$。這裏$w=(1,0)^T$只保留第一特徵，因而得分恰為$(-1,0,1)^T$。一般核方法未必能顯式寫出特徵，但$z=K_cq/\sqrt\lambda$仍能計算相同訓練得分。下面的長度證明同時解釋了為什麼必須要求$\lambda>0$。

q是樣本編號空間的單位向量，w是特徵空間的方向，兩者維度不同。對正特徵值：

$$\|w\|_2^2=\frac{q^T\Phi_c\Phi_c^Tq}{\lambda}=\frac{q^TK_cq}{\lambda}=q^Tq=1.$$ $$\Phi_c^Tq=(\sqrt2,0)^T,\qquad w=(1,0)^T,\qquad z=\Phi_cw=(-1,0,1)^T=\frac{K_cq}{\sqrt\lambda}=\sqrt\lambda\,q.$$

漏除$\sqrt\lambda$會使方向長度為$\sqrt2$，得分多乘$\sqrt2$，方差多乘2。錯在改變單位方向約束，不只是記號不規範。零特徵值不能放在這個分母。

評分: 單位長度證明2分；w及得分1分；遺漏正規化的後果1分。

題本 Q3(c)

(d) [4]

三個不同的量不要混成一個。 核矩陣特徵值2是平方得分總量；樣本方差是它再除以$n-1=2$；解釋比例則是保留方差除以總方差。直接核對：得分均值為0，所以樣本方差$[(-1)^2+0^2+1^2]/2=1$。特徵協方差的交叉項為$[(-1)(1/3)+0(-2/3)+(1)(1/3)]/2=0$，第二對角項為$[(1/3)^2+(-2/3)^2+(1/3)^2]/2=1/3$。

重建為何要加回均值？ $z_iw$重建的是“離均值多遠”，不是原特徵。完整重建是$\widehat\phi_i=\overline\phi+z_iw$。這裏第一座標全保留，第二座標全用均值2/3代替，因此只損失第二特徵的偏差。重建位於二維特徵空間，不必等於某個真實輸入的$\phi(t)$：例如$(0,2/3)$並不是$(t,t^2)$形式。題目沒有要求解這種逆映射。

題設樣本協方差分母為n−1=2，不是3：

$$S_\phi=\frac12\Phi_c^T\Phi_c=\begin{pmatrix}1&0\\0&1/3\end{pmatrix},\quad\operatorname{Var}(z)=1=\frac{\lambda_1(K_c)}{n-1},\quad\eta=\frac1{1+1/3}=\frac34.$$

先用得分乘方向重建中心化特徵，再加回均值：

$$\widehat\Phi_c=zw^T=\begin{pmatrix}-1&0\\0&0\\1&0\end{pmatrix},\qquad\widehat\Phi=\begin{pmatrix}-1&2/3\\0&2/3\\1&2/3\end{pmatrix}.$$ $$\|\Phi-\widehat\Phi\|_F^2=(1/3)^2+(-2/3)^2+(1/3)^2=\frac23.$$

誤差可用被捨棄核特徵值$\lambda_2(K_c)=2/3$核對，亦可用$(n-1)\lambda_2(S_\phi)=2(1/3)$。協方差正規化改變特徵值數值，不改變解釋比例；總平方誤差為2/3，不是1/3。

評分: 樣本方差1分；比例1分；重建與誤差2分。

題本 Q3(d)

Q4. 學習距離與隨機投影 (16)

題本 Q4

(a) [4]

因子分解把抽象二次型變成平方長度。 $M$為$2\times2$，$h=(h_1,h_2)^T\in\mathbb R^2$，可選$L$為$1\times2$，使二維向量映射成一個數。外積$L^TL$的四項為$1,2,2,4$，正好恢復$M$。半正定要求對所有$h$有非負二次型，正定則要求每個非零$h$都嚴格為正；兩者只差這個嚴格條件，卻決定距離能否區分不同點。由$Lh=h_1+2h_2$可見$h=(-2,1)^T$非零卻映成0，所以秩只能為1而不是2。

$$L=\begin{pmatrix}1&2\end{pmatrix},\quad L^TL=M,\quad h^TMh=\|Lh\|_2^2=(h_1+2h_2)^2\ge0.$$

這對每個h證明半正定性，不是逐元素檢查正負。第二行是第一行兩倍，且第一行非零，因此rank(M)=1。解$h_1+2h_2=0$得到以下零空間；其非零向量亦說明M不正定。

$$\ker M=\operatorname{span}\{(-2,1)^T\}.$$

評分: L1分；半正定證明1分；秩1分；零空間1分。

題本 Q4(a)

(b) [3]

先算變換後的座標，再算距離。 定義$d_M(x,y)=\sqrt{(x-y)^TM(x-y)}=|Lx-Ly|$。$u=(2,0)^T$與$v=(0,1)^T$在平面不同，卻都落到數軸的2，因此距離為0；這是降秩映射壓扁了一個方向。加$\tau I$須有$\tau>0$，其作用是給每個原方向補上$\tau$倍歐氏平方長度。最後的$5\tau$是平方距離，若問距離本身還要開方得到$\sqrt{5\tau}$。

$$Lo=0,\quad Lu=2,\quad Lv=2,\qquad d_M(o,u)=2,\quad d_M(o,v)=2,\quad d_M(u,v)=0.$$

u與v不同卻距離為0，所以這是偽度量，不是全平面上的度量。失敗的是分離性，不是對稱或非負性。加上$\tau I$後，每個非零方向嚴格為正：

$$h^TM_\tau h=(h_1+2h_2)^2+\tau\|h\|_2^2>0\quad(h\ne0).$$

因為$u-v=(2,-1)^T$位於原零空間：

$$d_{M_\tau}(u,v)^2=(u-v)^TM(u-v)+\tau\|u-v\|_2^2=5\tau.$$

原先被壓扁方向恢復正長度；正定二次型定義真正度量。

評分: 三個距離1分；偽度量及原因1分；5τ與正定理由1分。

題本 Q4(b)

(c) [3]

隨機的是矩陣，不是這裏的向量。 先固定$a\in\mathbb R^d$，再抽取$R\in\mathbb R^{k\times d}$，輸出$Ra\in\mathbb R^k$。期望是對重複抽取矩陣而言。將一個座標的平方展開：

$$\mathbb E b_\ell^2=\sum_j a_j^2\mathbb E R_{\ell j}^2+2\sum_{j<m}a_ja_m\mathbb E(R_{\ell j}R_{\ell m}).$$

零均值加獨立性給$\mathbb E(R_{\ell j}R_{\ell m})=\mathbb ER_{\ell j}\mathbb ER_{\ell m}=0$，而$\mathbb E R_{\ell j}^2=\operatorname{Var}(R_{\ell j})=1/k$。所以每個輸出座標平均分到原平方長度的$1/k$，再將$k$個座標相加便恢復原長度平方。這裏只證明平方範數的期望；不能把平方根直接移進期望，斷言$\mathbb E\|Ra\|=\|a\|$。

第ℓ個投影坐標寫為$b_\ell=(Ra)_\ell=\sum_{j=1}^dR_{\ell j}a_j$。均值為0使$\mathbb E b_\ell=0$；獨立性消去交叉項。每項方差為1/k，因此：

$$\mathbb E b_\ell^2=\operatorname{Var}(b_\ell)=\sum_{j=1}^d a_j^2\frac1k=\frac{\|a\|_2^2}{k},\qquad\mathbb E\|Ra\|_2^2=\sum_{\ell=1}^k\mathbb E b_\ell^2=\|a\|_2^2.$$

若元素方差誤設為1，結果會是$k\|a\|_2^2$。期望恆等式不控制每次抽樣誤差，(d)另加集中機率假設。

評分: 逐坐標均值方差1分；獨立性消去交叉項1分；各行求和1分。

題本 Q4(c)

(d) [6]

從“一對成功”到“全部同時成功”要付出點對數量。 對固定點對取$a=x_i-x_j$，題給單方向界控制事件$E_{ij}=\{|\|Ra\|^2-\|a\|^2|>\varepsilon\|a\|^2\}$。任意一對失敗就使整體要求失敗，所以整體壞事件是並集，不是交集；所有點對共用一個$R$，也不能把成功概率當獨立事件相乘。

對$n\ge2$、$0<\delta<1$，取對數的中間步驟是$\log(n(n-1))-ck\varepsilon^2\le\log\delta$，再得$ck\varepsilon^2\ge\log(n(n-1))-\log\delta$。移項時負號方向要檢查，最終除以正數$c\varepsilon^2$。維數是整數，向上取整才保證不低於門檻。保證的是平方距離；若要寫普通距離，應取$\sqrt{1-\varepsilon}$及$\sqrt{1+\varepsilon}$因子，不能無解釋地照抄平方距離界。

至多有$n(n-1)/2$對編號。重複點差向量為0，不會失敗，因此保留全部編號對仍是有效上界。每個壞事件為相對平方距離誤差超過ε。聯集界不要求這些事件互相獨立：

$$\Pr(\bigcup_{i<j}E_{ij})\le\frac{n(n-1)}2\,2e^{-ck\varepsilon^2}=n(n-1)e^{-ck\varepsilon^2}.$$

要求右邊不超過δ，取自然對數再移項。k為整數，因此充分條件為：

$$k\ge\left\lceil\frac{\log\!\bigl(n(n-1)/\delta\bigr)}{c\varepsilon^2}\right\rceil.$$

於是以至少$1-\delta$機率，同一個隨機矩陣同時滿足：

$$(1-\varepsilon)\|x_i-x_j\|_2^2\le\|Rx_i-Rx_j\|_2^2\le(1+\varepsilon)\|x_i-x_j\|_2^2\quad\forall\,i,j.$$

這是充分上界，不是必要最小維數。即使界大於d，亦不能僅憑此證明所有降維都不可能。須區分兩層量詞：至少$1-\delta$機率仍允許失敗；點集須在抽取R之前固定。若$k<d$，任何線性映射都有非零$a\in\ker R$，於是$\|Ra\|^2=0<(1-\varepsilon)\|a\|^2$，其中$0<\varepsilon<1$。所以一個這樣的映射不可能保留整個原空間的全部距離。

評分: 點對數及聯集界2分；充分維數2分；仍可能抽樣失敗1分；全空間零空間反證1分。

題本 Q4(d)

Q5. 完整一輪高斯EM (14)

題本 Q5

(a) [4]

E步到底在問什麼？ 兩個$x_i$是一維觀測，兩個成分各有一個權重$\pi_k$、均值$\mu_k$及方差$\sigma_k^2$；隱藏的是每個觀測來自哪個成分。責任度$r_{ik}$是“已見到$x_i$後，它來自成分$k$的條件概率”，不是高斯密度本身。貝葉斯公式為

$$r_{ik}=\frac{\pi_k^{old}\varphi(x_i;\mu_k^{old},(\sigma_k^2)^{old})}{\sum_{h=1}^{2}\pi_h^{old}\varphi(x_i;\mu_h^{old},(\sigma_h^2)^{old})}.$$

矩陣$r$的行是觀測，列是成分；同一行分母相同，表示該觀測的總混合密度。此步所有參數都用舊值，不能算完第一行就改均值。舊均值為−2、2，觀測到自己對應均值距離0，到另一均值距離4；方差相同使前因子$A$可約掉，但先驗$1/3,2/3$不相等，不能約掉。第二行分母為$A/6+2A/3=5A/6$，所以第一責任度$(A/6)/(5A/6)=1/5$。

令舊共同方差$s^2=8/\log2$，密度前因子$A=(2\pi s^2)^{-1/2}$。距離均值4時，密度乘以下因子：

$$\exp\!\left(-\frac{4^2}{2s^2}\right)=e^{-\log2}=\frac12.$$

兩行密度為$(A,A/2)$及$(A/2,A)$。先乘不相等的舊先驗，再正規化：x=−2的未正規化值為$(A/3,A/3)$，x=2為$(A/6,2A/3)$。因此：

$$(r_{ik})=\begin{pmatrix}1/2&1/2\\1/5&4/5\end{pmatrix}.$$

每行和為1。第一個觀測恰在第一均值，卻只有1/2責任度，因為第二成分較大先驗抵銷了較小密度。只按最近均值硬分配會忽略此區別。

評分: 指數密度比1分；使用先驗1分；每行責任度各1分。

題本 Q5(a)

(b) [6]

M步的分母為什麼有兩個？ E步按行分配“一個觀測的1份概率”；M步按列收集“一個成分分到多少觀測”。因此$N_k=\sum_i r_{ik}$是成分有效樣本量，$\pi_k^{new}=N_k/n$除以總觀測數$n=2$，而均值、方差除以該成分自己的$N_k$。第一列正規化後給兩個觀測權重$5/7,2/7$；第二列給$5/13,8/13$。這也解釋兩個新均值為什麼仍在觀測區間$[-2,2]$內。

把第二個方差也完整算一次。 圍繞新均值$6/13$，兩項偏差是$-2-6/13=-32/13$、$2-6/13=20/13$。加權平方和為$(1/2)(1024/169)+(4/5)(400/169)=832/169$；再除$13/10$得$640/169$。不是除以2，也不是仍圍繞舊均值2。

二階矩捷徑來自展開$\sum_i r_{ik}(x_i-\mu)^2=\sum_i r_{ik}x_i^2-2\mu\sum_i r_{ik}x_i+\mu^2N_k$，在新均值處$\sum_i r_{ik}x_i=N_k\mu$，故除以$N_k$後為加權二階矩減$\mu^2$。舊方差相同只是初始條件，本題分別更新兩個方差，並未施加“更新後必須相同”的約束。

本輪M步固定全部責任度。各欄和為有效樣本量，可以不是整數，但總和為2：

$$N_1=\frac12+\frac15=\frac7{10},\quad N_2=\frac12+\frac45=\frac{13}{10},\quad\pi_1^{new}=\frac7{20},\quad\pi_2^{new}=\frac{13}{20}.$$

把每個成分的責任度加權觀測和除以自身有效樣本量：

$$\mu_1^{new}=\frac{(-2)(1/2)+2(1/5)}{7/10}=-\frac67,\qquad\mu_2^{new}=\frac{(-2)(1/2)+2(4/5)}{13/10}=\frac6{13}.$$

兩個觀測的平方均為4，因此每個正規化加權二階矩也是4。減去新均值平方得方差：

$$(\sigma_1^2)^{new}=4-(-6/7)^2=\frac{160}{49},\qquad(\sigma_2^2)^{new}=4-(6/13)^2=\frac{640}{169}.$$

這是以下方差定義的計算捷徑，並非更換定義：

$$(\sigma_k^2)^{new}=\frac{\sum_i r_{ik}(x_i-\mu_k^{new})^2}{N_k}.$$

第一成分偏差為$-8/7,20/7$；加權平方和$(1/2)(64/49)+(1/5)(400/49)=112/49$，再除7/10得160/49。以下三個一致性檢查分別恢復總機率、觀測均值及二階矩：

$$\sum_k\pi_k^{new}=1,\quad\sum_k\pi_k^{new}\mu_k^{new}=0,\quad\sum_k\pi_k^{new}\bigl((\sigma_k^2)^{new}+(\mu_k^{new})^2\bigr)=4.$$

評分: 有效樣本量及權重2分；兩個均值2分；兩個方差2分。單一算術錯誤後仍可保留方法分。

題本 Q5(b)

(c) [2]

把“最大化似然”落實到導數。 寫$S_k=\sum_i r_{ik}(x_i-\mu_k^{new})^2$，則$Q'(v)=(S_k-N_kv)/(2v^2)$。本題$S_k>0,N_k>0$，分母始終正；當$v<S_k/N_k$時導數正，超過該點時導數負，因此駐點確為最大點。若某成分$N_k=0$，這些更新不能直接相除；若$S_k=0$，可能出現零方差邊界退化，不能不加條件套用正方差結論。本題兩列責任度都正且兩個觀測不同，因此沒有這兩種問題。

M步在責任度固定時最大化加權對數似然。正方差參數v的相關部分為：

$$Q(v)=-\frac{N_k}{2}\log v-\frac1{2v}\sum_i r_{ik}(x_i-\mu_k^{new})^2+\mathrm{const},$$ $$Q^{\prime}(v)=-\frac{N_k}{2v}+\frac{\sum_i r_{ik}(x_i-\mu_k^{new})^2}{2v^2}=0.$$

因此分母為$N_k$，不是無偏樣本修正$N_k-1$。本例$N_1=0.7$，機械除以$N_1-1$甚至會得到負方差。均值亦在本輪M步優化，因此偏差須圍繞新均值，不能沿用舊的−2或2。

評分: 最大似然分母1分；新均值及理由1分。

題本 Q5(c)

(d) [2]

先對成分求和，再對觀測取對數求和。 一個觀測可能來自任一成分，所以其密度是加權密度之和；兩個獨立觀測的聯合密度是這兩個混合密度相乘，取對數才變成下面的和。不能交換“log”和成分求和。E步用舊參數算後驗，使輔助下界在舊參數處貼住觀測對數似然；M步提高這個固定責任度的下界，因此新的觀測對數似然不低於舊值。這是軟EM的改進機制，不是一次更新就找到最佳聚類的保證。下一輪才用所有新參數重新計算責任度。

$$\ell(\theta)=\sum_{i=1}^2\log\!\left[\pi_1\varphi(x_i;\mu_1,\sigma_1^2)+\pi_2\varphi(x_i;\mu_2,\sigma_2^2)\right],\qquad\ell(\theta^{new})\ge\ell(\theta^{old}).$$

當E步、M步正確執行且更新有定義時，上述不等式成立。對象是觀測混合對數似然，不是最大單成分密度。它不保證唯一全局最優、正確標籤或不同初始化的相同結果。交換成分標籤不改變混合密度；無約束高斯混合還可能在方差趨零時退化。應更新全部指定參數，而非只更新一個成分。

評分: 正確目標與單調性1分；至少一種合理局限1分。

題本 Q5(d)

Q6. 均值漂移與密度層次 (13)

題本 Q6

(a) [4]

這裏有兩類位置：會動的查詢點和不動的觀測。 更新的是$p_t$；原始觀測集合$\{0,1,2,4,8\}$保持不變。平坦核只問$|x_i-p_t|\le2$是否成立，不按距離遠近給不同權重。起點4的五個距離為4、3、2、0、4，因此只取2與4，平均$(2+4)/2=3$；到3後取1、2、4，平均$(1+2+4)/3=7/3$。一次位置變化變小並不等於已停止，要再次核實鄰域及下一次平均不變。

平坦核對閉半徑2內原始觀測等權，因此每步是這些點的普通平均：

$$p_0=4:\ \{2,4\}\longrightarrow p_1=3;\qquad p_1=3:\ \{1,2,4\}\longrightarrow p_2=7/3;$$ $$p_2=7/3:\ \{1,2,4\}\longrightarrow p_3=7/3=p_2.$$

位置3時，觀測1恰好在半徑2邊界，必須納入。位置7/3到0,1,2,4,8的距離為$7/3,4/3,1/3,5/3,17/3$，核實鄰域不變及固定點$p^*=7/3$。不可把參考觀測4改成移動後位置3；參考樣本固定。

評分: 三個鄰域與更新3分；明確檢查固定點1分。

題本 Q6(a)

(b) [4]

本小問使用新的四點數據，別沿用(a)的五點。 這裏$x_1=0,x_2=1,x_3=4,x_4=5$，下標是編號，不是數值。核心距離是以該點為中心、能覆蓋三個觀測（含自身）的最小半徑。對於$x_2=1$，到自己為0，到0為1，到4為3，到5為4，所以第三項為3。隨後每條邊取$\max\{\operatorname{core}_3(x_i),\operatorname{core}_3(x_j),|x_i-x_j|\}$；例如(1,4)取$\max\{4,4,5\}=5$，而(2,3)取$\max\{3,3,3\}=3$。

先計入自身零距離，再選第三個距離：

$$\begin{array}{c|c|c}x_i&\mathrm{sort}_j|x_i-x_j|&\operatorname{core}_3(x_i)\\\hline0&0,1,4,5&4\\1&0,1,3,4&3\\4&0,1,3,4&3\\5&0,1,4,5&4\end{array}$$ $$\begin{array}{c|rrrrrr}(i,j)&(1,2)&(1,3)&(1,4)&(2,3)&(2,4)&(3,4)\\\hline |x_i-x_j|&1&4&5&3&4&1\\d_{mr}(x_i,x_j)&4&4&5&3&4&4\end{array}$$

例如(1,2)普通距離只有1，但互可達距離為$\max\{4,3,1\}=4$，反映兩端密度要求。這是三項最大值，不是和；不可排除自身後仍取相同鄰居編號。

評分: 四個核心距離2分；六條邊權2分。

題本 Q6(b)

(c) [3]

生成樹要求連通且沒有環。 四個頂點的樹恰有三條邊，不是簡單挑最小的三條邊：若三邊只圍着三個頂點成環，第四點仍沒連接。Kruskal逐條檢查一條候選邊的兩端是否已在同一連通分量；若是就跳過。選(2,3)後分量為$\{1\},\{2,3\},\{4\}$；選(1,2)後為$\{1,2,3\},\{4\}$；此時(1,3)在同一分量內，而(2,4)連接兩個分量，所以後者可選。

先按權重排序，再按題設字典序破平局：

$$(2,3):3;\quad(1,2):4,\ (1,3):4,\ (2,4):4,\ (3,4):4;\quad(1,4):5.$$

先選(2,3)，再選(1,2)。跳過(1,3)，因為它與前兩邊形成環。再選(2,4)，四點全部連通：

$$T=\{(2,3),(1,2),(2,4)\},\qquad w(T)=3+4+4=11.$$

這些邊在原數值中連接(1,4),(0,1),(1,5)。沒有破平局規定時其他同權樹亦可能正確，但本題已有規則，須遵守。

評分: 排序與跳環1分；樹邊1分；總權重1分。

題本 Q6(c)

(d) [2]

閾值切割是在圖上刪邊，不是在數軸上按相鄰間隔分組。 保留條件是互可達邊權不超過3；雖然0與1的普通距離只有1，它們之間的邊權是4，仍被刪除。孤立頂點也是連通分量，所以必須列出兩端單點。但“連通分量”只是此閾值下的圖論對象，“最終簇”或“噪聲”還取決於後續算法規則，兩種名稱不能直接互換。

權重不超過3的切割只保留邊(2,3)，連通分量為：

$$\{x_1\},\ \{x_2,x_3\},\ \{x_4\}=\{0\},\ \{1,4\},\ \{5\}.$$

這只是密度層次的一個閾值切片。HDBSCAN仍需根據最小簇大小等參數壓縮層次，並按穩定性選最後簇。題目未提供這些後續選擇，不能僅由切片認定單點必為最後簇或噪聲。

評分: 連通分量1分；指出層次壓縮、穩定性與最後選擇未完成1分。

題本 Q6(d)

Q7. 軟區域與中位中心 (6)

題本 Q7

(a) [3]

區域邊界來自“到兩站點一樣近”。 在0與10之間，$|t|=|t-10|$給$t=5$；插入3後，新站點與0的邊界為$(0+3)/2=3/2$，與10的邊界為$(3+10)/2=13/2$。先保留插入前的舊區域，再求新區間與它們的重疊，不能用更新後的舊區域，否則區域內部互不重疊。權重定義是$w_j=\operatorname{length}(R_x\cap R_j)/\operatorname{length}(R_x)$，所以分別算$(7/2)/5=7/10$及$(3/2)/5=3/10$；分母是同一個新區間長度。

舊站點0和10的中點為5，新站點3的兩邊界分別是它與0、10的中點：

$$R_1=(-\infty,5],\quad R_2=[5,\infty),\quad R_x=[3/2,13/2],\quad\operatorname{length}(R_x)=5.$$ $$\operatorname{length}(R_x\cap R_1)=5-3/2=7/2,\qquad\operatorname{length}(R_x\cap R_2)=13/2-5=3/2,\quad(w_1,w_2)=(7/10,3/10).$$

權重非負且和為1。共享端點長度為0，不影響答案。舊區域雖無界，新區間及重疊長度有限，不涉及無窮長度相除。這是重疊權重，不是點到站點距離的比例。

評分: 舊邊界及新區間1分；兩個重疊長度1分；正規化權重1分。

題本 Q7(a)

(b) [3]

先確認距離和中心允許在哪裏。 本題最小化絕對距離總和，不是平方距離總和。連續中心允許任意實數$c$，medoid則只能選觀測$0,2,9,11$中的一個；必須先求連續最小點集合，再與可選觀測相交。對於$2\le c\le9$，$|2-c|=c-2$而$|9-c|=9-c$，所以移動$c$時左右變化正好抵消。配對下界的等號條件分別是$c\in[0,11]$和$c\in[2,9]$，交集才是全部答案。若改成平方距離，目標及導數都變了，均值5.5雖也在本題中位區間，卻不能因此證明兩種規則一般相同。

$$H(c)=|c|+|2-c|+|9-c|+|11-c|.$$

對每個[2,9]內的c，按符號展開得到同一值：

$$H(c)=c+(c-2)+(9-c)+(11-c)=18.$$

為證明全局最優並找齊所有最小點，配對端點並用三角不等式：

$$|c|+|11-c|\ge11,\qquad|2-c|+|9-c|\ge7.$$

總和至少18，兩式同時等號恰在c屬於[2,9]。因此全部連續一中位中心為[2,9]；限制為觀測值時恰有兩個一medoid：2和9。偶數個樣本的中間兩數平均只是一個最小點，不是唯一解。

$$\sum_i\|x_i-c\|_1=\sum_j\sum_i|x_{ij}-c_j|.$$

L1目標按坐標分離，因此逐坐標中位數最小化它。歐氏長度透過平方根耦合坐標，總和一般由幾何中位數最小化，不能逐坐標套用。點(0,0),(2,0),(0,2)的逐坐標中位數為(0,0)，歐氏距離總和4；改取(1/2,1/2)，總和為$1/\sqrt2+\sqrt{10}\approx3.869<4$，直接否定歐氏情形的一般規則。下界證明及反例用於理解，不是額外要求的證明任務。

評分: 全部連續中心1分；全部medoid1分；區分L1及歐氏距離1分。

題本 Q7(b)

訂正路線：Q1檢查鏈式求導及損失與懲罰；Q2逐輪列殘差、選擇、係數與預測，OMP右端保留原始y；Q3先驗零行和，再區分核特徵值與特徵空間方差；Q4寫清固定點集、隨機抽樣、全部點對及失敗機率；Q5分開按行責任度正規化與按欄有效樣本量；Q6檢查參考點固定、邊界計入及自身計入；Q7先寫距離函數及中心允許集合，再用中位數規則。