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

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

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

 

Чтобы получить от нейронной сети наилучшие результаты для некоторого запроса, значения входных узлов для указанных в запросе слов устанавливают равными 1. Включаются выходы этих узлов, и они пытаются активировать скрытый слой. В свою очередь, узлы скрытого слоя, получающие достаточно сильный входной сигнал, включают свои выходы и пытаются активировать узлы выходного уровня. Узлы выходного уровня оказываются активны в разной степени, и по уровню их активности можно судить, как сильно данный URL ассоциирован со словами исходного запроса. На рис. 4.5 показана обработка запроса world bank (Всемирный банк). Сплошными линиями показаны сильные связи, а полужирный текст говорит о том, что узел стал очень активным.

Рис. 4.5. Ответ нейронной сети на запрос world bank

Разумеется, для этого необходимо, чтобы сила связей была установлена правильно. Это достигается обучением сети всякий раз, как кто-то выполняет поиск и выбирает один из результатов. В сети, изображенной на рис. 4.5, сколько-то человек переходили на сайт Всемирного банка (World Bank) после запроса world bank, и это усилило ассоциацию между данными словами и URL. В этом разделе мы покажем, как сеть обучается с помощью алгоритма обратного распространения backpropagation.

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

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

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

таблица для хранения скрытого слоя (которую мы назовем hiddennode) и две таблицы для хранения связей (одна – для связей между слоем слов и скрытым слоем, другая – для связей между скрытым и выходным слоем).

Создайте новый файл nn.py и в нем класс searchnet:

from math import tanh

from pysqlite2 import dbapi2 as sqlite

class searchnet:

def ___ init    (self,dbname):

self.con=sqlite.connect(dbname)

def __del__(self): self.con.close( )

def maketables(self):

self.con.execute(‘create table hiddennode(create_key)’) self.con.execute(‘create table wordhidden(fromid,toid,strength)’) self.con.execute(‘create table hiddenurl(fromid,toid,strength)’) self.con.commit( )

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

Нам потребуется два метода для доступа к базе данных. Первый, getstrength, определяет текущую силу связи. Поскольку новые связи создаются только по мере необходимости, этот метод должен возвращать некое специальное значение, если связей еще нет. Для связей между словами и скрытым слоем мы выберем в качестве такого значения -0,2, так что по умолчанию дополнительные слова будут несколько снижать уровень активации скрытого узла. Для связей между скрытым слоем и URL метод по умолчанию будет возвращать значение 0. def getstrength(self,fromid,toid,layer): if layer==0: table=’wordhidden’ else: table=’hiddenurl’

res=self.con.execute(‘select strength from %s where fromid=%%d and toid=%%d’ % (table,fromid,toid)).fetchone( ) if res==None: if layer==0: return -0.2 if layer==1: return 0 return res[0]

Еще необходим метод setstrength, который выясняет, существует ли уже связь, и создает либо обновляет связь, приписывая ей заданную силу. Он будет использоваться в коде для обучения сети:

def setstrength(self,fromid,toid,layer,strength): if layer==0: table=’wordhidden’ else: table=’hiddenurl’

res=self.con.execute(‘select rowid from %s where fromid=%%d and toid=%%d’ % (table,fromid,toid)).fetchone( )

if res==None:

self.con.execute(‘insert into %s (fromid,toid,strength) values (%d,%d,%f)’ %% (table,fromid,toid,strength)) else:

rowid=res[0]

self.con.execute(‘update %s set strength=%%f where rowid=%d’ % (table,strength,rowid))

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

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

def generatehiddennode(self,wordids,urls): if len(wordids)>3: return None

#       Проверить, создавали ли мы уже узел для данного набора слов createkey=’_’.join(sorted([str(wi) for wi in wordids])) res=self.con.execute(

"select rowid from hiddennode where create_key=’%s’" % createkey). fetchone( )

#       Если нет, создадим сейчас if res==None:

cur=self.con.execute(

"insert into hiddennode (create_key) values (‘%s’)" % createkey) hiddenid=cur.lastrowid # Задать веса по умолчанию for wordid in wordids:

self.setstrength(wordid,hiddenid,0,1.0/len(wordids)) for urlid in urls:

self.setstrength(hiddenid,urlid,1,0.1) self.con.commit( )

В интерпретаторе Python создайте базу данных и сгенерируйте скрытый узел для какого-нибудь слова и идентификатора URL: >> import nn

>> mynet=nn.searchnet(‘nn.db’) >> mynet.maketables( ) >> wWorld,wRiver,wBank =101,102,103 >> uWorldBank,uRiver,uEarth =201,202,203

>> mynet.generatehiddennode([wWorld,wBank],[uWorldBank,uRiver,uEarth]) >> for c in mynet.con.execute(‘select * from wordhidden’): print c

(101, 1, 0.5) (103, 1, 0.5)

>> for c in mynet.con.execute(‘select * from hiddenurl’): print c

(1, 201, 0.1) (1, 202, 0.1)

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

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

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

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

Рис. 4.6. Функция tanh

По оси X откладывается входной сигнал, подаваемый узлу. В окрестности 0 выходной сигнал быстро нарастает. Когда сила входного сигнала равна 2, выходной сигнал почти равен 1 и дальше уже почти не растет. Функции такого типа называются сигмоидными, они имеют форму буквы S. Для вычисления силы выходного сигнала нейронов в нейронных сетях почти всегда используются сигмоидные функции. Прежде чем вызывать алгоритм feedforward, наш класс должен прочитать из базы информацию об узлах и связях и построить в памяти часть сети, релевантную конкретному запросу. Первым делом мы напишем функцию, которая ищет все узлы из скрытого слоя, релевантные запросу; в нашем случае это узлы, связанные с любым из слов запроса или с каким-нибудь URL, принадлежащим множеству результатов поиска. Так как никакие другие узлы не участвуют в определении выхода или в обучении сети, то и включать их необязательно. def getallhiddenids(self,wordids,urlids):

l1={}

for wordid in wordids:

cur=self.con.execute(

‘select toid from wordhidden where fromid=%%d’ % wordid) for row in cur: l1[row[0]]=1 for urlid in urlids: cur=self.con.execute(

‘select fromid from hiddenurl where toid=%%d’ % urlid) for row in cur: l1[row[0]]=1 return l1.keys( )

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

#       списки значений self.wordids=wordids

self.hiddenids=self.getallhiddenids(wordids,urlids) self.urlids=urlids

#       выходные сигналы узлов self.ai = [1.0]*len(self.wordids) self.ah = [1.0]*len(self.hiddenids) self.ao = [1.0]*len(self.urlids)

#       создаем матрицу весов

self.wi = [[self.getstrength(wordid,hiddenid,0) for hiddenid in self.hiddenids] for wordid in self.wordids] self.wo = [[self.getstrength(hiddenid,urlid,1) for urlid in self.urlids] for hiddenid in self.hiddenids]

Вот теперь все готово для реализации алгоритма feedforward. Он принимает список входных сигналов, пропускает их через сеть и возвращает выходные сигналы от всех узлов на выходном уровне. Поскольку в данном случае мы сконструировали сеть только для слов, входящих в запрос, то выходной сигнал от всех входных узлов равен 1:

def feedforward(self):

#       единственные входные сигналы – слова из запроса for i in range(len(self.wordids)):

self.ai[i] = 1.0

#       возбуждение скрытых узлов

for j in range(len(self.hiddenids)): sum = 0.0

for i in range(len(self.wordids)):

sum = sum + self.ai[i] * self.wi[i][j] self.ah[j] = tanh(sum)

#       возбуждение выходных узлов

for k in range(len(self.urlids)):

sum = 0.0

for j in range(len(self.hiddenids)):

sum = sum + self.ah[j] * self.wo[j][k] self.ao[k] = tanh(sum)

return self.ao[:]

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

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

def getresult(self,wordids,urlids): self.setupnetwork(wordids,urlids) return self.feedforward( )

Протестируем эту сеть:

>> reload(nn)

>> mynet=nn.searchnet(‘nn.db’)

>> mynet.getresult([wWorld,wBank],[uWorldBank,uRiver,uEarth])

[0.76,0.76,0.76]

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

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

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

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

Чтобы определить, насколько следует изменить суммарный входной сигнал, алгоритм обучения должен знать наклон функции tanh для текущего уровня выходного сигнала. В средней точке графика, когда выходной сигнал равен 0,0, функция изменяется очень круто, поэтому небольшое изменение входного сигнала приводит к большому изменению выходного. По мере того как уровень выходного сигнала приближается к -1 или к 1, изменение входного сигнала меньше сказывается на выходном. Наклон нашей функции для любого значения выходного сигнала вычисляется с помощью следующей функции, которую нужно добавить в начало файла nn.py: def dtanh(y): return 1.0-y*y

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

1.         Вычислить разность между текущим и желательным уровнем выходного сигнала.

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

3.         Изменить вес каждой входящей связи пропорционально ее текущему весу и скорости обучения.

Для каждого узла в скрытом слое необходимо:

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

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

3.         Изменить вес каждой входящей связи пропорционально ее текущему весу и скорости обучения.

При реализации этого алгоритма мы вычисляем все поправки заранее, а затем подстраиваем веса, поскольку все расчеты основываются на знании текущих, а не измененных весов. Ниже приведен код: def backPropagate(self, targets, N=0.5): # вычислить поправки для выходного слоя output_deltas = [0.0] * len(self.urlids) for k in range(len(self.urlids)): error = targets[k]-self.ao[k] output_deltas[k] = dtanh(self.ao[k]) * error

#       вычислить поправки для скрытого слоя hidden_deltas = [0.0] * len(self.hiddenids) for j in range(len(self.hiddenids)):

error = 0.0

for k in range(len(self.urlids)):

error = error + output_deltas[k]*self.wo[j][k] hidden_deltas[j] = dtanh(self.ah[j]) * error

#       обновить веса связей между узлами скрытого и выходного слоя for j in range(len(self.hiddenids)):

for k in range(len(self.urlids)): change = output_deltas[k]*self.ah[j] self.wo[j][k] = self.wo[j][k] + N*change

#       обновить веса связей между узлами входного и скрытого слоя for i in range(len(self.wordids)):

for j in range(len(self.hiddenids)): change = hidden_deltas[j]*self.ai[i] self.wi[i][j] = self.wi[i][j] + N*change

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

def trainquery(self,wordids,urlids,selectedurl):

#       сгенерировать скрытый узел, если необходимо self.generatehiddennode(wordids,urlids)

self.setupnetwork(wordids,urlids) self.feedforward( ) targets=[0.0]*len(urlids) targets[urlids.index(selectedurl)]=1.0 error = self.backPropagate(targets) self.updatedatabase( )

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

def updatedatabase(self):

#       записать в базу данных

for i in range(len(self.wordids)): for j in range(len(self.hiddenids)): self.setstrength(self.wordids[i],self. hiddenids[]],0,self.wi[i][j]) for j in range(len(self.hiddenids)): for k in range(len(self.urlids)): self.setstrength(self.hiddenids[]],self.urlids[k],1,self.wo[]][k]) self.con.commit( )

Теперь можно прогнать простой тест, подав на вход тот же запрос, что и раньше, и посмотреть, как сеть отреагировала на обучение: >> reload(nn)

>> mynet=nn.searchnet(‘nn.db’)

>> mynet.trainquery([wWorld,wBank],[uWorldBank,uRiver,uEarth],uWorldBank) >> mynet.getresult([wWorld,wBank],[uWorldBank,uRiver,uEarth])

[0.335,0.055,0.055]

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

Проверка результатов обучения

Выше вы видели, как обучение на одном результате повышает уровень выходного сигнала для этого результата. Это хотя и полезно, но не показывает, на что в действительности способны нейронные сети, – как они могут делать выводы о входных данных, которых никогда прежде не видели. Введите следующие команды в интерактивном сеансе: >> allurls=[uWorldBank,uRiver,uEarth] >> for i in range(30):

… mynet.trainquery([wWorld,wBank],allurls,uWorldBank) … mynet.trainquery([wRiver,wBank],allurls,uRiver) … mynet.trainquery([wWorld],allurls,uEarth)

>> mynet.getresult([wWorld,wBank],allurls)

[0.861, 0.011, 0.016]

>> mynet.getresult([wRiver,wBank],allurls)

[-0.030, 0.883, 0.006] >> mynet.getresult([wBank],allurls)

[0.865, 0.001, -0.85]

Хотя сеть никогда раньше не видела запроса bank, она выдает правильную гипотезу. Более того, URL Всемирного банка получает гораздо более высокий ранг, чем URL River, хотя в обучающих примерах слово bank ассоциировалось со словом river так же часто, как с World Bank. Сеть не только поняла, какие URL с какими запросами ассоциируются, но и обучилась тому, какие слова важны в конкретном запросе. Достичь этого путем простого запоминания пары запрос-URL было бы невозможно.

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

Метод query класса searcher получает списки идентификаторов URL и идентификаторов слов в процессе создания и распечатки результатов. Можно заставить метод возвращать эти результаты, добавив в конец такую строку (файл searchengine.py):

return wordids,[r[1] for r in rankedscores[0:10]] Эти списки можно напрямую передать методу trainquery из класса searchnet.

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

Последний шаг при создании искусственной нейронной сети – это создание в классе searcher еще одного метода, который будет взвешивать результаты. Соответствующая функция похожа на все остальные весовые функции. Прежде всего следует импортировать класс нейронной сети в файл searchengine.py: import nn

mynet=nn.searchnet(‘nn.db’)

Затем добавьте в класс searcher такой метод:

def nnscore(self,rows,wordids): # Получить уникальные идентификаторы URL в виде упорядоченного списка urlids=[urlid for urlid in set([row[0] for row in rows])] nnres=mynet.getresult(wordids,urlids)

scores=dict([(urlids[i],nnres[i]) for i in range(len(urlids))]) return self.normalizescores(scores)

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

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100