Sparse Online Learning via Truncated Gradient
Sparse Online Learning via Truncated Gradient
复制标题
DOI：
10.5555/1577069.1577097
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
J. Langford;Lihong Li;Tong Zhang
中科院分区：
文献类型：
--
作者：
J. Langford;Lihong Li;Tong Zhang
我们提出了一个通用的方法，称为截断梯度诱导稀疏的权值凸损失的在线学习算法。该方法具有几个基本属性。首先，稀疏度是连续的-一个参数控制从没有稀疏化到总稀疏化的稀疏化速率。其次，该方法是理论上的动机，它的一个例子可以被看作是流行的L1正则化方法在批量设置的在线对应。我们证明稀疏率小的结果，在只有小的额外的遗憾，就典型的在线学习的保证。最后，该方法在经验上运作良好。我们将其应用于几个数据集，并发现具有大量特征的数据集，大量的稀疏性是可验证的。
We propose a general method called truncated gradient to induce sparsity in the weights of online-learning algorithms with convex loss. This method has several essential properties. First, the degree of sparsity is continuous—a parameter controls the rate of sparsification from no sparsification to total sparsification. Second, the approach is theoretically motivated, and an instance of it can be regarded as an online counterpart of the popular L1-regularization method in the batch setting. We prove small rates of sparsification result in only small additional regret with respect to typical online-learning guarantees. Finally, the approach works well empirically. We apply it to several datasets and find for datasets with large numbers of features, substantial sparsity is discoverable.