Fonte:
La regressione lineare è uno degli algoritmi di base per molte aree legate all'analisi dei dati. La ragione di ciò è ovvia. Si tratta di un algoritmo molto semplice e comprensibile, che ha contribuito al suo utilizzo diffuso per molte decine, se non centinaia, di anni. L'idea è di assumere una dipendenza lineare di una variabile da un insieme di altre variabili e quindi provare a ripristinare questa dipendenza.
Ma questo articolo non tratta dell’utilizzo della regressione lineare per risolvere problemi pratici. Qui considereremo le caratteristiche interessanti dell'implementazione degli algoritmi distribuiti per il suo ripristino, che abbiamo riscontrato durante la scrittura di un modulo di machine learning . Un po' di matematica di base, apprendimento automatico e calcolo distribuito possono aiutarti a capire come eseguire la regressione lineare anche quando i tuoi dati sono distribuiti su migliaia di nodi.
Di cosa stai parlando?
Siamo di fronte al compito di ripristinare la dipendenza lineare. Come dati di input viene fornito un insieme di vettori di variabili apparentemente indipendenti, a ciascuno dei quali è associato un determinato valore della variabile dipendente. Questi dati possono essere rappresentati sotto forma di due matrici:
Ora, poiché si assume la dipendenza, e per di più lineare, scriveremo la nostra ipotesi sotto forma di un prodotto di matrici (per semplificare la registrazione, qui e sotto si assume che il termine libero dell'equazione sia nascosto dietro e l'ultima colonna della matrice contiene unità):
Sembra molto simile a un sistema di equazioni lineari, non è vero? Sembra, ma molto probabilmente non ci saranno soluzioni a un simile sistema di equazioni. La ragione di ciò è il rumore, presente in quasi tutti i dati reali. Un'altra ragione potrebbe essere la mancanza di dipendenza lineare in quanto tale, che può essere combattuta introducendo variabili aggiuntive che dipendano in modo non lineare da quelle originali. Considera il seguente esempio:
Fonte:
Questo è un semplice esempio di regressione lineare che mostra la relazione di una variabile (lungo l'asse ) da un'altra variabile (lungo l'asse ). Affinché il sistema di equazioni lineari corrispondente a questo esempio abbia una soluzione, tutti i punti devono giacere esattamente sulla stessa retta. Ma non è vero. Ma non giacciono sulla stessa linea retta proprio a causa del rumore (o perché l'ipotesi di una relazione lineare era errata). Pertanto, per ripristinare una relazione lineare dai dati reali, è solitamente necessario introdurre un ulteriore presupposto: i dati di input contengono rumore e questo rumore ha . È possibile fare ipotesi su altri tipi di distribuzione del rumore, ma nella stragrande maggioranza dei casi viene presa in considerazione la distribuzione normale, che verrà discussa ulteriormente.
Metodo di massima verosimiglianza
Quindi, abbiamo ipotizzato la presenza di rumore casuale distribuito normalmente. Cosa fare in una situazione del genere? Per questo caso in matematica esiste ed è ampiamente utilizzato . Insomma, la sua essenza sta nella scelta e la sua successiva massimizzazione.
Torniamo a ripristinare una relazione lineare dai dati con rumore normale. Si noti che la relazione lineare assunta è l'aspettativa matematica distribuzione normale esistente. Allo stesso tempo, la probabilità che assume un valore o un altro, soggetto alla presenza di osservabili , assomiglia a questo:
Sostituiamo ora invece и le variabili di cui abbiamo bisogno:
Non resta che trovare il vettore , in cui questa probabilità è massima. Per massimizzare tale funzione, conviene prima prenderne un logaritmo (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 si chiama metodo . Spesso tutte le considerazioni di cui sopra vengono omesse e viene semplicemente utilizzato questo metodo.
Scomposizione QR
Il minimo della funzione precedente può essere trovato trovando il punto in cui il gradiente di questa funzione è zero. E il gradiente verrà scritto come segue:
è un metodo matriciale per risolvere il problema di minimizzazione utilizzato nel metodo dei minimi quadrati. A questo proposito riscriviamo l’equazione in forma matriciale:
Quindi scomponiamo la matrice alle matrici и ed eseguire una serie di trasformazioni (qui non verrà preso in considerazione l'algoritmo di scomposizione QR in sé, ma solo il suo utilizzo in relazione all'attività da svolgere):
matrice è ortogonale. Questo ci permette di liberarci del lavoro :
E se sostituisci su , allora funzionerà . Considerando che è una matrice triangolare superiore, assomiglia a questa:
Questo può essere risolto utilizzando il metodo di sostituzione. Elemento si trova come , elemento precedente si trova come e così via.
Vale la pena notare qui che la complessità dell'algoritmo risultante dovuta all'uso della scomposizione QR è uguale a . Inoltre, nonostante il fatto che l'operazione di moltiplicazione di matrici sia ben parallelizzata, non è possibile scrivere una versione distribuita efficace di questo algoritmo.
Discesa gradiente
Quando si parla di minimizzare una funzione, vale sempre la pena ricordare il metodo della discesa del gradiente (stocastica). Questo è un metodo di minimizzazione semplice ed efficace basato sul calcolo iterativo del gradiente di una funzione in un punto e quindi sullo spostamento nella direzione opposta al gradiente. Ciascuno di questi passaggi avvicina la soluzione al minimo. Il gradiente sembra sempre lo stesso:
Questo metodo è anche ben parallelizzato e distribuito grazie alle proprietà lineari dell'operatore gradiente. Si noti che nella formula sopra, sotto il segno di somma ci sono termini indipendenti. In altre parole, possiamo calcolare il gradiente indipendentemente per tutti gli indici dal primo al , parallelamente a questo, calcola il gradiente per gli indici con a . Quindi aggiungi i gradienti risultanti. Il risultato dell'addizione sarà lo stesso che se calcolassimo immediatamente il gradiente per gli indici dal primo al . Pertanto, se i dati sono distribuiti su più porzioni di dati, il gradiente può essere calcolato indipendentemente su ciascuna porzione, quindi i risultati di questi calcoli possono essere sommati per ottenere il risultato finale:
Da un punto di vista implementativo, questo si adatta al paradigma . Ad ogni fase della discesa del gradiente, viene inviata un'attività a ciascun nodo dati 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 facilità di implementazione e la possibilità di esecuzione nel paradigma MapReduce, la discesa del gradiente presenta anche degli svantaggi. In particolare, il numero di passaggi necessari per raggiungere la convergenza è significativamente più elevato rispetto ad altri metodi più specializzati.
LQSR
è un altro metodo per risolvere il problema, adatto sia per ripristinare la regressione lineare che per risolvere sistemi di equazioni lineari. La sua caratteristica principale è quella di combinare i vantaggi dei metodi a matrice e di un approccio iterativo. Le implementazioni di questo metodo possono essere trovate in entrambe le biblioteche e in . Una descrizione di questo metodo non verrà fornita qui (può essere trovata nell'articolo ). Verrà invece dimostrato un approccio per adattare LSQR all'esecuzione in un ambiente distribuito.
Il metodo LSQR si basa su . Questa è una procedura iterativa, ogni iterazione consiste dei seguenti passaggi:
Ma se assumiamo che la matrice è partizionato orizzontalmente, ciascuna iterazione può essere rappresentata come due passaggi MapReduce. In questo modo è possibile minimizzare i trasferimenti di dati durante ogni iterazione (solo vettori con lunghezza pari al numero di incognite):
È questo approccio che viene utilizzato quando si implementa la regressione lineare in .
conclusione
Esistono molti algoritmi di recupero della regressione lineare, ma non tutti possono essere applicati in tutte le condizioni. Pertanto la scomposizione QR è eccellente per una soluzione accurata su piccoli set di dati. La discesa del gradiente è semplice da implementare e consente di trovare rapidamente una soluzione approssimativa. E LSQR combina le migliori proprietà dei due algoritmi precedenti, poiché può essere distribuito, converge più velocemente rispetto alla discesa del gradiente e consente anche l'arresto anticipato dell'algoritmo, a differenza della decomposizione QR, per trovare una soluzione approssimativa.
Fonte: habr.com