Este artigo é uma tradução do artigo original de Ola Bini. Agradeço ao autor por permitir que eu realizasse tradução de seus artigos desta série. Sintan-se livres para apontar erros e sugestões para melhorias na tradução.

Acho que se você se interessa por Ruby, deve saber quem é Ola Bini. Se não conhece, recomendo que leia a entrevista feita pelo Akita.

Eu tenho estudado algumas coisas ligadas a IA (Inteligência Artificial), especialmente aprendizado de máquina (Machine Learning - ML). Pretendo escrever aqui alguns artigos de ML no futuro. Enquanto isso vou começar com esta tradução, já que achei a série de artigos do Ola bastante interessante. O código dele também é muito bem escrito.

---

Paradigmas da Programação para Inteligência Artificial (em Ruby)

Já que eu não me canso de participar de diferentes projetos, decidi inciar algo em que pensei a começar faz um bom tempo. Existem algumas razões para fazê-lo, a principal entre elas é que eu queria voltar a brincar com IA, e eu queria ter um projeto com muitas peçinhas que eu possa construir quando tenho algum tempo livre. Se, ao mesmo tempo, o projeto acabar por se tornar educacional ou útil para outras pessoas, bem, não estou reclamando!

Então, o quê é?

Bem, primeiro eu gostaria de apresentar um livro. Ele se chama Paradigms of Artificial Intelligence Programming ou, de maneira mais curta, PAIP. Foi escrito por Peter Norvig, que também escrevel alguns outros livros sobre IA. Atualmente ele é diretor de pesquisa no Google. O PAIP é provalmente meu livro preferido de IA, e também meu livro favorito de Common Lisp. É realmente um livro excelente. De verdade. Se você tem algum interesse em um destes dois assuntos você deve adquirí-lo. O PAIP não cobre assuntos de ponta da IA. Ao invés disso ele usa a visão histórica e analisa diversos exemplos de épocas diferentes, indo dos primeiros programas até coisas bastante avançadas.

Eu o li inúmeras vezes, examinei o código, refinei-o e assim por diante. É muito divertido. Mas isso foi faz alguns anos. Então, basicamente, o que quero fazer é explorar o livro de novo. Mas desta vez escreverei todos os programas em Ruby - convertendo-os do Common Lisp e então talvez melhorando-os um pouco para fazê-los mais idiomáticos. E planejo colocar aqui. Ou melhor, vou colocar o código fonte em http://www.github.com/olabini/paipr. Irei blogar sobre o código que escrever. Você não tem necessariamente que possuir o livre, já que eu irei cercar o código com algumas descrições e explicações.

Mais uma vez, então, por que alguém deveria se importar? Bem, não sei. Talvez ninguém ligue. Mas para mim, pessoalmente, será uma experiência interessante converter Common Lisp idiomático para Ruby idiomático. Será divertido revisitar as antigas abordagens da IA. E poderá servir como uma boa introdução, com bastante código, ao assunto para qualquer um que se interesse por ele.

Eu tenho a permissão de Peter Norvig para fazer isto. O código Ruby que estou escrevendo é coberto pela licença MIT, enquanto qualquer código Lisp colocada como parte deste exercício é coberto por esta licença: http://norvig.com/license.html.

Também atente-se ao fato que nem sempre escreverei o código Ruby mais óbvio - Será bom que ele tenha algumas conexões com código Lisp original.

---

Parte 1 - Geração de Linguagem

Artigo original de Ola Bini

Este artigo é o primeiro da série de artigos sobre o PAIPr. Leia a introdução acima para entender mais sobre o conceito.

Hoje eu gostaria de começar olhando o Capítulo 2. Você pode encontrar o código em lib/ch02 no repositório.

O Capítulo 2 introduz o Common Lisp através da criação de uma séria de maneiras de se fazer a geração de sentenças em inglês, baseando-se em simples gramáticas. É um capítulo interessante para se começar, visto que o código é simples e então é simples comparar as versões em Ruby e Common Lisp.

A primeira parte que temos que considerar é o arquivo common.rb, que contém dois métodos que precisaremos mais tarde:

require 'pp'

def one_of(set)
  [set.random_elt]
end

class Array
  def random_elt
    self[rand(self.length)]
  end
end

Como você pode ver eu também requeri o pp, para facilitar a a impressão de estruturas posteriormente.

Ambos os métodos oneof (um de) e e randomelt (elemento aleatório) são métodos extremamente simples, mas é sempre legal ter este tipo de abstração. Estou mantendo a mesma nomenclatura do livro para estes dois métodos.

require 'common'
def sentence; noun_phrase + verb_phrase; end
def noun_phrase; article + noun; end
def verb_phrase; verb + noun_phrase; end
def article; one_of %w(the a); end
def noun; one_of %w(man ball woman table); end
def verb; one_of %w(hit took saw liked); end

Como você pode ver, todos os métodos apenas definem sua estrutura combinando o resultado de métodos mais básicos. Uma frase substantiva (noun_phrase) é formada por um artigo (article) e então um substantivo (noun). Um artigo é ‘o/a’ (the) ou ‘um/uma’ (a) e um substantivo pode ser ‘homem’ (man). ‘bola’ (ball), ‘mulher’ (women) ou ‘mesa’ (table). Se você executar a sentença algumas vezes verá que em algumas ocasiões irá obter sentenças perfeitamente plausíveis como [“uma” “bola”,”acertou”,”a”,”mesa” ]. Mas você também pode obter coisas menos interessantes, como [“uma”,”bola”,”acertou”,”uma”,”bola”]. Neste ponto o espaço para variação é bastante limitado, mesmo assim você pode notar que há uma versão simplificada da língua inglesa nestes métodos.

Para criar um exemplo que envolve algumas estruturas mais interessantes, podemos introduzir adjetivos (adjectives) e preposições (prepositions). Dado que estes podem se repetir zero ou muitas vezes, nós iremos usar uma produção chamada PP* e Adj* (ppstar e adjstar no código). Isto está no simple2.rb:

require 'simple'

def adj_star
  return [] if rand(2) == 0
  adj + adj_star
end

def pp_star
  return [] if rand(2) == 0
  pp + pp_star
end

def noun_phrase; article + adj_star + noun + pp_star; end
def pp; prep + noun_phrase; end
def adj; one_of %w(big little blue green adiabatic); end
def prep; one_of %w(to in by with on); end

Nada muda muito aqui, exceto que em ambas produções opcionais retornamos aleatoriamente um array vazio em 50% do tempo. E então eles podem se chamar recursivamente. A produção de frases substantivas também muda um pouco, e adj e prep nos dão os dois novos terminais necessários. Se você tentar usar deste modo, poderá obter alguns resultados ainda mais interessantes, como por exemplo: [“uma”, “mesa”, “pegou”, “um”, “grande”, “adiabático”, “homem”]. É claro que ainda permanece sem sentido. E parece que essa abordagem com aleatoriedade gerará algumas saídas bem grandes em alguns casos. Para fazer esta solução realmente boa é provável que tenhamos que incluir algum viés redutor nos adjetivos e preposições baseado no tamanho da string já gerada.

Outro problema com esta abordagem é que ela é meio incômoda. Usar métodos para a gramática provavelmente não é uma boa escolha a longo prazo. Mais especificamente, nós ficamos atados a esta implementação tendo a gramática sendo representada por métodos.

Uma alternativa viável é representar tudo como uma definição de gramática - usando uma solução baseada em regras. A primeira parte do arquivo rule_based.rb se parece com isto:

require 'common'

# Uma gramática para um subconjunto trivial da língua inglesa
$simple_grammar = {
  :sentence => [[:noun_phrase, :verb_phrase]],
  :noun_phrase => [[:Article, :Noun]],
  :verb_phrase => [[:Verb, :noun_phrase]],
  :Article => %w(the a),
  :Noun => %w(man ball woman table),
  :Verb => %w(hit took saw liked)}

# A gramática usada pelo gerador. Inicialmente ela é $simple_grammar, mas
# podemos mudar para outras gramáticas
$grammar = $simple_grammar

Note que estou usando arrays duplos para as produções que não são terminais. Existe uma razão para isso que ficará mais clara mais tarde com as gramáticas que se baseiam nisto. Neste instante, entretanto, é fácil ver que uma produção é ou uma lista de palavras, ou uma lista de lista de produções. Os nomes das produções que começam com maiúsculas são terminais - esta é uma convenção na maioria das gramáticas. Eu não utilizei letras maiúsculas quando usando os métodos pois os métodos em Ruby nomeados desta maneira podem causar problemas adicionais quando chamados.

Agora que realmente temos a gramática, necessitamos também de um método ajudante (helper), PAIP define rule-lhs, rule-rhs e rewrites (reescreve), mas o único que realmente precisamos aqui é o rewrites (Do arquivo rule_based.rb):

def rewrites(category)
  $grammar[category]
end

E, na verdade, poderíamos nos virar sem ele também, mas com ele a legibilidade fica melhor em relação a usar um indexador de acesso.

A última coisa que precisamos é o método que realmente cria uma sentença a partir da gramática. Ele se parece com isso:

def generate(phrase)
  case phrase
  when Array
    phrase.inject([]) { |sum, elt|  sum + generate(elt) }
  when Symbol
    generate(rewrites(phrase).random_elt)
  else
    [phrase]
  end
end

Se o que nos é perguntando para gerar é um array, então geraremos tudo o que está dentro deste array e então combinamos estes elementos. Se a produção for um símbolo, então pegamos todas possíveis reescritas e pegamos um elemento aleatório delas. Atualmente toda produção tem uma reescrita, então o ramdom_elt não é estritamente necessário - mas como você verá mais tarde ele é bem bacana. E finalmente, se frase não for um array nem um símbolo, nós apenas retornaremos a frase como o elemento gerado.

Eu gosto especialmente do uso do método inject como uma versão mais geral de (mappend #gera a frase). Claro que, por legibilidade, seria possível também implementar o método mappend:

def mappend(sym, list)
  list.inject([]) do |sum, elt|
    sum + self.send(sym, elt)
  end
end

Mas ao invés disso eu preferi utilizar inject diretamente, já que ele é mais idiomático. Note que esta versão do mappend não funciona exatamente igual ao mappend do Common Lisp, visto que ela não permite uma função lambda.

Voltando ao método generate (gera). Se você rodasse generate(:sentence), você teria o mesmo tipo de saída do que rodando com a versão baseada no método - com a diferença de que mudar as regras é muito mais simples agora.

Então, por exemplo, você pode usar esse código da bigger_grammar.rb , que cria uma definição grande de gramática e então usá-la como gramática padrão:

$bigger_grammar = {
  :sentence => [[:noun_phrase, :verb_phrase]],
  :noun_phrase => [[:Article, :'Adj*', :Noun, :'PP*'], [:Name],
                   [:Pronoun]],
  :verb_phrase => [[:Verb, :noun_phrase, :'PP*']],
  :'PP*' => [[], [:PP, :'PP*']],
  :'Adj*' => [[], [:Adj, :'Adj*']],
  :PP => [[:Prep, :noun_phrase]],
  :Prep => %w(to in by with on),
  :Adj => %w(big little blue green adiabatic),
  :Article => %w(the a),
  :Name => %w(Pat Kim Lee Terry Robin),
  :Noun => %w(man ball woman table),
  :Verb => %w(hit took saw liked),
  :Pronoun => %w(he she it these those that)}

$grammar = $bigger_grammar

Esta gramática inclui alguns elementos que fazem a saída um pouco melhor. Por exemplo, nós temos nomes (names) aqui, e também pronomes (pronouns). Uma das razões para esta gramática ser mais fácil de usar é porque podemos definir diferentes versões das produções. Então uma frase substantiva pode, por exemplo, o mesmo que definimos antes, mas também pode ser apenas um único nome ou um único pronome. Nós usamos isso para lidar com as produções recursivas PP* e Adj*. Você pode também ver porque as produções são definidas com um array dentro de um array. Isto é para permitir opções nesta gramática.

Uma sentença típica desta gramática (chamando generate(:sentence)) resulta em [“Terry”, “saw”, “that”] (Terry viu aquilo) ou [“Lee”, “took”, “the”, “blue”, “big”, “woman”] (Lee pegou a grande mulher azul”).

Portanto é mais fácil mudar estas regras. Além disso, acredite que é mais fácil ler e entender as regras aqui. Mas uma das mudanças mais importantes trazidas pela abordagem orientada a dados é que você pode usar as mesmas regras para diferentes propósitos. Diga que queremos uma árvore de sentenças, que inclui o nome da produção usada para esta parte na árvore. Isto é tão simples quanto definir um novo método generate (no arquivo generate_tree.rb):

require 'bigger_grammar'

def generate_tree(phrase)
  case phrase
  when Array
    phrase.map { |elt| generate_tree(elt) }
  when Symbol
    [phrase] + generate_tree(rewrites(phrase).random_elt)
  else
    [phrase]
  end
end

Esse código segue os mesmos padrões que o generate, com algumas pequenas mudanças. Você pode ver que no lugar de anexar os resutados do array em conjunto, nó apenas usamos o método map em cada elemento, Isto porque precisamos de mais subarrays para criar uma árvore. Da mesma maneira quando temos um símbolo nós prefixiamos isto ao array gerado. E, realmento, nesta altura é bem interessante darmos uma olhada na versão Lisp deste código:

(defun generate-tree (phrase)
  (cond ((listp phrase)
         (mapcar #'generate-tree phrase))
        ((rewrites phrase)
         (cons phrase
               (generate-tree (random-elt (rewrites phrase)))))
        t (list phrase)))

E você pode ver que a estrutura é, na maior parte, a mesma. Eu fiz algumas escolhas diferentes na representação, o que significa que estou checando se a frase é um símbolo ao vés de ver se a reescrita de um símbolo é não nula. A chamada a mapcar é equivalente a chamada de map em Ruby.

O que ele gera então? Chamando-o como “pp generate_tree(:sentence)”, obtenho algo como isto:

[:sentence,
 [:noun_phrase, [:Name, "Lee"]],
 [:verb_phrase,
  [:Verb, "saw"],
  [:noun_phrase,
   [:Article, "the"],
   [:"Adj*",
    [:Adj, "green"],
    [:"Adj*"]],
   [:Noun, "table"],
   [:"PP*"]],
  [:"PP*"]]]

que mapeia muito bem para nossa gramática. Nós podemos gerar todas possíveis sentenças para uma gramática sem recursão, usando a mesma abordagem orientada a dados.

O código para esta abordagem é encontrado em generate_all.rb:

def generate_all(phrase)
  case phrase
  when []
    [[]]
  when Array
    combine_all(generate_all(phrase[0]),
                generate_all(phrase[1..-1]))
  when Symbol
    rewrites(phrase).inject([]) { |sum, elt|  sum + generate_all(elt) }
  else
    [[phrase]]
  end
end

def combine_all(xlist, ylist)
  ylist.inject([]) do |sum, y|
    sum + xlist.map { |x| x+y }
  end
end

Se você rodar generate(:sentence) você obterá uma lista de 256 possíveis sentenças para está simples gramática. Neste caso o algoritmo é um pouco mais complicado. Ele também está usando o idioma Lisp de trabalhar no primeiro elemento de uma lista e então repetir-se no restante dela. Isto possibilita combinar tudo em conjunto. Assumo que seja possível criar algo convenientemente esperto baseado nos novos métodos Array#Permutations ou possivelmente Enumerable#group_by ou zip.

É interessante quão bem o uso de mappend e mapcar mapeiam para o uso de inject e map neste código.

Note que eu estive usando variáveis globais para as gramáticas nesta implementação. Uma alternativa que provavelmente é melhor é passar adiante um parâmetro opcional para os métodos. Se nenhuma gramática é fornecida, apenas use a constante padrão no lugar.

De qualquer modo, o código para este capítulo está no repositório. Brinque um pouco com ele e veja se você consegue encontrar algo interessante. Este código é definitivamente mais uma introdução a Lisp, do que um sério programa de IA - embora ele mostre o tipo de abordagens que têm sido utilizadas para geração primitiva de código.