Calcule y grafique el límite de decisión de LDA

Vi una gráfica de LDA (análisis discriminante lineal) con límites de decisión de The Elements of Statistical Learning :

Entiendo que los datos se proyectan en un subespacio de menor dimensión. Sin embargo, me gustaría saber cómo obtenemos los límites de decisión en la dimensión original de modo que pueda proyectar los límites de decisión en un subespacio de dimensión inferior (como las líneas negras en la imagen de arriba).

¿Hay alguna fórmula que pueda usar para calcular los límites de decisión en la dimensión original (superior)? En caso afirmativo, ¿qué aportes necesita esta fórmula?

Esta figura particular en Hastie et al. se produjo sin calcular ecuaciones de límites de clase. En cambio, se utilizó el algoritmo descrito por @ttnphns en los comentarios, ver nota 2 en la sección 4.3, página 110:

Para esta figura y muchas figuras similares en el libro, calculamos los límites de decisión mediante un método exhaustivo de contorneado. Calculamos la regla de decisión en una fina red de puntos, y luego usamos algoritmos de contorneado para calcular los límites.

Sin embargo, procederé a describir cómo obtener ecuaciones de los límites de la clase LDA.

Comencemos con un simple ejemplo 2D. Aquí están los datos del conjunto de datos de Iris ; Descarto las medidas de pétalos y solo considero la longitud y el ancho del sépalo. Tres clases están marcadas con colores rojo, verde y azul:

Denotemos los medios de clase (centroides) como . LDA supone que todas las clases tienen la misma covarianza dentro de la clase; dados los datos, esta matriz de covarianza compartida se estima (hasta la escala) como , donde la suma está sobre todos los puntos de datos y el centroide de la clase respectiva se resta de cada punto.$\boldsymbol\mu_1, \boldsymbol\mu_2, \boldsymbol\mu_3$$\mathbf{W} = \sum_i (\mathbf{x}_i-\boldsymbol \mu_k)(\mathbf{x}_i-\boldsymbol \mu_k)^\top$

Para cada par de clases (por ejemplo, clase y ) hay un límite de clase entre ellas. Es obvio que el límite tiene que pasar por el punto medio entre los dos centroides de clase . Uno de los resultados centrales de LDA es que este límite es una línea recta ortogonal a . Hay varias formas de obtener este resultado, y aunque no fue parte de la pregunta, insinuaré brevemente tres de ellas en el Apéndice a continuación.$1$$2$$(\boldsymbol \mu_{1} + \boldsymbol \mu_{2})/2$$\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$

Tenga en cuenta que lo que está escrito anteriormente ya es una especificación precisa del límite. Si uno quiere tener una ecuación de línea en la forma estándar , a continuación, coeficientes de y se puede calcular y se dará por algunas fórmulas desordenado. Apenas puedo imaginar una situación en la que esto sea necesario.$y=ax+b$$a$$b$

Ahora apliquemos esta fórmula al ejemplo de Iris. Para cada par de clases encuentro un punto medio y trazo una línea perpendicular a :$\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{i} - \boldsymbol \mu_{j})$

Tres líneas se cruzan en un punto, como debería haberse esperado. Los límites de decisión están dados por rayos a partir del punto de intersección:

Tenga en cuenta que si el número de clases es , entonces habrá pares de clases y, por lo tanto, muchas líneas, todas intersectando en un enredo enredado. Para dibujar una buena imagen como la de Hastie et al., Uno necesita mantener solo los segmentos necesarios, y es un problema algorítmico separado en sí mismo (no relacionado con LDA de ninguna manera, porque uno no necesita hacerlo) la clasificación; para clasificar un punto, verifique la distancia de Mahalanobis a cada clase y elija el que tenga la distancia más baja, o use una LDA en serie o en pares).$K\gg 2$$K(K-1)/2$

En dimensiones, la fórmula permanece exactamente igual : el límite es ortogonal a y pasa a través de . Sin embargo, en dimensiones más altas esto ya no es una línea, sino un hiperplano de dimensiones . Con fines ilustrativos, uno simplemente puede proyectar el conjunto de datos a los dos primeros ejes discriminantes, y así reducir el problema al caso 2D (que creo que es lo que Hastie et al. Hicieron para producir esa figura).$D>2$$\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$$(\boldsymbol \mu_{1} + \boldsymbol \mu_{2})/2$$D-1$

Apéndice

¿Cómo ver que el límite es una línea recta ortogonal a ? Aquí hay varias formas posibles de obtener este resultado:$\mathbf{W}^{-1} (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$

1. La manera elegante: induce métrica de Mahalanobis en el avión; el límite debe ser ortogonal a en esta métrica, QED.$\mathbf{W}^{-1}$$\boldsymbol \mu_{1} - \boldsymbol \mu_{2}$

2. La forma gaussiana estándar: si ambas clases se describen mediante distribuciones gaussianas, entonces la probabilidad logarítmica de que un punto pertenece a la clase es proporcional a . En el límite, las probabilidades de pertenecer a las clases y son iguales; anótelo, simplifíquelo e inmediatamente obtendrá , QED$\mathbf x$$k$$(\mathbf x - \boldsymbol \mu_k)^\top \mathbf W^{-1}(\mathbf x - \boldsymbol \mu_k)$$1$$2$$\mathbf x^\top \mathbf W^{-1} (\boldsymbol \mu_{1} - \boldsymbol \mu_{2}) = \mathrm{const}$

3. La forma laboriosa pero intuitiva. Imagine que es una matriz de identidad, es decir, todas las clases son esféricas. Entonces la solución es obvia: el límite es simplemente ortogonal a . Si las clases no son esféricas, entonces uno puede hacerlas esféricamente. Si la descomposición propia de es , entonces matriz hará el truco (ver, por ejemplo, aquí ). Entonces, después de aplicar , el límite es ortogonal a . Si tomamos este límite, lo transformamos de nuevo conμ 1 - μ 2 W W = U D U ⊤ S = D - 1 / 2 U ⊤ S S ( μ 1 - μ 2 ) S - 1 S ⊤ S ( μ 1 - μ 2 ) $\mathbf{W}$$\boldsymbol \mu_1 - \boldsymbol \mu_2$$\mathbf{W}$$\mathbf{W} = \mathbf U \mathbf D \mathbf U^\top$$\mathbf S = \mathbf D^{-1/2} \mathbf U^\top$$\mathbf S$$\mathbf S (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$$\mathbf S^{-1}$ y pregunte qué es ahora ortogonal, la respuesta (izquierda como ejercicio) es: to . Al conectar la expresión para , obtenemos QED.$\mathbf S^\top \mathbf S \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$$\mathbf S$