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

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

⊆ × {− }
В некоторых случаях выборка 𝑆 R 1, 1 бывает зашумленной, т.е. значения компонентов векторов в 𝑆, представляющих объекты, могут немного отличаться от истинных значений. Также в 𝑆 м.б. и ошибочно размеченные пары, т.е. пары (, ) с неверным значением . Это мо- жет привести к тому, что выборка 𝑆 не будет линейно разделимой, т.е. невозможно найти АФ 𝑎_𝑆 вида

𝑎_𝑆() = 𝑔

_{(︁ ∑︁}
− ₀^)︁

(2.68)

такую, что 𝑄(𝑎_𝑆) = 0. Тем не менее, иногда в ситуации зашумленности и линейной неразделимости выборки 𝑆 все равно имеет смысл искать АФ
𝑎_𝑆 вида (2.68), допуская при этом небольшие ошибки классификации.

∑︁
Один из подходов к построению АФ 𝑎_𝑆 такого вида называется ме- тодом наименьших квадратов, он будет рассмотрен в следующем параграфе. Данный подход заключается в том, чтобы найти АФ 𝑎_𝑆 вида (2.68) с наименьшим значением 𝑄(𝑎_𝑆), где
𝑄(𝑎_𝑆) = (𝑎_𝑆() − )².
∈𝑋_𝑆
Другой подход является развитием подхода, изложенного в преды- дущем пункте. Он заключается в том, чтобы построить разделяющую полосу максимальной ширины, допуская при этом попадание некоторых объектов не в свое полупространство.
Напомним, что если границами разделяющей полосы являются ги- перплоскости, определяемые уравнениями
⟨, ⟩ − ₀ = 1, ⟨, ⟩ − ₀ = −1,
то ∀ ∈ 𝑋_𝑆 точка попадает в свое полупространство, если 𝑀 ≥ 1, где

⟨ ⟩ − .
def
𝑀 = ( , ₀)
Для адекватного определения целевой функции введем набор 𝜉 до-
полнительных переменных:
𝜉 = {𝜉 | ∈ 𝑋_𝑆},

−

∀ ∈
где 𝑋_𝑆 значение переменной 𝜉 будем понимать как величину ошиб- ки аппроксимации на объекте : она должна примерно соответствовать расстоянию от до своего полупространства, когда находится не в сво- ем полупространстве (т.е. 𝑀 < 1). Например, величину ошибки в этом случае можно определить как 1 𝑀.
Задача построения оптимальной разделяющей полосы в данной си- туации имеет вид минимизации целевой функции

| |²

2

+ 𝑐
^∑︁∈𝑋_𝑆

𝜉 (где 𝑐 – некоторая константа) (2.69)

при условиях

∀ ∈ 𝑋_𝑆 𝜉 ≥ 1 − 𝑀, 𝜉 ≥ 0

Целевая функция (2.69) выражает следующие требования:

• 
  | |
  

разделяющая полоса должна быть пошире (т.е. значение долж- но быть поменьше),

∑︀_∙
суммарная ошибка
∈𝑋_𝑆
𝜉 должна быть поменьше.

Константа 𝑐 позволяет регулировать баланс между требованиями

• 
  максимизации ширины разделяющей полосы, и
  
• 
  минимизации суммарной ошибки.
  

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

• 
  сначала задача решается при некотором 𝑐,
  

∙
затем из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки (такие объекты будут считаться или чрезмерно зашумленными, или ошибочно размеченными), а 𝑐 изме- няется следующим образом:

• 
  если ширина полосы получилась слишком маленькая, то 𝑐 уме- ньшается (это приведет к увеличению ширины полосы),
  
• 
  если слишком много объектов находятся далеко от своего по- лупространства, то 𝑐 увеличивается (полоса станет уже), и
  
• 
  после этого задача решается заново (с новыми 𝑆 и 𝑐). Возможно, придется проделать несколько таких итераций.
  

Функция Лагранжа для данной задачи имеет вид

𝐿 =

2

| |
+ 𝑐
2
^∑︁∈𝑋_𝑆

𝜉 −

^∑︁∈𝑋_𝑆

𝜆(𝑀 + 𝜉 − 1) −

^∑︁∈𝑋_𝑆

𝜂𝜉,

и соотношение (2.48) имеет следующий вид:

• 
  
  𝜕
  ∀ = 1, . . . , ^𝜕𝐿 (ˆ, 𝜆^ˆ, 𝜉^ˆ) = ˆ − ^∑︀
  

𝜆^ˆ = 0,

∈𝑋_𝑆

• 
  
  𝜕₀
  ^𝜕𝐿 (ˆ, 𝜆^ˆ, 𝜉^ˆ) = ^∑︀ 𝜆^ˆ = 0,
  

∈𝑋_𝑆

• 
  
  ^𝜕𝜉
  ∀ ∈ 𝑋_𝑆 ^𝜕𝐿 (ˆ, 𝜆^ˆ, 𝜉^ˆ) = 𝑐 − 𝜆^ˆ − 𝜂ˆ = 0, что можно переписать в виде
  

⎨

∑︀

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

(2.70)

∈𝑋_𝑆

⎪_⎩
∀ ∈ 𝑋_𝑆
𝜆^ˆ + 𝜂ˆ = 𝑐.

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

𝜆^ˆ = {𝜆^ˆ ≥ 0 | ∈ 𝑋_𝑆},
𝜂ˆ = {𝜂ˆ ≥ 0 | ∈ 𝑋_𝑆},

{ | ∈ }
а также вектора ˆ, числа ˆ₀, и набора чисел 𝜉 𝑋_𝑆 , удовлетво- ряющих равенствам (2.70) и условию

(2.71)

^⎨ 𝜂ˆ𝜉^ˆ = 0
𝜆^ˆ((⟨, ˆ⟩ − ˆ₀) + 𝜉^ˆ − 1) = 0

∀ ∈ 𝑋

𝑆

⎪_{⎩ ˆ}

ˆ
(⟨, ˆ⟩ − ˆ₀) + 𝜉 − 1 ≥ 0
𝜉 ≥ 0
Как и в предыдущем пункте, нахождение искомых наборов сводится к задаче минимизации выражения
^∑︁ 𝜆^ˆ((⟨, ˆ⟩ − ˆ₀) + 𝜉^ˆ − 1) + ^∑︁ 𝜂ˆ𝜉^ˆ



_𝜆ˆ
и 𝜂ˆ

которое, с учетом условий (2.70), можно переписать, используя лишь переменные 𝜆^ˆ и 𝜉^ˆ: