Статистическая теория обучения
Оценки через сжатие
Можно ли ограничить обобщающую ошибку, не считая VC-размерность? Да - через сжатие. Если алгоритм запоминает только k из m примеров, обобщение гарантировано - независимо от размерности пространства признаков.
- **SVM и опорные векторы:** SVM естественно реализует схему сжатия: k опорных векторов определяют гиперплоскость. PAC-граница через k SV часто острее VC-оценки
- **Сжатые сенсорные сети:** Сжатие данных в IoT-устройствах: хранение k ключевых измерений вместо m обеспечивает теоретические гарантии точности реконструкции
- **k-NN с прореживанием:** Coreset-методы для k-NN: хранение k прототипов вместо m обучающих точек с PAC-гарантией через размер coreset
- **Квантизация нейросетей:** Сжатие модели до k значащих весов - аналог схемы сжатия; теорема LW даёт теоретическую основу для гарантий точности
Предварительные знания
- PAC-обучение и VC-размерность
- Агностическое PAC-обучение
- Неравенство Хёффдинга и union bound
Схемы сжатия выборки
Ніко Літтлстоун и Мануэль Уормут в 1986 году доказали: если алгоритм обучения сжимает выборку до k примеров, то обобщающая ошибка не хуже O(k log m / m). В 2016 году Ливни и Менделсон доказали обратное: любой класс с конечной VC-размерностью d имеет схему сжатия размера 2^d. Это закрыло 30-летнюю открытую задачу о связи сжатия и обучаемости.
Что такое схема сжатия размера k?
Littlestone-Warmuth (1986): схема сжатия размера k для класса H - пара (sigma, p), где sigma(S) выбирает k точек из обучающей выборки S, а p(sigma(S)) воспроизводит гипотезу, согласующуюся с S. SVM с k опорными векторами - канонический пример: hypothesis полностью определяется ими.
Связь со сложностью и обобщением
Какую границу обобщения даёт схема сжатия размера k?
Littlestone-Warmuth: если класс H имеет схему сжатия размера k и алгоритм возвращает h, согласующуюся с обучающей выборкой, то с вероятностью 1-delta: R(h) <= (1/n)[k log(n/k) + log(C(n, k)/delta)]. Связь с VC: VC(H) <= O(k log n).
Алгоритмы: SVM, boosting и Sauer-Shelah
Схема сжатия как конспект экзаменатора - Экзаменатор (алгоритм) изучил m задач (обучающая выборка). Схема сжатия: он записал в шпаргалку только k ключевых задач, по которым восстанавливает все правила решения. Чем меньше шпаргалка - тем меньше переобучение. PAC-граница через сжатие независима от размерности пространства признаков: важно только, сколько примеров нужно алгоритму для полной реконструкции.
Какие алгоритмы используют схемы сжатия в чистом виде?
SVM: гипотеза полностью определяется опорными векторами (часто k << n). Boosting: combined classifier sum h_t зависит только от выбранных weak learners. 1-NN: каждая точка определяет область Voronoi. Эти схемы дают конкретные границы обобщения через число "критических" примеров.
Связи с другими темами
Схемы сжатия связывают классическую PAC-теорию с алгоритмами сжатия данных, SVM и современными методами сжатия нейросетей.
- VC-теория — Связанная тема
- SVM — Связанная тема
- Информационно-теоретическое обучение — Связанная тема
- Сжатие нейросетей — Связанная тема
Итоги
- Схема сжатия (κ,ρ) размера k: κ выбирает k примеров, ρ восстанавливает гипотезу с нулевой обучающей ошибкой
- PAC-граница: err(h) не хуже O((k·log(m/k) + log(1/δ)) / m) с вероятностью 1-δ
- Граница зависит от k, а не от размерности пространства признаков
- SVM - схема сжатия: k опорных векторов полностью определяют решение
- Теорема Livni et al. 2016: конечная VC эквивалентна конечному сжатию - закрыта 30-летняя открытая задача
Что гарантирует схема сжатия размера k?
Теорема Літтлстоуна-Уормута. Граница зависит от k (размера сжатия), а не от размерности признакового пространства.