Campo aleatorio condicional

Un campo aleatorio condicional (Conditional Random Field o CRF en inglés) es un modelo estocástico utilizado habitualmente para etiquetar y segmentar secuencias de datos o extraer información de documentos. En algunos contextos también se lo denomina campo aleatorio de Márkov (inglés: Markov random Fields, MRF).

Concepto

Dada una secuencia de datos ${\displaystyle O_{1},...O_{N}}$  este modelo asigna una etiqueta ${\displaystyle S_{i}}$  para cada elemento ${\displaystyle O_{i}}$ . Aunque presenta similitudes con los modelos ocultos de Márkov, estos son modelos generativos que modelan conjuntamente la distribución de probabilidad de las etiquetas (o estados) y las observaciones, ${\displaystyle P(S,O)}$ , mientras que los campos aleatorios condicionales modelan la probabilidad de la secuencia correcta de etiquetas condicionada por las observaciones, ${\displaystyle P(S|O)}$ , es decir, son modelos discriminativos.

Se puede representar con un grafo no dirigido ${\displaystyle G=(V,E)\,}$  en el que cada vértice represente una variable aleatoria cuya distribución de probabilidad debe ser deducida, y cada arista indique una dependencia entre las variables de los vértices que conecta. El grafo obedece la propiedad de Márkov extendida a grafos:

${\displaystyle P(S_{i}|O,S_{j};i\neq j)=P(S_{i}|O,S_{j};S_{i}\sim S_{j})}$ 

donde ${\displaystyle \sim }$  significa que los vértices ${\displaystyle S_{i}}$  y ${\displaystyle S_{j}}$  están conectados por una arista. En cuanto a los datos ${\displaystyle O_{i}}$ , también llamados observaciones, lo más frecuente es que sean también una secuencia. Además, es frecuente que cada ${\displaystyle O_{i}}$  sea un vector, no un valor escalar, en cuyo caso tendríamos observaciones multimensionales.

El grafo puede tener una estructura arbitrariamente compleja, aunque lo más común es que sea una cadena o un "rejilla". En una cadena, cada vértice está únicamente conectado con el vértice predecesor y con sus sucesor (se asume que los vértices están ordenados). En una rejilla, cada vértice está conectado con otros 4, excepto en los extremos; un vértice ${\displaystyle S_{ij}}$  estará conectado con ${\displaystyle S_{i,j-1},S_{i,j+1},S_{i-1,j}}$  y ${\displaystyle S_{i+1,j}}$ . En el caso de la cadena la propiedad de Márkov puede reescribirse de la siguiente forma:

${\displaystyle P(S_{i}|O,S_{j};i\neq j)=P(S_{i}|O,S_{j};S_{i-1},S_{i+1})}$ 

Entrenamiento y uso

Estos modelos necesitan ser entrenados con N muestras ${\displaystyle (O^{(i)},S^{(i)})_{N}^{1}}$ ; cada una contiene un conjunto de observaciones así como las etiquetas asociadas a esas observaciones. El modelo extrae un conjunto de características ${\displaystyle f(i,S_{i},S_{i+1})}$  y ${\displaystyle g(i,S_{i},O)}$  que representan las dependencias existentes entre diferentes estados y entre estos y la secuencia de observaciones. Al contrario que en los modelos ocultos de Márkov en donde cada estado ${\displaystyle S_{i}}$  depende únicamente de la observación ${\displaystyle O_{i}}$ , aquí cada estado puede depender de varias observaciones al mismo tiempo, incluso de la secuencia completa si fuese necesario. En el entrenamiento del modelo éste asigna unos pesos a cada una de esas características, indicando su relativa importancia según el caso. Puesto que el entrenamiento puede ser muy costoso en tiempo y en espacio, lo habitual es usar algoritmos de optimización numérica, como el denominado L-BFGS. En cuanto al uso, el algoritmo de Viterbi de los modelos ocultos de Márkov puede ser adaptado con facilidad. También se puede usar el algoritmo de propagación de creencias (belief propagation en inglés).

Herramientas

Algunas implementaciones de este modelo son las siguientes:

 * MALLET, en Java * , en C++ * Implementación de K.Murphy, en Matlab * Implementación de S.Sarawagi, en Java 

Referencias

• Lafferty, J., McCallum, A., Pereira, F.: Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In: Proc. 18th International Conf. on Machine Learning, Morgan Kaufmann, San Francisco, CA (2001) 282–289
• McCallum, A.: Efficiently inducing features of conditional random fields. In: Proc. 19th Conference on Uncertainty in Artificial Intelligence. (2003)
• Sha, F., Pereira, F.: Shallow parsing with conditional random fields. Technical Report MS-CIS-02-35, University of Pennsylvania (2003)
• Wallach, H.M.: Conditional random fields: An introduction. Technical Report MS-CIS-04-21, University of Pennsylvania (2004)
• Sutton, C., McCallum, A.: An Introduction to Conditional Random Fields for Relational Learning. In "Introduction to Statistical Relational Learning". Edited by Lise Getoor and Ben Taskar. MIT Press. (2006)
• Wang, Y., Loe, K.F., Wu, J.K.: A dynamic conditional random field model for foreground and shadow segmentation. IEEE Trans Pattern Anal Mach Intell. 28(2):279-89 (2006)

•   Datos: Q1124538