机器学习笔记-Radial Basis Function Network

林轩田机器学习技法关于特征学习系列，其中涉及到$Neural\ Network$，$Backpropagation\ Algorithm$，$Deep\ Learning$，$Autoencoder$，
$PCA$，$Radial\ Basis\ Function\ Network$，$K$-$Means$，$Matrix\ Factorization$ 等。

• 机器学习笔记-Neural Network
• 机器学习笔记-Deep Learning
• 机器学习笔记-Radial Basis Function Network
• 机器学习笔记-Matrix Factorization

Radial Basis Function Network

先从一个之前介绍过的模型 $Gassian\ SVM$ 说起，简单的来说这个模型就是在$SVM$中加入了高斯核函数，从而可以做到在无限维度的空间中找最大分隔超平面。该模型最终得到的分类器如下：

$$g_{svm}(x) = sign\bigg(\sum_{SV}\alpha_ny_nexp\big(-\gamma\|x-x_n\|^2\big) + b\bigg)\tag1$$

仅仅从最终得到的结果来看，$Gassian\ SVM$可以看做是一些高斯函数的线性组合，这些高斯函数的中心点是$support\ vector$，这些线性组合的系数是$\alpha_ny_n$。

$Radial\ basis\ function$指的是我们要计算的函数的结果只和距离$(\|x-x_n\|)$有关；

$Radial\ basis\ function$：径向基函数是一个取值仅仅依赖于离原点距离的实值函数。也就是$\Phi(x)=\Phi(\|x\|)$，或者还可以是到任意一点$c$的距离，$c$点称为中心点，也就是$\Phi(x, c)=\Phi(\|x-c\|)$ 。

我们记 $g_n(x) = y_nexp(-\gamma\|x-x_n\|^2)$，这个式子可以理解为，看看$x$和中心点$x_n$的距离，离得越近，$exp(-\gamma\|x-x_n\|^2)$的值越大，那么就给出越大的和样本$(x_n, y_n)$同方向上（同号）的得分 $y_nexp(-\gamma\|x-x_n\|^2)$。最终$(1)$式就可以理解为一个新的$x$到不同的中心$x_n$的得分$g_n(x)$在参数$\alpha_n$下的线性组合 $g_{svm}(x) = sign(\sum_{sv}\alpha_ng_n(x_n) + b)$。

这样的话这个模型就可以理解为是一些和支撑向量$(support\ vector)$有关的径向基函数$(radial\ basis\ function)$的线性组合$(linear\ aggregation)$。
这一篇要介绍的$Radial\ basis\ function\ network(RBFNetwork)$就是这样的模型的延伸：组合只与半径$(\|x-x_n\|)$有关的函数，从而得到好的学习结果。

如果把$RBFNetwork$的架构画出来和$neural\ network$是非常相似的，这可能也是其称为$network$的原因。如下图：

可以看到在$RBFNetwork$的中间一层，借用$neural\ network$的概念，也就是隐层中，共有$m$个节点，分别表示$m$个中心点，这一层的功能就是计算样本点到每一个中心点的$RBF$函数值，然后再在输出层进行$linear\ aggregation$。$RBFNetwork$是$neural\ network$的一个分支，它研究的是将$neural\ network$中的神经元的功能从计算权重和输入的內积变为计算一个有关距离的函数值时，模型可以取得怎么样的效果。

RBF Network Hypothesis

现在我们可以使用下面的式子来描述不同的$RBFNetwork$的形式：

$$h(x) = Output\bigg(\sum_{m = 1}^{M}\beta_mRBF(x, \mu_m) + b\bigg)$$

其中：$RBF(x, \mu_m)$可以是高斯或者是其他的距离的函数，$\mu_n$是中心点向量，$\beta_m$是线性组合的系数，$Output$的方式视要解决的问题是回归还是分类而定。这里面有两个比较关键的因素， 一个需要参考的中心点$\mu_m$有哪些，另一个是线性组合的系数$\beta_m$怎么来决定。例如对于$Gaussian\ SVM$来说：$RBF$是高斯函数；由于要解决的是二元分类问题，所以$Output$采用的函数是$sign$；$M$的大小是支持向量的个数；$\mu_m$是支持向量；$\beta_m$是对偶$SVM$问题的解$\alpha_m$和支持向量的$label$值$y_m$的乘积。

所以一般的来说， $RBFNetwork$需要决定的就是中心点$\mu_m$和线性组合的系数$\beta_m$，另外还有一个参数，例如$RBF$函数的选择以及$Output$的输出方式。

在SVM with Gaussian Kernel中曾经提到，$Kernel\ function$的结果简单来说就是两个向量转换到高维空间中的內积，既然是內积因此可以理解为是一种衡量相似性的方法，即原来两个低维空间向量的相似性通过转换到高维空间计算內积来描述。$Poly$核中隐藏着一个多项式转换，也可以说其描述的是一个更高维空间中的相似性，同理高斯函数中隐藏着一个无限维空间中的相似性。
而在这里的$RBF$也是一种相似性的衡量，不过是直接通过在$X$空间中的距离来计算的，例如高斯函数，就是将距离的平方取负号然后$exp$就可以描述相似性。所以只要距离能算出来就可以定义不同的$RBF$。
所以$Kernel$和$RBF$可以看成是两种相似性的衡量方法，而$Gaussian$是这两种方式的交集。

$RBFNetwork$告诉我们一个很重要的事情是：相似性是一种很好的定义特征转换的方法，所以当有另外的相似性的衡量方法，和$kernel$无关，和$RBF$无关，那么就可以利用这些相似性作为特征转化来提高学习的效果。

如下的三个函数都可以看做是$RBF$：

• $exp(-\gamma\|x-\mu\|^2)$
• $-\sqrt{x^Tx - 2x^T\mu + \mu^T\mu}$
• $\|x = \mu\|$

RBF Network Learning

上一小节介绍了$RBF$的基本概念

$$h(x) = Output\bigg(\sum_{m = 1}^{M}\beta_mRBF(x, \mu_m)\bigg)$$

其中一个需要解决的问题是中心点$\mu_m$如何选取，一个简单的解决方法是将每一个数据都当做是中心点，这样的$RBFNetwork$称为$Full\ RBFNetwork$。

$Full\ RBFNetwork： M = N$(资料量)，$\mu_m =x_m$。这样的方式可以理解为每一个已知的数据都会参与对未知数据的预测，只不过对预测结果的贡献取决于和未知样本的相似性或者说距离。例如，对于二分类问题来说， $y_m \in \{-1, +1\}$，$full\ RBF\ network$构成的分类器如下：

$$g_{uniform}(x) = sign\bigg(\sum_{m = 1}^{N}y_mexp(-\gamma\|x-x_m\|^2)\bigg)\tag2$$

Nearest Neighbors

由于不知道该如何选取中心点而把所有的样本都视为中心，其实对这样的方式稍加改进就能得到另一种十分常见的机器学习方法：$K$-$NN$，即$k$近邻。

在$2$式所示的$uniform\ full\ RBF\ network$中，可以理解为是在计算$N$个高斯函数的结果的线性组合，这些高斯函数的值有大有小，其中和$x$最相近的$x_m$所在的那个高斯函数取得最大的值，由于高斯函数衰减的很快，所以通常值最大的高斯函数给出的结果往往能够决定最终的结果，这样我们就可以使用高斯函数值最大的那个中心点的$label$作为对结果的预测，而不用对所有的高斯函数的结果进行求和。（这个时候模型由$aggregation$变为$selection$）。其实就是在所有的样本中找一个和待预测样本最相似的样本将其$label$做为待预测的样本的$label$。将这样的方式进行延伸就得到了 $k\ nearest\ neighbors$，即找和待预测样本最相似的 $k$ 个样本，对这些样本点的$label$做$voting$。

不管是$uniform\ full\ RBF\ network$ 还是 $k\ nearest\ neighbors$，可以看到在训练阶段只是做了数据的存储，所有的工作量都集中到了预测阶段。

Interpolation by full RBF network

上面介绍了$full\ RBF\ network$，但是其中用来组合高斯函数的参数被简单的设置为了$y_m$，这里我们对其进行改进，学习得到最佳的参数$\beta_m$。并且我们的目标是使用$full\ RBF\ network$来做$regression$。即我们希望得到的模型是：

$$h(x) = \bigg(\sum_{m=1}^{N}\beta_mRBF(x, x_m)\bigg)$$

要求得最佳的$\beta_m$，其实就是要在通过$RBF$进行转换之后的数据：$z_n = \{RBF(x_n, x_1), RBF(x_n, x_2),\cdots, RBF(x_n, x_N)\}, n = 1, 2, \cdots. N$上做一个线性回归。可以得到线性回归的最佳解：

$$\beta = (Z^TZ)^{-1}Z^Ty$$
其中

• • $Z$是一个$N\times N$的对称矩阵$(z_{i.j} = RBF(x_i, x_j) = RBF(x_j, x_i) = z_{j, i})$。
  • 当所有的$x_n$不同的时候，使用高斯函数计算得到的$Z$矩阵是可逆的。

  因为$Z$是对称的， 是可逆的，所以有$\beta = (Z^TZ)^{-1}Z^Ty = Z^{-1}Z^{-1}Zy = Z^{-1}y$

  所以当使用$Gaussian$函数作为$RBF$，每一个数据点都作为中心点，并且资料不重复的话，那么最佳的$\beta_m$有很简单的解析解$\beta = Z^{-1}y$。

  这样我们就得到了$full\ Gaussian\ RBF\ network\ for\ regression$的模型，如下：
  

  $$g_{RBF} = \bigg(\sum_{m=1}^{N}Z^{-1}y\ exp\|x-x_m\|^2\bigg)$$

  我们来分析看看这样的模型有什么特别之处。当我们把训练集中的一个样本的 $x_n$ 喂给该模型的时候发现经过该模型计算之后会得到该样本的 $y_n$ 值。具体的计算过程如：
  

  $$g_{RBF}(x_1) = \beta^Tz_1 = (Z^{-1}y)^T(first\ column\ of\ Z) = y^TZ^{-1}(first\ column\ of\ Z) = y^T[1\ 0\ \cdots\ 0]^T = y_1$$
  其中，$Z^T = Z\longrightarrow (Z^{-1})^T = Z^{-1}， Z^TZ = I$

  也就是说$g_{RBF}$在训练集上的错误率为$0$。这样的结果对于一些应用例如函数逼近$function\ approximation$来说是完美的，因为经过拟合的函数通过了每一个已知的样本点，但是对于$machine\ learning$来说不是一个好的结果，因为这可能有$overfitting$的风险。

  Regularized full RBF network

  在线性回归$linear\ regression$中，通过加入正则化项来防止过拟合，加了正则化项的$linear\ regression$称为$ridge\ regression$。此时求得的$regularized\ full\ RBFNet\ for\ regression$的最佳的$\beta$为：
  

  $$\beta = (Z^TZ+\lambda I)^{-1}Z^Ty\tag3$$

  在$kernel\ ridge\ regressrion$ 中最佳的$\beta$为：

  $$\beta = (K+\lambda I)^{-1}y\tag4$$

  可以看到$(3)$和$(4)$式非常的相近，因为$RBFNet$中的$Z$其实就等于高斯核矩阵$K$，而产生差别的原因在于$regularization$的方式不同，在$kernel\ ridge\ regressrion$中是针对无限多维的转换做$regularization$，在$regularized\ full\ RBFNet$中是对有限维度的转换做$regularization$。

  以上的讨论都是基于所有的资料都用作中心点的情况，我们说这样可能会出现$overfitting$，所以需要添加$regularizer$。借鉴$SVM$中$support\ vector$的结果，当不使用所有的数据点都作为中心点的时候，可能会有更好的结果。用比较少的中心点也可以当成是在做$regularization$， 因为这样的话第二层的权重就变少了。下一节我们将介绍如何从所有的数据点中选择出具有代表性的数据点作为中心点。

  k-Means Algorithm

  这一小节我们的主要目标是找一些有代表性的样本作为$RBFNetwork$的中心点，而不是将所有的样本都当成是$RBFNetwork$的中心点。因为当$x_1 \approx x_2$的时候，它们的径向基函数表达的意思也是差不多的，这样就可以找一些比较有代表性的样本点来构成最终的$RBF\ Network$，而不必在做预测的时候考虑所有点的影响。接下来可以看到， 在解决这个问题的过程中，我们推导出了聚类算法$k$-$Means$，并从数学的角度或者说是最优化的角度重新认识了这个简单但是十分有用的算法。

  这个找有代表性的样本点的问题可以转化为聚类问题，因为当对数据聚类完成之后，每一个类的聚类中心就是我们想要找的$RBF\ Network$中具有代表性的点。

  对于聚类问题，我们希望每一个类中的样本点要尽可能的相似，即， 如果 $x_1, x_2 \in S_m$，那么 $\mu_m \approx x_1 \approx x_2$。（假设$\mu_m$是$S_m$的聚类中心，也就是我们想要找的代表点）同样我们也可以定义一个损失函数如下：
  

  $$E_{in}(S_1, \cdots, S_M;\mu_1, \cdots,\mu_M) = \frac1N\sum_{n=1}^{N}\sum_{m=1}^{M}[[x_n \in S_m]]\|x_n - \mu_m\|^2\tag1$$
  我们想要$E_{in}$最小， 其中：如果$\bigcirc$成立， $[[\bigcirc]] = 1$；如果$\bigcirc$不成立，$[[\bigcirc]] = 0$，$N$为样本的个数， $M$为聚类的个数。直观上讲，1式就是要最小化所有样本点到聚类中心点的距离。一方面我们要找到最佳的数据聚类方式，这是一个组合最优化问题；另一方面我们需要找到最佳的中心点选取方式，这是一个数值最优化问题。也就是需要决定两组参数$\{S_1, \cdots, S_m\}, \{\mu_1, \cdots, \mu_M\}$，在这里我们采取的优化方式是进行交替的优化，$optimize\ alternatingly$。

  当$\mu_1, \cdots, \mu_M$固定的时候，也就是聚类中心已经固定下来了， 现在只需要考虑对于一个样本点$x_n$来说，如何决定其归属的类，根据1式很容易得到，当选择使得$\|x_n - \mu_m\|$最小的$S_m$，也就是离$x_n$最近的聚类中心所在的类作为$x_n$所属的类别时$E_{in}$最小。
  问题解决了一半， 当每一个样本点都决定了其归属的类别之后，接下来就可以更新每一个类的中心.

  通常我们会将类中数据点的均值作为该类新的聚类中心， 为什么这么做呢？

  当$S_1, \cdots, S_m$固定的时候，最小化$E_{in}$的问题就变成了针对变量$\mu$的一个无约束的最优化问题。当然毫不犹豫的求取梯度：

  $$\begin{align*} \bigtriangledown_{\mu_m}E_{in} &= \frac{\partial\bigg( \sum_{n=1}^{N}\sum_{m=1}^{M}[[x_n \in S_m]]\|x_n - \mu_m\|^2\bigg)}{\partial\mu_m} \\ &= -2\sum_{n=1}^{N}[[x_n \in S_m]](x_n - \mu_m) \\ &= -2\bigg(\sum_{x_n \in S_m}x_n - |S_m|\mu_m\bigg) \end{align*}$$

  令梯度为$0$求取最佳解。
  

  $$-2\bigg(\sum_{x_n \in S_m}x_n - |S_m|\mu_m\bigg) = 0\longrightarrow\mu_m = \frac{\sum_{x_n \in S_m}x_n}{ |S_m|}$$

  这样我们就得到了一个非常著名的无监督学习算法， $k$-$Means$聚类算法。上面的谈论给了一些不同的视角来看待这个算法的运作。

  $k\ Means\ Algorithm$

  • 随机从数据中选择 $k$ 个数据点作为初始的聚类中心
  • $repeate$
    
    • 将每一个样本点归属到离它最近的聚类中心，从而得到k个类
    • 求取每一个类中的均值作为新的聚类中心
  • $until\ converge$

  为什么该算法一定会收敛呢？也就是说为什么经过一定次数的迭代之后{S_1, \cdots, S_m}会不在发生变化而稳定呢？经过上面的分析我们知道，每一个步骤，不过是确定了中心划分数据点， 还是确定了类簇决定新的聚类中心，都是在最小化$E_{in}$，而$E_{in}$的下限为$0$， 所以该算法一定会收敛。

  RBF Network Using k-Means

  我们之所以会推导$k$-$Means$这个算法，是为了确定$RBF\ Network$的中心点。结合$k$-$Means$得到的$RBFNetwork$算法如下：

  $RBF\ Network\ Using\ k Means$

  • $run\ kMeans\ with\ k=M\ to\ get\ \{\mu_m\}$
  • $construct\ transform\ \Phi(x)\ from\ RBF\ at\ \mu_m:\Phi(x) = [RBF(x, \mu_1), RBF(x, \mu_2), \cdots, RBF(x, \mu_M)]$
  • $run\ linear\ model\ on\ \{(\phi(x_n), y_n)\}\ get\ \beta$
  • $return\ g_{rbfNet}(x) = LinearHypothesis(\beta, \Phi(x))$

  首先使用$k$-$Means$算法来得到样本的$M$个中心点，我们利用这些中心点结合径向基函数$RBF$定义特征转换 $\Phi(x)$，原始数据经过特征转换得到新的数据 $\Phi(x) = [RBF(x, \mu_1), RBF(x, \mu_2), \cdots, RBF(x, \mu_M)]$， 在这些数据上利用线性模型：$linear\ regression, logistic\ regression, linear\ SVM$等等来求解$\beta$，得到最后的$RBF\ Network$。

  这是我们第二次看到使用非监督的学习算法来萃取数据中的特征，第一次是利用$autoencoder$。

  在$RBF\ Network$中的参数主要有$M$：中心点的个数；$RBF$中的参数，例如如果使用$Gaussian$的话需要决定其中的$\lambda$。

  k-Means and RBF Network in Action

  $k$-$Means$算法的结果受给定的参数 $k$ 和初始聚类中心设定的影响，因为在求解的过程中使用的方法是$alternating\ optimization$所以并不一定会保证得到全局最优的解。

  下面的图给出了一个利用$RBFNetwork\ Using\ kMeans$做二分类的例子，

  
  

  从上图可以得到的结论是， 当使用$k$-$Means$方法能够找出更合理的数据中心点或者说数据的代表的时候，那么$RBF\ Network$在基于这样的特征转换之下会得到更好的结果。

  当使用$full\ RBF\ network$，也就是将所有的样本点都当做是中心点，来解决以上的二分类问题时，结果如下图，其中最右边的$kNN$也是使用所有的样本点作为中心点，只不过在做决策的时候只考虑$k$个。最左侧是在$full\ RBF\ network$上加了正则化项，得到了更加平滑的分类边界。由于在预测的时候，$full\ RBF\ network$这样的模型要考虑所有的资料，所有在实际中通常不是很常用。

  
  

  总结

  本篇主要介绍了$RBF\ network$，其模型由一些中心点$prototype$上的径向基函数$RBF$构成，这些径向基函数可以高斯函数等等，这些中心点可以是所有的样本点或者是部分具有代表性的样本点。在寻找具有代表性的中心点的过程中，推导出了无监督学习算法，$k$-$Means$聚类算法，其优化求解的过程是$alternating\ optimization$。当中心点被选取出来之后，构建$RBF\ network$模型就只需要将所有的原始数据经过利用这些中心点结合径向基函数$RBF$定义的特征转换得到的新数据上求解一个$linear\ model$。最后我们看到这样的算法的表现大多依赖一开始选择的中心点的设置。