Уменьшение размерности задачи линейной бинарной классификации(e.g. SVM)

Требуемые знания: знакомство с методами линейной бинарной классификации(e.g. SVM(см. SVM Tutorial)), линейная алгебра, линейное программирование

Рассмотрим линейную задачу бинарной классификации(если задача линейно неразделима, её можно свести к таковой с помощью симметричного интегрального L-2 ядра(см. SVM)). При решении такой задачи классифицируемые элементы(далее образцы) представляются в виде элементов векторного пространства размерности n. На практике в таких задачах n может быть чрезвычайно большим, например для задачи классификации генов оно может исчисляться десятками тысяч. Большая размерность влечёт, по-мимо высокого времени вычисления, потенциально высокую погрешность численных рассчётов. Кроме того использование большой размерности может требовать больших финансовых затрат(на проведение опытов). Постановка вопроса такова: можно ли и как уменьшить n отбрасыванием незначимых компонент образцов так, чтобы образцы разделялись «не хуже» в новом пространстве(эмпирическая ошибка не возросла или, что тоже самое, в новом пространстве образцы оставались линейно разделимы) или «не сильно хуже».
В своей статье я хочу для начала провести краткий обзор метода из этой статьи Gene_Selection_for_Cancer_Classification_using, после чего предложить свой метод.

Алгоритмы из Gene_Selection_for_Cancer_Classification_using

Основная идея метода понижения размерности в Gene_Selection_for_Cancer_Classification_using заключается в ранжировании всех компонент. Предлагается следующий алгоритм:

1. Присваиваем всем(оставшемся) компонентам некоторые весовые коэффициенты(о том как — далее)
2. Сортируем компоненты по весам
3. Выкидываем компоненту с минимальным весом из всех образцов.
4. Тренируем SVM. Если не удалось разделить образцы, то возвращаем компоненту и выкидываем следующую(по порядку весовых коэффициентов). Так пока они не закончатся. Закончились — выходим из алгоритма. Если удалось разделить образцы, то идём на шаг 1

В основном в статье расматривается способ присвоения весов полученных SVM.То есть используем в качестве весов коэффициенты в классифицирующей функции соответствующих компонент. Допустим после тренировки SVM мы получили классифицирующую функцию (w,x) + b=0, тогда wi компонент будет весом компоненты i. Также в статье рассматривается корреляционный способ задания весов, но он, как и любой другой, проигрывает SVM способу, т.к. при повторном попадании на шаг 1 весовые коэффициенты в SVM способе известны из шага 4.
Класс таких алгоритмов по-прежнему вынужден тренировать SVM на образцах большой размерности, т.е. проблемы погрешности и скорости не решаются. Всё что он даёт — это возможность после тренировки SVM сократить число компонент классифицируемых образцов. Если опытное получение значений сокращённых компонент финансово затратно, то можно сэкономить.
P.S. Кроме того выбор весов как wi довольно спорный. Я бы предложил хотя бы домножить их на выборочную дисперсию компоненты i по всем образцам или на первый центральный абсолютный выборочный момент компоненты i по всем образцам.

Мой алгоритм

Идея такова: выбрасываем компоненту и проверяем будет ли теперь(без этой компоненты) множество образцов линейно разделимо. Если да, то не возвращаем эту компоненту, если нет то возвращаем. Вопрос в том как проверить множество на линейную разделимость?
Пусть xi — образцы, yi — принадлежность образца к классу (yi=-1 — первый класс, yi=1 — второй класс) i=1..m. Тогда образцы линейно разделимы, если

— имеет нетривиальное решение, где

(условия как при тренировке SVM).
_____________________________________________________________________________________
Давайте для начала рассмотрим как можно проверить множество на строгую линейную разделимость:

— имеет решение. По лемме Фаркаша <=>

— имеет только тривиальное решение. Проверяем вектор 0 на оптимальность в задаче линейного программирования с полученными ограничениями и целевой функцией

Если 0 оказался оптимальным, значит множество строго линейно разделимо.
_____________________________________________________________________________________
Нестрогая линейная разделимость:

— имеет нетривиальное решение. По лемме Фаркаша <=>

— не имеет решений. <=>

— не имеет решений. Для проверки наличия решения полученных ограничений можно использовать любой метод нахождения начального опорного вектора в задаче линейного программирования с данными ограничениями.
_____________________________________________________________________________________
В некоторых задачах (особенно когда размерность(n) превышает число образцов(m)) мы можем захотеть отбрасывать компоненту только если разделение множества происходит с некоторым зазором. Тогда можно проверять такие условия:

— имеет решение, где c>=0 параметр зазора, а второе ограничение заменяет нормировку альфа(чтобы нельзя было решение A*x>0 просто умножить на достаточно большую константу k и удовлетворить системе A*k*x>=c). Эти условия по лемме Фаркаша(E — единичная матрица) <=>

Проверяем вектор 0 на оптимальность в задаче линейного программирования с полученными ограничениями(без последней строчки) и целевой функцией

Если 0 оказался оптимальным, значит множество можно разделить с заданным зазором.
_____________________________________________________________________________________
В некоторых задачах (особенно когда число образцов(m) превышает размерность(n)) мы можем захотеть отбрасывать компоненту даже если разделение множества происходит с некоторой ошибкой. Тогда можно проверять такие условия:

— имеет решение, где c<=0 параметр ошибки, а вторые ограничения заменяют нормировку альфа(чтобы нельзя было решение A*x>negative_number_less_than_c просто разделить на достаточно большую константу k и удовлетворить системе A*x/k>=c). Здесь всё аналогично вышеописанному случаю, только из-за дизъюнкции(квадратной скобки) придётся рассмотреть две задачи линейного программирования.

P.S. В задачах с ошибкой и с зазором правильно было бы использовать условие нормировки: норма альфа == 1. Однако оно нелинейно и поэтому не даёт возможности воспользоваться леммой Фаркаша и ЛП. Чтобы приблизить наши линейные условия к условию нормировки можно добавить такое условие: сумма всех компонент альфа по модулю меньше или равна единице. Чтобы ещё приблизить наши линейные условия к условию нормировки можно заменить единицы на как можно меньшее число.

Автор: Pavel_Osipyants

Источник