Что такое постоянные собственные векторы и алгоритм ранжирования страниц в Google.

Что такое постоянные собственные векторы и алгоритм ранжирования страниц в Google.

Я специалист по анализу данных, работаю в Дубае, Объединенные Арабские Эмираты. И имейте страсть к математике. Это будет мой первый технический блог. Я думаю, что линейная алгебра - это строительный блок для любого специалиста по данным, а собственные векторы - это поддомен линейной алгебры. Поэтому я решил написать блог о собственных векторах и о том, как основатели Google использовали собственные векторы, чтобы придумать алгоритм Page-Rank, который в конце концов помог тому, чем является Google сегодня.

ЧТО такое СОБСТВЕННЫЙ ВЕКТОР?

Слово «собственный вектор» взято из немецкого слова «собственная характеристика». Но что касается Векторов, о которых идет речь. Давайте сначала погрузимся в это.

Ниже мы видим 2D-плоскость с множеством векторов, начерченных из начала координат. Мы можем представить эти векторы в виде квадрата.

Далее мы возьмем только три вектора из всех этих векторов.

Чтобы понять собственные векторы, нам сначала нужно немного понять о вращении и масштабировании.

МАСШТАБ

Затем мы применим к этим векторам некоторые линейные преобразования, чтобы понять собственные векторы.

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

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

Теперь после трансформации:

ВРАЩЕНИЕ

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

Таким образом, мы можем сказать, что собственные векторы - это векторы, которые остаются неизменными после применения некоторого линейного преобразования.

Теперь перейдем к математическим уравнениям.

Итак, мы заинтересованы в

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

Допустим, у нас есть матрица ниже:

Мы можем вычислить определитель

Используя формулу ниже

Решая вышеизложенное, мы получаем следующий характеристический многочлен:

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

Давайте поработаем с примером:

Для лямбда на 1 мы можем сказать, что наш собственный вектор может быть любым вдоль оси x, пока вертикальное направление равно нулю. То же самое для собственного вектора на lambda 2, мы можем сказать, что наш собственный вектор может быть любым вдоль оси y, как пока ось абсцисс равна нулю.

Давайте теперь попробуем с матрицей преобразования, которая поворачивает вектор на 90 градусов.

Например, возьмем

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

АЛГОРИТМ РАНГА СТРАНИЦЫ:

Нижеприведенное определение взято из книги по математике для машинного обучения:
https://mml-book.github.io/book/mml-book.pdf

На приведенной выше диаграмме представлен мини-интернет. Где у нас есть четыре ссылки на веб-сайт A, B, C и D, которые ведут на другую веб-страницу. Мы построим выражение, которое сообщит нам, какая из этих ссылок наиболее актуальна для конкретного человека. Для этого мы будем использовать концепцию прокрастинации - похлопать человека, который выходит в Интернет и случайным образом нажимает на веб-ссылки. Мы можем построить модель, которая точно скажет нам, сколько времени пользователь проведет на определенной странице. Давайте сначала построим вектор для A на основе его ссылок. A имеет исходящие ссылки на B, C и D, но не имеет никаких ссылок на себя.

Выше мы можем видеть, что через Link-A мы можем перейти к B, C, D, но он не относится к себе, поэтому у нас есть вероятность для A = 0, B = 1/3, C = 1/3, &, D = 1/3. Аналогично для Link-B мы можем видеть через B, мы можем перейти только к A и D. Таким образом, вероятность для A и D равна 1/2 для B и C нулю. Для канала-C мы можем перейти к D, поэтому вероятность равна 1 для D. В то время как для Link-D A и Dis равны нулю, а для B и C - 1/2.

Итак, векторы ссылок для A, B, C, &, D:

Теперь давайте объединим все векторы в единую матрицу:

То, что у нас есть выше, - это вероятность попадания на веб-страницу с другой страницы. Как, например, единственный способ попасть в A - через B. Итак, нам нужно знать вероятность оказаться в B, которую мы можем пройти через A или D. В основном,
рейтинг всех страниц зависит от рангов других страниц.

Теперь давайте создадим вектор для рангов каждой страницы.

Уравнение для поиска собственного вектора, который показывает вероятности важности всех веб-страниц:

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

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

## Numpy library for matrix and vector manipulation
import numpy as np 
## Link matrix
L = np.array([[0,1/2,0,0], [1/3, 0, 0, 1/2], [1/3, 0, 0, 1/2], [1/3, 1/2, 1, 0]])
## Rank Matrix
r = np.array([1/4,1/4,1/4,1/4])
print(“i A B C D”) ## Print the link vector
## Looping over Link matrix And Rank vector.
for i in range(30):
 print(i, round(r[0],2), round(r[1], 2), round(r[2], 2), round(r[3],      2))
 r = L@r

Итак, мы видим, что после почти 10 итераций наша матрица рангов не меняется. Таким образом, мы можем сказать, что для случайного человека, который попадет на веб-ссылку, A равно 0,12, для B равно 0,24, C также 0,24, в то время как наиболее релевантной веб-ссылкой для этого конкретного человека является D.

Итак, мы узнали о собственных векторах и о том, как Google использует собственные векторы в своем алгоритме поиска. Это была просто базовая интерпретация собственных векторов, и если хотите, вы можете изучить курс Математика для машинного обучения на Coursera. Если хотите, можете ознакомиться с исследовательской работой здесь: http://infolab.stanford.edu/~backrub/google.html. Также вы можете прочитать о собственных векторах из книги https://mml-book.github.io/book/mml-book.pdf