ICMLA 2010 Tutorial On Sequence Labeling: Generative And Discriminative .

Binary Classifiers Regularized empirical risk (RER) minimization I Unifying framework for different linear classifiers Consider a predictor function fθ (x) : IRd IRm that can be used to predict output labels y from features x, m is the number of prediction values (discriminants) For the linear binary classification problem, m 1, θ w̃ and fw̃ (x) w̃T x̃ Define a “loss function” L : IRm Y IR that measures the cost of prediction We define the expected risk as follows: Z R(θ) L (fθ (x), y ) p(x, y )dxdy Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers Regularized empirical risk (RER) minimization II Since the joint distribution p(x, y ) is usually unknown, we can find an estimate of the risk from the training data called the “empirical risk” which needs to be minimized wrt the parameters θ N 1 X L (fθ (xi ), yi ) R̂(θ) N i 1 This can be interpreted as the training set error rate Usually we add a penalty term Ω(θ) for the parameters which penalizes complex (or large) predictor functions to arrive at what is called the “regularized empirical risk” N 1 X R̂(θ) L (fθ (xi ), yi ) Ω(θ) N i 1 Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers Regularized empirical risk (RER) minimization III Note that “structured risk” minimization is similar where the regularization function is replaced by the Vapnik-Chervonenkis (VC) confidence of the predictor function (which is also a measure of complexity of the predictor) All previous methods (FLD, LR and SVM) can be seen as variants of regularized empirical risk minimization by utilization of a different loss function as we elaborate in the following slides Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers Loss functions I RER for linear binary classification is as follows: R̂(w̃) N 1 X T L w̃ x̃i , yi Ω(w̃) N i 1 Using different loss functions yield different methods for linear binary classification Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers LS loss L(w̃T x̃, y ) (w̃T x̃ ty )2 Here ty are regression targets for each class in least squares regression. Using LS loss with no regularization is equivalent to FLD N when ty y where Ny is the number of samples in class y Ny [Bishop, 2006] LS-SVM uses ty y and a quadratic regularizer [Suykens and Vandewalle, 1999]. Without regularization, LS-SVM is similar to FLD Regularized LDA [Friedman, 1989] is equivalent to using a regularization function in the RER framework Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers BNLL loss n o L(w̃T x̃, y ) log 1 exp y w̃T x̃ Using binomial negative log-likelihood (BNLL) loss function with no regularization is equivalent to performing a logistic regression classification Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers Hinge loss L(w̃T x̃, y ) (1 y w̃T x̃) Using hinge loss function and a regularization function Ω(w̃) λw̃T Dw̃ (where D is a diagonal matrix with all ones in the diagonal except for the last entry which is zero) is equivalent to performing an SVM classification Note that Ω(w̃) λw̃T w̃ is also used which is slightly different (in liblinear [Fan et al., 2008]) Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers Other loss functions There are many other loss functions defined in the literature [LeCun et al., 2006] Huber-hinge loss is one which smooths the edge of the hinge loss so that we end up with a differentiable loss function Squared-hinge loss is the square of the hinge loss which is also differentiable (called L2 -SVM) Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers Loss function plots Illustration of loss functions L(z) absolute hinge squared hinge huber hinge logistic ls loss value, L(z) 1 0.5 0 0.5 0 0.5 1 1.5 z ywTx Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010 2

Binary Classifiers Regularization functions I Although originally FLD and LR do not use regularization, it was shown to be beneficial in all cases Typically an L2 -norm regularization Ω(w̃) λ w̃ 2 is used λ is a hyper-parameter that needs to be determined (next slide) Regularization helps in all classifiers arguably due to improving test accuracy due to penalizing the complexity of the classifier avoiding overtraining/overfitting avoiding numerical problems in implementation. L1 -norm is used when sparse parameter vectors are desired For example L1 -regularized L1 -SVM is considered in [Mangasarian, 2006]. Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers Estimating the hyperparameters I The hyperparameter λ can be found by grid search on validation data, that is by evaluating the performance of the trained classifier on the validation data Multiple fold cross-validation on the training data can also be performed for this purpose Bayesian “evidence framework” may be used with some losses to find the hyperparameters, this requires re-interpreting the empirical risk optimization as a maximum aposteriori probability (MAP) estimation problem [Hoffmann, 2007] - Bayesian LDA Perturbation analysis may be used [Zheng et al., 2009] Other ad-hoc methods exist as well Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers RER optimization methods LS and logistic losses are differentiable, so primal algorithms such as Newton’s method work very well LS loss has closed form solution For logistic loss, Newton’s method results in iterative re-weighted least squares (IRLS) formulation For hinge loss, one needs to go to the dual QP problem and solve it in the dual For squared-hinge or huber-hinge losses, one can solve it in the primal domain as well libsvm and liblinear are good libraries for solving RER formulations Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers How to obtain nonlinear classifiers? I Sometimes, class data are not separable by a line! 2 Feature 2 1 Replace x with φ(x) which is a nonlinear mapping into a higher dimensional space 0 1 2 3 2 1 0 1 Feature 1 2 If φ(x) is known explicity, you may use it instead of x to solve the problem Use the kernel trick to replace inner products with the kernel function: φ(xi )T φ(xj ) K (xi , xj ) Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Binary Classifiers How to obtain nonlinear classifiers? II No need to know what φ(.) is, if we use the kernel trick (φ can be infinite dimensional) just replace inner products with the kernel function Kernel versions usually solved in the dual, but it was shown it is possible to solve in the primal as well [Chapelle, 2007] We will not focus on kernel versions of these classifiers in this talk! linear classifiers are as good as or better than kernel versions for large scale learning [Fan et al., 2008] Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Outline 1 Sequence Labeling 2 Binary Classifiers 3 Multi-class classification 4 Hidden Markov Models 5 Generative vs Discriminative Models 6 Conditional random fields 7 Training CRFs 8 Structured SVM for sequence labeling Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Multi-class classification Using multiple binary classifiers and combining them (multiple machine) One-vs-all One-vs-one Error correcting output codes (ECOC) Direct multi-class classification (single machine) (explanation next slide) A paper compared these approaches and found that one-vs-one gave the best result (used in libsvm) [Hsu and Lin, 2002] For structured classification, we need direct multi-class classification since almost impossible to enumerate all possible output labels (topic of future lectures) Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Linear multi-class classification Given training data {(xi , yi ) : i [N]} where xi IRd and yi Y [M] xi [xi,1 , xi,2 , . . . , xi,d ]T are feature vectors, yi are class identities Find a set of weight vectors w̃y IRd 1 such that for test data x, we T obtain a score for class y as w̃T y x̃ wy x by Classification is done by ŷ arg maxy w̃T y x̃ Each w̃y represents a hyperplane in IRd 1 Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Geometry of linear multi-class discriminants Rblue Rred Rgreen Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Generative multi-class classification I Given class conditional probability distributions p(x y ) Obtain class posteriors as: p(x y )p(y ) 0 0 y 0 p(x y )p(y ) p(y x) P If class conditional probability distributions are from the exponential family n o p(x y ; θ y ) h(x) exp θ T y t(x) A(θ y ) where θ are the parameters (or transformed parameters) of the pdf, t(x) is the sufficient statistics vector, A(θ) is the log-partition function and h(x) is a base measure independent of the parameters. Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Generative multi-class classification II Then, the conditional likelihood has the form: exp{w̃T y φ(x)} p(y x) P T y 0 exp{w̃y 0 φ(x)} T T and φ(x) t(x)T , 1 where w̃y θ T y , A(θ y ) log (p(y )) This form of the conditional likelihood is called normalized exponential or softmax function. Hence, if we map the features x using the sufficient statistics and add a constant feature, conditional likelihood will have a log-linear form Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Generative multi-class classification III For example, for the Gaussian setup with means µy and equal covariances (known Σ) (multi-class FLD), we get the following θy µy t(x) x wy by Σ 1 µy 1 Σ 1 µy log(p(y )) µT 2 y Exercise: Perform the same analysis when both µy and Σy are different for each class. What are the sufficient statistics and parameters then? Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010 (6)

Multi-class classification Multi-class (multinomial) logistic regression I exp{w̃T y φ(x)} Assuming p(y x) P we can maximize the T y 0 exp{w̃y 0 φ(x)} conditional log-likelihood of the training data log p(y1 , . . . , yN x1 , . . . , xN ) N X log p(yi xi ) i 1 This yields the following negative log likelihood (NLL) objective function to minimize N X X w̃T exp{w̃T yi φ(xi ) log y 0 φ(xi )} i 1 y0 This objective can be minimized using gradient-based techniques. Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Multiclass SVM I Multiclass SVM was formulated in [Crammer and Singer, 2001] as follows T T T First define w [wT 1 , w2 , . . . , wM ] as concatenation of weight vectors. N X 1 ξi min w 2 C 2 i 1 subject to: T w̃T yi x̃i w̃y 0 x̃i ξi 1 ξi , i, y 0 6 yi 0 Let ȳi arg maxy 0 6 yi w̃T y 0 x̃i Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010 (7)

Multi-class classification Multiclass SVM II The first set of inequalities can also be written as: T w̃T yi x̃i w̃ȳi x̃i 1 ξi , i The problem can be formulated as an unconstrained minimization problem as follows: N X 1 min w 2 C (1 w̃T w̃T yi x̃i max y 0 x̃i ) y 0 6 yi 2 i 1 In multi-class classification, some class pairs may be less costly to be confused, so we can define a label-loss function (y , y 0 ) which gives a cost to replacing y with y 0 during classification, which can be incorporated in the SVM constraints formulation [Tsochantaridis et al., 2005] Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Multiclass SVM III “Margin rescaling” yields the set of constraints T 0 0 w̃T yi x̃i w̃y 0 x̃i (yi , y ) ξi , i, y 6 yi whereas “slack rescaling” yields the following set of constraints T w̃T yi x̃i w̃y 0 x̃i 1 ξi , i, y 0 6 yi (yi , y 0 ) There is a cutting-plane algorithm in [Tsochantaridis et al., 2005] which solves a series of constrained optimization algorithms to solve these problems Furthermore, [Joachims et al., 2009] introduced 1-slack constraints, 1-slack formulation with margin rescaling uses the constraints N N 1 X T 1 X T (w̃yi x̃i w̃y 0 x̃i ) (yi , yi0 ) ξ, (yi0 )N i 1 i N N i 1 i 1 Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Multiclass SVM IV 1-slack formulation with slack rescaling is also provided in the same paper There are efficient cutting-plane algorithms in [Joachims et al., 2009] for solving 1-slack problems in the dual space These solvers are provided in the svm-struct package Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Regularized empirical risk for multi-class I Remembering RER N 1 X R̂(θ) L (fθ (xi ), yi ) Ω(θ) N i 1 T T For multi-class, the parameters are w̃ [w̃T 1 , . . . , w̃M ] and the loss functions for each type are as follows: multi-class FLD: L (fw̃ (xi ), yi ) M X 2 (w̃T y x̃i t(y , yi )) y 1 where t(y , yi ) are appropriate targets for class y for least squares regression when the true class is yi Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Regularized empirical risk for multi-class II p p [Ye, 2007] shows that using t(y , y ) N/N Ny /N when y i p y yi and t(y , yi ) Nyi /N otherwise, is equivalent to linear discriminant analysis FLD is equivalent to using a least squares loss function multi-class LR: L (fw̃ (xi ), yi ) w̃T yi x̃i log X exp{w̃T y 0 x̃i } y0 multi-class SVM: L (fw̃ (xi ), yi ) (1 w̃T w̃T yi x̃i max y 0 x̃i ) 0 y 6 yi Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Regularized empirical risk for multi-class III Re-writing the SVM loss function is possible as follows: (w̃T L (fw̃ (xi ), yi ) w̃T yi x̃i max y 0 x̃i 1 δy ,yi ) 0 y This form is equivalent to the one before since this is guaranteed to be nonnegative We can generalize using label-loss (y , y 0 ) and “margin rescaling” introduced before to get 0 (w̃T L (fw̃ (xi ), yi ) w̃T yi x̃i max y 0 x̃i (yi , y )) 0 y We can replace the max with a softmax (log-sum-exp) to get an “approximation” SVM-softmax X 0 L (fw̃ (xi ), yi ) w̃T exp{w̃T yi x̃i log y 0 x̃i (yi , y )} y0 Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Regularized empirical risk for multi-class IV Comparing the LR loss function with the SVM-softmax one, we see that they are similar except for the addition of the label-loss function to provide additional margin for confusable classes in the SVM-softmax It is possible to get the RER expression for “slack rescaling” and 1-slack versions of margin and slack rescaling as well For other possible loss functions, for example see [LeCun et al., 2006] Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Optimization algorithms I Multi-class FLD has closed form solution Multi-class LR can be solved using Newton’s method in the primal yielding an iterative re-weighted least squares algorithm Multi-class SVM can be directly solved from the dual problem [Crammer and Singer, 2001, Fan et al., 2008] especially if number of training samples N is small Cutting-plane algorithms are attractive alternatives [Tsochantaridis et al., 2005, Joachims et al., 2009] Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Optimization algorithms II Multi-class SVM-softmax can be solved using Newton’s method in the primal If Newton algorithm’s Hessian is too big to be computed efficiently, L-BFGS can be used Stochastic gradient algorithms are fast and applicable, but need to be careful with convergence and choosing step sizes [Bottou, 2004] The optimal choice of the algorithm depends on the values of feature dimension d, number of classes M and number of training samples N Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Multi-class classification Log-linear models A general log-linear conditional model is given by: X 1 p(y x; w) exp wj Fj (x, y ) Z (x, w) j where Z (x, w) X y0 exp X j wj Fj (x, y 0 ) is called the partition function. Note that multi-class LR is a log-linear model where we define a T T concatenated weight vector w [w̃T 1 , . . . , w̃M ] and where the feature vector F (x, y ) x̃ ey where ey is the unit vector with one in position y and zeros elsewhere and denotes the Kronecker product. Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010

Hidden Markov Models Outline 1 Sequence Labeling 2 Binary Classifiers

Sequence Labeling Outline 1 Sequence Labeling 2 Binary Classi ers 3 Multi-class classi cation 4 Hidden Markov Models 5 Generative vs Discriminative Models 6 Conditional random elds 7 Training CRFs 8 Structured SVM for sequence labeling Hakan Erdogan, A tutorial on sequence labeling, ICMLA 2010, Bethesda MD, December 2010