線形回帰を試みるのに合理的なシステムの大きさはどれくらいですか？
具体的には、最大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) 行列を生成します
2 つの (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) 行列を生成します
- (m × m) 行列と (mx 1) 行列の最終的な行列乗算には、O(m²)の時間がかかります
したがって、Big-O の実行時間はO(n⋅m + n⋅m² + m³ + n⋅m + m²)です。
これで、次のことがわかりました。
- m² ≤ m³
- n·m ≤ n·m²
したがって、漸近的に、実際の Big-O の実行時間はO(n⋅m² + m³) = O(m²(n + m))です。
しかし、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 に答える