Download pdf - Chuong7 AI

Transcript
  • 8/14/2019 Chuong7 AI

    1/89

    NHP MN TR TU NHN TO

    @copyrights by DrNguyn XunHoi

  • 8/14/2019 Chuong7 AI

    2/89

    Nhp mn hc my

  • 8/14/2019 Chuong7 AI

    3/89

    Outline

    Th no l hc?

    Hc quy np.

    Hc vi cy quyt nh. Hc trong Mng Neural. Mng Perceptron.

    Mng Perceptron a lp vi thut gii BP.

  • 8/14/2019 Chuong7 AI

    4/89

    Th no l hc?

    Nh v lm li (hc vt).

    Hc nh quan st v khi qut ho (hc hiu). nh ngha ca H. Simon.

    Hc l s thay i thch ng trong h thng

    gip cho h thng c th x l vn ngycng hiu qu hn khi gp li nhng tnhhung tng t

  • 8/14/2019 Chuong7 AI

    5/89

    Hc lm g?

    Hc l cn thit trong nhng mi trng chaquen thuc,

    Hc l mt phng php hu hiu xy dng

    h thng

    Hc l cch cc chng trnh thng minh c

    th hiu chnh hnh vi tng hiu qu giiquyt vn .

  • 8/14/2019 Chuong7 AI

    6/89

    Learning agents

  • 8/14/2019 Chuong7 AI

    7/89

    Xy dng module hc cho h thng

    Vic xy dng module hc cho h thng phi tnhn yu t: Phn no cn hc tng hiu nng gii quyt vn .

    Thng tin phn hi i vi phn ny ca h thng.

    Biu din cho tri thc cn hc.

    Dng thng tin phn hi: Hc c gim st: tr li chnh xc cho cc cu hi.

    Hc khng gim st: khng c cu tr li chnh xc.

    Hc tng cng: thng nu lm ng.

  • 8/14/2019 Chuong7 AI

    8/89

    Hc quy np

    V d: hc mt hm t mu v d.

    flhm mc tiu

    Mt mu v d l mt cp (x, f(x))

    Bi ton: Tm gi thuyt hsao cho h fda trn tp mu cho trc

    M hnh n gin ho vic hc: Khng tnh n tri thc c sn Gi s tp mu l c .

  • 8/14/2019 Chuong7 AI

    9/89

    Phng php hc quy np

    Xy dng h gn vi ftrn tp hun luyn (h c gi l nht qun vi ftrn tp mu)

    E.g., khp ng cong:

  • 8/14/2019 Chuong7 AI

    10/89

    Phng php hc quy np

    Xy dng h gn vi ftrn tp hun luyn

    (h c gi l nht qun vi ftrn tp mu)

    E.g., khp ng cong:

  • 8/14/2019 Chuong7 AI

    11/89

    Phng php hc quy np Xy dng h gn vi ftrn tp hun luyn

    (h c gi l nht qun vi ftrn tp mu) E.g., khp ng cong:

  • 8/14/2019 Chuong7 AI

    12/89

    Phng php hc quy np

    Xy dng h gn vi ftrn tp hun luyn

    (h c gi l nht qun vi ftrn tp mu)

    E.g., khp ng cong:

  • 8/14/2019 Chuong7 AI

    13/89

    Phng php hc quy np

    Xy dng h gn vi f trn tp hun luyn

    (h c gi l nht qun vi f trn tp mu)

    E.g., khp ng cong:

  • 8/14/2019 Chuong7 AI

    14/89

    Phng php hc quy np Xy dng h gn vi f trn tp hun luyn

    (h c gi l nht qun vi f trn tp mu) E.g., khp ng cong:

    Ockhams razor: u tin nhng gi thit no xp

    x tt hm mc tiu v cng n gin cng tt

  • 8/14/2019 Chuong7 AI

    15/89

    Hc cc cy quyt nh

    Bi ton: Hc xem khi no th nn ngi bn i timt restaurant:1. Alternate: C restaurant no cnh y khng?2. Bar: Liu c khu vc quy bar c th ngi khng?3. Fri/Sat: hm nay l th 8 hay th 7?

    4. Hungry: c ang i khng?5. Patrons: S ngi trong restaurant (None, Some,Full)

    6. Price: khong gi ($, $$, $$$)7. Raining: ngoi tri c ma khng?

    8. Reservation: t trc cha?9. Type: loi restaurant (French, Italian, Thai, Burger)10. WaitEstimate: thi gian ch i (0-10, 10-30, 30-

    60, >60)

  • 8/14/2019 Chuong7 AI

    16/89

    Biu din thuc tnh gi tr Cc mu c biu din bng cc thuc tnh v gi tr(Boolean,

    discrete, continuous)

    Nhim v t ra l phn loi xem trng hp no trong tng lai l

    positive (T) hay negative (F)

  • 8/14/2019 Chuong7 AI

    17/89

    Cy quyt nh

    Biu din gi thit cn hc. V d:

  • 8/14/2019 Chuong7 AI

    18/89

    Kh nng biu din Cy quyt nh c kh nng dng biu din bt c hm no.

    E.g. hm Boolean:

    Vi mt cy quyt nh nht qun vi tp mu hun luyn th miinput, output ca hm tng ng vi mt ng i trong cy.Nhng cng c th kh nng khi qut ho khng cao i vi cc vd mi cha bit.

    u tin tm cy c phc tp nh.

  • 8/14/2019 Chuong7 AI

    19/89

    Khng gian gi thuyt

    S lng cy quyt nh cho hm Boolean == S lng hm boolean

    = s lng bng lun vi 2n hng = 22n

    E.g., nu c 6 thuc tnh Boolean, c18,446,744,073,709,551,616 cy

  • 8/14/2019 Chuong7 AI

    20/89

    Thut ton hc cy quyt nh Mc ch: Tm cy nh nht qun vi tp mu hun luyn.

    tng: Tm kim heuristic chn thuc tnh quan trng nht phn tch ( quy)

  • 8/14/2019 Chuong7 AI

    21/89

    Chn thuc tnh

    tng: chn thuc tnh (gi tr) sao cho sao cho n gip

    phn tch tp mu thanh hai tp thun khit (ch c positivehay ch c negative).

    Patrons?l la chn tt hn

  • 8/14/2019 Chuong7 AI

    22/89

    S dng l thuyt thng tin

    ci tChoose-Attribute

    trong thut tonDTL:

    Lng thng tin (Entropy):

    I(P(v1), , P(vn)) = i=1 -P(vi) log2 P(vi)

    i vi tp cp mu positive v n negative:

    np

    n

    np

    n

    np

    p

    np

    p

    np

    n

    np

    pI

    ++

    ++=

    ++ 22loglog),(

  • 8/14/2019 Chuong7 AI

    23/89

    Li thng tin (Information gain)

    chn thuc tnhA chia tp hun luyn Ethnh cc tpcon E1, , Ev tnh theo gi tr caA, v gi sA c vgi tr khc nhau.

    Li thng tin (IG) l gim trong entropy trong vic testthuc tnh:

    Chn thuc tnh c IG ln nht

    = ++++

    =

    v

    i ii

    i

    ii

    iii

    np

    n

    np

    p

    Inp

    np

    Aremainder1

    ),()(

    )(),()( Aremaindernp

    n

    np

    pIAIG ++=

  • 8/14/2019 Chuong7 AI

    24/89

    Li thng tin (Information gain)

    Trong tp mu ca v d, p = n = 6, I(6/12, 6/12) = 1 bit

    Xt thuc tnh Patrons v Type (v cc thuc tnh khc):

    Patrons c gi tr IG cao nht nn c DTL chn lm gcca cy quyt nh.

    bits0)]

    4

    2,

    4

    2(

    12

    4)

    4

    2,

    4

    2(

    12

    4)

    2

    1,

    2

    1(

    12

    2)

    2

    1,

    2

    1(

    12

    2[1)(

    bits0541.)]6

    4,

    6

    2(

    12

    6)0,1(

    12

    4)1,0(

    12

    2[1)(

    =+++=

    =++=

    IIIITypeIG

    IIIPatronsIG

  • 8/14/2019 Chuong7 AI

    25/89

    Li thng tin (Information gain) Cy quyt nh hc bi DTL t 12 v d:

    Nh hn cy quyt nh a ra lc u

  • 8/14/2019 Chuong7 AI

    26/89

    Khi no hc tt?

    Lm sao chc rng h f?

    s dng cc kt qu trong thng k v hc thng k. Th h trn tp v d mi (test set)

    Learning curve = % S lng on ng trn tp test khi kch thctp hun luyn tng ln.

  • 8/14/2019 Chuong7 AI

    27/89

    c thm

    Gio trnh: chng 18 (phn 1-3).

    MIT Open courseware: ch5, ch6, ch7.

    T. Mitchell, Machine Learning, McGraw-Hill.

    J.R. Quinlan, C4.5: Programs for MachineLearning, Morgan Kaufmann.

  • 8/14/2019 Chuong7 AI

    28/89

    Cu hi n tp

    1. nh ngha vic hc?2. Cho bit cc loi hc khc nhau?

    3. Cho bit cc dng hc trong hc my?

    4. Cu trc cy quyt nh?5. Ci t thut ton DTL.

    6. Dng C4.5, hoc thut ton DTL gii ccbi ton v Data Mining.

  • 8/14/2019 Chuong7 AI

    29/89

    PERCEPTRON N LP

  • 8/14/2019 Chuong7 AI

    30/89

    Cu trc Perceptron

    W

    w1 1, w1 2, w1 R,w2 1, w2 2, w2 R,

    wS 1, wS 2, wS R,

    =

    wi

    wi 1,wi 2,

    wi R,

    = W

    wT

    1

    wT

    2

    wT

    S

    =

    ai hardlim ni( ) hardlim wT

    i p bi+( )= =

  • 8/14/2019 Chuong7 AI

    31/89

    Perceptron n lp mt u ra

    a hardlim wT

    1 p b+( ) hardlim w1 1, p1 w1 2, p2 b+ +( )= =

    w 1 1, 1= w 1 2, 1= b 1=

  • 8/14/2019 Chuong7 AI

    32/89

    Bin quyt nh

    wT

    1

    p b+ 0= wT

    1

    p b=

    Tt c cc im trn bin quyt nh c cng tch vhng vi vector trng s.

    Tt c khi chiu ln vector trng s u quy v mt im.

    Ni khc i chng nm trn ng thng vung gc vivector trng s.

    V d h OR

  • 8/14/2019 Chuong7 AI

    33/89

    V d hm - OR

    p10

    0= t1 0=,

    p20

    1= t2 1=,

    p31

    0= t3 1=,

    p41

    1= t4 1=,

  • 8/14/2019 Chuong7 AI

    34/89

    Li gii cho bi ton phn lp OR

    w1

    0.5

    0.5=

    wT

    1 p b+ 0.5 0.50

    0.5b+ 0.25 b+ 0= = = b 0.25=

    Siu phng bin phi vung gc vi vector trng s.

    Ly mt im bt k trn siu phng bin tnh gi tr ca bias.

  • 8/14/2019 Chuong7 AI

    35/89

    Perceptron n lp nhiu u ra

    Mi mt neuron c mt siu phng bin ring.

    wT

    i p bi+ 0=

    Mi neuron c th dng phn tch hai lp.

    Do nu n-neuron u ra th c th dng phn

    tch 2n lp.

    L h d

  • 8/14/2019 Chuong7 AI

    36/89

    Lut hc qua v d

    p1 t1{ , } p2 t2{ , } pQ tQ{ , }, , ,

    p11

    2= t1 1=,

    p21

    2= t2 0=,

    p30

    1= t3 0=,

  • 8/14/2019 Chuong7 AI

    37/89

    Khi to ban u

    w11.0

    0.8=

    np p1 vo mng neural:

    a hardlim wT

    1 p1( ) hardlim 1.0 0.81

    2 = =

    a hardlim 0.6( ) 0= =

    Khi to ngu nhin:

    Phn sai lp.

  • 8/14/2019 Chuong7 AI

    38/89

    LUT HC t

    1w to p

    1

    Khng n nh

    cngp1

    vo1w

    Ift 1 and a 0, then w1ne w

    w1old

    p+== =

    w1new

    w1ol d

    p1+1.0

    0.8

    1

    2+ 2.0

    1.2= = =

    Ta c lut:

    V t th h i

  • 8/14/2019 Chuong7 AI

    39/89

    Vector mu th hai

    Ift 0 and a 1, then w1 ne w w1 old p== =

    a hardlim wT

    1p

    2( ) hardlim 2.0 1.2

    1

    2

    = =

    a ha rdlim 0.4( ) 1= = (Phn lp sai)

    Ta c lut hc:

    w1ne w

    w1ol d

    p22.0

    1.2

    1

    2

    3.0

    0.8= = =

    V h b

  • 8/14/2019 Chuong7 AI

    40/89

    Vector mu th ba

    Siu phng phn lp chnh xc.

    a hardlim wT

    1 p3( ) hardlim 3.0 0.80

    1

    = =

    a ha rdlim 0.8( ) 1= = (Phn lp sai)

    w1ne w

    w1ol d

    p33.0

    0.8

    0

    1 3.0

    0.2= = =

    Ift a, then w1ne w

    w1o ld

    .==

    L t h th ht

  • 8/14/2019 Chuong7 AI

    41/89

    Lut hc thng nht

    Ift 1 and a 0, then w1ne w

    w1old

    p+== =

    Ift 0 and a 1, then w1

    n eww

    1

    oldp== =

    Ift a, then w1

    n eww

    1

    ol d==

    e t a=

    Ife 1, then w1ne w

    w1old

    p+==

    Ife 1, then w1ne w

    w1old

    p==

    Ife 0, then w1ne w

    w1old

    ==

    w1new

    w1ol d

    e p+ w1ol d

    t a( )p+= =

    bne w

    bol d

    e+=

    ch : biastng ngvi u vo c

    kt nitrng s =1.

  • 8/14/2019 Chuong7 AI

    42/89

    Perceptron n lp nhiu u ra

    winew

    wiold

    e ip+=

    bine w

    biol d

    ei+=

    Wne w

    Wol d

    epT

    +=

    bnew

    bol d

    e+=

    Update dng th i ca ma trn trng s:

    Dng ma trn:

  • 8/14/2019 Chuong7 AI

    43/89

    V d t ng phn loi To/Chui

    W 0.5 1 0.5= b 0.5=

    a hardlim Wp1 b+( ) hardlim 0.5 1 0.51

    1

    1

    0.5+

    = =

    Tp hun luyn (ba thuc tnh: Shape, Texture,

    Weight)

    Trng s khi to

    Ln lp u tin

    p1

    1

    1

    1

    t1, 1= =

    p2

    1

    1

    1

    t2, 0= =

    a hardlim 0.5( ) 0= =

    Wne w

    Wol d

    epT

    + 0.5 1 0.5 1( ) 1 1 1+ 0.5 0 1.5= = =

    bne w

    bol d

    e+ 0.5 1( )+ 1.5= = =

    e t1 a 1 0 1= = =

  • 8/14/2019 Chuong7 AI

    44/89

    Ln lp th hai

    a hardlim Wp2 b+( ) hardlim 0.5 0 1.511

    1

    1.5( )+( )= =

    a hardlim 2.5( ) 1= =

    e t2 a 0 1 1= = =

    Wne w

    Wold

    e pT

    + 0.5 0 1.5 1( ) 1 1 1+ 1.5 1 0.5= = =

    bne w

    bol d

    e+ 1.5 1( )+ 0.5= = =

  • 8/14/2019 Chuong7 AI

    45/89

    Kim tra

    a hardl im Wp1 b+( ) hardlim 1.5 1 0.511

    1

    0.5+( )= =

    a hardlim 1.5( ) 1 t1= = =

    a hardl im Wp2 b+( ) hardlim 1.5 1 0.5

    1

    1

    1

    0.5+( )= =

    a hardlim 1.5( ) 0 t2= = =

  • 8/14/2019 Chuong7 AI

    46/89

    nh L hi t cho Perceptron

    1. Kh tch tuyn tnh: Hai tp im A v B trong khng gianvector X n-chiu c coi l kh tch tuyn tnh nu tn tin+1 s thc w1, ..., wn sao cho vi mi x=(x1,x2,...,xn)A tho

    mn wx wn+1 v vi mi y=(y1, y2,..,yn) B tho mn wy wn+1 v vi mi y=(y1, y2,..,yn) B tho mnwy

  • 8/14/2019 Chuong7 AI

    47/89

    nh L hi t cho Perceptronnh l (cho perceptron n lp mt u ra): Nu hai tp P v

    N l hu hn v kh tch tuyn tnh th lut ton hcPerceptron s hi t (c ngha l tw s ch c update mt shu hn ln).

    Chng minh:i) t P'=PN' trong N' gm nhng phn t khng thuc N.ii) Cc vector thuc P' c th chun ho (chun bng 1) v nutn ti w sao cho wx > 0 (vi mi x P') th x > 0 vi mi iii) Vector c th chun ho. Do gi thit l siu phng bin

    tn ti, nn phi c vector li gii c chun ho w*.

    h L hi t h P t

  • 8/14/2019 Chuong7 AI

    48/89

    nh L hi t cho PerceptronChng minh (tip): Gi s thut ton chy c t+1 bc, w(t+1) cupdate. C ngha l ti bc t tn ti vectorpi b phn lp sai (c th lp

    lun tng t trong trng hp vector b phn lp sai l ni). w(t+1)=w(t)+pi (1)Cosine ca gc gia w v w* l:

    cos =(w*. w(t+1))/(||w*||.||w(t+1)||) =(w*. w(t+1))/(||w(t+1)||) (2)Th (1) vo t s ca (2) ta c:

    w*.w(t+1)=w*(w(t)+pi)=w*. w(t)+w*.pi w*. wt + trong = min{w*.p / pP'}.

    Do bng quy np ta c: w*. w(t+1) w*. w(0) + (t+1) (3)Mt khc xt mu s ca (2):||w(t+1)||2=(w(t)+pi)(w(t)+pi)=||w(t)||2+2w(t).pi+||pi||2

    Do w(t).pi l s m hoc bng 0 (do mi phi update w(t))w(t+1) ||w(t)||2+||pi||2 ||w(t)||2+1 ||w(0)||2+(t+1) (4)Kt hp (3) v (4) ta c:cos (w*. w(0)+(t+1))/sqrt( ||w(0)||2+(t+1))

    V phi tng t l vi sqrt(t) (do > 0) do t bt buc phi hu hn (v

    cos 1). Kt thc chng minh.

    Ci ti th t t h P t

  • 8/14/2019 Chuong7 AI

    49/89

    Ci tin thut ton hc Perceptron

    Mc d nh l hi t m bo tnh dng ca thut ton hcPerceptron, tuy nhin trong thc t s ln lp c th rt ln

    (thm ch l hm s m vi u vo).2. Corrective Learning (perceptron mt u ra): = e.w(t).pi (e=yi-ti)

    w(t+1)= w (t)+ ((+).pi)/||pi||Mi sample b phn lp sai c th hiu chnh li trong mt bc

    phn lp ng. V d nu pi P b phn lp sai (w(t).pi0.

    Ci ti th t t h P t

  • 8/14/2019 Chuong7 AI

    50/89

    Ci tin thut ton hc Perceptron

    2. Thut gii hc Pocket (Gallant, 1990):

    Trong thc t tp d liu khng phi lc no cng kh tch tuyntnh mt cch hon ho. Do cn lu gi vector trng s (hay matrn trng s) t mc phn lp tt nht.Gii thut:(perceptron mt u ra)

    Bc khi to: Khi tr vectorw ngu nhin. t ws=w (ws lvector lu tr), hs=0 (hs l s vector phn lp thnh cng lin tip).Bc lp: Udate w s dng lut hc Perceptron. Dng bin h ghili s ln phn lp thnh cng lin tip. Nu h>hs th thay ws bng w

    v hs thay bng h. Tip tc lp.(Gallant, 1990) chng minh rng nu tp training l hu hn v ccvector u vo cng nh trng s l hu t th thut ton s hi tti li gii ti u vi xc sut bng 1.

  • 8/14/2019 Chuong7 AI

    51/89

    Hn ch ca Perceptron n lp

    wT

    1 p b+ 0=

    Bin quyt nh l tuyn tnh

    Khng dng uc i vi cc bi ton khng kh tch tuyn tnh

    Hm XOR

    c thm

  • 8/14/2019 Chuong7 AI

    52/89

    c thm M.T. Hagan, H.B. Demuth, and M. Beale, Neural

    Network Design, PWS Publishing. N.J. Nilson, Mathematical Foundations of

    Learning Machines, Morgan Kaufmann.

    Cu Hi n Tp

  • 8/14/2019 Chuong7 AI

    53/89

    Cu Hi n Tp1. Nu cu trc v lut hc ca mng Perceptron?

    2. Chng minh nh l hi t ca mng Perceptron?3. Ly cc v d v m phng Perceptron trong MatLab?

  • 8/14/2019 Chuong7 AI

    54/89

    PERCEPTRON A LP

    Ni dung: Cu trc mng Perceptron a lp. Thut gii lan truyn ngc (BP). nh L Kolmogorov v phc tp hc. Mt s Heuristics cho vic ci tin BP.

    P t L

  • 8/14/2019 Chuong7 AI

    55/89

    Perceptron a Lp

    R S1

    S2

    S3

    Network

  • 8/14/2019 Chuong7 AI

    56/89

    V d

    C bi t i h

  • 8/14/2019 Chuong7 AI

    57/89

    Cc bin quyt inh

    Mng con th nht

    Bin th nht:a1

    1 hardlim 1 0 p 0.5+( )=

    Bin th hai:

    a21

    hardlim 0 1 p 0.75+( )=

    C Bi Q t h

  • 8/14/2019 Chuong7 AI

    58/89

    Cc Bin Quyt nhBin th ba:

    Bin th t:

    Mng con th hai

    a31 hardlim 1 0 p 1.5( )=

    a41

    hardlim 0 1 p 0.25( )=

    M t h

  • 8/14/2019 Chuong7 AI

    59/89

    Mng tng hp

    W1

    1 0

    0 1

    1 0

    0 1

    = b1

    0.5

    0.751.5

    0.25

    =

    W2 1 1 0 0

    0 0 1 1

    = b2 1.5

    1.5

    =

    W3

    1 1= b3

    0.5=

    X X H

  • 8/14/2019 Chuong7 AI

    60/89

    Xp X Hm

    f1

    n( ) 11 e

    n+

    -----------------=

    f2

    n( ) n=

    w1 1,1

    10= w 2 1,1

    10= b11

    10= b21

    10=

    w1 1,2

    1= w1 2,2

    1= b2

    0=

    Gi tr cc tham s

  • 8/14/2019 Chuong7 AI

    61/89

    th "hm" ca mng

    -2 -1 0 1 2-1

    0

    1

    2

    3

    Th i i h

  • 8/14/2019 Chuong7 AI

    62/89

    Thay i gi tr cc tham s

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    1 w 1 1,2

    1

    1 w1 2,2

    1

    0 b21

    20

    1 b2

    1

    M L

  • 8/14/2019 Chuong7 AI

    63/89

    Mng a Lp

    a

    m 1+

    f

    m 1+

    W

    m 1+

    a

    m

    b

    m 1+

    +( )= m 0 2 M 1, , ,=

    a0

    p=

    a aM

    =

    H Li

  • 8/14/2019 Chuong7 AI

    64/89

    Hm Li

    p1 t1{ , } p2 t2{ , } pQ tQ{ , }, , ,

    Tp hun luyn

    F x( ) E e2 ][= E t a( )2 ][=

    MSE

    F x( ) E eT

    e ][= E t a( )T

    t a( ) ][=Dng Vector

    F x( )

    t k( )

    a k( )

    ( )

    Tt k( )

    a k( )

    ( )e

    Tk

    ( )e k

    ( )= =

    Xp x MSE

    w i j,m

    k 1+( ) wi j,m

    k( ) F

    w i j,m

    ------------= bim

    k 1+( ) bim

    k( ) F

    bim

    ---------=

    Approximate Steepest Descent

    o Hm Hm Hp

  • 8/14/2019 Chuong7 AI

    65/89

    o Hm Hm Hpf n w( )( )d

    wd-----------------------

    f n( )dnd

    --------------n w( )d

    wd---------------

    =

    f n( ) n( )cos= n e 2w= f n w( )( ) e2w( )cos=

    f n w( )( )dwd

    -----------------------f n( )d

    nd--------------

    n w( )dwd

    --------------- n( )sin( ) 2e 2w( ) e2w( )sin( ) 2e2w( )= = =

    V d

    Tnh Gradient

    F

    w i j,m

    ------------

    F

    nim

    ---------ni

    m

    wi j,m

    ------------= F

    bim

    ---------F

    nim

    ---------ni

    m

    bim

    ---------=

    TNH GRADIENT

  • 8/14/2019 Chuong7 AI

    66/89

    TNH GRADIENT

    ni

    mw

    i j,

    ma

    j

    m 1

    j 1=

    Sm 1

    b

    i

    m+=

    nim

    wi j,m

    ------------ ajm 1

    =ni

    m

    bim

    --------- 1=

    sim F

    nim

    ---------

    nhy

    Fw i j,

    m------------ si

    maj

    m 1=

    F

    bim

    --------- si

    m=

    Gradient

    Steepest Descent

  • 8/14/2019 Chuong7 AI

    67/89

    Steepest Descent

    wi j,m

    k 1+( ) wi j,m

    k( ) sim

    ajm 1

    = bim

    k 1+( ) bim

    k( ) sim

    =

    Wm

    k 1+( ) Wm

    k( ) sm

    am 1

    ( )T

    = bm

    k 1+( ) bm k( ) sm=

    sm F

    nm

    ----------

    Fn1

    m---------

    F

    n2m

    ---------

    F

    nS

    mm

    -----------

    =

    Bc tip theo: Tnh nhy (Backpropagation)

    Ma trn Jacobian

  • 8/14/2019 Chuong7 AI

    68/89

    Ma trn Jacobian

    nm 1+

    nm

    -----------------

    n1m 1+

    n1m----------------

    n1m 1+

    n2m----------------

    n1m 1+

    nS

    mm----------------

    n2m 1+

    n1m

    ----------------

    n2m 1+

    n2m

    ----------------

    n2m 1+

    nS

    mm

    ----------------

    nSm 1+m 1+

    n1m

    ----------------

    nSm 1+m 1+

    n2m

    ----------------

    nSm 1+m 1+

    nS

    mm

    ----------------

    nim1+

    nj

    m----------------

    wi l,

    m 1+al

    m

    l 1=

    Sm

    bi

    m 1++

    njm

    ----------------------------------------------------------- wi j,m 1+ aj

    m

    nj

    m---------= =

    fm

    njm( )

    fm

    njm( )

    njm

    ---------------------=

    F' m

    nm

    ( )

    fm n1m( ) 0 0

    0 fm

    n2m

    ( ) 0

    0 0 fm

    nSm

    m

    ( )

    =n

    m 1+

    nm

    ----------------- Wm 1+

    F'mn

    m( )=

    nim 1+

    njm

    ---------------- wi j,

    m 1+ fm

    njm( )

    njm

    --------------------- wi j,

    m 1+f'm n

    j

    m( )= =

  • 8/14/2019 Chuong7 AI

    69/89

    Backpropagation (Sensitivities)

    sm Fn

    m---------- n

    m 1+

    n

    m

    -----------------

    T

    Fn

    m 1+----------------- Fm nm( ) W m 1+( ) T F

    nm 1+

    -----------------= = =

    sm

    Fm

    nm

    ( ) Wm 1+

    ( )T

    sm 1+

    =

    nhy c tnh t tng cui cng vlan truyn ngc li cho n tng u.

    sM

    sM 1

    s2

    s1

    Khi u (Last Layer)

  • 8/14/2019 Chuong7 AI

    70/89

    Khi u (Last Layer)

    siM F

    niM

    ----------t a( )T t a( )

    niM

    ---------------------------------------tj aj( )

    2

    j 1=

    SM

    ni

    M----------------------------------- 2 ti ai( )

    ai

    niM

    ----------= = = =

    sM

    2FM

    nM

    ( ) t a( )=

    aini

    M---------- ai

    M

    ni

    M---------- f

    M

    n i

    M

    ( )ni

    M

    ----------------------- fM n iM( )= = =

    si

    M2 t

    i

    ai

    ( ) fM

    ni

    M( )=

    Tng kt thut ton

  • 8/14/2019 Chuong7 AI

    71/89

    Tng kt thut ton

    am 1+

    fm 1+

    Wm 1+

    am

    bm 1+

    +( )= m 0 2 M 1, , ,=

    a0

    p=

    a aM

    =

    sM

    2FM

    nM

    ( ) t a( )=

    s

    m

    F

    m

    n

    m

    ( ) W

    m 1+

    ( )

    T

    s

    m 1+

    = m M 1 2 1, , ,=

    Wm

    k 1+( ) Wm

    k( ) sm

    am 1

    ( )T

    = bm

    k 1+( ) bm

    k( ) sm

    =

    Lan truyn Xui

    Lan truyn ngc

    Cp nht trng s

  • 8/14/2019 Chuong7 AI

    72/89

    V d: Regression

    g p( ) 1 4---p

    sin+=

    1-2-1

    Network

    +

    -

    t

    a

    ep

  • 8/14/2019 Chuong7 AI

    73/89

    Network

    1-2-1Network

    ap

    Khi to ban u

  • 8/14/2019 Chuong7 AI

    74/89

    Khi to ban uW

    10( ) 0.27

    0.41

    = b1

    0( ) 0.48

    0.13

    = W2

    0( ) 0.09 0.17= b2

    0( ) 0.48=

    Network ResponseSine Wave

    -2 -1 0 1 2-1

    0

    1

    2

    3

    L T X i

  • 8/14/2019 Chuong7 AI

    75/89

    Lan Truyn Xuia

    0p 1= =

    a1

    f1

    W1

    a0

    b1

    +( ) logsig 0.270.41

    10.48

    0.13+

    logsig 0.75

    0.54

    = = =

    a1

    1

    1 e0.75

    +--------------------

    1

    1 e0.54

    +--------------------

    0.321

    0.368= =

    a2

    f2

    W2

    a1

    b2

    +( ) purelin 0.09 0.170.321

    0.3680.48+( ) 0.446= = =

    e t a 14---p

    sin+

    a2

    14--- 1

    sin+

    0.446 1.261= = = =

    o hm hm chuyn

  • 8/14/2019 Chuong7 AI

    76/89

    o hm hm chuyn

    f1

    n( )nd

    d 1

    1 en

    +-----------------

    en

    1 en

    +( )2

    ------------------------ 11

    1 en

    +-----------------

    1

    1 en

    +-----------------

    1 a1( ) a1( )= = = =

    f2

    n( )nd

    dn( ) 1= =

    L T N

  • 8/14/2019 Chuong7 AI

    77/89

    Lan Truyn Ngc

    s2 2F

    2

    n2( ) t a( ) 2 f2 n2( ) 1.261( ) 2 1 1.261( ) 2.522= = = =

    s1

    F1

    n1

    ( ) W2( )

    Ts

    2 1 a11( ) a11( ) 0

    0 1 a21

    ( ) a21( )

    0.09

    0.172.522= =

    s1 1 0.321( ) 0.321( ) 0

    0 1 0.368( ) 0.368( )

    0.09

    0.172.522=

    s1 0.218 0

    0 0.233

    0.227

    0.429

    0.0495

    0.0997= =

    Cp nht trng s

  • 8/14/2019 Chuong7 AI

    78/89

    Cp nht trng s

    W2

    1( ) W 2 0( ) s2 a1( )T

    0.09 0.17 0.1 2.522 0.321 0.368= =

    0.1=

    W2

    1( ) 0.171 0.0772=

    b2

    1( ) b2 0( ) s2 0.48 0.1 2.522 0.732= = =

    W1 1( ) W1 0( ) s 1 a 0( )T

    0.270.41

    0.1 0.04950.0997

    1 0.2650.420

    = = =

    b1

    1( ) b1 0( ) s1 0.480.13

    0.1 0.0495

    0.0997 0.475

    0.140= = =

    La chn Cu trc mng

  • 8/14/2019 Chuong7 AI

    79/89

    La chn Cu trc mngg p( ) 1 i

    4----- p

    sin+=

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    1-3-1 Network

    i = 1 i = 2

    i = 4 i = 8

    La chn cu trc mng

  • 8/14/2019 Chuong7 AI

    80/89

    La chn cu trc mngg p( ) 1 6

    4------ p

    sin+=

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    1-5-1

    1-2-1 1-3-1

    1-4-1

    Hi t

  • 8/14/2019 Chuong7 AI

    81/89

    Hi t

    g p( ) 1 p( )si n+=

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    1

    23

    4

    5

    0

    1

    2

    34

    5

    0

    Hi t n cc tr ton cc Hi t n cc tr a phng

    Khi qut ho

  • 8/14/2019 Chuong7 AI

    82/89

    Khi qut ho

    p1 t1{ , } p2 t2{ , } pQ tQ{ , }, , ,

    g p( ) 14---p

    sin+= p 2 1.6 1.2 1.6 2, , , , ,=

    -2 -1 0 1 2-1

    0

    1

    2

    3

    -2 -1 0 1 2-1

    0

    1

    2

    3

    1-2-1 1-9-1

    nh L Kolmogov v Phc Tp

  • 8/14/2019 Chuong7 AI

    83/89

    g pHc

    Bi ton s 13 ca David Hilbert "Nghim ca a th bc7 khng th biu din bng chng hm ca cc hm 2bin c th l a thc sau y: f7+xf3+yf2+zf+1=0 khngth gii c bng cc hm hai bin".

    V d v chng hm hai bin gii phng trnh bc 2.

    nh L Kolmogov v Phc Tp Hc

  • 8/14/2019 Chuong7 AI

    84/89

    nh L Kolmogov v Phc Tp Hc

    Nm 1957, Kolmogorov (Arnold, Lorenz) chng minh githit a ra trong bi ton ca Hilbert l sai. Thm chchng minh kt qu mnh hn: mi hm lin tc ubiu din c bng chng cc hm mt bin ch dngphp ton nhn v cng.

    nh L Kolmogorov: f:[0,1]n[0,1] l hm lin tc th tnti cc hm mt bin g, hi i=1,2,..,2n+1 v cc hng s isao cho:

    f(x1,x2,...,xn)= j=1,2n+1g( i=1,n ihj(xi))nh l cho mng Neural (Baron, 1993):Mng Perceptron hng tin mt lp n dng hmchuyn sigmoid c th xp x bt c hm kh tch Lbe

    no trn khong [0,1]

    nh L Kolmogov v Phc Tp Hc

  • 8/14/2019 Chuong7 AI

    85/89

    nh L Kolmogov v Phc Tp Hc

    Mc d vy cc nh l ch a ra s tn ti m khng

    a ra c thut ton cho vic xc nh cu trc mng(s neuron trong tng n) hay cc trng s.

    nh l NP v hc cho mng Neural (Judd, 1990):

    Bi ton tm cc trng s ti u cho mng Neural a lp

    c hm chuyn hardlims l NP y .Lu :

    - do thut ton BP khng m bo tm c nghimti u, thm ch khng m bo s hi t.

    -Vic xc nh cu trc mng v mt s yu t ca thutton hc cn mang tnh kinh nghim, Heuristic.

    Mt s Heuristics cho BP

  • 8/14/2019 Chuong7 AI

    86/89

    Cp nht theo ch tun t (online) hay batch(epoch): Thng vic hc theo ch tun t gip BP hi t nhanh hn,c bit khi d liu ln v d tha.

    Chun ho gi tr u ra:m bo gi tr u ra nm trong min gi tr ca hm chuyn trn

    cc neuron u ra tng ng (thng l nm trong khong[a+, b-]. Chun ho gi tr u vo:m bo gi tr trung bnh gn 0 hoc nh so vi lch tiu chun

    (stdev). Cc gi tr tt nht phi c lp vi nhau.Khi to gi tr trng s:Uniform random in [-, ]; [-, -][ , ] Kt thc sm:

    Khi lin tip n epoch training m khng c s ci thin ng k li

    Mt s Heuristics cho BP

  • 8/14/2019 Chuong7 AI

    87/89

    Mt s Heuristics cho BP Tc hc:

    Tc hc ca cc Neuron nn u nhau v vy, neuron tng sau(thng c gradient ln hn tng trc) nn c tc hc nh hntng trc, Neuron c t input nn c tc hc ln hn Neuron cnhiu input.

    Kim tra cho (crossvalidation):

    Tch tp d liu ra lm hai tp c lp (training and testing). T lthng l 2/3:1/3. Thc hin vic hc trn tp training v kim trakh nng khi qut ho ca mng trn tp testing.

    Lut phn lp ti u:

    Dng M neuron u ra cho bi ton phn M lp s dng lut cnhtranh winner-take-all.

    Xc nh s neuron lp n:

    Cc c lng cn th (s lng d liu, chiu VC). Phng php:Incremental, Decremental.

    c thm

  • 8/14/2019 Chuong7 AI

    88/89

    M.T. Hagan, H.B. Demuth, and M. Beale, Neural

    Network Design, PWS Publishing. Gio trnh, chng 19. MIT Courseware: ch8, ch9.

    Cu Hi n tp

  • 8/14/2019 Chuong7 AI

    89/89

    Cu Hi n tp

    1. Trnh by cu trc mng Neuron Perceptron a

    lp?

    2. Trnh by gii thut hc lan truyn ngc choMLP.

    3. Trnh by nh l Kolmogorov v ng dng choMLP.

    4. Ci t thut gii BP cho MLP.

    5. ng dng MLP gii cc bi ton nh:Classification v Regression.