Programação indutiva

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

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

Dependendo da linguagem de programação utilizada, existem vários tipos de programação indutiva. A programação funcional indutiva , que usa linguagens de programação funcionais, 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 o aprendizado 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 de uma solução ou outros vieses.

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

Em muitas aplicações, o programa de saída deve estar correto em 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 do programa , [1] [2] geralmente oposta à 'dedutiva' síntese do programa, [3] [4] [5] onde a especificação é geralmente completa.

Em outros casos, a programação indutiva é vista como uma área mais geral onde qualquer linguagem de programação ou representação declarativa pode ser utilizada e podemos até ter algum grau de erro nos exemplos, como no aprendizado de máquina geral , a área mais específica de mineração de estrutura ou a área de inteligência artificial simbólica . Uma característica distintiva é o número de exemplos ou especificação parcial necessária. 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 usadas: além da programação lógica e da programação funcional, outros paradigmas de programação e linguagens de representação têm sido usados ​​ou sugeridos na programação indutiva, como programação lógica funcional , programação de restrições , probabilística programação , programação lógica abdutiva , lógica modal , linguagens de ação, linguagens de 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 da década de 1970 e foi trazida para bases teóricas firmes com o seminal sistema THESIS de Summers [6] e o trabalho de Biermann. [7] Essas abordagens foram divididas em duas fases: primeiro, exemplos de entrada-saída são transformados em programas não recursivos (traços) usando um pequeno conjunto de operadores básicos; segundo, as regularidades nos traços são procuradas e usadas para dobrá-los em um programa recursivo. Os principais resultados até meados da década de 1980 são levantados por Smith. [8] Devido ao progresso limitado em relação à gama de programas que podem 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 80, especialmente devido ao sistema MIS de Shapiro [9] que acabou gerando o novo campo da programação lógica indutiva (ILP). [10] Os primeiros trabalhos de Plotkin, [11] [12] e sua " generalização relativamente menos geral (rlgg)", teve um enorme impacto na programação lógica indutiva. A maior parte do trabalho ILP aborda uma classe mais ampla de problemas, pois o foco não é apenas em programas de lógica recursiva, mas no aprendizado de máquina de hipóteses simbólicas a partir de representações lógicas. No entanto, houve alguns resultados encorajadores no aprendizado de programas recursivos em Prolog, como quicksort, a partir de exemplos, juntamente com conhecimento prévio adequado, por exemplo, com GOLEM . [16] com ILP cada vez menos focando em programas recursivos e inclinando-se cada vez mais para uma configuração de aprendizado de máquina com aplicações em mineração de dados relacionale descoberta do conhecimento. [17]

Em paralelo ao trabalho em ILP, Koza [18] propôs a programação genética no início da década de 1990 como uma abordagem baseada em gerar e testar para programas de aprendizado. A ideia de programação genética foi desenvolvida no sistema de programação indutiva ADATE [19] e no sistema baseado em busca sistemática MagicHaskeller. [20] 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 (fitness) que especifica o comportamento desejado de entrada/saída do programa a ser aprendido.

Os primeiros trabalhos em indução gramatical (também conhecido como inferência gramatical) estão relacionados à programação indutiva, pois sistemas de reescrita ou programas lógicos podem ser usados ​​para representar regras de produção. De fato, os primeiros trabalhos em inferência indutiva consideravam a indução gramatical e a inferência do programa Lisp como basicamente o mesmo problema. [21] Os resultados em termos de aprendizagem foram relacionados a conceitos clássicos, como identificação-no-limite, introduzidos na obra seminal de Gold. [22] Mais recentemente, o problema de aprendizagem de linguagens foi abordado pela comunidade de programação indutiva. [23] [24]

Nos últimos anos, as abordagens clássicas foram retomadas e avançadas com grande sucesso. Portanto, o problema de síntese foi reformulado no contexto de sistemas de reescrita de termos baseados em construtores, levando em consideração técnicas modernas de programação funcional, bem como o uso moderado de estratégias baseadas em busca e uso de conhecimento de fundo, bem como a invenção automática de subprogramas. Muitas aplicações novas e bem-sucedidas surgiram recentemente além da síntese de programas, principalmente na área de manipulação de dados, programação por exemplo e modelagem cognitiva (veja abaixo).

Outras ideias também têm sido exploradas com a característica comum de usar linguagens declarativas para a representação de hipóteses. Por exemplo, o uso de recursos, esquemas ou distâncias estruturadas de ordem superior tem sido defendido para um melhor manuseio de tipos e estruturas de dados recursivos; [25] [26] [27] a abstração também tem sido explorada como uma abordagem mais poderosa para o aprendizado cumulativo e a invenção de funções. [28] [29]

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 lógica bayesiana). [30] [31] [32] [33]

Á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 "a aprendizagem de programas ou regras recursivas são necessárias, [...] primeiro no domínio da engenharia de software onde a aprendizagem estrutural, assistentes de software e agentes de software podem ajudar a aliviar programadores de tarefas rotineiras, dar suporte de programação para usuários finais ou suporte de programadores novatos e sistemas tutores de programação. conceitos em web-mining 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 programação indutiva, como programação de usuário final , [34] as áreas relacionadas de programação por exemplo [35] e programação por demonstração , [36] e tutoria inteligente sistemas .

Outras áreas onde a inferência indutiva foi aplicada recentemente são aquisição de conhecimento , [37] inteligência artificial geral , [38] aprendizado por reforço e avaliação de teoria, [39] [40] e ciência cognitiva em geral. [41] [33] Também pode haver aplicações potenciais em agentes inteligentes, jogos, robótica, personalização, inteligência ambiental e interfaces humanas.

Veja também

Referências

  1. ^ Biermann, AW (1992). Shapiro, SC (ed.). "Programação automática". Enciclopédia de Inteligência Artificial : 18-35.
  2. ^ Rico, C.; Waters, RC (1993). Yovits, MC (ed.). Abordagens à programação automática (PDF) . Avanços em Computadores . Vol. 37. pp. 1–57. doi : 10.1016/S0065-2458(08)60402-7 . ISBN  9780120121373.
  3. ^ Lowry, ML; McCarthy, RD, eds. (1991). Projeto de software automático .
  4. ^ Maná, Z.; Waldinger, R. (1992). "Fundamentos da síntese de programa dedutivo". IEEE Trans Softw Eng . 18 (8): 674–704. CiteSeerX 10.1.1.51.817 . doi : 10.1109/32.153379 . 
  5. ^ Flener, P. (2002). "Conquistas e perspectivas de síntese do programa". Em Kakas, A.; Sadri, F. (eds.). Lógica Computacional: Programação Lógica e Além . Lógica Computacional: Programação Lógica e Além; Ensaios em homenagem a Robert A. Kowalski . Notas de aula em Ciência da Computação. Vol. LNAI 2407. pp. 310–346. doi : 10.1007/3-540-45628-7_13 . ISBN 978-3-540-43959-2.
  6. ^ Summers, PD (1977). "Uma metodologia para construção de programas LISP a partir de exemplos". J ACM . 24 (1): 161–175. doi : 10.1145/321992.322002 . S2CID 7474210 . 
  7. ^ Biermann, AW (1978). "A inferência de programas LISP regulares a partir de exemplos". IEEE Trans Syst Man Cybern . 8 (8): 585-600. doi : 10.1109/tsmc.1978.4310035 . S2CID 15277948 . 
  8. ^ Smith, DR (1984). Biermann, AW; Guiho, G. (eds.). "A síntese de programas LISP a partir de exemplos: uma pesquisa" . Técnicas de construção automática de programas : 307–324.
  9. ^ Shapiro, EY (1983). Depuração de programa algorítmico . A Imprensa do MIT.
  10. ^ Muggleton, S. (1991). "Programação lógica indutiva". Computação de Nova Geração . 8 (4): 295–318. CiteSeerX 10.1.1.329.5312 . doi : 10.1007/BF03037089 . S2CID 5462416 .  
  11. ^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "Uma nota sobre generalização indutiva" (PDF) . Inteligência de Máquina . 5 : 153-163.
  12. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "Uma nota adicional sobre generalização indutiva". Inteligência de Máquina . 6 : 101-124.
  13. ^ Muggleton, SH; Feng, C. (1990). "Indução eficiente de programas lógicos". Anais do Workshop sobre Teoria da Aprendizagem Algorítmica . 6 : 368-381. S2CID 14992676 . 
  14. ^ Quinlan, JR; Cameron-Jones, RM (1993). "Evitando armadilhas ao aprender teorias recursivas". IJCAI : 1050-1057. S2CID 11138624 . 
  15. ^ Quinlan, JR; Cameron-Jones, RM (1995). "Indução de programas lógicos: FOIL e sistemas relacionados" (PDF) . 13 (3-4). Springer: 287-312. {{cite journal}}: Cite journal requires |journal= (help)
  16. ^ Flener, P.; Yilmaz, S. (1999). "Síntese indutiva de programas de lógica recursiva: realizações e perspectivas". O Jornal de Programação Lógica . 41 (2): 141–195. doi : 10.1016/s0743-1066(99)00028-x .
  17. ^ Džeroski, Sašo (1996), "Programação Lógica Indutiva e Descoberta de Conhecimento em Bancos de Dados", em Fayyad, UM; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.), Avanços na Descoberta de Conhecimento e Mineração de Dados , MIT Press, pp. 117–152
  18. ^ Koza, JR (1992). Programação Genética: vol. 1, Sobre a programação de computadores por meio de seleção natural . Imprensa do MIT. ISBN  9780262111706.
  19. ^ Olsson, JR (1995). "Programação funcional indutiva usando transformação de programa incremental" . Inteligência Artificial . 74 (1): 55–83. doi : 10.1016/0004-3702(94)00042-y .
  20. ^ Katayama, Susumu (2008). "Geração exaustiva eficiente de programas funcionais usando pesquisa Monte-Carlo com aprofundamento iterativo" (PDF) . PRICAI 2008: Tendências em Inteligência Artificial . Notas de aula em Ciência da Computação. Vol. 5351. pp. 199–210. CiteSeerX 10.1.1.606.1447 . doi : 10.1007/978-3-540-89197-0_21 . ISBN   978-3-540-89196-3. {{cite book}}: ausente ou vazio |title=( ajuda )
  21. ^ Angluin, D.; CH, Smith (1983). "Inferência indutiva: Teoria e métodos". Pesquisas de Computação ACM . 15 (3): 237–269. doi : 10.1145/356914.356918 . S2CID 3209224 .  
  22. ^ Ouro, EM (1967). "Identificação da linguagem no limite" . Informação e Controle . 10 (5): 447–474. doi : 10.1016/s0019-9958(67)91165-5 .
  23. ^ Muggleton, Stephen (1999). "Programação em Lógica Indutiva: Problemas, Resultados e o Desafio de Aprender Linguagem em Lógica" . Inteligência Artificial . 114 (1–2): 283–296. doi : 10.1016/s0004-3702(99)00067-3 .; aqui: Seção 2.1
  24. ^ Olsson, JR; Poderes, DMW (2003). "Aprendizado de máquina da linguagem humana através de programação automática". Anais da Conferência Internacional sobre Ciência Cognitiva : 507-512.
  25. ^ Lloyd, JW (2001). "Representação de Conhecimento, Computação e Aprendizagem em Lógica de Ordem Superior" (PDF) . {{cite journal}}: Cite journal requires |journal= (help)
  26. ^ Lloyd, JW (2003). Lógica para aprender: aprendendo teorias compreensíveis a partir de dados estruturados . Springer. ISBN  9783662084069.
  27. ^ Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramírez-Quintana, MJ (2014). "Preenchendo a lacuna entre distância e generalização". Inteligência Computacional . 30 (3): 473-513. doi : 10.1111/moeda.12004 . S2CID 7255690 .  
  28. ^ Henderson, RJ; Muggleton, SH (2012). "Invenção automática de abstrações funcionais" (PDF) . Avanços na Programação em Lógica Indutiva .
  29. ^ Irvin, H.; Stuhlmuller, A.; Goodman, ND (2011). "Induzindo programas probabilísticos por fusão de programas Bayesiana". arXiv : 1110.5667 [ cs.AI ].
  30. ^ Muggleton, S. (2000). "Aprendendo programas de lógica estocástica" (PDF) . Elétron. Trans. Artif. Intel . 4(B) : 141-153.
  31. ^ De Raedt, L.; Kersting, K. (2008). Programação lógica indutiva probabilística . Springer.
  32. ^ Irvin, H.; Stuhlmuller, A.; Goodman, ND (2011). "Induzindo programas probabilísticos por fusão de programas Bayesiana". arXiv : 1110.5667 [ cs.AI ].
  33. ^ a b Stuhlmuller, A.; Goodman, ND (2012). "Raciocinando sobre o raciocínio por condicionamento aninhado: Modelagem da teoria da mente com programas probabilísticos". Pesquisa de Sistemas Cognitivos . 28 : 80-99. doi : 10.1016/j.cogsys.2013.07.003 . S2CID 7602205 .  
  34. ^ Lieberman, H.; Paterno, F.; Wulf, V. (2006). Desenvolvimento do usuário final . Springer.
  35. ^ Lieberman, H. (2001). Seu desejo é meu comando: Programando por exemplo . Morgan Kaufmann. ISBN  9781558606883.
  36. ^ Cypher, E.; Halbert, DC (1993). Veja o que eu faço: programação por demonstração . ISBN  9780262032131.
  37. ^ Schmid, U.; Hofmann, M.; Kitzelmann, E. (2009). "Programação indutiva analítica como um dispositivo de aquisição de regras cognitivas" (PDF) . Anais da Segunda Conferência sobre Inteligência Artificial Geral : 162-167.
  38. ^ Crossley, N.; Kitzelmann, E.; Hofmann, M.; Schmid, U. (2009). "Combinando programação indutiva analítica e evolutiva" (PDF) . Anais da Segunda Conferência sobre Inteligência Artificial Geral : 19-24.
  39. ^ Hernandez-Orallo, J. (2000). "Aprendizagem por reforço construtivo". Revista Internacional de Sistemas Inteligentes . 15 (3): 241–264. CiteSeerX 10.1.1.34.8877 . doi : 10.1002/(sici)1098-111x(200003)15:3<241::aid-int6>3.0.co;2-z . S2CID 123390956 .   
  40. ^ Kemp, C.; Goodman, N.; Tenenbaum, JB (2007). "Aprendendo e usando teorias relacionais" (PDF) . Avanços em Sistemas de Processamento de Informação Neural : 753–760.
  41. ^ Schmid, U.; Kitzelmann, E. (2011). "Aprendizagem de regras indutivas no nível do conhecimento". Pesquisa de Sistemas Cognitivos . 12 (3): 237–248. doi : 10.1016/j.cogsys.2010.12.002 . S2CID 18613664 .  

Leitura adicional

Links externos