Kwent May 23 2018 at 09:18

Исправление опечаток, взгляд сбоку

7 min

9.8K

Singularis corporate blogPython*Semantics*Data Mining*Machine learning*

Мы поговорим об использовании модных «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-грамм:

$V = \sum_{g \in G}{z_g},$

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

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

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

Язык	Датасет	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 мы отходили от буквенного представления слова, пытаясь сблизить слова вроде «царь» и «король», «мама» и «сын», сейчас же мы возвращаемся к «буквенной близости», что для семантической задачи может и не очень хорошо, но для нашего варианта (напомню — исправление опечаток) это то что надо.

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

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

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

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

Реализация

Тестовый код достаточно простой (спасибо, 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 — векторы одинаковые:

$similarity = cos(\theta) = \frac{A\cdot B}{\parallel A\parallel \parallel{B}\parallel} = \frac{\sum_{i=1}^n A_iB_i}{\sqrt{\sum_{i=1}^n A_i^2} \sqrt{\sum_{i=1}^n B_i^2}}$

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

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

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

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

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

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

Слово с опечаткой	Задуманное слово	№ в списке ближайших	Значение метрики
челавек	человек	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

Замечания:

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

Топ 10 ближайших слов для каждого

челавек:
человек 0.87035
челба 0.80893
человечий 0.77607
чек 0.74867
век 0.71127
челнок 0.68631
человеческий 0.63725
человечность 0.63615
внучек 0.59655
пчела 0.59173

стулент:
стул 0.73342
стулец 0.70797
брезент 0.67196
стукотёл 0.64903
инструмент 0.64340
фундамент 0.61881
шофер 0.60767
бридж 0.60279
тулуп 0.60249
чембур 0.59757
студент 0.58953

студечнеский:
студенческий 0.85685
юношеский 0.75904
веский 0.72052
химический 0.71119
отроческий 0.70076
истерический 0.69888
физический 0.69580
мальчишеский 0.68713
фосфорический 0.68312
всяческий 0.68136

чиловенчость:
человечность 0.75012
откровенность 0.74727
никчёмность 0.72961
близость 0.72873
ограниченность 0.72581
ценность 0.72350
трусость 0.72186
двусмысленность 0.72128
беременность 0.72121
значимость 0.72100

учавствовать:
здравствовать 0.93609
неистовствовать 0.89396
упорствовать 0.89216
бедствовать 0.88620
злорадствовать 0.87975
участвовать 0.87767
свирепствовать 0.87446
пьянствовать 0.86810
чувствовать 0.86627
сочувствовать 0.86622

тактка:
такт 0.87537
тактика 0.73542
табуретка 0.66532
этикетка 0.65750
чесотка 0.65702
щётка 0.64602
анютка 0.64291
решётка 0.62549
така 0.62321
свёртка 0.61241

вообщем:
сообщение 0.57405
вооружение 0.51535
незначащий 0.50341
вооружённый 0.49465
невооружённый 0.48958
общение 0.48076
общежитие 0.48069
путешествие 0.47493
малозначащий 0.46655
сообщать 0.46373

симпотичный:
личный 0.86102
уличный 0.84662
энергичный 0.83907
циничный 0.82305
отличный 0.81775
типичный 0.80783
фабричный 0.80701
яичный 0.80283
вторичный 0.79368
гаубичный 0.77946

зделать:
исделать 0.93598
сделать 0.91553
делать 0.90678
наделать 0.87672
недоделать 0.87297
отделать 0.85775
заделать 0.84235
желать 0.82316
поделать 0.78098
проделать 0.77232

сматреть:
смотреть 0.80055
усмотреть 0.78115
осмотреть 0.77926
треть 0.73819
посмотреть 0.716420
рассмотреть 0.71075
обветреть 0.68950
всмотреться 0.68513
пестреть 0.65353
посмотреться 0.65069

алгаритм:
ритм 0.85291
демисезон 0.69376
рейтузы 0.66552
цинизм 0.66278
тупяк 0.65656
шорин 0.65496
баритон 0.64623
фрашенбрудер 0.64395
жгут 0.63321
шпалера 0.63161

ложить:
вложить 0.89386
уложить 0.89129
обложить 0.87222
выложить 0.87199
отложить 0.84127
низложить 0.83720
заложить 0.83572
сложить 0.83549
наложить 0.82764
положить 0.81718

Заключение

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

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

Tags:

Hubs: