машинное обучение. А. М. Миронов Московский Государственный Университет Механикоматематический факультет Кафедра математической теории интеллектуальных систем Введение Книга
 Скачать 1.05 Mb.
|
|
∙ если 𝑀 𝑥 < 1, то 𝑥 находится за пределами своего полупространства (такой вектор называется выбросом). Согласно соотношениям в (2.71) и (2.73), ∀ 𝑥 ∈ 𝑋 𝑆 ∙ либо ˆ 𝜆 𝑥 = 0, ˆ 𝜂 𝑥 = 𝑐, либо ˆ 𝜉 𝑥 = 1 − 𝑀 𝑥 , ∙ либо ˆ 𝜆 𝑥 = 𝑐, ˆ 𝜂 𝑥 = 0, либо ˆ 𝜉 𝑥 = 0, ∙ 𝑀 𝑥 + ˆ 𝜉 𝑥 − 1 ≥ 0. Поэтому ∙ если 𝑥 – периферийный, т.е. 𝑀 𝑥 > 1, то невозможно, чтобы было верно равенство ˆ 𝜉 𝑥 = 1 − 𝑀 𝑥 , поэтому для такого вектора ˆ 𝜆 𝑥 = 0, ˆ 𝜂 𝑥 = 𝑐, откуда следует, что ˆ 𝜉 𝑥 = 0, ∙ если 0 < ˆ 𝜆 𝑥 < 𝑐, то 0 < ˆ 𝜂 𝑥 < 𝑐, ˆ 𝜉 𝑥 = 0 и 𝑀 𝑥 = 1, т.е. 𝑥 опорный, ∙ если 𝑥 – выброс, т.е. 𝑀 𝑥 < 1, то – невозможно, чтобы было верно равенство ˆ 𝜆 𝑥 = 0, т.к. если бы оно было верно, то тогда было бы верно равенство ˆ 𝜉 𝑥 = 0, поэтому 𝑀 𝑥 − 1 ≥ 0, что противоречит неравенству 𝑀 𝑥 < 1, – невозможно, чтобы было верно неравенство 0 < ˆ 𝜆 𝑥 < 𝑐, т.к. в этом случае ˆ 𝜉 𝑥 = 0, что, как было установлено выше, неверно, т.е. остается единственная возможность: ˆ 𝜆 𝑥 = 𝑐, ˆ 𝜂 𝑥 = 0, и ˆ 𝜉 𝑥 > 0. Читателю предлагается самостоятельно исследовать вопрос: возмож- но ли, чтобы 𝑥 был опорный, но 𝜆 𝑥 = 0 или 𝑐 (если невозможно, то доказать это, а если возможно, то привести соответствующий пример). 2.6 Ядерный метод машинного обучения 2.6.1 Спрямляющие пространства В некоторых случаях выборка 𝑆 линейно неразделима ∙ не по причинам зашумленности компонентов векторов в 𝑆, пред- ставляющих объекты, или ошибочной разметки, 51 ∙ а по причине наличия нетривиальных зависимостей между компо- нентами векторов в 𝑆, представляющих объекты. Например, рассмотрим выборку 𝑆 ⊆ R 2 × {−1, 1}, изображенную на картинке (в которой мы представляем вектора из R 2 точками плоскости) - 6 s s s s s s * * * * * * * * * * * где черные кружочки изображают объекты из 𝑆 + , а звездочки – объекты из 𝑆 − . Такая выборка принципиально линейно неразделима. В данном случае принадлежность вектора (𝑥 1 , 𝑥 2 ) ∈ R 2 к 𝑆 + или 𝑆 − лучше определять по его норме ||𝑥|| = √︀𝑥 2 1 + 𝑥 2 2 , т.е. искать 𝑎 𝑆 в виде 𝑎 𝑆 (𝑥) = 𝑠𝑖𝑔𝑛 (︁ ||𝑥|| − 𝑤 0 )︁ Поиск АФ, соответствующих таким выборкам 𝑆 ⊆ R 𝑛 × {−1, 1}, для которых невозможно построить АФ 𝑎 𝑆 в виде 𝑎 𝑆 (𝑥) = 𝑠𝑖𝑔𝑛 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ , (2.74) может делаться методом спрямляющих пространств, который заклю- чается в следующем: ∙ выбирается подходящее нелинейное отображение 𝜙 : R 𝑛 → R 𝑁 , (2.75) с таким расчетом, чтобы выборка 𝑆 𝜙 def = {(𝜙(𝑥), 𝑦 𝑥 ) | 𝑥 ∈ 𝑋 𝑆 } оказа- лась бы линейно разделимой, (R 𝑁 в (2.75) называется спрямляющим пространством) ∙ методом опорных векторов для 𝑆 𝜙 ищется АФ 𝑎 𝑆 𝜙 вида (2.74), и ∙ искомая АФ 𝑎 𝑆 определяется как композиция 𝑎 𝑆 𝜙 ∘ 𝜙. 52 Например, для описанного выше примера в качестве спрямляющего пространства можно взять R 2 , и 𝜙(𝑥 1 , 𝑥 2 ) def = (𝑥 2 1 , 𝑥 2 2 ). В других ситуациях рассматриваются функции 𝜙 : R 𝑛 → R 𝑁 вида 𝜙(𝑥 1 , . . . , 𝑥 𝑛 ) = (𝑥 1 , . . . , 𝑥 𝑛 , 𝑥 2 1 , . . . , 𝑥 2 𝑛 , . . . , 𝑥 𝑖 𝑥 𝑗 , . . .). Нетрудно доказать, что для любой выборки 𝑆 существует спрямляю- щее пространство – это м.б., например, пространство R 𝑁 , где 𝑁 – число элементов в 𝑆. Если выбрать в R 𝑁 ортонормированный базис, и опре- делить 𝜙 : R 𝑛 → R 𝑁 как инъективное отображение, сопоставляющее каждому элементу 𝑥 ∈ 𝑋 𝑆 некоторый вектор из этого базиса, то 𝑆 𝜙 бу- дет линейно разделима. Отметим важную особенность функции 𝑎 𝑆 𝜙 . Если 𝑆 𝜙 линейно разде- лима, то, как было показано выше, 𝑎 𝑆 𝜙 можно искать в виде 𝑎 𝑆 𝜙 (𝑥) = 𝑠𝑖𝑔𝑛(⟨𝜙(𝑥), ˆ 𝑤⟩ − ˆ 𝑤 0 ) = = 𝑠𝑖𝑔𝑛(⟨𝜙(𝑥), ∑︀ 𝑥 ′ ∈𝑋 𝑆 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 ′ 𝜙(𝑥 ′ )⟩ − ˆ 𝑤 0 ) = = 𝑠𝑖𝑔𝑛( ∑︀ 𝑥 ′ ∈𝑋 𝑆 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 ′ ⟨𝜙(𝑥), 𝜙(𝑥 ′ )⟩ − ˆ 𝑤 0 ), (2.76) где ˆ 𝜆 ищется как решение задачи минимизации выражения ∑︁ 𝑥,𝑥 ′ ∈𝑋 𝑆 ˆ 𝜆 𝑥 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 𝑦 𝑥 ′ ⟨𝜙(𝑥), 𝜙(𝑥 ′ )⟩ − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 (2.77) при условиях ∀ 𝑥 ∈ 𝑋 𝑆 ˆ 𝜆 𝑥 ≥ 0, ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 = 0. (2.78) Из (2.76) и (2.77) следует, что для построения 𝑎 𝑆 𝜙 не надо знать ∙ ни размерности спрямляющего пространства, ∙ ни векторов вида 𝜙(𝑥), где 𝑥 ∈ 𝑋 𝑆 , надо лишь знать скалярные произведения вида ⟨𝜙(𝑥), 𝜙(𝑥 ′ )⟩. Ядерный метод ML заключается в том, что построение АФ 𝑎 𝑆 де- лается методом, аналогичным описанному выше, но с заменой всех ска- лярных произведений ⟨𝜙(𝑥), 𝜙(𝑥 ′ )⟩ на выражения вида 𝐾(𝑥, 𝑥 ′ ), где 𝐾 – функция вида 𝐾 : R 𝑛 × R 𝑛 → R. Данная функция называется ядром. Она определяется для 𝑆 мето- дом подбора, и должна обладать следующими свойствами: 53 ∙ симметричность: ∀ 𝑥, 𝑥 ′ ∈ R 𝑛 𝐾(𝑥, 𝑥 ′ ) = 𝐾(𝑥 ′ , 𝑥), (2.79) ∙ положительная определенность: ∀ 𝑥 1 , . . . , 𝑥 𝑚 ∈ R 𝑛 , ∀ 𝛼 1 , . . . , 𝛼 𝑚 ∈ R 𝑚 ∑︁ 𝑖,𝑗=1 𝛼 𝑖 𝛼 𝑗 𝐾(𝑥 𝑖 , 𝑥 𝑗 ) ≥ 0. (2.80) Построение АФ 𝑎 𝑆 сводится к задаче минимизации выражения ∑︁ 𝑥,𝑥 ′ ∈𝑆 ˆ 𝜆 𝑥 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 𝑦 𝑥 ′ 𝐾(𝑥, 𝑥 ′ ) − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 , (2.81) при условиях (2.78). Искомая АФ 𝑎 𝑆 𝜙 определяется следующим образом: ∀ 𝑥 ∈ R 𝑛 𝑎 𝑆 𝜙 (𝑥) = 𝑠𝑖𝑔𝑛 (︁ ∑︁ 𝑥 ′ ∈𝑋 𝑆 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 ′ 𝐾(𝑥, 𝑥 ′ ) − ˆ 𝑤 0 )︁ , где ˆ 𝑤 0 def = ∑︀ 𝑥 ′ ∈𝑋 𝑆 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 ′ 𝐾(𝑥 ′′ , 𝑥 ′ ) − 𝑦 𝑥 ′′ , и 𝑥 ′′ – произвольный вектор из 𝑋 𝑆 , такой, что ˆ 𝜆 𝑥 ′′ ̸= 0. В общем случае ядро определяется как произвольная функция вида 𝐾 : 𝑋 × 𝑋 → R (2.82) (где 𝑋 – множество, элементами которого являются объекты), являю- щаяся симметричной и положительно определенной, т.е. верны аналоги соотношений (2.79) и (2.80), в которых аргументами 𝐾 являются элемен- ты множества 𝑋. Нетрудно доказать, что если 𝐾 – ядро вида (2.82), то ∙ ∀ 𝑥 ∈ 𝑋 𝐾(𝑥, 𝑥) ≥ 0, ∙ если ∀ 𝑥 ∈ 𝑋 𝐾(𝑥, 𝑥) = 0, то ∀ 𝑥, 𝑥 ′ ∈ 𝑋 𝐾(𝑥, 𝑥 ′ ) = 0, ∙ верен аналог неравенства Коши-Буняковского: ∀ 𝑥, 𝑥 ′ ∈ 𝑋 𝐾(𝑥, 𝑥 ′ ) ≤ √︀ 𝐾(𝑥, 𝑥)𝐾(𝑥 ′ , 𝑥 ′ ). 54 2.6.2 Примеры ядер 𝐾(𝑥, 𝑥 ′ ) может иметь, например, следующий вид: ∙ (𝑐⟨𝑥, 𝑥 ′ ⟩ + 𝑑) 𝑚 , где 𝑐, 𝑑 ∈ R ≥0 , 𝑚 ≥ 0 (полиномиальное ядро), (где R ≥0 – множество неотрицательных действительных чисел), ∙ 𝜎(𝑐⟨𝑥, 𝑥 ′ ⟩ + 𝑑), где 𝜎 – сигмоида (сигмоидное ядро), ∙ 𝑎 0 + ∑︀ 𝑛≥0 𝑎 𝑛 sin(𝑛𝑥) sin(𝑛𝑥 ′ )+ ∑︀ 𝑛≥0 𝑏 𝑛 cos(𝑛𝑥) cos(𝑛𝑥 ′ ), где ∑︀ 𝑛≥1 𝑎 2 𝑛 +𝑏 2 𝑛 < ∞ (ядро Фурье), ∙ exp(− ||𝑥−𝑥 ′ || 2 𝜎 2 ) (гауссово ядро), ∙ exp( ⟨𝑥,𝑥 ′ ⟩ 𝜎 2 ) (экспоненциальное ядро), ∙ 𝐾 1 (𝑥, 𝑥 ′ )𝐾 2 (𝑥, 𝑥 ′ ), где 𝐾 1 и 𝐾 2 – ядра, ∙ 𝛼 1 𝐾 1 (𝑥, 𝑥 ′ ) + 𝛼 2 𝐾 2 (𝑥, 𝑥 ′ ), где 𝐾 1 и 𝐾 2 – ядра, 𝛼 1 и 𝛼 2 ∈ R ≥0 , ∙ 𝐾(𝜙(𝑥), 𝜙(𝑥 ′ )), где 𝐾 – ядро, 𝜙 – произвольная функция. Приведем еще три примера ядра. 1. В качестве ядра 𝑋 × 𝑋 → R может выступать функция вида (𝑥, 𝑥 ′ ) ↦→ ⟨𝜙(𝑥), 𝜙(𝑥 ′ )⟩ где 𝜙 – произвольная функция вида 𝜙 : 𝑋 → ℋ, и ℋ – спрямляющее пространство, которое является гильберто- вым пространством, т.е. ∙ ℋ – линейное пространство со скалярным произведением, напомним, что скалярное произведение на ℋ – это функ- ция, сопоставляющая каждой паре (𝑥, 𝑦) ∈ ℋ×ℋ действитель- ное число ⟨𝑥, 𝑦⟩, и обладающая свойствами: ∀ 𝑥, 𝑥 ′ , 𝑦 ∈ ℋ – ∀ 𝛼, 𝛼 ′ ∈ R ⟨𝛼𝑥 + 𝛼 ′ 𝑥 ′ , 𝑦⟩ = 𝛼⟨𝑥, 𝑦⟩ + 𝛼 ′ ⟨𝑥 ′ , 𝑦⟩, – ⟨𝑥, 𝑦⟩ = ⟨𝑦, 𝑥⟩, – ⟨𝑥, 𝑥⟩ ≥ 0, причем ⟨𝑥, 𝑥⟩ = 0 ⇔ 𝑥 = ¯ 0 (нулевой вектор), 55 ∙ ℋ – полное метрическое пространство (где метрика 𝜌 на ℋ определяется нормой: 𝜌(𝑥, 𝑥 ′ ) = ||𝑥 − 𝑥 ′ ||, а норма определяется скалярным произведением: ||𝑥|| 2 = ⟨𝑥, 𝑥⟩), т.е. ∀ фундаменталь- ная последовательность имеет предел в ℋ, ∙ ℋ – сепарабельное пространство, т.е. ∃ счетное подмноже- ство 𝐻 ⊆ ℋ: ∀ 𝜀 > 0, ∀ ℎ ∈ ℋ ∃ ℎ ′ ∈ 𝐻 : 𝜌(ℎ, ℎ ′ ) < 𝜀. Примеры гильбертовых пространств: R 𝑛 или 𝑙 2 , где 𝑙 2 = {(𝑥 1 , 𝑥 2 , . . .) | ∑︁ 𝑖≥1 𝑥 2 𝑖 < ∞}, скалярное произведение в 𝑙 2 имеет вид ⟨(𝑥 1 , 𝑥 2 , . . .), (𝑦 1 , 𝑦 2 , . . .)⟩ = ∑︁ 𝑖≥1 𝑥 𝑖 𝑦 𝑖 2. Если 𝐾 – ядро вида 𝑋 × 𝑋 → R, где 𝑋 – произвольное множество, то функция 𝐾 ′ : 𝒫 𝑓 𝑖𝑛 (𝑋) × 𝒫 𝑓 𝑖𝑛 (𝑋) → R (где 𝒫 𝑓 𝑖𝑛 (𝑋) – множество всех конечных подмножеств 𝑋), опреде- ляемая следующим образом: ∀ 𝐴, 𝐵 ∈ 𝒫 𝑓 𝑖𝑛 (𝑋) 𝐾 ′ (𝐴, 𝐵) = ∑︁ 𝑎∈𝐴,𝑏∈𝐵 𝐾(𝑎, 𝑏) тоже является ядром. 3. Пусть заданы алфавит (т.е. множество символов) 𝐴, целое число 𝑛 ≥ 1, и действительное число 𝜆 ∈ (0, 1]. Обозначим записью 𝑛 * множество всех последовательностей ¯𝑖 = (𝑖 1 , . . . , 𝑖 𝑘 ), где 1 ≤ 𝑖 1 < . . . < 𝑖 𝑘 ≤ 𝑛. (2.83) Если последовательность ¯𝑖 ∈ 𝑛 * имеет вид (2.83), то ∙ запись 𝑙(¯𝑖) обозначает число 𝑖 𝑘 − 𝑖 1 + 1, и ∙ для каждой цепочки 𝑥 ∈ 𝐴 𝑛 , если 𝑥 имеет вид 𝑎 1 . . . 𝑎 𝑛 , то запись 𝑥[ ¯𝑖 ] обозначает цепочку 𝑎 𝑖 1 . . . 𝑎 𝑖 𝑘 Обозначим символом ℋ гильбертово пространство функций вида 𝑓 : 𝐴 𝑛 → R, 56 скалярное произведение на ℋ определяется следующим образом: ⟨𝑓, 𝑔⟩ = ∑︁ 𝑦∈𝐴 𝑛 𝑓 (𝑦)𝑔(𝑦). Ядро 𝐾 𝑛 : 𝐴 𝑛 × 𝐴 𝑛 → R определяется соотношением ∀ 𝑥, 𝑥 ′ ∈ 𝐴 𝑛 𝐾 𝑛 (𝑥, 𝑥 ′ ) = ⟨𝜙(𝑥), 𝜙(𝑥 ′ )⟩, где 𝜙 : 𝐴 𝑛 → ℋ, ∀ 𝑥 ∈ 𝐴 𝑛 𝜙(𝑥) : 𝐴 𝑛 → R, 𝑦 ↦→ ∑︀ ¯ 𝑖∈𝑛 * :𝑦=𝑥[ ¯ 𝑖 ] 𝜆 𝑙(¯ 𝑖) 𝐾 𝑛 используется в задачах анализа естественно-языковых текстов. 2.6.3 Каноническое гильбертово пространство, опре- деляемое ядром Каждому ядру 𝐾 : 𝑋 2 → R соответствует каноническое гильбертово пространство, определяемое ядром 𝐾. Данное пространство обознача- ется записью ℋ 𝐾 и обладает следующим свойством: ∃ 𝜙 : 𝑋 → ℋ 𝐾 : ∀ 𝑥, 𝑥 ′ ∈ 𝑋 𝐾(𝑥, 𝑥 ′ ) = ⟨𝜙(𝑥), 𝜙(𝑥 ′ )⟩. (2.84) ℋ 𝐾 определяется как подпространство линейного пространства R 𝑋 функций вида 𝑋 → R следующим образом: ∙ ∀ 𝑥 ∈ 𝑋 обозначим записью 𝐾 𝑥 функцию из R 𝑋 , которая отобра- жает каждый 𝑥 ′ ∈ 𝑋 в 𝐾(𝑥, 𝑥 ′ ), ∙ обозначим символом ℱ 𝑋 линейное подпространство в R 𝑋 , порож- денное всеми функциями вида 𝐾 𝑥 , т.е. ℱ 𝑋 = { ∑︁ 𝑖=1..𝑛 𝛼 𝑖 𝐾 𝑥 𝑖 | 𝑛 ≥ 1, ∀ 𝑖 = 1, . . . , 𝑛 𝛼 𝑖 ∈ R, 𝑥 𝑖 ∈ 𝑋}, ∙ определим скалярное произведение на ℱ 𝑋 : если 𝑓, 𝑔 из ℱ 𝑋 имеют вид 𝑓 = ∑︀ 𝑖=1..𝑛 𝛼 𝑖 𝐾 𝑥 𝑖 и 𝑔 = ∑︀ 𝑗=1..𝑚 𝛽 𝑗 𝐾 𝑥 ′ 𝑗 , то ⟨𝑓, 𝑔⟩ def = ∑︁ 𝑖=1..𝑛,𝑗=1..𝑚 𝛼 𝑖 𝛽 𝑗 𝐾(𝑥 𝑖 , 𝑥 ′ 𝑗 ) = ∑︁ 𝑖=1..𝑛 𝛼 𝑖 𝑔(𝑥 𝑖 ) = ∑︁ 𝑗=1..𝑚 𝛽 𝑗 𝑓 (𝑥 ′ 𝑗 ), заметим, что из этого определения следует свойство ∀ 𝑥, 𝑥 ′ ∈ 𝑋 ⟨𝐾 𝑥 , 𝐾 𝑥 ′ ⟩ = 𝐾(𝑥, 𝑥 ′ ) = 𝐾 𝑥 (𝑥 ′ ) = 𝐾 𝑥 ′ (𝑥), (2.85) 57 ∙ ℋ 𝐾 определяется как пополнение ℱ 𝑋 в метрике 𝜌, задаваемой ска- лярным произведением: ∀ 𝑓, 𝑔 ∈ ℱ 𝑋 𝜌(𝑓, 𝑔) = ||𝑓 − 𝑔|| = √︀⟨𝑓 − 𝑔, 𝑓 − 𝑔⟩, ∙ скалярное произведение на ℋ 𝐾 определяется следующим образом: ∀ 𝑓, 𝑔 ∈ ℋ 𝐾 , если 𝑓 = lim 𝑛→∞ 𝑓 𝑛 и 𝑔 = lim 𝑛→∞ 𝑔 𝑛 , где ∀ 𝑛 ≥ 1 𝑓 𝑛 , 𝑔 𝑛 ∈ ℱ 𝑋 , то ⟨𝑓, 𝑔⟩ def = lim 𝑛→∞ ⟨𝑓 𝑛 , 𝑔 𝑛 ⟩ (нетрудно доказать, что данный предел существует и не зависит от выбора последовательностей (𝑓 𝑛 ) и (𝑔 𝑛 ), сходящихся к 𝑓 и 𝑔 соот- ветственно). Функция 𝜙 : 𝑋 → ℋ 𝐾 определяется как отображение 𝑥 ↦→ 𝐾 𝑥 . Свой- ство (2.84) следует из определения функции 𝜙 и соотношения (2.85). Нетрудно доказать, что ∙ ∀ 𝑓 ∈ ℋ 𝐾 , ∀ 𝑥 ∈ 𝑋 𝑓 (𝑥) = ⟨𝑓, 𝐾 𝑥 ⟩, |𝑓 (𝑥)| ≤ ||𝑓 || √︀𝐾(𝑥, 𝑥), (2.86) неравенство в (2.86) верно потому, что оно эквивалентно неравен- ству Коши-Буняковского |⟨𝑓, 𝐾 𝑥 ⟩| ≤ ||𝑓 || √︀⟨𝐾 𝑥 , 𝐾 𝑥 ⟩, ∙ ∀ 𝑥 ∈ 𝑋 функционал ℋ 𝐾 → R : 𝑓 ↦→ 𝑓 (𝑥) непрерывен, т.е. 𝑓 = lim 𝑛→∞ 𝑓 𝑛 ⇒ 𝑓 (𝑥) = lim 𝑛→∞ 𝑓 𝑛 (𝑥), это можно обосновать с использованием свойства ∀ 𝑓, 𝑓 ′ ∈ ℋ 𝐾 , ∀ 𝑥 ∈ 𝑋 |𝑓 (𝑥) − 𝑓 ′ (𝑥)| ≤ ||𝑓 − 𝑓 ′ || √︀ 𝐾(𝑥, 𝑥), которое следует из неравенства в (2.86). Теорема 5. Пусть заданы ∙ выборка 𝑆 ⊆ 𝑋 × R, 58 ∙ ядро 𝐾 : 𝑋 2 → R, ∙ функция потерь 𝑐 : (𝑋 × R × R) * → R ≥0 (например, 𝑐 (︁ (𝑥 𝑖 , 𝑦 𝑖 , 𝑓 (𝑥 𝑖 )) 𝑖=1..𝑙 )︁ = 1 𝑙 𝑙 ∑︀ 𝑖=1 (𝑦 𝑖 − 𝑓 (𝑥 𝑖 )) 2 ), и ∙ строго возрастающая функция Ω : R ≥0 → R ≥0 Если ˆ 𝑓 ∈ ℋ 𝐾 – решение задачи 𝑐 (︁ (𝑥 𝑖 , 𝑦 𝑖 , 𝑓 (𝑥 𝑖 )) 𝑖=1..𝑙 )︁ + Ω(||𝑓 ||) → min (2.87) то ˆ 𝑓 = 𝑙 ∑︀ 𝑖=1 𝛼 𝑖 𝐾 𝑥 𝑖 , где 𝛼 1 , . . . , 𝛼 𝑙 ∈ R. Доказательство. Вектор ˆ 𝑓 ∈ ℋ 𝐾 можно представить в виде суммы ˆ 𝑓 = 𝑙 ∑︁ 𝑗=1 𝛼 𝑗 𝐾 𝑥 𝑗 + 𝑓 * , где 𝑓 * – вектор из ортогонального дополнения подпространства в ℋ 𝐾 , порожденного векторами 𝐾 𝑥 1 , . . . , 𝐾 𝑥 𝑙 , т.е. ∀ 𝑖 = 1, . . . , 𝑙 ⟨𝑓 * , 𝐾 𝑥 𝑖 ⟩ = 0. (2.88) Согласно равенству в (2.86) и соотношению (2.88), ∀ 𝑖 = 1, . . . , 𝑙 ˆ 𝑓 (𝑥 𝑖 ) = ⟨ ˆ 𝑓 , 𝐾 𝑥 𝑖 ⟩ = ⟨ 𝑙 ∑︁ 𝑗=1 𝛼 𝑗 𝐾 𝑥 𝑗 , 𝐾 𝑥 𝑖 ⟩ + ⟨𝑓 * , 𝐾 𝑥 𝑖 ⟩ = 𝑙 ∑︁ 𝑗=1 𝛼 𝑗 𝐾(𝑥 𝑗 , 𝑥 𝑖 ), откуда следует, что ˆ 𝑓 (𝑥 𝑖 ) не зависит от 𝑓 * , поэтому первое слагаемое в сумме в (2.87) не зависит от 𝑓 * Докажем, что 𝑓 * = ¯ 0 (нулевой вектор). Если 𝑓 * ̸= ¯ 0, то замена 𝑓 * на ¯ 0 не изменила бы первое слагаемое в сумме в (2.87), а второе бы только уменьшилось, т.к. ∀ 𝑓 1 , 𝑓 2 ∈ ℋ 𝐾 если ⟨𝑓 1 , 𝑓 2 ⟩ = 0, то ||𝑓 1 + 𝑓 2 || 2 = ⟨𝑓 1 + 𝑓 2 , 𝑓 1 + 𝑓 2 ⟩ = ⟨𝑓 1 , 𝑓 1 ⟩ + ⟨𝑓 2 , 𝑓 2 ⟩ = ||𝑓 1 || 2 + ||𝑓 2 || 2 поэтому || ˆ 𝑓 || 2 = || 𝑙 ∑︀ 𝑖=1 𝛼 𝑖 𝐾 𝑥 𝑖 || 2 + ||𝑓 * || 2 > || 𝑙 ∑︀ 𝑖=1 𝛼 𝑖 𝐾 𝑥 𝑖 || 2 , откуда следует нера- венство Ω(|| ˆ 𝑓 ||) > Ω(|| 𝑙 ∑︁ 𝑖=1 𝛼 𝑖 𝐾 𝑥 𝑖 ||) которое противоречит предположению о том, что ˆ 𝑓 – решение задачи (2.87). 59 2.7 Задача регрессии В задаче регрессии выборка, как правило, имеет вид 𝑆 = {(𝑥 1 , 𝑦 1 ), . . . , (𝑥 𝑙 , 𝑦 𝑙 )} ⊆ R 𝑛 × R, т.е. ответами являются действительные числа (м.б. также и вектора из действительных чисел). Задача регрессии заключается в том, чтобы по известным значениям 𝑦 𝑖 некоторой неизвестной функции в заданных точ- ках 𝑥 𝑖 (𝑖 = 1, . . . , 𝑙) предсказать значения этой функции в других точках. 2.7.1 Линейная регрессия Пусть задана выборка 𝑆 = {(𝑥 1 , 𝑦 1 ), . . . , (𝑥 𝑙 , 𝑦 𝑙 )} ⊆ R 𝑛 × R. Требуется найти АФ 𝑎 𝑆 (𝑥) в виде ⟨𝑥, 𝑤⟩ + 𝑤 0 , где 𝑤 ∈ R 𝑛 , 𝑤 0 ∈ R, причем должно быть выполнено условие 𝑄(𝑎 𝑆 ) = 1 𝑙 𝑙 ∑︁ 𝑖=1 ℒ(𝑎 𝑆 , 𝑥 𝑖 ) = 1 𝑙 𝑙 ∑︁ 𝑖=1 (𝑎 𝑆 (𝑥 𝑖 ) − 𝑦 𝑖 ) 2 → min . Поскольку множитель 1 𝑙 не влияет на решение задачи поиска опти- мальной АФ 𝑎 𝑆 , то мы его писать не будем. Заметим, что 𝑎 𝑆 (𝑥 𝑖 ) = ⟨𝑥 𝑖 , 𝑤⟩ + 𝑤 0 = ⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩, где ˜ 𝑤 = (𝑤, 𝑤 0 ) и ˜ 𝑥 𝑖 = (𝑥 𝑖 , 1). Таким образом, требуется найти ˜ 𝑤 ∈ R 𝑛+1 , решающий задачу 𝑄( ˜ 𝑤) def = 𝑙 ∑︁ 𝑖=1 (⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩ − 𝑦 𝑖 ) 2 → min (2.89) Обозначим символами 𝑋 и 𝑌 матрицу и столбец соответственно 𝑋 = ⎛ ⎝ ˜ 𝑥 1 ˜ 𝑥 𝑙 ⎞ ⎠ , 𝑌 = ⎛ ⎝ 𝑦 1 𝑦 𝑙 ⎞ ⎠ Если рассматривать ˜ 𝑤 как столбец, то можно переписать (2.89) в виде 𝑄( ˜ 𝑤) = ||𝑋 ˜ 𝑤 − 𝑌 || 2 → min (2.90) 𝑄( ˜ 𝑤) – выпуклая функция, т.к. она является суперпозицией выпуклой функции ˜ 𝑤 ↦→ ||𝑋 ˜ 𝑤 − 𝑌 || и выпуклой функции 𝑥 ↦→ 𝑥 2 , причем вторая 60 функция возрастает. Выпуклость второй из этих функций была обос- нована в пункте 2.5.2, выпуклость первой обосновывается следующим образом: ∀ 𝛼 ∈ [0, 1], ∀ ˜ 𝑤, ˜ 𝑤 ′ ∈ R 𝑛+1 ||𝑋(𝛼 ˜ 𝑤 + (1 − 𝛼) ˜ 𝑤 ′ ) − 𝑌 || = = ||𝑋(𝛼 ˜ 𝑤 + (1 − 𝛼) ˜ 𝑤 ′ ) − 𝛼𝑌 − (1 − 𝛼)𝑌 || = = ||𝛼(𝑋 ˜ 𝑤 − 𝑌 ) + (1 − 𝛼)(𝑋 ˜ 𝑤 ′ − 𝑌 )|| ≤ ≤ 𝛼||𝑋 ˜ 𝑤 − 𝑌 || + (1 − 𝛼)||𝑋 ˜ 𝑤 ′ − 𝑌 ||. Поэтому ˜ 𝑤 является решением задачи (2.90) если и только если |