ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 232
Скачиваний: 1
ГЛАВА II
256
Автоматы будут |
1-эквивалентными |
при данных |
началь |
||||||||||||
ных |
распределениях |
вероятностей |
|
р 2 ( |
0 ) и P 3 W , |
если |
|||||||||
равны выражения |
(2.8.37), |
(2.8.35) |
и (2.8.36), т. е. если |
||||||||||||
P i ( 0 ) 9 n + P 2 ( 0 ) < 7 2 i = 6 i ; |
|
|
|
|
|
|
|
|
(2.8.38) |
||||||
P 2 ( 0 ) 9 l l |
+ P l ( |
0 ) 9 2 1 = *2, |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|||||
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bl |
= A-r2a = J£ р ^ - г 2 |
( р т , ^ ~ |
|
|
Pm2+im); |
|
|
|
|||||||
b2 |
= A - r x a = ^ |
|
|
piM-rl(pm,«>)-pm,+i<0)); |
|
|
|
|
|||||||
|
|
|
1 = 1 |
|
|
|
|
|
|
|
|
|
|
|
|
p<o) |
— вектор начальных |
вероятностей |
состояний |
авто |
|||||||||||
мата со случайными переходами; Р<0) |
= ( |
р х т , . . . , |
р2т2т) |
- |
|||||||||||
Решая |
систему |
уравнений |
(2.8.38) |
|
относительно |
qxx |
и |
||||||||
q2X, |
находим: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 l P l ( 0 ) _ f e 2 p 2 ( 0 ) |
|
б 2 Р 1 ( 0 ) _ Й 1 р 2 ( о , |
|
|
|
|
|
|||||||
Ч |
^ |
р ^ - р ^ ' |
* 2 I = |
Р ^ - р 2 |
^ |
|
• |
( 2 ' 8 - 4 0 ) |
|||||||
Можно показать, что вероятности qx2 |
и q22 определяются |
||||||||||||||
формулами |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
<?12=1-<71Ь |
9 2 2 = 1 - 9 2 1 - |
|
|
|
|
|
|
(2.8.41) |
|
||||||
Следовательно, |
для автомата |
со случайными |
перехо |
||||||||||||
дами и детерминированными |
выходами и произвольным |
||||||||||||||
числом состояний |
2 т 2 |
и произвольным |
начальным |
рас |
|||||||||||
пределением |
состояний можно |
найти |
1-эквивалентный |
||||||||||||
ему |
автомат |
с детерминированными |
|
переходами |
и слу |
||||||||||
чайными |
выходами, имеющий два состояния, причем на |
||||||||||||||
чальное распределение этих состояний произвольное, а
вероятности |
выходов автомата определяются форму |
лами (2.8.40) |
и (2.8.41). |
Найдем требование, при выполнении которого вероят ности выходов автомата с детерминированными перехо дами удовлетворяют условию симметрии
9 u + 92i = l . |
(2.8.42) |
ПОИСК С САМООБУЧЕНИЕМ
257
Из формул (2.8.40) имеем
&, ( Р ! №) _ р 2 ( 0 ) ) + й 2 |
( р , (0) _ ^ 2 |
(0)) |
+ b2 = |
|
|
b{ |
(2.8.43)
По формулам (2.8.39) находим:
(0) 2pi (0)
1=1
(2.8.44)
г = т2 +2
Отсюда следует, что рассмотренные автоматы 1-эк
вивалентны при выполнении следующего условия:
(2.8.45)
г = 1 |
г = т 2 + 2 |
Этому требованию удовлетворяет, например, симметрич ное начальное распределение автомата А 2 .
Следовательно, если начальное распределение авто мата со случайными переходами и детерминированными выходами удовлетворяет условию (2.8.45), то он 1-экви
валентен некоторому автомату с детерминированными переходами и случайными выходами, вероятности выхо дов которого удовлетворяют условию симметрии (2.8.42).
Поскольку в формуле (2.8.45) не содержатся вероят ности ртат и Рт2+\т, то случай, когда у автомата со случайными переходами имеются только два состояния, необходимо рассмотреть отдельно. Для этого случая по формулам (2.8.39) получаем:
Ь1=р1(0)-Г2{р1(0)_р2(0)).
&2 = Р 1 ( 0 ) - П ( Р 1 ( 0 ) - р 2 < 0 » ) . |
(2.8.46) |
|
|
Складывая эти выражения, имеем |
|
61 +fe2=2p1(0)-p1(0>+ p2(0) = pI(0)+p2(0) = i. |
(2.8.47) |
17 — 2014
ГЛАВА II
£58
Следовательно, в этом случае оба автомата 1-экви.ва- лентны для произвольных начальных вероятностей со стояний автоматов; при этом выполняется условие сим метрии (2.8.42).
Теперь сопоставим автомат с детерминированными пе реходами и случайными выходами, у которого имеются два состояния, и автомат, представляющий алгоритм по координатного самообучения, имеющий 2tri\ состояний. Обозначим через Ъ\ и Б2 правые части формул (2.8.15):
2т, - 1
5 l = P l ( 0 4 ? l l ? l l + < 7 l 2 9 2 l ) + |
2j |
Ргт(Яг\Яг-\Л |
+ |
||||
|
|
|
|
г = 2 |
|
|
|
+ <7i2<7i+l,l) + P m , ( 0 |
) |
(q2ml,\q2m-l,l |
+ Q2~mv2Q2mv\) i |
||||
|
|
|
|
|
|
|
(2.8.48) |
|
|
|
|
2 m i - l |
|
|
|
Ь2 = Р\т{Я\2Яп |
+ |
ЯиЯ2\) |
+ |
^ |
P l W |
(Яг2Я1-1,1 + |
|
|
|
|
|
i = 2 |
|
|
|
+ ЯиЯг+\,\) |
+ P 2 m , < 0 ) |
(^2та,,292)11,-1,1 + |
Я2тх,\Я2тх,\) • |
||||
|
|
|
|
|
|
|
(2.8.49) |
Приравнивая правые части формул (2.8.37) к правым частям формул (2.8.15), (2.8.16), получаем систему урав нений
P i ( 0 ) t f i i + / V 0 ) ? 2 i = 5 i ; |
|
|
|
(2.8.50) |
||
р2тЯи |
+ Р\тЯ2\ |
= Ь~2 |
|
|
|
|
|
|
|
|
|||
и находим ее решение: |
|
|
|
|||
Ч п = |
~ Р ^ - р ^ |
' ? 2 1 = |
' P i ' ° ' - P 2 ' ° ' |
• |
( 2 - 8 ' 5 1 ) |
|
Вероятности qi2 |
и q22 |
выхода |
АХ(2> определяются |
форму |
||
лами |
(2.8.41). |
|
|
|
|
|
Следовательно, для автомата, представляющего собой алгоритм самообучения и имеющего произвольное число 2Ш[ состояний, причем начальные вероятности состояний произвольны, существует 1-эквивалентный ему автомат с детерминированными переходами и случайными выхо-
ПОИСК С САМООБУЧЕНИЕМ
25Э
дами, имеющий два состояния, причем начальные веро ятности этих состояний произвольны, а вероятности вы ходов автомата определяются формулами (2.8.51) и (2.8.41).
Найдем условие, при котором удовлетворяется требо вание (2.8.42). Из формул (2.8.51), (2.8.48) и (2.8.49) находим
51 + b2=p1^ |
(ql2qn |
+ qnq2l |
+ qnqu + qi2q2i) |
+ |
2т, |
-1 |
|
|
|
+ 2 |
^ |
(ЧпЯг-\Л + Яг2Яг+1Л + ЯиЬ-1Л + |
||
i = 2 |
|
|
|
|
+ Яг\Яг+1л) +P2mtW |
(<7m„l <72т,-1,1 + |
<72т„2 ^ 2 т , , 1 + |
||
+ 9 2 т 1 |
, 2 ? 2 т - 1 , 1 + Я2т^2т„2) |
= P l |
2т, |
- 1 |
|
+ ^ |
Р»( 0 ) (9*-1,1 + 9<+1,1) + Р 2 т, ( 0 ) |
|
г= 2
+&m„i) = l .
Предположим, что функция выхода обучения имеет вид
( 0 ) (^И + ?21) +
(Ч2Щ-1,1 +
(2.8.52)
алгоритма само
|
1, |
если |
w^>d; |
|
qu=F(wW) |
- l ( l + o > ( i ) ) . |
если |
|a)W»|^d; |
(2.8.53) |
|
0, |
если |
wW<d; |
|
Я12=1-Яп |
|
|
(2.8.54) |
|
^ |
(d = const; 0<d==Sl) |
|
|
|
и что состояния WW) автомата, представляющего собой алгоритм самообучения, определены формулами (2.1.92), т. е. что состояния автомата симметричны относительно нулевой точки
S y ( 2 m l - i + l ) = _ a y ( i ) i |
(2.8.55) |
17*
ГЛАВА П
260 |
|
|
|
Тогда вероятности |
qn (i = 1 , . . . , 2 т х ; / = 1 , 2) |
удовлетво |
|
ряют условию |
|
|
|
Яц + Я2т,-1+\,]= 1- |
|
|
(2.8.56) |
Требование (2.8.52) |
приобретает вид |
|
|
bl + b2=(plW-pSmiV>))(qu+q2l)+2p2mm |
+ ^ |
(Pi{0)~ |
|
|
|
i = 2 |
|
|
|
2m,-1 |
|
- j 5 2 n , 1 - 1 - + i ( 0 ) |
) ( f l f i - i , i + flli+i,i)+2 |
^ j 5 i « » = l . |
|
|
i = m i +1 |
(2.8.57) |
|
|
|
|
|
Это равенство соблюдается при выполнении |
условий |
||
jS.-<0> = P2m.-.-+i( 0 ) • |
|
(2.8.58) |
|
Следовательно, для автомата, представляющего собой алгоритм покоординатного самообучения с произволь ным числом Ъп\ состояний, начальные вероятности ко торых симметричны, т. е. удовлетворяют условию (2.8.58), существует 1-эквивалентный автомат с детерми нированными переходами и случайными выходами, име ющий два состояния, причем начальные вероятности этих состояний произвольны, а вероятности выходов ав томата определяются формулами (2.8.51) и (2.8.41) и удовлетворяют условию симметрии
<7ii+.<72i= 1.
Случай, когда у автомата алгоритма покоординатного самообучения имеются только два состояния, необхо димо рассмотреть отдельно. Из формулы (2.8.52) с уче том условия (2.8.56) имеем
*>1 + &2 = Д 1 < 0 ) ( й 1 + й н ) + Р 2 ( 0 ) ( ^ П + йп ) =
= (Piт+Р2т) |
(<7и + <Ы = <?п + fa = 1 • |
(2.8.59) |
Следовательно, в этом случае автоматы 1-эквива лентны друг другу при произвольных начальных вероят ностях их состояний.