对神经网络的监督学习有多种不同的方法。在我以前的文章里提到过的反向传播算法，可以是看做递归技术的应用，这种方法又叫做随机逼近。

在这篇文章中，我将采用完全不同的途径。具体来说，通过包含如下两阶段的混合方式来解决非线性可分模式的分类问题：

• 第一阶段将一个给定的非线性可分模式的集合转换为新的集合，在一定条件下，转换后的模式变为线性的可能性很高；关于这一转换的数学证明我就不具体介绍了，大家可以去查阅 Cover 大大在 1965 年的早期论文
• 第二阶段是通过最小二乘估计来解决给定的分类问题

我们首先通过插值问题的讨论来描诉关于这一混合方式对模式分类问题的一种执行方式：使用径向基函数网络(radial-basis function network)，简称RBF，该网络由三层组成：

• 输入层由一些源节点（感知单元）组成。它们将网络与外界环境链接起来
• 第二层由隐藏单元组成，它的作用是从输入空间到隐藏（特征）空间之间进行非线性变换。在大多数情况下网络仅有的隐藏层具有较高的维数，这一层是利用混合学习过程的第一阶段在非监督学习的方式下训练
• 输出层是线性的，它是为提供网络的响应而专门设计的，该响应提供给应用于输入层的激活模式。这一层是利用混合过程的第二阶段在监督学习的方式下训练的

从输入空间到隐藏空间的非线性变换以及隐藏空间的高维数满足了Cover定理的仅有两个条件

RBF网络的多维理论建立在高斯函数之上，这一类中一个重要成员是径向基函数。高斯函数可以看做是一个核–因此基于高斯函数的两阶段过程的设计可看成是核方法。

模式可分性的 Cover 定理

当用径向基函数神经网络来解决一个复杂的分类任务时，问题基本可通过以下方式解决：首先用非线性方法将其转换到高维空间，然后在输出层进行分类，模式可分性的 Cover 定理，说明了这样做的合法性，该定理可以定性的表述如下：

假设空间不是稠密可分的，将复杂的模式分类问题非线性的投射到高维空间将比投射到低维空间更可能是线性可分的

我们知道，一旦模式具有线性可分性，则分类问题相对而言就更容易解决。因此，我们通过研究模式的可分性可以深入了解RBF网络作为模式分类器是如何工作的。

考虑一族曲面，每一个曲面都自然的将输入空间分成两个区域。用 χ 代表 N 个模式（向量） x₁，x₂，…，x_N 的集合，其中每一个模式都分属于 χ₁ 和 χ₂ 中的一类。如果在这一族曲面中存在一个曲面能将分别属于 χ₁ 和 χ₂ 的这些点分为两个部分，我们则称这些点的二分（二元划分）关于这族曲面是可分的。对于每一个模式 x ∈ χ ，定义一个由一组实值函数 { φ₁(x) | i = 1, 2, …, m₁ } 组成的向量，表示如下：

φ(x) = [ φ₁(x), φ₂(x), …, φ_m1(x)]^T

假设模式 x 是 m₀ 维输入空间的一个向量，则向量 φ(x) 将 m₀ 维输入空间的点映射到新的 m₁ 维空间的相应的点上。我们将 φ_i(x) 称为隐藏函数，因为它与前面神经网络中的隐藏单元起着同样的作用。相应的，由隐藏函数集合 { φ_i(x) }_i=1^m₁ 所生成的空间称为隐藏空间或者特征空间。

我们称一个关于 χ 的二分 { χ₁, χ₂} 是 φ 可分的，如果存在一个 m₁ 维的向量 w 使得我们得到如下公式：

w^Tφ(x) > 0, x ∈ χ₁ w^Tφ(x) < 0, x ∈ χ₂

由方程 w^Tφ(x) = 0 定义的超平面描述 φ 空间（即特征空间）中的分离曲面。这个超平面的逆像，即 x: w^Tφ(x) = 0 定义输入空间中的分离曲面（即决策边界）。

考虑一个利用 r 次模式向量坐标乘积的线性组合实现的一个自然类映射。与此种映射相对应的分离曲面被称为 r 阶有理簇。一个 m₀ 维空间的 r 阶有理簇可描述为输入向量 x 的坐标的一个 r 次齐次方程，表示为：

∑ a_i1,i2,…,irx_i1x_i2…x_ir = 0 0 <= i₁,i₂,…,i_r <= m₀

其中 x_i 是输入向量的 x 的第 i 个元素。为了用齐次形式来表达方程，将 x₀ 的值置为单位值1。x 中项 x_i 的 r 阶乘积，即 x_i1x_i2…x_ir ，被称为单项式。对于一个 m₀ 维的输入空间在上式中一共有 ((m₀ - r)! / m₀!r!) 个单项式。上式所秒速的分离曲面的类型的例子有超平面（一阶有理簇）、二次曲面（二阶有理簇）和超球面（带有某些线性限制系数的二次曲面）等。

通常情况下，线性可分性暗示着球面可分性，而球面可分性又暗示着二次可分性；反之不一定成立。

在概率模式中，一个模式集合的可分性是一个随机事件，该随机事件依赖于选择的二分以及输入空间的模式分布。假设激活模式 x₁, x₂, …, x_N 是根据输入空间的概率特性二独立选取的。同时假设所有的关于 χ = { x_i }_i=1^N 的二分都是等概率的。令 P(N, m₁) 表示某一随机选取的二分是 φ 可分的概率，这里被选中的分离曲面的类具有 m₁ 维的自由度。则可将 P(N, m₁) 表述为：

P(N, m₁) = (1/2)^N-1∑(N-1), N > m₁-1 P(N, m₁) = (1/2)^N-1∑(m), N <= m₁-1

上式隐含了 Cover 的可分性定理对于随机模式的本质。他说明累计二项概率分布，相当于抛（N-1）次硬币有（m₁-1）次或者更少词头像向上的概率。

尽管在上式的推导中遇见的隐藏单元院是一个多项式的形式，因而与我们通常在径向基函数网络中用到的有所不同，但是该式的核心内容却具有普遍的适用性。具体来说，隐藏空间的维数 m₁ 越高，则概率 P(N, m₁) 就越趋向于1.总之，关于该模式可分性的 Cover 定理只要包含下面两个基本部分：

• 由 φ_i(x) 定义的隐藏函数的非线性构成，这里 x 是输入向量，且 i = 1, 2, …, m₁
• 高维数的隐藏（特征）空间，这里的高维数是相对于输入空间而言的。位数由赋给 m₁ 的值（即隐藏单元的个数）决定

综上所述，通常讲一个复杂的模式分类问题非线性的投射到高维数空间将会比投射到低维空间更可能是线性不可分的。但需要强调的是，有时使用非线性映射就足够导致线性可分，而不必升高隐藏单元空间维数。

曲面的分离能力

上式对于在多维空间中随机指定输入模式线性可分的期望最大数目有重要意义。为了研究这个问题，如前所诉将 x₁，x₂，…，x_N 视为一个随机模式（向量）序列。令 N 为一个随机变量，定义为该序列为 φ 可分时的最大整数，这里的 φ 具有 m₁ 的自由度。于是由上式可推导出当 N = n 时的概率：

为了解释上诉结果，我们回想一下负二项分布的定义。该分布相当于在一组重复的伯努利实验中有 r 次成功，k 次失败的概率。在这种概率分布中，每一次实验只有两个两种结果，不是成功就是失败，并且成功和失败的几率在整租实验中都是相同的。令 p 代表成功的概率，q 代表失败的概率，p + q = 1。负二项分布定义如下：

在 p = q = 1/2（即成功与失败具有相等的概率时）且 k + r = n 的特殊情况下，负二项分布将变为：

根据上诉定义，我们现在可以看出上式所表示的结果恰好就是负二项分布，只不过右移了 m₁ 个单位且具有参数 m₁ 和 1/2。这样，N 相当于在一组抛硬币的实验中出现了第 m₁ 次失败的“等待时间”。随机变量 N 的期望机器中位数分别为：

ε[N] = 2m₁ median[N] = 2m₁

因此，可以得到 Cover 定理的一个推论，用著名的渐进结果的形式可表述如下：

一组随机指定的输入模式（向量）的集合在 m1 维空间中线性可分，它的元素数目的最大期望等于2 m1

该结果表明，2m₁ 是对一族具有 m₁ 维自由度的决策曲面的分离能力的自然定义。在一定程度上，一个曲面的分离能力与 VC 维数的概念有着密切的联系

注释

径向基函数是在解决实多变量插值问题时首次提出的。现在径向基函数是数值分析研究中的一个主要方向

Cover 定理的证明遵循如下两个基本考虑：

Schlafli 定理，或函数计数定理：对 m₁ 维欧几里得空间上的 N 个处于一般位置的向量进行二分，可得到的齐次线性可分的二分方式的数目等于：

如果每一个含有 m₁ 个或者小于 m₁ 个的向量子集都是线性独立的，也就是说 m₁ 维的欧几里得空间上的集合 χ = { x_i }_i=1^N 处于一般位置

χ 的联合概率分布的反射不变性：一个随机的二分是可分的概率（在 χ 的条件下）等于 χ 的一个特定二分（所有的 N 个向量都属于一类）的非条件概率

小结

本系列的第一篇文章主要介绍了关于模式可分的 Cover 定理以及相关公式。

下一篇计划为介绍如何使用径向基函数来求解插值问题。

（Ps：公式由mathtype友情支持）