Campo aleatorio condicional

Para grafos generales, el problema de la inferencia exacta en CRF es intratable. El problema de inferencia para un CRF es básicamente el mismo que para un MRF y se aplican los mismos argumentos. ^{[ 7 ]} Sin embargo, existen casos especiales para los cuales la inferencia exacta es factible:

• Si el grafo es una cadena o un árbol, los algoritmos de paso de mensajes proporcionan soluciones exactas. Los algoritmos utilizados en estos casos son análogos a los algoritmos de avance-retroceso y Viterbi para el caso de los HMM.
• Si el CRF solo contiene potenciales por pares y la energía es submodular , los algoritmos combinatorios de corte mínimo/flujo máximo producen soluciones exactas.

Si la inferencia exacta es imposible, se pueden utilizar varios algoritmos para obtener soluciones aproximadas. Estos incluyen:

• Propagación de creencias absurdas
• Expansión alfa
• Inferencia de campo medio
• Relajaciones de programación lineal

Aprender los parámetros${\displaystyle \theta }$Por lo general, se realiza mediante aprendizaje de máxima verosimilitud para${\displaystyle p(Y_{i}|X_{i};\theta )}$Si todos los nodos tienen distribuciones de la familia exponencial y se observan durante el entrenamiento, esta optimización es convexa. ^{[ 7 ]} Se puede resolver, por ejemplo, utilizando algoritmos de descenso de gradiente o métodos cuasi-Newton como el algoritmo L-BFGS . Por otro lado, si algunas variables no se observan, el problema de inferencia debe resolverse para dichas variables. La inferencia exacta es intratable en grafos generales, por lo que se deben utilizar aproximaciones.

En el modelado de secuencias, el grafo de interés suele ser un grafo en cadena. Una secuencia de entrada de variables observadas${\displaystyle X}$representa una secuencia de observaciones y${\displaystyle Y}$representa una variable de estado oculta (o desconocida) que necesita ser inferida a partir de las observaciones.${\displaystyle Y_{i}}$están estructurados para formar una cadena, con un borde entre cada uno${\displaystyle Y_{i-1}}$y${\displaystyle Y_{i}}$Además de tener una interpretación sencilla de la${\displaystyle Y_{i}}$Como "etiquetas" para cada elemento en la secuencia de entrada, este diseño admite algoritmos eficientes para:

• entrenamiento del modelo , aprendizaje de las distribuciones condicionales entre las${\displaystyle Y_{i}}$y funciones de características a partir de un corpus de datos de entrenamiento.
• decodificación , determinación de la probabilidad de una secuencia de etiquetas dada${\displaystyle Y}$dado${\displaystyle X}$.
• inferencia , determinación de la secuencia de etiquetas más probable${\displaystyle Y}$dado${\displaystyle X}$.

La dependencia condicional de cada${\displaystyle Y_{i}}$en${\displaystyle X}$se define mediante un conjunto fijo de funciones de características de la forma${\displaystyle f(i,Y_{i-1},Y_{i},X)}$, que pueden considerarse como mediciones en la secuencia de entrada que determinan parcialmente la probabilidad de cada valor posible para${\displaystyle Y_{i}}$El modelo asigna a cada característica un peso numérico y las combina para determinar la probabilidad de un determinado valor para${\displaystyle Y_{i}}$.

Los CRF de cadena lineal comparten muchas aplicaciones con los modelos ocultos de Markov (HMM), conceptualmente más sencillos, pero flexibilizan ciertas suposiciones sobre las distribuciones de las secuencias de entrada y salida. Un HMM puede entenderse, en términos generales, como un CRF con funciones de características muy específicas que utilizan probabilidades constantes para modelar las transiciones y emisiones de estado. Por el contrario, un CRF puede entenderse, en términos generales, como una generalización de un HMM que transforma las probabilidades de transición constantes en funciones arbitrarias que varían según las posiciones en la secuencia de estados ocultos, en función de la secuencia de entrada.

Cabe destacar que, a diferencia de los HMM, los CRF pueden contener cualquier número de funciones de características, y estas funciones pueden inspeccionar toda la secuencia de entrada.${\displaystyle X}$en cualquier momento durante la inferencia, y el rango de las funciones de características no necesita tener una interpretación probabilística.

Los CRF se pueden extender a modelos de orden superior haciendo que cada${\displaystyle Y_{i}}$dependiente de un número fijo${\displaystyle k}$de variables previas${\displaystyle Y_{i-k},...,Y_{i-1}}$En las formulaciones convencionales de CRF de orden superior, el entrenamiento y la inferencia solo son prácticos para valores pequeños de${\displaystyle k}$(como k ≤ 5), ^{[ 8 ]} ya que su costo computacional aumenta exponencialmente con${\displaystyle k}$.

Sin embargo, un avance reciente ha logrado mitigar estos problemas aprovechando conceptos y herramientas del campo de la estadística bayesiana no paramétrica. Específicamente, el enfoque CRF-infinito ^{[ 9 ]} constituye un modelo tipo CRF capaz de aprender dinámicas temporales infinitamente largas de forma escalable. Esto se consigue introduciendo una nueva función potencial para CRF basada en el Memorizador de Secuencias (SM), un modelo bayesiano no paramétrico para aprender dinámicas infinitamente largas en observaciones secuenciales ^{[ 10 ]} . Para que dicho modelo sea computacionalmente viable, CRF-infinito emplea una aproximación de campo medio ^{[ 11 ]} de las nuevas funciones potenciales postuladas (que se basan en un SM). Esto permite diseñar algoritmos eficientes de entrenamiento e inferencia aproximados para el modelo, sin menoscabar su capacidad para capturar y modelar dependencias temporales de longitud arbitraria.

Existe otra generalización de los CRF, el campo aleatorio condicional semi-Markoviano (semi-CRF) , que modela segmentaciones de longitud variable de la secuencia de etiquetas.${\displaystyle Y}$. ^{[ 12 ]} Esto proporciona gran parte del poder de los CRF de orden superior para modelar dependencias de largo alcance de la${\displaystyle Y_{i}}$, a un coste computacional razonable.

Finalmente, los modelos de margen amplio para la predicción estructurada , como la máquina de vectores de soporte estructurada, pueden considerarse un procedimiento de entrenamiento alternativo a los CRF.

Los campos aleatorios condicionales dinámicos latentes ( LDCRF ) o los modelos de variables latentes probabilísticos discriminativos ( DPLVM ) son un tipo de CRF para tareas de etiquetado de secuencias. Son modelos de variables latentes que se entrenan de forma discriminativa.

En un LDCRF, como en cualquier tarea de etiquetado de secuencias, dada una secuencia de observaciones x =${\displaystyle x_{1},\dots ,x_{n}}$, el principal problema que debe resolver el modelo es cómo asignar una secuencia de etiquetas y =${\displaystyle y_{1},\dots ,y_{n}}$a partir de un conjunto finito de etiquetas Y. En lugar de modelar directamente P ( y | x ) como lo haría un CRF de cadena lineal ordinario, se "inserta" un conjunto de variables latentes h entre x e y utilizando la regla de la cadena de probabilidad : ^{[ 13 ]}

${\displaystyle P(\mathbf {y} |\mathbf {x} )=\sum _{\mathbf {h} }P(\mathbf {y} |\mathbf {h} ,\mathbf {x} )P(\mathbf {h} |\mathbf {x} )}$

Esto permite capturar la estructura latente entre las observaciones y las etiquetas. ^{[ 14 ]} Si bien los LDCRF se pueden entrenar utilizando métodos cuasi-Newton, también se ha desarrollado para ellos una versión especializada del algoritmo del perceptrón llamada perceptrón de variables latentes , basada en el algoritmo del perceptrón estructurado de Collins . ^{[ 13 ]} Estos modelos encuentran aplicaciones en visión artificial , específicamente en el reconocimiento de gestos a partir de secuencias de vídeo ^{[ 14 ]} y en el análisis superficial . ^{[ 13 ]}