TD 4 : Séparation Linéaire

On considère le jeu de données \(S\) suivant :

• \(\mathbf{x}^1 = (1,2,1)\), \(\mathbf{x}^2 = (-1,-1,2)\), \(\mathbf{x}^3 = (-1,2,2)\), \(\mathbf{x}^4 = (-1,0,0)\)
• \(y^1 = 1\), \(y^2 = -1\), \(y^3 = 1\), \(y^4 = -1\).

1. Écrire \(E(\mathbf{w}; S)\) explicitement.
2. Donner \(\Delta E\) en fonction \(w_1,w_2,w_3\).
3. Quelle est la valeur de \(\Delta E\) en \((0,0,0)\).

Pour un jeu de données \(S = (\mathbf{x}^1,y^1), \dots, (\mathbf{x}^n,y^n)\), on rappelle qu’on a:

\((\Delta E)_i = {\partial E \over \partial w_i} = \sum_{j=1}^m 2(\mathbf{w}^T \mathbf{x}^j - y^j) x_i^j\).

On note \(X\) la matrice \(m \times n\) dont la ligne \(i\) est le vecteur \(\mathbf{x}^j\).

1. Donnez une matrice \(A\) de dimension \(1 \times m\) telle que \(\Delta E = AX\).
2. En déduire une implémentation vectorisée en numpy pour calculer \(\Delta E\).

Une fonction Booléenne associe des vecteurs de \(\{0,1\}^n\) à une valeur Booléenne \(\{0,1\}\). On dit qu’une fonction Booléenne \(f\) est linéairement séparable s’il existe \(\mathbf{w}\in \mathbb{R}^{n}\) et \(b \in \mathbb{R}\) tels que pour tout \(\mathbf{x}\in \{0,1\}^n\), \(\mathbf{w}\mathbf{x}+b > 0\) si et seulement si \(f(\mathbf{x}) = 1\).

1. Montrez que les fonctions suivantes sont linéairement séparables :

   1. \(f_m(\mathbf{x})\) qui vaut \(1\) si au moins \(m \leq n\) valeurs de \(\mathbf{x}\) sont égales à \(1\).
   2. \(f_m(\mathbf{x})\) qui vaut \(1\) si au plus \(m \leq n\) valeurs de \(\mathbf{x}\) sont égales à \(1\).
   3. \(f_m(\mathbf{x})=1\) si le nombre de \(1\) dans \(x_1,\dots,x_{n/2}\) est plus grand que dans \(x_{n/2+1}, \dots, x_n\).

2. Montrer que s’il existe \(\mathbf{x}^1,\dots,\mathbf{x}^p\) tels que \(f(\mathbf{x}^j) = 1\) et \(\mathbf{y}^1,\dots,\mathbf{y}^p\) tels que \(f(\mathbf{y}^j) = 0\) et \(\sum_{i=1}^p \mathbf{x}^i = \sum_{j=1}^p \mathbf{y}^j\), alors \(f\) n’est pas linéairement séparable.

3. En déduire que la fonction \(f\) telle que \(f(\mathbf{x})=1\) ssi tous les \(1\) de \(\mathbf{x}\) sont consécutifs n’est pas linéairement séparable.