Исследование и разработка методов построения программных средств обнаружения неестественных текстов Аспирант 3 г.о. Павлов А.С. Научный руководитель: зав. лаб. НИВЦ МГУ к.ф.-м.н. Добров Б.В Павлов А.С., Обнаружение неестественных текстов 1

План доклада Введение – Проблема неестественных текстов – Генераторы текстов на основе цепей Маркова Обзор существующих решений Постановка задачи Предлагаемые алгоритмы: – Алгоритм на основе оценки тематического разнообразия – Алгоритм на основе комбинации статистических характеристик текстов Программная система обнаружения поискового спама – Архитектура системы – Вычислительные эксперименты Заключение Павлов А.С., Обнаружение неестественных текстов 2

Проблема неестественных текстов Неестественные тексты (текстовый спам) – это тексты, порожденные с помощью специализированных программ, на основе образцов существующих текстов, с целью дискредитации алгоритмов анализа текста Примеры: – Почтовый спам – Поисковый спам – Спам на веб-сайтах – «Корчеватель» Павлов А.С., Обнаружение неестественных текстов 3

Поисковый спам Поисковый спам – это любое намеренное действие, целью которого является незаслуженное повышение оценки страницы, по сравнению с ее реальной ценностью Масштабы: – 20% всех сайтов в Интернете являются спамом – 5-7% страниц на выдаче являются поисковым спамом Нацелен на дискредитацию алгоритмов, применяющиеся в поиске: – Тексты – Ссылки – Клики Павлов А.С., Обнаружение неестественных текстов 4

Пример поискового спама Павлов А.С., Обнаружение неестественных текстов 5 (

Алгоритм обнаружения текстового спама на основе эвристик Всего 9 статистических факторов: – Количество слов на странице – Количество слов в заголовке – Средняя длина слов – Доля текста в ссылках – Доля видимого текста – Сжимаемость текста – Доля популярных слов, содержащихся на странице – Доля слов на странице, входящих в список популярных – Доля редких 3-грамм Результат (на данных от MSN): – Полнота 86% – Точность 91% Павлов А.С., Обнаружение неестественных текстов 6 Ntoulas et. al., Detecting Spam Web Pages through Content Analysis // WWW 2006

Метод на основе анализа тематик текста Идея – спам часто относится к некоторым тематикам (страхование, недвижимость и т.п.) Применение статистической модели Скрытое Распределение Дирихле (Latent Dirichlet Allocation) для обнаружения спама СРД с учетом ссылочной структуры: – Учитывалась взаимосвязь тематик ссылающихся друг на друга документов Лучшие результаты на данных WebspamUK Павлов А.С., Обнаружение неестественных текстов 7 Biro et.al. Linked latent Dirichlet allocation in web spam filtering // AirWEB 2009

Недостатки существующих методов Не исследованы сложные типы спама – Цепи Маркова Учет ссылок сильно замедляет процесс обработки – Не применимы, когда ссылки не известны, или к ним нет эффективного доступа (снятие спама в реальном времени) Тематические классификаторы не могут отделить неестественные тексты от документов-образцов Павлов А.С., Обнаружение неестественных текстов 8

Постановка задачи Исследование и разработка модели массово порожденных неестественных текстов; Исследование и разработка алгоритмов обнаружения текстового спама на основе машинного обучения; Разработка программного модуля классификации текстового спама, удовлетворяющего следующим условиям: – точность и полнота обнаружения текстового спама, превосходящая существующие аналоги; – применимость к различным естественным языкам; – скорость обработки документов близкая к режиму реального времени; Павлов А.С., Обнаружение неестественных текстов 9

План доклада Введение – Проблема неестественных текстов – Генераторы текстов на основе цепей Маркова Обзор существующих решений Постановка задачи Предлагаемые алгоритмы: – Алгоритм на основе оценки тематического разнообразия – Алгоритм на основе комбинации статистических характеристик текстов Программная система обнаружения поискового спама – Архитектура системы – Вычислительные эксперименты Заключение Павлов А.С., Обнаружение неестественных текстов 10

Обобщенная модель генераторов текстов Методы генерации текстов используют документы-образцы для обучения: – Генераторы на основе «мешка слов» – Генераторы на основе цепей Маркова – Генераторы, копирующие фрагменты естественных текстов Была разработана обобщенная модель генератора текстов на основе документов- образцов Павлов А.С., Обнаружение неестественных текстов 11

Пример генератора на основе цепи Маркова Павлов А.С., Обнаружение неестественных текстов 12

Пример эквивалентной обобщенной модели Павлов А.С., Обнаружение неестественных текстов 13 1/6 Равновесное распределение

Тематическая структура Тематическая структура – распределение долей слов, принадлежащих каждой из K тематик – Лежит на K -мерном симплексе – Можно моделировать с помощью Скрытого распределения Дирихле (СРД, Latent Dirichlet Allocation) Теорема: Тематическая структура порожденного текста является усредненной тематической структурой документов-образцов Павлов А.С., Обнаружение неестественных текстов 14

Применение модели Скрытое распределение Дирихле Павлов А.С., Обнаружение неестественных текстов 15 Распределение вероятностей векторов тематической структуры K=3 Порожденные тексты (усредненное распределение нескольких естественных текстов) Естественные тексты (распределение Дирихле)

Комбинированный алгоритм Гипотеза: на настоящий момент не существует метода порождения, который воспроизводил бы все аспекты естественных текстов Используемые признаки: – Тематическое разнообразие – Читаемость – Стилистические характеристики – Характеристики разнообразия Метод обнаружения: – Выделяем признаки естественных текстов, которые трудно воспроизвести – С помощью методов машинного обучения с учителем строим классификатор Павлов А.С., Обнаружение неестественных текстов 16

Читаемость текстов Чем длиннее слова в тексте и длиннее предложения, тем сложнее восприятие текста «Сложность» текста можно измерить: – Например, индекс Колмана-Лиау: – Применяется в США при оценке уровня владения школьниками письменной речью Признаки, связанные с читаемостью: – Средняя длина слов в символах/слогах – Средняя/максимальная длина предложений – И т.п Павлов А.С., Обнаружение неестественных текстов

Стилистические характеристики Статистические методы определения авторства: – Доли частей речи и служебных слов Наличие экспрессивной пунктуации и частиц могут указывать на определенный стиль текста: «Ну и что же теперь делать?!» Статистика употребления: – Экспрессивной пунктуации (!,?,:)) – Редких оборотов и частей речи Павлов А.С., Обнаружение неестественных текстов

Глобальные характеристики разнообразия Естественным текстам свойственны повторы Повторы приводят к выполнению глобальных статистических законов: – Закон Ципфа Оцениваем значение параметров для конкретного текста Сжимаемость текста алгоритмами gzip, bz2 Закон Ципфа: Павлов А.С., Обнаружение неестественных текстов

Характеристики комбинированного метода Всего 75 признаков, не зависящих от тематики текстов: – Читаемость (12) – Жанр и стиль (54) – Разнообразие (7) – Тематическое разнообразие (2) Павлов А.С., Обнаружение неестественных текстов 20

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

План доклада Введение – Проблема неестественных текстов – Генераторы текстов на основе цепей Маркова Обзор существующих решений Постановка задачи Предлагаемые алгоритмы: – Алгоритм на основе оценки тематического разнообразия – Алгоритм на основе комбинации статистических характеристик текстов Программная система обнаружения поискового спама – Архитектура системы – Вычислительные эксперименты Заключение Павлов А.С., Обнаружение неестественных текстов 22

Программная система обнаружения поискового спама Павлов А.С., Обнаружение неестественных текстов 23

Апробация системы Система апробирована в инфраструктуре обнаружения поискового спама поисковой системы Яндекс: – Обнаружение спама в режиме близкому к реальному времени для Поиска по Блогам (обрабатывает 20 млн. документов в день на 4-х серверах) – Один из элементов системы обнаружения поискового спама в Веб-поиске Павлов А.С., Обнаружение неестественных текстов 24

Метрики качества Точность (Precision) – доля неестественных текстов, среди срабатываний классификатора Полнота (Recall) – доля неестественных текстов, обнаруженных классификатором F-мера – среднее гармоническое между точностью и полнотой AUC – площадь под кривой полноты/уровня ошибок. Применяется на наборе WebspamUK Павлов А.С., Обнаружение неестественных текстов 25 Уровень ложно- положительных ошибок Полнота AUC

Сравниваемые алгоритмы Базовый алгоритм – не учитываем характеристики тематического разнообразия Улучшенный алгоритм – учитываем все признаки CASIA – победитель Web Spam Challenge 2008 (основывается на эвристиках) Linked LDA – лучший результат на WebspamUK Павлов А.С., Обнаружение неестественных текстов 26

Эксперименты на коллекции блогов Собран набор русскоязычных записей в блогах на сервисе Livejournal.com за октябрь-декабрь 2010 года: – 2189 оцененных экспертами записей – 587 (27%) – поисковый спам Павлов А.С., Обнаружение неестественных текстов 27 ТочностьПолнотаF-мера Базовый алгоритм 91%96%93% Улучшенный алгоритм 94%96%95%

Эксперименты на WebspamUK Павлов А.С., Обнаружение неестественных текстов 28 AUC CASIA0.848 Linked LDA0.854 Базовая версия0.847 Улучшенная версия0.870 Предложенный метод превосходит существующие аналоги Уровень ошибок на 11% ниже, чем у существующих аналогов Позволяет обрабатывать документы в потоков режиме

Основные результаты 1.Для решения задачи построения программных средств определения текстового спама разработан новый алгоритм обнаружения текстового спама на основе оценки разнообразия тематик документа. 2.Теоретически и численно обоснована применимость разработанного алгоритма и программной системы для обнаружения текстового спама, порожденного генераторами текстов на основе цепей Маркова, широко используемыми для создания поискового спама. 3.Разработан комбинированный алгоритм классификации текстового спама на основе анализа большого числа факторов, моделирующих связность, стиль, читаемость текстов, а также учета результатов алгоритма оценки разнообразия тематик документа. 4.Реализована программная система определения поискового спама. Получены более высокие характеристики классификации поискового спама на стандартном наборе данных, по сравнению с известными методами. Разработанная система позволяет обрабатывать документы в режиме близком к реальному времени Павлов А.С., Обнаружение неестественных текстов 29

Спасибо! Павлов А.С., Обнаружение неестественных текстов 30

Актуальность работы Поисковый спам – одна из основных проблем в поисковых системах (SIGIR 2002 г.) Отдельные секции на ведущих конференциях (WWW, SIGIR): – Более 20 различных модификаций алгоритмов за гг. Специализированная конференция – Adversarial Information Retrieval on the Web ( , 2011 гг.) Соревнования по обнаружению поискового спама – Web Spam Challenge (2007, 2008) Павлов А.С., Обнаружение неестественных текстов 31

Апробация результатов Основные результаты диссертации докладывались: – на одиннадцатой и тринадцатой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции"(2009 и 2011 г.); – на международной конференции "Диалог 2010"(2010 г.); – на седьмом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS)(2011 г.); – на семинаре Лаборатории анализа информационных ресурсов (2011 г.); – на аспирантском семинаре кафедры АСВК (2010 г.); Павлов А.С., Обнаружение неестественных текстов 32

Публикации В изданиях из списка ВАК: – Павлов А.С., Добров Б.В., Метод обнаружения массово порожденных неестественных текстов на основе анализа тематической структуры // Вычислительные методы и программирование: новые вычислительные технологии. Т. 12, Раздел –72. – Павлов А.С. Метод определения неестественных текстов на основе характеристик тематического разнообразия // Вестник ТвГУ. Серия «Прикладная математика». – Pavlov A.S., Dobrov B.V. Web Spam Detection through Text Diversity Analysis // Сборник трудов ИСП РАН. Прочие: – Павлов А.С., Добров Б.В. Методы обнаружения поискового спама, порожденного с помощью цепей Маркова // Тр. XI Всероссийской научной конференции Электронные библиотеки: перспективные методы и технологии, электронные коллекции. Петрозаводск, –317. – Павлов А. С. Исследование устойчивости метода обнаружения поискового спама на основе статистических характеристик. // Программные системы и инструменты. Тематический сборник 10, М.: Изд-во факультета ВМиК МГУ, С – Павлов А.С., Добров Б.В. Метод определения массово порождаемых неестественных текстов // Компьютерная лингвистика и интеллектуальные технологии: по материалам ежегодной Международной конференции «Диалог». Вып. 9(16). – М.: Изд-во РГГУ, – Pavlov A.S., Dobrov B.V. Detecting Content Spam on the Web through Text Diversity Analysis // Proceedings of The Seventh Spring Researchers Colloquium on Databases and Information Systems, SYRCoDIS Павлов А.С., Обнаружение неестественных текстов 33

Свойства порожденных текстов При генерации документов слова порождаются из каждого документа- образца, пропорционально его размеру В порожденном тексте «смешаны» все документы-образцы Нарушаются глобальные структуры естественного текста Павлов А.С., Обнаружение неестественных текстов 34

Тематическая структура Лингвистическая теория для тематик текста (ван Дейк 1988 г.): – Каждый осмысленный текст – это комбинация макроконцептов Формализация модели: – Каждому тексту соответствует линейная комбинация тематик Тематическая структура – распределение долей слов, принадлежащих каждой из K тематик – Лежит на K -мерном симплексе – Моделируется с помощью Скрытого распределения Дирихле (СРД) Павлов А.С., Обнаружение неестественных текстов 35

Нарушение тематической структуры в порожденных текстах Теорема. Пусть D templ набор документов-образцов для генератора текстов и задана тематическая структура каждого документа. Пусть на их основе обучен смешивающий генератор текстов и с помощью него порождается документ d gen длины l. Тогда с ростом l тематическая структура порожденного документа θ gen сходится по вероятности к усредненной тематической структуре документов-образцов: Павлов А.С., Обнаружение неестественных текстов 36

Критерии обнаружения неестественных текстов Критерий Пирсона (проверка гипотезы, что распределение тематик в документе равномерное) Параметр рангового распределения весов тематик Предложенные характеристики стремятся к 0: – при увеличении длины порожденного документа – при увеличении количества документов-образцов Эмпирически подтверждена применимость для обнаружения порожденных текстов Павлов А.С., Обнаружение неестественных текстов 37

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

Архитектура системы (2) Подсистема оценки параметров распределения СРД: – Реализует метод Монте-Карло для оценки параметров СРД (Gibbs sampling) Подсистема классификации: – Реализует предложенный алгоритм машинного обучения – Поддерживает режим параллельного перебора вариантов разбиений на многоядерных процессорах Павлов А.С., Обнаружение неестественных текстов 39

Генераторы текстов на основе цепей Маркова Порождаем последовательность слов, где каждое слово зависит только от N предыдущих Вероятности порождения собираем по тестовой коллекции При порождении сохраняется локальная связность текстов Проверялась эффективность данного метода опорных векторов позволяет формулировать критерии принадлежности спаму или неспаму Павлов А.С., Обнаружение неестественных текстов 40 эффективностьданного метода подхода

Применимость для различных генераторов текстов F-мера Базовая версияУлучшенная версия Мешок слов98 %99% ЦМ-2 Русский95%98% ЦМ-3 Русский93%97% ЦМ-2 Английский96%98% ЦМ-3 Английский93%97% Фрагменты92%96% Doorway.Su95%98% Rusadult98%99% Павлов А.С., Обнаружение неестественных текстов 41

Обзор существующих решений Методы обнаружения текстового спама: – Алгоритм на основе обнаружения редких пар слов – Алгоритм обнаружения текстового спама на основе эвристик – Метод на основе анализа тематик текста Методы обнаружения дубликатов: – Обнаружение дубликатов на основе сравнения векторов признаков – Шинглирование Методы обнаружения ссылочного спама: – TrustRank – Алгоритм обнаружения ссылочных ферм – Алгоритм на основе комбинации ссылочных признаков – Алгоритм обнаружения продажных ссылок Павлов А.С., Обнаружение неестественных текстов 42

Обработка тупиковых состояний Павлов А.С., Обнаружение неестественных текстов 43

Обобщенная модель генераторов текстов (2) Каждый из рассматриваемых генераторов можно представить в виде цепи Маркова с множеством состояний T = {t} = (d,m,v) : – d – документ-образец, из которого взято слово – m – номер слова в документе-образце – v – слово, которое находится в документе d на словопозиции m Для данной ЦМ существует единственное равновесное распределение: Павлов А.С., Обнаружение неестественных текстов 44

Скрытое распределение Дирихле (Latent Dirichlet Allocation) Порождающая модель для текстов: – Тематическая структура порождена распределением Дирихле – Позволяет эффективно оценивать тематическую структуру для коллекции текстов Пусть набор текстов удовлетворяет модели СРД, тогда документы, порожденные по этому набору не будут соответствовать модели СРД Павлов А.С., Обнаружение неестественных текстов 45

СРД: порождающий процесс Павлов А.С., Обнаружение неестественных текстов 46 Для каждого документа Вектор весов тематик (скрытый слой) Для каждого слова Тематика для данного слова (скрытый слой) Слово (наблюдаемые данные) Распределение Дирихле По конечным документам можно восстановить значения на скрытых слоях модели

СРД: пример Павлов А.С., Обнаружение неестественных текстов 47 Тематика 1 (вес 0.4): Наука Ученый Журнал Публикация Статья … Тематика 2 (вес 0.3): Биология Мозг Эволюция Отбор Вид … Тематика 3 (вес 0.3): Текст Читать Восприятие Описание Писать …

Сравнение методов машинного обучения ТочностьПолнотаF-мера C4.5 91,35%82,65%86,78% C4.5 prunning 90,07%87,8%88,92% C4.5 bagging 96,88%84,69%90,38% Support Vector Machine 72,9%74,83%73,85% Gradient Boosting Machine 99,42%97,36%98,37% Предложенный алгоритм 98,37%97,93%98,14% Павлов А.С., Обнаружение неестественных текстов 48

Устойчивость алгоритма Павлов А.С., Обнаружение неестественных текстов 49

Подсистема оценки параметров распределения СРД Применяется метод Монте-Карло для оценки параметров СРД (Gibbs sampling) Сценарии: Обучение модели СРД: – По набору естественных текстов определяются веса слов в тематиках (обучение без учителя) – На выходе формируется бинарное представление модели Оценка тематической структуры: – Для нового документа вычисляется K-мерный вектор его тематик – Сложность оценки тематической структуры O(|d|) Павлов А.С., Обнаружение неестественных текстов 50

Подсистема классификации Реализует предложенный алгоритм машинного обучения Поддерживает режим параллельного перебора вариантов разбиений на многоядерных процессорах Сценарии: – Обучение с учителем – Классификация Павлов А.С., Обнаружение неестественных текстов 51

Критерии обнаружения неестественных текстов Критерий Пирсона (проверка гипотезы, что распределение тематик в документе равномерное): Параметр рангового распределения весов тематик: Предложенные характеристики стремятся к 0 при увеличении длины порожденного документа и количества документов-образцов Павлов А.С., Обнаружение неестественных текстов 52

Исследование применимости для критерия Пирсона Павлов А.С., Обнаружение неестественных текстов 53