5.4. СЛУЧАЙ ДВУХ ЛИНЕЙНО РАЗДЕЛИМЫХ КЛАССОВ

5.4.1. ГЕОМЕТРИЯ И ПРИНЯТАЯ ТЕРМИНОЛОГИЯ

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

Выборка классифицируется правильно, если помечен или если помечен Можно заметить, что во втором случае будет классифицироваться правильно, если

Рис. 5.6. Линейно разделяемые выборки и область решения в весовом пространстве. а — случай с нормированием, б — случай без нормирования.

Рис. 5.7. Влияние допуска на область решения. а — случай б — случай

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

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

Таким образом, вектор решения должен лежать в пересечении полупространств, и любой вектор, находящийся в данной области, будет являться вектором решения. Соответствующая область называется областью решений. На рис. 5.6 изображена область решений при нормировании и без нормирования на примере двумерного случая.

Из сказанного следует, что если существует вектор решения, то он не единствен. Дополнительные ограничения на вектор решения можно получить разными способами. Одна из возможностей заключается в поиске единичного вектора, который бы максимизировал минимальное расстояние от выборок до разделяющей плоскости. Другим способом является нахождение минимального весового вектора, удовлетворяющего условию для всех i, где b — положительная константа, называемая допуском. Иногда бывает удобным, чтобы выполнялось лишь условие . Как показано на рис. 5.7, область решений, получившаяся в результате пересечения полупространств, для которых находится внутри прежней области и отделена от старых границ расстоянием . Попытки определения вектора решения, расположенного ближе к «середине» области решения, основывались на интуитивном предположении, что полученное решение с большей вероятностью будет давать правильную классификацию новых выборок. Однако в случаях, подлежащих рассмотрению, для нас удовлетворительным будет любое решение, принадлежащее области решения. Основное внимание должно быть сосредоточено на том, чтобы любая используемая итеративная процедура не вызывала приближения к предельной точке, лежащей на границе. Данная задача всегда может быть решена путем введения допуска, т. е. выполнением требования для всех

5.4.2. ПРОЦЕДУРЫ, ОСНОВАННЫЕ НА МЕТОДЕ ГРАДИЕНТНОГО СПУСКА

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

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

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

где D является матрицей частных производных второго порядка вычисленных при условии . Тогда, используя взятое из соотношений (8) и (9), можно получить следующее выражение:

из чего следует, что функцию можно минимизировать, выбрав

Другую процедуру спуска можно получить, если, не используя (8), выбирать минимизирующее это разложение второго порядка. Это приводит к алгоритму Ньютона, имеющему вид:

Вообще говоря, один шаг алгоритма Ньютона обычно более эффективен, нежели шаг алгоритма простого градиентного спуска даже при оптимальном значении Однако если матрица D вырожденна, то алгоритм Ньютона неприменим. Более того, даже при условии, что матрица D невырожденна, потери времени, связанные с ее обращением, могут легко свести на нет указанные преимущества. Фактически зачастую небходимость сделать несколько лишних коррекций, если в качестве взято заниженное значение р, приводит к меньшим затратам времени, чем вычисление оптимального на каждом шаге. В дальнейшем еще придется вернуться ко всем этим вопросам.