Участник:Kruglikov/PLSA: различия между версиями
Kruglikov (обсуждение | вклад) (Структура) |
Kruglikov (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 4: | Строка 4: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| + | Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые ''темами''. Неформально под ''темой'' понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов <math>p(w|t)</math>, а ''тематикой документа'' называется условное распределение <math>p(t|d)</math>. Переменная <math>t</math> является скрытой. Таким образом, задача тематического моделирования — оценить вероятности <math>p(w|t)</math> и <math>p(t|d)</math> по наблюдаемым частотам <math>p(w|d)</math> слов в документах. | ||
| + | |||
| + | Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки ''EM-алгоритмом''. В применении к тематическому моделированию такой подход называется ''probabilistic latent semantic analysis'' — PLSA. | ||
| + | |||
| + | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| + | ====Обозначения==== | ||
| + | Пусть <math>D</math> — конечное множество документов, <math>W</math> — конечное множество терминов, <math>T</math> — конечное множество тем. | ||
| + | |||
| + | <math>(d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T</math> — коллекция текстовых документов. | ||
| + | |||
| + | Тематическая модель коллекции: <math>p(w|d) = \sum_{t \in T} p(w|t)p(t|d) = \sum_{t \in T} \phi_{wt} \theta_{td}</math> | ||
| + | |||
| + | Задача состоит в том, чтобы найти параметры <math>\phi_{wt}</math> и <math>\theta_{td}</math> | ||
| + | |||
| + | |||
| + | Введём набор счётчиков: | ||
| + | |||
| + | <math>n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t]</math> — частота <math>(d_i, w_i, t_i)</math> в коллекции; | ||
| + | |||
| + | <math>n_{wt} = \sum_{d} n_{dwt}</math> — частота термина <math>w</math> в теме <math>t</math>; | ||
| + | |||
| + | <math>n_{td} = \sum_{w} n_{dwt}</math> — частота терминов темы <math>t</math> в документе <math>d</math>; | ||
| + | |||
| + | <math>n_{t} = \sum_{d, w} n_{dwt}</math> — частота терминов темы <math>t</math> коллекции; | ||
| + | |||
| + | <math>n_{dw} = \sum_{t} n_{dwt}</math> — частота термина <math>w</math> в документе <math>d</math>; | ||
| + | |||
| + | <math>n_{w} = \sum_{d, t} n_{dwt}</math> — частота термина <math>w</math> в коллекции; | ||
| + | |||
| + | <math>n_{d} = \sum_{w, t} n_{dwt}</math> — длина документа <math>d</math>; | ||
| + | |||
| + | <math>n = \sum_{d, w, t} n_{dwt}</math> — длина коллекции. | ||
| + | |||
| + | |||
| + | ====EM-алгоритм в PLSA==== | ||
| + | В модели PLSA предлагается максимизировать правдоподобие | ||
| + | |||
| + | <math>\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>\phi_{wt} \le 0; \sum_{w \in W} \phi_{wt} = 1; \theta_{td} \le 0; \sum_{t \in T} = 1.</math> | ||
| + | |||
| + | Утверждается, что точка максимума правдоподобия удовлетворяет системе уравнений | ||
| + | |||
| + | <math> | ||
| + | \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-шаги до сходимости. | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
| Строка 12: | Строка 67: | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
| + | [http://www.machinelearning.ru/wiki/images/2/20/Voron-PTM-1.pdf Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)] | ||
[[en:Description of algorithm properties and structure]] | [[en:Description of algorithm properties and structure]] | ||
Текущая версия на 23:28, 2 ноября 2017
Общая схема описания алгоритмов имеет следующий вид:
Содержание
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые темами. Неформально под темой понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов [math]p(w|t)[/math], а тематикой документа называется условное распределение [math]p(t|d)[/math]. Переменная [math]t[/math] является скрытой. Таким образом, задача тематического моделирования — оценить вероятности [math]p(w|t)[/math] и [math]p(t|d)[/math] по наблюдаемым частотам [math]p(w|d)[/math] слов в документах.
Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки EM-алгоритмом. В применении к тематическому моделированию такой подход называется probabilistic latent semantic analysis — PLSA.
1.2 Математическое описание алгоритма
1.2.1 Обозначения
Пусть [math]D[/math] — конечное множество документов, [math]W[/math] — конечное множество терминов, [math]T[/math] — конечное множество тем.
[math](d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T[/math] — коллекция текстовых документов.
Тематическая модель коллекции: [math]p(w|d) = \sum_{t \in T} p(w|t)p(t|d) = \sum_{t \in T} \phi_{wt} \theta_{td}[/math]
Задача состоит в том, чтобы найти параметры [math]\phi_{wt}[/math] и [math]\theta_{td}[/math]
Введём набор счётчиков:
[math]n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t][/math] — частота [math](d_i, w_i, t_i)[/math] в коллекции;
[math]n_{wt} = \sum_{d} n_{dwt}[/math] — частота термина [math]w[/math] в теме [math]t[/math];
[math]n_{td} = \sum_{w} n_{dwt}[/math] — частота терминов темы [math]t[/math] в документе [math]d[/math];
[math]n_{t} = \sum_{d, w} n_{dwt}[/math] — частота терминов темы [math]t[/math] коллекции;
[math]n_{dw} = \sum_{t} n_{dwt}[/math] — частота термина [math]w[/math] в документе [math]d[/math];
[math]n_{w} = \sum_{d, t} n_{dwt}[/math] — частота термина [math]w[/math] в коллекции;
[math]n_{d} = \sum_{w, t} n_{dwt}[/math] — длина документа [math]d[/math];
[math]n = \sum_{d, w, t} n_{dwt}[/math] — длина коллекции.
1.2.2 EM-алгоритм в PLSA
В модели PLSA предлагается максимизировать правдоподобие
[math]\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]\phi_{wt} \le 0; \sum_{w \in W} \phi_{wt} = 1; \theta_{td} \le 0; \sum_{t \in T} = 1.[/math]
Утверждается, что точка максимума правдоподобия удовлетворяет системе уравнений
[math] \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-шаги до сходимости.
2 Программная реализация алгоритма
3 Литература
Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)
