Радемахеровская сложность

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

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

Содержание

Радемахеровская сложность (Rademacher complexity) — мера сложности множества вещественых функций. Интерпретируется как максимальная ковариация функций из данного множества со случайным (радемахеровским) шумом. Чем сложнее множество функций, тем выше шансы найти в нём функцию, похожую на произвольный случайный шум. Применяется в оценках обобщающей способности. Введена в теорию статистического обучения Владимиром Кольчинским и Дмитрием Панченко в 1999 году.

Радемахеровская сложность позволяет получать более точные оценки обобщающей способности, чем ранее применявшиеся меры сложности — размерность Вапника-Червоненкиса, fat-размерность, мощность покрытия.

Определения

Пусть Z — произвольное множество, \mathcal{F} — множество функций вида f:\: Z \to \mathbb{R}.

Эмпирическая радемахеровская сложность множества функций \mathcal{F} относительно выборки S=(z_1, z_2, \dots, z_m) \in Z^m есть

\widehat \mathcal{R}(\mathcal{F},S) = \frac{1}{m} \sup_{f \in \mathcal{F}} \left| \sum_{i=1}^m \sigma_i f(z_i)\right|,

где \sigma_i — независимые случайные величины, принимающие значения -1,+1 с равной вероятностью и называемые радемахеровскими:

\Pr(\sigma_i = +1) = \Pr(\sigma_i = -1) = 1/2 для всех i=1,2,\dots,m.

Пусть P — вероятностная мера на множестве Z.

Радемахеровская сложность множества функций \mathcal{F} относительно случайных независимых выборок длины m, выбираемых согласно мере P, есть

\mathcal{R}(\mathcal{F},m) = \mathbb{E}_S \left[ \widehat \mathcal{R}(\mathcal{F},S) \right],

Связь с другими мерами сложности

Связь с ёмкостью (размерностью Вапника-Червоненкиса):

\mathcal{R}(\mathcal{F},m) \leq C\sqrt{\frac{1}{m}\mathrm{VCdim}(\mathcal{F})},

где C — некоторая константа.

Гауссовская сложность

Гауссовская сложность — аналогичная мера сложности, в которой вместо радемахеровских случайных величин берутся независимые гауссовские случайные величины с нулевым математическим ожиданием и единичной дисперсией.

См. также

Ссылки

Литература

  1. Boucheron S., Bousquet O., Lugosi G. Theory of classification: A survey of some recent advances // ESAIM: Probability and Statistics. — 2005. — no. 9. — Pp. 323–375.
  2. Koltchinskii V., Panchenko D. Rademacher processes and bounding the risk of function learning // High Dimensional Probability, II / Ed. by D. E. Gine, J.Wellner. — Birkhauser, 1999. — Pp. 443–457.
  3. Koltchinskii V. Rademacher penalties and structural risk minimization // IEEE Transactions on Information Theory. — 2001. — Vol. 47, no. 4. — Pp. 1902-1914.
  4. Koltchinskii V., Panchenko D. Empirical margin distributions and bounding the generalization error of combined classifiers // The Annals of Statistics. — 2002. — Vol. 30, no. 1. — Pp. 1–50.
  5. Bartlett P. L., Mendelson S. Rademacher and Gaussian complexities: Risk bounds and structural results // COLT: 14th Annual Conference on Computational Learning Theory. — Vol. 2111. — Springer, Berlin, 2001. — Pp. 224–240.
  6. Bartlett P., Bousquet O., Mendelson S. Localized rademacher complexities // COLT: 15th Annual Conference on Computational Learning Theory. — Springer, Berlin, 2002. — Pp. 44–58.
  7. Bartlett P. L., Mendelson S., Philips P. Local complexities for empirical risk minimization // COLT: 17th Annual Conference on Learning Theory / Ed. by J. Shawe-Taylor, Y. Singer. — Springer-Verlag, 2004. — Pp. 270–284.
Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B4%D0%B5%D0%BC%D0%B0%D1%85%D0%B5%D1%80%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C»
Личные инструменты