机器算法验证 - 简单线性回归的时间复杂度大号1L1规范 - 吾爱随笔录

机器算法验证回归算法

2022-03-30 15:24:26

我来自计算机科学背景。我正在考虑使用简单的线性回归 $L_1$ 距离。

我们得到积分 $(x_1,y_1),\ldots,(x_n,y_n)\in \mathbb{R}^2$ . 我们有兴趣找到一条线 $f(x) = ax+b$ , 这样

\sum_{i = 1}^{n} | y_{i} - f (x_{i}) |

$\sum_{i=1}^n |y_i - f(x_i)|$ 被最小化。

我做了一些初步的文献搜索，似乎人们使用线性规划解决了这个问题。我有兴趣在点数方面找到最快的算法。也就是说，我正在寻找如下所示的参考资料

简单的线性回归 $L_1$ 范数可以解决 $O(T(n))$ 时间，地点 $n$ 是点数。

1个回答

有一个 $O(n^2)$ 运行时间算法。

很容易推导出：存在一条包含给定点之一的最优线（实际上，至少有 2 个点）。存在一个 $O(n)$ 时间算法来决定通过给定点的最佳线。基本上是加权中值计算。总之，它意味着一个 $O(n^2)$ 运行时间算法。

我知道的第一篇使用这个想法的论文如下。

布卢姆菲尔德，彼得；Steiger，William，最小绝对偏差曲线拟合，SIAM J. Sci。统计。计算。1, 290-301 (1980)。 ZBL0471.65007。

编辑 1： 使用计算几何中的高级工具，可以提高运行时间以 $\tilde{O}(n^{4/3})$ .

编辑2： 有一篇论文给出了 $O(n\log^2 n)$ 时间算法。

米吉多，宁录；Tamir, Arie，寻找最短距离线，SIAM J. 代数离散方法 4，207-211 (1983)。 ZBL0517.05007。

还有另一篇论文我仍然需要验证，它解释了 $O(n)$ 时间是可能的。事实上，似乎 $L_1$ 线性回归 $d$ 尺寸可以解决 $O(n)$ 时间如果 $d$ 是一个常数。

Zemel，Eitan，线性多项选择背包问题及相关问题的 O(n) 算法，Inf。过程。莱特。18, 123-128 (1984)。ZBL0555.90069。

其它你可能感兴趣的问题