Relazione del Progetto di architetture e progettazione di sistemi di elaborazione

Corso di Laurea Magistrale in Ingegneria Informatica

Relazione del Progetto di Architetture e Progettazione di Sistemi di Elaborazione:

“Polynomial Regression and Stochastic Gradient Descent”

Professori: Studenti:

Anno Accademico 2020/2021

1 DESCRIZIONE DEL PROBLEMA

.

2.PROGETTAZIONE E IMPLEMENTAZIONE

DELL’ALGORITMO IN C

Il progetto è stato diviso in due sezioni:

1. Conversione del dataset

2. Regressione Polinomiale (SGD BATCH, ADAGRAD)

2.1 CONVERSIONE DEL DATASET

Il primo problema affrontato è stato determinare la dimensione di x* (dataset convertito) e del vettore

theta per rendere il programma generico rispetto all’input (aumentando così la robustezza).

Abbiamo scritto il primo metodo di supporto chiamato dimXast() che sfrutta la formula matematica

delle combinazioni con ripetizioni:

La formula per raggiungere il risultato finale viene chiamata g-1 volte se il grado è uguale a g.

Per evitare il problema della dimensione dei fattoriali che restituivano un numero molto elevato che

non sarebbe stato rappresentabile, abbiamo effettuato delle semplificazioni su di essi.

Il metodo come si può vedere in Figura 1 ha come parametri il grado e la dimensione che vengono

passati rispettivamente dall’utente. Figura 1

Una volta ottenuta la dimensione di x* e theta, abbiamo sfruttato il principio di località spaziale visto

a lezione per allocare nella maniera più ottimizzata possibile i nostri dati in memoria.

Sia i dati di x* (dataset convertito) che di theta sono stati allocati rispettivamente in due vettori distinti

da ridurre notevolmente i tempi d’accesso rispetto all’utilizzo di

in modo tale un puntatore di

puntatore. Quindi abbiamo deciso di rappresentare a livello logico secondo Row Major Order che

codifica gli elementi per riga. Il metodo che ha calcolato gli elementi da inserire nel vettore x* si

chiama convert(). Figura 2

un vettore d’appoggio per calcolare le combinazioni risalendo

Il metodo convert() sfrutta tramite gli

indici alle corrette posizioni delle x nelle colonne di ogni riga del dataset ed effettuando poi il prodotto

di quest’ultime. Grazie all’algoritmo implementato siamo riusciti ad evitare le combinazioni ripetute

utilizzando solo un vettore di dimensioni pari al grado. Viene utilizzata una lunghezza del vettore di

appoggio pari al grado corrente.

Il metodo principale convert() utilizza dei metodi di supporto che sono:

• inizializzaGradoUno()

• ripristinaVetZero()

• calcoloXastGradoMaggioreDue()

• tuttiX()

inizializzaGradoUno() permette di calcolare gli elementi di x* relativi al grado 1 che concretamente

si basa su una copia degli elementi per ridurre i tempi di esecuzione dell’algoritmo.

utilizzati durante l’esecuzione

ripristinaVetZero() inizializza a 0 gli elementi del vettore di appoggio

dell’algoritmo per uno specifico grado. Si effettua quando si deve passare al calcolo delle

combinazioni per il grado successivo.

permette di calcolare l’elemento corretto del vettore x* in base al

calcoloXastGradoMaggioreDue()

vettore degli indici v.

permette di impostare i valori utilizzati nel vettore d’appoggio alla prossima combinazione

tuttiX()

di indici quando un indice arriva a dimensione-1.

2.2 SGD BATCH

In questa sezione è stato affrontato il problema principale del progetto che riguarda il calcolo dei theta

ottimi tramite il metodo sgdBatch(). Figura 3

come si può vedere in Figura 3, il metodo riceve tutta la struttura d’input e procede ad eseguire

Da

alcune funzioni. La prima è la fase di inizializzazione dei dati a zero sia per il vettore risultato che

per i theta.

Abbiamo scelto in seguito (Figura 4) di suddividere il codice in due porzioni in base al numero di

righe. Se il numero di righe è multiplo del batch viene eseguita una sezione altrimenti se non è

ne viene eseguita un’altra. Grazie a ciò

multiplo abbiamo evitato alcuni calcoli ripetuti.

Figura 4

Il metodo principale sgdBatch() utilizza dei metodi di supporto che sono:

• prodottoErrorexEtaxXast()

• calcoloPTheta()

prodottoErrorexEtaxXast() ci permette di calcolare e salvare in un vettore risultato i dati parziali

della formula sottostante:

calcoloPTheta() ci permette di aggiornare i valori di Theta ad ogni blocco di batch:

2.3 SGD ADAGRAD prima descritto con l’aggiunta dell’accelerazione

In questa sezione è stato affrontato il problema

adagrad. A differenza del metodo sgdBatch il nuovo metodo sgdAdagrad dovrebbe convergere

all’ottimo più velocemente. Figura 5

Come prima il metodo riceve tutta la struttura d’input e si occupa di inizializzare le strutture di

supporto a 0. Tra queste abbiamo Gj, il vettore dei theta e un vettore risultato.

Anche qui il codice è stato suddiviso in due sezioni in base al numero di righe in input per evitare la

ripetizione di alcune operazioni (Figura 6). Figura 6

Il metodo principale sgdAdagrad() utilizza dei metodi di supporto che sono:

• calcoloParziale()

• calcoloPThetaAdagrad()

calcoloParziale() permette di calcolare il vettore Gj considerando i valori delle operazioni precedenti.

dove verrà cumulato l’intero blocco per

Inoltre, permette di calcolare un vettore di appoggio risultato

ogni batch.

calcoloPThetaAdagrad() ci permette di aggiornare i valori di theta ad ogni blocco di batch: