Scribd
Upload
7 views73 pages

Sequential Learning

Parts of speech tagging involves classifying words into categories like nouns and verbs, with words often having multiple tags, necessitating sequence information for disambiguation. The document discusses generative and discriminative approaches to tagging, focusing on Hidden Markov Models (HMMs) for modeling the joint probability distribution of sequences. It covers HMM parameters, inference methods like the Viterbi algorithm, and training techniques, including supervised and semi-supervised models.

Uploaded by

mishranavneet1611
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
7 views73 pages

Sequential Learning

Parts of speech tagging involves classifying words into categories like nouns and verbs, with words often having multiple tags, necessitating sequence information for disambiguation. The document discusses generative and discriminative approaches to tagging, focusing on Hidden Markov Models (HMMs) for modeling the joint probability distribution of sequences. It covers HMM parameters, inference methods like the Viterbi algorithm, and training techniques, including supervised and semi-supervised models.

Uploaded by

mishranavneet1611
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Parts of Speech Tagging * Classifying words into categories such as noun, verb, adjective etc. * Words are ambiguous i.e., they can have more than one part of speech tag. * Example: the word “play” can have two part of speech tags, ‘noun’ or ‘verb’. erb in “I like to play cricket” joun in “| would like to act in that play” * Requires sequence information to disambiguate Sentence tagging: problem formulation * Given an input sequence x, the goal is to predict the corresponding label sequence y’. * For part of speech tagging problem, input sentence is xl, and the part of speech tags are yh * Two types of approaches * Generative approach: _ estimate joint distribution p(x’, yl’) * Discriminative approach: estimate conditional ply | xl) Generative Models * Given training examples (X'"), Y")) fork=1...K. * Model the joint probability distribution + p(X) * For a given x, Choose y that maximizes this probability. + P= argmax p(X,¥) Hidden Markov Model: Graphical view * Example * X= “the dog barks” * Y= 1 Y2 Ys is the corresponding unassigned state sequence, + Maps directly to the part-of- speech tag sequence in the tagging problem (G) ” () x, =the x2 =dog x3 =barks * Inference problem: compute the most probably state sequence given input sequence * y1=determiner, y2=noun, y3=verb — Hidden Markov Models: Generative Story A state is conditionally independent of all other states given the previous state ‘An observation x is conditionally independent of all other observations given the state that generated it the dog barks“ the, ~ the barks* * barks Generate sentence by traversing states and emitting words «/ae Hidden Markov Models: Notation * Let V be the set of all words in the language. + V= {nikon, samsung, images, bright, the ...} * Let S be the set of all states/tags. + $= {det, noun, verb, * Let X be the a sentence in the language XS xl = xyx x34. Xy where x; EV * Let Y be the corresponding state/label sequence + Ys yl = WiW2¥s¥e Yn — wherey, € S Hidden Markov Models: Parameters Example Initial Probabilities Transition Probabilities ay,_,., __Etmssion Probabilities - 8 we ° 5 . =~ a) Ja Tos det Jnoun | verb the [dog | barks S det | or | 99 | .00 det | 40 | 00 0 noun | 04 noun | 30 | 30 | 40 noun | 00 | 015 | 0031 verb | oA verb | 40 | 40 | 20 verb | 00 | .0008 | 020 aetmoun = 0.99 [Link] = 0.40 ee bnoun,barks = 0.0031 Hidden Markov Models: Parameters * The parameters 6 of the HMMs has three components (7, a, b) * Initial Probabilities ty, * my, =P) * Probability of starting from state s; : ms, = P(y1 = Si) * Transition Probabilities ay,_,y, + Byes = POIYe-1) * Probability of transitioning from state s;to state Sm‘ s,s, = Pe = SmlYe-1 = Si) * Emission Probabilities by, x, + Dycare = POLY) + Probability of emitting a word vy at state $) : bsjv, = P(t = Vkl¥e = Sj) o/ue /ae Hidden Markov Models: Modelling * Likelihood * po(X1..-Xn, Ya -Yw): Probability of the data (input and corresponding state sequence given the parameters) * First-order HMM approximation + Po(Xiy-Xne Yar on) = PO) * Palys) * Me PUel yea) * Pelyd) * Markov process: A state is conditionally independent of all other states given the previous state POU Ye-nye-2r-¥s) = POLY) * Observation independence: The output observation x(t) depends only on the state that produced the observation PURI Ytete-sYareXtnae--X1) = POHIYD * Likelihood over observed data: * Po (X1--Xw) = Lyn Por Xwe Ya Iw) Hidden Markov Model * Working with HMMs requires the solution of three problems: * Inference/Decoding: Given an observation sequence and an HMM, determine the most probable hidden state sequence * Likelihood: Determine the overall likelihood of an observation sequence X = (x1 Xz %3X4 ...Xy) being generated by an HMM. * Training: Given an observation sequence and an HMM, learn the best HMM parameters #/ae HMM inference 27 tag sequences possible ! = 27 paths HMM Inference: Viterbi Algorithm Dynamic Programming a 1. 5s(1) = te Boxy ee + Probability of starting the state sequence with a particular state s and emitting x, at the first position 7 2 Ss, (t) = Dgiyacp MAX Sg, (E— 1) * As,sq + Best probability of reaching Sm at location (t) and emitting x, 3 G5,,(t) = argmaxs, bs, (t — 1) * Asis + Best previous state before reaching s,, at location (t) #/ae veo bre tet HMM inference: Viterbi Algorithm Ys Let 6,..,(2) represent the probability of reaching the state ‘noun’ taking the best possible path and generating observation ‘dog’ «/ae HMM inference: Viterbi Algorithm x the dog barks Probability of reaching a state in the best possible way Snoun(2) = MAX{ Saet(1) * Aer, Snoun(t) * Sverv(1) * #/ae HMM inference: Viterbi Algorithm Ys The last tag of the most likely sequence o(T+1) = ARGMAX{ Si4er(3), Snoun(3), Svern(3) } «/ae Likelihood * Goal: determine pg (x1...xy) = Zyy Po CV Yn) * Sum over all possible state sequences that could result in the observation sequence X * How many paths calculations? NN: number of HMM states T: length of observation Computation complexity of multiplication: O(2T NT) The Forward algorithm reduces this to O(TN2) o/ue Forward Algorithm The probability of observing the observation sequence x; ...x,, and being in state “s” at time t as (€) = Po (Xr Xe Ye = 8) * Dynamic Programming L a(1) =m, bs, Aj " + Probability of starting the state sequence _ oe with a particular state oo. SDSGD) 2 Ais, (C) = Bsyprg * sy ts (t= 1) * 5,5 5) + Probability of reaching Sm at location (t) Rather than enumerating each sequence, compute the probabilities recursively (exploiting the Markov assumption) 3. Likelihood po(x1 Xt) = Ls, %s, (T) /ae tH @ =) Backward Algorithm To estimate the state occupation probabilities itis useful to define (recursively) another set of probabilties—the Backward probabilities 7 Be (©) = Poy Xes1 Xn l¥e = 8) The probability of future observations given that HMM is in state "s” at time t * Dynamic Programming =@ =O 1 B(T)=1 Bu NK beko * Final probability 9 ee — Beak 2 Bs (EC-V) = Ws Bom (* Osisin * Psmace + Probability of the state sequence from position t after visiting states, at position t-1 3 Likelihood po (xy Xt) = Lisp Bopp (1) * sy * Psy ey “/ae Hidden Markov Models: Training * Supervised model + Used when the entire training data is labelled i.e., all the input sequences are associated with an output sequence. * Here, the input sequences are labeled by a human expert in the domain. * Semi-supervised model * Used when part of the training data is labelled. * There is a huge amount of unlabeled data. HMMs: Supervised model * For agiven x1,..Xy , find “@” that maximizes the likelihood Do (X1-+- Xn Va--- Yn) * Here, the input sequence is associated with a corresponding state sequence. * Recall the HMM approximation © Po 1. -Xn Ya Yu) = PCr) * Priya) * Whe p(vel ya) * Ply) * Rewrite in terms of the parameters and observed states + Dot AN Vas oY) = Moy * Msp syy [sys] AS * Tsyvy [Psy vy] PO) HMMs: Maximize likelinood * For simplicity, ignore initial probability parameter. * Objective is to find the parameters — and BS vp that maximizes the following expression: THe syx [spsgl@EU™ 4 Tyg [Bs vy] POP) SLSm #/ae #/ae HMMs: Constraints * The parameters a8 sm and BS vy are probabilities. * Hence, + For each $1, Disin 1.5my = 2 * For each sj, Dv, DE vy =1 + For each state, different optimization functions are defined for both transition and emission parameters (Next Slide). HMMs: Constrained Optimization Problems TRANSITION PARAMETERS *Foreachs, * Maximize log Ms,5,, [49,5 ,]°@°e™ * Such that, Ys, 4s,.5m = 2 EMISSION PARAMETERS * For each Spr + Maximize 10g Mey, [B9, 4] 05") + Such that, Dy, b§n, =1 o/ae HMMs: Use Lagrange Multipliers TRANSITION PARAMETERS * For each s), + Maximize Yis,s,,Ca(SiSm) 10g G3,sq_ + Aa(Zsm Asm — 1) EMISSION PARAMETERS * For each Sj * Maximize Lsyvelo( Sj v_) log Dove + Ay (Loy B85 -1) o/ae HMMs: Differentiate and equate to zero TRANSITION PARAMETERS * Differentiating DsismCa(SiSm) log [Link] + Aa(Esin 295m — 1) and equating to 0 gives us: ‘ noe falSusm) 4 4 = 0 (EQUATION 1) asism EMISSION PARAMETERS * Differentiating LsyrpCo (Sj. Ve) log vg, ve + An(Dvy v8, vm, ~ 1) and equating to 0 gives us: colfye) +Ay =0 (EQUATION 2) Sj Pe o/ue HMMs: Rearranging terms ‘TRANSITION PARAMETERS * Rearranging and summing both sides over $,, in (EQUATION 1) * Ls CalS Sm) =-Aa Ls 8 ,5m =" Aa + Implies + da = 'Sm Ca(S Sm) (EQUATION 3) EMISSION PARAMETERS * Rearranging and summing both sides over vy in (EQUATION 2) + Loy Co(Sp Vk) =~ An Loy B04 =~ Ad + Implies + Ay = — Loy Co(5p-%) (EQUATION 4) o/ue HMMs: Final computation of parameters ‘TRANSITION PARAMETERS * Substituting value of Ag (= —Ys,,Ca(SiSm)) in (EQUATION 1) a(Si-Sm) ao. = Fsusm =F, CalSiSm) EMISSION PARAMETERS: * Substituting value of A, (= —Lv, ¢p(sj,v%)) in (EQUATION 2) po = (sir) i CT) o/ue o/ue HMMs: Parameter computation in words ‘TRANSITION PARAMETERS * Probability of transitioning from state s; to Sm oe 455m = EMISSION PARAMETERS # Number of transitions from state s1 to Sm # Total count of state s; * Probability of emitting word v;, from state s; po, = 5.0% = # Number of emissions of word vx from state sj # Total count of state sj HMMs: Semi-supervised model * For agiven x1,..Xy , find “@” that maximizes the log-likelihood log pg (x1... Xy) on the unlabeled dataset * Direct Optimization is not tractable as state sequence is “hidden”. + Need to sum over a large set of possible state sequences (unlike supervised model) + log po (%1...%w) = 10g Lyx .yy Po (Xt -- X01 Yn) * EM Algorithm (Iterative Algorithm) to maximize likelihood. /ae HMMs: Expectation step or E-step * Define auxiliary function as expectation over hidden sequences 84 Ey! ynlxyaxy | 108 Po Or XY Yn) | a + . kr hidden + In each iteration 7 + E-step: Compute Expectations over “hidden” sequences give current parameters 0; * M-step: Given current parameters 6; , compute parameters 6,4 that maximize log-likelihood Bian = argmaxy Ey! yy) x,y L108 Po (X= XNI1 Iw) | “/ae HMMs: Objective function * Objective function + p% [ logpe (1) + log pe (xaly1) + Yandnl Xan © EMS (log po (Vel Ye-1) + log po(%elye) ) 6 : = Ey yl xynxy Hog Pe 1)] | pone Et ‘yul xxaty LOB Po(Vel Ye-1)] "Peston of Sum = Sum of Expectations 8 Fete Ey yt x.y Hos Poelye) ] o/ue HMMs: Optimization related to initial prob. * OBJECTIVE FUNCTION 1 8 ESE yn x yuty HOB POO) = Zs Po = sit Xn) * 1089 (1 = 5) = Ys po = six ..xw) *logae Posterior Model parameter * Let’s first see how the posterior is computed .. “/ae HMMs: Posterior computation * po, = SlX1 XN) % Po; (%1 XW Mt = S) © po, (X1 Xe Ve = S,Xt41 Xn) Ys (C) pe, (1 Xe Ve = S) * Po, Xe41 XM = 5) Ltt : | : I © BO) Forward Probability, Backward Probability * Po, = Six, xy) % as (t) * Bs (t) “Teas O * Bs (0) —aa o/ae Back to OBJECTIVE FUNCTION 1. + Maximize Ds po, = 51x xy) *log 2 1. Introduce lagrange multiplier to constraint pg to be a probability distribution * Ls (po,01 = Slt %y) *logm?) +4 (Ls —1) 2. Differentiate [Link] 7, and equate toO * por = $1X1 xy) * 1/m8+d = 0 (EQUATION 5) * po (1 = Six1 %w) = -A* ne * Ls Par = Slx Xv) = —A* Dem? tae 3. Substitute 2 =-1 in (EQUATION 5) Se = 0 * Bi) E> Poa = $l mn) = Fee) o/ue ea HMMs: Opti * OBJECTIVE FUNCTION 2 Tne Ee yl xray HOB Poel Ye-1)] ansition prob. =EtLe Ls, Lsm Po; Ve-1 = Sve = SmlX1 Xn) * 10g Pol Ye = Sml¥e-1 = Sd) =Ethe Lsy Ls Po; (t-1 = Sve = SalX1 Xn) * 10g a8,s,, 1 , Posterior Model parameter . N. = 7 a = Ys Btee Ls Pap We-1 = Sv Ve = Smtr XN) * 10g af, | + For each sj, we have a different optimization problem «/Ee HMMs: Posterior computation for OBJECTIVE 2 * Pa, Vt-1 = SuVe = SmlX1 +X) X pe; (4 Xt-p Vea = SuXe Ve = Sms Xe41 Xn) X Po, (Xo Mtn Vena = $1) * Osysin * Dspace * Po; Kova Xn [Ve = Sm) + Forward Probability + Backward Probability an a, (1) Bay (©) sem Probability of being in state s; at time t-1 and s,, at time t, given model parameters and observation sequence Introducing Lagrange multiplier, differentiating and solving, we get: Doi e-1=SUHe=SmIx1XN) —_— Eke Syst) Po, t-1=SUYt=SmlX1 XN) Ys Ble2 §5,5m (6) expected number of transitions from state s1 to Sm expected number of transitions from state s, o/ue HMMs: Optimization related to emission prob. * OBJECTIVE FUNCTION 3 8; + ee Ey wut xyaxy Hog Poel yo] =EtLe Ls Po, (Ve = slx1 xn) * log bsx, * Introducing Lagrange multiplier, differentiating and solving, we get: Yel ee==v4) + Yo)(t) © Ds vy = FT Malt) isthe prob of being in 5; at time t, given entire observation sequence L Ler) _ expected number of times in state s_and observing symbol vx expected number of times in state s1 Applications in speech Speech signal fli MAN sms (gh Featare ete saat, E P(XVsayonaral) =PXWE. BOND. BXand Vi ‘Automatic Speech recognit Acoustic (phone) model [HMM] W" = arg max XW) POW) Acovstic_Language Emission probabilities y y yr Ogs ae ay a0 DO Bak bya ‘emission pdfs Summary * Formulation of HMM * Inference * Likelihood computation * Training url SD) es Sequential Learning PART 2 adie Tn ar) Corea a ste(lald ie Alexa, Amazon ed Topics Attention Mechanisms in LSTMs. Self-Attention and Transformers Subword Modeling, GPT, BERT TS Conclusion wPpwn Sequence-to-Sequence Models * Encoder-Decoder architecture * Training is conducted via Teacher Forcing Je parle francais | speak French Sequence-to-Sequence Models * Encoder-Decoder architecture * Training is conducted via Teacher Forcing Seq2Seq Overview Je parle francais | speak French Attention Mechanisms Important Unimportant Attention Mechanisms in RNNs Bahdanau Attention for} Additive Attention mE -i-B- is Cine 7 Other Types of Attention Mechanisms Alignment Scoring functions in Luong Attention * Dot Z score_alignrnent = H_encoder * H_decoder *General 4 score_alignment=W*(H_encoder * H_decoder) *Concat ¢ score_alignment=W*tanh(W_combined(H_encoder+H_decoder)) Issues with Recurrent Models * Linear Interaction Distance : Dependencies between words are are considered in a linear order from left-to-right (or right-to-left) 5 Ex. “there is a dog in the park next to my house and it has sharp teeth” The word “it” refers to the word “dog” and this dependency is not easy to capture because of the distance between the words. * Lack of Parallelizability : The linear order makes the computation serial and you cannot compute the output for a certain word unless all the previous words have been processed. Transformer - Architecture Transformer - Architecture NPUT étudiant taken fom hts Transformer — Self Attention Input Embedding, Queries Values Thinking 3 Machines yoo ie Peas} ofa we 7. ?*i [i nt we Poa v2 Ee w Image stake rom tps fatammacgthubofustrated transformer/ Transformer — Self Attention + The query, key and value vectors represent the different roles for each input word vector y’ Ea a =a ores Opened Peo em ars) Doran * Database index such as a primary index stores keys that will help us retrieve the corresponding value. Transformer — Self Attention * Similar to a database, we try to retrieve the values for queries with the help of relevant keys. * Database Query — query vector * Database Key — key vector * Database Value — value vector Transformer — Self Attention Input Embedding Queries Keys Values Score qe ky = 112 Images ake rom hps/falammac github iofusrate-ransforme/ Transformer — Self Attention Softmax eo x “ Ze ve Value sum > >» Contextual Representation of the word Images taken rom htps/alammarehtub fisted transformer] Transformer — Multi-headed Attenti 64 512 «64 51264 Bs He 512 x 64 Wo? ‘Wok Woy 512 a FA i : 51x64 oS Fea 512 x64 on WY mage taken rom ep:/fslamemar gb o sre vantormer] Since each query, key, value matrix is of size 64, we can have 8 Attention heads to get an output vector of size 512 Transformer — Positional Embedding * Self-Attention in itself does not deperid on the order of words * To account for the position of words, Position embedding is added onto the original input vector EMBEDDING WITH TIME SONAL ISIS +o sooo Posimionat | as .oooo emecooincs x; (INI | a inpur Je suis étudiant Transformer — Encoder Residuals * we add the self-attention output to the input vector to form a Residual Connection ENCODER #1 Self-Attention xi a] Thinking Machines Transformer — Encoder Residuals : * we add the self-attention output to the input vector to form a Residual Connection (feed Forward) iia pra Z ayertorm( =, a ENCODER #1 xi a] Thinking Machines Transformer — Decoder Architecture a: Cae uate a a, The “Encoder-Decoder Attention” is like multi-head attention where the queries corresponds to previous decoder output word and keys, values are taken from encoder words Self-Attention is only allowed for earlier positions. Mask future positions by—inf before the softmax step Subword Modelling * Traditional Models assumed a finite vocab and any new word (or) variation is treated as * Vocab can be large especially if the language exhibits complex morphology * To deal with these problems, we have Subword modeling : Learning on vocabulary of parts of words/subwords * “unfortunately” = “un” + “for” + “tun” + “ate” + “ly” Subword Modelling * Traditional Models assumed a finite vocab and any new word (or) variation is treated as * Vocab can be large especially if the language exhibits complex morphology : * To deal with these problems, we have Subword modeling : Learning on vocabulary of parts of words/subwords * “unfortunately” = “un” + “for” + “tun” + “ate” + “ly” Subword Modelling * Byte-Pair encoding [Sennrich et al.. 2016, Wu et al., 2016] : Find a way to represent entire text dataset with least number of tokens Step 0. Initialize vocabulary. Step 1. Represent each word in the corpus as a combination of the characters along with the special end of word token . Step 2. Iteratively count character pairs in all tokens of the vocabulary. Step 3. Merge every occurrence of the most frequent pair, add the new character n-gram to the vocabulary. Step 4. Repeat step 3 until the desired number of merge operations are completed or the desired vocabulary size js achieved (which is a hyperparameter Subword Modelling Other forms of Subword embeddings: * Unigram Subword Tokenization ([Link] pdf; * WordPiece [Uses the likelihood rather than count frequency to merge words] * SentencePiece * More on Tokenization : [Link] Pretraining through language modeling * Model p(w, | W;.,-), the probability distribution over words given their past contexts : [Link] goes to make tasty tea END Iroh goes to make tasty tea Image taken from hitp://web stanford edu/elass/es224n/sides/es224n-2021-ecturei0-pretraning pa Generative Pretrained Transformer (GPT) : Pretraining Decoder * GPT is a model that conducts pretraining for a Transformer Decoder * GPT architecture : 12 layers, 768-dimensional hidden state, 40,000 bpe codes * GPT is trained on BookCorpus Input format for GPT ¢ Translation task: C [START] what is your name [DELIM] GFSRT ale FAT B [EXTRACT] Finetuning GPT * Sentence classification task Take the output of last word and train a linear layer on top ofit one Linear) Ab Ray weehe Wy Wr @ * For sequence prediction, It is similar to pretraining and we try to learn certain output for each input word * GPT showed good results on six of eight GLUE tasks. nage aan om hp tnd ules Anadeetn 221 ee peacoat BERT : Pretraining Encoder * Encoder in the transformer formulation gets bi-directional context, so we can’t use language modelling (why 2). BERT uses WordPiece tokenizer to extract the sub-words for the text. + Masked Language Modeling(LM) > Replace some words with [MASK] token and try to predict these words BERT Architecture Bert-base: 12 layers, 768- week. for inviting last <2> 2 conruptng Spans tom the Paper Conclusion * We have discussed on various topics, starting from the concepts of attention and self-attention in deep learning. Then we showed how these concepts are applied in State-of-the-Art Models such as Transformers, BERT, TS * The underlying theme behind these Models is pre-training and it has greatly improved performance on downstream fine-tuning tasks. * Ina practical system such as Alexa, we use such pre-trained models and fine-tune on customer facing tasks to understand the User Intent, NER etc.

You might also like