§ 2. Общая рекуррентная процедура

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

Функция — столь широкий математический объект, что всякая попытка построить методы аппроксимации для произвольных функций, без ограничений, лишена смысла. другой стороны, всякое ограничение на классы рассматриваемых функций предопределяет одновременно и допустимый класс множеств, которые понимаются нами как образы. Поэтому, вводя ограничения на класс аппроксимируемых функций, надо иметь в виду два обстоятельства: с одной стороны, эти ограничения должны быть достаточно жесткими, чтобы задачу аппроксимации можно было решить; с другой стороны, ограничения не должны быть чересчур стеснительными, чтобы сохранить достаточную универсальность и естественность понятия «образ».

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

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

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

Множество рассматриваемых объектов («точек») образует пространство Мы не будем пока вводить расстояние в Всюду далее, оперируя с функциями, заданными на X, мы будем иметь в виду только функции, принимающие действительные числовые значения.

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

Если ряд (1) бесконечен, то он должен сходиться, и при том коэффициенты с должны достаточно быстро убывать с ростом

Условия, которые накладываются на убывание будут далее уточнены.

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

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

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

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

приближения функции Именно, выстраиваемая этими алгоритмами последовательность функций при стремится к функции, представимой рядом (1) и в то же время в некотором смысле наиболее близкой к

Имея это в виду, условимся в дальнейшем различать задачи о восстановлении функции и о приближении функции Далее, в § 4 этой главы, эти понятия будут уточнены.

Приступим теперь к описанию общей процедуры метода потенциальных функций.

В качестве потенциальной функции рассмотрим функцию вида

где коэффициенты удовлетворяют условиям:

Если ввести в рассмотрение функции

то выражение (2) можно записать так:

Далее везде будет предполагаться, что

где М — не зависящая от х константа.

Из условия (7) следует, что функция ограничена той же константой М, так как

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

где некоторые числовые последовательности.

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

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

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

могут зависеть только от знака а не от величины

Процедуре может быть придана иная форма, которая иногда более удобна.

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

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

Используя обозначение (5) и обозначая, кроме того,

можно выражение для записать в виде

а рекуррентную процедуру в виде

где предполагается, что зависящие, как уже говорилось, от выражены через с помощью формулы (9).

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

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

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

Рассмотрим далее эти два вопроса порознь.

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

Что касается последовательности то она принимается равной

так что процедуры приобретают вид

и

В этих выражениях некоторая функция Двух переменных, а неотрицательная числовая

последовательность, зависящая только от номера удовлетворяющая условию

и, кроме того, какому-либо одному из следующих трех условий:

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

Функция как функция двух переменных в выражении (10) в рассматриваемых алгоритмах является невозрастающей функцией переменной причем

так что

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

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

где — некоторые константы, не зависящие от х.

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

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

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

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

в непрерывном случае и

в дискретном случае, обозначается в обоих случаях одинаково, через

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

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

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

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

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