Содержание к диссертации
Введение
Глава 1. Постановка задачи 28
Вход 28
Вопросы , 33
Оглавления , 35
Требования к программному обеспечению 36
Информация о продаже товаров 38
Преобразование 38
Полуавтоматический анализ 39
Процедура анализа текста 40
Выход 42
Модели представления структурированной информации 43
Формат выхода 45
Глава 2. Общий способ анализа , 48
Связь с анализом текстов на естественном языке 48
Анализ текстов на естественном языке 51
Графематичес кий анализ 53
Синтаксический анализ 56
Применимые к рассматриваемой задаче методы 65
Предлагаемое решение бб
Выделение этапов анализа , 66
Графсматический этап анализа 67
Синтаксический анализ 77
Автоматическое выявление ошибок 90
Глава 3. Анализ текстов с вопросами 92
Графематический анализ , 94
Синтаксический анализ , 98
Выделение объектов первого уровня - вопросов 99
Определение частей вопросов 107
Автоматическое определение ошибок 115
Глава 4. Инструмент анализа 119
Выделение вопросов. 120
Определение атрибутов вопросов 122
Автоматическое определение ошибок анализа 123
Сохранение результатов анализа ,„ 126
Глава 5. Экспериментальные результаты 127
Заключение... ...136
Список использованных источников...
- Требования к программному обеспечению
- Анализ текстов на естественном языке
- Синтаксический анализ
- Автоматическое определение ошибок анализа
Введение к работе
С развитием мощности современной вычислительной техники возникает возможность обрабатывать грандиозные объёмы данных. Распространение современных цифровых библиотек и популяризация сети Интернет сделала огромные объёмы информации доступными широкой аудитории в виде компьютерных текстов. Тысячи новых документов появляются каждый день, постоянно создаются новости, журналы, научные статьи и размещаются на серверах сети Интернет. Электронная почта стала одним из самых распространённых способов общения. Фактически, лишь объём данных в текстовом формате сети Интернет оценивается терабайтами.
В то же время грандиозные хранилища текстовых данных в большинстве случаев не используются, а получение требуемой информации из этих источников информации является достаточно сложной задачей. Известно, что пользователи больших репозитариев текстовых данных считают сложной, а иногда невыполнимой задачу обнаружения интересующей информации.
Причина этого заключается в том, что пользователи заинтересованы в структурированной информации, которая содержится в тексте. Такую информацию невозможно идентифицировать традиционными интерфейсами поиска неинтеллектуальных инструментов: текстовых процессоров, почтовых ящиков, поисковых серверов, файловых систем, и т.п. Проблема состоит в несоответствии модели представления текстовых данных в репозитариях и операций, которые необходимо выполнять пользователям с содержащейся в них структурированной информацией.
Требования к программному обеспечению
Для каждой книги в указанном примере представлена информация об авторах, названиях, датах публикации и ценах. Только используя структурированную модель представления информации о книгах можно легко выполнять такие важные операции, как поиск книг, которые могут заинтересовать потенциального покупателя, то есть книг, удовлетворяющих некоторым ограничениям. Например, покупателей могут интересовать книги, которые принадлежат перу определённого автора, или книги, стоимость которых лежит в определённом диапазоне, или книги, выпущенные в течение какого-то периода времени. Преобразование
Преобразование заключается в составлении алгоритма анализа, то есть способа построения структурированной модели информации, содержащейся во входных данных, и применении построенного алгоритма.
Одним из главных преимуществ представленного в работе подхода является то, что выход анализа, то есть структурированная модель информации, определяется именно во время преобразования, и не должна быть фиксирована заранее. ориентированные на отображение.
Бумажные книги и статьи. Электронные документы Word, PDF, HTML.
Поскольку, как показано в примерах, объём текстовых данных, которые необходимо проанализировать, очень большой, анализ должен выполняться, насколько это возможно, автоматически.
С другой стороны, так как форматы представления текстов произвольны, и все их нельзя предусмотреть заранее, алгоритм анализа, подходящий для уникального, используемого в анализируемом тексте формата, должен составляться непосредственно во время выполнения анализа текста. При этом определить подходит или нет алгоритм для анализа текста, то есть указать правильно, или нет, проанализирован с его помощью текст, может только пользователь. Следовательно, анализ может быть выполнен только полуавтоматически: часть анализа может быть выполнена программой, а оставшуюся часть, в любом случае, необходимо выполнять пользователю.
Предложенное в работе решение минимизирует участие человека в анализе, и преобразование, насколько возможно, выполняется автоматически. Для этого используется специальный модуль обучения, который анализирует все действия пользователя, и копирует их. Модуль обучения устроен таким образом, что задача анализа текста сведена к задаче классификации, что позволяет применять для анализа текста весь арсенал этой области; методы обучения, основанные на статистических алгоритмах, правилах, прецедентах, и т.п.
Процедура анализа текста
Условно, процедуру анализа текста можно представить следующим образом. 1. Сделать некоторое предположение о том, как внутреннее представление текста соотносится с логической структурой информации, которую содержит текст. На основе этого предположения выбрать известный алгоритм анализа текста 2. Пользуясь алгоритмом, выполнить анализ текста, 3. Выявить ошибки анализа a. Если есть ошибки, то перейти к шагу 4, b. Если нет ошибок, то перейти к шагу 6. 4. Определить, как надо правильно анализировать небольшую часть текста, содержащую ошибки 5. Скорректировать алгоритм анализа и перейти к шагу 2. 6. Анализ текста завершен.
Схема процедуры выполнения анализа представлена на следующем рисунке. шаг обучения, или автоматического изучения действий пользователя, составления и корректировки алгоритма анализа. На этом шаге используются различные методы и технологии из областей обучения машин (Machine L earning, ML), искусственного интеллекта (Artificial Intelli gence, AI) и анализа текста на естественном языке (Natural Language Processing, NLP).
Участие пользователя в выполнении анализа необходимо, по крайней мере, на шагах 3 и 4, потому что только пользователь может понять бесконечное множество форматов текстов, определить, правильно ли извлечена информация из текста, и указать способ устранения ошибок анализа. Тем не менее, этап выявления ошибок в предложенном в работе решении может быть частично автоматизирован. То есть, программа может автоматически определять, правильно ли выполнен анализ текста, и указывать ошибки анализа, способ исправления которых все же должен задать пользователь. При определении ошибок возможно выполнение проверки того, удовлетворяют ли результаты выполнения анализа как ограничениям, заданным предметной областью, так и ограничениям, присущим лишь информации, содержащейся в текущем документе. В предложенном решении реализован способ обнаружения ограничений, заданных в виде регулярных грамматик. Этим ограничениям должны удовлетворять последовательности типов логических един и и информации, построенной структурированной модели.
Выход
Выходом анализа текстовых данных является структурированная модель информации: информация представлена в виде набора отдельных элементов (объектов), задан тип каждого элемента информации, и связи между элементами указаны явно.
Модель информации, которая является выходом анализа, должна несложно преобразовываться в модель, используемую хранилищем данных приложения, которое будет использовать извлечённую информацию. Чтобы обосновать сделанный в работе выбор, рассмотрим способы представления информации в современных хранилищах структурированной информации.
Анализ текстов на естественном языке
Таким образом, несмотря на то, что формализовать выполнение синтаксического анализа сложно, можно чётко определить его вход и выход. Это позволяет создавать проанализированные общедоступные наборы текстов, с помощью которых можно сравнивать эффективность работы различных подходов к выполнению этапа синтаксического анализа в задачах анализа текстов на естественном языке [CoNLL 2000].
Неудивительно, что самыми объёмными и самыми известными являются наборы проанализированных текстов на английском языке, и наиболее развито исследование выполнения синтаксического анализа текстов именно на английском языке. Поэтому выше приведены примеры синтаксического разбора текстов на естественном английском языке.
Для формирования алгоритма выполнения синтаксического анализа используются различные подходы. От построения нейронной сети, правила, функционирования которой фиксируются на этапе обучения, и смысл работы которой описать в терминах предметной области практически невозможно, до составления базы знаний экспертами - лингвистами и жёсткого фиксирования правил выполнения анализа. В первом предельном случае требуется большой объём правильно проанализированных текстов для обучения нейронных сетей. Во втором необходимы лингвисты -эксперты, способные составить набор верных правил «на все случаи жизни». Таким образом, по принципу формирования правил реализации этапа синтаксического анализа текста можно условно разделить на те, в которых правила выполнения анализа определяются экспертами предметной области, то есть лингвистами, и те, в которых правила анализа не задаются явно, а формируются автоматически из правильно проанализированного вручную текста.
В последнее время всё большую популярность приобретают системы, использующие второй подход к составлению правил выполнения синтаксического анализа, то есть автоматическое формирование набора правил. Это связано с тем, что относительно недавно, в 1995 году, задача выполнения синтаксического анализа, а именно объединения лексем в группы, была смоделирована в виде задачи классификации объектов на основе набора признаков. Это позволило применить к её решению богатый арсенал областей искусственного интеллекта (artificial intelligence) и обучения машин (machine learning). В настоящее время для решения задачи синтаксического анализа успешно применяются статистические, основанные на правилах, прецедентах, и комбинированные методы обучения и выполнения классификации объектов. Все эти способы были разработаны и хорошо изучены при решении прикладных задач из других областей, в которых находит своё применение искусственный интеллект.
Именно этот подход к выполнению синтаксического анализа используется в предлагаемом в этой работе решении. Это связано в первую очередь опять же, с произвольностью анализируемых текстовых данных и принципильной невозможностью составления предопределённых правил выполнения анализа. Поэтому остановимся подробно на переходе от задачи разбора текста к задаче классификации объектов, а также рассмотрим различные способы выполнения синтаксического анализа, алгоритм работы которых составляется автоматически с помощью образцов выполнения анализа.
Переход к задаче классификации выполняется с помощью перехода от задачи объединения объектов в группы к задаче определения синтаксических типов, которые присваиваются лексемам. В [Sang 2000] показано, что существует несколько эквивалентных наборов синтаксических типов, которые можно использовать для синтаксического анализа текста.
В работе используется набор типов, представленный в [Ratnaparkhi 1998]. В этом наборе используются два типа для каждого вида групп лексем, и один выделенный тип, обозначающий лексемы вне групп: В-Х для первой лексемы в группе вида X; 1-Х для не первой лексемы группы вида X; О для лексем вне групп. Выделение отдельного синтаксического типа В-Х, помимо 1-Х, необходимо для разделения лексем из двух следующих друг за другом групп лексем одного вида.
С помощью этого набора синтаксических типов, выделенные в предложении группы лексем могут быть представлены следующим образом:
Синтаксический анализ
Результаты экспериментов показывают, что использование информации о разметке не только не увеличивает, но даже уменьшает значение энтропии, потому их обязательно надо включить в набор типов лексем. Если бы информация о разметке не облегчала дальнейший анализ текста, то добавление соответствующих типов лексем должно было бы увеличить значение энтропии.
Поскольку набор 5 дает лучшие результаты и содержит наибольшее количество информации о тексте, то есть в нём больше всего типов лексем, именно этот набор типов лексем, именно он послужил основой набора графематических типов, используемого в разработанном инструменте анализа документов с вопросами,
Кроме этих типов в результате анализа многих документов с вопросами были выделены ещё 5 дополнительных типов, которые, часто участвуют в выделении логических элементов информации и, безусловно, облегчают выполнение последующих этапов анализа.
Таким образом, выделенные из текста с помощью набора типов 5 дополненного типами из таблицы выше, лексемы являются входом синтаксического этапа анализа. Синтаксический анализ
Синтаксический анализ документов с вопросами состоит из двух этапов, поскольку максимальная глубина вложенности структуры извлекаемой информации равна двум. При анализе документов с вопросами будут выделяться сложные объекты — вопросы и простые объекты второго уровня вложенности - их атрибуты: идентификатор вопроса, текст задания, вариант правильного ответа, и т.п.
Эта структура выделяемой информации является более простой, чем представленная в разделе «Постановка задачи» иллюстрации, и обладает лишь двумя уровнями вложенности логических элементов информации, в то время как на рисунке представлена более сложная структура. Дело в том, что в инструменте анализа необходимо фиксировать лишь ту модель информации, которая способна описать все документы выбранного класса задач и не содержит дополнительных ограничений, не выполняющихся для некоторых документов из выбранной предметной области. Так, модель информации, в которой документ состоит из вопросов, и у вопросов есть атрибуты, справедлива для всех документов выбранной предметной области. Более сложная структура может быть без каких-либо сложностей автоматически построена из выделенной с помощью инструмента модели информации. Рассмотрим выполнение указанных двух частей синтаксического анализа. Выделение объектов первого уровня - вопросов
Выделение вопросов в тексте заключается в определении информационных объектов — вопросов. Вопросы одного из документов, используемых в экспериментах, представлены на следующем рисунке. Переход к группам строк (дополнительное ограничение)
Оказалось, что подзадачу выделения вопросов эффективно решать в предположении, что каждый вопрос занимает целое количество строк. То есть каждая строка либо целиком является частью вопроса, либо не является частью вопроса. То есть не может быть, например, такой ситуации: часть строки содержит один вопрос, а вторая часть той же строки - другой.
Это условие выполняется для всех текстов с вопросами, с которыми приходилось иметь дело, и позволяет существенно упростить задачу выделения вопросов из текста. С учётом этого ограничения можно перейти от задачи выделения групп лексем, которые образуют вопрос, к задаче выделения соответствующих им групп строк.
Во-первых, это ограничение существенно уменьшает множество возможных вариантов разбиения текста на вопросы, во-вторых, опыт написания анализаторов «с фиксированным алгоритмом анализа» показывает, что именно свойства строк, а не отдельных лексем, определяют границы вопросов.
Таким образом, выделение вопросов в тексте сводится к задаче классификации строк и отнесению не лексем, а строк к одному из трёх типов: Первая строка вопроса Строка внутри вопроса Строка вне вопросов Используемые при классификации свойства
Свойства, на основе которых надо определять тип строки необходимо составить из представления текста - упорядоченного, и сгруппированного в строки набора лексем, которые составляют текст документа с вопросами.
Как показывает опыт написания анализаторов с «фиксированным» алгоритмом анализа, важными свойствами при определении того, принадлежит строка вопросу, или нет, являются Графематический тип и текст нескольких первых и последних лексем рассматриваемой строки, Графематический тип и текст нескольких первых и последних лексем строк, которые расположены сразу перед рассматриваемой строкой, и после неё.
Итак, набор свойств, которые можно использовать, задан, множество возможных типов классифицируемых объектов также фиксировано, осталось лишь определить адекватный решаемой задаче способ построения алгоритма классификации.
Автоматическое определение ошибок анализа
На всплывающей панели инструментов расположены кнопки, соответствующие различным типам атрибутов вопроса, и, кроме них, кнопка, обозначающая текст вне атрибутов, с помощью которой можно указать, что текст не входит ни в одну логическую единицу информации. Для каждого типа атрибута присутствует лишь одна кнопка, поскольку, как было отмечено выше, первые лексемы групп определённого типа ие выделяются в отдельный синтаксический тип из-за возможности дополнительного ограничения: атрибуты одинакового типа не следуют друг за другом. Предусмотрена возможность расширения множества типов атрибутов вопросов, выделяемых при анализе. Поскольку, как уже не раз было отмечено, необходимо обеспечить возможность определять модель выделяемой информации непосредственно во время выполнения анализа.
Далее необходимо нажать на кнопку, соответствующую типу атрибута, который соответствует выделенному тексту. В результате всем лексемам, текст которых был выделен, будет присвоен выбранный синтаксический тип.
Аналогично выделению строк каждый новый пример классификации лексем как атрибутов вопросов приводит к уточнению алгоритма классификации и применению его к ещё не проверенной пользователем части текста. На этом этапе также считается, что весь текст до явно указанной ошибки проверен, следовательно, проанализирован правильно.
Как видно, предложенный способ анализа текста не требует от пользователей каких-либо дополнительных действий: пользователь всего лишь размечает текст, как это он делал бы без помощи модуля обучения, а программа анализирует его действия и пытается их повторить. Это приводит к тому, что в больших документах, содержащих сотни вопросов пользователю необходимо лишь правильно разобрать с помощью удобного интерфейса два-три из них, указав правильный способ анализа. Остальные будут проанализированы программой. Кроме того, программа может автоматически указать возможные ошибки в предложенном совместно пользователем и программой варианте анализа.
Автоматическое определение ошибок анализа
Поскольку окончательным результатом работы инструмента должна быть полностью, то есть на 100%, правильно выделенная информация (а не текст, проанализированный, например, в 85% случаев правильно, что бывает при использовании описанных в литературе подходов к анализу слабо структурированных данных), важной и не простой задачей является поиск и устранение ошибок в предложенном варианте анализа.
В инструменте анализа реализована проверка правильности выделения информации с помощью регулярных грамматик. Пользователь может задать регулярную грамматику, которой должны удовлетворять последовательности типов атрибутов выделенных вопросов. Программа автоматически проверяет соответствие атрибутов выделенных вопросов заданной грамматике, и в случае, когда атрибуты не удовлетворяют грамматике, программа отмечает вопрос, привлекая к нему внимание пользователя.
На рисунке выше показано, что неправильно проанализированные вопросы выделяются с помощью красных прямоугольников в панели слева. В строках, соответствующих правильно проанализированным вопросам в панели слева отображаются зелёные прямоугольники.
Кроме того, на панели справа отображаются метки неправильно проанализированных вопросов. Положение меток по вертикали соответствует расположению неправильно проанализированных вопросов в масштабе текста всего документа. Нажав на метку, пользователь может перейти к тексту неправильно проанализированного вопроса.
Конечно, пользователю совершенно не обязательно полностью составлять регулярную грамматику и инструмент анализа оказывает ему помощь в этом. Чтобы составить грамматику, которая определит правильно проанализированные вопросы, необходимо выделить текст в вопросе и нажать соответствующий пункт главного меню. Программа предложит вариант регулярной грамматики, основанной на выбранном вопросе. Пользователь может внести исправления в предложенную грамматику. Окно редактирования грамматики представлено на следующем рисунке.
