Книга представляет собой введение в основные понятия, методы и ал

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

→
Каждому ядру 𝐾 : 𝑋² R соответствует каноническое гильбертово пространство, определяемое ядром 𝐾. Данное пространство обознача- ется записью ℋ_𝐾 и обладает следующим свойством: ∃ 𝜙 : 𝑋 → ℋ_𝐾:
∀ , ^′ ∈ 𝑋 𝐾(, ^′) = ⟨𝜙(), 𝜙(^′)⟩. (2.84)
ℋ_𝐾 определяется как подпространство линейного пространства R^𝑋
функций вида 𝑋 → R следующим образом:

• 
  ∀ ∈ 𝑋 обозначим записью 𝐾 функцию из R^𝑋, которая отобра- жает каждый ^′ ∈ 𝑋 в 𝐾(, ^′),
  

• 
  ℱ
  

обозначим символом _𝑋 линейное подпространство в R^𝑋, порож- денное всеми функциями вида 𝐾, т.е.

∑︁
ℱ_𝑋 = {
=1..
𝛼𝐾 | ≥ 1, ∀ = 1, . . . , 𝛼 ∈ R, ∈ 𝑋},

• 
  
  вид 𝑓 =
  
  𝛼𝐾 и 𝑔 =
  
  𝛽𝐾^′ , то
  определим_∑︀скалярное прои_∑︀зведение на ℱ_𝑋: если 𝑓, 𝑔 из ℱ_𝑋 имеют
  

=1..


=1..

⟨ ⟩

∑︁

∑︁
def
𝑓, 𝑔 =
=1..^∑︁,=1..
𝛼𝛽𝐾(, ^′ ) =
=1..

𝛼𝑔() =

=1..
𝛽𝑓 (^′ ),

заметим, что из этого определения следует свойство
∀ , ^′ ∈ 𝑋 ⟨𝐾, 𝐾^′ ⟩ = 𝐾(, ^′) = 𝐾(^′) = 𝐾^′ (), (2.85)

• 
  ℋ ℱ
  

_𝐾 определяется как пополнение _𝑋 в метрике 𝜌, задаваемой ска- лярным произведением:
∀ 𝑓, 𝑔 ∈ ℱ_𝑋 𝜌(𝑓, 𝑔) = |𝑓 − 𝑔 | = ^√︀⟨𝑓 − 𝑔, 𝑓 − 𝑔⟩,

• 
  скалярное произведение на ℋ_𝐾 определяется следующим образом:
  

∀ 𝑓, 𝑔 ∈ ℋ_𝐾, если 𝑓 = lim 𝑓 и 𝑔 = lim 𝑔, где ∀ ≥ 1 𝑓, 𝑔 ∈ ℱ_𝑋,

_то →∞

def
→∞

→∞
⟨𝑓, 𝑔⟩ = lim ⟨𝑓, 𝑔⟩
(нетрудно доказать, что данный предел существует и не зависит от выбора последовательностей (𝑓) и (𝑔), сходящихся к 𝑓 и 𝑔 соот- ветственно).

→ ℋ ↦→
Функция 𝜙 : 𝑋 _𝐾 определяется как отображение 𝐾. Свой- ство (2.84) следует из определения функции 𝜙 и соотношения (2.85).
Нетрудно доказать, что

• 
  ∀ 𝑓 ∈ ℋ_𝐾, ∀ ∈ 𝑋
  

|𝑓 ()| ≤ |𝑓 |

𝐾(, ),
𝑓 () = ⟨𝑓, 𝐾_√︀⟩,
(2.86)

неравенство в (2.86) верно потому, что оно эквивалентно неравен- ству Коши-Буняковского

|⟨𝑓, 𝐾⟩| ≤ |𝑓 | ^√︀⟨𝐾, 𝐾⟩,

• 
  ∀ ∈ 𝑋 функционал ℋ_𝐾 → R : 𝑓 ↦→ 𝑓 () непрерывен, т.е.
  

𝑓 = lim 𝑓 ⇒ 𝑓 () = lim 𝑓(),
→∞ →∞

√︀
это можно обосновать с использованием свойства

∀ 𝑓, 𝑓 ^′ ∈ ℋ_𝐾, ∀ ∈ 𝑋 |𝑓 () − 𝑓 ^′()| ≤ |𝑓 − 𝑓 ^′ | 𝐾(, ),

которое следует из неравенства в (2.86).
Теорема 5. Пусть заданы

• 
  выборка 𝑆 ⊆ 𝑋 × R,
  

• 
  ядро 𝐾 : 𝑋² → R,
  
• 
  функция потерь 𝑐 : (𝑋 × R × R)^* → R_≥0
  

(например,
_𝑐(︁
(, , 𝑓 ())_=1..^)︁ =
_{1 ∑︀}



( − 𝑓 ())²), и

=1

• 
  строго возрастающая функция Ω : R_≥0 → R_≥0. Если 𝑓^ˆ ∈ ℋ_𝐾 – решение задачи
  

𝑐^(︁(, , 𝑓 ())_=1..^)︁ + Ω( |𝑓 |) → min (2.87)

∑︀
то 𝑓^ˆ =
=1

𝛼𝐾
, где

𝛼₁, . . . , 𝛼 ∈ R.

Доказательство.

Вектор 𝑓^ˆ ∈ ℋ_𝐾 можно представить в виде суммы

∑︁


𝑓^ˆ = 𝛼𝐾 + 𝑓 ^*,
=1

ℋ
где 𝑓 ^* – вектор из ортогонального дополнения подпространства в _𝐾, порожденного векторами 𝐾₁ , . . . , 𝐾 , т.е.
∀ = 1, . . . , ⟨𝑓 ^*, 𝐾 ⟩ = 0. (2.88) Согласно равенству в (2.86) и соотношению (2.88), ∀ = 1, . . . ,


=1


=1

𝑓^ˆ() = ⟨𝑓^ˆ, 𝐾 ⟩ = ⟨^∑︁ 𝛼𝐾 , 𝐾 ⟩ + ⟨𝑓 ^*, 𝐾 ⟩ = ^∑︁ 𝛼𝐾(, ),
откуда следует, что 𝑓^ˆ() не зависит от 𝑓 ^*, поэтому первое слагаемое в сумме в (2.87) не зависит от 𝑓 ^*.

̸
Докажем, что 𝑓 ^* = ^¯0 (нулевой вектор). Если 𝑓 ^* = ^¯0, то замена 𝑓 ^* на
^¯0 не изменила бы первое слагаемое в сумме в (2.87), а второе бы только уменьшилось, т.к. ∀ 𝑓₁, 𝑓₂ ∈ ℋ_𝐾 если ⟨𝑓₁, 𝑓₂⟩ = 0, то

2

2

∑︀

∑︀

2

2
|𝑓₁ + 𝑓₂ | = ⟨𝑓₁ + 𝑓₂, 𝑓₁ + 𝑓₂⟩ = ⟨𝑓₁, 𝑓₁⟩ + ⟨𝑓₂, 𝑓₂⟩ = |𝑓₁ | + |𝑓₂ |

поэтому венство
|𝑓^ˆ|²

|
=

=1
𝛼𝐾 |
+ |𝑓 ^* |²

|
>

=1

∑︁

𝛼𝐾 |

², откуда следует нера-

Ω( |𝑓^ˆ|) > Ω( | 𝛼𝐾 |)
=1
которое противоречит предположению о том, что (2.87).

𝑓^ˆ – решение задачи

0. Задача регрессии

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

2.7.1 Линейная регрессия

{ } ⊆ ×
Пусть задана выборка 𝑆 = (₁, ₁), . . . , (, ) R R.

⟨ ⟩ ∈ ∈
Требуется найти АФ 𝑎_𝑆() в виде , + ₀, где R, ₀ R, причем должно быть выполнено условие

𝑆

𝑄(𝑎
) = ^{1 ∑︁} ℒ(𝑎



, ) = ^{1 ∑︁}(𝑎



( ) − )² → min .

𝑆

𝑆

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

мальной АФ 𝑎_𝑆, то мы его писать не будем.
Заметим, что
𝑎_𝑆() = ⟨, ⟩ + ₀ = ⟨˜, ˜⟩,
где ˜ = (, ₀) и ˜ = (, 1).
Таким образом, требуется найти ˜ ∈ R⁺¹, решающий задачу

˜) =

=1

𝑄( ^{def ∑︁}(⟨˜, ˜⟩ − )² → min (2.89)
Обозначим символами 𝑋 и 𝑌 матрицу и столбец соответственно
⎛ _˜1 ⎞ ⎛ ₁ ⎞

˜





𝑋 = ^⎝ . . . ^⎠ , 𝑌 = ^⎝ . . . ^⎠ .

Если рассматривать ˜ как столбец, то можно переписать (2.89) в виде

𝑄(˜) = |𝑋˜ − 𝑌 |² → min (2.90)
𝑄(˜) – выпуклая функция, т.к. она является суперпозицией выпуклой

функции ˜
↦→ |𝑋˜ − 𝑌 | и выпуклой функции ↦→ ², причем вторая

функция возрастает. Выпуклость второй из этих функций была обос- нована в пункте 2.5.2, выпуклость первой обосновывается следующим образом: ∀ 𝛼 ∈ [0, 1], ∀ ˜, ˜^′ ∈ R⁺¹
|𝑋(𝛼˜ + (1 − 𝛼)˜^′) − 𝑌 | =
= |𝑋(𝛼˜ + (1 − 𝛼)˜^′) − 𝛼𝑌 − (1 − 𝛼)𝑌 | =
= |𝛼(𝑋˜ − 𝑌 ) + (1 − 𝛼)(𝑋˜^′ − 𝑌 ) | ≤
≤ 𝛼 |𝑋˜ − 𝑌 | + (1 − 𝛼) |𝑋˜^′ − 𝑌 |.
Поэтому ˜ является решением задачи (2.90) если и только если
𝜕𝑄

∀ = 1, . . . , + 1


𝜕˜
= 0. (2.91)

Учитывая определение функции 𝑄, перепишем (2.91) в виде

𝜕𝑄

𝜕˜
∀ = 1, . . . , + 1

= ^∑︁ 2(⟨˜ , ˜⟩ − )(˜ )

= 0 (2.92)

∀ ∀

Поскольку = 1, . . . , , = 1, . . . , + 1 (˜) есть элемент 𝑋

матрицы 𝑋, то соотношения (2.92) можно переписать в виде

∀ = 1, . . . , + 1
^∑︁⟨˜, ˜⟩𝑋 = ^∑︁ 𝑋. (2.93)

Обозначим записью 𝑋^⊤ матрицу, транспонированную к 𝑋, т.е.

∀ = 1, . . . , + 1, ∀ = 1, . . . , 𝑋^⊤ = 𝑋,
и перепишем (2.93) в виде

∀ = 1, . . . , + 1
^∑︁ 𝑋^⊤ ⟨˜, ˜⟩ = ^∑︁ 𝑋^⊤ . (2.94)

∀ = 1, . . . , ⟨˜, ˜⟩ есть –й элемент столбца 𝑋˜, обозначим его записью (𝑋˜). Нетрудно видеть, что ∀ = 1, . . . , + 1

• 
  левая сумма в (2.94), т.е.
  

𝑋^⊤(𝑋˜), и

∑︀
=1
𝑋^⊤ (𝑋˜), есть –й элемент столбца

• 
  правая сумма в (2.94) есть –й элемент столбца 𝑋^⊤𝑌 .
  

Таким образом, столбцы 𝑋^⊤𝑋˜ и 𝑋^⊤𝑌 совпадают, т.е. искомый век- тор ˜ является решением уравнения
𝑋^⊤𝑋˜ = 𝑋^⊤𝑌. (2.95)
Нетрудно доказать, что данное уравнение всегда имеет решение. Если матрица 𝑋^⊤𝑋 невырождена, то уравнение (2.95) имеет един-
ственное решение
˜ = (𝑋^⊤𝑋)⁻¹𝑋^⊤𝑌,
а если она вырождена, то решение уравнения (2.95) м.б. неединственным. Так может произойти, например, если число пар в обучающей выборке
𝑆 меньше . В этом случае вместо задачи (2.90) разумнее решать задачу

| |
𝑄(˜) = |𝑋˜ − 𝑌 |² + 𝑐 |˜ |² → min, (2.96) где 𝑐 – параметр, выражающий штраф за большую ˜ .
Данная задача называется задачей гребневой (ridge) регрессии.
Поскольку минимизируемая функция 𝑄 в (2.96) является выпуклой и дифференцируемой, то искомое решение должно обращать в 0 все част- ные производные функции 𝑄:

𝜕𝑄

𝜕˜
∀ = 1, . . . , + 1

= ^∑︁ 2(⟨˜ , ˜⟩ − )(˜ )

+ 2𝑐˜

= 0.

Это соотношение можно переписать в виде

∑︁

∀ = 1, . . . , + 1
(⟨˜, ˜⟩ − )𝑋 + 𝑐˜ = 0. (2.97)
=1

_∑︀
Нетрудно доказать, что ∀ = 1, . . . , + 1

• 
  первое слагаемое в (2.97), т.е. столбца 𝑋^⊤𝑋˜ − 𝑋^⊤𝑌 , и
  

( ˜, ˜ )𝑋, есть –й элемент

⟨ ⟩ −
=1

• 
  слагаемое 𝑐˜ в (2.97) есть –й элемент столбца 𝑐˜. Поэтому искомый вектор ˜ является решением уравнения
  

𝑋^⊤𝑋˜ − 𝑋^⊤𝑌 + 𝑐˜ = 0^↓ (где 0^↓ – нулевой столбец порядка + 1),
которое можно переписать в виде
(𝑋^⊤𝑋 + 𝑐𝐸)˜ = 𝑋^⊤𝑌 (где 𝐸 – единичная матрица порядка + 1).

∀
Нетрудно доказать, что матрица 𝑋^⊤𝑋 + 𝑐𝐸 невырождена 𝑐 > 0. Таким образом, решение задачи гребневой регрессии имеет вид
˜ = (𝑋^⊤𝑋 + 𝑐𝐸)⁻¹𝑋^⊤𝑌.

0.