Home

Federica EU

1/18

Roberto Prevete » 4.Possibili problemi risolvibili con Reti Neurali

Introduzione

Nella prossime due lezione descriveremo un po’ più nel dettaglio alcuni problemi risolvibili con le reti neurali. In particolare:

Problemi di Classificazione
Problemi di Clusterizzazione
Problemi di Regressione

Iniziamo con il vedere cosa è un problema di classificazione …

Problema di Classificazione

Classificare è un’attività fondamentale svolta da tutti gli esseri viventi. Tramite i nostri sensi abbiamo esperienza di un oggetto e siamo subito in grado di “classificarlo” in una particolare categoria, ad esempio come:

sedia;
tavolo;
animale;
pianta;
commestibile;
velenoso;
ecc.

Problema di Classificazione (segue)

È importante osservare che questa capacità di classificare nella giusta categoria un “oggetto” passa attraverso una fase preliminare di “esperienza con oggetti simili”.

In maniera analoga, è possibile pensare ad un algoritmo in grado, tramite l’osservazione di un insieme di casi, di classificare “oggetti” nella appropriata categoria.

Problema di Classificazione: Un esempio

Supponiamo di avere un cesto pieno di palline di colore diverso e vogliamo distinguere le palline di colore rosso da tutte le altre. Quindi noi sappiamo, a priori, che il nostro insieme di palline si suddivide in due classi:

PALLINE ROSSE,
PALLINE NON ROSSE.

Il problema è quello di definire in maniera operativa un modo automatico (o semi-automatico) per assegnare ciascuna pallina alla classe PALLINE ROSSE o alla classe PALLINE NON ROSSE.

Problema di Classificazione: Un esempio (segue)

Ad esempio, possiamo definire un primo algoritmo (semplice) che possa risolvere il problema:

- classe ← PALLINE ROSSE
ELSE classe ← PALLINE NON ROSSE

Dove x è un array di dimensione 3 contente i valori R, G e B tramite i quali descriviamo il colore di ciascuna pallina.

Problema di Classificazione: Alcune osservazione

La classificazione di un oggetto avviene sempre in base a degli attributi, proprietà, caratteristiche dell’oggetto stesso che lo accomunano ad altri oggetti.

Le classi si possono considerare come “etichette” (spesso mutuamente esclusive) che si “pongono” su un oggetto.

Un oggetto da classificare è, allora, rappresentato da un vettore contenente i valori dei suoi attributi, caratteristiche.Nell’esempio precedente, allora, ogni pallina è rappresentato da un vettore $x=[R,G, B]$ costituito da tre valori (caratteristiche dell’oggetto).

Problema di Classificazione: Una formalizzazione

Un problema di classificazione può essere caratterizzato, in maniera non esaustiva ma utile per gli scopi del corso, nella seguente maniera:

Un insieme U di elementi, che costituiscono l’Universo, tale che ogni suo elemento $u \in U$ appartenga ad una tra m classi $C_k$ , con $k=1,2, ...,m$ , che rappresentano una partizione di U.
Un processo effettivo (un algoritmo) che associa ciascun elemento di U ad un insieme di valori. Possiamo dire che esiste una funzione $F: u\inU\rightarrow x^u=F(u)\in D\subseteqR^d$ . Cioè ogni elemento u di U è rappresentato da un unico elemento $x^u=(x^u_1,x^u_2,...,x^u_d)$ di D, dove D è, in genere, un sottoinsieme d-dimensionale di $R^d$ .

Problema di Classificazione: Una formalizzazione (segue)

Un processo effettivo (un algoritmo) che sia capace di assegnare ogni $u \in U$ , rappresentato da $x^u=(x^u_1,x^u_2,...,x^u_d)$ (vettore di caratteristiche), ad una ed una sola classe $C_k$ .

Una “misura di bontà” del risultato del processo di classificazione.

Problema di Classificazione: Una formalizzazione (segue)

Naturalmente una qualsiasi processo che faccia questo è sempre realizzabile, il problema è, però, se tale processo è un “buon” algoritmo di classificazione oppure no.

Vediamo, allora, quali sono alcune proprietà che definiscono un “buon” algoritmo di classificazione.

***

Problema di Classificazione: Una formalizzazione (segue)

In teoria, il miglior algoritmo di classificazione dovrebbe essere capace di classificare ogni $u\in C_k$ a $C_k$ stesso.

Dovrebbe permettere:

Classificazione accurata: classificare gli elementi in maniera accurata, anche in presenza di rumore o di dati mancanti.
Ampio dominio di applicabilità. Il classificatore deve essere adatto per classificare qualunque oggetto di qualunque dominio. Questo implica che sia in grado di trattare ugualmente bene attributi di tipo diverso (reali, interi, stringhe, date, ecc.)

Problema di Classificazione: Misura di bontà

Una possibile “misura di bontà” del risultato del processo di classificazione è dato da due parametri:

Recall;
Precision.

Qualitativamente, il primo parametro indica la capacità dell’algoritmo di recuperare tutti gli elementi della classe.

Il secondo parametro, invece, la capacità dell’algoritmo di non sbagliare.

Andiamo a precisare formalmente cosa intendiamo con recall e precision.

Problema di Classificazione: Misura di bontà (segue)

Supponiamo che l’insieme U di N elementi da classificare sia suddiviso in due classi C e U-C. Una volta che abbiamo realizzato il processo di classificazione su tutti gli N elementi di U, di cui conosciamo l’effettiva classificazione, definiamo:

True Positive (TP)= il numero di elementi che sono stati classificati come appartenenti a C e che effettivamente appartengono a C.
False Positive (FP)= il numero di elementi che sono stati classificati come appartenenti a C ma che, in realtà, appartengono a U-C.
True Negative (TN)= il numero di elementi che sono stati classificati come appartenenti a U-C e che effettivamente appartengono a U-C.
False Negative (FN)= il numero di elementi che sono stati classificati come appartenenti a U-C ma che, in realtà, appartengono a C.

Ovviamente è: TP+FP+TN+FN=N

Problema di Classificazione: Recall e Precision

Osserviamo che il numero di elementi che il processo di classificazione ha classificato come appartenenti a C è pari a TP+FP.
Allora definiamo:

Recall = TP/(TP+FN)
Precision= TP/(TP+FP)

In figura: Recall e Precision. L’ovale bianco corrisponde all’insieme U sottoposto al processo di classificazione. L’ovale grigio rappresenta gli elementi di U che appartengono alla classe C, i restanti elementi non appartengono alla classe C. Il rettangolo grigio rappresenta gli elementi che un processo di classificazione assegna alla classe C.

Recall e Precision.

Problema di Classificazione: Recall e Precision (segue)

La situazione ideale è quella per cui si ha Recall e Precision pari a 1. Recall=1 significa che tutti gli elementi che appartenevano alla classe C e che sono stati dati in input al processo di classificazione sono stati effettivamente classificati come appartenenti alla classe C. Mentre Precision=1 significa che tutti gli elementi che appartenevano alla classe U-C e che sono stati dati in input al processo di classificazione sono stati effettivamente classificati come appartenenti alla classe U-C.
Avere solo uno dei due pari a 1 (Recall o Precision) è facile, ad esempio Recall=1 si ottiene classificando sempre un elemento come appartenente alla classe C, il difficile è avere entrambi i valori alti.

Recall e Precision.

Problemi di Clusterizzazione

Un problema di clusterizzazione (o segmentazione) ha molte cose in comune con un problema di classificazione ma, possiamo affermare, che sussiste in una fase precedente.

In questo caso, infatti, l’insieme U di elementi che rappresenta il nostro universo non è a priori suddiviso in un numero finito di classi ma si vuole proprio determinare se tale insieme è suddivisibile in classi in base a qualche “misura di distanza” tra gli elementi dell’insieme U.

Problemi di Clusterizzazione (segue)

Anche in questo caso, in generale, possiamo dire che un problema di segmentazione è caratterizzato da:

Un insieme U di elementi, che costituiscono l’Universo.
Un processo automatico che associa ciascun elemento di U ad un insieme di valori. Possiamo dire che esiste una funzione $F: u\inU\rightarrow x^u=F(u)\in D\subseteqR^d$ . Cioè ogni elemento u di U è rappresentato da un unico elemento $x^u=(x^u_1,x^u_2,...,x^u_d)$ di D, dove D è, in genere, un sottoinsieme d-dimensionale di Rd.
Una misura di somiglianza tra due elementi di U. Cioè è definita una funzione $s: x,y \inD \rightarrow s(x,y) \in R$ in modo tale che la “somigliaza” tra $u,v_U$ è definita pari a $s(F(u),F(v))$ .
Un criterio per raggruppare gli elementi di U in differenti classi in base alla misura di somiglianza.

Problemi di Regressione

Nel caso dei problemi di regressione, invece, in maniera molto sintetica, abbiamo la necessità di modellare una relazione (espressa, in genere, in termini di una funzione) tra variabili continue.

Ad esempio, dato un insieme di n valori ordinati $x_1, x_2, \dots ,x_n$ a cui sono associati n valori $y_1, y_2, \dots,y_n$ tramite una qualche funzione sconosciuta f, cioè $y_i=f(x_i)$ , si vuole conoscere per il prossimo valore $x_{n+1}$ q uale sia il valore associato $y_{n+1}$ . Fondamentalmente, allora, abbiamo il problema di approssimare la funzione f sulla base dei valori $x_1, x_2, \dots,x_n$ e $y_1, y_2, \dots,y_n$ .

Problemi di Regressione (segue)

Nota importante.

I tre tipi di problemi fin qui esposti (classificazione, segmentazione, e regressione) si possono ridurre (o lo sono già di per sé) a problemi di approssimazione di funzioni.

Nel prosieguo focalizzeremo la nostra attenzione sui problemi di classificazione e di approssimazioni di funzioni.