论文标题
从有限集中选择的最佳模型的确切路径的线性时间动态编程
Linear time dynamic programming for the exact path of optimal models selected from a finite set
论文作者
论文摘要
许多学习算法都是根据查找模型参数来制定的，这些参数最大程度地减少了数据拟合损耗功能以及正常器。当常规化器涉及L0伪字符时，由此产生的正规化路径由一组有限的模型组成。用于计算正规化路径中断点的最快现有算法在模型数量中是二次的，因此它缩放到高维问题。我们提供了新的正式证明，即动态编程算法可用于在线性时间内计算断点。更改点检测问题的经验结果表明，相对于网格搜索和先前的二次时算法的准确性和速度提高了。
Many learning algorithms are formulated in terms of finding model parameters which minimize a data-fitting loss function plus a regularizer. When the regularizer involves the l0 pseudo-norm, the resulting regularization path consists of a finite set of models. The fastest existing algorithm for computing the breakpoints in the regularization path is quadratic in the number of models, so it scales poorly to high dimensional problems. We provide new formal proofs that a dynamic programming algorithm can be used to compute the breakpoints in linear time. Empirical results on changepoint detection problems demonstrate the improved accuracy and speed relative to grid search and the previous quadratic time algorithm.
