🗊Презентация Машина опорных векторов. Лабораторная работа № 5

Лабораторная работа № 5 Машина опорных векторов

Бизнес-задача Задача – отличить фальшивые банкноты от настоящих База Banknote authentification: https://archive.ics.uci.edu/ml/datasets/banknote+authentication Объекты представляют из себя характеристики изображений банкнот 1372 объекта 4 признака: энтропия изображения коэффициенты дисперсии, ассиметрии и эксцесса вейвлет-преобразования изображения Класс (фальшивые или настоящие)

Бизнес-задача Способ решения – классификация Метод классификации – SVM (Support Vector Machine) Положительные стороны SVM: быстрый метод классификации; метод сводится к решению задачи квадратичного программирования в выпуклой области, которая обычно имеет единственное решение; метод позволяет осуществлять более уверенную классификацию, чем другие линейные методы.

Метод Support Vector Machine Изобретён в 1963 году, авторы – Вапник, Червоненкис Современная постановка в 1995 году Классификатор – разделяющая гиперплоскость Гиперплоскость является наилучшей в смысле ширины «разделяющей полосы» Точки на границах «полосы» называются «опорными» - отсюда название В чём смысл увеличивать ширину полосы?

Математическая постановка Пусть даны два линейно разделимых класса объектов Мы можем описать все точки разделяющей гиперплоскости используя вектор-нормаль к этой гиперплоскости: Данная разделяющая гиперплоскость находится в «разделяющей полосе», которую мы также можем задать уравнениями:

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

Решение оптимизационной задачи Метод множителей Лагранжа: Производные: Двойственная проблема:

Случай линейно неразделимой выборки

Случай линейно неразделимой выборки Метод множителей Лагранжа: Производные: Двойственная проблема:

Предсказание Для предсказания результата алгоритма, используется функция sign: Для λi=0 точка xi не является «опорной», таким образом, в сумму, которая определяет класс нового объекта, влияние вносят только «опорные» точки.

Использование метода SVM Использован набор данных Banknote Authentification В качестве тестовой выборки взяты 107 последних объектов класса «0» (настоящие банкноты) и 119 объектов класса «1» (фальшивки). Остальные объекты используются в качестве обучающей выборки. Исходные параметры алгоритмов SVM взяты одинаковыми для разных библиотек.

Обучение модели, Intel DAAL

Предсказание, Intel DAAL

Предсказание, Intel DAAL

Алгоритм SVM, Python, R

Результаты вычислений для данных Banknote Authentification Результаты вычислений(суммарное время получения модели + предсказание, количество ошибок) с одинаковыми параметрами: DAAL: ~0.021 секунды, 2 ошибки Python: ~0.007 секунды, 2 ошибки R: ~0.14 секунды, 7 ошибок

Ядра (Kernel Trick) Ядро – функция специального вида: Симметричная Неотрицательно определенная Ядро используется вместо линейного скалярного произведения точек:

Kernel Trick Функция ядра переводит точки в пространство большей размерности. Пример:

Пример использования ядра  

Виды ядер  

Предсказание Для предсказания результата алгоритма, используется функция sign: Для λi=0 точка xi не является «опорной», таким образом, в сумму, которая определяет класс нового объекта, влияние вносят только «опорные» точки.

Результаты вычислений для данных Banknote Authentification Результаты вычислений (суммарное время получения модели + предсказание, количество ошибок): DAAL: ~2.5 секунды, 2 ошибки Python: ~0.014 секунды, 0 ошибок R: ~0.065 секунды, 1 ошибка Почему результаты получились разные?

Результаты вычислений для данных Banknote Authentification Результаты вычислений(суммарное время получения модели + предсказание, количество ошибок) с ядром radial и стандартными параметрами(200 MB кэш, большое количество итераций): DAAL: ~0.024 секунды, 0 ошибок Python: ~0.007 секунды, 0 ошибок R: ~0.065 секунды, 1 ошибка

Результаты вычислений для данных Banknote Authentification Результаты вычислений(суммарное время получения модели + предсказание, количество ошибок) с ядром radial и одинаковыми заданными параметрами (gamma = 1,iterations = no_limit): DAAL: ~0.035 секунды, 0 ошибок Python: ~0.061 секунды, 0 ошибок R: ~0.052 секунды, 0 ошибок

Набор данных Adult Income*

Признаки

Набор данных Adult Income*

Результаты вычислений для данных Adult Income Результаты вычислений: DAAL: ~400 секунд, точность 0.63 (линейное ядро, после бинаризации, 200000 итераций, точность 0.001) Python: ~20 секунд, точность 0.75(линейное ядро, после бинаризации, 100000 итераций, точность 0.001, сходимость не достигнута) Python: ~40 секунд, точность 0.56(линейное ядро, после бинаризации, 200000 итераций, точность 0.001, сходимость не достигнута) Python: ~2400 секунд, точность 0.79(линейное ядро, после бинаризации, без ограничения на количество итераций, точность 0.001, сходимость достигнута) Python ~150 секунд, точность 0.75(ядро rbf, после бинаризации, 100000 итераций, точность 0.001, сходимость достигнута) R: ~64 секунды, точность 0.848 (ядро rbf, без бинаризации) R: ~430 секунд, точность 0.839 (ядро rbf, после бинаризации) R: ~80 секунд, точность 0.846 (ядро linear, без бинаризации)

Результаты вычислений для данных Adult Income

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

Практическое задание Проанализировать разные результаты для набора данных Banknote Authentification, в чём разница базовых настроек алгоритма в разных инструментах? Найти наилучшие параметры для данных Banknote Authentification, используя технику кросс-валидации. Возможно ли улучшить точность алгоритма для данных Adult Income, используя другие параметры (gamma, C, параметры связанные с SVM)? Подобрать параметры, дающие большую точность или показать, что для большого набора параметров точность улучшить не удаётся.

Ссылки на реализации алгоритма http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf - LIBSVM: A Library for Support Vector Machines, Chih-Chung Chang and Chih-Jen Lin; статья с описанием реализации SVM – модели, алгоритмы(R,Python). http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf - Working Set Selection Using Second Order Information for Training Support Vector Machines, Rong-En Fan, Pai-Hsuen Chen, Chih-Jen Lin; статья с более детальным описанием реализации SVM(R,DAAL).

Литература Charu C. Aggarwal. Data Mining. The Textbook. Springer International Publishing Switzerland, 2015. http://www.ccas.ru/voron/download/SVM.pdf - К.В. Воронцов. Лекции по методу опорных векторов, 2007