Review: Logicomix

Agosto 12, 2012

Logicomix é uma estória em quadrinhos sobre a busca do fundamento da matemática. É um livro fantástico porque mistura romance, história, mitologia e matemática. Além disso é uma meta-estória, pois relata o processo de desenvolvimento dos quadrinhos na própria estória.

Um dos autores (e personagem) do livro é Christos Papadimitriou, atualmente professor de teoria da computação em Berkeley. Durante minha iniciação científica cheguei a estudar um de seus livros escrito com Ken Steiglitz sobre Otimização Combinatória, mas achei muito difícil e acabei usando outro :P

Teóricos da computação fazem muito uso da lógica, especialmente os que trabalham com complexidade computacional e computabilidade. A estória dá a entender que Papadimitriou foi convidado como o especialista em lógica, embora o autor principal, Apostolos Doxiadis tenha formação matemática também.

Spoiler! O restante deste post contém um breve resumo do livro, além de uma análise pessoal.

Resumo

Tractatus Logico-Philosophicus

Bertrand Russell é o personagem central do livro que descreve sua saga em busca dos fundamentos da matemática.

Russell aparece em dois planos: em um está no presente, palestrando a um grupo de americanos contrários à adesão dos Estados Unidos à Segunda Guerra Mundial. Durante essa palestra ele conta a história de sua vida, que acontece em um outro plano. A grande maioria dos acontecimentos acontece nesse segundo plano e o Russell do plano presente serve mais como um narrador.

Além desses dois planos temos o plano em que os autores do livro estão elaborando a estória ao mesmo tempo em que ela acontece. Eles geralmente aparecem para justificar alguma discrepância entre a história e a estória, além de explicar conceitos mais técnicos.

Logo criança, Russell torna-se órfão e passa a viver com seus avós na mansão Pembroke. É apresentado aos trabalhos de Euclides por um professor particular de matemática.

Russell segue para o Trinity College, onde conhece Alfred Whitehead. Casa-se com Alys Smith e então fazem uma viagem ao continente, passando primeiramente pela Alemanha, onde conhecem Gottlob Frege e George Cantor (embora o livro deixe claro que Russell não os conheceu pessoalmente).

Na França, conhecem a esposa de Whitehead, Evelyn Wade. A estória retrata um interesse de Russell em Evelyn, embora em nenhum momento do livro pareça ter havido algo mais entre eles. Depois, Russell participa do congresso internacional de matemáticos onde David Hilbert divulga a famosa lista de 23 problemas abertos em matemática.

Neste ponto Russell descobre um paradoxo na teoria dos conjuntos, que abala o mundo da matemática. Whitehead e Russell decidem então começar a escrita do Principia mathematica, que se mostra uma tarefa desgastante.

Russell passa a dar aulas em Cambridge e é quando Ludwig Wittgenstein torna-se seu estudante de doutorado. Evelyn, a esposa de Whitehad acha que está prestes a morrer e pede para Russell consolar seu filho, Eric. Cansado de seus trabalhos com a lógica, Russell sente-se reconfortado por exercitar sentimentos como compaixão e amor para com Eric.

Começa a primeira Guerra Mundial. Russell se posiciona contra a adesão do Reino Unido, o que acaba o levando à prisão. Wittgenstein se alista ao exército Autro-Húngaro enquanto Eric, filho de Whitehead, faz o mesmo pelo lado britânico. Wittgenstein sobreviveu à guerra, fazendo-o mudar sua maneira de ver o mundo. Por outro lado, Eric é abatido em combate.

Após o fim da primeira guerra, Wittgenstein estava impedido de ir à Inglaterra por ser austríaco e portanto se encontra com Russell em território neutro: Haia, Holanda. Nesse encontro Wittgenstein contrapõe diversas ideias de Russell.

Russell casa-se pela segunda vez com Dora Black, tendo o seu primeiro filho. Seu casamento era bastante liberal, sendo que ele aceitava que amantes frequentassem sua casa. Seus pais também tiveram um casamento desta forma. Juntos decidiram fundar uma escola progressista para crianças, a Beacon Hill. À mesma época, Wittgenstein começa a dar aulas em escolas primárias.

O matemático Moritz Schlick passa a organizar o Círculo de Viena, uma associação de filósofos que se encontravam em torno da Universidade de Viena. Em uma dessas reuniões, Russell conhece Kurt Gödel e John Von Neumann e foi nesse encontro que Gödel anunciou seu primeiro teorema de incompletude, destruindo o sonho de Russell de definir um conjunto de axiomas que pudesse demonstrar todas as verdades matemáticas. Em seguida, as influências nazistas começaram a se espalhar pelo continente e em 1936, Schlick foi assassinado por um fanático nazista, o que pôs fim ao círculo e é nesse ponto que Russell conclui sua narrativa.

A estória termina voltando para o plano dos autores, que vão assistir à participação de Anne Bardy em uma encenação da peça Oresteia.

Matemática

Das diversas referências matemáticas presentes no livro, gostaria de comentar sobre as três que achei mais interessante.

Paradoxo de Russell

Em 1901, Russel apresenta um paradoxo da teoria dos conjuntos. Esse paradoxo por ser melhor entendido através de um exemplo, o paradoxo dos barbeiros.

Considere uma cidade onde existe apenas um barbeiro e uma lei que diz que o barbeiro deve fazer a barba de todos os homens que não se barbeiam sozinhos, mas não pode fazer a barba de quem se barbeia sozinho.

Consideremos duas possibilidades: o barbeiro se barbeia sozinho ou não. Se ele se barbeia sozinho, está infringindo a lei, porque ele não pode barbear quem se barbeia sozinho. Por outro lado, se ele não se barbeia, a lei o obriga a fazer sua própria barba. Conclui-se que a lei é contraditória.

A generalização para a teoria dos conjuntos é a seguinte: seja R conjunto de todos os conjuntos que não contém a si mesmos. Pergunta-se: R está contido em si mesmo? Vamos analisar duas possibilidades. Se R está contido em si mesmo, então R é um conjunto que contém a si mesmo e não poderia estar em R. Por outro lado, se R não está contido em si mesmo, ele é um conjunto que não contém a si mesmo e portanto deveria ser incluído em R :)

O Infinito e a Teoria dos Conjuntos

Em Logicomix, Russell descreve o paradoxo do hotel de Hilbert que exemplifica o quão contra-intuitivo é trabalhar com o conceito de infinito. A ideia por trás do paradoxo pode ser usada para provar, por exemplo, que existe uma bijeção entre os números naturais pares e os números naturais!

Isso está relacionado com o trabalho de George Cantor, que criou os conceitos de conjuntos enumeráveis e não enumeráveis, sendo os enumeráveis aqueles com mesma cardinalidade dos números naturais, ou seja, para os quais existe um mapeamento um pra um de seus elementos para com os números naturais.

Assim como os números naturais pares têm mesma cardinalidade dos números naturais, Cantor demonstrou que os números inteiros são enumeráveis assim como o conjunto dos números racionais! O conjuntos dos números reais não é enumerável.

Os 23 problemas de Hilbert

David Hilbert divulgou uma lista de 23 problemas não resolvidos à época de 1900. Há três problemas sobre os quais gostaria de comentar.

O principal problema da lista, e que até hoje não foi resolvido, é o problema 8, que é demonstrar a Hipótese de Riemann. O livro The music of primes, fornece uma introdução bem acessível sobre a hipótese, a função zeta de Riemann e a relação com números primos.

Um problema importante também é o número 2, provar que os axiomas da aritmética são consistentes. O segundo teorema da incompletude de Gödel mostra que não é possível provar esse teorema usando a própria aritmética. Entretanto, não há um consenso se isto é uma solução ou não para o problema.

Finalmente, um problema que eu acho particularmente interessante é o número 10: encontrar um algoritmo que determina se uma equação Diofantina polinomial com coeficientes inteiros tem uma solução.

Gosto desse problema porque é fácil de enunciar, está relacionado à área que pesquisei no mestrado (programação linear inteira) e porque foi resultado de um trabalho longo e de contribuição de diversas pessoas, Martin Davis, Yuri Matiyasevich, Hilary Putnam e Julia Robinson.

Mitologia

Algumas referências mitológicas aparecem na estória. A primeira é a um mito indiano sobre a tartaruga que segura o mundo. Russell faz a analogia como o mundo sendo a matemática e a tartaruga seus fundamentos.

Em certo ponto Whitehead mostra a Russell o quadro “As Danaides” de John Waterhouse. As Danaides são as 50 filhas de Dánao, que estavam prometidas aos 50 filhos de Egipto, seu irmão gêmeo. Todas exceto Hipernestra assassinaram seus esposos na noite de núpcias e como punição foram obrigadas por Hades a encherem um jarro de água com furos durante toda a eternidade.

As Danaides: pintura a óleo de John Waterhouse

Whitehead usou o mito como metáfora para o trabalho do Principia Mathematica. Russell queria encontrar um fundamento para a matemática, mas sempre via necessidade de fundamentar cada base que encontrava. Como se disse no livro, ele estava procurando a base da tartaruga que segurava o mundo, mas encontrou uma torre infinita de tartarugas.

Finalmente, temos a encenação peça Oresteia, uma trilogia escrita pelo dramaturgo grego Ésquilo.

O livro retrata a terceira peça, Eunêmides, no qual as Erínias, deusas da vingança decidem punir Orestes. Atena intervém e decide que o futuro de Orestes deve ser decidido por um júri popular.

Literatura e Teatro

Alguns clássicos da literatura e teatro aparecem na estória. O avô de Russell possuia uma biblioteca onde Bertie descobriu a Divina Comédia de Dante Alighieri, que foi chamado de o livro proibido.

Em Cambridge lê Pais e Filhos, de Ivan Turguniev. Segundo a Wikipédia, o protagonista do livro é Bazárov, um jovem intelectual materialista, que nega o amor, a arte, a religião e a tradição, e diz acreditar apenas em verdades cientificamente comprovadas pela experiência. Essa negação da religião e tradição podem ser encontradas na personalidade de Russell na estória.

A estória também retrata a peça de teatro Espectros, do norueguês Henrik Ibsen. Há um destaque para a frase “os pecados dos pais se repetem nos filhos”. Talvez seja uma referência ao estilo de vida dos pais de Russell, que acabou se repetindo em seu casamento com Dora.

Russell passa a recitar versos do poema Alastor, de Percy Shelley. Segundo a Wikipedia, Alastor conta a história de um poeta que persegue a parte mais obscura da natureza em busca de “verdades estranhas em terras desconhecidas”. Podemos enxergar um paralelo aqui com a busca pelos fundamentos da matemática por porte de Russell.

Ao conhecer Alys, Russell cita diversos personagens do livro Alice no País das Maravilhas, de Lewis Carroll, como o Tweedledee, Tweedledum, Gato de Cheshire e o Chapeleiro maluco.

Após o fim da Primeira Guerra Mundial Russell demonstra seu descontentamento com o dadaísmo e cita versos do poema The Second Coming, the William Butler Yeats, que refletem sua opinião.

Conclusão

Gostei bastante deste livro e recomendo a quem gosta de lógica e história da matemática. Eu particularmente não sou muito fã de história em quadrinhos, achei que se fosse em prosa a estória poderia conter mais detalhes. Lendo sobre a vida dos principais personagens na Wikipedia, penso que faltou um pouco de coesão nos fatos relatados.

Achei excelente inserir referências a clássicos da literatura para ajudar a caracterizar a personalidade de Russell. Fico feliz de ter escrito esse resumo e análise porque acho que consegui enxergar alguns detalhes que tinham passados despercebidos na primeira leitura.

Interpretei o fato da estória ser uma meta-estória como uma alusão ao paradoxo de Russell, que tem como base conjuntos que contêm a si mesmos. No caso do Logicomix é uma estória que contém a si mesma.

A encenação de Orestéia me pareceu desconexa com o restante da estória. Talvez a ideia fosse mesmo contar duas estórias independentes (a de Bertrand e a dos autores).

Leitura adicional

Alguns livros e links que eu selecionei para o aprofundamento no conteúdo do Logicomix. Na verdade só li o primeiro e é o único que posso recomendar. Os outros estão na minha pilha de leitura.

[1] The Music of the Primes de Marcus du Sautory – Já li, e gostei muito. Fala sobre os 23 problemas de Hilbert e a hipótese de Riemmann de uma maneira bastante acessível.
[2] Alice no país das maravilhas de Lewis Carroll – Lewis Carroll era um matemático e lógico. Este livro é mencionado no Logicomix.
[3] Scott Aaronson – Filosofia e Ciência da Computação Teórica, Scott Aaronson é um professor de Teoria de Computação no MIT e conhecido por seu trabalho em Computação Quântica.

Anúncios

Probabilistic Graphical Models – Semana 3

Abril 8, 2012

Este post apresenta as notas das aulas da semana 3.

Engenharia do conhecimento

Essa aula discute aspectos práticos da modelagem por redes Bayesianas ou de Markov. Não existe necessariamente um modelo correto, o que caracteriza a tarefa de criação desses modelos como uma arte e não como uma ciência.

Os modelos podem ser classificados em diversos tipos, dependendo de suas características. A seguir são descritas situações em que um tipo é mais indicado que outro, servindo mais como guia, não como regra, notando também que é possível usar modelos híbridos.

Template vs. específico. Se o problema possui variáveis com características compartilhadas, é possível usar um modelo por templates, que tem um número menor de variáveis em comparação com um modelo específico, que possui um número grande de variáveis distintas.

Generativo vs. discriminativo. Um modelo discriminativo é mais apropriado quando se tem uma tarefa particular. Nesse caso definimos características bem precisas, de modo a ter baixa correlação entre elas. Isso em geral garante um bom desempenho do modelo. Por outro lado, um modelo generativo é usado quando a tarefa não está bem especificada, pois ele é mais flexível e mais fácil de treinar.

Tipos de variáveis

Podemos classificar as variáveis de um modelo em 3 tipos:

  • alvo – as que queremos prever (saída)
  • observadas (entrada)
  • latente – escondidas. Não são explicitamente usadas, mas podem ser usadas para simplificar o modelo. Como no exemplo da Figura 1, onde a variável GMT serve apenas para não termos que definir a dependência entre W_1, \cdots W_k explicitamente usando arestas.

Figura 1: Varíavel GMT é latente

Estrutura

Em especial para redes Bayesianas, decidir a causalidade, ou seja, a orientação das arestas, não é uma tarefa simples. Dependendo da escolha, podemos ter um modelo maior ou menor. Por exemplo, se no exemplo da Figura 1 quiséssemos inverter a orientação das arestas, tornaríamos as variáveis W indpendentes, o que exigiria adicionar novas arestas entre elas.

Refinamento iterativo do modelo

Uma abordagem na criação dos modelos é o uso de iterações para refinar o modelo e ajustar parâmetros.

Na minha opinião, a modelagem de redes Bayesianas principalmente, lembra muito a modelagem de classes em engenharia de sofware, onde precisamos decidir o relacionamento entre classes (arestas) e sua hierarquia (orientação). Processos iterativos são bastante utilizados nesses casos também.


Consultas de probabilidade condicional

Uma operação comum em redes Bayesianas e de Markov é determinar a distribuição de probabilidade dado uma obervação. Suponha que queiramos determinar a distribuição de um conjunto de variáveis Y dado uma evidência E = e, ou seja, queremos calcular P(Y|E = e).

Uma alternativa é calcular a distribuição conjunta e depois fazer operações de marginalização e redução. Porém, vimos que o tamanho de um fator é exponencial no número de variáveis do modelo. Será que não há um meio mais eficiente, visto que estamos interessados em apenas uma consulta específica?

Provavelmente não, pois esse problema é NP-difícil. Mesmo o problema de, dada uma rede \Phi, decidir se P_\Phi(X = x) > 0 para um dado x é NP-difícil.

Muitos algoritmos exatos ou heurísticos usados para calcular essa distribuição são chamados de soma-produto. Isso porque a distribuição conjunta é equivalente à mulitiplicação dos fatores e a marginalização corresponde à soma de entradas do fator resultante, ou seja, temos a soma de produtos.

Vamos formalizar essa ideia. Usando a definição de probabilidade condicional, temos

P(Y | E = e) = \dfrac{P(Y, E = e)}{P(E = e)}

A distribuição P(Y, E = e) pode ser obtida a partir da distribuição conjunta removendo-se as variáveis do modelo W que não estejam nem em Y nem em E, ou seja, W = \{X_1, \cdots, X_n\} - Y - E, através de marginalização.

P(Y, E = e) = \sum_W P(Y, W, E=e)
\quad = \sum_W (\prod_{\phi_k \in \Phi} \phi_k(D_k, E = e))

Note que P(E = e) é equivalente a uma constante de marginalização. Como sabemos que P(Y | E = e) é uma distribuição, suas entradas devem somar 1, não precisamos calcular P(E = e) bastando re-normalizar P(Y, E = e).

Probabilidade a posteriori máxima

Outra consulta que podemos querer fazer em uma rede é a probabilidade a posteriori máxima ou MAP (Maximum a Posteriori). Essa consulta basicamente consiste em dizer qual o valor de maior probabilidade dado um conjunto de evidência e é importante para decidir o valor de uma variável.

Matematicamente podemos definir um MAP como:

\mbox{MAP}(Y|E=e) = \mbox{argmax}_y\{P(Y = y | E = e)\}

Nesse caso, temos que Y = \{X_1, \cdots, X_n \} - E.

Infelizmente, dada uma rede com distribuição \Phi, determinar uma atribuição x tal que P_\Phi(X = x) é máximo, também é NP-difícil.

Para esse problema, os algoritmos exatos e heurísticos são baseados em max-produto, pois consistem em encontrar o valor máximo de um produto de fatores. Note que nesse caso não temos soma (marginalização), pois não há nenhuma variável fora de Y e E a ser removida. Já vimos que:

P(Y | E = e) = \dfrac{P(Y, E = e)}{P(E = e)} \propto P(Y | E = e)

Também temos que P(Y, E = e) corresponde ao produto de fatores reduzidos, ou seja, sem as entradas correspondentes E \neq e. Vamos denotar por \phi'_k(D'_k) o fator reduzido \phi_k(D_k)

P(Y, E = e) = \frac{1}{Z} \prod_{k} \phi'_k(D'_k) \propto \prod_{k} \phi'_k(D'_k)

Para encontrar a variável que maximiza uma função, não importa a constante multiplicativa, de modo que

\mbox{argmax}_Y \{P(Y|E=e)\} = \mbox{argmax}_Y \{\prod \phi'_k (D'_k)\}


Eliminação de variáveis

Definidos esses dois problemas NP-difíceis, vamos apresentar algoritmos para resolvê-los. Primeiramente, vamos nos concentar na consulta de probabilidade condicional.

O algoritmo de eliminação de variáveis consiste em determinar a marginalização do produto de fatores, eliminando uma variável de cada vez, ao mesmo tempo em que calcula o produtório. Note que as variáveis podem ser eliminadas em qualquer ordem. Entretanto, veremos que a ordem em que as mesmas são eliminadas pode afetar a complexidade do problema.

Um passo do algoritmo é sucintamente descrito a seguir. Seja Z a variável que queremos eliminar. Denotamos por \Phi' todos os fatores quem têm Z em seu domínio, ou seja,

\Phi' = \{\phi_i \in \Phi : Z \in \mbox{Escopo}[\phi_i]\}

Multiplicamos esses fatores e obtemos um fator \psi:

\psi = \prod_{\phi_i \in \Phi'} \phi_i

Podemos fazer então a marginalização para remover Z, gerando um novo fator \tau:

\tau = \sum_{Z} \psi

Perceba que reduzimos a um novo problema com um conjunto de fatores sem a variável Z. Procedendo dessa maneira, eventualmente chegaremos no fator final.

\Phi := (\Phi \setminus \Phi') \cup \{\tau\}

Observamos que esse algoritmo funciona tanto para BN’s quanto para MN’s.

Complexidade

Podemos provar que a complexidade do algoritmo é O(Nm), onde N é o número de entradas do maior fator, m é o número de fatores. Entretanto, N \in O(d^r), onde d é a cardinalidade da maior variável e r é o tamanho do maior domínio considerando todos os fatores.

O tamanho do maior domínio depende da ordem em que as variáveis são eliminadas.

Encontrando uma ordem de eliminação

Vamos apresentar um algoritmo que visa encontrar uma ordem para melhorar a complexidade do algoritmo de eliminação de variáveis. Para isso, é conveniente definirmos grafos auxiliares.

Rede de Markov induzida. Da mesma forma que definimos uma rede de Markov induzida para a distribuição de Gibbs, podemos defini-la para uma rede Bayesiana se olharmos apenas os fatores. Lembrando, esse grafo induzido tem conjunto de vértices correspondendo às variáveis e uma aresta entre duas variáveis que aparecem no domínio de um mesmo fator.

Um detalhe é que duas variáveis que não estão conectadas no grafo induzido original, podem aparecer no domínio dos fatores intermediários gerados ao longo do algoritmo. Nesse caso, adicionamos novas arestas ao grafo, que serão chamadas arestas de preenchimento (fill edges).

O grafo induzido final é denotado por I_{\Phi,\alpha}, dado um conjunto de fatores \Phi e uma ordem \alpha. É fácil ver que todo fator usado no algoritmo de eliminação de variável corresponde a uma clique em I_{\Phi,\alpha}.

Contrariamente, temos outra observação que não é tão trivial de ver:

Teorema. toda clique maximal em I_{\Phi,\alpha} é um fator produzido durante o algoritmo.

Vamos definir mais alguns termos. A largura do grafo induzido corresponde ao tamanho da maior clique no grafo menos 1. A largura induzida minimal é a menor largura de I_{\Phi,\alpha} considerando todas as ordenações \alpha. Com isso, podemos enunciar o seguinte teorema:

Teorema. Encontrar a ordem de eliminação que gere a largura induzida minimal de I_{\Phi,\alpha} é NP-difícil.

Note porém que mesmo com uma ordem ótima, o problema de decidir a inferência ainda pode ser exponencial.

Heuristicas

Há diversas heurísticas para encontar uma boa ordem de eliminação. Apresentamos a seguir algumas gulosas baseando-se em critérios como:

  • escolha do vértice que produz o fator de menor domínio;
  • escolha do vértice que produz o fator com menor número de entradas;
  • escolha do vértice que produz o menor número de arestas de preenchimento.

Há também uma outra heurística baseada no seguinte teorema:

Teorema. O grafo induzido I_{\Phi,\alpha} é triangulado, i.e., não possui ciclos de tamanho maior que 3.

A heurística consiste então em encontrar uma triangulação com pouca largura do grafo induzido original e então é possível obter uma ordem que gera esse grafo.

Conclusões

Fiquei curioso para saber qual é a redução utilizada para mostrar a NP-completude dos problemas. Se eu tiver um tempo vou pesquisar.

A última observação ficou meio nebulosa. Como obter uma ordenação de um grafo triangulado?


Algoritmo de Passagem de mensagem

Nesta seção é apresentado um algoritmo baseado em passagem de mensagem entre vértices de um grafo. Trata-se de um algoritmo heurístico para obter distribuições marginalizadas de um dado subconjunto de variáveis.

Vamos a algumas definições.

Grafo cluster. Grafo não direcionado, onde o conjunto de vértices são clusters (subconjuntos de variáveis). Associadas às arestas, temos um subconjunto de variáveis chamado sepset, denotado por S_{i,j} \subseteq C_i \cap C_j

Dado um conjunto de fatores \Phi, atribuímos cada \phi_k \in \Phi a um cluster C_{\alpha(k)}, tal que \mbox{escopo}[\phi_k] \subseteq C_{\alpha(k)}, onde \alpha(k) corresponde ao índice do cluster ao qual o fator k foi atribuído.

Definimos o potencial de um cluster C_i, denotado por \psi(C_i) como o produto dos fatores atribuídos a ele, ou seja, \psi(C_i) = \prod_{k: \alpha(k) = i} \phi_k

Definimos a passagem de mensagens entre dois clusters C_i e C_j como um fator dado sucintamente por

\delta_{i \rightarrow j} (S_{ij}) = \sum_{C_i \setminus S_{ij}} \psi(C_i) \prod_{k \in (N(i) \setminus \{C_j\})} \delta_{k \rightarrow i}

lembrando que S_{ij} é o sepset e corresponde ao conjunto de variáveis que se quer transmitir. N(i) é o conjunto de vizinhos de C_i.

Em palavras, a definição de uma mensagem entre C_i e C_j é o produto do potencial de C_i (\psi(C_i)) pelas mensagens recebidas dos vizinhos de C_i exceto C_j, marginalizado para ficar com domínio igual a S_{ij}.

A crença (belief) de um cluster C_i, denotada por \beta(C_i) é definida como:

\beta(C_i) = \phi(C_i) \prod_{k \in N(i)} \delta_{k \rightarrow i}

ou seja, o produto de todas as mensagem recebidas dos vizinhos de C_i e seu potencial.

Com isso, podemos definir o algoritmo de propagação de mensagens. Basicamente, inicializamos cada vértice do grafo com o fator nulo e efetuamos trocas de mensagens por um certo número de informações.

Algoritmo de propagação de crenças.

  • Atribua cada fator \phi_k \in \Phi para cada cluster C_{\alpha(k)}
  • Construa os potenciais \psi(C_i)
  • Inicializa todas as mensagens com 1 (equivalente ao fator nulo)
  • Repita:
    • Selecione uma aresta (i,j) e faça a passagem de mensagem, atualizando \delta_{i \rightarrow j}
  • Calcule a crença de cada cluster \beta(C_i)

Alguns detalhes que o algoritmo não especifica é: quantas vezes iterar? Uma observação é que o algoritmo pode não convergir. Além disso, como escolher a ordem das arestas? Uma sugestão é o uso do Round-Robin.

Propriedades dos grafos cluster

Um grafo cluster deve possuir as seguintes propriedades.

Preservação de família. (family preservation) Para cada fator \phi_k \in \Phi, deve existir um cluster C tal que \mbox{Escopo}[\phi_k] \subseteq C, para que possamos atribuir o fator a algum cluster.

Caminho de Interseções. (tradução livre de Running Intersection) Essa propriedade diz que para cada par de vértices C_i e C_j no grafo e uma variável X \in C_i \cap C_j, deve existir um único caminho entre C_i e C_j tal que X \in S_{u,v}, para toda aresta (u, v) neste caminho.

Intuitivamente, isto serve para garantir que X possa ser “transportado” entre C_i e C_j. Por outro lado, a existência de mais de um caminho implica em ciclos, o que poderia causa uma retro-alimentação indesejável.

Uma forma alternativa de definir essa propriedade é através da decomposição em árvore, que diz que para cada variável X, o conjunto de vértices e arestas que contêm X, (\{C_k | X \in C_k\} e \{(i,j) | X \in S_{ij}\}, respectivamente), devem formar uma árvore.

Construção de um grafo cluster

Grafo cluster Bethe. é um tipo especial de grafo cluster bastante simples de construir e que satisfaz as duas propriedades definidas acima. Ele é composto de dois tipos de vértices:

Clusters grandes correspondendo ao domínio de cada fator, ou seja, C_{\phi_k} = \mbox{Escopo}(\phi_k) e clusters pequenos, formado por apenas uma variável, C_i = \{X_i\}.

Existe uma aresta (C_{\phi_k}, C_{i}) se X_i \in C_k.

É fácil ver que esse grafo satisfaz a propriedade dos caminho de interseções, pois ao isolarmos uma variável, o conjunto de vértices e arestas que a contém é uma estrela.

Conclusões

Não ficou muito claro como podemos usar esse segundo algoritmo para calcular uma distribuição de probabilidade condicionada a uma observação, por exemplo P(Y|E=e). Pelo que entendi, a crença de um cluster representa a distribuição marginalizada das variáveis contidas nele.

Assim, podemos inicialmente reduzir os fatores removendo as entradas tais que E \neq e e adicionar um cluster contendo Y. Executamos o algoritmo e fazemos a consulta da crença neste cluster.


Puzzles

Dezembro 23, 2009

Sempre gostei de resolver sudokus como passatempo. Ultimamente tenho experimentado alguns puzzles diferentes no site puzzle picnic. Neste site tem muitos tipos de puzzles e alguns deles lembram muito problemas de teoria da computação, como o Hamilton Maze, que consiste em determinar um ciclo hamiltoniano e o Shadows que lembra algum tipo de problema de cobertura.

Lembro de algum professor falando sobre problemas NP-difíceis, em como o computador pode levar anos para resolver este tipo de problema, enquanto seres humanos têm capacidade de encontrar a solução muito mais facilmente. A maioria, se não a totalidade, é NP-difícil, inclusive o sudoku [1][2].

Implementação

Sudoku

Implementar um resolvedor de sudoku é bem simples, pois o problema pode ser escrito facilmente com linguagem matemática na forma de restrições. Já implementei diversas vezes um resolvedor de sudokus durante a maratona. Basicamente é um algoritmo de força-bruta: para cada célula chutamos um valor de 1 a 9 que não viole as restrições de linhas, colunas nem sub-quadrados (3×3). Para cada valor chutado, recursamos nas células restantes. Para cada valor chutado, modificamos as restrições para as células seguintes. Por exemplo, se chutarmos o valor 3 na célula (1,2), sabemos que não haverá o valor 3 em qualquer célula da linha 1, ou da coluna 2 ou do mesmo sub-quadrado que (1,2).

O modo mais eficiente que consegui encontrar foi, para cada nível da recursão, escolher a célula com menos possibilidades de valores a serem chutados. Essa é uma heurística comum em algoritmos de força-bruta pois desta forma diminuímos o tamanho da árvore de busca. Desta forma consigo resolver sudokus 9×9 muito rapidamente (16×16 já não fica tão eficiente).

Nonograma

Nonograma (picross) preenchido

Neste jogo temos que preencher algumas células. Em cada linha (coluna) há alguns números. Cada número deste indica que deve haver um bloco deste tamanho de células contínuas em cada linha (coluna) preenchidas. Blocos são separados por pelo menos um espaço em branco.

Fui implementar um resolvedor para este problema, mas tentei implementar as regras lógicas que eu pensei para resolver este problema como ser humano. Achei extremamente complicado e acabei desistindo :( Também não cheguei a pensar em nenhuma força bruta além da trivial de chutar 0 ou 1 em cada célula para no final verificar se satisfez os valores das linhas (colunas).

Referências:
[1] Tese de Takayuki Yato http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf
[2] NP-dificuldade de alguns puzzles http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Games_and_puzzles