Войти
Индуктивное программирование (IP) - это специальная область автоматического программирования, охватывающая исследования искусственного интеллекта и программирование, которое касается обучения обычно декларативного (логика или функциональный ) и часто рекурсивного программы из неполных спецификаций, таких как примеры ввода / вывода или ограничения.
В зависимости от используемого языка программирования существует несколько видов индуктивного программирования. Индуктивное функциональное программирование, в котором используются языки функционального программирования, такие как Lisp или Haskell, и особенно индуктивное логическое программирование, использующее логическое программирование. языки, такие как Prolog и другие логические представления, такие как логика описания, были более заметными, но также использовались другие парадигмы (программирования) языков, такие как программирование с ограничениями или вероятностное программирование.
Индуктивное программирование включает в себя все подходы, которые связаны с обучением программ или алгоритмов на основе неполных (формальных ) спецификаций. Возможные входы в IP-системе - это набор обучающих входов и соответствующих выходов или функция оценки выходных данных, описывающая желаемое поведение намеченной программы, трассировки или последовательности действий, которые описывают процесс вычисления конкретных выходов, ограничения для программы, которые должны быть наведены относительно ее эффективности по времени или ее сложности, различных видов базовых знаний, таких как стандартные типы данных, предопределенные функции, которые будут использоваться, схемы программ или шаблоны, описывающие данные последовательность действий намеченной программы, эвристика для поиска решения или другие предубеждения.
Вывод IP-системы - это программа на каком-то произвольном языке программирования, содержащая условные выражения и циклические или рекурсивные управляющие структуры, или любой другой тип Turing-complete языка представления.
Во многих приложениях программа вывода должна быть правильной по отношению к примерам и частичной спецификации, и это приводит к рассмотрению индуктивного программирования как особой области внутри автоматического программирования или синтеза программ, обычно противопоставляется «дедуктивному» программному синтезу, когда спецификация обычно является полной.
В других случаях индуктивное программирование рассматривается как более общая область, где можно использовать любой язык декларативного программирования или представления, и мы даже можем иметь некоторую степень ошибок в примерах, как в общем машинное обучение, более конкретная область структурного анализа или область символического искусственного интеллекта. Отличительной особенностью является количество необходимых примеров или частичных спецификаций. Как правило, методам индуктивного программирования можно научиться всего на нескольких примерах.
Разнообразие индуктивного программирования обычно зависит от используемых приложений и языков: помимо логического программирования и функционального программирования, в индуктивном программировании использовались или предлагались другие парадигмы программирования и языки представления, такие как программирование функциональной логики, программирование в ограничениях, вероятностное программирование, программирование абдуктивной логики, модальная логика, языки действий, агентные языки и многие типы императивных языков.
Исследования индуктивного синтеза рекурсивных функциональных программ начались в начале 1970-х годов и были заложены на прочную теоретическую основу с помощью основополагающего Тезиса система Саммерса и работа Бирманна. Эти подходы были разделены на два этапа: во-первых, примеры ввода-вывода преобразуются в нерекурсивные программы (трассировки) с использованием небольшого набора базовых операторов; во-вторых, ищутся закономерности в трассировках и используются для их объединения в рекурсивную программу. Основные результаты до середины 1980-х годов рассматриваются Смитом. Из-за ограниченного прогресса в отношении диапазона программ, которые можно было синтезировать, исследовательская деятельность значительно снизилась в следующее десятилетие.
Появление логического программирования принесло новый импульс, но также и новое направление в начале 1980-х, особенно из-за системы MIS Шапиро, которая в конечном итоге породила новую область индуктивного логического программирования (ILP). Ранние работы Плоткина и его «относительное наименьшее общее обобщение (rlgg)» оказали огромное влияние на индуктивное логическое программирование. Большая часть работы по ILP обращается к более широкому классу проблем, поскольку основное внимание уделяется не только программам рекурсивной логики, но и машинному обучению символических гипотез на основе логических представлений. Тем не менее, были получены некоторые обнадеживающие результаты при изучении рекурсивных программ на Прологе, таких как быстрая сортировка из примеров, вместе с соответствующими базовыми знаниями, например, с GOLEM. Но опять же, после первоначального успеха, сообщество было разочаровано ограниченным прогрессом в индукции рекурсивных программ с помощью ILP, все меньше и меньше фокусируясь на рекурсивных программах и все больше и больше склоняясь к настройке машинного обучения с приложениями в реляционном интеллектуальном анализе данных и открытие знаний.
Параллельно с работой в ILP, Коза предложил генетическое программирование в начале 1990-х годов как основанный на генерации и тестировании подход к программам обучения. Идея генетического программирования получила дальнейшее развитие в системе индуктивного программирования ADATE и системе MagicHaskeller, основанной на систематическом поиске. Здесь снова функциональные программы изучаются из наборов положительных примеров вместе с функцией оценки выхода (пригодности), которая определяет желаемое поведение ввода / вывода программы, которую необходимо изучить.
Ранние работы по индукции грамматики (также известной как грамматический вывод) связаны с индуктивным программированием, поскольку системы переписывания или логические программы могут использоваться для представления производственных правил. Фактически, ранние работы по индуктивному выводу считали индукцию грамматики и вывод программ на Лиспе в основном одной и той же проблемой. Результаты с точки зрения обучаемости были связаны с классическими концепциями, такими как идентификация в пределе, как это было введено в основополагающей работе Голда. Совсем недавно проблема изучения языка была решена сообществом индуктивного программирования.
В последние годы классические подходы были возобновлены и продвинуты с большим успехом. Таким образом, задача синтеза была переформулирована на фоне конструкторных систем переписывания терминов с учетом современных методов функционального программирования, а также умеренного использования стратегий поиска и использования фоновых знаний, а также автоматического изобретения подпрограмм. В последнее время появилось много новых и успешных приложений, выходящих за рамки синтеза программ, особенно в области манипулирования данными, программирования на примерах и когнитивного моделирования (см. Ниже).
Другие идеи также были исследованы с общей характеристикой использования декларативных языков для представления гипотез. Например, для лучшей обработки рекурсивных типов данных и структур рекомендуется использовать функции более высокого порядка, схемы или структурированные расстояния; абстракция также была исследована как более мощный подход к кумулятивному обучению и изобретению функций.
Одна мощная парадигма, которая недавно использовалась для представления гипотез в индуктивном программировании (обычно в форме из генеративных моделей ) - это вероятностное программирование (и связанные с ним парадигмы, такие как программы стохастической логики и байесовское логическое программирование).
первый семинар по подходам и приложениям индуктивного программирования (AAIP), проведенный в связи с ICML 2005, выявил все приложения, в которых «требуется изучение программ или рекурсивных правил, [...] первая в области разработки программного обеспечения, где структурное обучение, программные помощники и программные агенты могут помочь освободить программистов от рутинных задач, оказать поддержку программированию для конечных пользователей или поддержку начинающих программистов и систем наставников по программированию. Другими областями применения являются изучение языков, обучение r правила эксурсивного контроля для AI-планирования, изучения рекурсивных концепций в веб-майнинге или для преобразований формата данных ».
С тех пор эти и многие другие области показали себя как успешные ниши приложений для индуктивного программирования, такие как программирование для конечных пользователей, связанные области программирования на примере и программирование посредством демонстрации и интеллектуальные обучающие системы.
Другими областями, где недавно был применен индукционный вывод, являются получение знаний, общий искусственный интеллект, обучение с подкреплением и оценка теории, и когнитивная наука в целом. Также могут быть перспективные приложения в интеллектуальных агентах, играх, робототехнике, персонализации, окружающем интеллекте и человеческих интерфейсах.
