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

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

УРАЗЛИН ЮРИЙ КЛИМЕНТОВИЧ

АНАЛИЗ СЛАБО СТРУКТУРИРОВАННЫХ ТЕКСТОВЫХ ДАННЫХ

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

программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2005

Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)

Научный руководитель:

доктор физ.-мат. наук, профессор Флёров Юрий Арсениевич

Официальные оппоненты:

доктор физ.-мат. наук, профессор Павловский Юрий Николаевич

доктор физ.-мат. наук, профессор Афанасьев Александр Петрович

Ведущая организация:

Московский государственный институт электроники и математики (технический университет)

Защита состоится « 2.1 » декабря 2005 года в _час. на

заседании диссертационного совета К212.156.02 в Московском физико-техническом институте по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер., д. 9.

С диссертацией можно ознакомиться в библиотеке МФТИ.

Автореферат разослан «_№__» ноября 2005 г.

Ученый секретарь диссертационного совета —--7 Федько О.С.

иит

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

. -АГ

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

Цель работы

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

1. рассмотрена задача анализа текстов на естественном языке (NLP, natural language processing), выявлены сходства и различия решения этой задачи и задачи анализа слабо структурированных текстовых данных;

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

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

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

I '

Научная новизна

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

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

1. этапы указания примеров и применения полученного алгоритма анализа объединены, что облегчает обучение программы новому формату, практически устраняя дополнительные действия пользователей;

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

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

4. предложен метод автоматического сравнения адекватности возможных способов реализации графематического анализа решаемой прикладной задаче;

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

При решении задачи анализа текстов с вопросами:

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

2. с помощью предложенного в работе метода выбран способ выполнения графематического анализа;

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

4. экспериментально исследована эффективность предложенного в работе способа выполнения анализа.

Практическая ценность

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

Предложенный способ анализа слабо структурированных текстов существенно сокращает сроки анализа авторских документов, содержащих неструктурированное представление информации, которая используется системами дистанционного обучения. Разработанный с его помощью инструмент анализа текстов с вопросами способен в кратчайшее время построить структурированную модель содержащейся в авторских документах информации, и проанализировать тексты с тысячами вопросов. Он использовался при создании программных комплексов «Физика 7-11 классы» и «Биология, химия, экология». В настоящее время системы дистанционного обучения, разработанные компанией ФИЗИКОН, широко используются в процессе обучения, тестирования и самопроверки.

Апробация работы

Основные результаты работы докладывались и обсуждались на научных конференциях МФТИ (Долгопрудный, 2003, 2004, 2005), научных семинарах кафедры математических основ управления МФТИ и Центра сетевых образовательных технологий и систем МФТИ, на международной конференции «Компьютерное моделирование 2005» (Санкт-Петербург, 2005).

Публикации

По теме диссертации опубликовано 8 печатных работ.

Структура и объем работы

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

В главе 2 описан предлагаемый общий способ решения задачи анализа слабо структурированных текстовых данных, то

У

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

Рассмотрена задача анализа текстов на естественном языке, для демонстрации того, как методы её решения были адаптированы для решения рассматриваемой в работе задачи. Подробно рассмотрены реализации графематического и синтаксического этапов анализа. Указаны сходства и различия задач анализа текстов на естественном языке и рассматриваемой задачи. Так, в МЛ* этап графематического анализа, имеет относительно простые способы решения. Реализация синтаксического анализа текстов на естественном языке является намного более сложной. Её сводят к задаче классификации объектов на основе набора признаков, что позволяет успешно применить для её решения богатый арсенал областей Искусственного Интеллекта и Обучения Машин. Описаны различные подходы к его решению

1. основанные на индукции правил методы

2. методы, основанные на прецедентах

3. статистические методы

4. комбинированные методы

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

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

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

2. Пользуясь алгоритмом, выполнить анализ текста.

3. Выявить ошибки анализа

а. Если есть ошибки, то перейти к шагу 4.

Ь. Если нет ошибок, то перейти к шагу 6.

4. Определить, как надо правильно анализировать небольшую часть текста, содержащую ошибки

5. Скорректировать алгоритм анализа и перейти к шагу 2.

6. Анализ текста завершен.

Схема процедуры выполнения анализа представлена на

следующем рисунке.__

О

J\

1/'

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

И

Программа выполняет мм вщ* и*

проверенного текста используя текущий [ алгоритм. строит структурированную модель информации

Пользователь Просматривает документ и лроввряет есть ли ош иОда? L

Пользователь указывает как надо правильно выполнять анализ, исправляет несколько ошибок

_У I- Программа автоматически корректирует Я

\ I--алгоритм анализа Щ

хждкаша—ивд Рисунок 1. Схема процедуры выполнения анализа

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

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

Выполнение анализа документа делится на два относительно простых этапа:

1. Графематический

2. Синтаксический

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

Предположим, заданы два набора графематических типов: {Т1;} и {Т2,} и необходимо определить, какой набор эффективнее для решения некоторого класса задач. Сравнение эффективности использования различных наборов графематических типов выполняется с помощью понятия энтропии, и основывается на следующем предположении. Чем «больше порядка», при прочих равных условиях, в полученных в результате графематического анализа последовательностях лексем, тем проще выявить закономерности в текстовых данных на последующем этапе синтаксического анализа. Для сравне-

ния используется образцовый набор текстов, который содержит особенности текстов выбранной прикладной задачи. Для сравнения наборов необходимо выполнить графематический анализ образцовых текстов с помощью каждого сравниваемого набора графематических типов. В результате анализа получаются две последовательности лексем {Ы;} и {1Д}. Пусть этим последовательностям лексем соответствуют последовательности типов лексем: {ЬТ1;} и {ЬТ2,}. С помощью следующей формулы можно определить условную энтропию в последовательностях типов лексем.

#п = - 53 рф-) * 1°91РЬ1 и)

♦Ч?

= ~5* 1°92Р{Ь^Л 4- УМ^.Л * 1<>У2р(М)

= - 53 Р(Ь^Л * 1°92Р{к*]) + 53 Р(ЬЛ * 1°92РФг)

га г

Рисунок 2. Формула расчёта энтропии последовательности типов

лексем

В этой формуле

• Ь] — это блок из п-1 типа, j - произвольный тип, который следует за Ь;

• р(Ь^) - вероятность последовательности Ьь)

• рыб) - условная вероятность типа 3 при условии Ь;, то есть рф|иНр(Ь0

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

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

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

(NP Уои) (VP will stort to see) (NP shows) (ADVP where)

(NP viewers) (VP program) (NP the program).

You B-NP

will B-VP

start I-VP

to I-VP

see I-VP

shows B-NP

where B-ADVP

viewers B-NP

program B-VP

the B-NP

program I-NP

0

Рисунок 3. Выделение групп лексем с помощью разбиения

на классы

То есть объединение лексем в группы эквивалентно отнесению лексем к элементу заранее заданного множества классов.

12

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

Вход: объекты и свойства Выход: синтаксические классы

You PRP B-NP

will MO B-VP

start VB I-VP

to TO I-VP

see VB к I_VP

shows NNS [ -' \ B-NP

where WRB v B-ADVP

viewers NNS B-NP

program VBP B-VP

the DT B-NP

program NN I-NP

О

Рисунок 4. Выделение групп лексем как классификация объектов

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

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

• задан объект, обладающий набором свойств;

• заданы примеры правильного выполнения классификации, то есть объекты, обладающие аналогичными свойствами, и правильно определённые их классы;

• необходимо проанализировать примеры, на их основе составить алгоритм классификации, и с его помощью определить класс рассматриваемого объекта.

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

public interface Classifier

С

th>3 :s used tc ь"-; ckspfietf sampler

//fr.is tnefhod ,s чг.-ск^з fcr &cct ¿лт>p/e void learn(Case c, Object clazz) throws Exception;

//2 after el! samples are iecrred this method is invoked //to deduc* elas£>f>ca7ion Шдсп^г::--void trainO throws Exception;

/, ' than rhis юетпо 7 >s i»,:ked 12 fcvde canes tc be cia? ч'.Ъея

void setCaseSource(CaseSource caseSource);

//•i and final" ths :ne to set prtdic fad doss cf ever' case

//. n CaseSjurce

«»id predictO thro«» Exception;

}

Рисунок 5. Представление произвольного способа классификации в

программе

Описаны исследованные при решении задачи анализа текстов с вопросами способы классификации:

• Модель максимальной энтропии

• Способы, основанные на индукции правил Проведён обзор принципов работы этих методов, главные преимущества и недостатки.

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

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

• определяемые прикладной задачей;

• специфические для конкретного текста.

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

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

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

Название Регулярное выражение

Перенос строки \г|\п|\г\п

Открывающий тег

Закрывающий тег <Л\\у+Гл>1*>

Пробел

Число

Слово

Пунктуационный знак конца предложений [\.,\!Л?1

Пунктуационный знак

Другое Г\з1

Рисунок 6. Набор графематических типов для анализа документов

с вопросами

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

Название Регулярное выражение

Число, точка \<ИЛ.

Буква в скобках \(\М)

Буква, точка [а-Ь, А-Н]\.

Заглавная буква ГА-Н1\в+

Символ звёздочки 1\*1+

Рисунок 7. Дополнительные графематические типы

На этапе синтаксического анализа решаются две задачи классификации:

• Строк при определении границ вопросов

• Лексем при выделении атрибутов вопросов

Для этих задач построены два способа решения, основанные на индукции правил. Оба способа построения алгоритма работают по тому же принципу, что и описанная в работе система АЫлБ: сгенерировать - проверить - уточнить -проверить - уточнить, и т. д. Также исследована возможность применения статистических методов классификации, экспериментально определено, что Модель Максимальной Энтропии, неприменима для этой прикладной задачи.

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

• список свойств объектов - {Р,}, .. Оо

• множество наборов контекстов объектов - {Ь*}, ¡=1..ло

• каждый контекст Ь, - это набор значений свойств - { V,,}

• присвоенные объектам классы - {С;} Способ построения алгоритма:

1. Выбирается первый образец - первая строка. ¡=1

2. Выбирается первое по важности свойство из списка PJ (]=1), фиксируется его значение - Уу.

3. Пусть класс, присвоенный строке - С,.

4. Строится правило:

Ь е(Ву = {Ь: Рт= У|т,т=1 ....¡)=>^

5. Правило проверяется на наборе образцов.

a. Если найдётся такой объект {Ьк, Ск}, что Укт=У,т, т=1 ..0, но Ск^С;, то правило объявляется неправильным. Правило уточняется: j=j+l. Алгоритм переходит к пункту 3.

b. Если такого объекта нет, то правило считается верным, и добавляется в список сгенерированных правил. Все объекты, которые ему удовлетворяют, исключаются из рассмотрения. Алгоритм переходит к следующей строке (Н+1), к пункту 2.

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

Рисунок 8. Пространство и способ поиска правил при выделении

вопросов

Для классификации необходимо использовать набор свойств, составленный из графематических типов первых и последних лексем рассматриваемой, и соседних с ней строк. Определено, что сложность этого алгоритма - ООо* ¡о2)- Оценено время, необходимое для построения алгоритма, из чего следует, что для устойчивости алгоритма программа может использовать в качестве примеров правильной классификации также объек-

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

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

[свойство Р1 (графематический тип лексемы)

, Свежи во РЗ (с*6ч^^>чес*ии тип присвоенный Гу ^упредыдуц^ей лексеме) ч _

Текст задания j | Идентификаторвопроса [ Идентификатор варианта ответа j fj

L_

■SE

.s.

*

Рисунок 9. Пространство и способ поиска правил выделения атрибутов вопросов

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

1. Фиксируется первый образец, i=l.

2. Выполняется попытка построить самые общие правила, используя только одно свойство объекта, п=1.

3. Выбирается подмножество свойств объекта Conditions = {Vimk}, из множества свойств образца такое, что

|| Conditions ||=п. Здесь Шк - набор индексов, такой, что mie <}о, а |К|| =п.

a. Подмножества для каждого фиксированного значения п и i перебираются последовательно.

b. Если все возможные подмножества уже перебраны, то правило утоняется, п=п+1. Если n=j о, то алгоритм переходит к следующей лексеме (i=i+l), к шагу 2.

4. Проверяется на противоречивость правило:

Ъ е(В0 ={Ь: Ртк=У1тк)=>^

a. Если найдётся такой объект {Ьр, Ср}, что Vpmk=Vimk, для всех Шк, используемых в Conditions, но Ср^С,, то правило объявляется неверным. Алгоритм переходит к шагу 3 (рассматривается следующее подмножество, или правило уточняется).

b. Если такого объекта нет, правило считается правильным, оно добавляется в список сгенерированных правил, а все объекты, которые ему удовлетворяют, исключаются из рассмотрения. Алгоритм переходит к следующему образцу (i=i+l), к шагу 2.

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

o[io ¿С* j. Потому для разумной производительности необходимо при обучении использовать лишь явно указанные примеры. Неявно заданные примеры выполнения классификации, которые указывает пользователь, исправляя ошибки анализа в тексте после них, учитывать нельзя, поскольку это приведёт к недопустимым потерям производительности.

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

(номер вопроса) (текст вопроса) ((:1 варианта) (текст варианта))+ (маркер правильного ответа) (правильным vi в --г) (маркер п:'Дс/ч5к,;) (подсказку) ((название доп. атрибута) (значение доп. атрибута))*

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

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

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

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

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

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

В заключении приведены основные результаты диссертационной работы.

Основные результаты работы:

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

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

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

модели задача синтаксического анализа решается как определение класса объекта на основе его свойств.

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

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

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

По теме диссертации опубликованы следующие работы:

1.Уразлин Ю.К. Применение прецедентов для построения систем поиска в неструктурированных данных. // Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLV научной конференции. /Моск.физ. - техн. ин-т. - М. - Долгопрудный, 2002. - С. 65.

2.Уразлин Ю.К. Анализ слабо структурированных текстовых данных. // Моделирование и обработка информации: сб.ст. /Моск.физ.-тех. ин-т. - М., 2003. - С. 108-118.

3.Уразлин Ю.К. Анализ слабо структурированных текстовых данных. //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVI научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2003. - С. 62-64.

4.Уразлин Ю.К. Выделение групп лексем при анализе слабо структурированных текстовых данных. // Моделирование процессов управления: сб.ст./Моск.физ.-тех. ин-т. -М., 2004.-С. 95-105.

5.Уразлин Ю.К. Автоматическое выявление ошибок при анализе слабо структурированных текстовых данных. //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVII научной конференции. /Моск. физ. - техн. ин-т. - М.Долгопрудный, 2004. - С. 105-106.

6.Уразлин Ю.К. Анализ слабо структурированных текстовых данных в системах дистанционного образования. // Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т. - М., 2005. - С. 150-157.

7.Уразлин Ю.К. Автоматизация формирования наборов тестов в системах дистанционного образования. // Компьютерное моделирование 2005: Труды VI международной конференции. / СПб: Издательство Санкт-Петербургского государственного политехнического университета, 2005. - с. 566-573.

8.Уразлин Ю.К. Использование методов обработки текстов на естественном языке для анализа слабо структурированных текстовых данных. //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVIII научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2005. -С. 84-85.

05-2 27 09

РНБ Русский фонд

2006-4 23185

Уразлин Юрий Климентович Анализ слабо структурированных текстовых данных

Автореферат

Подписано в печать 14.11.2005. Усл. печ. л. 1.5. Тираж 80 экз. Заказ № 435.

Московский физико-технический институт (государственный университет) Печать на аппаратуре Rex-Rotary Copy Printer 1280.

141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Введение.

Решаемая проблема.

Пример.

Описание решения.

Сравнение с другими подходами.

Содержание.

Глава 1. Постановка задачи.

Вход.

Вопросы.

Оглавления.

Требования к программному обеспечению.

Информация о продаже товаров.

Преобразование.

Полуавтоматический анализ.

Процедура анализа текста.

Выход.

Модели представления структурированной информации.

Формат выхода.

Глава 2. Общий способ анализа.

Связь с анализом текстов на естественном языке.

Анализ текстов на естественном языке.

Графематический анализ.

Синтаксический анализ.

Применимые к рассматриваемой задаче методы.

Предлагаемое решение.

Выделение этапов анализа.

Графематический этап анализа.

Синтаксический анализ.

Автоматическое выявление ошибок. t

Глава 3. Анализ текстов с вопросами.

Графематический анализ.

Синтаксический анализ.

Выделение объектов первого уровня - вопросов.

Определение частей вопросов.

Автоматическое определение ошибок.

Глава 4. Инструмент анализа.

Выделение вопросов.

Определение атрибутов вопросов.

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

Сохранение результатов анализа.

Глава 5. Экспериментальные результаты.

Формат 1.

Формат 2.

Формат 3.

Формат 4.

Формат 5.

Решаемая проблема

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

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

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

Репоэитарии текстовых данных

Модель представления информации - язык, ориентированным на отображение

АИ t ah. tos*

Wt

Несоответствие модели представления текстовой информации в репозитариях и модели представления запросов

Запросы пользователей, и программ, использующих информацию

Вопросы X по географии, сложность от 2 до 5 кол-во вариантов > 3

Рисунок I. Несоответствие моделей хранении информации н операции пользователей

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

С другой стороны, информация в текстовых документах, которые хранятся в репозитариях текстовых данных, представлена на языках, ориентированных на отображение. Например, на языке разметки HTML [w3c HTML], или на языке инструкций текстового процессора Microsoft Word, отображающего текст. При этом соответствие между конструкциями языка представления (элементами разметки, инструкциями процессора, и т.п.) и логической структурой информации, содержащейся в документах, в большинстве случаев отсутствует. Можно считать, что тексты представлены лишь в виде последовательности символов без указания какой-либо логической структуры содержащейся в них информации, то есть каждый документ содержит много логических единиц информации, которые никак не выделены, и связи между которыми никак не заданы.

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

Запросы пользователей, и программ, использующих информацию

Репозигарии текстовых данных

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

Анализ V

Явно заданная структурированная модель представления информации

Рисунок 2. Решение проблемы несоответствия моделей

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

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

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

Пример

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

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

На следующем рисунке представлены примеры таких документов, содержащих вопросы.

Chapter 10 Personal SCrrss Management

MULTIPLE свша

1 The nonspecific response of the body to any demand mad* upon it is th* definition of. a. adaptive re *pons e b. remittance c. strete d. homeostasis

А КЗ с stress PO: 286 DIF: 1

2 Those things thai upssl or excde us axe known at: a stressors b life «vents c. changes d. negative thaugW*

AN5: a. stressors PO: 386 DIF: i

Which of the following describes eusUestf a. chronic slran b positive stress c. nonspecific response d. negative stress

ANS: b positive stress PO: 286 DIP: 2

ID: 1

AUIIKH: MJflUJH aim; BR

Content: Test: О MAT Ptfflculty: 4 EiHtoi:

EiMoi Statiu:

The idBB that "actions apeek louder than wPKte' derives from Aristntls who wrote ftat II is our choice of oaad ovsr evil thai determines our characler. not our opinion afeout good or evil.

A. deiWee from Aristotle who wrote that It is our cftoice of good ewer evil to at determines our character

0 derives from Aristotle who wrote that it ia our choke of good over evil determining our character

C. derives from Aristotle's view that it i9 our choice of good over evil that determines our character

The correct answer is (С), тпе original Incorrectly Places Aristotle aa the oCiact of| the preposition from. The quote derlree from something Aristotle wrote, not from Aristotle himeeif, so (A) is wrong. (B) and (E) contain the same error. (D) IjlffllSiitlY follavw wewwlth a prepoeition rather than /rtel.

ID: 2

Author Ma or am aim; 9R Content: Test: О MAT Difficulty: 2 Ed It си:

E<INm Status:

Al least onca a year, not only твазигв the lenath of each foot but also IhB width pfeach fpo| in order to be sure that shoes fit property.

A not only meaeure the length of each foot but also tne width of each foot

Section 2.1

1. How many of Bib elements эге known to occur In natur» (can be found outslOE of laboratories)''

A. 26

B. 106

C. 112

D. ее

E. « aiabali

A 26 elements are Know to be necessary for life, but others are found in nature

B. Your penodic taDle may list IDG elements, but not all ol these are found in nature.

С At least 113 elements have been discovered or synthesized, but not all of these are foirtnnaure

D. CORRECT

E. Artstoue would De proud

2. What is the name ol the element that has the chemical symbol А)? A silver e. gold

C. argon

D. aluminum E albert

Analysis

A The symbol for sih/er Is Ag. в The symbol for gold Is Au

C. The symool tor argon Is Pi.

D. CORRECT

E. "Albert" Is not an element

3. What Is the nana of the elemerrt that has the chemical symbol Ha?

A. oeryllum

B. banum

C. boron О sodium

F harry

CHAPTER 5 FREEDOM AND DETERMINISM

MULTIPLE CHOICE QUESTIONS

Note: An asterisk denotes the correct answer

LAxMsais a mental act of choosing or deciding." a drive. 5. an obsession. 4 a compulsion.

2. Determinism is the thesis that g. volitions determine actions, tj. actions determine volitions. 5. every event has a cause* 4 the will determines volitions.

3. The truth of Determinism is presupposed by

3. the First Cause argument for Cod's existence, tj the Design argument for God's existence. 5. the version of Dualism. 4 all of the above*

Which is not apart of descriptive statistics? Correct.

Descriptive statistics deals with organizing data. Incorrect Descriptive statistics deals with summarizing data. teisatiagiMi

Incorrect Descriptive statistics deals with presenting data

Statistics can be used to do all of the following except

Guarantee a correct answer.

Correct

Estimate a parameter.

Incorrect. Statistics can be used to estimate a parameter. Compare two populations.

Incorrect^ Statistics can be used to compare two populations. Determine whether two variables are related. besrrect. Statistics can be used to determine whether two variables are related.

Рисунок 3. Примеры документов с вопросами

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

Рисунок 4. Фрагмент документа с выделенными элементами информации - вопросами

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

IIJ The nonspecific response of the body to eny demand made upon his the definition of: ^^ e. adaptive response b. resistance c. stress d homeostasis

ANS: c. stress PG: 286 DIF 1

1\ Those things that upset or eicite ui en known it: a. stressors b. Hfe events c. changes d. negative thoughts

ANS: t. sties son

PO: 286

DIF: 1 О

3/ Which of the following descnbes eustress? i chronic stress b positive stress c. nonspecific response d. negative stress

ANS: b. positive stress PG 286 DfF: 2

MUot: МЗДШЗ

Шага; SR Coieeitf: Test; OMAT DtmcMly: 4 Editor:

Е<11ин Stain»:

The idoa thafactlorra speak louder than words": that It Is our Cfiaco of good over evil that determines our character notour opinion about good or evti.

A de rives from Aristotle who wrote that it is our choice of flood over evil that determines our character

В derrree from Aristotle who wrote that it is our choice of good over evil determining our character

C. derives from Aristotle's view that it is our choice of good over evil trial determines our character

The correct answer is <C) The original in correct* places AriatoUe as the oblect of| the preposition from The quote dertves from something Aristotle wrote, not from Aristotle himself, so (A) is wrong. (B) and (E) contain the same error. (D) ШйШоЙЙ follows vfewwith a preposition rather than that.

АипГСЯ: йШиаи йваж SR

СогЯмЯ:

Тем: OMAT млату: г E<l>oi:

EtIRoi stani«:

Рисунок 5. Идентификаторы вопросов

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

МчЦа.1т1иг1.5»«ИИди diopter 1: Yon in tb- Digital Ар Multiple ClioK? t Jin the Future, "tqleputerr' wijl bjji J a people who work on ta ^computer! and communicate by phone b. a combination of TV and computer pv color computer* telcvitjonj with more cable offering, с a]] of the above

ANS; В mvolvej a dffecs ifianng of e*penenee between two people & и the i am с a» rotrapcryqcigl convmurucancn 5. allows for the most drect feedback of alt types of communication j involves a lender, message, receiver and channel t all of the above

ANS: D

3 л conversation with Й mas: communication 5ШЕ5Ш1Й1 с ommunication

4 mterperional ctMnmunication e confidential communicaficm

ANS: С

Рисунок 6. Текст задания

За текстом задания следуют варианты ответов. При этом иногда непосредственно при перечислении возможных вариантов ответов указан правильный вариант, для этого в примерах используется символ «*», или текст «Correct».

I. In the future, "telejjuters" will be: a Ipeople who work on home computers and communicate bv phone and modem.] b. la combination of IV and computer. 1 c.[color computersj d.|televisions with more cable offerings .e. |all of the above j

LAxaliUsais

А 1а mental act of choosing or deciding]* fa. I a drivel ** g [an obsession"] указатель правильного варианта

Д. |a compulsion, [

Aiittioi; щш: SH

Г no isea Ih aT a t Лапь «р в *K boder № an wen*" QBrtvs from АлИой§ W,o wrota in H il li рш f ftoir* gf flgflfl ww tvw fafi oeiawmififli о it tn arat^r. noi our

ОИЧ1&П » put poo и (И evil

Л dimsi from Arlttolti who wrote in at it i в our th><0 or good over evil in dfftHimlna» out ehaifttter н denve в (тот Aria tot* wtiD wnte that it Is our с ftoke of good отчг e*l □ иИятитп о our character

С. derive ■ from Annotie и w»w in at rt n our chote* ol ge ed over ovj itiai

Tna tarred answer ■ (C) The original IncoiracUy ptatti Anitotle « me Qfejeci or| tna prapnfton from Trip aual* Овп*вв from aomelfiwg Anatoli» wrel#, nol from Л/isioba nmseff, (о СЛ) J в wrong <BJ and {£) contain vrc same error (D) UlUtLSjft folflwft wewwitft 4 prapoelfcon talncrtnan ifte* 2 A mil**; wiywt зя

Сы*«ге: Ta«C OWAT ОИПспНу: 2 гаим.

E'llltQI Stahia: aj la aai огня a notenfr mnaaurg ipf hnnfli of aaen foot out lUo the * pf q цеп To ot in order lo Ее «и w №f eho и at property

А па) only meaaura Iha lengift of each ton! but alio Ifte width ol each foal

Incorrect. Descriptive statistics deals with organizing data [Summarizing data~ nptive statistics deals with summarizing data. I Presenting data I

In^orregt Descriptive statistics deals with presenting data

Рисунок 7. Варианты ответов

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

I ТЬеnmfpscificrt гропзе of tbr body to *nj? demand Elide uponil LlUl* dffiraUDfl of

4 idiptlVf rtipOfBi b. rillfonct с иге» d htrmtotton J'j:l]

DIP: I

1 How many of ffw clencnta am hnowi to OCCiT In nitura [can be found outvHJe оt laOora'.oriBjp A 26 0 IDS С 113 О BH t 4 iryu.

A 26 elements й'с known to be песеяагу for trfe cut otners are fourifl in nature В Vow репож taeie may Hat 106 but гн* an of Bie-ж are found « nature r п.-n' i miMPiPfii-. nave been discovered or ?yntncjueo. out not at of (new are feu с ri ш

CORRECTS be (VOUO

ID: 1

Auiiiui: (^адДОЕ sr Content: Teal: О MAT ovnciikr; ■»

Ed Hoi:

Edtoi St.unit;

The idea tharertior» speak louder than woida'tl aat n л ш сдаст дот vm rut nm лишим ид впадав, notour pinion about good or ети a darws from Afiatom who w*ola that К is our choice of good over evil inal treteimines ourehaieeief

В derw®5 from Anttotte who wrote thai It la our c/cjce of good ovar evil deiBflmning our character

C. derives from Aristotle's new inal il ifi our сftok» of good over evil Ihat determines our character

Tnesgrraet answer« (ClThe ongmai incorrectly places Anslolie as the obietrl of| tne prepoMliri fi'om i nequole aerrvea from somelhlng AfltloUe wrolef nol from Aiistolle tirrr.eif to (A3 la wrong (B) and (E) contain the same error (D) follow» yj»w witn a preoosilion ramertnan Iftef

3- a mental act of choosing or decidin, ft drive. E- en obsession Й ft compulsion.

Рисунок 8. Указатель правильного варианта ответа

Для вопросов также могут быть заданы дополнительные атрибуты: ♦ Сложность

2. Those things that upset or excite us are known as: a. stressors b. life events c. changes d. negative thoughts

ANS: a. stressors PG: 286 DIF: 1

3. Which of the Mo wing des crib eseustress? a. chronic stress b. positive stress c. nonspecific response d. negative stress

ANS: b. positive stress

PG: 286 DIF: 2

Ijjlciiiy: 4 }

Ю: 1

Author: Мшаго ftlJJJKSR

The Idee tharacflons зрвак louder than woms"dBrivBB from Aristotle who wrotB that It is our choice of good over evil that determines our characlBr. not our opinion about goad or evil

A. derives from Aristotle who wrote that it Is our choice of good Dver evil that determines our character

B. derives from Aristotle who wrote that It >6 our ctoice of good over evil determining our character

The correct artawar Is (C). The original Incorrect^ places Aristotle as the ocject of| the preposition from. Trie quote derives fromeomething Aristotle wrote, not from Aristotle himself, so w is wrong. (B) and (E) contain the same error (D) llloolcalhr follows wewwlth a preposition rather than 1Ш

Editor siiitus:

At least ones a year, not only measure the length of each foot but also the vvtath of each foot In order to be sure that shoes fit properly

Рисунок 9. Дополнительные атрибуты вопросов, сложность

Автор

1Г1: riiinl.m- Mfldfflp

Й11ЙЖ SR Content: Test: GMAT Difficulty: 4 E.litot:

Editor status:

The Idea that "actions speak louder than woris" dartvas from Aristotle v»Ho wrote opinion about good or evil.

A derives from Aristotle who wrote that it Is our etaceofgood over evil that determines our character

B. derives from Aristotle who wrote that It Is our ctoice of good over evil determining our character

C. derives from Aristotle's view that it is our choice of good over evil that determines our character

The correct answer Is (C). The original incorrectly places ArlsloflB as the object of| the preposition from. The quote derives rrom something Aristotle wrote, not from Aristotle himself, so CA) is wrono. (B) and (E) contain the same error. (D) Щдавдй follows wewwith a preposition rather than ttist

Рисунок 10. Дополнительные атрибуты вопросов, автор

Тип вопроса

ID: 1

Test: gmat Difficulty: 4 Eilltoi:

Eililoi Status:

The idea that "actions speak louder than words" derives from Aristotle who wrote that it is our choice of good over evil that determines our character, not our opinion about good or evil.

A. derives from Aristotle who wrote that It is our choice of goad over evil that detemnines our character

B. derives from Aristotle who wrote that it is our choice of good Dver evil detemnininQ our character

C. derives from Aristotle's view that it is our choice of good over evil that determines our character

The correct answer Is (C). The original incorrectly places Aristotle as the object of| the preposition from. The quote derives from something Aristotle wrote, not from Aristotle himself, so (A) is wrong. (Б) and (E) contain the same error. (□) ЩОШЯЗЙfollows w'ewwith a preposition rather than thai

Рисунок 11. Дополнительные атрибуты вопросов, тип вопроса

• Номер страницы в книге, которая изначально содержала вопрос

1. The nonspecific response of the body to any demand made upon it is the definition of: a. adaptive response b. resistance c. stress d. homeostasis stress

G: 28 ij DIF: 1

Рисунок 12. Дополнительные атрибуты вопросов, номер страницы

• Информация, которую надо сообщать пользователю при выборе варианта ответа

1. Hcrw many of the elements are known ta occur in nature (can be found outside of laboratories)?

A. 26

B. 106

C. 112

D. 68

E. 4

Analysisr—™—,

A.r26"elements are known to be necessary for life, but others are found in nature.l

B. [Your periodic table may list 106 elements, but not all of these are found in nature. I

C.fAFleast 112~elements have been di^coverecШsyntl^ёsizFl37Б"цГri□t^all oftfTese are гоипШп nature. [

D. CORRECT

E. |Aristotle would be proud.|

Statistics can be used to do all of the following except

Guarantee a correct answer.

Correct.

Estimate a parameter. bcotrectJStatistics can be used to estimate a parameter. |

Compare two populations. bcojTect.JStatistics can be used to compare two populations !

Determine whether two variables are related. j^om^t. Statistics can be used to determine whether two variables are related.

Рисунок 13. Дополнительные атрибуты вопросов, подсказки • Объяснение выбора правильного варианта ответа. ю: 1

Author: ШШПЗ

Content: Test: G MAT Difficulty: 4 Editor:

Editor Status:

The idea that "actions sneak louder than words" derives from Aristotle who wrote that it is our choice cf goad aver evil that determines our character, not our □pinion about good or evil.

A. derives from Aristotle who wrate that it is our choice of good over evil that deteimines our character

B. derives from Aristotle who wrote that it is our choice of good over evil deteimining our character

C. derives from Aristotle's view that it is our choice of good over evil that deteimines our character

The correct answer is (C). The original incorrectly places Aristotle as the object of| the preposition from. The quote derives from something Aristotle wrote, not from Aristotle himself, so (A) is wrong. (B) and (E) contain the same error. (0) iiMtaUy follows w'ewwith a preposition rather than that. J

Рисунок 14. Дополнительные атрибуты вопросов, объяснение

Все эти данные являются атрибутами вопросов, то есть информационных объектов, и их несложно определить, просмотрев документ.

Говорят, что эта структурированная информация указана в документах неявно, поскольку она не была задана явно, например, так, как это делается, при определении схемы реляционной базы данных. То есть, даннные о вопросах в документе представлены в виде единой последовательности символов, в которой отдельные логические элементы информации явным образом не выделены. В результате невозможно автоматическое выполнение операций с этими логическими элементами информации, как это возможно, например, при хранении информации в реляционной базе данных и выполнении операций на SQL [Codd 1970], или представлении информации в XML документах, и использовании для операций языка XQuery [w3c 2005 XQuery], [w3c XML]. Кроме того, данные могут изменяться от одного вопроса к другому, например, для некоторых вопросов может быть не задана сложность, потому что автор посчитал, что в этом нет необходимости, могут отсутствовать идентификаторы вопросов, обозначение правильного вопроса может также отсутствовать, как и идентификатор вопроса. Такие текстовые данные называют слабо структурированными.

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

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

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

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

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

Описание решения

Автоматическое распознавание и построение структурированной модели информации, содержащейся в слабо структурированных текстовых данных, является современной и очень важной областью исследований. Часто эту задачу в литературе называют Извлечением Информации (Information Retrieval). Формально задачу можно сформулировать следующим образом:

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

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

1. The 5' designation ос a DNA molecule is derived from a ibe fifth oxygen ш the nitrogenous bate b. the fifth eaiboti in the nitrogenous base с the fifth ojtyfie-8 in the deoxyrtbose sujgar *d ПОЬ carbon m the dtoxynbose

1. The notapttifjc response ofthe body to my demand made up«A it i* the dafuntion of a adaptive response b resistance c. stress

AHS c. stress

Which i5 not &j>ai! of cWscripUve statistics?

Statistical taferencc.

Comet

Orgiruitng data.

Incorrect Descrqitivs mtist-.cs dttls with orgammg dam Sommarizinf data.

Incerrcc: Deter?tree statistics deals with suimsanmg data

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

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

Представленный в работе подход обладает очевидными преимуществами:

• пользователь может построить именно ту модель информации, которую он предпочитает, при этом не требуется, чтобы эта модель и способ извлечения информации были известны заранее

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

• в модуле автоматического анализа текста используются методы и технологии из области обработки текстов на естественном языке (natural language processing, NLP), что позволяет перейти от задачи разбора текста к задаче классификации и применить богатый арсенал области искусственного интеллекта (artificial intelligence, AI) и обучения машин (machine learning, ML)

Анализ выполняется следующим образом. В начале программа делает предположение о том, как внутреннее представление документа связано с логической структурой информации, содержащейся в нём. На основе этого предположения выбирается известный алгоритм анализа и пользователю предоставляется результат анализа текста, выполненного с его помощью. Затем пользователь просматривает результаты анализа и, если находит ошибки, исправляет их. В обнаружении ошибок анализа пользователю помогает инструмент анализа, привлекая внимание пользователя к автоматически найденным ошибкам анализа. При исправлении ошибок пользователь размечает небольшую часть текста с помощью специальных маркеров и удобного графического интерфейса (который подходит для решения конкретной задачи), как он это делал бы при отсутствии модуля автоматического анализа текстов. Таким образом, пользователь указывает программе правильный способ анализа текста. Программа анализирует действия пользователя, корректирует алгоритм, и выполняет разбор ещё не проверенной пользователем части документа, и т.д. При обучении, то есть автоматической корректировке алгоритма анализа, используются различные методы и технологии из областей обучения машин (Machine Learning, ML), искусственного интеллекта (Artificial Intelligence, AI) и анализа текста на естественном языке (Natural Language Processing, NLP).

Рисунок 16. Алгоритм анализа

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

Примерами таких классов задач могут быть

• анализ документов, содержащих наборы вопросов

• разбор текста оглавлений книг - выделение названий разделов, глав книг, и т.п.

• анализ текста HTML страниц, содержащих информацию о продаже товаров [Alberto 2002]

• выделение списков простых объектов (требований к программному продукту, замечаний заказчика и т.п.)

Предложенное решение анализирует документы, составленные на языке разметки HTML. Полученная в результате анализа структурированная модель информации представляется в виде XML документа определённого формата [w3c XML], Формат XML документа может быть рассмотрен, как метамодель информации, выделенной с помощью предложенного решения, понятие метамодели описано, например, в [Torlone], При этом данные XML документа легко могут быть автоматически, без участия человека, преобразованы в любую другую структурированную модель информации, например, другой XML формат, или содержание реляционной базы данных. Отображение данных XML документов в реляционные базы данных и наоборот является относительно хорошо изученной задачей [Claypool], [Papotti], [Mclnik], [Torlone Chameleon], [Torlone]. Выбор указанных форматов входов и выходов программы подробно рассмотрен ниже в соответствующих разделах.

Различные форматы, ориентированные на отображение.

Бумажные книги и статьи. Электронные документы Word, PDF. HTML.

Самый распространённый формат представлении, ориентированный на отображение

HTMLI > ХМ L к Анализ

Явно описывающий логическую структуру информации

Различные форматы, ориентированные на логическую структуру информации.

Реляционные БД, XML документы и XML базы данных.

Рисунок 17. Преобразование моделей представления информации

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

Сравнение с другими подходами

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

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

К решению этой проблемы существует много подходов, позволяющих ускорить разработку алгоритмов анализа. Одним из таких подходов является создание специальных языков программирования для создания алгоритмов анализа. В некоторых исследованиях используются существующие инструменты генерирования грамматик, такие, как, например, Java СС [Java СС], которые позволяют описывать LL(k) грамматики. В других определяются собственные языки программирования, такие как, например, объектно-ориентированная модель Object Exchange Model (OEM) в проекте TSIMM1S [Papakonstantinou 1995]. С помощью таких языков довольно просто можно описать много форматов документов, однако работа с такими языками требует существенного опыта программирования, и такие опять же подходы становятся невозможными при отсутствии высококлассных программистов.

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

Позже были предложены немного более общие способы генерирования алгоритмов анализа, например, Stalker [Muslea 2001], или SoftMealy [Hsu 1998]. Подход, предложенный в Stalker, основывается на, так называемых, дизъюнкциях меток границ. Каждая метка границы специализируется на извлечении определённого типа логических единиц информации. Эти подходы к анализу включали подход, предложенный в [Kushmerick 2000] как частный случай. Оба подхода допускают структурные вариации, такие как, например, отсутствие некоторых элементов информации в полученной логической структуре информации. Однако описанные в работах алгоритмы обладают существенными ограничениями. Например, при использовании предложенного в SoftMealy подхода, необходимо при обучении предоставить примеры всевозможных структурные вариаций. Способ генерирования алгоритмов, предложенный в Stalker принципиально не способен обобщать разделители логических единиц информации в текстовых документах, и потому очень чувствителен к примерам, используемым при обучении. Кроме того, при использовании Stalker необходимо заранее задать структуру информации в документе. Оба подхода при выделении информации также используют существенно ограниченный набор информации в алгоритмах анализа, а именно текст, окружающий различные типы единиц логической информации, и не могут использовать какую-либо дополнительную информацию.

Более поздние работы, например, DEBYE [Alberto 2002], позволяют извлекать информацию, допускающую произвольные структурные вариации и позволяют указывать структуру информации в документе непосредственно во время указания примеров. Так в DEBYE для этого используется понятие вложенных таблиц, и элементы информации указываются, начиная с самого нижнего уровня. Этот способ извлекаемой информации является несомненным преимуществом в сравнении, например, с более ранней NoDoSe [Adelberg 1998], где извлекаемую информацию необходимо указывать «сверху вниз», разбивая документ последовательно на всё меньшие части, поскольку пользователь избавлен от необходимости работать с фрагментами, не содержащими интересующие пользователя данные. Для выделения логических элементов информации DEBYE также пользует лишь текст, непосредственно их окружающий.

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

Во всех описанных системах, в отличие от предлагаемого в этой работе подхода, явно выделяются два этапа:

• составление алгоритма экспертами или обучение на основе примеров правильного анализа,

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

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

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

Содержание

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

Заключение

В работе достигнуты следующие результаты:

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

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

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

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

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

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

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

• пользователь может построить именно ту модель информации, которую он предпочитает, при этом не требуется, чтобы эта модель и способ извлечения информации были известны заранее

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

• в модуле автоматического анализа текста используются методы и технологии из области обработки текстов на естественном языке (natural language processing, NLP), что позволяет перейти от задачи разбора текста к задаче классификации и применить богатый арсенал области искусственного интеллекта (artificial intelligence, AI) и обучения машин (machine learning, ML)

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

• с точки зрения пользователей этапы указания примеров и составления алгоритма анализа объединены; в описанных в литературе системах анализа пользователь должен сначала закодировать способ выполнения анализа, затем применить полученный алгоритм, если алгоритм не подходит, и указанных примеров недостаточно, то пользователи должны вернуться к указанию примеров, и начать всё с начала; в предложенном решении обучение и выполнение анализа интегрированы, и пользователь не выполняет никаких дополнительных действий

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

• в связи с этим выполнение анализа документов интегрировано с автоматическим определением ошибок предложенного способа анализа, что позволяет автоматически обнаружить и устранить ошибки;

• анализ разбит на простейшие этапы, что позволило выделить графематический этапа анализа, и проанализировать его выполнение; предложен способ автоматического сравнения адекватности способов его реализации решаемой прикладной задаче;

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

Предложенный способ анализа слабо структурированных текстов существенно сокращает сроки анализа авторских документов, содержащих неструктурированное представление информации, которая используется системами дистанционного образования. Разработанный с его помощью инструмент анализа текстов с вопросами способен в кратчайшее время построить структурированную модель содержащейся в авторских документах информации, и проанализировать тексты с тысячами вопросов. Он использовался при создании программных комплексов «Физика 7-11 классы» и «Биология, химия, экология». В настоящее время системы дистанционного образования, разработанные компанией ФИЗИКОН, широко используются в процессе обучения, тестирования и самопроверки.

1. Уразлин Ю.К. Анализ слабо структурированных текстовых данных. // Моделирование и обработка информации: сб.ст. /Моск.физ.-тех. ин-т. М., 2003.-С. 108-118.

2. Уразлин Ю.К. Выделение групп лексем при анализе слабо структурированных текстовых данных. // Моделирование процессов управления: сб.ст./Моск.физ.-тех. ин-т. М., 2004. - С. 95-105.

3. Уразлин Ю.К. Анализ слабо структурированных текстовых данных в системах дистанционного образования. // Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т. М., 2005. - С. 150-157.

4. Мамонтов 2002. Мамонтов Д.И. (2002). Технология создания сетевых интерактивных ресурсов в образовании и научных исследованиях, диссертация на соискание ученой степени кандидата технических наук, МФТИ.

5. Codd 1970. Codd, Е. F. 1970. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM 13, no. 6 (June): 377-387. http://doi.acm.org/10.1145/362384.362685.

6. Alberto 2002. Data Extraction By Example, Alberto H.F. Laender, Berthier Riveiro-Neto, Altigran S. Da Silva, Data & Knowledge Engeneering 40 (2002), 121-154.

7. Kushmerick 2000. N. Kushmerick, Wrapper induction: efficiency and expressiveness, Artif. Intell. 118 (l-2)(2000) 15-68

8. Hsu 1998. C.-N. Hsu, M.-T. Dung, Generating finite-state transducer for semi-structured data extraction from the Web, Inf. Syst. 23 (8) (1998) 521-538.

9. Muslea 2001. I.Muslea, S.Milton, C.Knoblock, An hierarchical approach to wrapper induction for semi-structured information sources, Autonomous Agents Mulit-Agent Syst. 4 (1/2) (2001) 93-114.

10. Marcus 1993. M. Marcus, S. Santorini, and M. Marcinkiewicz. Building a Large Annotated Corpus of English: the Penn Treebank. Computational Linguistics, 19(2):313-330, 1993. URL http://citeseer.ni.nec.com/marcus93building.html.

11. Grefenstette 1994. Gregory Grefenstette et Pasi Tapanainen. What is a Word, What is a Sentence? Problems of Tokenization. Complex-94, pp. 79-87, Budapest, Hongrie, juillet 1994.

12. Сокирко 2003. Сокирко A.B. DDC программа поиска по морфологически и синтаксически размеченному массиву. // Труды Международного семинара Диалог'2003 по компьютерной лингвистике и ее приложениям.

13. Abney 1991. S. Abney. Parsing by Chunks. R. Berwick, S. Abney and C. Tenny (eds.) Principle-based Parsing. Kluwer Academic Publishers, Dordrecht, 1991.

14. Sang 2000. Erik F. Tjong Kim Sang. Text Chunking by System Combination. In Proceedings ofCoNLL-2000 and LLL-2000, Lisbon, Portugal, September 2000.

15. Ratnaparkhi 1998. A. Ratnaparkhi. Maximum Entropy Models for Natural Language Ambiguity Resolution. Phd. Thesis, University of Pennsylvania, 1998. http://www.cis.upenn.edu/.adwait.

16. CoNLL 2000. http://lcg-www.uia.ac.be/conll2000/chunking/. http://lcg-www.uia.ac.be/conll2001/clauses/.

17. Johansson 2000. Christer Johansson. A Context Sensitive Maximum Likelihood Approach to Chunking. In Proceedings of CoNLL-2000 and LLL-2000, Lisbon, Portugal, September 2000.

18. Veenstra 2000. Jorn Veenstra and Antal Van den Bosch. Single-Classi.er Memory-Based Phrase Chunking. In Proceedings of CoNLL-2000 and LLL-2000, Lisbon, Portugal, September 2000.

19. Daelemans 1997. W. Daelemans, Antal Van den Bosch, and T. Weijters. IGTree:

20. Using Trees for Compression and Classi.cation in Lazy Learning Algorithms. D. Ahaed.), Arti.cial Intelligence Review 11, Special issue on Lazy Learning. Kluwer Academic Publishers, 1997.

21. Molina 2002. A. Molina and F. Pla. Shallow parsing using specialized hmm. Journal of Machine Learning Research, 2002.

22. Ratnaparkhi 1998. Adwait Ratnaparkhi. (1998). Maximum Entropy Models for Natural Language Ambiguity Resolution. Ph.D. Dissertation. University of Pennsylvania.

23. Van Halteren 2000. Hans Van Halteren. Chunking with WPDV Models. In Proceedings ofCoNLL-2000 andLLL-2000, Lisbon, Portugal, September 2000.

24. Shannon 1951. С. E. Shannon. Prediction and Entropy of Printed English. Bell System Technical Journal, pages 50-64, 1951.

25. Lyon 1997. С. Lyon and S. Brown. Evaluating Parsing Schemes with Entropy Indicators. In MOL5, 5th Meeting on the Mathematics of Language, 1997

26. Adelberg 1998. B. Adelberg, NoDoSe A tool for semi-automatically extracting structured and semi structured data from text documents, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, Seatle, WA, 1998, pp. 283-294.

27. Freitag 2000. D. Freitag, Machine learning for information extraction in informal domains, Mach. Learning 39 (2-3)(2000) 169-202.

28. Dejean 2002. Herve Dejean, Learning Rules and Their Exceptions. In Journal of Machine Learning Research, volume 2 (March), 2002, pp. 669-693.

29. Baldridge 2005. Jason Baldridge, Tom Morton, and Gann Bierner. The opennlp.maxent package, mature Java package for training and using maximum entropy models (http://maxent.sourceforge.net').

30. Java CC. Java Compiler Compiler [tm] (JavaCC [tm]) The Java Parser Generator (https://iavacc.dev.iava.net/).36. Perl 2005. www.perl.org.

31. Miscrosoft Word. www.microsoft.com/ofnce/word

32. Open Office. http://www.openoffIce.org/

33. Fine Reader. http://www.abbyy.com/finereaderocr/40. w3c 2005 XQuery. http://www.w3 .org/XML/Query.

34. Ronald Bourret. http://www^bourret.com/xml/XMLDatabaseProds.htm42. w3c 2002 Web-services. http://www.w3.org/2002/ws/.43. w3c HTML. http://www.w3 .org/MarkUp/.44. w3c XML. http://www.vv3.org/XML/,

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

36. Data rich texts наполненные данными тексты2. Wrapper упаковщик

37. Narrow in ontological breadth texts близкие в онтологическом смысле тексты

38. Natural Language Processing анализ текстов на естественном языке

39. Machine Learning обучение машин6. Chunk группа7. Clause — выражение

40. Hidden Markov Model скрытая марковская модель