Mạng thần kinh nhân tạo cho phân lớp màu sắc part 4

Chia sẻ: Asg Ahsva | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

50
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong khoảng [0,1], điểm bắt đầu tìm kiếm là a1 = 1 – 0.618 = 0.382 và a2 = 0.618, không phụ thuộc vào N hoặc . Tỷ lệ 5  1 / 2 được biết trong toán học và kiến trúc cổ điển dưới tên tỷ lệ vàng (Golden Section). Nó chia một đoạn thành hai phần, làm cho một tỷ lệ rất lớn của đoạn ban đầu tương đương tỷ lệ nhỏ hơn. Vì lý do này nên kỹ thuật loại trừ này gọi là kỹ thuật tìm kiếm tỷ lệ vàng....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mạng thần kinh nhân tạo cho phân lớp màu sắc part 4

FN F FN 1  N 1  L2  FN 1 FN 2 FN 1  FN FN 1 1 L2    hoÆc FN 1 1  FN 1  L2 FN 1  L2  ( L2 ) 2  1 1 5  L2  2 5 1 L2   0.618 (12.8) 2 Trong kho¶ng [0,1], ®iÓm b¾t ®Çu t×m kiÕm lµ a1 = 1 – 0.618 = 0.382 vµ a2 = 0.618, kh«ng phô thuéc vµo N hoÆc . Tû lÖ 5  1 / 2 ®îc biÕt trong to¸n häc vµ kiÕn tróc cæ ®iÓn díi tªn tû lÖ vµng (Golden Section). Nã chia mét ®o¹n thµnh hai phÇn, lµm cho mét tû lÖ rÊt lín cña ®o¹n ban ®Çu t¬ng ®¬ng tû lÖ nhá h¬n. V× lý do nµy nªn kü thuËt lo¹i trõ nµy gäi lµ kü thuËt t×m kiÕm tû lÖ vµng. ThuËt to¸n cho t×m kiÕm tû lÖ vµng b©y giê cã thÓ tr×nh bµy b»ng c¸c bíc sau: 1. X¸c ®Þnh hai ®iÓm 1 vµ 2 mµ chøa ®iÓm gi¸ trÞ nhá nhÊt (1 > 2). 2. TÝnh L = 2 - 1, a2 = 0.618L + 1, vµ a1 = 1 + 2 - a2 (tham kh¶o h×nh 12.7). 3. TÝnh tol = 2 - 1; 4. NÕu tol <  th× dõng l¹i. 5. TÝnh y1 = f(a1) vµ y2 = f(a2). 6. NÕu y1 < y2 vµ a1 > a2 th× lo¹i trõ miÒn [1,a2], cô thÓ, 1 = a2 vµ a2 = 1 + 2 - a1. NÕu y1 < y2 vµ a1 < a2 th× lo¹i trõ miÒn [a2, 2], cô thÓ, 2 = a1 vµ a2 = 1 + 2 - a1. NÕu y1 > y2 vµ a1 > a2 th× lo¹i trõ miÒn [a1, 2], cô thÓ, 2 = a1 vµ a1 = 1 + 2 - a2. 288
NÕu y1 > y2 vµ a1 < a2 th× lo¹i trõ miÒn [1,a1], cô thÓ, 1 = a1 vµ a1 = 1 + 2 - a1. 7. ChuyÓn tíi bíc ba . Bµi tËp 12.1 LËp mét ch¬ng tr×nh C cho t×m kiÕm tû lÖ vµng. KiÓm tra ch¬ng tr×nh theo c¸c hµm díi ®©y: f(x) = 6.0 - 11x + 6x2 - x3 (Tr¶ lêi : 1.42256 cho kho¶ng [0,2]) 2 f(x) = (100 - x) (Tr¶ lêi : 100) x 2 -2x f(x) = e - 3x - 2e (Tr¶ lêi : 2.8316) Mét ph¬ng ph¸p ®ßi hái Ýt c¸c gi¸ trÞ hµm h¬n ph¬ng ph¸p tû lÖ vµng ®îc ph¸t triÓn bëi Powell. C¬ së cña ph¬ng ph¸p nµy dùa trªn ®¸nh gi¸ bËc hai liªn tiÕp. Ph¬ng ph¸p ®¸nh gi¸ bËc hai cho r»ng mét kho¶ng giíi h¹n mét hµm cã thÓ xÊp xØ bëi mét hµm bËc hai. Gi¸ trÞ cùc tiÓu cña hµm bËc hai nµy dïng nh ®¸nh gi¸ ®Çu tiªn cho gi¸ trÞ nhá nhÊt cña hµm. Gi¸ trÞ cùc tiÓu nµy cïng víi hai ®iÓm n÷a dïng ®Ó tÝnh ra mét xÊp xØ tèt h¬n, vµ cø tiÕp tôc nh vËy. Cuèi cïng, gi¸ trÞ cùc tiÓu cña hµm bËc hai sÏ xÊp xØ gi¸ trÞ nhá nhÊt thùc sù trong giíi h¹n sai sè nµo ®ã. Ph¬ng ph¸p xÊp xØ bËc hai cã thÓ m« t¶ b»ng c¸c bíc sau: Cho ba ®iÓm liªn tiÕp nhau x1, x2, x3 vµ gi¸ trÞ hµm t¬ng øng cña nã f1, f2, f3 chóng ta x¸c ®Þnh ba h»ng sè cña hµm bËc hai q(x) = a0 + a1(x-x1) + a2(x-x1)(x-x2) (12.9) V× f1 = f(x1) = q(x1) = a0 chóng ta cã a0 = f1 (12.0) V× f2 = f(x2) = q(x2) =f1 + a1 (x2 - x1) f 2  f1 chóng ta cã a1  x 2  x1 (12.11) Cuèi cïng t¹i x = x3 f 2  f1 (12.12) f 3  f ( x3 )  q( x3 )  f1  ( x3  x1 )  a 2 ( x3  x1 )( x3  x 2 ) x 2  x1 289
§Ó rót ra giíi h¹n cùc ®¹i (hoÆc cùc tiÓu) chóng ta lÊy vi ph©n q(x) theo x vµ cho biÓu thøc nµy b»ng 0. dq  a1  a 2 ( x  x1 )  a 2 ( x  x 2 )  0 dx Gi¶i biÓu thøc trªn theo biÕn x chóng ta rót ra gi¸ trÞ ®¸nh gi¸ x 2  x1 a 1 (12.13) x 2a 2 2 Chó ý r»ng gi¸ trÞ nhá nhÊt rót ra nÕu d 2q (12.14)  2a 2  0 d 2x ThuËt to¸n Powell dïng ®Ó ®¸nh gi¸ bËc hai liªn tiÕp ®îc cho bëi Powell. Tuy nhiªn, nÕu nh a2 b»ng 0 th× hµm nµy kh«ng thÓ xÊp xØ b»ng hµm bËc hai. Mét ph¬ng ph¸p bao gåm t×m kiÕm tû lÖ vµng vµ xÊp xØ bËc hai liªn tiÕp ®îc cho bëi Brent. Ph¬ng ph¸p cña Brent ®îc dïng cho hµm nhiÒu biÕn cho ë phÇn kÕ tiÕp díi ®©y. 12.5.2 Thu hÑp gi¸ trÞ nhá nhÊt Kh«ng cã ph¬ng ph¸p nµo dïng c¸c phÇn trªn lµ kh«ng cã bíc thu hÑp gi¸ trÞ nhá nhÊt lóc ban ®Çu. Mét lu ®å do Swann ph¸t triÓn ®îc t«i lùa chän ®Ó dïng. Ph¬ng ph¸p nµy ®îc tr×nh bµy tèt nhÊt q ua c¸c thuËt to¸n díi ®©y. 1. Lùa chän gi¸ trÞ ban ®Çu x0 vµ mét bíc nhá dx. 2. TÝnh x1 = x0 + dx y1 = f(x0) y2 = f(x1) 3. NÕu y1  y0 th× cho dx = -dx vµ tÝnh x1 = x0 + dx y1 = f(x1) 4. TÝnh 290
dx = 2.0 * dx x2 = x1 + dx y2 = f(x2) 5. LÆp l¹i c¸c bíc díi ®©y cho ®Õn khi y2 > y1 dx = 2.0 * dx x0 = x1 y0 = y1 x1 = x2 y1 = y2 x2 = x1 + dx y2 = f(x2) 6. MiÒn thu gän lµ (x0,x1) 12.5.3 Ph¬ng ph¸p tèi thiÓu ho¸ hµm nhiÒu biÕn Cã mét sè kü thuËt cã hiÖu qu¶ cho tèi thiÓu ho¸ mét hµm nhiÒu biÕn. Ph¬ng ph¸p mµ hay ®îc dïng sÏ x¸c ®Þnh mét híng t×m kiÕm trong kh«ng gian nhiÒu chiÒu. TiÕp theo, mét phÐp xÊp xØ mét biÕn sÏ x¸c ®Þnh gi¸ trÞ tèi thiÓu däc theo híng nµy. Mçi lÇn mét gi¸ trÞ tèi thiÓu ®îc t×m thÊy, mét híng míi ®îc t×m t×m thÊy vµ qu¸ tr×nh t×m kiÕm l¹i b¾t ®Çu l¹i tõ ®Çu. §iÒu nµy tiÕp tôc cho ®Õn khi ®¹t ®îc héi tô. Quy t¾c delta m« t¶ ë phÇn trªn cã liªn hÖ víi mét kü thuËt gäi lµ sù h¹ thÊp dèc nhÊt. Tuy nhiªn, vÉn cha cã mét kÕt qu¶ nµo ®îc t¹o ra ®Ó ®a ra mét sù t×m kiÕm ®¬n biÕn däc theo sù h¹ thÊp dèc nhÊt. Mét sù kh¸c biÖt n÷a lµ c¸c mÉu ®îc cho lÇn lît t¹i tõng thêi ®iÓm b»ng sù söa l¹i c¸c träng sè. Trong s¬ ®å hay ®îc dïng nhÊt th× ®iÒu nµy kh«ng x¶y ra, tÊt c¶ c¸c mÉu ®îc cung cÊp cho ch¬ng tr×nh ®Ó tÝnh mét híng t×m kiÕm thuËn tiÖn nhÊt. Bëi v× ®©y kh«ng ph¶i lµ mét quyÓn s¸ch tèi u, nªn t«i sÏ tr×nh bµy víi c¸c b¹n tÊt c¶ c¸c ph¬ng ph¸p tèi u ho¸ cho hµm nhiÒu biÕn. Nhng t«i sÏ chØ tr×nh bµy víi b¹n hai ph¬ng ph¸p mµ t«i thÊy cã kÕt qu¶ nhÊt. Ph¬ng ph¸p ®Çu tiªn mµ t«i tr×nh bµy ®îc ph¸t triÓn bëi Fletcher vµ Reeves gäi lµ ph¬ng ph¸p gradient kÕt hîp. Gradient kÕt hîp lµ mét híng c¬ së ®îc 291
thiÕt kÕ dïng ®Ó tèi thiÓu ho¸ mét hµm bËc hai ®Çy ®ñ cã N biÕn sau ®óng N bíc. Mét ph¬ng ph¸p kh¸c ®îc ph¸t triÓn bëi Davi®on, Fletcher, Reeves. Ph¬ng ph¸p nµy thêng hay ®îc dïng ®Ó tèi thiÓu ho¸ c¸c hµm cã sè biÕn lín. B¹n sÏ kh«ng cÇn ph¶i hiÓu c¸c chøng minh cña c¸c thuËt to¸n nµy khi ¸p dông. NÕu b¹n muèn t×m hiÓu thªm, t«i ®Ò nghÞ b¹n h·y t×m ®äc c¸c cuèn s¸ch ®îc xuÊt b¶n gÇn ®©y nhÊt vÒ tèi u ho¸. TiÕp theo t«i sÏ tr×nh bµy hai thuËt to¸n nµy. Chóng ta sÏ gi¶ thiÕt r»ng hµm N biÕn ®îc tèi thiÓu ho¸ cho díi d¹ng y = f(x0,x1,x2,...,xN-1) = f(X) vµ X = [ x0 x1 x2 ... xN-1]  f f f  f   ...   x0 x1 x N 1  Ph¬ng ph¸p gradient kÕt hîp Fletcher-Reeves. 1. Chän c¸c gi¸ trÞ ban ®Çu cho X = [x0 x1 x2 ... xN-1], vµ ®Æt biÕn ®Õm sè lÇn lÆp b»ng kh«ng, vÝ dô, iter = 0. Chän sè lÇn lÆp lín nhÊt cho phÐp. 2. TÝnh  f f f  f   ...   x0 x1 x N 1  3. §Æt S =  f = [s0 s1 s2 ... sN-1] 4. TÝnh N 1  | df i | test  i0 NÕu test <  th× héi tô ®· ®¹t ®îc, tr¶ l¹i gi¸ trÞ X vµ ra khái ch¬ng tr×nh. 5. §Æt fp = f. 6. Tèi thiÓu ho¸, dïng mét gi¶ thiÕt kh«ng biÕn, c¸c hµm sau theo  f ( x0  s 0 , x1  s1 ,..., x N 1  s N 1 7. Söa l¹i X = X + S. 8. TÝnh f(X). 9. CËp nhËt gi¸ trÞ cña S dïng: 292
f ( X )f ( X ) T S  f ( X )  s f ( X ) p f ( X ) T p 10. NÕu f si  0 x i cho i bÊt kú , ®Æt S = -f, vÝ dô , dïng sù h¹ thÊp dèc nhÊt. 11. TÝnh iter = iter + 1 12. NÕu (iter < sè lín nhÊt cña phÐp lÆp cho phÐp) th× chuyÓn tíi bíc 4, nÕu kh«ng th× tr¶ l¹i gi¸ trÞ X vµ tho¸t ra khái ch¬ng tr×nh. Ph¬ng ph¸p Davidon-Fletcher- Powell. Chóng ta coi r»ng hµm N biÕn ®îc tèi thiÓu cho bëi y = f(x0, x1 , x2, ..., xN-1) = f(X). ThuËt to¸n nµy bao gåm c¸c bíc: 1. Chän c¸c gi¸ trÞ ban ®Çu cho X = [x0 x1 x2 ... xN-1], vµ ®Æt biÕn ®Õm sè lÇn lÆp b»ng 0, vÝ dô, iter = 0. Chän sè lÇn lÆp lín nhÊt cho phÐp. 2. TÝnh  f f f  f   ...   x0 x1 x N 1  3. §Æt S = -f = [s0 s1 s2 ... sN-1]. 4. ThiÕt lËp ma trËn H ®ång nhÊt N  N phÇn tö, vÝ dô H = I. 5. TÝnh N 1 test   | df i | i 0 NÕu test <  th× héi tô ®· ®¹t ®îc, tr¶ l¹i gi¸ trÞ X vµ ra khái ch¬ng tr×nh. 6. §Æt fp = f. 7. §Ó tèi thiÓu ho¸, dïng mét ph¬ng ph¸p mét biÕn cho hµm díi ®©y theo biÕn  f ( x0  s 0 , x1  s1 ,..., x N 1  s N 1 8. Thay X = X + S. 9. TÝnh f(X). 293
10. TÝnh Y = f - fp. 11. CËp nhËt gi¸ trÞ cña H dïng c¸c biÓu thøc díi ®©y: ( HY T )(Y T H ) N  (YHY T ) ST S M  SY T H H M N 12. TÝnh S = -Hf. 13. NÕu f si  0 xi cho i bÊt kú, ®Æt S = -f, cô thÓ, dïng qu·ng dèc nhÊt. 14. TÝnh iter = iter +1. 15. NÕu (iter < gi¸ trÞ lín nhÊt cña sè lÇn lÆp cho tríc) th× quay vÒ bíc 5, nÕu kh«ng th× tr¶ l¹i gi¸ trÞ X vµ ra khái ch¬ng tr×nh. Cho c¶ hai ph¬ng ph¸p trªn th×  cã thÓ rót ra b»ng kü thuËt t×m kiÕm hµng cña Brent. §Ó dïng c¸c lu ®å nµy, gradient cña hµm cÇn tÝnh sÏ ph¶i ®îc tÝnh. C¸c gradient nµy ®îc cho bëi M 1 E    (d i  yi ) yi (1  yi ) x 0i (12.15)  0 i 0 M 1 E    (d i  y i ) yi (1  y i ) x1i vµ (12.16) 1 i 0 XÊp xØ gradient kÕt hîp dïng hµm sai lÖch tæng chØ ®ßi hái 36 lÇn lÆp ®Ó ®¹t ®îc héi tô. Gi¸ trÞ ban ®Çu ®îc cho ngÉu nhiªn vµ kÕt qu¶ lµ 0= 0.010559, 1= 0.021119, vµ  ®îc chän lµ 0.1. Gi¸ trÞ sai lÖch ban ®Çu cña hµm lµ 7.3. Sau 36 lÇn lÆp sai sè gi¶m xuèng 0.000134 vµ kÕt qu¶ cho bëi 0 = 115.72, 1 = -104.03, vµ  = 0,1. 294
Nh¾c l¹i lµ quy t¾c delta yªu cÇu 15,000 phÐp lÆp ®Ó sai sè gi¶m xuèng nhá h¬n mét mét Ýt. Tõ ®©y, ta cã thÓ lùa chän mµ kh«ng nghi ngê g× mét kü thuËt khi d¹y mét hÖ thèng thÇn kinh nhiÒu líp. 12.6 Perceptron nhiÒu líp Mét perceptron ®¬n lÎ víi hai ®Çu vµo cã thÓ biÓu diÔn díi d¹ng s¬ ®å b»ng mét ®êng th¼ng chia hai líp (H×nh 12.5). Râ rµng, ®Ó v©y quanh mét miÒn trong hÖ thèng hai ®Çu vµo (2-D sysem) ®ßi hái Ýt nhÊt ba ®êng th¼ng (H×nh 12.9). §iÒu nµy dÉn chóng ta mét c¸ch tù nhiªn ®Õn s¬ ®å perceptron hai líp cho trong h×nh (12.10). HÖ thèng nµy bao gåm mét líp ®Çu vµo, mét líp bÞ che khuÊt vµ mét líp ®Çu ra. Kh«ng khã kh¨n l¾m ®Ó chØ ra r»ng cho mét hÖ thèng ba ®Çu vµo (3-D system) cÇn Ýt nhÊt bèn mÆt dïng ®Ó bao kÝn miÒn, vÝ dô, bèn perceptron hoÆc nót sÏ ph¶i cÇn tíi trong líp bÞ che khÊt. Tæng qu¸t, cho mét siªu kh«ng gian N chiÒu, (N + 1) siªu mÆt ph¼ng sÏ cÇn ®Ó bao kÝn miÒn ®îc cho, N + 1 perceptron hoÆc nót ®îc cÇn trong líp bÞ che khuÊt. Mét miÒn låi lµ mét miÒn mµ trong nã bÊt cø ®êng nµo nèi c¸c ®iÓm trªn ®êng bao cña miÒn còng chØ ®i qua nh÷ng H×nh 12.9 MiÒn ®îc bao quanh. 295
H×nh 12.10 Perceptron ba líp. H×nh 12.11 C¸c kiÓu kh¸c nhau cña miÒn quyÕt ®Þnh. 296
H×nh 12.12 M¹ng ba líp tæng qu¸t. ®iÓm trong ph¹m vi miÒn ®ã. Mét perceptron ba líp, nãi mét c¸ch kh¸c, cã thÓ chia thµnh c¸c miÒn tuú ý vµ cã thÓ t¸ch thµnh c¸c líp khíp nhau nh trong h×nh 12.11. H×nh 12.12 miªu t¶ mét phÇn tö hÖ thèng c¶m nhËn ba líp. C¸c quan hÖ nèi liÒn nhau kh«ng ®îc thÓ hiÖn ®Ó lµm cho s¬ ®å kh«ng bÞ phøc t¹p. Chóng ta sÏ nhËn ®îc c¸c ®¹o hµm theo c¸c träng sè cho trêng hîp ba líp. Chóng ta sÏ tÝnh c¸c biÓu thøc trong trêng hîp tæng qu¸t, sau ®ã chóng ta còng ¸p dông c¸c biÓu thøc nµy perceptron hai líp. Sau ®©y chóng t«i sÏ cung cÊp cho c¸c b¹n file nguån cho mét ch¬ng tr×nh tæng qu¸t tÝnh cã thÓ dïng cho mét hÖ thèng cã kÝch thíc bÊt kú. TÊt nhiªn lµ mét vÝ dô còng ®îc cho theo kÌm. C¸c träng sè ®îc ®¸nh sè lµ ijl , ë ®©y i = vÞ trÝ nót trong líp l - 1 j = vÞ trÝ nót trong líp l Tæng cña c¸c tÝn hiÖu vµo vµo bÊt kú nót nµo ®îc ký hiÖu lµ netil, ë ®©y i = vÞ trÝ nót trong líp l +1 . TÝn hiÖu ra cña tõ bÊt kú nót nµo trong m¹ng ®îc ký hiÖu lµ yil, ë ®©y i = vÞ trÝ nót trong líp l+1. Tõ s¬ ®å h×nh 12.12 chóng ta cã thÓ viÕt hµm sai lÖch tiÕp theo:  N 3 1 1 M 1 2   ( 2)    d i (k )  y i (k )  (12.17) E 2 k 0  i 0    §Ó rót ra ®¹o hµm cña E theo c¸c träng sè chóng ta sÏ b¾t ®Çu víi c¸c träng sè cung cÊp cho líp ra. Bëi thÕ, y ( 2) (k )   N 3 1 M 1 E     d i (k )  y i( 2 ) (k ) i ( 2)     mn) k 0 (2  mn   i 0 Chóng ta cã thÓ viÕt 297
y i( 2) (k ) y i( 2) (k ) net i( 2 ) (k )    n2 ) ( net i( 2) (k )  mn) (2 f (net i( 2) (k ))   N 2 1 ( 2) (1)  ( 2   il  y l (k )   net i( 2) (k )  mn)  l  0  0 im    f (net ( 2) (k ))  y 1 (k ) i  m  m n M 1 E    (d m (k )  ym2) (k ))  f (netm2) (k ))  yn1) (k ) ( ( ( Cho nªn ( 2)  mn k 0 B»ng ®Þnh nghÜa  m (k )  (d m (k )  y m (k ))  f (net m2) (k )) 2 2 ( (12.18) chóng ta cã thÓ viÕt: M 1 E    m2) (k )  y n1) (k ) ( ( (12.19) (1)  mn k 0 §¹o hµm cña E theo c¸c träng sè cung cÊp cho líp Èn thø hai cã thÓ rót ra theo:  N 3 1 yi( 2) (k )  M 1 E ( 2)     (d i (k )  yi (k ))   mn) k  0  i 0 (1  mn)  (1 yi( 2) (k ) yi( 2) neti( 2) B©y giê   (1) neti( 2)  mn) (1  mn C«ng thøc cuèi cïng ®îc ®a ra nh sau: yi( 2) (k )   N 2 1 (   f i(neti( 2) )  (1)    il2) y1  l (1)  mn  mn  l 0  N 2 1 (1) ( f ( net l )  f i(neti( 2) )   il2)  mn) (1 l 0 N 2 1  ( f (netl(1) ) netl(1)   f i(neti( 2) )   il2)   (1  netl(1)  mn)  l 0  N 3 1 M 1 E   f (net m1) (k ))    i( 2) (k ) im ) y n0) (k ) ( (2 ( Bëi vËy (1)  mn k  0 i 0 298