birmaga.ru
добавить свой файл

1

Повышение производительности при распознавании текстовых ситуаций

Д.А. Кормалев1

Введение


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

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

Основные определения

Будем рассматривать особенности сопоставления для системы обработки текста, использующей один из диалектов языка CPSL [Appelt, 1996] или язык, основанный на CPSL с добавлением новых элементов, например, логических или функциональных. Использование языков такого типа подразумевает представление информации о тексте и его разметку при помощи специальных объектов — аннотаций (описаний) [Grishman, 1998; Кормалев, 2004].


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

Из любого множества аннотаций может быть построен так называемый граф аннотаций. Аннотации обычно представлены вершинами, а отношения между ними — дугами этого графа. В простейшем случае рассматривается только отношение непосредственного следования (без транзитивно замыкающих дуг) на множестве интервалов, границы которых совпадают с границами аннотаций. В этом случае граф аннотаций изоморфен некоторой диаграмме Хассе целочисленного интервального порядка [Fishburn, 1985], определенного на множестве аннотаций. Для некоторых задач оказывается полезным ввести в граф аннотаций дополнительные виды дуг-отношений: например, дуги, выражающие отношения взаимного расположения аннотаций, структурные или содержательные отношения между фрагментами текста [Кормалев, 2005].

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

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


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

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

Анализ потоков управления

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


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

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

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


  1. Разбиение каждой дуги в графе переходов КП с введением дополнительной вершины, в которую переносится пометка дуги. Впоследствии эти дополнительные вершины будут вершинами управляющего графа.
  2. Исключение исходных вершин с добавлением новых дуг. Новая дуга проводится из вершины A в вершину B, если существует путь из A в B, проходящий только через исходные вершины. В действительности в таком пути может быть не более одной промежуточной исходной вершины. По построению, после шага 1 смежными могут быть только исходная и дополнительная вершины; не допускается двух смежных исходных (дополнительных) вершин. Заметим, что A и B могут совпадать.


Введем некоторые определения (они схожи с определениями теории графов).

Обязательный предшественник (доминатор) для некоторой вершины a управляющего графа — такая вершина b, что b принадлежит каждому пути из начальной вершины управляющего графа в a (обозначается b dom a). Из определения следует, что dom a. Вершина b строго доминирует над вершиной a, если .

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

Фронт доминирования вершины a управляющего графа — множество всех вершин w, для которых a доминирует над предшественником w, но не доминирует строго над w.

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

Для определения доминаторов вершины n в заданном управляющем графе с начальной вершиной необходимо найти максимальное решение следующих соотношений:




,

где — множество доминаторов вершины n,

— множество предшественников вершины n.

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

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

Сформулируем прямой итерационный алгоритм построения множества доминаторов для всех вершин управляющего графа.

// Доминатор входа управляющего графа – он сам

Dom(n0) = {n0}

// Сначала для остальных вершин в доминирующее множество

// включаются все вершины

для каждого n из (N - {n0})

Dom(n) = N;

// На каждой итерации исключаются вершины,


// не являющиеся доминаторами

пока Dom(n) изменяется

для каждого n из (N - {n_0})

T = (пересечение Dom(p) для всех p из предшественников n)

Dom(n) = T + {n}

Сложность этого алгоритма , где N — множество вершин управляющего графа. Существуют более эффективные (и сложные по устройству) алгоритмы построения множества доминаторов: алгоритм Ленгауэра-Тарьяна [Lengauer, Tarjan, 1979] и сравнительно новый алгоритм, основанный на исследовании фронтов доминирования, с использованием вспомогательных структур данных для повышения эффективности [Cooper et al., 2001].

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

Оптимизация выполнения тестов при сопоставлении

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


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

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

A (all) — классы из тестов, связанных квантором всеобщности.

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

D (dependent) — классы из тестов, связанных квантором существования, для которых состояние перебора необходимо сохранять и изменять при бэктрекинге (например, выражения с переменными), и зависимые от них классы.

Тесты, связанные с блоком типа A, самостоятельны; более того, несложно показать, что достаточно строить блок типа A для каждого теста, связанного квантором всеобщности; рассматривать транзитивные зависимости между классами необязательно. Если классы из двух блоков типа A совпадают, эти блоки можно объединить (с сохранением информации о тестах). Блоки типа F строятся в обычном порядке с определением транзитивной зависимости. Если класс может быть отнесен и к блоку f типа F, и к блоку d типа D, он относится к d; кроме того, f присоединяется к d. В блоках типа D отдельно рассматриваются первичные классы (непосредственно использованные в тестах, которые могут повлиять на дальнейшее сопоставление, например, в присваивании переменных) и зависимые классы (использованные в прочих тестах).


Блоки типа A однократно проверяются в самом начале. Ясно, что выгодно начинать перебор с коротких блоков. Затем проверяются ограничения, из которых построены блоки типа F. Перебор также начинается с коротких блоков. Состояние перебора, при котором произошло успешное сопоставление такого ограничения, в дальнейшем изменяться не будет. Для первичных классов из блоков типа D необходимо вести перебор элементов декартова произведения с сохранением информации для бэктрекинга. Для зависимых классов осуществляется сквозной однократный перебор зависимых классов, как и в случае с локальными ограничениями (противоречия при выборе кандидатов в блоках D и F не возникает, поскольку множества аннотаций в блоках D и F не пересекаются — по построению).

Оптимизация операций со строками


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

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

Заключение


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

Работа выполнена при поддержке программы ОНИТ РАН «Фундаментальные основы информационных технологий и систем» — проект № 2.2 «Развитие методов обработки текста на естественном языке на основе использования неоднородных ресурсов знаний».

Работа выполнена при поддержке научно-технической программы Союзного государства «Разработка и использование программно-аппаратных средств Грид-технологий перспективных высокопроизводительных (суперкомпьютерных) вычислительных систем семейства "СКИФ"» — проект «Сервис анализа текстовой информации на базе грид-инфраструктуры».

Работа выполнена при поддержке научно-технической программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем» — проект «Исследование и разработка параллельных алгоритмов анализа больших объемов текстовой информации из глобальной сети и алгоритмов принятия решений на основе когнитивных методов».

Литература


[Кормалев, 2004] Кормалев Д.А. Представление лингвистической и предметно-ориентированной информации при помощи аннотаций // Тр. семинара ИАИ-2004. — Киев: Просвiта, 2004. — С. 120-128.

[Кормалев, 2005] Кормалев Д.А. Автоматическое построение правил извлечения информации из текста // Тр. Первой междунар. конф. «Системный анализ и информационные технологии» САИТ-2005, Переславль-Залесский, сентябрь 2005 г.: В 2 т. — М.: КомКнига, 2005. — Т. 2. — С. 205-209.


[Appelt, 1996] Appelt D.E. The Common Pattern Specification Language: Technical report / SRI International, Artificial Intelligence Center. — 1996.

[Appelt, Israel, 1999] Appelt D. E., Israel D. J. Introduction to Information Extraction. Tutorial // Sixteenth Int. Joint Conf. on Artificial Intelligence IJCAI’99, Stockholm, Sweden, 1999.

[Cooper et al., 2001] Keith D. Cooper, Timothy J. Harvey, Ken Kennedy. A Simple, Fast Dominance Algorithm. Software Practice and Experience, 2001.

[Fishburn, 1985] Fishburn P.C. Interval Orders and Interval Graphs. John Wiley & Sons, New York, 1985.

[Grishman, 1998] Grishman R. TIPSTER Text Architecture Design. Version 3.1. — New York: NYU, 1998.

[Lengauer, Tarjan, 1979] T. Lengauer, R.E. Tarjan. A fast algorithm for finding dominators in a flow graph. ACM Transactions on Programming Languages and Systems, 1(1):115120, July 1979.


1 152020, г. Переславль-Залесский, ИПС РАН, Исследовательский центр искусственного интеллекта; dk@conrad.botik.ru

2 В настоящее время проводятся эксперименты. Приведены предварительные результаты. В течение 1-2 недель будут получены точные результаты с указанием конфигураций.