paisarn

Transformation-Based Error-Driven Learning and NLP: A Case Study in Part-of-Speech TaggingEric Brill: 

Transformation-Based Error-Driven Learning and NLP: A Case Study in Part-of-Speech Tagging Eric Brill 11-748: Information Extraction Paisarn Charoenpornsawat

Introduction: 

Introduction Transformation-Based Error Driven Learning (TBL) a simple rule-based approach to automated learning of linguistic knowledge Idea: first solve a problem with a simple technique then apply transformations

Transformation-Based Error-Driven Learning: 

Transformation-Based Error-Driven Learning UNANNOTATED TEXT INITIAL STATE ANNOTATED TEXT LEARNNER TRUTH RULES

An Example of Learning TBL : 

An Example of Learning TBL

Two Components in Transformation: 

Two Components in Transformation A rewrite rule (Action) ex. Change the tag from modal to noun A triggering environment (Condition) ex. The preceding word is a determiner The/det can/modal rusted/verb ./. to The/det can/noun rusted/verb ./.

Two Additional Parameters: 

Two Additional Parameters whether transformation is applied immediately or only after the entire corpus has been examined right-to-left or left-to-right Input: AAAAAA ; A -andgt; B when prev=A Output: ABBBBB ;applied after the entire corpus … ABABAB ;applied immediately (left-to-right) ABBBBB ;applied immediately (right-to-left)

DT  Transformation List: 

DT  Transformation List This tree can be converted into the following transformation list: 1. Label with S. /* start state anontation */ 2. If X the S -andgt; A 3. S-andgt;B B A X ? DT: the classification is A if the answer to the query X? is yes, YES NO

DT ≠ Transformation Lists: 

DT ≠ Transformation Lists classify a character based on its position ex. if pos%4 == 0 then 'yes' else 'no'. A query use only a context of 2 chars to the left. A A A A A A A A A 0 1 2 3 4 5 6 7 8 DT: two chars before A3 and A4 are the same, but A3 and A4 should be classified differently

DT ≠ Transformation Lists: 

DT ≠ Transformation Lists TBL Lable with S: A/S A/S A/S A/S A/S A/S A/S A/S A/S If there is no previous char then S -andgt; F A/F A/S A/S A/S A/S A/S A/S A/S A/S If the char two to the left is labeled with F then S -andgt; F A/F A/S A/F A/S A/F A/S A/F A/S A/F If the character two to the left is labeled with F then F-andgt;S : A/F A/S A/S A/S A/F A/S A/S A/S A/F F -andgt; yes S -andgt; no A/yes A/no A/no A/no A/yes A/no A/no A/no A/yes

TBL for POS tagging: 

TBL for POS tagging The initial state annotator gives the most common tag for each word Transformation templates non-lexicalized features lexicalized features

Non-Lexicalized Features: 

Non-Lexicalized Features Change tag a to b when the preceding (following) word is tagged c the word two before(after) is tagged c one of the two preceding (following) words is tagged c one of the tree preceding (following) words is tagged c …

Slide12: 

Lexicalized Features: 

Lexicalized Features Change tag a to b when the preceding (following) word is w the word two before (after) is w one of the preceding (following) words is w the current word is w and the preceding (following) word is x … From IN to RB if the word two positions to the right is as. From VBP to VB if one of the previous two words is n’t. Examples from WSJ

Slide14: 

Tagging Unknown Words: 

Tagging Unknown Words The initial state annotator proper noun if capitalized common noun otherwise The set of allowable transformations using prefix, suffix information and special characters Word Accuracy: 82.2% with Lex. rules : 82.0% w/o Lex. rules

Slide16: 

Slide17: 

Slide18: 

Conclusions: 

Conclusions TBL obtains competitive performance with stochastic taggers on POS tagging. TBL captures linguistic information in a small number of simple non-stochastic rules. This learning technique have been applied to several other tasks such as prepositional phrase attachment disambiguation, text chunking, grapheme-to-phoneme conversions.