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

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

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

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

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

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

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

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

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

[math] \begin{align} F \approx \Phi \times \Theta \end{align} [/math]

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

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

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

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

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

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

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

[math] \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} [/math]

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

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

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

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

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

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

[math] \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} [/math]

[math] \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} [/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.7 Информационный граф

ToDo(Заночкин)

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

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

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

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

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

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

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

• Матрица модели [math]\Phi[/math], то есть распределений слов в полученных темах (если добавить кэширование матрицы [math]\Theta[/math], то можно сразу получить и её, хотя это скажется на объёме потребляемой памяти).

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

• [math]|W|\times|T| \big(+ |T|\times|D| \big)[/math].

1.9 Свойства алгоритма

ToDo(Заночкин)

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

В простейшем варианте (без внутренних итераций по [math]\theta_d[/math] и с хранением всех этих векторов) алгоритм без применения параллелизма и векторизации на языке Python выглядит следующим образом:

# Author: Murat Apishev (great-mel@yandex.ru)

def plsa_em(n_dw, num_topics, max_outer_iter, Phi_init, Theta_init):
    num_tokens, num_docs = n_dw.shape
    Phi = Phi_init if not Phi_init is None else init_matrix(num_tokens, num_topics)
    Theta = Theta_init if not Theta_init is None else init_matrix(num_topics, num_docs)

    for i in xrange(max_outer_iter):
        time_start = time.time()
        n_wt = np.zeros([num_tokens, num_topics]);
        n_t = [0] * num_topics
        Theta_new = np.array(Theta)

        for d in xrange(num_docs):
            Z_w = [0] * num_tokens
            for w in xrange(num_tokens):
                z_w = 0.0
                for t in xrange(num_topics):
                    z_w += Phi[w, t] * Theta[t, d]
                Z_w[w] = z_w

            for t in xrange(num_topics):
                value = 0.0
                for w in xrange(num_tokens):
                    if Z_w[w] < EPS:
                        continue

                    value += n_dw[w, d] * Phi[w, t] * Theta[t, d] / Z_w[w]

                denominator = np.sum(n_dw[:, d])
                if denominator < EPS:
                    continue

                Theta_new[t, d] = 1.0 / np.sum(n_dw[:, d]) * value

            for w in xrange(num_tokens):
                for t in xrange(num_topics):
                    if Z_w[w] < EPS:
                        continue

                    value = n_dw[w, d] * Phi[w, t] * Theta[t, d] / Z_w[w]
                    n_wt[w, t] += value
                    n_t[t] += value

        Phi = n_wt / n_t
        Theta = Theta_new
    return Phi, Theta

2.2 Локальность данных и вычислений

ToDo(Заночкин)

2.3 Масштабируемость реализации алгоритма

Данная параллельная реализация тестировалась на компьютере с 6 физическими ядрами (12 потоков), соответственно, максимальное количество параллельных обработчиков было равно 12. В качестве входных данных использовалась коллекция писем Х. Клинтон (точнее, её подмножество из 6000 тысяч писем, т.е. больше 80%). Коллекция применялась как в исходном виде, так и в искусственно увеличенном за счёт копирования тех же самых текстов. Далее при измерении масштабируемости будут рассматриваться количество раз, в которое был увеличен объём исходной коллекции. При этом вся коллекция делится на текстовые файлы, в каждом файле одна строка соответствует одному документу. Единицей параллелизма является файл, то есть рабочий поток забирает из очереди данных имя очередного файла для обработки, если очередь ещё не пуста.

ToDo(MelLain)

Реализация алгоритма на языке C++ (STL, Boost)

2.4 Существующие реализации алгоритма

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

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

3 Литература

1. Статья о ТМ на Википедии

2. Статья о ТМ на machinelearning.ru

3. Инструменты для обработки текстов