ALGEBRA LINEARE PER TUTTI [Parte 1]

Autore: Paolo Caressa

 

Premessa

Come in ogni altro settore interdisciplinare nel machine learning ed nel deep learning si utilizzano necessariamente nozioni, concetti e formalismi che provengono da diverse fonti e, per molti versi, che richiedono mentalità diverse per essere compresi.

Per questo motivo, si è soliti dire che il data scientist dovrebbe essere un “incrocio” fra un informatico, uno statistico e un matematico ma pochi sono versati in tutte e tre le materie e difficilmente tutte e tre risulteranno egualmente facili, intuitive e belle a una stessa mente.

In particolare, delle varie nozioni matematiche che sono indispensabili ad un data scientist, come per chi è unicamente interessato a capire come funziona un sistema di machine learning per poterlo gestire al meglio, una delle nemesi è l’algebra lineare.

Ciò è sorprendente per i matematici che invece considerano l’algebra lineare una cosa facilissima.

Mi permetto di dire, citando il matematico I.M. Herstein, che l’algebra lineare ha solo tre caratteristiche, è facile, utile e bella!

Lo scopo di questo tutorial è di spiegare in modo semplice ma non privo di rigore le nozioni di base dell’algebra pertanto se già sapete calcolare autovettori ed autovalori di una matrice o magari una decomposizione in valori singolari (SVD) o un’analisi delle componenti principali (PCA) ci salutiamo qua. In caso contrario, buona lettura!

 

Il piano e lo spazio cartesiano

Prendiamola un po’ alla lontana, andando a scavare nei nostri ricordi delle scuole superiori: “la geometria analitica (o cartesiana)”

Inventata da Cartesio e Fermat nel XVII secolo, l’idea di base della geometria cartesiana è di fornire un modello numerico per il piano e lo spazio. In breve, la scoperta consiste nell’identificare l’insieme dei punti del piano (cioè mappato in maniera biunivoca in modo da esserne indistinguibile) con l’insieme delle coppie di numeri (x,y) con x ed y indipendenti.

Per prima cosa ricordiamo che i punti della retta si identificano all’insieme dei numeri reali (cioè razionali ed irrazionali) ordinato dalla solita relazione <.

Fissiamo un punto O sulla retta e corrispondente a 0, si fissa un punto U (diverso da O) e lo si fa corrispondere a 1; tutti gli altri punti sono determinati dalla posizione relativa rispetto a questi:

 

recta

È quindi chiaro cosa voglia dire la distanza fra due punti P e Q sulla retta: se x ed y sono i numeri corrispondenti, la distanza PQ è pari a |x – y| (valore assoluto della differenza):

 

Cattura 1 1

 

 

Quindi su una retta basta fissare lo zero e l’uno, col che si è fissato il verso dei numeri positivi (quelli che stanno tutti da una parte di O e comprendono U) e dei numeri negativi (quelli che stanno tutti da una parte di O e non comprendono U).

In questo modo:

La retta della geometria si identifica completamente nell’insieme R dei numeri reali

 

Ad un punto corrisponde uno e un solo numero, dove ogni numero reale possiamo immaginarlo come un numero decimale avente un numero finito di cifre dopo la virgola, avente un numero finito di cifre dopo la virgola che si ripetono indefinitamente, o avente un numero infinito non periodico di cifre dopo la virgola (a rigore bisogna escludere le sequenze che terminano con un 9 periodico).

Passiamo ora al piano.

Si fissa un punto O nel piano e si prende una retta x che passi per il punto ed una seconda retta ortogonale a x, chiamata y. Su x e y si sceglie una stessa unità di misura (cioè un punto U diverso da O e si stabilisce convenzionalmente che la distanza OU vale 1).

In questo modo si può misurare la distanza fra due punti che stanno su x rispetto all’unità di misura fissata.

La corrispondenza fra un punto P del piano e una coppia (a,b) di numeri avviene come segue:

  1. Si proietta il punto P sull’asse x ottenendo un punto P’ e si pone a = distanza fra P’ e O.
  2. Si proietta il punto P sull’asse y ottenendo un punto P’’ e si pone b = distanza fra P’’ e O.

Questo associa in modo unico a P la coppia (a,b): per passare invece dalle coordinate (a,b) ai punti basterà trovare i punti P’ e P’’ sulle rette x e y che distano per a e b dall’origine O, tracciare le perpendicolare agli assi per questi punti e determinare P come la loro intersezione.

Plano cartesiano

Figura 1. Tre punti del piano cartesiano, le loro coordinate e le loro proiezioni sugli assi, Fonte: wikipedia

 

 

Quindi:

Il piano della geometria si identifica completamente all’insieme R2 delle coppie di numeri reali: a un punto corrisponde una e una sola coppia.

La notazione R2 indica le coppie ordinate di elementi di R. Se X è un insieme Xn è in generale l’insieme delle n-ple di elementi di X.

Che vantaggio c’è nel considerare il piano come l’insieme delle coppie di numeri (a,b)?

  • In primo luogo sappiamo dire cosa sia, un insieme di coppie appunto, non ci servono assiomi o altro.
  • In secondo luogo trasformiamo i problemi geometrici, che normalmente coinvolgono costruzioni complicate e ragionamenti assai lunghi, in calcoli.

La geometria cartesiana è quindi la geometria ideale da fare al computer: possiamo ridurre tutto a numeri e calcoli. Non a caso, le librerie 2D che si usano per disegnare sullo schermo del computer, o su una finestra di una applicazione, rappresentano i punti come coppie di numeri (le coordinate) e un attributo che ne rappresenta il colore.

Per esempio: come si rappresenta una curva nel piano cartesiano?

Ci sono due modi:

  • Tramite una equazione cartesiana, una singola relazione che lega le coordinate di un suo generico punto
  • Tramite una equazione parametrica, che esibisce il generico punto della retta in funzione di un parametro.

Per esempio consideriamo l’equazione x2+y2 = 1 e l’equazione 2x+y = 0. La prima rappresenta una circonferenza di centro l’origine e raggio 1, la seconda una retta passante per l’origine.

Supponiamo di volerne calcolare le intersezioni: utilizzando la geometria classica dovremmo costruire queste intersezioni in qualche modo, mentre con la geometria cartesiana ci stiamo facendo la seguente domanda: quali sono i punti di coordinate (x,y) soggetti simultaneamente alle relazioni  x2+y2 = 1 e 2x+y = 0?

La seconda equazione equivale a dire y = –2x, che sostituita nella prima offre x2+(–2x)2 = 1, cioè x2+4x2 = 1 cioè x2 = 1/5, che ha due soluzioni x = 1/√5 e x = –1/√5, col che troviamo le due intersezioni richieste: i punti (1/√5, –2/√5) e (–1/√5, 2/√5).

A questo punto identifichiamo lo spazio cartesiano in tre dimensioni con l’insieme delle triple (x,y,z) di numeri reali, cioè con l’insieme R3.

Un punto nello spazio è quindi univocamente determinato dalle sue tre coordinate cartesiane, su cui possiamo lavorare per risolvere i problemi geometrici, dopo averli tradotti in problemi algebrici

 

Distanza fra due punti

Abbiamo detto che lungo una retta, identificata con l’insieme dei numeri reali, le distanze si calcolano col valore assoluto della differenza. Come calcoliamo invece le distanze nel piano?

La cosa interessante è che esistono diversi modi di farlo, che costituiscono tutti generalizzazioni della distanza sulla retta, citiamo le tre principali tutte appartenenti alla famiglia delle distanze di Minkonski:

  • la distanza euclidea
  • la distanza di Manhattan
  • la distanza uniforme.

La distanza euclidea fra due punti P = (x1,y1) e Q = (x2,y2) nel piano è data dalla formula seguente:

Cattura 2

Intanto vediamo che se P e Q stanno su una stessa retta, per esempio l’asse delle x, questa distanza si riduce al valore assoluto della differenza delle coordinate: infatti se supponiamo P = (x1,0) e Q = (x2,0) la  formula precedente ci porge :

 

cattura 3

(come al solito quando prendiamo la radice quadrata di un numero consideriamo quella positiva).

La distanza euclidea andrebbe in realtà chiamata pitagorica, in quanto segue dal teorema di Pitagora: supponiamo di avere un triangolo rettangolo OPQ, con un vertice nell’origine, un lato sull’asse delle x e l’altro lato perpendicolare all’asse delle x.

Dunque le coordinate di P saranno del tipo (x,0) e quelle di Q del tipo (x,y): la distanza fra O e P è x e quella fra Q e P è y, col che, per il teorema di Pitagora, d(O,Q)2 = d(O,P)2 + d(P,Q)2 = x2 + y2. Per cui in questo caso, prendendo la radice quadrata,

Cattura 4

e la formula è verificata. Nel caso generale il ragionamento è analogo ma intervengono anche le coordinate di O (che nel nostro caso risultano essere nulle).

Quindi la distanza euclidea si riduce alla distanza fra due punti su una retta e ha un evidente contenuto geometrico.

recta.opq

 

La distanza nello spazio si calcola in modo analogo tenendo conto che i punti hanno una coordinata in più: se P = (x1,y1,z1) e Q = (x2,y2,z2) sono punti dello spazio cartesiano, la loro distanza è:

Cattura 5 1

Per i più curiosi, spiego nel resto di questo paragrafo altri due modi di calcolare la distanza nel piano, che danno luogo a valori diversi della distanza euclidea ma che sono modi comunque validi di misurare quanto due punti sono vicini (un bel teorema che non è il caso di riportare qui dice comunque che, ai fini della relazione di “essere nei pressi di”, tutte queste distanze sono equivalenti).

Un’altra distanza che talvolta si usa in machine learning è la “distanza di Manhattan” anche conosciuta come “distanza dei taxi”:

d_1\left ( P,Q \right )= \left \| X_1-X_2 \right \| + \left \| Y_1-Y_2 \right \|

Di nuovo, se P e Q stanno sull’asse delle x, questa distanza coincide con il valore assoluto della differenza. Il nome distanza dei taxi è data dal fatto che la distanza fra P e Q non si misura col teorema di Pitagora, che cerca una scorciatoia diagonale fra P e Q ma partendo da P e muovendosi lungo l’asse delle x fino a giungere sopra o sotto a Q, per poi spostarsi lungo l’asse delle y e raggiungere Q.

 

 

 

 

 

 

DITANZA EUCLIDEA TRIANGULO

Figura 2. Distanza euclidea (verde) vs. distanza dei taxi (rosso)

È la manovra che deve fare un taxi per andare da un punto di un isolato al punto opposto: non può passare in mezzo all’isolato ma deve costeggiarne i lati.

Un’altra distanza ancora, che talvolta è utilizzata, è la “distanza uniforme”, che è definita comed_0 \left ( P,Q \right )= max \left \{ |x_1-x_2 | \right \}\left \{ |y_1-y_2 | \right \}

Cioè questa si calcola prendendo la lunghezza massima del segmento ottenuto proiettando i due punti sugli assi delle x e delle y: di nuovo è ovvio che se i punti giacciono sull’asse delle x questa si riduce al valore assoluto della differenza fra due punti.

Una notazione di colore: nello spazio, una “palla” si definisce come l’insieme dei punti che hanno distanza minore di un numero fissato, il raggio, da un punto fissato, il centro: cioè se O è il centro e r il raggio, tutti i punti tali che d(P,O) < r costituiscono la palla. Questa terminologia è chiara se usiamo la distanza euclidea.

Ma, usando la distanza dei taxi, che figura geometrica viene fuori considerando tutti i punti P tali che d1(P,O) < r? (suggerimento: si dice che questa distanza abbia le palle quadrate…).

Introduzione a Metodi di riduzioni della Dimensionalità ed elementi di Algebra lineare [Parte 2]

 

Autore: Matteo Alberti

                            

Sommario

Metodi lineari per la riduzione: 2

Identificazione attraverso l’individuazione di sottospazi 2

Approssimazioni Matriciali per la riduzione. 10

Casi di applicazione base: Decomposizione in Valori Singolari (SVD). 11

Norme Matriciali 11

Norme vettoriali 13

Norme indotte. 13

Norme di Schatten. 13

Norma di Frobenius. 13

Casi di applicazione base: Analisi dei Cluster. 16

Definizione di metrica. 16

Distanze di Minkowski (Manhattan, Euclidea, Lagrange). 16

 

 

 

Lo scopo di questo primo tutorial è di introdurre le nozioni base di riduzione della dimensionalità dal punto di vista matematico (spazi, sottospazi, mappe lineari) e di riprendere gli elementi necessari di algebra lineare (norme, isometria, isomorfismo…) per ogni algoritmo di machine learning.

 

Norme Matriciali

 

Abbiamo a questo punto impostato il problema della riduzione della dimensionalità dei dati come un problema di approssimazione tra matrici, dobbiamo a questo punto andar a stabilire valutare e quindi calcolare la distanza fra la matrice dei dati originari e quella approssimante attraverso lo studio delle differenti norme:

Esistono tre principali tipologie di norme:

  • Norme vettoriali
  • Norme indotte
  • Norme di Schatten

Dove nel campo dell’analisi dei dati essenzialmente ci si riconduce, salvo eccezioni, alla norma di Frobenius (distanza euclidea)

 

 

 

 

Elementi di algebra:

Norma

Una norma (comunemente contrassegnata con ) è una funzione dallo spazio vettoriale delle matrici se:

 

Art2 1

 

Norme vettoriali

 

La famiglia delle norme vettoriali trattano la matrice X_n_x_k  come un vettore di nk componenti dove possiamo definire la norma utilizzando una delle qualsiasi norme seguenti:

art2 imagr2

Nota:

Ponendo p=2 ci si ricollega alla norma euclidea

 

Norme indotte

 

Una matrice X_n_x_k  può essere vista come un operatore lineare da   R^k \mapsto R^n .

Misurando in R^k  le lunghezze con una norma fissata e facciamo altrettanto in R^n , con una differente norma, possiamo andare a misurare quanto X allunga o accorcia un vettore , confrontando la norma di v  \in R^k con la relativa norma della sua immagine Xv.

La norma indotta  \parallel X \parallel _k _n  risulta definita come:

 

art2 3

Norme di Schatten

 

La norma di Schatten, di ordine p, di una matrice X è data semplicemente da:

Art2 4

Dove \omega_i  sono i valori singolari

 

 

Norma di Frobenius

 

La norma di Frobenius della nostra matrice  X_n_x_k di partenza è data da:

ART25

 

 

Andando a svolgere i conti, esplicitando il prodotto matriciale si ottiene:

art6.art2

Ne corrisponde che la norma di Frobenius è pari alla radice quadrata della somma del quadrato degli elementi ossia una norma euclidea vista come un vettore che coincide con la norma vettoriale di X di ordine 2.

 

 

 

 

 

Elementi di algebra:

Traccia

L’operatore traccia, indicata con Tr \left ( . \right ), è definita come la somma degli elementi diagonali della matrice argomento

 

 

 

 

 

 

 

 

Casi di applicazione base: Analisi dei Cluster

 

La cluster analysis e’ una tecnica di analisi multivariata attraverso la quale e’ possibile raggruppare le unità statistiche, in modo da minimizzare la “lontananza logica” interna a ciascun gruppo e di massimizzare quella tra i gruppi.

Rientra fra le tecniche di apprendimento non supervisionato.

Nasce quindi spontaneo dover definire che cosa si intende per lontananza logica ed in base a quale metrica.

 

 

 

Definizione di metrica

Sia  X^-\in R^p ed Y^-\in R^p definiamo metrica una funzione tale che   R^p x R^p\mapsto R^+   U\left \{ 0 \right \} 

che goda delle seguenti proprietà:

  •  d \left ( X^-, Y^- \right ) \geq O non negativa
  •  d \left ( X^-, Y^- \right ) = d \left ( Y^-,X^- \right ) simmetria
  •  d \left ( X^-, Y^- \right ) = 0 \leftrightarrow X= Y identità
  •  d \left ( X^-, Y^- \right ) \leq d \left ( X^-, Z^- \right ) + d \left ( Z^-, X^- \right )   diseguaglianza triangolare

 

Distanze di Minkowski (Manhattan, Euclidea, Lagrange)

 

Andiamo a questo punto ad analizzare i casi principali delle distanze appartenenti alla famiglia delle distanze di Minkowski dove:

art27

Evidenziamo i seguenti casi:

  • k=1 Distanza di Manhattan
  • k=2  Distanza Euclidea
  • k\rightarrow \infty Distanza Lagrangiana (Čebyšëv)

In particolare:

 

 

euclidea

Riprendendo dunque con l’esempio della Cluster Analysis, risulta fondamentale quindi definire il tipo di distanza con cui vogliamo affrontare la nostra analisi.

Principalmente nei pacchetti già implementati si trovano le tre varianti delle distanze di Minkowski (per variabili quantitative)

Importando da sklearn:

AgglomerativeClustering(n_clusters=2, affinity=’euclidean’, memory=None, connectivity=None, compute_full_tree=’auto’, linkage=’ward’

 

 

distanze