Vettori linearmente separabili!
Salve a tutti 
Innanzitutto mi scuso se la sezione non è quella più appropriata, se così fosse spostatela dove ritenete più opportuno
Studiando reti neurali mi sono imbattuto in un interessante problema, che geometricamente può essere sintetizzato come segue.
Chiamiamo [tex]\Omega[/tex] l'insieme dei vettori [tex]\vec \omega = (\omega_1, \omega_2, \dots , \omega_N)[/tex] con [tex]\omega_i \in \{-1,1\}[/tex]. In pratica si tratta dei vertici dell'ipercubo in [tex]\mathbb{R}^N[/tex] centrato nell'origine e con le "facce" parallele ai piani definiti da qualsiasi coppia di vettori della base normale.
Definendo i sottoinsiemi [tex]\Omega^+ \subseteq \Omega[/tex] e [tex]\Omega^- = \Omega \setminus \Omega^+[/tex], l'obiettivo è sapere quanti possibili differenti sottoinsiemi [tex]\Omega^+[/tex] (incluso l'insieme vuoto) posso definire in modo tale che [tex]\Omega^+[/tex] e [tex]\Omega^-[/tex] siano linearmente separabili, ovvero tali che esista un iperpiano [tex]U[/tex] il quale divide [tex]\mathbb{R}^N[/tex] in modo tale che in una metà siano presenti tutti e soli i vettori di [tex]\Omega^+[/tex] e nell'altra tutti e soli i vettori di [tex]\Omega^-[/tex].
Per ora l'unica cosa che riesco a pensare è che ci sono molte simmetrie da sfruttare (abbastanza facili da visualizzare per N= 2 o 3, più difficili per un N generico), ma ho bisogno di una spintarella per impostare un ragionamento un pò più generale Più che altro non riesco ad esprimere matematicamente il concetto di "stare da un lato del piano" 
Innanzitutto mi scuso se la sezione non è quella più appropriata, se così fosse spostatela dove ritenete più opportuno
Studiando reti neurali mi sono imbattuto in un interessante problema, che geometricamente può essere sintetizzato come segue.
Chiamiamo [tex]\Omega[/tex] l'insieme dei vettori [tex]\vec \omega = (\omega_1, \omega_2, \dots , \omega_N)[/tex] con [tex]\omega_i \in \{-1,1\}[/tex]. In pratica si tratta dei vertici dell'ipercubo in [tex]\mathbb{R}^N[/tex] centrato nell'origine e con le "facce" parallele ai piani definiti da qualsiasi coppia di vettori della base normale.
Definendo i sottoinsiemi [tex]\Omega^+ \subseteq \Omega[/tex] e [tex]\Omega^- = \Omega \setminus \Omega^+[/tex], l'obiettivo è sapere quanti possibili differenti sottoinsiemi [tex]\Omega^+[/tex] (incluso l'insieme vuoto) posso definire in modo tale che [tex]\Omega^+[/tex] e [tex]\Omega^-[/tex] siano linearmente separabili, ovvero tali che esista un iperpiano [tex]U[/tex] il quale divide [tex]\mathbb{R}^N[/tex] in modo tale che in una metà siano presenti tutti e soli i vettori di [tex]\Omega^+[/tex] e nell'altra tutti e soli i vettori di [tex]\Omega^-[/tex].
Per ora l'unica cosa che riesco a pensare è che ci sono molte simmetrie da sfruttare (abbastanza facili da visualizzare per N= 2 o 3, più difficili per un N generico), ma ho bisogno di una spintarella per impostare un ragionamento un pò più generale
Più che altro non riesco ad esprimere matematicamente il concetto di "stare da un lato del piano"
Risposte
Il problema necessita certamente di un'analisi approfondita, che in questo momento non farò. Mi riservo di pensarci a mente fresca. Mi limito a illustrare una condizione geometrica facile da visualizzare che descrive l'esistenza di un iperpiano separatore.
Avere un iperpiano separatore significa che esiste una funzione affine (ci si può anche ridurre al caso lineare con un po' di accortezza) $f: \RR ^N \to \RR$ che sia (strettamente) positiva su tutti i vertici in $\Omega_+$ e (strettamente) negativa su tutti i vertici in $\Omega_-$. Il luogo degli zeri di questa $f$ affine è l'iperpiano separatore.
Cerchiamo di visualizzare la cosa sul piano. Abbiamo un po' di punti $p_1 ... p_k$ e $q_1 ... q_m$ che riusciamo a separare con una retta. Prendiamo l'equazione cartesiana della retta $A x + B y + C = 0$. La retta è il luogo degli zeri della funzione affine $f(x,y) = Ax + By + C$. La funzione $f$ prenderà valori positivi sui punti da un lato della retta e valori negativi sui punti dall'altro lato.
Avere un iperpiano separatore significa che esiste una funzione affine (ci si può anche ridurre al caso lineare con un po' di accortezza) $f: \RR ^N \to \RR$ che sia (strettamente) positiva su tutti i vertici in $\Omega_+$ e (strettamente) negativa su tutti i vertici in $\Omega_-$. Il luogo degli zeri di questa $f$ affine è l'iperpiano separatore.
Cerchiamo di visualizzare la cosa sul piano. Abbiamo un po' di punti $p_1 ... p_k$ e $q_1 ... q_m$ che riusciamo a separare con una retta. Prendiamo l'equazione cartesiana della retta $A x + B y + C = 0$. La retta è il luogo degli zeri della funzione affine $f(x,y) = Ax + By + C$. La funzione $f$ prenderà valori positivi sui punti da un lato della retta e valori negativi sui punti dall'altro lato.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo