Вероятностно-логическое программирование
Парадигма программирования

Вероятностное логическое программирование — это парадигма программирования , сочетающая логическое программирование с вероятностями.

Большинство подходов к вероятностному логическому программированию основаны на семантике распределения, которая разделяет программу на набор вероятностных фактов и логическую программу. Она определяет распределение вероятностей по интерпретациям вселенной Эрбрана программы.

Языки

Большинство подходов к вероятностному логическому программированию основаны на семантике распределения, [1] которая лежит в основе многих языков, таких как Probabilistic Horn Abduction, PRISM, Independent Choice Logic, probabilistic Datalog , Logic Programs with Annotated Disjunctions, ProbLog , P-log и CP-logic. Хотя количество языков велико, многие из них разделяют общий подход, так что существуют преобразования с линейной сложностью , которые могут переводить один язык в другой. [2]

Семантика

В рамках семантики распределения вероятностная логическая программа интерпретируется как набор независимых вероятностных фактов ( основных атомарных формул, аннотированных вероятностью) и логическая программа , которая может использовать вероятностные факты в телах своих предложений. Вероятность любого присвоения значений истинности основаниям формул, связанных с вероятностными фактами, задается произведением их вероятностей; это эквивалентно предположению, что выбор вероятностных фактов является независимыми случайными величинами . [1] [3]

Стратифицированные программы

Если для любого выбора значений истинности для вероятностных фактов результирующая логическая программа стратифицирована , она имеет уникальную минимальную модель Эрбрана , которую можно рассматривать как уникальную интерпретацию, связанную с этим выбором значений истинности. [1]

Важными подклассами стратифицированных программ являются позитивные программы, которые не используют отрицание, но могут быть рекурсивными, и ациклические программы, которые могут использовать отрицание, но не имеют рекурсивных зависимостей. [1]

Программы набора ответов

Стабильная семантика модели, лежащая в основе программирования набора ответов, придает смысл нестратифицированным программам, выделяя потенциально более одного набора ответов для каждого назначения истинностного значения вероятностных фактов. Это поднимает вопрос о том, как распределить массу вероятности по наборам ответов. [4] [5]

Язык программирования вероятностной логики P-Log решает эту проблему, разделяя массу вероятности поровну между наборами ответов, следуя принципу безразличия . [4] [6]

В качестве альтернативы, вероятностное программирование набора ответов в рамках семантики креда выделяет набор креда каждому запросу. Его нижняя граница вероятности определяется только рассмотрением тех назначений истинностных значений вероятностных фактов, для которых запрос является истинным в каждом наборе ответов результирующей программы (осторожное рассуждение); его верхняя граница вероятности определяется рассмотрением тех назначений, для которых запрос является истинным в некотором наборе ответов (смелое рассуждение). [4] [5]

Вывод

В рамках семантики распределения вероятностная логическая программа определяет распределение вероятностей по интерпретациям ее предикатов в ее вселенной Эрбрана . Вероятность основного запроса затем получается из совместного распределения запроса и миров: это сумма вероятностей миров, где запрос истинен. [2] [7] [8]

Проблема вычисления вероятности запросов называется (маргинальным) выводом . Решение ее путем вычисления всех миров и последующего определения тех, которые влекут за собой запрос, непрактично, поскольку число возможных миров экспоненциально зависит от числа основных вероятностных фактов. [2] Фактически, уже для ациклических программ и атомарных запросов вычисление условной вероятности запроса, учитывая конъюнкцию атомов в качестве доказательства, является #P -полным. [9]

Точный вывод

Обычно точный вывод выполняется путем прибегания к компиляции знаний : согласно этому, пропозициональная теория и запрос компилируются в «целевой язык», который затем используется для ответа на запросы за полиномиальное время . Компиляция становится основным вычислительным узким местом, но значительные усилия были направлены на разработку эффективных компиляторов. Методы компиляции различаются по компактности целевого языка и классу запросов и преобразований, которые они поддерживают за полиномиальное время. [2]

Приблизительный вывод

Поскольку стоимость вывода может быть очень высокой, были разработаны приблизительные алгоритмы. Они либо вычисляют подмножества возможно неполных объяснений, либо используют случайную выборку. В первом подходе подмножество объяснений обеспечивает нижнюю границу, а набор частично расширенных объяснений обеспечивает верхнюю границу. Во втором подходе истинность запроса многократно проверяется в обычной логической программе , взятой из вероятностной программы. Затем вероятность запроса определяется долей успехов. [2] [10]

Обучение

Вероятностное индуктивное логическое программирование направлено на изучение вероятностных логических программ из данных. Это включает в себя обучение параметрам, которое оценивает вероятностные аннотации программы, в то время как сами предложения задаются пользователем, и структурное обучение, в котором сами предложения индуцируются вероятностной индуктивной логической системой программирования. [2]

Обычные подходы к параметрическому обучению основаны на максимизации ожидания или градиентном спуске , в то время как структурное обучение может быть выполнено путем поиска в пространстве возможных предложений с использованием различных эвристик. [2]

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

Ссылки

  1. ^ abcd Ригуцци, Фабрицио; Свифт, Тереза ​​(2018-09-01), «Обзор вероятностного логического программирования», Декларативное логическое программирование: теория, системы и приложения , ACM, стр.  185–228 , doi :10.1145/3191315.3191319, ISBN 978-1-970001-99-0, S2CID  70180651 , получено 2023-10-25
  2. ^ abcdefg Ригуцци, Фабрицио; Беллоди, Елена; Цезе, Риккардо (2014). «История вероятностного индуктивного логического программирования». Frontiers in Robotics and AI . 1. doi : 10.3389/frobt.2014.00006 . ISSN  2296-9144.
  3. ^ Де Рэдт, Люк; Киммиг, Ангелика (2015-07-01). «Концепции вероятностного (логического) программирования». Машинное обучение . 100 (1): 5– 47. doi :10.1007/s10994-015-5494-z. ISSN  1573-0565.
  4. ^ abc Riguzzi, Fabrizio (2023-05-22), «Программирование вероятностных наборов ответов», Основы вероятностного логического программирования , Нью-Йорк: River Publishers, стр.  165–173 , doi :10.1201/9781003427421-6, ISBN 978-1-003-42742-1, получено 2024-02-03
  5. ^ ab Cozman, Fabio Gagliardi; Mauá, Denis Deratani (2020). «Радость вероятностного программирования наборов ответов: семантика, сложность, выразительность, вывод». International Journal of Approximate Reasoning . 125 : 218– 239. doi : 10.1016/j.ijar.2020.07.004. S2CID  222233309.
  6. ^ Барал, Читта; Гелфонд, Майкл; Раштон, Нельсон (2009). «Вероятностное рассуждение с наборами ответов». Теория и практика логического программирования . 9 (1): 57– 144. doi :10.1017/S1471068408003645. ISSN  1471-0684.
  7. ^ Пул, Дэвид (1993). «Вероятностное Хорновское отведение и байесовские сети». Искусственный интеллект . 64 (1): 81– 129. doi :10.1016/0004-3702(93)90061-f. ISSN  0004-3702.
  8. ^ Сато, Тайсуке (1995), «Статистический метод обучения для логических программ с семантикой распределения», Труды 12-й Международной конференции по логическому программированию , The MIT Press, стр.  715–730 , doi :10.7551/mitpress/4298.003.0069, ISBN 978-0-262-29143-9, получено 2023-10-25
  9. ^ Ригуцци, Фабрицио (2023). Основы вероятностного логического программирования: Языки, семантика, вывод и обучение (2-е изд.). Gistrup, Дания: River Publishers. стр. 180. ISBN 978-87-7022-719-3.
  10. ^ Kimmig, Angelika; Demoen, Bart; Raedt, Luc De; Costa, Vítor Santos; Rocha, Ricardo (2011). «О реализации языка вероятностного логического программирования ProbLog». Теория и практика логического программирования . 11 ( 2– 3): 235– 262. arXiv : 1006.4442 . doi :10.1017/S1471068410000566. ISSN  1475-3081. S2CID  2022299.

По состоянию на 3 февраля 2024 г. эта статья полностью или частично основана на Riguzzi, Fabrizio; Bellodi, Elena; Zese, Riccardo (2014). "История вероятностного индуктивного логического программирования". Frontiers in Robotics and AI . 1 . doi : 10.3389/frobt.2014.00006 . Владелец авторских прав лицензировал контент таким образом, что позволяет повторное использование в соответствии с CC BY-SA 3.0 и GFDL . Все соответствующие условия должны быть соблюдены.

Взято с "https://en.wikipedia.org/w/index.php?title=Вероятностное_логическое_программирование&oldid=1231435352"