Мешок слов и TF-IDF

У нас есть идентификаторы токенов и способ измерить качество классификатора. Задача этой заметки конкретна: 120 000 новостных статей, четыре темы (World, Sports, Business, Sci/Tech) и модель, которая приписывает тему новой статье. Линейному классификатору нужен вектор фиксированной длины для каждого документа, а документы имеют разную длину. Простейший способ получить вектор фиксированной длины — полностью забыть о порядке и считать.

Обозначения. $V$ — словарь из $|V|$ записей, $D$ — обучающий корпус из $|D|$ документов. $N(t, d)$ — число вхождений токена $t$ в документ $d$; $\mathrm{df}(t) = |\{d \in D : t \in d\}|$ — число документов, содержащих $t$. Документ представлен вектором $x_d \in \mathbb R^{|V|}$.

Отправная точка: подсчёт токенов#

Представление мешок слов (bag of words) задаёт

$$(x_d)_t = N(t, d) \qquad \text{для всех } t \in V.$$

Документ становится вектором, координата которого для каждой записи словаря равна числу её вхождений. Порядок слов отбрасывается: «dog bites man» и «man bites dog» получают один и тот же вектор. Остаётся то, какие токены встречаются и как часто, и для классификации по темам это бо́льшая часть сигнала: статья о футбольном матче содержит match, goal и coach, в каком бы порядке ни шли предложения.

Размерности показывают цену. Со словарём AG News из заметки о предобработке $|V| = 29\,350$, и обучающая матрица $X$ имеет форму $120\,000 \times 29\,350$. В плотном виде это было бы $3.5 \times 10^9$ элементов; в разреженном — совсем немного, потому что у статьи из 40 различных токенов 40 ненулевых координат из 29 350. Всё в этой заметке работает с разреженными матрицами.

Линейный классификатор на счётчиках#

Многоклассовая логистическая регрессия отображает вектор в одну оценку на класс и нормирует оценки через softmax:

$$z = W x_d + b, \qquad W \in \mathbb R^{K \times |V|},\; b \in \mathbb R^K, \qquad p(y = k \mid d) = \frac{e^{z_k}}{\sum_{j=1}^K e^{z_j}}.$$

Строка $k$ матрицы $W$ содержит по одному весу на запись словаря; положительный вес goal в строке Sports повышает оценку Sports всякий раз, когда в статье встречается goal, пропорционально числу вхождений. Модель обучается минимизацией кросс-энтропии истинной метки относительно предсказанного распределения, усреднённой по корпусу:

$$\mathcal L = -\frac{1}{|D|}\sum_{d \in D} \log p(y_d \mid d).$$

Почему функция потерь именно такая и как она связана с энтропией и KL-дивергенцией, выведено в курсе по генеративным моделям; заметка об n-граммах повторяет четыре эквивалентные формы для случая языковой модели. Пока достаточно того, что минимизация $\mathcal L$ максимизирует правдоподобие обучающих меток.

Разобранный пример#

Три однострочных документа и словарь из пяти слов:

	cat	dog	sat	ran	fast
$d_1$ = «the cat sat»	1	0	1	0	0
$d_2$ = «the dog ran fast»	0	1	0	1	1
$d_3$ = «the cat ran fast fast»	1	0	0	1	2

the удалено как стоп-слово. У $d_3$ в столбце fast стоит 2, потому что токен встречается дважды. Классификатор, которому нужно отделить статьи «о животных» от статей «о движении», может поставить положительные веса на sat/cat/dog в одной строке и на ran/fast в другой; $d_3$, где смешано и то и другое, получает оценку, зависящую от счётчиков.

Где сырые счётчики не работают#

Векторы счётчиков искажают два эффекта.

Длина. У длинного документа счётчики больше, чем у короткого на ту же тему, поэтому его вектор длиннее, а оценки $z = Wx$ масштабируются вверх. Уверенность классификатора тогда измеряет длину, а не свидетельства.

Частые токены. Даже после удаления стоп-слов некоторые токены есть в большинстве документов корпуса: в новостном корпусе это said, year, new. Их счётчики велики, поэтому они доминируют в скалярных произведениях $Wx$, ничего не говоря о теме. Токен, который есть в каждом документе, самим своим присутствием ничего не говорит. Его счётчик всё ещё может различаться между классами (один раз на статью в одной теме, десять раз — в другой), но такие токены обычно мало говорят о теме. IDF понижает их вес по фиксированному правилу, которое не смотрит на метки; обученный классификатор тоже может выучить для них малые веса.

TF-IDF: перевзвешивание счётчиков#

Частота термина (term frequency) — это счётчик, в некоторых вариантах нормированный на длину документа:

$$\mathrm{tf}(t, d) = \frac{N(t, d)}{\sum_{k \in V} N(k, d)}.$$

Обратная документная частота (inverse document frequency) измеряет, насколько токен редок среди документов:

$$\mathrm{idf}(t) = \log\frac{|D|}{\mathrm{df}(t)}.$$

У токена, который есть в каждом документе, $\mathrm{df}(t) = |D|$ и $\mathrm{idf} = \log 1 = 0$: он выключается. У токена, который есть в одном документе из тысячи, $\mathrm{idf} = \log 1000 \approx 6.9$. Логарифм сжимает диапазон, так что токен из 1% документов не в 100 раз важнее токена из 100% документов, а важнее на $\log 100 \approx 4.6$ единицы. Произведение

$$\text{tf-idf}(t, d) = \mathrm{tf}(t, d)\cdot \mathrm{idf}(t)$$

и есть новая координата. Результаты ниже получены реализацией scikit-learn, которая отличается тремя деталями, важными при воспроизведении чисел: в качестве tf она берёт сырой счётчик $N(t, d)$; она сглаживает idf как $\log\frac{1 + |D|}{1 + \mathrm{df}(t)} + 1$ — как будто есть ещё один документ, содержащий все токены, — так что ни один вес не бесконечен, а прибавленная единица оставляет токену, который есть в каждом документе, вес 1 вместо 0; и она нормирует вектор каждого документа к единичной евклидовой норме, что напрямую убирает эффект длины и делает деление счётчиков на длину ненужным.

Разобранный пример, продолжение#

Для трёх документов выше $|D| = 3$. Документные частоты: cat 2, dog 1, sat 1, ran 2, fast 2. По простому определению $\mathrm{idf}(\text{cat}) = \ln(3/2) = 0.405$, $\mathrm{idf}(\text{dog}) = \ln 3 = 1.099$. Для $d_3$ (пять токенов вместе с the, четыре после удаления стоп-слов):

Токен	$N(t, d_3)$	$\mathrm{tf}$	$\mathrm{idf}$	tf-idf
cat	1	0.25	0.405	0.101
ran	1	0.25	0.405	0.101
fast	2	0.50	0.405	0.203

Если бы fast встречалось во всех трёх документах, его idf был бы равен 0, и самый большой счётчик в векторе ничего бы не дал. Перевзвешивание делает то, что мы просили: счётчики по-прежнему важны, но только для токенов, которые различают документы.

Весь метод на трёх документах — от счётчиков до классификатора:

Рисунок

От счётчиков через TF-IDF к линейной модели

Результаты на AG News#

Конвейер такой: обучить векторизатор на обучающих текстах (словарь и idf), преобразовать обе части, обучить логистическую регрессию, измерить долю правильных ответов (accuracy).

Признаки	Словарь	Доля верных (обучение)	Доля верных (тест)
TF-IDF, униграммы, min_df=4, max_df=0.95	29 350	0.940	0.918
TF-IDF, 1–3-граммы, min_df=10, max_df=0.95	101 284	0.951	0.920

Словарь формируют два отсечения по частоте. min_df=4 отбрасывает токены, встреченные меньше чем в четырёх обучающих документах: они слишком редки, чтобы оценить для них вес, и это в основном опечатки и имена; max_df=0.95 отбрасывает токены, встречающиеся более чем в 95% документов, которые idf и так почти обнулил бы.

Вторая строка добавляет n-граммы: идущие подряд пары и тройки токенов как дополнительные записи словаря. Это стандартное частичное решение проблемы порядка: not done становится отдельным признаком, отличным от not и done. Цена — размер словаря. При $|V|$ униграммах биграмм может быть до $|V|^2$, поэтому отсечение по частоте приходится поднять (min_df=10), чтобы матрица оставалась обозримой, а выигрыш здесь — 0.2 пункта, в пределах выборочной погрешности тестовой выборки из 7600 примеров: одна стандартная ошибка доли правильных ответов около 0.92 равна $\sqrt{0.92 \cdot 0.08 / 7600} \approx 0.003$, то есть 0.3 пункта. На этом корпусе тему несут отдельные токены, и биграммы мало что добавляют.

Разрыв в 2–3 пункта между долей правильных ответов на обучении и на тесте — умеренное переобучение: при 29 350 весах на класс и 120 000 документах модель может запомнить часть токенов, характерных только для обучающей выборки.

Что изменилось#

	Мешок слов	TF-IDF
Координата	$N(t, d)$	$\mathrm{tf}(t,d)\cdot\mathrm{idf}(t)$, вектор нормирован
Частые токены	Доминируют	Вес понижен почти до 0
Длина документа	Масштабирует вектор	Убрана нормировкой
Порядок слов	Игнорируется	Игнорируется (n-граммы возвращают соседние пары)
Стоимость	Одна разреженная матрица	То же плюс один проход для idf

Представление по-прежнему — разреженный вектор счётчиков; изменилось взвешивание, и одного этого хватает, чтобы линейная модель стала конкурентоспособной. Доля правильных ответов 0.92 на тесте — число, которое стоит запомнить: в заметке о CNN свёрточные сети поверх векторов слов достигают 0.90–0.91, ниже этого базового уровня, и только дообученный предобученный трансформер явно превосходит его в заметке о переносе обучения.

Ограничения#

• Нет порядка дальше n-грамм. «The film was not bad, it was great» и «the film was not great, it was bad» имеют почти все униграммы и биграммы общими.
• Нет сходства между токенами. cat и dog — ортогональные координаты; вес, выученный для одного, ничего не говорит о другом. Каждый токен должен встретиться при обучении достаточно часто, чтобы получить собственный вес. Ответ на это — заметка о векторах слов.
• Открытый словарь. У токена, которого не было в обучающей выборке, нет координаты, и при тестировании он молча отбрасывается.
• Размерность. $|V|$ координат на документ и $|V|^2$ с биграммами; представление не сжимает.
• Тема, а не смысл. Метод работает там, где метку можно предсказать по тому, какие слова встречаются. Он не может ответить на вопрос, перевести текст или сказать, кто что сделал с кем.

Что нужно запомнить#

• Мешок слов: документ — вектор счётчиков его токенов. Порядок отбрасывается; матрица разреженная.
• Линейный классификатор на этих счётчиках, обученный с кросс-энтропией, — сильный базовый уровень для классификации по темам.
• TF-IDF умножает каждый счётчик на $\log(|D|/\mathrm{df}(t))$, выключая токены, которые встречаются везде, и нормирует вектор, чтобы погасить влияние длины.
• Словарь и idf обучаются только на обучающих данных.
• AG News: 0.918 правильных ответов на тесте с униграммами, 0.920 с 1–3-граммами. Нейросетевые модели из следующих заметок должны превзойти 0.92, чтобы оправдать свою цену.

Ноутбук#

week01_word_embeddings.ipynb. Номера ячеек считают все ячейки, включая текстовые, начиная с 1. Приведённые числа взяты из прогона, сохранённого в курсе; у ячеек, изменённых с тех пор под текущие версии библиотек, сохранённого выхода нет.

• Ячейки 33–36 загружают AG News (120 000 обучающих и 7600 тестовых примеров, столбцы text и label, разделённые табуляцией); ячейка 38 строит сбалансированную гистограмму классов.
• Ячейки 42–43 приводят использованные выше формулы tf и idf.
• Ячейки 44–48 обучают TfidfVectorizer(min_df=4, max_df=0.95) на обучающих текстах, преобразуют обе части (обучающая матрица имеет форму (120000, 29350)), обучают LogisticRegression(max_iter=500) и печатают долю правильных ответов 0.94 на обучении и 0.918 на тесте.
• Ячейки 49–52 повторяют то же с ngram_range=(1, 3) и min_df=10: 0.951 на обучении, 0.92 на тесте. Размер этого словаря ноутбук не печатает; 101 284 получено отдельным обучением того же векторизатора.

Дальше#

Подсчёт токенов отвечает на вопрос «о чём этот документ». Он не может ответить на вопрос «что дальше», а это вопрос, стоящий за каждой генеративной моделью курса. Следующая заметка сохраняет подход подсчёта, но считает короткие последовательности токенов, что даёт первую языковую модель, способ порождать текст и метрику (перплексию), по которой измеряется каждая следующая языковая модель.

Литература#

• K. Spärck Jones. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1), 1972. Взвешивание idf.
• C. D. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. §6.2 (tf-idf) и §13 (классификация текстов).
• D. Jurafsky, J. H. Martin. Speech and Language Processing, 3rd ed. draft. Глава 5 (логистическая регрессия для текстов).
• scikit-learn developers. TfidfVectorizer и Feature extraction, §6.2.3.4. Сглаженный idf и нормировка L2, использованные в ноутбуке.
• X. Zhang, J. Zhao, Y. LeCun. Character-level Convolutional Networks for Text Classification. NeurIPS, 2015. Бенчмарк AG News; в таблице 4 приведены базовые уровни мешка слов и TF-IDF того же порядка, что и выше.