§ 9. Методы вычисления оптимальной разделяющей гиперплоскостиВычислять оптимальную разделяющую гиперплоскость на ЦВМ не многим сложнее, чем находить обобщенный портрет. Для этого достаточно в градиентных методах максимизации функции заменить условный градиент функции в положительном квадранте на условный градиент функции при ограничениях , , и в качестве начальной точки выбрать точку, удовлетворяющую (14.27). В соответствии с теоремой П. 4, доказанной в приложении, условный градиент функции на многообразии, задаваемом условиями (14.27), однозначно определяется формулой (14.31) при условии . Теперь остается подобрать величину так, чтобы это условие выполнялось. Будем рассматривать , в (14.31) как функции и обозначим . Очевидно, что для нахождения условного градиента достаточно найти корень уравнения . Из определения следует, что функция – монотонно возрастающая непрерывная кусочно-линейная функция. Кроме того, при она неограниченно убывает. Поэтому корень заведомо есть. Функция может иметь изломы (разрывы первой произвольной) только в точках , . Поэтому корень можно определить так: найти линейный кусок, на котором лежит корень, а затем найти корень линейной функции, совпадающий с на этом куске. Таким образом, приходим к следующему алгоритму. 1. Вычисляется значение функции в точках . 2. Если при всех функция , то корень лежит на луче и равен , где берется по всем векторам , для которых ; берется по всем векторам ; – число векторов , для которых ; – число векторов . 3. Если при некоторых функция меньше нуля, то следует найти максимальное , при котором . Обозначим его через . Тогда корень уравнения лежит на участке, прилегающем справа к точке , и равен , где берется по тем векторам , для которых или ; берется по тем векторам , для которых , или ; и – соответственно числа слагаемых в сумме и . 4. Значение вычисляется путем подстановки в (14.31) корня уравнения . Подробнее структура алгоритма построения оптимальной разделяющей гиперплоскости будет рассмотрена в главе XV.
|