Hispanopedia Wiki
Articulo de referencia

Programación inductiva

La programación inductiva ( PI ) es un área especial de la programación automática , que abarca la investigación en inteligencia artificial y programación , y que aborda el apre...

Hispanopedia WikiContenido en espanolLectura gratuita

La programación inductiva ( PI ) es un área especial de la programación automática , que abarca la investigación en inteligencia artificial y programación , y que aborda el aprendizaje de programas típicamente declarativos ( lógicos o funcionales ) y a menudo recursivos a partir de especificaciones incompletas, como ejemplos de entrada/salida o restricciones.

Dependiendo del lenguaje de programación utilizado, existen varios tipos de programación inductiva. La programación funcional inductiva , que utiliza lenguajes de programación funcional como Lisp o Haskell , y sobre todo la programación lógica inductiva , que utiliza lenguajes de programación lógica como Prolog y otras representaciones lógicas como las lógicas descriptivas , han sido las más destacadas, pero también se han utilizado otros paradigmas de lenguajes (de programación), como la programación con restricciones o la programación probabilística .

Definición

La programación inductiva abarca todos los enfoques relacionados con el aprendizaje de programas o algoritmos a partir de especificaciones incompletas ( formales ). Las posibles entradas en un sistema de programación inductiva son un conjunto de entradas de entrenamiento y sus correspondientes salidas o una función de evaluación de salida que describe el comportamiento deseado del programa, trazas o secuencias de acciones que describen el proceso de cálculo de salidas específicas, restricciones para el programa a inducir en cuanto a su eficiencia temporal o su complejidad, diversos tipos de conocimiento previo, como tipos de datos estándar , funciones predefinidas a utilizar, esquemas o plantillas de programa que describen el flujo de datos del programa previsto, heurísticas para guiar la búsqueda de una solución u otros sesgos.

La salida de un sistema IP es un programa en algún lenguaje de programación arbitrario que contiene condicionales y estructuras de control de bucle o recursivas, o cualquier otro tipo de lenguaje de representación Turing-completo .

En muchas aplicaciones, el programa de salida debe ser correcto con respecto a los ejemplos y la especificación parcial, y esto lleva a considerar la programación inductiva como un área especial dentro de la programación automática o síntesis de programas , [ 1 ] [ 2 ] generalmente opuesta a la síntesis de programas 'deductiva', [ 3 ] [ 4 ] [ 5 ] donde la especificación suele ser completa.

En otros casos, la programación inductiva se considera un área más general donde se puede utilizar cualquier lenguaje de programación declarativa o de representación, e incluso puede haber cierto grado de error en los ejemplos, como en el aprendizaje automático en general , el área más específica de la minería de estructuras o el área de la inteligencia artificial simbólica . Una característica distintiva es la cantidad de ejemplos o especificaciones parciales necesarias. Por lo general, las técnicas de programación inductiva pueden aprender con solo unos pocos ejemplos.

La diversidad de la programación inductiva suele provenir de las aplicaciones y los lenguajes que se utilizan: además de la programación lógica y la programación funcional, se han utilizado o sugerido otros paradigmas de programación y lenguajes de representación en la programación inductiva, como la programación lógica funcional , la programación con restricciones , la programación probabilística , la programación lógica abductiva , la lógica modal , los lenguajes de acción , los lenguajes de agente y muchos tipos de lenguajes imperativos .

Historia

Los primeros trabajos de Plotkin, [ 6 ] [ 7 ] y su " generalización relativa menos general (rlgg) ", tuvieron un enorme impacto en la programación lógica inductiva . Hubo algunos resultados alentadores en el aprendizaje de programas recursivos de Prolog, como quicksort, a partir de ejemplos junto con el conocimiento previo adecuado, por ejemplo con GOLEM. [ 8 ] Sin embargo, después del éxito inicial, la comunidad se sintió decepcionada por el progreso limitado en la inducción de programas recursivos [ 9 ] [ 10 ] [ 11 ], con la PLI cada vez menos enfocada en programas recursivos y más inclinada hacia un entorno de aprendizaje automático con aplicaciones en minería de datos relacionales y descubrimiento de conocimiento. [ 12 ]

Paralelamente a su trabajo en PLI, Koza [ 13 ] propuso la programación genética a principios de la década de 1990 como un enfoque de aprendizaje de programas basado en la generación y prueba. La idea de la programación genética se desarrolló posteriormente en el sistema de programación inductiva ADATE [ 14 ] y en el sistema de búsqueda sistemática MagicHaskeller [ 15 ] . En estos casos, los programas funcionales se aprenden a partir de conjuntos de ejemplos positivos junto con una función de evaluación de salida (aptitud) que especifica el comportamiento de entrada/salida deseado del programa a aprender.

Los primeros trabajos en inducción gramatical (también conocida como inferencia gramatical) están relacionados con la programación inductiva, ya que los sistemas de reescritura o los programas lógicos pueden utilizarse para representar reglas de producción. De hecho, los primeros trabajos en inferencia inductiva consideraban la inducción gramatical y la inferencia de programas Lisp como básicamente el mismo problema. [ 16 ] Los resultados en términos de aprendibilidad estaban relacionados con conceptos clásicos, como la identificación en el límite, introducida en el trabajo fundamental de Gold. [ 17 ] Más recientemente, la comunidad de programación inductiva abordó el problema del aprendizaje de lenguajes. [ 18 ] [ 19 ]

En los últimos años, los enfoques clásicos se han retomado y perfeccionado con gran éxito. Por lo tanto, el problema de la síntesis se ha reformulado en el contexto de los sistemas de reescritura de términos basados ​​en constructores, teniendo en cuenta las técnicas modernas de programación funcional, así como el uso moderado de estrategias de búsqueda y el aprovechamiento del conocimiento previo, además de la invención automática de subprogramas. Recientemente han surgido numerosas aplicaciones nuevas y exitosas más allá de la síntesis de programas, especialmente en el ámbito de la manipulación de datos, la programación por ejemplos y el modelado cognitivo (véase más adelante).

También se han explorado otras ideas con la característica común de utilizar lenguajes declarativos para la representación de hipótesis. Por ejemplo, se ha defendido el uso de características de orden superior, esquemas o distancias estructuradas para un mejor manejo de tipos y estructuras de datos recursivos ; [ 20 ] [ 21 ] [ 22 ] la abstracción también se ha explorado como un enfoque más potente para el aprendizaje acumulativo y la invención de funciones. [ 23 ] [ 24 ]

Un paradigma poderoso que se ha utilizado recientemente para la representación de hipótesis en programación inductiva (generalmente en forma de modelos generativos ) es la programación probabilística (y paradigmas relacionados, como los programas de lógica estocástica y la programación lógica bayesiana). [ 25 ] [ 26 ] [ 24 ] [ 27 ]

Áreas de aplicación

El primer taller sobre Enfoques y Aplicaciones de la Programación Inductiva (AAIP), archivado el 3 de marzo de 2016 en la Wayback Machine y celebrado junto con ICML 2005, identificó todas las aplicaciones en las que se requiere el aprendizaje de programas o reglas recursivas, [...] en primer lugar, en el ámbito de la ingeniería de software, donde el aprendizaje estructural, los asistentes de software y los agentes de software pueden ayudar a liberar a los programadores de tareas rutinarias, proporcionar soporte de programación a los usuarios finales o brindar apoyo a programadores novatos y sistemas de tutoría de programación. Otras áreas de aplicación son el aprendizaje de lenguajes, el aprendizaje de reglas de control recursivas para la planificación de IA, el aprendizaje de conceptos recursivos en la minería web o para transformaciones de formatos de datos.

Desde entonces, estas y muchas otras áreas han demostrado ser nichos de aplicación exitosos para la programación inductiva, como la programación para usuarios finales , [ 28 ] las áreas relacionadas de programación por ejemplo [ 29 ] y programación por demostración , [ 30 ] y sistemas de tutoría inteligentes .

Otras áreas donde se ha aplicado recientemente la inferencia inductiva son la adquisición de conocimiento , [ 31 ] la inteligencia artificial general , [ 32 ] el aprendizaje por refuerzo y la evaluación de teorías, [ 33 ] [ 34 ] y la ciencia cognitiva en general. [ 35 ] [ 27 ] También puede haber aplicaciones potenciales en agentes inteligentes, juegos, robótica, personalización, inteligencia ambiental e interfaces humanas.

Véase también

Referencias

  1. ↑ Biermann, AW (1992). Shapiro, SC (ed.). "Programación automática". Enciclopedia de Inteligencia Artificial : 18–35 .
  2. ↑ Rich, C.; Waters, RC (1993). Yovits, MC (ed.). Enfoques para la programación automática (PDF) . Advances in Computers. Vol. 37. pp. 1–57 . doi : 10.1016/S0065-2458(08)60402-7 . ISBN   9780120121373.
  3. ↑ Lowry, ML; McCarthy, RD, eds. (1991). Diseño automático de software .
  4. ^ Maná, Z.; Waldinger, R. (1992). "Fundamentos de síntesis de programas deductivos". IEEE Trans Softw Eng . 18 (8): 674– 704. CiteSeerX 10.1.1.51.817 . doi : 10.1109/32.153379 . 
  5. ↑ Flener, P. (2002). «Logros y perspectivas de la síntesis de programas». En Kakas, A.; Sadri, F. (eds.). Lógica computacional: programación lógica y más allá; ensayos en honor a Robert A. Kowalski . Lecture Notes in Computer Science. Vol. LNAI 2407. pp. 310–346 . doi : 10.1007/3-540-45628-7_13 . ISBN   978-3-540-43959-2.
  6. ↑ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "Una nota sobre la generalización inductiva" (PDF) . Machine Intelligence . 5 : 153–163 .
  7. ↑ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "Una nota adicional sobre la generalización inductiva". Machine Intelligence . 6 : 101–124 .
  8. ↑ Muggleton, SH; Feng, C. (1990). "Inducción eficiente de programas lógicos". Actas del Taller sobre Teoría del Aprendizaje Algorítmico . 6 : 368–381 . S2CID 14992676 . 
  9. ↑ Quinlan, JR; Cameron-Jones, RM (1993). "Evitando trampas al aprender teorías recursivas". IJCAI : 1050–1057 . S2CID 11138624 . 
  10. ↑ Quinlan, JR; Cameron-Jones, RM (1995). "Inducción de programas lógicos: FOIL y sistemas relacionados" (PDF) . 13 ( 3–4 ). Springer: 287–312 . Archivado del original (PDF) el 7 de septiembre de 2017. Recuperado el 7 de septiembre de 2017 .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  11. ↑ Flener, P.; Yilmaz, S. (1999). "Síntesis inductiva de programas lógicos recursivos: logros y perspectivas" . The Journal of Logic Programming . 41 (2): 141– 195. doi : 10.1016/s0743-1066(99)00028-x .
  12. ↑ Džeroski, Sašo (1996), "Programación lógica inductiva y descubrimiento de conocimiento en bases de datos", en Fayyad, UM; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.), Avances en el descubrimiento de conocimiento y la minería de datos , MIT Press, pp. 117–152 
  13. ↑ Koza, JR (1992). Programación genética: vol. 1, Sobre la programación de computadoras mediante selección natural . MIT Press. ISBN 9780262111706.
  14. ↑ Olsson, JR (1995). "Programación funcional inductiva mediante transformación incremental de programas" . Inteligencia Artificial . 74 (1): 55– 83. doi : 10.1016/0004-3702(94)00042-y .
  15. ↑ Katayama, Susumu (2008). "Generación exhaustiva y eficiente de programas funcionales mediante búsqueda de Montecarlo con profundización iterativa" (PDF) . PRICAI 2008: Tendencias en inteligencia artificial . Lecture Notes in Computer Science. 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.
  16. ↑ Angluin, D.; CH, Smith (1983). "Inferencia inductiva: Teoría y métodos". ACM Computing Surveys . 15 (3): 237– 269. doi : 10.1145/356914.356918 . S2CID 3209224 . 
  17. ↑ Gold, EM (1967). "Identificación de idiomas en el límite" . Information and Control . 10 (5): 447– 474. doi : 10.1016/s0019-9958(67)91165-5 .
  18. ↑ Muggleton, Stephen (1999). "Programación lógica inductiva: problemas, resultados y el desafío de aprender el lenguaje en lógica" . Inteligencia artificial . 114 ( 1–2 ): 283–296 . doi : 10.1016/s0004-3702(99)00067-3 .; aquí: Sec.2.1
  19. ↑ Olsson, JR; Powers, DMW (2003). "Aprendizaje automático del lenguaje humano mediante programación automática". Actas de la Conferencia Internacional sobre Ciencias Cognitivas : 507–512 .
  20. ↑ Lloyd, JW (2001). "Representación del conocimiento, computación y aprendizaje en lógica de orden superior" (PDF) .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  21. ↑ Lloyd, JW (2003). Lógica para el aprendizaje: aprendizaje de teorías comprensibles a partir de datos estructurados . Springer. ISBN 9783662084069.
  22. ↑ Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramirez-Quintana, MJ (2014). "Acortando la brecha entre distancia y generalización" . Inteligencia Computacional . 30 (3): 473– 513. doi : 10.1111/coin.12004 . hdl : 10251/34946 . S2CID 7255690 . 
  23. ↑ Henderson, RJ; Muggleton, SH (2012). "Invención automática de abstracciones funcionales" (PDF) . Avances en programación lógica inductiva .
  24. 1 2 Irvin, H.; Stuhlmuller, A.; Goodman, ND (2011). "Inducción de programas probabilísticos mediante la fusión de programas bayesianos". arXiv : 1110.5667 [ cs.AI ].
  25. ↑ Muggleton, S. (2000). "Aprendizaje de programas de lógica estocástica" (PDF) . Electron. Trans. Artif. Intell . 4(B) : 141–153 . Archivado del original (PDF) el 7 de septiembre de 2017. Consultado el 7 de septiembre de 2017 .
  26. ↑ De Raedt, L.; Kersting, K. (2008). Programación lógica inductiva probabilística . Springer.
  27. 1 2 Stuhlmuller, A.; Goodman, ND (2012). "Razonamiento sobre el razonamiento mediante condicionamiento anidado: modelado de la teoría de la mente con programas probabilísticos". Cognitive Systems Research . 28 : 80–99 . doi : 10.1016/j.cogsys.2013.07.003 . S2CID 7602205 . 
  28. ↑ Lieberman, H.; Paternò, F.; Wulf, V. (2006). Desarrollo por parte del usuario final . Springer.
  29. ↑ Lieberman, H. (2001). Tu deseo es mi orden: Programación mediante ejemplos . Morgan Kaufmann. ISBN 9781558606883.
  30. ↑ Cypher, E.; Halbert, DC (1993). Watch what I do: programming by demonstration . MIT Press. ISBN 9780262032131.
  31. ↑ Schmid, U. ; Hofmann, M.; Kitzelmann, E. (2009). "Programación inductiva analítica como dispositivo de adquisición de reglas cognitivas" (PDF) . Actas de la Segunda Conferencia sobre Inteligencia Artificial General : 162–167 .
  32. ↑ Crossley, N.; Kitzelmann, E.; Hofmann, M.; Schmid, U. (2009). "Combinación de programación inductiva analítica y evolutiva" (PDF) . Actas de la Segunda Conferencia sobre Inteligencia Artificial General : 19–24 .
  33. ↑ Hernandez-Orallo, J. (2000). "Aprendizaje por refuerzo constructivo". International Journal of Intelligent Systems . 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 .  
  34. ↑ Kemp, C.; Goodman, N.; Tenenbaum, JB (2007). "Aprendizaje y uso de teorías relacionales" (PDF) . Avances en sistemas de procesamiento de información neuronal : 753–760 .
  35. ↑ Schmid, U. ; Kitzelmann, E. (2011). "Aprendizaje inductivo de reglas a nivel de conocimiento". Cognitive Systems Research . 12 (3): 237– 248. doi : 10.1016/j.cogsys.2010.12.002 . S2CID 18613664 . 

Lecturas adicionales

  • Flener, P.; Schmid, U. (2008). "Una introducción a la programación inductiva". Artificial Intelligence Review . 29 (1): 45– 62. doi : 10.1007/s10462-009-9108-7 . S2CID 26314997 . 
  • Kitzelmann, E. (2010). «Programación inductiva: una revisión de las técnicas de síntesis de programas» (PDF) . Enfoques y aplicaciones de la programación inductiva . Lecture Notes in Computer Science. Vol.  5812. pp. 50–73 . CiteSeerX 10.1.1.180.1237 . doi : 10.1007/978-3-642-11931-6_3 . ISBN   978-3-642-11930-9.
  • Partridge, D. (1997). "Argumentos a favor de la programación inductiva". Computer . 30 (1): 36– 41. doi : 10.1109/2.562924 . S2CID 206403583 . 
  • Flener, P.; Partridge, D. (2001). "Programación inductiva". Ingeniería de software automatizada . 8 (2): 131– 137. doi : 10.1023/a:1008797606116 . S2CID 6675212 . 
  • Hofmann, M.; Kitzelmann, E. (2009). "Un marco unificador para el análisis y la evaluación de sistemas de programación inductiva" . Actas de la Segunda Conferencia sobre Inteligencia Artificial General : 55–60 .
  • Muggleton, S.; De Raedt, L. (1994). "Programación lógica inductiva: teoría y métodos" . The Journal of Logic Programming . 19–20 : 629–679 . doi : 10.1016/0743-1066(94)90035-3 .
  • Lavrac, N.; Dzeroski, S. (1994). Programación lógica inductiva: técnicas y aplicaciones . Nueva York: Ellis Horwood. ISBN 978-0-13-457870-5.https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/
  • Muggleton, S.; De Raedt, Luc.; Poole, D.; Bratko, I.; Flach, P.; Inoue, K.; Srinivasan, A. (2012). "ILP cumple 20 años" . Machine Learning . 86 (1): 3– 23. doi : 10.1007/s10994-011-5259-2 .
  • Gulwani, S.; Hernández-Orallo, J.; Kitzelmann, E.; Muggleton, SH; Schmid, U .; Zorn, B. (2015). "La programación inductiva se encuentra con el mundo real" . Comunicaciones de la ACM . 58 (11): 90– 99. CiteSeerX 10.1.1.696.3800 . doi : 10.1145/2736282 . hdl : 10251/64984 . S2CID 425881 .  
  • Página de la comunidad de Programación Inductiva , alojada por la Universidad de Bamberg.
Lecturas relacionadas
6 articulos
Programación automáticaProgramación automáticaEn informática , la programación automática [1] es un tipo de programación informática en la que algún mecanismo genera un programa informático par...Inteligencia artificialInteligencia artificialLa inteligencia artificial ( IA ), en su sentido más amplio, es la inteligencia que exhiben las máquinas , en particular los sistemas informáticos ...Programación de computadorasProgramación de computadorasLa programación o codificación informática es la composición de secuencias de instrucciones, llamadas programas , que las computadoras pueden segui...Aprendizaje automáticoAprendizaje automáticoEl aprendizaje automático ( ML ) es un campo de estudio en inteligencia artificial que se ocupa del desarrollo y estudio de algoritmos estadísticos...Programación declarativaEn informática , la programación declarativa es un paradigma de programación (un estilo de construir la estructura y los elementos de los programas...Programación lógicaLa programación lógica es un paradigma de programación , base de datos y representación del conocimiento basado en la lógica formal . Un programa l...