Введение к работе
Работа посвящена созданию инструментальной программной среды, облегчающей и ускоряющей процесс отладки большой системы лингвистических алгоритмов, конкретно алгоритмов поверхностно-синтаксического анализа русского предложения
В свое время (50-60 гт XX в) большим достижением в области информационных процессов и систем явилось создание документальных ИПС, использовавших в качестве поисковых признаков лексический состав - множества лексических единиц (ЛЕ) - документов, подлежащих выдаче на запросы пользователей (так называемые ИПС с грамматикой 1-го уровня [25, с. 6]), обеспечивавших среднюю полноту и точность поиска до 50-60 % Потребность в повышении полноты поиска без существенного падения точности в сочетании с потребностью в автоматической обработке все возрастающего потока входных документов (автоматизации индексирования) привели в 70-80-е гг к созданию и широкому распространению ИПС с грамматикой 2-го уровня, учитывающей такие относительно легко поддающиеся распознаванию синтагматические отношения ЛЕ в тексте, как взаимное расположение, расстояние между ними и вхождение в легко распознаваемые фрагменты текста, прежде всего предложения Собственно говоря, именно к этому типу принадлежат повсеместно используемые в настоящее время «поисковые машины» Интернета (Яндекс, Google и др) С одной стороны, эти системы имеют возможность выдвигать такие девизы, как «Найдется все», а с другой стороны в целом ряде случаев за полноту поиска приходится платить значительным возрастанием информационного шума Стремительное нарастание информационных массивов (в масштабах Интернета количество документов измеряется уже миллиардами) выдвигает повышенные требования к сочетанию показателей полноты и точности поисковых систем.
Актуальность темы
Одним из необходимых средств повышения точности документального (текстового) поиска является синтаксический анализ входного текста «Синтаксический анализ сам по себе не является достаточным средством существенного повышения качества поиска в документальных ИПС Однако он является необходимым условием эффективного применения, во-первых, тезаурусов понятий (дескрипторосочетаний, концептуальных словарей), являющихся (точнее, долженствующих быть) основным средством обеспечения эффективного семантического анализа - "понимания"
автоматизированными ИПС запросов к ним, текстов, подлежащих выдаче, и соответствия (отношения релевантности/нерелевантности) между ними» ([21] с 39) Иначе говоря, синтаксический анализ является необходимым элементом концептуального анализа текстов, понимаемого как «распознавание в них наименований понятий, выраженных словами и словосочетаниями, и отношений между понятиями» [7]
Другими важными областями применения автоматического синтаксического анализа в сфере информатики являются автоматическое извлечение фактов из текста (в частности, для введения в фактографические ИПС, или базы данных), автоматическое аннотирование и реферирование первичных документов, не говоря уже о машинном переводе Частичный синтаксический анализ уже применяется (например, в поисковой системе компании Интегрум Техно) для выявления в тексте документов составных имен собственных (имен лиц, названий организаций и т п) и отношений между ними (типа вступления некоторого лица в организацию, ухода из организации и тп)
Таким образом, синтаксический анализ текста (для нашей страны - в первую очередь русского текста) становится все более важным информационным процессом, а его автоматизация - все более существенной для повышения эффективности современных информационных систем и процессов
«Проблема синтаксического анализа неформализованных текстов в полном объеме еще не решена» [8, с 11], хотя в течение последних десятилетий над ней работал ряд весьма сильных научных коллективов (в большинстве случаев эта проблема ставилась ими не как самостоятельная, а как частичная задача в рамках таких задач, как машинный перевод или автоматический поиск текстов) Наиболее продвинутыми можно считать работы в рамках систем ЭТАП ([3, 4, 13]), ЛОТ ([28]), RETRANS ([8]) TREETON ([30, 31]) и нек др. В качестве самостоятельной задачи алгоритмизация (как основа для автоматизации) синтаксического анализа русского текста была поставлена ТЮКобзаревой [15-18] Ее подход отличается от подхода большинства из указанных выше коллективов тем, что синтаксический анализ рассматривается ею не в неразрывной связи с семантическим анализом («когда мы ведем речь о синтаксическом или о семантическом анализе и синтезе текстов, то надо иметь в виду, что это всегда бывает их семантико-синтаксический анализ и синтез» [1, разд 1 4], а как самостоятельный этап анализа текста, предшествующий семантическому анализу и использующий минимальные семантические сведения,
грамматикализованные, такие как «одушевленность - неодушевленность», или грамматикализуемые, такие как модели управления, сформулированные в самых общих грамматических терминах (таких как «управление определенным падежом», «управление предлогом» и т п , см с 26 диссертационной работы)
Неоднократные попытки программно реализовать разработанные Т Ю Кобзаревой алгоритмы синтаксического анализа русского текста не были завершены (хотя частичные программные реализации дают основание считать, что эти алгоритмы способны решить стоящую перед ними задачу) Помимо несовершенства доступных технических средств (первые попытки производились еще на ЭВМ ЕС) и потери квалифицированных исполнителей, связанной с событиями 90-х гг прошлого века, основной причиной этого можно считать объективную сложность задачи, исключающую возможность одноактного полного и окончательного решения ее «в голове» или «на бумаге» « Сколь бы глубоко и тщательно ни разрабатывался синтаксический анализатор < >, в нем неизбежно остаются белые пятна и лакуны Многие лингвистические факты, в том числе критически существенные для работы анализатора, никогда не попадали в поле зрения ученых просто потому, что они не имели возможности в массовом порядке оперировать материалом неверного или неожиданного синтаксического разбора предложений Именно такой материал в изобилии поставляет развитая система автоматической обработки текстов, а работа с этим материалом позволяет выявить лакуны научного описания и устранить их» [13, с 234] Этому соответствует итеративный процесс пробной программной реализации -оценки пробного решения и анализа его ошибок (как программных, так и алгоритмических) - исправления их в следующей пробной реализации и т д
Лингвистические знания обо всех этапах анализа текста обычно записываются специалистами предметной области в текстовых редакторах в виде правил, организованных некоторым образом Здесь можно выделить два подхода условно говоря, «словарный», использующий богатую лексическую информацию и относительно простые алгоритмические решения (примером может служить система ЭТАП), и «алгоритмический» - использующий минимально необходимую словарную информацию и достаточно сложные алгоритмы1, представленный в системе,
Под оловом «алгоритм» понимается совокупность лингвистических правил, связанных между собой так, что в зависимости от результатов применения текущего правила однозначно определено, какое правило следует применить следующим
описываемой в настоящей работе У каждого из них есть свои достоинства и недостатки. Когда объем информации, на основе которой строятся алгоритмы, становится большим, специалисту предметной области (особенно при втором подходе) становится все труднее отслеживать ее актуальность, корректность с лингвистической точки зрения, проводить умозрительно какие-либо эксперименты с работой алгоритмов на различных примерах
Основная идея предлагаемой работы состоит в том, что оптимальным способом осуществления этого итеративного процесса является разработка специальной инструментальной программной среды, которая позволила бы сделать постоянное изменение реализуемой системы программ регулярным процессом Таким образом, актуальным становится создание специального инструментального средства для наглядного, предметно ориентированного представления лингвистической информации об анализе текста, предоставляющего возможность отладки и лингвистического эксперимента специалисту, реализующему систему лингвистических правил Представляемая работа описывает такую систему (Идея создания специального интерпретатора для отладки лингвистических алгоритмов была выдвинута М Е Епифановым, разработавшим также объектную модель, положенную в основу описываемой инструментальной среды, реализация которой была выполнена автором данной диссертационной работы)
Цель работы и задачи исследования
В работе рассматривается инструментальная среда, реализованная для предметно ориентированного моделирования лингвистических алгоритмов и произведения с ними различной сложности вычислительных экспериментов (от изменения порядка их применения до детальной отладки каждого из входящих в них правил) Предметной базой для реализации описываемой среды стали алгоритмы поверхностно-синтаксического анализа (ПСА) Т Ю Кобзаревой [15-18]
При помощи рассматриваемой среды решаются следующие задачи. 1. реализация специального инструментального средства для наглядного, предметно ориентированного представления лингвистической информации об анализе текста, предоставляющего возможность отладки и вычислительного эксперимента специалисту, реализующему систему лингвистических правил
-
моделирование лингвистических алгоритмов на входном языке, отражающем специфику предметной области, близком по структуре к оригинальной записи лингвистических алгоритмов (сделанной специалистом предметной области) и открытом как для пополнения новыми лингвистически значимыми конструкциями, так и для изменения структуры алгоритмов и их блоков
-
отладка лингвистических алгоритмов с предоставлением функциональности, аналогичной функциональности сред программирования (установка прерывания, трассировка, протоколирование, просмотр результата в разных видах)
-
проведение вычислительных экспериментов с лингвистическими алгоритмами, не требующее чрезмерно больших человеко-временных затрат
-
поддержка работы с большой совокупностью лингвистических алгоритмов на уровне структуризации и обозримости алгоритмов и актуальных для них примеров текстов
Методы исследования
Основным методом исследования проблемы реализации инструментальной среды для экспериментов с алгоритмами ПСА являлось применение принципа максимальной предметной ориентированности представления алгоритмов, обеспечения их отладки и вычислительного эксперимента с ними в условиях, приближенных к отладке программ в современных средах программирования.
Был проведен анализ «топологии» алгоритмов ПСА с точки зрения переходов от одного узла к другому. Были выявлены основные типы конструкций, используемых в записи правил, для чего реализована специальная БД
Научная новизна
Проблемы обозримости, поддержки, пополнения и отладки совокупности лингвистических знаний при создании систем анализа текста на сегодняшний момент в различных системах решается по-разному Либо при помощи тесного взаимодействия с программистом, реализующим лингвистические знания в виде готовой программной системы (но при этом общий язык для взаимодействия - естественный, что затрудняет формализацию знания, кроме того, переделка лингвистической базы требует существенной модификации программного кода), либо при помощи использования для записи правил специального формального языка (но при этом результат эксперимента виден только на выходе, а не «в процессе») Средства для отладки лингвистических
алгоритмов анализа текста в печати не представлены В связи с этим представляются новыми следующие результаты, автоматизирующие решение данных проблем
-
реализована адекватная предметной области объектная модель разработано представление алгоритмов, правил, обрабатываемых примеров
-
реализована соответствующая вычислительная модель, ориентированная на пошаговое выполнение алгоритмов с возможностью прерывать вычисление на каждом шаге и просматривать во время таких прерываний значения используемых в этих алгоритмах переменных, состояние вычислительной среды, вычислять пробные значения каких-либо выражений и т п
-
разработаны входные языки описания алгоритмов синтаксис, процедурная семантика (для инструментальной среды, для взаимодействия с другими приложениями с целью просмотра результата)
-
реализованы средства отладки лингвистических алгоритмов с широкими возможностями (проход по алгоритмам, просмотр результата в режиме реального времени, вычисление различных выражений с лингвистическими переменными, участвующими в алгоритмах)
Практическая значимость работы
Средствами реализованной инструментальной среды были промоделированы и отлажены частично или полностью следующие блоки алгоритмов Т Ю Кобзаревой [15-18] анализ случаев частеречной омонимии [20], наиболее часто встречающихся или синтаксически наиболее значимых, сегментация (разделение предложения на части, соответствующие отдельным исходным экстралингвистическим ситуациям простые главные и придаточные предложения и всякого рода обособленные обороты), внутрисегментный анализ (установление синтаксических подчинительных связей внутри каждой части предложения), более подробно описанные в разделе «Алгоритмы поверхностно-синтаксического анализа ТЮ Кобзаревой» диссертационной работы Часть алгоритмов была реализована в сжатые сроки в рамках дипломных работ при консультировании или под руководством [24, 33] автора данной работы В ходе моделирования и отладки были выявлены некоторые неточности, исправленные автором алгоритмов
Апробация и внедрение
Ход и результаты работы были представлены на следующих международных конференциях (библиографические ссылки см в разделе «Результаты изложены в следующих публикациях»)
конференция по компьютерной лингвистике «Диалог» - доклады с демонстрацией в 2004,2005,2006,2007 гг,
конференция по искусственному интеллекту «КИИ» - доклады в 2004,
2006 гг.
конференция по интеллектуальной обработке данных «НТИ» - доклад в
2007 г,
конференция по прикладной лингвистике MegaLing - доклад в 2007 г
Разработанные положения отражены в трудах данных конференций, а также в
статье с участием автора в журнале «Программные продукты и системы»
Задача имплементации синтаксического анализа определений терминов реализуется автором средствами описываемой в данной работе инструментальной среды в рамках гранта РФФИ № 06-06-80434
Структура работы
Диссертацию открывает Введение, за ним следует глава 1 - обзор затрагиваемой в работе предметной области В главе 2 описываются алгоритмы Т Ю Кобзаревой, ставшие лингвистической базой для реализации инструментальной среды для экспериментов с алгоритмами ПСА
В главе 3 описывается проект по объектному моделированию в лингвистике и место в нем описываемой инструментальной среды В рамках общего проекта разрабатывается модель лексики языка, основанная на синтезе лингвистических единиц, [11, 12] и ведется преобразование этой модели в модель для морфологического анализа [2]
Модель лексики языка, основанная на синтезе лингвистических единиц, в целом охарактеризована в [11, 12] В данных работах задачей было выработать универсальные форматы хранения информации, за счет которых можно было бы уменьшить ограничение применимости словарей Подход основан на идее представления языковых единиц, информации о них и отношений между ними в виде объектов, объединенных в многоссылочную структуру
Модель для морфологического анализа представляет собой еще один подход к созданию морфологического анализатора Базой его реализации является объектная модель, основанная на синтезе лингвистических единиц Поскольку исходными данными инструментальной среды для экспериментов с системой алгоритмов поверхностно-синтаксического анализа являются предложения текста, лексические единицы которых представлены объектами модели лексики языка, основанной на синтезе лингвистических единиц, становится «актуальной задача проведения морфологического анализа в данной инструментальной среде таким образом, чтобы совокупность его результатов для слов предложения непосредственно формировала бы исходную структуру данных для поверхностно-синтаксического анализа этого предложения» [2]
В главе 4 приводится описание объектной модели инструментальной среды Данная модель представляет собой расширение объектной модели многофункциональных словарей, основанной на синтезе лингвистических единиц [11, 12] Для моделирования лингвистических алгоритмов к данной модели добавляются следующие объекты
алгоритм - объект верхнего уровня, содержащий информацию о характеристиках моделируемого алгоритма, «основным» данным этого объекта является иерархическая (т е без циклов) сеть его узлов, по которой осуществляется проход алгоритма на конкретном примере,
узел алгоритма - объект, представляющий узел лингвистического алгоритма и содержащий ссылку на объект-правило и ссылки на «да»/«нет» узлы, к которым происходит переход в случае выполнения/невыполнения условий правила,
правило - объект, содержащий информацию о присваиваниях переменным алгоритма, проверяемых в правиле условий, действиях в случае выполнения условий, действиях в случае невыполнения условий,
объекты-присваивания, содержащие информацию о различного вида контролируемых присваиваниях значений используемым в алгоритмах переменным;
а также объекты, служащие непосредственно для вычисления алгоритма на конкретном примере
скоуп (от англ scope) альтернативы - объект, содержащий сведения об анализируемом предложении - исходные и уже полученные как некоторый вариант в результате анализа к данному моменту времени, а также представляющий соответствующее этому варианту состояние вычислительной среды применения алгоритма к предложению,
объект, представляющий применение алгоритма к примеру в целом -содержит пространство альтернатив, то есть совокупность построенных к данному моменту их скоупов с выделением обрабатываемого в данный момент, а также общие сведения об алгоритме и предложении
Вычисление алгоритма на конкретном примере происходит, начиная с самого верхнего узла алгоритма Переход к следующему узлу осуществляется в зависимости от результата вычисления условий, находящихся в правиле текущего узла В процессе вычисления алгоритма могут порождаться альтернативы - возможные варианты, например, синтаксической структуры предложения (как в примере Мать любит дочь) или грамматических характеристик слов предложения (например, для не снятой по тем или иным причинам омонимии) В рамках одной альтернативы возможен переход не более чем к двум узлам алгоритма Алгоритм может вызывать другие алгоритмы, аналогично вызовам процедур и функций в программировании
В главе 5 описываются входные языки инструментальной среды Для входного описания объектов используется следующие языки
графический (используется в графическом редакторе структуры объектов [10,19])
предметно ориентированный язык, основанный на синтаксисе Лиспа (такое Лисп-описание алгоритма создается для трансляции в объектную модель)
языки в синтаксисе xml (служат посредниками между инструментальной средой и приложениями для просмотра результата работы)
Язык графического конструктора объектов был разработан в рамках создания графического конструктора структуры объектов [10, 19] Конструктор позволяет рисовать диаграммы объектов модели в MS Visio и является ориентированным на эту модель приложением
Предметно ориентированный пополняемый язык, основанный на синтаксисе Лиспа, был разработан специально для описания правил ПСА В основу была положена
идея о присваиваниях и перечислениях (см Главу 4 диссертационной работы -«Объектная модель поверхностно синтаксического анализа»), также были рассмотрены основные предикатные обороты, использующиеся предметным специалистом при записи правил Подробно этот язык описан в Приложении 1 к диссертационной работе
Языки в синтаксисе xml для взаимодействия между инструментальной средой и приложениями для просмотра результата работы содержат описание всех необходимых этим приложениям данных и подробнее охарактеризованы в разделе «Просмотр результатов работы» Главы 6 диссертационной работы
В главе 6 описывается отладка алгоритмов ПСА средствами инструментальной среды Подсистема отладки описываемой инструментальной среды реализована аналогично режиму отладки в инструментальных средах разработки ПО (debug)
В рассматриваемой инструментальной системе предметом тестирования (не только с целью отладки, а иногда и для проведения эксперимента) являются
-
порядок выполнения алгоритмов в общей схеме ПСА,
-
различные варианты объединения правил в алгоритмы,
-
отладка алгоритма в смысле организации (взаимосвязи) составляющих его правил,
(4) отладка отдельных правил (их предметного содержания) в контексте
использующих их алгоритмов,
(5) отладка правильности Лисп-кодов, реализующих присваивания, условия и
действия в правилах
Основные возможности режима отладки описываемой инструментальной среды установка прерывания, автоматическое вьшолнение части алгоритма, пошаговое выполнение алгоритма, просмотр контекста выполнения, пробное вычисление выражений элементов правил, трассировка выполнения алгоритма, режим пакетного тестирования (возможность автоматически применять алгоритм к пакету примеров, при этом для каждого примера конечное состояние вычислительной среды, как результат его анализа, проверяется «прогоном» автоматически сгенерированных ранее тестов)
Для просмотра результатов работы было реализовано два приложения приложение, показывающее проход алгоритма в виде дерева с соответствующей функциональностью сворачивания/разворачивания узлов [1] (автор - Г ЮАйриян) и приложение для графического отображения связей, сегментов и характеристик лексических единиц примера (автор -ИМ Ножов [25])
При работе с рассматриваемой системой роли распределяются следующим образом Лингвист содержательно разрабатывает лингвистические алгоритмы Вместе с программистом они доводят их до готовности к представлению в объектной модели При необходимости программист пополняет входной язык описания алгоритмов, основанный на Лисп-синтаксисе Алгоритмы (новые или варианты уже имеющихся) испытываются как с целью отладки, так и для улучшения их структуры и т п При отладке программист выявляет неточности или ошибки в процессе вычисления алгоритмов В зависимости от характера ошибок их исправляет либо сам программист, либо программист вместе с лингвистом В случае корректного завершения вычисления лингвист анализирует результаты и, при необходимости, содержательно исправляет алгоритмы, а программист корректирует модель В итоге, если задача тестирования 5 (п 6 1) выполняется только программистом, то задачи 1-4 (п 6 1), как правило, -специалистом предметной области и программистом вместе, причем рассматриваемая в диссертационной работе инструментальная среда облегчает их тесное взаимодействие
В главе 7 приводится общее описание реализации инструментальной среды
Реализация объектов модели и связей между ними выполнена на языке Common Lisp [35] с использованием встроенной в него библиотеки CLOS (Common Lisp Object System) в инструментальной среде разработки Corman Common Lisp версии 2 5 [34], Common Lisp - это интерпретируемый язык Поэтому его использование существенно облегчает программирование среды для отладки, в ходе работы которой требуется именно интерпретировать выражения. В описываемой системе алгоритмы рассматриваются как данные по отношению к интерпретатору Для записи алгоритмов используется своеобразный языковой «конструктор», что обеспечивает легкость модификации При составлении описания алгоритма мы или манипулируем (добавляем, переставляем, удаляем) готовыми «кирпичиками» - объектами, представляющими правила, или только меняем содержание правил Объектная модель и является таким «конструктором».
В Заключении приводится характеристика основных результатов работы (см далее раздел «Основные результаты работы»)
В Приложениях к диссертационной работе приведены следующие описания В Приложении 1 приведен синтаксис языка описания алгоритмов ПСА структуры алгоритмов, системно-определенных форм («предметных» конструкций), синтаксиса описания примеров В Приложении 2 приведен пример выходного xml-описания алгоритма для графического конструктора объектов В Приложении 3 приведен
пример оригинальной записи алгоритма и его представления на входном языке, основанном на синтаксисе Лиспа В Приложении 4 рассказывается о методике предварительного обозрения алгоритмов ПСА В Приложении 5 приведены некоторые примеры работы промоделированных средствами инструментальной среды алгоритмов, описанных в диссертационной работе
