Algebra Lineare per il Deep Learning Parte III

Inversione della Matrice – Algebra Lineare per il Deep Learning (parte 3)

Sommario

Nel precedente articolo sull’algebra lineare abbiamo considerato le operazioni di base sulle matrici come la somma e la moltiplicazione tra matrici. Queste operazioni sono un prerequisito necessario verso il concetto di inversione di matrice.

In questo articolo introduciamo l’inversione di matrice e  ne descriviamo l’importanza. Motiviamo l’inversione della matrice attraverso il concetto di risoluzione di equazioni lineari simultanee, che possono essere familiari dalle lezioni di matematica delle scuole superiori.

Risolvere equazioni lineari simultanee è indispensabile in molti campi della scienza applicata. Nella fisica e  nell’ingegneria, la simulazione numerica dei flussi di fluido su un computer richiede la risoluzione di equazioni lineari simultanee. Nella finanza quantitativa sono usate per risolvere il Black-Scholes PDE, necessaria per i prezzi di alcuni tipi di opzioni.

L’inversione della matrice è una tecnica importante perchè può aiutarci a risolvere queste equazioni lineari simultanee. È un metodo fondamentale nella statistica e nel machine learning, che deriva dalla soluzione della stima dei minimi quadrati ordinari per la regressione lineare .

Equazioni lineari simultanee

Iniziamo con un esempio motivante di un piccolo insieme di equazioni lineari simultanee:

\(\begin{eqnarray}
x + 2y + 4z &=& 10 \\
3x + y – 5z &=& -8 \\
4x – 3y + 7z &=& 4
\end{eqnarray}\)

L’obiettivo consiste nel trovare i valori di x, y e z che soddisfano queste equazioni. Nel caso precedente, con solo tre equazioni, una manipolazione algebrica relativamente semplice fornisce la risposta.

Quando il numero di equazioni aumenta in modo significativo, può diventare complicato dal punto di vista nozionale scrivere le equazioni in questo modo.

Un’alternativa è scrivere tali sistemi in modo compatto usando la notazione matriciale. Considerano \(\boldsymbol{x} = [x, y, z]^T\), \(\boldsymbol{b} = [10, -8, 4]^T\) e la matrice dei coefficienti A abbiamo quanto segue:

\(\boldsymbol{A} = \left[ \begin{array}{ccc}
1 & 2 & 4 \\
3 & 1 & -5 \\
4 & -3 & 7
\end{array} \right]\)

È possibile scrivere il sistema sopra come:

\(\left[ \begin{array}{ccc}
1 & 2 & 4 \\
3 & 1 & -5 \\
4 & -3 & 7
\end{array} \right]
\left[ \begin{array}{c}
x \\
y \\
z
\end{array} \right] =
\left[ \begin{array}{c}
10 \\
-8 \\
4
\end{array} \right]\)

Oppure, in modo più compatto:

\(\begin{eqnarray}
\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}
\end{eqnarray}\)

Il carattere in grassetto sottolinea che i termini nell’equazione sono quantità vettoriali e matriciali piuttosto che quantità scalari.

Se questa fosse un’equazione algebrica della forma \(A x = b\) con \(A \neq 0\), dove \(A, x, b \in \mathbb{R}\) cioè i termini sono tutte quantità scalari, allora questo potrebbe essere risolta per x dividendo semplicemente per A:

\(\begin{equation}
x = \frac{b}{A} = \frac{1}{A} b = A^{-1} b
\end{equation}\)

Questa equazione dimostra  che \(x = A^{-1} b\). Possiamo quindi chiederci se sia possibile risolvere l’equazione della matrice \(\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}x\) attraverso una forma simile all’espressione \(\boldsymbol{x} = \boldsymbol{A}^{-1} \boldsymbol{b}\)?

Poiché l’operazione di divisione per una matrice non è definita, la risposta sta nella definizione della matrice \(\boldsymbol{A}^{-1}\), nota come matrice inversa di A. Per farlo è però necessario introdurre ulteriori strumenti matematici.

Delta di Kronecker e matrici di identità

Il delta di Kronecker è una funzione matematica di due variabili i,- j con i seguenti valori:

\(\begin{equation}
\delta_{ij} =
\begin{cases}
1, & \text{if } i=j,\\
0, & \text{if } i\neq j.
\end{cases}
\end{equation}\)

In sostanza, il delta di Kronecker è pari a uno quando i e j sono uguali mentre è pari a zero quando sono diversi.

Questa funzione può essere utilizzata per definire una nuova matrice quadrata in cui ogni elemento della matrice in posizione i,j è uguale al delta di Kronecker di quel valore.

Matematicamente questo è scritto in modo compatto come \(\boldsymbol{I}_n=[\delta_{ij}]_{n \times n}\). La matrice stessa avrà la seguente forma:

\(\begin{equation}
\boldsymbol{I}_n=\begin{bmatrix}
\kern4pt 1 & 0 & 0 & \dots & 0 \kern4pt \\
\kern4pt 0 & 1 & 0 & \dots & 0 \kern4pt \\
\kern4pt 0 & 0 & 1 & \dots & 0 \kern4pt \\
\kern4pt \vdots & \vdots & \vdots & \ddots & \vdots \kern4pt \\
\kern4pt 0 & 0 & 0 & \dots & 1 \kern4pt \\
\end{bmatrix}
\end{equation}\)

In particolare tutti gli elementi della matrice sono zero tranne quelli sulla diagonale della matrice, che sono uguali a uno. Questo perché gli elementi diagonali rappresentano il caso in cui i=j e il delta di Kronecker è uguale a uno per questi valori.

Questo tipo di matrice è noto come matrice identità con dimensione n. La matrice identità possiede la proprietà unica che quando viene moltiplicata a sinistra o a destra per una qualsiasi matrice quadrata \(\boldsymbol{A} \in \mathbb{R}^{n \times n}\) lascia invariata A:

\(\begin{equation}
\boldsymbol{I}_n \boldsymbol{A} = \boldsymbol{A} \boldsymbol{I}_n = \boldsymbol{A}
\end{equation}\)

Questo è facilmente dimostrabile con la definizione di moltiplicazione tra matrici  descritte nell’articolo precedente.

Possiamo ora definire la matrice inversa \(\boldsymbol{A}^{-1}\). L’inversa di una matrice è precisamente la matrice che moltiplicata a sinistra o a destra per A produce la matrice identità:

\(\begin{equation}
\boldsymbol{A}^{-1} \boldsymbol{A} = \boldsymbol{I}_n = \boldsymbol{A} \boldsymbol{A}^{-1}
\end{equation}\)

Quanto sopra può essere dimostrato considerando le analoghe regole di moltiplicazione per un’equazione algebrica scalare equivalente:

\(\begin{equation}
\frac{a}{a} = \frac{1}{a} a = a^{-1} a = 1 = a a^{-1} = a \frac{1}{a} = \frac{a}{a}
\end{equation}\)

In particolare \(a^{-1} a = 1 = a a^{-1}\). Il valore 1 può essere interpretato come una matrice 1×1 con un unico valore.

Risolvere l’equazione matriciale

Con queste definizioni è ora possibile risolvere l’equazione originale \(\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}\):

\(\begin{eqnarray}
\boldsymbol{A} \boldsymbol{x} &=& \boldsymbol{b} \\
\boldsymbol{A}^{-1} \boldsymbol{A} \boldsymbol{x} &=& \boldsymbol{A}^{-1} \boldsymbol{b} \\
\boldsymbol{I}_n \boldsymbol{x} &=& \boldsymbol{A}^{-1} \boldsymbol{b} \\
\boldsymbol{x} &=& \boldsymbol{A}^{-1} \boldsymbol{b}\label{eqn-matrix-inverse}
\end{eqnarray}\)

Innanzitutto l’equazione viene moltiplicata a sinistra per la matrice inversa \(\boldsymbol{A}^{-1}\). Il termine \(\boldsymbol{A}^{-1} \boldsymbol{A}\) può quindi essere impostato sulla matrice identità \(\boldsymbol{I}_n\).

Dato che qualsiasi vettore o matrice rimane invariato quando moltiplicato per la matrice identità, possiamo rimuovere il riferimento a \(\boldsymbol{I}_n\) e quindi ottenere un’espressione per x in termini di matrice inversa \(\boldsymbol{A}^{-1}\) e il vettore b.

Possiamo quindi risolvere l’equazione \(\boldsymbol{x} = \boldsymbol{A}^{-1} \boldsymbol{b}\) per il vettore sconosciuto x supponendo che esista un’appropriata \(\boldsymbol{A}^{-1}\).

Tuttavia, dobbiamo ancora descrivere come procedere per calcolare \(\boldsymbol{A}^{-1}\) o se è possibile farlo.

Questo sarà argomento per futuri articoli della serie, ma descriviamo brevemente alcuni dei principali meccanismi per il calcolo dell’inversa della matrice.

Algoritmi per l’inversione di matrice

Un metodo comune per trovare l’inverso di una matrice (se esiste) consiste nell’utilizzare una tecnica nota come eliminazione Gauss-Jordan (o eliminazione gaussiana). Tuttavia per un matrice \(n \times n\) di grandi dimensioni è un meccanismo costoso e inefficiente per trovare l’inversa.

Il costo dell’operazione aumenta cubicamente con la dimensione della matrice, cioè ha una complessità aritmetica di \(\mathcal{O}(n^3)\). Questo può essere un problema significativo quando è necessario eseguire molte operazioni di calcolo delle matrici inverse.

Per la maggior parte delle applicazioni nelle scienze applicate, nella finanza quantitativa e nel deep learning è sufficiente approssimare la soluzione x entro una certa tolleranza piuttosto che cercare il valore esatto.

Esistono molti algoritmi meno intensivi dal punto di vista computazionale che sono abbastanza efficaci da fornire l’accuratezza necessaria.

Questi algoritmi consistono in una versione ben ottimizzata dell’eliminazione di Gauss-Jordan per  particolari matrici strutturateo utilizzano un approccio iterativo che approssima x con una certa precisione in un numero finito di iterazioni.

La necessità di approssimare efficacemente x nella suddetta equazione matriciale ha portato allo sviluppo di un intero sottocampo della matematica noto come Algebra Lineare Numerica.

Alcune fattorizzazioni di matrici possono essere estremamente utili per risolvere in modo più efficiente questa equazione. Tali fattorizzazioni sono ampiamente discussi negli articoli successivi.

Prossimi passi

Nel prossimo articolo descriviamo l’eliminazione di Gauss-Jordan e scriviamo del codice Python per eseguire un’inversione di matrice e confrontare la nostra implementazione con quella fornita dalla libreria SciPy.
SCRIVIMI SU TELEGRAM

Per informazioni, suggerimenti, collaborazioni...

Se è la prima volta che atterri su DataTrading, BENVENUTO!

Lascia che mi presenti. Sono Gianluca, ingegnere, trekker e appassionato di coding, finanza e trading. Leggi la mia storia.

Ho creato DataTrading per aiutare le altre persone ad utilizzare nuovi approcci e nuovi strumenti, ed applicarli correttamente al mondo del trading.

DataTrading vuole essere un punto di ritrovo per scambiare esperienze, opinioni ed idee.

TUTORIAL

TOOLBOX

Gli altri articoli di questa serie

Torna su