Об эффективности использования байесовского классификатора в задаче идентификации языка текста по биграммам

Авторы: Д. А. Бронников
Источник: Омский государственный университет путей сообщения:Динамика систем, механизмов и машин, № 1, 2016. Том 4 – г. Омск: 2016 год. – с.5–7 [Ссылка]

Аннотация: В статье рассматривается эффективность классификации языковой принадлежности текстов на иностранных языках с помощью алгоритма классификации Байеса. Целью данного исследования является анализ эффективности использования Байесовского классификатора для идентификации языка текста. В задачи исследования входит сравнительный анализ эффективности существующих методов классификации языковой принадлежности текстов, реализация и обучение Байесовского классификатора для идентификации языка текста. Полученные результаты – точность классификации не менее 90% при длине текста от 60 до 175 знаков, в зависимости от распознаваемого языка. Хотя Байесовский классификатор и проигрывает существующим более сложным алгоритмам по минимальной необходимой для классификации длине текста, благодаря простоте реализации он может использоваться в менее требовательных по длине текста задачах.

Ключевые слова: классификация языка текста, классификатор Байеса, биграммы.

Введение

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

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

Анализ патентов за период с 2003-го по 2013 год по заданной теме показал, что в настоящее время среди известных методов автоматической идентификации текста наиболее популярными являются такие методы, как словарный метод, метод выявления в тексте коротких функциональных слов, характерных для языка, метод выявления специфичных сочетаний букв и марковские N-граммные модели. По отдельности, каждый из этих методов показывает точность идентификации текстов в пределах 95–98% для текстов, длина которых составляет более 100 символов, 85–95% для текстов длиной от 20 до 100 символов, при работе с более короткими текстами точность определения языка резко падает вплоть до 60–65% [1–8].

Теория

В данной статье рассматривается эффективность использования классификатора Байеса для решения этой задачи. Введем несколько обозначений: 𝑊 – множество классов; 𝑋– множество признаков; 𝑃 (w_j∈ 𝑊) – предположение о вероятности w_j до учета экспериментальных данных; 𝑃 (x ∈ w_j) – вероятность появления признака 𝑥, если он принадлежит классу w_j; 𝑃(w_j|x) – вероятность попадания признака 𝑥 в класс w_j

– вероятность попадания признаков x₁, … , x_n в класс w_j

- вероятность появления признаков x₁, … , x_n если они принадлежат классу w_j

Процесс обучения классификатора сводится к нахождению множества условных вероятностей. Обучающей выборкой служат тексты достаточной длины (в данном исследовании брались тексты не менее 100000 знаков), по которым строятся распределения N самых часто встречающихся биграмм в языках. Пусть дан текст на неизвестном языке. Задача классификации текста на неизвестном P_max = max_{wj∈ w}P(w_j|( x₁, … , x_n))языке сводится к нахождению. Данное выражение приводится к следующему виду:

Для классификации текста необходимо построить распределение частот появления в нем н-грамм из множества Х. Затем для каждой биграммы находятся вероятности их появления в текстах на заданных языке. После этого по следующей формуле рассчитываются промежуточные вероятности для множества биграмм ( x₁, … , x_n):

P_prevj = P(w_maj)P_prevj где – вероятность для j класса с предыдущей итерации (для первой итерации)
P_max = max_{wj∈ w}P(w_j) после N итераций необходимо найти.

Результаты экспериментов

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

В качестве обучающей выборки были взяты тексты общим объемом не менее 100000 знаков для каждого языка.

Для обучения классификатора каждый из текстов разбивался на 1000 образцов длиной 300 знаков каждый. Затем для каждой биграммы строилось распределение вероятностей (рис. 1, 2).

Для самого эксперимента были взяты по 100 текстов с длинами от 40 до 400 знаков для каждого языка. Каждый из этих текстов был проанализирован предварительно обученным классификатором на языковую принадлежность. После чего были построены зависимости вероятностей распознавания языка текста от его длины.

По результатам данного исследования было получено, что правильная классификация языковой принадлежности текстов на основе биграмм с помощью описанного подхода с точностью не менее 90% достигается при длине текста от 60 до 175 символов, в зависимости от распознаваемого языка:

1. английский язык - длина текста 85 символов;
2. испанский язык - длина текста 175 символов;
3. итальянский язык - длина текста 60 символов;
4. немецкий язык - длина текста 95 символов;
5. русский язык - длина текста 130 символов;
6. французский язык - длина текста 155 символов;

Выводы

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

СПИСОК ЛИТЕРАТУРЫ

1. Пат 2251737 Российская Федерация. Способ автоматического определения языка распознаваемого текста при многоязычном распознавании /Анисимович К. В., Терещенко В.В., Рыбкин В.Ю. 10.05.2005.
2. Li Kang, Kloder Stephen Allen, Johnson Ian George, Alochau Siarhei Идентификация языка в многоязычных текстах / Microsoft Corporation, WO2012050743A2. 20.03.2008.
3. Powell Kevin R., Ramsey William D., Schmid Patricia M.. Эффективное определение языка / Microsoft Corporation EP1691299A2. 10.05.2009.
4. Bi Yan, Sienel Jürgen, Müller Wofgang. Метод идентификации языка с использованием N-грамм и списков коротких слов / Alcatel EP1612695A1. 04.01.2006.
5. Suontausta Janne, Tian Jilei. Идентификация языка текста с помощью масштабируемых нейронных сетей / Nokia Corporation EP1554670A1. 20.07.2005.
6. Barliga Bogdan, Harju Mikko A, Iso-Sipila Juha. Способ, устройство и компьютерный программный продукт для обеспечения гибкой идентификации языка текста / Nokia Corporation WO2008075161A3. 13.11.2008.
7. Kolo Brian Andrew. Методы и системы для автоматической идентификации языка / US7818165B2. 27.09.2012.
8. Fux Vadim, Kolomiets Sergey. Метод определения языка текста для портативных электронных устройств / Research In Motion Limited. US8423908B2. 16.04.2013.