close

Вход

Забыли?

вход по аккаунту

?

Воронцов К.В. - Лекции по искусственным нейронным сетям (2006).pdf

код для вставкиСкачать
?????? ?? ????????????? ????????? ?????
(????????)
?. ?. ????????
9 ?????? 2006 ?.
??????????
1 ????????????? ????????? ????
1.1 ??????????? ????????? ???? . . . . . . . . . . . . . . . . . . . .
1.1.1 ???????????? ?????? ? ??? ?????????? ?????? . . . . . .
1.1.2 ?????? ???????? ?????????? ??????? . . . . . . . . . . .
1.1.3 ???????? ??????? . . . . . . . . . . . . . . . . . . . . . . .
1.2 ???????????? ????????? ???? . . . . . . . . . . . . . . . . . . . .
1.2.1 ????? ????????? ??????????????? ?????? . . . . . . . . .
1.2.2 ????????? ?????????? ? ???????? ???????????? ????????
1.2.3 ????????????? ?????? ???????? . . . . . . . . . . . . . .
1.3 ???? ???????? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 ?????? ????????????? ???????? . . . . . . . . . . . . . . .
1.3.2 ?????????????????? ????? ???????? . . . . . . . . . . .
1.3.3 ????????? ???? ?????????? ??????????????? . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
2
4
9
12
12
15
19
20
20
22
24
?2?
1
????????????? ????????? ????
???????? ? ?????? ???????? ????????? ?? ?????? ???? ?????????? ????????????, ????????? ??????? ? ?????????. ???????????? ?????? ?????? ?????????
?????????? ??????, ????? ??????? ???? ?????? ????? ??????? ??????, ? ??????????? ??? ???????? ? ?????????????? ???????????.
???? ????????????? ????????? ???? (arti?cial neural networks, ANN) ???????? ???? ????????? ??????????? ????????? ???????????? ????????? ?????. ??????? ??????? ???????? ? ???????? ??????? ??????? ??? ?????????, ??????? ?????
??????? ? ??????? ??????????? ??????????. ?????? ??? ????????? ??????? ?????? ???????????? ????? ????????? ?????? ?????????? Ф???????????╗ ???? ?????
???????? ???????????????? ??????? ???????. ????????? ??????? ???????????
????????????? ANN ???????????? ????? ?????????????? ??????, ??????? ????
?????????? ???????? ? ????????????????.
1.1
??????????? ????????? ????
1.1.1
???????????? ?????? ? ??? ?????????? ??????
?????????? ? ????? ?????? ?????????? ? ???????? ?????? ??????? ?????? ?
????????????? ???????. ?????? ????? ????????? ????????????? ????????? ? ?????????, ? ???? ??????? ?????? ??????? ? ?????, ?? ????? ???????? ????????? ???????,
??????????? ? ?????? ??????? ???????. ?????? ??????? ?????? ????? ?????????? ? ???? ??????????: ??????? ? ????????????. ? ???????????? ????????? ??????
?????????? ????????????? ??????? ????????? ????? 100 ?? ? ????????????? 1 ??,
??????? ???????? ?? ?????? ?? ????????. ?????? ??? ??????? ???????? ????????
????????, ?????????????? ????????????? ????????????? ??????? ?????? ????????
??????. ??????? ????? ?????? ??????????? ??????????????? ??? ????????, ??????
????????? ???? ???????????? ??? ????????? ? ??? ?????????? ???????????. ???? ????????? ?????, ???????? ? ??????, ??????????? ????????? ?????, ?????? ???????????? ? ?????????? ???????, ??????? ???????????????? ?? ?????? ? ???????
?? ????????, ??? ???????????? ??????????? ????????? ??????. ????? ???????????
?????? ????????? ?????? ?????????? ? ????????? ????? ??? ?? ???????? ????????????
????? ????????. ????????? ????? ?????? ???????? ?? ??????, ?? ??????? ?????????? ?????????, ? ???? ? ????? ???????? ???????????? ????? ?????????.
???????? ??????????????? ???????? ???????? ?????????? ??????????????
100 ?/?, ??? ? ??????? ??? ?????? ???????? ??????????????? ?????????????? ??????? ? ?????? ?????????. ??? ?? ?????, ??????? ?????? ????????????? ??????? ??????
?? ????????? ????? ???????????. ??? ????????, ??? ??????????????? ??????? ??????? 102 ???????????????? ?????? ? ??????????? ? ??????? ???????? ????????????.
???? ????????? ????? ???????? ???????? ??????? 1011 ????????, ? ??????
?????? ?????? ? 103 ?104 ?????? ????????. ??? ???????????? ??????? ?????????????????? ??????? ?????? ? ?????????? ??????? ??????? ? ?????. ????? ????????????
???? ???????? ?? ???????? ???????? ???? ??????????????? ???????? ????????.
????????? ???? ????? ?????? ????????. ?? ??????????? ???? ???????????????? ???????? ????? 50 ????????? ????? ????????, ??????? ????????????? ????????? ? ?? ???????? ?????????????????.
?3?
Z
1.5
@ABC
GFED
x1
OOO
OO
w1OO
O
@ABC
GFED
x2 ZZZZw2 ZZZZO'- X
... oo7
N
oo
иии
w
o n
o
o
oo
@ABC
GFED
w0
xn
?
89:;
/ ?>=<
a
1.0
G
0.5
S
0.0
-0.5
T
-1.0
@ABC
GFED
?1
L
-1.5
-3.0
???. 1. ?????? ??????????-??????.
-2.5
-2.0
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
???. 2. ??????? ?????????.
?????? ??????????-??????. ? 1943 ???? ????????? ? ????? [8] ?????????? ?????????????? ?????? ???????, ???. 1. ????? ??????? n ??????? ??????? x1 , . . . , xn ?
???????? ?????????, ??????????? ?????? x. ???????? ???? ????????? ????? ?????????? ??? ???????? ?????????, ??????????? ?? ???? ??????? ????? n ???????
????????. ????? ???????, ???, ??????? ? ??????, ???????? ???????????? ? ??????
w1 , . . . , wn . ???? ??? ?????????????, ?? ??????????????? ?????? ????????????, ???? ?????????????, ?? ??????????. ???? ????????? ??????? ????????? ????????
????? ????????? w0 , ?? ?????? ???????????? ? ?????? ?? ?????? 1, ????? ???????? 0.
????? ???????, ?????? ????????? n-????? ?????? ???????
хX
Х
n
j
a(x) = ?
wj x ? w0 ,
j=1
??? ?(z) = [z > 0] ? ??????????? ??????? ?????????.
? ?????? ????????? ????? ??????? ?, ????????????? ???????? ?????????? ???????? ? ???????? ???????? ???????, ??????? ???????? ???????? ?????????.
????? ???????, ?????? ??????????-?????? ???????????? ????????? ??????????
??????????????.
??????? ?????????. ????? ?????? ??????????-?????? ???? ???????? ?? ?????? ???????????? ???????????? ?????? ? ???????, ? ????? ???????????? ???????
?????????. ?? ???????? ???? ????? ???????????? ??????? ?????????, ??????????
?? ???. 2:
?(z) = [z > 0]
?(z) = (1 + e?z )?1
th(z) = 2?(2z) ? 1
?
ln(z + z 2 + 1)
exp(?z 2 /2)
z
? ??????????? ??????? ?????????;
? S, ?????????? (?????????????) ???????;
? T, ??????????????? ???????;
? L, ??????????????? ???????;
? G, ??????????? ???????;
? Z, ????????????? (????????) ???????;
?4?
????????? ??????. ?????? ?????????????? ??????????? ??????? x0 ? ?1 ? ????????? ??????????? w = (w0 , w1 , . . . , wn ), x = (x0 , x1 , . . . , xn ). ????? ? ? ?????????
??????? ?????????. ????? ???????? ?????? ??????? ????? ???????? ????? ????????? ????? ????????? ????????????:
a(x) = ?
хX
n
j=0
1.1.2
wj x
j
Х
= ?(hw, xi).
(1.1)
?????? ???????? ?????????? ???????
?????????? ???????????. ? 1957 ???? ?????????? ????????? ????????????? ???????? ???????? ???????, ?????????? ?? ?????????, Ф?????????????╗ ? ???????????????. ???????????????? ???? ??????????, ??? ??? ?????????? ???????????
???? ????????? ??????? ?????? ????????????? ????? ????? ???? ???????????. ???
???? ?????? ????????? ?????????? ?????, ??? ??????? ?????????? ?????. ???????????? ?????????? ????? ???????? ? ???????????? ??????????? ??????????. ???? ?? ?????? ???????? ????? ????????? ??? ?????? ????????? ??????????????, ?????
??????????, ?????????? ?????????? ??????????. ????? ???????, ?????? ???????????
? ????????. ? ?????????????? ?????? ??????? ???? ?????? ?????? ?????? ????????????? ????? w.
?????? ??????? ???????? ???????? ?????????????.
????? ??????? ????????? ??????? ??????????? X ? = {x1 , . . . , x? }, ? ??? ??????? ??????? xi = (x1i , . . . , xni ) ???????? ?????????? ????? yi . ??? ????????, ???
? ?????? ????? ???? ???????? ?????????.
????? ??????? ???????? ?????? ????? ????????? ???????? ????????????????,
????????, ??????????? ???????? ??? ?????????? ??????????. ????? ?????????
??????? xi ?? ??????? ???????? ?? ???? ?????? ??????????-??????, ? ????????
?????? ???????????? ? ???????????.
???? ????? a(xi ) ????????? ? yi , ?? ?????? ????? ?? ??????????.
???? a(xi ) = 0 ? yi = 1, ?? ?????? ????? w ?????????????. ???????, ??? ??????????? ????? ????? ?????? ?? ???? wj , ??????? ????????????? ????????? ??????????? xji , ????????, ????? ???????? w := w + ?xi , ??? ? ? ????????? ?????????????
?????????, ?????????? ?????? ???????? (learning rate).
???? a(xi ) = 1 ? yi = 0, ?? ?????? ????? ???????????: w := w ? ?xi .
????????? ??? ???????? ????????, ??? ??? ?????? ????? ?????????? ? ????
???????:
А
б
w := w ? ? a(xi ) ? yi xi .
(1.2)
????????? ??????? ???????? ????? ??? ??????? ???????????, ?? ??? ???, ???? ????
??????????, ??. ???????? 1.1.
??????? ?????. ?????? ??????? ????????, ??? ?????? ???????? ??????? ?1 ? 1,
? ?????? ?????? ???? ?????????? ????????????:
a(x) = sign(hw, xi).
?5?
???????? 1.1. ???????? ??????????? ???????????
????:
X ? ? ????????? ???????;
? ? ???? ????????;
?????:
????????????? ???? w0 , w1 , . . . , wn ;
1: ???????????????? ???? wj ;
2: ?????????
3:
??? ???? i =А 1, . . . , ? б
4:
w := w ? ? a(xi ) ? yi xi ;
5: ???? ???? w ??????????;
????? ???????????? ?????? hw, xi i ? yi ????????, ??? ?????? ????????? ?? ??????? xi .
??? ???? ????????? (1.2) ????????????? ? ????????? ??????? ??????????? ?????:
???? hw, xi i yi < 0 ?? w := w + ?xi yi ,
(1.3)
?????????? ???????? ?????. ??? ????? ??????? ???????????? ? ??????? ???????
??????????, ???????????? ?? ?????? ??? ????????, ?? ? ??? ???????????? ?????????????? ?????????.
??????? 1.1. (???????, [10]) ????? X = Rn+1 , Y = {?1, 1}, ? ??????? X ? ??????? ????????? ? ?????????? ?????? w? ? ????????????? ????? ? ?????, ???
hw? , xi i yi > ? ??? ???? i = 1, . . . , ?. ????? ???????? 1.1 ???????? ? ??????? ?????, ???????????? ????????? ??????? ??? ??????, ?? ?????? ?????????? ????????? w0 , ?????????? ?? ??????? ???????????? ????????, ?? ???????? ????? ?????.
???? w0 = 0, ?? ??????????? ????? ??????????? ??????? ????? ?? ???????????
х Х2
D
tmax =
, ??? D = max kxk.
?
x?X ?
??????????????.
??????? ????????? ??? ???????? ???? ????? ???????? w? ? ???????? ?????
????? t-?? ??????????? wt , ??????? ??? ??????????? ???????? kw? k = 1:
? , wt ) =
\
cos(w
hw? , wt i
.
kwt k
??? t-? ??????????? ??????? ? ???????? ????? wt?1 ????????????? ?????????
?????? x, ?????????? ????? y, ? ?????? ????????? ??????: hwt?1 , xi y < 0. ?????
?????????? ??????????? ????? ?? ??????? ????? (1.3). ? ???? ??????? ????????
????????????, ??????????? ?????? ?????:
«
«
Г
Г
Г ? t « Г ? t?1 «
+ hw? , xi y > w? , wt?1 + ? > w? , w0 + t?.
w ,w = w ,w
? ???? ?????????????? ??????? kxk < D, ??????????? ?????? ??????:
Г
«
kwt k2 = kwt?1 k2 + kxk2 + 2 wt?1 , x y < kwt?1 k2 + D2 < kw0 k2 + tD2 .
?6?
??????????? ?????????? ??????????? ? ????????? ??? ????????:
hw? , w0 i + t?
? , wt ) > p
\
? ? ??? t ? ?.
cos(w
kw0 k2 + tD2
??????? ?? ????? ????????? ???????. ?????????????, ??? ????????? ??????????
??????? t ?? ???????? ?? ?????? x ? X ? ??????, ??? hwt , xi y < 0, ? ??????? ????????
?????????? ???????????.
???? w0 = 0, ?? ????????
??????? ?????? ??????????? ????? ???????????.
?
?? ??????? cos = 1 ??????? t?/D = 1, ?????? tmax = (D/?)2 .
Ц
?? ???????? ???????? ???????????? ??????? ???????? ?????? ???????????,
??? ????????. ???? ??????? ??????? ???????? ?? ?????????, ?? ??????? ????????
?????? ????? ????????? ????????????.
TODO: ????????? ?????? ????????????.
?????????? ???????? ???????. ? 1960 ???? ?????? ? ???? ?????????? ??????? ????????? ????????????? ?????, ?????????? ?? ??????????? ??????????????????
?????? [13]:
Q(w) =
?
X
А
i=1
a(xi ) ? yi
б2
? min .
w
? ?????? ???????????? ?????????, X = Rn , ? ???????? ??????? ?????????,
a(x) = hw, xi, ?????? ?????? ????? ?? ?????????? ?? ???????????? ?????? ????????
?????????. ???????? ??? ?? ??????? ????? ???????????? ??????. ??????? ???????
????????? ??????? ????? ?? ?????? ????????:
w := w ? ?
?Q
.
?w
?????????? ????????, ? ????????, ??? a(xi ) = hw, xi i, ??????? ???????:
?
X
А
б
w := w ? ?
a(xi ) ? yi xi ,
i=1
??? ? > 0 ? ???????? ???? ? ??????????? ?????????????. ????????? ??? ????????? ????????? ? ???????? ??????????? (1.2), ???? ?????? ??????????? ??? ??????
?????? ??? ?????? ???????. ?????? ??????? ???????? ???????? ??????-????????
(delta-rule), ? ??? ???????? ?????? ? ?????????? ???????? ????????? ADALINE.
????? ??????????????? ?????????. ????????? ???????????? ??????????? Q(w)
? ????????? ?Q/?w ?????? ????? ???????, ?????????? ??????? ?? ??????. ?? ?????
????????? ??????? ???????????? ??????????? ???????? ????????. ? ????? ???????
??????????? ???????? ?????????? ?? ??????? ??? ??????? ??????? ?????? ???? ??????????? ??? ??? ????? ?????????? ????? ?? ????????? ?????? ????? w ?????
??????? ?????
???????? ??????????, ??? ??????? ???????? ???????? ???????, ???? ??????????? ??????? ?? ?????? ? ????????? ???????, ?????? ??? ??????? ??????? ??????
ToDo1
?7?
???? ??????????? ???, ? ????? ????????? ?????? ?????. ???? ????? ??????? ???????? ??????????????? ????????? (stochastic gradient, SG). ???????????, ??? ??????
??? ? ??????? ?????????? ???????????, ?? ??????????? ????? ??? ??????????????????
???????????? ????????. ????? ??????? ????????????? ? ????????? ?????????????
???????, ??????? ???? ??????????? ???????????? ??? ????????????? [???].
???????????? ?????? SG ? ???, ??? ?? ????? ???????????, ????? ??????????
?? ????????? ???? ????? ??????? ??????????, ????????? ??????????? ???? ?? ???????? ????? ?????? ??????? ??????? (?? ???? ????, ??? ????????? ?????????? ????? ????????? ?????????? ??? ????????). ????? ??????????????? ????????? ????????? ???????????? ???????????? ????????? ????????? ?????.
?????????? SG ? ???, ??? ?????????? ? ????? ?????? ?? ?????????????.
?? ???????? ?????????? ?????????? ??????? ???? ? ??????. ?????????? ????????
???????? ????? ???????? ? ????????????, ?????????????? ????????? ??????????.
????????? ?? ??? ????? ??????????? ????, ? ??????? 1.2.2.
???????? ?????? ???? ? ???????? ??????????? ? ?????? ????????? ???????????.
? ?????????, ????? ??????????????? ??????? ?????????? ??????. ??? ADALINE ?????????? ?????? ??????????? ??????????? Q ?? ????????? ? ??????? ?????? ????????????. ??? ???????? ? ?????????? ????????? ??? ?????????? ???????????
???? [1] ??? ???????????? ?????????? ??????? xi :
?=
1
1
.
Pn А j б2 =
1 + kxi k2
1 + j=0 xi
????????, ??? ??? ????? ?????? ???? ??????? ???????? ADALINE ???????? [???].
????? ??????????? ? ????????????? ?????????. ??????????? ??????? ????? ???????????????? ?? ?????? ??????? ????????? ? ?????? ??????????? ????????. ?????????? ?????? ????????????? ? ????? ????????, Y = {?1, +1}. ?????? ?????????? ????????, ?????? ????? ?????? ????????????? ?? ????????? ??????? X ? :
Q(w) =
?
X
Б
i=1
ц
? hw, xi i yi > 0 ? min .
w
???????????? ????????????? ?????????
? ??????? ??, ?? ???????? ???? ??????????
??? ??????? ??????????????, ???. 3:
e
Q(w) 6 Q(w)
=
?
X
i=1
2.0
1.5
1.0
0.5
0.0
-2.0
А
б
? ln ? hw, xi i yi ,
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
???. 3. ??????????????? ?????????????
????????? ??????? ??????.
??? ? ? ?????????? ???????.
??? ???????????? ????????????? ?????????????? ??????????? ???????????
А
б
? hw, xi i yi = P{y ? (xi ) = yi }.
(1.4)
?8?
e
? ???? ?????? ??????????? ??????????? Q(w)
???????????? ?????????? ????????
????????? ?????????????:
e
Q(w)
= ? ln
?
?
Y
Y
А
б
? hw, xi i yi = ? ln
P{y ? (xi ) = yi } = ?L(X ? ; w).
i=1
i=1
?? ???????????
А
б(1.4) ????? ????????, ??? ?????? ? ?????????? ??????? ????????? a(x) = ? hw, xi ????????? ??????????? ?????????????? ??????? x ?????? +1.
??? ????????????? ???????? ?????? ?????????????? ???????????? ??? ??????????
?????????? ??????? ? ???????????????? ????????? ?????.
? ?? ?? ?????, ?? ????? ????????, ??? ????????? (1.4) ???????? ??? ????????
??????? ??????????????. ??-??????, ??????? ????????????? ??????? ?????? ???????????? ????????????????? ????????? ?????????????. ??-??????, ?????? ?????? ????? ?????? ????????? ????????, ?. ?. ? ????????? ?????? ????? Ф?????? ?????╗. ????? ????, ????? ????????? ?????? ?????????????? ?????????, ?? ??? ??????? ??????????????? ????????????? ??? ?????????? ?????????? ???????? x0 = ?1.
? ???????????? ??????? ????????????? ?????????? ?????? ???? ??????? ???? ??
????????. ??????? ?????????? ?????? ?????????? ??????? ????????? ??? ??????????? ??????? ? ??????? ?????????????. ?? ????? ???? ??? ???? ???? ??????
??????????? ??????? ?? ??????? ???????.
?????????? ?????? ??????????? ????? ???????? ??????? ? ?????????? ????e
???? ?????????. ???????? ???????? ??????????? Q(w),
???????????????? ?????
?
?????????? ?????????? ???????: ? = ?(1 ? ?) ? 1 ? ?(z) = ?(?z):
?
XА
e
А
бб
?Q
=?
1 ? ? hw, xi i yi yi xi .
?w
i=1
????? ? ?????? ??????????????? ????????? ??????? ?????????? ????? ??? ???????????? ?????????? xi , yi ????? ????? ???:
А
А
бб
w := w + ? 1 ? ? hw, xi i yi yi xi .
?????????? ??? ? ???????? ?????:
Б
ц
w := w + ? hw, xi i yi < 0 yi xi .
TODO: ???????
????? ??????, ??? ???????????? ??????? ???? ?? ??? ????, ??? ?????????? ??????? ??????? ?????. ? ??????? ????? ???????? ????? ?????????? ?????? ?????
?? ??????? xi ??????????? ??????. ? ????????????? ??????? ???????? ??? ??????,
??? ?????? ???????? hw, xi i yi , ?. ?. ??? ????????? ??????. ???? ???? ?????? ???,
?? ?????? ?????? ? ??????? ???????, ???? ?????????????? ???, ????? ??????? ?????? ??? ????? ?????? ?? ???????. ????????? ?????????? ?????? (margin) ?????
????????? ????????? ??????? ? ??????????? ???????????? ???????????? ????????? ???????? ????????????? ? ?????????? ???????? ??????????.
? ????????? ???????? ???????? ???????? ??? ??, ??? ? ??? ??????????? ???????????.
??????? ?????, ??? ????????? ????? ????????? ????? ??????????? ????? ?????? ????????????? ????????? IRLS, ?????????????? ? ??. ???????? ? ???, ??? ?????
ToDo2
?9?
GFED
@ABC
x1 LLL
LL
1 LL
LL& X
@ABC
GFED
/
1
x2
r8
r
r
r
1/2
rrr
@ABC
GFED
?1
/ (x1 ? x2 )
???. 4. ??????????? ??????????, ???????????
???????? ???.
GFED
@ABC
x1 9RRRR
99 1RRR
99
R( X
199
RRR
ll6
+1RRR X
l9l9l9 дB
l
(
ll1
9д
@ABC
GFED
x2 RR1RR ддд999┐
l
ll 6
P
дRдRRR( X lll?1
д
д
1/2
6
д
1/2
lll
ддlll3/2
@ABC
GFED
GFED
@ABC
?1
?1
/ (x1 ? x2 )
???. 5. ??????????? ????, ??????????? ???????? ???????????? ???.
?????????? ????? ??????? ??????? (??????????? ?????), ? ?? ????? ??? IRLS ??????? ?? ?????? ??????? ??????? (???????-???????), ??????? ?????? ?????????????? ??????????.
1.1.3
???????? ???????
????, ???????? ?????? ?????? ???? (1.1) ????????? ??????????? ???????? ????????????? ??? ???????? ?????????. ??? ??????? ???????????? ????? ??????????
??????????? ????????? ??????? ????????????. ?? ?????????????? ??????????? ????????? ??????? ? ??????? ? ????? ?????????? ????? Ф???????????╗ [9]. ????????? ???????????? ??????????? ???????????? ????????????? ????????? ?????????? ???? ????? ??????? ???????.
???????? Ф???????????? ???╗. ????? ????????? ???????, ??????????? ?????????? ??????? ?, ???, ?? (???. 4):
ц
Б
x1 ? x2 = x1 + x2 ? 21 > 0 ;
Б
ц
x1 ? x2 = x1 + x2 ? 32 > 0 ;
Б
ц
гx1 = ?x1 + 21 > 0 ;
?????? ??????? ???????????? ???
(
1, x1 = x2 ;
x 1 ? x2 =
0, x1 6= x2 ;
????????????? ?????????? ??????????? ????? ???????? ? ????? ??????? x1 ? x2 ,
????????? ????????? ????? ? ?????? ???? ??????? ??????? ???????????.
???????? ??? ???? ??????? ???? ????????.
?????? ???? ? ????????? ?????? ?????????, ??????? ?? ???? ??????? ?????????? ?????????????? ???????? ?????????. ? ?????????, ???? ????????? ???????????? ???????????? ???????????? ???????? ?????????, ?? ?????? ????? ???????
??? ?? ????????, ? ?????????????? ??????????? ???????????. ? ?????? ???????????? ??? ?????????? ???????? ?????? ???? ???? x1 x2 , ????? ? ???????????
???????????? ????????? ????? ? ?????? ????????? ??????? ???????????:
Б
ц
x1 ? x2 = x1 + x2 ? 2x1 x2 ? 21 > 0 .
? 10 ?
????? ??????????? ???????????? ????????? ???????? ????????????. ????????
??????????? ? ???, ??? ?????? ?????? ?????????? ?????????????? ???????? ????????????? ???????, ??????? ??? ?????? ?????? ?? ??? ??? ???????? ??????????.
?????? ???? ? ????????? ?????????? ?? ?????????? ????????. ????????,
??????????? ??? ????? ???????????, ????? ?????? ?-??????? ? ???-???????
?? ???? ??? ?????? ???-???????, ??? 5:
ц
Б
x1 ? x2 = (x1 ? x2 ) ? (x1 ? x2 ) ? 12 > 0 .
?????? ???? ?????????? ????? ?????. ????? ????, ?? ???????? ? ?????????? ????????? ????? ?? ????????? ?????????? ????????? ????????, ???????????? ???????????? ????????? ????.
???????????? ????????? ????. ?????????? ?????????? ????????, ?????????????? ?? ???. 6. ???????? ???? n ????????? ???????????? ???????? ?? ???? ???? H ???????? ??????? ????. ????? ?? ???????? ???????? ???????? ?? ???? ???? M ????????
?????????? ????. ? ?????? ?????? ???? ???? ???????? ???????? ? ????? ???? ?????????? ???????????.1 ? ????? ?????? ???? ????? ????????? ???????????? ?????
?????. ??? ????, ?? ??????????? ??????????, ?????????? ???????? (hidden layers).
?????????? ???????? ???????? ???? ????? ?????????????? ? ??????? ???????? ????????????, ?? ????? ??????, ?????? ????? ?????. ?????????? ???????????
?????????? ?????????? ????????? ?????, ? ??????? ?????????? ????????????? ?????????? ???????????. ?? ???? ?? ???????? ???? ???????????? ??????????? ??????????, ??????????? ?? ??????? ???????????????? ???????????.
?????????????? ??????????? ????????? ?????. ????????? ??????: ????? ??
??????? ????? ??????????? (???? ?? ???????????) ? ??????? ????????? ?????
????????? ????? ????????? ???????? ?? ???? ?????? ?????????????.
1. ????? ?????? ??????? ??????????? ? ???? ??????????? ????. ??? ??????????? ????????? ????????? ?????????????? ??????? ?, ???, ?? ? ??????????????
???????????? ??????? ??????? ? ???? ????????????? ?????????? ????? [4].
2. ?? ??????? ?????????????? ??????????? ????????, ??? ??????????? ????
? ?????????? ????????? ????????? ????????? ???????? ???????????? ????????
???????????? ? n-?????? ???????????? ?????????. ??????????? ???? ????????? ????????? ????? ???????? ???????? ?????????? ?????????????????? ??????? ???????? ??????????????, ?????????????, ???????????????? ????? ??????? ? ??????????? ????????, ??????? ?????????????, ? ????? ???????????????? ????? ??????????? ???????.
3. ???????? ??????? ??????????? ? ???, ??? ????? ??????????? ??????? n ?????????? ??????????? ? ???? ???????????? ??????????? ??????? ?????? ?????????
? ???????????? [2].
1
?????????? ????????????????? ???????? ? ????????? ????? ?????. ?????? ????? ???? (??????,
????? ?? ????????) ???????? ???????????, ?????? ????? x0 , x1 , . . . , xn ??????, Ф?????????????????╗ ?????. ?? ????, ? ???? ?????? ???? ?????? ????, ????????? ?? ??????????? ????????.
? 11 ?
??????? 1.2. (??????????, 1957) ????? ??????????? ??????? n ?????????? ??
????????? ???? [0, 1]n ??????????? ? ????
1
2
n
f (x , x , . . . , x ) =
2n+1
X
k=1
hk
хX
n
i=1
Х
?ik (x ) ,
i
??? hk , ?ik ? ??????????? ??????? ????? ??????????, ?????? ?ik ?? ??????? ?? ?????? f .
???????? ??????, ??? ?????????? ????? ????????? ????? ????????? ?????????
???? ? ????? ??????? ?????. ????? ???????, ???? ????? ??? ??????????, ????? ????????? ???????????? ??????????? ???????, ? ?? ???????????, ? ?????. ? ?????????, ????????????? ??????????? ?? ???????? ????????????: ??????? hk ????????,
??????? ?? f , ? ? ????? ?????? ?? ???????? ?????????????????.
4. ???????? ???????????? ??????? ???????????? ? ???, ??? ????? ??????????? ??????? n ?????????? ????? ?????????? ?????????? ????????? ? ????? ???????? ????????. ????? ????? ??????? ?????? ??????????, ??? ????? ???????????
??????? ?? ???????????? ???????? X ????? ?????????? ?? ?????? ???????????
?? ???????? ??????????, ?? ? ??????????? ?? ?????? ????????? ?????? ??????? F ,
??????????? ????? [12].
???. 1.1. ????? ??????? F ?????????? ??????????? ????? ????????? X, ????
??? ????? ????????? x, x? ? X ?????????? ??????? f ? F ?????, ??? f (x) 6= f (x? ).
??????? 1.3. (?????, 1948) ????? X ? ?????????? ????????????, C(X) ? ??????? ??????????? ?? X ???????????? ???????, F ? ?????? ? C(X), ??????????
????????? (1 ? F ) ? ??????????? ????? ????????? X. ????? F ?????? ? C(X).
?? ????? ???? ??????????? ??? ????? ????? ???????????. ???????????, ??????
??????????? (???????????? ???????? ???????? ? ?????????) ????? ????????????
?????????????? ???????? ? ?????-?????? (??????????? ????????????) ???????????
?????????? ??????? ?????? ????????? [3]. ???? ????????? ????? ?????? ????????? ? ????????? ?????, ????????? ??? ???????? ?? ???????? ????????, ?????????
? ?????????? ??????? ?????????.
???. 1.2. ????? ??????? F ? C(X) ?????????? ????????? ???????????? ??????? ? : R ? R, ???? ??? ?????? f ? F ????????? ?(f ) ? F .
??????? 1.4. (??????? ? ??., 1998) ????? X ? ?????????? ????????????, C(X) ?
??????? ??????????? ?? X ???????????? ???????, F ? ???????? ???????????????
? C(X), ????????? ???????????? ?????????? ??????????? ??????? ?, ??????????
????????? (1 ? F ) ? ??????????? ????? ????????? X. ????? F ?????? ? C(X).
??? ???????????????? ??? ??????????? ?? ????????????? ?????????????????
???????????? ???????????? ????????????: ? ??????? ???????? ???????? ? ????????????? ??????????? ???????? ? ????? ???????? ??????????, ??????????? ?????
??????????? ??????? ? ????? ???????? ?????????.
? 12 ?
??????? ????,
n ?????????
z
}|
{
??????? ????,
H ????????
z
GFED
@ABC
/
x1 ERERRw11
ll5<
l
EEw1h RR
l
l y
RR
lll y
. . . w1HEE llRlRlRlRlRlR yyyy
RyRyR
lElE
wj1 l EE
yy RRRR)
l
y
E
l
l
Ey
@ABC
GFED
/
xj RRR wjh yyyEyEEE
5
EEllllll A
wjH RRyy
yRR
llE
. . . wn1yyy lRlRlRlRlRlR EEEE
RRR EE
y
ll
RRR "
yy ll
R)
ylyllwnh
n
@ABC
GFED
/
x
wnH
w01
w0h
@ABC
GFED
?1
w0H
:
F
X
...
X
...
X
}|
{
?1 ERRR w11
z
/
ll5<
EEw1m R
l
l
E
RRR
ll y
RR llll yyy
w1ME
EElllllRlRRRRRyyy
yR
lE
wh1l EEE yyy RRRR
)
lllw
EEyy
/
?h RRR hm yyy EE
EE llll5
whM RRyy
l
A
llEElE
yyRR
yy lRlRlRlRlRlR EEE
wH1
RRR EE
yy llll
RRR "
yllylwHm
R)
/
?H wHM
:
w01
w0m
@ABC
GFED
?1
???????? ????,
M ????????
F
X
...
X
...
X
}|
{
?1
/ a1
?m
/ am
?M
/ aM
w0M
???. 6. ???????????? ???? ? ????? ??????? ?????.
?????? ??????? ?????? ?? ??????? ? ?????????? ????? ????????? ???? (???????
??????????? ????????????) ? ? ?????????? ????????, ??????????? ??? ????????????? ???????????? ???????. ????????? ????????? ????? ????? ?????????? ????????? ? ????????? ?????.
5.
TODO: ??????? ?? ????? ?????? [5].
????? ???????, ????????? ???? ???????? ?????????????? ????????????????
???????. ??????????? ???? ?????????? ? ??????????? ????? ????? ? ????? ???????? ? ???. ????-???? ?????, ??? ???????, ?????????? ??? ??????? ????????????
??????????? ???????????? ????? ?????????????, ????????? ? ???????????????.
1.2
???????????? ????????? ????
???????????? ???? ????? ????? ??????????? ???????????? ????????,
???????? ?? ???????? ?????????? ??????? ?????????????. ???????? ?????? ??????????? ?????? ?????????? ?????????, ??? ??????? ?????? ??????????? ??? ??????????? ?? ????? ????????, ???? ???????? ???????, ??? ??? ??????? ??????????
???? ?? ????? ???????.
?? ?????? ??????, ?????????? ????????, ??????????? ??? ?????????? ?????????, ?????? ???? ?? ???????? ??????????????? ????? ??????? ?????????????.
?????? ????? ??????? ???????? ????? ?????????????? ????????????????? ???????????? ? ??????????? ???? ??????????? ????????????? ???????. ?????? ?????
??????? ???????? ????????? ??????????????? ?????? (error back-propagation) [11].
1.2.1
????? ????????? ??????????????? ??????
?????????? ???????????? ????, ? ??????? ?????? ?????? ??????????? ????
?????? ?? ????? ????????? ???????????? ????, ???. 6. ??? ??????? ???????? ??????? X = Rn , Y = RM .
ToDo3
? 13 ?
?????? ????????? ???????????. ????? ???????? ???? ??????? ?? M ???????? ? ????????? ????????? ?m ? ???????? am , m = 1, . . . , M . ????? ??? ?????????
??????? ???? ?? H ???????? ? ????????? ????????? ?h ? ???????? uh , h = 1, . . . , H.
???? ????????????? ?????? ????? h-? ???????? ???????? ???? ? m-? ???????? ????????? ???? ????? ?????????? ????? whm . ????? ???? ????? ????? ?????????? ????
????????????????? ????, ???? ??? ???? ??????? ???? ? ???????? v j , j = 1, . . . , J
? ?????????????? ?????? wjh . ? ????? ?????? ????? ????? ????? ???? ????????????. ???? ???? ???????????, ?? J = n ? v j ? xj . ????????? ????? w ?????? ????
????????????? ????? ????.
???????? ???????? ???? ?? ??????? xi ??????????? ??? ????????????:
хX
Х
хX
Х
H
J
m
h
h
j
a (xi ) = ?m
whm u (xi ) ;
u (xi ) = ?h
wjh v (xi ) .
(1.5)
j=0
h=0
??????? ?????????? ?????????????????? ?????? ??? ?????????? ??????? xi :
Q(w) =
M
б2
1 XА m
a (xi ) ? yim .
2 m=1
(1.6)
? ?????????? ??? ??????????? ??????? ??????????? Q ?? ??????? ????????.
??????? ?? ??????? ??? ????????? ????:
?Q(w)
= am (xi ) ? yim = ?m .
m
?a
???????????, ??? ??????? ??????????? ????? ???????? ?????? ?m ?? ??????? xi .
?????? ??????? ??????? ??????????? ?? ??????? ???????? ????:
M
M
X
б ?
?Q(w) X А m
m
?
=
a
(x
)
?
y
?
w
=
?m ?m
whm = ?h .
i
i
m hm
?uh
m=1
m=1
??? ????????, ?? ???????? ? ?m , ????? ???????? ??????? ???? ?? ??????? ????
? ?????????? ????? ?h .
?
????? ?m
?????????? ??????????? ??????? ?????????, ??????????? ???
??? ?? ???????? ?????????, ??? ? ? (1.5). ???? ???????????? ?????????? ???????
?????????, ?? ??? ???????????? ?????????? ??????????? ????? ???????????????
?
???????? ?m
= ?m (1 ? ?m ).
???????, ??? ?h ??????????? ?? ?m , ???? ????????? ???? Ф????? ???????╗, ???
????? ?? ?????? ???????? ???????? ???? ???????? ?m ?m
? ???? ?? ?????? whm ,
? ????????? ?h ????????? ?? ?????:
h
? o
X tjjjjwh1
jTTTT
?1 ?1?
jjj
whM TTT
...
?
?M ?M
???? ????? ??????, ??? ???, ?? ????????? ??????? ??????????? ???????????
??????????:
H
?Q(w) X h ?
=
? ?h wjh = ?j .
?v j
h=1
? 14 ?
???????? 1.2. ???????? ??????????? ???? ??????? ????????? ???????????????
??????
????:
(xi , yi )?i=1 ? ????????? ???????, xi ? Rn , yi ? RM ;
H ? ????? ???????? ? ??????? ????;
? ? ???? ????????;
?????:
????????????? ???? wjh , whm ;
1: ????????????????
????
А
б ?????????? ?????????? ??????????:
2:
3:
4:
5:
6:
7:
8:
1
1
wjh := random А? 2n
;б
, 2n
1
1
whm := random ? 2H , 2H ;
?????????
??????? ?????? xi ????????? ???????;
?????? ??? ? ?????????:
uh (xi ), ?h? ??? ???? h = 1, . . . , H;
?
am (xi ),q?m
, ?m ??? ???? m = 1, . . . , M ;
PM
m 2
Qi :=
m=1 (? ) ;
????????
? ?????????:
PM ???
h
m ?
? := m=1 ? ?m whm ??? ???? h = 1, . . . , H;
??????????? ???:
? h
whm := whm ? ??m ?m
u , ??? ???? h = 0, . . . , H, m = 1, . . . , M ;
h ? j
wjh := wjh ? ?? ?h x , ??? ???? j = 0, . . . , n, h = 1, . . . , H;
Q := ??1
Q + 1? Qi ;
?
???? Q ?? ???????????????;
???? ??????? ??????????? ?? am ? uh , ????? ???????? ???????? Q ?? ?????:
?Q(w) ?am
?Q(w)
? h
=
= ?m ?m
u ,
m = 1, . . . , M, h = 0, . . . , H;
(1.7)
?whm
?am ?whm
?Q(w) ?uh
?Q(w)
=
= ?h ?h? v j ,
h = 1, . . . , H, j = 0, . . . , J;
(1.8)
?wjh
?uh ?wjh
? ??? ????? ??? ??????? ????.
?????? ?? ???????? ???? ???????????, ????? ????????? ???????? ????????
????????? ???????????????, ??. ???????? 1.2.
??????????? ?????? ????????? ???????????????.
? ?????????? ??????? ?????????????. ?????? ???, ???????? ??? ? ??????????
????????? ??????? ??????? O(Hn + HM ) ????????.
? ????? ?????? ?????? ???????? ?????????? ?????? ? ??????? ? ??? ????????.
??????? back-propagation ????? ??????????? ?? ?????????????? ???????????
? ???????????? ????????????.
? ??????? ??????? ????????. ???????? ????? ???????? ??? ????????????? ?????
?????, ???????????? ??????????? ??????? ? ???????????? ??????? ????????? (????????, ????????? ? ?????? ????????). ????? ????, back-propagation
? 15 ?
?? ??????????? ??????? ??????????? ?? ???????????? ????? ???????????.
??? ????? ????????? ?????? ? ?????? ???????????? ????????: ??????????
??????, ??????????? ??????????, ? ???????.
?????????? ?????? ????????? ???????????????.
? ????? ?? ?????? ????????. ??? ????????? ?????????? ?????????? ?????????
??????? ?????????? ????????? ????????????? ?????????.
? ??????? ???????????? ?????? ??????? ?????????? ? ?????????????? ?????????
????????? ??????????? Q.
? ?????????? ??????? ??????????? ????? ???????? ???????? ???? H. ? ?? ?? ?????, ??? ????????? ???????? ????????? ????, ?? ???????? ????? ???????????
???????? ???????? ???????? ? ???????? ??????????.
? ??? ?????????? ?????????? ????????? ???? ??????? ? ????????????.
? ???? ??????????? ??????? ????????? ? ??????????????? ???????????, ????
?????????? ??? th, ?? ???? ????? ???????? ? ????????? Ф????????╗. ??? ?????? ???????? ????????????? ????? ?? ????? ???????, ??? ????? ???????? ??????????? ? ? ? ????, ??? ?????? ????????? ????????????? ????? ? ????????????
? ????????? (1.7)?(1.8). ???? ?????? ???? ??? ???????? ? ????? Ф???????
????╗, ?? ? ???? ??????????? ?? ???????? ?????? ?? ??? ?????????. ?????????????? ????? ????????? ?????, ???????, ??? ??? ???? ? ?????.
1.2.2
????????? ?????????? ? ???????? ???????????? ????????
? ???? ??????? ??????????????? ????????????? ??????, ??????????? ? ??????? ??? ??????? ??????? ?????????? ?????????? ?????? ????????? ???????????????. ????????? ????????? ????????? ?????, ??? ?????? ?????? ????????? ????????? ???? ?? ????? ????????? ??????????, ??. ????? [7].
???????????? ??????. ??????? ????????? ???? ???????????? ? ????????? ? ????????? ????????? ?????????. ? ?????? ??????? ???????? ???? ????? ????????? ??????????????. ??????? ????? ????????? ??? ??????????? ???????? ???????? ??????????????? ???????????? ?????????:
xj ? xjmin
x := j
,
xmax ? xjmin
j
j
???? x :=
xj ? xj??
xj???
,
j = 1, . . . , n,
??? xjmin , xjmax , xj?? , xj??? ? ?????????????? ???????????, ????????????, ??????? ???????? ? ?????????????????? ?????????? ???????? xj .
????? ??????? ?????????. ?????????? ??????? ?(z) = (1 + e?z )?1 ????? ??????????? ??? ??????? ????? ?????????????. ?? ???????????? ? ??????????? ???????
??????????? ?????????????? ??????? ?????? ?? ??????? (1.4), ????????????? ?????????? ???????????, ?????????????? ????????? ????????. ?????????? ????????
? 16 ?
???????, ????? ??? th(z) = 2?(2z) ? 1, ??????????? ???????? ?????????? ????????
? ??????? ????.
??? ?????????????? ??????? ???????? ????? ????? ????????? ????????? ???????? ????: th z?+ ?z. ????? ???????????? ? ?????? ???????? ???????? ???????,
???????? ln(z + z 2 + 1).
??? ???? ??????? ????????? ??????? ? ??????????? ??????????? ?????????????????? ??????? (1.6) ? ??????? ?????????????. ???? ???????? ????? ???????
{?1, +1} ????????? ?? ?????????? ?????????????? ???????? ??????? ?????????
????????? ????, ?? ??????????????? ??????? ????? ?????????? ? ???????????????
?????????? ????????? ??????? ?????????, ?????????????, ? ???????? ?????????
???????. ????? ???????, ???????? ????? ??????? ?????? ?????????? ?????? ??????? ???????? ??????? ?????????. ? ?????? [7] ????????????? ???????????? ???????
????????? 1.7159 th( 23 z), ? ??????? ? ?????? {?1, +1} ??????????? ???????? ??????
???????????.
????? ?????????? ???????????. ?? ??? ?? ??????????? ?????????????? ???????? ????????????? ???? ?????? ?????????????????? ?????????? ?? ?????? ??????????. ? ?????????
Б 1 1 ц 1.2 ?? ???? 1 ???? ???????????????? ?????????? ??????????
?? ??????? ? 2k
, 2k , ??? k ? ????? ???????? ? ??? ????, ?? ???????? ??????? ??????
??????. ? ???? ?????? (? ??? ???????, ??? ??? ???????? ?????????????) ????????
????????? ???????????? ?????????????? ???????? ? Ф??????? ????╗ ??????? ?????????, ?????????????? ?? ???. 2.
??????? ???????????? ????????. ????? ??????????? ???????????? ???????????? ????? ??????????????? ????????? (?. ?. ??????????? ??????? ? ????????? ???????), ??????? ??? ????????? ???????????.
1. ?????????? ???????? ????? ????????? ??? ???? ???????, ??????? ???????? ????? ?? ???????, ????????????? ?? ????. ? ????? ?????? ???????? ??????
???????, ????? ?? ???????? ??????????? ???????????? ?? ?????? ???? ????????.
??????? ??? ?????????? ????????? ??????????? ? ???, ????? ??????????? ??????????? ??????? ?? ?????? ???????, ????????? ??????? ?????? ?????? ? ??????? ???????????? ???????? ?????? ??????????. ??? ??????? ?????????? ????????????
???????? (shu?ing).
2. ??? ???? ????????? ??????? ? ???, ????? ???? ??????????? ?? ???????,
?? ??????? ???? ???????? ??????. ??? ????? ??????????? ????????? ??????? ??????? ??????????? ? ???????????? ? ????????? ?????? ???? ?? ?????? ???????. ????
????? ????????????? ????????? ?????? ? ??? ???????, ????? ???????? ?????? ?? ???????? ????????, ????? ??????? ???????? ????? ??????????????? ?? ??????? ????????, ??????? ?????? ????????? ?? ????????? ?? ????????? ???????.
????????????? ??? ?????????? ?????. ???? ????? ???????? ??????? ???????
????????????? ??????????? ???????????? ????? ?? ?. ?. ????????. ?? ??????????
???????????????? ????????????? ???????? ???? ? ????????????? ?????????????
??????? ???????????????????? ? ????????? ?????????????? ?????, ????????????
???? ???????? ???????. ??????????? ????? ??????????? ? ???????? ??????????????? ??????? ? ? ???????? ?????????.
? 17 ?
????????, ??? ??? ???????? ???? ?????????????? ?????????? Q(w). ???? ??????????? ? ???, ????? ?????????? ????????? ???? ?????????? ???????? ?????,
??????? ? ?????????? ??????????? ???????? ?????????:
?
Q? (w) = Q(w) + kwk2 .
2
????????? ??????????? ???????? ? ????????? ?????????? ???????? ? ?????????:
?Q? (w)
?Q(w)
=
+ ?w.
?w
?w
??? ???? ??????? ?????????? ????? ????????? ???
w := w(1 ? ??) ? ?
?Q(w)
.
?w
???????????? ??????????? ??????????? ? ????????? ???????????????? ?????????
(1 ? ??), ??? ???????? ? ??????????? ?????????? ?????. ?????? ???????? ?????? ?
?????????? ????? (weights decay).
???????????? ??????? ?????? ? ???, ??? ?? ????? ?????? ??????????? ? ?????????? ? ?????? ????????????? ? ?????? ???????????? ???????? ???????????.
?????????? ????? ?????????? ? ??? ???????, ????? ????? ???????? ????????? ??????? ??????? ????????? ??? ?????? ???????????????.
?????????? ?????? ?????????? ????? ? ????????? ??????????????? ???????????? ????????? ?, ??????? ?????????? ????????? ????????????????.
?????????? ????? ??????.
TODO: optimal brain damage
????? ????? ?????. ???? ? ?????????? ?????? ???????? ? ???????? ????????????
??????? ???????? ?????????????, ?? ????? ???????????? ??????????? ?????. ??????????? ???? ????????? ???????????? ?????????? ?????????? ???????, ? ? ??????????? ??????? ????? ???????. ???????????? ?????? ????? ????? ????????????
??? ????????????? ??????? ???????????? ????????. ??? ?????? ?????, ??? ????
???????? ??????????? ??????, ? ??? ??????? ??????? ????.
????? ????? ???????? ? ??????? ???? H ?????????? ?????????? ?????????,
?? ?? ???? ?? ??? ?? ???????? ??????.
1. ?????????? ??????. ???? ??????? ??????? (??? ?????? ?????????) ??????? ????????, ??????, ???? ????????????, ? ?????????? ??????????? ????? ????????
? ??????? ????. ???? ??????? ??????? (??? ?????? ?????????) ?????????? ???????
?????? ?????????, ?? ???????? ??????? ??????????? ??????? ???????, ???? ????
????????? ??????? ?? ?????? ????????, ?? ???? ?????????????, ? ??????? ????
??????? ?????????. ?????????? ????? ??????? ? ???, ??? ?? ???????? ?????? ??? ?????
? ?????? ???????????? ???????????? (????????? ?????? ?????????).
2. ??????????? H ?? ???????? ????????. ? ?????????, ????? ??????????????
???????? ??????????? ???????? ??? ??????? ?????? ?? ??????????? ???????????
ToDo4
? 18 ?
??????? Q(X k ). ??????????? ??????? ????????? ?? ????????? ?????????, ????? ???????? H, ?????? ????? ??????????? ???????. ?????????? ????? ??????? ? ???, ???
?????????? ????? ??? ?????? ??????? ???? ??? ????????? ????????? ????????? H.
3. ???????????? ?????????? ????????. ??????? ???? ????????? ??? ????????
????????????? ???????? ???????? ???? H ? ?. ???????? ?????????? ?? ??? ???,
???? ?????? ?? ?????????? ???????. ????? ??????????? ????? ??????. ???? ?????
?????? ???????????????? ?????????? ?????????? ???????, ? ???????? ??????????? ?????. ????? ??????? ?????????? ?????? ??????? ????? ??????????, ????? ??????
???????? ? ???????? ????????. ?????????, ??? ????? ????? ???????? ?????? ??????????? ???? ? 1.5 ???? ??????, ??? ???? ?? ? ???? ????? ???? ?????? ??????????
????????. ??? ????????, ??? ??????????, ??????????? ? ????, ?? ???????? ?????????
??? ?????????? ??????? ?? ?????????? ???????????.
??? ??????????? ??????????? ???? ????????????? ????????? ?? ?????????
??????-?????? ???????? ????????. ??????????? ???????? Q(X k ) ????? ??????? ???????? ???????? ????????? ????????, ??? ??? ??????????????? ? ??????????????
???? ? ????????? ??????? ???????????????.
????? ???????? ????.
1. ????????, ??? ??????????? ?????? ???????? ??? ???????????? ????????,
???? ???????? ????P? ?????????P? ?????? ???????? t. ??????, ?????????? ????????
2
?????? ??? ?t ? 0, ?
t=1 ?t = ?,
t=1 ?t < ?, ? ????????? ????? ???????? ?t = 1/t.
??? ????????? ????????? ????? ?????????????? ??????? ?????????? ????? ?? ???????????, ??????? ????????? ???????????? ?????????? ???? ??????? ????????????
?????? ??? ????????????? ????????????.
2. ????? ?????????? ???????????? ?????? ???????? ? ??????
???????????
??А
б
?? ? ?????? ?? ??????? ?????????? ?????? ??????????? Q w ? ? ?Q
?
min
.
???w
?
????? ?????? ?????? ??? ?????? ????????? ??????????????? ?????? ???????? ??????????????? ? [1].
3. ? ????????? ??????????? ??????? ??????????? ???????? ???? ??????????? ????????????, ????????, ????????????? ??? ??????? ???????? ????????????
(??. ????).
????????? ???? ?? ????????? ????????? ??????????? ?????? ???? ????????????? ? ????? ???? ???????-?????? ????????? ?????????? back-propagation. ????
?? ?????????? ???????? ??????????? ? ???, ????? ??? ?????? ???????????? ??????????? ?????? ??????????? ????????? ??????????? ??????? ????? ? ????????
??????? ??????????? ???????? ???????? ? ????????? ??????? ???????????? ?????? ??
????? ?????. ???? ?????? ???????? ????????????? ????????????? (jog of weights).
?? ???? ????, ?? ???????? ????????? ???????????? ?????? ? ?????????? ??????????
?????? (stochastic local search).
????? ???????? ????????. ? ????????? 1.2 ? ???????? ???????? ???????? ???????????? ??????? ???????????? ?????????????????? ?????? Q. ?????? ?????????? ???? ???????? ??????????? ?? ?????????? ????? ???? ??? ????????? ???????
????? ?????? ????????. ??????????, ??? ??????????? ?? ??????????? ?????????????. ?????? ????? ?????????? Q ??????????? ???????????, ??? ????????????????
? 19 ?
?????????? ??????? ?????? Qi , ?????????? ?? ???????? xi , ??? ???? ??????? ???
???????? ???????, ????????????? ?????????? (??? 7).
?????? ???????. ??????? ???????? ??????????? ????? ????? ???????? ? ????????????. ??? ???????, ??????? ????? ?????????? ??????? ??????????? Q ?????
??????????????, ??? ????? ??????? ? ?????????? ????????? ???????. ??? ?????????????? ????????? ? ????? Ф?????????╗ ??????????? ??????? ??????? ????????
(early stopping). ?? ???? ???????? ??????????? ?????-?????? ??????? ????????,
? ???? ?? ???????? ??????????, ??????? ????????? ????????????.
????? ???????????? ?????? ???????????. ? ?????????, ??????????? ??????
??????? ??????? ???????? ???????? ????????, ? ?????? ????? ??????????? ?? ????????. ???????????? ?????? ??????? ??????? ????? ???????????, ?? ?? ?????? ??????? ? ??? ??????? ?????????? ??????? ?????? ??????????? ??????????? Q(w),
??????? ??????? ??????? ??????. ????? ??????????? ?????????? ????? ?? ???????, ?????? ? ??? ??????????? ?????? ?????????? ????????, ??? ???????????? ?????????? ??????????????? ?????????. ????? ???????, ?????????? ??????????? ??????????????? ?????? ??? ????????? ????????? ????? ??????? ????????????? ??????????????????. ? ?????? [7] ?????????? ????????? ????????????.
1. ???? ????????? ??????? ????? ??????? ????? (??????? ?????????? ?????
???????? ? ?????), ??? ???? ???????? ?????? ?????????????, ?? ????? ????????????
????? ??????????????? ????????? ? ?????????? ?????.
2. ???????????? ????? ??????????-?????????? ???????? ? ????????? ??? ???????. ? ???? ?????? ???????? ???? ??????????? ????????????? ??? ??????? ????????
????????????, ??? ???? ???????????? ?????? ???? ???????????? ??????? ???????
?????? ???????????:
?
?jh = ? 2 Q
+ х,
?w2
jh
??? ? ???????? ?????????? ?????????? ????? ????????, х ? ????? ????????, ??????????????? ????????? ???????????, ?, ??????????????, ?????????????? ??????????
????. ????????? ?/х ???? ???? ???????? ?? ?????? ???????? ??????????? Q(w),
??? ?????? ??????????? ?????????? ? ????. ???????????? ??????? ??????? ??????
??????????? ??????????? ? ??????? ???????????? ???????? back-propagation.
3. ???? ????????? ??????? ????? ????????? ?????, ??? ???? ???????? ??????
?????????, ?? ????? ???????????? ?????????????? ???????? ?????? ???????????
??????????. ????????? ??????????? ? ???, ??? ??????? ????????????? ?? ?? ??????, ? ???????? (batch learning). ??? ??????? ?????? ?????????????? ??????????
???????? ?????????????, ??? ????????? ????????? ????? ??????????? ??????????.
1.2.3
????????????? ?????? ????????
TODO: ???????? ?? ?????? (bagging). ????????????????? ????? ??? ???????? ToDo5
?????? (simulated annealing). ?????????????? ??????.
???????? ??????????? ???????? ?????????????? ????????????? ??????????
?????????? ???????. ????????, ??? ?????? ????????? ?????????? ??????????? ????? ???????????? ???????? ?? ??????, ????? ????????? back-propagation ??? ?????
? 20 ?
?????? ?????????? ?????, ? ??? ????????? ?? ????????? ????????? ????????? ?????????????? ??????.
1.3
???? ????????
?? ??? ??? ?? ????????????? ????????? ????, ??????????????? ??? ????????
? ????????, ????? ??? ??????? ??????? xi ????? ??????????????? ??? ????? yi . ????
???????? ????????? ?????? ?????? ???????? ??? ???????, ????? ???????? ??????
???? ??????? xi , ? ????????? ???????? ???????????? Ф??????? ???????╗ ???????? ?
????????, ? ????????? ???????? ????? ??????? ? ???? ?????????.
????????????? ???????????? ?? ?????????????, ??? ? ???????????? X ???????
??????? ? : X О X ? R, ??????????? ????????? ??????? ??????? ???????? ?????
???? ????????.
1.3.1
?????? ????????????? ????????
????? X = Rn ? ???????????? ????????, Y = {1, . . . , M } ? ????????? ?????????, ????? M ???????????. ?????? ????????? ??????? ???????? X ? = {xi }?i=1 .
????????? ?????????? ??????? ????????? ???????? ? ????????? a : X ? Y .
??????? ??????? ??????????? WTA. ???????? ????????? ?????? ???????????
? ???, ????? ?????? ??????? wm , m = 1, . . . , M , ??????????? ?????? ?????????,
? ???????? ????? ?????? x ? ?????????? ????????:
a(x) = arg min ?(x, wm ).
m?Y
(1.9)
??????? ??????, ???????? ??????????? ?? ????? ???????????? ? ???? ????????? ??????. ????????? ??????? ??????????? ???????????, ? Ф???????? ???╗, ??????? ??????
??????? ???????? WTA (winner takes all).
??? ???????????? ?????? ??????? ????? ?????????????? ?????????? ???????? ?????????????, ?????? ???????? ???????? ?????????? ????? ????????? ? ???????? ?????????:
?
1X 2
Q(w1 , . . . , wM ) =
? (xi , wa(xi ) ) ? min .
2 i=1
????????, ??? ??????? ?????????: ?(x, w) = kx?wk. ????? ????? ???????? ????????
??????????? Q ?? ??????? wm :
?
X
Б
ц
?Q
=
(wm ? xi ) a(xi ) = m .
?wm
i=1
???? ??? ?????? ??????? ????????? ????????? ????? ??????????????? ?????????,
?? ??????? ?????????? ????? ??? ???????????? ?????????? ??????? xi ????? ????????? ????????? ???????:
(
wm + ?(xi ? wm ), ???? a(xi ) = m;
(1.10)
wm :=
wm ,
???? a(xi ) 6= m;
? 21 ?
GFED
@ABC
x1 ?? w11 / ?(x, w1 )
?
LLL
?
──
LLL
1
wM
&
?? ───
arg
?─?─
иии
и
и
и
── ???
min
8
─
??
rr
wn
?┬
rrr
─1
r
─
─
n
@ABC
GFED
/ ?(x, wM )
x n wM
GFED
@ABC
x1 :
::
/ a(x)
???. 7. ????????????? ????????? ????????????? (1.9) ? ???? ??????????? ????????? ????.
w11
/
X
A
ЦЦ
Ц
: Ц
и и и ЦЦ:Ц:Ц: и и и
Ц ::
w1n
:└
Ц
X
ЦЦ
n
n
@ABC
GFED
/
w
x
M
1
wM
:
FF
FF
#
arg
max
;
xx
xx
/ a(x)
???. 8. ??????????? ???? ? ???????????? ?????????.
??? ? ? ??????????? ???, ?? ?? ???? ????????. ????? ??????? ??????? ? ???, ???
???? ?????? xi ????????? ? ???????? m, ?? ????? ??????? ???????? ??????? ??????????
? ??????????? ??????? xi , ????????? ?????? ?? ??????????.
?????????? ???????? ??????? (1.10) ? ????????????? ???????? ???????
?? ?????, ??? ????????????? ?????????????? ??????????, ??????????? ?????????
????. ????????? (1.9) ? ? ????? ???? ??????????? ? ???? ??????????? ????????????,
?????? ?????? ????????? ????????? ???????????? hx, wm i ??????????? ???????
?????????? ?(x, wm ), ? ?? ?????? ?????? ???????????? ??????????? ???????? ????????, ??. ???. 7. ??? ???? ?????? ????????? wm ??????? ?????????? ?????????????
???????? ???????? ???? (??????? ?????????? ????????? ????????) ? ?????? wm .
??????, ????? ???????? ?????????, ?????????? ????????-???????????.
????? ??????? ?????????, ? ??????? xi ? wm ???????????, ??????????? ?????????? ???????????? ???????????? ?????????? ????????????:
kx ? wm k2 = kxk2 + kwm k2 ? 2 hx, wm i = 2 ? 2 hx, wm i .
? ???? ?????? ????????? ???? ??????????? ????? ????????? ???, ? ??????????
?? ??????????? ???? ?????? ??????????? ????????? ?????? ???????????? ? ???????? ???????, ??. ???. 8.
????????????? ????????????? ????????? ????? ?? ????? ?????? ????????
? ??????????????? ? ?????????? ????? ? ???????????? ?????????.
??????? ???????????? ??????????? CWTA. ?????????? ????????????? ???????? ?? ??????? WTA ??????????? ? ???, ??? ??? ????????? ????????????? ?????
?????? ????? ??????? ? ????? ???????, ??? ?? ??????? ?? ?????? ???????????. ? ?????????? ???????? ??????????????? ?????? ???????.
??? ??????????? ????? ?????????? ???????? (1.9) ??????? ??????????????.
???????? Ф???????? ?????????╗ ??????????? ? ??????? CWTA (conscience WTA):
a(x) = arg min Cm ?(x, wm ),
m?Y
(1.11)
??? Cm ? ?????????? ????? m-?? ??????? ? ???? ????????. ????? ???????, ????????
?????????? ?? ??????? ?????? ????????????? ????????.
??????? ?????? ??????????? WTM. ?????? ??????????? ??????? WTA ???????? ????????? ???????? ??????????, ???????? ??? ????????????? ????????? ????????????? ??????? ???????? wm . ???????? ????????? ??????????? ? ???, ????? ?? ????????? ????????? ???????????? ??? ???????, ? ?? ?????? ???? ??????-??????????.
? 22 ?
??? ????? ???????? ????????????? ??????? ? ????????? ????????? ??????? ?????????? ?(?). ????????, ????? ????? ?(?) = exp(???2 ), ? > 0. ?????? ????????
??????? Ф?????????? ???????? ???╗ ???????? ????? ?????? ??????? Ф?????????? ???????? ??????╗ ? WTM (winner takes most):
А
б
wm := wm + ?(xi ? wm ) ? ?(xi , wm ) .
????? ???????, ?????? ???? ????????? ????????? ? ??????? ??????? xi , ?? ??????,
??????????? ?????? ?? xi , ????????? ??????.
?? ????????? ????????? ????? ????? ??????? ????????? ???????? ???????????? ?, ????? ??? ??????? ??????? ?????? ????????????? ????? ? ??????? ???????
????????. ????? ? ????? ???????????, ????? ??????????? ??? ????? ??????? ? ?????????? ???????? ? ????????? ?????? ?????? ???????-??????????.
????????? ??????????? ? ??????????? ??????? WTM ????? ??????????????
??????????. ???? ?? ????????? ? ?????????????????? ????? ????????.
1.3.2
?????????????????? ????? ????????
?????????????????? ????? ???????? (self-organizing maps, SOM) ??????????? ??? ???????????? ??????????? ??????. ??? ???? ?? ?????? ??????????????
??????????, ? ???? ????? ??????? ??????, ?????? ???????? ???????? ? ???????????? ??????????. ??? ?? ?????, ????? ???????? ?????? ???????. ?? ?????? ???????????? ??????? ??? ????????? ??????? ???????? ??????????? ?????????? ????????? ?????? ? ???????????? ??????? ????????? ??????.
???? ??????????? ? ???, ????? ????????????? ??? ??????? ??????? ?? ???????
?????, ? ????? ??????? ???????? ??????????????? ??????? ????? ?? ?????. ??? ?????
??????? ???? ???????? ???????? ?????????? ??????????????? ??????????. ??????
??? ????????????? ????? ??????? M О N , ? ?????? ???? ??????? ????????? ??????
? ???????? ????? wmn . ????????? ????????? Y ????????? ? ?????????? ????? ?????,
Y = {1, . . . , M } О {1, . . . , N }. ???????? ????????????? a(x) ?????? ???? ????????
(m, n) ? Y , ????????????, ? ????? ???? ????? ???????? ?????? x.
???????? ???????? ???????????? ??????? ??????????????? ?????????. ???????
??? ??????? xi ???????????? ??????-?????????? ???????? ??????? WTA. ????? ????
?????? ? ??? ????????? ?????? ?????????? ? ??????? ?????????? ??????? xi . ? ????
??????? ???????? ????? ? WTM, ?? ?????? ?????? ??????? ?(x, x? ) ?? ????????????
???????? ???????????? ????????? ??????? ?? ????????? ????? ????? Y :
А
б p
? (m, n), (m? , n? ) = (m ? m? )2 + (n ? n? )2 .
????? ???????, ??????? ???????? ????? ? SOM ????? ???
А
б
wmn := wmn + ?(xi ? wmn ) ? ?(a(xi ), (m, n)) ,
(1.12)
??? ?(?) ? ????????? ????????????? ???????, ????????, ?(?) = exp(???2 ). ???????? ? ?????? ??????? ???????????? ?????: ??? ?????? ?, ??? ????? ???????????
????????, ? ??? ????? ??????????? ????? ????????? ??????? ????????? ?? ?????. ????? ????? ??????????? ???????? ????????? ? ?? ???????? ? ????????, ?????
???? ???????? ??????? ????????? ?????????? ????????? Ф? ????? ??????╗, ? ?????
??????????????? ?? ???????.
? 23 ?
????????? ????????????? ???? ????????. ???? ????? ??????????? ????? ???????? (???????? a(x)) ?????????? ??? ??????? ????????? ??????? X ? , ?? ????????
????????? ???????????? ??????????? ? ??????? ????? ?? ?????. ??? ???? ???????
????? ? ?????-???????? ????? ???????????? ?????? ?? ??? ??????? ???????????????
?????????.
?????? ??? ?????? ????? ????? ????????? ??????? ?????????? ?? k ????????? ????? ???????, ? ?????????? ????????????? ?????????? ?????????? ? ????
??????????? ??????????? ?????. ?? ??? ?? ???????? ? ???? ????? ????????? ???????. ?? ????? ????? ?????? ?????, ??????? ????????? ????????, ? ? ????? ??????
????? ??? ?????????????.
TODO: ???????? ????????? ???????...
????????? ??? ? ????? ????????????? ?????????. ??? ????? ???????? ???
n ????, ?? ????? ????? ?? ?????? ???????. ?????? ???? ???? (m, n) ????????????? ???????? j-? ?????????? ??????? ????? wm,n . ?????? ??? ????? ????????????
? ????????????? ????? ?? ?????? ?? ???????????. ????? ??????? ????? ????????????? ?????????? ????????? j-?? ????????, ??????? ? ??????????. ????????? ?????
????????? ? ????? ?????? ?????????, ????? ????? ????????, ??????? ???????????
?????????? ??? ?????????? ???????? ????????? ?????????.
??? ???? ?????? ????????????? ? ????????? ?? ????? ???? ?????, ? ???????
???????? ????????? ???????????? ????????. ???? ??????? ??????????????? ? ????? ?????, ?????? ?? ????? ???? ? ????????? ??? ??? ??????. ?????? ?????????
???????????? ????????, ????? ????? ????????????? ????????? ??? ?? ?????.
?????????? ???? ????????.
? ??????????????. ?? ?????? ????, ????? ??????????? ????? ??????????? ?????????? ?????????? ??????, ? ????? ? ?????????? ????????????? ???????.
?? ?????? ????????? ? ??????????? ??????? ???????????? ?????? ?????????
? ??????? ??????????? ?????.
? ??????? ?????????. ??????? ??????? ????????? ???????????? ????? ?????????? ? ??????? ????? ?? ?????. ? ?????????, ?????????? ???????????? ???????? ????? ??????????? ?? ????????? [6]. ? ????????, ??????? ??????? ?????
???????? ????????? ?? ????? ?????, ????????, ???? ??? ???? ????????? ?????? ?? ???? ?????????. ????????? ????????? ??? ????????????? ????????????
???????????? ?? ?????????. ????????????? ????? ?? ????? ????????? ??????
???? ? ????????? ????????? ??????????? ??????, ? ?? ?? ??????.
? ??????????? ?? ?????????????. ????????? ????????????? ????? ???????????
?????? ?? ??????? ???????? ? ????? ??????????? ?? ?????? ?? ????????????
?????????, ?? ???? ?? ?? ??????????.
?? ??????, ??? ???????????? ???? ???????? ??????????? ? ???????????? ??????? ?? ???????????? ?????????????????? ? ????? ???????????? ??????? ????????????, ??????? ??? ?????????? ?? ???????????? ?????????????. ?? ???????? ???
??????????? ???? ??? ??????????????? ???????? ??? ???????????????? ??????????? ??????? ??????????? ??????.
ToDo6
? 24 ?
1.3.3
????????? ???? ?????????? ???????????????
???????-?????????? ?????????????.
??????? ?????????????. ??????????? ?????????? ???????? ???????.
?????? ??????????
[1] ??????? ?. ?. ????????? ????: ????????, ??????????? ? ??????????. ? ?.: ?????, 2001.
[2] ?????????? ?. ?. ? ????????????? ??????????? ??????? ?????????? ?????????? ? ???? ???????????? ??????????? ??????? ?????? ??????????? // ????.
?? ????. ? 1958. ? ?. 114, ? 5. ? ?. 953?956.
[3] ???????????????? / ?. ?. ???????, ?. ?. ?????-??????????, ?. ?. ??????,
?. ?. ??????, ?. ?. ??????????, ?. ?. ???????, ?. ?. ??????? ? ??. ? ???????????: ?????, 1998. ? ?. 296.
[4] ????????? ?. ?. ???????? ? ?????????? ??????????. ? ??????: ?????, 1986.
[5] Bishop C. M. Neural Networks for Pattern Recognition. ? Oxford University Press,
1995.
[6] Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. ?
Springer, 2001.
[7] LeCun Y., Bottou L., Orr G. B., Muller K.-R. E?cient BackProp // Neural
Networks: tricks of the trade. ? Springer, 1998.
[8] McCulloch W. S., Pitts W. A logical calculus of ideas immanent in nervous activity //
Bulletin of Mathematical Biophysics. ? 1943. ? no. 5. ? Pp. 115?133.
[9] Minsky M., Papert S. Perceptrons: an Introduction to Computational Geometry. ?
MIT Press, 1968.
[10] Noviko? A. B. J. On convergence proofs on perceptrons // Proceedings of the
Symposium on the Mathematical Theory of Automata. ? Vol. 12. ? Polytechnic
Institute of Brooklyn, 1962. ? Pp. 615?622.
[11] Rummelhart D. E., Hinton G. E., Williams R. J. Learning internal representations
by error propagation // Vol. 1 of Computational models of cognition and perception,
chap. 8. ? Cambridge, MA: MIT Press, 1986. ? Pp. 319?362.
[12] Stone M. N. The generalized weierstrass approximation theorem // Math. Mag. ?
1948. ? Vol. 21. ? Pp. 167?183, 237?254.
[13] Widrow B., Ho? M. E. Adaptive switching circuits // IRE WESCON Convention
Record. ? DUNNO, 1960. ? Pp. 96?104.
??? ?????????, ??????? ?? ???? ??????? ?????????? ?????????????? ???????? ?????????. ? ?????????, ???? ????????? ???????????? ???????????? ???????????? ???????? ?????????, ?? ?????? ????? ???????
??? ?? ????????, ? ?????????????? ??????????? ???????????. ? ?????? ???????????? ??? ?????????? ???????? ?????? ???? ???? x1 x2 , ????? ? ???????????
???????????? ????????? ????? ? ?????? ????????? ??????? ???????????:
Б
ц
x1 ? x2 = x1 + x2 ? 2x1 x2 ? 21 > 0 .
? 10 ?
????? ??????????? ???????????? ????????? ???????? ????????????. ????????
??????????? ? ???, ??? ?????? ?????? ?????????? ?????????????? ???????? ????????????? ???????, ??????? ??? ?????? ?????? ?? ??? ??? ???????? ??????????.
?????? ???? ? ????????? ?????????? ?? ?????????? ????????. ????????,
??????????? ??? ????? ???????????, ????? ?????? ?-??????? ? ???-???????
?? ???? ??? ?????? ???-???????, ??? 5:
ц
Б
x1 ? x2 = (x1 ? x2 ) ? (x1 ? x2 ) ? 12 > 0 .
?????? ???? ?????????? ????? ?????. ????? ????, ?? ???????? ? ?????????? ????????? ????? ?? ????????? ?????????? ????????? ????????, ???????????? ???????????? ????????? ????.
???????????? ????????? ????. ?????????? ?????????? ????????, ?????????????? ?? ???. 6. ???????? ???? n ????????? ???????????? ???????? ?? ???? ???? H ???????? ??????? ????. ????? ?? ???????? ???????? ???????? ?? ???? ???? M ????????
?????????? ????. ? ?????? ?????? ???? ???? ???????? ???????? ? ????? ???? ?????????? ???????????.1 ? ????? ?????? ???? ????? ????????? ???????????? ?????
?????. ??? ????, ?? ??????????? ??????????, ?????????? ???????? (hidden layers).
?????????? ???????? ???????? ???? ????? ?????????????? ? ??????? ???????? ????????????, ?? ????? ??????, ?????? ????? ?????. ?????????? ???????????
?????????? ?????????? ????????? ?????, ? ??????? ?????????? ????????????? ?????????? ???????????. ?? ???? ?? ???????? ???? ???????????? ??????????? ??????????, ??????????? ?? ??????? ???????????????? ???????????.
?????????????? ??????????? ????????? ?????. ????????? ??????: ????? ??
??????? ????? ??????????? (???? ?? ???????????) ? ??????? ????????? ?????
????????? ????? ????????? ???????? ?? ???? ?????? ?????????????.
1. ????? ?????? ??????? ??????????? ? ???? ??????????? ????. ??? ??????????? ????????? ????????? ?????????????? ??????? ?, ???, ?? ? ??????????????
???????????? ??????? ??????? ? ???? ????????????? ?????????? ????? [4].
2. ?? ??????? ?????????????? ??????????? ????????, ??? ??????????? ????
? ?????????? ????????? ????????? ????????? ???????? ???????????? ????????
???????????? ? n-?????? ???????????? ?????????. ??????????? ???? ????????? ????????? ????? ???????? ???????? ?????????? ?????????????????? ??????? ???????? ??????????????, ?????????????, ???????????????? ????? ??????? ? ??????????? ????????, ??????? ?????????????, ? ????? ???????????????? ????? ??????????? ???????.
3. ???????? ??????? ??????????? ? ???, ??? ????? ??????????? ??????? n ?????????? ??????????? ? ???? ???????????? ??????????? ??????? ?????? ?????????
? ???????????? [2].
1
?????????? ????????????????? ???????? ? ????????? ????? ?????. ?????? ????? ???? (??????,
????? ?? ????????) ???????? ???????????, ?????? ????? x0 , x1 , . . . , xn ??????, Ф?????????????????╗ ?????. ?? ????, ? ???? ?????? ???? ?????? ????, ????????? ?? ??????????? ????????.
? 11 ?
??????? 1.2. (??????????, 1957) ????? ??????????? ??????? n ?????????? ??
????????? ???? [0, 1]n ??????????? ? ????
1
2
n
f (x , x , . . . , x ) =
2n+1
X
k=1
hk
хX
n
i=1
Х
?ik (x ) ,
i
??? hk , ?ik ? ??????????? ??????? ????? ??????????, ?????? ?ik ?? ??????? ?? ?????? f .
???????? ??????, ??? ?????????? ????? ????????? ????? ????????? ?????????
???? ? ????? ??????? ?????. ????? ???????, ???? ????? ??? ??????????, ????? ????????? ???????????? ??????????? ???????, ? ?? ???????????, ? ?????. ? ?????????, ????????????? ??????????? ?? ???????? ????????????: ??????? hk ????????,
??????? ?? f , ? ? ????? ?????? ?? ???????? ?????????????????.
4. ???????? ???????????? ??????? ???????????? ? ???, ??? ????? ??????????? ??????? n ?????????? ????? ?????????? ?????????? ????????? ? ????? ???????? ????????. ????? ????? ??????? ?????? ??????????, ??? ????? ???????????
??????? ?? ???????????? ???????? X ????? ?????????? ?? ?????? ???????????
?? ???????? ??????????, ?? ? ??????????? ?? ?????? ????????? ?????? ??????? F ,
??????????? ????? [12].
???. 1.1. ????? ??????? F ?????????? ??????????? ????? ????????? X, ????
??? ????? ????????? x, x? ? X ?????????? ??????? f ? F ?????, ??? f (x) 6= f (x? ).
??????? 1.3. (?????, 1948) ????? X ? ?????????? ????????????, C(X) ? ??????? ??????????? ?? X ???????????? ???????, F ? ?????? ? C(X), ??????????
????????? (1 ? F ) ? ??????????? ????? ????????? X. ????? F ?????? ? C(X).
?? ????? ???? ??????????? ??? ????? ????? ???????????. ???????????, ??????
??????????? (???????????? ???????? ???????? ? ?????????) ????? ????????????
?????????????? ???????? ? ?????-?????? (??????????? ????????????) ???????????
?????????? ??????? ?????? ????????? [3]. ???? ????????? ????? ?????? ????????? ? ????????? ?????, ????????? ??? ???????? ?? ???????? ????????, ?????????
? ?????????? ??????? ?????????.
???. 1.2. ????? ??????? F ? C(X) ?????????? ????????? ???????????? ??????? ? : R ? R, ???? ??? ?????? f ? F ????????? ?(f ) ? F .
??????? 1.4. (??????? ? ??., 1998) ????? X ? ?????????? ????????????, C(X) ?
??????? ??????????? ?? X ???????????? ???????, F ? ???????? ???????????????
? C(X), ????????? ???????????? ?????????? ??????????? ??????? ?, ??????????
????????? (1 ? F ) ? ??????????? ????? ????????? X. ????? F ?????? ? C(X).
??? ???????????????? ??? ??????????? ?? ????????????? ?????????????????
???????????? ???????????? ????????????: ? ??????? ???????? ???????? ? ????????????? ??????????? ???????? ? ????? ???????? ??????????, ??????????? ?????
??????????? ??????? ? ????? ???????? ?????????.
? 12 ?
??????? ????,
n ?????????
z
}|
{
??????? ????,
H ????????
z
GFED
@ABC
/
x1 ERERRw11
ll5<
l
EEw1h RR
l
l y
RR
lll y
. . . w1HEE llRlRlRlRlRlR yyyy
RyRyR
lElE
wj1 l EE
yy RRRR)
l
y
E
l
l
Ey
@ABC
GFED
/
xj RRR wjh yyyEyEEE
5
EEllllll A
wjH RRyy
yRR
llE
. . . wn1yyy lRlRlRlRlRlR EEEE
RRR EE
y
ll
RRR "
yy ll
R)
ylyllwnh
n
@ABC
GFED
/
x
wnH
w01
w0h
@ABC
GFED
?1
w0H
:
F
X
...
X
...
X
}|
{
?1 ERRR w11
z
/
ll5<
EEw1m R
l
l
E
RRR
ll y
RR llll yyy
w1ME
EElllllRlRRRRRyyy
yR
lE
wh1l EEE yyy RRRR
)
lllw
EEyy
/
?h RRR hm yyy EE
EE llll5
whM RRyy
l
A
llEElE
yyRR
yy lRlRlRlRlRlR EEE
wH1
RRR EE
yy llll
RRR "
yllylwHm
R)
/
?H wHM
:
w01
w0m
@ABC
GFED
?1
???????? ????,
M ????????
F
X
...
X
...
X
}|
{
?1
/ a1
?m
/ am
?M
/ aM
w0M
???. 6. ???????????? ???? ? ????? ??????? ?????.
?????? ??????? ?????? ?? ??????? ? ?????????? ????? ????????? ???? (???????
??????????? ????????????) ? ? ?????????? ????????, ??????????? ??? ????????????? ???????????? ???????. ????????? ????????? ????? ????? ?????????? ????????? ? ????????? ?????.
5.
TODO: ??????? ?? ????? ?????? [5].
????? ???????, ????????? ???? ???????? ?????????????? ????????????????
???????. ??????????? ???? ?????????? ? ??????????? ????? ????? ? ????? ???????? ? ???. ????-???? ?????, ??? ???????, ?????????? ??? ??????? ????????????
??????????? ???????????? ????? ?????????????, ????????? ? ???????????????.
1.2
???????????? ????????? ????
???????????? ???? ????? ????? ??????????? ???????????? ????????,
???????? ?? ???????? ?????????? ??????? ?????????????. ???????? ?????? ??????????? ?????? ?????????? ?????????, ??? ??????? ?????? ??????????? ??? ??????????? ?? ????? ????????, ???? ???????? ???????, ??? ??? ??????? ??????????
???? ?? ????? ???????.
?? ?????? ??????, ?????????? ????????, ??????????? ??? ?????????? ?????????, ?????? ???? ?? ???????? ??????????????? ????? ??????? ?????????????.
?????? ????? ??????? ???????? ????? ?????????????? ????????????????? ???????????? ? ??????????? ???? ??????????? ????????????? ???????. ?????? ?????
??????? ???????? ????????? ??????????????? ?????? (error back-propagation) [11].
1.2.1
????? ????????? ??????????????? ??????
?????????? ???????????? ????, ? ??????? ?????? ?????? ??????????? ????
?????? ?? ????? ????????? ???????????? ????, ???. 6. ??? ??????? ???????? ??????? X = Rn , Y = RM .
ToDo3
? 13 ?
?????? ????????? ???????????. ????? ???????? ???? ??????? ?? M ???????? ? ????????? ????????? ?m ? ???????? am , m = 1, . . . , M . ????? ??? ?????????
??????? ???? ?? H ???????? ? ????????? ????????? ?h ? ???????? uh , h = 1, . . . , H.
???? ????????????? ?????? ????? h-? ???????? ???????? ???? ? m-? ???????? ????????? ???? ????? ?????????? ????? whm . ????? ???? ????? ????? ?????????? ????
????????????????? ????, ???? ??? ???? ??????? ???? ? ???????? v j , j = 1, . . . , J
? ?????????????? ?????? wjh . ? ????? ?????? ????? ????? ????? ???? ????????????. ???? ???? ???????????, ?? J = n ? v j ? xj . ????????? ????? w ?????? ????
????????????? ????? ????.
???????? ???????? ???? ?? ??????? xi ??????????? ??? ????????????:
хX
Х
хX
Х
H
J
m
h
h
j
a (xi ) = ?m
whm u (xi ) ;
u (xi ) = ?h
wjh v (xi ) .
(1.5)
j=0
h=0
??????? ?????????? ?????????????????? ?????? ??? ?????????? ??????? xi :
Q(w) =
M
б2
1 XА m
a (xi ) ? yim .
2 m=1
(1.6)
? ?????????? ??? ??????????? ??????? ??????????? Q ?? ??????? ????????.
??????? ?? ??????? ??? ????????? ????:
?Q(w)
= am (xi ) ? yim = ?m .
m
?a
???????????, ??? ??????? ??????????? ????? ???????? ?????? ?m ?? ??????? xi .
?????? ??????? ??????? ??????????? ?? ??????? ???????? ????:
M
M
X
б ?
?Q(w) X А m
m
?
=
a
(x
)
?
y
?
w
=
?m ?m
whm = ?h .
i
i
m hm
?uh
m=1
m=1
??? ????????, ?? ???????? ? ?m , ????? ???????? ??????? ???? ?? ??????? ????
? ?????????? ????? ?h .
?
????? ?m
?????????? ??????????? ??????? ?????????, ??????????? ???
??? ?? ???????? ?????????, ??? ? ? (1.5). ???? ???????????? ?????????? ???????
?????????, ?? ??? ???????????? ?????????? ??????????? ????? ???????????????
?
???????? ?m
= ?m (1 ? ?m ).
???????, ??? ?h ??????????? ?? ?m , ???? ????????? ???? Ф????? ???????╗, ???
????? ?? ?????? ???????? ???????? ???? ???????? ?m ?m
? ???? ?? ?????? whm ,
? ????????? ?h ????????? ?? ?????:
h
? o
X tjjjjwh1
jTTTT
?1 ?1?
jjj
whM TTT
...
?
?M ?M
???? ????? ??????, ??? ???, ?? ????????? ??????? ??????????? ???????????
??????????:
H
?Q(w) X h ?
=
? ?h wjh = ?j .
?v j
h=1
? 14 ?
???????? 1.2. ???????? ??????????? ???? ??????? ????????? ???????????????
??????
????:
(xi , yi )?i=1 ? ????????? ???????, xi ? Rn , yi ? RM ;
H ? ????? ???????? ? ??????? ????;
? ? ???? ????????;
?????:
????????????? ???? wjh , whm ;
1: ????????????????
????
А
б ?????????? ?????????? ??????????:
2:
3:
4:
5:
6:
7:
8:
1
1
wjh := random А? 2n
;б
, 2n
1
1
whm := random ? 2H , 2H ;
?????????
??????? ?????? xi ????????? ???????;
?????? ??? ? ?????????:
uh (xi ), ?h? ??? ???? h = 1, . . . , H;
?
am (xi ),q?m
, ?m ??? ???? m = 1, . . . , M ;
PM
m 2
Qi :=
m=1 (? ) ;
????????
? ?????????:
PM ???
h
m ?
? := m=1 ? ?m whm ??? ???? h = 1, . . . , H;
??????????? ???:
? h
whm := whm ? ??m ?m
u , ??? ???? h = 0, . . . , H, m = 1, . . . , M ;
h ? j
wjh := wjh ? ?? ?h x , ??? ???? j = 0, . . . , n, h = 1, . . . , H;
Q := ??1
Q + 1? Qi ;
?
???? Q ?? ???????????????;
???? ??????? ??????????? ?? am ? uh , ????? ???????? ???????? Q ?? ?????:
?Q(w) ?am
?Q(w)
? h
=
= ?m ?m
u ,
m = 1, . . . , M, h = 0, . . . , H;
(1.7)
?whm
?am ?whm
?Q(w) ?uh
?Q(w)
=
= ?h ?h? v j ,
h = 1, . . . , H, j = 0, . . . , J;
(1.8)
?wjh
?uh ?wjh
? ??? ????? ??? ??????? ????.
?????? ?? ???????? ???? ???????????, ????? ????????? ???????? ????????
????????? ???????????????, ??. ???????? 1.2.
??????????? ?????? ????????? ???????????????.
? ?????????? ??????? ?????????????. ?????? ???, ???????? ??? ? ??????????
????????? ??????? ??????? O(Hn + HM ) ????????.
? ????? ?????? ?????? ???????? ?????????? ?????? ? ??????? ? ??? ????????.
??????? back-propagation ????? ??????????? ?? ?????????????? ???????????
? ???????????? ????????????.
? ??????? ??????? ????????. ???????? ????? ???????? ??? ????????????? ?????
?????, ???????????? ??????????? ??????? ? ???????????? ??????? ????????? (????????, ????????? ? ?????? ????????). ????? ????, back-propagation
? 15 ?
?? ??????????? ??????? ??????????? ?? ???????????? ????? ???????????.
??? ????? ????????? ?????? ? ?????? ???????????? ????????: ??????????
??????, ??????????? ??????????, ? ???????.
?????????? ?????? ????????? ???????????????.
? ????? ?? ?????? ????????. ??? ????????? ?????????? ?????????? ?????????
??????? ?????????? ????????? ????????????? ?????????.
? ??????? ???????????? ?????? ??????? ?????????? ? ?????????????? ?????????
????????? ??????????? Q.
? ?????????? ??????? ??????????? ????? ???????? ???????? ???? H. ? ?? ?? ?????, ??? ????????? ???????? ????????? ????, ?? ???????? ????? ???????????
???????? ???????? ???????? ? ???????? ??????????.
? ??? ?????????? ?????????? ????????? ???? ??????? ? ????????????.
? ???? ??????????? ??????? ????????? ? ??????????????? ???????????, ????
?????????? ??? th, ?? ???? ????? ???????? ? ????????? Ф????????╗. ??? ?????? ???????? ????????????? ????? ?? ????? ???????, ??? ????? ???????? ??????????? ? ? ? ????, ??? ?????? ????????? ????????????? ????? ? ????????????
? ????????? (1.7)?(1.8). ???? ?????? ???? ??? ???????? ? ????? Ф???????
????╗, ?? ? ???? ??????????? ?? ???????? ?????? ?? ??? ?????????. ?????????????? ????? ????????? ?????, ???????, ??? ??? ???? ? ?????.
1.2.2
????????? ?????????? ? ???????? ???????????? ????????
? ???? ??????? ??????????????? ????????????? ??????, ??????????? ? ??????? ??? ??????? ??????? ?????????? ?????????? ?????? ????????? ???????????????. ????????? ????????? ????????? ?????, ??? ?????? ?????? ????????? ????????? ???? ?? ????? ????????? ??????????, ??. ????? [7].
???????????? ??????. ??????? ????????? ???? ???????????? ? ????????? ? ????????? ????????? ?????????. ? ?????? ??????? ???????? ???? ????? ????????? ??????????????. ??????? ????? ????????? ??? ??????????? ???????? ???????? ??????????????? ???????????? ?????????:
xj ? xjmin
x := j
,
xmax ? xjmin
j
j
???? x :=
xj ? xj??
xj???
,
j = 1, . . . , n,
??? xjmin , xjmax , xj?? , xj??? ? ?????????????? ???????????, ????????????, ??????? ???????? ? ?????????????????? ?????????? ???????? xj .
????? ??????? ?????????. ?????????? ??????? ?(z) = (1 + e?z )?1 ????? ??????????? ??? ??????? ????? ?????????????. ?? ???????????? ? ??????????? ???????
??????????? ?????????????? ??????? ?????? ?? ??????? (1.4), ????????????? ?????????? ???????????, ?????????????? ????????? ????????. ?????????? ????????
? 16 ?
???????, ????? ??? th(z) = 2?(2z) ? 1, ??????????? ???????? ?????????? ????????
? ??????? ????.
??? ?????????????? ??????? ???????? ????? ????? ????????? ????????? ???????? ????: th z?+ ?z. ????? ???????????? ? ?????? ???????? ???????? ???????,
???????? ln(z + z 2 + 1).
??? ???? ??????? ????????? ??????? ? ??????????? ??????????? ?????????????????? ??????? (1.6) ? ??????? ?????????????. ???? ???????? ????? ???????
{?1, +1} ????????? ?? ?????????? ?????????????? ???????? ??????? ?????????
????????? ????, ?? ??????????????? ??????? ????? ?????????? ? ???????????????
?????????? ????????? ??????? ?????????, ?????????????, ? ???????? ?????????
???????. ????? ???????, ???????? ????? ??????? ?????? ?????????? ?????? ??????? ???????? ??????? ?????????. ? ?????? [7] ????????????? ???????????? ???????
????????? 1.7159 th( 23 z), ? ??????? ? ?????? {?1, +1} ??????????? ???????? ??????
???????????.
????? ?????????? ???????????. ?? ??? ?? ??????????? ?????????????? ???????? ????????????? ???? ?????? ?????????????????? ?????????? ?? ?????? ??????????. ? ?????????
Б 1 1 ц 1.2 ?? ???? 1 ???? ???????????????? ?????????? ??????????
?? ??????? ? 2k
, 2k , ??? k ? ????? ???????? ? ??? ????, ?? ???????? ??????? ??????
??????. ? ???? ?????? (? ??? ???????, ??? ??? ???????? ?????????????) ????????
????????? ???????????? ?????????????? ???????? ? Ф??????? ????╗ ??????? ?????????, ?????????????? ?? ???. 2.
??????? ???????????? ????????. ????? ??????????? ???????????? ???????????? ????? ??????????????? ????????? (?. ?. ??????????? ??????? ? ????????? ???????), ??????? ??? ????????? ???????????.
1. ?????????? ???????? ????? ????????? ??? ???? ???????, ??????? ???????? ????? ?? ???????, ????????????? ?? ????. ? ????? ?????? ???????? ??????
???????, ????? ?? ???????? ??????????? ???????????? ?? ?????? ???? ????????.
??????? ??? ?????????? ????????? ??????????? ? ???, ????? ??????????? ??????????? ??????? ?? ?????? ???????, ????????? ??????? ?????? ?????? ? ??????? ???????????? ???????? ?????? ??????????. ??? ??????? ?????????? ????????????
???????? (shu?ing).
2. ??? ???? ????????? ??????? ? ???, ????? ???? ??????????? ?? ???????,
?? ??????? ???? ???????? ??????. ??? ????? ??????????? ????????? ??????? ??????? ??????????? ? ???????????? ? ????????? ?????? ???? ?? ?????? ???????. ????
????? ????????????? ????????? ?????? ? ??? ???????, ????? ???????? ?????? ?? ???????? ????????, ????? ??????? ???????? ????? ??????????????? ?? ??????? ????????, ??????? ?????? ????????? ?? ????????? ?? ????????? ???????.
????????????? ??? ?????????? ?????. ???? ????? ???????? ??????? ???????
????????????? ??????????? ???????????? ????? ?? ?. ?. ????????. ?? ??????????
???????????????? ????????????? ???????? ???? ? ????????????? ?????????????
??????? ???????????????????? ? ????????? ?????????????? ?????, ????????????
???? ???????? ???????. ??????????? ????? ??????????? ? ???????? ??????????????? ??????? ? ? ???????? ?????????.
? 17 ?
????????, ??? ??? ???????? ???? ?????????????? ?????????? Q(w). ???? ??????????? ? ???, ????? ?????????? ????????? ???? ?????????? ???????? ?????,
??????? ? ?????????? ??????????? ???????? ?????????:
?
Q? (w) = Q(w) + kwk2 .
2
????????? ??????????? ???????? ? ????????? ?????????? ???????? ? ?????????:
?Q? (w)
?Q(w)
=
+ ?w.
?w
?w
??? ???? ??????? ?????????? ????? ????????? ???
w := w(1 ? ??) ? ?
?Q(w)
.
?w
???????????? ??????????? ??????????? ? ????????? ???????????????? ?????????
(1 ? ??), ??? ???????? ? ??????????? ?????????? ?????. ?????? ???????? ?????? ?
?????????? ????? (weights decay).
???????????? ??????? ?????? ? ???, ??? ?? ????? ?????? ??????????? ? ?????????? ? ?????? ????????????? ? ?????? ???????????? ???????? ???????????.
?????????? ????? ?????????? ? ??? ???????, ????? ????? ???????? ????????? ??????? ??????? ????????? ??? ?????? ???????????????.
?????????? ?????? ?????????? ????? ? ????????? ??????????????? ???????????? ????????? ?, ??????? ?????????? ????????? ????????????????.
?????????? ????? ??????.
TODO: optimal brain damage
????? ????? ?????. ???? ? ?????????? ?????? ???????? ? ???????? ????????????
??????? ???????? ?????????????, ?? ????? ???????????? ??????????? ?????. ??????????? ???? ????????? ???????????? ?????????? ?????????? ???????, ? ? ??????????? ??????? ????? ???????. ???????????? ?????? ????? ????? ????????????
??? ????????????? ??????? ???????????? ????????. ??? ?????? ?????, ??? ????
???????? ??????????? ??????, ? ??? ??????? ??????? ????.
????? ????? ???????? ? ??????? ???? H ?????????? ?????????? ?????????,
?? ?? ???? ?? ??? ?? ???????? ??????.
1. ?????????? ??????. ???? ??????? ??????? (??? ?????? ?????????) ??????? ????????, ??????, ???? ????????????, ? ?????????? ??????????? ????? ????????
? ??????? ????. ???? ??????? ??????? (??? ?????? ?????????) ?????????? ???????
?????? ?????????, ?? ???????? ??????
Документ
Категория
Без категории
Просмотров
12
Размер файла
406 Кб
Теги
лекция, нейронные, сетях, искусственные, pdf, воронцова, 2006
1/--страниц
Пожаловаться на содержимое документа