Análisis discriminante de Fisher con kernel

En estadística , el análisis discriminante de Fisher con kernel (KFD) , ^{[ 1 ]} también conocido como análisis discriminante generalizado ^{[ 2 ]} y análisis discriminante con kernel , ^{[ 3 ]} es una versión con kernel del análisis discriminante lineal (LDA). Recibe su nombre de Ronald Fisher .

Intuitivamente, la idea de LDA es encontrar una proyección donde se maximice la separación de clases. Dados dos conjuntos de datos etiquetados ,${\displaystyle \mathbf {C} _{1}}$y${\displaystyle \mathbf {C} _{2}}$, podemos calcular el valor medio de cada clase,${\displaystyle \mathbf {m} _{1}}$y${\displaystyle \mathbf {m} _{2}}$, como

${\displaystyle \mathbf {m} _{i}={\frac {1}{l_{i}}}\sum _{n=1}^{l_{i}}\mathbf {x} _{n}^{i},}$

dónde${\displaystyle l_{i}}$es el número de ejemplos de clase${\displaystyle \mathbf {C} _{i}}$El objetivo del análisis discriminante lineal es lograr una gran separación de las medias de las clases, manteniendo al mismo tiempo una varianza intraclase pequeña. ^{[ 4 ]} Esto se formula como maximizar, con respecto a${\displaystyle \mathbf {w} }$, la siguiente proporción:

${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }},}$

dónde${\displaystyle \mathbf {S} _{B}}$es la matriz de covarianza entre clases y${\displaystyle \mathbf {S} _ {W}}$es la matriz de covarianza total dentro de cada clase:

${\displaystyle {\begin{aligned}\mathbf {S} _{B}&=(\mathbf {m} _{2}-\mathbf {m} _{1})(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\\\mathbf {S} _{W}&=\sum _{i=1,2}\sum _{n=1}^{l_{i}}(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})^{\text{T}}.\end{aligned}}}$

El valor máximo de la relación anterior se alcanza en

${\displaystyle \mathbf {w} \propto \mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).}$

como puede demostrarse mediante el método de los multiplicadores de Lagrange (esbozo de la demostración):

Maximizar${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }}}$es equivalente a maximizar

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }$

sujeto a

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} =1.}$

Esto, a su vez, es equivalente a maximizar${\displaystyle I(\mathbf {w} ,\lambda )=\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} -\lambda (\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} -1)}$, dónde${\displaystyle \lambda }$es el multiplicador de Lagrange.

Como máximo, las derivadas de${\displaystyle I(\mathbf {w} ,\lambda )}$con respecto a${\displaystyle \mathbf {w} }$y${\displaystyle \lambda }$debe ser cero. Tomando${\displaystyle {\frac {dI}{d\mathbf {w} }}=\mathbf {0} }$rendimientos

${\displaystyle \mathbf {S} _{B}\mathbf {w} -\lambda \mathbf {S} _{W}\mathbf {w} =\mathbf {0} ,}$

lo cual se satisface trivialmente por${\displaystyle \mathbf {w} =c\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1})}$y${\displaystyle \lambda =(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).}$

Para extender LDA a mapeos no lineales, los datos, dados como${\displaystyle \ell }$agujas${\displaystyle \mathbf {x} _{i},}$se puede asignar a un nuevo espacio de características,${\displaystyle F,}$a través de alguna función${\displaystyle \phi .}$En este nuevo espacio de características, la función que necesita ser maximizada es ^{[ 1 ].}

${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} }},}$

dónde

${\displaystyle {\begin{aligned}\mathbf {S} _{B}^{\phi }&=\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)^{\text{T}}\\\mathbf {S} _{W}^{\phi }&=\sum _{i=1,2}\sum _{n=1}^{l_{i}}\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)^{\text{T}},\end{aligned}}}$

y

${\displaystyle \mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\sum _{j=1}^{l_{i}}\phi (\mathbf {x} _{j}^{i}).}$

Además, tenga en cuenta que${\displaystyle \mathbf {w} \in F}$Calcular explícitamente las asignaciones${\displaystyle \phi (\mathbf {x} _{i})}$y luego realizar LDA puede ser computacionalmente costoso y, en muchos casos, intratable. Por ejemplo,${\displaystyle F}$puede ser de dimensión infinita. Por lo tanto, en lugar de mapear explícitamente los datos a${\displaystyle F}$, los datos pueden incrustarse implícitamente reescribiendo el algoritmo en términos de productos escalares y utilizando funciones de núcleo en las que el producto escalar en el nuevo espacio de características se reemplaza por una función de núcleo,${\displaystyle k(\mathbf {x} ,\mathbf {y} )=\phi (\mathbf {x} )\cdot \phi (\mathbf {y} )}$.

LDA puede reformularse en términos de productos escalares, observando primero que${\displaystyle \mathbf {w} }$tendrá una expansión de la forma ^{[ 5 ]}

${\displaystyle \mathbf {w} =\sum _{i=1}^{l}\alpha _{i}\phi (\mathbf {x} _{i}).}$

Entonces tenga en cuenta que

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\sum _{j=1}^{l}\sum _{k=1}^{l_{i}}\alpha _{j}k\left(\mathbf {x} _{j},\mathbf {x} _{k}^{i}\right)=\mathbf {\alpha } ^{\text{T}}\mathbf {M} _{i},}$

dónde

${\displaystyle (\mathbf {M} _{i})_{j}={\frac {1}{l_{i}}}\sum _{k=1}^{l_{i}}k(\mathbf {x} _{j},\mathbf {x} _{k}^{i}).}$

El numerador de${\displaystyle J(\mathbf {w} )}$entonces se puede escribir como:

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} =\mathbf {w} ^{\text{T}}\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)^{\text{T}}\mathbf {w} =\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } ,\qquad {\text{where}}\qquad \mathbf {M} =(\mathbf {M} _{2}-\mathbf {M} _{1})(\mathbf {M} _{2}-\mathbf {M} _{1})^{\text{T}}.}$

De manera similar, el denominador se puede escribir como

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} =\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } ,\qquad {\text{where}}\qquad \mathbf {N} =\sum _{j=1,2}\mathbf {K} _{j}(\mathbf {I} -\mathbf {1} _{l_{j}})\mathbf {K} _{j}^{\text{T}},}$

con el${\displaystyle n^{\text{th}},m^{\text{th}}}$componente de${\displaystyle \mathbf {K} _{j}}$definido como${\displaystyle k(\mathbf {x} _{n},\mathbf {x} _{m}^{j}),\mathbf {I} }$es la matriz identidad y${\displaystyle \mathbf {1} _{l_{j}}}$la matriz con todas las entradas iguales a${\displaystyle 1/l_{j}}$Esta identidad se puede derivar comenzando con la expresión para${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} }$y utilizando la expansión de${\displaystyle \mathbf {w} }$y las definiciones de${\displaystyle \mathbf {S} _{W}^{\phi }}$y${\displaystyle \mathbf {m} _{i}^{\phi }}$

${\displaystyle {\begin{aligned}\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} &=\left(\sum _{i=1}^{l}\alpha _{i}\phi ^{\text{T}}(\mathbf {x} _{i})\right)\left(\sum _{j=1,2}\sum _{n=1}^{l_{j}}\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)^{\text{T}}\right)\left(\sum _{k=1}^{l}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\phi ^{\text{T}}(\mathbf {x} _{i})\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)^{\text{T}}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{p=1}^{l_{j}}\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})\right)\left(\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{q=1}^{l_{j}}\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\alpha _{k}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {2\alpha _{i}\alpha _{k}}{l_{j}}}\sum _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})+{\frac {\alpha _{i}\alpha _{k}}{l_{j}^{2}}}\sum _{p=1}^{l_{j}}\sum _{q=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\alpha _{k}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {\alpha _{i}\alpha _{k}}{l_{j}}}\sum _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})\right)\right)\\[6pt]&=\sum _{j=1,2}\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {K} _{j}^{\text{T}}\mathbf {\alpha } -\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {1} _{l_{j}}\mathbf {K} _{j}^{\text{T}}\mathbf {\alpha } \\[4pt]&=\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } .\end{aligned}}}$

Con estas ecuaciones para el numerador y el denominador de${\displaystyle J(\mathbf {w} )}$, la ecuación para${\displaystyle J}$puede reescribirse como

${\displaystyle J(\mathbf {\alpha } )={\frac {\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } }{\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } }}.}$

Luego, al derivar e igualar a cero se obtiene

${\displaystyle (\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } )\mathbf {N} \mathbf {\alpha } =(\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } )\mathbf {M} \mathbf {\alpha } .}$

Dado que solo la dirección de${\displaystyle \mathbf {w} }$y por lo tanto la dirección de${\displaystyle \mathbf {\alpha } ,}$asuntos, lo anterior se puede resolver${\displaystyle \mathbf {\alpha } }$como

${\displaystyle \mathbf {\alpha } =\mathbf {N} ^{-1}(\mathbf {M} _{2}-\mathbf {M} _{1}).}$

Tenga en cuenta que, en la práctica,${\displaystyle \mathbf {N} }$suele ser singular y por eso se le añade un múltiplo de la identidad ^{[ 1 ].}

${\displaystyle \mathbf {N} _{\epsilon }=\mathbf {N} +\epsilon \mathbf {I} .}$

Dada la solución para${\displaystyle \mathbf {\alpha } }$, la proyección de un nuevo punto de datos viene dada por ^{[ 1 ]}

${\displaystyle y(\mathbf {x} )=(\mathbf {w} \cdot \phi (\mathbf {x} ))=\sum _{i=1}^{l}\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} ).}$

La extensión a casos donde hay más de dos clases es relativamente sencilla. ^{[ 2 ] [ 6 ] [ 7 ]} Sea${\displaystyle c}$sea ​​el número de clases. Entonces, el KFD multiclase implica proyectar los datos en un${\displaystyle (c-1)}$espacio -dimensional usando${\displaystyle (c-1)}$funciones discriminantes

${\displaystyle y_{i}=\mathbf {w} _{i}^{\text{T}}\phi (\mathbf {x} )\qquad i=1,\ldots ,c-1.}$

Esto se puede escribir en notación matricial.

${\displaystyle \mathbf {y} =\mathbf {W} ^{\text{T}}\phi (\mathbf {x} ),}$

donde el${\displaystyle \mathbf {w} _{i}}$son las columnas de${\displaystyle \mathbf {W} }$. ^{[ 6 ]} Además, la matriz de covarianza entre clases es ahora

${\displaystyle \mathbf {S} _{B}^{\phi }=\sum _{i=1}^{c}l_{i}(\mathbf {m} _{i}^{\phi }-\mathbf {m} ^{\phi })(\mathbf {m} _{i}^{\phi }-\mathbf {m} ^{\phi })^{\text{T}},}$

dónde${\displaystyle \mathbf {m} ^{\phi }}$es la media de todos los datos en el nuevo espacio de características. La matriz de covarianza dentro de la clase es

${\displaystyle \mathbf {S} _{W}^{\phi }=\sum _{i=1}^{c}\sum _{n=1}^{l_{i}}(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi })(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi })^{\text{T}},}$

La solución se obtiene ahora maximizando

${\displaystyle J(\mathbf {W} )={\frac {\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {W} \right|}{\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {W} \right|}}.}$

El truco del kernel se puede volver a utilizar y el objetivo de KFD multiclase se convierte en ^{[ 7 ].}

${\displaystyle \mathbf {A} ^{*}={\underset {\mathbf {A} }{\operatorname {argmax} }}={\frac {\left|\mathbf {A} ^{\text{T}}\mathbf {M} \mathbf {A} \right|}{\left|\mathbf {A} ^{\text{T}}\mathbf {N} \mathbf {A} \right|}},}$

dónde${\displaystyle A=[\mathbf {\alpha } _{1},\ldots ,\mathbf {\alpha } _{c-1}]}$y

${\displaystyle {\begin{aligned}M&=\sum _{j=1}^{c}l_{j}(\mathbf {M} _{j}-\mathbf {M} _{*})(\mathbf {M} _{j}-\mathbf {M} _{*})^{\text{T}}\\N&=\sum _{j=1}^{c}\mathbf {K} _{j}(\mathbf {I} -\mathbf {1} _{l_{j}})\mathbf {K} _{j}^{\text{T}}.\end{aligned}}}$

El${\displaystyle \mathbf {M} _{i}}$se definen como en la sección anterior y${\displaystyle \mathbf {M} _{*}}$se define como

${\displaystyle (\mathbf {M} _{*})_{j}={\frac {1}{l}}\sum _{k=1}^{l}k(\mathbf {x} _{j},\mathbf {x} _{k}).}$

${\displaystyle \mathbf {A} ^{*}}$Luego se puede calcular encontrando el${\displaystyle (c-1)}$vectores propios principales de${\displaystyle \mathbf {N} ^{-1}\mathbf {M} }$. ^{[ 7 ]} Además, la proyección de una nueva entrada,${\displaystyle \mathbf {x} _{t}}$, viene dado por ^{[ 7 ]}

${\displaystyle \mathbf {y} (\mathbf {x} _{t})=\left(\mathbf {A} ^{*}\right)^{\text{T}}\mathbf {K} _{t},}$

donde el${\displaystyle i^{th}}$componente de${\displaystyle \mathbf {K} _{t}}$es dado por${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{t})}$.

Tanto en KFD de dos clases como de múltiples clases, la etiqueta de clase de una nueva entrada se puede asignar como ^{[ 7 ].}

${\displaystyle f(\mathbf {x} )=arg\min _{j}D(\mathbf {y} (\mathbf {x} ),{\bar {\mathbf {y} }}_{j}),}$

dónde${\displaystyle {\bar {\mathbf {y} }}_{j}}$es la media proyectada para la clase${\displaystyle j}$y${\displaystyle D(\cdot ,\cdot )}$es una función de distancia.

El análisis discriminante de núcleo se ha utilizado en diversas aplicaciones. Estas incluyen:

• Reconocimiento facial ^{[ 3 ] [ 8 ] [ 9 ]} y detección ^{[ 10 ] [ 11 ]}
• Reconocimiento de dígitos escritos a mano ^{[ 1 ] [ 12 ]}
• Reconocimiento de huellas palmares ^{[ 13 ]}
• Clasificación de microcalcificaciones en racimo malignas y benignas ^{[ 14 ]}
• Clasificación de semillas ^{[ 2 ]}
• Búsqueda del bosón de Higgs en el CERN ^{[ 15 ]}

• Análisis factorial
• Análisis de componentes principales del núcleo
• Truco del kernel
• Análisis discriminante lineal

• Análisis discriminante de kernel en C# - Código C# para realizar KFD.
• Caja de herramientas de Matlab para la reducción de dimensionalidad Archivada el 18/12/2012 en Wayback Machine - Incluye un método para realizar KFD.
• Reconocimiento de escritura a mano mediante análisis discriminante de kernel : código C# que demuestra el reconocimiento de dígitos escritos a mano mediante KFD.