Machine Learning nell'era dei Big Data: algoritmi scientifici per la modellazione, analisi e creazione di nuova conoscenza dai dati

X

termine noto corrispondente all’intersezione con l’asse delle ordinate con nulle:

X

( ) 14

Machine Learning nell’era dei Big Data. 2016 Matteo Stefanini.

Per calcolare il valore dei parametri θ che meglio adattino i nostri dati in input

presenti nel training set, il dataset iniziale contenente le osservazioni conosciute del

fenomeno di riferimento, con le relative “risposte corrette”, detto anche output

osservato, dobbiamo introdurre il concetto di funzione di costo:

( ) ( )

( ) ( ( ) ) ( ) ( )

dove m è il numero di osservazioni del training set, e con la notazione si

( )

intende l’osservazione iesima di input-output presente nel training set.

La funzione di costo non è altro che la misura media degli errori quadratici tra il nostro

modello ed i reali output conosciuti

h(θ) Y .

Il nostro obiettivo è dunque quello di minimizzare , e così facendo ci

( )

riconduciamo esattamente al caso statistico noto del metodo dei minimi quadrati.

Nel minimizzare la funzione per ricavare i valori dei parametri risulta molto comodo

J

e affidabile l’implementazione del gradiente discendente, anche detto LMS “least

mean square” un algoritmo adattivo ed iterativo tra i più diffusi grazie alla sua

semplicità e robustezza, specialmente adatto nel caso di grandi moli di dati o grande

numero di variabili ingresso. Il principio di base è la minimizzazione dell'errore

quadratico medio tramite successive iterazioni. L’algoritmo parte da valori iniziali

casuali e ripetutamente compie il seguente aggiornamento:

( )

Aggiornamento effettuato simultaneamente per tutti i valori j = 0,…,n.

Il termine qui rappresenta il “learning rate” cioè un parametro per impostare la

α

velocità di convergenza dell’algoritmo, valori bassi corrispondono ad un avanzamento

lento, valori troppo alti rischiano invece di provocare divergenza.

Dopo una serie di calcoli per lo svolgimento della derivata parziale si può giungere

alla cosiddetta formula Widrow-Hoff learning rule [Web 2], secondo cui gli

aggiornamenti avvengono nel seguente modo facilmente implementabile:

( ) ( )

( ( ) )

( )

( ) ( )

( ( ) )

L’algoritmo appena mostrato è chiamato più propriamente “Batch Gradient Descent”

poiché utilizza l’intero Training Set per calcolare ad ogni iterazione l’aggiornamento a

cui sottoporre ogni parametro. Come abbiamo constatato successivamente, non sempre

questa è la soluzione migliore, soprattutto nel caso in cui il training set sia di grandi

15

Machine Learning nell’era dei Big Data. 2016 Matteo Stefanini.

dimensioni, andando a gravare notevolmente sulle prestazioni della nostra

implementazione. E’ per questo che sono state introdotte varianti chiamate “stochastic

gradient descent” e “mini-batch gradient descent” che ci permettono di velocizzare le

operazioni e raggiungere euristicamente un punto accettabile molto più velocemente.

Il gradiente discendente non è l’unico metodo per minimizzare , ma è sicuramente il

J

più utile quando si parla di big data e generalmente grande numero di variabili.

Occorre comunque citare anche la tecnica cosiddetta “Normal Equation” che

rappresenta la risoluzione ottima del problema dei minimi quadrati attraverso la

risoluzione matematica classica delle derivate parziali, il cui risultato finale è :

( )

nella quale la matrice è chiamata “Moore-Penrose pseudoinverse”

( )

[Web 3].

Questa equazione calcola i valori di ottimi che minimizzano i residui al quadrato, ma

θ

risulta notevolmente onerosa in termini computazionali, dell’ordine di O( ) con n

numero di variabili, ed è perciò sconsigliata nei problemi con più di 1.000-10.000

variabili in ingresso, nonostante le moderne potenze di calcolo.

Ciò ci consente finalmente di avere tutto il necessario per implementare in pratica un

algoritmo di regressione lineare con gradiente discendente, eseguirne il training ed

effettuare le successive predizioni con nuovi dati in ingresso arbitrari.

L’algoritmo di regressione lineare con gradiente discendente è stato sperimentato su

MATLAB utilizzando un dataset open source scaricato da [MLStanford 2016].

Per poter implementare e dimostrare l’efficacia della regressione lineare ad una

variabile è stato preso in considerazione un dataset contenente le coppie di valori con

popolazione di una città e profitto associato ad un ristorante in quella città della stessa

catena. Lo scopo dell’implementazione è “prevedere” il profitto di un nuovo ristorante

data la popolazione di una nuova città inserita, dando la possibilità ad un ipotetico

manager della catena alberghiera di prendere decisioni economiche tenendo conto di

questo fattore.

Logicamente si tratta di un esempio banale ed esemplificativo, nella realtà qualsiasi

manager di buon senso prenderebbe decisioni economiche di questo tipo tenendo in

considerazione molte più variabili e modelli più complessi.

In Figura 3 di seguito è mostrato il training set. 16

Machine Learning nell’era dei Big Data. 2016 Matteo Stefanini.

Figura 3 - Training Set per Regressione lineare univariata con Popolazione X e Profitto Y.

Segue l’implementazione dell’algoritmo di regressione lineare con gradiente

discendente sviluppato in ambiente e linguaggio MATLAB.

%% FILE MAIN: LinearRegression.m

%% Inizializzazione:

clear ; close all; clc

%% ======================= Grafici =======================

fprintf('Display dei dati iniziali ...\n')

data = load('data1.txt');

X = data(:, 1); y = data(:, 2);

m = length(y); % numero delle osservazioni del training set

% Grafico dati:

plotData(X, y);

fprintf('Programma in pausa. Premere invio per continuare.\n');

pause;

%% =================== Gradient descent ===================

fprintf('Esecuzione Gradient Descent ...\n')

X = [ones(m, 1), data(:,1)];

theta = zeros(2, 1); % inizializzazione paramentri theta

% Gradient descent settings:

iterations = 1500;

alpha = 0.01;

% Calcola e visualizza costo iniziale

computeCost(X, y, theta)

% esecuzione gradient descent

theta = gradientDescent(X, y, theta, alpha, iterations);

% visualizza theta

fprintf('Theta calcolati dal gradient descent: ');

fprintf('%f %f \n', theta(1), theta(2));

% Disegna la linea di regressione:

hold on; % mantieni grafico precedente sotto

plot(X(:,2), X*theta, '-')

legend('Training data', 'Linear regression')

hold off % Non sovrapporre nessun altro grafico su questa figura

% Predizione valori profitto per popolazioni con 35k e 70k:

predict1 = [1, 5] *theta; 17

Machine Learning nell’era dei Big Data. 2016 Matteo Stefanini.

fprintf('Con popolazione di 50 mila abitanti prevediamo un profitto di

%f\n',...

predict1*10000);

predict2 = [1, 9] * theta;

fprintf('Con popolazione di 90 mila abitanti prevediamo un profitto di

%f\n',...

predict2*10000);

fprintf('Programma in pausa. Premere invio per continuare.\n');

pause;

%% ============= Visualizzazione J(theta_0, theta_1) =============

fprintf('Visualizzazione J(theta_0, theta_1) ...\n')

% Griglia di valori equidistanziati dove andremo a calcolare J

theta0_v = linspace(-10, 10, 100);

theta1_v = linspace(-1, 4, 100);

% inizializzazione J_vals to ad una matrice di zeri

J_v = zeros(length(theta0_v), length(theta1_v));

% Compilazione J_vals

for i = 1:length(theta0_v)

for j = 1:length(theta1_v)

t = [theta0_v(i); theta1_v(j)];

J_v(i,j) = computeCost(X, y, t);

end

end

% Eseguiamo la trasposta di J per poter eseguire il comando surf e stampare

% il grafico senza assi invertiti

J_v = J_v';

% Grafico superfice parametrica di J in 3D

figure;

surf(theta0_v, theta1_v, J_v)

xlabel('\theta_0'); ylabel('\theta_1');

% Grafico curve di livello

figure;

% Visualizzare J_v con 15 linee di contorno spaziate logaritmicamente tra

0.01 e 100

contour(theta0_v, theta1_v, J_v, logspace(-2, 3, 20))

xlabel('\theta_0'); ylabel('\theta_1');

hold on;

plot(theta(1), theta(2), 'rx', 'MarkerSize', 10, 'LineWidth', 2);

% FILE gradientDescent.m

function [theta, J_history] = gradientDescent(X, y, theta, alpha,

num_iters)

% Inizializzazione di alcuni valori utili:

m = length(y); % numero di training examples

J_history = zeros(num_iters, 1);

for iter = 1:num_iters

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

J_history(iter) = computeCost(X, y, theta);

end

end

% FILE computeCost.m

function J = computeCost(X, y, theta)

% Inizializzazione di alcuni valori utili:

m = length(y); % numero di trainig examples

J = (sum((X*theta - y).^2))/(2*m);

end 18

Machine Learning nell’era dei Big Data. 2016 Matteo Stefanini.

I risultati dell’esecuzione del programma sono i seguenti mostrati in Figura 4, 5 e 6:

Figura 4 - Grafico regressione lineare calcolata sul training set.

Figura 5 - Linee di contorno della funzione di costo J con identificazione punto di minimo. 19

Machine Learning nell’era dei Big Data. 2016 Matteo Stefanini.

Figura 6 - Rappresentazione grafica della funzione di costo J in funzione dei parametri e .

Una volta calcolati i parametri trainando il nostro modello abbiamo ottenuto una

θ

linea di regressione visibile in Figura 4 che ci permette di generalizzare una previsione

per altri valori di popolazione.

Ad esempio abbiamo ipotizzato di prevedere i profitti di due nuovi ristoranti, in una

città rispettivamente con 50 mila e 90 mila abitanti e i risultati sono i seguenti:

Theta calcolati dal gradient descent: -3.630291 1.166362.

Con popolazione di 50 mila abitanti prevediamo un profitto di $ 22015,20.

Con popolazione di 90 mila abitanti prevediamo un profitto di $ 68669,69.

Il campo di applicazione della regressione lineare può essere esteso a molti tipi di

problemi, dove i dati possono avere un andamento non lineare oppure il modello

presentare più di un regressore, o variabile indipendente in ingresso.

Nella realtà infatti si assiste molto più frequentemente a problemi che hanno molte

variabili e strutture dati riconducibili a forme non lineari, ma è facilmente dimostrabile

che tramite alcune modifiche ed accorgimenti al modello base appena presentato, è

possibile implementare con relativa facilità queste varianti.

Nel caso di una regressione multivariata ciò che cambia sono il numero di variabili in

ingresso e cons