Вероятностно-логическое программирование
Вероятностно-логическое программирование — это парадигма программирования , сочетающая логическое программирование с вероятностями.
Большинство подходов к вероятностному логическому программированию основаны на семантике распределения, которая разбивает программу на набор вероятностных фактов и логическую программу. Он определяет распределение вероятностей интерпретаций вселенной Эрбрана программы.
Языки [ править ]
Большинство подходов к вероятностно-логическому программированию основаны на семантике распределения. [1] который лежит в основе многих языков, таких как вероятностное похищение рогов, PRISM, логика независимого выбора, вероятностный журнал данных , логические программы с аннотированными дизъюнктами, ProbLog , P-log и CP-логика. Хотя количество языков велико, все они используют общий подход, поэтому существуют преобразования с линейной сложностью , которые могут переводить один язык на другой. [2]
Семантика [ править ]
В соответствии с семантикой распределения программа вероятностной логики интерпретируется как набор независимых вероятностных фактов ( основных атомарных формул , помеченных вероятностью) и логическая программа , которая может использовать вероятностные факты в телах своих предложений. Вероятность любого присвоения истинностных значений основаниям формул, связанных с вероятностными фактами, определяется произведением их вероятностей; это эквивалентно предположению, что выбор вероятностных фактов является независимыми случайными величинами . [1] [3]
Стратифицированные программы [ править ]
Если для любого выбора значений истинности для вероятностных фактов результирующая логическая программа является стратифицированной , она имеет уникальную минимальную модель Эрбрана , которую можно рассматривать как уникальную интерпретацию, связанную с этим выбором значений истинности. [1]
Важными подклассами стратифицированных программ являются позитивные программы, которые не используют отрицание, но могут быть рекурсивными, и ациклические программы, которые могут использовать отрицание, но не имеют рекурсивных зависимостей. [1]
Программы набора ответов [ править ]
Семантика стабильной модели , лежащая в основе программирования набора ответов, придает смысл нестратифицированным программам, потенциально выделяя более одного набора ответов для каждого назначения истинностного значения вероятностных фактов. Возникает вопрос, как распределить вероятностную массу по наборам ответов. [4] [5]
Язык вероятностно-логического программирования P-Log решает эту проблему, разделив вероятностную массу поровну между наборами ответов, следуя принципу безразличия . [4] [6]
Альтернативно, вероятностное программирование набора ответов в соответствии с семантикой доверенности выделяет набор доверенностей для каждого запроса. Его нижняя граница вероятности определяется путем рассмотрения только тех присвоений значений истинности вероятностных фактов, для которых запрос верен в каждом наборе ответов результирующей программы (осторожное рассуждение); его верхняя граница вероятности определяется путем рассмотрения тех заданий, для которых запрос верен в некотором наборе ответов (смелое рассуждение). [4] [5]
Вывод [ править ]
В соответствии с семантикой распределения программа вероятностной логики определяет распределение вероятностей по интерпретациям своих предикатов в своей вселенной Эрбрана . Вероятность наземного запроса затем получается из совместного распределения запроса и миров: это сумма вероятностей миров, в которых запрос верен. [2] [7] [8]
Проблема вычисления вероятности запросов называется (маргинальным) выводом . Решение этой проблемы путем вычисления всех миров и последующего определения тех, которые влекут за собой запрос, непрактично, поскольку количество возможных миров экспоненциально зависит от количества основных вероятностных фактов. [2] Фактически, уже для ациклических программ и атомарных запросов вычисление условной вероятности запроса с учетом соединения атомов в качестве доказательства является #P -полным. [9]
Точный вывод [ править ]
Обычно точный вывод выполняется, прибегая к компиляции знаний : согласно этому теория высказываний и запрос компилируются в «целевой язык», который затем используется для ответа на запросы за полиномиальное время . Компиляция становится основным узким местом вычислений, но значительные усилия были направлены на разработку эффективных компиляторов. Методы компиляции различаются компактностью целевого языка и классом запросов и преобразований, которые они поддерживают за полиномиальное время. [2]
Приблизительный вывод [ править ]
Поскольку стоимость вывода может быть очень высокой, были разработаны приближенные алгоритмы. Они либо вычисляют подмножества возможно неполных объяснений, либо используют случайную выборку. В первом подходе подмножество объяснений обеспечивает нижнюю границу, а набор частично расширенных объяснений обеспечивает верхнюю границу. При втором подходе истинность запроса многократно проверяется в обычной логической программе , выбранной из вероятностной программы. Тогда вероятность запроса определяется долей успешных результатов. [2] [10]
Обучение [ править ]
Вероятностное индуктивное логическое программирование направлено на изучение программ вероятностной логики на основе данных. Сюда входит обучение параметрам, которое оценивает вероятностные аннотации программы, в то время как сами предложения задаются пользователем, и обучение структуре, при котором сами предложения вызываются системой вероятностного индуктивного логического программирования. [2]
Общие подходы к изучению параметров основаны на максимизации ожидания или градиентном спуске , тогда как изучение структуры осуществляется путем поиска в пространстве возможных предложений с использованием различных эвристик. [2]
См. также [ править ]
- Индуктивное логическое программирование
- Вероятностная база данных
- Вероятностное программирование
- Проблог
- Статистическое реляционное обучение
Ссылки [ править ]
- ^ Перейти обратно: а б с д Ригуцци, Фабрицио; Свифт, Тереза (01 сентября 2018 г.), «Обзор вероятностно-логического программирования» , Декларативное логическое программирование: теория, системы и приложения , ACM, стр. 185–228, doi : 10.1145/3191315.3191319 , ISBN 978-1-970001-99-0 , S2CID 70180651 , получено 25 октября 2023 г.
- ^ Перейти обратно: а б с д Это ж г Ригуцци, Фабрицио; Беллоди, Елена; Зезе, Риккардо (2014). «История вероятностного индуктивно-логического программирования» . Границы робототехники и искусственного интеллекта . 1 . дои : 10.3389/frobt.2014.00006 . ISSN 2296-9144 .
- ^ Де Рэдт, Люк; Киммиг, Анжелика (01 июля 2015 г.). «Концепции вероятностного (логического) программирования» . Машинное обучение . 100 (1): 5–47. дои : 10.1007/s10994-015-5494-z . ISSN 1573-0565 .
- ^ Перейти обратно: а б с Ригуцци, Фабрицио (22 мая 2023 г.), «Программирование набора вероятностных ответов» , Основы программирования вероятностной логики , Нью-Йорк: River Publishers, стр. 165–173, doi : 10.1201/9781003427421-6 , ISBN 978-1-003-42742-1 , получено 03 февраля 2024 г.
- ^ Перейти обратно: а б Козман, Фабио Гальярди; Мауа, Денис Дератани (2020). «Радость от программирования вероятностного набора ответов: семантика, сложность, выразительность, вывод» . Международный журнал приближенного рассуждения . 125 : 218–239. дои : 10.1016/j.ijar.2020.07.004 . S2CID 222233309 .
- ^ Барал, Читта; Гельфонд, Майкл; Раштон, Нельсон (2009). «Вероятностные рассуждения с наборами ответов» . Теория и практика логического программирования . 9 (1): 57–144. дои : 10.1017/S1471068408003645 . ISSN 1471-0684 .
- ^ Пул, Дэвид (1993). «Вероятностное похищение Хорна и байесовские сети» . Искусственный интеллект . 64 (1): 81–129. дои : 10.1016/0004-3702(93)90061-ф . ISSN 0004-3702 .
- ^ Сато, Тайсуке (1995), «Статистический метод обучения для логических программ с семантикой распределения» , Труды 12-й Международной конференции по логическому программированию , MIT Press, стр. 715–730, doi : 10.7551/mitpress/4298.003.0069 , ISBN 978-0-262-29143-9 , получено 25 октября 2023 г.
- ^ Ригуцци, Фабрицио (2023). Основы вероятностно-логического программирования: языки, семантика, вывод и обучение (2-е изд.). Гиструп, Дания: River Publishers . п. 180. ИСБН 978-87-7022-719-3 .
- ^ Киммиг, Анжелика; Демоэн, Барт; Рэдт, Люк Де; Коста, Витор Сантос; Роча, Рикардо (2011). «О реализации вероятностно-логического языка программирования ProbLog» . Теория и практика логического программирования . 11 (2–3): 235–262. arXiv : 1006.4442 . дои : 10.1017/S1471068410000566 . ISSN 1475-3081 . S2CID 2022299 .
По состоянию на 3 февраля 2024 г. эта статья полностью или частично заимствована из Ригуцци, Фабрицио; Беллоди, Елена; Зезе, Риккардо (2014). «История вероятностного индуктивно-логического программирования» . Границы робототехники и искусственного интеллекта . 1 . дои : 10.3389/frobt.2014.00006 . Владелец авторских прав лицензировал контент таким образом, чтобы его можно было повторно использовать в соответствии с CC BY-SA 3.0 и GFDL . Все соответствующие условия должны быть соблюдены.