90分鐘 · 100分 · 7道大題。原創自主練習，不是官方考試規格或權重預測。回答所有小問，寫清計算與證明，盡量保留精確值；需要小數答案時說明捨入方法；特徵向量及配對奇異向量一致反號可接受。以題面分母、定義域及平局規則為準，不可無條件求逆。本練習使用Casio fx-50FH II，可用一張雙面A4參考紙；這是練習安排，不是新增官方考試規定。

配套題本 · Revision

評分用於自評；等價正確方法同分。單一算術錯誤後若方法正確，應保留相應方法分，不反覆扣同一錯誤。請先讀題本；以下說明條件與核對，不只列答案。

Q1. 加權多項式回歸與唯一性 (20)

配套題本 Q1

(a) [4]

每筆記錄貢獻截距、一次、二次三項。W對稱，因此殘差範數含W²；展開二次型後求導。Hessian半正定，駐點條件足以全局最優；若正定則進一步唯一。

$$\begin{gathered} M=\begin{pmatrix}1&-2&4\\1&-1&1\\1&1&1\\1&2&4\end{pmatrix},\quad W=\operatorname{diag}(1,2,2,1),\quad y=(2,1,3,4)^T. \\R(c)=(y-Mc)^TW^2(y-Mc)=y^TW^2y-2c^TM^TW^2y+c^TM^TW^2Mc. \\\nabla R(c)=-2M^TW^2y+2M^TW^2Mc=0,\qquad M^TW^2M\widehat c=M^TW^2y. \\\nabla^2R(c)=2M^TW^2M\succeq0. \end{gathered}$$

把每個對象先認清。 未知量不是四個擬合值，而是所有觀測共用的三個係數：c是3維列向量，y和殘差是4維列向量。M有4行、3列，每一行對應一條觀測，每一列對應一個基函數；第一列全為1，所以不能忘記截距。W是4×4的對角矩陣，左乘殘差表示分別縮放四條殘差；因此WM是4×3，正規方程左邊的係數矩陣是3×3，右邊是3維列向量。

為什麼出現平方權重？ 本題先把第i條殘差乘以wᵢ，然後才平方，所以權重2意味着該殘差平方被乘以4。展開時兩個交叉項互為轉置，且都是標量，故能合併成係數−2的一項。第一項不含c，求導為零；對稱二次型的導數則給出兩倍矩陣乘c。令梯度為零不是隨意套公式，而是在求這個特定目標的駐點。

何時可以寫逆矩陣？ 半正定只保證凸性，不自動保證唯一性；必須再證明正定或滿列秩，才能用逆矩陣表示唯一系數。本題把這一條件留到(c)證明。只寫“最小二乘所以可逆”不能代替證明。

評分： M、W共2；加權二次型1；求導方程1。

配套題本 Q1(a)

(b) [7]

橫坐標及權重對稱，奇數階加權矩為零。反應決定右端；先解獨立一次項，再解二元系統。代入四個輸入後算加權而非普通殘差平方和。正交檢查是MᵀW²r，不要求未加權殘差正交。

$$\begin{gathered} \sum w_i^2=10,\quad\sum w_i^2x_i=\sum w_i^2x_i^3=0,\quad\sum w_i^2x_i^2=16,\quad\sum w_i^2x_i^4=40. \\M^TW^2M=\begin{pmatrix}10&0&16\\0&16&0\\16&0&40\end{pmatrix},\quad M^TW^2y=\begin{pmatrix}22\\12\\40\end{pmatrix}. \\10c_0+16c_2=22,\quad16c_1=12,\quad16c_0+40c_2=40,\quad10(40)-16^2=144. \\c_0=\frac{22(40)-16(40)}{144}=\frac53,\quad c_1=\frac34,\quad c_2=\frac{10(40)-16(22)}{144}=\frac13. \\\widehat f(x)=\frac53+\frac34x+\frac13x^2,\quad \widehat y=(3/2,5/4,11/4,9/2)^T,\quad r=(1/2,-1/4,1/4,-1/2)^T. \\R(\widehat c)=\frac14+4\frac1{16}+4\frac1{16}+\frac14=1,\quad W^2r=(1/2,-1,1,-1/2)^T,\quad M^TW^2r=0. \end{gathered}$$

怎樣從數據得到矩陣，而不是背答案？ M的三列是1、x、x²；取任意兩列相乘，再乘平方權重並求和，就是Gram矩陣對應的條目。因此左上角是1+4+4+1=10，左下角是4+4+4+4=16，右下角是16+4+4+16=40。含奇數次x的條目正負抵消；這裏要同時有位置與權重對稱，不能只看橫座標。

右端還包含響應y，不能直接套“奇數項為零”：三個分量分別為2+4+12+4=22、−4−4+12+8=12，以及8+4+12+16=40。先用中間一行求一次項，再處理截距和二次項，是利用零條目簡化運算，不是忽略其他方程。二元系統行列式144非零，故這兩個係數可唯一求出。

代回和核驗怎麼做？ 例如在x=−2，預測是5/3−3/2+4/3=3/2，所以第一條殘差是2−3/2=1/2；其餘三條按同一順序計算。四個加權誤差貢獻恰好各為1/4，總和為1。檢查一次項的加權內積時，四項是−1、1、1、−1，相加為零；截距和二次項的內積也為零。這檢查的是最優性，不意味着每條殘差必須為零，也不意味着普通未加權RSS等於1。

評分： 矩陣右端2；三個係數3；殘差1；加權最小值1。

配套題本 Q1(b)

(c) [5]

二次型是非負加權多項式值平方和。至少三個正權重時，若二次型為零，次數至多二的多項式在三個互異點為零，只能恆零，係數向量為零，故正定。反之，至多兩個正權重使WM至多兩個非零行，不可能三欄獨立；非零零空間向量令Gram矩陣奇異。零權重不提供識別約束。

$$\begin{gathered} q_v(x)=v_0+v_1x+v_2x^2,\quad v^TM^TW^2Mv=\|WMv\|^2=\sum_iw_i^2q_v(x_i)^2\ge0. \\\#\{i:w_i>0\}\ge3,\ v^TM^TW^2Mv=0\Longrightarrow q_v\equiv0\Longrightarrow v=0. \\m=\#\{i:w_i>0\}\le2\Longrightarrow\operatorname{rank}(WM)\le m<3\Longrightarrow\exists v\ne0:WMv=0. \\M^TW^2Mv=0\quad\Longrightarrow\quad M^TW^2M\text{ is singular}. \end{gathered}$$

為什麼要把矩陣問題變成多項式問題？ 要證明3×3的Gram矩陣可逆，直接算一般權重的行列式很繁瑣。它本來就是一個矩陣轉置乘自身，所以先檢查二次型是否只在零向量取零最自然。向量v的三個分量可以看作另一個二次以下多項式的係數；Mv就是在全部輸入點計算這個多項式的結果。

充分性中的關鍵一步。 平方和為零時，因為每項非負，所以每一個正權重對應的多項式值都必須為零，不能靠正負抵消。互異輸入保證這是三個不同的根；“次數至多二”包括常數、一次及零多項式，只有零多項式能擁有三個不同的根。因此三個係數全零，恰好滿足正定的定義。

必要性不是説方程數量看起來少。 至多兩個非零行使WM的秩至多為2，但它有3列。秩—零度關係保證存在非零v滿足WMv=0，從而Gram矩陣把這個非零v映到零，必然奇異。這裏假設權重非負、輸入互異；重複橫座標即使重複很多次，也不增加不同根的數量。若某最優解存在，沿這樣的零空間方向移動係數不會改變目標，所以係數也不能唯一。

評分： 二次型1；三根充分性2；秩必要性2。

配套題本 Q1(c)

(d) [4]

每折剩n−1個互異正權重點。原有四點時每折剩三個，足夠唯一。原有三點時每折只剩u,v；在一條插值多項式上加任意倍在u,v消失的二次式，兩預測不變而係數不同。更少點亦秩不足。

$$\begin{gathered} n-1\ge3\Longleftrightarrow n\ge4,\qquad n_{\min}=4. \\f_t(x)=f_0(x)+t(x-u)(x-v),\quad t\in\mathbb R,\quad f_t(u)=f_0(u),\quad f_t(v)=f_0(v). \end{gathered}$$

先區分兩個“樣本數”。 全數據擬合有n條記錄，但留一交叉驗證要訓練n個模型，每個模型只能使用n−1條；被留出的響應不能拿回來幫助確定係數。要求的是每一折的係數唯一，而不是最後用全數據擬合時唯一。因此上一問的“三個互異正權重點”必須應用於每個訓練子集。

為什麼三條總記錄不夠？ 兩個保留輸入u、v處可以先用一條直線插值，作為f₀。因為(x−u)(x−v)在這兩點都等於零，加上它的任意倍數不會改變兩個訓練預測，也不會改變訓練損失；但t不同會改變二次項及其他係數。缺少的正是第三個獨立限制。於是n=4既足夠又最小；若輸入重複或某些權重為零，單憑總記錄數4仍不能保證。

評分： 答案1；充分性1；兩點非唯一論證2。

配套題本 Q1(d)

Q2. 正則化、訓練評分與驗證 (14)

配套題本 Q2

(a) [6]

展開求導，二階導正給唯一解。R²評未懲罰RSS，而優化器權衡RSS與截距自身的懲罰。均值預測RSS更小，但總目標更大，所以單獨最小化RSS的OLS基線證明不適用。

$$\begin{gathered} F(a)=4a^2-12a+20,\quad F'(a)=8a-12,\quad F''(a)=8>0,\quad\widehat a=3/2. \\\bar y=3,\quad\mathrm{TSS}=1+1=2,\quad\mathrm{RSS}=(2-3/2)^2+(4-3/2)^2=13/2. \\R^2=1-\frac{13/2}{2}=-9/4,\quad F(3/2)=11<20=F(3),\quad\mathrm{RSS}(3)=2. \end{gathered}$$

先寫清正在優化什麼。 兩個觀測共享常數預測a，所以未懲罰誤差是(2−a)²+(4−a)²；題目額外加上2a²。展開前兩項得到2a²−12a+20，再加懲罰才成為上面的4a²−12a+20。正的二階導説明駐點是唯一全局極小點，而不是最大點或僅僅一個候選值。

為什麼評分負了，優化卻沒錯？ R²的分子只放未懲罰RSS，不把2a²一起放進去。預測都為3/2時，兩條誤差平方分別是1/4與25/4，所以RSS為13/2。TSS始終圍繞觀測均值3計算，不能圍繞3/2計算。RSS比TSS大，R²自然小於零，意思是在這批數據上，單看預測誤差還不如全部預測均值。

但是優化器比較的是另一個量：在3/2處懲罰為9/2，總目標11；在3處懲罰為18，總目標20。縮小截距帶來的懲罰下降超過誤差增加，所以選擇3/2完全符合目標。不要由“在訓練集上評分”就斷言R²非負；還須檢查截距是否受到懲罰。

評分： 最優及極小性2；RSS1；TSS1；R²1；目標區別1。

配套題本 Q2(a)

(b) [4]

取均值截距、零斜率的可行基線，懲罰為零，整個目標等於TSS。全局最優及懲罰非負夾住RSS，再除正TSS。不須滿秩，亦不須聲稱罰回歸殘差與全部設計欄正交。其他非負且零斜率時為零的懲罰同理。

$$\begin{gathered} L(a,b)=\|y-a\mathbf1-Xb\|^2+\lambda\|b\|^2,\quad(a_0,b_0)=(\bar y,0),\quad L(a_0,b_0)=\mathrm{TSS}. \\0\le\mathrm{RSS}(\widehat a,\widehat b)\le L(\widehat a,\widehat b)\le L(a_0,b_0)=\mathrm{TSS}. \\0\le1-\mathrm{RSS}(\widehat a,\widehat b)/\mathrm{TSS}\le1. \end{gathered}$$

這道證明為何不需求出係數？ 我們只需證明最優預測不會比一個特定基準的RSS更差，不需要知道最優參數具體是多少。設X是n×p的特徵矩陣，b是p維斜率向量，a是標量；選b=0後，所有特徵的貢獻都消失，只剩預測常數a。再選a為訓練響應均值，就恰好得到TSS基準。

把不等式鏈逐段讀。 RSS是平方和，所以非負；懲罰係數非負，使RSS不大於“RSS加懲罰”；全局最優解的整個目標不大於任意可行比較點的目標；最後比較點的懲罰是零，所以其目標正好為TSS。這裏最關鍵的是截距不受罰，否則最後這一步會像(a)那樣失效。隨後除以正TSS，先得到RSS/TSS在0和1之間，再用1減去它得到R²的範圍。

若TSS=0，所有響應相同，通常的R²分式分母為零，這個證明不能宣稱其值為0或1。證明也只針對用於優化的訓練數據；另一批測試數據的均值和誤差不同，不在這個比較鏈中。係數是否唯一與這個分數界是不同問題，因此不需要X滿秩。

評分： 比較點1；目標TSS1；不等式鏈1；正TSS及界1。

配套題本 Q2(b)

(c) [4]

第一，均值尺度與PCA方向預先讀取測試特徵，即使沒讀標籤亦洩漏。第二，用測試成績選參數使測試集充當驗證，最好成績有選擇偏差。先隔離最終測試並尊重時間或群組結構；訓練內部每折只用該折訓練子集擬合縮放、PCA、ridge，固定變換用於驗證，再匯總選擇懲罰及維數。鎖定後全開發數據重新擬合整個流程，最後獨立測試一次。先全開發數據PCA再CV仍折內洩漏。

先辨認什麼算“擬合”。 訓練不只是在最後調用ridge。計算均值、標準差、PCA方向也在用數據估計參數；沒有使用標籤，不等於沒有使用測試信息。測試集的目的，是模擬尚未見過的數據，不能讓它參與選擇表示方式。

可以把正確過程按時間順序寫成四步：①先隔離最終測試集，並按需要採用時間或羣組劃分；②在開發數據內部劃分每個訓練折和驗證折；③只在訓練折估計縮放參數、擬合PCA及ridge，用同一套已固定的變換處理驗證折，彙總驗證誤差後選擇懲罰強度與維數；④鎖定選擇，在全部開發數據上重新估計整條流程，然後對最終測試集評價一次。驗證折不能自己重新估計一套均值或PCA，否則座標系也與訓練模型不一致。

兩個錯誤必須分別指出。 即使修正了預處理，反覆看測試成績挑參數仍然會泄漏；即使不調測試成績，提前全數據PCA也仍然泄漏。如果測試集已被用於選參數，它的最好成績不能再被描述為獨立最終測試結果。評分看的是指出信息進入流程的位置，並説明每一折如何重新擬合，不是隻寫一句“使用交叉驗證”。

評分： 預處理洩漏1；測試調參1；折內流程1；重新擬合獨立測試1。

配套題本 Q2(c)

Q3. 負主特徵值與一次補全 (15)

配套題本 Q3

(a) [4]

矩陣相乘得到原向量及長度。最大絕對值特徵值為−3，初值在其方向投影非零。偶數步趨向正第一軸、奇數步趨向負第一軸；有向向量不收斂到一個向量，但直線方向收斂。除以正長度不會使特徵值估計必為正。

$$\begin{gathered} Bv^{(0)}=\frac1{\sqrt2}\binom{-3}{1},\quad\|Bv^{(0)}\|=\sqrt5,\quad v^{(1)}=\frac1{\sqrt{10}}\binom{-3}{1}. \\(v^{(1)})^TBv^{(1)}=-3\frac9{10}+\frac1{10}=-\frac{13}5. \\v^{(t)}=\frac1{\sqrt{9^t+1}}\binom{(-3)^t}{1},\quad\frac{-3\cdot9^t+1}{9^t+1}\longrightarrow-3. \end{gathered}$$

按算法順序，不跳過長度。 B是2×2，迭代向量有兩個分量。先用B乘初始向量，再算所得向量的歐氏長度：其長度平方為(9+1)/2=5，所以除以√5後得到分母√10。新向量的平方長度是(9+1)/10=1，因此Rayleigh商的分母已經是1；不能把這個長度當作帶符號的特徵值。

負號為什麼一直出現？ 連續乘B，會使第一分量每次乘−3，第二分量每次乘1。歸一化只改變整體長度，不改變分量之比，所以可直接寫出第t步表達式。第一分量絕對值相對第二分量越來越大，但符號每步翻轉。冪法所需的是初始向量在絕對值最大特徵方向上的分量非零，本題滿足；若一開始只有第二分量，就不會找到−3。

Rayleigh商使用第一、第二分量的平方作為權重，因此向量統一反號不改變商。第一方向的平方權重趨向1，商便趨向−3。要分別回答“向量是否收斂”“無向直線是否收斂”和“商是否收斂”，不能用其中一個替代其餘兩個。

評分： 歸一化向量1；商1；極限1；符號方向區別1。

配套題本 Q3(a)

(b) [6]

先分解Gram矩陣得奇異值平方；選右向量後用矩陣相乘再除對應奇異值得左向量。原對稱矩陣第二特徵值為負，因此第二左向量須為右向量負號。對稱不代表非負奇異值分解可以U=V；須核對正交及乘積。

$$\begin{gathered} (X^{(0)})^TX^{(0)}=\begin{pmatrix}5&4\\4&5\end{pmatrix},\quad(5-\eta)^2-16=(\eta-9)(\eta-1),\quad\sigma_1=3,\ \sigma_2=1. \\v_1=\frac1{\sqrt2}(1,1)^T,\quad v_2=\frac1{\sqrt2}(1,-1)^T,\quad X^{(0)}v_1=3v_1,\quad X^{(0)}v_2=-v_2. \\u_1=v_1,\quad u_2=-v_2,\quad U=\frac1{\sqrt2}\begin{pmatrix}1&-1\\1&1\end{pmatrix},\quad\Sigma=\begin{pmatrix}3&0\\0&1\end{pmatrix},\quad V=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}. \\U^TU=V^TV=I_2,\qquad U\Sigma V^T=\frac32\begin{pmatrix}1&1\\1&1\end{pmatrix}-\frac12\begin{pmatrix}1&-1\\-1&1\end{pmatrix}=X^{(0)}. \end{gathered}$$

為什麼先算Gram矩陣？ 奇異值按定義非負，而原矩陣的特徵值可能有負號。右奇異向量是轉置乘原矩陣所得Gram矩陣的單位特徵向量，奇異值則是其特徵值的非負平方根。這裏兩個特徵值9與1分別給出3與1，而不是把9、1直接填進Σ。U、Σ、V都是2×2，每一列的先後次序必須與對應奇異值一致。

左向量不能獨立任選。 選定v₁、v₂以後，用原矩陣乘它們，再分別除以3與1，才得到配對的u₁、u₂。第二方向被原矩陣反向，所以負號必須放入第二左向量；若強行取U=V且Σ非負，重構會失去這個負號。可同時把同一對左右向量反號，因為兩個負號在外積中抵消，但只改一邊會改變乘積。

最後把兩個秩一項分別相加：第一項為3/2乘全1矩陣，第二項為−1/2乘交替符號矩陣，因此對角得到1、非對角得到2。正交性檢查每列長度為1且兩列內積為零；乘積檢查確保方向、符號和次序都配對正確。

評分： Gram及譜2；奇異值1；V1；配對U1；驗證1。

配套題本 Q3(b)

(c) [5]

軟閾值後只留值2的一個奇異分量。恢復時左下角改回觀測2，缺失的右上角仍為估計1。低秩估計與滿足觀測的迭代矩陣用途不同；恢復條目不保持秩，亦不必保持對稱。不能因初值對稱就一起改兩處非對角。

$$\begin{gathered} (3-1)_+=2,\quad(1-1)_+=0,\quad Y=U\operatorname{diag}(2,0)V^T=\begin{pmatrix}1&1\\1&1\end{pmatrix}. \\X^{(1)}=\begin{pmatrix}1&1\\2&1\end{pmatrix},\quad\operatorname{rank}(Y)=1,\quad\det X^{(1)}=-1,\quad\operatorname{rank}(X^{(1)})=2. \end{gathered}$$

把兩個操作分開。 軟閾值作用在奇異值上，不是把矩陣每個條目減1；(s−1)₊表示先減1，再與0取最大值。所以3變2，1變0。只剩第一對奇異向量的外積，得到四個條目均為1的Y。它只有一個非零奇異值，秩為1。

接下來才執行“恢復觀測”：檢查觀測位置的掩碼，而不是檢查矩陣是否對稱。左下角是觀測值2，必須寫回2；右上角是缺失值，保留Y給出的估計1；兩個對角觀測本來就是1，不再改變。得到的X⁽¹⁾因此不對稱，其行列式為1−2=−1，所以在2×2情形下滿秩。

這不矛盾：Y承擔低秩收縮估計的角色，X⁽¹⁾承擔下一輪輸入且滿足觀測的角色。恢復硬約束會破壞低秩性質；本問只要求這一次更新，不能把Y誤報為已恢復矩陣，也不能因一次更新滿秩就聲稱算法失敗。

評分： 閾值1；Y1；恢復矩陣1；兩秩1；角色解釋1。

配套題本 Q3(c)

Q4. 經典多維尺度分析 (9)

配套題本 Q4

(a) [5]

中心化坐標的距離平方等於兩個範數平方減兩倍內積。左右乘H時因H1=0消去只依賴行或列的範數項，且HGH=G。計算平方距離行均值及總均值可省兩次矩陣乘法；行和零檢查中心化。先平均再平方是不同操作。

$$\begin{gathered} D_{ij}^2=G_{ii}+G_{jj}-2G_{ij},\quad D^{(2)}=g\mathbf1^T+\mathbf1g^T-2G,\quad H\mathbf1=0,\quad HGH=G. \\HD^{(2)}H=-2G,\quad D^{(2)}=\begin{pmatrix}0&1&9\\1&0&4\\9&4&0\end{pmatrix}. \\(\overline{D^2}_{1\cdot},\overline{D^2}_{2\cdot},\overline{D^2}_{3\cdot})=(10/3,5/3,13/3),\quad\overline{D^2}_{\cdot\cdot}=28/9. \\G_{ij}=-\frac12(D_{ij}^2-\overline{D^2}_{i\cdot}-\overline{D^2}_{\cdot j}+\overline{D^2}_{\cdot\cdot}),\quad G_{11}=16/9,\quad G_{12}=4/9. \\G=\frac19\begin{pmatrix}16&4&-20\\4&1&-5\\-20&-5&25\end{pmatrix},\quad G\mathbf1=0. \end{gathered}$$

雙中心化究竟消掉什麼？ 設Z的每一行是一點的中心化座標，G=ZZᵀ是3×3的內積矩陣，g記錄G的三個對角元，即各點的平方長度。平方距離展開成“第i點長度平方＋第j點長度平方−兩倍內積”。前兩項分別只依賴行或列，所以能寫成含全1向量的兩個外積。

H是3×3的中心化矩陣I−11ᵀ/3。由於H乘全1向量為零，左右乘H就消除了這兩個外積；又因為Z已中心化，HZ=Z，故HGH=G，留下的只有−2G。這説明為什麼要先逐元素平方距離，再做雙中心化，而不是直接中心化距離，也不是計算矩陣乘積D·D。

逐項計算示範。 第一行平方距離0、1、9的平均是10/3；第二行是5/3；第三行是13/3。九個條目總和為28，所以總均值是28/9，不是除以3。算G₁₁時，括號內為0−10/3−10/3+28/9=−32/9，乘−1/2得16/9；算G₁₂時，括號內為1−10/3−5/3+28/9=−8/9，得4/9。其餘條目按同樣規則算，並用對稱性與每行和為零複核。

評分： 距離展開中心化2；平方矩陣1；G2。

配套題本 Q4(a)

(b) [4]

識別秩一外積，唯一正特徵值為向量平方範數，其餘為零。單位特徵向量乘特徵值平方根而非特徵值。坐標和零並重現所有距離；中心化固定平移，但同時反號的鏡像仍可。若不中心化，還可整體平移。

$$\begin{gathered} z=\frac13(-4,-1,5)^T,\quad G=zz^T,\quad\lambda_1=z^Tz=\frac{42}9=\frac{14}3,\quad\lambda_2=\lambda_3=0. \\q_1=\frac1{\sqrt{42}}(-4,-1,5)^T,\quad\sqrt{\lambda_1}q_1=(-4/3,-1/3,5/3)^T=z. \\\sum_i z_i=0,\quad |z_1-z_2|=1,\quad|z_1-z_3|=3,\quad|z_2-z_3|=2,\quad z\longleftrightarrow-z. \end{gathered}$$

如何不用展開三次特徵方程？ 已算出的G各行成比例，可嘗試寫成一個列向量乘其轉置。找到z後，直接計算Gz=z(zᵀz)，説明z是特徵向量，特徵值為它的長度平方。任何與z正交的向量都會被G映成零，因此另外兩個特徵值都是零。三個對象只需一維，是由秩決定，不是由對象數量直接決定。

為何座標要乘平方根？ 單位特徵向量只規定方向與單位長度，若座標取αq₁，其Gram矩陣便是α²q₁q₁ᵀ。為了匹配特徵值λ₁，必須讓α²=λ₁，因此取平方根；直接乘λ₁會把尺度平方錯。最後不只檢查座標和為零，還要逐對求絕對差，得到1、3、2，才真正驗證重建了全部題設距離。

同時反號相當於一維鏡像，所有差的絕對值不變，是同樣正確的解；只反號其中一個點則一般不正確。中心化排除了整體平移自由度，但沒有排除鏡像自由度。

評分： 譜1；向量或外積1；坐標1；鏡像與中心化1。

配套題本 Q4(b)

Q5. 指定協方差歸一化的LDA (9)

配套題本 Q5

(a) [4]

類內協方差須各點減本類均值。第一類只橫向變化，第二類只縱向變化；外積和除指定4，不改n−1或各類樣本分母。類間協方差則類均值減總體均值再平均外積。

$$\begin{gathered} \mu_1=(0,0)^T,\quad\mu_2=(3,2)^T,\quad\mu=(3/2,1)^T. \\S_1=\begin{pmatrix}2&0\\0&0\end{pmatrix},\quad S_2=\begin{pmatrix}0&0\\0&8\end{pmatrix},\quad\Sigma_W=\frac{S_1+S_2}{4}=\begin{pmatrix}1/2&0\\0&2\end{pmatrix}. \\\mu_1-\mu=(-3/2,-1)^T,\quad\mu_2-\mu=(3/2,1)^T,\quad\Sigma_B=\begin{pmatrix}9/4&3/2\\3/2&1\end{pmatrix}. \end{gathered}$$

先決定減哪個均值。 每個觀測是2維列向量，協方差矩陣是2×2。類內變化描述同類點圍繞本類中心的離散，不能先減總體均值，否則類間分離也會混進類內量。第一類偏差是(−1,0)與(1,0)，兩個外積各在左上角貢獻1；第二類偏差是(0,−2)與(0,2)，兩個外積各在右下角貢獻4。因此未歸一化的散佈和分別為2與8。

題面要求把兩類散佈相加後除以全部樣本數4，便得到對角元1/2與2。這是指定定義，不是要自行估計無偏協方差。類間量則以兩個類均值為對象，減總體均值後得兩個互為相反的向量；相反向量的外積相同，取平均仍是同一個矩陣。其非對角元為(3/2)×1=3/2，而不是零。

檢查：兩類樣本數相同，所以總體均值也是兩個類均值的簡單平均；兩種協方差均應對稱且半正定。總體中心化與類內中心化不能互換，分母的修改也不能被當成無關細節，因為下一問的廣義特徵值會受影響。

評分： 均值1；類內中心化協方差2；類間1。

配套題本 Q5(a)

(b) [3]

類內矩陣正定，可用逆協方差加權。兩類等大使類間協方差為均值差外積的四分之一。廣義譜為5與0；最大方向單位化並滿足符號。不能直接用單位均值差，因為第一特徵類內變化較小。漏四分之一不改方向卻使特徵值錯誤擴大四倍。

$$\begin{gathered} d=\mu_2-\mu_1=(3,2)^T,\quad\Sigma_B=dd^T/4,\quad\Sigma_W^{-1}d=(6,1)^T,\quad u=\frac1{\sqrt{37}}(6,1)^T. \\\Sigma_W^{-1}\Sigma_B=\begin{pmatrix}9/2&3\\3/4&1/2\end{pmatrix},\quad\begin{pmatrix}9/2&3\\3/4&1/2\end{pmatrix}\binom61=5\binom61. \\\lambda_{\max}=5,\quad u^T\Sigma_Wu=20/37,\quad u^T\Sigma_Bu=100/37,\quad\frac{u^T\Sigma_Bu}{u^T\Sigma_Wu}=5. \end{gathered}$$

為何方向要乘逆類內協方差？ LDA比較投影后的類間變化與類內變化之比。均值差d只告訴我們兩類中心隔多遠，沒有考慮各方向內部有多“散”。第一座標的類內方差為1/2，第二座標為2；逆協方差分別乘2與1/2，把低類內噪聲方向的權重提高，於是(3,2)變成(6,1)，而不是直接把(3,2)單位化。

正定性保證任意非零方向的分母為正，也保證可以求逆。此處類間矩陣是秩一，所以除最大方向外只剩零特徵值；乘積矩陣的跡為9/2+1/2=5，行列式為0，給出特徵值5與0，證明找到的不只是某個特徵方向，而是最大方向。注意逆矩陣乘類間矩陣不必對稱，不能僅憑外觀就否認它的用途。

將(6,1)除以√37後長度為1，第一分量為正，符合題設符號約定。再分別算分子100/37與分母20/37，其比為5，提供獨立檢查。方向縮放不會改變這個比值，但把類間協方差漏掉1/4會把比值整體放大四倍。

評分： 可逆與方向1；單位化符號1；最大特徵值1。

配套題本 Q5(b)

(c) [2]

逐點與原始觀測取內積，平均應等於總體均值的投影。中心化投影會各減該共同值，雖不改變類間分離，卻不是本問指定坐標。

$$\begin{gathered} (u^Tx_1,u^Tx_2,u^Tx_3,u^Tx_4)=\frac1{\sqrt{37}}(-6,6,18,22),\quad\frac14\sum_i u^Tx_i=\frac{10}{\sqrt{37}}=u^T\mu. \end{gathered}$$

把投影看成一個具體算式。 uᵀx是標量：將原始點第一座標乘6，第二座標乘1，再把總和除以√37。四個原始點依次為(−1,0)、(1,0)、(3,0)、(3,4)，故分子依次為−6、6、18、22。這裏不再另減均值，也不把投影結果再單位化。

利用線性性，先投影再平均應等於先平均再投影，所以四個分子的平均為10，正好與6×(3/2)+1=10一致。若誤用中心化數據，分子會全部減10，變成−16、−4、8、12；這能保留相對距離，卻不是本問所要的原始投影。這個核驗能發現“答案看起來分得開，但整體位置錯了”的情況。

評分： 每個投影0.5。

配套題本 Q5(c)

Q6. 層次聚類：連結定義的重要性 (15)

配套題本 Q6

(a) [4]

先列六個原始距離。單連結取跨簇最小距離。合併A、B後重算到C、D距離；B到C較短，使C下一步加入；最後D按到C距離加入。鏈式吸收不要求C靠近簇內每一點，本例無影響選擇的平局。

$$\begin{gathered} \begin{array}{c|rrrrrr}\text{pair}&AB&AC&AD&BC&BD&CD\\d&2&5&17/2&3&13/2&7/2\end{array} \\d_{\rm single}(AB,C)=\min(5,3)=3,\quad d_{\rm single}(AB,D)=\min(17/2,13/2)=13/2,\quad d(C,D)=7/2. \\d_{\rm single}(ABC,D)=\min(17/2,13/2,7/2)=7/2. \\ A+B\text{ at }2;\qquad AB+C\text{ at }3;\qquad ABC+D\text{ at }7/2. \end{gathered}$$

從點距離到簇距離。 點在實數軸上，所以用座標差的絕對值，不用平方距離。開始每點獨立成簇，六個點對中2最小，所以第一步沒有爭議。合併A、B之後，算法的對象已經變成三個簇，不能繼續從舊點對錶中機械取下一個尚未用過的數。

單鏈接的規則是每兩個當前簇之間取最短跨簇距離。因此AB到C要比較AC與BC，取3；AB到D比較AD與BD，取13/2；C到D仍為7/2。再比較這三個候選距離，3最小，才得到ABC。最後比較A、B、C各自到D的距離，最小者來自C，給7/2。

合併高度記錄當時兩個簇的鏈接距離，不是新簇的直徑。例如ABC的直徑是5，但它在高度3形成。樹狀圖應先在2連接A、B，再在3接C，最後在7/2接D；三個高度遞增，且最終只剩一個簇，可作為流程核驗。

評分： 初始與首合併1；更新與第二步2；最終1。

配套題本 Q6(a)

(b) [7]

單點間定義相同，所以首步仍A、B。此後平均所有跨簇點對，不再選最近點對。C、D距離小於AB到C平均，故第二步合併C、D。最後兩兩大小為2的簇共有四點對，全部平均；樹形和高度都與單連結不同，不能改成質心距離。

$$\begin{gathered} d_{\rm av}(AB,C)=\frac{5+3}{2}=4,\quad d_{\rm av}(AB,D)=\frac{17/2+13/2}{2}=15/2,\quad d(C,D)=7/2<4. \\d_{\rm av}(AB,CD)=\frac{d(A,C)+d(A,D)+d(B,C)+d(B,D)}{4} \\=\frac{5+17/2+3+13/2}{4}=23/4. \\ A+B\text{ at }2;\qquad C+D\text{ at }7/2;\qquad AB+CD\text{ at }23/4. \end{gathered}$$

相同的第一步不代表後面相同。 單點簇之間只有一個跨簇點對，所以取最小值與取平均都給原點距離。出現AB這個二點簇後，AB到C有兩個點對，平均為4；AB到D也有兩個，平均為15/2。此時C到D的7/2比4更小，所以不能沿用上一問的AB吸收C，而要先形成CD。

最後比較AB與CD，跨簇配對是AC、AD、BC、BD，恰好2×2=4個。AB和CD自身內部的距離不屬於跨簇和，不可放入分子；分母也不是“兩個簇所以除以2”。四個距離總和為23，再除4得到23/4。它位於這四個距離的最小值3與最大值17/2之間，滿足平均值的基本範圍。

樹形也要説明。 單鏈接在第二步產生一個三點簇；平均鏈接在第二步產生兩個二點簇，最後才合併兩邊。平均鏈接的定義是平均全部跨簇點對距離，不能一般地用質心距離替代，即使某些一維分離情形下數值碰巧相同。

評分： 首步1；三個距離3；第二步1；四對平均及高度2。

配套題本 Q6(b)

(c) [4]

把雙和拆成S、T兩組，每個舊均值先乘對應點對數再合併；共同|U|約去。簇大小相等才對任意舊距離保證簡單平均；大小不等時若舊距離恰等亦偶然正確，但不是通則。數值反例顯示差別。

$$\begin{gathered} d_{\rm av}(S\cup T,U)=\frac{\sum_{s\in S,u\in U}d(s,u)+\sum_{t\in T,u\in U}d(t,u)}{(|S|+|T|)|U|} \\=\frac{|S||U|d_{\rm av}(S,U)+|T||U|d_{\rm av}(T,U)}{(|S|+|T|)|U|} \\=\frac{|S|d_{\rm av}(S,U)+|T|d_{\rm av}(T,U)}{|S|+|T|}. \\|S|=|T|\Longrightarrow d_{\rm av}(S\cup T,U)=\tfrac12[d_{\rm av}(S,U)+d_{\rm av}(T,U)]. \\|S|=2,\ |T|=1,\ d_{\rm av}(S,U)=4,\ d_{\rm av}(T,U)=10:\quad\frac{2(4)+10}{3}=6\ne7=\frac{4+10}{2}. \end{gathered}$$

為什麼必須用簇大小作權重？ 舊距離dₐᵥ(S,U)本身已經是平均數，不是總距離。要把它與另一個平均數合併，先恢復各自的總量：S與U有|S||U|個點對，所以乘這個數量；T與U則乘|T||U|。兩份總量相加後，再除新的總點對數(|S|+|T|)|U|。共同的|U|約掉，才得到按|S|與|T|加權的更新式。

這裏S、T是互不相交的非空舊簇，U也是另一非空簇，所以分母不為零且拆和不重複計數。簡單平均給兩個舊簇相同權重，而真正定義給每個跨簇點對相同權重；大簇提供更多點對，理應貢獻更大。

例如兩份舊平均分別4和10，第一份對應兩倍數量的點對，所以合併平均更接近4，得到6，不是中點7。只有簇大小相等才能對任意兩份舊距離保證簡單平均正確；兩份舊距離本身相同也會碰巧正確，但這不是忽略大小的普遍依據。

評分： 拆和1；點對數1；公式1；保證與偶然區別1。

配套題本 Q6(c)

Q7. DBSCAN：共享邊界點不是核心橋 (18)

配套題本 Q7

(a) [6]

先列閉鄰域，再按至少四點判核心。E僅三鄰居，不是核心，但鄰近核心D、F，所以是邊界不是噪聲。J既非核心亦不在任何核心半徑1內，故噪聲。漏自身會改變題設約定。

$$\begin{gathered} \begin{array}{c|l|r}p&N_1(p)&|N_1(p)|\\A&\{A,B,C,D\}&4\\B&\{A,B,C,D\}&4\\C&\{A,B,C,D\}&4\\D&\{A,B,C,D,E\}&5\\E&\{D,E,F\}&3\\F&\{E,F,G,H,I\}&5\\G&\{F,G,H,I\}&4\\H&\{F,G,H,I\}&4\\I&\{F,G,H,I\}&4\\J&\{J\}&1\end{array} \\\text{core}=\{A,B,C,D,F,G,H,I\},\quad\text{border}=\{E\},\quad\text{noise}=\{J\}. \end{gathered}$$

先固定三個容易混淆的定義。 鄰域由距離不超過1的點構成，包括自身，也包括距離恰好為1的點；核心點要求鄰域數量至少4，不是“除了自身再找4個”；非核心點若鄰近某個核心點就是邊界點，否則才是噪聲。分類應先確定所有核心點，再判斷剩餘點，不能把所有不足4的點立即標成噪聲。

例如D座標為−0.9，到A、B、C的距離分別為0.9、0.8、0.7，到自身為0，到E為0.9，故共5個；到F已經是1.8，不在鄰域。E位於0，只有自身及兩邊0.9處的D、F共3個，不足核心門檻，但D和F都是核心，所以E是共享邊界點。J到最近的I仍為2.2，大於1，只有自身且不鄰近任何核心點，所以是噪聲。

表中的A、B、C與G、H、I各有四個鄰域點，恰好達門檻，不能把“至少4”誤讀為“超過4”。逐點列鄰域比憑圖形覺得某點密集更可靠；評分需要數量與分類都正確。

評分： 全部數量3；八核心、E邊界、J噪聲3。

配套題本 Q7(a)

(b) [4]

從A開始，左核心分量擴張到D並納入E；E非核心，不能繼續到F。處理F時形成右簇，E保留首次歸屬。若先處理右邊，E可能改歸右，但兩核心分量不會因此合併；區分邊界歸屬依賴次序與核心連通結構。

$$\begin{gathered} C^{(1)}=\{A,B,C,D,E\},\quad C^{(2)}=\{F,G,H,I\},\quad\text{noise}=\{J\}. \end{gathered}$$

按訪問順序模擬，而不是把所有相鄰點直接連通。 先處理A，因為A是核心，它的鄰域進入第一簇；B、C、D也都是核心，可繼續貢獻它們的鄰域。D把E帶入第一簇，但處理E時發現它只有三個鄰居，於是停止從E繼續傳播。E可以成為隊列中被訪問的點，卻不因此取得核心點的擴張權限。

再走到尚未屬於已有簇的F，它是核心，啓動第二簇並吸收G、H、I。雖然F也看得到E，但本題“第一次歸屬保留”規則使E仍留在第一簇。J沒有任何核心鄰居，最後仍是噪聲。最終兩個簇的大小為5與4，加上1個噪聲，正好覆蓋全部10個點且不重複分配。

若反向訪問，E可能屬於右簇，但左側四個核心與右側四個核心仍是兩個獨立核心分量。這裏順序影響的是共享邊界點的標籤，不是允許借E把兩簇合並。

評分： 左核心1；右核心1；E歸左1；J噪聲1。

配套題本 Q7(b)

(c) [4]

不等價。D、F核心，所以D–E與E–F均為合法圖邊，路徑把兩密集分量接通，雖內部E非核心。無向傳遞連通忽略該區別。標準擴張可從D到E，卻不能由E再發起到F。忠實表示應先只連核心點求核心分量，再按次序附加邊界；邊界不負責合併。

$$\begin{gathered} |D-E|=0.9\le1,\quad|E-F|=0.9\le1,\quad D\longleftrightarrow E\longleftrightarrow F. \\\operatorname{component}_{\rm graph}(D)=\{A,B,C,D,E,F,G,H,I\}\ne C^{(1)}. \end{gathered}$$

先確認反例確實符合研究者規則。 這條圖規則只要求邊的兩個端點中至少一個是核心。D–E邊有核心端點D，E–F邊有核心端點F，兩條長度又都不超過1，所以兩條都是合法無向邊。雖然E本身不是核心，無向圖連通性依然允許先走D到E，再走E到F，從而把兩邊的核心區域合為一個連通分量。

標準DBSCAN的條件卻附着在“誰發起下一步擴張”上：從核心D可以把E納入，但E不是核心，不能再從E走到F。把這種有條件傳播替換成無向路徑傳遞，就丟掉了關鍵限制；不是因為兩條邊距離算錯，而是圖模型表達的關係與算法不同。

因此僅寫“不等價”不夠，要展示兩條合法邊和合並後的九點分量，並指出E是阻止標準擴張繼續的非核心內部點。忠實的構造是先在核心點子圖求分量，再按題定順序把相鄰邊界點附加進去；不能讓邊界點充當合併分量的橋。

評分： 不等價1；兩圖邊1；合併分量1；非核心不擴張1。

配套題本 Q7(c)

(d) [4]

排序距離含起始零；第四第五並列不改變至少包含四點的最小半徑。E須更寬鄰域才有足夠密度，將普通長度0.9提高至權重1.6，使稀疏連接在密度層次較晚發生。這只是HDBSCAN構造的一部分，不等於完成最終選簇。

$$\begin{gathered} D:\ 0,0.7,0.8,0.9,0.9,\ldots\quad\Longrightarrow\quad\operatorname{core}_4(D)=0.9. \\E:\ 0,0.9,0.9,1.6,1.6,\ldots\quad\Longrightarrow\quad\operatorname{core}_4(E)=1.6. \\d_{\rm mr}(D,E)=\max\{0.9,1.6,0.9\}=1.6. \end{gathered}$$

核心距離和是否核心是兩個相關但不同的問題。 在固定半徑1下，E不是核心；它仍然有一個“要把半徑擴大到多少才納入至少4點”的核心距離。排序時含自身的零距離，所以找第4項，而不是跳過零以後再找第4項。D的前三項來自自身、C、B，第四項來自A或E，所以核心距離0.9；E的前三項來自自身、D、F，第四項來自C或G，所以為1.6。

第四、第五項並列，只表示在該半徑同時納入兩個點，不需要挑一個打破平局。定義是至少4點的最小半徑，不要求恰好4點。互可達距離取三者最大值：兩個端點各自的核心距離，以及兩點原始距離，所以必須同時尊重兩端的密度尺度，最後由E的1.6主導。

原始邊D–E只有0.9，看似很近；升到1.6表示這條邊受到稀疏端點的限制。在按距離閾值逐漸增大而連接的層次中，它要等到更大的閾值才出現。這裏只算一條互可達邊，尚未計算完整最小生成樹、凝聚層次或穩定性選簇，不能據此報出最終HDBSCAN聚類。

評分： 各核心距離1；互可達1；密度與升權解釋1。

配套題本 Q7(d)