منبع:
رگرسیون خطی یکی از الگوریتم های اساسی برای بسیاری از حوزه های مرتبط با تجزیه و تحلیل داده ها است. دلیل این امر واضح است. این یک الگوریتم بسیار ساده و قابل درک است که به استفاده گسترده از آن برای ده ها، اگر نه صدها سال کمک کرده است. ایده این است که ما وابستگی خطی یک متغیر را به مجموعه‌ای از متغیرهای دیگر فرض می‌کنیم و سپس سعی می‌کنیم این وابستگی را بازیابی کنیم.
اما این مقاله در مورد استفاده از رگرسیون خطی برای حل مسائل عملی نیست. در اینجا ما ویژگی های جالب اجرای الگوریتم های توزیع شده را برای بازیابی آن در نظر خواهیم گرفت، که در هنگام نوشتن یک ماژول یادگیری ماشینی با آن مواجه شدیم. . کمی ریاضی ابتدایی، یادگیری ماشین و محاسبات توزیع شده می تواند به شما کمک کند تا دریابید که چگونه رگرسیون خطی انجام دهید، حتی زمانی که داده های شما در هزاران گره توزیع شده است.
ما در مورد چه چیزی صحبت می کنیم؟
ما با وظیفه بازگرداندن وابستگی خطی روبرو هستیم. به عنوان داده ورودی، مجموعه ای از بردارها از متغیرهای فرضی مستقل ارائه می شود که هر کدام با مقدار مشخصی از متغیر وابسته مرتبط هستند. این داده ها را می توان در قالب دو ماتریس نشان داد:
حال، از آنجایی که وابستگی فرض می شود، و علاوه بر این، خطی است، فرض خود را به صورت حاصل ضرب ماتریس ها می نویسیم (برای ساده سازی ضبط، در اینجا و در زیر فرض می شود که عبارت آزاد معادله پنهان شده است. و آخرین ستون ماتریس شامل واحدها):
به نظر بسیار شبیه یک سیستم معادلات خطی است، اینطور نیست؟ به نظر می رسد، اما به احتمال زیاد هیچ راه حلی برای چنین سیستم معادلاتی وجود نخواهد داشت. دلیل این امر نویز است که تقریباً در هر داده واقعی وجود دارد. دلیل دیگر ممکن است فقدان وابستگی خطی باشد، که می توان با معرفی متغیرهای اضافی که به طور غیرخطی به متغیرهای اصلی بستگی دارند، با آن مبارزه کرد. به مثال زیر توجه کنید:
منبع:
این یک مثال ساده از رگرسیون خطی است که رابطه یک متغیر (در امتداد محور) را نشان می دهد ) از متغیر دیگری (در امتداد محور ). برای اینکه سیستم معادلات خطی متناظر با این مثال راه حلی داشته باشد، همه نقاط باید دقیقاً روی یک خط مستقیم قرار گیرند. اما این درست نیست. اما آنها دقیقاً به دلیل نویز (یا به این دلیل که فرض یک رابطه خطی اشتباه بود) روی یک خط مستقیم قرار نمی گیرند. بنابراین، برای بازیابی یک رابطه خطی از داده‌های واقعی، معمولاً لازم است یک فرض دیگر ارائه شود: داده‌های ورودی حاوی نویز هستند و این نویز دارای نویز است. . شما می توانید در مورد انواع دیگر توزیع نویز فرضیاتی داشته باشید، اما در اکثریت قریب به اتفاق موارد این توزیع نرمال است که در نظر گرفته می شود که بیشتر مورد بحث قرار خواهد گرفت.
روش حداکثر احتمال
بنابراین، ما وجود نویز معمولی تصادفی را فرض کردیم. در چنین شرایطی چه باید کرد؟ برای این مورد در ریاضیات وجود دارد و به طور گسترده استفاده می شود . به طور خلاصه، جوهر آن در انتخاب نهفته است و حداکثر سازی بعدی آن
ما به بازیابی یک رابطه خطی از داده ها با نویز معمولی باز می گردیم. توجه داشته باشید که رابطه خطی فرض شده انتظار ریاضی است توزیع نرمال موجود در عین حال، این احتمال وجود دارد که با توجه به حضور قابل مشاهده‌ها، ارزشی به خود می‌گیرد ، به شرح زیر است:
اجازه دهید اکنون به جای آن جایگزین کنیم и متغیرهایی که نیاز داریم عبارتند از:
تنها چیزی که باقی می ماند یافتن بردار است ، که در آن این احتمال حداکثر است. برای به حداکثر رساندن چنین تابعی، راحت است ابتدا یک لگاریتم از آن بگیرید (لگاریتم تابع در همان نقطه خود تابع به حداکثر می رسد):
که به نوبه خود منجر به کمینه سازی عملکرد زیر می شود:
اتفاقاً به این روش می گویند . اغلب تمام ملاحظات فوق حذف می شوند و این روش به سادگی مورد استفاده قرار می گیرد.
تجزیه QR
حداقل تابع فوق را می توان با یافتن نقطه ای که گرادیان این تابع در آن صفر است، پیدا کرد. و گرادیان به صورت زیر نوشته می شود:
یک روش ماتریسی برای حل مسئله کمینه سازی است که در روش حداقل مربعات استفاده می شود. در این رابطه معادله را به صورت ماتریسی بازنویسی می کنیم:
بنابراین ماتریس را تجزیه می کنیم به ماتریس ها и و یک سری تبدیل انجام دهید (الگوریتم تجزیه QR خود در اینجا در نظر گرفته نخواهد شد، فقط استفاده از آن در رابطه با کار در دست انجام است):
ماتریس متعامد است. این به ما امکان می دهد از کار خلاص شویم :
و اگر جایگزین کنید بر ، پس از آن به نتیجه خواهد رسید . با توجه به اینکه یک ماتریس مثلثی بالایی است، به شکل زیر است:
این را می توان با استفاده از روش جایگزینی حل کرد. عنصر به عنوان واقع شده است ، عنصر قبلی به عنوان واقع شده است و به همین ترتیب.
در اینجا شایان ذکر است که پیچیدگی الگوریتم حاصل به دلیل استفاده از تجزیه QR برابر است با . علاوه بر این، با وجود این واقعیت که عملیات ضرب ماتریس به خوبی موازی شده است، نمی توان نسخه توزیع شده موثری از این الگوریتم نوشت.
گرادیان نزول
هنگام صحبت از کمینه کردن یک تابع، همیشه ارزش دارد که روش نزول گرادیان (تصادفی) را به خاطر بسپارید. این یک روش کمینه‌سازی ساده و مؤثر است که مبتنی بر محاسبه تکراری گرادیان یک تابع در یک نقطه و سپس تغییر آن در جهت مخالف گرادیان است. هر مرحله از این قبیل راه حل را به حداقل می رساند. گرادیان همچنان یکسان به نظر می رسد:
این روش همچنین به دلیل خصوصیات خطی عملگر گرادیان به خوبی موازی و توزیع شده است. توجه داشته باشید که در فرمول فوق، در زیر علامت جمع، عبارت های مستقلی وجود دارد. به عبارت دیگر، ما می توانیم گرادیان را به طور مستقل برای همه شاخص ها محاسبه کنیم از اول تا ، به موازات این، گرادیان را برای شاخص های با محاسبه کنید به . سپس گرادیان های به دست آمده را اضافه کنید. نتیجه جمع همان خواهد بود که اگر بلافاصله گرادیان شاخص ها را از اول به محاسبه کنیم . بنابراین، اگر داده ها بین چندین قطعه داده توزیع شود، می توان گرادیان را به طور مستقل بر روی هر قطعه محاسبه کرد و سپس نتایج این محاسبات را برای به دست آوردن نتیجه نهایی جمع کرد:
از نقطه نظر اجرا، این با پارادایم مطابقت دارد . در هر مرحله از نزول گرادیان، یک وظیفه برای محاسبه گرادیان به هر گره داده ارسال می‌شود، سپس گرادیان‌های محاسبه‌شده با هم جمع‌آوری می‌شوند و از نتیجه حاصل جمع آنها برای بهبود نتیجه استفاده می‌شود.
علیرغم سهولت اجرا و قابلیت اجرا در پارادایم MapReduce، نزول گرادیان نیز دارای اشکالاتی است. به طور خاص، تعداد مراحل مورد نیاز برای دستیابی به همگرایی در مقایسه با سایر روش های تخصصی تر به طور قابل توجهی بیشتر است.
LSQR
روش دیگری برای حل مسئله است که هم برای بازیابی رگرسیون خطی و هم برای حل سیستم های معادلات خطی مناسب است. ویژگی اصلی آن ترکیبی از مزایای روشهای ماتریسی و رویکرد تکراری است. پیاده سازی های این روش را می توان در هر دو کتابخانه یافت ، و در . شرحی از این روش در اینجا داده نخواهد شد (آن را می توان در مقاله یافت ). در عوض، رویکردی برای تطبیق LSQR برای اجرا در یک محیط توزیع شده نشان داده خواهد شد.
روش LSQR بر اساس . این یک روش تکراری است که هر تکرار شامل مراحل زیر است:
اما اگر فرض کنیم که ماتریس به صورت افقی پارتیشن بندی می شود، سپس هر تکرار را می توان به عنوان دو مرحله MapReduce نشان داد. به این ترتیب، می توان انتقال داده ها را در طول هر تکرار به حداقل رساند (فقط بردارهایی با طول برابر با تعداد مجهولات):
این رویکرد است که هنگام اجرای رگرسیون خطی در استفاده می شود .
نتیجه
الگوریتم های بازیابی رگرسیون خطی زیادی وجود دارد، اما همه آنها را نمی توان در همه شرایط اعمال کرد. بنابراین تجزیه QR برای حل دقیق در مجموعه داده های کوچک بسیار عالی است. پیاده سازی گرادیان نزول ساده است و به شما امکان می دهد به سرعت یک راه حل تقریبی پیدا کنید. و LSQR بهترین ویژگی‌های دو الگوریتم قبلی را ترکیب می‌کند، زیرا می‌تواند توزیع شود، در مقایسه با گرادیان نزول سریع‌تر همگرا می‌شود، و همچنین اجازه می‌دهد تا الگوریتم را بر خلاف تجزیه QR، برای یافتن یک راه‌حل تقریبی متوقف کنیم.
منبع: www.habr.com