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

Применение метода

Применим изложенный выше метод к оптимизационной задаче (2.42) при условиях (2.41). В данном случае

• 
  
  2
  целевая функция 𝑓 имеет вид ^{| |}2 , и
  
• 
  условия являются линейными неравенствами
  

(⟨, ⟩ − ₀) − 1 ≥ 0, где ∈ 𝑋_𝑆. (2.59)

2
Докажем, что целевая функция выпукла. Данная функция является суперпозицией трех функций: функции ↦→ | |, функции ↦→ ², и функции ↦→ ¹ . Эти функции выпуклы, т.к.

• 
  выпуклость функции ↦→ | | следует из неравенства треуголь- ника ( |𝑎 + 𝑏 | ≤ |𝑎 | + |𝑏 |) для нормы в произвольном векторном пространстве: ∀ , ^′ ∈ R, ∀ 𝛼 ∈ [0, 1]
  

|𝛼 + (1 − 𝛼)^′ | ≤ |𝛼 | + |(1 − 𝛼)^′ | = 𝛼 | | + (1 − 𝛼) |^′ |,

• 
  выпуклость функции ↦→ ² обосновывается следующим образом:
  

∀ , ^′ ∈ R, ∀ 𝛼 ∈ [0, 1] требуемое неравенство
(𝛼 + (1 − 𝛼)^′)² ≤ 𝛼² + (1 − 𝛼)(^′)²
после раскрытия скобок, перегруппировки слагаемых и приведения подобных членов преобразуется в эквивалентное неравенство
𝛼²( − ^′)² ≤ 𝛼( − ^′)²
которое верно потому, что 𝛼 ∈ [0, 1],

2

• 
  ↦→
  

функция ¹ выпукла потому, что любая линейная функция является выпуклой.
Нетрудно доказать, что если функции 𝑓 : R → R и 𝑔 : R → R выпуклы и, кроме того, 𝑔 монотонно неубывающая, то их суперпозиция (𝑔 ∘ 𝑓 ) тоже выпукла. Действительно, ∀ , ^′ ∈ R, ∀ 𝛼 ∈ [0, 1]
(𝑔 ∘ 𝑓 )(𝛼 + (1 − 𝛼)^′) = 𝑔(𝑓 (𝛼 + (1 − 𝛼)^′)) ≤
≤ 𝑔(𝛼𝑓 () + (1 − 𝛼)𝑓 (^′)) ≤ 𝛼𝑔(𝑓 ()) + (1 − 𝛼)𝑔(𝑓 (^′)) =
= 𝛼(𝑔 ∘ 𝑓 )() + (1 − 𝛼)(𝑔 ∘ 𝑓 )(^′).

2

↦→ ↦→ →
Поскольку функции ² и ¹ : R R – выпуклы и монотонно неубывающие, то, следовательно их суперпозиция с выпуклой функцией

2

↦→ | | ↦→ | |
, т.е. функция ^{1 2} тоже выпукла.
Функция Лагранжа для данной задачи имеет вид

𝐿 =

| |²

−

2∑︁∈𝑋_𝑆
𝜆((⟨, ⟩ − ₀) − 1), (2.60)

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

∀ = 1, . . . , ˆ − ∑︁ 𝜆^ˆ = 0, 0 − ∑︁ 𝜆^ˆ(−1) = 0,

∈𝑋_𝑆
что можно переписать в виде
∈𝑋_𝑆

∈𝑋_𝑆


∈𝑋_𝑆

ˆ = ∑︁ 𝜆^ˆ, ∑︁ 𝜆^ˆ = 0. (2.61)
Из теоремы 3 следует, что исходная задача сводится к задаче поиска вектора ˆ, числа ˆ₀, и набора чисел 𝜆^ˆ = 𝜆^ˆ 0 𝑋_𝑆 , удовлетво- ряющих соотношениям в (2.61) и условию

Теорема 4.

∀ ∈ 𝑋_𝑆
(⟨, ˆ⟩ − ˆ₀) − 1 ≥ 0

{ ≥ | ∈ }

{︂
𝜆^ˆ((⟨, ˆ⟩ − ˆ₀) − 1) = 0.
(2.62)

{ ≥ | ∈ }
Задача нахождения объектов ˆ, ˆ₀, и 𝜆^ˆ = 𝜆^ˆ 0 𝑋_𝑆 , удовле-

∑︁
творяющих соотношениям (2.61) и (2.62), сводится к задаче нахождения объектов ˆ, ˆ₀, и 𝜆^ˆ, минимизирующих значения выражения
𝜆^ˆ((⟨, ˆ⟩ − ˆ₀) − 1) (2.63)
∈𝑋_𝑆

∑︀
при условиях
ˆ =

⎪_⎩
∈𝑋_𝑆
𝜆^ˆ, 𝜆^ˆ = 0,

∑︀

{︂
∈𝑋_𝑆

∀ ∈ 𝑋_𝑆

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

𝜆^ˆ ≥ 0
(⟨, ˆ⟩ − ˆ₀) − 1 ≥ 0.
(2.64)

1. 
   Пусть объекты ˆ, ˆ₀, и 𝜆^ˆ = {𝜆^ˆ ≥ 0 | ∈ 𝑋_𝑆} удовлетворяют
   

соотношениям (2.61) и (2.62). Тогда при их подстановке вместо со- ответствующих объектов в (2.63) и (2.64) получаем, что

∙
значение суммы (2.63) будет равно 0 (т.к., согласно второму равенству в (2.62), каждое слагаемое в этой сумме равно 0), и

• 
  соотношения в (2.64) верны, это следует из (2.61) и (2.62).
  

С другой стороны, сумма (2.63) при условиях (2.64), не может быть меньше 0, т.к., согласно этим условиям, каждое ее слагаемое явля- ется произведением неотрицательных чисел.

{ ≥ | ∈ }
Таким образом, объекты ˆ, ˆ₀, и 𝜆^ˆ = 𝜆^ˆ 0 𝑋_𝑆 – решение задачи минимизации суммы (2.63) при условиях (2.64).

2. 
   Согласно условиям (2.64), каждое слагаемое в сумме (2.63) при этих условиях неотрицательно, т.е. сумма (2.63) неотрицательна, и
   

∙
если минимальное значение этой суммы равно 0, то каждое слагаемое в этой сумме равно 0, т.е. объекты ˆ, ˆ₀, и 𝜆^ˆ, реша- ющие задачу минимизации (2.63) при условиях (2.64), удовле-
творяют соотношениям (2.61) и (2.62), и

{ ≥ | ∈ }

∙
если минимальное значение этой суммы больше 0, то тогда решение задачи нахождения ˆ, ˆ₀, и 𝜆^ˆ = 𝜆^ˆ 0 𝑋_𝑆 , удовлетворяющих соотношениям (2.61) и (2.62), не существует
(что по предположению невозможно).
Перепишем сумму (2.63) путем раскрытия скобок, перегруппировки слагаемых и использования линейности скалярного произведения:

∈∑︀𝑋
𝜆^ˆ , ˆ

∑^︀⟨ ⟩ −
∈𝑋_𝑆
𝜆^ˆˆ₀

∑︀₋
∈𝑋_𝑆
𝜆^ˆ =

₌ ∑︀

∈𝑋_𝑆

∈𝑋_𝑆
= ⟨ ^∑︀
⟨𝜆^ˆ, ˆ⟩ − ( ^∑︀

∈𝑋_𝑆

∈𝑋_𝑆
𝜆^ˆ, ˆ⟩ − ( ^∑︀
𝜆^ˆ)ˆ₀ − ^∑︀

∈𝑋_𝑆

∈𝑋_𝑆
𝜆^ˆ)ˆ₀ − ^∑︀
𝜆^ˆ =
𝜆^ˆ.
(2.65)

Из условий (2.64) следует, что (2.65) можно переписать в виде

∈𝑋_𝑆


∈𝑋_𝑆

⟨ˆ, ˆ⟩ − ∑︁ 𝜆^ˆ = |ˆ|² − ∑︁ 𝜆^ˆ. (2.66)
Выражение (2.66) можно переписать, используя лишь переменные 𝜆^ˆ:

,∑︁^′∈𝑋_𝑆
𝜆^ˆ𝜆^{ˆ′ ′} ⟨, ^′⟩ − 𝜆^ˆ. (2.67)

∑︁
∈𝑋_𝑆

Таким образом, исходная задача свелась к задаче нахождения набора
𝜆^ˆ = {𝜆^ˆ | ∈ 𝑋_𝑆}

минимизирующего значение выражения (2.67), при условиях

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

∑︁
∈𝑋_𝑆

Такая задача называется задачей квадратичного программиро- вания (ЗКП). Существует много алгоритмов решения этой задачи.
Искомый вектор ˆ вычисляется по найденному решению 𝜆^ˆ данной
ЗКП согласно первому равенству в (2.64). Для вычисления искомого ˆ₀
выбирается такая пара ∈ 𝑋_𝑆, что 𝜆^ˆ ̸= 0, в этом случае, согласно
второму равенству в (2.62), должно быть верно равенство
(⟨, ˆ⟩ − ˆ₀) − 1 = 0,

из которого следует, что
ˆ₀ = ⟨, ˆ⟩ − .

Если данная ЗКП имеет не единственное решение, то среди всех этих ре- шений выбирается такое, что число ˆ₀, вычисленное по этому решению, удовлетворяет последнему неравенству в (2.64).
Обоснуем, почему ∃ ∈ 𝑋_𝑆 : 𝜆^ˆ 0. Если бы все числа 𝜆^ˆ были равны
0, то ˆ – нулевой вектор, и из последнего неравенства в (2.64) следует, что ∀ ∈ 𝑋_𝑆 − ˆ₀ − 1 ≥ 0, или −ˆ₀ ≥ 1. Выборка 𝑆 предполагается нетривиальной, т.е. м.б. равно как 1, так и −1, откуда следует, что
_ˆ0 ≥ 1 и −ˆ₀ ≥ 1, что невозможно.

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

⊆ × {− }
В некоторых случаях выборка 𝑆 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) и условию

^⎨ 𝜂ˆ𝜉^ˆ = 0

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

⎪_{⎩ ˆ}

ˆ

∀ ∈ 𝑋

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





_𝜆ˆ

и 𝜂ˆ

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

,^′∈𝑋_𝑆


∈𝑋_𝑆


∈𝑋_𝑆

∑︁ 𝜆^ˆ𝜆^{ˆ′ ′} ⟨, ^′⟩ − ∑︁ 𝜆^ˆ + 𝑐 ∑︁ 𝜉^ˆ. (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 или 𝑐 (если невозможно, то доказать это, а если возможно, то привести соответствующий пример).

6.