Sentiment classification using tree‐based gated recurrent units

BOOKSPINE ii                            Sen imen Classi ica ionUsingT ee‐BasedGa ed Recu en Uni s VasileiosTsakalos Disse a ionp esen edaspa ial equi emen  o ob aining heMas e ’sdeg eeinIn o ma ionManagemen     Sen imen Classi ica ion Using T ee-Based Ga ed Recu en Uni s Copy igh © Vasileios Tsakalos, NOVA In o ma ion Managemen School, NOVA Uni- e si y o Lisbon. The NOVA In o ma ion Managemen School and he NOVA Uni e si y o Lisbon ha e he igh , pe pe ual and wi hou geog aphical bounda ies, o ile and publish his dis- se a ion h ough p in ed copies ep oduced on pape o on digi al o m, o by any o he means known o ha may be in en ed, and o dissemina e h ough scien i ic eposi o ies and admi i s copying and dis ibu ion o non-comme cial, educa ional o esea ch pu poses, as long as c edi is gi en o he au ho and edi o . This documen was c ea ed using he (pd )L A T EX p ocesso , based in he “no a hesis” empla e[1], de eloped a he Dep. In o má ica o FCT-NOVA [2]. [1] h ps://gi hub.com/joaomlou enco/no a hesis [2] h p://www.di. c .unl.p Acknowledgemen s I would like o hank my supe iso p o esso , D . Robe o Hen iques, o helping me s uc u e he epo , ad ising me wi h ega ds o he ma hema ically complexi y e- qui ed. Mo eo e I would like o hank my b o he , E angelos Tsakalos, o p o iding me wi h he compu a ional powe o un he expe imen s and ad ising me ega ding he subjec o my mas e hesis. Abs ac Na u al Language P ocessing is one o he mos challenging ields o A i icial In elli- gence. The pas 10 yea s, his ield has wi nessed a ascina ing p og ess due o Deep Lea ning. Despi e ha , we ha en’ achie ed o build an a chi ec u e o models ha can unde s and na u al language as humans do. Many a chi ec u es ha e been p o- posed, each o hem ha ing i s own s eng hs and weaknesses. In his epo , we will co e he ee based a chi ec u es and in pa icula we will p opose a di e en ee based a chi ec u e ha is e y simila o he T ee-Based LSTM, p oposed by Tai(2015). In his wo k, we aim o make a c i ical compa ison be ween he p oposed a chi ec- u e - T ee-Based GRU - wi h T ee-based LSTM o sen imen classi ica ion asks, bo h bina y and ine-g ained. Keywo ds: Deep Lea ning, Na u al Language P ocessing, Recu si e Neu al Ne wo ks, Sen imen Classi ica ion ii Resumo ix Chap e 1 In oduc ion 1.1 Mo i a ion This pape aims o con ibu e o he A i icial In elligence communi y by p oposing a di e en a chi ec u e(T ee-based GRU 3.2.6) and p esen ing i s esul s in compa - ison o T ee-Based LSTM [77](3.2.5). The conduc ion o his expe imen is done as GRU a chi ec u e is less complica ed and has less pa ame e s o compu e han LSTM. The e o e, we hypo hesize ha i is as e o ain. GRU is a new app oach, i is no de e mined whe he i is be e han LSTM o no [10], so a i is assumed ha he compa ison be ween hose wo models is like a compa ison be weem non-linea ac i- a ion unc ions, he e is no "bes " unc ion bu some non-linea i ies sui be e some p oblems. 1.2 O e iew o Thesis This hesis consis s o 5 chap e s. The i s chap e , he in oduc ion, p o ides he eade wi h he necessa y backg ound o be able o ead his epo . The second chap- e (2), wo d embeddings, is abou he ep esen a ion o he wo ds on he ec o space. On he second chap e we will go h ough he wo d embeddings bene i s and he mos e icien algo i hms ha a e used o achie e his ans o ma ion ( om wo ds, o ec o s). I is impo an o he eade o be awa e o he ac ha wo d embeddings a e he inpu o he T ee-based GRU (and e e y o he language model ha we co e in his epo ). The hi d chap e (3), eedback neu al ne wo ks, makes an in dep h commen a y o he eedback neu al ne wo ks and i s mos common a chi ec u es. The o h chap e (4), ne wo k aining, goes h ough he g adien descen algo i hm, i s di e en a ian s and ex ensions bu also co e s he p ope ies o he neu al ne wo k’s 1 CHAPTER 1. INTRODUCTION hype pa ame e s. Finally, he i h chap e (5), expe imen s, demons a es he com- pa ison be ween T ee-based GRU and T ee-based LSTM, i also desc ibes he g adien descen a ian s and he hype pa ame e s ha we e selec ed o he aining o he model. 1.3 Backg ound This sec ion p o ides he essen ial backg ound on sen imen classi ica ion, sequences, syn ac ic s uc u es, and neu al ne wo ks. 1.3.1 Sen imen Classi ica ion and Sequences Sen imen analysis/classi ica ion [59] (also known as opinion mining) is he classi ica- ion on whe he a piece o ex is posi i e, nega i e o neu al using NLP, s a is ics, o machine lea ning me hods. A sequence is a s ing o objec s. Each sequence is a ow o i em se s.The indi idual elemen s in a sequence a e also called e ms. In he case o he wo d sequences, a wo d co esponds o an i em. In he case o he heal h ca e da a, a es alue is an i em. T ea ing da a as sequen ial (when hey a e sequences) imp o e he p edic ion accu acy o he classi ie s [50]. 1.3.2 Syn ac ic S uc u e The sen ences can be desc ibed wi h wo ways o a machine o make sense ou o hem, he i s one is by b eaking up he sen ence o ph ases(cons i uen s), which is known as cons i uen s uc u e, and he second is by connec ing he wo ds wi h links, which is known as dependency s uc u e. Those s uc u es a e cons uc ed by pa sing algo i hms. The pa se s o cons uc ing a cons i uen ee a e called ph ase s uc u ed pa se s and he pa se s o dependency s uc u es a e called dependency pa se s. 1.3.2.1 Cons i uency S uc u e The ph ase s uc u e was in oduced by Noam Chomsky, he idea behind cons i uency ph ase s uc u e is o o ganize he wo ds in o nes ed cons i uen s[58] [46](Figu e 1.1). Meaning ha each nes ed cons i uen (wo d ph ase) is a wo d uni . The e has been di e en c i e ia o de e mining he cons i uen s. The mos popula is he one ha claims ha a cons i uen beha es as a uni no ma e he place ha is loca ed in he sen ence. Rega ding o he cons uc ion o his s uc u e, one g ea pa se is he cons i uen pa se om Zhu[83]. 2 1.3. BACKGROUND Figu e 1.1: Cons i uency T ee Sou ce :“A Gene a i e Cons i uen -Con ex Model o Imp o ed G amma Induc ion.”, D.Klein, 2002 1.3.2.2 Dependency S uc u e The idea behind dependency s uc u e is ha ing wo ds connec ed wi h a dependency ela ion (Figu e 1.2),whe e one o hem is he head and he o he is he dependen and he e is a link connec ing hem. In mo e de ail, he dependen is he modi ie , objec , o complemen while he head de e mines he beha io o he pai . The dependen equi es he p esence o he head; he head on he o he hand doesn’ equi e he p esence o he dependen . [17]. In gene al, he dependency s uc u e is a ee wi h he main e b as i s oo (head o he whole s uc u e). I is wo h men ioning ha a dependency s uc u e can be cons uc ed om cons i uen ees as well [19]. The idea behind dependency s uc u e is o di ec ly show o he wo ds o a sen ence which a e he wo ds depend on (modi y o a e a gumen s o ) which o he wo ds. [45] Figu e 1.2: Dependency T ee Sou ce :“A Gene a i e Cons i uen -Con ex Model o Imp o ed G amma Induc ion.”, D.Klein, 2002 1.3.3 Neu al Ne wo ks Neu al ne wo ks a e models o compu a ion ha we e inspi ed by he way (we assume) ou b ain wo ks [52], [65],[66]. The s uc u e o a i icial neu al ne wo ks (ANN) is a ne wo k o small p ocessing uni s (neu ons) ha a e connec ed wi h weigh ed join s. O e he yea s many a ian s o ANN has been p oposed. One impo an dis inc ion is he way hey a e connec ed,wi h cycles o wi hou . The o me case o neu al ne wo ks 3 CHAPTER 1. INTRODUCTION a e called eedback o ecu si e neu al ne wo ks and will be examined a chap e 3, he la e case o neu al ne wo ks a e he Feed o wa d ne wo ks ha will be examined a he nex subsec ion. 1.3.3.1 Feed o wa d Ne wo ks Gi en he absence o cycles, all nodes can be a anged in o laye s, and he ou pu s in each laye can be calcula ed gi en he ou pu s om he lowe laye s. The inpu i o a eed o wa d ne wo k is p o ided by se ing he alues o he lowes laye . Each highe laye is hen successi ely compu ed un il ou pu is gene a ed a he ou pu laye o (Figu e 1.3). Figu e 1.3: Feed- o wa d neu al ne wo k Sou ce : h ps://www.linkedin.com/pulse/lea ning-scale-end- hen-logic-ish iaq- ahman Le wl jk be he weigh o he connec ion om he k h neu on in he laye l − 1 o he j h neu on in he l h laye , bl j he bias o node j a laye l and αl j o he ac i a ion o neu on ja l h laye . The equa ion below is using he sigmoid unc ion. αl j=σ(X limi =k wl jkαl−1 k+bl j) (1.1) Ha ing he equa ion abo e in mind, we can ew i e i in a mo e compac and ec o ized o m: αl=σ(wlαl−1+bl) (1.2) Le zl=Plimi =kwl jkαl−1 k+bl jbe he weigh ed inpu o he neu ons in laye l. αl=σ(zl) (1.3) The mos popula choices o ac i a ion unc ion a e he hype bolic angen (1.4), sigmoid (1.5), ec i ied linea uni (1.6), so max (gene aliza ion o sigmoid o K classes)(1.7) . 4 1.3. BACKGROUND anh(x) = e2x1 e2x+ 1 (1.4) σ(x) = 1 1 + ex(1.5) (x) = max(0,x) (1.6) so max(x)j=exj K X k=1 exk , o j = 1,....,K (1.7) The mos popula FNNs a e pe cep ons[65], Kohonen maps[63] and Hop ield ne s[41] and mul ilaye pe cep on (MLP)[66],[80], [6]. 1.3.3.2 Backp opaga ion The mos success ul algo i hm o aining neu al ne wo ks is backp opaga ion, i was in oduced o his pu pose by Rumelha , Hin on, Williams[66] and some al e - a ions we e sugges ed by Zipse [84], and We bos [80]. Backp opaga ion uses he chain ule o calcula e he de i a i e o he loss unc ion L wi h espec o each pa ame- e (weigh s and biases) in he ne wo k. The weigh s a e hen adjus ed by g adien descen algo i hm (which we will go in o de ail a chap e 4). While i is no ce ain ha backp opaga ion will each a global minimum (unless he loss su ace is con ex 1 ) ,many esea che s ha e wo ked on heu is ic p e- aining and op imiza ion echniques ha make hem p ac ically good enough o supe ised lea ning asks. To calcula e he g adien in a eed o wa d neu al ne wo k, backp opaga ion p o- ceeds as ollows. Fi s ,p oceeds o he o wa d pass, an example is p opaga ed o wa d h ough he ne wo k o p oduce a alue αl j , a each node j a laye l and ou pu s αL a he ou pu laye L . Then, a loss unc ion alue L( αL k , yk ) is compu ed a each ou pu node k. Subsequen ly, o each ou pu node j , we calcula e he e o whe e he i s exp ession θL(αL j,yj) θαL j co esponds o he a e o change in espec o he ou pu neu on j, and he second e m measu es how as he ac i a ion unc ion σis changing a zL j: δL j=θL(αL j,yj) θαL j σ0(zL j) (1.8) 1con ex su ace:when he local op ima is equal o he global op ima 5 CHAPTER 1. INTRODUCTION The equa ion abo e could be w i en in a mo e compac and ma ix-based o m, whe e ∇αL co esponds o he he a e o change o L wi h espec o he ou pu ac i a ions, as: δL=∇αLσ0(zL) (1.9) Ha ing compu ed he e o o he ou pu laye , we go o compu e he e o o he p io laye . The equa ion o compu ing he laye be o e is: δl= ((wl+1)Tδl+1)σ0(zl) (1.10) By combining he equa ions 1.9 and 1.10, we can compu e he e o a any laye . The backp opaga ion algo i hm s a s om he ou pu laye L calcula ing he δL wi h equa ion 1.9 and mo es o he p e ious laye s wi h equa ion 1.10. The equa ion o he a e o change o he cos in espec o he bias o node j in laye lis: θL θbl j =δl j(1.11) A mo e clean and ec o ized o m o he equa ion abo e can be w i en as: θL θb =δ(1.12) The equa ion o he a e o change o he cos in espec o he weigh ha connec s he node kand node jin laye lis: θL θwl jk =αl−1 kδl j(1.13) whe e α is he ac i a ion o he neu on inpu o he weigh w and δ is he e o o he neu on ou pu om he weigh w. θL θw =αIN δOUT (1.14) 6 Chap e 2 Wo d Embeddings Wo d embedding is a ep esen a ion o a wo d in ec o space whe e seman ically simila wo ds a e mapped o nea by poin s. Wo d embeddings can be ained and used o de i e simila i ies be ween wo ds. They a e an a angemen o numbe s ep- esen ing he seman ic and syn ac ic in o ma ion o wo ds in a o ma ha compu e s can unde s and. Fo many yea s, NLP sys ems and echniques would ep esen mean- ing o wo ds using Wo dNe (Geo ge A. Mille , P ince on Uni e si y, 1985) which is basically a e y la ge g aph ha de ines di e en ela ionships be ween wo ds. In ec o space e ms, e e y wo d is a ec o wi h one 1 and a lo o ze os ( ocabula y size -1). This is a so called one-ho ha desc ibes wo ds in he simples way. Howe e , his disc e e ep esen a ion had many issues, such as missing nuances, missing new wo ds, he equi emen o human labo o c ea e and adap , i was ha d o compu e ac- cu a e wo d simila i y and mos impo an ly when he ocabula y is la ge, he ec o ep esan a ion is gigan ic. The new app oach o ep esen ing wo ds was inspi ed by he quo e "You shall know a wo d by he company i keeps"[27]. Ins ead o ep esen ing a wo d by i s own index, ep esen a wo d by means o i s wo ds. This app oach o ep esen ing wo ds is by c ea ing a dense embedding ec o (wo d embedding). The wo d embeddings a e de i ed by Vec o Space Models (VSM) [67] which a e di ided in wo ca ego ies which ha e been c i ically compa ed by Ba on [2]. The i s ype o models is he coun -based me hod (aka ull documen me hod) ha compu e he s a is ics o how o en some wo ds co-occu wi h i s neighbo wo ds in a la ge ex co pus and hen map hose s a is ics o a low dimensional, dense ec o . Some wo h men ioning examples o his me hodology a e Hype space Analogue o Language [9], COALS me hod [21], Hellinge PCA [13]. The mos popula model o he coun -based me hod is he La en Seman ic Analysis [20] which we will co e a he sec ion (2.1). The second 7 CHAPTER 2. WORD EMBEDDINGS ype o VSM models a e he p edic i e models which y o p edic di ec ly he wo d om i s neighbo s in e ms o lea ned low dimensional, dense embedding ec o s. Some models wo h men ioning o his ca ego y a e Seman ic Role Labeling(SRL) [15], Mnih and Ka ukcuoglu LBL and i LBL[55],[54],Le y [48] p oposed explici wo d embeddings based on a PPMI me ic. A sec ions 2.2 and 2.3 we will co e he mos popula models o he VSM p edic i e models , named Wo d2Vec and GloVe. The 2.1 and 2.2 a e co e ed jus o demons a e way ha GloVe 2.3 was concei ed, he e o e hey a e co e ed wi h no much de ails. The new app oach o wo d ep esen a ion ackles he p oblems o high dimension- ali y, he scalabili y o he ocabula y and he seman ic ela edness o he wo ds. 2.1 La en Seman ic Analysis La en seman ic analysis (LSA) is a me hodology in na u al language p ocessing o analyzing ela ionships be ween a se o documen s and he e ms hey con ain by p o- ducing a se o concep s ela ed o he documen s and e ms. LSA assumes ha wo ds ha a e close in meaning will occu in simila pieces o ex . The e m-documen ma- ix ha is c ea ed, is qui e spa se. The e o e a ma hema ical echnique called singula alue decomposi ion (SVD) is used o educe he numbe o ows while p ese ing he simila i y s uc u e among columns. Singula Value Decomposi ion [31] is a me hod o iden i ying and o de ing he dimensions o he obse a ion ha exhibi he mos a ia ion. Once we ha e ound whe e he mos a ia ion lies, we can ind he bes app oxima ion o he o iginal obse a ion using ewe dimensions. The e o e, i can be used o dimensionali y educ ion asks. Le X be a ma ix wi h m e ms and n documen s whe e elemen (i,j) desc ibes he occu ence o e m i in documen j co-occu ence ma ix. Acco ding o SVD, he e is a decomposi ion o X so ha U and V a e o hogonal ma ices and Σ is a diagonal ma ix.The alues s1,...,sl a e called he singula alues, and u1,...,ul and 1 , ..., l he le and igh singula ec o s. X             x11 ··· x1n . . ..... . . xm1··· xmn             = U             u11 ··· u1 . . ..... . . um1··· um             Σ             s11 ··· 0 . . ..... . . 0··· s             VT             u11 ··· u1 . . ..... . . un1··· u n             Mo eo e he The ma ix p oduc XXT gi es us he he co ela ion be ween he e ms o e he se o documen s and he XTX gi es us he co ela ion be ween he documen s o e he se o e ms. XXT= (UΣVT)(UΣVT)T= (UΣVT)(VTTΣTUT) = UΣVTVΣTUT=UΣΣTUT=UΣ2UT XTX= (UΣVT)T(UΣVT)=(VTTΣTUT)(UΣVT) = VΣTUTUΣVT=VΣTΣVT=VΣ2VT Since ΣΣT and ΣTΣ a e diagonal we can sa ely conclude ha U a e he eigen ec o s o XXT , V a e he eigen ec o s o XTX and bo h p oduc s ha e he same eigen alues, 8 2.2. WORD2VEC gi en by he en ies o ΣΣT o ΣTΣ . F om F obenius no m 1 [32] we can de i e ha by aking he k la ges singula alues (exp ess he impo ance o e e y wo d), and hei co esponding singula ec o s, we ge he ank k app oxima ion o X wi h he lowes e o . The wo d ec o s o he co pus will be he k columns o he ma ix . X             x11 ··· x1n . . ..... . . xm1··· xmn             ≈ ˆ U             u11 ··· u1k . . ..... . . um1··· umk             ˆ S             s11 ··· 0 . . ..... . . 0··· skk             ˆ VT             u11 ··· u1k . . ..... . . un1··· xkn             While his me hod sol es he p oblem o dimensionali y, i unde lies some p ob- lems as well. Fi s o all, he compu a ional cos inc eases quad a ically as he size o he ma ix inc eases. Mo eo e when new wo ds appea SVD has o be un again om sc a ch. Finally, i is able o ind simila i ies be ween wo ds, bu i canno ep esen ela ionships. 2.2 Wo d2Vec Wo d2Vec (Mikolo , 2013) is a p edic i e model ha lea ns wo d embeddings on an online way. The main idea behind Wo d2Vec is o p edic he su ounding wo ds o e e y wo d in a window o leng h m, ins ead o cap u ing all he co-occu ence coun s di ec ly. I is simple and as e han LSA and can easily add a new wo d o he ocabula y. The objec i e unc ion o p edic i e VSMs (aka Neu al p obabilis ic language mod- els) aim o maximize he a e age log p obabili y o any con ex wo d gi en he cu en cen e wo d whe e is he numbe o okens, m he co-occu ence window and θ all he a iables we op imize using s ochas ic g adien descen . J(θ) = 1 T T X i=1 X −m≤j≤m,j,0 logp(w +j|w ) (2.1) Fo p(w +j|w ) : p(o|c) = exp(uT o c) W P w=1 exp(uT w c) (2.2) whe e o is he ou pu wo d id, c is he cen e wo d id, u is he cen e wo d ec o and is he ou pu ec o . This objec i e unc ion is no scalable and i akes much ime o ain when he ocabula y is la ge. Those wo models a e g ea a cons uc ing wo d ec o s, bu when he ocabula y becomes oo la ge he upda es a each i e a ion ake oo much ime. This p oblem is 1 F obenius no m: is ma ix no m o an m × n ma ix A de ined as he squa e oo o he sum o he absolu e squa es o i s elemen s 9 CHAPTER 3. FEEDBACK NEURAL NETWORKS 3.1.2.1 A chi ec u e Long-Sho Te m Memo y ne wo ks’ s uc u e is like Simple RNN’s, wi h only di e - ence on he hidden laye s uc u e. While RNNs ha e a single laye , he LSTMs ha e ou hidden laye s. The LSTM is consis ed o cells and ga es, cells con ain he in o - ma ion and ga es egula e "how much"o in o ma ion o le go, ga es a e composed o a sigmoid laye ha ou pu s an in e al om 0 o 1 whe e 0 s ands o "pass no in o - ma ion"and 1 o "pass e e y hing". In mo e de ail, i is consis ed o he o ge ga e ( ) which decides how much in o ma ion (cu en and pas ) o pass o he ne wo k, he inpu ga e ( i ) which decides wha in o ma ion o s o e a he cell, he cell s a e( C ) which is he upda ed s a e, and inally he ou pu ga e. Figu e 3.2: Long-Sho Te m Memo y Sou ce : h ps://deeplea ning4j.o g/ls m.h ml 3.1.2.2 Fo wa d Pass The i s s ep is o decide wha o inpu o he ne wo k, he e is whe e o ge ga e comes in (3.7) whe e akes as inpu he p e ious s a e ( h −1 ) and he cu en inpu ( x ) and i ou pu s an in e al be ween 0 o 1 o he candida e cell s a e( ˜ C )(3.8). Then we decide wha alues o upda e (3.9) a he inpu ga e( i . A e ha ing compu ed candida e cell and he inpu ga e we combine hem wi h he p e ious cell s a e( C −1 ) o de i e he cu en cell s a e ( C )(3.10). Finally we eed he cell s a e o he ou pu ga e in o de o decide how much o he cell s a e o ou pu (3.11) as well as o a anh laye so o squash he alues be ween -1 and 1(A.1). i =σ(W(i)x +U(i)h −1) (3.6) =σ(W( )x +U( )h −1) (3.7) o =σ(W(o)x +U(o)h −1) (3.8) ˜ C = anh(W(C)x +U(C)h −1) (3.9) C = C −1+i ˜ C (3.10) h =o  anh(C ) (3.11) 16 3.1. RECURRENT NEURAL NETWORKS 3.1.2.3 Backwa d Pass The o iginal LSTM aining algo i hm [39] used an app oxima e e o g adien calcu- la ed wi h a combina ion o Real Time Recu en Lea ning [64] and Backp opaga ion Th ough Time (BPTT) [84].The BPTT pa was unca ed a e one ime-s ep, since memo y blocks would deal wi h he longe dependencies.The unca ing me hod has he bene i o making he algo i hm online, meaning ha weigh upda es can be made a e e e y ime-s ep.Howe e in his epo we will he ex ac he LSTM g adien wi h BPTT[G a es2005a], o u he de ails look a appendix A. 3.1.3 Ga ed Recu en Uni Ga ed ecu en uni (Figu e 3.3) is ano he a ian o ecu en uni s p oposed by KyungHyun Cho[10]. I is closely ela ed Long-Sho Te m Memo y. The GRU also con ols he low o in o ma ion like he LSTM, bu wi hou using a memo y uni . I exposes he ull hidden con en wi hou any con ol. 3.1.3.1 A chi ec u e A GRU has wo ga es, a ese ga e , and an upda e ga e z . The ese ga e indica es how o combine he new inpu wi h he p e ious memo y. The upda e ga e de ines how much o he p e ious s a e o keep.The basic idea o using a ga ing mechanism o lea n long- e m dependencies is he same as in a LSTM, bu he e a e a ew di e ences in e ms o a chi ec u e. Fi s o all, i doesn’ ha e an ou pu ga e so i has ewe pa ame e s ( wo ga es, ins ead o h ee). Secondly he inpu and o ge ga es a e subs i u ed by an upda e ga e z and he ese ga e is applied di ec ly o he p e ious hidden s a e. Thus, he esponsibili y o he ese ga e in a LSTM is eally spli up in o bo h and z . Finally we don’ apply a second nonlinea i y when we compu e he ou pu . Figu e 3.3: Ga ed Recu en Uni Sou ce : h ps://deeplea ning4j.o g/ls m.h ml 3.1.3.2 Fo wa d Pass The i s s ep is o de e mine he inpu alues, his is upda e ga e’s ask i will decide how much o he p e ious hidden s a e and how much o he candida e hidden s a e 17 CHAPTER 3. FEEDBACK NEURAL NETWORKS combines o ge he new hidden s a e (3.12). A e he upda e ga e, he ese ga e while i has he exac same unc ional o m (3.13) as he upda e ga e and all he weigh s a e a he same size, wha makes i di e en is i s posi ion a he model. The ese ga e is mul iplied by he p e ious hidden s a e i con ols how much om he p e ious hidden s a e we will conside when we c ea e he new candida e hidden s a e. In o he wo ds, i has he abili y o ese he hidden s a e , i we se he ese ga e o 0 om (3.14) we s a o e om a new sequence as i h is he beginning o a new sequence. Howe e his is no he ull pic u e since ˜ h is jus a candida e o he hidden s a e, he ac ual hidden s a e will be a combina ion o p e ious hidden s a e h −1 and he candida e hidden s a e ˜ h con olled by he upda e ga e z (3.15) . z =σ(W(z)x +U(z)h −1) (3.12) =σ(W( )x +U( )h −1) (3.13) ˜ h = anh(W(h)x +U(h)(h −1 )) (3.14) h = (1 −z)˜ h +zh −1(3.15) 3.1.3.3 Backwa d Pass Ga ed Recu en Uni s also use he BPTT algo i hm in o de o be ained. We will de i e he g adien s o E (e o ),W,U and by hand using he chain ule, o u he de ails look a appendix B 3.2 Recu si e Neu al Ne wo ks Recu si e Neu al Ne wo ks (RNNs) [71], [61], [30], [16], [36] a e pe ec o se ings ha ha e nes ed hie a chy and an in insic ecu si e s uc u e [73]. The syn ac ic ules o language a e highly ecu si e, he e o e we use ha ecu si e s uc u e wi h a model ha complies wi h ha p ope y. I is impo an o no ice ha RNN don’ comp ehend sen ences as sequences bu as hie a chies which makes hem ideal o seman ic ep- esen a ion asks (pa aph ase de ec ion [71], ela ion classi ica ion, sen imen analy- sis, ph ase simila i y) bu hey can’ p edic u u e i ems om a sequence(nex wo d om a gi en sen ence),some hing ha Recu en Neu al Ne wo ks a e e y good a due o hei linea s uc u e.Recu en Neu al Ne wo ks ep esen sen ences as pa se ees(Figu e 3.4). 18 3.2. RECURSIVE NEURAL NETWORKS Wha RNNs a e e y good a , is handling nega ion. Due o hei hie a chical s uc- u e, when nega ion is spo ed, he meaning is jus being e e sed. You ha e a label a e e y node o he ee, and he lea es o he ee ep esen wo ds. Mo eo e ano he eason ha RNN a e so popula o na u al language p ocessing asks, is ha he inpu sequence leng h (sen ence in ou case) is no a es ic ion, i can ake inpu s o a bi a y leng hs. The la e bene i is accomplished by making he inpu ec o o sen ence a p ede ined size no ma e he leng h o he sen ence. ([4],[35], [14]. Essen ially wha RNNs do is o me ge he seman ic unde s anding 1 o he wo ds, hen he g amma ic unde s anding 2 o he ph ase o sen ence,which esul s o a pa se ee ep esen a ion o a ph ase o a sen ence. Ha ing unde s ood he wo ds, and knowing he way wo ds a e pu oge he we can e ie e he meaning o he sen ence. E en hough g amma ical unde s anding is an assump ion and i is no p o en ha i imp o es he accu acy, i is s ill unde deba e bu we will assume ha i helps he model. In sho , i ex ac s om he sen ence he syn ac ic s uc u e, which indica es he ela ionship be ween ph ases, and i iden i ies he meaning ul ph ases wi hin he sen- ences and he ela ionship be ween hem. In o de o ex ac he ec o ep esen a ion o he sen ence, he idea is o ecu si ely me ge pai s o ep esen a ions o smalle seg- men s o ge ep esen a ion ha co e s bigge sen eces. The Recu si e Neu al Ne wo ks a e ained wi h he Backp opaga ion Th ough S uc u e algo i hm[30] which is e y simila o he s anda d Backp opaga ion, we use he 1.10 and he 1.14, ha was discussed a subsec ion 1.3.3 wi h h ee mino di e ences. Fi s ly we sum up he de i a i es o W om all he nodes, secondly we spli he de i a i es a each node and inally we add di e en e o messages om pa en node and sel node. Finally, i is assumed ha he ee s uc u ed is gi en, which indica es ha some p ep ocessing is equi ed i i is no gi en. In ou expe imen we will use he S an o d Sen imen T eebank(SST) ha was ained wi h he S an o d Pa se [70],which is simi- la o max-ma gin pa sing [78], o de i e he ee s uc u e is o e e y sen ence. We will no go h ough he way ha he sen ence ees we e cons uc ed because we will add unnecessa y complexi y ha is beyond he scope o his epo , bu a a high le el explana ion he pa se ha is used, ha e a loss e m ha penalizes he no plausible ph ases. 3.2.1 Simple Recu si e Neu al Ne wo k This model (Figu e 3.5) is he s anda d ecu si e neu al ne wo k. The i s s ep o ake is o ake a sen ence pa se ee and he sen ence wo d ec o s and begin om he bo om lea es o he op oo o he ee. The ma hema ical o mula o me ge 1 seman ic unde s anding: unde s anding o he meaning o a sen ence, ep esen accu a ely he ph ase as a ec o in a s uc u ed seman ic space 2g amma ical unde s anding: i is iden i ied he unde lying g amma ical s uc u e o he sen ence 19 CHAPTER 3. FEEDBACK NEURAL NETWORKS Figu e 3.4: Recu si e Neu al Ne wo k Sou ce : h ps://s a s.s ackexchange.com/ques ions/153599/ ecu en - s- ecu si e- neu al-ne wo ks-which-is-be e - o -nlp hose wo ec o s (aka child en) and c ea e a new "wo d ph ase" ec o (pa en ) can be illus a ed below (3.16). The h ec o now ep esen he " his assignmen "ph ase. Ha - ing compu ed he ec o ep esen a ions o he sen ences, we compu e a s sco e 3.17 which ep esen s he quali y o he me ge and decides which pai o ep esen a ions o me ge i s . In ode o de i e some meaning o he wo d ec o , we eed i o a so max laye (3.18) o compu e he sco e o e a se o sen imen classes, a disc e e se o known classes ha ep esen some meaning. This p ocess happens ill he model each he oo o he ee. Mo eo e i is impo an o no e ha he W pa ame e s is he same o all he nodes o he ees. I is ob ious ha his is qui e a nai e app oach and linguis ic complexi y is highe han ha . I is oo much o ask om a simple unc ion like his o cap u e he language complexi y. h1= anh(W      c1 c2      +b) (3.16) s1=Wsco ep(3.17) ˆ y=so max(W h1+b) (3.18) 3.2.2 Syn ac ically Un ied SU-RNN One ex ension o he Simple RNN, he Syn ac ically Un ied RNN model [73](Figu e 3.6) was in oduced o sol e he p oblem men ioned a he p e ious subsec ion. Wha his model does, is o ha e unique weigh ma ices o e e y syn ac ic ca ego y. The syn ac ic ca ego ies a e iden i ied om he pa se ha de e mined he s uc u e o he 20 3.2. RECURSIVE NEURAL NETWORKS Figu e 3.5: Simple Recu si e Neu al Ne wo k Sou ce: h ps://www.slidesha e.ne /jiessiecao/pa sing-na u al-scenes-and-na u al- language-wi h- ecu si e-neu al-ne wo ks ee. This has p o en o inc eases he weigh ma ices o lea n and ou pe o ms he me hods ha we e men ioned ill ha poin ,bu he pe o mance boos we gained is no signi ican . One imp essi e accomplishmen o his model is ha he ained weigh ma ices a e capable o lea ning he seman ics o he ph ases. Fo example a de e mine ol- lowed by a noun ph ase (e.g. "an elephan ") emphasizes mo e on he noun ph ase han on he de e mine . The a chi ec u e o he SU-RNN model compa ed o he Simple RNN is illus a ed a Figu e 3.6. Figu e 3.6: Syn ac ically Un ied Recu si e Neu al Ne wo k Sou ce: h ps://wugh.gi hub.io/pos s/2016/05/cs224d-no es5- ecusi e-neu al-ne wo ks/ 3.2.3 Ma ix-Vec o Recu si e Neu al Ne wo ks Ano he al e a ion o Recu si e Neu al ne wo ks is he Ma ix-Vec o Recu si e Neu al Ne wo ks [72] (Figu e ?? )which imp o es he seman ic ep esen a ion o he sen ences. The majo di e ence is ha no only we include a wo d ec o (d-dimensional), bu also a wo d ma ix (dXd)(Figu e 3.7). 21 CHAPTER 3. FEEDBACK NEURAL NETWORKS h1= anh(W      C2c1 C1c2      +b) (3.19) This app oach no only ep esen s he meaning o each wo d bu also he e ec ha i has on he neighbo ing wo ds. Suppose we eed wo wo ds o he model, a and b, he pa en ec o is he conca ena ion o he wo d ec o o he o me mul iplied wi h he wo d ma ix o he la e and he wo d ec o o he la e is mul iplied by he wo d ma ix o he o me (Ab and Ba). In he igu e’s example, he wo d ma ix o " e y"could also be he iden i y 3 mul iplied by a scala (abo e one) which indica es he impac i has o he wo d "bad". Figu e 3.7: Ma ix-Vec o Recu si e Neu al Ne wo ks Sou ce: h ps://wugh.gi hub.io/pos s/2016/05/cs224d-no es5- ecusi e-neu al-ne wo ks/ Despi e he ac ha his is he mos exp essi e model we ha e explo ed ill now, i is s ill no good enough. I ails o cap u e he seman ics o some ela ions. The e ha e been obse ed h ee ypes o e o s. [73] The i s ype (Figu e 3.8)is he nega ed posi i es, his case occu s when some hing is classi ied as posi i e bu one wo d u ns i nega i e, he model can no cap u e he impo ance o ha one wo d s ong enough o lip he sen imen o he en i e sen ence. Figu e 3.8: Nega ed posi i es Sou ce: h ps://cs224d.s an o d.edu/lec u eno es/Lec u eNo es5.pd The second ype (Figu e 3.9) is he nega ed nega i e, whe e we say some hing is no 3iden i y ma ix: squa e ma ix wi h ones on he main diagonal and ze os elsewhe e 22 3.2. RECURSIVE NEURAL NETWORKS bad. The MVRNN can no ecognize ha he wo d ”no ” because i u ns sen imen om nega i e o neu al. Figu e 3.9: Nega ed Nega i e Sou ce: h ps://cs224d.s an o d.edu/lec u eno es/Lec u eNo es5.pd The inal ype o e o s (Figu e 3.10) we obse e is he ”X bu Y conjunc ion”. In ou example, X is nega i e bu he Y is posi i e and he sen imen is posi i e. The MV-RNNs ha e some issues wi h such cases. Figu e 3.10: X bu Y conjunc ion Sou ce: h ps://cs224d.s an o d.edu/lec u eno es/Lec u eNo es5.pd Thus, we mus look o an e en mo e exp essi e composi ion algo i hm ha will be able o ully cap u e hese ypes o high le el composi ions. 3.2.4 Recu si e Neu al Tenso Ne wo k The hi d Recu si e Neu al Ne wo k a ian ha will be co e ed is he Recu si e Neu- al Tenso Ne wo k(Figu e 3.11). RNTN was concei ed by Richa d Soche [73] in o de o sol e he h ee ypes o e o s we le o wi h a he subsec ion 3.2.3. Mo eo e i is amously qui e sucess ul o dealing wi h double nega ions. The Recu si e Neu al Tenso Ne wo k ge s id o he concep o a wo d ma ix as well as he a ine ans- o ma ion 4 p e- anh/σ concep ha we saw be o e. To combine wo wo d ec o s o ph ase ec o s, we again conca ena e hem o o m a ec o ∈2d bu ins ead o pu ing i h ough an a ine unc ion hen a nonlinea , we pu i h ough a quad a ic i s , hen a nonlinea , such as: 4a ine ans o ma ion: is a ans o ma ion composed o a linea unc ion+ a cons an 23 CHAPTER 3. FEEDBACK NEURAL NETWORKS h(1) = anh(xTV x +W x) (3.20) Whe e V is a 3 d o de enso ∈2d×2d×d . The quad a ic shows ha we can indeed allow o he mul iplica i e ype o in e ac ion be ween he wo d ec o s wi hou needing o main ain and lea n wo d ma ices. Figu e 3.11: One slice o a RNTN. No e he e would be d o hese slices. Figu e 3.11: Recu si e Neu al Tenso Ne wo k Sou ce: h ps://wugh.gi hub.io/pos s/2016/05/cs224d-no es5- ecusi e-neu al-ne wo ks/ A majo p oblem o he models we co e ed be o e is hei inabili y o handle nega- ion[69]. The able 3.1 below shows how he RNTN handles nega ions. Table 3.1: Nega ions Model Nega ed Posi i e Nega ed Nega i e RNN 33.3 45.5 MV-RNN 52.4 54.6 RNTN 71.4 81.8 3.2.5 T ee-Based Long-Sho Te m Memo y Ne wo ks T ee-Based LSTM (Figu e 3.12) was ecen ly concei ed by Kai Sheng Tai [77]. This is a hyb id model ha combines LSTMs and Recu si e neu al ne wo k. I is impo an o no ice ha LSTMs we e used o linea chained s uc u ed ecu si e neu al ne wo ks ( ecu en neu al ne wo ks). The main di e ence ha his model has wi h he s anda d LSTMs is ha i is equi ed he a e age o he child ec o s and a special o ge ga e o each child. The idea behind his a chi ec u e is mos ly o handle nega ion, by keep- ing in memo y he seman ically impo an wo ds and o ge ing he non signi ican . This p ocess happens as he model goes h ough he ee s uc u e. The Figu e3.12 illus a es how he new memo y cell c1 and hidden s a e h1 a e composed wi h wo child en. 24 3.2. RECURSIVE NEURAL NETWORKS Figu e 3.12: T ee-Based LSTM Memo y Cell Composi ion Sou ce: h ps://a xi .o g/pd /1503.00075.pd The T ee-LSTM beha es e y simila o he s anda d LSTM, i akes as inpu ec o xj wi h only di e ence ha he inpu ec o depends on he ee s uc u e (1.3.2). I he ee is a cons i uency ee, he lea nodes ake he co esponding wo d ec o s as inpu , i he ee is a dependency ee each node in he ee akes he ec o co esponding o he head wo d as inpu . The wo ex ensions ha Tai(2015) p oposed a e he Child T ee-LSTM and N-a y T ee-LSTM. 3.2.5.1 Child-Sum T ee-LSTM Sum T ee-LSTM uni condi ions i s componen s on he sum o child hidden s a es hk , his model pe o ms well wi h high b anching ac o ee s uc u es o wi h s uc u es ha i s child en a e no o de ed. Dependency ees is a good choice o s uc u e o ha model since he numbe o dependen s o a head can be qui e a ian . Le C ( j ) he se o child en o node j and k∈C ( j ), he equa ions o he model a e he ollowing: ˜ hj=X k hk(3.21) ij=σ(Wixj+Ui˜ hj+bi) (3.22) jk =σ(W xj+U hk+b ) (3.23) oj=σ(Woxj+Uo˜ hj+bo) (3.24) ˜ Cj= anh(Wuxj+Uu˜ hj+bu) (3.25) 25 CHAPTER 4. NEURAL NETWORK TRAINING Figu e 4.1: Vanilla s Momen um Sou ce : ’h p://dsdeepdi e.blogspo .com/2016/03/op imiza ions-o -g adien -descen .h ml’ a ough app oxima ion o whe e he pa ame e will be, so now i can e ec i ely look ahead by calcula ing he g adien wi h ega ds o he app oxima ion o he u u e posi ion and no he cu en one (4.6). Acco ding o Bengio[5] he es ima ed upda e p e en s us om going oo as and esul s in inc eased esponsi eness. =γ −1+η∇θJ(θ−γ −1) (4.6) θ=θ− Sou ce :h p ://dsdeepdi e.blogspo .com/2016/03/op imiza ions −o −g adien −descen .h ml (4.7) The di e ence be ween he wo app oaches can be illus a ed below a Figu e 4.2. Figu e 4.2: Momen um s Nes e o Momen um Sou ce: h ps://www.slidesha e.ne /c egly/g adien -descen -back-p opaga ion-and- au o-di e en ia ion-ad anced-spa k-and- enso low-mee up-08042016 4.2.4 AdaG ad AdaG ad[23] adap s he lea ning a e o e e y ea u e which elimina es he need o manually uning he lea ning a e. I adap s he lea ning a e o he pa ame e s, pe o ming la ge upda es o in equen and smalle upda es o equen pa ame e s. Fo his eason, i is well-sui ed o dealing wi h spa se da a.[12] Mo eo e , Penning on [60] used Adag ad o ain GloVe(sec ion 2.3) wo d embeddings ha we use a ou 32 4.2. GRADIENT DESCENT EXTENSIONS expe imen on he nex chap e . The eason he used AdaG ad, is because in equen wo ds equi e much la ge upda es han equen ones. Since AdaG ad uses di e en lea ning a e o e e y pa ame e θi a e e y ime s ep o he sake o con enience we assume g ,i (4.8) o be he g adien o he objec i e unc ion o pa ame e i and g (4.9) be he ec o o all he pa ame e s a ime s ep . Apa om he elemen -wise p ope y o his app oach, Duchi makes use o a diagonal ma ix G∈Rdxd ha is consis ed o he sum o he squa es o he g adien s wi h espec o he pa ame e up o ime s ep , while i also has a smoo hing e m  ha p e en s i om being di ided wi h 0. I is adap ing he lea ning a e by caching he sum o squa ed g adien s wi h espec o each pa ame e a each ime s ep. The eason ha we use he squa ed sums is no speci ied, bu i pe o ms way be e han aking he ma ix wi hou he squa e oo ope a ion. Finally he o mula o compu ing he pa ame e can be seen below. g ,i =∇θJ(θi(4.8) θ +1 =θ −η √G +g (4.9) Despi e i s high pe o mance, Adag ad has a se ious d awback which s ems om he ac ha he lea ning a e sh inks a e some poin due o i s accumula ion o he squa ed g adien s in he denomina o . This is he eason ha i is no o iously agg essi e a he machine lea ning communi y. 4.2.5 AdaDel a In o de o ackle he lea ning a e sh inking p oblem Zeile came up wi h a di e en way o adap ing he lea ning a e. Adadel a [82] comes o escue. Adadel a is an ex ension o Adag ad ha alle ia es i s agg essi ely mono onically dec easing lea ning a e. I was sugges ed ha ins ead o accumula ing all he p e ious g adien s i would be be e o se a ixed window o size w and ake he accumula ed g adien s o size w . Mo eo e , ano he al e a ion o Adag ad is he way i ea s he pas g adien s. Ins ead o s o ing he pas squa ed g adien s, he sum o g adien s is de ined as a decaying a e age o all pas squa ed g adien s. The a e age o ime s ep depends only on he p e ious a e age and he cu en g adien . I is also used he momen um e m , ha was co e ed a subsec ion 4.2.2, which de e mines how much o he pas a e age will a ec he cu en a e age. E[g2] =γE[g2] −1+ (1 −γ)g2 (4.10) The pa ame e upda e is de ined simila o he AdaG ad bu ins ead o he diagonal ma ix G we use he decaying a e age o he pas squa ed g adien s E[g2] . 33 CHAPTER 4. NEURAL NETWORK TRAINING ∆θ =−η pE[g2] +g (4.11) Mo eo e he denomina o o (4.11) is he oo mean squa ed(RMS) e o o c i e- ion o he g adien , ha ing no iced ha Ziegel de ined he decaying a e age o he squa ed pa ame e upda es. Howe e he RMS[∆θ] is no known so i is app oxi- ma ed wi h he RMS o he pa ame e upda es om he p e ious ime s ep. The e o e he upda es o he pa ame e s can be compu ed as : ∆θ =RMS[∆θ] −1 RMS[g] g (4.12) Some hing in e es ing abou his app oach is ha he lea ning a e is i ele an , as i is nowhe e in he upda e ule. 4.2.6 RMSp op RMSp op is an unpublished adap i e lea ning me hod om Hin on a his cou se a Machine Lea ning cou se ha is commonly used om he deeop lea ning communi y (i is e en a buil -in unc ion a enso low). RMSp op is e y simila wi h AdaDel a, in ac is is jus like he i s pa o AdaDel a bu ins ead o γ he e is a de aul alue o 0.9 while i s sugges ed ini ial lea ning a e is 0.001. E en hough hey we e es ablished he same pe iod hey we e concei ed independen ly. E[g2] = 0.9E[g2] −1+ 0.1g2 (4.13) ∆θ =−η pE[g2] +g (4.14) 4.3 Hype pa ame e s 4.3.1 Lea ning Ra e Lea ning a e can be hough as he a e ha he pa ame e upda e based on i s g adi- en . Choosing a p ope lea ning a e can be di icul . A lea ning a e ha is oo small leads o slow con e gence, while a lea ning a e ha is oo la ge can make he loss unc ion luc ua e a ound he minimum o e en di e ge. 4.3.2 Regula iza ion I is a me hod o p e en ing o e i ing. I essen ially wo ks by se ing a penal y a complexi y penal y o he loss unc ion. In p ac ice, his means ha i penalizes a 34 4.3. HYPERPARAMETERS unc ion ha is oo non-linea and lea ns by hea he in o ma ion ha is con ained in he aining se and is no able o gene alize well o new examples. In his pape we will men ion he mos popula egula ize s ha we will also use a he expe imen s. Le hose be L2 egula ize and d opou egula ize . Bu why do we eally need egu- la iza ion? I doesn’ help he model pe o m well a he aining se bu pe o m well a he new examples( es se ), which means ha i minimizes he gene aliza ion e o . The gene aliza ion e o is he sum o he squa ed bias and a iance o he ained model. The a iance o he model indica es how much he model a ies i we change he aining se , he bias o he model is how close is he model o he ue solu ion ( he model ha gene a ed hose ins ances). 4.3.2.1 L2 Regula iza ion The L2 egula iza ion me hod [40] adds a egula iza ion e m in o de o p e en he coe icien s o i so pe ec ly o o e i . When i comes o neu al ne wo ks i only egula izes he connec ion weigh s he hidden laye s. In mo e de ail, wha we do is o penalize he squa e o he weigh alue o each hidden laye k and o each connec ion i,j . No ice ha he sum o i,j om equa ion (4.15) co esponds o he F obenius No m he e o e i can be w i en as (4.16) Ω(θ) = X k X i X j (W(k) i,j )2(4.15) Ω(θ) = X kkW(k)kF(4.16) The g adien o he egula ize wi h espec o he k h laye is wo imes he weigh ma ix : ∇w(k)Ω(θ)=2W(k)(4.17) I is impo an o no ice ha his is applied only a he weigh s, because we don’ expec o o e i he aining se by changing he biases a lo bu mo e by changing he weigh s ha eally de e mine how he unc ion can become mo e o less non-linea . 4.3.2.2 D opou Regula iza ion In deep neu al ne wo ks ha e been p oposed wo ways o dealing wi h o e - i ing , he i s one is he unsupe ised p e- aining [26](which we will no discuss because i will no be used in his expe imen he e o e i is beyond he scope o his pape ), he second is d opou [37]. D opou was p oposed by Geo ey Hin on as a echnique o pe o ming egula iza ion. I wo ks by andomly d opping nodes in a neu al ne wo k and i emula es ensembles 1 o neu al ne wo ks. The applica ion can be seen 1 ain a g oup o p edic ion models, hen a e age hei p edic ion o ake he majo i y o e 35 CHAPTER 4. NEURAL NETWORK TRAINING a igu es 4.3,4.4 whe e Figu e 4.3 illus a es a s anda d neu al ne wo k while Figu e 4.4 illus a es he e y same neu al ne wo k a e ha ing applied d opou . In p ac ice, o each hidden uni once i ha e been compu ed we will independen ly se i o 0 (d opping ou he alue de i ed om he aining) wi h a p obabili y ,usually o 0.5. This p ocess con inues ill we each he ou pu laye . The e o e as a esul o he whole p ocess he hidden uni s can’ collabo a e wi h each o he in o de o gene a e complex pa e ns ha migh be use ul o i he aining da a so hey a e o ced o ex ac a ea u e ha is use ul in gene al. Figu e 4.3: S anda d Feed- o wa d Neu al Ne wo k Figu e 4.4: A e applying D opou Sou ce: h p://cs231n.gi hub.io/neu al-ne wo ks-2/ The d opou egula iza ion echnique, i has an impac on bo h he o wa d and backwa d p opaga ion algo i hm o aining a neu al ne wo k. In mo e de ail, e- ga ding he o wa d p opaga ion, we se a andom bina y mask m(k) wi h alues 0 (d opou he weigh o he uni ) o 1( e ains he alue), when i comes o he backwa d p opaga ion, when we backp opaga e he g adien ill he p eac i a ion( z 1.3) we also need o mul iply i by he mask ec o , due o he chain ule. This p ac ically means ha many g adien s will be se o ze o so he backp opaga ion won’ low h ough he hidden uni s ha we e d opped ou . 36 Chap e 5 Expe imen s This chap e is dedica ed o he p ac ical compa ison be ween he Cons i uen LSTM, wi h he T ee-Based GRU o Cons i uen GRU. I is impo an o no ice ha he ex- pe imen s ha e been conduc ed 5 imes and he esul s a e he p oduc o he a - e aged esul s o all he ials. We use he S an o d Sen imen T eebank(SST), and we use he s anda d ain/de / es spli s o 6920/872/1821 o he bina y classi ica- ion sub ask and 8544/1101/ 2210 o he ine-g ained classi ica ion sub ask ( he e a e ewe examples o he bina y sub ask since he neu al ins ances ha e been ex- cluded). The sen imen label a each node is p edic ed using he classi ie co e ed a he nex subsec ion 5.1.1. Mo eo e he SST ha e each sen ence s uc u ed as con- s i uen pa se ees, he e o e we will use he Cons i uen LSTM as a compa ison o ou model. Please ind he code necessa y o unning hose expe imen s o he nex u l: h ps://gi hub.com/VasTsak/mas e _ hesis. 5.1 Model compa ison Be o e p oceeding o he expe imen s we made he assump ion ha he T ee-based GRU will be as e o be ained because o i s ewe pa ame e s. The expe imen s p o ed us igh . Bu aining speed is jus a ac o (no e en ha c i ical) o selec a model, wha we eally ca e abou is i s capabili y o being able o iden i y he unde - lying pa e n jus igh , no lea n he aining se by hea (o e i ing) no igno ing some impo an ea u es(unde i ing). 5.1.1 Classi ica ion model The goal o he pape is o compa e he pe o mance o he T ee-GRU a chi ec u e agains he T ee-LSTM a chi ec u e on sen imen classi ica ion asks. In p ac ice, he 37 CHAPTER 5. EXPERIMENTS model p edic s a label ˆ y om a se o classes (2 o bina y, 5 o ine g ained) o some subse o nodes in a ee. The classi ie and he objec i e unc ion a e exac ly he same o bo h a chi ec u es. Le {x}j be he inpu s obse ed a nodes in he sub ee wi h oo he node j. ˆ pθ(y|{x}j) = so max(Wphj+bp),(5.1) ˆ yj= a gmax y ˆ pθ(y|{x}j).(5.2) Le m be he numbe o labeled nodes in he aining se and he supe sc ip k be he k h labeled node, he cos unc ion is: J(θ) = −1 m m X k=1 log ˆ pθ(y(k)|{x}(k)) + λ 2kθk2 2(5.3) 5.1.2 Bina y Classi ica ion The bina y classi ica ion is a p oblem ha classi ies whe he he sen imen o he sen ence is posi i e o nega i e. The p ocess o he aining can be seen a he Figu es 5.1 ,5.2, and 5.3 whe e a Figu e 5.1 i is plo ed he a e age aining ime o each i e a ion and a Figu es 5.2 a e plo ed he a e age loss o each i e a ion and a Figu e 5.3 he aining p ocess1o T ee-GRU and T ee-LSTM. Figu e 5.1: Bina y Classi ica ion A e age T aining Time Figu e 5.2: Bina y Classi ica ion A e age T aining Loss All he plo s ha e as hei x-axis he numbe o epochs. The me ics ha we plo a e compu ed ill he 12 h epoch and in cases o ea ly s opping 2 we wouldn’ ake in o accoun he 0 o "Non Assigned Numbe "o he ial ha i s aining s opped ea lie bu we would jus skip i and calcula e he esul s based on he es ials ha had a ull aining p ocess. 1 aining p ocess: he aining and alida ion sco es a each epoch. 2 ea ly s opping: when he alida ion e o inc eases o a speci ied numbe o i e a ions, he aining p ocess s ops 38 5.1. MODEL COMPARISON Figu e 5.3: Bina y Classi ica ion T aining P ocess 5.1.3 Fine-g ained Classi ica ion The Fine-g ained classi ica ion is a 5-class sen imen classi ica ion(1-Ve y Nega i e,2- Nega i e,3-Neu al,4-Posi i e,5-Ve y Posi i e). The expe imen o he Fine-g ained classi ica ion is unde he same ci cums ances. The a e age ime ha each i e a ion las ed du ing he aining p ocess can be illus a ed a Figu e 5.4, he a e age loss ha occu ed du ing he aining p ocess is illus a ed a Figu e 5.5 and he aining p ocess o he ine g ained classi ica ion can be seen a Figu e 5.6. Figu e 5.4: Fine G ained Classi i- ca ionA e age T aining Time Figu e 5.5: Fine G ained Classi i- ca ion A e age Loss 5.1.4 Hype pa ame e s and T aining De ails We ha e ini ialized he wo d ep esen a ions using he p e- ained 300-dimensional GloVe ec o s[60].The aining o he model was done wi h AdaG ad[23] and a lea ning a e o 0.05 also we used he mini-ba ch g adien descen algo i hm wi h ba ch size o 25. The model pa ame e s we e egula ized wi h L2 egula iza ion s eng h o 0.0001 and d opou a e o 0.5. Fo he aining p ocess we ha e applied he ea ly s opping echnique in o de o a oid o e i ing. The goal o his pape is no o achie e a s a e- o -a accu acy bu o make a c i ical compa ison be ween he wo models he e o e we 39 CHAPTER 5. EXPERIMENTS Figu e 5.6: Fine G ained Classi ica ion T aining P ocess won’ upda e he wo d ep esen a ions du ing he aining which boos s he accu acy app oxima ely 0.05 ( ha is he accu acy boos ga e o he T ee-LSTM). 5.2 Resul s The esul s o bo h he bina y and ine g ained classi ica ion can be seen in Table 5.1 we can see ha T ee-based GRU ha e sligh ly be e pe o mance wi h he ee-based LSTM, bu i is impo an o no ice om Table 5.2 he s anda d de ia ion o he indi- idual p edic ions ha he p edic ion om T ee-GRU seem o be mo e luc ua e han he ones om T ee-LSTM he e o e i is possible ha his di e ence o pe o mance can be andom, because he s anda d de ia ion is qui e high o he case o T ee-GRU. Some hing impo an o no ice abou he aining p ocess o ine g ained classi- ica ion is ha , he T ee-based GRU would s op a he 8 h i e a ion while he LSTM would go all he way ill he 12 h i e a ion. Mo eo e some hing else o no ice is ha he T ee-LSTM o ine-g ained classi ica ion seems like i has some mo e aining o do be o e i o e i s, in con as wi h he T ee-GRU which would o e i be o e ha ing execu ed wel e i e a ions, which can be obse ed abo e (Figu es 5.6). This may ha e o do wi h he hype pa ame e s ha we ha e chosen. We ha e se he ea ly s opping a 2 i e a ions(as he T ee-based LSTM pape had), i we would se i o 3 he T ee-GRU may keep on aining ill he 12 h i e a ion. Mo eo e T ee-GRU’s aining and alida ion sco es seem o luc ua e mo e in he ine-g ained classi ica ion 5.6 which may unde lies uns able p edic ion and he need o ain mo e. Table 5.1: Sen imen Classi ica ion Accu acy Model Bina y Fine-g ained T ee-LSTM 84.43 45.71 T ee-GRU 85.61 46.43 40 5.3. CONCLUSIONS AND FUTURE WORK Table 5.2: Sen imen Classi ica ion S anda d De ia ion Model Bina y Fine-g ained T ee-LSTM 0.35 0.55 T ee-GRU 0.93 0.98 5.3 Conclusions and Fu u e Wo k We can conclude ha he e is a di e ence in e ms o pe o mance ,no ha signi ican hough, be ween he ee-based LSTM and ee-based GRU. Mo eo e , T ee-based GRUs a e ained as e -compu a ionally- and T ee-based GRUs seem o con e ge as e so, he aining p ocess can s op ea lie .The e o e i is a good al e na i e,i no a subs i u e. The a ea o Na u al Language P ocessing is e y ac i e a ea o esea ch, ee-based a chi ec u es p o ed o be e y powe ul o Na u al Language P ocessing asks, mos ly because o hei capabili y o handling nega ions. Many po en ial p ojec s can be de eloped a ound T ee-Based GRUs, namely a Child-Sum app oach,o he o use unique ese and upda e ga e o each child, o e en y di e en GRU a chi ec u es [22]). Fo he end, one philosophical hough . Can you imagine an en i e sys em o neu al ne wo ks pe o ming di e en asks, so ha he end esul is some hing ac ionable. Like building a b ain, he language p ocessing sys em would be jus a small pa , bu you may ha e a neu al ne wo k o do pa o speech agging ano he neu al ne wo k o do name en i y ecogni ion and ano he ne wo k o pa se sen ences in o ees. E en a mo e challenging p oblem migh be o igu e ou wha is he gene al a chi ec u e we can use so ha we don’ e en ha e o ell he sys em o lea n hese hings. In o he wo ds, a ne wo k o neu al ne wo ks whe e each neu al ne wo k can igu e ou wha i should do on i s own and be use ul o he o e all sys em in a gloal manne . 41 BIBLIOGRAPHY [52] W. S. Mcculloch and W. Pi s. “A logical calculus ne ous ac i i y.” In: Bulle in o Ma hema ical Biology 52.l (1990), pp. 99–115. issn: 00074985. doi: 10.1007/ BF02478259. [53] T. Mikolo , K. Chen, G. Co ado, and J. Dean. “Dis ibu ed Rep esen a ions o Wo ds and Ph ases and hei Composi ionali y.” In: Nips (2013), pp. 1–9. issn: 10495258. doi:10.1162/jml .2003.3.4-5.951. a Xi : 1310.4546. [54] T. Mikolo , K. Chen, G. Co ado, and J. Dean. “E icien Es ima ion o Wo d Rep esen a ions in Vec o Space.” In: CoRR abs/1301.3781 (2013). u l: h p: //a xi .o g/abs/1301.3781. [55] A. Mnih. “Lea ning wo d embeddings e icien ly wi h noise-con as i e es ima- ion.” In: Nips (2013), pp. 1–9. issn: 10495258. doi: 10.3115/ 1/P14-1023 . a Xi : a Xi :1011.1669 3. [56] Y. Nes e o . “A me hod o sol ing a con ex p og amming p oblem wi h con e - gence a e O (1/k2).” In: So ie Ma hema ics Doklady. Vol. 27. 2. 1983, pp. 372– 376. [57] A. Ng. “1. Supe ised lea ning.” In: Machine Lea ning (2012), pp. 1–30. [58] C. Noam. “Syn ac ic S uc u es.” In: (1958). doi: 10.1515/9783110218329 . u l:h p://www.deg uy e .com/ iew/p oduc /41408. [59] B. Pang, L. Lee, and S. Vai hyana han. “Thumbs up?: sen imen classi ica ion using machine lea ning echniques.” In: P oceedings o he Con e ence on Em- pi ical Me hods in Na u al Language P ocessing (2002), pp. 79–86. issn: 1554- 0669. doi: 10 . 3115 / 1118693 . 1118704 . a Xi : 0205070 [cs] .u l: h p : //po al.acm.o g/ci a ion.c m?id=1118693.1118704. [60] J. Penning on, R. Soche , and C. D. Manning. “GloVe : Global Vec o s o Wo d Rep esen a ion.” In: (2014), pp. 1532–1543. [61] J. B. Pollack. “Recu si e Dis ibu ed Rep esen a ions.” In: A i . In ell. 46.1-2 (No . 1990), pp. 77–105. issn: 0004-3702. doi: 10. 1016/0004 - 3702(90) 90005-K.u l:h p://dx.doi.o g/10.1016/0004-3702(90)90005-K. [62] N. Qian. “On he momen um e m in g adien descen lea ning algo i hms.” In: Neu al Ne wo ks 12.1 (1999), pp. 145 –151. issn: 0893-6080. doi: h p: / / dx . doi . o g / 10 . 1016 / S0893 - 6080(98 ) 00116 - 6 .u l: h p : / / www . sciencedi ec .com/science/a icle/pii/S0893608098001166. [63] H. Ri e and T. Kohonen. “Sel -o ganizing seman ic maps.” In: Biological Cybe - ne ics 61.4 (1989), pp. 241–254. issn: 03401200. doi:10.1007/BF00203171. [64] F. Robinson A. J. Fallside. “The u ili y d i en dynamic e o p opaga ion ne - wo k.” In: (1987). 48 BIBLIOGRAPHY [65] F. Rosenbla . “P inciples o Neu odynamics. Pe cep ons and he Theo y o B ain Mechanisms.” In: A chi es o Gene al Psychia y 7 (1962), pp. 218–219. issn: 0003-990X. doi:10.1001/a chpsyc.1962.01720030064010. [66] D. E. Rumelha , G. E. Hin on, and R. J. Williams. Lea ning ep esen a ons by back- p opaga ing e o s. 1986. doi:10.1038/323533a0. a Xi : a Xi :1011.1669 3. [67] G. Sal on, A. Wong, and C. S. Yang. “A Vec o Space Model o Au oma ic Indexing.” In: Commun. ACM 18.11 (No . 1975), pp. 613–620. issn: 0001-0782. doi: 10.1145/361219.361220 .u l: h p://doi.acm.o g/10.1145/361219. 361220. [68] J. J. Schmidhube . “Lea ning Complex, Ex ended Sequences Using he P inciple o His o y Comp ession.” In: Neu al Compu . 4.2 (1992), pp. 234–242. issn: 0899-7667. doi: 10 . 1162 / neco . 1992 . 4 . 2 . 234 . a Xi : 1103 . 0398 .u l: h p://dx.doi.o g/10.1162/neco.1992.4.2.234. [69] R. Soche . “Recu si e Deep Lea ning o Na u al Language P ocessing and Compu e Vision.” In: PhD hesis Augus (2014). [70] R. Soche , C. D. C. Manning, and A. Y. A. Ng. “Lea ning con inuous ph ase ep- esen a ions and syn ac ic pa sing wi h ecu si e neu al ne wo ks.” In: P oceed- ings o he NIPS-2010 Deep Lea ning and Unsupe ised Fea u e Lea ning Wo kshop (2010), pp. 1–9. issn: 0302-9743. doi: 10.1007/978-3-540-87479-9 .u l: h p://wuawua.googlecode.com/ iles/Lea ningCon inuousPh aseRep esen a ionsandSyn ac icPa singwi hRecu si eNeu alNe wo ks. pd . [71] R. Soche , E. Huang, and J. Penning on. “Dynamic Pooling and Un olding Re- cu si e Au oencode s o Pa aph ase De ec ion.” In: Ad ances in Neu al In o ma- ion P ocessing Sys ems (2011), pp. 801–809. issn: 9781618395993. u l: h p: //machinelea ning.wus l.edu/mlpape s/pape { _} iles/NIPS2011{ _ }0538.pd { %}5Cnh ps://pape s.nips.cc/pape /4204-dynamic-pooling- and - un olding - ecu si e - au oencode s - o - pa aph ase - de ec ion . pd . [72] R. Soche , B. Hu al, C. D. Manning, and A. Y. Ng. “Seman ic Composi ionali y h ough Recu si e Ma ix-Vec o Spaces.” In: P oceedings o he 2012 Join Con- e ence on Empi ical Me hods in Na u al Language P ocessing and Compu a ional Na u al Language Lea ning M (2012), pp. 1201–1211. issn: 9781937284435. doi:10.1162/153244303322533223. a Xi : a Xi :1301.3781 3. [73] R. Soche , A. Pe elygin, and J. Wu. “Recu si e deep models o seman ic compo- si ionali y o e a sen imen eebank.” In: P oceedings o he . .. (2013), pp. 1631– 1642. issn: 1932-6203. doi: 10.1371/jou nal.pone.0073791 . a Xi : 1512. 03385 .u l: h p://nlp.s an o d.edu/{~}soche /EMNLP2013{ _}RNTN. pd { %}5Cnh p://www.aclweb.o g/an hology/D13-1170{ %}5Cnh p:// 49 BIBLIOGRAPHY aclweb.o g/supplemen als/D/D13/D13-1170.A achmen .pd { %}5Cnh p: //oldsi e.aclweb.o g/an hology-new/D/D13/D13-1170.pd . [74] I. Su ske e . “T aining Recu en neu al Ne wo ks.” In: PhD hesis (2013), p. 101. a Xi : 1456339 [a Xi :submi ]. [75] I. Su ske e , O. Vinyals, and Q. V. Le. “Sequence o Sequence Lea ning wi h Neu al Ne wo ks.” In: CoRR abs/1409.3215 (2014). u l: h p://a xi .o g/ abs/1409.3215. [76] R. S. Su on. “Lea ning o P edic by he Me hod o Tempo al Di e ences.” In: Machine Lea ning 3.1 (1988), pp. 9–44. issn: 08856125. doi: 10.1023/A: 1018056104778.u l:ci esee .is .psu.edu/su on88lea ning.h ml. [77] K. S. Tai, R. Soche , and C. D. Manning. “Imp o ed Seman ic Rep esen a ions F om T ee-S uc u ed Long Sho -Te m Memo y Ne wo ks.” In: Acl (1) (2015), pp. 1556–1566. issn: 9781941643723. doi: 10 . 1515 / pope s - 2015 - 0023 . a Xi : 1503.0075.u l:h p://aclweb.o g/an hology/P/P15/. [78] B. Taska , D. Klein, M. Collins, D. Kolle , and C. Manning. “Max-Ma gin Pa s- ing.” In: P oc. EMNLP (2004), pp. 1–8. [79] O. Vinyals, A. Toshe , S. Bengio, and D. E han. “Show and Tell: A Neu al Image Cap ion Gene a o .” In: CoRR abs/1411.4555 (2014). u l: h p://a xi .o g/ abs/1411.4555. [80] P. J. We bos. “Backwa ds Di e en ia ion in AD and Neu al Ne s: Pas Links and New Oppo uni ies.” In: Lec u e No es in Compu a ional Science and Enginee ing 50 (2006), pp. 15–34. issn: 14397358. doi:10.1007/3-540-28438-9_2. [81] W. Za emba and I. Su ske e . “Lea ning o Execu e.” In: CoRR abs/1410.4615 (2014). u l:h p://a xi .o g/abs/1410.4615. [82] M. D. Zeile . “ADADELTA: An Adap i e Lea ning Ra e Me hod.” In: CoRR abs/1212.5701 (2012). u l:h p://a xi .o g/abs/1212.5701. [83] M. Zhu, Y. Zhang, W. Chen, M. Zhang, and J. Zhu. “Fas and Accu a e Shi - Reduce Cons i uen Pa sing.” In: P oceedings o he 51s Annual Mee ing o he Associa ion o Compu a ional Linguis ics (Volume 1: Long Pape s) (2013), pp. 434– 443. u l: h p://www.aclweb.o g/an hology/P/P13/P13- 1043.pd { % }5Cnh p://www.aclweb.o g/an hology/P13-1043. [84] D. Zipse and R. J. Williams. “G adien -Based Lea ning Algo i hms o Recu - en Ne wo ks and Thei Compu a ional Complexi y.” In: Back-p opaga ion: Theo y, A chi ec u es and Applica ions (1995), pp. 433–486. 50 Appendix A Appendix 1 Le E is he e o ,δh =θE θh , we seek o ind δo ,δC ,δi ,δ˜ C ,δ , , δC −1. δo =θE θo =θE θh θh θo =δh  anh(C ) (A.1) δC =θE θC =θE θh θh θC =δh o (1 − anh2(C )) (A.2) δi =θE θi =θE θC θC θi =δC ˜ C (A.3) δ˜ C =θE θ˜ C =θE θC θC θ˜ C =δC i (A.4) δ =θE θ =θE θC θC θ =δC C −1(A.5) δC −1=θE θC −1 =θE θC θC θC −1 =δC  (A.6) 51 Appendix B Appendix 2 Gi en δh =θE θh we seek o ind δ˜ h h ,δ and δz δ˜ h =θE θ˜ h =θE θh θh θ˜ h =δh (1 −z) (B.1) δ =θE θ =θE θ˜ h θ˜ h θ =δ˜ h h −1Uh(1 −˜ h2 ) (B.2) δz =θE θz =θE θh θh θz =δh (h −1−˜ h ) (B.3) 53