[БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] Давайте рассмотрим с вами самого яркого представителя ссылочного ранжирования, а именно алгоритм PageRank. Во-первых, так как это алгоритм ранжирования, то в конечном счете PageRank — это конкретное число, связанное с конкретным документом, которое показывает, насколько хорош этот документ. Кроме того, для того чтобы вычислить значение PageRank для каждого документа, мы будем основываться исключительно на ссылках между документами в нашем корпусе. Таким образом, нам достаточно вычислить PageRank, и он будет верен до тех пор, пока мы не меняем каким-то образом документы в корпусе либо не перестраиваем сам корпус. Итак, что же такое алгоритм PageRank? Представим, что у нас есть пользователь, который случайным образом путешествует по нашему корпусу, переходя с документа на документ по ссылкам. В конечном счете с определенной вероятностью он остановится на каком-то документе. Именно эта вероятность и является PageRank этого документа. Таким образом, PageRank отдельно взятого документа складывается из PageRank тех документов, откуда он может прийти на этот документ, и количества ссылок на них. Кроме того, добавим несколько случайных величин. Во-первых, с определенной вероятностью пользователь может наконец прекратить блуждать между документами. Во-вторых, для того чтобы перейти с одного документа на другой, пользователь должен с определенной вероятностью выбрать, по какой именно ссылке перейти. В случае если у документа несколько исходящих ссылок, то будем считать, что пользователь перейдет по каждой из них с одинаковой вероятностью. Ну и, наконец, есть еще коэффициент телепортации, который показывает нам, что с какой-то вероятностью пользователь может с текущего документа переместиться на другой документ, не обязательно связанный напрямую с исходным какой-то ссылкой. В первую очередь это важно в случае, если мы окажемся в тупике, то есть в документе, из которого нет исходящих ссылок. Кроме того, не стоит забывать, что пользователь может с тем же успехом телепортироваться и из документа, в котором есть исходящие ссылки. Итак, давайте формализуем все эти знания и заменим большую часть вероятностей на коэффициент угасания. Этот коэффициент лежит в пределах от 0 до 1, обычно его берут в пределах от 0,25 до 0,85. Мы в наших примерах будем рассматривать именно 0,85. Этот коэффициент показывает, насколько угасает интерес пользователя к текущей странице. Итак, в конечном счете формула будет иметь такой вид. Первое слагаемое — это единица минус вероятность того, что пользователю не нравится эта страница, то есть мы получаем вероятность того, что пользователю данная страница нравится, и он на ней остается. Дальше во втором слагаемом у нас есть все та же вероятность, которая говорит нам о том, что пользователю надоели предыдущие страницы, откуда он пришел, и поэтому он оказался здесь. И, естественно, второй множитель — это, собственно, вероятности того, что он оказался на тех страницах, то есть это PageRank этих страниц, относящиеся к количеству ссылок на них, по которым он перешел на текущую страницу. Итак, казалось бы, формула ясна, однако мы сталкиваемся со следующей проблемой. Для того чтобы вычислить PageRank для конкретной страницы, мы должны вычислить PageRank для тех страниц, которые на нее ссылаются, которые в свою очередь прямо или косвенно зависят от PageRank текущей страницы. Для того чтобы решить эту проблему, существует несколько подходов, и мы с вами их сейчас и рассмотрим. [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА]
