Вероятностная мягкая логика

Вероятностная мягкая логика (PSL) — это статистическая реляционная обучающая структура (SRL) для моделирования вероятностных и реляционных доменов. ^[2] Она применима к различным задачам машинного обучения , таким как коллективная классификация , разрешение сущностей , прогнозирование связей и выравнивание онтологий . PSL объединяет два инструмента: логику первого порядка с ее способностью лаконично представлять сложные явления и вероятностные графические модели , которые охватывают неопределенность и неполноту, присущие знаниям реального мира. Более конкретно, PSL использует «мягкую» логику в качестве своего логического компонента и случайные поля Маркова в качестве своей статистической модели. PSL предоставляет сложные методы вывода для поиска наиболее вероятного ответа (т. е. максимального апостериорного (MAP) состояния). «Смягчение» логических формул делает вывод операцией полиномиального времени , а не NP-трудной операцией.

Описание

Сообщество SRL представило несколько подходов, которые объединяют графические модели и логику первого порядка , чтобы обеспечить разработку сложных вероятностных моделей с реляционными структурами. Ярким примером таких подходов являются логические сети Маркова (MLN). ^[3] Как и MLN, PSL является языком моделирования (с сопутствующей реализацией ^[4] ) для обучения и прогнозирования в реляционных областях. В отличие от MLN, PSL использует мягкие значения истинности для предикатов в интервале между [0,1]. Это позволяет быстро решать базовый вывод как задачу выпуклой оптимизации. Это полезно в таких задачах, как коллективная классификация , прогнозирование связей , моделирование социальных сетей и идентификация объектов/разрешение сущностей/связывание записей .

Probabilistic Soft Logic был впервые выпущен в 2009 году Лизой Гетур и Маттиасом Брёхелером. ^[5] Эта первая версия была в значительной степени сосредоточена на рассуждениях о сходствах между сущностями. Более поздние версии PSL по-прежнему сохраняли возможность рассуждать о сходствах, но обобщали язык, чтобы сделать его более выразительным.

В 2017 году в журнале Journal of Machine Learning Research была опубликована статья, в которой подробно описывался PSL и лежащая в его основе графическая модель, а также была выпущена новая основная версия PSL (2.0.0). ^[2] Главными новыми функциями в PSL 2.0.0 были новый тип правил, используемый в основном для указания ограничений, и интерфейс командной строки .

Синтаксис и семантика

Терминология

• Программа PSL — набор правил, каждое из которых является шаблоном для потенциала в графической модели.
• Правило — Выражение, связывающее атомы. Правила обычно принимают форму либо логической импликации первого порядка , либо линейной комбинации .
• Константа — Строка или число, представляющее реальный элемент во вселенной, над которой представлена ​​программа PSL. Константы могут представлять атрибуты или целые сущности.
• Переменная — идентификатор, который можно заменить константами.
• Термин — константа или переменная.
• Предикат — отношение, определяемое уникальным именем и числом принимаемых им аргументов.
• Атом — предикат вместе со своими аргументами-терминами.
• Основной атом — атом, в котором все аргументы являются константами.

Синтаксис

Модель PSL состоит из серии взвешенных правил и ограничений. PSL поддерживает два типа правил: логические и арифметические. ^[6]

Логические правила состоят из импликации с единственным атомом или конъюнкцией атомов в теле и единственным атомом или дизъюнкцией атомов в голове. Поскольку PSL использует мягкую логику, жесткие логические операторы заменяются на мягкие логические операторы Лукасевича . Пример выражения логического правила:

Похожие ( A ,  B )  и  ИмеетМетку ( A ,  X )  ->  ИмеетМетку ( B ,  X )

Это правило можно интерпретировать следующим образом: если A и B подобны и A имеет метку X, то есть доказательства того, что B также имеет метку X.

Арифметические правила — это отношения двух линейных комбинаций атомов. Ограничение каждой стороны линейной комбинацией гарантирует, что результирующий потенциал будет выпуклым . Поддерживаются следующие реляционные операторы: =, <=, и >=.

Подобный ( А ,  В )  =  Подобный ( В ,  А )

Это правило кодирует представление о том, что сходство в этой модели симметрично.

Часто используемой функцией арифметических правил является операция суммирования. Операция суммирования может использоваться для объединения нескольких атомов. При использовании атом заменяется суммой всех возможных атомов, где переменные, не являющиеся суммированием, являются фиксированными. Переменные суммирования создаются путем добавления префикса +. Пример Fox:

HasLabel ( A ,  + X )  =  1.0

Если возможными значениями X являются label1 , label2 и label3 , то указанное выше правило эквивалентно следующему:

HasLabel ( A ,  'label1' )  +  HasLabel ( A ,  'label2' )  +  HasLabel ( A ,  'label3' )  =  1.0

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

Семантика

HL-MRF

Программа PSL определяет семейство вероятностных графических моделей , параметризованных данными. Более конкретно, семейство графических моделей, которое она определяет, принадлежит к особому классу случайных полей Маркова, известному как поле Маркова с шарнирными потерями (HL-MRF). HL-MRF определяет функцию плотности по набору непрерывных переменных с совместной областью определения, используя набор свидетельств , весов и потенциальных функций вида , где — линейная функция и . Условное распределение с учетом наблюдаемых данных определяется как ${\displaystyle \mathbf {y} =(y_{1},\cdots ,y_{n})}$ ${\displaystyle [0,1]^{n}}$ ${\displaystyle \mathbf {x} =(x_{1},\cdots ,x_{m})}$ ${\displaystyle \mathbf {w} =(w_{1},\cdots ,w_{k})}$ ${\displaystyle \mathbf {\phi } =(\phi _{1},\cdots ,\phi _{k})}$ ${\displaystyle \mathbf {\phi _{i}(\mathbf {x} ,\mathbf {y} )} =\max(\ell _{i}(\mathbf {x} ,\mathbf {y} ),0)^{d_{i}}}$ ${\displaystyle \ell _{i}}$ ${\displaystyle d_{i}\in \{1,2\}}$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {x} }$

${\displaystyle P(\mathbf {y} |\mathbf {x} )={\frac {1}{Z(\mathbf {y} )}}\exp(\sum _{i=1}^{k}w_{i}\phi _{i}(\mathbf {x} ,\mathbf {y} ))}$

Где — это функция распределения. Эта плотность является логарифмически выпуклой функцией , и, таким образом, общая задача вывода в PSL нахождения максимальной апостериорной оценки совместного состояния является выпуклой задачей. Это позволяет сделать вывод в PSL достижимым за полиномиальное время. ${\displaystyle Z(\mathbf {y} )=\int _{\mathbf {y} }\exp(\sum _{i=1}^{k}w_{i}\phi _{i}(\mathbf {x} ,\mathbf {y} ))}$ ${\displaystyle \mathbf {y} }$

Открытые/закрытые предикаты — предположение о закрытом мире

Предикаты в PSL можно обозначить как открытые и закрытые.

Когда предикат помечен как закрытый, PSL делает предположение о закрытом мире : любые предикаты, которые явно не предоставлены PSL, предполагаются ложными. Другими словами, предположение о закрытом мире предполагает, что предикат, который является частично истинным, также известен как частично истинный. Например, если бы у нас были следующие константы в данных для представления людей: и следующая константа для фильмов: , и мы предоставили PSL данные предиката и были помечены как закрытые, то PSL предположил бы это, даже если бы эти данные никогда явно не предоставлялись системе. ${\displaystyle \{Alice,Bob\}}$ ${\displaystyle \{Avatar\}}$ ${\displaystyle \{rating(Alice,Avatar)=0.8\}}$ ${\displaystyle rating(\cdot )}$ ${\displaystyle \{rating(Bob,Avatar)=0\}}$

Если предикат помечен как открытый, то PSL не делает предположения о закрытом мире. Вместо этого PSL попытается коллективно вывести ненаблюдаемые примеры.

Заземление

Данные используются для создания нескольких потенциальных функций в процессе, называемом заземлением. Полученные потенциальные функции затем используются для определения HL-MRF.

Заземление предикатов в PSL — это процесс выполнения всех возможных замен переменных в каждом предикате на существующие константы в данных, что приводит к созданию набора базовых атомов. Затем производятся все возможные замены базовых атомов на предикаты в правилах для создания базовых правил. ${\displaystyle \mathbf {y} =\{y_{1},\cdots ,y_{n}\}}$

Каждое из основных правил интерпретируется как потенциалы или жесткие ограничения в индуцированном HL-MRF. Логическое правило переводится как непрерывная релаксация булевых связок с использованием логики Лукасевича . Основное логическое правило преобразуется в его дизъюнктивную нормальную форму . Пусть будет набором индексов переменных, которые соответствуют атомам, которые не отрицаются, и, аналогично, набором индексов, соответствующих атомам, которые отрицаются, в дизъюнктивном предложении. Тогда логическое правило отображается в неравенство: ${\displaystyle I^{+}}$ ${\displaystyle I^{-}}$

${\displaystyle 1-\sum _{i\in I^{+}}y_{i}-\sum _{i\in I^{-}}(1-y_{i})\leq 0}$

Если логическое правило взвешено с весом и возведено в степень с , то потенциал ${\displaystyle w}$ ${\displaystyle d\in \{1,2\}}$

${\displaystyle \phi (\mathbf {y} )={\Big (}\max {\Big \{}1-\sum _{i\in I^{+}}y_{i}-\sum _{i\in I^{-}}(1-y_{i}),0{\Big \}}{\Big )}^{d}}$

добавляется в HL-MRF с весовым параметром . ${\displaystyle w}$

Арифметическое правило применяется , и результирующий потенциал принимает форму . ${\displaystyle \ell (\mathbf {y} )\leq 0}$ ${\displaystyle \phi (\mathbf {y} )=(\max\{\ell (\mathbf {y} ),0\})^{d}}$

Интерфейсы

PSL доступен через три различных языковых интерфейса : CLI , Java и Python . Интерфейс командной строки PSL (CLI) является рекомендуемым способом использования PSL. ^[7] Он поддерживает все обычно используемые функции в воспроизводимой форме, которая не требует компиляции. Поскольку PSL написан на Java, интерфейс PSL Java является наиболее обширным, и пользователи могут напрямую обращаться к ядру PSL. ^[8] Интерфейс Java доступен через центральный репозиторий Maven . ^[9] Интерфейс PSL Python доступен через PyPi ^[10] и использует pandas DataFrames для передачи данных между PSL и пользователем. ^[11]

Ранее PSL предоставлял интерфейс Groovy. ^[12] Он был объявлен устаревшим в версии PSL 2.2.1 и, как планируется, будет удален в версии 2.3.0. ^[13]

Примеры

Лаборатория LINQS, разработчики официальной реализации PSL, поддерживают коллекцию примеров PSL. ^[14] Эти примеры охватывают как синтетические, так и реальные наборы данных и включают примеры из академических публикаций с использованием PSL. Ниже приведен игрушечный пример из этого репозитория, который можно использовать для вывода отношений в социальной сети. Вместе с каждым правилом есть комментарий, описывающий мотивирующую интуицию, стоящую за утверждениями.

/* Люди, живущие в одном месте, с большей вероятностью знают друг друга. */ 20 :  Жил ( P1 ,  L )  &  Жил ( P2 ,  L )  &  ( P1  ! =  P2 )  ->  Знает ( P1 ,  P2 )  ^ 2/* Люди, которые не жили в одном месте, вряд ли знают друг друга. */ 5 :  Жил ( P1 ,  L1 )  &  Жил ( P2 ,  L2 )  &  ( P1  ! =  P2 )  &  ( L1  ! =  L2 )  ->  ! Знает ( P1 ,  P2 )  ^ 2/* Два человека со схожими интересами, скорее всего, знают друг друга. */ 10 :  Нравится ( P1 ,  X )  &  Нравится ( P2 ,  X )  &  ( P1  ! =  P2 )  ->  Знает ( P1 ,  P2 )  ^ 2/* Люди в одних и тех же кругах, как правило, знают друг друга (транзитивность). */ 5 :  Знает ( P1 ,  P2 )  &  Знает ( P2 ,  P3 )  &  ( P1  ! =  P3 )  ->  Знает ( P1 ,  P3 )  ^ 2/* Знание друг друга симметрично. */ Знает ( P1 ,  P2 )  =  Знает ( P2 ,  P1 )  ./* По умолчанию предполагается, что два произвольных человека не знают друг друга (отрицательный априор). */ 5 :  ! Знает ( P1 ,  P2 )  ^ 2

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

• Статистическое реляционное обучение
• Вероятностная логическая сеть
• Марковская логическая сеть
• Нечеткая логика

Ссылки

1. "PSL 2.2.2". GitHub . Получено 16 июля 2020 .
2. Бах, Стивен; Брохелер, Маттиас; Хуан, Берт; Гетур, Лиз (2017). «Случайные поля Маркова с потерями шарниров и вероятностная мягкая логика». Журнал исследований машинного обучения . 18 : 1–67.
3. Гетур, Лиз ; Таскар, Бен (2007). Введение в статистическое реляционное обучение. MIT Press. ISBN  978-0262072885.
4. "Репозиторий GitHub" . Получено 26 марта 2018 г. .
5. Брохелер, Маттиас; Гетур, Лиз (2009). Вероятностная логика сходства. Международный семинар по статистическому реляционному обучению (SRL).
6. "Спецификация правил". psl.linqs.org . LINQS Lab. 6 декабря 2019 г. . Получено 10 июля 2020 г. .
7. Августин, Эрик (15 июля 2018 г.). «Начало работы с PSL». Вероятностная мягкая логика . Получено 15 июля 2020 г.
8. "PSL API Reference". Вероятностная мягкая логика . Получено 15 июля 2020 г.
9. "Maven Repository: org.linqs » psl-java". mvnrepository.com . Получено 15 июля 2020 г. .
10. "pslpython: Интерфейс Python к программному обеспечению PSL SRL/ML". Индекс пакетов Python . Получено 15 июля 2020 г.
11. Августин, Эрик (6 декабря 2019 г.). "PSL 2.2.1 Release". Probabilistic Soft Logic . Получено 15 июля 2020 г. .
12. "Репозиторий Maven: org.linqs » psl-groovy". mvnrepository.com .
13. Августин, Эрик (6 декабря 2019 г.). "PSL 2.2.1 Release". Probabilistic Soft Logic . Получено 15 июля 2020 г. .
14. "linqs/psl-examples". Github . linqs. 19 июня 2020 г.

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

• Видеолекции о PSL на Youtube