Separabilidad lineal

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

En la 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 coloreados de azul y el otro conjunto de puntos como coloreados de 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 separador en caso de que lo sea, 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 , tales que cada punto satisface y cada punto satisface , donde es el componente -ésimo 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 respectivas envolturas convexas están disjuntas (coloquialmente, no se superponen). ^[1]

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 caerá el otro conjunto de puntos.

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

Sin embargo, no todos los conjuntos de cuatro puntos, ni siquiera 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:

Obsérvese que tres puntos que son colineales y tienen la forma "+ ⋅⋅⋅ — ⋅⋅⋅ +" tampoco son linealmente separables.

Número de separaciones lineales

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

Separabilidad lineal de funciones booleanas ennortevariables

Una función booleana en n variables puede considerarse 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. ^[3] ${\displaystyle 2^{2^{n}}}$

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 valor sólo se conoce con exactitud hasta el caso, pero el orden de magnitud se conoce con bastante exactitud: tiene límite superior y límite inferior . ^[6] ${\displaystyle n=9}$ ${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$ ${\displaystyle 2^{n^{2}-n\log _{2}n-O(n)}}$

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

Máquinas de vectores de soporte

H ₁ no separa los conjuntos. H ₂ sí lo hace, pero con un pequeño margen. H ₃ los separa con el máximo margen.

La clasificación de 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 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 dichos puntos con un hiperplano ( p  − 1)-dimensional . Esto se llama clasificador lineal . Hay muchos hiperplanos que podrían clasificar (separar) los datos. Una opción razonable como el mejor hiperplano es el 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 existe dicho hiperplano, se lo 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 de la forma ${\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 de dimensión p . 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 intentar maximizar su distancia.

Véase también

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

Referencias

1. Boyd, Stephen; Vandenberghe, Lieven (8 de marzo de 2004). Optimización convexa. Cambridge University Press. doi :10.1017/cbo9780511804441. ISBN 978-0-521-83378-3.
2. MacKay, David (25 de septiembre de 2003). Teoría de la información, inferencia y algoritmos de aprendizaje. Cambridge University Press . pág. 483. ISBN. 9780521642989.
3. Russell, Stuart J. (2016). Inteligencia artificial: un enfoque moderno . Norvig, Peter 1956- (Tercera edición). Boston. pág. 766. ISBN 978-1292153964.OCLC 945899984  .{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
4. Muroga, Saburo (1971). Lógica de umbral y sus aplicaciones . Nueva York: Wiley-Interscience. ISBN 978-0-471-62530-8.
5. Knuth, Donald Ervin (2011). El arte de la programación informática . Upper Saddle River: Addison-Wesley. págs. 75-79. ISBN 978-0-201-03804-0.
6. Šíma, Jiří; Orponen, Pekka (1 de diciembre de 2003). "Computación de propósito general con redes neuronales: un estudio de los resultados teóricos de la complejidad". Computación neuronal . 15 (12): 2727–2778. doi :10.1162/089976603322518731. ISSN  0899-7667. PMID  14629867. S2CID  264603251.
7. Gruzling, Nicolle (2006). "Separabilidad lineal de los vértices de un hipercubo n-dimensional. Tesis de maestría" (Documento). Universidad del Norte de Columbia Británica.