Перейти к содержимому
Compvision.ru
privetvision

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

Recommended Posts

Отступление:

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

Проблема.

Не могу найти пример на пальцах (с подставленными значениями), точнее нашел, но не полный.

 

Что мне не понятно.

Понятно, что надо найти максимальное расстояние между двумя группами объектов и гиперплоскость

Не понимаю что делать в самом начале алгоритма. Вот у нас имеется квадраты и кружочки. 

1. Находим крайнюю кружочек и крайний квадрат.2

2. Получаем их координаты, на видео это x1 = (1,1) и x2 = (2,3)

3. Потом ищется вектор весов (или нормали) w = (2,3) - (2,1) = (1, 2) = (a, 2a) - первый вопрос зачем? Что это?

4.Потом берется формула w*x1 - w0 = 1    и      w*x2 - w0 = -1. Что такое w0?

5. Далее подставляем в формулу значения и выражаем w0 = 1 - 8a  и w0 = -1 - 3a

6. Выражаем одно через другое, 1 - 8a = -1 -3a, 5a = 2, и получаем a =2/5

7. Потом подставляем a = 2/5 в формулу w0 = 1 - 8a и получаем w0 = - 11/5

8. Подставляем a=2/5 в вектор w = (a, 2a) = (2/5, 4/5) - повторный вопрос это что за вектор?

9.Ну и наконец мы подставляем координаты вектора w в формулу g(x) = 2/5 * z1 + 4/5 * z2 - w0. Тут вопрос, что это за функция g(x), что это за значения z1 и z2?

И как все-таки мы построили гиперплоскость? Как получить координаты гиперплоскости? Что-то я упустил

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

SVM не тривиальная штука, поэтому и нет объяснений "на пальцах".

g(x) - граница решений задается линейным уравнением типа y=kx+b в форме k1x+k2y+b=0 или если обозначать y как x2 и собрать вектор получится то что у них (k у них обозначено как омега).

z1 и z2 отступы от границы решений до границы решений. Суть SVM в том, чтобы найти границу решений, где эти отступы максимальны (максимален минимальный отступ от границы решений).

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

Омега, это коэффициенты уравнения зеленой прямой. Вектор коэффициентов всегда направлен перпендикулярно прямой. 

Дальше уравнение масштабируется для того (a - масштабный коэффициент), чтобы расстояние до точек было равно единице (1 и -1), тем самым находим уравнение границы решений (зеленой прямой).

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

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

 Методы типа SVM еще называются методами максимального отступа.

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я это понимаю так, что задаётся некая ф-ия минимизации ( convex optimization problem ), а потом она уже специальными методами решается.

Даже для Linear SVM бывают разные подвиды с регуляризацией L1, L2, Lasso и т.д.

https://www.csie.ntu.edu.tw/~cjlin/liblinear/

 

И да веса линейной модели(W,b) можно получить не только через Linear SVM. SVM это так называемый maximum margin classifier.

https://habrahabr.ru/post/278513/

Заодно и регрессия https://habrahabr.ru/post/279117/

 

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Постепенно подкапываюсь к понимаюнию. Только вот, что это Screenshot_1.png такое? Двойной модуль? Или корень от квадрата w?

И немного перепутал w и w0, в первом случае это вектор весов или нормали к гиперплоскости, а w0 - это омега, какое-то число, пока не понял для чего.

П.С. что-то хостинг периодически жалуется на лимит ресурсов процессора 

S5rbkpK.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Лимит, да, роботы лезут :) баню их, лезут с других адресов. Может сменю хостинг осенью, пока лень.

||X|| - это норма вектора, проще говоря евклидова длина (корень квадратный из суммы квадратов всех координат).

w0 - смещение, то же что и b в уравнении прямой y=k*x+b. 

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Вот вопрос, в начале когда у нас два класса: круги и квадраты, нам надо найти:

1. крайний правый круг для левого класса

2. крайний левый квадрат для правого класса?

Путем сравнения координат по x и y?

А дальше работать с этими двумя точками, как в алгоритме выше

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Не "крайний левый" и "крайний правый", а ближайший к границе со стороны квадратов и ближайший к границе со стороны кругов (это и будут опорные векторы).

PS: Есть формула для определения расстояния от точки до прямой.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 час назад, Smorodov сказал:

Не "крайний левый" и "крайний правый", а ближайший к границе со стороны квадратов и ближайший к границе со стороны кругов (это и будут опорные векторы).

PS: Есть формула для определения расстояния от точки до прямой.

Я про самое начало, на примере рассматриваются 2 точки, а если их больше будет? Где сам алгоритм выбора этих 2-ух точек? Граница ищется относительно этих 2 точек, а как их выбрать, если их множество. Тут на ум приходит только самый крайний левый и крайний правый. А вы уже рассказываете конец алгоритма.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Все !!! 

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 часа назад, Smorodov сказал:

Просто берете две ближайшие друг к другу точки соседних выборок

Ну вот, я этот момен описал более детальнее:

18 часов назад, privetvision сказал:

Вот вопрос, в начале когда у нас два класса: круги и квадраты, нам надо найти:

1. крайний правый круг для левого класса

2. крайний левый квадрат для правого класса?

Путем сравнения координат по x и y?

А дальше работать с этими двумя точками, как в алгоритме выше

 

Цитата

, проводите между ними прямую, находите середину этой прямой, проводите перпендикуляр через эту точку.

Хм, вот этого раньше не встречал! Круто! Вопрос, перпендикуляр это вектор нормали, он же w в нашем алгоритме верно?

Цитата

Делите координаты всех точек (и коэффициенты прямой) на половину расстояния между двумя ближайшими точками. 

хм, не понял зачем делить координаты ВСЕХ точек? Что это дает? например точка p7 (3; 2) ее коорды делить на ||w||/2, пусть ||w|| = 10, тогда будет p7 / 5, в итоге у нас будет новый вектор p7 (3/5; 2/5), что он дает?

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Если упрощать так до конца :)

Ближайшие точки ищутся брутфорсом, просто перебираете расстояния между всеми точками обоих классов и находите минимум.

Да, если построить вектор коэффициентов прямой это будет нормаль к ней. Чтобы измерять расстояния до прямой, удобно перейти в систему координат заданную этой прямой. Оси обычно задаются ортами (векторами единичной длины), для этого делим на половину длины. Т.к. у нас целевая координата одной точки +1, другой -1. Разница равна 2.

Координаты точек масштабируются вместе с системой координат (не уверен, что там все срастется, сейчас голова забита).

ЗЫ: если хотите реализовать это не "для поиграть", то этот метод не имеет ничего общего с реально используемыми методами.

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

 

Прикрепил свою лекцию по SVM :) но там в общем виде дано, нужна мат. подготовка (да и лекция эта восьмая). Картинки зато есть. 

Lec8.pdf

 

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

v1.PNG

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Подумал еще, метод с прямой между ближайшими точками работает только в некоторых случаях. Надо искать проекции на систему координат, построенную на прямой. Но для двух точек, как в примере, работать будет :)

 

Кстати, вот это описание вроде получше будет: 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

И все-таки, начал делать на яве, простой вопрос, как найти вектор весов (нормаль к гиперпроскости) ? 

Если у нас такой случай, как на картинке ниже и если мы будем делать как видео в первом посте, то W = (0:3) что полная чушь...

 

Screenshot_8.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Думаю что так

grid.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
22 минуты назад, Smorodov сказал:

Думаю что так

grid.png

Вы можете объяснить на этом примере, как получить численно W

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Ух!

Нарисовал последовательность шагов.

1) Берем начальную гипотезу границы (случайно).

ищем ближайшие точки из каждого набора (E и H). 

1.PNG

2) Передвигаем прямую так, чтобы выровнять расстояния.

2.PNG

3) Заново ищем ближайшие точки.

3.PNG

4) Опять выравниваем расстояния.

4.PNG

5) повторять до сходимости.

6) Нормировать коэффициенты так, чтобы расстояние до каждого класса было равно единице.

 

Вроде так должно получиться. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Мне кажется так не сработает, потому что не понятно какой брать наклон гиперплоскости

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Вроде как все однозначно.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Ну так максимизировать отступы и выровнять расстояния и прямая встанет как надо.

Screenshot_3.png.9f9650c8f4e60bf0bab11f624a1b94fc.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
6 часов назад, Smorodov сказал:

Ну так максимизировать отступы и выровнять расстояния и прямая встанет как надо.

Screenshot_3.png.9f9650c8f4e60bf0bab11f624a1b94fc.png

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Для этого вводят шаг итерации обычно, чтобы изменения не происходили резко а прямая постепенно меняла коэффициенты с малым шагом и еще условия останова задают. Кстати, и OpenCV-шных реализациях они задаются, если посмотрите документацию.

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

 

Вообще, как я уже говорил, этот алгоритм имеет очень мало общего с реальным SVM. 

И описывать его таким образом больше на спорт смахивает.  

Поэтому, все равно, придется иметь дело с квадратичным программированием, множителями Лагранжа и условиями Каруша-Куна-Таккера.

 

Кстати, еще одна неплохая статейка: http://www.statistica.ru/branches-maths/metod-opornykh-vektorov-supported-vector-machine-svm/

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Хотя, так подумав, максимальным расстоянием до прямой между двумя точками будет перпендикурялр опущенный к центру этого расстояния

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

В общем сделал как на первом видео. Я ошибся, вектор нормали был (3;0), а не (0;3) поэтому там все нормально. 

Только вот проблема, получается этот упрощенный метод только для двух точек? 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×