1. Introduction

機器學習問題可以做如下分類：

有監督學習（supervised learning） : Applications in which the training data comprises examples of the input vectors along with their corresponding target vectors.
1. 分類（classification） : to assign each input vector to one of finite number of discrete categories.
  1. 例子：識別手寫數字並將其標記為0~9這10個數字中的一個。
2. 回歸（regression） : the desired output consists of one or more continuous variables.
  1. 例子：基於反應物、溫度、壓力預測化學製造過程的產出。
無監督學習（unsupervised learning） : Pattern recognition problems in which the training data consists of a set of input vectors without any corresponding target values.
1. 聚類（clustering） : to discover groups of similar examples within the data
2. 密度估計（density estimation） : to determine the distribution of data within the input space
3. 降維（dimensionality reduction） : to project the data from a high-dimensional space down to two or three dimensions
4. 數據點/樣本生成（data point/sample generation） : to obtain new samples from the probability distribution that is close to the underlying probability distribution of the data points/samples
強化學習（reinforcement learning） : Problems about finding suitable actions to take in a given situation in order to maximize a reward, where optimal outputs are unknown.
1. 例子：Play the game of backgammon to a high standard with a neural network using appropriate reinforcement learning techniques (Tesauro, 1994). (這可能是深度強化學習最早成功的案例之一了。)
2. 上面的案例也可作為 credit assignment 的一個例子。具體地說，在一局遊戲結束後，勝利或失敗被以某種形式歸因於遊戲中採取的所有行動。個人認為這裡 credit assignment 是指在一個episodic task結束後，如何恰當的給特定行動，或者在某個特定狀態採取特定行動賦予合適的reward。
3. 這裡也有提到explore vs exploit和trial and error的思想。但總的來說因為本書基本沒怎麼觸及強化學習，講的不是特別好。如果要比較好了解強化學習的話還是應該看 Sutton & Barto 那本書。

本章主要介紹了一些最重要的概念和一些簡單的例子。在這之中包括將貫穿全書的三個工具：概率論、決策論以及信息論。

1.1 Example: Polynomial Curve Fitting

Example/Motivation : (a simple regression problem)

Given a real-valued target variable t, we wish to use this observation to predict the value of a real-valued target variable t. In particular, given N observations of x written as $\mathbf{x} \equiv $x\_{1}, \cdots, x\_{N}$^T$ together with corresponding observations of t written as $\mathbf{t}\equiv $t\_{1}, \cdots, t\_{N}$^{T}$ , can we fit the data so that we can make predictions of the value $\hat{t}$ of the target variable for some new value $\hat{x}$ of the input variable?

這是一個典型的二維回歸問題。上過Andrew Ng Coursera公開課的朋友們應該還記得一上來遇到的那個給定住宅面積預測住宅價格的問題。Bishop這裡給的訓練數據則是 $\sin$2\pi x$$ 在 $0,1$ $N$ 個均勻分佈點上的取值加以基於同一高斯分佈產生的隨機噪聲。如下圖是 $N=10$ 時的情況。

首先我們考慮用一個 $M$ 階多項式擬合數據，

$y$x,\mathbf{w}$=w\_{0}+w\_{1}x+w\_{2}x^{2}+\cdots+w\_{M}x^{M}=\sum\_{j= 0}^{M}w\_{j}x^{j}$ , $\mathbf{w}=$w\_{0}, \cdots, w\_{M}$$ (1.1)

$y$ 是一個關於 $\mathbf{w}$ 的線性方程。

定義：關於未知參數的線性方程被稱為線性模型（linear models）。

我們基於訓練數據決定 $\mathbf{w}$ 的取值，一個潛在的假設是我們需要預測的 $\hat{x},\hat{t}$ 和訓練數據來自同一分佈或兩者分佈非常接近，否則就沒有意義了。

a. 誤差函數

怎樣的 $\mathbf{w}$ 取值是好的呢？我們需要一把尺子來度量，這就是誤差函數（error function）。通過累加每一個訓練數據的預測目標變量 $y$\hat{x},\mathbf{w}$$ 相對真實目標變量 $\hat{t}$ 的偏移程度，誤差函數負責衡量訓練好的模型，即 $y$ 和訓練數據分佈之間的相似程度，其取值一般為非負。誤差函數的值越大，對於訓練數據而言模型越糟。

例子： $E$\mathbf{w}$=\frac{1}{2}\sum\_{n=1}^{N}\{y$x\_{n},\mathbf{w}$-t\_{n}\} ^{2}$ （平方誤差函數）

很自然地，在回歸問題中，當模型完美擬合訓練數據時，誤差一般會降到0。但值得注意的是在分類問題中，即便分類完美無缺誤差也可能不為0。

以下圖為例，我們有一個二元分類問題。在二維平面上有一個紅色類和一個藍色類。假設我們想用一條直線（在第二講裡我們會提到，它們被稱為決策邊界）來把它們分開。圖中同樣①和②都完美進行了分類，但我們會更希望模型訓練得到的是①而不是②因為①離兩個類最短距離之和要大於②。直覺來說當我們有更多數據樣本而不只是眼前6個的時候①成功的可能性更高。這個問題的正式名稱是泛化，我們在後面會提到。因此我們可能設計一個誤差函數使得②的誤差高於①。因此同樣①、②在數據上都能沒有錯誤地進行分類，②的誤差可能仍然不為0。

訓練模型的過程中，我們希望調整 $\mathbf{w}$ 來減少誤差函數的值，可以說是面向減少誤差建模，故用 $E$\mathbf{w}$$ 來表示誤差的值。

對於某些誤差函數（涉及函數的convexity，凸性），如平方誤差，我們可以通過對錶達式關於未知參數（如 $\mathbf{w}$ 之於 $E$\mathbf{w}$$ ）進行求導，令求導後的表達式等於0來得到最優參數 $\mathbf{w}^{\star }$ ,這樣得到的參數有閉型（有限次常見運算組合給出的表達式）。

b. 由泛化而來的模型選擇問題

現在我們知道了對於一個給定的正整數M，如何擬合訓練數據。一個接踵而來的問題是我們要如何決定M的取值。

考慮 $M=0,1,3,9$ 的四種情況，對於每一種情況，我們都基於平方誤差找到擬合訓練數據最好的多項式，如下圖。紅線為多項式圖形，綠線為 $\sin$2\pi x$$ 的圖形。

由上圖可知， $M$ 越大，多項式擬合數據的能力越強。當 $M=9$ 時，多項式甚至完美擬合了所有數據。然而我們從形狀上可以發現此時多項式的形狀與 $\sin$2\pi x$$ 相去甚遠。可以預見當我們在 $\sin$2\pi x$$ 上取新的數據點的話，多項式很難較好擬合這些新的數據點。相較之下， $M=3$ 時我們得到的多項式形狀則相當接近 $\sin$2\pi x$$ 的形狀。像 $M=9$ 時我們得到的模型這樣能很好擬合訓練數據卻對於從同一概率分佈得到的新數據擬合能力極差的情況，被稱為過擬合。像 $M=0,1$ 時這樣模型連訓練數據都無法很好擬合的情況被稱為欠擬合。

回到問題的出發點，我們希望訓練出的模型能盡可能學習到數據的原始分佈（或者不妨稱之為數據的生成器），使得模型能精準預測來自該分佈的新數據。模型不光需要在訓練數據上有好的表現，在新的數據上也應如此。正確預測新數據標籤（即 $\hat{x},\hat{t}$ 裡的 $\hat{t}$ ）的能力被稱為泛化。

由此，我們可以提出一種衡量模型泛化能力的量化方法。除了訓練數據外，我們另外取一組測試數據。在知道數據真實分佈的情況下（如例子中的 $\sin$2\pi x$$ ），我們直接從數據分佈裡採集新的數據點。否則我們可以預先把手頭的數據集劃分成訓練數據和測試數據。在訓練模型（擬合訓練數據）的過程中，擬合僅僅基於訓練數據。在訓練完後，我們用測試數據檢測模型的泛化能力，計算誤差函數的數值。

當我們用這一方法應用到多項式模型上時，我們會發現 $M=9$ 時模型在測試數據上的表現相比 $M\leq 8$ 時所有模型的表現都要糟糕的多。回到式1.1，當 $M=9$ 時，考慮標量的話，我們有十個未知參數 $w\_{0}, \cdots, w\_{9}$ 。當我們有十個線性獨立的數據點時，我們可以精確得到每個未知參數的唯一解，因而得到的多項式模型完全依賴於訓練數據點。事實上我們應該可以通過插值法得到近乎完全一樣（考慮到可能存在數值誤差）的多項式。我們注意到 $M=3$ 時多項式對訓練數據的擬合其實已經相當不錯了。一個由此而生的想法是在數據擬合改進有限的情況下，我們應該盡可能選擇簡單的模型，在多項式模型裡就是選擇盡可能小的 $M$ 。上述原則也可以被概括為“如無必要，勿增實體”，即是著名的奧卡姆剃刀原理。當然不同人對於這個問題可能存在不同看法。有人就認為我們在考慮泛化能力的前提下還是要盡可能選擇複雜的模型從而盡可能避免關於數據分佈信息的丟失。

對於某一特定模型，避免過擬合還有一種方法是使用盡可能多的訓練數據。同樣在 $M=9$ 的情況下，當我們取15個數據點乃至100個數據點時，隨著訓練數據集越來越大，我們曲線擬合的結果也越來越好。

在這100個數據點上， $M=3$ 時得到的模型很可能不如 $M=9$ 來得好。通常數據集越大，我們所能擬合的模型的複雜程度或表示能力越高，因此得到的模型可能更接近於數據的真實分佈。一種粗略的機制是訓練數據的樣本數量應當不小於未知參數數量的某一固定倍數（如5倍或10倍）。值得一提的是未知參數的數量並不能完全衡量模型的複雜度，在第三章我們會接觸到更多這方面的內容。

c. 正則化（regularization）

動機：複雜的模型擁有更強的表示能力，有沒有可能在無法隨意增加數據集的情況下，避免或改善過擬合的問題呢？

回到之前的回歸問題，當 $M=9$ 時，如果我們具體寫出擬合得到多項式的係數值的話會發現係數的絕對值非常大。係數越大，模型上下起伏越厲害。而係數越小，模型的形狀越平滑。我們希望能在擬合訓練數據程度和模型波動程度之間達成一個平衡，並寄希望於這種平衡能在一定程度上反映出模型對於真實數據分佈的學習程度。我們引入一種叫正則化的方法。

具體地，我們給原本的誤差函數加上一個正則項，令 $\tilde{E}$\mathbf{w}$=E$\mathbf{w}$+\lambda\Omega$\mathbf{w}$$ （或者在更一般的情況下我們考慮 $\Omega$f$$ ，預測函數的複雜度）， $\lambda$ 決定了正則項的權重， $\Omega$ 可以看做是一個衡量模型複雜度的函數。最常見的 $\Omega$ 就是 $\ell\_{p}$ 范數（ $\ell\_{p}$ -norm）， $\|\|\mathbf{w}\|\|\_{p}=$\sum\_{i=1}^{n}\|x\_{i}\|^{p}$^{1/p}$ 。上述正則化採取的是Tikhonov形式（form），另外一種正則化的形式是Ivanov形式： $\tilde{E}$\mathbf{w}$$ 使得 $\Omega$\mathbf{w}$\leq r$ 。 $r$ 一般由交叉驗證（cross validation）決定。

我們定義Tikhonov形式和Ivanov形式等價，如果：

$\forall r> 0$ , Ivanov解， $w\_{r}^{\*}=argmin\_{w}E$w$$ 使得 $\Omega$\mathbf{w}$\leq r$ ，對於某些 $\lambda>0$ 也是一個Tikhonov解： $w\_{r}^{\*}=argmin\_{w}E$\mathbf{w}$+\lambda\Omega$w$$ ， $\lambda> 0$ 。
反過來， $\forall \lambda> 0$ ， $\exists r> 0$ 使得與 $\lambda$ 對應的Tikhonov解為一個與 $r对应的$ 對應的Ivanov解。

換言之，兩者的解空間相同。

兩種形式是否滿足上述等價的定義要根據具體的誤差函數和模型複雜函數 $\Omega$ 來決定。

$\ell\_{2}$ 範數可能是最常見的正則項了： $\tilde{E}$\mathbf{w}$= E$\mathbf{w}$+\frac{\lambda}{2}\|\|w\|\|\_{2}^{2}$ , $\|\|w\|\|\_{2}^{2}=\sum\_{j=0}^{M}w\_{j}^{2}$ （1.4）。值得注意的是通常我們不選擇把 $w\_{0}$ 納入正則項，因為這會導致結果取決於對目標變量/標籤的原點的選擇。

加入正則項這樣的技巧在統計裡被稱為收縮（shrinkage），因為他們降低了係數的數值。在神經網絡裡，這種途徑被稱為權重下降（weight decay）。

在式1.4中，我們選擇了一個二階正則式。當 $E$\mathbf{w}$$ 為平方誤差函數時，目標函數為式1.4的回歸問題被稱為ridge regression。如果我們選擇了一個一階正則項,即 $\|\|w\|\|\_{1}=\sum\_{j=0}^{M}\|w\_{j}\|$ 時， $E$\mathbf{w}$+\frac{\lambda}{2}\|\|w\|\|\_{1}$ 代表的回歸問題被稱為lasso(least absolute shrinkage and selection operator) regression，在3.1.4我們會更深入地學習這個問題。

d.訓練集，驗證集，測試集

我們往往通過超參數（hyperparameter），一類由我們預先選擇而不是模型從數據習得的參數，來決定模型的複雜度（如之前提到的 $M$ 以及 $\lambda$ ）。我們不應該基於測試集（測試數據的集合）來決定模型複雜度，否則模型可能會直接對測試集過擬合，這無異於作弊。同樣由於過擬合的考慮，我們也不能基於訓練集（訓練數據的集合）來選擇超參數。我們取一個新的數據集，驗證集，來選擇模型超參數。當我們知道數據的真實分佈時，我們可以直接從分佈採集驗證集，否則我們可以把手上的數據集分成訓練集、驗證集或者訓練集、驗證集、測試集。

1.2 Probability Theory

動機：模式識別裡的一個關鍵概念是不確定性。不確定性的來源有兩個：測量的噪聲以及數據集大小有限。概率論提供了一種量化和操作不確定性的工具，是模式識別的根基之一。當我們同時運用概率論和決策論，我們可以基於給定信息做出最優預測，無論信息是否完整、明確。

如沒有特別強調，以下 $X,Y$ 均表示隨機變量。嚴格地說一個隨機變量 $X:\Omega\rightarrow E$ 是一個從樣本空間（sample space,潛在結果的集合） $\Omega$ 到可測空間（measurable space） $E$ 的可測函數（measurable function）。這涉及到測度論的知識，遠遠超出了本書對讀者數學知識的假設。鑑於我們這裡不追求嚴格的定義，可以認為一個隨機變量是一個可以從一個集合中取不同值的變量。

條件概率： $p$Y=y\_{j}\|X=X\_{i}$$ 表示已知 $X=X\_{i}$ 的情況下， $Y=y\_{j}$ 發生的概率，被稱為給定 $X=X\_{i}$ , $Y=y\_{j}$ 的條件概率。我們可以把這一定義拓展到給定多於一個條件的情況下如 $p$Y=y\_{j}\|X\_{1}=x\_{1,i}, X\_{2}=x\_{2,i},\cdots$$ 。

sum rule : $p$X$=\sum\_{Y}p$X, Y$$ ,這裡的 $p$X$$ 常被稱為邊際概率（marginal probability），因為它可經由取便其它變量（如 $Y$ ）的所有可能值時，計算 $X$ 與它們的聯合分佈的概率的總和來得到。

product rule : $p$X, Y$=P$Y\|X$P$X$$

symmetry property : $p$X,Y$=p$Y,X$$

基於product rule和symmetry property，我們可以得到大名鼎鼎的貝葉斯定理/公式（Bayes’ theorem）： $p$Y\|X$=\frac{p$X,Y$}{p$X$}=\frac{p$Y,X$}{p$X$}=\frac{p$X\|Y$ p$Y$}{p$X$}$ 。由sum rule, product rule和symmetry property可得 $p$X$=\sum\_{Y}p$X,Y$=\sum\_{Y}p$Y,X$=\sum\_{Y}p$X\|Y$p$Y$$ 。 $\sum\_{Y}p$Y\|X$=\sum\_{Y}\frac{p$X\|Y$p$Y$}{p$X$}=1$ 。因此上式中 $p$X$$ 可被看做使左邊取所有可能 $Y$ 值的條件概率之和為1的歸一化常數。

sum rule，product rule以及symmetry property像條件概率一樣可以被拓展到多於兩個隨機變量的情況。

貝葉斯定理的一個重要解釋涉及先驗概率（prior probability）和後驗概率（posterior probability）。通俗地講，先驗概率是我們一無所知的情況下根據經驗、常規情況計算的，後驗概率是在我們得到了新的信息情況下對先驗概率進行的修正，更加準確。我們可以考慮 $p$Y$$ 為 $Y$ 的先驗概率而 $p$Y\|X$$ 為知道 $X$ 後 $Y$ 的後驗概率。

獨立： $X, Y$ 為兩個隨機變量，如果 $p$X,Y$=p$X$p$Y$$ ，我們稱 $X$ 獨立於 $Y$ 且 $Y$ 獨立於 $X$ 或者 $X,Y$ 彼此獨立。注意這種情況下 $p$Y\|X$=\frac{p$X,Y$}{p$X$}=\frac{p$X$p$Y$}{p$X$}=p$Y$$ 。我們還會經常見到兩兩獨立（pairwise independence，一個隨機變量的集合中任取兩個隨機變量都彼此獨立）和彼此獨立（mutually independence，對於一個隨機變量的集合 $\{X\_{1},...,X\_{n}\}$ ，它們一起的聯合分佈概率等於它們各自的分佈概率之積: $p$X\_{1}=a\_{1},\cdots,X\_{n}=a\_{n}$=\prod\_{i=1}^{n}p$X\_{i}=a\_{i}$$ ）。

1.2.1 Probability densities

隨機變量有離散型和連續性兩種。離散型隨機變量定義在事件的離散集合上（如篩子的點數，硬幣的正反等等），連續型隨機變量定義在事件的連續集合上（如區間）。就像離散型隨機變量與概率質量函數（probability mass function）相關聯一樣，連續型隨機變量與概率密度函數（probability density function）相關聯。

a.概率密度函數 $p$x$$ 具有以下特點：

$p$x$\geq 0$ ;
$\int\_{-\infty}^{\infty}p$x$dx=1$ ;
$x$ 在 $a, b$ 的概率為 $p$x\in\(a,b$\)=\int\_{a}^{b}p$x$dx$ 。

b. 換元/變量選擇

給定 $x$ 的概率密度函數 $p\_{x}$x$$ ，令 $x=g$y$$ ，則有 $p\_{y}$y$=p\_{x}$x$\|\frac{dy}{dx}\|=p\_{x}$g\(y$\)\|g'$y$\|$ 。一個相關的結果是概率密度函數的最大值取決於變量的選擇。

c. 累積分佈函數（cumulative distribution function）

$x\in$-\infty,z$$ 的概率為 $P$z$=\int\_{-\infty}^{z}p$x$dx$ , $P$ 被稱為累積分佈函數。 $P'$x$=p$x$$ 。

d.多元分佈

考慮多個連續型隨機變量的聯合分佈。假設我們有 $D$ 個連續型隨機變量 $x\_{1},\cdots,x\_{D}$ ，我們可以用一個向量把它們“封裝”起來： $\mathbf{x}=$x\_{1},\cdots,x\_{D}$$ 使得 $p$\mathbf{x}$=p$x\_{1},\cdots,x\_{D}$$ 。如此得到的概率密度函數仍然要滿足a部分的特點。我們同樣也可以考慮離散型隨機變量和連續型隨機變量的聯合分佈。

1.2.2 期望（expectation）和協方差（covariance）

期望：函數 $f$x$$ 在概率分佈 $p$x$$ 下的平均值被稱為 $f$x$$ 的期望，用 $E\[f\]$ 表示。

對於離散型隨機變量， $\mathbb{E}\[f\]=\sum\_{x}p$x$f$x$$ ；
對於連續型隨機變量， $\mathbb{E}\[f\]=\int p$x$f$x$dx$ 。

給定概率分佈採集到的 $N$ 個數據點: $\{$x\_{1},f\(x\_{1}$\),\cdots, $x\_{N},f\(x\_{N}$\)\}$ ，我們可以近似計算 $\mathbb{E}\[f\]$ 的值為 $\mathbb{E}\[f\]\simeq \frac{1}{N}\sum\_{n=1}^{N}f$x\_{n}$$ 。由大數定理可知，隨著 $N\rightarrow\infty$ ，這一近似逼近 $\mathbb{E}\[f\]$ 。

當我們考慮多變量函數的期望時，我們可以在 $\mathbb{E}$ 右下角加一個下標表示關於哪個隨機變量取期望，如 $\mathbb{E}\_{x}\[f$\cdots,x,y,\cdots$\]$ 表示 $f$ 關於 $x$ 的期望。

條件期望（conditional expectation）： $f$x$$ 在條件概率分佈 $p$x\|y$$ 下的平均值被稱為 $f$x$$ 的條件期望，用 $\mathbb{E}\_{x}\[f$x$\|y\]$ 表示。

對於離散型隨機變量， $\mathbb{E}\_{x}\[f$x$\|y\]=\sum\_{x}p$x\|y$f$x$$ ；
對於連續型隨機變量， $\mathbb{E}\_{x}\[f$x$\|y\]=\int p$x\|y$f$x$dx$ 。

方差（variance）： $f$x$$ 的方差為 $Var\[f\]=\mathbb{E}\[$f\(x$-\mathbb{E}\[f$x$\]\)^{2}\]=\mathbb{E}\[f$x$^{2}- 2f$x$\mathbb{E}\[f$x$\]+\mathbb{E}\[f$x$\]^{2}\]=\mathbb{E}\[f$x$^{2}\]-\ mathbb{E}\[f$x$\]^{2}$ 。可以認為方差衡量了 $f$x$$ 在 $\mathbb{E}\[f$x$\]$ 附近的變化性。

協方差（covariance）：對於任意兩個隨機變量 $X,Y$ ，它們之間的協方差定義為 $cov\[x,y\]=\mathbb{E}\_{x,y}\[\{x-\mathbb{E}\[x\]\}\{y-\mathbb{E}\[y\]\}\]=\ mathbb{E}\_{x,y}\[xy-x\mathbb{E}\[y\]-y\mathbb{E}\[x\]+\mathbb{E}\[x\]\mathbb{E}\[y\]\] =\mathbb{E}\_{x,y}\[xy\]-\mathbb{E}\[x\]\mathbb{E}\[y\]$ ,它反映了 $x,y$ 一起變化的程度。

一個隨機變量與其本身之間的協方差等於其方差。
當 $X,Y$ 彼此獨立時， $cov\[X,Y\]=\mathbb{E}\_{X,Y}\[XY\]-\mathbb{E}\[X\]\mathbb{E}\[Y\]=\mathbb{E}\[X\]\mathbb{ E}\[Y\]-\mathbb{E}\[X\]\mathbb{E}\[Y\]=0$ 。
當 $\mathbf{x},\mathbf{y}$ 為兩個隨機變量的向量時，設 $\mathbf{x}$ 含有 $m$ 個元素， $\mathbf{y}$ 含有 $n$ 個元素 $cov\[\mathbf{x},\mathbf{y}\]=\mathbb{E}\_{x,y}\[\{x-\mathbb{E}\[x\]\}\{y^{T}-\ mathbb{E}\[y^{T}\]\}\]=\mathbb{E}\_{x,y}\[xy^{T}\]-\mathbb{E}\[x\]\mathbb{E}\[y^ {T}\]$ ，此時 $cov\[\mathbf{x},\mathbf{y}\]$ 實際上是一個 $m \times n$ 的矩陣，並且矩陣中第 $i$ 行的第 $j$ 個元素代表了 $\mathbf{x}\_{i}$ 和 $\mathbf{y}\_{j}$ 之間的協方差。
對於任意一個隨機變量的向量 $\mathbf{x}$ ， $cov\[\mathbf{x}\]\equiv cov\[\mathbf{x},\mathbf{x}\]$ 。