|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
Об эффективных рандомизированных алгоритмах поиска вектора PageRank
А. В. Гасниковab, Д. Ю. Дмитриевba a 141000 Долгопрудный, М.о., Институтский пер., 9, МФТИ
b ИППИ РАН
Аннотация:
В работе рассматриваются два рандомизированных способа поиска вектора PageRank, т.е. решения системы $\mathbf{p}^{\mathrm{T}}=\mathbf{p}^{\mathrm{T}}P$, со стохастической матрицей $P$ размера $n\times n$ (решение ищется в классе распределений вероятностей), где $n\sim 10^7$–$10^9$, с точностью $\varepsilon: \varepsilon\gg n^{-1}$, таким образом исключается возможность “честного” умножения матрицы $P$ на столбец, если рассматривать не разреженные объекты. Первый способ базируется на идее Markov chain Monte Carlo. Этот подход эффективен в случае “быстрого” выхода итерационного процесса $\mathbf{p}_{t+1}^{\mathrm{T}}=\mathbf{p}_t^{\mathrm{T}}P$ на стационар, и учитывает также другую специфику матрицы $P$ — равенство отличных от нуля вне диагональных элементов матрицы $P$ по строчкам (это используется при организации случайного блуждания по графу с матрицей $P$). На основе современных неравенств концентрации меры в работе приводятся новые оценки времени работы такого метода, учитывающие специфику матрицы $P$. В основе второго способа лежит идея сведения поиска ранжирующего вектора к поиску равновесия в антагонистической матричной игре:
$$
\min_{\mathbf{p}\in S_n(1)}\max_{\mathbf{u}\in S_n(1)}\langle \mathbf{u}, (P^{\mathrm{T}}-I)\mathbf{p}\rangle,
$$
где $S_n(1)$ — единичный симплекс в $\mathbb{R}^n$, а $I$ — единичная матрица. Возникшая задача решается с помощью небольшой модификации алгоритма Григориадиса–Хачияна (1995). Этот метод, также как метод Назина–Поляка (2009), является рандомизированным вариантом метода зеркального спуска А. С. Немировского. Отличие заключается в том, что у Григориадиса–Хачияна рандомизация осуществляется на этапе проектирования на симплекс, а не на этапе вычисления стохастического градиента. Для разреженных матриц $P$ предложенный нами метод показывает заметно лучшие результаты. Библ. 67.
Ключевые слова:
метод зеркального спуска, Markov chain Monte Carlo, стохастическая оптимизация, рандомизация, PageRank.
Поступила в редакцию: 03.09.2014
Образец цитирования:
А. В. Гасников, Д. Ю. Дмитриев, “Об эффективных рандомизированных алгоритмах поиска вектора PageRank”, Ж. вычисл. матем. и матем. физ., 55:3 (2015), 355–371; Comput. Math. Math. Phys., 55:3 (2015), 349–365
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10164 https://www.mathnet.ru/rus/zvmmf/v55/i3/p355
|
Статистика просмотров: |
Страница аннотации: | 716 | PDF полного текста: | 264 | Список литературы: | 94 | Первая страница: | 9 |
|