Файл: Основы проектирования программ. Этапы создания программного обеспеченияКурсовая работа.pdf

Таблица 1

Матрица ошибок

Сразу стоит внести ясность, почему мы отказываемся от использования метрики accuracy (точность), которая вычисляется как доля объектов, для которых правильно предсказан результат, из всех объектов. При неравенстве классов эта метрика перестаёт быть достоверной.

Precision – это доля всех объектов, которые в самом деле принадлежат данному классу, из всех объектов, которые были отнесены к этому классу классификатором. Вычисляется она по формуле (3):

Precision = TP/(TP+FP) (3)

Recall – это доля объектов, принадлежащих классу и найденных системой, из всех объектов данного класса (4):

Recall = TP/(TP+FN) (4)

F-мера – это метрика, которая позволяет объединить в себе и точность, и полноту благодаря вычислению гармонического среднего (5):

F = 2(Precision*Recall) / (Precision + Recall) (5)

Данная формула придаёт равные веса полноте и точности [12].

Методы предобработки текстов

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

В сфере обработки естественного языка (Natural Language Processing или NLP) существует задача, именуемая word embedding. Основной целью данного раздела NLP является преобразование слов с языка, который понимает человек, в язык, который понимает компьютер [13]. Результатом word embedding является векторное представление слова. Наиболее популярными методами для решения данной задачи являются LSA, Word2Vec и GloVe. Все три подхода основываются на идее того, что описание слова зависит от контекста, в котором он расположен.

LSA

Латентно-семантический анализ (Latent semantic analysis, LSA) [14] – это статистический метод, состоящий из двух этапов:

1. Строится матрица М зависимости слова от документа, где каждая строка соответствует слову, а столбец – документу. Элемент (i, j) матрицы – частота появления i-того слова в j-том документе.

2. Делается сингулярное разложение матрицы М на три матрицы (6). U и V^t – ортогональные матрицы, W – диагональная. Суть этого разложения состоит в том, что оно показывает ключевые элементы матрицы М: меньшие сингулярные значения из диагональной матрицы W соответствуют столбцам и строкам элементов, которые делают наименьший вклад в произведение. Таким образом, для того, чтобы убрать шумы и тем самым уменьшить семантическое пространство, векторы из матриц U и V^t, соответствующие наименьшим сингулярным значениям, удаляются из матриц.

M = U * W * V^t(6)

Этот подход к word embedding основывается на таких главных параметрах, как: локальные и глобальные частоты встречаемости слов и размер семантического пространства.

GloVe

Этот метод был представлен в 2014 году департаментом Компьютерных Наук университета Стенфорд [15]. Сутью этого метода является вычисление частоты появления слова в корпусе текстов. Реализовывается метод в два шага:

1. Создаётся матрица смежностей Х, где каждый её элемент (i, j) – это количество появлений слова i в контексте слова j. Тогда X_i = ∑_k X_ik– количество появлений какого-либо слова в контексте слова i или, иными словами, количество слова i в корпусе.

2. P_ij = P(j|i) = X_ij / X_i – вероятность появления слова j в контексте слова i. Но для построения векторного отображения слов имеет значение не сама вероятность, а коэффициент, который получается при P_ik / P_jk, зависящий от трёх слов i, j, k. Этот скаляр кодирует разность векторов. В более общем виде модель имеет вид (7).

(7)

w ϵ R^d – вектора слов, ϵ R^d– вектор контекстного слова.

Однако, для сохранения линейности и предотвращения смешивания размерностей используется скалярное произведение (8).

(8)

Заметим, что для матрицы смежностей разница между словом и контекстным словом произвольна, и их роли можно свободно менять между собой. Но если делается замена , то должна и происходить замена . Чтобы свойство симметрии выполнялось, необходимо сделать преобразование (9).

(9)

Таким образом, авторы этого подхода решили использовать метод наименьших квадратов. В итоге, формула будет иметь вид (10), где V – размер словаря.

(10)

Word2Vec

Word2Vec – это метод, позволяющий реализовать отображение слов в векторное пространство. Впервые был предложен Миколовым в 2013 году [16]. В его основе лежат две архитектуры – непрерывный мешок слов (Continuous Bag-of-Words или CBoW) и Skip-gram.

Но прежде чем перейти непосредственно к описанию CBoW и Skip-gram, необходимо описать алгоритм работы самого метода. По своей сути Word2Vec состоит из 5 шагов [17]:

1. Вычисляется частота каждого слова в корпусе. Учитывая эти данные, массив отсортировывается.

2. Словарь кодируется двоичным деревом Хаффмана (Huffman binary tree): лексемам с наибольшей частотой присваивается свой двоичный код. Благодаря этому происходит существенное снижение времени работы и вычислительной сложности алгоритма.

Приведём пример, где будут кодироваться не слова, а символы бессмысленной строчки «boop beep beer!» с помощью дерева Хаффмана [17].

Вычислим частоты каждого символа (табл.2).

Отсортируем символы по увеличению частоты (рис.1).

Рис. 1.

Таблица 2

Частоты символов

Возьмём два символа с наименьшей частотой, свяжем их, тем самым создав узел будущего дерева. Вес этого узла будет равен весу этих символов. Поставим его обратно в очередь (рис. 2).

Рис. 2

Далее, выполняя последовательно вышеописанное действие, получим следующие результаты (рис. 3, рис. 4, рис. 5, рис. 6).

Рис. 2

Рис. 3

Рис. 4

Рис. 5

На конечном этапе создаём узел, связывающий оба этих дерева, и проставляем веса для каждого перехода (рис. 7): влево – 0, вправо – 1.

Рис. 7

Таким образом, получили таблицу (табл. 3) с кодом для каждого из символов.

Таблица 3

Таблица Хаффмана

продолжение таблицы 3

3. Осуществляется субсэмплирование (sub-sampling) каждого предложения из корпуса, то есть наиболее часто встречаемые слова удаляются. Таким образом, происходит повышение качества работы будущей модели.

4. Далее по каждому предложению проходят окном (максимальное расстояние между предсказываемым и текущим словом) для формирования блока из n-грам, например, для размера окна равным 3 предложение «Сегодня утро было солнечным» после обработки будет выглядеть так: «сегодня утро было», «утро было солнечным».

5. В работу включаются нейронные сети прямого распространения (сигнал направляется строго от входного к выходному слою), соответствующие CBoW и Skip-gram, с функцией активации иерархический софтмакс (hierarchical softmax) [19]. Его суть заключается в том, что при фиксированном контексте нам интересно только прогнозируемое слово. Формула вероятности, что w – искомое слово (11):

(11)

где L(w) – длина пути в дереве Хаффмана от корня до искомого слова w; n(w,j) – j-ая вершина в этом пути; (x) = 1/(1 + e^-x) –сигмоидальная функция; lch(n) – левый поток вершины; - усредненный вектор контекста при использовании CBoW, - при использовании skip-gram.

Вычисляются при этом также вероятности того, что путь от определенного узла может продолжится как налево, так и направо (12, 13):

(12)

(13)

CBoW основывается на идее, что слова, расположенные в похожих контекстах, имеют одинаковую семантику. Состоит из трёх слоёв (рис. 8):

• Входной слой (input layer). На вход ему подаётся N ближайших соседей исследуемого слова. Они кодируются как one-hot векторы. В NLP one-hot вектор – это вектор размерностью V, состоящий из «0», за исключением одной «1», которая ставится на место k, где k – номер слова в словаре, а V – это размер словаря (рис. 9). Таким образом, мы теряем информацию о последовательности слов в предложении, и именно поэтому этот подход называют мешок слов (bag-of-words). Однако, это не влияет на работу следующего слоя.

Рис. 6. Архитектура нейронной сети CBoW

Рис. 7. One-Hot кодирование

• Слой проекции (projection layer). Каждый нейрон этого слоя представлен строкой матрицы весов, длина которой равняется размеру словаря. Каждое слово из контекста, который был подан на входной слой, проецируется на последний выходной слой с помощью этой матрицы (рис. 10). То есть слову, представленному one-hot вектором, у которого на i-том месте стоит «1», ставится в соответствие i-тый столбец матрицы.

Рис. 8. Пример работы слоя проекции

• Выходной слой (output layer). Получаем вектор слова из слоя проекции.

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

(14)

где V – это размер словаря, с – размер окна, которым проходим по каждому предложению в 4 пункте для получения контекста слова.

Архитектура метода skip-gram точно такая же, как и у CBoW, но вместо предсказывания слова по его контексту этот метод пытается максимизировать классификацию слова на основе другого слова из этого же предложения (рис. 11). Если же выражаться более точно, используется каждое текущее слово в качестве входных данных и прогнозируются слова в определенном диапазоне до и после текущего слова.

Рис. 11. Архитектура нейронной сети skip-gram

Последний этап данного алгоритма основывается на корректировании векторного отображения слов, сравнивая их с каждым словом из контекста, при помощи метода обратного распространения ошибки. Таким образом, осуществляется максимизация уравнения (15):

(15)

Метод CBoW работает быстрее и лучше с наиболее частотными словами для корпусов текстов с большой размерностью. Skip-gram же подходит для небольших корпусов и лучше работает с редкими словами.

Сравнение методов

Задача Microsoft Sentence Completion Challenge была недавно представлена ​​как задача для развития языкового моделирования и других методов NLP [20]. Эта задача состоит из 1040 предложений, где в каждом предложении отсутствует одно слово, и цель состоит в том, чтобы выбрать слово, которое наиболее соответствует остальной части предложения, с учетом списка из пяти разумных вариантов. На этом наборе уже сообщалось о выполнении нескольких методов, в том числе и вышеописанного метода латентно-семантического анализа (LSA). Миколов в своей работе приводит результаты выполнения своих методов для решения этой задачи (табл. 4) [16]. Видим, что точность моделей CBoW и Skip-gram очень близка друг к другу, однако, значительно обходят модель LSA.

Таблица 4

Сравнение моделей в задаче Microsoft Sentence Completion Challenge