Articoli

ALGEBRA LINEARE PER TUTTI [Parte 2]

 

Autore: Paolo Caressa

 

 

Punti, vettori e loro algebra

Abbiamo fin qui parlato di punti come la totalità dei punti del piano che si identificano in modo biunivoco con la totalità di tutte le coppie possibili di numeri reali.

Per quanto riguarda il machine Learning, siamo interessati a insiemi finiti di punti, in quanto vogliamo rappresentare particolari oggetti da classificare o fenomeni da correlare come punti in uno spazio cartesiano. Per trovare una regolarità o un “pattern” in questi punti, spesso ci interessa considerare rette, piani oltre che di figure geometriche più complesse come le coniche nel piano o le quadriche nello spazio.

Abbiamo visto prima, con un esempio, che alcune figure geometriche possono essere rappresentate da singole o da sistemi di equazioni.

Limitiamoci al caso delle rette e dei piani per capire in generale come li si rappresenta, dato che spesso queste rappresentazioni sono utilizzate nel machine learning.

 

Una retta è intuitivamente un insieme allineato di punti: uno degli assiomi di Euclide afferma che per due punti passa una sola retta, cioè che per determinare univocamente una retta basta indicarne due punti distinti.

Per capire come questo si possa fare nel piano cartesiano, consideriamo due punti distinti P e Q, di coordinate P=(x1,y1) e Q=(x2,y2).

Definiamo il vettore che va da P a Q come la coppia di numeri

Cattura 6

Cioè un vettore è per definizione una differenza di punti, dove con il termine differenza intendiamo la differenza fra le componenti che hanno lo stesso indice.

Dal punto di vista informatico possiamo pensarla in questo modo: un punto è un array (o lista) con due elementi che sono numeri. Normalmente un array A = [x,y] si indicizza a partire da 0, cioè A[0] = x e A[1] = y. Allora, se A e B sono array, il vettore \overline{AB}  si può rappresentare con l’array [B[0] – A[0], B[1] – A[1]].

Resta da capire perché chiamiamo “vettore” una differenza di punti: perché è un oggetto dotato di direzione, verso e intensità, come i vettori della fisica.

La direzione è semplicemente la retta che passa per P e Q; il verso è quello che va da P verso Q (il vettore opposto sarebbe \overline{PQ}  che va da Q verso P: quali sono le sue componenti?)

 

L’intensità è la distanza fra i punti P e Q. Pertanto un vettore determina una retta, e su di essa una direzione: naturalmente esistono infiniti vettori che determinano la stessa retta.

Per esempio la retta che passa per i punti  P= (0,1)  e Q= (0,-2)  è individuata dal vettore \overline{PQ}= (-2,2)   , ma anche dal vettore (-1,1)  che ha stessa direzione e verso ma intensità diversa.

In generale, per ogni numero  (-a,a) a non nullo  rappresenta questa retta. Diciamo che due vettori sono paralleli se sono l’uno multiplo dell’altro per un fattore di scala non nullo.

In effetti, un altro modo di determinare una retta è individuarne un punto P  e un vettore \overline{v}  in modo da esprimere tutti i punti della retta come traslati per i vettori paralleli a \overline{v}

 X= P+ \overline{av}

Questa si chiama l’equazione parametrica della retta, perché esprime il generico punto  della retta per mezzo di un parametro  che varia in tutti i numeri reali.

Si noti che abbiamo usato l’operazione di somma fra un punto e un vettore, definita in modo ovvio: se  P= (X,Y)  e  v= \overline{RS} allora   P + \overline{RS} \left ( x+w-a,y+z -b\right )  , supponendo che le coordinate dei punti R e  S siano  R=(a,b)  e S=(w,z) . Cioè sommiamo le coordinate del punto e le componenti del vettore per ottenere un nuovo punto.

Quando sommiamo un vettore a un punto diciamo anche che applichiamo il vettore in quel punto.

 

I vettori, oltre a consentire di definire le rette ed in dimensioni più alte piani ed iperpiani possiamo notare che:

  1. I vettori possono essere sommati e fra loro ottenendo altri vettori:

\overline{PQ} + \overline{RS}= Q-P+S-R

Notiamo che allora  \overline{PQ} + \overline{QP}=0  (il vettore nullo) e  \overline{QP} è il vettore opposto  \overline{PQ}.

Inoltre, questa operazione di somma soddisfa le usuali proprietà commutativa e associativa

2. I vettori possono essere moltiplicati per un numero ottenendo altri vettori: Inoltre questa operazione di prodotto soddisfa le usuali proprietà commutativa, associativa e distributiva.In particolare il vettore nullo  \overline{0} è ottenuto moltiplicando per zero ed il vettore  opposto di un vettore dato  \overline{v}, cioè quel vettore  \overline{w} tale che  \overline{v} + \overline{w}=0  , è ottenuto   \overline{v}  moltiplicando per  -1.

Inoltre questa operazione di prodotto soddisfa le usuali proprietà commutativa, associativa e distributiva.

 

Con il termine spazio vettoriale si intende un insieme di elementi con due operazioni, di somma fra gli elementi e di moltiplicazione di un elemento per un numero, che soddisfi le stesse proprietà delle operazioni fra i vettori del piano.

vettore in un piano

Figura 3. Il vettore ottenuto come somma  di due vettori del piano si costruisce prendendo la diagonale del  parallelogramma individuato dai due vettori se applicati in uno stesso punto.

In realtà, nel machine learning si utilizzano invariabilmente spazi vettoriali di dimensione finita i cui vettori sono espressi in coordinate, e in questo caso i vettori sono differenze di punti proprio come nell’esempio che stiamo discutendo.

In effetti un elemento di confusione per i principianti è che sia i punti che i vettori dello spazio cartesiano sono rappresentati come coppie di numeri.

Vogliamo ricordare che, anche se si rappresentano allo stesso modo, sono oggetti concettualmente distinti. Un punto individua un singolo punto dello spazio, un vettore individua uno spostamento lungo una direzione, verso e di una certa lunghezza dove si può far corrispondere un punto a un vettore e viceversa nel modo seguente:

al punto P possiamo far corrispondere il vettore   \overline{OP}  che va dall’origine del piano cartesiano al punto P; se invece  \overline{v}   è un vettore, possiamo associargli il punto   0+\overline{v} .

 

Questa distinzione fra punti e vettori è spesso trascurata ma è importante intanto per distinguere concetti apparentemente identici, e poi perché aiuta a interpretare le applicazioni della teoria: per esempio nella seguente figura sono rappresentate, secondo un certo algoritmo di machine learning, alcune parole di un corpus di documenti in inglese con i punti del piano cartesiano:

 

italy

 

Come si vede i punti rappresentano parole.

I vettori cosa rappresentano in questo caso?

Prendiamo il vettore che va da “pizza” a “italy” e applichiamolo a “sushi”: otteniamo indicativamente “japan”. Ne deduciamo che quel vettore rappresenta la risposta a una domanda, cioè “dato un piatto tipico qual è la sua nazione?”.

In questo caso è chiaro che punti e vettori rappresentano concetti distinti.

 

Lunghezza e angolo fra vettori, similarità del coseno

Per definire la lunghezza di un vettore introduciamo una notazione molto usata: il prodotto scalare (o dot-product).

Sia  \overline{v} =(v_1,v_2) e  \overline{v} = (v_1,w_2) diciamo che la il prodotto scalare di   \overline{v}  e  \overline{w}  è il numero:

ecuacion 1

 

ottenuto come somma dei prodotti delle componenti di pari indice dei due vettori.

In particolare, il prodotto scalare di un vettore per se stesso è, per definizione, il quadrato della sua lunghezza:

ecuacion 2

La lunghezza di un vettore si chiama anche norma: si noti che la formula mostra chiaramente come la norma che abbiamo considerato sia “euclidea”, e il motivo è dato dal fatto che, se scriviamo  come differenza di punti troviamo che

nueva ecuacion 3

La lunghezza di un vettore che abbiamo qui definito è quella che in fisica si chiama la sua intensità: oltre alla lunghezza, possiamo anche definire l’angolo  \theta = \overline{V} \overline{W}  fra due vettori, implicitamente per mezzo della formula :

ecuacion 4

Usando la funzione arcocoseno è possibile calcolare questo angolo a partire dal prodotto scalare dei due vettori e dalle loro lunghezze: il motivo per cui questa formula definisce effettivamente l’angolo fra i vettori è legato alla trigonometria.

Notiamo che   \theta  è un numero compreso fra -1 e 1  tale che:

imagen 3

Dunque, mentre la distanza confronta la similarità fra due punti, che sono tanto più simili quanto più la loro distanza è prossima a zero, il coseno misura la similarità fra due vettori, nel senso che più è prossimo a 1 in valore assoluto e più i vettori determinano la stessa retta.

Questa misura è spesso usata in machine learning per classificare oggetti mappati su spazi vettoriali.

Lo spazio cartesiano a N dimensioni

Nel tour de force di geometria cartesiana e vettoriale che abbiamo fin qui seguito, ci siamo limitati al caso della dimensione N = 2 per aiutarci con i disegni e sviluppare i concetti in un ambiente familiare: ma nelle applicazioni abbiamo a che fare con spazi di dimensione anche molto alta.

In questo caso dobbiamo rinunciare all’intuizione, ma in realtà tutte le formule che abbiamo dato e tutti i concetti che abbiamo definito si trasportano “pari pari” al caso di dimensione qualsiasi.

Infatti tutte le formule dipendono da somme e sottrazioni delle coordinate dei punti e delle componenti dei vettori: se queste componenti sono 2 oppure 20.000 non fa una reale differenza. Ancora meglio, tutto questo si implementa in modo molto efficiente su un computer, cui possiamo far digerire punti e vettori in spazi di dimensione altissima senza problemi!

Un concetto dobbiamo tuttavia spiegarlo, quello di iperpiano: nel caso del piano coincide col concetto di retta e nel caso dello spazio ordinario col concetto di piano.

Fissata una dimensione N consideriamo lo spazio cartesiano R^n.

 

Una retta di questo spazio è, come nel caso di dimensione 2, determinata da una coppia di punti o da un punto e da un vettore: l’equazione parametrica è la stessa che nel caso bidimensionale.

Se N > 2 possiamo anche considerare equazioni parametriche del tipo:

ecuacion 5

In questo caso abbiamo due parametri che variano indipendentemente, quindi, a intuito, l’insieme dei punti X che soddisfano questa equazione al variare di a e b nei numeri reali corrisponde alle coppie (a,b) cioè al piano. In altri termini, è un oggetto bidimensionale.

In realtà questo non è sempre vero: per esempio se    \overline{v}= \overline{w} l’equazione parametrica precedente si riduce alla

ecuacion 6

quindi in realtà rappresenta una retta.

Quindi se scriviamo una equazione parametrica con più parametri, la dimensione dell’insieme dei punti descritti da questa equazione dipende dalle relazioni fra i vettori usati per scriverla: nel caso precedente, se i vettori sono paralleli l’equazione rappresenta una retta e non un piano.

Se in generale, in uno spazio di dimensione N, scriviamo una equazione parametrica in N – 1 parametri, abbiamo:

ecuacion 7

Se tutti i vettori che vi figurano sono paralleli, otteniamo ancora una retta! Per assicurarci di avere un oggetto di dimensione N – 1 dobbiamo trovare un analogo della condizione di parallelismo fra due vettori che sia esprimibile per più di due.

 

Diciamo che n vettori :

Cattura 1

sono linearmente indipendenti se l’unico modo per soddisfare l’equazione

ecuacion 8

È che tutti i coefficienti a_1, a_2,a_n   siano nulli! Cioè l’unica soluzione di questa equazione vettoriale deve essere

Cattura2

Ora possiamo definire un iperpiano di dimensione N – 1 in uno spazio cartesiano di dimensione N come l’insieme dei punti definiti dall’equazione parametrica

ecuacion 9

al variare in tutti i modi possibili dei numeri:

Cattura 3

e supponendo che i vettori rappresentanti qui sotto, siano linearmente indipendenti.

Cattura4

Un iperpiano può essere descritto anche da una equazione cartesiana, cioè da una relazione lineare fra le coordinate del generico punto che gli appartiene:

ecuacion 10

dove  b_i non tutti i  sono nulli.

Un modo per determinare questa equazione è notare che la somma di prodotti dei coefficienti e delle coordinate è il prodotto scalare fra il vettore   \overline{b} = (b_1, b_2,..,b_n) e il vettore   \overline{x} = (x_1, x_2,..,x_n) delle coordinate, di modo che possiamo scriverla

Cattura 5

Questo vuol dire che l’iperpiano è formato dai vettori che sono perpendicolari al vettore  che rappresenta la direzione perpendicolare all’iperpiano, quella mancante per colmare tutto lo spazio.

Un iperpiano di dimensione N – 1 in uno spazio di dimensione N separa in due parti lo spazio, esattamente come una retta separa in due il piano e un piano separa in due lo spazio tridimensionale: i punti che appartengono a una delle due parti in cui viene separato lo spazio dall’iperpiano hanno le coordinate che soddisfano la disequazione.

 

ecuacion 13

Mentre i punti le cui coordinate soddisfano la disequazione

ecuacion 14

costituiscono l’altra parte dello spazio delimitata dall’iperpiano.

Questa idea di usare un iperpiano per separare in due parti lo spazio è la separabilità lineare ed è utilizzata negli algoritmi classici di machine learning, come alberi decisionali o le support vector machines.

 

Matrici e loro algebra

Una delle caratteristiche dell’algebra lineare è la facilità e universalità dei suoi metodi numerici: in sostanza basta aver implementato un algoritmo (o una sua variante), cioè l’eliminazione di Gauss, per poter sostanzialmente fare qualsiasi cosa [una introduzione a questo algoritmo si trova per esempio in queste note]. Questi algoritmi sono tipicamente già implementati in tutte le librerie standard di calcolo numerico, per esempio numpy.linalg di Python.

Per chiudere questo tutorial (ormai fin troppo lungo) è opportuno introdurre la nozione chiave che coinvolge tutti questi algoritmi, e che è utile anche in tutti gli sviluppi concettuali dell’algebra lineare: il concetto di matrice.

Una matrice è semplicemente una tabella di numeri: oppure anche definibile come un array bidimensionale. Diciamo quindi che una matrice n×m è una tabella di numeri che denotiamo con due indici, i e j, dove il primo indice individua la riga e il secondo la colonna: all’incrocio della riga i e della colonna j si trova il numero  individuato da questi indici (in matematica gli indici partono da 1 e non da 0 come in informatica)

Quando la scriviamo per esteso, una matrice si rappresenta nel modo tabellare seguente:

ecuacion15

Una matrice in cui n = m si dice matrice quadrata.

Dal punto di vista pratico, una matrice sembra semplicemente un vettore di lunghezza nm i cui elementi sono arrangiati in forma tabellare anziché scritti in sequenza.

Tuttavia questo cambio notazionale è fondamentale per poter usare questi oggetti.

In particolare, le matrici arricchiscono l’algebra dei vettori con una operazione di moltiplicazione vera e propria: prima notiamo che possiamo sommarle e moltiplicarle per un numero ottenendo ancora matrici dello stesso tipo

Catturab6

In altri termini le matrici n×m formano uno spazio vettoriale di dimensione nm.

Ricordiamo che abbiamo detto che un vettore si può moltiplicare per un numero e ottenere ancora un vettore. Ma non sappiamo come moltiplicare un vettore per se stesso e ottenere ancora un vettore: il prodotto scalare di due vettori produce un numero e non un vettore.

Per introdurre una moltiplicazione dobbiamo scrivere i vettori in due modi distinti: vettori riga e vettori colonna. Un vettore riga è una sequenza di numeri, come lo abbiamo scritto fin qui, per esempio (1,2,0).

Un vettore colonna è una sequenza di numeri scritti dall’alto verso il basso, come :

Cattura66

Apparentemente non c’è differenza sostanziale, ma in realtà se interpretiamo un vettore come un particolare tipo di matrice, il vettore riga è una matrice 1×3 mentre il vettore colonna è una matrice 3×1.

Quel che si può fare è in effetti, data una matrice A del tipo n×m e una matrice B del tipo n×r moltiplicare A per B ottenendo una matrice n×r. Il coefficiente di indici i e j della matrice AB è calcolato come la somma seguente:

Cattura 12

Si noti che questo è il prodotto scalare del vettore riga dato dalla riga i-esima di A per il vettore colonna dato dalla colonna j-esima di B: ecco perché il prodotto di matrici di chiama prodotto righe per colonne.

Esempio: moltiplichiamo una matrice 2×3 per una matrice 2×3:

image1

Torniamo ora ai nostri vettori: possiamo moltiplicare il vettore riga per il vettore colonna, e ne risulta una matrice 1×1 vale a dire un numero (il prodotto scalare). Ma possiamo anche moltiplicare il vettore colonna 3×1 per il vettore riga 1×3 ottenendo una matrice 3×3:

catura 12

 

Notiamo quindi che moltiplicando due vettori di uno spazio di dimensione N otteniamo un vettore di uno spazio di un’altra dimensione: 1 oppure N×N.

La matrice identità è la matrice quadrata che contiene zero dappertutto tranne che sulla diagonale dove contiene 1 (gli elementi diagonali di una matrice sono quelli il cui indice di riga è uguale all’indice di colonna: ). Per esempio in dimensione 3 la matrice identità è

ecuacion 16

Come suggerisce il nome, moltiplicando una matrice A per la matrice identità si ottiene ancora A. Inoltre il prodotto di matrici è distributivo rispetto alla somma.

Tuttavia l’algebra delle matrici ha una particolarità: il prodotto non è commutativo, il che vuol dire che AB è diversa da BA (in effetti BA potrebbe non avere senso, se per esempio n m).

Per esempio

ultima ecuacion

 

Un’altra operazione tipica che si effettua è la moltiplicazione di una matrice n×m per un vettore colonna di m componenti: ne risulta un vettore colonna di n componenti.

La GTX 745 e l’installazione di tensorflow – gpu su Windows

Autrice: Eleonora Bernasconi

 

Specifiche della scheda grafica NVIDIA GeForce GTX 745

Specifiche: https://www.geforce.com/hardware/desktop-gpus/geforce-gtx-745-oem/specifications

CUDA Cores: 384

Base Clock (MHz): 1033

Memory Clock: 1.8 Gbps

Standard Memory Config: 4 GB

Memory Interface: DDR3

Memory Bandwidth (GB/sec): 28.8

 

Figura 01 – nvidia-smi per il monitoraggio della GPU

Apri il Command Prompt ed inserisci:

cd C:\Program Files\NVIDIA Corporation\NVSMI

nvidia-smi

N.B.La percentuale di utilizzo della GPU oscilla tra il 92% e il 94%, nel Task Manager di Windows si mantiene sul 70%.

Installazione tensorflow con GPU per Windows 10

Requisiti

Python 3.5

Nvidia CUDA GPU. Vedi se la GPU è compatibile con CUDA.

Settaggio della scheda Nvidia GPU

Installa Cuda Toolkit 8.0 e cuDNN v5.1.

Download ed installazione di CUDA Toolkit

Toolkit 8.0 https://developer.nvidia.com/cuda-downloads

Esempio directory di installazione: C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v8.0

Download ed installazione di cuDNN

Installa cuDNN versione 5.1 per Windows 10: https://developer.nvidia.com/cudnn

Estrai i file cuDNN ed inseriscili nella directory Toolkit.

Variabili d’ambiente

Assicurati dopo aver installato CUDA toolkit, che CUDA_HOME sia impostata nelle variabili d’ambiente, altrimenti aggiungile manualmente.

Figura 02 – Variabili d’ambiente CUDA_HOME parte 01

 

Figura 03 – Variabili d’ambiente CUDA_HOME parte 02

Installa Anaconda

Download : https://www.anaconda.com/download/

Crea un nuovo ambiente con il nome tensorflow-gpu e la versione di python 3.5.2

conda create -n tensorflow-gpu python=3.5.2

N.B. Nel caso in cui ci si ritrovasse con versioni incompatibili tra di loro, basta attivare questi comandi per risolvere il problema:

conda install -c conda-forge tensorflow-gpu

Anaconda installerà automaticamente le versioni richieste di cuda, cudNN e gli altri packages.

Figura 04 – conda install -c conda-forge tensorflow-gpu

 

activate tensorflow-gpu

Figura 05 – activate tensorflow-gpu

 

Installa tensorFlow

pip install tensorflow-gpu

Figura 06 – pip install tensorflow-gpu

Adesso hai finito ed hai installato con successo tensorflow con la GPU!

Ricordati di attivare il comando: activate tensorflow-gpu per metterti in modalità GPU!

 

Test GPU

python

import tensorflow as tf

sess = tf.Session(config=tf.ConfigProto(log_device_placement=True))

 

Figura 07 – test GPU

 

Test su CIFAR-10 con 10 epoche

Tempo medio per epoca: 150 sec

Tempo totale: 25 min

Figura 08 – Test su CIFAR-10 con 10 epoche