【ＳＶＭ在距离空间中的研究】 空间中点到平面的距离
时间：2018-12-23 19:53:42 来源：雅意学习网 本文已影响 人 
摘 要：本文提出了一种基于支持向量机思想的对任意距离空间求解最大分类间隔的方法，其优化问题可以用输入空间的距离来表示。首先我们将输入空间等距嵌入到Hilbert空间，在线性的Hilbert空间对优化问题进行线性处理，但是这种方法只适用于特定的距离空间。在原方案的基础上我们研究了对任意距离空间求解最大分类间隔的方法。
关键词：距离空间 分类间隔 凸集 核函数
1 引言
距离空间又称度量空间，它是一种拓朴空间，其上的拓朴由指定的一个距离决定。对于距离空间(?掊，ρ)，?掊是一个非空集，ρ叫做?掊上的一个距离。通常SVM问题都是以核函数k作为研究对象，其分类结果与k的选择有关。由于分类间隔从几何形式上讲它等于两个互不相交凸集间的距离，所以我们尝试将距离作为研究对象，把问题放在距离空间里讨论。但并不是所有的情况都是线性可分的，这时可以考虑将原空间等距嵌入到线性空间。一方面，使得输入空间的距离大小在嵌入后保持不变；另一方面，可以对问题进行线性处理。我们首先在Hilbert空间上用距离ρ表示该优化问题，但这必须在-ρ 条件正定的条件下进行。因此我们研究了能够适用于任意距离空间的距离分析方法，就是将任意距离空间等距嵌入到Banach空间，在线性的Banach空间用计算两凸集间的距离的方法求解最大分类间隔。
2 分类超平面与分类间隔
考虑线性可分的情况，分类超平面在泛函分析中的解释如下：
Hahn-Banach凸集分离定理。设E 和E 是Banach空间中两个互不相交的非空凸集，E 有内点，那么?埚S∈R及非零线性连续泛函g，使得超平面H分离E 和E ，换句话说，存在一个非零线性泛函g，使得
规范形式的超平面分类间隔大小为 ，即在约束条件y (w・x+b)≥1下求‖w‖ 的最小值。在这里我们讨论的不是如何求出分类函数中参数的具体值，而是采用距离空间的研究方法，用距离ρ来表示该优化问题。接下来根据Reproducing Kernel Hilbert Space（RKHS）理论来说明通常的SVM方法。
3 在Hilbert空间求解最大分类间隔
3.1 基于RKHS理论的SVM方法
首先给出正定函数与条件正定函数的概念：
定义1：集合?掊×?掊上的实值函数k正定当且仅当k对称且
显然正定函数一定是条件正定的。通过正定核函数来建立基于RKHS理论的希尔伯特空间H，其方法如下：
(1) 定义特征映射?准：
(2) 在特征空间定义有界线性算子f，f为?准 的线性组合，即f= a ?准 ；
(4) 建立完备的内积空间即Hilbert空间H。
根据以上定义，将SVM方法描述如下：输入空间?掊通过函数?准映射到Hilbert空间H，在H空间确定最优分类面。Riesz定理指出，任意一个线性连续函数都对应Hilbert空间的一个向量。最优分类面则对应着Hilbert空间上的线性连续函数。
3.2 用距离空间(?掊，ρ)做输入空间
通常我们对SVM问题的求解按以下步骤进行：
即都是通过核函数k将原空间转换到Hilbert空间。这一部分我们在集合?掊上定义距离ρ，将距离空间（?掊，ρ）作为输入空间等距嵌入到Hilbert空间：
下面的命题给出了用核函数k构造距离的一种方法，也可以有不同的形式［４］。
命题1：设集合?掊非空，k是?掊×?掊→R上的一个条件正定核函数，定义函数
则ρ是?掊上的一个距离且-ρ 是条件正定的。存在?掊→R上的函数h，使得
证明：若k条件正定，由(7)得
下面我们将生成的距离空间等距嵌入到Hilbert空间。
命题2：设（?掊，ρ）是命题1中定义的距离空间，
(1)（?掊，ρ）能够等距嵌入到Hilbert空间H；
(2)若核函数k有界，则H能连续嵌入到空间（C (?掊)，‖・‖ ），C (?掊)代表集合?掊上有界连续函数的全体。
证明：由命题1证明中的(8)式，可以通过条件正定核函数k得到正定核函数 ，由于两者定义了相同的距离，所以可用正定核函数 来建立基于RKHS理论的Hilbert空间H，其特征映射为?准 = (x，・)。
对任意的f∈H，
Schoenberg已于1938年提出了正定函数与条件正定函数的概念并证明了以上结论［５］。我们不难得到以下定理：
定理1：距离空间(?掊，ρ)等距嵌入到Hilbert空间的充分必要条件是-ρ 条件正定。
3.3用距离ρ表示SVM优化问题
根据前面的结论，我们可以尝试将距离ρ作为研究对象代入原问题。由(8)式定义了正定核函数 ，通过映射?准 = (x，・)将其代入基于RKHS理论的Hilbert空间。因为存在约束条件，所以化简后将(8)式中其余项略去，只留下条件正定核函数k，再将由k构造的距离ρ代入，优化问题最后表示为距离ρ的函数。
定理2：SVM问题可以通过距离空间（?掊，ρ）来求解，其中-ρ 条件正定。通过正定核函数将（?掊，ρ）等距嵌入到Hilbert空间。问题结果只与输入空间的距离ρ有关。
我们可以直接构造这样的距离ρ，使得-ρ 条件正定。虽然问题结果的表示只与距离ρ有关，但是通过条件正定核函数k来构造ρ可能更容易些。
4 在Banach空间求解最大分类间隔
由于只有在-ρ 条件正定时才能将输入空间(?掊，ρ)等距嵌入到Hilbert空间，所以上面的方法只适用于距离空间的一个子集。下面讨论如何对任意距离空间求解。我们的想法是将任意一个距离空间等距嵌入到Banach空间，再根据分类间隔大小等于两凸集间的距离求解。即
上式中 是?掊上的一个Banach空间，它是有界连续函数全体的一个子集。
4.1将任意距离空间等距嵌入到Banach空间
建立两个Banach空间。将距离空间（?掊，ρ）等距嵌入到第一个Banach空间，第二个Banach空间用来定义线性连续函数。设（?掊，ρ）是紧空间，任取x ∈?掊，定义映射：
令S=span{?准 ：x∈?掊}，即S为?掊上关于映射?准的线性包；T=span{ψ ∶x∈?掊}，即T为?掊上关于映射ψ的线性包。集合S的闭包 是一个Banach空间，在 中定义范数‖?准 ‖ = |?准 (y)|，?准 (y)∈ 。距离空间(?掊，ρ)通过映射?准等距嵌入到空间 ， 的对偶空间 与集合T的闭包 等距同构，因此可认为 与 等价。又定义范数：
4.2 在Banach空间求解两凸集间的距离
在Banach空间两个互不相交凸集间的距离大小等于最大分类间隔［３］。定义凸集如下：
为了便于计算，我们将问题放在T的有限维子空间研究。设有限集Z?奂?掊且Z的维数为m，根据定理4的平移不变性，任取一点x ，令x =z ，z ∈Z。得到|β |，约束条件：
以上优化问题可用线性方法解决，如果我们令Z=E，将得到和文献相同的结论。
根据定理4，我们写出原问题的对偶形式：
由于a 于β 之间的关系没有确定的公式，所以还不能直接通过a 来计算分类函数。原问题可以在有限集Z上得到近似结果，同样我们在对偶问题中也可以在Z上计算上确界。
结论与讨论
在这篇文章里我们给出了如何通过距离空间求解最大分类间隔的方法。将距离空间等距嵌入到Hilbert空间这只限于特定的距离空间。对于距离ρ的构造可以有多种形式，在解决一个实际问题时，如何根据具体的数据构造一个适当的距离ρ还没有固定的准则。更一般的，将任意距离空间等距嵌入到Banach空间的方法好于文献中的距离分类方法，但它与前一种方法的数学结构之间的联系，以及两种方法的推广能力如何仍有待研究。
参考文献：
［1］张恭庆，林源渠.泛函分析讲义.北京：北京大学出版社，2001.
［2］边肇祺，张学工等.模式识别（第2版）.北京：清华大学出版社，2000.
［3］K.P.Bennett，E.J.Bredensteiner，Dualityand Geometry in SVM classifiers， Proceedings of the Seventeenth International Conference on Machine Learning，2000，57-64.
［4］C.Berg，J.P.R.Cristensen，P.Ressel，Harmonic Analysis on Semigroups，Springer Verlag，New York，1984.
［5］B.Scholkopf，The Kernel Trick for Distanances，Neural Information Processing Systems(NIPS)，2000，13.
［6］W.Rudin，Functional Analysis，McGraw Hill，1991.
［7］T.Graepel，R.Herbrich，B.Scholkopf，A.Smola，P.Bartlett，K.R.Muller，K.Obermayer and R.Williamson，Classification on proximity Data with LP-machines，Internation Conference on Artificial Neural Networks，1999，304-309.
［8］E.Pekalska，P.Paclik，R.P.W.Duin，A Generalized Kernel Approach to Dissimilarity based Classification，Journal of Machine Learning Research，2001，2，175-211.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文
