Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v11(1-4)/osokin-635-652.pdf Дата изменения: Mon Feb 18 14:08:22 2008 Дата индексирования: Mon Oct 1 23:57:55 2012 Кодировка: Поисковые слова: m 101

. .

, n- , , , , , . , n- . . . , . .

1. .
, n- N, . , n- , 2n . , , n , . , ,


636

. .

2n ( , , ). , , , . . . [1]. , , . [2]. . . . [3], . . [4]. , . , , [5] [6] . . . 80- . [7]. (exact learning) . - (Probably Approximately Correct learning) 80- XX (. , [8]). , , . , , n- (, ). , n- . .




637

n- , . [9, 10] R , R . R = RR R R , n R o(log 2 n). , , , . , -, . n . n- , i- 1, i- , 0 . - ( . f : B n N) , , , . , , f , , , - (, ), , f . [11]. . . .

2.
k - B k R : B k N, i


638

. .

R(B k ) R -1 (i) B k . R , , k - () . n N. {y1 , . . . , yn } , R k . Gk g : {1, . . . , k } {y1 , . . . , yn , 0, 1}. n n = {R(g (1), . . . , g (k )), g Gk } R n y 1 , . . . , yn , k . n n- 2 k R . R = {R1 , . . . , Rm } . k (Ri ), i {1, . . . , m}, Ri . n = R
max k (Ri ) n R
1



n R

2

...

n R

m

, n- . 2i{1,...,m} R1 : B 4 {1, 2, 3, 4, 5}, R2 : B 3 {1, 2, 3, 4} R3 : B 3 {1, 2, 3, 4, 5}. , , . 1. n = 5, 5 = 5 1 5 2 5 3 R R R R y1 , y2 , y3 , y4 , y5 , f = R1 (y1 , y3 , y5 , 0) 5 . R 2 3 f (y1 , . . . , y5 ) = 4 5 y y y y
1 1 5 1

= = = =

y5 = 0, y3 = 1; y3 = y5 = 0; 1; 1, y5 = 0.

(1)




639

. 1. R 1 , R2 R3 . n : , R Af , B n f n . R Af f (y1 , . . . , yn ). n, m k . R(m, k ) R = {R1 , . . . , Rl } , l m max k (Ri ) k . F
i{1,...,l}

, R R(m, k ). R1 , . . . , Rl R Af , f n . R F F , Af B n . F , . (F , R, f ) A f f F . (n, m, k ) = min
F F RR(m,k ) f

max

max (F , R, f ) n
R




640

. .

. (n, m, k ) n . : 1. k n k o(log2 n), n (n, m, k ) k log 2 n. cn, c < 1, m =

3.
[10] (n, 1, k ) (k -] log 2 k [)] log 2 (n - k + 1)[. , m, n k (n, m, k ) (n, 1, k ). . 1. n, m, k (n, m, k ) (k -] log 2 k [)] log 2 (n - k + 1)[.

4.
[10] A B n , , , n . A. , ] log 2 n[ . A q в n {0, 1} a B n A · a (A a) q в n, (A · a)ij = Aij · ai ( (A a)ij = Aij ai ). A q в n {0, 1} a {0, 1, 2}n A a q в n, (A a)ij = ai , ai = 2; Aij .




641

B k k - x1 , . . . , xk . B = {(1 , . . . , k ) B k : i1 = 1 , . . . , is = s } . , B K (B ) = x11 . . . xss . B1 B2 i i k . B K (B ), B 1 1 B2 K (B2 ). N (B1 , B2 ) , K (B 1 ), K (B2 ), , . R(x1 , . . . , xk ) , k - B k . F {0, 1, 2}k xi1 , . . . , xil , l k , i {i1 , . . . , il } {1, 2, . . . , k } i- F 2, 2. i- Fi F x i , Fi = 2. F (R) , R x i , Fi = 0, , xi , Fi = 1, . , f n , R R , R R, k (R) g Gn , f = R(g (1), . . . , g (k (R))). F , f : B n N n , |R| = m max k (Ri ) = k . R
i{1,...,m}

Rpos , X R1 , . . . , X Rm , essR1 , . . ., essRm , . - Rpos R, R , , , k (R) f = R(g (1), . . . , g (k (R))) g G n . Rpos = R; - essRi , i {1, . . . , m}, k (Ri ), y1 , . . . , yn , 0, 1 . Ri


642

. .

, ess Ri , f = Ri (g (1), . . . , g (k (Ri ))), g (1) = essRi , . . . , g (k (Ri )) = essR(iRi ) . 1 k ess
R
i

;

- X Ri , i {1, . . . , m}, essRi , ; F S (A, l, r, lr, d), . A (u в n) (u ), l r N. S F A B n , l r f : . , lr , d {1, . . . , u}. S , , S , . lr , S : (lr = 0) (lr = 1). d A, f S . S . A f A, d, , c, Af (c) = l Af (c) = r . . a) c , q . d l (dr ) A, S Af l ( r ). lr = 0, dl = d dl , lr = 1, dr = d dr . dl = dl {q }, dr = dr {q }. S (A · c, l, Af (c), 0, dl ).




643

S (A c, Af (c), r, 1, dr ). b) . b u, i {1, . . . , u} bi = 0, Af (Ai ) = l bi = 1, Af (Ai ) = r , Ai i- A. pos j R = N (R-1 (l ), R-1 (r )). R R Rpos R, j R = . A , b ( w), R Rpos essR j R yw . F . A B n u, A , . , u =] log 2 (n + 2)[. 1) Af (0), Af (1), 0 n, 1 n. l = A f (0), r = Af (1). l = r , , B n l = r . Rpos , l. R Rpos K (R-1 (l)). i K (R-1 (l)) , essR = 0. i essR . , , R Rpos f = R(essR , . . . , essR(R) ), 1 k F . l = r , S (A, l, r, 0, ). 2) R R pos , k (R) = |X R |. F X R , : - j X R , essR = 0 (essR = 1) j j j (), Fj = 0 (Fj = 1); - i, j {1, 2, . . . , k } ess R = essR , Fi = Fj ; i j


644

. .

- j X R Fj = 2; - F (R) . , R R pos 2. hF , h {0, 1, 2} , n, j - hF = j Fs , s : essR = yj ; s h .

Af (0F ) = Af (1F ), S (A 2F , Af (0F ), Af (1F ), 0, ) 2. x j , K (R-1 (Af (0F ))) ( ), Fj = 2, essR = 0 (essR = 1 ). j j R Rpos , k (R) = |X R |, 2. 3) |Rpos | = 1, , R, R pos , f = R(essR , . . . , essR(R) ). R1 R2 1 k Rpos , F x1 , . . . , xk(R1 ) F x1 , . . . , xk(R2 ) , : - ess
R i
1

= ess

R j

2

i j , Fi = Fj ;
R j
1

- j X R1 , ess (essR1 = 1) Fj = 0 (Fj = 1); j

=0

- j X R2 , essR2 = 0 j (essR2 = 1) Fj = 0 (Fj = 1); j - F (R1 ) F (R2 ) , F (R1 ) = F (R2 ). R1 R2 Rpos , , R R pos f = R(essR , . . . , essR(R) ). Af (0F ) = F (R1 ), 1 k




645

R1 Rpos . Af (0F ) = F (R2 ), R2 Rpos , y i , i {1, . . . , n}, essR1 , yj , j {1, . . . , n}, essR2 , . Af (0F ) = Af (0F ) , , . 3. . , , f , (1). f 5 = 5 1 5 2 5 3 , R R R R R1 , R2 , R3 .1. ] log2 7[= 3 : 00011 A= 0 1 1 0 0 10101 , Af (00000) = 3 l = 3; Af (11111) = 4 r = 4; l r , S (A, 3, 4, 0, ). Af A: Af (00011) = 4. r = 4, A f : Af (01100) = 2. l = 2, r {1, 2}, A0 0 A0 = 0 0 = 2, dl = {2} = {2}, = A · (01100) A1 = A (01100) : 0000 011 1 1 0 0 ; A1 = 0 1 1 0100 111 dr = {1} {2} = 11 0 0 . 01


646

. .

S (A0 , 3, 2, 0, {2}). Af (A0 ) = 3 = l, 1 Af (A0 ) = 2 = r (, A f (A0 ) 2 2 , 2 {2}, Af (A2 )), Af (A0 ) = 2 = r , , b = (011)T . 3 j R1 = N (x3 x1 x2 , x3 x1 x2 ) = {2}, j R2 = N (x3 x1 , x3 x1 ) = {1}, j R3 = N (x2 x1 x3 , x2 x1 x3 ) = {3}. , , b A0 , ess
R
1

= (, y3 , , ), ess

R

2

= (y3 , , ), ess

R

3

= (, , y3 ).

S (A1 , 2, 4, 1, {1, 2}). Af (A1 ) = 1 4 = r ( Af (A1 ) , 1 {1, 2} 1 Af (A1 )), Af (A1 ) = 2 = l ( Af (A1 ) 2 2 , 2 {1, 2} Af (A2 )), Af (A1 ) = 4 = r , 3 , b = (101)T . j R1 = N (x3 x1 x2 , x3 x4 ) = {3}, j R2 = N (x3 x1 , x2 x3 ) = {3}, j R3 = N (x2 x1 x3 , x2 ) = {2}. , , b A 1 , ess
R
1

= (, y3 , y5 , ), ess

R

2

= (y3 , , y5 ), ess

R

3

= (, y5 , y3 ).

R1 (x1 , x2 , x3 , x4 ). , x2 x3 , R1 . , F : F2 = 0, F3 = 1. 0F = (00001), - 1F = (11011), Af (0F ) = Af (1F ) = 4. R1 1 (4) x4 x3 , , F3 = 2, F4 = 2, 0. essR1 = (, y3 , y5 , 0). , x4 F : F2 = 1, F3 = 0. 0F = (00100), 1F = (11110), Af (0F ) = 2, Af (1F ) = 5, , Af (0F ) = Af (1F ). 2F = (22120) 00110 A = A 2F = 0 1 1 0 0 . 10100

S (A 2F , 2, 5, 0, ). Af (A1 ) = 2 = l, Af (A2 ) = 2 = l, Af (A3 ) = 5 = r , , b = (001)T .




647

5 R 2 , Rpos . R1 R3 j R1 = N (x3 x1 , x3 x1 x2 ) = {1}, j R3 = N (x2 x1 x3 , x2 x1 x3 ) = {1}. , , b A , ess
R
1

= (y1 , y3 , y5 , 0), ess

R

3

= (y1 , y5 , y3 ).

, R1 R2 . 3 : F : F4 = 0, F3 = 0, F1 = 1, F2 = 0, F : F3 = 0, F1 = 1, F2 = 0. F (R2 ) = 2, 0F = (10000) F (R1 ) = 5 = Af (0F ). R1 R1 ) = R (y , y , y , 0), , f = R1 (ess 1135 . . 2. A l r , F S i, i {1, . . . , n}, yi K (f -1 (l)) K (f -1 (r )) , i- A , . . , l r , S l = r . S 1 2, . S , . f l = r , f -1 (l) f -1 (r ) . , yi , i {1, . . . , n}, K (f -1 (l)), K (f -1 (r )) , . 0A , j - , j - A , , j {1, . . . , n}. j - 1 A , j - A , . S 1 2, , , Af (0A ) = l, Af (1A ) = r . , S 1 Af (0A ) = Af (0) = l; Af (1A ) = Af (1) = r , S 2


648
F

. .
F

Af (0A 2 ) = Af (0F ), Af (1A 2 ) = Af (1F ). , Af (0A ) = l, Af (1A ) = r , S . , Af (0
A·c

) = l, Af (1

A·c

) = Af (c),

, Af (0A ) = l. 0A·c = 0A , 1A·c = c. , Af (1A ) = r , Af (0
Ac

) = Af (c), Af (1

Ac

) = r.

, yi K (f -1 (l)) , K (f -1 (r )) . , , Af (0A ) = l, 0A = 0, i Af (1A ) = r , 1A = 1. , i A i , . , , y i K (f -1 (l)) , K (f -1 (r )) . : 0A , , , y i K (f -1 (l)) , yi K (f -1 (r )) . . 3. b) S A, b, . . . b 2, b. i, yi . 2 , A i , . , A . . 4. R R, f n . R S 1 2 X R k . N Af , S , k (] log 2 n[+2).




649

. S . . . 0. S . S S (A, l, r, lr, d) v , S . 2 v , S S (A · c, l, A f (c), 0, dl ), S S (A c, A f (c), r, 1, dr ). 0, 1. , v , S v . D v v . , N = v D N (S ), N (S ) v S , Af S . N l (S v ) , l, N r (S v ) , r . v 0 ( 1) v c 0 ( 1 ), v v 0 ( 1 ). v D v . D f in , D lf in f D f in , 0, D r in D f in , 1. , v1 v2 D v1 D v2 = vDf in D v = D . N=
v D
f in

N (S v )
v D
v

N l (S v ) + N r (S v ) + k
v D
f in

v D

v

N l (S v ) + N r (S v ) +
v D
f in l

N r (S v ) + N l (S v ) +
f in r

v D

v

v D

v D

v


650
v D

. .

+k

.

(] log 2 n[+1)

1+
f in l

v D

f in r

1 + k = k (] log 2 n[+2).



1. R R, f n , k R f . Af , F S f , k (] log 2 n[+2). . S X R k , S X R . , 4, . 5. k =
i{1,...,m}

max

k (Ri ). -

Af , F f S , 2m(k + 1). . S F Af 2 3, Af (0F ) Af (1F ). 2 F Af . , Af (0F ) = Af (1F ) S , X R . Af (0F ) = Af (1F ) K (R-1 (Af (0F ))) , , X R . , , X R k , , R R A f 2k . , R m, 2k m 2. , 3 F Rpos , m, 3 2m. 2k m + 2m = 2m(k + 1). .




651

2. R R(m, k ) f n R (F , R, f ) k (] log 2 n[+2) + 2m(k + 1). . 1 2 (k -] log 2 k [)] log 2 (n - k + 1)[ (n, m, k ) k (] log 2 n[+2) + 2m(k + 1),

.


[1] . . // . . 13. .: , 1965. [2] Hansel G. n // . . . . 5. .: , 1968. [3] . . // - . : . . -, 1987. . 155­163. [4] . . / - . , 1998. [5] . ., . ., . ., . . . .: , 2006. [6] . . . . : , 1986. [7] Angluin D. Queries and Concept Learning // Machine Learning. Vol. 2. 1988. P. 319­342. [8] Valiant L.G. A Theory of the Learnable // Comm. ACM. 27. 1984. P. 1134­1142.


652

. .

[9] . . // IX . . 1. . 2. 2006. . 191­193. [10] . . // , . [11] . . // IX , 75- . . . 2007. . 343­346.