Campo aleatório de Markov

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ficheiro:Markov random field example.png
Um exemplo de um campo aleatório de Markov. Cada aresta 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 D e C. C depende E.

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.[1]. 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.[2]

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.[3]

Definição[editar | editar código-fonte]

Dado um grafo não direcionado , um conjunto de variáveis aleatórias indexadas por   formam um campo aleatório de Markov com relação a  se satisfizerem as propriedades de Markov:

Propriedade de Markov dos pares[editar | editar código-fonte]

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

Propriedade de Markov local[editar | editar código-fonte]

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

onde é o conjunto de vizinhos de e é a vizinhança de .

Propriedade de Markov global[editar | editar código-fonte]

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

onde cada caminho de um nó em para um nó em passa por .

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[editar | editar código-fonte]

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 , seja a probabilidade de uma configuração de campo particular de em . Isto é, é a probabilidade de encontrar as variáveis aleatórias assumindo o valor particular . Como é um conjunto, a probabilidade de deve ser compreendida como relacionada a uma distribuição conjunta de .

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

então forma um campo aleatório de Markov com relação a . Aqui, é o conjunto de cliques de . 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 .

Embora alguns MRFs não fatorem (um exemplo simples pode ser construído em um ciclo de 4 nós[4]), 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[editar | editar código-fonte]

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

onde a notação

é simplesmente um produto do ponto sobre o campo de configurações, 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. Geralmente, as funções são definidas de tal modo que elas são indicadoras da configuração do clique, isto é if 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 é a cardinalidade do clique, e o peso de corresponde ao do logaritmo do fator clique correspondente, isto é, , onde é a i-ésima configuração do k-ésimo clique, isto é, o i-ésimo valor no domínio do clique .

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 é 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 Jv, para cada vértice v do grafo, para a função de partição para obter:

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

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

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[editar | editar código-fonte]

Gaussiana[editar | editar código-fonte]

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

de tal forma que

.[5]

Inferência[editar | editar código-fonte]

Como em uma rede bayesiana, pode-se calcular a distribuição condicional de um conjunto de nós dados valores para outro conjunto de nós em um campo aleatório de Markov ao somar todas as possíveis atribuições de ; 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.[6][7] 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.[8]

Campos aleatórios condicionais[editar | editar código-fonte]

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 . Neste modelo, cada função é um mapeamento de todas as atribuições para ambos o clique k e as observações 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.[9]

Aplicações variadas[editar | editar código-fonte]

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.[10] 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.[11] 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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. SINAPE - Simpósio Nacional de Probabilidade e Estatística (julho de 2010). «Campos Aleatórios de Markov e Distribuições Especificadas Através das Densidades Condicionais». Consultado em 23 de janeiro de 2012. 
  2. Kindermann, Ross; Snell, J. Laurie (1980). Markov Random Fields and Their Applications (PDF) American Mathematical Society [S.l.] ISBN 0-8218-5001-6. MR 0620955. 
  3. Li, S. Z. (2009). Markov Random Field Modeling in Image Analysis Springer [S.l.] 
  4. Moussouris, John (1974). «Gibbs and Markov random systems with constraints». Journal of Statistical Physics [S.l.: s.n.] 10 (1): 11–33. doi:10.1007/BF01011714. MR 0432132. 
  5. Rue, Håvard; Held, Leonhard (2005). Gaussian Markov random fields: theory and applications CRC Press [S.l.] ISBN 1-58488-432-0. 
  6. Taskar, Benjamin; Chatalbashev, Vassil; Koller, Daphne (2004), "Learning associative Markov networks", in Brodley, Carla E., Proceedings of the Twenty-first International Conference on Machine Learning (ICML 2004), Banff, Alberta, Canada, July 4-8, 2004, ACM International Conference Proceeding Series, 69, Association for Computing Machinery, doi:10.1145/1015330.1015444 .
  7. Duchi, John C.; Tarlow, Daniel; Elidan, Gal; Koller, Daphne (2006), "Using Combinatorial Optimization within Max-Product Belief Propagation", in Schölkopf, Bernhard; Platt, John C.; Hoffman, Thomas, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, Advances in Neural Information Processing Systems, 19, MIT Press, pp. 369–376, http://papers.nips.cc/paper/3117-using-combinatorial-optimization-within-max-product-belief-propagation .
  8. Petitjean, F.; Webb, G.I.; Nicholson, A.E. (2013). Scaling log-linear analysis to high-dimensional data (PDF). International Conference on Data Mining. Dallas, TX, USA: IEEE. 
  9. «Two classic paper prizes for papers that appeared at ICML 2013». ICML. 2013. Consultado em 15 December 2014. 
  10. Kindermann & Snell, Ross & Laurie (1980). Markov Random Fields and their Applications (Rhode Island: American Mathematical Society). ISBN 0-8218-5001-6. 
  11. Zhang & Zakhor, Richard & Avideh (2014). «Automatic Identification of Window Regions on Indoor Point Clouds Using LiDAR and Cameras». VIP Lab Publications [S.l.: s.n.] 

Ligações externas[editar | editar código-fonte]