Programação indutiva - Inductive programming

Paradigmas de programação

A programação indutiva ( IP ) é uma área especial da programação automática , cobrindo pesquisa de inteligência artificial e programação , que aborda a aprendizagem de programas tipicamente declarativos ( lógicos ou funcionais ) e frequentemente recursivos a partir de especificações incompletas, como exemplos de entrada / saída ou restrições.

Dependendo da linguagem de programação usada, existem vários tipos de programação indutiva. A programação funcional indutiva , que usa linguagens de programação funcional, como Lisp ou Haskell , e mais especialmente a programação lógica indutiva , que usa linguagens de programação lógica como Prolog e outras representações lógicas, como lógicas de descrição , têm sido mais proeminentes, mas outras linguagens (de programação) paradigmas também têm sido usados, como programação de restrição ou programação probabilística .

Definição

A programação indutiva incorpora todas as abordagens que se preocupam com a aprendizagem de programas ou algoritmos a partir de especificações incompletas ( formais ). As entradas possíveis em um sistema IP são um conjunto de entradas de treinamento e saídas correspondentes ou uma função de avaliação de saída, descrevendo o comportamento desejado do programa pretendido, traços ou sequências de ação que descrevem o processo de cálculo de saídas específicas, restrições para o programa a ser induzido em relação à sua eficiência de tempo ou sua complexidade, vários tipos de conhecimento de fundo, como tipos de dados padrão , funções predefinidas a serem usadas, esquemas de programa ou modelos que descrevem o fluxo de dados do programa pretendido, heurísticas para orientar a busca por uma solução ou outros vieses.

A saída de um sistema IP é um programa em alguma linguagem de programação arbitrária contendo estruturas de controle condicionais e loop ou recursivas, ou qualquer outro tipo de linguagem de representação completa de Turing .

Em muitas aplicações, o programa de saída deve estar correto com relação aos exemplos e especificações parciais, e isso leva à consideração da programação indutiva como uma área especial dentro da programação automática ou síntese de programa , geralmente oposta à síntese de programa 'dedutiva', onde a especificação geralmente está completo.

Em outros casos, a programação indutiva é vista como uma área mais geral onde qualquer programação declarativa ou linguagem de representação pode ser usada e podemos até ter algum grau de erro nos exemplos, como no aprendizado de máquina em geral , a área mais específica de mineração de estrutura ou a área da inteligência artificial simbólica . Uma característica distintiva é o número de exemplos ou especificações parciais necessárias. Normalmente, as técnicas de programação indutiva podem aprender com apenas alguns exemplos.

A diversidade da programação indutiva geralmente vem das aplicações e das linguagens que são utilizadas: além da programação lógica e da programação funcional, outros paradigmas de programação e linguagens de representação foram usados ​​ou sugeridos na programação indutiva, como programação lógica funcional , programação de restrição , probabilística programação , programação abductive lógica , a lógica modal , línguas ação , línguas agente e muitos tipos de linguagens imperativas .

História

A pesquisa sobre a síntese indutiva de programas funcionais recursivos começou no início dos anos 1970 e foi trazida para bases teóricas firmes com o sistema seminal TESE de Summers e o trabalho de Biermann. Essas abordagens foram divididas em duas fases: primeiro, os exemplos de entrada-saída são transformados em programas não recursivos (rastreios) usando um pequeno conjunto de operadores básicos; segundo, regularidades nos traços são pesquisadas e usadas para dobrá-los em um programa recursivo. Os principais resultados até meados da década de 1980 são levantados por Smith. Devido ao progresso limitado com respeito à gama de programas que poderiam ser sintetizados, as atividades de pesquisa diminuíram significativamente na próxima década.

O advento da programação lógica trouxe um novo élan, mas também uma nova direção no início dos anos 1980, especialmente devido ao sistema MIS de Shapiro que acabou gerando o novo campo da programação lógica indutiva (ILP). Os primeiros trabalhos de Plotkin, e sua " relativa menor generalização geral (rlgg) ", tiveram um enorme impacto na programação lógica indutiva. A maior parte do trabalho de ILP aborda uma classe mais ampla de problemas, já que o foco não está apenas em programas lógicos recursivos, mas no aprendizado de máquina de hipóteses simbólicas a partir de representações lógicas. No entanto, houve alguns resultados encorajadores na aprendizagem de programas Prolog recursivos, como quicksort a partir de exemplos juntamente com o conhecimento de fundo adequado, por exemplo, com GOLEM. Mas, novamente, após o sucesso inicial, a comunidade ficou desapontada com o progresso limitado sobre a indução de programas recursivos com ILP focando cada vez menos em programas recursivos e se inclinando cada vez mais para uma configuração de aprendizado de máquina com aplicativos em mineração de dados relacional e descoberta de conhecimento.

Paralelamente ao trabalho em ILP, Koza propôs a programação genética no início de 1990 como uma abordagem baseada em geração e teste para programas de aprendizagem. A ideia de programação genética foi desenvolvida no sistema de programação indutiva ADATE e no sistema baseado em busca sistemática MagicHaskeller. Aqui, novamente, os programas funcionais são aprendidos a partir de conjuntos de exemplos positivos, juntamente com uma função de avaliação de saída (adequação) que especifica o comportamento de entrada / saída desejado do programa a ser aprendido.

O trabalho inicial de indução gramatical (também conhecido como inferência gramatical) está relacionado à programação indutiva, uma vez que sistemas de reescrita ou programas lógicos podem ser usados ​​para representar regras de produção. Na verdade, os primeiros trabalhos em inferência indutiva consideraram a indução gramatical e a inferência de programa Lisp como basicamente o mesmo problema. Os resultados em termos de aprendizagem foram relacionados a conceitos clássicos, como a identificação no limite, introduzidos na obra seminal de Gold. Mais recentemente, o problema de aprendizagem de línguas foi abordado pela comunidade de programação indutiva.

Nos últimos anos, as abordagens clássicas foram retomadas e desenvolvidas com grande sucesso. Portanto, o problema de síntese foi reformulado com base em sistemas de reescrita de termos baseados em construtor, levando em consideração técnicas modernas de programação funcional, bem como uso moderado de estratégias baseadas em pesquisa e uso de conhecimento prévio, bem como invenção automática de subprogramas. Muitos aplicativos novos e bem-sucedidos surgiram recentemente além da síntese de programas, mais especialmente na área de manipulação de dados, programação por exemplo e modelagem cognitiva (veja abaixo).

Outras ideias também foram exploradas com a característica comum de usar linguagens declarativas para a representação de hipóteses. Por exemplo, o uso de recursos de ordem superior, esquemas ou distâncias estruturadas têm sido defendidos para um melhor tratamento de tipos e estruturas de dados recursivos ; abstração também foi explorada como uma abordagem mais poderosa para aprendizagem cumulativa e invenção de função.

Um paradigma poderoso que tem sido usado recentemente para a representação de hipóteses em programação indutiva (geralmente na forma de modelos generativos ) é a programação probabilística (e paradigmas relacionados, como programas de lógica estocástica e programação de lógica Bayesiana).

Áreas de aplicação

O primeiro workshop sobre Abordagens e Aplicações de Programação Indutiva (AAIP) realizado em conjunto com ICML 2005 identificou todas as aplicações onde "aprendizagem de programas ou regras recursivas são necessárias, [...] primeiro no domínio da engenharia de software onde aprendizagem estrutural, assistentes de software e agentes de software podem ajudar a aliviar os programadores de tarefas rotineiras, fornecer suporte de programação para usuários finais ou suporte de programadores novatos e sistemas de tutor de programação. Outras áreas de aplicação são aprendizagem de linguagem, aprendizado de regras de controle recursivo para planejamento de IA, aprendizado recursivo conceitos em mineração na web ou para transformações de formato de dados ".

Desde então, essas e muitas outras áreas têm se mostrado nichos de aplicação bem-sucedidos para a programação indutiva, como a programação do usuário final , as áreas relacionadas de programação por exemplo e programação por demonstração e sistemas de tutoria inteligentes .

Outras áreas onde a inferência indutiva foi aplicada recentemente são a aquisição de conhecimento , inteligência geral artificial , aprendizagem por reforço e avaliação de teoria e ciências cognitivas em geral. Também pode haver aplicações prospectivas em agentes inteligentes, jogos, robótica, personalização, inteligência ambiental e interfaces humanas.

Veja também

Referências

Leitura adicional

links externos