Fonte:
La regressione lineare è uno degli algoritmi fondamentali per molte aree legate all'analisi dei dati. La ragione è ovvia: è un algoritmo molto semplice e comprensibile, che ne facilita l'ampio utilizzo da decenni, se non da secoli. L'idea è che si presume una dipendenza lineare di una variabile da un insieme di altre variabili, e poi si cerca di ripristinare questa dipendenza.
Ma in questo articolo non si parlerà dell'applicazione della regressione lineare per risolvere problemi pratici. Verranno esaminate caratteristiche interessanti dell'implementazione di algoritmi distribuiti per il suo ripristino, con cui ci siamo imbattuti durante la scrittura di un modulo di machine learning in . Un po' di matematica di base, nozioni fondamentali di machine learning e calcolo distribuito aiuteranno a comprendere come ripristinare la regressione lineare, anche quando i dati sono distribuiti tra migliaia di nodi.
Di cosa si tratta?
La nostra sfida è ricostruire una dipendenza lineare. I dati in ingresso consistono in un insieme di vettori di variabili presumibilmente indipendenti, ciascuno dei quali è associato a un certo valore di una variabile dipendente. Questi dati possono essere rappresentati sotto forma di due matrici:
Ora, dato che si presume una dipendenza, e inoltre lineare, esprimiamo la nostra ipotesi come un prodotto di matrici (per semplificare la notazione, si presume che il termine costante dell'equazione sia nascosto da 
, e l'ultima colonna della matrice 
contiene delle unità):
Ricorda molto un sistema di equazioni lineari, vero? Sembra così, ma è probabile che tale sistema di equazioni non abbia soluzioni. La causa è il rumore, presente praticamente in tutti i dati reali. Inoltre, potrebbe mancare una dipendenza lineare a cui si possa tentare di ovviare introducendo variabili aggiuntive che dipendono in modo non lineare dalle 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 sulla stessa retta. Ma non è così. Non si trovano sulla stessa 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, di solito è 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.
Metodo di massima verosimiglianza
Quindi, abbiamo ipotizzato la presenza di rumore casuale normalmente distribuito. Come comportarsi in questa situazione? A questo scopo, in matematica esiste e viene ampiamente utilizzato . In breve, esso consiste nella scelta e nella successiva massimizzazione.
Torniamo all'analisi della dipendenza lineare basata su dati con rumore normale. Notiamo che la dipendenza lineare prevista è l'aspettativa matematica 
di una distribuzione normale esistente. Allo stesso tempo, la probabilità che 
prenda un certo valore, a condizione che siano osservabili 
, appare nel modo seguente:
Sostituiamo ora 
e 
le variabili di cui abbiamo bisogno:
Restiamo solo da trovare il vettore 
, per cui questa probabilità è massima. Per massimizzare una tale funzione, è conveniente prima logaritmarla (il logaritmo della funzione raggiungerà il massimo nello stesso punto della funzione stessa):
Il che, a sua volta, si riduce a minimizzare la seguente funzione:
A proposito, questo è conosciuto come il metodo . Spesso tutte le considerazioni sopra citate vengono trascurate e si utilizza semplicemente questo metodo.
Decomposizione QR
Il minimo della funzione sopra citata può essere trovato individuando il punto in cui il gradiente di questa funzione è zero. E il gradiente verrà scritto come segue:
è un metodo matriciale per risolvere il problema della minimizzazione utilizzato nel metodo dei minimi quadrati. Pertanto, riscriveremo l'equazione in forma matriciale:
Quindi, decomponiamo la matrice 
in matrici 
e 
e eseguiamo una serie di trasformazioni (l'algoritmo di decomposizione QR non verrà trattato qui, solo il suo utilizzo rispetto al problema proposto):
La matrice 
è ortogonale. Questo ci permette di eliminare il prodotto di 
:
E se sostituiamo 
con 
, otterremo 
. Considerando che 
è una matrice triangolare superiore, appare in questo modo:
Questo può essere risolto mediante sostituzione. L'elemento 
si trova come 
, elemento precedente 
si trova come 
e così via.
Vale la pena notare che la complessità dell'algoritmo risultante, grazie all'utilizzo della decomposizione QR, è 
. Tuttavia, nonostante l'operazione di moltiplicazione delle matrici si presti bene alla parallelizzazione, non è possibile scrivere una versione distribuita efficace di questo algoritmo.
Discesa del gradiente
Parlando della minimizzazione di una certa funzione, è sempre utile ricordare il metodo del (gradiant descent) stocastico. Questo è un metodo semplice ed efficace di minimizzazione, basato sul calcolo iterativo del gradiente della funzione in un punto e sul successivo spostamento in direzione opposta al gradiente. Ogni passo avvicina la soluzione al minimo. Il gradiente rimane lo stesso:
Inoltre, questo metodo si presta bene alla parallelizzazione e alla distribuzione grazie alle proprietà lineari dell'operatore gradiente. Notiamo che nella formula sopra menzionata, sotto il segno di somma, ci sono termini indipendenti. In altre parole, possiamo calcolare il gradiente in modo indipendente per tutti gli indici. 
da primo a 
, parallelamente, possiamo calcolare il gradiente per gli indici da 
fino a 
. Poi sommiamo i gradienti ottenuti. Il risultato della somma sarà lo stesso come se avessimo calcolato direttamente il gradiente per gli indici da primo a 
. Pertanto, se i dati sono distribuiti tra più parti, il gradiente può essere calcolato indipendentemente su ogni parte, e poi i risultati di questi calcoli possono essere sommati per ottenere il risultato finale:
Dal punto di vista dell'implementazione, questo rientra nella paradigmaticità . Ad ogni passo della discesa del gradiente, un compito per il calcolo del gradiente viene inviato a ciascun nodo di dati, quindi i gradienti calcolati vengono raccolti insieme e il risultato della loro somma è utilizzato per migliorare il risultato.
Nonostante la semplicità di implementazione e la possibilità di esecuzione nella paradigmaticità MapReduce, la discesa del gradiente ha anche i suoi svantaggi. In particolare, il numero di passaggi necessari per raggiungere la convergenza è notevolmente maggiore rispetto ad altri metodi più specializzati.
LSQR
è un altro metodo per risolvere il problema, adatto sia per il recupero della regressione lineare che per la risoluzione di sistemi di equazioni lineari. La sua principale caratteristica è che combina i vantaggi dei metodi matriciali e dell'approccio iterativo. Le implementazioni di questo metodo possono essere trovate sia nelle librerie , sia in . Non verrà fornita una descrizione di questo metodo (può essere trovata nell'articolo ). Invece, verrà mostrato un approccio che consente di adattare LSQR per l'esecuzione in un ambiente distribuito.
Alla base del metodo LSQR c'è . Si tratta di una procedura iterativa, ogni iterazione consiste nei seguenti passi:
Ma se si considera che la matrice 
è partizionata orizzontalmente, allora ogni iterazione può essere rappresentata come due passi di MapReduce. In questo modo si riesce a minimizzare il trasferimento di dati durante ciascuna delle iterazioni (solo vettori della lunghezza pari al numero di incognite):
È proprio questo approccio che viene usato nell'implementazione della regressione lineare in .
Conclusione
Esistono molti algoritmi per la regressione lineare, ma non tutti possono essere applicati in qualsiasi condizione. Ad esempio, la decomposizione QR è particolarmente adatta per risolvere con precisione piccole quantità di dati. Il metodo del gradiente è facilmente implementabile e consente di trovare rapidamente una soluzione approssimativa. LSQR combina le migliori proprietà dei due algoritmi precedenti, poiché può essere distribuito, converge più rapidamente rispetto al metodo del gradiente e consente un'interruzione anticipata dell'algoritmo, a differenza della decomposizione QR per trovare una soluzione approssimativa.
Fonte: habr.com
