Source:
Сызыктуу регрессия маалыматтарды талдоо менен байланышкан көптөгөн аймактар үчүн негизги алгоритмдердин бири болуп саналат. Мунун себеби айдан ачык. Бул абдан жөнөкөй жана түшүнүктүү алгоритм, анын көптөгөн ондогон, болбосо жүздөгөн жылдар бою кеңири колдонулушуна салым кошкон. Идея бир өзгөрмөнүн башка өзгөрмөлөрдүн жыйындысына сызыктуу көз карандылыгын кабыл алып, андан кийин бул көз карандылыкты калыбына келтирүүгө аракет кылууда.
Бирок бул макала практикалык маселелерди чечүү үчүн сызыктуу регрессияны колдонуу жөнүндө эмес. Бул жерде биз аны калыбына келтирүү үчүн бөлүштүрүлгөн алгоритмдерди ишке ашыруунун кызыктуу өзгөчөлүктөрүн карап чыгабыз, алар машинаны үйрөнүү модулун жазууда кездешкен. . Бир аз негизги математика, машина үйрөнүү жана бөлүштүрүлгөн эсептөө маалыматтарыңыз миңдеген түйүндөр боюнча бөлүштүрүлгөндө да сызыктуу регрессияны кантип аткарууга болорун аныктоого жардам берет.
Биз эмне жөнүндө сүйлөшүп жатабыз?
Биздин алдыбызда сызыктуу көз карандылыкты калыбына келтирүү милдети турат. Киргизилген маалыматтар катары ар бири көз каранды өзгөрмөнүн белгилүү бир мааниси менен байланышкан болжолдуу көз карандысыз өзгөрмөлөрдүн векторлорунун жыйындысы берилет. Бул маалыматтар эки матрица түрүндө берилиши мүмкүн:
Эми, көз карандылык кабыл алынгандыктан, жана, андан тышкары, сызыктуу, биз өз божомолубузду матрицалардын көбөйтүндүсү түрүндө жазабыз (жазууну жөнөкөйлөтүү үчүн, бул жерде жана ылдыйда теңдеменин эркин мүчөсү артында катылган деп болжолдонууда) , жана матрицанын акыркы тилкеси бирдиктерди камтыйт):
Сызыктуу теңдемелер системасына абдан окшош, туурабы? Кыязы, бирок, сыягы, мындай теңдемелер системасынын чечимдери жок болот. Мунун себеби ызы-чуу болуп саналат, ал дээрлик бардык реалдуу маалыматтарда бар. Дагы бир себеп сызыктуу көз карандылыктын жоктугу болушу мүмкүн, аны менен сызыктуу эмес көз каранды болгон кошумча өзгөрмөлөрдү киргизүү аркылуу күрөшүүгө болот. Төмөнкү мисалды карап көрөлү:
Source:
Бул бир өзгөрмөнүн байланышын көрсөткөн сызыктуу регрессиянын жөнөкөй мисалы (ок боюнча ) башка өзгөрмөдөн (октун боюнда ). Бул мисалга туура келген сызыктуу теңдемелер системасы чечимге ээ болушу үчүн бардык чекиттер так бир түз сызыкта жатышы керек. Бирок бул андай эмес. Бирок алар бир түз сызыкта так ызы-чуунун (же сызыктуу байланышты болжолдоо жаңылыш болгондугу үчүн) так эмес. Ошентип, реалдуу маалыматтардан сызыктуу байланышты калыбына келтирүү үчүн, адатта, дагы бир божомолду киргизүү керек: киргизилген маалыматтарда ызы-чуу бар жана бул ызы-чуу бар . Сиз ызы-чууну бөлүштүрүүнүн башка түрлөрү жөнүндө божомолдорду жасай аласыз, бирок көпчүлүк учурларда бул нормалдуу бөлүштүрүү болуп саналат, ал мындан ары талкууланат.
Максималдуу ыктымалдык ыкмасы
Ошентип, биз кокустук, нормалдуу бөлүштүрүлгөн ызы-чуунун болушун болжолдодук. Мындай кырдаалда эмне кылуу керек? Бул үчүн математикада бар жана кеңири колдонулат . Кыскасы, анын маңызы тандоодо жана андан кийинки максималдуу.
Биз кадимки ызы-чуу менен маалыматтардан сызыктуу байланышты калыбына келтирүүгө кайтып келебиз. Болжолдонгон сызыктуу байланыш математикалык күтүү экенин эске алыңыз учурдагы нормалдуу бөлүштүрүү. Ошол эле учурда, ыктымалдыгы байкала турган нерселердин болушуна жараша тигил же бул мааниге ээ болот , төмөнкүдөй:
Эми анын ордуна алмаштыралы и Бизге керек болгон өзгөрмөлөр:
Болгону векторду табуу гана калды , бул ыктымалдык максималдуу болуп саналат. Мындай функцияны максималдаштыруу үчүн адегенде анын логарифмасын алуу ыңгайлуу (функциянын логарифминин максимумуна функциянын өзү менен бирдей чекитте жетет):
Бул, өз кезегинде, төмөнкү функцияны минималдаштырууга алып келет:
Айтмакчы, бул ыкма деп аталат . Көбүнчө жогоруда айтылгандардын бардыгы эске алынбай, бул ыкма жөн гана колдонулат.
QR ажыратуу
Жогорудагы функциянын минимумун бул функциянын градиенти нөлгө барабар болгон чекитти табуу менен табууга болот. Жана градиент төмөнкүчө жазылат:
эң аз квадраттар методунда колдонулган минимизациялоо маселесин чечүүнүн матрицалык ыкмасы. Ушуга байланыштуу теңдемени матрица түрүндө кайра жазабыз:
Ошентип, биз матрицаны ажыратабыз матрицаларга и жана бир катар трансформацияларды аткарыңыз (бул жерде QR декомпозиция алгоритминин өзү каралбайт, анын тапшырмага карата колдонулушу гана):
Булакта ортогоналдык болуп саналат. Бул бизге иштен кутулууга мумкундук берет :
Жана алмаштырсаңыз боюнча , анда ал иштейт . Ошону эске алып жогорку үч бурчтук матрица болуп саналат, ал төмөнкүдөй көрүнөт:
Бул алмаштыруу ыкмасын колдонуу менен чечсе болот. Элемент катары жайгашкан , мурунку элемент катары жайгашкан жана башкалар.
Бул жерде белгилей кетүү керек, QR декомпозициясын колдонуудан улам пайда болгон алгоритмдин татаалдыгы . Анын үстүнө, матрицаны көбөйтүү операциясы жакшы параллелдүү болгонуна карабастан, бул алгоритмдин эффективдүү бөлүштүрүлгөн версиясын жазуу мүмкүн эмес.
Градиенттин түшүүсү
Функцияны минималдаштыруу жөнүндө сөз кылганда, градиенттин (стохастикалык) түшүү ыкмасын эстен чыгарбоо керек. Бул бир чекиттеги функциянын градиентин итеративдик эсептөөгө жана андан кийин аны градиентке карама-каршы багытта жылдырууга негизделген жөнөкөй жана эффективдүү минимизациялоо ыкмасы. Ар бир мындай кадам чечимди минимумга жакындатат. Градиент мурдагыдай эле көрүнөт:
Бул ыкма да градиент операторунун сызыктуу касиеттеринен улам жакшы параллелдештирилген жана бөлүштүрүлгөн. Жогорудагы формулада сумма белгисинин астында өз алдынча терминдер бар экенине көңүл буруңуз. Башкача айтканда, биз бардык индекстер үчүн градиентти өз алдынча эсептей алабыз биринчиден , муну менен катар индекстер үчүн градиентти эсептеңиз үчүн . Андан кийин пайда болгон градиенттерди кошуңуз. Кошуунун натыйжасы биз дароо эле биринчиден баштап индекстер үчүн градиентти эсептегендей болот . Ошентип, эгерде маалыматтар бир нече маалыматтардын арасында бөлүштүрүлсө, анда градиент ар бир бөлүк боюнча өз алдынча эсептелип, андан кийин бул эсептөөлөрдүн натыйжалары жыйынтыкталган жыйынтыкты алуу үчүн жыйынтыкталышы мүмкүн:
Ишке ашыруу көз карашынан алганда, бул парадигмага туура келет . Градиенттин түшүүсүнүн ар бир кадамында градиентти эсептөө үчүн ар бир маалымат түйүнүнө тапшырма жөнөтүлөт, андан кийин эсептелген градиенттер чогуу чогултулат жана натыйжаны жакшыртуу үчүн алардын суммасынын натыйжасы колдонулат.
Ишке ашыруунун жөнөкөйлүгүнө жана MapReduce парадигмасында аткаруу мүмкүнчүлүгүнө карабастан, градиенттин түшүүсүнүн да кемчиликтери бар. Атап айтканда, конвергенцияга жетишүү үчүн зарыл болгон кадамдардын саны башка адистештирилген методдорго салыштырмалуу кыйла жогору.
LSQR
сызыктуу регрессияны калыбына келтирүү үчүн да, сызыктуу теңдемелер системасын чечүү үчүн да ылайыктуу болгон маселени чечүүнүн дагы бир ыкмасы. Анын негизги өзгөчөлүгү матрицалык ыкмалардын артыкчылыктарын жана итеративдик ыкманы айкалыштырганында. Бул ыкманын ишке ашырылышын эки китепканадан тапса болот жана . Бул ыкманын сүрөттөлүшү бул жерде берилбейт (ал макалада тапса болот ). Анын ордуна, LSQRди бөлүштүрүлгөн чөйрөдө аткарууга ылайыкташтыруу ыкмасы көрсөтүлөт.
LSQR ыкмасы негизделген . Бул кайталануучу процедура, ар бир итерация төмөнкү кадамдардан турат:
Бирок матрица деп ойлосок горизонталдуу түрдө бөлүнгөн болсо, анда ар бир итерация эки MapReduce кадамы катары көрсөтүлүшү мүмкүн. Мына ушундай жол менен ар бир итерация учурунда берилиштерди өткөрүп берүүнү минималдаштырууга болот (узундугу белгисиздердин санына барабар болгон векторлор гана):
Дал ушул ыкма сызыктуу регрессияны ишке ашырууда колдонулат .
жыйынтыктоо
Көптөгөн сызыктуу регрессияны калыбына келтирүү алгоритмдери бар, бирок алардын бардыгын бардык шарттарда колдонууга болбойт. Ошентип, QR декомпозициясы кичинекей маалымат топтомдорун так чечүү үчүн эң сонун. Градиенттин түшүүсүн ишке ашыруу оңой жана болжолдуу чечимди тез табууга мүмкүндүк берет. Ал эми LSQR мурунку эки алгоритмдин эң жакшы касиеттерин айкалыштырат, анткени ал бөлүштүрүлүшү мүмкүн, градиенттин түшүүсүнө салыштырмалуу тезирээк биригет, ошондой эле QR декомпозициясынан айырмаланып, болжолдуу чечимди табуу үчүн алгоритмди эрте токтотууга мүмкүндүк берет.
Source: www.habr.com