stringtranslate.com

Programación inductiva

La programación inductiva ( PI ) es un área especial de la programación automática , que abarca la investigación de la inteligencia artificial y la programación , 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 más especialmente la programación lógica inductiva , que utiliza lenguajes de programación lógica como Prolog y otras representaciones lógicas como 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 incorpora todos los enfoques que se ocupan de aprender programas o algoritmos a partir de especificaciones incompletas ( formales ). Las posibles entradas en un sistema IP son un conjunto de entradas de entrenamiento y salidas correspondientes o una función de evaluación de salida, que describe el comportamiento deseado del programa previsto, rastros o secuencias de acción que describen el proceso de cálculo de salidas específicas, restricciones para el programa que se inducirá en relación con su eficiencia temporal o su complejidad, varios tipos de conocimiento previo como tipos de datos estándar , funciones predefinidas que se utilizarán, esquemas de programa o plantillas que describan 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 recursivas o de bucle, 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 representación o programación declarativa e incluso podemos tener algún grado de error en los ejemplos, como en el aprendizaje automático general , el área más específica de minería de estructuras o el área de inteligencia artificial simbólica . Una característica distintiva es la cantidad de ejemplos o especificación parcial necesaria. Por lo general, las técnicas de programación inductiva pueden aprender a partir de solo unos pocos ejemplos.

La diversidad de la programación inductiva generalmente proviene 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 por 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

La investigación sobre la síntesis inductiva de programas funcionales recursivos comenzó a principios de los años 1970 y alcanzó bases teóricas sólidas con el sistema seminal THESIS de Summers [6] y el trabajo de Biermann [7] . Estos enfoques se dividieron en dos fases: primero, los ejemplos de entrada-salida se transforman en programas no recursivos (trazas) utilizando un pequeño conjunto de operadores básicos; segundo, se buscan regularidades en las trazas y se utilizan para plegarlas en un programa recursivo. Los principales resultados hasta mediados de los años 1980 son examinados por Smith [8] . Debido al progreso limitado con respecto a la gama de programas que se podían sintetizar, las actividades de investigación disminuyeron significativamente en la década siguiente.

El advenimiento de la programación lógica trajo consigo un nuevo impulso pero también una nueva dirección a principios de los años 1980, especialmente debido al sistema MIS de Shapiro [9] que eventualmente generó el nuevo campo de la programación lógica inductiva (ILP). [10] Los primeros trabajos de Plotkin, [11] [12] y su " generalización relativa mínima general (rlgg) ", tuvieron un enorme impacto en la programación lógica inductiva. La mayor parte del trabajo de ILP aborda una clase más amplia de problemas, ya que el enfoque no solo está en programas lógicos recursivos sino en el aprendizaje automático de hipótesis simbólicas a partir de representaciones lógicas. Sin embargo, hubo algunos resultados alentadores en el aprendizaje de programas Prolog recursivos como quicksort a partir de ejemplos junto con el conocimiento previo adecuado, por ejemplo con GOLEM. [13] Pero nuevamente, después del éxito inicial, la comunidad se decepcionó por el progreso limitado sobre la inducción de programas recursivos [14] [15] [16] con ILP cada vez menos enfocándose en programas recursivos y inclinándose cada vez más hacia un entorno de aprendizaje automático con aplicaciones en minería de datos relacionales y descubrimiento de conocimiento. [17]

En paralelo al trabajo en ILP, Koza [18] propuso la programación genética a principios de los años 1990 como un enfoque basado en la generación y prueba de programas de aprendizaje. La idea de la programación genética se desarrolló aún más en el sistema de programación inductiva ADATE [19] y el sistema basado en búsqueda sistemática MagicHaskeller [20] . Aquí nuevamente, 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 que se va 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 se pueden utilizar sistemas de reescritura o programas lógicos para representar reglas de producción. De hecho, los primeros trabajos en inferencia inductiva consideraban que la inducción gramatical y la inferencia de programas Lisp eran básicamente el mismo problema. [21] Los resultados en términos de capacidad de aprendizaje se relacionaban con conceptos clásicos, como la identificación en el límite, tal como se introdujo en el trabajo seminal de Gold. [22] Más recientemente, la comunidad de programación inductiva abordó el problema del aprendizaje de idiomas. [23] [24]

En los últimos años, los enfoques clásicos se han retomado y avanzado con gran éxito. Por lo tanto, el problema de síntesis se ha reformulado sobre la base de 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 basadas en búsqueda y el uso de conocimientos previos, así como la invención automática de subprogramas. Recientemente han aparecido muchas aplicaciones nuevas y exitosas más allá de la síntesis de programas, especialmente en el área de manipulación de datos, programación por ejemplo y modelado cognitivo (ver más abajo).

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 estructuras y tipos de datos recursivos ; [25] [26] [27] también se ha explorado la abstracción como un enfoque más potente para el aprendizaje acumulativo y la invención de funciones. [28] [29]

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). [30] [31] [29] [32]

Áreas de aplicación

El primer taller sobre Enfoques y aplicaciones de la programación inductiva (AAIP, por sus siglas en inglés), celebrado en conjunto con ICML 2005, identificó todas las aplicaciones en las que "se requiere el aprendizaje de programas o reglas recursivas, [...] primero en el dominio de la ingeniería de software, donde el aprendizaje estructural, los asistentes de software y los agentes de software pueden ayudar a aliviar a los programadores de tareas rutinarias, brindar soporte de programación a los usuarios finales o brindar soporte a programadores novatos y sistemas de tutoría de programación. Otras áreas de aplicación son el aprendizaje de idiomas, el aprendizaje de reglas de control recursivas para la planificación de IA, el aprendizaje de conceptos recursivos en 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 del usuario final , [33] las áreas relacionadas de programación por ejemplo [34] y programación por demostración , [35] y sistemas de tutoría inteligente .

Otras áreas en las que se ha aplicado recientemente la inferencia inductiva son la adquisición de conocimiento , [36] la inteligencia artificial general , [37] el aprendizaje por refuerzo y la evaluación de teorías, [38] [39] y la ciencia cognitiva en general. [40] [32] También puede haber aplicaciones prospectivas 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 de la programación automática (PDF) . Avances en computadoras. Vol. 37. págs. 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 . Apuntes de clase en informática. Vol. LNAI 2407. págs. 310–346. doi :10.1007/3-540-45628-7_13. ISBN 978-3-540-43959-2.
  6. ^ Summers, PD (1977). "Una metodología para la construcción de programas LISP a partir de ejemplos". J ACM . 24 (1): 161–175. doi : 10.1145/321992.322002 . S2CID  7474210.
  7. ^ Biermann, AW (1978). "La inferencia de programas LISP regulares a partir de ejemplos". 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.). "La síntesis de programas LISP a partir de ejemplos: un estudio". Técnicas de construcción automática de programas : 307–324.
  9. ^ Shapiro, EY (1983). Depuración de programas algorítmicos . The MIT Press.
  10. ^ Muggleton, S. (1991). "Programación lógica inductiva". Computación de nueva generación . 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.). "Una nota sobre la generalización inductiva" (PDF) . Machine Intelligence . 5 : 153–163.
  12. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "Una nota adicional sobre la generalización inductiva". Inteligencia artificial . 6 : 101–124.
  13. ^ 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.
  14. ^ Quinlan, JR; Cameron-Jones, RM (1993). "Cómo evitar errores al aprender teorías recursivas". IJCAI : 1050–1057. S2CID  11138624.
  15. ^ Quinlan, JR; Cameron-Jones, RM (1995). "Inducción de programas lógicos: FOIL y sistemas relacionados" (PDF) . 13 (3–4). Springer: 287–312. Archivado desde el original (PDF) el 2017-09-07 . Consultado el 2017-09-07 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
  16. ^ 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 .
  17. ^ 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 minería de datos , MIT Press, págs. 117-152
  18. ^ Koza, JR (1992). Programación genética: vol. 1, Sobre la programación de computadoras por medio de la selección natural. MIT Press. ISBN 9780262111706.
  19. ^ Olsson, JR (1995). "Programación funcional inductiva utilizando transformación incremental de programas". Inteligencia artificial . 74 (1): 55–83. doi : 10.1016/0004-3702(94)00042-y .
  20. ^ 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 . Apuntes de clase en informática. Vol. 5351. págs. 199–210. CiteSeerX 10.1.1.606.1447 . doi :10.1007/978-3-540-89197-0_21. ISBN .  978-3-540-89196-3.
  21. ^ 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.
  22. ^ Gold, EM (1967). "Identificación del lenguaje en el límite". Información y Control . 10 (5): 447–474. doi : 10.1016/s0019-9958(67)91165-5 .
  23. ^ Muggleton, Stephen (1999). "Programación lógica inductiva: problemas, resultados y el desafío de aprender lenguaje en lógica". Inteligencia artificial . 114 (1–2): 283–296. doi : 10.1016/s0004-3702(99)00067-3 .; aquí: Sec.2.1
  24. ^ Olsson, JR; Powers, DMW (2003). "Aprendizaje automático del lenguaje humano mediante programación automática". Actas de la Conferencia Internacional sobre Ciencia Cognitiva : 507–512.
  25. ^ Lloyd, JW (2001). "Representación del conocimiento, computación y aprendizaje en lógica de orden superior" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
  26. ^ Lloyd, JW (2003). Lógica para el aprendizaje: aprendizaje de teorías comprensibles a partir de datos estructurados. Springer. ISBN 9783662084069.
  27. ^ Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramirez-Quintana, MJ (2014). "Cerrando la brecha entre la distancia y la generalización". Inteligencia Computacional . 30 (3): 473–513. doi : 10.1111/coin.12004 . S2CID  7255690.
  28. ^ Henderson, RJ; Muggleton, SH (2012). "Invención automática de abstracciones funcionales" (PDF) . Avances en programación lógica inductiva .
  29. ^ ab 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].
  30. ^ Muggleton, S. (2000). "Aprendizaje de programas de lógica estocástica" (PDF) . Electron. Trans. Artif. Intell . 4(B) : 141–153. Archivado desde el original (PDF) el 2017-09-07 . Consultado el 2017-09-07 .
  31. ^ De Raedt, L.; Kersting, K. (2008). Programación lógica inductiva probabilística . Springer.
  32. ^ ab Stuhlmuller, A.; Goodman, ND (2012). "Razonamiento sobre razonamiento mediante condicionamiento anidado: modelado de la teoría de la mente con programas probabilísticos". Investigación de sistemas cognitivos . 28 : 80–99. doi :10.1016/j.cogsys.2013.07.003. S2CID  7602205.
  33. ^ Lieberman, H.; Paternò, F.; Wulf, V. (2006). Desarrollo de usuario final . Springer.
  34. ^ Lieberman, H. (2001). Tus deseos son órdenes: Programación con ejemplos. Morgan Kaufmann. ISBN 9781558606883.
  35. ^ Cypher, E.; Halbert, DC (1993). Observa lo que hago: programación por demostración. MIT Press. ISBN 9780262032131.
  36. ^ 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.
  37. ^ 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.
  38. ^ Hernandez-Orallo, J. (2000). "Aprendizaje por refuerzo constructivo". 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. 
  39. ^ Kemp, C.; Goodman, N.; Tenenbaum, J. B. (2007). "Aprendizaje y uso de teorías relacionales" (PDF) . Avances en sistemas de procesamiento de información neuronal : 753–760.
  40. ^ Schmid, U. ; Kitzelmann, E. (2011). "Aprendizaje de reglas inductivas en el nivel de conocimiento". Cognitive Systems Research . 12 (3): 237–248. doi :10.1016/j.cogsys.2010.12.002. S2CID  18613664.

Lectura adicional

Enlaces externos