Camp aleatori condicional

Un camp aleatori condicional (Conditional Random Field o CRF en anglés) és un model estocàstic utilisat habitualment per a etiquetar i segmentar seqüències de senyes o extraure informació de documents. En alguns contexts també li'l denomina camp aleatori de Márkov (anglés: Markov random Fields, MRF).

Concepte

Donada una seqüència de senyes $O_1,\mathrm{...}{O}_N$ este model assigna una etiqueta $S_i$ per a cada element $O_i$. Encara que presenta similituts en els models amagats de Márkov, estos són models generativos que modelen conjuntament la distribució de provabilitat de les etiquetes (o estats) i les observacions, $P(S,O)$, mentres que els camps aleatoris condicionals modelen la provabilitat de la seqüència correcta d'etiquetes condicionada per les observacions, $P(S|O)$, és dir, són models discriminativos.

Es pot representar en un grafo no dirigit $G=(V,E)$ en el que cada vèrtiç represente una variable aleatòria la distribució de la qual de provabilitat deu ser deduïda, i cada aresta indique una dependència entre les variables dels vèrtiços que conecta. El grafo obedix la propietat de Márkov estesa a grafos:

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

a on $\sim$ significa que els vèrtiços $S_i$ i $S_j$ estan conectats per una aresta. Sobre les senyes $O_i$, també cridats observacions, lo més freqüent és que siguen també una seqüència. Ademés, és freqüent que cada $O_i$ siga un vector, no un valor escalar, en el cas del qual tindríem observacions multimensionales.

El grafo pot tindre una estructura arbitrariamente complexa, encara que lo més comuna és que siga una cadena o un "reixeta". En una cadena, cada vèrtiç està únicament conectat en el vèrtiç predecessor i en els seus successor (s'assumix que els vèrtiços estan ordenats). En una reixeta, cada vèrtiç està conectat en atres 4, llevat en els extrems; un vèrtiç $S_{ij}$ estarà conectat en $S_{i,j-1},S_{i,j+1},S_{i-1,j}$ i $S_{i+1,j}$. En el cas de la cadena la propietat de Márkov pot reescriure's de la següent forma:

$P(S_i|O,S_j;i\ne j)=P(S_i|O,S_j;S_{i-1},S_{i+1})$

Entrenament i us

Estos models necessiten ser entrenats en N mostres $(O^{(i)},S^{(i)}{)}_N^1$; cada una conté un conjunt d'observacions aixina com les etiquetes associades a eixes observacions. El model extrau un conjunt de característiques $f(i,S_i,S_{i+1})$ i $g(i,S_i,O)$ que representen les dependències existents entre diferents estats i entre estos i la seqüència d'observacions. Al contrari que en els models amagats de Márkov en a on cada estat $S_i$ depén únicament de l'observació $O_i$, ací cada estat pot dependre de vàries observacions al mateix temps, inclús de la seqüència completa si fora necessari. En l'entrenament del model este assigna uns pesos a cada una d'eixes característiques, indicant la seua relativa importància segons el cas. ya que l'entrenament pot ser molt costós en temps i en espai, lo habitual és usar algoritmes d'optimisació numèrica, com el denominat L-BFGS. Sobre l'us, l'algoritme de Viterbi dels models amagats de Márkov pot ser adaptat en facilitat. També es pot usar l'algoritme de propagació de creències (belief propagation en anglés).