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

,^′∈𝑋_𝑆


∈𝑋_𝑆


∈𝑋_𝑆

^∑︁ 𝜆^ˆ𝜆^{ˆ′ ′} ⟨, ^′⟩ − ^∑︁ 𝜆^ˆ + 𝑐 ^∑︁ 𝜉^ˆ. (2.72)
Нетрудно установить, что исходная задача, рассматриваемая в насто- ящем пункте, сводится к задаче минимизации (2.72) с условиями

⎩
⎧_⎪⎨
∈^∑︀𝑋
𝜆^ˆ = 0,

𝑆

^⎪ ∀ ∈ 𝑋
^{︂ 0 ≤ 𝜆^ˆ ≤ 𝑐,
𝜉^ˆ ≥ 0,
(2.73)

=
где 𝑀 ^def (⟨, ˆ⟩ − ˆ₀),
def

𝑀

+ 𝜉^ˆ

ˆ =
^(,∑︀)∈

𝜆^ˆ.

— 1 ≥ 0,
Эта задача – тоже ЗКП. В результате ее решения получаются опти- мальные 𝜆^ˆ, 𝜉^ˆ, ˆ₀, по которым можно вычислить оптимальные ˆ и 𝜂ˆ.
Отметим некоторые особенности оптимального решения 𝜆^ˆ, 𝜂ˆ, 𝜉^ˆ, ˆ, ˆ₀

∀ ∈
исходной задачи. 𝑋_𝑆 вектор относится к одному из трех классов,
в зависимости от значения 𝑀:

∙
если 𝑀 > 1, то находится в своем полупространстве, но не на его границе (такой вектор называется периферийным),

∙
если 𝑀 = 1, то находится в своем полупространстве, на его границе (такой вектор называется опорным),

∙
если 𝑀 < 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 или 𝑐 (если невозможно, то доказать это, а если возможно, то привести соответствующий пример).

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

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

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

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

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

⊆ × {− }
Например, рассмотрим выборку 𝑆 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,
  
• 
  верен аналог неравенства Коши-Буняковского:
  

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

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

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

• 
  (𝑐⟨, ^′⟩ + 𝑑), где 𝑐, 𝑑 ∈ 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,
^¯∈^*:=[ ^¯ ]
_𝜆(^¯)_.

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

0.