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

Ядерный метод машинного обучения

1. Спрямляющие пространства

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

∙
не по причинам зашумленности компонентов векторов в 𝑆, пред- ставляющих объекты, или ошибочной разметки,

∙
а по причине наличия нетривиальных зависимостей между компо- нентами векторов в 𝑆, представляющих объекты.

⊆ × {− }
Например, рассмотрим выборку 𝑆 R² 1, 1 , изображенную на картинке (в которой мы представляем вектора из R² точками плоскости)

где черные кружочки изображают объекты из 𝑆⁺, а звездочки – объекты из 𝑆⁻. Такая выборка принципиально линейно неразделима.

лучше определять по его норме || =

² + ², т.е. искать 𝑎_𝑆 в виде

1


2

В данном случае принадлежность в_√︀ектора (₁, ₂) ∈ R² к 𝑆⁺ или 𝑆⁻
𝑎_𝑆() = 𝑔(︁ || − ₀)︁.

⊆ × {− }
Поиск АФ, соответствующих таким выборкам 𝑆 R 1, 1 , для которых невозможно построить АФ 𝑎_𝑆 в виде

𝑎_𝑆() = 𝑔

_{(︁ ∑︁}
− ₀
)︁, (2.74)

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

• 
  выбирается подходящее нелинейное отображение
  

𝜙 : R → R^𝑁 , (2.75)

=
с таким расчетом, чтобы выборка 𝑆_𝜙 ^def {(𝜙(), ) | ∈ 𝑋_𝑆} оказа-
лась бы линейно разделимой,
(R^𝑁 в (2.75) называется спрямляющим пространством)

• 
  методом опорных векторов для 𝑆_𝜙 ищется АФ 𝑎_𝑆𝜙 вида (2.74), и
  
• 
  искомая АФ 𝑎_𝑆 определяется как композиция 𝑎_𝑆𝜙 ∘ 𝜙.
  

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

пространства можно взять R², и 𝜙(₁, ₂
def
², ²).

) = ( _{1 2}
В других ситуациях рассматриваются функции 𝜙 : R → R^𝑁 вида
𝜙(₁, . . . , ) = (₁, . . . , , ², . . . , ² , . . . , , . . .).
1

∈

→
Нетрудно доказать, что для любой выборки 𝑆 существует спрямляю- щее пространство – это м.б., например, пространство R^𝑁 , где 𝑁 – число элементов в 𝑆. Если выбрать в R^𝑁 ортонормированный базис, и опре- делить 𝜙 : R R^𝑁 как инъективное отображение, сопоставляющее каждому элементу 𝑋_𝑆 некоторый вектор из этого базиса, то 𝑆_𝜙 бу- дет линейно разделима.
Отметим важную особенность функции 𝑎_𝑆𝜙 . Если 𝑆_𝜙 линейно разде- лима, то, как было показано выше, 𝑎_𝑆𝜙 можно искать в виде

∑︀_⟨
𝑎_𝑆𝜙 () = 𝑔(⟨𝜙(), ˆ⟩ − ˆ₀) =

= 𝑔( 𝜙(),

∑︀
′∈𝑋_𝑆
𝜆^{ˆ′ ′} 𝜙(^′)⟩ − ˆ₀) =
(2.76)

= 𝑔(
^′∈𝑋_𝑆
𝜆^{ˆ′ ′} ⟨𝜙(), 𝜙(^′)⟩ − ˆ₀),

где 𝜆^ˆ ищется как решение задачи минимизации выражения

при условиях
,∑︁^′∈𝑋_𝑆
𝜆^ˆ𝜆^{ˆ′ ′} ⟨𝜙(), 𝜙(^′)⟩ − 𝜆^ˆ (2.77)

∑︁
∈𝑋_𝑆

∀ ∈ 𝑋_𝑆
𝜆^ˆ ≥ 0, 𝜆^ˆ = 0. (2.78)

∑︁
∈𝑋_𝑆

Из (2.76) и (2.77) следует, что для построения 𝑎_𝑆𝜙 не надо знать

• 
  ни размерности спрямляющего пространства,
  
• 
  ни векторов вида 𝜙(), где ∈ 𝑋_𝑆,
  

⟨ ⟩
надо лишь знать скалярные произведения вида 𝜙(), 𝜙(^′) .

⟨ ⟩
Ядерный метод ML заключается в том, что построение АФ 𝑎_𝑆 де- лается методом, аналогичным описанному выше, но с заменой всех ска- лярных произведений 𝜙(), 𝜙(^′) на выражения вида 𝐾(, ^′), где 𝐾 – функция вида
𝐾 : R × R → R.
Данная функция называется ядром. Она определяется для 𝑆 мето- дом подбора, и должна обладать следующими свойствами:

• симметричность:

∀ , ^′ ∈ R 𝐾(, ^′) = 𝐾(^′, ), (2.79)

• положительная определенность:

∀ ₁, . . . , ∈ R , ∀ 𝛼₁, . . . , 𝛼 ∈ R

∑︁
𝛼𝛼𝐾(, ) ≥ 0. (2.80)
,=1

Построение АФ 𝑎_𝑆 сводится к задаче минимизации выражения

∑︁,^′∈𝑆
𝜆^ˆ𝜆^{ˆ′ ′} 𝐾(, ^′) − 𝜆^ˆ, (2.81)

∑︁
∈𝑋_𝑆

при условиях (2.78). Искомая АФ 𝑎_𝑆𝜙 определяется следующим образом:

∀ ∈ R 𝑎_𝑆𝜙

() = 𝑔

(︁ _∑︁
′∈𝑋_𝑆
𝜆^{ˆ′ ′} 𝐾(, ^′) − ˆ₀)︁,

ˆ

=

^′∈𝑋_𝑆
где ₀ ^{def ∑︀} 𝜆^{ˆ′ ′} 𝐾(^′′, ^′) − ^′′ , и ^′′ – произвольный вектор из 𝑋_𝑆,

̸
такой, что 𝜆^ˆ′′ = 0.
В общем случае ядро определяется как произвольная функция вида
𝐾 : 𝑋 × 𝑋 → R (2.82)
(где 𝑋 – множество, элементами которого являются объекты), являю- щаяся симметричной и положительно определенной, т.е. верны аналоги соотношений (2.79) и (2.80), в которых аргументами 𝐾 являются элемен- ты множества 𝑋.
Нетрудно доказать, что если 𝐾 – ядро вида (2.82), то

• 
  ∀ ∈ 𝑋 𝐾(, ) ≥ 0,
  
• 
  если ∀ ∈ 𝑋 𝐾(, ) = 0, то ∀ , ^′ ∈ 𝑋 𝐾(, ^′) = 0,
  
• 
  верен аналог неравенства Коши-Буняковского:
  

∀ , ^′ ∈ 𝑋 𝐾(, ^′) ≤ ^√︀𝐾(, )𝐾(^′, ^′).

2. Примеры ядер

𝐾(, ^′) может иметь, например, следующий вид:

• 
  (𝑐⟨, ^′⟩ + 𝑑), где 𝑐, 𝑑 ∈ R_≥0, ≥ 0 (полиномиальное ядро), (где R_≥0 – множество неотрицательных действительных чисел),
  
• 
  
  • 
    𝑎₀ + ^∑︀ 𝑎 sin() sin(^′)+ ^∑︀ 𝑏 cos() cos(^′), где ^∑︀ 𝑎² +𝑏² < ∞
    
  𝜎(𝑐⟨, ^′⟩ + 𝑑), где 𝜎 – сигмоида (сигмоидное ядро),
  

≥0
(ядро Фурье),
≥0

≥1

• 
  
  _𝜎2
  exp(− ^|−′ ^|2 ) (гауссово ядро),
  
• 
  
  _𝜎2
  exp(^⟨,′^⟩ ) (экспоненциальное ядро),
  
• 
  𝐾₁(, ^′)𝐾₂(, ^′), где 𝐾₁ и 𝐾₂ – ядра,
  
• 
  𝛼₁𝐾₁(, ^′) + 𝛼₂𝐾₂(, ^′), где 𝐾₁ и 𝐾₂ – ядра, 𝛼₁ и 𝛼₂ ∈ R_≥0,
  
• 
  𝐾(𝜙(), 𝜙(^′)), где 𝐾 – ядро, 𝜙 – произвольная функция. Приведем еще три примера ядра.
  

1. 
   В качестве ядра 𝑋 × 𝑋 → R может выступать функция вида
   

(, ^′) ↦→ ⟨𝜙(), 𝜙(^′)⟩
где 𝜙 – произвольная функция вида
𝜙 : 𝑋 → ℋ,

ℋ
и – спрямляющее пространство, которое является гильберто- вым пространством, т.е.

• 
  ℋ – линейное пространство со скалярным произведением, напомним, что скалярное произведение на ℋ – это функ- ция, сопоставляющая каждой паре (, ) ∈ ℋ×ℋ действитель- ное число ⟨, ⟩, и обладающая свойствами: ∀ , ^′, ∈ ℋ
  

– ∀ 𝛼, 𝛼^′ ∈ R ⟨𝛼 + 𝛼^′′, ⟩ = 𝛼⟨, ⟩ + 𝛼^′⟨^′, ⟩,
– ⟨, ⟩ = ⟨, ⟩,
– ⟨, ⟩ ≥ 0, причем ⟨, ⟩ = 0 ⇔ = ^¯0 (нулевой вектор),

• 
  ℋ – полное метрическое пространство (где метрика 𝜌 на ℋ определяется нормой: 𝜌(, ^′) = | − ^′ |, а норма определяется скалярным произведением: ||² = ⟨, ⟩), т.е. ∀ фундаменталь- ная последовательность имеет предел в ℋ,
  
• 
  ℋ – сепарабельное пространство, т.е. ∃ счетное подмноже- ство 𝐻 ⊆ ℋ: ∀ 𝜀 > 0, ∀ ℎ ∈ ℋ ∃ ℎ^′ ∈ 𝐻 : 𝜌(ℎ, ℎ^′) < 𝜀.
  

Примеры гильбертовых пространств: R или ₂, где

2 = {(₁, ₂, . . .) | ∑︁ ² < ∞},

≥1

∑︁
скалярное произведение в ₂ имеет вид
⟨(₁, ₂, . . .), (₁, ₂, . . .)⟩ = .
≥1

2. 
   
   × →
   Если 𝐾 – ядро вида 𝑋 𝑋 R, где 𝑋 – произвольное множество, то функция
   

𝐾^′ : _𝑓(𝑋) × _𝑓(𝑋) → R

(где _𝑓(𝑋) – множество всех конечных подмножеств 𝑋), опреде- ляемая следующим образом:

∑︁
∀ 𝐴, 𝐵 ∈ _𝑓(𝑋) 𝐾^′(𝐴, 𝐵) =
𝑎∈𝐴,𝑏∈𝐵
𝐾(𝑎, 𝑏)

тоже является ядром.

3. 
   Пусть заданы алфавит (т.е. множество символов) 𝐴, целое число
   

≥ 1, и действительное число 𝜆 ∈ (0, 1].
Обозначим записью ^* множество всех последовательностей
^¯ = (₁, . . . , ), где 1 ≤ ₁ < . . . < ≤ . (2.83) Если последовательность ^¯ ∈ ^* имеет вид (2.83), то

• 
  запись (^¯) обозначает число − ₁ + 1, и
  

• 
  ∈
  

для каждой цепочки 𝐴, если имеет вид 𝑎₁ . . . 𝑎, то запись [ ^¯ ] обозначает цепочку 𝑎₁ . . . 𝑎 .
Обозначим символом ℋ гильбертово пространство функций вида
𝑓 : 𝐴 → R,

∑︁
скалярное произведение на ℋ определяется следующим образом:
⟨𝑓, 𝑔⟩ = 𝑓 ()𝑔().
∈𝐴

Ядро 𝐾 : 𝐴 × 𝐴 → R определяется соотношением

^∑︀→ ℋ ∀ ∈ → ↦→
∀ , ^′ ∈ 𝐴 𝐾(, ^′) = ⟨𝜙(), 𝜙(^′)⟩,

где 𝜙 : 𝐴 , 𝐴 𝜙() : 𝐴 R,
^¯∈^*:=[ ^¯ ]
_𝜆(^¯)_.

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

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

→
Каждому ядру 𝐾 : 𝑋² 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).