特征扩展
当线性模型在原始特征空间内\(x\in \mathbb{R}^d\)效果不好时，可以把特征映射到高维空间\(\phi(x) \in \mathbb{R}^D (D > d)\)，然后在高维空间再进行线性建模。但是应该怎么映射这都是case by case的，通常可以使用“kitchen sink”法，然后用\(\ell_1\)正则化来进行特征筛选 \[ w_{\ell_1} = {\rm arg}\min_w \sum_{i=1}^n f(y_i, \phi(x_i), w) + \lambda |\!|w|\!|_1 \]
不过更简单地，我们可以只考虑特征展开的内积\(\phi(x_i)^\mathsf{T}\phi(x_j)\)，称之为核，记作\(K(x_i, x_j)\)
核
以感知机为例，由前面的讲解，可知感知机从数据中构建超平面的方法是将所有错分样本的标签和数据的内积累加起来，即 \[ w = \sum_{i \in \mathcal{M}} y_ix_i \] 其中\(\mathcal{M}\)是所有错分样本的一个顺序集合 有了\(w\)以后就可以对新的样本\(x_0\)预测其对应的\(y_0\) \[ y_0 = {\rm sign}(x_0^\mathsf{T}w) = {\rm sign}\left(\sum_{i \in \mathcal{M}}y_ix_0^\mathsf{T}x_i\right) \] 如果对所有数据都进行特征扩展，那么上面的预测方法就会被改写。注意\(x_0\)会被映射到\(\phi(x_0)\)，\(x_i\)也会被映射到\(\phi(x_i)\) \[ y_0 = {\rm sign}\left(\phi(x_0)^\mathsf{T}w\right) = {\rm sign}\left(\sum_{i \in \mathcal{M}}y_i\phi(x_0)^\mathsf{T}\phi(x_i)\right) \] 这里就出现了一个核 可以对核做出一个定义：核\(K(\cdot, \cdot): \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}\)是一个对称函数 (\(K(a,b) = K(b,a)\))，并且满足对任意\(n\)个\(\mathbb{R}^d\)中的数据点\(x_1, \ldots, x_n \in \mathbb{R}^d\)，其构成的\(n\)阶方阵\(K\)（\(K_{ij} = K(x_i, x_j)\)）是半正定的。从直觉来看，这说明\(K\)满足了作为一个协方差矩阵的所有属性
Mercer定理：如果函数\(K(\cdot, \cdot)\)满足了上述条件，则肯定存在一个映射\(\phi: \mathbb{R}^d \rightarrow \mathbb{R}^D\)使得 \[ K(x_i, x_j) = \phi(x_i)^\mathsf{T}\phi(x_j) \]
如果我们先定义\(\phi\)，则肯定能得到\(K\)。不过有时我们先定义\(K\)，避免定义\(\phi\)
最被广泛使用的一种核称为高斯核，也叫作径向基函数 (radial basis function, RBF) \[ K(x, x') = a\exp\left\{-\frac{1}{b}|\!|x-x'|\!|^2\right\} \] RBF衡量了两个点之间的距离。当两个点重合时，函数取得最大值\(a\)；当两点无限远时，函数取得最小值0。高斯核的映射\(\phi(x)\)能把原始数据映射到无限维空间
另一种核：\(K(x, x') = (1+x^\mathsf{T}x')^b, b > 0\)
通过以下三种方法，可以从旧核\(K_1, K_2\)构建新核 \[ \begin{align*} K(x,x') &= K_1(x,x')K_2(x,x') \\ K(x,x') &= K_1(x,x')+K_2(x,x') \\ K(x,x') &= \exp\{K_1(x,x')\} \end{align*} \]
核感知机
如果选择径向基函数(\(a=1\))作为核，那么核感知机的决策过程为 \[ \begin{align*} y_0 &= {\rm sign}\left(\sum_{i \in \mathcal{M}}y_i\phi(x_0)^\mathsf{T}\phi(x_i)\right) \\ &= {\rm sign}\left(\sum_{i \in \mathcal{M}}y_iK(x_0, x_1)\right) \\ &= {\rm sign}\left(\sum_{i \in \mathcal{M}}y_i\exp\left\{-\frac{1}{b}|\!|x_0 - x_i|\!|^2\right\}\right) \end{align*} \] 考虑之前介绍的RBF的性质，上面的决策过程实际就是遍历错分点，判断错分点与新数据之间的距离。如果距离远，函数值趋近于0，说明其标签在最后总和里的权重小；否则则大。即RBF使得决策过程类似一个“软投票” (soft voting)过程。 训练时也是找一个新的\(x'\)满足\(y' \not= {\rm sign}(\sum_{i\in \mathcal{M}_t}y_i K(x',x_i))\)，但是这时只需要把\(x'\)的索引加入到\(\mathcal{M}\)，而不需要计算\(w^{(t+1)}\)
核感知机的思想可以进一步推广到核k-NN上。在这里我们不止针对错分的数据集\(\mathcal{M}\)，而是对所有数据进行求和，即 \[ y_0 = {\rm sign}\left(\sum_{i=1}^n y_i\exp \left\{-\frac{1}{b}|\!|x_0 - x_i|\!|^2\right\}\right) \] 由于将各求和项统一除以一个正数不会改变总和的符号（即不会改变最终决策的结果），因此可以统一除以 \[ Z = \sum_{j=1}^n \exp \left\{-\frac{1}{b}|\!|x_0 - x_i|\!|^2\right\} \] 记 \[ p_i(x_0) = \frac{1}{Z}\exp \left\{-\frac{1}{b}|\!|x_0 - x_i|\!|^2\right\} \] 则最后的决策\(y_0\)为 \[ y_0 = {\rm sign}\left(\sum_{i=1}^n y_ip_i(x_0)\right) \] 可以看做是让所有数据投票，但是我们为每个数据根据其与新数据的距离分配投票的权重。离新数据近的权重大，远的权重小。这里\(p(x_0)\)扮演了置信度的概念，我们可以调整\(b\)使得对大部分\(x_i\)有\(p_i(x_0) \approx 0\)，使得我们只需要注意\(x_0\)附近的点
核回归
也称Nadaraya-Watson模型。其思想与核KNN方法类似。对新的样本\((x_0, y_0)\)，预测\(y_0\)为 \[ y_0 = \sum_{i=1}^n y_i \frac{K(x_0, x_i)}{\sum_{j=1}^n K(x_0, x_j)} \] 其意义是找到离\(x_0\)比较近的\(x_i\)，计算它们对应\(y_i\)的加权平均值
高斯过程
假设有\(n\)个样本，响应值\(y \in \mathbb{R}^n\)，特征矩阵为\(X\)，似然和先验分别为 \[ y \sim N(Xw, \sigma^2 I),\ \ w \sim N(0, \lambda^{-1}I) \] 可知（= =）其边缘分布为 \[ p(y|X) = \int p(y|X, w)p(w)dw = N(0, \sigma^2I + \lambda^{-1}XX^\mathsf{T}) \] 注意有\((XX^\mathsf{T})_{ij} = x^\mathsf{T}_ix_j\)，将\(x\)用\(\phi(x)\)替换，则有\((\phi(X)\phi(X)^\mathsf{T})_{ij} = K(x_i, x_j)\)，记为\(K\)，所以有 \[ p(y|X) = \int p(y|X, w)p(w)dw = N(0, \sigma^2I + \lambda^{-1}K) \] 称为高斯过程
定义：假设\(f(x) \in \mathbb{R}\)，且\(x \in \mathbb{R}^d\)，定义\(K(x,x')\)为两个点\(x\)和\(x'\)之间的核，则\(f(x)\)是高斯过程，\(y(x)\)是对结果附加的噪声过程，如果 \[ y|f \sim N(f, \sigma^2 I),\ f \sim N(0, K) \Leftrightarrow y \sim N(0, \sigma^2I + K) \] 其中\(y = (y_1, \ldots, y_n)^\mathsf{T}\)，\(K\)是\(n\)阶方阵，且\(K_{ij} = K(x_i, x_j)\) 注意高斯过程本身是不带噪声的，但是观测到的值会受到噪声影响（即\(f(x)\)）。这里噪声都是服从i.i.d.的，而且是无限维的
讲义中高斯过程的生成：选取\(x\in [0,1]\)，然后将其分成1000份，每个区间抽一个点出来，然后构建\(K\)，\(K\)是一个\(1000 \times 1000\)的矩阵，使用高斯核
贝叶斯线性回归：假设我们有\(n\)个样本对\(\mathcal{D} = \{(x_i,y_i)\}_{i=1}^N\)，我们想根据\(x_0\)预测\(y_0\)，积掉\(w\)，联合分布为 \[ \left[\begin{array}{c} y_0 \\ y \end{array}\right] \sim {\rm Normal}\left(0, \sigma^2I+ \left[\begin{array}{cc} x_0^\mathsf{T}x_0 & (Xx_0)^\mathsf{T} \\ Xx_0 & XX^\mathsf{T} \end{array}\right] \right) \] 那么有 \[ \begin{align*} y_0 | \mathcal{D}, x_0 &\sim {\rm Normal}(\mu_0, \sigma_0^2) \\ \mu_0 &= (Xx_0)^\mathsf{T}(XX^\mathsf{T})^{-1}y \\ \sigma_0^2 &= \sigma^2 + x_0^\mathsf{T}x_0 - (Xx_0)^\mathsf{T}(XX^\mathsf{T})^{-1}(Xx_0) \end{align*} \]
类似地，高斯过程可以估计\(y(x)\)这一预测的分布：给定样本数据集\(\mathcal{D}_n = \{(x_1, y_1), \ldots , (x_n, y_n)\}\)，对任何新的\(x\)，都可以计算\(y(x)\)的分布来做预测
令\(K(x,\mathcal{D}_n) = [K(x,x_1), \ldots, K(x,x_n)]\)，\(K_n\)是\(n\times n\)核矩阵，有 \[ \begin{align*} y(x)|\mathcal{D}_n & \sim N(\mu(x), \Sigma(x)), \\ \mu(x) &= K(x, \mathcal{D}_n)K_n^{-1}y, \\ \Sigma(x) &= \sigma^2 + K(x,x) - K(x,\mathcal{D}_n)K_n^{-1}K(x,\mathcal{D}_n)^\mathsf{T} \end{align*} \]
对\(f(x)\)的后验，只需要移去\(\sigma^2\)
高斯过程可以拟合任何形状的函数，求回归
