машинное обучение. А. М. Миронов Московский Государственный Университет Механикоматематический факультет Кафедра математической теории интеллектуальных систем Введение Книга
 Скачать 1.05 Mb.
|
|
−𝑣𝑢 0 ¯ 0 = 𝜋 2 , поэтому ¯ 0 ∈ 𝑃 . Вектор, определяемый отрезком [−𝑣, 𝑢 0 ], т.е. 𝑢 0 − (−𝑣) = 𝑢 0 + 𝑣, ортогонален 𝑃 и принадлежит 𝑍, поэтому 𝑍 = {𝑥 ∈ R 𝑚+1 | ⟨𝑢 0 + 𝑣, 𝑥⟩ ≥ 0} и в качестве искомого вектора 𝜆 * можно взять 𝑢 0 + 𝑣. Продолжим доказательство теоремы Каруша-Куна-Таккера. Пусть вектор 𝜆 * , обладающий свойством (2.54), имеет вид (𝜆 * 0 , . . . , 𝜆 * 𝑚 ). 1. Докажем, что ∀ 𝑖 = 0, . . . , 𝑚 𝜆 * 𝑖 ≥ 0. Поскольку Λ содержит вектора 𝜆 (0) = (1, 0, . . . , 0) и 𝜆 (𝑖) = (𝜀, 0 . . . , 0, 1, 0, . . . , 0) (∀ 𝑖 = 1, . . . , 𝑚) где 𝜀 > 0, и единица в 𝜆 (𝑖) стоит в позиции номер 𝑖 (мы считаем, что первая позиция в 𝜆 (𝑖) имеет номер 0), то из (2.54) следует, что ⟨𝜆 * , 𝜆 (0) ⟩ = 𝜆 * 0 ≥ 0 ∀ 𝑖 = 1, . . . , 𝑚 ⟨𝜆 * , 𝜆 (𝑖) ⟩ = 𝜆 * 0 𝜀 + 𝜆 * 𝑖 ≥ 0 откуда, ввиду произвольности 𝜀, заключаем, что 𝜆 * 𝑖 ≥ 0. 2. Докажем, что ∀ 𝑖 ∈ {1, . . . , 𝑚} 𝜆 * 𝑖 𝑔 𝑖 (ˆ 𝑥) = 0. (2.56) Т.к. ∀ 𝜀 > 0 множество Λ содержит вектор 𝜆 def = (𝜀, 0, . . . , 0, 𝑔 𝑖 (ˆ 𝑥), 0, . . . , 0), то из (2.54) следует, что ⟨𝜆 * , 𝜆⟩ = 𝜆 * 0 𝜀 + 𝜆 * 𝑖 𝑔 𝑖 (ˆ 𝑥) ≥ 0, откуда, ввиду произвольности 𝜀, заключаем, что 𝜆 * 𝑖 𝑔 𝑖 (ˆ 𝑥) ≥ 0. Таким образом, либо 𝜆 * 𝑖 𝑔 𝑖 (ˆ 𝑥) = 0, либо 𝜆 * 𝑖 𝑔 𝑖 (ˆ 𝑥) > 0. Однако если бы было верно неравенство 𝜆 * 𝑖 𝑔 𝑖 (ˆ 𝑥) > 0, то, учитывая доказанное в предыдущем пункте неравенство 𝜆 * 𝑖 ≥ 0, заключаем, что 𝑔 𝑖 (ˆ 𝑥) > 0, что противоречит условию 𝑔 𝑖 (ˆ 𝑥) ≤ 0. 42 3. Докажем, что ∀ 𝑥 ∈ R 𝑛 𝜆 * 0 𝑓 (ˆ 𝑥) + 𝑚 ∑︁ 𝑖=1 𝜆 * 𝑖 𝑔 𝑖 (ˆ 𝑥) ≤ 𝜆 * 0 𝑓 (𝑥) + 𝑚 ∑︁ 𝑖=1 𝜆 * 𝑖 𝑔 𝑖 (𝑥). (2.57) Из (2.56) следует, что левая часть (2.57) равна 𝜆 * 0 𝑓 (ˆ 𝑥). Т.к. ∀ 𝜀 > 0 множество Λ содержит вектор 𝜆 def = (𝑓 (𝑥) − 𝑓 (ˆ 𝑥) + 𝜀, 𝑔 1 (𝑥), . . . , 𝑔 𝑚 (𝑥)), то из (2.54) следует, что ⟨𝜆 * , 𝜆⟩ = 𝜆 * 0 (𝑓 (𝑥) − 𝑓 (ˆ 𝑥) + 𝜀) + 𝑚 ∑︁ 𝑖=1 𝜆 * 𝑖 𝑔 𝑖 (𝑥) ≥ 0, откуда, ввиду произвольности 𝜀, следует (2.57). 4. Докажем, что 𝜆 * 0 ̸= 0. Если 𝜆 * 0 = 0, то из 𝜆 * ̸= ¯ 0 следует, что ∃ 𝑖 ∈ {1, . . . , 𝑚} : 𝜆 * 𝑖 > 0. По предположению, для некоторого 𝑥 ∈ R выполнено условие (2.44). Для этого 𝑥 верно также (2.57), однако в данном случае левая часть (2.57) равна 0, а правая часть (2.57) меньше 0, что невозможно. Искомые значения ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 определяются как 𝜆 * 1 𝜆 * 0 , . . . , 𝜆 * 𝑚 𝜆 * 0 Истинность каждого из трех соотношений в (2.47) следует из соот- ветствующих пунктов изложенного выше рассуждения. Докажем, что если функции 𝑓, 𝑔 1 , . . . , 𝑔 𝑚 дифференцируемые, то тре- тье соотношение в (2.47) равносильно соотношению (2.48), т.е. 𝐿(ˆ 𝑥, ˆ 𝜆) = min 𝑥∈R 𝑛 𝐿(𝑥, ˆ 𝜆) ⇔ ∀ 𝑖 = 1, . . . , 𝑛 𝜕𝐿 𝜕𝑥 𝑖 (ˆ 𝑥, ˆ 𝜆) = 0, (2.58) где ˆ 𝜆 = (ˆ 𝜆 1 . . . , ˆ 𝜆 𝑚 ). Импликация «⇒» в (2.58) верна потому, что ее правая часть является необходимым условием минимума дифференцируемой функции. Обоснуем импликацию «⇐» в (2.58). Из выпуклости 𝑓, 𝑔 1 , . . . , 𝑔 𝑚 и неотрицательности ˆ 𝜆 1 , . . ., ˆ 𝜆 𝑚 следует выпуклость функции 𝑥 ↦→ 𝐿(𝑥, ˆ 𝜆): ∀ 𝑥, 𝑥 ′ ∈ R 𝑛 , ∀ 𝛼 ∈ [0, 1] 𝐿(𝛼𝑥 + (1 − 𝛼)𝑥 ′ , ˆ 𝜆) = = 𝑓 (𝛼𝑥 + (1 − 𝛼)𝑥 ′ ) + 𝑚 ∑︀ 𝑖=1 ˆ 𝜆 𝑖 𝑔 𝑖 (𝛼𝑥 + (1 − 𝛼)𝑥 ′ ) ≤ ≤ 𝛼𝑓 (𝑥) + (1 − 𝛼)𝑓 (𝑥 ′ ) + 𝑚 ∑︀ 𝑖=1 ˆ 𝜆 𝑖 (𝛼𝑔 𝑖 (𝑥) + (1 − 𝛼)𝑔 𝑖 (𝑥 ′ )) = = 𝛼𝐿(𝑥, ˆ 𝜆) + (1 − 𝛼)𝐿(𝑥 ′ , ˆ 𝜆), 43 откуда на основании такого же рассуждения, которое приведено в конце пункта 2.3.2, следует, что значение аргумента ˆ 𝑥, удовлетворяющее пра- вой части (2.58), является глобальным минимумом этой функции. Применение метода Применим изложенный выше метод к оптимизационной задаче (2.42) при условиях (2.41). В данном случае ∙ целевая функция 𝑓 имеет вид ||𝑤|| 2 2 , и ∙ условия являются линейными неравенствами 𝑦 𝑥 (⟨𝑥, 𝑤⟩ − 𝑤 0 ) − 1 ≥ 0, где 𝑥 ∈ 𝑋 𝑆 (2.59) Докажем, что целевая функция выпукла. Данная функция является суперпозицией трех функций: функции 𝑤 ↦→ ||𝑤||, функции 𝑥 ↦→ 𝑥 2 , и функции 𝑥 ↦→ 1 2 𝑥. Эти функции выпуклы, т.к. ∙ выпуклость функции 𝑤 ↦→ ||𝑤|| следует из неравенства треуголь- ника (||𝑎 + 𝑏|| ≤ ||𝑎|| + ||𝑏||) для нормы в произвольном векторном пространстве: ∀ 𝑤, 𝑤 ′ ∈ R 𝑛 , ∀ 𝛼 ∈ [0, 1] ||𝛼𝑤 + (1 − 𝛼)𝑤 ′ || ≤ ||𝛼𝑤|| + ||(1 − 𝛼)𝑤 ′ || = 𝛼||𝑤|| + (1 − 𝛼)||𝑤 ′ ||, ∙ выпуклость функции 𝑥 ↦→ 𝑥 2 обосновывается следующим образом: ∀ 𝑥, 𝑥 ′ ∈ R, ∀ 𝛼 ∈ [0, 1] требуемое неравенство (𝛼𝑥 + (1 − 𝛼)𝑥 ′ ) 2 ≤ 𝛼𝑥 2 + (1 − 𝛼)(𝑥 ′ ) 2 после раскрытия скобок, перегруппировки слагаемых и приведения подобных членов преобразуется в эквивалентное неравенство 𝛼 2 (𝑥 − 𝑥 ′ ) 2 ≤ 𝛼(𝑥 − 𝑥 ′ ) 2 которое верно потому, что 𝛼 ∈ [0, 1], ∙ функция 𝑥 ↦→ 1 2 𝑥 выпукла потому, что любая линейная функция является выпуклой. Нетрудно доказать, что если функции 𝑓 : R 𝑛 → R и 𝑔 : R → R выпуклы и, кроме того, 𝑔 монотонно неубывающая, то их суперпозиция (𝑔 ∘ 𝑓 ) тоже выпукла. Действительно, ∀ 𝑥, 𝑥 ′ ∈ R 𝑛 , ∀ 𝛼 ∈ [0, 1] (𝑔 ∘ 𝑓 )(𝛼𝑥 + (1 − 𝛼)𝑥 ′ ) = 𝑔(𝑓 (𝛼𝑥 + (1 − 𝛼)𝑥 ′ )) ≤ ≤ 𝑔(𝛼𝑓 (𝑥) + (1 − 𝛼)𝑓 (𝑥 ′ )) ≤ 𝛼𝑔(𝑓 (𝑥)) + (1 − 𝛼)𝑔(𝑓 (𝑥 ′ )) = = 𝛼(𝑔 ∘ 𝑓 )(𝑥) + (1 − 𝛼)(𝑔 ∘ 𝑓 )(𝑥 ′ ). 44 Поскольку функции 𝑥 ↦→ 𝑥 2 и 𝑥 ↦→ 1 2 𝑥 : R → R – выпуклы и монотонно неубывающие, то, следовательно их суперпозиция с выпуклой функцией 𝑤 ↦→ ||𝑤||, т.е. функция 𝑤 ↦→ 1 2 ||𝑤|| 2 тоже выпукла. Функция Лагранжа для данной задачи имеет вид 𝐿 = ||𝑤|| 2 2 − ∑︁ 𝑥∈𝑋 𝑆 𝜆 𝑥 (𝑦 𝑥 (⟨𝑥, 𝑤⟩ − 𝑤 0 ) − 1), (2.60) и соотношение (2.48) имеет следующий вид: ∀ 𝑖 = 1, . . . , 𝑛 ˆ 𝑤 𝑖 − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 𝑥 𝑖 = 0, 0 − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 (−1) = 0, что можно переписать в виде ˆ 𝑤 = ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 𝑥, ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 = 0. (2.61) Из теоремы 3 следует, что исходная задача сводится к задаче поиска вектора ˆ 𝑤, числа ˆ 𝑤 0 , и набора чисел ˆ 𝜆 = {ˆ 𝜆 𝑥 ≥ 0 | 𝑥 ∈ 𝑋 𝑆 }, удовлетво- ряющих соотношениям в (2.61) и условию ∀ 𝑥 ∈ 𝑋 𝑆 {︂ 𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) − 1 ≥ 0 ˆ 𝜆 𝑥 (𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) − 1) = 0. (2.62) Теорема 4. Задача нахождения объектов ˆ 𝑤, ˆ 𝑤 0 , и ˆ 𝜆 = {ˆ 𝜆 𝑥 ≥ 0 | 𝑥 ∈ 𝑋 𝑆 }, удовле- творяющих соотношениям (2.61) и (2.62), сводится к задаче нахождения объектов ˆ 𝑤, ˆ 𝑤 0 , и ˆ 𝜆, минимизирующих значения выражения ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 (𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) − 1) (2.63) при условиях ⎧ ⎪ ⎨ ⎪ ⎩ ˆ 𝑤 = ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 𝑥, ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 = 0, ∀ 𝑥 ∈ 𝑋 𝑆 {︂ ˆ 𝜆 𝑥 ≥ 0 𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) − 1 ≥ 0. (2.64) Доказательство. 1. Пусть объекты ˆ 𝑤, ˆ 𝑤 0 , и ˆ 𝜆 = {ˆ 𝜆 𝑥 ≥ 0 | 𝑥 ∈ 𝑋 𝑆 } удовлетворяют соотношениям (2.61) и (2.62). Тогда при их подстановке вместо со- ответствующих объектов в (2.63) и (2.64) получаем, что 45 ∙ значение суммы (2.63) будет равно 0 (т.к., согласно второму равенству в (2.62), каждое слагаемое в этой сумме равно 0), и ∙ соотношения в (2.64) верны, это следует из (2.61) и (2.62). С другой стороны, сумма (2.63) при условиях (2.64), не может быть меньше 0, т.к., согласно этим условиям, каждое ее слагаемое явля- ется произведением неотрицательных чисел. Таким образом, объекты ˆ 𝑤, ˆ 𝑤 0 , и ˆ 𝜆 = {ˆ 𝜆 𝑥 ≥ 0 | 𝑥 ∈ 𝑋 𝑆 } – решение задачи минимизации суммы (2.63) при условиях (2.64). 2. Согласно условиям (2.64), каждое слагаемое в сумме (2.63) при этих условиях неотрицательно, т.е. сумма (2.63) неотрицательна, и ∙ если минимальное значение этой суммы равно 0, то каждое слагаемое в этой сумме равно 0, т.е. объекты ˆ 𝑤, ˆ 𝑤 0 , и ˆ 𝜆, реша- ющие задачу минимизации (2.63) при условиях (2.64), удовле- творяют соотношениям (2.61) и (2.62), и ∙ если минимальное значение этой суммы больше 0, то тогда решение задачи нахождения ˆ 𝑤, ˆ 𝑤 0 , и ˆ 𝜆 = {ˆ 𝜆 𝑥 ≥ 0 | 𝑥 ∈ 𝑋 𝑆 }, удовлетворяющих соотношениям (2.61) и (2.62), не существует (что по предположению невозможно). Перепишем сумму (2.63) путем раскрытия скобок, перегруппировки слагаемых и использования линейности скалярного произведения: ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 ⟨𝑥, ˆ 𝑤⟩ − ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 ˆ 𝑤 0 − ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 = = ∑︀ 𝑥∈𝑋 𝑆 ⟨ˆ 𝜆 𝑥 𝑦 𝑥 𝑥, ˆ 𝑤⟩ − ( ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 ) ˆ 𝑤 0 − ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 = = ⟨ ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 𝑥, ˆ 𝑤⟩ − ( ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 ) ˆ 𝑤 0 − ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 (2.65) Из условий (2.64) следует, что (2.65) можно переписать в виде ⟨ ˆ 𝑤, ˆ 𝑤⟩ − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 = || ˆ 𝑤|| 2 − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 (2.66) Выражение (2.66) можно переписать, используя лишь переменные ˆ 𝜆 𝑥 : ∑︁ 𝑥,𝑥 ′ ∈𝑋 𝑆 ˆ 𝜆 𝑥 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 𝑦 𝑥 ′ ⟨𝑥, 𝑥 ′ ⟩ − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 (2.67) Таким образом, исходная задача свелась к задаче нахождения набора ˆ 𝜆 = {ˆ 𝜆 𝑥 | 𝑥 ∈ 𝑋 𝑆 } 46 минимизирующего значение выражения (2.67), при условиях ∀ 𝑥 ∈ 𝑋 𝑆 ˆ 𝜆 𝑥 ≥ 0, ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 = 0. Такая задача называется задачей квадратичного программиро- вания (ЗКП). Существует много алгоритмов решения этой задачи. Искомый вектор ˆ 𝑤 вычисляется по найденному решению ˆ 𝜆 данной ЗКП согласно первому равенству в (2.64). Для вычисления искомого ˆ 𝑤 0 выбирается такая пара 𝑥 ∈ 𝑋 𝑆 , что ˆ 𝜆 𝑥 ̸= 0, в этом случае, согласно второму равенству в (2.62), должно быть верно равенство 𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) − 1 = 0, из которого следует, что ˆ 𝑤 0 = ⟨𝑥, ˆ 𝑤⟩ − 𝑦 𝑥 Если данная ЗКП имеет не единственное решение, то среди всех этих ре- шений выбирается такое, что число ˆ 𝑤 0 , вычисленное по этому решению, удовлетворяет последнему неравенству в (2.64). Обоснуем, почему ∃ 𝑥 ∈ 𝑋 𝑆 : ˆ 𝜆 𝑥 ̸= 0. Если бы все числа ˆ 𝜆 𝑥 были равны 0, то ˆ 𝑤 – нулевой вектор, и из последнего неравенства в (2.64) следует, что ∀ 𝑥 ∈ 𝑋 𝑆 − 𝑦 𝑥 ˆ 𝑤 0 − 1 ≥ 0, или −𝑦 𝑥 ˆ 𝑤 0 ≥ 1. Выборка 𝑆 предполагается нетривиальной, т.е. 𝑦 𝑥 м.б. равно как 1, так и −1, откуда следует, что ˆ 𝑤 0 ≥ 1 и − ˆ 𝑤 0 ≥ 1, что невозможно. 2.5.3 Построение оптимальной разделяющей гипер- плоскости по зашумленной выборке В некоторых случаях выборка 𝑆 ⊆ R 𝑛 × {−1, 1} бывает зашумленной, т.е. значения компонентов векторов в 𝑆, представляющих объекты, могут немного отличаться от истинных значений. Также в 𝑆 м.б. и ошибочно размеченные пары, т.е. пары (𝑥, 𝑦 𝑥 ) с неверным значением 𝑦 𝑥 . Это мо- жет привести к тому, что выборка 𝑆 не будет линейно разделимой, т.е. невозможно найти АФ 𝑎 𝑆 вида 𝑎 𝑆 (𝑥) = 𝑠𝑖𝑔𝑛 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ (2.68) такую, что 𝑄(𝑎 𝑆 ) = 0. Тем не менее, иногда в ситуации зашумленности и линейной неразделимости выборки 𝑆 все равно имеет смысл искать АФ 𝑎 𝑆 вида (2.68), допуская при этом небольшие ошибки классификации. 47 Один из подходов к построению АФ 𝑎 𝑆 такого вида называется ме- тодом наименьших квадратов, он будет рассмотрен в следующем параграфе. Данный подход заключается в том, чтобы найти АФ 𝑎 𝑆 вида (2.68) с наименьшим значением 𝑄(𝑎 𝑆 ), где 𝑄(𝑎 𝑆 ) = ∑︁ 𝑥∈𝑋 𝑆 (𝑎 𝑆 (𝑥) − 𝑦 𝑥 ) 2 Другой подход является развитием подхода, изложенного в преды- дущем пункте. Он заключается в том, чтобы построить разделяющую полосу максимальной ширины, допуская при этом попадание некоторых объектов не в свое полупространство. Напомним, что если границами разделяющей полосы являются ги- перплоскости, определяемые уравнениями ⟨𝑥, 𝑤⟩ − 𝑤 0 = 1, ⟨𝑥, 𝑤⟩ − 𝑤 0 = −1, то ∀ 𝑥 ∈ 𝑋 𝑆 точка 𝑥 попадает в свое полупространство, если 𝑀 𝑥 ≥ 1, где 𝑀 𝑥 def = 𝑦 𝑥 (⟨𝑥, 𝑤⟩ − 𝑤 0 ). Для адекватного определения целевой функции введем набор 𝜉 до- полнительных переменных: 𝜉 = {𝜉 𝑥 | 𝑥 ∈ 𝑋 𝑆 }, где ∀ 𝑥 ∈ 𝑋 𝑆 значение переменной 𝜉 𝑥 будем понимать как величину ошиб- ки аппроксимации на объекте 𝑥: она должна примерно соответствовать расстоянию от 𝑥 до своего полупространства, когда 𝑥 находится не в сво- ем полупространстве (т.е. 𝑀 𝑥 < 1). Например, величину ошибки в этом случае можно определить как 1 − 𝑀 𝑥 Задача построения оптимальной разделяющей полосы в данной си- туации имеет вид минимизации целевой функции ||𝑤|| 2 2 + 𝑐 ∑︁ 𝑥∈𝑋 𝑆 𝜉 𝑥 (где 𝑐 – некоторая константа) (2.69) при условиях ∀ 𝑥 ∈ 𝑋 𝑆 𝜉 𝑥 ≥ 1 − 𝑀 𝑥 , 𝜉 𝑥 ≥ 0 Целевая функция (2.69) выражает следующие требования: ∙ разделяющая полоса должна быть пошире (т.е. значение ||𝑤|| долж- но быть поменьше), ∙ суммарная ошибка ∑︀ 𝑥∈𝑋 𝑆 𝜉 𝑥 должна быть поменьше. 48 Константа 𝑐 позволяет регулировать баланс между требованиями ∙ максимизации ширины разделяющей полосы, и ∙ минимизации суммарной ошибки. Обычно ее выбирают методом скользящего контроля: ∙ сначала задача решается при некотором 𝑐, ∙ затем из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки (такие объекты будут считаться или чрезмерно зашумленными, или ошибочно размеченными), а 𝑐 изме- няется следующим образом: – если ширина полосы получилась слишком маленькая, то 𝑐 уме- ньшается (это приведет к увеличению ширины полосы), – если слишком много объектов находятся далеко от своего по- лупространства, то 𝑐 увеличивается (полоса станет уже), и ∙ после этого задача решается заново (с новыми 𝑆 и 𝑐). Возможно, придется проделать несколько таких итераций. Функция Лагранжа для данной задачи имеет вид 𝐿 = ||𝑤|| 2 2 + 𝑐 ∑︁ 𝑥∈𝑋 𝑆 𝜉 𝑥 − ∑︁ 𝑥∈𝑋 𝑆 𝜆 𝑥 (𝑀 𝑥 + 𝜉 𝑥 − 1) − ∑︁ 𝑥∈𝑋 𝑆 𝜂 𝑥 𝜉 𝑥 , и соотношение (2.48) имеет следующий вид: ∙ ∀ 𝑖 = 1, . . . , 𝑛 𝜕𝐿 𝜕𝑤 𝑖 ( ˆ 𝑤, ˆ 𝜆, ˆ 𝜉) = ˆ 𝑤 𝑖 − ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 𝑥 𝑖 = 0, ∙ 𝜕𝐿 𝜕𝑤 0 ( ˆ 𝑤, ˆ 𝜆, ˆ 𝜉) = ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 = 0, ∙ ∀ 𝑥 ∈ 𝑋 𝑆 𝜕𝐿 𝜕𝜉 𝑥 ( ˆ 𝑤, ˆ 𝜆, ˆ 𝜉) = 𝑐 − ˆ 𝜆 𝑥 − ˆ 𝜂 𝑥 = 0, что можно переписать в виде ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ ˆ 𝑤 = ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 𝑥, ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 = 0, ∀ 𝑥 ∈ 𝑋 𝑆 ˆ 𝜆 𝑥 + ˆ 𝜂 𝑥 = 𝑐. (2.70) 49 Из теоремы Каруша-Куна-Таккера следует, что исходная задача сво- дится к задаче поиска наборов чисел ˆ 𝜆 = {ˆ 𝜆 𝑥 ≥ 0 | 𝑥 ∈ 𝑋 𝑆 }, ˆ 𝜂 = {ˆ 𝜂 𝑥 ≥ 0 | 𝑥 ∈ 𝑋 𝑆 }, а также вектора ˆ 𝑤, числа ˆ 𝑤 0 , и набора чисел {𝜉 𝑥 | 𝑥 ∈ 𝑋 𝑆 }, удовлетво- ряющих равенствам (2.70) и условию ∀ 𝑥 ∈ 𝑋 𝑆 ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ ˆ 𝜆 𝑥 (𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) + ˆ 𝜉 𝑥 − 1) = 0 ˆ 𝜂 𝑥 ˆ 𝜉 𝑥 = 0 𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) + ˆ 𝜉 𝑥 − 1 ≥ 0 ˆ 𝜉 𝑥 ≥ 0 (2.71) Как и в предыдущем пункте, нахождение искомых наборов ˆ 𝜆 и ˆ 𝜂 сводится к задаче минимизации выражения ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 (𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ) + ˆ 𝜉 𝑥 − 1) + ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜂 𝑥 ˆ 𝜉 𝑥 которое, с учетом условий (2.70), можно переписать, используя лишь переменные ˆ 𝜆 𝑥 и ˆ 𝜉 𝑥 : ∑︁ 𝑥,𝑥 ′ ∈𝑋 𝑆 ˆ 𝜆 𝑥 ˆ 𝜆 𝑥 ′ 𝑦 𝑥 𝑦 𝑥 ′ ⟨𝑥, 𝑥 ′ ⟩ − ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 + 𝑐 ∑︁ 𝑥∈𝑋 𝑆 ˆ 𝜉 𝑥 (2.72) Нетрудно установить, что исходная задача, рассматриваемая в насто- ящем пункте, сводится к задаче минимизации (2.72) с условиями ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ ∑︀ 𝑥∈𝑋 𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 = 0, ∀ 𝑥 ∈ 𝑋 𝑆 {︂ 0 ≤ ˆ 𝜆 𝑥 ≤ 𝑐, ˆ 𝜉 𝑥 ≥ 0, 𝑀 𝑥 + ˆ 𝜉 𝑥 − 1 ≥ 0, (2.73) где 𝑀 𝑥 def = 𝑦 𝑥 (⟨𝑥, ˆ 𝑤⟩ − ˆ 𝑤 0 ), ˆ 𝑤 def = ∑︀ (𝑥,𝑦 𝑥 )∈𝑆 ˆ 𝜆 𝑥 𝑦 𝑥 𝑥. Эта задача – тоже ЗКП. В результате ее решения получаются опти- мальные ˆ 𝜆, ˆ 𝜉, ˆ 𝑤 0 , по которым можно вычислить оптимальные ˆ 𝑤 и ˆ 𝜂. Отметим некоторые особенности оптимального решения ˆ 𝜆, ˆ 𝜂, ˆ 𝜉, ˆ 𝑤, ˆ 𝑤 0 исходной задачи. ∀ 𝑥 ∈ 𝑋 𝑆 вектор 𝑥 относится к одному из трех классов, в зависимости от значения 𝑀 𝑥 : ∙ если 𝑀 𝑥 > 1, то 𝑥 находится в своем полупространстве, но не на его границе (такой вектор называется периферийным), 50 |