ÿþW a l i d a c j a d r z e w d e c y z j i
( A . D b r o w s k i : O t e o r i i i n f o r m a c j i . W S i P , W a r s z a w a 1 9 7 4 )
S y s t e m i d e n t y f i k a c y j n y S 1
C z y r z u c o n o 1 o r 2 ?
T N
Y N
C z y r z u c o n o 3 l u b 4 ?
C z y r z u c o n o 1 ?
T N
T N
1
2
C z y r z u c o n o 3 ?
C z y r z u c o n o 5 ?
T N T N
4
3
6
5
2 * ( 1 / 6 ) + 2 * ( 1 / 6 ) + 3 * ( 1 / 6 ) + 3 * ( 1 / 6 ) + 3 * ( 1 / 6 ) + 3 * ( 1 / 6 ) = 1 / 3 + 1 / 3 +
+ 1 / 2 + 1 / 2 + 1 / 2 + 1 / 2 = 2 . 6 6
S y s t e m i d e n t y f i k a c y j n y S 2
C z y r z u c o n o 1 ?
1
C z y r z u c o n o 3 l u b 4 ?
C z y r z u c o n o 3 ? C z y r z u c o n o 2 ?
3
4 2
C z y r z u c o n o 5 ?
5
6
1 * ( 1 / 6 ) + 2 * ( 1 / 6 ) + 2 * ( 1 / 6 ) + 3 * ( 1 / 6 ) + 4 * ( 1 / 6 ) + 4 * ( 1 / 6 ) = 1 / 6 + 1 / 3 +
+ 1 / 3 + 1 / 2 + 2 / 3 + 2 / 3 = 3 . 0 0
d l a X = { x 1 , x 2 , x 3 , . . . x N } P { x i } = p i ( i = 1 , 2 , 3 , . . . N )
E ( S 1 ) = 2 . 6 6 E ( S 2 ) = 3 . 0 0
S 1 j e s t l e p s z y o d S 2
p o n i e w a |: E ( S 1 ) < E ( S 2 )
S y s t e m i d e n t y f i k a c y j n y S 3
X = { x 1 , x 2 , x 3 , . . . x N } p 1 = 0 . 9 5 , p 2 , p 3 , p 4 , p 5 , p 6 , = 0 . 0 1
E ( S 3 ) = 1 . 1 2
O b e c n i e r o z s t r z y g n i e m y k o l e j n e z a g a d n i e n i e m o |l i w o [c i u t -
w o r z e n i a o p t y m a l n e g o d r z e w a p y t a D.
M a m y z b i ó r l i c z b , k t ó r e m o g b y r z d a m i w z Bó w t e r m i n a l -
n y c h w t a k i m d r z e w i e :
S ( x 1 ) = 2 S ( x 3 ) = 3 S ( x 5 ) = 4
S ( x 2 ) = 2 S ( x 4 ) = 3
x 1 x 2
x 3 x 4
x 5
G d y w s z y s t k i e a l t e r n a t y w y ( o b i e k t y , p r z y p a d k i ) m a j t o s a m e
p r a w d o p o d o b i e Ds t w o , n p .
p 1 = p 2 = p 3 = p 4 = p 5 = 0 . 2 0 , w t e d y E ( S E ) = 2 . 8 0
J e d n a k |e g d y p r a w d o p o d o b i e Ds t w a s r ó |n e , n p . :
p 1 = 0 . 5 , p 2 = 0 . 2 , p 3 = p 4 = p 5 = 0 . 1
t o [r e d n i a l i c z b a p y t a D w t y m s a m y m s y s t e m i e i d e n t y f i k a c y j -
n y m , E ( S D ) , w y n o s i 2 . 4 0 . C o s p o w o d o w a Bo , |e r o z p a t r y w a n y
s y s t e m s t a B s i l e p s z y ? Z j a w i s k o t o z o s t a l o s p o w o d o w a n e p o -
p r z e z u m i e j s c o w i e n i e ( l o s o w e ) a l t e r n a t y w b a r d z i e j p r a w d o p o -
d o b n y c h w w z Bc h n i |s z y c h r z d ó w ( t j . w z Bó w o s i g a l n y c h
p r z y m n i e j s z e j l i c z b i e p y t a D) . S t d , z g o d n i e z e z n a n o g ó l n r e -
g u B ( z n a n p o d n a z w r e g u By H u f f m a n n a ) k o n s t r u o w a n i a o p -
t y m a l n y c h s y s t e m ó w i d e n t y f i k a c y j n y c h , n a l e |y a l t e r n a t y w y o
n a j w i k s z y m p r a w d o p o d o b i e Ds t w i e l o k o w a w d r z e w i e p y t a D w
w z Ba c h m o |l i w i e n a j n i |s z e g o r z d u .
S c i [l e m ó w i c m o |n a u t w o r z y w i e l e r ó |n y c h d r z e w , p o s i a d a -
j c y c h w z By t e r m i n a l n e o k r e [l o n e g o r z d u . J e d n a k i d e n t y f i k a -
c y j n e o d p o w i a d a j c e t y m d r z e w o m , n i e m u s z b y t a k i e s a m e ,
a r ó w n o w a |n e . M u s i m y b o w i e m p a m i t a , |e n i e k a |d a s e k -
w e n c j a l i c z b n 1 , n 2 , n 3 , . . . , n N m o |e r e p r e z e n t o w a r z d y w z -
Bó w t e r m i n a l n y c h . N a p r z y k Ba d , l i c z b y 1 , 1 , 1 n i e m o g b y r z -
d a m i l i [c i w j a k i m k o l w i e k b i n a r n y m d r z e w i e , p o n i e w a | n i e
w i c e j n i | d w a w z By m o g b y r z d u p i e r w s z e g o . Z a t e m , i n t e -
r e s u j c a m o |e b y o d p o w i e d z n a o g ó l n e p y t a n i e :
J a k i e w a r u n k i m u s z s p e Bn i a l i c z b y n 1 , n 2 , n 3 , . . n N , a b y i s t n i a -
Bo d r z e w o b i n a r n e , k t ó r e g o w z By t e r m i n a l n e m a j o d p o w i e d n i o
r z d S ( x 1 ) = n 1 , S ( x 2 ) = n 2 , S ( x 3 ) = n 3 , . . . , S ( x N ) = n N ?
O d p o w i e d z i n a p o w y |s z e p y t a n i e j e s t n i e r o w n o [ K r a f t a . L i -
c z b y
n 1 , n 2 , n 3 , . . . n N
m o g b y r z d a m i w z Bó w w p e w n y m d r z e w i e w t e d y i t y l k o
w t e d y , g d y s p e Bn i a j t n i e r ó w n o [:
W n a s z y m p r z y p a d k u n i e r ó w n o [c K r a f t a j e s t s p e Bn i o n a ( 0 . 2 5 +
0 . 2 5 + 0 . 1 2 5 + 0 . 1 2 5 + 0 . 0 6 2 5 = 0 . 8 1 2 5 ) , z a t e m l i c z b y 2 , 2 , 3 , 3
o r a z 4 m o g b y r z d a m i w z Bó w t e r m i n a l n y c h b i n a r n e g o d r z e -
w a u p r z e d n i o p o k a z a n e g o .
P o r ó w n a n i e [r e d n i e j l i c z b y p y t a D d l a d w u ( l u b w i c e j ) s y s t e -
m ó w i d e n t y f i k u j c y c h t e n s a m z b i ó r p r z y p a d k ó w u m o |l i w i a
s t w i e r d z e n i e , k t ó r y z r o z p a t r y w a n y c h s y s t e m ó w j e s t l e p s z y . N a -
l e |y j e d n a k p o s t a w i p y t a n i e , c z y ( i k i e d y ? ) d a n e d r z e w o j e s t
o p t y m a l n e , t z n . c z y r e p r e z e n t u j e n a j l e p s z y s y s t e m ? O d p o w i e d z
n a t o p y t a n i e m o |n a u z y s k a p r z y j m u j c z a Bo |e n i e , |e d l a z b i o -
r u p r z y p a d k ó w ( a l t e r n a t y w ) X i s t n i e j e l i c z b a , k t ó r a j e s t d o l n
g r a n i c w a r t o [c i [r e d n i e j l i c z b y p y t a D w s z y s t k i c h s y s t e m ó w i d e n -
t y f i k a c y j n y c h t e g o z b i o r u X . J e |e l i E ( S k ) j e s t r ó w n e t e j l i c z b i e
( d l a p e w n e g o s y s t e m u ) w t e d y w i e m y n a p e w n o , |e j e s t t o n a j -
l e p s z y s y s t e m i d e n t y f i k a c y j n y d a n e g o z b i o r u a l t e r n a t y w . D o -
k Ba d n y z a p i s w s p o m n i a e g o z a Bo |e n i a j e s t n a s t p u j c y :
N i e c h X = { x 1 , x 2 , x 3 , . . . x N } b d z i e z b i o r e m a l t e r n a t y w , z a [
l i c z b y P { x i } = p i ( d l a i = 1 , 2 , 3 , . . . N ) p r a w d o p o d o b i e Ds t w e m
e l e m e n t ó w z b i o r u X . W t e d y d l a k a |d e g o s y s t e m u i d e n t y f i k a -
c y j n e g o S z a c h o d z i n i e r ó w n o [:
E ( S ) > = H ( X )
g d z i e
j e s t i l o [c i i n f o r m a c j i p o t r z e b n e j d o i d e n t y f i k a c j i e l e m e t ó w z -
b i o r u X , l u b k r ó c e j - i l o s c i i n f o r m a c j i z a w a r t e j w z b i o r z e X .
H ( X ) [ b i t ó w ] m o |e b y c z a t e m u z n a n e z a [r e d n i l i c z b p y t a D w
p e w n y m i d e a l n y m s y s t e m i e r o z p o z n a j c y m e l e m e n t y z b i o r u X .
N i e c h , n a p r z y k Ba d X = { x 1 , x 2 , x 3 , x 4 } ,
P { x 1 } = 0 . 5 P { x 2 } = 0 . 2 5 P { x 3 } = P { x 4 } = 0 . 1 2 5
S ( x 1 ) = 1 , S ( x 2 ) = 2 , S ( x 3 ) = S ( x 4 ) = 3
E ( S ) = 0 . 5 * 1 + 0 . 2 5 * 2 + 0 . 1 2 5 * 3 + 0 . 1 2 5 * 3 = 7 / 4
H ( X ) = 0 . 5 * l o g 2 0 . 5 0 . 2 5 * l o g 2 0 . 2 5 2 * ( 0 . 1 2 5 * l o g 2 0 . 1 2 5 ) = 7 / 4
N a s u w a s i p y t a n i e , d l a j a k i c h z b i o r ó w X o r a z o d p o w i e d n i c h
s y s t e m ó w i d e n t y f i k a c y j n y c h S k , j e s t w a |n a ( p r a w d z i w a ) z a l e |-
n o [ E ( S ) = H ( X ) ? I n a c z e j m ó w i c , j e s t e [m y z a i n t e r e s o w a n i
p r o b l e m e m , c z y d l a d a n e g o z b i o r u p r z y p a d k ó w i s t n i e j e t a k i s y -
s t e m i d e n t y f i k a c y j n y , k t ó r y s p e Bn i a t o g ó l n z a l e |n o [? M o |-
l i w o [ u d z i e l e n i a o d p o w i e d z i n a t o p y t a n i e , m o |e o s z c z d z i
m n ó s t w o n i e p o t r z e b n e g o w y s i Bk u . U |y t e c z n y m w r o z s t r z y g n i -
c i u p o s t a w i o n e g o p r o b l e m u j e s t t e o r e m a t s t w i e r d z a j c y , |e a b y
i s t n i a B s y s t e m S i d e n t y f i k u j c y e l e m e n t y z b i ó r u X , k o n i e c z n y m
i w y s t a r c z a j c y m j e s t a b y d l a k a |d e g o i = 1 , 2 , 3 , . . . N , l o g 2 p i
b y B l i c z b c z Bk o w i t . N a r z u c a t o w n i o s e k , |e j e d y n i e n i e k t ó r e
z b i o r y a l t e r n a t y w m o g m i e a b s o l u t n i e n a j l e p s z y s y s t e m i d e n -
t y f i k a c y j n y [ t z n . E ( S ) = H ( X ) ] . W s z y s t k i e i n n e z b i o r y p r z y p a d -
k ó w ( a l t e r n a t y w ) w y k a z u j t a k w Ba [c i w o [, |e z a w s z e i s t n i e j e
s y s t e m i d e n t y f i k a c y j n y , w k t ó r y m [r e d n i a l i c z b a p y t a D r ó |n i s i
o d w a r t o [c i H ( X ) o n i e w i c e j n i | j e d e n ,
t z n . H ( X ) < E ( S ) < H ( X ) + 1 .
W r ó m y d o p r z y k Ba d u r o z w a |a n e g o p o p r z e d n i o ( s y s t e m E ( S D ) ) .
M a m y E ( S D ) = 2 . 4 ( d l a n i e r ó w n o r o z d z i e l o n y c h p r a w d o p o d o -
b i e Ds t w p o s z c z e g ó l n y c h p r z y p a d k ó w ) , p o d c z a s g d y :
H ( X ) = 0 . 5 * l o g 2 0 . 5 0 . 2 * l o g 2 0 . 2 3 ( 0 . 1 * l o g 2 0 . 1 ) = 1 . 9 6 1
Z a t e m E ( S D ) > H ( X ) , a t o o z n a c z a , |e E ( S D ) n i e j e s t o p t y m a l n y m
s y s t e m e m i d e n t y f i k a c j i a l t e r n a t y w z b i o r u X . W r o z p a t r y w a -
n y m p r z y p a d k u j e d y n i e m o |n a p r z y p u s z c z a , |e m o |e i s t n i e
t a k i s y s t e m i d e n t y f i k a c j i p r z y p a d k ó w z e z b i o r u X , d l a k t ó r e g o
[r e d n i a l i c z b a p y t a D j e s t b l i |s z a w a r t o [c i H ( X ) ; w p r z y p a d k u
s y s t e m u d o s k o n a Be g o E ( S D ) b d z i e r ó w n e H ( X ) . M u s i m y j e d n a k
s p r a w d z i , c z y b d z i e t o m o |l i w e ? O k a z u j e s i , |e d l a r o z p a t r y -
w a n e g o z b i o r u a l t e r n a t y w ( z p r z y p i s a n y m i w a r t o [c i a m i p r a w -
d o p o d o b i e Ds t w a ) n i e m o |n a z a p r o j e k t o w a o p t y m a l n e g o s y s t e -
m u , p o n i e w a | l o g 2 0 . 2 o r a z l o g 2 0 . 1 n i e s l i c z b a m i c a Bk o w i t y m i .
Z t e g o w i c w z g l d u , [r e d n i a l i c z b a p y t a D j e s t l i c z b z p r z e d z i a -
Bu
E ( S D ) "
" < 1 . 9 6 1 , 2 . 9 6 1 >
"
"
[ B y m o |e n a l e |y p r z y p o m n i e d e f i n i c j l o g a r y t m u :
l o g B N = Z
B Z = N
( n p . l o g 1 0 2 = 0 . 3 0 1 0 , p o n i e w a | 1 0 0 . 3 0 1 0 = 2 )
l o g 2 N = Z , w i c 2 Z = N
Z l n 2 = l n N
Z = l n N / l n 2 = l n N / 0 . 6 9 3 1 ]
Wyszukiwarka
Podobne podstrony:
8zti8zti8zti&8zti uzup8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8ztiwięcej podobnych podstron