Mənbə:
Xətti reqressiya verilənlərin təhlili ilə bağlı bir çox sahələr üçün əsas alqoritmlərdən biridir. Bunun səbəbi bəllidir. Bu, çox sadə və başa düşülən bir alqoritmdir ki, bu alqoritm bir çox onlarla, hətta yüzlərlə ildir ki, onun geniş yayılmasına kömək edir. İdeya ondan ibarətdir ki, biz bir dəyişənin digər dəyişənlər toplusundan xətti asılılığını qəbul edirik və sonra bu asılılığı bərpa etməyə çalışaq.
Lakin bu məqalə praktiki problemləri həll etmək üçün xətti reqressiyadan istifadə etməkdən getmir. Burada maşın öyrənmə modulu yazarkən qarşılaşdığımız onun bərpası üçün paylanmış alqoritmlərin həyata keçirilməsinin maraqlı xüsusiyyətlərini nəzərdən keçirəcəyik. . Bir az əsas riyaziyyat, maşın öyrənməsi və paylanmış hesablama məlumatlarınız minlərlə qovşaq arasında paylansa belə, xətti reqressiyanın necə həyata keçiriləcəyini anlamağa kömək edə bilər.
Nədir?
Qarşımızda xətti asılılığı bərpa etmək vəzifəsi durur. Giriş məlumatları olaraq, hər biri asılı dəyişənin müəyyən bir dəyəri ilə əlaqəli olduğu güman edilən müstəqil dəyişənlərin vektorları toplusu verilir. Bu məlumatlar iki matris şəklində təqdim edilə bilər:
İndi, asılılıq qəbul edildiyindən və üstəlik, xətti olduğundan, fərziyyəmizi matrislərin hasili şəklində yazacağıq (qeydiyyatı sadələşdirmək üçün burada və aşağıda tənliyin sərbəst müddətinin arxasında gizləndiyi güman edilir. , və matrisin son sütunu vahidləri ehtiva edir):
Xətti tənliklər sisteminə çox bənzəyir, elə deyilmi? Görünür, amma çox güman ki, belə bir tənliklər sisteminin həlli olmayacaq. Bunun səbəbi, demək olar ki, hər hansı bir real məlumatda mövcud olan səs-küydür. Başqa bir səbəb xətti asılılığın olmaması ola bilər ki, bununla da orijinallardan qeyri-xətti asılı olan əlavə dəyişənlərin tətbiqi ilə mübarizə aparmaq olar. Aşağıdakı misalı nəzərdən keçirək:
Mənbə:
Bu, bir dəyişənin (ox boyunca) əlaqəsini göstərən xətti reqressiyanın sadə nümunəsidir ) başqa dəyişəndən (ox boyunca ). Bu nümunəyə uyğun gələn xətti tənliklər sisteminin həlli üçün bütün nöqtələr tam olaraq eyni düz xətt üzərində yerləşməlidir. Amma bu doğru deyil. Lakin onlar səs-küyə görə (və ya xətti əlaqə fərziyyəsi səhv olduğuna görə) eyni düz xətt üzərində yatmırlar. Beləliklə, real məlumatlardan xətti əlaqəni bərpa etmək üçün adətən daha bir fərziyyə təqdim etmək lazımdır: giriş məlumatında səs-küy var və bu səs-küy var. . Səs-küyün paylanmasının digər növləri ilə bağlı fərziyyələr irəli sürə bilərsiniz, lakin əksər hallarda bu, daha sonra müzakirə ediləcək normal paylama hesab olunur.
Maksimum ehtimal üsulu
Beləliklə, biz təsadüfi normal paylanmış səs-küyün mövcudluğunu fərz etdik. Belə bir vəziyyətdə nə etməli? Bu hal üçün riyaziyyatda var və geniş istifadə olunur . Bir sözlə, onun mahiyyəti seçimdədir və onun sonrakı maksimallaşdırılması.
Normal səs-küylə verilənlərdən xətti əlaqəni bərpa etməyə qayıdırıq. Qeyd edək ki, ehtimal olunan xətti əlaqə riyazi gözləntidir mövcud normal paylanma. Eyni zamanda, ehtimal ki müşahidə olunanların mövcudluğundan asılı olaraq bu və ya digər qiymət alır , göstərildiyi kimi:
İndi əvəzinə əvəz edək и Bizə lazım olan dəyişənlər bunlardır:
Yalnız vektoru tapmaq qalır , bu zaman bu ehtimal maksimumdur. Belə bir funksiyanı maksimuma çatdırmaq üçün əvvəlcə onun loqarifmini götürmək rahatdır (funksiyanın loqarifmi funksiyanın özü ilə eyni nöqtədə maksimuma çatacaq):
Bu da öz növbəsində aşağıdakı funksiyanı minimuma endirmək deməkdir:
Yeri gəlmişkən, buna bir üsul deyilir . Çox vaxt yuxarıda göstərilən bütün mülahizələr buraxılır və bu üsul sadəcə istifadə olunur.
QR parçalanması
Yuxarıdakı funksiyanın minimumunu bu funksiyanın gradientinin sıfır olduğu nöqtəni tapmaqla tapmaq olar. Və gradient aşağıdakı kimi yazılacaq:
ən kiçik kvadratlar metodunda istifadə edilən minimumlaşdırma məsələsinin həlli üçün matris üsuludur. Bununla əlaqədar olaraq tənliyi matris şəklində yenidən yazırıq:
Beləliklə, matrisi parçalayırıq matrislərə и və bir sıra transformasiyaları həyata keçirin (burada QR parçalanma alqoritminin özü nəzərə alınmayacaq, yalnız onun tapşırığı ilə əlaqədar istifadəsi):
matris ortoqonaldır. Bu bizə işdən qurtulmağa imkan verir :
Və əvəz etsəniz haqqında , sonra nəticə verəcəkdir . Bunu nəzərə alaraq yuxarı üçbucaqlı matrisdir, belə görünür:
Bu, əvəzetmə metodundan istifadə etməklə həll edilə bilər. Element kimi yerləşir , əvvəlki element kimi yerləşir və s.
Burada qeyd etmək lazımdır ki, QR parçalanmasının istifadəsi nəticəsində yaranan alqoritmin mürəkkəbliyi bərabərdir. . Üstəlik, matrisin vurma əməliyyatının yaxşı paralelləşdirilməsinə baxmayaraq, bu alqoritmin effektiv paylanmış versiyasını yazmaq mümkün deyil.
gradient eniş
Funksiyanı minimuma endirmək haqqında danışarkən, həmişə (stokastik) gradient eniş metodunu xatırlamağa dəyər. Bu, bir nöqtədə funksiyanın qradientinin iterativ hesablanmasına və sonra onu qradientin əksi istiqamətində dəyişməyə əsaslanan sadə və effektiv minimuma endirmə üsuludur. Hər bir belə addım həlli minimuma yaxınlaşdırır. Qradiyent hələ də eyni görünür:
Bu üsul həm də qradiyent operatorunun xətti xassələrinə görə yaxşı paralelləşdirilmiş və paylanmışdır. Qeyd edək ki, yuxarıdakı düsturda cəmi işarəsinin altında müstəqil terminlər var. Başqa sözlə desək, bütün indekslər üçün qradiyenti müstəqil hesablaya bilərik birincidən , bununla paralel olaraq indekslər üçün qradiyenti hesablayın üzrə . Sonra ortaya çıxan gradientləri əlavə edin. Əlavənin nəticəsi indekslər üçün gradienti birincidən dərhal hesabladığımız kimi olacaq . Beləliklə, əgər məlumatlar bir neçə məlumat parçası arasında bölüşdürülürsə, hər bir parça üzrə gradient müstəqil hesablana bilər və sonra yekun nəticəni əldə etmək üçün bu hesablamaların nəticələri cəmlənə bilər:
İcra baxımından bu, paradiqmaya uyğun gəlir . Qradiyentin enməsinin hər bir addımında qradiyentin hesablanması üçün hər bir məlumat qovşağına tapşırıq göndərilir, sonra hesablanmış qradiyentlər birlikdə toplanır və nəticənin yaxşılaşdırılması üçün onların cəminin nəticəsi istifadə olunur.
İcra asanlığına və MapReduce paradiqmasında icra etmək qabiliyyətinə baxmayaraq, gradient enişinin də çatışmazlıqları var. Xüsusilə, konvergensiyaya nail olmaq üçün tələb olunan addımların sayı digər daha ixtisaslaşmış üsullarla müqayisədə xeyli yüksəkdir.
LSQR
problemin həlli üçün həm xətti reqressiyanın bərpası, həm də xətti tənliklər sistemlərinin həlli üçün uyğun olan başqa bir üsuldur. Onun əsas xüsusiyyəti odur ki, o, matris metodlarının üstünlüklərini və iterativ yanaşmanı özündə birləşdirir. Bu metodun tətbiqinə hər iki kitabxanada rast gəlmək olar , və . Bu metodun təsviri burada verilməyəcək (məqalədə tapa bilərsiniz ). Bunun əvəzinə LSQR-ni paylanmış mühitdə icraya uyğunlaşdırmaq üçün yanaşma nümayiş etdiriləcək.
LSQR metodu əsaslanır . Bu iterativ prosedurdur, hər iterasiya aşağıdakı addımlardan ibarətdir:
Amma matris olduğunu fərz etsək üfüqi olaraq bölünür, onda hər iterasiya iki MapReduce addımı kimi təqdim edilə bilər. Bu yolla, hər bir iterasiya zamanı məlumat ötürülməsini minimuma endirmək mümkündür (yalnız uzunluğu bilinməyənlərin sayına bərabər olan vektorlar):
Məhz bu yanaşma xətti reqressiya tətbiq edərkən istifadə olunur .
Nəticə
Çoxlu xətti reqressiyanın bərpası alqoritmləri var, lakin onların hamısını bütün şəraitdə tətbiq etmək mümkün deyil. Beləliklə, QR parçalanması kiçik məlumat dəstlərində dəqiq həll üçün əladır. Gradient enişinin həyata keçirilməsi sadədir və tez bir zamanda təxmini həlli tapmağa imkan verir. Və LSQR əvvəlki iki alqoritmin ən yaxşı xassələrini birləşdirir, çünki o, paylana bilir, gradient enişlə müqayisədə daha sürətli birləşir və həmçinin təxmini həll tapmaq üçün QR parçalanmasından fərqli olaraq alqoritmin erkən dayandırılmasına imkan verir.
Mənbə: www.habr.com