Loading AI tools
Из Википедии, свободной энциклопедии
Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра и стремится к при стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения . Про такое событие говорят, что оно происходит «с высокой вероятностью» (англ. with high probability, обычно сокращается до w.h.p.) или «асимптотически почти наверное» (asymptoticaly almost surely). Всякое почти достоверное событие (которое происходит с вероятностью ) асимптотически достоверно, обратное неверно.
Используется в информатике при асимптотическом анализе вероятностных алгоритмов. Например, если некоторый алгоритм работает на графах с вершинами и вероятность того, что алгоритм выдаст правильный результат равна , то при достаточно большом количестве вершин в графе вероятность того, что алгоритм выдаст правильный ответ будет близка к , то есть, можно говорить, что «алгоритм корректен с высокой вероятностью».
Некоторые алгоритмы, использующие понятие асимптотической достоверности:
В машинном обучении применяется схема вероятно приближённо корректного обучения, в котором конструируемая функция обладает низкой ошибкой обобщения с высокой вероятностью.
Выделяется класс сложности BQP, состоящий из задач, для которых существуют полиномиальные квантовые алгоритмы, корректные с высокой вероятностью.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.