Введение в метод опорных векторов 0:09 Лекция продолжает обсуждение линейных моделей классификации и регрессии. Фокус на методе опорных векторов, который считается одним из лучших методов классификации наряду с нейронными сетями и бустингом.
Основы метода опорных векторов 1:00 Обсуждение основ метода, обобщений и регуляризаторов. Обозначения: обучающая выборка, объекты с n числовыми признаками, ответы +1 или -1.
Конструкция линейного классификатора 2:00 Линейный классификатор определяется скалярным произведением вектора признаков на вектор весов. Использование свободного члена для сравнения скалярного произведения. Критерий оптимизации — минимум эмпирического риска.
Аппроксимация функции потерь 2:59 Замена разрывной функции потерь на непрерывную. Введение понятия отступа как расстояния от объекта до разделяющей гиперплоскости. Пример аппроксимации пороговой функции потерь.
Регуляризация и метод опорных векторов 4:25 Применение квадратичных регуляризаторов для борьбы с мультиколлинеарностью и переобучением. Принцип метода опорных векторов: аппроксимация пороговой функции потерь и регуляризация.
Принцип оптимально разделяющей гиперплоскости 6:16 Линейная разделимость выборки и система неравенств. Задача поиска максимальной совместной подсистемы. Нормировка системы неравенств для минимального отступа, равного единице.
Эвристика для разделяющей гиперплоскости 8:39 Принцип максимальной ширины разделяющей полосы между классами. Доказательство, что максимально широкая полоса упирается в объекты обучающей выборки. Определение положения точки в пространстве относительно разделяющей гиперплоскости через выражение отступа.
Геометрическое место точек 10:30 Разделяющая полоса как геометрическое место точек, удовлетворяющих определённому неравенству. Выбор пограничных точек в классах +1 и -1 для определения положения точки в пространстве.
Ширина разделяющей полосы 11:10 Для определения ширины разделяющей полосы нужно взять разность векторов x+ и x- и спроецировать её на нормаль разделяющей гиперплоскости. Проекция вычисляется через скалярное произведение с нормированным вектором. Ширина полосы равна 2, делённой на норму вектора.
Смысл регуляризатора 11:49 Максимизация ширины полосы эквивалентна минимизации нормы вектора. Регуляризатор помогает максимизировать ширину полосы при определённых ограничениях. Геометрический смысл задачи связан с минимизацией нормы вектора.
Принцип оптимальности разделяющей гиперплоскости 12:49 В линейно-разделимом случае задача сводится к квадратичному программированию. В общем случае система неравенств может быть несовместной, поэтому ограничения ослабляются. Вводятся дополнительные переменные k_i для штрафа за нарушение неравенств.
Модификация задачи 13:46 Минимизируются норма вектора весов и сумма штрафных коэффициентов k_i. Функционалы взвешиваются с константой c. Новая задача всегда совместна благодаря дополнительным переменным.
Эквивалентность задач 14:45 Доказывается эквивалентность исходной и модифицированной задач. Из всех решений выбирается то, у которого сумма k_i минимальна.
Методы оптимизации 16:36 Кусочно-линейная функция потерь не является гладкой, поэтому стандартные методы оптимизации неприменимы. Используются субградиентные методы или метод опорных векторов. Метод опорных векторов основан на решении задачи квадратичного программирования.
Введение в условия Куна-Таккера 17:42 Условия Куна-Таккера используются для решения задач квадратичного программирования с ограничениями равенства и неравенства. Они представляют собой инструмент для оптимизации, который нужно уметь применять.
Выписывание лагранжиана 18:35 Лагранжиан — это линейная комбинация функционала и ограничений. Для решения задачи необходимо выписать лагранжиан, приравнять нулю производные и учесть все типы ограничений.
Применение условий Куна-Таккера 20:25 Согласно условиям Куна-Таккера, все производные по параметрам должны быть равны нулю. Получаются три важных условия, которые будут использоваться в дальнейшем.
Определение вектора решения 21:11 Вектор решения выражается через двойственные переменные лямбда. Если лямбда равна нулю, решение не зависит от данного объекта обучающей выборки. Объекты, от которых решение зависит, называются опорными векторами.
Типы объектов по значениям лямбда 22:09 Объекты делятся на три типа в зависимости от значений лямбда: лямбда равна нулю, лямбда в интервале от 0 до c, лямбда меньше нуля. Первый тип объектов не является опорным, второй тип — опорные граничные объекты, третий тип — опорные нарушители.
Выпуклая задача 27:06 Задача квадратичного программирования относительно переменных лямбда является выпуклой. Решение гарантированно будет единственным.
Численные методы решения 28:04 Для решения задачи используются специализированные численные методы, учитывающие специфику функционала и ограничений. Методы, разработанные для больших данных, работают эффективно. Основная идея методов — использование эвристик для быстрого поиска решений, особенно когда опорных векторов немного.
Решение задачи и нахождение вектора 29:31 Подставляем полученное решение лямбда-иты в выражение и находим вектор-дубль в. Определяем дубль в ноль, выбирая объекты с отступом, равным единице. Записываем линейный классификатор в новом виде, используя скалярное произведение вектора дубль в и вектора икса.
Новый вид классификатора 30:29 Классификатор остаётся линейным, но теперь по коэффициентам лямда. Вместо признаков выступают скалярные произведения объекта икса с обучающими объектами. Число признаков равно числу обучающих объектов.
Вычисление близости объектов 31:24 Вычисляем близость объекта икса до опорных объектов обоих классов. Складываем близости с коэффициентами лямда и сравниваем результаты. Метод опорных векторов сравнивает объекты с опорными объектами через скалярное произведение.
Вопрос о скалярном произведении 32:55 Обсуждается возможность замены скалярного произведения более общей функцией близости. В постановке задачи фигурируют только скалярные произведения исходных объектов.
Подбор константы ц 33:50 Константа ц подбирается для совмещения критериев ширины разделяющей полосы и минимума штрафов за нарушение ограничений. Большой коэффициент ц соответствует слабой регуляризации, а уменьшение ц усиливает регуляризацию. Решение слабо зависит от выбора константы ц, её можно подбирать в широком диапазоне.
Идея спрямляющего пространства 36:12 Рассматривается возможность замены скалярного произведения функцией от пары объектов. Функция должна быть симметричной и неотрицательно определённой. Преобразование объектов в новое пространство позволяет использовать скалярные произведения этого пространства.
Ядра и их свойства 38:41 Ядро должно удовлетворять требованиям симметрии и неотрицательной определённости. Правила порождения новых ядер: произведение ядер, константа, произведение функции от объекта на ядро. Сумма ядер является ядром только при неотрицательных коэффициентах.
Преобразование ядер 41:51 Преобразование объектов с использованием ядра кано может привести к новому ядру. Симметрично интегрируемая функция от пар объектов может быть свернута в ядро.
Создание нового ядра из существующего 42:25 Для создания нового ядра из существующего необходимо, чтобы функция была представима в виде сходящего степенного ряда с неотрицательными коэффициентами. Примеры таких функций: экспонента и геометрическая прогрессия.
Анализ аналитического выражения 43:16 Аналитическое выражение функции можно представить в виде композиции допустимых преобразований. Если выражение можно представить таким образом, то функция является ядром.
Пример с квадратом скалярного произведения 43:39 Квадрат скалярного произведения является ядром, так как произведение ядер остаётся ядром. Преобразование переводит двумерные векторы в трёхмерное пространство.
Разделяющая поверхность в новом пространстве 45:32 В пространстве размерности три ядро строит гиперплоскость. В исходном пространстве размерности два разделяющая поверхность представляет собой полином.
Построение полиномиальных ядер 46:31 Можно построить полиномиальное ядро, возводя скалярное произведение в степень. Это позволяет перейти от линейных классификаторов к нелинейным.
Аналогия с нейронными сетями 48:29 Использование тангенса гиперболического функции эквивалентно построению нейронной сети с сигмоидными функциями активации. Ядро может быть интерпретировано как радиальные базисные функции в двухслойной нейронной сети.
Принцип работы SVM 50:02 SVM использует ядра для вычисления близости между объектами. Число нейронов скрытого слоя определяется автоматически.
Пример с гауссовским ядром 51:15 Гауссовское ядро вычисляет близость между объектами в евклидовом метрическом пространстве. Экспонента в ряду Тейлора обеспечивает положительные коэффициенты, что делает её ядром.
Преимущества SVM 52:54 SVM сочетает свойства линейного классификатора, метрического классификатора и двухслойной нейронной сети. Решение задачи SVM является выпуклым и имеет единственное решение.
Сложности и оптимизация ядра 53:43 Нет общих подходов к оптимизации ядра под задачу. Обычно используются линейные, полиномиальные ядра и RBF. Принцип максимизации разделяющей полосы повышает обобщающую способность SVM.
Переход от классификации к регрессии 55:00 Использование линейной модели регрессии для предсказания вещественных значений. Введение кусочно-линейной функции потерь: при отклонении до дельты потери нулевые, затем штраф нарастает линейно.
Постановка задачи регрессии 56:02 Применение квадратичного регуляризатора для линейной модели. Сведение задачи к квадратичному программированию путём замены переменных. Необходимость замены переменных для применения условий Карри-Куна-Такера.
Особенности задачи регрессии 56:55 Увеличение количества штрафных переменных для учёта отклонений прогноза. Сохранение вида задачи квадратичного программирования с линейными ограничениями.
Опорные векторы и положительная срезка 57:50 Определение опорных векторов как объектов на границе дельта-трубки или за её пределами. Использование положительной срезки для обработки данных.
Переход к нелинейной регрессии 58:45 Возможность использования ядер для перехода от линейной к нелинейной регрессии.
Свойства L1-регуляризатора 59:10 L1-регуляризатор зануляет коэффициенты, отбирая признаки. Параметр селективности мю контролирует степень отбора признаков.
Проблемы метода Lasso 1:01:18 Возможность отбрасывания значимых признаков при усилении регуляризации. Проблема переобучения на конечной выборке.
Эффект группировки признаков 1:02:39 Необходимость модели, способной выделять значимые признаки независимо от их коллинеарности. Lasso не обладает эффектом группировки.
Математическое обоснование отбора признаков 1:04:57 Замена переменных для устранения негладкости критерия. Увеличение коэффициента мю приводит к обнулению коэффициентов признаков.
Практическое сравнение регуляризаторов 1:07:27 Иллюстрация работы L1- и L2-регуляризаторов на примере задачи классификации с восемью признаками. L1-регуляризатор эффективно отбирает признаки, в то время как L2-регуляризатор не обладает этой способностью.
Эффект группировки и регуляризация 1:08:52 Сумма L1 и L2 регуляризаторов позволяет учитывать эффект группировки признаков. L1 регуляризатор гуманно отбрасывает признаки, предотвращая разбегание коэффициентов. L2 регуляризатор прижимает коэффициенты к нулю, но не зануляет их.
Недостаток эффекта группировки 1:09:46 Эффект группировки может оставить шумовые признаки в модели. Линейная комбинация шумовых признаков может выглядеть как информативный признак. Увеличение коэффициента селективности может привести к удалению важных признаков.
Альтернативные методики регуляризации 1:10:41 Предлагаются альтернативные методики регуляризации для устранения недостатка. Обсуждается проблема определения коэффициентов регуляризации при наличии нескольких регуляризаторов.
Принцип работы Elastic Net 1:12:02 Elastic Net более гуманно относится к коэффициентам, чем Lasso. По мере ослабления регуляризации увеличивается количество признаков в модели.
Регуляризатор для шумовых признаков 1:13:07 Предлагается регуляризатор, который группирует информативные признаки, но подавляет шумовые по одному. Функция регуляризации склеивается из модуля L1 и параболы. При маленьком M шумовые признаки подавляются, а значимые остаются в модели.
Регуляризатор для задач с важными признаками 1:15:22 Для задач, где все признаки важны одновременно, предлагается новый регуляризатор. Регуляризатор обладает эффектом группировки и лучше отбирает значимые признаки.
Применение регуляризаторов 1:16:53 Регуляризаторы применимы не только в SVM, но и в логистической регрессии и других задачах. Комбинирование функций потерь и регуляризаторов позволяет добиваться различных эффектов.
Резюме и общий взгляд 1:18:11 Подчёркивается свобода выбора функций потерь и регуляризаторов. Негладкость функции потерь приводит к отбору опорных объектов. Кернел-трик позволяет сравнивать объекты по скалярному произведению или с помощью ядра.
