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

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

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

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

Определение

Индуктивное программирование включает в себя все подходы, которые касаются обучения программ или алгоритмов от неполных (формальный ) технические характеристики. Возможные входы в 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] Также могут быть перспективные приложения в интеллектуальных агентах, играх, робототехнике, персонализации, окружающем интеллекте и человеческих интерфейсах.

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

Рекомендации

  1. ^ Бирманн, А. (1992). Шапиро, С.С. (ред.). «Автоматическое программирование». Энциклопедия искусственного интеллекта: 18–35.
  2. ^ Rich, C .; Waters, R.C. (1993). Йовиц, М. (ред.). Подходы к автоматическому программированию (PDF). Достижения в области компьютеров. 37. С. 1–57. Дои:10.1016 / S0065-2458 (08) 60402-7. ISBN  9780120121373.
  3. ^ Lowry, M.L .; Маккарти, Р.Д., ред. (1991). Автоматическая разработка программного обеспечения.
  4. ^ Manna, Z .; Уолдингер, Р. (1992). «Основы синтеза дедуктивных программ». IEEE Trans Softw Eng. 18 (8): 674–704. CiteSeerX  10.1.1.51.817. Дои:10.1109/32.153379.
  5. ^ Фленер, П. (2002). Какас, А .; Садри, Ф. (ред.). Достижения и перспективы программного синтеза. Вычислительная логика: логическое программирование и не только; Очерки в честь Роберта А. Ковальски. Конспект лекций по информатике. LNAI 2407. С. 310–346. Дои:10.1007/3-540-45628-7_13. ISBN  978-3-540-43959-2.
  6. ^ Саммерс, П. (1977). «Методика построения LISP-программ на примерах». J ACM. 24 (1): 161–175. Дои:10.1145/321992.322002.
  7. ^ Бирманн, А. (1978). «Вывод обычных LISP-программ из примеров». IEEE Trans Syst Man Cybern. 8 (8): 585–600. Дои:10.1109 / tsmc.1978.4310035.
  8. ^ Смит, Д. (1984). Biermann, A.W .; Гихо, Г. (ред.). «Синтез программ LISP на примерах: обзор». Автоматические методы построения программ: 307–324.
  9. ^ Шапиро, Э. (1983). Отладка алгоритмической программы. MIT Press.
  10. ^ Магглетон, С. (1991). «Индуктивное логическое программирование». Вычислительная техника нового поколения. 8 (4): 295–318. CiteSeerX  10.1.1.329.5312. Дои:10.1007 / BF03037089.
  11. ^ Плоткин, Гордон Д. (1970). Мельцер, Б .; Мичи, Д. (ред.). «Заметка об индуктивном обобщении» (PDF). Машинный интеллект. 5: 153–163.
  12. ^ Плоткин, Гордон Д. (1971). Мельцер, Б .; Мичи, Д. (ред.). «Еще одно замечание об индуктивном обобщении». Машинный интеллект. 6: 101–124.
  13. ^ Muggleton, S.H .; Фэн, К. (1990). «Эффективное наведение логических программ». Материалы семинара по теории алгоритмического обучения. 6: 368–381. S2CID  14992676.
  14. ^ Quinlan, J.R .; Кэмерон-Джонс, Р. (1993). «Как избежать ловушек при изучении рекурсивных теорий». IJCAI: 1050–1057. S2CID  11138624.
  15. ^ Quinlan, J.R .; Кэмерон-Джонс, Р. (1995). «Индукция логических программ: FOIL и родственные системы» (PDF). 13 (3–4). Springer: 287–312. Цитировать журнал требует | журнал = (помощь)
  16. ^ Flener, P .; Йилмаз, С. (1999). «Индуктивный синтез рекурсивных логических программ: достижения и перспективы». Журнал логического программирования. 41 (2): 141–195. Дои:10.1016 / с0743-1066 (99) 00028-х.
  17. ^ Джероски, Сашо (1996), «Индуктивное логическое программирование и обнаружение знаний в базах данных», в Файяд, США; Пятецкий-Шапиро, Г .; Smith, P .; Утурусами Р. (ред.), Достижения в области обнаружения знаний и интеллектуального анализа данных, MIT Press, стр. 117–152.
  18. ^ Коза, Дж. Р. (1992). Генетическое программирование: т. 1. О программировании компьютеров посредством естественного отбора.. MIT Press. ISBN  9780262111706.
  19. ^ Олссон, Дж. Р. (1995). «Индуктивное функциональное программирование с использованием инкрементального программного преобразования». Искусственный интеллект. 74 (1): 55–83. Дои:10.1016 / 0004-3702 (94) 00042-г.
  20. ^ Катаяма, Сусуму (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.
  21. ^ Angluin, D .; Ч., Смит (1983). «Индуктивный вывод: теория и методы». Опросы ACM Computing. 15 (3): 237–269. Дои:10.1145/356914.356918.
  22. ^ Голд, E.M. (1967). «Определение языка в пределе». Информация и контроль. 10 (5): 447–474. Дои:10.1016 / s0019-9958 (67) 91165-5.
  23. ^ Магглетон, Стивен (1999). «Индуктивное логическое программирование: проблемы, результаты и проблема изучения языка в логике». Искусственный интеллект. 114 (1–2): 283–296. Дои:10.1016 / с0004-3702 (99) 00067-3.; здесь: Раздел 2.1
  24. ^ Olsson, J.R .; Пауэрс, D.M.W. (2003). «Машинное обучение человеческого языка посредством автоматического программирования». Материалы Международной конференции по когнитивной науке.: 507–512.
  25. ^ Ллойд, Дж. (2001). «Представление знаний, вычисления и обучение в логике высокого порядка» (PDF). Цитировать журнал требует | журнал = (помощь)
  26. ^ Ллойд, Дж. (2003). Логика для обучения: изучение понятных теорий на основе структурированных данных. Springer. ISBN  9783662084069.
  27. ^ Estruch, V .; Ferri, C .; Hernandez-Orallo, J .; Рамирес-Кинтана, М.Дж. (2014). «Преодоление разрыва между дистанцией и обобщением». Вычислительный интеллект. 30 (3): 473–513. Дои:10.1111 / монета.12004. S2CID  7255690.
  28. ^ Хендерсон, Р.Дж .; Muggleton, S.H. (2012). «Автоматическое изобретение функциональных абстракций» (PDF). Достижения в индуктивном логическом программировании.
  29. ^ Irvin, H .; Stuhlmuller, A .; Гудман, Н.Д. (2011). «Вызвание вероятностных программ путем объединения байесовских программ». arXiv:1110.5667 [cs.AI ].
  30. ^ Магглетон, С. (2000). «Изучение программ стохастической логики» (PDF). Электрон. Пер. Артиф. Intell. 4 (В): 141–153.
  31. ^ De Raedt, L .; Керстинг, К. (2008). Вероятностное индуктивное логическое программирование. Springer.
  32. ^ Irvin, H .; Stuhlmuller, A .; Гудман, Н.Д. (2011). «Вызвание вероятностных программ путем объединения байесовских программ». arXiv:1110.5667 [cs.AI ].
  33. ^ а б Stuhlmuller, A .; Гудман, Н.Д. (2012). «Рассуждение о рассуждениях посредством вложенных условий: моделирование теории разума с помощью вероятностных программ». Исследование когнитивных систем. 28: 80–99. Дои:10.1016 / j.cogsys.2013.07.003. S2CID  7602205.
  34. ^ Либерман, H .; Paternò, F .; Вульф, В. (2006). Разработка для конечных пользователей. Springer.
  35. ^ Либерман, Х. (2001). Ваше желание - моя команда: Программирование на примере. Морган Кауфманн. ISBN  9781558606883.
  36. ^ Cypher, E .; Халберт, округ Колумбия (1993). Смотрите, чем я занимаюсь: программирование путем демонстрации. ISBN  9780262032131.
  37. ^ Schmid, U .; Hofmann, M .; Китцельманн, Э. (2009). «Аналитическое индуктивное программирование как средство усвоения когнитивных правил» (PDF). Труды Второй конференции по общему искусственному интеллекту: 162–167.
  38. ^ Crossley, N .; Kitzelmann, E .; Hofmann, M .; Шмид, У. (2009). «Сочетание аналитического и эволюционного индуктивного программирования» (PDF). Труды Второй конференции по общему искусственному интеллекту: 19–24.
  39. ^ Эрнандес-Оралло, Дж. (2000). «Конструктивное обучение с подкреплением». Международный журнал интеллектуальных систем. 15 (3): 241–264. CiteSeerX  10.1.1.34.8877. Дои:10.1002 / (sici) 1098-111x (200003) 15: 3 <241 :: aid-int6> 3.0.co; 2-z.
  40. ^ Kemp, C .; Goodman, N .; Тененбаум, Дж. Б. (2007). «Изучение и использование теорий отношений» (PDF). Достижения в системах обработки нейронной информации: 753–760.
  41. ^ Schmid, U .; Китцельманн, Э. (2011). «Индуктивное обучение правилам на уровне знаний». Исследование когнитивных систем. 12 (3): 237–248. Дои:10.1016 / j.cogsys.2010.12.002.

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

внешняя ссылка