Комбинаторные оценки переобучения пороговых решающих правил

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