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 a menudo se aplican 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 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 , los CRF de "cadena lineal" son populares, en los que cada predicción depende únicamente 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 procesamiento del lenguaje natural o secuencias biológicas , ^[1] etiquetado de parte del discurso , análisis superficial , ^[2] reconocimiento de entidades nombradas , ^[3] búsqueda de genes , péptido crítico búsqueda de regiones funcionales, ^[4] y reconocimiento de objetos ^[5] y segmentación de imágenes en visión por computadora . ^[6]

Descripción

Los CRF son un tipo de modelo gráfico probabilístico no dirigido 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 gráfico 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 a la propiedad de Markov con respecto a la gráfica; 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

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

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

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

Aprendizaje de parámetros

El aprendizaje de los parámetros generalmente se realiza mediante aprendizaje de máxima probabilidad para . Si todos los nodos tienen distribuciones familiares exponenciales y todos los nodos se observan durante el entrenamiento, esta optimización es convexa. ^[7] Puede resolverse, 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 esas variables. La inferencia exacta es intratable en gráficos generales, por lo que se deben utilizar 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 en cadena. Una secuencia de entrada de variables observadas representa una secuencia de observaciones y representa una variable de estado oculta (o desconocida) que debe inferirse dadas las observaciones. Están estructurados para formar una cadena, con un borde entre cada uno y . Además de tener una interpretación sencilla de las "etiquetas" para cada elemento de 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 , aprendiendo las distribuciones condicionales entre las funciones y características de algún corpus de datos de entrenamiento. ${\displaystyle Y_{i}}$
• decodificación , determinando la probabilidad de una determinada 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 uno se define a través de un conjunto fijo de funciones características de la forma , que pueden considerarse como mediciones de la secuencia de entrada que determinan parcialmente la probabilidad de cada valor posible de . El modelo asigna a cada característica un peso numérico y los combina para determinar la probabilidad de un determinado 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 en términos generales como un CRF con funciones características muy específicas que utilizan probabilidades constantes para modelar transiciones de estado y emisiones. Por el contrario, un CRF puede entenderse en términos generales como una generalización de un HMM que convierte las probabilidades de transición constantes en funciones arbitrarias que varían entre 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 pueden ampliarse a modelos de orden superior haciendo que cada uno de ellos dependa de un número fijo de variables anteriores . En 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. Específicamente, el enfoque CRF-infinity ^[9] constituye un modelo tipo CRF que es capaz de aprender dinámicas temporales infinitamente largas de forma escalable. Esto se logra mediante la introducción de una nueva función potencial para los CRF que se basa en Sequence Memoizer (SM), un modelo bayesiano no paramétrico para aprender dinámicas infinitamente largas en observaciones secuenciales. ^[10] Para hacer que dicho modelo 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 inferencia y entrenamiento 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 verse como un procedimiento de entrenamiento alternativo a los CRF.

Campo aleatorio condicional dinámico latente

Los campos aleatorios condicionales dinámicos latentes ( LDCRF ) o los modelos de variables latentes probabilísticas discriminativas ( 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 = , el principal problema que debe resolver el modelo 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 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 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 del perceptrón llamado perceptrón de variable latente , basado en el algoritmo de perceptrón estructurado de Collins . ^[13] Estos modelos encuentran aplicaciones en visión por computadora , específicamente reconocimiento de gestos a partir de transmisiones de video ^[14] y análisis superficial . ^[13]

Ver 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 secuencia". Proc. XVIII Conferencia Internacional. sobre aprendizaje automático . Morgan Kaufman. págs. 282–289.
2. Sha, F.; Pereira, F. (2003). análisis superficial con campos aleatorios condicionales.
3. Se instala, B. (2004). "Reconocimiento de entidades biomédicas con nombre mediante campos aleatorios condicionales y conjuntos de funciones enriquecidos" (PDF) . Actas del taller conjunto internacional sobre procesamiento del lenguaje natural en biomedicina y sus aplicaciones . págs. 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". MÁS UNO . 10 (3): e0119490. Código Bib : 2015PLoSO..1019490C. doi : 10.1371/journal.pone.0119490 . PMC 4372350 . PMID  25803302. 
5. JR Ruiz-Sarmiento; C. Galindo; J. González-Jiménez (2015). "UPGMpp: una biblioteca de software para el reconocimiento de objetos contextuales". 3er. Taller de Reconocimiento y Acción para la Comprensión de la Escena (REACTS) .
6. Él, X .; Zemel, RS; Carreira-Perpinñán, MA (2004). "Campos aleatorios condicionales multiescala para etiquetado de imágenes". Sociedad de Computación IEEE. CiteSeerX 10.1.1.3.7826 . 
7. Sutton, Charles; McCallum, Andrés (2010). "Introducción a los campos aleatorios condicionales". arXiv : 1011.4088v1 [estad.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. pag. 433.
9. Chatzis, Sotirios; Demiris, Yiannis (2013). "El modelo de campos aleatorios condicionales de orden infinito para el modelado de datos secuenciales". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 35 (6): 1523-1534. doi :10.1109/tpami.2012.208. hdl : 10044/1/12614 . PMID  23599063. S2CID  690627.
10. Gasthaus, enero; 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. Código Bib : 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 Semi-Markov para extracción de información". En Lawrence K. Saúl; Yair Weiss; León Bottou (eds.). Avances en los sistemas de procesamiento de información neuronal 17. Cambridge, MA: MIT Press. págs. 1185-1192. Archivado desde el original (PDF) el 30 de noviembre de 2019 . Consultado el 12 de noviembre de 2015 .
13. Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Algoritmo de perceptrón de variables latentes para clasificación estructurada. IJCAI. págs. 1236-1242. Archivado desde el original el 6 de diciembre de 2018 . Consultado el 6 de diciembre de 2018 .
14. Morency, LP; Quattoni, A.; Darrell, T. (2007). "Modelos discriminativos dinámicos latentes para el reconocimiento continuo de gestos" (PDF) . Conferencia IEEE 2007 sobre visión por computadora y reconocimiento de patrones . pag. 1. CiteSeerX 10.1.1.420.6836 . doi :10.1109/CVPR.2007.383299. ISBN  978-1-4244-1179-5. S2CID  7117722.

Otras lecturas

• McCallum, A.: Inducción eficiente de características de campos aleatorios condicionales. En: Proc. XIX Jornada sobre Incertidumbre en Inteligencia Artificial . (2003)
• Wallach, HM : Campos aleatorios condicionales: una introducción. Informe técnico MS-CIS-04-21, Universidad de Pennsylvania (2004)
• Sutton, C., McCallum, A.: Introducción a los campos aleatorios condicionales para el aprendizaje relacional. En "Introducción al Aprendizaje Estadístico Relacional". Editado por Lise Getoor y Ben Taskar. Prensa del MIT. (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 Informática, Universidad Tecnológica de Dortmund, diciembre de 2007. ISSN 1864-4503. PDF en línea