Министерство образования и науки российской федерации федеральное агентство по образованию санктпетербургский государственный университет
 Скачать 1.41 Mb.
|
|
«ВЕРНО ЛИ, ЧТО женская особь животного имеет молочные железы?» Если пользователь ответит утвердительно, то факт «животное относится к классу млекопитающих» считается установленным (для простоты не будем рассматривать ситуацию, когда мы встретили самца). После этого правило для определения леопарда требует установить, является ли животное хищником. Установить это факт достоверно можно только будучи съеденным, поэтому, из гуманных соображений, в базу знаний помещено правило: «ЕСЛИ животное имеет когти ИЛИ животное имеет клыки ТО животное относится к виду хищников» Пользователь не увидел ни клыков, ни когтей, а напротив, заметил копыта. Следовательно, гипотеза «леопард» отвергается, и экспертная система переходит к проверке следующей гипотезы «зебра». Факт «млекопитающее» уже установлен, и теперь нужно установить, относится ли животное к виду травоядных. Соответствующее правило выглядит следующим образом: «ЕСЛИ животное имеет рога ИЛИ животное имеет копыта, ТО животное относится к виду травоядных». Экспертная система сначала задаст вопрос: «ВЕРНО ЛИ, ЧТО животное имеет рога?» Пользователь отвечает отрицательно, а поскольку условия в данном правиле связаны операцией ИЛИ, задается следующий вопрос: «ВЕРНО ЛИ, ЧТО животное имеет копыта?» Пользователь отвечает утвердительно, следовательно, факт «животное относится к виду травоядных» считается установленным. Для проверки гипотезы «зебра» остается проверить последнее условие: «ВЕРНО ЛИ, ЧТО животное имеет черные и белые поперечные полосы?» Если полосы имеются, то гипотеза «зебра» подтверждается, а задача, поставленная перед экспертной системой, считается выполненной. Рис.6.1 содержит фрагмент простой экспертной системы, реализованной в среде VISIRULE, разработанной компанией LPA ( http://lpa.co.uk ). 67 Рис.6.1. Пример представления правил Основное требование к проектированию экспертных систем заключается в том, что пользователю должны задаваться такие вопросы, на которые он в состоянии ответить. Иными словами, экспертная система преобразует знания пользователя в знания эксперта. В приведенном выше примере идентификации животных явно неудачным вопросом является вопрос о молочных железах (особенно, если речь идет о случайно встреченном нами леопарде). Вместо него следует использовать правило: «ЕСЛИ животное имеет волосяные покровы ТО животное относится к классу млекопитающих» Другим важным свойством экспертной системы является способность объяснить, как был получен тот или другой вывод, что является лучшим подтверждением истинности полученного вывода. Если вспомнить рассказы А. Конан-Дойла, то нас, как и доктора Ватсона вывод вначале любой Шерлока Холмса кажется парадоксальным и выдуманным, но после объяснения, как этот вывод был сделан, мы удивляемся, что сами об этом не догадались. Экспертные системы используются в самых различных областях знаний, в том числе в медицине (диагностика и лечение), геологоразведке (определение перспективности месторождений), химии (прогнозирование свойств органических соединений). В последнее время экспертные системы активно используются в Интернет-торговле для помощи покупателям в выборе товара. Наиболее известной является экспертная система ГУРУ на Яндексе ( http://market.yandex.ru/guru-categories.xml ), которая заменяет квалифицированного продавца-консультанта по самому широкому перечню товаров. 68 7. Семантические сети 7.1. Определение Семантическая сеть - структура для представления знаний с помощью графа, в виде узлов, соединенных дугами. Узлы соответствуют понятиям, а дуги – отношениям между ними. Элементом семантической сети в простейшем случае является триплет следующего вида: Одно и то же понятие может присутствовать в нескольких триплетах, что и обуславливает сетевую структуру. Основным свойством семантических отношений является арность, т.е. количество аргументов. Выше приведен пример бинарного отношения, т.е. отношения с арностью 2. Если все отношения в сети однотипные, то сеть называется однородной. Пример однородной сети – классификация биологических видов. В неоднородной сети количество типов отношений больше одного. Основная цель применения семантических сетей для представления знаний – обеспечение независимости от языка, а также устранение неточностей и двусмысленностей, свойственных естественным языкам. Естественный язык – как живой организм, развивается и эволюционирует в сторону совершенствования основной своей цели – обеспечения понимания участников разговора. Однако, в силу природной лени носителей языка, эта оптимизация зачастую сводится к предельному упрощению конструкций, в результате чего смысл отдельной фразы выявить можно только из контекстного окружения. Хрестоматийный пример даже не двусмысленности, а «трехсмысленности» являет фраза «Он встретил ее на поляне с цветами». Совершенно непонятно, где цветы: у него, у нее или на поляне. От неоднозначности страдают все языки, включая английский. Так, вопрос “Tell me, what has four wheels and flies” заставляет нас вспомнить, какой летательный аппарат имеет четыре колеса. Речь при этом идет о “garbage truck”, и «flies» означает «мухи», а не «летает». Семантическая же сеть должна содержать знания в математически точной форме. 7.2. Историческая справка Математика позволяет описать большинство явлений в окружающем мире в виде логических высказываний. Семантические сети возникли как попытка визуализации математических формул. Прародителями современных семантических сетей можно считать экзистенциальные графы, предложенные Чарльзом Сандерзом Пирсом в 1909г. Они использовались в органической химии для представления логических высказываний в виде особых диаграмм. Пирс назвал этот способ «логикой будущего». субъект объект предикат 69 Важным начинанием в исследовании сетей стали работы немецкого психолога Отто Зельца 1913 и 1922гг. В них для организации структур понятий и ассоциаций, а также изучения методов наследования свойств он использовал графы и семантические отношения. Научные изыскания Зельца имели огромное влияние на изучение тактики в шахматах, которые в свою очередь повлияли на таких теоретиков, как Саймон и Ньюэлл. Исследователи Дж. Андерсон (1973), Д. Норман (1975) и другие использовали эти работы для моделирования человеческой памяти и интеллектуальных свойств. Что касается лингвистики, то первым ученым, занимавшимся разработкой графических описаний, стал Теньер. Он использовал графическую запись для своей грамматики зависимостей. Теньер существенно повлиял на развитие лингвистики в Европе. Компьютерные семантические сети были детально разработаны Ричардом Риченсом в 1956 году в рамках проекта Кембриджского центра изучения языка по машинному переводу. Процесс машинного перевода подразделяется на 2 части: перевод исходного текста в промежуточную форму представления, а затем эта промежуточная форма транслируется на нужный язык. Такой промежуточной формой как раз и были семантические сети. Первая такая система, которую создала Мастерман, включала в себя 100 примитивных концептов таких, как, например, НАРОД, ВЕЩЬ, ДЕЛАТЬ, БЫТЬ. С помощью этих концептов она описала словарь объемом 15000 единиц, в котором также имелся механизм переноса характеристик с гипертипа на подтип. Некоторые системы машинного перевода базировались на корреляционных сетях Цеккато, которые представляли собой набор 56 различных отношений, некоторые из которых - падежные отношения, отношения подтипа, члена, части и целого. Он использовал сети, состоящие из концептов и отношений для руководства действиями программы текстового разбора и разрешения неоднозначностей. Эти исследования были продолжены Робертом Симмонсом (1966), Уилксом (1972) и другими учёными [4]. В системах искусственного интеллекта семантические сети используются для ответа на различные вопросы, изучение процессов обучения, запоминания и рассуждений. В конце 70-х сети получили широкое распространение. В 80-х годах границы между сетями, фреймовыми структурами и линейными формами записи постепенно стирались. Выразительная сила больше не является решающим аргументом в пользу выбора сетей или линейных форм записи, поскольку идеи, записанные с помощью одной формы записи, могут быть легко переведены в другую. И наоборот, особо важную роль стали играть такие е факторы, как читаемость, эффективность, неискусственность и теоретическая элегантность, также учитываются легкость введения в компьютер, редак- тирование и распечатка [5]. На понимание проблем представления знаний с помощью семантических сетей большое влияние оказало эссе Дрю МакДермота «Искусственный интеллект сталкивается с естественной глупостью» [6], которое цитируется уже в течение 30 лет. Наиболее продвинутой отечественной разработкой в области применения 70 аппарата семантических сетей в задачах анализа и поиска текстовой информации является набор программных продуктов под торговой маркой RCO (Russian Context Optimizer) компании «Гарант Парк Интернет» ( www.rco.ru ). Наконец, следует упомянуть концепцию Семантической Паутины (Semantic Web), которая будет подробнее рассмотрена в подразд. 7.7 и 7.8. Семантическая Паутина – это дальнейшее развитие Всемирной паутины, заключающееся в том, что документы, размещаемые на ее ресурсах, содержат семантическую разметку, позволяющую извлечь смысл информации, содержащейся в этих документах. Такие семантические документы создаются, в основном, в формате RDF (Resource Description Framework) – расширении языка XML, дополненном средствами представления триплетов субъект- предикат-объект. 7.3. Типы семантических сетей Семантическая сеть, в которой все отношения бинарные, образует реляционный граф (рис. 7.1.). Рис.7.1. Пример реляционного графа Несмотря на то, что понятия “Larry Smith” и “Man” обозначаются на графе одинаковыми эллипсами, их смысловое качество различно. “Larry Smith” – экземпляр класса мужчин, а “Man” – множество мужчин. В свою очередь, “Man” и “Woman” являются подмножествами более мощного множества людей (“Person”). Таким образом, как и в реляционных базах данных, здесь имеют место отношения «один к одному», «один ко многим», «многие к многим». Если арность отлична от двух, изобразить семантическую сеть в виде графа уже сложнее. Но, как и в базах данных, можно провести нормализацию и привести все к бинарным отношениям. Например, унарное отношение типа «мотор – работает» можно привести к виду «мотор» -> «состояние» -> «работа». Отношение с арностью 3 типа «Самолет летит из Петербурга в Москву» оперирует с тремя понятиями: субъект – это самолет, а объекты – Москва и Петербург. Предикат – выполнение полета («летит»). Введя дополнительное понятие «полет», данное отношение можно представить a_kind_of a a_kind_of is_a husband wife Larry Smith Man Person Mammal a_kind_of is_a Laura Smith Woman 71 следующим фрагментом семантической сети (рис.7.2): Рис. 7.2. К определению концептуального графа Во многих случаях в качестве понятия в отношении участвует не простой объект или субъект, а другое отношение или целый фрагмент семантической сети. Например, мальчик видит в небе самолет и думает, что этот самолет летит из Петербурга в Москву. Рис.7.3. Концептуальный граф Такие сети называются пропозиционными сетями, а граф такой сети – концептуальным графом (рис.7.3). Вложенность отношений в пропозиционных сетях может быть сколь угодно велика. Например, родители мальчика могут полагать, что он ошибается, если думает, что самолет летит из Петербурга в Москву, а их дедушка и бабушка, в свою очередь, могут считать, что родители недооценивают дедуктивные способности внука и т.д. Для представления событий более подходит граф с глаголом в центре или граф Растье. Пример: Собака кусает почтальона (рис.7.4). Рис.7.4. Граф Растье Почтальон Кусать Собака Агент Объект думает в из выполняет Самолет полет Петербург Москва Мальчик в из выполняет Самолет полет Петербург Москва 72 В основе лежит не понятие, а действие или событие, в данном случае кусание. Субъектом или агентом кусания является собака, а объектом – почтальон. Граф с центром в глаголе позволяет обходиться без вложенности графов. Мы можем достаточно просто расширить базу знаний о данном событии (рис.7.5): Рис.7.5. Семантическая сеть «Почтальон» Следствием того, что собака свирепо покусала почтальона, стало то, что почтальон поколотил во дворе хозяина собаки. 7.4. Типы отношений в семантических сетях Самым распространенным типом отношений в семантических сетях является иерархический тип, описывающий отношения между элементами, множествами и частями объектов. К ним относятся: 1) отношение классификации ISA (от английского “is a”). Говорят, что множество (класс) классифицирует свои экземпляры (например, “Сократ есть человек”). Иногда это отношение именуют “member of”. По-русски это может называться «есть» (единственное число) или «суть» (множественное число). Обратное отношение – “example of” или «пример». 2) Отношение между множеством и подмножеством AKO (“a kind of”), например, «Магистры подмножество студентов». Отличие от отношения ISA заключается в том, что классификация – отношение «один ко Почтальон Кусать Собака Агент Объект Владеть Объект Агент Хозяин Объект Бить Агент Следствие Место Двор Манера свирепо 73 многим», а подмножество – «много к многим». По-русски – «подмножество» 3) Отношение целого и части. Отношение меронимии – отношение целого к части (“has part”). Мероним – объект, являющийся частью другого объекта. Отношение холонимии – отношение части к целому (“is a part”). Рука – холоним для тела. Тело – мероним для руки. Применяя иерархические типы отношений, следует четко различать, какие объекты являются классами, а какие – экземплярами классов. При этом вовсе не обязательно одно и то же понятие будет классом или экземпляром во всех предметных областях. Так, «человек» всегда будет классом в базах знаний типа «студенческая группа» или «трудовой коллектив», но может быть экземпляром класса млекопитающих в базе знаний по биологии. Вершины семантического графа могут обозначать не только объекты, но и свойства или значения свойств. Отображение свойств на графе повышает его наглядность, но может сильно загромоздить его. Кроме иерархических отношений в семантических сетях часто используются следующие типы отношений (во вторых скобках указаны типы вершин): 1) функциональные связи («производит», «влияет», …) (объект – объект); 2) количественные («больше», «меньше», «равно», …) (объект – объект или объект – свойство); 3) пространственные («далеко от», «близко к», «за», «над», «под», «выше», …) (объект – объект); 4) временные («раньше», «позже», «одновременно с», …) (объект – объект); 5) атрибутивные («иметь свойство», «иметь значение»,…) (объект – свойство или свойство - значение); 6) логические («и», «или», «не») (объект – объект или свойство – свойство); 7) лингвистические. Число типов отношений может быть очень большим. Основная проблема при этом заключается в возможности идентификации этих отношений в запросах к базе знаний. В этой связи предпочтительным является сокращение числа типов связей (и вершин) за счет увеличения числа вершин. Например, вместо отношения «семантсеть» - «предназначена» - «представление_данных» можно использовать «семантсеть» - «имеет» - «назначение»; «назначение» - «есть» - «представление»; «представление» - «чего» - «данных». Сети с глаголом в центре (сети Растье) оперируют со следующими типами связей [5], приведенными в таблице 7.1. Рис. 7.6. содержит граф Растье, описывающий пример с почтальоном, где отношения приведены к стандартной форме. 74 Таблица 7.1. Типы связей в графах Растье Имя Тип Определение Упрощенное имя (ACC) accusative Объект воздействия PATient (ASS) assumptive Точка зрения PERspective (ATT) attributive Свойство, характеристика CHARacteristic (BEN) benefactive Сущность, выступающая в роли выгодоприобретателя BENeficiary (CLAS) classitive Экземпляр класса CLASsitive (COMP) comparative Элементы, объединяемые сравнением COMParison (DAT) dative Получатель RECeiver (ERG) ergative Эргатив, агент процесса или действия AGEnt (FIN) final Результат или ожидаемая цель GOAL (INST) instrumental Использованные средства MEAns (LOC S) spatial locative Положение (позиция) в пространстве SPAce (LOC T) temporal locative Положение (позиция) во времени TIME (MAL) malefactive Сторона, пострадавшая в результате действия MALeficiary (PART) partitive Часть целого PARTitive (RES) resultative Результат, эффект, следствие EFFect (или CAUse) Рис.7.6. Граф Растье со стандартными отношениями почтальон кусать собака ERG ACC владеть ACC ERG хозяин ACC бить ERG RES LOC двор ATT свирепо 75 7.5. Онтологии и правила наследования отношений Представление знаний – весьма сложный и творческий процесс. Основная проблема здесь заключается в том, что создание базы знаний почти всегда начинается «с нуля»; при этом отсутствуют т.н. знания начального уровня, которыми человек обзаводится, начиная с раннего детства. Создание таких баз бытовых знаний ведется уже более 25 лет компанией Cycorp. ( www.cyc.com ), однако, по признанию ее основателя Дагласа Лената (Douglas Lenat), машина все еще нуждается в том, чтобы ей в явном виде сообщали, что родители старше своих детей, и что люди перестают выписывать газеты, когда умирают. Знания конкретной предметной области можно разделить на общие для всех экземпляров и индивидуальные для каждого. Очевидно, что если формализация знаний для класса объектов будет выполнена один раз, то затем она может использоваться другими авторами при описании отдельных экземпляров. Таким образом, формализация знаний любой предметной области должна базироваться на знаниях более общего уровня, описывающих основные отношения между объектами и общие свойства объектов. Такие знания называются онтологиями. Например, онтология для описания класса «человек», может содержать отношения “has part” с объектами «рука», «голова» и свойства «имеет имя», «имеет дату рождения» и т.п. Применение таких знаний к объектам нижнего уровня осуществляется с помощью правил наследования: Если X AKO Y и Y AKO Z то X AKO Z – если X является подмножеством Y, а тот, в свою очередь, частью еще большего множества Z, то класс X является подмножеством Z. Если X ISA Y и Y AKO Z то X ISA Z – если X является экземпляром класса Y, а тот, в свою очередь, частью множества Z, то X является экземпляром класса Z. Если X has_part Y и Y has_part Z то X has_part Z – если X имеет в своем составе Y, а тот, в свою очередь, имеет составную часть Z, то X имеет в своем составе Z. Если X ISA Y и Y has_part Z то X has_part Z – если X является экземпляром класса Y, а тот, в свою очередь, имеет составную часть Z, то экземпляр X имеет в своем составе Z. Если X AKO Y и Y has_part Z то X has_part Z – если X является подмножеством Y, а тот, в свою очередь, имеет составную часть Z, то класс X имеет в своем составе Z. Если X ISA Y и Y has_a Z то X has_a Z – если X является экземпляром класса Y, а тот, в свою очередь, имеет свойство Z, то экземпляр X имеет свойство Z. Если X AKO Y и Y has_a Z то X has_a Z – если X является подмножеством Y, а тот, в свою очередь, имеет свойство Z, то класс X имеет 76 свойство Z. Использование правил наследования позволяет описания всех свойств каждого экземпляра указать лишь принадлежность к классу, для которого все необходимые свойства уже описаны. 7.6. Примеры На рис.7.7 приведен граф семантической сети, воспроизводящий в себе известное стихотворение. Несмотря на исходную рекурсивность конструкции (существует даже программа на языке Prolog, генерирующая текст этого стихотворения), здесь не потребовалась пропозиционная сеть, поскольку все связи укладываются в обычные триплеты: старушка доит корову, а не процесс лягания коровой пса и т.д. Рис.7.7. Граф семантической сети «Дом, который построил Джек» ловит треплет свойство ворует хранится в свойство Дом Джек который построил Пшеница Чулан темный Синица Птица вид свойство веселая Кот пугает Пес без хвоста Корова свойство безрогая лягнула Старушка доит свойство свойство строгая седая 77 Читатель, хорошо знакомый с оригиналом, может отметить, что граф не отражает тот факт, что синица ворует пшеницу ловко, а пес треплет кота за шиворот. Эти факты относятся не к объектам и субъектам, а к процессам или действиям. Синица может быть в целом неуклюжей, ловко только воровать пшеницу, причем не любую, а только ту, «которая в темном чулане хранится…». Ну а «за шиворот» - это не свойство пса или кота, а характеристика процесса трепания. Второе свойство данного графа – статичность. Из графа, как, впрочем, и из текста не следует, что сначала кот ловит синицу, затем его треплет пес. Все эти действия – постоянные во времени, за исключением коровы, которая совершила однократный акт лягания пса, причем безотносительно его манипуляций с котом. Другой пример перевода стихотворного произведения в семантическую сеть более схематичен и всего лишь отражает основной смысл. Для разнообразия возьмем англоязычный вариант (не будем разбираться, кто у кого списал). "The Cicada and the Ant" Jean de La Fontaine (1988) Cicada, having sung her song She said, "I'll pay you everything All summer long, Before fall, my word as animal, Found herself without a crumb Interest and principal." When winter winds did come. Well, no hasty lender is the Ant; Not a scrap was there to find It's her finest virtue by a lot. Of fly or earthworm, any kind. "And what did you do when it was hot?" Hungry she ran off to cry She then asked this mendicant. To neighbor Ant, and specify: "To all comers, night and day, Asking for a loan of grist, I sang. I hope you don't mind." A seed or two so she'd subsist "You sang? Why, my joy is unconfined. Just until the coming spring. Now dance the winter away." Граф на рис.7.8 не воспроизводит художественную сторону произведения, а всего лишь отражает процессы, события и причинно-следственные связи между ними. Так, мы видим, что имеется процесс пения (“Sing”). Агентом (эргативом) пения является цикада, а позицией во времени – лето. Следствием пения цикады летом стало отсутствие пищи (“No food”) и голодание (“Hunger”) зимой (позиция во времени – “Winter”).Объект голодания (“accusative”) – цикада. К сожалению, на графе лето и зима находятся в диаметрально противоположных точках, и факт наступления зимы после лета отразить не удалось. 78 Рис.7.8. Граф Растье для стихотворения "The Cicada and the Ant" Вследствие голода стрекоза пришла (“Go”) к муравью с целью (“Fin”) получить еды (“Food”). Муравей предложил стрекозе плясать (“Dance”) вследствие того, что она пришла к нему, и того, что она пела летом. 7.7. Проблемы построения семантических сетей Как показано в подразд.7.1, семантическая сеть должна хранить знания в математически точной форме. В этой связи, ее построение требует аккуратности и хорошего понимания предметной области и всех связанных с ней понятий. Проблемы представления знаний были изложены в уже упомянутой работе Дрю Макдермота [6]. На первый взгляд, построение графов подобных приведенным в подразд. 7.3. примерам может проходить легко и непринужденно. Однако это далеко не всегда так. Рассмотрим следующую конструкцию: Иными словами, Ту-154 с бортовым номером 85600 является экземпляром имеет свойство Ту-154 б/н 85600 Летать Самолет один из Summer The Cicada ERG LOC T Hunger ACC RES No food Winter LOC T Go ERG DAT The Ant RES FIN Food Offer ERG ACC Dance FIN ERG RES RES RES Sing 79 класса самолетов, а самолеты обладают свойством летать. Поскольку отдельный представитель класса наследует признаки класса, мы делаем вывод, что Ту-154 с бортовым номером 85600 тоже может летать, и будем правы. Но если теперь мы наложим на такую же схему другие факты (очень старый и широко известный парадокс): Сократ – один из людей. Людей много. Следовательно, Сократов много. А ведь в отношении самолета это работало! Мы попали в ловушку по следующей причине. Понятия «Самолеты» и «Люди» - это множества самолетов и людей соответственно. Свойство «летать» относится не к множеству, а к его экземплярам. Свойство же «Многочисленность» относится к классу в целом и неприменимо к отдельным экземплярам данного класса. Таким образом, всегда следует четко понимать, что соответствует тому или иному понятию, единичный экземпляр или подмножество, и правильно применять предикаты. Другая проблема связана с присвоением понятиям имен. В приведенном выше примере с самолетом не зря конкретный самолет был идентифицирован бортовым номером. В противном случае было бы непонятно, какой именно экземпляр самолета имеется в виду. Для выявления свойства «летать» точная идентификация экземпляра не критична, чего нельзя сказать, если речь идет о необходимости устранении неисправности. Приведенная выше идентификация 85600 также не является исчерпывающей. Во-первых, данная комбинация цифр может относиться к чему угодно, например, номеру телефона. Во-вторых, самолет может попасть в гражданскую авиацию из авиации военной, где идентификация совершенно другая, и мы не сможем ничего узнать о прошлой жизни самолета, например, о предыдущих ремонтах, а это совершенно недопустимо. Проблема идентификации понятий имеет место и в реальной жизни, но здесь мы мудро пользуемся «бритвой Оккама»: Не умножай сущностей сверх необходимости. Если мы общаемся в небольшой компании, достаточно имен. В студенческой группе можно идентифицировать каждого фамилией. Однофамильцы при этом удостаиваются имени, а тезки – еще и отчества. Если создается семантическая сеть, охватывающая большое количество объектов, то один из подмножество 85600 Самолет Ту-154 имеет свойство Ту-154 б/н 85600 Летать 80 неизбежно возникает проблема синонимии, когда одно имя указывает на различные понятия. И если в древности достаточно было сказать «Иисус из Назарета», чтобы идентифицировать человека, то сейчас даже используемая в паспортном учете триада «ФИО» - «дата рождения» - «место рождения» не гарантирует отсутствия повторяющихся идентификаторов. Кроме того, такой громоздкий ключ (выражаясь в терминах баз данных) не способствует наглядности и простоте восприятия. В этой связи для локальных семантических сетей могут использоваться принятые в практике номера зачетных книжек, табельные номера, ИНН и т.п. Другая проблема – полисемия, когда одно слово используется для обозначения различных понятий. Синонимия и полисемия могут катастрофически усложнить проблему построения больших сетей и, в частности, объединение фрагментов, написанных разными авторами. Название вершины является всего лишь символическим именем, его осмысленность только увеличивает наглядность графа. Полностью идентифицируют вершину ее свойства, например, для человека – фамилия, имя, отчество, дата рождения и т.п. 7.8. Факты и правила в семантической сети Рассмотренные выше отношения, записанные в виде субъект-предикат- объект, представляют собой неизменные знания, т.е. факты. Занесение всех известных фактов о каждом объекте может потребовать неоправданно много времени. В качестве примера уместно привести родственные отношения. Для любых двух родственников есть название отношения между ними: дядя- племянник, свекровь-зять и т.п. Таким образом, для семьи из n=10 человек число отношений будет равно n*(n-1) = 90. При этом часть отношений являются первичными (супруг-супруга и родитель-ребенок), остальные отношения вытекают из первичных. Если информацию о том, как вторичные отношения определяются на основе первичных, записать в виде правил, то для каждого объекта можно заносить в базу знаний только первичные факты. Для семейных отношений это означает сокращение, не менее, чем, в n/3 раз, если считать, что каждый член семьи является чьим-то ребенком и родителем, а также чьим-то супругом, и не более того. Одним из стандартов языка представления правил является SWRL - Semantic Web Rule Language ( http://www.w3.org/Submission/SWRL/ ). Данный язык является расширением XML, и конструкции на нем предназначены исключительно для машинной интерпретации. Редакторы правил обычно предоставляют вариант “human readable” правил в формате, подобном правилам на Прологе, для их создания и отладки. Ниже приведен фрагмент правила определения отношения «дядя» для чтения человеком и исходный текст данного правила на языке SWRL. hasParent(?x1,?x2) ∧ hasBrother(?x2,?x3) ⇒ hasUncle(?x1,?x3) 81 … Устанавливая правила для объектов семантической сети, мы можем столкнуться с проблемой открытого или закрытого мира (Open or Closed World Assumption). Допущение об открытом мире предполагает, что никто не располагает полной информацией об окружающем мире, следовательно, выводы должны делаться исключительно на основании того, что известно. Допущение о закрытом мире предполагает, что вся информация известна наблюдателю. В качестве примера можно привести родственное отношение типа «мачеха». Пусть в базе знание имеются следующие факты: Андрей является родителем Егора. Юлия является супругой Андрея. В соответствии с допущением закрытого мира, Юлия является мачехой Егора, поскольку в базе нет сведений о том, что она его мать. В открытом мире Юлию можно считать мачехой Егора только в том случае, если известно, что его матерью является не Юлия, а другая женщина. Применение правил крайне полезно в тех случаях, когда в базе знаний содержится неполная информация. Пусть, например, в предыдущем примере указано, Андрей – это человек, но нет сведений, что Юлия – человек. Тогда все правила наподобие Если Х человек, то Х имеет фамилию не смогут быть применены к Юлии. Если же создать правило 82 Если Х человек И Х супруг Y TO Y человек то можно будет установить факт, что Юлия тоже человек. Помимо положительного эффекта от использования правил имеется и недостаток: комбинаторная сложность, которая по мере увеличения объема базы знаний довольно быстро вырастает до космических масштабов. Так, например, если в достаточно маленькой базе знаний имеется 100 фактов и 10 правил по три факта в каждом, то общее количество попыток применить правила к фактам может достигать значения 10*100*100*100 = 10 7 , поскольку в каждое правило последовательно будут подставляться все возможные факты. Очевидно, что такая «наивная реализация» поиска в семантической сети нежизнеспособна. Как в любой задаче поиска, здесь нужно решать проблему сокращения комбинаторной сложности. В качестве примера ускорения обработки правил можно привести алгоритм Rete (Рити) ( http://en.wikipedia.org/wiki/Rete_algorithm ), основной смысл которого заключается в том, что строится дерево, каждый узел которого соответствует части условий правил и хранит список фактов, удовлетворяющих этим условиям. Поскольку в ходе применения правил постоянно возникают новые факты, они прогоняются по сети, и списки фактов при вершинах обновляются. Узким местом алгоритма Rete является большой требуемый объем памяти, поскольку одни и те же факты многократно дублируются в списках при вершинах графа. В качестве одного из альтернативных путей решения можно запускать все возможные правила для каждого документа один раз и сохранять результаты в виде фактов. Для базы родственных связей это будет означать, что в документ вначале заносятся только первичные связи (родители-дети и супруги), затем из них вычисляются все опосредованные отношения (внучатные племянники и т.д.), которые на равных правах затем пополняют базу знаний. После этого все факты будут извлекаться одинаково быстро. Такой подход является разновидностью вывода на основе прецедентов (Case based reasoning), и его можно считать аналогом навыков в человеческом интеллекте. На самом деле, мы почти всегда действуем по аналогиям, например, в устной речи. Если бы мы при построении каждой фразы применяли правила языка, то скорость речи не превышала бы нескольких предложений в час. Это особенно заметно, когда мы переводим русский текст на иностранный язык. Если языковая конструкция нам знакома (многократно использовалась ранее), то перевод идет в быстром темпе. Если мы создаем предложение в первый раз, то процесс перевода замедляется в десятки и сотни раз. 7.9. Интеллектуальный агент семантической сети Построить семантическую сеть – задача непростая. Но после того, как мы с ней справимся, возникнет вопрос, а как извлекать знания из семантической сети? Очевидно, для этой цели должна быть разработана специальная программа, которая на основе запроса пользователя проведет поиск требуемых 83 знаний и выдаст результат. В настоящее время существует несколько языков запросов к базам знаний в виде семантических сетей в формате RDF, в частности, DQL, R-DEVICE, RDFQ, RDQ, RDQL, SeRQL. Наиболее стандартизованным является язык SPARQL, прошедший стандартизацию в группе Data Access Working Group (DAWG) консорциума World Wide Web ( W3C ). Существуют несколько реализаций языка SPARQL для различных программных платформ. Автор протестировал некоторые из них, и оказалось, что запросы на языке SPARQL обрабатывают только факты (триплеты субъект-предикат-объект), но не понимают правил. Тем самым вся работа по созданию онтологий становится бессмысленной. Для устранения этого недостатка автор разработал упрощенный язык представления семантических документов и программу, поддерживающую визуализацию знаний и выполнение простейших запросов. Программа SEMANTIC, предлагаемая в рамках данной дисциплины в качестве оболочки для создания и исследования семантических сетей, содержит зачатки свойств такого интеллектуального агента. В частности, программа применяет ко всем фактам, записанным в базу знаний, правила наследования, а также позволяет пользователю создавать собственные правила. Более подробная информация об этой программе содержится в Приложении 3. 7.10. Управление контекстом Необходимость однозначно идентифицировать все объекты семантической сети приводит не только к усложнению процедуры добавления фактов, но и к тому, что извлечение знаний становится очень громоздким. Упростить понимание этой проблемы можно не простом примере. Пусть мы хотим на денек попросить у соседа конспект лекций по искусственному интеллекту, который он, в свою очередь, одолжил у своей подружки. Тогда диалог будет приблизительно следующим: «Гражданин Российской Федерации Сидоров Владимир Иванович, родившийся в 1985 году в г. Саратове, имеющий паспорт № 60 04 123456, выданный 20.05.2003 51-м ОМ г. Санкт-Петербурга, дай мне, гражданину Российской Федерации Петрову Ивану Викторовичу, родившемуся в 22.04.1986г. в г. Пскове, имеющему паспорт № 6606 654321, на 24 часа 00 минут 00 секунд конспект лекций по дисциплине «Искусственный интеллект», который читает к.т.н., доцент кафедры вычислительной техники Бессмертный Игорь Александрович, ...». Фраза, немыслимая в повседневной ситуации, но совершенно нормальная в милицейском протоколе. Очевидно, что при создании семантической сети один раз можно постараться и идентифицировать все объекты однозначно, хотя это существенно усложнит работу. Но для доступа к знаниям необходимо дать возможность вести упрощенный диалог, подобный имеющему место в реальной 84 жизни. Такая функция может быть возложена на интеллектуальный агент, осуществляющий доступ к знаниям. База контекста должна состоять из двух компонентов: постоянного и временного. Постоянный контекст – это знания, не изменяющиеся в процессе диалога. Например, мы хотим узнать, который час. На этот вопрос, который ни у кого не вызывает затруднений, не может быть получен ответ без информации о местоположении субъекта. Следовательно, в базе контекста должна быть информация о том, где находится субъект, а также часовой пояс данного места. Иными словами, в базу должно быть загружено контекстное окружение. Временный контекст – это факты, которые устанавливаются или уничтожаются (забываются) в процессе диалога, а также временные ассоциации, устанавливаемые для упрощения диалога. Временные факты – это, например, ответы на вопросы, которые были заданы ранее, т.е. знания, принесенные извне и не требующие сохранения в базе знаний. Примером таких фактов могут быть ответы пациента на вопросы врача, который пытается поставить диагноз. Отсутствие такой памяти сделает диалог похожим на многочисленные анекдоты про склеротиков. Временные ассоциации дают возможность присвоить объектам или фактам короткие имена для использования только в данном диалоге. Временные ассоциации широко используются как в повседневной жизни, так и в документах. Например, в текстах договоров обычно используется оборот типа «ООО РОГА И КОПЫТА в лице директора Фунта А.А., действующего на основании устава, именуемое в дальнейшем ПОКУПАТЕЛЬ…». Таким образом, база контекста позволит создать для пользователя упрощенное представление (модель) семантической сети, которое позволит вести диалог в привычном виде. 7.11. Семантическая сеть и Семантическая паутина Как показано в подразд.7.2, семантическая сеть имеет давнюю историю, и до последнего времени это понятие не вызывало никаких двусмысленностей. Однако, после того, как изобретатель Всемирной паутины (WWW) Тим Бернерс Ли в 2001 году провозгласил концепцию “Semantic Web”, в русскоязычной литературе эти два понятия стали смешиваться. Для устранения недоразумений предлагается переводить понятие “Semantic Web” как «Семантическая Паутина» или, в данном тексте – просто «Паутина». Суть идеи Тима Бернерса Ли заключается в том, чтобы снабдить ресурсы Интернета специальными метаданными, доступными для компьютерной обработки и однозначно характеризующими свойства и содержание ресурсов Всемирной паутины, вместо используемого в настоящее время текстового анализа документов. В частности, предполагается снабдить все ресурсы Интернета тегами, позволяющими установить автора каждого документа. Следует отметить, что это решение сделано «вдогонку» к концепции WWW после того, как Интернет 85 из хранилища знаний превратился в информационную «помойку» из-за допускаемой анонимности ресурсов. Однако, данное свойство семантической паутины нас интересует в последнюю очередь. В центре нашего интереса – свойства Семантической Паутины доставлять пользователю информацию, которую он хочет получить. Основное отличие Семантической Паутины от WWW заключается в том, что связи между ресурсами WWW отражают размещение документов, а связи Паутины – содержание. Правда, как в WWW, так и в Паутине ссылки содержат адреса ресурсов, но в WWW ссылки обезличенные; их смысл должен понимать пользователь. В Паутине же ссылки имеют явно указанный смысл, который доступен для машинной обработки. Таким образом, Семантическая Паутина подразумевает роботизированный поиск информации вместо имеющего место сейчас Web сёрфинга, когда пользователь Интернета переходит по ссылкам от документа к документу. 7.12. Семантическая Паутина: принципы и текущее состояние В основе Семантической Паутины лежит тот же триплет субъект- предикат-объект. Отличие заключается в представлении каждого из элементов триплета. В Паутине субъект, объект и предикат представлены универсальными идентификаторами ресурсов или URI (Uniform Resource Identifier). Так, граф визитной карточки основателя Википедии выглядит следующим образом (рисунок позаимствован в той же Википедии): URI только выглядит как адрес ресурса URL. На самом деле по любому из приведенных на рисунке адресов, таких как 86 http://www.w3.org/2000/10/swap/pim/contact#mailbox , вы не найдете ничего похожего на почтовый ящик, или хотя бы его описание, как это может показаться на первый взгляд. Такая система именования нужна только для обеспечения уникальности имен. Наиболее популярным языком представления знаний в Паутине является язык RDF. Фрагмент RDF-документа, описывающие отношения Сергей имеет ребенка Никиту, а Никита имеет родителя Сергея, приведен ниже. |