Apprendimento automatico - Regressione lineare con discesa gradiente batch

Question

Sto cercando di implementare la discesa gradiente batch su un set di dati con una singola funzione e più esempi di addestramento (m).

Quando provo a utilizzare l'equazione normale, ottengo la risposta corretta ma quella sbagliata con questo codice sotto cui esegue la discesa gradiente batch in MATLAB.

function [theta] = gradientDescent(X, y, theta, alpha, iterations) 
     m = length(y); 
     delta=zeros(2,1); 
     for iter =1:1:iterations 
      for i=1:1:m 
       delta(1,1)= delta(1,1)+(X(i,:)*theta - y(i,1)) ; 
       delta(2,1)=delta(2,1)+ ((X(i,:)*theta - y(i,1))*X(i,2)) ; 
      end 
      theta= theta-(delta*(alpha/m)); 
     computeCost(X,y,theta) 
     end 
end 

y è il vettore dei valori obiettivo, X è una matrice con la prima colonna completo di pile e seconde colonne di valori (variabile).

ho implementato utilizzando questo vettorizzazione, cioè

theta = theta - (alpha/m)*delta 

... dove delta è un elemento 2 vettore colonna inizializzato a zero.

La funzione di costo J(Theta) è 1/(2m)*(sum from i=1 to m [(h(theta)-y)^2]).

Answer 1

L'errore è molto semplice. La dichiarazione delta deve trovarsi all'interno del primo ciclo for. Ogni volta che accumuli le differenze ponderate tra il campione di allenamento e l'output, dovresti iniziare ad accumulare dall'inizio.

Evitando di fare questo, quello che stai facendo sta accumulando gli errori dalla precedente iterazione che prende l'errore della versione precedente appreso theta in considerazione che non è corretto. È necessario inserire all'inizio del primo ciclo for.

Inoltre, sembra che ci sia una chiamata esterna computeCost. Suppongo che questo calcoli la funzione di costo ad ogni iterazione dato i parametri attuali, e quindi creerò un nuovo array di output chiamato cost che mostra questo a ogni iterazione. Sono anche andando a chiamare questa funzione e assegnare agli elementi corrispondenti in questo array:

function [theta, costs] = gradientDescent(X, y, theta, alpha, iterations) 
    m = length(y); 
    costs = zeros(m,1); %// New 
% delta=zeros(2,1); %// Remove 
    for iter =1:1:iterations 
    delta=zeros(2,1); %// Place here 
    for i=1:1:m 
     delta(1,1)= delta(1,1)+(X(i,:)*theta - y(i,1)) ; 
     delta(2,1)=delta(2,1)+ ((X(i,:)*theta - y(i,1))*X(i,2)) ; 
    end 
    theta= theta-(delta*(alpha/m)); 
    costs(iter) = computeCost(X,y,theta); %// New 
end 
end 

---

Una nota sulla corretta vettorizzazione

FWIW, non ritengo questa implementazione completamente vettorializzare . È possibile eliminare il secondo ciclo for utilizzando le operazioni vettorializzate. Prima di farlo, lascia che ti spieghi un po 'di teoria, quindi siamo sulla stessa pagina. Qui stai usando la discesa del gradiente in termini di regressione lineare. Noi vogliamo ricercare le migliori parametri theta che sono i nostri coefficienti di regressione lineare che cercano di minimizzare questo funzione di costo:

m corrisponde al numero di campioni di formazione che abbiamo a disposizione e x^{i} corrisponde al I ^esimo esempio di allenamento. y^{i} corrisponde al valore di verità del terreno che abbiamo associato al campione di allenamento i ^o.h è la nostra ipotesi, e si è dato come:

Si noti che nel contesto di regressione lineare in 2D, abbiamo solo due valori in theta vogliamo calcolare - il termine intercetta e la pendenza.

Possiamo ridurre al minimo la funzione di costo J per determinare i migliori coefficienti di regressione che possono darci le migliori previsioni che riducono al minimo l'errore del set di allenamento. In particolare, iniziando con alcuni parametri iniziali theta ... di solito un vettore di zeri, iteriamo su iterazioni da 1 fino a quante ne pensiamo, e ad ogni iterazione aggiorniamo i nostri parametri theta con questa relazione:

Per ciascun parametro che si desidera aggiornare, è necessario determinare il gradiente della funzione di costo rispetto a ciascuna variabile e valutare quale è allo stato corrente di theta. Se si lavora questo fuori usando Calculus, otteniamo:

Se siete poco chiaro di come questa derivazione è accaduto, allora vi rimando a questo bel post Matematica Stack Exchange che parla:

https://math.stackexchange.com/questions/70728/partial-derivative-in-gradient-descent-for-two-variables

Ora ... come possiamo applicare questo al nostro problema attuale? In particolare, è possibile calcolare le voci di delta analizzando abbastanza facilmente tutti i campioni insieme in una volta. Quello che voglio dire è che si può solo fare questo:

function [theta, costs] = gradientDescent(X, y, theta, alpha, iterations) 
    m = length(y); 
    costs = zeros(m,1); 
    for iter = 1 : iterations 
     delta1 = theta(1) - (alpha/m)*(sum((theta(1)*X(:,1) + theta(2)*X(:,2) - y).*X(:,1))); 
     delta2 = theta(2) - (alpha/m)*(sum((theta(1)*X(:,1) + theta(2)*X(:,2) - y).*X(:,2))); 

     theta = [delta1; delta2]; 
     costs(iter) = computeCost(X,y,theta); 
    end 
end 

Le operazioni su delta(1) e delta(2) possono essere completamente vettorizzati in una singola istruzione per entrambi. Cosa si sta facendo theta^{T}*X^{i} per ogni campione i da 1, 2, ..., m. È possibile posizionarlo comodamente in un'unica dichiarazione sum.

Possiamo andare ancora oltre e sostituirlo con operazioni puramente a matrice. Prima di tutto, ciò che puoi fare è calcolare theta^{T}*X^{i} per ogni campione di input X^{i} molto rapidamente usando la moltiplicazione della matrice. Supponiamo che se:

Qui, X è nostra matrice che compone di m righe corrispondenti al m campioni di training e n colonne corrispondenti ai n caratteristiche. Allo stesso modo, theta è il nostro vettore di peso imparato dalla discesa del gradiente con le funzioni n+1 che rappresentano il termine di intercettazione.

Se si calcola X*theta, otteniamo:

Come si può vedere qui, abbiamo calcolato l'ipotesi per ogni campione e hanno posto ciascuno in un vettore. Ogni elemento di questo vettore è l'ipotesi per il campione di allenamento i .Ora, ricordare ciò che il termine gradiente di ogni parametro è in discesa del gradiente:

Vogliamo implementare questo tutto in una volta per tutti i parametri nel vostro vettore imparato, e così mettere questo in un vettore ci dà:

Infine:

Pertanto, sappiamo che y è già un vettore di lunghezza m, e in modo che possiamo molto compatto calcolare discesa del gradiente ad ogni iterazione da:

theta = theta - (alpha/m)*X'*(X*theta - y); 

.... in modo che il codice è ora solo:

function [theta, costs] = gradientDescent(X, y, theta, alpha, iterations) 
    m = length(y); 
    costs = zeros(m, 1); 
    for iter = 1 : iterations 
     theta = theta - (alpha/m)*X'*(X*theta - y); 
     costs(iter) = computeCost(X,y,theta); 
    end 
end