// svn.txt
// Bruno Bouzy
// 26 novembre 2010

 Comprendre comment marchent les SVN en lisant:

 Corinna Cortes and Vladimir Vapnik, Support-Vector Networks, Machine Learning 1995.

 Exemple du XOR inséparable dans le plan par une droite.

 Fonction noyau z = (1+x*y)^2

 1er exemple
 A(0,0,+) B(1,0,-) C(0,1,-) D(1,1,+)
 M'=(M,noyau(M))
 A'(0, 0, 1) B'(1, 0, 1) C'(0, 1, 1) D'(1, 1, 4)
 Dans l'espace en dimension 3, A', B', C' et D' sont séparables par un plan separateur P
 M+ equivaut a M'+ et M- equivaut a M'-

 Equation du plan séparateur:
 soit J' = (B'+C')/2 = (1/2, 1/2, 1)
 2 vecteurs directeurs de P: A'D' (1,1,3) et B'C' (-1,1,0)
 U vecteur orthogonal a A'D' et B'C' solution de
 x+y+3z=0 et -x+y=0
 d'ou u(1,1,2/3)
 droite delta passant par A'D' et B'C' = J'+lambda*u
 d'ou lambda = -9/22
 I' intersection de A'D' et delta I'(1/11, 1/11, 14/11)
 K' = (I'+J')/2 = (13/44, 13/44, 50/44)
 le plan separateur passe par K'
 z = 1/4 + 3/2 (x+y)

 2eme exemple (plus simple)
 A(-0.5, -0.5, +)      B(0.5, -0.5, -)     C(-0.5, 0.5, -)     D(0.5, 0.5, +)
 A'(-0.5, -0.5, 25/16) B'(0.5, -0.5, 9/16) C'(-0.5, 0.5, 9/16) D'(0.5, 0.5, 25/16)
 I'(0, 0, 25/16)       J'(0, 0, 9/16)      K'(17/16)
 Equation du plan séparateur: z = 17/16

 Ce que fait le programme:
 Il affiche la généralisation des exemples + et - dans le plan.
 Pour chaque point M du plan, M+ equivaut a noyau(M)>planseparateur(M), M- sinon.

 L'idée 1 des SVN est marrante et surtout très simple: 
 On n'arrive pas a séparer simplement les exemples dans l'espace des exemples.
 On plonge les exemples dans un surespace avec une fonction noyau.
 Dans le sur-espace, on sépare simplement avec un perceptron.
 Dans l'espace de départ, un exemple est + (resp -) si le sur-exemple est + dans le sur-espace (resp -)

 Idée analogue pour le Go ?

 on veut savoir si une position est + ou -
 plonger le damier dans un sur-damier avec une fonction noyau
 prendre des exemples et des contre-exemples de parties + et -
 pour une position donnée, la plonger et voir de quel cote elle se trouve.

 espace a 1000 dimensions
 3^1000 buckets
 10^500: impossible

 forme 3x3 + ou - 9 dimensions
 20 dimensions pour le sur-espace
 3^20 = 10^10 de buckets
 6561 exemples
 d'ou plan séparateur
 d'ou fonction immediate pour savoir si le pattern 3x3 est + ou -

 fin de la réflexion.