Il Perceptrone

Nell'ambito dei neuroni di McCulloch-Pitts, $S(x)=\theta[J\cdot x-U]$ l'apprendimento consiste nel modificare l'insieme delle connessioni, ovvero i "pesi" $\{J_{i}\}$, e la soglia $U$, in modo da migliorare l'esecuzione di una data operazione $M:\Omega\subseteq\{0,1\}^{K}\rightarrow\{0,1\}$. Assumiamo di non conoscere $M$ esplicitamente, ma di averne solo degli esempi costituiti da un insieme "insegnante" di coppie (domanda,risposta); le domande corrispondono a vettori input $x\in\{0,1\}^{K}$, mentre le risposte sarebbero i relativi $M(x)$.
Il punto di partenza, stiamo considerando l'apprendimento di un solo neurone, è un neurone con dei parametri $\{J_{i}\}$ e $U$ scelti a caso. Una sessione di allenamento "on-line" consiste nell'iterazione della seguente procedura:

passo 1:Scegliere una domanda a caso, ovvero un $x\in\Omega$ qualsiasi.

passo 2:Controllare se "studente" ed "insegnante" sono d'accordo:

$M(x)=S(x)$:    ritorna al passo 1
$M(x)\neq S(x)$:    modifica i parametri e torna al passo 1

modifica parametri:

$J\quad\rightarrow\quad J+\Delta J[J,U;x,M(x)]$
$U\quad\rightarrow\quad U+\Delta U[J,U;x,M(x)]$

Lo scopo ultimo è quello di ottenere un neurone che riesca ad eseguire perfettamente l'operazione $M$, ovvero tale che $M(x)=S(x)=\theta[J\cdot x-U]\forall s\in\Omega$, che è possibile solo se $M$ è linearmente separabile, visto che stiamo parlando di un solo neurone. La questione è come scegliere $\Delta U$ e $\Delta J$ nella maniera adguata.

Definizione: si dice perceptrone un neurone "studente" di McCulloch-Pitts che impara seguendo la seguente regola di apprendimento:

$$\begin{array}{ccc} M(x)=0,\quad S(x)=1: & \Delta J=-x, ... ...)=1,\quad S(x)=0: & \Delta J=x, & \Delta U=-1 \ \end{array}$$ (7)

L'idea della regola di apprendimento è che se $S(x)=1$ ma dovrebbe essere 0, allora si cerca di diminuire il termine $h=J\cdot x-U$, mentre se $S(x)=0$ invece di 1, allora si cerca di far crescere il termine $h$. La proprietà interessante di questa regole di apprendimento è che converge in un numero finito di passi.

Teorema di Convergenza del Perceptrone: se l'operazione $M$ è linearmente separabile, allora la procedura di apprendimento del Perceptrone converge, in un numero finito di passi, ad una configurazione stazionaria in cui $\forall x\in\Omega:\quad S(x)=M(x)$.

Dimostrazione:

Iniziamo semplificando le equazioni introducendo la costante $x_{0}=1$, ed identificando $J_{0}=-U$ per cui possiamo scrivere:

$$S(x)=\theta[J\cdot x],\quad x=(x_{0},x_{1},...,x_{K})\in\{0,1\}^{K+1}$$

$$J=(J_{0},J_{1}...J_{K})\in\Re^{K+1}$$

Learning rule:

$$\begin{array}{ccc} M(x)=0, & S(x)=1: & \Delta J=-x \\ M(x)=1, & S(x)=0: & \Delta J=x \end{array}$$

$$\Updownarrow$$

$$\Delta J=[2M(x)-1]x$$

Il nuovo insieme $\Omega$ ora consiste di tutti i vettori del tipo $(x_{0}=1,x_{1},...,x_{K})$ con $(x_{1},...,x_{K})$ nell'insieme originale.

• Il primo passo della dimostrazione consiste nel tradurre la separabilità lineare di $M$ nella seguente affermazione:
  
  $$\exists W\in\Re^{K+1}\quad tale\quad che\quad\forall x\in \Omega:\quad M(x)=\theta[W\cdot x]$$
  
  
  e, poichè la funzione a gradini $\theta$ non può avere argomento nullo:
  
  $$\exists\delta>0:\quad tale\quad che\quad \forall x\in\Omega:\quad \vert M\cdot x\vert>\delta$$
  
  
  Per cui il perceptrone insegnante può essere visto come $M(x)=\theta[W\cdot x]$, e poichè le proprietà di linearità ce lo permettono possiamo scegliere $W$ t.c. $\vert W\vert=1$.
• Dato un passo di modifica dei parametri, $J\rightarrow J\prime=J+\Delta J$, valgono le seguenti disuguaglianze:
  
  $$J'\cdot W=J\cdot W+[2M(x)-1]x\cdot W=J\cdot W+[2\theta[x\cdot W]-1]x\cdot W$$
  
  
  
  
  $$= J\cdot W+[s\cdot W]\geq J\cdot W+\delta$$
  
  
  
  

  $$J'\cdot W \geq J\cdot W+\delta$$ (8)

  
  
  e
  
  $$\vert J'\vert^{2}=[J+[2M(x)-1]x]^{2}=J^{2}+2 sgn[W\cdot x]J\cdot x+x^{2}$$
  
  
  
  
  $$\leq J^{2}-2 sgn[W\cdot x]J\cdot x+K+1\leq J^{2}+K+1$$
  
  
  
  

  $$\vert J'\vert^{2}\leq J^{2}+K+1$$ (9)

  
  
  Dopo $n$ modifiche, usando a ripetizione tali disuguaglianze, abbiamo:
  

  $$J(n)\cdot W\geq J(0)\cdot W+n\delta\qquad \vert J(n)\vert^{2}\leq \vert J(0)\vert^{2}+n(K+1)$$ (10)

  
  

• Definiamo ora $\omega=\frac{J\cdot W}{\vert J\vert}$. Per la disuguaglianza di Schwartz $\vert x\cdot y\vert\leq\vert x\vert\vert y\vert$ sappiamo che $\vert\omega\vert\leq\vert W\vert=1$. Dopo $n$ modifiche abbiamo:
  

  $$\omega(n)=\frac{J(n)\cdot W}{\vert J(n)\vert}\geq\frac{J(0)\cdot W+n\delta}{\sqrt{\vert J(0)\vert^{2}+n(K+1)}}$$ (11)

  
  
  Da questo concludiamo che ci può essere solo un numero $n$ finito di modifiche, l'algoritmo ad un certo punto deve fermarsi, per non andare in conflitto con la condizione $\vert\omega(n)\vert\leq1$:
  
  $$\lim_{n\rightarrow\infty}\omega(n)\geq\lim_{n\rightarrow\in... ...)\cdot W+n\delta}{\sqrt{\vert J(0)\vert^{2}+n(K+1)}}=\infty$$
  
  
  Poichè non possono più avvenire modifiche, il sistema deve essere in una situazione stazionaria in cui $M(x)=S(x)\forall x\in\Omega$.

Il teorema di convergenza del perceptrone è potente in quanto dipende solo dalla separabilità di $M$, e , in particolare non dipende dalla distribuzione delle probabilità del vettore input $x$. Ad ogni modo esso non da alcuna informazione sul numero $n$ di modificazioni necessario affinchè si abbia convergenza. Una maggiorazione $n_{max}$ per $n$ si può ottenere controllando dopo quanti passaggi si crea effettivamente il conflitto con la condizione $\vert\omega\vert\leq1$:

$$\frac{[J(0)\cdot W+n_{max}\delta]^{2}}{\vert J(0)^{2}+n_{max}(K+1)}=1$$

Se le condizioni iniziali sono $J(0)=(0,...,0)$, otteniamo:

$$n_{max}=\frac{K+1}{\delta^{2}}$$

Anche se questo risultato non è particolarmente utile dal punto di vista pratico, in quanto non conosciamo $\delta$, è però coerente con l'idea geometrica di separabilità lineare: tanto più è complicata $M$ (in termini di disposizione dei vertici contrassegnati "1" nell'ipercubo), tanto più l'iperpiano "separante" deve essere vicino ai vertici, tanto più $\delta$ sarà piccolo, e quindi servirà un numero maggiore di adattamenti.
Osserviamo che $n$ non è il numero di inputs da dare in pasto al perceptrone affinchè questo impari, ma è il numero di modifiche dei parametri, per cui può sempre accadere che il numero di iterazioni necessarie sia molto più alto, questo dipende anche dalla probabilità o meno di pescare "domande" rilevanti. Questo solleverebbe la questione di come scegliere gli inputs nella fase di apprendimento, essi possono essere presi a caso, oppure tramite una sequenza prefissata. La seconda opzione però rischia di far salire troppo il numero delle iterazioni che sono maggiorate da $2^{K}$, mentre, procedendo a caso il numero dei tentativi è dell'ordine di $K$.

Inserisci i termini di ricerca

Web	www.mkvale.it

Invia modulo di ricerca