Aprendiz indutivo de primeira ordem

No aprendizado de máquina, o Aprendiz Indutivo de Primeira Ordem (AIPO) é um algoritmo de aprendizado baseado em regras.

História

Desenvolvido em 1990 por Ross Quinlan, AIPO aprende funções livres de Cláusulas de Horn, um subconjunto de cálculo de predicados de primeira ordem. Dados exemplos positivos e negativos de algum conceito e um conjunto de conhecimentos prévios de predicados, AIPO indutivamente gera um conceito definido logicamente, ou regra, para o conceito. A regra induzida não deve conter nenhuma constante (cor(X,vermelha) se torna cor(X,Y), vermelha(Y)) ou símbolos de função, mas pode permitir predicados negativos; e conceitos recursivos também são aprendíveis. Como o algoritmo ID3, AIPO escala usando uma métrica baseada na teoria da informação, para construir uma regra que cubra os dados. Diferente do ID3, entretanto, AIPO usa um método "separar-para-conquistar" em vez de "dividir para conquistar", focando em criar uma regra por vez e coletando exemplos descobertos para a próxima iteração do algoritmo.

Algoritmo

O algoritmo AIPO é como segue:

Entrada Lista de exemplos

Saída Regra em lógica de predicados de Primeira-Ordem

AIPO(Exemplos)

Sejam Pos os exemplos positivos

Sejam Pred os predicados a serem aprendidos

Até que Pos esteja vazio, faça:

Sejam Neg os exemplos negativos

Defina Corpo como vazio

Chame AprenderCorpoDaCláusula

Adicione Pred' ← Corpo à regra

Remova de Pos todos os exemplos que satisfazem Corpo

Procedural AprenderCorpoDaCláusula

Até que Neg esteja vazio, faça:

Escolha um literal L

Una L à Corpo

Remova de Neg exemplos que não satisfaçam L

Exemplo

Suponha que a tarefa do AIPO é aprender o conceito de avô(X,Y), dadas as relações pai(X,Y) e mãe(X,Y). Além disso, suponha que nosso Body atual consiste de avô(X,Y) ← mãe(X,Z). Isso pode ser estendido unindo o Body com quaisquer literais pai(X,X), pai(Y,Z), mãe(U,Y) ou vários outros. Para criar esse literal, o algoritmo deve escolher ambos o nome do predicado e um conjunto de variáveis para esse (pelo menos um dos quais é necessário a ser já presente numa literal não-negação da cláusula). Se AIPO estende uma cláusula 'avô(X,Y) ← verdadeiro, unindo o literal mãe(X,Z), isso é, introduzindo a nova variável Z. Exemplos positivos agora consistem desses valores <X,Y,Z>, tal que avô(X,Y) é verdadeiro e mãe(X,Z) é verdadeiro; e exemplos negativos são aqueles em que avô(X,Y) é verdadeiro mas mãe(X,Z) é falso.

Na próxima iteração de AIPO, depois que mãe(X,Z) foi adicionado, o algoritmo vai considerar todas as combinações de nomes de predicados e variáveis, tal que pelos menos uma variável no novo literal está presente na cláusula existente. Isso resulta em um espaço de busca muito grande. Muitas extensões da teoria AIPO mostraram que acréscimos ao algoritmo básico podem reduzir esse espaço de busca, algumas vezes drasticamente.

Extensões

O algoritmo FOCL (First Order Combined Learner) estende AIPO em uma variedade de maneiras, que afetam como FOCL seleciona literais para testar enquanto estende uma cláusula em construção. Restrições no espaço de busca são permitidas, como são predicados que são definidos em uma regra em vez de um conjunto de exemplos (chamados "predicados intencionais"); sobretudo, uma hipótese potencialmente incorreta é permitida como uma aproximação inicial para o predicado a ser aprendido. O objetivo principal do FOCL é incorporar métodos de aprendizagem baseada em explicação (EBL) no método empírico de AIPO.

Mesmo quando nenhum conhecimento adicional é fornecido para FOCL sobre AIPO, entretanto, ele utiliza uma estratégia iterativa de busca semelhante ao "busca em profundidade": primeiro FOCL tenta aprender uma cláusula através sem introduzir variáveis livres. Se isso falhar (nenhum ganho positivo), uma variável livre por falha é permitida até que o número de variáveis livres exceda o máximo usado para qualquer predicado.

Restrições

Ao contrário do AIPO, que não coloca restrições de tipos em suas variáveis, FOCL usa tipagem como uma maneira barata de incorporar uma simples forma de conhecimento prévio. Por exemplo, o predicado vive(X,Y) pode ter tipos viveEm (pessoa, localidade). Predicados adicionais podem precisar ser introduzidos, embora - sem tipos perto(X,Y) que poderiam determinar se as pessoas X e Y vivem lado a lado; ou quando duas localidades são próximas entre si. Com tipos, dois predicados diferentes perto(pessoa, pessoa) e perto(localidade, localidade) precisariam existir para essa funcionalidade ser mantida. Entretanto, esse mecanismo de tipagem elimina a necessidade para predicados como éPessoa(X) ou éLocalidade(Y), e não precisa considerar viveEm(A,B) quando A e B são definidas como variáveis de pessoas, reduzindo o espaço de busca. adicionalmente, a tipagem pode aumentar a precisão da regra resultante ao eliminar a consideração de literais impossíveis como viveEm(A,B), o que, obstante, pode parecer um alto ganho de informação.

Em vez de implementar predicados triviais, como igual(X,X) ou entre(X,X,Y), FOCL introduz restrições implícitas às variáveis, reduzindo ainda mais o espaço de busca. Alguns predicados devem ter todas as variáveis únicas, outros devem ter comutatividade (adjacente(X,Y) é equivalente a adjacente(Y,X)), outros ainda podem exigir que uma determinada variável esteja presente na cláusula atual; e muitas outras restrições potenciais.

Regras operacionais

As regras operacionais são aquelas regras que são definidas extensionalmente, ou como uma lista de tuplas em que um predicado é verdadeiro. AIPO permite apenas regras operacionais, enquanto FOCL amplia sua base de conhecimento para permitir combinações de regras chamadas regras não-operacionais, assim como regras parcialmente ou incorretamente definidas para robustez. Permite definições parciais reduzirem a quantidade de trabalho necessário, já que o algoritmo não precisa gerar essas definições parciais para si; e as regras incorretas não aumentam significativamente o trabalho necessário, uma vez que são descartadas se não forem julgadas para proporcionar ganho de informação positiva. Regras não-operacionais são vantajosas já que as regras individuais que combinam podem não fornecer ganho de informação por conta própria, mas são úteis quando tomadas em conjunto. Se um literal com o máximo ganho de informação em uma iteração de FOCL é não-operacional, este é operacionalizado e sua definição é adicionada à cláusula em construção.

Entradas Literal de ser operacionalizado, Lista de exemplos positivos, Lista de exemplos negativos

Saída Literal na forma operacional

Operacionalizar(Literal, Exemplos positivos, Exemplos negativos)

Se Literal é operacional

Retorne Literal

Inicialize LiteraisOperacionais como conjunto vazio

Para cada cláusula na definição de Literal

Calcule o ganho de informação da cláusula sobre exemplos positivos e exemplos negativos

Para a cláusula com o ganho máximo

Para cada literal L na cláusula

Adicione Operacionalizar(L, Exemplos positivos, Exemplos negativos) para LiteraisOperacionais

Uma regra operacional pode ser o literal menosQue(X,Y); e uma regra não-operacional pode ser entre(X,Y,Z) ← menosQue(X,Y), menosQue(Y,Z).

Regras iniciais

A adição de regras não-operacionais para a base de conhecimento aumenta o tamanho do espaço que FOCL deve procurar. Ao invés de simplesmente fornecer o algoritmo com um conceito alvo (e.g. avô(X,Y)), o algoritmo toma como entrada um conjunto de regras não-operacionais que ele testa para correção e operacionaliza por seu conceito aprendido. Um conceito alvo correto irá melhorar claramente o tempo computacional e a precisão, mas mesmo um conceito incorreto dará o algoritmo de uma base, a partir da qual irá trabalhar e melhorar a precisão e o tempo.