ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 229
Скачиваний: 1
ГЛАВА II
|
242 |
|
|
|
|
|
|
|
|
|
Если для |
автомата А\ |
с |
начальным |
распределением |
||||||
P i ( 0 ) |
и для автомата А2 |
с |
начальным |
распределением |
||||||
Р 2 ( 0 ) |
имеем |
|
|
|
|
|
|
|
|
|
|
(АХ,ДХ2 . .. AXN/Clc2 |
...cN) |
= Р £ ( 0 ) |
( A X , A X 2 . . . |
||||||
|
. .. AXN/CiC2 |
...ся) |
|
|
|
|
|
(2.8.8) |
||
при |
всех входных |
последовательностях |
С\С2... cN |
и |
всех |
|||||
выходных |
последовательностях |
A X [ A X 2 . . . ДХ^, |
имею |
|||||||
щих длину N, то системы |
(Pi< 0 ) , Тг) и (Р2{0), |
Т2) |
называ |
|||||||
ются |
Л^-эквивалентными. |
Системы |
(Pi ( 0 ) , |
Т\) |
и ( Р г ' 0 ' , ^ ) |
|||||
называются эквивалентными, если они ^-эквивалентны для всех N.
Достаточным условием эквивалентности двух систем
является |
их |
(тх |
+ т2 — 1)-эквивалентность, |
где |
тх и |
|||
т2 — количество |
внутренних состояний |
соответственно |
||||||
автомата Ах |
и автомата А2. |
|
|
|
|
|||
|
|
ВЕРОЯТНОСТИ |
СООТНОШЕНИЙ |
в х о д / ? — |
|
|||
|
|
В Ы Х О Д А АЛГОРИТМОВ САМООБУЧЕНИЯ |
|
|||||
|
|
Рассмотрим |
о д н о м е р н ы й |
с л у ч а й |
(я = |
|||
= 1). Построим матрицы |
T(AXW/c) |
для |
алгоритма |
слу |
||||
чайного |
поиска с самообучением. |
Нумерация |
состояний |
|||||
автомата и переходы из одного состояния в другое для
этого алгоритма при различных значениях |
с и АХ(^' по |
||||
казаны |
на рис. 2.8.1. |
Ах^ |
= — 1, так |
|
|
Пусть |
Дх( 1 ) = 1 и |
как в |
одномерном |
||
случае |
выходы AXW и |
состояния |
W<»' автомата явля |
||
ются не векторами, |
а числами. Тогда составленные по |
||||
рис. 2.8.1 и формуле |
(2.8.2) матрицы переходов при фик |
||||
сированном входном |
сигнале с и при учете |
вероятностей |
|||
выходного сигнала АХ( ^ на yV-м шаге имеют вид (2.8.9) —
(2.8.12). |
|
|
|
|
|
|
|
Яп |
0 |
0 . |
0 |
0 |
|
Qt(lMo(l) |
Я21 |
0 |
0 . |
0 |
0 |
|
0 |
031 |
0 . . . |
0 |
0 |
(2.8.9) |
|
|
0 |
0 |
0 .-• • |
Я2т1,\ |
0 |
|
ПОИСК С САМООБУЧЕНИЕМ
о |
-о— |
|
|
|
-О |
с-о |
|
п*2 |
m,tl |
т. |
йХ-1 |
||||
2т, |
|
|
|||||
2т, |
2т, -1 |
Щ*2 |
- о |
т. |
|
|
|
|
|
|
|||||
2т, |
2щ-1 |
М,*2 |
- О - |
Щ |
|
|
|
Щ+t |
|
|
|||||
о |
- о — |
|
-О |
|
|
АХ-1 |
|
2т, |
2т,-I |
т,*2 |
т,*1 |
|
|
|
Рис. 2.8.1. Графы переходов автомата с переходной функцией, зависящей от выхода автомата для п=\.
|
|
0 |
<7l2 |
|
0 |
0 |
|
0 |
|
|
|
|
0 |
0 |
Я22 |
0 |
|
0 |
|
||
Qi(2)A0(2) |
= |
|
|
|
|
|
|
|
|
(2.8.10) |
|
|
0 |
0 |
|
|
0 |
0 |
• • • |
Qim-\,2 |
|
|
|
0 |
0 |
|
0 |
0 |
• • • |
Ц2тл,2 |
||
|
|
0 |
Ч\\ |
|
0 |
0 |
|
0 |
|
|
|
1 |
0 |
0 |
|
Я21 |
0 |
|
|
0 |
|
Q i ( i ) A ( i ) = J |
|
|
|
|
|
|
|
|
(2.8.11) |
|
|
|
0 |
0 |
0 |
0 |
• • |
a2m-\,\ |
|||
|
|
0 |
0 |
|
0 |
0 |
• • |
<72m,-l,l |
||
|
|
a i2 |
0 |
|
0 |
|
0 |
0 |
|
|
|
|
022 |
0 |
|
0 |
|
|
0 |
0 |
|
Qi(2)Al(2) |
= |
0 |
|
qz2 |
0 |
|
0 |
0 |
(2.8.12) |
|
|
|
0 |
|
0 |
0 |
|
a2mv2 |
0 |
||
16*
7,(ЛХ«)/0) = |
|
|
о |
о |
|
|
|
|
quqи |
q^qii |
о |
|
о |
о |
о |
||
<?21<7и |
о |
q^qzi |
о |
о |
|
о |
о |
о |
|
|
|
|
|
|
о |
о |
о |
О |
О |
О |
0 |
0 . . . |
q%m—\,\q%m—1,i 0 |
72т,—1,272т,,.? |
||
О |
0 |
0 |
0 |
0 . . . |
|
О |
72m,,l72m, - l,j |
q2m[,2q2ml,j |
|
|
|
|
|
|
|
|
(/=1.2) |
|
|
|
|
|
|
|
|
(2.8.13) |
Т\ (АХО)/1) = |
|
|
|
|
|
|
|
|
7 l 2 7 l j |
^п^г з |
0 |
0 |
о |
|
|
0 |
0 |
722713 |
о |
7217зз |
0 |
о |
|
|
0 |
0 |
0 |
7з27гз |
0 |
g3 i743 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 . . |
• 7 2 г п , - 1 , 2 7 2 т - 2 , з |
0 |
7 2 т - 1 , 1 7 2 т , , j |
|
О |
0 |
0 |
0 |
0 . . . |
О |
<72 т„272т,-1„? |
72m,,l72m,,j |
|
|
|
|
|
|
|
|
|
(/=1.2) |
|
|
|
|
|
|
|
|
(2.8.14) |
ПОИСК С САМООБУЧЕНИЕМ
245
По матрицам (2.8.9) — (2.8.12) и формуле (2.8.4) нахо дим матрицы (2.8.13) и (2.8.14) переходов автомата для
фиксированных |
его входных с = 0, 1 и выходных AX<i> |
(/ = 1, 2) сигналов. |
|
Из формулы |
(2.8.7) с учетом матриц (2.8.13) и (2.8.14) |
имеем следующие выражения для определения вероят
ности |
появления |
сигнала АХ^'> (/=1 , 2) на выходе авто |
||||||||
мата, |
если на его вход был подан сигнал |
с (с = 0, 1): |
||||||||
Вер (АХО)/0) = Р ^ Г , (ДХО-)/0)е, = р1 <0 ) |
(ЯиЯи + ЯмЯа) + |
|||||||||
|
|
2т, -1 |
|
|
|
|
|
|
|
|
|
+ |
^ P i i 0 ) |
(ЯпЯг-из |
+ Яг2Я1+1,з) + |
|
|
|
|||
|
|
i = 2 |
|
|
|
|
|
|
|
|
|
+ |
Р2т,т |
{Я2т[Л |
q2m,-l,j |
+ Я2т1,2Я2т„]) |
\ |
(2.8.15) |
|||
Вер(АХО-)/1) = Р1 (°)Г1 (АХ(Я/1)е1 = р 1 ( 0 ) ( ( 7 1 ^ 1 з . + <71 1 ^) + |
||||||||||
|
|
2т,— 1 |
|
|
|
|
|
|
|
|
|
+ ^ Рг(0)(Я12Яг-\,3 |
+ Яг\Яг+\,з) |
+ |
|
|
|
||||
|
|
г = 2 |
|
|
|
|
|
|
|
|
|
+ |
Р 2 т , < 0 ) |
(Я2т1,2Я2т1-и+ |
<72m„l<72m„j) » |
(2.8.16)' |
|||||
где Pi ( 0 ' — вектор |
начальных вероятностей |
состояний |
||||||||
|
|
автомата |
Ах |
(алгоритма |
покоординатного |
|||||
|
|
самообучения); |
|
|
|
|
||||
Р 1 ( 0 > = ( р 1 ( ° ) , . . . , Р 2 п г 1 ( 0 ) ) ; |
|
|
|
|
'2.8.17> |
|||||
Г,(АХО')/с) |
определены |
формулами |
(2.8.13), |
(2.8.14); |
||||||
ei — единичный вектор размерности |
2т1: |
|
|
|||||||
|
1 |
|
|
|
|
|
|
|
|
|
е , = |
|
> 2т, |
|
|
|
|
|
|
(2.8.18) |
|