Хабрахабр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$V = \sum_{z_g},$

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

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

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

Язык

Датасет

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 — векторы одинаковые:

$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}}$

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

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

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

  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-грамм получаются примерно одинаковые вектора.

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

87035
челба 0. челавек:
человек 0. 77607
чек 0. 80893
человечий 0. 71127
челнок 0. 74867
век 0. 63725
человечность 0. 68631
человеческий 0. 59655
пчела 0. 63615
внучек 0. 73342
стулец 0. 59173

стулент:
стул 0. 67196
стукотёл 0. 70797
брезент 0. 64340
фундамент 0. 64903
инструмент 0. 60767
бридж 0. 61881
шофер 0. 60249
чембур 0. 60279
тулуп 0. 58953

студечнеский:
студенческий 0. 59757
студент 0. 75904
веский 0. 85685
юношеский 0. 71119
отроческий 0. 72052
химический 0. 69888
физический 0. 70076
истерический 0. 68713
фосфорический 0. 69580
мальчишеский 0. 68136

чиловенчость:
человечность 0. 68312
всяческий 0. 74727
никчёмность 0. 75012
откровенность 0. 72873
ограниченность 0. 72961
близость 0. 72350
трусость 0. 72581
ценность 0. 72128
беременность 0. 72186
двусмысленность 0. 72100

учавствовать:
здравствовать 0. 72121
значимость 0. 89396
упорствовать 0. 93609
неистовствовать 0. 88620
злорадствовать 0. 89216
бедствовать 0. 87767
свирепствовать 0. 87975
участвовать 0. 86810
чувствовать 0. 87446
пьянствовать 0. 86622

тактка:
такт 0. 86627
сочувствовать 0. 73542
табуретка 0. 87537
тактика 0. 65750
чесотка 0. 66532
этикетка 0. 64602
анютка 0. 65702
щётка 0. 62549
така 0. 64291
решётка 0. 61241

вообщем:
сообщение 0. 62321
свёртка 0. 51535
незначащий 0. 57405
вооружение 0. 49465
невооружённый 0. 50341
вооружённый 0. 48076
общежитие 0. 48958
общение 0. 47493
малозначащий 0. 48069
путешествие 0. 46373

симпотичный:
личный 0. 46655
сообщать 0. 84662
энергичный 0. 86102
уличный 0. 82305
отличный 0. 83907
циничный 0. 80783
фабричный 0. 81775
типичный 0. 80283
вторичный 0. 80701
яичный 0. 77946

зделать:
исделать 0. 79368
гаубичный 0. 91553
делать 0. 93598
сделать 0. 87672
недоделать 0. 90678
наделать 0. 85775
заделать 0. 87297
отделать 0. 82316
поделать 0. 84235
желать 0. 77232

сматреть:
смотреть 0. 78098
проделать 0. 78115
осмотреть 0. 80055
усмотреть 0. 73819
посмотреть 0. 77926
треть 0. 71075
обветреть 0. 716420
рассмотреть 0. 68513
пестреть 0. 68950
всмотреться 0. 65069

алгаритм:
ритм 0. 65353
посмотреться 0. 69376
рейтузы 0. 85291
демисезон 0. 66278
тупяк 0. 66552
цинизм 0. 65496
баритон 0. 65656
шорин 0. 64395
жгут 0. 64623
фрашенбрудер 0. 63161

ложить:
вложить 0. 63321
шпалера 0. 89129
обложить 0. 89386
уложить 0. 87199
отложить 0. 87222
выложить 0. 83720
заложить 0. 84127
низложить 0. 83549
наложить 0. 83572
сложить 0. 81718

82764
положить 0.

Заключение

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть