Медианный трюк

Медианный трюк — это общий подход, который увеличивает шансы вероятностного алгоритма на успех. Судя по всему, впервые использован в 1986 году. Джеррум и др. для алгоритмов приближенного подсчета этот метод позже был применен к широкому кругу задач классификации и регрессии .

Идея медианного трюка очень проста: запустите рандомизированный алгоритм с числовым выводом несколько раз и используйте медиану полученных результатов в качестве окончательного ответа. Например, для сублинейных по времени алгоритмов один и тот же алгоритм можно запускать повторно (или параллельно) над случайными подмножествами входных данных, и, согласно неравенству Чернова , медиана результатов будет очень быстро сходиться к решению. Для алгоритмов, которые являются сублинейными в пространстве (например, подсчитывают отдельные элементы потока), разные рандомизации алгоритма (скажем, с разными хэш-функциями ) должны использоваться для повторных прогонов одних и тех же данных.

Источники

• Коглер, Александр; Трэкслер, Патрик (2017). «Параллельная и надежная минимизация эмпирического риска с помощью медианного трюка». Математические аспекты компьютерных и информационных наук . Чам: Международное издательство Springer. дои : 10.1007/978-3-319-72453-9_31 . ISBN  978-3-319-72452-2 . ISSN   0302-9743 .
• Джеррам, Марк Р.; Валиант, Лесли Г.; Вазирани, Виджай В. (1986). «Случайная генерация комбинаторных структур из равномерного распределения». Теоретическая информатика . 43 . Эльзевир Б.В.: 169–188. дои : 10.1016/0304-3975(86)90174-х . ISSN   0304-3975 .
• Ван, Дэн; Хан, Чжу (2015). «Основы сублинейных алгоритмов». Сублинейные алгоритмы для приложений с большими данными . Чам: Международное издательство Springer. дои : 10.1007/978-3-319-20448-2_2 . ISBN  978-3-319-20447-5 . ISSN   2191-5768 .