ხაზოვანი რეგრესია და მისი აღდგენის მეთოდები

წყარო: xkcd

ხაზოვანი რეგრესია არის ერთ-ერთი ძირითადი ალგორითმი მონაცემთა ანალიზთან დაკავშირებული მრავალი სფეროსთვის. ამის მიზეზი აშკარაა. ეს არის ძალიან მარტივი და გასაგები ალგორითმი, რომელმაც ხელი შეუწყო მის ფართო გამოყენებას მრავალი ათეული, თუ არა ასობით წლის განმავლობაში. იდეა არის ის, რომ ჩვენ ვივარაუდოთ ერთი ცვლადის წრფივი დამოკიდებულება სხვა ცვლადების სიმრავლეზე და შემდეგ ვცდილობთ ამ დამოკიდებულების აღდგენას.

მაგრამ ეს სტატია არ ეხება ხაზოვანი რეგრესიის გამოყენებას პრაქტიკული პრობლემების გადასაჭრელად. აქ განვიხილავთ მისი აღდგენისთვის განაწილებული ალგორითმების განხორციელების საინტერესო მახასიათებლებს, რომლებიც შეგვხვდა მანქანაში სწავლის მოდულის დაწერისას. Apache Ignite. ცოტა საბაზისო მათემატიკა, მანქანათმცოდნეობა და განაწილებული გამოთვლები დაგეხმარებათ გაიგოთ, როგორ შეასრულოთ წრფივი რეგრესია მაშინაც კი, როცა თქვენი მონაცემები ნაწილდება ათასობით კვანძში.

რაზე ვსაუბრობთ?

ჩვენ წინაშე დგას ხაზოვანი დამოკიდებულების აღდგენის ამოცანა. როგორც შეყვანის მონაცემი, მოცემულია სავარაუდო დამოუკიდებელი ცვლადების ვექტორების ნაკრები, რომელთაგან თითოეული ასოცირდება დამოკიდებული ცვლადის გარკვეულ მნიშვნელობასთან. ეს მონაცემები შეიძლება წარმოდგენილი იყოს ორი მატრიცის სახით:

ახლა, რადგან დამოკიდებულება არის ვარაუდი და, უფრო მეტიც, წრფივი, ჩვენ დავწერთ ჩვენს ვარაუდს მატრიცების ნამრავლის სახით (ჩაწერის გასამარტივებლად, აქ და ქვემოთ ვარაუდობენ, რომ განტოლების თავისუფალი წევრი იმალება უკან და მატრიცის ბოლო სვეტი შეიცავს ერთეულებს):

ძალიან ჰგავს წრფივი განტოლებების სისტემას, არა? როგორც ჩანს, მაგრამ, სავარაუდოდ, განტოლებების ასეთი სისტემის ამონახსნები არ იქნება. ამის მიზეზი ხმაურია, რომელიც თითქმის ნებისმიერ რეალურ მონაცემშია. კიდევ ერთი მიზეზი შეიძლება იყოს ხაზოვანი დამოკიდებულების არარსებობა, როგორც ასეთი, რომლის წინააღმდეგ ბრძოლა შესაძლებელია დამატებითი ცვლადების შემოღებით, რომლებიც არაწრფივად არის დამოკიდებული ორიგინალზე. განვიხილოთ შემდეგი მაგალითი:

წყარო: Wikipedia

ეს არის წრფივი რეგრესიის მარტივი მაგალითი, რომელიც აჩვენებს ერთი ცვლადის ურთიერთობას (ღერძის გასწვრივ ) სხვა ცვლადიდან (ღერძის გასწვრივ ). იმისთვის, რომ ამ მაგალითის შესაბამის წრფივ განტოლებათა სისტემას ჰქონდეს ამონახსნი, ყველა წერტილი ზუსტად უნდა იყოს ერთსა და იმავე სწორ ხაზზე. მაგრამ ეს ასე არ არის. მაგრამ ისინი არ წევენ ერთსა და იმავე სწორ ხაზზე ზუსტად ხმაურის გამო (ან იმიტომ, რომ წრფივი ურთიერთობის ვარაუდი მცდარი იყო). ამრიგად, რეალური მონაცემებიდან წრფივი ურთიერთობის აღსადგენად, ჩვეულებრივ, საჭიროა კიდევ ერთი დაშვების დანერგვა: შეყვანის მონაცემები შეიცავს ხმაურს და ეს ხმაური აქვს ნორმალური დისტრიბუცია. თქვენ შეგიძლიათ გამოთქვათ ვარაუდები სხვა ტიპის ხმაურის განაწილების შესახებ, მაგრამ უმეტეს შემთხვევაში ეს არის ნორმალური განაწილება, რომელიც განიხილება შემდგომში.

მაქსიმალური ალბათობის მეთოდი

ასე რომ, ჩვენ ვივარაუდეთ შემთხვევითი ნორმალურად განაწილებული ხმაურის არსებობა. რა უნდა გააკეთოს ასეთ სიტუაციაში? ამ შემთხვევისთვის მათემატიკაში არის და ფართოდ გამოიყენება მაქსიმალური ალბათობის მეთოდი. მოკლედ, მისი არსი არჩევანშია ალბათობის ფუნქციები და მისი შემდგომი მაქსიმიზაცია.

ჩვენ ვუბრუნდებით ხაზოვანი ურთიერთობის აღდგენას მონაცემებიდან ნორმალური ხმაურით. გაითვალისწინეთ, რომ სავარაუდო წრფივი ურთიერთობა არის მათემატიკური მოლოდინი არსებული ნორმალური განაწილება. ამავე დროს, იმის ალბათობაც იღებს ამა თუ იმ მნიშვნელობას, დაკვირვებადობის არსებობის გათვალისწინებით , შემდეგნაირად:

მოდით ახლა შევცვალოთ ამის ნაცვლად и ჩვენ გვჭირდება ცვლადები:

რჩება მხოლოდ ვექტორის პოვნა , სადაც ეს ალბათობა მაქსიმალურია. ასეთი ფუნქციის მაქსიმიზაციისთვის, მოსახერხებელია ჯერ მისი ლოგარითმის აღება (ფუნქციის ლოგარითმი მაქსიმუმს მიაღწევს იმავე წერტილში, როგორც თავად ფუნქცია):

რაც, თავის მხრივ, მცირდება შემდეგი ფუნქციის მინიმუმამდე:

სხვათა შორის, ამას მეთოდს უწოდებენ უმცირესი კვადრატები. ხშირად ყველა ზემოთ ჩამოთვლილი მოსაზრება გამოტოვებულია და ეს მეთოდი უბრალოდ გამოიყენება.

QR დაშლა

ზემოაღნიშნული ფუნქციის მინიმუმის პოვნა შესაძლებელია იმ წერტილის იპოვით, სადაც ამ ფუნქციის გრადიენტი ნულის ტოლია. და გრადიენტი დაიწერება შემდეგნაირად:

QR დაშლა არის მატრიცული მეთოდი მინიმიზაციის პრობლემის გადასაჭრელად, რომელიც გამოიყენება უმცირესი კვადრატების მეთოდში. ამასთან დაკავშირებით, ჩვენ ხელახლა ვწერთ განტოლებას მატრიცის სახით:

ასე რომ, ჩვენ ვანადგურებთ მატრიცას მატრიცებამდე и და შეასრულეთ ტრანსფორმაციების სერია (თავად QR დაშლის ალგორითმი აქ არ განიხილება, მხოლოდ მისი გამოყენება სამუშაოსთან მიმართებაში):

matrix არის ორთოგონალური. ეს საშუალებას გვაძლევს თავი დავაღწიოთ სამუშაოს :

და თუ შეცვლით on , მაშინ გამოვა . Იმის გათვალისწინებით არის ზედა სამკუთხა მატრიცა, ის ასე გამოიყურება:

ეს შეიძლება მოგვარდეს ჩანაცვლების მეთოდით. ელემენტი მდებარეობს როგორც , წინა ელემენტი მდებარეობს როგორც და ასე შემდეგ.

აქვე უნდა აღინიშნოს, რომ QR დაშლის გამოყენების გამო მიღებული ალგორითმის სირთულე უდრის . უფრო მეტიც, მიუხედავად იმისა, რომ მატრიცის გამრავლების ოპერაცია კარგად არის პარალელიზებული, ამ ალგორითმის ეფექტური განაწილებული ვერსიის დაწერა შეუძლებელია.

გრადიენტული დაღმართი

ფუნქციის მინიმიზაციაზე საუბრისას ყოველთვის ღირს (სტოქასტური) გრადიენტული დაღმართის მეთოდის გახსენება. ეს არის მარტივი და ეფექტური მინიმიზაციის მეთოდი, რომელიც ეფუძნება ფუნქციის გრადიენტის განმეორებით გამოთვლას წერტილში და შემდეგ გადაადგილებას გრადიენტის საწინააღმდეგო მიმართულებით. ყოველი ასეთი ნაბიჯი აახლოებს გამოსავალს მინიმუმამდე. გრადიენტი ისევ იგივე გამოიყურება:

ეს მეთოდი ასევე კარგად არის პარალელიზებული და განაწილებული გრადიენტური ოპერატორის ხაზოვანი თვისებების გამო. გაითვალისწინეთ, რომ ზემოთ მოცემულ ფორმულაში ჯამის ნიშნის ქვეშ არის დამოუკიდებელი ტერმინები. სხვა სიტყვებით რომ ვთქვათ, ჩვენ შეგვიძლია გამოვთვალოთ გრადიენტი დამოუკიდებლად ყველა ინდექსისთვის პირველიდან , ამის პარალელურად, გამოთვალეთ გრადიენტი ინდექსებისთვის დან . შემდეგ დაამატეთ მიღებული გრადიენტები. მიმატების შედეგი იგივე იქნება, თითქოს მაშინვე გამოვთვალოთ გრადიენტი ინდექსებისთვის პირველიდან . ამრიგად, თუ მონაცემები განაწილებულია რამდენიმე მონაცემზე, გრადიენტი შეიძლება გამოითვალოს დამოუკიდებლად თითოეულ ნაწილზე და შემდეგ ამ გამოთვლების შედეგები შეიძლება შეჯამდეს საბოლოო შედეგის მისაღებად:

განხორციელების თვალსაზრისით, ეს შეესაბამება პარადიგმას MapReduce. გრადიენტური წარმოშობის ყოველ საფეხურზე, თითოეულ მონაცემთა კვანძს ეგზავნება დავალება გრადიენტის გამოსათვლელად, შემდეგ გამოთვლილი გრადიენტები გროვდება ერთად და მათი ჯამის შედეგი გამოიყენება შედეგის გასაუმჯობესებლად.

მიუხედავად განხორციელების სიმარტივისა და MapReduce პარადიგმაში შესრულების შესაძლებლობისა, გრადიენტულ დაცემას ასევე აქვს თავისი ნაკლი. კერძოდ, კონვერგენციის მისაღწევად საჭირო საფეხურების რაოდენობა მნიშვნელოვნად მაღალია სხვა უფრო სპეციალიზებულ მეთოდებთან შედარებით.

LSQR

LSQR პრობლემის გადაჭრის კიდევ ერთი მეთოდია, რომელიც შესაფერისია როგორც წრფივი რეგრესიის აღდგენისთვის, ასევე წრფივი განტოლებების სისტემების ამოსახსნელად. მისი მთავარი მახასიათებელია ის, რომ აერთიანებს მატრიცული მეთოდების უპირატესობებს და განმეორებით მიდგომას. ამ მეთოდის დანერგვა შესაძლებელია ორივე ბიბლიოთეკაში მეცნიერი, და MATLAB. ამ მეთოდის აღწერა აქ არ იქნება მოცემული (ის შეგიძლიათ იხილოთ სტატიაში LSQR: ალგორითმი მწირი წრფივი განტოლებისთვის და იშვიათი უმცირესი კვადრატებისთვის). ამის ნაცვლად, ნაჩვენები იქნება მიდგომა LSQR-ის ადაპტაციისთვის განაწილებულ გარემოში შესრულებაზე.

LSQR მეთოდი ეფუძნება ბიდიაგონალიზაციის პროცედურა. ეს არის განმეორებითი პროცედურა, თითოეული გამეორება შედგება შემდეგი ნაბიჯებისგან:


მაგრამ თუ დავუშვებთ, რომ მატრიცა არის ჰორიზონტალურად დაყოფილი, შემდეგ ყოველი გამეორება შეიძლება წარმოდგენილი იყოს MapReduce-ის ორი საფეხურად. ამ გზით, შესაძლებელია მონაცემთა გადაცემის მინიმუმამდე შემცირება ყოველი გამეორების დროს (მხოლოდ ვექტორები, რომელთა სიგრძე უდრის უცნობის რაოდენობას):

სწორედ ეს მიდგომა გამოიყენება ხაზოვანი რეგრესიის განხორციელებისას Apache Ignite ML.

დასკვნა

არსებობს მრავალი წრფივი რეგრესიის აღდგენის ალგორითმი, მაგრამ ყველა მათგანის გამოყენება არ შეიძლება ყველა პირობებში. ასე რომ, QR დაშლა შესანიშნავია მცირე მონაცემთა ნაკრების ზუსტი გადაწყვეტისთვის. გრადიენტური წარმოშობა მარტივია განსახორციელებლად და საშუალებას გაძლევთ სწრაფად იპოვოთ სავარაუდო გამოსავალი. და LSQR აერთიანებს წინა ორი ალგორითმის საუკეთესო თვისებებს, რადგან ის შეიძლება განაწილდეს, უფრო სწრაფად იყრის თავს გრადიენტულ დაღმართთან შედარებით და ასევე საშუალებას აძლევს ალგორითმის ადრეულ შეჩერებას, QR დაშლისგან განსხვავებით, სავარაუდო გადაწყვეტის პოვნა.

წყარო: www.habr.com