=Paper=
{{Paper
|id=Vol-1297/243-252_paper-35
|storemode=property
|title=Тематические модели: учет сходства между униграммами и биграммами
(Topic Models: Taking into Account Similarity Between Unigrams and Bigrams)
|pdfUrl=https://ceur-ws.org/Vol-1297/243-252_paper-35.pdf
|volume=Vol-1297
|dblpUrl=https://dblp.org/rec/conf/rcdl/Nokel14
}}
==Тематические модели: учет сходства между униграммами и биграммами
(Topic Models: Taking into Account Similarity Between Unigrams and Bigrams)
==
https://ceur-ws.org/Vol-1297/243-252_paper-35.pdf
Тематические модели: учет сходства между
униграммами и биграммами
c М. А. Нокель
МГУ им. М. В. Ломоносова, Москва
mnokel@gmail.com
Аннотация С момента своего появления тематические мо-
дели достигли значительных успехов в задачах
В статье представлены результаты экспе- информационного поиска [2], разрешении морфо-
риментов по добавлению сходства между логической неоднозначности [3], многодокумент-
униграммами и биграммами в тематиче- ного аннотирования [4], кластеризации и катего-
ские модели. Вначале изучается возмож- ризации документов [5]. Также они успешно при-
ность применения ассоциативных мер для меняются в выявлении трендов в научных публи-
выбора и последующего включения биграмм кациях и новостных потоках [6], обработке аудио-
в тематические модели. Затем предлагает- и видео-сигналов [7] и других задачах. Самыми
ся модификация оригинального алгорит- известными представителями являются латентное
ма PLSA, учитывающая похожие униграм- размещение Дирихле (LDA) [1], использующее апри-
мы и биграммы, начинающиеся с одних орное распределение Дирихле, и метод вероятност-
и тех же букв. И в конце статьи предла- ного латентного семантического анализа (PLSA) [8],
гается новый итеративный алгоритм без не связанный ни с какими параметрическими апри-
учителя, показывающий, как темы сами орными распределениями.
могут выбирать себе наиболее подходящие В работах [9] и [10] было показано, что исполь-
биграммы. В качестве текстовой коллек- зование тематических моделей в задаче извлече-
ции была взята подборка статей из элек- ния однословных терминов способно значитель-
тронных банковских журналов на русском но улучшить качество извлечения последних из
языке. Эксперименты показывают значи- текстов предметных областей. Поэтому актуаль-
тельное улучшение качества тематических ной является и проблема улучшения качества са-
моделей по всем целевым метрикам. мих тематических моделей за счет использования
некоторой лингвистической информации, чему и
посвящена данная работа.
1 Введение Одним из главных недостатков тематических
моделей является использование модели “мешка
Вероятностные тематические модели (далее слов”, в которой каждый документ рассматрива-
просто тематические модели) – одно из совре- ется как набор встречающихся в нем слов. Дан-
менных приложений машинного обучения к ана- ная модель не учитывает порядок слов и основы-
лизу текстов. Тематические модели предназначе- вается на гипотезе независимости появлений слов
ны для описания текстов с точки зрения их тем. в документах друг от друга. На данный момент
Они определяют, к каким темам относится каж- проведено множество исследований, посвященных
дый документ в текстовой коллекции и какие сло- изучению вопроса добавления словосочетаний, n-
ва образуют каждую такую тему. При этом те- грамм и многословных терминов в тематические
мы представляются в виде дискретных распреде- модели. Однако часто это приводит к ухудшению
лений на множестве слов, а документы – в виде качества модели в связи с увеличением размера
дискретных распределений на множестве тем [1]. словаря или к значительному усложнению моде-
Пользователям темы предоставляются, как пра- ли [12], [13], [14].
вило, в виде некоторых списков часто встречаю- В статье предлагается новый подход, позволя-
щихся рядом друг с другом слов, упорядоченных ющий учесть взаимосвязь между похожими сло-
по убыванию степени принадлежности им. вами (в частности, однокоренными) в тематиче-
ских моделях (такими, как банк – банковский –
Труды 16-й Всероссийской научной банкир, кредит – кредитный – кредитовать – кре-
конференции “Электронные библиотеки: дитование). На основании данного метода в ста-
перспективные методы и технологии, тье описывается и новый подход к добавлению би-
электронные коллекции” – RCDL-2014, грамм в тематические модели, который рассмат-
Дубна, Россия, 13-16 октября 2014 г. ривает биграммы уже не как “черные ящики”, а
243
учитывает взаимосвязь между ними и униграм- распределение слов по документам.
мами, основанную на их внутренней структуре. Согласно данной модели коллекция D – это
Предлагаемый алгоритм улучшает качество тема- выборка наблюдений (d, w), генерируемых Алго-
тических моделей по двум целевым метрикам: пер- ритмом 1.
плексии и согласованности тем [15].
Все эксперименты, описанные в статье, прове- Algorithm 1: Порождение коллекции тек-
дены на основе алгоритма PLSA и его модифи- стов с помощью тематической модели
каций на коллекции текстов банковской тематики Input: распределения P (w|t) и P (t|d)
на русском языке, взятых из электронных журна- Output: коллекция D = {(d, w)}
лов. 1 for d ∈ D do
Статья организована следующим образом. В 2 Задать длину nd документа d
разделе 2 рассматриваются близкие работы. В раз- 3 for i = 1, . . . , nd do
деле 3 описывается текстовая коллекция, исполь- 4 Выбрать тему t из P (t|d)
зующаяся в экспериментах, все стадии её предоб- 5 Выбрать слово w из P (w|t)
работки и метрики, применяемые для оценивания 6 Добавить в D пару (d, w)
качества работы тематических моделей. В разде-
ле 4 проводится обширный анализ ассоциативных
мер для выбора и последующего включения би-
грамм в тематические модели. В разделе 5 пред- Самыми известными представителями данной
лагается новый алгоритм, позволяющий учесть сход- категории являются метод вероятностного латент-
ство между униграммами и биграммами в тема- ного семантического анализа (PLSA) [8] и латент-
тических моделях. В разделе 6 предлагается еще ное размещение Дирихле (LDA) [1].
один новый итеративный алгоритм, использую-
щий тот факт, что темы могут сами выбирать себе 2.2 Словосочетания в тематических моде-
наиболее подходящие биграммы. И в последнем лях
разделе приводятся выводы. Все описанные в прошлом разделе алгоритмы
работают только со словами, основываясь на ги-
2 Близкие работы потезе о независимости слов друг от друга – моде-
ли “мешка слов”. Идея же использования словосо-
2.1 Тематические модели четаний в тематических моделях сама по себе не
На сегодняшний день разработано достаточно нова. На данный момент существуют 2 подхода к
много различных тематических моделей. Истори- решению данной проблемы: создание унифициро-
чески одними из первых появились модели, осно- ванной вероятностной модели и предварительное
ванные на традиционных методах кластеризации извлечение словосочетаний и n-грамм для их по-
текстов [11]. При этом после окончания работы следующего добавления в тематические модели.
алгоритма кластеризации каждый получившийся Большинство исследований на данный момент
кластер рассматривается как отдельная тема для посвящено первому подходу. Так, первая попыт-
вычисления вероятностей входящих в него слов ка выйти за пределы модели “мешка слов” была
по следующей формуле: предпринята в работе [12], где была представле-
на Биграммная Тематическая Модель. В этой мо-
f (w|t) дели вероятности слов зависят от вероятностей
P (w|t) = P
f (w|t) непосредственно предшествующих им слов. Мо-
w дель словосочетаний LDA расширяет Биграммную
где f (w|t) – частотность слова w в теме t. Тематическую Модель за счет введения дополни-
Естественным ограничением таких моделей яв- тельных переменных, способных генерировать и
ляется отнесение каждого документа лишь к од- униграммы, и биграммы. В работе [14] представ-
ной теме. лена Тематическая N-граммная Модель, усложня-
В последнее время появились вероятностные ющая предыдущие для обеспечения возможности
механизмы нахождения тем в документах, рас- формирования биграмм в зависимости от контек-
сматривающие каждый документ в виде смеси тем, ста. В работе [16] предложена тематическая мо-
а каждую тему в виде некоторого вероятностного дель Слово-Символ, выходящая за рамки исполь-
распределения над словами. Вероятностные моде- зовавшегося ранее предположения о том, что те-
ли порождают слова по следующему правилу: ма каждой n-граммы определяется в зависимо-
X сти от тем слов, составляющих данное словосоче-
P (w|d) = P (w|t)P (t|d) тание. Эта модель оказалась наиболее пригодной
t для китайского языка. В работе [17] устанавлива-
где P (t|d) и P (w|t) – распределение тем по доку- ется связь между LDA и вероятностными контекстно-
ментам и слов по темам, а P (w|d) – наблюдаемое свободными грамматиками и предлагаются две но-
244
вые вероятностные модели, сочетающие в себе идеи счета их совместной встречаемости в документах
из LDA и вероятностных контекстно-свободных коллекции. Предлагаемый подход никак не увели-
грамматик для добавления словосочетаний и имен чивает вычислительную сложность оригинально-
собственных в тематические модели. го алгоритма PLSA.
Несмотря на то, что все описанные выше мо-
дели имеют теоретически элегантное обоснование,
3 Текстовая коллекция и методы оце-
у них очень большая вычислительная сложность,
что ведёт к неприменимости на реальных данных. нивания качества тематических мо-
Так, например, вычислительная сложность Биграмм- делей
ной Тематической Модели равна O(W 2 T ), в то
3.1 Текстовая коллекция и предобработка
время как для LDA она равна O(W T ), для PLSA
– O(W T +DT ), где W – размер словаря, D – коли- В экспериментах, описанных в данной статье,
чество документов в коллекции и T – число тем. использовалась текстовая коллекция из 10422 ста-
Поэтому такие модели представляют в основном тей на русском языке, взятых из некоторых элек-
чисто теоретический интерес. тронных банковских журналов (таких, как Ауди-
Алгоритм, предложенный в работе [18], отно- тор, РБК, Банковский журнал и др.). В данных
сится ко второму типу методов, добавляющих сло- документах содержится почти 15.5 млн слов.
восочетания в тематические модели. На этапе пре- На этапе предобработки был проведен морфо-
добработки авторы извлекают биграммы с помо- логический анализ документов. В экспериментах
щью t-теста и заменяют отдельные униграммы луч- рассматривались только существительные, при-
шими по данной мере биграммами. При этом ис- лагательные, глаголы и наречия, поскольку слу-
пользуются 2 метрики оценивания качества полу- жебные слова не играют значительной роли в опре-
ченных тем: перплексия и согласованность тем [15]. делении тем. Кроме того, из рассмотрения исклю-
В статье показано, что добавление биграмм в те- чались слова, встретившиеся менее 5 раз во всей
матические модели приводит к ухудшению пер- текстовой коллекции.
плексии и к улучшению согласованности тем. На этапе предобработки из документов также
Данная работа также относится ко второму ти- извлекались биграммы в формах сущ. + сущ. в
пу методов и отличается от работы [18] в том, родительном падеже и прил. + сущ. В экспери-
что описываемый здесь подход учитывает внут- ментах рассматривались только такие биграммы,
реннюю структуру биграмм и взаимосвязь меж- поскольку темы, как правило, задаются именны-
ду ними и составляющими их униграммами, что ми группами.
приводит к улучшению обоих показателей: и пер-
плексии, и согласованности тем. 3.2 Методы оценивания качества темати-
Идея использования априорных лингвистиче- ческих моделей
ских знаний в тематических моделях сама по себе
не нова. Так, в работе [19] предметно-ориентиро- Для оценивания качества полученных тем в
ванные знания представляются в виде Must-Link статье рассматриваются две метрики.
и Cannot-Link примитивов с помощью априорно- Во-первых, использовалась перплексия, явля-
го леса Дирихле. Эти примитивы отвечают за то, ющаяся стандартным критерием качества темати-
чтобы слова порождались одними и теми же или, ческих моделей [22]. Эта мера несоответствия мо-
наоборот, разными темами. Однако позднее бы- дели p(w|d) словам w, наблюдаемым в документах
ло замечено, что данный метод может привести к коллекции, определяется через логарифм правдо-
экспоненциальному росту при кодировании Cannot- подобия:
Link примитивов, и потому его сложно применять 1 XX
с большим количеством ограничений [20]. Другой P erplexity(D) = exp (− ndw ln p(w|d))
n
способ включения подобных знаний представлен d∈D w∈d
в работе [21], где был предложен частично обу- где n – число всех рассматриваемых слов в тексто-
чаемый с учителем EM-алгоритм для группиров- вой коллекции, D – множество всех документов в
ки выражений в некоторые заданные пользовате- коллекции, ndw – частота слова w в документе d,
лем категории. Для обеспечения наилучшей ини- p(w|d) – вероятность появления слова w в доку-
циализации EM-алгоритма предложенный в ста- менте d.
тье метод использует априорное знание о том, что Чем меньше значение перплексии, тем лучше
синонимы и выражения, имеющие одинаковые сло- модель предсказывает появление слов w в доку-
ва, должны, скорее всего, относиться к одним и ментах коллекции D. Поскольку известно, что пер-
тем же группам. Данная работа отличается от при- плексия, вычисленная на той же самой обучаю-
ведённых выше тем, что в ней сходства между щей коллекции документов, склонна к переобуче-
униграммами и биграммами добавляются в тема- нию и может давать оптимистически заниженные
тическую модель естественным образом путем под-
245
значения [1], в данной статье используется стан- биграмм вычисляются путем деления количества
дартный метод вычисления контрольной перплек- документов, в которых встретилась та или иная
сии, описанный в работе [24]. Коллекция докумен- униграмма или биграмма, на число всех докумен-
тов изначально разбивалась на 2 части: обучаю- тов в коллекции. Другой вариант вычисления ме-
щую D, по которой строилась модель, и контроль- ры согласованности тем на основе логарифма от
ную D0 , по которой вычислялась данная метри- условной вероятности (T C-LCP ), предложенный
ка. Хотя на данный момент существует множе- в работе [25], не рассматривается, поскольку в ра-
ство исследований, утверждающих, что перплек- боте [18] было показано, что этот вариант работа-
сию нельзя применять для оценивания качества ет значительно хуже, чем T C-P M I.
тематических моделей [23], данная метрика по-
прежнему широко используется для сравнения раз-
4 Добавление биграмм в тематиче-
личных тематических моделей.
В то же время неоднократно предпринимались ские модели
попытки предложить способ автоматического оце- На первом этапе экспериментов исследовалось,
нивания качества тематических моделей, никак может ли улучшиться качество тематической мо-
не связанного с перплексией и коррелирующего дели путем добавления в неё биграмм в качестве
с мнениями экспертов. Данная постановка зада- отдельных элементов словаря. Для этой цели бы-
чи является очень сложной, поскольку эксперты ли извлечены все биграммы, встретившиеся в кол-
могут достаточно сильно расходиться во мнени- лекции, с частотностью не меньше 5. Для последу-
ях. Однако в недавних работах [15], [25] было по- ющего упорядочения извлечённых биграмм при-
казано, что возможно автоматически оценивать менялись ассоциативные меры – математические
согласованность тем, основываясь на семантике критерии, определяющие силу связи между со-
слов с точностью, почти совпадающей с экспер- ставными частями фраз, основываясь на часто-
тами. Предложенная метрика измеряет интерпре- тах встречаемости отдельных слов и словосоче-
тируемость тем, основываясь на способах оцени- таний целиком. В экспериментах были использо-
вания экспертом [15]. Поскольку темы, как пра- ваны следующие 15 ассоциативных мер: Взаим-
вило, предоставляются экспертам для проверки в ная Информация (MI) [28], Дополненная Взаим-
виде первых топ-N слов, согласованность тем оце- ная Информация (Дополненная MI) [29], Кубиче-
нивает то, насколько данные слова соответству- ская Взаимная Информация (Кубическая MI) [30],
ют рассматриваемой теме. Newman в работе [15] Нормализованная Взаимная Информация (Норма-
предложил использовать автоматический способ лизованная MI) [31], Настоящая Взаимная Ин-
вычисления данной метрики исходя из меры вза- формация (Настоящая MI), Коэффициент Dice
имной информации: (DC) [32], Модифицированный Коэффициент Dice
j−1
10 X (Модифицированный DC) [33], T-Score, Симмет-
X P (wj , wi )
T C-P M I(t) = log ричная Условная Вероятность [34], Коэффициент
P (wj )P (wi )
j=2 i=1 Простого Соответствия, Коэффициент Kulczinsky,
где (w1 , w2 , . . . , w10 ) – топ-10 слов в рассматривае- Коэффициент Yula [30], Хи-Квадрат, Отношение
мой теме t, P (wi ) и P (wj ) – вероятности униграмм логарифмического правдоподобия [35] и Лексиче-
wi и wj соответственно, а P (wj , wi ) – вероятность ская Связность [36].
биграммы (wj , wi ). Итоговая мера согласованно- В соответствии с результатами [18] в темати-
сти тем вычисляется усреднением T C-P M I(t) по ческие модели добавлялись топ-1000 биграмм для
всем темам t. каждой ассоциативной меры. Так, в каждом экс-
Данная метрика показывает очень высокую кор- перименте к словарю в качестве отдельных эле-
реляцию с оценками экспертов [15]. Предложен- ментов добавлялись топ-1000 биграмм, и в каж-
ная метрика рассматривает только первые топ-10 дом документе, содержащем любые из добавля-
слов в каждой теме, поскольку они, как правило, емых словосочетаний, из частот образующих их
предоставляют достаточно информации для фор- униграмм вычитались частоты биграмм, а сами
мирования предмета темы и отличительных черт словосочетания добавлялись в его разреженное пред-
одной темы от другой. Согласованность тем ста- ставление. Отдельно следует отметить, что во всех
новится все более широко используемым способом экспериментах число топиков фиксировалось рав-
оценивания качества тематических моделей наря- ным 100.
ду с перплексией. Так, в работе [26] также было Хотя эксперименты были проведены для всех
показано, что данная метрика очень сильно кор- 15 упомянутых выше ассоциативных мер, в табли-
релирует с оценками экспертом. А в работе [27] це 1 представлены только наиболее характерные
она просто используется для оценки качества по- результаты добавления топ-1000 биграмм наряду
лученных тем. с результатом оригинального алгоритма PLSA без
В соответствии с подходом, изложенным в ра- добавления биграмм (значения, выделенные полу-
боте [25], в данной статье вероятности униграмм и жирным шрифтом, соответствуют улучшению по
246
одному из критериев). • S = {Sw } – множество похожих слов, где Sw
– множество слов, похожих на w;
Ассоциативная мера Перплексия TC-PMI • ndw и nds – частотности слов w и s в доку-
Оригинальный PLSA 1694 86.4
менте d;
MI 1683 79.2
Настоящая MI 2162 110.7 • n̂wt – оценка частотности слова w в теме t;
Кубическая MI 2000 95 • n̂td – оценка частотности темы t в документе
DC 1777 89.6 d;
Модифицированный DC 2134 94.1 • n̂t – оценка частотности темы t в коллекции
T-Score 2189 104.9
Лексическая Связность 1928 101.3
документов D.
Хи-Квадрат 1763 89.6 Псевдокод алгоритма PLSA-SIM представлен
в Алгоритме 2. Единственная модификация ори-
Таблица 1: Результаты добавления биграмм в те- гинального алгоритма PLSA касается строчки 6,
матическую модель где в рассмотрение добавляются предварительно
вычисленные множества похожих слов (в ориги-
Как видно, добавление топ-1000 биграмм, упо- нальном алгоритме данная строчка отсутствует, а
рядоченных по той или иной ассоциативной ме- в строчке 9 вместо fdw используется ndw ). Тем са-
ре, как правило, приводит к увеличению разме- мым вес подобных слов увеличивается в каждом
ра словаря и, следовательно, ухудшению перплек- документе коллекции.
сии, в то время как согласованность тем стано-
вится лучше. Эти выводы полностью согласуют- Algorithm 2: PLSA-SIM алгоритм: PLSA с
ся с результатами, описанными в работе [18]. Од- похожими словами
нако, используя некоторые ассоциативные меры Input: коллекция документов D,
(например, Взаимную Информацию), можно по- количество тем |T |,
лучить немного лучше перплексию, но чуть хуже начальные приближения Φ и Θ,
согласованность тем, что обусловлено добавлени- множества похожих слов S
ем нестандартных и низкочастотных биграмм. Output: распределения Φ и Θ
1 while не выполнится критерий остановки
do
5 Добавление схожих униграмм и би- 2 for d ∈ D, w ∈ W , t ∈ T do
грамм в тематические модели 3 n̂wt = 0, n̂td = 0, n̂t = 0
5.1 Добавление схожих униграмм в тема- 4 for d ∈ D,
P w ∈ W do
тические модели 5 Z = φwt θtd ,
t P
Оригинальные тематические модели (PLSA и 6 fdw = ndw + nds
s∈Sw
LDA) используют модель “мешка слов”, предпола-
7 for t ∈ T do
гающую независимость слов друг от друга. Одна-
8 if φwt θtd > 0 then
ко в документах есть много слов, связанных меж-
9 δ = fdw φwt θtd /Z
ду собой по смыслу – в частности, однокоренные
10 n̂wt = n̂wt + δ
слова, например: банк – банковский – банкир, кре-
11 n̂td = n̂d + δ
дит – кредитный – кредитовать – кредитование
12 n̂t = n̂t + δ
и др. Поэтому на следующем этапе экспериментов
исследовалась возможность учета в тематических
13 for w ∈ W , t ∈ T do
моделях подобных похожих слов – а именно, слов,
14 φwt = n̂wt /n̂t
начинающихся с одних и тех же букв.
Для данной цели был модифицирован ориги- 15 for d ∈ D, t ∈ T do
нальный алгоритм PLSA. При описании прове- 16 θtd = n̂td /n̂t
дённой модификации будет использоваться опи-
сание алгоритма PLSA, представленное в рабо-
те [37], и следующие обозначения: Поскольку в русском языке достаточно бога-
тая морфология, а темы в основном задаются имен-
• D – коллекция документов; ными группами, в качестве потенциальных кан-
• T – множество полученных тем; дидатов в похожие слова рассматривались толь-
• W – словарь (множество уникальных слов в ко существительные и прилагательные. В табли-
коллекции документов D); це 2 представлены результаты добавления похо-
• Φ = {φwt = p(w|t)} – распределение слов w жих слов в тематические модели наряду с ориги-
по темам t; нальным алгоритмом PLSA (значения, выделен-
• Θ = {θtd = p(t|d)} – распределение тем t по ные полужирным шрифтом, соответствуют луч-
документам d; шим значениям по одному из критериев).
247
Число одинаковых букв Перплексия TC-PMI PLSA алгоритм PLSA-SIM алгоритм
0 букв (PLSA) 1694 86.4 Бумага Документ Аудитор Правый
2 буквы 1852 187.2 Ценный Электронный Аудиторский Право
3 буквы 1565 432.9 Акция Форма Аудитор Правило
4 буквы 1434 2432.3 Рынок Организация Аудируемый Акция
5 букв 1620 2445.3 Облигация Подпись Проверка Акционер
6 букв 1610 1310.85
Таблица 4: Топ-5 слов, взятых из тем, полученных
Таблица 2: Результаты экспериментов по добавле- с помощью алгоритмов PLSA и PLSA-SIM
нию похожих униграмм в тематическую модель
5.2 Добавление схожих биграмм в темати-
Как видно, наилучшие результаты показыва- ческие модели
ет модель, рассматривающая в качестве похожих
слова, начинающиеся с 4 одинаковых букв. Од- Для применения подхода, представленного в
нако в русском языке есть множество приставок разделе 5.1 к топ-1000 биграммам, упорядочен-
длины в 4 буквы и больше. Учитывая это, был ными в соответствии с различными ассоциатив-
составлен список из 43 наиболее широко исполь- ными мерами, описанными в разделе 4, было ре-
зующихся таких приставок (анти-, гипер-, пере- шено ввести дополнительный критерий схожести
и др.) и введён дополнительный критерий: если биграмм и униграмм. Биграмма (w1 , w2 ) считает-
слова начинаются на одну и ту же приставку, то ся похожей на униграмму w3 , если выполнен один
они считаются похожими, если следующая буква из следующих критериев:
после приставки также совпадает. Данный кри- • слово w3 похоже на w1 или w2 в соответствии
терий позволил еще больше снизить перплексию с критериями, описанными в разделе 5.1;
до 1376 и оставить согласованность тем пример-
но на лучшем уровне – 2250. В дальнейших экс- • слово w3 совпадает с w1 или w2 и длина w3
периментах, описываемых в данной статье, было больше трех букв.
решено использовать именно эти 2 критерия.
Следует отметить, что в результате добавле- Хотя эксперименты были проведены для всех
ния знаний о похожести слов в тематические моде- ассоциативных мер, описанных в разделе 4, в таб-
ли такие слова с большей вероятностью окажутся лице 5 представлены только наиболее характер-
в топ-10 в полученных темах. Тем самым проис- ные результаты интеграции биграмм и добавле-
ходит неявная максимизация меры T C-P M I, по- нию похожести униграмм и биграмм наряду с ре-
скольку похожие слова склонны встречаться в од- зультатами алгоритмов PLSA и PLSA-SIM (зна-
них и тех же документах. Поэтому было приня- чения, выделенные полужирным шрифтом, соот-
то решение модифицировать данную метрику для ветствуют лучшим значениям по одному из кри-
учета не всех топ-10 слов, а только топ-10 непохо- териев).
жих слов в темах (в дальнейшем в статье данная
Алгоритм Перплексия TC-PMI-nSIM
метрика будет обозначаться как TC-PMI-nSIM ). PLSA 1694 78.3
В таблице 3 подытожены результаты добавления PLSA-SIM 1376 87.8
похожих слов в тематические модели с использо- PLSA-SIM + MI 1411 106.2
ванием описанных выше критериев и введённой PLSA-SIM +
1204 177.8
Настоящая MI
новой метрики: PLSA-SIM +
1186 151.7
Кубическая MI
Алгоритм Перплексия TC-PMI-nSIM PLSA-SIM + DC 1288 99
Исходный PLSA 1694 78.3 PLSA-SIM +
PLSA-SIM 1376 87.8 Модифицированный 1163 156.2
DC
PLSA-SIM +
1222 171.5
Таблица 3: Результаты наилучших способов до- T-Score
бавления похожих слов в тематическую модель PLSA-SIM +
Лексическая 1208 125.6
связность
Как видно, модифицированная версия алгорит- PLSA-SIM +
1346 122.9
ма PLSA-SIM показывает результаты лучше ори- Хи-квадрат
гинального алгоритма PLSA по обоим целевым
метрикам. В таблице 4 представлены топ-5 слов, Таблица 5: Результаты добавления похожих уни-
взятых из двух случайно выбранных тем для ори- грамм и биграмм в тематическую модель
гинального и модифицированного алгоритмов.
Как видно, добавление в тематическую модель
похожих униграмм и топ-1000 биграмм, упорядо-
ченных в соответствии с большинством ассоциа-
248
тивных мер, приводит к улучшению качества по- Algorithm 3: Итеративный алгоритм
лучающихся тем по сравнению с алгоритмом PLSA- Input: коллекция документов D,
SIM. В таблице 6 представлены топ-5 униграмм число тем |T |,
и биграмм, взятых из двух случайно выбранных множество биграмм B
тем, полученных с помощью алгоритма PLSA-SIM Output: полученные темы
с добавлением топ-1000 биграмм, упорядоченных 1 Запуск оригинального PLSA на коллекции
Модифицированным Коэффициентом Dice (Мо- документов D для получения тем T
дифицированным DC), для которого достигаются 2 BA = ∅
наилучшее значение перплексии. 3 while не выполнится критерий остановки
Инвестиция Финансовый рынок
do
Инвестор Финансовая система 4 SA = ∅
Инвестирование Финансовый 5 for t ∈ T do
Иностранный инвестор Финансовый институт 6 SA = SA ∪ {ut1 , ut2 , . . . , ut10 }
Иностранное инвестирование Финансовый ресурс 7 for uti , utj ∈ (ut1 , ut2 , . . . , ut10 ) do
8 if (uti , utj ) ∈ B and
Таблица 6: Топ-5 униграмм и биграмм, взятых из
тем, полученных с помощью PLSA-SIM с биграм- f (uti , utj ) > f (utj , uti ) then
мами, упорядоченными Модифированным DC 9 BA = BA ∪ {(uti , utj )}
10 SA = SA ∪ BA
11 Запуск PLSA-SIM с множеством
6 Итеративный алгоритм для выбо- похожих слов SA и с множеством
ра наиболее подходящих биграмм биграмм BA для получения тем T
На последнем этапе экспериментов было сде-
лано предположение, что темы могут сами вы-
бирать себе наиболее подходящие биграммы. Для В таблице 7 представлены первые несколько
проверки данной гипотезы был предложен новый итераций предложенного итеративного алгоритма
итеративный алгоритм выбора биграмм исходя из наряду с результатами оригинального алгоритма
вида верхушек тем. PLSA (в таблице обозначен как нулевая итера-
При описании предлагаемого алгоритма будут ция).
использоваться следующие дополнительные обо-
Итерация Перплексия TC-PMI-nSIM
значения: 0 (PLSA) 1694 78.3
1 936 180.5
• B – множество всех биграмм в коллекции 2 934 210.2
документов D; 3 933 230
• BA – множество биграмм, добавленных в те- 4 940 235.8
матическую модель; 5 931 193.5
• SA – множество потенциальных кандидатов
на похожие слова;
Таблица 7: Результаты итеративного алгоритма
• (ut1 , . . . , ut10 ) – топ-10 униграмм в теме t;
построения тематической модели
• f (ut1 , ut2 ) – частота биграммы (ut1 , ut2 ).
Псевдокод предлагаемого алгоритма представ- Как видно, после первой итерации наблюда-
лен в Алгоритме 3. На каждой итерации алгоритм ется существенное улучшение качества получае-
добавляет в множество кандидатов в похожие сло- мых тем по обеим целевым метрикам. Однако на
ва топ-10 униграмм из каждой темы. Также в это следующих итерациях результаты начинают ко-
же множество и в саму тематическую модель до- лебаться вокруг примерно тех же самых уровней
бавляются все биграммы, которые могут быть об- перплексии и согласованности тем (с незначитель-
разованы с помощью этих топ-10 униграмм. Бы- ным улучшением последней). Поэтому мы счита-
ло принято решение анализировать только первые ем, что согласно результатам первой итерации вы-
топ-10 слов в темах, поскольку одной из целевой бор необходимых биграмм и кандидатов в похо-
метрик является согласованность тем, использую- жие слова самими темами приводит к наилучшим
щая именно это множество (см. определение мет- значениям перплексии и согласованности тем. В
рики в разделе 3). В соответствии с данным алго- таблице 8 приведены топ-5 униграмм и биграмм,
ритмом темы могут выбирать себе только те би- взятых из двух случайно выбранных тем, полу-
граммы, которые образуются с помощью топ-10 ченных после первой итерации предложенного ал-
униграмм в темах, а такие биграммы с большей горитма.
вероятностью могут оказаться наиболее подходя-
щими.
249
Банковский кредит Ипотечный банк Topic Models. In the Proceedings of the ACL-
Банковский сектор Ипотечный кредит
Кредитование Ипотечное кредитование
IJCNLP 2009 Conference Short Papers, pp.
Кредитная система Жилищное кредитование 297–300, 2009.
Кредит Ипотека
[5] S. Zhou, K. Li, and Y. Liu. Text Categorization
Based on Topic Model. International Journal of
Таблица 8: Топ-5 униграмм и биграмм, взятых из Computational Intelligence Systems, Vol. 2, No.
тем, полученных с помощью итеративного алго- 4, pp. 398–409, 2009.
ритма построения тематической модели
[6] L. Bolelli, Ş. Ertekin, C. L. Giles. Topic
and Trend Detection in Text Collections
7 Благодарности Using Latent Dirichlet Allocation. In ECIR
Proceedings, Lecture Notes in Computer
Работа частично поддержана грантом РФФИ Science, Vol. 5478, pp. 776–780, 2009.
14-07-00383.
[7] T. Hyunh, M. Fritz, B. Schiele. Discovery of
activity patterns using topic models. In the
8 Заключение Proceedings of the 10th international conference
В работе представлены эксперименты по до- on Ubiquitous computing, pp. 10–19, 2008.
бавлению биграмм в тематические модели. Экс- [8] T. Hofmann. Probabilistic Latent Semantic
перименты, проведённые на русскоязычных ста- Indexing. In the Proceedings of the 22nd Annual
тьях из электронных банковских журналов, по- International SIGIR Conference on Research
казывают, что большинство ассоциативных мер and Development in Information Retrieval, pp.
упорядочивает биграммы таким образом, что при 50–57, 1999.
добавлении верхушки этих списков в тематиче-
ские модели ухудшается перплексия и улучшается [9] E. Bolshakova, N. Loukachevitch, M. Nokel.
согласованность тем. Затем в статье предлагает- Topic Models Can Improve Domain Term
ся новый алгоритм PLSA-SIM, добавляющий схо- Extraction. In ECIR Proceedings, Lecture
жесть униграмм и биграмм в тематические моде- Notes in Computer Science, Vol. 7814, pp. 684–
ли. Проведённые эксперименты показывают зна- 687, 2013.
чительное улучшение перплексии и согласованно-
сти тем для этого алгоритма. В конце статьи пред- [10] M. Nokel, N. Loukachevitch. Application of
лагается еще один новый итеративный алгоритм, Topic Models to the Task of Single-Word Term
основанный на идее, что темы сами могут выби- Extraction. In RCDL’2013 Proceedings, pp. 52–
рать себе наиболее подходящие биграммы и похо- 60, 2013.
жие слова. Эксперименты показывают дальней- [11] Q. He, K. Chang, E. Lim, A. Banerjee.
шее улучшение качества по обеим целевым мет- Keep It Smile with Time: A Reexamination
рикам. of Probabilistic Topic Detection Models. In
the Proceedings of IEEE Transaction Pattern
Список литературы Analysis and Machine Intelligence, vol. 32, issue
10, pp. 1795–1808, 2010.
[1] D. Blei, A. Ng and M. Jordan. Latent Dirichlet
Allocation. Journal of Machine Learning [12] H. Wallach. Topic Modeling: beyond bag-
Research, No. 3, pp. 993–1002, 2003. of-words. In the Proceedings of the 23rd
International Conference on Machine Learning,
[2] X. Wei and B. Croft. LDA-based document pp. 977–984, 2006.
models for ad-hoc retrieval. In the Proceedings
of the 29th International ACM-SIGIR [13] T. Griffiths, M. Steyvers, and J. Tenenbaum.
Conference on Research and Development Topics in semantic representation. Psychological
in Information Retrieval, pp. 178–185, 2006. Review, 144, 2, pp. 211–244, 2007.
[3] J. Boyd-Grabber, D. Blei and X. Zhu. A Topic [14] X. Wang, A. McCallum, and X. Wei. Topical
Model for Word Sense Disambiguation. In the n-grams: Phrase and topic discovery, with
Proceedings of the 2007 Joint Conference on an application to information retrieval. In
Empirical Methods in Natural Language the Proceedings of the 2007 Seventh IEEE
Processing and Computational Natural International Conference on Data Mining, pp.
Language Processing, pp. 1024–1033, 2007. 697–702, 2007.
[4] D. Wang, S. Zhu, T. Li, and Y. Gong. Multi- [15] D. Newman, J. H. Lau, K. Grieser, and
Document Summarization using Sentence-based T. Baldwin. Automatic evaluation of topic
250
coherence. In the Proceedings of Human coherence in topic models. In the Proceedings
Language Technologies: The 11th Annual of EMNLP’2011, pp. 262–272, 2011.
Conference of the North American Chapter of
the Association for Computational Linguistics, [26] K. Stevens, P. Kegelmeyer, D. Andrzejewski, D.
pp. 100-108, 2010. Butter. Exploring topic coherence over many
models and many topics. In the Proceedings of
[16] W. Hu, N. Shimizu, H. Sheng. Modeling chinese EMNLP-CoNLL’12, pp. 952–961, 2012.
documents with topical word-character models.
In the Proceedings of the 22nd International [27] D. Andrzejewski and D. Buttier. Latent
Conference on Computational Linguistics, pp. topic feedback for information retrieval. In
345–352, 2008. the Proceedings of tthe 17th ACM SIGKDD
International Conference on Knowledge
[17] M. Johnson. PCFGs, topic models, adaptor discovery and data mining, pp. 600–608, 2011.
grammars and learning topical collocations
and the structure of proper names. In the [28] K. Church and P. Hanks. Word Association
Proceedings of the 48th Annual Meeting of the Norms, Mutual Information, and Lexicography.
ACL, pp. 1148–1157, 2010. Computational Linguistics, vol. 16, pp. 22–29,
1990.
[18] J. H. Lau, T. Baldwin, and D. Newman.
On Collocations and Topic Models. In [29] W. Zhang, T. Yoshida, T. Ho, and X. Tang.
ACM Transactions on Speech and Language Augmented Mutual Information for Multi-
Processing, 10 (3), pp. 1–14, 2013. Word Term Extraction. International Journal
of Innovative Computing, Information and
[19] D. Andrzejewski, X. Zhu, and M. Craven. Control, 8(2), pp. 543–554, 2008.
Incorporating domain knowledge into topic
modeling via Dirichlet Forest priors. In the [30] B. Daille. Combined Approach for Terminology
Proceedings of the 26th Annual International Extraction: Lexical Statistics and Linguistic
Conference on Machine Learning, pp. 25–32, Filtering. PhD Dissertation, University of Paris,
2009. 1995.
[20] B. Liu. Sentiment Analysis and Opinion Mining. [31] G. Bouma. Normalized Pointwize Mutual
Syntheses Lectures on Human Language Information. In the Proceedings of the Biennal
Technologies. Morgan & Claypool Publishers. GSCL Conference, pp. 31–40, 2009.
2012 [32] F. Smadja, K. McKeown, and V.
[21] Z. Zhai, B. Liu, H. Xu, and P. Jia. Grouping Hatzivassiloglou. Translating Collocations
Product Features Using Semi-Supervised for Bilingual Lexicons: A Statistical Approach.
Learning with Soft-Constraints. In the Computational Linguistics, 22(1), pp. 1–38,
Proceedings of the 23rd International 1996.
Conference on Computational Linguistics, [33] M. Kitamura and Y. Matsumoto. Automatic
pp. 1272–1280, 2010. Extraction of Word Sequence Correspondences
[22] A. Daud, J. Li, and F. Muhammad. Knowledge in Parallel Corpora. In the Proceedings of the
discovery through directed probabilistic topic 4th Annual Workshop on Very Large Corpora,
models: a survey. Frontiers of Computer Science pp. 79–87, 1996.
in China, 4(2), pp. 280–301, 2010. [34] J. G. P. Lopes and J. F. Silva. A Local Maxima
[23] J. Chang, J. Boyd-Grabber, C. Wang, S. Method and a Fair Dispersion Normalization for
Gerrich, and D. Blei. Reading tea leaves: Extracting Multiword Units. In the Proceedings
How human interpret topic models. In the of the 6th Meeting on the Mathematics of
Proceedings of the 24th Annual Conference Language, pp. 369–381, 1999.
on Neural Information Processing Systems, pp. [35] T. Dunning. Accurate Methods for the Statistics
288–296, 2009. of Surprise and Coincidence. Computational
[24] A. Asuncion, M. Welling, P. Smyth, and Linguistics, 19(1), 1993.
Y. W. Teh. On smoothing and inference [36] Y. Park, R. Bird, and B. Boguraev. Automatic
for topic models. In the Proceedings of the Glossary Extraction: Beyond Terminology
International Conference on Uncertainty in Identification. In the Proceedings of the 19th
Artificial Intelligence, 2009. International Conference on Computational
[25] D. Mimno, H. Wallach, E. Talley, M. Leenders, Linguistics, 2002.
and A. McCallum. Optimizing semantic
251
[37] K. Vorontsov and A. Potapenko. EM-like
algorithms for probabilistic topic modeling.
Machine Learning and Data Analysis, vol. 1(6),
pp. 657–686, 2013.
Topic models: taking into account similarity
between unigrams and bigrams
Michael Nokel
The paper presents the results of experimental
study of integrating word similarity and bigram collo-
cations into topic models. First of all, we analyze
a variety of word association measures in order to
integrate top-ranked bigrams into topic models. Then
we propose a modification of the original algorithm
PLSA, which takes into account similar unigrams
and bigrams that start with the same beginning. And
at the end we present a novel unsupervised iterative
algorithm demonstrating how topics can choose the
most relevant bigrams. As a target text collection we
took articles from various Russian electronic banking
magazines. The experiments demonstrate significant
improvement of topic models quality for both collec-
tions.
252