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

Оставшаяся часть разбивается по символам и нумеруется. Отсчет начинается со второго символа. Дальше, для каждой буквы с индексом (номером) “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

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

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

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

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

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