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) pensando en un conjunto de puntos de color azul y el otro conjunto de puntos de color rojo. Estos dos conjuntos son linealmente separables si existe al menos una línea en el plano con todos los puntos azules en un lado de la línea y todos los puntos rojos en el otro lado. 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 es linealmente separable y encontrar un hiperplano de separación si lo es, surge en varias áreas. En estadística y aprendizaje automático, clasificar ciertos tipos de datos es un problema para el que existen buenos algoritmos que se basan en este concepto.

Definición matemática

Vamos ${displaystyle X_{0}$ y ${displaystyle X_{1}$ ser dos conjuntos de puntos en un n-dimensional Espacio euclidiano. Entonces... ${displaystyle X_{0}$ y ${displaystyle X_{1}$ son linealmente separable si existe n + 1 números reales ${displaystyle...$, tal que cada punto ${displaystyle xin X_{0}$ satisfizo ${displaystyle sum ¿Qué?$ y cada punto ${displaystyle xin X_{1}$ satisfizo ${displaystyle sum ¿Qué?$, donde ${displaystyle x_{i}}$ es ${displaystyle i}$-to componente de ${displaystyle x}$.

De manera equivalente, dos conjuntos son linealmente separables precisamente cuando sus respectivos cascos convexos están separados (coloquialmente, no se superponen).

En 2D simple, también se puede imaginar que el conjunto de puntos bajo una transformación lineal colapsa en una línea, en la que existe un valor, k, mayor que el cual caerá un conjunto de puntos y menor que el cual. el otro conjunto de puntos cae.

Ejemplos

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 '+' no se muestra, pero es similar al caso de todos '-'):

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

Observe que tres puntos que son colineales y de la forma "+ ⋅⋅⋅ — ⋅⋅⋅ +" Tampoco son linealmente separables.

Separabilidad lineal de funciones booleanas en n variables

Una función booleana en n variables se pueden considerar como una asignación 0 o 1 a cada vértice de un hipercubo booleano en n dimensiones. Esto da una división natural de los vértices en dos conjuntos. Se dice que la función booleana es linealmente separable siempre que estos dos conjuntos de puntos sean linealmente separables. El número de diferentes funciones booleanas es ${displaystyle 2^{2^{n}}$Donde n es el número de variables pasadas en la función.

Máquinas de vectores de soporte

Clasificar datos es una tarea común en el aprendizaje automático. Supongamos que se dan algunos puntos de datos, cada uno de los cuales pertenece a uno de dos conjuntos, y deseamos crear un modelo que decida en qué conjunto estará un nuevo punto de datos. En el caso de máquinas de vectores de soporte, un punto de datos se ve como un vector p-dimensional (una lista de números p) y queremos saber si podemos separar dichos puntos con un ( hiperplano p − 1)-dimensional. A esto se le llama clasificador lineal. Hay muchos hiperplanos que podrían clasificar (separar) los datos. Una elección razonable como mejor hiperplano es aquella que representa la mayor separación o margen entre los dos conjuntos. Entonces, elegimos el hiperplano de modo que se maximice la distancia desde él hasta el punto de datos más cercano en cada lado. Si dicho hiperplano existe, 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, dado algunos datos de capacitación ${displaystyle {fnMithcal}}$, un conjunto de n puntos de la forma

${displaystyle {mathcal {}=left{ {x} _{i},y_{i})mid mathbf {x} _{i}in mathbb {R} ^{p},,y_{i}in {-1,1}derecho}$

Donde Sí._i es 1 o −1, indicando el conjunto al cual el punto ${displaystyle mathbf {x} _{i}$ pertenece. Cada uno ${displaystyle mathbf {x} _{i}$ es un p- vector real dimensional. Queremos encontrar el hiperplano máximo-margin que divide los puntos teniendo ${displaystyle Y...$ de los que tienen ${displaystyle Y...$. Cualquier hiperplano se puede escribir como el conjunto de puntos ${displaystyle mathbf {x}$ satisfacción

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

Donde ${displaystyle cdot }$ denota el producto del punto y ${displaystyle {fnh}$ el (no necesariamente normalizado) vector normal al hiperplano. El parámetro ${displaystyle {tfrac {}{fnMitbf} {}}$ determina la compensación del hiperplano del origen a lo largo del vector normal ${displaystyle {fnh}$.

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