Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.intsys.msu.ru/magazine/archive/v12(1-4)/sokolov-363-388.pdf Äàòà èçìåíåíèÿ: Thu Sep 10 00:03:18 2009 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 00:08:42 2012 Êîäèðîâêà:

. .


, . C x1 w1 + . . . + xn wn - . , , . , , f . f , f . , f , f . , 2n , . , . , , , .


364

. .

. . (n). , n . , n log (n) n log n. . , . , f , U (f ). , U (f ) . , U (f ) , , , U (f ) f .

1. ,
. R ,
n

lw, (x1 , . . . , xn ) =
i=1

xi wi - ,

Rn . w = (w1 , . . . , wn ) , . , -. n f (x1 , . . . , xn ) : E2 E2 , E2 = {0, 1}, , lw, (x1 , . . . , xn ) = x1 w1 + . . . + xn wn - ,




365

, lw f (x1 , . . . , xn ) lw
,

1, n x w - ii f (x1 , . . . , xn ) = i=1 0, . f (x1 , . . . , xn ) f
w,

0; -

,

(x1 , . . . , xn ) .

RT . f (x1 , . . . , xn ) Z-, x1 w1 + . . . + xn wn - , f (x1 , . . . , xn ). Z- ZT . , ZT RT ? . 1. ZT RT . 1 , , . lw, = x1 w1 + . . . + xn wn - s lw, = (s1 , . . . , sn ), : si = 1, wi > 0; 0, ,

i = 1, . . . , n. , f (x1 , . . . , xn ) xi , i {1, . . . , n}, = (a1 , . . . , ai-1 , 0, ai+1 , . . . , an ) , = (a1 , . . . , ai-1 , 1, ai+1 , . . . , an ) , , f () = f ( ). , . lw,sigma , .


366

. .

2. lw, lw , f , s lw, = s lw , . 2 , f , s (f ). . : ? . x, d E2 , xd = x, d = 1; x, d = 0. ¯

f (x1 , . . . , xn ) f (x1 , . . . , xn ) xi1 , . . . , xik ; i1 , . . . , ik {1, . . . , n}; f (x1 , . . . , xn ) = f


xd1 , . . . , xdn , n 1

j {1, . . . , n} dj = 0, j {i1 , . . . , ik } ; dj = 1, . M M , x1 , . . . , xn . M M xi1 , . . . , xik ; i1 , . . . , ik {1, . . . , n}, f M f M xi1 , . . . , xik , , , f M f M . M M , . ZT n n . n n ZT .




367

3. ( ). n ZT 2n , n . . lw , lw , n . lw , lw , :
n

lw



,



; lw



,



= -



+
i=1

wi - wi .

, , . f (x1 , . . . , xn ) f (x1 , . . . , xn ). : f ; f


=

lw lw

min
, ,

f f

l ; l




.

lw lw ,sigma , f f , . (n) : (n) =
f ,f Z T



,sig ma



max

n

f ; f



.

n . (n). 4. log2 (n) n log2 n, n .


368

. .

f (x1 , . . . , xn ) , l1 l2 n , f . , l1 + l2 f . U (f ) n , f . , U (f ) . , U (f ) ? , , U (f ). . 5. f (x1 , . . . , xn ) U (f ) , . , 5 , U (f ).

2. 1
ZT RT , , , ZT RT . . , . 1. lw, f (x1 , . . . , xn ), k lk·w,k· f (x1 , . . . , xn ). lw, = n (a1 , . . . , an ) E2 . lw, ()
n

l,
i=1

xi wi - = 0.

2.
n

ai wi - lw, () =
i=1 n i=1 2 wi

.




369

. = (b1 , . . . , bn ) Rn l, . : inf
n n i=1

(bi - ai )2 , (1)

bi wi - = 0.

i=1

:
n n

L (b1 , . . . , bn ) = 0
i=1

(bi - ai ) + 1
i=1

2

bi wi - .

1 b1 , . . . , bn , Lbi = 0, i = 1 . . . n. , L L
b1

bn

= 0 (2b1 - 2a1 ) + 1 w1 = 0; ... = 0 (2bn - 2an ) + 1 wn = 0.

: 1) 0 = 0, 1 = 0, , , ; 2) 0 = 1, i bi = ai - 1 1 wi . 2 1 bi 1
n i=1

1 ai wi - 1 2

n 2 wi - = 0. i=1


370 ,

. .

n

2· 1 =

aj wj -
j =1 n j =1

.
2 wj

, l i
n

wi bi = ai -

aj wj -
j =1 n j =1

.
2 wj

, ,
n

2w, () = l
i=1

(bi - ai )2 =
n j =1 n

n

=
i=1

,

wi

j =1

aj wj - = 2 w
j n

2

n

2

aj wj -
j =1 n j =1 2 wj

.

aj wj - lw, () =
j =1 n j =1 2 wj

.

. 3. w Rn , R > 0, w Zn Z , w w n lw, (), = (a1 , . . . , an ) E2 lw, () - lw
,

() < < .




371

. lw1 ,1 , lw2 ,2 , . . . , lwk ,k , . . . , lim lim cos k = lim
k wk . w ·wk k |w|·|wk | k

lw, () - lw

k , k

() = 0

= 1, k

-

w wi w wi = wi0 , wi1 . . . wik . . . ; = s0 , s1 s2 . . . sk . . . . w10 , . . . , wn0 , s .
0

w

wk = ( w10 . . . w1k , w20 . . . w2k , . . . , wn0 . . . wnk ) k = s 0 . . . s
k

.

, wk 10k · w , k 10k · k , , , () = lim
k
n

k

lim

lw, () - lwk

, k



n j =1

n

aj wj -
n

-

j =1

aj wkj -k
n

w
j =1 n

2 j

w

n j =1

k



lim lim

aj wj - w
j =1 2 j

-

10k ·

j =1

aj wj -
n

10k

·

w
j =1

2 j



j =1

2 kj



=0

k

w · wk 10k · w · w = lim = 1. |w | · |wk | k 10k · |w | · |w|

. 4. RT ZT .


372

. .

. R- f (x1 , . . . , xn ), lw, , wi , R, i = 1 . . . n. lw, Rn , f (x1 , . . . , xn ) . :
n 1) E2 , lw, . f (x1 , . . . , xn ) 0 1. , f (x1 , . . . , xn ) ZT . lw, = 1 lw , = -1, . n 2) E2 , lw, , .

= min lw, (). n
E
2

, V lw, = v Rn : lw, (v ) < . B n 1 1 2 , . . . , 2 2 . B . 3 , , lw , , wi , Z, i = 1 . . . n, , B V lw, . , , lw, . , lw , , wi , Z, i = 1 . . . n, f (x1 , . . . , xn ). n 3) E2 , lw, , , . =
n E2 , lw, ()=0

min

lw, () .




373

, lw,- 2 , lw, , . , . . 4 1. . ( ). lw, f (x1 , . . . , xn ), lw, , > 0, R, i {1, . . . , n} l(w l(
w1 ,...,wn ),+
1

,...,w

i-1

, w i + , w

i+1

,...,wn ),

f (x1 , . . . , xn ) ,

f (x1 , . . . , xn ) .

3. 2 3
, f (x1 , . . . , xn ) , lw, , f , . . 5. f (x1 , . . . , xn ) lw, f (x1 , . . . , xn ), f , s lw, = (1, . . . , 1). . . n . E2 n f (x1 , . . . , xn ), f () = 1, E2 , < , ) = 0. f , f ( n 1 , . . . , m , k E2 ; k = 1 . . . m. B = A1 A2 . . . Am


374

. .

f , Ai , i , i = 1 . . . m. xj , j = 1 . . . n, Ai , j - i 1. f , xi , i = 1 . . . n, Aj , j {1, . . . , m}, xi . j = (a1 , . . . ai-1 , 1, ai+1 , . . . , an ) , = (a1 , . . . ai-1 , 0, ai+1 , . . . , an ) . j lw, f . j f , w1 a1 + . . . + wi-1 ai-1 + wi · 1 + wi+1 ai+1 + . . . + wn an - 0, w1 a1 + . . . + wi-1 ai-1 + wi · 0 + wi+1 ai+1 + . . . + wn an - < 0, wi > 0. j j xi , s lw, = (1, . . . , 1). . fw, (x1 , . . . , xn ) Z- , lw, . n E2 . - Z- ZT . f
wi = wi , di = 1, wi = -wi , , n w ,

= (d1 , . . . , dn ) ,

(x1 , . . . , xn ) = f

w ,



(x1 , . . . , xn ),

= +

(di - 1) wi ,
i=1

i = 1 . . . n. - Z- .




375

n 6. fw, (x1 , . . . , xn ) ZT , = (d1 , . . . , dn ) E2 = n , (a1 , . . . , an ) E2

f

w ,

(a1 , . . . , an ) = f

w ,

ad1 , . . . , adn n 1

.

. . fw, (a1 , . . . , an )
n

ai wi - .
i=1

fw
n

,

ad1 , . . . , adn n 1
n

, , -

(-1)
i=1

di +1

· ai wi +
i=1

(1 - di ) wi - .

n , = (a1 , . . . , an ) E2 . .

, - . n ZT s Z- n , s. .
n 1) s, E2 , f , f Z T s , f = f , [f ] = [f ]. n

2) E = s (f ), [f ]

.
n n s

n 7. s, s E2 s = s , Z T s Z T

= .

. f (x1 , n , f Z T s , f lw, lw , , wi < 0, si = 0; wi .

... f, >

, xn ) Z- n Z T s . , wi > 0, si = 1, 0, s = 1, wi < 0, s = 0, i i


376

. .

= s - f , lw, lw , . 6 f
w ,

(x1 , . . . , xn ) = f

w ,



(x1 , . . . , xn ) .

= s, 6 n-, , , . . s=s 7 2. 3. 7 , ZT =
i=1 n 2n

Z T si ,
2n

n

s1 = (0, . . . , 0); s2 = (0, . . . , 0, 1); . . . ; s n n i = j , Z T si Z T sj = .
n s

= (1, . . . , 1); ,
n s

s = (1, . . . , 1), = s. Z T

=

[f ] : f Z T . 6 . : = ¯), ( n f Z T (1,...,1) , [f ] Z T (0,...,0) . , = s, n n Z T s = Z T (1,...,1) . , Z T si , i {1, . . . , 2n }, . .
n

4. 4
L lw
,

= max (|w1 | , . . . , |wn | , | |) .




377

f L (f ) = min L lw
lw, f ,

.

, f . ZT n L (n) = minn L (f ) .
f ZT

, (n) (n + 1) · L (n). (n) f ZT n , L (n). , f . , lw, , f , . , L (n). ¯ f = f . , f , . , (f , f ) L (n). log L (n) log (n) log L (n) + log (n + 1) . (2)

n i = (a1 , . . . , an ) E2 ; i = 1, . . . , 2n ; Nf = n : f () = 1} { E2 , f 1. , (w1 , . . . , wn , ), , lw, , f .

, (n) log L (n). log L (n) . f (x1 , . . . , xn ) n E2 . 2n . 2n & (i · w - 0) , i Nf (3) (i · w - < 0) . &
n i E2 \N f


378

. .
n , E2 i i +1

,

n = (i1 , . . . , in , 1) i E2 , i = , N i i f i = - , . i i

2n
i E

&

n 2

· w i

1,

(4)

w = w1 , . . . , wn+1 . , w , (4), (3). w = (w1 , . . . , wn ), = -wn+1 . , (4) M Rn+1 . M n + 1 . w M . w A = aij (n+1)â(n+1) , aij E2

A · w = 1. i ; i = 1 . . . n + 1, A, i Ai , A i- . , i i- . 2, i {1, . . . , n + 1}
wi =

i = 2 · , i ± 1 , i 2 [2]
i

1 2

n +1

· (n + 1)

n+1 2

=

n+1 4

n+1 2

; i = 1 . . . n + 1,




379

, |i | 2 n+1 4
n+1 2

.

, w = || · w (4), wi . , L (n) log L (n) 2· n+1 4
n+1 2

,

n+1 1 · log (n + 1) - n = n log n + o (n) . 2 2

log L (n) . 6. ([1]) n = 2k , k N, k f (x1 , . . . , xn ) , L (f ) 1- e 2n
4n
log 3 2

3, -

()

2

1 2

n log n-n

.
log2 n

, n = 2k , k N, n = 2

. ,

x ). n , f (x1 , . . . , xn ) 6. , f f (x1 , . . . , xn ). , L (f ) : 1 log (3/2) 1 n log n- 3 n 4. L (f ) > e-2n 24 n , n : log L (n) 1 n log n + o (n) . 4

1 · n < 2log2 n-1 < n = 2log2 n n. 2 , x ( -


380

. .

log L (n), 1 n log n + o (n) 4 log L (n) 1 n log n + o (n) , 2

4.

5. 5
lw, lw , lw, lw , , , fw, = fw , . , U (f ) . , , . L , [L] L , , L . 8. f Z- , U (f ) - Z. . . , f . L = {l1 (x1 , . . . , xn ) , . . . , lk (x1 , . . . , xn )} , [L] = U (f ). li L, L, , , [L\li ] = [L]. , L , , . , , L - . lw, U (f ) , lw, .




381

[L] = U (f ), lw, L,
k

lw

,

=
j =1

aj lj , aj N0 , lj L, j {1, . . . , k } .

, c N,
k j =1


k

aj lj c ·



k j =1

aj lj .



p N. : lw, l lw, l . , i {1, . . . , n} c N, lw, l . 4 , lw, = w1 x1 + . . . + wn xn - , , l = w1 x1 + . . . + wi-1 xi-1 + (wi + )xi + wi+1 xi+1 + . . . + wn xn - , = 1 , q N, , lw q i {1, . . . , n}. c = p · q , lw c · l =
i-1 j =1 ,

l = c ·

j =1

aj lj + pxi , i {1, . . . , n} ,

l . l

,

p · q · wj xj + p · q · wi +

=p·q·

1 q

n

xi +
j =i+1 n

p · q · wj xj - =

j =1

wj xj - + p · xi = l .


382

. .

, c, lw, l . , l U (f ) , , l L,
k k

l =
j =1

a lj = j
j =1

aj lj + pxi .

~ = xi . : ~ L ~ L. l l l/ , . . lw, -, . xi -
n

lw

,

=
j =1

wj xj - v (xi , lw, ) = wi
n

.

wj
j =1

: 1) 0 v (xi , lw, ) 1;
,

2) N, v (xi , lw, ) = v (xi , lw

);


3) lw, , lw , , v (xi , lw, + lw , ) max(v (xi , lw, ), v (xi , lw , )).

N,

p , , c, v (xi , l ) > max(v (xi , l1 ), . . . , v (xi , lk )), . , ~ L. , l xi , , xi L. l l = c · (a1 l1 + . . . + ak lk ) + p, p N, , 1 L.




383

- . , - [L] , , U (f ), . . L B . , B L , [B \l] = L. B L , B L l B [B \l] = L. 8 , U (f ) . U (f ) , , . , U (f ) . 9. f ZT , U (f ) . . f (x) = x. f , U (f ) - . , l U (f ) l (x) = wx - , w > 0 > 0. , U (f ) = {w · x - : w ; w, N} .
1

U (f ) . 1. B = {(1,1), (2,1), (3,1), . . . }. w, . , lw, (x) = wx - U (f ) lw, (x) = l(
w -+1),1

(x) + ( - 1) · l1,1 (x) .


384

. .

. 1. U (f ) f (x) = x. , B lw,1 (x), , . B U (x). 10. f ZT , U (f ) . . f (x1 , x2 ) = x1 &x2 . f , U (f ) - . , l U (f ) l (x1 , x2 ) = w1 x1 + w2 x2 - , w1 , w2 , > 0. , U (f ) = {w1 · x1 + w2 · x2 - : w1 + w2 ;
2

w1 < ; w2 < ; w1 , w2 , N} . U (f ) U (f ) = Ui (f ) = lw
, i=2

U
n

=i

(f ),
,

Z L : lw

f; = i .




385

. 2 U (x1 &x2 ). Bi = lw
,

Ui (f ) : (w1 = i - 1) (w2 = i - 1) , i = 2, 3, . . .

B = B2 B3 B4 . . .. , B U (x1 &x2 ). B , i 4 Ui (x1 &x2 ) \Bi ( . 2 ) l(1,1,2) + l , l(1,1,2) = x1 + x2 - 2, l Ui-2 (x1 &x2 ). , B . , Ui (f ) w1 < i, w2 < i. , B , , , w1 - 2, w2 - 2.

B w1 = - 1, w2 = - 1. , B U (x1 &x2 ). . 9 10, 5. 5. , f n . . f , , U (f ) Nn+1 . Nn+1 : N
n +1

= K1 (K2 \K1 ) (K3 \K2 ) . . . ,


386

. .

U2 (x1 &x2 )

U3 (x1 &x2 )

U4 (x1 &x2 )

U5 (x1 &x2 )

U6 (x1 &x2 )

U7 (x1 &x2 )

. 2. U (x1 &x2 ).




387

Ki = {(a1 , . . . , an+1 ) : aj N, aj i, j = 1 . . . n + 1} , i = 1 . . . . Ki Nn+1 i. B , : 1) K1 K1 U (f ). Ki i(n+1) , K1 U (f ) . K1 U (f ) B . 2) (K2 \K1 ). , (K2 \K1 ) U (f ). , K1 U (f ) L2 . L2 , K1 U (f ), 2, . [(K2 \K1 ) U (f )] \L2 B . 3) (K3 \K2 ). [(K3 \K2 ) U (f )] \L3 . L3 (K3 \K2 ) U (f ), K2 U (f ). 4) . . 5) (Ki+1 \Ki ). [(Ki+1 \Ki ) U (f )] \Li+1 , Li+1 (Ki+1 \Ki ) U (f ), Ki U (f ). 6) . . B : B=
i=1

[(Ki \Ki-1 ) U (f )] \Li ,


388

. .

Li (Ki \Ki-1 ) U (f ), Ki-1 U (f ). L1 = . , B U (f ). B U (f ) B , . B . , [(Ki \Ki-1 ) U (f )] \Li [(Kj \Kj -1 ) U (f )] \Lj , j > i, [(Kj \Kj -1 ) U (f )] \Lj , i. B . B , [(Ki \Ki-1 ) U (f )] \Li , i = 1, 2, . . ., . .


, .


[1] Hastad J. On the size of weights for threshold gates // SIAM J. Discr. Math. 1994. [2] . . . .: , 1985.