Текст диплома (без формул)

Полный текст можно скачать с этого сайта

~
~

Оглавление.

1. Введение.
2. Постановка задачи и проблематика проекта.
3. Структура когнитивного словаря WordNet.
4. Построение вопросно-ответной системы.
5. Работа вопросно-ответной системы.
6. Схема данных словаря.
7. Техническая реализация системы.
8. Описание системы.
9. Результаты работы.
10. Будущие планы (вместо заключения).
11. Литература.


1. Введение.

Проблема поиска информации является одной из острейших для современного сетевого сообщества. Одной из главных отличительных особенностей информационного массива является высокая степень его динамики. Каждую секунду появляются новые факты, материалы, исследования. Постоянное обновление и одновременным ростом объема информационного массива делает крайне сложным учет всей или, по крайней мере, большинства существующей информации. Сведения, представляющие огромную ценность часто остаются невостребованными пользователями по единственной причине трудностей их разыскания. Ситуация в данном случае очень напоминает известную задачу поиска иголки в стоге сена.
Деятельность отдельных людей, коллективов и организаций сейчас все в большей степени зависит от имеющейся у них информации и способности ее эффективно использовать.
Когда мы хотим что-то узнать, мы спрашиваем – задаем вопрос. Для нас в этих словах значима несомненная связь между поиском ответа на вопрос и обработкой информации, получением знаний.
Имея доступ к морю информации, представленной в Internet, пользователю хотелось бы получать только нужные ему данные, в то время как поисковые системы работают более чем неудовлетворительно. Проблема усугубляется еще и тем, что различные группы людей, занимающиеся сбором и поиском информации, используют для общения с поисковыми системами, как свои специальные термины, так и термины, широко используемые другими сообществами в ином контексте. Вследствие этого может возникнуть проблема несовместимости используемых терминов, так как современные машины поиска используют в основном механизмы поиска по ключевым словам, не учитывающие контекст, в котором существует информация. В итоге результатом работы таких машин поиска являются сотни тысяч ссылок, большинство из которых указывают на документы, не относящиеся к делу, что затрудняет восприятие и выбор полезной информации. Таким образом, возникает противоречие между хранящейся в Internet информации и ограниченными возможностями человека по ее поиску и переработке.
Порожденный указанными выше проблемами информационный кризис еще больше подогрел интерес к разработке интеллектуальных механизмов поиска информации. Web стал рассматриваться как потенциальная база знаний, для работы с которой нужны специальные методы представления и обработки знаний и запросов. Разумным здесь кажется применение методов и средств, разработанных в области искусственного интеллекта.
В последнее время сильно увеличилось количество проектов, разрабатывающих технологии ответа на простые вопросы, ответ на который может состоять из нескольких слов, небольшого отрывка из связного текста. Пока эти проекты обходят стороной ответы на более сложные вопросы, как, например, рассказы о событиях, описание объектов и т.д…
Все подобные системы строятся в первом приближении по стандартной схеме. Все они создают запрос из вопроса пользователя, потом проводят поиск по базе документов и выбирают те, которые больше всего подходят в качестве ответа. Основные различия систем кроятся именно в механизме выбора походящих документов.
Статистические методы дробят документы на огромное количество отрывков, которые потом по отдельности индексируются и в последствии выдаются в качестве ответа. Сложность состоит в том, что сегменты необходимо сделать настолько маленькими, чтобы они могли играть роль ответа, но при этом должна сохраниться возможность их индексирования.
Семантические методы сравнивают семантическую близость различных предложений документа и вопроса пользователя и в последствии выбирают наиболее подходящий вариант. Сложность заключается в том, что необходимо создать систему, которая будет осуществлять поиск за приемлемое время. Чисто семантические методы, как правило, сильно проигрывают статистическим в быстродействии.
Типовая вопросно-ответная система состоит из большого количества сложных элементов, предназначенных для статистического и семантического анализа вопроса и обрабатываемых документов. Эти элементы разрабатываются независимыми группами и, как правило, работают только с английским языком. Этот факт является серьезным препятствием для российских разработчиков, которые хотят создавать системы, работающие на русском языке. В свободном доступе нет русскоязычных систем морфологического, синтаксического и, тем более, семантического анализа.

2. Постановка задачи и проблематика проекта.

Разработка вопросно-ответной системы, которая в качестве базы знаний использует простые текстовые документы, не простая задача. Для того чтобы проанализировать текст необходимо провести его синтаксический анализ. В каждом предложении необходимо выявить подлежащие, сказуемые, определения и дополнения. Да и сам ответ необходимо сформировать синтаксически грамотно.
Решить эту задачу доступными средствами не представлялось возможным, и поэтому было решено построить вопросно-ответную системы – менеджер ЧАВО (часто задаваемых вопросов).
Основными задачами Менеджера ЧАВО являются
- сравнение вопроса, который задает пользователем, с вопросами, которые находятся в списке ЧАВО;
- выбор наиболее близкого вопроса;
- печать заранее заготовленного ответа.
Информационной базой для Менеджера ЧАВО являются: список ЧАВО и заранее заготовленные ответы.
Подобные системы оказываются востребованными в различных информационных службах, службах технической поддержки и послепродажного обслуживания.
Пример: Вы хотите поехать на горнолыжный курорт. Своего оборудования у Вас нет и Вам нужно узнать, сколько стоит прокат, когда он работает, и что нужно, чтобы воспользоваться прокатным снаряжением. Можно просто зайти на сайт в раздел «прокат» или позвонить администратору. Большинство людей предпочитает позвонить. И приходится содержать отдельного человека, который целыми днями будет отвечать на вопросы: «Сколько стоит прокат горных лыж?», «Можно ли взять на прокат горнолыжные ботинки?», «Сколько стоит аренда горнолыжного снаряжения?» и т.д. Ответ на все эти вопросы одинаковый, и менеджер постоянно дает давно заученные одинаковые ответы. Специалисты служб технической поддержки говорят, что спустя пару недель все вопросы начинают повторяться. И количество принципиально различных вопросов сводится к нескольким десяткам или сотням.
Сразу же возникает вопрос: а можно ли заменить менеджера компьютером? Оказывается, что можно, но для этого компьютер должен знать, что «горные лыжи» и «оборудование» это одно и то же. «Оборудование» включает в себя «горные лыжи», «ботинки» и «палки». А «взять на прокат» и «арендовать» означает сделать одно и то же.
Люди уже давно пытаются обучить компьютер «понимать» человеческий язык. Понимать в данном случае означает воспринимать не знаковое, а смысловое значение. При разработке Менеджера ЧАВО компьютеру не нужно знать, что
ЛЫЖИ – это 1. Плоские деревянные (или пластиковые) полозья для хождения, бега по снегу. Горные лыжи (1) предназначенные для скоростного спуска с гор; 2) вид спорта скоростной спуск с гор на лыжах по специальным трассам). 2. Вид спорта хождение, бег на таких полозьях.
Достаточно только знать, что «лыжи» эквивалентны «горным лыжам» и входят в состав «оборудования» и «снаряжения». Подобную информацию компьютер может получить из тезауруса.
Тезаурус – это Словарь, в котором слова, относящиеся к каким-либо области знания, расположены по тематическому принципу и показаны семантические отношения (родо-видовые, синонимические и др.) между лексическими единицами. В информационно-поисковых тезаурусах лексические единицы текста заменяются дескрипторами.
Тезаурус - прежде всего иерархическая классификация и она нужна для того, чтобы сначала найти нужную сущность (денотат). Действительно, если я вижу гайку и не знаю, как она называется на моем родном языке, тезаурус предлагает мне такую схему поиска по дереву - это идея или материальная сущность. Затем - гайка - это природой созданный предмет или создан человеком и т.д. Мы движемся по дереву, пока не достигнем своего денотата, а потом видим, как он называется, т.е. определяем дескриптор. Соответственно, воспользовавшись этим деревом можно определить, как связаны между собой различные дескрипторы и связаны ли они вообще.
Таким образом, для любой словарной статьи нужно указать в какие более общие понятия, конструкции и т.п. интегрируется описываемый ею объект - т.е. вышестоящие статьи. Аналогичное рассуждение справедливо и в обратную сторону. Эта стройная иерархическая классификация дополняется перекрестными связями самого разного рода - чаще всего синонимическими или антонимическими, различного рода ассоциативными связями.
При построении Менеджера ЧАВО было решено воспользоваться когнитивным словарем WORDNET - интеллектуальным компьютерным тезаурусом. WORDNET создан в Принстонском университете и свободно распространяется.
Слова в нем сгруппированы в синонимические группы (синсеты - synsets) и разбиты на 4 словаря - существительные, прилагательные, глаголы и наречия. Синсеты объединены как в иерархические связи (гипонимы и гиперонимы), так и в отношения синонимии и антонимии и также меронимии (быть частью чего-либо или состоять из частей).
Остановимся на структуре когнитивного словаря WordNet более подробно.

3. Структура когнитивного словаря WordNet.

WordNet - диалоговая лексическая справочная система, в которой английские существительные, глаголы, и прилагательные, организованы в наборы синонимов, каждый из которых представляет одну лексическую единицу. Наборы синонимов связаны различными отношениями.
Стандартный способ организации лексической информации - запись слов в алфавитном порядке. Существенный минус подобной организации заключается в том, что поиск нужного слова может оказаться утомительным и занять много времени. Поэтому, много людей, которые хотели бы обратиться к словарю, решают не делать этого, потому что поиск информации надолго прерывает их работу и ход их мыслей.
Очевидная причина использовать компьютерные словари, лексические базы данных - компьютеры могут обрабатывать такие буквенные списки намного быстрее чем люди.
Ответ словаря может быть доступен, как только нужное слово отобрано или напечатано на клавиатуре. Кроме того, так как словари изначально подготавливались на компьютере, их достаточно просто преобразовать в понятную компьютеру форму. Превращение обычных словарей в компьютерные кажется простым и естественным решением.
Очень быстро становится очевидным, что чрезвычайно неэффективно использовать эти мощные машины всего на всего как быстрые переворачиватели-страниц.
WordNet - эффективный способ превращения традиционных словарей в современное быстродействующее лексическое средство.
Наиболее очевидное различие между WordNet и стандартным словарем - это то, что WordNet делит словарь в пять категорий: существительные, глаголы, прилагательные, наречия, и слова-функции. Фактически, WordNet содержит только существительные, глаголы, прилагательные, и причастия. Наиболее примечательно особенностю WordNet, однако, является его попыткой организовать лексическую информацию в терминах значения слова, нежели формы слова. В этом отношении, WordNet больше напоминает тезаурус чем словарь.
Проблема буквенного тезауруса - избыточные вхождения: если слово Wx и слово Wy синонимы, то пара должна быть введена дважды, когда расположена в алфавитном порядке под Wx и снова - в алфавитном порядке под Wy, удваивая, таким образом, время поиска. Однако, WordNet не просто он-лайновый тезаурус. Чтобы оценить то, что было сделано в WordNet, необходимо понять сначала его структуру.
Лексическая семантика начинается с признания того факта, что слово это ассоциация между лексической концепцией и произнесением, которое играет синтаксическую роль. Это определение "слова" поднимает по крайней мере три класса проблем для исследования. Во-первых, Какие виды произнесения вступают в эти лексические ассоциации? Во вторых, что является принципом выделения лексических концепций, которые слова могут выражать? В-третьих, какие синтаксические роли играют различные слова? Хотя и невозможно игнорировать любой из этих классов, здесь мы сделаем акцент только на втором классе, на проблемах, которые имеют дело с семантической структурой словаря.
Чтобы исключить двусмысленность, далее мы будем называть произнесение слова "формой слова", а его лексическую концепцию - "значением слова".
Отношение между формами и значениями - многие-к-многим - некоторые формы имеют несколько различных значений, а некоторые значения могут быть выражены несколькими различными формами. Две сложных проблемы лексикографии, полисемия и синонимия, могут рассматриваться как дополнительные аспекты этого отношения.
Как значения слова представлены в WordNet? Чтобы моделировать лексическую матрицу необходимо иметь некоторый способ представить, и формы и значения для компьютера.
В WordNet для этого служат наборы синонимов (синсеты), которые служат для выделения лексических концепций. Например, board может означать или кусок древесины или группу людей собравшихся для некоторой цели. Синсеты, board, plank и board, committee будут служить как однозначные определения этих двух значений слова board.
Эти наборы синонимов (синсеты) не объясняют, чем являются концепции; они просто показывают, что они существуют. Так как Английский язык богат синонимами, синсет являются достаточным для отличительных целей.
Синонимия, конечно, лексическое отношение между формами слова, но ей назначена центральная роль в WordNet. WordNet связан семантическими отношениями. Так как семантическое отношение – отношение между значениями, и так как значения могут быть представлены синсетами, естественно думать о семантических отношениях как указателях между синсетами.
При создании WordNet использовались следующие отношения:
Синонимы - слова или выражения, совпадающие или близкие по значению с другими словами, выражениями.
Антонимы - слова, противоположные друг другу по значению, например, «светлый» и «тёмный».
Гиперонимы – отношение «является частью».
Меронимы – отношение «состоит из».

~
~

4. Построение вопросно-ответной системы.

Вернемся теперь к построению вопросно-ответной системы. Искать ответы на вопросы пользователя, используя базу, состоящую из текстовых документов, не просто. Так как в этом случае успех предприятия зависит от эффективности механизма синтаксического анализа, поэтому мы решили ограничиться обработкой списка ЧАВО (FAQ). Задача была поставлена следующим образом. Имеется список «базовых» вопросов, или список ЧАВО в виде вопрос-ответ. Т.е. на каждый «базовый» вопрос уже есть готовый ответ. Необходимо было получить вопрос пользователя, его обработать, сравнить с вопросами из списка ЧАВО и вывести те, которые наиболее близки к вопросу пользователя по смыслу. Для сравнения вопросов использовался метод матрицы соответствия, а для определения семантического расстояния между словами – когнитивный словарь WordNet.
Итак, у нас есть два вопроса, и мы хотим узнать, насколько они близки друг другу. Иными словами, нам нужна функция, которая ставит в соответствие двум множествам слов в некоторое число. Такую операцию можно осуществить различными способами. Мы решили сравнить все возможные комбинации слов и построить матрицу соответствия, элементами которой являются коэффициенты родства двух отдельных слов, а потом свести эту матрицу к матрице единичной размерности, т.е. к числу.
Итак, первой частью этого метода является сравнение каждого слова вопроса пользователя с каждым словом вопроса ЧАВО. Предположим, что - i-ое слово вопроса пользователя, - j-ое слово вопроса ЧАВО. Тогда степень родства этих слов вычисляется по формуле:
,
где - длина пути между словами и (о том, как определяется величина будет рассказано далее); - максимально допустимая длина пути; и - нормировочные константы, определяющие диапазон изменения .
Матрицей соответствия вопроса пользователя длиной слов вопросу ЧАВО длиной слов является матрица размерностью :

.

Следующим шагом матрица соответствия сводится к единичному числу следующим образом:
.

Число и является мерой семантической близости вопросов и .
Следующий шаг - определение "близости" слов при помощи WordNet. При определении возникает следующая проблема: работа и устройство системы WordNet различны для различных частей речи, а определить, какой частью речи является конкретное слово в конкретном предложении, не представляется возможным. Поэтому, независимо разбирались все части речи...
Для каждой части речи отбирались синсеты, в которые входит данное слово. В результате, каждое слово в предложении заменялось 4мя наборами синсетов (для каждой части речи).
Пример:
word1 as noun is in synsets - 1, 3, 4, 5
verb ---"----- - 10, 11
adv ---"----- - no match
adj ---"----- - 20
word2 as noun is in synsets - 1, 2, 3
verb ---"----- - 13
adv ---"----- - 19
adj ---"----- - no match
После сравнения следует, что word1 соответствует word2
as noun в 2х синсетов из min(3, 4) возможных
as verb, adv, adj - 0
В случае наличия прямой синонимической связи, вектор соответствия этих слов по частям речи будет иметь вид: (2/3, 0, 0,0). После умножения этого вектора на коэффициент близости слов получаем окончательное значение элемента матрицы соответствия.
Однако в языке не так много прямых синонимических связей. И, самое главное, очень редко вопрос пользователя отличается от вопроса ЧАВО только на уровне синонимов. Поэтому систему сравнения было необходимо усложнить и строить систему сравнения слов, используя не только отношения синонимии, но и отношения «гиперонимов» и «меронимов». В результате сравнивались уже не списки синсетов, а деревья синсетов гиперонимов. Длина пути считалась, как количество узлов между словами в этом дереве.

5. Работа вопросно-ответной системы.

По такому принципу была разработана вопросно-ответная система, использующая в качестве словаря Wordnet, доступ к которому осуществлялся при помощи стандартной библиотеки, которая включена в поставку WordNet. Система была написана на языке C++ и работала только в режиме командной строки, чего было достаточно для того, чтобы проверить качество и релевантность ответов.
В качестве тестового задания системе были предложены списки вопросов ЧАВО на английском языке, взятые из различных общедоступных источников. В качестве вопросов пользователя брались а) список тех же самых вопросов ЧАВО, б) специально подготовленные вопросы.
Рассмотрим, как работу системы на примере. Ниже я приведу подробный результат сравнения двух существительных и конечный результат сравнения двух наборов вопросов.
Итак, определим семантическую близость двух слов: bear (медведь) и water (вода):
Слово bear определено следующим образом:
Как существительное:
1. bear -- (massive plantigrade carnivorous or omnivorous mammals with long shaggy coats and strong claws)
2. bear -- (an investor with a pessimistic market outlook)
Как глагол:
1. bear -- (have: "bear a resemblance"; "bear a signature")
2. give birth, deliver, bear, birthe, birth, have -- (give birth (to a newborn); "My wife had twins yesterday!")
3. endure, stomach, bear, stand, tolerate, brook, abide, suffer, put up -- (put up with something or somebody unpleasant; "I cannot bear his constant criticism"; "The new secretary had to endure a lot of unprofessional remarks")
4. bear -- (move while holding up or supporting; "Bear gifts"; "bear a heavy load"; also with communication nouns: "bear news"; "bearing orders")
5. bear, turn out -- (bring forth, "The apple tree bore delicious apples this year"; "The unidentified plant bore gorgeous flowers")
6. bear, take over, accept, assume -- (take on as one's own expenses or debts of another person; "I'll accept the charges"; "She agreed to bear the responsibility")
7. hold, bear, carry, contain -- (contain or hold; have within: "The jar carries wine"; "The canteen holds fresh water"; "This can contains water")
8. yield, pay, bear -- (bring in; as of investments; "interest-bearing accounts"; "How much does this savings certificate pay annually?")
9. wear, bear -- (have one one's person; "He wore a red ribbon"; "bear a scar")
10. behave, acquit, bear, deport, conduct, comport, carry -- (behave in a certain manner; "She carried herself well"; "he bore himself with dignity"; "They conducted themselves well during these difficult times")
11. bear, hold -- (have rightfully; of rights, titles, and offices; "She bears the title of Duchess"; "He held the governorship for almost a decade")
12. hold, carry, bear -- (support or hold in a certain manner; "She holds her head high"; "He carried himself upright")
13. bear, carry, gestate, expect -- (be pregnant with; "She is bearing his child"; "The are expecting another child in January")

Слово water:
Как существительное:
1. water, H2O -- (a clear colorless odorless tasteless liquid; "he asked for a drink of water")
2. body of water, water -- (the part of the earth's surface covered with water; "they invaded our territorial waters")
3. water system, water supply, water -- (source of water; "the town debated the purification of the water supply"; "first you have to cut off the water")
4. water -- ((archaic) once thought to be one of four elements composing the universe)
5. perspiration, sweat, diaphoresis, sudor, hidrosis, water -- (salty fluid secreted by sweat glands; "sweat poured off his brow")
6. urine, piss, pee, piddle, weewee, water -- (liquid excretory product; "there was blood in his urine"; "the child had to make water")
7. lacrimal secretion, lachrymal secretion, water -- (saline fluid secreted by lacrimal glands; lubricates the surface of the eyeball)
Как глагол:
1. water, irrigate -- (pour water on; "Water the lawn")
2. water -- (provide with water: "We watered the buffalo")
3. water -- (secrete or form water, as tears or saliva: "My mouth watered at the prospect of a good dinner"; "His eyes watered")
4. water -- (fill with tears; "His eyes were watering")

Деревья гиперономов для существительных bear и water выглядят следующим образом:
Для bear:
Значение 1
bear
=> carnivore
=> placental, placental mammal, eutherian, eutherian mammal
=> mammal
=> vertebrate, craniate
=> chordate
=> animal, animate being, beast, brute, creature, fauna
=> life form, organism, being, living thing
=> entity, something
Значение 2
bear
=> investor
=> capitalist
=> person, individual, someone, somebody, mortal, human, soul
=> life form, organism, being, living thing
=> entity, something
=> causal agent, cause, causal agency
=> entity, something
Для water:
Значение 1
water, H2O
=> liquid
=> fluid
=> substance, matter
=> object, physical object
=> entity, something
Значение 2
body of water, water
=> object, physical object
=> entity, something
Значение 3
water system, water supply, water
=> facility, installation
=> artifact, artefact
=> object, physical object
=> entity, something
Значение 4
water
=> element
=> substance, matter
=> object, physical object
=> entity, something
Значение 5
perspiration, sweat, diaphoresis, sudor, hidrosis, water
=> secretion
=> liquid body substance, bodily fluid, body fluid
=> body substance
=> substance, matter
=> object, physical object
=> entity, something
Значение 6
urine, piss, pee, piddle, weewee, water
=> body waste, excretion, excreta, excrement, excretory product
=> waste, waste material, waste matter, waste product
=> material, stuff
=> substance, matter
=> object, physical object
=> entity, something
Значение 7
lacrimal secretion, lachrymal secretion, water
=> secretion
=> liquid body substance, bodily fluid, body fluid
=> body substance
=> substance, matter
=> object, physical object
=> entity, something
Таким образом слова bear и water схожи только в одном. Они оба «растут» от понятия «entity, something». Причем, слово bear входит в эту сущность 2 раза, слово water 7 раз. При подсчете суммарного результата, следует учесть, что степени семантической близости для каждого значения суммируется. Таким образом, часто употребляемые слова имеют более высокую степень соответствия, чем редко употребляемые. На самом деле, такой результат плохо соответствует реальному положению вещей. К примеру, если в вопросе пользователя и ЧАВО вопросе присутствует слово «топенант», то они должны быть ближе друг другу, чем два вопроса с общим словом, например, «система». При помощи словаря WordNet можно оценивать встречаемость слов, и, соответственно, вводить поправочные коэффициенты.
Вернемся к вопросам. Ниже представлен результат работы программы, сравнивающий список ЧАВО, состоящий их трех предложений, с тремя вопросами пользователя.
Q: Do bears like water in winter?
FAQ: Bear likes water.
Question score: 26.000000
FAQ: Winter is good for bears.
Question score: 18.557875
FAQ: Bears don't like winter.
Question score: 27.557875
=============================
Q: Is water good for bears?
FAQ: Bear likes water.
Question score: 26.000000
FAQ: Winter is good for bears.
Question score: 45.557875
FAQ: Bears don't like winter.
Question score: 15.936844
=============================
Q: What do bears do in winter?
FAQ: Bear likes water.
Question score: 15.000000
FAQ: Winter is good for bears.
Question score: 18.000000
FAQ: Bears don't like winter.
Question score: 18.000000

Из этого примера видно, что, во-первых, система достаточно корректно выбирает правильные ответы. Числовое значение, определяющее степень соответствия существенно зависит от распространенности слов в вопросе.
Система, построенная на словаре WordNet, показала хорошие результаты при ответе на вопросы общей тематики. Однако оказалась совершенно не жизнеспособной при работе с узкоспециализированными текстами. Система просто не могла узнать о том, что Windows, например, это «операционная система», а окна можно не только мыть. Подобных примеров можно привести сотни и даже тысячи.
Однако сложившуюся проблему надо решать. Вариант, который сразу же приходит в голову, прост – необходимо дополнить существующий словарь WordNet необходимыми терминами и связями.
Мы пошли именно по такому пути, решив предоставить пользователю возможность самому определять необходимые для его предметной области связи, группировать термины в наборы синонимов. Иными словами, мы предоставили пользователю возможность создать свой собственный, карманный Wordnet, который полностью будет описывать необходимую владельцу область знаний.

6. Схема данных словаря.

Для решения проблемы создания собственного карманного словаря WordNet в реляционной СУБД была построена следующая структура:


Предложенная схема данных мало отличается от структуры когнитивного словаря WordNet. Основные отличия заключаются в том, что в предложенной схеме нет жесткого понятия «отношение». Необходимые отношения пользователь может создавать самостоятельно. В этом есть как свои плюсы, так и свои минусы. Плюсы заключаются в том, что появляется возможность тонкой настройки на отношения, необходимые для данной предметной области. Минусы – в том, что для каждого отношения придется переделывать алгоритм поиска, т.е. исправлять исходные коды программы.

~
~

~
~

7. Техническая реализация системы.

При разработке собственного словаря WordNet было решено использовать реляционную СУБД MySQL в качестве средства хранения данных. И скриптовый язык PHP для доступа к ним. Данные средства были выбраны ввиду ряда причин. Во-первых, оба продукта широко распространены в сети интернет, поддерживаются практически на всех площадках крупных провайдеров интернет-хостинга. Оба средства хорошо документированы, просты в изучении и работе. К тому же существует огромное количество специалистов, умеющих работать с ними. Следует отметить, что словарь WordNet является скорее семантической сетью, а при проекции семантической сети на реляционную структуру, для доступа к данным возникает необходимость в выполнении большого количество коротких запросов типа «select». При большом объеме словаря выполнение этих selectов может существенно замедлить работу системы. Таким образом, переход от собственной базы WordNet к реляционной СУБД накладывает ограничения на суммарный размер словаря. Ввиду того, что с самого начала система позиционируется как «карманная», ограниченный размер словаря не является существенным недостатком.
Существенным отличием SQL-версии от WordNet-версии является способ хранения вопроса. В предыдущих главах я писал о том, что каждое слово вопроса пользователя сравнивается с каждым словом вопроса ЧАВО, при этом дерево гиперонимов строиться как для вопроса пользователя так и для вопроса ЧАВО. Несмотря на то, что такой механизм работы упрощает ввод в систему новых вопросов, от него было решено отказаться и заставить пользователя вручную определять синсеты, к которым принадлежат слова вопроса ЧАВО. Такой подход усложняет работу администратора, зато существенно улучшает точность ответов, так как вопросы-ЧАВО оказываются жестко структурированы. Т.е., пропадает возможность ошибки при определении значения слова в вопросе ЧАВО.
В системе не реализованы модули морфологического анализа. В текущем варианте системы морфологический анализ реализован при помощи таблицы WORDFORM, в которой хранятся все возможные формы слова и ссылка на форму инфинитива.
Система умеет собирать информацию о «неизвестных» словах. Т.е. о словах, которые отсутствуют в словаре. Незнакомые слова собираются в специальной таблице-приемнике. Администратор системы может в любой момент на них посмотреть и решить, являются ли они синтаксическими ошибками, редко встречаемыми словами, или недостатками при составлении словаря, требующими немедленного устранения.
Важным элементом системы является так называемый «Интерфейс администратора». Он позволяет администратору системы редактировать словарь, добавлять новые слова, синсеты, отношения. Относить слова к синсетам, связывать синсеты отношениями. В качестве «Интерфейса администратора» использовался модифицированный «Менеджер таблиц MySQL». «Менеджер таблиц» позволяет администратору системы совершать любые операции над данными. Такой подход является оправданным на этапе бета-тестирования системы. Однако, является совершенно неприменимым в реальных рабочих системах, так как не обеспечивает целостности данных при работе со словарем.
Основными функциями «Интерфейса Администратора» являются:
1. Система накопления незнакомых слов и не отвеченных вопросов (сейчас работает просто как «куча»).
2. Система сортировки слов по синсетам.
3. Система создания/удаления новых синсетов.
4. Система установки связей между синсетами.
5. Система ввода и редактирования вопросов ЧАВО.
6. Разбиение вопросов ЧАВО на слова и определение соответствующих синсетов.
Сравнение и выбор наиболее подходящего вопроса реализованы в отдельном модуле. Язык PHP является гибким средством для работы с текстовыми данными. Впрочем, почти вся работа по сравнению вопросов переложена на внутренний движок MySQL. В PHP-части системы производится только разбиение вопроса на слова и последовательный запуск очереди запросов для формирования дерева синсетов. Такой метод замедляет работу системы, зато позволяет избежать необходимости формирования и сравнения деревьев гиперонимов средствами PHP. Эти деревья строятся и сравниваются в промежуточных таблицах MySQL. Такой «неэффективный» подход был применен сознательно, так как впоследствии планируется на его основе построить систему кэширования наиболее употребительных вопросов и слов.
Я намеренно не буду приводить результаты работы системы, так как их нельзя считать объективными. Дело в том, что в процессе написания данного диплома так и не было создано отдельного словаря достаточного объема. Для всех, проводимых мной, тестов я делал отдельный словарь, который формировался с учетом будущей специфики вопросов. Поэтому, результат получался предвзятым, т.е. я получал те результаты, которые хотел получить. Впрочем, построение большого словаря и проверка работы системы на произвольных вопросах будет следующим этапом работы.
Точность и правильность ответов будет во многом зависеть от работы администратора. И для того, чтобы оценить окажется ли подобная система применимой в реальной жизни потребуется накопление большого количества статистических данных. Тем не менее, эксперимент, проведенный с полной базой WordNet, показывает, что есть все основания надеяться на отличный результат.

8. Описание системы.

Теперь можно перейти к описанию построенной при помощи PHP и MySQL вопросно-ответной системы. Сначала кратко напомню постановку задачи.
Имеется список «базовых» вопросов, или список ЧАВО, в виде вопрос-ответ. Т.е. на каждый «базовый» вопрос уже есть готовый ответ. Необходимо получить вопрос пользователя, сравнить с вопросами из списка ЧАВО и вывести ответы на те вопросы, которые наиболее близки к вопросу пользователя по смыслу.
По основным функциям систему можно разбить на три основных модуля:
1. Модуль поиска и сравнения – предназначен для обработки вопросов пользователя и поиска наиболее подходящего вопроса из списка вопросов ЧАВО.
2. Словарный модуль – предназначен для работы со словарем: добавления, изменения, удаления слов, синсетов, отношений.
3. Вопросный модуль – предназначен для работы со списком вопросов ЧАВО. Позволяет вводить, удалять, редактировать вопросы ЧАВО, определять синсеты, к которым принадлежат слова вопроса.
Модуль поиска и сравнения – относится к пользовательскому интерфейсу. Словарный и вопросный модули находятся в интерфейсе администратора. Все модули написаны на PHP и работают независимо друг от друга.
Функции системы распределены между PHP-модулями и движком MySQL следующим образом: PHP-модули выполняют:
1. Формирование запросов к серверу БД.
2. Форматирование информации для клиента.
3. Обеспечение интерфейса экранных форм.
Движок MySQL выполняет:
1. Хранение данных когнитивного словаря.
2. Выполнение запросов на сервере БД.
3. Предоставление PHP-клиентам неформатированных данных.
Разберем работу модулей по отдельности.
8.1. Модуль поиска и сравнения (МПС).
Входными данными для МПС является пользовательский вопрос (ПВ). Первым этапом обработки ПВ является разбивка его на слова. Слова отделяются друг от друга пробелами и знаками препинания. Далее проверяется принадлежит ли слово стоп-листу. Это делается для того, чтобы отфильтровать предлоги, вопросительные слова и часто встречаемые слова, не придающие вопросу смысловой окраски. В системе не реализован морфологический анализ и, поэтому, приведение к форме инфинитива осуществляется «в лоб». В таблице WORDFORMS собраны все возможные склонения и спряжения слов словаря, поэтому определение формы инфинитива не является проблемой. Слова, не найденные ни в стоп листе, ни в таблице WORDFORMS, помещаются в таблицу-приемник UNKNOWN. В последствии, данные этой таблицы могут быть просмотрены администратором системы, который принимает решение о необходимости доработки словаря.
По форме инфинитива определяются синсеты, в которые входит анализируемое слово. Помимо базовых синсетов на этом этапе отбираются и те, которые необходимо включить в «дерево», определяются семантические расстояния между элементом дерева и базовым синсетом. Все «дерево» записывается в промежуточную таблицу Table1 (Номер слова, Синсет, Семантическое расстояние) с потерей древовидной структуры. Далее строится таблица соответствия слов вопроса пользователя словам вопроса ЧАВО (эта операция повторяется для каждого вопроса ЧАВО, поэтому далее мы будем иметь ввиду, что одновременно сравниваются только два вопроса). Эта таблица Table2 включает поля: Номер слова, Синсет, Семантическое расстояние, Номер слова ЧАВО, Синсет ЧАВО. Далее из этой таблицы выбираются записи у которых Синсет и Синсет ЧАВО совпадают. Таблица сортируется по убыванию семантического расстояния и из нее формируется набор, дающий максимальную сумму семантический расстояний для вопроса ЧАВО. Эта максимальная сумма и является мерой близости вопросов. Далее из всех сумм для вопросов списка ЧАВО следует выбрать максимальные и вывести пользователю ответы на них. Ответы на вопросы ЧАВО хранятся в базе в виде ссылок на внешние файлы. Такой метод хранения используется для простоты редактирования ответов.

8.2. Словарный модуль.
Модуль предназначен для работы со словарем. Для добавления, удаления, изменения слов, синсетов и отношений. Для того, чтобы процесс создания словаря был наиболее прост и не обременителен, следует соблюдать порядок ввода сущностей. Т.е. сначала необходимо определить отношения, которые будут использоваться в словаре. В системе нет жесткой привязки к определенному типу отношений. Тем не менее, на начальном этапе рекомендуется использовать отношения, использованные в WordNet. Они являются каноническими и упрощают построение словаря. Далее вводятся синсеты. Не следует забывать, что синсет в первую очередь определяет некую сущность, и только потом ассоциируется со словом. Нумерация синсетов может быть как ручной, так и автоматической. Автоматическая нумерация осуществляется просто по порядку номеров. Поэтому при разработка больших словарей, и тогда, когда планируется регулярная работа со словарем рекомендуется давать синсетам более осмысленные идентификаторы, которые будут отражать положение синсета в иерархии. для упрощения поиска нужного синсета при редактировании словаря в системе предусмотрена возможность разбивать синсеты на одноуровневые категории (см. таблицу SYNCATEGORY). Добавление слов в синсеты самая простая задача. Следует только следить за уникальностью идентификаторов слов при редактировании. При добавлении слова необходимо также определить все его морфологические формы.

8.3. Вопросный модуль.
Вопросный модуль предназначен для добавления, редактирования и удаления вопросов ЧАВО. Алгоритм ввода в систему нового ЧАВО вопроса схож с первоначальной обработкой запроса пользователя. Вначале следуют те же самые разбиение на слова, проверка на принадлежность стоп-листу и нормализация. Отличие от обработки пользовательского вопроса заключается в том, что сортировку слов вопроса ЧАВО по синсетам осуществляет пользователь. Таким образом, получается, что уже при вводе вопроса ЧАВО исключается многозначность его толкования.

9. Результаты работы.

Результатами работы следует считать написание двух вопросно-ответных систем:
1. Работающая с использованием словаря WordNet.
2. Использующая базу MySQL для хранения словаря.
Обе системы работают идентично. Механизм сравнения вопросов пользователя и вопросов ЧАВО полностью перенесен из системы 1 в систему 2 и построен на использовании матрицы соответствия.
Различие систем заключается в следующем:
1. Изменен формат и средства хранения данных.
2. Для доступа к данным мспользован PHP вместо C++.
3. Деревья синсетов строятся не динамически в памяти, а в таблицах MySQL.
Я не зря потратил несколько листов на описание структуры словаря WordNet. Дело в том, что словарь в MySQL строился мной таким же образом. Определялись те же самые связи, точно также вводились деревья гиперонимов.
Хотя в системе и предусмотрена возможность определения произвольных связей, эксперименты в этом направлении не проводились.
На этом основании справедливо полагать, что результаты работы системы 1 полностью проецируются на систему 2 при условии одинаковости словаря.


10. Будущие планы (вместо заключения).

Несмотря на то, что диплом является своего рода завершением проекта, мне хотелось бы упомянуть о дальнейшем плане работ по созданию вопросно-ответных систем. Конечно, первоочередной задачей будет построение словаря и проверка работы системы на реальных вопросах с реальными пользователями. Предстоит изменить интерфейс администратора, сделать его менее громоздким и более понятным для пользователя. Хотелось бы автоматизировать ряд функций, так как вариант, существующий сейчас, подходит только для небольших словарей.
Возможно, механизм составления словаря будет позаимствован из WordNetа. Т.е. пользователь готовит исходные файлы в текстовом формате, которые потом автоматически преобразуются в словарь. Такой метод делает невозможным on-line изменение словаря, зато ускоряет скорость доступа к нему.
Необходимо дополнить систему модулем морфологического анализа. Добавить возможность работы со словосочетаниями.


Литература.

1. Robin D. Burke, Kristian J. Hammond, Vladimir A. Kulyukin, Question Answering from Frequently-Asked Question Files: Experiences with the FAQ Finder System.
2. George A. Miller, Introduction to WordNet: An On-line lexical database.
3. Alexander Budanitsky, Graeme Hirst, Semantic Distance in WordNet: An experimental, application-oriented evaluation of five measures.
4. Eduard Hovy, Laurie Gerber, Ulf Hermyakob, et al, Question Answering in Webclopedia.
5. Richard J. Cooper, Stefan M. Ruger, A Simple Question Answering System.
6. Ellen M. Voorhees, Overview of TREC 2001 Question Answering Track
7. John Prager, Jennifer Chu-Carrol, Use of WordNet Hypernyms for Answering What-Is Questions.
8. Dan Roth, Learning Components for a Question-Answering System.