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

жеств индексов элементов выборки. Каждое такое подмножество определяет функцию классификации hS. Для каждой такой функции классификации hS вероятность того, что она согласована с остальными l d точками, но имеет ошибку обобщения >, ограничена (1 )ld exp( (l d)). Тогда вероятность того, что какая-нибудь функция классификации hS, построенная с помощью схемы сжатия по подмножеству размера d, согласована с l векторами и имеет ошибку обобщения больше чем, ограничена величиной Таким образом, мы доказали теорему Теорема 2.2. Пусть задана некоторая схема сжатия информации (S). Тогда для любого распределения вероятностей P на X {1, 1}, с P l -вероятностью 1 на случайной выборке S размера l функция классификации hS, построенная с помощью схемы сжатия по подмножеству выборки размера d, имеет ошибку обобщения не более Из этой теоремы следует, что при d > 2 и при достаточно больших l где d – число опорных векторов.

2.4. SVM-метод в пространстве признаков Задана выборка S = ((1, y1 ), (2, y2 ),..., (l, yl )). Метод SVM основан на следующей идее. Векторы выборки x1,..., xl, принадлежащие пространству Rn, отображаются в пространство более высокой размерности – пространство признаков (feature space) с помощью некоторого нелинейного отображения, выбранного априори:

Получаем векторы (1 ),..., (l ) в пространстве признаков Заметим, что отображение (2.19) может быть необратимым.

Исходное пространство Rn переходит при отображении x () в некоторое подмножество пространства признаков R В пространстве RN будет строиться оптимальная гиперплосx x кость, разделяющая векторы (1 ),..., (l ).

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

Вводим новые переменные в пространстве признаков Всего имеется N = 2n+ n(n1) таких переменных. Таким образом, мы построили нелинейное отображение пространства Rn в пространство RN.

Прообразом разделяющей гиперплоскости в пространстве признаков Z = RN :

при отображении x () = z является поверхность второго порядка в исходном пространстве Rn :

где (ji, ki ) – пара натуральных чисел с номером i в какой-нибудь взаимно однозначной нумерации всех пар натуральных чисел n.

Рассмотрим теперь общий случай. Пусть задано отображение (2.19) исходного пространства Rn в пространство признаков В координатах это отображение записывается в виде zj = j (), x Элементы выборки x1,..., xl исходного пространства Rn пеx1 ),..., (l ) пространства признаков RN.

реходят в вектора ( Используя метод построения разделяющей гиперплоскости, изложенный в разделе 2.2, построим гиперплоскость в пространстве признаков RN :

разделяющую векторы (1 ),..., (l ).

Эта гиперплоскость имеет своим прообразом в пространстве Rn, в общем случае нелинейную, поверхность Используя представление функции классификации в двойственной форме, представим вектор весов разделяющей гиперплоскости в пространстве признаков в виде линейной комбинации опорных векторов из множества {(i ) : i > 0}:

В координатах это представление имеет вид при j = 1,..., N. Число слагаемых в этой сумме не зависит от размерности пространства признаков.

Подставим (2.22) в (2.21) и получим выражение для нелинейной поверхности, которая является прообразом в пространстве Rn разделяющей гиперплоскости, построенной в пространстве признаков RN :

где Таким образом, все рассуждения для линейных SVM-машин (оптимальных гиперплоскостей) в пространстве Rn годятся и для нелинейных машин в том же пространстве, если мы заменим скалярное произведение (i · x) в двойственном представлении опx тимальной гиперплоскости (2.17) :

на функцию K(i, x), которая задается выражением (2.24) и коx торая будет называться ядром.

Отметим, что вычисление нелинейной функции соответствующей гиперплоскости (2.23) требует всего l операций и не зависит от размерности N пространства признаков. Из этой формулы также видно, что для построения нелинейного классификатора в исходном пространстве Rn с помощью линейного классификатора в пространстве признаков нам не нужно знать отображение x (), а достаточно только знать ядро K(i, x).

Для решения прямой задачи классификации формально мы строим в пространстве RN гиперплоскость, разделяющую образы векторов x1,..., xl выборки. При решении задачи построения оптимальной гиперплоскости нам надо решить двойственную задачу – максимизировать функцию W (), заданную выражением (2.14).

Эта функция, с учетом определения ядра, упрощается следующим образом:

Таким образом, для нахождения оптимальной гиперповерхности (2.25), разделяющей выборку ((1, y1 ),..., (l, yl )) в пространстве n, нам надо максимизировать нелинейную функцию (2.26) при условиях (2.13) и i 0, i = 1,..., l. При этом, нам не требуется знание N -мерных векторов (1 ),..., (l ), достаточно знать, что их попарные скалярные произведения K(i, xj ) вычисляются с помощью ядра.

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

2.5. Ядра В этом разделе рассмотрим свойства ядер более подробно. Пусть X – произвольное множество. В общем случае под ядром мы понимаем произвольную функцию K(x, y) отображающую X X в множество всех действительных чисел R, которая может быть представлена в виде скалярного произведения где – отображение множества X в некоторое пространство признаков снабженное скалярным произведением.

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

Первый пример: K(, y ) = ( · y )d или K(, y ) = (( · y ) + c)d – полиномиальные ядра.

Пример. Рассмотрим отображение из Rn в R 2 :

Тогда K(, y ) = (()· ()) = 1+ Экспоненциальное ядра можно разложить в ряд Тейлора в виде бесконечной суммы полиномиальных ядер:

Экспоненциальное ядро трансформируется в Гауссово ядро следующим образом:

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

Пусть – конечный алфавит. Слово s в этом алфавите – это произвольная конечная последовательность букв s = s1 s2... sn ;

– множество всех слов в алфавите, включая пустое слово.

|s| = n – длина слова s ; длина пустого слова равна 0.

Пусть n – множество всех слов (последовательностей) длины n. По определению = n. n= Также, st – это слово, полученное конкатенацией слов s и t, s[i : j] = si si+1... sj.

Слово u является подсловом (подпоследовательностью) слова s, если существует последовательность индексов = (i1,..., i|u| ) такая, что j = 1,..., |u|; Это также обозначаем u = s[ Длиной подпоi].

следовательности u в s называется число l( = i|u| i1 + 1.

Мы предполагаем, что на всех словах задан линейный порядок: всем словам меньшей длины предшествуют слова большей длины, а все слова одной длины упорядочены лексикографичеn ски. Тогда можно рассмотреть пространство признаков Fn = R – множество всех векторов действительных чисел, индексами которых являются все слова длины n.

Определим отображение из множества всех слов в пространство признаков где при 0 < 1, которое представляет собой числа всех вхождений подпоследовательностей из n букв в последовательность s, взвешенные в соответствии с длинами этих вхождений в s.

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

При таком задании вычисление ядра Kn (s, t) требует большого числа вычислительных операций. Существуют рекурсивные схемы для вычисления подобных сумм за приемлемое полиномиальное время (см. [10]).

Ядра такого типа используются при классификации текстов.

Более подробно о ядрах см. монографию Шолькопфа и Смолы [27].

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

Предварительно рассмотрим пример из раздела 2.4.

Пусть функция K(, y ) = (() · ()) задана некоторым отобx ражением из евклидова пространства Rn в евклидово пространство признаков RN.

По определению функция K(, y ) является симметричной: K(, y ) = K(, x) для всех x и y. Кроме этого, выполнено еще одно важное свойство: для любой последовательности элементов x1,..., xn и любой последовательности вещественных чисел 1,..., n выполнено В общем случае сформулируем свойство (2.29) в качестве определения. Пусть X – произвольное множество. Функция K : X X R называется положительно определенной, если для любого набора элементов x1,..., xn и любого набора вещественных чисел 1,..., n выполнено Согласно (2.29) функция K(, y ) = (() · ()) является положиx тельно определенной.

Матрица (K(xi, xj )n Гильбертово пространство порожденное воспроизводящим ядром По каждой симметричной положительно определенной функции K(x, y) определим некоторое каноническое функциональное гильбертово пространство F. Определим отображение : X RX из множества X в множество всех функций из X в R:

По определению (x) это функция, для которой: Kx (y) = K(x, y) для всех y. Определим пространство функций, порожденное всеми линейными комбинациями где n, i R и xi X – произвольные. Операции сумма и умножение на константу определяются стандартным образом. Опреn Легко проверить, что выражение (2.31) можно представить в виде выражение (2.31) определено однозначно и не зависит от представления функций f и g в виде линейных комбинаций. Отсюда также следует, что функция (f · g) является билинейной по f и g. Она также симметричная: (f · g) = (g · f ) для всех f и g. Она также является положительно определенной.

Предварительно заметим, что Учитывая это свойство получаем, что для любого набора функций f1,..., fn и набора 1,..., n R коэффициентов будет выполнено условие положительной определенности функции (f · g):

По свойству (2.31) выполнено (Kx · f ) = f (x) и, в частности, (Kx · Ky ) = K(x, y) для всех x и y. Из-за этих свойств симметричная положительно определенная функция K(x, y) называется воспроизводящим ядром.

Из этих свойств и из свойства (2.30) также следует, что В частности, из (f · f ) = 0 следует, что f (x) = 0 для всех x.

Функция f = (f · f ) является нормой, так как она определена по скалярному произведению. Рассмотрим пополнение множества всех линейных комбинаций (2.30) относительно этой нормы до полного метрического пространства F. Полученное гильбертово пространство называется гильбертовым пространством порожденным воспроизводящим ядром (Reproducing Kernel Hilbert Space – RKHS).

Другой вариант определения RKHS заключается в следующем. RKHS – это гильбертово пространство F функций на X, которое обладает следующим свойством: функционал f f (x) является непрерывным линейным функционалом. По теореме Рисса– Фишера для каждого x X существует элемент Kx F такой, что f (x) = (Kx · f ). Воспроизводящее ядро определяется K(x, y) = (Kx · Ky ).

тельно определенным и поэтому по нему можно определить каноническое гильбертово пространство RKHS и соответствующее отображение в это пространство.

Заметим без доказательства, что хотя ядро, определенное по некоторому отображению с помощью равенства (2.27), является симметричным и положительно определенным, восстановленное по нему отображение в каноническое гильбертово пространство F может не совпадать с исходным отображением. С другой стороны, каждому симметричному положительно определенному ядру соотсетствует единственное каноническое гильбертово пространство RKHS [6].

Теорема о представителе Теорема о представителе (Representer theorem) показывает, что решения широкого класса оптимизационных задач можно представить в виде линейных комбинаций значений ядер в точках обучающей выборки. Эта теорема была доказана Киммельдорфом и Вахбой [19]. См. также [27].

Теорема 2.3. Пусть X – некоторое множество объектов и S = ((x1, y1 ),..., (xl, yj )) – обучающая выборка, где (xi, yi ) X R.

Пусть K(x, x ) – положительно определенное ядро на X X и F – соответствующее единственное каноническое гильбертово пространство RKHS с нормой ·.

Заданы также функция потерь c : (X 2 R)l R {} и некоторая строго монотонно возрастающая функция на множестве всех неотрицательных вещественных чисел.

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

Пример такого риск функционала для задачи регрессии в пространстве признаков f F:

где > 0.

Доказательство. Напомним, что Kxi = K(xi, ·) – функция, порожденная ядром. Любая функция f F представляется в виде f (x) = (f · Kx ) для всех x.

Рассмотрим разложение линейного пространства F в прямую сумму конечномерного пространства, порожденного всеми линейными комбинациями функций Kxi, i = 1,..., l, и его ортогонального дополнения. Тогда любая функция f F представляется в виде:

Вычислим значения f (xj ) для всех j = 1,..., l:

Здесь важно, что значение функции f (xj ) не зависит от элемента f из ортогонального дополнения. Таким образом, значение главной части c((x1, y1, f (x1 )),..., (xl, yj, f (xl ))) регуляризованного функционала (2.32) не зависит от f.

ляется строго монотонной, выполнено причем равенство достигается тогда и только тогда, когда f = 0. Поэтому в точке минимума функционала (2.32) должно быть f = 0. Отсюда решение задачи минимизации функционала (2.32) должно иметь вид (2.33):

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

Теорема 2.3 показывает, что для решения задачи (2.32) функциональной минимизации в произвольном RKHS (которое может оказаться бесконечномерным) достаточно решить задачу минимизации в конечномерном пространстве Rn.

Пример риск функционала, соответствующего оптимизационной задаче SVM:

где xi Rn и yi {1, +1} при i = 1,..., l. Соответствующее пространство признаков F порождается ядром K(x, x ). Функция f F, минимизирующая функционал (2.32), имеет вид 2.6. Случай неразделимой выборки Предварительно получим верхнюю оценку ошибки обобщения для случая, когда выборка не полностью разделена функцией классификации. Эта оценка послужит основой для постановки соответствующей оптимизационной задачи построения функции классификации.

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

Задан класс F функций типа X R, с помощью которых производится классификация. Область определения X функций из F является подмножеством Rn. По каждой функции f F определим индикаторную функцию классификации Задана выборка S = ((1, y1 ),..., (l, yl )). Пусть i = yi f (i ) – граница ошибки примера (i, yi ) X {1, 1} относительно функции f F. Заметим, что i > 0 означает, что классификация с помощью функции f является правильной.

Распределение ошибок на выборке S = ((1, y1 ),..., (l, yl )) определяется вектором MS (f ) = (1,..., l ). Пусть – граница ошибки классификации выборки S посредством f. Величина mS (f ) > 0 тогда и только тогда, когда f строго разделяет S без ошибок.

Пусть > 0. Переменная мягкого отступа (margin slack variable) примера (i, yi ) X {1, 1} для пороговой функции f и границы ошибки определяется как Заметим, что из i > следует, что классификация примера (i, yi ) является ошибочной.

Вектор = (1,..., l ) называется вектором переменных мягкого отступа для выборки S = ((1, y1 ),..., (l, yl )).

По определению yi f (i ) + i для всех i.

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

Если i >, то yi f (i ) < 0, т.е. классификация примера (i, yi ) с помощью f является ошибочной. В этом случае, велиx чина i отражает степень удаленности примера (i, yi ) от разx деляющей гиперплоскости – она тем больше, чем больше ошибка классификации.

i = 0 тогда и только тогда, когда yi f (i ) ; в этом случае классификация правильная и даже с некоторым запасом.

Случай 0 < i является промежуточным, в этом случае классификация 0 < yi f (i ) – правильная, но с очень маленьx ким порогом, например, это может быть вследствие наличие шума в исходных данных.

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

Если норма вектора положительна, то выборка не разделима классификатором f () с порогом > 0 и теорема 1.9 в этом случае прямо не применима. Однако в случае линейного классификатора можно сделать выборку разделимой, если перейти к эквивалентной задаче в пространстве большей размерности. Этот результат, принадлежащий Шо-Тэйлору и Кристианини [25] представлен в следующей ниже теореме.

Теорема 2.4. Пусть L – класс всех линейных функций вида L() = (w · x) + b с единичным весовым вектором w = 1. Пусть > 0. Тогда существует константа c такая, что для произвольного распределения вероятностей P на X {1, 1} с носителем внутри шара радиуса R и с центром в начале координат с P l -вероятностью 1 произвольная функция f L имеет на где – вектор переменных мягкого отступа относительно гиперплоскости L и порога > 0, а l 64(R+2 ).

Доказательство. Рассмотрим линейный классификатор f () = x (w · x) + b, где w = 1. Из определения переменной мягкого отступа = (1,..., l ), определенной для этого классификатора и выборки S = (1,..., xl ), будет Пусть > 0 – параметр, значение которого мы оптимизируем позже. Заменим векторы обучающей выборки x1,..., xl размерности n на вспомогательные векторы x1,..., xl размерности n+l, которые определяются следующим образом:

при i = 1,..., l, где (n + i)-я координата вектора xi равна, а остальные дополнительные координаты равны 0. Полученную выборку обозначим S = ((1, y1 )..., (l, yl )).

Гиперплоскость f () = (w · x) + b заменяем на гиперплоскость а x – произвольный вектор размерности n + l.

Из условия (2.35) следует, что новая выборка S оказвается разделенной новым классификатором (2.36) с порогом :

Имеется в виду шар в пространстве Rn, которому принадлежат классифицируемые элементы x1,..., xl выборки S.

Для того, чтобы применить к новой выборке и новому классификатору теорему 1.9 из раздела 1.3, необходимо нормировать направляющий вектор гиперплоскости (2.36). Имеет место равенство Кроме того, все векторы xi содержатся в шаре радиуса R, где После нормировки условие (2.37) превращается в условие при i = 1,..., l. Отсюда следует, что главный множитель из оценки следствия 1.4 имеет вид Преобразуем Минимум этого выражения достигается при 2 = R, а само выражение приобретает вид Применяя теорему 1.9 из раздела 1.3, получаем оценку (2.34) при l 64(R+2 ). Теорема доказана.

2.6.2. Оптимизационные задачи для классификации с Случай квадратичной нормы ма, рассматривается задача оптимизации с переменными мягкого отступа i, i = 1,..., l.

Найдем векторы w, и число b, так чтобы при i = 1,..., l. Константа C определяет баланс между двумя частями функционала.

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

Заметим, что условие i 0 можно опустить, так как оптимальное решение w,, b, где некоторые i < 0, является оптимальным и при i = 0.

Лагранжиан задачи (2.38) – (2.40) имеет вид где i 0 – множители Лагранжа.

Соответствующая двойственная задача формулируется путем дифференцирования лагранжиана а также подстановкой этих соотношений в (2.41) :

Таким образом, мы должны максимизировать по величину при условиях i 0, i = 1, 2,... l, где ij = 1 при i = j и ij = 0 при i = j. Соответствующие условия Каруша–Куна–Таккера имеют вид Согласно (2.42) вектор весов выражается в виде линейной комбинации опорных векторов:

Из условий Каруша–Куна–Таккера следует, что i = 0, если yi ((w· xi )+b) > 1, при этом i = 0. Эти векторы правильно классифицируются и лежат с внешней стороны относительно граничных гиперплоскостей. Опорными являются те векторы xi, для которых выполнено yi ((w·i )+b) 1, при этом i 0 и i 0. Это те вектоx ры, которые лежат на граничных гиперплоскостях или же неправильно ими классифицируются, в этом случае yi ((w · xi ) + b) < и i > 0.

Сформулируем задачу оптимизации для пространства признаков, заданного некоторым ядром K(i, xj ).

Теорема 2.5. Даны пространство признаков, определенное ядром K(i, xj ), и обучающая выборка S = ((1, y1 ),..., (l, yl )).

Пусть вектор параметров является решением задачи оптимизации:

Тогда соответствующая разделяющая поверхность имеет вид где b находится из условия yi f (i ) = 1 i /C для произвольного i такого, что i = 0.

Функция классификации sign(f ()) разделяет элементы выx борки так же, как соответствующая гиперплоскость, полученная в результате решения задачи оптимизации (2.38) – (2.40) в пространстве признаков, определенном ядром K(, z ), где переx менные отступа определяются для границы ошибки:

Для вычисления b используем равенства i = Ci, также условия Каруша–Куна–Таккера:

Величина (w) = |w|, определяющая расстояние между гиперплоскостями (w · xi ) + b) = ±1 (в ядерном случае) определяется следующим образом:

В (2.45) можно заменить ядро K(i, xj ) на и далее использовать методы построения оптимальной гиперплоскости, приведенные выше.

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

Применим теорему 2.4. Оценка вероятности ошибки (2.34) имеет место для пороговых линейных функций с единичным весовым вектором w. Для того чтобы ее применить к задаче (2.38) – (2.40), поделим обе части неравенства (2.39) на w, где w – оптимальное решение задачи. Тогда в (2.34) надо взять в качестве i величину i / w, а = 1/ w. Получим новую версию вероятности ошибки Рис. 1.2. Опорные векторы расположены на граничных гиперплоскостях или же неправильно ими классифицируются (2.34) :

Неравенство (2.47) показывает, что для минимизации верхней оценки вероятности ошибки обобщения нам действительно необходимо минимизировать величину (2.38).

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

Находим векторы w, и число b, так чтобы при i = 1,..., l. Константа C определяет баланс между двумя частями функционала.

Соответствующий лагранжиан имеет вид Соответственная двойственная задача получается путем приравнивания к нулю производных:

Подставляем решения этих уравнений в прямую задачу и получаем двойственное представление задачи в виде задачи максимизации функционала:

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

Единственное отличие от задачи с квадратичной нормой заключается в том, что условие C i ri = 0 вместе с условием ri 0 вынуждает неравенство i C. В то же время i > 0 выполнено только при ri = 0. Отсюда следует, что i = C для всех таких i. Таким образом, условия Каруша–Куна–Таккера имеют вид Согласно этим условиям переменная мягкого отступа i отлична от нуля только при i = C.

Опорные векторы – это те векторы xi, где i > 0 (в таком случае i = C). Для них выполнено условие yi ((i · xj ) + b) 1 и i 0. Это те векторы, которые лежат на границах гиперплоскостей или неправильно ими классифицируются. Легко видеть, что расстояние от такого вектора до соответствующей разделяющей гиперплоскости равно (см. рис. 1.2).

Для произвольного ядра получаем следующее утверждение.

Теорема 2.6. Даны обучающая выборка S = ((1, y1 ),..., (l, yl )) и пространство признаков, определенное ядром K(i, xj ). Пусть вектор параметров является решением задачи оптимизации:

Тогда соответствующая разделяющая поверхность имеет вид где b находится из условия yi f (i ) = 1 для произвольного i таx кого, что C > i > 0.

Тогда функция классификации sign(f ()) разделяет элементы выборки так же, как соответствующая гиперплоскость, полученная в результате решения задачи оптимизации (2.48) – (2.49) в пространстве признаков, определенном ядром K(, z ), где переx менные мягкого отступа определены для границы ошибки:

Таким образом, задача оптимизации (2.48) – (2.49) эквивалентна задаче оптимизации (2.38) – (2.40) с одним дополнительным условием, что i C. По этой причине эти ограничения называются квадратными (box constraints), так как они требуют, чтобы каждое i находилось внутри квадрата со стороной C, расположенного в положительном октанте.

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

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

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

В этом случае рассматривается задача оптимизации:

где i = 1,..., l. Константа C определяет баланс между двумя частями функционала.

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

2.7. Среднее по Радемахеру и оценка ошибки классификации В этом разделе будут получены оценки вероятности ошибки обобщения для функции классификации линейной в пространстве признаков, заданном некоторым ядром. 2 Напомним основные понятия теории пороговой классификации. Задан класс F функций типа X R, с помощью которых производится классификация.

В наших приложениях область определения X функций из F является подмножеством Rn. По каждой функции f F определим индикаторную функцию классификации В наших приложениях x – вектор из Rn.

Задана обучающая выборка S = ((1, y1 ),..., (l, yl )), где xi Rn и yi {1, 1}.

Материал данного раздела использует результаты из монографии ШоТэйлора и Кристианини [26].

Задано отображение : Rn RN заданное ядром K(, y ). x Пусть F – класс всех функций линейных в пространстве признаков RN с ограниченным весовым вектором. Каждая функция из класса F имеет вид f () = (w · ()) + b, где w, () RN и w 1. Для простоты полагаем b = 0.

Пусть K = (K(i, xj ))n ментах для выборки S; tr(K) = i=1 K(i, xi ) – след матрицы Приведем оценку выборочного среднего Радемахера для класса F относительно обучающей выборки S.

Теорема 2.7. Выборочное среднее Радемахера класса F относительно обучающей выборки S = ((1, y1 ),..., (l, yl )) удовлетвоx x ряет неравенству Доказательство. Имеет место следующая цепочка равенств и неравенств:

Здесь при переходе от 2-й строки к 3-й мы использовали неравенство Коши–Буняковского, при переходе от 3-й строки к 4-й было использовано определение нормы вектора. При переходе от 4-й строки к 5-й было использовано неравенство Йенсена, при переходе от 5-й строки к 6-й мы использовали независимость случайных величин i, а также E(i ) = 0 и E(i j ) = E(i )E(j ) = 0 при i = j. Теорема доказана.

Напомним, что число i = yi f (i ) называется границей ошибx ки примера (i, yi ) X {1, 1} относительно функции f F.

Заметим, что i > 0 означает, что классификация с помощью функции f является правильной.

Задана выборка S = ((1, y1 ),..., (l, yl )). Пусть задано число > 0. Переменная мягкого отступа примера (i, yi ) для пороговой функции f и границы ошибки определяется как Здесь (x)+ = max{0, x}. Напомним, что из i > следует, что классификация примера (i, yi ) является ошибочной.

Вектор = (1,..., l ) называется вектором переменных мягкого отступа для выборки S = ((1, y1 ),..., (l, yl )).

Определим вспомогательную функцию f (, y) = yf (). Пусть Предполагаем, что элементы выборки S генерируются независимо друг от друга с помощью вероятностного распределения P. Легко проверить, что Пусть K = (K(i, xj ))n для выборки S.

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

Теорема 2.8. Для произвольного > 0 с вероятностью выполнено Заметим, что правая часть неравенства (2.54) является случайной величиной. Матрица K построена по случайной выборке S. Переменные мягкого отступа i также зависят от элементов выборки xi и поэтому также являются случайными величинами.

Доказательство. Напомним, что > 0 – порог функции классификации. Определим вспомогательную функцию g : R [0, 1]:

Из определения этой функции следует, что g(r) (r). Отсюда и по следствию 1.6 с вероятностью 1 выполнено По определению переменной мягкого отступа (2.53) выполнено при 1 i l.

По теореме 1.12, где L = 1/, имеем Из неравенства (2.55) и неравенства (2.52) теоремы 2.7 следует, что с вероятностью 1, Теорема доказана.

В частности, если функция f () разделяет выборку S без ошиx бок, то имеет место оценка:

Следствие 2.1. Допустим, что функция f () разделяет выборx ку S без ошибок, а также выполнены все приведенные выше предположения. Тогда для произвольного > 0 с вероятностью выполнено Оценка (2.54) по порядку уступает аналогичной оценке, полученной с помощью понятия пороговой размерности. Пусть xi R для всех 1 i l. Для малых своих значений величина по порядку больше главного члена оценки (1.28) теоремы 1. или главного члена оценки (2.34) теоремы 2.4, имеющих порядок O l 2. Оценки (1.28) и (2.34) были получена в рамках теории пороговой размерности классов функций.

2.8. Задача многомерной регрессии 2.8.1. Простая линейная регрессия Пусть задана обучающая выборка S = ((1, y1 ),..., (l, yl )), где Задача линейной регрессии заключается в нахождении линейной функции наилучшим образом интерполирующей элементы выборки S. Геометрически данная функция представляет собой гиперплоскость, которая приближает точки yi на аргументах xi при i = 1,..., l.

Данная задача была решена Гауссом и Лежандром еще в XVIII веке при помощи минимизации суммы квадратов разностей значений функции f (i ) и точек yi при i = 1,..., l. Теория обобщеx ния для данного метода хорошо представлена в математической статистике для случая линейной модели генерации данных с гауссовским случайным шумом.

В дальнейшем произвольный вектор x также будет рассматриваться как матрица типа (n 1), т.е. как вектор-столбец Этот же вектор, записанный в виде строки (x1,..., xn ), т.е. в виде транспонированной матрицы типа (1n), будет записываться как x. Произведение двух матриц A и B обозначается AB без точки между ними. Мы часто будем отождествлять скалярное произведение векторов ( · z ) и матрицу x z :

типа (11) с единственным элементом, равным этому скалярному произведению.

Согласно методу наименьших квадратов, минимизируем квадратичную функцию потерь:

Обозначим w – расширенный вектор-столбец весовых коэффициентов и свободного члена Аналогичным образом, обозначим x – расширенный вектор-столбец В новых расширенных переменных функция регрессии имеет однородный вид без свободного члена:

Рассмотрим матрицу типа (l (n + 1)), строками которой являются расширенные векторы-строки xi = (i, 1) переменных Вводим также l-мерный вектор-столбец значений интерполяции ся остатками. Вектор-столбец остатков имеет вид y X · w, а функционал (2.57) можно записать в матричном виде как квадрат нормы вектора-столбца остатков:

Здесь и далее для произвольной матрицы A посредством A обозначаем транспонированную матрицу A.

Теперь задача регрессии может быть записана в виде задачи минимизации квадрата нормы вектора остатков:

Геометрически это может интерпретироваться так же, как поиск проекции наименьшей длины вектора y на подпространство (гиперплоскость), порожденное векторами – столбцами матрицы X.

Для поиска минимума приравниваем частные производные этого функционала (по переменным w1,..., wn, b) к нулю. Получим систему из n + 1 уравнений Преобразуем эту систему к виду Если матрица X X обратима, получаем решение этой системы:

2.8.2. Гребневая регрессия Другой метод, обеспечивающий численную устойчивость – гребневая регрессия (ridge regression), был рассмотрен Хоэрлом и Кеннардом.

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

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

Решение задачи гребневой регрессии в прямой форме Для нахождения экстремума приравниваем к нулю частные производные L(w) по wi, i = 1,..., n + 1, В матричной форме это уравнение имеет вид Решение записывается в матричной форме:

где I – единичная матрица.

Матрицы X X, I и I + X X имеют размер (n + 1) (n + 1).

X является положительно определенной, т.е.

Матрица X для любого вектора z. Это следует из равенства При добавлении к матрице X X матрицы I, при > 0, новая матрица становится строго положительно определенной при z = Известно, что любая положительно определенная матрица обратима. Поэтому решение задачи гребневой регрессии всегда существует при > 0.

При = 0 матрица X X может оказаться необратимой. В этом случае решение задачи регрессии не является единственным. Поэтому гребневая регрессия при > 0 численно существенно проще, чем простая регрессия. Кроме того, параметр играет роль штрафа за большую норму вектора весов w.

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

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

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

2.9. Регрессия с опорными векторами 2.9.1. Ошибка обобщения при регрессии Задача регрессии заключается в нахождении функции f (), ко- x торая аппроксимирует отображение из некоторого подмножества X Rn в множество действительных чисел R. Данная функция определяется по обучающей выборке. Соответствующая теория обобщения дает вероятность ошибки аппроксимации на тестовой выборке.

Пусть S = ((1, y1 ),..., (l, yl )) – обучающая выборка, xi X и yi R.

Напомним, что разности |f (i ) yi | называются остатками.

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

Пусть задано число > 0 – точность регрессии. Тогда функция g(, y) = |f () y| определяет способ решения некоторой задачи классификации пар (, y) : условие g(, y) > 0 означает, что пара (, y) классифицируется функцией g как положительx ный пример; в противном случае она классифицируется как отрицательный пример.

Для получения оценки вероятности ошибки обобщения, не зависящей от размерности пространства, вводим число – нижнюю границу ошибки соответствующей задачи классификации, 0 < <. По определению условие g(, y) x эквивалентно условию |f () y|.

Теперь теорема 1.9 может быть переформулирована для случая многомерной регрессии. Соответствующая теорема 2.9 имеет место для случая, когда при обучении требуется точное попадание данных выборки в слой размера вокруг гиперплоскости (см. [10], теорема 4.26).

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

Пусть 0 < < R и P – распределение вероятностей, сконцентрированное в шаре радиуса R с центром в начале координат генерирующее выборку S = ((1, y1 ),..., (l, yl )).

Тогда с вероятностью 1 произвольная гипотеза f L, для которой |f (i ) yi | для всех i = 1,..., l, имеет верхнюю оценку вероятности ошибки:

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

где – заданная точность приближения, – потери на границе.

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

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

Если в результате обучения i > 0, то т.е. эта величина показывает, насколько в результате обучения i-й остаток вышел из слоя размера =, проходящего вокруг значений функции регрессии. 3 Величина i тем больше, чем больше ошибка регрессии на примере (i, yi ).

Если |yi f (i )| x, то i = 0, и мы считаем, что ошибки регрессии на примере нет; значение исходного данного yi лежит в слое размера, расположенном вокруг значений функции регрессии на обучающей выборке.

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

Заметим, что из i > следует, что ошибка на (i, yi ) больше чем.

В монографии [10] приведена теорема (теорема 4.28), которая в отличие от теоремы 2.9 не требует точного попадания данных выборки в слой размера = вокруг гиперплоскости, а использует вектор переменных мягкого отступа = (1,..., l ). Здесь возможно произвольное отклонение данных при обучении от гиперплоскости регрессии. При этом большие отклонения ухудшают оценку вероятности ошибки регрессии.

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

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

Заметим, что размер слоя исчисляется по вертикали.

c, что для произвольного распределения вероятностей P, сконцентрированного в шаре радиуса R с центром в начале координат, выполнено следующее: с P l -вероятностью 1 на выборке ром переменных мягкого отступа = (1,..., l ) имеет оценку вероятности ошибки обобщения:

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

Следствие 2.2. Рассмотрим задачу регрессии с помощью линейных функций f () = (w · x) + b L, где x X Rn.

Пусть > 0. Тогда существует такая константа c, что для произвольного распределения вероятностей P, сконцентрированного в шаре радиуса R с центром в начале координат, выполнено следующее: с P l -вероятностью 1 на случайной выборке S = ((1, y1 ),..., (l, yl )) произвольная гипотеза f L имеет оценку вероятности ошибки обобщения:

Оценка (2.62) может быть использована для гребневой регрессии, где = 0.

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

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

Линейная -нечувствительная функция потерь – это функция вида где f – произвольная функция типа Rn R.

Пусть = (1,..., l ) – вектор переменных мягкого отступа, Аналогично, -нечувствительная квадратичная функция потерь определяется Задача минимизации в случае квадратичной функции потерь Оценка (2.61) теоремы 2.10 показывает, что для уменьшения верхней оценки вероятности ошибки обобщения метода регрессии нам надо минимизировать величину где f () = (w · x) + b.

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

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

Прямая задача минимизации в случае квадратичной функции потерь (2.64) при фиксированных значениях параметров C и формулируется следующим образом:

при условиях ((w · xi ) + b) yi На практике параметр C подбирается путем процедуры типа перебора для данной обучающей выборки.

Лагранжиан прямой задачи имеет вид Заметим, что так же, как в задаче классификации, условия i 0, i 0 можно опустить, так как всякое решение, где i < 0 или i < 0, можно преобразовать в решение i = 0 или i = 0.

Для поиска минимума приравниваем частные производные к нулю Из первого равенства получаем выражение для весового вектора Заметим, что для любого допустимого решения задачи (2.65) выполнено i i = 0 для всех i.

Поэтому для двойственной задачи будет i i = 0.

Соответствующая двойственная задача формулируется следующим образом:

где ij = 1 тогда и только тогда, когда i = j.

Условия Каруша–Куна–Таккера следующие:

Если ввести обозначение i = i i, i = 1,..., l, и использовать соотношения i i = 0, то двойственная задача (2.67) формулируется аналогично двойственной задаче для случая классификации:

Из условий Каруша–Куна–Таккера (2.68) следует, что для всех векторов выборки xi, попавших в слой размера вокруг гиперплоскости регрессии, выполнено i = i = 0. Поэтому в сумме (2.66) соответствующие слагаемые отсутствуют ( опорных векторов становится меньше), и решение задачи нахождения максимума в двойственной задаче упрощается. Кроме этого, уменьшается норма вектора переменных мягкого отступа в верхней оценке вероятности ошибки обобщения (2.61) из теоремы 2.10. Заметим, что опорными являются векторы xi, для которых (w · xi ) + b yi Насколько уменьшается число параметров i, i, зависит от взаимного расположения векторов выборки. Обычно такое уменьшение происходит при увеличении до определенного предела, при этом увеличивается точность регрессии на тестовой выборке.

При дальнейшем увеличении эта точность падает.

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

Ядерная версия результата формулируется следующим образом. Для удобства изложения обозначим i посредством i, т.е. i имеет теперь другой смысл, чем ранее.

Теорема 2.11. Задана выборка S = ((1, y1 ),..., (l, yl )), где xi X и yi R. Используется пространство признаков, задаваемое ядром K(, z ).

Пусть является решением квадратичной оптимизационной задачи:

Пусть также f () = чтобы f (i ) yi = i /C для произвольного i с i > 0.

Тогда функция f () эквивалентна гиперплоскости в пространx стве признаков, определяемом ядром K(i, x), которая решает задачу оптимизации (2.65).

Задача минимизации в случае линейной функции потерь Аналогичным образом рассматривается задача регрессии при линейной функции потерь (2.63).

Оценка, аналогичная оценке (2.61) теоремы 2.10 (в данном пособии эта оценка и соответствующая теорема не приводятся, см.

теорему 4.30 из [10]), показывает, что для уменьшения верхней оценки вероятности ошибки обобщения метода регрессии нам надо минимизировать величину где f () = (w · x)+b, C – параметр, контролирующий баланс межx ду сложностью регрессионной гипотезы и суммой величин линейных остатков для этой гипотезы.

Прямая задача минимизации в случае линейной функции потерь (2.63) при фиксированных значениях параметров C и формулируется следующим образом:

при условиях ((w · xi ) + b) yi На практике параметр C подбирается путем процедуры типа перебора для данной обучающей выборки.

Лагранжиан прямой задачи имеет вид Соответствующая прямой задаче (2.71) двойственная задача формулируется следующим образом:

а ее решение такое, как указана далее.

Условия Каруша–Куна–Таккера имеют вид:

Опорные векторы – это xi, для которых i > 0 или i > 0. Если yi находится вне слоя размера вокруг оптимальной гиперплоскости (гиперповерхности), то i = C или i = C (для линейной нормы).

0 < i < C может быть только для векторов со значениями yi на границе слоя.

Векторы xi, у которых значения yi расположены внутри слоя, заведомо не являются опорными; для них i = 0 и i = 0, так как в этом случае выполнены неравенства Весовой вектор – линейная комбинация опорных векторов Выполнено i i = 0.

Функция линейной регрессии имеет вид:

Для пространства с ядром двойственная задача имеет вид:

Функция регрессии для ядерной версии имеет вид:

2.9.3. Гребневая регрессия в двойственной форме Гребневая регрессия может быть представлена как частный случай регрессии с опорными векторами при -нечувствительной квадратичной функции потерь (2.64), где = 0.

Проиллюстрируем решение этой задачи как частный случай регрессии с опорными векторами в случае = 0, независимо от результатов раздела 2.8.2.

Оценка ошибки обобщения для гребневой регрессии дается неравенством (2.62), приведенном в следствии 2.2.

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

Тогда функция регрессии c расширенной переменной x будет иметь однородный вид Рассматривается прямая задача минимизации В этом случае лагранжиан имеет вид Приравниваем к нулю частные производные лагранжиана (2.76) по wj и j :

при i = 1,..., l. Отсюда выражаем весовой вектор функции регрессии и переменные мягкого отступа через переменные двойственной задачи:

Предварительно вычислим Подставим эти выражения в (2.76), получим задачу в двойственной форме Эту задачу можно переписать в векторной форме где K – матрица Грама, элементами которой являются попарные скалярные произведения векторов Ki,j = (i · xj ).

Приравнивая к нулю частные производные W ( ) в выражении (2.77) по i, получим систему уравнений, записанную в векторном виде Решение этого уравнения в векторном виде записывается так:

Получаем уравнение регрессии в двойственной форме.

Представим скалярное произведение расширенного весового вектора и вектора расширенных переменных Матрица K является симметрической, поэтому K = K. По свойству транспонирования произведения матриц (AB) = B A и (2.78) имеем Отсюда функция регрессии имеет вид Отметим один недостаток данной постановки. Поскольку в данной постановке = = 0, число параметров i равно размеру выборки l, поэтому размер обращаемой матрицы K + I равен l l, и мы не можем использовать для обучения слишком большую выборку.

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

Нелинейная гребневая регрессия с помощью ядер Двойственная форма регрессии служит основой для обобщения линейной регрессии до нелинейной ее формы в пространстве признаков. Для этого вводится ядро K(, y ). x Рассмотрим схему построения нелинейной регрессии в пространстве признаков более подробно. Рассмотрим отображение x () в пространство признаков большей размерности RN.

Тогда скалярное произведение в RN порождает ядро K(i, xj ) = Матрица Грама K имеет вид Вектор z будет иметь вид Прообразом гиперплоскости (2.79), построенной в пространстве признаков RN, по образам векторов (1 ),..., (l ) при отобраявляется нелинейная поверхность жении Для построения нелинейной поверхности (2.80) совсем не обязательно знать конкретный вид отображения в пространство признаков, достаточно знать ядро K(, z ). x Основной проблемой при решении таких задач является подбор ядра, наилучшим образом подходящего для разделения исходных данных. Другая проблема заключается в удачном подборе нормализующего параметра. Для ее решения разработаны специальные алгоритмы.

Вероятностный аналог изложенного выше способа построения регрессии с произвольным ядром называется кригингом (Krieging). При вероятностной постановке векторы x1,..., xl являются случайными величинами, при этом задан вид ковариационной функции R(i, xj ) = E(i ·j ). Обычно предполагается, что вид веx xx роятностного распределения, генерирующего векторы x1,..., xl, известен с точностью до небольшого числа параметров.

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

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

Прямая задача оптимизации Заданы вещественные функции f (w), gi (w), hi (w), i = 1,..., m, определенные на R Последние два условия можно записать в векторном виде g (w) и h(w) = Пусть – область допустимости решений.

Решение задачи оптимизации – это такой вектор w, что R и не существует w Rn такого, что f (w) < f (w ). Иными словами, на векторе w достигается глобальный минимум функции f. Если данное свойство верно в некоторой окрестности w, то получаем определение локального минимума. Функция f называется целевой функцией.

Если f (w) – квадратичная функция от координат w, а g и h – линейные функции, то такая задача оптимизации называется задачей квадратичного программирования.

Функция f называется выпуклой, если для всех w, u Rn и 0 1 выполнено Теория Лагранжа – это случай, когда имеются только условия h(w) = Лагранжиан имеет вид Необходимое условие минимума Это условие является достаточным, если функция L выпуклая.

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

Теорема 2.12. Пусть вектор w удовлетворяет условиям (2.81) и (2.82) прямой задачи оптимизации (в частности, он может быть решением прямой задачи), а (, ) – решение двойственной задачи (2.83). Тогда f (w) (, ).

Доказательство. Имеем Здесь g (w) 0, так как и g (w) h(w) = Непосредственно из теоремы получаем Следствие 2.3. Значение решения двойственной задачи не превосходит значения решения прямой задачи:

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

w ) = то w и (, ) – решения прямой и двойственной задач соответственно.

В этом случае также g (w ) = 0.

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

Другое достаточное условие равенства значений решений прямой и двойственной задачи дано в следующей теореме.

Теорема 2.13. Пусть область допустимости задачи – выпуклое подмножество Rn, функции h, g – аффинные (т.е. hi (w), gi (w) имеют вид Ai w + b значения решений прямой и двойственной задач совпадают.

Теорема Куна–Таккера – основная теорема выпуклой нелинейной оптимизации.

Теорема 2.14. Пусть область допустимости задачи – выпуклое подмножество Rn, функция f – выпуклая, функции h, g – аффинные (т.е. hi (w), gi (w) имеют вид Ai w + i, где Ai – некоторая матрица).

Тогда вектор w является решением прямой задачи тогда и только тогда, когда существует пара (, ) такая, что Условия достижения максимума по линейной по и функции L(w,, ) задаются условиями (2.85); они эквивалентны совокупности условий: hi (w ) = 0, i = 1,..., k.

Условия максимума функции L(w,, ) по i содержатся в вращается в условие gi (w ) = 0 (что эквивалентно равенству нулю производной L(w,, ) по i ), а при gi (w ) < 0 в точке максимудолжно быть = 0.

Условия (2.86) называются условиями Каруша–Куна–Таккера.

Они означают, что если решение задачи оптимизации достигается на границе i-го условия, то i 0, в противном случае i = 0.

Квадратичное программирование Рассмотрим задачу квадратичного программирования где Q – n n-положительно определенная матрица, k – n-вектор, c – m-вектор, w – n-вектор неизвестных, X – (m, n)-матрица.

Допускаем, что условия определяют непустое множество векторов. Тогда задача может быть переписана в виде: найти максимум Минимум по w в (2.88) достигается при Подставляем это выражение в (2.87), получим двойственную задачу Двойственная задача также является квадратичной, но ее граничные условия проще, чем у прямой задачи.

2.11. Конформные предсказания Задана выборка S = ((1, y1,..., (l, yl )), где xi Rn и yi {1, +1} при 1 i l.

При решении задачи классификации с помощью разделяющей гиперповерхности, различные примеры из выборки классифицируются с разной степенью качества. Мера качества классификации примера (i, yi ) – мера некомформности – была введена Воx вком и Гаммерманом [33]. Мера некомформности применяется для повышения эффективности известных алгоритмов на основе новых способов оценки уровня доверия к результатам их работы.

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

Мы определим меру некомформности для классификации с помощью SVM. Напомним основные положения метода построения машин на опорных векторах (SVM). В методе SVM исходные векторы xi отображаются в векторы (i ) в пространстве признаков, определенным ядром K(, x ). После этого, строится разделяx ющая гиперплоскость в пространстве признаков, Согласно (2.42) вектор весов разделяющей гиперплоскости выражается в виде линейной комбинации образов опорных векторов:

где коэффициенты Лагранжа i вычисляются в результате решения двойственной задачи оптимизации.

По теореме 2.5 в исходном пространстве соответствующая разделяющая поверхность имеет вид:

Решаем оптимизационную задачу построния SVM по выборке S, при этом будут вычислены коэффициенты Лагранжа i. Возьмем в качестве меры некомформности примера (i, yi ) значение коэфx фициента Лагранжа i.

Это определение обосновывается следующим образом. Из услоx вий Каруша–Куна–Таккера следует, что i = 0, если yi ((w·(i ))+ b) > 1. Такие векторы xi правильно классифицируются и лежат с внешней стороны относительно граничных гиперплоскостей. Опорными являются те векторы xi, для которых выполxi )) + b) нено yi ((w · ( те векторы, образы которых лежат на граничных гиперплоскостях или же неправильно ими классифицируются, в этом случае yi ((w · (i )) + b) < 1. В случае линейной нормы добавляется условие i C, где C – соответственная константа из задачи оптимизации. Таким образом:

• примеры с i = 0 правильно классифицируются и поэтому имеют высшую степень согласованности с выборкой (по которой построена гиперповерхность);

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

Введенная мера некомформности применяется к примеру (i, yi ).

Определяется p-тест (p-value):

По определению 0 pi 1. Малое значение pi означает, что пример (i, yi ) имеет одну из самых больших мер некомформности среди примеров выборки.

На основе введенного понятия p-теста можно построить метаалгоритм для вычисления конформных предсказаний с использованием SVM.

Пусть дана выборка S = ((1, y1,..., (l, yl )) и вектор xl+1, которому надо приписать метку класса yl+1 {1, +1}. Задан также уровень доверия > 0.

Мета-алгоритм:

Для каждого y {1, +1} решаем оптимизационную задачу построения SVM по выборке S = ((1, y1,..., (l, yl ), (l+1, y)), находим значения коэффициентов Лагранжа i, 1 i l+1 и вычислем значение p-теста Результат работы алгоритма:

• если p(y) < для всех y, то алгоритм не выдает никакого результата;

• если p(y) для некоторого y, то выдаем в качестве результата то значение y, для которого величина p(y) принимает максимальное значение:

Подобный порядок действий обосновывается вероятностным результатом, который утверждает, что при некоторых вероятностных предположениях о механизме генерации примеров выборки p-тест удовлетворяет естественному условию: P {pi }, где P – некоторая мера на наборах i инвариантная относительно их перестановок (подровнее см. в [33]).

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

Приведем пример меры некомформности для алгоритма классификации методом ближайшего соседа.

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

ное множество меток. Допустим, что {1,..., xk } – множество k ближайших к x объектов и {y1,..., yk } – их метки.

(, y) – некоторый пример. Определим меру некомформности этого примера в виде отношения минимального расстояния от оъекта x до объектов xi с той же меткой yi = y к минимальному расстоянию от этого объекта x до объектов xi с другими метками yi = y:

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

Чем больше величина (,y) тем ближе расположен объект x к другим объектам отмеченным метками отличными от y, т.е. тем больше степень некомформности примера (, y).

2.12. Задачи и упражнения 1. Доказать оставшуюся часть утверждения леммы 2.1.

2. Построить отображения Rn в пространства признаков и соответствующие полиномиальные ядра для полиномов общего вида и более высокого порядка (k = 3, 4,... ), а также соответствующие функции классификации вида (2.25).

3. Для любой положительно определенной функции K(x, y) выполнено неравенство типа Коши–Буняковского:

Указание: из положительной определенности (2 2) матрицы K(xi, xj ) следует, что ее собственные значения неотрицательные.

Поэтому то же верно и для определителя.

4. Докажите, что (i) K(x, x) 0 для всех x.

(ii) Если K(x, x) = 0 для всех x, то K(x, y) = 0 для всех x и y.

Заметим, что функция K(x, y) в общем случае не является билинейной.

5. Рассматривается гильбертово пространство F функций на X, которое обладает следующим свойством: функционал f f (x) является непрерывным линейным функционалом. По теореме Рисса–Фишера для каждого x X существует элемент Kx F такой, что f (x) = (Kx · f ). Воспроизводящее ядро определяется K(x, y) = (Kx · Ky ).

Доказать, что функция K(x, y) = (Kx · Ky ) является симметричной и положительно определенной.

6. Пусть K1 (x, y), K2 (x, y),..., – положительно определенные ядра на X. Доказать, что следующие их комбинации также являются положительно определенными ядрами:

(i) 1 K1 (x, y) + 2 K2 (x, y), где 1, 2 0;

(ii) K(x, y) = lim Kn (x, y);

(iii) K1 (x, y)K2 (x, y) (Указание: использовать представление положительно определенной матрицы (Грама) в виде K = P P );

(iv) K(A, B) = K(x, y), где A, B – конечные подмножества X (это ядро на множестве всех конечных подмножеств X).

Указать соответствующие отображения в пространства признаков.

7. Доказать, что в оптимизационной задаче (2.70) значение b не зависит от i.

8. Показать, что соответствующая прямой задаче (2.71) двойственная задача формулируется в виде (2.73). Обосновать соотношения (2.75) для этой задачи.

9. Доказать, что матрица Грама Ki,j = (i · xj ) обратима тогда и только тогда, когда векторы x1,..., xl линейно независимы.

10. (i) Найти максимум объема параллелепипеда при заданной площади поверхности.

(ii) Найти максимум энтропии H(p1,..., pn ) = pi ln pi при условиях 11. Провести все необходимые выкладки для получения решения (2.89) квадратичной задачи.

12. Доказать, что для класса F всех линейных (однородных) функций множество является -разделимым тогда и только тогда, когда оно -разделимо (может быть для другого ) на одном уровне, причем r = 0.

13. Вывести соотношения (2.69) для двойственной задачи регрессии.

2.13. Лабораторные работы по теме SVM В этом разделе предлагаются стандартные лабораторные работы для решения задачи классификации с помощью SVM.

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

• Загрузить исходные данные из соответствующего сайта. Как правило, исходные данные – это набор векторов большой размерности, в которых уже указан класс объекта.

• Разделить данные на обучающую и тестовую выборки. Класс объекта используется в обучающей выборке для проведения обучения, а в тестовой выборке – для проверки правильности классификации. После проведения классификации требуется подсчитать долю правильных ответов.

• Перевод данных в формат, допускаемый программным обеспечением SVM.

• Провести калибровку (шкалирование) исходных данных.

Шкалирование данных помогает избежать потери точности из-за слишком малых или слишком больших значений некоторых признаков. В частности, это важно при использовании гауссова ядра. Рекомендуется нормировать численное значение каждого признака так, чтобы оно попадало в интервал типа [1, 1] или [0, 1].

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

1) линейное ядро K(, y ) = ( · y ), 2) полиномиальное ядро K(, y ) = (( · y ) + r)d, где > 0, 3) гауссово ядро K(, y ) = e 4) сигмоидное ядро K(, y ) = tanh(( · y ) + r).

Рекомендуется первоначально выбрать гауссово ядро K(, y ) = e 2. Имеются случаи, когда гауссово ядро дает неудовлетворительные результаты. Например, это может происходить в случае, когда размерность пространства объектов очень большая. В этом случае хорошие результаты может давать линейное ядро.

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

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

Подбор параметров C и может производиться простым перебором по некоторому дискретному подмножеству – решетке. Недостатком этого метода является большое время вычисления. Применяются различные эвристические методы перебора C и.

• Выбрать для использования параметры C и, которые дают наилучшую точность классификации.

• Провести классификацию на тестовой выборке. Оформить результаты с сопоставлением точности классификации на обучающей и тестовой выборках.

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

Программное обеспечение SVM можно найти на сайтах http://www.csie.ntu.edu.tw/cjlin/libsvm/ www.support-vector.net По адресу http://www.csie.ntu.edu.tw/cjlin/papers/guide/guide.pdf можно найти инструкции по практическому применению программ SVM и подготовке исходных данных. Там же приведены примеры.

На сайте http://archive.ics.uci.edu/ml/ содержатся исходные данные для решения задач классификации и регрессии.

Лабораторная работа Провести обучение и классификацию рукописных цифр. Данные в формате MATLAB можно найти по адресу http://www.cs.toronto.edu/roweis/data.html В частности, по этому адресу имеются данные из базы USPS, содержащие цифровые образы различных написаний рукописных цифр.

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

Библиотека LIBSVM для машин с опорными векторами находится по адресу http://www.csie.ntu.edu.tw/cjlin/libsvm/ База данных для машинного обучения находится по адресу http://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/ Примеры данных и задач:

1) Провести обучение и классификацию видов лейкемии по медицинским данным из следующего сайта:

http://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/ 2) Откалиброванные данные для классификации вин (по признакам) имеются по адресу http://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/ multiclass/wine.scale База данных UCI Machine Learning Repository находится на сайте http://archive.ics.uci.edu/ml/datasets.html Она содержит 190 наборов данных для классификации и регрессии.

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

Глава Универсальные предсказания 3.1. Универсальное прогнозирование в режиме онлайн Рассматривается следующая задача прогнозирования: предсказатель получает в режиме онлайн некоторую числовую последовательность исходов 1, 2,..., n1,... При этом предсказателю не известно распределение вероятностей источника, генерирующего эту последовательность. Задачей предсказателя является вычисление оценок вероятностей pn будущих событий n по уже известным n 1 исходам 1, 2,..., n1.

Число pn может рассматриваться как вероятность события n = 1 в том случае, когда i принимают значения 0 или 1. Легко видеть, что в этом случае число pn также является математическим ожиданием случайной величины n.

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

Исторически первой процедурой универсального прогнозирования является правило Лапласа. Эта процедура использует гипотезу о том, что исходы i порождаются некоторым источником, который генерирует их независимо друг от друга с одной и той же вероятностью единицы, равной p. Особенность данной задачи заключается в том, что мы не знаем истинного значения p и хотим построить процедуру прогнозирования, которая бы годилась для всех p таких, что 0 p 1.

Пусть исходы i принадлежат множеству {0, 1}. Мы также предполагаем, что в каждый момент времени i = 1, 2,... исход i порождается независимо от предыдущих исходов с неизвестными нам постоянными вероятностями p = P {i = 1} и q = P {i = 0} = 1 p. Необходимо оценивать эти вероятности в режиме онлайн на основе статистики предыдущих исходов.

Пусть мы наблюдаем исходы n = 1,... n, в которых имеется n1 единиц и n2 нулей, n1 +n2 = n. Вероятность получить такую последовательность исходов равна pn1 (1 p)n2, если вероятность единицы равна p. Так как истинная вероятность p неизвестна, рассмотрим байесовскую смесь вероятностей последовательности длины n по всем возможным p :

Значение этого интеграла легко вычислить.

Лемма 3.1.

Доказательство. Проверим это равенство обратной индукциpn dp = Предположим, что Интегрируя по частям, получим Условная вероятность события n+1 = 1 при известных исходах n = 1,..., n равна Таким образом, получаем правило Лапласа:

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

Из теории информации известно, что эта величина с точностью до 1 совпадает со средним количеством двоичных битов, необходимых для кодирования последовательностей n, состоящих из n1 единиц и n2 нулей и порождаемых источником с данным распределением вероятностей.

Для правила Лапласа Тогда для произвольной последовательности n выполнено Таким образом, используя для кодирования вероятности, вычисленные по правилу Лапласа, мы истратим ln(n + 1) дополнительных битов по сравнению с длиной оптимального кода, т.е. кода, построенного на основе истинных вероятностей источника, порождающего исходы i.

Легко проверить, что Другой, более точный, метод прогнозирования был предложен Кричевским и Трофимовым. Рассматривается байесовская смесь вероятностей последовательности длины n по всем возможным p с плотностью 1/( p(1 p)) :

В этом случае условная вероятность 1 после n наблюдений n = 1,..., n равна Имеет место оценка:

Эти утверждения предлагается далее в разделе 3.5 в виде задач 1 и 2.

Отсюда получаем оценку на дополнительное число битов при кодировании с использованием прогнозирования по методу Кричевского и Трофимова:

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

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

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

Предсказатель погоды считается хорошо калибруемым, если дождь случается так же часто, как он прогнозируется предсказателем. Например, если дождь случается в 80% всех дней, для которых предсказатель давал прогноз pn = 0.8, и т.д. Величина среднего отклонения частоты исходов n от прогнозов pn, где pn p, для различных значений p может использоваться как тест для выявления плохих предсказателей.

В предыдущем примере pn [0, 1]. Можно рассматривать последовательности данных более общего характера. Например, пусть n = Sn – цена некоторого финансового инструмента в некоторые последовательные моменты времени n = 1, 2,.... Цена имеет стохастический характер изменения. В практических приложениях иногда трудно восстановить параметры модели, управляющей изменением цены. Кроме этого, эти параметры могут изменяться со временем. Число pn рассматривается как прогноз среднего значения этой величины на шаге n.

В разделе 3.3 мы будем рассматривать как бинарные исходы n {0, 1}, так и вещественные исходы, лежащие в единичном интервале: n [0, 1]; число pn лежит в единичном отрезке [0, 1].

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

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

Однако на практике мы часто имеем дело с единственной исторической последовательностью исходов 1, 2,..., n1,... и не имеем представления о механизмах, генерирующих эту последовательность. Мы даже можем не знать, являются ли эти механизмы стохастическими.

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

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

Приведенное выше правило проверки предсказателя погоды можно записать в следующем виде: для любого действительного числа p [0, 1] выполнено если знаменатель отношения (3.1) стремится к бесконечности при n. Здесь мы использовали символ приближенного равенства, потому что на практике число p можно задавать только с некоторой точностью. Условие pi p требует дальнейшего уточнения.

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

FOR n = 1, 2,...

Предсказатель анонсирует прогноз pn [0, 1].

Природа анонсирует исход n {0, 1}.

ENDFOR

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

Приведем точное определение калибруемости, предложенное Дейвидом [11]. Рассмотрим произвольные подынтервалы I = [a, b], (a, b], [a, b), (a, b) интервала [0, 1] и их характеристические функции Последовательность прогнозов p1, p2,... калибруется на бесконечной последовательности 1 2..., если для характеристической функции I(p) каждого подынтервала [0, 1] калибровочная ошибка стремится к нулю, т.е.

если знаменатель отношения (3.2) стремится к бесконечности при n. Характеристическая функция I(pi ) определяет некоторое правило выбора, которое определяет те номера исходов i, для которых мы вычисляем отклонение прогноза pi от соответствующего исхода i.

Простые соображения показывают, что никакой алгоритм, вычисляющий прогнозы на основании прошлых исходов, не может всегда выдавать калибруемые прогнозы. А именно, для произвольного такого алгоритма f можно определить последовательность = 1 2... так, что где pi = f (1... i1 ), i = 1, 2,.... Легко видеть, что для интервала I = [0, 1 ) или для интервала I = [ 2, 1) условие калибруемости (3.2) нарушается.

Данная последовательность = 1 2... является простейшим примером адаптивно враждебной стратегии Природы. При генерации очередного исхода i согласно приведенному выше протоколу Природа уже знает наш прогноз pi и использует это знание для формирования очередного исхода.

Подобные трудности предсказания оказались преодолимыми с помощью понятия рандомизированной предсказательной системы. Пусть P[0, 1] – множество всех вероятностных мер на отрезке [0, 1]. Под рандомизированной предсказательной системой понимается функция f : P[0, 1], значениями которой являются распределения вероятностей на отрезке [0, 1]. Мы также обозначаем Prx (·) = f (x), где x – конечная последовательность исходов.

Обозначаем i1 = 1... i1. Для каждой бесконечной последовательности = 1 2... (которая в данном случае является параметром) условные вероятностные распределения Pri1 (·) порождают распределение вероятностей Pr = Pri1 на множеi= стве всех бесконечных последовательностей прогнозов p1, p2,..., где pi [0, 1], i = 1, 2,... Данное распределение вероятностей Pr является бесконечным произведением мер Pri1, i = 1, 2,...

В этом случае при фиксированной последовательности можно рассматривать вероятность Pr события (3.2).

Заметим, что такая мера Pr существует и в гораздо более общем случае, а именно, когда последовательность = 1 2... зависит от последовательности прогнозов p1, p2,..., точнее последовательность i1 = 1... i1 является измеримой функцией от последовательности p1,..., pi1 для всех i. В этом случае по теореме Ионеско–Тульчи [3] о продолжении меры существует вероятностная мера Pr на множестве [0, 1] всех бесконечных траекторий прогнозов p1, p2,... такая, что условные вероятности, соответствующие этой мере, для всех n удовлетворяют условиям для любого борелевского подмножества A единичного интервала.

Фостер и Воора [12], а также Какаде и Фостер [16], определили для произвольного параметра > 0 рандомизированную предсказательную систему f такую, что для произвольной бесконечной последовательности = 1 2... с Pr-вероятностью 1 :

где траектории прогнозов p1, p2,... распределены по вероятностной мере Pr, а I(p) – характеристическая функция произвольного подынтервала [0, 1].

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

В этом случае (3.2) также выполнено для алгоритма Какаде и Фостера, если 3.3. Алгоритм вычисления калибруемых прогнозов Приведем некоторый модернизированный вариант рандомизированного алгоритма Какаде и Фостера. Пусть 1 1... – произвольная последовательность элементов {0, 1} или [0, 1], поступающая в режиме онлайн. Построим алгоритм для вычисления случайной величины, выдающей прогноз pn [0, 1] будущего значения n по начальному фрагменту 1... n1. Основное требование к таким прогнозам: они должны с вероятностью 1 удовлетворять условию калибруемости. Соответствующее распределение вероятностей является внутренним по отношению к алгоритму и строится в процессе конструкции.

Предварительно разобъем интервал значений прогнозов [0, 1] на равные части длины = 1/K с помощью рациональных точек vi = i, где i = 0, 1,..., K. Пусть V обозначает множество всех этих точек. Любое число p [0, 1] представляется в виде линейной комбинации граничных точек подынтервала разбиения, содержащего p :

Полагаем wv (p) = 0 для всех остальных значений v V.

В дальнейшем детерминированный прогноз p, выдаваемый алгоритмом, приведенным далее, будет округляться до vi1 с вероятностью wvi1 (p) и до vi с вероятностью wvi (p).

Сначала построим алгоритм, выдающий детерминированные прогнозы.

Пусть прогнозы p1,..., pn1 уже определены (пусть p1 = 0).

Вычислим прогноз pn.

Рассмотрим вспомогательную величину Имеем (µn (v))2 = (µn1 (v))2 + 2wv (pn )µn1 (v)(n pn ) + Суммируем (3.3) по v :

Изменим порядок суммирования в сумме вспомогательных величин где – вектор вероятностей округления, p [vi1, vi ], и – скалярное произведение соответствующих векторов (ядро). По определению K(p, pi ) – непрерывная функция.

Второй член правой части равенства (3.4) при подходящем значении pn всегда можно сделать меньшим или равным нулю.

Действительно, в качестве pn берем корень pn = p уравнения если он существует. В противном случае если левая часть уравнения (3.6) (которая является непрерывной по p функцией) больше нуля для всех значений pn, то полагаем pn = 1, если она меньше нуля, то полагаем pn = 0. Определенное таким образом значение pn выдаем в качестве детерминированного прогноза.

Третий член (3.4) ограничен числом 1. Действительно, так как |i pi | 1 для всех i, имеем для произвольного n Отсюда и по (3.4), если последовательно выбирать прогнозы pi согласно указанному правилу, получим Пусть теперь pi – случайная величина, принимающая значения v V с вероятностями wv (pi ) (на самом деле, для каждого p ненулевыми являются только значения wv (p) для двух соседних границ подынтервала разбиения, содержащего детерминированный прогноз pi ). Пусть также I(p) – характеристическая функция произвольного подынтервала [0, 1]. Для любого i математическое ожидание случайной величины I(i )(i pi ) равно Согласно усиленному мартингальному закону больших чисел (см. следствие 4.9 ниже) с Pr-вероятностью 1 :

при n.

По определению детерминированного прогноза pi и функции wv (p) для каждого i.

Применяем неравенство Коши–Буняковского к векторам {µn (v) :

v V } и {I(v) : v V }, учитываем (3.10), и получаем где K = 1/ - число подынтервалов разбиения.

Используя (3.10) и (3.11), получаем верхнюю оценку для абсолютной величины суммы математических ожиданий (3.8) :

для всех n.

Из (3.12) и (3.9) получаем, что c Pr-вероятностью 1 :

Сформулируем результаты этого раздела в виде следующей теоремы.

Теорема 3.1. Для каждого > 0 можно построить рандомизированную предсказательную систему f такую, что для произвольной бесконечной последовательности = 1 2... c вероятностью 1 выполнено:

где бесконечные траектории прогнозов p1, p2,... распределены по мере Pr, I(p) – характеристическая функция произвольного подынтервала [0, 1]. Такая функция называется правилом выбора, определенным прогнозом.

Если в процессе конструкции в определенные моменты времени ns, s = 1, 2,..., изменять = s так что s 0 при s, можно достичь асимптотически точного результата:

Теорема 3.2. Можно построить рандомизированную предсказательную систему f такую, что для произвольной бесконечной последовательности = 1 2... c вероятностью 1 выполнено:

Рис. 2.1. Пример последовательности данных 1, 2,... и последовательности калибруемых прогнозов p1, p2,...

где I(p) – характеристическая функция произвольного подынтервала [0, 1].

Детали конструкции оставляем читателю.

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

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

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

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

Можно показать, что оба эти подхода, по существу, эквивалентны (см. [16]).

Второй метод прогнозирования будет рассмотрен в этом разделе.

Метод построения алгоритмов универсального прогнозирования, предложенный в работах Фостера и Вооры [12], а также Какаде и Фостера [16], был обобщен В. Вовком на случай произвольных ядер в работах [35] и [37]. В этом разделе мы представим основную идею этого обобщения.

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

В этой игре прогнозы будут детерминированными, подобно прогнозам pi, которые вычисляются в виде корней уравнений типа (3.6) в разделе 3.3. Мы рассмотрим более общую постановку, а именно, введем дополнительную информацию – сигналы.

Задано множество сигналов X Rm – множество m-мерных векторов x = (x1,..., xm ), на котором рассматривается обычная m-мерная евклидова норма Сигналы можно интерпретировать как дополнительную информацию, которая поступает Предсказателю в режиме онлайн.

Полагаем начальный выигрыш Скептика K0 = 1.

Игра регулируется следующим протоколом.

FOR n = 1, 2,...

Природа анонсирует сигнал xn X.

Скептик анонсирует непрерывную по p функцию Sn : [0, 1] R.

Предсказатель анонсирует прогноз pn [0, 1].

Природа анонсирует исход yn {0, 1}.

Скептик вычисляет свой выигрыш на шаге n игры Kn = Kn1 + Sn (pn )(yn pn ).

ENDFOR

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

Теорема 3.3. Предсказатель имеет стратегию, при которой Доказательство. Стратегия Предсказателя заключается в следующем.

На произвольном шаге n игры Предсказатель вычисляет свой прогноз pn следующим образом. Если Sn (p) положительно для всех p [0, 1], то полагаем pn = 1. Если Sn (p) отрицательно для всех p [0, 1], то полагаем pn = 0. В противном случае из теоремы о промежуточных значениях следует, что уравнение рассматриваемое относительно p, имеет корень. В этом случае Предсказатель выбирает в качестве pn один из таких корней.

Легко видеть, что при таком выборе pn выигрыш Скептика всегда не возрастает, как бы он не выбирал непрерывную по p функцию Sn (p), т.е. всегда выполнено для всех n.

Мы будем использовать ядро K((p, x), (p, x )) - вещественную гладкую функцию на ([0, 1] X)2. Пример ядра – гауссово ядро:

где 1, 2 – параметры ядра.

Рассмотрим следующую стратегию Скептика, которая будет вынуждать Предсказателя делать на каждом шаге n хорошо калибруемые прогнозы:

Пусть Предсказатель использует стратегию, описанную в теореме 3.3. Тогда выигрыш Скептика за N шагов игры удовлетворяет соотношениям По теореме Мерсера (см. раздел 2.5) существует гильбертово пространство признаков H и отображение : [0, 1] X H такое, что при a, b [0, 1] X, где · – скалярное произведение в пространстве H (далее · – соответствующая норма).

Величина cH = sup (a) называется константой вложения (embedding constant). Мы рассматриваем гильбертовы пространства H, для которых эта величина конечна: cH <.

Перепишем (3.17) в виде По предположению Тогда из (3.18) следует Неравенство (3.19) перепишем в виде Иными словами, средняя ошибка алгоритма предсказания ограничена Используя полученную оценку средней ошибки алгоритма предсказания, получим результат о калибруемости, аналогичный результату из раздела 3.3. Для этого возьмем в качестве ядра какоенибудь семейство гладких приближений к характеристическим функциям одноэлементных множеств {(p, x )}, где (p, x ) [0, 1] X, т.е. семейство функций вида Примером такого семейства Ip (p) является семейство гауссовых ядер типа (3.16).

Для прогнозов pi будет выполнено Следствие 3.1.

для каждой точки (p, x ) [0, 1] X.

Доказательство. По свойству ядра существует такая функция (p, x) со значениями в некотором гильбертовом пространстве признаков H, что Применим неравенство Коши–Буняковского к неравенству (3.20) и получим Отсюда получаем (3.22).

Величина является гладким аналогом числа пар (pn, xn ), находящихся в мягкой окрестности пары (p, x ).

Неравенство (3.22) можно переписать в виде Оценка (3.23) имеет смысл при т.е. сходимость частот к прогнозам будет иметь место только в подпоследовательностях статистически значимой длины.

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

3.5. Задачи и упражнения 1. Доказать, что при использовании смешивания по методу Кричевского и Трофимова условная вероятность 1 после n бинарных наблюдений n = 1,..., n равна 2. Доказать, что также имеет место оценка:

3. Для некоторых последовательностей легко построить калибруемые предсказания. Последовательность 1 2..., состоящая из 0 и 1, называется стационарной, если предел существует.

Доказать, что последовательность прогнозов p1, p2,..., определенная соотношениями p1 = 0 и при i > 1, калибруется на стацонарной последовательности 1 2....

3.6. Лабораторные работы Алгоритм, описанный в разделе 3.3, может быть легко реализован в виде компьютерной программы. При этом для вычисления корня уравнения (3.6) лучше всего использовать гладкое приближение к ядру (3.5) – гауссово ядро K(p, p ) = e(pp ), для некоторого > 0. 1 Можно также использовать ядро вида K(p, p ) = cos((p p )2 ). Корень уравнения (3.6) или (3.15) можно искать методом деления отрезка пополам.

Различные временные ряды можно загружать с сайта FINAM:

http://old.nam.ru/analysis/export/default.asp Например, можно загрузить поминутные данные цен акций какой-нибудь компании:

и откалибровать их так, чтобы Si [0, 1] для всех i.

Лабораторная работа Реализовать алгоритм раздела 3.3. Написать программу для вычисления хорошо калибруемых прогнозов p1, p2,..., pn для двоичной последовательности 1 2... n, где i {0, 1}. Сравнить эти прогнозы с прогнозами по правилу Лапласа.

Двоичную последовательность можно образовать из последовательности приращений S0, S1,..., Sn1, где Si = Si Si1. Это можно сделать следующим образом где – некоторое положительное число.

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

В данном случае сигналы отсутствуют. Для использования сигналов можно использовать ядро (3.16).

Создать графическое представление результатов.

Лабораторная работа Загрузить временной ряд цен какой-либо акции. Нормировать цены акции S0, S1,..., Sn1 так, чтобы Si [0, 1].

Написать программу для вычисления хорошо калибруемых прогнозов p1, p2,..., pn для откалиброванной последовательности чисел S0, S1,..., Sn1.

Произвести отбор подпоследовательностей, на которых прогноз удовлетворяет pi > Si1 + для различных значений > 0.

Создать графическое представление результатов.

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

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

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

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

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

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

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