Книга представляет собой введение в основные понятия, методы и ал
Построение оптимальной разделяющей гипер- плоскости по зашумленной выборке
Download 1.93 Mb.
|
machine-learning-mironov
Построение оптимальной разделяющей гипер- плоскости по зашумленной выборке⊆ × {− } В некоторых случаях выборка 𝑆 R 1, 1 бывает зашумленной, т.е. значения компонентов векторов в 𝑆, представляющих объекты, могут немного отличаться от истинных значений. Также в 𝑆 м.б. и ошибочно размеченные пары, т.е. пары (, ) с неверным значением . Это мо- жет привести к тому, что выборка 𝑆 не будет линейно разделимой, т.е. невозможно найти АФ 𝑎𝑆 вида 𝑎𝑆() = 𝑔 (︁ ∑︁ − 0)︁ (2.68)
такую, что 𝑄(𝑎𝑆) = 0. Тем не менее, иногда в ситуации зашумленности и линейной неразделимости выборки 𝑆 все равно имеет смысл искать АФ 𝑎𝑆 вида (2.68), допуская при этом небольшие ошибки классификации. ∑︁ Один из подходов к построению АФ 𝑎𝑆 такого вида называется ме- тодом наименьших квадратов, он будет рассмотрен в следующем параграфе. Данный подход заключается в том, чтобы найти АФ 𝑎𝑆 вида (2.68) с наименьшим значением 𝑄(𝑎𝑆), где 𝑄(𝑎𝑆) = (𝑎𝑆() − )2. ∈𝑋𝑆 Другой подход является развитием подхода, изложенного в преды- дущем пункте. Он заключается в том, чтобы построить разделяющую полосу максимальной ширины, допуская при этом попадание некоторых объектов не в свое полупространство. Напомним, что если границами разделяющей полосы являются ги- перплоскости, определяемые уравнениями ⟨, ⟩ − 0 = 1, ⟨, ⟩ − 0 = −1, то ∀ ∈ 𝑋𝑆 точка попадает в свое полупространство, если 𝑀 ≥ 1, где ⟨ ⟩ − . def 𝑀 = ( , 0) Для адекватного определения целевой функции введем набор 𝜉 до- полнительных переменных: 𝜉 = {𝜉 | ∈ 𝑋𝑆}, − ∀ ∈ где 𝑋𝑆 значение переменной 𝜉 будем понимать как величину ошиб- ки аппроксимации на объекте : она должна примерно соответствовать расстоянию от до своего полупространства, когда находится не в сво- ем полупространстве (т.е. 𝑀 < 1). Например, величину ошибки в этом случае можно определить как 1 𝑀. Задача построения оптимальной разделяющей полосы в данной си- туации имеет вид минимизации целевой функции | |2 2
+ 𝑐 ∑︁∈𝑋𝑆 𝜉 (где 𝑐 – некоторая константа) (2.69) при условиях ∀ ∈ 𝑋𝑆 𝜉 ≥ 1 − 𝑀, 𝜉 ≥ 0 Целевая функция (2.69) выражает следующие требования: | | ∑︀∙ суммарная ошибка ∈𝑋𝑆 𝜉 должна быть поменьше. Константа 𝑐 позволяет регулировать баланс между требованиями максимизации ширины разделяющей полосы, и минимизации суммарной ошибки. Обычно ее выбирают методом скользящего контроля: сначала задача решается при некотором 𝑐, ∙ затем из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки (такие объекты будут считаться или чрезмерно зашумленными, или ошибочно размеченными), а 𝑐 изме- няется следующим образом: если ширина полосы получилась слишком маленькая, то 𝑐 уме- ньшается (это приведет к увеличению ширины полосы), если слишком много объектов находятся далеко от своего по- лупространства, то 𝑐 увеличивается (полоса станет уже), и после этого задача решается заново (с новыми 𝑆 и 𝑐). Возможно, придется проделать несколько таких итераций. Функция Лагранжа для данной задачи имеет вид 𝐿 = 2 | | + 𝑐 2 ∑︁∈𝑋𝑆 𝜉 − ∑︁∈𝑋𝑆 𝜆(𝑀 + 𝜉 − 1) − ∑︁∈𝑋𝑆 𝜂𝜉,
и соотношение (2.48) имеет следующий вид: 𝜕 ∀ = 1, . . . , 𝜕𝐿 (ˆ, 𝜆ˆ, 𝜉ˆ) = ˆ − ∑︀ 𝜆ˆ = 0, ∈𝑋𝑆 𝜕0 𝜕𝐿 (ˆ, 𝜆ˆ, 𝜉ˆ) = ∑︀ 𝜆ˆ = 0, ∈𝑋𝑆 𝜕𝜉 ∀ ∈ 𝑋𝑆 𝜕𝐿 (ˆ, 𝜆ˆ, 𝜉ˆ) = 𝑐 − 𝜆ˆ − 𝜂ˆ = 0, что можно переписать в виде ⎨ ∑︀ ∈𝑋𝑆 𝜆ˆ = 0, ⎧⎪ ˆ = ∑︀ 𝜆ˆ, (2.70) ∈𝑋𝑆 ⎪⎩ ∀ ∈ 𝑋𝑆 𝜆ˆ + 𝜂ˆ = 𝑐. Из теоремы Каруша-Куна-Таккера следует, что исходная задача сво- дится к задаче поиска наборов чисел 𝜆ˆ = {𝜆ˆ ≥ 0 | ∈ 𝑋𝑆}, 𝜂ˆ = {𝜂ˆ ≥ 0 | ∈ 𝑋𝑆}, { | ∈ }
(2.71) ⎨ 𝜂ˆ𝜉ˆ = 0 𝜆ˆ((⟨, ˆ⟩ − ˆ0) + 𝜉ˆ − 1) = 0 ∀ ∈ 𝑋 𝑆 ⎪⎩ ˆ ˆ (⟨, ˆ⟩ − ˆ0) + 𝜉 − 1 ≥ 0 𝜉 ≥ 0 Как и в предыдущем пункте, нахождение искомых наборов сводится к задаче минимизации выражения ∑︁ 𝜆ˆ((⟨, ˆ⟩ − ˆ0) + 𝜉ˆ − 1) + ∑︁ 𝜂ˆ𝜉ˆ 𝜆ˆ и 𝜂ˆ которое, с учетом условий (2.70), можно переписать, используя лишь переменные 𝜆ˆ и 𝜉ˆ: Download 1.93 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling