LPBoost - Википедия - LPBoost

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

{ displaystyle f: { mathcal {X}} to {- 1,1 },}

который классифицирует образцы из космоса ${ displaystyle { mathcal {X}}}$ в один из двух классов, обозначенных 1 и -1 соответственно. LPBoost - это алгоритм учиться такая классификационная функция задана набором обучающих примеров с известными метками классов. LPBoost - это машинное обучение техника и особенно подходит для приложений совместной классификации и выбора признаков в структурированных областях.

Обзор LPBoost

Как и во всех повышающих классификаторах, окончательная классификационная функция имеет вид

{ displaystyle f ({ boldsymbol {x}}) = sum _ {j = 1} ^ {J} alpha _ {j} h_ {j} ({ boldsymbol {x}}),}

куда ${ displaystyle alpha _ {j}}$ неотрицательные веса для слабый классификаторы ${ displaystyle h_ {j}: { mathcal {X}} to {- 1,1 }}$ . Каждый отдельный слабый классификатор ${ displaystyle h_ {j}}$ может быть немного лучше, чем случайный, но полученная линейная комбинация многих слабых классификаторов может работать очень хорошо.

LPBoost конструкции ${ displaystyle f}$ начиная с пустого набора слабых классификаторов. Итеративно выбирается один слабый классификатор для добавления к набору рассматриваемых слабых классификаторов, добавляется и все веса ${ displaystyle { boldsymbol { alpha}}}$ для текущего набора слабых классификаторов настроены. Это повторяется до тех пор, пока не останется слабых классификаторов для добавления.

Свойство, что все веса классификатора корректируются на каждой итерации, известно как полностью корректирующий свойство. Ранние методы повышения, такие как AdaBoost не обладают этим свойством и сходятся медленнее.

Линейная программа

В общем, пусть ${ Displaystyle { mathcal {H}} = {ч ( cdot; omega) | omega in Omega }}$ - возможно бесконечное множество слабых классификаторов, также называемых гипотезы. Один из способов записать проблему, которую решает LPBoost, - это линейная программа с бесконечным числом переменных.

Основная линейная программа LPBoost, оптимизирующая неотрицательный весовой вектор. ${ displaystyle { boldsymbol { alpha}}}$ неотрицательный вектор ${ displaystyle { boldsymbol { xi}}}$ резервных переменных и поле ${ displaystyle rho}$ следующее.

{ displaystyle { begin {array} {cl} { underset {{ boldsymbol { alpha}}, { boldsymbol { xi}}, rho} { min}} & - rho + D sum _ {n = 1} ^ { ell} xi _ {n} { textrm {sb.t.}} & sum _ { omega in Omega} y_ {n} alpha _ { omega} h ({ boldsymbol {x}} _ {n}; omega) + xi _ {n} geq rho, qquad n = 1, dots, ell, & sum _ { omega in Omega} alpha _ { omega} = 1, & xi _ {n} geq 0, qquad n = 1, dots, ell, & alpha _ { omega} geq 0, qquad omega in Omega, & rho in { mathbb {R}}. end {array}}}

Обратите внимание на влияние переменных резервирования ${ Displaystyle { boldsymbol { xi}} geq 0}$ : их единичная норма штрафуется в целевой функции на постоянный коэффициент ${ displaystyle D}$ , который - если он достаточно мал - всегда приводит к практически выполнимой линейной программе.

Здесь мы приняли обозначение пространства параметров ${ displaystyle Omega}$ , так что на выбор ${ displaystyle omega in Omega}$ слабый классификатор ${ Displaystyle ч ( cdot; omega): { mathcal {X}} to {- 1,1 }}$ однозначно определено.

Когда вышеупомянутая линейная программа была впервые написана в ранних публикациях о методах повышения, она не рассматривалась как неразрешимая из-за большого количества переменных. ${ displaystyle { boldsymbol { alpha}}}$ . Лишь позже было обнаружено, что такие линейные программы действительно могут быть эффективно решены с использованием классической техники генерация столбца.

Генерация столбцов для LPBoost

В линейная программа а столбец соответствует первичной переменной. Генерация столбца это метод решения больших линейных программ. Обычно он работает в ограниченной задаче, имея дело только с подмножеством переменных. Итеративная генерация простых переменных по требованию позволяет в конечном итоге решить исходную неограниченную проблему со всеми переменными. Путем грамотного выбора столбцов для генерации можно решить проблему таким образом, чтобы при сохранении оптимальности полученного решения для исходной полной проблемы, нужно было создать только небольшую часть столбцов.

LPBoost двойная проблема

Столбцы в первичной линейной программе соответствуют строкам в двойная линейная программа. Эквивалентная двойная линейная программа LPBoost - это следующая линейная программа.

{ displaystyle { begin {array} {cl} { underset {{ boldsymbol { lambda}}, gamma} { max}} & gamma { textrm {sb.t.}} & sum _ {n = 1} ^ { ell} y_ {n} h ({ boldsymbol {x}} _ {n}; omega) lambda _ {n} + gamma leq 0, qquad omega in Omega, & 0 leq lambda _ {n} leq D, qquad n = 1, dots, ell, & sum _ {n = 1} ^ { ell} lambda _ {n} = 1, & gamma in mathbb {R}. end {array}}}

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

Критерий сходимости

Рассмотрим подмножество удовлетворенных ограничений в двойственной задаче. Для любого конечного подмножества мы можем решить линейную программу и, таким образом, удовлетворить все ограничения. Если бы мы могли доказать, что из всех ограничений, которые мы не добавляли к двойной задаче, ни одно ограничение не нарушается, мы бы доказали, что решение нашей ограниченной задачи эквивалентно решению исходной задачи. Более формально, пусть ${ displaystyle gamma ^ {*}}$ - оптимальное значение целевой функции для любого ограниченного экземпляра. Затем мы можем сформулировать задачу поиска «наиболее нарушенного ограничения» в исходном проблемном пространстве, а именно найти ${ displaystyle omega ^ {*} in Omega}$ в качестве

{ displaystyle omega ^ {*} = { underset { omega in Omega} { textrm {argmax}}} sum _ {n = 1} ^ { ell} y_ {n} h ({ boldsymbol {x}} _ {n}; omega) lambda _ {n}.}

То есть мы ищем пространство ${ displaystyle { mathcal {H}}}$ для одного пень решения ${ Displaystyle ч ( cdot; omega ^ {*})}$ максимизируя левую часть двойного ограничения. Если ограничение не может быть нарушено никаким выбором пня решения, ни одно из соответствующих ограничений не может быть активным в исходной задаче, и ограниченная задача эквивалентна.

Константа пенализации ${ displaystyle D}$

Положительное значение константы штрафов ${ displaystyle D}$ должен быть найден с помощью выбор модели техники. Однако, если мы выберем ${ Displaystyle D = { гидроразрыва {1} { ell nu}}}$ , куда ${ displaystyle ell}$ - количество обучающих выборок и ${ Displaystyle 0 < ню <1}$ , то новый параметр ${ displaystyle nu}$ обладает следующими свойствами.

${ displaystyle nu}$ - верхняя граница доли ошибок обучения; то есть, если ${ displaystyle k}$ обозначает количество неверно классифицированных обучающих выборок, тогда ${ displaystyle { frac {k} { ell}} leq nu}$ .
${ displaystyle nu}$ - это нижняя граница доли обучающих выборок вне или на границе.

Алгоритм

Вход:
- Обучающий набор ${ displaystyle X = {{ boldsymbol {x}} _ {1}, dots, { boldsymbol {x}} _ { ell} }}$ , ${ displaystyle { boldsymbol {x}} _ {i} in { mathcal {X}}}$
- Этикетки для обучения ${ displaystyle Y = {y_ {1}, dots, y _ { ell} }}$ , ${ Displaystyle у_ {я} в {- 1,1 }}$
- Порог сходимости ${ displaystyle theta geq 0}$
Выход:
- Функция классификации ${ displaystyle f: { mathcal {X}} to {- 1,1 }}$

Инициализация
1. Гири, униформа ${ displaystyle lambda _ {n} leftarrow { frac {1} { ell}}, quad n = 1, dots, ell}$
2. Край ${ displaystyle gamma leftarrow 0}$
3. Количество гипотез ${ displaystyle J leftarrow 1}$
Повторять
1. ${ displaystyle { hat {h}} leftarrow { underset { omega in Omega} { textrm {argmax}}} sum _ {n = 1} ^ { ell} y_ {n} h ( { boldsymbol {x}} _ {n}; omega) lambda _ {n}}$
2. если ${ displaystyle sum _ {n = 1} ^ { ell} y_ {n} { hat {h}} ({ boldsymbol {x}} _ {n}) lambda _ {n} + gamma leq theta}$ $sum _ {{n = 1}} ^ {{ ell}} y_ {n} { hat h} ({ boldsymbol {x}} _ {n}) lambda _ {n} + gamma leq theta$ тогда
  1. перемена
3. ${ displaystyle h_ {J} leftarrow { hat {h}}}$
4. ${ Displaystyle J leftarrow J + 1}$
5. ${ displaystyle ({ boldsymbol { lambda}}, gamma) leftarrow}$ решение двойного LPBoost
6. ${ displaystyle { boldsymbol { alpha}} leftarrow}$ Лагранжевы множители решения двойственной задачи LPBoost
${ displaystyle f ({ boldsymbol {x}}): = { textrm {sign}} left ( sum _ {j = 1} ^ {J} alpha _ {j} h_ {j} ({ полужирный символ {x}}) right)}$

Обратите внимание, что если порог сходимости установлен на ${ displaystyle theta = 0}$ полученное решение является глобальным оптимальным решением указанной выше линейной программы. На практике, ${ displaystyle theta}$ устанавливается на небольшое положительное значение, чтобы быстро получить хорошее решение.

Реализованная маржа

Фактический запас, разделяющий обучающие выборки, называется реализованная маржа и определяется как

{ displaystyle rho ({ boldsymbol { alpha}}): = min _ {n = 1, dots, ell} y_ {n} sum _ { alpha _ { omega} in Omega } alpha _ { omega} h ({ boldsymbol {x}} _ {n}; omega).}

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

Гарантия сходимости

Доказано, что приведенный выше алгоритм сходится, в отличие от других формулировок повышения, таких как AdaBoost и TotalBoost, нет известных границ сходимости для LPBoost. Однако на практике известно, что LPBoost быстро сходится, часто быстрее, чем другие составы.

Базовые ученики

LPBoost - это ансамблевое обучение метод и, следовательно, не диктует выбор базовых учащихся, пространство гипотез ${ displaystyle { mathcal {H}}}$ . Demiriz et al. показал, что при умеренных предположениях можно использовать любого базового учащегося. Если базовые учащиеся особенно просты, их часто называют пни решения.

Количество базовых учащихся, обычно используемых с Boosting в литературе, велико. Например, если ${ Displaystyle { mathcal {X}} substeq { mathbb {R}} ^ {п}}$ , базовым учеником может быть линейный мягкий запас Машина опорных векторов. Или еще проще - простой культей формы

{ displaystyle h ({ boldsymbol {x}}; omega in {1, -1 }, p in {1, dots, n }, t in { mathbb {R}}) ): = left {{ begin {array} {cl} omega & { textrm {if ~}} { boldsymbol {x}} _ {p} leq t - omega & { textrm {иначе}} end {array}} right ..}

Вышеупомянутые пни решения выглядят только в одном измерении. ${ displaystyle p}$ входного пространства и просто устанавливает пороговое значение для соответствующего столбца выборки, используя постоянный порог ${ displaystyle t}$ . Затем он может принять решение в любом направлении, в зависимости от ${ displaystyle omega}$ для положительного или отрицательного класса.

При заданных весах для обучающих выборок построение оптимального пня решения в приведенной выше форме просто включает поиск по всем столбцам выборки и определение ${ displaystyle p}$ , ${ displaystyle t}$ и ${ displaystyle omega}$ для оптимизации функции усиления.

LPBoost - Википедия - LPBoost

Содержание

Обзор LPBoost