Derivación de$S_W^{-1} S_B$ durante el cálculo de LDA

Question

Yo intente razón los cálculos durante la búsqueda para el peso óptimo de vectores $w$ durante los cálculos de la LDA. Por lo tanto, yo uso varios libros de texto como:

1. Kuhn, M. y Johnson, K. (2013) Aplicar modelos Predictivos. Nueva York: Springer. p.289
2. Hastie, T., Tibshirani R. y Friedman, J. (2008). Los Elementos de Aprendizaje Estadístico. 2ª ed. Stanford: Springer. p.116

En el 2º libro, los autores escriben que el $w$, lo que maximiza $\frac{w^TS_Bw}{w^tS_Ww}$ se puede encontrar mediante la búsqueda de los valores propios de la matriz $S_W^{-1}S_B$.

Pero, ¿por qué es esto y cómo ellos no vienen a esta ecuación $S_W^{-1}S_B$?

Answer 1

Hastie, T., Tibshirani R. y Friedman, J. (2008). Los Elementos de Aprendizaje Estadístico. 2ª ed. Stanford: Springer. p.116, la autora afirma que el problema de optimización de la Fisher LDA es (Ecuación 4.16),

\begin{equation} J = \max_{\mathbf{w}} \mathbf{w}^T \mathbf{S_B} \mathbf{w}, \end{equation} sujeto a la restricción \begin{equation} \mathbf{w}^{T} \mathbf{S_W} \mathbf{w} = 1. \end{equation}

Este problema puede ser resuelto mediante la optimización de Lagrange, por la reescritura de la función de costo en la forma de Lagrange,

\begin{equation} L = \mathbf{w}^T \mathbf{S_B} \mathbf{w} + \lambda(1 - \mathbf{w}^{T} \mathbf{S_W} \mathbf{w}). \end{equation}

Ahora, es posible tomar la derivada parcial de esta función para encontrar maxima,

\begin{equation} \frac{\partial L}{\partial \mathbf{w}} = \mathbf{S_b} \mathbf{w} - \lambda \mathbf{S_w} \mathbf{w}. \end{equation}

La configuración de este cero y reordenando se obtiene,

\begin{equation} \mathbf{S_b} \mathbf{w} = \lambda \mathbf{S_w} \mathbf{w} .\end{equation}

Aviso, que podemos arreglar esto a la forma de un autovalor problema. La ecuación de un autovalor problema es

\begin{equation} \mathbf{A} \mathbf{w} = \lambda \mathbf{w}. \end{equation}

Así que por la inspección y reorganizar podemos ver, que el problema de optimización puede ser recasted a encontrar los vectores propios de la matriz $ \mathbf{S_w}^{-1} \mathbf{S_b} $.

Creo que una mayor comprensión de este problema puede ser obtenida mediante la comparación con el Análisis de Componentes Principales. Si usted tiene una sólida comprensión de por qué PCA resultados en un autovalor problema, entonces se vuelve mucho más sencilla que la LDA es, efectivamente, una "regularización" de la PCA problema y por lo tanto conduce a una solución similar.

Answer 2

Como una adición a @bookmins respuesta el concepto de cómo llegar al término de $S_W^{-1}S_B$ puede ser consultado aquí y en Marsland, S. (2015). Máquina de Aprendizaje de un algoritmo Perspectiva. 2ª ed. Boca Raton: CRC Press. p.132 así.
Además, aquí se afirma, que la búsqueda de la máxima de
$$\frac{\boldsymbol{w}^T S_B \boldsymbol{w}}{\boldsymbol{w}^T S_W \boldsymbol{w}}$$ es lo mismo que maximizar el nominador, manteniendo el denominador constante y por ello puede ser denominado como un problema de optimización restringida con:

$\max_\limits{w}\boldsymbol{w}^TS_B\boldsymbol{w}$ con la restricción $\boldsymbol{w}^TS_W\boldsymbol{w}=K$

Traer a este problema de optimización restringida en forma de Lagrange da: $$L=\boldsymbol{w}^T S_B \boldsymbol{w}-\lambda(\boldsymbol{w}^T S_W \boldsymbol{w}-K)$$ Encontrar el máximo de una función se puede lograr mediante el cálculo y ajuste de la derivada igual a cero. $$\frac{\delta L}{\delta \boldsymbol{w}}=S_B\boldsymbol{w}-\lambda S_W\boldsymbol{w}=\boldsymbol{0}$$ o $$S_B\boldsymbol{w}=\lambda S_W \boldsymbol{w}$$
Este es un generalizada Autovalor problema y puede (siempre que $S_W^{-1}$ existe) ser escrita como: $$S_W^{-1}S_B\boldsymbol{w}=\lambda\boldsymbol{w}$$ $$=$$ $$(S_W^{-1}S_B-\lambda\boldsymbol{I})\boldsymbol{w}=0$$ La solución de esta ecuación nos da los Valores propios ($\lambda$) y vectores propios ($\boldsymbol{w}$) y puede lograrse mediante el uso de numpy.linalg.eig(a) establecimiento $S_W^{-1}S_B$ por una o manualmente mediante el cálculo de $det(S_W^{-1}S_B-\lambda\boldsymbol{I})=0$, solución para $\lambda$ lo que nos da los Valores propios. La inserción de estos Autovalores ($\lambda$) a $(S_W^{-1}S_B-\lambda\boldsymbol{I})\boldsymbol{w}=0$ nos da un conjunto de ecuaciones lineales y resolver estas ecuaciones para $\boldsymbol{w}$ nos da los correspondientes vectores propios.