|
|
Стохастический анализ в задачах
21 сентября 2013 г. 11:00, г. Москва, Большой Власьевский переулок, дом 11
|
|
|
|
|
|
Задача о двуруком бандите в приложении к параллельной обработке данных
А. В. Колногоров Новгородский государственный университет им. Ярослава Мудрого
|
Количество просмотров: |
Эта страница: | 282 | Материалы: | 64 |
|
Аннотация:
Рассматривается задача о двуруком бандите в приложении к обработке больших массивов данных. Предполагается, что данные могут обрабатываться одним из двух альтернативных методов с фиксированными, но априори неизвестными эффективностями. Надо так организовать обработку, чтобы определить более эффективный метод и обеспечить его преимущественное применение. При этом данные допускается объединять в группы и обрабатывать параллельно.
Суть результата состоит в том, что параллельная обработка практически не приводит к потере качества управления, т.е. к увеличению минимаксного риска. Например, 30000 тысяч данных могут быть обработаны партиями по 1000 штук за 30 этапов приблизительно с такими же максимальными потерями, как если бы они обрабатывались оптимально по одному. Важно, что минимаксные стратегия и риск могут быть найдены численными методами для произвольного конечного горизонта управления. При этом оказывается, что для практических целей горизонт совсем не должен быть большим. Например, 30 или 50 этапов управления вполне достаточно (т.е. данные надо разбивать на 30 и, соответственно, 50 партий). Отметим, что большинство результатов в данной области, напротив, имеют дело с асимптотическими оценками, которые мало что дают для небольших значений горизонта.
Дополнительные материалы:
review.pdf (1.7 Mb)
,
two_armed.pdf (2.6 Mb)
|
|