Иерархическая классификация коллекций документов Кузьмин Арсентий Александрович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Кузьмин Арсентий Александрович. Иерархическая классификация коллекций документов: диссертация ... кандидата Физико-математических наук: 05.13.17 / Кузьмин Арсентий Александрович;[Место защиты: ФГУ «Федеральный исследовательский центр «Информатика и управление» Российской академии наук»], 2017.- 120 с.

Содержание к диссертации

Введение

Глава1. Постановка задачи 11

1.1. Предобработка документов 13

1.2. Составление словаря коллекции 14

1.3. Представление слов из словаря в виде векторов 15

1.4. Представление документа в виде вектора 20

1.5. Жесткие иерархические модели 22

1.6. Вероятностные модели 26

1.7. Иерархические вероятностные модели 31

1.8. Описательно-вероятностные модели и смеси моделей 33

1.9. Иерархическая классификация документов 35

Глава 2. Отбор признаков и метрическая кластеризация 40

2.1. Выбор взвешенной метрики 40

2.2. Алгоритм оптимизации весов метрики 42

2.3. Сравнение экспертной и алгоритмической модели 43

2.4. Анализ метрических свойств описаний документов 44

2.5. Анализ алгоритмов иерархической кластеризации 46

Глава 3. Иерархическая классификация неразмеченных документов 49

3.1. Иерархическая функция сходства 49

3.2. Оператор релевантности 53

3.3. Энтропийная модель важности слов 55

3.4. Учет векторного представления слов в функции сходства 56

3.5. Оптимизация параметров иерархической функции сходства 58

3.6. Оптимизация правдоподобия модели 60

3.7. Байесовские оценки параметров иерархической функции сходства. 63

3.8. Построение тематической модели конференции 79

Глава 4. Верификация тематической модели 83

4.1. Построение иерархической модели схожей с экспертной 83

4.2. Верификация тематической модели конференции 86

Глава5. Анализ прикладных задач 89

5.1. Иерархическая классификация тезисов крупной конференции 89

5.2. Визуализация иерархической тематической модели на плоскости 96

5.3. Иерархическая классификация веб-сайтов индустриального сектора 100

Заключение 104

Список основных обозначений 106

Список иллюстраций 108

Список таблиц 110

Список литературы

Представление слов из словаря в виде векторов
Анализ метрических свойств описаний документов
Учет векторного представления слов в функции сходства
Верификация тематической модели конференции

Введение к работе

Актуальность темы. В работе исследуются методы категоризации и классификации текстовых документов, автоматически структурирующие документы в виде иерархий тем и оптимизирующие уже существующие, выявляя в них тематические несоответствия (Hofmann: 1999, He: 2010, Blei: 2010).

Тематическая модель – модель коллекции текстовых документов, которая определяет, к каким темам относится каждый документ коллекции. В работе исследуется фундаментальная проблема тематического моделирования – классификация документов из частично размеченных коллекций с экспертно заданной иерархической структурой тем (McCallum: 1998, Лукашевич: 2008, Кузнецов: 2015). Решением задачи классификации является отображение подмножества неразмеченных документов коллекции во множество тем, наилучшим образом восстанавливающее экспертную классификацию согласно заданному критерию качества. В случае большого числа тем вместо единственного релевантного кластера предлагается ранжированный список кластеров согласно их релевантности документу. При несовпадении экспертного мнения и наиболее релевантного кластера эксперт рассматривает следующие по релевантности кластеры в качестве альтернативных вариантов.

Коллекциями документов являются аннотации к научным работам (Joachims: 1998), доклады на конференциях (Кузнецов: 2015), текстовые сообщения в социальных сетях (Лукашевич: 2016), текстовая информация веб-сайтов (Xue: 2008), описания патентов, новостные сводки (Ikonomakis: 2005, Linghui: 2011) и описания фильмов (Schedl: 2012). Предполагается, что экспертное разделение документов на темы является эталонным. В связи со значительным размером коллекций и числом тем распределение документов по темам является для экспертов трудоемкой задачей. Поэтому автоматическая классификация неразмеченных документов и поиск небольшого числа наиболее подходящих тем для каждого неразмеченного документа для дальнейшего принятия решения экспертом являются актуальными задачами.

Для текстовой классификации и кластеризации были предложены жесткие методы, в которых каждому документу ставится в соответствие единственный кластер (Hartigan: 1979, Hao: 2007), описательно вероятностные методы, в которых оценивается вероятность принадлежности документа каждому из кластеров (He: 2010), смеси моделей (Banerjee: 2003) и вероятностные методы (Blei: 2003, Воронцов: 2015) в которых темы являются распределениями над множеством слов, а документы – распределениями над множеством тем. Для коллекций с большим числом тем были предложены иерархические методы, позволяющие учитывать взаимосвязи между темами (Hao: 2007, Zavitsanos: 2011).

Важной проблемой при построении метрических алгоритмов классификации и кластеризации является выбор метрики (Leisch: 2006) как способа сравнения векторных представлений документов. В (Amorim: 2012) для учета соот-

ношения масштабов признаков рассматривается взвешенная метрика Минков-ского. Веса интерпретируются как важность слов. В данной работе исследуются способы оптимизации весов взвешенной метрики, а также различные способы векторного представления документов, наилучшим образом восстанавливающие экспертную классификацию. Альтернативой взвешенной функции расстояния является взвешенная функция сходства (Yih: 2009). Для уменьшения числа параметров оптимизации предлагается энтропийный метод определения важности слов во взвешенной функции сходства через их энтропию относительно экспертной кластеризации на различных уровнях иерархии. Для иерархической классификации предлагается иерархическая взвешенная функция сходства, позволяющая учитывать сходство сразу со всей веткой дерева экспертной иерархической структуры коллекции.

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

При наличии априорных распределений параметров аналитический байесовский вывод апостериорного распределения параметров иерархической функции сходства и совместного апостериорного распределения параметров и классов неразмеченных документов не является возможным. В работах (Gershman: 2012, Blei: 2016) рассматриваются способы приближенного вариационного вывода и аппроксимации правдоподобия. В работе данные идеи используются для аналитического вывода апостериорного распределения параметров (Bishop: 2006, Стрижов: 2016), а также для аппроксимации совместного апостериорного распределения классов неразмеченных документов и параметров.

Для размеченных коллекций возникает задача верификации. Решением этой задачи является изменение у фиксированного набора документов их тем так, чтобы качество полученной модели стало максимальным. Для этого предлагается алгоритм построения иерархической модели, схожей с существующей, для выявления значимых тематических несоответствий в модели. Предлагаются варианты устранения несоответствий путем переноса некоторых документов в другие кластеры.

Для визуализации тематической модели были предложены различные подходы (Millar: 2009, Ando: 2000). В случае, когда документы представляются в виде действительных векторов, для их визуализации используются методы понижения размерности (Lee: 2007). При этом кластеры из разных ветвей иерархической модели могут пересекаться. В данной работе предлагается метод построения плоской вложенной визуализации иерархической модели, при которой кластеры более низкого уровня остаются внутри кластеров более высокого уровня на плоскости. Предлагаемый подход опирается на методы, минимизирующие изменения относительного расстояния между документами и центрами

кластеров иерархии (Sammon: 1969).

Цели работы.

Исследовать метрические свойства описаний текстовых документов.
Предложить критерии качества модели иерархической классификации документов.
Построить оптимальную модель иерархической классификации.
Получить вариационные оценки апостериорных распределений параметров и гиперпараметров модели.
Разработать алгоритм построения модели и провести вычислительный эксперимент для сравнения различных подходов к решению задачи иерархической классификации документов.

Основные положения, выносимые на защиту.

Предложен метод иерархической классификации коллекций документов на основе оператора релевантности.
Разработана и исследована вероятностная модель иерархической классификации.
Предложены методы оптимизации параметров и гиперпараметров модели.
Предложен способ вычисления иерархической вероятности класса документа и построения ранжированного списка для последующей экспертной оценки.
Разработан программный комплекс для экспертного построения программы конференции.

Методы исследования. Для достижения поставленных целей используются методы иерархического тематического моделирования (Воронцов: 2015, Mimno: 2007, Hao: 2007, Blei: 2012, Zavitsanosh: 2011). Для метрической иерархической кластеризации применяются методы плоской кластеризации (Leisch: 2006, Kogan: 2005) совместно с агломеративным и дивизимным подходами (Ruiz: 2002, Hao: 2007). Для построения локально оптимальной взвешенной метрики используются методы отбора признаков (Воронцов: 2010) и методы условной оптимизации (Boyd: 2004, Bishop: 2006). Для сравнения документов при иерархической классификации используется взвешенная функция сходства (Yih: 2009), а для оптимизации ее параметров развивается энтропийный метод, предложенный в (Ruiz: 2002). Для оптимизации параметров иерархической взвешенной функции сходства и энтропийной модели используются методы вариационного вывода (Gershman: 2012, Blei: 2016), методы выбора моделей (Стрижов: 2014) и методы локальных вариаций (Bishop: 2006). Для построения оператора релевантности используются методы иерархической

классификации (Кузнецов: 2015, McCallum: 1998). Для построения плоской вложенной визуализации иерархической тематической модели используются методы понижения размерности (Sammon: 1969). Для учета синонимичности слов используются языковые модели (Mnih: 2009, Mikolov: 2013) и методы оптимизации параметров нейронных сетей. Кроме того, используются элементы теории вероятности и выпуклой оптимизации.

Научная новизна. Разработан новый подход иерархической классификации частично размеченных коллекций текстовых документов с экспертной иерархической структурой. Предложена иерархическая взвешенная функция сходства документа и кластера, учитывающая иерархичность экспертной кластерной структуры. Предложен метод оценки важности слов с помощью энтропийной модели. Предложена вероятностная модель текстовой коллекции и способ аппроксимации совместного апостериорного распределения параметров модели и классов неразмеченных документов. Предложен способ представления иерархической функции сходства в виде многослойной нейронной сети и способ учета синонимичности слов. Введен оператор релевантности, ранжирующий кластеры тематической модели по убыванию релевантности новому документу. Для верификации экспертной тематической модели предложен метод построения модели, схожей с экспертной, и выявления наиболее значимых несоответствий. Предложен метод вложенной визуализации экспертной иерархической тематической модели на плоскости, а также выявленных несоответствий и вариантов повышения тематической целостности модели.

Теоретическая значимость. В данной диссертационной работе предложенные ранее функции расстояния обобщаются для учета важности признаков путем введения их весов. Взвешенная функция сходства обобщается на случай иерархических моделей. Вычисляются оценки весов взвешенной функции сходства с помощью обобщения энтропийного подхода. Для вероятностной модели коллекции документов, основанной на иерархической функции сходства, предлагается способ оценки апостериорного распределения параметров, а также совместного апостериорного распределения параметров и классов неразмеченных документов. Доказываются свойства полученных оценок.

Практическая значимость. Предложенные в работе методы предназначены для иерархической классификации коллекций текстов с учетом существующих экспертных моделей; выявления тематических несоответствий в экспертных моделях и значимого повышения тематической целостности уже построенных тематических моделей с помощью небольшого числа изменений; визуализации иерархических моделей и выявленных несоответствий на плоскости.

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

проверкой полученных методов на реальных задачах иерархической классификации коллекций тезисов конференции и коллекций сайтов индустриального сектора; публикациями результатов исследования в рецензируемых научных изданиях, в том числе рекомендованных ВАК. Результаты работы докладывались и обсуждались на следующих научных конференциях.

Международная конференция “26th European Conference on Operational Research”, 2013.
Международная конференция “20th Conference of the International Federation of Operational Research Societies”, 2014.
Всероссийская конференция “Математические методы распознавания образов” ММРО-17, 2015.
Всероссийская конференция “58 научная конференция МФТИ”, 2015.
Всероссийская конференция “Ломоносов-2016”, 2016.
Международная конференция “28th European Conference on Operational Research”, 2016.

Работа поддержана грантами Российского фонда фундаментальных исследований и Министерства образования и науки РФ.

14-07-31264, Российский фонд фундаментальных исследований в рамках гранта “Развитие методов визуализации иерархических тематических моделей”.
07.524.11.4002, Министерство образования и науки РФ в рамках Государственного контракта “Система агрегирования и публикации научных документов ВебСервис: построение тематических моделей коллекции документов”.

Публикации по теме диссертации. Основные результаты по теме диссертации изложены в 10 печатных изданиях, 4 из которых изданы в журналах, рекомендованных ВАК. Список публикаций приведен в конце автореферата.

Личный вклад. Все приведенные результаты, кроме отдельно оговоренных случаев, получены диссертантом лично при научном руководстве д.ф.-м.н. В. В. Стрижова.

Структура и объем работы. Диссертация состоит из оглавления, введения, пяти разделов, заключения, списка иллюстраций, списка таблиц, перечня основных обозначений и списка литературы из 123 наименований. Текст работы занимает 120 страниц.

Представление слов из словаря в виде векторов

После предобработки коллекции D, словарь W содержит слова из коллекции D без повторений. Добавление в W устойчивых словосочетаний позволяет улучшить качество кластеризации коллекции [65, 66]. Устойчивым словосочетанием называется последовательность слов, TV-грамма, часто встречающаяся в документах коллекции.

Для поиска устойчивых словосочетаний в [66] предлагается упорядочить всевозможные пары слов по значению ассоциативной меры T-Score(Wl№2,D) = Ftf(№lW,D)f(Wl,D)tf(№2,D) \W\y/ti(w1w2,D) где ti(w,D) - частота слова w в коллекции D. Словосочетания с наибольшим значением T-Score являются наиболее устойчивыми и добавляются в словарь. В [67] для отбора устойчивых словосочетаний используется взаимная информация: MI(U)l№2)=logJM y.

Чем больше ее значение для словосочетания W\W2, тем более устойчивым оно является. Однако данная мера не ограничена сверху, а ti{w\,D) и tf(it 2,D) в знаменателе не зависят от того, встретилось ли слово W\ вместе с w2 или нет. Чтобы учесть эти недостатки, были предложены аналоги данной меры: дополненная взаимная информация [68] и нормализованная взаимная информация [69].

В [65] предлагается подход PLSA-ITER, основанный на алгоритме PLSA [1], в котором шаг построения модели PLSA чередуется с шагом генерации и добавления в словарь всевозможных словосочетаний слов, с наибольшей вероятностью характеризующих одну из тем, полученных с помощью PLSA. В [70] для увеличения числа словосочетаний предлагается в качестве А -грамм рассматривать последовательности слов с не более чем т пропусками. 1.3. Представление слов из словаря в виде векторов

Пусть каждому слову w из словаря W ставится в соответствие некоторый вектор w(w) Є Mm, а сходство двух слов sw(wi,Wj) выражается как косинус угла между их векторами: v JJ w( )w( )ll y/(w(wi),w(wi))y/(w(wj)Mwj)) Тривиальным векторным представлением слова Wj, стоящего на позиции j в словаре W, является единичный вектор e(j) с единицей на позиции j: W(WJ) = e(J) Є #1 e(j) = [0 ... О 1 0 ... 0]. При этом сходство между двумя произвольными словами равно 1, если слова совпадают, и 0, если слова разные: Sw( , .) = [i = j].

Чтобы сохранить информацию о синонимичности слов, для слов-синонимов используются схожие векторы. Для описания процесса оптимизации векторов w(it ), рассмотрим языковую модель (LM, англ. Language Modeling).

Языковая модель. Языковая модель применяется в распознавании речи, распознавании печатного и рукописного текста, в области машинного перевода и проверки орфографии [71, 72, 73, 74, 75]. Она определяет вероятность p(wi,W2, iWn) последовательности слов W\W2- -Wn. В [76] предполагается, что вероятность слова зависит только от предыдущих слов: p(whw2, ...,wn)= p(wx) p(w2\w1) ... -p(wnwn_i,... ,«л). (1.1) Оценить p(wi\wi-i,... , W\) при больших і сложно, поэтому предполагается, что слово зависит только от двух предыдущих. Данное предположение называется триграммным. Условные вероятности в (1.1) оцениваются как p(Wi\Wi-U . . . ,WX) = p(Wi\Wi-UWi-2) = N(ViWi-lWi-2,D) (1.2) где N(wiWi-i... , D) - число последовательностей слов Wi, w -i,... в коллекции D.

Матрица оценок вероятностей p(wi\wi-i,..., W\) будет разреженной, так как многие тройки слов не встретятся в D. Для решения проблемы разреженности были предложены различные формы дисконтирования, перераспределяющие вероятность встретившихся троек на другие схожие тройки слов. Применяется дисконтирование Катца [77] или Джелинека-Мерсера [78]. В [79] показывается, что дисконтирование Кнесера-Нея [80] превосходит по качеству остальные техники дисконтирования, а в [76] приводится теоретическое обоснование этого. Для увеличения числа последовательностей слов в [70] рассматриваются всевозможные триграммы с пропусками.

Распределенное представление слова. Альтернативными методами оценки вероятности (1.1) являются модели [81, 82, 41, 42], использующие распределенное представление слов в виде действительных векторов w(w).

Пусть каждому слову w из словаря W соответствует вектор w(w) Є Mm, а в матрице W размера \W\ т строка с номером і соответствует векторному представлению слова с номером і из словаря W. Пусть Wt - слово с порядковым номером t в документе. Вероятность слова Wt быть словом Wi из словаря W при заданной последовательности предшествующих ему слов Wt-i... Wt-n+i задается как г-й элемент параметрической вектор-функции f Є M)w\: р(щ = WilllH-!, . . . , Wt-n+l) = /(w(wt_i), . . , W(wt_n+1), 0) .. В [81] функция f представляется в виде нейронной сети, показанной на рис. 1.1: f(w(wt.l),...,w(wt.n+l),e) =f(y(x,0)), где (1.3) y(g, в) = Ъ + Vx + Ug, g = tanh(a), а = d + Нх, (1.4) х= [w(wt.l),w(wt.2),... (wt.n+l)}T. (1.5) Здесь х - конкатенация векторных представлений слов, полученных из матрицы W, у(х,0) - вектор значений предактивации выходного слоя, g - вектор значений активации скрытого слоя, а - вектор значений предактивации скрытого слоя, b - вектор констант нейронов выходного слоя, V - матрица весов связей, соединяющих напрямую векторные представления слов с выходным слоем, U - матрица весов соединений между скрытым слоем и выходным слоем, Н - матрица весов соединений входного слоя векторного представления слов х со скрытым слоем, аd- вектор констант нейронов выходного слоя.

В качестве функции активации выходного слоя используется функция softmax(y): е, \ ехрЫ exp(yi) Г Г(у) = [7771 шГ\ (1.6) Число параметров данной модели \W\{\+nm + h) + h{\ + {n — 1)т). Наибольший вес в данную сумму вносит член VKnm. Таким образом, число свободных параметров растет линейно с размером словаря W, размерностью пространства векторного представления слов т и числом слов в рассматриваемых словосочетаниях.

Анализ метрических свойств описаний документов

Множество взвешенных метрик (2.1) задается набором весовых коэффициентов Л. Их оптимизация осуществляется алгоритмом последовательного добавлении признаков [38]. Слово с индексом т называется активным признаком, если соответствующий ему вес Лто больше нуля. Пусть А - множество активных признаков. Выборка D разбивается случайным образом на обучающее Dy и контрольное Dj. Изначально Л = 0 и А = 0. На каждом шаге алгоритма в А добавляется наилучший признак следующим образом. 1. Для каждого признака т А найти набор весов Лто для множества при знаков Ат = {A U т}, доставляющий максимум функции качества Xm = d,igmaxV(p,Xm,Dv), Лті = 1, Лт,г = О, і Ат. (2.6) 2. Найти признак т которому соответствует максимальное качество m = aigmaxV(p,Xm,Dv) га и добавить его во множество А, обновив вектор весов А = А Алгоритм повторяется до тех пор, пока значение функции качества V(p, A, Dj) на контрольной выборке Dj увеличивается. Утверждение 7. При условии \D\ \Dy\ \Dj\ сложность описанного выше алгоритма где t – число итераций алгоритма оптимизации (2.6). Доказательство. Для вычисления качества метрики (2.5) для каждого документа необходимо найти к ближайших соседей и вычислить (2.4). Это делается за 0(D2log2 \D\) с помощью сортировки. При к log2 \D\ это можно сделать за 0(\D\2k2).

На каждом шаге выбирается признак, дающий максимальный прирост каче ства метрики. Для поиска данного признака необходимо перебрать все возмож ные и найти для каждого оптимальный вес, решив задачу (2.6). На каждой итерации алгоритма оптимизации, необходимо вычислить качество метрики, таким образом для добавления очередного признака необходимо 0(D2&2VK) операций. Локально оптимальный набор признаков содержит 0(VK) элемен тов, таким образом сложность всего алгоритма 0(\D\2k2\W\2t). П Чтобы снизить сложность, вместо функции качества V используется среднее внутрикластерное расстояние [с(х) = с(у)]р(А,х,у) F0 = х,уєД , У min, Ai = 1, А 0, (2.7) У J с(х) = c(y)J А где [ = ]- индикаторная функция. Утверждение 8. Решением оптимизационной задачи (2.7) для взвешенной метрики городских кварталов (2.1) с р = 1 является единичный вектор е(-).

Доказательство. Fo является линейной функцией относительно весов Л. Ее требуется минимизировать на множестве Лі = 1,Л 0, которое является выпуклым. У этой задачи существует решение, причем минимум реализуется в вершине \W\-мерного симплекса. В каждой вершине этого симплекса все коор динаты равны нулю, кроме одной, которая равна единице.

Таким образом при оптимизации (2.7) отбирается единственный признак. Поэтому необходимо учитывать не только внутрикластерное расстояние, но и межкластерное. Оно определяется как [с(х) с(у)]р(А,х,у) F\ = — max, Ai = 1, А О, (2.8) / _, [с(х) ф c(y)J А х,ує и вместо функции качества (2.5) используется: F = ——у min. (2.9) F\ А 2.3. Сравнение экспертной и алгоритмической модели Пусть с(х) - номер кластера документа х на уровне h в построенной алгоритмом тематической модели М, а с(х) - номер его кластера в экспертной тематической модели М. Пусть В (с) - оператор, возвращающий родительский кластер заданного кластера с на следующем уровней. Родительским кластером документа х на уровне / является кластер _В/г_/(с(х)). Обозначим /х(с) координаты центра кластера с.

Определение 13. Ошибка классификации документа х в алгоритмической модели М относительно экспертной модели М задается как суммарное расстояние между центрами экспертных и алгоритмических кластеров документа х на всех уровнях иерархии v{ ,M,M) = Y, Р {» {Bh l (с(х))) ,А (ВЛ- (С(Х)))) . (2.10) Определение 14. Расстояние Т(М, М) между экспертной моделью М и алгоритмической моделью М определяется как сумма ошибки классификации неразмеченных документов Т(М, М) = у v(x,M,M). (2.11) xeD 2.4. Анализ метрических свойств описаний документов Для анализа способов векторного представления документов и свойств алгоритма построения метрики с оптимальным набором весов Л был проведен эксперимент плоской кластеризации \D\ = 1342 тезисов научной конференции European Conference on Operational Research на i = 26 кластеров. Количество кластеров выбрано в согласии с числом научных областей (англ. Areas) на конференции. Рассматривались три способа векторного представления документа, описанные в разделе 2.1.

Кластеризация документов. Для кластеризации использовался алгоритм /c-means, описанный в разделе 1.5., с функцией расстояния (2.1). Начальные положение центров кластеров задавались согласно экспертной кластеризации размеченных документов. Для оценки качества полученной кластеризации использовалась функция (2.11). На рис. 2.1 а.-г. показаны расхождения между построенной и экспертной моделью. Эти графики строились следующим образом.

1. При помощи метода главных компонент центры полученных кластеров нумеровались таким образом, чтобы наиболее близкие кластеры имели близкие порядковые номера.

2. Все документы откладывались на плоскости: координатой документа по оси абсцисс являлся номер кластера в алгоритмической модели М, а по оси ординат - номер кластера в экспертной модели М. В каждой точке рисовался круг с радиусом пропорциональным числу документов, попавших в эту точку. Наибольшему кругу соответствовало 80 документов.

Чем дальше документ находился от прямой у = х на данной плоскости, тем сильнее отличались тематики кластеров, к которым он был отнесен алгоритмом и экспертом. Как видно из рис. 2.1 для булевых признаков характерен меньший разброс документов относительно диагонали. Это подтверждается значениями расстояния (2.11) между построенной моделью и экспертной, указанными в таблице 2.1. При использовании дополнительной настройки весов Л алгоритм кластеризации показывал более высокие результаты. Алгоритм оптимизации Л позволил удалить некоторые неинформативные слова, например, “matrix”, “compute”, “activity”, встречающиеся почти во всех кластерах, и не несущие информации о кластеризации, так как большая часть тезисов конференции EURO посвящена методам оптимизации.

Учет векторного представления слов в функции сходства

Чтобы снизить сложность, вместо функции качества V используется среднее внутрикластерное расстояние [с(х) = с(у)]р(А,х,у) F0 = х,уєД , У min, Ai = 1, А 0, (2.7) У J с(х) = c(y)J А где [ = ]- индикаторная функция. Утверждение 8. Решением оптимизационной задачи (2.7) для взвешенной метрики городских кварталов (2.1) с р = 1 является единичный вектор е(-). Доказательство. Fo является линейной функцией относительно весов Л. Ее требуется минимизировать на множестве Лі = 1,Л 0, которое является выпуклым. У этой задачи существует решение, причем минимум реализуется в вершине \W\-мерного симплекса. В каждой вершине этого симплекса все коор динаты равны нулю, кроме одной, которая равна единице.

Пусть с(х) - номер кластера документа х на уровне h в построенной алгоритмом тематической модели М, а с(х) - номер его кластера в экспертной тематической модели М. Пусть В (с) - оператор, возвращающий родительский кластер заданного кластера с на следующем уровней. Родительским кластером документа х на уровне / является кластер _В/г_/(с(х)). Обозначим /х(с) координаты центра кластера с.

Для визуализации кластеризации документов и сравнения алгоритмической кластеризации с экспертной строились гистограммы, изображенные на рис. 2.2. Количество столбцов совпадало с количеством кластеров, каждому документу присваивался цвет экспертного кластера. Высота части столбца одного цвета показывала число документов, экспертно отнесенных к кластеру с данным цветом, которое алгоритм отнес к кластеру, соответствующему номеру столбца. Рис. 2.2 а. построен по экспертной кластеризации, поэтому каждый столбец

Верификация тематической модели конференции

Аппроксимация совместного апостериорного распределения. При построении оператора i?2, конечной целью описанного выше вариационного вывода является получение оценки p(ztk\%) вероятности принадлежности неразмеченного документа х кластеру с к. Однако зная оценку апостериорного распределения д, взять интеграл (3.73) аналитически не получается. Рассмотрим альтернативный подход, в котором с помощью вариационного вывода вместо аппроксимации апостериорного распределения параметров ищется аппроксимация совместного апостериорного распределения параметров и классов Z неразмеченных документов. Данное распределение является оценкой всего подынтегрального выражения (3.73) и позволяет взять интеграл, не используя дополнительных оценок.

Совместное распределение (3.44) и распределение меток неизвестных классов Z имеет вид p(Z, Z, 0, т, V, а) = p(Z0, ct)p(Z, 0, а, m, V). (3.80) В качестве g(Z, 0, т, V, а) будем искать аппроксимацию распределения p(Z, 0, m, V, aZ). Предполагается, что q факторизуется следующим образом: g(Z,0,m, V, а) = q(0)q(ot, m, V)g(Z). (3.81) Стоит отметить, что подобное предположение о факторизации не влечет независимость распределения меток классов Z и параметров 0,а. Наоборот, параметры распределения g(Z) будут выражаться через параметры остальных распределений таким образом, чтобы найденная аппроксимация q была максимально приближена к p(Z, 0, m, V, aZ). Выписав выражение для нижней границы C(q) и сгруппировав его аналогично (3.47), получаем вид оптимальных факторов q, максимизирующих C(q) при фиксированных остальных факторах: lng(0) = Ea)m)V)z[lnp(Z,Z,0,m,V,a)] +const(0), Inq(a, m, V) = E [lnp(Z, Z, 0, m, V, a)] + const(a, m, V), (3.82) In g(Z) = Eajmjv,0[lnp(Z, Z, 0, m, V, a)] +const(Z). Подставляя в выражение (3.80) совместную модель (3.44), априорные распределения параметров (3.55), правдоподобие (3.32) вместо p(Z0,a) и p(Z0, а), воспользовавшись верхней оценкой softmax (3.52) и взяв логарифм от обоих частей получившегося равенства, получаем где (W, z/) - нормировочный множитель в распределении Уишарта (3.55), индекс t Є {1,..., Т} соответствует документам х тестовой выборки Df, Т - число документов тестовой выборки, а вектор вариационных параметров t соответствует верхней оценке softmax для документа х . Подставляя (3.83) в (3.82) и группируя соответствующие слагаемые, получаем следующие леммы.

Лемма 5. Фактор q(ct) из (3.82) имеет нормальное распределение. Доказательство. Оставляя в (3.83) только члены, зависящие от а получаем: т Kh / Kh ( , \ Inq(a) = J2Y1 E xt TAMfcE6/fc - Eztk 6Xp fc,jxt TAMFE6 F + t=i k=i k =i 9{ы) N Kh /t n + 2 2 тпАМкЕЄк znk n=\ k=\ ЄХР 5П - -aTa + aaTa0 + const(a). (3.84) Преобразуем иерархическую функцию сходства так, чтобы она явным образом зависела от а: \w\ \w\ х;ЛМ = хпт{Мквк)т + aT inm(Mfe )mtm = m=l m=l = aT xnm(Mkek)mLm + const(a). (3.85) m=l Подставив (3.85) в (3.86) получаем выражение, которое после группировки слагаемых, содержащих а, принимает вид квадратичной формы а \nq(a.) = —(а — а.о)т1(а. — ао) + const(а), (3.86) где ао задается как \w\ т к \w\ т кн U \Kh ra=l t=l k=l 9\t) k =l (3.87) xnmim [mktvk)m ЄХР1 +Vy rrnmtm V(MfcE6Um m=l n=l ;=! Так как при умножении (3.44) на p(Z0,a), слагаемые, зависящие от т и V& никак не изменились, то факторы q(mk,\ k) имеют вид, полученный в леммах 1 и 2. Получим выражение для факторов q(0k).

Лемма 6. Фактор q(6) из (3.82) разбивается на произведение факторов q(0k), каждый из которых имеет нормальное распределение. Доказательство. Оставляя в (3.83) только члены, зависящие от в получаем: т Kh (Kh (Р \ \ In д(в) =J2J2 ЕІ№тЕаЛМ - Eztk J2 xt T EQAMFflF + t=i k=i k =i 9{ы) N Kh , (t \\ + Yl Yl Еалмкок Znk n=\ k=\ 7 (3.88) 9{n) % \ Y Emfc,vfc(0fc - шку\к(вк - mk) + const(0). Подставляя математическое ожидание (3.64) и группируя (3.88) относительно вк получаем, что фактор q(6) представим в виде произведения нормальных распределений, так как его логарифм разбивается на сумму квадратичных форм относительно вк: lnq(6) = 2 {0 k — шокУ к(вк — т ок) + const(0), (3.89) к=\ где параметры т.ок выражаются как Т К, / 1 -Ьтпчгтг- \ г- ЄХр( Л) V ,_ ток = то/; Н—;(Wfc ) ШкЕаА ,xt -ztk / E-Ztk l/TTT_hTTr. А Л / exp(njfe)\ -\—[уук ) M EQA 2,xn znk (t (3.90) v n=i 9\Sn) Лемма 7. Фактор g(Z) из (3.82) факторизуется на произведение факторов q(ztk), каждый из которых имеет вид распределения Бернулли. Доказательство. Логарифм распределения Бернулли представим в виде \np(ztk) = lnpflk(l-ptk)l- Ztk = ztklnptk + (1 - ztk)ln(l-ptk) = = ztkln( 1 +ln(l-Of ). (3.91) l-ptk Взяв математическое ожидание (3.83) по всем параметрам кроме Ztk и оставив только слагаемые, зависящие от Ztk, получаем q(ztk) = Ztk Г- ln#(t) + Ctk] + const(ztk) = kk In ІЦ exp (Ctk)] + const( jfe), (3.92) где для удобства введено обозначение (tk = "ЕаЛМ&Е0& + у ( tk — х ЕаЛМ&/Е0&/). (3.93) f=i 9{t) Параметр распределения ptk является решением уравнения 1 1 ,, exp(Ctfc) 1 =— exp [Ctk) = Ptk = . (3.94) X Vtk g(t) exp(Ctfc)+ (6 Таким образом, факторы q(ztk) имеют распределение Бернулли с параметра ми ptk, заданными (3.94). Теорема 6. Функцией q из класса (3.81), заданной оптимальными оценками факторов (3.82), в которых правдоподобие L (3.32) оценивается с помощью верхней оценки функции softmax (3.52), а априорные распределения параметров 0,т, V, а задаются как (3.43) и (3.42), является Kh \Т\ q(Z, 0, m, V, а) = q(a) ]J q(Ok)q(mk\Vk)q(Vk) П q{ztk), k=i t=i (3.95) q{ek) M{m!0k){v V q(mk\Vk) M(m0kAb Vk)-l)i g(VA) W(WA,i/), q{a) Af(a0,a-lI), q(ztk) Bemiptk), с параметрами, заданными (3.58), (3.60), (3.87), (3.90), и (3.94) соответственно. Доказательство. Согласно (3.82), подставляем результаты лемм 1, 2, 5, 6, 7 в (3.81), что дает утверждение теоремы.

Для настройки параметров данных распределений используется аналогичный EM-алгоритм, как и в случае оценки апостериорного распределения. На E шаг добавляется вычисление математического ожидания Eztk = Ptk и пересчет параметров рц . Применяя результаты теоремы 4 для вариационных параметров t, получаем их оптимальные значения при фиксированных параметрах q: Ігк = ±JAMkm ok.