ما هو Bigo من الانحدار الخطي؟
-
21-09-2019 - |
سؤال
ما حجم النظام الذي من المعقول محاولة القيام بانحدار خطي؟
على وجه التحديد: لدي نظام مع ~ 300k عينة ونقاط ~ 1200 مصطلحات خطية. هل هذا ممكن من الناحية الحسابية؟
المحلول
يمكنك التعبير عن هذا كمعادلة مصفوفة:
حيث المصفوفة هو 300 ألف صفوف و 1200 عمود ، متجه معامل هو 1200x1 ، وناقل RHS هو 1200x1.
إذا كنت تضاعف كلا الجانبين من خلال تحويل المصفوفة , ، لديك نظام من المعادلات للمجهولون 1200 × 1200. يمكنك استخدام تحلل LU أو أي خوارزمية أخرى ترغب في حلها للمعاملات. (هذا ما تفعله المربعات الصغرى.)
لذا فإن السلوك الكبير O هو شيء مثل O (M.مn) ، حيث M = 300k و n = 1200. كنت تمثل transpose ، وضرب المصفوفة ، والتحلل LU ، والاستبدال الأمامي للحصول على المعاملات.
نصائح أخرى
يتم حساب الانحدار الخطي كـ (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_mathematicy_operations#matrix_algebra
إذا كنت تتخيل ، يبدو أنه يمكنك الحصول على الوقت لأسفل إلى O (K^2*(N+K^0.376)) مع خوارزمية Coppersmith -Winograd.
يتم حساب الانحدار الخطي لنموذج الشكل المغلق على النحو التالي: مشتق من
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