Campo aleatório de Markov
No domínio da física e da probabilidade, um campo aleatório de Markov, 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.
Dado um grafo não direcionado G = ( V , E ) {\displaystyle G=(V,E)} , um conjunto de variáveis aleatórias X = ( X v ) v ∈ V {\displaystyle X=(X_{v})_{v\in V}} indexadas por V {\displaystyle V} formam um campo aleatório de Markov com relação a G {\displaystyle 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 ⊥ ⊥ X v ∣ X V ∖ { u , v } if { u , v } ∉ E {\displaystyle 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 ⊥ ⊥ X V ∖ cl ( v ) ∣ X ne ( v ) {\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {cl} (v)}\mid X_{\operatorname {ne} (v)}} onde ne ( v ) {\displaystyle \operatorname {ne} (v)} é o conjunto de vizinhos de v {\displaystyle v} e cl ( v ) = v ∪ ne ( v ) {\displaystyle \operatorname {cl} (v)=v\cup \operatorname {ne} (v)} é a vizinhança de v {\displaystyle v} .
Propriedade de Markov global
Quaisquer dois subconjuntos de variáveis são condicionalmente independentes dado a separação do subconjunto: X A ⊥ ⊥ X B ∣ X S {\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}} onde cada caminho de um nó em A {\displaystyle A} para um nó em B {\displaystyle B} passa por S {\displaystyle 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.
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 ∈ V {\displaystyle X=(X_{v})_{v\in V}} , seja P ( X = x ) {\displaystyle P(X=x)} a probabilidade de uma configuração de campo particular de x {\displaystyle x} em X {\displaystyle X} . Isto é, P ( X = x ) {\displaystyle P(X=x)} é a probabilidade de encontrar as variáveis aleatórias X {\displaystyle X} assumindo o valor particular x {\displaystyle x} . Como X {\displaystyle X} é um conjunto, a probabilidade de x {\displaystyle x} deve ser compreendida como relacionada a uma distribuição conjunta de X v {\displaystyle X_{v}} . Se este conjunto de densidade pode ser fatorizado sobre os cliques de G {\displaystyle G} :
Qualquer campo aleatório de Markov (com uma densidade estritamente positiva) pode ser escrito como um modelo log-linear com funções f k {\displaystyle f_{k}} de tal forma que a distribuição conjunta pode ser escrita como é simplesmente um produto do ponto sobre o campo de configurações, e Z é a função de partição: Aqui, X {\displaystyle {\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 {\displaystyle 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 {\displaystyle f_{k,i}(x_{\{k\}})=1} if x { k } {\displaystyle 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 = | dom ( C k ) | {\displaystyle N_{k}=|\operatorname {dom} (C_{k})|} é a cardinalidade do clique, e o peso de f k , i {\displaystyle f_{k,i}} corresponde ao do logaritmo do fator clique correspondente, isto é, w k , i = log ϕ ( c k , i ) {\displaystyle w_{k,i}=\log \phi (c_{k,i})} , onde c k , i {\displaystyle c_{k,i}} é a i-ésima configuração do k-ésimo clique, isto é, o i-ésimo valor no domínio do clique C k {\displaystyle C_{k}} .
Gaussiana
Uma distribuição normal multivariada forma um campo aleatório de Markov em relação a um grafo G = ( V , E ) {\displaystyle G=(V,E)} se as arestas faltantes correspondem aos zeros na matriz de precisão (a inversa da matriz de covariância):
Como em uma rede bayesiana, pode-se calcular a distribuição condicional de um conjunto de nós V ′ = { v 1 , … , v i } {\displaystyle V'=\{v_{1},\ldots ,v_{i}\}} dados valores para outro conjunto de nós W ′ = { w 1 , … , w j } {\displaystyle W'=\{w_{1},\ldots ,w_{j}\}} em um campo aleatório de Markov ao somar todas as possíveis atribuições de u ∉ V ′ , W ′ {\displaystyle 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.
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 {\displaystyle o} . Neste modelo, cada função ϕ k {\displaystyle \phi _{k}} é um mapeamento de todas as atribuições para ambos o clique k e as observações o {\displaystyle 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.
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.
