Campo aleatório de Markov

No domínio da física e da probabilidade, um campo aleatório de Markov (muitas vezes abreviado como MRF), rede de Markov ou modelo gráfico não-direcionado é um conjunto de variáveis aleatórias que possuem uma propriedade de Markov descrita por um grafo não-direcionado. Em outras palavras, um campo aleatório é dito ser de Markov se o mesmo satisfaz as propriedades de Markov.

Uma rede de Markov ou MRF é semelhante a uma rede bayesiana na sua representação de dependências; as diferenças sendo que as redes Bayesian são dirigidas e acíclicas, ao passo que as redes de Markov estão sem direção e podem ser cíclica. Assim, uma rede de Markov pode representar certas dependências que uma rede Bayesiana não pode (como dependências cíclicas); Por outro lado, não pode representar certas dependências que uma rede pode Bayesiana (tais como dependências induzidas). O gráfico subjacente de um campo aleatório de Markov pode ser finito ou infinito.

Quando a densidade de probabilidade conjunta das variáveis aleatórias é estritamente positiva, ela é também referida como um campo aleatório de Gibbs, porque, de acordo com o teorema de Hammersley-Clifford, ele pode então ser representada por uma medida de Gibbs para uma apropriada (definida localmente) função de energia. O campo aleatório de Markov prototípico é o modelo Ising; de fato, o campo aleatório de Markov foi introduzido como a configuração geral para o modelo Ising.

No domínio da inteligência artificial, um campo aleatório de Markov é usado para modelar tarefas de baixo a médio nível de processamento de imagem e visão computacional.

Definição

Dado um grafo não direcionado $G=(V,E)$, um conjunto de variáveis aleatórias $X=(X_{v})_{v\in V}$ indexadas por $V$  formam um campo aleatório de Markov com relação a $G$ se satisfizerem as propriedades de Markov:

Propriedade de Markov dos pares

Quaisquer duas variáveis não adjacentes são condicionalmente independentes, dado que todas as outras variáveis:

$X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\setminus \{u,v\}}\quad {\text{if }}\{u,v\}\notin E$

Propriedade de Markov local

Uma variável é condicionalmente independente de todas as outras variáveis, dados os seus vizinhos:

$X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {cl} (v)}\mid X_{\operatorname {ne} (v)}$

onde $\operatorname {ne} (v)$ é o conjunto de vizinhos de $v$ e $\operatorname {cl} (v)=v\cup \operatorname {ne} (v)$ é a vizinhança de $v$.

Propriedade de Markov global

Quaisquer dois subconjuntos de variáveis são condicionalmente independentes dado a separação do subconjunto:

$X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}$

onde cada caminho de um nó em $A$ para um nó em $B$ passa por $S$.

As três propriedades de Markov acima não são equivalentes: a propriedade de Markov local é mais forte do que a dos pares e mais fraca do que a global.

Fatoração clique

Como as propriedades de Markov de uma distribuição de probabilidade arbitrária podem ser difíceis de se estabelecer, uma classe comumente usada de campos aleatórios de Markov são aquelas que podem ser fatorado de acordo com os cliques do grafo.

Dado um conjunto de variáveis aleatórias $X=(X_{v})_{v\in V}$, seja $P(X=x)$ a probabilidade de uma configuração de campo particular de $x$ em $X$. Isto é, $P(X=x)$ é a probabilidade de encontrar as variáveis aleatórias $X$ assumindo o valor particular $x$. Como $X$ é um conjunto, a probabilidade de $x$ deve ser compreendida como relacionada a uma distribuição conjunta de $X_{v}$.

Se este conjunto de densidade pode ser fatorizado sobre os cliques de $G$:

$P(X=x)=\prod _{C\in \operatorname {cl} (G)}\phi _{C}(x_{C})$

então $X$ forma um campo aleatório de Markov com relação a $G$. Aqui, $\operatorname {cl} (G)$ é o conjunto de cliques de $G$. A definição é equivalente apenas se o máximo de cliques são utilizados. As funções φ_C são por vezes referidas como fator de potenciais ou clique potenciais. Note, no entanto, o conflito entre a terminologia em uso: a palavra potencial é muitas vezes aplicada ao logaritmo de φ_C. Isso porque, em mecânica estatística, log(φ_C) tem uma interpretação direta como a energia potencial de uma configuração $x_{C}$.

Embora alguns MRFs não fatorem (um exemplo simples pode ser construído em um ciclo de 4 nós), em certos casos, pode ser mostrado para ser equivalentes dadas certas condições:

• se a densidade for positiva (pelo teorema Hammersley-Clifford),
• se o gráfico é de cordas (por equivalência a uma rede bayesiana).

Quando tal fatoração existir, é possível construir um grafo fator para a rede.

Modelo logístico

Qualquer campo aleatório de Markov (com uma densidade estritamente positiva) pode ser escrito como um modelo log-linear com funções $f_{k}$ de tal forma que a distribuição conjunta pode ser escrita como

$P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)$

onde a notação

$w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})$

é simplesmente um produto do ponto sobre o campo de configurações, e Z é a função de partição:

$Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)$

Aqui, ${\mathcal {X}}$ denota o conjunto de todas as atribuições possíveis de valores para todas as variáveis aleatórias da rede. Geralmente, as funções $f_{k,i}$ são definidas de tal modo que elas são indicadoras da configuração do clique, isto é $f_{k,i}(x_{\{k\}})=1$ if $x_{\{k\}}$ corresponde a i-ésima configuração possível do k-ésimo clique e 0 caso contrário. Esse modelo é equivalente ao de fatoração clique dado acima, se $N_{k}=|\operatorname {dom} (C_{k})|$ é a cardinalidade do clique, e o peso de $f_{k,i}$ corresponde ao do logaritmo do fator clique correspondente, isto é, $w_{k,i}=\log \phi (c_{k,i})$, onde $c_{k,i}$ é a i-ésima configuração do k-ésimo clique, isto é, o i-ésimo valor no domínio do clique $C_{k}$.

A probabilidade P é muitas vezes chamada de medida de Gibbs. Esta expressão de um campo de Markov como um modelo logístico só é possível se todos os fatores do clique são não-nulos, ou seja, se nenhum dos elementos de ${\mathcal {X}}$ é atribuída uma probabilidade de 0. Isso permite que técnicas de álgebra matricial sejam aplicadas, por exemplo, que o traço de uma matriz é o log do determinante, com a matriz de representação de um grafo decorrendo do grafo da matriz de incidência.

A importância da função de partição Z é que muitos conceitos de mecânica estatística, tais como entropia, diretamente generalizam para o caso de redes de Markov, e uma intuitiva compreensão pode, assim, ser adquirida. Além disso, a função de partição permite serem aplicados métodos variacionais para a solução do problema: pode-se anexar uma força motriz para uma ou mais das variáveis aleatórias, e explorar a reação da rede em resposta a esta perturbação. Assim, por exemplo, pode-se adicionar um termo de condução J_v, para cada vértice v do grafo, para a função de partição para obter:

$Z[J]=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})+\sum _{v}J_{v}x_{v}\right)$

Diferenciando formalmente com respeito a J_v oferece o valor esperado da variável aleatória X_v associado com o vértice v:

$E[X_{v}]={\frac {1}{Z}}\left.{\frac {\partial Z[J]}{\partial J_{v}}}\right|_{J_{v}=0}$

As funções de correlação são calculadas da mesma forma; a correlação de dois pontos é:

$C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}$

Modelos log-lineares são especialmente convenientes para a interpretação. Um modelo log-linear pode fornecer uma representação mais compacta para muitas distribuições, especialmente quando as variáveis têm grandes domínios. Eles são convenientes também porque as verossimilhanças negativas são convexas. Infelizmente, embora a verossimilhança de uma rede de Markov logística ser convexa, avaliando-se a probabilidade ou o gradiente da probabilidade de um modelo requer inferência no modelo, que é geralmente impraticável.

Exemplos

Gaussiana

Uma distribuição normal multivariada forma um campo aleatório de Markov em relação a um grafo $G=(V,E)$ se as arestas faltantes correspondem aos zeros na matriz de precisão (a inversa da matriz de covariância):

$X=(X_{v})_{v\in V}\sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )$

de tal forma que

$(\Sigma ^{-1})_{uv}=0\quad {\text{if}}\quad \{u,v\}\notin E$.

Inferência

Como em uma rede bayesiana, pode-se calcular a distribuição condicional de um conjunto de nós $V'=\{v_{1},\ldots ,v_{i}\}$ dados valores para outro conjunto de nós $W'=\{w_{1},\ldots ,w_{j}\}$ em um campo aleatório de Markov ao somar todas as possíveis atribuições de $u\notin V',W'$; isso é chamado de inferência exata. No entanto, a exata inferência é um problema #P-completo, e, portanto, computacionalmente intratável no caso geral. Técnicas de aproximação, tais como Monte Carlo via cadeia de Markov e propagação de crença em ciclos são muitas vezes mais viáveis na prática. Algumas subclasses de campos aleatórios de Markov, tais como árvores, possuem algoritmos de inferência de tempo polinomial; a descoberta de tais subclasses é um ativo tema de pesquisa. Há também subclasses de campos aleatórios de Markov que permitem eficiência máxima a posteriori, ou inferência; exemplos destes incluem redes associativas. Outra interessante sub-classe é a de modelos decomponíveis (quando o grafo é cordal): tendo uma forma fechada para a MLE, é possível descobrir uma estrutura consistente para centenas de variáveis.

Campos aleatórios condicionais

Uma variante notável de um campo aleatório de Markov é um campo aleatório condicional, em que cada variável aleatória pode também ser condicionada a um conjunto de observações globais $o$. Neste modelo, cada função $\phi _{k}$ é um mapeamento de todas as atribuições para ambos o clique k e as observações $o$ para os números reais não-negativos. Esta forma de rede de Markov pode ser mais apropriada para a produção de classificadores discriminatórios, que não modelam a distribuição através de observações. Campos aleatórios condicionais foram propostos por John D. Lafferty, Andrew McCallum e Fernando C. N. Pereira , em 2001.

Aplicações variadas

Campos aleatórios de Markov encontram aplicação em uma variedade de campos, variando de gráficos de computador para visão computacional e aprendizado de máquina. Campos aleatórios de Markov são utilizados no processamento de imagem para gerar texturas pois eles podem ser usados para gerar modelos de imagens flexíveis e estocásticos. Na modelação de imagem, a tarefa é encontrar uma distribuição de intensidade adequada de uma determinada imagem, onde a adequação depende do tipo de tarefa e campos aleatórios de Markov são flexíveis o suficiente para serem usados para síntese da imagem e textura, compressão de imagem e de restauração, segmentação de imagens, reconstrução de superfície, registo de imagem, síntese de textura, super-resolução, correspondência estéreo e recuperação de informação. Eles podem ser usados para resolver vários problemas de visão computacional que podem ser colocadas como problemas de minimização de energia ou problemas onde as diferentes regiões têm que ser distinguidas utilizando um conjunto de características de discriminação dentro de um quadro de campo aleatório de Markov, para prever a categoria da região. Campos aleatórios de Markov foram uma generalização sobre o modelo Ising e tem, desde então, sido amplamente usado na otimizações combinatória de redes.

Veja também

• Sistemas de partícula em interação
• Modelo Ising
• Cadeias de Markov
• Máxima Entropia

Ligações externas

• MRF implementation in C++ for regular 2D lattices