Содержание к диссертации
Введение
Глава 1. Аналитический обзор современных методов автоматического анализа потоков текстовых сообщений. Постановка задачи 15
1.1 Современные методы информационного поиска 15
1.1.1 Метод информационного поиска на основе булевой алгебры 16
1.1.2 Оценка веса терминов в документе 16
1.1.3 Оценка схожести документов 19
1.2 Современные методы анализа потоков новостных сообщений 21
1.2.1 Современные средства представления и доставки потоков новостных сообщений в сети Интернет 22
1.2.2 Методы кластеризации потоков новостных сообщений 23
1.3 Лингвистические методы анализа текста 29
1.3.1 Методы синтаксического анализа основе экспертных знаний 36
1.3.2 Представление информации о языке на основе размеченных корпусов текстов 38
1.4 Методы синтаксического анализа на основе машинного обучения 39
1.4.1 Синтаксический анализ предложения с использованием алгоритма
максимальных остовных деревьев 40
1.4.2 Метод синтаксического анализа предложения на основе системы переходов 42
1.5 Постановка задачи диссертационного исследования 46
Глава 2. Разработка гибридного алгоритма синтаксического анализа 49
2.1 Алгоритм снятия морфологической омонимии для русского языка 50
2.2 Модификация алгоритма Ковингтона для задачи анализа потоков новостных сообщений 56
2.3 Дополнение модифицированного алгоритма Ковингтона априорной информацией, извлеченной из системы ЭТАП-3 60
2.4 Уточненная математическая модель признаков для синтаксического анализа русского языка 64
2.5 Краткие выводы 67
Глава 3. Разработка функциональной структуры комплекса и алгоритмов анализа потоков новостных сообщений 69
3.1 Математическая модель многоуровнего представления документа 69
3.2 Алгоритм кластеризации потоков новостных сообщений на модели признаков на основе обобщенной векторной модели документа 73
3.3 Базовые уровни представления новостного сообщения 77
3.4 Дополнительные уровни представления новостного сообщения на основе лингвистического анализа 79
3.5 Функциональная структура комплекса обработки новостных сообщений 83
3.5.1 Модуль первичного сбора и предварительной обработки новостей 85
3.5.2. Модуль индексирования 85
3.5.3 Модуль синтаксического анализа 87
3.5.4 Модуль кластеризации новостных сообщений 88
3.6 Краткие выводы 88
Глава 4. Экспериментальное исследование качества кластеризации потоков новостных сообщений и основных параметров синтаксического анализа 90
4.1 Задачи экспериментального исследования 90
4.2 Оценка качества снятия морфологической омонимии 90
4.3 Метрики оценки качества синтаксического анализа 93
4.4 Построение экспериментального корпуса новостных сообщений 96
4.5 Метрики оценки качества кластеризации новостных сообщений 97
4.6 Оценка качества кластеризации новостных сообщений 98
4.7 Оценка влияния различных уровней представления на точность и полноту кластеризации новостных сообщений 100
4.8 Экспериментальное определение зависимости точности и полноты кластеризации потоков новостных сообщений от точности синтаксического анализа 101
4.9 Вклад синтаксических групп в качество кластеризации новостных сообщений 103
4.10 Оценка влияния метрики расстояния именованных сущностей на качество кластеризации 104
4.11 Оценка влияния алгоритма кластеризации на качество кластеризации 105
4.12 Краткие выводы 106
Заключение 108
Библиография 113
- Метод информационного поиска на основе булевой алгебры
- Модификация алгоритма Ковингтона для задачи анализа потоков новостных сообщений
- Дополнительные уровни представления новостного сообщения на основе лингвистического анализа
- Метрики оценки качества синтаксического анализа
Введение к работе
Актуальность темы диссертации.
Быстрый рост числа доступных электронных лент новостей,
наблюдающийсяв последние годы, повлк за собой определнные трудности в чтении, восприятии и анализе обильно поступающей новостной информации. Существенные изменения произошли и в структуре самих новостных сообщений. Современная новость состоит не только из даты, заголовка и текста, но кроме этого, обладает необходимой вспомогательной информацией, полезной при анализе новостного потока и принятии оперативных решений на его основе. В сообщениях обычно присутствуют ссылки на рубрики, к которым относятся информационные объекты, во многих случаях также присутствует большой объм дополнительных ссылок на новостные сообщения сходной тематики, добавленные редактором.
Задача отслеживания развития сюжетов событий во многом схожа с задачей кластеризации текстов. Как и в задаче кластеризации текстов, в современных комплексах и системах кластеризации новостных потоков предполагается, что слова текста независимы друг от друга, а «значимость» каждого слова определяется на основе некоторой семантической метрики «веса» слова. При выполнении этой процедуры используются не сами, слова, а их основы, полученные в результате процедуры стемминга (англ., stemming, выделение основы слова).Из этих основ образуется «мешок слов» (англ., bagofwords) над которым выполняются процедуры преобразования и кластеризации. При таком «поверхностном» (shallow, англ.) представлении текстовых данных «поверхностная» кластеризация на основе «мешка слов» не учитывает ни структуру текста, ни присутствующие в тексте именованные сущности (имена персон, названия организаций, географические названия), ни связи между этими сущностями в тексте. Вместе с тем, несомненным достоинством «поверхностных» методов обработки текстов является высокая скорость обработки текстовых сообщений.
За последние годы получают развитие автоматические системы обработки
текстов, основанные на методах и алгоритмах компьютерной лингвистики,
которые выполняют глубокий лингвистический анализ текстов на естественном
языке. Классический лингвистический подход к анализу текста предполагает
существование относительно независимых уровней анализа, в том числе,
морфологического, синтаксического и семантического. Кроме того, он
предполагает определенную процедуру и последовательность анализа, в начале
- морфологического, затем синтаксического и, наконец, семантического.
Лингвистические методы анализа текстов основываются на правилах,
разработанных экспертами-лингвистами. Для создания автоматических систем
на основе этих правил требуется разработка модели естественного языка, что в
каждом отдельном случае требует больших трудозатрат
высококвалифицированных лингвистов и системных операторов.
Альтернативным методом построения компьютерных лингвистических анализаторов является метод на основе размеченных лингвистических «корпусов текстов». При использовании этого метода производится
обогащение массивов текстов на естественном языке соответствующей
лингвистической информацией, например, морфологической и синтаксической,
разметкой именованных сущностей. Разработка таких лингвистических
ресурсов менее трудоемка, чем разработка модели языка. При использовании
«корпусного метода» автоматические лингвистические анализаторы
конструируются с использованием, в том числе, методов машинного обучения.
В результате применения машинного обучения происходит обобщение частных
примеров, представленных в лингвистическом корпусе текстов, при этом
конструируются общие, качественные и во многих случаях эффективные
процедуры обработки и анализа текстов. В частности, этот метод успешно
применяется для создания синтаксических анализаторов. Проблемой на этом
пути является отсутствие априорной информации о возможных синтаксических
связях предложения, которая может быть получена с помощью
лингвистических правил. Одна из наиболее совершенных среди современных систем синтаксического анализа — лингвистический процессор ЭТАП-3 (Апресян и др., 2001) обладает фильтровым подходом к синтаксическому анализу. Вначале, на основе лингвистических правил конструируются все возможные потенциальные синтаксические связи предложения, затем выполняется процедура фильтрации до тех пор, пока не будет построена корректная с точки зрения совместимости синтаксических связей структура. Основной проблемой при использовании системы ЭТАП-3 является ресурсомкая процедура «перебора альтернатив», которая во времениобладает экспоненциальной сложностью.
Ряд авторитетных ученых и исследователей, таких как Ю.Д. Апресян, И.М. Богуславский, Л.Л. Иомдин, Д.В. Ландэ, И.А. Мельчук, Н.И. Ножов, Г.С. Осипов, И.Е. Поляков, И.В. Сегалович, И.В. Соловьев, В.Я. Цветков, Л.Л. Цинман, J. Allan, R. Barzilay, J. Beringer, D. Cutting, S. Kubler, J. Nivre, G.Salton, своими работами внесли значительный вклад в развитие теории информационных систем, методов информационного поиска, методов классификации и кластеризации полнотекстовых документов, методов синтаксического анализа и извлечения знаний из текстов. Активно ведут работы в этих направлениях такие организации, как Институт системного анализа РАН, Институт Проблем Передачи Информации РАН, Центр Анализа Интернет Ресурсов, Яндекс, Microsoft, Google, Объединенный Институт Ядерных Исследований, Центр Высокопроизводительных Вычислительных Кластерных Технологий, Научно-Исследовательский Вычислительный Центр МГУ.
В диссертационной работе, на основе подробного обозрения и
критического анализа существующих перспективных подходов и методов
построения автоматических анализаторов текстов гипотезируется, что создание
«гибридных» методов обработки и анализа потоков новостных сообщений,
объединяющих подходы, параметры и характеристики как «поверхностных»,
так и глубоких методов лингвистического анализа, может обеспечить
эффективное сочетание высокого качества анализа, свойственного
лингвистическим методам с высокой скоростью обработки текстов «поверхностными» методами.
Целью диссертационной работыявляется разработка моделей и алгоритмов оперативной обработки потоков новостных сообщений, способных объединить в себе достоинства поверхностного представления текстовых данных с правилами и процедурами уточненного лингвистического анализа.
Для достижения указанной цели в диссертационной работе поставлены и решены следующие задачи:
-
Разработка гибридного алгоритма синтаксического анализа, который сочетает преимущества метода экспертных знаний существующей системы ЭТАП-3 и методов синтаксического анализа, основанных на машинном обучении.
-
Разработка алгоритма снятия морфологической омонимии, необходимого для эффективной реализации гибридного алгоритма синтаксического анализа
-
Разработка математической модели признаков для синтаксического анализа, учитывающая особенности русского языка и русскоязычных текстов.
-
Разработка математической модели многоуровнего представления новостного сообщения для задачи кластеризации.
-
Разработка алгоритма и программного обеспечения кластеризации потока новостных сообщений, который бы эффективно обрабатывал многоуровневое представление новостного сообщения.
-
Определение функциональной структуры комплекса обработки новостных сообщений и проведение экспериментальных исследований, верифицирующих научные положения диссертации.
-
Внедрение выводов и рекомендаций диссертации в практические разработки и учебный процесс МГТУ МИРЭА.
Объектом исследованиядиссертации является комплекс обработки и анализа потоков новостных сообщений на естественном языке.
Предмет исследования определен областью исследований №
3(разработка научных методов и алгоритмов организации специальной обработки данных, хранения и ввода-вывода информации) паспорта специальности 05.13.15, а также перечнем задач, решаемых в диссертации.
Методы исследования базируются на положениях современной теории систем и системного анализа, теории множеств, теории массового обслуживания, а также на методах компьютерной лингвистики.
Научная новизнаполученных результатов состоит в том, что:1) разработан гибридный алгоритм синтаксического анализа, сочетающий в себе возможности и характеристики лингвистического процессора ЭТАП-3, так и алгоритма Ковингтона. Разработанный гибридный алгоритм позволяет значительно ускорить (в среднем на 50%) процесс синтаксического анализа при незначительной для задачи кластеризации новостных сообщений потери в его точности.
2) Впервые предложена математическая модель кластеризации потоков
новостных, сообщений, использующая не только «поверхностное»
представление текста, но и его лингвистическую структуру.
3) Разработана математическая модель признаков синтаксического
анализа, учитывающая особенности русского языка и русскоязычных текстов,
что позволяет увеличить точность синтаксического анализа на естественном
языке.
4) Разработана математическая модель многоуровнего представления
новостного сообщения, дополняющая классическую векторную модель и
позволяющая учитыватьразличные виды информации, присутствующиев
документе.
5) Разработан алгоритм кластеризации потоков новостных сообщений на
основе математической модели многоуровнего представления документов.
Предложенный алгоритм оценивает близость двух новостных сообщений на
основе линейной комбинации расстояний различных уровней представления
документа, что позволяет значительно расширить представление новостного
сообщения.
6) Разработана математическая модель представления синтаксической
структуры новостного сообщения, которая при совместномиспользовании с
разработанным алгоритмом кластеризации, существенно (более чем на 10%)
улучшает точность и полноту кластеризации новостных сообщений.
7) Определена функциональная схема комплекса анализа потоков
новостных сообщений и математическая модель представления синтаксической
структуры новостного сообщения. Разработанная модель, при использовании
совместно с разработанным алгоритмом кластеризации потоков новостных
сообщений, позволяет существенно улучшить точность и полноту
кластеризации новостных сообщений.
Значение полученных соискателем результатов исследования для практики подтверждается тем, что доказана эффективность гибридного синтаксического анализа на реальных потоках новостных сообщений. Произведена оценка качества кластеризации на корпусе размеченных новостных сообщений ведущих информационных агентств – «РИА Новости», «Интерфакс» и новостных сайтов «Лента.Ру», и«NewsRu.COM». Предложенная в работе математическая модель кластеризации потоков новостных сообщений была реализована на языке программирования Javaи показала высокую производительность, достаточную для анализа более 20 тыс. новостных сообщений в сутки, что соответствует трафику потоков новостных сообщений ведущих информационных агентств.
Оценка достоверности результатов.Методами компьютерного
моделирования и прямыми экспериментами установлено, что при
использовании разработанного алгоритма точность кластеризации
увеличивается более чем на 5%, а полнота – более чем на 10% по сравнению с базовой моделью. Экспериментально установлено ощутимое улучшение качества кластеризации при использовании разработанного гибридного
алгоритма синтаксического анализа. Установлен вклад каждого из уровней представления документа в качество кластеризации потоков новостных сообщений.
Научные положения диссертации внедрены в учебный процесс МГТУ
МИРЭА в дисциплине «Информационно-поисковые системы».Выводы и
рекомендации использованы в действующихпоисково-аналитических
системахкомпаний-производителей лингвистических процессоров, что
подтверждено актами о внедрении. Получено свидетельство о государственной регистрации программы для ЭВМ № 2014611834 от 11 февраля 2014 г. «Программа для кластеризации потоков новостных сообщений на основе многоуровневой модели представления документа».
Апробация работы. Результаты диссертационной работы доложены, обсуждены и получили положительные отзывы на5научных конференциях, конкурсах и семинарах.По материалам диссертационной работы опубликовано 15 печатных работ, в том числе 5 в журналах из перечня ВАКи 1 в журнале, входящем в базу цитирования Scopus.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав основного текста, Заключения, Библиографии (135 наименований) и трх приложений. Общий объем работы — 155страниц, включая 13 рисунков и 10 таблиц.
Метод информационного поиска на основе булевой алгебры
За прошедшие десятилетия произошел взрывной рост количества доступных электронных лент новостей ведущих информационных агентств. В результате возникли серьезные затруднения как для чтения в изобилии поступающих новостных сообщений, так и для их анализа с целью принятия решений на основе полной доступной информации [18-20][18][19][20].
Произошли существенные изменения в структуре самого новостного сообщения. Современная новость состоит не только из даты, заголовка и текста, но кроме этого, обладает вспомогательной информацией, которая может оказаться полезной при анализе новостного потока. В сообщении обычно присутствует ссылка на рубрику, к которой оно относится, во многих случаях также присутствуют дополнительные ссылки на новостные сообщения сходной тематики, добавленные редактором [21].
Существующие комплексы и системы, предназначенные для решения задач кластеризации новостных сообщений, имеют существенные ограничения. Представление новостного сообщения в таких системах и комплексах основано на «поверхностном» (shallow) представлении и анализе текста [3,13,22][3][13][22]. Это представление предполагает, что слова текста независимы друг от друга, а релевантность, или «важность» каждого слова определяется на основе некоторой семантической [23,24][23][24] метрики веса слова. В результате приведения слов к их нормальным формам или выполнения процедуры стемминга (англ., stemming, выделение основы слова) [25], образуется «мешок слов», который представляется в виде пар {термин, частота} над которым выполняются процедуры преобразования и кластеризации. При таком способе представления практически полностью теряется важная лингвистическая информация, которая могла бы существенно улучшить качество кластеризации [26,27][26][27]. В частности, не совершенно не учитывается информация о порядке слов, теряются и синтаксические зависимости, на основе которых можно было бы извлечь информацию об основных объектах новостного сообщения. В результате, кластеризация на основе традиционного представления документа не учитывает ни структуру текста, ни присутствующие в тексте именованные сущности — имена персон, названия организаций, географические названия. Кроме того, метод на основе «мешка слов» не учитывает связи между этими сущностями в тексте [3]. Вместе с тем, несомненным достоинством «поверхностных» методов обработки текстов является их высокая скорость работы [28].
С другой стороны, за последние годы значительно усовершенствовались методы глубокого автоматического лингвистического анализа текстов на естественном языке [29,30,31][29][30][31].
Классический лингвистический подход к анализу текста предполагает существование относительно независимых уровней анализа; в том числе: морфологического, синтаксического и семантического. Кроме того, он предполагает определенную последовательность анализа, в начале -морфологического, затем синтаксического, и наконец, семантического.
Лингвистические методы автоматического анализа текстов основываются на правилах, разработанных экспертами-лингвистами (см. например [32]). Их модели разработки лингвистических ресурсов очень трудоемки, поскольку для создания автоматических систем необходима разработка модели представления значительной части естественного языка, что требует больших трудозатрат высококвалифицированных лингвистов и системных операторов.
Другим способом построения лингвистических анализаторов является подход на основе размеченных лингвистических «корпусов текстов». При использовании этого подхода производится обогащение массивов текстов на естественном языке соответствующей лингвистической информацией, например морфологической, синтаксической, разметкой именованных сущностей. Разработка таких лингвистических ресурсов менее трудоемка, чем разработка модели языка [13].
При использовании «корпусного подхода» лингвистические анализаторы конструируются на основе статистических методов, в частности, на основе методов машинного обучения. В результате применения машинного обучения происходит обобщение частных примеров, представленных в корпусе. В итоге конструируются общие, качественные и во многих случаях эффективные процедуры обработки и анализа текстов. Ряд авторитетных ученых и исследователей, таких как И.Е. Поляков, И.В. Соловьев, В.Я. Цветков, Г.С.Осипов, Д.В. Ландэ, Ю.Д. Апресян, И.А. Мельчук, И.В. Сегалович, И.М. Богуславский, Л.Л. Иомдин, Л.Л. Цинман, Н.И. Ножов, G.Salton, R. Barzilay, J. Nivre, S. Kubler, J. Allan, D. Cutting, J. Beringer своими работами внесли значительный вклад в развитие методов информационного поиска, методов классификации и кластеризации полнотекстовых документов, методов синтаксического анализа и извлечения знаний из текстов. Активно ведут работы в этих направлениях такие организации, как Институт системного анализа РАН, Институт Проблем Передачи Информации РАН, Центр Анализа Интернет Ресурсов, Яндекс, Microsoft, Google, Объединенный Институт Ядерных Исследований, Центр Высокопроизводительных Вычислительных Кластерных Технологий, Научно-Исследовательский Вычислительный Центр МГУ.
Модификация алгоритма Ковингтона для задачи анализа потоков новостных сообщений
Принципиально другим подходом к представлению лингвистической информации являются размеченные корпуса текстов [13]. Корпусная лингвистика — относительно молодая область, поскольку первые корпусы с синтаксической разметкой представляли собой карточки, на которых был представлена синтаксическая структура предложения. Кроме того, основным предназначением корпусов было создание и проверка существующих лингвистических теорий. Такая организация корпусов резко снижала возможности прикладного использования этих корпусов из-за высокой трудоемкости.
Первым корпусом, представленным в электронном виде, содержащим синтаксическую разметку был корпус Lancaster-Leeds Treebank [13] [115], созданный в 1989 году в рамках экспериментов по синтаксическому анализу. В настоящее время электронные корпуса с синтаксической разметкой существуют не только для английского, но и для многих других языков. В частности, для русского языка существует Национальный корпус русского языка (НКРЯ) [113]. В настоящее время одним из основных применений размеченных корпусов текстов является их использование для построения и усовершенствования алгоритмов автоматической обработки текстов. При наличии в корпусе синтаксической разметки возможным становится построение процедур автоматического синтаксического анализа без привлечения экспертов-лингвистов. Корпус в таком подходе используется одновременно для двух целей. С одной стороны он служит основным источником материала для обучения автоматических алгоритмов синтаксического анализа, с другой — является эталонной моделью для оценки качества производимого анализа.
Для эффективного использования размеченных корпусов в вышеуказанных целях необходимо соблюдение ряда условий. Наиболее важным является заранее определенной экспертами-лингвистами формальной схемы разметки. Во-вторых, необходимо, чтобы при разметке корпуса лингвисты последовательно придерживались этой схемы. Предполагается, что тексты являются реализацией модели языка, и если их лингвистическая разметка не будет последовательной, то алгоритмы автоматической машинного обучения не смогут выявить закономерности языка.
Другим важным условием является репрезентативность корпуса. Корпус должен содержать большое количество разнообразных текстов из различных областей и жанров для того, чтобы системы, построенные на его основе, могли качественно обрабатывать текст.
1.4 Методы синтаксического анализа на основе машинного обучения
Развитие корпусной лингвистики и появление размеченных корпусов текстов большого объема сделало возможным использование методов машинного обучения для построения автоматических синтаксических анализаторов [29,115][29][116]. В этом случае корпус рассматривается не как реализация языковой модели, а как материал для обучающей выборки, поскольку для каждого предложения доступна его эталонная синтаксическая структура.
В процессе обучения производится выявление закономерностей [117], которые при обработке реальных текстов позволят получать синтаксические структуры, максимально приближенные к эталонным. Для этого используются современные методы и модели машинного обучения
Рассмотрим два наиболее эффективных алгоритма по результатам соревнования автоматических алгоритмов синтаксического разбора, проведенного на конференции CoNLL в 2006 году [31]: алгоритма на основе максимальных остовных деревьев и алгоритма на основе системы переходов.
Синтаксический анализ предложения с использованием алгоритма максимальных остовных деревьев
Алгоритм на основе максимальных остовных деревьев [116] преобразует задачу синтаксического анализа в задачу нахождения максимального остовного дерева на графе возможных связей. Для этого вводится функция оценки связи s(i,j) = w f(i,j\ где f(i,j) — функция векторизации признаков, на основе которых принимается решение о проведении связи из слова с индексом / в слово с индексом у, w — весовая модель оценки связи, полученная с помощью машинного обучения.
Задача обучения заключается в получении такой функции оценки связи, которая бы для максимального количества предложений из корпуса позволяла построить эталонную синтаксическую структуру
В данном случае, задача обучения является задачей ранжирования — необходимо, чтобы правильная связь получала большую оценку, чем остальные потенциальные связи: Таким образом, все связи можно представить как ранг, наиболее важным элементом которого является правильная (эталонная) связь.
Для применения этого алгоритма необходимо определить правила для построения рангов. Для деревьев зависимостей их можно определить на основе следующих фактов: 1. для каждого слова правильна только одна входящая связь; 2. для данного слова потенциальными хозяевами могут быть все остальные слова предложения и вершина.
Другим важным вопросом является выбор функции векторизации признаков связи. Эта функция определяет преобразование информации о связи и ее участниках в числовой вектор. Классический вариант алгоритмов - максимальных остовных деревьев предполагает независимость ребер графа — каждая синтаксическая связь проводится независимо от уже существующих.
Дополнительные уровни представления новостного сообщения на основе лингвистического анализа
Важной особенностью предложенного алгоритма SVMTAG является то, что в отличие от методов на основе марковских моделей при снятии морфологической омонимии используются характеристики слов, для которых омонимия еще не снята – это текущее слово и его правый контекст. С этой целью вводится дополнительный тип характеристик класс неоднозначности слова по некоторой морфологической категории или группы категорий. Для некой рассматриваемой характеристики извлекаются все ее варианты из возможных морфологических разборов данного слова. Затем, они сортируются в некотором наперед заданном порядке и удаляются повторяющиеся. Затем они склеиваются в одно значение. Например, для приведенного выше примера класс неоднозначности по характеристике части речи у слова «мыла» будет «СУЩ/ГЛАГ», потому что оно может быть как глаголом, так и существительным, по падежам класс эквивалентности будет «ИМ/РОД/ВИН» - именительный, родительный и винительный падежи соответственно. Левый контекст описывается достаточно просто, поскольку в нем уже разрешена морфологическая омонимия. Из левого контекста используются: n-граммы словоформ, частей речи и морфологических характеристик для следующих комбинаций: w[-1], w[-2], w[-3], w[-4], w[-1,-2], w[-1,-3], w[-1,-4], w[-2,-3], w[-2, -4], w[-1,-2, -3], w[-2,-3, -4].
Для описания правого и смешанного контекстов также используются признаки на основе n-грамм словоформ, частей речи и морфологических характеристик для следующих комбинаций слов: w[-1,0,1], w[-2,-1,0], w[-1,0], w[-1,1], w[0,1], w[0,2], w[1,2], w[1,2,3], w[-1,1,2].
Алгоритм SVMTAG предполагает, что при снятии омонимии предложения существует вектор весов, позволяющий оценить вероятность данного конкретного морфологического омонима по его контексту.
Для получения такой оценки используется линейное взвешивание векторизованного представления контекста и вектора весов: score(x) = wt х, (2.1) Где х - векторизованное представление контекста, а wt - вектор весов для набора морфологических характеристик t.
Векторизация контекста производится следующим образом. Каждая пара характеристика-значение контекста склеивается в единое значение и помещается в таблицу, где каждому уникальному значению ставится в соответствие некоторое число - координата этого признака в пространстве R. Если данная пара характеристика-значение присутствует в рассматриваемом контексте, то значение соответствующей координаты вектора контекста устанавливается в 1, в противном случае - 0. Например, информация о том, что часть речи слова w[-1] - глагол в такой таблице может быть представлено как значение «ЧастьРечи(w[-1]=Глагол» и обладать индексом 56312.
Для того чтобы вычислить оптимальный вектор весов воспользуемся алгоритмом SVM [130]. Поскольку для каждого слова из нескольких омонимов необходимо выбрать один, то решаемая задача относится к типу классификации по нескольким классам. Соответствующая задача оптимизации формулируется следующим образом:
Где wm - искомый вектор весов для набора морфологических характеристик m, x - i-тый пример для обучения, yt - метка -того примера для обучения, С - гиперпараметр, определяющий соотношение между точностью и общностью решения.
Для успешного применения любых методов обучения с учителем необходима обучающая выборка. В качестве такой выборки для задачи снятия морфологической омонимии воспользуемся корпусом СинТагРус [113], в котором кроме синтаксической разметки присутствует и морфологическая разметка.
Для кодирования потенциального варианта морфологического разбора существуют два варианта кодирования. Первый вариант заключается в том, что все морфологические характеристики разбора кодируются некоторым уникальным числом. Несмотря на всю простоту реализации этого подхода, у него есть существенный недостаток — число возможных вариантов морфологических характеристик составляет около 500. Это вызывает как вычислительные трудности при обучении и использовании — необходимо хранить 500 векторов весов для каждого набора. Так и возникают трудности с обучением, поскольку для большого числа этих наборов в корпусе СинТагРус существует малое количество примеров. В свою очередь вызывает трудности обобщения.
Другой вариант [129], используемый в настоящей работе, состоит в том, что в качестве класса для обучения выступает каждая отдельная морфологическая характеристика. В приведенном выше примере для слова «мыла» создаются несколько примеров для обучения — по каждому на каждую отдельную морфологическую характеристику. Такой подход существенно уменьшает количество классов для обучения — в русском языке порядка 50 морфологических характеристик. Что на порядок снижает количество классов, по которым нужно проводить обучение. Некоторым недостатком такого подхода можно считать увеличение на 30% объема обучающей выборки, однако этот недостаток играет роль только на стадии обучения, и для его устранения рекомендуется использовать последовательный алгоритм обучения SVM вместо параллельного.
Метрики оценки качества синтаксического анализа
Модуль предназначен для первоначального сбора новостных сообщений в формате RSS и их дальнейшей обработки Входным материалом для этого блока являются новостные ленты в формате RSS. При обработке из каждого RSS-сообщения извлекается ссылка на новостное сообщение, которое затем скачивается из сети Интернет. В результате для анализа появляется доступ к непосредственно новостному сообщению в формате HTML.
Несмотря на то, что формат разметки веб-страниц HTML стандартизирован, для его обработки необходимы специальные библиотеки, которые справляются с обработкой различных нестандартных ситуаций при анализе. Кроме того, в ходе обработки новостного сообщения модуль удаляет неинформативное содержание страницы новости — удаляются рекламные блоки, средства глобальной и локальной навигации, картинки, а также мультимедиа-контент.
Результатом работы этого модуля является новостное сообщение, состоящее из заголовка, основного текста, даты создания и дополнительных заголовков и ссылок, которое пригодно для дальнейшей обработки с помощью разработанных алгоритмов и моделей.
Модуль индексирования Поскольку в процедуре кластеризации используются признаки на основе модели TF-IDF: wt = tf idf (3.12) (N-n + 0,5 idf = log I, (3-13) w V щ + 0,5 / то для их эффективного вычисления необходим модуль поддержки индексов сущностей, обрабатываемых в процессе кластеризации. В разработанном алгоритме кластеризации такими сущностями являются: Термины документа; Персоны, упоминаемые в документе; Организации, упоминаемые в документе; Пары рядом стоящих слов в тексте новостного сообщения; Пары синтаксически связанных слов.
Для создания индекса составляется инвертированный список сущностей указанных типов, встречающихся во всех документах.
При проведении индексирования обрабатываемого текста для каждого его слова собирается информация о частоте встречаемости и позициях, на которых это слово встретилось. Также проводится подсчет текущих значений TF-IDF (частоты слова во всем массиве текстов и обратной частоты слова в документах).
Для эффективного использования аппаратных ресурсов комплекса используется дельта-кодирование всех числовых значений. При таком кодировании на физические носители данных записываются не абсолютные величины, а разность относительно предыдущих элементов:
В результате уменьшается средняя величина записываемых чисел. В результате возможно применить кодирование чисел по переменной длине, что приводит к резкому сокращению необходимого объема дискового пространства. Например, пусть дана последовательность упоминаний (p) некоторого термина t в документе:
Если предположить, что в документе может быть до 65536 слов, то каждая позиция кодируется двумя байтами. Следовательно, для этого списка необходимо 18 байт. При использовании дельта-кодирования последовательность будет выглядеть следующим образом:
Если такое представление закодировать с помощью кода переменной длины, то для такой последовательности необходимо всего 9 байт, что в два раза меньше исходного.
Модуль синтаксического анализа
Основным отличием разработанного комплекса является проведение полного синтаксического анализа текста новостного сообщения.
Первым шагом собственно анализа текста является его морфологический анализ. При его проведении каждому слову приписываются возможные наборы морфологических характеристик.
В качестве входных данных для этого компонента является текст новости. В ходе обработки с текстом производятся следующие преобразования: Разбиение текста на предложения; Разбиение предложений на слова; Приписывание каждому слова наиболее вероятного набора морфологических характеристик.
Затем производится снятие морфологической омонимии и проведение синтаксического анализа всего новостного сообщения с помощью алгоритма, разработанного в разделе 2.3.
После проведения синтаксического анализа новостных сообщений необходимо идентифицировать именованные сущности, которые в нем встречаются: имена людей, названия городов и компаний. Для решения этой задачи с одной стороны используются полу-структурированные открытые источники знаний, в частности, ресурс Wikipedia, с другой — методы на основе машинного обучения.
Модуль кластеризации новостных сообщений После проведения глубокого лингвистического анализа новостного сообщения выполняется процедура кластеризации с помощью алгоритма и математической модели кластеризации разработанной в разделе 3.2.
Для ее проведения новостное сообщение преобразуется в многоуровневое представление документа, а затем выполняется разработанный алгоритм.
При оценке расстояния от нового документов до существующих кластеров вводится понятие активных кластеров. Активным кластером считается такой кластер, в который очередной документ добавлялся не позже чем k временных отсчетов. В результате достигается существенная экономия таких вычислительных ресурсов как объем используемой оперативной памяти и процессорного времени.
