尝试对多大的系统进行线性回归是合理的？
具体来说：我有一个具有约 300K 样本点和约 1200 个线性项的系统。这在计算上可行吗？
问问题
15388 次
4 回答
8
线性回归计算为 (X'X)^-1 X'Y。
如果 X 是 (nxk) 矩阵：
(X' X) 花费 O(n*k^2) 时间并产生一个 (kxk) 矩阵
(kxk) 矩阵的矩阵求逆需要 O(k^3) 时间
(X' Y) 花费 O(n*k^2) 时间并产生一个 (kxk) 矩阵
两个 (kxk) 矩阵的最终矩阵乘法需要 O(k^3) 时间
所以 Big-O 的运行时间是 O(k^2*(n + k))。
另见：http ://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra
如果您喜欢它，看起来您可以使用 Coppersmith–Winograd 算法将时间缩短到 O(k^2*(n+k^0.376))。
于 2010-12-03T04:17:06.187 回答
5
您可以将其表示为矩阵方程：
其中矩阵
为300K行1200列，系数向量
为1200x1，RHS向量
为1200x1。
如果你将两边都乘以矩阵的转置
，你就有一个未知数的方程组，即 1200x1200。您可以使用 LU 分解或您喜欢的任何其他算法来求解系数。（这就是最小二乘法正在做的事情。）
所以 Big-O 的行为类似于 O(m m n)，其中 m = 300K 和 n = 1200。您需要考虑转置、矩阵乘法、LU 分解和前后替换以获得系数。
于 2009-12-23T20:49:16.590 回答
2
线性回归计算为(X'X)^-1 X'y。
据我所知，y是结果向量（或者换句话说：因变量）。
因此，如果X是 (n × m) 矩阵并且y是 (n × 1) 矩阵：
- (n × m) 矩阵的转置需要O(n⋅m)时间并产生 (m × n) 矩阵
- (X' X)花费O(n⋅m²)时间并产生一个 (m × m) 矩阵
- (m × m) 矩阵的矩阵求逆需要O(m³)时间
- (X' y)花费O(n⋅m)时间并产生一个 (m × 1) 矩阵
- a (m × m) 和 (mx 1) 矩阵的最终矩阵乘法需要O(m²)时间
所以 Big-O 的运行时间是O(n⋅m + n⋅m² + m³ + n⋅m + m²)。
现在，我们知道：
- 平方米 ≤ 立方米
- n⋅m ≤ n⋅m²
所以渐近地，实际的 Big-O 运行时间是O(n⋅m² + m³) = O(m²(n + m))。
这就是我们从 http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra得到的
但是，我们知道情况 n → ∞ 和 m → ∞ 之间存在显着差异。 https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variables
那么我们应该选择哪一个呢？显然，更可能增长的是观察的数量，而不是属性的数量。所以我的结论是，如果我们假设属性的数量保持不变，我们可以忽略 m 项，这是一种解脱，因为多元线性回归的时间复杂度变成了单纯的线性O(n)。另一方面，当属性数量大幅增加时，我们可以预期我们的计算时间会大幅增加。
于 2020-05-06T16:47:21.290 回答
0
封闭式模型的线性回归计算如下：
RSS(W) = -2H^t (y-HW)
所以，我们解决
-2H^t (y-HW) = 0
那么W值为
W = (H^t H)^-1 H^2 y
其中： W : 是预期权重的向量 H : 是特征矩阵 N*D 其中 N 是观察数，D 是特征数 y : 是实际值
那么，复杂度
H^t H 是 n D^2
转置的复杂度为 D^3
所以，复杂度
(H^t H)^-1 is n * D^2 + D^3
于 2016-03-01T18:53:26.413 回答