论文阅读——Efficient and Robust Feature Selection via Joint L2,1-Norms Minimization

本文主要是介绍论文阅读——Efficient and Robust Feature Selection via Joint L2,1-Norms Minimization，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、前言

最近因为对结构化多任务学习，以及对带范数目标函数求解的学习，一直都很想求解带L2,1范数的目标函数（其实这只是个过程），针对这样的不光滑目标函数，梯度下降法并不合适。

虽然sklearn中的MultiTaskLasso也是这样的目标函数，并且使用了坐标下降法来求解，但是当目标函数中的损失函数也用L2,1范数时我又懵圈了。

正当我琢磨是不是能把两部分合在一起求解一个L2,1范数时（其实是数学底子不够，对优化方法了解太少），在一篇论文的参考文献里看到这篇十年前的文章。该文章的目标函数在损失函数和正则化两部分都使用了L2,1范数，同时作者也给出了一种迭代的求解方法，所以学习并在此记录一下。

二、正文

1.Reformulation as A Constrained Problem

因为是十年前的文章，就不介绍背景了。直接放出主角——要求解的目标函数：

首先将上述目标函数变为带约束的形式，如下：

把上面的问题改写成：

令A和U如下：


则目标函数进一步改写成式（1）：

一般认为，L2,1范数最小化问题比L1范数最小化问题更难解决。现有的算法通常将其转化为二次锥规划(SOCP)或半定规划(SDP)问题，可采用内点法或bundle法（并没有听过，只能这么写了）求解。然而，求解SOCP或SDP在计算上非常昂贵，这限制了它们在实践中的应用。

最近（十年前），人们提出了一种有效的算法来解决式(1)，方法是将问题复杂地重新表述为min-max problem，然后应用近似方法求解。结果表明，该算法比现有的算法具有更高的效率。然而，该算法是一种梯度下降类型的方法，收敛速度非常慢。此外，该算法可用于求解特定问题，不能直接应用于求解其他一般的L2,1范数最小化问题。

在下一小节中，是作者提出的一个非常简单的方法来求解式（1），同时这种方法也很容易应用到其他一般的L2,1范数最小化问题中。

2.An Efficient Algorithm to Solve the Constrained Problem

式（1）的拉格朗日函数可以写为：

求上式对U的偏导并令其为0，得到式（2）：

其中D是对角矩阵，第i个元素为：

左乘AD^-1，并有AU = Y，可以得到如下式子：

将上式代回求式（2），得到式（3）：

由于式(1)中的问题是一个凸问题，当且仅当式(3)满足时，U是该问题的全局最优解。注意，D依赖于U，因此也是一个未知变量。

作者提出了如下的迭代算法来获得满足式(3)的解U：

在每次迭代中，用当前的D计算U，然后根据当前计算的U更新D。迭代过程不断重复，直到算法收敛。

（看到这里突然觉得这个目标函数真的很好编代码）

3.Experimental Results

之后作者分析了算法的收敛性，并在六个公开数据集上做了特征选择以及分类，以此验证方法的有效性。实验结果如下，在此就不再介绍，感兴趣可以阅读原文。

4.Conclusions

总结一下作者的工作：
1.提出了一种新的有效而稳健的特征选择方法，该方法在损失函数和正则化两个方面都使用L2,1范数最小化。
2.给出了一种有效的求解算法，证明了算法的收敛性。
3.对两个生物信息学任务(六个数据集)进行了大量的实证研究，证明了作者提出方法的性能。

参考：

Nie, F., Huang, H., Cai, X., & Ding, C. (2010). Efficient and robust feature selection via joint ℓ 2;1-norms minimization. Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010, 1–9.

这篇关于论文阅读——Efficient and Robust Feature Selection via Joint L2,1-Norms Minimization的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---