Растригин Л.А. Адаптация сложных систем

Подождите немного. Документ загружается.

Рис. 4.6.2. Алгоритмическая блок-схема пакета программ для

синтеза коллективных алгоритмов распознавания.

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

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

специального пакета оптимизируемых программ распознавания. Его

алгоритмическая структура представлена на рис. 4.6.2.

Основой пакета является библиотека алгоритмов распознавания и

оптимизации. В библиотеке должны быть объединены как

параметрические, так и непараметрические алгоритмы раслознавания.

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

измеряться как в метрической шкале (количественные признаки), так и

в шкале наименований (качественные лризнаки). Так как пока

существует мало алгоритмов распознавания для объектов со

смешанными признаками, то необходимо предусмотреть

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

качественным признакам (при большом числе таких признаков) или

только к количественным (при малом числе качественных признаков).

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

правил, соответствующих различным значениям качественных

признаков.

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

способов быстрой оценки критерия эффективности алгоритма, так как

метод скользящего контроля [13] требует значительных затрат при

большой обучающей выборке.

На пользователя следует возложить функцию выбора:

а) алгоритмов распознавания из библиотеки;

б) структуры синтезируемого решающего правила (отдель

ный алгоритм, гибрид или коллектив);

в) способа варьирования правил или оптимизации (варьиро

вание обучающей выборки, параметров алгоритмов и их сверток

или последовательное наращивание структуры коллектива).

Сервисная часть пакета должна обеспечивать надежные оценки

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

и наглядное представление результатов на экране дисплея в

интерактивной версии пакета.

§ 4.7. Адаптивная идентификация

параметров распределения

Пусть

р (х, С) (4.7.1)

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

х, где С = (c

, ..., c

) — вектор неизвестных параметров распределения.

Это означает, что плотность распределения (4.7.1) известна с

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

в процессе наблюдения за реализациями случайной величины х:

x1, x

, ..., x

, (4.7.2)

порожденными распределением (4.7.1) при С = С*:

р (х, С*), . (4.7.3)

где С* — искомый вектор неизвестных параметров. Таким образом,

задача определения плотности (4.7.1) предполагается

параметризованной.

Обычным (неадаптивным) способом решения этой задачи является

известный метод максимума правдоподобия, при котором

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

(4.7.4)

где N>k, или, логарифм этой функции

(4.7,5)

Максимум функции правдоподобия

соответствует оптимальной оценке неизвестных параметров на

базе наблюдений (4.7.2):

(4.7.6)

Эта оценка, как известно [120], обладает свойствами состоятельности

(4.7.7)

и асимптотической эффективности

(4.7.8)

где D — знак дисперсии.

Однако задача минимизации функции (4.7.5) часто представляет

собой не столько сложную, сколько громоздкую вычислительную

задачу, которая обычно сводится к решению системы

трансцендентных уравнений вида

(4.7.9)

Некоторое упрощение можно

получить, если воспользоваться моментами случайной величины х.

Для этого по распределению (4.7.1) определяются m≥k первых

начальных моментов, которые являются функцией неизвестных

параметров С:

(4.7.10)

Оценки этих же моментов можно найти по выборке (4.7.2):

(4.7.11)

Теперь, приравнивая эти выражения, получаем

систему трансцендентных уравнений:

(4.7.12)

которую при m>k можно решать, например, методом наименьших

квадратов. Однако и этот подход сводится к чрезвычайно громоздким

вычислениям (он был использован в работе [91] для случая m = k = 2).

Эти соображения заставляют обратиться к итерационным методам

оценки неизвестных параметров распределений. Рассмотрим

применение методов адаптации к решению изложенной задачи.

Исходя из свойства (4.7.7), выражение (4.7.5) при N→∞ можно

записать в виде

(4.7.13)

т. е.

(4.7.14)

Задача оценки параметров С,

обеспечивающих максимум этого выражения, теперь может быть

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

[237]:

(4.7.15)

где C

— значение вектора

определяемых параметров на N-м шаге:

= (c

(N)

, ..., c

(N)

); (4.7.16)

— матрица коэффициентов k×k:

= || γ

(N)

k×k

; (4.7.17)

вектор градиента:

(4.7.18)

(N)

— элемент выборки (4.7.2), получаемый путем ее циклического

обхода.

Для упрощения матрицу (4.7.17) удобно представить в диа-

гональном виде

(4.7.19)

Проиллюстрируем этот метод на примере определения параметров

нормального закона распределения

(4.7.20)

Здесь С = (а, σ

). Пусть сначала

определяется математическое ожидание а, а дисперсия σ

предполагается известной. Тогда k=1, с

= а и получаем

4.7.21) причем алгоритм адаптации (4.7.15)

принимает вид

(4.7.22)

где a

— начальная априорная оценка а.

При γ

— σ

/N получаем известный алгоритм оценки среднего

значения [237]:

(4.7.23)

Теперь рассмотрим адаптацию по

двум параметрам — математическому ожиданию и дисперсии. В этом

случае k = 2; с

= а; с

= σ

(4.7.24)

В результате

получаем алгоритм адаптации в виде

(4.7.25)

где начальные значения

, σ

равны априорным

значениям параметров a и σ. Эти выражения могут быть упрощены:

= a

N-1

+γ

(3)

(N)

- a

N-1

); (4.7.26)

= σ

N-1

+γ

(4)

[ (x

(N)

- a

)

- σ

N-1

где параметры γ

(i)

(i = l, ..., 4) выбираются в соответствии с

поставленной задачей.

Так, при и получаем известные опти-

мальные [102] оценки математического ожидания и дисперсии:

(4.7.27)

Покажем, как применяется адаптация такого рода для оценки

параметров объекта в процессе его оптимизации методом случайного

поиска.

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

дисперсии помехи, накладывающейся на Q. Приращение показателя

качества в процессе случайного поиска с парными пробами (3.3.5)

имеет вид

∆Q' = Q' (U + gξ) - Q' (U - gξ), (4.7.28)

где U = (u

, ..., u

) — оптимизируемые параметры; g — величина

пробного шага; ξ = (ξ

, ..., ξ

) — единичный случайный вектор,

равномерно распределенный в пространстве параметров {U}. Помеха

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

Q' (U) = Q (U) + ε (σ). (4.7.29)

Здесь ε (σ) — случайная помеха, имеющая нормальное распределение

с дисперсией σ

и нулевым средним. Подставляя (4.7.29) в (4.7.28),

получим

(4.7.30)

Здесь оба слагаемых являются случайными

величинами. Величина ∆Q распределена при случайном поиске в

линейном поле по закону [161]:

(4.7.31)

где q — размерность оптимизируемого объекта; ;

Г — гамма-функция; k — модуль градиента оптимизируемой функции:

(4.7.32)

Помеха распределена нормально с нулевым

математи-

ческим ожиданием и дисперсией 2σ

(4.7.33)

Определим плотность распределения случайной

величины ∆Q'. В соответствии с выражением (4.7.30) это будет

композиция двух распределений (4.7.31) и (4.7.33). Стандартным

образом [47] получаем

(4.7.34)

В простейшем случае для q=3 имеем

(4.7.35)

где Φ — функция Лапласа [47].

Теперь определим составляющие градиента логарифма функции

(4.7.35):

(4.7.36)

Алгоритм адаптивной оценки модули градиента k и средне-

квадратичного отклонения а имеет вид

(4.7.37)

Входящие в выражения

(4.7.37) частные

производные довольно громоздки. При q≠3 приведенные зависимости

будут еще сложнее, а при нечетных q, возможно, и не удастся найти их

явное выражение для (4.7.34), необходимое для организации процесса

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

производных (4.7.18) целесообразно воспользоваться методом Монте-

Карло. Рассмотрим этот подход в общем виде.

Пусть случайная величина х является заданной функцией

независимых случайных величин у

, ..., y

x = f (y

, ..., y

) (4.7.38)

с заданными законами распределения

( y

, C

(i)

) (i = l, ..., l), (4.7.39)

где C

(i)

= ( c

), ..., ck

(i)) — векторы параметров распределений

(4.7.39), которые нужно определить по наблюдаемым реализациям

(4.7.2) величины х.

Пусть плотность распределения х имеет по-прежнему вид (4.7.1),

где, однако,

= c

(1)

, c

= c

(1)

, ..., c

= ck

(l)

(4.7.40)

(4.7.41)

Ввиду сложности функции (4.7.38) зависимость (4.7.1) в

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

идентификации (4.7.15) вместо градиента (4.7.18) следует ввести его

оценку

(4.7.42)