Модификация, разработка и реализация методов классификации новостных текстов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Шаграев, Алексей Галимович

• Шаграев, Алексей Галимович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Шаграев, Алексей Галимович

Содержание

Введение

1. Задача текстовой классификации как задача обучения по прецедентам

1.1 Оценка качества методов классификации

1.1.1 Метрики точности и полноты

1.1.2 Метрика Accuracy

1.1.3 Метрика AUC

1.1.4 Комбинированные метрики

1.2 Методы решения задачи текстовой классификации

1.2.1 Наивный байесовский метод

1.2.2 Метод ближайших соседей

1.2.3 Оценка качества

2. Задача классификации текстов

2.1 Линейные методы классификации

2.1.1 Наивный байесовский метод и его модификации

2.1.2 Логистическая регрессия

2.2 Модельные деревья решений

2.2.1 Одномерная линейная регрессия

2.2.2 Инкрементальное обновление

2.2.3 Многомерная линейная регрессия

2.3 Алгоритмические композиции

2.3.1 Алгоритмические композиции в задаче регрессии

2.3.2 Алгоритмические композиции в задаче бинарной классификации

2.4 Матричное разложение как метод выделения признаков

2.5 Выводы

3. Экспериментальное исследование рассмотренных методов

3.1 Методика экспериментального исследования

3.1.1 Метод скользящего контроля

3.1.2 Стратификация

3.2 Исследуемые наборы данных

3.2.1 Коллекция ЯеШегБ-21578

3.2.2 Коллекция иС1

3.3 Результаты численных экспериментов

3.3.1 Линейные методы классификации

3.3.2 Линейные методы восстановления регрессии

3.3.3 Модельные деревья решений в задаче восстановления регрессии

3.3.4 Алгоритмические композиции на основе модельных деревьев в задачах классификации

3.4 Выводы

Заключение

4. Список сокращений и условных обозначений

Литература

5. Приложение. Тексты программ для решения задач линейной регрессии

Введение диссертации (часть автореферата) на тему «Модификация, разработка и реализация методов классификации новостных текстов»

ВВЕДЕНИЕ

Классификация текстов - одна из важных задач информационного поиска [26], заключающаяся в отнесении документа к одной или нескольким категориям (классам) из некоторого заранее определенного набора на основании анализа содержания этого документа.

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

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

• фильтрация спама;

• контекстная реклама;

• автоматическое реферирование наборов текстов;

• категоризация (рубрикация) в агрегирующих системах;

• обеспечение разнообразия поисковой выдачи и другие.

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

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

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

1. Тексты являются текстами на естественном языке, не имеют четкой формализации, не структурированы, не являются техническими.

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

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

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

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

Для достижения этой цели в диссертации решаются следующие задачи:

1. Разработка способов признакового описания текстовых документов.

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

3. Разработка модифицированных версий классических алгоритмов машинного обучения.

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

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

6. Разработка метода понижения размерности в задаче классификации текстов.

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

8. Сравнительный анализ рассмотренных методов применительно к задаче классификации текстов.

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

Научная новизна. Основные результаты работы являются новыми, оригинальными и заключаются в следующем:

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

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

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

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

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

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

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

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

Практическая ценность.

1. Осуществлена программная реализация всех предложенных методов.

2. В результате исследований на коллекциях задач из репозитория иС1 [22] было установлено, что предложенные методы решения задач восстановления регрессии и классификации значительно превосходят по качеству получаемых моделей известные методы.

3. В результате экспериментов на коллекции текстовых документов 11еШ:ег8-21578 [24] было установлено, что предложенные модификации стандартных линейных методов классификации значительно превосходят по качеству моделей стандартные методы. Так, удалось добиться улучшения показателей качества наивного байесовского метода на 20% по сравнению с оригинальным методом, а для метода логистической регрессии-на 8%. Также было установлено, что алгоритм, основанный на алгоритмической композиции

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

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

Апробация. Положения диссертационной работы докладывались на XVII ежегодной международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 2011 году, XVIII ежегодной международной конференции «Информационные средства и технологии» в 2010 году, на рабочих совещаниях и выступлениях в компании «Яндекс».

Публикации. По теме диссертации опубликовано четыре научные работы, в том числе две - в изданиях по перечню ВАК.

Объем и структура работы. Диссертация состоит из введения, трех глав и заключения. Список использованной литературы содержит 54 наименования. Текст диссертации содержит 108 страниц машинописного текста, включая 16 рисунков и 7 таблиц.

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

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

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

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

Наконец, предлагается метод матричного разложения в качестве способа снижения размерности в задаче классификации текстов. Этот метод может рассматриваться и в качестве метода тематического моделирования, позволяющего учитывать некоторые семантические особенности текстов.

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

Эксперименты подтверждают значительный рост качества предложенных автором линейных методов классификации по сравнению со стандартными методами.

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

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

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

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

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

1. ЗАДАЧА ТЕКСТОВОЙ КЛАССИФИКАЦИИ КАК ЗАДАЧА ОБУЧЕНИЯ ПО ПРЕЦЕДЕНТАМ

Неформально задача обучения по прецедентам [45] может быть сформулирована следующим образом. Имеется множество объектов и множество возможных ответов. Существует некоторая зависимость между объектами и ответами - целевая функция, но она неизвестна. Известно только конечное множество прецедентов - пар, состоящих из объектов и соответствующих им ответов. Это множество будем называть выборкой. На основе множества прецедентов необходимо восстановить неизвестную зависимость, то есть, построить алгоритм, способный для всякого объекта предсказать соответствующий ему ответ. Этот алгоритм будет называться решающей функцией. Значения решающей функции будем называть предсказаниями. Способ построения решающей функции по множеству прецедентов называется методом обучения, а процесс построения решающей функции будем называть процессом обучения. Выборку, используемую в процессе обучения, будем называть обучающей выборкой.

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

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

требования рассматривается другая выборка прецедентов, никак не связанная с обучающей - тестовую {контрольную), и измерить качество предсказаний на ней.

Способность осуществлять качественные предсказания не только на объектах обучающей выборке, но и на других объектах, называется обобщающей способностью.

Более формально, будем считать, что имеется множество объектов X, множество ответов У и существует неизвестная целевая функция значения которой измерены на конечном подмножестве X' сХ,\Х'\ =1

Обучающая выборка X1 определяется тогда следующим образом:

X1 = {(ХиУг)6 Г,у, = Г(*)}и.

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

Если а & А, х е X то значение а(х) называется предсказанием решающей функции а на объекте х.

Функционал качества (2 (а равно и функционал потерь) - это функция, определенная для всякой выборки и решающей функции. Если Хь - тестовая выборка, то значение функционала

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

выборки. Вопросы получения более содержательных оценок обсуждаются в главе 3.

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

В зависимости от множества ответов различают следующие задачи машинного обучения:

• задача восстановления регрессии, если У = М;

• задача бинарной классификации, если |У| = 2;

• задача мультиклассификации, если |У| = п

и другие некоторые другие. Для бинарной классификации обычно полагают У = {—1,+1}.

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

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

конкретный класс индивидуальным образом. Поэтому будем рассматривать здесь только задачу бинарной текстовой классификации.

Итак, будем считать, что заданы:

• непустое множество термов {слов) IV = {w1,

• множество документов £) = ..., каждый из которых является вектором термов: с^ = (и^м^,м^.)7,1 < / < Ы;

• подмножество С с О документов, которые считаются релевантными, т.е. относящимися к исследуемому классу.

Множество всех различных слов, входящих в документ (¿¿, будем обозначать Ь(с^).

Определим функцию принадлежности у: И {—1,+1}:

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

1.1 Оценка качества методов классификации

В этом разделе будут рассмотрены различные способы определения показателей качества классификаторов в задаче бинарной классификации с множеством ответов У — {—1, +1}.

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

Ы,+1}.

Итак, пусть имеется выборка X1 и решающая функция а. 1.1.1 Метрики точности и полноты

Определим следующие величины:

• количество верно определенных экземпляров положительного класса (true positives, TP):

TP(Xl,a) = [у = +1ла(*) = +1];

{x,y)exl

• количество верно определенных экземпляров отрицательного класса (true negatives, TN):

TN(Xl,a)= ^ [у = —1Л a(x) = —1];

<x,y)exl

• количество неверно определенных экземпляров положительного класса (false positives, FP):

FP{Xl,a) = ^ [у = —1Л a(x) = +1];

(x,y)exl

• количество неверно определенных экземпляров отрицательного класса (false negatives, FN):

FN(Xl,a) = ^ [у — —1A cz(x) — —1].

ix.y) EX1

Используя эти величины, можно определить метрики точности (precision, Р) и полноты (recall, R) [28]:

„ . . ТР(Х1,а)

Р(Х1,а) =

R(Xl, а) =

TP(Xl,a) + FP(Xl, а)'

ТР(Х1,а) TP(Xl, а) + FN(Xl,a.y

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

Такая интерпретация является весьма естественной для многих приложений. Рассмотрим, к примеру, новостной сервис, задача которого - продемонстрировать пользователю страницу, содержащую новости по некоторой тематике. Для такого сервиса вполне естественными являются следующие вопросы:

• Какая доля показанных новостей действительно относятся к заявленной тематике?

• Какова доля показанных новостей среди всех новостей, относящихся к данной тематике?

Легко видеть, что значение метрики точности является ответом на первый вопрос, а значение метрики полноты - ответом на второй вопрос.

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

1.1.2 Метрика Accuracy

Метрика Accuracy [26] определяется следующим образом:

TP(Xl,a) + TN(Xl,a)

AccuracyiX1 ,а) =

I*1!

В качестве соответствующего функционала потерь используется метрика Error:

Err or (X1, а) =

FP(Xl,a) + FN(Xl,a)

ОТ

= 1 — Ac cur асу {X1, a).

Интерпретация этих метрик также достаточно очевидна. Значение метрики Accuracy равняется доле верных, а метрики Error - доле

Данные метрики находят свое применение в различных задачах классификации и мультиклассификации, однако именно в задачах текстовой классификации (и некоторых других задачах бинарной классификации) их использование представляется сомнительным. Задачи текстовой классификации, как правило, являются сильно несбалансированными, т.е. количество объектов отрицательного класса значительно превосходит количество объектов положительного класса. В такой ситуации использование метрик, для которых верные отрицательные предсказания столь же важны, сколь и верные положительные предсказания, могут привести к совершенно неадекватным результатам. Рассмотрим простой пример, сравнив две решающих функции, аг и а2, на выборке X1 размера 1000:

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

Более того, оказывается [40], что решающая функция, всегда предсказывающая отрицательный класс, с точки зрения метрики

ошибочных предсказаний среди всех предсказаний.

ТР(Х1,а1)= 10, TN(Xl,a^) = 970, FP(Xl,aJ = 10,

FN(Xl,a1) = Ю,

TP(Xl,a2) = 0, TN(Xl, а2) = 980, FP(Xl,a2) = 0, FN(Xl,a2) = 20.

Accuracy может превосходить любые нетривиальные методы классификации. Ясно, что причиной этого является нечувствительность метрики к распределению верных ответов между положительным и отрицательным классом, как замечено в [7].

1.13 Метрика AUC

Предположим, что решающая функция определяется при помощи некоторой другой функции f:X Ж (например, путем сравнения значения функции / с некоторым порогом).

Тогда метрику AUC [25] можно определить как вероятность того, что для пары из случайно выбранного экземпляра положительного класса и случайно выбранного экземпляра отрицательного класса величина функции / окажется большей для экземпляра положительного класса. Легко будет определить ее значение, введя следующие обозначения:

Х+={(х,у)еХ1\у = +1}, Х- = {(х,у) Е Х1\у =-1].

Тогда

X PR Z !/«>/(*')!.

(х,у)ех+ (х'У)ех-

Эта метрика подробно обсуждается в работе [26], где показывается, что с точки зрения нескольких достаточно важных показателей метрика AUC превосходит метрику Accuracy.

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

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

1.1.4 Комбинированные метрики

Итак, из этого краткого обзора становится понятным, что метрики точности и полноты являются наиболее адекватными метриками качества классификации.

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

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

ab(d) = sign(/(*) - Ь), где / - некоторая вещественная функция, определенная на X.

Рассмотрим здесь некоторые из них:

• Точность, усредненная по 11 точкам (eleven-point average precision [26]). Метрика классификации, аналогичная часто использующейся в информационном поиске метрике средней

точности. Выбираются 11 порогов Ь00,Ь0...,Ь0ш9,Ъ1Л, таких, что при их использовании метрика полноты принимает соответственно значения 0.0, 0.1,...,0.9 и 1.0. В этих же точках измеряются значения метрики точности, которые затем усредняются. Эта метрика является аналогом известной метрики mean average precision (MAP [26]), используемой в информационном поиске и весьма часто используется при анализе методов классификации текстов (см., например, [32,33,34,40,41,42]).

Точка равновесия точности и полноты (precision-recall breakeven point [1]). Порог b определяется таким образом, что значения точности и полноты при использовании этого порога оказываются одинаковыми. На практике точного равенства добиться, как правило, невозможно, однако, можно использовать тот факт, что метрика точности как правило возрастает при увеличении порога, а метрика полноты, напротив, при этом падает. Поэтому в качестве точки равновесия можно выбрать точку пересечения графиков точности и полноты после линейной интерполяции. Метрикой является равновесное значение точности и полноты. Эта метрика является чрезвычайно популярной в литературе, посвященной классификации текстов (см., например, [1,8,9,11,19,20,23,24]).

F^-мера Ван Ризбергена [38]. Эта метрика определяется следующим образом:

F(yl , (/?2 + 1 )-P(Xl,a)-R(Xl,a) >а> f$2P(Xl,a) + R(Xl,a) '

Параметр /? выступает в качестве коэффициента, который отражает «важность» точности в сравнении с полнотой. Особый

интерес представляет частный случай /? = 1, для которого метрика называется сбалансированной или просто ^-мерой, а ее значение становится в точности равным среднему гармоническому точности и полноты. Эта метрика качества также весьма часто используется в литературе, посвященной классификации текстов (см., например, [7,24,38]).

В настоящей работе в качестве основной метрики для оценки качества классификации используется FrMepa.

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

Использование же точки равновесия точности и полноты, на взгляд автора, представляется методологически неверным, т.к. для определения точки равновесия на тестовой выборке необходимо использовать разметку. Стоит также обратить внимание на следующие недостатки этой метрики, нашедшие отражение в литературе:

Список литературы диссертационного исследования кандидат наук Шаграев, Алексей Галимович, 2014 год

ЛИТЕРАТУРА

1. Apte С., Damerau F. J., Weiss S. M. Automated learning of decision rules for text categorization // ACM Trans, on Inform. Syst. - Vol 12 №3. - 1994.

2. Baker L. D., McCallum A. K. Distributional clustering of words for text classification // In Proceedings of SIGIR-98, 21st ACM International Conference on Research and Development in Information Retrieval. - 1998.

3. Bentley J. L. Multidimensional binaiy search trees used for associative searching // Communications of the ACM. - 1975.

4. Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet Allocation // Journal of Machine Learning. - 2002. - №3.

5. Bottou L. Large-Scale Machine Learning with Stochastic Gradient Descent. [Электронный ресурс]. - Режим доступа: http://leon.bottou.org/pubHcations/pdf7compstat-2010.pdf

6. Breiman L. Random Forests // Machine Learning. - №45. - 2001.

7. Cohen W. W. Learning to classify English text with ILP methods. // Advances in Inductive Logic Programming, L. De Raedt, ed. IOS Press, Amsterdam, The Netherlands. - 1995.

8. Cohen W. W., Singer Y. Contextsensitive learning methods for text categorization // ACM Trans. Inform. Syst. - Vol. 17 №2. - 1999.

9. Dagan I., Karov Y., Roth D. Mistakedriven learning in text categorization // In Proceedings of EMNLP-97, 2nd Conference on Empirical Methods in Natural Language Processing (Providence, RI, 1997). - 1997.

10. De Berg M. Computational Geometry: Algorithms and Applications. -Springer. - 2008.

11. Domingos P., Pazzani M. J. On the optimality of the simple Bayesian classifier under zero-one loss // Machine Learning. Mach. Learn. - Vol. 29, №2-3.

12. Freund Y., Schapire R. Experiments with a new boosting algorithm // In Proceedings of the Thirteenth International Conference on Machine Learning. - 1996.

13. Friedman J. H., Bentley J. L., Finkel R. A. An Algorithm for Finding Best Matches in Logarithmic Expected Time // ACM Transactions on Mathematical Software. - №3. - 1977.

14. Friedman, J. H. Greedy function approximation: a gradient boosting machine // Technical report, Dept. of Statistics, Stanford University. -1999.

15. Fuhr N. Models for retrieval with probabilistic indexing // Information Processing and Management. - Vol. 25 №1. - 1989.

16. Genkin A., Madigan D., Lewis D. D.. Sparse logistic regression for text categorization. [Электронный ресурс]. - Режим доступа: http://dimacs.mtgers.edu/Research/MMS/loglasso-v3a.pdf.

17. Hofmann, Т., Puzicha, J., Jordan, M. I. Unsupervised learning from dyadic data // Advances in Neural Information Processing Systems. -1999. -№11.

18. Holmes G., Donkin A. Witten I. H. Weka: A machine learning workbench // Proc Second Australia and New Zealand Conference on Intelligent Information Systems, Brisbane, Australia. - 1994.

19. Joachims T. Text categorization with support vector machines: learning with many relevant features // In Proceedings of ECML-98, 10th European Conference on Machine Learning. - 1998.

20. Joachims T. Transductive inference for text classification using support vector machines // In Proceedings of ICML-99, 16th International Conference on Machine Learning. - 1999.

21. Koller D., Sahami M. Hierarchically classifying documents using very few words // In ACM Computing Surveys. - Vol. 34 №1. - 2002.

22. Langley P. Crafting papers on machine learning // Proceedings of the 17th International Conference on Machine Learning. - 2000.

23. Lewis D. D. An evaluation of phrasal and clustered representations on a text categorization task // In Proceedings of SIGIR-92, 15th ACM International Conference on Research and Development in Information Retrieval. - 1992.

24. Lewis, D. D. Representation and Learning in Information Retrieval // PhD thesis, Department of Computer Science, University of Massachusetts. - 1992.

25. Ling C. X., Huang J., Zhang H. AUC: a statistically consistent and more discriminating measure than accuracy // Proceedings of 18th International Conference on Artificial Intelligence. -2003.

26. Manning, C. D., Raghavan, P., Schütze, H. Introduction to Information Retrieval // Cambridge, England: Cambridge University Press. - 2008.

27. McCallum A. K., Rosenfeld R. Mitchell T. M., NG A. Y. Improving text classification by shrinkage in a hierarchy of classes // In Proceedings of ICML-98, 15th International Conference on Machine Learning. - 1998.

28. Powers D. M. Evaluation: From precision, recall and f-factor to roc, informedness, markedness and correlation. // Technical report, School of Informatics and Engineering, Flinders University Adelaide, South Australia. - 2007.

29. Quinlan J. R. C4.5: Programs for Machine Learning. - San Mateo: Morgan Kaufmann Publishers Inc. — 1993.

30. Quinlan J. R. Learning with continuous Classes // In 5th Australian Joint Conference on Artificial Intelligence Singapore. - 1992.

31. Salton G., Buckley C. Term-weighting approaches in automatic text retrieval // Information Processing and Management. - Vol. 25 №5. -1998.

32. Schapire R. E., Singer Y. BoosTexter: a boosting-based system for text categorization // Machine Learning. - Vol. 39, №2-3. - 2000.

33. Schutze H., Hull D. A., Pedersen J. O. A comparison of classifiers and document representations for the routing problem // In Proceedings of SIGIR-95, 18th ACM International Conference on Research and Development in Information Retrieval. - 1995.

34. Sebastiani F. Machine Learning in Automated Text Categorization. [Электронный ресурс]. - Режим доступа: httpy/nmis.isti.cnr.it/sebastiani/Publications/ACMCS02.pdf

35. Sherman J., Morrison W. J. Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix // Annals of Mathematical Statistics. - 1949.

36. Steel R. G. D, Torrie J. H. Principles and Procedures of Statistics with Special Reference to the Biological Sciences. - McGraw Hill. - 1960.

37. Strang G. Introduction to Linear Algebra (3rd edition ed.). -Wellesley-Cambridge Press: Wellesley, MA. - 2003.

38. Van Rijsbergen (^.Information Retrieval, 2nd ed. - Butterworths, London, UK. - 1979.

39. Wang, Y., Witten, I. H. Induction of model trees for predicting continuous classes // Proceedings of the poster papers of the European Conference on Machine Learning, University of Economics, Faculty of Informatics and Statistics, Prague. - 1997.

40. Yang Y. An evaluation of statistical approaches to text categorization // Information Retrieval. - Vol. 1, №1-2. - 1999.

41. Yang Y., Liu X. A re-examination of text categorization methods. // Proceedings of SIGIR-99, 22nd ACM International Conference on Research and Development in Information Retrieval. - 1999.

42. Yang Y., Pedersen J. O. A comparative study on feature selection in text categorization // In Proceedings of ICML-97, 14th International Conference on Machine Learning. - 1997.

43. Zhao Y., Zhang Y. Comparison of decision tree methods for finding active objects. [Электронный ресурс]. - Режим доступа: http У/arxiv. о rg/p df/0708.4274.p df.

44. Амосов А. А., Дубинский Ю. А., КопченоваН. В. Вычислительные методы для инжинеров. — М.: Высшая школа. - 1994.

45. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. - М.: Наука. - 1979.

46. Воронцов К.В. Комбинаторные оценки качества обучения по прецедентам // Доклады РАН. - 2004. - Т. 394, №2.

47. Воронцов К.В. Обзор современных исследований по проблеме качества обучения алгоритмов. [Электронный ресурс]. - Режим доступа: Ьйр,У/уАУШ.ссаз.ги/Ггс/рарег5/уогоп041л¥т.риГ

48. Коршунов А., Гомзин А. Тематическое моделирование текстов на естественном языке // Труды Института системного программирования РАН. — 2012.

49. Тихонов А.Н. О решении некорректно поставленных задач и методе регуляризации. - ДАН СССР. - 1963. - Т. 151. № 3

50. Тихонов А.Н. Об устойчивости обратных задач. - ДАН СССР. -1943. - Т. 39. № 5.

51. Шаграев А. Г., Бочаров И. А. Фальк В. Н. Трансдуктивное обучение логистической регрессии в задаче классификации текстов. // Программные продукты и системы. - №2. - 2014.

52. Шаграев А. Г., Фальк В. Н. Линейные классификаторы в задаче классификации текстов // Вестник МЭИ. - №4. - 2013.

53. Шаграев А. Г., Фальк В. Н. Сети и сетевые языки. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2010). - Т.З. - 2010.

54. Шаграев А. Г., Фальк В. Н. Статистически обоснованный метод обрезания регрессионных деревьев. // Радиоэлектроника, электротехника и энергетика: Семнадцатая Междунар. науч-техн. конф. студентов и аспирантов: Тез. докл. В 3-х т. - Т. 1. - 2011.

5. ПРИЛОЖЕНИЕ. ТЕКСТЫ ПРОГРАММ ДЛЯ РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОЙ РЕГРЕССИИ

Приведем программный код библиотеки, при помощи которой можно вычислять суммы квадратов отклонений для линейных регрессионных моделей, построенных по методам sir, bslr и plr, а также для вычисления суммы квадратов отклонения ответов от их среднего.

Реализация приведена с использованием языка программирования С++, разработка производилась в среде MS Visual Studio 2013.

#include <algorithm>

#include <vector> #include <iostream> ♦include <string>

using std::min; using std::max;

using std::vector; using std:¡string;

using std::cout; using std::cerr;

using std::pair; using std::make_pair;

class TGoalsDeviationCalculator { private:

double SumGoals; double SumSquaredGoals; double SumWeights; public:

explicit TGoalsDeviationCalculator(double sumGoals = 0.,

double sumSquaredGoals = 0., double sumWeights = 0.)

: SumGoals(sumGoals) , SumSquaredGoals(sumSquaredGoals) , SumWeights(sumWeights)

{ }

inline double SumSquaredErrors() const { if (¡SumWeights) { return 0.;

}

double sumSquaredErrors = SumSquaredGoals - SumGoals / SumWeights * SumGoals;

return max(0., sumSquaredErrors);

}

inline void Add(double goal, double weight) { double weightedGoal = goal * weight; SumGoals += weightedGoal; SumSquaredGoals += goal * weightedGoal;

SumWeights += weight;

class TSLRDeviationCalculator { private:

double SumFeatures; double SumSguaredFeatures;

double SumGoals; double SumSguaredGoals;

double SumProducts;

double SumWeights; public:

explicit TSLRDeviationCalculator(double sumFeatures = 0.,

double sumSguaredFeatures = 0., double sumGoals = 0. , double sumSguaredGoals = 0., double sumProducts = 0., double sumWeights = 0.)

: SumFeatures(sumFeatures) , SumSguaredFeatures(sumSguaredFeatures) , SumGoals(sumGoals) , SumSguaredGoals(sumSguaredGoals) , SumProducts(sumProducts) , SumWeights(sumWeights)

{ }

template ctypename F, typename G>

inline void Add(const vector<F>& features, const vector<G>& goals) { YASSERT(features.size() == goals .size ()) ;

const F* feature = features.begin(); const G* goal = goals.begin();

for (; feature != features.end(); ++feature, ++goal) { Add (*goal, 1., *feature);

)

}

template ctypename F, typename G, typename W>

inline void Add(const vector<F>& features, const vector<G>& goals, const vector<W>& weights) {

YASSERT(features.size() == weights.size()); YASSERT(goals.size() == weights.size());

const F* feature = features.begin(); const G* goal = goals.begin(); const W* weight = weights.begin();

for (; feature != features.end(); ++feature, ++goal, ++weight) { Add(*goal, *weight), *feature);

}

}

inline double SumSguaredErrors(double sumGoals, double sumSguaredGoals, double sumFeatureGoalProducts) const { if (¡SumWeights) { return 0.;

double sumGoalSguaredDeviations = sumSguaredGoals - sumGoals / SumWeights * sumGoals;

double denominator = SumSquaredFeatures - SumFeatures / SumWeights SumFeatures;

if (¡denominator) {

return sumGoalSquaredDeviations;

}

double numerator = sumFeatureGoalProducts - SumFeatures / SumWeight

* sumGoals;

double sumSquaredErrors = sumGoalSquaredDeviations - numerator * numerator / denominator;

return max(0., sumSquaredErrors);

}

inline double SumSquaredErrors() const {

return SumSquaredErrors(SumGoals, SumSquaredGoals, SumProducts);

>

void Solve(double sumGoals,

double sumFeatureGoalProducts, doubles factor, doubles offset) const

{

if (¡SumGoals) {

factor = offset = 0.; return;

}

double denominator = SumSquaredFeatures - SumFeatures / SumWeights SumFeatures;

if (¡denominator) {

factor = 0.;

offset = sumGoals / SumWeights; return;

}

double numerator = sumFeatureGoalProducts - SumFeatures / SumWeight

* sumGoals;

factor = numerator / denominator;

offset = sumGoals / SumWeights - factor * SumFeatures / SumWeights;

}

void Solve(doubles factor, doubles offset) const { Solve(SumGoals, SumProducts, factor, offset);

}

inline void Add(double goal, double weight, double feature) { double weightedFeature = feature * weight; double weightedGoal = goal * weight;

SumFeatures += weightedFeature;

SumSquaredFeatures += feature * weightedFeature;

SumGoals += weightedGoal; SumSquaredGoals += goal * weightedGoal;

SumProducts += feature * weightedGoal;

SumWeights += weight;

}

double GetSumFeatures() const { return SumFeatures;

}

double GetSumProducts() const {

return SumProducts;

class TBSLRDeviationCalculator { private:

vector<TSLRDeviationCalculator> SLRDeviationCalculators;

typedef vector<TSLRDeviationCalculator>::iterator TSLRIterator; typedef vector<TSLRDeviationCalculator>::const_iterator TConstSLRIterator; public:

explicit TBSLRDeviationCalculator(size_t featuresCount) : SLRDeviationCalculators(featuresCount)

{ }

double SumSquaredErrors() const {

TConstSLRIterator slrCalculator = SLRDeviationCalculators.begin (); double bestSumSguaredErrors = slrCalculator->SumSguaredErrors(); for (++slrCalculator; slrCalculator != SLRDeviationCalculators.end(); ++slrCalculator) {

bestSumSguaredErrors = min(bestSumSquaredErrors, slrCalculator-

>SumSquaredErrors () ) ; }

return bestSumSguaredErrors;

}

inline void Add(const vector<double>& features, double goal, double weight) {

TSLRIterator slrCalculator = SLRDeviationCalculators.begin() ; vector<double>::const_iterator feature = features.begin(); for (; feature != features.end(); ++feature, ++slrCalculator) { slrCalculator->Add(goal, weight, *feature);

}

}

} ;

class TLinearizedSguareOLSMatrix : public vector<double> { private:

typedef vector<double> TBase; size_t Size; public:

TLinearizedSquareOLSMatrix(size_t featuresCount)

: TBase ((featuresCount + 1) * (featuresCount + 1)) , Size(featuresCount + 1)

{ }

void AddTriangle(const vector<double>& features, double weight) { vector<double>::const_iterator leftFeature = features.begin(); vector<double>::iterator matrixElement = this->begin(); size_t offset = 0;

for (; leftFeature != features.end(); ++leftFeature, ++matrixElement, ++offset) {

double weightedFeature = weight * *leftFeature; matrixElement += offset;

vector<double>::const_iterator rightFeature = features.begin(); for (; rightFeature != features.end(); ++rightFeature, ++matrixElement) {

*matrixElement += weightedFeature * *rightFeature;

}

*matrixElement += weightedFeature;

this->back() += weight;

void RestoreFromTriangle() {

for (vector<double>::iterator diagonalElement = this->begin(); diagonalElement < this->end{); diagonalElement += Size +1) {

vector<double>::iterator rowElement = diagonalElement + 1; vector<double>::iterator columnElement = diagonalElement + Size; while (columnElement < this->end()) { *columnElement = *rowElement; ++rowElement; columnElement += Size;

}

}

}

class TOLSVector : public vector<double> { private:

typedef vector<double> TBase; public:

TOLSVector(size_t featuresCount) : TBase (featuresCount + 1)

{ }

void Add(const vector<double>& fea tureS/ double goal, double weight) { double weightedGoal = goal * weight;

vector<double>::iterator vectorElement = this->begin(); for (vector<double>::const_iterator feature = features.begin(); feature != features.end(); ++feature, ++vectorElement) { *vectorElement += *feature * weightedGoal;

}

*vectorElement += weightedGoal;

}

};

class TPositionalLRCalculator { private:

size_t FeaturesCount; size_t IterationsCount;

TLinearizedSquareOLSMatrix OLSMatrix;

vector<TSLRDeviationCalculator> SLRDeviationCalculators; vector<double> SumGoalProducts;

double SumGoals; double SumSquaredGoals; double SumWeights;

typedef vector<TSLRDeviationCalculator>:: iterator TSLRIterator; typedef vector<TSLRDeviationCalculator>::const_iterator TConstSLRIterator; public:

TPositionalLRCalculator(size_t featuresCount, size_t iterationsCount) : FeaturesCount(featuresCount) , IterationsCount(iterationsCount) , OLSMatrix(featuresCount) , SLRDeviationCalculators(featuresCount) , SumGoalProducts(featuresCount) , SumGoals(0.) , SumSquaredGoals(0.) , SumWeights (0.)

{ }

double SumSquaredErrors() { InitGoalProducts() ;

double sumGoals = SumGoals;

double sumSquaredGoals = SumSquaredGoals;

for (size_t iterationNumber = 0; iterationNumber < IterationsCount; ++iterationNumber) {

pair<TConstSLRIterator, double> bestSplitterlnfo = GetBestSplitter (sumGoals, sumSquaredGoals);

TConstSLRIterator bestSplitter = bestSplitterlnfo.first; double bestSumSquaredErrors = bestSplitterlnfo.second;

ProcessBestSplitter(bestSplitter, sumGoals);

sumGoals = 0.;

sumSquaredGoals = bestSumSquaredErrors;

}

return sumSquaredGoals;

}

inline void Add(const vector<double>& features, double goal, double weight) {

OLSMatrix.AddTriangle(features, weight);

vector<double>::const_iterator feature = features.begin(); for (TSLRIterator slrCalculator = SLRDeviationCalculators.begin(); slrCalculator != SLRDeviationCalculators.end(); ++slrCalculator, ++feature) { slrCalculator->Add(goal, weight, *feature);

}

double weightedGoal = goal * weight; SumGoals += weightedGoal; SumSquaredGoals += goal * weightedGoal;

SumWeights += weight;

}

private :

void InitGoalProducts() (

vector<double>::iterator sumGoalProducts = SumGoalProducts.begin(); TConstSLRIterator slrCalculator = SLRDeviationCalculators.begin(); for (; sumGoalProducts != SumGoalProducts.end(); ++sumGoalProducts, ++slrCalculator) {

*sumGoalProducts = slrCalculator->GetSumProducts();

}

}

pair<TConstSLRIterator, double> GetBestSplitter(double sumGoals, double sumSquaredGoals) {

TConstSLRIterator bestSLRDeviationCalculator = SLRDeviationCalculators.begin() ;

vector<double>::const_iterator sumGoalProducts = SumGoalProducts.begin() ;

double bestSumSquaredErrors = bestSLRDeviationCalculator->SumSquaredErrors(sumGoals, sumSquaredGoals, *sumGoalProducts);

TConstSLRIterator slrCalculator = bestSLRDeviationCalculator + 1;

for (++sumGoalProducts; slrCalculator != SLRDeviationCalculators.end() ; + + slrCalculator, ++sumGoalProduc ts ) {

double sumSquaredErrors = slrCalculator->SumSquaredErrors(sumGoals, sumSquaredGoals, *sumGoalProducts);

if (sumSquaredErrors < bestSumSquaredErrors) bestSumSquaredErrors = sumSquaredErrors; bestSLRDeviationCalculator = slrCalculator;

}

}

return std: :make_pair(bestSLRDeviationCalculator,

bestSumSquaredErrors); }

void ProcessBestSplitter(TConstSLRIterator bestSLRDeviationCalculator, double sumGoals) {

size_t bestSplitterNumber = bestSLRDeviationCalculator -SLRDeviationCalculators.begin();

double factor, offset;

bestSLRDeviationCalculator->Solve(sumGoals, SumGoalProducts[bestSplitterNumber], factor, offset);

TConstSLRIterator slrCalculator = SLRDeviationCalculators.begin(); vector<double>::iterator sumGoalProducts = SumGoalProducts.begin();

vector<double>::const_iterator covariationMatrixElement = OLSMatrix.begin() + bestSplitterNumber;

for (; slrCalculator < bestSLRDeviationCalculator; ++slrCalculator, ++sumGoalProducts, covariationMatrixElement += FeaturesCount + 1) {

*sumGoalProducts -= factor * *covariationMatrixElement + offset slrCalculator->GetSumFeatures() ; )

for (; slrCalculator < SLRDeviationCalculators.end (); ++covariationMatrixElement, ++slrCalculator, ++sumGoalProducts) {

*sumGoalProducts -= factor * *covariationMatrixElement + offset

slrCalculator->GetSumFeatures(); }

}

};

M