Question

红色石头的个人网站： redstonewill.com

上节课我们主要介绍了 Deep Learning 的概念。Deep Learing 其实是 Neural Networ 的延伸，神经元更多，网络结构更加复杂。深度学习网络在训练的过程中最核心的问题就是 pre-training 和 regularization。pre-training 中，我们使用 denoising autoencoder 来对初始化权重进行选择。denoising autoencoder 与统计学中经常用来进行数据处理的 PCA 算法具有很大的关联性。这节课我们将介绍 Radial Basis Function Network，把之前介绍的 adial Basis Function 和 Neural Network 联系起来。

RBF Network Hypothesis

之前我们介绍过，在 SVM 中引入 Gaussian Kernel 就能在无限多维的特征转换中得到一条“粗壮”的分界线（或者高维分界平面、分界超平面）。从结果来看，Gaussian SVM 其实就是将一些 Gaussian 函数进行线性组合，而 Gaussian 函数的中心就位于 Support Vectors 上，最终得到预测模型。

Gaussian kernel 的另一种叫法是 Radial Basis Function(RBF) kernel，即径向基函数。这个名字从何而来？首先，radial 表示 Gaussian 函数计算结果只跟新的点 x 与中心点的距离有关，与其它无关。basis function 就是指 Gaussian 函数，最终的矩就是由这些 basis function 线性组合而成。

从另外一个角度来看 Gaussian SVM。首先，构造一个函数：

上式中，指数项表示新的点 x 与之间的距离大小。距离越近，即权重越大，相当于对投的票数更多；而距离越远，权重越小，相当于对投的票数更少。其物理意义是新的点与的距离远近决定了与的接近程度。如果距离越近，则对的权重影响越大；如果距离越远，则对的权重影响越小。那么整体来说，就由所有的 SV 组成的线性组合而成，不同对应的系数是，最后由 sign 函数做最后的选择。这个过程很类型我们之前介绍的 aggregation 中将所有较好的 hypothesis 线性组合，不同的有不同的权重。我们把叫做 radial hypotheses，Gaussian SVM 就是将所有 SV 对应的 radial hypotheses 进行线性组合（linear aggregation）。

那么，Radial Basis Function(RBF) Network 其实就是上面 Gaussian SVM 概念的延伸，目的就是找到所有 radial hypotheses 的 linear aggregation，得到更好的网络模型。

之所以叫作 RBF Network 是因为它的模型结构类似于我们之前介绍的 Neural Network。

Neural Network 与 RBF Network 在输出层基本是类似的，都是上一层 hypotheses 的线性组合（linear aggregation）。但是对于隐藏层的各个神经元来说，Neural Network 是使用内积（inner-product）加上 tanh() 函数的方法，而 RBF Network 是使用距离（distance）加上 Gaussian 函数的方法。总的来说，RBF Network 是 Neural Network 的一个分支。

至此，RBF Network Hypothesis 以及网络结构可以写成如下形式：

上式中，表示每个中心点的位置，隐藏层每个神经元对应一个中心点；表示每个 RBF 的权重，即投票所占比重。

对应到 Gaussian SVM 上，上式中的 RBF 就是 Gaussian 函数。由于是分类问题，上式中的 Output 就是 sign 函数。其中，RBF 的个数 M 就等于支持向量的个数 SV，就代表每个 SV 的坐标，而就是在 Dual SVM 中推导得到的值。那我们学习的目标就是根据已知的 RBF 和 Output，来决定最好的中心点位置和权重系数。

在之前介绍 SVM 的时候，我们就讲过 Mercer 定理：一个矩阵是 Kernel 的充分必要条件是它是对称的且是半正定的，条件比较苛刻。除了 Gaussian kernel 还有 Polynomial kernel 等等。Kernel 实际上描述了两个向量之间的相似性，通过转换到 z 空间计算内积的方式，来表征二者之间的相似性。而 RBF 实际上是直接使用 x 空间的距离来描述了一种相似性，距离越近，相似性越高。因此，kernel 和 RBF 可以看成是两种衡量相似性（similarity）的方式。本文介绍的 Gaussian RBF 即为二者的交集。

除了 kernel 和 RBF 之外，还有其它衡量相似性的函数。例如神经网络中的神经元就是衡量输入和权重之间的相似性。

经过以上分析，我们知道了 RBF Network 中 distance similarity 是一个很好的定义特征转换的方法。除此之外，我们还可以使用其它相似性函数来表征特征转换，从而得到更好的机器学习模型。

RBF Network Learning

我们已经介绍了 RBF Network 的 Hypothesis 可表示为：

其中表示中心点的位置。的个数 M 是人为决定的，如果将每个样本点都作为一个中心点，即 M=N，则我们把这种结构称为 full RBF Network。也就是说，对于 full RBF Network，每个样本点都对最终的预测都有影响（uniform influence），影响的程度由距离函数和权重决定。如果每个样本点的影响力都是相同的，设为 1，，那么相当于只根据距离的远近进行投票。最终将 x 与所有样本点的 RBF 距离线性组合，经过 sign 函数后，得到最终的预测分类结果。这实际上就是 aggregation 的过程，考虑并计入所有样本点的影响力，最后将 x 与所有样本点的 distance similarity 进行线性组合。

full RBF Network 的矩可以表示为：

我们来看上式中的 Gaussian 函数项，当 x 与样本点越接近的时候，其高斯函数值越大。由于 Gaussian 函数曲线性质，越靠近中心点，值越大；偏离中心点，其值会下降得很快。也就是说，在所有 N 个中心样本点中，往往只有距离 x 最近的那个样本点起到关键作用，而其它距离 x 较远的样本点其值很小，基本可以忽略。因此，为了简化运算，我们可以找到距离 x 最近的中心样本点，只用这一个点来代替所有 N 个点，最后得到的矩也只由该最近的中心点决定。这种模型叫做 nearest neighbor model，只考虑距离 x 最近的那一个“邻居”。

当然可以对 nearest neighbor model 进行扩展，如果不是只选择一个“邻居”，而是选择距离 x 最近的 k 个“邻居”，进行 uniformly aggregation，得到最终的矩。这种方法通常叫做 k 近邻算法（k nearest neighbor）。

k nearest neighbor 通常比 nearest neighbor model 效果更好，计算量上也比 full RBF Network 要简单一些。值得一提的是，k nearest neighbor 与 full RBF Network 都是比较“偷懒”的方法。因为它们在训练模型的时候比较简单，没有太多的运算，但是在测试的时候却要花费更多的力气，找出最相近的中心点，计算相对复杂一些。

接下来，我们来看一下 Full RBF Network 有什么样的优点和好处。考虑一个 squared error regression 问题，且每个 RBF 的权重为而不是前面简化的。目的是计算最优化模型对应的值。该 hypothesis 可表示为：

很明显，这是一个简单的线性回归问题，每个 RBF 都可以看成是特征转换。特征转换后的向量可表示为：

那么，根据之前线性回归介绍过的最优化解公式，就能快速地得到的最优解为：

上述解的条件是矩阵是可逆的。

矩阵 Z 的大小是 NxN，是一个方阵。而且，由于 Z 中每个向量表示该点与其它所有点的 RBF distance，所以从形式上来说，Z 也是对称矩阵。如果所有的样本点都不一样，则 Z 一定是可逆的。

根据 Z 矩阵的这些性质，我们可以对的解进行化简，得到：

将的解代入矩的计算中，以为例，得到：

结果非常有趣，模型的输出与原样本完全相同。同样，对任意的，都能得到。因此，。看起来，这个模型非常完美了，没有 error。但是，我们之前就说过，机器学习中，并非好事，很可能造成模型复杂度增加及过拟合。

当然，这种方法在某些领域还是很有用的。比如在函数拟合（function approximation）中，目标就是让，使得原所有样本都尽可能地落在拟合的函数曲线上。

为了避免发生过拟合，我们可以引入正则项，得到的最优解为：

我们再来看一下 Z 矩阵，Z 矩阵是由一系列 Gaussian 函数组成，每个 Gaussian 函数计算的是两个样本之间的 distance similarity。这里的 Z 与之前我们介绍的 Gaussian SVM 中的 kernel K 是一致的。当时我们得到 kernel ridgeregression 中线性系数的解为：

比较一下 kernel ridgeregression 与 regularized full RBF Network 的解，形式上相似但不完全相同。这是因为 regularization 不一样，在 kernel ridgeregression 中，是对无限多维的特征转换做 regularization，而在 regularized full RBF Network 中，是对有限维（N 维度）的特征转换做 regularization。因此，两者的公式解有细微差别。

除此之外，还有另外一种 regularization 的方法，就是不把所有 N 个样本点都拿来作中心点，而是只选择其中的 M 个样本点作为中心点。类似于 SVM 中的 SV 一样，只选择具有代表性的 M 个中心点。这样减少中心点数量的同时也就减少了权重的数量，能够起到 regularization 的效果，避免发生过拟合。

下一部分，我们将讨论如何选取 M 个中心点作为好的代表。

k-Means Algorithm

之所以要选择代表，是因为如果某些样本点很接近，那么就可以用一个中心点来代表它们。这就是聚类（cluster）的思想，从所有 N 个样本点中选择少数几个代表作为中心点。

聚类（clustering）问题是一种典型的非监督式学习（unsupervised learning）。它的优化问题有两个变量需要确定：一个是分类的分群值，每一类可表示为；另外一个是每一类对应的中心点。那么对于该聚类问题的优化，其 error function 可使用 squared error measure 来衡量。

那么，我们的目标就是通过选择最合适的和，使得最小化。对应的公式可表示为：

从这个最小化公式，我们能够发现这是一个组合最佳化的问题，既要优化分群值，又要求解每一类的中心点。所以，这个最小化问题是比较复杂、难优化的。通常的办法是对 S 和分别进行最优化求解。

首先，如果是固定的，目标就是只要对所有的进行分群归类。这个求解过程很简单，因为每个样本点只能属于一个群 S，不能同时属于两个或多个群。所以，只要根据距离公式，计算选择离最近的中心点即可。

然后，如果是固定的，目标就是只要找出每个类的中心点。显然，根据上式中的 error function，所有的分群是已知的，那么该最小化问题就是一个典型的数值最优化问题。对于每个类群，利用梯度下降算法，即可得到的解。

如上图所示，中心点就等于所有属于类群的平均位置处。

经过以上的推导，我们得到了一个非常有名的一种 unsupervised learning 算法，叫做 k-Means Algorithm。这里的 k 就是代表上面的 M，表示类群的个数。

k-Means Algorithm 的流程是这样的：首先，随机选择 k 个中心点；然后，再由确定的中心点得到不同的类群；接着，再由确定的类群计算出新的不同的 k 个中心点；继续循环迭代计算，交互地对和 S 值进行最优化计算，不断更新和 S 值，直到程序收敛，实现最小化。具体算法流程图如下所示：

有一个问题是，k-Means Algorithm 的循环迭代一定会停止吗？或者说一定能得到最优解吗？答案是肯定的。因为每次迭代更新，和 S 值都会比上一次的值更接近最优解，也就是说是不断减小的。而的下界是 0，所以，最终会等于 0，和 S 最终能得到最优解。

k-Means Algorithm 已经介绍完毕。接下来，我们把 k-Means Algorithm 应用到 RBF Network 中去。首先，使用 k-Means，得到原始样本的 k 个中心点。原始样本到 k 个中心点组成了 RBF 特征转换。然后，根据上面介绍过的线性模型，由最优化公式解计算得到权重值。最后，将所有的用线性组合，即得到矩的表达式。具体的算法流程如下所示：

值得一提的是，这里我们使用了 unsupervised learning（k-Means）与我们上节课介绍的 autoencoder 类似，同样都是特征转换（feature transform）的方法。

在最优化求解过程中，参数有 k-Means 类群个数 M、Gaussian 函数参数等。我们可以采用 validation 的方法来选取最佳的参数值。

k-means and RBF Network in Action

下面这部分，我们将举几个例子，看一下 k-Means Algorithm 是如何处理分类问题的。

第一个例子，平面上有 4 个类群，k=4。首先，我们随机选择 4 个中心点，如下图中四种颜色的方块所示：

第一次迭代，由初始中心点，得到 4 个类群点的分布：

4 个类群点确定后，再更新 4 个中心点的位置：

第二次迭代，由上面得到的 4 个中心点，再计算 4 个类群点的分布：

4 个类群点确定后，再更新 4 个中心点的位置：

第三次迭代，由上面得到的 4 个中心点，再计算 4 个类群点的分布：

4 个类群点确定后，再更新 4 个中心点的位置：

第四次迭代，由上面得到的 4 个中心点，再计算 4 个类群点的分布：

4 个类群点确定后，再更新 4 个中心点的位置：

第五次迭代，由上面得到的 4 个中心点，再计算 4 个类群点的分布：

4 个类群点确定后，再更新 4 个中心点的位置：

第六次迭代，由上面得到的 4 个中心点，再计算 4 个类群点的分布：

4 个类群点确定后，再更新 4 个中心点的位置：

从上图我们可以看到，经过六次迭代计算后，聚类的效果已经相当不错了。从另外一个角度来说，k 值的选择很重要，下面我们来看看不同的 k 值对应什么样的分类效果。

如上图所示，初始时，我们分别设定 k 为 2，4，7，随机选择中心点位置。在经过多次迭代后，得到的聚类结果如下：

通过上面这个例子可以得出，不同的 k 值会得到不同的聚类效果。还有一点值得注意的是，初始中心点位置也可能会影响最终的聚类。例如上图中 k=7 的例子，初始值选取的右边三个中心点比较靠近，最后得到的右边三个聚类中心点位置也跟初始位置比较相近。所以，k 值大小和初始中心点位置都会影响聚类效果。

接下来，我们把 k-Means 应用到 RBF Network 中，同样分别设定 k 为 2，4，7，不同模型得到的分类效果如下：

很明显，k=2 时，分类效果不是太好；k=4 时，分类效果好一些；而 k=7 时，分类效果更好，能够更细致地将样本准确分类。这说明了 k-Means 中 k 值设置得是否合理，对 RBF Network 的分类效果起到重要的作用。

再来看一个例子，如果使用 full RBF Network 进行分类，即 k=N，如下图左边所示，设置正则化因子。下图右边表示只考虑 full RBF Network 中的 nearest neighbor。下图中间表示的是 k=4 的 RBF Network 的分类效果。

从上图的比较中，我们可以发现 full RBF Network 得到的分类线比较弯曲复杂。由于 full RBF Network 的计算量比较大，所以一般情况下，实际应用得不太多。

总结

本节课主要介绍了 Radial Basis Function Network。RBF Network Hypothesis 就是计算样本之间 distance similarity 的 Gaussian 函数，这类原型替代了神经网络中的神经元。RBF Network 的训练学习过程，其实就是对所有的原型 Hypotheses 进行 linear aggregation。然后，我们介绍了一个确定 k 个中心点的 unsupervised learning 算法，叫做 k-Means Algorithm。这是一种典型的聚类算法，实现对原始样本数据的聚类分群。接着，将 k-Means Algorithm 应用到 RBF Network 中，选择合适数量的中心点，得到更好的分类模型。最后，我们列举了几个在实际中使用 k-Means 和 RBF Network 的例子，结果显示不同的类群 k 值对分类的效果影响很大。

注明：

文章中所有的图片均来自台湾大学林轩田《机器学习技法》课程

更多 AI 资源请关注公众号：红色石头的机器学习之路（ID：redstonewill）