Clasificación SVM

Variante del algoritmo SVM

En el aprendizaje automático , un algoritmo de máquina de vectores de soporte (SVM) de clasificación es una variante del algoritmo de máquina de vectores de soporte , que se utiliza para resolver ciertos problemas de clasificación (mediante el aprendizaje de la clasificación ). El algoritmo de SVM de clasificación fue publicado por Thorsten Joachims en 2002. ^[1] El propósito original del algoritmo era mejorar el rendimiento de un motor de búsqueda de Internet . Sin embargo, se descubrió que el algoritmo de SVM de clasificación también se puede utilizar para resolver otros problemas, como Rank SIFT . ^[2]

Descripción

El algoritmo de clasificación SVM es una función de recuperación de aprendizaje que emplea métodos de clasificación por pares para ordenar de forma adaptativa los resultados en función de su relevancia para una consulta específica. La función de clasificación SVM utiliza una función de mapeo para describir la coincidencia entre una consulta de búsqueda y las características de cada uno de los resultados posibles. Esta función de mapeo proyecta cada par de datos (como una consulta de búsqueda y una página web en la que se hizo clic, por ejemplo) en un espacio de características. Estas características se combinan con los datos de clics correspondientes (que pueden actuar como un indicador de la relevancia de una página para una consulta específica) y luego se pueden utilizar como datos de entrenamiento para el algoritmo de clasificación SVM.

Generalmente, la clasificación SVM incluye tres pasos en el período de entrenamiento:

1. Mapea las similitudes entre las consultas y las páginas en las que se hizo clic en un espacio de características determinado.
2. Calcula las distancias entre cualesquiera dos de los vectores obtenidos en el paso 1.
3. Forma un problema de optimización que es similar a una clasificación SVM estándar y resuelve este problema con el solucionador SVM normal.

Fondo

Método de clasificación

Supongamos que es un conjunto de datos que contiene elementos . se aplica un método de clasificación a . Entonces, en se puede representar como una matriz binaria. Si el rango de es mayor que el rango de , es decir , la posición correspondiente de esta matriz se establece en el valor "1". De lo contrario, el elemento en esa posición se establecerá en el valor "0". ${\displaystyle \mathbb {C} }$ ${\displaystyle N}$ ${\displaystyle c_{i}}$ ${\displaystyle r}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle r}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle N\times N}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{j}}$ ${\displaystyle r\ c_{i}<r\ c_{j}}$

La tau de Kendall[3][4]

Tau de Kendall también se refiere al coeficiente de correlación de rango tau de Kendall , que se utiliza comúnmente para comparar dos métodos de clasificación para el mismo conjunto de datos.

Supongamos que y son dos métodos de clasificación aplicados al conjunto de datos , la Tau de Kendall entre y se puede representar de la siguiente manera: ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$

${\displaystyle \tau (r_{1},r_{2})={P-Q \over P+Q}=1-{2Q \over P+Q}}$

donde es el número de pares concordantes y es el número de pares discordantes (inversiones). Un par y es concordante si ambos y concuerdan en cómo se ordenan y . Es discordante si no están de acuerdo. ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle d_{i}}$ ${\displaystyle d_{j}}$ ${\displaystyle r_{a}}$ ${\displaystyle r_{b}}$ ${\displaystyle d_{i}}$ ${\displaystyle d_{j}}$

Calidad de recuperación de información[5][6][7]

La calidad de la recuperación de información generalmente se evalúa mediante las tres medidas siguientes:

1. Precisión
2. Recordar
3. Precisión media

Para una consulta específica a una base de datos, sea el conjunto de elementos de información relevantes en la base de datos y sea el conjunto de elementos de información recuperados. Entonces, las tres mediciones anteriores se pueden representar de la siguiente manera: ${\displaystyle P_{relevant}}$ ${\displaystyle P_{retrieved}}$

${\displaystyle {\begin{aligned}&{\text{precision}}={\frac {\left|P_{\text{relevant}}\cap P_{\text{retrieved}}\right|}{\left|P_{\text{retrieved}}\right|}};\\[6pt]&{\text{recall}}={\frac {\left|P_{\text{relevant}}\cap P_{\text{retrieved}}\right|}{\left|P_{\text{relevant}}\right|}};\\[6pt]&{\text{average precision}}=\int _{0}^{1}{\text{Prec}}({\text{recall}})\,d{\text{recall}},\\\end{aligned}}}$

¿Dónde está el de ? ${\displaystyle {\text{Prec}}({\text{Recall}})}$ ${\displaystyle {\text{Precision}}}$ ${\displaystyle {\text{Recall}}}$

Sean y sean los métodos de clasificación esperados y propuestos de una base de datos respectivamente, el límite inferior de la precisión promedio del método se puede representar de la siguiente manera: ${\displaystyle r^{*}}$ ${\displaystyle r_{f(q)}}$ ${\displaystyle r_{f(q)}}$

${\displaystyle \operatorname {AvgPrec} (r_{f(q)})\geqq {1 \over R}\left[Q+{\binom {R+1}{2}}\right]^{-1}\left(\sum _{i=1}^{R}{\sqrt {i}}\right)^{2}}$

donde es el número de elementos diferentes en las partes triangulares superiores de las matrices de y y es el número de elementos relevantes en el conjunto de datos. ${\displaystyle Q}$ ${\displaystyle r^{*}}$ ${\displaystyle r_{f(q)}}$ ${\displaystyle R}$

Clasificador SVM[8]

Supongamos que es el elemento de un conjunto de datos de entrenamiento, donde es el vector de características y es la etiqueta (que clasifica la categoría de ). Un clasificador SVM típico para dicho conjunto de datos se puede definir como la solución del siguiente problema de optimización. ${\displaystyle ({\vec {x}}_{i},y_{i})}$ ${\displaystyle {\vec {x}}_{i}}$ ${\displaystyle y_{i}}$ ${\displaystyle {\vec {x}}_{i}}$

${\displaystyle {\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+CF\sum \xi _{i}^{\sigma }\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\sigma \geqq 0;\\\forall y_{i}({\vec {w}}{\vec {x}}_{i}+b)\geqq 1-\xi _{i}^{\sigma };\end{array}}\\[6pt]&\mathrm {where} \\[6pt]&{\begin{array}{l}b{\text{ is a scalar;}}\\\forall y_{i}\in \left\{-1,1\right\};\\\forall \xi _{i}\geqq 0;\\\end{array}}\end{aligned}}}$

La solución del problema de optimización anterior se puede representar como una combinación lineal de los vectores de características s. ${\displaystyle x_{i}}$

${\displaystyle {\vec {w}}^{*}=\sum _{i}\alpha _{i}y_{i}x_{i}}$

donde están los coeficientes a determinar. ${\displaystyle \alpha _{i}}$

Algoritmo de clasificación SVM

Función de pérdida

Sea la tau de Kendall entre el método de clasificación esperado y el método propuesto , se puede demostrar que maximizar ayuda a minimizar el límite inferior de la precisión promedio de . ${\displaystyle \tau _{P(f)}}$ ${\displaystyle r^{*}}$ ${\displaystyle r_{f(q)}}$ ${\displaystyle \tau _{P(f)}}$ ${\displaystyle r_{f(q)}}$

• Función de pérdida esperada ^[9]

Se puede seleccionar el negativo como función de pérdida para minimizar el límite inferior de la precisión promedio de ${\displaystyle \tau _{P(f)}}$ ${\displaystyle r_{f(q)}}$

${\displaystyle L_{\text{expected}}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})\,dPr(q,r^{*})}$

¿Dónde está la distribución estadística de para cierta consulta ? ${\displaystyle Pr(q,r^{*})}$ ${\displaystyle r^{*}}$ ${\displaystyle q}$

• Función de pérdida empírica

Dado que la función de pérdida esperada no es aplicable, se selecciona la siguiente función de pérdida empírica para los datos de entrenamiento en la práctica.

${\displaystyle L_{\text{empirical}}=-\tau _{S}(f)=-{1 \over n}\sum _{i=1}^{n}\tau (r_{f(q_{i})},r_{i}^{*})}$

Recopilación de datos de entrenamiento

${\displaystyle n}$ Las consultas iid se aplican a una base de datos y cada consulta corresponde a un método de clasificación. El conjunto de datos de entrenamiento tiene elementos. Cada elemento contiene una consulta y el método de clasificación correspondiente. ${\displaystyle n}$

Espacio de características

Puntos etiquetados en el espacio de características

Se requiere una función de mapeo ^{[10] [11]} para mapear cada consulta y el elemento de la base de datos a un espacio de características. Luego, cada punto en el espacio de características se etiqueta con un rango determinado mediante un método de clasificación. ${\displaystyle \Phi (q,d)}$

Problema de optimización

Los puntos generados por los datos de entrenamiento se encuentran en el espacio de características, que también contiene la información de rango (las etiquetas). Estos puntos etiquetados se pueden utilizar para encontrar el límite (clasificador) que especifica su orden. En el caso lineal, dicho límite (clasificador) es un vector.

Supongamos que y son dos elementos en la base de datos y denotan si el rango de es más alto que en cierto método de clasificación . Sea vector el candidato a clasificador lineal en el espacio de características. Entonces, el problema de clasificación se puede traducir al siguiente problema de clasificación SVM. Tenga en cuenta que un método de clasificación corresponde a una consulta. ${\displaystyle c_{i}}$ ${\displaystyle c_{j}}$ ${\displaystyle (c_{i},c_{j})\in r}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{j}}$ ${\displaystyle r}$ ${\displaystyle {\vec {w}}}$

${\displaystyle {\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+{\text{constant}}\cdot \sum \xi _{i,j,k}\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\forall \xi _{i,j,k}\geqq 0\\\forall (c_{i},c_{j})\in r_{k}^{*}\\{\vec {w}}(\Phi (q_{1},c_{i})-\Phi (q_{1},c_{j}))\geqq 1-\xi _{i,j,1};\\\,\,\,\vdots \\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\{\text{where }}k\in \left\{1,2,\ldots ,n\right\},\ i,j\in \left\{1,2,\ldots \right\}.\end{array}}\end{aligned}}}$

El problema de optimización anterior es idéntico al problema de clasificación SVM clásico, razón por la cual este algoritmo se llama Ranking-SVM.

Candidato W

No soy un candidato

Función de recuperación

El vector óptimo obtenido por la muestra de entrenamiento es ${\displaystyle {\vec {w}}^{*}}$

${\displaystyle {\vec {w}}^{*}=\sum \alpha _{k,\ell }^{*}\Phi (q_{k},c_{i})}$

Por lo tanto, la función de recuperación podría formarse en función de dicho clasificador óptimo.
Para una nueva consulta , la función de recuperación primero proyecta todos los elementos de la base de datos en el espacio de características. Luego, ordena estos puntos de características por los valores de sus productos internos con el vector óptimo. Y el rango de cada punto de característica es el rango del elemento correspondiente de la base de datos para la consulta . ${\displaystyle q}$ ${\displaystyle q}$

Aplicación del sistema de clasificación SVM

El algoritmo SVM de clasificación se puede aplicar para clasificar las páginas según la consulta. El algoritmo se puede entrenar utilizando datos de clics, que consta de las tres partes siguientes:

1. Consulta.
2. Ranking actual de resultados de búsqueda
3. Resultados de búsqueda en los que hizo clic el usuario

La combinación de 2 y 3 no puede proporcionar el orden completo de los datos de entrenamiento que se necesita para aplicar el algoritmo SVM completo. En cambio, proporciona una parte de la información de clasificación de los datos de entrenamiento. Por lo tanto, el algoritmo se puede revisar ligeramente de la siguiente manera.

${\displaystyle {\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+{\text{constant}}\cdot \sum \xi _{i,j,k}\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\forall \xi _{i,j,k}\geqq 0\\\forall (c_{i},c_{j})\in r_{k}'\\{\vec {w}}(\Phi (q_{1},c_{i})-\Phi (q_{1},c_{j}))\geqq 1-\xi _{i,j,1};\\\,\,\,\vdots \\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\{\text{where }}\ k\in \left\{1,2,\ldots ,n\right\},\ i,j\in \left\{1,2,\ldots \right\}.\end{array}}\end{aligned}}}$

El método no proporciona información de clasificación de todo el conjunto de datos, sino que es un subconjunto del método de clasificación completo. Por lo tanto, la condición del problema de optimización se vuelve más relajada en comparación con el método de clasificación SVM original. ${\displaystyle r'}$

Referencias

1. Joachims, T. (2002), "Optimización de motores de búsqueda mediante datos de clics", Actas de la Conferencia de la ACM sobre descubrimiento de conocimiento y minería de datos
2. Bing Li; Rong Xiao; Zhiwei Li; Rui Cai; Bao-Liang Lu; Lei Zhang; "Rank-SIFT: Aprendiendo a clasificar puntos de interés locales repetibles", Visión artificial y reconocimiento de patrones (CVPR) , 2011
3. M. Kemeny. Métodos de correlación de rangos, Hafner , 1955
4. A. Mood, F. Graybill y D. Boes. Introducción a la teoría de la estadística . McGraw-Hill, 3.ª edición, 1974.
5. J. Kemeny y L. Snell. Modelos matemáticos en las ciencias sociales. Ginn & Co. 1962
6. Y. Yao. "Medición de la eficacia de la recuperación basada en las preferencias de los usuarios respecto de los documentos". Journal of the American Society for Information Science , 46(2): 133–145, 1995.
7. R. Baeza-Yates y B. Ribeiro-Neto. Recuperación de información moderna . Addison-Wesley-Longman, Harlow, Reino Unido, mayo de 1999
8. C. Cortes y VN Vapnik. "Redes de vectores de soporte". Machine Learning Journal , 20: 273–297, 1995
9. V. Vapnik. Teoría del aprendizaje estadístico . WILEY, Chichester, GB, 1998
10. N. Fuhr. "Funciones óptimas de recuperación polinómica basadas en el principio de clasificación de probabilidad". ACM TRANSACTIONS on Information Systems , 7(3): 183–204
11. N. Fuhr, S. Hartmann, G. Lustig, M. Schwantner, K. Tzeras y G. Knorz. "Air/x: un sistema de indexación multietapa basado en reglas para campos temáticos amplios". En RIAO, 1991