Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Обучающую выборку для регрессии с шумными метками удалось сократить до объёма, который не зависит от числа примеров, сохранив среднюю квадратичную ошибку в пределах α от лучшей функции выбранного класса. В нерецензированном препринте Guangjian Zhang, где все численные оценки получены самим автором, размер схемы ограничен O(fat(F, cα) · log³(2/α)); прежним общим конструкциям требовался дополнительный множитель, который в худшем случае мог расти экспоненциально. Это улучшает теоретическую границу хранения, но пока не даёт готового алгоритма для продукта.
Сжатие выборки оставляет часть исходных размеченных примеров и служебные биты, по которым затем восстанавливает функцию. Главная величина в оценке — масштабная размерность (fat-shattering dimension): она показывает, насколько сложные разделения способен задавать класс функций при выбранной точности. Новая граница почти линейно зависит от этой размерности и не зависит от исходного объёма выборки.
В прежних схемах восстановленная функция должна была приближать цель на каждом примере. Для этого ансамбль разрежали, а доказательство добавляло двойственную масштабную размерность. Новая схема контролирует только основную долю точек: поскольку значения ограничены от нуля до единицы, оставшаяся доля вносит ограниченный вклад в среднюю ошибку. Число раундов усиления модели поэтому зависит от α, а не от размера выборки.
Для работы с произвольными шумными метками схема сначала выбирает функцию с ошибкой, близкой к минимальной. Её значения на сохранённых точках квантуются и записываются в служебные биты, после чего восстановитель собирает взвешенную медиану нескольких функций. Так схема обходится исходными примерами, хотя фактически учится по синтетическим целевым значениям.
Теорема охватывает конечные выборки с метками и предсказаниями в диапазоне от нуля до единицы и требует положительной допустимой ошибки α. Конструкция информационно-теоретическая: она использует поиск почти лучшей функции и операции выбора, которые не обязаны вычисляться алгоритмом. Константы также велики — даже при α, равной единице, доказанная настройка требует не менее 509 раундов. Для разработки продукта результат пока меняет оценку принципиально возможного объёма хранения, а не выбор реализуемой архитектуры.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
