En geometría , el teorema de separación de hiperplanos es un teorema sobre conjuntos convexos disjuntos en el espacio euclidiano n- dimensional . Hay varias versiones bastante similares. En una versión del teorema, si ambos conjuntos son cerrados y al menos uno de ellos es compacto , entonces hay un hiperplano entre ellos e incluso dos hiperplanos paralelos entre ellos separados por un espacio. En otra versión, si ambos conjuntos convexos disjuntos están abiertos, entonces hay un hiperplano entre ellos, pero no necesariamente ningún espacio. Un eje que es ortogonal a un hiperplano de separación es un eje de separación, porque las proyecciones ortogonales de los cuerpos convexos sobre el eje son inconexas.
El teorema de la separación del hiperplano se debe a Hermann Minkowski . El teorema de separación de Hahn-Banach generaliza el resultado a espacios vectoriales topológicos .
Un resultado relacionado es el teorema del hiperplano de apoyo .
En el contexto de las máquinas de vectores de soporte , el hiperplano que separa de manera óptima o el hiperplano de margen máximo es un hiperplano que separa dos cascos convexos de puntos y es equidistante de los dos. [1] [2] [3]
Declaraciones y prueba
Teorema de separación de hiperplanos [4] - Sean A y B dos subconjuntos convexos no vacíos disjuntos de R n . Entonces existe un vector v distinto de cero y un número real c tal que
para todo x en A e y en B ; es decir, el hiperplano, V el vector normal, separa A y B .
La prueba se basa en el siguiente lema:
Lema - Dejarser un subconjunto convexo cerrado no vacío de R n . Entonces existe un vector único en de norma mínima (longitud).
Prueba de lema : Let Dejar ser una secuencia en tal que . Tenga en cuenta que es en desde es convexo y entonces . Desde
como , es una secuencia de Cauchy y por lo tanto tiene límite x en. Es único ya que si y está en y tiene norma δ, entoncesy x = y .
Demostración del teorema : Dados conjuntos convexos no vacíos disjuntos A , B , sea
Desde es convexo y la suma de conjuntos convexos es convexa,es convexo. Por el lema, el cierre de , que es convexo, contiene un vector de norma mínima. Desde es convexo, para cualquier en , el segmento de línea
yace en y entonces
- .
Para , así tenemos:
y dejando da: . Por tanto, para cualquier x en A e y en B , tenemos:. Por tanto, si v es distinto de cero, la demostración es completa ya que
De manera más general (cubriendo el caso v = 0), tomemos primero el caso cuando el interior deno está vacío. El interior puede agotarse mediante una secuencia anidada de subconjuntos convexos compactos no vacíos. [ aclaración necesaria ] Dado que 0 no está en, cada contiene un vector distinto de cero de longitud mínima y por el argumento de la primera parte, tenemos: para cualquier . Podemos normalizar eldebe tener la longitud uno. Entonces la secuenciacontiene una subsecuencia convergente (porque la n-esfera es compacta) con límite v , que es distinto de cero. Tenemospara cualquier x en el interior dey por continuidad lo mismo vale para todo x en. Ahora terminamos la prueba como antes. Finalmente, sitiene interior vacío, el conjunto afín que abarca tiene una dimensión menor que la de todo el espacio. como consecuencia está contenido en algún hiperplano ; por lo tanto,para todo x en y terminamos la prueba como antes.
El número de dimensiones debe ser finito. En los espacios de dimensión infinita hay ejemplos de dos conjuntos cerrados, convexos y disjuntos que no pueden ser separados por un hiperplano cerrado (un hiperplano donde un funcional lineal continuo es igual a alguna constante) incluso en el sentido débil donde las desigualdades no son estrictas. [5]
La prueba anterior también prueba la primera versión del teorema mencionado en el lede (para verlo, tenga en cuenta que en la demostración se cierra bajo la hipótesis del teorema siguiente.)
Teorema de separación I - Sean A y B dos conjuntos convexos cerrados no vacíos disjuntos, uno de los cuales es compacto. Entonces existe un vector v distinto de cero y números reales tal que
para todos x en A y y en B .
Aquí, la compacidad de la hipótesis no se puede relajar; vea un ejemplo en la siguiente sección. Esta versión del teorema de la separación se generaliza a la dimensión infinita; la generalización se conoce más comúnmente como el teorema de separación de Hahn-Banach .
También tenemos:
Teorema de separación II - Sean A y B dos conjuntos convexos no vacíos disjuntos. Si A está abierto, entonces existe un vector v distinto de cero y un número real tal que
para todos x en A y y en B . Si ambos conjuntos están abiertos, entonces existe un vector v distinto de cero y un número real tal que
para todos x en A y y en B .
Esto se deriva de la versión estándar, ya que el hiperplano de separación no puede intersecar los interiores de los conjuntos convexos.
Inverso del teorema
Tenga en cuenta que la existencia de un hiperplano que sólo "separa" dos conjuntos convexos en el sentido débil de que ambas desigualdades no son estrictas, obviamente, no implica que los dos conjuntos sean disjuntos. Ambos conjuntos podrían tener puntos ubicados en el hiperplano.
Contraejemplos y singularidad
Si uno de A o B no es convexo, entonces hay muchos contraejemplos posibles. Por ejemplo, A y B podrían ser círculos concéntricos. Un contraejemplo más sutil es aquel en el que A y B están cerrados pero ninguno es compacto. Por ejemplo, si A es un semiplano cerrado y B está limitado por un brazo de una hipérbola, entonces no hay un hiperplano estrictamente separador:
(Aunque, según un ejemplo del segundo teorema, hay un hiperplano que separa sus interiores). Otro tipo de contraejemplo tiene A compacto y B abierto. Por ejemplo, A puede ser un cuadrado cerrado y B puede ser un cuadrado abierto que toca A .
En la primera versión del teorema, evidentemente el hiperplano separador nunca es único. En la segunda versión, puede ser único o no. Técnicamente, un eje de separación nunca es único porque se puede trasladar; en la segunda versión del teorema, un eje de separación puede ser único hasta la traslación.
Uso en detección de colisiones
El teorema del eje de separación (SAT) dice que:
Dos objetos convexos no se superponen si existe una línea (llamada eje) sobre la cual las proyecciones de los dos objetos no se superponen.
SAT sugiere un algoritmo para probar si dos sólidos convexos se cruzan o no.
Independientemente de la dimensionalidad, el eje de separación es siempre una línea. Por ejemplo, en 3D, el espacio está separado por planos, pero el eje de separación es perpendicular al plano de separación.
El teorema del eje de separación se puede aplicar para la detección rápida de colisiones entre mallas poligonales. La dirección normal u otra característica de cada cara se utiliza como eje de separación. Tenga en cuenta que esto produce posibles ejes de separación, no líneas / planos de separación.
En 3D, el uso de caras normales por sí solas no logrará separar algunos casos de borde a borde que no colisionen. Se requieren ejes adicionales, que consisten en los productos cruzados de pares de bordes, uno tomado de cada objeto. [6]
Para una mayor eficiencia, los ejes paralelos se pueden calcular como un solo eje.
Ver también
Notas
- ^ Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2008). Los elementos del aprendizaje estadístico: minería de datos, inferencia y predicción (PDF) (segunda edición). Nueva York: Springer. págs. 129-135.
- ^ Witten, Ian H .; Frank, Eibe; Hall, Mark A .; Pal, Christopher J. (2016). Minería de datos: herramientas y técnicas prácticas de aprendizaje automático (cuarta ed.). Morgan Kaufmann. págs. 253-254.
- ^ Deisenroth, Marc Peter; Faisal, A. Aldo; Ong, Cheng Soon (2020). Matemáticas para el aprendizaje automático . Prensa de la Universidad de Cambridge. págs. 337–338. ISBN 978-1-108-45514-5.
- ^ Boyd y Vandenberghe 2004 , ejercicio 2.22.
- ^ Haïm Brezis , Analyse fonctionnelle: théorie et applications , 1983, remarque 4, p. 7.
- ^ https://docs.godotengine.org/en/stable/tutorials/math/vectors_advanced.html#collision-detection-in-3d
Referencias
- Boyd, Stephen P .; Vandenberghe, Lieven (2004). Optimización convexa (pdf) . Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3.
- Golshtein, EG; Tretyakov, NV (1996). Lagrangianos modificados y mapas monótonos en optimización . Nueva York: Wiley. pag. 6. ISBN 0-471-54821-9.
- Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Programación matemática no diferenciable y de dos niveles . Boston: Editores académicos de Kluwer. pag. 19. ISBN 0-7923-9821-1.
enlaces externos
- Detección y respuesta a colisiones