§ 11. Локальные алгоритмы восстановления значений характеристической функции

Наконец, рассмотрим третью идею построения алгоритмов восстановления значений функции.

Определим для каждого вектора х полной выборки систему окрестностей:

Таким образом, задается систем окрестностей, своя для каждого вектора полной выборки:

Пусть теперь произошло разделение множества X на обучающую и рабочую выборки.

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

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

размерность пространства

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

С вероятностью для элементов из справедлива оценка

Найдем теперь такую окрестность точки для которой достигается минимум (по ) величины Пусть

минимум достигается на окрестности — полученная классификация векторов рабочей! выборки из этой окрестности. Очевидно, что с вероятностью эта классификация содержит меньше ошибок.

Аналогично могут быть найдены решения для окрестностей всех векторов генеральной совокупности. В результате получим табл. 1.

Таблица 1

В первом столбце таблицы указаны векторы, задающие систему окрестностей, затем наилучшая по данной системе окрестностей классификация векторов и, наконец, гарантированная оценка числа ошибок классификации.

Заметим, что одни и те же векторы рабочей выборки принадлежат окрестностям различных векторов, а классификация некоторых векторов рабочей выборки, данная в разных строках второго столбца таблицы, может не совпадать.

Обозначим через истинную классификацию векторов рабочей выборки .

Тогда содержание таблицы может быть переписано в виде

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

Каждое из неравенств (10.56) выполняется с вероятностью Следовательно, система совместна (все не?

равенства выполняются одновременно) с вероятностью, большей

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

Найдем среди векторов минимаксный — т. е. наименее удаленный от самого далекого вектора из допустимого множества :

Вектор мы и примем за окончательное решение задачи классификации векторов рабочей выборки.

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

На практике используются разные идеи задания окрестностей. В частности, окрестность вектора может быть определена по метрической близости (множество содержит векторы полной выборки, для которых , где с — константа. Набор констант определяет систему окрестностей).