Programmation inductive - Inductive programming

Paradigmes de programmation

La programmation inductive ( IP ) est un domaine particulier de la programmation automatique , couvrant la recherche en intelligence artificielle et en programmation , qui aborde l' apprentissage de programmes typiquement déclaratifs ( logiques ou fonctionnels ) et souvent récursifs à partir de spécifications incomplètes, telles que des exemples ou des contraintes d'entrée/sortie.

Selon le langage de programmation utilisé, il existe plusieurs types de programmation inductive. La programmation fonctionnelle inductive , qui utilise des langages de programmation fonctionnels tels que Lisp ou Haskell , et plus particulièrement la programmation logique inductive , qui utilise des langages de programmation logique tels que Prolog et d'autres représentations logiques telles que les logiques de description , ont été plus importantes, mais d'autres langages (de programmation) des paradigmes ont également été utilisés, tels que la programmation par contraintes ou la programmation probabiliste .

Définition

La programmation inductive intègre toutes les approches qui concernent l'apprentissage de programmes ou d'algorithmes à partir de spécifications ( formelles ) incomplètes . Les entrées possibles dans un système IP sont un ensemble d'entrées d'apprentissage et de sorties correspondantes ou une fonction d'évaluation de sortie, décrivant le comportement souhaité du programme prévu, des traces ou des séquences d'action qui décrivent le processus de calcul des sorties spécifiques, des contraintes pour le programme à induire concernant son efficacité en temps ou sa complexité, divers types de connaissances de base telles que des types de données standard , des fonctions prédéfinies à utiliser, des schémas de programme ou des modèles décrivant le flux de données du programme prévu, des heuristiques pour guider la recherche d'une solution ou d'autres biais.

La sortie d'un système IP est un programme dans un langage de programmation arbitraire contenant des structures de contrôle conditionnelles et en boucle ou récursives, ou tout autre type de langage de représentation complet de Turing .

Dans de nombreuses applications, le programme de sortie doit être correct par rapport aux exemples et à la spécification partielle, ce qui conduit à considérer la programmation inductive comme un domaine spécial à l'intérieur de la programmation automatique ou de la synthèse de programme , généralement opposée à la synthèse de programme « déductive », où la spécification est généralement complet.

Dans d'autres cas, la programmation inductive est considérée comme un domaine plus général où n'importe quel langage de programmation ou de représentation déclaratif peut être utilisé et nous pouvons même avoir un certain degré d'erreur dans les exemples, comme dans l' apprentissage automatique général , le domaine plus spécifique de l' exploration de structure ou le domaine de l'intelligence artificielle symbolique . Une caractéristique distinctive est le nombre d'exemples ou de spécifications partielles nécessaires. En règle générale, les techniques de programmation inductive peuvent apprendre à partir de quelques exemples.

La diversité de la programmation inductive provient généralement des applications et les langues utilisées: en dehors de la programmation logique et programmation fonctionnelle, d' autres paradigmes de programmation et langages de représentation ont été utilisés ou suggérés dans la programmation inductive, tels que la programmation fonctionnelle logique , la programmation par contraintes , probabiliste la programmation , la programmation logique abduction , la logique modale , langues d'action , les langues d'agents et de nombreux types de langages impératifs .

Histoire

La recherche sur la synthèse inductive de programmes fonctionnels récursifs a commencé au début des années 1970 et a été amenée sur des bases théoriques solides avec le système fondateur de THESIS de Summers et les travaux de Biermann. Ces approches ont été divisées en deux phases : premièrement, les exemples d'entrées-sorties sont transformés en programmes non récursifs (traces) à l'aide d'un petit ensemble d'opérateurs de base ; deuxièmement, des régularités dans les traces sont recherchées et utilisées pour les replier dans un programme récursif. Les principaux résultats jusqu'au milieu des années 1980 sont recensés par Smith. En raison des progrès limités en ce qui concerne la gamme de programmes pouvant être synthétisés, les activités de recherche ont considérablement diminué au cours de la prochaine décennie.

L'avènement de la programmation logique a apporté un nouvel élan mais aussi une nouvelle direction au début des années 1980, notamment en raison du système MIS de Shapiro qui a finalement engendré le nouveau domaine de la programmation logique inductive (ILP). Les premiers travaux de Plotkin, et sa « généralisation relative moins générale (rlgg) », ont eu un impact énorme dans la programmation logique inductive. La plupart des travaux de l'ILP abordent une classe plus large de problèmes, car l'accent n'est pas seulement mis sur les programmes logiques récursifs, mais sur l'apprentissage automatique d'hypothèses symboliques à partir de représentations logiques. Cependant, il y a eu des résultats encourageants sur l'apprentissage de programmes Prolog récursifs tels que le tri rapide à partir d'exemples avec des connaissances de base appropriées, par exemple avec GOLEM. Mais encore une fois, après le succès initial, la communauté a été déçue par les progrès limités concernant l'induction de programmes récursifs avec ILP se concentrant de moins en moins sur les programmes récursifs et se penchant de plus en plus vers un environnement d'apprentissage automatique avec des applications dans l'exploration de données relationnelles et la découverte de connaissances.

Parallèlement à son travail sur l'ILP, Koza a proposé la programmation génétique au début des années 1990 comme une approche basée sur la génération et le test des programmes d'apprentissage. L'idée de la programmation génétique a été développée dans le système de programmation inductive ADATE et le système basé sur la recherche systématique MagicHaskeller. Ici encore, les programmes fonctionnels sont appris à partir d'ensembles d'exemples positifs avec une fonction d'évaluation de sortie (fitness) qui spécifie le comportement d'entrée/sortie souhaité du programme à apprendre.

Les premiers travaux sur l'induction grammaticale (également connue sous le nom d'inférence grammaticale) sont liés à la programmation inductive, car des systèmes de réécriture ou des programmes logiques peuvent être utilisés pour représenter des règles de production. En fait, les premiers travaux sur l'inférence inductive considéraient l'induction de la grammaire et l'inférence du programme Lisp comme fondamentalement le même problème. Les résultats en termes d'apprenabilité étaient liés à des concepts classiques, tels que l'identification-à-la-limite, tels qu'introduits dans les travaux fondateurs de Gold. Plus récemment, le problème de l'apprentissage des langues a été abordé par la communauté de la programmation inductive.

Ces dernières années, les approches classiques ont été reprises et avancées avec grand succès. Par conséquent, le problème de synthèse a été reformulé sur le fond des systèmes de réécriture de termes basés sur des constructeurs en tenant compte des techniques modernes de programmation fonctionnelle, ainsi que d'une utilisation modérée des stratégies basées sur la recherche et de l'utilisation des connaissances de base ainsi que de l'invention automatique de sous-programmes. De nombreuses applications nouvelles et réussies sont récemment apparues au-delà de la synthèse de programmes, plus particulièrement dans le domaine de la manipulation de données, de la programmation par exemple et de la modélisation cognitive (voir ci-dessous).

D'autres idées ont également été explorées avec la caractéristique commune d'utiliser des langages déclaratifs pour la représentation d'hypothèses. Par exemple, l'utilisation de caractéristiques d'ordre supérieur, de schémas ou de distances structurées a été préconisée pour une meilleure gestion des types et des structures de données récursives ; l'abstraction a également été explorée comme une approche plus puissante de l' apprentissage cumulatif et de l'invention de fonctions.

Un paradigme puissant qui a été récemment utilisé pour la représentation d'hypothèses dans la programmation inductive (généralement sous la forme de modèles génératifs ) est la programmation probabiliste (et les paradigmes associés, tels que les programmes logiques stochastiques et la programmation logique bayésienne).

Zone d'application

Le premier atelier sur les Approches et Applications de la Programmation Inductive (AAIP) organisé conjointement avec l' ICML 2005 a identifié toutes les applications où « l'apprentissage de programmes ou de règles récursives est nécessaire, [...] d'abord dans le domaine du génie logiciel où l'apprentissage structurel, les assistants logiciels et les agents logiciels peuvent aider à soulager les programmeurs des tâches de routine, apporter une aide à la programmation pour les utilisateurs finaux ou aider les programmeurs novices et les systèmes de tuteurs en programmation. concepts dans le web-mining ou pour les transformations de format de données".

Depuis lors, ces domaines et bien d'autres se sont révélés être des créneaux d'application réussis pour la programmation inductive, tels que la programmation pour l'utilisateur final , les domaines connexes de la programmation par exemple et la programmation par démonstration , et les systèmes de tutorat intelligents .

D'autres domaines où l'inférence inductive a été récemment appliquée sont l' acquisition de connaissances , l'intelligence artificielle générale , l' apprentissage par renforcement et l'évaluation de la théorie, et les sciences cognitives en général. Il peut également y avoir des applications potentielles dans les agents intelligents, les jeux, la robotique, la personnalisation, l'intelligence ambiante et les interfaces humaines.

Voir également

Les références

Lectures complémentaires

Liens externes