Стивен Строгац - Удовольствие от Х.Увлекательная экскурсия в мир математики от одного из лучших преподавателей в мир

Мастер По. Закрой глаза. Что ты слышишь?

Юный Кэйн. Я слышу воду. Я слышу пение птиц.

По. Слышишь ли ты, как бьется твое сердце?

Кэйн. Нет.

Мастер По. Слышишь ли ты кузнечика, что стрекочет у твоих ног?

Кэйн. Старик, как тебе удается слышать все это?

По. Юноша, как ты умудряешься этого не слышать?

Признание существования проблемы замкнутого круга для ранжирования веб-страниц, а также ее решение с помощью линейной алгебры вылилось в два направления исследований, опубликованных в 1998 году. Одно было проведено моим коллегой по Корнуолльскому университету Джоном Клейнбергом, который впоследствии стал экспертом исследовательского центра IBM Almaden Research Center. Его исследование посвящено алгоритму HITS (альтернативной форме анализа ссылок, появившейся немного раньше, чем алгоритм PageRank от Google), см. J. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (1998).

Вторая линия исследований проводилась основателями Google Ларри Пейджем и Сергеем Брином. В основе их алгоритма PageRank лежало количество времени, которое случайный пользователь сети будет проводить на каждой странице. Этот процесс описывается по-иному, но приводит все к той же проблеме замкнутого круга. Обоснования метода PageRank даны в статье S. Brin and L. Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the Seventh International World Wide Web Conference (1998), рр. 107–117.

Как это часто случается в науке, поразительно похожие предвестники этих идей уже были открыты в других ее областях. С предысторией появления PageRank в библиометрике, психологии и социологии можно ознакомиться в статье М. Franceschet, PageRank: Standing on the shoulders of giants, Communications of the ACM, Vol. 54, № 6 (2011), доступной на http://arxiv.org/abs/1002.2858, а также S. Vigna, Spectral ranking, на http://arxiv.org/abs/0912.0238.

Введение в линейную алгебру и способы ее применения в различных областях науки прекрасно изложены в книге G. Strang, Introduction to Linear Algebra, 4th edition (Wellesley-Cambridge Press, 2009).

Некоторые наиболее впечатляющие области применения линейной алгебры описаны в работе D. James, М. Lachance, and J. Remski, Singular vectors’ subtle secrets, College Mathematics Journal, Vol. 42, № 2 (March 2011), рр. 86–95.

Согласно Google, термин PageRank происходит от имени Ларри Пейджа, а не от английского слова webpage (веб-страница). См. http://web.archive.org/web/20090424093934/http://www.google.com/press/funfacts.html.

Эта идея основана на том, что лицо человека представляет собой комбинацию небольшого числа его основных компонентов. Впервые линейная алгебра была применена для распознавания лиц в работе L. Sirovich and М. Kirby, Low-dimensional procedure for the characterization of human faces, Journal of the Optical Society of America A, Vol. 4 (1987), рр. 519–524 и получила дальнейшую разработку в исследовании М. Turk and A. Pentland, Eigenfaces for recognition, Journal of Cognitive Neuroscience, Vol. 3 (1991), рр. 71–86, доступном на http://cse.seu.edu.cn/people/xgeng/files/under/turk91eigenfaceForRecognition.pdf.

Полный список работ, посвященных этой проблеме, см. на главной странице сайта Face Recognition (http://www.face-rec.org/interesting-papers/).

См. L. Sirovich, A pattern analysis of the second Rehnquist U.S. Supreme Court, Proceedings of the National Academy of Sciences, Vol. 100, № 13 (2003), рр. 7432–7437. Этому исследованию посвящена статья N. Wade, A mathematician crunches the Supreme Court’s numbers, New York Times (June 24, 2003). Следующая работа предназначена для специалистов в области права и написана математиком и профессором права: P. H. Edelman, The dimension of the Supreme Court, Constitutional Commentary, Vol. 20, № 3 (2003), рр. 557–570.

Историю приза компании Netflix, а также интересные подробности о первых претендентах на него читайте в статье C. Thompson, If you liked this, you’re sure to love that — Winning the Netflix prize, New York Times Magazine (November 23, 2008). Победитель был определен в сентябре 2009 года, через три года после начала соревнования, см. S. Lohr, A $1 million research bargain for Netflix, and maybe a model for others, New York Times (September 22, 2009). Применение метода разложения матрицы по собственным значениям для определения приза Netflix описано в работе B. Cipra, Blockbuster algorithm, SIAM News, Vol. 42, № 4 (2009).

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

С другой стороны, существуют сети, где некоторые страницы или группы страниц открыты для накапливания PageRank, но при этом не делают ссылок на другие страницы. Подобные страницы действуют как накопители PageRank.