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

Алгоритмы 12-5 и 12-6 восстановления по выборке

значений функции в заданных точках

в классе линейных функций основаны на двух различных идеях задания структуры.

В алгоритме 12-5 на множестве задается та же самая структура, что и в алгоритме 12-4:

элемент содержит функции, разложимые по первым членам ряда (12.23). Однако, в отличие от алгоритма 12-4, здесь матрица Ф составлена по всем элементам обучающей и рабочей выборок. (Поэтому задание структуры здесь является априорным.)

Проблема состоит в том, чтобы выбрать элемент структуры а в нем функцию минимизирующие оценку

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

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

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

Пусть исключено точек выборки из обучающей и из рабочей, Тогда:

1) Строится упорядоченная система собственных векторов матрицы (элементы матрицы построены по выборке, из которой исключено элементов). По построенной упорядоченной системе функций задается структура на классе линейных функций.

2) По этой структуре отыскивается такой элемент а в нем такая функция, что достигается минимум выражения

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

3) Перебором по числу исключенных точек отыскивается решение, которое минимизирует функционал (12.27).

Алгоритм 12-6 основан на идее упорядочения классов эквивалентности линейных функций. Согласно теории все множество линейных функций делится на конечное число классов эквивалентности, одинаково упорядочивающих

полную выборку гл. X). Каждый класс эквивалентности характеризуется числом Зададим на множестве линейных функций структуру

где к элементу относятся все те классы эквивалентности, для которых

Для множества этой структуры емкость равна

Таким образом, возникает необходимость найти такой элемент структуры и такую в нем функцию, для которых оценка суммарного риска (12.27) минимальна. Решение этой задачи в полном объеме — проблема чрезвычайно трудная. Поэтому здесь мы рассмотрим лишь частное решение.

Пусть

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

Предположим, что известна функция

принадлежащая элементу с минимальным номером для которой выполняется условие если для элементов обучающей последовательности окажется то выполняется неравенство (Ниже будет приведен алгоритм построения такой функции.)

Функция минимизирует первый сомножитель оценки (12.27) при выполнении условия а функция второй сомножитель.

Рассмотрим теперь параметрическое (по семейство линейных функций

при функция (12.30) совпадаете (12.28), а при функция (12.30) совпадает с (12.29).

Найдем среди семейства (12.30) функцию (значение параметров у и которая доставляет минимум оценке (12.27). Поиск такой тройки может быть проведен по следующему алгоритму:

для всякого фиксированного у значение параметров определяется из условия минимизации по эмпирического риска.

Для того чтобы оценить качество полученного решения, необходимо определить величину

Перенумеруем векторы х полной выборки в порядке возрастания величин

Значение

вычислим с помощью алгоритма 11-2 (модификация 2).

Вектор определяющий (12.31), выражается через минимальный по модулю вектор удовлетворяющий неравенству

А именно

В качестве диаметра минимальной сферы, содержащей полную выборку, примем диаметр выборки и найдем величину По найденным величинам вычислим оценку (12.27).

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

Итак, для реализации алгоритма 12-6 осталось определить способ построения линейной функции, принадлежащей элементу структуры с наименьшим номером и удовлетворяющей условию Построение такой функции будем проводить, строя оптимальную разделяющую гиперплоскость (см. § 6 гл. XI).

Пусть на полной выборке, состоящей из I элементов обучающей и элементов рабочей выборки, задан фиксированный порядок следования

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

Для построения вектора используем алгоритм 11-1 (модификация 2). С помощью этого алгоритма удается построить вектор который при условии выполнения (12.32) минимизирует функционал т. е. определяет направление, которое максимизирует

Нам осталось определить такой порядок следования векторов, при котором для элементов обучающей выборки будет выполнено условие: предшествует если и при этом модуль вектора удовлетворяющего условию (12.32), достигает минимума. Вектор и определяет

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

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

1. Сначала упорядочим элементы обучающей последовательности в соответствии с величинами у и найдем минимальный по модулю вектор удовлетворяющий неравенствам (12.32).

2. Затем найдем такой элемент х рабочей выборки и так его расположим в ряду

чтобы минимизировать модуль вектора при условии выполнения неравенств

Перенумеруем последовательность (12.33) от 1 до

3. Найдем еще один элемент рабочей выборки, который при соответствующем расположении в ряду приводит к минимизации нормы вектора для которого выполнены условия (12.32) и т. д.

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

Итак, последовательность действий алгоритма 12-6 следующая:

1. Отыскивается функция

2. Отыскивается функция

минимизирующая эмпирический риск.

3. Определяется трехпараметрическое семейство функций

в котором находится оптимальное решение по следующему правилу: для каждого фиксированного у определяются величины и 1%.

С помощью величин определяется оценка суммарного риска (12.27). Перебором по у находится такая функция, для которой оценка риска минимальна. С помощью найденной функции определяются величины у для точек рабочей выборки.

Алгоритм может быть усилен за счет селекции выборки.