Campo aleatório de Markov - Markov random field

Um exemplo de um campo aleatório de Markov.
Um exemplo de um campo aleatório de Markov. Cada borda representa dependência. Neste exemplo: A depende de B e D. B depende de A e D. D depende de A, B e E. E depende de D e C. C depende de E.

No domínio da física e da probabilidade , um campo aleatório de Markov ( MRF ), rede de Markov ou modelo gráfico não direcionado é um conjunto de variáveis ​​aleatórias com uma propriedade de Markov descrita por um gráfico não direcionado . Em outras palavras, um campo aleatório é considerado um campo aleatório de Markov se ele satisfizer as propriedades de Markov.

Uma rede Markov ou MRF é semelhante a uma rede Bayesiana em sua representação de dependências; as diferenças são que as redes bayesianas são direcionadas e acíclicas , enquanto as redes de Markov são não direcionadas e podem ser cíclicas. 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 bayesiana pode representar (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 , ela pode então ser representada por uma medida de Gibbs para um apropriado (definido localmente) função de energia. O campo aleatório de Markov prototípico é o modelo de Ising ; na verdade, o campo aleatório de Markov foi introduzido como o cenário geral para o modelo de Ising. No domínio da inteligência artificial , um campo aleatório de Markov é usado para modelar várias tarefas de nível baixo a médio em processamento de imagem e visão computacional .

Definição

Dado um gráfico não direcionado , um conjunto de variáveis ​​aleatórias indexadas por   forma um campo aleatório de Markov em relação a   se eles satisfazem as propriedades de Markov locais:

Propriedade de Markov pairwise: Quaisquer duas variáveis ​​não adjacentes são condicionalmente independentes, dadas todas as outras variáveis:
Propriedade local de Markov: uma variável é condicionalmente independente de todas as outras variáveis, dados seus vizinhos:
onde está o conjunto de vizinhos de , e é a vizinhança fechada de .
Propriedade Markov global: quaisquer dois subconjuntos de variáveis ​​são condicionalmente independentes, dado um subconjunto de separação:
onde cada caminho de um nó em para um nó em passa .

A propriedade Global Markov é mais forte do que a propriedade Local Markov, que por sua vez é mais forte do que a Pairwise. No entanto, as três propriedades de Markov acima são equivalentes para distribuições positivas (aquelas que atribuem apenas probabilidades diferentes de zero às variáveis ​​associadas).

Fatoração de Clique

Como a propriedade de Markov de uma distribuição de probabilidade arbitrária pode ser difícil de estabelecer, uma classe comumente usada de campos aleatórios de Markov são aqueles que podem ser fatorados de acordo com os cliques do gráfico.

Dado um conjunto de variáveis ​​aleatórias , seja a probabilidade de uma configuração de campo particular em  . Ou seja, é a probabilidade de descobrir que as variáveis ​​aleatórias assumem o valor particular . Por ser um conjunto, a probabilidade de deve ser entendida como sendo considerada com relação a uma distribuição conjunta de .

Se esta densidade de junta pode ser fatorada sobre os cliques de :

em seguida, forma um campo aleatório de Markov em relação a . Aqui está o conjunto de cliques de . A definição é equivalente se apenas cliques máximos forem usados. As funções às vezes são chamadas de potenciais de fator ou potenciais de clique . Observe, entretanto, que terminologia conflitante está em uso: a palavra potencial é freqüentemente aplicada ao logaritmo de . Isso porque, na mecânica estatística , tem uma interpretação direta como a energia potencial de uma configuração .  

Alguns MRF's não fatoram: um exemplo simples pode ser construído em um ciclo de 4 nós com algumas energias infinitas, ou seja, configurações de probabilidades zero, mesmo que uma, mais apropriadamente, permita que as energias infinitas atuem no gráfico completo .

O MRF fatoriza se pelo menos uma das seguintes condições for atendida:

Quando tal fatoração existe, é possível construir um gráfico de fator para a rede.

Família exponencial

Qualquer campo aleatório de Markov positivo pode ser escrito como família exponencial na forma canônica com funções de característica de modo que a distribuição full-joint pode ser escrita como

onde a notação

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

Aqui, denota o conjunto de todas as atribuições possíveis de valores para todas as variáveis ​​aleatórias da rede. Normalmente, as funções de característica são definidas de modo que sejam indicadores da configuração do clique, ou seja , se corresponde à i -ésima configuração possível do k- ésimo clique e 0 caso contrário. Este modelo é equivalente ao modelo de fatoração de clique dado acima, se é a cardinalidade do clique, e o peso de uma característica corresponde ao logaritmo do fator de clique correspondente, ou seja , onde é a i -ésima configuração possível do k - o clique, ou seja , o i -ésimo valor no domínio do clique .

A probabilidade P é freqüentemente 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 de clique forem diferentes de zero, ou seja , se nenhum dos elementos de forem atribuídos a uma probabilidade de 0. Isso permite que técnicas de álgebra de matriz sejam aplicadas, por exemplo , que o traço de uma matriz é o log do determinante , com a representação da matriz de um gráfico surgindo da matriz de incidência do gráfico .

A importância da função de partição Z é que muitos conceitos da mecânica estatística , como a entropia , se generalizam diretamente para o caso das redes de Markov, e assim pode-se obter um entendimento intuitivo . Além disso, a função de partição permite que métodos variacionais sejam aplicados à solução do problema: pode-se atribuir uma força motriz a uma ou mais das variáveis ​​aleatórias e explorar a reação da rede em resposta a essa perturbação . Assim, por exemplo, pode-se adicionar um termo condutor J v , para cada vértice v do gráfico, à função de partição para obter:

A diferenciação formal em relação a J v dá o valor esperado da variável aleatória X v associada ao vértice v :

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

Infelizmente, embora a probabilidade de uma rede de Markov logística seja convexa, avaliar a probabilidade ou gradiente da probabilidade de um modelo requer inferência no modelo, que geralmente é computacionalmente inviável (consulte 'Inferência' abaixo).

Exemplos

Gaussiana

Uma distribuição normal multivariada forma um campo aleatório de Markov em relação a um gráfico se as arestas ausentes corresponderem a zeros na matriz de precisão (a matriz de covariância inversa ):

de tal modo que

Inferência

Como em uma rede Bayesiana, pode-se calcular a distribuição condicional de um conjunto de nós com valores dados a outro conjunto de nós no campo aleatório de Markov pela soma de todas as atribuições possíveis a ; isso é chamado de inferência exata . No entanto, a inferência exata é um problema # P-completo e, portanto, computacionalmente intratável no caso geral. As técnicas de aproximação, como a cadeia de Markov Monte Carlo e a propagação de crenças malucas, costumam ser mais viáveis ​​na prática. Algumas subclasses particulares de MRFs, como árvores (ver árvore de Chow-Liu ), têm algoritmos de inferência de tempo polinomial; descobrir tais subclasses é um tópico de pesquisa ativo. Existem também subclasses de MRFs que permitem a inferência de MAP eficiente , ou mais provavelmente de atribuição; exemplos disso incluem redes associativas. Outra subclasse interessante é a dos modelos decomponíveis (quando o gráfico é cordal ): tendo uma forma fechada para o MLE , é possível descobrir uma estrutura consistente para centenas de variáveis.

Campos aleatórios condicionais

Uma variação notável de um campo aleatório de Markov é um campo aleatório condicional , no qual cada variável aleatória também pode ser condicionada a um conjunto de observações globais . Neste modelo, cada função é um mapeamento de todas as atribuições ao clique k e das observações aos números reais não negativos. Esta forma da rede de Markov pode ser mais apropriada para produzir classificadores discriminativos , que não modelam a distribuição sobre as observações. Os CRFs foram propostos por John D. Lafferty , Andrew McCallum e Fernando CN Pereira em 2001.

Aplicativos variados

Os campos aleatórios de Markov encontram aplicação em uma variedade de campos, desde computação gráfica até visão computacional, aprendizado de máquina ou biologia computacional . Os MRFs são usados ​​no processamento de imagens para gerar texturas, pois podem ser usados ​​para gerar modelos de imagem flexíveis e estocásticos. Na modelagem de imagens, a tarefa é encontrar uma distribuição de intensidade adequada de uma determinada imagem, onde a adequação depende do tipo de tarefa e os MRFs são flexíveis o suficiente para serem usados ​​para síntese de imagem e textura, compressão e restauração de imagem , segmentação de imagem , imagem 3D inferência de imagens 2D, registro de imagem , síntese de textura , super-resolução , correspondência estéreo e recuperação de informações . Eles podem ser usados ​​para resolver vários problemas de visão computacional que podem ser apresentados como problemas de minimização de energia ou problemas onde diferentes regiões devem ser distinguidas usando um conjunto de recursos discriminantes, dentro de uma estrutura de campo aleatório de Markov, para prever a categoria da região. Os campos aleatórios de Markov foram uma generalização do modelo de Ising e, desde então, têm sido amplamente usados ​​em otimizações combinatórias e redes.

Veja também

Referências