|
|
Стохастический анализ в задачах
30 марта 2013 г. 11:00–15:30, г. Москва, Большой Власьевский переулок, дом 11
|
|
|
|
|
|
О “Google problem” и эффективных рандомизированных алгоритмах поиска вектора PageRank
(на основе совместных результатов с Ю.Е. Нестеровым и Д.Ю. Дмитриевым)
А. В. Гасников Московский физико-технический институт (государственный университет)
|
Количество просмотров: |
Эта страница: | 581 | Материалы: | 56 |
|
Аннотация:
В докладе рассматриваются два рандомизированных способа поиска вектора PageRank, т.е. решения системы $p^{T}=p^{T}*P$ ($p^{T}$ - строка $p$), со стохастической матрицей $P$ размера $n \times n$ (решение ищется в классе распределения вероятностей), где $n \simeq 10^{8}$, т.о. исключается возможность “честного” умножения матрицы $P$ на столбец, если рассматривать не разреженные объекты. Первый способ базируется на идеи Markov chain Monte Carlo. Этот способ эффективен в случае “быстрого” выхода итерационного процесса $p_{t+1}^{T}=p_{t}^{T}*P$ на стационар, и учитывает также другую специфику матрицы $P$ – равенство отличных от нуля вне диагональных элементов матрицы $P$ по строчкам (это используется при организации случайного блуждания по графу с матрицей $P$). Другой способ использует только разреженность матрицы $P$. Его идея – свести поиск вектора к решению негладкой задачи выпуклой оптимизации: $\max_{k=1,...,n}{p^{T}*P^{<k>} - p_{k}} \to \min$ ( вектор $p$ - принадлежит единичному симплексу), где $P^{<k>}$ -k-ый столбец матрицы $P$. Возникшая задача решается рандомизированным (по Григориадису–Хачияну, 1995) вариантом метода зеркального спуска (для матричных игр). Этот метод приводит практически к таким же оценкам, что и предложенный Назиным–Поляком (2011) для поиска PageRank рандомизированный вариант метода зеркального спуска А.С. Немировского, но для разреженных матриц P предложенный метод показывает заметно лучшие результаты.
Дополнительные материалы:
Автоматика_и_Телемеханика_2014_pagerank.pdf (920.4 Kb)
|
|