LPBoost
Повышение с помощью линейного программирования ( LPBoost ) — это контролируемый классификатор из с повышением семейства классификаторов . LPBoost максимизирует разницу между обучающими выборками разных классов и, следовательно, также относится к классу контролируемых алгоритмов классификации, максимизирующих разницу. Рассмотрим функцию классификации
который классифицирует образцы из пространства в один из двух классов, обозначенных 1 и -1 соответственно. LPBoost — это алгоритм для изучения такой функции классификации на основе набора обучающих примеров с известными метками классов. LPBoost — это метод машинного обучения , который особенно подходит для приложений совместной классификации и выбора признаков в структурированных областях.
Обзор LPBoost
[ редактировать ]Как и во всех повышающих классификаторах, окончательная функция классификации имеет вид
где являются неотрицательными весами для слабых классификаторов . Каждый отдельный слабый классификатор может быть немного лучше, чем случайное, но полученная линейная комбинация многих слабых классификаторов может работать очень хорошо.
Конструкции LPBoost начав с пустого набора слабых классификаторов. Итеративно выбирается один слабый классификатор для добавления к набору рассматриваемых слабых классификаторов, добавляется и все веса для текущего набора слабых классификаторов скорректированы. Это повторяется до тех пор, пока не останется слабых классификаторов, которые можно добавить.
Свойство, заключающееся в том, что все веса классификатора корректируются на каждой итерации, известно как полностью корректирующее свойство. Ранние методы повышения, такие как AdaBoost, не обладают этим свойством и сходятся медленнее.
Линейная программа
[ редактировать ]В более общем смысле, пусть быть возможно бесконечным набором слабых классификаторов, также называемых гипотезами . Один из способов записать проблему, которую решает LPBoost, — это линейная программа с бесконечным количеством переменных.
Основная линейная программа LPBoost, оптимизирующая неотрицательный весовой вектор. , неотрицательный вектор слабых переменных и запаса заключается в следующем.
Обратите внимание на влияние слабых переменных : их одна норма штрафуется в целевой функции постоянным коэффициентом , который, если он достаточно мал, всегда приводит к простой допустимой линейной программе.
Здесь мы приняли обозначение пространства параметров , такой, что для выбора слабый классификатор определяется однозначно.
Когда приведенная выше линейная программа была впервые записана в ранних публикациях о методах бустинга, ее игнорировали как трудноразрешимую из-за большого количества переменных. . Лишь позже было обнаружено, что такие линейные программы действительно могут быть эффективно решены с использованием классической техники генерации столбцов .
Генерация столбцов для LPBoost
[ редактировать ]В линейной программе столбец . соответствует основной переменной Генерация столбцов — это метод решения больших линейных программ. Обычно он работает в ограниченной задаче, имея дело только с подмножеством переменных. Путем итеративной генерации основных переменных по требованию в конечном итоге восстанавливается исходная неограниченная проблема со всеми переменными. Умно выбрав столбцы для создания проблемы, можно решить ее так, что, гарантируя, что полученное решение будет оптимальным для исходной полной задачи, нужно будет создать лишь небольшую часть столбцов.
Двойная проблема с LPBoost
[ редактировать ]Столбцы в основной линейной программе соответствуют строкам в двойной линейной программе . Эквивалентной двойной линейной программой LPBoost является следующая линейная программа.
Для линейных программ оптимальное значение основной и двойственной задач одинаково. Для вышеупомянутых основных и двойственных задач оптимальное значение равно отрицательному «мягкому запасу». Мягкая маржа — это размер границы, разделяющей положительные и отрицательные экземпляры обучения, за вычетом положительных слабых переменных, которые влекут за собой штрафы за образцы, нарушающие границы. Таким образом, мягкий запас может быть положительным, хотя не все выборки линейно разделены функцией классификации. Последняя называется «жесткой маржой» или «реализованной маржой».
Критерий сходимости
[ редактировать ]Рассмотрим подмножество удовлетворяемых ограничений в двойственной задаче. Для любого конечного подмножества мы можем решить линейную программу и, таким образом, удовлетворить все ограничения. Если бы мы могли доказать, что из всех ограничений, которые мы не добавили к двойственной задаче, ни одно ограничение не нарушается, мы бы доказали, что решение нашей ограниченной задачи эквивалентно решению исходной задачи. Более формально, пусть быть оптимальным значением целевой функции для любого ограниченного случая. Затем мы можем сформулировать задачу поиска «наиболее нарушенного ограничения» в исходном проблемном пространстве, а именно найти как
То есть мы ищем пространство за один пень решения максимизация левой части двойного ограничения. Если ограничение не может быть нарушено каким-либо выбором пня решения, ни одно из соответствующих ограничений не может быть активным в исходной задаче, и ограниченная задача эквивалентна.
Константа штрафа
[ редактировать ]Положительное значение константы штрафа должен быть найден с использованием методов выбора модели . Однако, если мы выберем , где количество обучающих выборок и , то новый параметр имеет следующие свойства.
- – верхняя граница доли ошибок обучения; то есть, если обозначает количество неправильно классифицированных обучающих выборок, затем .
- — это нижняя граница доли обучающих выборок за пределами или на границе.
Алгоритм
[ редактировать ]- Вход:
- Тренировочный набор ,
- Тренировочные этикетки ,
- Порог сходимости
- Выход:
- Функция классификации
- Инициализация
- Весы, униформа
- Край
- Количество гипотез
- Итерировать
- если затем
- перерыв
- решение двойного LPBoost
- Множители Лагранжа решения двойственной задачи LPBoost
Обратите внимание, что если порог сходимости установлен на полученное решение является глобальным оптимальным решением указанной выше линейной программы. На практике, установлено небольшое положительное значение, чтобы быстро получить хорошее решение.
Реализованная маржа
[ редактировать ]Фактическая разница, разделяющая обучающие выборки, называется реализованной границей и определяется как
Реализованная маржа может и обычно будет отрицательной на первых итерациях. Для пространства гипотез, которое позволяет выделить любую отдельную выборку, как это обычно бывает, реализованная разница в конечном итоге сойдется к некоторому положительному значению.
Гарантия конвергенции
[ редактировать ]Хотя доказана сходимость приведенного выше алгоритма, в отличие от других формул повышения, таких как AdaBoost и TotalBoost , для LPBoost не существует известных границ сходимости. Однако на практике известно, что LPBoost сходится быстро, часто быстрее, чем другие составы.
Базовые ученики
[ редактировать ]LPBoost является методом ансамблевого обучения и поэтому не диктует выбор базовых обучающихся, пространства гипотез. . Демирис и др. показали, что при мягких предположениях можно использовать любого базового обучаемого. Если базовые учащиеся особенно просты, их часто называют пнями решений .
Число базовых обучающихся, обычно используемых с Boosting в литературе, велико. Например, если Базовым обучающимся может быть линейная машина опорных векторов с мягкими границами . Или еще проще, простой обрубок вида
Вышеупомянутые пни решения выглядят только в одном измерении. входного пространства и просто устанавливает пороговое значение для соответствующего столбца выборки, используя постоянный порог . Затем он может принять решение в любом направлении, в зависимости от для положительного или отрицательного класса.
Учитывая веса обучающих выборок, построение оптимальной пени решения приведенной выше формы просто включает поиск по всем столбцам выборки и определение , и для оптимизации функции усиления.
Ссылки
[ редактировать ]- Повышение эффективности линейного программирования посредством генерации столбцов , А. Демирис, К. П. Беннетт и Дж. Шоу-Тейлор. Опубликовано в 2002 г. в журнале Kluwer Machine Learning 46, страницы 225–254.