【机器猫说机器学习】如何避免机器学习中的过拟合-FISTA

【什么是过拟合】

Ref: 维基百科-过拟合

【要解决什么问题】

首先看看这是一个什么问题？

其中y和A是已知的,b是噪声，目的是求x。m是样本量，n是特征维度。通常的做法是设计一个目标函数square loss，使这个目标函数最小化。当前，我们可以设计不同的loss函数，loss如果是square loss，那就是最小二乘；如果是hinge loss，那就是svm；如果是exp-loss，那就是boosting；如果是log-loss，那就是logistic regression；不同的loss函数，具有不同的拟合特性。

用square loss举个栗子，当m=n，并且A是非奇异的时候，方程是有解的。但是更多情况，是m<n 或者m=n 但是rank（A)<n，这种情况下，A就是ill-conditioned，方程往往有无穷解或者无解，失去了生活的意义。

【怎么解决呢】

我们的目标是求解x，而且x是稀疏的，那为什么不利用这个条件呢？最easy的方法，在loss后面加一个正则化项。正则化项可以是2范数，也可以是1范数，甚至可以是q范数（0<q<1）。[知识点] 当q<1，就能得到稀疏解，q越小效果越好；当0<q<0.5，得到的稀疏解效果差不多；所以，q=0.5可以得到比q=1更好的稀疏解，具体可以去查下西交徐宗本院士的工作。这里我们仅介绍L1的情况。

通俗的说，loss函数目的是在训练集上最小化empirical risk error，但是当我们学习一个model，希望具备良好的泛化性能。因此，增加一个正则化项，用来平衡模型的structural risk 和 exmpirical risk。

【ISTA和FISTA】

ok， 回顾下我们要解决的是什么问题：

要解决这个问题，我们先要了解下什么是 soft thresholding：

其中S是问题P的最优解。博客写公式真的很麻烦，证明过程请参考下图：

好，现在的问题是，如何把L1正则化问题写成soft thresholding function：

求解的迭代过程可以写成：xk = soft（x k-1）

FISTA和ISTA的不同在于每次迭代中，approximate function的starting point不一样

上式具体的推导过程，请参考Appendix2

这样，我们就求解得到了稀疏解。