Forrás:
A lineáris regresszió az adatelemzéssel kapcsolatos számos területen az egyik alapvető algoritmus. Ennek oka nyilvánvaló. Ez egy nagyon egyszerű és érthető algoritmus, amely sok tíz, ha nem több száz éve hozzájárult széles körű használatához. Az ötlet az, hogy feltételezzük egy változó lineáris függését más változók halmazától, majd megpróbáljuk visszaállítani ezt a függőséget.
De ez a cikk nem arról szól, hogy a lineáris regressziót gyakorlati problémák megoldására használjuk. Itt megvizsgáljuk az elosztott algoritmusok megvalósításának érdekes jellemzőit annak helyreállításához, amelyekkel egy gépi tanulási modul írásakor találkoztunk. . Egy kis matematikai alapismeret, a gépi tanulás és az elosztott számítástechnika segíthet kitalálni, hogyan hajthat végre lineáris regressziót még akkor is, ha az adatok több ezer csomópont között vannak elosztva.
Miről beszélünk?
A lineáris függőség helyreállításának feladatával állunk szemben. Bemeneti adatként feltehetően független változók vektorkészletét adjuk meg, amelyek mindegyike a függő változó egy bizonyos értékéhez kapcsolódik. Ezek az adatok két mátrix formájában ábrázolhatók:
Most, mivel a függőség feltételezett, ráadásul lineáris, feltevésünket mátrixok szorzata formájában írjuk fel (a rögzítés egyszerűsítése érdekében itt és alább azt feltételezzük, hogy az egyenlet szabad tagja mögött van elrejtve , és a mátrix utolsó oszlopa egységet tartalmaz):
Nagyon úgy hangzik, mint egy lineáris egyenletrendszer, nem igaz? Úgy tűnik, de nagy valószínűséggel nem lesz megoldás egy ilyen egyenletrendszerre. Ennek oka a zaj, ami szinte minden valós adatban jelen van. Egy másik ok lehet a lineáris függés mint olyan hiánya, amely ellen további, az eredeti változóktól nemlineárisan függő változók bevezetésével lehet küzdeni. Tekintsük a következő példát:
Forrás:
Ez egy egyszerű példa a lineáris regresszióra, amely megmutatja egy változó kapcsolatát (a tengely mentén ) egy másik változótól (a tengely mentén ). Ahhoz, hogy a példának megfelelő lineáris egyenletrendszernek legyen megoldása, minden pontnak pontosan ugyanazon az egyenesen kell lennie. De ez nem igaz. De nem éppen a zaj miatt fekszenek ugyanazon az egyenesen (vagy azért, mert a lineáris összefüggés feltételezése hibás volt). Így ahhoz, hogy a valós adatokból lineáris kapcsolatot állítsunk vissza, általában még egy feltételezést kell bevezetni: a bemeneti adatok zajt tartalmaznak, és ez a zaj . Feltételezéseket lehet tenni más típusú zajeloszlásról is, de az esetek túlnyomó többségében a normál eloszlást veszik figyelembe, amelyről a továbbiakban még lesz szó.
Maximális valószínűség módszere
Tehát véletlenszerű, normális eloszlású zaj jelenlétét feltételeztük. Mit kell tenni ilyen helyzetben? Erre az esetre a matematikában széles körben használják és használják . Röviden, a lényeg a választásban rejlik és ennek későbbi maximalizálása.
Visszatérünk a lineáris kapcsolat helyreállításához normál zajú adatokból. Vegyük észre, hogy a feltételezett lineáris összefüggés a matematikai elvárás létező normális eloszlás. Ugyanakkor annak a valószínűsége ilyen vagy olyan értéket vesz fel, a megfigyelhető elemek jelenlététől függően , alábbiak szerint:
Most cseréljük ki и A szükséges változók a következők:
Már csak a vektort kell megtalálni , amelynél ez a valószínűség maximális. Egy ilyen függvény maximalizálása érdekében célszerű először egy logaritmust venni belőle (a függvény logaritmusa ugyanazon a ponton éri el a maximumot, mint maga a függvény):
Ami viszont a következő függvény minimalizálását jelenti:
Ezt egyébként módszernek hívják . Gyakran a fenti megfontolásokat figyelmen kívül hagyják, és egyszerűen ezt a módszert használják.
QR-bontás
A fenti függvény minimumát úgy találhatjuk meg, hogy megkeressük azt a pontot, ahol ennek a függvénynek a gradiense nulla. És a gradiens a következőképpen lesz írva:
egy mátrix módszer a legkisebb négyzetek módszerében használt minimalizálási probléma megoldására. Ebben a tekintetben átírjuk az egyenletet mátrix formában:
Tehát felbontjuk a mátrixot mátrixokhoz и és hajtson végre egy sor transzformációt (magát a QR-felbontási algoritmust itt nem vesszük figyelembe, csak annak használatát az adott feladattal kapcsolatban):
mátrix merőleges. Ez lehetővé teszi számunkra, hogy megszabaduljunk a munkától :
És ha lecseréled on , akkor menni fog . Tekintve, hogy egy felső háromszög mátrix, így néz ki:
Ezt helyettesítési módszerrel lehet megoldani. Elem néven található , előző elem néven található és így tovább.
Itt érdemes megjegyezni, hogy a kapott algoritmus bonyolultsága a QR dekompozíció alkalmazása miatt egyenlő . Ráadásul annak ellenére, hogy a mátrixszorzási művelet jól párhuzamosított, ennek az algoritmusnak nem lehet hatékony elosztott változatát írni.
Gradiens Descent
Amikor egy függvény minimalizálásáról beszélünk, mindig érdemes megjegyezni a (sztochasztikus) gradiens süllyedés módszerét. Ez egy egyszerű és hatékony minimalizálási módszer, amely egy függvény gradiensének iteratív kiszámításán alapul egy pontban, majd eltolja azt a gradienssel ellentétes irányba. Minden ilyen lépés közelebb viszi a megoldást a minimumhoz. A gradiens továbbra is ugyanúgy néz ki:
Ez a módszer a gradiens operátor lineáris tulajdonságai miatt is jól párhuzamosított és elosztott. Vegye figyelembe, hogy a fenti képletben az összeg jele alatt független tagok találhatók. Más szóval, a gradienst minden indexre függetlenül ki tudjuk számítani elsőtől ig , ezzel párhuzamosan számítsa ki a gradienst az indexekre -val a . Ezután adjuk hozzá a kapott színátmeneteket. Az összeadás eredménye ugyanaz lesz, mintha azonnal kiszámítanánk az indexek gradiensét az elsőtől . Így, ha az adatokat több adat között osztjuk el, a gradiens minden egyes darabon függetlenül számítható, majd ezeknek a számításoknak az eredményeit összegezve megkapjuk a végeredményt:
A megvalósítás szempontjából ez megfelel a paradigmának . A gradiens süllyedésének minden lépésében minden adatcsomóponthoz feladatot küldenek a gradiens kiszámításához, majd a számított gradienseket összegyűjtik, és az összegük eredményét az eredmény javítására használják fel.
A könnyű implementáció és a MapReduce paradigmában való végrehajtási képesség ellenére a gradiens süllyedésnek is vannak hátrányai. Különösen a konvergencia eléréséhez szükséges lépések száma lényegesen magasabb más speciálisabb módszerekhez képest.
LSQR
A probléma megoldásának egy másik módszere, amely mind a lineáris regresszió helyreállítására, mind a lineáris egyenletrendszerek megoldására alkalmas. Fő jellemzője, hogy egyesíti a mátrix módszerek előnyeit és az iteratív megközelítést. Ennek a módszernek a megvalósítása mindkét könyvtárban megtalálható és be . Ennek a módszernek a leírását itt nem adjuk meg (a cikkben található ). Ehelyett egy olyan megközelítést mutatunk be, amely az LSQR-t az elosztott környezetben történő végrehajtáshoz igazítja.
Az LSQR módszer azon alapul . Ez egy iteratív eljárás, minden iteráció a következő lépésekből áll:
De ha feltételezzük, hogy a mátrix vízszintesen particionálva van, akkor minden iteráció két MapReduce lépésként ábrázolható. Ily módon minimalizálható az adatátvitel minden iteráció során (csak az ismeretlenek számával megegyező hosszúságú vektorok):
Ezt a megközelítést használják a lineáris regresszió alkalmazásakor .
Következtetés
Számos lineáris regressziós helyreállítási algoritmus létezik, de nem mindegyik alkalmazható minden körülmények között. A QR dekompozíció tehát kiválóan alkalmas kis adathalmazok pontos megoldására. A gradiens süllyedés egyszerűen megvalósítható, és lehetővé teszi a hozzávetőleges megoldás gyors megtalálását. Az LSQR pedig az előző két algoritmus legjobb tulajdonságait ötvözi, hiszen elosztható, gyorsabban konvergál a gradiens süllyedéshez képest, és lehetővé teszi az algoritmus korai leállítását is, ellentétben a QR dekompozícióval, hogy közelítő megoldást találjunk.
Forrás: will.com