Rede de dependência (modelo gráfico) - Dependency network (graphical model)

Redes de dependência (DNs) são modelos gráficos , semelhantes às redes de Markov , em que cada vértice (nó) corresponde a uma variável aleatória e cada aresta captura dependências entre as variáveis. Ao contrário das redes bayesianas , os DNs podem conter ciclos. Cada nó está associado a uma tabela de probabilidade condicional, que determina a realização da variável aleatória a partir de seus pais.

Manta de markov

Em uma rede bayesiana , a manta de Markov de um nó é o conjunto de pais e filhos desse nó, junto com os pais dos filhos. Os valores dos pais e filhos de um nó evidentemente fornecem informações sobre esse nó. No entanto, os pais de seus filhos também devem ser incluídos na manta de Markov, porque podem ser usados ​​para explicar o nó em questão. Em um campo aleatório de Markov , a manta de Markov para um nó são simplesmente seus nós adjacentes (ou vizinhos). Em uma rede de dependência, o cobertor de Markov para um nó é simplesmente o conjunto de seus pais.

Rede de dependência versus redes bayesianas

As redes de dependência têm vantagens e desvantagens em relação às redes Bayesianas. Em particular, eles são mais fáceis de parametrizar a partir dos dados, pois existem algoritmos eficientes para aprender a estrutura e as probabilidades de uma rede de dependência a partir dos dados. Tais algoritmos não estão disponíveis para redes Bayesianas, para as quais o problema de determinação da estrutura ótima é NP-difícil. No entanto, uma rede de dependência pode ser mais difícil de construir usando uma abordagem baseada em conhecimento conduzida por conhecimento especializado.

Redes de dependência versus redes de Markov

Redes de dependência consistente e redes de Markov têm o mesmo poder de representação. No entanto, é possível construir redes de dependência não consistentes, ou seja, redes de dependência para as quais não há distribuição de probabilidade conjunta válida compatível . As redes de Markov, ao contrário, são sempre consistentes.

Definição

Uma rede de dependência consistente para um conjunto de variáveis ​​aleatórias com distribuição conjunta é um par onde é um gráfico cíclico direcionado, onde cada um de seus nós corresponde a uma variável em , e é um conjunto de distribuições de probabilidade condicional. Os pais do nó , denotados , correspondem às variáveis que satisfazem os seguintes relacionamentos de independência ${\ textstyle \ mathbf {X} = (X_ {1}, \ ldots, X_ {n})}$${\ displaystyle p (\ mathbf {x})}$${\ displaystyle (G, P)}$${\ displaystyle G}$${\ displaystyle \ mathbf {X}}$${\ displaystyle P}$${\ displaystyle X_ {i}}$${\ displaystyle \ mathbf {Pa_ {i}}}$${\ displaystyle \ mathbf {Pa_ {i}} \ subseteq (X_ {1}, \ ldots, X_ {i-1}, X_ {i + 1}, \ ldots, X_ {n})}$

${\ displaystyle p (x_ {i} \ mid \ mathbf {pa_ {i}}) = p (x_ {i} \ mid x_ {1}, \ ldots, x_ {i-1}, x_ {i + 1} , \ ldots, x_ {n}) = p (x_ {i} \ mid \ mathbf {x} - {x_ {i}}).}$

A rede de dependência é consistente no sentido de que cada distribuição local pode ser obtida a partir da distribuição conjunta . Redes de dependência aprendidas usando grandes conjuntos de dados com grandes tamanhos de amostra quase sempre serão consistentes. Uma rede não consistente é uma rede para a qual não há distribuição de probabilidade conjunta compatível com o par . Nesse caso, não há distribuição de probabilidade conjunta que satisfaça as relações de independência subsumidas por aquele par. ${\ displaystyle p (\ mathbf {x})}$${\ displaystyle (G, P)}$

Aprendizagem de estrutura e parâmetros

Duas tarefas importantes em uma rede de dependência são aprender sua estrutura e probabilidades a partir dos dados. Essencialmente, o algoritmo de aprendizagem consiste em realizar de forma independente uma regressão probabilística ou classificação para cada variável no domínio. Vem da observação que a distribuição local para variável em uma rede de dependência é a distribuição condicional , que pode ser estimada por qualquer número de técnicas de classificação ou regressão, como métodos que usam uma árvore de decisão probabilística, uma rede neural ou um vetor de suporte probabilístico máquina. Portanto, para cada variável no domínio , estimamos independentemente sua distribuição local a partir de dados usando um algoritmo de classificação, embora seja um método distinto para cada variável. Aqui, mostraremos brevemente como as árvores de decisão probabilísticas são usadas para estimar as distribuições locais. Para cada variável em , uma árvore de decisão probabilística é aprendida onde é a variável de destino e são as variáveis ​​de entrada. Para aprender uma estrutura de árvore de decisão para , o algoritmo de busca começa com um nó raiz único sem filhos. Em seguida, cada nó folha na árvore é substituído por uma divisão binária em alguma variável em , até que nenhuma substituição aumente a pontuação da árvore. ${\ displaystyle X_ {i}}$${\ displaystyle p (x_ {i} | \ mathbf {x} - {x_ {i}})}$${\ displaystyle X_ {i}}$${\ displaystyle X}$${\ displaystyle X_ {i}}$${\ displaystyle \ mathbf {X}}$${\ displaystyle X_ {i}}$${\ displaystyle \ mathbf {X} -X_ {i}}$${\ displaystyle X_ {i}}$${\ displaystyle X_ {j}}$${\ displaystyle \ mathbf {X} -X_ {i}}$

Inferência Probabilística

Uma inferência probabilística é a tarefa na qual desejamos responder às perguntas probabilísticas da forma , dado um modelo gráfico para , onde (as variáveis ​​de 'destino') (as variáveis ​​de 'entrada') são subconjuntos disjuntos de . Uma das alternativas para realizar inferências probabilísticas é o uso da amostragem de Gibbs . Uma abordagem ingênua para isso usa um amostrador de Gibbs ordenado, cuja dificuldade importante é que se ou for pequeno, então muitas iterações são necessárias para uma estimativa de probabilidade precisa. Outra abordagem para estimar quando é usar o amostrador de Gibbs ordenado modificado, onde ele fixa durante a amostragem de Gibbs. ${\ displaystyle p (\ mathbf {y \ mid z})}$${\ displaystyle \ mathbf {X}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {X}}$${\ displaystyle p (\ mathbf {y \ mid z})}$${\ displaystyle p (\ mathbf {z})}$${\ displaystyle p (\ mathbf {y \ mid z})}$${\ displaystyle p (\ mathbf {z})}$${\ displaystyle \ mathbf {Z = z}}$

Também pode acontecer que seja raro, por exemplo, contém muitas variáveis. Assim, a lei da probabilidade total junto com as independências codificadas em uma rede de dependência pode ser usada para decompor a tarefa de inferência em um conjunto de tarefas de inferência em variáveis ​​únicas. Essa abordagem tem a vantagem de que alguns termos podem ser obtidos por consulta direta, evitando, assim, algumas amostragens de Gibbs. ${\ displaystyle \ mathbf {y}}$${\ displaystyle \ mathbf {Y}}$

Você pode ver abaixo um algoritmo que pode ser usado para obter para uma instância particular de e , onde e são subconjuntos separados. ${\ displaystyle p (\ mathbf {y | z})}$${\ displaystyle \ mathbf {y} \ in \ mathbf {Y}}$${\ displaystyle \ mathbf {z} \ in \ mathbf {Z}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {Z}}$

• Algoritmo 1:

1. ${\ displaystyle \ mathbf {U: = Y}}$ (* as variáveis ​​não processadas *)
2. ${\ displaystyle \ mathbf {P: = Z}}$ (* as variáveis ​​processadas e condicionantes *)
3. ${\ displaystyle \ mathbf {p: = z}}$(* os valores para *)${\ displaystyle \ mathbf {P}}$
4. Enquanto : ${\ displaystyle \ mathbf {U} \ neq \ emptyset}$
   1. Escolha tal que não tenha mais pais do que qualquer variável em${\ displaystyle X_ {i} \ in \ mathbf {U}}$${\ displaystyle X_ {i}}$${\ displaystyle U}$${\ displaystyle U}$
   2. Se todos os pais de estão em${\ displaystyle X}$${\ displaystyle \ mathbf {P}}$
      1. ${\ displaystyle p (x_ {i} | \ mathbf {p}): = p (x_ {i} | \ mathbf {pa_ {i}})}$
   3. Senão
      1. Use um amostrador Gibbs ordenado modificado para determinar ${\ displaystyle p (x_ {i} | \ mathbf {p})}$
   4. ${\ displaystyle \ mathbf {U: = U} -X_ {i}}$
   5. ${\ displaystyle \ mathbf {P: = P} + X_ {i}}$
   6. ${\ displaystyle \ mathbf {p: = p} + x_ {i}}$
5. Retorna o produto das condicionais ${\ displaystyle p (x_ {i} | \ mathbf {p})}$

Formulários

Além dos aplicativos para inferência probabilística, os seguintes aplicativos estão na categoria de Filtragem Colaborativa (CF), que é a tarefa de prever preferências. Redes de dependência são uma classe de modelo natural na qual basear as previsões de CF, uma vez que um algoritmo para essa tarefa precisa apenas de estimativa para produzir recomendações. Em particular, essas estimativas podem ser obtidas por uma consulta direta em uma rede de dependência. ${\ displaystyle p (x_ {i} = 1 | \ mathbf {x} - {x_ {i}} = 0)}$

• Prever de quais filmes uma pessoa vai gostar com base em suas avaliações dos filmes vistos;
• Prever quais páginas da web uma pessoa acessará com base em seu histórico no site;
• Prever em quais notícias uma pessoa está interessada com base em outras histórias que leu;
• Prever qual produto uma pessoa comprará com base nos produtos que ela já comprou e / ou colocou em sua cesta de compras.

Outra classe de aplicativos úteis para redes de dependência está relacionada à visualização de dados, ou seja, visualização de relacionamentos preditivos.

Veja também

• Rede de dependência relacional

Referências