«Машинный семантический анализ русского языка и его применения ...»

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Мозговой Максим Владимирович

Машинный семантический анализ русского языка и его применения

Специальность 05.13.11 — математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

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

кандидата физико-математических наук

Научный руководитель — доктор физико-математических наук, профессор Тузов В.А.

Санкт-Петербург – 2006 2 Оглавление ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

О структуре диссертации

ГЛАВА 1. ЗАДАЧА ФОРМАЛИЗАЦИИ ЕСТЕСТВЕННОГО ЯЗЫКА

Формальные грамматики Н. Хомского

Модель «смысл текст» И. Мельчука

Семантический анализатор В. Тузова

ГЛАВА 2. СЕМАНТИЧЕСКИЙ АНАЛИЗ В ВОПРОСНО-ОТВЕТНЫХ СИСТЕМАХ.... Принципы организации простой вопросно-ответной системы........... Классификация вопросительных предложений

Примеры вопросов и ответов

ГЛАВА 3. СЕМАНТИЧЕСКИЙ АНАЛИЗ В ЗАДАЧАХ ИНФОРМАЦИОННОГО ПОИСКА

И РУБРИКАЦИИ

Поиск и рубрикация с помощью словарей классов

Усовершенствованный механизм поиска

Дополнительные возможности для существующих поисковых машин

ГЛАВА 4. СПЕЛЛЧЕКЕР И ТЕЗАУРУС

Семантический анализатор как модуль проверки правописания........ Контекстно-ориентированный тезаурус на основе семантического анализатора

ГЛАВА 5. ПОИСК ЧАСТИЧНО СОВПАДАЮЩИХ ДОКУМЕНТОВ И ВЫЯВЛЕНИЕ

ПЛАГИАТА

О задаче выявления плагиата и поиске частичных совпадений.......... Технические особенности систем выявления плагиата

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

ГЛАВА 6. ВВЕДЕНИЕ В МАШИННЫЙ ПЕРЕВОД

Морфологический и синтактико-семантический уровни анализа текста

Семантический уровень анализа текста

Адаптация семантического анализатора для различных языков......... Схема простейшей системы машинного перевода на основе семантического анализатора

Практический пример: русско-финский перевод

ГЛАВА 7. ТЕХНИЧЕСКИЕ ДЕТАЛИ

Текущая реализация семантического анализатора и её перспективы. Формат выходных данных семантического анализатора

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение Обработка текстов на естественных языках (natural language processing, NLP) — тема, не теряющая своей актуальности на протяжении десятилетий. Системы информационного поиска, диалоговые системы, инструменты для машинного перевода и автореферирования, синтезаторы речи (выполняющие хотя бы базовую интонационную разметку), рубрикаторы и модули проверки правописания так или иначе выполняют анализ текстов, написанных на естественных языках. Важность и амбициозность задачи научить вычислительную машину понимать человеческий язык привлекала внимание исследователей уже на заре компьютерной эры. Так, в 50-х годах появляются первые публикации о системах машинного перевода [1]. В наши дни успехи направления можно охарактеризовать как переменные. С одной стороны, почти все коммерческие текстовые редакторы содержат спеллчекер, а переводчики фирмы Promt [2] успешно рекламируются и продаются. С другой стороны, несовершенство существующих систем проверки правописания и низкое качество машинного перевода общеизвестны.

В книге [3] перечисляются типичные этапы, проходимые человеком, самостоятельно изучающим иностранный язык: «На первом этапе он, как правило, бурно и эмоционально переживает свои первые успехи в движении от незнания к знанию: всё кажется легко, просто и быстро. На втором этапе работы у него появляются сомнения в себе, в своей памяти, в силе воли и даже в своих способностях, а заодно и в качестве учебников, с которым он работает… На третьем этапе он приходит к выводу и вполне философскому, а именно: “я знаю, что ничего не знаю!” Именно на этом-то этапе и начинается труд по изучению иностранного языка с увлечением, который, подобно спорту, захватывает человека».

По всей видимости, отношение специалистов к таким сложным и искусственный интеллект, обработка текстов на естественном языке и распознавание образов1, эволюционирует сходным образом. Первые успехи на игрушечных примерах заканчиваются экзальтированными заявлениями о скором нахождении полного решения задачи. Затем наступает неизбежное разочарование. Переход к более масштабным проектам наглядно свидетельствует: усложнение системы не есть механическое наращивание функциональности. Уметь распознавать десять Самообучаться игре в крестики-нолики ещё не значит уметь учиться игре в шахматы. Основанную на правилах экспертную систему нельзя просто так расширить в несколько раз, механически добавляя новые и новые правила.

Изучая литературу, можно убедиться, что первые два этапа эволюции отношения к задачам сферы искусственного интеллекта пришлись, соответственно, на 50-60-е и 70-80-е годы прошлого столетия2. Вот лишь некоторые цитаты:

§ 1956г.: «Задача заключается в том, чтобы работать на основе предположения, что любой аспект обучения или другой функции разума может быть описан так точно, чтобы машина смогла его симулировать. Мы попытаемся определить, как сделать так, чтобы И обработка текстов, и распознавание образов тоже могут быть отнесены к задачам искусственного интеллекта в широком смысле слова.

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

машины могли пользоваться языком, формулировать абстракции и концепции, решать задачи, которыми сейчас занимаются только люди, а также заниматься самообучением» [4].

§ «В 1960-е гг. сильный ИИ3 продолжал оставаться главной темой в разработках ИИ» [5].

§ «Первая публичная демонстрация переводящего устройства имела эксперимент, проведенный в Нью-Йорке в 1954 году. Тогда все смотрели на возможности компьютерного перевода сквозь розовые очки. Профессиональным переводчикам пророчили в недалеком будущем голодную смерть. Однако вскоре выяснилось, что многие аспекты языка чрезвычайно далеки от формализации, необходимой для успешной работы компьютера с текстом. Многие проблемы казались неразрешимыми, и интерес к машинному переводу сильно упал» [6].

§ «1970-е гг. показали резкий спад интереса к ИИ после того, как исследователям не удалось выполнить нереальные обещания его успеха». «1980-е продемонстрировали как рост, так и спад интереса к ИИ. Основной причиной этого были сбои экспертных систем Также были идентифицированы ограничения в работе экспертных систем, поскольку их знания становились всё больше и сложнее» [5].

Начиная с 90-х годов XX века отношение к задачам искусственного интеллекта вообще и к обработке текстов на естественном языке в частности становится всё более прагматичным. Если не удаётся сделать компьютер интеллектуальным, пусть он поступает разумно хотя бы в чёмТо есть программное обеспечение, благодаря которому компьютеры смогут думать так же, как люди.

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

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

семантического анализатора, созданного проф. В. Тузовым.

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

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

Лишь немногие из них, однако, оказали существенное влияние на современное состояние NLP. Мы рассмотрим три возможных подхода:

грамматики Хомского как наиболее влиятельную модель, оказавшую большое воздействие на теорию компиляции, модель «смысл текст»

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

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

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

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

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

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

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

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

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

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

после появления работ Н. Хомского, Т. Бэкуса, А. Ахо, Дж. Ульмана и других. Неудивительно, что проблема приведения предложений естественного языка к строгому формальному виду изучается со времён возникновения NLP.

Среди наиболее известных и влиятельных работ, посвящённых формальному описанию языков, можно выделить теорию формальных грамматик Н. Хомского [7] и модель «смысл текст» И. Мельчука [8].

Идеи Хомского лежат в основе известных алгоритмов анализа текстов компьютерных программ. Многие синтаксические анализаторы англоязычных текстов (см., напр., [10]) так или иначе используют грамматики Хомского. Модель Мельчука изначально предназначалась для изучения проблемы формализации естественных языков, и на теорию компиляции влияния не оказала. Кроме того, как отмечается в работе [11], независимостью (т.е. ориентирована на русскоязычные тексты), что препятствует её распространению на Западе. Однако в работах российских исследователей по теоретической и компьютерной лингвистике результаты Мельчука широко цитируются.

Как уже было указано выше, данная работа базируется на модели формализации русского языка, предложенной проф. В. Тузовым [12]. В распространения, но программные продукты, его использующие, уже существуют (см. [13] и [14]). В следующем разделе мы кратко ознакомимся с идеями Н. Хомского и И. Мельчука и чуть подробнее — с основными положениями теории В. Тузова. Знакомство с базовыми принципами работы семантического анализатора необходимо для понимания дальнейшего материала работы; модели же Хомского и Мельчука описаны с целью доказательства оригинальности теории В. Тузова4.

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

Формальные грамматики Н. Хомского В книге [17] формальные грамматики определяются следующим образом. Если V — некоторый алфавит (то есть множество символов), то:

§ V+ — множество всех цепочек (строк) над алфавитом V без пустой цепочки ;

§ V* — множество всех цепочек над алфавитом V, включая.

Грамматика состоит из множества терминальных символов VT, множества нетерминальных символов (переменных) VN, множества правил вывода грамматики P и начального символа S VN. Для грамматик наиболее Некоторые авторы (см., напр., [15]) несправедливо утверждают, что теория В. Тузова основана на упрощённых идеях Мельчука.

общего типа 0 правила вывода имеют вид, где (VN VT)+, (VN VT)*. В наиболее часто применяемых на практике контекстносвободных (тип 2) грамматиках используются лишь правила вида A, где A VN, V*.

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

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

§ терминальными символами являются отдельные слова языка («the», «cat», «to», «walk»);

§ в качестве нетерминальных символов указываются члены предложения отдельные части речи («глагол», «существительное», «причастие»);

§ начальным символом грамматики является символ «предложение».

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

СУЩЕСТВИТЕЛЬНОЕ cat | dog | table |... (существительные языка)

ПРЕДЛОЖЕНИЕ ПОДЛЕЖАЩЕЕ СКАЗУЕМОЕ ДОПОЛНЕНИЕ

ПРЕДЛОЖЕНИЕ ПОДЛЕЖАЩЕЕ СКАЗУЕМОЕ ДОПОЛНЕНИЕ ОБСТОЯТЕЛЬСТВО

Выражение A a | b является сокращённой формой записи A a, A b.

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

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

Рис. 1.1. Дерево разбора предложения «The cat ate the banana».

На практике синтаксические анализаторы английского языка нередко до сих пор используют эвристические статистические алгоритмы (см., напр., библиотеку OpenNLP [19]). По всей видимости, задача нахождения полного набора формальных правил вывода для английского К сожалению, ситуация с русским языком ничуть не лучше.

языка так ещё и не решена7. Впрочем, независимо от способа получения дерева, общая идея его организации остаётся неизменной (см. рис. 1.2).

Рис. 1.2. Дерево разбора предложения, полученное при помощи OpenNLP.

Названия нетерминальных символов в современных синтаксических анализаторах обычно совпадают с обозначениями, используемыми в проекте Penn Treebank [20]. В частности:

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

S — начальный символ (sentence) NP — именная группа (noun phrase) VP — глагольная группа (verb phrase) PP — предложная группа (prepositional phrase) JJ — прилагательное (adjective) NN — noun, singular (существительное, единственное число) DT — determiner (определяющее слово) VBZ — verb, 3rd person s.p. (глагол, 3-е л., наст. время, ед.ч.) TO — particle to (частица to) Заметим, что грамматики Хомского предназначены, прежде всего, для описания структуры предложения. Не менее важный вопрос описания смыслов отдельных слов остаётся за пределами их возможностей.

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

гласит: «Естественный язык есть система, устанавливающая соответствия между любым заданным смыслом и всеми выражающими его текстами;

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

В основе модели лежит, в первую очередь, так называемый «толковокомбинаторный словарь современного русского языка». И. Мельчук утверждает, что толково-комбинаторный словарь «претендует на чисто НАУЧНОЕ описание русской лексики, не делая никаких уступок педагогическим, коммерческим, типографским и тому подобным соображениям» [9]. Действительно, данный словарь является смелой попыткой применить математические стандарты определений в языкознании. Наиболее важными особенностями словаря Мельчука являются активность и формализованность.

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

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

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

Важно отметить, что в каждой словарной статье описывается не отдельное слово, а так называемая пропозициональная форма, состоящая из лексемы (некоторого значения слова) и переменных, составляющих её контекст. Например, слову «восхищаться» соответствует, в частности, такая запись: «X восхищается Y-ом = X находится в достаточно интенсивном положительном эмоциональном состоянии, каузированном тем, что X считает воспринимаемый им Y очень хорошим ».

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

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

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

Правила, разработанные Мельчуком, применяются последовательно:

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

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

§ формальный («семантический») язык, позволяющий в строгом однозначном виде записать любое предложение естественного языка;

§ семантический словарь, содержащий формальные представления слов естественного языка;

формальному виду.

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

Основное отличие описываемой теории от подходов Хомского и Мельчука заключается в изучении текста на естественном языке как выполняемой структуры. Проводится чёткая аналогия между обычным текстом и компьютерной программой: разница лишь в том, что семантика в предложениях естественного языка спрятана гораздо глубже. На этом вопросе необходимо остановиться немного подробнее.

Основные этапы взаимодействия компьютера с текстом на языке программирования (например, с программой на Паскале) показаны на рис. 1.3. Аналогичная схема для текста на естественном языке изображена на рис. 1.4.

Рис. 1.3. Этапы взаимодействия компьютера с программой (упрощённая схема).

Рис. 1.4. Этапы взаимодействия компьютера с текстом на естественном языке.

Наиболее очевидная сложность в схеме на рис. 1.4 связана с этапом выполнения. Процессор непосредственно умеет выполнять инструкции машинного кода; цель и результат выполнения той или иной команды чётко определены. Для естественного (например, русского) языка смысл «выполнения» не столь очевиден. Ответ на этот вопрос лежит уже в сфере прагматики, то есть способа использования естественного языка человеком, а не семантики языка. Цель программы на Паскале (находить корень уравнения, сортировать массив) чётко определена; цель фразы на естественном языке («сарай горит», «Президент поддержал инициативу законодателей») в общем случае неизвестна. Например, может подразумеваться, что «выполнение» фразы приводит к изображению описываемой ею ситуации на экране компьютера («сарай горит»). С тем же успехом можно полагать, что «выполнение» предложения печатает список найденных в базе данных документов, содержащих сходную информацию.

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

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

программу, необходимо понимать смысл ключевых слов, таких как if или repeat. Аналогично, для выполнения текста на естественном языке требуется словарь, содержащий (в частности) описания смысла отдельных слов языка. Заметим, что этот факт с очевидностью следует из аналогии между естественными и компьютерными языками. Никому не приходит в голову создавать компилятор, основанный на статистическом анализе, цепях Маркова или каком-либо виде «поверхностного» семантического разбора. Когда же речь заходит о естественных языках, подобные методы почему-то рассматриваются как вполне подходящие.

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

Слова русского языка делятся на две группы: базовые (около слов в текущей реализации) и производные (около 90000). Базовые слова, такие как Иванов, радость или абразив не выражаются через другие. Для базового слова можно только указать его класс (см. табл. 1.1) и, в ряде случаев, краткое формальное описание. Например, слово абразив принадлежит классу «поделочные материалы» и описано как «вещество, используемое для обработки металлов»:

$12127(Usor_o1(ВЕЩЕСТВО$1211,Caus(#,Lab(МЕТАЛЛ$12122,ОБРАБОТКА$15131))) Таблица 1.1. Примеры базовых слов Иванов Существительное / Физический объект / Живой / Человек / радость Существительное / Психика / Душа / Чувства / Довольство / абразив Существительное / Физический Объект / Неодушевлённый / Классификация объектов — задача сложная и неоднозначная. Можно разработать альтернативную классификацию (вплоть до того, чтобы разбить все объекты на три класса — «маленькие», «большие» и «неопределённого размера») и аргументировать её превосходство. На практике всё определяется изучаемой предметной областью: классы лишь сообщают некоторые сведения о словах, доступные для дальнейшего использования. Если предметная область требует разделения всех объектов на «большие» и «маленькие», систему классов можно адаптировать, не внося при этом никаких изменений в программу семантического анализа.

Используемая в настоящее время система, состоящая более чем из классов (см. рис. 1.5), претендует если не на универсальность, то, по крайней мере, на применимость в типичных случаях.

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

Производные слова определяются через базовые путём применения к ним базисных функций8 (см. табл. 1.2, табл. 1.3).

Это не отменяет необходимости приписывать производным словам соответствующие им классы.

Таблица 1.2. Некоторые базисные функции Caus(x, y) Copul(x, y) Lab(x, y) Таблица 1.3. Примеры производных слов аморфный NeHab(z1, ФОРМА) мулатка Copul(МУЛАТ, ЖЕНЩИНА) Таким образом, формулу слова «жечь» можно интерпретировать следующим образом: z1 делает так, что z2 подвергается действию огня.

Аналогично, «аморфный» — это «z1, не имеющий формы», а «мулатка» — это «мулат, который является женщиной». Словам, имеющим несколько значений, сопоставляется несколько описаний в семантическом словаре. В процессе анализа будет выбрана альтернатива, согласующаяся с реально встретившимся контекстом. Контекст определяется при помощи синтактико-семантической формулы слова, в которой всегда указываются Названия базисных функций в словаре Тузова позаимствованы у Мельчука, однако сами функции здесь интерпретируются не как лексические, а как смысловые операции над понятиями, предназначенные для получения новых понятий.

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

РАЗБИТЬ PerfCaus(Z1,IncepPrepar(Z2,ИСПОЛЬЗОВАНИЕ$15301(Z3))) ПРИГОТОВЛЕНИЕ$152310(Z1: !Им,Z2: !Вин,Z3: !Для) РАЗБИТЬ PerfCaus(Z1,FinFunc(Lab(Z2,УДАР$1520310(Z3)))) Описание каждой трактовки слова состоит из двух формул — смысловой и синтактико-семантической. Смысловая формула объясняет значение слова.

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

Смысловая формула из первого описания определяет слово разбить как «приготовить для дальнейшего использования» («разбить палатку»).

Синтактико-семантическая формула указывает, что слово разбить именительным (кто разбивает) и винительным (что разбивает) падежами, а также с предлогом для (для чего разбивает). Аналогично, смысловая формула из второго описания определяет слово разбить как «прекратить Соответствующая синтактико-семантическая формула сообщает, что слово разбить принадлежит классу РАЗБИВАНИЕ$11031 и сочетается с творительным (чем разбивает) падежами. Вместо творительного может также встретиться винительный падеж с предлогом об/обо (обо что разбивает). В формуле также указано, что слово, соответствующее винительному падежу, должно принадлежать классу ВЕЩЬ$1213, либо классу ОКНО$123372. Более подробно устройство словаря обсуждается в шестой главе.

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

Идея представления предложения в виде суперпозиции слов продолжает аналогию между естественными языками и языками программирования. Выражаясь точнее, в соответствии с моделью В. Тузова предложения естественного языка имеют функциональную природу, то есть адекватно описываются с помощью суперпозиции программирования, такие как Haskell и Standard ML). Так, предложение Иван купил у Петра книгу преобразуется семантическим анализатором к следующему виду:

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

Во введении уже упоминалось, что семантический анализатор может применяться и как дополнительный механизм, улучшающий качество работы какой-либо существующей системы, и как мощный фундамент для нового проекта, способный в конечном итоге радикально улучшить достижения в некоторых областях NLP. «Косметические» улучшения достигаются сравнительно малыми усилиями, что делает применение анализатора ещё более привлекательным. Данная работа посвящена в основном изучению способов внедрения семантического анализатора в существующие проекты. Пересмотр всего подхода к решению задачи с использованием теории В. Тузова в качестве фундамента требует солидных трудозатрат, но может окупиться впечатляющими достижениями. Далее мы рассмотрим как теоретические возможности для новых проектов в сфере NLP, так и некоторые практически полученные результаты. Однако говорить о каком-либо по-настоящему серьёзном законченном проекте, полностью основанном на функциональной модели В. Тузова, ещё рано.

Вопросно-ответная система — это программа, которая умеет обрабатывать введённый пользователем вопрос на естественном языке и печатать осмысленный ответ. Таким образом, вопросно-ответные системы образуют подмножество хорошо известных диалоговых приложений, к которым относятся такие разные примеры, как командная строка DOS, администратор СУБД на основе языка SQL или экспертная система.

Некоторые диалоговые системы (восходящие к знаменитой программе ELIZA [22]) пытаются создать атмосферу полноценного «общения» между человеком и компьютером на естественном языке. На практике «интеллектуальность» большинства подобных программ ещё весьма неудовлетворительна; с другой стороны, не каждый текстовый интерфейс нуждается в мощной поддержке технологиями ИИ.

семантического анализатора В. Тузова, мы остановимся лишь на системах, которые занимаются обработкой запросов, сформулированных на естественном языке. Как правило, под «обработкой» подразумевается поиск релевантной запросу информации в некотором банке данных. Эта задача родственна, но не идентична информационному поиску (information retrieval). В задаче поиска результатом обработки запроса является список релевантных документов, то есть считается, что пользователь ищет некоторый документ. В вопросно-ответных системах в качестве результата выводится только конкретный ответ на конкретно поставленный вопрос («Когда начнётся матч?» — «в 18:00 по московскому времени»).

В работе [23] вопросно-ответные системы характеризуются «уровнями понимания». На первом уровне ответы формируются только на основе прямого содержания текста: система сумеет извлечь релевантные данные, только если в вопросе присутствуют те же синтаксические конструкции, которые уже присутствуют во входном тексте. На втором уровне к механизму системы добавляются средства логического вывода, позволяющие делать заключения о месте и времени происходящих событий, казуальной зависимости и т.п. Третий уровень вносит стереотипные знания о ситуациях реального мира, позволяющие «достраивать» базу фактов на основании «здравого смысла», то есть знаний более общего рода.

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

Лучшие из существующих проектов, ориентированные на английский язык (см., напр., [25] и [26]), используют связку из синтаксического анализатора, словаря и статистического модуля. Для английского языка анализаторы [19], [27] и электронные словари (самым известным из которых является WordNet [28]). Синтаксические анализаторы, как Treebank [20]. Словарь WordNet по сути является толковым словарём, содержащим, помимо объяснений смысла слов (в виде обычного английского текста), некоторую дополнительную информацию, такую как тип слова (часть речи), список синонимов, список других форм того же слова (актуально для английских глаголов) и т.п. Хотя разметка слов выдаётся в хорошо структурированном виде, удобном для анализа компьютером, всё-таки WordNet ориентирован в первую очередь на использование человеком. При анализе слов не учитывается контекст, и распечатка данных, скажем, по слову table включает в себя шесть значений, пять из которых относятся к существительным и одно — к глаголам. Список синонимов наряду с пользой добавляет сложностей.

Например, согласно WordNet синонимами слова table являются такие разные понятия, как mesa (столовая гора) и tabular array (таблица).

Здесь уделено так много внимания словарю WordNet лишь с одной целью: показать типичные проблемы, связанные с автоматическим использованием стандартных словарей. Обычно их пытаются (с той или иной степенью успеха) решать с помощью статистических методов (см., напр., сборник статей по задаче определения корректного смысла слов [29]). Синтактико-семантический словарь В. Тузова лишён подобных недостатков. В выражениях «девушка с русой косой» и «девушка со стальной косой» анализатор с помощью словаря выберет правильное значение слова коса. Само собой, слово косой в качестве прилагательного заведомо не будет фигурировать в распечатке разбора как не сочетающееся с контекстом.

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

Принципы организации простой вопросно-ответной Перед тем, как изложить основные тезисы [30], отметим, что исследования систем различных уровней понимания могут вестись независимо друг от друга. С одной стороны, первый уровень понимания совершенно необходим для построения вопросно-ответных систем второго и третьего уровней; с другой стороны, механизмы извлечения информации из базы знаний (то есть реализующие высшие уровни понимания) могут разрабатываться независимо, поскольку анализ предложений текста на естественном языке — не единственный возможный способ её пополнения.

Поскольку наши исследования связаны в первую очередь с семантическим анализом, а не с организацией баз знаний, мы в основном ограничивались первым уровнем понимания. Так, система [30] обрабатывает лишь так называемые специальные вопросы (то есть вопросы, задаваемые к тому или иному члену предложения) с вопросительными словами кто, кого, кому, кем, о ком, что, чего, чему, чем, о чём, а также где, куда и откуда. В качестве базы знаний выступает обычный текстовый документ, рассматриваемый как последовательность предложений. Чтобы получить корректный ответ, в большинстве случаев достаточно выполнить синтаксический анализ вопросительного предложения, а также предложений входного текста. Часть утвердительного предложения, содержащего ответ, можно найти по падежу. Например, вопросу кто соответствует именительный падеж.

Однако три вопросительных слова (из рассматриваемых) требуют уже базового семантического разбора. Речь идёт о словах где, куда и откуда. В принципе, можно сказать, что вопросительному слову где соответствует предложный падеж, вопросительному слову куда — винительный, а вопросительному слову откуда — родительный. Однако на вопросы где прошла жизнь?, куда пошёл Сергей? и откуда пришёл Иван? нельзя ответить сочетаниями в трудах, на риск и из вежливости соответственно, хотя с точки зрения падежей ответы являются корректными. Чтобы выявить, к примеру, принципиальное отличие в значениях сочетаний из вежливости и из ресторана, необходим семантический анализ. Другим, менее ярким примером использования семантической информации в семантического словаря) на одушевлённость. В частности, слово собака не может быть ответом на вопрос что лежит на диване?

предположениях10:

предложения является глаголом (куда собираются экспортировать нефть? собираются(куда, экспортировать(нефть)); на кого окажет давление Путин? окажет_давление(на(кого), Путин)).

2. Вопросительное слово является первым аргументом центрального слова вопросительного предложения. Специальной обработки требует только случай предложного падежа. Скобочная форма типичного вопроса с центр_глагол(о(ком), арг2, …, аргn).

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

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

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

Классификация вопросительных предложений При разработке экспериментальной вопросно-ответной системы [30] нами была изучена задача классификации вопросительных предложений. Из доступных лингвистических изданий лишь [31] предлагает системный подход к описанию разновидностей вопросов в русском языке. Однако и он представляется недостаточно формальным для непосредственного использования в компьютерных программах. На основе примеров из [31] мы разработали собственную классификацию вопросительных предложений, уделяя особое внимание конструкциям, имеющим практический смысл в контексте вопросно-ответных систем. Как правило, для вопросительных предложений семантический анализатор генерирует простые, удобные при дальнейшей обработке структуры.

Общие вопросы (требующие ответа в форме «да» / «нет») Общие вопросы, как правило, образуются при помощи интонации (см. табл. 2.1). Несколько реже используются частицы — либо для акцентирования отдельных слов, либо для придания экспрессивности.

Таблица 2.1. Образование при помощи интонации Утвердительное предложение Вопросительное предложение Он встретил Ваню. Он встретил Ваню?

Сергей вернулся домой из гостей. Сергей вернулся домой из гостей?

Для получения утвердительной части образованного при помощи интонации вопросительного предложения достаточно лишь заменить в нём вопросительный знак точкой.

Таблица 2.2. Образование при помощи частиц ли, разве, неужели, ужели, что, что ли Утвердительное Вопросительное предложение предложение Учиться необходимо. Разве учиться необходимо?

Поезд опять опаздывает. Что, поезд опять опаздывает (что ли)?

Она красивее тебя. Что она, красивее тебя (что ли)?

Почтальон тебе письмо Что это почтальон — тебе письмо принёс?

принёс.

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

Рис. 2.1. Расположение вопросительных частиц в деревьях разбора.

К общим вопросам относятся ещё два небольших класса: вопросы с не и вопросы схемы не ли (см. табл. 2.3, табл. 2.4).

Таблица 2.3. Использование частицы не для акцентирования слов Отец приехал? Отец не приехал? (по смыслу вопросы Таблица 2.4. Использование схемы не ли Образованный интонацией Он за меня заступится? Не заступится ли он за меня?

Здесь необходимо отметить, что для ответа на вопрос с частицей не уже недостаточно ограничиться простой формой «да» / «нет». Ответ должен сопровождаться пояснением:

Ты не встретил Ваню? Да, встретил (Нет, встретил) / Не встретил ли ты Ваню? Да, встретил / Нет, не встретил.

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

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

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

Таблица 2.5. Примеры анализа общих вопросов автомобиль?

Специальные вопросы (требующие развёрнутого ответа) По смыслу специальные вопросы могут быть разделены на несколько различных типов, но с точки зрения семантического анализа эти типы мало различаются. Практически все специальные вопросы образуются с помощью вопросительных слов. К вопросительным словам относятся:

1. местоимения-существительные кто, что;

2. местоимённые прилагательные какой, который, чей, каков;

3. наречия где, куда, откуда, когда, зачем, отчего, почему, как и сколько.

В контексте диалога специальные вопросы могут состоять даже из одного слова: «Придётся ждать. — Сколько?» При использовании вопросно-ответных систем первого уровня понимания подобные вопросы не имеют смысла.

Наиболее многочисленная (и наиболее важная в контексте вопросноответных систем) группа вопросов образуется при помощи схемы (см. табл. 2.6).

Таблица 2.6. Использование схемы Кто (это) пришёл? Что (это) случилось? Сколько народу собралось? От кого письмо? Какую книгу вы читаете? Что (это) он на меня так смотрит?

Почему шум? Откуда сквозит?

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

1. Деревья вопроса со словом кто и предложения, являющегося потенциальным ответом, изображены на рис. 2.2.

Рис. 2.2. Деревья вопроса со словом кто и потенциального ответа на него.

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

2. Вопрос со словом что обрабатывается аналогично, только кроме именительного падежа в дереве потенциального ответа допустимым считается также винительный (что увидел Саша?).

3. Вопрос со словом какой задаётся к определению. Определение — это свойство (или свойства) объекта, на уровне семантического анализа выделяемое в аргументы слова-функции, соответствующего этому объекту (см. рис. 2.3).

Рис. 2.3. Деревья вопроса со словом какой и потенциального ответа на него.

Если дерево ответа соответствует дереву вопроса (QT AT), в качестве результата печатаются все найденные определения (В доме стоял итальянский дубовый шкаф с резными ножками. Какой шкаф стоял в доме? итальянский, дубовый, с резными ножками).

4. Вопросительное предложение со словом чей обрабатывается аналогично случаю со словом какой. Добавляется единственное новое ограничение:

слово, соответствующее запрашиваемой сущности, должно быть одушевлённым.

5. Вопрос со словом каков семантически эквивалентен вопросу со словом какой. Разница заключается лишь в синтаксисе: Какой шкаф стоял в доме? Каков был шкаф, стоявший в доме?

6. Если не брать в расчёт устойчивое сочетание который час (малоосмысленное в контексте вопросно-ответной системы), слово который также используется в качестве замены слову какой в некоторых контекстах: Который из двух братьев — старший?

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

8. Вопрос со словом куда разбирается аналогично вопросу со словом где.

Семантический анализатор в этом случае также распознаёт указание на место (атрибут @Куда).

9. Наречие откуда в вопросах имеет два смысла. Либо вопрос как-то связан с указанием месторасположения (слово, обратное куда), либо слово откуда используется как эквивалент конструкций по какой причине, каким образом. В первом случае (откуда приехал Иван? — Иван приехал из деревни) семантический анализатор вырабатывает атрибут @Откуда. Извлечение ответа при этом аналогично ситуации с атрибутом куда. Второй случай менее интересен для вопросно-ответных месторасположении кого или чего-либо, носят либо ярко выраженный риторический характер, либо не могут быть легко сопоставлены тому или иному утвердительному предложению (необходим контекст диалога): Сколько ему лет? — Откуда я знаю?; Откуда он взял деньги на машину? — Да вот же.

10. По своей структуре вопрос со словом когда аналогичен предыдущим рассмотренным вопросам (откуда, куда, где…) В данном случае запрашиваемая сущность связана со временем, и семантический анализатор вырабатывает для неё атрибут @Когда.

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

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

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

12.Вопрос со словом как — это вопрос к наречию или к конструкции, центральным словом которой является наречие. Общая форма вопроса сохраняется неизменной, не меняется и способ поиска ответа. В некоторых случаях слово как служит синонимом сочетания каким образом: Как Сергей вернулся домой? — Сергей вернулся домой на автобусе. В подобных ситуациях для выявления ответа потребуется найти конструкцию с предложным падежом в корне дерева.

13. Вопрос со словом сколько обращён к числительному. В простых случаях общая форма совпадает с ранее рассмотренными: Сколько лет Ивану? — Ивану 30 лет. Однако очень часто слова из вопроса не фигурируют в ответе, что затрудняет нахождение соответствия: Сколько у Петра с собой денег? — У Петра с собой пятьсот рублей; Сколько прошло времени? — Прошло два часа.

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

Таблица 2.7. Использование схемы Кому сюда прийти? Как нам поступить? Сколько ещё ждать? Куда поставить чемодан? Что же делать? Какой толк спорить?

Для корректной обработки вопросительных предложений этого вида первого уровня понимания уже недостаточно. Кроме того, приведённые вопросы, скорее всего, малополезны для использования в вопросноответных системах. Аналогичным образом дело обстоит с вопросами, образуемыми с помощью схем, приведённых на табл. 2.8 – табл. 2.11.

Единственное исключение связано с формой, которая может быть использована для извлечения определений понятий (что такое «брандмауэр»?; что есть «криогенная установка»?).

Таблица 2.8. Использование схемы (именительный или косвенный падеж, возможно, с предлогом) или Как здоровье? Как семья? Что на работе? Как с уроками?

Таблица 2.9. Фразеологизированные схемы что за Что за шум? Что за разговоры?

Что мне до них? Какое дело ему Таблица 2.10. Использование инфинитивного предложения (возможно, с частицей) в качестве вопроса Начинать? Спросить? Послать его к вам? Разве уже обедать? Не начинать ли? Неужели начинать?

Таблица 2.11. Использование схемы а / а А бедный брат? А друзья? А к нам? А читать? А петь?

В завершение раздела уместно привести примеры ответов системы (см. табл. 2.12) на задаваемые пользователем вопросы. Входным текстом будет небольшой фрагмент рассказа Чехова «Поцелуй» (пример взят из [30]):

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

Все почувствовали, что в воздухе пахнет молодой листвой тополя, розами и сиренью.

Таблица 2.12. Вопросы и ответы Чем пахнет в воздухе? Молодой листвой тополя, розами и Глава 3. Семантический анализ в задачах информационного поиска и рубрикации Задача информационного поиска (information retrieval), связанная с алгоритмами быстрого извлечения требуемых документов из некоторого банка данных, считается одной из самых актуальных и широко исследуемых тематик компьютерной науки последнего десятилетия. В первую очередь это связано, разумеется, с бурным ростом интернета — по своей форме гигантской неструктурированной коллекции самых разнообразных данных, поиск в которой представляет серьёзную научную и техническую проблему. В настоящее время ведутся исследования по самым разным направлениям, включающим, например, поиск мультимедийных данных [32], улучшение методик вычисления релевантности [33] и изучение структуры Web [34]. Теоретически при разработке методик информационного поиска приоритет должен, вероятно, отдаваться обеспечению качества извлекаемых документов, то есть разработке адекватных критериев релевантности. На практике для интернетовских поисковых машин зачастую важнее полнота (то есть охват как можно большего количество документов Web), скорость поиска и предоставление дополнительных служб, таких как поиск по электронным библиотекам, магазинам или нахождение информации об объектах на географической карте. Поэтому при разработке алгоритмов извлечения релевантных данных более надёжными можно считать эксперименты, проводимые с так называемыми настольными поисковыми системами, предназначенными для нахождения информации на локальных дисках пользователя. Подобные системы существуют и развиваются уже не Архивариус 3000 [36]). Изучение настольных поисковых систем позволяет также сконцентрироваться на алгоритмах нахождения релевантности, определяющих ранг документа прямо на основании его соответствия запросу, а не на характерных для интернета косвенных признаках, таких как популярность страницы или количестве ссылок на неё.

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

Во-первых, она не оставляет возможности объяснить системе, чт именно желает найти пользователь. Так, система Яндекс в ответ на запрос Лев Толстой. Война и мир выдаёт большое количество ссылок на рефераты. Текст романа (наиболее релевантный документ) в первой тридцатке результатов занимает лишь 11-е и 29-е места (состояние на март 2006г.) Сложно найти и документ, содержащий неизвестное слово (например, узнать название бывшей улицы Пушкинской в Москве). В любом случае, само существование конкурсов по поиску в интернете (Кубка Яндекса, к примеру) наглядно свидетельствует о том, что поиск требуемой информации с помощью существующих систем — задача нетривиальная.

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

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

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

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

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

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

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

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

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

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

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

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

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

Усовершенствованный механизм поиска Некоторые возможности по улучшению качества поиска с помощью семантического анализа можно рассмотреть на примере нашей экспериментальной системы [39]. Для удобства оценки качества поиска мы несколько отошли от классической модели извлечения информации на уровне целых документов: наша система определяет рейтинг каждого предложения документа по отдельности. Правила вычисления рейтинга достаточно просты:

1. Если в предложении встретилось искомое слово, и оно является именем собственным (это можно узнать по классу слова: например, к именам собственным относятся слова из классов физический_объект / поселения / страны / название и физический_объект / живой / человек / индивидуум / ФИО), рейтинг предложения повышается на 8 баллов.

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

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

4. Если в предложении есть слово, в семантическом описании которого встречается та же операция, что и в описании некоторого слова запроса, рейтинг предложения повышается на 1 балл. К примеру, в формальном описании слова удалось встречается запись Hab\$12411/033, что идентификатором класса физический_объект / живой / человек / заслуга / успех). Та же самая запись может быть найдена в описании слова получаться, поэтому рейтинг предложения, содержащего слово получаться, будет повышен на единицу, если в запросе встретилось слово удалось.

Таким образом, простая поисковая система, основанная на классах, использует только правило №3. В программе же [39] используется более гибкая градация, включающая в себя как более важные (нахождение имени собственного или точного слова), так и менее важные (совпадение операций) случаи.

В табл. 3.1 и табл. 3.2 приведены примеры ответов системы на запросы пользователя11.

Таблица 3.1. Результат запроса глава учреждения сообщил (рейтинг: 16) Такое мнение высказал в воскресенье РИА «Новости» глава комитета Госдумы по международным делам Константин Косачёв.

Соответствия:

глава — ГЛАВА учреждения — РИА_НОВОСТИ, ГОСДУМА, КОМИТЕТ сообщил — ВЫСКАЗАТЬ (рейтинг: 11) «Положение в стране крайне нестабильное» — отметил в интервью РИА «Новости» вице-спикер Госдумы Вячеслав Володин.

В качестве тестовой коллекции была использована подборка документов с новостного сервера NEWSru.com Соответствия:

глава — ВИЦЕ-СПИКЕР учреждения — РИА_НОВОСТИ, ГОСДУМА сообщил — ОТМЕТИТЬ, ИНТЕРВЬЮ (рейтинг: 10) Такой неутешительный прогноз дал в интервью ИТАРТАСС заместитель директора Института океанологии РАН Леопольд Лобковский.

Соответствия:

глава — ЗАМЕСТИТЕЛЬ, ДИРЕКТОР учреждения — ИТАР-ТАСС, ИНСТИТУТ сообщил — ИНТЕРВЬЮ (рейтинг: 3) Кроме того, в регионе ЮВА работают два российских госпиталя.

Соответствия:

учреждения — ГОСПИТАЛЬ Таблица 3.2. Результат запроса сложные погодные условия (рейтинг: 20) По словам собеседника агентства ситуацию осложняют погодные условия — сильный боковой ветер, минусовая температура и непрекращающийся снегопад.

Соответствия:

сложные — ОСЛОЖНЯТЬ погодные — ПОГОДНЫЙ, ВЕТЕР, СНЕГОПАД условия — УСЛОВИЯ (рейтинг: 3) обледенения.

Соответствия:

погодные — ОБЛЕДЕНЕНИЕ (рейтинг: 3) В выходные буран в Москве стихнет.

Соответствия:

погодные — БУРАН (рейтинг: 3) В дневные часы термометр покажет минус 8-10 градусов в Москве и 7-12 градусов мороза в её окрестностях.

Соответствия:

погодные — МИНУС, МОРОЗ Как видно из примеров, большинство выданных системой предложений не содержат в точности указанных в запросе слов, тем не менее, все они справедливо сочтены релевантными.

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

§ логические операции при поиске (и/или/не);

§ поиск точной фразы (цитаты);

§ возможность указать слова, которые обязательно должны содержаться в документе;

§ поиск изображений, mp3-файлов;

§ поиск файлов с известным именем;

§ поиск в документах со сложной структурой (DOC, PDF);

§ применение расстояния между словами.

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

Когда поисковая система индексирует некоторый документ, каждому его слову присваивается порядковый номер. Расстояние между двумя словами — это просто разница их порядковых номеров. Если в документе, допустим, встречается сочетание красная шапочка, расстояние между словами красная и шапочка равно единице, а расстояние между словами шапочка и красная — минус единице. Требуемое расстояние можно ввести прямо в строке поиска. К примеру, если в Яндексе ввести запрос поставщики /2 кофе, то найдутся документы, в которых содержится и слово поставщики, и слово кофе, а расстояние между этими словами будет не больше 2. Таким образом, релевантными окажутся документы, содержащие фразы вида поставщики колумбийского кофе, поставщики кофе из Колумбии и т.п.

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

Поиск с расстоянием — разумная альтернатива. Например, в ответ на запрос чёрный /2 кофе можно получить и просто чёрный кофе, и чёрный молотый кофе, и чёрный бразильский кофе. Однако документ, содержащий сочетание чёрный молотый бразильский кофе уже не будет считаться релевантным. Можно ещё увеличить расстояние (чёрный / кофе), но при этом увеличится доля нерелевантных документов, содержащих фразы вроде чёрный пакет с кофе.

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

Изучение дерева разбора даёт возможность выделить, по крайней мере, два типа связей между словами: связь-свойство и связь-отношение.

Связи первого типа возникают, когда одно слово является свойством (или как бы является свойством) второго. Например, именно так связаны слова чёрный и кофе во фразе я пью чёрный кофе» или слова Большой и театр в предложении Я иду в Большой театр.

На уровне дерева предложения это означает выполнения простого требования: одно из слов пары является аргументом другого.

Рассмотрим, к примеру, дерево фразы я купил чёрный бразильский кофе (см. рис. 3.1).

Рис. 3.1. Дерево фразы я купил чёрный бразильский кофе.

Слова чёрный и кофе, чёрный и бразильский связаны по смыслу, причём связью первого типа.

1. Связь-отношение возникает между двумя словами-потомками некоторого третьего слова-предка A.

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

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

1. Маша любит Сашу (см. рис. 3.2).

Эта фраза — простейший пример возникновения связи-отношения (в данном случае между словами Маша и Сашу). Скобочная форма записи предложения хорошо отражает этот факт: любит(Маша, Сашу). Других связей в предложении нет.

2. Большой театр находится в Москве (см. рис. 3.3).

Рис. 3.3. Дерево фразы Большой театр находится в Москве.

Слова Большой и театр, а также в и Москве связаны зависимостью первого типа. Каждое из слов Большой и театр также связано с каждым из слов в и Москве зависимостью второго типа.

3. Я купил кофе в чёрном пакете (см. рис. 3.4).

Это предложение — хороший пример того, как семантический анализатор корректно распределяет не связанные между собой (хотя и стоящие почти рядом) первым типом зависимости слова кофе и чёрном по разным ветвям дерева. Здесь слово чёрном связано первым типом зависимости лишь со словами пакете и в. Со словом кофе оно тоже связано, но тип зависимости здесь — второй.

Рис. 3.4. Дерево фразы я купил кофе в чёрном пакете.

Мы не будем обсуждать аспекты реализации интернетовской поисковой машины, использующей описанные типы зависимостей, поскольку, как уже было сказано выше, поиск в интернете неразрывно связан с индексированием больших объёмов данных, распараллеливанием алгоритмов и тому подобными вещами, непосредственно не относящимися к информационному поиску. Наша экспериментальная система, предназначенная для поиска релевантных документов на локальных дисках пользователя, работает следующим образом. Пользователь задаёт запрос в виде набора слов. Некоторые пары набора могут быть обрамлены скобками (напр.: я купил (чёрный кофе)). Далее специальный модуль с помощью семантического анализатора отбирает из коллекции лишь те документы, в которых заключённые в скобки слова состоят в требуемом типе связи. Затем для отобранных документов вызывается алгоритм ранжирования на основе классической модели векторного пространства, и полученный список возвращается пользователю. Качество результатов правильность определения зависимостей между словами) (вернее, полностью зависит от качества семантического анализатора и достигает 90-95%.

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

Семантический анализатор как модуль проверки Мощные спеллчекеры на практике встречаются редко. Как правило, реализуется простой просмотр словаря языка12 с дальнейшим выбором похожих по написанию слов с помощью расстояния Левенштейна [40].

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

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

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

Например, в немецком отдельные слова часто «склеиваются» в одно длинное слово, и поиск в словаре оказывается связанным с поиском тех или иных его частей.

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

Это объясняется тем, что семантический анализатор был создан для обработки реальных текстов, возможно, содержащих ошибки (впрочем, программирование иных приоритетов — задача вполне посильная).

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

1. Предложение у меня дома на полке книги разбирается без ошибок.

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

Смысл его подозрителен, однако допустим (на полке могут стоять дом).

3. Предложение чашка стояла на стле разбирается, однако слово стле помечается как неизвестное.

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

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

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

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

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

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

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

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

1. сломать, испортить (разбить чашку);

2. приготовить для использования (разбить палатку);

3. стать причиной душевных переживаний (разбить сердце);

4. разделить целое на части (разбить задачу на подзадачи).

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

Чтобы создать качественный контекстно-ориентированный тезаурус, следует применить семантический анализатор в связке с хорошим словарём синонимов (например, с [41]). Можно воспользоваться и встроенным словарём семантического анализатора. Каждое слово семантического словаря описано некоторой смысловой формулой.

Близким по значению словам (то есть синонимам) соответствуют близкие (по некоторому критерию) смысловые формулы.

Изучению методов автоматического извлечения синонимов из семантического словаря посвящены работы [42] и [43]. В статье [42] некоторых классов слов. Также описывается методика построения таких запросов.

В работе [43] рассматривается общий критерий семантической близости, определяемый как расстояние Левенштейна над множеством упрощённых семантических формул, включающих только номера классов и названия базисных функций из исходного описания. Эксперименты показывают, что расстояние, равное нулю (точное совпадение упрощенных формул) почти всегда сигнализирует о найденных синонимах. Расстояние, равное единице, в ряде случаев также обеспечивает хорошее смысловое приближение. Расстояние, превосходящее или равное двум, обычно уже свидетельствует об отсутствии синонимичности (см. табл. 4.1).

Таблица 4.1. Примеры найденных синонимов (песчаная) (косоглазый) (источник) Интересно отметить, что «близость» в терминах семантического словаря далеко не всегда совпадает со смысловой близостью, отраженной в обычных словарях синонимов. Например, слову косой (в смысле косоглазый) достаточно близки слова криворогий и кареглазый.

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

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

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

О задаче выявления плагиата и поиске частичных Проблема плагиата в учебных заведениях по всему миру стоит достаточно остро. Так, по результатам исследования, проведённого в копирование предложений без указания источника, 11% копировали без изменений обширные фрагменты текста, 9% выдавали компьютерные программы, написанные другими, за свои [44]. Плагиат нередко встречается и в научных работах, публикуемых в журналах и в сборниках трудов конференций [45].

К сожалению, в то время как на Западе этой проблеме уделяется пристальное внимание, в России её практически игнорируют. На Западе плагиат считается очень серьёзным нарушением устава университета (или особого «кодекса чести», см., напр., [46], [47]) и может повлечь за собой строгие меры вплоть до исключения студента из учебного заведения.

Учёному плагиат также может стоить карьеры. В нашей стране проблема плагиата накладывается на всеобщее снисходительное отношение к этому явлению. Как отмечают авторы статьи [48], «Проблема [плагиата] в России осознаётся многими преподавателями, но изменить к лучшему ситуацию непросто. [Российская] система образования страдает от недостатка финансирования. Поэтому многие преподаватели бедны и не имеют мотивации следить за тем, что происходит у них за спинами и перед глазами. Взяточничество — обычный способ заработать больше.

Российское общество основано на званиях. Звания открывают двери. Не имеет значения, что вы изучали, если вы окончили известный университет.

Высокие ожидания провоцируют некоторых избрать лёгкий путь».

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

Системы выявления плагиата прежде всего можно разделить на две категории — «онлайновые» и «оффлайновые» (или «герметичные») [49].

«Онлайновые»

исследуемого текста в интернете, либо во встроенной обширной базе статей. Подобные службы выявления плагиата (к ним относится, например, Turnitin [50]) почти всегда являются платными и рассчитаны на широкое использование на уровне целых университетов. «Герметичные»

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

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

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

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

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

Технические особенности систем выявления плагиата На первый взгляд система выявления плагиата работает примерно так же, как и программа поиска или рубрикации — собирает отдельные файлы действительности же метрику в явном виде используют сравнительно редко. Дело в том, что при поиске плагиата «степень подобия» документов не так важна. Важно наличие общих подстрок, доказывающее факты «заимствования».

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

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

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

С помощью токенизации [51] можно бороться со всеми видами Токенизирующий модуль заменяет различные элементы компьютерных идентификатора может быть подставлен токен, а вместо каждого значения — токен. Таким образом, строка будет заменена строкой Теперь переименование переменных ничего не даст, поскольку любая последовательность вида «идентификатор = идентификатор + значение;»

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

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

переименованием идентификаторов с помощью более тонкой методики.

Две строки будут признаны этим алгоритмом идентичными, если в них наблюдаются регулярные изменения в именах идентификаторов. Иными словами, алгоритм отслеживает употребление имён, и сочтёт строки идентичными, только если переменные в них используются одинаковым образом. Например, все три строки a=a+ x=x+ a=b+ будут признаны любым простым алгоритмом токенизации совпадающими.

Алгоритм же параметризованного поиска укажет только на совпадение первых двух строк. Параметризованный поиск может быть реализован достаточно эффективно [53].

Сравнение деревьев разбора [54] — наиболее развитая методика для сегодняшний день. Её суть заключается в поуровневом рекурсивном сравнении деревьев разбора, генерируемых синтаксическим анализатором.

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

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

Используя семантический анализатор В. Тузова, можно адаптировать методики токенизации и сравнения деревьев разбора для систем выявления плагиата в текстах на естественном языке. Результаты этого опыта описаны в статье [55].

В качестве исходной системы выявления плагиата была использована программа [56], созданная при непосредственном участии автора данной работы. Программа [56] представляет собой «герметичный» детектор плагиата со встроенным токенизатором для текстов на языке Java.

Особенностью системы является пониженная алгоритмическая сложность по сравнению со стандартной «наивной» реализацией попарного сравнения файлов коллекции. Система хранит файлы коллекции в особой структуре на основе массива суффиксов [57]. Далее для каждого файла коллекции применяется специальный механизм эвристического поиска, позволяющий быстро найти совпадения со всеми прочими файлами изучаемого набора.

Наш эксперимент заключался в замене токенизатора Java-файлов модулем на основе семантического анализатора, реализующим аналогичную функциональность для русского языка. Токенизацию можно рассматривать как процесс замены элемента текста его классом. Так, элементы x, y, step программы на языке Java могут быть отнесены к классу «ИДЕНТИФИКАТОР», а элементы 10, 15.3, -2 — к классу «ЗНАЧЕНИЕ».

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

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

На первом уровне слово заменяется его непосредственным классом.

Например, слово лиса будет заменено классом «ЖИВОТНЫЕ-ДИКИЕ», а слово собака — классом «ЖИВОТНЫЕ-ДОМАШНИЕ». На втором уровне классы становятся более общими. Теперь и лиса, и собака попадают в один и тот же класс «ЖИВОТНЫЕ». Токенизация более высоких уровней уже лишена практического смысла, поскольку в результате избыточной широты классов семантически абсолютно разные слова начинают трактоваться как эквивалентные.

Для оценки качества системы была использована коллекция из документов, взятых с сервера новостного агентства NEWSru.com. Каждый документ имеет осмысленное название и включён в одну из следующих категорий: В России, В мире, Экономика, Религия, Криминал, Спорт, Культура. Размер статей варьируется от 450 байт до 19 килобайт (медианный размер составляет 2 КБ). Типичная статья состоит из 8- абзацев, содержащих достаточно строгие повествовательные предложения и цитаты. Мы не ставили цели уличить авторов статей в плагиате, однако ожидали извлечь пары документов, либо посвящённых одному и тому же событию, либо прямо цитирующих одни и те же источники.

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

Без применения токенизации программа обнаружила 20 пар частично совпадающих документов (перекрывающихся, по крайней мере, на 4% от общего размера). Ниже перечислены типичные примеры найденных пар (цит. по [55]):

§ Пара документов, посвящённых солнечному затмению 20 марта 2006г.

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

§ Пара документов о погодных условиях в Европе. В первом говорится о наводнениях в странах Евросоюза; второй представляет собой прогноз погоды в Европе (предсказывающий, в том числе, последующие наводнения).

§ Пара документов, посвящённых слухам о помощи, оказанной российской разведкой бывшему иракскому руководству в марте 2003г.

Первый указывает позицию Москвы, второй цитирует реакцию Вашингтона.

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

§ Система перестала различать падежные формы одних и тех же слов.

§ Система указала один и тот же класс для различных (но сходных) слов.

Например, в выражениях резиденция в Греции и резиденция в Афинах слова Греции и Афинах были преобразованы в класс «ПОСЕЛЕНИЕ».

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

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

Теоретически можно воспользоваться методикой [54] для сравнения деревьев, и тем самым ещё повысить качество детектора, но о практических результатах говорить ещё рано.

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

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

Типичные проблемы существующих систем (на примере англорусского перевода) иллюстрирует табл. 6.1. Перевод сделан с помощью пакета Promt [2], тестовые предложения взяты с вебсайта корпорации Microsoft.