径向基函数网络

2015-02-11 | 研究学术 | 机器学习基础神经网络最近邻算法 k均值算法回归核方法正则化特征学习

径向基函数网络

高斯核SVM，可以实现无限维特征空间的最大边界分类器，它的实现方式是利用$\alpha_n$实现以支持向量$\mathbf x_n$为中心高斯函数的线性组合。

高斯核通常也称为径向基函数（RBF，radial basis function）。radial表示函数值只依赖于$\mathbf x$与“中心”$\mathbf x_n$之间的距离；basis function表示用来组合的系数$\alpha_n，y_n$。

令$g_n(\mathbf x)=y_n\exp\left(-\gamma\left\lVert\mathbf x-\mathbf x_n\right\rVert^2\right)$，它表示基于$\mathbf x$与$\mathbf x_n$之间距离权重的加权投票（$+1$或$-1$的票）。高斯核SVM可以表示为 \[ g_{SVM}(\mathbf x)=\mbox{sign}\left(\sum_{SV}\alpha_ng_n(\mathbf x)+b\right)， \] 它是径向基假设的线性融合。

径向基函数网络就是径向基假设的线性融合，它也是一种神经网络。

图 1: 神经网络与径向基函数网络 [PNG]

神经网络与径向基函数网络如上图所示：

隐藏层：神经网络采用“内积＋$\tanh$”，径向基函数网络采用“距离＋高斯函数”；
输出层都是同样的线性融合模型。

径向基函数网络的假设为 \begin{equation} h(\mathbf x)=\mbox{Output}\left( \sum_{m=1}^{M}\beta_m\mbox{RBF}(\mathbf x,\boldsymbol\mu_m)+b \right)， \end{equation} 高斯函数只是一种径向基函数$\mbox{RBF}$，$\beta_m$是投票权值，$\mbox{Output}$形式由不同的回归或分类问题确定。$\boldsymbol\mu_m$和$\beta_m$（带符号）是两个关键参数。高斯核SVM是一种径向基函数网络：径向基函数$\mbox{RBF}$采用高斯函数；对二分类问题输出是$\pm 1$；$M=\#SV$；$\boldsymbol\mu_m$是支持向量$\mathbf x_m$；$\beta_m$是从对偶SVM推导的$\alpha_my_m$。

给定径向基函数$\mbox{RBF}$和输出，径向基函数网络需要学习的参数是$\mu_m$和$\beta_m$。

核和RBF是两种不同的相似度度量方法。核描述基于$\mathcal Z$空间内积的相似性，需要满足Mercer条件。RBF通过$\mathcal X$空间的距离度量相似性，这种相似性与距离是单调递减（monotonically non-increasing）关系。一般采用度量$\mathbf x$和$\mathbf x’$相似性的函数还可以是¹ \[ \mbox{Neuron}(\mathbf x,\mathbf x’)=\tanh\left(\gamma\mathbf x^\top\mathbf x’+1\right)，\quad\mbox{DNASim}(\mathbf x,\mathbf x’)=\mbox{EditDistance}(\mathbf x,\mathbf x’)。 \] 神经网络的神经元也是在比较输入向量与权值向量之间的相似性。

RBF网络展示了通过度量到中心的距离也是一种很好的特征转换。相似性是一种很好的特征转换方法，相似性不一定与距离有关，也不一定与核有关。

学习算法

当$M=N$和$\boldsymbol\mu_m=\mathbf x_m$时，称为完全RBF网络。它的物理含义是每个点$\mathbf x_m$对周围的数据$\mathbf x$有权重$\beta_m$的影响，假设对二分类问题均匀影响（uniform influence）周围的数据，$\beta_m=1\cdot y_m$，那么 \begin{equation} g_{uniform}(\mathbf x)=\mbox{sign}\left(\sum_{m=1}^Ny_m\exp\left(-\gamma\left\lVert\mathbf x-\mathbf x_m\right\rVert^2\right)\right)， \end{equation} 这就是每个数据通过相似度对新数据的投票融合。这和k最近邻算法思想很相似。离$\mathbf x$最近的$\mathbf x_m$让$\exp\left(-\gamma\left\lVert\mathbf x-\mathbf x_m\right\rVert^2\right)$取得最大值。高斯函数衰减很快，最大的投票很可能会左右投票结果，不需要让所有数据投票，只用离$\mathbf x$最近数据投票，用选择法（selection）替代融合法（aggregation）， \begin{equation} g_{nbor}=y_m\mbox{ such that }\mathbf x\mbox{ closest to }\mathbf x_m， \end{equation} 这就是最近邻算法。若让k个$\mathbf x_m$参与对$\mathbf x$投票就是k最近邻算法。

如果不直接用$y_m$作为$\beta_m$投票，而更进一步考虑对$\beta_m$进行优化，用完全RBF网络解决基于平方误差的回归问题， \begin{equation} h(\mathbf x)=\sum_{m=1}^{M}\beta_m\mbox{RBF}(\mathbf x,\mathbf x_m)。 \end{equation} 这是基于RBF特征转换的线性回归， \[ \mathbf z_n=[\mbox{RBF}(\mathbf x_n,\mathbf x_1),\mbox{RBF}(\mathbf x_n,\mathbf x_2),\ldots,\mbox{RBF}(\mathbf x_n,\mathbf x_N)]， \] 最优解为$\boldsymbol\beta=\left(\mathbf Z^\top\mathbf Z\right)^{-1}\mathbf Z^\top\mathbf y$（若$\mathbf Z^\top\mathbf Z$可逆），$\mathbf Z$是$N\times N$的对称方阵，那么就有 \begin{equation} \boldsymbol\beta=\mathbf Z^{-1}\mathbf y。 \end{equation} 若每个$\mathbf x_n$都不一样，那么$\mathbf Z$总可逆。对于数据$\mathbf x_1$， \[ g_{RBF}(\mathbf x_1) =\boldsymbol\beta^\top\mathbf z_1 =\mathbf y^\top\mathbf Z^{-1}\cdot(\mbox{first column of }\mathbf Z) =\mathbf y^\top\left[1,0,\ldots,0\right]^\top =y_1， \] 那么就有 \begin{equation} g_{RBF}(\mathbf x_n)=y_n， \end{equation} 对于回归问题$E_{in}(g_{RBF})=0$。在函数逼近（function approximation）领域这叫完美内插（exact interpolation）；对机器学习而言这是过拟合，需要正则化。

正则化

对正则化的完全RBF网络的脊回归可得 \begin{equation} \boldsymbol\beta=\left(\mathbf Z^\top\mathbf Z+\lambda\mathbf I\right)^{-1}\mathbf Z^\top\mathbf y， \end{equation} 其中$\mathbf Z$可以看作高斯核矩阵，$\mathbf K=\mathbf Z$，对比脊回归的核模型，二则只相差矩阵$\mathbf Z^\top$，前者是有限$N$维转换的回归，后者是无限维转换的回归。

对于SVM核模型，只采用了支持向量作为参考进行距离度量。减少中心数量（也就减少了参与投票的权值），只使用部分代表点（prototype）作为中心，使$M\ll N$，也是一种有效的正则化方法。

如何找出这些有效的代表点呢？

k均值聚类

若$\mathbf x_1\approx\mathbf x_2$，不需要$\mbox{RBF}(\mathbf x,\mathbf x_1)$和$\mbox{RBF}(\mathbf x,\mathbf x_2)$都出现在RBF网络中，可以只用一个cluster$\boldsymbol\mu\approx\mathbf x_1\approx\mathbf x_2$替代两个点即可。

聚类是将数据$\{\mathbf x_n\}$分为不相交的集合（类）$S_1,S_2,\ldots,S_M$。当每个集合用$\boldsymbol\mu_m$作为代表时，若$\mathbf x_1$和$\mathbf x_2$都属于$S_m$，当且仅当$\boldsymbol\mu_m\approx\mathbf x_1\approx\mathbf x_2$。聚类的目标函数为 \begin{equation} \min_{\{S_1,\ldots,S_M;\boldsymbol\mu_1,\ldots,\boldsymbol\mu_M\}}E_{in}(S_1,\ldots,S_M;\boldsymbol\mu_1,\ldots,\boldsymbol\mu_M) ={1\over N}\sum_{n=1}^{N}\sum_{m=1}^M[[\mathbf x_n\in S_m]]\lVert\mathbf x_n-\boldsymbol\mu_m\rVert^2。 \end{equation} 这是混合的组合数值优化问题，很难最优化，但是可以简化为分别交替最优化$S_m$和$\boldsymbol\mu_m$：

最优划分：固定$\boldsymbol\mu_1,\ldots,\boldsymbol\mu_M$；选择每个$\mathbf x_n$所属的唯一类别$S_m$，使$\lVert\mathbf x_n-\boldsymbol\mu_m\rVert$最小。
最优计算：固定$S_1,\ldots,S_M$；对每个$\boldsymbol\mu_m$，由于 \[ \nabla_{\boldsymbol\mu_m}E_{in} =-2\sum_{n=1}^N[[\mathbf x_n\in S_m]](\mathbf x_n-\boldsymbol\mu_m) =-2\left(\left(\sum_{\mathbf x_n\in S_m}\mathbf x_n\right)-\left|S_m\right|\boldsymbol\mu_m\right)=0， \] 可得最佳$\boldsymbol\mu_m$是属于$S_m$所有$\mathbf x_n$的均值。

以上就是k均值算法的关键步骤，$k=M$，重复以上2步直至收敛。通常随机选择k个$\mathbf x_n$作为$\boldsymbol\mu_k$的初始值。收敛是指$S_1,\ldots,S_k$不再改变。算法通过交替最小化使$E_{in}$减小，一定能收敛。

####基于k均值的RBF网络

利用k均值算法，$k=M$，得到$\{\boldsymbol\mu_m\}$；

进行特征转换 \[ \Phi(\mathbf x)=\left[\mbox{RBF}(\mathbf x,\boldsymbol\mu_1),\mbox{RBF}(\mathbf x,\boldsymbol\mu_2),\ldots,\mbox{RBF}(\mathbf x,\boldsymbol\mu_M)\right]； \]

通过$\{(\Phi(\mathbf x_n),y_n)\}$上的线性模型得到参数$\boldsymbol\beta$；

返回$g_{RBFNET}(\mathbf x)=\mbox{LinearHypothesis}(\boldsymbol\beta, \Phi(\mathbf x))$。

上述算法采用非监督的k均值作为特征转换，如同自编码器。RBF网络需要确定的的参数是$M$和$\mbox{RBF}$函数，这些可通过验证方法确定。

虽然RBF网络和SVM的核模型与神经网络性能差不多，但在实际中并不常用。