ГЛАВА V. ПОСТРОЕНИЕ АДАПТИВНЫХ ПРЕДИКТОРОВ ПРЕСТУПНОСТИ

S.Î. Градиентный подход к построению адаптивных предикторов

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

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

%[n+l] =f( Ф M, g /и/, и, « /. а) ,        (5,1)

где X [п+1] - прогнозируемая последовательность на период м-*-/; <Цп] - оператор преобразования исходного ряда в прогнозируемый; g[n] - ряд, связанный с прогнозируемым и определенным образом влияющий на него; и - текущее дискретное время; s - допуски прогноза; / - период упреждения; а - некоторый числовой параметр, определяющий свойства функции /(•), її задан критерий оптимальности, выраженный в виде функционала вектора Ф

Q(<P)=MX{Q(X,0)},            (5.2)

в явной форме неизвестный. Это значит, что пло «госта распределения р(х) неизвестна, а известны лишь реализации Q(X, Ф}, которые зависят от последовательностей Хк вектора Ф, Задача состоит в определении оптимального вектора Ф*, доставляющего экстремум Функционалу (5.2). Единственно возможный путь решения этой за-Дачи связан с наблюдением реализаций и их обработкой с помощью вероятностных итеративных методов [25]. Запишем условие оптимальности в виде

У&Ф) = Мх (Чф 0(Х,Ф)} = 0 ,            (5 3)

где

-68-

представляет, собой градиент £)(.А', Ф) по Ф,

Здесь нам неизвестен градиент функционала, т.е. У{?(Ф), з извест-

ны лишь реализации Ч фС(Х,Ф).

Центр тльная идея вероятностных итеративных методов, в общем случае имеющих вид

ФЫ~Ф{а-\}-Г\п}ЧфО(Х\п},Ф(п-\})                (5.4)

заключается в выборе матрицы Г[п] с использованием различных разновидностей процедур нелинейного программирования при помощи замены градиента функционала V £?(<?)

Сказанное проил;іюстрируем примером построения

у

настройки коэффициентов предиктора .т{л]=Ф \п- \\X\n. р\ на ос нове критерия минимума суммы квадратов ошибок

Записав выршкение для градиента криіерия идентификации на л-й итерации

УФЄ(А-,Ф) = -2А'г(л>/7Кф.]-ФГ{п- 1Щп,р]),       (5.5) несложно получить алгориш настройки коэффициентов в виде

Ф [н] = Ф [п - 1} + Г [п]ХТ(п,р)(х{п] - ФТ[п ~ 1 1^4,^1? (5.6) • с неизвестной матрицей Г[п], вопросам опрьделегйя .-оперой посвящен следующий раздел. Необходимо отмс гчть, ню к нроцедурем типа (5.4) относятся и алі'оритмьі стохастической ангфоксимадан [17] втом случае, если Г[п] удовлетворяет 'шк называемым условиям Дворецкого:

_

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

В тех случаях, когда по какой-либо причине невозможно полу-vs'T. градиент реализации ЧфО(Х,Ф)> но сами реализация VQ',1/1) могут быть измерены, можно ясли ît'iiObaffc поисковые алгоритмы адаптация. Введем обозначения

0+(Х,Ф,а)*(0(Х,Ф+аІІ,..„0(Х,Ф ю/.)),         (5.7)

(5,8)

где      а • скаляр,     / , (і = 1, 2, .... р) - базисные векторы,     такие, чту /І(1,0, ..., 0), /2(0,1,. ...0),...,/,(0, 0,. ..,!)•

Градиент оценивается приближенно с помощью   разделенных •донос гей

^£> „ уф ± ОСЛ'.Ф.а),         (5.10)

2«

или

(5-Й)

(5.12)

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

Ф [п]*Ф \п - 1]- Г [n]V0± 0(Х[п},Ф[п~\1а[п}).        (5.13) В заключение необходимо отметить, чю    адаптивный    подход оказывается предиочгтельным даже в тех случаях, когда можно применять и обычный метод,

5.2, Одношаговые вдаптмвчые алгоритмы ооегроегзна предикторов

Рассмотрим адачу прогаоэировакия временной последоваїель-ностн -V в момент времени т по данным о ее предыстории [15]. Пусіь оценка (ирої поз) х[гі\ представлена линейной формой

.гі.           (5.14)

где <Цп-1}^(р,\п-\1 <рг[п-Ц ,,.„,-{\), \\п,р] ~(х\п-\1 х[п~2],   ..„

)г, \\п,р]

Использование   квадратичного   критерия    идентификации    и Градиентной   процедуры   настройки   коэффициентов   гф-е.лм; позволяет получить алгоритм »ида

<Pl\n\ = 9t{n-l\ + Y [n]v\n]x\n-'l         IS Ь)

или в м?.т[жчиой форме

Ф{п\ = Ф[п~ l\ + r\»}v[»] Al" ~p\,    О ! (•>)

где v[«]=T|»]-i|n] - ошибка нроінозирований на н-м шш«, ;-|«] -некоторый положительный параметр.

Значение параметра у[«] должно выбираться на ^і,і\дс.,.І ..... дя кч условий   максимальной   скорости    сходимости

-70-

Вводя критерий в = \в \n~\f- -\\в Dîjf2, где О [i]~Ф*-Ф[і], Ф* * вектор значений коэффициентов "идеального" предиктора,, | • | -евклидова норма, и минимизируя его на каждом шаге по у [я], несложно получить оптимальный алгоритм настройки. Для этого запишем следующие очевидные соотношения:

Ф [п] - Ф[п]- Ф -Ф[п~\]-у [п\\?[п]Х[п-р],

(5.17) (5.18)

Далее имеем

откуда следует, что

«-

0

Ришив уравнение

несложно получить оптимачьное значение

/    as ————

Учитывая очєвщщое соотношение От[п - ПХ[п,р} = (Ф* - Ф[пЪТ

можно переписать (5.22) в виде

(5.19)

(5.20) О, (5.21)

•     (5.22) in], (5.23)

Х*[п,р]Х[п,р]

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

-.Г—І Ъ1Т—.    —1

-,              (5.25)

чтс совпадаем- с апгоригщом Качмажа [33].

Аналогичный   результат   с     использованием    методов сто-хасмяеской ашірогссимішин 6ь?л получен в [84], при этом

ГІ»! = - , (5.26)

ч

что удовлетворяет условиям Дворещсого.

Известно [71], что алгоритмы типа Кяшажа обладают высокой •>:оростью сходимости в условиях некоррелированности наблюде-

-7l-

няй х[і]. Для случайных последовательностей, характеризующих значения реальных показателей преступности, это условие, как правило, не выполняется. Заметим, что искомые коэффициенты <р t являются функциями автокорреляций процесса и в принципе могут быть определены путем решения системы уравнений Юла-Уокера. Однако в случае значительной коррелированности наблюдений эта система может оказаться плохо обусловленной, что приводит к неустойчивому решению.

Для обеспечения устойчивосы и повышения точности прогноза временной последовательности х[п] в условиях коррелированности ее отдельных наблюдений можно восионьчоваться методом регуляризации А.Н.Тихонова, в соответствии с которым вмесіо обычного квадратичного функционала минимизируется функционал

!),            (5.2?)

где aàO - параметр регуляризации, 0(Ф[п]) -регуляризующий (спшжившощий) функционал, который в простейшем случае может быть принят в виде

= ~W я

(5.28)

Поскольку' функционал (5.27) (или ею градиент) заданы лишь при-

б нп.і-'л.ю, чочное решение регуляризованной задачи вообще не« BcmuM.no и поэтому негод регуляризации А.Н.Тихонова здесь в "чистом виде" неприменим. В свят с этим посгроение регуллри-зованных алгоритмов нрої иошроаания временных последовательностей будем проводігі'ь на основе сочетания и'дей адаптации и регуляризации. Тогда Ірадиентньїй процесс минимизации критерия (5.27) с учетом (5.28) и максимизацией критерия ©описывается выражением

v[n]X[ntp]

1-І       *.     ' f   І     fvfPb     fM         1 І і             f &ï   ^Hl\

- ~-     - a«^a i« - Іj j.      p.zv;

Парамеі.ризация   полученного  рсгллярилоыаиного     а,иор>,ша

типа Качмажа с помощью множнгеля релаксации в Іти неі<чзках

г (х[п]-Ф [n]X[»j}] пшвояяет решать задачу оптимального пропш-

знровашш закона изменения временной последоьдгеїь.і. ^ tu л[н] s случае ее дрейфа.

Основными  ііокашіелялш,  характеризующими  работоспосрб»

носи» «VMfuuBnoro реіуляризоьашю)о алгоритма -гипа К.ічмажл нв-

Ь СХОДИМОСІИ И Kd4C(.'iW» ці..

-72-

ния закона изменения временной последовательности в случае ее дрейфа При этом скорость сходимости алгоритма и качество прогнозирования существенно определяются компонентами вектора оценок Фа[п]:

где ФаСт[п] - математическое ожидание ьсктора оценок Фа[п] в установившемся состоянии. Оценки сходимости и скорости сходимости алгоритма (5.29) рассмотрим для стационарных условий, т.е.

когда Ф[га] = const. Тогда уравнение относительно е^[п] при отсутствии помех измерений имеет вид

где р - размерность вектора Л| я/>]. Из выражения (5.32) следует, что в отношении Єд[п] алгоритм (5.29) ведет себя как экспоненциальный фильтр, а сходимость и время его сходимости определяются величиной

' Sa = 1 - 2pp~J + $2p~l - pa(2 - 2$p~l - Зо)      (5.33)

й, в кокездом счете, величиной множителя релаксации р, параметра регул *,- чзацик a и размерностью задачи р.

Omet? м, что для оГычного адаптивного алгоритма типа Качма-

жа (5.25) уравнение относительно ea[n] при отсутствии помех имеет вид

e|[n] = (î-2pp~1 +P2p~*)e^[n-lj,         (5.34)

2

из которого следует, что в отношении ea[n] алгоритм (5.2S) также ведет себя как экспоненциальный фильтр, а сходимость и время его сходимости определяются величиной

S = l-2pp"1+p2p"1.              (5.35)

'ьгчным Вместе с ••с алгоритма меньс^. в конечном счете, на временной последова-очлеко еведенигг.ї до-

Сравнивая (5.33) и (5.35), видно, что они отличаются на величину pa(2~2pp-i -pa), которая для условий монотонной сходимости (О < р < ! ) всегда больше нуля. Поэтому в этих л словиях | Sa | < j S j, что указывает л& дртшую сходимо-еть адаптизноги регуляризован-н Ігор--'-»® типа Качмаже ^о сейнер . сходимости у регулг,

1   ::.-, sto дчнаьзРІ

. •   'ч-;-;:>:ровашя закон;' №

,   ІІ , І.    .v*jae ей дрейфа. З'!" о<

-73

полнительного "запаса устойчивости" в алгоритм (5.29) в виде ре-гуляризующей добавки.

Следует отметить, что способность рассмотренною алгоритма (5.29) прогнозировать параметры нестационарного процесса основывается на том факте, что ом независимо от начальных условий по истечении переходного процесса определяет истинные парамеї-ры стационарного процесса, если j Sa j < 1 . Кроме того, из структуры этого алгоритма следует, что он является многомерным экспоненциальным фильтром со случайными коэффициентами.

Рассмотрим получение количественных оценок качества прогнозирования временной последовательности х[п] в случае дрейфа ее параметров с помощью адаптивного рсгуляризованноі'о алгоритма. Предположим, что статистические свойства вектора Х[п,р] таковы, что его компоненты имеют одинаковые средние значения и дис-переш. Тогда уравнение относительно математического ожидания вектора сценок <£а[п} для алгоритма (5.29) имеет вид

ФаМН 0 - ««1 + А)}Фа[п - 1J+ рАФа{п),       (5.36)

где I - единичная матрица,   а   элементы   матрицы   А= |ау| определяются выражениями

при   І = j,

При    І & j.

(5.37)

Уравнение относительно центрированного вектора оценок ^aW^^aW"^!11)' по которому можно судить о степени разброса оценок Фа[п] относительно среднего значения Фа{п], следует из выражения для алгоритма (5.29) и из уравнения относительно математического ожидания вектора оценок Фа[п] (5.36):

<М = [I - Р(АМ ч- о!)1Ф® [0 -1) + р(А{п] - А)(Ф|> -1] - Фа [п -1])

(5.38)

Для решения задачи оптимизации алгоритма (5.29) может быть использовано уравнение относительно вектора ошибки

ДФа[п] = Фа[п]-Ф[п],         (5.39)

' которое с учетом (5.38) примет вид

АФаМ = [1 - Р(АМ + а!)]ДФа[п ~ 1] +

+ [1 - р(А[п]а1)](Ф[п -1] - Фв[в».      (5.40)

Обычно для реальных временных последовательностей имеет

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

что закон   изменения   параметров    процесса    предсіавляет    р-

-74-

мерный стационарный случайный процесс, статистически не связанный с вектором Х[п,р]. Пусть корреляционная функция каждой из компонент вектора Ф{п] равна

Качество воспроизведения процесса Ф[п] с помощью   адаптивного алгоритма будем оцениваїь но отношению ошибка/оригинал

р = Б2/ФТФ,         (5.42)

где е2 = ДФ^[п}ДФа[п|-   средняя   квадратическая    ошибка.   Для

определения I   запишем решение уравнения (5.140) в виде ДФ{пї= В[п]АФ[п] + Bf п]В[п - 1]ДФ[п - 1] +

+ B[n]pf п - Ц...В[п - k]ДФ{n - k],     (5.43)

где матрица В[п] в соотвечствии с  выражением для алгоритма (5.29) имеет вид

B[n] =

(5.44)

а. ДФ[п] = Ф[п-1]-Ф[п]. Умножая (5.43) слева на Ф [п] и производя группировку полученных в результате умножения слагаемых, получим:

АФТ[п]ДФ[п]= {ДФТ[п]ВТ{п]В1п]ДФ[п]+ ДФТ{п]ВТ[п- l]BT[n] x

х В[п]ДФ[п - 1]+...} + {(ДФТ[пЗВТ[п]В{р - 1]ДФ[п - 1)+ ЛФТ[п- 1] х

х ВТ[п - 1]ВТ[п]В[п1ДФ[п]) + (ДФ[п - 1]ВТ[п - 1}ВТ[п]В[п} х

х В[п - 2]ДФ[ п - 2] + ДФ{п - 2]ВТ[п - 2]ВТ[п - 1)В[п] х

хВ{п-1]ДФ{п -}])+••.}+••. - (5.45)

Середняя (5.45) и учитывая статистические свойства вектора Х[п,р], получим:

п1= ДФТ[п}(ВТВ + (ВТВ)2-+-...)ДФ[п] +

+ 2ДФТ[п]В(ВТВ + (ВТВ)2+...)ДФ[п - 1}+

+ 2ДФТ[п]В2(ВТВ + (ВТВ)2

п - 2]+.., .    (5.46)

Можно показать, что

+РХП .

(5.47) (5.48)

jm (5.47) и (5.48) выражение для ДФ Дф примет вид

— 75 —

ДФТДФ =

2РР'1- -

х (ДФТДФ + 2(1 -Можно показать, что при т=0

-Ра(2-2рр^-ра) -ра)ДФТДФ-к..).

(5.49)

(5.50)

a при m * О

ДФТДФ = -p0|)[i]Sm(l - S)2.

(5.51)

Окончательно можно записать выражение для среднеквадратиче-ской ошибки

(2р~ - Рр    + а(2 -и отношения ошибка/оригинал

є2

- ра(2

- 20 ~ Рр"1+РУ

р = -

(2 - р + о(2 - 2Р - рар))(1 - а(1 -

.-і

- Ô)

- S)

\3.5Z)

(5.53)

где

-1

= ! - 2РР

(5.54)

' - ра(2 - 2РР'1 - ра)

-Р2р~!

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

Таким образом, построенный адаптивный регуляршованный алгоритм типа Качмажа является устойчивым к случайным флук-туациям исходных данных за счет введенного дополнительного "запаса устойчивости" aQ(O{n]), по сложности реализации не отличается от обычных адаптивных алгоритмов [50] и в целом является эффективным средством прогнозирования временных последовательностей.

-76-