¿Cómo calcular las ponderaciones del criterio de Fisher?

Question

Estoy estudiando reconocimiento de patrones y aprendizaje automático, y me encontré con la siguiente pregunta.

Consideremos un problema de clasificación de dos clases con igual probabilidad de clase a priori $$P(D_1)=P(D_2)= \frac{1}{2}$$

y la distribución de instancias en cada clase dada por

$$p(x|D_1)= {\cal N} \left( \begin{bmatrix} 0 \\0 \end{bmatrix}, \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \right),$$

$$p(x|D_2)= {\cal N} \left( \begin{bmatrix} 4 \\ 4 \end{bmatrix}, \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \right).$$

¿Cómo calcular las ponderaciones del criterio de Fisher?

Actualización 2: El peso calculado que proporciona mi libro es: $W=\begin{bmatrix} \frac{-4}{3} \\ \frac{-2}{9} \end{bmatrix}$ .

Actualización 3: Tal y como insinúa @xeon, entiendo que debo determinar la línea de proyección del discriminante de Fisher.

Actualización 4: Dejemos que $W$ sea la dirección de la línea de proyección, entonces el método discriminante lineal de Fisher encuentra que la mejor $W$ es aquella para la que se maximiza la función de criterio. El reto pendiente es cómo podemos obtener numéricamente $W$ ¿Vector?

Answer 1

Siguiendo el documento que enlazaste (Mika et al., 1999) tenemos que encontrar el $\mathbf{w}$ que maximiza el llamado cociente de Rayleigh generalizado ,

$$\frac{\mathbf{w}^\top \mathbf{S}_B \mathbf{w}}{\mathbf{w}^\top \mathbf{S}_W \mathbf{w}},$$

donde para significa $\mathbf{m}_1, \mathbf{m}_2$ y las covarianzas $\mathbf{C}_1, \mathbf{C}_2$ ,

\begin {align} \mathbf {S}_B &= ( \mathbf {m}_1 - \mathbf {m}_2)( \mathbf {m}_1 - \mathbf {m}_2)^ \top , & \mathbf {S}_W &= \mathbf {C}_1 + \mathbf {C}_2. \end {align}

La solución se puede encontrar resolviendo la problema generalizado de valores propios \begin {align} \mathbf {S}_B \mathbf {w} = \lambda \mathbf {S}_W \mathbf {w}, \end {align} calculando primero los valores propios $\lambda$ resolviendo \begin {align} \det ( \mathbf {S}_B - \lambda \mathbf {S}_W) = 0 \end {align} y luego resolver el vector propio $\mathbf{w}$ . En su caso, $$\mathbf{S}_B - \lambda \mathbf{S}_W = \begin{pmatrix}16 - 3\lambda & 16 \\ 16 & 16 - 2\lambda\end{pmatrix}.$$ El determinante de esta matriz de 2x2 se puede calcular a mano.

El vector propio con el mayor valor propio maximiza el cociente de Rayleigh. En lugar de hacer los cálculos a mano, he resuelto el problema de valores propios generalizados en Python utilizando scipy.linalg.eig y consiguió $$w_1 \approx 0.5547, w_2 \approx 0.8321,$$ que es diferente de la solución que encontró en su libro. A continuación he representado el hiperplano óptimo del vector de pesos que he encontrado (negro) y el hiperplano del vector de pesos encontrado en tu libro (rojo).

$\hskip1in$

Answer 2

$\mathbf{SOLUTION 1:}$

Siguiendo a Duda et al. (Pattern CLassification) que tiene una solución alternativa a la de @lucas y en este caso da una solución muy fácil de calcular a mano. (¡Espero que esta solución alternativa ayude! :))

En el LDA de dos clases el objetivo es:

$\frac{w^TS_Bw}{w^TS_Ww}$ que sólo significa que aumenta la varianza entre clases y disminuye la varianza dentro de la clase.

donde $S_B = (m_1-m_2)(m_1-m_2)^T$ y $S_W = S_1 + S_2$ Aquí $S_1,S_2$ son la matriz de covarianza y $m_1,m_2$ son las medias de las clases 1 y 2 respectivamente.

La solución de este cociente de Raleigh generalizado es un probema de valor propio generalizado.

$S_Bw = \lambda S_Ww \rightarrow {S_W}^{-1}S_Bw = \lambda w$

La formulación anterior tiene una solución de forma cerrada. $S_B$ es una matriz de rango 1 con base $m_1-m_2$ así que $w \propto {S_W}^{-1}(m1-m2)$ que puede ser normlizd para obtener la respuesta.

Acabo de calcular el $w$ y obtuvo [0,5547;0,8321].

${S_W}^{-1}(m1-m2) = {(S_1 + S_2)}^{-1}(m1 - m2) = {(\begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix})}^{-1}(\begin{bmatrix} 0 \\ 0 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \end{bmatrix} ) ={(\begin{bmatrix} 1/3 & 0 \\ 0 & 1/2 \end{bmatrix})}(\begin{bmatrix} 0 \\ 0 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \end{bmatrix} ) = \begin{bmatrix} -1.3333 \\ -2.0000 \end{bmatrix} \propto \begin{bmatrix} 0.5547 \\ 0.8321 \end{bmatrix}$

Ref: Clasificación de patrones de Duda, Hart, Stork

$\mathbf{SOLUTION 2:}$

Alternativamente, puede resolverse encontrando el vector propio del problema de valor propio generalizado. $S_Bw = \lambda S_Ww$

Un polinomio en lambda puede estar formado por $determinant(S_B - \lambda S_W)$ y las soluciones de ese polinomio serán el valor propio de $S_Bw = \lambda S_Ww$ . Ahora digamos que tienes un conjunto de valores propios $\lambda_1,\lambda_2, ..., \lambda_n,$ como raíces del polinomio. Ahora sustituye $\lambda = \lambda_i, i \in \{1,2,..,n\}$ y obtener el vector propio correspondiente como solución del sistema lineal de ecuaciones $S_Bw_i = \lambda_i S_Ww_i$ . Haciendo esto para cada i se puede obtener un conjunto de vectores $\{w_i\}_{i=1}^{n}$ y es un conjunto de vectores propios como soluciones.

$determinant(S_B - \lambda S_W) = \begin{bmatrix} 16 - 3\lambda & 16 \\ 16 & 16 - 2\lambda \end{bmatrix} =6\lambda^2 - 80\lambda$ Así que los valores propios son raíces del polinomio $6\lambda^2 - 80\lambda$ .

Así que $\lambda=$ 0 y 40/3 son las dos soluciones. Para el LDA, el vector propio correspondiente al valor propio más alto es la solución.

Solución al sistema de ecuaciones $(S_B - \lambda_i S_W)w_i = 0$ y $\lambda_i = 40/3$

que resulta ser $\begin{bmatrix} 16 - 3\lambda & 16 \\ 16 & 16 - 2\lambda \end{bmatrix}w_i \propto \begin{bmatrix} -72 & 48 \\ 48 & -32 \end{bmatrix}w_i = 0$

La solución del sistema de ecuaciones anterior es $\begin{bmatrix} -0.5547 \\ -0.8321 \end{bmatrix} \propto \begin{bmatrix} 0.5547 \\ 0.8321 \end{bmatrix}$ que es la misma que la solución anterior.

Alternativamente, podemos decir que $\begin{bmatrix} 0.5547 \\ 0.8321 \end{bmatrix}$ se encuentra en el espacio nulo de $\begin{bmatrix} -72 & 48 \\ 48 & -32 \end{bmatrix}$ .

Para el LDA de dos clases, el vector propio con mayor valor propio es la solución. En general, para el LDA de clase C, los primeros vectores propios C - 1 hasta los valores propios C - 1 más altos constituyen la solución.

Este vídeo explica cómo calcular los vectores propios para un problema simple de valores propios. ( https://www.khanacademy.org/math/linear-algebra/alternate_bases/eigen_everything/v/linear-algebra-finding-eigenvectors-and-eigenspaces-example )

A continuación, un ejemplo. http://www.sosmath.com/matrix/eigen2/eigen2.html

LDA multiclase: http://en.wikipedia.org/wiki/Linear_discriminant_analysis#Multiclass_LDA

Cálculo del espacio nulo de una matriz: https://www.khanacademy.org/math/linear-algebra/vectors_and_spaces/null_column_space/v/null-space-2-calculating-the-null-space-of-a-matrix