一种新型直接优化NDCG的排序模型构造算法

针对现有直接优化NDCG的排序算法或基于虚梯度或基于结构化学习,其得到的模型均不够精确,提出一种新的排序算法.算法以多类SVM为框架,在此基础上设计了一个面向NDCG的目标函数.考虑到该函数的非光滑性,提出使用割平面算法进行求解,同时注意到已有割平面算法可能存在的"主问题"非单调递减,会降低算法的收敛速度,进而设计了一种高效的线性搜索算法对割平面的选择进行改进,确保了"主问题"的单调递减.基准数据集上的实验证明了所提算法的有效性.

训练结构化支持向量机的优化切平面法

结构化支持向量机是机器学习中描述结构化输出问题的一种新模型,对其进行训练是一个典型的非光滑凸优化问题,最常用的训练算法是切平面法。切平面法中原问题的目标函数往往会发生振荡,因此一般需要加入线搜索环节。但是还没有针对结构化支持向量机的高效的线搜索方法。该文提出了一种优化的切平面法,通过二次插值来进行近似线搜索,并将其应用到结构化支持向量机的训练中。在多类分类上的实验表明:该算法的迭代次数接近精确线搜索,而每次迭代的计算量保持不变。在序列分类上的实验表明:该算法在训练其他复杂类型的结构化支持向量机时仍然比当前主流算法效率高很多。