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

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

В зависимости от используемого языка программирования существует несколько видов индуктивного программирования. Индуктивное функциональное программирование , которое использует функциональные языки программирования, такие как 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 посвящена более широкому классу проблем, поскольку основное внимание уделяется не только рекурсивным логическим программам, но и машинному обучению символических гипотез из логических представлений. Однако были некоторые обнадеживающие результаты по обучению рекурсивным программам Prolog, таким как быстрая сортировка из примеров, вместе с подходящими фоновыми знаниями, например, с GOLEM. [13] Но снова, после первоначального успеха, сообщество было разочаровано ограниченным прогрессом в индукции рекурсивных программ [14] [15] [16], поскольку ILP все меньше и меньше фокусировался на рекурсивных программах и все больше и больше склонялся к настройке машинного обучения с приложениями в реляционном анализе данных и обнаружении знаний. [17]

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

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

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

Ссылки

  1. ^ Бирманн, AW (1992). Шапиро, SC (ред.). «Автоматическое программирование». Энциклопедия искусственного интеллекта : 18–35 .
  2. ^ Rich, C.; Waters, RC (1993). Yovits, MC (ред.). Подходы к автоматическому программированию (PDF) . Advances in Computers. Vol. 37. pp.  1– 57. doi :10.1016/S0065-2458(08)60402-7. ISBN 9780120121373.
  3. ^ Лоури, М. Л.; Маккарти, Р. Д., ред. (1991). Автоматическое проектирование программного обеспечения .
  4. ^ Манна, З.; Уолдингер, Р. (1992). «Основы дедуктивного программного синтеза». IEEE Trans Softw Eng . 18 (8): 674–704 . CiteSeerX 10.1.1.51.817 . дои : 10.1109/32.153379. 
  5. ^ Flener, P. (2002). «Достижения и перспективы синтеза программ». В Kakas, A.; Sadri, F. (ред.). Computational Logic: Logic Programming and Beyond; Essays in Honour of Robert A. Kowalski . Lecture Notes in Computer Science. Vol. LNAI 2407. pp.  310– 346. doi :10.1007/3-540-45628-7_13. ISBN 978-3-540-43959-2.
  6. ^ Саммерс, PD (1977). «Методология построения программ LISP из примеров». J ACM . 24 (1): 161– 175. doi : 10.1145/321992.322002 . S2CID  7474210.
  7. ^ Бирманн, AW (1978). «Вывод обычных программ LISP из примеров». IEEE Trans Syst Man Cybern . 8 (8): 585– 600. doi :10.1109/tsmc.1978.4310035. S2CID  15277948.
  8. ^ Смит, DR (1984). Бирманн, AW; Гихо, G. (ред.). «Синтез программ LISP из примеров: обзор». Методы автоматического построения программ : 307–324 .
  9. ^ Шапиро, EY (1983). Алгоритмическая отладка программ . MIT Press.
  10. ^ Muggleton, S. (1991). «Индуктивное логическое программирование». New Generation Computing . 8 (4): 295–318 . CiteSeerX 10.1.1.329.5312 . doi :10.1007/BF03037089. S2CID  5462416. 
  11. ^ Плоткин, Гордон Д. (1970). Мельцер, Б.; Мичи, Д. (ред.). «Заметка об индуктивном обобщении» (PDF) . Машинный интеллект . 5 : 153–163 .
  12. ^ Плоткин, Гордон Д. (1971). Мельцер, Б.; Мичи, Д. (ред.). «Дополнительное замечание об индуктивном обобщении». Машинный интеллект . 6 : 101–124 .
  13. ^ Muggleton, SH; Feng, C. (1990). «Эффективная индукция логических программ». Труды семинара по теории алгоритмического обучения . 6 : 368–381 . S2CID  14992676.
  14. ^ Куинлан, Дж. Р.; Кэмерон-Джонс, Р. М. (1993). «Избегание ловушек при изучении рекурсивных теорий». IJCAI : 1050– 1057. S2CID  11138624.
  15. ^ Куинлан, Дж. Р.; Кэмерон-Джонс, Р. М. (1995). «Индукция логических программ: FOIL и связанные с ней системы» (PDF) . 13 ( 3–4 ). Springer: 287–312 . Архивировано из оригинала (PDF) 2017-09-07 . Получено 2017-09-07 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  16. ^ Фленер, П.; Йилмаз, С. (1999). «Индуктивный синтез рекурсивных логических программ: достижения и перспективы». Журнал логического программирования . 41 (2): 141– 195. doi : 10.1016/s0743-1066(99)00028-x .
  17. ^ Джероски, Сашо (1996), «Индуктивное логическое программирование и обнаружение знаний в базах данных», в Fayyad, UM; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (ред.), Advances in Knowledge Discovery and Data Mining , MIT Press, стр.  117–152
  18. ^ Коза, Дж. Р. (1992). Генетическое программирование: т. 1, О программировании компьютеров с помощью естественного отбора. MIT Press. ISBN 9780262111706.
  19. ^ Олссон, Дж. Р. (1995). «Индуктивное функциональное программирование с использованием инкрементального преобразования программ». Искусственный интеллект . 74 (1): 55– 83. doi : 10.1016/0004-3702(94)00042-y .
  20. ^ Катаяма, Сусуму (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.
  21. ^ Angluin, D.; CH, Smith (1983). «Индуктивный вывод: теория и методы». ACM Computing Surveys . 15 (3): 237– 269. doi :10.1145/356914.356918. S2CID  3209224.
  22. ^ Голд, Э. М. (1967). «Языковая идентификация в пределе». Информация и управление . 10 (5): 447– 474. doi : 10.1016/s0019-9958(67)91165-5 .
  23. ^ Магглтон, Стивен (1999). «Индуктивное логическое программирование: проблемы, результаты и проблема изучения языка в логике». Искусственный интеллект . 114 ( 1– 2): 283– 296. doi : 10.1016/s0004-3702(99)00067-3 .; здесь: Раздел 2.1
  24. ^ Олссон, Дж. Р.; Пауэрс, Д. М. В. (2003). «Машинное обучение человеческому языку посредством автоматического программирования». Труды Международной конференции по когнитивной науке : 507–512 .
  25. ^ Ллойд, Дж. В. (2001). «Представление знаний, вычисления и обучение в логике высшего порядка» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  26. ^ Ллойд, Дж. У. (2003). Логика для обучения: изучение понятных теорий из структурированных данных. Springer. ISBN 9783662084069.
  27. ^ Эструх, В.; Ферри, К.; Эрнандес-Оралло, Дж.; Рамирес-Кинтана, М.Дж. (2014). «Преодоление разрыва между расстоянием и обобщением». Computational Intelligence . 30 (3): 473–513 . doi : 10.1111/coin.12004 . S2CID  7255690.
  28. ^ Хендерсон, Р. Дж.; Магглтон, С. Х. (2012). «Автоматическое изобретение функциональных абстракций» (PDF) . Достижения в индуктивном логическом программировании .
  29. ^ ab Ирвин, Х.; Штульмюллер, А.; Гудман, Н.Д. (2011). «Индуцирование вероятностных программ путем слияния байесовских программ». arXiv : 1110.5667 [cs.AI].
  30. ^ Muggleton, S. (2000). «Изучение стохастических логических программ» (PDF) . Electron. Trans. Artif. Intell . 4(B) : 141– 153. Архивировано из оригинала (PDF) 2017-09-07 . Получено 2017-09-07 .
  31. ^ Де Рэдт, Л.; Керстинг, К. (2008). Вероятностное индуктивное логическое программирование . Springer.
  32. ^ ab Stuhlmuller, A.; Goodman, ND (2012). «Рассуждения о рассуждениях с помощью вложенного обусловливания: моделирование теории разума с помощью вероятностных программ». Cognitive Systems Research . 28 : 80–99 . doi :10.1016/j.cogsys.2013.07.003. S2CID  7602205.
  33. ^ Либерман, Х.; Патерно, Ф.; Вульф, В. (2006). Разработка конечного пользователя . Springer.
  34. ^ Либерман, Х. (2001). Ваше желание — мой закон: Программирование на примере. Морган Кауфманн. ISBN 9781558606883.
  35. ^ Cypher, E.; Halbert, DC (1993). Посмотрите, что я делаю: программирование с помощью демонстрации. MIT Press. ISBN 9780262032131.
  36. ^ Шмид, У .; Хофманн, М.; Китцельманн, Э. (2009). «Аналитическое индуктивное программирование как средство приобретения когнитивных правил» (PDF) . Труды Второй конференции по общему искусственному интеллекту : 162–167 .
  37. ^ Кроссли, Н.; Китцельманн, Э.; Хофманн, М.; Шмид, У. (2009). «Объединение аналитического и эволюционного индуктивного программирования» (PDF) . Труды Второй конференции по общему искусственному интеллекту : 19–24 .
  38. ^ Эрнандес-Оралло, Дж. (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. 
  39. ^ Кемп, К.; Гудман, Н.; Тененбаум, Дж. Б. (2007). «Изучение и использование реляционных теорий» (PDF) . Достижения в области нейронных систем обработки информации : 753–760 .
  40. ^ Шмид, У.; Китцельманн, Э. (2011). «Индуктивное обучение правилам на уровне знаний». Cognitive Systems Research . 12 (3): 237– 248. doi :10.1016/j.cogsys.2010.12.002. S2CID  18613664.

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

  • Фленер, П.; Шмид, У. (2008). «Введение в индуктивное программирование». Обзор искусственного интеллекта . 29 (1): 45– 62. doi :10.1007/s10462-009-9108-7. S2CID  26314997.
  • Kitzelmann, E. (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.
  • Партридж, Д. (1997). «Дело в пользу индуктивного программирования». Компьютер . 30 (1): 36– 41. doi :10.1109/2.562924. S2CID  206403583.
  • Фленер, П.; Партридж, Д. (2001). «Индуктивное программирование». Автоматизированная программная инженерия . 8 (2): 131– 137. doi :10.1023/a:1008797606116. S2CID  6675212.
  • Хофманн, М.; Китцельманн, Э. (2009). «Объединяющая структура для анализа и оценки систем индуктивного программирования». Труды Второй конференции по общему искусственному интеллекту : 55–60 .
  • Muggleton, S.; De Raedt, L. (1994). «Индуктивное логическое программирование: теория и методы». Журнал логического программирования . 19– 20: 629– 679. doi : 10.1016/0743-1066(94)90035-3 .
  • Lavrac, N .; Dzeroski, S. (1994). Индуктивное логическое программирование: методы и приложения . Нью-Йорк: Ellis Horwood. ISBN 978-0-13-457870-5.https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/
  • Muggleton, S.; De Raedt, Luc.; Poole, D.; Bratko, I.; Flach, P.; Inoue, K.; Srinivasan, A. (2012). «ILP исполняется 20 лет». Машинное обучение . 86 (1): 3– 23. doi : 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.
  • Страница сообщества индуктивного программирования, поддерживаемая Университетом Бамберга.
Взято с "https://en.wikipedia.org/w/index.php?title=Индуктивное_программирование&oldid=1202053632"