Метод опорных векторов

  • Метод опорных векторов (англ. SVM, support vector machine) — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов и может также рассматриваться как специальный случай регуляризации по Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора, поэтому метод также известен как метод классификатора с максимальным зазором.

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

Источник: Википедия

Связанные понятия

В прикладной статистике метод наименьших полных квадратов (МНПК, TLS — англ. Total Least Squares) — это вид регрессии с ошибками в переменных, техника моделирования данных с помощью метода наименьших квадратов, в которой принимаются во внимание ошибки как в зависимых, так и в независимых переменных. Метод является обобщением регрессии Деминга и ортогональной регрессии и может быть применён как к линейным, так и нелинейным моделям.
Метод главных компонент (англ. principal component analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретён Карлом Пирсоном в 1901 году. Применяется во многих областях, в том числе, в эконометрике, биоинформатике, обработке изображений, для сжатия данных, в общественных науках.
Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — МидаСимплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Подробнее: Симплекс-метод
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Двойственность, или принцип двойственности, — принцип, по которому задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу. Решение двойственной задачи даёт нижнюю границу прямой задачи (при минимизации). Однако, в общем случае, значения целевых функций оптимальных решений прямой и двойственной задач не обязательно совпадают. Разница этих значений, если она наблюдается, называется разрывом двойственности. Для задач выпуклого программирования разрыв двойственности...
Вычислительные (численные) методы — методы решения математических задач в численном видеПредставление как исходных данных в задаче, так и её решения — в виде числа или набора чисел.
Алгоритм Гаусса — Ньютона используется для решения задач нелинейным методом наименьших квадратов. Алгоритм является модификацией метода Ньютона для нахождения минимума функции. В отличие от метода Ньютона, алгоритм Гаусса — Ньютона может быть использован только для минимизации суммы квадратов, но его преимущество в том, что метод не требует вычисления вторых производных, что может оказаться существенной трудностью.
Приближение с помощью кривых — это процесс построения кривой или математической функции, которая наилучшим образом приближается к заданным точкам с возможными ограничениями на кривую . Для построения такого приближения может использоваться либо интерполяция , где требуется точное прохождение кривой через точки, либо сглаживание, когда «сглаживающая» функция проходит через точки приближённо. Связанный раздел — регрессионный анализ, который фокусируется, главным образом, на вопросах статистического...
В математике монодро́ми́ей называется явление, состоящее в преобразовании некоторого объекта при обнесении его вдоль нетривиального замкнутого пути.

Подробнее: Монодромия
Пучок — структура, используемая для установления отношений между локальными и глобальными данными.
Размерность Вапника — Червоненкиса или VC-размерность — это характеристика семейства алгоритмов для решения задачи классификации с двумя классами, характеризующая сложность или ёмкость этого семейства. Это одно из ключевых понятий в теории Вапника-Червоненкиса о статистическом машинном обучении, названное в честь Владимира Вапника и Алексея Червоненкиса.
Квадратичное программирование (англ. quadratic programming, QP) — это процесс решения задачи оптимизации специального типа, а именно — задачи оптимизации (минимизации или максимизации) квадратичной функции нескольких переменных при линейных ограничениях на эти переменные. Квадратичное программирование является частным случаем нелинейного программирования.
Ко́мпле́ксный ана́лиз, тео́рия фу́нкций ко́мпле́ксного переме́нного (или ко́мпле́ксной переме́нной; сокращенно — ТФКП) — раздел математического анализа, в котором рассматриваются и изучаются функции комплексного аргумента.
Сглаживающий сплайн (англ. smoothing spline) это метод сглаживания (аппроксимации кривой набора зашумлённых исходных данных) с использованием сплайн-функций.
В математике, матричная функция — это функция, отображающая матрицу в другую матрицу.
Суммирующая функция делителей в теории чисел — функция, являющаяся суммой функции делителей.
В вычислительной математике одной из наиболее важных задач является создание эффективных и устойчивых алгоритмов нахождения собственных значений матрицы. Эти алгоритмы вычисления собственных значений могут также находить собственные векторы.

Подробнее: Алгоритм вычисления собственных значений
Квазиньютоновские методы — методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.
Топологическая энтропия — в теории динамических систем неотрицательное вещественное число, которое является мерой сложности системы.
Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.
Геометрический центр дискретного множества точек евклидова пространства (говоря статистическим языком — выборки) — это точка, в которой минимизируется сумма расстояний до точек множества. Геометрический центр обобщает медиану в математической статистике, которая минимизирует расстояния в одномерной выборке данных. Таким образом, геометрический центр отражает центральную тенденцию в пространствах высокой размерности. Понятие известно также по названиям 1-медиана , пространственная медиана, или точка...
Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств. Разработан А.С. Немировским и доведён до алгоритмической реализации Л.Г. Хачияном в ВЦ АН СССР.
Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован...
Многочлен Александера — это инвариант узла, который сопоставляет многочлен с целыми коэффициентами узлу любого типа. Джеймс Александер обнаружил его, первый многочлен узла, в 1923. В 1969 Джон Конвей представил версию этого многочлена, ныне носящую название многочлен Александера — Конвея. Этот многочлен можно вычислить с помощью скейн-соотношения, хотя важность этого не была осознана до открытия полинома Джонса в 1984. Вскоре после доработки Конвеем многочлена Александера стало понятно, что похожее...
Расстояние Махалано́биса — мера расстояния между векторами случайных величин, обобщающая понятие евклидова расстояния.
В статистике, машинном обучении и теории информации снижение размерности — это преобразование данных, состоящее в уменьшении числа переменных путём получения главных переменных. Преобразование может быть разделено на отбор признаков и выделение признаков.

Подробнее: Снижение размерности
Ве́ктор (от лат. vector, «несущий») — в простейшем случае математический объект, характеризующийся величиной и направлением. Например, в геометрии и в естественных науках вектор есть направленный отрезок прямой в евклидовом пространстве (или на плоскости).
Метод наименьших квадратов (МНК) — математический метод, применяемый для решения различных задач, основанный на минимизации суммы квадратов отклонений некоторых функций от искомых переменных. Он может использоваться для «решения» переопределенных систем уравнений (когда количество уравнений превышает количество неизвестных), для поиска решения в случае обычных (не переопределенных) нелинейных систем уравнений, для аппроксимации точечных значений некоторой функции. МНК является одним из базовых методов...
Алгоритм Левенберга — Марквардта — метод оптимизации, направленный на решение задач о наименьших квадратах. Является альтернативой методу Ньютона. Может рассматриваться как комбинация последнего с методом градиентного спуска или как метод доверительных областей. Алгоритм был сформулирован независимо Левенбергом (1944) и Марквардтом (1963).
Вариацио́нное исчисле́ние — раздел анализа, в котором изучаются вариации функционалов. Наиболее типичная задача — найти функцию, на которой заданный функционал достигает экстремального значения.
Сетевое кодирование предоставляет возможность увеличить пропускную способность и улучшить устойчивость сети без какого-либо централизованного управления. К сожалению, оно очень восприимчиво к атакам, в которых вредоносные узлы изменяют данные. Благодаря тому, как пакеты распространяются в сети, единственный неправильный пакет данных может сделать недействительными все дальнейшие данные. Злоумышленник может повредить пакет, даже если он зашифрован: для этого ему нужно подделать подпись, либо найти...

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

Подробнее: Математическая формулировка общей теории относительности
Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.
Отношение инцидентности — это бинарное отношение между двумя различными типами объектов. Это включает понятия, которые можно выразить такими фразами как «точка лежит на прямой» или «прямая принадлежит плоскости». Наиболее существенное отношение инцидентности — между точкой P и прямой l, которое записывается как P I l. Если P I l, пара (P, l) называется флагом. В разговорном языке существует много выражений, описывающих отношение инцидентности (например, прямая проходит через точку, точка лежит на...

Подробнее: Инцидентность (геометрия)
Вейвлеты Добеши (англ. Daubechies wavelet) — семейство ортогональных вейвлетов с компактным носителем, вычисляемым итерационным путём. Названы в честь математика из США, первой построившей данное семейство, Ингрид Добеши.
Лине́йная комбина́ция — выражение, построенное на множестве элементов путём умножения каждого элемента на коэффициенты с последующим сложением результатов (например, линейной комбинацией x и y будет выражение вида ax + by, где a и b — коэффициенты).
Нейронные сети Кохонена — класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена обрабатываются по правилу «Победитель получает всё»: наибольший сигнал превращается в единичный, остальные обращаются в ноль.
Схема шифрования GGH (англ. Goldreich–Goldwasser–Halevi) — асимметричная криптографическая система, основанная на решётках. Также существует схема подписи GGH.
Ковариа́нтность и контравариа́нтность — используемые в математике (линейной алгебре, дифференциальной геометрии, тензорном анализе) и в физике понятия, характеризующие то, как тензоры (скаляры, векторы, операторы, билинейные формы и т. д.) изменяются при преобразованиях базисов в соответствующих пространствах или многообразиях. Контравариантными называют «обычные» компоненты, которые при смене базиса пространства изменяются с помощью преобразования, обратного преобразованию базиса. Ковариантными...
Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды) — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Частным случаем БЧХ-кодов является код Рида — Соломона.
Кэлеровы дифференциалы представляют собой адаптацию дифференциальных форм для произвольных коммутативных колец или схем. Это понятие было введено Эрихом Кэлером в 1930-х.

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

Подробнее: Спектральная кластеризация
Лемма регулярности Семереди — лемма из общей теории графов, утверждающая, что вершины любого достаточно большого графа можно разбить на конечное число групп таких, что почти во всех двудольных графах, соединяющих вершины из двух разных групп, рёбра распределены между вершинами почти равномерно. При этом минимальное требуемое количество групп, на которые нужно разбить множество вершин графа, может быть сколь угодно большим, но количество групп в разбиении всегда ограничено сверху.
Стохастическое вложение соседей с t-распределением (англ. t-distributed Stochastic Neighbor Embedding, t-SNE) — это алгоритм обучения машин для визуализации, разработанный Лоренсом ван дер Маатеном и Джеффри Хинтоном. Он является техникой нелинейного снижения размерности, хорошо подходящей для вложения данных высокой размерности для визуализации в пространство низкой размерности (двух- или трехмерное). В частности, метод моделирует каждый объект высокой размерности двух- или трёхмерной точкой таким...
Схе́ма — математическая абстракция, позволяющая связать алгебраическую геометрию, коммутативную алгебру и дифференциальную геометрию и переносить идеи из одной области в другую. В первую очередь понятие схемы позволяет перенести геометрическую интуицию и геометрические конструкции, такие как тензорные поля, расслоения и дифференциалы, в теорию колец. Исторически теория схем возникла с целью обобщения и упрощения классической алгебраической геометрии итальянской школы XIX века, занимавшейся исследованием...
Множество больших тригонометрических сумм — понятие теории чисел — множество индексов, в которых преобразование Фурье характеристической функции заданного подмножества группы принимает достаточно большие значения.
Ба́зис (др.-греч. βασις «основа») — упорядоченный (конечный или бесконечный) набор векторов в векторном пространстве, такой, что любой вектор этого пространства может быть единственным образом представлен в виде линейной комбинации векторов из этого набора. Векторы базиса называются базисными векторами.
Ориента́ция, в классическом случае — выбор одного класса систем координат, связанных между собой «положительно» в некотором определённом смысле.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я