http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/
Sparsity 是当今机器学习领域中的一个重要话题。John Lafferty 和 Larry Wasserman 在 2006 年的一篇评论中提到:
Some current challenges … are high dimensional data,sparsity,semi-supervised learning,the relation between computation and risk,and structured prediction.John Lafferty and Larry Wasserman. Challenges in statistical machine learning. Statistica Sinica. Volume 16,Number 2,pp.307-323,2006.
Sparsity 的最重要的客户
大概要属 high dimensional data 了吧。现在的机器学习问题中,具有非常高维度的数据随处可见。例如,在文档或图片分类中常用的bag of words模型里,如果词典的大小是一百万,那么每个文档将由一百万维的向量来表示。高维度带来的的一个问题就是计算量:在一百万维的空间中,即使计算向量的内积这样的基本操作也会是非常费力的。不过,如果向量是稀疏的的话(事实上在 bag of words 模型中文档向量通常都是非常稀疏的),例如两个向量分别只有
当然高维度带来的问题不止是在计算量上。例如在许多生物相关的问题中,数据的维度非常高,但是由于收集数据需要昂贵的实验,因此可用的训练数据却相当少,这样的问题通常称为small
——我们一般用
使用 square loss 来进行学习的话,就变成最小化如下的问题
这里
然而,如果
解决 overfitting 最常用的办法就是 regularization ,例如著名的 ridge regression 就是添加一个
直观地来看,添加这个 regularizer 会使得模型的解偏向于 norm 较小的
其中
不过,特别是在像生物或者医学等通常需要和人交互的领域,稀疏的解除了计算量上的好处之外,更重要的是更具有可解释性
。比如说,一个病如果依赖于 5 个变量的话,将会更易于医生理解、描述和总结规律,但是如果依赖于 5000 个变量的话,基本上就超出人肉可处理的范围了。
在这里引入稀疏性的方法是用
该问题通常被称为 LASSO (least absolute shrinkage and selection operator) 。LASSO 仍然是一个 convex optimization 问题,不过不再具有解解析解。它的优良性质是能产生稀疏性,导致
可是,为什么它能产生稀疏性呢?这也是一直让我挺感兴趣的一个问题,事实上在之前申请学校的时候一次电话面试中我也被问到了这个问题。我当时的回答是背后的理论我并不是很清楚,但是我知道一个直观上的理解。下面我们就先来看一下这个直观上的理解。
首先,很 ridge regression 类似,上面形式的 LASSO 问题也等价于如下形式:
也就是说,我们将模型空间限制在
-
@H_404_2108@
ℓ1 -ball meets quadratic function.ℓ1 -ball has corners. It’s very likely that the meet-point is at one of the corners.