Автор молодец, просто работа не нужна больше
Информация о работе
Подробнее о работе
Сравнительный анализ оптимизационных подходов к решению задачи классификации
- 49 страниц
- 2019 год
- 22 просмотра
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Введение 3
1. Постановка задачи классификации 5
1.1. Случай линейной разделимости 5
1.2. Случай линейной неразделимости 7
2. Способы регуляризации 9
2.1. 𝐿2 регуляризация 10
2.2. 𝐿1 регуляризация 10
2.3. Комбинированный метод регуляризации 12
3. Методы расщепления 13
4. Эксперименты 17
4.1. Сравнение решений задач классификации с 𝐿1и 𝐿2 регуляризацией.
........................................................................................................................................17
4.2. Сравнение эффективности SVM с 𝐿1, 𝐿2 и комбинированной
регуляризациями 27
4.3. Вычислительная сложность метода расщепления 29
Заключение 30
Список литературы 31
Приложения 33
Введение
Работа посвящена изучению методов бинарной классификации на
основе машины опорных векторов [1] (англ. SVM, suрроrt veсtоr maсhine) с различными способами регуляризации. Метод опорных векторов – один из популярных и эффективных алгоритмов машинного обучения, применяемый в задачах линейной и нелинейной классификации, регрессии, а также обнаружения аномальных объектов.
В работе рассматривается линейный подход к задаче бинарной
классификации. Предполагается, что дан обучающий набор 𝑋, 𝑌 = {𝑥𝑖 , 𝑦𝑖 }, где каждый объект 𝑥𝑖 ∈ ℝ𝑛 представлен вектором в 𝑛-мерном пространстве признаков и имеет метку класса 𝑦𝑖 ∈ {+1 , −1}. Задача заключается в
построении модели-классификатора на основе обучающей выборки для того,
чтобы спрогнозировать метку нового объекта 𝑥 ∈ ℝ𝑛 .
Однако при решении задач классификации могут возникнуть такие проблемы, как избыточность признаков объекта, что связано с опасностью переобучения, и наличие шумов, неточностей в значениях признаков может сказаться на решении.
...
1.1. Случай линейной разделимости
Для начала рассмотрим простейший случай: линейно-разделимой выборки [1]. Допустим, что дан тренировочный набор точек с метками
𝑥𝑖 , 𝑦𝑖 , 𝑖 = 1 , 𝑙, 𝑥𝑖 ∈ ℝ𝑛 , 𝑦𝑖 ∈ {−1, 1} и существует гиперплоскость, разделяющая точки с метками −1 от точек с метками 1. Уравнение гиперплоскости имеет следующий вид
< 𝑤, 𝑥 > + 𝑏 = 0, 𝑤, 𝑥 ∈ ℝ𝑛 , 𝑏 ∈ ℝ,
𝑤 − вектор нормали гиперплоскости,
𝑏
𝑤 2
− кратчайшее расстояние от начала координат до гиперплоскости,
𝑛
𝑤 2 = ( 𝑤2)0.5 − Евклидова норма вектора 𝑤.
𝑖=1
Пусть 𝑑+ (𝑑−) – расстояние от гиперплоскости до ближайшей к ней точки с меткой +1 (−1). Сумму 𝑑+ + 𝑑− назовем зазором. В случае линейной разделимости, задача состоит в том, чтобы максимизировать этот зазор.
Допустим, весь тренировочный набор удовлетворяет следующим неравенствам:
< 𝑤, 𝑥𝑖 > + 𝑏 ≤ −1 ∀ 𝑖: 𝑦𝑖 = −1, (1)
< 𝑤, 𝑥𝑖 > + 𝑏 ≥ 1 ∀ 𝑖: 𝑦𝑖 = 1.
...
1.2. Случай линейной неразделимости
Для решения задачи классификации на линейно неразделимом наборе точек мы можем развить описанную выше идею следующим образом.
Добавив неотрицательные переменные 𝜉𝑖 , 𝑖 = 1 , 𝑙 в ограничения:
1 − 𝑦𝑖 < 𝑤, 𝑥𝑖 > + 𝑏 ≤ 𝜉𝑖 , 𝑖 = 1 , 𝑙
(5)
𝜉𝑖 ≥ 0, 𝑖 = 1 , 𝑙
(6)
Теперь, когда мы смягчили ограничения, вполне логично добавить штрафы в целевую функцию. При ограничениях (5), (6) получим
следующую задачу:
min
𝑤∈ℝ𝑛 ,𝑏∈ℝ
𝑙
→ 𝑤 2 + 𝐶 𝜉𝑖
(7)
𝑖=1
1 − 𝑦𝑖 < 𝑤, 𝑥𝑖 > + 𝑏 ≤ 𝜉𝑖 , 𝑖 = 1 , 𝑙
𝜉𝑖 ≥ 0, 𝑖 = 1 , 𝑙
Здесь значение гиперпараметра С ≥ 0 задано заранее. Заметим, что при
𝐶 → ∞ задача (7) принимает следующий вид
𝑙
min
𝑤∈ℝ𝑛 ,𝑏∈ℝ
𝜉𝑖
𝑖=1
(8)
1 − 𝑦𝑖 < 𝑤, 𝑥𝑖 > + 𝑏 ≤ 𝜉𝑖 , 𝑖 = 1 , 𝑙, 𝜉𝑖 ≥ 0, 𝑖 = 1 , 𝑙
Рисунок 2 - Разделяющая гиперплоскость в случае линейной неразделимости.
...
2. Способы регуляризации
Метод опорных векторов и многие другие алгоритмы машинного обучения чувствительны к масштабам признаков. На левом графике рисунка 3 изображены точки, у которых масштаб по вертикали сильно превышает масштаб по горизонтали, поэтому разделяющая гиперплоскость близка к горизонтальной прямой, на правом графике изображены нормализованные данные и разделяющая гиперплоскость.
Рисунок 3 - Разделяющая гиперплоскость при разных масштабах признаков.
Самый простой и распространенный способ нормализации – каждый признак привести к нулевому среднему и единичному среднеквадратичному отклонению. Самое главное преимущество нормализации – регуляризация весов. Однако у нормализации есть и недостатки: необходимость хранить
среднее значение и среднеквадратическое отклонение обучающей выборки, что не выгодно при больших размерностях задачи. Поэтому были
разработаны методы автоматической регуляризации в процессе обучения.
...
2.3. Комбинированный метод регуляризации
Рассмотренные выше способы регуляризации имеют свои
преимущества и недостатки. Дальнейшее развитие методов регуляризации натолкнуло к идее комбинирования 𝐿1 и 𝐿2 регуляризаций, то есть
использования выпуклой комбинации 𝑤 1 и 𝑤 2 [4].
𝛽
min → 𝑤 2 + (1 − 𝛽) 𝑤
𝑤∈ℝ𝑛 ,𝑏∈ℝ 2 2 1
𝑙
+ С (max 0, 1 − 𝑦𝑖 < 𝑤, 𝑥𝑖 > + 𝑏 )2 (14)
𝑖=1
где 𝛽 ∈ [0, 1].
При 𝛽 = 1, получается задача (12), а при 𝛽 = 0 – задача (13). Чем ближе 𝛽 к 1, тем больше решение будет обладать свойствами 𝐿2
регуляризации, чем ближе к 0, тем больше решение будет обладать
свойствами 𝐿1 регуляризации. При 𝛽 близком к 0.5 решение будет обладать комбинированным свойством обоих регуляризаций. Таким образом решение задачи (14) будет обладать свойством группировки весовых коэффициентов,
то есть группа весов, имеющих высокую попарную корреляцию, либо примет ненулевые значения, если она имеет высокую информативность, либо
останется нулевой, если вклад в качество предсказаний незначителен.
...
3. Методы расщепления
Пусть имеется оптимизационная задача
min → 𝑓 𝑣 + (𝑣) (15)
𝑣∈𝑉
Здесь функция 𝑓: ℝ𝑛 → ℝ - гладкая, но не обязательно выпуклая, а функция
: ℝ𝑛 → ℝ – не обязательно гладкая, но выпуклая, допустимое множество 𝑉 – непустое, выпуклое и замкнутое множество в пространстве ℝ𝑛 . Получается задача невыпуклой недифференцируемой оптимизации, которая достаточно сложно решается обычными субградиентными методами.
Однако для этого существуют методы расщепления [2, 3], которые позволяют итеративно определять на итерации 𝑘 = 0, 1, … новую точку 𝑣𝑘+1, решая следующее неравенство
< 𝑓′ 𝑣𝑘 + 𝜏−1 𝑣𝑘+1 − 𝑣𝑘 , 𝑣 − 𝑣𝑘+1 > + 𝑣 − 𝑣𝑘+1 ≥ 0
∀𝑣 ∈ 𝑉 ⊆ ℝ𝑛 , (16)
где параметр 𝜏𝑘 > 0 определяет длину шага.
...
4. Эксперименты
4.1. Сравнение решений задач классификации с 𝑳𝟏и 𝑳𝟐
регуляризацией
Напомним задачу оптимизации с 𝐿1 регуляризацией
𝑙
min
𝑤∈ℝ𝑛 ,𝑏∈ℝ
→ 𝑤 1 + С ∗ (max 0, 1 − 𝑦𝑖 < 𝑤, 𝑥𝑖 > + 𝑏 )2
𝑖=1
и с 𝐿2 регуляризацией
𝑙
min
𝑤∈ℝ𝑛 ,𝑏∈ℝ
→ 𝑤 2 + С ∗ (max 0, 1 − 𝑦𝑖 < 𝑤, 𝑥𝑖 > + 𝑏 )2
𝑖=1
Для решения этих задач был использован ранее описанный метод расщепления. А для поиска длины шага был использован метод деления отрезка пополам. Процесс поиска длины шага (деления отрезка)
останавливается, если длина отрезка стала достаточно маленькой, в частности, при решении описанных ниже задач – меньше, чем 10−7.
a. Сгенерированный набор точек
Был сгенерирован набор из 400 точек из пространства ℝ2. Классы представлены в соотношении 1:1. В тренировочном наборе 300 точек, в тестовом - 100. Сгенерированные точки визуализированы и представлены на рисунке 5.
ниже.
Рисунок 5 - График точек
Таблица результатов классификации в двумерном случае представлена
𝐶
Точность классификации a.
...
классификации с 𝐿2 регуляризацией, его модификация c 𝐿1 регуляризацией, а также комбинированная, с 𝐿1 и 𝐿2 регуляризациями [4], основанные на
методе опорных векторов, рассмотрен способ решения оптимизационных задач методом расщепления [2,3].
В результате работы ожидается получить эффективный метод решения задач классификации с точки зрения скорости поиска решения и простоты
полученного решения, при котором точность классификации будет не хуже по сравнению существующими методами.
1. Постановка задачи классификации
1.1. Случай линейной разделимости
Для начала рассмотрим простейший случай: линейно-разделимой выборки [1]. Допустим, что дан тренировочный набор точек с метками
𝑥𝑖 , 𝑦𝑖 , 𝑖 = 1 , 𝑙, 𝑥𝑖 ∈ ℝ𝑛 , 𝑦𝑖 ∈ {−1, 1} и существует гиперплоскость, разделяющая точки с метками −1 от точек с метками 1.
...
Заключение
По результатам проделанной работы можно сделать вывод, что задачи
𝐿1 и 𝐿2 регуляризации обеспечивают наиболее точную классификацию при небольших значениях параметра регуляризации 𝐶. Точность классификации при правильно подобранных параметрах практически одинакова. Однако 𝐿1 в отличие от 𝐿2 обладает свойством отбора весов, как было замечено ранее, при этом точность не становится хуже. Стоит отметить, что комбинированный метод регуляризации позволяет объединить свойства обоих регуляризаторов, точность классификации при этом также не хуже, однако требует больше вычислительных затрат.
Свойство отбора весов означает, что 𝐿1 регуляризация по сравнению с
𝐿2 дает более разреженное решение, то есть облегченную модель классификатора, среди коррелирующих между собой весов оставляет ненулевыми наиболее информативные, а наименее значимые веса или веса, увеличение которых приводит к большему штрафу регуляризации, чем
штрафу за ошибки классификации, обнуляет.
...
[1] Christoger Burges, J.C. A Tutorial on Support Vector Machine for pattern recognition, Kluwer Academic Publishers. – 1998. – 7-16 c.
[2] Коннов, И.В. Нелинейная оптимизация и вариационные неравенства, Казанский университет – 2013. – 379-381 с.
[3] Konnov, I.V. Sequential threshold control in descent splitting methods for decomposable optimization problems, Optimization Methods and Software. – 2015. – 1-4 с.
[4] Wang L., Zhu J., Zou H., The doubly regularized support vector machine, Statistica Sinica. – 2006. – 3-7 с.
[5] Ссылка на набор данных Heart Disease (диагностика сердечных заболеваний) [Электронный ресурс]. – URL:
https://www.kaggle.com/ronitf/heart-disease-uci (дата обращения 26.01.2019)
[6] Ссылка на набор данных Voice (определение пола человека по акустическим характеристикам) [Электронный ресурс]. – URL: https://www.kaggle.com/primaryobjects/voicegender (дата обращения 24.01.2019)
[7] Ссылка на набор данных MNIST (классификация рукописных цифр) [Электронный ресурс]. – URL: https://www.kaggle.com/c/digit- recognizer/overview (дата обращения 24.12.2018)
[8] Ссылка на набор данных Epileptic Seizure (обнаружение эпилептических припадков) [Электронный ресурс]. – URL: https://archive.ics.uci.edu/ml/datasets/Epileptic+Seizure+Recognition (дата обращения 14.04.2019)
[9] Ссылка на набор данных Biodegradation (классификация химических веществ) [Электронный ресурс]. – URL: https://archive.ics.uci.edu/ml/datasets/QSAR+biodegradation (дата обращения 15.04.2019)
[10] Ссылка на набор данных Biodegradation (прогнозирование выпадения осадков) [Электронный ресурс]. – URL:
https://www.kaggle.com/jsphyg/weather-dataset-rattle- package/downloads/weather-dataset-rattle-package.zip/2 (дата обращения 15.04.2019)
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
