privetvision 4 Report post Posted April 14, 2016 Отступление: Перебрал кучу разных статей по 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? И как все-таки мы построили гиперплоскость? Как получить координаты гиперплоскости? Что-то я упустил 1 Share this post Link to post Share on other sites
Smorodov 578 Report post Posted April 15, 2016 SVM не тривиальная штука, поэтому и нет объяснений "на пальцах". g(x) - граница решений задается линейным уравнением типа y=kx+b в форме k1x+k2y+b=0 или если обозначать y как x2 и собрать вектор получится то что у них (k у них обозначено как омега). z1 и z2 отступы от границы решений до границы решений. Суть SVM в том, чтобы найти границу решений, где эти отступы максимальны (максимален минимальный отступ от границы решений). Уравнение можно без ущерба для решаемой задачи масштабировать, что и делается для того чтобы получить отступы до ближайших опорных векторов равными единице всегда. Делается для упрощения оптимизации. Омега, это коэффициенты уравнения зеленой прямой. Вектор коэффициентов всегда направлен перпендикулярно прямой. Дальше уравнение масштабируется для того (a - масштабный коэффициент), чтобы расстояние до точек было равно единице (1 и -1), тем самым находим уравнение границы решений (зеленой прямой). В реальных задачах применяется более сложная математика (методы линейной оптимизации), и описанное решение позволяет понять только смысл простейшего варианта SVM с "жестким" отступом, который реально почти не применяется, а применяется в основном SVM с "мягким" отступом, позволяющая классификацию в линейно неразделимых выборках. Его можно кратко сформулировать и без этих измышлений: "найти уравнение разделяющей гиперплоскости такое, чтобы минимальное расстояние от нее до любой точки выборки было как можно больше." Методы типа SVM еще называются методами максимального отступа. 1 Share this post Link to post Share on other sites
mrgloom 242 Report post Posted April 15, 2016 Я это понимаю так, что задаётся некая ф-ия минимизации ( 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/ Share this post Link to post Share on other sites
Smorodov 578 Report post Posted April 15, 2016 Ну регрессия и опорные векторы, как я понимаю, это несколько отличающиеся методы, по крайней мере по паре признаков: регрессия минимизирует среднеквадратическое отклонение (максимизирует правдоподобие), а опорные векторы максимизируют отступ от границы до опорного вектора. Решения будут близкими в простых случаях, но могут заметно отличаться в более сложных. Логистическая регрессия дает вероятности, опорные векторы нет, они дают только границу разделения ибо построены на других соображениях. Share this post Link to post Share on other sites
privetvision 4 Report post Posted April 17, 2016 Постепенно подкапываюсь к понимаюнию. Только вот, что это такое? Двойной модуль? Или корень от квадрата w? И немного перепутал w и w0, в первом случае это вектор весов или нормали к гиперплоскости, а w0 - это омега, какое-то число, пока не понял для чего. П.С. что-то хостинг периодически жалуется на лимит ресурсов процессора Share this post Link to post Share on other sites
Smorodov 578 Report post Posted April 17, 2016 Лимит, да, роботы лезут баню их, лезут с других адресов. Может сменю хостинг осенью, пока лень. ||X|| - это норма вектора, проще говоря евклидова длина (корень квадратный из суммы квадратов всех координат). w0 - смещение, то же что и b в уравнении прямой y=k*x+b. 1 Share this post Link to post Share on other sites
privetvision 4 Report post Posted April 17, 2016 Вот вопрос, в начале когда у нас два класса: круги и квадраты, нам надо найти: 1. крайний правый круг для левого класса 2. крайний левый квадрат для правого класса? Путем сравнения координат по x и y? А дальше работать с этими двумя точками, как в алгоритме выше Share this post Link to post Share on other sites
Smorodov 578 Report post Posted April 17, 2016 Не "крайний левый" и "крайний правый", а ближайший к границе со стороны квадратов и ближайший к границе со стороны кругов (это и будут опорные векторы). PS: Есть формула для определения расстояния от точки до прямой. Share this post Link to post Share on other sites
privetvision 4 Report post Posted April 17, 2016 1 час назад, Smorodov сказал: Не "крайний левый" и "крайний правый", а ближайший к границе со стороны квадратов и ближайший к границе со стороны кругов (это и будут опорные векторы). PS: Есть формула для определения расстояния от точки до прямой. Я про самое начало, на примере рассматриваются 2 точки, а если их больше будет? Где сам алгоритм выбора этих 2-ух точек? Граница ищется относительно этих 2 точек, а как их выбрать, если их множество. Тут на ум приходит только самый крайний левый и крайний правый. А вы уже рассказываете конец алгоритма. Share this post Link to post Share on other sites
Smorodov 578 Report post Posted April 18, 2016 Просто берете две ближайшие друг к другу точки соседних выборок, проводите между ними прямую, находите середину этой прямой, проводите перпендикуляр через эту точку. Делите координаты всех точек (и коэффициенты прямой) на половину расстояния между двумя ближайшими точками. Все !!! 1 Share this post Link to post Share on other sites
privetvision 4 Report post Posted April 18, 2016 2 часа назад, Smorodov сказал: Просто берете две ближайшие друг к другу точки соседних выборок Ну вот, я этот момен описал более детальнее: 18 часов назад, privetvision сказал: Вот вопрос, в начале когда у нас два класса: круги и квадраты, нам надо найти: 1. крайний правый круг для левого класса 2. крайний левый квадрат для правого класса? Путем сравнения координат по x и y? А дальше работать с этими двумя точками, как в алгоритме выше Цитата , проводите между ними прямую, находите середину этой прямой, проводите перпендикуляр через эту точку. Хм, вот этого раньше не встречал! Круто! Вопрос, перпендикуляр это вектор нормали, он же w в нашем алгоритме верно? Цитата Делите координаты всех точек (и коэффициенты прямой) на половину расстояния между двумя ближайшими точками. хм, не понял зачем делить координаты ВСЕХ точек? Что это дает? например точка p7 (3; 2) ее коорды делить на ||w||/2, пусть ||w|| = 10, тогда будет p7 / 5, в итоге у нас будет новый вектор p7 (3/5; 2/5), что он дает? п.с. извиняюсь за глупые вопросы, приходится разобраться в алгоритме, чтобы реализовать на яве. Share this post Link to post Share on other sites
Smorodov 578 Report post Posted April 18, 2016 Если упрощать так до конца Ближайшие точки ищутся брутфорсом, просто перебираете расстояния между всеми точками обоих классов и находите минимум. Да, если построить вектор коэффициентов прямой это будет нормаль к ней. Чтобы измерять расстояния до прямой, удобно перейти в систему координат заданную этой прямой. Оси обычно задаются ортами (векторами единичной длины), для этого делим на половину длины. Т.к. у нас целевая координата одной точки +1, другой -1. Разница равна 2. Координаты точек масштабируются вместе с системой координат (не уверен, что там все срастется, сейчас голова забита). ЗЫ: если хотите реализовать это не "для поиграть", то этот метод не имеет ничего общего с реально используемыми методами. Там математика много сложнее. Так что лучше взять готовую библиотеку, думаю для явы таковые тоже имеются. Прикрепил свою лекцию по SVM но там в общем виде дано, нужна мат. подготовка (да и лекция эта восьмая). Картинки зато есть. Lec8.pdf Кстати в этом (см прикрепленную картинку) случае, когда ближайших точек больше чем 2, описанный выше метод не подойдет. Share this post Link to post Share on other sites
Smorodov 578 Report post Posted April 18, 2016 Подумал еще, метод с прямой между ближайшими точками работает только в некоторых случаях. Надо искать проекции на систему координат, построенную на прямой. Но для двух точек, как в примере, работать будет Кстати, вот это описание вроде получше будет: Share this post Link to post Share on other sites
privetvision 4 Report post Posted May 25, 2016 И все-таки, начал делать на яве, простой вопрос, как найти вектор весов (нормаль к гиперпроскости) ? Если у нас такой случай, как на картинке ниже и если мы будем делать как видео в первом посте, то W = (0:3) что полная чушь... Share this post Link to post Share on other sites
Smorodov 578 Report post Posted May 25, 2016 Думаю что так Share this post Link to post Share on other sites
privetvision 4 Report post Posted May 25, 2016 22 минуты назад, Smorodov сказал: Думаю что так Вы можете объяснить на этом примере, как получить численно W Share this post Link to post Share on other sites
Smorodov 578 Report post Posted May 25, 2016 Ух! Нарисовал последовательность шагов. 1) Берем начальную гипотезу границы (случайно). ищем ближайшие точки из каждого набора (E и H). 2) Передвигаем прямую так, чтобы выровнять расстояния. 3) Заново ищем ближайшие точки. 4) Опять выравниваем расстояния. 5) повторять до сходимости. 6) Нормировать коэффициенты так, чтобы расстояние до каждого класса было равно единице. Вроде так должно получиться. Share this post Link to post Share on other sites
privetvision 4 Report post Posted May 26, 2016 Мне кажется так не сработает, потому что не понятно какой брать наклон гиперплоскости Share this post Link to post Share on other sites
Smorodov 578 Report post Posted May 26, 2016 Вначале любой.Выбираем 2 ближайшие точки и максимизируем (не указал выше этот пункт) расстояния от прямой до этих точек, при этом расстояния эти должны быть равны между собой. Вроде как все однозначно. Share this post Link to post Share on other sites
privetvision 4 Report post Posted May 26, 2016 А если так выбреем? Share this post Link to post Share on other sites
Smorodov 578 Report post Posted May 26, 2016 Ну так максимизировать отступы и выровнять расстояния и прямая встанет как надо. Share this post Link to post Share on other sites
privetvision 4 Report post Posted May 26, 2016 6 часов назад, Smorodov сказал: Ну так максимизировать отступы и выровнять расстояния и прямая встанет как надо. Мне тут подсказали, что тут зацикливание будет, мол находится новая ближайшая точка, а на след. итерации предыдущая точка стала ближе и так зациклимся. Share this post Link to post Share on other sites
Smorodov 578 Report post Posted May 26, 2016 Для этого вводят шаг итерации обычно, чтобы изменения не происходили резко а прямая постепенно меняла коэффициенты с малым шагом и еще условия останова задают. Кстати, и OpenCV-шных реализациях они задаются, если посмотрите документацию. А если будет переключаться, то изменения будут уже в пределах малой величины. Вообще, как я уже говорил, этот алгоритм имеет очень мало общего с реальным SVM. И описывать его таким образом больше на спорт смахивает. Поэтому, все равно, придется иметь дело с квадратичным программированием, множителями Лагранжа и условиями Каруша-Куна-Таккера. Кстати, еще одна неплохая статейка: http://www.statistica.ru/branches-maths/metod-opornykh-vektorov-supported-vector-machine-svm/ Share this post Link to post Share on other sites
privetvision 4 Report post Posted May 28, 2016 Правильно ли я понимаю, что после того, как мы уровняли расстояние от прямой до точек из разных кластеров, мы должны поворачивать эту прямую вокруг своей оси на 360*, чтобы найти максимальное расстояние. Хотя, так подумав, максимальным расстоянием до прямой между двумя точками будет перпендикурялр опущенный к центру этого расстояния Share this post Link to post Share on other sites
privetvision 4 Report post Posted May 28, 2016 В общем сделал как на первом видео. Я ошибся, вектор нормали был (3;0), а не (0;3) поэтому там все нормально. Только вот проблема, получается этот упрощенный метод только для двух точек? Share this post Link to post Share on other sites
