В данном посте мы рассмотрим современные подходы, применяемые для классификации текстов на естественном языке по их тематикам. Выбранные методы работы с документами определены общей сложной спецификой задачи – зашумлёнными обучающими выборками, выборками недостаточного размера или вообще отсутствующими выборками, сильным перекосом размеров классов и так далее. В общем – реальные практические задачи. Прошу под кат.
Решаемые задачи
Основных задач две – это бинарная классификация и мультиклассовая классификация. Бинарная классификация даёт нам ответ, интересен вообще этот документ, или он вообще не в тему и читать его не стоит. Здесь мы имеем перекос по размерам классов примерно 1 к 20, то есть – на один хороший документ приходится двадцать негодных. Но и сама обучающая выборка проблемная – в ней присутствуют шумы как по полноте, так и по точности. Шум по полноте – это когда не все хорошие, годные документы размечены как хорошие (FalseNegative), а шум по точности – когда не все размеченные хорошими документы на самом деле хорошие (FalsePositive).
Мультиклассовая классификация ставит перед нами задачу определить тематику документа и отнести его к одному из сотни тематических классов. Обучающая выборка по этой задаче сильно зашумлена по полноте, но довольно чиста по точности – всё таки разметка идёт только вручную, не как в первом случае – на эвристиках. Но зато, благодаря большому числу классов, мы начинаем наслаждаться сильными перекосами по количеству документов на класс. Максимальный зафиксированный перекос – более 6-ти тысяч. То есть, когда в одном классе документов больше, чем в другом, в 6-ть тысяч раз. Просто потому, что во втором классе лежит один документ. Единственный. Но это не самый большой из доступных перекосов, поскольку есть классы, в которых лежит ноль документов. Ну, ассесоры не нашли подходящих документов – вертись как знаешь.
То есть, наши проблемы таковы:
- Зашумлённые обучающие выборки;
- Сильные перекосы по размерам классов;
- Классы, представленные малым числом документов;
- Классы, в которых вообще документов нет (но работать с ними надо).
Решать эти задачи мы будем последовательно, разработав один классификатор – сигнатурный, потом другой – закрывающий слабые места первого – шаблонный, а потом отполируем это всё машинным обучением в виде xgboostи регрессии. И поверх этого ансамбля моделей накатим метод, закрывающий недостатки всех перечисленных – а именно метод работы без обучающих выборок вообще.
Дистрибутивная семантика (Word2Vec)
Гугль и Яндекс знают, какой пост показывать первым, когда люди спрашивают про Word2Vec. Поэтому дадим краткую выжимку из того поста и уделим внимание тому, о чём там не написано. Разумеется, есть другие хорошие методы в разделе дистрибутивной семантики – GloVe, AdaGram, Text2Vec, Seq2Vec и другие. Но каких-то сильных преимуществ по сравнению с W2V в них я не увидел. Если научиться работать с векторами W2V, можно получать удивительные результаты.
Word2Vec:
- Обучается без учителя на любых текстах;
- Ставит каждому токену в соответствие вектор действительных чисел, такой, что:
- Для любых двух токенов можно определить метрику* расстояния между ними (косинусная мера);
- Для семантически связанных токенов расстояние оказывается положительным и стремится к 1:
- Взаимозаменяемые слова (модель Skipgram);
- Ассоциированные слова (модель BagofWords).
* На самом деле – нет
Взаимозаменяемые слова
Enter word or sentence (EXIT to break): кофе
коффе 0.734483
чая 0.690234
чай 0.688656
капучино 0.666638
кофн 0.636362
какао 0.619801
эспрессо 0.599390
Ассоциированные слова
Enter word or sentence (EXIT to break): кофе
зернах 0.757635
растворимый 0.709936
чая 0.709579
коффе 0.704036
mellanrost 0.694822
сублемированный 0.694553
молотый 0.690066
кофейные 0.680409
Обобщение нескольких слов (A+B)
Enter word or sentence (EXIT to break): мобильный телефон
сотовый 0.811114
телефона 0.776416
смартфон 0.730191
телфон 0.719766
мобильного 0.717972
мобильник 0.706131
Проецирование отношений (A-B+С)
Найти такое слово, которое относится к украине так-же, как доллар относится к сша (то есть – что является валютой украины?):
Enter three words (EXIT to break): сша доллар украина
гривне 0.622719
долар 0.607078
гривны 0.597969
рубля 0.596636
Найти такое слово, которое относится к germany так-же, как франция относится к france (то есть – перевод слова germany):
Enter three words (EXIT to break): france франция germany
германия 0.748171
англия 0.692712
нидерланды 0.665715
великобритания 0.651329
Преимущества и недостатки:
Учится быстро на неподготовленных текстах:
- 1.5 месяца на 100 Гб обучающий файл, модели BagOfWords и Skipgram, на 24-х ядрах;
- Снижает размерность:
- 2.5 млн. токенов словарь ужимается до 256 элементов вектора действительных чисел;
- Векторные операции быстро деградируют:
- Результат сложения 3-5 слов уже практически бесполезен => неприменимо для обработки текстов;
Элементы вектора смысла не имеют, имеют смысл только расстояния между векторами => метрика между токенами одномерна. Этот недостаток самый обидный. Вроде-бы, имеем аж 256 действительных чисел, целый килобайт памяти занимаем, а по факту единственная нам доступная операция – сравнить этот вектор с другим таким-же, и получить косинусную меру как оценку близости этих векторов. Обработать два килобайта данных, получить 4-ре байта результата. И более ничего.
Семантический вектор
- Пример с кофе показывает, что токены группируются по смыслу (напитки);
- Необходимо сформировать достаточное число кластеров;
- Размечать кластеры нет необходимости.
Тогда, получим набор кластеров, в которых токены сгруппированы по смыслу, и, при необходимости, каждому кластеру можно присвоить метку => каждый кластер имеет независимый от других смысл.
Более подробно о построении семантического вектора рассказано в этом посте.
Сигнатура текста
Текст состоит из токенов, каждый из которых привязан к своему кластеру;
Можно подсчитать количество вхождений токена в текст и перевести в количество вхождений кластера в текст (сумма всех токенов, входящих в кластер);
В отличии от размеров словаря (2.5 млн. токенов), количество кластеров много меньше (2048) => работает эффект снижения размерности;
Перейдём от общего количества подсчитанных в тексте токенов к их относительному количеству (доле). Тогда:
- Доля не зависит от длины текста, а зависит только от частоты появления токенов в тексте => появляется возможность сравнивать тексты разной длины;
- Доля характеризует тематику текста => тематика текста определяется теми словами, которые используются;
Отнормируем доли конкретных текстов мат. ожиданием и дисперсией, вычисленными по всей базе:
Это повысит значимость редких кластеров (встречающихся не во всех текстах – например, названия) по сравнению с частыми кластерами (например – местоимения, глаголы и прочие связующие слова);
Текст определяется своей сигнатурой – вектором 2048 действительных чисел, имеющих смысл как нормированные доли токенов тематических кластеров, из которых составлен текст.
Сигнатурный классификатор
Каждому текстовому документу ставится в соответствие сигнатура;
Размеченная обучающая выборка текстов превращается в размеченную базу сигнатур;
Для исследуемого текста формируется его сигнатура, которая последовательно сравнивается с сигнатурами каждого файла из обучающей выборки;
Решение по классификации принимается на основе kNN (k ближайших соседей), где k=3.
Преимущества и недостатки
Преимущества:
Нет потерь информации от обобщения (сравнение идёт с каждым оригинальным файлом из обучающей выборки). Суть машинного обучения – найти какие-то закономерности, выделить их и работать только с ними – кардинально сокращая размеры модели по сравнению с размерами обучающей выборки. Истинные это закономерности или ложные, возникшие как артефакты процесса обучения или из-за недостатка обучающих данных – неважно. Главное в том, что исходная обучающая информация более недоступна – приходится оперировать только моделью. В случае сигнатурного классификатора мы можем себе позволить держать в памяти всю обучающаую выборку (не совсем так, об этом позже – когда пойдёт речь о тюнинге классификатора). Главное — мы можем определить, на какой именно пример из обучающей выборки похож наш документ более всего и подключить при необходимости дополнительный анализ ситуации. Отсутствие обобщения – суть отсутствие потерь информации;
Приемлемая скорость работы – порядка 0.3 секунды на прогон базы сигнатур в 1.7 млн. документов в 24 потока. И это без SIMD инструкций, но уже с учётом максимизации попаданий в кэш. И вообще – папа может в си;
Возможность выделять нечёткие дубликаты:
- Бесплатно (сравнение сигнатур и так происходит на этапе классификации);
- Высокая избирательность (анализируются только потенциальные дубли, составленные преимущественно из тех-же самых токенов, т.е. – имеющих высокую меру близости сигнатур);
- Настраиваемость (можно занизить порог срабатывания и получать не просто дубли, а тематически и стилистически близкие тексты);
Нормированность оценок (0;1];
Лёгкость пополнения обучающей выборки новыми документами (и лёгкость исключения документов из неё). Новые обучающие образы подключаются на лету – соответственно, качество работы классификатора растёт по мере его работы. Он учится. А удаление документов из базы хорошо для экспериментов, построения обучающих выборок и так далее – просто исключите из базы сигнатур сигнатуру данного конкретного документа и прогоните его классификацию – получите корректную оценку качества работы классификатора;
Недостатки:
Никак не учитывается взаимное расположение токенов (словосочетания). Понятно, что словосочетания – сильнейший классифицирующий признак;
Большие неснижаемые требования к оперативной памяти (35+ Гб);
Плохо (никак) не работает, когда на класс приходится малое количество образцов (единицы). Представим себе 256-ти мерную поверхность сферы… Нет, лучше не надо. Просто есть область, в которой должны располагаться документы интересующей нас тематики. Если в этой области довольно много точек – сигнатур документов из обучающей выборки – шансы новому документу оказаться близко с тремя из таких точек выше (kNN-же), чем если на всю область гордо горят 1-2 точки. Поэтому, шансы сработать есть даже с единственным положительным примером на класс, но шансы эти, понятное дело, реализуются не так часто, как хотелось-бы.
Точность и полнота (бинарная классификация)
Как вычислить оценку для бинарной классификации? Очень просто – берём среднее расстояние до 3-х лучших сигнатур из каждого класса (положительного и отрицательного) и оцениваем как:
Положительный/(положительный + отрицательный).
Поэтому большинство оценок лежат в очень узком диапазоне, а человекам, как обычно, хочется видеть цифры, интерпретируемые в качестве процентов. Что 0.54 – это очень хорошо, а 0.46 – очень плохо – объяснять долго и не продуктивно. Тем не менее графики выглядят хорошо, классический крест.
Тонкая настройка сигнатурного классификатора
Как видно из графика “точность и полнота” рабочая область классификатора достаточно узкая. Решение – разметить оригинальный текстовый обучающий файл, по которому учится Word2Vec. Для этого в текст документа внедряются метки, определяющие класс документа:
Как результат, кластеры располагаются в векторном пространстве не случайным образом, а разводятся так, что бы кластеры одного класса тяготели друг к другу и отстояли на максимальное расстояние от кластеров противоположного класса. Кластеры, характерные для обоих классов располагаются посередине.
Требования к памяти снижаются путём сокращения размеров базы сигнатур:
Сигнатуры обучающей выборки, содержащие излишнее количество образцов (более миллиона), последовательно кластеризуются на большое число кластеров и из каждого кластера используется одна сигнатура. Тем самым:
- Сохраняется относительно равномерное покрытие векторного пространства сигнатурами образцов;
- Удаляются сигнатуры образцов, излишне близких друг другу, и, соответственно, мало полезных для классификации.
Сигнатурный классификатор, резюме
- Быстрый;
- Легко дополняемый;
- Позволяет также обнаруживать дубликаты;
- Не учитывает взаимное расположение токенов;
- Не работает, когда в обучающей выборке мало примеров.
Шаблонный классификатор
Исправить недостатки сигнатурного классификатора призван классификатор на шаблонах. На нграммах, проще говоря. Если сигнатурный классификатор ставит тексту в соответствие сигнатуру и спотыкается, когда таких сигнатур мало, то шаблонный классификатор читает содержимое текста более вдумчиво и, если текст достаточно объёмен, даже единственного текста достаточно, что бы выделить большое количество классифицирующих признаков.
Шаблонный классификатор:
Основан на граммах длиной до 16-ти элементов:
Часть целевых текстов оформлена по стандартам (ISO). Есть много типовых элементов:
- Заголовки;
- Подписи;
- Листы согласования и архивные метки;
Часть целевых документов содержат в себе информацию по оформлению:
- Xml (включая все современные офисные стандарты);
- Html;
Практически все содержат устойчивые словосочетания, например:
- “строго конфиденциально, перед прочтением сжечь”;
Является упрощённой реализацией Наивного Баессового классификатора (без нормировки);
Генерит до 60-ти млн. классифицирующих грамм;
Работает быстро (конечный автомат).
Построение классификатора
Из текстов выделяются граммы;
Вычисляется относительная частота грамм на класс;
Если для разных классов относительная частота сильно отличается (в разы) грамма является классифицирующим признаком;
Редкие граммы, встреченные 1 раз, отбрасываются;
Обучающая выборка классифицируется, и по тем документам, по которым классификация была ошибочна, формируются дополнительные граммы, и добавляются в общую базу грамм.
Использование классификатора
Из текста выделяются граммы;
Суммируются веса всех грамм для каждого класса, к которому они относятся;
Побеждает класс, набравший наибольшую сумму весов;
При этом:
- Класс, в котором было больше обучающих текстов, формирует обычно больше классифицирующих грамм;
- Редкий класс (мало обучающих текстов) генерит мало грамм, но их средний вес выше (из-за преобладания длинных уникальных для данного класса грамм);
- Текст, в котором нет явного преобладания редких длинных грамм, будет отнесён к классу с большим числом обучающих примеров (апостериорное распределение стремится к априорному). Так работает оригинальный наивный Баесс и вообще все универсальные классификаторы;
- Текст, имеющий длинные уникальные граммы редкого класса, будет отнесён скорее к данному редкому классу (намеренно внесённое искажение в апостериорное распределение с целью повысить избирательность на редких классах). Деньги платят за результат, и чем труднее получить результат, тем больше денег. Это понятно. Самый трудный результат – это как раз редкие тематические классы. Поэтому имеет смысл исказить свой классификатор таким способом, что бы лучше искать редкие классы, пусть и проседая в качестве на больших, попсовых классах. В конце концов, с попсовыми классами прекрасно справляет сигнатурный классификатор.
Преимущества и недостатки
Преимущества:
- Относительно быстрый и компактный;
- Неплохо параллелится;
- Способен обучаться по единственному документу в обучающей выборке на класс;
Недостатки:
- Оценки ненормированы и в оригинальном виде не обеспечивают критерий pairwize (нельзя гарантировать, что оценка с большим весом более вероятна);
- Генерится огромное количество грамм с околонулевой вероятностью встретить их в реальных документах (не дублях). Но зато, встретив такую редкую грамму в документе, можно об этом документе сразу сказать много интересного. А памяти на сервере хватает – это не проблема;
- Огромные требования к памяти на этапе обучения. Да, нужен кластер, но их есть у нас (смотри поскриптум к данному посту).
Ненормированность оценок
Почему:
Нет необходимости делать нормировку – сильное упрощение кода;
Ненормированные оценки содержат больше потенциально доступной для классификации информации.
Как использовать:
Оценки классификатора являются хорошими признаками для использования в универсальных классификаторах (xgboost, SVM, ANN);
При этом, универсальные классификаторы сами определяют оптимальную величину нормировки.
Итоговый обобщённый классификатор (мультикласс)
Ответы сигнатурного и шаблонного классификаторов объединяются в единый вектор признаков, который подвергается дополнительной обработке:
- Нормировка оценок к единице, для получения их относительной доли на класс;
- Группировка редких классов для получения достаточного числа обучающих примеров на группу;
- Взятие разности групповых оценок для получения более пологой поверхности для градиентного спуска.
По результирующему вектору признаков строится модель xgboost, дающая прирост точности в пределах 3% к точности оригинальных классификаторов.
Бинарный обобщённый классификатор
Суть регрессия от:
- Сигнатурного классификатора:
- Шаблонного классификатора:
- XgBoost на выходах сигнатурного и шаблонного классификатора.
Критерий оптимизации – максимум площади под произведением полноты на точность на отрезке [0;1] при этом, выдача классификатора не попадающая в отрезок считается ложным срабатыванием.
Что даёт:
Максимизирует рабочую область классификатора. Человеки видят привычную оценку в виде процентов, от нуля до ста, при этом, эта оценка ложится так, что бы максимизировать и полноту и точность. Понятно, что максимум произведения находится в области креста, где и полнота и точность не обладают слишком маленькими значениями, а вот области справа и слева, где высокая полнота умножается на никакую точность и где высокая точность умножается на никакую полноту – неинтересны. За них денег не платят;
Отбрасывает часть примеров в область ниже нуля => является сигналом, что классификатор не в состоянии отработать данные примеры => классификатор даёт отказ. С инженерной точки зрения это вообще отличная способность – классификатор сам честно предупреждает, что да, в отброшенном потоке есть 1-2% хороших документов, но сам классификатор с ними работать не умеет – используйте другие методы. Или смиритесь.
Бинарный обобщённый классификатор, 1:20
Шикарный график, особенно радует завал справа. Напоминаю, что у нас тут соотношение положительных примеров в потоке в двадцать раз меньше, чем отрицательных. Тем не менее, график полноты выглядит вполне канонично – выпукло-вогнутый с точкой перегиба посередине, в районе 0.3. Почему это важно, покажем дальше.
Бинарный обобщённый классификатор, 1:20, Анализ
Полнота начинается с 73% => 27% всех положительных примеров не могут быть эффективно отработаны классификатором. Эти 27% положительных примеров оказались в области ниже нуля именно из-за проводимой оптимизации регрессии. Для бизнеса лучше сообщить, что не умеем работать с этими документами, чем дать на них ложноотрицательные срабатывания. Зато рабочая область классификатора начинается с почти 30% точности – а это те цифры, которые уже нравятся бизнесу;
Наличествует завал точности от 96% до 0% => в выборке есть порядка 4% примеров, размеченных как негативные, хотя на самом деле они позитивные (проблема полноты разметки);
Явно видны пять областей:
- Область отказа классификатора (менее нуля);
- две квазилинейные области;
- Область насыщения (максимальная эффективность);
- Область завала (проблема полноты разметки).
Деление на области даёт возможность разработать дополнительные средства классификации для каждой из областей, особенно для 1-й и 5-й.
Бинарный обобщённый классификатор, 1:182
Тут мы решаем ту же задачу бинарной классификации, но при этом на один положительны пример приходится уже 182 отрицательных.
Бинарный обобщённый классификатор, 1:182, Анализ
Полнота начинается с 76% => 24% всех положительных примеров не могут быть эффективно отработаны классификатором;
12% всех положительных примеров однозначно узнаются классификатором (100% точность);
Явно видны четыре области:
- Область отказа классификатора (менее нуля);
- две квазилинейные области;
- Область 100% точности.
График полноты вогнут без точек перегиба => классификатор обладает высокой избирательностью (соответствует правой части классического графика полноты с точкой перегиба посередине).
Построение классификатора для классов, у которых нет обучающих примеров
Реальность такова, что существует достаточно большое количество классов, к которым не размечено ни одного документа, и единственная доступная информация – это сообщение Заказчика, какие именно документы он желает классифицировать в данный класс.
Построение обучающей выборки вручную невозможно, поскольку на 1.7 млн. имеющихся в базе документов можно ожидать только несколько документов, подпадающих под данный класс, а возможно – и не одного.
Класс “Маркетинговые исследования косметики”
Из анализа названия класса мы видим, что Заказчику интересны документы, имеющие отношение к “Маркетинговые исследования” и “Косметика”. Для обнаружения таких документов необходимо:
Сформировать семантическое ядро из текстов по заданным тематикам, при этом, на всех представляющих интерес языках;
Найти те тематики, которые не имеют отношения к заданному классу – их использовать в качестве негативных примеров (например – политика);
Найти в базе документов несколько образцов документов, которые имеют частичное либо точное отношение к заданному классу;
Разметить найденные документы силами ассесоров Заказчика;
Построить классификатор.
Сборка семантического ядра текстов.
Идём в википедию и находим статью которая называется, как ни странно,“маркетинговые исследования”. Внизу там есть неприметная ссылочка «категории». В категориях даны все статьи Википедии по данной тематике и вложенные категории со своими статьями. В общем – богатый источник тематических текстов.
Но и это не всё. Справа в меню лежат ссылки на аналогичные статьи и категории на других языках. Тексты той-же тематики, но на интересующих нас языках. Или на всех подряд – классификаторы сами разберутся.
Использование семантических ядер
У нас есть три тематики:
- Маркетинговые исследования;
- Косметика;
- Политика.
Используем шаблонный классификатор на данные три класса. Обработаем все документы в базе документов и получим:
- Маркетинговые исследования 20%;
- Косметика 6%;
- Политика 74%.
Данные доли не показывают фактическое распределение документов по тематикам, они показывают только средние веса признаков каждого класса, выделенных шаблонным классификатором.
Однако, если исследуется документ, имеющий распределение долей 30%, 20%, 50% о таком документе можно утверждать, что он содержит больше признаков текста с заданными тематиками против негативной тематики (политика), соответственно – данный текст потенциально интересен:
Результаты поиска документов
В результате обработки всей базы документов было выделено ~80 документов, из которых: Два оказались имеющими полное соответствие классу:
- не были найдены ранее при обработке документов вручную;
- На разных языках, отличных от языка точки входа в семантическое ядро (русского);
~36 % всех найденных документов имеют частичное отношение к классу;
Остальные не имеют отношения к классу вообще.
Важно, что в результате оценки получена размеченная выборка ~80 документов, содержащих как позитивные, так и негативные примеры.
Построение классификатора
Более 60% ложных срабатываний сигнализируют о том, что одной политики в качестве негативного примера недостаточно.
Решение:
Найти автоматическим способом другие тематики текстов, которые могут использоваться в качестве негативных и, потенциально, позитивных примеров. Для этого:
Сформировать автоматически наборы текстов на большое количество тематик и выделить те из них, что коррелируют (негативно или положительно) с размеченной выборкой ~80 документов.
Онтология DBPedia
Если кто-то ещё не знает, вся Википедия уже любезно распаршена и разложена по файликам в формате RDF. Бери и пользуйся. Представляют интерес:
- ShortAbstracts – краткая аннотация статьи;
- LongAbstracts – длинная аннотация статьи;
- Homepages – ссылки на внешние ресурсы, домашние страницы;
- Article Categories – категория страницы;
- Categorylabels – читаемые названия категорий;
- Externallinks – ссылки на внешние ресурсы по теме;
- Interlanguagelinks – Эта же статья на других языках.
Стоит помнить, что в качестве источника текстов для машинной лингвистики DBPedia не заменяет Википедию, так как размер аннотации обычно – 1-2 параграфа, и ни в какое сравнение не идёт с большинством статей по объёмам. Но никто не запрещает выкачать понравившиеся статьи и их категории из Википедии в дальнейшем, правильно?
[Ожидаемые] результаты поиска коррелированных тематик в DBPEdia
Результатом поиска коррелированных тематик будут являться:
- Наборы текстов на всех языках по заданным тематикам;
- Оценка степени коррелированности текстов по отношению к классу;
- Человекочитаемое (словестное) описание тематик.
При этом, коррелированные тематики зависят не только от класса “Маркетинговые исследования косметики”, но и от тематик документов, содержащихся в базе (для тематик с отрицательной корреляцией). Что позволяет использовать найденные тематики:
- для ручного построения классификаторов на другие темы;
- как дополнительные признаки для текстов, классифицируемых итоговым обобщённым классификатором;
- Для создания дополнительных измерений метрик подобия текстов в векторном пространстве сигнатурного классификатора: тут я отсылаю к своей статье в сборнике Диалога 2015 года по обучению по аналогии в смешанных онтологических сетях. И к соответствующему посту.
Постскриптум
Данный пост показал те технологии, которые мы используем в настоящий момент и куда мы планируем двигаться в дальнейшем (а это онтологии). Пользуясь случаем хочу сказать, что в мою группу набираем людей, начинающих/продолжающих изучать машинную лингвистику, особенно рады студентам/выпускникам сами знаете каких вузов.