Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v12(1-4)/osokin-159-178.pdf
Дата изменения: Thu Sep 10 00:00:14 2009
Дата индексирования: Mon Oct 1 23:58:28 2012
Кодировка:

,
. . , . .

, . , k log2 n . k : log2 n n .

, . , , . , . XX . [1]

160

. . , . .

. [2] . [3] , . 20 . [4] [5]. . , . (., , [6], [7], [8]) , . . . , , f f . , f f . , , , k log n + 2k . . , k log n. k , n log n . . [9],

161

. , , [10] [11]. , [10], [11] - . . . .

1.
n n E2 = {0, 1}n n- , f : E2 Z2k n , k . , f 0 2k - 1. k,n . Fk,n , f k,n f . , . Fk,n , f , f . (F, f ) F Fk,n f k,n , F , f .

162

. . , . .

~ (k, n) = min
F Fk
,n

f

max (F, f ).
k ,n

: ~ max(k + 1, log2 n) (k, n) min(n, k log2 n), ~ (k, n) log2 n + A(k) n , A(k) , . k log2 log2 n A(k) 2k + k2 . k : 1. k = log2 log2 n + (n), 2 ~ (k, n) log2 n. 2. k n, n ~ (k, n) n.
(n)

0 n .

2.
, . F Fk,n . X X . - = (1 , 2 . . . n ) = ~ ^ (i1 , i2 . . . is ), j, j X . i = (i , i . . . i ) j = (j , j . . . j ) ~ ~ n n 1 2 1 2 ^i,j = {s | i = j } . X s s

163

i = (i , i . . . i ) j = (j , j . . . j ) ~ ~ n n 1 2 1 2 - Xij , Xij = , ^ Xi,j , f (i ) = f (j ); ~ ~ , f (i ) = f (j ). ~ ~

i = (i , i . . . i ) j = (j , j . . . j ) ~ ~ n n 1 2 1 2 - Xij , Xij = , ^ ~ ~ Xi,j , f (i ) = f (j ); , f (i ) = f (j ). ~ ~

, , , . C - H - , . . ^ 1. i, j Xi,j = Xij Xij , Xij , , , = . Xi,j / , : 1) , , , , , . 2) , , , , , , , , , . .

164

. . , . .

2. s · sX

, i, j , s Xij . ,

· s X , i, j , {s} Xij X . ,

3.
, k n. 1. k ~ (k, n) k log2 n n . . F Fk,n, f k,n k log2 n. n E2 y1 , y2 , . . . , yn+1 , y1 , yn+1 , . f k + 1 , , . f , . k. k = 1. f 2 0 1. f . , 0, 1. i , f (yi ) = 0, f (yi+1 ) = 1. f yi , i = n+2 . 2 0 1. ,

165

, yi . , ( ), . . , , . . r = ]log2 n[ . r > n , 2 r , n. , 1, , y1 . : rr , ,..., ] 24 2 r
log2 n[-1

= 2.

f (0, 0, . . . , 0), ( , ), : (F, f ) = 1 + ]log2 n[ - 1 = ]log2 n[ . k = s. k = s + 1. C f . , , k = 1, , . 2 + l . , n , n = 2l . x k - x , x k - x . x ]log2 n [ (k - x) ]log2 n [. F f

166

. . , . .

(F, f ) = 2 + l + x log2 n + (k - x) log2 n = n = 2 + l + k log2 l = 2 + l + k ]log2 n[ - kl k log2 n. 2 . ~ 2. k, n (k, n) n.

. , n. 1 = (1, 0, 0, . . . , 0, 0); ~ 2 = (0, 1, 0, . . . , 0, 0); ~ . . . n ~
-1

= (0, 0, 0, . . . , 1, 0);

n = (0, 0, 0, . . . , 0, 0). ~ . i- n- , . : 1) n - k , 2) n - k - 1 . . k . . 3. k n ~ (k, n) min(n, k log2 n).

4.
. , k n. n k 2 . k 4 .

n 2

167

3. k

~ , (k, n)

log2 n - 1.

. 0 2k - 1 . , k - 1 , k- . ~ = (1 , 2 . . . n ) = (1 , 2 . . . n-k+1 ), 0 = ~ ~ (0, 0 . . . 0, n-k+2 . . . n ) 1 = (1, 1 . . . 1, n-k+2 . . . n ), ~ . w( ) ~ n -k +1 . , , 2 , ~ 1 . 0 . ~ ~ , . , , , . , i- , n-k+1 2i n 2i+1 .

1, (F, f ) , . ~ 3. n (n - 1, n) n. log2 n - 1.

. n - 1 ~ 1 , . . . , n-1 . ~ ( 2k = 2n-1 ,

168

. . , . .

~ i . , ~i = 0. i : , . ~ , r k(M ) n - 1. , i1 . . . it : t =1 ij = 0, j t 2. ij , , , , ij - . , 2 C -, ij ij . t 2, n - 1 , , n - 2 . . 2 3 : ~ 4. n (n - 1, n) = n. : 4. k n ~ (k, n) k + 1.

). M(n 1 , . . . , n-1 : ~ ~ 1 1 2 1 M = . . . n 1
-1

-1)вn

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

1 2 2 2 . . . n 2
-1

.

. , n - k - 1 , . , k + 1 , , . , .

169

, k k + 1, 4 k + 1. . 3 4 . 4. k ~ (k, n) n max(k + 1, log2 n - 1).

5.
, k. k . k = 2 k = 3. 5. k = 2 n ~ (2, n) ]log2 n[ + 2.

. , f . . t 1 . . . t ~ ~ : M t в n, , , , . t log2 n. t ]log2 n[. , , 1 . . . t , ~ ~ M , , M .

170

. . , . .

2 E2 . , . , . , 0 3. . , , , . , (0, 1) 1, (1, 0) 2. , ]log2 n[ 2 ( ), . .

6. k = 3 n : ~ (3, n) ]log2 n[ + 6.

. 5. 3 E2 , , 3 6 1 6. , ]log2 n[ . . , i , ~ , , . , . ( 1 6, 2 5), (3 4). , ( )

171

. : ~ 1 (1, 0, 0) 1 (1, 0, 0) 2 (1, 0, 1) ~ 1 (0, 1, 0) 2 (1, 1, 0) 2 (1, 1, 0) ~~ 2 (1, 1, 0) ~ 2 (1, 1, 0) = 3 (1, 1, 1)

, . , , ~~ . , , . k = 2, , . : (F, f ) = 2 + ]log2 n[ + 2 + 2 = ]log2 n[ + 6. . , ]log2 n[ , , , . , . : 5. A(k) , n ~ (k, n) log2 n + A(k),

A(k) k < log2 log2 n A(k) 2k + k2 .

172

. . , . .

. . 5 6 . k, n. k. , , , , 1, 0, . , , , . , , , log2 n + A(k). A(k) k < log2 log2 n. n . log2 n (. ). s (s 2k ). 2k < log2 n, . i j , ~ ~ , , , , , , . i j . ~ ~ , s . . log2 n , l- 2log2 n-l , . i j , ~ ~ .

173

, 4 () (0, 0) ( , i- j - ), (0, 1), (1, 0), (1, 1). , (0, 1) (1, 0). l 3 : ~ 1) l > j . , . . 2) j > l > i. , (0, 0) (0, 1). 3) i > l. , , , . , (0, 0, 0, 0, 1, 1, 1, 1) (0, 0, 1, 1, 0, 0, 1, 1) (0, 1, 0, 1, 0, 1, 0, 1) 1, 2 3 (i, j, l), (i, l, j ) (l, i, j ) . i- . , , , . i ~ , . s 2s . k s 2 , 1 k 2k = log2 n + 2k , k . ~~ = i j ~ ~ (k, n) log2 n + k log2 2
2k k

= log2 n + k

174

. . , . .

. : log2 L ( L ), ( ) , . 3 : ~ 1) . . , . ~ 2) , . . 2k - s. ~ 3) , - . , ~ , . , . ~~ , . ~~ . , . , . , , , ~~ . , : i1 i2 . . . t2r t t
i
+1 2r = (i1-t 1) (i2-t 1) . . . (L-+1 1) = L L t 2r = i1-t i2-t . . . L-+1 1, L L t

i

i

. ~ , i , ~

175

~ i , . ~ , i = 1, ( ). , 0 1 i . ~ ~ . . , , , . , i i . ~ ~ , . , ~~ ~ f ( ) = f ( ). , , . , . 2 , . , ~~~ . , , . , . , . , , . , 1. , . 2s s . , , , . 2k - s. -

176

. . , . .

, , . T . 2s-T , s - T . s + (2k - s) = 2k . - , , = 1 1 2 2 . . . s ~ ~ ~
-T

s ~

-T

,

i {0, 1} . 2s-T , 2s-T 2k s - T k s - k T s. ~ (k, n): ~ (k, n) log2 n + (2k - s) + T + k log2 2s
-T

log2 n + 2k + k2 .

.

6.
1. . 5 ~ ~ (k, n) log2 n + 2k . , (k, n) log2 n, , : 2k log2 n; 2k = (n) log2 n, (n) 0 n ; k = log2 ((n) log2 n) = log2 log2 n + log2 (n); log
2

2k = log2 log2 n, (n)

177

, k = log2 log2 n + (n), (n) , 2 (n) . . , 2 (n) 0 (n) -. , (n) , . , (n) = - log2 log2 log2 log2 n. 2 3 4.

[1] Hansel G. n // . . . . 5. .: , 1968. [2] . . / - . , 1998. [3] . . // . . 11. 2007. . 587606. [4] Angluin D. Queries and Concept Learning // Machine Learning. Vol. 2. 1988. P. 319342. [5] Valiant L. A Theory of the Learnable // Comm. ACM. 27. 1984. P. 11341142. [6] Uehara R., Tsuchida K., Wegener I. Optimal attribute-efficient learning of disjunction, parity, and threshold functions // Lecture Notes In Computer Science. Vol. 1208. 1997. [7] Damaschke P. Adaptive Versus Nonadaptive Attribute-Efficient Learning // Machine Learning. 41. 2000. P. 197215. [8] . . // . . 20, . 2. 2008. . 4662. [9] . ., . ., . . . .: , 2007.

178

. . , . .

[10] . . // . . , 1963. [11] . . , / . , 2007.