Pronto — прототип системы вероятностного логического вывода в OWL

, , | PavelK | 30.05.2009 | 3 комментария


Введение

В предыдущих двух заметках я затронул тему неопределенности в онтологиях вообще, а затем, сузив область рассмотрения, перешел к вероятностным онтологиям, т.е. тем, в которых используется аппарат теории вероятности для придания семантики неопределенным утверждениям (или, следуя терминологии OWL — аксиомам). Теперь я могу кратко рассказать о своих попытках реализации вероятностного логического процессора, который (в какой-то степени) способен делать логические выводы над OWL-онтологиями, содержащими вероятностные аксиомы. Он называется Pronto (PRobabilistic ONTOlogies) и работает поверх известного OWL-процессора Pellet.

Замечание: по ссылке выше размещен Pronto 0.2 — достаточно старая версия, не содержащая многих оптимизаций. Скоро должна появиться новая, значительно более быстрая версия, но к сожалению мы с Clark & Parsia пока не пришли к единому мнению о типе лицензии и правах на нее. В ближайшем будущем произойдет одно из двух: либо C&P так или иначе приобретет права на Pronto, либо я выложу его от имени университета Манчестера. Так или иначе, обещаю, что процессор останется в виде open source.

Как известно, OWL не предоставляет никаких средств для представления неопределенных знаний. Во многом это происходит потому, что на данный момент нет единого (или достаточно влиятельного) мнения насчет того, как именно они должны интерпретироваться, насколько это будет полезно в реальных задачах, а также насколько проблемной будет реализация. Собственно, Pronto — это попытка реализовать поддержку неопределенных знаний на основе теории вероятности, причем основной целью было сделать так, чтобы в основу вероятностной онтологии можно было положить любую существующую онтологию в OWL. Другими словами, пользователи должны иметь возможность расширять свои онтологии, добавляя неопределенные знания по мере необходимости, а не создавать все с нуля, только потому, что в какой-то момент что-то не получилось сформулировать в точных терминах. Последний сценарий я лично считаю малореалистичным.

Рассмотрим пример. Многие знают, что на текущий момент наиболее крупные и активно использующиеся онтологии встречаются в медицине и био-информатике. Ярким примером является Тезаурус американского национального института рака (NCI Thesaurus [1]), который содержит десятки тысяч классов, описывающих симптомы, гены, факторы риска и прочие знания, относящиеся к раковым заболеваниям. В то же время, у NCI есть маленькое online-приложение BRC Calculator [2], помогающее женщинам оценить персональный риск заболевания раком груди (breast cancer). Казалось бы, имея огромную и постоянно обновляемую базу знаний, в которой представлено все факторы риска, относящиеся к раку груди, она должна использоваться в модели этого приложения. Однако — нет, что несколько разочаровывает. Причина банальна — при прогнозировании рака груди необходимо учитывать статистику о заболеваемости категорий женщин, обладающих теми или инами факторами риска (такими как: употребление алкоголя, рак у ближайших родственников, уровень эстрогена в крови и т. д.). Эти знания, которых относительно немного по сравнению с общим объемом Тезауруса, не могут быть туда добавлены, поскольку OWL не предоставляет средств для работы со статистикой. В результате используется статистическая модель Гейла (Gail model), которая учитывает менее 10 различных факторов (в Тезаурусе содержится намного больше). Ничего не имея против статистических моделей, замечу, что ситуация выглядит немного неудачно по двум причинам:

  • Плохая интероперабельность между приложениями, использующими статистические модели и онтологии (как минимум сложно обеспечить согласованность в терминологии).
  • Приходится обновлять две независимые модели при поступлении новых знаний (ведь клинические исследования идут постоянно).

В идеале онтологические и статистические модели можно было бы совместить в виде единой гибридной модели — вероятностной онтологии. При этом приложения, которым не нужны неопределенные знания, могли бы использовать ее как и раньше, а приложения вроде BRC Calculator — могли бы запрашивать сервисы вероятностного вывода. Это бы решило обе вышеперечисленные проблемы. В какой-то степени, Pronto пытается решить именно эту задачу. Разумеется, до победы еще очень далеко, но об этом позже.

Представление вероятностных аксиом в OWL

Сначала рассмотрим расширение OWL под названием P-OWL, которое позволяет формулировать вероятностные аксиомы. Этот язык в дополнение к OWL включает следующие синтаксические конструкции:

  1. Общие вероятностные ограничения (generic probabilistic constraints) — выражения вида (D|C)[l,u], где D и C представляют собой произвольные классы в OWL, [l,u] — интервал, в который попадает вероятность. Неформально, подобные выражение интерпретируются следующим образом: «Возьмем случайный экземпляр класса C. Тогда вероятность того, что он также будет являться экземпляром D попадает в интервал [l,u]».
  2. Индивидуальные вероятностные ограничения (individual probabilistic constraints) — выражения вида (a:C)[l,u], где a — это конкретный объект, а C — произвольный класс. Они интерпретируются как «вероятность того, что объект а является экземпляром С попадает в интервал [l,u]».

Выражения первого типа служат для представления статистических знаний, а второго — для представления субъективных знаний о том или ином объекта (см. предыдущую статью). При этом надо заметить, что семантически между ними разницы нет, поскольку в процессе логического вывода выражения типа (a:C)[l,u] преобразуются к виду (С|owl:Thing)[l,u]. Это один из недостатков языка, которое приводит к ряду странноватых побочных эффектов (их обсуждение мы можем обсудить в одной из следующих заметок).

Замечание: Если быть до конца точным, то P-OWL — это расширение OWL без номиналов (т.е. расширение описательной логики SRIQ).

Для выражения аксиом P-OWL в форматах, пригодных для представления OWL (т.е. RDF/XML, OWL XML и т.д.), используются аннотации, добавленные в OWL 2.0. Была введена специальная аннотация с URI http://clarkparsia.com/pronto#certainty, в которой задается интервал [l,u]. Самое же выражение (D|C) задается в виде обычной аксиомы C SubClassOf D. В RDF/XML аксиома (D|C)[0.5,0.7] выглядит вот так:

<rdf:Description>
<rdf:type rdf:resource=»&owl;Axiom«/>
<pronto:certainty>0.5;0.7</pronto:certainty>
<owl:predicate rdf:resource=»&rdfs;subClassOf«/>
<owl:subject rdf:resource=»C»/>
<owl:object rdf:resource=»D»/>
</rdf:Description>

Таким образом, можно, в частности, сформулировать утверждение «как минимум 80% птиц летают»: (FlyingObject|Bird)[0.8, 1] или «Твити — птица с вероятностью не более 10%»: (tweety:Bird)[0,0.1]

Вероятностный логический вывод по умолчанию в Pronto

Семантика P-OWL и принципы логического вывода, использующиеся в Pronto основаны на работах Томаса Лукашевича [3] и Дэниела Леманна [4].  Лукашевич сформулировал синтаксис и семантику вероятностной описательной логики P-SHOIN (название означает вероятностное расширение DL SHOIN, которая лежит в основе OWL), а Леманн известен своим подходом к так называемому «логическому выводу по умолчанию» (default reasoning), элементы которого реализованы в Pronto. На них следует остановиться поподробнее.

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

Нетрудно заметить, что в реальности все несколько сложнее. Зачастую случается так, что получая новую информацию нам приходится корректировать предыдущую картину. Классическим примером являются птицы и пингвины (первые, как правило, летают, вторые — нет). Допустим, что агент знает, что Твити — это птица. При этом следуя законам монотонной логики, он не может сделать вывод о том, летает ли Твити (т.к. не все птицы летают). После добавления знания, что Твити — не просто птица, а пингвин, агент сможет вывести, что Твити — не летает. Вроде все логично, но проблема в том, что во многих случаях хочется более сильного логического вывода, который бы позволил вывести, что Твити летает если явно нет знаний о том, что он принадлежит классу нелетающих птиц. Это объяснимо, поскольку птицы, как правило, летают. В этом случае вывод «Твити летает» придется пересмотреть (т.е. удалить) после получения уточняющих знаний «Твити — пингвин». Так вот «логика по умолчанию» (default logic) формализует подобные принципы логического вывода, придавая строгую семантику выражениям вроде «птицы, как правило, летают».

В P-OWL требование монотонности стало бы еще менее удовлетворительным, чем в OWL. Рассмотрим пример вероятностной онтологии, состоящей из следующих компонентов:

  1. Классической (OWL) онтологии, включающей классы Penguin, Bird, FlyingObject (пингвины, птицы, летающие объекты) и аксиому Penguin SubClassOf Bird (все пингвины — птицы),
  2. Вероятностной части, включающей утверждения (FlyingObject|Bird)[0.8,1.0], (FlyingObject|Penguin)[0, 0.05] (в целом птицы летают с вероятностью более 80%, а пингвины — менее 5%).

Казалось бы, все нормально. Однако проблема в том, что пингвины — это тоже птицы, а следовательно, для них тоже должна удовлетворяться аксиома (FlyingObject|Bird)[0.8,1.0]. Другими словами, два вероятностных утверждения конфликтуют и могут быть удовлетворены одновременно только в случае если вероятность того, что птица окажется пингвином равно нулю (тогда аксиома (FlyingObject|Penguin)[0, 0.05] будет удовлетворена тривиально). Это будет фактически означать: «пингвинов нет». А они есть.

Для решения этой проблемы используется логический вывод по умолчанию, в соответствии с которым выражения вида (FlyingObject|Bird)[0.8,1.0] интерпретируются как «как правило, случайно выбранная птица будет летать с вероятностью >80%». Это допускает существование подклассов-исключений, для которых это неверно. Главным моментом здесь является разрешение конфликтов. Традиционно для это используется принцип специфичности знаний, т.е. более специфичные знания обладают приоритетом нам менее специфичными. В данном случае, если бы у нас был объект Твити класса Пингвин, то знание того, что он — пингвин специфичнее (конкретнее), чем то, что он — птица. Соответственно был бы сделан вывод, что вероятность того, что Твити летает — <5%. Но до появления в базе знаний аксиомы (FlyingObject|Penguin)[0,0.05] вероятность была бы >80%.

Последнее, о чем важно упомянуть в контексте логического вывода в Pronto — это то, что он никак не связан с сетями Байеса и вообще любыми формализмами где во главу угла ставятся графические модели (сети Байеса, сети Маркова и т. д.). В Pronto используется исключительно логический подход, в котором не учитываются неявные отношения вероятностной независимости между классами/переменными (т.е. нет никакого d-separation, как в сетях Байеса). У этого подхода есть как преимущества, так и недостатки (о некоторых из них я упомяну ниже).

Работа с Pronto

Далее скажу пару слов о том, как работать с Pronto. Он написан на Java, так что может работать под любой ОС, под которую есть JRE. Консольный интерфейс следующий (также планируется плагин для Protege, но пока до него руки не дошли):

pronto.bat (или .sh если используются ОС семейства Unix) <URI онтологии> <режим> <URI файла с запросом>
Параметры:

  • <URI онтологии> — физический URI вероятностной части онтологии
  • <режим> — может принимать значения «s» и «e». «s» означает, что вероятностная часть формулируется отдельно от остальной онтологии и импортирует ее. «e» означает, что обе части совмещены в одной онтологии.
  • <URI файла с запросом> — физический URI файла, в котором содержится запрос к Pronto.

Запросы могут быть следующие:

  • psat. Проверка выполнимости (satisfiability) онтологии (как классической, так и вероятностной ее части). Выполнимость означает, что существует вероятностная модель (см. предыдущую статью), которая удовлетворяет все вероятностные аксиомы.
  • Вывод общего вероятностного утверждения: entail D C, где D и C — URI классов. Будет посчитан интервал для (D|C)[…]
  • Вывод индивидуального вероятностного утверждения: entail a C, где a — URI объекта, а C — URI класса. Будет посчитан интервал для (a:C)[…]

В процессе вывода Pronto так же должен предоставить объяснения (explanations) результатов. Они считаются в виде минимального набора вероятностных аксиом, которые обеспечивают данный результат (в этом плане они напоминают объяснения в OWL).

Существующие проблемы и планы на будущее

На данный момент у Pronto есть две главные проблемы:

  1. Недостаточная выразительность. Существующий набор синтаксических конструкций позволяет выражать вероятностные отношения между классами, между классом и объектом, но не между двумяобъектами . Грубо говоря, можно выразить, что Джон — отец с вероятностью 90%, но нельзя выразить, что Джон — отец Майкла с вероятностью 90%. Лукашевич предлагает частично решить проблему с помощью номиналов в OWL, т.е. представить это утверждение в виде (john:C)[0.9,0.9] где C — это класс «fatherOf some {Michael}», но номиналы резко ухудшают вычислительную сложность, поэтому от них было пока решено отказаться.
  2. Производительность. Это главная проблема. В отсутствие неявных предположений о независимости (аналогичных Байесовским моделям) размер вероятностных интерпретаций (моделей) может расти экспоненциально от количества вероятностных аксиом. Это приводит к тому, что версия 0.2 сталкивается с серьезными проблемами уже при 15-20 вероятностных аксиомах. Правда с момента ее выхода прошел уже год и последние эксперименты показывают масштабируемость уже до 80-100 аксиом (в зависимости от сложности классической части OWL-онтологии), причем это не предел.

Кроме работы над масштабируемостью, я также занимаюсь расширением P-OWL для решения первой проблемы (скорее всего он будет называться P-OWL+). Скорее всего первый доклад на эту тему будет на DL Workshop в конце июля этого года [5].

Спасибо за внимание. На самом деле, это очень краткое описание Pronto и его языка P-OWL, но если тема заинтересует, то можно будет залатать дыры в последующих заметках.

Литература

[1] The NCI Thesaurus http://nciterms.nci.nih.gov/NCIBrowser/Dictionary.do
[2] Breast Cancer Risk Assessment Tool, www.cancer.gov/bcrisktool/
[3] Thomas Lukasiewicz, Expressive Probabilistic Description Logics, Artificial Intelligence, 172(6-7), 852-883, April 2008.
[4] Daniel J. Lehmann: Another perspective on Default Reasoning CoRR cs.AI/0203002: (2002)
[5] Pavel Klinov, Bijan Parsia и Ulrike Sattler, «On Correspondences between Probabilistic FirstOrder and Description Logics«, submitted to the International Workshop on Description Logic, Oxford, UK, 2009


Понравилась статья? Поделитесь с друзьями!


3 Responses to Pronto — прототип системы вероятностного логического вывода в OWL

  1. roshchin:

    Сергей, спасибо большое за статью. Вы не рассматривали варианты подобного описания и последующего вывода, но только без вероятностей?

    что я имею ввиду: исключения про пингвина могут быть описаны с помощью дополнительных классов: птицы_летающие и птицы_нелетающие. а вероятностные значения можно записать с помощью свойств: птица1 = летит 80. самолет1 = летит 100.
    и соответственно летающий_объект = летит (> 90).
    т.е. таким образом мы можем выражать в том числе и вероятностные вещи на достаточно примитвном уровне.

    проблема в том, что пока новый Пронто не вышел, работать с тем же p-owl достаточно нелегко в проектах, где надо менять модели на ходу…

  2. мое дело маленькое в данном случае — тех. поддержка — а благодарности все перенаправляю автору Павлу Клинову, создателю Пронто ))
    Кстати, для заметки — Авторы статьи указываются на SHCHERBAK.NET в виде рубрики в начале заметки.

  3. Лично я не рассматривал, однако многие рассматривали. Расширений DL для default reasoning достаточно немало (default description logic). Даже у Pellet, насколько я помню, была версия, поддерживающая т.н. «K-operator» для подобных целей. У C&P в блогах наверняка остались о ней записи.
    Если же Вы имеете в виду моделирование подобного средствами *обычной* монотонной DL, то тут сразу куча проблем. Во-первых, количество классов начнет расти экспоненциально. Птицы бывают не только летающие и не летающие, а еще и с крыльями и без крыльев (кстати, знаете таких?) и т.д. Плюс я не очень понял как планируется моделировать «летит > 90». Cardinality restrictions для подобного размера чисел работают мягко говоря не очень быстро.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *


Ответить с помощью ВКонтакте: