Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

PAGERANK 115
Тур
Страница 1 Страница 2 Страница 3 Страница 4 Страница 5 Страница 6
начало
0,17 0,17 0,17 0,17 0,17 0,17 1
0,08 0,22 0,14 0,00 0,42 0,14 2
0,00 0,25 0,25 0,00 0,29 0,21 3
0,00 0,22 0,22 0,00 0,33 0,22
Произошло следующее: несмотря на отсутствие висячих узлов, у нас все равно есть узлы, которые ведут себя в качестве слива для остального графа.
Если присмотреться, можно заметить, что у узлов 2, 3, 5 и 6, если их объеди- нить, есть только входные ссылки. Мы можем перейти в эту группу из узлов 1 или 4, но после этого перемещаться можно будет только внутри этой группы.
Мы не можем выйти за ее пределы. Наш блуждающий пользователь окажется в ловушке, которая представляет собой не одну, а сразу несколько страниц, ссылающихся только друг на друга.
1 2
3 4
5 6
Нам опять нужно помочь блуждающему пользователю выбраться из этой ловушки. На этот раз в матрицу гиперссылок придется внести более комплексные изменения. Наша исходная матрица позволяла пользователю переходить между страницами только с помощью ссылок, существующих в графе. Затем мы ее модифицировали, чтобы избежать появления строк, состоящих из одних нолей; так у нас получилась S-матрица, позволявшая при попадании в висячий узел переходить в любое место графа. Теперь мы еще немного поменяем поведение блуждающего пользователя, модифици- ровав S-матрицу.
Сейчас, когда пользователь оказывается на узле, его возможные переходы определяются S-матрицей. В последнем примере ввиду отсутствия нулевых строк S-матрица ничем не отличалась от матрицы гиперссылок:

116 ГЛАВА 5 0
1 2 0
0 1 2 0
0 0
1 2 0 1 2 0
0 1 2 0
0 0
1 2 1 2 0
0 0 1 2 0
0 1 3 1 3 0 0
1 3 0
0 0
0 1
0
/
/
/
/
/
/
/
/
/
/
/
⎡⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎥
⎥
⎥
⎥
Если блуждающий пользователь окажется на странице 5, то, как показы- вает S-матрица, он может перейти только на страницу 2, 3 или 6, и в каждом случае вероятность будет равна 1/3. Давайте сделаем его более проворным, чтобы он мог следовать S-матрице не всегда, а только с какой-то выбранной нами вероятностью a; таким образом шансы на то, что он перейдет в любую точку графа, без учета S-матрицы, равны (1 – a).
Способность переходить куда угодно откуда угодно означает, что в ма- трице никогда не может быть нулевых строк, ведь ноль обозначает переход, который невозможно выполнить. Чтобы этого достичь, нам придется увели-
чить значения нулевых записей и уменьшить значения ненулевых, чтобы вся строка всегда давала в сумме 1. Итоговые значения матрицы можно вычис- лить с помощью линейной алгебры, основываясь на S и вероятности a. Новая производная матрица называется матрицей Google; обозначим ее символом
G. Если она определяет поведение блуждающего пользователя, все зарабо- тает так, как мы того хотели: пользователь станет следовать S-матрице с ве- роятностью a и двигаться независимо с вероятностью (1 — a). В нашем при- мере матрица Google будет выглядеть так:
3 120 54 120 3
120 3
120 54 120 3
120 3
120 3
120 54 120 3
120 54 120 3
120 3
120 54 1120 3
120 3
120 3
120 54 120 54 120 3
120 3
120 54 120 3
120 3
120 3
120 37 120 37 1120 3
120 3
120 37 120 3
120 3
120 3
120 3
120 105 120 3
120
⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎤
⎦⎦
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
Сравните это с S-матрицей. Обратите внимание на то, что в первой строке две записи имели значения 1/2, а стальные были нулевыми. Теперь же

PAGERANK 117
в матрице Google две записи 1/2 превратились в 54/120, а остальные стали равны 3/120 вместо 0. Аналогичные преобразования произошли и в других строках. Теперь, если блуждающий пользователь окажется на странице 1, ве- роятность перехода на страницы 2 и 5 составит 54/120 в каждом из случаев, а вероятность перехода на любую другую страницу будет равна 3/120.
Теперь мы можем дать окончательное определение алгоритму PageRank.
1. Формируем из графа матрицу Google.
2. Начинаем с исходных оценок рейтингов, назначая каждой странице рейтинг 1/n, где n — общее количество страниц.
3. Применяем степенной метод, умножая рейтинговый вектор на матрицу
Google до тех пор, пока не сойдутся значения этого вектора.
Мы просто заменили «матрицу гиперссылок», которая была в исходном алгоритме, «матрицей Google». Если пройтись этим алгоритмом по нашему графу со «сливной» группой узлов, получится следующее:
Тур
Страница 1 Страница 2 Страница 3 Страница 4 Страница 5 Страница 6
начало 0,17 0,17 0,17 0,17 0,17 0,17 1
0,10 0,14 0,14 0,10 0,31 0,21 2
0,07 0,15 0,17 0,07 0,31 0,23 3
0,05 0,14 0,18 0,05 0,32 0,26 4
0,05 0,14 0,17 0,05 0,33 0,27
Все сработало как нужно; мы больше не получаем нулевых рейтингов.
Степенной метод в сочетании с матрицей Google работает всегда. Линей- ная алгебра говорит о том, что он всегда сходится на финальном наборе рей- тингов, сумма которых равна 1; на это не влияют ни висячие узлы, ни участки графа, которые высасывают рейтинги из остальных узлов. Нам даже не нужно делать начальные рейтинги равными 1/n. Для инициализации можно ис- пользовать любые значения, которые в сумме дают единицу.
PageRank на практике
Итак, мы выработали метод поиска рейтингов в любом графе. Вопрос в том, являются ли конечные результаты осмысленными.

118 ГЛАВА 5
Рейтинговый вектор (в том виде, в котором мы его определили) играет особую роль в отношении матрицы Google. Когда степенной метод заканчи- вает работу, этот вектор больше не меняется. Следовательно, умножив его на матрицу Google, мы просто получим тот же вектор. В линейной алгебре это называется первым собственным вектором матрицы Google. Если не углуб- ляться в математику, эта теория подтверждает, что этот вектор имеет особое значение для нашей матрицы.
Окончательным и важнейшим показателем того, что алгоритм PageRank подходит для назначения рейтингов веб-страницам, является то, насколько полезны его результаты людям. Поисковая система Google выдает хорошие результаты, то есть то, что мы, пользователи, получаем в ответ на наши за- просы, соответствует нашему представлению о важной информации. Если бы рейтинговый вектор был математической диковинкой, не имеющей отноше- ния к веб-страницам, он бы нас не заинтересовал.
Еще одно преимущество алгоритма PageRank в том, что его можно эф- фективно реализовать. Матрица Google имеет огромный размер; нам нужны одна строка и один столбец для каждой страницы в Интернете. Тем не менее матрица Google, как мы видели, является производной от S-матрицы, которая в свою очередь была получена из матрицы гиперссылок. Нам вовсе не нужно создавать и хранить саму матрицу Google; мы можем получить ее динами- чески, применяя матричные операции к матрице гиперссылок. Это удобно.
В отличие от матрицы Google, у которых нет нулевых записей, матрица ги- перссылок хранит множество нолей. Интернет может состоять из миллиар- дов страниц, но каждая из них ссылается лишь на горстку других ресурсов.
Матрица гиперссылок является разреженной, то есть она в основном состоит из нолей, с небольшим количеством ненулевых значений (которых на не- сколько порядков меньше, чем нулевых). Благодаря этому мы можем хра- нить нашу матрицу с применением ловких методик, позволяющих размещать в памяти не все сразу, а лишь те позиции, в которых находятся ненулевые зна- чения. Нам нужна не вся матрица гиперссылок, а только координаты нену- левых записей, занимающих намного меньше места. Это дает существенное преимущество при практическом применении алгоритма PageRank.
Но есть один важный нюанс. Нам известно, что этот алгоритм сыграл ключевую роль в успехе Google, но мы не знаем, в каком качестве он исполь- зуется сейчас и используется ли вообще. Поисковая система Google постоянно развивается, и проводимые изменения не являются публичными. Известно, что Google использует историю поисковых запросов для оптимизации после- дующих результатов. Оптимизация может зависеть от страны, в которой мы

проживаем, или от общих тенденций в поисковых запросах, выполняемых людьми со всего мира. Все эти ингредиенты составляют секретный рецепт, с помощью которого Google улучшает свой продукт и удерживает позицию на рынке поисковых систем. Тем не менее все это не умаляет эффективности
PageRank для назначения рейтингов веб-страницам, представленным в виде узлов графа.
PageRank подчеркивает еще один важный фактор успеха алгоритма. Это не только элегантность и эффективность, но и то, насколько он подходит для решения конкретной задачи. Это творческий аспект. Если мы хотим искать по Интернету, нам нужно преодолеть одну важную проблему — его огромный размер. Но если представить его в виде графа, размер из препятствия превра- тится в преимущество. Именно ввиду такого большого количества взаимо- связанных страниц можно ожидать, что для решения задачи подойдет метод, основанный на ссылочной структуре графа. Способность смоделировать за- дачу является первым шагом на пути к ее алгоритмическому решению.

120 ГЛАВА 6
ГЛАВА 6
ГЛУБОКОЕ ОБУЧЕНИЕ
В последние годы приобрели популярность системы глубокого обучения.
О них даже начали писать в средствах массовой информации. С их помощью компьютеры могут делать вещи, которые раньше считались прерогативой человека. Еще более неловким является тот факт, что эти системы часто пре- подносятся так, будто они работают подобно человеческому разуму. Это, ко- нечно, намек на то, что ключом к искусственному интеллекту может быть эмуляция того, как мыслят люди.
Но, если не обращать внимания на рекламные преувеличения, боль- шинство ученых, работающих в сфере глубокого обучения, не разделяют мнение о том, что эти системы похожи по своему принципу на разум чело- века. Их задача в том, чтобы продемонстрировать какое-то полезное пове- дение, которое зачастую ассоциируют с интеллектом. Однако мы не пыта- емся копировать природу; строение человеческого мозга слишком сложное для того, чтобы эмулировать его на компьютере. Но мы все же поглядываем на природу, сильно упрощаем наши наблюдения и пытаемся проектировать системы, которые в некоторых сферах могут заменять биологические орга- низмы, эволюционировавшие на протяжении миллионов лет. Более того, системы глубокого обучения можно рассматривать с точки зрения алгорит- мов, которые они используют, чем мы и займемся в этой главе. Это помо- жет получить некоторое представление о том, что именно и как они делают.
Благодаря этому мы сможем увидеть, что за их сложным поведением скры- ваются простые фундаментальные принципы. Вы убедитесь в том, что для извлечения из них какой-то пользы требуется недюжинная изобретатель- ность.
Чтобы понять, что такое глубокое обучение, нужно начать с менее мас- штабных и более скромных вещей. На их основе мы постепенно сформируем более развернутую картину. В конце этой главы вы будете знать, что такого
«глубокого» в этом обучении.

ГЛУБОКОЕ ОБУЧЕНИЕ 121
Нейроны, настоящие и искусственные
Нашей отправной точкой будет главная составляющая систем глубокого об- учения, позаимствованная из биологии. Мозг — это часть нервной системы, основными компонентами которой выступают клетки под названием ней-
роны. Нейронам присуща определенная форма; они не похожи на шарооб- разные структуры, которые обычно ассоциируют с клетками. Ниже пред- ставлено одно из первых изображений нейронов, нарисованное в 1899 году испанцем Сантьяго Рамоном-и-Кахалем, отцом современных нейронаук.
В центре изображения находятся два нейрона голубиного мозга. Как видите, нейрон состоит из тела клетки и отростков, которые из него исхо- дят. Эти отростки соединяются друг с другом с помощью синапсов, объеди- няя нейроны в сеть. Нейроны асимметричные. На одной стороне каждого из них расположено множество отростков, а на другой — всего один. Сторону с большим количеством отростков можно считать вводом нейрона, а проти- воположную сторону — его выводом. Ввод имеет вид электрических сигналов,

122 ГЛАВА 6
поступающих по входным отросткам. Многие нейроны могут также отправ- лять сигналы. Чем больший ввод принимает нейрон, тем большая вероят- ность того, что он пошлет (сгенерирует) сигнал. В этом случае говорят, что нейрон активируется.
Человеческий мозг — это огромная сеть нейронов, которых насчитыва- ется порядка ста миллиардов, и каждый из них соединен в среднем с тысячей других. У нас нет возможности создать ничего подобного, но мы можем стро- ить системы на основе упрощенных, идеализированных моделей нейронов.
Модель искусственного нейрона показана ниже.
Это абстрактная версия биологического нейрона, представляющая собой структуру с несколькими входами и одним выходом. Выход биологического нейрона зависит от его входного сигнала; точно так же искусственный ней- рон должен активироваться с учетом полученного ввода. Нас интересует мир компьютеров, а не биохимии мозга, поэтому нашему искусственному ней- рону нужна вычислительная модель. Мы исходим из того, что в качестве сиг- налов нейрон получает и отправляет числа. Иными словами, он собирает весь ввод, вычисляет на его основе какое-то арифметическое значение и отправ- ляет на выход какой-то результат. Для реализации искусственного нейрона не требуется никакой специальной электронной схемы. Можете считать, что это крошечная компьютерная программа, которая, как и любая другая, при- нимает входные значения и генерирует вывод. Нам не нужно создавать ней- ронные сети в буквальном смысле; мы можем их симулировать.
Частью процесса обучения биологических нейронных сетей является уси- ление или ослабление синапсов между нейронами. Развитие новых когнитив- ных способностей и поглощение знаний приводит к тому, что одни синапсы становятся сильнее, а другие ослабевают или даже полностью расходятся. Бо- лее того, синапсы могут не только стимулировать, но и блокировать акти- вацию нейрона; когда сигнал доходит до такого синапса, нейрон не должен активироваться. На самом деле у маленьких детей больше мозговых синап- сов, чем у взрослых. В процессе взросления нейронная сеть в нашей голове упрощается. Представьте, что мозг младенца — это глыба мрамора; с каждым

ГЛУБОКОЕ ОБУЧЕНИЕ 123
годом мы становимся опытнее и учимся новому, откалывая от нее кусочек за кусочком. В итоге она начинает приобретать определенную форму.
В искусственном нейроне пластичность синапсов и их способность бло- кировать сигнал определяются весами, которые мы применяем к вводу. В на- шей модели есть n входных значений, x
1
, x
2
, …, x
n
. К каждому из них мы при- меняем веса, w
1
, w
2
, …, w
n
. Каждый вес умножается на соответствующий ввод.
Это итоговое значение, полученное нейроном, является суммой произведе- ний: w
1
x
1
+ w
2
x
2
+ … + w
n
x
n
. К этому взвешенному вводу мы добавляем сдвиг b, который можно считать склонностью нейрона к активации; чем больший сдвиг, тем вероятнее активация. Отрицательный сдвиг, добавленный к взве- шенному вводу, будет блокировать нейрон.
Веса и сдвиг — это параметры нейрона, поскольку они влияют на его пове- дение. Вывод искусственного как и биологического нейрона зависит от его ввода.
Это достигается за счет передачи входных значений специальной функции ак-
тивации (или передаточной функции), которая и генерирует вывод. Ниже пока- зана схема этого процесса, на которой функция активации обозначена как f(ڄ).
Простейшей функцией активации является ступенчатая, которая выдает либо 0, либо 1. Нейрон генерирует 1, если поданное на вход значение больше ноля. В остальных случаях возвращается 0 (то есть нейрон не срабатывает).
–5 5
0 0.75 0.5 0.25 2.5 0
–2.5 1

124 ГЛАВА 6
Сдвиг можно представить себе в качестве порогового значения. Нейрон возвращает 1, если взвешенный ввод превышает определенную величину, или 0, если нет. Действительно, если записать поведение нейрона в виде фор- мулы, первым условием будет w
1
x
1
+ w
2
x
2
+ … + w
n
x
n
+ b > 0 или w
1
x
1
+ w
2
x
2
+
… + w
n
x
n
> –b. Если t = –b, получится w
1
x
1
+ w
2
x
2
+ … + w
n
x
n
> t, где t — про- тивоположность сдвигу; это пороговое значение, которое должен превысить ввод, чтобы нейрон активировался.
На практике вместо ступенчатой обычно используют другие, родствен- ные функции активации. На следующей странице показаны три такие функ- ции, которые часто можно встретить.
Та, что сверху, называется сигмоидой, так как она имеет форму буквы S.
Ее вывод находится в диапазоне от 0 до 1. Крупный положительный ввод дает вывод, близкий к 1; крупный отрицательный ввод дает вывод, близкий к 0.
Это примерно то, как работает биологический нейрон, который активиру- ется только при сильном сигнале; это также плавное приближение ступен- чатой функции. Функция активации, размещенная в центре, называется ги-
перболическим тангенсом, или, сокращенно, tanh (произносится по-разному: tan-H, как в then, или thents с мягким th, как в thanks). Она похожа на сиг- моиду, но находится в диапазоне от –1 до +1; крупный отрицательный ввод дает отрицательный вывод, что эквивалентно блокирующему сигналу. Ниж- няя функция называется выпрямителем. Она превращает любой отрица- тельный ввод в 0; в противном случае ее вывод прямо пропорционален вводу.
В таблице, представленной ниже, показан вывод этих трех функций актива- ции с учетом разного ввода.
С чем связано такое разнообразие функций активации (ведь существуют и другие)? Дело в том, что, как показывает практика, каждая из них имеет определенную сферу применения. Функции активации играют ключевую роль в поведении нейронов, что часто отражается на названиях последних.
Нейрон, который использует ступенчатую функцию, называется перцептро-
ном. Существуют также сигмоидные и tanh-нейроны. Нейрон является струк- турно-функциональной единицей (unit) нервной системы, поэтому нейроны на основе выпрямителей называются ReLU (rectified linear unit — выпрямлен- ная линейная единица).