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 les denomina campos aleatorios de Márkov (inglés: Markov random Fields,MRF).

Dada una secuencia de datos O₁,...O_N este modelo asigna una etiqueta S_i para cada elemento O_i. Aunque presenta similitudes con los modelos ocultos de Márkov, estos son modelos generativos que modelan connjuntamente la distribución de probabilidad de las etiquetas (o estados) y las observaciones, P(S,O), mientras que los campos aleatorios condicionales modelan la probabilidad de la secuencia correcta de etiquetas condicionada por las observaciones, P(S | O), es decir, son modelos discriminativos.

Se puede representar con un grafo no dirigido $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 extendía a grafos:

$P(S_i|O, S_j ; i \neq j) = P(S_i|O, S_j ; S_i \sim S_j)$

donde ∼ significa que los vértices S_i y S_j están conectados por una arista. En cuanto a los datos O_i, también llamados observaciones, lo más frecuente es que sean también una secuencia. Además, es frecuente que cada 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 S_ij estará conectado con S_{i,j − 1},S_{i,j + 1},S_{i − 1,j} y S_{i + 1,j}. En el caso de la cadena la propiedad de Márkov puede reescribirse de la siguiente forma:

$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 $(O^{(i)},S^{(i)})^1_N$; cada una contiene un conjunto de observaciones así como las etiquetas asociadas a esas observaciones. El modelo extrae un conjunto de características f(i,S_i,S_{i + 1}) y g(i,S_i,O) que representan las dependencia 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 S_i depende únicamente de la observación 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
   * CRF++, 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)