DOI: 10.12731/wsd-2015-8.2-5 УДК 004
АЛГОРИТМ ПОСТРОЕНИЯ СЕМАНТИЧЕСКОГО ЯДРА ДЛЯ ТЕКСТОВОГО КЛАССИФИКАТОРА
Бондарчук Д.В.
Многие методы машинного обучения, основаны на так называемом «мешке слов» (bag of words): каждый документ представляется, как вектор c численным значением компоненты для каждого терма, содержащий все слова, представленные в обучающей подборке текстов. Каждая компонента данного вектора отражает частоту появления терма в документе. Однако, такой подход имеет несколько существенных недостатков:
- отображает словосочетания в разные сущности;
- отображает синонимы в разные сущности;
- отображает полимонимы в одинаковые сущности.
В статье предлагается другой подход, основанный на построении семантического ядра. В этом случае можно избежать явного вычисления вектора признаков для каждого терма. Одним из ключевых достоинств данного подхода является его модульность: разграничение собственно алгоритма анализа данных от статистического анализа, необходимого на предварительном этапе. Основная идея применения методов, основанных на сборе семантического ядра - переход к новому семантическому пространству, размерность которого меньше размерности исходного пространства.
Ключевые слова: data-mining; text-mining; семантическое ядро; интеллектуальный анализ данных; интеллектуальный анализ текстов; векторная модель представления знаний.
AN ALGORITHM FOR BUILDING A SEMANTIC KERNEL FOR A TEXT CLASSIFIER
Bondarchuk D.V.
Many machine learning methods are based on a so-called "bag of words": each document is represented as a vector with a numerical value of the component for each term that contains all the words presented in the training set of texts. Each component of the vector represents the frequency of occurrence of the term in the document. However, this approach has several significant disadvantages. It:
- represents word-combinations in different entities;
- represents synonyms in different entities;
- represents polyhomonyms in the same entities. The article proposes another approach based on building a semantic kernel. In this case, the explicit computation of the feature vector for each term can be avoided. One of the key advantages of this approach is its modularity: separation of the actual algorithm of data analysis from statistical analysis necessary at the preliminary stage. The main idea of application of the methods, based on building a semantic kernel, is the transition to a new semantic space, the dimension of which is fewer than the dimension of the original space.
Keywords: data-mining; text-mining; semantic kernel; knowledge representation vector model.
Введение
Многие методы машинного обучения, основаны на так называемом «мешке слов» (bag of words): каждый документ представляется, как вектор c численным значением компоненты для каждого терма, содержащий все слова, представленные в обучающей подборке текстов. Каждая компонента данного вектора отражает частоту появления терма в документе. Однако, такой подход имеет несколько существенных недостатков:
- отображает словосочетания в разные сущности;
- отображает синонимы в разные сущности;
- отображает полимонимы в одинаковые сущности.
Хотя известные методы, такие, как использование стоп-слов, использование стеммеров и пр. позволяют добиться некоторых улучшений, но, к сожалению, качество обучения остается незначительным.
Методы машинного обучения, основанные на сборе семантического ядра - это относительно новый подход решения проблем обработки текстов на естественном языке. В этом случае можно избежать явного вычисления вектора признаков для каждого терма. Одним из ключевых достоинств данного подхода является его модульность: разграничение собственно алгоритма анализа данных от статистического анализа, необходимого на предварительном этапе. Кроме того, ядра сами по себе имеют модульную структуру, что позволяет с помощью простых правил строить более сложные семантические ядра из более простых таким образом, чтобы они не выходили за границы семантического пространства.
Основная идея применения методов, основанных на сборе семантического ядра - переход к новому семантическому пространству, размерность которого меньше размерности исходного пространства и решение задач (например, классификации) в котором легче [4].
1. Постановка задачи
Предположим у нас есть некоторая обучающая выборка текстов. Представим её в виде таблицы В = {х1,х2,...,хя}, где x. - вектор i-того терма, n - количество термов. Вектор терма представляет собой следующий вектор-столбец:
х,.=mtM^tM^M)}' (!)
где d - документ из обучающей выборки, df - частота встречаемости терма в документе (documentfrequency), l - количество документов, содержащихся в обучающей выборке, t. - i-тый терм.
Необходимо обработать данную подборку текстов таким образом, чтобы, во-первых, была учтена взаимосвязь слов внутри документа,
во-вторых, была учтена проблема синонимии и полисемии. Так же необходимо представить информацию таким образом, чтобы ее можно было использовать в качестве обучающей базы для текстового классификатора.
2. Алгоритм построения семантического ядра
Обучающую информацию, доступную для использования при построении семантического ядра (формула 1) можно представить в виде следующей матрицы, которая состоит их всех возможных скалярных произведений между векторами обучающей выборки. Размерность данной матрицы получится (я*я).
0 = ((х„Х;))1м (2)
Назовем данную матрицу матрицей корреспонденций термов. После того, как матрица построена, можно приступать к следующему шагу, а именно к ее сингулярному разложению.
Матрица составленная из скалярных произведений называется матрицей Грама. Очевидно, что любая такая матрица является симметричной.
2.1. Сингулярное разложение Сингулярное разложение - это математическая операция, раскладывающая матрицу на три составляющие. Сингулярное разложение полученной матрицы Грама можно представить в виде следующей формулы.
G = иБУГ (3)
где О - исходная матрица, и и V - ортогональные матрицы, - диагональная матрица.
Как известно [5], что для любой вещественной (п*п) матрицы А существуют матрицы и и V такие, что
= 5 (4)
где и и V - квадратная вещественная матрица размерности (я*я), 5 - диагональная матрица размерности (я*я). Кроме того, матрицы и и Vявляются ортогональными матрицами, то есть:
ииГ = Е = Е
(5)
или, что тоже самое, их обратные матрицы равны обратным:
ии-1 = Е УУ-1 = Е
(6)
Столбцы матрицы и называются левыми сингулярными векторами матрицы О, столбцы V (или строки УГ) - правыми сингулярными векторами.
Матрица 5 является диагональной матрицей, значения на диагонали которой называются сингулярными коэффициентами матрицы G. Сингулярные коэффициенты всегда строго больше нуля. Так же сингулярные коэффициенты всегда строго больше нуля. Более того, матрицы и и V можно подобрать таким образом, чтобы диагональные элементы 5 выглядели следующим образом:
где г - ранг матрицы G, то есть сингулярный коэффициент в строке матрицы О всегда больше, либо равен коэффициенту в строке ниже. В частности, в случае, если матрица О невырождена, то:
Вычисление сингулярного разложения сводится к вычислению собственных чисел и собственных векторов матриц ОГ и ОГО. Собственные вектора матрицы ОГО - это столбцы матрицы V, а собственные вектора матрицы ОГ - столбцы матрицы и. В качестве сингулярных значений берутся квадратные корни общих собственных чисел матриц ОГО и ОГ. Однако, в случае сингулярного разложения матрицы корреспонденций термов, в качестве исходной матрицы используется квадратная матрица, поэтому количество собственных чисел у матриц ОГ и ОГО будет одинаковым. Количество сингулярных коэффициентов соответствует рангу матрицы О, то есть числу линейно-независимых столбцов.
Таким образом, общий алгоритм сингулярного разложения можно представить следующей последовательностью шагов:
(7)
1> 1> ... I > 0
1 — 2 — п
'1 —
(8)
1. Вычисление матрицы От.
2. Вычисление собственных чисел и собственных векторов матрицы От.
3. Вычисление матрицы ОтО.
4. Вычисление собственных чисел и собственных векторов матрицы ОтО.
5. Вычисление квадратного корня из общих собственных чисел матриц От и ОтО.
6. Составление матриц и, Vи &
Рассмотрим вычисление собственных чисел отдельно. Собственными числами и собственными векторами квадратной матрицы А называются число X и вектор х, такие, что [3]:
Ах = Хх (9)
Данное утверждение можно так же записать следующим способом:
(А - ХЕ)х = 0, х ф 0 (10)
Это означает, что для вычисления собственных чисел достаточно решить следующее уравнение:
1(А - Щ = 0 (11)
Степень получившегося многочлена равна размеру матрицы А. Это означает, что, если матрица А имеет размер (п*п), то она может иметь п собственных чисел. Сам определитель, как и получившийся многочлен, полезны для аналитических рассуждений, однако численное решение уравнения (22) в случае большой размерности матрицы А с помощью программного обеспечения представляет собой очень сложную задачу. Наиболее известным и эффективным способом вычисления собственных чисел и векторов считается метод QR, который был представлен Дж. Уил-кинсоном в 1965 году [7]. Данный алгоритм используется в большинстве известных математических пакетов (например, МайЬаЬ) и библиотек (например, XLispStat).
Для реализации некоторых математических алгоритмов (сингулярное разложение, поиск собственных векторов), использованных в данном исследовании были использованы инструменты библиотеки XlispStat для языка программирования С++. Данная библиотека была разработана Л. Тиерни в университете Минесоты [6]. Она отвечает всем заявленным
требованиям к программному обеспечению, изложенных в данной главе, поскольку реализована на функциональном языке программирования, в результате его работает очень быстро.
Основная идея применения сингулярного разложения состоит в том, что часть матрицы Грама содержащая только k линейно независимых компонент, отражает основную структуру зависимостей, присутствующих в исходной матрице. Таким образом, термы, которые чаще встречаются в корпусе, получ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.