L0,L1,L2范数及其应用
在线性代数，函数分析等数学分支中，范数（Norm）是一个函数，其赋予某个向量空间（或矩阵）中的每个向量以长度或大小。对于零向量，另其长度为零。直观的说，向量或矩阵的范数越大，则我们可以说这个向量或矩阵也就越大。有时范数有很多更为常见的叫法，如绝对值其实便是一维向量空间中实数或复数的范数，而Euclidean距离也是一种范数。
范数的一般化定义：设p≥1p≥1的实数，p-norm定义为：
p-范数此处，当p=1时，我们称之为taxicab Norm，也叫Manhattan Norm。其来源是曼哈顿的出租车司机在四四方方的曼哈顿街道中从一点到另一点所需要走过的距离。也即我们所要讨论的l1范数。其表示某个向量中所有元素绝对值的和。
而当p=2时，则是我们最为常见的Euclidean norm。也称为Euclidean distance。也即我们要讨论的l2范数。
而当p=0时，因其不再满足三角不等性，严格的说此时p已不算是范数了，但很多人仍然称之为l0范数。 这三个范数有很多非常有意思的特征，尤其是在机器学习中的正则化（Regularization）以及稀疏编码（Sparse Coding）有非常有趣的应用。
下图给出了一个Lp球的形状随着P的减少的可视化图。
1- L0 范数
0-范数上面的公式仍然让人不是很明白，0的指数和平方根严格意义上是受限条件下才成立的。因此在实际应用中，多数人给出下面的替代定义：
0-范数2- L1 范数
对于向量X，其L1范数的定义如下：
1-范数 L1 VS L2但由于L1范数并没有平滑的函数表示，起初L1最优化问题解决起来非常困难，但随着计算机技术的到来，利用很多凸优化算法使得L1最优化成为可能。
3- L2 范数
当然范数中最常见，也最著名的非L2范数莫属。其应用也几乎包括科学和工程的各个领域。定义公式如下：
2-范数也Euclidean Norm，如果用于计算两个向量之间的不同，即是Euclidean Distance.
欧几里德范数的最优化问题可以用如下公式表述：
最优化借助拉格朗日乘子，我们便可以解决该最优化问题。由L2衍生，我们还可以定义无限norm，即l-infinity norm：
无穷范数
无穷范数一眼看上去上面的公式还是有点tricky的。我们通过一个简单的数学变换，假设X_j是向量中最大的元素，则根据无限大的特性，我们可以得到：
则根据公式无穷范数的定义，我们可以得到：
因此我们便可以说l-infinity norm是X向量中最大元素的长度。
无穷范数4- 机器学习中的应用
不知道有多少人是因为机器学习中的正则化和特征选择等才开始了解这些范数的，至少我是。L0范数本身是特征选择的最直接最理想的方案，但如前所述，其不可分，且很难优化，因此实际应用中我们使用L1来得到L0的最优凸近似。L2相对于L1具有更为平滑的特性，在模型预测中，往往比L1具有更好的预测特性。当遇到两个对预测有帮助的特征时，L1倾向于选择一个更大的特征。而L2更倾向把两者结合起来。
4-1 正则化
Regularized Logistic Regression
Regularized Neural Network
Soft Margin SVM
而加上L2正则项后，其变为：
从而可以直接求逆，改善了condition number。
而对于无解析解，通过迭代优化的算法，L2正则化通过将目标函数变为λ-strongly convex（λ强凸），有效的加快了其收敛速度。
4-2 贝叶斯先验
正则化项从贝叶斯学习理论的角度来看，其相当于一种先验函数。即当你训练一个模型时，仅仅依靠当前的训练集数据是不够的，为了实现更好的预测（泛化）效果，我们还应该加上先验项。而L1则相当于设置一个Laplacean先验，去选择MAP（maximum a posteriori）假设。而L2则类似于 Gaussian先验。如下图所示：
从上图可以看出，L1先验对大值和小值的tolerate都很好，而L2先验则倾向于均匀化大值和小值。
4-3 特征选择与稀疏编码
机器学习社区里通常把特征选择的方法分为三种。一种是基于统计学的一些方法，对特征进行预筛选，选出子集作为模型输入。如统计推理使用的假设检验，P值。另一种是采用某种成熟的学习算法进行特征选择，如决策树中采用信息增益来选择特征。还有一种便是在模型算法中进行自动特征选择。而L1范数作为正则化项，其特征选择的图谱倾向于spiky，实现了有效的特征选择。
稀疏编码也是想通过寻找尽可能少的特征表达某个输入的向量X。
其中ϕiϕi是所要寻找的基向量，a(j)iai(j)是我们要优化的各个基向量的权重。最右边的表达式便是其正则化惩罚项，在这里也称Sparse Cost。实际中我们通常便用L1范数。
加入两个题目
题目1 题目25 参考