§ 12. Алгоритмы метода обобщенного портрета

Алгоритмы метода обобщенного портрета реализуют идею минимизации эмпирического риска в классе линейных и кусочно-линейных функций.

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

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

В качестве примера приведем здесь идею двух таких алгоритмов (подробно система алгоритмов метода обобщенного портрета будет рассмотрена в третьей части книги).

Если обучающая последовательность не может быть безошибочно разделена на два класса, среди векторов обучающей последовательности определяется тот, который наиболее «препятствует» разделению. Он исключается из обучающей последовательности, а оставшиеся векторы вновь разделяются гиперплоскостью. Если разделение все еще невозможно, то исключается еще один вектор, и так до тех пор, пока множество оставшихся векторов не будет разделено. При этом считается, что число исключенных векторов минимально (или близко к нему). Правило удалений определяется эвристическим понятием «вектора, наиболее препятствующего разделению». Удаленные из обучающей последовательности векторы как раз и составляют множество неправильно опознанных векторов. Отношение числа этих векторов к числу всех векторов обучающей последовательности определяет величину эмпирического риска для выбранного решающего правила (обобщенного портрета). Величина же истинного риска для найденного правила с вероятностью  отличается от эмпирического риска не более чем на , где  определяется согласно (5.11).

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

С увеличением числа  кусков гиперплоскостей уменьшается количество неправильно опознанных векторов, т. е. уменьшается величина эмпирического риска. Однако величина гарантированного уклонения истинного риска от эмпирического растет с ростом числа кусков гиперплоскостей по линейному закону

.

Отсюда следует, что желательно разделить обучающую последовательность с помощью минимального числа кусков гиперплоскостей.

Различные алгоритмы реализуют разные идеи построения такого кусочно-линейного правила, которое минимизирует сумму величины эмпирического риска и величины гарантированного уклонения.