本章主要是介绍了核方法和高斯过程的一些知识。笔记分两部分，这是第一部分：核方法。
注：本文仅属于个人学习记录而已！参考Chris Bishop所著Pattern Recognition and Machine Learning(PRML)以及由Elise Arnaud, Radu Horaud, Herve Jegou, Jakob Verbeek等人所组织的Reading Group。
目录
1、前言
之前我们的模型一些参数模型，比如神经网络、线性回归等等，是学习一个由参数控制的的输入到输出的映射，模型学习完成之后，就可以扔掉所有的训练数据，预测时只根据参数就可以得到预测值。也有一些机器学习算法，在模型训练完成之后，并不扔掉所有的训练数据，在模型预测时，会用的所有的或者一部分训练数据，比如KNN和SVM。
徆多线性参数模型都可以通过 dual representation（对偶表示/达）的形式表达为核函数的形式。什么是核函数呢？核函数是指特征映射后的内积表达，即使用非线性变换\(\Phi(x)\)把输入属性映射到特征空间，核函数是\(k(x,x') = \Phi(x)^T \Phi(x')\)。从定义看，核函数是一个对称函数，即\(k(x,x') = k(x',x)\)。这里\(\Phi(x)\)是可以等于x的。考虑到核函数是特征空间里的点的内积，那么许多已知的一些算法都可以用核函数来改写，有时候称之为kernel trick。即使用别的核来替换原来的内积。核函数的种类也比较多，后面会慢慢提到。
2、对偶表达
很多线性回归和分类模型可以用对偶表达来重新阐述。这也方便我们后面理解SVM模型。对于线性回归，我们采用最小二乘法，它的误差函数是\(j(w) = \frac{1}{2} \sum^N_{n=1}(w^T \Phi(x_n) - t_n)^2 + \frac{\lambda}{2} w*Tw\)。这里\(\lambda \le 0\)。如果我们对w取偏导为0，我们可以得到w的解是向量\(\Phi(x_n)\)的线性组合,即\(w = \Phi^T a\)，其中，\(a = (a_1, ... , a_n)^T, \ \ a_n = \frac{1}{\lambda} (w^T \Phi(x_n) - t_n)\) ，之后把得到的w再带回到误差函数J中，即得到对偶表达(dual formulation)如下：
\[J(a) = \frac{1}{2} a^T \Phi \Phi^T \Phi \Phi^T a - a^T \Phi \Phi^T t + \frac{1}{2} t^T t + \frac{\lambda}{2} \Phi \Phi^T a\]这里的\(t = (t_1, ... , t_N)^T\)。如果我们取\(K = \Phi \Phi^T\)，那么J就可以表示为:
\[J(a) = \frac{1}{2} a^TKKa - a^T Kt + \frac{1}{2}t^Tt + \frac{\lambda}{2} a^TKa\]这里的我们对a取导数为0，可以得到\(a = (K + \lambda I_N)^ {-1} t\)。如果我们再带回去，就可以得到\(y(x) = w^T \Phi(x) = a^T \Phi \Phi(x) = k(x)^T (K + \lambda I_N)^ {-1} t\)。这里的k就是所谓的核函数。由此，我们可以看到，最终的预测是输入x与训练数据的x和t的组合得到的，即把基于特征的学习转换成了基于样本的学习。
在对偶表达中，决定参数的向量a是N维方阵，而在原始的方法中，参数w的是M维的方阵。通常样本数N远大于特征数M，所以对偶表达在实际中看起来没什么用。但是，对偶表达的优点是，它可以通过核函数k(x, x’)来完整的表达，因此我们可以直接研究核函数而不考虑特征向量\(\Phi(x)\)，即允许我们使用高维度特征空间，甚至是无限维。
3、构造核函数
构造核函数的方式之一是选择一个特征空间变换映射\(\Phi(x)\)，之后使用该变换选择一个对应的核函数。比如\(k(x, x') = \Phi(x)^T \Phi(x') = \sum _ {i=1} ^M \Phi_i(x) \Phi_i(x')\)，这里我们根据计算可以得到核函数的具体值。
另一种方式是我们自己直接构建一个核函数，这种情况下，我们必须要选择一个有效的核，即它对应了某个特征空间的向量的数乘。比如核函数\(k(x,z) = (x^T z)^2\), 如果我们带入一个二维输入\(x =(x_1, x_2)\)，那么我们可以展开k(x, z)可以得到：
\[k(x,z) = (x^Tz)^2 = (x_1z_1 + x_2z_2)^2 = (x_1^2, \sqrt{2}x_1x_2,x_2^2)(z_1^2, \sqrt{2}z_1z_2,z_2^2)^T = \Phi(x) \Phi(z)\]事实上，我们不需要每次都去分解判断。 判断有效核的充分必要条件是mercer定理，即核矩阵是半正定的。此外，我们可以使用核函数的一些性质来构造核函数。根据这些性质，如果我们限制我们的核是对称的，半正定的，那么它可以在一些应用中来表征x和x’之间的相似度(similarity)。这种“核工程”，可以参考其他的论文。接下来，书中举了很多例子。这里以高斯核为例, \(k(x,z) = exp(- \mid \mid x - z \mid \mid ^2 / (2 \sigma^2)\), 这里高斯并不代表概率密度，所以归一化因子省略。我们可以看到\(\mid \mid x - z \mid \mid ^2 = x^Tx + z^Tz - 2x^Tz\)，那么\(k(x, z) = exp(-x^Tx / (2\sigma^2)) exp(-z^Tz / (2\sigma^2))exp(x^Tz/ (\sigma^2))\),之后使用核函数的一些性质可以证明这个一个有效核。需要注意的是高斯核对应的特征空间是无限维的（因为指数可以展开成无线维）。此外高斯核也并不限定使用欧几里得距离，即可以使用非线性核k(x, z)来替换高斯核里的\(x^Tz\)。
还有一种使用概率生成来构造核函数，使得在判别设定下可以使用生成模型。生成模型可以很自然的处理缺失值，而且对于隐式马尔科夫模型(hidden Markov models)可以处理长度不一的序列数据。而判别模型在判别任务中表现要更好。那么如何结合两者呢？一种方式是 使用生成模型构造核函数，之后用判别方法来使用核函数。
对于生成模型p(x),定义核函数为\(k(x,z) = p(x)p(z)\),很明显这是一个有效核，可以理解为如果输入x和z同时有较大的概率，那么它们非常相似。同样，我们可以引入权重变量i(潜在变量)，可以得到\(k(x,z) = \sum_i p(x \mid i) p(z \mid i) p(i)\)，对于连续的值，那么可以换成是积分的形式。那么考虑一个例子，长度为L的观测序列\(X=(x_1, ... , x_L)\),使用隐式马尔科夫模型，用p(X)表示在隐式状态\(Z=(z_1, ..., z_L)\)的边际分布。那么用如下的核函数可以衡量两个序列X和Y和相似度,即
\[k(X,Y) = \sum_z p(X \mid Z) p(Y \mid Z) p(Z)\]两个序列都是隐式序列Z中生成的。这个核函数，可以衡量不同长度的观测序列。
还有一种是使用Fisher核来应用生成模型。考虑生成模型\(p(x \mid \theta), \theta\)是参数向量，目标是寻找一个核函数来衡量由生成模型产生的向量x和z的相似度。他们定义Fisher分数为\(g(\theta, x) = \nabla _ \theta \ln p(x \mid \theta)\)，那么定义Fisher核为\(k(x,z) = g(\theta, x)^T F ^ {-1} g(\theta, z)\),其中F是指Fisher信息矩阵\(F = E_x [g(\theta, x) g(\theta, x)^T]\)。实际中，Fisher信息矩阵不可求，一般都要去近似。更一般的是我们之间使用\(k(x,z) = g(\theta, x)^T g(\theta, z)\)。Fisher核的应用之一是在文本检索领域。
4、RBF网络
4.1RBF推导
在之前，我们讨论通过基函数来进行特征变换，一个比较常用的基函数是RBF(radial basis functions),定义为\(\Phi_j(x) = h( \mid \mid x - \mu_j \mid \mid)\)。
首先我们看看RBF的引入。给定输入向量\(x_1, ..., x_N\)，对应目标值为\(t_1, ..., t_N\),我们的目标是找到一个能够完美拟合每一个值的平滑函数f(x)，即\(f(x_n) = t_n\)，这个可以通过RBF的线性组合得到：\(f(x) = \sum_ {n=1}^N w_n h( \mid \mid x - x_n \mid \mid)\),这里的w可以使用最小二乘得到。当然，这个在模式识别中，很容易因为噪声导致过拟合。
此外RBF也可以通过正则理论来得到，即融合不同的正则操作，使用Green’s Function。还可以从有噪声输入的问题中得到，比如输入x伴随的噪声\(\zeta\),分布为\(v(\zeta)\),那么最小二乘误差如下:
\[E = \frac{1}{2} \sum_ {n=1} ^N \int (y(x_n + \zeta) - t_n)^2 v(\zeta) d \zeta\]类似于之前的推导（课后练习里有），我们可以得到 \(y(x_n) = \sum^N_ {n=1} t_n h(x-x_n)\)，其中：
\[h(x - x_n) = \frac{v(x-x_n)}{ \sum^N_ {n=1} v(x-x_n)}\]这个模型也称之为Nadaraya-Watson模型。如果\(\zeta\)是各向同性的，那么基函数将是radial的。此外，我们注意到\(h(x-x_n)\)是被归一化的，所以对于所有的x，均有\(\sum_n h(x-x_n) = 1\)。在实际中，我们有时也会选择归一化，来避免输入空间的某些区域均取得较小值，或者完全被基函数参数所决定。
此外，我们也可以由＆密度估计得到，这个之后会提到。
需要注意的是，如果我们的基函数与每一个数据都有关联，那么针对每一个新的预测，得到对应的模型都会要很大的计算量。因此，提出了一些扩展模型。通常基函数数量和他们的中心\(\mu_i\)都是只依赖于输入数据的，那么基函数和对应的系数可以根据最小二乘法不断的优化。此外，选择基函数的中心，最简单的方法是随机选择一部分数据的子集。一个更系统的方法是正交最小二乘法(orthogonal least squares)（这是一个序列选择过程，选择能够使得误差下降最大的点作为基函数的中心，不断的迭代）。也可以通过聚类的方法来选择，比如K-means。
4.2Nadaraya-Watson模型
在之前我们看到，使用回归模型预测一个新的输入时，结果可以是训练数据的目标值的线性组合得到，使用等价核(equivalent kernel)。这里我们可以从核密度估计来看核回归模型(kernel regression model)。比如我们训练数据是\((x_n, t_n)\)，我们使用Parzen窗法来估计联合分布p(x,t)，那么我们有： \(p(x,t) = \frac{1}{N} \sum^N _ {n=1} f(x-x_n, t-t_n)\)
这里的f(x,t)是组分密度函数，每个训练数据对应一个。那么我们的回归函数y(x)是基于训练数据的期望，即： \(y(x) = E(t \mid x) = \int ^ \infty _ {- \infty} tp(t \mid x)dt = \frac{\int tp(x,t)dt}{\int p(x,t)dt}\)
如果我们假设组分密度函数均值为0，即\(\int ^ \infty _ {- \infty} f(x,t) t dt = 0\),那么我们有:
\[y(x) =\frac{\sum_n g(x-x_n)t_n}{\sum_mg(x-x_m)} = \sum_n k(x,x_n)t_n\]其中，\(k(x,x_n) = \frac{g(x - x_n)}{\sum_m g(x-x_m)}, \ \ g(x) = \int ^ \infty _ {- \infty} f(x,t)dt\)。这种方法称之为Nadaraya-Watson模型，也称之为核回归(kernel regression),这里需要注意核函数满足\(\sum^N _ {n=1} k(x,x_n) = 1\)(有上面的推导定义可知)。
当然，这个模型不仅可得条件分布的期望，也可以直接得到条件分布，即：
\[p(t \mid x) = \frac{p(t,x)}{\int p(t,x) dt} = \frac{\sum_n f(x-x_n,t-t_n)}{\sum_m \int f(x-x_m,t-t_m)dt}\]作为一个例子，如果我们的输入是单变量x，f(x,t)是均值为0，方差为\(\sigma^2\)的高斯分布z=(x,t)，那么得到的条件分布是混合高斯分布。该模型的一个明显的扩展是，可以使用更加灵活的高斯组成的形式。更进一步的说，我们可以使用混合高斯模型来表示p(t,x)，使用在第九章会提到的一些方法来训练。此外，我们混合模型的组分个数可以小于训练数据个数，从而得到更快速的预测值。