Комбинаторная теория переобучения: оценка расслоения-связности | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Несмотря на коронавирус, электронный вариант журнала выйдет 6 июня.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №19 (309) май 2020 г.

Дата публикации: 09.05.2020

Статья просмотрена: 4 раза

Библиографическое описание:

Акбаров, Б. Х. Комбинаторная теория переобучения: оценка расслоения-связности / Б. Х. Акбаров, У. М. Негматов. — Текст : непосредственный // Молодой ученый. — 2020. — № 19 (309). — С. 104-106. — URL: https://moluch.ru/archive/309/69693/ (дата обращения: 29.05.2020).



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

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

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. Комбинаторный множитель есть верхняя оценка вероятности получить алгоритм в результате обучения. Величина экспоненциально убывает с ростом не оптимальности и связности . Это указывает на пару важных для практики вывода.

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

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

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

.

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

Литература:

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


Похожие статьи

Анализ эффективности алгоритмов сортировки и вcтроенных...

В данной статье показана значительная роль проведения анализа работы алгоритмов сортировки на массивах данных различной размерности. Рассмотрены актуальные алгоритмы и стандартные реализации сортировки в языке программирования Java.

Особенности оценки качества и оптимизации алгоритмов...

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

Рис. 1. Классификация показателей качества алгоритмов шифрования.

Использование обобщенных параметров группирующихся...

Коэффициенты связности представлены в виде: ; . Оценка качества канала по сигналам стираний для модели Пуртова, учитывающего

Модель источника ошибок и стираний может быть использована для оценки обнаруживаемой способности кодов и выбора оптимальной...

Один способ генерации графа | Статья в журнале...

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра

Количество компонент связности растет тем медленней, чем больше компонент на шаге выбирают одновременное связывание.

Регулярные алгоритмы устойчивого оценивания состояния...

где — вектор состояния системы размерности n; — вектор управления размерности l; — вектор наблюдения

Это обстоятельство обусловливает необходимость либо оценки неизвестных статистических характеристик

Алгоритм оценки состояния линейных динамических систем.

Алгоритм статистических испытаний для определения...

Рассмотрим подробно работу алгоритма статистических испытаний по методу Монте-Карло.

Для графов существует несколько способов представления исходных данных в машинной памяти.

При оценке связности сети в качестве исходных данных алгоритм Монте-Карло...

Алгоритмы устойчивого оценивания параметров динамических...

Приводятся алгоритмы устойчиво оценивания параметров динамических объектов управления на основе методов регуляризации. The firm estimation algorithms of the dynamic object control parameters are given on the basic of regularization methods.

Анализ методов распознавания образов | Статья в журнале...

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

Сравнение методов оценки тональности текста | Статья в журнале...

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

Ошибка — это доля неправильных решений классификатора. Решения классификатора сравнивают с решениями экспертов...

Похожие статьи

Анализ эффективности алгоритмов сортировки и вcтроенных...

В данной статье показана значительная роль проведения анализа работы алгоритмов сортировки на массивах данных различной размерности. Рассмотрены актуальные алгоритмы и стандартные реализации сортировки в языке программирования Java.

Особенности оценки качества и оптимизации алгоритмов...

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

Рис. 1. Классификация показателей качества алгоритмов шифрования.

Использование обобщенных параметров группирующихся...

Коэффициенты связности представлены в виде: ; . Оценка качества канала по сигналам стираний для модели Пуртова, учитывающего

Модель источника ошибок и стираний может быть использована для оценки обнаруживаемой способности кодов и выбора оптимальной...

Один способ генерации графа | Статья в журнале...

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра

Количество компонент связности растет тем медленней, чем больше компонент на шаге выбирают одновременное связывание.

Регулярные алгоритмы устойчивого оценивания состояния...

где — вектор состояния системы размерности n; — вектор управления размерности l; — вектор наблюдения

Это обстоятельство обусловливает необходимость либо оценки неизвестных статистических характеристик

Алгоритм оценки состояния линейных динамических систем.

Алгоритм статистических испытаний для определения...

Рассмотрим подробно работу алгоритма статистических испытаний по методу Монте-Карло.

Для графов существует несколько способов представления исходных данных в машинной памяти.

При оценке связности сети в качестве исходных данных алгоритм Монте-Карло...

Алгоритмы устойчивого оценивания параметров динамических...

Приводятся алгоритмы устойчиво оценивания параметров динамических объектов управления на основе методов регуляризации. The firm estimation algorithms of the dynamic object control parameters are given on the basic of regularization methods.

Анализ методов распознавания образов | Статья в журнале...

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

Сравнение методов оценки тональности текста | Статья в журнале...

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

Ошибка — это доля неправильных решений классификатора. Решения классификатора сравнивают с решениями экспертов...

Задать вопрос