与函数的凸性和凹性有关的混淆

计算科学 优化 凸优化 支持向量机
2021-11-25 22:49:33

我正在阅读这篇论文http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf与用于非线性分类的自适应多超平面机有关

在那篇论文中,他们提到了多类 SVM,每个类都有多个权重。

任何分类的损失是

l(xn,yn)=maxiϵy\yn(0,1+maxg(i,xn)g(yn,xn))

在哪里yn是第 n 个示例的标签,并且xn是特点。

当他们训练这个算法时,我有这种困惑。他们称之为 SVM MM(多超平面)。

他们说凸近似问题被定义为

minWP(W|z)=λ2||W||2+1Nn=1Nlcvx(W;(xn,yn);zn)

他们有凹项的地方g(yn,zn)替换为凸项wyn,znTxn.

我不确定我是否已经清楚地描述了它。但我也会附上论文的截图。问题是我不明白这有什么区别g(yn,zn)wyn,znTxn. 在我看来,它们是同一个词。

我可能会问很多。但是谁能提供一些信息?

在此处输入图像描述 在此处输入图像描述

我用红色矩形标记了我不明白的部分。我可能会问很多。但我没有得到那部分。为什么会这样?

1个回答

免责声明:我的大部分优化相关工作都是在非凸优化中完成的,而且我没有接受过任何支持向量机 (SVM) 方面的培训。

根据我从阅读 Wikipedia 和我的优化背景中得知的信息,我的猜测是他们选择用上限替换原始的非凸目标,以对原始问题制定凸限制。“损失项”看起来像是一个惩罚项,旨在确保这个特定 SVM 中超平面的法线向量都是不同的;在最小化问题的目标函数中用更大的凸项替换非凸项只会增加分配给“太相似”的法线向量的惩罚。

这种修改可能是为了使问题更容易解决;凸优化问题可以在多项式时间内求解(作为决策变量的数量、约束和存储输入所需的位数的函数),而非凸优化问题在多项式时间内无法求解,并且通常具有以下算法是指数运行时间(同样,作为决策变量数量的函数等)。所有这些指数运行时间算法都是猜测和检查的复杂变体,因为在没有理论突破的情况下,这种策略是我们能做的最好的,比如P=NP.