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

Идея построения кусочно-линейных функций путем использования таксонной структуры множества X обучающей последовательности являются эвристической. Такая

идея может быть проведена строго лишь для задачи восстановления значений функции в заданных точках. Реализует ее алгоритм 12-8.

На множестве х, состоящем из I элементов обучающей последовательности и из 4 элементов рабочей выборки, задается таксонная структура. Элемент таксонной структуры определяет разбиение множества векторов состоящего из векторов обучающей и рабочей выборок на подмножеств

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

Тогда, используя алгоритмы § 7, для каждого множества в классе линейных функций восстановим значения функции в точках рабочей выборки (в тех точках, которые принадлежат по эмпирическим данным (также из

При этом воспользуемся следующей оценкой величины суммарного риска:

где наименьшее решение неравенства

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

Величина суммарного риска по всем подмножествам равна

Минимизацией по элементам таксонной структуры найдем наилучшее решение.

Наконец, рассмотрим локальный алгоритм 12-9 восстановления значений функции в заданных точках. Этрт

алгоритм с точностью до реализации метода минимизации суммарного риска в классе линейных функций повторяет локальный алгоритм распознавания образов 11-8.

1. Так же как и в алгоритме 11-8, для каждого элемента полной выборки

рассматривается система окрестностей (окрестность вектора состоит из тех векторов, для которых

Иначе говоря, рассматривается систем вложенных множеств

2. Пусть исследуются окрестности точки и пусть окрестность точки

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

где наименьшее решение неравенства

В (12.36) - число элементов обучающей последовательности, число элементов рабочей выборки с векторами х из

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

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

Составим табл. 1.

Таблица 1

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

4. Обозначим через искомые значения функции в точках Поставим в соответствие каждой строке таблицы неравенство и рассмотрим систему

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

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

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

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

рассмотрим цилиндры с прямоугольными основаниями

Очевидно, что допустимое множество содержит допустимое множество Минимаксная же точка множества отыскивается по следующему простому правилу: для каждого вектора рабочей выборки найдем с помощью и последнего столбцов таблицы два числа

Минимаксный вектор множества есть вектор с координатами