Радемахеровская сложность
Материал из MachineLearning.
(уточнение) |
(дополнение) |
||
| Строка 42: | Строка 42: | ||
* [http://en.wikipedia.org/wiki/Rademacher_complexity Rademacher complexity] — Википедия | * [http://en.wikipedia.org/wiki/Rademacher_complexity Rademacher complexity] — Википедия | ||
* [http://en.wikipedia.org/wiki/Hans_Rademacher Ганс Радемахер], немецкий математик | * [http://en.wikipedia.org/wiki/Hans_Rademacher Ганс Радемахер], немецкий математик | ||
| + | * [http://videolectures.net/vladimir_koltchinskii Bounding Excess Risk in Machine Learning] — видеолекция Кольчинского. | ||
== Литература == | == Литература == | ||
Текущая версия
|
Радемахеровская сложность (Rademacher complexity) — мера сложности множества вещественых функций. Интерпретируется как максимальная ковариация функций из данного множества со случайным (радемахеровским) шумом. Чем сложнее множество функций, тем выше шансы найти в нём функцию, похожую на произвольный случайный шум. Применяется в оценках обобщающей способности. Введена в теорию статистического обучения Владимиром Кольчинским и Дмитрием Панченко в 1999 году.
Радемахеровская сложность позволяет получать более точные оценки обобщающей способности, чем ранее применявшиеся меры сложности — размерность Вапника-Червоненкиса, fat-размерность, мощность покрытия.
Определения
Пусть
— произвольное множество,
— множество функций вида
.
Эмпирическая радемахеровская сложность множества функций относительно выборки
есть
где
— независимые случайные величины, принимающие значения
с равной вероятностью и называемые радемахеровскими:
для всех
.
Пусть — вероятностная мера на множестве
.
Радемахеровская сложность множества функций относительно случайных независимых выборок длины
, выбираемых согласно мере
, есть
Связь с другими мерами сложности
Связь с ёмкостью (размерностью Вапника-Червоненкиса):
где — некоторая константа.
Гауссовская сложность
Гауссовская сложность — аналогичная мера сложности, в которой вместо радемахеровских случайных величин берутся независимые гауссовские случайные величины с нулевым математическим ожиданием и единичной дисперсией.
См. также
Ссылки
- Rademacher complexity — Википедия
- Ганс Радемахер, немецкий математик
- Bounding Excess Risk in Machine Learning — видеолекция Кольчинского.
Литература
- 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.
- 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.
- Koltchinskii V. Rademacher penalties and structural risk minimization // IEEE Transactions on Information Theory. — 2001. — Vol. 47, no. 4. — Pp. 1902-1914.
- 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.
- 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.
- Bartlett P., Bousquet O., Mendelson S. Localized rademacher complexities // COLT: 15th Annual Conference on Computational Learning Theory. — Springer, Berlin, 2002. — Pp. 44–58.
- 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.
