Этот кураторский список алгоритмов для обучения моделей машинного обучения, которые часто задают во время интервью MLE/MLS.
[Это часть I из трех частей Обновление интервью ML]
SVM
Представьте, что у вас есть набор данных с двумя классами, представленными точками в двумерном пространстве. Цель состоит в том, чтобы найти границу решения, которая как можно лучше разделяет два класса.
Рабочий процесс SVM:
1. Представление данных:
Допустим, у нас есть обучающий набор данных, состоящий из входных признаков X и соответствующих меток класса y. Каждый обучающий пример представлен как (xᵢ, yᵢ), где xᵢ — вектор входных признаков, а yᵢ — соответствующая метка класса (+1 или -1).
2. Маржа и граница решения.
Алгоритм SVM стремится найти гиперплоскость, которая разделяет два класса с максимально возможной маржой. Поле — это расстояние между гиперплоскостью и ближайшими точками данных для каждого класса. Гиперплоскость определяется уравнением:
wᵀx + b = 0
Здесь w — вектор нормали к гиперплоскости, x — вектор входных признаков, а b — член смещения.
3. Максимальная маржа:
SVM выбирает гиперплоскость, которая максимизирует маржу, но при этом правильно классифицирует обучающие примеры. Поле вычисляется как расстояние между гиперплоскостью и ближайшими точками данных для каждого класса. Эти ближайшие точки называются опорными векторами, отсюда и название «Машины опорных векторов».
4. Формулировка задачи оптимизации.
Чтобы найти оптимальную гиперплоскость, SVM формулирует задачу оптимизации. Он направлен на минимизацию нормы вектора весов (||w||) при условии, что все обучающие примеры правильно классифицированы в соответствии с их метками классов:
минимизировать: (1/2) * ||w| |²
при условии: yᵢ * (wᵀxᵢ + b) ≥ 1
для всех обучающих примеров (xᵢ, yᵢ)
Целевая функция (1/2) * ||w||² представляет собой член регуляризации, который способствует нахождению гиперплоскости с большим запасом, а ограничение неравенства обеспечивает правильную классификацию.
5. Решение задачи оптимизации.
Задача оптимизации обычно решается с использованием методов квадратичного программирования или оптимизации. Метод множителя Лагранжа используется для вывода двойственной задачи, что приводит к задаче квадратичной оптимизации, которую можно эффективно решить.
6. Опорные векторы и правило принятия решения.
Обучающие примеры, лежащие на границе или нарушающие границы, являются опорными векторами. Эти опорные векторы играют решающую роль в определении границы решения.
Правило принятия решения для классификации нового тестового примера x может быть получено из изученных весов и смещений следующим образом:
Если wᵀx + b > 0, предсказать класс +1. class -1.
Знак скалярного произведения wᵀx + b определяет метку класса.
SVM находит оптимальную гиперплоскость, которая максимизирует запас и разделяет классы, при этом опорные векторы играют решающую роль в границе решения. Задача оптимизации обеспечивает правильную классификацию при минимизации нормы весового вектора.
Краммер-Зингер SVM
Crammer-Singer SVM — это многоклассовое расширение машин опорных векторов (SVM), которое напрямую формулирует задачу оптимизации для многоклассовой классификации. Это позволяет избежать необходимости преобразования проблемы в несколько задач бинарной классификации с использованием подходов «один против одного» или «один против остальных». Вместо этого он оптимизирует совместную целевую функцию, чтобы найти единую границу решения для всех классов.
Рабочий процесс Crammer-Singer:
1. Представление данных:
Давайте рассмотрим задачу мультиклассовой классификации с K классами. У нас есть обучающий набор данных, состоящий из входных признаков X и соответствующих меток класса y. Каждый обучающий пример представлен как (xᵢ, yᵢ), где xᵢ — вектор входных признаков, а yᵢ — соответствующая метка класса. Метки класса yᵢ представляют собой векторы с горячим кодированием, где только один элемент равен 1, что указывает на истинный класс.
2. Целевая функция:
SVM Crammer-Singer стремится минимизировать совместную целевую функцию, которая включает в себя как максимизацию запаса, так и точность классификации. Целевая функция определяется как:
минимизировать: 1/2 ||w||² + C * ξ
при условии: (wᵀφ(xᵢ) — wᵀφ(xⱼ))yᵢ ≥ 1 — ξ
- ξ ≥ 0 для всех обучающих примеров (xᵢ, yᵢ)
- w - весовой вектор
- φ(x) — это карта объектов, которая неявно отображает входные объекты x в многомерное пространство.
- C — параметр регуляризации, который контролирует компромисс между максимизацией маржи и ошибкой обучения.
- ξ — переменная запаса, допускающая некоторые ошибки обучения.
- Первый член целевой функции,
- 1/2 ||w||² представляет цель максимизации маржи, аналогичную стандартной SVM.
- Второй член, C * ξ, наказывает ошибки обучения.
- Ограничение гарантирует, что оценка правильного класса (wᵀφ(xᵢ)) выше, чем оценки других классов (wᵀφ(xⱼ)) с запасом не менее 1 — ξ.
3. Оптимизация:
целевая функция решается с использованием методов оптимизации, таких как квадратичное программирование или методы на основе градиента. Процесс оптимизации направлен на поиск оптимальных значений вектора весов w и резервных переменных ξ, которые минимизируют целевую функцию при соблюдении ограничений.
4. Классификация.
Чтобы классифицировать новый тестовый пример x, в качестве прогнозируемой метки класса выбирается класс с наивысшим баллом. Оценки класса рассчитываются как wᵀφ(x), где w — изученный вектор весов, полученный в результате оптимизации.
Crammer-Singer SVM напрямую изучает единую границу решения для всех классов, рассматривая совместную задачу оптимизации. Он направлен на максимизацию разницы между классами при обеспечении правильной классификации. Он может эффективно обрабатывать многоклассовую классификацию и устраняет необходимость преобразования проблемы в несколько бинарных задач.
Стоит отметить, что SVM Crammer-Singer — это всего лишь один из подходов к формулировке многоклассового SVM, и также доступны другие методы, такие как «один против одного» и «один против остальных». Выбор рецептуры зависит от конкретной проблемы и требований.
Трюк с ядром в SVM
Уловка ядра — это метод, используемый в машинном обучении, особенно в машинах опорных векторов (SVM), для неявного преобразования входных признаков в многомерное пространство признаков без явного вычисления преобразованных признаков. Это позволяет SVM эффективно обрабатывать нелинейные границы решений и сложные распределения данных.
Концепцию трюка с ядром можно объяснить следующим образом:
1. Линейный SVM и нелинейные данные:
SVM с линейным ядром могут эффективно разделять данные, когда классы линейно разделимы. Однако многие наборы данных реального мира не являются линейно разделимыми. В таких случаях для точной классификации данных требуется нелинейная граница решения.
2. Отображение в многомерное пространство.
Хитрость ядра позволяет нам неявно отображать исходные входные объекты в многомерное пространство признаков, где классы могут стать линейно разделимыми. Это преобразование выполняется с помощью функции ядра, которая вычисляет сходство или внутренний продукт между парами точек данных в многомерном пространстве.
3. Функция ядра.
Функция ядра измеряет сходство между двумя образцами без явного вычисления преобразованных признаков в многомерном пространстве. Он напрямую работает с исходным пространством входных признаков, делая вычисления более эффективными. Часто используемые функции ядра включают:
* Линейное ядро: K(x, y) = xᵀy
* Полиномиальное ядро: K(x, y) = (αxᵀy + c)ᵈ
* Гауссово ( RBF) Ядро: K(x, y) = exp(-γ||x-y||²)
Здесь x и y — векторы входных признаков, α, c, d и γ — параметры ядра.
4. Обучение и классификация.
Используя трюк с ядром, SVM можно обучать и применять в исходном входном пространстве признаков, неявно работая в многомерном пространстве признаков. Задача оптимизации SVM формулируется с использованием функции ядра, что позволяет изучать сложные нелинейные границы решений.
5. Преимущества трюка с ядром:
трюк с ядром позволяет SVM фиксировать сложные шаблоны и нелинейные отношения в данных без явного вычисления преобразованных признаков. Он предлагает следующие преимущества:
– Позволяет обрабатывать нелинейные границы решений.
– Избегает вычислительных затрат на явное преобразование признаков в многомерное пространство.
– Может работать с бесконечномерными пространствами признаков (например, с ядром Гаусса).< br /> - Поддерживает эффективное обучение и вывод.
Трюк с ядром — это мощный инструмент в SVM, поскольку он позволяет эффективно обрабатывать нелинейные и сложные распределения данных. Это позволяет SVM неявно работать в многомерных пространствах признаков, открывая возможность точной классификации данных, которые не могут быть линейно разделены в исходном пространстве входных признаков.
Логистическая регрессия
Логистическая регрессия — это популярный алгоритм, используемый для задач бинарной классификации. Он моделирует взаимосвязь между входными функциями и вероятностью того, что целевая переменная принадлежит определенному классу. Алгоритм оценивает параметры логистической функции, чтобы делать прогнозы.
Рабочий процесс логистической регрессии:
1. Представление данных:
Обучающие данные состоят из векторов входных признаков X и соответствующих меток двоичного класса y. Каждый обучающий пример представлен как (xᵢ, yᵢ), где xᵢ — вектор входных признаков, а yᵢ — метка двоичного класса (0 или 1).
2. Логистическая функция (сигмовидная).
Логистическая регрессия использует логистическую функцию, также известную как сигмовидная, для моделирования вероятности того, что целевая переменная находится в классе 1.
Сигмовидная функция определяется как:
σ(z) = 1 / (1 + exp(-z))
, где z — это линейная комбинация входных признаков и соответствующих весов.
3. Функция гипотезы:
Функция гипотезы логистической регрессии определяется следующим образом:
hθ(x) = σ(θᵀx)
Здесь hθ(x) представляет прогнозируемую вероятность целевой переменной. находясь в классе 1 для вектора входных признаков x, θ — вектор весов (параметров), а x — вектор входных признаков.
4. Функция стоимости:
Функция стоимости в логистической регрессии представляет собой логарифмическую функцию потерь (также называемую функцией кросс-энтропийных потерь) и определяется как:
J(θ) = -(1/m) * Σ [yᵢ * log(hθ(xᵢ)) + (1-yᵢ) * log(1 — hθ(xᵢ))]
где m — количество обучающих примеров, yᵢ — истинная метка класса (0 или 1) для i-го примера, а hθ(xᵢ) — прогнозируемая вероятность для i-го примера.
Функция стоимости наказывает большие ошибки в прогнозах и направлена на минимизацию несоответствия между прогнозируемыми вероятностями и истинные этикетки.
5. Оптимизация:
Цель состоит в том, чтобы найти оптимальные значения вектора весов θ, которые минимизируют функцию стоимости. Обычно это достигается с помощью алгоритмов оптимизации, таких как градиентный спуск. Алгоритм градиентного спуска итеративно обновляет веса, чтобы найти минимум функции стоимости.
6. Граница решения и прогноз.
После оптимизации весов граница решения определяется на основе порога вероятности (обычно 0,5). Если прогнозируемая вероятность выше порога, пример классифицируется как класс 1; в противном случае он классифицируется как класс 0.
Чтобы делать прогнозы на новых примерах, входные признаки передаются через функцию гипотезы, а полученная вероятность сравнивается с порогом для определения прогнозируемого класса.
Логистическая регрессия — это простой и интерпретируемый алгоритм, который хорошо работает, когда граница принятия решений между классами относительно линейна. Он широко используется в различных приложениях, и такие расширения, как полиномиальная логистическая регрессия, могут использоваться для многоклассовой классификации.
Логистическую регрессию также можно расширить для решения проблем классификации нескольких классов, используя один из следующих подходов: один против остальных (один против всех) или полиномиальную логистическую регрессию (регрессия softmax).
Подход "один против остальных" (один против всех) для многоклассовой классификации
В подходе «один против остальных» для каждого класса обучается отдельная модель логистической регрессии, которая рассматривается как положительный класс, а остальные классы рассматриваются как отрицательный класс. Шаги, связанные с этим подходом, следующие:
Представление данных: обучающие данные состоят из векторов входных признаков X и соответствующих меток классов y, где y может принимать несколько дискретных значений, представляющих разные классы.
Обучение модели: для каждого класса бинарная модель логистической регрессии обучается независимо. Во время обучения положительный класс устанавливается на текущий рассматриваемый класс, а все остальные классы рассматриваются как отрицательный класс.
Прогноз: Чтобы делать прогнозы, каждая модель бинарной логистической регрессии используется для прогнозирования вероятности того, что входные данные принадлежат положительному классу. Класс с наибольшей вероятностью выбирается в качестве прогнозируемой метки класса.
Подход «один против остальных» преобразует проблему многоклассовой классификации в задачи множественной бинарной классификации. Он может обрабатывать несбалансированные распределения классов и позволяет интерпретировать границы решений для конкретных классов. Однако он может столкнуться с перекрывающимися или сильно коррелированными классами.
Полиномиальная логистическая регрессия (регрессия Softmax) для многоклассовой классификации
Полиномиальная логистическая регрессия, также известная как регрессия softmax, напрямую моделирует вероятности входных данных, принадлежащих каждому классу. Он обобщает логистическую регрессию для одновременной обработки нескольких классов. Шаги, связанные с этим подходом, следующие:
Представление данных: обучающие данные состоят из векторов входных признаков X и соответствующих меток классов y, где y может принимать несколько дискретных значений, представляющих разные классы.
Обучение модели: функция softmax используется в качестве функции активации. Модель изучает набор весов для каждого класса и присваивает вероятность каждому классу. Веса обучаются, чтобы максимизировать вероятность наблюдаемых меток классов.
Прогноз: чтобы делать прогнозы, входные функции передаются через обученную модель, что приводит к вероятности класса для каждого входа. Класс с наибольшей вероятностью выбирается в качестве прогнозируемой метки класса.
Полиномиальная логистическая регрессия напрямую моделирует совместное распределение вероятностей по всем классам с учетом их отношений. Он обеспечивает единый подход к многоклассовой классификации и может фиксировать сложные взаимодействия между классами. Однако он может быть чувствителен к несбалансированному распределению классов и требует больше вычислительных ресурсов по сравнению с подходом «один против остальных».
Оба подхода расширяют логистическую регрессию для задач мультиклассовой классификации, каждый из которых имеет свои преимущества и ограничения. Выбор между ними зависит от конкретной задачи, характеристик данных и требований к интерпретируемости.
