b"\n_START_ARTICLE_\nAprendiz indutivo de primeira ordem\n_START_SECTION_\nHist\xc3\xb3ria\n_START_PARAGRAPH_\nDesenvolvido em 1990 por Ross Quinlan, AIPO aprende fun\xc3\xa7\xc3\xb5es livres de Cl\xc3\xa1usulas de Horn, um subconjunto de c\xc3\xa1lculo de predicados de primeira ordem. Dados exemplos positivos e negativos de algum conceito e um conjunto de um conhecimento pr\xc3\xa9vio predicados, AIPO indutivamente gera um conceito definido logicamente ou regra para o conceito. A regra induzida n\xc3\xa3o deve conter nenhuma constante (cor(X,vermelha) se torna cor(X,Y), vermelha(Y)) ou s\xc3\xadmbolos de fun\xc3\xa7\xc3\xa3o, mas pode permitir predicados negativos; conceitos recursivos tamb\xc3\xa9m s\xc3\xa3o aprend\xc3\xadveis. Como o algoritmo ID3, AIPO escala usando uma m\xc3\xa9trica baseada na teoria da informa\xc3\xa7\xc3\xa3o para construir uma regra que cubra os dados. Diferente de ID3, entretanto, AIPO usa um m\xc3\xa9todo separar-para-conquistar em vez de dividir para conquistar, focando em criar uma regra por vez e coletando exemplos descobertos para a pr\xc3\xb3xima itera\xc3\xa7\xc3\xa3o do algoritmo.\n_START_SECTION_\nExemplo\n_START_PARAGRAPH_\nSuponha que a tarefa do AIPO \xc3\xa9 aprender o conceito de av\xc3\xb4(X,Y) dadas as rela\xc3\xa7\xc3\xb5es pai(X,Y) e m\xc3\xa3e(X,Y). Al\xc3\xa9m disso, suponha que nosso Body atual consiste de av\xc3\xb4(X,Y) \xe2\x86\x90 m\xc3\xa3e(X,Z). Isso pode ser estendido unindo Body com quaisquer literais pai(X,X), pai(Y,Z), m\xc3\xa3e(U,Y), ou v\xc3\xa1rios outros - para criar esse literal, o algoritmo deve escolher ambos o nome do predicado e um conjunto de vari\xc3\xa1veis para o predicado (pelo menos um dos quais \xc3\xa9 necess\xc3\xa1ria a ser j\xc3\xa1 presente numa literal n\xc3\xa3o-negado da cl\xc3\xa1usula). se AIPO estende uma cl\xc3\xa1usula 'av\xc3\xb4(X,Y) \xe2\x86\x90 verdadeiro unindo o literal m\xc3\xa3e(X,Z), isso \xc3\xa9, introduzindo a nova vari\xc3\xa1vel Z. Exemplos positivos agora consistem desses valores <X,Y,Z> tal que av\xc3\xb4(X,Y) \xc3\xa9 verdadeiro e m\xc3\xa3e(X,Z) \xc3\xa9 verdadeiro; exemplos negativos s\xc3\xa3o aqueles onde av\xc3\xb4(X,Y) \xc3\xa9 verdadeiro mas m\xc3\xa3e(X,Z) \xc3\xa9 falso._NEWLINE_Na pr\xc3\xb3xima itera\xc3\xa7\xc3\xa3o de AIPO depois que m\xc3\xa3e(X,Z) foi adicionado, o algoritmo vai considerar todas as combina\xc3\xa7\xc3\xb5es de nomes de predicados e vari\xc3\xa1veis tal que pelos menos uma vari\xc3\xa1vel no novo literal est\xc3\xa1 presente na cl\xc3\xa1usula existente. Isso resulta em um espa\xc3\xa7o de busca muito grande. Muitas extens\xc3\xb5es da teoria AIPO mostraram que acr\xc3\xa9scimos ao algoritmo b\xc3\xa1sico podem reduzir esse espa\xc3\xa7o de busca, algumas vezes, drasticamente.\n_START_SECTION_\nExtens\xc3\xb5es\n_START_PARAGRAPH_\nO 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\xc3\xa1usula em constru\xc3\xa7\xc3\xa3o. Restri\xc3\xa7\xc3\xb5es no espa\xc3\xa7o de busca s\xc3\xa3o permitidas, como s\xc3\xa3o predicados que s\xc3\xa3o definidas em uma regra em vez de um conjunto de exemplos (chamados predicados intencionais); sobretudo, uma hip\xc3\xb3tese potencialmente incorreta \xc3\xa9 permitida como uma aproxima\xc3\xa7\xc3\xa3o inicial para o predicado a ser aprendido. O objetivo principal do FOCL \xc3\xa9 incorporar m\xc3\xa9todos de aprendizagem baseada em explica\xc3\xa7\xc3\xa3o (EBL) no m\xc3\xa9todo emp\xc3\xadrico de AIPO._NEWLINE_Mesmo quando nenhum conhecimento adicional \xc3\xa9 fornecido para FOCL sobre AIPO, entretanto, ele utiliza uma estrat\xc3\xa9gia iterativa de busca semelhante ao busca em profundidade: primeiro FOCL tenta aprender uma cl\xc3\xa1usula atrav\xc3\xa9s sem introduzir vari\xc3\xa1veis livres. Se isso falhar (nenhum ganho positivo), uma vari\xc3\xa1vel livre por falha \xc3\xa9 permita at\xc3\xa9 que o n\xc3\xbamero de vari\xc3\xa1veis livres exceda o m\xc3\xa1ximo usado para qualquer predicado.\n_START_SECTION_\nRestri\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nAo contr\xc3\xa1rio do AIPO, Que n\xc3\xa3o coloca restri\xc3\xa7\xc3\xb5es de tipos em suas vari\xc3\xa1veis, FOCL usa tipagem como uma maneira barata de incorporar uma simples forma de conhecimento pr\xc3\xa9vio. Por exemplo, o predicado viveEm(X,Y) pode ter tipos viveEm(pessoa, localidade). Predicados adicionais podem precisar de ser introduzidos, embora - sem tipos, perto(X,Y) poderia determinar se as pessoas X e Y vivem lado a lado, ou quando duas localidades s\xc3\xa3o pr\xc3\xb3ximas entre si. com tipos, dois predicados diferentes perto(pessoa, pessoa) e perto(localidade, localidade) precisaria existir para essa funcionalidade ser mantida. Entretanto, esse mecanismo de tipagem elimina a necessidade para predicados como \xc3\xa9Pessoa(X) ou \xc3\xa9Localidade(Y), e n\xc3\xa3o precisa considerar viveEm(A,B) quando A e B s\xc3\xa3o definidas como vari\xc3\xa1veis de pessoas, reduzindo o espa\xc3\xa7o de busca. adicionalmente, tipagem pode aumentar a precis\xc3\xa3o da regra resultante ao eliminar a considera\xc3\xa7\xc3\xa3o de literais imposs\xc3\xadveis como viveEm(A,B) o que, obstante, pode parecer um alto ganho de informa\xc3\xa7\xc3\xa3o._NEWLINE_Em vez de implementar predicados triviais, como igual(X,X) ou entre(X,X,Y), FOCL introduz restri\xc3\xa7\xc3\xb5es impl\xc3\xadcitas \xc3\xa0s vari\xc3\xa1veis, reduzindo ainda mais o espa\xc3\xa7o de busca. Alguns predicados devem ter todas as vari\xc3\xa1veis \xc3\xbanicas, outros devem ter comutatividade (adjacente(X,Y) \xc3\xa9 equivalente a adjacente(Y,X)), outros ainda podem exigir que uma determinada vari\xc3\xa1vel esteja presente na cl\xc3\xa1usula atual, e muitas outras restri\xc3\xa7\xc3\xb5es potenciais.\n_START_SECTION_\nRegras iniciais\n_START_PARAGRAPH_\nA adi\xc3\xa7\xc3\xa3o de regras n\xc3\xa3o-operacionais para a base de conhecimento aumenta o tamanho do espa\xc3\xa7o que FOCL deve procurar. Ao inv\xc3\xa9s de simplesmente fornecer o algoritmo com um conceito alvo (e.g. av\xc3\xb4(X,Y)), o algoritmo toma como entrada um conjunto de regras n\xc3\xa3o-operacionais que ele testa para corre\xc3\xa7\xc3\xa3o e operacionaliza por seu conceito aprendido. Um conceito alvo correto ir\xc3\xa1 melhorar claramente o tempo computacional e a precis\xc3\xa3o, mas mesmo um conceito incorreto dar\xc3\xa1 o algoritmo de uma base a partir da qual a trabalhar e melhorar a precis\xc3\xa3o e o tempo."