On the Effective VC dimensions

Замечательная идея "Эффективной Размерность Вапника — Червоненкиса (или VC-размерность)" основана на гипотезе о том, что зависимость между ошибкой обобщения и числом обучающих примеров может быть выражена формулой, алгебраически сходной с VC-гранью. Эта гипотеза вызывала серезное обсуждение с тех пор, как традиционная VC-грань широко использовалась для оценки ошибки обобщения.

В этой статье описана зависимость алгоритма и данных от оценки емкости. Доверительный интервал может быть получен из разности между ошибкой обучения и ошибкой обобщения. Этот доверительный интервал намного уже, чем традиционная VC-грань.

Дополнитеьлная точность получается простым изменением формулировки: этот доверительный интервал охватывает разницу между ошибкой на обучающем и тестовом множестве, вместо разницы ошибок на обучающем множеством и некоторой гипотетической абсолютной истиной. Такой "трансдуктивный" метод допустим для оценки данных и алгоритма на основе доверительного интервала.

Оригинал статьи: On the Effective VC Dimension (как PDF)