Участник:Kruglikov/PLSA

Общая схема описания алгоритмов имеет следующий вид:

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

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

Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые темами. Неформально под темой понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов [math]\displaystyle{ p(w|t) }[/math], а тематикой документа называется условное распределение [math]\displaystyle{ p(t|d) }[/math]. Переменная [math]\displaystyle{ t }[/math] является скрытой. Таким образом, задача тематического моделирования — оценить вероятности [math]\displaystyle{ p(w|t) }[/math] и [math]\displaystyle{ p(t|d) }[/math] по наблюдаемым частотам [math]\displaystyle{ p(w|d) }[/math] слов в документах.

Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки EM-алгоритмом. В применении к тематическому моделированию такой подход называется probabilistic latent semantic analysis — PLSA.

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

Обозначения

Пусть [math]\displaystyle{ D }[/math] — конечное множество документов, [math]\displaystyle{ W }[/math] — конечное множество терминов, [math]\displaystyle{ T }[/math] — конечное множество тем.

[math]\displaystyle{ (d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T }[/math] — коллекция текстовых документов.

Тематическая модель коллекции: [math]\displaystyle{ p(w|d) = \sum_{t \in T} p(w|t)p(t|d) = \sum_{t \in T} \phi_{wt} \theta_{td} }[/math]

Задача состоит в том, чтобы найти параметры [math]\displaystyle{ \phi_{wt} }[/math] и [math]\displaystyle{ \theta_{td} }[/math]

Введём набор счётчиков:

[math]\displaystyle{ n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t] }[/math] — частота [math]\displaystyle{ (d_i, w_i, t_i) }[/math] в коллекции;

[math]\displaystyle{ n_{wt} = \sum_{d} n_{dwt} }[/math] — частота термина [math]\displaystyle{ w }[/math] в теме [math]\displaystyle{ t }[/math];

[math]\displaystyle{ n_{td} = \sum_{w} n_{dwt} }[/math] — частота терминов темы [math]\displaystyle{ t }[/math] в документе [math]\displaystyle{ d }[/math];

[math]\displaystyle{ n_{t} = \sum_{d, w} n_{dwt} }[/math] — частота терминов темы [math]\displaystyle{ t }[/math] коллекции;

[math]\displaystyle{ n_{dw} = \sum_{t} n_{dwt} }[/math] — частота термина [math]\displaystyle{ w }[/math] в документе [math]\displaystyle{ d }[/math];

[math]\displaystyle{ n_{w} = \sum_{d, t} n_{dwt} }[/math] — частота термина [math]\displaystyle{ w }[/math] в коллекции;

[math]\displaystyle{ n_{d} = \sum_{w, t} n_{dwt} }[/math] — длина документа [math]\displaystyle{ d }[/math];

[math]\displaystyle{ n = \sum_{d, w, t} n_{dwt} }[/math] — длина коллекции.

EM-алгоритм в PLSA

В модели PLSA предлагается максимизировать правдоподобие

[math]\displaystyle{ \mathcal{L}(\Phi, \Theta) = \sum_{d \in D} \sum_{w \in d} n_{dw} \ln \sum_{t \in T} \phi_{wt} \theta_{dw} \to \max_{\Phi, \Theta} }[/math]

при ограничениях неотрицательности и нормировки

[math]\displaystyle{ \phi_{wt} \le 0; \sum_{w \in W} \phi_{wt} = 1; \theta_{td} \le 0; \sum_{t \in T} = 1. }[/math]

Утверждается, что точка максимума правдоподобия удовлетворяет системе уравнений

[math]\displaystyle{ \begin{cases} n_{dwt} & = & n_{dw} \frac{\phi_{wt}\theta_{td}}{\sum_s \phi_{ws} \theta{ws}}; & \text{(E-шаг)} \\ \phi_{wt} & = & \frac{n_{wt}}{n_t}; n_{wt} = \sum_{d \in D} n_{dwt}; n_t = \sum_w n_{wt}; & \text{(M-шаг)} \\ \theta_{td} & = & \frac{n_{td}}{n_d}; n_{td} = \sum_{w \in d} n_{dwt}; n_d = \sum_t n_{wt} . \end{cases} }[/math]

Эту систему можно решить EM-алгоритмом, применяя последовательно E- и M-шаги до сходимости.

Литература

Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)