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

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

4.1. Алгоритм взвешенного большинства В этом разделе мы рассмотрим простейшие алгоритмы на точное предсказание будущего исхода. Имеется два возможных исхода {0, 1}. Имеются N экспертов (стратегий), которые на каждом шаге выдают предсказания pi {0, 1}, i = 1,..., N.

Изучающий алгоритм обозревает в режиме онлайн бинарную последовательность 1... t1 и прогнозы экспертов pi,..., pi, i = 1,..., N, и предсказывает будущий исход pt {0, 1}.

Предварительно рассмотрим случай, когда один из экспертов, например это эксперт 1, точно предсказывает будущий исход: p1 = t t для всех t.

Рассмотрим так называемый Алгоритм большинства. Алгоритм определяет на каждом шаге t = 1, 2,... множество всех экспертов, которые ни разу не сделали ошибку на предыдущих шагах:

Алгоритм большинства выдает прогноз pt = 1, если большинство ранее ни разу не ошибавшихся экспертов выдают 1 в качестве такого прогноза, в противнов случае pt = 0. Точнее, Теорема 4.1. Допустим, что существует эксперт i такой, что pi = t для всех t. Тогда Алгоритм большинства делает не более чем log2 N ошибок, где N – число экспертов.

Доказательство. Если Алгоритм большинства делает ошибку на шаге t, то число ранее никогда не ошибавшихся экспертов уменьшается по крайней мере вдвое: |Bt+1 | |Bt |/2. По предположению |Bt | 1 для всех t. Отсюда число уменьшений величины |Bt | в два раза не превосходит log2 N.

Рассмотрим теперь случай, когда эксперта, точно угадывающего будущие исходы, не существует. В этом случае рассмотрим рассмотрим Алгоритм взвешенного большинства, который был предложен Литтлстоуном и Вармутом [20].

Приведем протокол игры на предсказания с экспертами. Участники игры: Эксперт i, i = 1,..., N, Статистик, Природа. Каждому участнику игры в момент его действия доступна информация о всех действиях других игроков в моменты, предшествующие данному. Говорим, что это игра с полной информацией.

Пусть Алгоритм W M A( ) Полагаем w1 = 1 при i = 1,..., N.

Эксперт i выдает прогноз pi {0, 1}, i = 1,..., N Статистик выдает прогноз pt алгоритма W M A( ):

ENDIF Природа выдает исход t {0, 1} Статистик производит пересчет весов экспертов:

Пусть Et = {i : pi = t } – множество всех экспертов i, которые выдали ошибочный прогноз на шаге t.

Уменьшаем веса таких экспертов:

ENDFOR

|pt t | – число всех ошибок Статистика, т.е. алгоритма W M A( ) на T шагах.

Теорема 4.2. Для любого i выполнено для всех t.

число ошибок наилучшего эксперта на T шагах. Пусть этот минимум достигается для эксперта i. Тогда вес эксперта i корректировался не более m раз. Тогда для всех t таких, что 1 t T.

С другой стороны, если наш алгоритм делает ошибку на шаге t, то Следовательно, По определению Wt+1 Wt для любого t. Отсюда для любого T > 0 имеем где M = LT – общее число ошибок алгоритма W M A( ) на первых T шагах.

Вычисляем натуральный логарифм от обоих частей этого неравенства, проводим следующие переходы:

Вторая строка (4.3) получена из первой с помощью неравенства ln(1 + x) x, которое имеет место при x > 1.

Последняя строка (4.3) получено из предпоследней с помощью неравенства Это неравенство получается из неравенства ln(1 + x) x путем подстановки x = y/(1 y).

Теорема 4.2 показывает, что алгоритм взвешенного большинства WMA ошибается не более чем почти в два раза больше, чем наилучший эксперт.

Теорема 4.1 является частным случаем теоремы 4.2.

Исторически, по-видимому, это первый алгоритм такого рода. Он был предложен Литлстоуном и Вармутом в 1989 году и назывался Weighted Majority Algorithm [20]. Несколько позже, в 1990 году, В.Г. Вовк предложил более общий агрегирующий алгоритм (Aggregating Algorithm) и понятие перемешиваемости, которые работают для игр более общего типа [29].

4.2. Алгоритм оптимального распределения потерь в режиме онлайн В этом разделе мы рассмотрим простейшую модель и алгоритм оптимального следования за экспертами в режиме онлайн для того случая, когда нам доступны только величины потерь экспертов на каждом шаге (какая-либо конкретная функция потерь отсутствует). Этот алгоритм бы предложен Фройндом и Шапире [13].

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

Процесс предсказания представим в форме протокола некоторой игры с полной информацией. Участники игры: стратегии или Эксперты, 1, 2,..., N, а также Распределитель. Цель Распределителя построить стратегию, потери которой были бы не намного больше, чем потери наилучшего эксперта.

На каждом шаге игры t = 1, 2,..., T распределитель определяет вектор распределения стратегий pt = (p1,..., pN ), где дая из стратегий объявляет свои потери на шаге t – число lt, где i = 1, 2,..., N. Потери распределителя на шаге t равны смеси потерь экспертов на этом шаге где t = (lt,..., lt ) – вектор потерь всех стратегий на шаге t.

Мы будем предполагать, что потери экспертов на каждом шаге ограничены, например, lt [0, 1] для всех i и t.

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

Кумулятивные потери Эксперта i на шагах t = 1, 2,..., T равны Соответственно, кумулятивные потери Распределителя на шагах t = 1, 2,..., T равны Цель Распределителя заключается в выборе такой стратегии распределения pt, t = 1, 2,..., T, чтобы минимизировать величину Для решения этой задачи рассмотрим алгоритм Hedge() из работы [13]. Его параметром является число (0, 1), и вектор весов w1 = (w1,..., w1 ).

Предполагаем, что начальные веса всех экспертов удовлетвоN ряют условию Алгоритм Hedge() Распределитель вычисляет распределение экспертных стратегий:

Эксперт i объявляет свои потери lt, i = 1, 2,..., N. Пусть t = 1,..., lN ) – вектор потерь всех стратегий на шаге t.

Распределитель подсчитывает свои потери: lt = (t · t ).

Распределитель производит пересчет весов экспертных стратегий:

ENDFOR

Лемма 4.1. Для любой последовательности векторов потерь 1,..., T экспертных стратегий 1,..., N выполнено неравенl l ство где LT – потери алгоритма распределения Hedge() за T шагов.

Доказательство. Из выпуклости экспоненты имеет место неравенство r 1 (1 )r при всех r [0, 1] и 0 < < 1. Используя это неравенство и комбинируя (4.4) и (4.5), получаем Последовательно применяя (4.7) при t = 1,..., T, получим Мы также использовали свойство Отсюда немедленно следует утверждение леммы.

По (4.6) имеем Из определения весов (4.5) следует Отсюда получаем следующую теорему.

Теорема 4.3. Для любой последовательности векторов потерь 1,..., T экспертных стратегий i = 1,..., N для произвольных i и T выполнено неравенство В случае конечного числа экспертов естественно положить наi чальные веса экспертных стратегий равными w1 = N для всех i.

Тогда (4.10) можно переписать в виде Неравенство (4.11) можно интерпретировать как то, что кумулятивные потери распределительного алгоритма Hedge() не превосходят потерь наилучшего эксперта, умноженных на константу 1 плюс регрет 1.

В работе [30] показано, что оценка (4.11) является неулучшаемой. А именно имеет место теорема.

Теорема 4.4. Пусть B – произвольный алгоритм распределения потерь с произвольным числом экспертов. Допустим, что существуют такие положительные действительные числа a и c, что для произвольного числа N стратегий и для любой последовательности векторов потерь 1,..., T экспертных стратеl l Тогда для всех (0, 1) будет выполнено одно из неравенств:

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

также = g(L/R), где Тогда Доказательство. Мы будем использовать следующее неравенство: ln 1 при (0, 1]. Следующая цепочка преобразований приводит к нужному результату:

Так как мы предполагали, что 0 lt 1 для всех i и t, кумулятивные потери каждого эксперта ограничены: Li T для всех i и T. Поэтому можно в неравенстве (4.12) положить L = T.

Полагаем также R = ln N. Тогда по лемме 4. где LT – кумулятивные потери алгоритма Hedge() за T шагов.

Недостатком этой оценки является то, что параметр зависит от горизонта T. См. также комментарий в конце раздела 4.4.

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

4.3. Алгоритм следования за возмущенным В этом разделе мы рассмотрим другой общий подход к задаче оптимального распределения потерь – алгоритм следования за возмущенным лидером – Follow the Perturbed Leader – FPL. Этот алгоритм еще называется алгоритмом Ханнана по имени его первооткрывателя – см. работу Ханнана [14], а также статью Калаи и Вемпала [18] и монографию Сеза-Бианки и Лугоши [21].

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

Регрет нашего алгоритм имеет тот же порядок, что и алгоритм оптимального распределения потерь или алгоритм взвешенного большинства.

Предсказания с экспертами происходят следующим образом.

На каждом шаге t эксперты i = 1,... N несут потери si. Мы предt полагаем, что потери экспертов на каждом шаге t ограничены:

0 si 1 для всех i и t.

< t, i = 1,... N. Статистик принимает решение следовать за одним из этих экспертов, скажем за экспертом i. В конце шага Статистик несет те же потери, что и выбранный эксперт i: st = si. Кумулятивные потери эксперта исчисляются в виде Легко привести пример игры с двумя экспертами, который показывает, что простое следование за наилучшим экспертом может привести к большим потерям Статистика, значительно превышающим потери каждого из экспертов.

Пусть потери каждого эксперта на шагах t = 0, 1,..., 6 есть s0,1,2,3,4,5,6 = ( 2, 0, 1, 0, 1, 0, 1) and s всегда будет принимать неправильное решение и его кумулятивные потери на каждом шаге будут как минимум в два раза больше чем потери каждого эксперта.

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

Метод следования за возмущенным лидером был впервые предложен Ханнаном [14] в 1957г. Калаи и Вемпала [18] заново переоткрыли этот метод и опубликовали более простое доказательство.

Они предложили название Follow the Perturbed Leader – FPL Дальнейшее изучение этого алгоритма проводилось Хуттером и Поландом [15], которые обобщили его на счетный класс экспертов.

Алгоритм FPL выдает в качестве предсказания номер эксперта i, для которого эяляется минимальной величина где это параметр обучения, и i, i = 1,... N, t = 1, 2,..., есть последовательность независимых одинаково распределенных слуFPL алгоритм.

Статистик выбирает эксперта, имеющего наименьшие возмущеннные кумулятивные потери на шагах < t:

Эксперт i несет потери si for i = 1,..., N.

Статистик несет потери st = sIt.

ENDFOR

чайных внличин распределенных согласно экспоненциальному закону с плотностью p(x) = exp{x}, x 0.

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

Мы будем использовать свойства экспоненциального распределения: P { > a} = ea и P { > a + b} = eb P { > a} для всех неотрицательных значений a и b. Эти и другие свойства экспоненциального распределения предлагаются в виде задач в разделе 5.3.

На шаге t игры каждые из N экспертов несет потери si [0, 1], i = 1,... N ; кумулятивные потери эксперта i исчисляются Пусть t = a/ t для всех t, где константа a будет уточнена далее. Мы предполагаем, что si = v0 = 0 для всех i и 0 =.

Псевдокод FPL алгоритма представлен на рис. 4.1.

шагах T.

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

Теорема 4.5. Математическое ожидание кумулятивных потерь алгоритма FPL с переменным параметром обучения t = ограничено сверху кумулятивными потерями наилучшеt го эксперта плюс регрет:

Доказательство. Анализ оптимальности алгоритма FPL основан на сравнении его потерь с потерями вспомогательного алгоритма IFPL (Infeasible FPL) (see рис. 4.2).

Алгоритм IFPL делает свои предсказания на основе использования величин si, i = 1,... N, которые еще неизвестны Статиt стику в начале шага t. По этой причине данный алгоритм физически не реализуем и служит только для анализа потерь алгоритма FPL.

Математическое ожидание одношаговых на шаге t и кумулятивных потерь алгоритмов FPL и IFPL на шаге T обозначим соответственно, где sIt – потери алгоритма FPL на шаге t и sJt – потери алгоритма IFPL на шаге t, символ E обозначает математическое ожидание.

Лемма 4.3. Средние кумулятивные потери алгоритммов FPL и IFPL удовлетворяют неравенству для всех T.

IFPL алгоритм.

Статистик выбирает эксперта, имеющего наименьшие возмущеннные кумулятивные потери на шагах t:

Эксперт i несет потери si for i = 1,..., N.

Статистик несет потери sJt.

ENDFOR

Доказательство. Пусть c1,... cN – поизвольные неотрицательные действительные числа. Для произвольного 1 j N определим числа mj и mj :

Производим сравнение условных вероятностей:

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

При переходе от 3-й строки к 4-й мы использовали неравенство P { a + b} a} для случайной величины, распределенной согласно экспоненциальному закону, где a и b – произвольные неотрицательные вещественные числа.

Так как эти оценки имеют место при всех условиях ci, они также имеют место в безусловном виде:

Суммируем (4.16) по t = 1,..., T и получим неравенство Неравенство lt rt t lt следует из неравенства rt (1 r)lt при r 1. Суммируем эти неравенства по t = 1,..., T и берем во внимание 0 lt 1 для всех t. В результате получим Лемма доказана.

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

Лемма 4.4. Математическое ожидание кумулятивных потерь алгоритма IFPL ограничено сверху for all T.

Доказательство. Введем в этом доказательстве st = (s1,... sN ) – вектор одношаговых потерь экспертов и s1:t = (s1,... sN ) – векt 1:t тор кумулятивных потерь экспертов. Пусть также = ( 1,... N ) – вектор координатами которого являются экспоненциально распределенные случайные величины.

Рассмотрим вспомогательные векторы:

Для произвольного вектора s = (s1,..., sN ) и единичного вектора d = (0,..., 1,..., 0) обозначим где D = {(0,..., 1),..., (1,..., 0)} – множество, состоящее из N размерности N и “·” – скалярное произведение.

По определению M (s) есть единичный вектор, i-я координата которого равна 1, где si = min sj. Если имеется более одного такого i, то полагаем M (s) равным наименьшему из них.

По определению (M (s) · s) = min sj.

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

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

Имеем 1:T = 1:T 1 + T по определению, а также так как правая часть этого неравенства равна минмальной координате вектора 1:T 1, тогда как левая его часть равна координаs те, которая выбиралась по другому критерию.

Соединяем оба эти замечания вместе и получаем утверждение индукции (4.20) для шага T используя предположение индукции для шага T 1:

Вспоминая определение (4.18) вектора t, мы можем перепиs сать (4.20) следующим образом:

Аналогично, используя определение (4.19) вектора 1:t и то что критерий выбора координаты вновь был изменен, получаем неравенство По определению (M (s1:T ) · ) = k для некоторог k.

Так как E() = 1 для экспоненциально распределенной случайной величины, математическое ожидание вычитаемого члена в (4.22) равно Второй член (4.21) удовлетвояет Здесь мы использовали свойство t < t1 для всех t.

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

Действительно, для экспоненциально распределенных случйных величин i, i = 1,... N, выполнено Для произвольной неотрицательной случайной величины выполнено Доказательство этого соотношение предоставляется читателю в виде задачи из раздела 5.3. Тогда по (4.26) имеем Следовательно, E(maxi i ) 1 + ln N. Согласно (4.25) математическое ожидание (4.24) ограничено сверху числом 1 (1 + ln N ).

Комбинируя оценки (4.21)–(4.24) и (4.23), получим Лемма доказана..

Завершим доказательство теоремы.

Неравенство (4.14) леммы 4.3 и неравенство (4.17) леммы 4. влекут неравенство for all T. Минимизируем (4.29) по a, получим оптимальное значение a = 2 ln N. Таким образом, мы получили оценку (4.13) теоремы Теорема доказана.

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

Для этого нам необходимо усложнить рандомизацию, применяемую в алгоритме FPL. Прежде мы на каждом шаге использовали одну и ту же последовательность независимых одинаково распределенных случайных величин 1,..., N. Мы модифицируем алгоритмы FPL и IFPL следующим образом. Рассмотрим бесконечную последовательность серий независимых одинаково распределенных согласно экспоненциальному закону случайных величин 1,..., N, t = 1, 2,..., так, что все эти случайные величины рассматриваемые вместе независимы.

В алгоритме FPL на рис. 4.1 на шаге t мы будем возмущать каждого эксперта с помощью серии случайных величин t,..., t. Статистик выбирает эксперта, имеющего наименьшие возмущенные кумулятивные потери на шагах < t:

Аналогичное изменения вносим в алгоритм IFPL.

В этом случае одношаговые потери st, t = 1, 2,..., алгоритма FPL будут независимыми случайными величинами.

Доказательства леммы 4.3 остается тем же, доказательство леммы 4.4 изменяется незначительно, надо только в неравенствах (4.21), (4.22) и (4.24) сразу рассмотреть математическое ожидание от обоих их частей и использовать то, что E(t ) = 1 для всех i и Следствие 4.1. Для произвольного > 0 с вероятностью выполнено неравенство Алгоритм FPL является асимптотически состоятельным:

с вероятностью 1.

Доказательство. Для доказательства первого утверждения мы используем вариант неравенство Чернова (4.60) из следствия 4.5:

Пусть X1, X2,... – последовательность независимых случайных величин таких, что при всех i = 1, 2,... выполнено 0 Xi 1. Тогда для любого > неравенства (4.32) следует, что с вероятностью Из этого неравенства и оценки (4.13) теоремы 4.5 получаем неравенство (4.30).

Для доказательства утверждения (4.31) мы применим другой вариант (4.61) неравенства Чернова Здесь полагаем Xt = st. Так как ряд экспонент в правой части этого неравенства сходится, по лемме Бореля–Кантелли с вероятностью 1. Из этого соотношения и оценки (4.13) теоремы 4.5 получаем неравенство (4.31) для верхнего предела.

Следствие 4.1 верно и в более общем случае адаптивно враждебных экспертов, потери которых на каждом шаге t могут зависеть от значений случайных величин st при t < t. В этом случае случайные величины X t = st не будут независимыми, но величины Xt E(Xt ) = st E(st ) образуют мартингал-разности, и мы можем применить соответствующее неравенство Хефдинга– Азумы (4.65) и усиленный мартингальный закон больших чисел (4.63).

4.4. Алгоритм экспоненциального взвешивания экспертных решений Напомним, что R – это множество всех вещественных (действительных) чисел. Пусть – множество исходов, – множество решений или предсказаний (прогнозов), – множество параметров (экспертных стратегий, экспертов). Предполагаем, что – конечное множество, Rn. В этой главе – произвольное множество объектов любой природы.

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

Рассматривается игра с полной информацией между тремя игроками: Статистик (Learner), Множество экспертов (Decision Pool), Природа (Nature). Игра происходит в соответствии со следующим протоколом.

FOR t = 1, 2,...

Эксперты делают предсказания: t.

Статистик принимает свое решение: t.

Природа анонсирует исход: t.

Эксперты вычисляют свои суммарные потери на шаге t игры:

Статистик вычисляет свои суммарные потери на шаге t игры:

Здесь L0 () = L0 = 0 для всех.

ENDFOR

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

Целью Статистика является выбор такой последовательности прогнозов 1, 2,..., чтобы для каждого t его суммарные потери Lt были бы с некоторой степенью точности не больше чем суммарные потери наиболее эффективного эксперта, т.е. не больше чем inf Lt ().

Природа может быть враждебной по отношению к Статистику: выдаваемые ею исходы t могут зависеть от прогнозов t, так как Природа выдает исход t тогда, когда прогноз t уже выдан Статистиком.

Количественной оценкой метода прогнозирования является кумулятивная ошибка, или кумулятивный регрет (cumulative regret) относительно эксперта :

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

Прогнозы будут элементами n-мерного евклидового пространства Rn. Таким образом, их можно складывать и умножать на вещественные числа.

Подножество Z евклидового пространства Rn называется выпуклым, если для любых точек z, z Z и любого числа 0 p точка pz + (1 p)z Z.

Функция h(z), определенная на выпуклом множестве Z, называется выпуклой, если ее надграфик {(x, y) : y h(x)} – выпуклое множество. Это эквивалентно тому, что если для любых z, z Z и любого числа 0 p 1 выполнено неравенство Заданы множества исходов и множество прогнозов. Задана некоторая функция потерь (, ).

Пусть множество экспертов конечно: = {1,..., N }. В этом разделе предполагаем, что множество прогнозов – выпуклое подмножество Rn, а функция потерь (, ) является выпуклой по прогнозу.

Простейший алгоритм взвешивания экспертных прогнозов вычисляет прогноз Статистика по формуле где t Rn – прогноз i-го эксперта на шаге t, wi,t1, i = 1,..., N, – веса, приписанные экспертам на шаге t, – нормированные веса. Так как – выпуклое множество, t для всех t.

В алгоритме экспоненциального взвешивания в качестве весов экспертов берут величины i = 1,..., N, где Lt1 (i) – суммарные потери i-го эксперта на шагах от 1 до t 1, > 0 – некоторый параметр – параметр обучения.

В этом случае прогноз Статистика вычисляется по формуле где – вес эксперта i, i = 1,..., N.

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

Теорема 4.6. Допустим, что функция потерь (, ) является выпуклой по второму аргументу и принимает значения в [0, 1].

Тогда для любых > 0, T и 1,..., T кумулятивная ошибка алгоритма экспоненциального взвешивания удовлетворяет неравенству Доказательство. Определим вспомогательные величины W0 = N.

В доказательстве будет использоваться неравенство Хефдинга, которое сформулировано и доказано в разделе 4.7 в виде леммы 4.5. Эта лемма утверждает следующее: пусть X – случайная величина и a X b. Тогда для произвольного s R где E – математическое ожидание.

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

Нижняя оценка получается следующим образом. Заметим, что так как wi,0 = 1 для всех i = 1,..., N, Верхняя оценка величины ln WT получается с помощью следуW ющих выкладок. Имеем для произвольного t где математическое ожидание рассматривается относительно распределения вероятностей:

Применим неравенство Хефдинга (4.58), в котором a = 0, b = 1, случайная величина X принимает значение (t, t ) с вероятностью wi,t1. Используем также выпуклость функции потерь (, ) по второму аргументу. В результате получаем следующие неравенства:

где t – прогноз по алгоритму экспоненциального смешивания (4.40).

Отсюда, суммируя (4.46) по t = 1,..., T, получим Используя нижнюю оценку (4.44) и верхнюю оценку (4.47), получим Теорема доказана.

2T ln N. Очевидный недостаток при выборе параметра заключается в том, что для его выбора надо фиксировать величину T – горизонт, до которого делается предсказание.

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

4.5. Алгоритм экспоненциального взвешивания с переменным параметром обучения Рассмотрим технически более сложную конструкцию алгоритма экспоненциального взвешивания с переменным параметром обучения, предложенную Алексеем Черновым [8].

Далее, LT (i) – суммарные потери i-го эксперта за первые T шагов, LT – суммарные потери Статистика.

Множество экспертов конечно: = {1,..., N }, множество прогнозов – выпуклое подмножество Rn, а функция потерь (, ) является выпуклой по прогнозу.

Модифицируем алгоритм экспоненциального взвешивания – в качестве весов экспертов берем величины i = 1,..., N, где Lt1 (i) – суммарные потери i-го эксперта на шагах от 1 до t 1, t > 0 – переменный параметр обучения.

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

Теорема 4.7. Для любой последовательности положительных вещественных чисел 1 2..., для любого n 1 и для любых 1,..., n, ошибка (регрет) алгоритма экспоненциального взвешивания с переменным параметром обучения t удовлетворяет неравенству Доказательство. На шаге t Статистик вычисляет свое предсказание по формуле pt = N t wi,t1 /Wt1, где wi,t1 = et Lt1 (i) и Wt1 = j=1 wj,t1. Из выпуклости функции по второму аргументу получаем Применяем неравенство Хефдинга и получаем Перепишем это неравенство в виде Введем вспомогательные величины и заметим, что Докажем, что N N sj,t 1 математической индукцией по t.

При t = 0 это утверждение выполнено, так как si,0 = 1 для всех i. Допустим, что N N sj,t1 1. Тогда и [0, 1] и так как 0 t t1. Используя (4.52) в качестве границы знаменателя из правой части (4.51), получим wi,t1 /Wt Заметим, что Отсюда получим N N sj,t 1.

Так как для произвольного i выполнено получаем отсюда следует (4.49).

4.6. Рандомизированные прогнозы Заданы множества исходов и множество прогнозов. Имеется N экспертов. Задана некоторая функция потерь (, ). В этом разделе мы не предполагаем, что функция потерь выпуклая по второму аргументу.

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

Пусть L0 = 0, L0 (i) = 0, i = 1,..., N.

FOR t = 1, 2,...

Эксперт i выбирает прогноз: t, i = 1,..., N.

Статистик выбирает прогноз: t.

Природа выбирает исход: t.

Эксперт i вычисляет свои суммарные потери на шаге t игры:

Статистик вычисляет свои суммарные потери на шаге t игры:

ENDFOR

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

Потери Статистика на шагах t = 1,..., T равны Потери эксперта i на шагах t = 1,..., T равны Пример. Приведем пример, который показывает, что в некоторых играх с невыпуклой по прогнозу функцией потерь (, ) любой метод детерминированных предсказаний имеет недопустимо большую ошибку, которая растет линейно с ростом длины периода предсказания.

Рассмотрим простую игру с двумя экспертами 1 и 2. Пространства исходов и прогнозов совпадают: = = [1, 2]. Потери при предсказании и исходе равны: (, ) = 1{=} – характеристическая функция множества {(, ) : = }.

Легко проверить, что эта функция потерь не является выпуклой по прогнозу.

Заметим, что для любой детерминированной стратегии Статистика 1, 2,... существует такая последовательность исходов 1, 2,..., что потери Статистика максимальны, т.е. LT = T для всех T. Действительно, Природа может определить для всех Рассмотрим двух экспертов, один из которых – эксперт 1, всегда предсказывает t = 1, а другой – эксперт 2, всегда предсказывает 2 = 2, t = 1, 2,.... Пусть L (i) – потери i-го эксперта, i = 1, 2.

Заметим, что Статистик при прогнозе t = 1 просто следует решению эксперта 1, а при прогнозе t = 2 – следует решению эксперта 2.

Легко видеть, что, так как для произвольной последовательности исходов 1, 2,..., t число единиц или число двоек будут не больше чем t/2, у одного из экспертов потери будут не более чем t/2. Поэтому mini=1,2 Lt (i) t/2 для всех t.

Таким образом, для любой стратегии Статистика адаптивно враждебная Природа может предоставить последовательность 1, 2,... такую, что для всех T.

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

Этот же пример подходит для = = {1, 2}.

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

Пусть теперь на каждом шаге t игры Статистик выдает прогноз в виде смешанной стратегии – распределения вероятностей pt = {p1,t,..., pN,t } на множестве экспертов {1,..., N }.

Мы введем еще одного игрока – Генератора случайных чисел, который будет генерировать элементы множества {1,..., N } согласно заданному ему распределению вероятностей.

Протокол рандомизированной игры имеет следующий вид.

Пусть L0 = 0, L0 (i) = 0, i = 1,..., N.

FOR t = 1, 2,...

Эксперт i выбирает прогноз: t, i = 1,..., N.

Статистик выдает распределение вероятностей: p1,t,..., pN,t на множестве экспертов {1,..., N }.

Природа выбирает исход: t.

Генератор случайных чисел выбирает эксперта: it {1,..., N } с вероятностью pi,t.

Эксперт i вычисляет свои суммарные потери на шаге t игры:

Статистик вычисляет свои суммарные потери на шаге t игры:

ENDFOR

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

Вводим случайные переменные It, так что It = i тогда и только где величины U1, U2,... – независимые равномерно распределенные в единичном отрезке случайные величины. Из определения следует, что P {It = i} = pi,t для всех t.

В такой игре потери Статистика (t, t t ) являются случайной величиной. В этом случае качество Статистика измеряется также случайной величиной – случайной ошибкой предсказания:

Рассмотрим постановку, при которой целью Статистика является минимизация математического ожидания ошибки (4.53) :

Будем вычислять распределение вероятностей на множестве экспертов с помощью соотношений (4.4) из раздела 4.2. На шаге t определим Алгоритм вычисления вероятностных стратегий (4.55) будет называться вероятностным алгоритмом экспоненциального взвешивания.

Из леммы 4.2 следует Теорема 4.8. Пусть LT – случайные кумулятивные потери алгоритма Hedge() за T шагов при = g(T / ln N ), где Тогда имеет место оценка математического ожидания случайных потерь вероятностного алгоритма экспоненциального взвешивания Недостатком этой оценки является то, что параметр зависит от горизонта T. См. также комментарий в конце раздела 4.4.

Заметим, что для любого t вектор вероятностей {p1,t,..., pN,t } на множестве экспертов зависит от последовательности предшествующих исходов 1,..., t1, выдаваемых Природой, а последовательность 1,..., t, в свою очередь может зависеть от последовательности распределений {p1,s,..., pN,s }, s = 1,... t, выдаваемых Статистиком.

По теореме Ионеско–Тульчи (см. [3]) существует распределение вероятностей P, определенное на бесконечных траекториях выбираемых экспертов i1, i2,..., где it {1,... N }, при всех t = 1, 2,..., порожденное всеми распределениями {p1,t,..., pN,t }, Используя следствие 4.7 из неравенства Хефдинга–Азумы (лемма 4.6 ниже), можно получить следующее следствие из неравенства 4.56.

Следствие 4.2. Пусть 0 < < 1. Тогда ошибка (регрет) вероятностного алгоритма экспоненциального взвешивания с вероятностью 1 удовлетворяет неравенству Доказательство. По определению случайные величины представляют собой последовательность ограниченных мартингалразностей. Поэтому для их сумм по следствию 4.7 выполнено неравенство где c – произвольное положительное число (см. неравенство (4.63)).

Отсюда для произвольного > 0 выполнено неравенство Утверждение следствия теперь прямо следует из этого неравенства и неравенств (4.54) и (4.56).

Пусть в игре на предсказания с использованием экспертов i = 1,..., N некоторый предсказатель выдает прогнозы 1, 2,..., а i-й эксперт выдает прогнозы 1, 2,....

Предсказатель называется состоятельным по Ханнану, если с P-вероятностью Следствие 4.2 влечет следующее следствие.

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

При этом прогнозы предсказателя определяются как t = t t для всех t.

Поясним, как соотносится пример, приведенный в начале этого раздела, со следствием 4.3. В примере Статистик при прогнозе t = 1 на шаге t просто следует решению эксперта it = 1, а при прогнозе t = 2 - следует решению эксперта it = 2. Получаем бесконечную траекторию выбираемых экспертов: i1, i2,... При рандомизированном выборе экспертов P-вероятность выбрать эту траекторию, а также любую другую, на которой нарушается условие (4.57), равна 0.

Сравнение с теоремой 4.2 показывает, что радомизированный алгоритм, примененный к простой функции потерь, имеет примерно в два раза меньшую оценку ошибки, чем детерминированный алгоритм взвешенного большинства WMA.

4.7. Некоторые замечательные неравенства Приведем несколько замечательных неравенств, которые неоднократно используются в доказательствах теорем. Основным таким неравенством будет неравенство Хефдинга.

для произвольного s R Доказательство. Так как достаточно доказать, что для любой случайной величины X с E(X) = 0, a X b, будет Из выпуклости экспоненты имеем при a x b.

Обозначим p = ba. Так как E(X) = 0, то применяя математическое ожидание к обеим частям этого неравенства, получим при x = X :

где u = s(b a), (u) = pu + ln(1 p + peu ).

Производная (u) по u равна Имеем (0) = (0) = 0. Кроме того, Действительно, обозначим q = (1 p)eu. Тогда надо доказать неравенство (p+q) По формуле Тейлора для некоторого [0, u] получаем так как u = s(b a). Лемма доказана.

Рассмотрим несколько следствий, разъясняющих значение этого неравенства.

Следствие 4.4. Пусть X – случайная величина такая, что P {a X b} = 1. Тогда Доказательство. Предварительно напомним неравенство Маркова. Пусть X – случайная величина, X 0. Из следует, что P {X > c} E(X)/c.

Используя это неравенство и неравенство (4.58), получим для всех s. Находим минимум правой части по s. Он достигается при s = 4c/(b a)2. Отсюда получаем Аналогично получаем Окончательно получаем Более известным является следующее следствие из этой леммы – неравенство Чернова. Следствие 4.5. Пусть X1, X2,... – последовательность независимых случайных величин таких, что при всех i = 1, 2,...

выполнено P {ai X bi } = 1. Тогда для любого > 0 :

Для удобства иногда используем обозначение exp(x) = ex.

а также Доказательство. Доказательство аналогично доказательству следствия 4.4. Из неравенства Маркова и неравенства (4.58) получаем При преходе от второй строки к третьей мы использовали независимость случайных величин X1, X2,....

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

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

Следствие 4.6. Пусть X1, X2,... – последовательность независимых случайных величин таких, что при всех i = 1, 2,...

выполнено P {ai X bi } = 1. Тогда для любого > Если ai = 0, bi = 1 для всех i, то Последовательность случайных величин V1, V2,... называется мартингал-разностью относительно последовательности случайных величин X1, X2,..., если для любого i > 1 величина Vi есть функция от X1,..., Xi и с вероятностью 1. Следующее неравенство называется неравенством Хефдинга–Азумы.

Лемма 4.6. Пусть V1, V2,... – мартингал-разность относительно последовательности случайных величин X1, X2,..., кроме этого, Vi [Ai, Ai + ci ] для некоторой случайной величины Ai, измеримой относительно X1,..., Xi, и некоторой последоk для любого s > Доказательство. Имеем Здесь при переходе от первой строки ко второй была использована лемма 4.5.

Результат леммы получается путем итерации неравенства (4.62).

Следующее следствие доказывается аналогично следствию 4.4.

Следствие 4.7. Пусть V1, V2,... – мартингал-разность относительно последовательности случайных величин X1, X2,..., кроме этого, Vi [Ai, Ai + ci ] для некоторой случайной величины Ai, измеримой относительно X1,..., Xi, и некоторой последоn вательности положительных констант ci. Если Sn = Vi, то для любого n > Доказательство. Используем неравенство Маркова и неравенство (4.58). Получим для произвольного n :

для всех s. Находим минимум правой части по s. Он достигается Аналогично получаем Окончательно получаем Следствие 4.8. В условиях следствия 4.7, где к тому же ci = для всех i, получаем Так как ряд экспонент в правой части неравенства (4.64) сходится, по лемме Бореля–Кантелли получим Следствие 4.9. В условиях следствия 4.7, где к тому же выполнено B1 < ci < B2 для всех i, для некоторых положительных констант B1, B2 получаем усиленный мартингальный закон больших чисел:

4.8. Задачи и упражнения 1. Построить вариант алгоритма большинства для случая года ммеется эксперт, про которого извество, что он делает не более k ошибок. Получить оценку числа его ошибок.

2. Допустим, что потери экспертов равны 0 или 1. Пусть s – эксперт, имеющий минимальные кумулятивные потери Ls, LT – потери предсказателя в алгоритме Hedge. Доказать, что LT Ls. T 3. Рассмотрим протокол игры на предсказания с использованием экспертов, в котором Природа выдает последовательность 0T (01)T 1T. Имеется три эксперта, каждй из которых выдает постоянное предсказание: Эксперт 1 всегда предсказывает t = для всех t = 1,..., 4T, Эксперт 2 предсказывает t = 1 ля всех t = 1,..., 4T, Эксперт 3 предсказывает t t = 1,..., 4T. Функция потерь – (, ) = | |.

Вычислить для всех t = 1,..., 4T :

(i) веса экспертов;

(ii) потери Распределителя из алгоритма Hedge и предсказания алгоритма экспоненциального взвешивания.

4. Проверить простейшие свойства экспоненциального распределения с плотностью p(x) = ex : P { > a} = ea и P { > a+b} = eb P { > a} для всех неотрицательных значений a и b.

5. Доказать, что для любой неотрицательной случайной величины с плотностьью распределения p(t) выполнено соотношение:

Замечание. Использовать свойство p(y) = F (y), где F (y) = 0 p(t)dt = 1 P { y} – функция распределения случайной величины. После этого, проинтегрировать по частям E() = 0 tp(t)dt.

6. Провести доказательство леммы 4.4 для того случая, когда на каждом шаге t в алгоритмах FPL и IFPL для рандомизации исN пользуется вся серия случайных величин t,..., t, t = 1, 2,....

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

Будет изучаться алгоритм AdaBoost (от английских слов адаптивность и усиление ), предложенный Фройндом и Шапире [13].

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

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

Напомним задачу построения классификатора. Предсказатель получает выборку, S = ((1, y1 ),..., (l, yl )), где xi X и yi Y.

мерного арифметического векторного пространства. Мы также предполагаем, что для всех i пары (i, yi ) одинаково и независимо распределены согласно неизвестному нам распределению вероятностей P на X Y.

Cтрогий алгоритм машинного обучения для произвольных, > 0 при обучении на достаточно большой случайной выборке S с вероятностью 1 выдает гипотезу классификации hS, которая имеет ошибку обобщения не более. Кроме этого, время работы такого алгоритма должно полиномиальным образом зависеть от 1/, 1/ и размера выборки.

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

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

Пусть D(i) – произвольное распределение вероятностей на индексах (элементах) выборки. По определению D(i) 0 для всех i Естественный пример такого распределения – равномерное распределение на элементах выборки: D(i) = 1/l для всех i.

Ошибка обучения классификатора h на обучающей выборке S относительно распределения D определяется как В частности, при распределении D(i) = 1/l ошибка обучения равна доле числа неправильных классификаций объектов:

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

В этом разделе мы решаем частный случай общей задачи – мы рассмотрим метод усиления слабого алгоритма классификации на обучающей выборке. Будет приведен алгоритм AdaBoost (предложенный Фройндом и Шапире [13]), который перестраивает произвольный слабый алгоритм классификации, имеющий ошибку обучения угодно малую ошибку обучения (все ошибки – относительно распределения D).

Алгоритм AdaBoost деление D на {1,..., l}, слабый алгоритм классификации WeakLearn.

Определим начальные значения весов: w1 = D(i) для i = 1,..., l.

1) Полагаем при i = 1,..., l 2) Вызываем алгоритм WeakLearn, в котором D(i) = pi для всех i и который возвращает гипотезу классификации ht .

3) Вычисляем ошибку обучения классификатора ht :

4) Полагаем t = t /( 5) Определим адаптированные веса при i = 1,..., l :

ENDFOR

Результат работы алгоритма: выдать гипотезу – индикаторную функцию:

где пороговая функция f определяется в виде линейной комбинации гипотез алгоритма WeakLearn с весами Приведенный алгоритм представляет собой некоторую версию алгоритма оптимального распределения потерь в режиме онлайн Hedge() (см. раздел 4.2), в котором параметр динамически изменяется по шагам алгоритма. Кроме того, рассматривается двойственная версия этого алгоритма. В данном алгоритме веса приписываются не стратегиям, а элементам выборки. Так как теперь потери на шаге t измеряются величиной lt = 1 |ht (i ) yi |, такие потери равны нулю, если гипотеза ht неправильно классифицирует объект xi, и они максимальны (единица), если классификация – правильная. Соответственно, вес неправильной классификации растет, а вес правильной классификации уменьшается. Таким образом, алгоритм AdaBoost выделяет примеры, на которых алгоритм WeakLearn дает неправильные классификации и заставляет его обучаться на этих примерах.

При анализе будет существенно использоваться свойство слабого алгоритма WeakLearn – при любом распределении на элементах выборки его ошибка обучения меньше чем 1/2 на некоторую положительную величину.

Результат работы алгоритма AdaBoost оценивается в следующей теореме.

Теорема 5.1. Предположим, что слабый алгоритм классификации WeakLearn при его вызовах алгоритмом AdaBoost на шагах t = 1,..., T выдает гипотезы с ошибками обучения 1,..., T (относительно соответствующих распределений, заданных в векторном виде p1 = D, p2,..., pT ). Тогда ошибка обучения результирующей гипотезы h, выданной алгоритмом AdaBoost после T шагов работы, ограничена Доказательство. Так же, как в доказательстве лемм 4.1 и 4. ем верхнюю оценку:

Используя (5.2) T раз, получим ритма WeakLearn на шаге t :

Лемма 5.1. Результирующий классификатор h делает ошибку на объекте xi тогда и только тогда, когда Доказательство. Действительно, это утверждение прямо следует из определения классификатора hf в случае, когда yi = 0, так как в таком случае t t i i = t t i для всех t. По определению равенство h(i ) = 1 может быть тогда и только тогда, когда Неравенство (5.5) эквивалентно неравенству (5.4).

|ht (i )yi | (1ht (i )) Равенство h(xi ) = 0 по определению возможно только при Неравенство (5.7) эквивалентно неравенству Неравенство (5.8) с учетом равенства (5.6) эквивалентно неравенству (5.4) леммы. Лемма доказана.

Возвращаясь к доказательству теоремы, заметим, что по определению По лемме 5.1 из (5.4) и (5.9) получаем где – ошибка обучения результирующего классификатора h относительно распределения D.

Комбинируя (5.3) и (5.10), получим Так как элементы произведения (5.11) неотрицательны, можно минимизировать по t каждый сомножитель отдельно. Приравниваем к нулю производную по t :

и получаем: t = t /(1 t ). Подставляем это выражение для t в (5.11) и получаем (5.1). Теорема доказана.

Следствие 5.1. Ошибка обучения результирующего классификатора h удовлетворяет неравенству В случае, когда t = для всех t, неравенство (5.12) упрощается до Доказательство. Действительно, в оценке (5.1) теоремы 5. при t = 2 t будет Отсюда Неравенство (5.12) доказано.

Для доказательства (5.13) заметим, что неравенство (5.12) при t = превращается в Оценка (5.13) представляет собой обычную экспоненциально убывающую оценку ошибки обучения типа неравенства Хефдинга.

Неравенство (5.13) позволяет оценить число итераций алгоритма AdaBoost, необходимых для достижения ошибки обучения результирующего классификатора h :

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

5.3. Problems 1. Construct a variant of the weighted majority algorithm for the case when an expert exists in the pool which makes no more than k mistakes. Compute a performance bound for this algorithm.

2. Assume that one-step losses of all experts are 0 and 1. Let s be the best expert which has minimal cumulative loss Ls at the rst T steps, and let LT be a cumulative loss of the algorithm Hedge. Prove 3. Consider the protocol of the game of prediction with expert advice, where Nature outputs a sequence 0T (01)T 1T. There are three constant experts. Expert 1 ouputs t = 0 for all t = 1,..., 4T, Expert all t = 1,..., 4T. The loss function is (, ) = | |.

Compute at all time points t = 1,..., 4T :

(i) the weights of experts;

(ii) the loss Allocator and prediction of the exponentially weighted forecaster.

4. Check the simplest properties of the exponential distribution with density p(x) = ex : P { > a} = ea and P { > a + b} = eb P { > a} for all nonnegative a and b.

5. Prove that for any non-negative random variable with a density p(t) the following equality is valid:

Note. Use p(y) = F (y), where F (y) = 0 p(t)dt = 1 P { y}.

After that, apply the integration by parts of E() = 0 tp(t)dt.

Глава Агрегирующий алгоритм Вовка Рассмотренные в главе 4 алгоритмы машинного обучения, использующие конкурирующие экспертные стратегии, имели регрет (ошибку обучения) порядка O( T ln N ), где T – длина периода, N – число экспертных стратегий. Для некоторых специальных функций потерь, среди которых – квадратичная и логарифмическая – эту ошибку можно значительно уменьшить до величины порядка O(ln N ). В данной главе будут сформулированы общие требования к подобным функциям потерь и будет описан соответствующий агрегирующий алгоритм, имеющий регрет O(ln N ).

6.1. Экспоненциально вогнутые функции Рассматриваем простейший случай, когда множество исходов является двухэлементным = {0, 1} и множество предсказаний есть единичный интервал = [0, 1]. Аналогичным образом рассматривается случай = {1, 1} и = [1, 1]. Мы будем предполагать, что функции потерь (, ) является неотрицательной и удовлетворяет следующим условиям:

• при каждом функция (, ) непрерывна по ;

• существует [0, 1] такое, что оба значения (0, ) и (1, ) конечные;

• не существует [0, 1] такого, что оба значения (0, ) и (1, ) бесконечные.

Для произвольной функции потерь (, ) рассматривается множество предсказаний и множество суперпредсказаний Из первого свойства функции потерь и компактности [0, 1] следует, что множество суперпредсказаний замкнуто. Для рассматриваемых ниже функций потерь множество предсказаний (6.1) является границей множества суперпредсказаний (6.2).

Нам будет удобно называть полуплоскость [0, +)2, в которой рассматриваются множества предсказаний и суперпредсказаний, пространством предсказаний.

Для произвольного > 0 пусть E : [0, +)2 (0, 1]2 есть гомоморфизм из пространства предсказаний в экспоненциальное пространство для всех x, y [0, +).

При этом гомоморфизме множество предсказаний (6.1) переходит в множество а множество суперпредсказаний (6.2) переходит в множество Функция потерь (, ) называется -смешиваемой, если множество E ( ) является выпуклым. Функция потерь называется смешиваемой (или экспоненциально вогнутой), если она является -смешиваемой для некоторого > 0.

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

Мы будем рассматривать следующие функции потерь: логарифмическую, квадратичную, абсолютную и простую. Первые две будут смешиваемыми.

В случае, когда – конечное, – множество всех распределений вероятностей на, логарифмическая функция потерь определяется: (, ) = ln {}, где и – вероятностная мера на конечном множестве.

Если = {0, 1}, то можно отождествить с вероятностью единицы, тогда 1 – это вероятность нуля. В этом случае можно взять = [0, 1] и рассмотреть логарифмическую функцию потерь в виде или, более подробно, Обобщенная логарифмическая функция потерь определяется как где > 0 – параметр.

Квадратичная функция потерь определяется как где c – некоторая положительная константа. Можно рассмотреть = {0, 1} и = [0, 1].

Рис. 6.1. Множество предсказаний и суперпредсказаний логарифмической функции потерь Можно также использовать непрерывное множество исходов – единичный интервал = [1, 1] и аналогичное множество предсказаний = [1, 1]. Эти множества будут рассматриваться в задаче регрессии.

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

Простая игра на предсказание (простая функция потерь) рассматривается в случае = = {0, 1}. Функция потерь совпадает с абсолютной функцией потерь (при c = 1) и удовлетворяет свойРис. 6.2. Образы множества предсказаний и суперпредсказаний логарифмической функции потерь в экспоненциальном пространстве ству Обсудим геометрические свойства смешиваемых функций потерь. Здесь обобщенная логарифмическая функция потерь играет особую роль.

Легко видеть, что множество предсказаний (6.1) обобщенной логарифмической функции потерь (6.5) есть кривая:

Мы будем рассматривать параллельные сдвиги кривой (6.6) в плоскости суперпредсказаний, т.е. кривые вида Рис. 6.3. Множество предсказаний и суперпредсказаний квадратичной функции потерь для произвольного вектора (, ).

Говорим, что точка плоскости (x1, y1 ) находится северо-восточнее, чем точка плоскости (x2, y2 ), если x1 x2 и y1 y2.

Множество A R2 находится северо-восточнее некоторого параллельного сдвига кривой (6.6), если каждая его точка находится северо-восточнее некоторой точки, лежащей на этом сдвиге (6.7).

Заметим, что прообразами всех прямых вида ax + by = c, где a > 0 и b > 0, рассматриваемых в экспоненциальном пространстве, при гомоморфизме (6.3) являются все параллельные сдвиги кривой ex + ey = 1, рассматриваемой в пространстве суперпредсказаний. Действительно, легко проверить, что прообраз прямой ax + by = c при гомоморфизме E есть кривая Рис. 6.4. Образы множества предсказаний и суперпредсказаний квадратичной функции потерь в экспоненциальном пространстве т.е. параллельный сдвиг кривой ex + ey = 1 на вектор Таким образом, имеется взаимно-однозначное соответствие между такими прямыми ax+by = c в экспоненциальном пространстве и параллельными сдвигами кривой ex +ey = 1 в пространстве суперпредсказаний.

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

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

Предложение 6.1. Функция потерь является -смешиваемой тогда и только тогда, когда для любой точки (a, b), лежащей на границе множества суперпредсказаний, существует параллельный сдвиг e(x) + e(y) = 1 кривой ex + ey = 1, проходящий через точку (a, b), и такой, что все множество суперпредсказаний лежит северо-восточнее этого сдвига.

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

Для смешиваемых функций потерь чрезвычайно эффективным является так называемый агрегирующий алгоритм, который бы предложен в 1990 году В.Г. Вовком [29]. Этот алгоритм был исторически одним из первых алгоритмов подобного рода. Он является обобщением более простого алгоритма взвешенного большинства, который был предложен в 1989 году Литлстоуном и Вармутом [20]. Агрегирующий алгоритм Вовка имеет ошибку предсказания, которая зависит только от числа экспертов и не зависит от длины последовательности.

6.2. Конечное множество экспертов В разделах 4.4 и 4.6 алгоритмы предсказания имели ошибку порядка O( T ln N ), где T – длина периода, а N – число экспертов.

Алгоритмы и результаты этих разделов относились к функциям потерь произвольного вида (в разделе 4.4 дополнительно требовалась выпуклость функции потерь по прогнозам).

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

Приводимый ниже алгоритм имеет ошибку предсказания, не зависящую от длины периода T, эта ошибка имеет вид O(ln N ), где N – число экспертов.

В дальнейшем мы построим стратегию предсказателя, для которой для всех T, где в общем случае может быть c() > 1 для любого значения параметра обучения алгоритма (0, ).

В случае смешиваемых функций потерь будет c() = 1 для некоторых значений параметра обучения.

Предварительно рассмотрим схему алгоритма в случае множества исходов = {0, 1} и конечного множества экспертов = {1, 2,..., N }. Прогнозы могут принимать любые действительные значения = R. Задана функция потерь (, ), где В последующих разделах будут рассматриваться бесконечные (и даже несчетные) пространства экспертов. При этом результаты существенно не изменятся, надо только ввести меры на экспертах и суммы по экспертам заменить на интегралы по.

Напомним протокол игры на предсказания с использованием экспертных прогнозов.

Пусть L0 = 0, L0 (i) = 0, i = 1,..., N.

FOR t = 1, 2,...

Эксперт i выбирает прогноз t, i = 1,..., N.

Статистик выбирает прогноз t.

Природа выбирает исход t.

Эксперт i вычисляет свои суммарные потери на шаге t игры:

Статистик вычисляет свои суммарные потери на шаге t игры:

ENDFOR

Фиксируем параметр обучения > 0 (learning rate), полагаем Введем некоторое априорное распределения P0 (i) на множестве экспертов. Естественно брать равномерное априорное распределение на экспертах P0 (i) = 1/N для всех i, где N – число экспертов.

На шагах t = 1, 2,... Статистик перестраивает веса экспертов i = 1,..., N согласно формуле Таким образом, вес эксперта, имеющего большие потери, уменьшается.

Веса экспертов (6.8) нормируем:

чтобы сумма нормированных весов стала равной 1.

Введем вспомогательную функцию, которая называется псевдопредсказанием :

Алгоритм, выдающий псевдопредсказания, вычисленные по формуле (6.10), обозначаем APA (Aggregating Pseudo Algorithm). Обозначим суммарные потери алгоритма APA за T шагов на последовательности исходов 1,..., T :

Следующая лемма представляет суммарные потери алгоритма APA в более простом и ясном виде.

Лемма 6.1. Суммарные потери обобщенного алгоритма за T шагов могут быть представлены в виде Доказательство. Из (6.8) следует, что Из определения имеют место следующие равенства Последнее равенство следует из определения (6.10). Поскольку (6.12) имеет место для всех T, получаем утверждение леммы Псевдопредсказание gt () представляет собой некоторые усредненные потери и не дает самого предсказания, для которого предназначены эти потери.

В некоторых случаях можно перевести псевдопредсказание в обычное предсказание. Функцией подстановки называется функция t = (gt ), такая, что (, (gt )) gt () для всех.

Рис. 6.5. Пример определения предсказания. Прямая, проходящая через точку M, отмечает точку N = ( (0, ), (1, ) ) на кривой, по которой вычисляется предсказание Мы покажем, что функция подстановки существует, если функция потерь (, t ) является смешиваемой.

Предложение 6.2. Если функция потерь является смешиваемой, то функция подстановки существует.

Доказательство. Пусть функция потерь (, ) является смешиваемой и пусть = e. Из выпуклости образа в экспоненциальном пространстве множества суперпредсказаний функции (, ) следует, что существует такая, что для всех T {0, 1}. Неравенство (6.13) означает, что абсцисса и ордината точки больше или равны чем абсцисса и ордината точки Полагаем (gt ) =. Условие (, (gt )) gt () будет выполнено для всех.

Если функция потерь (, ) вычислима некоторым алгоритмом, то также существует алгоритм, который на шаге t выдает предсказание t = (gt ). Этот алгоритм называется агрегирующим алгоритмом (AA-алгоритм, Aggregating Algorithm).

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

В том случае, когда (gt ) существует, из леммы 6.1 следует, что будет иметь место неравенство Припишем каждому эксперту одинаковый вес P0 (i) = 1/N. Тогда из (6.14) следует, что для произвольного i, для всех T Оценка (6.15) означает, что суммарные потери агрегирующего алгоритма AA не превосходят потери любого эксперта, в том числе и наилучшего, т.е., имеющего наименьшие потери среди всех экспертов, плюс некоторый регрет (ошибку предсказания), который зависит только от числа экспертов и параметра и, что очень важно, не зависит от длины периода предсказания, как это было в алгоритме экспоненциального взвешивания.

6.3. Бесконечное множество экспертов Повторим схему алгоритма в случае бесконечного множества экспертов. Мы предполагаем, что на задана структура вероятностного пространства – сигма алгебра борелевских множеств.

Это позволяет рассматривать меры на. В этом случае суммы по экспертам i = 1,..., N заменяются на интегралы по этим мерам По-прежнему = {0, 1}, = [0, 1]. Задана функция потерь Пусть задано некоторое априорное вероятностное распределение P0 (d) на множестве экспертов.

На шаге t = 1, 2,... Статистик перестраивает веса экспертов в соответствии с формулой Таким образом, вес эксперта, имеющего большие потери, уменьшается. По определению задание весов (6.16) эквивалентно способу вычисления вероятностей событий E по формуле Веса (6.16) нормируем:

Нормированные веса представляют собой вероятностную меру;

для нее Pt () = 1.

Аналогичным образом введем псевдопредсказание Алгоритм, выдающий псевдопредсказания, также обозначается APA, а суммарные потери алгоритма APA за T шагов равны Из (6.16) следует, что Тогда равенство (6.18) переписывается в виде Имеет место аналог леммы 6.1.

Лемма 6.2. Суммарные потери обобщенного алгоритма за T шагов могут быть представлены в виде Доказательство. Доказательство леммы аналогично доказательству леммы 6.1. Из (6.8) следует, что Из определения имеют место следующие равенства:

Последнее равенство следует из определения (6.18).

Поскольку (6.23) имеет место для всех T, получаем утверждение леммы.

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

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

В общем случае, когда функция потерь не является смешиваемой, определяется кривая смешиваемости (mixability curve) c() :

При некоторых естественных предположениях на исходные множества функция c() является непрерывной и невозрастающей.

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

Можно определить минимаксную функцию подстановки.

По определению любая минимаксная функция подстановки (g), удовлетворяющая (6.26), удовлетворяет и неравенству (6.25).

Заметим, что могут существовать другие – не минимаксные, функции подстановки такие, что выполнено условие (6.25). Часто их проще вычислить.

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

В случае конечного числа экспертов неравенство (6.15) переходит в неравенство для всех T и всех k = 1,..., N.

6.5. Логарифмическая функция потерь Пусть множество всех исходов и множество всех экспертов – конечные, множество всех прогнозов = P() – множество всех вероятностных распределений на. При и, величина () = ({}) равна вероятности элемента. Логарифмическая функция потерь определяется (, ) = ln ().

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

Прогноз эксперта i на шаге t – это распределение вероятностей t = t (·) на пространстве исходов.

С каждым экспертом i на шаге t будем связывать распределение вероятностей Qi на, определяемое условными вероятностями:

Такое распределение можно интерпретировать как субъективное условное распределение эксперта i на t-м шаге. Величина (6.27) равна условной вероятности, которую i-й эксперт приписывает будущему исходу, после того как он наблюдал исходы 1,..., t1.

Тогда субъективная вероятность, которая приписывается на шаге t экспертом i последовательности исходов 1,..., t равна произведению Веса экспертов перестраиваются согласно (6.8). В данном случае вес i-го эксперта переопределяется на шаге t :

Веса (6.29) экспертов нормируются как Вероятность Pt (i) представляет собой апостериорную вероятность эксперта i после наблюдения исходов 1,..., t.

Так как (t,t ) = t (t ), псевдопредсказание (6.10) превращаi ется в логарифм байесовской смеси распределений, предлагаемых на шаге t экспертами, Возьмем в качестве предсказания (gt ) алгоритма AA распределение вероятностей, которое представляет собой байесовскую смесь распределений, предлагаемых на шаге t экспертами.

Распределение вероятностей – предсказание алгоритма AA, определяется как Тогда значение логарифмической функции потерь на исходе t при предсказании Статистика, равном распределению t, просто равно псевдопредсказанию Разьясним данный метод и его связь с байесовским правилом на примере первых двух шагов: t = 1, 2.

Каждому эксперту i на шаге t = 1 соответствует его прогноз – распределение вероятностей 1 = 1 (·) на. На первом шаге предсказание алгоритма AA – представляет собой байесовскую смесь вероятностных распределений экспертов относительно априорного распределения P0 на множестве всех экспертов.

После того как появился первый исход 1, Статистик перестраивает априорное распределение на множестве экспертов. Сначала он определяет веса экспертов:

После этого путем нормирования весов вычисляются апостериорные вероятности экспертов i после наблюдения исхода 1 :

Нетрудно заметить, что данная формула представляет собой формулу Байеса для вычисления апостериорной вероятности P1 (i) эксперта i после наблюдения исхода 1.

Аналогичным образом поступаем на шаге t = 2.

Каждому эксперту i на шаге t = 2 соответствует его прогноз – распределение вероятностей 2 (·) на. Предсказание алгоритма представляет собой байесовскую смесь вероятностных распределений экспертов относительно апостериорного распределения P на множестве всех экспертов, построенного на основе исхода, полученного на предыдущем шаге.

После того как появился второй исход 2, Статистик перестраивает апостериорное распределение на множестве экспертов.

Сначала он переопределяет веса экспертов P2 (i) = (2,2 ) P1 (i) = 2 (2 )P1 (i) = 1 (1 )2 (2 )P0 (i).

После этого путем нормирования весов вычисляются апостериорные вероятности экспертов i после наблюдения исходов 1, 2 :

Вновь нетрудно заметить, что последняя часть равенства представляет собой формулу Байеса для вычисления апостериорной вероятности P2 (i) эксперта i после наблюдения исхода 2 на основе предыдущих апостериорных вероятностей P1 (i), вычисленных на предыдущем шаге.

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

Потери i-го эксперта за T шагов равны Это равенство использует определение субъективной вероятности (6.27), которую Статистик приписывает экспертам на шаге t.

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

Неравенство (6.15) превращается в неравенство 6.6. Простая игра на предсказания Напомним, что простая игра на предсказание рассматривается в случае, когда пространство исходов и пространство прогнозов – двухэлементные и совпадают = = {0, 1}. Задача предсказания заключается в том, чтобы точно предсказать будущий исход.

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

Имеется N экспертов; эксперт i делает на шаге t предсказание t {0, 1}.

Для анализа этой игры каждое псевдопредсказание представляется в виде точки (g(0), g(1)) на координатной плоскости R2. Эта точка имеет вид марный вес экспертов, предсказывающих 1 на шаге t, при этом 1p = Pt1 (i) – суммарный вес экспертов, предсказывающих 0 на шаге t.

Все точки типа (6.36) образуют выпуклую кривую, соединяющую точки (1, 0) и (0, 1), которые соответствуют p = 0 и p = 1.

По определению 1/c() равно абсциссе (ординате) точки пересечения прямой y = x и этой кривой. При p = 2 из (6.36) получаем или Применим алгоритм AA к этой игре.

Определим функцию подстановки = (g) следующим образом: (g) = 0, если точка (g(0), g(1)), вычисленная по (6.36), лежит выше прямой y = x, = (g) = 1, если точка (g(0), g(1)) лежит ниже или на прямой y = x.

Эта функция подстановки удовлетворяет условию (6.25), так как при = 0 будет абсцисса g(0) (0, 0) = 0 и ордината g(1) больше ординаты c() точки пересечения биссектрисы координатного угла и кривой (6.36). Таким образом, g(1) c() = c() (1, 0).

Поэтому (, 0) c()g() при всех {0, 1}.

Аналогичным образом получаем неравенство (, 1) c()g() при всех {0, 1}.

Заметим, что если точка (g(0), g(1)) лежит выше прямой y = x, то абсцисса меньше ординаты, т.е. g(0) < g(1), или что эквивалентно p < 1. В этом случае алгоритм предсказывает В противном случае, т.е. если точка (g(0), g(1)) лежит ниже (или на) прямой y = x, то что эквивалентно p 2. В этом случае алгоритм предсказывает Это означает, что алгоритм AA предсказывает 1, если суммарный вес экспертов, предсказывающих 1, больше суммарного веса экспертов, предсказывающих 0; алгоритм AA предсказывает 0 в противоположном случае. Таким образом, алгоритм AA предсказывает как взвешенное большинство экспертов. Этот алгоритм был описан в разделе (4.1).

В этом случае для любого эксперта будет иметь место неравенство 6.7. Игра с квадратичной функцией потерь Изучим игру с квадратичной функцией потерь в простейшем случае, когда пространство исходов двухэлементное: = {1, 1}, пространство прогнозов это по-прежнему все действительные числа = R. Функция потерь – квадрат разности между исходом и прогнозом (, ) = ( )2.

Мы расматриваем случай = {1, 1}, поскольку доказательства в этом случае проще. Все приведенные ниже утверждения также верны и для случая = [1, 1].

Лемма 6.3. Квадратичная функция потерь является -смешиваемой тогда и только тогда, когда 2.

Доказательство. Представим псевдопредсказание (g(1), g(1)) точкой в экспоненциальном пространстве:

Множеству всех предсказаний [1, 1] соответствует параметризованная кривая в экспоненциальном пространстве Функция потерь будет -смешиваемой, если образ множества суперпредсказаний в экспоненциальном пространстве является выпуклым множеством, т.е. тогда и только тогда, когда ограничивающая его кривая поворачивает налево при возрастании (при этом абсцисса уменьшается). Это будет в случае, если выполнено условие вогнутости кривой: d2 x 0.

Вычислим вторую производную параметрически заданной кривой При возрастании параметра величина x() убывает, поэтому dx 1 прогноза величины yt по ранее полученным значениям (x1, y1 ),..., (xt1, yt1 ) и значению аргумента xt. Имеются эксперты – линейные функции f (x) = ( · x), где, x Rn. Значения этих функций при x = xt интерпретируются как прогнозы экспертов на шаге t. В этом разделе мы не подчеркиваем векторы чертой сверху.

Задачей регрессии в режиме онлайн является построение на каждом шаге t прогноза величины yt, используя прогнозы таких линейных экспертов.

В соответствии с теорией предсказаний с использованием экспертных стратегий введем в эту игру экспертов Rn. Эксперт дает на шаге t предсказание – значение линейной функции:

t = ( · xt ).

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

Рассматривается игра с полной информацией между игроками:

Эксперт, Статистик и Природа.

FOR t = 1, 2,...

Природа анонсирует xt Rn.

Эксперты анонсируют прогнозы t = ( · xt ), Rn.

Статистик представляет предсказание t R.

Природа анонсирует yt [Y, Y ].

ENDFOR

Для исчисления потерь используется квадратичная функция потерь. На шаге t Эксперт вычисляет свои потери (yt ( · xt ))2.

Статистик вычисляет свои потери (yt t )2.

Применим к этой игре алгоритм AA с параметром обучения = 1/2Y 2. Введем априорное распределение где a – некоторый параметр (аналогичный параметру, который используется в гребневой регрессии), а константы выбраны из условия нормализации. Здесь используется евклидова норма вектора = (1,..., n ), заданная формулой = 1 + · · · + n. Напомним также, что мы отождествляем скалярное произведение ( · x) и одноэлементную матрицу x, где x – вектор-строка, – вектор-столбец.

Тогда потери произвольного эксперта Rn на шаге t равны:

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

Напомним, что xt = (x1,t,..., xn,t ), = (1,..., n ), а xt, – эти же векторы, записанные в виде столбцов. Здесь мы использовали равенство xt xt = (xt xt ), которое можно проверить по-координатными преобразованиями:

Потери этого эксперта Rn за первые T шагов равны Согласно (6.8) и (6.22) имеем Поэтому произвольное псевдопредсказание на шаге t имеет вид Отсюда, учитывая представления (6.55) для априорного распределения и (6.56) для функции потерь, получим Аналогичное представление имеет место для gT (Y ).

В случае квадратичной функции потерь и множества предсказаний [Y, Y ] можно показать, что функция подстановки существует и имеет вид (6.49) (см. [32]).

Тогда, используя формулу (6.59) для gT (Y ) и аналогичную формулу для gT (Y ), получаем Здесь мы сразу сократили общий множитель PT 1 () в числителе и знаменателе 2-й строки. При переходе от 2-й строки к 3-й мноT житель e t=1 в числителе и знаменателе был вынесен из под интеграла и сокращен.

При переходе от 3-й строки к 4-й мы используем следующую ниже лемму 6.4, из которой следует, что интеграл в числителе 3-й строки равен а интеграл в знаменателе 3-й строки равен где В 4-й строке мы использовали обозначение а при переходе от 5-й строки к 6-й – следующую ниже лемму 6.5, согласно которой F (A, c, x) = c A1 x.

Приведем формулировки и доказательства лемм 6.4 и 6.5.

A – симметричная положительно определенная матрица типа (n n). Тогда где Q0 = minRn Q().

Доказательство. Пусть минимум квадратичной формы достигается при = 0. Полагаем = 0 и Q() = Q( + 0 ).

Легко видеть, что квадратичная часть формы Q есть A. Так (0,..., 0), эта форма не может иметь линейной части. Действительно, в достаточно малой окрестности линейная часть доминировала бы над квадратичной частью и тогда бы на форма Q не принимала бы минимальное значение.

Так как минимум Q() равен Q0, можно заключить, что константа формы есть Q0. Таким образом, Q() = A + Q0.

Остается доказать, что Это следует из теоремы 3 (раздела 2.7) монографии [1].

Лемма 6.5 показывает, что F (A, c, x) = c A1 x.

Лемма 6.5. Пусть A – симметричная положительно определенная матрица типа (n n), b, x Rn. Тогда Доказательство. Для нахождения первого минимума приравниваем частные производные квадратичной формы A+c +x по i к нулю. Здесь = (1,..., n ). Получаем систему уравнений 2A + c + x = Отсюда легко видеть, что этот минимум достигается при значении вектора 1 = 1 A1 (c + x). Аналогично, минимум второй части достигается при 1 = 2 A1 (c x).

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

Таким образом, согласно выражению (6.60) для T, на шаге T Эти формулы показывают, что мы можем записать теперь алгоритм AAR для регрессии следующим образом:

A = aI; b = 0.

FOR t = 1, 2,...

Алгоритм получает xt Rn.

Вычисляем A = A + xt xt.

Выдаем предсказание t = b A1 xt.

Алгоритм получает yt [Y, Y ].

Вычисляем b = b + yt xt.

ENDFOR

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

Теорема 6.3. Для произвольного T Доказательство. Пусть = 2Y. По лемме 6.2 потери алгоритма APA выражаются в виде формулы (6.21). В нашем случае эта формула записывается в виде Экспонента в (6.64) имеет вид eF (), где Пусть минимум F () достигается при = 0.

Тогда по лемме 6.4 выражение (6.64), представляющее потери APA, равно По определению (6.57) кумулятивных потерь эксперта Так как LT (AAR) LT (AP A), отсюда получаем утверждение теоремы.

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

Вспомним формулы для вычисления основных параметров алгоритма:

Пусть K(x, x ) – некоторое ядро, где x, x Rn, и мы получаем на вход выборку S = ((1, y1 ), (2, y2 ),... ) Вводем обозначения:

kT = (k(xi, xT ))T – последний столбец матрицы KT ;

YT – вектор-столбец исходов;

(YT 1, 0) = (y1,..., yT 1, 0) – неполный вектор-столбец исходов, дополненный нулем.

Запишем онлайн алгоритм линейной регрессии (6.65) в виде удобном для перевода в ядерную форму.

Введем матрицу типа T n у которой строки – векторы-строки x1,..., xT. Тогда легко проверить, что а также Имеет место следующая Лемма 6.6. Для любой nm матрицы B и любой mn матрицы C таких, что матрицы aIn + CB и aIm + BC обратимы, имеет место равенство где a – любое вещественное число и In – единичная матрица размера n. Далее индекс n опускаем.

Доказательство. Равенство (6.66) эквивалентно равенству которое очевидно ввиду дистрибутивности умножения матриц.

Используя лемму представим значение предсказания линейной регрессии где KT = XT XT и kT = XT xT. Заметим также, что т.е. элементы матрицы и вектора представляют собой скалярные произведения векторов x1,..., xT.

Адаптивный алгоритм ядерной версии получается из алгоритма линейной онлайн регресии заменой скалярных произведений из матрицы KT = XT XT и вектора kT = XT xT на значения ядра KT = (K(xi, xj ))i,j=1 и kT = (k(xi, xT ))T. Получим выражение для прогноза ядерной версии ядерной многомерной регрессии Оценка ошибки предсказания для ядерной многомерной регрессии имеет вид для всех T.

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

Пусть алгоритм предсказания A использует входные векторы x1, x2,... xT только в виде их скалярных произведений.

Пусть задано ядро K(x, y), где x, y Rn.

Формула для предсказания методом гребневой регрессии может быть преобразована с помощью леммы 6.6 к виду Заметим, что в этих же обозначениях формула (6.67) для адаптивной ядерной регрессии имеет несколько отличный вид:

6.10. Задачи и упражнения 1. Нарисовать графики предсказаний и области суперпредсказаний, а также их образы в экспоненциальном пространстве для квадратичной, логарифмической, асолютной и простой функций потерь для различных > 0. Привести примеры, при которых для логарифмической и квадратичной функций потерь соответствующие области в экспоненциальном пространстве будут выпуклыми (а также невыпуклыми).

2. Доказать, что абсолютная функция потерь не является смешиваемой.

3. Проверить выпуклость кривой (6.36).

4. Нарисовать график кривой c(), заданной равенством (6.37).

5. Вывести неравенство (6.38). Найти оптимальное значение, для которого регрет в (6.38) принимает минимальное значение.

6. Использовать лемму 4.2 из раздела 4.2 для получения оценки с регретом O( T ).

6.11. Лабораторные работы Использовать данные из следующих сайтов для решения задач регрессии.

http : //www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/.

База данных UCI Machine Learning Repository находится на сайте http : //archive.ics.uci.edu/ml/datasets.html Она содержит 185 наборов данных для классификации и регрессии.

Лабораторная работа Построить простую линейную, гребневую регрессии, а также регрессию с помощью стандартного программного обеспечения SVM, данных по формулам разделов 2.8 и 2.8.2, 2.9.2. Дать сравнительный анализ точности регрессии для всех использованных методов.

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

Лабораторная работа Провести линейную регрессию в режиме онлайн с помощью агрегирующего алгоритма из раздела 6.9. Провести сравнительный анализ точности регрессии с другими методами.

Глава Элементы теории игр В данной главе мы сначала рассмотрим классические вопросы теории игр – игры двух лиц с нулевой суммой. Мы докажем минимаксную теорему Дж. фон Неймана, а также рассмотрим методы решения таких игр. Далее, в разделе 9, мы применим минимаксную теорему для решения бесконечно повторяющихся игр на предсказания. В частности, будет рассмотрен новый теоретикоигровой подход к теории вероятностей, предложенный Вовком и Шейфером [24]. В рамках этого подхода наиболее естественным образом формулируется и решается задача построения универсальных предсказаний, рассмотренная в главе 3.

7.1. Антагонистические игры двух игроков Пусть X и Y – множества произвольной природы. Рссмотрим антагонистическую игру двух лиц. Первый игрок выбирает стратегию x X; одновременно с ним второй игрок выбирает стратегию y Y. В нормальной форме игры каждый игрок выбирает стратегию независимо от выбора другого игрока. Задана функция f (x, y) выигрыша первого игрока, которая одновременно является функцией проигрыша второго игрока. Функция f (x, y) определена на декартовом произведении X Y.

В случае f (x, y) < 0 выигрыш первого игрока отрицательный, т.е. является его проигрышем.

Цель первого игрока – максимизация своего выигрыша, цель второго игрока заключается в минимизации своего проигрыша.

Если первый игрок выбрал стратегию x, то его выигрыш будет не меньше чем inf yY f (x, y) независимо от выбора второго игрока. Эта величина называется гарантированным результатом для первого игрока. Наилучший гарантированный результат для первого игрока:

называется нижним значением игры.

Стратегия x0 первого игрока называется максиминной, если С точки зрения второго игрока, выбор стратегии y гарантирует ему максимальный проигрыш: supxX f (x, y) – его гарантированный результат. Наилучший гарантированный результат второго игрока – величина называется верхним значением игры.

Стратегия y 0 второго игрока называется минимаксной, если Доказательство. Имеем для любых x X и y Y Отсюда Левая часть последнего неравенства зависит от x, а правая – нет.

Поэтому для всех y, следовательно, Лемма доказана.

Точка (x0, y 0 ) X Y называется седловой точкой функции f, если Условие (7.1) эквивалентно условию Заметим, что когда мы пишем min вместо inf или max вместо sup, то имеем ввиду, что эти экстремальные значения достигаются в некоторой точке.

Говорят, что антагонистическая игра имеет решение, если функция f (x, y) имеет седловую точку (x0, y 0 ). Число v = f (x0, y 0 ) называется значением, или ценой игры, x0, y 0 – оптимальные стратегии игроков, (x0, y 0, v) – решение игры. Эти названия оправдываются следующей теоремой.

Теорема 7.1. 1) Для того чтобы функция f (x, y) имела седловую точку, необходимо и достаточно, чтобы было выполнено условие 2) Пусть выполнено (7.3). Тогда пара (x0, y 0 ) тогда и только тогда является седловой точкой, когда x0 – максиминная, а y 0 – минимаксная стратегии игроков.

Доказательство. Доказательство необходимости 1) и 2). Пусть (x0, y 0 ) – седловая точка функции f (x, y). Тогда Отсюда v v. По лемме 7.1 имеем равенство v = v. Тогда в (7.4) имеют место равенства, и поэтому x0 – максиминная, а y 0 – минимаксная стратегии.

Доказательство достаточности. Допустим, что (7.3) выполнено. Возьмем x0 – максиминную, y 0 – минимаксную стратегии.

Покажем, что пара (x0, y0 ) является седловой точкой. Действительно, Отсюда следует, что во всех этих неравенствах можно поставить знаки равенства. Таким образом, (x0, y 0 ) – седловая точка.

Игра в орлянку, при которой первый игрок загадывает число 0 или 1, а второй отгадывает, с матрицей выплат не имеет седловой точки. Для нее наилучший гарантированный результат для первого игрока равен: v = maxi minj ai,j = 1, а наилучший гарантированный результат для второго игрока (т.е.

его проигрыш) равен: v = minj maxi ai,j = 1. Эта игра не имеет решения.

7.2. Достаточное условие существования седловой точки Докажем достаточное условие существования седловой точки, следствием к которому является минимаксная теорема.

Предварительно напомним, что подмножество Z Rn евклидового пространства Rn называется выпуклым, если для любых точек z, z Z и любого числа 0 p 1 точка pz + (1 p)z Z.

Функция h(z), определенная на выпуклом множестве Z, называется выпуклой, если для любых z, z Z и любого числа 0 p 1 выполнено неравенство Функция h(z) называется вогнутой, если выполнено неравенство (7.5), где знак заменен на.

Теорема 7.2. Пусть X, Y – выпуклые подмножества Rn и Rm соответственно (где n и m – произвольные натуральные числа), Y – компакт, функция f (x, y) определена на X Y, принимает вещественные значения и ограничена по абсолютной величине, функция f (x, ·) – выпуклая и непрерывная (по y) для каждого значения x X, f (·, y) – вогнутая для каждого значения y Y.

Тогда Доказательство. По лемме 7.1 надо доказать, что Допустим для простоты, что f (x, y) [0, 1].

Фиксируем достаточно малое > 0 и достаточное большое натуральное число n. Из компактности Y следует, что существует -сеть в Y, т.е. конечное множество точек {y 1,..., y N } такое, что каждая точка y Y находится в -окрестности одной из точек y i.

Определим последовательность точек y1, y2,..., yn Y и последовательность точек x1, x2,..., xn X рекурсивно. Пусть x – любая точка X. Определим при t = 1,..., n :

где = (8 ln N )/n и xt выбирается так, чтобы было Так как функция f является выпуклой по второму аргументу, мы можем применить теорему 4.6 с функцией потерь (x, y) = f (x, y).

В алгоритме экспоненциального взвешивания (7.6) величины yi – прогнозы экспертов, i = 1,..., N, xt – исходы, t = 1,..., n, yt – прогноз Статистика. По (4.42) получим Делим это неравенство на n :

Пользуемся выпуклостью функции f по второму аргументу и вогнутостью по первому, а также используя (7.7), получаем Переход от 1-й строки ко 2-й происходит по определению; переход от 2-й к 3-й – по выпуклости f (x, ·); переход от 3-й к 4-й происходит, так как супремум суммы не превосходит суммы супремумов;

переход от 4-й к 5-й происходит по определению xt ; переход от 5-й к 6-й происходит по (7.7); переход от 6-й к 7-й происходит по вогнутости функции f (·, y); переход от 7-й к 8-й происходит по определению супремума.

Таким образом, мы доказали, что для всех n Устремляем n к бесконечности и получаем Устремляем Теорема доказана.

Доказательство теоремы 7.2 содержит метод вычисления цены игры, так как из 1-й, 5-й и 8-й строк неравенства (7.8) следует, что ем к цене игры при достаточно малом 7.3. Смешанные расширения матричных игр 7.3.1. Минимаксная теорема Пусть теперь X = {1,..., N }, Y = {1,..., M }. Соответствующая игра называется матричной. Функция выигрыша f (i, j) = ai,j может быть представлена в виде матрицы. Первый игрок выбирает номер строки, второй игрок – номер столбца, элемент ai,j, находящийся на их пересечении, определяет выигрыш первого игрока и проигрыш второго.

Смешанной стратегией игрока называется распределение вероятностей на множестве его ходов. Смешанное расширение матp ричной игры (X, Y, f (x, y)) определяется как игра (X, Y, f (, q )), где X – множество смешанных стратегий первого игрока, Y – множество смешанных стратегий второго игрока, f (, q ) – среднее значение выигрыша относительно меры p q :

Имеет место минимаксная теорема Дж. фон Неймана.

Теорема 7.3. Всякая матричная игра имеет решение в смешанных стратегиях:

Доказательство. Достаточно доказать, что функция f (, q ) имеет седловую точку. Применим теорему 7.2. Множества X и Y – симплексы в евклидовых пространствах, поэтому являются выp пуклыми. Функция f (, q ) – билинейная и поэтому непрерывна по обоим аргументам, вогнута и выпукла по ним.

Замечание. Можно также рассмотреть последовательный вариант игры двух игроков: сначала первый игрок выбирает элемент p X, потом второй игрок выбирает q Y; при этом второй игрок знает выбор первого игрока. В этом случае первый игрок по-прежнему предполагает, что второй игрок своим выбором будет пытаться минимизировать его выигрыш. Поэтому его оптимальная стратегия состоит в том, чтобы добиться того, чтобы достигался maxpX minqY f (, q ).

При другой последовательности действий сначала второй игрок выбирает q Y, а затем первый игрок, зная его выбор, выбирает p X. Здесь второй игрок зная, что первый игрок в ответ на его ход будет максимизировать его проигрыш, выберет свой ход q Y так, чтобы достигался minqY maxpX f (, q ).

Нетрудно убедиться, что в этом случае по-прежнему верна минимаксная теорема 7.3, т.е.

7.3.2. Чистые стратегии Рассмотрим матричную игру на X = {1,..., N }, Y = {1,..., M } с функцией выигрыша f (i, j) = ai,j. Приведем три простых утверждения, которые более детально описывают структуру оптимального решения в терминах чистых стратегий.