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


 

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

57737. Дії над раціональними числами 99 KB
  Мета. Закріпити в учнів навички виконання дій над раціональними числами, обчислення значень виразів, що містять раціональні числа; розвивати позитивні риси особистості...
57738. Розв’язування систем рівнянь з параметрами 1.32 MB
  Розвивальна мета: розвивати логічне мислення творчі здібності формувати вміння міркувати висловлювати думку. Формувати соціальну компетентність: давати учням змогу вибору варіантів завдань та шляхів розв’язку задач.
57739. Дж. Байрон. Поема «Мазепа». Історична основа та романтичний міф 112 KB
  Очікувані результати: учень переказує зміст поеми Мазепа визначає її історичну основу розгром шведів російськими військами втеча Мазепи з почтом Карла ХІІ та переповідає романтичний міф про прив’язаного до коня молодого Мазепу...
57740. Генетична термінологія і символіка. Методи генетичних досліджень. Закони Г. Менделя 66.5 KB
  МЕТА: сформувати поняття про генетику як науку що вивчає спадковість і мінливість організмів; почати формувати знання про основні генетичні закономірності успадкування ознак; розкрити основні генетичні поняття...
57741. Що таке милосердя 162.5 KB
  Мета уроку: розкрити зміст понять милосердя співчуття благодійність; навчити наводити приклади милосердя у вчинках; розвивати в учнях здібність робити самоаналіз своїх вчинків; формувати власне ставлення...
57742. Узагальнення та систематизація знань з теми «Многочлен» 350.5 KB
  МЕТА: Організувати діяльність учнів по узагальненню і систематизації знань і умінь учнів з теми Многочлен домогтися засвоєння учнями математичних понять сприяти формуванню специфічних вмінь і навичок з даної теми...
57743. Арифметичні дії з многочленами. Розв’язування вправ 1.23 MB
  Мета уроку: актуалізувати знання учнів необхідні для сприйняття нового матеріалу підвести поняття алгоритму додавання і віднімання многочленів множення одночлена на многочлен та многочленна на многочлен...
57745. Многогранники навколо нас 598 KB
  Діапазон застосувань геометрії у різних сферах діяльності людини дуже широкий тому на даному занятті студенти розглядають многогранники з математичної точки зору означення властивості моделі п’яти правильних многогранників...