Маркова логика сети ( МЛН ) является вероятностной логикой , которая применяет идеи в сеть Маркова к логике первого порядка , что позволяет неопределенное умозаключение . Сети марковской логики обобщают логику первого порядка в том смысле, что в определенном пределе все невыполнимые утверждения имеют вероятность ноль, а все тавтологии имеют вероятность один.
История
Работа в этой области началась в 2003 году Педро Домингосом и Мэттом Ричардсоном, и они начали использовать термин MLN для ее описания. [1] [2]
Описание
Вкратце, это набор формул из логики первого порядка , каждой из которых присваивается действительное число - вес. В качестве сети Маркова вершины графа сети представляют собой атомарные формулы , а ребра - логические связки, используемые для построения формулы. Каждая формула считается кликой , а марковское одеяло - это набор формул, в которых фигурирует данный атом. С каждой формулой связана потенциальная функция, которая принимает значение единицы, если формула истинна, и нуля, если она ложна. Потенциальная функция комбинируется с весом для образования меры Гиббса и статистической суммы для сети Маркова.
Приведенное выше определение затушевывает тонкий момент: атомарные формулы не имеют значения истинности, если они не обоснованы и не имеют интерпретации ; то есть до тех пор, пока они не станут основными атомами в интерпретации Гербранда . Таким образом, логическая сеть Маркова становится сетью Маркова только в отношении определенного заземления и интерпретации; Полученная марковская сеть называется наземной марковской сетью . Вершины графа основной сети Маркова являются основными атомами. Таким образом, размер результирующей сети Маркова сильно (экспоненциально) зависит от количества констант в предметной области .
Вывод
Цель вывода в логической сети Маркова - найти стационарное распределение системы или близкое к нему; То, что это может быть сложно или не всегда возможно, иллюстрируется разнообразием поведения, наблюдаемым в модели Изинга . Как и в сети Маркова, стационарное распределение находит наиболее вероятное присвоение вероятностей вершинам графа; в этом случае вершины являются основными атомами интерпретации. То есть распределение указывает вероятность истинности или ложности каждого основного атома. Учитывая стационарное распределение, можно затем выполнить вывод условной вероятности в традиционном статистическом смысле : получить вероятность эта формула A верна при условии, что формула B верна.
Логический вывод в MLN может быть выполнен с использованием стандартных методов вывода сети Маркова по минимальному подмножеству соответствующей сети Маркова, необходимому для ответа на запрос. Эти методы включают в себя выборку Гиббса , которая эффективна, но может быть чрезмерно медленной для больших сетей, распространение убеждений или приближение через псевдовероятность .
Смотрите также
Ресурсы
- ^ Домингос, Педро (2015). Главный алгоритм: как машинное обучение меняет нашу жизнь . п. 246-7.
- ^ Ричардсон, Мэтью; Домингос, Педро (2006). "Марковские логические сети" (PDF) . Машинное обучение . 62 (1–2): 107–136. DOI : 10.1007 / s10994-006-5833-1 .
Внешние ссылки
- Группа статистического реляционного обучения Вашингтонского университета
- Алхимия 2.0: логические сети Маркова в C ++
- pracmln: логические сети Маркова в Python
- ProbCog: логические сети Маркова на Python и Java, которые могут использовать собственный механизм вывода или алгоритм Alchemy.
- markov thebeast: логические сети Маркова в Java
- RockIt: логические сети Маркова на Java (с веб-интерфейсом / REST API)
- Tuffy: механизм обучения и вывода с сильной оптимизацией на основе RDBM для масштабируемости
- Феликс: преемник Tuffy, с предварительно созданными подмодулями для ускорения общих подзадач.
- Factorie: язык вероятностного вывода на основе Scala с предварительно созданными подмодулями для обработки естественного языка и т. Д.
- Фигаро: язык MLN на основе Scala
- LoMRF: логические марковские случайные поля, реализация марковских логических сетей с открытым исходным кодом в Scala