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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Доказательство неравенства)
 
(2 промежуточные версии не показаны)
Строка 32: Строка 32:
== Аннотация ==
== Аннотация ==
В статье представлено неравенство концентрации меры, затрагивающее семейство независимых случайных перестановок.
В статье представлено неравенство концентрации меры, затрагивающее семейство независимых случайных перестановок.
 +
 +
== Реферат ==
 +
=== Основной результат ===
 +
Вкратце основной результат, представленный в статье, можно сформулировать следующим образом:
 +
 +
пусть
 +
<tex>
 +
Z = h(Y),\;
 +
Y=(X, \pi)\in \Omega \times G,\;
 +
\textstyle{\Omega=\prod_i \Omega_i,\; G = \prod_j \mathrm{Sym}(B_j)},
 +
</tex>
 +
 +
где <tex>\mathrm{Sym}(B_j)</tex> - симетрическая группа конечного множества <tex>B_j</tex>;
 +
случайная величина <tex>X</tex> и случайная перестановка <tex>\pi</tex> независимы.
 +
 +
Пусть функция <tex>h</tex> удовлетворяет следующим условиям:
 +
* Перестановка любых двух координат случайной величины <tex>X</tex>, а также транспозиция любых двух элементов перестановки <tex>\pi\in G</tex> меняют значение <tex>h(X,\pi)</tex> не более, чем на <tex>2c</tex> и <tex>c</tex> соответственно (для некоторой <tex>c\geq 0</tex>);
 +
* Если <tex>h(X,\pi)=s</tex>, то можно указать не более <tex>rs</tex> координат (<tex>r</tex> — положительная константа), таких что <tex>h(X',\pi')\geq s</tex> для любых пар <tex>(X',\pi')\in \Omega</tex>, значения которых совпадают с <tex>(X,\pi)</tex> по этим координатам.
 +
 +
Тогда для любого неотрицательного <tex>t</tex> выполнено:
 +
::<tex>P(Z\geq m+t) \leq 2\exp\biggl(-\frac{t^2}{16rc^2(m+t)}\biggr);</tex>
 +
::<tex>P(Z\leq m-t) \leq 2\exp\biggl(-\frac{t^2}{16rc^2m}\biggr),</tex>
 +
 +
где <tex>m</tex> — медиана случайной величины <tex>Z</tex>.
 +
 +
=== Доказательство неравенства ===
 +
Доказательство сформулированного выше утверждения во всей красе использует индуктивный метод, разработанный Талаграном ([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> до этого подмножества:
 +
::<tex>\mathsf{P}(A) \mathsf{E}\bigl(\frac{1}{4}f^2(A,x)\bigr)\leq1,</tex>
 +
 +
где <tex>f(A,x)</tex> — расстояние, введенное Талаграном.
 +
 +
== Литература ==
 +
#{{книга
 +
|автор = Michel Talagrand
 +
|заглавие = Concentration Of Measure And Isoperimetric Inequalities In Product Spaces
 +
|издание =
 +
|место =
 +
|издательство =
 +
|год = 1995
 +
|страниц =
 +
|ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1050
 +
|isbn =
 +
}}
 +
[[Категория:Электронная библиотека|McDiarmid]]
[[Категория:Электронная библиотека|McDiarmid]]
</noinclude>
</noinclude>

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

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