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

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





Для просмотра файлов Вам могут потребоваться








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


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

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

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

Количество просмотров:
Эта страница:385
Материалы:46

Аннотация: В докладе рассматриваются два рандомизированных способа поиска вектора 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)

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020