ما هو Bigo من الانحدار الخطي؟

Question

ما حجم النظام الذي من المعقول محاولة القيام بانحدار خطي؟

على وجه التحديد: لدي نظام مع ~ 300k عينة ونقاط ~ 1200 مصطلحات خطية. هل هذا ممكن من الناحية الحسابية؟

Answer 1

يمكنك التعبير عن هذا كمعادلة مصفوفة:

حيث المصفوفة هو 300 ألف صفوف و 1200 عمود ، متجه معامل هو 1200x1 ، وناقل RHS هو 1200x1.

إذا كنت تضاعف كلا الجانبين من خلال تحويل المصفوفة , ، لديك نظام من المعادلات للمجهولون 1200 × 1200. يمكنك استخدام تحلل LU أو أي خوارزمية أخرى ترغب في حلها للمعاملات. (هذا ما تفعله المربعات الصغرى.)

لذا فإن السلوك الكبير O هو شيء مثل O (M.مn) ، حيث M = 300k و n = 1200. كنت تمثل transpose ، وضرب المصفوفة ، والتحلل LU ، والاستبدال الأمامي للحصول على المعاملات.

Answer 2

يتم حساب الانحدار الخطي كـ (x'x)^-1 x'y.

إذا كانت x مصفوفة (NXK):

1. (x 'x) يأخذ O (n*k^2) وينتج مصفوفة (kxk)

2. انعكاس المصفوفة لمصفوفة (KXK) يأخذ O (k^3) الوقت

3. (x 'y) يأخذ وقت O (n*k^2) وينتج مصفوفة (kxk)

4. الضرب المصفوفة النهائي لمصفوفتين (KXK) يأخذ O (k^3) الوقت

وبالتالي فإن وقت التشغيل Big-O هو O (K^2*(N + K)).

أنظر أيضا: http://en.wikipedia.org/wiki/computational_complexity_of_mathematicy_operations#matrix_algebra

إذا كنت تتخيل ، يبدو أنه يمكنك الحصول على الوقت لأسفل إلى O (K^2*(N+K^0.376)) مع خوارزمية Coppersmith -Winograd.

Answer 3

يتم حساب الانحدار الخطي لنموذج الشكل المغلق على النحو التالي: مشتق من

RSS (W) = -2H^T (Y -HW)

لذلك ، نحن نحل

-2H^T (Y-HW) = 0

ثم ، قيمة w

w = (h^t h)^-1 h^2 y

أين:ث: هل متجه الأوزان المتوقعةح: هل الميزات مصفوفة n*d حيث n هو عدد الملاحظات ، و d هو عدد الميزاتذ: هي القيمة الفعلية

ثم ، تعقيد

h^t h is n d^2

تعقيد التحويل هو d^3

لذلك ، تعقيد

(H^t H)^-1 is n * D^2 + D^3