Algoritmo relajado con margen incorporado

Algoritmo de aprendizaje automático

El algoritmo relajado con margen infundido (MIRA) ^[1] es un algoritmo de aprendizaje automático , un algoritmo en línea para problemas de clasificación multiclase . Está diseñado para aprender un conjunto de parámetros (vector o matriz) procesando todos los ejemplos de entrenamiento dados uno por uno y actualizando los parámetros de acuerdo con cada ejemplo de entrenamiento, de modo que el ejemplo de entrenamiento actual se clasifique correctamente con un margen contra clasificaciones incorrectas al menos tan grande como su pérdida. ^[2] El cambio de los parámetros se mantiene lo más pequeño posible.

Una versión de dos clases denominada MIRA binaria ^[1] simplifica el algoritmo al no requerir la solución de un problema de programación cuadrática (ver más abajo). Cuando se utiliza en una configuración de uno contra todos, MIRA binaria se puede extender a un aprendiz multiclase que se aproxima al MIRA completo, pero puede ser más rápido de entrenar.

El flujo del algoritmo ^{[3] [4]} se ve como sigue:

Algoritmo MIRA Entrada: Ejemplos de entrenamiento Salida: Conjunto de parámetros ${\displaystyle T=\{x_{i},y_{i}\}}$  ${\displaystyle w}$

  ${\displaystyle i}$← 0, ← 0 para ← 1 a para ← 1 a ← actualizar según ← fin para fin para volver ${\displaystyle w^{(0)}}$  ${\displaystyle n}$  ${\displaystyle N}$   ${\displaystyle t}$  ${\displaystyle |T|}$  ${\displaystyle w^{(i+1)}}$ ${\displaystyle w^{(i)}}$ ${\displaystyle \{x_{t},y_{t}\}}$  ${\displaystyle i}$ ${\displaystyle i+1}$     ${\displaystyle {\frac {\sum _{j=1}^{N\times |T|}w^{(j)}}{N\times |T|}}}$

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

El paso de actualización se formaliza entonces como un problema de programación cuadrática ^[2] : encontrar , de modo que , es decir, la puntuación del entrenamiento correcto actual debe ser mayor que la puntuación de cualquier otro posible por al menos la pérdida (número de errores) de ese en comparación con . ${\displaystyle min\|w^{(i+1)}-w^{(i)}\|}$ ${\displaystyle score(x_{t},y_{t})-score(x_{t},y')\geq L(y_{t},y')\ \forall y'}$ ${\displaystyle y}$ ${\displaystyle y'}$ ${\displaystyle y'}$ ${\displaystyle y}$

Referencias

1. Crammer, Koby; Singer, Yoram (2003). "Algoritmos en línea ultraconservadores para problemas multiclase". Revista de investigación en aprendizaje automático . 3 : 951–991.
2. McDonald, Ryan; Crammer, Koby; Pereira, Fernando (2005). "Entrenamiento en línea de gran margen de analizadores de dependencia" (PDF) . Actas de la 43.ª reunión anual de la ACL . Asociación de Lingüística Computacional . págs. 91–98.
3. Watanabe, T. et al (2007): "Entrenamiento en línea de amplio margen para traducción automática estadística". En: Actas de la Conferencia conjunta de 2007 sobre métodos empíricos en procesamiento del lenguaje natural y aprendizaje computacional del lenguaje natural , 764–773.
4. Bohnet, B. (2009): Análisis eficiente de estructuras de dependencia sintáctica y semántica . Actas de la Conferencia sobre aprendizaje de lenguajes naturales (CoNLL), Boulder, 67–72.

Enlaces externos

• adMIRAble – Implementación de MIRA en C++
• Miralium – Implementación de MIRA en Java
• Implementación de MIRA para Mahout en Hadoop