Programación inductiva
# Programación inductiva

La programación inductiva (IP por sus siglas en inglés) es una área específica dentro de la programación automática, cubriendo investigaciones de inteligencia artificial y programación, que encara el aprendizaje de programas típicamente declarativos (lógicos o funcionales) y frecuentemente recursivos a partir de especificaciones incompletas tales como ejemplos de pares entrada/salida y restricciones..

Dependiendo del lenguaje de programación utilizado, hay varios tipos de programación inductiva. La programación inductiva funcional, que usa lenguajes funcionales tales como Lisp o Haskell y especialmente la mayoría de la programación de lógica inductiva, que usan lenguajes como Prolog y otras representaciones lógicas como lógica descriptiva han sido los paradigmas más prominentes pero otros paradigmas también han sido usados como la programación mediante restricciones o la programación probabilística

## Definición

La programación inductiva incorpora todos los enfoques relacionados con el aprendizaje de programas o algoritmos a partir de especificaciones formales incompletas. Las posibles entradas de un sistema de IP son conjuntos de entrenamiento y sus salidas correspondientes o una función de evaluación de salida que describe el comportamiento deseado del programa pretendido, trazas o secuencias de acciones que describan el proceso de cálculo de salidas específicas, restricciones para que el programa sea inducido para ser eficiente en tiempo o complejidad, varios tipos de conocimientos previos, como tipos de datos estándar, funciones predefinidas que se utilizarán, esquemas o plantillas de programas describiendo el flujo de datos del programa previsto o heurísticas para guiar la búsqueda de una solución.

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

En muchas aplicaciones el programa emitido debe ser correcto respecto a ejemplos y una especificación parcial y esto lleva a la consideración de la programación inductiva como un área particular dentro de la programación automática o la síntesis de programas, usualmente opuesto a la síntesis "deductiva" de programas donde la especificación es completa.

En otros casos, la programación inductiva es vista más como un área general donde cualquier lenguaje de representación o de programación declarativa puede ser usar y puede tener incluso algún grado de error en los ejemplos, como en aprendizaje automático en general y las áreas más específicas de structure mining o de la inteligencia artificial simbólica. Una característica distintiva es el número de ejemplos o especificaciones parciales necesario. Típicamente, las técnicas de programación inductiva pueden aprender de unos pocos ejemplos.

La diversidad de programación inductiva usualmente surge de las aplicaciones y los lenguajes usados: además de la programación lógica y la programación funcional, otros paradigmas y lenguajes de representación han sido usados o sugeridos en la programación inductiva, tales 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, lenguajes de agentes y muchos tipos de lenguajes imperativos.

## Historia

La investigación en la síntesis inductiva de programas funcionales recursivos comenzaron a principios de 1970 y fue puesto en firmes cimientos teóricos con el sistema seminal THESIS de Summers y el trabajo de Biermann. Estos enfoques fueron divididos en dos fases: primero, los ejemplos de entrada-salida son transformados en programas no recursivos (trazas) usando un pequeño conjunto de operadores básicos; segundo, se buscan las regularidades en las trazas y se usan en un programa recursivo. Los resultados principales hasta mediados de 1980 fueron encuestados por Smith y Biermann. Debido al progreso limitado con respecto al rango de programas que podrían ser sintetizados, las actividades de investigación decrecieron significantemente en la siguiente década.

El advenimiento de la programación lógica trajo una nueva dirección a principios de los 1980, especialmente debido al sistema MIS de Shapiro eventualmente engendrando el campo nuevo de la programación lógica inductiva (ILP por sus siglas en inglés). Los primeros trabajos de Plotkin y su "relativa generalización menos general (rigg)", tuvieron un enorme impacto en la programación lógica inductiva. La mayor parte del trabajo en ILP maneja una amplia clase de problemas, ya que el foco no está solo en los programas lógicos recursivos sino también en el aprendizaje automático de hipótesis simbólicas desde representaciones lógicas. Sin embargo, hubieros algunos resultados prometedores en el aprendizaje de programas Prolog recursivos tales como quicksort desde ejemplos junto a un conocimiento pre-existente adecuado, por ejemplo con GOLEM.

