авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

Национальный исследовательский университет “Высшая школа экономики”

На правах рукописи

Кириллов Антон

Владимирович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ПРОГРАММНАЯ

РЕАЛИЗАЦИЯ СЕМАНТИЧЕСКОГО ПРЕОБРАЗОВАНИЯ

ПОИСКОВЫХ ЗАПРОСОВ

Специальность 05.13.18 – Математическое моделирование, численные методы

и комплексы программ

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н В.А.Фомичев Москва – 2012 2 СОДЕРЖАНИЕ СОДЕРЖАНИЕ..................................................................................................... 2 ВВЕДЕНИЕ............................................................................................................ Глава 1. Основные подходы к поиску информации в электронных документах................................................................................................................................... Традиционные поисковые системы....................................................... 1.1.

Формальные компоненты поисковой системы............................... 1.1. Логический метод определения множества претендентов............ 1.1. Проблема ранжирования: переход от ~ к................................... 1.1.3 Логический метод ранжирования................................................ 1.1.3. Ранжирование на основе вектора документа.............................. 1.1.3. Реалистичные модели ранжирования.......................................... 1.1.3. Оценка качества документа на основе цитирования: алгоритм 1.1. PageRank.......................................................................................................... Вычисление рейтинга страницы по алгоритму PageRank......... 1.1.4. Наглядное обоснование................................................................. 1.1.4. Семантический поиск............................................................................. 1.2.

Естественно-языковые поисковые системы......................................... 1.3.

Обзор зарубежных естественно-языковых поисковых систем..... 1.3. Обзор отечественных естественно-языковых поисковых систем 1.3. Постановка задачи диссертационного исследования.......................... 1.4.

Выводы по главе 1................................................................................... 1.5.

Глава Формализация и алгоритмизация обработки аспектно 2.

ориентированных запросов................................................................................ Состояние исследований по семантической обработке вопросов на 2. естественном языке............................................................................................. Базовые принципы нового подхода к семантически-ориентированному 2. поиску информации в Интернете...................................................................... Разработка принципов семантического расширения аспектно 2. ориентированных запросов................................................................................ Центральные идеи предлагаемого подхода.................................... 2.3. Первичные информационные единицы для разработки алгоритма 2.3. анализа аспектно-ориентированных запросов............................................ Краткая характеристика теории К-представлений.............................. 2. Разработка математической модели проблемно-ориентированной 2. системы первичных единиц концептуального уровня.................................... Разработка плана алгоритма построения семантического расширения 2. аспектно-ориентированного поискового запроса............................................ Анализ структуры входных запросов аспектно-ориентированного 2. типа……………………………………………………………………………… Формализация предположений о входном языке аспектно 2. ориентированных поисковых запросов............................................................. Основные идеи разработки алгоритмов определения типа и объектов 2. интереса входных запросов................................................................................ Алгоритмы определения типа аспектно-ориентированного вопроса и 2. его объектов интереса......................................................................................... Алгоритм определения типа запроса........................................... 2.10. Алгоритм определения объектов интереса запроса................... 2.10. Разработка алгоритма построения семантического расширения 2. аспектно-ориентированного поискового запроса............................................ Обсуждение разработанных алгоритмов.............................................. 2. Выводы по главе 2.................................................................................. 2. Глава 3. Разработка алгоритмов семантического преобразования обобщенных запросов на основе математических моделей компонентов базы знаний.... Разработка принципов семантического расширения обобщенных 3.1.

запросов достижения целей............................................................................... Формальная модель базы знаний для представления целей.............. 3.2.

Анализ структуры запросов достижения целей................................... 3.3.

Разработка алгоритма определения типа вопросов достижения целей и 3.4.

их объектов интереса.......................................................................................... Метод преобразования вопросов достижения целей к расширенному 3.5.

виду……………………………………………………………………………. Разработка принципов семантического расширения обобщенных 3.6.

запросов об изменениях состава множеств...................................................... Разработка формальной модели базы знаний для описания изменений 3.7.

состава множеств.............................................................................................. Анализ структуры запросов об изменениях составов множеств..... 3.8.

Разработка алгоритма определения типа запросов об изменениях 3.9.

составов множеств и их объектов интереса................................................... Метод построения семантического расширения вопросов об 3.10.

изменениях в составе множеств...................................................................... Разработка итоговой модели базы знаний для поддержки поиска.. 3.11.

Выводы по главе 3................................................................................ 3.12.

Глава 4. Программная реализация системы семантически-ориентированного поиска на основе предложенного метода и исследование полученных результатов......................................................................................................... 4.1 Разработка и реализация архитектуры программного комплекса AOS Engine.................................................................................................................. 4.1.1Разработка концептуальной архитектуры программного комплекса... Разработка компонентной архитектуры программного комплекса. 4.1. Общая архитектура программного комплекса и выбор 4.1.2. платформы реализации........................................................................ Лингвистическая база знаний............................................. 4.1.2. Аспектно-ориентированная база знаний........................... 4.1.2. Подсистема AOS Engine...................................................... 4.1.2. Выбор платформы реализации........................................... 4.1.2. Разработка итогового алгоритма построения расширенного множества 4. запросов и ранжирования результатов............................................................ Исследование полученных результатов.............................................. 4. Выводы по главе 4................................................................................. 4. Заключение........................................................................................................ СПИСОК ЛИТЕРАТУРЫ................................................................................ ПРИЛОЖЕНИЯ................................................................................................. Приложение 1. Структура и примеры входных аспектно-ориентированных запросов.............................................................................................................. Приложение 2. Система продукций разработанной КС-грамматики.......... Приложение 3. Полная таблица записей словарей, используемых для анализа структуры входных запросов........................................................................... Приложение 4. Алгоритмы............................................................................. Приложение 5. Анализ структуры понятий, являющихся множествами.... Приложение Примеры построения множества семантически 6.

преобразованных запросов............................................................................... Приложение 7. Экранные формы программных компонентов.................... Приложение 8. Данные для баз знаний........................................................... Приложение 9. Акты внедрения...................................................................... ВВЕДЕНИЕ Актуальность темы исследования. В настоящее время параллельно с ростом объемов информации в Интернете происходит разработка новых и совершенствование существующих подходов к ее поиску. Все большую актуальность приобретают средства семантического поиска, под которыми понимаются системы, принимающие на вход некоторый запрос, обрабатывающие его с использованием рассуждений над специфичной базой знаний и возвращающие совместимые результаты. Входным запросом может являться, например, вопрос на естественном языке (ЕЯ), представление вопроса при помощи триплетов, графическое представление, набор ключевых слов, отдельные фразы и т.д. В роли базы знаний могут выступать онтологии, аннотированные массивы текста, текстовые документы, Веб, XML- документы, RDF документы, HTML документы и т.д. В нашей стране значительный вклад в развитие семантического поиска внесли Э.Э. Гасанов, А.Е. Ермаков, А.Н.

Королев, И.П. Кузнецов, Д.Г. Лахути, Н.Н. Леонтьева, М.Г. Мальковский, А.Г.

Мацкевич, А.С. Нариньяни, И. С. Некрестьянов, Г.С. Осипов, И.В. Сегалович, А.В. Сокирко, Н.В. Перцов, Н.Н. Перцова, Э.В. Попов, В.Ш. Рубашкин, И.А.

Тихомиров, В.О. Толчеев, В.А. Тузов, В.А. Фомичёв, Н.П. Харин, В.Ф.

Хорошевский и другие учёные.

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

Объект исследования: методы семантической обработки поисковыми системами естественно-языковых запросов.

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

разработать такой метод семантического Цель исследования:

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

Задачи исследования:

1.Провести анализ состояния исследований по семантической обработке поисковыми системами вопросов на естественном языке (ЕЯ) с целью выявления классов вопросов, недостаточно проработанных в научной литературе и имеющих большую практическую значимость для систем естественно-языкового поиска.

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

Выбрать наиболее соответствующую предложенному методу 3.

методологическую основу исследования для построения математических моделей компонентов базы знаний, необходимых для семантического преобразования естественно-языковых запросов.

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

5. На основе предложенных моделей разработать алгоритмы анализа и преобразования поисковых запросов в форму (множество производных запросов), позволяющую повысить релевантность документов, выдаваемых системами поиска по ключевым словам. Разработать алгоритм ранжирования результатов по степени релевантности поисковому запросу.

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

Провести тестирование разработанного программного комплекса и 7.

проанализировать полученные результаты.

Теоретико-методологическую основу исследования составляют теория алгоритмов, теория графов, теория контекстно-свободных грамматик, теория К-представлений, методы теоретического программирования и Веб программирования.

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

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

Впервые предложен Теоретическая значимость исследования.

базирующийся на математической модели подсистемы базы знаний метод семантического преобразования ЕЯ-запросов поисковых систем (ПС) в форму (множество производных запросов), позволяющую повысить релевантность результатов работы систем поиска по ключевым словам.

Практическая значимость исследования состоит в том, что предложен новый подход к анализу и преобразованию ЕЯ-запросов ПС в такую форму (множество производных запросов), которая позволяет повысить релевантность документов, получаемых от традиционных ПС. Данный подход базируется на построении математических моделей семантических объектов, которые используются алгоритмами построения множества преобразованных запросов.

Разработанные алгоритмы позволяют определять типы и подтипы ЕЯ-запросов поисковой системы, а также выделять объекты интереса запросов. На основе разработанной модели базы знаний для поддержки преобразования запросов и поиска в зависимости от типа запроса и выделенных объектов интереса происходит построение множества семантически преобразованных запросов, которые подаются на вход традиционной ПС. Разработанный алгоритм ранжирования результатов поисковой выдачи позволяет повысить релевантность результатов по сравнению с системами поиска по ключевым словам. Математический подход, базирующейся на теории К-представлений, является предметно независимым и может быть использован при проектировании базы знаний для поддержки преобразования запросов и поиска в разных предметных областях. Важным аспектом практической ценности разработанного комплекса является возможность его интеграции с любым количеством поисковых систем, а также возможность управления информацией в базе знаний с целью повышения соответствия результатов поиска информационной потребности пользовате-лей, что не требует внесения изменений в разработанные алгоритмы.

Полученные в диссертации результаты использованы в научных и проектных исследованиях компании Голосовые «Вокском – Телекоммуникации» (Москва), а также в лекционных и лабораторных занятиях по дисциплине «Проектирование лингвистических процессоров» на кафедре «Информационные технологии» «МАТИ» – Российского государственного технологического университета им. К.Э. Циолковского.

Основные положения, выносимые на защиту:

1. Разработан комплекс математических моделей семантических и семантико-синтаксических объектов, предназначенных для расширения пользовательских поисковых запросов:

Математическая модель проблемно-ориентированной системы 1.1.

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

1.2. Математическая модель концептуальной базы целей, используемая для преобразования запросов о достижении целей.

1.3. Математическая модель базы знаний об изменениях множеств, используемой для поддержки преобразования запросов об изменениях множеств.

1.4. Итоговая математическая модель базы знаний для поддержки семантического преобразования запросов и поиска.

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

3. Разработаны метод и алгоритм построения множества преобразованных запросов.

4. Разработан программный комплекс, реализующий предлагаемый метод семантического преобразования поисковых запросов и использующий разработанные алгоритмы. Разработанный программный комплекс был успешно развернут по адресу http://www.aosengine.ru.

5. Разработана КС-грамматика в форме Бэкуса-Наура для описания входного языка поисковых запросов пользователей.

Апробация и внедрение результатов исследования. Основные результаты работы представлялись и получили одобрение на научно практической конференции студентов и аспирантов «Информационные технологии в экономике, бизнесе, управлении» (ГУ-ВШЭ, 2010), на IX Международной научно-технической конференции «Новые информационные технологии и системы» (НИТиС-2010), на молодежной научной конференции «Гагаринские чтения» в МАТИ (2011) и на научном семинаре «Математические модели информационных технологий» Отделения прикладной математики и информатики факультета бизнес-информатики НИУ ВШЭ в 2012 году. По теме диссертационной работы опубликовано 7 научных работ, включая две статьи в изданиях из списка изданий, рекомендованных ВАК РФ. Разработанный в диссертации программный комплекс был развернут по адресу http://www.aosengine.ru/.

Структура диссертации: основной текст диссертации изложен на страницах, состоит из введения, четырёх глав, заключения, списка литературы из 100 наименований и девяти приложений.

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

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

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

Анализируется структура запросов аспектно-ориентированного типа и разрабатывается математическая модель проблемно-ориентированной системы первичных единиц концептуального уровня с целью создания основы для разработки алгоритмов семантического преобразования запросов данного типа.

Предлагается новый метод формального описания структуры входных текстов анализатора аспектно-ориентированных запросов рассматриваемых видов на основе аппарата контекстно-свободных грамматик.

Разрабатываются план алгоритма семантического преобразования аспектно-ориентированных запросов и вспомогательный структурированный алгоритм определения типа и объектов интереса запросов данного вида.

В третьей главе анализируются запросы достижения целей, строится математическая модель компонента базы знаний поисковой системы, необходимого для семантического преобразования вопросов о достижении/недостижении цели. Для этого определен класс формальных объектов, названных концептуальными базами целей (к.б.ц.). В отличие от понятия концептуального базиса, введенного в теории К-представлений В.А.Фомичева, концептуальные базы целей включают формальные представления целей интеллектуальных систем (в том числе организаций), являющиеся выражениями СК-языков (стандартных концептуальных языков).

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

Разрабатывается метод преобразования вопросов достижения целей в множество производных запросов на основе концептуальной базы целей и набора шаблонов семантической трансформации. Преимуществом метода является компактность представления данных, позволяющих построить семантическое расширение запроса о достижении/недостижении цели.

Предлагаются метод и алгоритм построения семантического расширения вопросов об изменениях множеств. Строится математическая модель компонента базы знаний поисковой системы, необходимого для семантического преобразования вопросов об изменениях множеств. Для этого определен класс формальных объектов, названных базами знаний об изменениях множеств. В отличие от понятия концептуального базиса, введенного в теории К-представлений В.А.Фомичева, базы знаний об изменениях множеств включают формальные представления составных элементов множеств и индикаторов изменений состава множеств.

В рассматривается логическая архитектура четвертой главе разрабатываемого программного комплекса и формулируются основные требования к программной реализации. На основании разработанной логической архитектуры и требований проектируется компонентная архитектура решения, состоящего из трех основных подсистем:

лингвистической базы знаний, аспектно-ориентированной базы знаний и подсистемы анализа и расширения запросов – AOS Engine.

Далее в главе разрабатывается итоговый алгоритм построения расширенного множества запросов для любого из рассмотренных типов и подтипов, основанный на предложенном методе.

Разрабатываются требования к компонентам и подсистемам программного комплекса, на этой основе выбираются платформа реализации и библиотеки, удовлетворяющие сформулированным требованиям.

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

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

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

Самыми распространенными примерами поисковых систем, встречающихся повсюду, являются поисковые системы для Веба (такие как Google и Yahoo, например), которые используются для обнаружения текстовой информации (например, документов в формате HTML и PDF), хранящейся на веб-серверах, расположенных по всему миру. Схожие технологии используются и при поиске информации в корпоративных внутренних сетях.

1.1.1 Формальные компоненты поисковой системы Большинство поисковых систем состоит из двух основных компонентов, которыми являются и компонент индексирования компонент поиска.

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

Формально компонент индексации может быть представлен функцией I : U R, где U - это множество, которое называется универсумом и содержит данные, среди которых будет вестись поиск. Для поисковой системы Интернета – это страницы, которые мы загружаем из сети, для графической поисковой системы им будет являться набор изображений, а для академической поисковой системы универсум будет представлен, например, собранием работ, статей и книг. Множество R является внутренним представлением универсума U, называется репозиторием. Репозиторий имеет вид R = { d | 1 d n}. Каждое d является документом, где d - соответствующий уникальный идентификатор документа, называющийся DOCID. Когда речь идет о документе d, используется преобразование d a d. Каждое представление d зависит, в первую очередь, от поисковой системы.

Следует отметить, что функция I обычно применяется к подмножеству U ' множества U, и поэтому поиск происходит только в части всего репозитория R ' = I(U ' ). Объясняется это тем, что множество U слишком велико, чтобы быть проанализировано полностью (см. ниже).

Проиллюстрируем концепцию индексирования на примере поисковой системы для Веба. Местонахождение веб-страниц обычно определяется по унифицированному указателю ресурса Пример (URL) [75]. URL:

«http://www.hse.ru». При индексировании система имеет дело с набором URL различных документов в Вебе называются и страницами) (которые последовательно присваивает всем документам идентификаторы (DOCID).

Затем данные страницы выгружаются из Веба в репозиторий, т.е. хранилище внутренних представлений каждой из страниц. Количество выгружаемых страниц обычно очень велико (в современных поисковых системах это порядка 1010 документов), но, тем не менее, оно значительно меньше реального числа страниц в U, т.е. количества страниц, находящихся в Интернете. Таким образом, одной из основных задач построения поисковых систем для Веба U' является определение адекватного подмножества.

Рассмотрим компонент поиска, который обращается к документам, расположенным в репозитории, для того, чтобы осуществить выборку, соответствующую поисковому запросу. Формально, поисковый компонент может быть представлен как функция S : a, где - поисковый запрос, конечная строка, введенная пользователем (принадлежащая используемому алфавиту). Поисковый запрос принято считать состоящим из термов, являющихся атомарными словами, поиск которых ведется, и операторов, которые описывают, как интерпретировать термы. Например, в поисковом запросе «цепи Маркова», запрос состоит из термов 1 = цепи и 2 = Маркова.

Оператором в данном случае будет являться логическое И, что описывает ситуацию, когда нам необходимы документы, содержащие оба этих терма.

- это результат, являющийся упорядоченным набором (или же вектором) отдельных документов: = ( 1, 2,..., r ) ~ (1, 2,..., r ), где используется свойство изоморфности документов, такое, что i : s фактически является идентифика r = | | тором документа(DOCID). Количество возвращаемых документов называется выборкой для данного поискового запроса. Очевидно, что 0 r n.

Результат - это информация, представляемая пользователю. Элементы это все документы, которые поисковая система сочла достаточно подходящими для включения в результирующий набор. Более того, элементы в результирующем множестве расположены в таком порядке, что считается i более значимым для пользователя, чем i+1. При обычном веб-поиске документов, представленных на первой странице результатов, будут соответствовать Точность определяется долей возвращенных - 10.

документов, которые фактически релевантны, т.е.

|{Релевантные _ документы} | Точность = | | Здесь понятие релевантности является абсолютно произвольным и полностью зависит от поисковой системы (или, возможно, от ее пользователей).

Рассмотрим проблему получения на основании поискового запроса и репозитория R. Поисковая система обычно осуществляет выборку в два этапа:

1. Выбор множества претендентов ~ R, такого, что все элементы ~ в той или иной степени релевантны поисковому запросу. Определение релевантности на данном этапе очень приближенное. Например, может быть использован логический метод, рассматриваемый далее.

2. Для каждого i ~ определяется его релевантность Rel ( i ), а затем ~ сорти руется в порядке уменьшения релевантности. При сортировке некоторые элементы, имеющие релевантность ниже порогового значения, могут быть исключены из выборки. Результирующей выборкой будет являться.

1.1.2 Логический метод определения множества претендентов Рассмотрим процесс определения множества претендентов ~, который обычно происходит с использованием логического метода. Основная идея данного метода заключается в том, что результирующее множество поискового запроса (например, «цепи Маркова») должно содержать только страницы, относящиеся ко всем уникальным термам запроса (в данном случае ими будут являться «Маркова» и «цепи»). Затем ответ на поисковый запрос может быть дан после просмотра всех документов, содержащих термы «Маркова» и «цепи», используя пересечение множеств документов, содержащих любой из этих термов (или оба терма), как результирующее множество претендентов. Это объясняется тем, что основной задачей компонента индексации является построение инвертированного индекса, являющегося структурой данных, в которой термам в соответствие ставятся документы (или же DOCID), содержащие данные слова. В Таблице представлен пример 1. инвертированного индекса - одной из важных частей вышеупомянутого внутреннего представления документов. Запрос, таким образом, подвергается декомпозиции в древовидную структуру с термами (т.е. атомарными словами или фразами) в качестве листьев и логическими операторами в качестве узлов.

Наиболее используемыми логическими операторами являются AND, OR и равнозначные операциям и NOT, (пересечения), (объединения) (дополнения) между множествами DOCID соответственно. В дальнейшем эти символы будут использованы для того, чтобы различать операции над множествами и логические операции. AND обычно используется в случае отсутствия оператора между двумя термами. Примеры логических представлений поисковых запросов представлены в Таблице 1.2.

Логическое сравнение – это простой путь получения ~ потенциально реле вантных документов, не представляющий их в порядке соответствия запро-су.

Поэтому используются разные методы при сортировке ~ и при получении.

Таблица 1.1. Пример инвертированного индекса.

Терм DOCID документов, содержащих данный терм Маркова 35, 678, 432,1839, 6456, … цепи 7834, 889, 8912, 325, 91, … Таблица 1.2. Примеры логических интерпретаций поисковых запросов.

Запрос Логическая интерпретация Маркова Цепи {Маркова} {Цепи} Маркова -Цепи {Маркова} {Цепи} Маркова (Цепь OR Процесс) {Маркова} ({Цепь} {Процесс}) 1.1.3 Проблема ранжирования: переход от ~ к После определения ~ происходит поиск зависимой от поискового запроса Rel : ~ [ 0, ) функции ранжирования или релевантности такой, что Rel ( i ) Rel ( j ), если элемент i считается более релевантным запросу, чем j, и, таким образом, должен быть расположен в до него. Другими словами результирующее множество нужно отсортировать по убыванию значения Функции класса определяют схему ранжирования, т.е. те Rel. Rel характеристики документа, которые были определены как значимые при формировании результатов для определенного поискового запроса.

Логический метод в той или иной степени является применимым к любому набору данных, однако проблема ранжирования в высшей степени зависит от окружения U, из которого данные были извлечены. Например, поисковые системы для веба постоянно сталкиваются с проблемой спама: веб-страницы, которые пытаются поисковые системы, предоставляя «перехитрить»

необычайно высокое значение Rel для конкурентоспособного : s, тем самым рассчитывая на увеличение количества появлений страницы в результатах поиска. Данная проблема приводит к тому, что функция Rel должна определяться как можно тщательнее и скептически. Тем временем также не стоит отсеивать «честные» документы. Это приводит к тому, что решение проблемы ранжирования результатов в неконтролируемой среде становится очень востребованным и перспективным. Обычно спам не является проблемой в более контролируемых средах, таких как поисковые системы для академических работ или внутренних сетей.

Рассмотрим ранжирование в неконтролируемых средах, таких как Веб. Здесь функция ранжирования принимает в расчет как внешние факторы (on-page factors): информационное содержимое и его размещение на странице, так и внутренние факторы (inter-page factors): обычно, информация о том, как страницы соотносятся с другими посредством гиперссылок и т.п. Основное внимание следует уделить внутреннему фактору гиперссылок между страницами, однако сделаем небольшой обзор процесса ранжирования в целом.

Мотивацией к изучению внутренних факторов является то, что все внешние факторы находятся под полным контролем автора страницы. Изучение различных отношений внутри документа с гораздо большим числом страниц позволяет более эластично оценить качество исследуемой страницы.

В общем случае, функция ранжирования поисковой системы для Веба выбирается следующим образом:

Rel ( ) = (, )q(), (1.1) где (, ) является показателем документа для запроса по внешним факторам, т.е. насколько релевантна информация, расположенная на странице, по отношению к запросу, а q ( ) является качественной функцией от, которая рассчитывается на основании факторов, не представленных непосредственно на самой странице. Качественная функция q может включать в себя внутренние факторы страницы и признаки ручного вмешательства (т.е.

страница была специально изменена для поднятия рейтинга и позиции в результатах поиска). Следует отметить, что q не является функцией, зависящей от запроса, а скорее присваивает обобщенный весовой коэффициент каждой странице независимо от запроса. Функция q принимает значения в пределах [0;

1], таким образом, умножение на q используется для дампинга рангов документов (т.е. набранных ими «очков» по внешним факторам). Рассмотрим далее три возможных метода определения (, ).

1.1.3.1 Логический метод ранжирования Представим простейшую поисковую систему, принимающую (, ) =1, в результате имеющую Rel ( ) = q( ). Результирующее множество будет состоять исключительно из множества претендентов ~, отсортированного по убыванию значения q. Так функционирует чисто логическая поисковая система: все страницы, имеющие любое отношение к термам, которые ищет пользователь, одинаково релевантны поисковому запросу.

1.1.3.2 Ранжирование на основе вектора документа Рассмотрим подход к ранжированию с использованием вектора документа, который является достаточно популярной технологией.

Первым предположением в данной модели является то, что документ должен иметь высокий рейтинг по терму i, если данный терм часто встречается на этой странице. Предположим, что запрос 2 состоит из L термов: 1.. L. Зададим частоту термов, TF ( ), как отношение количества i появлений терма i в документе к размеру ( S ) документа в некоторых удобных единицах измерения (например, количество слов или байтов).

Далее, предположим, что некоторые термы более значимы при поиске, чем другие. Стандартный метод определения значимости термов заключается в нахождении обратной частоты документа (Inverse Document Frequency, IDF).

Предположим, Ri является подмножеством репозитория R и состоит из документов, содержащих терм i. Вероятность того, что документ, выбранный |R |.

случайно, будет содержать терм i, такова: p = В теории информации i |R| Шэннона [92] это соответствует собственной информации (self-information) ). На основании этого определяется инверсивная частота документа log 2 ( p |R| ), |R | IDF(i ) = log( i т.е. логарифм отношения общего числа документов в репозитории к количеству документов, содержащих терм i (обычно принято использовать логарифм по основанию 10). Инверсивная частота документа представляет собой оценку количества информации, свойственной терму. Если терм часто встречается в документах, находящихся в репозитории, то вероятность того, что он весьма общий, высока, и поиск определенного ресурса при помощи поисковой системы не даст значительных результатов, поэтому ему присваивается низкое значение IDF. В Таблице 1.3 представлены примеры вычисленных значений IDF для некоторых термов (в примере используются словосочетания), относящихся к хорошо известной теории множеств, но с возрастающей степенью обобщения и, поэтому, с убывающим количеством содержащейся в документах полезной информации.

TF и IDF будут использоваться для определения оценки документа. Для каждого ~ определим вектор документа, состоящий из L элементов (по одному для каждого терма), такой, что выполняется соотношение:

[ ]i = IDF(i ) TFi ( ).

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

|R| Таблица 1.3. вычисленные поисковой системой Yahoo, при IDF, приблизительно равном 20 10 Терм Количество вхождений IDF теорема Перрона - Фробениуса 8270 6. цепь Маркова 1050000 4. Теория вероятностей 10900000 3. математика 92900000 2. наука 816000000 1. Можно рассматривать поисковый запрос (ПЗ) как документ сортов, в кото ром каждый из термов запроса встречается только один раз. Пусть - это L вектор для каждого i = S1 IDF ( i ), где S - это размер ПЗ, представленный в тех же единицах измерения, что и размер упоминавшегося документа. Помимо этого, можно рассматривать это как вектор документа для запроса. Поскольку неизвестно, как пользователь задает приоритеты термам в его запросе, весовые коэффициенты термам будут присвоены в соответствии с их IDF.

Определим зависящую от запроса часть функции отношения, т.е. (, ) в (1.1), чтобы установить соответствие между и, а определением соответствия, в данном случае, будет являться угол между векторами в L пространстве:

(, ) = cos( (,)) = (1.2) 2 Пример 1. Продемонстрируем векторную модель на практике, рассмотрев процесс поиска для запроса «связный граф».

В хорошо известной поисковой системе для Веба можно обнаружить примерно 20 10 9 документов, в которых терм «связный» встречается в 7 10 документах, а терм «граф» в 150 10 6 документах. Таким образом, значения IDF будут следующими: IDF(связный) = 0.46 и IDF(граф) = 2.1. Используя количество слов, как единицу измерения, получаем размер запроса, равный 2, и вектор запроса = (1 IDF (связный ),1 IDF ( граф)) = (0.23,1.05). Нужно сравнить по релевантности два документа A и B, которые, предположим, одного размера.

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

Таблица 1.4. Количество вхождений термов запроса в документы и соответствующие векторы документов.

Документ A Документ B Количество вхождений терма «связный» 10 Количество вхождений терма «граф» 4 Вектор документа A = ( 4.6,8.4 ) B = ( 0.92,6.3 ) A = 9.6 B = 6. Оценка (по (2)) 0.96 0. Простой подсчет количества вхождений термов дает преимущество документу A, однако видно, что B фактически лучше удовлетворяет запросу.

Это интуитивно доказуемо. Например, большее число вхождений терма «связный» в документе A показывает, что этот документ посвящен связям в несколько другом контексте, чем «связные графы», и поэтому слабо удовлетворяет запросу.

1.1.3.3 Реалистичные модели ранжирования Большинство поисковых систем в действительности используют улучшенную модель вектора документа. Тем не менее, существует множество противников данной модели, т.к. самый существенный ее недостаток в том, что подход, использующий подсчет частоты вхождений термов, может дать ошибочные результаты, т.к. количество слов на странице подсчитывается «вслепую». Поэтому вносятся корректирующие коэффициенты, основанные на таких факторах, как расположение термов относительно друг друга, статистические измерения корреляции между термами и аспектами форматирования страницы (такими как шрифт и размер шрифта, которым представлены термы). Одним из популярных методов ранжирования является OKAPI BM25 [93], где рейтинг документа вычисляется на основе формулы:

(k + 1 )TF ( ) IDF( i, (, ) = ) i d TF ( ) + k( 1 b + b ) i d i где, обычно, k=1.2, b=0.75, d - длина документа (т.е. количество слов в документе) и d - средняя длина всех документов. Данная функция пытается нормализовать рейтинги документов, исходя из их длины: большой документ может содержать гораздо больше повторений отдельных термов, чем маленький, и, тем не менее, быть менее релевантным запросу.

Следующим улучшенным вариантом является функция OKAPI BM25F, в которой ранжирующая функция разбивается на части относительно полей документа, таких как заголовки, ссылки, основной текст и т.д.

Однако у всех представленных методов существует еще одна проблема.

Пользователь, совершающий поиск, ожидает найти авторитетную информацию в результатах поиска раньше, чем все остальное. Хотя в большинстве случаев стандартные слова в поисковом запросе не выделены особым образом на анализируемых при поиске страницах. Например, не все производители автомобилей используют слово «машина» на своих веб-сайтах! Более того, неавторитетные или даже вредоносные ресурсы могут легко обогнать авторитетные по рейтингу, просто используя термы несколько раз на своих страницах: например, при поиске «Volvo», главная страница компании Volvo будет находится гораздо ниже в рейтинге, чем локальные дистрибьюторы автомобилей, использующие слово «Volvo» десятки раз у себя на страницах.

Это не тот результат, который нужен. Необходимо решение, которое позволило бы оценивать качество страницы независимо от запроса.

Эта проблема, а также проблема спама, являются основными причинами введения в функцию ранжирования (1) коэффициента q( ).

1.1.4 Оценка качества документа на основе цитирования: алгоритм PageRank Рассмотрим один из наиболее популярных и широко используемых методов оценки качества документов, основанный на подсчете количества ссылок между документами, так называемый рейтинг цитируемости. Примерами цитат могут служить список цитированной литературы в научных работах или гиперссылки между веб-страницами. Идея рейтинга цитируемости заключается в определении качественной оценки документа на основании количества и качества ссылающихся на него документов.

Абстрагируясь от того, что цитата представляет собой только ссылку с одной страницы на другую без каких-либо специфических атрибутов (т.е. не учитывается размещение ссылки в документе, ее формат и т.д.), можно представить ссылочную структуру в виде графа. Предположим, репозиторий состоит из n документов, имеющих уникальные идентификаторы DOCID, последовательно присвоенные документам и находящиеся в интервале V = [1, n].

Определение 1. Цитатой, или ссылкой, называется упорядоченная пара документов (i, j) V 2. Ссылками называются исходящая связь документа i и входящая связь документа j.

Сформировав из всех ссылок между документами из V множество E, становится ясно, что G=(V,E) является ориентированным графом с вершинами, являющимися ссылками. Назовем данный граф графом ссылок.

Определение 2. Пусть G=(V,E) и i V. Тогда множество входящих связей будет обозначаться как I(i), а множество исходящих связей как O(i), т.е.

I(i) = {e E | e = (j,i), j V }, O(i) = {e E | e = (i, j), j V }.

|I(i)| Рейтинг Страница I(i) 1 {2} 1 0. 2 {1,3} 2 0. 3 {1,2} 2 0. 4 {1,2,3,5} 4 0.36 5 {1} 1 0. 6 {4} 1 0. Рисунок 1.1. Индекс цитирования с подсчетом входящих связей.

Определение 3. Документ i V называется висячим, если O(i) =.

Пример 2. Тривиальным примером для рейтинга цитируемости будет служить q(i) = const |I(i)|, т.е. документу i присваивается рейтинг, прямо пропорциональный числу документов, ссылающихся на него. На Рисунке 1. представлен граф, в котором простой подсчет входящих связей для каждого узла и формирует представленные показатели рейтинга (после нормализации по общему числу связей в графе).

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

Проблема поиска метода оценки качества ссылок, который бы работал в такой разнородной среде, как Веб, наиболее успешно решилась с изобретением алгоритма PageRank. Алгоритм разработан Сергеем Брином и Лоренсом Пейджем и в дальнейшем послужил частью технологической базы поисковой системы Google (www.google.com). Впервые алгоритм был описан в [42] и [81], после этого была проведена многолетняя работа на основе этих публикаций.

1.1.4.1 Вычисление рейтинга страницы по алгоритму PageRank Можно провести аналогию между списками использованной литературы в академических работах и ссылками на определенные страницы в Вебе. Подсчет ссылок на страницу из разных источников дает приближенное значение важности или, другими словами, качества страницы. Алгоритм PageRank расширяет данный подход не только подсчетом количества ссылок (принимая значимость ссылок с каждой из страниц равной), но и упорядочивая страницы по количеству ссылок, содержащихся в них. Рейтинг страницы по PageRank определяется следующим образом [81]: Предположим, что на документ A ссылаются страницы T1...Tn. Параметр d является коэффициентом затухания, находящимся в интервале (0;

1). Обычно d присваивается значение равное 0.85.

C(A) определяет количество исходящих со страницы A ссылок. Тогда рейтинг страницы A по PageRank определяется как PR(A) = ( 1 d) + d(PR(T1 ) / C(T1 ) +... + PR(Tn ) / C(Tn )).


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

Рейтинг PageRank (PR(A)) может быть вычислен с использованием простого итеративного алгоритма и будет соответствовать главному собственному вектору нормализованной матрицы ссылок. Нужно отметить, что рейтинг PageRank для 26 миллионов веб-страниц может быть вычислен за несколько часов на рабочей станции средней мощности [42].

1.1.4.2 Наглядное обоснование Алгоритм можно рассматривать как модель поведения PageRank пользователя. Предполагается, что веб-серфер (пользователь, «путешествующий» по веб-страницам, т.е. переходящий по ссылкам с одной на другую) с заданной случайным образом стартовой страницы переходит по ссылкам (также выбирая их случайным образом) на другие страницы и никогда не возвращается на предыдущую страницу, иногда прерывая переход по ссылкам и начиная снова с другой случайной страницы. Вероятность того, что веб-серфер посетит определенную страницу и является ее рейтингом PageRank.

А коэффициент затухания d определяет, насколько скоро веб-серфер начнет процесс заново, перейдя на случайную страницу. Единственное важное различие в задании фактора d заключается в том, что он может быть присвоен как группе страниц, так и отдельным страницам. Данный подход позволяет персонализировать выборку и сводит к минимуму вероятность того, что система ошибется, присваивая странице рейтинг. Существует несколько расширений алгоритма Page Rank, описанных в [82].

Другое наглядное обоснование того, что страница может иметь высокий рейтинг заключается в определении количества страниц, PageRank, ссылающихся на нее и имеющих также высокий рейтинг PagRank. Таким образом, страницы, на которые ссылается множество документов в вебе, являются более предпочтительными. Также страницы, имеющие хотя бы одну ссылку, например, с домашней страницы являются более Yahoo!, предпочтительными. Если ссылка на страницу не работает или страница низкого качества, то маловероятно, что домашняя страница Yahoo! будет ссылаться на нее. PageRank анализирует подобные ситуации, а также рекурсивные ссылки нескольких страниц, посредством которых их владельцы пытаются повысить их рейтинг.

1.2. Семантический поиск Так же, как и в ситуации с Всемирной Сетью, рост Семантического Веба будет обуславливаться развитием возможностей его применения.

Семантический поиск – это процесс поиска информации, основанный на установлении соответствия между смысловым содержанием запроса и смыслом текста, представленного в документах целевого репозитория. Поиск является наиболее популярным направлением использования Веба, это область со значительными возможностями для улучшения. Семантический поиск пытается расширить и улучшить традиционные результаты поиска (основанные на технологиях извлечения информации) при помощи использования данных из Семантического Веба.

Семантический поиск – это также процесс, используемый для улучшения результатов онлайн-поиска посредством использования данных из разнообразных баз знаний для разрешения неоднозначности между поисковыми запросами и текстами электронных документов в целях получения более релевантных результатов [90]. М. Хильдебранд в своей работе[89] проводит обзор существующих поисковых систем (ПС) и выделяет некоторые другие возможности использования семантики в процессе поиска. Р.Гуха [67] выделяет два основных типа поиска информации: и навигационный исследовательский.

В случае навигационного поиска, пользователь использует ПС как навигационное устройство для перехода к конкретному документу, содержащему в себе текст поискового запроса. Семантический поиск не применим к навигационному типу поиска. При исследовательском типе поиска пользователь подает на вход ПС фразу, являющуюся описанием объекта, о котором пользователь пытается найти информацию. При этом не существует какого-то определенного документа, который ищет пользователь, напротив, он пытается найти некоторое множество документов, которые совместно предоставят ему информацию об объекте интереса поискового запроса.

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

Некоторые авторы ервоначально рассматривают семантический поиск как набор техник для извлечения знаний из хорошо структурированных источников данных, таких как онтологии, находящиеся в Смантическом Вбе [95].

Традиционно под средствами семантического поиска понимаются системы, принимающие на вход некоторый запрос, обрабатывающие его с использованием рассуждений над специфической базой знаний и возвращающие совместимые результаты [97]. Входным запросом может являться, например, естественно-языковой вопрос, представление вопроса при помощи триплетов[76], графическое представление, набор ключевых слов, отдельные фразы и т.д. В роли базы знаний могут выступать онтологии, аннотированные массивы текста, текстовые документы, Веб, XML[48, 78, 98, 99] документы, RDF[87, 85, 83, 84] документы, HTML документы и т.д.

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

В области семантического поиска существует значительное число разнообразных программных средств, которые можно разделить на три основных класса по применяемым подходам: программные средства, специали зирующиеся на семантическом поиске, основанном на структурированных языках запросов, таких как SPARQL[94] (например, ARQ [36]);

программные средства для поиска онтологий в Вебе (например, Swoogle[46]);

и программные средства, применяющие ориентированные на пользователя подходы для поиска и извлечения информации и знаний (например, SemSearch[74]). Системы каждого из этих классов обладают специфическими характеристиками с точки зрения конечных пользователей:

1. Программные средства, основанные на использовании запросов на структурированных языках, требуют от пользователей квалификации в использовании специфического языка запросов, подразумевая знание логически-ориентированных языков, чего обычно нельзя ожидать от среднестатистического пользователя ПС. Более того, такие системы, как правило, не производят предварительную обработку результатов, т.к. они в целом не поддерживают какой-либо естественно-языковой пользовательский интерфейс (ЕЯПИ).

2. Ориентированные на пользователя средства извлечения онтологических данных из Веба, однако, в том или ином виде ЕЯПИ (как правило, поддерживается поиск по ключевым словам). Системы такого класса позволяют пользователям находить URI[38, 75] онтологических документов, представленных с помощью RDF, XML, OWL[80,79] и т.д. Такие системы так же называются системами семантического поиска, потому что они зачастую предоставляют механизм повышения качества поиска за счет использования онтологических концептов, таких как Organisation, Person и т.д. Тем не менее, такие системы обычно возвращают только URI объекта - результата поиска, а не какие-либо специфичные детали о нем, а также не производят обработку найденных ответов для их представления в естественно-языковой форме.

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

Класс средств семантического поиска, ориентированных на пользователя, представляется наиболее интересным, поэтому проведем дальнейшую категоризацию подходов, представленных данным классом:

1. Подходы, основанные на ключевых словах, рассматривают естественно языковой запрос как набор ключевых слов (“bag of words”)(например, NLPReduce[72]);

2. Естественно-языковые подходы используют моделирование лингвистической структуры поискового запроса (например, AquaLog [73]);

3. Подходы, основанные на графах, сравнивают онтологические термы, используя интерфейс, основанный на графах (например, Semantic Crystal [39], SEWASIE [91], Corese [45]);

4. Гибридные подходы (например, K-Search [41]).

Естественно, рассматриваемые категории средств семантического поиска различаются как с точки зрения обработки входных запросов, так и с точки зрения стратегии и формата представления результатов. Некоторые принимают на вход только ключевые слова или фразы, другие только целые предложения или графическое представление запросов, а некоторые комбинируют несколько подходов друг с другом. Некоторые даже поддерживают пользователя при создании поискового запроса, предлагая возможные (т.е. подходящие для данной системы) концепты, извлеченные из словаря онтологии (например, Ginseng [40]).


Подходы, применяемые для получения результатов, также весьма различны.

Некоторые средства семантического поиска используют методы извлечения информации, такие как сравнение шаблонов, извлечение информации и рассуждения, также как и логические подходы для определения корректного ответа. Другие средства сканируют Интернет как огромное собрание документов в противоположность другой группе средств, которые анализируют большие корпусы текстовых документов, таких как новости или статьи Wikipedia. Иной класс средств запрашивает информацию из баз данных, использует XML базы данных для анализа или применяет одну или несколько семантических баз знаний, таких как онтологии, для того, чтобы получить результат поиска. Некоторые из средств даже используют техники машинного перевода для предоставления возможности ответов на мульти-языковые запросы. Более того, существуют гибридные системы, комбинирующие все разнообразие методов анализа, поиска результатов и источников знаний (например, K-Search[41]).

В последние годы применяемые в семантическом поиске подходы весьма разнообразны: увеличение семантической релевантности посредством дополнительного синтаксического анализа и использования обнаруженных данных RDF[68], анализ поисковых запросов и документов на основе триплетов с использованием онтологии предметной области[76], использование автоматически сгенерированных онтологий при поиске[51], вопросно-ответные системы на основе семантических графов и анализа триплетов[47], извлечение семантических отношений естественного языка с помощью шаблонов грамматических зависимостей[32] и многие другие.

1.3. Естественно-языковые поисковые системы Естественно-языковой поисковой системой (ЕЯПС) называется поисковая система, спроектированная для поиска информации в указанных источниках, использующая при поиске методики анализа текстов, представленных на естественном языке (ЕЯ).

Наиболее распространенным типом таких поисковых систем (ПС) являются вопросно-ответные системы, множество входных запросов которых представлено на ЕЯ. Естественно-языковой поиск является одной из основных целей в разработке Семантического Веба.

ЕЯПС должна находить целевые ответы на запросы (вопросы на естественном языке) пользователя, в чем и заключается ее отличие от систем поиска по ключевым словам. Например, когда в традиционную ПС подается запрос «В каком из штатов США самый высокий подоходный налог?», то система игнорирует его вопросительную форму и осуществляет поиск по ключевым словам {«штат», «доход», «налог»} (набор ключевых слов зависит непосредственно от поисковой системы и будет отличаться для двух отдельно взятых поисковых машин). С другой стороны, ЕЯПС пытается определить семантику вопроса, используя методики естественно-языкового анализа, и затем найти и вернуть подмножества репозитория U, документы которого содержат в себе ответ на заданный вопрос. Если поисковый запрос на ЕЯ проанализирован корректно, то результаты, возвращаемые ПС такого типа, будут иметь гораздо более высокую степень релевантности по сравнению с системой поиска по ключевым словам.

Зачастую ЕЯПС используют для поиска данные, возвращаемые традиционными поисковыми системами. Если количество источников превосходит один, то такая система называется системой метапоиска.

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

Предпосылкой существования и функционирования таких систем является то, что Интернет (Веб) слишком огромен для индексирования любой отдельно взятой ПС, и более комплексные результаты поиска могут быть получены объединением результатов работы нескольких поисковых систем. Это также предоставляет пользователям возможность пользоваться одной поисковой системой, вместо нескольких различных. С точки зрения программной реализации, системы метапоиска являются гибридными приложениями.

Зачастую, в системах ЕЯ-поиска используются методы машинного обучения научной дисциплины, посвященной проектированию и разработке – алгоритмов, позволяющих компьютерам адаптировать свое поведение в зависимости от эмпирической информации, поступающей извне (например, из базы данных или какой-либо внешней системы).

1.3.1 Обзор зарубежных естественно-языковых поисковых систем Рассмотрим некоторые из существующих и функционирующих зарубежных ЕЯПС. Краткое описание систем представлено в Таблице 1.5.

Таблица 1.5. Описание некоторых из существующих естественно-языковых поисковых систем.

Система Описание Brainboost является системой метапоиска, разработанной для Brainboost предоставления ответов на вопросы, сформированные на ЕЯ1. В настоящее время поддерживается только аглийский язык. Ядро Brainboost использует техники машинного обучения и анализа естественного языка для ответов на вопросы пользователей.

в отличие от традиционных ПС, генерирует Brainboost, множество различных запросов, которые затем передает в традиционные системы поиска информации. Тексты документов, полученных от ПС, анализируются на наличие в них ответов на вопрос, введенный пользователем. Затем ответы, обнаруженные в данных документах, ранжируются при помощи алгоритма AnswerRank и возвращаются пользователю.

Hakia2 это поисковая система для Интернета, Hakia – использующая технологию QDEX (Query Detection and Домашняя страница системы Brainboost. Режим доступа: http://www.brainboost.com/.

Домашняя страница системы Hakia. Режим доступа: http://www.hakia.com/.

Extraction), являющуюся альтернативной новой архитектурой для индексации. При индексации электронных документов используется алгоритм SemanticRank, который сочетает в себе решения из таких дисциплин, как онтологическая семантика, нечеткая логика, компьютерная лингвистика и математика.

Lexxe3 – поисковая система для Интернета, которая Lexxe использует обработку естественно-языковых текстов запросов.

Поисковые запросы могут быть представлены как вопросительными предложениями, например, «Сколько лет Wikipedia?», так и ключевыми словами и фразами.

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

Powerset4 является компанией, разрабатывающей Powerset естественно-языковую поисковую систему для Интернета, которая сможет находить ответы на вопросы, задаваемые пользователем. Например, когда в традиционную поисковую систему подается запрос «В каком из штатов США самый высокий подоходный налог?», то система игнорирует его вопросительную форму и осуществляет поиск по ключевым словам {«штат», «доход», «налог»}.

Обзор отечественных естественно-языковых поисковых 1.3. систем Из отечественных систем естественно-языкового и семантического поиска наиболее интересными представляются AskNet, Exactus и RCO (Russian Context Optimizer).

Домашняя страница системы Lexxe. Режим доступа: http://www.lexxe.com/.

Домашняя страница компании Powerset. Режим доступа: http://www.powerset.com/.

Таблица 1.6. Описание отечественных естественно-языковых поисковых систем.

Система Описание Семантический анализ заключается в классификации AskNet объектов иерархических семантических (учитываемых категорий), а также выявлении отношений между ними.

Используются предопределенные семантические типы в морфологическом словаре, синтаксический анализ предложений, выявление комбинаторных семантических понятий объектов, представленных (семантических несколькими словами). Проводится сопоставление семантически эквивалентных, но синтаксически различных конструкций (активный, пассивный залог). Для выявления семантических объектов используются регулярные выражения, синтаксические и семантические правила продукции, порождающие грамматики (виртуальные словари) чисел и т.п.

[10] Для решения задач естественно-языкового поиска предлагается RCO подход, основанный на преобразовании входных запросов с их последующей передачей в целевую систему поиска по ключевым словам [2, 16]. Для расширения поисковых запросов предназначен модуль RCO Query Parser, который разбирает контекстный поисковый запрос на русском языке и, с учетом грамматики и семантики, строит оптимальное поисковое выражение для обработки в поисковой машине, которая индексирует текст, ничего не зная о языке, за исключением того, что слова разделяются пробелами.

Предлагаемый в [2] способ поиска основан на использовании синтаксических связей между словами поискового запроса для выбора оптимального выражения на языке запросов целевой поисковой машины. Акцент данного метода ставится на использование различных операторов между словами запроса, что позволяет более гибко манипулировать запросом, передаваемым целевой поисковой машине. При отсутствии результатов поиска по первоначальному варианту оптимизированного запроса формируется последовательность менее строгих поисковых запросов с максимальным сохранением первоначального смысла, что обеспечивает последовательное повышение полноты поиска с минимальной потерей точности [2, 16]. Основная идея метода заключается в использовании синтаксических связей между словами запроса для применения различных поисковых ограничений, отражающих силу этих связей, а также в последующем пошаговом ослаблении ограничений (вплоть до TF IDF ) для достижения желаемой полноты [16].

Система базируется на реляционно-ситуационном методе Exactus поиска и анализа текстов, предложенном Г.С. Осиповым[15, 14]. Данный метод опирается на коммуникативную грамматику русского языка[4, 3] и на теорию неоднородных семантических сетей[12, 1].

Основным понятием в коммуникативной грамматике является понятие синтаксемы как минимальной единицы высказывания.

Синтаксемой называется минимальная синтактико семантическая единица языка, несущая обобщенный категориальный смысл и характеризующаяся взаимодействием морфологических, семантических и функциональных признаков[15]. Для анализа предложений и словосочетаний одних синтаксем недостаточно, важна их сочетаемость, которая определяется семейством бинарных отношений на множестве синтаксем [13]. Данные отношения отражают их семантические связи, т. е. являются ситуативными отношениями понятий в понятийной системе предметной области. Для определения синтаксем и отношений между ними в рассматриваемом методе описана следующая последовательность шагов: (1) морфологический анализ (распознаются слова, выделяются лексемы), синтаксический анализ (2) (установление зависимостей между лексемами и выделение синтаксем), (3) реляционно-ситуационный анализ значений (выявление синтаксем и семантических связей между ними).

Результатом работы данного метода являются структуры, описывающие семантическую информацию, передаваемую текстом, в виде реляционно-ситуационной модели. С формальной точки зрения данные структуры являются неоднородными семантическими сетями [12, 1] и называются семантическими образами текстов запросов и документов.

При ранжировании документов больший ранг получает тот документ, в котором слова запроса находятся в тех же семантических отношениях, в которых они входят в данный запрос. Однако для быстрого поиска необходимо создание семантического индекса, содержащего список вхождений слов в документы, статистический вес значимости слова в документе ( TF IDF ) и значение соответствующей синтаксемы.

1.4. Постановка задачи диссертационного исследования Анализ научной литературы показал, что существует большое разнообразие методов и алгоритмов поиска информации в различных источниках. Развитие Семантического Веба и разнообразие подходов, применяемых для поиска и извлечения информации, а также значительное количество естественно языковых и семантических поисковых систем показывает, что тема семантического поиска информации по естественно-языковым запросам (ЕЯ запросам) является весьма актуальной.

Однако, несмотря на большое разнообразие методов и подходов к семантическому поиску, у существующих поисковых систем имеется ряд недостатков. К ним можно отнести отсутствие семантического описания электронных документов (в большинстве случаев), высокую трудоемкость алгоритмизации автоматизированного создания такого описания, большой разрыв между технологиями семантического веба и гипертекстового поиска (развиваются параллельно и независимо друг от друга), недостаточные интеллектуальные возможности анализаторов ЕЯ-запросов.

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

Для достижения этой цели необходимо решить ряд задач:

1. Провести анализ состояния исследований по семантической обработке вопросов на естественном языке с целью выявления классов вопросов, имеющих недостаточную степень проработки и большую практическую значимость для систем естественно-языкового поиска.

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

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

4. Построить математические модели, полезные для описания семантического преобразования поисковых запросов для выбранных типов вопросов. Построить итоговую математическую модель для поддержки семантически-ориентированного преобразования запросов и поиска.

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

Разработать алгоритм ранжирования результатов по степени релевантности поисковому запросу.

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

7. Провести исследование работоспособности разработанных алгоритмов и их соответствия предложенному методу. На основании проведенного анализа сделать вывод о практической применимости и результативности предложенного метода.

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

Рассматриваются отечественные и зарубежные разработки в области семантического поиска, методы и модели, применяемые в таких системах.

Формулируется задача диссертационного исследования.

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

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

Проводится анализ структуры аспектно-ориентированных запросов, на основании которого разрабатывается новый метод формального описания структуры входных текстов анализатора запросов данного типа на основе аппарата контекстно-свободных грамматик.

Разрабатываются общий план алгоритма семантического преобразования аспектно-ориентированных запросов и детальные алгоритмы определения типа и объектов интереса запросов данного вида.

Состояние исследований по семантической обработке 2.1.

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

В работах В.А. Фомичева [22, 26, 29, 63] были рассмотрены основные виды вопросов, составляющих часть входных текстов алгоритма построения матричного семантико-синтаксического представления ЕЯ-текста. Приведем примеры входных вопросов, рассматриваемых в качестве типичных представителей определенных подклассов входных текстов.

Частно-утвердительные (или общие) вопросы 1. Поставляется ли продукция компании Apple в Россию?

Вопросы с вопросительно-относительным местоимением “какой” 1. Какой процессор устанавливается в ноутбуке MacBook?

2. Каким рейсом перевозится продукция компании Dell выпуска 2010 года?

3. Какие решения, предлагаемые компанией Oracle, предназначены для поддержки принятия управленческих решений?

4. В какие страны поставляется продукция заводов компании Sony, расположенных в Азиатском регионе?

5. Какие контейнеры с электронной техникой, поступившие в пятницу, предназначены для ООО “Кубера”?

6. В какие страны экспортирует серверы компания IBM?

7. Какие статьи опубликованы Мартином Фоулером в 2010 году?

Вопросы частноинформативного актуально-синтаксического типа 1. Откуда и для кого поступили 2 трехтонных контейнера с электроникой?

2. Где выступал в 2009 году идеолог экстремального программирования Мартин Фоулер?

3. Где работает лектор Дэн Роусторн?

4. Где расположена штаб-квартира компании Asus?

5. Для кого предназначены два контейнера с электроникой?

Вопросы относительно количества предметов 1. Сколько статей, опубликованных Дэном Роусторном с 1990 года, относятся к методологии Scrum?

2. Сколько трехтонных контейнеров, поступивших в пятницу из Бостона, предназначены ООО “Кубера”?

Вопросы относительно количества событий 1. Сколько раз в году проходит сертификация Scrum Alliance?

2. Сколько раз в прошлом году проводилась сертификация SCJP?



Pages:   || 2 | 3 | 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.