Мы поговорим об использовании модных «Word embedding» не совсем по назначению — а именно для исправления опечаток (строго говоря, и ошибок тоже, но мы предполагаем, что люди грамотные и опечатываются). На хабре была довольно близкая статья, но здесь будет немного о другом.


Визуализация Word2Vec модели, полученная студентом. Обучалась на «Властелине колец». Явно что-то на черном наречии.

Постановка задачи

Дано: Словарь (множество слов).
Необходимо: Для входного слова с опечаткой (которого может и не быть в словаре) найти ближайшие слова из словаря на основе заранее заданной метрики. Эти найденные слова и являются вариантами исправления входного слова.

Теоретический ликбез

Для нашей задачи нам понадобится Word Embedding, или векторное представление слов (по поводу перевода термина до сих пор есть сомнения у русскоязычного сообщества), и снова на хабре есть замечательная статья, которая хорошо рассказывает об этом. Чтобы не повторяться, но и не гонять читателя по ссылкам — краткий экскурс в тему.

Word embedding — это векторное представление слов, то есть одному слову сопоставляется вектор фиксированной размерности, например, для условного слова «дом» — [0.1, 0.3, ..., 0.7]. Важное замечание: обычно размерность вектора значительно меньше размерности словаря, иначе это вырождается в one-hot encoding.

Количество элементов вектора зависит от многих условий: выбранного метода, требований задачи, погоды в Красноярске и многого другого. В текущих SotA реализациях это 100-500 значений (чаще 300).

Векторы получаются в процессе обучения, для этого алгоритму скармливается какой-то текст или тексты (от художественных произведений до дампа википедии), и для каждого слова итеративно высчитывается вектор.

Есть различные методы получения этих векторов, самые популярные сейчас это Word2Vec, GloVe, WordRank и FastText.

Если коротко, то в основе лежит идея: слова, контексты которых похожи — скорее всего имеют схожие значения. Отсюда следует каким образом исправляются опечатки в первом приведенном примере. То есть у нас есть два предложения: «найти туры с преключениями» и «найти туры с приключениями», контексты похожи, следовательно, слова «преключениями» и «приключениями» по смыслу похожи (это грубое приближение, но смысл такой).

У такого подхода исправления опечаток, кроме очевидных достоинств, есть один важный недостаток — все варианты ошибок, которые мы можем исправить, должны быть в тексте, на котором мы обучаемся. То есть мы не можем получить вектор для слова, которое раньше не встречали.

Все (известные автору) современные методы получения векторов слов, кроме FastText, оперируют словами как неделимыми сущностями (слово заменятся целочисленным индексом, и потом идет работа с индексом). В FastText (если еще точнее, то в его дополнении) добавлено интересное предложение: а давайте считать эти вектора не для слов целиком, а для n-грамм из символов. Например, слово «стол» (с добавленными символами начала и конца слова, вроде "<стол>") преобразуется в следующий список: 3-граммы: <ст, сто, тол, ол>; 4-граммы: <сто, стол, тол>. Авторы предлагают использовать n-граммы от 3 до 6 включительно, не будем с ними спорить. Тогда результирующий вектор слова равен сумме векторов составляющих его n-грамм:

$$

где
$$ — множество всех n-грамм слова,
$$ — вектор соответствующей n-граммы,
$$ — вектор слова.

Какие важные изменения сулит нам этот подход?

Во-первых, авторы ввели это, чтобы лучше работало на языках с богатой морфологией (каким является русский). И действительно, морфологические изменения теперь меньше влияют на расстояние между словами, вот вам табличка для разных языков из той же статьи в качестве пруфов:

Язык	Датасет	Sg	CBOW	sisg-	sisg
Ar	WS353	51	52	54	55
De	Gur350	61	62	64	70
De	Gur65	78	78	81	81
De	ZG222	35	38	41	44
En	RW	43	43	46	47
En	WS353	72	73	71	71
Es	WS353	57	58	58	59
Fr	RG65	70	69	75	75
Ro	WS353	48	52	51	54
Ru	HJ	59	60	60	66

Корреляция между экспертной оценкой и оценкой метода. SG и CBOW — соответственно skip-gram и continious bag of words варианты Word2Vec, sisg- — когда неизвестные слова заменяем нулевым вектором, и sisg — когда неизвестные слова заменяем на сумму их n-грамм.

Во-вторых, это немного шаг назад, в Word2Vec мы отходили от буквенного представления слова, пытаясь сблизить слова вроде «царь» и «король», «мама» и «сын», сейчас же мы возвращаемся к «буквенной близости», что для семантической задачи может и не очень хорошо, но для нашего варианта (напомню — исправление опечаток) это то что надо.

На этом теоретическая часть закончена, перейдем к практике.

Практический полигон

Введем некоторые предусловия:

1. Для тестов возьмем сравнительно небольшой текст, а именно какое-нибудь художественное произведение, например, «Тихий Дон» Шолохова. Почему так? Это будет проще повторить заинтересованному читателю и, осознавая контекст произведения, мы сможем объяснить поведение нашего метода. В общем случае, векторные представления слов обучаются на больших корпусах языка, таких как дампы Википедии.
2. Нормализуем слова перед обучением, то есть приведем их в нормальную форму (например, для существительных это единственное число и именительный падеж). Это сильное упрощение, чтобы не возиться с окончаниями и увеличить частоту встречаемости слов для более адекватных векторов (именно для этого в первую очередь обучают на больших корпусах, чтобы получить как можно больше употреблений для каждого слова).

Реализация

Тестовый код достаточно простой (спасибо, gensim), весь скрипт есть здесь, непосредственно обучение модели в одну строчку:

model = gensim.models.FastText(sentences, size=300, window=3, min_count=2, sg=1, iter=35)

Небольшие пояснения:
sentences — список списков, каждый элемент — предложение, каждый элемент предложения — слово;
size — размер выходных векторов;
window — размер окна, слова в пределах окна мы считаем контекстом для слова в центре;
min_count — учитывать только слова, которые встречаются хотя бы 2 раза;
sg — использовать skip-gram вариант, а не CBOW;
iter — количество итераций.

Кроме того, есть два параметра, которые оставлены по умолчанию, их значение обсуждали выше, но вы можете с ними поиграться: min_n и max_n — нижний и верхний пороги, какие n-граммы брать (по умолчанию от 3 до 6 символов)

Мера сходства

В качестве метрики возьмем ставшую уже классической в этой задачи меру сходства между векторами Cosine similarity, которая принимает значения от 0 до 1, где 0 — векторы абсолютно разные, 1 — векторы одинаковые:

$$

где $$ и $$ — компоненты соответствующих векторов.

Эксперименты

Итак, мы разобрались с тем что у нас есть, и чего мы хотим, на всякий случай еще раз:

1. Гипотеза состоит в том, что на основе векторного представления слов мы можем исправлять опечатки.
2. У нас есть обученная FastText модель всего лишь на одном произведении, слова в ней нормализованы, также мы можем получить вектор для неизвестных слов.
3. Способ сравнения слов, а точнее их векторов, определен в предыдущем пункте.

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

Сводная таблица с результатами:

Слово с опечаткой	Задуманное слово	№ в списке ближайших	Значение метрики
челавек	человек	1	0.88227
стулент	студент	10	0.67878
студечнеский	студенческий	1	0.85078
чиловенчость	человечность	1	0.75012
учавствовать	участвовать	6	0.87767
тактка	тактика	2	0.73543
вообщем	вообще	(1)	0.96243
симпотичный	симпатичный	(1)	0.92399
зделать	сделать	2	0.91553
сматреть	смотреть	1	0.80055
алгаритм	алгоритм	(1)	0.86162
ложить	положить	10	0.81719

Замечания:

1. Если № указан в скобках, то это значит, что слова нет в словаре, но оно могло бы быть на этом месте (на основе метрики).
2. С парой ложить-положить на самом деле все не так плохо, так как слова выше это «сложить», «отложить», «выложить» и т.д. (см. спойлер).
3. Иногда в топе похожих слов есть слова, сильно отличающиеся от запросов (стулент — шофер), предположительно это связано со своего рода коллизией векторов — когда для разных n-грамм получаются примерно одинаковые вектора.

Заключение

Использование векторного представления несомненно может помочь в задаче исправления опечаток/ошибок, но в одиночку его использовать достаточно опасно, так как иногда (хоть и редко) возникают сильные ошибки.

По сути это еще одна метрика сравнения двух строк на схожесть, но уже уровнем выше, чем, например, то же расстояние Дамерау — Левенштейна. Использование FastText как дополнение к другим методам вполне может повысить качество исправления опечаток.