Usuário(a):MGromov/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 têm uma propriedade Markov descrito por um grafo não direcionado. Em outras palavras, um campo aleatório é dito ser campo aleatório de Markov, desde que preencha as propriedades de Markov.

Uma rede de Markov ou MRF é semelhante a uma rede Bayesiana na sua representação das 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, que é também referida como um campo aleatório Gibbs, porque, de acordo com o teorema de Hammersley-Clifford, ele pode então ser representada por uma medida de Gibbs para um apropriado (definido localmente) função de energia. O campo aleatório protótipo Markov é o modelo de Ising; de fato, o campo aleatório de Markov foi introduzido como a configuração geral para o modelo de Ising. No domínio da inteligência artificial, um campo aleatório de Markov é usado para modelar vários baixa a tarefas de nível médio no processamento de imagens e visão computacional.

https://en.wikipedia.org/wiki/File: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.

Definição

Dado um grafo não direcionado {\ displaystyle G = (V, E)} G = (V, E), um conjunto de variáveis ​​aleatórias {\ displaystyle X = (X_ {v}) _ {v \ in V}} {\ displaystyle X = (X_ {v}) _ {v \ in v}} indexados pelo {\ displaystyle v} formulário v um campo aleatório de Markov com respeito a {\ displaystyle G} G se satisfizerem as propriedades locais de Markov:

Pairwise Markov propriedade: Quaisquer duas variáveis ​​não adjacentes são condicionalmente independentes dado todas as outras variáveis: {\ Displaystyle X_ {u} \ perp \! \! \! \ Perp X_ {v} \ meados X_ {V \ setminus \ {u, v \}} \ quad {\ text {if}} \ {u, v \} \ notin E} X_u \ perp \! \! \! \ perp X_v \ meados X_ {v \ setminus \ {u, v \}} \ quad \ text {if} \ {u, v \} \ notin E propriedade Markov local: Uma variável é condicionalmente independente de todas as outras variáveis ​​dadas seus vizinhos: {\ Displaystyle X_ {v} \ perp \! \! \! \ Perp X_ {V \ setminus \ operatorname {cl} (v)} \ mid X _ {\ operatorname {ne} (v)}} X_v \ perp \! \! \! \ perp X_ {v \ setminus \ operatorname {cl} (v)} \ mid X _ {\ operatorname {ne} (v)} onde {\ textstyle \ operatorname {ne} (v)} {\ textstyle \ operatorname {ne} (v)} é o conjunto de vizinhos de {\ displaystyle v} v, e {\ displaystyle \ operatorname {cl} (v) = v \ cup \ operatorname {ne} (v)} {\ displaystyle \ operatorname {cl} (v) = v \ cup \ operatorname {ne} (v)} é o bairro fechado de {\ displaystyle v} v. propriedade global Markov: Quaisquer dois subconjuntos de variáveis ​​são condicionalmente independentes dado um subconjunto de separação: {\ Displaystyle X_ {A} \ perp \! \! \! \ Perp X_ {B} \ meados X_ {S}} X_A \ perp \! \! \! \ Perp X_B \ meados X_S onde cada caminho de um nó na {\ displaystyle A} A para um nó na {\ displaystyle B} B passa por {\ displaystyle S} S. As três propriedades Markov acima não são equivalentes: A propriedade local Markov é mais forte do que o Pairwise um, enquanto mais fraco do que o global.

Fatoração

Como as propriedades de Markov de uma distribuição de probabilidade arbitrária pode ser difícil estabelecer, de uma classe vulgarmente utilizado de campos aleatórios de Markov são aqueles que podem ser fatorado de acordo com as cliques do gráfico.

Dado um conjunto de variáveis ​​aleatórias {\ displaystyle X = (X_ {v}) _ {v \ in V}} {\ displaystyle X = (X_ {v}) _ {v \ in V}}, seja {\ displaystyle P (X = X)} P (X = X) a probabilidade de uma determinada configuração do campo {\ displaystyle x x} em {\ displaystyle X} X. Isto é, {\ displaystyle P (X = X)} P (X = x) é a probabilidade de encontrar que as variáveis ​​aleatórias {\ displaystyle X} X opinião sobre o valor particular {\ displaystyle x} x. Porque {\ displaystyle X} X é um conjunto, a probabilidade de {\ displaystyle x} x deve ser entendida a serem tomadas em relação a uma distribuição conjunta da {\ displaystyle X_ {v}} {\ displaystyle X_ {v}} .

Se esta densidade conjunta pode ser fatorada durante os cliques de {\ displaystyle G} G:

{\ Displaystyle P (X = x) = \ prod _ {C \ in \ operatorname {cl} (G)} \ phi _ {C} (x_ {C})} P (X = x) = \ Prod_ {C \ in \ operatorname {cl} (G)} \ phi_C (x_C) em seguida, {\ displaystyle X} X forma um campo aleatório de Markov com respeito a {\ displaystyle G} G. Aqui, {\ displaystyle \ operatorname {cl} (G)} {\ displaystyle \ operatorname {cl} (G)} é o conjunto de pequenas associações dos {\ displaystyle G} G. A definição é equivalente se forem utilizados apenas cliques maximais. As funções φC são por vezes referidos como potenciais fator ou potenciais Clique. Note, no entanto, conflitantes terminologia está em uso: o potencial palavra é muitas vezes aplicada ao logaritmo da φC. Isto porque, na mecânica estatística, log (φC) tem uma interpretação direta como a energia potencial de uma configuração {\ displaystyle x_ {C}} {\ displaystyle 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 Bayesian). Quando um tal fatorização existir, é possível construir um gráfico fator para a rede.

Modelo Logístico

Qualquer campo aleatório de Markov (com uma densidade estritamente positivo) pode ser escrita como modelo log-linear com funções de recurso {\ displaystyle f_ {k}} f_ {k} tal que a distribuição full-articulação pode ser escrita como

{\ Displaystyle P (X = x) = {\ frac {1} {Z}} \ exp \ left (\ sum _ {k} W_ {k} ^ {\ top} f_ {k} (x _ {\ {k \}}) \ right)} P (X = x) = \ frac {1} {Z} \ exp \ left (\ sum_ {k} w_k ^ {\ top} F_k (x_ {\ {k \}}) \certo) onde a notação

{\ Displaystyle W_ {k} ^ {\ top} f_ {k} (x _ {\ {k \}}) = \ sum _ {i = 1} ^ {N_ {k}} W_ {k, i} \ cdot f_ {k, i} (x _ {\ {k \}})} w_k ^ {\ top} F_k (x_ {\ {k \}}) = \ sum_ {i = 1} ^ {N_k} W_ {k, i} \ cdot f_ {k, i} (x _ {\ {k \}}) é simplesmente um produto de ponto sobre configurações de campo, e Z é a função de partição:

{\ Displaystyle Z = \ sum _ {x \ in {\ mathcal {X}}} \ exp \ left (\ sum _ {k} W_ {k} ^ {\ top} f_ {k} (x _ {\ {k \}}) \ right).} Z = \ sum_ {x \ in \ mathcal {X}} \ exp \ left (\ sum_ {k} w_k ^ {\ top} F_k (x_ {\ {k \}}) \certo). Aqui, {\ displaystyle {\ mathcal {X}}} {\ 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 de recurso {\ displaystyle F_ {k, i}} F_ {k, i} são definidas de tal modo que eles são indicadores da configuração do bando, ou seja, {\ displaystyle F_ {k, i} (x _ {\ {K \ }}) = 1} f_ {k, i} (x _ {\ {k \}}) = 1 se {\ displaystyle x _ {\ {k \}}} x _ {\ {k \}} corresponde à i- configuração possível th da camarilha do k-th e 0 caso contrário. Este modelo é equivalente ao modelo fatoração camarilha dado acima, se {\ displaystyle N_ {k} = | \ operatorname {dom} (C_ {k}) |} N_k = | \ operatorname {dom} (C_K) | é a cardinalidade do clique, e o peso de um recurso {\ displaystyle f_ {k, i}} f_ {k, i} corresponde ao logaritmo do fator camarilha correspondente, ou seja, {\ displaystyle W_ {k, i} = \ log \ phi (c_ {k, i})} W_ {k, i} = \ log \ phi (c_ {k, i}), onde {\ displaystyle c_ {k, i}} c_ {k, i} é a possível configuração i-th da camarilha do k-th, ou seja, o valor i-th no domínio da camarilha {\ displaystyle C_ {k}} C_ {k}.

A probabilidade P é muitas vezes chamado a medida Gibbs. Esta expressão de um campo de Markov como um modelo logístico só é possível se todos os fatores camarilha são diferentes de zero, ou seja, se nenhum dos elementos da {\ displaystyle {\ mathcal {X}}} {\ mathcal {X}} é atribuído um probabilidade de 0. Isto permite técnicas de álgebra de matrizes para ser aplicada, por exemplo, que o traço de uma matriz é o log do determinante, com a representação da matriz de um gráfico resultante de matriz de incidência do gráfico.

A importância da função de partição Z é que muitos conceitos de mecânica estatística, tais como entropia, generalizar diretamente para o caso de redes de Markov, e uma compreensão intuitiva pode assim ser obtida. Além disso, a função de partição permite métodos variacional a ser aplicado para a solução do problema: um possível anexar uma força motriz para uma ou mais das variáveis ​​aleatórias, e explorar a reacção da rede em resposta a essa perturbação. Assim, por exemplo, pode-se adicionar um termo condução JV, para cada vértice V do gráfico, para a função de partição para obter:

{\ Displaystyle 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)} 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) Formalmente diferenciação em relação à Jv dá o valor esperado do Xv variável aleatória associada ao vértice v:

{\ Displaystyle E [X_ {v}] = {\ frac {1} {Z}} \ left {\ frac {\ Z parcial [J]} {\ J_ parcial {v}}} \ right |. _ {J_ {v} = 0}} E [X_v] = \ frac {1} {Z} \ left \ frac {\ Z parcial [J]} {\ J_v parcial} \ right |.. _ {J_v = 0}. funções de correlação são calculados da mesma forma; a correlação de dois pontos é:

{\ Displaystyle C [X_ {u}, X_ {v}] = {\ frac {1} {Z}} \ left. {\ Frac {\ partial ^ {2} Z [J]} {\ J_ parcial {u } \ J_ parcial {v}}} \ right |.. _ {J_ {u} = 0, J_ {v} = 0}} C [X_u, X_v] = \ frac {1} {Z} \ left \ frac {\ partial ^ 2 Z [J]} {\ partial J_u \ J_v parcial} \ right | _ {J_u = 0, J_v = 0}. Modelos log-lineares são especialmente conveniente para a sua interpretação. Um modelo log-linear pode fornecer uma representação muito mais compacto para muitas distribuições, especialmente quando as variáveis ​​têm grandes domínios. Eles são convenientes também porque as suas probabilidades de log negativos são convexas. Infelizmente, embora o risco de uma rede de Markov logística é convexa, avaliar a probabilidade de gradiente ou a probabilidade de um modelo requer inferência no modelo, o que é geralmente computacionalmente inviável (ver 'Inference' abaixo).

Exemplos

Gaussiano Uma distribuição normal multivariada forma um campo aleatório de Markov com respeito a um gráfico {\ displaystyle G = (V, E)} L = (V, E) se as arestas falta de correspondência de zeros na matriz de precisão (da matriz covariância inversa):

{\ Displaystyle X = (X_ {v}) _ {v \ in V} \ sim {\ mathcal {N}} ({\ boldsymbol {\ mu}}, \ Sigma)} X = (X_v) _ {v \ em V} \ sim \ mathcal N (\ boldsymbol \ mu, \ Sigma) de tal modo que

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

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 {\ displaystyle o} S. Neste modelo, cada função {\ displaystyle \ phi _ {k}} \ phi _ {k} é um mapeamento de todas as atribuições de ambos os k camarilha e as observações {\ displaystyle o} o para os números reais não negativos. Esta forma da rede de Markov pode ser mais apropriado para a produção de classificadores discriminativos, que não modelam a distribuição sobre as observações. CRFs 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ções numa variedade de campos, variando de computação gráfica para visão por computador e aprendizagem automática.CAMs são usados ​​no processamento de imagem para gerar texturas como eles podem ser usados ​​para gerar modelos de imagem flexível e estocásticos. Na modelação da imagem, a tarefa é encontrar uma distribuição de intensidade apropriada de uma dada imagem, onde adequação depende do tipo de tarefa e CAMs são flexíveis o suficiente para serem usados para a síntese de imagem e textura, compressão de imagem e de restauração, a segmentação da imagem, a reconstrução da superfície, registo de imagem, a síntese de textura, super-resolução, correspondência estéreo e recuperação da informação. Eles podem ser usados ​​para resolver vários problemas de visão computacional que podem ser colocados como problemas de minimização de energia ou problemas em diferentes regiões têm que ser distinguidos utilizando um conjunto de características discriminantes, dentro de um quadro campo aleatório de Markov, para prever a categoria da região. Campos aleatórios de Markov foram uma generalização sobre o modelo de Ising e tem, desde então, sido amplamente utilizadas em otimizações e redes combinatória.

Página inicial: Testes

Edições completas: Mecânica estatística  • Modelo Hodgkin-Huxley  • Neurociência computacional  • Modelo probabilístico para redes neurais  • Teoria de campo médio  • Modelo FitzHugh–Nagumo  • Processo Lévy  • Cadeias de Markov  • Processo de Poisson  • Galves–Löcherbach model  • Stochastic chains with memory of variable length  • Lesão do plexo braquial  • Somatotopia  • Função densidade  • Modelos de grafos aleatórios exponenciais • Processo de Gram-Schmidt  • Equação de Chapman–Kolmogorov  • Predefinição:Processos estocásticos  • Algoritmo de autovalores  • Transição de fase  • Hipótese do cérebro crítico  • Critical brain hypothesis  • Passeio aleatório  • Plasticidade sináptica  • Potencial pós-sináptico excitatório  • Potencial pós-sináptico inibitório  • Modelo de Morris-Lecar  • Plexo braquial  • Processo gaussiano  • Campo aleatório de Markov  • Eletroencefalografia  • Modelo de Hindmarsh-Rose  • Sistemas de partícula em interação  • Medida de Gibbs  • Nervo escapular dorsal  • Nervo radial  • Nervo peitoral lateral  • Nervo musculocutâneo  • Medida de Dirac  • Nervo torácico longo  • Sigma-álgebra  • Nervo peitoral medial  • Nervo ulnar  • Potencial evocado  • Estimulação magnética transcraniana repetitiva  • Teorema de Donsker  • Desigualdade de Boole  • Codificação neural  • Aprendizado de máquina  • Independência condicional  • Inferência estatística  • Nervo subclávio  • Nervo supraescapular  • Nervo mediano  • Nervo axilar  • Movimento browniano geométrico  • Caminho autoevitante  • Tempo local  • Nervo subescapular superior  • Nervo toracodorsal  • Nervo subscapular inferior  • Caminho (teoria dos grafos)  • Campo aleatório  • Lei do logaritmo iterado

Edições em andamento: Nervo cutâneo medial do braço (N)  • Nervo cutâneo medial do antebraço (N)  • Cérebro estatístico (N)  • Statistician brain  • Distribuição de probabilidade condicional (N)  • Esperança condicional (N)  • Integral de Itō (N)  • Martingale  • Variação quadrática (N)  • Processo Ornstein–Uhlenbeck  • Ruído branco  • Teoria ergódica  • Avalanche neuronal (N)  • Teoria da percolação (N)  • Função totiente de Euler  • Ruído neuronal (N)  • Distribuição de Poisson  • Córtex cerebral  • Estímulo (fisiologia)

Referência: Markov random field