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

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


    где
    $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 ближайших слов для каждого
    челавек:
    человек 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 как дополнение к другим методам вполне может повысить качество исправления опечаток.
    • +13
    • 4,5k
    • 4

    Singularis

    60,00

    Компания

    Поделиться публикацией

    Похожие публикации

    Комментарии 4
      +2
      Можно отбросить все отличающиеся по длине более чем на 1 букву и результат резко улучшится.
        0
        Да, здесь есть много вариантов, не только по длине, но и пороги по тому же расстоянию Дамерау-Левенштейна улучшат ситуацию, набор эвристик все-таки индивидуален для конкретного применения.
        0
        А что со скоростью этого алгоритма? Вы считали расстояние от каждого примера до каждого вектора в словаре, или приеняли какие-то оптимизации?
          0
          Я использовал метод Gensim'a для получения N ближайших слов (most_similar), думаю, внутри есть оптимизации. Замеры по времени не делал, «визуально» быстро (несколько мс на один запрос), если очень важно — могу сделать с числами.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое