Transformation-Based Learning:
Three Lectures, One Assignment and A Couple of Project Suggestions

Introduction

This series of lectures and exercises have been developed for a course in Machine Learning to be held at Göteborg University in the fall of 2005. The full course consists of four parts, and this page is concerned only with the second part, dealing specifically with Transformation-Based Learning (TBL).

Before you do anything else, you need to install the learner and the material relevant to the assignment. See below. Note that even if you already have an installation of the system, you will still need the course material.

Lectures

• Introduction to Transformation-Based Learning (TBL)
  • What rules look like, what they mean, and what they do
  • Templates, scoring and various thresholds
  • The learning algorithm
  • TBL applied to part of speech tagging
• Other kinds of rules to learn with TBL
  • Unknown word guessing
  • Word sense disambiguation
  • Phrase chunking
  • Constraint grammar tagging
  • Dialogue act tagging
• Deploying your rule sequences
  • Compiling into source code (in various programming languages)
  • Tagging with a theorem prover
  • Compiling into finite-state transducers
  • Incremental tagging
• Practical (for those who have not used the MUTBL system before)

Lecture Notes

Can be found here (PDF).

Assignment

The assignment consists of six parts, where each part involves the training and testing of rules for a particular NLP task (each of which will have been touched upon in the lectures):

1. A part of speech tagger
2. An unknown word guesser
3. A word sense disambiguator
4. A noun-phrase chunker
5. A constraint grammar tagger
6. A dialogue act tagger

So, are you expected to do all of them? No, if you have already taken the GSLT course NLP1, then you have already done 1), and I do of course not expect you to do it again. But then you must do 2) - 6). If you haven't done 1) before, then you must do it, but then you are not required to do 5) and 6). I encourage you to have a go at them anyway, but you are not required to.

All material in the form of training and test data, and in some cases small sets of templates, will be made available to you. Your task is to - with an eye to the suggested literature (see below) - perform a few traning-test-modifcation runs in order to get a result as good as possible. For practical reasons, the training material will be small, so you should not expect to reach top-notch performance figures. Once you know how to work, you should not have to spend more than an hour, and maybe only half an hour, on each task (except for 1, which takes longer). Note, however, that you should also read the papers. Preferably, you have already browsed the papers before the course starts.

Your short report should specify - for each task, and at a minimum - the set of templates that you ended up using, the (initial part of the) resulting rule sequence, and the performance (in terms of accuracy, recall and precision, etc.) that the resulting rule sequence has. (The report that I expect you to write for task 1) is a bit more involved - see the instructions for that particular task.) Sometimes I have given you some additional questions to consider as well, and any other kind of comments or relevant discussion is of course also welcome.

Relevant papers

PoS tagging and unknown word guessing

• Brill, Eric (1995) Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part of Speech Tagging. Computational Linguistics, December 1995. (.ps)
• Lager, Torbjörn (1999) The µ-TBL System: Logic Programming Tools for Transformation-Based Learning. In Proceedings of the Third International Workshop on Computational Natural Language Learning (CoNLL'99), Bergen, 1999. (.ps)

NP chunking

• Ramshaw, Lance and Mitchell Marcus (1995) Text Chunking using Transformation-Based Learning. In Proceedings of the ACL Third Workshop on Very Large Corpora, June 1995, pp. 82-94. (.ps)

Dialogue act tagging

• Samuel, Ken, Sandra Carberry and K. Vijay-Shanker (1998) Dialogue Act Tagging with Transformation-Based Learning. In Proceedings of COLING/ACL'98, pp. 1150-1156. (.ps)
• Lager, Torbjörn and Natalia Zinovjeva (1999) Training a Dialogue Act Tagger with the µ-TBL System. Paper presented at the Third Swedish Symposium on Multimodal Communication, Linköping University Natural Language Processing Laboratory (NLPLAB), October 16-17, 1999. (.pdf)

Constraint grammar tagging

• Lager, Torbjörn (2001) Transformation-Based Learning of Rules for Constraint Grammar Tagging. Paper presented at The 13th Nordic Conference in Computational Linguistics, Uppsala, May 21-22, 2001. (.ps)

Word sense disambiguation

• Lager, Torbjörn and Natalia Zinovjeva (2001) Sense and Deduction: The Power of Peewees Applied to the SENSEVAL-2 Swedish Lexical Sample Task. In Proceedings of SENSEVAL-2: Second International Workshop on Evaluating Word Sense Disambiguation Systems. July 5-6, 2001, Toulouse, France. (.ps)

Suggestions for individual projects

In case you choose to carry out your individual course project within the TBL framework, here are some suggestions:

• A possible project is to scale up one of the assignment tasks, and make a 'real' application out of it. You most likely need to work on larger training corpora (which you may have to prepare yourself), you need to allow more time for training, etc. You should also build a 'real' standalone tagging component, using one of the methods suggested here, or one that you design yourself (you could, for example, write a compiler for compiling MUTBL rules into C, or Haskell, or whatever).
• Another interesting project is to train a tagger for a task not included in the above list: a named entity recognizer, a grapheme to phoneme converter, or whatever. A good way to find inspiration is to browse the papers listed in the TBL Bibliography. Note that the MUTBL system may not be able to handle your task as it stands; you may have to modify the source code of the full MUTBL system, or perhaps only MUTBL Light.
• You may want to write your own tranformation-based learner. (If someone could implement the algorithm described in (Ngai & Florian 2001) in a programming language that I can read, I will be forever grateful - their implementation is written in C++).
• Another hacker's challenge is to implement the algorithms described in (Roche & Schabes 1995) for turning a sequence of transformation rules into deterministic finite state transducers.

Software Installation

If your work from home, you need to install the learner plus material for the course yourself. Download one of the following:

• The µ-TBL System for Windows + course pack
• The µ-TBL System for MacOSX + course pack

Unpack the distribution. The resulting directory contains all you need. The distribution also contains a user's manual. Make sure you read it!

Test

To test the distribution, invoke the µ-TBL system with the -f flag and the script 'pos_tagging.script' from the examples directory.

> ./mutbl -f examples/pos_tagging.script

If everything is installed all right, then you should see the following being printed to the screen:

*****************************************************
           The µ-TBL system, version 1.0
          Copyright © Torbjörn Lager 2000
Department of Linguistics, Uppsala University, Sweden
 The µ-TBL system comes with absolutely no warranty.
    Type "help." to list all available commands.
*****************************************************

Learning a rule sequence...
Loading data: data/wsj_7500 ... done! Size is 7494.
Loading algorithm: algorithms/brill ... done!
Loading templates: templates/test_templates ... done!
11    1.00   tag:'VBP'>'VB' <- tag:'MD'@[-1,-2]
11    1.00   tag:'VBN'>'VBD' <- tag:'PP'@[-1]
8     1.00   tag:'NN'>'VB' <- tag:'MD'@[-1]
7     0.77   tag:'JJ'>'RB' <- wd:due@[0]
7     1.00   tag:'VBP'>'VB' <- tag:'TO'@[-1]
6     1.00   tag:'VB'>'VBP' <- tag:'NNS'@[-1]
6     0.88   tag:'VB'>'NN' <- tag:'DT'@[-1,-2]
6     1.00   tag:'IN'>'WDT' <- tag:'VBD'@[1]
8 rule(s) for feature(s) [tag]
Testing the learned rule sequence...
Loading templates: templates/pos_tagging_templates ... done!
Loading data: data/wsj_test ... done! Size is 9625.

DATA STATISTICS:

            Corpus Size: 9625
         Number of Tags: 9625
 Number of Correct Tags: 9228
       Number of Errors: 397
                 Recall: 95.9%
              Precision: 95.9%
                F-Score: 95.9%
Number of Tags per Word: 1.000

Applied 8 rule(s) for feature(s) [tag] in 0.220 seconds

DATA STATISTICS:

            Corpus Size: 9625
         Number of Tags: 9625
 Number of Correct Tags: 9245
       Number of Errors: 380
                 Recall: 96.1%
              Precision: 96.1%
                F-Score: 96.1%
Number of Tags per Word: 1.000

Saving the rule sequence(s) in file 'rules/test.pl'.
Generating data for the Error Browser...
Load (or reload) the file "error_data.html"
into a HTML browser to view error data.
Finished!
bash-2.05$

It is a good idea to study the script 'examples/pos_tagging.script' together with the manual and to try connect the different commands in there with what is written out when running the script.