Удовольствие от Х.Увлекательная экскурсия в мир математики от одного из лучших преподавателей в мир
Шрифт:
Защитник обвиняемого Алан Дершовиц [129] приводил доводы, что даже если бы голословные утверждения о домашнем насилии оказались правдой, они не относятся к делу и, следовательно, недопустимы. Позднее он написал: «Нам необходимо было доказать, что среди тех, кто избивает своих партнеров, лишь ничтожно малое число, менее 1 из 2500, совершают убийство».
В действительности же обе стороны просили суд рассмотреть вероятность того, что Симпсон убил бывшую жену, принимая во внимание тот факт, что при жизни он ее избивал. Однако специалист в области статистики И. Гуд отметил, что для этого не существует верного доказательства, на которое можно было бы сослаться.
129
Каким образом Дершовиц пришел к выводу, что среди лиц, избивающих своих партнеров, менее 1 из 2500 убивают их? На странице 104 его книги Reasonable Doubts приведены следующие цифры: в 1992 году в США от 2,5 до 4 миллионов женщин подвергались избиению со стороны мужей, любовников и бывших любовников. В том же году, согласно отчетам ФБР об уровне преступности , 913 женщин были убиты своими мужьями, а еще 519 — своими любовниками или бывшими любовниками. Если разделить общее количество убийств 1432 на 2,5 миллиона избитых женщин, то выйдет 1 убийство на 1746 избиений, а если принимать во внимание верхний порог числа избиений в 4 миллиона, то в результате получим одно убийство на 2793 избиений. Очевидно, что среди этих крайних показателей Дершовиц выбрал значение 2500.
Однако остается неясным, какая доля убитых женщин подвергалась при жизни избиениям
Вопрос на самом деле в следующем: какова вероятность того, что муж убил свою бывшую жену, если до убийства он ее бил и она была кем-то убита? Условная вероятность в таком случае очень далека от схемы 1 на 2500.
Чтобы разобраться почему, представим себе выборку из 100 тысяч избитых женщин. Ссылаясь на предоставленные Дершовицем цифры — 1 из 2500, допустим, что примерно сорок из этих женщин были убиты мужьями в этом году (поскольку 100 000 разделить на 2500 равно 40). Можно также предположить, что еще трое из них убиты кем-либо другим [130] (эта оценка основана на статистике ФБР, касающейся количества женщин, убитых в 1992 году). Итак, из этих 43 жертв 40 были убиты теми, кто их избивал. Другими словами, в 93 % случаев убийцей являлось лицо, избивавшее женщину.
130
Согласно отчетам ФБР об уровне преступности, 4936 женщин были убиты в 1992 году. Среди них 1432 (около 29 %) убиты мужьями или любовниками. Оставшиеся 3504 пострадали от рук кого-то другого. Следовательно, принимая во внимание, что в США на тот период проживало около 125 миллионов женщин, доля тех, кто стал жертвами убийства со стороны лиц, не являвшихся их партнерами, составила 3504 на 125 миллионов, или 1 убийство на 35 673 женщин в год.
Предположим, что эта доля убийств одинакова для всех женщин независимо от того, избивали их при жизни или нет. Тогда делим 100 тысяч избиваемых женщин из нашей гипотетической выборки на 35 673 и в результате получаем 2,8 женщин, то есть столько убито лицами, которые не являлись их партнерами. Округлив 2,8 до 3, получаем оценку, приведенную в данной работе.
Не путайте это число с вероятностью того, что это сделал Симпсон. Она зависит от множества других обстоятельств, от разных «за» и «против». Например, от заявления защиты о том, что полиция выдвинула Симпсону ложные обвинения, а также от заявления обвинения, что убийца и Симпсон носили одинаковую обувь, перчатки и имели почти одинаковый код ДНК.
Какова вероятность того, что что-нибудь из перечисленного изменит ваше мнение о вынесенном приговоре? Ноль.
24. Распутывание всемирной паутины
В те далекие времена, когда Google еще не существовало, поиск в сети был безнадежным занятием [131] . Сайты, предлагаемые старыми поисковыми машинами, часто не соответствовали запросу, а те, которые содержали нужную информацию, были либо глубоко запрятаны в списке результатов, либо вообще отсутствовали.
Алгоритмы на основе анализа ссылок решили проблему, проникнув в суть парадокса, подобного коанам дзен: в результате поиска в интернете должны были отображаться лучшие страницы. А что же, кузнечик [132] , делает страницу лучшей? Когда на нее ссылаются другие не менее хорошие страницы.
131
Введение в поиск в интернете и анализ ссылок см. D. Easley and J. Kleinberg, Networks, Crowds, and Markets (Cambridge University Press, 2010). Популярное изложение истории поиска в сети, рассказ о его основных действующих лицах и компаниях ищите в J. Battelle, The Search (Portfolio Hardcover, 2005). Тем, кто хорошо знаком с линейной алгеброй, будет интересна история развития анализа ссылок в статье S. Robinson, The ongoing search for efficient Web search algorithms, SIAM News, Vol. 37, № 9 (2004).
132
Если вас смутило использованное мной слово «кузнечик», поясню, что этим ласковым именем называют ученика, которому еще предстоит многому научиться у мастера дзен. В телесериале «Кунг-фу» слепой монах По учит мудрости своего ученика Кэйна и на первом уроке называет его кузнечиком.
Мастер По. Закрой глаза. Что ты слышишь?
Юный Кэйн. Я слышу воду. Я слышу пение птиц.
По. Слышишь ли ты, как бьется твое сердце?
Кэйн. Нет.
Мастер По. Слышишь ли ты кузнечика, что стрекочет у твоих ног?
Кэйн. Старик, как тебе удается слышать все это?
По. Юноша, как ты умудряешься этого не слышать?
Звучит подобно рассуждениям про замкнутый круг. [133] Так и есть. Именно поэтому все настолько сложно. Ухватившись за эту идею и превратив ее в преимущество, алгоритм анализа ссылок дает решение поиска в сети в стиле джиу-джитсу.
Этот подход построен на идеях, взятых из линейной алгебры [134] , изучения векторов и матриц. Если вы хотите выявить закономерности в огромном скоплении данных или выполнить гигантские вычисления с миллионами переменных, линейная алгебра предоставит для этого все необходимые инструменты [135] . С ее помощью был построен фундамент для алгоритма PageRank [136] , положенного в основу Google. Она также помогает ученым классифицировать человеческие лица [137] , провести анализ голосования в Верховном суде [138] , а также выиграть приз Netflix [139] (вручаемый команде, сумевшей улучшить более чем на 10 % систему Netflix, на основе которой составляются рекомендации для просмотра лучших фильмов).
133
Признание существования проблемы замкнутого круга для ранжирования веб-страниц, а также ее решение с помощью линейной алгебры вылилось в два направления исследований, опубликованных в 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), доступной наа также S. Vigna, Spectral ranking, на http://arxiv.org/abs/0912.0238.
134
Введение в линейную алгебру и способы ее применения в различных областях науки прекрасно изложены в книге G. Strang, Introduction to Linear Algebra, 4th edition (Wellesley-Cambridge Press, 2009).
135
Некоторые наиболее впечатляющие области применения линейной алгебры описаны в работе D. James, М. Lachance, and J. Remski, Singular vectors’ subtle secrets, College Mathematics Journal, Vol. 42, № 2 (March 2011), рр. 86–95.
136
Согласно Google, термин PageRank происходит от имени Ларри Пейджа, а не от английского слова webpage (веб-страница). См. http://web.archive.org/web/20090424093934/http://www.google.com/press/funfacts.html.
137
Эта идея основана на том, что лицо человека представляет собой комбинацию небольшого числа его основных компонентов. Впервые линейная алгебра была применена для распознавания лиц в работе 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 .
138
См. 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.
139
Историю приза компании 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. А чтобы выявить его сущность без лишней суеты, представим игрушечную паутину, состоящую всего из трех страниц, связанных между собой следующим образом:
Стрелки указывают, что страница X содержит ссылку на страницу Y, однако Y не отвечает ей взаимностью. Наоборот, Y ссылается на Z. Тем временем X и Z ссылаются друг на друга, сцепившись между собой цифровыми лапками.
Какие страницы самые важные в этой маленькой паутине? Вы можете подумать, что это невозможно определить из-за недостатка информации об их содержимом. Но такой способ мышления устарел. Беспокойство по поводу контента вылилось в неудобный способ ранжирования страниц. Компьютеры мало понимают в смысловом наполнении, а люди не справляются с тысячами новых страниц, которые каждый день появляются в сети.
Подход, придуманный Ларри Пейджем и Сергеем Брином, аспирантами университета и основателями Google, состоял в том, чтобы позволить страницам самим ранжироваться в определенном порядке, голосуя ссылками. В приведенном выше примере страницы X и Y ссылаются на Z, благодаря чему Z становится единственной страницей с двумя входящими ссылками. Следовательно, она и будет самой популярной страницей в данной среде. Однако если ссылки поступают со страниц сомнительного качества, они станут работать против себя. Популярность сама по себе ничего не значит. Главное — иметь ссылки с хороших страниц.
И здесь мы снова оказывается в замкнутом круге. Страница считается хорошей, если на нее ссылаются хорошие страницы, но кто изначально решает, какие из них хорошие?
Это решает сеть. Вот как все происходит. (Далее я буду пропускать некоторые подробности, изложенные в примечании [140] .)
Алгоритм Google назначает для каждой страницы дробное число от 0 до 1. Это численное значение называется PageRank и измеряет «важность» страницы по отношению к другим, высчитывая относительное количество времени, которое гипотетический пользователь потратит на ее посещение. Хотя пользователь может выбирать более чем из одной исходящей ссылки, он выбирает ее случайно с равной вероятностью. При таком подходе страницы считаются более авторитетными, если они чаще посещаются.
140
Для простоты я представлю только базовую версию алгоритма PageRank. Для обработки сетей с некоторыми другими структурными свойствами его необходимо изменить. Предположим, в сети есть страницы, которые ссылаются на другие, но те, в свою очередь, на них не ссылаются. В процессе обновления эти страницы потеряют свой PageRank. Они отдают его другим, и он больше не восполняется. Таким образом, в конце концов они получат значения PageRank, равные нулю, и с этой точки зрения становятся неразличимыми.
С другой стороны, существуют сети, где некоторые страницы или группы страниц открыты для накапливания PageRank, но при этом не делают ссылок на другие страницы. Подобные страницы действуют как накопители PageRank.
Чтобы избежать подобных результатов, Брин и Пейдж изменили свой алгоритм следующим образом. После каждого этапа в процессе обновления данных все текущие значения PageRank уменьшаются на постоянный коэффициент, так что их сумма будет меньше 1. Затем остатки PageRank равномерно распределяются между всеми узлами в сети, как будто «сыплются с неба». Таким образом, алгоритм завершается действием уравнивания, распределяющим значения PageRank между самыми «бедными» узлами.
Более тщательно математика PageRank и интерактивные исследования рассматриваются в работе E. Aghapour, T. P. Chartier, A. N. Langville, and K. E. Pedings, Google PageRank: The mathematics of Google . Полную информацию, изложенную в доступной форме, вы найдете в книге A. N. Langville and С. D. Meyer, Google’s PageRank and Beyond (Princeton University Press, 2006).
А поскольку индексы PageRank определяются как пропорции, их сумма по всей сети должна составлять 1. Этот закон сохранения предполагает другой, возможно, более осязаемый способ визуализации PageRank. Представьте его как жидкое вещество, текущее по сети, количество которого уменьшается на плохих страницах и увеличивается на хороших. С помощью алгоритма мы пытаемся определить, как эта жидкость распределяется по интернету на протяжении длительного времени.
Ответ получим в результате многократно повторяющегося следующего процесса. Алгоритм начинается с некоего предположения, затем обновляет все значения PageRank, распределяя жидкость в равных частях по исходящим ссылкам, после этого она проходит несколько кругов, пока не установится определенное состояние, при котором страницы получат причитающуюся им долю.
Изначально алгоритм задает равные доли, что позволяет каждой странице получить одинаковое количество PageRank. В нашем примере три страницы, и каждая из них начинает движение по алгоритму со счетом 1/3.
Начальные значения PageRank
Затем счет обновляется, отображая реальное значение каждой страницы. Правило состоит в том, что каждая страница берет свой PageRank с последнего круга и равномерно распределяет его по всем страницам, на которые ссылается. Следовательно, обновленное значение страницы X после прохождения первого круга по-прежнему равно 1/3, поскольку именно столько PageRank она получает от Z, единственной страницы, которая на нее ссылается. При этом счет страницы Y уменьшается до 1/6, так как она получает только половину PageRank от X после предыдущего круга. Вторая половина переходит к странице Z, что делает ее победителем на данном этапе, поскольку она добавляет себе еще 1/6 от страницы X, а также 1/3 от Y, и всего получается 1/2. Таким образом, после первого круга мы имеем следующие значения PageRank: