Algoritmo de árvore de junção - Junction tree algorithm

Image
Exemplo de árvore de junção

O algoritmo de árvore de junção (também conhecido como 'Clique Tree') é um método usado em aprendizado de máquina para extrair marginalização em gráficos gerais . Em essência, envolve a propagação de crenças em um grafo modificado denominado árvore de junção . O gráfico é chamado de árvore porque se ramifica em diferentes seções de dados; nós de variáveis ​​são os ramos. A premissa básica é eliminar os ciclos agrupando-os em nós únicos. Várias classes extensas de consultas podem ser compiladas ao mesmo tempo em estruturas maiores de dados. Existem diferentes algoritmospara atender a necessidades específicas e para o que precisa ser calculado. Os algoritmos de inferência reúnem novos desenvolvimentos nos dados e os calculam com base nas novas informações fornecidas.

Algoritmo de árvore de junção

Algoritmo de Hugin

  • Se o gráfico for direcionado, moralize -o para torná-lo não direcionado.
  • Apresente as evidências.
  • Triangule o gráfico para torná-lo cordal.
  • Construa uma árvore de junção a partir do gráfico triangulado (chamaremos os vértices da árvore de junção de " supernós ").
  • Propagar as probabilidades ao longo da árvore de junção (via propagação de crença )

Observe que esta última etapa é ineficiente para gráficos de grande largura de árvore . O cálculo das mensagens a serem transmitidas entre os supernós envolve fazer a marginalização exata das variáveis ​​em ambos os supernós. Executar este algoritmo para um gráfico com largura de árvore k terá, portanto, pelo menos um cálculo que leva tempo exponencial em k. É um algoritmo de passagem de mensagens . O algoritmo Hugin leva menos cálculos para encontrar uma solução em comparação com Shafer-Shenoy.

Algoritmo Shafer-Shenoy

  • Calculado recursivamente
  • Múltiplas recursões do algoritmo Shafer-Shenoy resultam no algoritmo Hugin
  • Encontrado pela equação de passagem de mensagem
  • Potenciais de separação não são armazenados

O algoritmo Shafer-Shenoy é o produto da soma de uma árvore de junção. Ele é usado porque executa programas e consultas com mais eficiência do que o algoritmo Hugin. O algoritmo possibilita cálculos para funções condicionais para funções de crença . As distribuições conjuntas são necessárias para que os cálculos locais aconteçam.

Teoria subjacente

Image
Exemplo de uma rede Bayesiana Dinâmica

A primeira etapa diz respeito apenas a redes bayesianas e é um procedimento para transformar um grafo direcionado em um não direcionado . Fazemos isso porque permite a aplicabilidade universal do algoritmo, independentemente da direção.

A segunda etapa é definir as variáveis ​​para seus valores observados. Isso geralmente é necessário quando queremos calcular probabilidades condicionais, então fixamos o valor das variáveis ​​aleatórias que condicionamos. Também se diz que essas variáveis ​​estão restritas a seus valores particulares.

Image
Exemplo de um gráfico de cordas

A terceira etapa é garantir que os gráficos sejam feitos de acordes, caso ainda não sejam acordes. Esta é a primeira etapa essencial do algoritmo. Ele faz uso do seguinte teorema:

Teorema: para um gráfico não direcionado, G, as seguintes propriedades são equivalentes:

  • O gráfico G é triangulado.
  • O grafo de clique de G tem uma árvore de junção.
  • Há uma ordem de eliminação para G que não leva a nenhuma aresta adicionada.

Assim, ao triangular um gráfico, garantimos que a árvore de junção correspondente existe. Uma maneira usual de fazer isso é decidir uma ordem de eliminação para seus nós e, em seguida, executar o algoritmo de eliminação de variável . O algoritmo de eliminação de variável afirma que o algoritmo deve ser executado cada vez que houver uma consulta diferente. Isso resultará na adição de mais arestas ao gráfico inicial, de forma que a saída seja um gráfico de acordes . Todos os gráficos cordais têm uma árvore de junção. A próxima etapa é construir a árvore de junção . Para fazer isso, usamos o gráfico da etapa anterior e formamos seu gráfico de clique correspondente . Agora, o próximo teorema nos dá uma maneira de encontrar uma árvore de junção:

Teorema: Dado um grafo triangulado, pondere as arestas do grafo do clique por sua cardinalidade, | A∩B |, da intersecção dos cliques adjacentes A e B. Então, qualquer árvore geradora de peso máximo do grafo do clique é uma árvore de junção .

Então, para construir uma árvore de junção, nós apenas temos que extrair uma árvore de abrangência de peso máximo do gráfico de clique. Isso pode ser feito de forma eficiente, por exemplo, modificando o algoritmo de Kruskal . A última etapa é aplicar a propagação de crenças à árvore de junção obtida.

Uso: Um gráfico de árvore de junção é usado para visualizar as probabilidades do problema. A árvore pode se tornar uma árvore binária para formar a construção real da árvore. Um uso específico pode ser encontrado em codificadores automáticos , que combinam o gráfico e uma rede de passagem em grande escala automaticamente.

Algoritmos de inferência

Image
Condicionamento de cutset

Propagação de crenças em looping: Um método diferente de interpretação de gráficos complexos. A propagação de crença maluca é usada quando uma solução aproximada é necessária em vez da solução exata . É uma inferência aproximada .

Condicionamento de cutset: usado com conjuntos menores de variáveis. O condicionamento de cutset permite gráficos mais simples que são mais fáceis de ler, mas não são exatos .

Referências