Nei post precedenti abbiamo visto come prevedere un valore continuo utilizzando una funzione lineare, nonché un metodo per misurare l’errore partendo da una matrice di dati di test e da un insieme di valori ipotetici theta.

In questo articolo descriveremo una funzione in grado di far convergere il vettore theta verso i suoi valori ottimali (o, in alternativa, verso un minimo locale), nota come discesa del gradiente.

Per semplificare il concetto, supponiamo di avere un vettore $\theta$ a sole due dimensioni (i valori di pendenza e intercetta di una semplice retta). Tracciando il grafico di $\theta_0$, $\theta_1$ e il risultato della funzione di costo, si otterrà una figura simile a questa:

Dato un qualsiasi punto di partenza casuale $\langle\theta_0,\theta_1\rangle$, calcolando la derivata parziale della funzione si otterrà una direzione che si allontana dal minimo locale; di conseguenza, è possibile compiere un passo ($\alpha$) in direzione opposta per avvicinarsi all’obiettivo. In termini matematici, la discesa del gradiente si esprime in questo modo:

$\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta_0, \theta_1)$

Il passo $\alpha$ che si compie a ogni iterazione verso il minimo locale prende il nome di learning rate (o a volte step size). Per il momento, supponiamo di utilizzare un valore fisso, e di fare altrettanto per il numero di iterazioni necessarie a raggiungere il minimo locale.

Derivando questa formula, il risultato è il seguente:

$$\begin{align*} \text{repeat until convergence: } \lbrace & \\ \theta_0 := & \theta_0 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}(h_\theta(x_{i}) - y_{i}) \\ \theta_1 := & \theta_1 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}\left((h_\theta(x_{i}) - y_{i}) x_{i}\right) \\ \rbrace & \end{align*}$$

oppure, in forma più generale (assumendo che $x_0^{(i)}=1$):

$$\begin{align*} & \text{repeat until convergence:} \; \lbrace \\ \; & \theta_j := \theta_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)} \; & \text{for j := 0..n} \\ & \rbrace \end{align*}$$

Tuttavia, ciò che si desidera implementare è una versione vettorizzata di tale formula, ovvero:

$\theta := \theta - \frac{\alpha}{m} X^{T} (X\theta - \vec{y})$

Ancora una volta, grazie all’uso dei vettori, il risultato è molto più leggibile e semplice da implementare. Possiamo finalmente passare all’effettiva implementazione in Go:

// m = Number of Training Examples
// n = Number of Features
m, n := X.Dims()
h := mat64.NewVector(m, nil)
new_theta := mat64.NewVector(n, nil)
partials := mat64.NewVector(n, nil)

for i := 0; i < numIters; i++ {
        h.MulVec(X, new_theta)
        for el := 0; el < m; el++ {
            val := (h.At(el, 0) - y.At(el, 0)) / float64(m)
            h.SetVec(el, val)
        }
        partials.MulVec(X.T(), h)

        // Update theta values
        for el := 0; el < n; el++ {
            new_val := new_theta.At(el, 0) - (alpha * partials.At(el, 0))
            new_theta.SetVec(el, new_val)
        }
}

La variabile h è un Dense Matrix Vector, mentre numIters è una costante di tipo int. L’implementazione completa è disponibile qui, mentre i relativi test si trovano qui.

Un’ottima spiegazione visiva è offerta nel seguente video del professor Alexander Ihler:

Aggiornamento (6 febbraio 2016): il codice è stato corretto, per cui ora h e new_theta sono di tipo Vector anziché DenseMatrix.