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

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

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

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.
Личные инструменты