112 年 國立成功大學數據科學研究所《計算機概論（含資料結構）》

核心觀念

本題綜合考查：

• 決策樹的 pruning 與 bias–variance trade-off
• DFS、BFS、最小生成樹與圖論複雜度
• 分類、迴歸與 Logistic Regression
• $k$-NN 的訓練誤差
• 神經網路反向傳播
• Dijkstra 演算法的適用條件
• Hash、Heap、正則化與遞迴

判斷是非題時，應先辨認敘述中的「永遠」「不能」「全球最優」等強烈字眼，再對照定義與適用條件。

---

選項分析

(a) Pruning a decision tree will remove some branches. Pruning a decision tree will decrease model bias.

判斷：False

決策樹 pruning 會移除部分子樹或分支，使模型變得更簡單，因此「移除部分分支」是正確的。

然而，模型複雜度降低通常會造成：

• 偏差（bias）上升
• 變異（variance）下降

Pruning 的主要目的在於降低過度配適，而不是降低 bias。因此後半句錯誤。

正確說法是：Pruning 通常會增加模型 bias、降低模型 variance。

---

(b) Pruning a decision tree will decrease model variance.

判斷：True

未修剪的決策樹通常非常複雜，容易受到訓練資料中的雜訊影響。不同訓練資料可能產生差異很大的樹，代表模型 variance 高。

Pruning 移除不重要的分支，降低模型複雜度，使模型對訓練資料的微小變動不那麼敏感，因此通常會降低 variance。

這是典型的 bias–variance trade-off：

$$\text{Pruning} \Rightarrow \text{bias 上升，variance 下降}$$

---

(c) For a graph $G$ and a node $v$ in that graph, the DFS and BFS trees of $G$ rooted at $v$ always contain the same number of edges.

判斷：True

以 $v$ 為起點執行 DFS 或 BFS 時，兩者都會拜訪從 $v$ 可達的所有頂點。設可達頂點數為 $|R|$，則每個 traversal tree 都是該連通區域的 spanning tree，因此邊數皆為：

$$|R|-1$$

DFS 與 BFS 產生的樹形狀可能不同，但邊數相同。

若整張圖不連通，兩種演算法都只涵蓋 $v$ 所在的連通分量，結論仍成立。

---

(d) Prim's algorithm is a greedy algorithm but Kruskal's algorithm is not.

判斷：False

Prim 與 Kruskal 都是求最小生成樹（Minimum Spanning Tree, MST）的 greedy algorithm。

• Prim：每次選擇連接目前樹與樹外頂點的最小權重邊。
• Kruskal：每次選擇目前尚未形成 cycle 的最小權重邊。

Kruskal 通常使用 Disjoint Set Union（Union-Find）判斷加入邊後是否會形成 cycle，但這不影響其 greedy 性質。

因此正確說法是：Prim 與 Kruskal 都是 greedy algorithms。

---

(e) We cannot determine if an undirected graph $G=(V,E)$ has a cycle in $O(|V|+|E|)$ time.

判斷：False

無向圖可以利用 DFS 或 BFS 判斷是否含有 cycle，時間複雜度為：

$$O(|V|+|E|)$$

以 DFS 為例，若探索到一條連接至「已拜訪頂點」的邊，且該頂點不是目前頂點的 parent，便表示存在 cycle。

因此敘述錯誤。正確說法是：可以在 $O(|V|+|E|)$ 時間內判斷無向圖是否有 cycle。

---

(f) Since classification is a special case of regression, logistic regression is a special case of linear regression.

判斷：False

Logistic Regression 雖然名稱含有 regression，但它主要用於分類。其模型先計算線性組合：

$$z=\mathbf{w}^{T}\mathbf{x}+b$$

再套用 sigmoid function：

$$P(y=1\mid \mathbf{x}) = \sigma(z) = \frac{1}{1+e^{-z}}$$

輸出是機率，通常再依門檻值分類。

Linear Regression 直接預測連續數值：

$$\hat{y}=\mathbf{w}^{T}\mathbf{x}+b$$

兩者的輸出型態、損失函數與機率模型不同。Logistic Regression 可說是具有線性決策邊界的分類模型，但不是 Linear Regression 的特殊情況。

---

(g) The training error of $k$-Nearest Neighbor classifier with $k=1$ cannot be 0.

判斷：False

對訓練資料中的某一筆樣本 $\mathbf{x}_i$ 使用 $1$-NN 分類時，該樣本本身距離自己為 $0$，通常會被視為最近鄰，因此預測標籤就是自己的標籤。

所以在沒有特殊重複樣本處理問題的標準設定下：

$$\text{Training error}_{1\text{-NN}}=0$$

題目說「cannot be 0」錯誤。$1$-NN 的訓練誤差通常為 $0$，但測試誤差不一定低，因為模型可能過度配適。

---

(h) The back-propagation algorithm learns a globally optimal neural network with hidden layers.

判斷：False

Back-propagation 是利用鏈鎖律計算損失函數對各參數的梯度，再配合 Gradient Descent 更新權重：

$$\theta \leftarrow \theta-\eta\nabla_{\theta}L$$

含有 hidden layers 的神經網路通常具有非凸（non-convex）損失函數，因此訓練過程可能收斂至：

• local minimum
• saddle point
• 依初始化與最佳化方法而定的不同解

Back-propagation 並不保證找到全域最優解。

---

核心觀念

本題利用鄰接矩陣的乘冪計算圖中兩個頂點之間的路徑數。

設圖共有 $n$ 個頂點，鄰接矩陣為 $A$：

$$A_{uv}= \begin{cases} 1, & \text{頂點 }u\text{ 與 }v\text{ 相鄰}\\ 0, & \text{否則} \end{cases}$$

對無權圖而言，矩陣乘法的基本性質為：

$$(A^k)_{ij} = \text{從頂點 }i\text{ 到頂點 }j\text{、長度恰為 }k\text{ 的 walk 數量}$$

此處的 walk 允許重複經過頂點或邊。考試題目將此類長度為 $k$ 的走法稱為 paths，以下依此定義作答。

---

解題方法：動態規劃

令

$$dp[t][v] = \text{從頂點 }i\text{ 出發，走 }t\text{ 條邊到達頂點 }v\text{ 的方法數}$$

初始狀態為：

$$dp[0][i]=1$$

因為長度為 $0$ 時，從 $i$ 到 $i$ 有唯一一種空走法；對所有 $v\neq i$：

$$dp[0][v]=0$$

每增加一條邊，依據鄰接矩陣進行轉移：

$$dp[t][v] = \sum_{u=1}^{n} dp[t-1][u]A_{uv}$$

其中只有在 $u$ 與 $v$ 相鄰時，$A_{uv}=1$，因此可將所有長度為 $t-1$ 到達 $u$ 的走法延伸至 $v$。

經過 $k$ 次轉移後，答案為：

$$dp[k][j]$$

關鍵程式碼

CountPaths(A, n, i, j, k):
    dp[1..n] = 0
    dp[i] = 1

    for t = 1 to k:
        next[1..n] = 0

        for u = 1 to n:
            for v = 1 to n:
                if A[u][v] == 1:
                    next[v] = next[v] + dp[u]

        dp = next

    return dp[j]

若題目採用 $0$ 起始編號，頂點編號須相應調整。

---

正確性說明

以數學歸納法說明。

當 $t=0$ 時，只有從 $i$ 到 $i$ 的長度 $0$ 走法，因此：

$$dp[0][i]=1$$

且其他頂點的數值皆為 $0$，初始條件正確。

假設 $dp[t-1][u]$ 已正確表示從 $i$ 到 $u$ 的長度 $t-1$ 走法數。對任一頂點 $v$，每一條長度 $t$ 的走法必定能唯一拆成：

1. 從 $i$ 到某個頂點 $u$ 的長度 $t-1$ 走法；
2. 再從 $u$ 經過一條邊到 $v$。

因此，所有可行走法數量為：

$$\sum_{u=1}^{n}dp[t-1][u]A_{uv}$$

核心觀念

本題考查常見函數的漸近成長速度，主要使用：

1. 對數恆等式：
   $\log(x^2)=2\log x$

2. Stirling 公式：
   $\log(n!)=\Theta(n\log n)$

3. 階乘函數的成長速度遠快於多項式、對數函數。

不同對數底數只會造成常數倍差異，不影響時間複雜度排序。

解題方法

逐一化簡四個函數。

$F_1(x)=\log x^2$

由對數公式：

$$F_1(x)=\log(x^2)=2\log x$$

因此：

$$F_1(x)=\Theta(\log x)$$

---

$F_2(x)=(\log x)!$

令：

$$n=\log x$$

利用階乘的 Stirling 公式：

$$\log(n!)=\Theta(n\log n)$$

但本題函數本身是 $(\log x)!$，不是其對數，因此可直接使用 Stirling 近似：

$$(\log x)! \approx \sqrt{2\pi\log x} \left(\frac{\log x}{e}\right)^{\log x}$$

其成長速度遠大於 $\log x$，但遠小於 $x$。在比較時，可將其視為：

$$F_2(x)=x^{\Theta(\log\log x)}$$

更精確地說，若對數底數固定，則：

$$(\log x)! = \exp\bigl(\Theta(\log x\log\log x)\bigr)$$

---

$F_3(x)=(x+1)!$

這是以 $x$ 為階數的階乘函數。由 Stirling 公式：

$$(x+1)! \approx \sqrt{2\pi(x+1)} \left(\frac{x+1}{e}\right)^{x+1}$$

因此其成長速度遠快於其他三個函數：

$$F_3(x)=\exp(\Theta(x\log x))$$

---

這題考驗對二元樹的三種標準遍歷方式（前序、中序、後序）的理解和實作。

圖示的二元樹結構:
從圖片中解析出二元樹的結構。這棵樹不是一個嚴格意義上的二元搜尋樹 (BST)，它是一個一般的樹結構，但我們可以套用二元樹的遍歷規則。
根節點是 9。
9 的左子節點是 5，右子節點是 20。
5 的左子節點是 3，右子節點是 8。
3 的左子節點是 1，右子節點是 4。
8 的左子節點是 6，右子節點是 10。
20 的左子節點是 12，右子節點是 30。
10 的左子節點是 11。
12 的左子節點是 21，右子節點是 31。
11, 1, 4, 6, 21, 31, 30 是葉節點。

遍歷規則:

• 前序遍歷 (Preorder Traversal): 訪問根節點 -> 遍歷左子樹 -> 遍歷右子樹。
• 中序遍歷 (Inorder Traversal): 遍歷左子樹 -> 訪問根節點 -> 遍歷右子樹。
• 後序遍歷 (Postorder Traversal): 遍歷左子樹 -> 遍歷右子樹 -> 訪問根節點。

遍歷過程:

1. 前序遍歷 (Preorder: Root, Left, Right)
從根節點 9 開始：

• 訪問 9。
• 遍歷左子樹 (根節點 5)：
  • 訪問 5。
  • 遍歷左子樹 (根節點 3)：
    • 訪問 3。
    • 遍歷左子樹 (根節點 1)：
      • 訪問 1。
      • 1 沒有左子樹。
      • 1 沒有右子樹。
    • 遍歷右子樹 (根節點 4)：
      • 訪問 4。
      • 4 沒有左子樹。
      • 4 沒有右子樹。
  • 遍歷右子樹 (根節點 8)：
    • 訪問 8。
    • 遍歷左子樹 (根節點 6)：
      • 訪問 6。
      • 6 沒有左子樹。
      • 6 沒有右子樹。
    • 遍歷右子樹 (根節點 10)：
      • 訪問 10。
      • 遍歷左子樹 (根節點 11)：
        • 訪問 11。
        • 11 沒有左子樹。
        • 11 沒有右子樹。
      • 10 沒有右子樹。
• 遍歷右子樹 (根節點 20)：
  • 訪問 20。
  • 遍歷左子樹 (根節點 12)：
    • 訪問 12。
    • 遍歷左子樹 (根節點 21)：
      • 訪問 21。
      • 21 沒有左子樹。
      • 21 沒有右子樹。
    • 遍歷右子樹 (根節點 31)：
      • 訪問 31。
      • 31 沒有左子樹。
      • 31 沒有右子樹。
  • 遍歷右子樹 (根節點 30)：
    • 訪問 30。
    • 30 沒有左子樹。
    • 30 沒有右子樹。

前序遍歷結果: 9, 5, 3, 1, 4, 8, 6, 10, 11, 20, 12, 21, 31, 30

2. 中序遍歷 (Inorder: Left, Root, Right)
從根節點 9 開始：

• 遍歷左子樹 (根節點 5)：
  • 遍歷左子樹 (根節點 3)：
    • 遍歷左子樹 (根節點 1)：
      • 遍歷左子樹 (無)。
      • 訪問 1。
      • 遍歷右子樹 (無)。
    • 訪問 3。
    • 遍歷右子樹 (根節點 4)：
      • 遍歷左子樹 (無)。
      • 訪問 4。
      • 遍歷右子樹 (無)。
  • 訪問 5。
  • 遍歷右子樹 (根節點 8)：
    • 遍歷左子樹 (根節點 6)：
      • 遍歷左子樹 (無)。
      • 訪問 6。
      • 遍歷右子樹 (無)。
    • 訪問 8。
    • 遍歷右子樹 (根節點 10)：
      • 遍歷左子樹 (根節點 11)：

程式流程

• num1="111"、num2="99"，長度分別 m=3、n=2。
• 外層 i 從右至左遍歷 num1 的每一位 a，內層 j 從右至左遍歷 num2 的每一位 b。
• 每對位元貢獻值 a·b·10^{i+j} 加至 ans。

計算

$i$	$a$	$j$	$b$	$a·b·10^{i+j}$
0	1	0	9	$1·9·10^{0}=9$

核心觀念

本題考查作業系統的三個基本概念：

1. Context switching（內容切換）：處理器由一個執行中的 process 或 thread 切換至另一個。
2. I/O-bound 與 CPU-bound 程式：依程式主要消耗 I/O 時間或 CPU 計算時間分類。
3. Internal fragmentation 與 external fragmentation：記憶體配置後產生的空間浪費問題。

本題為非選擇題，沒有選項需要逐一判斷。

---

(a) Context switching

定義

**Context switch（內容切換）**是指作業系統暫停目前正在執行的 process，保存其執行狀態，再載入另一個 process 的執行狀態，使 CPU 改為執行另一個 process。

Process 的 context 通常包含：

• Program Counter（PC）：下一個要執行的指令位置
• CPU registers：一般暫存器、Stack Pointer 等
• Processor status word：旗標、處理器狀態
• 記憶體管理資訊：例如 page table 或 address space 資訊
• 核心堆疊與排程相關狀態

這些資訊通常保存在該 process 的 PCB（Process Control Block） 中。

作業系統處理流程

當發生下列事件時，作業系統可能進行 context switch：

• 時間片用完，產生 timer interrupt
• 執行中的 process 等待 I/O
• 發生 system call
• process 被較高優先權的 process 搶占
• process 結束執行

典型流程如下：

1. 進入核心模式
   透過 interrupt、exception 或 system call 進入作業系統核心。

2. 保存目前 process 的 context
   作業系統將目前 CPU 中的 PC、暫存器、堆疊指標與處理器狀態等資料寫入目前 process 的 PCB。

3. 更新 process 狀態
   依事件將 process 標記為：

   • Ready：可執行但等待 CPU
   • Waiting／Blocked：等待 I/O 或其他事件
   • Terminated：已結束

4. 執行排程器
   Scheduler 從 ready queue 中依排程演算法選出下一個要執行的 process，例如 Round Robin、Priority Scheduling 或 Multilevel Feedback Queue。

5. 載入下一個 process 的 context
   將新 process 的 PCB 內容載入 CPU 暫存器、PC、Stack Pointer 等位置，必要時切換記憶體位址空間。

6. 恢復執行
   Dispatcher 將 CPU 控制權交給新 process，從其儲存的 PC 繼續執行。

Context switch 本身不執行使用者程式的有效工作，因此會產生額外成本，包括保存與恢復暫存器、切換位址空間，以及可能造成 CPU cache、TLB 等快取失效。這段時間稱為 context-switch overhead。

---

(b) I/O-bound 與 CPU-bound 程式

I/O-bound 程式

I/O-bound 程式主要時間花在輸入／輸出操作，例如：

• 讀取磁碟或資料庫
• 等待網路封包
• 等待鍵盤或其他裝置
• 大量檔案存取

其執行特徵通常是：

$$\text{短時間 CPU 計算} \rightarrow \text{等待 I/O} \rightarrow \text{短時間 CPU 計算}$$

因此，I/O-bound process 常在 CPU burst 結束後進入 waiting state，等待 I/O 完成。

CPU-bound 程式

CPU-bound 程式主要時間花在處理器計算，例如：

• 矩陣運算
• 科學計算
• 影像或影片編碼
• 大量排序與模擬
• 密碼分析

其特徵是 CPU burst 較長，通常較少因 I/O 而阻塞：

$$\text{長時間 CPU 計算} \rightarrow \text{偶爾 I/O 或結束}$$

兩者比較

比較項目	I/O-bound	CPU-bound
主要瓶頸	I/O 裝置或外部事件	CPU 計算能力
CPU burst	短且頻繁	長且持續
常見狀態	頻繁進入 waiting state	長時間處於 running state
適合的排程考量	優先回應，降低等待時間	提高 CPU 使用率與吞吐量
常見程式	文字編輯器、檔案伺服器	科學運算、影片編碼

排程上的意義

核心觀念

本題綜合考查資料科學中的四個核心主題：

1. 監督式學習與過度擬合
2. 正則化（regularization）
3. 深度學習相對於傳統機器學習的優勢
4. Bagging 與 Boosting 集成學習法

過度擬合是指模型過度記憶訓練資料，連同雜訊也納入模型，因此訓練誤差很低，但對未見過的測試資料預測能力變差。常見處理方式包括降低模型複雜度、正則化、交叉驗證、提早停止與增加訓練資料。

---

解題方法與參考答案

(a) 兩種監督式學習方法及避免過度擬合的策略

方法一：決策樹（Decision Tree）

決策樹透過一連串特徵判斷將資料切分成不同區域，分類時常使用資訊增益或基尼不純度作為分裂依據。

若決策樹不斷分裂，直到每個葉節點只剩少量資料，模型便容易記住訓練資料中的偶然特徵，造成過度擬合。

避免方式：

• 限制最大樹深度 max_depth
• 限制葉節點最少樣本數 min_samples_leaf
• 限制分裂節點最少樣本數
• 使用剪枝（pruning）

剪枝可分為：

1. 預剪枝：在建樹過程中限制深度、分裂條件或葉節點大小。
2. 後剪枝：先建立較大的樹，再刪除對驗證資料幫助不大的分支。

例如，若訓練誤差隨樹深度增加而持續下降，但驗證誤差在某一深度後開始上升，應選擇驗證誤差最低的樹深度。

---

方法二：邏輯斯迴歸（Logistic Regression）

邏輯斯迴歸用於二元分類，先計算線性組合：

$$z=w^Tx+b$$

再透過 sigmoid 函數轉換成屬於正類別的機率：

$$P(y=1\mid x)=\sigma(z)=\frac{1}{1+e^{-z}}$$

一般損失函數為交叉熵：

$$L(w,b) = -\frac{1}{n}\sum_{i=1}^{n} \left[ y_i\log \hat y_i+ (1-y_i)\log(1-\hat y_i) \right]$$

雖然邏輯斯迴歸本身是相對簡單的模型，但當特徵數很多、特徵彼此高度相關，或加入大量多項式特徵時，仍可能過度擬合。

避免方式是加入正則化，例如 L2 正則化：

$$J(w,b)=L(w,b)+\lambda\sum_{j=1}^{d}w_j^2$$

其中 $\lambda$ 控制正則化強度。$\lambda$ 越大，模型越傾向使用較小的權重，決策邊界通常較平滑，過度依賴單一特徵的情形也會降低。$\lambda$ 應透過驗證集或交叉驗證選擇。

---

(b) 正則化的定義、作用與例子

正則化的定義

正則化是在原本的訓練損失函數中加入一個懲罰項，限制模型的複雜度：

$$J(\theta)=L(\theta)+\lambda\Omega(\theta)$$

其中：

• $L(\theta)$：模型在訓練資料上的損失
• $\Omega(\theta)$：複雜度懲罰項
• $\lambda$：正則化強度
• $\theta$：模型參數

常見種類如下：

L2 正則化

$$\Omega(w)=\sum_j w_j^2$$

完整目標函數為：

$$J(w)=L(w)+\lambda\sum_j w_j^2$$

L2 會使權重變小，但通常不會直接變成零，因此適合保留多數特徵的情況。

L1 正則化

$$\Omega(w)=\sum_j |w_j|$$

L1 正則化容易使部分權重變成零，因此具有特徵選擇效果。

---

為何正則化能避免過度擬合

假設資料有兩個真正重要的特徵 $x_1,x_2$，另有一個含有大量雜訊的特徵 $x_3$。若不使用正則化，模型可能為了降低訓練誤差，給予 $x_3$ 一個很大的權重：

$$\hat y=w_1x_1+w_2x_2+100x_3+b$$

由於 $x_3$ 主要是雜訊，模型在訓練資料上看似表現良好，但遇到新的資料時，$x_3$ 的雜訊模式不會重現，導致預測失準。

加入 L2 正則化後，目標函數會額外懲罰過大的權重：

$$J(w)=L(w)+\lambda \left(w_1^2+w_2^2+100^2\right)$$

模型若要保留 $w_3=100$，便會付出很大的懲罰，因此最佳化過程會傾向降低 $w_3$。模型不再過度依賴雜訊特徵，測試資料上的泛化能力因而提升。

正則化的本質是讓模型在「訓練誤差」與「模型複雜度」之間取得平衡，而不是單純追求訓練誤差最低。

---

(c) 深度學習相對於傳統機器學習的主要優勢

1. 自動學習特徵表示

傳統機器學習通常需要人工設計特徵，例如影像中的邊緣、紋理，文字中的詞頻或 n-gram。深度學習能透過多層神經網路，從原始資料中自動學習由低階到高階的特徵。

以影像為例：

• 前層學習邊緣與簡單形狀
• 中層學習局部構造
• 後層學習物體或語意概念

因此可減少人工特徵工程的需求。

2. 能表達複雜的非線性關係

深度神經網路透過多層非線性轉換，能近似非常複雜的函數，適合處理影像、語音、自然語言等複雜問題。相較之下，部分傳統模型的表達能力受限於模型形式或人工設計的特徵。

3. 適合處理非結構化資料

深度學習在以下資料型態上表現特別突出：

• 影像：卷積神經網路
• 語音與時間序列：循環神經網路、Transformer
• 文字：Transformer 與大型語言模型
• 影片：空間與時間特徵聯合建模

4. 可進行端到端學習

這題考驗對邏輯迴歸、決策樹（ID3 演算法）的理解，以及它們在處理不同數據集時的表現，特別是關於過度擬合和線性可分性的問題。

數據集分析:

• Dataset 1: 顯示「+」和「*」兩類數據點，它們之間有明顯的線性界線。可以找到一條直線將兩類數據完全分開。
• Dataset 2: 顯示「+」和「*」兩類數據點，它們之間沒有明顯的線性界線，存在交叉。無法用一條直線完全分開。
• Dataset 3: 包含「+」和「*」兩類數據點，但有一個特殊的三角形點，它同時屬於「cross」和「star」兩個類別，並且是唯一一個跨越類別界線的點。從圖上看，如果忽略三角形點，其他點看起來是線性可分的。但這個三角形點的存在使得情況複雜化。

(a) By using Logistic Regression without regularization, which datasets among these three can produce 100% training accuracy? Explain your solution.

邏輯迴歸 (Logistic Regression) 的特性:

• 邏輯迴歸在沒有正則化的情況下，本質上是尋找一個線性決策邊界 (linear decision boundary)。它通過 sigmoid 函數將線性模型的輸出映射到機率，然後基於一個閾值（通常是 0.5）進行分類。
• 對於一個二元分類問題，邏輯迴歸模型學習到的決策邊界是線性的。如果數據是線性可分的，邏輯迴歸可以找到一個超平面（在二維空間中是一條直線）將兩個類別完全分開，從而實現 100% 的訓練準確率。
• 如果數據不是線性可分的，邏輯迴歸即使在訓練集上，也無法找到一個完美的線性決策邊界，因此訓練準確率不可能達到 100%。

分析各數據集:

• Dataset 1: 數據點清晰地顯示出線性可分性。可以找到一條直線將「+」和「*」完全分開。因此，沒有正則化的邏輯迴歸可以找到這樣的線性決策邊界，從而達到 100% 的訓練準確率。
• Dataset 2: 數據點之間存在交叉，不是線性可分的。無法用一條直線將兩類數據完全分開。因此，沒有正則化的邏輯迴歸無法在訓練集上達到 100% 的準確率。
• Dataset 3: 數據集中有一個三角形點，同時屬於兩個類別。這意味著該點本身就存在類別重疊。
  • 如果邏輯迴歸試圖將「+」和「*」分開，它會尋找一條線性邊界。
  • 考慮三角形點：它同時是 cross 和 star。
    • 如果我們將三角形視為 cross，那麼 star 類別中會有一個點在 cross 區域。
    • 如果我們將三角形視為 star，那麼 cross 類別中會有一個點在 star 區域。
  • 最關鍵的是，題目描述「Dataset 3 contains one data point (triangle) that belongs to both cross and star classes, and is the only one overlapping point of different classes in these three datasets」。這句話意味著這個點本身就導致了類別的重疊。
  • 在標準的分類問題定義中，一個樣本點只能屬於一個類別。但這裡將一個點定義為同時屬於兩個類別，這在邏輯迴歸的框架下是難以直接處理的，因為邏輯迴歸通常輸出一個樣本屬於每個類別的機率（例如，屬於 class 1 的機率 $p$，屬於 class 0 的機率 $1-p$）。
  • 然而，如果我們理解為，這個三角形點使得數據集本質上不是線性可分的（因為任何線性決策邊界都會將這個「兩者皆是」的點劃分到一個類別，而它實際上屬於兩個類別），那麼邏輯迴歸就無法 100% 準確地分類它。
  • 另一種解釋: 如果我們將三角形點視為一個「模糊」的點，它可能被模型預測為屬於某個類別。如果模型預測它屬於 cross，而它實際上也是 cross，那麼這一次預測就對 cross 類別是正確的。但它也屬於 star 類別。
  • 更嚴謹的理解是，如果一個點被定義為同時屬於兩個類別，那麼任何單一類別的分類器（包括邏輯迴歸）都無法在這一個點上同時滿足「屬於 cross」和「屬於 star」的要求。
  • 或者，我們可以將這個三角形點視為一個「噪音點」或「模糊點」。如果邏輯迴歸試圖找到一個線性邊界，它可能會將這個點劃分到某個類別。如果該點的「真實」標籤被認為是「cross」且模型預測為「cross」（雖然它同時也是 star），這一次預測對於「cross」來說是正確的。但問題是如何定義 100% 的訓練準確率。
  • 最直接的解釋: 「重疊點」意味著數據集不是線性可分的。任何線性分類器都無法完美地區分。