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