基于全变差和欧拉弹性杆的有监督模式识别方法

摘要

本发明公布了一种基于全变差和欧拉弹性杆的有监督模式识别方法，首先在所述最小二乘正则化框架下构造出基于全变差和欧拉弹性杆的能量泛函；然后利用变分法将该能量泛函最小化问题转换为求解对应的欧拉-拉格朗日偏微分方程；对所述偏微分方程求解，进而得到最终的分类器；运用该分类器对数据进行模式识别。本发明对有监督模式识别问题提出了新的方法，可以应用于一般情况下的分类问题，例如手写体数字识别；在绝大多数数据集上，本发明提出的方法能达到与现有的流行方法相媲美的效果。

权利要求

1.一种基于全变差和欧拉弹性杆的有监督模式识别方法，该方法基于连续的最小二乘正则化框架： 其中x是用于模式识别的一个样本的特征向量表示，u(x)为要求的函数，y为训练数据集中样本x的类标签值，Ω为训练样本所处的定义域，λ是参数，S(u)为正则项，其特征是，

所述正则项S(u)采用全变差和欧拉弹性杆的形式，从而得到新的有监督模式识别方法，包括如下步骤：

1)首先在所述最小二乘正则化框架下构造出基于全变差和欧拉弹性杆的能量泛函；

2)然后利用变分法将该能量泛函最小化问题转换为求解对应的欧拉-拉格朗日偏微分方程；

3)对所述偏微分方程求解，进而得到最终的分类器；

4)运用该分类器对数据进行模式识别；

步骤1)中所述全变差能量泛函为：

其中，x是用于模式识别的一个样本的特征向量表示，u(x)为要求的函数，y为训练数据集中一个样本的类标签值，JTV[u]表示关于u(x)的基于全变差的能量泛函，第二项为在u(x)连续的情况下的全变差，Ω是自变量所在的定义域，是梯度算子，代表了函数u(x)的梯度向量的模范数，λ是可预先设定的一个正则化参数；

步骤1)中所述欧拉弹性杆的能量泛函为：

其中，x是用于模式识别的一个样本的特征向量表示，u(x)为要求的函数，y为训练数据集中一个样本的类标签值，JEE[u]代表关于u(x)的基于欧拉弹性能量的能量泛函，κ为函数u的等值超曲面的平均曲率，Ω是自变量所在的定义域， 是函数u的梯度， 代表了函数u(x)的梯度向量的模范数， 是散度算子的形式表达，λ是可预先设定的一个正则化参数，a与b是控制全变差与欧拉弹性能量贡献度的两个参数。

2.如权利要求1所述的有监督模式识别方法，其特征是，步骤3)中，采用梯度下降的时间搜索算法对所述偏微分方程进行求解，即增加一个虚拟的时间变量，采用梯度下降法对所述偏微分方程进行迭代求解。

3.如权利要求1所述的有监督模式识别方法，其特征是，步骤3)中，采用滞后的线性方程组迭代法对所述偏微分方程进行求解，即固定住优化代价函数中的非线性部分，使其变成一个线性方程组，对线性方程组求解后再更新之前滞后的非线性部分，进行反复迭代求解。

说明书

基于全变差和欧拉弹性杆的有监督模式识别方法

技术领域

[0001] 本发明属于模式识别技术领域，具体涉及将图像处理中基于全变差和欧拉弹性杆的模型应用于能量最小化的最小二乘正则化(RLS)框架，用于有监督的模式识别。

背景技术

[0002] 有监督学习技术是模式识别领域中的一大热门问题，在计算机视觉等多个领域有着广泛的应用。模式识别究其本质研究的是分类技术，在不产生歧义的情况下，本说明书中用分类这个术语来指代模式识别。有监督分类指的是利用有标签的训练样本集训练出一种规则(分类器)来对新的样本进行预测，其一般形式描述为：

[0003] 给定训练集{(x1，y1)，...(xn，yn)}，其中xi∈Rd，Rd为d维实向量空间，对于二类分类问题yi∈{+1，-1}。其实质是要学习一个从向量x到标签y的映射，因此可以把分类问题归到一个函数学习的框架下来考虑。一般的有监督分类的正则化框架可以表示为：

[0004]

[0005] 其中u(x)是要学习的映射函数，n是训练样本个数，L代表损失函数，S(u)是正则项用来刻画映射u(x)的某些性质，λ是参数，用来调节损失项和正则项的比重。当L取预测值u(x)和真实值y之差的平方时，就是最小二乘正则化框架，本发明就是基于这个最小二乘正则化的连续情况下的框架。

[0006] 现有的一些方法如SVM，采用的hinge损失函数，正则项惩罚的是分界面的间隙宽度，但其仍是基于统计学习理论。常用的贝叶斯推理等统计学方法虽然取得了丰硕的成果，但也逐渐暴露出某些缺点，比如参数过多从而导致维数灾难，经典的统计分布函数与真实数据的实际分布不一致，难以有效估计数据的概率密度函数等。目前基于泛函能量极小化的函数学习方法越来越受到重视，R.M.Rifkin在2003年提出基于Tikhonov正则化的最小二乘分类(RLSC)；2010年Kush R等利用水平集的方法做有监督分类的研究，借鉴图像分割中的水平集方法，将决策边界(水平集函数的零水平集)的表面积作为正则化能量泛函，都取得了不错的效果。

[0007] 本发明从基础数学的角度出发，在一个连续的框架下建立能量泛函正则化模型，并利用泛函分析变分法等工具，采用合理的求解方法来实现有监督分类。

[0008] 在图像处理中，全变差图像去噪模型和欧拉弹性杆图像修补模型都取得了很大的成功，均是通过建立泛函模型，利用变分法等数学手段来求解。可以把图像去噪、图像修补理解为在已知的数据点上已有标签值(像素值)，要求得一个函数(要求的图像)来预测未知的点或有污染的点上的值，将这种二维的情形上升到高维，就类似于分类问题。本发明将这两种模型结合正则化的能量最小化框架来做有监督分类，这两种模型给出的正则项在不同程度上刻画了所求函数的几何性质，使得从另一种全新的角度来解决分类问题。

发明内容

[0009] 本发明的目的在于提出一种新的基于正则化框架的有监督模式识别方法。

[0010] 本发明的技术方案如下：

[0011] 一种基于全变差和欧拉弹性杆的有监督模式识别方法，该方法基于连续的最小二乘正则化框架： 其中x是用于模式识别的一个样本的特征向量表示，u(x)为要求的函数，y为训练数据集中样本x的类标签值，Ω为训练样本所处的定义域，λ是参数，S(u)为正则项，

[0012] 所述正则项S(u)采用全变差和欧拉弹性杆的形式，从而得到新的有监督模式识别方法。

[0013] 所述的有监督模式识别方法，包括如下步骤(参图1)：

[0014] 1)首先在所述最小二乘正则化框架下构造出基于全变差和欧拉弹性杆的能量泛函；

[0015] 2)然后利用变分法将该能量泛函最小化问题转换为求解对应的欧拉-拉格朗日偏微分方程；

[0016] 3)对所述偏微分方程求解，进而得到最终的分类器；

[0017] 4)运用该分类器对数据进行模式识别。

[0018] 所述的有监督模式识别方法，步骤3)中，采用梯度下降的时间搜索算法对所述偏微分方程进行求解，即增加一个虚拟的时间变量，采用梯度下降法对所述偏微分方程进行迭代求解。

[0019] 所述的有监督模式识别方法，步骤3)中，采用滞后的线性方程组迭代法对所述偏微分方程进行求解，即固定住优化代价函数中的非线性部分，使其变成一个线性方程组，对线性方程组求解后再更新之前滞后的非线性部分，进行反复迭代求解。

[0020] 所述的有监督模式识别方法，步骤1)中所述全变差能量泛函为：

[0021]

[0022] 其中，x是用于模式识别的一个样本的特征向量表示，u(x)为要求的函数，y为训练数据集中一个样本的类标签值，JTV[u]表示关于u(x)的基于全变差的能量泛函，第二项 为在u(x)连续的情况下的全变差，Ω是自变量所在的定义域，是梯度算子，代表了函数u(x)的梯度的L2模范数，λ是可预先设定的正则化参数。

[0023] 所述的有监督模式识别方法，步骤1)中所述欧拉弹性杆的能量泛函为：

[0024]

[0025] 其中，x是用于模式识别的一个样本的特征向量表示，u(x)为要求的函数，y为训练数据集中一个样本的类标签值，JEE[u]代表关于u(x)的基于欧拉弹性能量的能量泛函，κ为函数u的等值超曲面(水平集)的平均曲率，Ω是自变量所在的定义域， 是函数u的梯度， 代表了函数u(x)的梯度向量的模范数， 是散度算子的形式表达，λ是可预先设定的一个正则化参数，a与b是控制全变差与欧拉弹性能量贡献度的两个参数。

[0026] 本发明的有益效果：本发明对有监督模式识别问题提出了新的方法，可以应用于一般情况下的分类问题，例如手写体数字识别；在绝大多数数据集上，本发明提出的方法能达到与现有的流行方法相媲美的效果。

附图说明

[0027] 图1是本发明的流程图。

[0028] 图2是USPS手写体数字集中的样本示意图及分类结果示意。

具体实施方式

[0029] 本发明的实施方式如下：

[0030] 实施例一：USPS手写体数字识别

[0031] USPS(U.S.Postal Service)数据集使用美国邮政信封上扫描的手写体数字图片，每张图片是16*16的灰度图片，包含一个数字，如图2(a)给出了其部分数据展示，从数字0到9，共10类。本实施例从中随机抽取了1000个样本来做实验，由于原始数据维数较高，用主成分分析方法(PCA)将其降至30维，并归一化到[0，1]区间。

[0032] 步骤1：在正则化框架下构造能量泛函

[0033] (a)全变差能量泛函

[0034] 数学上，函数f(x)的全变差(Total Variation)在一维情况下并且当函数连续时有形式： 表示f(x)的全变差，a和b为区间的端点，f′(x)为函数的导数。可以看到全变差是对于函数的所有变化的总和的度量。

[0035] 将关于函数u(x)的全变差作为泛函能量的正则项，得到的有监督分类的能量泛函为：

[0036]

[0037] 其中JTV[u]表示关于u(x)的基于全变差的能量泛函(TV是Total Variation的缩写)，第二项 为在u(x)连续的情况下的全变差，Ω是自变量所在的区域，是梯度算子(例如 代表了函数u(x)的梯度的L2模范数，λ是参数。在图像去噪中，全变差正则项的作用在于保持图像中物体边缘处的信息。一般的去噪方法往往会使得图像边缘处也被模糊了，而全变差模型可以抑制这种模糊。这里在监督分类的能量泛函中，全变差项不仅限制函数变化总和较小，使得在分类中可得到一个大部分区域平缓的函数，而且在类与类的边界处允许有较大的变化，来使分类的边界更明显。最小化这个关于u的能量泛函得到的函数即可给出最终的分类器，函数的零水平集为分类边界。

[0038] (b)欧拉弹性杆能量泛函

[0039] 将欧拉弹性杆的模型推广到高维的有监督分类中，不像全变差那样直接，图像修补中的模型为：

[0040]

[0041] 其中I为所求图像，I0为原始要修补图像，Ω为整个图像区域，D为要修补区域，a、b为参数，κ为图像中等高线的曲率，形式上为：

[0042]

[0043] 为散度算子，n为等高线的单位外法向量， 为图像的梯度， 为图像的梯度模，此处是L2模范数。欧拉弹性杆(Euler’s Elastica)是指达到如下弹性能量平衡态的2
曲线γ：E2[γ]＝∫γ(a+bκ)ds，ds为弧长，κ为γ的曲率。修补模型中的第一项是对图像中所有等高线的欧拉弹性能量的积分。将欧拉弹性杆运用于图像修补，其优势在于弹性杆的插值能力，这种非线性样条是填补缺失区域的有力工具。把这种弹性能量推广到高维时，需要考虑曲率κ推广到高维的情形，在二维情况下u(x，y)＝0(此处x，y为二维自变量)，决定一条等高线y＝u(x)，而其曲率则具有形式 在三维情况下u(x，y，z)＝0(x，y，z为三维自变量)决定的是一个等值曲面，而该等值曲面的平均曲率具有和一维情况下曲线曲率相同的形式。曲面的平均曲率是曲面的外在度量，它刻画了曲面嵌入到周围空间的弯曲程度。更高维的情况，由u＝0决定的超曲面是函数u的等值超曲面，欧拉弹性能量迁移到高维就是刻画这些超曲面的弹性能量。表1给出了从u的表达式通过隐函数定理决定的曲线或(超)曲面，以及他们的曲率形式，其(平均)曲率除了一个和维数有关的常数因子外具有相同的形式。

[0044] 表1由隐函数定理决定的曲线(超)曲面及其曲率

[0045]

[0046] 由此本发明给出了欧拉弹性杆正则项的函数学习能量泛函：

[0047]

[0048] 其中，JEE[u]代表关于u(x)的基于欧拉弹性能量的能量泛函(EE是Euler’s Elastica的缩写)，κ为函数u的等值超曲面的平均曲率。为了形式的简化，在这里仍然保留原始模型中κ的形式，省去了前面的系数因子 在计算时将这个因子添加到权重b上。其余记号含义与之前TV的能量泛函中类似。能量泛函中第一项平方损失项限制函数尽量接近训练数据的真实值，正则项限制函数u等值超曲面的弹性能量使其尽量的小，这就意味着最终得到的分类边界有最低的弹性能量。如果令EE能量泛函中的a＝1，b＝0，这个能量泛函就退化成为没有考虑由曲率项带来的能量的TV能量泛函。

[0049] 步骤2：利用变分法将能量最小化转为偏微分方程

[0050] 利用变分法可以将TV和EE的能量泛函最小化问题转变成求解对应的欧拉-拉格朗日偏微分方程(PDE)。全变差能量泛函对应的PDE为：

[0051]

[0052] 注意此处 为散度算子， 是函数u的梯度， 代表了函数u(x)的梯度向量的模范数。这是一个非线性椭圆方程。对于欧拉弹性杆能量泛函，对应的PDE为：

[0053]2

[0054] 其中采用记号φ(κ)：＝a+bκ，φ′(κ)表示关于曲率κ的导数。

[0055] 步骤3：采用两种方法来求解，得到最终的分类器

[0056] 偏微分方程在高维的情况下若采用常规的数值方法(例如有限差分、有限元)会遇到维数灾难，而且上述的偏微分方程(1)和(2)形式十分复杂，数值上暂时没有适用的方法。本发明采用函数近似的思想，将函数泛函最小化转化为关于线性系数的最小化问题，并采用梯度下降的时间搜索算法(GD)和滞后的线性方程组迭代法(IagLE)两种方法来求解。

[0057] 利用函数近似的思想，将函数u(x)表示成一些径向基函数的线性组合：

[0058]

[0059] 其中m为基函数的个数，wi为线性系数， 为高斯径向基函数，c和zi均为参数，T||x-zi||为向量的L2范数。令w＝(w1，w2，...，wm)，于是求解函数u(x)的问题变为求解线性系数w。在实施时基函数 中的zi取所有的训练样本点。

[0060] 两种方法求解系数w：

[0061] (a)梯度下降的时间搜索算法(GD)

[0062] 由于全变差方法是欧拉弹性能量方法的一个特例，从欧拉弹性能量方法的求解出发，全变差的求解是类似的。引入时间变量t，从变分法得到的偏微分方程(2)中，得到函数u的梯度为：

[0063]

[0064] 将u表示成矩阵乘以向量的形式：u＝Φw，其中Φ为矩阵，其元素为将Φ固定，把u的梯度转换为系数向量w的梯度，于是梯度下降算法的迭代公式变为：

[0065]

[0066] 其中τ为时间步长，公式中 的第一项 由如下形式计算(经过一系列推导并略去u的三阶及以上导数)：

[0067]

[0068]

[0069] 其中 Δ是拉普拉斯算子，H(u)是u的Hessian阵。(0)
当b取零时，就可得到全变差的下降公式。按照上述迭代公式(4)，初值选为w ＝T -1 T T (k)
(ΦΦ+ηI) Φy，η为参数，y＝(y1，y2，...，yn)，每步更新w 直至其收敛。

[0070] (b)滞后的线性方程组迭代法(IagLE)

[0071] 由于TV的欧拉拉格朗日偏微分方程(1)具有相对较简单的形式，首先从TV的求解来推导。将PDE公式(1)中的非线性项 的散度算子展开得到：

[0072]

[0073] 将u的高斯径向基函数组合的形式公式(3)代入上式，并将参数zi用所有训练样本点xi代替，此时基函数的个数m就等于训练样本的个数n，经过一系列推导后得到如下的方程组：

[0074]

[0075] 其中d为数据的维数，|·|为向量的L2范数，把g固定可以得到关于w的线性方程组。于是利用滞后的思想，本发明提供了另外一种迭代解法，称之为滞后的线性方程组迭代法(IagLE)：

[0076] 1)给w一个随机的初值w(0)然后计算出g(0)。

[0077] 2)利用最小二乘方法求解关于w的线性方程组(5)，给出一个新的w(k)并计算g(k)。

[0078] 3)迭代执行第2)步直至w收敛。

[0079] 对于EE方法具有复杂的欧拉拉格朗日方程(2)，将含有曲率的项固定，记为K＝2
a+bκ，于是可以得到类似的方程组：

[0080]

[0081] 将g和K都固定即可得到关于w的线性方程组。同样给w一个初值，用与TV相同的迭代方法，每步更新g和K直至w收敛。

[0082] 在求解线性方程组的时候，假设该线性方程组形式上为Ψw＝y，Ψ为形式上简化的矩阵。由于w的模有时会非常大使得线性方程组变成坏条件的，一个比较好的求解策略是求解如下的正则化的最小二乘问题：

[0083]

[0084] 其中η为正则化参数，其解为w＝(ΨTΨ+ηI)-1ΨTy。于是滞后的线性方程组迭代法中有三个参数：高斯径向基函数中的参数c，能量泛函中的正则化因子λ和求解线性方程组的参数η。

[0085] 将得到的w代入基函数的线性组合表达式(3)，即可得到函数u的近似解析表达式。该近似解析表达式的零水平集为二类分类边界，最初得到的是一个二类分类器，即在预测时，将样本代入u中，若函数值大于零则预测标签为1，小于等于零则标签为-1。而此实施例中的手写体数字共10类，是个多类分类问题，采用一种常用的一对多的策略，即训练10个二类分类器，再将这10个二类分类器组合得到最终的分类器。图2(b)表示的是对于图2(a)的识别结果。

[0086] 在求解过程中对于EE方法固定b＝0.01，于是对于TV和EE的GD解法均只有两个参数c和λ，lagLE解法有三个参数c，λ和η，此处采用对数据集五折交叉验证来选择最优参数，并与SVM和BPNN(反向传播神经网络算法)进行分类效果的对比。表2给出的是各种方法的准确率对比，此处的准确率是各方法五折交叉验证中最优参数对应的最优准确率。从表2中可以看出本发明提出的基于全变差和欧拉弹性能量的两种方法在USPS数据集上效果超过了SVM和BPNN。

[0087] 表2各种方法在USPS数据集上准确率的对比结果(％)

[0088]

[0089] 实施例二：应用于其他一些常用分类数据

[0090] 本实施例基于Iibsvm网站以及UCI机器学习库中的8个分类的数据集，包括两类及多类数据。对于所有数据集都归一化到[0，1]区间，操作步骤与实施例一中相同。对于所有方法都仍然用五折交叉验证来选取最优参数，各方法的最优准确率对比如表3所示：

[0091] 表3各方法的分类准确率对比(％)

[0092]

[0093] 从表3中可以看出本发明提出的TV和EE模式识别方法的IagLE解法在总体上比GD的要好，EE的效果略胜于TV的效果，他们在所有数据集上都比BPNN的准确率要高。EE方法在IagLE解法下在六个数据集上超过了SVM，在其余两个数据上的效果与SVM也相差不大，可以看出本发明提出的基于全变差和欧拉弹性能量的模式识别方法可以与现在很成熟的SVM算法相媲美。