Аннотация

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

Замечание: В комментариях к предыдущей статье было сделано полезное замечание о том, что в русских источниках под неопределенностью часто понимают неточные знания вообще. Учитывая это, я несколько подкорректирую терминологию. Далее неточные знания типа 1, которые мы ранее называли неопределенными, будут называться вероятностно неопределенными (ВН-знания), подчеркивая то, что их семантика будет определяться при помощи теории вероятности. Тип 2 (нечеткие знания) останется без изменений.

Твити, птицы и летающие объекты

Как вы помните, мы остановились на примере двух вероятностных утверждений, которые вполне могут встретиться в неопределенной онтологии:

  1. Птицы летают с вероятностью 90%
  2. Твити - птица с вероятностью 90%

Вопрос заключался в том, есть ли разница в семантике (т.е. в смысле) этих утверждений. Очевидно, что оба утверждения относятся к типу ВН (вероятностно неопределенных) знаний, т.е. каждый объект (птица или нет) либо летает, либо не летает (опуская клинические случаи "частично летающих" птиц), поэтому семантику логично формулировать при помощи теории вероятности (ТВ).
Начнем с того, что попробуем представить эти утверждения в версии OWL, которая допускает присвоение вероятностей аксиомам (назовем ее P-OWL). Утверждения будут выглядеть следующим образом (я использую функциональный синтаксис OWL [1]):

  1. SubClassOf(Bird, FlyingObject)[0.9]
  2. ClassAssertion(tweety, Bird)[0.9]

Итак, неформально это можно прочитать следующим образом:

  1. Класс Bird (Птица) является подклассом FlyingObject (Летающий объект) с вероятностью 90%
  2. Объект tweety (Твити) является экземпляром класса Bird с вероятностью 90%

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

Бросается в глаза то, что в первом случае речь идет о птицах вообще, а во-втором - о конкретном объекте. Разница в смысле становится очевидной, если подумать, откуда могли появиться эти самые 90% в первом и во втором случае. В первом случае 90% скорее всего подразумевает некоторую выборку птиц, на которой было проведено исследование - сколько из них летает, а сколько не летает. Например, над каждой птицей был проведен эксперимент - выкидывание ее из окна, после чего было заключено, что 90% птиц летают, остальные разбиваются. Другими словами, данное утверждение представляет собой статистические знания о классе Bird.
Что же касается второго случая, то нетрудно видеть, что никакой статистики за утверждением "Твити - птица с вероятностью 90%" нет. Здесь нет выборки и нет подсчета результатов экспериментов. Разумеется, Твити тоже можно выкинуть из окна, но результата может быть только два - либо летает, либо разбивается. Так откуда же тут берутся 90% вероятности? И что вообще тут "вероятность"?
Подобного рода вопросы, разумеется, встают далеко не только в контексте онтологий. Давно было замечено, что статистическая интерпретация вероятности как относительного числа успешных экспериментов (помните школьное подбрасывание монетки?) не объясняет высказывания наподобие "с 80% вероятностью динозавры погибли от столкновения Земли с метеоритом". Поэтому была предложена альтернативная интерпретация - так называемая субъективная интерпретация вероятности [2] (на самом деле интерпретаций больше, но нам пока хватит этих двух). Субъективисты (в частности де Финетти и Рэмси) утверждают, что вероятность в таких случаях следует интерпретировать как степень веры (degree of belief) конкретного субъекта (человека, программы, агента и т.д.) в то, что данное утверждение является истинным. При этом вопрос о том, как именно эта вера формируется (например, из наблюдений за другими птицами, подбрасыванием Твити и т.д.) в данном случае является второстепенным.
На этом месте вполне законно задать вопрос, а какое мы имеем право называть эти 90% веры в то, что Твити - птица, вероятностью? Однако если отвлечься на минуту и вспомнить, что такое "вероятность" вообще, то выяснится, что это понятие гораздо шире, чем классическая "частотная" интерпретация. Вероятностью можно назвать любую вещественную функцию на пространстве событий, которая удовлетворяет трем аксиомам Колмогорова [3]:

  1. Вероятность каждого события неотрицательна.
  2. Общая вероятность всего пространства равна 1 (например, вероятность того, упадет монетка вверх орлом или решкой равна 1).
  3. Суммарная вероятность взаимоисключающих событий равна сумме вероятностей каждого.

И все. Никакой статистики, никаких экспериментов тут нет и в помине. Таким образом, если функция степени веры некоторого субъекта (агента) в то, что некоторые объекты являются птицами, удовлетворяет этим аксиомам, то данный субъект имеет полное право называть ее вероятностью. Самое замечательное в этом то, что в начале 20-го века Фрэнк Рэмси (Frank Ramsey) убедительно показал на примере простой игры ("голландского аукциона"), что если агент желает действовать рационально, основываясь на степени своей вере в то, что он досконально не знает, то эта степень веры обязана удовлетворять аксиомам Колмогорова [4]. Вдумайтесь, это очень сильное и строго доказанное утверждение: любой агент, действующий в условиях неопределенности и делающий выводы, нарушающие законы вероятности, обречен на проигрыш даже в очень простой игре! Насколько я знаю, это на данный момент самое убедительный аргумент в пользу теории вероятности (в частности, в пользу ее использования в семантических технологиях, мы же хотим, чтобы наши агенты были рациональными, верно?)

Статистические и субъективные аксиомы в OWL

Возможно кому-то покажется, что я зря потратил столько времени, на рассмотрение этого примера с точки зрения разных толкователей вероятности. Тем не менее, если перед нами стоит задача поддерживать вероятностные расширения как аксиом TBox (т.е. утверждений о классах), так и ABox (утверждений об объектах), то необходимо формулировать их семантику с учетом различий в интерпретации. Иначе есть риск того, что результаты вероятностного логического вывода будут либо слишком слабыми (т.е. агент не сможет получить достаточно информации), либо некорректными с точки зрения законов вероятности.

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

Начнем с семантики аксиом TBox. В  OWL они представляют собой утверждения вида SubClassOf(A B) с интерпретацией "множество объектов A является подмножеством объектов В". В P-OWL мы расширим их до вида SubClassOf(A B)[p], где "p" - это вероятность утверждения. По аналогии с летающими птицами интерпретация будет следующей:

  • Отношение числа экземпляров А, которые также являются экземплярами В, к общему числу экземпляров А есть p.

Обратите внимание, что это отнюдь не эквивалентно интерпретации, "p - это вероятность того, что А - это подкласс В". Очевидно, что если существует хотя бы один экземпляр А, который не является членом В (т.е. птица, которая не летает), то А - это не подкласс В (т.е. вероятность этого 0). Аналогично, если все экземпляры А являются экземплярами В, то А - подкласс В (вероятность 1). Другим корректным вариантом интерпретации будет следующий:

  • Случайно выбранный экземпляр А с вероятностью p будет экземпляром В.

Стандартную семантику OWL достаточно просто расширить, чтобы учитывать эту статистическую вероятность. Как вы помните из статьи о формальных основах, интерпретация в OWL состоит из двух компонентов - домена (или области определения - Dom) и интерпретирующей функции I. I отображает каждый класс на подмножество Dom (т.е. явно указывает какие объекты в домене принадлежат данному классу). Все что требуется для формализации статистической вероятности - это добавить третий компонент - функцию распределения вероятности P на Dom. Грубо говоря, для каждого объекта в домене х, Р(х) будет характеризовать вероятность того, что при случайном выборе одного объекта из всего домена, этим объектом будет именно х.
Далее можно определить вероятность класса - Р(С). Она будет показывать вероятность того, что случайно выбранный объект из всего домена, окажется экземпляром С. Например, Р(Bird) - это вероятность того, что случайно взятый объект реального мира является птицей.
Теперь осталось сделать предпоследний шаг к формализации SubClassOf(A B)[p]. Определим условную вероятность P(D|C) (т.е. вероятность того, что случайный объект будет экземпляром D если известно, что он является экземпляром C) как отношение P(D \and C)/P(C). Как известно D \and C - это класс (пересечение D и C), поэтому его вероятность четко определена выше, как и P(C).
Теперь мы может интерпретировать аксиомы вида SubClassOf(A B)[p] как P(D|C) = p. Например, аксиома SubClassOf(Bird, FlyingObject)[0.9] интерпретируется как "случайно выбранный объект класса Bird является экземпляром FlyingObject с вероятностью p". Другими словами, "случайно выбранная птица летает с вероятностью 90%". Т.е. именно то, что соответствует интуитивному представлению о смысле утверждения "Птицы летают с вероятностью 90%" (см. обсуждение предыдущей статьи). Вуаля.

Субъективная семантика и возможные миры

К сожалению с утверждениями вида ClassAssertion(tweety, Bird)[0.9] дело обстоит куда сложнее. Функция распределения вероятности на домене никак не поможет нам формализовать семантику этого утверждения в желаемой форме (а именно, "Объект tweety является экземпляром класса Bird с вероятностью 0.9"). Интерпретацией tweety будет единственный объект домена - I(tweety), который либо принадлежит I(Bird), либо нет, третьего не дано.
Вместо этого следует определить субъективную интерпретацию утверждения. Для этого было предложено использовать понятие возможных миров (possible worlds) или состояний (states), которые хорошо изучены в модальной логике (modal logic). Что же такое "мир"? Выражаясь неформально, мир - это один из возможных вариантов интерпретирования классов, свойств и объектов, принятый некоторым агентом (или группой агентов). Рассмотрим пример онтологии, содержащей класс "Ключ". В мире одного агента интерпретацией этого класса будет множество объектов, предназначенных для открывания дверей. В мире другого агента интерпретацией будет множество родников (я специально взял пример с омонимами, однако ничто не мешает создать агента, в чьем мире интерпретацией "Ключ" будет множество, скажем, летающих объектов). С некоторыми оговорками можно считать, что мир агента - это то, как он "понимает" классы, объекты и свойства (те из вас, кто знаком с модальной логикой, несомненно проведут параллель с известной структурой Крипке - Kripke structure - она, как правило, используется для задания семантики в МЛ).
Возвращаясь к примеру с Твити, главным является то, что в одних мирах Твити может быть птицей, а в других - нет. Более того, если нам удастся зафиксировать множество миров, то можно будет выбирать их случайным образом и проверять, является Твити птицей или нет. Другими словами, миры возвращают нам понятие эксперимента, которого нам так не хватало, чтобы определить, что же является вероятностью в случае с Твити!
Мы сделаем это чуть позже, а пока введем множество миров в интерпретацию в P-OWL. Т.е. к паре <Dom,I> добавляется третий компонент - W (множество миров). W еще часто называют индексным множеством, т.к. миры выступают в роли своеобразного индекса для интерпретирующей функции (т.е. в мире 1 интерпретирующая функция принимает вид I_1, в мире 2 - I_2 и т.д.). Последним компонентом будет выступать, разумеется, функция распределения вероятности, однако определена она будет не на домене, как ранее, а на множестве миров W. Она будет показывать насколько вероятен тот или иной мир с субъективной точки зрения некоторого агента (опять же, как именно он будет определять свою степень веры в тот или иной мир, в данном случае не так важно. Например, если он знает, что всего 2 мира, причем 9 агентов придерживаются мира 1, а один агент - мира 2, то его вера в мир 1 будет 0.9, а в мир 2 - 0.1. Это лишь один из вариантов).
Этого достаточно, чтобы сформулировать семантику для многострадальной аксиомы ClassAssertion(tweety, Bird)[0.9]. Это делается следующим образом:

  • Суммарная вероятность тех миров, в которых Твити обозначает экземпляр класса Птица, равна 0.9.

Например, если существует 10 миров, у нашего агента нет никаких предпочтений (т.е. степень его веры в каждый из них составляет 0.1), а Твити является птицей в 9 из них, то субъективная вероятность того, что Твити - птица, равна 90%. Можно провести следующую грубую аналогию: наш агент не знает, что такое Твити. Но из 9 источников он узнал, что Твити - птица, а из одного - что Твити - не птица. Если агент доверяет всем источникам в равной мере, то его субъективная вероятность в том, что Твити - птица, будет составлять 90%
Остается последняя трудность: необходимо конкретизировать, что понимается под мирами в семантике P-OWL, так как без этого мы не сможем вычислять вероятности в процессе логического вывода. Здесь нет единого подхода и в разных логиках могут использоваться разные понятия миров. Например, можно считать, что любой способ интерпретирования классов, свойств и объектов, который не противоречит онтологии, является миром. Другими словами, миры отождествляются с моделями онтологии (см. заметку о формальных основах OWL, если вы забыли, что такое модель), т.е. если продолжать аналогию миров и агентов, то существует столько разных "точек зрения" на онтологию, сколько их в принципе может быть. Трудность этого варианта заключается в том, что в общем случае число моделей (возможных интерпретаций) может быть бесконечно. Разумеется, ничто не мешает определить функцию распределения вероятности на бесконечном множестве, однако с логическим выводом будут некоторые чисто практические сложности.

Заключение

Целью этой заметки было показать, что неоднозначности в семантике (смысле) неопределенных знаний возникают даже при рассмотрении только одного типа неопределенности, а именно - вероятностной неопределенности. Семантические теории, позволяющие интерпретировать неопределенные знания, значительно сложнее "классических" теорий и далеко не всегда легко сделать выбор в пользу одной из альтернатив.
Дополнительные проблемы возникают при желании сочетать в одном языке (P-OWL) разные виды утверждений, которые интерпретируются разными структурами (Dom, I, P) в одном случае и (Dom, I_w, W, P) в другом. Я намеренно опустил обсуждение этих моментов в этой статье, так как применительно к OWL (точнее DL) это еще никогда не было сделано. Подобная комбинированная семантика была сформулирована для вероятностной логики первого порядка, которую можно теоретически перенести на P-OWL (я над этим сейчас работаю). Пока же единственная реализация вероятностного логического вывода для OWL в стиле, описанном в этой статье (мой проект Pronto), выполнена исключительно на основе миров, т.е. даже статистические утверждения интерпретируются при помощи распределения вероятности по мирам. Это приводит к некоторым странным эффектам.
Наконец, еще одной проблемой (last but not least!) является вычислительная сложность. Известно, что логический вывод в OWL в худшем случае имеет более чем экспоненциальную сложность (класс NEXPTIME), что уже очень плохо. К счастью, оптимизации современных логических процессоров позволяют сводить число таких "худших случаев" к минимуму. Добавление вероятностей еще повышает сложность (в худшем случае в exp(|W|) раз, где |W| - это число миров). При этом вопросы оптимизации остаются по большей части открытыми.
Во многом все эти неоднозначности и проблемы вычислительной сложности и являются главными причинами того, что расширения OWL, направленные на представление и обработку неопределенных знаний, пока не рассматриваются в качестве кандидатов на стандартизацию. Споры ведутся даже о том, что является оптимальной семантикой вероятностных утверждений, не говоря уже о реализации логических процессоров и т.д. Надеюсь, что этот очерк хоть немного приоткрывает завесу тайны над этими проблемами (хотя бы в плане их существования, а не решения).
Пока это все. Если тема продолжит вызывать интерес, то в следующей заметке я подробно расскажу о Pronto, а именно о том, как он соответствует общей теории и покажу его возможности на примерах.

Заранее спасибо за комментарии!

Литература

1. OWL 2 Functional Syntax, http://www.w3.org/TR/owl2-syntax/
2. Interpretations of Probability, http://plato.stanford.edu/entries/probability-interpret/
3. Аксиоматика Колмогорова, http://ru.wikipedia.org/wiki/%D0%90%D0%BA%D1%81%D0%B8%D0%BE%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_%D0%9A%D0%BE%D0%BB%D0%BC%D0%BE%D0%B3%D0%BE%D1%80%D0%BE%D0%B2%D0%B0
4. Dutch Book Argument, http://plato.stanford.edu/entries/probability-interpret/#SubPro