机器学习中的范数规则化

L0、L1与L2范数

机器学习的目标：在规则化参数的同时最小化误差

监督学习的通用目标

• 第一项：误差
• 第二项：规则化函数，约束我们的模型尽量的简单

对于第一项Loss函数，如果是Square loss，那就是最小二乘了；如果是Hinge Loss，那就是著名的SVM了；如果是exp-Loss，那就是牛逼的 Boosting了；如果是log-Loss，那就是Logistic Regression了。

绿色的线为 square loss ，蓝色的线为 hinge loss， 红的的线为负 log 损失。
hinge loss (E(z)=max(0,1-z))

yi时候正确的输出，wx+b是预测值，只有当他们符号相同时，loss为0，否则loss function就会变大。loss function是不能微分的，只能求它的次梯度subgradient：

c即是它的次导数

对于第二项

• L0范数是指向量中非0的元素的个数
• L1范数是指向量中各个元素绝对值之和，是L0范数的最优凸近似，任何的规则化算子，如果他在Wi=0的地方不可微，并且可以分解为一个“求和”的形式，那么这个规则化算子就可以实现稀疏。
  好处：特征选择，可解释性

• L2范数：它的回归叫“岭回归”，也叫它“权值衰减”，可以防止过拟合。 L2范数是指向量各元素的平方和然后求平方根。
  好处：防止过拟合，优化计算（有助于处理 condition number不好的情况下矩阵求逆很困难的问题）
  L1和L2的区别：

  
  最小化的过程坡度变化， L1人称Lasso，L2人称Ridge。
  L1在和每个坐标轴相交的地方都有“角”出现，即更多的0

核范数与规则项参数选择

核范数||W||*是指矩阵奇异值的和。矩阵奇异值是矩阵奇异值分解后中间的对角矩阵的对角线上的元素。
假如rank (X)远小于m和n，则我们称X是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出，可见它包含大量的冗余信息。
rank(w)的凸近似就是核范数||W||*。
应用：

• 矩阵填充（用户对物品的喜好矩阵的填充）

• 鲁棒主成分分析：将含有噪声的矩阵分解成低秩的（不含噪声）和稀疏的（噪声）矩阵相加。

  
  含噪声的矩阵=...
  转化为凸优化问题

• 背景建模

  
  背景：低秩矩阵，前景：稀疏矩阵