«В.В.Вьюгин ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ТЕОРИИ МАШИННОГО ОБУЧЕНИЯ Допущено Учебно-методическим объединением высших учебных заведений Российской Федерации по образованию в области прикладных математики и физики в качестве ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное агентство по образованию

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

(государственный университет)

Учреждение Российской академии наук

Институт проблем передачи информации им. А.А. Харкевича

РАН

В.В.Вьюгин

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ

ТЕОРИИ МАШИННОГО ОБУЧЕНИЯ

Допущено Учебно-методическим объединением высших учебных заведений Российской Федерации по образованию в области прикладных математики и физики в качестве учебного пособия для студентов по направлению Прикладные математика и физика

МОСКВА

МФТИ УДК 005.519.8(075.8) ББК 65.290-2в6я Рецензенты:

д.ф-м.н. проф. А.В.Бернштейн, д.ф-м.н. проф. Н.К.Верещагин Вьюгин В.В. Элементы математической теории машинного обучения (учебное пособие). М.: 2010. - 341 с.

Предназначено для первоначального знакомства с математическими основами современной теории машинного обучения (Machine Learning) и теории игр на предсказания. Цель данного пособия – дать краткий обзор основных математических методов и алгоритмов, наиболее широко обсуждаемых в мировой научной литературе последних лет. В первой части излагаются основы статистической теории машинного обучения, рассматриваются задачи классификации и регрессии с опорными векторами, теория обобщения Вапника–Червоненкиса и алгоритмы построения разделяющих гиперплоскостей. Во второй части рассматриваются задачи адаптивного прогнозирования в режиме онлайн в теоретикоигровой и сравнительной постановке: игры с рандомизированными предсказаниями, предсказания с использованием экспертных стратегий (Prediction with Expert Advice).

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

Библ. 22.

c КУ ВПО, c ИППИ РАН, Оглавление Введение 1 Элементы теории классификации 1.1. Задача классификации.................. 1.1.1. Постановка задачи классификации...... 1.1.2. Байесовский классификатор.......... 1.1.3. Линейные классификаторы: персептрон.... 1.2. Теория обобщения.................... 1.2.1. Верхние оценки вероятности ошибки классификации................. 1.2.2. VC-размерность.................. 1.3. Теория обобщения для задач классификации с помощью пороговых решающих правил.......... 1.3.1. Пороговая размерность и ее приложения... 1.3.2. Покрытия и упаковки.............. 1.4. Средние по Радемахеру................. 1.5. Средние по Радемахеру и другие меры емкости класса функций........................ 1.6. Задачи и упражнения.................. 2 Метод опорных векторов 2.1. Оптимальная гиперплоскость.............. Оглавление 2.2. Алгоритм построения оптимальной гиперплоскости..................... 2.3. Оценка вероятности ошибки обобщения через число опорных векторов.................... 2.4. SVM-метод в пространстве признаков......... 2.5. Ядра............................ 2.5.1. Положительно определенные ядра....... 2.6. Случай неразделимой выборки............. 2.6.1. Вектор переменных мягкого отступа..... 2.6.2. Оптимизационные задачи для классификации с ошибками.................... 2.7. Среднее по Радемахеру и оценка ошибки классификации........................... 2.8. Задача многомерной регрессии............. 2.8.1. Простая линейная регрессия.......... 2.8.2. Гребневая регрессия............... 2.9. Регрессия с опорными векторами........... 2.9.1. Ошибка обобщения при регрессии....... 2.9.2. Решение задачи регрессии с помощью SVM. 2.9.3. Гребневая регрессия в двойственной форме. 2.10.Нелинейная оптимизация................ 2.11.Конформные предсказания............... 2.12.Задачи и упражнения.................. 2.13.Лабораторные работы по теме SVM.......... 3.1. Универсальное прогнозирование 3.2. Калибруемость прогнозов................ 3.3. Алгоритм вычисления калибруемых 3.4. Прогнозирование с произвольным ядром....... 3.6. Лабораторные работы.................. 4 Элементы сравнительной теории машинного 4.1. Алгоритм взвешенного большинства.......... 4.2. Алгоритм оптимального распределения потерь в режиме онлайн....................... 4.3. Алгоритм следования за возмущенным лидером... 4.4. Алгоритм экспоненциального взвешивания экспертных решений.......... 4.5. Алгоритм экспоненциального взвешивания с переменным параметром обучения............. 4.6. Рандомизированные прогнозы............. 4.7. Некоторые замечательные неравенства........ 5.2. Лабораторные работы.................. 6.1. Экспоненциально вогнутые функции 6.2. Конечное множество экспертов............. 6.3. Бесконечное множество экспертов........... 6.4. Произвольная функция потерь............. 6.5. Логарифмическая функция потерь........... 6.6. Простая игра на предсказания............. 6.7. Игра с квадратичной функцией потерь........ 6.8. Универсальный портфель................ 6.9. Многомерная онлайн регрессия............. 6.9.1. Многомерная регрессия с помощью 6.9.2. Переход к ядерной многомерной регрессии.. 6.9.3. Двойственная форма задачи регрессии.... 6.10.Задачи и упражнения.................. 6.11.Лабораторные работы.................. 7.1. Антагонистические игры двух игроков........ 7.2. Достаточное условие существования 7.3. Смешанные расширения матричных игр....... 8.1. Теоретико-игровой закон больших чисел....... 8.2. Игры на универсальные предсказания......... 8.3. Рандомизированные калибруемые предсказания... 9.1. Бесконечно повторяющиеся игры двух игроков с нулевой суммой....................... 9.2. Теорема Блекуэлла о достижимости.......... 9.3. Калибруемые предсказания............... 9.4. Калибруемые предсказания и Введение Основная задача науки и реальной жизни – получение правильных предсказаний о будущем поведении сложных систем на основании их прошлого поведения.

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

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

Подход, при котором прошлые данные или примеры используются для первоначального формирования и совершенствования схемы предсказания, называется методом машинного обучения (Machine Learning).

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

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

Методы машинного обучения первого типа будут рассмотрены в главах 1 и 2, которые посвящены статистической теории машинного обучения, методы второго типа будут изучаться в главе 3 в теории хорошо калибруемых предсказаний (Calibration) и в главах 4 и 7, в которых представлена теория последовательных предсказаний с использованием предсказаний экспертов (Prediction with Expert Advice).

В главе 5 излагается алгоритм усиления слабых классификаторов – бустинг (Boosting). Приводится алгоритм AdaBoost, решающий эту задачу.

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

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

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

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

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

Глава 2 посвящена построению алгоритмов классификации и регрессии. В основном, это алгоритмы, использующие метод опорных векторов.

Теория последовательного предсказания (глава 3) идет несколько дальше. Она вообще не использует гипотез о стохастических механизмах, генерирующих данные. Наблюдаемые исходы могут генерироваться совершенно неизвестным нам механизмом, который может быть как детерминистским так и стохастическим, или даже, адаптивно враждебным к нашим предсказаниям (т.е., может использовать наши прошлые предсказания при генерации очередного исхода).

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

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

Ошибка алгоритма предсказателя (регрет – regret) определяется как минимальное значение такой разности.

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

В главе 5 метод распределения потерь в режиме онлайн будет применен для усиления слабых алгоритмов классификации. Слабый алгоритм классификации делает лишь незначительно меньшее число ошибок, чем простое случайное угадывание. Алгоритм AdaBoost, приводимый в этой главе, усиливает слабый алгоритм классификации до алгоритма, который с некоторого момента в процессе обучения начинает делать как угодно малое число ошибок.

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

Предсказания в режиме онлайн тесно связаны с теорией игр.

Теория игр рассматривается в главе 7. Мы рассмотрим матричную игру двух лиц с нулевой суммой и докажем для нее минимаксную теорему Дж. фон Неймана. Доказательство минимаксной теоремы проведено в стиле теории машинного обучения с использованием метода экспоненциального смешивания. В этой главе также вводятся понятия равновесия Нэша и коррелированного равновесия Аумана.

В главе 8 рассматривается новый теоретико-игровой подход к теории вероятностей, предложенный Вовком и Шейфером [24]. В рамках этого подхода формулируются игры, в которых, при определенных условиях, выполнены различные законы теории вероятностей. Примеры таких законов – закон больших чисел, закон повторного логарифма, центральная предельная теорема и т.д.

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

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

В главе 9 будут рассматриваться более сложные вопросы теории игр. В основе излагаемой теории находится знаменитая теорема Блекуэлла о достижимости (Blackwell approachability theorem).

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

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

Данное учебное пособие представляет собой расширенный вариант курса лекций, прочитанных автором в 2008–2012 годах в Московском физико-техническом институте (МФТИ) в рамках специализации Математические и информационные технологии.

Автор благодарен студентам МФТИ П.Д. Ерофееву, И.А. Жарову, А.А. Крещуку, А.Д. Шишкину за сделанные ими замечания.

Автор также благодарен Владимиру Вовку и Юрию Калнишкану за ценные замечания и советы по поводу изложения материала данного учебного пособия.

При составлении этого учебного пособия были использованы монографии: В.Н. Вапник и А.Я. Червоненкис [2], Vladimir Vapnik [28], Nello Cristianini, John Shawe-Taylor [10], Gabor Lugosi, Nicolo Cesa-Bianchi [21], Glenn Shafer, Vladimir Vovk [24], а также учебное пособие Е.В. Шикин, Г.Е. Шикина [4].

Глава Элементы теории классификации 1.1. Задача классификации 1.1.1. Постановка задачи классификации Как было замечено во введении, теория машинного обучения решает задачи предсказания будущего поведения сложных систем в том случае, когда отсутствуют точные гипотезы о механизмах, управляющих поведением таких систем.

Мы рассмотрим два основных класса задач теории машинного обучения: задачи классификации и задачи регрессии.

В этом разделе будет рассматриваться задача классификации.

Пусть задано множество объектов X и множество D классов этих объектов. В дальнейшем X Rn, где R – множество всех действительных чисел, а D – конечное множество с небольшим числом элементов. Размерность n евклидового пространства Rn обычно велика по сравнению с числом классов.

Далее элементы Rn будем называть векторами (точками) и обозначать подчеркнутыми сверху буквами: x, y,... Rn ; в координатах – x = (x1,..., xn ). Будут рассматриваться операции сложения векторов умножения на вещественное число ляется как При решении задачи классификации мы исходим из обучающей дового пространства R может быть цифровой образ какого-либо изображения), yi – это элемент конечного множества D с небольшим числом элементов (метка класса), например, yi {1, 1}. Элементы yi D определяют классы объектов xi.

При решении задачи многомерной регрессии также рассматривается обучающая выборка S = ((1, y1 ),..., (l, yl )), при этом элементы yi обычно являются вещественными числами, т.е.

D = R. Задача регрессии будет рассмотрена в разделах 2.8, 2.9, 2.9.2, а также в разделе 6.9.

рируется (порождается) некоторым источником. Основное предположение об источнике, порождающем выборку S, заключается С помощью штриха мы уточняем форму представления вектора в виде матрицы – простую или транспонированную, но только в тех случаях когда это имеет существенное значение.

в том, что на парах (, y), т.е. на пространстве X D задано расx пределение вероятностей P, а пары (i, yi ), образующие выборку S, одинаково и независимо распределены.

Соответственно на множестве (X D)l задано распределение вероятностей P l = P P · · · P.

Строго говоря, пары (, y) являются реализациями случайx ной величины (X, Y ), которая имеет распределение вероятностей P. Плотность распределения P будет обозначаться так же как P (, y).

Правило или функция классификации – это функция типа h : X D, которая разбивает элементы xi X на несколько классов. Мы будем также называть функцию h классификатором, или решающим правилом.

В дальнейшем у нас всегда будет рассматриваться случай бинарной классификации D = {1, 1}, а функция h : X D будет называться индикаторной.

В этом случае вся выборка S разбивается на две подвыборки:

+ = ((, y ) : y = 1) – положительные примеры (или первый класс) и S = ((i, yi ) : yi = 1) – отрицательные примеры (или второй класс).

В некоторых случаях индикаторная функция классификации h задается с помощью некоторой вещественной функции f и числа Качество произвольной функции классификации h будет оцениваться по ошибке классификации, которая определяется как вероятность неправильной классификации Здесь h(X) – функция от случайной величины X, также является случайной величиной, поэтому можно рассматривать вероятность события {h(X) = Y }.

Функция errP (h) также называется риск-функционалом.

Основная цель при решении задачи классификации – для заданного класса функций классификации H построить оптимальный классификатор, т.е. такую функцию классификации h H, при которой ошибка классификации errP (h) является наименьшей в классе H.

1.1.2. Байесовский классификатор Предварительно рассмотрим один простейший метод классификации. Легко построить оптимальный классификатор, если распределение вероятностей P, генерирующее пары (i, yi ), известно.

Рассмотрим пары случайных переменных (X, Y ), принимающих значения в множестве типа X {1, 1}. Предполагаем, что на этим парам соответствует распределение вероятностей P и соответствующая плотность вероятности P (, y). Предполагаем, что существуют условные плотности P (|Y = 1) – плотность распределения векторов первого класса, а также P (|Y = 1) – плотность распределения векторов второго класса. Величины P {Y = 1} и P {Y = 1} определяют вероятности появления векторов первого и второго классов соответственно. Все эти вероятности и плотности вероятностей легко вычисляются по плотности вероятности P (, y). Например, P {Y = 1} = P (, 1)d, а P (|Y = 1) = P (, 1)/P {Y = 1}. Используя эти вероятности, можно по формуле Байеса определить апостериорные вероятности принадлежности вектора x к первому и второму классу где Рассмотрим условную вероятность того, что вектор x принадлежит первому классу Здесь и далее мы предполагаем, что P {Y = 1} > 0 и P {Y = 1} > 0, а также P (|Y = 1) > 0 и P (|Y = 1) > 0.

Для произвольного классификатора g : X {1, 1} вероятность ошибки классификации равна Байесовский классификатор определяется как Следующая лемма показывает, что байесовский классификатор минимизирует вероятность ошибки errP (h), которая в данном случае, называется байесовской ошибкой.

Лемма 1.1. Для любого классификатора g : X {1, 1} Доказательство. Для произвольного классификатора g условная вероятность ошибки классификации при X = x выражается в виде нено, и 1R() () = 0, в противном случае.

Аналогичное неравенство выполнено для классификатора h(). x сификации g. Таким образом, для каждого x X по определению байесовского классификатора h.

Интегрируем обе части этого неравенства по x. Получим неравенство леммы.

Байесовский классифкатор служит эталоном для оценки качества алгоритмов классификации.

Обозначим посредством D множество всех измеримых функций классификаторов типа g : X {1, 1}. Условие (1.1) можно записать в виде Пусть некоторый классификатор gl D построен некоторым алгоритмом A по случайной выборке S = ((1, y1 ),..., (l, yl )) сгеx x нерированной распределением вероятностей P. Алгоритм классификации A называется состоятельным для распределения P, если случайная величина errP (gl ) сходится к errP (h) по вероятности P, т.е. для любого > при l.

Алгоритм классификации A называется универсально состоятельным, если условие (1.2) имеет место для любого распределения P.

Недостатком байесовского классификатора является то, что он использует для вычисления значений функции h() вероятностx ное распределение P, генерирующее пары (, y). Прежде чем исx пользовать байесовский классификатор, надо решить задачу восстановления вероятностного распределения P по его реализациям. На практике такое вероятностное распределение часто неизвестно и его трудно восстановить. Обычно для получения достоверного результата требуется довольно много реализаций случайной величины (X, Y ).

Основные проблемы статистической теории классификации связаны с тем, что при построении классификаторов h() мы не можем использовать распределения вероятностей, генерирующие пары (, y).

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

Байесовский классификатор служит для оценки качества других алгоритмов классификации.

1.1.3. Линейные классификаторы: персептрон Рассмотрим один из наиболее старых алгоритмов классификации – персептрон.

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

Математическая модель персептрона будет задаваться следующим образом. Задано пространство X исходных описаний объекта. Преобразование y = (), которое в координатном виде запиx сывается как yi = i (), i = 1,..., n, ставит исходному описанию x = (x1,..., xm ) X объекта преобразованное описание объекта y = (y1,..., yn ) Y. Предполагаем, что X Rm и Y Rn для некоторых m, n.

Персептрон задается однородной линейной функцией где действительные числа i интерпретируются как веса, приписываемые преобразованным признакам yi. Здесь ( · ()) обознаx чает скалярное произведение двух векторов = (1,..., n ) и () = (1 (),..., n ()) в евклидовом в пространстве Rn.

В некоторых персептронах рассматриваются преобразованные признаки, которые принимают всего два значения (бинарные признаки), например, рассматривается случай Y = {1, 1}.

Для простоты считаем, что персептрон различает два понятия или класса объектов. Персептрон относит вектор x к первому классу, если в противном случае, персептрон относит вектор x ко второму классу.

Геометрически это означает, что в пространстве признаков X задана гиперповерхность которая делит пространство X на два полупространства. Объекты первого класса относятся к одному полупространству, объекты второго класса относятся ко второму полупространству. Подобная гиперповерхность называется разделяющей.

Каждой разделяющей гиперповерхности (1.3) соответствует разделяющая гиперплоскость в пространстве преобразованных признаков Y. Пространство Y также называется спрямляющим.

Пусть задана бесконечная обучающая выборка в спрямляющем пространстве где i обозначает принадлежность объекта yi = (i ) классу Допустим, что существует гиперплоскость, разделяющая выборку S. Пусть = (1,..., n ) – вектор коэффициентов этой разделяющей гиперплоскости. По определению гиперплоскость строго разделяет выборку, если выполнены неравенства для всех i.

Для удобства преобразуем обучающую выборку следующим образом. Рассмотрим последовательность векторов y1, y2,..., где для всех i. Тогда условие строгого разделения (1.4) запишется в виде для всех i.

Обозначим Условие строгой разделимости выборки S может быть записано в виде 0 > 0.

Переходим теперь к описанию алгоритма Розенблатта построения разделяющей гиперплоскости.

Пусть задана произвольная бесконечная обучающая выборка и пусть существует гиперплоскость, проходящая через начало координат ( · y ) = 0, строго разделяющая эту выборку, т.е. такая, что для всех i. Считаем, что | | = 1. Для бесконечной выборки мы усилим условие строгого разделения (1.6): предполагаем, что существует порог разделения – число 0 > 0 такое, что для всех i. Также предполагаем, что векторы yi равномерно ограничены по модулю Алгоритм Розенблатта построения разделяющей гиперплоскости Обучение персептрона заключается в изменении координат вектора весов на каждом шаге алгоритма.

Пусть t = (1,t,..., n,t ) – текущий вектор коэффициентов гиперплоскости, вычисленный на шаге t алгоритма, t = 1, 2,....

Алгоритм использует преобразованную последовательность векторов y1, y2,....

FOR t = 1, 2,...

Если (t1 · yt ) > 0, то полагаем t = t1.

(т.е. если очередной вектор классифицируется правильно, то текущая гиперплоскость не изменяется).

Если (t1 · yt ) 0 (очередной вектор классифицируется неправильно), то производим корректировку вектора гиперплоскости t = t1 + yt, назовем эту операцию также исправлением ошибки.

ENDFOR

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

Теорема 1.1. Если существует гиперплоскость, разделяющая бесконечную выборку с положительным порогом, то в алгоритме Розенблатта исправление ошибки происходит не более чем раз. Это значит, что неравенство t = t1 выполнено для не более чем D2 различных t. 3 После этого, разделяющая гиперплоскость стабилизируется и будет безошибочно делить всю бесконечную оставшуюся часть последовательности.

Доказательство. Если на шаге t происходит изменение вектора t, то Так как (t1 · yt ) 0 (классификация t-го вектора неправильная) Если до шага T включительно произошло k таких исправлений, то получаем По условию разделимости (1.7) существует единичный вектор такой, что для всех i.

Оценим величину (t · ). По определению (0 · ) = 0. Если на шаге t алгоритм производит исправление, то Если на шаге t исправления не происходит, то Таким образом, если к шагу t алгоритм произвел k исправлений, [r] – целая часть вещественного числа r.

По неравенству Коши–Буняковского Поэтому имеет место неравенство Объединяем неравенства (1.8) и (1.9), получаем Таким образом, число исправлений не превосходит Теорема доказана.

По теореме 1.1, какова бы ни была бесконечная разделимая с положительным порогом выборка, алгоритм Розенблатта, сделав конечное число исправлений, не превосходящее D2, найдет какую-либо гиперплоскость строго разделяющую всю выборку.

В некоторых случаях в персептроне рассматривается бинарное спрямляющее пространство, т.е. Y = {1, 1}n.

В этом случае ясно, что D2 n. Тогда оценка теоремы 1. имеет вид т.е. число коррекций алгоритма обучения персептрона растет линейно с размерностью пространства.

В этом разделе была рассмотрена двухуровневая модель перx септрона. На первом уровне определяется отображение y = () исходного пространства описаний объектов X в спрямляющее пространство Y. На втором уровне реализуется алгоритм обучения – построение разделяющей гиперплоскости в пространстве Y на основе обучающей последовательности. Основное требование к отображению диктует вторая часть модели, а именно, множества векторов – образов y, принадлежащих к различным классам должны быть разделимы гиперплоскостью.

Возникает естественный вопрос, всегда ли существует такое отображение y = (), при котором образы любых двух непересекающихся в исходном пространстве X множеств были бы разделены в спрямляющем пространстве Y гиперплоскостью.

Было показано, что если исходное пространство X бинарное, то такое отображение существует, более того, оно может быть осуществлено с помощью линейных функций (см. [2]). Недостатком этого результата является то, что размерность спрямляющего пространства оказывается очень большой. Для большинства пар множеств отношение D2 слишком велико и поэтому обучение персептрона может потребовать значительно большого времени.

По этой причине, обычно отображение y = () выбирается на основании знания конкретной предметной области.

Многослойная нейронная сеть Персептроны можно комбинировать в виде многослойных нейронных сетей. В каждой вершине такой сети располагается некоторая функция Функция называется функцией активации; на место аргумента в ней подставлено значение персептрона. Примеры функций активации:

где Рассмотрим сеть вершин, состоящую из l слоев. Заданы натуральные числа n1,..., nl – размеры слоев (число верщин в слое), причем, самый верхний слой состоит из одной вершины: nl = 1.

С каждой j-ой вершиной i-го слоя сети ассоциируется функция fi,j () = ((wi,j · x) + bi,j ), где wi,j, x Rni1 и bi,j R.

Нейронная сеть может быть представлена в виде набора векторнозначных функций i = 1,..., l, где fi = (fi,1,..., fi,ni1 ).

Выход нейронной сети задается одномерной функцией – композицией Векторы wi,j называются весами, которые приписаны вершинам (i, j) нейронной сети.

1.2. Теория обобщения 1.2.1. Верхние оценки вероятности ошибки классификации В теории обобщения вычисляются вероятности ошибки классификации на тестовой выборке, после того как функция классификации определена по обучающей выборке, т.е. проведено обучение алгоритма классификации.

В этом разделе мы приведем основные положения статистической теории обобщения.

Статистическая теория машинного обучения использует гипотезу о том, что пары (xi, yi ) генерируются некоторым неизвестным нам распределением вероятностей, при этом, как правило, рассматривается очень широкий класс таких распределений. Используется только предположение о том, что данные независимо и одинаково распределены.

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

Функция классификации проверяется на тестовой выборке.

Задачей теории обобщения является оценить вероятность ошибки классификации на произвольной тестовой выборке.

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

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

Это позволяет контролировать зависимость параметров обучения и вероятности ошибки в будущем.

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

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

Критерий выбора функции классификации основан на минимизации верхней оценки вероятности ошибки обобщения.

Пусть S = ((1, y1 ),..., (l, yl )) – обучающая выборка. Здесь n-мерное евклидово векторное пространство.

В данном разделе при вероятностном анализе мы предполагаем, что выборка S – это случайная величина, состоящая из случайных величин (i, yi ), i = 1,... l. Для удобства (в отличие от раздела 1.1.2) мы обозначаем случайные величины (i, yi ) маленьx кими буквами.

Пусть задано правило (или функция) h : X {1, 1}. Риск функционал (или ошибка классификации) определяется как Эта величина равна вероятности неправильной классификации.

Гипотеза классификации h согласована с выборкой если h(i ) = yi для всех – относительное число ошибок классификации h на выборке S.

Здесь |A| – число элементов множества A. Тогда гипотеза классификации h согласована с выборкой S, если errS (h) = 0.

Для произвольной гипотезы классификации h и > 0 имеем Здесь мы использовали независимость ошибок на элементах выборки.

Пусть H – некоторый класс гипотез классификации. Если класс H конечный, то из (1.10) получаем оценку Интерпретация (1.11) заключается в следующем.

Пусть задан критический уровень > 0 принятия ошибочной гипотезы классификации h H, согласованный с обучающей выборкой S. Тогда по (1.11) мы можем утверждать, что с верогипотеза классификации hS H, построенная ятностью по случайной обучающей выборке S и согласованная с ней, будет иметь ошибку классификации errP (h) l Другими словами, всякая гипотеза классификации h, имеюH|el не будет щая ошибку errP (h) >, с вероятностью согласована со случайной выборкой длины l.

В случае бесконечного семейства функций H аналогичные оценки на ошибку классификации дает теория обобщения Вапника–Червоненкиса. Сложность класса H оценивается с помощью функции роста Свойства этой функции будут изучаться далее.

Имеет место теорема – аналог соотношения (1.11) для бесконечного H.

Теорема 1.2. При l > 2/ имеет место оценка Доказательство теоремы Аналогично 1h()=y (, y) есть случайная величина, равная 1, если h() = y и равная 0, в противном случае. Тогда где E – математическое ожидание по мере P. По определению – частота ошибок классификации на выборке S.

Утверждение теоремы будет следовать из следующих двух лемм.

Лемма 1.2. Пусть задан класс H функций классификации. Рассматриваются две случайные выборки S, S длины l. Тогда для любого > 0 при l > 2/ имеет место неравенство Доказательство. Легко видеть, что неравенство (1.12) эквивалентно неравенству Докажем (1.13). Для каждой выборки S из множества левой части неравенства (1.13) обозначим посредством hS какую-нибудь функцию из класса H, для которой выполняются равенство errS (hS ) = 0 и неравенство errP (hS ) >. Это случайная величина, зависящая от выборки.

Имеет место следующее неравенство между случайными величинами Возьмем математическое ожидание по второй выборке S от обеих частей неравенства (1.14). Получим неравенство для случайных величин, зависящих от первой выборки S :

1errS (hS ) = 0&errP (hS ) > Здесь 1errS (hS )=0&errP (hS )> (S) = 0, если S не лежит в множестве из левой части неравенства (1.13). Также 1errS (hS )=0&err (hS )> 1 (SS ) = 0, если SS не лежит в множестве из правой части неравенства (1.13).

Используя свойства биномиального распределения получаем при l > 2/. Здесь p = errP (hS ).

Действительно, при l > 2/ будет p /2 < p 1/l. Поэтому достаточно доказать, что Это неравенство эквивалентно неравенству Сумма первой и третьей сумм из (1.17) меньше 1. Поэтому каждая из них меньше 1/2.

Подставляя неравенство (1.16) в (1.15), получим Возьмем среднее по S и получим Отсюда получаем (1.13). Лемма доказана.

Лемма 1.3. Вероятность того, что на двух случайных выборках S и S длины l некоторая функция классификации h H согласована с первой из них и совершает более l ошибок на второй выборке ограничена величиной Доказательство. Определим функцию, которая по произвольной выборке SS = ((1, y1 ),..., (2l, y2l )) длины 2l выдает ее состав, т.е. множество пар ее составляющих вместе с кратностями где ki – число вхождений пары (i, yi ) в выборку SS, i = 1,..., L, L – число различных пар (i, yi ) в выборке SS ; по определению В отличие от выборки ее состав – неупорядоченное множество.

Мера P 2l на выборках длины 2l индуцирует меру P на их составах:

где – множество, состоящее из составов типа.

Фиксируем некоторый состав для выборок длины 2l. Предварительно также фиксируем некоторую функцию классификации h.

Для каждой двойной выборки SS = ((1, y1 ),..., (2l, y2l )) определим бинарную последовательность 1,..., 2l ошибок классификации, где где i = 1,..., 2l.

Поскольку ошибки классификации описываются бернуллиевским распределением с вероятностью ошибки P {h() = y}, любые два набора ошибок 1,..., 2l и 1,..., 2l на двух выборках с одним и тем же составом равновероятны. Поэтому вероятность того, что для некоторого фиксированного состава на некоторой двойной выборке SS, имеющей состав (т.е. такой, что (SS ) = ), функция h делает m ошибок и все они сосредоточены на второй половине этой выборки, оценивается Пусть теперь функция классификации h принимает любое значение из класса H. Число всех функций, которые получаются ограничением области определения функций из H на множество всех объектов {1,..., x2l } из выборок SS данного соx става (SS ) =, не превосходит числа элементов множества следовательностей длины 2l.

Оценку числа таких функций дает функция роста семейства индикаторных функций H :

Ясно, что BH (l) 2l. Точные оценки функции роста различных семейств классификаторов будут даны в следующем разделе.

Из определения функции роста следует, что число всех ограничений функций классификации из H на выборках длины 2l не превосходит BH (2l).

Эти вероятности определяются биномиальным распределением и равны pk (1 p)2lk, где p = P {h() = y} и k – число единиц (число ошибок) в выборке.

Поэтому условная вероятность того, что некоторая функция классификации из класса H делает более l ошибок на двойной выборке с данным составом и все они сосредоточены на второй половине этой выборки, ограничена сверху P 2l {SS : ( h H)(errS (h) = 0&errS (h) > |(SS ) = } Левая часть этого неравенства представляет собой случайную величину (функцию от состава ). Правая часть неравенства не зависит от состава.

Интегрируя это неравенство по мере P на составах, получим безусловное неравенство Лемма 1.3 доказана.

Теорема 1.2 непосредственно следует из лемм 1.2 и 1.3.

Из теоремы 1.2 следует, что всякая гипотеза классификации h, имеющая ошибку errP (h) >, с вероятностью 1 2BH (2l)e l/ не будет согласована со случайной выборкой длины l > 2/, т.е.

будет отвергнута как ошибочная.

Обозначим = 2BH (2l)e l/4. Тогда при 0 < < 1 будет выполнено l > 2, т.е. условие теоремы 1.2 выполнено. Отсюда получаем следующее следствие Следствие 1.1. Допустим, что класс H функций классификации имеет конечную VC-размерность d. Пусть задан критический уровень 0 < < 1 принятия ошибочной гипотезы классификации h H, согласованной с обучающей выборкой S.

Тогда с P l -вероятностью 1 гипотеза классификации hS H, построенная по случайной обучающей выборке S и согласованная с ней, будет иметь ошибку классификации Определение VC-размерности дано в следующем разделе 1.2.2. Там же получена оценка BH (l) при l d.

Все эти результаты можно усилить на случай обучения с ошибками. Аналогичным образом доказываются следующие две леммы 1.4 и 1.5, а также их следствие – теорема 1.3.

Лемма 1.4. Пусть задан класс H функций классификации. Рассматриваются две случайные выборки S, S длины l. Тогда для любого > 0 при l > 2/ имеет место неравенство Лемма 1.5. Вероятность того, что на двух случайных выборках S и S длины l частоты ошибок некоторой функции классификации h H различаются более чем на > 0, ограничена величиной P 2l {SS : (h H)(errS (h) errS (h) > )} Доказательство этой леммы аналогично доказательству леммы 1.3. При этом удобно использовать неравенство Хефдинга (см.

следствие 4.5 из раздела 4.7 ниже).

Следующая теорема дает оценку вероятности отклонения риск функционала от среднего числа ошибок на обучающей выборке.

Теорема 1.3. Имеет место оценка P l {S : ( h H)(errP (h) errS (h) > )} при l > 2/.

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

Следствие 1.2. Допустим, что класс H функций классификации имеет конечную VC-размерность d, 0 < < 1. Тогда для h H с вероятностью 1 выполнено Следует отметить, что оценки теорем 1.2 и 1.3, а также следствий 1.1 и 1.2, имеют в основном теоретическое значение, так как на практике VC-размерность d может быть сравнимой с длиной выборки l. Ближе к практике находятся оценки не зависящие от размерности пространства (см. теоремы 1.9, 2.10, следствие 2. далее).

1.2.2. VC-размерность В этом разделе мы рассмотрим определение и свойства размерности Вапника–Червоненкиса – VC-размерности, которая характеризует сложность бесконечного класса функций классификации.

Пусть H – произвольный класс функций классификации, функция h H. Бинарный набор (h(1 ),..., h(l )), состоящий из элементов множества {1, 1}, определяет разделение множества ные примеры и {i : h(i ) = 1} – отрицательные примеры.

Множество {1,..., xl } полностью разделено функциями из H (shattered by H), если Функция роста семейства классификаторов H определяется как максимальное число различных разбиений выборок длины l на два подмножества, которые можно осуществить с помощью функций из класса H Ясно, что BH (l) (функциями из класса H) множество (выборка) из l элементов, то BH (l) = 2l.

Основная теорема теории VC-размерности (лемма Сауэра) 7 :

Это утверждение было также независимо получено Вапником и Червоненкисом [2].

Теорема 1.4. Для любого класса индикаторных функций H реализуется одна из двух возможностей:

1) BH (l) = 2l для всех l, т.е. для любого l существует полностью разделимая выборка размера l.

2) Существует полностью разделимая выборка максимального размера d; в этом случае BH (l) = 2l при l d и при l > d.

Другими словами, функция GH (l) = ln BH (l) – линейная или, начиная с некоторого значения, ограничена логарифмической функцией O(d ln l) (Например, она не может иметь вид O( l)).

Число d называется размерностью Вапника–Червоненкиса или VC-размерностью класса функций H. Если реализуется первый случай, то VC-размерность класса H бесконечная.

Доказательство. Допустим, что VC-размерность некоторого класса индикаторных функций H равна d. Тогда по определению BH (l) = 2l при всех l d.

Мы докажем неравенство (1.21) математической индукцией по величине l + d. Для l = d = 1 это неравенство верно, так как обе его части равны 2.

Допустим, что это неравенство верно для любой суммы < l+d, в частности, для l 1 и d, а также для l 1 и d 1.

Докажем его для случая, когда размер выборки равен l, а VCразмерность класса функций равна d.

Введем обозначение Тогда нам надо доказать, что для любого класса функций H с VC-размерностью d будет BH (l) h(l, d) для всех l.

Из свойства биномиальных коэффициентов:

получаем соответствующее свойство, связывающее значения функции h :

Пусть H – произвольный класс функций с VC-размерностью d и пусть X1 = {x1, x2,..., xl } – произвольное множество объектов мощьности l, X2 = {x2,..., xl } – оно же, но без первого элемента.

Рассмотрим ограничения H1 = H|X1 функций из класса H на множество X1 и H2 = H|X2 – ограничения функций из класса H на множества X2.

Пусть также класс функций H3 состоит функций f из класса H2, для каждой из которых найдется функция f H такая, что f (x1 ) = f (x1 ).

Заметим, что |H1 | = |H2 |+|H3 | поскольку класс H2 отличается от класса H1 тем, что двум индикаторным функциям f и f из класса H1, различающимся на объекте x1 (если такие функции существуют), соответствует только одна функция из класса H2.

Также заметим, что VC-размерность класса H2 не превосходит d, поскольку это подкласс класса H1.

VC-размерность класса H3 не превосходит d 1, поскольку, если класс функций полностью разделяет некоторое множество объектов мощности d, то сущствуют расширения этих функций из класса H1 на элемент x1, которые полностью разделят это же множество с добавленным к нему элементом x1 (так как для x и любой функции из класса H3 найдутся два их расширения из H1, принимающие противоположные значения этом элементе). В это случае, класс H1 также полностью разделяет это расширенное множество, а его размерность равна d + 1. Противоречие.

По предположению индукции Поэтому Так множество X произвольное, получаем Неравенство (1.21) доказано. Оценка при l > d, следует из следующей цепочки неравенств:

Теорема доказана.

Мы приведем оценку VC-размерности для класса L всех линейных классификаторов на Rn, т.е. всех индикаторных функций вида h() = sign(L()), где L() – линейная функция. Здесь sign(r) = 1, если r > 0, sign(r) = 1, в противном случае. Иногда классификатором будем называть соответствующую функцию L().

Линейная функция – это функция вида L() = ( · x) + b, где x Rn – переменная, a Rn – вектор весов, b – константа.

Если b = 0, то линейный классификатор sign(L()) = sign( · x) называется однородным.

Заметим, что в случае линейных (и однородных) классификаторов выборка разделима тогда и только тогда, когда она строго разделима.

Теорема 1.5. 1) VC-размерность класса всех линейных функций классификации над Rn равна n + 1.

2) VC-размерность класса всех линейных однородных классификаторов над Rn равна n.

3) Для класса всех линейных однородных функций классификации над Rn выполнено при l > n.

Доказательство. Предварительно докажем второе утверждение. Набор n векторов e1 = (1, 0,..., 0),..., en = (0, 0,..., 1) является полностью строго разделимым, так как для любого подмножества ei1,..., eik этого набора существует линейный однородный классификатор h() = sign(L()), где L() = a1 x1 + · · · + an xn, который отделяет векторы этого подмножества от остальных векторов набора. Определим коэффициенты гиперплоскости L(), проходящей через начало координат, следующим образом:

L(ij ) = 1 при 1 j k и L(ij ) = 1 для всех остальных j.

Допустим, что некоторые n + 1 векторов u1,..., un, un+1 могут быть полностью строго разделимыми. Тогда существуют 2n+ весовых векторов a1,..., a2n+1 таких, что в матрице Z, образованной числами zi,j = (j · ui ), i = 1,..., n + 1, j = 1,..., 2n+1, знаки элементов j-го столбца (выделенных черным цветом) соответствуют j-му классификационному классу, поэтому знаки элементов столбцов образуют все 2n+1 бинарных последовательностей длины n + 1.

Векторы u1,..., un, un+1 расположены в n-мерном пространстве и поэтому линейно зависимы, т.е. для некоторой их нетривиальной (i = 0 хотя для одного i) линейной комбинации Домножаем это равенство на aj, j = 1,..., 2n+1, и получаем равенство нулю линейной комбинации с вещественными коэффициентами 1,..., n+1 элементов произвольного j-го столбца, Среди столбцов имеется хотя бы один, знаки элементов которого совпадают со знаками набора 1,..., n+1. Одно из чисел i не равно нулю. Поэтому сумма попарных произведений для одного из столбцов положительна. Полученное противоречие доказывает второе утверждение теоремы.

Докажем первое утверждение теоремы. Заметим, что набор из n + 1 векторов является полностью строго разделимым с помощью линейных классификаторов. Для доказательства этого утверждения, для любого подмножества {i1,..., eik } данного набора рассмотрим линейный классификатор h() = sign(L()), где Коэффициенты гиперплоскости, отделяющей это подмножество от всех остальных векторов набора определяются следующим обk, и ai = 1 для всех остальных i, b = 2, если вектор e0 входит в подмножество и b = 1 в противном случае. Тогда выполнено L(ij ) > 0 при 1 j k и L(ij ) < для всех остальных j.

Допустим, что существует выборка из n+2 векторов n-мерного пространства, полностью строго разделимая линейными классификаторами. Пусть это векторы Покажем, что соответствующая выборка, состоящая из n + 2 векторов x1 = (x1,1,..., x1,n, 1),..., xn+2 = (xn+2,1,..., xn+2,n, 1), лежащих в n+1-мерном пространстве, полностью разделима однородными классификаторами. Рассмотрим произвольное подмножество выборки xi1,..., xik, а также соответствующее подмножество xi1,..., xik исходной выборки. Пусть некоторая гиперплоскость отделяет подмножество xi1,..., xik от остальных векторов исходного набора, т.е. L(ij ) > 0 при j = 1,..., k и L(i ) < 0 для остальных i.

Рассмотрим соответствующий линейный однородный классификатор в n + 1-мерном пространстве Тогда L (i ) = L(i ) при i = 1,..., n + 2. Поэтому линейный однородный классификатор L ( ) отделяет соответствующее подx множество xi1,..., xik от всех остальных элементов выборки x1 = (x1,1,..., x1,n, 1),..., xn+2 = (xn+2,1,..., xn+2,n, 1).

Таким образом, некоторая выборка n + 1-мерного пространства, состоящая из n+2 векторов, оказалась полностью разделимой однородными классификаторами. Это противоречит второму утверждению теоремы. Данное противоречие доказывает первое утверждение теоремы.

Докажем третье утверждение теоремы. Пусть даны l векторов x1,..., xl. Мы рассматриваем все возможные разбиения этих векторов на два подкласса. Такие разбиения производятся с помощью гиперплоскостей L() = ( · x), где u – весовой вектор, задающий гиперплоскость, а x – переменный вектор.

По определению Rn (u) = Rn (x) = Rn. Для удобства мы выделяем переменную, пробегающую по этому множеству.

Каждому вектору u Rn (u) соответствует гиперплоскость L() = ( · x) в Rn (x).

Заметим, что можно рассмотреть двойственный вариант. Вектору x Rn (x) соответствует гиперплоскость L() = ( · u) в Rn (u), а l векторам x1,..., xl из Rn (x) соответствуют l гиперплоскостей X1,..., Xl в пространстве Rn (u), проходящих через начало координат.

Пусть u Rn (u) – вектор, соответствующий некоторой гиперплоскости L() = ( · x) в Rn (x), разделяющей x1,..., xl.

Если непрерывно двигать эту гиперплоскость в Rn (x), так что разделение векторов x1,..., xl не нарушается, соответствующий вектор u заметает компоненту в пространстве Rn (u). Компонента – это множество векторов (точек) пространства Rn (u), ограниченное гиперплоскостями X1,..., Xl, образованными в Rn (u) векторами x1,..., xl, которые в данном случае рассматриваются как весовые. Заметим, что таким образом каждая такая компонента соответствует одному варианту разбиения векторов x1,..., xl на два класса.

Тогда максимальное число вариантов разбиения векторов x1,..., xl на два класса гиперплоскостями, проходящими через начало координат в Rn (x), равно максимальному числу компонент, на которые l гиперплоскостей X1,..., Xl делят n-мерное пространство Rn (u).

Пусть (n, l) – максимальное число компонент, на которые l гиперплоскостей X1,..., Xl разделяют n-мерное пространство Rn (u).

Имеем (1, l) = 2, так как функция L(x) = ux может разделить l точек на прямой только на два класса. Также (n, 1) = 2, так как одна гиперплоскость может разделить точки Rn (u) только на две компоненты.

Пусть теперь заданы l 1 векторов x1,..., xl1 в пространn (x). Им соответствуют l 1 гиперплоскостей X,..., X в пространстве Rn (u), которые разделяют это пространство как максимум на (n, l 1) компонент.

Добавим новый вектор xl к ранее рассмотренным векторам x1,..., xl1 в пространстве Rn (x). Ему соответствует новая гиперплоскость Xl в пространстве Rn (u).

Если эта гиперплоскость Xl пересекает одну из компонент, она делит ее на две части. Появляется новая компонента.

В то же время эта новая компонента добавляет новое разделение гиперплоскости Xl – новую компоненту внутри гиперплоскости Xl.

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

Так как размерность Xl равна n 1, число этих делений не превосходит (n 1, l 1).

Отсюда получаем рекуррентное соотношение на максимум числа компонент с начальными условиями (1, l) = 2, (n, 1) = 2.

Доказать в виде задачи, что рекуррентное соотношение (1.24) имеет решение:

Для получения последнего неравенства из (1.23) (а также из имеет место при любом n l. Эта оценка следует из цепочки неравенств (1.22). Доказательство теоремы закончено.

Получим верхнюю оценку VC-размерности класса всех многослойных нейронных сетей заданного размера для случая функции активации (t) = sign(t).

Пусть F – некоторый класс иидикаторных функций, определенных на Rn. Эти функции могут быть векторнозначными.

Функцию роста класса F можно записать в виде где F|X – множество всех функций, которые получаются ограничением функций из класса F на конечное множество X.

Необходимая оценка будет следовать из следующего утверждения.

Предложение 1.1. Пусть F 1 и F 2 два класса функций и F = F 1 F 2 – их декартово произведение, а G = F 1 F 2 – класс функций, которые являются композициями функций из этих классов.

Тогда для произвольного m Доказательство. Для доказательства (1) заметим, что для любого X такого, что |X| = m выполнено Доказательства части (2) предоставляется читателю.

Как было замечено в разделе 1.1.3 нейронная сеть может быть представлена в виде набора векторнозначных функций где ni – натуральные числа, i = 1,..., l, fi = (fi,1,..., fi,ni1 ) – набор одномерных функций типа Rni1 R.

Выход нейронной сети задается одномерной функцией – композицией Пусть F есть класс всех таких функций f, которые вычисляются с помощью нейронной сети, F i – класс векторнозначных функций fi : Rni1 Rni и F i,j – класс функций, которые образуют j-ю компоненту этих композиций.

Заметим также, что функции ассоциированные с вершинами i-го слоя являются линейными пороговыми функциями, поэтому VC-размерность класса F i,j равна ni1 + 1 для каждого j.

По предложению 1.1, также по лемме Сауэра, выполнены следующие неравенства:

где – общее число параметров нейронной сети.

Оценим теперь VC-размерность класса F. Пусть m – размер максимального по числу элементов множества, которое полностью разделимо функциями из класса F. Тогда 2m (me)N. Это неравенство выполнено при m = O(N log N ). Таким образом, VCразмерность класса F оценивается как O(N log N ).

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

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

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

1.3.1. Пороговая размерность и ее приложения Пусть F – класс вещественных функций с областью определения Rn, S = ((1, y1 ),..., (l, yl )) – выборка длины l, > 0.

Каждой функции f F сопоставим индикаторную функцию классификации Границей ошибки при классификации примера (i, yi ) с помоx щью вещественной функции f называется величина i = yi f (i ).

Заметим, что i > 0 означает, что классификация с помощью f является правильной. Кроме этого, будем рассматривать величину – границу ошибки классификации с помощью функции f на выборке S. По определению mS (f ) > 0 тогда и только тогда, когда функция f классифицирует S без ошибок и с положительным порогом.

Назовем -покрытием множества функций F относительно множества X = {1,..., xl } любое конечное множество функx ций B такое, что для любого f F существует g B такая, что Пусть N (, F, X) – размер покрытия B, имеющего наименьшее значение величины |B| (минимальное покрытие).

Максимум этих величин по всем множествам X мощности l называется числом покрытия класса F.

По определению errS (f ) – доля ошибок классификации с помощью функции f на выборке S = ((1, y1 ),..., (l, yl )). Эта величина равна доле векторов xi таких, что yi f (i ) 0.

Пусть P – распределение вероятностей на R {1, 1} генерирующее элементы выборки S. Рассмотрим вероятность ошибочной классификации примера (, y) с помощью функции f :

Имеет место теорема – аналог теоремы 1.2.

Теорема 1.6. Для произвольных >0и> при l > 2/.

Доказательство теоремы 1.6 аналогично доказательству теоремы 1.2. Надо только к равенству errS (f ) = 0 добавить более сильное условие mS (f ) (в правой части условия (1.12) леммы 1.4). Аналогичная лемма утверждает, что Лемма 1.6. При l > 2/ 2P 2l {S S : ( f F)(errS (f ) = 0&mS (f ) &errS (f ) > )}.

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

Вторая лемма аналогична лемме 1. Лемма 1.7. При l > 2/ Для доказательства леммы рассмотрим /2-покрытие B множества F относительно двойной выборки S S. Пусть g B приближает функцию f F с точностью до /2. Если mS (f ), то mS (g) > /2. Кроме этого, если errS (f ) = 0 и mS (f ), то errS (g) = 0.

Если функция f ошибочно классифицирует вектор xi, т.е.

yi f (i ) лю тех i, для которых yi g(i ) < /2, где xi находится во второй части двойной выборки S. Отсюда следует неравенство Далее рассуждения аналогичны комбинаторной части доказательства леммы 1.5. Здесь мы оцениваем долю вариантов, при которых некоторая функция g B разделяет первую часть выборки S без ошибок: errS (g) = 0, и более того, с порогом mS (g) > /2, а на второе половине выборки либо делает ошибки, либо имеет порог разделения /2 в доле errS (/2, g) > 2 примеров. Оценка такая же как и в лемме 1.5, а именно, (1.20).

В результате получаем оценку P 2l {S S : ( g B)(errS (g) = 0&mS (g) &errS (/2, g) > )} Из оценок лемм 1.6 и 1.7 получаем оценку теоремы 1.6.

Из теоремы 1.6 получаем Следствие 1.3. Заданы класс F вещественных функций и числа > 0, > 0. Тогда для любого распределения вероятностей P на Rn {1, 1} с вероятностью 1 на случайной выборке S длины l любая функция f F, которая классифицирует S с границей ошибки mS (f ) >, имеет верхнюю границу вероятности ошибочной классификации при всех l.

Каждый класс функций F порождает так называемую пороговую размерность или fat-размерность (fat-shattered dimension). Пусть > 0. Множество X = {1,..., xl } называется -разделимым, если существуют вещественные числа r1,..., rl такие, что для любого подмножества E X существует функция fE F такая, что fE (i ) ri +, если xi E, и fE (i ) < ri, если xi E.

Множество X называется -разделимым на одном уровне, если ri = r для всех i.

Пороговая размерность fat (F) класса F равна размеру самого большого по количеству элементов -разделимого множества X. По определению пороговая размерность класса F зависит от параметра > 0. Класс F имеет бесконечную пороговую размерность, если существуют как угодно большие -разделимые выборки.

Следующая теорема является прямым следствием теоремы 1.10, которая будет доказана в разделе 1.3.2.

Теорема 1.7. Пусть F – класс функций типа Rn [a, b], где a < b. Выберем 0 < < 1 и обозначим d = fat/4 (F). Тогда Теорема 1.7 вместе со следствием 1.3 влечет следующее следствие Следствие 1.4. Пусть F – класс вещественных функций со значениями в отрезке [1, 1], > 0, > 0 и P – распределение вероятностей, генерирующее выборку S. Тогда с вероятностью любая гипотеза f F, для которой mS (f ), имеет верхнюю границу вероятности ошибочной классификации при l d, где d = fat/8 (F).

Для класса всех (однородных) линейных функций с ограниченной областью определения имеет место не зависящая от размерности пространства объектов верхняя оценка пороговой размерности.

Теорема 1.8. Пусть X – шар радиуса R в n-мерном евклидовом пространстве: X = { : || R}, и F – класс линейных однородxx ных функций f () = (w · x), где w 1 и x X. Тогда Доказательство. Допустим, что множество Y = {1,..., xl } является -разделимым с помощью линейных однородных функций из класса F. Тогда для произвольного подмножества Y Y найдется весовой вектор w, w Из неравенства Коши–Буняковского для евклидовой нормы получаем Из (1.25), (1.26) и из неравенства |w Пусть = (1,..., l ) – случайный равномерно распределенный бинарный вектор длины l; i {1, 1} при i = 1,..., l.

Вектор естественным образом определяет разбиение множества Y на два подмножества Y и Y \ Y. Вычислим математическое ожидание квадрата нормы разности (1.27) относительно случайного разбиения множества Y определяемого вектором. Имеем Найдется хотя бы одно подмножество Y, для которого значение нормы разности меньше или равно ее среднего значения:

Вместе с неравенством (1.27) это влечет R l l. Отсюда получаем l (R/)2. Это означает, что fat (F) (R/)2.

Подставляем оценку теоремы 1.8 в оценку следствия 1.4 и получаем следующую итоговую теорему.

Теорема 1.9. Рассмотрим задачу классификации с помощью линейных функций f () = (w· x)+b L, где x Rn, w = 1. Задано число > 0.

Для произвольного распределения вероятностей P, сконцентрированного в шаре радиуса R с центром в начале координат генерирующего выборку S = ((1, y1 ),..., (l, yl )), с вероятностью 1 произвольная гипотеза f L с границей ошибки mS (f ) имеет верхнюю оценку ошибки классификации Оценки теорем 1.8 и 1.9 послужат основой для получения не зависящих от размерности пространства оценок вероятности ошибки обобщения для машин на опорных векторах в теореме 2. из раздела 2.6.1 и в теоремах 2.9 и 2.10 из раздела 2.9.1.

1.3.2. Покрытия и упаковки При составлении данного раздела были использованы лекции Какаде и Тевари [17].

Рассмотрим содержание предыдущего раздела с более общих позиций.

Пусть (X, d) – некоторое метрическое пространство, d(x, y) – расстояние между элементами x, y X.

Пусть A X и B A и > 0. Говорим, что множество B является -покрытием множества A, если для любого a A существует b B такое, что d(a, b) <. Числом покрытия множества A называется функция Nd (, A) = min{|B| : B является -покрытием A}. (1.29) Говорим, что множество B X является отделимым, если для любых a, b B таких, что a = b, будет d(a, b) >. Числом упаковки множества A называется функция Md (, A) = max{|B| : B A является -отделимым}. (1.30) Основные соотношения между числом покрытия и числом упаковки даются в следующей лемме.

Лемма 1.8. Для любых A X и > Доказательство. Пусть M – 2-отделимое подмножество A и N – -покрытие A. По определению множества N для каждого a M найдется b N такое, что d(a, b) <. Если a, a M различные и b, b N им таким образом соответствуют, то b и b также различные, так как иначе было бы b = b и d(a, a ) d(a, b) + d(b, a ) < 2. Это противоречит тому, что любые два различные элемента M находятся на расстоянии большем. Отсюда заключаем, что |M | |N |. Первое неравенство доказано.

Пусть M – максимальное по включению -отделимое подмножество A. Докажем, что M является -покрытием множества A.

Допустим, это не так. Тогда найдется элемент x A такой, что нет ни одного элемента из M в окрестности x радиуса. Добавим x к M и получим строго большее по включению подмножество M {x} множества A, которое также -отделимо. Получаем противоречие с выбором M. Данное противоречие доказывает второе неравенство из условия леммы.

Основная цель данного раздела – доказательство теоремы 1.7.

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

Пусть X – некоторое множество и B = {0, 1,..., b} – конечное множество. Рассмотрим некоторый класс F B X, определенных на множестве X и принимающих конечное число значений из множества B. Рассмотрим метрику на F Две функции f, g F отделены (2-отделены), если l(f, g) > 2.

Иными словами существует x X такое, что |f (x) g(x)| > 2.

Класс F отделим, если любые две функции f, g F отделены.

Пусть X = {x1,..., xn } X – некоторое множество с заданным линейным порядком на его элементах (выборка) и F B X.

По определению класс F строго разделяет множество X, если существует набор s = (s1,..., sn } элементов B такой, что для любого E X существует функция fE F такая, что для любого i.

Говорят также, что F строго разделяет множество X относительно набора s. Размер максимального множества X строго разделимого с помощью класса функций F называется строгой размерностью F и обозначается Sdim(F).

Рассмотрим простую дискретизацию, переводящую произвольную вещественнозначную функцию f : X [0, 1] в функцию, принимающую конечное число значений. Для произвольного вещественного > 0 определим для всех x, а также F = {f : f F}.

Очевидно, что функция f принимает значения в множестве {0, 1,..., 1/}.

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

Число покрытия Nd (, A) и число упаковки Md (, A) были определены согласно (1.29) и (1.30).

Определим специальную метрику на F, связанную с множеством X = {x1,..., xn }, следующим образом:

Рассмотрим соответствующие числа покрытия и упаковки:

Связь между строгой размерностью дискретизированного класса функций и пороговой размерностью исходного класса представлена в следующей лемме.

Лемма 1.9. Пусть F B X и > 0. Тогда Доказательство леммы предлагается в качестве задачи.

Следующая лемма представляет техническую часть основного результата этого раздела.

Лемма 1.10. Пусть |X | = n и B = {0, 1,..., b}. Пусть также F B X и d = Sdim(F). Тогда Доказательство. Допустим, что b 2 и определим функцию t(h, n). Значение этой функции определяется следующим образом.

Рассматриваются все отделимые подклассы F класса функций F, содержащие по h элементов. Понятие отделимости класса функций было определено ранее в этом разделе. Пусть Sh – состоит из всех таких F. Каждый такой класс функций F может строго разделять некоторые множества X X относительно некоторых последовательностей s. Пусть kF – число всех таких возможных пар (X, s) строго разделимых классом F. Полагаем t(h, n) = minF Sh kF.

Эквивалентным образом, функцию t(h, n) можно задаеть формальным условием:

F строго разделяет не менее k (X, s) пар}.

Когда мы говорим, что F строго разделяет пару (X, s), мы имеем ввиду, что F строго разделяет пару X относительно последовательности s.

Лемма 1.11. Если t(h, n) > y и Sdim(F) Доказательство. Допустим, что Ml (2, F) h. Это значит, что существует отделимое множество F F размера h. Так как t(h, n) y, F строго разделяет по-крайней мере y (X, s) пар.

Так как Sdim(F) d, если F строго разделяет пару (X, s), собами, кроме того имеется < bi возможных последовательностей s длины i (из-за строгой разделимости X элементами s не могут быть 0 или b). Таким образом, F строго разделяет менее чем (X, s) пар. Полученное противоречие доказывает лемму.

Из леммы 1.11 следует, что для того, чтобы доказать лемму 1.10, достаточно доказать, что Для того, чтобы доказать неравенство (1.33) предварительно докажем следующее утверждение.

Лемма 1.12.

Доказательство. Для любых двух отделимых функций f и g, |f (x)g(x)| 2 хотя бы для одного x, т.е., эти функции разделяют одноэлементное множество {x}. Таким образом, t(2, n) 1, т.е., неравенство (1.34) выполнено.

Для доказательства (1.35) рассмотрим множество F, содержащее по-крайней мере 2mn(b + 1)2 попарно отделимых функций.

Если такого множества не существует, то t(2mn(b + 1)2, n) = и неравенство (1.35) автоматически выполнено. Разделим произвольным образом функции из F на пары {f, g}. Всего таких пар не менее чем mn(b + 1)2. Пусть P обозначает это множество пар.

Для произвольной пары {f, g} P пусть (f, g) равно одному из тех x, для которых |f (x) g(x)| 2.

bin(x, i, j) = {{f, g} P : (f, g) = x, {f (x), g(x)} = {i, j}}.

Общее число таких множеств не превосходит Напомним, что по условию леммы 1.10 выполнено |X | = n.

Число все пар равно mn(b+1)2. Отсюда должны существовать Определим два множества функций Здесь A, где множество A состоит из пар, есть множество состоящее из элементов всех таких пар.

Ясно, что |F1 | = |F2 | 2m. Класс функций F1 отделим, если рассматривать эти функции на множестве X \ {x }. Действительно, класс F, а значит и класс F1 отделим на X, поэтому для любых двух функций f, f F1 будет |f (x ) f (x )| 2 для некоторого x, причем x X \{x }, так как на x значения этих функций совпадают. Аналогичным образом, класс функций F2 также отделим на области определения X \ {x }.

Следовательно, должны существовать два множества U и V размера строго разделяет пары из U и F2 строго разделяет пары из V.

Очевидно, что любая пара из U V строго разделяется классом F. Пусть (X, s) U V. Тогда пара ({x } X, i +j, s) также строго разделяется посредством F. Это так, поскольку любые функции f F1 и g F2, строго разделяющие X, удовлетворяют из этих функций строго разделяет выбранное подмножество.

f (x) si 1 при x E для некоторого набора s = (s1,..., sn1 ).

Аналогично, пусть g(x) x E для некоторого набора s = (s1,..., sn1 ). При этом f F1 и g F2. Тогда f разделяет E относительно набора s1 = ( i +j, s1,..., sn1 ), если x E, или g разделяет E относительно набора s2 = ( i +j, s1,..., sn1 ), если x E.

Следовательно, класс F строго разделяет пар (X, s). Неравенство (1.35) и лемма 1.12 доказаны.

Переходим теперь к доказательству леммы 1.10. Применяя неравенства (1.34) и (1.35) рекурсивным образом, получим при n > r 1.

Если log y < n, то полагаем r = log y в (1.36) и получаем неравенство (1.10).

превышает число всех функций со значениями в B и областью определения X, |X | = n. В этом случае ни одного отделимого множества F размера 2(n(b + 1)2 ) log y не существует и Таким образом, лемма (1.10) доказана.

Теперь мы можем сформулировать и доказать основное утверждение этого раздела – теорему Алона, Бен-Давида, Сеза-Бьянки и Хаусслера [5].

Теорема 1.10. Пусть F [0, 1]X и [0, 1]. Обозначим d = fat/4 (F). Тогда Доказательство. Используя то, что число упаковки не превосходит числа покрытия, неравенство (1.32) леммы 1.9, а также лемму 1.10, получим следующую цепочку неравенств Заметим, класс функций F /2 удовлетворяет условию леммы 1.10 при b =.

Из неравенства (1.31) леммы 1.9 получаем d f at/4 (F) = d.

Отсюда В частности, log y (ben/d).

Теорема доказана.

Теорема 1.7 из раздела 1.3 является переформулировкой этой теоремы с небольшим ослаблением оценки.

1.4. Средние по Радемахеру В этом разделе мы введем еще одно определение емкости класса функций – среднее по Радемахеру. Это понятие позволяет получить верхнюю оценку ошибки обобщения.

При составлении данного раздела были использованы лекции Какаде и Тевари [17].

Пусть z l = (z1,..., zl ) – некоторая выборка. Пусть элементы выборки принадлежат некоторому множеству X, на котором задано вероятностное распределение P. Мы предположим, что элементы выборки независимо и одинаково распределены согласно распределению P.

Задан класс F равномерно ограниченных функций, определенных на множестве X : a b для всех x X и всех f F, где a < b.

Пусть 1,..., l – независимые бернуллиевские величины, принимающие два значения +1 и 1 с равными вероятностями:

случайные величины называются случайными Радемахера.

Обозначим посредством = B1/2 распределение всего набора 1,..., l длины l.

Выборочным средним Радемахера класса F называется усовное математическое ожидание Вероятностное распределение P на элементах выборки индуцирует вероятностное распределению P l на выборках z l = (z1,..., zl ) длины l.

Средним по Радемахеру класса F называется число Согласно определению среднее по Радемахеру равна среднему значению выборочного среднего по Радемахеру относительно распределения P l.

Приведем ряд свойств средних по Радемахеру, которые будут использоваться при получении верхней оценки ошибки обобщения в разделе 2.7.

Пусть элементы выборки z l = (z1,..., zl ) независимо друг от друга генерируются с помощью вероятностного распределения P. По определению выборочное среднее функции f на выборке z l (z1,..., zl ).

равно Математическое ожидание функции f равно EP (f ) = f (z)dP.

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

Теорема 1.11. Для произвольной функции f F имеет место неравенство личины, распределенные также как случайные величины z l = (z1,..., zl ). Кроме этого, предполагаем, что есть последовательность независимых случайных величин.

Имеет место следующая цепочка равенств и неравенств:

Переход от 2-й строки к 3-й происходит по свойству:

которое в свою очередь следует из свойства: супремум суммы не превосходит суммы супремумов. Появление в 5-й строке i не изменило супремум, так как иатематическое ожидание супремума инвариантно относительно перестановок переменных zi и zi ; по этой же причине мы можем вставить в 6-й строке символ среднего EB1/2.

Неравенство (1.37) доказано.

Приведем два следствия из теоремы 1.11.

Во-первых, неравенство (1.37) можно обратить:

Следствие 1.5. Для произвольной функции f F имеет место неравенство Неравенство ()1.39 прямо следует из неравенства (1.37) и очевидного равенства Rl (F) = Rl (F), где F = {f : f F}.

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

Лемма 1.13. Пусть f : Z l R – функция, удовлетворяющая условию для любого i и для всех z1,..., zl, zi Z, где c1,..., cl – некоторые константы.

Пусть также z1,..., zl – независимые одинаково распределенные (согласно вероятностному распределению P ) случайные величины, принимающие значения в множестве Z.

Тогда имеет место неравенство где EP l – символ математического ожидания по распределению P l на выборках длины l.

Доказательство этой леммы можно найти в работе [23] и в монографии [26].

Так как условие леммы выполнено при замене f на f, выполнено также неравенство Следующее следствие дает равномерную по функциям из класса F оценку разности между математическим ожиданием функции и выборочным средним этой же функции. Эти величины отличаются на удвоенное среднее по Радемахеру класса функций.

Следствие 1.6. Допустим, что значения функций из класса F лежат в интервале [0, 1]. Тогда для произвольного > 0 с вероятнстью 1 для произвольной функции f F выполнено Доказательство. Для заданной f имеет место очевидное неравенство Применим неравенство (1.40) леммы 1.13 ко второму члену (1.43).

Так как значения функции f ограничены единицей, можно взять ci = 1/l при 1 i l. Подставляем эти значения в правую часть неравенства (1.40) и приравниваем ее /2. Получаем 2l. Из неравенства (1.40) следует, что с вероятностью 1 /2 выполнено Неравенство (1.37) утверждает, что Отсюда и из (1.44) получаем Отсюда следует, что с вероятностью 1 /2 выполнено для любой функции f F. Таким образом выполнено первое неравенство (1.42) следствия.

Аналогичным образом, с помощью неравенства (1.41) леммы 1.13 получаем, что с вероятностью 1 /2 выполнено Из неравенств (1.46) и (1.47) получаем, с вероятностью 1 выполнено второе неравенство (1.42) следствия.

В следующей теореме дается оценка среднего по Радемахеру класса F = (F) = {(f ) : f F } композиций функций из F с заданной функцией.

Теорема 1.12. Пусть функция удовлетворяет условию Липшица с константой L:

для всех x, y. Тогда выборочное среднее и среднее по Радемахеру классов F и F связаны неравенствами:

Доказательство. Пусть z l = (z1,..., zl ) – случайная выборка элементов из области определения функций из класса F, распределенная согласно мере P, 1,..., l – набор независимых бернуллиевских случайныех величин со значениями из множества {+1, 1}, и пусть – соответствующее распределение на наборах этих величин.

Преобразования ниже верны при E = E, а также при E = EP l E – соответствующие математические ожидания по распределениям на этих наборах. Таким образом мы сразу докажем оба неравенства (1.48) и (1.49).

По определению (выборочное) среднее по Радемахеру класса функций (F) равно Для простоты рассуждений предполагаем, что L = 1. 9 Нам необходимо доказать неравенство Мы осуществим переход от (1.50) к (1.51) с помощью цепочки неравенств по шагам. На каждом шаге рассматривается последовательность вспомогательных функций (1,..., l ), где каждая функция i есть функция или тождественная функция I.

На первом шаге все функции i =, на последнем шаге все эти функции – тождественные: i = I. Мы также предполагаем, что на каждом шаге, кроме последнего, 1 =. При переходе к следующему шагу очередная функция i = будет заменяться на Можно заменить функцию на /L.

тождественную функцию: i = I. При этом будет выполнена следующая цепочка неравенств:

где набор функций 1,..., l имеет на единицу большее число тождественных функций чем набор 1,..., l.

В цепочке (1.52) при переходе от 1-й строки к 2-й и 3-й было взято математическое ожидание по 1 ; после этого можно попрежнему рассмативать E как математическое ожидание по всему набору, так как теперь переменная 1 отсутствует. При переходе от 4-й и 5-й строки к 6-й и 7-й было использовано замечание, что супремум достигается при неотрицательном значении разности (f (z1 )) (f (z1 )), поэтому можно заменить ее на ее абсолютную величину, после чего, использовать условие Липшица с L = 1. Аналогичное замечание было использовано при переходе от 6-й и 7-й строки к 8-й и 9-й. При переходе от 8-й и 9-й строки к 10-й строке было использовано то же соображение, что и при переходе от 1-й строки к 2-й и 3-й.

Применяя несколько раз цепочку преобразований (1.52) мы получим выражение в котором все i являются тождественными функциями, т.е. сумма (1.53) равна Rl (F).

Первая строка цепочки (1.52) равна Rl ((F)) при E = EP l E или Rl ((F)) при E = E. Таким образом, неравенства (1.48) и (1.49) выполнены и теорема доказана.

1.5. Средние по Радемахеру и другие меры емкости класса функций Укажем связь среднего по Радемахеру с другими известными мерами емкости классов функций – функцией роста BF (l) и числом покрытия N (, F, l).

Связь с функцией роста Нам потребуется следуещее вспомогательное утверждение – лемма Массара:

Лемма 1.14. Пусть A – кончное подмножество Rl и 1,..., l – независимые бернуллиевские случайные величины. Тогда где a = (a1,..., al ).

Доказательство. Имеет место следующая ниже цепочка равенств и неравенств. Обозначим E = E. При переходе от первой строки ко второй используется выпуклость логарифма. При переходе от 7-й строки к 8-й используется неравенство ex + ex 2ex /2. Остальные переходы очевидны:

где r = sup a.

Логарифмируем первую и последнюю строки этого неравенства и получаем неравенство Легко проверяется, что правая часть неравенства (1.54) достигает своего минимума при = 2 ln |A|/r2. Подставляем это значение в правую часть неравенства (1.54) и получаем Лемма доказана.

Связь среднего по Радемахеру с функцией роста устанавливается в следующей теореме.

Теорема 1.13. Пусть F – класс индикаторных функций, т.е.

функций принимающих бинарные значения из множества {1, +1}.

Тогда для всех l.

Доказательство. Пусть E = EP l и бинарная строка a = (a1,..., al ) представляет значения (f (z1 ),..., f (zl )). Имеет место следующая цепочка неравенств:

При переходе от 1-й строки ко 2-й была использована лемма 1.14, при переходе от 2-й строке к 3-й было использовано значение евклидовой нормы бинарного вектора a = l. Здесь же было использовано определение функции роста семейства. Теорема доказана.

Связь с числом покрытия Пусть F – класс функций с областью определения X и с областью значений [1, 1]. На множестве X задана некоторая вероятностная мера. Пусть xl = (x1,..., xl ) – случайная выборка из элементов X.

Рассмотрим норму lxl (f, g) = sup1 i l |f (xi ) g(xi )| на выборке xl и число покрытия N (, F, xl ) относительно этой выборки, которое равно размеру наименьшего по числу элементов множества B F такого, что для любого f F найдется g B так что lxl (f, g) <.

Теорема 1.14. Для выборочного среднего по Радемахеру имеет место неравенство Доказательство. Пусть B – минимальное покрытие класса F относительно выборки xl. Можно считать, что область определения функций из B есть {x1,..., xl }.

Пусть также Из определения покрытия имеем gB B (g) = F. Поэтому Для среднего из последней строки (1.56) выполнено неравенство По лемме 1.14 получаем деления функции g равен l, а значения по абсолютной величине ограничены единицей.

Соединяем вместе неравенства (1.57) и (1.58) и получаем неравенство Так как неравенство (1.59) выполнено для любого > 0, оно выполнено и для нижней грани по > 0. Отсюда получаем неравенство (1.55). Теорема доказана.

Из теоремы 1.14 очевидным образом вытекает аналогичное неравенство между средним по Радемахеру и числом покрытия.

Следствие 1.7.

1.6. Задачи и упражнения 1. Провести полное доказательство лемм 1.4 и 1.5.

2. Пусть Z – некоторое бесконечное множество, – множество всех его подмножеств, содержащих не более k элементов, fA – характеристическая функция подмножества A, т.е.

функция, равная 1 на элементах A, и 0 на элементах его дополнения. Пусть HZ – класс всех характеристических функций. Доказать, что функция роста BHZ (l) удовлетворяет соотношениям при l > k.

3. Найти значения функции роста BH (3), BH (4), BH (5),..., где a) H – класс всех однородных классификаторов;

b) H – класс всех линейных классификаторов;

c) H – класс всех классификаторов, порожденных многочленами 2-го порядка, 3-го порядка и т.д.

4. Привести примеры классов функций – классификаторов, для которых V C-размерность равна. Рассмотреть класс функций F = {sign(sin(tx)) : t R}.

5. Получить оценку 3) из теоремы 1.5 для класса всех линейных функций классификации.

Глава Метод опорных векторов Задача классификации и регрессии с помощью метода опорных векторов – Support Vector Machines (SVM), имеет целью разработку алгоритмически эффективных методов построения оптимальной разделяющей гиперплоскости в пространстве признаков высокой размерности. Оптимальность понимается в смысле минимизации верхних оценок вероятности ошибки обобщения.

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

yi {1, 1}, i = 1,..., l, называется разделимой (отделимой) с помощью гиперплоскости (w · xi ) c = 0, если существуют вектор w единичной длины (|w| = 1) и число c такие, что В том случае, когда разделяющая гиперплоскость (w · xi ) c = существует, определим По определению c1 (w) > c2 (w). Кроме того, c1 (w) > c > c2 (w), если гиперплоскость (w · xi ) c = 0 разделяет выборку.

Определим Тогда (w) = 1 ((c1 (w) c) + (c c2 (w)) равно половине суммы расстояний от ближайших сверху и снизу точек до разделяющей гиперплоскости (w · x) c = 0 (см. (2.1)).

Допустим, что что выборка S разделима, т.е. существует c такое, что выполнено условие (2.1).

Максимум непрерывной функции (w) на компакте {w : |w| 1} существует. Пусть максимум достигается при w = w0.

Лемма 2.1. Пусть указанный выше максимум (w) достига- ется при w = w0. Тогда гиперплоскость (w0 · x) c0 = 0, где c0 = 2 (c1 (w0 ) + c2 (w0 )), отделяет выборку S и находится точно в середине между ближайшими сверху и снизу точками положительной и отрицательной частями выборки.

Доказательство. Действительно, при yi = При yi = Оставшаяся часть леммы предоставляется читателю в качестве задачи.

Назовем гиперплоскость (w0 · x) c0 = 0 оптимальной. Для этой гиперплоскости сумма расстояний от ближайшей к ней (сверху и снизу) точек выборки максимальна среди всех разделяющих S гиперплоскостей.

Лемма 2.2. Оптимальная гиперплоскость – единственная гиперплоскость такая, что сумма расстояний от ближайшей к ней (сверху и снизу) точек выборки максимальна среди всех разделяющих S гиперплоскостей, расположенных на равных от них расстояниях.

Доказательство. Максимум w0 непрерывной функции (w) на компакте |w| 1 достигается на границе, так как в противном случае при w = |w0 | было бы |w | = 1 и (w ) = (w00|) > (w0 ).

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

Докажем, что функция (w) вогнутая. Для этого надо проверить, что для всех 0 1 и w, u, лежащих в единичном шаре.

Имеют место неравенства для произвольных функций f и g и множества I.

По определению Из (2.6) при f (i) = (w · xi ) и g(i) = ( · xi ) имеем Аналогичное неравенство имеет место для максимумов.

Вычитанием соответствующих неравенств получаем неравенство (2.5).

Рассмотрим эквивалентное определение оптимальной разделяющей гиперплоскости. На основе этого определения будет разработан алгоритмически эффективный метод построения оптимальной гиперплоскости в виде задачи квадратичного программирования. Точный алгоритм, построенный по этому методу, будет приведен в следующем разделе.

Найдем вектор w0 и число b0 так, чтобы было где i = 1,..., l, и величина w0 была бы минимальна при этих ограничениях.

Теорема 2.1. Вектор w0, удовлетворяющий условиям (2.7) и имеющий минимальную норму, определяет оптимальную разw деляющую гиперплоскость с весовым вектором w0 = w0. При этом Доказательство. Имеем так как по (2.7):

Остается доказать, что (w0 ) > w0 невозможно. Допустим проw ство так как w0 = 1.

Докажем, что вектор w1 удовлетворяет условию (2.7) при b0 = c1 (w1 )+c2 (w1 ). Имеем при yi = 1 :

Случай yi = 1 разбирается аналогичным образом.

Отсюда получаем противоречие, так как вектор w1 имеет меньПоэтому (w ) = 1.

По выбору w По теореме 2.1 величина (w0 ) = w0 равна расстоянию от ближайших точек (положительной и отрицательной) части выборки до оптимальной гиперплоскости которая расположена на равных расстояниях между гиперплоскостями оптимально ограничивающими точки положительной и отрицательной частей выборки. Уравнение оптимальной гиперплоскости также можно записать в виде 2.2. Алгоритм построения оптимальной гиперплоскости В этом разделе мы приведем алгоритм построения оптимальной гиперплоскости.

Две группы условий (2.7) запишем в виде Согласно результатам предыдущего раздела, для нахождения оптимальной гиперплоскости мы должны минимизировать норму весового вектора w при ограничениях (2.8).

В разделе 2.10 (ниже) указано, что для решения квадратичной задачи оптимизации при ограничениях (2.7) (или эквивалентных им ограничениям (2.8)) составим лагранжиан где i 0 – множители Лагранжа.

Для того, чтобы найти седловую точку лагранжиана (2.9), необходимо минимизировать его по переменным w и b, а после этого, максимизировать по множителям Лагранжа при условиях Необходимое условие минимума лагранжиана имеет вид Из (2.10) – (2.11) следует, что Подставим (2.12) в (2.9) и полагаем W ( ) = L(w, b, ). С учетом (2.13) получим Для нахождения оптимальной гиперплоскости нам надо максимизировать функцию (2.14) при условиях (2.13) и i 0, где Пусть максимум достигается при i = i, i = 1,..., l. Тогда решение задачи поиска оптимальной гиперплоскости имеет вид При этом Оптимальные решения w0 и b0 должны удовлетворять условиям Каруша–Куна–Таккера Отсюда следует, что i > 0 может быть только для тех i, для которых yi ((w0 · xi ) + b0 ) 1 = 0, т.е. для тех векторов, которые лежат на гиперплоскостях (w0 · xi ) + b0 = ±1. Такие векторы называются опорными векторами (support vectors). Вектор весов w0 Рис. 1.1. Опорные векторы расположены на граничных гиперплоскостях H1 и H представляет собой линейную комбинацию опорных векторов xis, s = 1,..., k, где k – число опорных векторов Оптимальная гиперплоскость имеет вид Остальные, неопорные векторы, можно не принимать во внимание, например, их можно изменить, при этом оптимальная гиперплоскость не изменится.

Приведем также некоторые соотношения с опорными векторами.

а также Суммируя (2.16) получим По (2.11) второе слагаемое этой суммы равно 0. Отсюда, используя (2.18), получаем 2.3. Оценка вероятности ошибки обобщения через число опорных векторов Выше было показано, что оптимальная разделяющая гиперплоскость определяется не всеми векторами выборки S, а только опорными векторами.

Можно рассматривать переход от выборки S к разделяющей гиперплоскости (S) как схему сжатия информации, содержащейся в выборке S.

Небольшое число опорных векторов и их признаков S определяет ту же гиперплоскость, что и вся выборка S, т.е. (S) = (S).