Source:
Գծային ռեգրեսիան տվյալների վերլուծության հետ կապված բազմաթիվ ոլորտների հիմնական ալգորիթմներից մեկն է: Սրա պատճառն ակնհայտ է. Սա շատ պարզ և հասկանալի ալգորիթմ է, որը նպաստել է դրա լայն տարածմանը տասնյակ, եթե ոչ հարյուրավոր տարիներ։ Գաղափարն այն է, որ մենք ենթադրում ենք մեկ փոփոխականի գծային կախվածություն այլ փոփոխականների մի շարքից, այնուհետև փորձում ենք վերականգնել այդ կախվածությունը:
Բայց այս հոդվածը գործնական խնդիրների լուծման համար գծային ռեգրեսիա օգտագործելու մասին չէ: Այստեղ մենք կդիտարկենք դրա վերականգնման համար բաշխված ալգորիթմների ներդրման հետաքրքիր առանձնահատկությունները, որոնք մենք հանդիպեցինք մեքենայական ուսուցման մոդուլ գրելիս. . Մի փոքր հիմնական մաթեմատիկան, մեքենայական ուսուցումը և բաշխված հաշվարկը կարող են օգնել ձեզ պարզել, թե ինչպես կատարել գծային ռեգրեսիա, նույնիսկ երբ ձեր տվյալները բաշխված են հազարավոր հանգույցների վրա:
Ինչի՞ մասին ենք խոսում։
Մեր առջեւ խնդիր է դրված վերականգնել գծային կախվածությունը։ Որպես մուտքային տվյալ՝ տրվում է ենթադրաբար անկախ փոփոխականների վեկտորների մի շարք, որոնցից յուրաքանչյուրը կապված է կախված փոփոխականի որոշակի արժեքի հետ։ Այս տվյալները կարող են ներկայացվել երկու մատրիցայի տեսքով.
Այժմ, քանի որ կախվածությունը ենթադրվում է, և, առավել ևս, գծային, մենք մեր ենթադրությունը կգրենք մատրիցների արտադրյալի տեսքով (ձայնագրությունը պարզեցնելու համար այստեղ և ներքևում ենթադրվում է, որ հավասարման ազատ անդամը թաքնված է հետևում. , և մատրիցայի վերջին սյունակը պարունակում է միավորներ):
Շատ նման է գծային հավասարումների համակարգի, այնպես չէ՞: Թվում է, բայց, ամենայն հավանականությամբ, նման հավասարումների համակարգի լուծումներ չեն լինի։ Դրա պատճառը աղմուկն է, որն առկա է գրեթե ցանկացած իրական տվյալների մեջ։ Մեկ այլ պատճառ կարող է լինել գծային կախվածության բացակայությունը որպես այդպիսին, որի դեմ կարելի է պայքարել՝ ներմուծելով լրացուցիչ փոփոխականներ, որոնք ոչ գծային կախված են սկզբնականներից: Դիտարկենք հետևյալ օրինակը.
Source:
Սա գծային ռեգրեսիայի պարզ օրինակ է, որը ցույց է տալիս մեկ փոփոխականի կապը (առանցքի երկայնքով ) մեկ այլ փոփոխականից (առանցքի երկայնքով ) Որպեսզի այս օրինակին համապատասխան գծային հավասարումների համակարգը լուծում ունենա, բոլոր կետերը պետք է գտնվեն ճիշտ նույն ուղիղ գծի վրա: Բայց դա ճիշտ չէ: Բայց նրանք նույն ուղիղ գծի վրա չեն պառկում հենց աղմուկի պատճառով (կամ այն պատճառով, որ գծային հարաբերությունների ենթադրությունը սխալ էր): Այսպիսով, իրական տվյալներից գծային կապը վերականգնելու համար սովորաբար անհրաժեշտ է ներկայացնել ևս մեկ ենթադրություն. մուտքային տվյալները պարունակում են աղմուկ, և այդ աղմուկն ունի. . Դուք կարող եք ենթադրություններ անել աղմուկի բաշխման այլ տեսակների վերաբերյալ, սակայն դեպքերի ճնշող մեծամասնության մեջ դիտարկվում է նորմալ բաշխումը, որը կքննարկվի հետագա:
Առավելագույն հավանականության մեթոդ
Այսպիսով, մենք ենթադրեցինք պատահական նորմալ բաշխված աղմուկի առկայությունը: Ի՞նչ անել նման իրավիճակում: Այս դեպքի համար մաթեմատիկայի մեջ կա և լայնորեն կիրառվում է . Մի խոսքով, դրա էությունը ընտրության մեջ է և դրա հետագա մաքսիմալացումը:
Մենք վերադառնում ենք նորմալ աղմուկով տվյալներից գծային հարաբերությունների վերականգնմանը: Նշենք, որ ենթադրյալ գծային հարաբերությունը մաթեմատիկական ակնկալիքն է գոյություն ունեցող նորմալ բաշխում: Միաժամանակ, հավանականությունը, որ ընդունում է այս կամ այն արժեքները, որոնք ենթակա են դիտելիության առկայությանը , Ինչպես նշված է հետեւյալում:
Եկեք հիմա փոխարինենք դրա փոխարեն и Մեզ անհրաժեշտ փոփոխականներն են.
Մնում է միայն գտնել վեկտորը , որի դեպքում այս հավանականությունը առավելագույնն է: Նման ֆունկցիան առավելագույնի հասցնելու համար հարմար է նախ վերցնել դրա լոգարիթմը (ֆունկցիայի լոգարիթմը առավելագույնի կհասնի նույն կետում, ինչ ֆունկցիան ինքնին).
Ինչն իր հերթին հանգում է հետևյալ գործառույթի նվազագույնի.
Ի դեպ, սա կոչվում է մեթոդ . Հաճախ վերը նշված բոլոր նկատառումները բաց են թողնվում, և այս մեթոդը պարզապես օգտագործվում է:
QR տարրալուծում
Վերոնշյալ ֆունկցիայի նվազագույնը կարելի է գտնել՝ գտնելով այն կետը, որտեղ այս ֆունկցիայի գրադիենտը զրո է։ Իսկ գրադիենտը կգրվի հետևյալ կերպ.
նվազագույն քառակուսիների մեթոդով կիրառվող մինիմիզացման խնդրի լուծման մատրիցային մեթոդ է: Այս առումով, մենք վերագրում ենք հավասարումը մատրիցային ձևով.
Այսպիսով, մենք քայքայում ենք մատրիցը դեպի մատրիցներ и և կատարել մի շարք փոխակերպումներ (QR տարրալուծման ալգորիթմն ինքնին այստեղ չի դիտարկվի, միայն դրա օգտագործումը առաջադրանքի հետ կապված).
մատրիցա ուղղանկյուն է. Սա մեզ թույլ է տալիս ազատվել աշխատանքից :
Իսկ եթե փոխարինես մասին , ապա այն կաշխատի . Հաշվի առնելով դա վերին եռանկյունաձև մատրիցա է, այն ունի հետևյալ տեսքը.
Սա կարող է լուծվել փոխարինման մեթոդով: Տարր գտնվում է որպես , նախորդ տարր գտնվում է որպես եւ այլն:
Այստեղ հարկ է նշել, որ QR տարրալուծման կիրառման արդյունքում ստացված ալգորիթմի բարդությունը հավասար է. . Ավելին, չնայած այն հանգամանքին, որ մատրիցային բազմապատկման գործողությունը լավ զուգահեռականացված է, հնարավոր չէ գրել այս ալգորիթմի արդյունավետ բաշխված տարբերակը։
Գրադիենտ ծագում
Երբ խոսում ենք ֆունկցիան նվազագույնի հասցնելու մասին, միշտ արժե հիշել (ստոխաստիկ) գրադիենտ ծագման մեթոդը։ Սա մինիմալացման պարզ և արդյունավետ մեթոդ է, որը հիմնված է մի կետում ֆունկցիայի գրադիենտի կրկնվող հաշվարկի վրա և այնուհետև այն գրադիենտին հակառակ ուղղությամբ տեղափոխելու վրա: Յուրաքանչյուր նման քայլ լուծումը մոտենում է նվազագույնին։ Գրադիենտը դեռ նույնն է թվում.
Այս մեթոդը նույնպես լավ զուգահեռացված և բաշխված է գրադիենտ օպերատորի գծային հատկությունների շնորհիվ: Նկատի ունեցեք, որ վերը նշված բանաձևում գումարի նշանի տակ կան անկախ տերմիններ: Այլ կերպ ասած, մենք կարող ենք ինքնուրույն հաշվարկել գրադիենտը բոլոր ինդեքսների համար առաջինից մինչև , սրան զուգահեռ հաշվարկեք ինդեքսների գրադիենտը դեպի . Այնուհետև ավելացրեք ստացված գրադիենտները: Հավելման արդյունքը կլինի նույնը, ինչ եթե մենք անմիջապես հաշվարկենք ինդեքսների գրադիենտը առաջինից մինչև . Այսպիսով, եթե տվյալները բաշխված են մի քանի տվյալների միջև, գրադիենտը կարող է ինքնուրույն հաշվարկվել յուրաքանչյուր մասի վրա, այնուհետև այս հաշվարկների արդյունքները կարող են ամփոփվել՝ վերջնական արդյունք ստանալու համար.
Իրականացման տեսանկյունից սա համապատասխանում է պարադիգմին . Գրադիենտ անկման յուրաքանչյուր քայլում յուրաքանչյուր տվյալների հանգույց ուղարկվում է գրադիենտը հաշվարկելու առաջադրանք, այնուհետև հաշվարկված գրադիենտները հավաքվում են միասին, և դրանց գումարի արդյունքն օգտագործվում է արդյունքը բարելավելու համար:
Չնայած իրականացման հեշտությանը և MapReduce պարադիգմում գործարկելու հնարավորությանը, գրադիենտ ծագումն ունի նաև իր թերությունները: Մասնավորապես, կոնվերգենցիայի հասնելու համար անհրաժեշտ քայլերի թիվը զգալիորեն ավելի մեծ է այլ ավելի մասնագիտացված մեթոդների համեմատ:
LSQR
Խնդիրը լուծելու ևս մեկ մեթոդ է, որը հարմար է ինչպես գծային ռեգրեսիան վերականգնելու, այնպես էլ գծային հավասարումների համակարգերի լուծման համար։ Դրա հիմնական առանձնահատկությունն այն է, որ այն համատեղում է մատրիցային մեթոդների առավելությունները և կրկնվող մոտեցումը: Այս մեթոդի իրականացումը կարելի է գտնել երկու գրադարաններում եւ ներս . Այս մեթոդի նկարագրությունը այստեղ չի տրվի (այն կարելի է գտնել հոդվածում ) Փոխարենը կցուցադրվի մոտեցում՝ LSQR-ը բաշխված միջավայրում կատարմանը հարմարեցնելու համար:
LSQR մեթոդը հիմնված է . Սա կրկնվող ընթացակարգ է, յուրաքանչյուր կրկնություն բաղկացած է հետևյալ քայլերից.
Բայց եթե ենթադրենք, որ մատրիցը հորիզոնական բաժանված է, այնուհետև յուրաքանչյուր կրկնություն կարող է ներկայացվել որպես MapReduce երկու քայլ: Այս կերպ հնարավոր է նվազագույնի հասցնել տվյալների փոխանցումը յուրաքանչյուր կրկնության ընթացքում (միայն անհայտների թվին հավասար երկարությամբ վեկտորներ).
Այս մոտեցումն է, որն օգտագործվում է գծային ռեգրեսիա իրականացնելիս .
Ամփոփում
Գոյություն ունեն գծային ռեգրեսիայի վերականգնման բազմաթիվ ալգորիթմներ, բայց ոչ բոլորը կարող են կիրառվել բոլոր պայմաններում: Այսպիսով, QR-ի տարրալուծումը հիանալի է փոքր տվյալների հավաքածուներում ճշգրիտ լուծման համար: Գրադիենտ ծագումը հեշտ է իրականացնել և թույլ է տալիս արագ գտնել մոտավոր լուծում: Եվ LSQR-ն համատեղում է նախորդ երկու ալգորիթմների լավագույն հատկությունները, քանի որ այն կարող է բաշխվել, ավելի արագ զուգակցել գրադիենտ իջնելու համեմատ, ինչպես նաև թույլ է տալիս ալգորիթմի վաղ դադարեցումը, ի տարբերություն QR-ի տարրալուծման, մոտավոր լուծում գտնելու համար:
Source: www.habr.com