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

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

Версия от 10:35, 15 марта 2011; Tolstikhin (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

McDiarmid, C. Concentration for Independent Permutations. — 2002. — Vol. 11. — No. 2. — Pp. 163-178. — ISSN 0963-5483.

Содержание

1 Аннотация
2 Реферат
- 2.1 Основной результат
- 2.2 Доказательство неравенства
3 Литература

Аннотация

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

Реферат

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

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

пусть $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$ до этого подмножества: