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);


 

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

44930. Основные этапы складывания древнерусского государства 20.74 KB
  Основные этапы складывания древнерусского государства В своем развитии древнерусское государство прошло ряд этапов. На первом этапе образования древнерусского государства VIIIсередина IХ вв. процесс складывания государства ускоряется во многом благодаря активному вмешательству внешних сил хазар и норманнов варягов. Норманнская теория происхождения древнерусского государства.
44932. Australia. Австралия 15.29 KB
  Australia is one of the most unusual and exotic countries of the world. A significant feature of modern Australian society is the representation of a lot of cultures drawn from many lands by its people
44933. Два способа установки ПО 22.78 KB
  В первом случае пакет ПО обычно поставляется в виде trgz архива во втором случае в виде rpm пакета но это не обязательно исполняемые модули также могут распространяться в виде trgz архива. Проще всего установить ПО представленное в виде rpm пакета содержащего исполняемые файлы. Программа rpm Название этой программы или команды является аббревиатурой от Redht Pckge Mnger. Программа rpm в некотором смысле аналогична программам типа setup wizrd для MS Windows.
44934. Влади́мир Андре́евич Фаво́рский 38.9 KB
  Фаворский вспоминает: Там я встретил целый ряд русских между прочим Истомина. Фаворский вспоминает: Бегали ещё в университет слушать профессоров Фуртвенглера и Фолля и к Молье слушать его лекции по анатомии Студенты Академии протестовали против нашего присутствия и выгоняли нас Молье услыша об этом возмутился и сказал что всякий кому интересно может слушать и мы слушали. Фаворский хорошо знал немецкий язык в отдельных случаях он даже исполнял роль переводчика на занятиях.
44935. Предмет и задачи методики преподавания РЯ 13.34 KB
  Методика РЯ опирается на лингвистические и психологические концепции о роли языка в социальном развитии о связи языка и сознания речи и мышления. Методика обеспечивает такую систему обучения языку которая строго соответствует современной теории лингвистики о сущности языка и его социальной функции быть важнейшим средством человеческого общения средством формирования мысли и ее выражения в языковом коде. Для решения своих задач методика выбирает оптимальные варианты в рамках классноурочной системы жестко ограниченного числа уроков и...
44936. Имя существительное 14.24 KB
  Род существительное не словоизменительная категория. Существительное относится к одному из трех родов. Род сущ. Или по значению выделяется корпус слов: плакса обжора умника род опред.