Källa:
Linjär regression är en av de grundläggande algoritmerna för många områden relaterade till dataanalys. Anledningen till detta är uppenbar. Detta är en mycket enkel och begriplig algoritm, som har bidragit till dess utbredda användning i många tiotals, om inte hundratals, år. Tanken är att vi antar ett linjärt beroende av en variabel på en uppsättning andra variabler och sedan försöker återställa detta beroende.
Men den här artikeln handlar inte om att använda linjär regression för att lösa praktiska problem. Här kommer vi att överväga intressanta funktioner i implementeringen av distribuerade algoritmer för återställning, som vi stötte på när vi skrev en maskininlärningsmodul i . Lite grundläggande matematik, maskininlärning och distribuerad beräkning kan hjälpa dig att ta reda på hur du utför linjär regression även när dina data är fördelade över tusentals noder.
Vad pratar vi om?
Vi står inför uppgiften att återställa linjärt beroende. Som indata ges en uppsättning vektorer av förment oberoende variabler, som var och en är associerad med ett visst värde på den beroende variabeln. Dessa data kan representeras i form av två matriser:
Nu, eftersom beroendet antas, och dessutom linjärt, kommer vi att skriva vårt antagande i form av en produkt av matriser (för att förenkla registreringen, här och nedan antas det att ekvationens fria term döljs bakom , och den sista kolumnen i matrisen innehåller enheter):
Låter mycket som ett system av linjära ekvationer, eller hur? Det verkar, men troligtvis kommer det inte att finnas några lösningar på ett sådant ekvationssystem. Anledningen till detta är brus, som finns i nästan alla verkliga data. En annan orsak kan vara avsaknaden av linjärt beroende som sådant, vilket kan bekämpas genom att införa ytterligare variabler som olinjärt beror på de ursprungliga. Tänk på följande exempel:
Källa:
Detta är ett enkelt exempel på linjär regression som visar förhållandet mellan en variabel (längs axeln ) från en annan variabel (längs axeln ). För att det linjära ekvationssystemet som motsvarar detta exempel ska ha en lösning måste alla punkter ligga exakt på samma räta linje. Men det är inte sant. Men de ligger inte på samma räta linje just på grund av brus (eller för att antagandet om ett linjärt samband var felaktigt). För att återställa ett linjärt förhållande från verkliga data är det därför vanligtvis nödvändigt att införa ytterligare ett antagande: indata innehåller brus och detta brus har . Man kan göra antaganden om andra typer av brusfördelning, men i de allra flesta fall är det normalfördelningen som beaktas, som kommer att diskuteras vidare.
Maximal likelihood-metod
Så vi antog närvaron av slumpmässigt normalfördelat brus. Vad ska man göra i en sådan situation? För detta fall i matematik finns och används ofta . Kort sagt, dess väsen ligger i valet och dess efterföljande maximering.
Vi återgår till att återställa ett linjärt förhållande från data med normalt brus. Observera att det antagna linjära sambandet är den matematiska förväntan befintlig normalfördelning. Samtidigt är sannolikheten att antar ett eller annat värde, med förbehåll för närvaron av observerbara , som följer:
Låt oss nu ersätta istället и Variablerna vi behöver är:
Allt som återstår är att hitta vektorn , där denna sannolikhet är maximal. För att maximera en sådan funktion är det bekvämt att först ta en logaritm av den (funktionens logaritm når ett maximum vid samma punkt som själva funktionen):
Vilket i sin tur handlar om att minimera följande funktion:
Detta kallas förresten en metod . Ofta utelämnas alla ovanstående överväganden och denna metod används helt enkelt.
QR-sönderdelning
Minimum av ovanstående funktion kan hittas genom att hitta den punkt där gradienten för denna funktion är noll. Och gradienten kommer att skrivas som följer:
är en matrismetod för att lösa det minimeringsproblem som används i minsta kvadratmetoden. I detta avseende skriver vi om ekvationen i matrisform:
Så vi bryter ner matrisen till matriser и och utför en serie transformationer (Själva QR-sönderdelningsalgoritmen kommer inte att beaktas här, bara dess användning i förhållande till uppgiften):
matris är ortogonal. Detta gör att vi kan bli av med arbetet :
Och om du byter ut på , så löser det sig . Med tanke på att är en övre triangulär matris ser den ut så här:
Detta kan lösas med hjälp av substitutionsmetoden. Element ligger som , föregående element ligger som och så vidare.
Det är värt att notera här att komplexiteten hos den resulterande algoritmen på grund av användningen av QR-nedbrytning är lika med . Dessutom, trots det faktum att matrismultiplikationsoperationen är väl parallelliserad, är det inte möjligt att skriva en effektiv distribuerad version av denna algoritm.
Gradient Descent
När man talar om att minimera en funktion är det alltid värt att komma ihåg metoden för (stokastisk) gradientnedstigning. Detta är en enkel och effektiv minimeringsmetod baserad på att iterativt beräkna gradienten för en funktion vid en punkt och sedan flytta den i motsatt riktning mot gradienten. Varje sådant steg för lösningen närmare ett minimum. Gradienten ser fortfarande likadan ut:
Denna metod är också väl parallelliserad och fördelad på grund av gradientoperatorns linjära egenskaper. Observera att i formeln ovan, under summatecknet finns det oberoende termer. Med andra ord kan vi beräkna gradienten oberoende för alla index från första till , parallellt med detta, beräkna gradienten för index med до . Lägg sedan till de resulterande gradienterna. Resultatet av tillägget blir detsamma som om vi omedelbart beräknade gradienten för index från första till . Således, om data fördelas på flera delar av data, kan gradienten beräknas oberoende på varje bit, och sedan kan resultaten av dessa beräkningar summeras för att erhålla det slutliga resultatet:
Ur implementeringssynpunkt passar detta paradigmet . Vid varje steg av gradientnedstigning skickas en uppgift till varje datanod för att beräkna gradienten, sedan samlas de beräknade gradienterna ihop och resultatet av deras summa används för att förbättra resultatet.
Trots den enkla implementeringen och möjligheten att köra i MapReduce-paradigmet har gradientnedstigning också sina nackdelar. I synnerhet är antalet steg som krävs för att uppnå konvergens betydligt högre jämfört med andra mer specialiserade metoder.
LSQR
är en annan metod för att lösa problemet, som är lämplig både för att återställa linjär regression och för att lösa linjära ekvationssystem. Dess huvudsakliga egenskap är att den kombinerar fördelarna med matrismetoder och ett iterativt tillvägagångssätt. Implementeringar av denna metod finns i båda biblioteken , och i . En beskrivning av denna metod kommer inte att ges här (den finns i artikeln ). Istället kommer ett tillvägagångssätt att demonstreras för att anpassa LSQR till exekvering i en distribuerad miljö.
LSQR-metoden bygger på . Detta är en iterativ procedur, varje iteration består av följande steg:
Men om vi antar att matrisen är horisontellt uppdelad, då kan varje iteration representeras som två MapReduce-steg. På detta sätt är det möjligt att minimera dataöverföringar under varje iteration (endast vektorer med en längd lika med antalet okända):
Det är detta tillvägagångssätt som används när man implementerar linjär regression i .
Slutsats
Det finns många linjära regressionsåterställningsalgoritmer, men alla kan inte tillämpas under alla förhållanden. Så QR-sönderdelning är utmärkt för exakta lösningar på små datamängder. Gradientnedstigning är enkel att implementera och låter dig snabbt hitta en ungefärlig lösning. Och LSQR kombinerar de bästa egenskaperna hos de två föregående algoritmerna, eftersom den kan distribueras, konvergerar snabbare jämfört med gradientnedstigning och tillåter också tidigt stopp av algoritmen, till skillnad från QR-sönderdelning, för att hitta en ungefärlig lösning.
Källa: will.com