Система проверки орфографии для башкирского языка

Размещено на http://www.allbest.ru/

Правительство Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего образования

Национальный исследовательский университет

«Высшая школа экономики»

Факультет гуманитарных наук

Образовательная программа «Фундаментальная и компьютерная лингвистика»

Выпускная квалификационная работа

Система проверки орфографии для башкирского языка

студент 4 курса бакалавриата группы БКЛ-152

Татаринов Дмитрий Юрьевич

Научный руководитель

канд. филологических наук, доц.

Б.В. Орехов

Москва 2019



Введение

В настоящее время особенно сильна тенденция к автоматизации обработки данных, при которой работа выполняется не человеком, а с помощью вычислительных машин. Это помогает избавиться от человеческого фактора во время проведения работы, тем самым повысить качество выполнения задачи, а также осуществлять значительно более трудоемкие операции, которые трудны для человека. К процессам, которые переходят на стадию автоматической обработки, можно отнести проверку правописания набранного компьютерным способом текста. При отсутствии готовых решений этой задачи с помощью вычислительных машин, человеку приходится вручную, в некоторых случаях с помощью бумажного словаря, проверять напечатанные или рукописные тексты. Такой процесс может занять достаточно много времени и человеческого ресурса, а также в силу ограниченности человеческих возможностей предполагает пропуск ошибок.

Для языков с большим количеством носителей, автоматизация проверки текста стала обычным делом. Помимо распространенных задач, таких как автоматическая коррекция текста во время печати на портативных устройствах и настольных компьютерах, алгоритм распознавание ошибок можно использовать в научных целях. Например, проверка работы технологии OCR, технологии распознавания рукописного текста. Эти технологии с помощью нейронных сетей или других средств разделяют поступающий отсканированный документ на текстовый слой и слой с изображениями. Текстовый слой, с помощью обученных нейронных сетей, которые на основе имеющихся представлений о внешних признаках символа текста, переводится из изображения в напечатанный текст (Усилин, Николаев, Постников, 2009). На стадии тестирования, необходимо оценить точность работы таких алгоритмов при помощи сопоставления реальных текстов и их распознанных версий.

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

Для башкирского языка, таких сервисов, на данный момент нет. Этот факт подчеркивает актуальность разработки средств автоматической обработки текстов для языков, для которых такие средства отсутствуют (малоресурсные языки), в том числе для башкирского языка. Разработка продукта позволит не только развить использование таких средств в повседневной жизни, что значительно упростит выполнение ежедневных задач, связанных с работой с текстом, но также позволит развивать другие технологии, основанные на лингвистическом знании, и имеют непосредственную близость к работе с языком в целом.

Также необходимо отметить одну особенность, присущую разработке алгоритмов автоматической проверки текстов в настоящее время. Еще при первых разработках спелл-чекеров использовались технологии, основанные на автоматической проверке текста с использованием сформированного словаря. То есть человек исключался из цепи проверки текста и заменялся компьютером (Nielsen & Microsystems, 1996). При этом, словарь составлялся людьми, что не исключало ошибок. Ошибки при составлении словаря нарушали работу алгоритма. Таким образом, формировалась словарная зависимость работы алгоритма. Со временем развивались и технологии позволяющие заменять человека не только в качестве проверяющего, но и обучающего. Речь идет не о полном исключении человека из создания алгоритма, а об алгоритмах с использованием машинного обучения и нейронных сетей.

Методы машинного обучения, позволяют создавать модели, которые формируют числовое и формульное представление об объекте, тем самым вычислять их признаки на основе предоставленных данных (Pedregosa и др., 2011). Нейронные сети, как и следует из названия, формируют цепь из искусственных нейронов. Такая система меняет свою структуру, подстраиваясь под представленные данные, с целью построения цепей-зависимостей, которые также позволяют определять признаки входящих данных (Krogh & Vedelsby, 1995). Оба метода показывают высокое качество работы в области автоматической обработке текстов, в том числе автоматикой проверки текстов, однако имеют несколько значимых недостатков. Для достижения хорошего качества работы алгоритмов необходимо составить большой корпус материала, на котором модели будут строить свои зависимости. Помимо размера корпуса, корпус текстов должен содержать предварительно размеченные положительные и отрицательные примеры токенов. Помимо этого, корпус не должен быть составлен на основе тематических текстов. Использование тематических корпус в качестве материала для обучения моделей может негативно сказаться на качество работы итоговой модели из-за характерных языковых конструкций, которые присущи выбранной тематике. Это обусловлено ограниченностью и специфичностью набора словоформ ( Митрофанова, Захаров, б. д.). В случае башкирского языка и формата ВКР (выпускной квалификационной работы) не представляется возможным формирования корпуса такого типа и объема, что делает проблематичным использование вышеуказанных методов в качестве основной технологии. Это обусловлено тем, что готового размеченного корпуса для башкирского языка, на данный не существует, а подготовка материала представляет из себя трудозатратный процесс. Таким образом, задача по созданию алгоритма автоматической проверки текстов включает в себя разработку нового алгоритма, который не будет зависеть от тематики и размера корпуса. За основу берется идея определения приемлемости биграмм-последовательностей внутри языковой парадигмы, которая подвергается меньшему влиянию тематики и объема корпуса. Развитие посимвольной проверки текстов позволит разрабатывать технологии для языков, текстовые корпуса которых не позволяют строить модели на основе работы целиком со словоформами.



1. Постановка цели работы

автоматический проверка башкирский язык

Основная цель данной работы - это разработка алгоритма автоматической проверки текстов на основе текстов башкирского языка. За неимением возможности формирования большого корпуса текстов, который будет содержать как правильные, так и неправильные размеченные словоформы для работы с уже существующими методами автоматической обработки напечатанных текстов, а также узкой направленностью имеющихся текстов, необходимо разработать свой собственный алгоритм, основанный на проверке корректности последовательности биграмм-конструкций. Для решения поставленной цели необходимо:

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

2. Подробно изучить уже существующие методы построения спелл-чекеров, рассмотреть их слабые и сильные стороны.

3. Проанализировать, описать и подготовить предоставленный корпус башкирских текстов для работы алгоритма.

4. Изучить и составить распределение вероятностей существования всех возможных биграмм-конструкций для башкирского языка.

5. Разработать алгоритм проверки текстов при помощи языка программирования Python на основе полученных сведений о вариативности и частотности употреблений биграмм-конструкций.

6. Провести тестирование на различных тактовых выборках, чтобы выявить финальный результат, сильные и слабые стороны построенного алгоритма.

7. На основе результатов теста, провести возможные операции по улучшению качества работы алгоритма.



2. Изучение возможных опечаток на письме

Начало разработки алгоритма корректировки напечатанного текста необходимо начать с разбора и описания возможных типом ошибок, которые человек может допустить во время набора текста (Chatterjee, Athayle, Akhawe, Juels, & Ristenpart, 2016). Это необходимо сделать до начала разработки алгоритма, чтобы проанализировать природу возникновения ошибок, и разобраться с тем, какие ошибки можно распознать только путем анализа текста человеком, а какие ошибки можно распознать с помощью вычислительной машины.

1. Вставки символов с неправильным регистром - Такие типы ошибок могут возникнуть при неисправности печатной техники, или ошибочного нажатия клавиши верхнего регистра во время быстрого набора символов. Такого типа ошибки не имеют большого значения, если опечатка совершена не в начале слова. Заглавная буква является определяющей при распознавании и различии имен нарицательных и имен собственных. Таким образом, если ошибка совершена не в начале слова, спелл-чекер позволяет распознать ошибку без особого труда. В обратном случае, необходим более глубокий анализ природы происхождения слова.

2. «Клавиатурные опечатки» - При быстром наборе или недостаточной внимательности, человек может набрать символ, который находится на клавиатуре рядом с необходимым символом, например слово мир напечатано как мтр. Такого рода ошибки могут быть также вызваны механическим сбоем печатного устройства. Распознать такие ошибки можно при помощи сверки со словарем, а также, если последовательность символов нарушена грубо и противоречит возможным для данного языка правилам построения конструкций. Однако, существуют варианты, которые невозможно распознать без помощи контекстного анализа, например слово дом и слово лом. На русской раскладке компьютерной клавиатуры буква д находится непосредственно рядом с буквой л.Распознавание таких ошибок не входит в общий функционал спелл-чекеров.

3. Транспозиционные ошибки - Возникают при смене местами двух или более символов словоформы. Важно, что данные символы находятся последовательно. В отличии от «Клавиатурных опечаток», состав символов при таких ошибках не изменяется, нарушается только порядок. Распознавание таких ошибок спелл-чекером возможно только при грубом нарушении изначального строя слова с формированием несуществующей словоформы.

4. Нарушение морфологического строя - Если сформированная в процессе написания словоформа не нарушает правило формирования словоформ для данного языка, а лишь нарушает смысл построения предложения, тогда ошибка не может быть распознана без контекстного анализа текста. Такого типа ошибки не распознаются спелл-чекерами.

5. Пропуск слова - При пропуске целой словоформы, с последующим нарушением логики построения предложения, как и других примерах, связанных с отсутствием нарушения правила построения словоформы, необходимо использовать методы контекстного анализа предложения. Распознавание такого типа ошибок также не входит в основные задачи спелл-чекеров.

Описанные типы ошибок можно распределить на две определяющие группы:

1. Ошибки, которые формируют несуществующие для изучаемого языка словоформы - non-worderrors (NWE)

2. Ошибки, которые формируют существующие для изучаемого языка словоформы - real-worderrors (RWE)

Спелл-чекер предназначен для распознавания ошибок типа NWE, так как само по себе правописание словоформ при возникновении RWE ошибок не противоречит правилам написания (Choudhury, Thomas, Mukherjee, Basu, & Ganguly, 2007). Соответственно не являются с данной точки зрения неправильными. Определение таких слов зачастую происходит при помощи сверки со словарем. Если словоформа не определена в словаре, значит такая словоформа принимается за неправильную (Choudhury и др., 2007). Для распознавания ошибок типа RWE необходимо проводить дополнительный семантический анализ текста, который осуществляется посредствам создания языковых моделей на основе уже упомянутых нейронных сетей, что невозможно в рамках выполняемой работы.

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

2.1 Работа с ошибками при использовании техники OCR

Отдельно стоит рассмотреть работу спелл-чекера в связке с технологией распознавания текста с изображений при помощи технологии OCR. Характер ошибок работы данного алгоритма непредсказуем и совмещает в себе ошибка двух типов, как RWE, так и NWE. Это происходит по той причине, что распознавание символов текста основано на визуальном сходстве двух единиц. Таким образом, схожие по своему образу букву и числа с большой вероятностью будут распознаны неправильно, замещая друг друга. Также, при отсутствии каких-либо ассоциативных рядов для определения символа, единица будет распознана как пустой символ или пробел, таким образом нарушается строй предложение со значительным повреждением словоформы. Такие ошибка тяжело распознаются спелл-чекерами. Для решения подобных задач формируются отдельные алгоритмы контекстного анализа и предсказания праформы, которые дополняются модель спелл-чекера для повышения точности проверки и оптимизации работы технологии (Tong & Evans, 1996).



2.2 Изучение существующих методов создания алгоритмов автоматической коррекции текста

Данная глава предназначена для описания возможных решений поставленной задачи, с целью изучения слабых и сильных сторон с дальнейшим использованием полученных данных.

2.3 Построение нейронных сетей

Нейронные модели широко используются в процессах обработки информации, поскольку они позволяют распознавать образы объектов, производить классификацию по множеству признаков, а также прогнозировать время выполнения процессов, таким образом оценивая продуктивность работы алгоритма. Финальная модель, после обучения, способна к обобщению данных, что уменьшает воздействия шумов и не валидной выборки на результат работы классификации. Также, нейронные сети способны к воссозданию исходной формы объекта, поступающего на вход, при незначительных его повреждениях ( Заенцев, 1999). Такие модели обладают высоким качеством работы при решении задач, связанных с текстами, вплоть до задач генерации текста. Однако для формирования такой модели необходимо собрать корпус текстов, которые гарантированно будут иметь положительные и отрицательные примеры (Правильные и неправильные словоформы). Собрать такой корпус проблематично, особенно когда речь идет о языке с низким уровнем развития сферы использования цифровых технологий в языковом функционировании. Недостаточность корпуса по какому-то параметру может резко негативно отразиться на работе модели и ее дальнейшем результате. При этом, обучение такой модели занимает длительное время и больших затрат по производительности вычислительной машины. В условиях выпускной квалификационной работы подход не рассматривается как оптимальный.

2.4 Использование методов машинного обучения

В качестве альтернативы нейронным сетям существует вариант использования методов машинного обучения, а именно SVM моделей и модели с построением деревьев зависимости (Liu, Cheng, Luo, Duh, & Matsumoto, 2013).

SVM - метод опорных векторов, основан на расширении размерности плоскости построения векторного представления объекта. Это позволяет увеличить размерность плоскостей, определяющих принадлежность объекта к классу, что повышает качество алгоритмов классификации (Colas & Brazdil, 2006). При решении задач с текстовыми данными, метод используется в совокупности с технологиями, которые позволяют представить текст в виде векторов. Например, готовым методом CountVectorizer из библиотеки Sklearn для Python, который основан на подсчете количества уникальных токенов внутри объекта, тем самым задавая числовые параметры для построения векторного представления (Hackeling, 2017).

Деревья зависимость - это иной подход к решению классификации, который основан на определении характеристики объекта при помощи последовательной совокупности его признаков. Например, если нам необходимо описать слово, мы можем задать его при помощи последовательности символов. В качестве решения нашей задачи, данное решение как раз разбивает токен на последовательность символов и, если последовательность приводит к вершине дерева, которая не определяет словоформу как верную, токен определяется неправильным.

Оба метода хорошо себя зарекомендовали в задачах текстовой классификации, а также при решении других лингвистических задач (Colas & Brazdil, 2006). Такой подход позволяет повысить трудоемкость работы алгоритмов и ускорить как процесс создания модели, так и увеличить скорость её работы. Однако качество таких методов ниже, чем качество работы нейронных сетей. При этом, для проведения классификации также необходим корпус, который по своей характеристике и минимальным требованиям схож с корпусом, необходимым для использования нейронных сетей. Также, методы машинного обучения требуют более глубокой предобработки текста, которая требует написания дополнительных алгоритмов, которые могут значительно усложняют процесс.

Если производить оценку и сравнение данного решения и решения с помощью нейронных сетей, то можно отметить упрощение схемы построения моделей, меньшие затраты по вычислениям, уменьшение времени самого процесса обучения. При этом, итоговая точность работы алгоритма меньше, а зависимость от корпусных факторов наоборот возрастает.

2.5 Построение векторной модели языка

Идея построения векторной модели языка основана на представлении, что можно задать такое пространство, с помощью которого можно будет через вектора и задающие его числовые значение описать любой объект выборки. Иными словами, объект изучения представляется с помощью вектора внутри общей картины исследования таким образом, что всем различным объектам соответствуют различные вектора. При обучении такой модели на текстовых данных, в качестве признаков может выступать количество определенных символов в той или иной словоформе, или другие существующие метрики (Crow, Scarberry, Calaprist, Miller, Nakamura, Saffer 2003). Такой метод позволяет хранить тексты ином, векторном представлении, с дальнейшим сравнением при помощи вычисления дистанции между полученными векторами. Проверка приемлемости словоформ работает схожим образом, как и проверка при помощи словаря, только вместо сравнений словоформ происходит сравнение векторов. Данный метод, помимо проверки позволяет строить предположения об первообразном представлении неправильной словоформы. Также, сложение нескольких векторов позволяет производить контекстный анализ текстов, для решения проблем с распознаванием ошибок типа RWE. При всем при этом, данная методика больше всех зависит от качества построения и подготовки корпуса к обучению модели. Если обучать такую модель на тематическом корпусе, тогда и представление о языке будет строиться в рамках узкого лексического круга, что негативно влияет на работу алгоритма.

2.6 Итоги анализа существующих методов

Анализ показал, что ни один из вышеуказанных методов не подходит для решения поставленной задачи. Было принято решение создания собственного алгоритма, который не будет использовать методику проверки текста при помощи словаря, а будет анализировать последовательность символов, которая задается языком. Вне зависимости от тематики и размерности корпуса, язык будет соблюдать допустимые нормы формирования словоформ при помощи заданных последовательностей. Для этого необходимо сформировать математическую формулу, которая позволит численно оценить корректность токена через сравнение с базисным числом. При этом в дальнейшем, алгоритм должен быть способен к воссозданию изначальной формы некорректной словоформы.



3. Формирование логики алгоритма

Разработанный нами алгоритм для проверки правописания башкирских текстов основан на взаимодействии символьных биграмм-конструкций внутри языковой модели и скрытых моделей Маркова (HMM) в совокупности с формулой полной вероятности цепи Маркова. Основная идея скрытых моделей Маркова заключается в том, что на основе имеющихся, проверенных состояний объекта, в случае нашей задачи, этим объектом является текстовый корпус, можно определить последующее состояние. Например, предугадать, какое будет следующее слово в предложении, как это реализовано при наборе текста на портативных устройствах, когда во время набора текста, пользователю предлагаются возможные варианты продолжения написанного им текста (Ueda and Nakagawa, 1990).

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

Если нам известно, возможные кандидаты на следующие состояния объекта, значит на основе этих данных, можно проверить актуальность полученных состояний с помощью рассчитанных вероятностей. Если новое состояние не наблюдалось или ожидалось, с очень низкой вероятностью, то тогда такое состояние можно принимать за неправильное.

Слова в качестве составляющих биграмм конструкций были приведены в качестве наглядного примера, в реальных условиях, для решения поставленной задачи слова будут заменены последовательностью символов, которые составляют слова. Это обусловлено тем, что последовательность символов внутри словоформ распределена не хаотично, а определена для каждого языка своя. Таким образом, эту заданную последовательность можно задать с помощью вероятностей, которые буду описывать вероятность ожидания символа в данной позиции в рамках грамматики башкирского языка

Таким образом разработка алгоритма заключается в нескольких этапах:

Выявление различных биграмм-конструкций на основе корпуса правильных текстов.

Подсчет вероятностей существования выявленных конструкций в данном языке.

Выбор пороговой метрики для фильтрации неправильных вариантов.

Создание самой последовательности проверки и сверки вероятностей.

Тестирование и отлаживание качества работы алгоритма проверки.

Помимо этого, необходимо выполнить ряд дополнительных задач, таких как:

Произвести очистку корпуса от пунктуации, а также слов, которые не подходят под необходимую выборку.

Написать код для проверки качества работы полученного алгоритма.

Собрать корпус для проведения тестов на новых текстах.

Оценить работу алгоритма с помощью реальных людей.



4. Предобработка текста для подсчета вероятностей

Предобработка текста позволяет повысить качество обучения модели путем более точного определения словоформы. Так как пунктуация не является частью словоформы, следовательно, и учитывать ее при подсчете вероятностей возможных конструкций словоформ не представляется разумным.

Первый этап чистки текста заключается в очистке текста от пунктуации, которая не учитывается в проверке правописания. Отдельное внимание стоит уделить словам с дефисным написанием. Такие слова изначально были нехарактерны для башкирского языка, а появились позже посредствам соединения несколько основ. В данном случае, дефис не просто исключается из выборки, а заменяется с помощью регулярных выражений на пробел в каждом тексте корпуса, чтобы разделить слово на самостоятельные части. После обработки слов с дефисным написанием, создается список пунктуации. За основу берется встроенный в модуль string список пунктуации string.punctuation. Данный список, дополнительно расширяется вручную символами пунктуации, которые были выявлены при первых тестовых чистках текста. Каждый текст делится на символы, эти символы поочередно сверяются со списком пунктуации. Если символ входит в данный список, то он исключается из текста. Таким образом, получается наиболее эффективно очистить текст от пунктуации не только на границах слова, но и возможных позициях внутри него.

Второй этап подготовки текста заключает в себе процесс исключения из корпуса иностранных слов. Для корректной работы модели, необходимо убедиться в том, что работа производится только со словами башкирского языка. Если в выборку попадают иностранные слова или числа, то распределение вероятностей изменятся и перестает быть показательным. На основе грамматики формируется алфавит башкирского языка. Текст делится по пробелам на слова. Для каждой буквы, каждого слова, проверяется условие, входит ли буква в алфавит. На выходе получается список со значениями True / False. С помощью встроенного метода all проверяется наличие значения False. Если такое значение присутствует, то слово исключается из выборки. После того, как каждый текст корпуса прошел чистку, производится завершающая стадия подготовки текста.

Поскольку в башкирском языке нет слов длиной в один символ, такие вхождения необходимо также удалить из выборки. Удаление происходит по такой же логике, как и в предыдущих этапах. На этом же этапе необходимо выправить регистр текста. Имена собственные, наименования и другие слова, которые необходимо писать верхнего регистра зачастую отличаются по своей конструкции, а также заимствованы из других языков. Такие слова необходимо рассматривать отдельно от общего корпуса, однако отделить их непросто. В данной работе, было принято решение, относить к таким словам все токены, которые начинаются с заглавной буквы, то есть не на границе предложения. С помощью регулярных выражений, все слова корпуса, которые стоят в первой позиции предложения были приведены к нижнему регистру. Регулярные выражения представляют собой набор функций, который работает по логике вхождения значения в указанный объект. Если хотя бы один элемент указанного объекта имеет указанную структуру, тогда над ним выполняется заданное пользователем условие. Слова, написанные заглавными буквами, принимаются за имя нарицательное и также приводятся к нижнему регистру.



5. Формирование вероятностей

В дальнейшем, будут описаны два подхода к написанию алгоритма проверки, однако оба они используют одни данные, вероятность существования последовательности символов в тексте. В данной главе подробно распишем как считались эти вероятности.

После подготовки корпуса, в Python создаются словари, для хранения подсчетов данных. Словарь в Python представляет из себя набор связок ключ-значение, с помощью которых можно хранить необходимые данные под указанным индексом, который постоянно привязан этому значению. Всего насчитывается 6 словарей. Таким образом мы постоянно имеем доступ к этим данным. Первый тип словаря предназначен для хранения информации про первую позицию слова. Ключ в данном словаре - все возможные буквы башкирского алфавита, которые встречаются в первой позиции слова. Значение - вероятность нахождения буквы-ключа в первой позиции. Словарей такого типа создается два, для слов, которые начинаются на букву нижнего и верхнего регистра отдельно. Второй тип словаря - имеет такую же структуру, однако подсчет ведется для букв последней позиции. Таких словарей также создается два, для разного типа словоформ. Третий тип словаря предназначен для хранения вероятностей биграмм конструкций. Ключом в данном словаре также является буква башкирского алфавита, однако в качестве значения выступает еще один словарь, в котором в качестве ключей хранятся буквы, которые идут после первичной буквы-ключа, а значением выступают вероятности существования последовательности, где первая буква - ключ словаря первого уровня, а вторая буква - ключ словаря второго уровня. Такая структура помогает удобно хранить вероятности и быстро обращаться к ним.

Для получения тех самых значений, все тексты склеиваются в один текст, который делится по пробелам для получения списка слов. После этого, алгоритм проходится по каждому слову и разбивает его на три группы:

Буква первой позиции.

Буква последней позиции.

Список символов слова без последней буквы.

Последний символ отделяется от словоформы, так как его вероятность считается отдельно.

Когда слово попадает на итерацию, в первую очередь алгоритм анализирует первую букву. На данном этапе идет отделение слов, которые начинаются на заглавную букву, для определения словарей, в которые будут производиться записи. После этого алгоритм обращается к словарю первого типа и проверяют, есть ли там ключ со значением первой буквы слова. Если такого ключа нет, то он создается со значением 1. Если ключ уже есть, то к его значению прибавляется единица. По такой же логике обрабатывается последняя буква слова, а затем исключается из списка символов.

Оставшаяся часть разбивается по символам и нумеруется. Отсчет начинается со второго символа. Дальше, для каждой буквы с индексом (номером) “x” вычисляется буква с индексом “x - 1”. После этого производится запись в словарь хранения биграмм. Сперва делается обращение по ключу-букве с индексом “x - 1”. Если такого ключа нет, то он заводится и ему задается в значение пустой словарь, в который записывается ключ-буква и индексом “x”, значение которой равно 1. Если ключ-слово с индексом “x - 1” существует, тогда происходит процесс подобный записи в словари первого и второго типа. Таки образом словари заполняются количеством комбинаций разных символов во всех возможных позициях. После этого, полученные значения необходимо поделить на суммарное количество вхождений в каждом словаре, чтобы получить вероятность существования символа в указанной позиции. Слова длинной в два символа считаются за один полноценный биграмм.

По окончанию процесса подсчета количества всех различных вариаций для первой, последней позиции слова и биграмм составляющих, необходимо перевести числа в вероятности. Для вычисления вероятности вычисляется сумма значения для словаря, затем каждая позиция делится на полученное число.

Рисунок 1. Схема обработки словоформ при формировании вероятностей



6. Алгоритм проверки

Ранее уже была описана логика процесса проверки. В данной главе будет расписана реализация алгоритма.

6.1 Проверка с помощью формулы цепи Маркова

Чтобы посчитать вероятность существования последовательности из четырех событий, нам необходимо рассчитать всевозможные комбинации этих событий и выбрать самое вероятное. Однако, основное преимущество цепей Маркова заключается в том, что итоговую вероятность существования последовательности можно рассчитать с помощью формулы, которая исключает этот трудозатратынй процесс. Правило гласит, что состояние объекта зависит только от предыдущего состояния, а все, что идет перед ним, нас не интересует. Итоговая формула выглядит для последовательности четырех состояний выглядит так:

P(общ.) = P(С1 ) * P( С1 С2 ) * P( С2 С3 ) * P( С4 )

Где P(общ.) - Это общая вероятность последовательности. P(С1 ) - Вероятность состояния 1 выступать в качестве первого состояния. P( С1 С2 ) - Это вероятность следования состояния 2 после состояния 1. P( С2 С3 ) - Это вероятность следования состояния 3 после состояния 2. P( С4 ) - Вероятность состояния 4 выступать в качестве заключающего состояния. Рассмотрим работу в формате нашей задачи и распишем формулы для слова «дом»:

w= дом

P(w) = P( _д ) * P( до ) * P( м_ )



Где в данной формуле P(w) - вероятность существования данного слова (данной конструкции) в языке, P( _д ) - вероятность нахождения «д» в первой позиции слова для языка, P( до ) - вероятность существования биграмма «до» для языка и P( м_ ) - вероятность нахождения «м» в последней позиции слова для языка.

После того, как значение получено, его необходимо сравнить с другим значением, чтобы определить валидность конструкции. В оригинале логике цепей Маркова, полученную вероятность принято сравнивать с вероятностями конструкций, которые также могут стоять в данной позиции. В нашем случае, при оценке актуальности конструкции, нет других вариантов. Для этого используется пороговое значение, которое выражает минимальную вероятность, определяющую правильную конструкцию. Существует два варианта формул, первая упрощенная, вторая расширенная. Упрощенная формула учитывает общую вероятность первой позиции, общую вероятность последней позиции и общую вероятность всех возможных биграмм конструкций. Общая вероятность - это долевая вероятность согласно выбранной метрики, например медиана всех вероятностей первой и последней позиции. Выбор метрики влияет на общее смещение порогового значения относительно шкалы валидности конструкции. Про выбор метрики будет описано подробно в следующей главе, на данный момент будем считать, что метрика - это медиана значений. Упрощенная формула порогового значения для слова выглядит так:

P(wi) = P(Metric (_#) ) * ( P(Metric (биграмм)) * (x - 2) ) * P( Metric (#_))

В данной формуле P(wi) - итоговая пороговая вероятность, Metric(_#) - значение вероятность для первой позиции слова в соответствие с выбранной метрикой, Metric(#_) - значение вероятность для последней позиции слова в соответствие с выбранной метрикой, P(Metric (биграмм)) - долевое значение вероятностей по всем биграмм-конструкциям корпуса в соответствие с выбранной метрикой, x - длина слова, которое поступает на проверку.

В свою очередь расширенная формула учитывает не общее значение по всем вероятностям биграмм - конструкциям, а учитывает значение для каждого биграмма отдельно в соответствии с первой буквой. Таким образом, формула для высчитывания порогового значения для слова “дом”, выглядит так:

P(wi) = P(Metric (_#) ) * P(Metric (д#)) * P( Metric (#_))

Где в данной формуле P(wi) - итоговая пороговая вероятность для слова w(дом), Metric(_#) - значение вероятность для первой позиции слова в соответствие с выбранной метрикой, Metric(#_) - значение вероятность для последней позиции слова в соответствие с выбранной метрикой, Metric(д#) - значение вероятности для биграмма начинающегося на букву «д».

Если P(w) < P(wi), то слово признается неправильным, в обратном случае, признается верным.

6.2 Проверка с помощью биграмм модели

Данный алгоритм проверки основан на логике формулы цепей Маркова, но проверяется не итоговая вероятность существования конструкции, а вероятность существования составляющих конструкции по отдельности. После подсчета вероятностей, как и в логике с формулой, рассчитываются пороговые вероятности. Затем слово разбивается на три части, на первую букву, на последнюю букву и на биграмм составляющие компоненты слова без последней буквы. Вероятность существования каждой части сверяется с пороговым значением, после чего, если хотя бы одна составляющая встречается в языке реже, чем пороговое значение, слово признается неправильным. Данный способ предназначен для того, чтобы на стадии проверки можно было определить часть слова, в которой совершена ошибка с наибольшей вероятностью.



7. Подсчет пороговых вероятностей

Представим все рассчитанные вероятности распределенными по шкале от 0 до 1, как самые характерные и самые нехарактерные для башкирского языка. Для того, чтобы определять поступающие на проверку слова, необходимо их составляющие распределять в зависимость от их вероятностей по данной шкале. В таком случае, пороговое значение - это такое значение вероятности, при котором значения ниже характерны для слов нехарактерных для башкирского языка, и наоборот.

Первоначально в качестве долей при подсчете пороговых значений использовалась медиана, первый квартиль и третий квартиль. Как показали эксперименты, выбор первого квартиля и медианы в качестве метрики приводят к тому, что качество определения неправильных слов, как неправильных, было ниже среднего, при этом качество определения правильных слов как правильных было приближено к максимальному. Обратная ситуация была при использование долевого деления при помощи третьего квартиля. Модель с большей вероятность определяло слово как неправильное, из-за чего качество определения правильных слов как правильно падало. Из-за неравных и крайне противоположных результатов, было принято решение определить доли отдельно для каждой из моделей при помощи библиотеки Numpy.

Метод Numpy.quantile позволяет определить долю распределения случайных вероятностей. С помощью этого метода, можно определить границу порогового значения и протестировать различные варианты, подобрав то значение, при котором медиана между долей определения правильных слов и долей определения неправильных слов становится максимальной. Для выяснения написан отдельный алгоритм, который делит шкалу распределения от 0 до 1 на 10 частей (0.1, 0.2, … , 0.9, 1). С помощью Nympy.quantile получаем пороговую вероятность соответствующей значению доли. Данная вероятность принимается за пороговую в процессе проверки текстов корпуса. Выявляется медиана качества работы алгоритма и берется за точность определения. По завершению получается наблюдать зависимость доли от 0 до 1 в десятых и точности работы алгоритма. Такой процесс можно повторять неограниченное количество раз, подбирая разные границы шкалы, а также количество делений, однако в данной работе, проводилось две итерации. На первой определялось самая продуктивная доля десятков, а после этого на второй итерации определялась самая продуктивная доля тысячных. Более точная настройка позволяет производить тюнинг модели с последующим улучшением качества.



8. Проведение тестирований

Результат работы алгоритма проверялся тремя способами:

Формирование несуществующих словоформ и исследование процента выявления таких слов моделью.

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

Парсинг статей википедии, проверка слов волонтерами и построенным алгоритмом, с дальнейшем сравнением результатов.

Перед тем, как описывать различные варианты проверки, необходимо описать как формируется оценка качества работы алгоритма. При оценки учитывается две характеристики:

Процент правильных слов, которые распознаны как правильные.

Процент неправильных слов, которые определены как неправильные.

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

Рассмотрим отдельно каждый метод и полученные результаты.

8.1 Проверка на сгенерированных словоформах

Для проведения первого эксперимента был написан код, который формирует слова на основе полученного слова и башкирского алфавита. На вход алгоритма поступает слово из корпуса и количество символов, которые необходимо изменить в слове. Программа генерирует случайный индекс символа слова, после чего заменяет букву под данным индексом на случайный символ из алфавита. Затем, проверяется, не входит ли это слово в слова корпуса, чтобы убедиться в том, что сформированная словоформа действительно некорректная. Когда сформирован список неправильных слов, формируем список правильных словоформ, который по объему равен списку неверных слов. После этого, проверяем работу на сформированных списках, чтобы получить результат. После этого высчитываем процент определения, и медиану значений качества работы алгоритма для получения общей оценки. Данная методика использовалась для первичной проверки работы алгоритма и не принималась за показательную.

8.2 Проверка на OCR текстах

В качестве материала был предоставлен корпус текстов, распознанных с помощью, а также проверенные вручную людьми версии данных текстов. Для составления выборки правильных и неправильных слов, была написана программа, которая находит разницу между двумя двух текстами. Существующие программы и алгоритмы нахождения разницы текстов позволяют найти и отобразить фрагменты текста, которые уникальны для каждого текста, а также фрагменты, которые остались без изменения. Для решения нашей задачи, это является избыточной информацией. Наша программа позволяет составить словарь текста, в котором хранятся правильные и неправильные слова. Правильные слова - это словоформы, которые встречаются как в распознанном с помощью OCR технологии тексте, так и проверенном человеком тексте. Неправильные словоформы - Это словоформы которые уникальны для текста, распознанного с помощью технологии OCR. После составления списков слов, производится такой же алгоритм проверки, как и при первом методе, рассчитывается соотношение определения правильных и неправильных слов, после чего вычисляется медиана для получения общего значения качества работы алгоритма. При тестировании на значении доли для порогового значения от 0.1 до 1 получаются результаты:



Таблица 1. Качество работы алгоритма на OCR данных при разных долях порогового значения от 0 до 1

При более точном вычислении долей в диапазоне от 0.4 до 0.5:

Наилучшее качество работы алгоритма при проверке текстов, распознанных с помощью технологии OCR достигается с пороговой долью 0,477. Результаты в количестве словоформ и долях соответственно:

Таблица 2. Наилучшая точность работы алгоритма на OCR данных с пороговой долей 0.477

		Изначальный статус словоформы
		Словоформа верна кол-во (доля)	Словоформа не верна кол-во (доля)
Предсказание модели	Словоформа верна кол-во (доля)	8904 (0.829)	309 (0.602)
	Словоформа не верна кол-во (доля)	1843 (0.171)	204 (0.398)

8.3 Проверка на статьях башкирской википедии

Проверка качества работы алгоритма на текстах статей башкирской Википедии, является самым показательной характеристикой. Это обусловлено тем, что статьи на данном сайте пишутся реальными людьми, которые совершают ошибки, характерные для пользователей устройств, на которых можно использовать спелл-чекеры. Для начала, необходимо загрузить из интернета статьи. Размер статей составляет минимум 250 слов. Также, программа по загрузке текстов определяет процент уникальных словоформ, для того чтобы избежать шаблонных статей, а также собрать максимально репрезентативную выборку. Итого, было загружено 7 текстов, в состав которых входит суммарно 1200 уникальных словоформ. После составления списка уникальных словоформ, данные публикуются на сервисе онлайн таблиц, где волонтеры, работающие с башкирским языком, оставляют свои суждения по поводу приемлемости представленных словоформ. Также в таблице присутствует поле для того, чтобы волонтеры несогласные с уже существующей оценкой могли оставить свои пометки или добавить комментарии.

После разметки данных, список словоформ проверяется созданным алгоритмом проверки и результаты сравниваются с результатами разметки волонтеров. Оценка качества идет в соответствии с другими вариантами тестирования. При тестировании на долях в диапазоне от 0 до 1:

Таблица 3. Качество работы алгоритма на данных википедии при разных долях порогового значения от 0 до 1

При более точном вычислении долей в диапазоне от 0.45 до 0.55:

Наилучшее качество работы алгоритма при проверке текстов, собранных с сайта башкирской википедии достигается с пороговой долью 0,505. Результаты в количестве словоформ и долях соответственно:



Таблица 4. Наилучшая точность работы алгоритма на текстах с википедии, с пороговой долей 0.505

		Изначальный статус словоформы
		Словоформа верна кол-во (доля)	Словоформа не верна кол-во (доля)
Предсказание модели	Словоформа верна кол-во (доля)	724 (0.752)	53 (0.484)
	Словоформа не верна кол-во (доля)	167 (0.248)	42 (0.516)



9. Результат работы

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

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



10. Варианты улучшение качества работы алгоритма

10.1 Использование уникальных словоформ при формировании вероятностей

Изначально при подсчете вероятностей конструкций башкирского корпуса использовались все токены, входящие в тексты. После проведения тестов, было сделано предположение, что использование только уникальных словоформ корпуса должно повысить качество работы алгоритма.

Это суждение обосновывалось тем, что несмотря на независимость разработанного алгоритма от корпусной тематики, существует проблема частого употребления редких конструкций. Предположим, что в тексте необходимо употребляется и частое повторение словоформы с нехарактерной для Башкирского языка конструкцией. Таким образом, при подсчете вероятностей, такая конструкция может быть принята за нормальную и вытеснить из зоны допускаемы вероятностей корректные варианты. Таким же образом на качество работы алгоритма влияют и заимствованные слова. Если учитывать только уникальные словоформы, тогда можно решить проблему с частым употреблением нехарактерных и заимствованных слов.

Однако, повторные тесты на обновленном корпусе показали обратный результат. Качество работы модели незначительно, но ухудшилось. После проведения анализа результатов, выяснилось, что качество упало из-за увеличения общей доли заимствованных слов.

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

Решением данной проблемы, является исключение заимствованных слов из выборки обучения, что является сложным процессом. В результате, был сделан вывод, что при работе с Башкирским языком, как с языком с большим количеством заимствованных слов, в рамках нашей задачи будут использоваться все токены, входящие в состав корпуса, а не только уникальные словоформы.

10.2 Улучшение работы качества при помощи стемминга текстов

Второе предположение по поводу улучшения качества работы алгоритма, это использование методов стемминга словоформ при подсчете вероятностей и непосредственно во время проверки. Стемминг - это процесс нахождения основы исходной словоформы. Проблема автоматического стемминга представляет собой этап предобработки текста в лингвистических исследованиях. По этой причине, для большинства “популярных” языков, например английского и русского, уже существуют готовые решения стемминга. Для башкирского языка, готового решения, которое бы подходило для решения нашей проблемы, нет.

Для произведения стемминга текстов в рамках нашей задачи написана собственная программа, которая работает на основе жадных алгоритмов регулярных выражений. Первоначально формирует список всех возможных аффиксов в башкирском языке. После этого, когда на обработку поступает слово, программа проверяет, есть ли на конце словоформы группа символов, схожая с аффиксом из сформированного списка. Если вхождения есть, тогда данная группа символов отделяется от словоформы и помещается в хранение аффиксных групп этой проверки. Процесс повторяется до тех пор, пока пересечений конечных символов остаточной словоформы и аффиксной группы не обнаружено. По окончанию работы, программа возвращает объект-словарь в котором хранится изначальная словоформа, основа и отделенная аффиксная группа.

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

Однако тесты показали, что данная методика, не помогает в улучшении точности работы алгоритма. Это происходит по той причине, что выравнивание вероятностей по шкале частотности не повышает качество работы модели с нашим алгоритмом. Если представить это распределение без использования стемминга, тогда выделяются три основные группы:

Конструкции, которые входят в аффиксные группы - самые вероятные комбинации.

Конструкции, которые нехарактерны для башкирского языка - группа с минимальной вероятностью.

Конструкции, которые характерны для башкирского языка - группа, вероятности которой распределены между двумя предыдущими группами.

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



10.3 Улучшение работы алгоритма при помощи группировки слов по их природе

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

Мы предполагаем, что точность работы разработанной нашей программы можно улучшить посредствам введения дополнительных этапов проверки с дальнейшим распределением слов по разным потокам проверки. На дополнительном этапе проверки, определяется природа происхождения слова. Дальше, для каждой группы слов, обучается самостоятельная модель, которая определяет приемлемость словоформы в парадигме группы, к которой она принадлежит. Таким образом, получится добиться максимальной точности работы алгоритма, поскольку будет решена проблема с шумом в виде малой вероятности для характерных конструкций, а также неравного распределения из-за смешения нескольких словесных групп.



Библиография

1. Митрофанова О.А., Захаров В.П. (б. д.). Извлечено от http://www.dialog-21.ru/media/1599/49.pdf.

2. Усилин C.А., Николаев Д.П., Постников В.В. (б. д.). Извлечено от http://www.isa.ru/proceedings/images/documents/2009-45/159-173.pdf.

3. Chatterjee, R., Athayle, A., Akhawe, D., Juels, A., & Ristenpart, T. (2016). pASSWORD tYPOS and How to Correct Them Securely. 2016 IEEE Symposium on Security and Privacy (SP), 799-818. https://doi.org/10.1109/SP.2016.53.

4. Choudhury, M., Thomas, M., Mukherjee, A., Basu, A., & Ganguly, N. (2007). How Difficult is it to Develop a Perfect Spell-checker? A Cross-linguistic Analysis through Complex Network Approach. arXiv:physics/0703198. Извлечено от http://arxiv.org/abs/physics/0703198.

...