Roberto Prevete » 19.Parametri delle funzioni a base radiale

Introduzione

Nella presente lezione ci concentreremo sulla stima dei parametri delle funzioni a base radiale,
in particolare nel caso delle gaussiane:

• Sul calcolo dei centri e

• Sul calcolo della deviazione standard.

Calcolo dei parametri delle funzioni a base radiale

La scelta dei centri delle funzioni di base dovrebbe essere tale da rispecchiare la densità dei dati di ingresso.

• Vi sono vari approcci per scegliere questi centri.

• Un metodo è quello di avere tante funzioni quanti sono i punti a disposizione e scegliere come centri delle funzioni proprio questi punti.

Calcolo dei parametri delle funzioni a base radiale (segue)

Questa strada non è tuttavia praticabile, per due ragioni fondamentali:

• La prima è il costo computazionale che crescerebbe troppo al crescere dei punti a disposizione;

• La seconda è che ciò costringerebbe la rete a creare un mapping che passi esattamente per i punti di training che di solito sono affetti da errore creando problemi di overfitting e dunque scarsa capacità di generalizzazione.

Calcolo dei parametri delle funzioni a base radiale (segue)

Un altro approccio è quello di scegliere i centri delle funzioni di base in
modo casuale fra i punti di training.

Il risultato di tale approccio dipende molto da quanto il campione di training sia effettivamente rappresentativo della popolazione.

Calcolo dei parametri delle funzioni a base radiale (segue)

Un ulteriore metodo per scegliere i centri delle funzioni base radiale consiste nell’utilizzare un algoritmo di clustering sui punti di training.

Anche in questo caso è importante che i dati di training sia effettivamente rappresentativi della popolazione.

Un algoritmo semplice di clusterizzazione è il K-Means descritto di seguito.

Calcolo dei parametri delle funzioni a base radiale (segue)

Anche la scelta della “ampiezza” delle funzioni a base radiale può essere fatta seguendo varie strade.

Una di queste consiste nello scegliere tale ampiezza come media della distanza Euclidea dei centri dei p centri più vicini.

Il calcolo dell’ampiezza in questo caso può essere, però, computazionalmente abbastanza costoso.

Calcolo dei parametri delle funzioni a base radiale (segue)

Nel caso dell’uso di algoritmi di clustering come metodo per scegliere i centri delle funzioni a base radiale si possono calcolare le ampiezze delle funzioni di base come:

La deviazione standard dei punti appartenenti ai cluster rispetto al centro del cluster stesso.

Un algoritmo di clustering: K-means

Il K-means è un algoritmo di clustering in cui il numero di cluster è deciso a priori.

Il funzionamento dell’algoritmo è il seguente:

Supponiamo di aver a disposizione N punti xⁿ e di voler trovare un insieme di m vettori rappresentativi μ_j con j = 1, . . . ,m. L’algoritmo prova a partizionare l’insieme dei punti x_n in m sottoinsiemi disgiunti S_j contenenti N_j punti in modo da minimizzare la funzione somma dei quadrati data da:

J=∑_{j=1, …,k} ∑_x∈Sj ||x – μ_j||²

Dove μ_j è il vettore “media” dei punti appartenenti a S_j, cioè:

μ_j = (1/N_j) ∑_x∈Sj x

Un algoritmo di clustering: K-means (segue)

La versione batch di tale algoritmo consta dei seguenti passi:

1. Assegna gli N punti a K insiemi S_j in modo casuale.
2. Calcola il punto medio μ_j per ogni insieme S_j.
3. Riassegna ogni punto al sottoinsieme S_j che ha il punto medio più vicino al punto stesso.
4. Se almeno un punto è stato spostato da un insieme ad un altro ritorna al passo 2, altrimenti l’algoritmo termina.

Self-Organizing Map (SOM)

Un altro algoritmo di clustering puo’ essere realizzato tramite un particolare tipo di reti neurali.

Sel-Organizing Map

Vediamo quale è la loro strutture e quale il loro comportamento.

Self-Organizing Map (SOM)

Più nel dettaglio abbiamo il seguente algoritmo:

Consider a set of N vector in a D-dimentional space (dataset):

X = {x1, x2, . . . , xN}

K is the number of output layer nodes.

For each output node nj with j = 1, . . . ,K there is a D-dimentional prototype vector w_j = [w_j1,w_j2, . . . ,w_jD].

We can consider the Euclidean distance as the similarity measure of two vectors.

Self-Organizing Map (SOM) (segue)

Computing the winner neuron.

Let t be the iteration step of the learning process.

Let x(t) be the input vector presented to the network at the step t.

Let w_j(t) be the prototype vector associated to the output nodes j at time t.

The winner neuron for the input vector x(t) is the output node j for which:

w_j(t) = min_i=1,K{|| x(t) – w_i(t) ||}

Where || x(t) – w_i(t) || is the Euclidean distanza of w_j(t) from x(t).

Self-Organizing Map (SOM) (segue)

Updating the winner neuron

w_j(t + 1) = w_j(t) + a(t)[x(t) - w_j]

Where :

w_j is the winner neuron

a(t) is the learning rate and vary according to t (in general it decreases as t increases)

Self-Organizing Map (SOM) (segue)

Updating the nodes in the neighborhood of the winner neuron

Let N(j) be the set of nodes in the neighborhood of the winner node j

The prototype vectors are updated using the following rule:

w_i(t + 1) = w_i(t) + b_ij(t)[x(t) - w_i(t)] for every i belonging to N(j)

w_j(t) otherwise

Where b_ij(t) is a coefficient dependent on both i and j, and it can change at every iterative step.