Индуктивное программирование
Индуктивное программирование ( IP ) — это особая область автоматического программирования , охватывающая исследования в области искусственного интеллекта и программирования , которая направлена на изучение обычно декларативных ( логических или функциональных ) и часто рекурсивных программ на основе неполных спецификаций, таких как примеры ввода/вывода или ограничения.
В зависимости от используемого языка программирования существует несколько видов индуктивного программирования. Индуктивное функциональное программирование , в котором используются языки функционального программирования, такие как Lisp или Haskell , и особенно индуктивное логическое программирование , в котором используются языки логического программирования, такие как Пролог, и другие логические представления, такие как логика описания , было более известным, но другие языки (программирования) Также использовались парадигмы, такие как программирование в ограничениях или вероятностное программирование .
Определение [ править ]
Индуктивное программирование включает в себя все подходы, связанные с обучением программ или алгоритмов на основе неполных ( формальных ) спецификаций. Возможными входными данными в системе ИС являются набор обучающих входных данных и соответствующих выходных данных или функция оценки выходных данных, описывающая желаемое поведение намеченной программы, трассировки или последовательности действий, которые описывают процесс расчета конкретных выходных данных, ограничений для запускаемой программы. относительно эффективности использования времени или сложности, различных видов базовых знаний, таких как стандартные типы данных , предопределенные функции, которые будут использоваться, программные схемы или шаблоны, описывающие поток данных предполагаемой программы, эвристика для руководства поиском решения или другие предубеждения.
Результатом работы IP-системы является программа на каком-либо произвольном языке программирования, содержащая условные выражения и циклические или рекурсивные структуры управления, или любой другой язык полного по Тьюрингу представления .
Во многих приложениях выходная программа должна быть правильной по отношению к примерам и частичной спецификации, и это приводит к рассмотрению индуктивного программирования как особой области внутри автоматического программирования или синтеза программ . [1] [2] обычно выступает против «дедуктивного» синтеза программ, [3] [4] [5] где спецификация обычно полная.
В других случаях индуктивное программирование рассматривается как более общая область, в которой можно использовать любой декларативный язык программирования или представления, и мы даже можем иметь некоторую степень ошибок в примерах, как в общем машинном обучении , более специфической области анализа структур или область символического искусственного интеллекта . Отличительной особенностью является количество необходимых примеров или частичной спецификации. Обычно методы индуктивного программирования можно изучить всего на нескольких примерах.
Разнообразие индуктивного программирования обычно обусловлено приложениями и используемыми языками: помимо логического программирования и функционального программирования, в индуктивном программировании использовались или предлагались другие парадигмы программирования и языки представления, такие как функциональное логическое программирование , программирование в ограничениях , вероятностное программирование. программирование , абдуктивное логическое программирование , модальная логика , языки действий , языки агентов и многие типы императивных языков .
История [ править ]
Исследования индуктивного синтеза рекурсивных функциональных программ начались в начале 1970-х годов и были подведены на прочную теоретическую основу с помощью плодотворной системы THESIS Саммерса. [6] и работы Бирмана. [7] Эти подходы были разделены на два этапа: во-первых, примеры ввода-вывода преобразуются в нерекурсивные программы (трассы) с использованием небольшого набора базовых операторов; во-вторых, в следах ищутся закономерности и с их помощью складываются в рекурсивную программу. Основные результаты до середины 1980-х годов обобщены Смитом. [8] Из-за ограниченного прогресса в отношении спектра программ, которые можно было бы синтезировать, исследовательская деятельность в следующем десятилетии значительно сократилась.
Появление логического программирования принесло новый импульс, а также новое направление в начале 1980-х годов, особенно благодаря системе MIS Шапиро. [9] в конечном итоге породив новую область индуктивного логического программирования (ILP). [10] Ранние произведения Плоткина, [11] [12] и его « относительное наименьшее общее обобщение (rlgg) » оказали огромное влияние на индуктивное логическое программирование. Большая часть работ ПДОДИ посвящена более широкому классу проблем, поскольку основное внимание уделяется не только программам рекурсивной логики, но и машинному обучению символических гипотез на основе логических представлений. Тем не менее, были получены некоторые обнадеживающие результаты при изучении рекурсивных программ на Прологе, таких как быстрая сортировка из примеров, вместе с соответствующими базовыми знаниями, например, с GOLEM. [13] Но опять же, после первоначального успеха, сообщество было разочаровано ограниченным прогрессом во внедрении рекурсивных программ. [14] [15] [16] при этом ILP все меньше и меньше сосредотачивается на рекурсивных программах и все больше склоняется к настройке машинного обучения с приложениями для реляционного анализа данных и обнаружения знаний. [17]
Параллельно работать в НЛП Коза [18] предложил генетическое программирование в начале 1990-х годов как подход к программам обучения, основанный на создании и тестировании. Идея генетического программирования получила дальнейшее развитие в системе индуктивного программирования ADATE. [19] и система систематического поиска MagicHaskeller. [20] Здесь снова функциональные программы изучаются на основе наборов положительных примеров вместе с функцией оценки вывода (приспособленности), которая определяет желаемое поведение ввода/вывода изучаемой программы.
Ранние работы в области грамматической индукции (также известной как грамматический вывод) связаны с индуктивным программированием, поскольку для представления правил производства можно использовать системы переписывания или логические программы. Фактически, в ранних работах по индуктивному выводу индукция грамматики и вывод программ на Лиспе рассматривались как, по сути, одна и та же проблема. [21] Результаты с точки зрения обучаемости были связаны с классическими концепциями, такими как идентификация в пределе, представленными в основополагающей работе Голда. [22] Совсем недавно проблемой изучения языка занялось сообщество индуктивного программирования. [23] [24]
В последние годы классические подходы были возобновлены и с большим успехом развиваются. Таким образом, проблема синтеза была переформулирована на основе систем переписывания терминов на основе конструкторов с учетом современных методов функционального программирования, а также умеренного использования стратегий поиска и использования фоновых знаний, а также автоматического изобретения подпрограмм. В последнее время появилось много новых и успешных приложений, выходящих за рамки синтеза программ, особенно в области манипулирования данными, программирования на примерах и когнитивного моделирования (см. ниже).
Другие идеи также были исследованы с общей характеристикой использования декларативных языков для представления гипотез. Например, использование функций, схем или структурированных расстояний более высокого порядка пропагандируется для лучшей обработки рекурсивных типов и структур данных; [25] [26] [27] абстракция также изучалась как более мощный подход к кумулятивному обучению и изобретению функций. [28] [29]
Одной мощной парадигмой, которая недавно использовалась для представления гипотез в индуктивном программировании (обычно в форме генеративных моделей ), является вероятностное программирование (и родственные парадигмы, такие как программы стохастической логики и байесовское логическое программирование). [30] [31] [29] [32]
Области применения [ править ]
Первый семинар по подходам и применениям индуктивного программирования (AAIP), проведенный совместно с ICML 2005, выявил все приложения, в которых «требуется изучение программ или рекурсивных правил, [...] сначала в области разработки программного обеспечения, где структурное обучение, Программные помощники и программные агенты могут помочь освободить программистов от рутинных задач, оказать поддержку в программировании конечным пользователям или поддержку начинающих программистов и систем обучения программированию. Дальнейшими областями применения являются изучение языка, изучение правил рекурсивного управления для ИИ-планирования, рекурсивное обучение. концепции веб-майнинга или преобразования формата данных».
С тех пор эти и многие другие области оказались успешными нишами приложений для индуктивного программирования, например, программирование для конечных пользователей , [33] смежные области программирования на примерах [34] и программирование путем демонстрации , [35] и интеллектуальные системы обучения .
Другими областями, где в последнее время стал применяться индуктивный вывод, являются приобретение знаний , [36] общий искусственный интеллект , [37] обучение с подкреплением и оценка теории, [38] [39] и когнитивная наука в целом. [40] [32] Также могут найтись перспективные применения в интеллектуальных агентах, играх, робототехнике, персонализации, окружающем интеллекте и человеческих интерфейсах.
См. также [ править ]
Ссылки [ править ]
- ^ Бирманн, AW (1992). Шапиро, Южная Каролина (ред.). «Автоматическое программирование». Энциклопедия искусственного интеллекта : 18–35.
- ^ Рич, К.; Уотерс, Р.К. (1993). Йовитс, MC (ред.). Подходы к автоматическому программированию (PDF) . Достижения в области компьютеров. Том. 37. стр. 1–57. дои : 10.1016/S0065-2458(08)60402-7 . ISBN 9780120121373 .
- ^ Лоури, ML; Маккарти, РД, ред. (1991). Автоматическое проектирование программного обеспечения .
- ^ Манна, З.; Уолдингер, Р. (1992). «Основы дедуктивного программного синтеза». IEEE Trans Softw Eng . 18 (8): 674–704. CiteSeerX 10.1.1.51.817 . дои : 10.1109/32.153379 .
- ^ Фленер, П. (2002). «Достижения и перспективы синтеза программ». В Какас, А.; Садри, Ф. (ред.). Вычислительная логика: логическое программирование и не только; Очерки в честь Роберта А. Ковальского . Конспекты лекций по информатике. Том. LNAI 2407. стр. 310–346. дои : 10.1007/3-540-45628-7_13 . ISBN 978-3-540-43959-2 .
- ^ Саммерс, П.Д. (1977). «Методология построения программ LISP на примерах» . Дж АСМ . 24 (1): 161–175. дои : 10.1145/321992.322002 . S2CID 7474210 .
- ^ Бирманн, AW (1978). «Вывод обычных LISP-программ из примеров». IEEE Trans Syst Man Cybern . 8 (8): 585–600. дои : 10.1109/tsmc.1978.4310035 . S2CID 15277948 .
- ^ Смит, Д.Р. (1984). Бирманн, AW; Гуйхо, Г. (ред.). «Синтез LISP-программ на примерах: обзор» . Методы автоматического построения программ : 307–324.
- ^ Шапиро, EY (1983). Алгоритмическая отладка программы . Массачусетский технологический институт Пресс.
- ^ Магглтон, С. (1991). «Индуктивное логическое программирование». Компьютеры нового поколения . 8 (4): 295–318. CiteSeerX 10.1.1.329.5312 . дои : 10.1007/BF03037089 . S2CID 5462416 .
- ^ Плоткин, Гордон Д. (1970). Мельцер, Б.; Мичи, Д. (ред.). «Заметки об индуктивном обобщении» (PDF) . Машинный интеллект . 5 : 153–163.
- ^ Плоткин, Гордон Д. (1971). Мельцер, Б.; Мичи, Д. (ред.). «Дальнейшее примечание об индуктивном обобщении». Машинный интеллект . 6 : 101–124.
- ^ Магглтон, Шотландия; Фэн, К. (1990). «Эффективное внедрение логических программ». Труды семинара по теории алгоритмического обучения . 6 : 368–381. S2CID 14992676 .
- ^ Куинлан-младший; Кэмерон-Джонс, РМ (1993). «Как избежать ошибок при изучении рекурсивных теорий». IJCAI : 1050–1057. S2CID 11138624 .
- ^ Куинлан-младший; Кэмерон-Джонс, РМ (1995). «Индукция логических программ: FOIL и родственные системы» (PDF) . 13 (3–4). Спрингер: 287–312. Архивировано из оригинала (PDF) 7 сентября 2017 г. Проверено 7 сентября 2017 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Фленер, П.; Йылмаз, С. (1999). «Индуктивный синтез рекурсивных логических программ: достижения и перспективы» . Журнал логического программирования . 41 (2): 141–195. дои : 10.1016/s0743-1066(99)00028-x .
- ^ Джероски, Сашо (1996), «Индуктивное логическое программирование и обнаружение знаний в базах данных», в Файяде, УМ; Пятецкий-Шапиро, Г.; Смит, П.; Утурусами, Р. (ред.), « Достижения в области обнаружения знаний и интеллектуального анализа данных» , MIT Press, стр. 117–152.
- ^ Коза, младший (1992). Генетическое программирование: том. 1. О программировании компьютеров посредством естественного отбора . МТИ Пресс. ISBN 9780262111706 .
- ^ Олссон, младший (1995). «Индуктивное функциональное программирование с использованием поэтапного преобразования программы» . Искусственный интеллект . 74 (1): 55–83. дои : 10.1016/0004-3702(94)00042-у .
- ^ Катаяма, Сусуму (2008). «Эффективная исчерпывающая генерация функциональных программ с использованием поиска Монте-Карло с итеративным углублением» (PDF) . PRICAI 2008: Тенденции в области искусственного интеллекта . Конспекты лекций по информатике. Том. 5351. стр. 199–210. CiteSeerX 10.1.1.606.1447 . дои : 10.1007/978-3-540-89197-0_21 . ISBN 978-3-540-89196-3 .
- ^ Англуин, Д.; CH, Смит (1983). «Индуктивный вывод: теория и методы». Обзоры вычислительной техники ACM . 15 (3): 237–269. дои : 10.1145/356914.356918 . S2CID 3209224 .
- ^ Золото, ЕМ (1967). «Языковая идентификация в лимите» . Информация и контроль . 10 (5): 447–474. дои : 10.1016/s0019-9958(67)91165-5 .
- ^ Магглтон, Стивен (1999). «Индуктивное логическое программирование: проблемы, результаты и проблемы изучения языка в логике» . Искусственный интеллект . 114 (1–2): 283–296. дои : 10.1016/s0004-3702(99)00067-3 . ; здесь: Раздел 2.1
- ^ Олссон-младший; Пауэрс, DMW (2003). «Машинное обучение человеческого языка посредством автоматического программирования». Материалы Международной конференции по когнитивной науке : 507–512.
- ^
Ллойд, JW (2001). «Представление знаний, вычисления и обучение в логике высшего порядка» (PDF) .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Ллойд, JW (2003). Логика обучения: изучение понятных теорий на основе структурированных данных . Спрингер. ISBN 9783662084069 .
- ^ Эструх, В.; Ферри, К.; Эрнандес-Оралло, Дж.; Рамирес-Кинтана, MJ (2014). «Преодоление разрыва между расстоянием и обобщением» . Вычислительный интеллект . 30 (3): 473–513. дои : 10.1111/coin.12004 . S2CID 7255690 .
- ^ Хендерсон, Р.Дж.; Магглтон, Ш. (2012). «Автоматическое изобретение функциональных абстракций» (PDF) . Достижения в области индуктивного логического программирования .
- ^ Перейти обратно: а б Ирвин, Х.; Штулмюллер, А.; Гудман, Северная Дакота (2011). «Создание вероятностных программ путем слияния байесовских программ». arXiv : 1110.5667 [ cs.AI ].
- ^ Магглтон, С. (2000). «Изучение программ стохастической логики» (PDF) . Электрон. Пер. Артиф. Интелл . 4 (Б) : 141–153. Архивировано из оригинала (PDF) 7 сентября 2017 г. Проверено 7 сентября 2017 г.
- ^ Де Рэдт, Л.; Керстинг, К. (2008). Вероятностное индуктивно-логическое программирование . Спрингер.
- ^ Перейти обратно: а б Штулмюллер, А.; Гудман, Северная Дакота (2012). «Рассуждения о рассуждениях с помощью вложенных условий: моделирование теории разума с помощью вероятностных программ». Исследование когнитивных систем . 28 : 80–99. дои : 10.1016/j.cogsys.2013.07.003 . S2CID 7602205 .
- ^ Либерман, Х.; Патерно, Ф.; Вульф, В. (2006). Развитие конечных пользователей . Спрингер.
- ^ Либерман, Х. (2001). Ваше желание — мой приказ: Программирование на примере . Морган Кауфманн. ISBN 9781558606883 .
- ^ Сайфер, Э.; Халберт, округ Колумбия (1993). Посмотрите, что я делаю: программирование путем демонстрации . МТИ Пресс. ISBN 9780262032131 .
- ^ Шмид, Ю. ; Хофманн, М.; Китцельманн, Э. (2009). «Аналитическое индуктивное программирование как средство получения когнитивных правил» (PDF) . Материалы Второй конференции по общему искусственному интеллекту : 162–167.
- ^ Кроссли, Н.; Китцельманн, Э.; Хофманн, М.; Шмид, У. (2009). «Сочетание аналитического и эволюционного индуктивного программирования» (PDF) . Материалы второй конференции по общему искусственному интеллекту : 19–24.
- ^ Эрнандес-Оралло, Дж. (2000). «Конструктивное обучение с подкреплением». Международный журнал интеллектуальных систем . 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 . S2CID 123390956 .
- ^ Кемп, К.; Гудман, Н.; Тененбаум, Дж. Б. (2007). «Изучение и использование реляционных теорий» (PDF) . Достижения в области нейронных систем обработки информации : 753–760.
- ^ Шмид, Ю. ; Китцельманн, Э. (2011). «Индуктивное обучение правилам на уровне знаний». Исследование когнитивных систем . 12 (3): 237–248. дои : 10.1016/j.cogsys.2010.12.002 . S2CID 18613664 .
Дальнейшее чтение [ править ]
- Фленер, П.; Шмид, У. (2008). «Введение в индуктивное программирование». Обзор искусственного интеллекта . 29 (1): 45–62. дои : 10.1007/s10462-009-9108-7 . S2CID 26314997 .
- Китцельманн, Э. (2010). «Индуктивное программирование: обзор методов синтеза программ» (PDF) . Подходы и приложения индуктивного программирования . Конспекты лекций по информатике. Том. 5812. стр. 50–73. CiteSeerX 10.1.1.180.1237 . дои : 10.1007/978-3-642-11931-6_3 . ISBN 978-3-642-11930-9 .
- Партридж, Д. (1997). «Дело об индуктивном программировании». Компьютер . 30 (1): 36–41. дои : 10.1109/2.562924 . S2CID 206403583 .
- Фленер, П.; Партридж, Д. (2001). «Индуктивное программирование». Автоматизированная разработка программного обеспечения . 8 (2): 131–137. дои : 10.1023/а:1008797606116 . S2CID 6675212 .
- Хофманн, М.; Китцельманн, Э. (2009). «Объединяющая структура для анализа и оценки систем индуктивного программирования» . Материалы второй конференции по общему искусственному интеллекту : 55–60.
- Магглтон, С.; Де Рэдт, Л. (1994). «Индуктивно-логическое программирование: теория и методы» . Журнал логического программирования . 19–20: 629–679. дои : 10.1016/0743-1066(94)90035-3 .
- Лаврак, Н. ; Дзероски, С. (1994). Индуктивное логическое программирование: методы и приложения . Нью-Йорк: Эллис Хорвуд. ISBN 978-0-13-457870-5 . https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/
- Магглтон, С.; Де Рэдт, Люк; Пул, Д.; Братко И.; Флах, П.; Иноуэ, К.; Шринивасан, А. (2012). «НЛП исполняется 20 лет» . Машинное обучение . 86 (1): 3–23. дои : 10.1007/s10994-011-5259-2 .
- Гулвани, С.; Эрнандес-Оралло, Дж.; Китцельманн, Э.; Магглтон, Шотландия; Шмид, Ю. ; Зорн, Б. (2015). «Индуктивное программирование встречается с реальным миром» . Коммуникации АКМ . 58 (11): 90–99. CiteSeerX 10.1.1.696.3800 . дои : 10.1145/2736282 . hdl : 10251/64984 . S2CID 425881 .
Внешние ссылки [ править ]
- Страница сообщества индуктивного программирования , организованная Университетом Бамберга.