Автоматика и телемеханика, № 11, 2019

(Колумбийский университет, Нью-Йорк, США;

Отдел исследования ИИ Фэйсбук, Нью-Йорк, США)

ПОЛНАЯ СТАТИСТИЧЕСКАЯ ТЕОРИЯ ОБУЧЕНИЯ

Памяти выдающегося ученого и

замечательного человека Я.З. Цыпкина

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

из гильбертова пространства с воспроизводящим ядром: найти в данном

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

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

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

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

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

лучено аналитическое решение.

Ключевые слова: статистическая теория обучения, первая задача выбо-

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

ядром, обучающая выборка.

DOI: 10.1134/S0005231019110023

1. Введение

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

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

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

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

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

условной функции вероятности. Несмотря на качественное различие этих за-

дач, в [1-3] развит единый подход к их решению, позволяющий путем ми-

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

ческих данных, находить функцию, для которой среднее значение функции

потерь близко к минимальному. Мера близости, естественно, зависит от коли-

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

ций, в котором ищется решение поставленной задачи.

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

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

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

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

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

мую функцию. При этом повышается статистическая надежность ответа, но

и, возможно, возрастает смещение найденного решения относительно истин-

ного.

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

точности эмпирических данных известна в функциональном анализе в обла-

сти решения некорректных задач [4]. Метод регуляризации задает процедуру

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

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

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

теории обучения.

В статье рассматривается общая математическая модель обучения, в рам-

ках которой одновременно решаются как задача выбора подмножества до-

пустимых функций, учитывающего специфику эмпирических данных, так и

задача поиска в этом подмножестве решения поставленной задачи. При ре-

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

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

воспроизводящим ядром, описываемые далее. При этом задача минимиза-

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

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

мизации регуляризованного функционала в конечномерном пространстве, а

искомое решение представляется в виде разложения по функциям воспроиз-

водящего ядра.

2. Ограничения существующей статистической теории обучения

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

ния (теория Вапника-Червоненкиса)¹ [1, 2]. Эта теория рассматривает сле-

дующую математическую задачу:

Допустим, что в данном множестве индикаторных функций² y =

= θ(f(x,α)), α ∈ Λ, функция y = θ(f(x,α_ℓ)) минимизирует число ошибочных

классификаций y в ℓ наблюдаемых парах

(x₁, y₁), . . . , (x_ℓ, y_ℓ), x ∈ Rⁿ, y ∈ {0, 1},

где пары (x_i, y_i) генерируются случайно и независимо в соответствии с неиз-

вестной функцией распределения P (x, y) = P (y|x)P (x).

Определим эмпирическую функцию потерь правила θ(f(x, α_∗)) как

∑

P_ℓ(α_∗) =

|y_i - θ(f(x_i, α_∗))|

i=1

и функцию средних потерь относительно распределения P (y, x) как

∫

P (α_∗) =

|y - θ(f(x, α_∗)|dP (x, y).

¹ Теория Вапника-Червоненкиса также называется Статистической теорией обучения.

² Здесь используется обозначение индикаторной функции как y = θ(f(x, α)), α ∈ Λ, где

θ(u) — ступенчатая функция: θ(u) = 1, если u ≥ 0, и θ(u) = 0, если u < 0. Функции f(x, α),

α ∈ Λ, являются параметрическим подмножеством действительных функций, где α ∈ Λ —

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

функций.

Вопрос состоит в том, когда с вероятностью 1 - η можно утверждать, что

наименьшее значение эмпирической функции потерь сходится к наименьше-

му значению функции средних потерь с ростом числа наблюдений ℓ. Другими

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

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

{



}



(2.1)

lim

inPℓ(α) - minP (α)

∀ε > 0.

^m

^>

ℓ→∞

α∈Λ

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

вают выполнение (2.1), и оценить скорость сходимости.

VC теория показала, что для обеспечения условия (2.1), т.е. состоятельно-

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

зываемые методы минимизации эмпирического риска), необходимо и доста-

точно, чтобы специально определенная мера мощности данного (бесконечно-

го) множества функций y = θ(f(x, α)), α ∈ Λ (так называемая комбинаторная

размерность h этого множества), была конечна (определение комбинаторной

размерности и ее значение для теории обучения обсуждается далее).

Было показано, что с вероятностью 1 - η одновременно для всех функ-

ций из множества θ(f(x, α), α ∈ Λ, комбинаторная размерность которого h^∗,

справедлива оценка

(

√

)

4P_ℓ(α)

(2.2)

P (α) ≤ P_ℓ(α) +

где

)

⁽h^∗ - lnη

ε=O

ℓ

Так как (2.2) справедлива для всех α ∈ Λ, то она также справедлива для

функций θ(f(x, α_ℓ)), которые минимизируют частоту P_ℓ(α_ℓ) ошибки обуче-

ния. В соответствии с (2.2) эта функция определяет для данного множества

функций наименьшую гарантированную (с вероятностью 1 - η) вероятность

ошибочной классификации.

Оценка (2.2) показывает, что для гарантии успеха обучения требуется, что-

бы комбинаторная размерность допустимого множества функций θ(f(x, α)),

α ∈ Λ, была мала (чтобы ε в (2.2) было мало), и чтобы допустимое множество

функций содержало функцию, “хорошо” аппроксимирующую y = θ(f(x, α_ℓ))

(чтобы значение P_ℓ(α_ℓ) было мало).

Поэтому полное решение задачи машинного обучения требует решения не

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

1. Выбрать из широкого множества функций (с бесконечной комбинаторной

размерностью) малое допустимое подмножество функций, у которого ком-

бинаторная размерность мала и содержит хорошую аппроксимирующую

функцию θ(f(x, α_ℓ)) (с малым значением P_ℓ(α_ℓ));

2. В допустимом подмножестве функций θ(f(x, α)), α ∈ Λ, выбрать наилуч-

шую аппроксимирующую функцию (для которой P_ℓ(α_ℓ) мало).

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

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

подмножестве³ и не рассматривают первую, возможно более важную, зада-

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

аппроксимирующую функцию (с малым значением функции потерь) с малой

комбинаторной размерностью.

Метод решения первой задачи выбора — основная тема статьи. Однако

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

результаты VC теории, которые используются в этой статье.

3. Некоторые результаты VC теории

3.1. Определение комбинаторной размерности

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

принят термин VC dimension (размерность Вапника-Червоненкиса). Пусть

функции f(x, α), α ∈ Λ, определены на x ∈ X ∈ Rⁿ. Рассмотрим множество

индикаторных функций θ(f(x, α)), α ∈ Λ. Известно, что ℓ различных векто-

ров x₁, . . . , x_ℓ допускают 2^ℓ различных разделений на два подмножества.

Будем говорить, что множество индикаторных функций θ(f(x, α)), α ∈ Λ,

имеет комбинаторную размерность h, если для этого множества:

1) существует h векторов, разделяемых всеми 2^h способами;

2) не существует h + 1 векторов, разделяемых всеми 2(h+1) способами;

3) если для любого ℓ существуют векторы, которые могут быть разделе-

ны всеми 2^ℓ способами, то комбинаторная размерность такого множества

считается бесконечной.

Это определение комбинаторной размерности описывает разнообразие дан-

ного множества функций: было показано в [1], что если множество функций

имеет конечную комбинаторную размерность h, то любые ℓ векторов могут

быть разделены (используя функции множества) не более чем O(ℓ^h) раз-

личными способами. Если комбинаторная размерность h бесконечна, то для

любого ℓ существуют ℓ векторов x_i, которые могут быть разделены всеми 2^ℓ

возможными способами. Комбинаторная размерность — мера разнообразия

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

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

свойство разнообразия (иногда называемого емкостью или сложностью) дан-

ного множества функций.

Справедлива следующая теорема [1-3]:

Теорема 1. Если комбинаторная размерность множества допусти-

мых функций равна h, тогда любые ℓ векторов x_i могут быть разделены

³ Отметим, что наилучшая функция в допустимом множестве может иметь большое

значение функции потерь.

на два подмножества не более чем

)_h

⁽ eℓ

N ≤

различными способами.

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

В теории обучения важную роль играет теорема, которая оценивает ком-

бинаторную размерность множества линейных функций [1].

Теорема 2. Комбинаторная размерность множества линейных функ-

ций

f (x, w) = x^Tw, w ∈ Rⁿ,

где векторы x принадлежат шару радиуса R (т.е. ||x|| ≤ R) и векторы w

принадлежат шару радиуса Δ (т.е. ||w|| ≤ Δ), ограничена выражением

(3.1)

h ≤ min([R²Δ²

], n) + 1.

В соответствии с этой теоремой в пространствах большой размерности n

комбинаторная размерность может быть меньше размерности пространства⁴.

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

емого в этой статье (см. оценку (2.2)).

3.3. Принцип структурной минимизации риска

Для выбора наилучшего правила, используя оценку (2.2), в [1] был предло-

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

пустимом множестве функций S = {θ(f(x, α)), α ∈ Λ} задана структура вло-

женных подмножеств функций S_m = {θ(f(x, α)), α ∈ Λ^m}

S₁ ⊂ S₂ ⊂ ... ⊂ S_m ⊂ ... ,

для которых соответствующие значения комбинаторной размерности h^m упо-

рядочены по возрастанию

h¹ < h² < ... < h^m < ...

Теперь можно минимизировать правую часть в (2.2) выбирая как подходя-

щее подмножество Λ^m, комбинаторная размерность которого равна h^m, так и

функцию θ(f(x, α^mℓ)), которая минимизирует частоту ошибок обучения в Λ^m.

Верна следующая теорема [4-6].

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

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

Эти оценки показывают, что в пространствах очень большой размерности d ∼ 10¹⁰ оценки

комбинаторной размерости составляли всего несколько сотен.

Теорема 3. Если покрытие множества

⋃

S_k = S

k=1

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

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

Этот факт и оценка (2.2) обосновывают многие алгоритмы обучения,

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

риваемых в этой статье.

3.4. Выбор допустимых множеств в методах обучения

Отсутствие в теории обучения механизмов выбора допустимого подмноже-

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

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

отражающими различные типы предположений. Далее опишем два из пред-

положений.

1. Допущение о роли признаков в классификационных методах.

В 1970-х гг. XX в. была представлена идея о том, что допустимое подмно-

жество функций определяется разложением (например, линейным) по специ-

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

и различным для различных задач) и что хорошее решение задачи обучения

должно быть выражено в виде функции (скажем, линейной) от этих синте-

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

Знание свойств таких признаков рассматривалось как априорное знание

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

задачи.

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

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

функций, тем больше данных необходимо для нахождения хорошей аппрок-

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

стороны, чем больше признаков использовано, тем выше шанс найти хоро-

шую аппроксимирующую функцию в допустимом подмножестве. Поэтому ко-

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

ситуацией.

Чтобы разрешить это противоречие, рассматриваются методы сокращения

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

предположении, что существует “хорошее малопризнаковое пространство” и

можно неформально найти его. Формулы (2.2) и (3.1) часто противоречат та-

кому предположению, так как хорошее обобщение зависит не от размерности

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

(см. теорему 3) и существования в подмножестве хорошо аппроксимирующей

функции.

Построение признаков не гарантирует решения какой-либо из задач выбо-

ра.

2. Допущение в обучении с использованием глубоких нейронных сетей.

В 2005-х гг. возникла новая идея структурирования допустимого подмноже-

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

используются нейронные сети со многими слоями. Построение глубоких ней-

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

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

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

ронной сетью. Считается, что (из-за “умной” конструкции глубокой сети) это

подмножество содержит хорошо аппроксимирующую функцию и пытается

найти ее, используя стохастический градиентный спуск (решение второй за-

дачи выбора).

С теоретической точки зрения успех решения обеих задач путем выбора

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

выбор желаемой функции в этом подмножестве) не обоснован, поскольку:

1. Глубокая нейронная сеть не обязательно содержит хорошую аппроксима-

цию желаемой функции. Более того, в соответствии с теоремой о пред-

ставителе (описанной далее) для широких множеств функций гильберто-

ва пространства решения, которые минимизируют функционал эмпириче-

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

“мелкой” сетью (всего с одним скрытым слоем).

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

ния, может не найти наилучшую функцию в подмножестве (этот метод

находит локальный, но не глобальный минимум).

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

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

ную задачу обучения.

4. Теория информации и машинное обучение

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

чения, рассмотрим задачу обучения с точки зрения теории информации.

4.1. Основная модель Шеннона

Развитие теории информации К. Шеннон начал со следующей основной

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

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

ты “да” (y = 1) или “нет” (y = 0), предоставляя запрашивающему один бит

информации.

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

n = log2 N (для простоты предполагаем, что N = 2ⁿ). В самом деле, можно

разделить множество из N объектов на два подмножества и сделать запрос:

к какому из двух подмножеств принадлежит объект: к первому (ответ 1) или

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

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

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

от оставшихся объектов после каждого ответа. Итак, после n = log₂ N запро-

сов найдем желаемый объект. Поэтому чтобы найти один объект в множестве

из N объектов, необходимо получить не более чем n = log₂ N =lnNln2 бит ин-

формации.

4.2. Основная модель Шеннона в терминах теории обучения

Повторим эту модель в терминах задачи распознавания образов. Допу-

стим, что рассматриваемые объекты являются конечным множеством y =

= θ(f(x,a_t)), t = 1,... ,N, индикаторных функций в x ∈ Rⁿ и поставлена

цель — найти в этом множестве неизвестную функцию классификации

y = θ(f(x,α_∗)), запрашивая значение функции для некоторого вектора x.

Допустим, что можно найти такой вектор x₁ ∈ Rⁿ, для которого полови-

на функций из имеющегося множества принимает значение θ(f(x₁, atj )) = 1,

j = 1,...,N/2, а другая половина принимает значение θ(f(x₁,atj)) = 0,

j = N/2 + 1,...,N. Спрашивается, какая классификация вектора x₁ задает

искомую функцию.

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

(x₁, y₁). Используя первый элемент обучающей выборки (x₁, y₁), удаляем из

данного множества половину функций, для которых θ(f(x₁, α)) = y₁ и про-

должаем данную процедуру на оставшихся N/2 функциях.

После

ln N

(4.1)

n = log2 N =

ln 2

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

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

выбранных векторах, необходимо ℓ = log₂ N пар (x_i, y_i).

4.3. Первая модификация модели обучения

Чтобы найти требуемую функцию в рамках базовой модели, необходимо

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

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

классифицирующие данный вектор (считаем, что такое разделение существу-

ет). Чтобы упростить модель, рассмотрим ситуацию, когда векторы x_i полу-

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

ной) мере P (x) и для любого x_i можем узнать соответствующую метку y_i,

формируя обучающую выборку (x_i, y_i). Как и раньше, после каждого запроса

функции, значения которых на векторе x_i отличаются от сообщенного значе-

ния y_i, удаляются из рассмотрения (они могут составлять меньше половины

от текущего набора функций).

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

ходимых для нахождения функции, которая с вероятностью 1 - η ε-близка

к искомой функции (напомним, что как ε-близость, так и вероятность 1 - η

ε-близости определяются относительно меры P (x)). Решение этой проблемы

составляет специальный случай VC теории [3, 7]: число необходимых запро-

сов (наименьший требуемый размер обучающей выборки) равно

ln N - ln η

(4.2)

ℓ=

Полученное выражение отличается от оценки (4.1) на постоянную вели-

чину: ε-1 вместо (ln 2)-1. После этого числа запросов с вероятностью 1 - η

любая функция в оставшемся наборе является ε-близкой к искомой функции.

Данная оценка неулучшаема.

4.4. Вторая модификация модели обучения

До сих пор рассматривалась ситуация, в которой набор из N функций

включал функцию, не делающую ошибок. Ослабим это допущение: любая

из N функций может ошибаться. Проблема заключается в поиске функ-

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

меры P (x). В этой ситуации нельзя воспользоваться методом выбора искомой

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

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

зуемся обобщением данного метода, в котором среди N заданных функций

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

ными в запросах значениями, т.е. минимизирующая эмпирические потери на

обучающей выборке

(x₁, y₁), . . . , (x_ℓ, y_ℓ).

Можно показать, что для того чтобы с вероятностью 1 - η гарантировать

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

ln N - ln η

(4.3)

ℓ=

ε²

примеров [3, 6]. В этой модификации числитель ln N - ln η остается прежним,

но в отличие от (4.2) в знаменателе стоит ε².

Оценкам (4.2) и (4.3) можно дать следующую интерпретацию: в стати-

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

выбора искомой функции меньше одного бита информации, в то время как в

модели обучения Шеннона один обучающий пример вносит один бит инфор-

мации. Оценки (4.2) и (4.3) неулучшаемы.

4.5. Третья модификация (VC модель)

Теперь рассмотрим набор функций θ(f(x, α)), α ∈ Λ, с бесконечным чис-

лом элементов. Вообще говоря, в этой ситуации нельзя гарантировать, что

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

обучающих примеров.

Тем не менее если этот набор функций имеет конечную комбинаторную

размерность h, то в соответствии с VC теорией с вероятностью 1 - η ε-близкое

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

)

⁽h - lnη

ℓ∼O

примеров, если аппроксимирующая функция не делает ошибок. Если ошибки

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

)

⁽h - lnη

ℓ∼O

ε²

Отметим, что эти оценки имеют вид границ (4.2), (4.3), где величина ком-

бинаторной размерности замещает логарифм числа функций в наборе. Эти

оценки неулучшаемы [3, 7].

4.6. Три категории больших чисел

Следуя А.Н. Колмогорову, выделим три категории целых чисел.

1. Обычные числа. Назовем обычными целые числа n, если они соответству-

ют ряду понятий из обычной жизни. Например, можно определить как

обычные (маленькие) целые числа от 1 до миллиона (или миллиарда).

2. Большие числа. Назовем целые числа N большими числами, если

10⁹ < N << 2ⁿ (n принадлежит категории обычных чисел).

3. Гигантские числа. Назовем целые числа N гигантскими числами, если

больше больших чисел N >> 2ⁿ (скажем, имеют порядок N = O(22n )).

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

функции из множества N функций, когда один пример вносит до одного бита

информации (число кандидатов уменьшается максимум вдвое). Следователь-

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

мере большим (но не гигантским).

В рассмотренных моделях, используя обычное число ℓ обучающих при-

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

элементов (либо из набора функций с большой или бесконечной величиной

комбинаторной размерности). Чтобы это сделать, необходимо использовать

механизм, в котором один «пример» может внести гораздо больше, чем один

бит информации.

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

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

5. Два вида сходимости в гильбертовом пространстве

В настоящей статье в качестве множества аппроксимирующих функций

используются действительные функции f(x, α), α ∈ Λ, которые принадлежат

гильбертовому пространству. Гильбертово пространство H определяется опе-

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

бых двух элементов u, v пространства значение (u, v) скалярного произведе-

ния. Скалярное произведение определяется как величина, удовлетворяющая

следующим трем свойствам:

1. Симметричность. Скалярное произведение двух элементов — симметрич-

ная функция

(u, v) = (v, u).

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

((a₁u₁ + a₂u₂), v) = a₁(u₁, v) + a₂(u₂, v).

3. Положительная определенность. Скалярное произведение положительно

определено

(u, u) ≥ 0

∀u,

(u, u) = 0, если и только если u = 0.

При использовании скалярного произведения (u, v) расстояние определя-

ется как

√

ρ(u, v) = ||u - v|| =

((u - v), (u - v)).

Гильбертово пространство определяется как полное метрическое простран-

ство относительно этой метрики.

5.1. Сильная и слабая сходимости в гильбертовом пространстве

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

странстве — расстояние и скалярное произведение — позволяют ввести два

разных вида сходимости: сильную и слабую.

1. Сильная сходимость функций f_ℓ(x) к f₀(x) требует, чтобы

lim

||f_ℓ(x) - f₀(x)|| = 0

ℓ→∞

(сходимость в пространстве функций).

2. Слабая сходимость функцийf_ℓ(x) к f₀(x) требует, чтобы

lim

((f_ℓ(x), φ(x)) - (f₀(x), φ(x)) = 0

∀φ ∈ L₂

ℓ→∞

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

должно выполняться для всех функций φ(x) ∈ L₂.

Используя неравенство Коши—Шварца, легко показать, что сильная схо-

димость влечет за собой слабую⁵. В самом деле,

((f_ℓ(x) - f₀(x)), φ(x))² ≤ ||f_ℓ(x) - f₀(x)||²||φ(x)||²,

т.е. сильная сходимость в правой части неравенства влечет слабую в левой

части.

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

рассматриваемых в этой статье (принадлежащие к гильбертовому пространству с воспро-

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

Существующая статистическая теория обучения посвящена решению

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

сильную сходимость аппроксимирующих функций f_ℓ(x), построенных на ос-

новании данных

(x_i, y₁), . . . , (x_ℓ, y_ℓ)

и искомой функции f₀(x).

Решение Первой задачи обучения основывается на механизмах слабой схо-

димости. Допустим, дано множество из m функций φ₁(x), . . . , φ_m(x) (φ_i ∈ L₂)

(называем их предикатами). Идея решения первой задачи выбора состоит в

выборе подмножества функций f(x, α), α ∈ Λ, для которых выполнено равен-

ство

(5.1)

(f(x, α), φ_s(x)) = u_s

s = 1,...,m,

где

(5.2)

u_s = (f₀(x),φ_s

(x)), s = 1, . . . , m.

Назовем подмножество функций {f(x)} из L₂, которое удовлетворяет

m интегральным соотношениям (5.1), допустимым подмножеством⁶. Заме-

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

цию f₀(x).

Допустим, что дано наряду с предикатами φ_s(x), s = 1, . . . , m, значение u_s,

s = 1,...,m, определенное в (5.2). Тогда задача выбора допустимого подмно-

жества функций может быть сформулирована следующим образом:

для заданных пар

(φ₁(x), u₁), . . . , (φ_m(x), u_m)

найти в множестве функций f(x, α), α ∈ Λ, подмножество, удовлетворяю-

щее (5.1).

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

значение u_s и найти подмножество функций f(x, α), α ∈ Λ, удовлетворяю-

щих (5.1).

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

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

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

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

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

только два вида сходимости, то существуют только два основных механизма

обучения.

⁶ Так как слабая сходимость определена всеми функциями φ(x) ∈ L2, то любое подмно-

жество φi(x), i = 1, . . . , m, определяет допустимое подмножество.

6. Инструменталистские и реалистические модели обучения

6.1. Феноменологическая модель обучения

Рассмотрим следующую схему обучения: допустим, что неизвестный гене-

ратор G случайно и независимо генерирует векторы x ∈ X. Предположим,

что некоторый объект O возвращает на каждом входе x_i бинарный выход

y_i ⊂{1,0}, используя неизвестную условную функцию распределения P(y|x).

Это означает, что объект O использует функцию 0 ≤ P (y = 1|x) ≤ 1 и ме-

ханизм, который определяет классификацию y_i вектора x_i подбрасыванием

монетки: с вероятностью P (y = 1|x_i) возвращается значение y_i = 1 и с веро-

ятностью 1 - P (y = 1|x_i) возвращается y_i = 0.

Пары (x_∗, y_∗) (классификация y_∗ входного вектора x_∗) наблюдаются обу-

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

жества функций f(x, α), α ∈ Λ. Требуется по наблюдениям ℓ пар

(x₁, y₁), . . . , (x_ℓ, y_ℓ)

найти индикаторную функцию y = θ(f(x, α_ℓ)), которая минимизирует ма-

тематическое ожидание числа несовпадающих классификаций, задаваемых

функцией y = θ(f(x, α_ℓ)) и правилом P (y|x).

Существуют две различные философские позиции для постановки задачи

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

1. Позиция философского инструментализма, которая утверждает, что це-

лью исследования является имитация работы объекта O (чтобы предска-

зать выход y объекта O на любом векторе x, сгенерированном G), т.е. най-

ти наилучшую функцию, прогнозирующую y = θ(f(x, α_ℓ)) в допустимом

подмножестве f(x,α), α ∈ Λ;

2. Позиция философского реализма, которая утверждает, что целью исследо-

вания является оценка условной функции распределения P (y = 1|x), ко-

торая использует объект O. Используя аппроксимацию P (y = 1|x), может

быть определено классификационное правило.

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

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

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

низмов вселенной.

1. Модель, основанная на подходе инструментализма. С позиции фило-

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

классификации (обучения) требует нахождения функции θ(f(x, α₀)), мини-

мизирующей функционал

∫

R_inst(α) = (y - θ(f(x,α)))²dP(x,y)

на множестве допустимых индикаторных функций θ(f(x, α)), α ∈ Λ.

2. Модель, основанная на подходе реализма. С позиции философского реа-

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

чающих данных для того, чтобы оценить на множестве допустимых действи-

тельных функций 0 ≤ f(x, α) ≤ 1, α ∈ Λ, условную функцию распределения

f (x, α₀) = P (y = 1|x). Используя соответствующую оценку P_ℓ(y = 1|x), мож-

но получить классификационное правило

(6.1)

r(α_ℓ) = θ(P_ℓ

(y = 1|x) - 0,5).

В [3], обосновывая постановку задачи обучения, которая отражает пози-

цию инструментализма, автором сформулирован императив: “Решая интере-

сующую вас задачу, не решайте более общую задачу как промежуточную.

Решайте интересующую вас задачу, а не более сложную”. В настоящей статье

автор отказывается от этого императива и будет рассматривать постановку

задачи обучения с реалистической точки зрения оценивания условной функ-

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

классификационного правила (6.1).

Такой подход позволит включить в обучение оба механизма сходимости,

существующие в гильбертовом пространстве: механизм сильной и слабой схо-

димости (см. соответствующий раздел далее).

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

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

ности P (y = 1|x) и получения правила классификации (6.1). Обобщение на

p-классовую классификацию y ∈ {0, . . . , (p - 1)} основано на p-оценках услов-

ных функций вероятности P (y = t|x), t = 0, . . . , (p - 1). Используя эти функ-

ции, можно получить правило классификации

y = argmax(P(y = 0|x),...,P(y = (p - 1)|x))

(специальные детали для мультиклассовой классификации даны далее).

7. Выбор допустимого подмножества функций

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

Далее для решения двухклассовой задачи классификации оцениваем

условную функцию вероятности P (y|x), где y ⊂ {0, 1}. Для этого необходимо

найти функцию f(x, α₀) = P (y = 1|x).

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

P_v(y = 1|x) -→_v→∞ P(y = 1|x)

означает равенство

∫

lim

φ(x)P_v(y = 1|x)dP (x) = φ(x)P (y = 1|x)dP (x)

∀φ(x) ∈ L₂

v→∞

(для всех функций φ(x) из L₂). Для условных функций вероятности это ра-

венство эквивалентно равенству

∫

(7.1)

lim

φ(x)P_ℓ(y = 1|x)dP (x) = φ(x)dP (y = 1, x)

∀φ(x) ∈ L₂.

ℓ→∞

Ослабим требования к слабой сходимости. Пусть решение (7.1) принадле-

жит множеству функций f(x, α), α ∈ Λ, которые удовлетворяют конечному

числу равенств m (как в (7.1))

∫

(7.2)

φ_s(x)P_ℓ(y = 1|x)dP(x) = φ_s

(x)dP (y = 1, x), s = 1, . . . , m,

заданных с помощью предикат φ_s(x), s = 1, . . . , m. Заметим, что так как бес-

конечное число предикатов заменено конечным, то решение (7.2) не един-

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

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

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

(x₁, y₁), . . . , (x_ℓ, y_ℓ), x ∈ X, y ⊂ {1, 0}.

Тогда согласно закону больших чисел справедливо следующее приближение

равенства (7.2) для оценки условных функций вероятности P_ℓ(y = 1|x):

∑

(7.3)

φ_s(x_i)P_ℓ(y = 1|x_i) ≈

y_iφ_s(x_i

s = 1,...,m.

ℓ

i=1

Определения:

1. Говорим, что функция P_∗(y = 1|x) принадлежит подмножеству допусти-

мых функций, если для данных предикатов φ_s(x), s = 1,... ,m, то она удо-

влетворяет (7.3).

2. Называем равенства (7.3) статистическими инвариантами. Правую

часть равенства (7.3) называем эмпирическими данными о предикате φ_s и

левую часть (7.3) — теоретическими данными об этом предикате.

3. Называем метод оценки правила классификации (6.1), использующий

условную функцию вероятности, которая удовлетворяет (7.3), обучением,

использующим статистические инварианты (или LUSI).

Равенство (7.3) требует, чтобы данные, полученные для теоретической мо-

дели условной вероятности, подтверждались эмпирическими данными (по-

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

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

Для полного решения задачи обучения (которое включает в себя две за-

дачи выбора: выбор допустимого подмножества функций и выбор из этого

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

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

предикаты.

2. Найти требуемую условную функцию вероятности в допустимом подмно-

жестве.

3. Построить правило (6.1), используя оцененную условную функцию веро-

ятности.

Замечания о механизме слабой сходимости.

Замечание 1. Так как слабая сходимости требует существования ра-

венства (7.1) для всех функций φ(x) ∈ L₂, можно выбрать произвольные m

функций φ_s(x) из L₂ в качестве предикатов.

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

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

риантов.

Замечание 3. Хорошая аппроксимация функции принадлежит множе-

ству функций, удовлетворяющих инвариантам (так как эмпирические данные

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

условной функции вероятности).

Замечание 4. Как упоминалось ранее, в классической модели любая но-

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

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

множество предикатов) с добавлением одного предиката можно обеспечить

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

ций из подмножества удовлетворяют инварианту с этим предикатом).

Замечание 5. Выбор “хороших” новых предикатов (которые отсека-

ют большое количество функций, нарушающих инвариант соответствующего

предиката) — это творческая часть задачи, которая частично обсуждается в

разделе 8.

7.2. Пример логики вывода, основанной на слабой сходимости

Существует так называемый “тест на утку” (Duck test), который иллю-

стрирует логику вывода, основанную на слабой сходимости. “Тест на утку”,

описанный в английской пословице, гласит: “Если что-то выглядит как ут-

ка, плавает как утка, крякает как утка, значит, это, возможно, утка”.

В рамках машинного обучения “тест на утку” может быть выражен так:

Во-первых, выберите подмножество допустимых правил, каждое из ко-

торых удовлетворяет свойству “утка”, для которого применимы два типа

предикатов:

1. Предикаты общего типа — “выглядит как утка”.

2. Предикаты специального типа — “плавает как утка”, “крякает как утка”.

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

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

Рассматриваем предикат “выглядит как класс y = 1” (класс “утки” ) как

предикат общего типа, потому что он выражает общие (математические)

свойства элементов обучающей выборки, которые принадлежат классу y = 1,

и не использует специальные знания о данной задаче классификации.

Называем предикаты “плавает как утка” и “крякает как утка” предиката-

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

⁷ Смысл “теста на утку” в том, что существуют такие хорошие предикаты, что любое

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

статочно трех предикатов. В предложенном методе будем выбирать требуемую аппрокси-

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

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

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

диката, то можно рассматривать предикаты вида: “прыгает как утка” или

“играет в шахматы как утка”. Однако такие предикаты не слишком полезны

в задаче классификации птиц.

Выбор предиката общего типа является в большей степени математиче-

ской частью задачи. Выбор предиката специального типа в большой степе-

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

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

учителя на процесс обучения. Это предмет взаимодействия Учитель — Сту-

дент.

7.3. Примеры предикатов общего типа

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

ражают идею “выглядит как утка”. В этом разделе рассмотрим три мате-

матические концепции, отражающие существующий статистический подход,

называемый методом моментов. Пусть

(x₁, y₁), . . . , (x_ℓ, y_ℓ), x ∈ X, y ⊂ {0, 1},

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

сгенерированной в соответствии с P (x, y) = P (y|x)P (x).

1. Предикат для статистического инварианта момента нулевого порядка.

Рассмотрим предикат φ(x) = 1. Используя эту функцию в (7.3), получаем

инвариант

∑

(7.4)

P_ℓ(y = 1|x_i) =

y_i,

i=1

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

вителей класса y = 1, посчитанное на основе оценки условной функции ве-

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

са y = 1 в обучающей выборке.

2. Предикаты для статистического инварианта момента первого порядка.

Рассмотрим вектор-функцию предикатов φ(x) = x, где x_i = (x1i,

...,xni )^T — вектор размерности n, x ∈ X. Используя эту функцию в (7.3),

получаем (покоординатно) n инвариантов

∑

(7.5)

x_iP(y = 1|x_i) =

y_ix_i, x_i = (x1i,... ,xⁿⁱ)^T.

i=1

Равенство (7.5) требует, чтобы центр масс векторов x из обучающей вы-

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

условной функции вероятности, и векторов x₁, . . . , x_ℓ совпадал с центром

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

вого класса.

3. Предикаты для статистического инварианта момента второго порядка.

Чтобы ввести 0,5n(n+1) инвариантов относительного статистического мо-

мента второго порядка, рассмотрим предикаты, определяемые ковариаци-

онной матрицей n × n

φ(x_i) = x_ix^Ti.

Соответствующие матричные инварианты имеют вид

∑

(7.6)

x_ixTiP_ℓ(y = 1|x_i) =

y_ix_ixTi.

i=1

Матричное равенство (7.6) рассматривается поэлементно. Каждый эле-

мент a_k,m матрицы n × n в левой части, полученный при использовании

оценки P_ℓ(y = 1|x), должен быть равен соответствующему элементу a^∗km

матрицы в правой части равенства (7.3), посчитанному при использова-

нии векторов первого класса из обучающей выборки. Из (7.6) может быть

получено 0,5n(n + 1) различных инвариантов⁸, которые определяют инва-

рианты для всех попарных координат входного вектора x.

Инварианты для нулевого (7.4), первого (7.5) и второго (7.6) порядков момен-

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

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

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

Предикат подмножества пространства. Пусть I_S (x) является индика-

тором, который определяет принадлежность вектора x подмножеству S

в каком-то подпространстве X^∗ пространства X (например, S(x) =

= {||x - a|| ≤ b}, где векторы x, a ∈ X и x^∗ = (x¹, . . . , x^k, 0, . . . , 0) определены

первыми k координатами вектора x). Рассмотрим предикат, определенный

индикаторной функцией

{

1, если x ∈ S(x),

I_S(x) =

иначе,

и соответствующий инвариант

∑

(7.7)

I_S(x_i)P_ℓ(y = 1|x_i) =

y_iI_S(x_i

i=1

Инвариант (7.7) требует, чтобы число векторов обучающей выборки первого

класса, которые принадлежат S(x), т.е. число, посчитанное при использова-

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

класса в S(x), непосредственно посчитанным по обучающей выборке.

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

⁸ Так как матрица симметрична, она содержит 0,5n(n + 1) различных элементов.

⁹ Напомним, что метод моментов является важным методом в задаче оценки плотности.

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

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

сующей задаче.

Предикаты специального типа (такие как “плавает как утка” и “крякает

как утка” в пословице, но не “прыгает как утка” или “играет в шахматы как

утка”, которые допустимы) основываются на знаниях о задаче.

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

шения задачи обучения. Они основаны на добавочных (специальных) знани-

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

ученика в процессе обучения.

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

вания цифр. При построении функции условной вероятности для распозна-

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

свойство “горизонтальной симметрии” (верхняя часть соответствующей циф-

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

рии. Можно ввести число, которое измеряет коэффициент горизонтальной

симметрии φ(x), и использовать его в качестве предиката для построения

инвариантов специального типа.

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

x^∗ является размытой версией изображения x, определенного на (k × p)-

пространстве пикселей X. Каждое (размытое) изображение цифры 3 может

быть описано вектором N = ((c1,1, . . . , c1,p), . . . , (ck,1, . . . , c_k,p)) размерности kp

(конкатенация первой строки пикселей со второй и т.д.). Для того чтобы

ввести коэффициент симметрии, наряду с вектором N, рассмотрим вектор

N^∗ = ((ck1 ,... ,c_k,p),... ,(c1,1,... ,c1,p)) размерности k × p (конкатенация по-

следней строки пикселей с предыдущей и т.д.).

В качестве коэффициента симметрии цифры x рассмотрим значение ска-

лярного произведения векторов N и N^∗ или φ_sim(x) = (N, N^∗).

Аналогичным образом может быть введена мера вертикальной симметрии.

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

части пространства пикселей (используя среднее значение пикселей в данной

части пространства).

8. Оценка функции условной вероятности

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

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

методов.

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

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

функция распределения P (x) случайной величины x.

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

даны P (x) описание эксперимента со случайной величиной x, нужно найти

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

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

но наблюдение результатов ℓ случайных (независимых, одинаково распреде-

ленных) испытаний x с P (x), найти функцию распределения P_ℓ(x) (или неко-

торые ее характеристики, как, скажем, первый момент).

Этот раздел посвящен формализации задачи оценки условной функции

распределения P (y = 1|x) на основании наблюдений

(x₁, y₁), . . . , (x_ℓ, y_ℓ), x ∈ R, y ∈ {0, 1, },

сгенерированных случайно и независимо в соответствии с P (y, x) =

= P(y|x)P(x): рассматриваем задачу оценки условной функции распределе-

ния как задачу решения интегрального уравнения Фредгольма¹⁰

∫

(8.1)

θ(x - x^′)P (y = 1|x^′)dP (x^′

) = P(y = 1,x),

определенного с помощью ядра θ(x - x^′). Необходимо решить интегральное

уравнение (8.1) (относительно неизвестной функции P (y = 1|x)), если функ-

ции распределения P (x) и P (y = 1, x) неизвестны, но дана выборка (x_i, y_i).

Заметим, что решение интегрального уравнения Фредгольма составляет

плохо обусловленную задачу. Более того, в рассматриваемом случае — плохо

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

равенства P (y = 1, x) должна быть определена приближенно, но и оператор

интегрального уравнения (функция P (x^′) в левой части (8.1)) должен быть

оценен по данным, поэтому он также определен приближенно.

9. Оценка функции распределения

Оценка функции распределения является основной задачей статистики.

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

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

истинной.

9.1. Эмпирическая функция распределения

и теорема Гливенко-Кантелли

Для оценки функции распределения P (x) по наблюдениям x₁, . . . , x_ℓ необ-

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

следующую форму для оценки функции распределения

∑

(9.1)

P_ℓ(x) =

θ(x - x_i

ℓ

i=1

¹⁰ Уравнение (8.1) эквивалентно

∫

P(y = 1|t)dP(t) = P(y = 1, x),

-∞

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

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

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

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

статистике¹¹.

Теорема 4. Эмпирическая функция распределения P_ℓ(z) сходится к ре-

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

sup|Pℓ(z) - P (z)| -→Pℓ→∞= 0.

В 1933 г. А.Н. Колмогоров нашел асимптотически точную скорость сходи-

мости для случая z ∈ R¹. Он показал, что справедливо соотношение

[

]

√

∑

P lim

ℓsup|P_ℓ(z) - P(z)| > ε

(-1)k-1 exp -2ε²k²

∀ε.

ℓ

k=1

Позже (в 1956-1990 гг.), Дворецкий-Кифер-Вольфовиц-Массарт нашли

точную неасимптотическую оценку, в которой правая часть в точности сов-

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

[

]

P sup|P_ℓ(x) - P(x)| > ε

≤ 2exp-2ε²ℓ

∀ε.

Обобщение оценки на n-мерный случай x = (x¹, . . . , xⁿ) ∈ Rⁿ, где

∑

∏

P_ℓ(x) =

θ(x^k - x^ki),

ℓ

i=1 k=1

было получено в 1970 г. с использованием VC теории:

[

]

{

(

) }

n ln ℓ

P sup|Pℓ(z) - P (z)| > ε

≤ 2exp

- ε² -

ℓ

∀ε.

ℓ

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

вый индуктивный прием: будем замещать функцию распределения ее эмпи-

рической оценкой (9.1).

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

ную функцию распределения, заменим в (8.1) неизвестные функции распре-

деления P (x) и P (y = 1, x)¹² выражениями:

∑

P_ℓ(x) =

θ(x - x_i), P_ℓ(y = 1, x) =

y_jθ(x - x_j).

ℓ

i=1

j=1

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

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

главным индуктивным шагом в статистике.

¹² Идея такой замены отражает стандартный индуктивный шаг в статистическом выво-

де.

Получим, что

∑

(9.2)

θ(x - x_i)P (y = 1|x_i) ≈

y_jθ(x - x_i

ℓ

i=1

j=1

Цель заключается в решении уравнения (9.2) на множестве функций

P (y = 1|x) ∈ {f(x, α), α ∈ Λ}, которые удовлетворяют инвариантам

∑

φ_s(x_i)P(y = 1|x_i) ≈

y_iφ_s(x_i), s = 1,... ,m,

ℓ

i=1

где φ_s(x), s = 1, . . . , m, - выбранные предикаты.

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

теории обучения.

10. Оценка функции условной вероятности

является плохо обусловленной задачей

Проблема решения операторного уравнения

(10.1)

Af = F,

которое отражает функции {f} в {F }, принадлежит к так называемым плохо

обусловленным задачам, т.е. если решение уравнения существует, единствен-

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

ния (10.1) (||F_δ - F || ≤ δ), которые могут привести к большим возмущениям

решения (||f_δ - f_δ|| ≥ C). Другими словами, обратное отображение (которое

отображает {F } в {f} ) не непрерывно.

В рассматриваемом случае имеется плохо обусловленная задача (8.1), где

не только правая часть уравнения P (y = 1, x) оценивается по данным и, зна-

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

дан приближенно (функция P (x^′) в левой части (8.1) и также оценивается по

данным.

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

ризации, разработанные для решения плохо обусловленных задач [4].

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

Основная идея решения плохо обусловленных задач связана с леммой об

обратном операторе. Допустим, что существует единственное решение f₀ ∈

∈ {f} операторного уравнения

Af = F, f ∈ {f},

где A - непрерывный линейный оператор, отображающий функции f ∈ {f} в

функции F ∈ {F }. Пусть A-1 является обратным оператором к A, задающим

отображение из {F } в {f}

A-1F = f.

Справедлива следующая лемма.

Лемма (об обратном операторе). Оператор A-1, обратный к непрерыв-

ному оператору A, определенному на множестве {f}, непрерывен, если это

множество компактно.

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

тегрального уравнения (заданного непрерывным оператором A), необходимо

выбрать некоторое компактное подмножество функций {f^∗}, которое вклю-

чает искомое решение, и затем решить уравнение в этом подмножестве.

При решении плохо обусловленных задач обычно используется следующая

форма задания компактных множеств:

(10.2)

f ∈ {W(f) ≤ C},

где W (f) — положительная выпуклая функция (выпуклость требуется из

вычислительных соображений), C константа.

Пусть решение принадлежит множеству (10.2) при некоторой фиксирован-

ной константе C. В этом случае для решения операторного уравнения (10.1)

необходимо минимизировать функционал

R(f) = ρ²(Af, F )

при ограничениях (10.2). Подобная форма решения плохо обусловленных за-

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

функционала W (f) квазирешение — единственно.

С помощью множителей Лагранжа проблему условной минимизации мож-

но записать как проблему безусловной минимизации функционала

(10.3)

R(f) = ρ(Af, F ) + γW (f).

Такая форма решения называется регуляризацией. Параметр γ > 0 в ре-

гуляризованной проблеме (10.3) определяется константой C в (10.2).

Главные теоремы из области плохо обусловленных задач утверждают, что

если решение принадлежит компакту (10.2) с некоторой константой C (или γ

в эквивалентной форме (10.3)), то существует такой закон выбора парамет-

ра C_δ (или γ_δ) в зависимости от точности представления правой части опе-

раторного уравнения (10.1), что соответствующие решения уравнения (10.1)

сходятся к искомому решению при δ → 0 [4]. Кроме того, показано, что при

некоторых общих условиях описанные решения плохо обусловленных задач

с приближенно заданным оператором A_ℓ и приближенно заданной правой

частью также сходятся к искомому решению [8].

10.2. Оценка функции условного распределения

Для решения плохо обусловленной задачи оценки условной функции рас-

пределения при использовании регуляризованного функционала (10.3) (или

метода квазирешений) необходимо определить три элемента:

1. Квадрат расстояния ρ²(Af, F ). В настоящей статье используем расстояние

L₂(μ)

∫

ρ(Af, F ) = (Af(x) - F (x))²dμ(x),

где μ(x) — некоторая заданная вероятностная мера (например μ(x) =

= P(x)).

2. Множество функций {f}, в котором ищется решение, автор использует

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

щим ядром K(x, x^′), которое будет определено далее.

3. Регуляризирующий функционал W (f): автор использует квадрат нормы

функции W (f) = (f, f).

11. Оценки с использованием V-матриц

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

ки функции условной вероятности в множестве f(x, α), α ∈ Λ, в виде

⎛

⎞

∫

∑

ρ(A_ℓf, F_ℓ) =

⎝¹

θ(x - x_i)f(x_i, α) -

y_jθ(x - x_j)^⎠ dμ(x),

ℓ

i=1

j=1

где μ(x) — заданная вероятностная мера.

В статье вместо меры μ(x) автор использует ее эмпирическую оценку

∑

μ_ℓ(x) =

θ(x - x^′t),

t=1

вычисленную на основании L элементов универсума (набора элементов, ко-

торый содержит ℓ элементов x_i обучающих данных и (L - ℓ) векторов, сгене-

рированных мерой μ(x) ≈ P (x))¹³. Получим

∑

(11.1)

ρ²(A_ℓf,F_ℓ) =

(f(x_i, α)f(x_j , α) - 2y_jf(x_i, α) + y_iy_j) V (x_i, x_j

i,j=1

где обозначено

∫

∑

∏

(11.2)

V (x_i, x_j) = θ(x - x_i)θ(x - x_j)dμ_ℓ(x) =

θ(x^kt - x^ki∨j

t=1 k=1

В (11.2) используется обозначение x^ki∨j = max{x^ki, x^kj}, где x^ki — k-я коор-

дината векторов x_i = (x1i, . . . , xⁿⁱ) из обучающей выборки. Векторы x_t обозна-

чают элементы из универсума. Чем больше число L векторов x_t, тем точнее

оценка матрицы V . Уравнение (11.1) можем переписать в виде

∑

(11.3)

ρ(A_ℓf, F_ℓ) =

(f(x_i, α) - y_i)(f(x_j , α) - y_j)V (x_i, x_j

i,j=1

¹³ Например, при распознавании цифр элементы универсума наряду с примерами напи-

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

Таким образом, расстояние (11.3) между двумя функциями, определяю-

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

δ_i = (y_i - f(x_i,α)) попарные положения наблюдаемых векторов относитель-

но векторов из универсума. Функционал (11.3) отличается от стандартного

функционала из метода наименьших квадратов

∑

ρ(A_ℓf, F_ℓ) =

(f(x_i, α) - y_i)².

i=1

Замечание 6. Для удобства вычислений рекомендуется вместо матри-

цы V использовать нормализованную матрицу V/||V ||, где ||V || — любая нор-

ма матрицы V .

12. Функции из гильбертова пространства с воспроизводящим ядром

Пусть K(x, x^′) — положительно определенная функция¹⁴. Говорят, что

функция f(x) принадлежит гильбертовому пространству с воспроизводящим

ядром K(x, x^′), если выполняется следующее воспроизводящее свойство:

(12.1)

(K(x, x^′), f(x^′

)) = f(x)

(в скалярном произведении (12.1) автор рассматривает K(x, x^′) как функ-

цию x^′ при фиксированном x). Легко видеть, что существует простая кон-

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

странство с воспроизводящим ядром K(x, x^′). Действительно, согласно тео-

реме Мерсера любая положительно определенная функция K(x, x^′) (ядро)

имеет представление

∑

K(x, x^′) =

λ_pψ_p(x)ψ_p(x^′),

i=1

где ψ₁(x), . . . , ψ_p(x), . . . — система ортонормированных функций и λ1 ≥

≥ λ₂ ... ≥ λ_p ... ≥ 0, причем λ_p сходится к нулю при p → ∞. Рассмотрим

гильбертово пространство функций вида

∑

(12.2)

f (x) =

c^pψ_p

(x)

p=1

со скалярным произведением

∑

cp1cp2

(12.3)

(f₁(x), f₂(x)) =

λ_p

p=1

∑

¹⁴ Положительно определенная функция удовлетворяет условию

αiαj K(xi, xj ) ≥ 0

i,j=1

для любого m, любых xi, . . . , xm и любых αi, i = 1, . . . , m.

где c₁ = (c¹,...,c

,...) и c₁ = (c¹²,...,cp2,...) — коэффициенты разложе-

ния (37) функций f₁(x) и f₂(x). Норма функции в этом пространстве равна

∑

(c^p)²

(12.4)

||f(x)||² =

λ_p

p=1

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

вимы разложением по ортонормированным базисным функциям ψ_p(x), ска-

лярное произведение определяется соотношением

∑

(f₁(x), f₂(x)) =

cp1cp2,

а норма —

∑

||f(x)||² =

(c^p)²

(т.е. имеют вид (12.3) и (12.4) при λ_p = 1).

12.1. Гильбертово пространство с воспроизводящим ядром

В статье при оценке условной вероятности автор использует в качестве

регуляризирующего функционала квадрат нормы ||f||² с параметром регу-

ляризации γ > 0 (см. 10.3)). Это эквивалентно поиску функций вида (12.2) с

коэффициентами разложения c^p, принадлежащих области

∑

(c^p)²

(12.5)

||f(x)||² =

≤ C,

λ_p

p=1

где константа C определяется константой регуляризации γ > 0 в (10.3) (и на-

оборот).

Поскольку λ_p в знаменателе в левой части (12.5) стремится к нулю при p,

стремящемся к бесконечности, неравенство (12.5) задает множество гладких

функций: коэффициенты в разложении (12.2) функции с ограниченной нор-

мой должны стремиться к нулю при p → ∞. Для любого фиксированного

C > 0 множество функций из гильбертова пространства с воспроизводящим

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

зоваться как регуляризирующий функционал W (f) = ||f||² в (10.3) при ре-

шении плохо обусловленных задач.

12.2. Теорема о представителе

Важную роль в теории и методах Reproducing Kernel Hilbert Space (RKHS)

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

Теорема 5. Функция f(x) из RKHS, которая минимизирует функцио-

нал

∑

R(f) = L(y_i - f(x_i)) + γ||f(x)||²,

i=1

наряду с разложением (12.2) представима в виде

∑

(12.6)

f (x, α_ℓ) =

α_iK(x_i

,x).

i=1

Квадрат нормы этой функции наряду с (12.4) представим в виде

∑

(12.7)

||f(x, α_ℓ)||² =

α_iα_jK(x_ix_j

i,j=1

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

ром K(x, x^′) функция, минимизирующая R(f), наряду с разложением по бес-

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

нечному числу функций, задаваемых ядром K(x, x^′). Это делает функции

из RKHS с ядром K(x, x^′) важным инструментом аппроксимации функций

(в особенности функций высокой размерности).

12.3. Примеры ядер: ядра Мелера и RBF

В теории аппроксимации важную роль играют полиномы Эрмита и функ-

ции Эрмита. Полиномы Эрмита H₁(x), . . . , H_k(x), . . ., определяют ортого-

нальные с весовой функцией exp{-x²} полиномы, т.е.

∞

∫

P_s(x)P_n(x)e-x2 dx = 2ⁿn!√πδn,s,

−∞

где δ_n,s — символ Кронекера (δ_s,n = 0, если s = n, и δ_s,n = 1, если s = n).

Ортонормированные функции

(

e_n(x) =

2nn!√π)-1/2 Hn(x)e-x2

называются функциями Эрмита. Показано, что

|e_n(x)| < 0,82.

Функции Эрмита образуют ортонормированный базис в L₂. Таким обра-

зом, любая функция из L₂ однозначно представима в виде разложения по

функциям Эрмита.

В 1866 г. Мелер показал, что для любого 0 < ε < 1 справедливо соотноше-

ние

{

}

∑

ε²(x - x^′)² + 2(ε - ε²)xx^′

K_M (x,x^′) =

ε^ke_k(x)e_k(x^′) =

√

exp

1-ε²

k=0

Правая часть этого равенства называется ядром Мелера. Нормализованное

ядро Мелера называется RBF (радиальные базисные функции) ядром

K_M (x,x^′)

K(x, x^′) =

√

= exp{-δ(x - x^′)²},

K_M (x,x)K_M (x^′x^′)

где параметр δ > 0 задается величиной ε:

δ=

1-ε²

13. Полное решение задачи классификации

13.1. Решение Второй задачи выбора

Получим полное решение задачи распознавания образов для двухклассо-

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

ства с воспроизводящим ядром K(x, x^′). Решим уравнение (9.2) на множестве

функций (12.6), принадлежащих RKHS с ядром K(x, x^′) как плохо обуслов-

ленную задачу, используя регуляризационный функционал (12.7).

Согласно теореме о представителе решение P_ℓ(y = 1|x) = f_ℓ(x) имеет вид

∑

f_ℓ(x) =

α_iK(x_i,x)

i=1

и квадрат нормы ||f_ℓ(x)|| равен

∑

||f_ℓ(x)||² =

α_iα_jK(x_i,x_j).

i,j=1

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

значения. Пусть (x₁, y₁), . . . , (x_ℓ, y_ℓ) — элементы обучающей выборки. Рас-

сматриваем вектор Y = (y₁, . . . , y_ℓ)^T, определенный элементами обучающей

выборки. Для двухклассовой задачи Y является бинарным вектором. Рас-

сматриваем (ℓ×ℓ)-матрицу K = K(x_i, x_j ), определяемую элементами обучаю-

щей выборки. Рассмотрим вектор-функцию K(x) = (K(x₁, x), . . . , K(x_ℓ, x))^T

размерности ℓ и вектор коэффициентов разложения A = (α₁, . . . , α_ℓ)^T раз-

мерности ℓ.

В этих обозначениях по теореме о представителе функция f_ℓ(x) имеет вид

f_ℓ(x) = A^TK(x).

Введем (ℓ×ℓ)-матрицу V = ||V (x_i, x_j )|| с элементами V (x_i, x_j). В данных обо-

значениях для решения второй задачи выбора необходимо минимизировать

регуляризованный функционал

R(A) = (KA - Y )^TV (KA - Y ) + γA^TKA.

Однако автор будет искать решение задачи в более общем множестве

функций, рассматривая множество функций из RKHS, которые имеют сво-

бодный член

f_ℓ(x) = A^TK(x) + c.

Для нахождения оценки минимизируем функционал

R(A, c) = (KA + c1_ℓ - Y )^TV (KA + c1_ℓ - Y ) + γA^TKA,

где используем ℓ-мерный вектор 1_ℓ = (1, . . . , 1)^T. Необходимыми условиями

минимума R(A, c) являются

⎧

⎪

∂R(A,c)

⎨

=⇒ V KA + cV 1_ℓ - V Y + γ_ℓA = 0,

∂A

(13.1)

⎪

R(A, c)

⎩ ∂

=⇒ 1TℓV KA + c1TℓV 1_ℓ - 1TℓV Y = 0.

∂c

Из первого равенства в (13.1) получим

(V K + γI)A = V Y - cV 1_ℓ

или

(13.2)

A = (V K + γI)-1V (Y - c1_ℓ

Используя обозначения

(13.3)

B = (V K + γI)-1

из (13.2) получим, что требуемый вектор A имеет вид

(13.4)

A = B(Y - c1_ℓ

Из второго равенства в (13.1) и (13.4) получим уравнение для определения c:

1T_ℓV KB(Y - c1_ℓ) + c1TℓV 1_ℓ - 1TℓV Y = 0,

[

]

[

]

1T_ℓV KB1_ℓ - 1TℓV 1_ℓ

·c =

1TV KBY - 1TℓV Y

Значением свободного члена c является

[

]

[

]

1T_ℓV KB1_ℓ - 1TℓV Y

1T_ℓ

V K(V K + γI)-1 - I

1T_ℓSV Y

(13.5)

[

] =

1T_ℓV KB1_ℓ - 1TℓV 1_ℓ

1T_ℓ [V K(V K + γI)-1 - I] V 1_ℓ

1T_ℓSV 1_ℓ

где введено обозначение

S = V K(V K + γI)-1 - I.

Подставляя c в (13.4), получим требуемые параметры A.

13.2. Калибровка n функций условных вероятностей

Рассмотрим задачу n-классовой классификации, в которой величина y

принимает одно из n значений y ⊂ {1, . . . , n}. Определим за вектор Y_p бинар-

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

выборки y_s = p, и равна нулю, если y_s = p. Пусть для любого фиксированно-

го p функция

(13.6)

f (x; A_p, c_p) = ATpK(x) + c_p

p = 1,

определяет условную вероятность P (y = p|x) класса y = p при заданном x.

Допустим, что для всех p оценок пар (A_p, c_p) использовалось одно и то же

ядро K, минимизируя функционалы

R(A_p, c_p) = (KA_p + c_p1_ℓ - Y_p)^TV (KA_p + c_p1_ℓ - Y_p) + γATpKA_p,

(13.7)

p = 1,...,n,

для n различных Y_p с одним и тем же параметром регуляризации γ > 0. Легко

∑_n

убедиться (используя (13.5)), что поскольку

Y_s = 1_ℓ, имеем, что

s=1

∑

1T_ℓSV Y_p

(13.8)

c_k =

= 1.

1T_ℓSV 1_ℓ

p=1

Используя (13.4), получаем

∑

∑(

)

∑

(

)

(13.9)

A_p =

(V K + γI)-1V Y_p

- c_p

(V K + γI)-1V 1_ℓ

V1_ℓ =0_ℓ,

p=1

где 0_ℓ обозначает ℓ-мерный вектор, состоящий из нулей. Из (13.8) и (13.9)

получаем, что

∑

(13.10)

P_ℓ(y = p|x) =

c_p

p=1

для всех x ∈ X.

Свойство (13.10) n оценок называется совместной калибровкой n условных

плотностей.

13.3. Одновременное решение обеих проблем выбора

Чтобы найти функцию условной вероятности P (y = p|x), которая является

решением обеих проблем выбора, минимизируем (13.7) при m ограничениях

(инвариантах)

ΦTsKA_p + c_pΦTs1_ℓ = ΦTsY_p, s = 1,... ,m,

где Φ_s — ℓ-мерный вектор, сконструированный с использованием преди-

кат φ_s(x) и элементов x_i обучающей выборки:

Φ_s = (φ_s(x₁),... ,φ_s(x_ℓ))^T, s = 1,... ,m.

Метод условной минимизации. В [9] для случая ℓ > m найдено следующее

решение этой проблемы: вектор параметров A_p функции (13.6) имеет вид

∑

A_p = B(Y_p - c_p1_ℓ) - μ_sA_s,

s=1

где наравне с обозначением (13.3) использовано обозначение

A_s = (V K + γI)-1Φ_s, s = 1,... ,n.

Коэффициенты μ_s и c_p, которые определяют вектор A_p и свободный

член c_p в (13.6), являются решениями следующих линейных уравнений:

[

]

∑

[

]

[

]

c_p

1T_ℓV KB1_ℓ - 1TℓV 1_ℓ

+ μ_s

1T_ℓV KA_s - 1TℓΦ_s

1T_ℓV KBY_p - 1TℓV Y_p

s=1

[

]

∑

[

]

c_p

Φ_kKB1_ℓ - ΦTk1_ℓ

+ μ_sATsKΦ_k =

ΦTsKBYTp - YTpΦ_k

k = 1,...,m.

s=1

Метод безусловной минимизации. Далее найдем приближенное решение

рассматриваемой проблемы (которое включает случай ℓ < m) путем мини-

мизации функционала

L(A, c) = (KA_p + c_p1_ℓ - Y_p)^TV (KA + c1_ℓ - Y_p) -

- 2(KA_p + c_p1_ℓ - Y_p)^TV Y_p + γATp KA_p +

(13.11)

∑

μ_s

+τ

(ΦTsKA_p + c_pΦTs1_ℓ - ΦTsY_p)²,

s=1

где τ ≥ 0 — дополнительный параметр функционала и

(

μ_s =

ΦTsΦ_s

)-1 .

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

∂L(A_p,c_p,)

=⇒ V (KA_p + c_p1_ℓ - Y_p) + γA_p + τM(KA_p + c1_ℓ - Y_p) = 0,

∂A_p

(13.12)

∂L(A_p,c_p,)

=⇒ 1TℓV (KA_p + c_p1_ℓ - Y_p) + τ1TℓM(KA_p + c_p1_ℓ - Y_p) = 0.

∂c_p

В (13.12) использовано матричное обозначение

∑

^∑Φ_sΦTs

(13.13)

M =

μ_sΦ_sΦTs =

ΦTsΦ_s

s=1

Замечание 7. В случае когда предикаты φ_s(x) таковы, что d_s = ΦTs 1_ℓ = 0

(это справедливо, если рассматривать в качестве предикат выражение

φ^′s(x) = φ_s(x) - d_s), элементы M_i,j матрицы M задают “корреляцию” между

векторами x_i и x_j относительно предикат φ′1(x), . . . , φ^′m(x).

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

W_τ = V + τM.

Используя обозначение из первого уравнения (13.12), получим

(W_τ K + γI)A_p = W_τ Y_p - c_pW_τ 1_ℓ

и выражение

(13.14)

A_p = (W_τ K + γI)-1W_τ (Y_p - c_p1_ℓ

Введя векторы

A^pb = (W_τ K + γI)-1W_τ Y_p

A^′c = (W_τ K + γI)-1W_τ 1_ℓ,

из (13.14) найдем требуемый вектор A_p в виде

(13.15)

A_p = A^pb - c_pA^′c.

Подставляя выражение (13.15) во второе уравнение (13.12), найдем свобод-

ный член c_p

[

]

[

]

1TWτ KAbp - 1TℓWτ Yp

1T_ℓ

W_τ K(W_τ K + γI)-1 - I

W_τ Y_p

(13.16)

c_p

= [ ℓ

] =

1T_ℓW_τ KA^′c - 1TℓW_τ 1_ℓ

1T_ℓ [W_τ K(W_τ K + γI)-1 - I] W_τ 1_ℓ

Подставляя c_p в (13.15), найдем вектор A_p. Параметр c_p и вектор A_p опре-

деляют выражение (13.6) для оценки функции условной вероятности.

13.4. Решение n-классовой проблемы классификации

При решении задачи классификации n классов оцениваем n функций

условных вероятностей P (y = p|x), p ⊂ {1, . . . , n}. Используя эти оценки,

сконструируем правило

r(x) = argmax{P_ℓ(y = 1|x), . . . , P_ℓ(y = n|x)}.

Допустим, что для оценки n функций условных вероятностей используем

одно и то же ядро K(x, x^′), один и тот же набор предикатов φ₁(x), . . . , φ_m(x) и

один и тот же параметр регуляризации γ. Тогда матрицы K и W_τ не зависят

от p (класс y = p, для которого оцениваем условную вероятность). В этом

случае поскольку

∑

Y_p = 1_ℓ,

p=1

то, используя (13.15) и (13.16), получим, что

∑

c_p = 1,

A_p = 0_ℓ,

p=1

т.е.

∑

P_ℓ(y = p|x) = 1

p=1

для всех x ∈ X. Другими словами, получаем n совместно калиброванных ре-

шений, которые решают обе проблемы выбора.

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

В настоящей статье рассмотрена общая модель проблемы обучения: найти

в множестве функций {f(x)} функцию f_ℓ(x), минимизирующую функционал

среднего риска

∫

R(f) = (y - f(x))²dP (x, y)

при неизвестной кумулятивной функции распределения P (x, y), но при за-

данной независимой выборке одинаково распределенных пар

(x₁, y₁), . . . , (x_ℓ, y_ℓ).

Показано, что для решения этой задачи необходимо в {f} минимизировать

целевой функционал

R_ℓ(f) = (Y - F(f))^TV(Y - f(F)),

где Y = (y₁, . . . , y_ℓ)^T, F (f) = (f(x₁, . . . , f(x_ℓ))^T и V — матрица, состоящая из

элементов V (x_i, x_j ). Используя m предикат φ₁(x), . . . , φ_m(x), можно извлечь

из данных дополнительную информацию. Для этого необходимо в {f} мини-

мизировать функционал (13.11) при ограничениях

ΦTkF(f) = ΦTkY, k = 1,... ,m.

Задачу условной минимизации в {f} можно переписать в виде задачи без-

условной минимизации, минимизируя в {f} функционал

∑

R_un(f) = (Y - F(f))^TV(Y - f(F)) +

(ΦTkF (f) - ΦTkY )²,

ΦTkΦ_t

k=1

который можно переписать в виде

R_un(f) = (Y - F(f))^T(V + τP)(Y - f(F)),

где матрица P равна:

∑

Φ_kΦTk

P =

ΦTkΦ_k

k=1

В статье получено решение для функций с ограниченной нормой, принад-

лежащих RKHS. Функции из RKHS с ядром K(x, x^′) допускают линейное

представление с вектором параметров A

f_ℓ(x) = A^TK(x),

при этом F (f) = KA, а норма функции ||f||² = A^TKA, где K — матрица с

элементами K(x_i, x_j). В статье для этого случая получено решение.

Для множества функций {f}, задаваемых нейронными сетями, минимиза-

ция функционала (13.13) методом стохастического градиентного спуска при-

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

дартную схему обратного распространения, вместо обратного распростране-

ния вектора ошибок E = (e₁, . . . , e_ℓ)^T разностей e_i = y_i -z_i (значение целевой

переменной y_i из обучающей выборки (x_i, y_i) минус выход z_i последнего слоя

нейронной сети в ответ на входной вектор x_i) осуществляется обратное рас-

пространение модифицированного вектора (V + τP)E.

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

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

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

С. 264-279.

Vapnik V.N., Chervonenkis A.Ya. On Uniform Convergence of the Frequencies of

Events to Their Probabilities // Theory Probab. Apl. 1971. V. 16. No. 2. P. 264-280.

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

3. Vapnik V. The Nature of Statistical Learning Theory. Springer, 1995.

4. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука,

1979.

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

1979.

6. Devroy L., Geofry L., Lugosi G. A Probabilistic Theory of Pattern Recognition.

Springer, 1996.