Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

<includeonly>{{Статья|PageName = Публикация:McDiarmid 2002 Concentration for Independent Permutations |автор = McDiarmid, C. |название = Concentration for Independent Permutations |журнал = Comb. Probab. Comput. |год = 2002 |издание = |издатель = Cambridge University Press |редактор = |том = 11 |номер = 2 |страницы = 163--178 |url = |url статьи = http://www.machinelearning.ru/wiki/images/3/32/Mcdiarmid2002concentration.pdf |issn = 0963-5483 |язык = english }}</includeonly><noinclude>{{Статья|BibtexKey = mcdiarmid2002concentration |автор = McDiarmid, C. |название = Concentration for Independent Permutations |журнал = Comb. Probab. Comput. |год = 2002 |издание = |издатель = Cambridge University Press |редактор = |том = 11 |номер = 2 |страницы = 163-178 |url = |url статьи = http://www.machinelearning.ru/wiki/images/3/32/Mcdiarmid2002concentration.pdf |issn = 0963-5483 |язык = english }} == Аннотация == В статье представлено неравенство концентрации меры, затрагивающее семейство независимых случайных перестановок. == Реферат == === Основной результат === Вкратце основной результат, представленный в статье, можно сформулировать следующим образом: пусть <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(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/download;jsessionid=836D8E512EF351A85FDF035F2B8EA772?doi=10.1.1.21.1050&rep=rep1&type=pdf |isbn = }} [[Категория:Электронная библиотека|McDiarmid]] </noinclude>

• Шаблон:!
• Шаблон:BibtexAuthors
• Шаблон:Nobr
• Шаблон:Биб.статья
• Шаблон:ВсеАвторы
• Шаблон:Книга
• Шаблон:Переводы
• Шаблон:Статья

Возврат к странице Публикация:McDiarmid 2002 Concentration for Independent Permutations.