Исследование завышенности оценок переобучения пороговых решающих правил

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