среда, 8 октября 2014 г.

Обучение нейронной сети



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

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

Проектирование сети отслеживания переходов

Есть много разновидностей нейронных сетей, но все они состоят из множества узлов (нейронов) и связей между ними (синапсов). Мы собираемся построить MLP сеть (multilayer perceptron). Такая сеть состоит из нескольких уровней нейронов, первый из которых принимает входные данные – в данном случае поисковой запрос. Последний уровень возвращает результаты – список весов найденных URL.

Промежуточных уровней может быть много, но мы ограничимся только одним. Он называется скрытым уровнем, так как не взаимодействует напрямую с внешним миром, а реагирует на комбинации входных данных.
Общий принцип таков, значения входных узлов для указанных в запросе слов устанавливают равными 1. Включаются выходы этих узлов, и они пытаются активировать скрытый слой. В свою очередь, узлы скрытого слоя, получающие достаточно сильный входной сигнал, включают свои выходы и пытаются активировать узлы выходного уровня.  Узлы выходного уровня оказываются активны в разной степени, и по уровню их активности можно судить, как сильно данный URL ассоциирован со словами исходного запроса.  Разумеется, для этого необходимо, чтобы сила связей была установлена правильно. Это достигается обучением сети всякий раз, как кто-то выполняет поиск и выбирает один из результатов.
Уровни в БД:      word_list             word_hidden             hidden_node           hidden_urls                url_list                          .                                                                           
Как пример,  в сети, изображенной на рисунке выше, сколько-то человек переходили на сайт Всемирного банка (World Bank) после запроса world bank, и это усилило ассоциацию между данными словами и URL. Сплошными линиями показаны сильные связи, а полужирный текст говорит о том, что узел стал очень активным.
Мы будем обучать сеть с помощью алгоритма обратного распространения backpropagation.  

Прошу обратить внимание на подпись под картинкой. Каждый уровень (прямоугольничек или стрелочка) имеет свое отображение в БД. Я подписал названия таблиц им соответствующих, для большего понимания, что мы будем делать, но если сейчас Вам что-то не очень понятно, вернитесь к прочтению данного принципа, после описания механизма работы и все встанет на свои места!)

Подготовка базы данных

У тех, кто осилил прошлую статью, уже есть 2 таблицы - это word_list и url_list, где хранятся списки слов и урлов, соответственно. Теперь нужно еще 3: 1 - hidden_node (скрытый слой) и 2 таблицы связи с ним (одна hidden_word – для связей между слоем слов и скрытым слоем, другая hidden_url – для связей между скрытым и выходным слоем).

Нам потребуется два метода для доступа к базе данных. Первый, get_strength, определяет текущую силу связи. Поскольку новые связи создаются только по мере необходимости, этот метод должен возвращать некое специальное значение, если связей еще нет. Для связей между словами и скрытым слоем мы выберем в качестве такого значения –0,2, так что по умолчанию дополнительные слова будут несколько снижать уровень активации скрытого узла. Для связей между скрытым слоем и URL метод по умолчанию будет возвращать значение 0.

 def get_strength(self, from_id, to_id, layer):

  if layer == 0: 
   table = 'word_hidden'
  else: 
   table = 'hidden_url'

  self.cur.execute('select strength from %s where from_id = %d and to_id = %d' % (table, from_id, to_id))
                res = self.cur.fetchone()

  if res == None: 
   if layer == 0: 
    return -0.2

   if layer == 1: 
    return 0
    
  return res[0]

Еще необходим метод set_strength, который выясняет, существует ли уже связь, и создает либо обновляет связь, приписывая ей заданную силу. Он будет использоваться в коде для обучения сети:
 def set_strength(self, from_id, to_id, table, strength):

  self.cur.execute('select id from %s where from_id = %d and to_id = %d' % (table, from_id, to_id))
  res = self.cur.fetchone()

  if res == None: 
   self.cur.execute('insert into %s (from_id, to_id, strength) values (%d, %d, %f)' % (table, from_id, to_id, strength))
  else:
   row_id = res[0]
   self.cur.execute('update %s set strength = %f where id = %d' % (table, strength, row_id))

  self.db_commit()
Можно было бы предварительно создать гигантскую сеть с тысячами узлов в скрытом слое и уже готовыми связями, но мы с Вами будем создавать скрытые узлы, когда в них возникает надобность.

Следующая функция создает новый скрытый узел всякий раз, как ей передается не встречавшаяся ранее комбинация слов. Затем она создает связи с весами по умолчанию (для url сила маленькая, т.к. сеть не обучена, пусть 0.1, а для слов в сумме = 1) между этими словами и скрытым узлом и между узлом запроса и URL, который этот запрос возвращает.

 def generate_hidden_node(self, word_ids, urls):

                # Для простоты ограничимся 2-х словными фразами
  if len(word_ids) > 3: 
   return None

  # Проверить, создавали ли мы уже узел для данного набора слов
  sorted_words = map(str, word_ids)
  sorted_words.sort()
  create_key = '_'.join(sorted_words)
  self.cur.execute("select count(id) from hidden_node where create_key = '%s'" % create_key)
  count_hidden_id = self.cur.fetchone()

  # Если нет, создадим сейчас
  if not count_hidden_id:
   self.cur.execute("insert into hidden_node (create_key) values ('%s')  returning hidden_node.id" % create_key)
   hidden_id = self.cur.fetchone()[0]

   # Задать веса по умолчанию
   for word_id in word_ids:
    self.set_strength(word_id, hidden_id, 'word_hidden', 1.0/len(word_ids))

   for url_id in urls:
    self.set_strength(hidden_id, url_id, 'hidden_url', 0.1)

   self.db_commit()

Прямой проход

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

Для начала выберем функцию, которая описывает, с какой силой каждый узел должен реагировать на входной сигнал. В нашем примере сети мы воспользуемся для этого функцией гиперболического тангенса (tanh), график которой изображен ниже.
Функция tanh
По оси X откладывается входной сигнал, подаваемый узлу. В окрестности 0 выходной сигнал быстро нарастает. Когда сила входного сигнала равна 2, выходной сигнал почти равен 1 и дальше уже почти не растет. Функции такого типа называются сигмоидными, они имеют форму буквы S. Для вычисления силы выходного сигнала нейронов в нейронных сетях почти всегда используются сигмоидные функции.

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

 def get_all_hidden_ids(self, word_ids, url_ids):

  l1 = {}
  for word_id in word_ids:

   self.cur.execute('select to_id from word_hidden where from_id = %d' % word_id)
   cur = self.cur.fetchall()

   for row in cur:
    l1[row[0]] = 1

  for url_id in url_ids:

   cur = self.cur.execute('select from_id from hidden_url where to_id = %d' % url_id)
   cur = self.cur.fetchall()
   
   for row in cur:

    l1[row[0]] = 1

  return l1.keys()
Нам также понадобится метод для конструирования релевантной сети с текущими весами из базы данных. Эта функция инициализирует различные переменные экземпляра класса: список слов, относящиеся к запросу узлы и URL, уровень выходного сигнала для каждого узла и веса всех связей между узлами. Веса считываются из базы данных с помощью ранее разработанных функций.

 def setup_network(self, word_ids, url_ids):

  # списки значений
  self.word_ids = word_ids
  self.hidden_ids = self.get_all_hidden_ids(word_ids, url_ids)
  self.url_ids = url_ids

  # выходные сигналы узлов
  self.hidden_word_output = [1.0]*len(self.word_ids)
  self.hidden_layer_output = [1.0]*len(self.hidden_ids)
  self.hidden_url_output = [1.0]*len(self.url_ids)

  # создаем матрицу весов
  self.word_layer_weights = [
     [self.get_strength(word_id, hidden_id, 0) for hidden_id in self.hidden_ids] for word_id in self.word_ids
       ]

  self.layer_url_weights = [
     [self.get_strength(hidden_id, url_id, 1) for url_id in self.url_ids] for hidden_id in self.hidden_ids
     ]
Вот теперь все готово для реализации алгоритма feedforward. Он принимает список входных сигналов, пропускает их через сеть и возвращает выходные сигналы от всех узлов на выходном уровне. Поскольку в данном случае мы сконструировали сеть только для слов, входящих в запрос, то выходной сигнал от всех входных узлов равен 1:

 def feed_forward(self):

  # единственные входные сигналы – слова из запроса
  for i in xrange(len(self.word_ids)):
   self.hidden_word_output[i] = 1.0

  # возбуждение скрытых узлов
  for j in xrange(len(self.hidden_ids)):
   sum = 0.0
   for i in xrange(len(self.word_ids)):
    sum = sum + self.hidden_word_output[i] * self.word_layer_weights[i][j]
   self.hidden_layer_output[j] = tanh(sum)

  # возбуждение выходных узлов
  for k in xrange(len(self.url_ids)):
   sum = 0.0
   for j in range(len(self.hidden_ids)):
    sum = sum + self.hidden_layer_output[j] * self.layer_url_weights[j][k]
   self.hidden_url_output[k] = tanh(sum)

  return self.hidden_url_output[:]
Алгоритм feedforward в цикле обходит все узлы скрытого слоя и для каждого из них вычисляет сумму величин выходных сигналов от узлов входного слоя, помноженных на вес соответствующей связи. Выходной сигнал каждого скрытого узла – это результат применения функции tanh к взвешенной сумме входных сигналов. Этот сигнал передается на выходной уровень. Выходной уровень делает то же самое – умножает полученные от предыдущего уровня сигналы на веса связей и применяет функцию tanh для получения окончательного результата. Сеть можно легко обобщить, введя дополнительные уровни, которые будут преобразовывать выходные сигналы от предыдущего уровня во входные сигналы следующему.

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

 def get_result(self, word_ids, url_ids):

  self.setup_network(word_ids, url_ids)
  return self.feed_forward()


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


Обучение с обратным распространением

А вот теперь начинаются самое интересное. Сеть принимает вход- ные сигналы и генерирует выходные, но, поскольку ее не научили, какой результат считать хорошим, выдаваемые ею ответы практически бесполезны. Сейчас мы это исправим!)

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

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

Чтобы определить, насколько следует изменить суммарный входной сигнал, алгоритм обучения должен знать наклон функции tanh для текущего уровня выходного сигнала. В средней точке графика, когда выходной сигнал равен 0, функция изменяется очень круто, поэтому небольшое изменение входного сигнала приводит к большому изменению выходного. По мере того как уровень выходного сигнала приближается к –1 или к 1, изменение входного сигнала меньше сказывается на выходном. Наклон нашей функции для любого значения выходного сигнала вычисляется с помощью следующей функции:

def dtanh(y):
 return 1.0 - y*y

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

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

 def back_propagate(self, targets, N=0.5):

  # вычислить поправки для выходного слоя
  output_deltas = [0.0] * len(self.urlids)
  for k in xrange(len(self.urlids)):
   error = targets[k] - self.hidden_url_output[k]
   output_deltas[k] = dtanh(self.hidden_url_output[k]) * error

  # вычислить поправки для скрытого слоя
  hidden_deltas = [0.0] * len(self.hiddenids)
  for j in xrange(len(self.hiddenids)):
   error = 0.0
   for k in xrange(len(self.urlids)):
    error = error + output_deltas[k]*self.layer_url_weights[j][k]
   hidden_deltas[j] = dtanh(self.hidden_layer_output[j]) * error

  # обновить веса связеи между узлами скрытого и выходного слоя
  for j in xrange(len(self.hiddenids)):
   for k in xrange(len(self.urlids)):
    change = output_deltas[k]*self.hidden_layer_output[j]
    self.layer_url_weights[j][k] = self.layer_url_weights[j][k] + N*change

  # обновить веса связей между узлами входного и скрытого слоя
  for i in xrange(len(self.wordids)):
   for j in xrange(len(self.hiddenids)):
    change = hidden_deltas[j]*self.hidden_word_output[i]
    self.word_layer_weights[i][j] = self.word_layer_weights[i][j] + N*change


Осталось только написать простой метод, который подготовит сеть, вызовет алгоритм feed_forward и запустит обратное распространение. Этот метод принимает в качестве параметров списки word_ids, url_ids и выбранный URL:

 def train_query(self, word_ids, url_ids, selected_url_id): 

  # сгенерировать скрытыи узел, если необходимо
  self.generate_hidden_node(word_ids, url_ids)

  self.setup_network(word_ids, url_ids)      
  self.feed_forward()
  targets = [0.0]*len(urlids)
  targets[urlids.index(selected_url_id)] = 1.0
  error = self.back_propagate(targets)
  self.update_database()

Для сохранения результатов понадобится метод записи в базу данных новых весов, которые хранятся в переменных экземпляра word_layer_weights и layer_url_weights:


 def update_database(self):
  
  for i in xrange(len(self.word_ids)):
   for j in xrange(len(self.hidden_ids)):
    self.set_strength(self.word_ids[i], self. hidden_ids[j], 0, self.word_layer_weights[i][j])

  for j in xrange(len(self.hidden_ids)):
   for k in xrange(len(self.url_ids)):
    self.set_strength(self.hidden_ids[j], self.url_ids[k], 1, self.layer_url_weights[j][k])

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

Подключение к поисковой машине

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

def neiron_net_score(self, rows, word_ids):

  # Get unique URL IDs as an ordered list
  url_ids = [row[0] for row in rows]

  nn_res = self.neiron_net.get_result(word_ids, url_ids)
  scores = {url_ids[i]: nn_res[i] for i in xrange(len(url_ids))}
  return self.normalize_scores(scores)


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

Мы не уделяли внимание вопросам производительности, но безусловно - это очень острый вопрос в таких системах. Тут я полностью доверяю Вам!)