Modelo condicional restringido

Un modelo condicional restringido (CCM) es un marco de aprendizaje automático e inferencia que amplía el aprendizaje de modelos condicionales (probabilísticos o discriminativos) mediante restricciones declarativas. Estas restricciones permiten incorporar conocimiento previo expresivo al modelo y orientar las asignaciones del modelo aprendido para que satisfagan dichas restricciones. El marco facilita la toma de decisiones en un espacio de salida expresivo, manteniendo la modularidad y la manejabilidad del entrenamiento y la inferencia.

Los modelos de este tipo han atraído recientemente mucha atención dentro de la comunidad de procesamiento del lenguaje natural ( PLN ). Formular problemas como problemas de optimización con restricciones sobre la salida de modelos aprendidos tiene varias ventajas. Permite centrarse en el modelado de problemas al brindar la oportunidad de incorporar conocimiento específico del dominio como restricciones globales utilizando un lenguaje de primer orden. El uso de este marco declarativo libera al desarrollador de la ingeniería de características de bajo nivel , al tiempo que captura las propiedades específicas del dominio del problema y garantiza una inferencia exacta. Desde una perspectiva de aprendizaje automático, permite desacoplar la etapa de generación del modelo (aprendizaje) de la etapa de inferencia con restricciones, lo que ayuda a simplificar la etapa de aprendizaje y a mejorar la calidad de las soluciones. Por ejemplo, en el caso de generar oraciones comprimidas, en lugar de simplemente confiar en un modelo de lenguaje para conservar los n-gramas más utilizados en la oración, se pueden usar restricciones para asegurar que si se conserva un modificador en la oración comprimida, también se conservará su sujeto.

La toma de decisiones en muchos ámbitos (como el procesamiento del lenguaje natural y los problemas de visión artificial ) suele implicar la asignación de valores a conjuntos de variables interdependientes, donde la estructura de dependencia expresiva puede influir, o incluso determinar, las asignaciones posibles. Estas configuraciones son aplicables no solo a problemas de aprendizaje estructurado, como el etiquetado de roles semánticos, sino también a casos que requieren el uso de múltiples componentes preaprendidos, como la generación de resúmenes, la inferencia textual y la respuesta a preguntas . En todos estos casos, resulta natural formular el problema de decisión como un problema de optimización con restricciones, cuya función objetivo se compone de modelos aprendidos, sujetos a restricciones específicas del dominio o del problema.

Los modelos condicionales restringidos forman un marco de aprendizaje e inferencia que amplía el aprendizaje de modelos condicionales (probabilísticos o discriminativos) con restricciones declarativas (escritas, por ejemplo, utilizando una representación de primer orden) como una forma de apoyar las decisiones en un espacio de salida expresivo, manteniendo la modularidad y la manejabilidad del entrenamiento y la inferencia. Estas restricciones pueden expresar restricciones estrictas, prohibiendo completamente algunas asignaciones, o restricciones flexibles, penalizando las asignaciones improbables. En la mayoría de las aplicaciones de este marco en PLN, siguiendo ^{[ 1 ]} , se utilizó la Programación Lineal Entera (PLE) como marco de inferencia, aunque se pueden utilizar otros algoritmos para ese propósito.

Dado un conjunto de funciones de características${\displaystyle \{\phi _{i}(x,y)\}}$y un conjunto de restricciones${\displaystyle \{C_{i}(x,y)\}}$, definido sobre una estructura de entrada${\displaystyle x\in X}$y una estructura de salida ${\displaystyle y\in Y}$, un modelo condicional de restricción se caracteriza por dos vectores de peso, w y${\displaystyle \rho }$y se define como la solución al siguiente problema de optimización:

${\displaystyle argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)}$.

Cada restricción ${\displaystyle C_{i}\in C}$ es una asignación booleana que indica si la asignación conjunta${\displaystyle (x,y)}$viola una restricción y${\displaystyle \rho }$es la penalización por violar las restricciones. Las restricciones con una penalización infinita se conocen como restricciones estrictas y representan asignaciones inviables para el problema de optimización.

Las ventajas de la formulación declarativa CCM y la disponibilidad de solucionadores listos para usar han llevado a que se formulen dentro del marco una gran variedad de tareas de procesamiento del lenguaje natural , incluyendo el etiquetado de roles semánticos , ^{[ 7 ]} el análisis sintáctico, ^{[ 8 ]} la resolución de correferencias , ^{[ 9 ]} la generación de resúmenes, ^{[ 10 ] [ 11 ] [ 12 ]} la transliteración , ^{[ 13 ]} la generación de lenguaje natural ^{[ 14 ]} y la extracción conjunta de información . ^{[ 15 ] [ 16 ]}

La mayoría de estos trabajos utilizan un solucionador de programación lineal entera (PLI) para resolver el problema de decisión. Si bien teóricamente la resolución de un programa lineal entero es exponencial en función del tamaño del problema de decisión, en la práctica, utilizando solucionadores de última generación y técnicas de inferencia aproximada ^{[ 17 ],} se pueden resolver problemas de gran escala de manera eficiente.

La principal ventaja de utilizar un solucionador de programación lineal entera (PLI) para resolver el problema de optimización definido por un modelo condicional con restricciones es la formulación declarativa utilizada como entrada para el solucionador de PLI, que consiste en una función objetivo lineal y un conjunto de restricciones lineales.

• Tutorial de CCM : Predicción de estructuras en PLN: Modelos condicionales restringidos y programación lineal entera en PLN

• Grupo de Computación Cognitiva de la Universidad de Illinois
• Taller sobre programación lineal entera para el procesamiento del lenguaje natural, NAACL-2009