Публикация:McDiarmid 2002 Concentration for Independent Permutations

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Доказательство неравенства)
 
(1 промежуточная версия не показана)
Строка 60: Строка 60:
Доказательство сформулированного выше утверждения во всей красе использует индуктивный метод, разработанный Талаграном ([http://people.math.jussieu.fr/~talagran/ Michel Talagrand]) в ходе его исследования парадокса концентрации меры ([[Концентрация вероятностной меры|concentration of measure]]).
Доказательство сформулированного выше утверждения во всей красе использует индуктивный метод, разработанный Талаграном ([http://people.math.jussieu.fr/~talagran/ Michel Talagrand]) в ходе его исследования парадокса концентрации меры ([[Концентрация вероятностной меры|concentration of measure]]).
Оно опирается на (уже классической в теории статистического обучения) теореме Талаграна (торема 4.1.1, [1]), связывающей меру подмножества <tex>A \subset \Omega^N</tex> с расстоянием от случайного элемента <tex>x\in\Omega^N</tex> до этого подмножества:
Оно опирается на (уже классической в теории статистического обучения) теореме Талаграна (торема 4.1.1, [1]), связывающей меру подмножества <tex>A \subset \Omega^N</tex> с расстоянием от случайного элемента <tex>x\in\Omega^N</tex> до этого подмножества:
-
::<tex>\mathsf{P}(A) \mathsf{E}\bigl(f^2(A,x)\bigr)\leq1,</tex>
+
::<tex>\mathsf{P}(A) \mathsf{E}\bigl(\frac{1}{4}f^2(A,x)\bigr)\leq1,</tex>
где <tex>f(A,x)</tex> — расстояние, введенное Талаграном.
где <tex>f(A,x)</tex> — расстояние, введенное Талаграном.
Строка 73: Строка 73:
|год = 1995
|год = 1995
|страниц =
|страниц =
-
|ссылка = http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=836D8E512EF351A85FDF035F2B8EA772?doi=10.1.1.21.1050&rep=rep1&type=pdf
+
|ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1050
|isbn =
|isbn =
}}
}}

Текущая версия

McDiarmid, C. Concentration for Independent Permutations // Comb. Probab. Comput.. — Cambridge University Press, 2002. — Vol. 11. — No. 2. — Pp. 163-178.

BibTeX: 
 @article{mcdiarmid2002concentration,
   author = "McDiarmid, C.",
   title = "Concentration for Independent Permutations",
   journal = "Comb. Probab. Comput.",
   publisher = "Cambridge University Press",
   volume = "11",
   number = "2",
   pages = "163-178",
   url = "http://www.machinelearning.ru/wiki/images/3/32/Mcdiarmid2002concentration.pdf",
   year = "2002",
   language = english
 }

Содержание

Аннотация

В статье представлено неравенство концентрации меры, затрагивающее семейство независимых случайных перестановок.

Реферат

Основной результат

Вкратце основной результат, представленный в статье, можно сформулировать следующим образом:

пусть Z = h(Y),\; Y=(X, \pi)\in \Omega \times G,\; \textstyle{\Omega=\prod_i \Omega_i,\; G = \prod_j \mathrm{Sym}(B_j)},

где \mathrm{Sym}(B_j) - симетрическая группа конечного множества B_j; случайная величина X и случайная перестановка \pi независимы.

Пусть функция h удовлетворяет следующим условиям:

  • Перестановка любых двух координат случайной величины X, а также транспозиция любых двух элементов перестановки \pi\in G меняют значение h(X,\pi) не более, чем на 2c и c соответственно (для некоторой c\geq 0);
  • Если h(X,\pi)=s, то можно указать не более rs координат (r — положительная константа), таких что h(X',\pi')\geq s для любых пар (X',\pi')\in \Omega, значения которых совпадают с (X,\pi) по этим координатам.

Тогда для любого неотрицательного t выполнено:

P(Z\geq m+t) \leq 2\exp\biggl(-\frac{t^2}{16rc^2(m+t)}\biggr);
P(Z\leq m-t) \leq 2\exp\biggl(-\frac{t^2}{16rc^2m}\biggr),

где m — медиана случайной величины Z.

Доказательство неравенства

Доказательство сформулированного выше утверждения во всей красе использует индуктивный метод, разработанный Талаграном (Michel Talagrand) в ходе его исследования парадокса концентрации меры (concentration of measure). Оно опирается на (уже классической в теории статистического обучения) теореме Талаграна (торема 4.1.1, [1]), связывающей меру подмножества A \subset \Omega^N с расстоянием от случайного элемента x\in\Omega^N до этого подмножества:

\mathsf{P}(A) \mathsf{E}\bigl(\frac{1}{4}f^2(A,x)\bigr)\leq1,

где f(A,x) — расстояние, введенное Талаграном.

Литература

  1. Michel Talagrand Concentration Of Measure And Isoperimetric Inequalities In Product Spaces. — 1995.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%83%D0%B1%D0%BB%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D1%8F:McDiarmid_2002_Concentration_for_Independent_Permutations»
Личные инструменты