المصدر:
يعد الانحدار الخطي أحد الخوارزميات الأساسية للعديد من المجالات المتعلقة بتحليل البيانات. سبب هذا واضح. هذه خوارزمية بسيطة جدًا ومفهومة، وقد ساهمت في استخدامها على نطاق واسع لعشرات، إن لم يكن مئات، السنين. الفكرة هي أننا نفترض الاعتماد الخطي لمتغير واحد على مجموعة من المتغيرات الأخرى، ثم نحاول استعادة هذا الاعتماد.
لكن هذه المقالة لا تتعلق باستخدام الانحدار الخطي لحل المشكلات العملية. سننظر هنا في الميزات المثيرة للاهتمام لتنفيذ الخوارزميات الموزعة لاستعادتها، والتي واجهناها عند كتابة وحدة التعلم الآلي في . يمكن أن يساعدك القليل من الرياضيات الأساسية والتعلم الآلي والحوسبة الموزعة في معرفة كيفية إجراء الانحدار الخطي حتى عندما يتم توزيع بياناتك عبر آلاف العقد.
عن ماذا نتحدث؟
نحن نواجه مهمة استعادة الاعتماد الخطي. كبيانات مدخلة، يتم إعطاء مجموعة من المتجهات للمتغيرات المستقلة المفترضة، يرتبط كل منها بقيمة معينة للمتغير التابع. يمكن تمثيل هذه البيانات في شكل مصفوفتين:
الآن، نظرًا لأن الاعتماد مفترض، علاوة على ذلك، خطي، فسنكتب افتراضنا في شكل منتج مصفوفات (لتبسيط التسجيل، يُفترض هنا وأدناه أن الحد الحر للمعادلة مخفي خلف والعمود الأخير من المصفوفة يحتوي على وحدات):
يبدو الأمر وكأنه نظام من المعادلات الخطية، أليس كذلك؟ يبدو، ولكن على الأرجح لن يكون هناك حلول لمثل هذا النظام من المعادلات. والسبب في ذلك هو الضوضاء الموجودة في أي بيانات حقيقية تقريبًا. قد يكون السبب الآخر هو عدم وجود الاعتماد الخطي في حد ذاته، والذي يمكن مكافحته عن طريق إدخال متغيرات إضافية تعتمد بشكل غير خطي على المتغيرات الأصلية. خذ بعين الاعتبار المثال التالي:
المصدر:
هذا مثال بسيط على الانحدار الخطي الذي يوضح العلاقة بين متغير واحد (على طول المحور ) من متغير آخر (على طول المحور ). لكي يحصل نظام المعادلات الخطية المقابل لهذا المثال على حل، يجب أن تقع جميع النقاط تمامًا على نفس الخط المستقيم. ولكن هذا ليس صحيحا. لكنها لا تقع على نفس الخط المستقيم على وجه التحديد بسبب الضوضاء (أو لأن افتراض وجود علاقة خطية كان خاطئا). وبالتالي، من أجل استعادة العلاقة الخطية من البيانات الحقيقية، من الضروري عادةً تقديم افتراض آخر: تحتوي البيانات المدخلة على ضوضاء وهذا الضجيج له . يمكنك وضع افتراضات حول أنواع أخرى من توزيع الضوضاء، ولكن في الغالبية العظمى من الحالات، يتم أخذ التوزيع الطبيعي بعين الاعتبار، وهو ما سيتم مناقشته بشكل أكبر.
طريقة الاحتمالية القصوى
لذلك، افترضنا وجود ضوضاء عشوائية موزعة بشكل طبيعي. ماذا تفعل في مثل هذه الحالة؟ لهذه الحالة في الرياضيات هناك ويستخدم على نطاق واسع . باختصار، جوهرها يكمن في الاختيار وتعظيمه لاحقاً.
نعود إلى استعادة العلاقة الخطية من البيانات ذات الضوضاء العادية. لاحظ أن العلاقة الخطية المفترضة هي التوقع الرياضي التوزيع الطبيعي الموجود وفي الوقت نفسه احتمال يأخذ قيمة أو أخرى، بشرط وجود ما يمكن ملاحظته ، كالآتي:
دعونا الآن نعوض بدلا من ذلك и المتغيرات التي نحتاجها هي:
كل ما تبقى هو العثور على المتجه ، حيث يكون هذا الاحتمال هو الحد الأقصى. لتعظيم مثل هذه الوظيفة، من الملائم أن نأخذ أولاً لوغاريتمًا لها (سيصل لوغاريتم الدالة إلى الحد الأقصى عند نفس نقطة الدالة نفسها):
والذي بدوره يؤدي إلى تقليل الوظيفة التالية:
بالمناسبة، هذا ما يسمى الطريقة . في كثير من الأحيان يتم حذف جميع الاعتبارات المذكورة أعلاه ويتم استخدام هذه الطريقة ببساطة.
تحليل QR
يمكن العثور على الحد الأدنى للدالة المذكورة أعلاه من خلال إيجاد النقطة التي يكون فيها تدرج هذه الوظيفة صفرًا. وسيتم كتابة التدرج على النحو التالي:
هي طريقة مصفوفية لحل مشكلة التصغير المستخدمة في طريقة المربعات الصغرى. وفي هذا الصدد، نعيد كتابة المعادلة في شكل مصفوفة:
لذلك نحن نحلل المصفوفة إلى المصفوفات и وتنفيذ سلسلة من التحويلات (لن يتم النظر هنا في خوارزمية تحليل QR نفسها، فقط استخدامها فيما يتعلق بالمهمة المطروحة):
قالب متعامد. هذا يسمح لنا بالتخلص من العمل :
وإذا استبدلت في ، ثم سوف تنجح . معتبرا أن هي مصفوفة مثلثية عليا، تبدو كما يلي:
يمكن حل هذا باستخدام طريقة الاستبدال. عنصر يقع كما ، العنصر السابق يقع كما وهلم جرا.
ومن الجدير بالذكر هنا أن تعقيد الخوارزمية الناتجة بسبب استخدام تحليل QR يساوي . علاوة على ذلك، على الرغم من أن عملية ضرب المصفوفة متوازية بشكل جيد، فإنه ليس من الممكن كتابة نسخة موزعة فعالة من هذه الخوارزمية.
نزول متدرج
عند الحديث عن تصغير دالة، من المفيد دائمًا أن نتذكر طريقة النسب المتدرج (العشوائي). هذه طريقة تصغير بسيطة وفعالة تعتمد على الحساب التكراري لتدرج دالة عند نقطة ما ثم تحويلها في الاتجاه المعاكس للتدرج. كل خطوة من هذه الخطوات تجعل الحل أقرب إلى الحد الأدنى. لا يزال التدرج يبدو كما هو:
هذه الطريقة أيضًا متوازية وموزعة بشكل جيد نظرًا للخصائص الخطية لمشغل التدرج. لاحظ أنه في الصيغة أعلاه، تحت علامة المجموع هناك مصطلحات مستقلة. بمعنى آخر، يمكننا حساب التدرج بشكل مستقل لجميع المؤشرات من الأول إلى ، بالتوازي مع هذا، حساب التدرج للمؤشرات مع إلى . ثم أضف التدرجات الناتجة. ستكون نتيجة الإضافة هي نفسها كما لو قمنا على الفور بحساب التدرج للمؤشرات من الأول إلى . وبالتالي، إذا تم توزيع البيانات بين عدة أجزاء من البيانات، فيمكن حساب التدرج بشكل مستقل على كل قطعة، ومن ثم يمكن جمع نتائج هذه الحسابات للحصول على النتيجة النهائية:
من وجهة نظر التنفيذ، وهذا يناسب النموذج . في كل خطوة من خطوات نزول التدرج، يتم إرسال مهمة إلى كل عقدة بيانات لحساب التدرج، ثم يتم جمع التدرجات المحسوبة معًا، ويتم استخدام نتيجة مجموعها لتحسين النتيجة.
على الرغم من سهولة التنفيذ والقدرة على التنفيذ في نموذج MapReduce، فإن النسب المتدرج له أيضًا عيوبه. وعلى وجه الخصوص، فإن عدد الخطوات المطلوبة لتحقيق التقارب أعلى بكثير مقارنة بالطرق الأخرى الأكثر تخصصًا.
LSQR
هي طريقة أخرى لحل المشكلة، وهي مناسبة لاستعادة الانحدار الخطي وحل أنظمة المعادلات الخطية. وتتمثل ميزتها الرئيسية في أنها تجمع بين مزايا أساليب المصفوفة والنهج التكراري. يمكن العثور على تطبيقات هذه الطريقة في كلا المكتبات ، وفي . لن يتم تقديم وصف لهذه الطريقة هنا (يمكن العثور عليه في المقالة ). بدلاً من ذلك، سيتم عرض طريقة لتكييف LSQR مع التنفيذ في بيئة موزعة.
تعتمد طريقة LSQR على . هذا إجراء تكراري، كل تكرار يتكون من الخطوات التالية:
ولكن إذا افترضنا أن المصفوفة تم تقسيمه أفقيًا، ثم يمكن تمثيل كل تكرار كخطوتين من MapReduce. بهذه الطريقة، من الممكن تقليل عمليات نقل البيانات أثناء كل تكرار (فقط المتجهات ذات الطول يساوي عدد العناصر المجهولة):
هذا هو النهج الذي يتم استخدامه عند تنفيذ الانحدار الخطي في .
اختتام
هناك العديد من خوارزميات استرداد الانحدار الخطي، ولكن لا يمكن تطبيقها جميعًا في جميع الظروف. لذا يعد تحليل QR ممتازًا للتوصل إلى حل دقيق لمجموعات البيانات الصغيرة. يعتبر النزول المتدرج سهل التنفيذ ويسمح لك بإيجاد حل تقريبي بسرعة. ويجمع LSQR أفضل خصائص الخوارزميتين السابقتين، حيث أنه يمكن توزيعه، ويتقارب بشكل أسرع مقارنة بالنسب المتدرج، كما يسمح بالإيقاف المبكر للخوارزمية، على عكس تحليل QR، لإيجاد حل تقريبي.
المصدر: www.habr.com