77216

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

Курсовая

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

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

Русский

2015-02-02

282 KB

6 чел.

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

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

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

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

Курсовая работа студента 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);


 

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

27466. Демократический политический режим 24.5 KB
  Государственнополитический режим это элемент формы государства характеризующий совокупность приемов методов способов и средств осуществления государственной власти. Основными признаками демократического режима являются: господство закона; разделение властей; наличие у граждан реальных политических и социальных прав и свобод и их юридическая защищенность и гарантированность; выборность и сменяемость центральных и местных органов государственной власти их подотчетность перед избирателями гласность; наличие свободно формируемых...
27467. Законность, понятие и характеристика 25.5 KB
  Понятие законности неотделимо от понятия права. В результате реализации этого требования органами государства и его должностными лицами возникает особый режим система общественных отношений – режим законности. Законность как принцип – одно из руководящих системообразующих начал построения и деятельности правового государства выражающееся в системе принципов и требований отражающих идею законности. Режим законности – такое состояние общественных отношений когда во взаимоотношениях между государственной властью и населением господствует...
27468. Законотворчество в РФ 31.5 KB
  104 Конституции РФ принадлежит Президенту РФ Совету Федерации членам Совета Федерации депутатам Государственной Думы Правительству РФ законодательным представительным органам субъектов Федерации. 50 1 голос; федеральные же конституционные законы считаются принятыми если за них проголосовало не менее 2 3 голосов от общего числа депутатов Государственной Думы; б одобрение закона Советом Федерации в соответствии с ч. 105 Конституции РФ федеральный закон считается одобренным Советом Федерации если за него проголосовало более...
27469. К каким источникам права относятся, либо с ними связаны: договор купли-продажи, договор найма жилого помещения, союзный договор между суверенными республиками 25 KB
  К каким источникам права относятся либо с ними связаны: договор куплипродажи договор найма жилого помещения союзный договор между суверенными республиками. Виды источников: правовой обычай правовой прецедент правовая доктрина договоры нормативного содержания нормативный правовой акт. Договор куплипродажи и договор найма жилого помещения – типовые договоры. Типовой договор стандартная типовая отпечатанная типографским способом форма договора со стандартными условиями и формулировками.
27470. К какому виду норм можно отнести ст.7 ГК РФ 40 KB
  Гражданское законодательство и нормы международного права 1. Общепризнанные принципы и нормы международного права и международные договоры РФ являются в соответствии с Конституцией РФ составной частью правовой системы РФ. Здесь присутствуют нормы: 1. исходные нормыначала 2.
27471. К какому виду норм относятся: правила дорожного движения; правила безопасной эксплуатации домашних бытовых приборов; правила, регламентирующие порядок проведения митингов и демонстраций 30.5 KB
  1 Правила дорожного движения – общие императивные запрещающие нормы. Общие нормы – это предписания охватывающие своим действием как правило все правовые институты той или иной отрасли. Императивные нормы – категорические строго обязательные не допускающие отступлений и иной трактовки предписания. Императивными являются большинство норм права относящихся к различным его отраслям а исходные юридические нормы будут таковыми всегда.
27472. К какому виду относятся правоотношения собственности (обще-регулятивные, относительные, абсолютные, правильного ответа нет) 26 KB
  К какому виду относятся правоотношения собственности общерегулятивные относительные абсолютные правильного ответа нет Правовые отношения могут классифицироваться по различным основаниям: l в зависимости от предмета правового регулирования отраслевого признака они подразделяются на: конституционные административные уголовные гражданские и т.; ПС: материальные 3 в зависимости от функциональной роли на регулятивные возникают на основе норм права или договора и охранительныесвязаны с государственным принуждением и реализацией...
27473. К какому виду толкования норм права относятся Комментарии к законодательству, постановление Пленума Верховного Суда РФ по конкретному делу, распространенное на подобные дела в дальнейшем 34 KB
  Комментарии к законодательству – неофициальное доктринальное толкование. Постановление Пленума Верховного Суда РФ – официальное профессиональное нормативное толкование. Толкование деятельность соответствующих субъектов по уяснению и разъяснению смысла и содержания правовых норм а также результаты этой деятельности выраженные в интерпретационных актах актах толкования. 3 По субъекту – аутентическое и легальное а также толкование обыденное профессиональное и доктринальное.
27474. Перечислите и охарактеризуйте основные части правоприменительного акта 26.5 KB
  Перечислите и охарактеризуйте основные части правоприменительного акта. Акт применения права это такой правовой акт который содержит индивидуальное властное предписание вынесенное компетентным органом в результате решения конкретного юридического дела. Правоприменительный акт как итог правоприменительной деятельности характеризуется следующими особенностями: исходит от компетентных органов; носит государственновластный характер; носит индивидуальный персонифицированный а не нормативный характер поскольку адресован конкретным...