77216

Применение нейронных сетей к ранжированию результатов информационного поиска

Курсовая

Информатика, кибернетика и программирование

Существует ряд алгоритмов машинного обучения, которые позволяют определять ранг документов. Например, RankProp, PRank и RankBoost. Данные адаптивные алгоритмы тренируются на обучающей выборке документов, чтобы выявить зависимости положения документа от его признаков.

Русский

2015-02-02

282 KB

7 чел.

Санкт-Петербургский Государственный Университет

Математико-механический факультет

Кафедра системного программирования

Применение нейронных сетей к ранжированию результатов информационного поиска

Курсовая работа студента 445 группы
Петрова Александра Георгиевича

Научный руководитель      Вахитов А.Т

Санкт-Петербург

2009

Содержание

[1] Содержание

[1.1] Введение

[1.2]
Обзор алгоритмов ранжирования

[1.3] Постановка задачи

[1.4] Теоретическая основа курсовой работы

[1.5] Реализация

[1.6] Результаты

[1.7] Заключение

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

[1.9] Приложение

Введение

В настоящее время Интернет развивается по пути максимальной персонализации общения с пользователем. Наряду с рекомендационными системами, стали появляться персонализированные поисковые системы. Компания Google запустила в 2009 году персонализированный поиск для всех зарегистрированных пользователей.

Использование двухсторонней связи «поисковая система-пользователь»

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

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


Обзор алгоритмов ранжирования

Существует ряд алгоритмов машинного обучения, которые позволяют определять ранг документов. Например, RankProp, PRank и RankBoost. Данные адаптивные алгоритмы тренируются на обучающей выборке документов, чтобы выявить зависимости положения документа от его признаков. Признаками документов могут выступать таки параметры, как PageRank или TF-IDF мера.

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

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

Постановка задачи

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

В рамках данной курсовой работы моя задача состояла в следующем:

  •  Обучение новым технологиям
    •  Получить навыки работы с Matlab
    •  Получить навыки работы с Matlab Neural Network Toolbox
  •  Изучение алгоритмов
    •  Алгоритмы обучения нейронной сети
    •  Алгоритмы информационного поиска с использованием нейронной сети
      •  RankNet
      •  LambdaRank
      •  LambdaRank с SPSA
  •  Реализация прототипа
    •  Создание модуля для ранжирования результатов поиска на Matlab

Теоретическая основа курсовой работы

Информационный поиск

Существует несколько метрик оценки качества информационного поиска. В своей курсовой работе, я использую метрику Normalized Discounted Cumulative Gain (NDCG).

 - релевантность j-го документа i-му поисковому запросу.

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

- количество документов, которое берется для подсчета NDCG.

Но NDCG нельзя использовать в качестве функции стоимости для обучения нейронной сети, потому что она не дифференцируема. Поэтому в [1] предлагается использовать вероятностную функцию стоимости – перекрестную энтропию.

- выход нейронной сети на i-м документе

Тогда частные производные будут иметь вид

Усредняя по всем документам для данного поискового запроса, получаем, что частная производная для i-го документа представляется в виде

- документы более релевантные, чем i-й.

- документы менее релевантные, чем i-й.

Архитектура нейронной сети

В работе используется двухслойная нейронная сеть с 245 входами и 1 выходом [1]. На первом слое расположено 10 узлов. На втором – 1. На каждом из слоев присутствуют сдвиги. В качестве функции активации используется сигмоид.

Выход нейронной сети считается по такому правилу:

-функция активации на i-1 слое

Алгоритм обучения нейронной сети

Для каждого запроса рассматривается множество документов, которое соответствует ему. Данные документы поочередно пропускаются через нейронную сеть и результаты запоминаются. Затем при помощи алгоритма обучения нейронной сети «Обратное распространение ошибки», происходит обучение нейронной сети. Обучение сети основывается на поиске минимума целевой функции – перекрестной энтропии. Минимум ищется при помощи метода градиентного спуска. Для обучения нейронной сети минимизировать следующие производные: , , ,

Визуализация процесса обучения нейронной сети при помощи Matlab Neural Network Toolbox.

Реализация

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

Для реализации был выбран пакет прикладных программ Matlab по ряду причин:

  •  Удобство написания математических функций
  •  Matlab Neural Network Toolbox 
  •  Экспорт в C++
  •  Возможность вызова программы из Java, .NET

Создание нейронной сети с таким спецефическим процессом обучения затруднило использование встроенных в пакет готовых решений нейронных сетей и потребовало полного описания архитектуры сети и реализации новой функций для пакета Matlab Neural Network Toolboxcrossentropyerror.m. Функция используется для обучения нейронной сети.

Для обучения нейронной сети требуется файл с обучающей выборкой. Признаки документов записываются по такому правилу:

<line> .=. <relevance> <feature>:<value> <feature>:<value> ... <feature>:<value> # <queryid>
<relevance> .=. <float>
<feature> .=.
<integer>
<value> .=. <float>
<queryid> .=. <integer>

Для описания документов используется 245 признаков. Если признак для документа равен нулю, то допускается его отсутствие в векторе признаков. Все признаки являются числами из интервала [0,1]. Значение релевантности документа берется из диапазона [0,4].

При создании нейронной сети веса и сдвиги брались произвольным образом из интервала [0,1]. Для обучения использовалась встроенная в пакет Neural Network Toolbox функция обучения –traingda.m. Данная функция адаптивным образом управляет коэффициентом обучения для градиентного спуска, что позволяет повысить точность и скорость обучения нейронной сети.  

При реализации курсовой работы использовались данные с конкурса Яндекс Интернет математика 2009.

В приложении приведен код описания нейронной сети на Matlab.

Результаты

Результатом курсовой работы является модуль ранжирования на языке Matlab.

Были проведены эксперименты с использованием данных конкурса Яндекс Интернет математика. Данные разбиты на два файла – обучающее множество (imat2009_learning.txt) и множество для оценки (imat2009_test.txt). Файл с обучающим множеством содержит 97 290 строк, которые соответствуют 9 124 запросам. Результаты следующие – усредненное значение NDCG по всем запросам равно 0,7273 (для запросов, которые участвовали при обучении). В среднем, каждому запросу соответствует 10 документов.

Оценка качества ранжирования для произвольных запросов

Кол-во запросов для обучения

4

9

12

NDCG10

0,3829

0,3613

0,3780

Шаг обучения

0,0001

0,001

0,01

NDGC10

0,3149

0,3498

0,3829

Заключение

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

В дальнейшем планируется пойти по пути улучшения качества алгоритма ранжирования. Существует два способа улучшения – использовать другую функцию стоимости (заместитель NDCG [2]) или оптимизровать напрямую NDCG при обучении нейронной сети [3]. Оптимизацией будет являться исполльзование адаптивного шага обучения нейронной сети.

Возможно ускорение процесса обучения нейронной сети за счет использования алгоритма РСА, предложенного О.Н Граничиным [4], для оценки минимума целевой функции при обучении нейронной сети. В [3] были проведены опыты с использование SPSA, и доказано уменьшение времени обучения сети при сохранении качества.

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

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

[1] C. Burges, T. Sheked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to rank using gradient descent. In Proceedings of ICML’05, Bonn, Germany, August 2005

[2] C. Burges, R. Ragno, and Q. Le. Learning to rank with non-smooth cost functions. In Proceedings of NIPS’06, 2006.

[3] On Using Simultaneous Perturbation Stochastic Approximation for Learning to Rank, and the Empirical Optimality of LambdaRank.

[4] Granichin O.N., Polyak B.T. Randomized Algorithms of an Estimation and Optimization Under Almost Arbitrary Noises . Nauka, Moscow, 2003.

Приложение

Описание нейронной сети на Matlab

function net=initnnetwork()

mynet = network;

mynet.numInputs = 245;

mynet.numLayers = 2;

%слои, в которых добавляются сдвиги

mynet.biasConnect = [1; 1];

 

%указываем для всех 245 входов, что они идут на первый слой

for i=1:245

   mynet.inputConnect(1, i) = 1;

end

%указываем, что первый слой соединен со вторым (веча идет от первого ко второму)

mynet.layerConnect(2, 1) = 1;

%указываем, от какого слоя идет выход

mynet.outputConnect = [1 1];

 

%количество узлов в первом слое

mynet.layers{1}.size = 10;

 

mynet.initFcn = 'initlay';

%финукции инициализации определяются собственными фнкциями весов и сдвигов

mynet.layers{1}.initFcn = 'initwb';

mynet.layers{2}.initFcn = 'initwb';

 

%функция от выходов i-го слоя -  сигмоид

mynet.layers{1}.transferFcn = 'logsig';

mynet.layers{2}.transferFcn = 'logsig';

 

%инициализируем и настраиваем весы от входов к первому слою

rands(0,1);

for i=1:245

  %инициализируем веса нулями

  mynet.inputWeights{1,i}.initFcn = 'rands';

end

%настройка сдвига в первом слое

rands(1,1);

mynet.biases{1}.initFcn = 'rands';

mynet.layerWeights{2,1}.initFcn = 'rands';

%инициализация сдвига на втором слое значениеми произвольно взятыми с равномерным распределением

mynet.biases{2}.initFcn = 'rands';

%batch training

mynet.trainFcn = 'traingda';

%тренируем пока не достигнем нуля

mynet.trainParam.epochs = 1000;

mynet.trainParam.min_grad = 0.01;

mynet.trainParam.lr = 0.01;

%функция стоимоисти - определена в crossentropyerror.m

mynet.performFcn = 'crossentropyerror';

net = init(mynet);


 

А также другие работы, которые могут Вас заинтересовать

22272. Сушарка розпилювальна дискова для зневоднення бульйону пташиного 1.95 MB
  Вологу з матеріалів можна видалити різними способами: механічним, фізико-хімічним та тепловим. При механічному способі вологу відтискують у пресах або центрифугах. Фізико-хімічний спосіб ґрунтується на застосуванні вологовідбірних засобів і використовується переважно в лабораторній практиці.
22273. ОСТРЫЕ ПНЕВМОНИИ 37.5 KB
  Локализация: Паренхиматозная пневмония воспалительный экссудат в альвеолах Бронхопневмония экссудат в бронхах и альвеолах Межуточная пневмония клеточный инфильтрат в строме легкого. Вид экссудата: Серозная пневмония Серознолейкоцитарная Гнойная Фибринозная крупозная Геморрагическая Серозногеморрагическая. КРУПОЗНАЯ ПНЕВМОНИЯ Определение. Крупозная пневмония острое инфекционноаллергическое заболевание с поражением целой доли легкого долевая пневмония фибринозным экссудатом в альвеолах паренхиматозная...
22274. ПАРЕНХИМАТОЗНЫЕ ДИСТРОФИИ (ПД) 27.5 KB
  Гиалиновокапельная дистрофия Определение: это тяжелая необратимая белковая паренхиматозная дистрофия при которой в цитоплазме появляются крупные капли похожие на гиалин. Гидропическая дистрофия Определение: это тяжелая необратимая белковая паренхиматозная дистрофия характеризующаяся появлением в клетке вакуолей наполненных жидкостью. При резко выраженной дистрофии клетки похожи на баллон это баллонноя дистрофия. Роговая дистрофия Определение: эта дистрофия характеризуется образованием большого количества рогового вещества в ороговевающем...
22275. Самодержавие и реформы в России во второй половине XIX, в начале XX века 284 KB
  Первые шаги к отмене крепостного права в России были сделаны императором Александром I в 1803 году изданием Указа о вольных хлебопашцах, в котором прописан юридический статус отпускаемых на волю крестьян.
22276. СМЕШАННЫЕ ДИСТРОФИИ (СД) 39 KB
  НАРУШЕНИЯ ОБМЕНА ХРОМОПРОТЕИДОВ Хромопротеиды или эндогенные пигменты делят на три группы гемоглобиногенные ферритин гемосидерин билирубин гематоидин гематины порфирин. Нарушения обмена гемоглобиногенныз пигментов В норме при распаде эритроцитов гемоглобин превращается в пигменты красящие вещества: ферритин гемосидерин билирубин При патологии изза усиленного гемолиза распад эритроцитов могут образовываться новые пигменты: гематоидин гематины порфирины. Среди нарушенного обмена...
22277. СТРОМАЛЬНО-СОСУДИСТЫЕ ДИСТРОФИИ 42.5 KB
  Мукоидное набухание Определение это нетяжелая обратимая дезогранизация соединительной ткани. В норме в соединительной ткани белки и гиалуроновая кислота находятся в связанном состоянии в виде белковополисахаридных комплексов. Это ведет к набуханию волокон соединительной ткани и набуханию основного вещества. Микро Набухает основное вещество и волокна соединительной ткани.
22278. ТУБЕРКУЛЕЗ. Первичный туберкулезный комплекс (ПТК) 35 KB
  Вызывает туберкулез микобактерия туберкулеза палочка Коха. Туберкулез подразделяют на первичный гематогенный и вторичный. Первичный туберкулез туберкулез у людей впервые инфицированных микобактерией характеризующийся возникновением первичного туберкулезного комплекса первичный аффект лимфангит лимфаденит.
22279. ТУБУЛОПАТИИ. Острая тубулопатия или острый некротический нефроз 36 KB
  Макро: почки увеличены набухшие отечные корковый слой бледносерый мозговой темнокрасный. Больные чаще всего погибают в первые две стадии от уремии но с помощью искусственной почки большинство больных можно спасти. ПИЕЛОНЕФРИТ Определение: пиелонефрит это воспалительное бактериальное заболевание с поражением лоханки пиелит и межуточной ткани почки. нисходящий гематогенный механизм возбудитель попадает в почки из первичного внепочечного очага воспаления ангина пневмония и т.
22280. ХРОНИЧЕСКИЕ НЕСПЕЦИФИЧЕСКИЕ ЗАБОЛЕВАНИЯ ЛЕГКИХ (ХНЗЛ) 41 KB
  Классификация ХНЗЛ В группу ХНЗЛ входят следующие болезни: Хронический бронхит Бронхоэктазы Хроническая пневмония Эмфизема легких Хронический абсцесс легкого Пневмосклероз Интерстициальные болезни легких ИБЛ. Выделяют 3 патогенетические механизма ХНЗЛ: Бронхитогенный механизм в основе хронический бронхит и его осложнения бронхоэктазы пневмосклероз эмфизема. Исходы и осложнения: бронхоэктаз Эмфизема Пневмосклероз. ЭМФИЗЕМА ЛЕГКИХ Определение: эмфизема это повышенное содержание воздуха в легких и увеличение их...