§ 4. Функционалы, экстремизируемые процедурами метода потенциальных функций

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

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

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

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

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

при сходимости в среднем квадрате — величина

Сам же факт сходимости последовательности по определению означает, что при

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

В связи с тем, что функция случайная функция (она зависит от статистики показа; см. § 2), величина также случайная величина, и стремление к нулю понимается в вероятностном смысле (например, в смысле сходимости почти наверное; см. гл. IV).

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

Рассмотрим введенные в § 2 системы функций связанные соотношением (5). Будем говорить, что

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

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

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

где

и если

Покажем, что если функция принадлежит классу то она заведомо принадлежит и Для этого достаточно показать, что математическое ожидание квадрата функции, удовлетворяющей условиям (26), (28), конечно. Используя неравенство Коши — Буняковского, получаем из (26)

В силу равенства (6) имеем поэтому

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

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

Поэтому, если и, следовательно, то и а значит, Предположение (см.

§ 2) о том, что для исходной функции выполнено условие

означает, что Отсюда следует в силу индукции, что при любом

Будем говорить, что последовательность функций приближает функцию если при

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

Очевидно, что если то последовательность приближающая функцию восстанавливает ее, так как в этом случае правая часть в (29) равна нулю:

Если же функция не принадлежит классу а приближение (29) имеет место, то последовательность в пределе «выделяет» из всех функций класса функцию, наиболе близкую к в смысле минимизации функционала

В главах V—VIII при исследовании конкретных алгоритмов доказываются теоремы, устанавливающие, в

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

Предположение т. е.

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

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

конечномерным случаем этой процедуры:

Полное рассмотрение процедуры (11), (12) проведено в главе IV.

Введем функцию

где некоторая функция х. В силу того, что (см. § 2)

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

получим функцию

Обратим внимание на то, что с помощью функции процедура (31) может быть записана в виде

Тождественность формул (31) и (35) легко проверяется прямым дифференцированием функции по если учесть определения (33) и (34).

Если бы точка в (35) оставалась бы одной и той же при всех а помеха отсутствовала бы

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

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

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

существует. Именно это выражение при определенной формулой (33), и служит основным функционалом при рассмотрении в главах V—VII конкретных алгоритмов метода потенциальных функций. Непосредственно видно, что . Вопрос о том, при каких условиях и в каком смысле функционал (37) минимизируется процедурой (11), (12), рассматривается в последующих главах.

Выше было получено выражение для функционала, минимизируемого процедурой (!), при и при определяемом выражением (10). Точно таким же образом может быть получено выражение для

минимизируемого функционала в случае, когда по-прежнему определяется соотношением (10), а

Формула (35) сохраняется и в этом случае, если только положить в ней

где функция определяется по-прежнему формулой (33). Минимизируемый функционал имеет в этом случае вид

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