La programación inductiva ( IP ) es un área especial de programación automática , que cubre 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 la lógica de descripción , han sido más prominentes, pero otros lenguajes (de programación) También se han utilizado paradigmas, como la programación de restricciones o la programación probabilística .
Definición
La programación inductiva incorpora todos los enfoques relacionados con programas de aprendizaje o algoritmos a partir de especificaciones incompletas ( formales ). Las posibles entradas en un sistema IP son un conjunto de entradas de formación y salidas correspondientes o una función de evaluación de salida, que describe el comportamiento deseado del programa previsto, trazas o secuencias de acción que describen el proceso de cálculo de salidas específicas, restricciones para que el programa se induzca con respecto a su eficiencia en el tiempo o su complejidad, varios tipos de conocimientos previos, como tipos de datos estándar , funciones predefinidas que se utilizarán, esquemas de programa o plantillas 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 recursivas o de bucle, o cualquier otro tipo de lenguaje de representación completo de Turing .
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 'deductiva' síntesis del programa, [3] [4] [5] donde la especificación suele estar completa.
En otros casos, la programación inductiva se ve como un área más general donde se puede utilizar cualquier lenguaje de programación o representació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 la inteligencia artificial simbólica . Una característica distintiva es el número de ejemplos o especificaciones parciales necesarias. Normalmente, las técnicas de programación inductiva pueden aprender de unos pocos ejemplos.
La diversidad de la programación inductiva por lo general proviene de las aplicaciones y los idiomas que se utilizan: además de la programación lógica y la programación funcional, otros paradigmas de programación y lenguajes de representación se han utilizado o sugerido en la programación inductiva, tales como la programación lógica funcional , programación con restricciones , probabilística programación , la programación lógica abductiva , la lógica modal , lenguas de acción , agente idiomas y muchos tipos de lenguajes imperativos .
Historia
La investigación sobre la síntesis inductiva de programas funcionales recursivos comenzó a principios de la década de 1970 y se llevó a bases teóricas firmes 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; en segundo lugar, se buscan regularidades en las trazas y se utilizan para plegarlas en un programa recursivo. Smith examina los principales resultados hasta mediados de la década de 1980. [8] Debido al progreso limitado con respecto a la gama de programas que podrían sintetizarse, las actividades de investigación disminuyeron significativamente en la próxima década.
El advenimiento de la programación lógica trajo un nuevo impulso, pero también una nueva dirección a principios de la década de 1980, especialmente debido a que el sistema MIS de Shapiro [9] finalmente generó el nuevo campo de la programación lógica inductiva (ILP). [10] Los primeros trabajos de Plotkin, [11] [12] y su " generalización menos general relativa (rlgg) ", tuvieron un impacto enorme 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 los programas de lógica recursiva, sino también en el aprendizaje automático de hipótesis simbólicas a partir de representaciones lógicas. Sin embargo, se obtuvieron algunos resultados alentadores en el aprendizaje de programas recursivos de Prolog, como Quicksort de ejemplos junto con conocimientos previos adecuados, 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 centrado en programas recursivos y inclinándose cada vez más hacia un aprendizaje automático entorno con aplicaciones de minería de datos relacionales y descubrimiento de conocimientos. [17]
Paralelamente al trabajo en ILP, Koza [18] propuso la programación genética a principios de la década de 1990 como un enfoque basado en generar y probar para los 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úsquedas sistemáticas 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.
El trabajo inicial en inducción gramatical (también conocido como inferencia gramatical) está relacionado con la programación inductiva, ya que los sistemas de reescritura o programas lógicos se pueden usar para representar reglas de producción. De hecho, los primeros trabajos sobre inferencia inductiva consideraron la inducción gramatical y la inferencia del programa Lisp como básicamente el mismo problema. [21] Los resultados en términos de capacidad de aprendizaje se relacionaron con conceptos clásicos, como la identificación en el límite, como se introdujo en la obra fundamental 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 reanudado y avanzado con gran éxito. Por lo tanto, el problema de síntesis se ha reformulado sobre la base 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 basadas en búsquedas 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 abogado por el uso de características, esquemas o distancias estructuradas de orden superior 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 poderoso 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 la 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 de lógica bayesiana). [30] [31] [32] [33]
Áreas de aplicación
El primer taller sobre Enfoques y Aplicaciones de la Programación Inductiva (AAIP) realizado en conjunto con ICML 2005 identificó todas las aplicaciones donde "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 liberar a los programadores de las tareas rutinarias, dar soporte de programación para usuarios finales o soporte de programadores novatos y sistemas de tutores de programación. Otras áreas de aplicación son el aprendizaje de idiomas, el aprendizaje de reglas de control recursivo para la planificación de la IA, el aprendizaje conceptos en minería web o para transformaciones de formato 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 , [34] las áreas relacionadas de programación por ejemplo [35] y programación por demostración , [36] y tutoría inteligente. sistemas .
Otras áreas en las que se ha aplicado recientemente la inferencia inductiva son la adquisición de conocimientos , [37] la inteligencia artificial general , [38] el aprendizaje reforzado y la evaluación de la teoría, [39] [40] y la ciencia cognitiva en general. [41] [33] También puede haber posibles aplicaciones en agentes inteligentes, juegos, robótica, personalización, inteligencia ambiental e interfaces humanas.
Ver también
- Programación evolutiva
- Razonamiento inductivo
- Desarrollo impulsado por pruebas
Referencias
- ^ Biermann, AW (1992). Shapiro, SC (ed.). "Programación automática". Enciclopedia de inteligencia artificial : 18–35.
- ^ Rich, C .; Waters, RC (1993). Yovits, MC (ed.). Enfoques de la programación automática (PDF) . Avances en informática . 37 . págs. 1-57. doi : 10.1016 / S0065-2458 (08) 60402-7 . ISBN 9780120121373.
- ^ Lowry, ML; McCarthy, RD, eds. (1991). Diseño de software automático .
- ^ Manna, Z .; Waldinger, R. (1992). "Fundamentos de la síntesis del programa deductivo". IEEE Trans Softw Eng . 18 (8): 674–704. CiteSeerX 10.1.1.51.817 . doi : 10.1109 / 32.153379 .
- ^ Flener, P. (2002). "Logros y perspectivas de síntesis del programa". En Kakas, A .; Sadri, F. (eds.). Lógica computacional: programación lógica y más . Lógica Computacional: Programación Lógica y Más Allá; Ensayos en honor a Robert A. Kowalski . Apuntes de conferencias en informática. LNAI 2407. págs. 310–346. doi : 10.1007 / 3-540-45628-7_13 . ISBN 978-3-540-43959-2.
- ^ 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 .
- ^ 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 .
- ^ Smith, DR (1984). Biermann, AW; Guiho, G. (eds.). "La síntesis de programas LISP a partir de ejemplos: una encuesta" . Técnicas automáticas de construcción de programas : 307–324.
- ^ Shapiro, EY (1983). Depuración algorítmica de programas . La prensa del MIT.
- ^ 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 .
- ^ Plotkin, Gordon D. (1970). Meltzer, B .; Michie, D. (eds.). "Una nota sobre la generalización inductiva" (PDF) . Inteligencia de máquina . 5 : 153-163.
- ^ Plotkin, Gordon D. (1971). Meltzer, B .; Michie, D. (eds.). "Una nota adicional sobre la generalización inductiva". Inteligencia de máquina . 6 : 101-124.
- ^ Muggleton, SH; Feng, C. (1990). "Inducción eficiente de programas logicos". Actas del Taller de Teoría del Aprendizaje Algorítmico . 6 : 368–381. S2CID 14992676 .
- ^ Quinlan, JR; Cameron-Jones, RM (1993). "Evitar trampas al aprender teorías recursivas". IJCAI : 1050–1057. S2CID 11138624 .
- ^ Quinlan, JR; Cameron-Jones, RM (1995). "Inducción de programas lógicos: FOIL y sistemas relacionados" (PDF) . 13 (3-4). Springer: 287–312. Cite journal requiere
|journal=
( ayuda ) - ^ Flener, P .; Yilmaz, S. (1999). "Síntesis inductiva de programas de lógica recursiva: logros y perspectivas". El diario de la programación lógica . 41 (2): 141-195. doi : 10.1016 / s0743-1066 (99) 00028-x .
- ^ Džeroski, Sašo (1996), "Programación lógica inductiva y descubrimiento de conocimientos en bases de datos", en Fayyad, UM; Piatetsky-Shapiro, G .; Smith, P .; Uthurusamy, R. (eds.), Advances in Knowledge Discovery and Data Mining , MIT Press, págs. 117-152
- ^ Koza, JR (1992). Programación genética: vol. 1, Sobre la programación de computadoras mediante selección natural . Prensa del MIT. ISBN 9780262111706.
- ^ Olsson, JR (1995). "Programación funcional inductiva mediante transformación incremental de programa". Inteligencia artificial . 74 (1): 55–83. doi : 10.1016 / 0004-3702 (94) 00042-y .
- ^ Katayama, Susumu (2008). "Generación eficiente y exhaustiva de programas funcionales mediante búsqueda Monte-Carlo con profundización iterativa" (PDF) . PRICAI 2008: Tendencias en Inteligencia Artificial . Apuntes de conferencias en informática. 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. Falta o vacío
|title=
( ayuda ) - ^ Angluin, D .; CH, Smith (1983). "Inferencia inductiva: teoría y métodos". Encuestas de computación ACM . 15 (3): 237–269. doi : 10.1145 / 356914.356918 .
- ^ Gold, EM (1967). "Identificación del idioma en el límite" . Información y control . 10 (5): 447–474. doi : 10.1016 / s0019-9958 (67) 91165-5 .
- ^ Muggleton, Stephen (1999). "Programación de 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í: Sección 2.1
- ^ 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.
- ^ Lloyd, JW (2001). "Representación del conocimiento, computación y aprendizaje en lógica de orden superior" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Lloyd, JW (2003). Lógica para aprender: aprender teorías comprensibles a partir de datos estructurados . Saltador. ISBN 9783662084069.
- ^ Estruch, V .; Ferri, C .; Hernandez-Orallo, J .; Ramírez-Quintana, MJ (2014). "Cerrar la brecha entre la distancia y la generalización". Inteligencia computacional . 30 (3): 473–513. doi : 10.1111 / moneda.12004 . S2CID 7255690 .
- ^ Henderson, RJ; Muggleton, SH (2012). "Invención automática de abstracciones funcionales" (PDF) . Avances en la programación lógica inductiva .
- ^ 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 ].
- ^ Muggleton, S. (2000). "Aprendizaje de programas de lógica estocástica" (PDF) . Electrón. Trans. Artif. Intell . 4 (B) : 141-153.
- ^ De Raedt, L .; Kersting, K. (2008). Programación lógica inductiva probabilística . Saltador.
- ^ 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 ].
- ^ a b Stuhlmuller, A .; Goodman, ND (2012). "Razonamiento sobre el razonamiento por 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 .
- ^ Lieberman, H .; Paternò, F .; Wulf, V. (2006). Desarrollo del usuario final . Saltador.
- ^ Lieberman, H. (2001). Tu deseo es mi comando: Programación con el ejemplo . Morgan Kaufmann. ISBN 9781558606883.
- ^ Cypher, E .; Halbert, DC (1993). Mira lo que hago: programación por demostración . ISBN 9780262032131.
- ^ Schmid, U .; Hofmann, M .; Kitzelmann, E. (2009). "Programación analítica inductiva como un dispositivo de adquisición de reglas cognitivas" (PDF) . Actas de la Segunda Conferencia sobre Inteligencia Artificial General : 162-167.
- ^ 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.
- ^ Hernández-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 .
- ^ Kemp, C .; Goodman, N .; Tenenbaum, JB (2007). "Aprendizaje y uso de teorías relacionales" (PDF) . Avances en los sistemas de procesamiento de información neuronal : 753–760.
- ^ Schmid, U .; Kitzelmann, E. (2011). "Aprendizaje de reglas inductivas a nivel de conocimiento". Investigación de sistemas cognitivos . 12 (3): 237–248. doi : 10.1016 / j.cogsys.2010.12.002 .
Otras lecturas
- Flener, P .; Schmid, U. (2008). "Introducción a la programación inductiva". Revisión de inteligencia artificial . 29 (1): 45–62. doi : 10.1007 / s10462-009-9108-7 .
- Kitzelmann, E. (2010). "Programación inductiva: un estudio de las técnicas de síntesis de programas" (PDF) . Enfoques y aplicaciones de la programación inductiva . Apuntes de conferencias en informática. 5812 . págs. 50–73. CiteSeerX 10.1.1.180.1237 . doi : 10.1007 / 978-3-642-11931-6_3 . ISBN 978-3-642-11930-9. Falta o vacío
|title=
( ayuda ) - Partridge, D. (1997). "El caso de la programación inductiva". Computadora . 30 (1): 36–41. doi : 10.1109 / 2.562924 .
- Flener, P .; Partridge, D. (2001). "Programación inductiva". Ingeniería de software automatizada . 8 (2): 131-137. doi : 10.1023 / a: 1008797606116 .
- Hofmann, M .; Kitzelmann, E. (2009). "Un marco unificador para el análisis y 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" . El diario de la programación lógica . 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" . Aprendizaje automático . 86 (1): 3–23. doi : 10.1007 / s10994-011-5259-2 .
- Gulwani, S .; Hernandez-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 .
enlaces externos
- Página de la comunidad de programación inductiva , alojada por la Universidad de Bamberg.