# 1. 分類器的基本架構
在二分類問題中（例如判斷是 Pokémon 還是 Digimon），分類器函數 𝑓(𝑥) 會根據輸入特徵做出類別判斷，從輸入資料 𝑥 預測其類別標籤 𝑦∈{0,1}。

## 1.1. 閾值分類器與函數族𝐻
考慮一整組可能的分類函數組成假設空間（hypothesis space）𝐻：

$\mathcal{H} = \{ f_h \mid h \in \{1, 2, \dots, 10000\} \}$。

表示有 10000 個可能的分類器，每個對應一個不同的 threshold ℎ。任務是從這個假設空間中選出一個最適合的分類器。

## 1.2. 最佳分類器
給定一組訓練資料：

$\mathcal{D}_{\text{train}} = \{ (x^1, \hat{y}^1), (x^2, \hat{y}^2), \dots, (x^N, \hat{y}^N) \}$。

目標是找到一個最小化損失的分類器 $h^{\text{train}}$，即：

$h^{\text{train}} = \arg\min_{h \in \mathcal{H}} L(h, \mathcal{D}_{\text{train}})$。

其中，$L(h, \mathcal{D}_{\text{train}})$ 表示模型 $h$ 在訓練資料上的平均錯誤率（損失）。理想情況下，分類器 $h^{\text{train}}$ 應該也能在真實世界中所有資料 $\mathcal{D}_{\text{all}}$ 上有相似表現：

$L(h^{\text{train}}, \mathcal{D}_{\text{all}}) \approx L(h^{\text{all}}, \mathcal{D}_{\text{all}})$。

其中，$h^{\text{all}}$ 是在全資料下訓練出來的理想分類器。

# 2. 損失函數與可導性
機器學習透過最小化損失函數 $L(h, \mathcal{D})$ 來選出最佳分類器。0-1 Loss 與 Cross-Entropy Loss 為兩種常見損失函數。

【0-1 Loss】

僅計算預測錯誤的比例，$\mathbb{I}$ 為指示函數，條件為真則為 1，否則為 0。優點為直觀，缺點為不可導，無法用於梯度下降訓練。公式如下：

$L(h, \mathcal{D}) = \frac{1}{N} \sum_{n=1}^{N} \mathbb{I}(f_h(x^n) \ne \hat{y}^n)$。

【Cross-Entropy Loss】

可導，適合用於深度學習。預測越接近正確類別，損失越小。公式如下：

$L(h, \mathcal{D}) = - \frac{1}{N} \sum_{n=1}^{N} \left[ y^n \log(\hat{y}^n) + (1 - y^n) \log(1 - \hat{y}^n) \right]$。

## 2.1. 可導性與訓練的重要性
訓練過程多使用梯度下降法（Gradient Descent）更新參數。若損失函數不可導，無法計算梯度，模型將無法有效學習。

| 損失函數 | 是否可導 | 是否適合訓練 | 用途 |
| ------ | ----- | ------ | -------- |
| 0-1 損失 |不可導 |不適合 | 測試/評估準確率 |
| 交叉熵損失 |可導|適合 | 用於訓練過程 |

## 2.2. 損失的平均與樣本數關係
損失函數通常表示為資料上的平均錯誤：$L(h, \mathcal{D}) = \frac{1}{N} \sum_{n=1}^{N} \ell(h, x^n, \hat{y}^n)$。

其中，$\ell(h, x, \hat{y})$ 是單一樣本的損失。當 $N$ 越大，平均損失越穩定，可更貼近真實誤差。

# 3. 訓練與泛化的目標
訓練過程中的目標是找到使訓練損失最小的分類器：

$h^{\text{train}} = \arg\min_{h \in \mathcal{H}} L(h, \mathcal{D}_{\text{train}})$。

但最關心的是真實資料上的表現，也就是理想分類器 $h^{\text{all}}$ 的損失：

$h^{\text{all}} = \arg\min_{h \in \mathcal{H}} L(h, \mathcal{D}_{\text{all}})$。

## 3.1. 泛化能力的目標
目標是讓實際訓練出的分類器 $h^{\text{train}}$ 在真實資料上的表現接近 $h^{\text{all}}$：

$L(h^{\text{train}}, \mathcal{D}_{\text{all}}) \approx L(h^{\text{all}}, \mathcal{D}_{\text{all}})$。

訓練出來的模型不應只在訓練資料表現好，更應在未見過的資料上維持穩定表現。

## 3.2.誤差界限的目標形式
若可保證下式成立，表示模型有良好泛化能力：

$L(h^{\text{train}}, \mathcal{D}_{\text{all}}) - L(h^{\text{all}}, \mathcal{D}_{\text{all}}) \leq \delta$。

其中 $\delta$ 為容許的泛化誤差範圍。理想情況下，應使 $\delta$ 趨近於 0。

# 4. i.i.d.與樣本抽樣假設
常見假設：訓練資料為獨立且同分布（i.i.d., independent and identically distributed）。目的為確保訓練資料能代表整體資料分布，避免偏誤。

## 4.1. 好資料的定義
若對任意分類器 $h \in \mathcal{H}$，皆有：

$|L(h, \mathcal{D}{\text{train}}) - L(h, \mathcal{D}{\text{all}})| \leq \varepsilon$。

則稱此 $\mathcal{D}_{\text{train}}$ 為「好」的訓練資料。此性質稱為均勻收斂（uniform convergence）。

## 4.2. 使用測試集近似整體分布
由於 $\mathcal{D}{\text{all}}$ 通常不可得，訓練後以測試集 $\mathcal{D}{\text{test}}$ 估計模型在未知資料上的表現：

$L(h, \mathcal{D}{\text{test}}) \approx L(h, \mathcal{D}{\text{all}})$。

測試集須與訓練集相互獨立，且同樣來自整體分布，才能合理作為泛化能力的評估依據。

# 5. 訓練失敗機率與聯集界限
## 5.1. 壞資料的定義
若存在某個 $h \in \mathcal{H}$ 使得：

$|L(h, \mathcal{D}{\text{train}}) - L(h, \mathcal{D}{\text{all}})| > \varepsilon$。

則稱 $\mathcal{D}_{\text{train}}$ 為「壞」的訓練資料。此情況代表模型在訓練資料上表現佳，但無法泛化至整體資料。

## 5.2. Union Bound：擴展至整體失敗機率
整體訓練失敗機率為所有 $h \in \mathcal{H}$ 出錯的聯集機率：

$\Pr(\mathcal{D}{\text{train}} \text{ is bad}) = \Pr\left( \bigcup{h \in \mathcal{H}} \text{bad due to } h \right)$。

由 union bound 得：

$\Pr(\mathcal{D}{\text{train}} \text{ is bad}) \leq \sum{h \in \mathcal{H}} \Pr(\text{bad due to } h)$。

即便單一模型錯誤機率低，只要模型數量多，整體失敗機率仍可能變高。

## 5.3. Hoeffding Inequality：單一模型出錯機率上限
Hoeffding 不等式給出單一模型出錯機率上限：

$\Pr\left( |L(h, \mathcal{D}{\text{train}}) - L(h, \mathcal{D}{\text{all}})| > \varepsilon \right) \leq 2 \exp(-2N \varepsilon^2)$。

其中，$N$ 為訓練資料筆數。當 $N$ 增加，錯誤機率指數下降。

# 6. 模型複雜度與泛化保證
將 union bound 與 Hoeffding 不等式結合，可得整體訓練失敗機率上限：

$\Pr(\mathcal{D}_{\text{train}} \text{ is bad}) \leq |\mathcal{H}| \cdot 2 \exp(-2N \varepsilon^2)$。

此式顯示模型數量 $|\mathcal{H}|$ 越多，或資料筆數 $N$ 越少，整體失敗機率越高。

## 6.1. 降低失敗機率的方法
依上式，失敗機率可透過以下方式降低：

1. 增加資料筆數 $N$

2. 降低模型空間大小 $|\mathcal{H}|$

3. 調整容許誤差 $\varepsilon$（但 $\varepsilon$ 不宜太大）

## 6.2. 連續參數模型的處理
現實中多數模型參數為連續值，理論上 $|\mathcal{H}|$ 為無限大。處理方式如下：

【有限精度離散化】

電腦實作中參數為有限精度，實際上模型空間有限，可視為離散。

【使用 VC-dimension】

可用 VC 維度衡量假設空間容量，作為 $|\mathcal{H}|$ 的替代指標。

# 7. 複雜度取捨與深度學習的應對
## 7.1. 假設空間過小的風險
若假設空間 $|\mathcal{H}|$ 過小，雖然能降低泛化誤差，但可能無法包含理想分類器 $h^{\text{all}}$，導致模型表現上限偏低：

$L(h^{\text{train}}, \mathcal{D}{\text{all}}) > L(h^{\text{all}}, \mathcal{D}{\text{all}})$。

此為理想損失無法達成的情況。

## 7.2. 假設空間過大的風險
若 $|\mathcal{H}|$ 過大，雖然可能包含 $h^{\text{all}}$，但容易選到在訓練資料上表現很好、在真實資料上表現差的模型，產生 overfitting。失敗機率上限會因 $|\mathcal{H}|$ 增加而提高。

## 7.3. 複雜度與資料量的平衡
1. 模型複雜度越高，需更多資料支撐
2. 模型複雜度越低，表現極限下降
3. 應使模型複雜度與資料量匹配，確保既不欠擬合也不過擬合。