Содержание к диссертации
Введение
1 Анализ предметной области 12
1.1 Задача анализа мнений 12
1.1.1 Обнаружение субъективности в текстах и идентификация мнений 14
1.1.2 Задача определения тональности фрагмента текста 15
1.1.3 Автоматическое аннотирование субъективных текстов 17
1.2 Подходы к классификации текстов по тональности 18
1.2.1 Критерии оценки качества алгоритмов классификации текстов по тональности 20
1.2.2 Классификация на основе методов машинного обучения 22
1.2.2.1 Алгоритмы классификации 23
1.2.2.2 Признаковое описание объектов и веса признаков 28
1.2.2.3 Подходы с использованием алгоритмов машинного обучения 30
1.2.3 Классификация по тональности на основе словарей и
правил 32
1.2.3.1 Методы построения словарей оценочной лексики 32
1.2.3.2 Подходы с использованием словарей оценочных слов 36
1.2.4 Классификация текстов по тональности на русском языке 37
1.2.5 Адаптация алгоритмов к различным предметным областям 39
1.3 Выводы к первой главе 40
2 Модель оценочных слов для построения словаря в заданной предметной области 42
2.1 Модель мнения пользователя 42
2.2 Модель извлечения оценочных слов для заданной предметной области 45
2.2.1 Описание текстовых коллекций 45
2.2.2 Признаки оценочных слов 46
2.2.2.1 Частотные признаки 47
2.2.2.2 Признаки на основе оценок пользователей 48
2.2.2.3 Лингвистические признаки 49
2.2.3 Алгоритмы и оценки качества 50
2.2.4 Исследование качества признаковых наборов 52
2.2.5 Теоретическое исследование признака «Странность» 55
2.2.5.1 Распределения слов в коллекциях текстов 56
2.2.5.2 Распределение случайной величины признака и его некоторые особенности 60
2.2.5.3 Взаимная информация между признаком и классом слова 61
2.2.6 Использование извлеченных оценочных слов в задаче классификации 65
2.2.6.1 Коллекции для тестирования качества классификации отзывов 66
2.2.6.2 Пространство признаков для классификации отзывов 66
2.2.6.3 Эксперименты по классификации отзывов с учётом тональности 69
2.2.6.4 Оценка отзывов экспертами 73
2.3 Перенос модели оценочных слов на различные предметные области 75
2.3.1 Описание результатов переноса модели 75
2.3.2 Использование извлеченных словарей в задачах классификации на РОМИП 2011 77
2.3.2.1 Коллекции и предобработка данных 77
2.3.2.2 Наборы признаков на основе оценочных слов 79
2.3.2.3 Результаты экспериментов по классификации отзывов в различных областях 81
2.3.3 Применение модели к другим языкам 8Г
2.3.4 Система извлечения оценочных слов DomEx 84
2.4 Выводы ко второй главе 85
3 Создание обобщенного списка оценочных слов 87
3.1 Методика формирования обобщенного списка 88
3.2 Перенос классификатора тональности на различные области 91
3.2.1 Меры качества в задаче переноса классификатора 93
3.2.2 Основные результаты переноса классификатора 94
3.3 Поиск и извлечение отзывов из коллекции блогов 95
3.4 Выводы к третьей главе 99
4 Классификация оценочных слов по тональности 100
4.1 Задача классификации слов по тональности 100
4.2 Марковские сети и модель Изинга 103
4.3 Алгоритм распространения доверия 106
4.4 Построение и инициализация модели 109
4.5 Эксперименты и оценка качества 111
4.6 Выводы к четвертой главе 114
Заключение 115
Список рисунков 116
Список таблиц 118
Литература
- Подходы к классификации текстов по тональности
- Признаки на основе оценок пользователей
- Перенос классификатора тональности на различные области
- Алгоритм распространения доверия
Введение к работе
Актуальность темы. С развитием сети Интернет неуклонно растет объем хранимой неструктурированной информации, представленной текстами на естественных языках. Условно такую информацию можно разделить на два типа: «фактическая информация» и «субъективные мнения пользователей». За прошедшее десятилетие наиболее активному исследованию подвергались алгоритмы и программные системы связанные с обработкой фактической информации (например, поисковые машины).
С появлением Веб 2.0 и построенных на его основе социальных сетей, платформ для блогов и микроблогов, объём информации второго типа стал существенно увеличиваться. «Блогосфера» стала наиболее динамичной частью всемирной паутины, которая развивается, реагируя на события в реальной жизни. Вследствие этого растет научный и практический интерес к задачам обработки субъективной информации.
В рамках решения таких задач важными понятиями являются субъективность и тональность текста. Субъективность текста определяется наличием в нём точки зрения автора и выражением его мнения, а не констатацией фактов. Тональность — это эмоциональное отношение автора высказывания к некоторому объекту (объекту реального мира, событию, процессу, или их свойствам/атрибутам) .
Для решения задачи анализа мнений необходимо обладать большим количеством вспомогательных знаний об объектах и их атрибутах, оценочных словах и выражениях, а также владельцах мнений - в виде специализированной базы знаний. Одним из наиболее важных видов знаний являются словари оценочных слов и проставленные оценки тональности для каждого слова. Однако построение универсального словаря оценочных слов является невыполнимой задачей, так как оценочность суждения во многих случаях зависит от предметной области.
Каждая предметная область может иметь свойственную только ей оценочную лексику, либо значения оценочных слов могут меняться в разных областях. Например, «нужно увидеть» является сильным оценочным выражением в предметной области о фильмах, но нейтральным в общественно-политической области. На практике это означает, что необходимо повторять трудоёмкую процедуру по составлению словарей оценочных слов для каждой предметной области, чтобы качество обработки субъективной информации оставалось на приемлемом уровне.
Таким образом, актуальной является проблема автоматического извлечения словарей оценочных слов из коллекций текстов для различных предметных
областей. Такие словари могут быть полезны при адаптации алгоритмов анализа мнений к конкретной области, а также для улучшения качества работы в различных задачах, например в поиске оценочной информации. Кроме того, извлечение оценочных слов непосредственно из текстовых коллекций позволяет найти сленг и другие несловарные слова, которые могут быть важными факторами при обработке мнений.
Цель диссертационной работы. Целью диссертационной работы является разработка методов и программных средств построения базы знаний для задачи анализа мнений. Разрабатываемые программные средства должны удовлетворять следующим требованиям: высокая точность извлеченных словарей оценочных слов; применимость к различным предметным областям; возможность комбинации словарей из различных предметных областей; определение тональности извлеченных оценочных слов.
Для достижения этой цели были решены следующие задачи:
-
Исследование и разработка модели извлечения оценочных слов для заданной предметной области и перенос обученной модели извлечения оценочных слов на другие предметные области без дополнительной разметки;
-
Разработка методов автоматического определения тональности извлеченных слов;
-
Построение обобщенного словаря оценочных слов, не зависящего от предметной области, на основе извлеченных знаний;
-
Разработка программного модуля извлечения оценочных слов для заданной предметной области и комбинации знаний из разных предметных областей.
Основные положения, выносимые на защиту:
-
Предложен новый метод автоматического извлечения оценочной лексики заданной предметной области, основанный на использовании нескольких текстовых коллекций и совокупности признаков. Показана переносимость предложенной модели извлечения оценочных слов на разные предметные области;
-
Предложен и реализован новый метод автоматического определения тональности извлеченных оценочных слов. Метод основан на применении марковских случайных полей;
-
На основе предложенного метода извлечения оценочной лексики был создан словарь оценочных слов, независящих от предметной области. Данный
словарь был опубликован и является первым общедоступным словарем оценочной лексики для русского языка. Показана полезность данного ресурса в нескольких задачах анализа тональности текстов;
Научная новизна: Новизна настоящей диссертационной работы заключается в том, что предложен новый метод построения базы знаний для задачи анализа мнений на основе ряда текстовых коллекций и комбинации статистических признаков. Применимость метода обоснована теоретически, на основе анализа полезности ряда признаков для классификации оценочных слов, а также численно, для чего были проведены эксперименты с использованием извлеченных знаний. Разработанный метод может применяться в различных предметных областях для извлечения знаний и построения автоматических алгоритмов анализа мнений на их основе.
Практическая значимость. На основе предложенного метода спроектирована и реализована программная система для извлечения оценочных слов в заданной предметной области. Разработанная система также имеет возможность комбинирования списков оценочных слов для формирования общих, независящих от предметной области словарей. Такой словарь был создан для мета-области товаров и общедоступен для исследовательских целей1. Таким образом, разработанная система может быть использована для создания баз знаний оценочных выражений в различных предметных областях без какого-либо дополнительного участия человека.
Результаты научных исследований, представленных в диссертации, частично использовались в рамках гранта РФФИ № 11-07-00588-а под руководством Лукашевич Н.В.
Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:
На международной конференции «Диалог» (2010г.);
На международной конференции «Ломоносов» (2010г.);
На 12-й национальной конференция по искусственному интеллекту с международным участием (2010г.)
На международной конференции «Диалог» (2011г.);
На семинаре по поиску концептов в неструктурированной информации (CDUD), проходящему совместно с конференцией RSFDGrC (2011г.);
На семинаре по поиску информации и извлечению знаний (IEKA), проходящему совместно с конференцией RANLP (2011г.);
На международной конференции «Диалог» (2012г.);
На летней школе по информационному поиску RUSSIR (2012г.);
На международной конференции COLING (2012г.);
На международной конференции «Ломоносов» (2013г.);
На международной конференции «Диалог» (2013г.);
Кроме того, результаты обсуждались на семинаре лаборатории анализа информационных ресурсов НИВЦ МГУ, на семинаре в НИУ ВШЭ и на регулярном семинаре ACM SIGMOD в Москве.
Личный вклад заключается в выполнении основного объема теоретических и экспериментальных исследований, изложенных в диссертационной работе, включая разработку теоретических моделей, методик экспериментальных исследований, проведение исследований, анализ и оформление результатов в виде публикаций и научных докладов.
Результаты, связанные с извлечением оценочных слов, частично использовались в рамках гранта РФФИ № 11-07-00588-а под руководством Лукашевич Н.В.
Публикации. По теме диссертации опубликовано 18 работ, основные результаты изложены в 10 печатных работах, в том числе в 2 статьях в журналах из списка ВАК [1,2], 1 статье, входящей в базу SCOPUS [3], и в 7 других изданиях [4-Ю].
Объем и структура работы. Диссертация состоит из введения, четырёх глав, заключения и двух приложений. Полный объем диссертации составляет 131 страницу с 8 рисунками и 17 таблицами, объем приложений - 15 страниц. Список литературы содержит 103 наименования.
Подходы к классификации текстов по тональности
Первой, базовой подзадачей, возникающей в рамках задачи анализа мнений, является определения субъективности или объективности текста. В работе [2] указывается, что все тексты могут содержать два типа информации: субъективные мнения (выражение оценки, чувств автора) и объективные данные (факты, формальные высказывания). Зачастую при автоматической обработке текстов заранее может быть не известно содержит ли конкретный текст субъективную информацию или нет.
В целом задача классификации текстов на субъективные и объективные является более сложной, чем последующая классификация текстов по тональности [31]. Данный факт позволяет предположить, что улучшение качества решения данной задачи, будет вести к улучшению всех зависящих от нее задач (классификация по тональности, автоматическое аннотирование). Так, согласно результатам работы [32], за счёт исключения объективных предложений из текстов отзывов о фильмах, удалось существенно улучшить качество классификации отзывов по тональности.
Задача идентификации мнений решалась в ряде работ [33,34] и в дальнейшем в рамках текущего исследования (если иное не указано явно) будем предполагать, что все тексты о которых идет речь содержат оценку автора и являются субъективными мнениями. Данное предположения не накладывает каких-либо ограничений на текущую работу, поскольку существует большое количество порталов в Интернете, которые нацелены на сбор именно мнений и отзывов пользователей, заведомо содержащих какую-либо оценку.
Общая постановка задачи определения тональности выглядит следующим образом: для субъективного фрагмента текста, в котором содержится общее мнение только об одной теме или объекте, необходимо классифицировать мнение в одну из двух противоположных категорий — положительную или отрицательную, либо определить позицию на непрерывной прямой между этими двумя полярностями.
Большое количество исследований [26] в рамках данной задачи связано с обработкой отзывов (например, «понравилось» или «не понравилось», для отзывов о фильмах). При этом тональность текста отождествляется с отношением к некоторому объекту, «понравилось» значит «положительный». Существует ряд задач, где такое соответствие носит более сложный характер, например «поддерживает» или «высказывается против» некоторой темы автор политического выступления. Другим примером может быть: высказывается ли большинство людей в блогах «за» некоторого кандидата или «против». Несмотря на различия категорий в каждом из приведённых примеров, классификация идет на два различных субъективных класса, вследствие чего, подходы к решению остаются одними и теми же во всех случаях.
В текущем исследовании в качестве данных для работы были выбраны отзывы о различных товарах (фильмы, книги, мобильные телефоны), так как они заведомо содержат субъективную оценку по отношению только к одному объекту и представляют интерес для широкого пользователя.
Хотя классификация по тональности на два класса остаётся наиболее популярной и востребованной задачей на практике, зачастую необходимо сравнить несколько объектов или представить более детально сильные и слабые стороны какой-либо сущности. В этом случае классификации на два класса уже недостаточно. В литературе рассматриваются задачи классификации на три, пять или более классов [26]. Такие задачи можно формулировать в виде мультиклассовой классификации, либо как задачу восстановления регрессии, ввиду упорядоченности тональных оценок на прямой от отрицательной оцеш ки, до положительной.
В отличие от тематической классификации [35], в которой может быть от двух до нескольких тысяч классов, заданных некоторой таксономией, при классификации текстов по тональности используется относительно небольшое количество классов (от двух до пяти), которые должны оставаться консистентными в различных предметных областях и для различных пользователей. Кроме того, в то время как классы в тематической классификации являются практически не связанными друг с другом, в задаче классификации по тональности все целевые категории можно упорядочить на прямой градаций тональности от отрицательной, до положительной.
Как показывает сравнение задач классификации по тематикам и по тональ ности [29], во втором случае сложнее сформировать набор ключевых слов, которые позволяют получить высокое качество работы. Автоматическая обработка отзывов осложняется такими факторами как наличие иронии и сарказма, учет отрицаний, словами, которые становятся оценочными только в кон кретной предметной области или контексте. Обзор полезных признаков для решения данной задаче описан в разделе 1.2.2.2.
Все эти факты способствовали формированию отдельной области исследований, посвященных задаче классификации текстов по тональности.
При аннотировании одного документа основной целью является выявление ключевых субъективных фрагментов текста, которые выражают общую оценку всего текста. Такая постановка может быть полезна при анализе больших рецензий кинокритиков или при автоматической обработке политических обзоров. В литературе описан ряд подходов к решению данной задачи [26], где основной идеей является извлечение субъективных предложений (или других согласованных частей текста) и составление из них аннотации по аналогии с тематическим аннотированием.
Когда идет обработка группы документов об одном объекте, наиболее востребованной является задача составления по-атрибутного представления. Для этого из субъективных фрагментов текстов необходимо извлечь ключевые части и свойства объекта с соответствующими им оценками. Основные подходы к решению данной задачи включают в себя два этапа [36]: поиск и извлечение атрибутов и сбор субъективных оценок по каждому атрибуту. В некоторых работах данные этапы выполняются итеративно, так как атрибуты объекта часто встречаются с оценочными словами и наоборот [37]. В более поздних иссле дованиях предпринимаются попытки совместного рассмотрения всех атрибутов и их оценок одновременно, что позволяет составить более согласованную аннотацию [38,39].
Признаки на основе оценок пользователей
В качестве эталона качества для автоматических систем классификации текстов по тональности обычно выступает ручная разметка экспертов, которым было дано такое же задание как и системам. Так как разметка по тональности является трудоемкой задачей, то зачастую в качестве эталона используют оценки авторов отзывов, которые можно найти на многих рекомендательных сервисах и агрегаторах отзывов в Интернете (например, www.imhonet.ru). В этом случае автор отзыва сам выступает в роли эксперта, ставящего численную оценку в соответствии с написанным текстом.
Чтобы снизить влияние субъективного фактора, для разметки текстов по тональности по возможности привлекается несколько экспертов. В данном случае становится возможным оценить согласие экспертов, которое становит ся верхней границей качества, а также появляется возможность использовать различные схемы измерения качества:
Качество решения задачи классификации текстов по тональности существенно зависит от используемых алгоритмов машинного обучения, а также от выбора признакового описания объектов и задания весов каждого из признаков. В данном разделе будут рассмотрены наиболее распространенные ал горитмы обучения с учителем и модели признакового представления текстов, которые позволяют получить высокое качество работы в данной задаче.
В данном разделе описаны основные алгоритмы машинного обучения с учителем, которые чаще всего применяются для классификации текстов по тональности.
Метод опорных векторов. Метод опорных векторов — один из наиболее эффективных и популярных алгоритмов классификации, основные идеи которого были предложены коллективом советских математиков в 70-е годы [40]. Ключевой идеей данного алгоритма является построение оптимальной разделяющей гиперплоскости между объектами из разных классов. Требование оптимальности заключается в максимизации расстояния от объектов каждого из классов в обучающей выборке до гиперплоскости.
Параметр С О — управляющий параметр метода, который позволяет находить компромисс между максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки. Для нахождения минимума целевой функции при граничных условиях-неравенствах используется метод Лагранжа.
К основным достоинствам метода можно отнести единственность решения в задаче квадратичного программирования, существование эффективных реализаций данного алгоритма, обобщаемость метода на случай нелинейных разделяющих поверхностей за счет введения функций ядра. К недостаткам можно отнести относительно медленный процесс обучения, слабую устойчивость к шумам в тренировочном наборе и чувствительность к нормировке пространства признаков.
Метод опорных векторов широко применяется в различных задачах обработки текстов на естественном языке, таких как тематическая классификация или классификация текстов по тональности [26].
Логистическая регрессия. Метод логистической регрессии является линейным классификатором, опирающимся на ряд вероятностных предположений. Данные предположения, в частности, позволяют однозначно определить функцию потерь и получить численные оценки вероятности принадлежности кажт дого объекта к некоторому классу.
Пусть множество объектов и ответов X х Y является вероятностным про-: странством, а выборка прецедентов Xі = (xi,yi)li=1 получена случайно и независимо согласно вероятностному распределению с плотностью р{х,у) = ру(х)р(у). Дополнительно предположим, что функции правдоподобия классов ру(х) принадлежат экспоненциальному семейству распределений и отличаются только параметрами сдвига ву [41].
Основными преимуществами данного метода являются простота и достаточно низкая ресурсоемкость. Время обучения линейно зависит от размера обучающей выборки. К недостаткам метода можно отнести низкое качество классификации в случае невыполнения базовых предположений. Обычно данный метод используется в качестве базового уровня в различных задача классификации, в том числе при обработке текстов на естественном языке.
Методы построения ансамбля классификаторов. При решении задачи классификации зачастую бывает так, что ни один из распространённых методов (включая вышеописанные) не позволяет получить высокое качество работы. Одной из причин может быть существенно более высокая сложность и многофакторность задачи, которую не удаётся смоделировать каким-либо одним алгоритмом.
В таком случае зачастую в литературе [42] предлагается использовать ансамбли классификаторов. Существует достаточно большое количество методов построения таких ансамблей, но в данной работе будут рассмотрены два наиболее распространённых: бэгинг (bagging) и бустинг (boosting).
В рамках первого подхода (bagging) строится набор слабых классификаторов, где каждый их них обучается по ограниченной произвольной подвыбор-ке тренировочного набора. Таким образом, на основе одного тренировочного набора строится большое количество различных классификаторов. Затем все построенные классификаторы объединяются в один с помощью процедуры голосования, причём вес всех слабых классификаторов одинаков. Такой подход позволяет строить более устойчивые к переобучению алгоритмы, поскольку каждый слабый классификатор обучается независимо от других. Одним из наиболее распространённых методов, построенных на основе данного подхода, является случайный лес (Random Forest), где в качестве слабых классификаторов выступают решающие деревья [42].
Второй подход к построению ансамблей классификаторов — это адаптивная коррекция ошибок (boosting). Основная идея данного подхода следующая: строится последовательность слабых классификаторов, где каждый последующий минимизирует ошибку, которую даёт объединение всех предыдущих классификаторов. Наиболее известным классификатором на основе бустинга является алгоритм AdaBoost [42]. В данной работе также широко будет использоваться LogitBoost, который является модификацией AdaBoost с использованием логистической функции [42].
Преобразование фрагмента текста в вектор признаков, которые позволяют описать наиболее важные особенности и скрытые закономерности необходимые для качественного решения конкретной задачи, является важным этапом при построении алгоритмов классификации на основании алгоритмов машинного обучения. Традиционным подходом к представлению текста является модель «мешок слов», когда фрагмент текста представляется в виде вектора слов, длинна которого равна размеру заранее заданного словаря. В качестве весов признаков могут использоваться как частота слова в тексте, так и бинарное значение: встретилось слово в тексте или нет. В ранних исследованиях задачи классификации по тональности отмечается, что на практике бинарные веса работают лучше [29].
Перенос классификатора тональности на различные области
В данной главе вводится формальная модель «мнения» пользователя и описываются основные типы знаний, необходимые для решения задачи анализа мнений. Одним из ключевых видов знаний являются оценочные слова и выражения, с помощью которых выражается отношение автора к объекту. Для автоматического построения словарей оценочных слов предлагается новый метод, основанный на использовании нескольких текстовых коллекций и набора статистических признаков. Для наиболее значимого признака «Странность» предлагается теоретическая модель, объясняющая зависимость качества признака от коллекций, с помощью которых он вычисляется. Словари оценочных слов, извлеченные с использованием разработанного алгоритма, применяются в задаче классификации отзывов по тональности.
Для эффективного решения задачи анализа мнений необходимо формальт но определить понятие мнения пользователя. В целом, мнения пользователей могут быть выражены о чем угодно, о продукте, услуге, человеке, организации или событии. В данной работе будет использоваться термин объект для обозначения целевой сущности, о которой высказано мнение. Каждый объект может иметь набор компонент (или частей), а также набор свойств. Каждый компонент также может иметь набор компонент и свойств. Таким образом, каждый объект может быть представлен в виде иерархии на основе отношений часть-целое [2].
Рассмотрим конкретный пример: некоторая модель мобильного телефона является объектом. У данного объекта есть набор компонент, таких как батарея или экран, и набор свойств, таких как размер, вес или качество звука. У батареи также есть набор свойств, таких как размер батареи и емкость батареи.
Но данное представление объекта в виде иерархии является очень сложным для практического применения и упрощается за счёт объединения компонент и свойств объекта в одну группу атрибутов [2]. В такой нотации объект может быть представлен как атрибут, который находится на вершине вышеописанной иерархии. Таким образом мы переходим от понятия иерархии к объекту и его набору атрибутов (где объект сам по себе является своим атрибутом).
К каждому атрибуту может относиться некоторое мнение, высказанное его владельцем. Под владельцем мнения будем понимать человека или организацию выражающих некоторое отношение к объекту или его атрибуту. В случае отзывов о продуктах, записей в блогах, владельцем мнения является автор текста.
Основной вид информации в рамках данной работы — субъективные мнения пользователей о тех или иных объектах и их атрибутах. Мнение об атрибуте / — это общая эмоция, суждение или оценка по поводу /, высказанная владельцем мнения. У каждого мнения может присутствовать тональность или эмоциональная окраска: положительная, отрицательная, смешанная или нейтральная. Наиболее простым случаем является положительная тональность, например «Я в диком восторге!!!!» или отрицательная тональность «Это какой-то ужас». На основе введенных понятий можно определить формальную модель объекта и на основании этой модели — формальную модель мнения.
Формальная модель мнения: В общем виде некоторый документ d содержит мнения о наборе объектов о\,..., од от набора владельцев мнений h\,..., hq. Мнение по каждому объекту Oj выражено в отношении подмножества его атрибутов Fj. Мнение — это пятёрка (oj,fjk,ooijki,hi,ti), где Oj это некоторый объект, fjk это атрибут объекта Oj, oo ki это тональность мнения по отношению к атрибуту fjk, hi это владелец мнения, а і/ это время в которое было высказано мнение. Для каждого атрибута fjk владелец мнения выбирает соответствующее слово или фразу из набора Wjk и выражает мнение с помощью оценочных слов и выражений из некоторого набора Wp, которые зависят от предметной области D и, зачастую, от контекста. Здесь под оценочными сло-т вами и выражениями понимаются все слова и словосочетания, которые выражают оценку напрямую, либо неявно, с использованием скрытого смысла, иронии или сарказма.
В рамках текущей работы основное внимание будет уделяться второму типу знаний — оценочным словам и выражениям. Будет описано построение и обучение модели извлечения оценочных слов на данных из предметной области о фильмах.
Оценочные слова обладают рядом особенностей: концентрация оценочных слов в отзывах пользователей существенно выше, чем, например, в новостных текстах; каждое оценочное слово обладает некоторой тональностью и за счёт этого чаще употребляется в текстах с определённой эмоциональной окраской; оценочные слова чаще являются прилагательными или наречиями, реже существительными или глаголами. На основании данных наблюдений предлагается и исследуется модель оценочных слов для их качественного извлечения.
Во-первых, для построения модели было собрано 28,773 отзыва о фильмах различного жанра с рекомендательного портала www.imhonet.ru. Каждому отзыву соответствовала оценка автора по десятибалльной шкале. Эта коллекция является основной для работы, назовем её коллекцией мнений.
Пример отзыва: Неплохой фильм, главное не выключить его в начале, где он напоминает просто ужасную пародию на Адреналин. Ну а в целом в фильме есть, как и положительные (адреналиновые, захватывающие и интересные сцены) так и отрицательные (неоднозначный финал, не везде удачная режиссура) качества.
Алгоритм распространения доверия
В качестве алгоритма классификации предпочтительно было использовать алгоритмы обучения, где не требуется дополнительная ручная разметка, так как это требует существенных трудозатрат. В данном случае применение простых алгоритмов жесткой кластеризации (например К-средних) или нежесткой кластеризации (например ЕМ-алгоритм) является нецелесообразным из-за предположения о взаимной независимости объектов. Такое ограничение не является вполне естественным, так как тональность оценочных слов зависит от их совместной встречаемости и среднего расстояния между ними.
Более естественным подходом к данной задаче является представление множества оценочных слов и связей между ними в виде структурированного набора, состоящего из нефиксированного заранее числа «элементарных» объектов, которые в свою очередь кодируются конечномерными векторами [97]. То есть решается задача классификации взаимосвязанного массива данных.
В текущей главе, для оценочных слов в заданной предметной области, строится неориентированный граф, где каждая вершина представляет случайную величину, обозначающую тональность некоторого слова из вышеупомянутого списка. Также высказывается предположение, что тональность оценочного слова зависит только от слов, встречающихся с ними в непосредственной близости. То есть тональность слова является локальной характеристикой, или формально, выполняется локальное марковское свойство для вершин в графе. Тогда построенный граф представляет собой марковскую сеть, в которой заданы попарные и унарные потенциальные функции. Реализуемая модель схожа по построению с моделью Изинга, математической моделью статистической физики, предназначенной для описания намагничивания материала.
Аналогичный подход рассматривается в работе [98]. Авторы также используют модель Изинга для определения тональностей слов. Для этого строится граф, в котором связи задаются на основе появления некоторого слова в определении из толкового словаря другого слова. Кроме того, связи дополняются с помощью синонимов, антонимов и гиперонимов из тезауруса WordNet и учёта встречаемости через союзы И, ИЛИ, НО в коллекции текстов по аналогии с [27].
Для небольшой группы слов из графа задаются правильные значения тональности и используется метод самосогласованного поля для поиска оптимального состояния системы. В результате производится оценка только слов, входящих в словарь общезначимой оценочной лексики General Inquirer [58], без учета всех остальных слов.
В данном разделе будет сделано краткое введение в теорию Марковских случайных полей и модель Изинга.
Систему случайных величин, зависящих от нескольких параметров, обычно называют случайным полем. Понятие случайного поля есть естественное обобщение понятия случайного процесса &(ги) на случай, когда параметр t имеет размерность большую единицы. В данной работе рассматриваются случайные величины с дискретными аргументами.
Пусть t = (t1, 2, ...,iu) совокупность векторов в евклидовом пространстве, где каждая компонента принимает целочисленные значения. Множество таких точек обозначим за Tv. Сопоставим каждой точке t Є Tv случайную величину t. Если ff принимает значение в некотором конечном множестве X, то совместное распределение имеет вид: Введем понятие условной вероятности того, что случайное поле приняло некоторые значения х\,Х2, хп на точках множества S — і,І2 , п ПРИ условии, что вне этого множества оно приняло значения х(і) Є X [99],
To есть случайная величина условно независима от всех других величин, при заданных значениях её соседей. В более простой форме: марковское случайное поле - это вероятностная модель, в которой зависимости между случайными величинами представлены в виде неориентированного графа и множество случайных величин обладает марковским свойством.
Для параметризации марковских сетей часто используют гиббсовскую факторизацию, так как это зачастую более удобный и эквивалентный способ определения [100]:
Действительную функцию U(y,x(t),s,t) часто называют потенциалом переменных х,у Є X и s,t є Tv, она может принимать любые вещественные значения и симметрична относительно перестановки переменных х, у.
Модель Изинга. Пусть задана система из N частиц в пространстве, каждая из которых имеет свой спин (равный +1 или -1). Спины соседних частиц взаимодействуют друг с другом и энергетически пытаются иметь одинаковое направление. Такая модель называется моделью Изинга и её энергетическая
Одним из наиболее распространённых и широко известных алгоритмов вывода для марковских случайных полей является алгоритм распространения доверия. В общем случае данная задача является NP-трудной и может быть решена лишь приближенно, но для отдельного класса графов — ациклических, алгоритм находит точное решение. В случае циклических графов можно инициировать передачу сообщений из случайно выбранных узлов и циклически передавать их до сходимости. Такой подход называется loopy belief propagation (циклический алгоритм распространения доверия), но он не гарантирует сходимость (и сходимость к точному ответу в частности). Зачастую циклический алгоритм распространения доверия позволяет найти хорошее приближение к решению.
Рассмотрим случай ациклического графа с заданными унарными и парными потенциалами. Рассуждения в общем случае будут верны и для произвольной ациклической марковсной сети с произвольными потенциальными функциями [101].
Для решения данной задачи дискретной оптимизации, в общем случае необходимо перебрать все К возможных значений X (где К это коли 106 чество значений, которое может принимать каждая переменная). В случае ациклических марковских сетей, алгоритм распространения доверия (belief propagation), основанный на передаче сообщений между вершинами графа, позволяет найти точное решение.
Будем рассматривать связанный ациклический граф, который по определению является деревом. Выберем произвольную вершину, которую будем считать корнем. Пронумеруем все вершины от 1 до iV так, чтобы путь от любого листа до корня состоял из вершин с убывающими номерами. Это можно сделать, например, с помощью обхода в ширину. Обозначим через X поддерево с корнем г и вершинами j і, путь от которых до корня проходит через і. Не ограничивая общности, предположим, что количество ребер, связанных с корнем, равно двум. Введем следующую функцию:
