Индуктивное программирование - Inductive programming

Парадигмы программирования

Индуктивное программирование ( IP ) - это особая область автоматического программирования , охватывающая исследования в области искусственного интеллекта и программирования , которые касаются обучения обычно декларативных ( логических или функциональных ) и часто рекурсивных программ на основе неполных спецификаций, таких как примеры ввода / вывода или ограничения.

В зависимости от используемого языка программирования существует несколько видов индуктивного программирования. Индуктивное функциональное программирование , в котором используются языки функционального программирования, такие как Lisp или Haskell , и особенно индуктивное логическое программирование , использующее языки логического программирования, такие как Prolog, и другие логические представления, такие как логика описания , были более заметными, но другие языки (программирования) Также использовались парадигмы, такие как программирование в ограничениях или вероятностное программирование .

Определение

Индуктивное программирование включает в себя все подходы, связанные с обучением программ или алгоритмов на основе неполных ( формальных ) спецификаций. Возможные входы в IP-системе - это набор обучающих входов и соответствующих выходов или функция оценки выходных данных, описывающая желаемое поведение предполагаемой программы, трассировки или последовательности действий, которые описывают процесс расчета конкретных выходных данных, ограничения для программы, которая должна быть вызвана. касательно эффективности использования времени или сложности, различных видов базовых знаний, таких как стандартные типы данных , предопределенные функции, которые будут использоваться, программные схемы или шаблоны, описывающие поток данных предполагаемой программы, эвристика для поиска решения или другие предубеждения.

Выходные данные IP-системы - это программа на каком-то произвольном языке программирования, содержащая условные выражения и циклические или рекурсивные управляющие структуры, или любой другой язык полного представления по Тьюрингу .

Во многих приложениях программа вывода должна быть правильной по отношению к примерам и частичной спецификации, и это приводит к рассмотрению индуктивного программирования как особой области внутри автоматического программирования или синтеза программ , обычно в отличие от `` дедуктивного '' синтеза программ, где спецификация обычно бывает полным.

В других случаях индуктивное программирование рассматривается как более общая область, в которой можно использовать любой язык декларативного программирования или представления, и мы даже можем иметь некоторую степень ошибки в примерах, как в общем машинном обучении , более конкретной области исследования структуры или область символического искусственного интеллекта . Отличительной особенностью является количество необходимых примеров или частичных спецификаций. Как правило, методам индуктивного программирования можно научиться всего на нескольких примерах.

Разнообразие индуктивного программирования обычно зависит от используемых приложений и языков: помимо логического программирования и функционального программирования, в индуктивном программировании использовались или предлагались другие парадигмы программирования и языки представления, такие как функциональное логическое программирование , программирование с ограничениями , вероятностное программирование. программирование , программирование абдуктивной логики , модальная логика , языки действий, языки агентов и многие типы императивных языков .

История

Исследования индуктивного синтеза рекурсивных функциональных программ начались в начале 1970-х годов и получили прочную теоретическую основу с помощью основополагающей системы THESIS Саммерса и работ Бирмана. Эти подходы были разделены на два этапа: во-первых, примеры ввода-вывода преобразуются в нерекурсивные программы (трассировки) с использованием небольшого набора базовых операторов; во-вторых, ищутся закономерности в трассировках и используются для их объединения в рекурсивную программу. Основные результаты до середины 1980-х гг. Были рассмотрены Смитом. Из-за ограниченного прогресса в отношении диапазона программ, которые можно было синтезировать, исследовательская деятельность значительно снизилась в следующее десятилетие.

Появление логического программирования принесло новый импульс, но также и новое направление в начале 1980-х годов, особенно благодаря системе MIS Шапиро, которая в конечном итоге породила новую область индуктивного логического программирования (ILP). Ранние работы Плоткина и его « относительное наименьшее общее обобщение (rlgg) » оказали огромное влияние на индуктивное логическое программирование. Большая часть работы по ILP направлена ​​на более широкий класс проблем, поскольку основное внимание уделяется не только программам рекурсивной логики, но и машинному обучению символических гипотез на основе логических представлений. Тем не менее, были получены некоторые обнадеживающие результаты при изучении рекурсивных программ на Прологе, таких как быстрая сортировка из примеров, вместе с соответствующими базовыми знаниями, например, с GOLEM. Но опять же, после первоначального успеха, сообщество было разочаровано ограниченным прогрессом в индукции рекурсивных программ с помощью ILP, все меньше внимания уделялось рекурсивным программам и все больше и больше склонялось к настройке машинного обучения с приложениями в реляционном анализе данных и обнаружении знаний.

Параллельно с работой в ILP, Коза предложил генетическое программирование в начале 1990-х годов как основанный на генерации и тестировании подход к программам обучения. Идея генетического программирования получила дальнейшее развитие в системе индуктивного программирования ADATE и системе MagicHaskeller, основанной на систематическом поиске. Здесь снова функциональные программы изучаются из наборов положительных примеров вместе с функцией оценки результатов (пригодности), которая определяет желаемое поведение ввода / вывода программы, которую необходимо изучить.

Ранняя работа в области грамматической индукции (также известной как грамматический вывод) связана с индуктивным программированием, поскольку системы переписывания или логические программы могут использоваться для представления производственных правил. Фактически, ранние работы по индуктивному выводу считали индукцию грамматики и вывод программ на Лиспе в основном одной и той же проблемой. Результаты с точки зрения обучаемости были связаны с классическими концепциями, такими как идентификация в пределе, как это было введено в основополагающей работе Голда. Совсем недавно проблема изучения языка была решена сообществом индуктивного программирования.

В последние годы классические подходы были возобновлены и продвинуты с большим успехом. Таким образом, задача синтеза была переформулирована на фоне конструкторных систем переписывания терминов с учетом современных методов функционального программирования, а также умеренного использования стратегий на основе поиска и использования фоновых знаний, а также автоматического изобретения подпрограмм. В последнее время появилось много новых и успешных приложений, выходящих за рамки синтеза программ, особенно в области манипулирования данными, программирования на примерах и когнитивного моделирования (см. Ниже).

Другие идеи также были исследованы с общей характеристикой использования декларативных языков для представления гипотез. Например, для лучшей обработки рекурсивных типов и структур данных рекомендуется использовать функции высшего порядка, схемы или структурированные расстояния ; абстракция также рассматривалась как более мощный подход к совокупному обучению и функциональному изобретению.

Одна мощная парадигма, которая недавно использовалась для представления гипотез в индуктивном программировании (обычно в форме генеративных моделей ), - это вероятностное программирование (и связанные с ним парадигмы, такие как программы стохастической логики и программирование байесовской логики).

Области применения

Первый семинар по подходам и применению индуктивного программирования (AAIP) проводится совместно с ICML 2005 определены все приложения , в которых «изучение программ или рекурсивных правил называются в [...] первая в области программной инженерии , где структурное обучение, программные помощники и программные агенты могут помочь освободить программистов от рутинных задач, оказать поддержку программированию для конечных пользователей или поддержку начинающих программистов и систем наставников по программированию.Другими областями применения являются изучение языка, изучение рекурсивных правил управления для планирования ИИ, обучение рекурсивному концепции веб-майнинга или преобразования формата данных ».

С тех пор эти и многие другие области показали себя как успешные ниши приложений для индуктивного программирования, такие как программирование для конечных пользователей , связанные области программирования на примере и программирование путем демонстрации , а также интеллектуальные обучающие системы .

Другие области, где недавно был применен индуктивный вывод, - это получение знаний , общий искусственный интеллект , обучение с подкреплением и оценка теории, а также когнитивная наука в целом. Также могут быть перспективные приложения в интеллектуальных агентах, играх, робототехнике, персонализации, окружающем интеллекте и человеческих интерфейсах.

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки