книги / Методы и средства цифровой обработки пространственно-временных сигналов
..pdfЭлементы ( I ) - суть |
непустые |
подмножества |
/, М |
о коли- |
||||||||||
чеством элементов, |
не превосходящим |
N . |
|
|
|
|
||||||||
|
Полагаем |
У р с Р |
, Е € УС' |
С е ( б С ) [Е ] |
; - |
|
|
|||||||
что |
Х ( р , Е , С) |
|
есть |
ив/ |
множество всех |
отобра |
||||||||
жений |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X |
0 . СГЁ1 ~ |
Р |
|
%ДЛЯ квздого из которых |
Х (0)=р |
|||||||||
н |
Уд 6 Т,С[Е] |
|
|
|
|
выполняется: |
|
|
|
|
||||
|
Х ( * ) е А С(6) (X ( 6 - 0 ) |
|
|
|
|
|
|
|||||||
Элементы |
X ( р уЕ,С) |
- "движения", отвечающие начальному |
||||||||||||
состоянию |
р |
и |
|
последовательности |
С |
выполнения опе |
||||||||
раций, нумеруемых числами из |
Е . |
|
Именно движение ХеХ(руЕ>С) |
|||||||||||
начинается в |
точке |
|
р |
, |
затем |
|
X (1) |
выбирается из |
||||||
А ц 1)(Р) |
и т .д . |
Тогда |
У р еР , |
Е € УС, С е ( 6 1 )[Е ] 7 |
||||||||||
X е X ( Р , Е у С) |
|
|
число |
|
|
|
|
|
|
|||||
^ ( р , е , с , х )& I в Ш } ( х а - о , х а ) ) |
|
|
( 2) |
|||||||||||
есть затраты на выполнение операций из множества |
Е |
в оче |
||||||||||||
редности |
I |
, |
складывающиеся вдоль движения |
X |
. Качество |
|||||||||
самой очередности |
|
(маршрута) |
С |
естественно при втог харак |
||||||||||
теризовать нижней гранью значений (2) при переборе всех |
Х ё Х * |
|||||||||||||
*\Р,Е,С). |
именно |
У р е Р , Е е Ж |
|
б е ( б 1 ) [ Е ] |
|
|||||||||
число |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т ( р > * Л * |
|
|
( Р , Е , С , х ) е [ 0 , о о [ |
|
|
|
||||||||
|
|
|
Х е Х ( р , Е , С ) |
|
|
|
|
|
|
( э > |
||||
определяет |
качество |
|
С |
. Минимизация |
(3) |
посредством |
||||||||
рационального выбора |
|
С |
составляет основную цель. Тогда |
|||||||||||
У р е Р |
, Е е Ж |
|
|
|
|
|
|
|
|
|
||||
|
П р , Е ) й Щ |
|
Г ( Р , Е , 0 |
|
|
|
|
|
||||||
|
|
|
1 е ( б 1 ) [ Е ] |
|
|
|
|
|
|
____ |
||||
есть соответствующий оптимум затрат. Вводим далее* |
У%€ /М |
|||||||||||||
множество |
|
|
|
|
|
|
|
|
|
|
|
|
|
Т [ 1 ] й ( Е Е е Г с [ Е ] = г ]
(семейство всех |
% -элементных подмножеств |
!уМ ),Кро |
|
ме того, имеем |
Уч Е 1>N: |
|
|
Ж[1]й{Е Е е Х , С [ Е ] = % } = Г [ 1 ] |
|
||
Наконец, полагаем |
Уке 0УИ~1 |
, ЕеТ[М~~к] 3 |
|
что Х * [ Е ] |
естьйв/ |
семейство всех множеств |
|
И Е Л [М" к] |
, содержащихся:кавдое в |
Е . Элементы |
[Е]характеризуют возможные варианты оставшихся, еще
не выполненных после |
к |
шагов, |
операций. Любой из |
этих |
|||||
вариантов доступен исследователю, так что |
Ук € 0,/У~ / |
|
|||||||
реР.,- Е е Т [ М - к ] |
|
|
|
|
|
|
|||
|
1 Р & ] * н ц ^ ' 1-) |
|
|
|
|
и ) |
|||
есть*"полный" оптимум возможных затрат после перехода |
8а |
к |
|||||||
шагов в состояние |
р |
, Наиболее просто величина |
(4) |
вы |
|||||
числяется при к = N-1 |
|
. Именно(Г[М ~(/У~I)] =Л. |
|||||||
Далее |
Ур Е Р 5 |
Е Е Л |
|
|
|
|
|
|
|
Основной интерес представляет |
^д [Р± |
Г,71] |
для тех |
||||||
или иных |
РЕ Р |
, поскольку эта величина характеризует оп |
|||||||
тимум суммарных затрат при выполнении ^ |
N |
(из М |
) опера |
||||||
ций, Переход от |
^ _ 1/*•;•] |
к |
^д |
|
будет осу |
ществляться посредством процедуры динамического программирова
ния, модифицированной соответствующим образом для исследования
маршрутной задачи.
Уравнение Зедлмана, Цель его состоит в определении соотно шений, связывающих функции (4) для разных значений дискретного
времени (нижний индекс в левой части (4)), Конечно, учитывается,
«о Н е Р ^ Х ^ - / ) ,ЕеГ[М-к], }е Е
Е\{1}чГ[М-(к*1)] (е)
<3 учетом (6) и приведенных выше определений Непосредственно йроверяется, что справедлива оледувдая
Теорема |
I . |
Пусть |
к е 0,М-1\ |
( М 7 р в А ; |
ЕеТ [М - |
|
Тогда |
|
|
[ |
~ к ] < |
|
||
|
|
|
|
(7) |
Выражение |
(7) есть |
не что иное» |
как вариант уравнения |
Веллмана. Важной особенностью (7) является "совместная" опта-
миэация: выбор |
/ в Е |
и затем выбор7 € А^(р) |
на |
каждом шаге дискретного |
процесса. |
|
|
Построение функции Веллмана. Соотношения (5) и (7) |
пред |
ставляют фактически принципиальный способ решения задачи о вы-
полнении |
N |
операций из М |
возможных с наименьшими |
суымарными |
затратами. Приведем соответствующую процедуру реше |
ния в достаточно подробном виде, испольэуя содержательную фор му изложения. Обсудим построение системы
(Ч*Г-; ], |
1) |
(8) |
(точки на месте соответствующих аргументов означают, что ука занные функции рассматриваются как целое); систему (6) именуем функцией Веллмана, что вполне согласуется с общепринятой трак
товкой. Построение |
системы (6) |
будет включать |
N |
шагов, на |
пером из которых используется |
(5 ): функция |
|
|
|
[ • ; ] |
последнее сечение искомой функции Вел |
|||
лмана - непосредственно определяется соотношением (5 ). |
|
(см. ( 6 ) - ( 7 ) ) . Дальнейшее постр^эние аналогично, сяо попользу ет (7 ).
Действительно, |
пусть |
(Пе 1,М |
таково, что УкеЩ] |
|
функция |
ц |
I* \ '] |
У®0 построена. |
Если при этом |
/77 = N , то нужное построение функции Веллмана завершено.
Пусть |
/77 < N |
Тогда /77 +1 е / , /У |
и Л/-(/П+Ое |
е 0,М~1\{М~1] . |
Определяем |
. У |
из условия: V р € Р ,Е еТ[М~(1\/~(Л1+!%]
Такам образом, эа |
N |
фагов может |
быть построена |
||
функция Веллмана (8 ). В частности, |
Т [ М ] |
= ( / , М] |
|||
и определена, в силу упомянутой процедуры, |
зависимость |
||||
^0 |
= (1 а [ р ; О Т ) р е Р , |
|
|||
переводящая |
Р |
в [ 0 ; 00 [ |
и представляющая основной |
||
интерес. |
|
|
|
|
|
Реализация оптимальных: решений. Полагаем зафиксированньы
начальное |
состояние |
Ро ^ Р |
Кроме того, |
считаем, |
||
что функция Веллмана |
( 8 |
) уже построена. В итоге |
имеем число |
|||
V |
; Т О |
|
, характеризующее оптимум в мар |
|||
шрутной задаче. Зададимся теперь произвольным числом |
6 * ^ /?> |
|||||
О < в# |
в .качестве |
параметра |
точноотй. С учетом |
(7) име |
||
ем, что |
|
|
|
|
|
|
+ ^ Г г ; / , / п ( У ! Л |
|
С уч. гом (9) выберем Л, Е Т^Ц |
и Р ^ А , ( Р0) , |
тек что |
1 |
к , (Р0 , Р , ) ^ и Р , ; й ч \ ( о С { } ] < - 94 -
|
< К [ Р 0- ,1,Н)+ - М |
|
|
|
|
( Ю ) |
|||||||
|
|
|
|
|
|
||||||||
Далее выбор, |
подобный |
(1 0 )„ следует повторять. Действительно, |
|||||||||||
допустим, |
что |
|
П в /, |
N |
|
и уяе построены наборы |
|||||||
(^ О ш т п |
!>п |
|
|
> (РскеГ^п |
{>л |
^ |
|||||||
|
г- |
Д |
е |
Д /? |
|
|
выполняется Р[€ АоС[(р[-,) ; |
||||||
|
г. |
7 к е |
/,П VI е |
|
/,л |
|
|
|
|
|
|||
|
|
( кфР. ) |
=$>(оСц ф оС( ) |
■ |
|
|
|||||||
|
^ |
|
Д |
|
-/) Рс)< |
[ Ро >^ р ] " ^л I- Рп > |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
(I I ) |
Если при |
этом |
П -N |
, |
то |
построение завершено, причем, |
||||||||
как ето |
следует из |
( I I ) , |
выполняется неравенство |
|
|||||||||
^ |
Д (Р[-1 |
|
|
^0 [Ро ; |
!’М ]+ |
|
(12) |
||||||
Поскольку в данном случае |
[ еС[ |
Сё |
|
есть N |
|||||||||
элементное |
подмножество |
|
^77 |
и |
|
^ |
|||||||
|
|
|
|
|
|
то |
(12) |
означает построение |
Й * -о п ти -. |
||||
мяльного решения. |
|
|
|
|
|
|
|
|
|
||||
|
Пусть |
П < N |
. Рассмотрим |
отдельно |
следующие два слу |
||||||||
чая: |
П<1/~Л |
|
и |
/7=/V-/ |
|
|
__ |
||||||
|
а) Пусть |
Л |
< |
/ У - / 2 |
|
. |
Поскольку Л |
|
|||||
и /,М\$оС1 |
С€ К~П] € Т [ М ~ Я ] |
, |
восполь |
||||||||||
зуемся теоремой |
I . Используя |
(7 )» выберем |
сСп+/е /,М\ |
||||||||||
\[сС^ |
|
Сё /,Л ] |
|
и |
|
Рр+1 ^ |
|
|
|||||
так, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
< ц „ „ г д , . |
|
* С , |
|
|
; № № 1 |
® » |
|||||||
■ и г р г п ' ) ] < ^„ [ р „ ; К Н \ ^ с ( е / 7 Т > ] Л - % |
|||||||||||||
Из |
( I I ) , |
(13 ) |
следует, |
что |
|
|
|
|
|
||||
П±1 |
|
|
|
|
|
|
|
|
|
^ 1 Р п , / > !>М\ |
|||
§ |
^ г Р 1 - п Р с ) < |
№ |
. |
> |
I |
1 е 1 ,П + 1 } ] + |
|
Соотношение (14) фактически означает, что удалось "продлить11
наборы |
(<^'с)сб^п |
) |
( Р^сеЦ* |
на °дан шаг |
0 о х р а |
||||
нением условий' 1 -3 . |
|
|
|
|
|
|
|
||
Пусть |
П = уУ ~ / |
. Воспользуемся соотношением ( 5 ) , |
|||||||
учитывая, что 1,М\ [оС[ |
С€ / \И~1} € Л |
в |
_______ |
||||||
Тогда, используя (5 ), выберем |
сС^е /, М\ [оС{ |
I в /, N"1^ |
|||||||
* Рне |
(Рц-!) |
|
И3 УСЛ0ВИЯ: ____ |
|
|
||||
^ N ^ N -1 |
^ N-1 [ |
Рц~ !о» |
|
|
(15) |
||||
\ |
[сб^ |
с е 1,й - / ] ] |
+ |
ги |
|
|
|
||
Тогда, |
используя ( I I ) , |
получим неравенство |
|
|
|||||
Д воС( (Рм л |
)< V [ Ро |
+ |
|
|
Комбинируя утверждения, отвечающие разным случаям, полу чаем, что посредством алгоритма, основанного на принципе ди намического программирования, после N шагов будут по строены наборы
(Рскея?? |
о,н— Р |
|
такие, что а) Vк € I, N |
С € /, N |
выполняется |
( Ш ) = > и л Ф*е) |
__ |
|
|
|||
в> (р[)1ебд7е Х (ро |
|
/ € I* # ]•(<**)(€пт)‘> |
||||
с > ^ ( Р |
о 4 1 е |
|
ке1~Й |
? |
|
|
(Рзке^й) < ^о,/Ро » |
|
|
|
|
||
В силу произвольности |
внбора |
б * |
, б# |
> 0 7 |
по |
|
лучаем способ построения |
б |
-оптимальных решений при |
||||
всяк°'1 выборе |
б > 0 |
. Конечно же, |
данный алгоритм пост |
роен но "функциональном уровне"; вычислительная реализация это го алгоритма может оказаться весьма затруднительной. Тем не
- 96 -
менее при помощи теоремы I |
определится структура пошаговой |
оптимизации и характеризуется |
логика процесса маршрутизации с |
одновременным выбором параметра.
Библиографичоски И список
1.БКИЛМАН Р. Применение динамического программирования к задаче о коммивояжере / / кибернетический сборник. Вин.9. м ., 1964. С .219-222.
2.ХЭДЛИ Д. Но мнейиое и динамическое программирование.
М., 1967. с.
3.КЕШ Дж.Л. Общая топология. М ., 1981. 431 с.
4.АДЕКСАПДРЯН Р .Л ., ЩРЙЛХЛНЯН Э.Л. Общая топология, М ., 1979. 336 с.
УДК 1319.7 |
А.Р.Хетерин |
(Уральский политех |
|
нический институт) |
|
АНАЛИЗ ПРАВИЛ |
"ПРОСТОЕ ГОЛОСОВАНИЕ" И |
"ВЗВЕШЕННОЕ |
СУММИРОВАНИЕ" 1 ЗАДАЧЕ КОЛЛЕКТИВНОГО РАСПОЗНАВАНИЯ ТРЕХ КЛАССОВ
В различных задачах распознавания могут возникать ытуации,
когда нельзя достигнуть заданного качества классификации при наличии только одного распознающего автомата (РА). В таких слу чаях для повышения достоверности классификации необходимо ис пользовать несколько РА. При этом появляется необходимость объединения в некотором центральном автомате (ЦА) информации, поступающей от различных РА. В работе проводится анализ приме нения правил "простое голосование" и "взвешенное суммирование" при объединении данных нескольких РА с целью коллективного рас
познавания трех классов.
Способ совместной обработки поступивших в ДА данных и ка чество его работы определяются :арактером этих данных и априор ной информацией о рассматриваемой ситуации. В идеальном случае,
т .е . при наличии полной априорной информации о статистике |
из |
||
меряемых признаков в |
РА и |
отсутствии ограничений на пропускную |
|
способность каналов |
связи, |
саждый РА передает измеренные |
значе |
ния признаков в ЦА, |
где осуществляется распознавание классов |
||
|
|
- 97 - |
|
в соответствии с критерием максимуме правдоподобия. Если на пропускную способность каналов связи наложены жесткие ограни чения, то может вложиться ситуация, когда данные, приходящие в ЦА, будут содержать информацию только о решениях, принятых в РА.
Еоли при этом отсутствует полное статистическое описание ситуации
и лЗЬ |
ЗТНО ТОЛЬКО, ЧТО ВОрОЯТ- |
|
|||
ность |
правильного распознавания |
|
|||
одним РА превышает 0,33, |
то це |
|
|||
лесообразной процедурой принятия |
|
||||
решения в этом случае является |
|
||||
"простое голосование" |
[ I ] |
. Это |
|
||
правило означает, что |
в ЦА реше |
|
|||
ние принимается в пользу того |
|
||||
класса, который был выбран боль |
|
||||
шинством РА. Бели из трех |
были |
Рио.1. Зависимость |
|||
выбраны два или три класса, за |
|||||
требуемой ВПР от коли |
|||||
которые проголосовало |
одинако |
||||
чества РА |
|||||
вое количество автоматов, |
то |
||||
|
|||||
.между ними проводится |
равнове |
|
роятный случайный выбор. При г зданной вероятности правильного
распознавания (БПР) применение совокупности РА позволяет сни зить требования к достоверности работы одного РА. На рис.1 по
казана |
зависимость требуемой ВНР одного |
РА Р / |
от I |
-к о |
|
личества идентичных РА в |
системе при заданной ШР всего |
кол |
|||
лектива |
. Из ри с.1, |
в частности, |
видно, что |
при |
Р^ =0,9 |
увеличение числа автоматов в системе (до шести) позволяет сни зить требования к НОР одр го РА до 0 ,7 .
Однако применение правила "простое голосование" в системе,
которая состоит из РА, имеющих существенно различные значения ВНР, может привести к немалым потерям в эффективности работы коллектива. В качестве примера рассмотрим следующую ситуацию. Пусть имеется система, где все РА, за исключением одного, име
ют одинаковую ВОР, |
равную 0 ,4 . Один автомат обладает ВНР, рав |
ной 0 ,9 . На рио.2 |
изображена зависимость ЧПР системы от коли |
чества РА, полученная путем моделизвания описанного случая. Из р и с.2 видно, что, во-первых, ШР всей системы в целом мень-
рч, чем ШР одного "хорошего" |
РА, во-вторых, в рассматриваемом |
- 98 |
- |
интервале |
значений |
с увеличением |
числа автоматов ВПР коллекти |
ва падает. |
Отсюда |
следует вывод, |
что для подобных ситуаций |
требуется иметь хотя бы грубые оценки достоверности работы раз личных автоматов и с их учетом строить правило коллективного
|
■принятия решения. |
|
|
|
|||
|
|
Если известно |
полное |
ста |
|||
|
тистическое |
описание |
работы РА, |
||||
|
т .е . заданы Р[^ |
-вероятнрсти |
|||||
|
принятия решения в |
пользу |
Ь -г о |
||||
|
класса |
С -м РА при наличии |
|||||
|
/ - г о |
класса; |
|
= ГТЗ; |
|||
|
^ = I , I. |
|
и отсутствует |
||||
|
статистическая |
связ;. меяду их |
|||||
|
решениями, |
то |
оптимальной по |
||||
|
критерию максимума правдоподо |
||||||
|
бия процедурой принятия решения |
||||||
|
в ДА является правило |
''взвешен |
|||||
Рис.2. Зависимость ВПР |
ного суммирования". В этом слу |
||||||
чае в |
зависимости от |
поступив- |
|||||
системы от количества РА (Ш1Р |
щего от РА решения в |
ЦА каядо- |
|||||
одного РА - 0 ,9 ; ВР 1 осталь- |
щ из |
классов |
назначается |
свой |
|||
ных РА - 0 ,4 ) |
"в ес". |
Решение принимаётся в |
|||||
|
пользу |
того |
класса, |
которому |
соответствует максимальная сумма "весов" по всем РА. Проведя соответствующую нормировкудэнаем, что значение "веса", прида
ваемого |
^ -му классу, при выборе |
С РА |
I - г о клаоса |
определяется из соотношения: |
|
|
|
|
~ А ^ Р ц с/ Р и |
'> |
|
тРц =пМРф ; А = (тШ Рце/РиТ
Заметим, что п р г
Ре
(!~Ре)/д Р6> о,м
справедливо |
и С= ^ / ° ^ |
. где <^г Щ Щ /(!- Рс), 4 / - |
СИМ |
|
ВОЛ Кронекера, |
т .е . получаем правило "взвешенного |
голосова |
||
ния" [V ] |
|
|
|
|
Зачастую полное статистическое описание работы РА отсу> - |
||||
ствует, т .е . нет априорной I* формации, необходимой |
для реа |
|||
лизации метода |
"взвешенного |
суммирования". Однако |
в этом |
слу- |
Рис.З. Зависимость усредненной ВПР от количества обучающих выборок
чае можно применить процедуру обучения, состоящую в получении
оценки достоверности работы различных РА по мере накопления
экспериментальных данных в процессе работы системы. С учетом этих оценок в ЦА выставляется "вес" решению РА. Данный подход
был реализован при моделировании принятия коллективного реше
ния в |
системе, где все РА, кроме одного, |
имели БИР, равную |
0 ,3 3 , |
а один РА обладал ВПР, равной 0 ,9 . |
Результаты моделиро |
вания даны на рис.З, показывающем зависимость усредненной ШР системы от количества обучающих выборок при различном коли честве автоматов. Из рис.З следует, что при трех РА в системе средняя ВНР приближается к потенциально возможной (0 ,9 ) уже