Марковские логические сети (MLN): вероятностная логика для статистического обучения. Определение распределений вероятностей, формулы первого порядка, веса.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Марковская логическая сеть (MLN) — это вероятностная логика, которая применяет принципы сети Маркова к логике первого порядка, определяя распределения вероятностей по возможным мирам для любой заданной области.
A Markov logic network (MLN) is a probabilistic logic which applies the ideas of a Markov network to first order logic, defining probability distributions on possible worlds on any given domain .
История
В 2002 году Бен Таскар, Питер Аббель и Дафне Коллер представили реляционные сети Маркова как шаблоны для абстрактного описания сетей Маркова, не привязанные к конкретной предметной области. Работа над сетями Марковской логики началась в 2003 году благодаря усилиям Педро Домингоса и Мэтта Ричардсона. По состоянию на 2023 год сети Марковской логики остаются одними из наиболее популярных формализмов для статистического реляционного обучения.
In 2002, Ben Taskar, Pieter Abbeel and Daphne Koller introduced relational Markov networks as templates to specify Markov networks abstractly and without reference to a specific domain. Work on Markov logic networks began in 2003 by Pedro Domingos and Matt Richardson. as of 2023, Markov logic networks are still among the most popular formalisms for statistical relational learning.
Синтаксис
Логическая сеть Маркова состоит из набора формул логики первого порядка, каждой из которых присвоен вещественный вес. Основная идея заключается в том, что интерпретация тем более вероятна, чем больше формул с положительными весами она удовлетворяет, и тем менее вероятна, чем больше формул с отрицательными весами она удовлетворяет.
A Markov logic network consists of a collection of formulas from first order logic, to each of which is assigned a real number, the weight. The underlying idea is that an interpretation is more likely if it satisfies formulas with positive weights and less likely if it satisfies formulas with negative weights.
Семантика
Вместе с заданной областью, сеть Марковской логики определяет распределение вероятностей на множестве всех интерпретаций ее предикатов в этой области. Основная идея заключается в том, что интерпретация тем более вероятна, чем больше формул с положительными весами она удовлетворяет, и тем менее вероятна, чем больше формул с отрицательными весами она удовлетворяет. Для любого n-арного символа предиката, встречающегося в сети Марковской логики, и для каждой n-кортежа элементов домена, дается заземление. Интерпретация задается путем присвоения каждого заземления элемента булевого значения истинности (истина или ложь). Истинным заземлением формулы в интерпретации со свободными переменными является такое присваивание значений переменным, при котором формула истинна в этой интерпретации. Тогда вероятность любой данной интерпретации прямо пропорциональна ∑wᵢ, где wᵢ – вес i-го предложения в сети Марковской логики, а – количество ее истинных заземлений. Маргинальный вывод может быть выполнен с использованием стандартных методов вывода в марковских сетях, применяемых к минимальному подмножеству релевантной марковской сети, необходимому для ответа на запрос. Точный вывод является #P-полной задачей по размеру домена. Методы приближенного вывода включают выборку Гиббса, распространение убеждений или приближение с помощью псевдоправдоподобия. Класс сетей Марковской логики, использующих только две переменные в любой формуле, позволяет выполнять точный вывод за полиномиальное время путем сведения к задаче взвешенного подсчета моделей.
Together with a given domain, a Markov logic network defines a probability distribution on the set of all interpretations of its predicates on the given domain. The underlying idea is that an interpretation is more likely if it satisfies formulas with positive weights and less likely if it satisfies formulas with negative weights. For any ary predicate symbol that occurs in the Markov logic network and every tuple of domain elements, is a grounding of An interpretation is given by allocating a Boolean truth value (true or false) to each grounding of an element. A true grounding of a formula in an interpretation with free variables is a variable assignment of that makes true in that interpretation. Then the probability of any given interpretation is directly proportional to , where is the weight of the th sentence of the Markov logic network and is the number of its true groundings. Marginal inference can be performed using standard Markov network inference techniques over the minimal subset of the relevant Markov network required for answering the query. Exact inference is known to be #P complete in the size of the domain. Techniques for approximate inference include Gibbs sampling, belief propagation, or approximation via pseudolikelihood. The class of Markov logic networks which use only two variables in any formula allows for polynomial time exact inference by reduction to weighted model counting.