Факты и правила в семантической сети

Рассмотренные выше отношения, записанные в виде субъект — предикат — объект, представляют собой неизменные знания, т. е. факты. Занесение всех известных фактов о каждом объекте может потребовать неоправданно много времени. В качестве примера уместно привести родственные отношения. Для любых двух родственников есть название отношения между ними: дядя-племянник, свекровь-зять и т. п. Таким образом, для семьи из п = 10 человек число отношений будет равно п* (п — 1) = 90. При этом часть отношений являются первичными (супруг-супруга и родитель-ребенок), остальные отношения вытекают из первичных. Если информацию о том, как вторичные отношения определяются на основе первичных, записать в виде правил, то для каждого объекта можно заносить в базу знаний только первичные факты. Для семейных отношений это означает сокращение, не менее, чем, в n/З раз, если считать, что каждый член семьи является чьим-то ребенком и родителем, а также чьим-то супругом, и не более того.

Одним из стандартов языка представления правил является SWRL — Semantic Web Rule Language (http://www.w3.org/ Submission/SWRL/). Данный язык является расширением XML, и конструкции на нем предназначены исключительно для машинной интерпретации. Редакторы правил обычно предоставляют вариант «human readable» правил в формате, подобном правилам на Прологе, для их создания и отладки. Ниже приведен фрагмент правила определения отношения «дядя» для чтения человеком и исходный текст данного правила на языке SWRL.

hasParent (?xl, ?х2) л hasBrother (?х2, РхЗ) => hastlncle.

(?xl, РхЗ).

" #hasBrother" />

Устанавливая правила для объектов семантической сети, мы можем столкнуться с проблемой открытого или закрытого мира (Open or Closed World Assumption). Допущение об открытом мире предполагает, что никто не располагает полной информацией об окружающем мире, следовательно, выводы должны делаться исключительно на основании того, что известно. Допущение о закрытом мире предполагает, что вся информация известна наблюдателю. В качестве примера можно привести родственное отношение типа «мачеха». Пусть в базе знание имеются следующие факты:

Андрей является родителем Егора.

Юлия является супругой Андрея.

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

Применение правил крайне полезно в тех случаях, когда в базе знаний содержится неполная информация. Пусть, например, в предыдущем примере указано, Андрей — это человек, но нет сведений, что Юлия — человек. Тогда все правила наподобие.

Если X человек, то X имеет фамилию

не смогут быть применены к Юлии. Если же создать правило.

Если X человек И X супруг YTOY человек

то можно будет установить факт, что Юлия тоже человек. Помимо положительного эффекта от использования правил имеется и недостаток: комбинаторная сложность, которая по мере увеличения объема базы знаний довольно быстро вырастает до космических масштабов. Так, например, если в достаточно маленькой базе знаний имеется 100 фактов и 10 правил по три факта в каждом, то общее количество попыток применить правила к фактам может достигать значения 10 * 100 * 100 * 100 = 10⁷, поскольку в каждое правило последовательно будут подставляться все возможные факты. Очевидно, что такая «наивная реализация» поиска в семантической сети нежизнеспособна. Как в любой задаче поиска, здесь нужно решать проблему сокращения комбинаторной сложности. В качестве примера ускорения обработки правил можно привести алгоритм Rete (Рити) (http://en.wikipedia. org/wiki/Rete_algorithml), основной смысл которого заключается в том, что строится дерево, каждый узел которого соответствует части условий правил и хранит список фактов, удовлетворяющих этим условиям. Поскольку в ходе применения правил постоянно возникают новые факты, они прогоняются по сети, и списки фактов при вершинах обновляются. Узким местом алгоритма Rete является большой требуемый объем памяти, поскольку одни и те же факты многократно дублируются в списках при вершинах графа.

В качестве одного из альтернативных путей решения можно запускать все возможные правила для каждого документа один раз и сохранять результаты в виде фактов. Для базы родственных связей это будет означать, что в документ вначале заносятся только первичные связи (родители-дети и супруги), затем из них вычисляются все опосредованные отношения (внучатные племянники и т. д.), которые на равных правах затем пополняют базу знаний. После этого все факты будут извлекаться одинаково быстро. Такой подход является разновидностью вывода на основе прецедентов (Case based reasoning), и его можно считать аналогом навыков в человеческом интеллекте. На самом деле, мы почти всегда действуем по аналогиям, например, в устной речи. Если бы мы при построении каждой фразы применяли правила языка, то скорость речи не превышала бы нескольких предложений в час. Это особенно заметно, когда мы переводим русский текст на иностранный язык. Если языковая конструкция нам знакома (многократно использовалась ранее), то перевод идет в быстром темпе. Если мы создаем предложение в первый раз, то процесс перевода замедляется в десятки и сотни раз.