WIXLIB

Module L101: Machine Learning for Language ProcessingNaive Bayes’ Classifier Simple form of generative model:– joint distribution: P (x, ωj ) P (ωj )– classification: P (ωj x) P (ωj )QdQdi 1 P (xi ωj )i 1 P (xi ωj ) Elements of the feature vector conditionally independent given the classωx1x2 write as a Bayesian Network (BN)x3––––shaded observed variableunshaded unobserved variablecircle continuous variablesquare discrete variable More on Bayesian Networks (and Graphical Models) later in the moduleCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science14

Module L101: Machine Learning for Language ProcessingProbability Distributions For generative models need to decide form of conditional distribution P (x ωj )– (d-dimensional) feature vector may be discrete or continuous Discrete distributions (probability mass functions) - primary interest here– Multivariate-Bernoulli distribution: xi {0, 1},P (x ωj ) dYpxjii (1 pji)1 xi ;0 pji 1i 1– Multinomial distribution: xi {0, . . . , n}n!P (x ωj ) QddYi 1 xi ! i 1pxjii ,n dXxi,i 1dXpji 1,pji 0i 1 Continuous distribution, xi [ , ], less interest on this moduleCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science15

Module L101: Machine Learning for Language ProcessingMaximum Likelihood Training The class-conditional distribution P (x ωj ) needs to be trained– only the data from the class of interest used– for class ωj with n training examples x1, . . . , xnλ̂j argmaxλ(nYP (xτ λ)τ 1) argmaxλ(nX)log (P (xτ λ))τ 1 For the multivariate Bernoulli distribution: λj {pj1, . . . , pjd}λ̂j argmaxλj(n XdXxτ i log(pji) (1 xτ i) log(1 pji)τ 1 i 1Differentiating wrt λj and equating to zero yields: pji Cambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science1n)Pnτ 1 xτ i16

Module L101: Machine Learning for Language ProcessingImproving the Basic Model Incorporating a Prior: What happens if a count is zero?– simplest solution to initialise counts with a constant α: for Bernoullipji 1α nα nXxτ iτ 1!– more details on this topic in discussion of language models Mixture Model: more “powerful” distribution combining multiple distributions:P (x ωj ) MXP (cm ωj )P (x cm, ωj )m 1– component cm has prior, P (cm ωj ) and probability distribution, P (x cm, ωj )– more details on this topic in the lectures on graphical modelsCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science17

Module L101: Machine Learning for Language ProcessingLimitations of Generative Models An obvious question is:If Bayes’ decision rule minimises average probability of errorand we can train generative models - why do anything else?Plus often able to estimate parameters simply by counting! The classifier is the minimum error classifier only if––––form of the class-conditional distribution is correcttraining sample set is infinitetraining algorithm finds the correct parameterscorrect prior is usedNone of these are usually true!, but still used for some tasksCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science18

Module L101: Machine Learning for Language ProcessingDiscriminative Models Classification requires the class-posterior P (ωj x)– can just directly model the posterior distribution– avoids the complexity of modelling the joint distribution P (x, ωj ) Form of model called a discriminative model Many debates of generative versus discriminative models:––––discriminative model criterion more closely related to classification processnot dependent on generative process being correctjoint distribution can be very complicated to accurately modelonly final posterior distribution needs to be a valid distribution Initially consider classifiers that yield linear decision boundariesCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science19

Module L101: Machine Learning for Language ProcessingLinear Decision Boundaries Decision boundaries partition the feature-space into regions– associated with each region is a class label– linear decision boundaries use:lines (d 2); planes (d 3); hyper-planes (d 3) to determine regions Initially only binary (2-class) classification tasks will be consideredConsider linear decision boundary whereg(x) wTx bClass 1x2Decisions are made based onDecide class ω1 g(x) 0class ω2 g(x) 0Parameters of decision boundary b & wCambridge UniversityEngineering DepartmentMPhil in Advanced Computer ScienceClass 2x120

Module L101: Machine Learning for Language ProcessingLogistic Regression/Classification For binary classification - logistic regression classification is a simple form– class posterior probability a function of the perpendicular distance to thedecision boundaryexp( (wTx b))P (ω2 x) 1 exp( (wTx b))1;P (ω1 x) T1 exp( (w x b))– linear decision boundary - need to find λ {w, b}. Often parameters combined into single vectorsx̃ Cambridge UniversityEngineering Departmentx1 ,w̃ wb ,w̃Tx̃ wTx bMPhil in Advanced Computer Science21

Module L101: Machine Learning for Language ProcessingForm of Posterior The posterior distribution of class 1 and perpendicular distance to the decisionboundary a sigmoid function11101000.90.81P (ω1 x) 1 exp( ρz)0.70.60.5where ρz wTx b0.40.30.2 diagram shows variations with ρ0.10 10 8 6 4 20246810 Posterior is only a function of perpendicular distance to the decision boundary Altering the value of the priors simply moves the sigmoid to the right or leftCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science22

Module L101: Machine Learning for Language ProcessingMaxEnt Model A multi-class generalisation of logistic regression is the MaxEnt model 1TP (ωj x) exp wj x bj ;ZZ KXexpwkTx bkk 1 Z is the normalisation term A more general form of MaxEnt model considers class-specific features– can use a feature function of the observation and class, f (x, ωj )1P (ωj x) expZDXi 1!λifi(x, ωj ) ;Z KXk 1expDXi 1λi fi(x, ωk )!– D is the size of the combined feature-vector for all classesCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science23

Module L101: Machine Learning for Language ProcessingMaxEnt Model (cont) Feature-functions can represent the simple linear form λ w1b1.wKbK ; f (x, ω1) x10.0 ; f (x, ωk ) 0.x10. Relationship to logistic regression (note binary case, restricted feature function) Texp w1 x b1 P (ω1 x) TTexp w1 x b1 exp w2 x b2 Cambridge UniversityEngineering Department11 exp ((w2 w1)Tx (b2 b1))MPhil in Advanced Computer Science24

Module L101: Machine Learning for Language ProcessingDiscriminative Model Training Similar criterion to ML-training of generative models– maximise posterior of the correct class (rather than generating the data)λ̂ argmaxλ(NX)log (P (yτ xτ , λ))τ 1where yτ {ω1, . . . , ωK } and training data {(x1 , y1), . . . , (xN , yN )} Useful properties– multi-class training of parameters λ– all training examples used to derive all the model parameters– different features may be used for different classes(generative model requires same feature-space)Cambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science25

Module L101: Machine Learning for Language ProcessingTraining MaxEnt Models Training MaxEnt model is a convex optimisation problem– one solution to train parameters is generalised iterative scaling(l 1)λi(l) λi 1logCPNτ 1 fi (xτ , yτ )PN PK(l)τ 1k 1 P (ωk xτ , λ )fi (xτ , ωk )!– iterative approach (parameters at iteration l are λ(l)) (strictly) requires that the features add up to a constantDXfi(xτ , ωk ) C, τ, ki 1– extensions relaxes this requirements, e.g. improved iterative scalingCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science26

Module L101: Machine Learning for Language ProcessingDiscriminative Functions Aim to directly minimise the error rate– all we care about for classification– don’t need to determine class posteriors, P (ωj x), just decision boundaries Wide range of possible optimisation schemes/criteria (Duda, Hart and Stork)– perceptron algorithm described in this lecture Some disadvantages to not obtaining a posterior probability: issues with– reject option: don’t quote answer if posterior below a threshold– compensating for class priors: priors are sometimes estimated on differentdata (e.g. language models)– combining models: sometimes build and combine multiple systems usingposteriors (could use voting .)Cambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science27

Module L101: Machine Learning for Language ProcessingCost Functions Need to decide on the criterion, cost function, to train the decision boundaryCost 1 (incorrect)Cost x b (Incorrect)Cost 0 (correct)Cost 0 (correct)bideal cost functionperceptron cost function Would like to minimise the error rate - ideal cost function above shown above– differentiating this function yields a delta-function– awkward to train (consider gradient descent with this) An alternative is the perceptron algorithm, which is differentiable– the distance of incorrect observations from the decision boundaryCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science28

Module L101: Machine Learning for Language ProcessingPerceptron Criterion The perceptron criterion cost for a sample is– zero when correctly classified– perpendicular distance to the decision boundary, g(x), when misclassified The distance to the decision boundary for misclassified samples– for class ω1, g(x) 0– for class ω2, g(x) 0 To simplify training the extended training observations, x̃τ , are normalisedxτ x̃τ , belongs to ω1 x̃τ , belongs to ω2w̃Txτ 0correctly classifiedCambridge UniversityEngineering Departmentw̃Txτ 0misclassifiedMPhil in Advanced Computer Science29

Module L101: Machine Learning for Language ProcessingPerceptron Algorithm The perceptron algorithm can be used to find w̃1. Choose initial value w̃(0), l 0; (w̃(l) estimate at iteration l)2. Obtain the set of mis-classified points, Y (l), using current estimate w̃(l),i.e. find all the points where w̃(l)Txτ 03. Minimise the total perceptron criterionE(w̃) X( w̃Txτ )xτ Y (l)update rule isw̃(l 1) w̃(l) Xxτxτ Y (l)4. If converged (Y (l) is empty), or max iter, STOP; else l l 1 goto (2).Cambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science30

Module L101: Machine Learning for Language ProcessingPerceptron Algorithm (cont) For linearly separable data:– a linear decision boundary that correctly classifies all points exists– in this case using the algorithm guaranteed to find a solutionw̃(l 1) w̃(l) Xxτxτ Y (l)– automatically stops when the set of mis-classified points is empty. Two forms of update may be considered:– batch update: all the data is presented for each iterationthe decision boundary is only updated after all the samples have been seen– sequential update: data is presented one sample at a timethe decision boundary is updated after each sampleCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science31

Module L101: Machine Learning for Language ProcessingPerceptron Solution Region Each sample x̃τ places a constraint on possible location of solution vector. w̃Tx̃τ 0 defines a hyperplane through the origin on the “weight-space” ofw̃ vectors with x̃τ as a normal vector. Normalised data: solution must be on the positive side of every such hyperplane– it is not unique (if it exists) and lies anywhere within solution region Figure shows solution region for un-normalised and normalised data (DHS).– note change of notation: a w̃, y x̃ (left) y x (right)solutionregion y2solutionregion y2aaa tin gseparCambridge UniversityEngineering Departmentp la n ey1aneg" ply1ratin"sepaMPhil in Advanced Computer Science32

Module L101: Machine Learning for Language ProcessingStructured Data So far considered the case where the labels (training and test) are “scalar”– not always the case - consider translationSpeech recognition is difficult Lleferydd cydnabyddiaeth yn anodd Consider the number of possible classes– every possible possible “sentence” translation - vast This is also an issue with the possible features to extract– can consider pairs of words, triples etc etcNeed to make conditional-independence assumptionsCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science33

Module L101: Machine Learning for Language Processing”Theory” Part of Module These lectures give underlying theory for the seminars and associated papers Graphical Models––––––Bayesian networks and graphical models (beyond naive Bayes)Markov chains (including language modelling)mixture models (including Gaussian mixture models)hidden Markov models (including Viterbi algorithm)conditional random fieldsexpectation maximisation and variational approaches Support Vector Machines– large margin training and dual representation– kernel methods (including sequence kernels) Clustering– unsupervised approaches (including K-means clustering)– latent Dirichlet allocationCambridge UniversityEngineering DepartmentMPhil in Advanced Computer Science34

Module L101: Machine Learning for Language Processing Training and Evaluation Data The basic machine learning framework has two sets of data: 1. Training data: is used to train the classifier - data may be: - supervised: the correct classes of the training data are known. - unsupervised: the correct classes of the training data are not .