Campo aleatorio condicional

Clase de métodos de modelado estadístico

Los campos aleatorios condicionales ( CRF ) son una clase de métodos de modelado estadístico que se aplican a menudo en el reconocimiento de patrones y el aprendizaje automático y se utilizan para la predicción estructurada . Mientras que un clasificador predice una etiqueta para una sola muestra sin considerar las muestras "vecinas", un CRF puede tener en cuenta el contexto. Para ello, las predicciones se modelan como un modelo gráfico , que representa la presencia de dependencias entre las predicciones. El tipo de gráfico que se utiliza depende de la aplicación. Por ejemplo, en el procesamiento del lenguaje natural , son populares los CRF de "cadena lineal", para los cuales cada predicción depende solo de sus vecinos inmediatos. En el procesamiento de imágenes, el gráfico normalmente conecta ubicaciones con ubicaciones cercanas y/o similares para garantizar que reciban predicciones similares.

Otros ejemplos en los que se utilizan CRF son: etiquetado o análisis de datos secuenciales para el procesamiento del lenguaje natural o secuencias biológicas , ^[1] etiquetado de partes del discurso , análisis superficial , ^[2] reconocimiento de entidades nombradas , ^[3] búsqueda de genes , búsqueda de regiones funcionales críticas de péptidos, ^[4] y reconocimiento de objetos ^[5] y segmentación de imágenes en visión artificial . ^[6]

Descripción

Los CRF son un tipo de modelo gráfico probabilístico no dirigido y discriminativo .

Lafferty , McCallum y Pereira ^[1] definen un CRF sobre observaciones y variables aleatorias de la siguiente manera: ${\displaystyle {\boldsymbol {X}}}$ ${\displaystyle {\boldsymbol {Y}}}$

Sea un grafo tal que , de modo que esté indexado por los vértices de . ${\displaystyle G=(V,E)}$ ${\displaystyle {\boldsymbol {Y}}=({\boldsymbol {Y}}_{v})_{v\in V}}$ ${\displaystyle {\boldsymbol {Y}}}$ ${\displaystyle G}$

Entonces es un campo aleatorio condicional cuando cada variable aleatoria , condicionada a , obedece la propiedad de Markov con respecto al gráfico; es decir, su probabilidad depende sólo de sus vecinos en G: ${\displaystyle ({\boldsymbol {X}},{\boldsymbol {Y}})}$ ${\displaystyle {\boldsymbol {Y}}_{v}}$ ${\displaystyle {\boldsymbol {X}}}$

${\displaystyle P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\neq v\})=P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\sim v\})}$, donde significa que y son vecinos en . ${\displaystyle {\mathit {w}}\sim v}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle G}$

Lo que esto significa es que un CRF es un modelo gráfico no dirigido cuyos nodos se pueden dividir exactamente en dos conjuntos disjuntos y , las variables observadas y de salida, respectivamente; luego se modela la distribución condicional. ${\displaystyle {\boldsymbol {X}}}$ ${\displaystyle {\boldsymbol {Y}}}$ ${\displaystyle p({\boldsymbol {Y}}|{\boldsymbol {X}})}$

Inferencia

En el caso de los grafos generales, el problema de la inferencia exacta en las CRF es insoluble. El problema de inferencia para una CRF es básicamente el mismo que para una MRF y se aplican los mismos argumentos. ^[7] Sin embargo, existen casos especiales en los que es factible la inferencia exacta:

• Si el gráfico es una cadena o un árbol, los algoritmos de paso de mensajes proporcionan soluciones exactas. Los algoritmos utilizados en estos casos son análogos al algoritmo de avance-retroceso y al algoritmo de 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 no es posible realizar una inferencia exacta, se pueden utilizar varios algoritmos para obtener soluciones aproximadas. Entre ellos se incluyen:

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

Aprendizaje de parámetros

El aprendizaje de los parámetros se realiza generalmente mediante el aprendizaje de máxima verosimilitud para . Si todos los nodos tienen distribuciones familiares exponenciales y todos los nodos 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 Quasi-Newton como el algoritmo L-BFGS . Por otro lado, si algunas variables no se observan, el problema de inferencia debe resolverse para estas variables. La inferencia exacta es intratable en gráficos generales, por lo que deben usarse aproximaciones. ${\displaystyle \theta }$ ${\displaystyle p(Y_{i}|X_{i};\theta )}$

Ejemplos

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

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

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

Los CRF de cadena lineal tienen muchas de las mismas aplicaciones que los modelos ocultos de Markov (HMM), conceptualmente más simples, pero relajan ciertas suposiciones sobre las distribuciones de secuencia de entrada y salida. Un HMM puede entenderse libremente como un CRF con funciones de características muy específicas que utilizan probabilidades constantes para modelar las transiciones de estado y las emisiones. Por el contrario, un CRF puede entenderse libremente como una generalización de un HMM que convierte las probabilidades de transición constantes en funciones arbitrarias que varían a lo largo de las posiciones en la secuencia de estados ocultos, dependiendo de la secuencia de entrada.

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

Variantes

CRF de orden superior y CRF semi-Markov

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

Sin embargo, otro avance reciente ha logrado mejorar estos problemas aprovechando conceptos y herramientas del campo de la no parametría bayesiana. En concreto, el enfoque CRF-infinity ^[9] constituye un modelo de tipo CRF que es capaz de aprender dinámicas temporales infinitamente largas de forma escalable. Esto se logra introduciendo una nueva función potencial para CRF que se basa en el Memorizador de Secuencia (SM), un modelo bayesiano no paramétrico para aprender dinámicas infinitamente largas en observaciones secuenciales. ^[10] Para que un modelo de este tipo sea computacionalmente manejable, CRF-infinity emplea una aproximación de campo medio ^[11] de las nuevas funciones potenciales postuladas (que son impulsadas por un SM). Esto permite diseñar algoritmos de entrenamiento e inferencia aproximados eficientes para el modelo, sin socavar su capacidad para capturar y modelar dependencias temporales de longitud arbitraria.

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

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

Campo aleatorio condicional latente-dinámico

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

${\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 perceptrón llamado perceptrón de variable latente , basado en el algoritmo perceptrón estructurado de Collins . ^[13] Estos modelos encuentran aplicaciones en la visión por computadora , específicamente el reconocimiento de gestos a partir de transmisiones de video ^[14] y el análisis superficial . ^[13]

Véase también

• Teorema de Hammersley-Clifford
• Modelo de Markov de máxima entropía (MEMM)

Referencias

1. Lafferty, J.; McCallum, A.; Pereira, F. (2001). "Campos aleatorios condicionales: modelos probabilísticos para segmentar y etiquetar datos de secuencias". Proc. 18.ª Conferencia Internacional sobre Aprendizaje Automático . Morgan Kaufmann. págs. 282–289.
2. Sha, F.; Pereira, F. (2003). Análisis superficial con campos aleatorios condicionales.
3. Settles, B. (2004). "Reconocimiento de entidades con nombre biomédico mediante campos aleatorios condicionales y conjuntos de características enriquecidos" (PDF) . Actas del Taller conjunto internacional sobre procesamiento del lenguaje natural en biomedicina y sus aplicaciones . pp. 104–107.
4. Chang KY; Lin Tp; Shih LY; Wang CK (2015). "Análisis y predicción de las regiones críticas de péptidos antimicrobianos basados ​​en campos aleatorios condicionales". PLOS ONE . ​​10 (3): e0119490. Bibcode :2015PLoSO..1019490C. doi : 10.1371/journal.pone.0119490 . PMC 4372350 . PMID  25803302. 
5. JR Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez (2015). "UPGMpp: una librería de software para el reconocimiento de objetos contextuales". 3er. Taller sobre Reconocimiento y Acción para la Comprensión de Escenas (REACTS) .
6. He, X. ; Zemel, RS; Carreira-Perpinñán, MA (2004). "Campos aleatorios condicionales multiescala para etiquetado de imágenes". IEEE Computer Society. CiteSeerX 10.1.1.3.7826 . 
7. Sutton, Charles; McCallum, Andrew (2010). "Introducción a los campos aleatorios condicionales". arXiv : 1011.4088v1 [stat.ML].
8. Lavergne, Thomas; Yvon, François (7 de septiembre de 2017). "Aprendizaje de la estructura de CRF de orden variable: una perspectiva de estados finitos". Actas de la Conferencia de 2017 sobre métodos empíricos en el procesamiento del lenguaje natural . Copenhague, Dinamarca: Asociación de Lingüística Computacional. pág. 433.
9. Chatzis, Sotirios; Demiris, Yiannis (2013). "El modelo de campo aleatorio condicional de orden infinito para el modelado secuencial de datos". IEEE Transactions on Pattern Analysis and Machine Intelligence . 35 (6): 1523–1534. doi :10.1109/tpami.2012.208. hdl : 10044/1/12614 . PMID  23599063. S2CID  690627.
10. Gasthaus, Jan; Teh, Yee Whye (2010). "Mejoras en el Memorizador de secuencias" (PDF) . Proc. NIPS .
11. Celeux, G.; Forbes, F.; Peyrard, N. (2003). "Procedimientos EM que utilizan aproximaciones similares a campos medios para la segmentación de imágenes basada en modelos de Markov". Reconocimiento de patrones . 36 (1): 131–144. Bibcode :2003PatRe..36..131C. CiteSeerX 10.1.1.6.9064 . doi :10.1016/s0031-3203(02)00027-4. 
12. Sarawagi, Sunita ; Cohen, William W. (2005). "Campos aleatorios condicionales semimarkovianos para la extracción de información". En Lawrence K. Saul; Yair Weiss; Léon Bottou (eds.). Avances en sistemas de procesamiento de información neuronal 17. Cambridge, MA: MIT Press. págs. 1185–1192. Archivado desde el original (PDF) el 2019-11-30 . Consultado el 2015-11-12 .
13. Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Algoritmo de perceptrón de variable latente para clasificación estructurada. IJCAI. págs. 1236–1242. Archivado desde el original el 2018-12-06 . Consultado el 2018-12-06 .
14. Morency, LP; Quattoni, A.; Darrell, T. (2007). "Modelos discriminatorios dinámicos latentes para el reconocimiento continuo de gestos" (PDF) . Conferencia IEEE de 2007 sobre visión artificial y reconocimiento de patrones . pág. 1. CiteSeerX 10.1.1.420.6836 . doi :10.1109/CVPR.2007.383299. ISBN.  978-1-4244-1179-5. Número de identificación del sujeto  7117722.

Lectura adicional

• McCallum, A.: Inducción eficiente de características de campos aleatorios condicionales. En: Proc. 19th Conference on Uncertainty in Artificial Intelligence . (2003)
• Wallach, HM : Campos aleatorios condicionales: una introducción. Informe técnico MS-CIS-04-21, Universidad de Pensilvania (2004)
• Sutton, C., McCallum, A.: Introducción a los campos aleatorios condicionales para el aprendizaje relacional. En "Introducción al aprendizaje relacional estadístico". Editado por Lise Getoor y Ben Taskar. MIT Press. (2006) PDF en línea
• Klinger, R., Tomanek, K.: Modelos probabilísticos clásicos y campos aleatorios condicionales. Informe de ingeniería de algoritmos TR07-2-013, Departamento de Ciencias de la Computación, Universidad Tecnológica de Dortmund, diciembre de 2007. ISSN 1864-4503. PDF en línea