Summary_16_Galkina_Shramov (1185761)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Галкина Екатерина, Шрамов ГеоргийLecture 16: Learning: Support Vector MachinesВведениеМы уже изучили простые методы обучения, рассмотрели идею, основанную на строении мозга человека, обратились к проблеме фонологии и изучению концепций. Но сегоднямы вернёмся в самое начало и подумаем о том, как можно разделить пространство с помощью границ решений.Можно разделить пространство с помощью нейронной сети, метода ближайших соседей или распознающих деревьев.

Все эти идеи очень просты и часто срабатывают. Сегоднямы обратимся к изощрённой идее, у которой, тем не менее, существует простая реализация: метод опорных векторов. На примере этой идеи мы посмотрим, как она постепенноразвивалась, потому что такие алгоритмы не могут прийти в голову за один вечер.Есть несколько способов нарисовать границу решений для одной и той же задачи.В методе ближайших соседей она строится по срединным перпендикулярам, для распознающего дерева части границы всегда будут параллельны одной из осей, а нейроннаясеть может провести практически любую линию в зависимости от того, как она была обучена. На рисунке 1 приведён пример того, как эти алгоритмы решают одну и ту же задачу.Рис. 1: Разделение пространства с использованием различных алгоритмовОсновная идея методаРабота над разделением пространства с помощью границы решений велась на протяжении 50-75 лет, и казалось, что ничего нового уже нельзя придумать.

Но, ко всеобщемуудивлению, в начале 1990-х годов Владимир Вапник предложил новый метод.Рассмотрим пространство с положительными и отрицательными примерами. Мы хотим их отделить друг от друга прямой линией. Но какую именно линию нужно провести?Это можно сделать по-разному, но линия не должна лежать слишком близко к примерамиз одной группы.

Линия, показанная на рисунке 2, проведена так, чтобы между положительными и отрицательными примерами был максимальный зазор.1Теперь нам нужно понять, какое формальное правило соответствует этой границе.Пусть имеется вектор w произвольной ненулевой длины, перпендикулярный разделяющей прямой, и вектор u, обозначающий объект, подлежащий классификации. Мы хотимпонять, с какой стороны от разделяющей прямой находится этот вектор. Для этого намнеобходимо построить его проекцию на вектор w, потому что длина этой проекции будет показывать, насколько близко находится неизвестный объект к положительным илиотрицательным примерам.Рис.

2: Классификация методом опорных векторовТаким образом, нужно проверить условие w · u ≥ c, где c — некоторая константа. Мыполучили такое условие, потому что скалярное произведение двух векторов равно длинепроекции одного вектора на другой. Если это условие выполняется, объект классифицируется как положительный.Вывод уравненийДля удобства преобразуем полученное условие к виду:w·u−b≥0(1)Это и будет правилом, согласно которому будут классифицироваться объекты.

Здесь wи b неизвестны, но мы знаем, что вектор w должен быть перпендикулярным к разделяющейпрямой. Пока что у нас недостаточно ограничений, чтобы узнать точные значения этихпараметров.Для того, чтобы найти неизвестные, w и b, наложим дополнительные ограничения вследующем виде:w · x+ − b ≥ 1w · x− − b ≤ −1Здесь x+ — любой положительный пример, а x− — отрицательный. Эти уравнения означают, что объекты из разных классов должны быть отделены друг от друга зазором.Для удобства записи введём новую переменную yi , равную 1, если i-й объект являетсяположительным, и -1 в противном случае.

Умножив оба уравнения на yi , получим для2каждого примера одинаковое уравнение вида yi (w · xi − b) − 1 ≥ 0. Далее добавим дополнительные ограничения для объектов, которые лежат на границах зазора. Для них значениеэтого выражения должно быть равно нулю.

Получим следующую систему уравнений:(yi (w · xi − b) − 1 ≥ 0(2)yi (w · xi − b) − 1 = 0, xi ∈ gutterНашей финальной целью является нахождение прямой, разделяющий пространствотаким образом, чтобы между положительными и отрицательными примерами был максимальный зазор. Попробуем выразить размер этого зазора. Если бы мы знали единичнуюнормаль к разделяющей прямой, то это расстояние можно было бы выразить как скалярное произведение единичной нормали и разности векторов x+ и x− (см. рис.

3). Но,как было сказано выше, вектор w является нормалью, поэтому мы можем получить иединичную нормаль. Тогда выражение для ширины зазора принимает вид:W idth = (x+ − x− ) ·wkwkРаскрывая скобки и подставляя равенство из системы (2), получим следующие преобразования:W idth = (x+ − x− ) ·w112= (x+ · w − x− · w)= (1 + b − (b − 1))=kwkkwkkwkkwkРис. 3: Определение ширины зазораТаким образом, мы получили простое выражение для ширины зазора:W idth =2kwk(3)Нам нужно максимизировать это значение, или максимизировать значение kwk, но дляудобства дальнейших вычислений мы перейдём к эквивалентной задаче поиска минимального значения функции 21 kwk2 . Другими словами, необходимо найти решение следующейзадачи:(1kwk2 → min2(4)yi (w · xi − b) − 1 = 0, xi ∈ gutter3Для нахождения условного экстремума функции используется метод множителей Лагранжа, который позволяет получить новое выражение, для которого нужно будет найти экстремум, но уже без учёта ограничений.

Применив этот метод, задачу (4) можно свести кпоиску экстремума следующей функции:X1L = kwk2 −αi [yi (w · xi − b) − 1]2i(5)Суммирование ограничений ведётся по всем примерам из обучающей выборки, αi —некоторые константы. Для поиска экстремума функции возьмём частную производную поw и приравняем её к нулю:XX∂L=w−αi yi xi = 0 ⇐⇒ w =α i y i xi∂wii(6)Мы получили, что вектор w является линейной комбинацией векторов из обучающейвыборки. Некоторые из них в неё не войдут, поскольку для них коэффициент αi будетравен нулю.Далее подсчитаем частную производную по b:XX∂L=−αi yi = 0 ⇐⇒αi y i = 0∂bii(7)Подставим выражение, полученное для w в уравнении (6), в уравнение (5):!!!XXX1 Xα i y i xi ·α j y j xj −α i y i xi ·α j y j xj −L=2ijijXX−αi y i b +αiiiС учётом уравнения (7) получим, что третья сумма равно нулю.

Вторую сумму можнопредставить как произведение двух сумм, или как двойную сумму. Получим:L=Xαi −i1 XXαi αj yi yj xi · xj2 i j(8)Таким образом, нам удалось упростить исходное выражение (5). Далее решение экстремальной задачи (8) можно найти с помощью численных методов. Мы проделали этиупрощения для того, чтобы понять, как зависит поиск экстремума от векторов из обучающей выборки, и выяснили, что в результирующее выражение входит только скалярноепроизведение этих векторов.Далее подставим выражение (6) для w в правило (1):Xα i y i xi · u + b ≥ 0(9)iЕсли выполняется условие (9), то неизвестный объект классифицируется как положительный.

Заметим, что это условие также зависит только от скалярного произведениявекторов.4Случай линейной неразделимости множествВ случае, если множества из обучающей выборки линейно неразделимы, алгоритмбудет работать с ошибкой даже на объектах этой выборки.Эта проблема решается переходом в новое пространство, в котором множества можнобудет линейно разделить. Пусть переход к новому пространству задаётся отображениемφ(x).Ранее было сказано, что функция, которую нужно максимизировать, зависит только от скалярного произведения векторов из обучающей выборки.

То же самое верно идля правила, используемого для классификации. После трансформации пространства ввыражения 8 и 9 будут входить множители φ(xi ) · φ(xj ) и φ(xi ) · φ(u). Поэтому для решения задачи нам не нужно знать само отображение φ(x), а достаточно задать функциюK(xi , xj ) = φ(xi ) · φ(xj ). Такая функция называется ядром. На практике чаще всего используются следующие ядра:1.

Полиномиальное ядро K(x, y) = (x · y + 1)n ;2. Радиальная базисная функция K(x, y) = e−kx−ykσ.Теперь у нас есть обобщённый метод, который работает на выпуклых множествах,поэтому всегда может найти глобальный экстремум. Конечно, этот метод не лишён недостатков. В частности, если в качестве ядра выбрать радиальную базисную функцию сдостаточно малым значением параметра σ, то проявится проблема переобучения.Историческая справкаПриведём краткую историю создания метода опорных векторов. Создаётся впечатление, что эта идея гораздо новее того, что мы уже изучили.Владимир Вапник иммигрировал из СССР в США примерно в 1991 году.

Никто доэтого не слышал об идее опорных векторов, но он работал над этим методом ещё в рамках своей кандидатской диссертации в начале 1960-х в Московском Институте проблемуправления.Для реализации метода в то время не хватало вычислительной мощности, поэтомуследующие 25 лет Вапник работал над прикладными проблемами онкологии в одном изинститутов СССР. О нём узнали в Bell Labs и пригласили работать в США, куда онвпоследствии иммигрировал.В 1992 году Вапник предлагает к публикации три статьи в журнал NIPS (NeuralInformation Processing Systems), и все они были отклонены.В 1993 году Bell Labs в заинтересовываются проблемой распознавания рукописноговвода и нейронными сетями.

Вапник считал, что нейронные сети не очень хорошо покажутсебя в этом, поэтому поспорил со своим коллегой, что метод опорных векторов сработаетлучше. В итоге коллега, который как раз работал над распознаванием рукописного ввода,решается попробовать метод опорных векторов с полиномиальным ядром при n = 2, малоотличающийся от линейного, и он работает как по волшебству.Использовали ли тогда ядро впервые? Эта идея появлялась ещё в диссертации Вапника, но он не придавал ей значения.

Но как только эта идея сработала на задаче распознавания почерка, он оживил её и начал развивать, и в итоге она стала существенной частьювсего метода опорных векторов.Главная мысль заключается в том, что между концепцией идеи и моментом, когдао ней кто-то услышал, прошло около 30 лет. И так случается довольно часто: великиеидеи появляются, затем о них надолго забывают, а потом случается переломный момент,когда исходная идея, лишь немного изменённая, приобретает огромную мощь.

А Вапник,5о котором никто не слышал до начала 1990-х, стал знаменит благодаря идее, о которойсейчас знают все, кто интересуется машинным обучением.6.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций