Soy estudiante de CS y no entiendo muy bien las matemáticas que hay detrás de un problema de optimización procedente de un algoritmo de aprendizaje automático. El algoritmo está en la sección 5 del documento http://visl.technion.ac.il/bron/publications/BroBroOvsGuiTOG10.pdf
Planteamiento del problema
dado $P$ pares de ejemplos $(f_p, {f_p}')$ etiquetado por {1,-1}, donde $f_p$ es un vector de características v-dimensional y +1 (reps., -1) indica pares similares (reps., disímiles), el objetivo es encontrar el $s$ X $v$ matriz A y $v$ X1 vector b tal que $d_{A,b}$ refleja la similitud deseada de los ejemplos de entrenamiento. La distancia $d_{A,b}$ se define como:
$d_{A,b}(x, x')=d_H(\mbox{sign}(Af+b), \mbox{sign}(Af'+b))$ ,
donde $d_H(y,y')=\frac{s}{2}-\frac{1}{2}\sum_{i=1}^s\mbox{sign}(y_i{y_i}')$ es la métrica de Hamming en el espacio Hamming de s dimensiones de las secuencias binarias de longitud s.
Lo ideal sería conseguir $d_{A,b}(f,f')\leq d_0$ para pares similares (P) y $d_{A,b} > d_0$ para los disímiles (N), donde $d_0$ es un umbral. Sin embargo, en la práctica, siempre existen falsos positivos y falsos negativos. Por lo tanto, los valores óptimos de A, b deben ser mínimos:
$min\frac{1}{P}\sum_{(f,f')\in P}e^{\mbox{sign}(d_{A,b}(f,f')-d_0)}+\frac{1}{N}\sum_{(f,f')\in N}e^{\mbox{sign}(d_0-d_{A,b}(f,f')}$
Algoritmo
El aprendizaje de los parámetros óptimos A y b se plantea como un problema de clasificación binaria potenciada, donde $\mbox{sign}(Af+b)$ actúa como un clasificador binario fuerte y cada dimensión de la proyección lineal $\mbox{sign}(A_ix+b_i)$ es un clasificador débil. De este modo, el algoritmo AdaBoost ( http://www.cs.rochester.edu/users/faculty/stefanko/Teaching/09CS446/Boosting2.pdf ) se puede utilizar para construir progresivamente A y b. Intuitivamente, este algoritmo aumenta los pesos de los ejemplos clasificados incorrectamente para que el aprendiz se vea obligado a centrarse en los ejemplos difíciles del conjunto de entrenamiento.
Entrada: P pares de ejemplos $(f_p, {f_p}')$ etiquetado por $s_p$
- Inicializar ${w_p}^i=1/P$
-
Para i = 1, ..., d hacer
Establecer la i-ésima fila de A y b resolviendo el problema de optimización $(A_i, b_i)=\min \sum_{p=1}^P {w_p}^is_p(2-\mbox{sign}(A_if_p+b_i))(2-\mbox{sign}(A_i{f_p}'+b_i))$
Actualizar los pesos ${w_p}^{i+1}={w_p}^ie^{-s_p\mbox{sign}(A_if_p+b_i)\mbox{sign}(A_i{f_p}'+b_i)}$
Mi pregunta La optimización en el algoritmo anterior es difícil, por lo que el autor trató de resolver un problema más sencillo estableciendo
$A_i=\arg \max \frac{{A_i}^TC_NA_i}{{A_i}^TC_PA_i}$
donde $C_P$ y $C_N$ son las matrices de covarianza de los pares de ejemplos positivos y negativos
El autor dice que $A_i$ que maximiza la fórmula anterior es el mayor vector propio generalizado de ${C_P}^{-1/2}{C_N}^{1/2}$ . Como esto no coincide exactamente con el problema de optimización original, el autor selecciona un subespacio abarcado por los 10 mayores vectores propios, de los cuales se selecciona la dirección y el parámetro umbral b que minimiza la pérdida exponencial. No entiendo cómo se hace la selección. ¿Alguien me puede explicar? Muchas gracias.
