Separabilità lineare

Le operazioni elementari incontrate finora non solo possono essere realizzate con neuroni di McCulloch-Pitts, ma addirittura ne basta uno per ciascuna di esse, ci si chiede quindi se questo è vero per una qualsiasi operazione $M:\{0,1\}^{K}\rightarrow\{0,1\}$. Per $K=1$ basta controllare tutte le possibilità per vedere che possiamo sempre costruire un neurone $S(x)=\theta\left[Jx-U\right]$ che realizza l'operazione:

$x$	$M_{a}(x)$	$\theta[-1]$	$M_{b}(x)$	$\theta[-x+1/2]$	$M_{c}(x)$	$\theta[x-1/2]$	$M_{d}(x)$	$\theta[1]$
0	0	0	1	1	0	0	1	1
1	0	0	0	0	1	1	1	1

Per $K>1$ invece la risposta è no, lo mostriamo con un esempio per $K=2$ che può essere utilizzato per costruire controesempi per $K>2$. L'operazione di cui parliamo è XOR, ovvero l'OR esclusivo:

$x$	$y$	XOR(x,y)
0	0	0
0	1	1
1	0	1
1	1	0

Proposizione:Non esiste alcuna terna di numeri $\{J_{x},J_{y},U\}$ tali che:

$$\theta\left[J_{x}x+J_{y}y-U\right]=XOR(x,y)\qquad\forall(x,y)\in\{0,1\}^{2}$$

Dimostrazione:

Supponiamo che invece una tale terna esista, allora:

$(x,y)=(0,1):\quad J_{y}-U>0\qquad\Rightarrow J_{y}>U$
$(x,y)=(1,0):\quad J_{x}-U>0\qquad\Rightarrow J_{x}>U$
$(x,y)=(1,1):\quad J_{x}+J_{y}-U<0\qquad\Rightarrow J_{x}+J_{y}<U$

Le tre condizioni, dettate dalla tavola di verità di XOR, non possono essere tutte verificate allo stesso tempo, da cui segue la validità della proposizione. Per $K>2$ possiamo costruire esempi simili applicando XOR alle prime due variabili d'input:

$$M:\{0,1\}^{K}\rightarrow\{0,1\}\qquad \left(x_{1},...x_{K})=XOR(x_{1},x_{2})\right)$$

Di conseguenza sappiamo che $\forall K\geq 2 \exists$ operazioni che non possono essere realizzate con un singolo neurone di McCulloch-Pitts. Per analizzare il problema e capire quali operazioni possono essere realizzate con un singolo neurone possiamo dare un'interpretazione un po' più geometrica della situazione. Tanto per cominciare, il numero totale delle operazioni è:

$$\char93 \{M:\{0,1\}^{K}\rightarrow\{0,1\}\}=2^{2^{K}}$$

L'insieme $\{0,1\}_{K}$ dei possibili vettori input corrisponde ai vertici dell'ipercubo unitario in $\Re^{K}$, mentre il neurone che esegue l'operazione

$$S:\{0,1\}^{K}\rightarrow\{0,1\}\qquad S(x)=\theta\left[\sum^{K}_{k=1}J_{k}x_{k}-U\right]$$

può essere interpretato come operatore che divide $\Re^{K}$ in due sottospazi separati dall'iperpiano $\sum^{K}_{k=1}J_{k}x_{k}=U$. L'informazione che otteniamo dal neurone, quindi, è semplicemente in quale sottospazio di $\Re^{K}$ si trova un dato vettore input $x\in\{0,1\}^{K}$. Questa suddivisione in sottospazi, in realtà, corrisponde a quella già introdotta precedentemente dell'insieme $\Omega\subseteq\{0,1\}^{K}$ in $\Omega^{+}$ e $\Omega^{-}$: l'insieme dei vertici dell'ipercubo per cui vale $S(x)=1$ corrisponde ad $\Omega^{+}$, mentre l'insieme dei vertici su cui $S$ vale $0$ è $\Omega^{-}$. Poichè ciascuna delle $2^{2^{K}}$ operazioni è univocamente identificata dall'insieme $\Omega^{+}$, è possibile rappresentare ciascuna di esse disegnando l'ipercubo, colorando di nero i vertici appartenenti ad $\Omega^{+}$, e di bianco quelli appartenenti ad $\Omega^{-}$.
Per $K=1$ l'ipercubo è un segmento con 2 vertici, 4 sono le operazioni $M:\{0,1\}\rightarrow\{0,1\}$ possibili, ovvero 4 modi di colorare i vertici:

$$K=1:\qquad x\in\{0,1\},\qquad \begin{array}{c} \bullet:\... ...x)=1 \\ \circ:\quad x\in\Omega^{-},\quad M(x)=0 \end{array}$$

$$\circ--\circ\qquad\bullet--\circ\qquad\circ--\bullet\qquad\bullet--\bullet$$

Per $K=2$ l'ipercubo è un quadrato e ci sono $s^{2^{2}}=16$ operazioni $M:\{0,1\}^{2}\rightarrow\{0,1\}$, 16 modi di colorare i quattro vertici del quadrato:

$$K=2:\qquad x\in\{0,1\}^{2},\qquad \begin{array}{c} \bull... ...=1 \\ \circ:\quad x\in\Omega^{-},\quad M(x)=0 \end{array}$$

$\circ\quad\circ \qquad \circ\quad\circ \qquad \circ\quad\circ \qquad \bullet\quad\circ$
$\circ\quad\circ \qquad \bullet\quad\circ \qquad \circ\quad\bullet \qquad \circ\quad\circ$

$\circ\quad\bullet \qquad \circ\quad\circ \qquad \bullet\quad\circ \qquad \circ\quad\bullet$
$\circ\quad\circ \qquad \bullet\quad\bullet \qquad \bullet\quad\circ \qquad \bullet\quad\circ$

$\bullet\quad\circ \qquad \circ\quad\bullet \qquad \bullet\quad\bullet \qquad \bullet\quad\circ$
$\circ\quad\bullet \qquad \circ\quad\bullet \qquad \circ\quad\circ \qquad \bullet\quad\bullet$

$\circ\quad\bullet \qquad \bullet\quad\bullet \qquad \bullet\quad\bullet \qquad \bullet\quad\bullet$
$\bullet\quad\bullet \qquad \bullet\quad\circ \qquad \circ\quad\bullet \qquad \bullet\quad\bullet$

Per $K=3$ l'ipercubo è un cubo, con 8 vertici, per cui ci sono $2^{2^{3}}=256$ operazioni $M:\{0,1\}^{3}\rightarrow\{0,1\}$, 256 modi di colorare i vertici del cubo.
Ricordandoci che il neurone di McCulloch-Pitts divide $\Re^{K}$ in due semispazi con un iperpiano, risulta chiaro che, di tutte le operazioni elencate negli esempi, esso può eseguire solo quelle per cui $\Omega^{+}$ ed $\Omega^{-}$ possono essere separati con un singolo iperpiano $x\cdot J=U$. Operazioni che godono di tale caratteristica si chiamano linearmente separabili.
Rivedendo gli esempi sopra rappresentati appare chiaro come per $K=1$ sia sempre possibile separare i vertici neri da quelli bianchi con un singolo iperpiano, mentre per $K=2$ esistono due operazioni per cui questo non è possibile:

$\bullet\quad\circ \qquad \circ\quad\bullet$
$\circ\quad\bullet \qquad \bullet\quad\circ$

Le due operazioni in questione sono esattamente $XOR$ e $\neg XOR$:

$x$	$x$	$M_{a}(x,y)$
0	0	0
0	1	1
1	0	1
1	1	0

$x$	$y$	$M_{b}(x,y)$
0	0	1
0	1	0
1	0	0
1	1	1

Nel prossimo paragrafo vedremo come si possono eseguire tali operazioni, utilizzando più di un neurone di McCulloch-Pitts.

Inserisci i termini di ricerca

Web	www.mkvale.it

Invia modulo di ricerca