• 統計學習方法
  • 第 1 章 統計學習及監督學習概論
    • 附加知識
      • 各種空間介紹
      • 維度詛咒
    • 參考文獻
  • 第 2 章 感知機

統計學習方法

第一版

第二版

第 1 章 統計學習及監督學習概論

統計學習的主要特點是：

1. 統計學習以電腦及網路為平台，是建立在電腦及網路之上的；
2. 統計學習以數據為研究對象，是數據驅動的學科；
3. 統計學習的目的是對數據進行預測與分析；
4. 統計學習以方法為中心，統計學習方法構建模型並應用模型進行預測與分析；
5. 統計學習是概率論、統計學、資訊理論、計算理論、最優化理論及電腦科學等多個領域的交叉學科，並且在發展中逐步形成獨自的理論體系與方法論。

假設空間(hypothesis space)：
$$\begin{gathered} \mathcal{H}=\{f(x;\theta )|\theta \in {\mathbb{R}}^D\} \\ or\mathcal{F}=\{P|P(Y|X;\theta ),\theta \in {\mathbb{R}}^D\} \end{gathered}$$
其中$f(x;\theta )$是參數為θ

$\theta$

θ 的函數（決策函數），也稱為模型（Model），參數向量θ

$\theta$

θ取值與D

$D$

D維歐式空間RD

$\mathbb{R}^D$

RD,也稱為參數空間(parameter space)，D

$D$

D 為參數的數量(維度)

模型的假設空間(hypothesis space)包含所有可能的條件概率分布或決策函數

特徵空間（feature space）：
每個具體的輸入是一個實例（instance），通常由特徵向量（feature vector）表示。這
時，所有特徵向量存在的空間稱為特徵空間（feature space）。特徵空間的每一維對應於
一個特徵。

輸入空間中的一個輸入向量x=(x1,x2)

$x = (x_1,x_2)$

x=(x1​,x2​)，在多項式模型中特徵向量是(x21,x1x2,x22,...

$x_1^2,x_1x_2,x_2^2,…$

x12​,x1​x2​,x22​,…)
一般說的線性模型，指的是特徵向量的線性組合，而不是指輸入向量，所以說模型都是定義在特徵空間上的

統計學習的三要素：

1. 模型的假設空間(hypothesis space)，簡稱：模型(model)
2. 模型選擇的準則(evaluation criterion)，簡稱：策略(strategy)或者學習準則
3. 模型學習的演算法(algorithm)，簡稱：演算法(algorithm)

以線性回歸（Linear Regression）為例：
模型： f(x;w,b)=wTx+b

$f(x;w,b) = w^Tx +b$

f(x;w,b)=wTx+b
策略(strategy)或者學習準則: 平方損失函數 L(y,yˆ)=(y−f(x,θ))2

$\mathcal L(y,\hat{y}) = (y-f(x,\theta))^2$

L(y,y^​)=(y−f(x,θ))2
演算法：解析解analytical solution(閉式解closed-form solution)和數值解numerical solution，如：closed-form的最小二乘的解以及梯度下降法

機器學習的定義：

使用訓練數據來計算接近目標 𝑓 的假設（hypothesis ）g （來自：Machine Learning Foundations（機器學習基石）,25 頁）

監督學習：
監督學習(supervised learning)是指從標註數據中學習預測模型的機器學習問題。本質是學習輸入到輸出的映射的統計規律。

輸入變數與輸出變數均為連續變數的預測問題稱為回歸問題；
輸出變數為有限個離散變數的預測問題稱為分類問題；
輸入變數與輸出變數均為變數序列的預測問題稱為標註問題(可以理解為特殊的分類問題)。

監督學習的模型可以是概率模型或非概率模型，由條件概率分布P(Y∣X)

$P(Y|X)$

P(Y∣X)或決策函數（decision function）Y=f(X)

$Y=f(X)$

Y=f(X)表示，隨具體學習方法而定。對具體的輸入進行相應的輸出預測時，寫作P(y∣x)

$P(y|x)$

P(y∣x)或Y=f(x)

$Y=f(x)$

Y=f(x)。
$$y=\underset{y}{\mathrm{argmax}}P(y|x)$$

聯合概率分布：
監督學習假設輸入與輸出的隨機變數 X 和 Y 遵循聯合概率分布P(X,Y)

$P(X,Y)$

P(X,Y)。P(X,Y)

$P(X,Y)$

P(X,Y)表示分布函數，或分布密度函數。注意，在學習過程中，假定這一聯合概率分布存在，但對學習系統來說，聯合概率分布的具體定義是未知的。訓練數據與測試數據被看作是依聯合概率分布P(X,Y)

$P(X,Y)$

P(X,Y)獨立同分布產生的。
統計學習假設數據存在一定的統計規律，X

$X$

X和Y

$Y$

Y具有聯合概率分布的假設就是監督學習關於數據的基本假設。

非監督學習：
非監督學習(unsupervised learning)是指從無標註數據中學習預測模型的機器學習問題。本質是學習數據中的統計規律或潛在結構。

非監督學習的模型可以表示為函數z=g(x)

$z = g(x)$

z=g(x)或者條件概率分布P(z∣x)

$P(z|x)$

P(z∣x) （輸出z

$z$

z可以是聚類或者降維）
$$z=\underset{z}{\mathrm{argmax}}P(z|x)$$
以及 條件概率分布P(x∣z)

$P(x|z)$

P(x∣z) （用來做概率密度估計，比如 GMM 中P(x∣z)

$P(x|z)$

P(x∣z)屬於高斯分布，如果假設知道數據來自哪個高斯分布，即知道z

$z$

z，我們可以用極大似然估計來估計相關參數）。

概率模型（probabilistic model）與非概率模型（non-probabilistic model）或者確定性模型（deterministic model）：

概率模型（probabilistic model）- 條件概率分布 P(y|x)和 非概率模型（non-probabilistic model） – 函數 y=f(x)可以相互轉化，條件概率分布最大化後得到函數，函數歸一化後得到條件概率分布。所以概率模型與非概率模型的區別不在於輸入輸出之間的映射關係，而在於模型的內部結構：概率模型一定可以表示為聯合概率分布的形式，而非概率模型則不一定存在這樣的聯合概率分布。

概率模型的代表是概率圖模型（probabilistic graphical model）參考文獻[3]

$^{參考文獻[3]}$

參考文獻[3]，聯合概率分布可以根據圖的結構分解為因子乘積的形式，可以用最基本的加法規則和乘法規則進行概率推理：
$$\begin{gathered} P(x)=\sum _{y}P(x,y) \\ P(x,y)=P(x)P(y|x) \end{gathered}$$

參數化模型（parametric model）和非參數化模型（non-parametric model）：

參數化模型假設模型參數的維度固定，模型可以由有限維參數完全刻畫。(如：感知機、GMM)
非參數化模型假設模型參數的唯獨不固定或者說無窮大，隨著訓練數據量的增加而不斷增大。(如：決策樹、支援向量機)

在線學習（online learning）和批量學習（batch learning）：

在線學習每次接受一個樣本，預測後學習模型，並不斷重複該操作。
批量學習一次接受所有數據，學習模型之後進行預測。

在線學習比批量學習更難，因為每次模型更新中可利用的數據有限。

貝葉斯學習（Bayesian learning）/ 貝葉斯推理（Bayesian inference）：
$$\begin{gathered} \mathrm{Bayes}\mathrm{Rule}: \\ \underset{\mathrm{posterior}}{\underbrace{P(X|Y)}}=\frac{\stackrel{\mathrm{likelihood}}{\overbrace{P(Y|X)}}\stackrel{\mathrm{prior}}{\overbrace{P(X)}}}{\underset{\mathrm{evidence}}{\underbrace{P(Y)}}}=\frac{\stackrel{\mathrm{likelihood}}{\overbrace{P(Y|X)}}\stackrel{\mathrm{prior}}{\overbrace{P(X)}}}{\underset{\mathrm{evidence}}{\underbrace{\sum _{x}P(Y|X)P(X)}}} \end{gathered}$$

核技巧（kernel trick）/ 核方法（kernel method）：

核方法是一類把低維空間的非線性可分問題，轉化為高維空間的線性可分問題的方法。
核技巧是一種利用核函數直接計算 ⟨ϕ(x),ϕ(z)⟩

$\lang \phi(x),\phi(z) \rang$

⟨ϕ(x),ϕ(z)⟩ ，以避開分別計算 ϕ(x)

$\phi(x)$

ϕ(x) 和 ϕ(z)

$\phi(z)$

ϕ(z) ，從而加速核方法計算的技巧。

核函數：設 X

$\mathcal X$

X 是輸入空間（即 xi∈X

$x_i \in \mathcal X$

xi​∈X ， X

$\mathcal X$

X 是 Rn

$\mathbb R^n$

Rn 的子集或離散集合 ），又設 H

$\mathcal H$

H 為特徵空間（​ 希爾伯特空間附加知識:各種空間介紹

$^{附加知識:各種空間介紹}$

附加知識:各種空間介紹），如果存在一個從 X

$\mathcal X$

X 到 H

$\mathcal H$

H 的映射

$$\varphi (x):\mathcal{X}\to \mathcal{H}$$

使得對所有 x,z∈X

$x,z \in \mathcal X$

x,z∈X ，函數 K(x,z)

$K(x,z)$

K(x,z) 滿足條件

$$K(x,z)=\varphi (x).\varphi (z)=⟨\varphi (x),\varphi (z)⟩$$

則稱 K(x,z)

$K(x,z)$

K(x,z) 為核函數。其中 ϕ(x)

$\phi(x)$

ϕ(x) 為映射函數， ⟨ϕ(x),ϕ(z)⟩

$\lang \phi(x),\phi(z) \rang$

⟨ϕ(x),ϕ(z)⟩ 為內積。

核技巧的想法是，在學習和預測中只定義核函數 K(x,z)

$K(x,z)$

K(x,z) ，而不顯式地定義映射函數 ϕ

$\phi$

ϕ。通常直接計算K(x,z)

$K(x,z)$

K(x,z)比較容易，而通過ϕ(x)

$\phi(x)$

ϕ(x)和ϕ(z)

$\phi(z)$

ϕ(z)計算K(x,z)

$K(x,z)$

K(x,z)並不容易。

注意：ϕ

$\phi$

ϕ是輸入空間Rn

$\mathbb{R}^n$

Rn到特徵空間H

$\mathcal H$

H的映射，特徵空間H

$\mathcal H$

H一般是高維的，甚至是無窮維的。所以ϕ

$\phi$

ϕ不好計算，甚至會帶來維度災難又稱維度詛咒（Curse of Dimensionality）附加知識:維度詛咒

$^{附加知識:維度詛咒}$

附加知識:維度詛咒。

附加知識

各種空間介紹

線性空間就是定義了加法和數乘的空間(空間里的一個元素就可以由其他元素線性表示)。

---

度量空間就是定義了距離的空間（曼哈頓距離，歐氏距離，閔可夫斯基距離，馬氏距離，切比雪夫距離）。
定義距離時，有三條公理必須遵守：

1. 非負性、同一性：dist(xi,xj)≥0
   $dist(x_i,x_j) \geq 0$

   dist(xi​,xj​)≥0(非負性)，dist(xi,xj)=0

   $dist(x_i,x_j) = 0$

   dist(xi​,xj​)=0當且僅當xi=xj

   $x_i=x_j$

   xi​=xj​(同一性)

2. 對稱性：dist(xi,xj)=dist(xj,xi)
   $dist(x_i,x_j) = dist(x_j,x_i)$

   dist(xi​,xj​)=dist(xj​,xi​)

3. 三角不等式(也叫直遞性)：dist(xi,xj)≤dist(xi,xk)+dist(xk,xj)
   $dist(x_i,x_j) \leq dist(x_i,x_k) + dist(x_k,x_j)$

   dist(xi​,xj​)≤dist(xi​,xk​)+dist(xk​,xj​)
   希爾伯特空間(Hilbert)

文字解釋：【兩點之間距離不為負；兩個點只有在 空間 上重合才可能距離為零；a 到 b 的距離等於 b 到 a 的距離;a 到 c 的距離加上 c 到 b 的距離大於等於 a 直接到 b 的距離;】

---

賦范空間就是定義了範數的空間。
x的範數||x||就是x的長度。那麼這裡的長度和上一節中說的距離到底有什麼區別呢。距離的概念是針對兩個元素來說的，例如d(x,y)指的是x與y兩個元素之間的距離，而範數是針對一個元素來說的，每一個元素都對應一個範數，可以將範數理解為一個元素到零點的距離（這只是一種理解，並不是定義），也就是它自己的長度。
定義：
稱 映射∣∣.∣∣:Rn→R

$||.|| : \mathbb{R}^n \to \mathbb{R}$

∣∣.∣∣:Rn→R為 Rn

$\mathbb{R}^n$

Rn 上的範數，當且僅當：

1. 非負性： ∀x∈Rn,∣∣x∣∣≥0
   $\forall x \in \mathbb{R}^n ,||x|| \geq 0$

   ∀x∈Rn,∣∣x∣∣≥0 ,∣∣x∣∣=0

   $||x|| = 0$

   ∣∣x∣∣=0當且僅當x=0

   $x=0$

   x=0

2. 數乘：∀x∈Rn,a∈Rn,∣∣ax∣∣=∣a∣.∣∣x∣∣
   $\forall x \in \mathbb{R}^n ,a \in \mathbb{R}^n, ||ax|| = |a|.||x||$

   ∀x∈Rn,a∈Rn,∣∣ax∣∣=∣a∣.∣∣x∣∣

3. 三角不等式: ∀x,y∈Rn,∣∣x+y∣∣≤∣∣x∣∣+∣∣y∣∣
   $\forall x,y \in \mathbb{R}^n ,||x+y|| \leq ||x|| + ||y||$

   ∀x,y∈Rn,∣∣x+y∣∣≤∣∣x∣∣+∣∣y∣∣

如果我們定義了範數，可以在這基礎上定義距離：dist(x,y)=||x-y||。根據範數的三條性質，我們可以證明我們這樣定義的距離也滿足距離的定義，聰明的你可以自己證明一下（對稱性的證明，提一個-1出來，一加絕對值就是1了）。

也就是說範數其實是一個更加具體的概念，有了範數一定能利用範數定義距離，但是有距離不能定義範數。

也許你會問，你不是說理解範數就是一個元素到零點的距離嗎，那定義範數為||x||=dist(x,0) 不就行了嗎。這樣的話，對於範數的第二條性質就不一定會滿足，||ax||=dist(ax,0)，而dist(ax,0)不一定等於|a|dist(x,0)，具體等不等於還要看你的距離是怎麼定義的。

了解到這裡那麼你會發現：
歐式距離對應L2範數
曼哈頓距離對應L1範數

---

線性賦范空間就是定義了加法、數乘和範數的空間。

---

巴拿赫空間就是完備的賦范線性空間。(Banach space)
完備的空間的定義：如果一個空間是完備的，那麼該空間中的任何一個柯西序列都收斂在該空間之內。

首先來說一下柯西序列是什麼，柯西序列就是隨著序數增加，值之間的距離越來越小的序列。換一種說法是，柯西序列可以在去掉有限個值之後，使任意兩個值之間的距離¯¯¯¯¯¯¯

$\underline{\mathrm{距離}}$

距離​都小於任意給定正常數（其實這就是定義了一個極限而已）。

那麼任意一個柯西序列都收斂在該空間內是什麼意思呢，舉個例子你就明白了。

設定義在有理數空間Q上的序列：xn=[2√n]n

$x_n = \frac{[\sqrt{2}n]}{n}$

xn​=n[2​n]​，其中[x]表示x取整數部分。
對於這個數列來說，每一個元素的分子分母都是整數，所以每一個xn

$x_n$

xn​都在有理數空間Q上，那這個序列的極限呢，稍有常識的人都能看出，這個序列的極限是2–√

$\sqrt{2}$

2​，而這並不是一個有理數，所以這個柯西序列的極限不在該空間裡面，也就是說有理數空間Q是不完備的。

所以完備的意義我們可以這樣理解，那就是在一個空間上我們定義了極限，但是不論你怎麼取極限，它的極限的值都不會跑出這個空間，那麼這個空間就是完備空間。

另外，不知道你有沒有發現，上面在解釋什麼是柯西序列的時候，有一個詞我加了下劃線，那就是距離，也就說說在定義完備空間之前，要先有距離的概念。所以完備空間，其實也是完備度量空間。

所以，巴拿赫空間滿足幾條特性呢：距離、範數、完備。

---

內積空間就是定義了內積的空間。Inner product space
有時也稱准希爾伯特空間。
內積就是我們所說的點乘、標積，它的定義方式也不是唯一的，但如同距離範數的定義一樣，內積的定義也要滿足某些條件，不能隨便定義。

定義映射⟨.,.⟩:V×V→F

$\lang .,. \rang : V \times V \to \mathbb{F}$

⟨.,.⟩:V×V→F, 其中V

$V$

V是向量，F

$\mathbb{F}$

F是標量
有x,y,z∈V,s∈F

$x,y,z \in V ,s \in \mathbb{F}$

x,y,z∈V,s∈F，那麼內積滿足

1. 第一個參數中的線性:
   $$\begin{gathered} ⟨sx,y⟩=s⟨x,y⟩ \\ ⟨x+y,z⟩=⟨x,z⟩+⟨y,z⟩ \\ ⟨0,x⟩=0 \end{gathered}$$

2. 共軛對稱:⟨x,y⟩=⟨y,x⟩¯¯¯¯¯¯¯¯

   $\lang x,y \rang = \overline{\lang y,x \rang }$

   ⟨x,y⟩=⟨y,x⟩​

3. 正定性:⟨x,x⟩>0if  x≠0

   $\lang x,x \rang > 0 \quad\mathrm{if}\; x \neq 0$

   ⟨x,x⟩>0ifx=0

4. 正半定性或非負定性:∀x,⟨x,x⟩≥0

   $\forall{x}, \lang x,x \rang \geq 0$

   ∀x,⟨x,x⟩≥0

5. 確定性：⟨x,x⟩=0必然有x=0

   $\lang x,x \rang = 0 必然有 x=0$

   ⟨x,x⟩=0必然有x=0

3，4，5可以跟上面定義範數和距離一樣寫成一個

例子-歐幾里得向量空間:
x,y∈Rn,⟨x,y⟩=xTy=∑ni=1xiyi

$x,y \in \mathbb{R}^n , \lang x,y \rang = x^Ty=\sum_{i=1}^n{x_iy_i}$

x,y∈Rn,⟨x,y⟩=xTy=∑i=1n​xi​yi​

只有定義了內積，才會有夾角的概念，才會有正交的概念，另外內積也可以定義範數，也就是說內積是比範數更具體的一個概念。

---

歐式空間就是定義了內積的有限維實線性空間。

---

希爾伯特空間就是完備的內積空間。(Hilbert space)
希爾伯特空間中的元素一般是函數，因為一個函數可以視為一個無窮維的向量。

參考：一片文章帶你理解再生核希爾伯特空間（RKHS）以及各種空間

維度詛咒

維度詛咒通常是指在涉及到向量的計算的問題中，隨著維數的增加，計算量呈指數倍增長的一種現象。高維度有更大的特徵空間，需要更多的數據才可以進行較準確的估計。

若特徵是二值的，則每增加一個特徵，所需數據量都在以2的指數級進行增長，更何況很多特徵不只是二值的。

幾何角度1：

上圖表示一個多維空間（以二維為例），設正方形邊長為1，則其內切圓半徑為r=0.5

$r=0.5$

r=0.5，則正方形面積為1，內切圓面積為π(0.5)2

$\pi(0.5)^2$

π(0.5)2 。若將此變為三維情況下，正方體體積為1，內切球體積為43π(0.5)3

$\frac{4}{3}\pi(0.5)^3$

34​π(0.5)3。

因此球體的體積可以表示為V(d)=πd/2Γ(d2+1)0.5d=k(0.5)d

$V(d) = \frac{\pi^{d/2}}{\varGamma(\frac{d}{2}+1)}0.5^d = k(0.5)^d$

V(d)=Γ(2d​+1)πd/2​0.5d=k(0.5)d(d為維度),則 limd→∞k(0.5)d=0

$\lim_{d \to \infty}k(0.5)^d = 0$

limd→∞​k(0.5)d=0，其內切超球體的體積為0。由此可知，高維情況下，數據大都分布在四角（正方形內，內切圓外），稀疏性太大，不好分類。

維度越大，超球體體積越小。說明落在超球體內的樣本越少，因為超球體是超立方體的內切球。不在球內,那隻能在角落！

幾何角度2：

上圖也表示一個多維空間（以二維為例），則其中圖形的體積有如下關係：外圓半徑r=1

$r=1$

r=1，內圓半徑為r−ε

$r−\varepsilon$

r−ε 。同樣在高維情況下，外圓體積為V外圓=k.1d=k

$V_{外圓} = k.1^d = k$

V外圓​=k.1d=k，中間的圓環體積為V圓環=k−k(1−ε)d

$V_{圓環} = k – k(1-\varepsilon)^d$

V圓環​=k−k(1−ε)d，則：
$$\underset{d\to \infty }{\lim }\frac{V_{圓環}}{V_{外圓}}=\underset{d\to \infty }{\lim }\frac{k-k(1-\epsilon {)}^d}{k}=\underset{d\to \infty }{\lim }(1-(1-\epsilon {)}^d)=1$$

高維情況下，無論ε

$\varepsilon$

ε多小，只要d足夠大，圓環幾乎佔據了整個外圓，內圓體積趨向於0，導致數據稀疏。

參考：
The Curse of Dimensionality in classification
機器學習-白板推導系列(五)-降維（Dimensionality Reduction）

參考文獻

[1] Hastie T,Tibshirani R,Friedman J. The Elements of Statistical Learning: DataMining,Inference,and Prediction. Springer. 2001（中譯本：統計學習基礎——數據挖掘、推理與預測。范明，柴玉梅，昝紅英等譯。北京：電子工業出版社，2004）

[2] Bishop M. Pattern Recognition and Machine Learning. Springer,2006

[3] Probabilistic Graphical Models: Principles and Techniques by Daphne Koller, Nir Friedman from The MIT Press

[4] Deep Learning (Ian Goodfellow, Yoshua Bengio, Aaron Courville)

[5] Tom M Michelle. Machine Learning. McGraw-Hill Companies,Inc. 1997（中譯本：機器學習。北京：機械工業出版社，2003）

[6] Bayesian Reasoning and Machine Learning by David Barber 2007–2020 ,other version

[7] Reinforcement Learning:An Introduction (second edition 2020) by Richard S. Sutton and Andrew G. Barto ,other version

[8] 周志華，機器學習，清華大學出版社 (手推筆記 以及 公式推導解析)

[9] Lecture Notes in MACHINE LEARNING Dr V N Krishnachandran