Тематическое моделирование

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''Тематическая модель''' (topic model) — модель коллекции текстовых документов, которая определяет, к каким ...)
(Литература)
(29 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
{{TOCright}}
'''Тематическая модель''' (topic model) — модель коллекции текстовых документов, которая определяет, к каким темам относится каждый документ коллекции. Алгоритм построения тематической модели получает на входе коллекцию текстовых документов. На выходе для каждого документа выдаётся числовой вектор, составленный из оценок степени принадлежности данного документа каждой из тем. Размерность этого вектора, равная числу тем, может либо задаваться на входе, либо определяться моделью автоматически.
'''Тематическая модель''' (topic model) — модель коллекции текстовых документов, которая определяет, к каким темам относится каждый документ коллекции. Алгоритм построения тематической модели получает на входе коллекцию текстовых документов. На выходе для каждого документа выдаётся числовой вектор, составленный из оценок степени принадлежности данного документа каждой из тем. Размерность этого вектора, равная числу тем, может либо задаваться на входе, либо определяться моделью автоматически.
'''Тематическое моделирование''' (topic modeling) — построение тематической модели.
'''Тематическое моделирование''' (topic modeling) — построение тематической модели.
-
== Виды тематических моделей ==
+
== Задача построения тематической модели ==
 +
Задана коллекция текстовых документов <tex>D</tex>.
 +
Каждый документ <tex>d</tex> из коллекции <tex>D</tex> представляет собой последовательность слов <tex>W_d=(w_1,\ldots,w_{n_d})</tex> из словаря <tex>W</tex>, где <tex>n_d</tex>&nbsp;— длина документа <tex>d</tex>.
 +
Предполагается, что каждый документ может относиться к одной или нескольким темам.
 +
Темы отличаются друг от друга различной частотой употребления слов.
 +
Требуется найти эти темы, то есть определить
 +
* число тем;
 +
* распределения частот слов, характерное для каждой темы;
 +
* тематику каждого документа — в какой степени он относится к каждой из тем.
-
===Метод главных компонент и неотрицательные матричные разложения===
+
Данная задача может рассматриваться как задача одновременной [[кластеризация|кластеризации]] документов и слов по одному и тому же множеству кластеров, называемых ''темами''.
 +
Обычно строится [[мягкая кластеризация]], то есть документ может принадлежать нескольким темам в различной степени.
 +
 
 +
Целью построения тематической модели может быть как непосредственно выявление множества латентных тем, так и решение различных дополнительных задач.
 +
 
 +
'''Примеры дополнительных задач:'''
 +
* ранжировать документы по степени релевантности заданной теме (тематический поиск);
 +
* ранжировать документы по степени тематического сходства с заданным документом или его фрагментом;
 +
* построить иерархический тематический каталог коллекции документов и выработать правила каталогизации новых документов;
 +
* определить, как темы изменялись со временем (предполагается, что для каждого документа известно время его создания);
 +
* определить тематику авторов (предполагается, что для каждого документа известен список второв);
 +
* определить тематику различных сущностей (entities), связанных с документами (например, журналов, конференций, организаций, стран);
 +
* разбить документ на тематически однородные фрагменты.
 +
 
 +
'''Типичные приложения:'''
 +
* анализ коллекций научных статей;
 +
* анализ новостных потоков;
 +
* [[рубрикация]] коллекций изображений, видео, музыки;
 +
* [[аннотация генома]] и другие задачи [[биоинформатика|биоинформатики]];
 +
* [[коллаборативная фильтрация]].
 +
 
 +
==Латентный семантический анализ==
 +
===Метод главных компонент===
 +
===Неотрицательные матричные разложения===
 +
 
 +
==Вероятностные тематические модели==
 +
Базовые вероятностные тематические модели (probabilistic topic model) основаны на следующих предположениях.
 +
* порядок документов в коллекции не важен;
 +
* порядок слов в документе не важен, документ — «мешок слов» (bag of words);
 +
* слова, встречающиеся в большинстве документов, не важны для определения тематики, их обычно исключают из словаря и называют ''стоп-словами'';
 +
* слово в разных формах — это одно и то же слово;
 +
* коллекцию документов можно рассматривать как [[простая выборка|простую выборку]] пар «документ–слово» <tex>(d,w),\; d\in D,\; w\in W_d</tex>.
 +
* каждая тема <tex>t\in T</tex> описывается неизвестным распределением <tex>p(w|t)</tex> на множестве слов <tex>w\in W</tex>;
 +
* каждый документ <tex>d\in D</tex> описывается неизвестным распределением <tex>p(t|d)</tex> на множестве тем <tex>t\in T</tex>;
 +
* гипотеза условной независимости: <tex>p(w|t,d)=p(w|t)</tex>.
 +
 
 +
Построить тематическую модель — значит, найти матрицы <tex>\Phi = ||p(w|t)||</tex> и <tex>\Theta = ||p(t|d)||</tex> по коллекции&nbsp;<tex>D</tex>.
 +
 
 +
В более сложных вероятностных тематических моделях некоторые из этих предположений заменяются более реалистичными.
 +
Например,
 +
вместо модели «мешка слов» может использоваться марковская цепь;
 +
множество документов может рассматриваться как упорядоченное по времени их создания, и&nbsp;т.&nbsp;д.
===Вероятностный латентный семантический анализ===
===Вероятностный латентный семантический анализ===
 +
{{Main|Вероятностный латентный семантический анализ}}
 +
[[Вероятностный латентный семантический анализ]] (probabilistic latent semantic analysis, PLSA) предложен Томасом Хофманном в 1999 году.
 +
 +
Вероятностная модель появления пары «документ–слово» <tex>(d,w)</tex> может быть записана тремя эквивалентными способами:
 +
::<tex>p(d,w) = \sum_{t\in T} p(t) p(w|t) p(d|t) = \sum_{t\in T} p(d) p(w|t) p(t|d) = \sum_{t\in T} p(w) p(t|w) p(d|t),</tex>
 +
где <tex>T</tex> — множество тем;
 +
:<tex>p(t)</tex> — неизвестное априорное распределение тем во всей коллекции;
 +
:<tex>p(d)</tex> — априорное распределение на множестве документов, эмпирическая оценка <tex>p(d) = n_d/n</tex>, где <tex>n = \sum_d n_d</tex> — суммарная длина всех документов;
 +
:<tex>p(w)</tex> — априорное распределение на множестве слов, эмпирическая оценка <tex>p(w) = n_w/n</tex>, где <tex>n_w</tex> — число вхождений слова <tex>w</tex> во все документы;
 +
 +
Искомые условные распределения <tex>p(w|t),\: p(t|d)</tex> выражаются через <tex>p(t|w),\: p(d|t)</tex> по формуле Байеса:
 +
::<tex>p(w|t) = \frac{p(t|w)p(w)}{\sum_{w'} p(t|w')p(w')};\qquad p(t|d) = \frac{p(d|t)p(t)}{\sum_{t'} p(d|t')p(t')}.</tex>
 +
 +
Для идентификации параметров тематической модели по коллекции документов применяется принцип максимума правдоподобия, который приводит к задаче максимизации функционала
 +
::<tex>\sum_{d\in D} \sum_{w\in d} n_{dw}\log p(w|d) \to \max_{\Phi,\Theta} ,</tex>
 +
при ограничениях нормировки
 +
::<tex>\sum_w p(w|t) = 1,\; \sum_t p(t|d) = 1,\; \sum_t p(t) = 1,</tex>
 +
где <tex>n_{dw}</tex> — число вхождений слова <tex>w</tex> в документ <tex>d</tex>.
 +
 +
Для решения данной оптимизационной задачи обычно применяется [[EM-алгоритм]].
 +
 +
'''Основные недостатки PLSA:'''
 +
* Число параметров растёт линейно по числу документов в коллекции, что может приводить к [[переобучение|переобучению]] модели.
 +
* При добавлении нового документа <tex>d</tex> в коллекцию распределение <tex>p(t|d)</tex> невозможно вычислить по тем же формулам, что и для остальных документов, не перестраивая всю модель заново.
===Латентное размещение Дирихле===
===Латентное размещение Дирихле===
 +
Метод латентного размещения Дирихле (latent Dirichlet allocation, LDA) предложен Дэвидом Блеем в 2003 году.
 +
В&nbsp;этом методе устранены основные недостатки PLSA.
-
===Ненаправленные модели===
+
Метод LDA основан на той же вероятностной модели
 +
::<tex>p(d,w) = \sum_{t\in T} p(d) p(w|t) p(t|d),</tex>
 +
при дополнительных предположениях:
 +
* векторы документов <tex>\theta_d = \bigl(p(t|d):\: t\in T\bigr)</tex> порождаются одним и тем же вероятностным распределением на нормированных <tex>|T|</tex>-мерных векторах; это распределение удобно взять из параметрического семейства распределений Дирихле <tex>\mathrm{Dir}(\theta,\alpha),\; \alpha\in\mathbb{R}^{|T|}</tex>;
 +
* векторы тем <tex>\phi_t = \bigl(p(w|t):\: w\in W\bigr)</tex> порождаются одним и тем же вероятностным распределением на нормированных векторах размерности <tex>|W|</tex>; это распределение удобно взять из параметрического семейства распределений Дирихле <tex>\mathrm{Dir}(\theta,\beta),\; \beta\in\mathbb{R}^{|W|}</tex>.
 +
 
 +
Для идентификации параметров модели LDA по коллекции документов применяется [[самплирование Гиббса]], [[вариационный байесовский вывод]] или метод [[Expectation-Propagation]].
 +
 
 +
==Оценивание качества тематических моделей==
== Литература ==
== Литература ==
-
# ''Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman''. Indexing by Latent Semantic Analysis. JASIS (41) 1990 pp. 391-407.
+
# ''Воронцов К. В.'' [[Media:voron17survey-artm.pdf|Вероятностное тематическое моделирование: теория, модели, алгоритмы и проект BigARTM]]. 2020.
-
# ''Thomas Hofmann''. Probilistic latent semantic analysis. Proceedings of the Twenty-Second Annual International SIGIR Conference on Research and Development in Information Retrieval. 1999.
+
# ''Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman''. Indexing by Latent Semantic Analysis // JASIS (41) 1990 pp. 391-407.
-
# ''David M. Blei, Andrew Ng, Michael Jordan''. Latent Dirichlet allocation. Journal of Machine Learning Research (3) 2003 pp. 993-1022.
+
# ''Thomas Hofmann''. Probilistic latent semantic analysis // Proceedings of the Twenty-Second Annual International SIGIR Conference on Research and Development in Information Retrieval. 1999.
-
# ''Mark Steyvers, Tom Griffiths''. Probabilistic Topic Models. In Handbook of Latent Semantic Analysis. 2007.
+
# ''David M. Blei, Andrew Ng, Michael Jordan''. Latent Dirichlet allocation // Journal of Machine Learning Research (3) 2003 pp. 993-1022.
-
# ''Ali Daud, Juanzi Li, Lizhu Zhou, Faqir Muhammad''. Frontiers of Computer Science in China, Vol.4, No.2, 2010, p. 280-301. [[Media:Daud2009survey-rus.pdf|Перевод на русский язык (PDF,&nbsp;1&nbsp;МБ)]].
+
# ''T. L. Griffiths, M. Steyvers''. Finding scientific topics // Proceedings of the National Academy of Sciences, Vol. 101, Nr. Suppl. 1 (April 2004) , p. 5228-5235. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.3205 Скачать с CiteSeer]
 +
# ''Mark Steyvers, Tom Griffiths''. Probabilistic Topic Models // In Handbook of Latent Semantic Analysis. 2007.
 +
# ''Ali Daud, Juanzi Li, Lizhu Zhou, Faqir Muhammad''. Knowledge discovery through directed probabilistic topic models: a survey // Frontiers of Computer Science in China, Vol.4, No.2, 2010, p. 280-301. [[Media:Daud2009survey-rus.pdf|Перевод на русский язык (PDF,&nbsp;1&nbsp;МБ)]].
 +
# ''Khoat Than, Tu bao Ho''. Fully sparse topic models // Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). 2012. [[Media:FSTM-summary.pdf|Реферат статьи на русском языке (PDF,&nbsp;1&nbsp;МБ)]].
== Ссылки ==
== Ссылки ==
-
* [http://www.cs.princeton.edu/~mimno/topics.html Topic Modeling Bibliography] — коллекция ссылок Дэвида Мимно.
+
* [http://www.cs.princeton.edu/~blei/topicmodeling.html Страница Дэвида Блея] — последние тьюториалы, лекции, полезные ссылки.
 +
* [http://mimno.infosci.cornell.edu/topics.html Topic Modeling Bibliography] — коллекция ссылок Дэвида Мимно.
 +
* [https://tmasada.wikispaces.com/Links+to+the+Papers+Related+to+Topic+Models Links to the Papers Related to Topic Models] — коллекция Томонари Масады.
* [http://en.wikipedia.org/w/index.php?title=Topic_model Topic Model] — англоязычная Википедия.
* [http://en.wikipedia.org/w/index.php?title=Topic_model Topic Model] — англоязычная Википедия.
 +
 +
Страницы исследователей:
 +
* [http://www.cs.princeton.edu/~blei David M. Blei]
 +
* [http://mimno.infosci.cornell.edu/ David Mimno]
 +
* [http://www.cs.cmu.edu/~chongw/ Chong Wang]
 +
* [http://people.cs.umass.edu/~mccallum/pubs.html Andrew McCallum]
 +
* [http://www.cs.princeton.edu/~mdhoffma Matt Hoffman]
 +
* [http://people.cs.umass.edu/~wallach/ Hanna M. Wallach]
 +
* [http://www.cs.berkeley.edu/~jpaisley/Papers.htm John Paisley]
 +
* [http://www.ics.uci.edu/~chandra/ Chaitanya Chemudugunta]
 +
 +
== См. также ==
 +
* [[Аддитивная регуляризация тематических моделей]]
 +
* [[BigARTM]]
 +
* [[Коллекции документов для тематического моделирования]]
 +
* Лекция по латентному размещению Дирихле в рамках спецкурса [[bmmo|БММО]] [[Media:BMMO11_14.pdf|(PDF, 480 КБ)]].
{{stub}}
{{stub}}

Версия 14:55, 27 июля 2020

Содержание

Тематическая модель (topic model) — модель коллекции текстовых документов, которая определяет, к каким темам относится каждый документ коллекции. Алгоритм построения тематической модели получает на входе коллекцию текстовых документов. На выходе для каждого документа выдаётся числовой вектор, составленный из оценок степени принадлежности данного документа каждой из тем. Размерность этого вектора, равная числу тем, может либо задаваться на входе, либо определяться моделью автоматически.

Тематическое моделирование (topic modeling) — построение тематической модели.

Задача построения тематической модели

Задана коллекция текстовых документов D. Каждый документ d из коллекции D представляет собой последовательность слов W_d=(w_1,\ldots,w_{n_d}) из словаря W, где n_d — длина документа d. Предполагается, что каждый документ может относиться к одной или нескольким темам. Темы отличаются друг от друга различной частотой употребления слов. Требуется найти эти темы, то есть определить

  • число тем;
  • распределения частот слов, характерное для каждой темы;
  • тематику каждого документа — в какой степени он относится к каждой из тем.

Данная задача может рассматриваться как задача одновременной кластеризации документов и слов по одному и тому же множеству кластеров, называемых темами. Обычно строится мягкая кластеризация, то есть документ может принадлежать нескольким темам в различной степени.

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

Примеры дополнительных задач:

  • ранжировать документы по степени релевантности заданной теме (тематический поиск);
  • ранжировать документы по степени тематического сходства с заданным документом или его фрагментом;
  • построить иерархический тематический каталог коллекции документов и выработать правила каталогизации новых документов;
  • определить, как темы изменялись со временем (предполагается, что для каждого документа известно время его создания);
  • определить тематику авторов (предполагается, что для каждого документа известен список второв);
  • определить тематику различных сущностей (entities), связанных с документами (например, журналов, конференций, организаций, стран);
  • разбить документ на тематически однородные фрагменты.

Типичные приложения:

Латентный семантический анализ

Метод главных компонент

Неотрицательные матричные разложения

Вероятностные тематические модели

Базовые вероятностные тематические модели (probabilistic topic model) основаны на следующих предположениях.

  • порядок документов в коллекции не важен;
  • порядок слов в документе не важен, документ — «мешок слов» (bag of words);
  • слова, встречающиеся в большинстве документов, не важны для определения тематики, их обычно исключают из словаря и называют стоп-словами;
  • слово в разных формах — это одно и то же слово;
  • коллекцию документов можно рассматривать как простую выборку пар «документ–слово» (d,w),\; d\in D,\; w\in W_d.
  • каждая тема t\in T описывается неизвестным распределением p(w|t) на множестве слов w\in W;
  • каждый документ d\in D описывается неизвестным распределением p(t|d) на множестве тем t\in T;
  • гипотеза условной независимости: p(w|t,d)=p(w|t).

Построить тематическую модель — значит, найти матрицы \Phi = ||p(w|t)|| и \Theta = ||p(t|d)|| по коллекции D.

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

Вероятностный латентный семантический анализ

Вероятностный латентный семантический анализ (probabilistic latent semantic analysis, PLSA) предложен Томасом Хофманном в 1999 году.

Вероятностная модель появления пары «документ–слово» (d,w) может быть записана тремя эквивалентными способами:

p(d,w) = \sum_{t\in T} p(t) p(w|t) p(d|t) = \sum_{t\in T} p(d) p(w|t) p(t|d) = \sum_{t\in T} p(w) p(t|w) p(d|t),

где T — множество тем;

p(t) — неизвестное априорное распределение тем во всей коллекции;
p(d) — априорное распределение на множестве документов, эмпирическая оценка p(d) = n_d/n, где n = \sum_d n_d — суммарная длина всех документов;
p(w) — априорное распределение на множестве слов, эмпирическая оценка p(w) = n_w/n, где n_w — число вхождений слова w во все документы;

Искомые условные распределения p(w|t),\: p(t|d) выражаются через p(t|w),\: p(d|t) по формуле Байеса:

p(w|t) = \frac{p(t|w)p(w)}{\sum_{w'} p(t|w')p(w')};\qquad  p(t|d) = \frac{p(d|t)p(t)}{\sum_{t'} p(d|t')p(t')}.

Для идентификации параметров тематической модели по коллекции документов применяется принцип максимума правдоподобия, который приводит к задаче максимизации функционала

\sum_{d\in D} \sum_{w\in d} n_{dw}\log p(w|d) \to \max_{\Phi,\Theta} ,

при ограничениях нормировки

\sum_w p(w|t) = 1,\; \sum_t p(t|d) = 1,\; \sum_t p(t) = 1,

где n_{dw} — число вхождений слова w в документ d.

Для решения данной оптимизационной задачи обычно применяется EM-алгоритм.

Основные недостатки PLSA:

  • Число параметров растёт линейно по числу документов в коллекции, что может приводить к переобучению модели.
  • При добавлении нового документа d в коллекцию распределение p(t|d) невозможно вычислить по тем же формулам, что и для остальных документов, не перестраивая всю модель заново.

Латентное размещение Дирихле

Метод латентного размещения Дирихле (latent Dirichlet allocation, LDA) предложен Дэвидом Блеем в 2003 году. В этом методе устранены основные недостатки PLSA.

Метод LDA основан на той же вероятностной модели

p(d,w) = \sum_{t\in T} p(d) p(w|t) p(t|d),

при дополнительных предположениях:

  • векторы документов \theta_d = \bigl(p(t|d):\: t\in T\bigr) порождаются одним и тем же вероятностным распределением на нормированных |T|-мерных векторах; это распределение удобно взять из параметрического семейства распределений Дирихле \mathrm{Dir}(\theta,\alpha),\; \alpha\in\mathbb{R}^{|T|};
  • векторы тем \phi_t = \bigl(p(w|t):\: w\in W\bigr) порождаются одним и тем же вероятностным распределением на нормированных векторах размерности |W|; это распределение удобно взять из параметрического семейства распределений Дирихле \mathrm{Dir}(\theta,\beta),\; \beta\in\mathbb{R}^{|W|}.

Для идентификации параметров модели LDA по коллекции документов применяется самплирование Гиббса, вариационный байесовский вывод или метод Expectation-Propagation.

Оценивание качества тематических моделей

Литература

  1. Воронцов К. В. Вероятностное тематическое моделирование: теория, модели, алгоритмы и проект BigARTM. 2020.
  2. Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman. Indexing by Latent Semantic Analysis // JASIS (41) 1990 pp. 391-407.
  3. Thomas Hofmann. Probilistic latent semantic analysis // Proceedings of the Twenty-Second Annual International SIGIR Conference on Research and Development in Information Retrieval. 1999.
  4. David M. Blei, Andrew Ng, Michael Jordan. Latent Dirichlet allocation // Journal of Machine Learning Research (3) 2003 pp. 993-1022.
  5. T. L. Griffiths, M. Steyvers. Finding scientific topics // Proceedings of the National Academy of Sciences, Vol. 101, Nr. Suppl. 1 (April 2004) , p. 5228-5235. Скачать с CiteSeer
  6. Mark Steyvers, Tom Griffiths. Probabilistic Topic Models // In Handbook of Latent Semantic Analysis. 2007.
  7. Ali Daud, Juanzi Li, Lizhu Zhou, Faqir Muhammad. Knowledge discovery through directed probabilistic topic models: a survey // Frontiers of Computer Science in China, Vol.4, No.2, 2010, p. 280-301. Перевод на русский язык (PDF, 1 МБ).
  8. Khoat Than, Tu bao Ho. Fully sparse topic models // Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). 2012. Реферат статьи на русском языке (PDF, 1 МБ).

Ссылки

Страницы исследователей:

См. также

Личные инструменты