Separabilidad lineal

En geometría euclidiana , la separabilidad lineal es una propiedad de dos conjuntos de puntos . Esto se visualiza más fácilmente en dos dimensiones (el plano euclidiano ) imaginando que un conjunto de puntos es azul y el otro, rojo. Estos dos conjuntos son linealmente separables si existe al menos una línea en el plano con todos los puntos azules a un lado y todos los puntos rojos al otro. Esta idea se generaliza inmediatamente a espacios euclidianos de dimensiones superiores si la línea se reemplaza por un hiperplano .

El problema de determinar si un par de conjuntos son linealmente separables y encontrar un hiperplano separador en caso afirmativo surge en diversas áreas. En estadística y aprendizaje automático , la clasificación de ciertos tipos de datos es un problema para el cual existen buenos algoritmos basados ​​en este concepto.

Dejar${\displaystyle X\subset \mathbb {R} ^{d}}$ser un conjunto de${\displaystyle m}$puntos y${\displaystyle Y\subset \mathbb {R} ^{d}}$ser un conjunto de${\displaystyle n}$puntos en un${\displaystyle d}$Espacio euclidiano de -dimensiones .${\displaystyle X}$y${\displaystyle Y}$son linealmente separables si pueden ser "separados" por un${\displaystyle d}$hiperplano de dimensión tal que cada punto en${\displaystyle X}$se encuentra en un lado del hiperplano y cada punto en${\displaystyle Y}$yace al otro lado.

El hiperplano separador está compuesto por puntos${\displaystyle \left\{z\in \mathbb {R} ^{d}:w^{\top }z+k=0\right\}}$, dónde${\displaystyle w\in \mathbb {R} ^{d}}$es el vector normal al hiperplano y${\displaystyle k\in \mathbb {R} }$es un desplazamiento escalar .${\displaystyle X}$y${\displaystyle Y}$son linealmente separables si existe un vector normal.${\displaystyle w}$y un desplazamiento escalar${\displaystyle k}$de tal manera que cada punto${\displaystyle x\in X}$Satisface${\displaystyle w^{\top }x+k>0}$y cada punto${\displaystyle y\in Y}$Satisface${\displaystyle w^{\top }y+k<0}$, o cada punto${\displaystyle x\in X}$Satisface${\displaystyle w^{\top }x+k<0}$y cada punto${\displaystyle y\in Y}$Satisface${\displaystyle w^{\top }y+k>0}$.

De forma equivalente, dos conjuntos son linealmente separables precisamente cuando sus respectivas envolturas convexas son disjuntas (coloquialmente, no se superponen). ^{[ 1 ]}

Tres puntos no colineales en dos clases ('+' y '-') siempre son linealmente separables en dos dimensiones. Esto se ilustra con los tres ejemplos de la siguiente figura (el caso de todos los puntos '+' no se muestra, pero es similar al caso de todos los puntos '-'):

Sin embargo, no todos los conjuntos de cuatro puntos, ni siquiera tres colineales, son linealmente separables en dos dimensiones. El siguiente ejemplo requeriría dos líneas rectas y, por lo tanto, no es linealmente separable:

Nótese que tres puntos que son colineales y de la forma "+ ⋅⋅⋅ — ⋅⋅⋅ +" tampoco son linealmente separables.

Dejar${\displaystyle T(N,K)}$Sea el número de maneras de separar linealmente N puntos (en posición general) en K dimensiones, entonces ^{[ 2 ]}$${\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}}\right)&K<N\end{array}}\right.}$$Cuando K es grande,${\displaystyle T(N,K)/2^{N}}$está muy cerca de uno cuando${\displaystyle N\leq 2K}$, pero muy cerca de cero cuando${\displaystyle N>2K}$En otras palabras, una unidad de perceptrón puede memorizar casi con certeza una asignación aleatoria de etiquetas binarias en N puntos cuando${\displaystyle N\leq 2K}$pero casi con toda seguridad no cuando${\displaystyle N>2K}$.

Una función booleana en n variables puede considerarse como la asignación de 0 o 1 a cada vértice de un hipercubo booleano en n dimensiones. Esto da como resultado una división natural de los vértices en dos conjuntos. Se dice que la función booleana es linealmente separable si estos dos conjuntos de puntos son linealmente separables. El número de funciones booleanas distintas es${\displaystyle 2^{2^{n}}}$donde n es el número de variables pasadas a la función. ^{[ 3 ]}

Estas funciones también se denominan lógica de umbral lineal o perceptrones . La teoría clásica se resume en ^{[ 4 ]} , como afirma Knuth. ^{[ 5 ]}

El número de funciones booleanas que son linealmente separables solo se conoce con exactitud hasta el${\displaystyle n=9}$caso, pero el orden de magnitud se conoce con bastante exactitud: tiene límite superior${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$y límite inferior${\displaystyle 2^{n^{2}-n\log _{2}nO(n)}}$. ^{[ 6 ]}

Es co-NP-completo decidir si una función booleana dada en forma normal disyuntiva o conjuntiva es linealmente separable. ^{[ 6 ]}

Una puerta lógica de umbral lineal es una función booleana definida por${\displaystyle n}$pesos${\displaystyle w_{1},\dots,w_{n}}$y un umbral${\displaystyle \theta }$. Se necesita${\displaystyle n}$entradas binarias${\displaystyle x_{1},\dots ,x_{n}}$y produce 1 si${\displaystyle \sum _{i}w_{i}x_{i}>\theta }$y en caso contrario, la salida es 0.

Para cualquier fijo${\displaystyle n}$, debido a que solo hay un número finito de funciones booleanas que pueden ser calculadas por una unidad lógica de umbral, es posible establecer todas${\displaystyle w_{1},\dots,w_{n},\theta}$ser números enteros.${\displaystyle W(n)}$ser el número más pequeño${\displaystyle W}$de tal manera que cada posible función umbral real de${\displaystyle n}$Las variables se pueden realizar utilizando ponderaciones enteras de valor absoluto.${\displaystyle \leq W}$. Se sabe que ^{[ 8 ]}$${\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)}$$Véase ^{[ 9 ] : Sección 11.10} para una revisión de la literatura.

La clasificación de datos es una tarea común en el aprendizaje automático . Supongamos que se nos dan algunos puntos de datos, cada uno perteneciente a uno de dos conjuntos, y deseamos crear un modelo que decida a qué conjunto pertenecerá un nuevo punto de datos. En el caso de las máquinas de vectores de soporte , un punto de datos se considera un vector p -dimensional (una lista de p números), y queremos saber si podemos separar dichos puntos con un hiperplano ( p - 1)-dimensional . Esto se denomina clasificador lineal . Existen muchos hiperplanos que podrían clasificar (separar) los datos. Una opción razonable como el mejor hiperplano es aquel que representa la mayor separación, o margen, entre los dos conjuntos. Por lo tanto, elegimos el hiperplano de manera que la distancia desde este al punto de datos más cercano en cada lado sea máxima. Si existe tal hiperplano, se conoce como hiperplano de margen máximo y el clasificador lineal que define se conoce como clasificador de margen máximo .  

Más formalmente, dados algunos datos de entrenamiento${\displaystyle {\mathcal {D}}}$, un conjunto de n puntos de la forma

${\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}$

donde y _i es 1 o −1, lo que indica el conjunto al que pertenece el punto${\displaystyle \mathbf {x} _{i}}$pertenece. Cada${\displaystyle \mathbf {x} _{i}}$es un vector real p -dimensional . Queremos encontrar el hiperplano de margen máximo que divide los puntos que tienen${\displaystyle y_{i}=1}$de aquellos que tienen${\displaystyle y_{i}=-1}$Cualquier hiperplano puede escribirse como el conjunto de puntos${\displaystyle \mathbf {x} }$satisfactorio

${\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,}$

dónde${\displaystyle \cdot }$denota el producto escalar y${\displaystyle {\mathbf {w} }}$El vector normal (no necesariamente normalizado) al hiperplano. El parámetro${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$determina el desplazamiento del hiperplano desde el origen a lo largo del vector normal${\displaystyle {\mathbf {w} }}$.

Si los datos de entrenamiento son linealmente separables, podemos seleccionar dos hiperplanos de tal manera que separen los datos y no haya puntos entre ellos, y luego intentar maximizar su distancia.

• Agrupamiento (estadística)
• Teorema de separación de hiperplanos
• Teorema de Kirchberger
• Perceptrón
• Dimensión Vapnik-Chervonenkis