Автоматика и телемеханика, № 5, 2021

Интеллектуальные системы управления,

анализ данных

(Вычислительный центр им. А.А. Дородницына ФИЦ ИУ РАН, Москва),

К. В. ВОРОНЦОВ, д-р физ.-мат. наук (vokov@forecsys.ru)

(Московский физико-технический институт)

ИССЛЕДОВАНИЕ ЗАВЫШЕННОСТИ ОЦЕНОК ПЕРЕОБУЧЕНИЯ

ПОРОГОВЫХ РЕШАЮЩИХ ПРАВИЛ¹

Данная статья посвящена проблеме вычисления точной верхней оцен-

ки функционалов обобщающей способности семейства одномерных по-

роговых решающих правил. Исследуется алгоритм, решающий постав-

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

по объему обучающей выборки. Доказывается теорема для вычисления

оценки функционала ожидаемой переобученности семейства и оценки ча-

стоты ошибок метода минимизации эмпирического риска на контрольной

выборке. Проводится сравнение точных оценок, вычисленных с помощью

теоремы, с известными ранее быстро вычислимыми верхними оценками с

целью оценить порядки их завышенности и выявить те оценки, которые

можно было бы использовать в реальных задачах.

Ключевые слова: пороговый классификатор, обобщающая способность,

комбинаторная теория, вероятность переобучения, полный скользящий

контроль, Радемахеровская сложность.

DOI: 10.31857/S000523102105010X

1. Введение

При решении задачи обучения на основании обучающей выборки объек-

тов, часто называемой обучением по прецедентам, строится алгоритм, восста-

навливающий зависимость выходных переменных от входных на объектах из

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

принимает бинарные значения, а алгоритмы называются классификаторами.

Для успешного применения построенного классификатора он должен иметь

высокую обобщающую способность, т.е. хорошо работать на произвольных

объектах, не обязательно входящих в обучение. Если же качество классифи-

катора на независимой выборке, называемой контрольной, оказывается зна-

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

обучение. В качестве характеристик обобщающей способности используются

функционалы вероятности переобучения и полного скользящего контроля [1].

¹ Исследование выполнено при финансовой поддержке гранта Правительства РФ для

государственной поддержки научных исследований, проводимых под руководством веду-

щих ученых (соглашение № 075-15-2019-1926).

151

Получение оценок обобщающей способности семейства классификаторов

на основе информации об обучающей выборке и о структуре семейства с пуб-

ликации [2] остается одной из основных задач теории статистического обуче-

ния. В конце 70-х годов XX века советские ученые В.Н. Вапник и А.Я. Чер-

воненкис сформулировали основные статистические проблемы обучения в

терминах проблемы минимизации среднего риска, т.е. вероятности ошибки

классификатора на новом объекте, и предложили методы оценки среднего

риска по эмпирическим данным [3, 4]. Вапник и Червоненкис получили рав-

номерные по семействам классификаторов оценки, связывающие вероятность

уклонения среднего риска от эмпирического с длиной обучающей выборки и

сложностью семейства, над которыми минимизируется средний риск. Этот

фундаментальный результат активно используется и сегодня.

Однако оценки Вапника-Червоненкиса являются завышенными. Экспери-

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

6-12 порядков [5], что может приводить к неоптимальному выбору структур-

ных параметров [6-8]. Кроме того, завышенные оценки не дают возможности

исследовать явление переобучения, оценивать и контролировать его значе-

ния при решении реальных задач. В [5] исследуются причины завышенности

оценок, из которых основной является независимость оценок от конкретной

выборки. Оценка Вапника-Червоненкиса универсальна и, следовательно, яв-

ляется оценкой худшего случая.

Теория статистического обучения продолжает активно развиваться, по-

следователи теории занимаются повышением точности равномерных оце-

нок с учетом особенностей данных и конкретных алгоритмов классифика-

ции [9, 10]. Среди плодотворных подходов можно выделить оценки, адапти-

рующиеся к данным и использующие понятие Радемахеровской сложности,

предложенной в 1999 г. В. Колчинским [11].

В комбинаторной теории [12], предложенной К.В. Воронцовым, для обоб-

щающей способности была получена оценка расслоения-связности [13], учи-

тывающая особенности способа построения классификатора по обучающей

выборке, а также локальные свойства семейства классификаторов - эф-

фекты расслоения и связности [14]. В [15] получены условия, при которых

оценка расслоения-связности является точной. Имеются уточнения данной

оценки за счет учета попарного взаимодействия классификаторов [16] и за

счет учета сходства классификаторов [17], но оценки по-прежнему остаются

завышенными.

В комбинаторной теории вероятностью переобучения называют долю раз-

биений конечного множества объектов на обучающую и контрольную вы-

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

определение ранее появлялось в [18] для частного случая контрольной вы-

борки, состоящей из одного объекта.

Точность эмпирических оценок функционалов обобщающей способности,

полученных методом Монте-Карло, зависит от числа случайных разбиений.

Вычисление точных оценок по определению требует экспоненциального по

общему количеству объектов перебора всех возможных разбиений. Но для

некоторых модельных семейств классификаторов удается аналитически вы-

152

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

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

и унимодальных цепей [19] и многомерных сетей [20], хэмминговых шаров и

некоторых их разреженных подмножеств [21]. Разработан теоретико-группо-

вой подход [22], который позволяет получать точные оценки для семейств с

произвольными симметриями.

В [23] предложен способ аппроксимации вероятности переобучения стан-

дартных методов классификации (нейронных сетей, решающих деревьев,

ближайшего соседа) на реальных задачах с помощью монотонных сетей под-

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

критерия отбора признаков при построении элементарных конъюнкций в ло-

гических алгоритмах классификации [13] или в качестве критерия ветвления

в решающих деревьях [20].

В данной статье, являющейся продолжением публикации [24], рассматри-

вается задача построения точных верхних оценок обобщающей способности

одномерных пороговых решающих правил.

Практический интерес связан с тем, что данная задача возникает при по-

строении алгоритмов классификации, в частности в решающих деревьях, ло-

гических закономерностях [25], алгоритмах вычисления оценок [26], а также

при построении линейных классификаторов методом покоординатной опти-

мизации.

Теоретический интерес связан с тем, что в рамках комбинаторного подхо-

да до сих пор не удавалось получать точные оценки обобщающей способности

для данного семейства. Точные оценки были известны только для частных

случаев задач классификации, где классы были линейно разделимы [19]. Так-

же для частного случая, когда признак принимает попарно различные зна-

чения на объектах, был известен алгоритм вычисления верхней и нижней

оценок обобщающей способности [27]. Однако завышенность верхней оценки

остается неизученной.

В [24] был предложен алгоритм вычисления точных оценок вероятности

переобучения и полного скользящего контроля одномерных пороговых ре-

шающих правил, полиномиальный по общему количеству объектов. Алго-

ритм допускает наличие связок во множестве значений признака и различные

методы обучения.

В данной статье демонстрируется универсальность алгоритма по отноше-

нию к вычисляемым функционалам обобщающей способности. Доказывается

теорема для вычисления оценки функционала ожидаемой переобученности

порогового классификатора, т.е. разности доли ошибочно классифицирован-

ных объектов на обучающей и контрольной выборках.

Недостатком алгоритма является его большая вычислительная сложность.

В данной статье проводится сравнение точных оценок, вычисленных с помо-

щью алгоритма, с известными ранее быстро вычислимыми верхними оценка-

ми, с целью оценить порядки их завышенности и выявить те оценки, которые

можно было бы использовать в реальных задачах.

153

2. Основные определения

Пусть задано конечное множество X = {x₁, . . . , x_L}, элементы которого на-

зываются объектами, и конечное множество A, элементы которого называ-

ются классификаторами. Множество A называется семейством классифика-

торов.

Пусть задана функция I : A × X → {0, 1}, называемая индикатором ошиб-

ки. Если I(a, x) = 1, то говорят, что на элементе x классификатор a допус-

кает ошибку. Если I(a, x) = 0, то говорят, что классификатор не ошибается

на данном элементе.

Предполагается, что каждому классификатору a ∈ A взаимно однозначно

соответствует его вектор ошибок (I(a, x_i))^Li=1, т.е. два классификатора с оди-

наковыми векторами ошибок отождествляются. Далее через a будет обозна-

чаться как сам классификатор, так и его вектор ошибок.

Числом ошибок классификатора a на выборке X ⊂ X называется величина

∑

n(a, X) =

I(a, x).

x∈X

Частотой ошибок классификатора a на выборке X ⊂ X называется вели-

чина

n(a, X)

ν(a, X) =

|X|

где через |X| обозначен объем выборки X.

Пусть множество X разбито на две выборки X иX = X\X. Выборка X на-

зывается обучающей, выборкаX - контрольной. Переобученностью класси-

фикатора a на двух выборках X иX = X\X называется величина

δ(a, X) = ν(a,X) - ν(a, X).

Методом обучения называется отображение µ: 2^X → A, которое обучаю-

щей выборке ставит в соответствие классификатор из заданного семейства.

Пусть [X]^ℓ - множество всех выборок X ⊂ X без возвращения объема ℓ < L.

Введем на [X]^ℓ равномерное распределение

P(X) =

C^ℓ

Для фиксированного метода обучения µ, семейства классификато-

ров A, множества X и объема обучающей выборки ℓ вероятностью пере-

обучения метода µ называется функционал

∑

Q_ε(µ,A,X,ℓ) = P[δ(µX,X) ≥ ε] =

[δ(µX, X) ≥ ε].

C^ℓ

L X∈[X]^ℓ

154

Здесь и далее квадратные скобки будут использоваться для преобразо-

вания логического условия в числовое значение по правилу [истина] = 1,

[ложь] = 0.

Полным скользящим контролем называется функционал, равный мате-

матическому ожиданию числа ошибок метода обучения на контрольной вы-

борке:

∑

CCV (µ,A,X,ℓ) = Eν(µX, X) =

ν(µX,X).

C^ℓ

L X∈[X]^ℓ

Ожидаемой переобученностью называется функционал, равный матема-

тическому ожиданию переобученности классификатора, выбранного методом

обучения:

∑

EOF(µ,A,X,ℓ) = Eδ(µX,X) =

ν(µX,X) - ν(µX, X).

C^ℓ

L X∈[X]^ℓ

Для краткости параметры, от которых зависят данные величины, опуска-

ются.

В данной статье рассматривается метод обучения, минимизирующий эм-

пирический риск (МЭР)

µX ∈ M(X) = Argmin n(a,X),

a∈A

и метод обучения, максимизирующий переобученность (МП)

µX = arg max δ(a,X).

a∈A

Для получения верхних оценок Q_ε, CCV и EOF вводится понятие метода

пессимистичной минимизации эмпирического риска (ПМЭР)

µX = arg max n(a,X).

a∈M(X)

Это метод МЭР, который в случае неоднозначности среди M(X) выбирает

классификатор с наибольшим числом ошибок на множестве X [19].

3. Постановка задачи

Пусть дано семейство A = {a₀, . . . , a_P }. Рассмотрим множество объектов,

по которым различаются соседние классификаторы:

(1)

Gp = {x ∈ X | I(ap, x) = I(ap+1,x)}, p = 0,... ,P - 1.

Определение 1. Прямой последовательностью называется семейство

классификаторов, обладающее свойством

Gp ∩ Gd = ∅

∀ p,d = 0,... ,P - 1.

155

x₀

x₁

x₂

x₃

f(x)

a₀

a₁

a₂

a₃

a₄

n(a_p, X)

4 p

Рис. 1. Пример семейства одномерных пороговых решающих правил. По оси

отложены объекты x ∈ X, упорядоченные по значениям признака f(x). Объек-

ты из разных классов обозначены точками • и ◦. Пороги расположены между

соседними объектами, каждому значению порога соответствует свой класси-

фикатор. Ниже оси изображен график числа ошибок классификаторов.

Определение 2. Прямая последовательность называется прямой це-

пью, если каждая пара соседних классификаторов различается по одному

объекту

|G_p| = 1, p = 0, . . . , P - 1.

В [24] доказано, что прямые последовательности порождаются семей-

ством одномерных пороговых решающих правил a_θ(x) = [f(x) ≥ θ] над при-

знаком f, полученных варьированием порога θ вдоль значений признака.

В случае когда числовой признак принимает попарно различные значения

на объектах множества X, семейство является прямой цепью.

На рис. 1 изображен пример данного семейства. По горизонтальной оси

отложены объекты множества X, упорядоченные по значениям признака f.

Объекты класса 0 обозначены точками ◦, объекты класса 1 точками •. По-

роги θ расположены между соседними объектами, каждому порогу соответ-

ствует свой классификатор. Объекты, расположенные правее порога, клас-

сификатор относит к классу 1. Ниже оси изображен график числа ошибок

классификаторов. Например, число ошибок классификтора a₂ равно 2: клас-

сификатор ошибочно относит объект x₀ к классу 0, а объект x₂ - к классу 1.

Покажем, что переобучение цепи зависит от геометрической структуры

классов.

Эмпирической оценкой функции φ(X,X), не зависящей от порядка эле-

ментов в выборках X и

X, называется величинаÊφ(X,X), полученная ме-

тодом Монте-Карло путем усреднения по некоторому случайному подмноже-

ству выборок N ⊂ [X]^l

∑

Êφ(X,X) =

φ(X,X).

|N|

X∈N

На рис. 2 изображены прямые цепи различной формы. График частоты

ошибок классификаторов на полном множестве изображен линией с точкой.

Цепи упорядочены по возрастанию количества классификаторов в нижних

156

0,325

0,300

0,275

0,250

0,225

0,325

0,300

0,275

0,250

0,225

20 40 60

80 100

20 40 60

80 100 0

20 40 60

80 100

20 40 60 80 100

Рис. 2. Сравнение переобучения прямых цепей различной формы. По го-

ризонтали отложены номера p классификаторов цепи. Условия эксперимен-

та: L = 200, ℓ = 150, ε = 0,05. Минимальная частота ошибок равна 0,245.

слоях, где слои определяются по числу ошибок. Пилообразные участки соот-

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

с другом. Чем чаще пила, тем выше уровень шума. Рассматриваются слу-

чаи, когда пилообразные участки расположены вдали от границы классов

(верхний ряд) и вблизи от границы (нижний ряд).

Горизонтальными линиями показаны эмпирические оценки частоты оши-

бок метода ПМЭР, вычисленные методом Монте-Карло по 10⁵ разбиениям.

Пунктирной линией изображена оценка на обучающей выборкеÊν(µX, X) и

сплошной линией - оценка на контрольной выборкеÊν(µX,X). Чем больше

расстояние между ними, равноеÊδ(µX, X), тем сильнее переобучается семей-

ство.

Данный эксперимент показывает, что одни семейства переобучаются зна-

чительно сильнее, чем другие: переобучение тем выше, чем больше класси-

фикаторов находится в нижних слоях семейства и чем более они различны.

Вследствие этого ставится следующая задача: для прямой последователь-

ности A общего вида, методов обучения ПМЭР и МП вычислить точные зна-

чения вероятности переобучения, полного скользящего контроля и ожидае-

мой переобученности.

4. Обзор известных оценок вероятности переобучения

При построении оценок используется понятие гипергеометрической функ-

ции распределения

min{⌊s⌋,ℓ,m}∑

H^l,mL(s) =

C^imC^ℓ-iL-m,

C^l

i=0

157

где через ⌊x⌋ обозначена целая часть x, т.е. наибольшее целое число, не пре-

восходящее x. Гипергеометрическая функция распределения H^ℓ,mL(s) для дан-

ного множества X мощности L и выборки X₀ ⊂ X объема m равна доле вы-

борок множества X объема ℓ, содержащих не более s элементов из X₀. Пред-

полагается Cⁱⁿ = 0 при невыполнении условия 0 ≤ i ≤ n.

4.1. Оценка Вапника-Червоненкиса

Верхняя оценка вероятности переобучения, полученная Вапником и Чер-

воненкисом, является функцией от мощности множества объектов и слож-

ности семейства алгоритмов. Мерой сложности на заданном множестве объ-

ектов является коэффициент разнообразия, определяемый как число попар-

но различных бинарных векторов ошибок, индуцируемых классификаторами

семейства. В комбинаторной теории коэффициент разнообразия равен мощ-

ности семейства.

Теорема 1 (см. [2]). Для любого метода обучения, множества X, семей-

ства классификаторов A, объема ℓ обучающей выборки и порога ε ∈ (0,1)

(

)

ℓ

Q_ε ≤ |A| max

H^ℓ,n

(n - ε(L - ℓ))

n=1,...,L

^L L

4.2. Оценка расслоения-связности

В комбинаторном подходе учитываются геометрические свойства булевых

векторов ошибок классификаторов - расслоение и связность.

Под расслоением семейства понимается распределение классификаторов

по слоям ошибок. Слоем называется множество классификаторов, допускаю-

щих на множестве X равное число ошибок. Чем меньше ошибок допускает

классификатор, тем ниже его слой.

Связность предполагает, что для каждого классификатора в семействе

найдется множество похожих классификаторов, отличающихся от него толь-

ко на одном объекте выборки.

Пусть дано семейство классификаторов A = {a₀, . . . , a_P } с известными

векторами ошибок на множестве X. На множестве классификаторов, как век-

торов ошибок, существует отношение лексикографического порядка ≤. Гово-

рят, что классификатор a предшествует b и записывают a ≺ b, если a ≤ b

и расстояние Хемминга между ними равно 1.

Для каждого a ∈ A через u, q и n будут обозначаться:

u = |{b ∈ A|a ≺ b}|,

q = |{x ∈ X|I(a,x) = 1, ∃b < a : I(b,x) = 0}|,

n = n(a,X).

Теорема 2 (см. [13]). Для произвольного множества X, семейства клас-

сификаторов A, метода обучения ПМЭР, объема ℓ обучающей выборки и по-

158

рога ε ∈ (0,1) справедливы оценки

(

)

∑

C^l-uL-u-q

ℓ

Q_ε ≤

H^ℓ-u,n-q

(n - ε(L - ℓ))

C^ℓL

L-u-q L

a∈A

(2)

(

)

∑

C^l-uL-u-q

(n - q)(ℓ - u)

CCV ≤

C^ℓ

L-ℓ

(L - u - q)(L - ℓ)

a∈A

В [16] оценка была улучшена за счет более тонкого анализа эффекта связ-

ности.

Теорема 3 (см. [16]). Пусть S - множество истоков семейства A, т.е.

множество классификаторов s таких, что нет классификаторов a ≺ s.

Тогда верна оценка



∑

Ci|Bps|CL

−u-|Bps|

(3) Q_ε ≤

min

s∈S 

C^ℓ

p=0

i=0

)}

(ℓ

×Hℓ-u-i,n-|Bps|

(n - ε(L - ℓ)) - i)

L-u-|Bps|

где

A_ij = {x ∈ X |I(a_i,x) = 0, I(a_j,x) = 1} ,

B_ij = {x ∈ X |I(a_i,x) = 1, I(a_j,x) = 0} .

5. Обзор известных оценок полного скользящего контроля

В комбинаторной теории наряду с оценкой расслоения-связности (2) для

частного случая семейства имеются оценки Гуза.

5.1. Оценки Гуза

Рассмотрим семейство одномерных пороговых решающих правил над чис-

ловым признаком, принимающим попарно различные значения на объектах

множества X. Пусть порог пробегает все возможные значения. Для данно-

го семейства в [27] был предложен полиномиальный алгоритм вычисления

верхней и нижней оценок полного скользящего контроля.

Теорема 4 (см. [27]). Для произвольного множества X, семейства клас-

сификаторов A, метода обучения ПМЭР, объема ℓ обучающей выборки спра-

ведливы верхняя и нижняя оценки полного скользящего контроля:

∑

|E¹(i)| ≤ CCV ≤ 1 -

|E⁰(i)|,

L-ℓC^ℓ

L i=1

159

где для каждого i множества E⁰(i) безошибочных выборок и E¹(i) ошибоч-

ных выборок определены как

{

}

E⁰(i) =

X |x_i∈ X, ∀µX∈M(X) I(µX,x_i) = 0

⊆ [X]^ℓ,

{

}

E¹(i) =

X |x_i∈ X, ∀µX∈M(X) I(µX,x_i) = 1

⊆ [X]^ℓ.

6. Переобучение прямой последовательности классификаторов

Пусть дана прямая последовательность A = {a₀, . . . , a_P }. Определим мно-

жество

(4)

D = {x ∈ X|∃a,a^′ ∈ A: I(a,x) = I(a^′

,x)},

объекты которого будем называть ребрами последовательности A.

Объекты множества N = X \ D назовем нейтральными. На множестве N

классификаторы семейства допускают одинаковое число ошибок

(5)

m = n(a,N)

∀a ∈ A.

Рассмотрим классификатор a_p. Определим величину D_p(t, e), равную чис-

лу разбиений множества D, таких что a_p является результатом обучения:

{



}

D_p(t,e) = #

(X ∩ D,X ∩ D)

µX=ap, t = |X ∩ D|, e = n(a_p,X ∩ D)

Такие разбиения назовем допустимыми.

Ранее в [24] были доказаны теоремы о выражении функционалов веро-

ятности переобучения и скользящего контроля через мощность множества

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

для функционала ожидаемой переобученности.

Теорема 5. Для методов обучения µ МП и ПМЭР, произвольной прямой

последовательности классификаторов A = {a₀,... ,a_P }, множества X мощ-

ности L, объема обучающей выборки ℓ выражение для ожидаемой переобу-

ченности имеет вид

∑

(6)

EOF =

D_p(t,e)F_p

(t, e),

C^ℓ

L p=0 (t,e)∈Ψp

где множество D и параметр m определяются по (4) и (5) и

(

)

min{ℓ-t,m}∑

(

)

(7) F_p(t, e) =

C^smC^ℓ-t-s

n(a_p, X) - (s + e)

(s + e)

;

L-P -m L - ℓ

ℓ

s=0

{

}

(8)

Ψ_p =

(t, e) | 0 ≤ t ≤ min{l, |D|}, 0 ≤ e ≤ min{t, n(a_p, D)}

Доказательство данной теоремы приведено в Приложении.

160

Алгоритм из [24] легко дополняется формулами (6)-(8), добавляя возмож-

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

дублирования текста публикации [24] полное описание алгоритма не приво-

дится.

Алгоритм вычисления всех трех функционалов обобщающей способности

для методов ПМЭР и МП реализован на языке C++ и доступен в репозито-

рии GitHub [28].

7. Оценка частоты ошибок метода ПМЭР на контрольной выборке

В данном разделе доказывается теорема для вычисления оценок часто-

ты ошибок классификатора, выбранного методом ПМЭР, на контрольной

выборке.

Пусть задана вероятностная мера P_σ. Для семейства A и множества X

определим Радемахеровскую сложность

∑

R_L(A,X) = 2E_σ sup

σ_iI(a,x_i),

a∈A L

i=1

где I(a, x_i) обозначает ошибку классификатора, E_σ - математическое ожида-

ние по мере P_σ, а радемахеровские случайные величины σ₁, . . . , σ_L, незави-

симые в совокупности, определяются как



+1, Pσ =

σ_i =

-1, P_σ =1

Радемахеровская сложность описывает сложность семейства классифика-

торов. Чем больше Радемахеровская сложность, тем лучше ошибки класси-

фикаторов семейства могут коррелировать со случайным шумом σ_i.

В [29] было продемонстрировано, что функционал ожидаемой переобучен-

ности возникает в выражении Радемахеровской сложности, таким образом

связывая комбинаторную теорию с теорией эмпирических процессов и нера-

венств концентрации вероятностной меры:

Лемма 1 (см. [29]). Для метода обучения µ_δ МП, конечного семейства

классификаторов A, множества X мощности L, объема обучающей выборки

ℓ = ^L2 верно

EOF(µ_δ,A,X,ℓ) = R_L(A,X).

Из определения ожидаемой переобученности и метода МП следует лем-

ма 2.

Лемма 2. Для методов обучения µ_δ МП и µ ПМЭР, конечного семей-

ства классификаторов A, множества X мощности L, объема обучающей

выборки ℓ верно

EOF(µ,A,X,ℓ) ≤ EOF(µ_δ,A,X,ℓ).

161

Из лемм 1 и 2 следует теорема 6.

Теорема 6. Для метода обучения µ ПМЭР, конечного семейства клас-

сификаторов A, множества X мощности L с вероятностью ε верно

(9)

ν(µX,X

) ≤ ν(µX,X) + EOF(µ,A,X,ℓ) + η(ε),

(10)

ν(µX,X) ≤ ν(µX, X) + R_L

(A, X) + η(ε),

√

где поправка η(ε) =

-2ln^ε2 и объем обучающей выборки ℓ =^L2.

Доказательство данной теоремы приведено в Приложении.

Оценки, предложенные в теореме 6, различаются следующим. Из леммы 2

следует, что оценка (9) является более точной, чем оценка (10). Однако недо-

статком оценки (9), вычислямой по теореме 5, является большая вычисли-

тельная сложность O(L⁵), тогда как для Радемахеровской сложности воз-

можно построить быстро вычислимую верхнюю оценку, основанную на лемме

Массара [10].

В данной статье мы сравним точные значения ожидаемой переобученности

методов обучения ПМЭР µ и МП µ_δ на примере семейства прямых последо-

вательностей. Если зазор между значениями EOF (µ_δ) и EOF (µ) окажется

достаточно малым, то в правой части неравенства (10) можно заменить вели-

чину R_L(A, X) на ее быстро вычислимую оценку и использовать полученную

оценку в практических задачах.

8. Вычислительные эксперименты

Напомним обозначения. Дана прямая последовательность A = {a₀, . . . , a_P },

множество X мощности L, множество D ребер последовательности. Объем

обучающей выборки ℓ. Точность ε. Параметр m равен числу ошибок на мно-

жестве X \ D.

8.1. Модельные данные

В экспериментах используются случайные прямые последовательности.

Для порождения таких семейств генерируются класс нулей X₀ ∼ N (0, 1) и

класс единиц X₁ ∼ N (Δ, 1) как выборки равной мощности^L2 из нормаль-

ных распределений. Параметр Δ влияет на минимальное количество ошибок

классификаторов семейства. Объединение выборок является множеством X.

Множество D соответствует значениям, которые пробегает порог.

В экспериментах по сравнению оценок полного скользящего контроля в си-

лу ограниченности оценок Гуза рассматриваются прямые цепи. Для порож-

дения таких цепей из выборок X₀ и X₁ удаляются совпадающие элементы.

Также оценки Гуза справедливы только для случая, когда порог пробегает

все возможные значения, т.е. множество D совпадает с X.

8.2. Сравнение с существующими оценками вероятности переобучения

На рис. 3 в логарифмической шкале отложены значения оценки Вапника-

Червоненкиса (точки ■), оценки расслоения-связности (точки ♦) и оценки

162

-1

100

108

116120

Минимальное количество ошибок

Рис. 3. Сравнение верхних оценок вероятности переобучения в логарифми-

ческой шкале. Условия эксперимента: L = 240, ℓ = 160, m = 20, ε = 0,05.

По горизонтали отложено минимальное количество ошибок классификаторов.

Соколова (точки •) в сравнении с точной верхней оценкой вероятности пе-

реобучения прямой последовательности (точки ◮). Горизонтальной линией

указано значение Q_ε = 1.

Оценки расслоения-связности и Соколова являются точными только в

одном случае, когда минимальное количество ошибок совпадает с парамет-

ром m. В этом случае семейство является унимодальной цепью (второй гра-

фик в верхнем ряду на рис. 2), т.е. на границе классов отсутствует шум и гра-

ница определяется четко. С увеличением минимального количества ошибок

оценка (3) начинает превосходить реальное значение вероятности переобуче-

ния. Оценка Вапника-Червоненкиса для рассматриваемой последовательно-

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

ошибок.

8.3. Сравнение с существующими оценками полного скользящего контроля

На рис. 4 по вертикали в логарифмической шкале отложены значения

нижней (точки •) и верхней оценок Гуза (точки ■) и оценки расслоения-

связности (точки ♦) в сравнении с точной верхней оценкой (точки ◮).

-1

-2

-3

-4

-5

Минимальное количество ошибок

Рис. 4. Сравнение верхних оценок полного скользящего контроля в логариф-

мической шкале. Условия эксперимента: L = 240, ℓ = 160, m = 0. По горизон-

тали отложено минимальное количество ошибок классификаторов.

163

-2,5

-3,0

-3,5

100

108

116120

Минимальное количество ошибок

Рис. 5. Сравнение оценок ожидаемой переобученности для методов ПМЭР

и МП в логарифмической шкале. Условия эксперимента: L = 240, ℓ = 120,

m = 0. По горизонтали отложено минимальное количество ошибок классифи-

каторов.

Оценка расслоения-связности оказывается точной только в случае, когда

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

делимы, для остальных значений параметра она является завышенной. Верх-

няя оценка Гуза практически совпадает с точной, из чего можно сделать

вывод о высокой точности оценок.

8.4. Сравнение с Радемахеровской сложностью

На рис. 5 по вертикали в логарифмической шкале отложены значения ожи-

даемой переобученности классификатора, выбираемого методами обучения

ПМЭР (точки •) и МП (точки ◮). Можно отметить, что с увеличением ми-

нимального числа ошибок классификаторов в семействе, т.е. с увеличением

шума, два метода обучения начинают давать близкие значения ожидаемой

переобученности. В этом случае для получения верхней оценки частоты оши-

бок классификатора, выбранного методом ПМЭР, на контрольной выборке,

можно использовать оценку (10). Но при малом уровне шума ожидаемая пе-

реобученность метода ПМЭР оказывается ниже на два порядка. В этом слу-

чае для повышения точности оценок необходимо пользоваться оценкой (9).

9. Заключение

Проведено исследование обобщающей способности семейства одномерных

пороговых решающих правил, определяемой с помощью функционалов веро-

ятности переобучения, полного скользящего контроля и ожидаемой переоб-

ученности.

Показано, что имеющиеся верхние оценки вероятности переобучения яв-

ляются завышенными на 1-2 порядка. Оценки Вапника-Червоненкиса не

учитывают геометрическую структуру классов, от которой, как показано в

экспериментах, зависит обобщающая способность семейства. Комбинаторные

оценки, несмотря на то что принимают во внимание такие геометрические

свойства, как расслоение и связность, все равно являются завышенными для

данного семейства.

164

Оценки Гуза для полного скользящего контроля, полученные в рамках

комбинаторной теории переобучения и вычислимые за полиномиальное от

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

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

Оценки Радемахеровской сложности оказываются достаточно точными

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

случае, когда граница между классами определяется четко, оценки Радема-

херовского типа являются завышенными на несколько порядков и неприме-

нимыми на практике.

Поскольку имеющиеся верхние оценки обобщающей способности, за ис-

ключением оценок Гуза, не продемонстрировали высокую точность, возника-

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

шения его вычислительной сложности. Также следующей задачей является

применение точных оценок для повышения качества алгоритмов классифи-

кации, в частности для модификации критериев отбора признаков в жадных

алгоритмах индукции конъюнктивных логических закономерностей и других

логических алгоритмах классификации.

Авторы выражают глубокую признательность рецензентам за тщательное

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

и способствовали улучшению изложения.

ПРИЛОЖЕНИЕ

Доказательство теоремы 5. Запишем формулу переобученности и

переставим в ней знаки суммирования:

∑

EOF =

[µX = a_p] δ (a_p, X) =

C^ℓ

L X∈[X]^l p=0

∑

[µX = a_p] δ(a_p, X).

C^ℓ

L p=0X∈[X]l

Рассмотрим множество разбиений (X,X) с фиксированными значениями t

и e:

t = |X ∩ D|, e = n(a_p,X ∩ D).

Множество допустимых значений (t, e) есть Ψ_p согласно (8).

Обозначим s = n(a_p, X ∩ N). Из ограничений s + t ≤ l и s ≤ m следует

верхняя оценка параметра s в (7).

Поскольку число ошибок классификатора a_p на контрольной выборке рав-

но

(

)

a_p,X

= n(a_p,X) - n(a_p,X) =

= n(a_p,X) - n(a_p,X ∩ D) - n(a_p,X ∩ N),

165

переобученность классификатора a_p для данных s и e представляется в виде

(

)

δ (a_p, X) =

a_p,X

n (a_p, X) =

L-ℓ

ℓ

(n (a_p, X) - (s + e)) -

(s + e).

L-ℓ

ℓ

В [24] доказано, что выполнение условия µX = a_p не зависит от выбора

разбиения множества N, и показано, что количество разбиений множества N

для данных t и s равно C^smC^ℓ-t-sL-P-m, откуда следует утверждение теоремы 5.

Доказательство теоремы 6. С помощью неравенства Хёфдинга [30]

с вероятностью ε можно оценить отклонение η = η(ε) переобученности от ее

математического ожидания:

(

)

µX,X

≤ EOF (µ) + η (ε) ,

√

где отклонение η =

-2ln^ε2.

Тогда частоту ошибок классификатора, выбранного методом ПМЭР, на

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

на обучающей выборке и математическое ожидание переобученности:

(

)

(

)

(

)

µX,X

=ν

µX,X

+δ

µX,X

≤ ν (µX,X) + EOF (µ) + η (ε),

что обосновывает неравенство (9). Отсюда и из лемм 1 и 2 следует неравен-

ство (10). Теорема 6 доказана.

СПИСОК ЛИТЕРАТУРЫ

1. Kohavi R. A Study of Cross-Validation and Bootstrap for Accuracy Estimation

and Model Selection // Proc. Int. Joint Conf. on Artificial Intelligence.

1995.

P. 1137-1143.

2. Вапник В.Н., Червоненкис А.Я. О равномерной сходимости частот появления

событий к их вероятностям // Теория вероятности и ее применения. 1971. Т. 16.

№ 2. С. 264-280.

3. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974.

4. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука,

1979.

5. Vorontsov K.V. Combinatorial probability and the tightness of generalization

bounds // Patt. Rec. and Image An. 2008. V. 18. No. 2. P. 243-259.

6. Langford J. Quantitatively Tight Sample Complexity Bounds: Ph.D. thesis //

Carnegie Mellon Thesis, 2002.

7. Freund Y., Schapire R.E. A decision-theoretic generalization of on-line learning and

an application to boosting // Journal of Computer and System Sciences. 1997. V. 55.

No. 1. P. 119-139.

8. Kearns M.J., et.al. An experimental and theoretical comparison of model selection

methods // Computational Learning Theory. 1995. P. 21-30.

9. Boucheron S., Bousquet O., Lugosi G. Theory of classification: A survey of some

recent advances // ESAIM: Probability and Statistics. 2005. V. 9. P. 323-375.

166

10.

Shalev-Shwartz S., Ben-David S. Understanding Machine Learning: From Theory to

Algorithms. Cambridge University Press, 2014.

11.

Koltchinskii V. Oracle Inequalities in Empirical Risk Minimization and Sparse Re-

covery Problems:

École d’Été de Probabilités de Saint-Flour XXXVIII-2008. Lecture

Notes in Mathematics. Springer, 2011.

12.

Воронцов К.В. Точные оценки вероятности переобучения // Докл. РАН. 2009.

Т. 429. № 1. С. 15-18.

13.

Vorontsov K.V., Ivahnenko A.A. Tight combinatorial generalization bounds for

threshold conjunction rules // 4th Int. Conf. on Pattern Recognition and Machine In-

telligence, 2011. Lecture Notes in Computer Science. Springer-Verlag, 2011. P. 66-73.

14.

Vorontsov K.V. Splitting and similarity phenomena in the sets of classifiers and

their effect on the probability of overfitting // Pattern Recogn. and Image Anal.

2009. V. 19. No. 3. P. 412-420.

15.

Животовский Н.К., Воронцов К.В. Критерии точности комбинаторных оце-

нок обобщающей способности // Интеллектуализация обработки информации

(ИОИ-2012). М.: Торус Пресс, 2012. С. 25-28.

16.

Воронцов К.В., Фрей А.И., Соколов Е.А. Вычислимые комбинаторные оценки

вероятности переобучения // Машинное обучение и анализ данных. 2013. T. 1.

№ 6. С. 734-743.

17.

Фрей А.И., Толстихин И.О. Комбинаторные оценки вероятности переобучения

на основе кластеризации и покрытий множества алгоритмов // Машинное об-

учение и анализ данных. 2013. T. 1. № 6. С. 761-778.

18.

Haussler D., Littlestone N., Warmuth M.K. Predicting 0, 1-functions on randomly

drawn points // Information and Computation. 1994. V. 115. No. 2. P. 248-292.

19.

Vorontsov K.V. Exact combinatorial bounds on the probability of overfitting for

empirical risk minimization // Pattern Recogn. and Image Anal. 2010. V. 20. No. 3.

P. 269-285.

20.

Botov P.V. Exact estimates of the probability of overfitting for multidimensional

modeling families of algorithms // Pattern Recogn. and Image Anal. 2010. V. 20.

No. 4. P. 52-65.

21.

Толстихин И.О. Вероятность переобучения некоторых разреженных семейств

алгоритмов // Междунар. конф. ИОИ-8. М.: МАКС Пресс, 2010. С. 83-86.

22.

Frei A.I. Accurate estimates of the generalization ability for symmetric set of predic-

tors and randomized learning algorithms // Pattern Recogn. and Image Anal. 2010.

V. 20. No. 3. P. 241-250.

23.

Ботов П.В. Точные оценки вероятности переобучения для монотонных и уни-

модальных семейств алгоритмов // Математические методы распознавания

образов-14. М.: МАКС Пресс, 2009. С. 7-10.

24.

Ишкина Ш.Х. Комбинаторные оценки переобучения пороговых решающих пра-

вил // Уфимск. матем. журн. 2018. Т. 10. № 1. С. 50-65.

25.

Журавлёв Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические

методы. Программная система. Практические применения. М.: ФАЗИС, 2005.

26.

Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания

или классификации // Проблемы кибернетики. 1978. Т. 33. С. 5-68.

27.

Гуз И.С. Конструктивные оценки полного скользящего контроля для пороговой

классификации // Математическая биология и биоинформатика. 2011. Т. 6. № 2.

С. 173-189.

167