[Перевод] Учебное пособие по методу опорных векторов (SVM)

искусственный интеллект

Учебное пособие по методу опорных векторов (SVM)

Изучение SVM на примерах

существуетStatsbotСообщение о командеОбнаружение аномалий временных рядовПосле нашего поста многие читатели попросили нас рассказать им о подходе SVM. Пришло время познакомить вас с SVM без сложной математики и поделиться полезными библиотеками и ресурсами, которые помогут вам начать работу.

Если вы использовали машинное обучение для выполнения классификации, вы, вероятно, слышалиМетоды опорных векторов (SVM). Представленные более 50 лет назад, они со временем эволюционировали и были адаптированы к различным другим проблемам, таким какРегрессионный анализ, анализ выбросовиранжирование.

SVM — лучший инструмент для многих специалистов по машинному обучению. существует[24]7, мы также используем их для решения различных задач.

В этом посте мы постараемся глубже понять, как работают SVM. Я бы сосредоточился на развитии интуиции, а не на стремлении к строгости. По сути, это означает, что мы пропустим как можно больше математики и создадим интуитивное понимание того, как все работает.

проблема классификации

Предположим, ваш университет предлагает курсы машинного обучения (МО). Преподаватели курса заметили, что учащиеся получат наибольшую пользу, если будут хороши в математике или статистике. Со временем они зафиксировали баллы принятых студентов по этим предметам. Кроме того, у каждого из этих студентов есть метка, описывающая, насколько они «хорошо» или «плохо» справились с курсом машинного обучения.

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

Что случится? Давайте начнем с представления данных, которые у них есть. Мы можем нарисовать двухмерный график, на одной оси которого представлены математические оценки, а на другой — статистические. Учащиеся с определенным баллом отображаются в виде точки на графике.

Цвет точек — зеленый или красный — представляет его успеваемость в классе машинного обучения: «хорошо» или «плохо» соответственно.

Нарисованный график может выглядеть так:

Когда ученица подает заявку на зачисление, наш учитель просит ее предоставить свои баллы по математике и статистике. Основываясь на имеющихся у них данных, они делают обоснованные предположения о том, как они поведут себя на курсе машинного обучения.

По сути, нам нужен какой-то «алгоритм», в котором вы можете ввести «кортеж оценок» таблицы (math_score, статистика_score). Он сообщит вам, является ли конкретный ученик красной или зеленой точкой на графике (красная/зеленая также может называтьсясвоего родаилиЭтикетка). Конечно, алгоритм каким-то образом воплощает шаблоны, существующие в уже имеющихся у нас данных, также известные кактренировочные данные.

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

Прямая линия здесь нашаразделительная граница(потому что он разделяет вкладки) илиКлассификатор(Мы используем его для классификации точек). На рисунке показаны оба возможных классификатора для нашей задачи.

хорошие и плохие классификаторы

Вот интересный вопрос: обе строки выше могут разделять красный и зеленый наборы данных. Есть ли у нас веская причина предпочесть одно другому?

Помните, что ценность классификатора не в том, как он различает обучающие данные. В конечном итоге мы хотим, чтобы он классифицировал точки данных, которые еще не были просмотрены (называемыеТестовые данные). Учитывая это, мы хотим выбрать линию, которая захватываетосновной режим, так что есть большая вероятность, что он будет хорошо работать на тестовых данных.

Первая строка выше выглядит немного «наклонной». В нижней половине он кажется слишком близким к набору данных цвета красных точек, а в верхней половине он слишком близок к набору данных зеленого цвета. Конечно, он идеально разделяет обучающие данные, но если тестовые точки будут немного дальше от набора данных, то, скорее всего, он получит неправильную метку.

На второй прямой такой проблемы нет. Например, взгляните на контрольные точки, показанные в виде квадратов на изображении ниже, и на метки, назначенные классификатором.

Вторая строка находится как можно дальше от двух наборов данных, сохраняя при этом правильное разделение обучающих данных. Он проходит через середину двух наборов данных, он менее «рискованный» и может дать каждому классу некоторое пространство для размещения распределения данных, что делает его подходящим для тестовых данных.

SVM пытается найти эту вторую строку. Мы выбрали лучший классификатор визуально, но нам нужно более точно определить лежащий в его основе принцип, чтобы применить его в целом. Вот упрощенная версия SVM:

  1. Найдите строку, которая правильно классифицирует обучающие данные.
  2. Из всех этих линий выберите ту, которая находится дальше всего от ближайшей точки.

Ближайшие к прямой точки называютсяопорные векторы. Область, которую они определяют вокруг этой линии, называетсяинтервал (маржа).

Ниже показаны опорные векторы для второй линии: точки с черными краями (их два) и пробелы (заштрихованные области).

Машины опорных векторов дают вам возможность выбирать между множеством возможных классификаторов, чтобы убедиться, что тестовые данные помечены с более высокой степенью правильности. Этот метод очень прост, не так ли?

Хотя на рисунке выше показаны линия и данные в двумерном пространстве, следует отметить, что SVM могут работать в любом количестве измерений, в этих измерениях они находят аналогию для двумерной линии.

Например, в трехмерном пространстве ищутсамолет(мы скоро увидим пример этого), а в более высоких измерениях они ищутгиперплоскость- Обобщение 2D-линий и 3D-плоскостей на любое количество измерений.

Данные, которые можно разделить прямой линией (или обычно гиперплоскостью), называютсялинейно отделимыйданные. гиперплоскость действует каклинейный классификатор.

Отказоустойчивость

В предыдущем разделе мы рассмотрели простой случай идеально линейно разделимых данных. Однако реальные данные часто бывают беспорядочными. Вы почти всегда будете сталкиваться с некоторыми экземплярами, которые линейный классификатор не сможет правильно разделить.

Ниже приведен пример таких данных:

Очевидно, что если мы используем линейный классификатор, мы никогда не сможем полностью разделить метки. Мы также не хотим полностью отказываться от линейного классификатора, так как он кажется хорошим решением проблемы, за исключением нескольких неправильных моментов.

Как SVM справляется с этим? Они позволяют указать количество ошибок, которые вы готовы допустить.

Вы можете предоставить SVM параметр с именем "C", это позволит вам найти компромисс между:

  1. Есть большие пробелы.
  2. правильная классификациятренироватьсяданные. Более высокое значение C означает, что вы хотите меньше ошибок в своих обучающих данных.

Стоит повторить, что этокомпромиссМетод. ты сможешьСтоимостьдиапазон, чтобы выбрать лучший классификатор для обучающих данных.

На приведенном ниже графике показано, как классификатор и интервал изменяются по мере увеличения значения C (векторы поддержки не показаны):

Обратите внимание, как линия «искажается», когда мы увеличиваем значение C. При высоких значениях он пытается разместить большую часть красных точек в правом нижнем углу диаграммы. Это могут быть не те тестовые данные, которые нам нужны. Первый график с C = 0,01, по-видимому, лучше отражает общую тенденцию, хотя данные обучения менее точны, чем результаты для более высоких значений C.

Поскольку это компромисс, обратите внимание, что по мере увеличения значения C ширина интервала уменьшается.

В предыдущем примере интервал — это «нейтральная полоса» точек данных. Здесь мы видим, что не может быть ситуации, когда есть хорошая разделительная граница, а на интервале нет точек. На самом деле некоторые точки входят внутрь интервала.

Важным практическим вопросом является определение хорошего значения для C. Эта потребность возникает часто, поскольку данные реального мира почти никогда не бывают неразделимыми. Обычно мы используем что-то вродеперекрестная проверкаТакой метод выбирает хорошее значение для C.

Нелинейно разделимые данные

Мы видели, как SVM систематически обрабатывают идеально/почти линейно разделимые данные. Как он обрабатывает случай абсолютно нелинейно разделимых данных? В конце концов, под эту категорию попадает множество реальных данных. Конечно, поиск гиперплоскости уже не применим. Это кажется неудачным, учитывая, что SVM отлично справляются с этой задачей.

Вот пример нелинейно разделимых данных (это знаменитаяНабор данных XORвариант ), показанный с помощью линейного классификатора SVM:

Вы должны думать, что это не выглядит хорошо. Наша точность на тренировочном наборе составляет всего 75% — это лучший результат, которого мы можем достичь, используя только прямую линию. Более того, линия очень близка к некоторым данным. Оптимальная точность тоже не велика, и для баланса линия почти полностью пересекает некоторые точки.

нам нужно сделать лучше

Это моя любимая вещь в SVM. Вот что у нас есть на данный момент: у нас есть техника, которая очень хорошо находит гиперплоскости. Однако у нас также есть данные, которые не являются линейно разделимыми. так что нам делать? Спроецируйте данные наМожетЛинейно разделимое пространство и найдем гиперплоскость в этом пространстве!

Я объясню идею шаг за шагом.

Мы начинаем с набора данных на изображении выше и проецируем его в трехмерное пространство, где новые координаты:

Вот как выглядят прогнозируемые данные. Вы видите самолет, на котором мы можем скользить по самолету?

Запустим SVM:

Хорошо! Мы отлично разделяем этикетки! Давайте спроецируем плоскость обратно в исходное 2D-пространство и посмотрим, как выглядит граница сегментации:

100% точность набора обучающих данныхиГраницы разделения не подходят слишком близко к данным! отличный!

Форма границы сегментации в исходном пространстве зависит от проекции. В проекционном пространстве этодовольно частоявляется гиперплоскостью.

Помните, что основная цель проецирования данных — использовать способность SVM обнаруживать разделяющие гиперплоскости.

При сопоставлении его обратно с исходным пространством разделенная граница больше не является прямой линией. То же самое верно для интервалов и опорных векторов. Что касается нашей визуальной интуиции, они имеют смысл в спроецированном пространстве.

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

В спроецированном пространстве есть 4 опорных вектора, что кажется разумным. Они лежат на двух плоскостях, определяющих интервал. В исходном пространстве они все еще находятся на интервале, но на данный момент этого кажется недостаточно.

Давайте отступим и проанализируем, что произошло:

1. Как узнать, в какое пространство проецировать данные?

Похоже, я точно знаю, что нужно делать — взять квадратный корень из 2!

В этом примере я хотел показать, как работает проекция на более высокие измерения, поэтому я выбрал очень конкретную проекцию. В общем, это трудно узнать. Однако то, что мы знаем, это то, что из-заТеорема обложки, при проецировании на более высокие измерения данные болеевозможныйлинейно отделима.

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

2. Должен ли я сначала спроецировать данные, а затем запустить SVM?

Нет. Чтобы упростить понимание приведенного выше примера, я делаю это так, как будто нам нужно сначала спроецировать данные. Фактически, вы просите SVM сделать прогноз за вас. Это имеет некоторые преимущества. Во-первых, SVM делает эти проекции, используя так называемую функцию ядра, которая работает очень быстро (как мы скоро увидим).

Кроме того, помните проекцию в бесконечные измерения, о которой я упоминал в предыдущем разделе? Как вы представляете или храните бесконечные измерения, если вы проецируете данные самостоятельно? Оказывается, SVM очень умны в этом, в том числе благодаря функциям ядра.

Теперь пришло время взглянуть на функцию ядра.

Функция ядра

Наконец, есть секреты эффективной работы SVM. Здесь также необходимо изучать математику.

Давайте посмотрим на то, что мы видели до сих пор:

  1. Для линейно разделимых данных SVM работают очень хорошо.
  2. Для почти линейно разделимых данных с правильным значением C SVM все еще может работать хорошо.
  3. Для данных, которые не являются линейно разделимыми, мы можем спроецировать данные в полностью/почти линейно разделимое пространство, сводя проблему к шагу 1 или 2, где мы начинаем с данных.

Кажется, что важная операция, позволяющая сделать SVM универсально применимым к любой ситуации, — это спроецировать его на более высокие измерения. Для этого и предназначена функция ядра.

Во-первых, отступление.

Одна из очень удивительных вещей в SVM заключается в том, что во всей математике, которую он использует, точная проекция, даже количество измерений, не отображается. Вы можете основывать различные точки данных (представленные в виде векторов) междуточечные продуктывыразить все. заpразмерный векторiиj, где первый нижний индекс относится к точке, а второй нижний индекс относится к размерному числу:

Скалярный продукт определяется следующим образом:

Если наш набор данных имеетnточек, то SVMТолькоКлассификатор должен быть построен по скалярному произведению каждой пары точек. Это все. То же самое верно, когда мы хотим спроецировать данные в более высокие измерения. Нам не нужно предоставлять точную проекцию для SVM; нам нужно вычислить скалярное произведение между комбинациями всех точек в спроецированном пространстве.

Это важно, потому что это именно то, что делает функция ядра. Функция ядра (kernel functionсокращение от ) принимает две точки в качестве входных данных в исходном пространстве и дает скалярный продукт непосредственно в спроецированном пространстве.

Давайте вернемся к проекциям, которые мы сделали раньше, и посмотрим, сможем ли мы придумать соответствующую функцию ядра. Мы также будем следить за количеством вычислений, выполненных для проекции, а затем вычислим скалярное произведение — посмотрим, как функция ядра используется для сравнения.

для точкиi:

Наши соответствующие прогнозируемые точки:

Чтобы вычислить эту проекцию, нам нужно сделать следующее:

  • Получить новые данные первого измерения: 1 продукт
  • Данные второго измерения: 1-й продукт
  • Данные 3-го измерения: 2-й продукт

Всего 1+1+2 =4-й продукт.

Скалярный продукт в новом измерении равен:

Чтобы вычислить две точкиiиj, нам нужно сначала вычислить их проекции. Таким образом, 4 + 4 = 8 произведений, тогда само скалярное произведение требует 3 умножения и 2 сложений.

Короче говоря, это:

  • Продукт: 8 (проекция) + 3 (точечный продукт) = 11 продуктов
  • Сложение: 2 (точечный продукт)

Всего 11 + 2 =13 операций.

Я объявляю эту функцию ядра, и результат тот же:

мыво-первыхВозьмите скалярное произведение векторов в исходном пространстве и возведите результат в квадрат.

Давайте расширим его и проверим правильность моего утверждения:

Оно делает. Сколько операций это занимает? Посмотрите на шаг (2) выше. Чтобы вычислить двумерный скалярный продукт, мне нужно 2 умножения и 1 сложение. Возведение в квадрат — это еще одно умножение.

Итак, итого:

  • Умножения: 2 (точечный продукт в исходном пространстве) + 1 (для квадрата результата) = 3 умножения
  • Дополнение: 1 (точечный продукт в исходном пространстве)

Всего 3 + 1 =4 операции. ЭтотТолько31% операций, которые нам были нужны раньше.

Похоже, что быстрее использовать функцию ядра для вычисления нужного скалярного произведения. Это может показаться не таким уж большим делом: мы сравниваем 4 операции с 13 операциями, но по мере того, как входные точки имеют все больше и больше измерений, а размерность проекционного пространства становится выше, вычисления на больших наборах данных экономят время все больше и больше. Это огромное преимущество использования функций ядра.

В большинстве библиотек SVM предварительно упакованы некоторые популярные функции ядра, такие какПолиномиальная, радиальная базисная функция (RBF)иСигмовидная функция. Когда мы не используем проекцию (как в первом примере этой статьи), мы вычисляем скалярное произведение в исходном пространстве — мы называем этоЛинейная функция ядра.

Многие из этих функций ядра предоставляют вам дополнительные средства для дальнейшей настройки на основе ваших данных. Например, полиномиальная функция ядра:

позволяет вам выбиратьcиdзначение (степень многочлена). Для 3D-проекции выше я использовалc = 0иd = 2Полиномиальная функция ядра .

Но мы еще не закончили с мощью функции ядра!

Помните проекцию в бесконечные измерения, о которой я упоминал ранее? Если вы еще не догадались, способ заставить это работать состоит в том, чтобы иметь подходящую функцию ядра. Таким образом, нам не нужно проецировать входные данные и беспокоиться о хранении бесконечномерных данных.

Если у вас есть точные данные проекции, функция ядра вычислит скалярное произведение.

Функция ядра RBF обычно используется дляконкретныйБесконечномерная проекция. Мы не будем здесь заниматься математикой, ознакомьтесь со ссылками в конце этой статьи.

Как мы можем по-прежнему вычислять скалярное произведение с бесконечными измерениями? Если этот вопрос вас сбивает с толку, подумайте, как мы вычисляем суммы бесконечных рядов. Точно так же в скалярном произведении есть бесконечные члены, но есть формула для вычисления их суммы.

Это отвечает на вопрос, который мы задали в предыдущем разделе. в заключении:

  1. Обычно мы не определяем конкретные прогнозы для наших данных. Вместо этого мы выбираем из доступных ядер и в некоторых случаях корректируем их, чтобы найти то, которое лучше всего соответствует данным.
  2. Конечно, ничто не мешает нам определять собственные ядра или выполнять проекции самостоятельно, но во многих случаях нам это и не нужно. Или мы, по крайней мере, начнем с того, что мы можем сделать.
  3. Если для нужной нам проекции доступна функция ядра, мы обычно предпочитаем использовать функцию ядра, поскольку обычно она быстрее вычисляется.
  4. Функция ядра RBF может проецировать точки в бесконечные измерения.

Начало работы с библиотекой SVM

Есть много библиотек SVM, с которых вы можете начать практиковаться:

рисунокscikit-learnМногие такие библиотеки машинного обучения общего назначения также предоставляют модули SVM, которые обычно являются оболочками для специализированных библиотек SVM. Мое предложение проверено и провереноlibSVMНачинать.

libSVM доступен как инструмент командной строки, но загружаемый файл также поставляется в комплекте с оболочками Python, Java и Matlab. Вы можете использовать его, если у вас есть файл данных в формате, который понимает libSVM (это объясняется в загруженном файле README и других доступных параметрах).

На самом деле, если вам нужноочень быстроЧтобы понять, как разные функции ядра, разные значения C и т. д. влияют на поиск границ сегментации, см.ДомойПопробуйте использовать "графический интерфейс". Отметьте точки данных, принадлежащие разным классам, выберите параметры SVM и нажмите «Выполнить!».

Мне не терпится быстро отметить несколько моментов:

Да, я не упрощаю SVM.

Затем я попробовал несколько функций ядра:

Интерфейс не показывает границы сегментации, но показывает области, которые SVM определяет как принадлежащие определенной метке. Как видите, линейное ядро ​​полностью игнорирует красную точку. Он считает все пространство желтым (скажем, зеленым). Но функция ядра RBF ловко использует кольцеобразную область, чтобы закрыть красные маркеры!

полезные ресурсы

Мы полагались прежде всего на визуальное интуитивное понимание. Хотя это отличный способ получить начальное понимание, я настоятельно рекомендую копнуть глубже. Примеров визуально интуитивного понимания может быть недостаточно для понимания ширины интервала и опорных векторов для нелинейно разделимых случаев.

Помните, что эти количества определяются компромиссами оптимизации. Некоторые результаты могут показаться нелогичными, если вы не посмотрите на математику.

Еще одним полезным аспектом математики является понимание функций ядра. В этой короткой статье я едва коснулся функции ядра RBF. Я надеюсь, что его «загадка» — его связь с бесконечномерными проекциями в сочетании с фантастическими результатами на последнем наборе данных («кольцах») — убедила вас присмотреться к нему поближе.

Ресурсы, которые я рекомендую:

  1. Видеолекция: Обучение на основе данных. Автор Ясер Абу-Мостафа. В частях с 14 по 16 лекции обсуждаются SVM и функции ядра. Если вы ищете введение в машинное обучение, я также настоятельно рекомендую всю серию, которая имеет хороший баланс между математикой и интуицией.
  2. Книга: Элементы статистического обучения. Авторами являются Тревор Хасти, Роберт Тибширани и Джером Фридман. В главе 4 представлена ​​основная идея SVM, а в главе 12 она подробно обсуждается.

учись, совершенствуйся каждый день!

Если вы обнаружите ошибки в переводе или в других областях, требующих доработки, добро пожаловать наПрограмма перевода самородковВы также можете получить соответствующие бонусные баллы за доработку перевода и PR. начало статьиПостоянная ссылка на эту статьюЭто ссылка MarkDown этой статьи на GitHub.

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.

Категории