Участник:MelLain/ЕМ-алгоритм (Тематическое моделирование)

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

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

1.2 Математическое описание

1.2.1 Математическое описание модели

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

Вероятностная модель PLSA имеет следующий вид:

$\begin{align} F \approx \Phi \times \Theta \end{align}$

Здесь $F$ - это матрица исходных данных размера $|W| \times |D|$, где $D$ - это множество документов, а $W$ - словарь коллекции, т.е. множество всех уникальных слов, встретившихся в документах.

$\Phi$ - это матрица параметров модели размера $|W| \times |T|$, где $T$ - это множество тем, которые мы хотим извлечь из коллекции. Под темой в бытовом смысле смысле понимается набор слов, характеризующих её. Формально говоря, тема - это вероятностное распределение на множестве слов $W$, поэтому матрица $\Phi$ является стохастической, т.е. столбцы её неотрицательны и суммируются в единицу.

$\Theta$ - матрица результатов кластеризации обучающей коллекции по полученным темам размера $|T| \times |D|$, в ней столбцы также являются вероятностными распределениями, на этот раз документов на множестве тем.

Фактически, PLSA есть ни что иное, как задача приближённого стохастического матричного разложения, в ходе которой производится мягкая бикластеризация данных (мягкая - потому что объекты распределяются по классам не строго, а с некоторой вероятностью, би - потому что производится одновременная кластрезация слов по темам, и тем - по документам). Поставленную задачу можно решать методом максимального правдоподобия, с помощью ЕМ-алгоритма.

В данной статье будут расматриваться только плотные матрицы (хотя при определённых условиях можно эффективно использовать разреженные).

1.2.2 Математическое описание ЕМ-алгоритма

Задача максимизации логарифма правдоподобия для описанной модели имеет следующий вид:

$\begin{align} \mathcal{L}(\Phi, \Theta) = \sum_{d \in D}\sum_{w \in d} n_{dw} \,\mathrm{ln}(\sum_{t \in T} \phi_{wt} \theta_{td}) \rightarrow \underset{\Phi, \Theta}{\mathrm{max}} \end{align}$

$\begin{align} \sum_{w \in W} \phi_{wt} = 1, \, \forall t \in T, \quad \phi_{wt} \ge 0; \end{align}$

$\begin{align} \sum_{t \in T} \theta_{td} = 1, \, \forall d \in D, \quad \theta_{td} \ge 0. \end{align}$

Прямая оптимизация логарифма правдоподобия - очень сложная задача, поэтому её решают приближённо с помощью метода простых итераций, в котором чередуются два шага: E (expectation) и M (maximization). Перед первой итерацией выбираются начальные приближения параметров $\Phi$ и $\Theta$.

На Е-шаге по текущим значениям параметров с помощью формулы Байеса вычисляются вспомогательные переменные - условные вероятности $p(t\, | \,d, \,w)$ для всех тем $t \in T$, для каждого термина $w \in d$ для каждого документа $d \in D$:

$\begin{align} p(t\, | \,d, \,w ) = \cfrac{\phi_{wt}\theta_{td}}{\sum_{s \in T}\phi_{ws}\theta_{sd}} \end{align}$

На М-шаге, наоброт, по условным вероятностям $p(t\, | \,d, \,w)$ вычисляется новое приближение параметров $\phi_{wt}$, $\theta_{td}$:

$\begin{align} \phi_{wt} = \cfrac{\hat n_{wt}}{\hat n_t}, \quad \hat n_t = \sum_{w \in W} \hat n_{wt}, \quad \hat n_{wt} = \sum_{d \in D} n_{dw} p(t\, | \,d, \,w ) \end{align}$

$\begin{align} \theta_{td} = \cfrac{\hat n_{dt}}{\hat n_d}, \quad \hat n_d = \sum_{t \in T} \hat n_{dt}, \quad \hat n_{dt} = \sum_{w \in d} n_{dw} p(t\, | \,d, \,w ) \end{align}$

Строгое обоснование данных формул можно получить с помощью теоремы Куна-Таккера.

1.2.3 Общие слова о модернизациях

Как уже было сказано, и как видно из описания выше, данный алгоритм сложно применять на практике в чистом виде из-за необходимости хранения трёхмерной матрицы $p(t\, | \,d, \,w)$ и двумерной матрицы $\Theta$, размеры которых зависят от количества обрабатываемых и данных, которых может быть очень много.

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

В этом варианте алгоритма вычисление $\theta_d$ будет перенесено с М-шага на Е-шаг, и для каждого нового документа этот вектор будет инициализирован равномерным распределением. Для ускорения скорости сходимости можно производить итерации "пересчёт $p(t\, | \,d, \,w)$" - "обновление $\theta_d$" многократно в течении обработки одного документа.

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

1.3 Вычислительное ядро алгоритма

Наиболее вычислительно затратной операцией в данном алгоритме является Е-шаг, в ходе которого рассчитываются вспомогательные переменные и векторы $\theta_d$. С введением внутренних итераций нагрузка на Е-шаг только увеличивается.

1.4 Макроуструктура алгоритма

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

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

1.5 Схема реализации последовательного алгоритма

Приведём здесь листинг описываемого алгоритма:

1. Инициализировать $\phi_{wt}^0$ для всех $w \in W$, $t \in T$;

2. Внешний итерация по коллекции $i = 1 ... num\_outer\_iter$:

3. ____ $n_{wt}^i := 0, n_t^i := 0$ для всех $w \in W$ и $t \in T$;

4. ____ Цикл по документам $d \in D$:

5. ________ Инициализировать вектор $\theta_d^{0}$ для всех $t \in T$ и $Z_w^{0}$ для всех $w \in d$;

6. ________ Внутренняя итерация по документу $j = 1 ... num\_inner\_iter$:

7. ____________ $Z_w^{j}$ := $\sum_{t \in T} \phi_{wt}^{i-1}\theta_{td}^{j-1}$ для всех $w \in d$;

8. ____________ $\theta_{td}^{j}$ := $\cfrac{1}{n_d}\sum_{w \in d} n_{dw} \phi_{wt}^{i-1}\theta_{td}^{j-1} / Z_w^{j}$ для всех $t \in T$;

9. ________ Увеличить $n_{wt}^i$ и $n_t^i$ на $n_{dw}\phi^{i-1}_{wt}\theta_{td}/Z_w$ для всех $w \in W$ и $t \in T$;

10. ____ $\phi_{wt}^i$ := $\cfrac{n_{wt}^i}{n_t^i}$ для всех $w \in W$ и $t \in T$

Здесь $Z_w$ - это сумма всех $p(t \, | \, d, \, w)$ для данного документа, нормировочная константа.

1.6 Последовательная сложность алгоритма

Рассмотрим ЕМ-алгоритм с $num\_outer\_iter$ внешними итерациями и $num\_inner\_iter$ внутренними применительно к набору документов $D$ и слов $W$, классифицирующий коллекцию по темам $T$.

Так на каждой внутренней итерации производится

• умножений: $|W|\cdot|T| + 2|T|\cdot|D|$ ,
• делений : $|T|\cdot(|D| + 1)$,
• сложений: $|W|\cdot(|T|-1) + |T|\cdot(|D| - 1)$.

А значит на одной внешней итерации производится

• умножений: $(|W|\cdot|T| + 2|T|\cdot|D|)\cdot num\_inner\_iter \cdot |D|$ ,
• делений : $|T|\cdot(|D| + 1)\cdot num\_inner\_iter \cdot |D| + |W|\cdot|T|$ ,
• сложений: $\Big(\big[|W|\cdot(|T|-1) + |T|\cdot(|D| - 1)\big]\cdot num\_inner\_iter + |W|\cdot|T|\Big)\cdot |D|$ .

Соответственно для всего алгоритма каждая из этих операций повторяется $num\_outer\_iter$ раз. Наиболее часто выполняется операция умножения, однако порядок величин одинаковый. Разница будет заметна лишь в том случае, когда $|D|$ имеет меньший порядок, чем $|W|$. В этом случае делений будет значительно меньше, чем сложений и умножений.

По классификации по последовательной сложности ЕМ-алгоритм можно отнести к линейным по $num\_inner\_iter, num\_outer\_iter , |T|, |W|$, а попеременной $|D|$ - с квадратичной сложностью.

1.8 Входные и выходные данные алгоритма

Если рассматривать EM-алгоритм на прикладном уровне, но в качестве входных параметров выступает коллекция документов $D$, которая предварительно анализируется и порождает множество слов $W$. Также к входным данным относится набор тем $T$. Поскольку анализ документов и выделение слов являются отдельной задачей, то мы будем полагать, что на вход подаются оцифрованные данные в следующем виде:

Входные данные:

• матрица частот $n_{dw}$, отвечающая количеству слов $w$, встречающихся в документе $d$. По определению элементы этой матрицы могут принимать лишь неотрицательные целые значения.
• пара параметров $num\_outer\_iter, num\_inner\_iter$ и количество тем $|T|$. Эти величины могут быть только положительными целыми числами.

Объём входных данных:

• Матрица частот размером $|W|\times |D|$, а также три скалярные константы.

Выходные данные:

• Матрица результатов кластеризации обучающей коллекции по полученным темам $\Theta$, столбцы которой являются вероятностными распределениями, а значит сумма элементов столбцов должна быть равна единице.

Объём входных данных:

• $|W|\times|D|$.