Press "Enter" to skip to content

论文笔记:Support Vector Method For Novelty Detection(Schölkopf) OCSVM经典论文“Schölkopf et…

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

目录

 

1. 概要

 

论文名直译过来就是:用于新颖性检测的支持向量方法

 

Schölkopf—OCSVM(其实这篇论文中并没有出现OCSVM,应该是后来被冠以了这个名称?以下简称为OCSVM)是要解决这样一个问题:给定一个遵循某一个概率分布P的数据集,找到一个输入空间的简单子集S,使得任意从P中采样的样点落在S之外的概率由一个位于(0,1)区间内的先验参数 指定。

 

这个算法可以看作是传统的用于监督学习中的分类问题的支持向量机(SVM)算法向无监督学习的一个自然的扩展。

 

(从结果来看)OCSVM将所有(正常的)训练数据点与特征空间的原点通过特征空间的超平面分离开来,并且使得该超平面与原点的距离最大化(i.e. with maximum margin)。这就导致了一个二值函数This results in a binary function which captures regions in the input space where the probability density of the data lives. 当数据位于包含训练数据的一个小区域内时该函数返回“+1”,否则返回“-1”。

 

2. 数学模型

 

与经典的SVM一样,OCSVM的优化问题仍然是一个二次规划(quadratic programming)问题。其数学表述与传统的SVM的虽然略有不同,但是其相似点还是显而易见的。如下所示:

 

考虑训练数据 ,为了简单起见,可以认为 表示训练数据集。考虑从训练数据集到一个点积(dot-product[注1])特征空间的映射 ,使得该映射的像空间的点积可以通过一个简单的核函数(kernel function)进行评估:

 

 

一个最常用的核函数是高斯核函数:

 

 

注意,如非特别指出,这里x,y等均指 上的向量。不同的核函数就代表着输入空间上的不同的非线性转换估计算子。

 

基于以上铺垫,上述二次规划问题可以表述为:

 

 

(3)

 

对应的判决函数为:

 

 

(4)

 

其中 表示松弛变量,代表目标函数中的惩罚项。 的含义参见下一节说明。

 

经过( Using Lagran ge Technique ) 推导以上二次规划问题的对偶问题为:

 

 

基于以上对偶问题的解{  } ,并基于式(1)所定义的点积,可以得到判决函数可以转换称为以下形式(SV expansions):

 

 

其中非零的   对应的样本数据 称为支撑向量(SV:Support Vector)。

 

这个问题可以通过标准的二次规划流程(QP routine, Quadratic programming)来解,当然也可以利用它的约束条件的简单性,而采用SMO的一个变体来解决。

 

对于任何既不在上边界也不在下边界的 ,它所对应的样本数据 均满足:

 

 

这个性质可以用来计算 ρ

 

[注1] A dot product is a very specific inner product that works on   (or more generally , where F is a field) and refers to the inner product given by: . 内积(inner product)是一个更广泛的概念,点积(dot-product)是内积一个特例

 

3. 参数的物理含义

 

类似于二分类SVM中的参数C,作为正则化参数,其物理含义(原论文Proposition 1)为:

 

1. 为(训练集中)异常值的比例设置了一个上限(即异常值所占比例不得超过这个值)

 

2.  是训练数据集里面做为支持向量的样本的比例的下界(即支持向量所占比例不得低于这个值)         因为这个参数的重要性,这种方法也被称为 ν-SVM

 

ν→0 ,拉格朗日乘子的上边界趋向于无穷大,式(5)中的第2个不等于约束就变得无效了(小于等于无穷大等于没有约束)。同样由(3)式可知,此时对于错误的惩罚变得无穷大,因此问题退化为相应的hard margin algorithm.

 

另一方面,当 ν→∞ ,约束条件将导致唯一的解,即 . 在这种情况下,对于积分值归一化为1的核函数,判决函数对应于a threshold Parzen windows estimator.

 

参数 ρ 刻画的是超平面到零点的距离,也就是decision margin.

 

4. Experiments

 

读一篇论文的最重要的环节当然是复现论文中的实验结果。不过本渣目前力量还不够,还要继续学习学习等完成热身后,再来看看能不能复现论文中的实验结果。

 

敬请期待。。。

 

Ref: Schölkopf et al , Support Vector Method For Novelty Detection, NIPS 1999

 

相关博客: 论文笔记:Support vector domain description(Tax,Duin1999) https://blog.csdn.net/chenxy_bwave/article/details/120906276

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注