Изменения

Перейти к: навигация, поиск

Граница Чернова

436 байт убрано, 09:08, 29 апреля 2019
м
Нет описания правки
==Применение==
Оценка границей Чернова используется в решении проблем уравновешивания множеств <ref>[https://en.wikipedia.org/wiki/Set_balancing Wikipedia {{{---}}} Set balancing]</ref> и маршрутизации пакетов в разреженных сетях.<ref>Michael Mitzenmacher, Eli Upfal. «Probability and Computing: Randomized Algorithms and Probabilistic Analysis» {{---}} «Cambridge University Press», 2005 г. {{---}} 72-83 стр. {{---}} ISBN 0-521-83540-2</ref>
Задача уравновешивания двух множеств возникает при планировании статистических экспериментов. Обычно при планировании эксперимента известны свойства каждого участника, задача состоит в том, чтобы разделить участников на две группы: контрольную и тестовую, так, чтобы каждое свойство было как можно более сбалансированно между двумя группами. <ref>Michael Mitzenmacher, Eli Upfal. «Probability and Computing: Randomized Algorithms and Probabilistic Analysis» {{---}} «Cambridge University Press», 2005 г. {{---}} 71-72 стр. {{---}} ISBN 0-521-83540-2</ref>
Граница Чернова используется в теории вычислительного обучения для оценки того, что алгоритм с большой вероятностью имеет небольшую ошибку на достаточно большом наборе обучающих данных<ref>M. Kearns, U. Vazirani. «An Introduction to Computational Learning Theory» {{---}} «MIT Press», 1994 г. {{---}} 190-192 стр. {{---}} ISBN 0-262-11193-4</ref>
== См. также ==
* [[Математическое ожидание случайной величины]]
== Примечания ==
<references/>
 
== Источники информации ==
* [https://www.lektorium.tv/lecture/12871 Лекториум CS-центра {{---}} Лекция Дмитрия Ицыксона]
* [https://en.wikipedia.org/wiki/Chernoff_bound Wikipedia {{---}} Chernoff bound]
* Michael Mitzenmacher, Eli Upfal. «Probability and Computing: Randomized Algorithms and Probabilistic Analysis» {{---}} «Cambridge University Press», 2005 г. {{---}} 61-71 83 стр. {{---}} ISBN 0-521-83540-2* M. Kearns, U. Vazirani. «An Introduction to Computational Learning Theory» {{---}} «MIT Press», 1994 г. {{---}} 190-192 стр. {{---}} ISBN 0-262-11193-4
== Примечания ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
89
правок

Навигация