SVM Multiclass and Structured Prediction Bin Zhao Part I Multi Class SVM 2 Class SVM Primal form Dual form Real world classification problems Automated protein classification Object recognition 10 Phoneme recognition 100 300 600 http www glue umd edu zhelin recog html Digit recognition The number of classes is sometimes big 50 The multi class algorithm can be heavy Waibel Hanzawa Hinton Shikano Lang 1989 How can we solve multi class problem One against one One against rest Crammer Singer s formulation Error correcting output coding Empirical comparisons One against one One against rest Problems One against one One against rest Crammer Singer s formulation A Na ve approach Crammer Singer s formulation A Na ve approach C S s formulation Error Correcting Output Code ECOC 0 1 0 0 0 0 0 0 0 0 Codeword Meta classifier Source Dietterich and Bakiri 1995 Discussions Special cases of ECOC One against one One against rest Empirical Study In Defense of One Vs All Classification JMLR 2004 The most important step in good multiclass classification is to use the best binary classifier available Once this is done it seems to make little difference what multiclass scheme is applied and therefore a simple scheme such as OVA or AVA is preferable to a more complex errorcorrecting coding scheme or single machine scheme Part II Structured SVM Slides Courtesy Ioannis Tsochantaridis Thomas Hofmann Thorsten Joachims Yasemin Altun Local Classification brar e Classify using local information Ignores correlations thanks to Ben Taskar for slide Structured Classification brac e Use local information Exploit correlations thanks to Ben Taskar for slide Case Study Max Margin Learning on DomainIndependent Web Information Extraction Motivation Understand web page Assign semantics to each component of a page Understand functionality of each section Distinguish main content from side contents Page layout reveals important cues Motivation Cont Human can understand a page written in foreign language Position Size Font Color Boldness Relative position to other sections Can a computer fulfill similar task Domain independent web information extraction The Proposed Approach Page Segmentation vision tree Built based on DOM tree With visual information Correspond to how each node is displayed Structured Segmentation Assign label for each node in the vision tree Information extraction based on node classification Structured Classification Label space for leaf nodes attribute name attribute value non attribute image nav bar main title page tail image caption non atribute anything else Label space for non leaf nodes structure block data record nav bar block non attribute block value block page tail block name block image block image caption block main title block Max Margin Learning Structured output space tree If treated as conventional classification exponential number of classes unable to train Augmented loss misclassify a tree by one node should receive much less penalty than misclassifying the entire tree Input output feature mapping Linear discriminant function Response to input x Max Margin Learning Cont Augmented loss of disagreements between y and y Learning use SVM to find optimal w Inference dynamical programming Input Output Feature Mapping Two types of cliques in the hierarchical model Cliques Cliques covering observation state node pairs covering state state node pairs Correspondingly two types of features Features describing cliques Features describing cliques Input Output Feature Mapping Type I Spatial features Position of block center block height block weight block area Features for all nodes Link number number of various HTML tags number of child nodes Features for leaf nodes only Text length font bold italic word count number of images image size link text length Input Output Feature Mapping Type II Parent child relationship Label co occurrence pattern Connect spatially adjacent blocks Link a node with its k nearest neighbors Define label co occurrence pattern for connected node pair i j Learning and Inference Learning Quadratic programming with exponential number of constraints cutting plane algorithm a k a constraint generation bundle method Inference Without edges between spatially adjacent blocks dynamical programming a k a Viterbi decoding With edges between spatially adjacent blocks loopy belief propagation Empirical Study Block level prediction results Attribute name value pair extraction 1000 web pages Precision 56 91 Recall 59 37 Thank you
View Full Document
Unlocking...