Участник:MelLain/ЕМ-алгоритм (Тематическое моделирование)
Содержание
- 1 Свойства и структура алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
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 Информационный граф
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].
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 Особенности параллельной реализации алгоритма
Как уже было отмечено, в описанном алгоритме большая часть вычислений приходится на Е-шаг (в экспериментах он занимал более 99% времени работы). Поэтому именно он был выбран в качестве объекта для реализации параллелизма. Общую схему можно описать следующим образом. Вместо того, чтобы обрабатывать документы в цикле последовательно, можно делать это параллельно, поскольку для описанного алгоритма обработки разных документов являются независимыми операциями. Таким образом, входные данные, то есть документы, разбиваются на пакеты, в каждом из которых находится фиксированное количество документов, каждый пакет сохраняется на диск в виде отдельного файла, все файлы хранятся в одной директории, подаваемой на вход алгоритму. Далее алгоритм перед началом очередной итерации прохода по коллекции просматривает рабочую директорию и сохраняет в специальную очередь имена файлов с документами. Перед началом каждой итерации производится создание нескольких параллельных потоков-обработчиков, каждый из которых занимается вычислением Е-шага. Для этого каждый обработчик, не занятый в текущий момент времени, проверяет очередь с именами файлов на наличие в ней необработанных пакетов, и, в случае присутствия таких, извлекает очередное имя файла, открывает сам файл и последовательно обрабатывает все находящиеся в нём документы. Имя обрабатываемого файла из очереди удаляется. Итерация заканивается тогда, когда все обработчики завершили свою работу. На этом параллельный Е-шаг завершается, алгоритм производит последовательный М-шаг, и либо завершается, либо начинает новую внешнюю итерацию.
2.4 Масштабируемость параллельной реализации алгоритма
Данная параллельная реализация тестировалась на компьютере со вычислительными следующими характеристиками:
Intel(R) Core(TM) i7-5820K @ 3.30GHz (6 физических ядер, 12 потоков, без использования аппаратного ускорения ядер).
Соответственно, максимальное количество параллельных обработчиков было равно 12. В качестве входных данных использовалась коллекция писем Х. Клинтон (точнее, её подмножество из 6000 тысяч писем, т. е. больше 80%). Вся коллекция, как было отмечено выше, делится на текстовые файлы, в каждом файле одна строка соответствует одному документу. Единицей параллелизма является файл.
Измеряемыми параметрами масштабируемости являются:
- количество тем;
- размера пакета документов (регулирует единоразовую нагрузку на один поток-обработчик);
- количество потоков-обработчиков.
Число внутренних итераций зафиксируем равным 5. Внешних - 10.
Измеряемым параметром является время работы алгоритма без учёта вспомогательных операций (сбор словаря коллекции, который реализация умеет производить однократно и далее переиспользовать сохранённый на диск результат). Для каждого фиксированного числа тем и размера пакета строится двумерный график зависимости времени работы от числа потоков, т.е. график масштабируемости алгоритма.
ToDo(MelLain)
Реализация алгоритма на языке C++ (STL, Boost)
2.5 Существующие реализации алгоритма
Наиболее близкой (хотя далеко не идентичной) реализацией описанного алгоритма является ЕМ-алгоритм для тематического моделирования из бибилиотеки BigARTM. Там реализован полноценный онлайновый ЕМ-алгоритм с относительно сложной архитектурой распараллеливания, позволяющий добиться эффективной онлайновой обработки огромных текстовых коллекций на одной машине.
Существуют и другие программные реализации алгоритмов для тематического моделирования, но большинство из них не использует ЕМ-алгоритм, или же использует его вариационный вариант, который здесь не рассматривается.
