РАСПРОСТРАНЕНИЕ ВЕРОЯТНОСТНЫХ МЕТОДОВ НА ПРЕДСТАВЛЕНИЯ В ЛОГИКЕ ПЕРВОГО ПОРЯДКА
Поэтому мы должны умерить наши амбиции, по крайней мере, на время. В частности, определим ограниченный язык, для которого интересующими становятся только модели, количество которых является конечным. Для этого можно использовать несколько способов. В этом разделе будут описаны реляционные вероятностные модели, или RPM (Relational Probability Model), идея которых заимствована из семантических сетей (см. главу 10) и из объектно-реляционных баз данных. Другие подходы обсуждаются в библиографических и исторических заметках в конце настоящей главы.
Модели RPM допускают использование константных символов, которыми именуются объекты. Например, допустим, что Prof Smith— имя профессора, г Jones— имя студента. Каждый объект представляет собой экземпляр некоторого класса; например, Prof Smith относится к классу Professor (Профессор), Jones — к классу Student (Студент). Предполагается, что класс каждого константного символа известен.
Применяемые нами функциональные символы будут подразделяться на два типа. Функции первого типа, простые функции, отображают объект не на другой структурированный объект, а на некоторое значение из фиксированной области значений, полностью аналогично случайной переменной. Например, значениями функций Intelligence (Jones) (Интеллект Джонса) и Funding (Prof Smith) (Финансирование профессора Смита) могут быть hi (высокий) или 2о (низкий), а значениями функций Success (Jones) (Успех Джонса) и Fame(ProfSmith) (Известность профессора Смита) могут быть true (истинный) или false (ложный). Функциональные символы не должны применяться к таким значениям, как true и false, поэтому вложение простых функций невозможно. Это позволяет исключить один из источников бесконечных ветвлений. Значение простой функции, применяемое к конкретному объекту, может быть наблюдаемым или неизвестным; для нашего представления эти значения будут служить значениями основных случайных переменных8.
Допускается также использование сложных функций, которые отображают объекты на другие объекты. Например, значением функции Advisor (Jones) (Консультант Джонса) может быть ProfSmith. Каждая сложная функция имеет заданную область определения и диапазон значений, которые являются классами. Например, областью определения функции Advisor является Student, а диапазоном значений — Professor. Функции применяются только к объектам соответствующего им класса; например, значение консультанта Advisor для Prof Smith не определено. Сложные функции могут вкладываться, например значением выражения DeptHead(Advisor(Jones) ) может быть ProfMoore. На данный момент предполагается, что для всех константных символов значения всех сложных функций известны. Поскольку база знаний является конечной, из этого следует, что каждая цепочка применений сложных функций приводит к получению одного объекта из конечного множества объектов9.
Последним необходимым нам элементом является вероятностная информация. Для каждой простой функции задается множество родительских объектов, так же, как и в байесовских сетях. Родительскими объектами могут быть другие простые функции от того же объекта; например, финансирование (Funding) некоторого профессора (Professor) может зависеть от его известности (Fame). Кроме того, родительские объекты могут быть простыми функциями от связанных объектов, например, успех (Success) студента может зависеть от его интеллекта (Intelligence) и от известности (Fame) консультанта этого студента. По сути подобные высказывания представляют собой утверждения о родительских объектах всех объектов в классе с квантором всеобщности. Таким образом, можно записать следующее:
Vx х Е Student =>
Parents(Success(х)) = {Intelligence(x),Fame{Advisor(x))}
(При менее формальном подходе можно нарисовать диаграммы, подобные приведенной на рис. 14.10, а.) Теперь определим распределение условных вероятностей для дочернего объекта, если даны значения его родительских объектов. Например, можно сформулировать следующее утверждение:
Vx х G Student =>
Как и в семантических сетях, распределение условных вероятностей можно закрепить за самим классом так, чтобы его экземпляры наследовали зависимости и условные вероятности от этого класса.
В семантике для языка RPM подразумевается, что каждый константный символ ссылается на отдельный объект; в этом состоит предположение об уникальности имен, описанное в главе 10. С учетом этого определения и ограничений, перечисленных выше, можно показать, что каждая модель RPM вырабатывает фиксированное конечное множество случайных переменных, причем каждая из них является результатом применения простой функции к константному символу. Таким образом, при условии, что родительско-дочерние зависимости являются ациклическими, можно составить эквивалентную байесовскую сеть. Это означает, что модель RPM и
P(Success(x)=true I Intelligence(x)=hi,Fame(Advisor(x))=true) = 0.95
байесовская сеть задают идентичные вероятности для каждого возможного мира. На рис. 14.10, б показана байесовская сеть, соответствующая модели RPM, приведенной на рис. 14.10, а. Обратите внимание на то, что связи Advisor, имеющиеся в модели RPM, в байесовской сети отсутствуют. Это связано с тем, что такие связи являются фиксированными и известными. Однако они присутствуют в топологии сети неявно, например, объект Success (Jones) имеет в качестве родительского объект Fame(ProfSmith), поскольку значением функции Advisor {Jones) является Prof Smith. Вообще говоря, отношения, которые имеют место между объектами, определяют характер зависимостей между свойствами этих объектов.
Для повышения выразительной мощи моделей RPM применяется несколько способов. В частности, могут быть разрешены рекурсивные зависимости между переменными, позволяющие представить несколько типов зависимостей, которые ссылаются сами на себя. Например, предположим, что склонность к питанию всухомятку вызвана фактором McGene. В таком случае для любого х истинность выражения McGene(x) зависит от McGene (Father (х) ) и McGene (Mother (х) ), которые, в свою очередь, зависят от McGene (Fa ther (Fa ther (x) ) ), McGene (Mo ther (Fa ther (x) ) ), и т.д. Даже несмотря на то, что такие базы знаний соответствуют байесовским сетям с бесконечно большим количеством случайных переменных, иногда решения могут быть получены на основе уравнений с неподвижной точкой (fixed-point equation). Например, равновесное распределение вероятностей для генетического фактора McGene можно рассчитать на основе условной вероятности наследования этого фактора. Еще одно очень важное семейство рекурсивных баз знаний состоит из временнб/х вероятностных моделей, которые описаны в главе 15. В этих моделях свойства рассматриваемого состояния во время t зависят от свойств этого состояния во время fc-1 и т.д.
Модели RPM могут быть также расширены, чтобы в них можно было представить реляционную неопределенность, т.е. неопределенность, касающуюся значений сложных функций. Например, в базе знаний может отсутствовать информация о том, кто является консультантом Джонса, Advisor (Jones). В таком случае Advisor (Jones) становится случайной переменной с возможными значениями ProfSmi th и Pro fMoore. Соответствующая сеть показана на рис. 14.11.
Модели RPM позволяют также представить такое свойство, как неопределенность идентичности (identity uncertainty); например, в базе знаний может отсутствовать информация о том, что Магу и ProfSmi th — одно и то же лицо. При наличии свойства неопределенности идентичности количество объектов и высказываний в разных возможных мирах может изменяться. В мире, где Магу и ProfSmi th — одно и то же лицо, количество объектов меньше, чем в том мире, где они считаются разными людьми. В результате этого процесс вероятностного вывода усложняется, но основные принципы, установленные в уравнении 14.12, все еще соблюдаются: вероятность любого высказывания вполне определена и может быть рассчитана. Свойство неопределенности идентичности является особенно важным для роботов и встроенных систем датчиков, которые должны следить за многими объектами. Мы вернемся к описанию этой проблемы в главе 15.
Теперь рассмотрим проблему вероятностного вывода. Очевидно, что такой вывод может осуществляться в эквивалентной байесовской сети при условии, что язык RPM будет ограничен таким образом, чтобы эквивалентная сеть была конечной и имела фиксированную структуру. Такой подход аналогичен способу, с помощью которого логический вывод в логике первого порядка может быть выполнен посредством логического вывода в пропозициональной логике по эквивалентной пропозициональной базе знаний (см. раздел 9.1). Но, как и в случае логического вывода, эквивалентная сеть может оказаться слишком большой для того, чтобы существовала возможность ее построить, не говоря уже о том, чтобы выполнять в ней вычисления. Кроме того, при этом возникает проблема плотных взаимосвязей (см. упр. 14.12). Поэтому для вероятностного вывода на основе модели RPM очень полезными являются приближенные алгоритмы, такие как МСМС (см. раздел 14.5).
В ходе применения алгоритма МСМС к байесовской сети, которая эквивалентна простой базе знаний RPM без реляционной неопределенности или неопределенности идентичности, алгоритм формирует выборки из пространства возможных миров, определяемых значениями простых функций, заданных на объектах. Можно легко показать, что такой подход может быть также дополнен с учетом реляционной неопределенности или неопределенности идентичности. В таком случае переход между возможными мирами способен привести к изменению значения простой функции или сложной функции и поэтому вызвать изменение структуры зависимостей. Кроме того, переходы могут стать причиной изменения отношений идентичности между константными символами. Поэтому создается впечатление, что алгоритм МСМС представляет собой изящный способ осуществления вероятностного вывода на основе весьма выразительных вероятностных баз знаний в логике первого порядка.
Исследования в этой области все еще находятся на ранних этапах, но уже стало очевидно, что вероятностные рассуждения в логике первого порядка позволяют достичь колоссального повышения эффективности применения систем искусственного интеллекта для обработки неопределенной информации. К числу потенциальных приложений относятся машинное зрение, обработка естественного языка, выборка информации и оценка ситуаций. Во всех этих областях множество объектов (и поэтому множество случайных переменных) заранее не известно, поэтому "чисто пропозициональные" методы, такие как байесовские сети, не способны полностью представить ситуацию. Была предпринята попытка расширить возможности таких сетей с помощью метода поиска в пространстве моделей, но подходы, основанные на использовании моделей RPM, обеспечивают формирование рассуждений об указанных видах неопределенности в рамках одной модели.