Los campos aleatorios condicionales ( CRF ) son una clase de método de modelado estadístico que a menudo se aplica en el reconocimiento de patrones y el aprendizaje automático y se utiliza 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, la predicción se modela como un modelo gráfico , que implementa dependencias entre las predicciones. El tipo de gráfico que se utilice depende de la aplicación. Por ejemplo, en el procesamiento del lenguaje naturalLos CRF de cadena lineal son populares, que implementan dependencias secuenciales en las predicciones. En el procesamiento de imágenes, el gráfico normalmente conecta ubicaciones con ubicaciones cercanas y / o similares para hacer cumplir que reciben predicciones similares.
Otros ejemplos en los que se utilizan los CRF son: etiquetado o análisis sintáctico de datos secuenciales para el procesamiento del lenguaje natural o secuencias biológicas , [1] etiquetado POS , análisis superficial , [2] reconocimiento de entidades con nombre , [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 discriminativo no dirigido .
Lafferty , McCallum y Pereira [1] definen un CRF en observacionesy variables aleatorias como sigue:
Dejar ser un grafo tal que
, así que eso está indexado por los vértices de . Luego es un campo aleatorio condicional cuando las variables aleatorias , condicionado a , obedece la propiedad de Markov con respecto al gráfico:, dónde significa que y son vecinos en.
Lo que esto significa es que un CRF es un modelo gráfico no dirigido cuyos nodos se pueden dividir en exactamente dos conjuntos disjuntos. y , las variables observadas y de salida, respectivamente; la distribución condicional luego se modela.
Inferencia
Para gráficos generales, el problema de la inferencia exacta en los CRF es insoluble. 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 que es factible una inferencia exacta:
- 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 usar 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
Aprendiendo los parámetros generalmente se realiza mediante el 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 estas variables. La inferencia exacta es intratable en gráficos generales, por lo que se deben utilizar aproximaciones.
Ejemplos de
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 debe inferirse dadas las observaciones. La están estructurados para formar una cadena, con un borde entre cada y . Además de tener una interpretación simple de la como "etiquetas" para cada elemento en la secuencia de entrada, este diseño admite algoritmos eficientes para:
- modelo de entrenamiento , aprendiendo las distribuciones condicionales entre los y funciones de características de algún corpus de datos de entrenamiento.
- decodificación , determinando la probabilidad de una secuencia de etiquetas dada dado .
- inferencia , determinando la secuencia de etiquetas más probable dado .
La dependencia condicional de cada en se define a través de un conjunto fijo de funciones características de la forma, que se puede considerar como medidas en 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 los combina para determinar la probabilidad de un cierto valor para.
Los CRF de cadena lineal tienen muchas de las mismas aplicaciones que los modelos de Markov ocultos (HMM) conceptualmente más simples, pero relajan ciertos supuestos 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 en 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 de características, las funciones de características pueden inspeccionar toda la secuencia de entrada. en cualquier punto durante la inferencia, y el rango de funciones de características no necesita tener una interpretación probabilística.
Variantes
CRF de orden superior y CRF semi-Markov
Los CRF se pueden extender a modelos de orden superior haciendo que cada dependiente 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.
Sin embargo, otro avance reciente ha logrado mejorar estos problemas aprovechando conceptos y herramientas del campo de los no paramétricos bayesianos. Específicamente, 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 mediante la introducción de una función potencial novedosa para los CRF que se basa en el 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 del, a un costo computacional razonable.
Por último, los modelos de gran margen para la predicción estructurada , como la máquina de vectores de soporte estructurado, 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ísticos discriminativos ( DPLVM ) son un tipo de CRF para tareas de etiquetado de secuencias. Son modelos de variables latentes que se entrenan discriminativamente.
En un LDCRF, como en cualquier tarea de etiquetado de secuencia, 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 un CRF de cadena lineal ordinaria haría, un conjunto de variables latentes h se "insertada" entre x y y utilizando el regla de la cadena de la probabilidad : [13]
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 de perceptrón llamado perceptrón de variable latente , basado en el algoritmo de 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 secuencias de video [14] y el análisis sintáctico superficial . [13]
Software
Esta es una lista parcial de software que implementa herramientas CRF genéricas.
- RNNSharp CRFs basados en redes neuronales recurrentes ( C # , .NET )
- CRF-ADF CRF de cadena lineal con formación rápida de ADF en línea ( C # , .NET )
- CRFSharp CRF de cadena lineal ( C # , .NET )
- GCO CRF con funciones de energía submodular ( C ++ , Matlab )
- DGM CRF generales ( C ++ )
- CRF generales de GRMM ( Java )
- fábricas CRF generales ( Scala )
- CRF de caída general ( Matlab )
- CRF de cadena lineal CRF de Sarawagi ( Java )
- Biblioteca HCRF CRF de estado oculto ( C ++ , Matlab )
- Accord.NET CRF, HCRF y HMM de cadena lineal ( C # , .NET )
- CRF de cadena lineal rápida Wapiti ( C ) [15]
- CRFSuite CRF de cadena lineal restringida rápida ( C )
- CRF ++ CRF de cadena lineal ( C ++ )
- FlexCRFs CRF de Markov de primer y segundo orden ( C ++ )
- crf-chain1 CRF de cadena lineal de primer orden ( Haskell )
- imageCRF CRF para segmentar imágenes y volúmenes de imágenes ( C ++ )
- MALLET Cadena lineal para etiquetado de secuencias ( Java )
- Aprendizaje estructurado de PyStruct en Python ( Python )
- Pycrfsuite Un enlace de Python para crfsuite ( Python )
- Figaro Lenguaje de programación probabilístico capaz de definir CRF y otros modelos gráficos ( Scala )
- Herramientas computacionales y de modelado de CRF para CRF y otros modelos gráficos no dirigidos ( R )
- Biblioteca OpenGM para modelos de gráficos de factores discretos y operaciones distributivas en estos modelos ( C ++ )
- UPGMpp [5] Biblioteca para construir, entrenar y realizar inferencias con modelos gráficos no dirigidos ( C ++ )
- KEG_CRF CRF lineales rápidos ( C ++ )
Esta es una lista parcial de software que implementa herramientas relacionadas con CRF.
- Reconocedor de entidades nombradas de MedaCy Medical ( Python )
- Predictor de genes basado en Conrad CRF ( Java )
- Reconocedor de entidad con nombre Stanford NER ( Java )
- BANNER Reconocimiento de entidades con nombre ( Java )
Ver también
- Teorema de Hammersley-Clifford
- Modelo grafico
- Campo aleatorio de Markov
- Modelo de Markov de máxima entropía (MEMM)
Referencias
- ↑ a b Lafferty, J., McCallum, A., Pereira, F. (2001). "Campos aleatorios condicionales: modelos probabilísticos para segmentar y etiquetar datos de secuencia" . Proc. 18a Conf. Internacional sobre aprendizaje automático . Morgan Kaufmann. págs. 282-289.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Sha, F .; Pereira, F. (2003). análisis superficial con campos aleatorios condicionales .
- ^ Se instala, B. (2004). "El reconocimiento Biomédica entidad llamada usando campos aleatorios condicionales y conjuntos de características rico" (PDF) . Actas del Taller conjunto internacional sobre procesamiento del lenguaje natural en biomedicina y sus aplicaciones . págs. 104-107.
- ^ 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. doi : 10.1371 / journal.pone.0119490 . PMC 4372350 .
- ^ a b JR Ruiz-Sarmiento; C. Galindo; J. González-Jiménez (2015). "UPGMpp: una biblioteca de software para el reconocimiento contextual de objetos". . 3er. Taller de Reconocimiento y Acción para la Comprensión de Escenas (REACTS) .
- ^ Él, X .; Zemel, RS; Carreira-Perpinñán, MA (2004). "Campos aleatorios condicionales multiescala para etiquetado de imágenes". Sociedad de Informática IEEE. CiteSeerX 10.1.1.3.7826 .
- ^ a b Sutton, Charles; McCallum, Andrew (2010). "Una introducción a los campos aleatorios condicionales". arXiv : 1011.4088v1 [ stat.ML ].
- ^ Lavergne, Thomas; Yvon, François (7 de septiembre de 2017). "Aprendizaje de la estructura de los CRF de orden variable: una perspectiva de estado finito" . 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.
- ^ Chatzis, Sotirios; Demiris, Yiannis (2013). "El modelo de campo aleatorio condicional de orden infinito para el modelado de datos secuenciales". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 35 (6): 1523-1534. doi : 10.1109 / tpami.2012.208 . hdl : 10044/1/12614 . PMID 23599063 .
- ^ Gasthaus, Jan; Teh, Yee Whye (2010). "Mejoras en el Sequence Memoizer" (PDF) . Proc. NIPS .
- ^ Celeux, G .; Forbes, F .; Peyrard, N. (2003). "Procedimientos EM utilizando aproximaciones de campo medio para la segmentación de imágenes basada en el modelo de Markov". Reconocimiento de patrones . 36 (1): 131-144. CiteSeerX 10.1.1.6.9064 . doi : 10.1016 / s0031-3203 (02) 00027-4 .
- ^ Sarawagi, Sunita; Cohen, William W. (2005). "Campos aleatorios condicionales Semi-Markov para extracción de información" (PDF) . En Lawrence K. Saul; Yair Weiss; Léon Bottou (eds.). Avances en los sistemas de procesamiento de información neuronal 17 . Cambridge, MA: MIT Press. págs. 1185-1192.
- ^ a b c Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Algoritmo de perceptrón variable latente para clasificación estructurada . IJCAI. págs. 1236-1242.
- ^ a b Morency, LP; Quattoni, A .; Darrell, T. (2007). "Modelos discriminativos dinámicos latentes para el reconocimiento continuo de gestos" (PDF) . 2007 Conferencia IEEE sobre visión artificial y reconocimiento de patrones . pag. 1. CiteSeerX 10.1.1.420.6836 . doi : 10.1109 / CVPR.2007.383299 . ISBN 978-1-4244-1179-5.
- ^ T. Lavergne, O. Cappé y F. Yvon (2010). CRF prácticos a muy gran escala Archivado el 18 de julio de 2013 en la Wayback Machine . Proc. 48ª Reunión Anual de la ACL , págs. 504-513.
Otras lecturas
- McCallum, A .: Inducción eficiente de características de campos aleatorios condicionales . En: Proc. XIX Congreso 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 relacional estadístico". 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 Ciencias de la Computación, Universidad Tecnológica de Dortmund, diciembre de 2007. ISSN 1864-4503. PDF en línea