Александр Владимирович Гасников
О задаче ранжирования web-страниц и её окрестностях
А.В.Гасников планирует провести 4 занятия.
|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2013/courses/gasnikov.htm
Дата изменения: Sat Jul 20 10:43:58 2013 Дата индексирования: Sun Apr 10 12:02:59 2016 Кодировка: koi8-r |
| На главную страницу ЛШСМ-2013 | К списку курсов ЛШСМ-2013 |
Александр Владимирович ГасниковО задаче ранжирования web-страниц и её окрестностяхА.В.Гасников планирует провести 4 занятия. |
|
В цикле лекций будет предпринята попытка на нескольких ярких примерах доступно рассказать основные современные подходы к решению выпуклых задач huge-scale оптимизации и on-line оптимизации. Первые задачи возникают, например, при ранжировании web-страниц (Google problem: поиск вектора PageRank), а вторые возникают, например, в задачах о многоруком бандите. Задача ранжирования web-страниц сводится к поиску собственного вектора стохастической матрицы. Проблема в том, что матрица эта размером: миллиаррд на миллиард. И даже проверка того, что мы нашли подходящий вектор может занять годы... А задачу нужно как-то решать. Простейший вариант задачи о многоруком бандите (кстати, к таким задачам сводятся некоторые модели управления социальными сетями) можно сформулировать так: есть две ручки, дергая за первую ручку мы выигрываем один рубль с вероятность p1, а за вторую — p2. На каждом из N>>1 шагов мы можем дергать только одну ручку. Целью является так организовать процедуру дергания ручек, чтобы ожидаемый доход после N шагов был бы наибольшим. Проблема в том, что p1 и p2 нам не известны. Тем не менее, дергая ручки мы можем запоминать какая ручка, что давала, и использовать эту информацию при принятии решений на последующих шагах.
Оказывается, эти и многие другие задачи можно эффективно решать единым методом (восходящим к Немировскому–Юдину), о котором и пойдет речь в этом цикле лекций.