标题： 有限集合中选择的最优模型的精确路径的线性时间动态规划 显示英文标题

标题： 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.