§ 5. Сравнение второго и третьего алгоритмов с другими алгоритмами метода потенциальных функций

Как было отмечено в § 3, задача аппроксимации степени достоверности может быть понята как задача аппроксимации функции и поэтому для ее решения предлагалось использовать один из алгоритмов главы VI (первый алгоритм из § 3 настоящей главы). Вместе с тем, как отмечалось в § 1, задача распознавания образов в детерминистской постановке (гл. V) является частным случаем рассматриваемой в настоящей главе вероятностной задачи, так что алгоритмы настоящей главы могут быть использованы и для решения детерминистской задачи. Поэтому представляет интерес, с одной стороны, сравнить второй и третий алгоритмы настоящей главы с первым алгоритмом при решении задачи аппроксимации степени достоверности и, с другой стороны, сравнить эти алгоритмы с алгоритмом гл. V при решении детерминистской задачи распознавания образов.

1. Сравнение первого алгоритма со вторым и третьим.

Рассмотрим последовательность величин

где приближение функции на шаге процедуры. Для первого алгоритма определяется рекуррентной процедурой (16) гл. VI), а для второго и третьего алгоритмов определяется рекуррентной процедурой главы II с определяемыми из Если выполнено условие (34), то все три алгоритма решают задачу восстановления функции в смысле соотношения

Если условие (34) не выполнено, но выполнено условие (36), или даже более общее условие (39), то, как показано в § 4, второй и третий алгоритмы по-прежнему гарантируют восстановление функции в смысле (40), в то время как при использовании первого алгоритма это не гарантируется, Тем самым при решении задачи

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

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

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

где некоторая постоянная (зависящая от Тогда, если справедливо неравенство

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

Для доказательства утверждения (41) отметим, что для функционала (31) при имеет место неравенство

Это неравенство немедленно следует из легко устанавливаемого неравенства

справедливого при любом и 1, если учесть, что

Неравенства (33) и (42) объединяются в неравенство

В силу правой части неравенства (43) имеем

Но для последовательности выстраиваемой вторым или третьим алгоритмами, можно записать (в силу левой части неравенства соотношение

из которого с учетом следует, что

Неравенства (44) и (45) доказывают утверждение (41).

2. Сравнение второго и третьего алгоритмов с алгоритмом главы V.

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

где

так что , если .

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

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

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

Для того чтобы установить, что при условии (48) имеет место восстановление функции вида (46), покажем, что она принадлежит классу определяемому условием (39). С этой целью рассмотрим последовательность функций

В силу условия Поэтому остается лишь показать, что

Обращаясь к формулам (31), (32), убеждаемся, что

и поэтому

Очевидно, что разность

отлична от нуля лишь для тех х, где

Но поскольку, кроме того,

то

Отсюда следует, что

и

так как

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

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