Марковская логическая сеть

( Логическая сеть Маркова MLN ) — это вероятностная логика , которая применяет идеи сети Маркова к логике первого порядка , определяя распределения вероятностей в возможных мирах в любой заданной области .

История

В 2002 году Бен Таскар , Питер Аббил и Дафна Коллер представили реляционные сети Маркова в качестве шаблонов для абстрактного определения сетей Маркова без привязки к конкретной области . ^[1]^[2] Работа над марковскими логическими сетями началась в 2003 году Педро Домингосом и Мэттом Ричардсоном. ^[3]^[4] Марковские логические сети — популярный формализм статистического реляционного обучения . ^[5]

Синтаксис

Логическая сеть Маркова состоит из набора формул логики первого порядка , каждой из которых присвоено вещественное число — вес. Основная идея заключается в том, что интерпретация более вероятна, если она удовлетворяет формулам с положительными весами, и менее вероятна, если она удовлетворяет формулам с отрицательными весами. ^[6]

Например, следующая логическая сеть Маркова описывает, как курильщики с большей вероятностью будут дружить с другими курильщиками и как стресс способствует курению: ^[7] ${\begin{array}{lcl}2.0&::&\mathrm {smokes} (X)\leftarrow \mathrm {smokes} (Y)\land \mathrm {influences} (X,Y)\\0.5&::&\mathrm {smokes} (X)\leftarrow \mathrm {stress} (X)\end{array}}$

Семантика

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

Для любого $n$ -арный символ предиката $R$ что происходит в логической сети Маркова и в каждом $n$ - кортеж $a_{1},\dots ,a_{n}$ элементов домена, $R(a_{1},\dots ,a_{n})$ является заземлением $R$ . Интерпретация ) дается путем присвоения логического значения истинности ( истина или ложь каждому основанию элемента. Истинное обоснование формулы $\varphi$ в интерпретации со свободными переменными $x_{1},\dots ,x_{n}$ представляет собой переменное присвоение $x_{1},\dots ,x_{n}$ это делает $\varphi$ верно в такой интерпретации.

Тогда вероятность любой данной интерпретации прямо пропорциональна $\exp(\sum _{j}w_{j}n_{j})$ , где $w_{j}$ это вес $j$ -е предложение логической сети Маркова и $n_{j}$ есть число его истинных заземлений. ^[1]^[4]

Это также можно рассматривать как создание сети Маркова , узлы которой являются основаниями для предикатов, встречающихся в логической сети Маркова. Характерными функциями этой сети являются обоснования предложений, встречающихся в логической сети Маркова, со значением $e^{w}$ если заземление истинно, и 1 в противном случае (где снова $w$ – вес формулы). ^[1]

Вывод

Распределения вероятностей, индуцированные логическими сетями Маркова, можно запросить на предмет вероятности конкретного события, заданного атомарной формулой ( маргинальный вывод ), возможно, обусловленного другой атомарной формулой. ^[6]

Маржинальный вывод может быть выполнен с использованием стандартных методов вывода сети Маркова по минимальному подмножеству соответствующей сети Маркова, необходимому для ответа на запрос. Известно, что точный вывод #P -полный в зависимости от размера домена. ^[6]

На практике точная вероятность часто аппроксимируется. ^[8] Методы приближенного вывода включают выборку Гиббса , распространение убеждений или аппроксимацию с помощью псевдоправдоподобия .

Класс марковских логических сетей, которые используют только две переменные в любой формуле, допускает точный вывод за полиномиальное время путем сведения к взвешенному подсчету моделей . ^[9]^[6]

См. также

Ресурсы

^ Jump up to: ^а ^б ^с Козман, Фабио Гальярди (2020), «Языки вероятностного моделирования в структурированных и реляционных областях», Экскурсия по исследованиям искусственного интеллекта , Cham: Springer International Publishing, стр. 247–283, doi : 10.1007/978-3-030- 06167-8_9 , ISBN 978-3-030-06166-1
^ Таскар, Бен; Аббель, Питер; Коллер, Дафна (1 августа 2002 г.). «Дискриминативные вероятностные модели для реляционных данных» . Материалы Восемнадцатой конференции по неопределенности в искусственном интеллекте . УАИ'02. Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc.: 485–492. ISBN 978-1-55860-897-9 .
^ Домингос, Педро (2015). Главный алгоритм: как машинное обучение меняет нашу жизнь . п. 246-7.
^ Jump up to: ^а ^б Ричардсон, Мэтью; Домингос, Педро (2006). «Марковские логические сети» (PDF) . Машинное обучение . 62 (1–2): 107–136. дои : 10.1007/s10994-006-5833-1 .
^ Августин, Эрик (2023). Построение практических статистических реляционных систем обучения (Диссертация). Калифорнийский университет в Санта-Крус.
^ Jump up to: ^а ^б ^с ^д Сунь, Чжэнъя; Чжао, Янъян; Вэй, Чжоюй; Чжан, Вэньшэн; Ван, Цзюй (2017). «Масштабируемое обучение и вывод в логических сетях Маркова» . Международный журнал приближенного рассуждения . 82 : 39–55. дои : 10.1016/j.ijar.2016.12.003 . ISSN 0888-613X .
^ Марра, Джузеппе; Думанчич, Себастьян; Манхаев, Робин; Де Рэдт, Люк (01 марта 2024 г.). «От статистического реляционного к нейросимволическому искусственному интеллекту: опрос» . Искусственный интеллект . 328 : 104062. arXiv : 2108.11451 . дои : 10.1016/j.artint.2023.104062 . ISSN 0004-3702 . В эту статью включен текст Джузеппе Марры, Себастьяна Думанчича, Робина Манхаева и Люка Де Раедта, доступный по лицензии CC BY 4.0 .
^ Венугопал, Дипак (2017). «Достижения в методах вывода для марковских логических сетей» (PDF) . Бюллетень IEEE по интеллектуальной информатике . 18 (2): 13–19.
^ Кузелка, Ондрей (29 марта 2021 г.). «Взвешенный подсчет модели первого порядка во фрагменте с двумя переменными с счетными кванторами» . Журнал исследований искусственного интеллекта . 70 : 1281–1307. arXiv : 2007.05619 . дои : 10.1613/jair.1.12320 . ISSN 1076-9757 .

Внешние ссылки

[:0-1] Jump up to: ^а ^б ^с Козман, Фабио Гальярди (2020), «Языки вероятностного моделирования в структурированных и реляционных областях», Экскурсия по исследованиям искусственного интеллекта , Cham: Springer International Publishing, стр. 247–283, doi : 10.1007/978-3-030- 06167-8_9 , ISBN 978-3-030-06166-1

[2] Таскар, Бен; Аббель, Питер; Коллер, Дафна (1 августа 2002 г.). «Дискриминативные вероятностные модели для реляционных данных» . Материалы Восемнадцатой конференции по неопределенности в искусственном интеллекте . УАИ'02. Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc.: 485–492. ISBN 978-1-55860-897-9 .

[Dom2015-3] Домингос, Педро (2015). Главный алгоритм: как машинное обучение меняет нашу жизнь . п. 246-7.

[:1-4] Jump up to: ^а ^б Ричардсон, Мэтью; Домингос, Педро (2006). «Марковские логические сети» (PDF) . Машинное обучение . 62 (1–2): 107–136. дои : 10.1007/s10994-006-5833-1 .

[5] Августин, Эрик (2023). Построение практических статистических реляционных систем обучения (Диссертация). Калифорнийский университет в Санта-Крус.

[:2-6] Jump up to: ^а ^б ^с ^д Сунь, Чжэнъя; Чжао, Янъян; Вэй, Чжоюй; Чжан, Вэньшэн; Ван, Цзюй (2017). «Масштабируемое обучение и вывод в логических сетях Маркова» . Международный журнал приближенного рассуждения . 82 : 39–55. дои : 10.1016/j.ijar.2016.12.003 . ISSN 0888-613X .

[7] Марра, Джузеппе; Думанчич, Себастьян; Манхаев, Робин; Де Рэдт, Люк (01 марта 2024 г.). «От статистического реляционного к нейросимволическому искусственному интеллекту: опрос» . Искусственный интеллект . 328 : 104062. arXiv : 2108.11451 . дои : 10.1016/j.artint.2023.104062 . ISSN 0004-3702 . В эту статью включен текст Джузеппе Марры, Себастьяна Думанчича, Робина Манхаева и Люка Де Раедта, доступный по лицензии CC BY 4.0 .

[8] Венугопал, Дипак (2017). «Достижения в методах вывода для марковских логических сетей» (PDF) . Бюллетень IEEE по интеллектуальной информатике . 18 (2): 13–19.

[9] Кузелка, Ондрей (29 марта 2021 г.). «Взвешенный подсчет модели первого порядка во фрагменте с двумя переменными с счетными кванторами» . Журнал исследований искусственного интеллекта . 70 : 1281–1307. arXiv : 2007.05619 . дои : 10.1613/jair.1.12320 . ISSN 1076-9757 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]