Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Стохастический анализ в задачах
30 марта 2013 г. 11:00–15:30, г. Москва, Большой Власьевский переулок, дом 11
 


О “Google problem” и эффективных рандомизированных алгоритмах поиска вектора PageRank (на основе совместных результатов с Ю.Е. Нестеровым и Д.Ю. Дмитриевым)

А. В. Гасников

Московский физико-технический институт (государственный университет)
Дополнительные материалы:
Adobe PDF 920.4 Kb

Количество просмотров:
Эта страница: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)
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024