Support Vector Regression

Это 20-й день моего участия в августовском испытании обновлений. Узнайте подробности события:Испытание августовского обновления

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

Kernel Ridge Regression

Прежде всего, давайте рассмотрим теорему о представителях, введенную в предыдущем уроке.Для любой L2-регуляризованной линейной модели, содержащей регулярные члены, ее оптимальное решениеw может быть записано как линейная комбинация z.Поэтому можно ввести методы ядра для преобразования модель в ядро.

Так как же превратить регрессионную модель в форму ядра? Наиболее часто используемая оценка ошибки для линейной/гребенчатой ​​регрессии, которую мы ввели ранее, — это квадрат ошибки, т. е.. Решение, соответствующее этой форме, является аналитическим решением, то есть линейный метод наименьших квадратов может быть использован для непосредственного получения оптимального решения посредством векторных операций. Затем мы изучим, как ввести ядро ​​в гребневую регрессию и получить соответствующее аналитическое решение.

Давайте сначала запишем проблему регрессии Kernel Ridge:

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

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

решатьЗадачу можно записать так:

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

Вопрос, который должен волновать здесь,Обратная матрица ? Ответ положительный. Поскольку мы представили ранее, функция ядра K удовлетворяет условию Мерсера, она положительно полуопределена и,такдолжен быть обратимым. С точки зрения вычислительной сложности времени, посколькуимеет размер NxN, поэтому временная сложность. Еще один момент,Он состоит из произведения двух предметов, а другой элемент — К. Будет ли ситуация, когда К = 0? Фактически, поскольку функция ядра K представляет собой внутренний продукт пространства z, в общем случае, если два вектора не перпендикулярны друг другу, внутренний продукт равен нулю, в противном случае K вообще не равен нулю. Эта причина также определяетявляется плотной матрицей, т.е.Решения в основном ненулевые значения. Это свойство будет объяснено позже.

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

Как показано на рисунке выше, слева показана линейная гребенчатая регрессия, представляющая собой прямую линию, а справа — ядерная гребенчатая регрессия, представляющая собой кривую. Для грубого сравнения лучше подходит кривая справа. Каковы преимущества и недостатки этих двух регрессий? Для линейной гребневой регрессии это линейная модель, которая может соответствовать только прямым линиям; во-вторых, сложность ее обучения, сложность прогноза, эта модель более эффективна, если N много больше, чем d. Для ядерной гребневой регрессии он преобразуется в пространство z ​​и использует методы ядра для получения нелинейной модели, что делает его более гибким; во-вторых, его сложность обучения, сложность прогноза, относятся только к Н. Когда N очень велико, объем вычислений очень велик, поэтому регрессия гребня ядра подходит для случаев, когда N не очень велико. Для сравнения можно сказать, что линейный и ядерный на самом деле являются компромиссом между эффективностью и гибкостью.

Support Vector Regression Primal

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

Давайте сначала посмотрим на различия между результатами Gaussian SVM с мягким запасом и Gaussian LSSVM для определенной задачи.

Как показано на рисунке выше, если вы посмотрите только на границу классификации, гауссовский SVM с мягкими краями и гауссовский LSSVM не сильно отличаются, то есть полученные линии классификации почти одинаковы. Но если вы посмотрите на опорный вектор (точка, отмеченная прямоугольником на рисунке), SV гауссовой SVM с мягким полем слева невелика, в то время как в основном каждая точка гауссовой LSSVM справа является SV. Это связано с тем, что гауссовский SVM с мягким запасом вБольшинство равны нулю,Точек всего несколько, поэтому СВ меньше. А для LSSVM мы представили в предыдущем разделеРешения в основном ненулевые значения, поэтому каждая соответствующая точка в основном SV. Слишком много СВ принесет проблему, то есть момент предсказания,еслиЕсли ненулевых значений больше, то величина вычисления g относительно велика, что снижает скорость вычислений. По этой причине гауссовский SVM с мягким запасом более выгоден.

Тогда для плотного в LSSVMНедостатки, можем ли мы использовать некоторые методы, чтобы получить разреженные, чтобы SV не было слишком много, чтобы можно было получить тот же эффект классификации, что и SVM с мягкой маржой? Ниже мы попытаемся решить эту проблему.

Метод заключается во введении метода под названием Tube Regression, то есть область (нейтральная область) очерчена на верхней и нижней линиях линии классификации.Если точки данных распределены в этой области, это не считается ошибкой классификации. , только неправильная классификация вне нейтральной области.Это ошибка.

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

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

Во-первых, мы сравниваем ошибку регрессии трубки с квадратом ошибки:

Затем нарисуйте кривые зависимости err(y,s) и s соответственно:

На приведенном выше рисунке красная линия представляет квадрат ошибки, а синяя линия представляет ошибку трубки. Мы обнаружили, что когда |s-y| относительно мало, то есть когда s близко к y, квадрат ошибки и ошибка трубки примерно одинаковы. В области, где |s-y| относительно велика, скорость роста квадрата ошибки намного больше, чем скорость роста ошибки трубки. Чем больше увеличение ошибки, тем сильнее подвержены влиянию шума, что не способствует решению задачи оптимизации. Таким образом, с этой точки зрения функция ошибок трубной регрессии лучше.

Теперь запишем L2-Regularized Tube Regression:

Эта задача оптимизации, поскольку она содержит максимальный член, не везде дифференцируема, поэтому ее нельзя решать с помощью GD/SGD. Более того, хотя оно и удовлетворяет теореме о представителях, его можно решить, введя ядро, но это не гарантирует получения разреженности.. С другой стороны, мы можем преобразовать эту задачу в условную задачу QP, имитировать метод вывода двойственного SVM, ввести ядро ​​и получить условие KKT, тем самым обеспечив решениеявляется редким.

Следовательно, мы можем написать L2-Regularized Tube Regression в форме, аналогичной SVM:

Стоит отметить, что коэффициентнаходится в обратной зависимости от C,Чем больше соответствует меньшему C,Меньший соответствует большему C. Кроме того, формула такжеТо есть b выносится отдельно, что согласуется с нашим предыдущим методом получения решения SVM.

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

Как показано в правой части рисунка выше, это стандартная задача QP, гдеиУказывает на нарушения верхней и нижней труб соответственно. Эта форма называется первичной регрессией опорных векторов (SVR).

Стандартная QP-форма SVR содержит несколько важных параметров: C и. C представляет собой компромисс между регуляризацией и нарушением трубки. Большой C склонен к трубчатому нарушению, а маленький C склонен к регуляризации.Он характеризует ширину участка трубы, то есть допуск на неправильные точки.Чем он больше, тем выше устойчивость к ошибкам.— устанавливаемая константа, уникальная для задач SVR и не имеющая этого параметра в SVM. Кроме того, QP-формы SVR разделяютпараметры, условия 2N+2N.

Support Vector Regression Dual

Теперь, когда у нас есть основная форма SVR, мы получим двойную форму SVR. Во-первых, как и в двойственной форме SVM, шиллинговый лагранжев фактори, соответственно сиНеравенство соответствует. игнорируется здесь сиСоответствующий фактор Лагранжа.

Затем, выполняя тот же вывод и упрощение, что и SVM, функция Лагранжа частично дифференцируется до нуля для соответствующих параметров и получаются соответствующие условия ККТ:

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

Наконец, мы собираемся обсудить, действительно ли решение SVR является разреженным. Решение w, полученное в двойственной форме SVR, было получено как:

Соответствующая дополнительная нежесткость:

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

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

Summary of Kernel Models

В этом разделе будут обобщены и обобщены все модели ядра, которые мы представили. Всего мы представили три линейные модели, а именно PLA/карман, регуляризованную логистическую регрессию и линейную гребенчатую регрессию. Все три модели могут быть решены с помощью функций библиотеки Liblinear, разработанной доктором Чжи-Джен Линь из Национального Тайваньского университета.

Кроме того, мы вводим линейный SVM с мягким запасом, где функция ошибок, которая может быть решена стандартной задачей QP. Линейный SVM с мягкой маржой решает ту же проблему, что и PLA/pocket. Затем также вводится линейная проблема SVR, которая решает ту же проблему, что и линейная гребневая регрессия.С точки зрения SVM используйте, преобразованный в задачу QP для решения, что также является основным содержанием этого урока.

Соответствующая модель на приведенном выше рисунке также может быть преобразована в двойную форму и введено ядро ​​Общая блок-схема выглядит следующим образом:

Среди них SVM, SVR и вероятностный SVM могут быть решены с помощью библиотечной функции LLibsvm, разработанной доктором Чжи-Джен Лином из Национального Тайваньского университета. Вообще говоря, SVR и вероятностный SVM являются наиболее часто используемыми из этих моделей.

Суммировать

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