séparabilité linéaire

En géométrie euclidienne , la séparabilité linéaire est une propriété de deux ensembles de points . On la visualise aisément en deux dimensions (le plan euclidien ) en imaginant un ensemble de points colorés en bleu et l'autre en rouge. Ces deux ensembles sont linéairement séparables s'il existe au moins une droite dans le plan qui regroupe tous les points bleus d'un côté et tous les points rouges de l'autre. Cette idée se généralise immédiatement aux espaces euclidiens de dimension supérieure si l'on remplace la droite par un hyperplan .

Le problème consistant à déterminer si deux ensembles sont linéairement séparables et, le cas échéant, à trouver un hyperplan de séparation, se pose dans plusieurs domaines. En statistique et en apprentissage automatique , la classification de certains types de données est un problème pour lequel il existe de bons algorithmes basés sur ce concept.

Définition mathématique

Laisser ${\displaystyle X\subset \mathbb {R} ^{d <semantics><mrow><mstyle><mi>X</mi><mo>⊂</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>d</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle X\subset \mathbb {R} ^{d}}</annotation></semantics></math><img src=$ ${\displaystyle m <semantics><mrow><mstyle><mi>m</mi></mstyle></mrow><annotation>{\displaystyle m}</annotation></semantics></math><img src=$ ${\displaystyle Y\subset \mathbb {R} ^{d <semantics><mrow><mstyle><mi>Y</mi><mo>⊂</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>d</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle Y\subset \mathbb {R} ^{d}}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle X <semantics><mrow><mstyle><mi>X</mi></mstyle></mrow><annotation>{\displaystyle X}</annotation></semantics></math><img src=$ ${\displaystyle Y <semantics><mrow><mstyle><mi>Y</mi></mstyle></mrow><annotation>{\displaystyle Y}</annotation></semantics></math><img src=$ linéairement séparables si elles peuvent être « séparées » par un ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle X <semantics><mrow><mstyle><mi>X</mi></mstyle></mrow><annotation>{\displaystyle X}</annotation></semantics></math><img src=$ ${\displaystyle Y <semantics><mrow><mstyle><mi>Y</mi></mstyle></mrow><annotation>{\displaystyle Y}</annotation></semantics></math><img src=$

L'hyperplan de séparation est composé de points ${\displaystyle \left\{z\in \mathbb {R} ^{d}:w^{ op }z+k=0 ight\ <semantics><mrow><mstyle><mrow><mo>{</mo><mrow><mi>z</mi><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>d</mi></mrow></msup><mo>:</mo><msup><mi>w</mi><mrow><mi>⊤</mi></mrow></msup><mi>z</mi><mo>+</mo><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mo>}</mo></mrow></mstyle></mrow><annotation>{\displaystyle \left\{z\in \mathbb {R} ^{d}:w^{ op }z+k=0 ight\}}</annotation></semantics></math><img src=$ ${\displaystyle w\in \mathbb {R} ^{d <semantics><mrow><mstyle><mi>w</mi><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>d</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle w\in \mathbb {R} ^{d}}</annotation></semantics></math><img src=$ ${\displaystyle k\in \mathbb {R} <semantics><mrow><mstyle><mi>k</mi><mo>∈</mo><mrow><mi>R</mi></mrow></mstyle></mrow><annotation>{\displaystyle k\in \mathbb {R} }</annotation></semantics></math><img src=$ ${\displaystyle X <semantics><mrow><mstyle><mi>X</mi></mstyle></mrow><annotation>{\displaystyle X}</annotation></semantics></math><img src=$ ${\displaystyle Y <semantics><mrow><mstyle><mi>Y</mi></mstyle></mrow><annotation>{\displaystyle Y}</annotation></semantics></math><img src=$ ${\displaystyle w <semantics><mrow><mstyle><mi>w</mi></mstyle></mrow><annotation>{\displaystyle w}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle x\in X <semantics><mrow><mstyle><mi>x</mi><mo>∈</mo><mi>X</mi></mstyle></mrow><annotation>{\displaystyle x\in X}</annotation></semantics></math><img src=$ $0 w^{⊤} x + k > 0$ 0 et chaque point ${\displaystyle y\in Y <semantics><mrow><mstyle><mi>y</mi><mo>∈</mo><mi>Y</mi></mstyle></mrow><annotation>{\displaystyle y\in Y}</annotation></semantics></math><img src=$ ${\displaystyle w^{ op }y+k<0 <semantics><mrow><mstyle><msup><mi>w</mi><mrow><mi>⊤</mi></mrow></msup><mi>y</mi><mo>+</mo><mi>k</mi><mo><</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle w^{ op }y+k<0}</annotation></semantics></math><img src=$ ${\displaystyle x\in X <semantics><mrow><mstyle><mi>x</mi><mo>∈</mo><mi>X</mi></mstyle></mrow><annotation>{\displaystyle x\in X}</annotation></semantics></math><img src=$ ${\displaystyle w^{ op }x+k<0 <semantics><mrow><mstyle><msup><mi>w</mi><mrow><mi>⊤</mi></mrow></msup><mi>x</mi><mo>+</mo><mi>k</mi><mo><</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle w^{ op }x+k<0}</annotation></semantics></math><img src=$ ${\displaystyle y\in Y <semantics><mrow><mstyle><mi>y</mi><mo>∈</mo><mi>Y</mi></mstyle></mrow><annotation>{\displaystyle y\in Y}</annotation></semantics></math><img src=$ $0 w^{⊤} y + k > 0$ 0 .

De manière équivalente, deux ensembles sont linéairement séparables précisément lorsque leurs enveloppes convexes respectives sont disjointes (en langage courant, ne se chevauchent pas).

Exemples

Trois points non colinéaires appartenant à deux classes (« + » et « - ») sont toujours linéairement séparables en deux dimensions. Ceci est illustré par les trois exemples de la figure suivante (le cas où tous les points sont « + » n'est pas représenté, mais il est similaire au cas où tous les points sont « - ») :

Cependant, tous les ensembles de quatre points, et notamment les ensembles de trois points alignés, ne sont pas linéairement séparables en deux dimensions. L'exemple suivant nécessiterait deux segments de droite et n'est donc pas linéairement séparable :

Remarquez que trois points qui sont colinéaires et de la forme "+ ⋅⋅⋅ — ⋅⋅⋅ +" ne sont pas non plus linéairement séparables.

Nombre de séparations linéaires

Laisser ${\displaystyle T(N,K) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>N</mi><mo>,</mo><mi>K</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(N,K)}</annotation></semantics></math><img src=$ N points (en position générale) dans K dimensions, alors ${\displaystyle T(N,K)=\left\{{\begin{array}{cc}2^{N}&K\geq N\\2\sum _{k=0}^{K-1}\left({\begin{array}{c}N-1\\k\end{array}} ight)&K<N\end{array}} ight. <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>N</mi><mo>,</mo><mi>K</mi><mo>)</mo><mo>=</mo><mrow><mo>{</mo><mrow><mtable><mtr><mtd><msup><mn>2</mn><mrow><mi>N</mi></mrow></msup></mtd><mtd><mi>K</mi><mo>≥</mo><mi>N</mi></mtd></mtr><mtr><mtd><mn>2</mn><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>−</mo><mn>1</mn></mrow></munderover><mrow><mo>(</mo><mrow><mtable><mtr><mtd><mi>N</mi><mo>−</mo><mn>1</mn></mtd></mtr><mtr><mtd><mi>k</mi></mtd></mtr></mtable></mrow><mo>)</mo></mrow></mtd><mtd><mi>K</mi><mo><</mo><mi>N</mi></mtd></mtr></mtable></mrow><mo></mo></mrow></mstyle></mrow><annotation>{\displaystyle T(N,K)=\left\{{\begin{array}{cc}2^{N}&K\geq N\\2\sum _{k=0}^{K-1}\left({\begin{array}{c}N-1\\k\end{array}} ight)&K<N\end{array}} ight.}</annotation></semantics></math><img src=$ K est grand, ${\displaystyle T(N,K)/2^{N <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>N</mi><mo>,</mo><mi>K</mi><mo>)</mo><mrow><mo>/</mo></mrow><msup><mn>2</mn><mrow><mi>N</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle T(N,K)/2^{N}}</annotation></semantics></math><img src=$ ${\displaystyle N\leq 2K <semantics><mrow><mstyle><mi>N</mi><mo>≤</mo><mn>2</mn><mi>K</mi></mstyle></mrow><annotation>{\displaystyle N\leq 2K}</annotation></semantics></math><img src=$ $2K N > 2 K$ 2K En d'autres termes, une unité de perceptron peut presque certainement mémoriser une attribution aléatoire d'étiquettes binaires sur N points lorsque ${\displaystyle N\leq 2K <semantics><mrow><mstyle><mi>N</mi><mo>≤</mo><mn>2</mn><mi>K</mi></mstyle></mrow><annotation>{\displaystyle N\leq 2K}</annotation></semantics></math><img src=$ $2K N > 2 K$ 2K .

Séparabilité linéaire des fonctions booléennes à n variables

Une fonction booléenne à n variables peut être vue comme l'attribution de 0 ou de 1 à chaque sommet d'un hypercube booléen à n dimensions. Ceci définit une division naturelle des sommets en deux ensembles. La fonction booléenne est dite linéairement séparable si ces deux ensembles de points le sont également. Le nombre de fonctions booléennes distinctes est ${\displaystyle 2^{2^{n <semantics><mrow><mstyle><msup><mn>2</mn><mrow><msup><mn>2</mn><mrow><mi>n</mi></mrow></msup></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{2^{n}}}</annotation></semantics></math><img src=$ n est le nombre de variables passées à la fonction.

Ces fonctions sont également appelées logique à seuil linéaire, ou perceptrons . La théorie classique est résumée dans , comme l'affirme Knuth.

Le nombre de fonctions booléennes linéairement séparables n'est connu avec exactitude qu'à un degré près. ${\displaystyle n=9 <semantics><mrow><mstyle><mi>n</mi><mo>=</mo><mn>9</mn></mstyle></mrow><annotation>{\displaystyle n=9}</annotation></semantics></math><img src=$ ${\displaystyle 2^{n^{2}-n\log _{2}n+O(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>−</mo><mi>n</mi><msub><mi>enregistrer</mi><mrow><mn>2</mn></mrow></msub><mo>⁡</mo><mi>n</mi><mo>+</mo><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}</annotation></semantics></math><img src=$ ${\displaystyle 2^{n^{2}-n\log _{2}n-O(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>−</mo><mi>n</mi><msub><mi>enregistrer</mi><mrow><mn>2</mn></mrow></msub><mo>⁡</mo><mi>n</mi><mo>−</mo><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{n^{2}-n\log _{2}nO(n)}}</annotation></semantics></math><img src=$

Il est co-NP-complet de décider si une fonction booléenne donnée sous forme normale disjonctive ou conjonctive est linéairement séparable.

Logique de seuil

Une porte logique à seuil linéaire est une fonction booléenne définie par ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle w_{1},\dots ,w_{n <semantics><mrow><mstyle><msub><mi>w</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>w</mi><mrow><mi>n</mi></mrow></msub></mstyle></mrow><annotation>{ displaystyle w_ {1}, dots, w_ {n}}</annotation></semantics></math><img src=$ ${\displaystyle heta <semantics><mrow><mstyle><mi>θ</mi></mstyle></mrow><annotation>{\displaystyle heta }</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle x_{1},\dots ,x_{n <semantics><mrow><mstyle><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle x_{1},\dots ,x_{n}}</annotation></semantics></math><img src=$ $heta \sum_{je} w_{je} x_{je} > θ$ heta , et sinon renvoie 0.

Pour toute valeur fixe ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle w_{1},\dots ,w_{n}, heta <semantics><mrow><mstyle><msub><mi>w</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>w</mi><mrow><mi>n</mi></mrow></msub><mo>,</mo><mi>θ</mi></mstyle></mrow><annotation>{ displaystyle w_ {1}, dots, w_ {n}, theta}</annotation></semantics></math><img src=$ ${\displaystyle W(n) <semantics><mrow><mstyle><mi>W</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle W(n)}</annotation></semantics></math><img src=$ ${\displaystyle W <semantics><mrow><mstyle><mi>W</mi></mstyle></mrow><annotation>{\displaystyle W}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle \leq W <semantics><mrow><mstyle><mo>≤</mo><mi>W</mi></mstyle></mrow><annotation>{\displaystyle \leq W}</annotation></semantics></math><img src=$ ${\displaystyle {\frac {1}{2}}n\log n-2n+o(n)\leq \log _{2}W(n)\leq {\frac {1}{2}}n\log n-n+o(n) <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow><mi>n</mi><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>−</mo><mn>2</mn><mi>n</mi><mo>+</mo><mi>o</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>≤</mo><msub><mi>enregistrer</mi><mrow><mn>2</mn></mrow></msub><mo>⁡</mo><mi>W</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>≤</mo><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow><mi>n</mi><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>−</mo><mi>n</mi><mo>+</mo><mi>o</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1}{2}}n\log n-2n+o(n)\leq \log _{2}W(n)\leq {\frac {1}{2}}n\log n-n+o(n)}</annotation></semantics></math><img src=$

Machines à vecteurs de support

1) dimensions . On parle alors de classificateur linéaire . De nombreux hyperplans peuvent permettre de classifier (séparer) les données. Un choix judicieux, considéré comme le meilleur hyperplan, est celui qui représente la plus grande séparation, ou marge, entre les deux ensembles. On choisit donc l'hyperplan de manière à maximiser la distance entre celui-ci et le point de données le plus proche de chaque côté. Si un tel hyperplan existe, il est appelé hyperplan à marge maximale , et le classificateur linéaire qu'il définit est appelé classificateur à marge maximale .

Plus formellement, étant donné certaines données d'entraînement ${\displaystyle {\mathcal {D <semantics><mrow><mstyle><mrow><mrow><mi>D</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathcal {D}}}</annotation></semantics></math><img src=$ n points de la forme

{\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\} ight\}_{i=1}^{n <semantics><mrow><mstyle><mrow><mrow><mi>D</mi></mrow></mrow><mo>=</mo><msubsup><mrow><mo>{</mo><mrow><mo>(</mo><msub><mrow><mi>x</mi></mrow><mrow><mi>je</mi></mrow></msub><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>∣</mo><msub><mrow><mi>x</mi></mrow><mrow><mi>je</mi></mrow></msub><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>p</mi></mrow></msup><mo>,</mo><mspace></mspace><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>∈</mo><mo>{</mo><mo>−</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo>}</mo></mrow><mo>}</mo></mrow><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\} ight\}_{i=1}^{n}}</annotation></semantics></math></span><img src=

où le y _i vaut soit 1, soit −1, indiquant l'ensemble auquel appartient le point ${\displaystyle \mathbf {x} _{i <semantics><mrow><mstyle><msub><mrow><mi>x</mi></mrow><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathbf {x} _{i}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {x} _{i <semantics><mrow><mstyle><msub><mrow><mi>x</mi></mrow><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathbf {x} _{i}}</annotation></semantics></math><img src=$ p . On cherche l'hyperplan à marge maximale qui divise les points ayant ${\displaystyle y_{i}=1 <semantics><mrow><mstyle><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle y_{i}=1}</annotation></semantics></math><img src=$ ${\displaystyle y_{i}=-1 <semantics><mrow><mstyle><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>−</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle y_{i}=-1}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {x} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {x} }</annotation></semantics></math><img src=$

{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0, <semantics><mrow><mstyle><mrow><mi>w</mi></mrow><mo>⋅</mo><mrow><mi>x</mi></mrow><mo>−</mo><mi>b</mi><mo>=</mo><mn>0</mn><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,}</annotation></semantics></math></span><img src=

où ${\displaystyle \cdot <semantics><mrow><mstyle><mo>⋅</mo></mstyle></mrow><annotation>{\displaystyle \cdot }</annotation></semantics></math><img src=$ ${\displaystyle {\mathbf {w} <semantics><mrow><mstyle><mrow><mrow><mi>w</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathbf {w} }}</annotation></semantics></math><img src=$ ${\displaystyle { frac {b}{\|\mathbf {w} \| <semantics><mrow><mstyle><mrow><mstyle><mfrac><mi>b</mi><mrow><mo>‖</mo><mrow><mi>w</mi></mrow><mo>‖</mo></mrow></mfrac></mstyle></mrow></mstyle></mrow><annotation>{\displaystyle { frac {b}{\|\mathbf {w} \|}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathbf {w} <semantics><mrow><mstyle><mrow><mrow><mi>w</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathbf {w} }}</annotation></semantics></math><img src=$

Si les données d'entraînement sont linéairement séparables, nous pouvons sélectionner deux hyperplans de telle sorte qu'ils séparent les données et qu'il n'y ait aucun point entre eux, puis essayer de maximiser leur distance.