Separabilidad lineal - Linear separability

La existencia de una línea que separa los dos tipos de puntos significa que los datos son linealmente separables.

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 ) al pensar en un conjunto de puntos como de color azul y el otro conjunto de puntos como 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 es reemplazada por un hiperplano .

El problema de determinar si un par de conjuntos es linealmente separable y encontrar un hiperplano separador 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

Sean y dos conjuntos de puntos en un espacio euclidiano n- dimensional. Entonces y son linealmente separables si existen n + 1 números reales , de modo que cada punto satisface y cada punto satisface , donde es la -ésima componente de . ${\ Displaystyle X_ {0}}$${\ Displaystyle X_ {1}}$${\ Displaystyle X_ {0}}$${\ Displaystyle X_ {1}}$${\ Displaystyle w_ {1}, w_ {2}, .., w_ {n}, k}$${\ Displaystyle x \ in X_ {0}}$${\ Displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i}> k}$${\ Displaystyle x \ in X_ {1}}$${\ Displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} <k}$${\ Displaystyle x_ {i}}$${\ Displaystyle i}$${\ Displaystyle x}$

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

Ejemplos de

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

Sin embargo, no todos los conjuntos de cuatro puntos, ni 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 separables linealmente.

Separabilidad lineal de funciones booleanas en n variables

Una función booleana en n variables se puede considerar como una asignación de 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 funciones booleanas distintas es donde n es el número de variables pasadas a la función. ${\ Displaystyle 2 ^ {2 ^ {n}}}$

Máquinas de vectores de soporte

H ₁ no separa los conjuntos. H _{2 lo} hace, pero solo con un pequeño margen. H _{3 los} separa con el margen máximo.

La clasificación de datos es una tarea común en el aprendizaje automático . Suponga que se dan algunos puntos de datos, cada uno de los cuales pertenece a uno de los dos conjuntos, y deseamos crear un modelo que decidirá en qué conjunto estará un nuevo punto de datos. En el caso de las máquinas de vectores de soporte , un punto de datos se ve como un vector p -dimensional (una lista de p números), y queremos saber si podemos separar tales puntos con un hiperplano ( p  - 1) -dimensional . A esto se le llama clasificador lineal . Hay muchos hiperplanos que pueden clasificar (separar) los datos. Una elección razonable como mejor hiperplano es la que representa la mayor separación, o margen, entre los dos conjuntos. Así que elegimos el hiperplano para maximizar la distancia desde él hasta el punto de datos más cercano en cada lado. Si tal 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, dados algunos datos de entrenamiento , un conjunto de n puntos del formulario ${\ Displaystyle {\ mathcal {D}}}$

${\ 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 . Cada uno es un vector real p -dimensional . Queremos encontrar el hiperplano de margen máximo que divide los puntos que tienen de los que tienen . Cualquier hiperplano puede escribirse como el conjunto de puntos que satisfacen ${\ Displaystyle \ mathbf {x} _ {i}}$${\ Displaystyle \ mathbf {x} _ {i}}$${\ Displaystyle y_ {i} = 1}$${\ Displaystyle y_ {i} = - 1}$${\ Displaystyle \ mathbf {x}}$

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

donde denota el producto escalar y el vector normal (no necesariamente normalizado) al hiperplano. El parámetro determina el desplazamiento del hiperplano desde el origen a lo largo del vector normal . ${\ Displaystyle \ cdot}$${\ Displaystyle {\ mathbf {w}}}$${\ Displaystyle {\ tfrac {b} {\ | \ mathbf {w} \ |}}}$${\ 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 tratar de maximizar su distancia.

Ver también

• Teorema de separación de hiperplano
• Teorema de kirchberger
• Perceptrón
• Dimensión Vapnik-Chervonenkis

Referencias