Статья содержит краткий обзор теории расслоения-связности комбинаторной теории переобучения.

Ключевые слова: ИИ, переобучения, оценка, обобщающая способность, комбинаторная теория.

The article contains a brief review of the bundle-connected theory of the combinatorial theory of overfitting.

Keywords: AI, overfitting, assessment, generalization ability, combinatorial theory.

В теории обучения одной из главных проблем является оценка вероятностей ошибок исходя из семейства алгоритмов, обучающей выборки и метода обучения. Уменьшение количества оценок позволяет создавать алгоритмы, обобщающую способность, которых можно контролировать. В большинстве случаев решения — не оптимальны. При комбинаторном подходе вместо вероятности ошибки оценивается средняя ошибка на неизвестной контрольной выборке, что не меняет сути оценок [3].

Постановка задачи, определения и обозначения приведены в [3].

Оценки вероятности переобучения

Будем полагать, что все алгоритмы из A имеют попарно различные векторы ошибок. Введём на A естественное отношение порядка:

и

Для постройки отношений между алгоритмами a и b используем метрику. В качестве функции расстояния между векторами ошибок используем хэммингово расстояние, и обозначаем через .

Если и при этом то будем говорить, что предшествует и записывать . Очевидно, что .

Графом расслоения–связности множества алгоритмов A будем называть направленный граф с множеством рёбер

Граф расслоения–связности является дольным, много-дольным, доли соответствуют слоям алгоритмов рёбрами могут соединяться только алгоритмы соседних слоёв. Каждому ребру соответствует единственный объект, такой, что и .

Верхней (нижней) связностью алгоритма будем называть число рёбер графа, исходящих из (входящих в) вершину , соответственно:

Связность есть реализуемое семейством число способов изменить алгоритм a так, чтобы он стал делать на одну ошибку больше (или меньше). Связность можно интерпретировать как число степеней свободы семейства в локальной окрестности алгоритма . Для семейства линейных классификаторов значение связности концентрируется вокруг значения размерности пространства [4].

Не оптимальностью алгоритма будем называть число объектов , на которых алгоритм ошибается, при том, что существует алгоритм , , не ошибающийся на

.

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

В общем случае . Равенство достигается на всех алгоритмах двух самых нижних слоёв. Равенство достигается в случае, когда существует корректный алгоритм .

Оценка расслоения–связности: Теорема.

Определим для всех функцию гипергеометрического распределения:

Пусть метод минимизации эмпирического риска, векторы ошибок всех алгоритмов из попарно различны. Тогда для любого .

,

где верхняя связность и не оптимальность алгоритма a соответственно,

Рассмотрим основные свойства данной оценки.

1. Комбинаторный множитель есть верхняя оценка вероятности получить алгоритм в результате обучения. Величина экспоненциально убывает с ростом не оптимальности и связности . Это указывает на пару важных для практики вывода.

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

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

2. Если пренебречь расслоением и связностью, положив для каждого , то получится оценка Вапника–Червоненкиса (при ):

.

3. Оценка расслоения–связности является достижимой. Она обращается в равенство в случае специальных модельных семейств алгоритмов монотонных цепей и многомерных сетей.

Литература:

1. Игнатьев Н. А. Обобщенные оценки и локальные метрики объектов в интеллектуальном анализе данных. Ташкент: Университет, 2014. C. 68–72.
2. Мадрахимов III.Ф., Саидов Д. Ю. Устойчивость объектов классов и группировка признаков // Проблемы вычислительной и прикладной математики. 2016. № 3 (5). С. 50–55.
3. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупа-нова. М.: Физматлит, 2004. Т. 13. С. 5–36.
4. Кочедыков Д. А. Структуры сходства в семействах алгоритмов классификации и оценки обобщающей
5. Воронцов К. В. Комбинаторная теория переобучения: результаты, приложения и открытые проблемы // Всероссийская конференция «Математические методы распознавания образов». Петрозаводск, 2011 г. C.:2–7.