Fonte:
La regressione lineare è uno degli algoritmi di base per molte aree legate all'analisi dei dati. La ragione è evidente. È un algoritmo molto semplice e comprensibile, che ne favorisce un ampio utilizzo da decenni, se non secoli. L'idea è che supponiamo un rapporto lineare tra una variabile e un insieme di altre variabili, e poi cerchiamo di ricostruire questo rapporto.
Ma in questo articolo non parleremo dell'applicazione della regressione lineare per risolvere problemi pratici. Qui verranno considerate caratteristiche interessanti della realizzazione di algoritmi distribuiti per il suo ripristino, con cui ci siamo trovati ad affrontare durante la scrittura del modulo di apprendimento automatico in . Un po' di matematica di base, fondamenti di apprendimento automatico e calcolo distribuito aiutano a capire come ripristinare la regressione lineare, anche se i dati sono distribuiti tra migliaia di nodi.
Di cosa si tratta?
Ci troviamo di fronte al problema di ripristinare una dipendenza lineare. Come dati di input viene fornito un insieme di vettori di variabili presumibilmente indipendenti, a ciascuno dei quali viene associato un certo valore di una variabile dipendente. Questi dati possono essere rappresentati come due matrici:
Ora, dato che si presume una dipendenza, e in più lineare, scriviamo la nostra supposizione come un prodotto di matrici (per semplificare l'annotazione si presume qui e in seguito che il termine indipendente dell'equazione sia nascosto da 
, e l'ultima colonna della matrice 
contiene degli zeri):
Assomiglia molto a un sistema di equazioni lineari, vero? Sì, ma è probabile che questo sistema non abbia soluzioni. La ragione è il rumore, che è presente praticamente in qualsiasi dato reale. Inoltre, una causa può essere l'assenza di una dipendenza lineare in sé, che si potrebbe cercare di mitigare introducendo variabili aggiuntive che dipendono non linearmente da quelle originali. Consideriamo il seguente esempio:
Fonte:
Questo è un semplice esempio di regressione lineare, che dimostra la dipendenza di una variabile (sull'asse 
) da un'altra variabile (sull'asse 
). Affinché il sistema di equazioni lineari corrispondente a questo esempio abbia una soluzione, tutti i punti devono trovarsi esattamente su una linea retta. Ma non è così. E non si trovano su una linea retta proprio a causa del rumore (o perché l'ipotesi di una dipendenza lineare era errata). Pertanto, per ripristinare la dipendenza lineare dai dati reali è solitamente necessario introdurre un'altra ipotesi: i dati in ingresso contengono rumore e questo rumore ha . Si possono fare ipotesi anche su altri tipi di distribuzione del rumore, ma nella stragrande maggioranza dei casi si considera proprio la distribuzione normale, di cui parleremo in seguito.
Il metodo della massima verosimiglianza
. Dunque, abbiamo ipotizzato la presenza di un rumore casuale distribuito normalmente. Cosa fare in questa situazione? A tal fine, in matematica esiste e viene ampiamente utilizzato . In sintesi, consiste nella scelta e nella successiva massimizzazione.
Torniamo al ripristino della dipendenza lineare dai dati con rumore normale. Notiamo che la dipendenza lineare prevista è una media matematica 
della distribuzione normale presente. Allo stesso tempo, la probabilità che 
assuma un certo valore, a condizione della presenza di osservazioni 
, si presenta nel seguente modo:
Ora sostituiamo 
e 
le variabili che ci servono:
Resta solo trovare il vettore 
, per il quale questa probabilità è massima. Per massimizzare tale funzione è conveniente prima logaritmizzarla (il logaritmo della funzione raggiungerà il massimo nello stesso punto in cui si trova la funzione stessa):
Ciò si riduce, a sua volta, a minimizzare la seguente funzione:
A proposito, questo è chiamato metodo . Spesso tutte le considerazioni sopra riportate vengono omesse e si utilizza semplicemente questo metodo.
Scomposizione QR
Il minimo della funzione sopra riportata può essere trovato se si trova il punto in cui il gradiente di questa funzione è nullo. E il gradiente sarà scritto nel seguente modo:
è un metodo matrice per risolvere il problema di minimizzazione utilizzato nel metodo dei minimi quadrati. Pertanto, riscriviamo l'equazione in forma matriciale:
Pertanto, scomponiamo la matrice 
in matrici 
e 
e svolgiamo una serie di trasformazioni (l'algoritmo di fattorizzazione QR non verrà considerato qui, soltanto il suo utilizzo rispetto al compito assegnato):
Matrice 
è ortogonale. Questo ci consente di liberarci dal prodotto 
:
E se sostituiamo 
in 
, otteniamo 
. Considerando che 
è una matrice triangolare superiore, appare nel modo seguente:
Questo può essere risolto con il metodo di sostituzione. L'elemento 
si trova come 
, l'elemento precedente 
si trova come 
e così via.
Qui vale la pena notare che la complessità dell'algoritmo risultante grazie all'uso della fattorizzazione QR è pari a 
. Tuttavia, nonostante l'operazione di moltiplicazione delle matrici si presti bene alla parallelizzazione, scrivere una versione distribuita efficace di questo algoritmo non sembra possibile.
Discesa del gradiente
Parlando della minimizzazione di una certa funzione, è sempre utile ricordare il metodo (stocastico) del gradiente discendente. Questo è un metodo semplice ed efficace per la minimizzazione, basato sul calcolo iterativo del gradiente della funzione in un punto e sul successivo spostamento nella direzione opposta al gradiente. Ogni passo di questo tipo avvicina la soluzione al minimo. Il gradiente assume ancora la stessa forma:
Inoltre, questo metodo si presta bene alla parallelizzazione e distribuzione grazie alle proprietà lineari dell'operatore gradiente. Notiamo che nella formula sopra riportata, sotto il segno di sommatoria ci sono termini indipendenti. In altre parole, possiamo calcolare il gradiente in modo indipendente per tutti gli indici 
da uno fino a 
, parallelamente, calcolare il gradiente per gli indici da 
fino a 
. Poi sommare i gradienti risultanti. Il risultato della somma sarà lo stesso di se avessimo calcolato il gradiente per gli indici da uno fino a 
. Pertanto, se i dati sono distribuiti tra più parti, il gradiente può essere calcolato indipendentemente su ciascuna parte, e poi i risultati di questi calcoli possono essere sommati per ottenere il risultato finale:
Dal punto di vista dell'implementazione, ciò rientra nella paradigmatica . In ogni fase del gradiente discendente, a ciascun nodo di dati viene assegnato un compito per calcolare il gradiente, quindi i gradienti calcolati vengono raccolti insieme e il risultato della loro somma viene utilizzato per migliorare il risultato.
Nonostante la semplicità di implementazione e la possibilità di esecuzione nella paradigmi MapReduce, il gradiente discendente presenta anche i suoi svantaggi. In particolare, il numero di passi necessari per raggiungere la convergenza è significativamente maggiore rispetto ad altri metodi più specializzati.
LSQR
è un altro metodo per risolvere il compito assegnato, adatto sia per la ricostruzione della regressione lineare che per la risoluzione di sistemi di equazioni lineari. La sua principale caratteristica è che combina i vantaggi dei metodi matriciali con l'approccio iterativo. Le implementazioni di questo metodo possono essere trovate sia nella libreria , sia in . Non verrà fornita qui la descrizione di questo metodo (puoi trovarla nell'articolo ). Invece, verrà dimostrato un approccio che consente di adattare LSQR per l'esecuzione in un ambiente distribuito.
Alla base del metodo LSQR c'è . Questa è una procedura iterativa, ogni iterazione consiste nei seguenti passaggi:
Ma se assumiamo che la matrice 
sia partizionata orizzontalmente, allora ogni iterazione può essere rappresentata come due passaggi MapReduce. In questo modo si riesce a minimizzare il passaggio di dati durante ciascuna delle iterazioni (solo vettori di lunghezza pari al numero di incognite):
Proprio questo approccio viene utilizzato nell'implementazione della regressione lineare in .
Conclusione
Esistono molti algoritmi per la ricostruzione della regressione lineare, ma non tutti possono essere applicati in qualsiasi condizione. Ad esempio, la decomposizione QR è ottima per risolvere con precisione su piccole masse di dati. Il gradiente discendente si implementa facilmente e consente di trovare rapidamente una soluzione approssimata. LSQR, d'altra parte, combina le migliori caratteristiche dei due algoritmi precedenti, poiché può essere distribuito, converge più rapidamente rispetto al gradiente discendente e consente anche un arresto anticipato dell'algoritmo, a differenza della decomposizione QR per la ricerca di soluzioni approssimate.
Fonte: habr.com
