数据挖掘 - 线性回归的时间复杂度是多少？ - 吾爱随笔录

数据挖掘机器学习回归统计数据线性回归成本函数

2021-09-24 20:32:24

我正在使用线性回归，我想知道大 O 表示法的时间复杂度。没有优化算法（例如梯度下降）的线性回归的成本函数需要在权重组合的迭代中计算（作为蛮力方法）。这使得计算时间取决于权重的数量，并且显然取决于训练数据的数量。

如果 $n$ 是训练数据的数量， $W$ 是权重的数量，权重空间的每个分辨率设置为 $m$ 意味着每个权重都会迭代 $m$ 可能值的数量。那么这个线性回归的时间复杂度是

$O(m^Wn)$

这个对吗？

2个回答

这在很大程度上取决于您使用的“求解器”。

打电话 $n$ 观察次数和 $p$ 权重的数量，整体复杂度应该是 $n^2p+p^3$ .

实际上，在执行线性回归时，您正在执行复杂度为的矩阵乘法 $n^2p$ （评估时 $X'X$ ) 并反转得到的矩阵。它现在是一个方阵 $p$ 行，矩阵求逆的复杂度通常为 $p^3$ （虽然它可以降低）。

因此理论上的复杂性： $n^2p+p^3$ .

旁注

然而，数值模拟（使用 python 的 scikit 库）的时间复杂度似乎接近 $n^{0.72} p^{1.3}$

这可能是因为实际上没有实现完全反转（相反，系统可以使用梯度下降来求解），或者是因为还有其他方法可以校准线性回归的权重。

来源

为了清楚起见（因为@RUser4512 没有更新他的答案），在线性回归中你必须解决

(X^{'} X)^{- 1} X^{'} Y,

$(X'X)^{-1}X'Y,$ 在哪里

X

$X$ 是一个

n \times p

$n\times p$ 矩阵。现在，通常矩阵产品的复杂性

A B

$AB$ 是 O(abc)

A

$A$ 是

a \times b

$a\times b$ 和

B

$B$ 是

b \times c

$b\times c$ . 因此，我们可以评估以下复杂性：

a) 矩阵积 $X'X$ 复杂的 $O(p^2n)$ .

b) 矩阵-向量积 $X'Y$ 复杂的 $O(pn)$ .

c) 逆 $(X'X)^{-1}$ 具有复杂性 $O(p^3)$ ,

因此复杂度是 $O(np^2 + p^3)$ .

其它你可能感兴趣的问题