《PRML》笔记第一章

第一章引言

1. 一些机器学习基本概念的定义

General Process of Machine Learning

The result of running the machine learning algorithm can be expressed as a function $y(x)$ which takes a new digit image $x$ as input and that generates an output vector $y$ , encoded in the same way as the target vectors. The precise form of the function $y(x)$ is determined during the training phase, also known as the learning phase, on the basis of the training data. Once the model is trained it can then determine the identity of new digit images, which are said to comprise a test set.
Generalization

The ability to categorize correctly new examples that differ from those used for training is known as generalization.
- In practical applications, the variability of the input vectors will be such that the training data can comprise only a tiny fraction of all possible input vectors, and so generalization is a central goal in pattern recognition.
Pre-processing

For most practical applications, the original input variables are typically preprocessed to transform them into some new space of variables where, it is hoped, the pattern recognition problem will be easier to solve. This pre processing stage is sometimes also called feature extraction. Note that new test data must be pre-processed using the same steps as the training data.
Applications in Machine Learning
1. Supervised Learning
  
  Applications in which the training data comprises examples of the input vectors along with their corresponding target vectors are known as supervised learning problems.
  - Classification
    
    Cases such as the digit recognition example, in which the aim is to assign each input vector to one of a finite number of discrete categories, are called classification problems.
  - Regression
    
    If the desired output consists of one or more continuous variables, then the task is called regression.
2. Unsupervised Learning
  
  In other pattern recognition problems, the training data consists of a set of input vectors x without any corresponding target values.
  - Clustering
    
    The goal in such unsupervised learning problems may be to discover groups of similar examples within the data, where it is called clustering.
  - Density Estimation
    
    Determine the distribution of data within the input space.
  - Visualization
    
    Project the data from a high-dimensional space down to two or three dimensions for the purpose of visualization.
3. Reinforcement Learning
  
  The technique of reinforcement learning is concerned with the problem of finding suitable actions to take in a given situation in order to maximize a reward. Here the learning algorithm is not given examples of optimal outputs, in contrast to supervised learning, but must instead discover them by a process of trial and error. Typically there is a sequence of states and actions in which the learning algorithm is interacting with its environment. In many cases, the current action not only affects the immediate reward but also has an impact on the reward at all subsequent time steps.
  - Credit Assignment Problem
    
    A major challenge is that a game of backgammon can involve dozens of moves, and yet it is only at the end of the game that the reward, in the form of victory, is achieved. The reward must then be attributed appropriately to all of the moves that led to it, even though some moves will have been good ones and others less so.
  - Exploration & Exploitation
    
    A general feature of reinforcement learning is the trade-off between exploration, in which the system tries out new kinds of actions to see how effective they are, and exploitation, in which
    the system makes use of actions that are known to yield a high reward. Too strong a focus on either exploration or exploitation will yield poor results.
Validation Set & Test Set

We have already seen that, in the maximum likelihood approach, the performance on the training set is not a good indicator of predictive performance on unseen data due to the problem of over-fitting. If data is plentiful, then one approach is simply to use some of the available data to train a range of models, or a given model with a range of values for its complexity parameters, and then to compare them on independent data, sometimes called a validation set, and select the one having the best predictive performance. If the model design is iterated many times using a limited size data set, then some over-fitting to the validation data can occur and so it may be necessary to keep aside a third test set on which the performance of the selected model is finally evaluated.
Cross-validation
- 在数据量有限的情况下，交叉验证能够帮助我们尽可能地利用有限数据进行模型评估。数据量越小，交叉验证所对应的折数应越大。而对于数据极度缺乏的情况下，会将折数设置为样本数，也就是说，仅留一个样本用于验证，这种做法也被称为留一法。
- 交叉验证的缺点显而易见，就是计算量很大，因为需要跑S（折数）次。如果在超参数多的情况下结合网格搜索等调参方法，那么模型的运行次数会随着超参数数量的增加呈现指数级的增长。这对于一些本身训练时间较长的模型来说是非常耗时的。
This allows a proportion $(S −1)/S$ of the available data to be used for training while making use of all of the data to assess performance. When data is particularly scarce, it may be appropriate to consider the case $S = N$ , where $N$ is the total number of data points, which gives the leave-one-out technique.

2. 概率论知识点

2.1 离散型随机变量的概率运算法则

加法法则（全概率公式）： $p(X) = \sum\limits_{Y}p(X,Y)$
乘法法则： $p(X,Y) = p(Y|X)p(X)$
如果两个随机变量独立，则有：
$\begin{equation} \begin{gathered} p(X,Y) = p(X)p(Y)\\ p(Y|X) = p(Y) \end{gathered} \end{equation}$

2.2 贝叶斯公式（Bayes' theorem）

$p(Y|X) = \frac{p(X|Y)p(Y)}{p(X)}=\frac{p(X|Y)p(Y)}{\sum\limits_{Y}p(X,Y)}=\frac{p(X|Y)p(Y)}{\sum\limits_{Y}p(X|Y)p(Y)} \tag{1}$

其中， $p(Y)$ 称为先验概率（prior probability），而 $p(Y|X)$ 称为后验概率（Posterior probability）**，它可以看成是事件 $X$ 已经发生的情况下，经过事实修正后的概率。

We can view the denominator in Bayes’ theorem as being the normalization constant required to ensure that the sum of the conditional probability on the left-hand side of (1) over all values of Y equals one.

2.3 概率密度：对连续型随机变量的概率建模

假定 $x$ 落在区间 $(x,x+\delta x)$ 的概率为 $p(x)$ ，当 $\delta x \rightarrow 0$ 时，将 $p(x)$ 称为随机变量 $x$ 的概率密度。需要注意的是， $p(a)$ 并不能被简单地理解为随机变量等于 $a$ 时的概率，因为 $p(x)$ 在任意单点处概率都是趋于 $0$ 的。
$p(x)$ 需要满足的两条性质：
$\begin{equation} \begin{gathered} p(x)\ge0\\ \int_{-\infty}^{\infty}p(x)dx=1 \end{gathered} \end{equation}$
基于概率密度 $p(x)$ ， $x$ 落在区间 $(a,b)$ 中的概率可以表示为：
$p(x\in (a,b))=\int_a^b p(x)dx$
定义如下符号用于表示随机变量 $x$ 落在区间 $(-\infty,z)$ ，也就是 $x\le z$ 的概率：
$P(z) = \int_{-\infty}^zp(x)dx$
因此， $p(x\in (a,b))$ 也等价于 $P(b)-P(a)$ 。
随机变量代换的运算法则：设变量代换 $x=g(y)$ ，并分别定义 $p_x(x)$ 和 $p_y(y)$ 为 $x$ 和 $y$ 的概率密度，则 $p_x(x)$ 和 $p_y(y)$ 之间满足：

$\begin{equation} \begin{aligned} p_y(y)&=p_x(x)|\frac{dx}{dy}|\\ &=p_x(g(y))|g'(y)| \end{aligned} \end{equation}$

            $|\frac{dx}{dy}|$实际上就是雅可比行列式。

与离散型随机变量相类似，连续型随机变量的加法和乘法运算法则如下：
$\begin{equation} \begin{gathered} p(x) = \int p(x,y)dy\\ p(x,y) = p(y|x)p(x) \end{gathered} \end{equation}$

2.4 期望

设随机变量的函数 $f[x]$ ，随机变量的概率分布为 $p(x)$ ,则 $f(x)$ 的期望可以计算为：
$\begin{equation} \begin{gathered} \text{离散型:}\quad\mathbb{E}[f] = \sum\limits_x p(x)f(x)\\ \text{连续型:}\quad\mathbb{E}[f] = \int p(x)f(x)dx\\ \end{gathered} \end{equation}$
对于联合概率分布 $f(x,y)$ ，其关于 $x$ 的边缘期望可表示为 $\mathbb{E}_x[f(x,y)]$ ，它是一个关于 $y$ 的函数。
进一步地，还可以定义在条件概率分布下的函数期望如下：

$\mathbb{E}_x[f|y] = \sum_xp(x|y)f(x)$

2.5 方差

函数 $f(x)$ 的方差可以定义为：
$\text{var}[f] = \mathbb{E}[(f(x)-\mathbb{E}[f(x)])^2]$
可以通过推导得到如下计算方差的方法：
$\text{var}[f] = \mathbb{E}[f(x)^2]-\mathbb{E}[f(x)]^2$
与方法类似，定义两随机变量的协方差如下：
$\begin{equation} \begin{aligned} \text{cov}[x,y] &= \mathbb{E}_{x,y}[\{x-\mathbb{E}[x]\}\{y-\mathbb{E}[y]\}]\\ &=\mathbb{E}_{x,y}[xy]-\mathbb{E}[x]\mathbb{E}[y] \end{aligned} \end{equation}$
将其拓展到多元随机变量，则其协方差为一个矩阵：
$\begin{equation} \begin{aligned} \text{cov}[\mathbf{x},\mathbf{y}] &= \mathbb{E}_{\mathbf{x},\mathbf{y}}[\{\mathbf{x}-\mathbb{E}[\mathbf{x}]\}\{\mathbf{y}^\mathrm{T}-\mathbb{E}[\mathbf{y}^\mathrm{T}]\}]\\ &=\mathbb{E}_{\mathbf{x},\mathbf{y}}[\mathbf{xy^\mathrm{T}}]-\mathbb{E}[\mathbf{x}]\mathbb{E}[\mathbf{y}^\mathrm{T}] \end{aligned} \end{equation}$
其中 $\mathbf{x}$ 和 $\mathbf{y}$ 均为列向量。

2.6 频率学派 vs 贝叶斯学派

频率学派（frequentist interpretation）**观点：通过随机可重复时间的发生频率来定义相应的概率。

So far in this chapter, we have viewed probabilities in terms of the frequencies of random, repeatable events. We shall refer to this as the classical or frequentist interpretation of probability.
一些特殊的事件并没有办法重复地发生多次（例如南极洲消失），在这种情况下使用频率来定义概率的方法就不再适用。虽然这些事件仅发生了若干次甚至没有发生，我们依然可以基于一些先验知识估计其发生的概率。这就是贝叶斯（Bayesian）*****学派的观点，其想法是基于证据或是已观测到的事实来建模事件发生的不确定性*，其核心是基于贝叶斯公式：

$p(\mathbf{w}|\mathcal{D}) = \frac{p(\mathcal{D}|\mathbf{w})p(\mathbf{w})}{p(\mathcal{D})} \tag{2}$

在已经观测到数据集 $\mathcal{D}$ 的情况下评估 $\mathbf{w}$ 的不确定性，即 $p(\mathbf{w}|\mathcal{D})$ 。 $p(\mathbf{w})$ 称为先验概率（prior probability），可以理解为我们一开始就对 $\mathbf{w}$ 拥有的先验知识；而 $p(\mathbf{w}|\mathcal{D})$ 则被称为后验概率（posterior probability），它是观测到 $\mathcal{D}$ 之后，对 $p(\mathbf{w})$ 进行的修正。 $p(\mathcal{D}|\mathbf{w})$ 被称为似然函数（likelihood function）**，它表示给定不同的参数向量 $\mathbf{w}$ ，观测到数据集 $\mathcal{D}$ 的可能性。需要注意的是 $p(\mathcal{D}|\mathbf{w})$ 并不是一个关于 $\mathbf{w}$ 的概率分布，因为它关于 $\mathbf{w}$ 的积分不一定等于 $1$ 。
机器学习的任务是给定数据 $\mathcal{D}$ ，求解模型参数 $\mathbf{w}$ 。因此，基于(2)，我们可以得到如下结论：
$\text{后验概率}p(\mathbf{w}|\mathcal{D})\propto \text{似然函数} p(\mathcal{D}|\mathbf{w}) \times\text{先验概率}p(\mathbf{w}) \tag{8}$
而分母项 $p(\mathcal{D})$ 是一个关于 $\mathbf{w}$ 的常数，它可以被理解为一个标准化因子，目的是确保 $p(\mathbf{w}|\mathcal{D})$ 符合概率的性质（积分等于 $1$ ）。
似然函数在频率学派和贝叶斯学派中均扮演了重要的角色，但两者使用它的方式是截然不同的。
- 频率学派认为 $\mathbf{w}$ 是固定的参数，而数据集 $\mathcal{D}$ 的值是不确定的，因此频率学派希望借助一些基于 $\mathbf{w}$ 和 $\mathcal{D}$ 的度量来确定 $\mathbf{w}$ 的值。而似然函数 $p(\mathcal{D}|\mathbf{w})$ 就是其中一种被广泛使用的度量方法，通过寻找一个最合适的 $\mathbf{w}$ 来使得 $\mathcal{D}$ 出现的概率最大，以此确定 $\mathbf{w}$ 的值。
- 与频率学派不同，贝叶斯学派认为数据集只有一个（即观测到的 $\mathcal{D}$ ），因此 $\mathcal{D}$ 是固定的，而参数 $\mathbf{w}$ 是不确定的，利用概率分布对其建模。
- 引入先验知识从直观上讲是一件自然而然的事，这是贝叶斯学派的一个优势。例如，如果将一个硬币抛十次都是正面，从频率学派的角度，正面朝上的概率就是1，这显然是不符合事实的。而这样的判断就来自于我们对硬币有一个先验知识，因此贝叶斯角度能够帮助我们对概率有一个更精确的建模。但先验的选择往往不是一件容易的事，当先验选择得不好时，贝叶斯方法有很大的可能性会给出错误的结果，这也是贝叶斯学派的一个缺陷。

2.7 高斯分布

$\mathcal{N}\left(x \mid \mu, \sigma^{2}\right)=\frac{1}{\left(2 \pi \sigma^{2}\right)^{1 / 2}} \exp \left\{-\frac{1}{2 \sigma^{2}}(x-\mu)^{2}\right\}$

其中 $\mu$ 和 $\sigma^{2}$ 分别表示均值（mean）和方差（variance），定义 $\beta=1/\sigma ^2$ 代表精度（precision）**。高斯分布的函数图像如下所示：

高斯分布满足以下性质：
$\int \mathcal{N}\left(x \mid \mu, \sigma^{2}\right)dx=1$

$\mathbb{E}[x]=\int \mathcal{N}\left(x \mid \mu, \sigma^{2}\right)xdx=\mu$

$\mathbb{E}[x^2]=\int \mathcal{N}\left(x \mid \mu, \sigma^{2}\right)x^2dx=\mu^2+\sigma^2$

$\text{var}[x] = \mathbb{E}[x^2]-\mathbb{E}[x]^2=\sigma^2$

多元高斯分布的定义如下：
$\mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}, \boldsymbol{\Sigma})=\frac{1}{(2 \pi)^{D / 2}} \frac{1}{|\boldsymbol{\Sigma}|^{1 / 2}} \exp \left\{-\frac{1}{2}(\mathbf{x}-\boldsymbol{\mu})^{\mathrm{T}} \boldsymbol{\Sigma}^{-1}(\mathbf{x}-\boldsymbol{\mu})\right\} \tag{3}$
其中 $\mathbf{x}$ 和 $\boldsymbol{\mu}$ 是 $D$ 维列向量，而 $\boldsymbol{\Sigma}$ 是 $D\times D$ 维的协方差矩阵。 $|\boldsymbol{\Sigma}|$ 表示 $\boldsymbol{\Sigma}$ 的行列式。

2.7.1 使用极大似然估计进行参数求解

对于从高斯分布中独立同分布采样的多个样本，其联合概率表示为：
$p(\boldsymbol{\mathcal{x}}|\mu,\sigma^2)=\prod_{n=1}^{N} \mathcal{N}\left(x_{n} \mid \mu, \sigma^{2}\right) \tag{4}$
注意这里 $\boldsymbol{\mathcal{x}}$ 表示 $N$ 个独立同分布采样得到的一维样本构成的数据集，而不是一个 $N$ 维的样本， $N$ 维样本的概率见式(3)。

以一维高斯分布为例，通过极大化公式(4)来求解 $\mu$ 和 $\sigma^2$ 。为了简化运算，通常的做法是取公式(4)的对数函数进行计算，这样做的好处不仅在于能够简化运算，还有有效防止由于计算机精度的限制造成的精度下溢出（即类似于 $10 ^{-128}$ 被当成0的情况）：
$\mathrm{ln}\;p(\boldsymbol{\mathcal{x}}|\mu,\sigma^2)=-\frac{1}{2 \sigma^{2}} \sum_{n=1}^{N}\left(x_{n}-\mu\right)^{2}-\frac{N}{2} \ln \sigma^{2}-\frac{N}{2} \ln (2 \pi) \tag{5}$
其中 $x_{n}$ 表示第 $n$ 个样本。关于 $\mu$ 极大化式(5)，有
$\mu_{ML} = \frac{1}{N}\sum\limits_{n=1}^Nx_n \tag{17}$
$\mu_{ML}$ 被称为样本均值。而关于 $\sigma^2$ 极大化式(5)，有
$\sigma^2_{ML} =\frac{1}{N}\sum\limits_{n=1}^N(x_n-\mu_{ML})^2$
$\sigma_{ML}^2$ 称为样本方差。需要注意的是，我们实际上是需要基于式(5)联合求解 $\mu_{ML}$ 和 $\sigma_{ML}^2$ 的，而之所以能够将他们解耦为两个单独的步骤，是因为 $\mu_{ML}$ 的求解不依赖于 $\sigma_{ML}^2$ 。

这样基于样本数据利用极大似然估计方法求解得到的方差距离随机变量的真实方差实际上是有差距的，具体来说， $\mu_{ML}$ , $\sigma^2_{ML}$ , $\mu$ 和 $\sigma^2$ 之间有如下关系：
$\mathbb{E}[\mu_{ML}]=\mu$

$\mathbb{E}[\sigma^2_{ML}] = (\frac{N-1}{N})\sigma^2 \tag{6}$

式(6) 推导如下：

首先证明引理： $\mathbb{E}[x_nx_m] = \mu^2+I_{nm}\sigma^2$ ，其中 $I_{nm}$ 为指示变量，如果 $n=m$ , $I_{nm}=0$ ，否则等于 $1$ ：

当 $n\neq m$ ， $p[x_n,x_m] = p(x_n)p(x_m)$ ，因此有
$\mathbb{E}[x_nx_m] = \int\int x_nx_mp(x_n)p(x_m)dx_ndx_m=\mu^2$
当 $n= m$ ， $p[x_n,x_m] = p(x_n)$ ，因此有
$\mathbb{E}[x_nx_m] = \int\int x_nx_mp(x_n,x_m)dx_ndx_m=\int x_n^2p(x_n)dx_n=\mu^2+\sigma^2$
综上， $\mathbb{E}[x_nx_m] = \mu^2+I_{nm}\sigma^2$ 。

接下来，利用如上结论证明式(6)：
$\begin{equation} \begin{aligned} \mathbb{E}[\sigma^2_{ML}] &= \mathbb{E}[\frac{1}{N}\sum\limits_{n=1}^N(x_n-\mu_{ML})^2]\\ & = \frac{1}{N}\sum\limits_{n=1}^N\{\mathbb{E}[x_n^2]-2\mathbb{E}[x_n\frac{1}{N}\sum\limits_{m=1}^Nx_m]+\frac{1}{N^2}\mathbb{E}[\sum\limits_{i=1}^N\sum\limits_{j=1}^Nx_ix_j]\}\\ & = \frac{1}{N}\sum\limits_{n=1}^N\{\mathbb{E}[x_n]^2+\text{var}[x_n]-\frac{2}{N}\sum\limits_{m=1}^N\mathbb{E}[x_nx_m]+\frac{1}{N^2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\mathbb{E}[x_ix_j]\}\\ & = \frac{1}{N}\sum\limits_{n=1}^N\{\mathbb{E}[x_n]^2+\text{var}[x_n]-\frac{2}{N}\sum\limits_{m=1}^N\mathbb{E}[x_nx_m]+\frac{1}{N^2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\mathbb{E}[x_ix_j]\}\\ & = \frac{1}{N}\sum\limits_{n=1}^N\{\mu^2+\sigma^2-\frac{2}{N}(N\mu^2+\sigma^2)+\frac{1}{N^2}\sum\limits_{i=1}^N(N^2\mu^2+N\sigma^2)\}\\ & = \frac{1}{N}\sum\limits_{n=1}^N\{\sigma^2-\frac{1}{N}\sigma^2\}\\ & = \frac{N-1}N{\sigma^2} \end{aligned} \end{equation}$

可以看到， $\sigma^2_{ML}$ 实际上低估（underestimate）了真实方差，但当 $N$ 足够大时，两者的差距将逐渐缩小，直至逼近。

2.7.2 基于高斯分布进行曲线拟合（频率角度）

给定数据集 $\boldsymbol{\mathcal{x}} = (x_1, x_2, \dots, x_N)$ 以及他们对应的标签 $\mathbf{t} = (t_1, t_2, \dots, t_N)$ 。回忆前文中提过的，频率学派假定参数是固定的，而数据是随机变量，服从某种分布。因此，如果假定样本标签 $t$ 符合高斯分布，则有：
$p(t|x,\mathbf{w},\beta) = \mathcal{N}(t|y(x,\mathbf{w}),\beta^{-1}) \tag{7}$
其中 $y(x,\mathbf{w})$ 表示给定样本x的情况下，标签t分布的均值，它实际上也就是 $x$ 基于模型参数 $\mathbf{w}$ 得到的预测标签。因此，曲线拟合的问题转化为求解参数 $\mathbf{w}$ 和 $\beta$ 。下图说明了公式(7)中给定x的条件下t的概率分布：

因此，在给定训练数据 $\{\boldsymbol{x},\mathbf{t}\}$ 的情况下，假定数据均为独立采样得到的，则有：
$p(\mathbf{t}|\boldsymbol{x},\mathbf{w},\beta) = \prod_{n=1}^N \mathcal{N}(t_n|y(x_n,\mathbf{w}),\beta^{-1}) \tag{9}$
与前文类似，首先求得其对数似然函数：
$\ln \;p(\mathbf{t}|\boldsymbol{x},\mathbf{w},\beta)=-\frac{\beta}{2}\sum\limits_{n=1}^N\{y(x_n,\mathbf{w})-t_n\}^2+\frac{N}{2}ln\;\beta-\frac{N}{2}ln\;(2\pi)$
参数 $\mathbf{w}$ 的求解仅与第一项有关，最大化第一项等价于最小化 $\sum\limits_{n=1}^N\{y(x_n,\mathbf{w})-t_n\}^2$ ，由此可以得知，如果假设数据服从高斯分布，求解其对数似然函数可以导出平方误差以及均方误差函数。同样地，基于前两项，可以得到参数 $\beta$ 的解：
$\frac{1}{\beta_{ML}} = \frac{1}{N}\sum_{n=1}^N\{y(x_n,\mathbf{w}_{ML})-t_n\}^2$
在确定了模型参数 $\mathbf{w}_{ML}$ 和 $\beta$ 后，给定一个新样本 $x$ ，可以求得其标签 $t$ 的概率分布：
$p(t|x,\mathbf{w}_{ML},\beta_{ML}) = \mathcal{N}(t|y(x,\mathbf{w}_{ML}),\beta_{ML}^{-1})$
进一步地，如果假定 $\mathbf{w}$ 不固定，我们可以参考贝叶斯方法，对 $\mathbf{w}$ 引入先验。例如，对于一个M维参数向量 $\mathbf{w}$ ^[1]，假定其符合如下形式的高斯分布：
$p(\mathbf{w}|\alpha) =\mathcal{N}(\mathbf{w}|\mathbf{0},\alpha^{-1}\mathbf{I}) = (\frac{\alpha}{2\pi})^{(M+1)/2}\;\text{exp}\{-\frac{\alpha}{2}\mathbf{w}^\mathrm{T}\mathbf{w}\} \tag{10}$

为简单起见，上式假定 $\mathbf{w}$ 的对应的高斯分布的均值为 $0$ ，而方差由超参数 $\alpha$ 控制。

结合结论(8)，有
$p(\mathbf{w}|\boldsymbol{x},\mathbf{t},\alpha,\beta)\propto p(\mathbf{t}|\boldsymbol{x},\mathbf{w},\beta)\times p(\mathbf{w}|\alpha) \tag{11}$
由此，我们可以通过最大化 $\mathbf{w}$ 的后验概率 $p(\mathbf{w}|\boldsymbol{x},\mathbf{t},\alpha,\beta)$ 来求解参数 $\mathbf{w}$ ，我们称这种方法为MAP(maximum posterior)。结合式(9)，式(10)和式(11)，对 $p(\mathbf{w}|\boldsymbol{x},\mathbf{t},\alpha,\beta)$ 求解关于 $\mathbf{w}$ 的对数似然函数，有：
$\begin{equation} \begin{gathered} \max_{\mathbf{w}} -\frac{\beta}{2}\sum\limits_{n=1}^N\{y(x_n,\mathbf{w})-t_n\}^2-\frac{\alpha}{2}\mathbf{w}^\mathrm{T}\mathbf{w}\\ \Rightarrow \min_{\mathbf{w}} \frac{\beta}{2}\sum\limits_{n=1}^N\{y(x_n,\mathbf{w})-t_n\}^2+\frac{\alpha}{2}\mathbf{w}^\mathrm{T}\mathbf{w} \end{gathered} \tag{12} \end{equation}$
式(12)可以看成是平方损失函数加上一个正则化项 $\mathbf{w}^\mathrm{T}\mathbf{w}$ ，参数 $\alpha$ 和 $\beta$ 权衡了两者的相对关系。正则化项 $\frac{\alpha}{2}\mathbf{w}^\mathrm{T}\mathbf{w}$ 实际上是由加入的先验 $p(\mathbf{w}|\alpha)$ 导出的，根据先验的不同，最后的到的正则化项也会不同**。

2.7.3 从贝叶斯角度进行曲线拟合

尽管在上一节的最后，MAP方法引入了 $\mathbf{w}$ 的先验，但它并不能算作一个贝叶斯方法。因为在⼀个纯粹的贝叶斯⽅法中，我们应该自始至终地运用概率的加法法则和乘法法则，这需要我们对 $\mathbf{w}$ 所有的取值进行积分。具体来说，给定了训练集 $\{\boldsymbol{x},\mathbf{t}\}$ ，假设参数 $\alpha$ 和 $\beta$ 已固定，对于一个新样本 $\hat{x}$ ，有
$p(t|\hat{x},\boldsymbol{x},\mathbf{t}) = \int p(t|\hat{x},\mathbf{w})p(\mathbf{w}|\boldsymbol{x},\mathbf{t})d\mathbf{w}$
其中 $p(t|\hat{x},\mathbf{w})$ 可以由式(9)求得，后验概率 $p(\mathbf{w}|\boldsymbol{x},\mathbf{t})$ 可以由式(11)求得。上式积分将在后续章节中推导得到解析解。

下图展示了一个使用贝叶斯方法处理曲线拟合的例子。可以看到，使用贝叶斯方法预测得到的模型并不是固定的，只能得到模型参数的一个概率分布。

2.7.4 三种方法的比较

纯粹的频率角度：通过最大化似然函数 $p(t|x,\mathbf{w},\beta) = \mathcal{N}(t|y(x,\mathbf{w}),\beta^{-1})$ 求解参数；
MAP：最大化 $\mathbf{w}$ 的后验概率 $p(\mathbf{w}|\boldsymbol{x},\mathbf{t},\alpha,\beta)$ 来求解参数；
纯粹的贝叶斯方法：通过预测概率 $p(t|\hat{x},\boldsymbol{x},\mathbf{t})$ 求解问题。

3. 决策论知识点

模式识别问题可以大致分为推断（inference）和决策（decision）两个子问题。推断问题是指基于给定的训练数据集，学习到一个能够表征概率分布 $p(\mathcal{C}_k|\mathbf{x})$ （或 $p(\mathcal{C}_k,\mathbf{x})$ ）的模型。而决策问题则是基于学习到的模型或者说概率分布，将新样本指派到最合适的类别。推断问题是本书关注的重点，将在后续章节详细介绍。而本节关注于决策问题，介绍在决策过程中常用的准则。

3.1 最小化错分率（misclassification rate）

首先假设一个很简单的目标，我们的目标仅仅是尽可能地降低错分率。我们需要一个准则来把每个x划分到一个合适的类别，这样的规则会将输入空间切分成不同的区域 $\mathcal{R}_k$ ，这种区域也被称为决策区域（decision region）。一种类别对应了一个区域，换言之，类别 $\mathcal{C}_k$ 就对应区域 $\mathcal{R}_k$ 。每个区域未必是连续的，它们可以由若干个分离的区域共同构成。而不同的区域之间的边界被称为决策边界（decision boundaries）或是决策面（decision surfaces）。确定准则的过程可以理解为确定决策边界的过程。

下面首先考虑最简单的二分类情况，我们希望通过最小化错分率来设定分类准则。对于二分类，错分的情况出现在本应属于第一类的样本被误分到第二类，以及本应属于第二类的样本被误分到第一类这两种情况。因此，错分的可能性可以表示为：
$\begin{equation} \begin{aligned} p(\text{mistake}) &= p(x\in\mathcal{R}_1,\mathcal{C}_2)+p(x\in\mathcal{R}_2,\mathcal{C}_1)\\ &= \int_{\mathcal{R}_1}p(x,\mathcal{C}_2)dx+\int_{\mathcal{R}_2}p(x,\mathcal{C}_1)dx \end{aligned} \tag{13} \end{equation}$
为了最小化错分的可能性，我们应该使得上式的被积函数尽可能小。例如，如果对样本x，有 $p(x,\mathcal{C}_1)>p(x,\mathcal{C}_2)$ ，那么我们应该将其划分给第 $1$ 类，因为在这种情况下，它的错分可能性为 $p(x,\mathcal{C}_2)$ ，是尽可能小的那一方。而回到这个不等式 $p(x,\mathcal{C}_1)>p(x,\mathcal{C}_2)$ ，根据乘法规则，在不等式两边同时消去 $p(x)$ 后，我们可以得到 $p(\mathcal{C}_1|x)>p(\mathcal{C}_2|x)$ ，换句话说，在给定样本数据后，我们应该将其划分给可能性最大的那一类^[2]。下图对(13)的决策规则做了一个图形化说明。

进一步拓展到多分类情况，此时考虑错分的情况过于复杂，考虑正确分类的情况相对更简单，因此分类准则变为最大化正确分类的可能性：
$\begin{equation} \begin{aligned} p(\text{correct}) &= \sum\limits_kp(x\in\mathcal{R}_k,\mathcal{C}_k)\\ &= \sum\limits_k\int_{\mathcal{R}_k}p(x,\mathcal{C}_k)dx \end{aligned} \label{eq:max_correct_rate} \end{equation}$
因此和前文类似，对于新来的样本，只需要将其划分到使得 $p(\mathcal{C}_k|x)$ 最大的第 $k$ 类即可。

3.2 最小化期望损失（expected loss）

在现实生活中，我们可能有比单纯最小化错分率更加复杂的目标。例如，在癌症诊断中，误诊（将实际健康的病人诊断为患癌）和漏诊（将癌症病人诊断为健康）都属于错分的情况。对于前者，健康的病人再进行一次检查并不会对生活带来太大的影响。而后者却可能延误患者的治疗时机，造成重大的生命财产损失。因此我们会更加关注后者，希望尽可能减少出现后者的几率，哪怕由于少犯第二种错误，而导致第一种错误增加也没关系。

我们可以通过损失函数（loss function）来形式化地描述这个问题，损失函数也被称为代价函数（cost function）。注意在这个问题背景下我们希望的是最小化整体的损失。而如果要最大化目标，则对应的函数被称为效用函数（utility function）。以癌症诊断为例，我们可以通过如下损失矩阵 $L$ 来定义这样一个准则。对于分类正确的情况，我们将损失设置为0，如果健康的就诊者被误诊为患癌，则损失为1，而对于我们最关注的癌症患者被漏诊的情况，我们将损失设置为1000。

	健康	患病
健康	0	1000
患病	1	0

该损失矩阵依赖于真实标签，但是对于一个新样本，我们并不能知道它的真实标签是什么。我们知道的只有分布 $p(x,\mathcal{C}_k)$ 。因此，我们可以转而针对这个联合概率分布去最小化它的期望损失（expected loss），即
$\mathbb{E}[L] = \sum\limits_k\sum\limits_j \int_{\mathcal{R}_j}L_{kj}\;p(x,\mathcal{C}_k)dx = \sum\limits_j \int_{\mathcal{R}_j}\sum\limits_kL_{kj}\;p(x,\mathcal{C}_k)dx \tag{15}$
其中 $L_{kj}$ 代表原本属于第 $k$ 类的样本被错分为第 $j$ 类的代价。而与最小化错分率类似，为了最小化上式，我们需要最小化被积函数 $\sum\limits_kL_{kj}p(x,\mathcal{C}_k)$ 。也就是说，对于一个新来的样本 $x$ ，我们只需要将其划分到使得如下目标最小的类别 $j$ ：
$\begin{equation} \begin{gathered} \min_j\sum\limits_kL_{kj}\;p(x,\mathcal{C}_k)\\ \Leftrightarrow\min_j\sum\limits_kL_{kj}\;p(\mathcal{C}_k|x)\;p(x)\\ \Leftrightarrow\min_j\sum\limits_kL_{kj}\;p(\mathcal{C}_k|x) \end{gathered} \tag{14} \end{equation}$

3.3 拒绝选项

当我们发现误分类的概率 $p(\mathcal{C}_k|x)$ 远小于1，或者不同类别之间的概率 $p(\mathcal{C}_k|x)$ 十分接近时（例如对于二分类问题样本属于第一类的概率是0.51，而属于另一类的概率是0.49），样本的类别归属是比较难确定的。这种情况下，也许避免让模型进行决策，而留给人类去完成可能是更好的选择。例如在医疗诊断中，如果模型难以区分受试者是否患病，那么最好的办法转给医生去判别。为了能够做到这一点，我们可以对后验概率 $p(\mathcal{C}_k|x)$ 设定一个阈值 $\theta$ ，当 $p(\mathcal{C}_k|x)$ 的最大值小于 $\theta$ 时，模型会拒绝识别该样本。需要注意的是，当我们将 $\theta$ 设为大于等于 $1$ 的数时，会使得模型拒绝所有的样本。而将 $\theta$ 设置为 ${1}/{K}$ （ $K$ 为类别总数）以下会使得所有的样本均被模型接受。

阈值\theta可以很容易地推广到最小化期望损失上。由(14)，设 $m=\arg\min\limits_j\sum\limits_kL_{kj}\;p(\mathcal{C}_k|x)$ ，则可知 $p(\mathcal{C}_m|x)$ 必定是 $p(\mathcal{C}_k|x)(k=1,\dots,K)$ 中的最大值。因此，如果 $p(\mathcal{C}_m|x)$ 大于 $\theta$ ，则将样本划分到第 $m$ 类，否则拒绝该样本。

3.4 推断和决策

在本节一开始我们提到模式识别问题可以大致分为推断和决策两个阶段。在推断阶段，我们基于训练数据学习 $p(\mathcal{C}_k|x)$ 或 $p(\mathcal{C}_k,x)$ ，而在决策阶段，我们基于决策论的知识使用后验概率来进行最优的分类。事实上，根据推断和决策的处理方式不同，现有的方法可以分为以下三类：

（1）生成式模型首先对于每个类别 $\mathcal{C}_k$ ，独立地确定类条件密度 $p(x|\mathcal{C}_k)$ （推断问题），接着基于数据集推断先验概率 $p(\mathcal{C}_k)$ 。之后，使用贝叶斯定理
$p(\mathcal{C}_k|x) = \frac{p(x|\mathcal{C}_k)p(\mathcal{C}_k)}{\sum_j p(x|\mathcal{C}_j)p(\mathcal{C}_j)} \label{eq:gen_model}$
求出后验概率 $p(\mathcal{C}_k|x)$ 。也有另一种做法是直接求联合概率分布 $p(\mathcal{C}_k,x)$ （推断问题），然后基于贝叶斯定理归一化得到后验概率。这种做法成为生成式模型的原因是因为可以通过取样人工生成新的输出空间的数据点。

（2）判别式模型 则是直接解决 $p(\mathcal{C}_k|x)$ 这一推断问题。接下来再使用决策论的知识对新输入的 $x$ 进行分类。

（3）判别函数与前两者不同，这类方法通过基于训练数据学习出一个函数 $f(x)$ ，将输入的数据直接映射成类别标签，从而同时解决两个问题。函数 $f(x)$ 被称为判别函数（discriminant function）。

上述三种方法的复杂度是逐级递减的。生成式模型需要求解的东西最多，因为该方法涉及寻找 $x$ 和 $\mathcal{C}_k$ 的联合概率分布。如果 $x$ 的维度很高，我们需要大量的训练数据才能在合理的精度下确定类条件概率。而先验概率 $p(\mathcal{C}_k)$ 经常是根据训练数据中各类别的比例得到的。但是生成式模型多个优点，其中一个就是能够人工生成新的数据，还有一个优点是它能够得到边缘概率密度p(x)，对于一些低概率的数据点，模型对它们的预测准确度可能会很低，生成式模型能够将它们检测出来，这类应用被称为离群点检测（outlier detection）或是异常检测（novelty detection）。

对于生成式模型，为了求出后验概率，我们需要先求得类条件概率，而实际上类条件密度包含了很多对后验概率几乎没有影响的结构。如下图所示，假定类先验概率 $p(\mathcal{C}_k)$ 相同的情况下，左边是类条件概率，而右边是后验概率，可以看到类条件概率的峰值对于后验概率分布是没有影响的。如果我们只是想要进行分类的决策，那么直接求后验概率即可。此时，使用判别式模型能够节省计算资源。

使用判别函数的方法最简单，基于训练数据直接就可以把 $x$ 映射到对应的类别上，这种方法无需计算概率。但是这种方法最大的问题就是我们不再能够接触到后验概率 $p(\mathcal{C}_k|x)$ 了。实际应用中有很多理由需要我们保留后验概率，例如：

在最小化风险时，我们引入了损失矩阵。实际应用中可能出现损失矩阵时时刻刻被修改的例子（例如金融应用），如果使用判别函数的方法，对于不同的损失矩阵，需要重新训练函数以适应规则。但有了后验概率，只需要修改决策 $\sum\limits_kL_{kj}\;p(\mathcal{C}_k|x)$ 中对应的 $L_{kj}$ 即可。
判别函数没有办法引入拒绝标准。无论该样本是不是难以分类，判别函数都只能生硬地将它分到某一个类别。而如果给定了拒绝数据点所占的比例，后验概率就能够让我们确定最小化风险的拒绝标准。
基于贝叶斯公式，我们可以通过补偿类先验概率缓解类不平衡数据集所带来的问题。
对于一些多源的数据，我们可以通过分解的方式将其分解为多个后验概率的乘积，而不是将其全部集中到一个高维的输入空间。例如，考虑两个数据来源 $x_A$ ， $x_B$ ，假设对于每个类别 $\mathcal{C}_k$ ， $x_A$ 和 $x_B$ 是独立的，则有
$p(x_A,x_B|\mathcal{C}_k)=p(x_A|\mathcal{C}_k)\;p(x_B|\mathcal{C}_k)$
则后验概率可以通过如下方式分解：
$\begin{equation} \begin{aligned} p(\mathcal{C}_k|x_A,x_B) &\propto p(x_A,x_B|\mathcal{C}_k)\;p(\mathcal{C}_k)\\ &\propto p(x_A|\mathcal{C}_k)\;p(x_B|\mathcal{C}_k)\;p(\mathcal{C}_k)\\ &\propto \frac{p(\mathcal{C}_k|x_A) p(\mathcal{C}_k|x_B)}{p(\mathcal{C}_k)} \end{aligned} \end{equation}$
这样的分解，能够降低模型的复杂度。

3.5 用于回归模型的损失函数

有了分类问题的基础，接下来介绍如何解决回归模型中的决策问题。回归模型的决策关键在于对每个输入 $x$ ，确定一个对 $t$ 的具体的估计 $y(x)$ 。和式(15)类似，我们可以引入损失函数，通过最小化期望损失的方法来为输入数据 $x$ 确定合适的估计：
$\mathbb{E}[L] = \int\int L(t,y(x))p(x,t)dxdt$
一个常用的损失函数是 $L(t,y(x)) = \{y(x)-t\}^2$ ，此时期望损失变为
$\mathbb{E}[L] = \int\int \{y(x)-t\}^2p(x,t)dxdt$
我们的目标是通过选取合适的 $y(x)$ 来最小化 $\mathbb{E}[L]$ ，这个问题可以形式化地通过变分法求解：
$\begin{equation} \begin{gathered} \frac{\delta \mathbb{E}[L]}{\delta y(x)}=\int 2\{y(x)-t\}p(x,t)dt=0\\ \Rightarrow y(x) = \frac{\int tp(x,t)dt}{\int p(x,t)dt}=\frac{\int tp(x,t)dt}{p(x)} = \int tp(t|x)dt = \mathbb{E}_t[t|x] \end{gathered} \end{equation}$
在获得这个结果之后，我们对 $\mathbb{E}[L]$ 做一些变换，从而进一步了解回归问题的本质：
$\begin{equation} \begin{aligned} \mathbb{E}[L] &= \int\int \{y(x)-t\}^2p(x,t)dxdt\\ &= \int\int \{y(x)-\mathbb{E}_t[t|x]+\mathbb{E}_t[t|x]-t\}^2p(x,t)dxdt\\ &=\int\int \{y(x)-\mathbb{E}_t[t|x]\}^2p(x,t)dxdt+\int\int 2\{y(x)-\mathbb{E}_t[t|x]\}\{\mathbb{E}_t[t|x]-t\}p(x,t)dxdt+\int\int \{\mathbb{E}_t[t|x]-t\}^2p(x,t)dxdt\\ &=\int \{y(x)-\mathbb{E}_t[t|x]\}^2p(x)dx+\int \text{var}[t|x]p(x)dx \end{aligned} \end{equation}$

最后一步的推导过程如下：

第一项显然。

下面证明第二项等于零：
$\begin{equation} \begin{aligned} &\int \{y(x)-\mathbb{E}_t[t|x]\}\{\mathbb{E}_t[t|x]-t\}p(x,t)dt\\ =&\{y(x)-\mathbb{E}_t[t|x]\}\int \{\mathbb{E}_t[t|x]-t\}p(x,t)dt\\ =&\{y(x)-\mathbb{E}_t[t|x]\}\{\int\mathbb{E}_t[t|x]p(x,t)dt-\int tp(x,t)dt\}\\ =&\{y(x)-\mathbb{E}_t[t|x]\}\{p(x)\mathbb{E}_t[t|x]-\int tp(x)\frac{p(x,t)}{p(x)}dt\}\\ =&\{y(x)-\mathbb{E}_t[t|x]\}\{p(x)\mathbb{E}_t[t|x]-p(x)\int t{p(t|x)}dt\}\\ =&\{y(x)-\mathbb{E}_t[t|x]\}\{p(x)\mathbb{E}_t[t|x]-p(x)\mathbb{E}_t[t|x]\}\\ =&\{y(x)-\mathbb{E}_t[t|x]\}\{0\}\\ =&0 \end{aligned} \end{equation}$
接下来推导最后一项：
$\begin{equation} \begin{aligned} &\int \{\mathbb{E}_t[t|x]-t\}^2p(x,t)dt\\ =&\int \{\mathbb{E}_t[t|x]\}^2p(x,t)dt-2\int t\mathbb{E}_t[t|x]p(x,t)dt+\int t^2p(x,t)dt\\ =&\{\mathbb{E}_t[t|x]\}^2p(x)-2\{\mathbb{E}_t[t|x]\}^2p(x)+\mathbb{E}_t[t^2|x]p(x)\\ =&\mathbb{E}_t[t^2|x]p(x)-\{\mathbb{E}_t[t|x]\}^2p(x)\\ =&\text{var}[t|x]p(x) \end{aligned} \end{equation}$

需要注意的是，平方损失并不是回归问题的损失函数的唯一选择。事实上，在一些情况下，平方损失的效果很差。除了平方损失外，还可以考虑它的推广形式：
$\mathbb{E}[L_q] = \int\int |y(x)-t|^qp(x,t)dxdt$
该函数被称为闵可夫斯基损失函数（Minkowski Loss），当 $q$ 等于 $2$ 时，闵可夫斯基损失退化成平方损失，而最优的估计 $y(x)$ 也已经求得是 $t$ 的条件均值。而在 $q=1$ 和 $q\rightarrow 0$ 时，其对应的最优估计分别是 $t$ 的条件中位数和条件众数。

与分类问题类似，对于回归问题，同样有生成式模型，判别式模型以及判别函数三种不同的解决方式。他们之间的区别和分类问题类似，因此不再赘述。

4. 信息论知识点

⾸先考虑⼀个离散的随机变量 $x$ 。当我们观察到这个变量的⼀个具体值的时候，我们接收到了多少信息呢？信息量可以被看成在学习 $x$ 的值的时候的“惊讶程度”。如果我们知道，某件事一定会发生，那么我们就接收不到什么信息。而如果一件相当不可能的事件发生了，那么我们收到的信息就会多于我们被告知某个很可能发生的事件发生时收到的信息。

4.1 信息量

如果用概率分布 $p(x)$ 来衡量事件发生的可能性，我们希望寻找一个函数 $h(x)$ 来衡量信息量，那么根据前文假设， $h(x)$ 应该是一个关于 $p(x)$ 的单调递减函数。除此之外，我们要求 $h(x)$ 能够满足以下性质：如果有两个不相关的事件x和y，那么我们观察到两个事件同时发生时获得的信息量应该等于观察事件各自发生时所获得的信息量之和，即 $h(x,y) = h(x)+h(y)$ 。而对于不相关的事件本身，有 $p(x,y) = p(x)p(y)$ 。根据这两个式子，可以很容易地推断出 $h(x)$ 的表达式与 $p(x)$ 的对数有关。因此，我们有
$h(x) = -\log_2 p(x) \tag{16}$
其中符号是为了确保信息量 $h(x)$ 恒大于等于 $0$ 。可以看到，信息量 $h(x)$ 关于 $p(x)$ 是递减的，也就是说，低概率事件对应了更高的信息量。 $h(x)$ 的底数可以是任意的，信息论中一般取作 $2$ ，接下来我们将看到，此时 $h(x)$ 的单位是比特(bit)，即对应信息的平均编码长度。

4.2 离散型变量的信息熵——离散熵

假设如果一个发送者想要传输一个随机变量的值给接收者。这个过程中，他们传输的平均信息量 $H[x]$ 可以通过求解式(16)关于概率分布 $p(x)$ 的期望得到，即
$H[x] = \mathbb{E}_x[h(x)]=\sum_x -p(x)\;\log_2 p(x)$
这个期望值也被称为随机变量 $x$ 的信息熵（entropy）。注意，由于 $\lim_{p(x)\rightarrow 0}p(x)log_2p(x)=0$ ，因此当 $p(x)=0$ 时，我们令 $p(x)log_2p(x)=0$ 。除此之外，还需要注意区分信息量 $h(x)$ 和信息熵 $H[x]$ 的符号上的区别，前者表示的是事件 $x$ 发生后我们所能获得的信息量，而后者则是在信息量 $h(x)$ 的基础上，我们对整体的信息传输过程中平均信息量的一个估计。

熵的最早概念起源于物理学，它被用作描述对统计学中无序程度的度量。

接下来举例说明以 $2$ 为底的信息熵在信息传输中的物理意义。考虑一个随机变量 $x$ ，它有 $8$ 种可能的状态 $\{a,b,c,d,e,f,g,h\}$ 。假设这8种状态符合均匀分布（uniform distribution），即每种状态出现的概率是相同的。我们可以用 $3$ 个比特位来表示这 $8$ 种状态，即 $\{000, 001, 010, \dots, 111\}$ 。而计算其信息熵也可得
$H[x] = 8\times (-\frac{1}{8}\text{log}_2 \frac{1}{8}) = 3 \text{bits}$
而如果假设这8种状态并不符合均匀分布，其概率分布为 $\{\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{64}, \frac{1}{64}, \frac{1}{64}, \frac{1}{64}\}$ 。则计算对应的信息熵可得
$H[x] = -\frac{1}{2}\text{log}_2\frac{1}{2}-\frac{1}{4}\text{log}_2\frac{1}{4}-\frac{1}{8}\text{log}_2\frac{1}{8}-\frac{1}{16}\text{log}_2\frac{1}{16}-\frac{4}{64}\text{log}_2\frac{1}{64}=2\text{bits}$
可以由这个例子看出，非均匀分布所具有的信息熵小于均匀分布的信息熵。前面说过信息熵对应的事平均编码长度，而为了能够得到两比特的平均编码长度，我们可以使用下面的编码串： $0,10,110,1110,111100,111101,111110,111111$ 。则平均的编码长度为
$\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{16}\times 4+\frac{4}{64}\times 6=2\text{bits}$
事实上，根据无噪声编码定理（noiseless coding theorem）可以得出如下结论：熵是传输一个随机变量状态值平均所需比特位的下界。

接下来把熵的底换成 $e$ ，这样做更便于我们将熵的概念与书的后续章节相结合。在这种情况下，熵的单位变成了nat，而非bit。对于离散变量，熵的定义为：
$H[x] =\sum_x -p(x)\;\ln p(x)$

4.3 连续型变量的信息熵——微分熵

而对于连续型变量同样可以定义熵，此时的熵称为微分熵（differential entropy）：
$H[x] =-\int p(x)\;\ln p(x)dx$
对于离散型变量，我们已经得知当随机变量满足均匀分布时，熵最大。类似地，接下来我们也将求解对于连续型变量，其最大熵所对应的概率分布 $p(x)$ 。为了使这个最大值有一个合理的定义，我们需要限制p(x)的一阶矩和二阶矩。再结合其归一化的限制，我们在最大化微分熵时需要满足下面三个限制：
$\int_{-\infty}^{\infty} p(x)dx = 1$

$\int_{-\infty}^{\infty} xp(x)dx = \mu$

$\int_{-\infty}^{\infty} (x-\mu)^2p(x)dx = \sigma^2$

结合这些约束条件，利用拉格朗日乘数法求解，我们首先得到如下形式的目标函数：
$\min_{p(x),\lambda_1,\lambda_2,\lambda_3}-\int p(x)\;\ln p(x)dx+\lambda_1(\int_{-\infty}^{\infty} p(x)dx-1)+\lambda_2(\int_{-\infty}^{\infty} xp(x)dx - \mu)+\lambda_3(\int_{-\infty}^{\infty} (x-\mu)^2p(x)dx - \sigma^2)$
利用变分法，令上式关于 $p(x)$ 的导数等于零，可得
$\begin{equation} \begin{gathered} -ln\;p(x)-1+\lambda_1+\lambda_2 x+\lambda_3(x-\mu)^2 = 0\\ \Rightarrow p(x) = \text{exp}(-1+\lambda_1+\lambda_2 x+\lambda_3(x-\mu)^2) \end{gathered} \end{equation}$
将p(x)代入三个约束中，可以求得
$\begin{equation} \begin{aligned} \lambda_1 &= 1-\frac{1}{2}\ln (2\pi \sigma^2)\\ \lambda_2 &= 0\\ \lambda_3 &= -\frac{1}{2\sigma^2}\\ p(x) &= \frac{1}{\left(2 \pi \sigma^{2}\right)^{1 / 2}} \exp \left\{-\frac{(x-\mu)^{2}}{2 \sigma^{2}}\right\} \end{aligned} \end{equation}$
因此，最大化微分熵对应的分布是高斯分布。对应地，如果我们求高斯分布的微分熵，我们可以得到：
$\begin{equation} \begin{aligned} H[x] & = -\int_{-\infty}^{\infty} p(x)\ln p(x)dx\\ & = -\int_{-\infty}^{\infty}p(x) [-\frac{(x-\mu)^2}{2\sigma^2}-\frac{1}{2}\ln (2\pi \sigma^2)]dx\\ & = \frac{1}{2\sigma^2}\int_{-\infty}^{\infty}(x-\mu)^2p(x)dx+\frac{1}{2}\ln (2\pi \sigma^2)\\ & = \frac{1}{2}+\frac{1}{2}\ln (2\pi \sigma^2) \end{aligned} \end{equation}$
从上式也可以看出，与离散熵不同，微分熵是可以为负的。因为对于上式，当 $\sigma^2<1/(2\pi e)$ 时， $H[x]<0$ 。

4.4 条件熵（conditional entropy）

假设我们有一个联合概率分布 $p(x,y)$ ，我们从这个分布中抽取了一对 $x$ 和 $y$ 。如果x的值已知，那么y值所带来的附加信息量就是 $-\ln p(y|x)$ 。此时，变量y所带来的信息熵就为
$H[y|x] = -\int\int p(y,x)\;\ln p(y|x)dydx$
根据概率的乘法法则，容易得到
$H[x,y] = H[y|x]+H[x]$
即，描述 $x$ 和 $y$ 所需要的信息，等于描述 $x$ 自己所需要的信息，加上在给定 $x$ 的情况下描述 $y$ 所需要的信息。

4.5 相对熵（KL散度，Kullback-Leibler divergence）

考虑某个未知的分布 $p(x)$ ，我们已经使用了一个近似的分布 $q(x)$ 对它进行建模。如果我们使用 $q(x)$ 建立了一套编码体系，用于把 $x$ 的值传给接收者，那么，由于我们使用的是近似分布 $q(x)$ ，而非真实分布 $p(x)$ ，所以相对于使用 $p(x)$ 建立编码体系，我们需要一些附加信息。我们需要的平均的附加信息量可以通过下式定义：
$\begin{equation} \begin{aligned} KL(p||q) &= -\int p(x)\ln q(x)dx-\left(-\int p(x)\ln p(x)dx\right)\\ &= -\int p(x)\ln \frac{q(x)}{p(x)}dx \end{aligned} \end{equation}$
这被称为分布 $p(x)$ 和 $q(x)$ 之间的相对熵，也称KL散度（Kullback-Leibler divergence）。需要注意是KL散度并不是一个对称量，即 $KL(p||q)\not\equiv KL(q||p)$ 。可以证明， $KL(p||q)\ge0$ ，当且仅当 $p=q$ 时等号成立。

关于KL散度恒大于等于零的推导如下：

首先 $-\ln(x)$ 是凸函数，由凸函数性质可知
$f(\mathbb{E}[x])\le \mathbb{E}[f(x)]$
而对于连续变量，有
$f\left(\int x p(x) dx\right)\le \int f(x) p(x)dx$
所以对照KL散度的形式，有
$KL(p||q) = \int \left(-\ln \frac{q(x)}{p(x)}\right)p(x)dx\ge \ln\int \left(- \frac{q(x)}{p(x)}\right)p(x)dx = -\ln \int q(x) dx = 0$
而另一方面，由于 $-\ln x$ 是一个单调函数，所以仅当 $q(x)/p(x)=1$ ，即 $p(x)=q(x)$ 时， $KL(p||q)=0$ 。

对于未知分布 $p(x)$ ，如果我们尝试使用分布 $q(x|\theta)$ 来近似，其中 $\theta$ 可以控制该分布的形状，那么其中一种确认 $\theta$ 的方法就是最小化 $p(x)$ 和 $q(x|\theta)$ 之间的KL散度。但是由于真实分布 $p(x)$ 是未知的，所以我们并不能直接这么做。但是假设我们已经观察到了服从 $p(x)$ 分布的若干个训练数据点 $x_n$ ，那么根据式(17)中样本均值和随机变量整体均值的关系，我们可以通过如下公式近似表示KL散度：
$KL(p||q)\simeq \frac{1}{N}\sum_{n=1}^N \{-\ln p(x_n|\theta)+\ln q(x_n)\}$

公式右侧的第二项与 $\theta$ 无关，可以忽略，因此，为了最小化 $KL(p||q)$ ，实际上就是最大化 $\frac{1}{N}\sum_{n=1}^N -\ln p(x_n|\theta)$ 。因此我们可以看到，最小化KL散度实际上等价于极大化似然函数。

4.6 互信息（mutual information）

在KL散度的基础上，我们进一步定义两个随机变量的互信息。考虑由 $p(x,y)$ 给出的由 $x$ 和 $y$ 组成的数据集。如果 $x$ 和 $y$ 独立，则我们有 $p(x,y) = p(x)p(y)$ 。而如果两个变量不是独立的，则我们通过 $p(x,y)$ 和 $p(x)p(y)$ 之间的KL散度来判断它们是否接近于相互独立，即
$\begin{equation} \begin{aligned} I[x,y]&\equiv KL(p(x,y)||p(x)p(y))\\ &=-\int\int p(x,y)\ln \frac{p(x)p(y)}{p(x,y)}dxdy \end{aligned} \end{equation}$
这被称为变量 $x$ 和变量 $y$ 之间的互信息（mutual information）。根据KL散度的性质，我们知道 $I[x,y]\ge 0$ ，当且仅当 $x$ 和 $y$ 相互独立时等号成立。使用概率的加法规则和乘积规则，我们可以看到互信息和条件熵之间的关系为
$I[x,y] = H[x]-H[x|y] = H[y]-H[y|x]$

推导如下：
$\begin{equation} \begin{aligned} I[x,y] & = -\int\int p(x,y)\ln \frac{p(x)p(y)}{p(x,y)}dxdy\\ & = -\int\int p(x,y)\ln \frac{p(x)p(y)}{p(x|y)p(y)}dxdy\\ & = -\int\int p(x,y)\ln \frac{p(x)}{p(x|y)}dxdy\\ & = -\int p(x)\ln {p(x)}dx-\left(-\int\int p(x,y)\ln p(x|y)dxdy\right)\\ & = H[x]-H[x|y] \end{aligned} \end{equation}$
同理有 $I[x,y] = H[y]-H[y|x]$ 。

因此，我们可以把互信息看成由于知道 $y(x)$ 值造成的对 $x(y)$ 的不确定性的减小量。

下图可视化了互信息和条件熵之间的关系（蓝色错了，应该是 $H[y]$ ）：

这里不一定对应线性模型，例如对于多项式模型 $\sum_{k}w_kx ^k$ ， $\mathbf{w}$ 的维度可以是任意的。 ↩
这一节的目的并不是去求损失函数，而是希望基于损失函数去推导新来一个样本，该怎么将其划分到类别上。对应于第一种情况，就是将x划分给 $p(\mathcal{C}_k|x)$ 最大的第 $k$ 类。 ↩

最后编辑于：2022.10.13 01:31:35

禁止转载，如需转载请通过简信或评论联系作者。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 220,367评论 6赞 512
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,959评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,750评论 0赞 357
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,226评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,252评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,975评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,592评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,497评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,027评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,147评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,274评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,953评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,623评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,143评论 0赞 23
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,260评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,607评论 3赞 375
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,271评论 2赞 358

《PRML》笔记 第一章

第一章 引言