Announcements: On Wed April 28, all project groups will give a 10-minute presentation of their work.

Supplemental material: Instructions for installing minorthird; Vitor's also maintaining an FAQ for minorthird.

Description

Information extraction is finding names of entities in unstructured or partially structured text, and determining the relationships that hold between these entities. Information integration is reasoning with data taken from multiple sources. Together these techniques let one automatically perform the tremendously challenging task of deriving structured information from text, and relating it to previously-known facts.

The course will discuss many of the sub-problems involved in information extraction and integration, and the techniques required to solve them. We will consider the problems of text segmentation, relational learning, classification of text segments, finding and clustering of similar records, and reasoning with objects whose identity is uncertain. We will survey a variety of learning techniques that have been used on these problems, including rule-learning, boosting, semi-supervised learning, finite-state sequential classification methods (such as conditional Markov models and conditional random fields), character-based edit distances and adaptive generative models for modifying them, and other topics as time allows.

Readings will be based on research papers. Grades will be based on class participation, paper presentations, and a project.

More specifically, students will be expected to:

• Prepare short summaries of the papers being discussed.
• Present one or more "optional" papers from the syllabus (or some other mutually agreeable paper) to the class.
• Do a course project in a group of 2-3 people. Typical course projects might be: systematically comparing two or more existing extraction of integration methods on an existing dataset; exploring a new extraction or integration application, by collecting a dataset and evaluating an existing method; or rigorous formal analysis of a course-related topic. The end result of the project will be a written report, with format and length appropriate for a conference publication.

Prerequisites: a machine learning course (e.g., 15-781 or 15-681) or consent of the instructor.

Syllabus

Overview/Survey

Readings:

• Adaptive information extraction: Core technologies for information agents, Kushmerick and Thomas.
• Machine Learning for Sequential Data: A Review, Tom Dietterich.
• Adaptive Name-Matching in Information Integration, Bilenko et al.
• Comparative Experiments on Learning Information Extractors for Proteins and their Interactions, Bunescu et al.

Information Extraction as Classifying Text Segments

Readings:

• Information Extraction from Voicemail Transcripts, Janche and Abney. (For background, here's the Huang et al 2001 paper they compare to.)
• Understanding Captions in Biomedical Publications, Cohen et al..
• Bottom-Up Relational Learning of Pattern Matching Rules for Information Extraction, Califf and Mooney.
• A Flexible Learning System for Wrapping Tables and Lists in HTML Documents, Cohen et al.
• (Optional) Ranking Algorithms for Named-Entity Extraction: Boosting and the Voted Perceptron., Collins.
• (Optional) Relational Learning via Propositional Algorithms: An Information Extraction Case Study, Roth and Yih.
• (Optional) Unsupervised Models for Named Entity Classification, Collins and Singer.
• (Optional)Information Extraction from HTML: Application of a General Machine Learning Approach, Freitag.

IE as Boundary Detection

Readings:

• Wrapper induction: Efficiency and expressiveness, Kushmerick
• Boosted wrapper induction, Freitag and Kushmerick

IE as Sequential Token Classification: HMMs

Readings:

• Automatic segmentation of text into structured records, Borkar, Deshmukh, and Sarawagi.
• An Algorithm that Learns What's in a Name, Bikel et al

IE as Sequential Token Classification: Other Directed Graphical Models

Readings:

• A Maximum Entropy Part-Of-Speech Tagger, Ratnaparkhi.
• Maximum Entropy Markov Models for Information Extraction and Segmentation Freitag et al.
• (Optional) Information Extraction Using Hidden Markov Models, Leek.
• (Optional) Information Extraction with HMM Structures Learned by Stochastic Optimization, Freitag and McCallum.
• (Optional) Boosting Applied to Tagging and PP Attachment, Abney et al.

Readings:

• Exploiting Diverse Knowledge Sources via Maximum Entropy in Named Entity Recognition, Borthwick et al
• Description Of The LTG System Used For MUC-7, Mikheev et al
• (Optional) Use of Support Vector Machines in Extended Named Entity Recognition, Takeuchi and Collier
• (Optional) Named Entity Recognition with Character-Level Models, Klein et al
• Background tutorials: Mike Collins on learning in NLP, including a section on maxent taggers; Dan Klein on maxent.

IE as Sequential Token Classification: "Undirected" Graphical Models

Lecture: (2/23) Comments on Klein and Manning et al paper and the Toutanova paper

Readings:

• Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data , Lafferty et al.
• Shallow parsing with conditional random fields.Sha and Pereira.
• Conditional Structure versus Conditional Estimation in NLP Models, Klein and Manning.
• Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network, Toutanova et al.
• (Optional) Hidden Markov Models for Labeled Sequences, Krogh
• (Optional) Efficient Training of Conditional Random Fields, Wallach.
• (Optional) Transformation-Based Error-Driven Learning and Natural Language Processing, Brill.
• (Optional) Early Results for Named Entity Recognition with Conditional Random Fields, Feature Induction and Web-Enhanced Lexicons, McCallum and Li.
• (Optional) Table Extraction Using Conditional Random Fields, Pinto et al.

IE as Sequential Token Classification: Margin-based Methods

Lecture: (3/1) Guest lecture from Russ Greiner (U Alberta) on Web-IC.

Lecture: (3/3) Comments on the Collins paper and Altun et al paper.

Readings:

• Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms, Collins.
• Hidden Markov Support Vector Machines, Altun et al
• Max-Margin Markov Networks, Taskar et al
• Background: Large Margin Classification Using the Perceptron Algorithm, Freund and Schapire; A Statistical Learning Model of Text Classification with Support Vector Machines, Joachims.

Information Integration: Distance Metrics for Text

Lecture: (3/17) More on edit-distance computations; TFIDF distances for data integration

Lecture: (3/22) Review of various distance metrics and comparative experiments with different metrics

Readings:

• The field matching problem: Algorithms and applications, Monge and Elkan
• WHIRL: A Word-based Information Representation Language, Cohen
• A Comparison of String Distance Metrics for Name-Matching Tasks, Cohen, Ravikumar & Stephen Fienberg
• (Optional) Text Joins in an RDBMS for Web Data Integration, Gravano et al.
• (Optional) Efficient Clustering of High-Dimensional Data Sets with Application to Reference Matching, McCallum et al

IE with Large Dictionaries

Lecture: (3/25) Guest lecture from Carlos Guestrin on Max Margin Markov networks.

Lecture: (3/29) Review of previous remarks, and comments on Krauthammer et al paper.

Lecture: (3/31) Comments on Bunescu et al and Cohen and Sarawagi papers

Lecture: (4/5) Additional comments on Cohen and Sarawagi paper

Readings:

• Using BLAST for identifying gene and protein names in journal articles., Krauthammer et al.
• Extracting Gene and Protein Names from Biomedical Abstracts, Bunescu et al.
• Exploiting Dictionaries in Named Entity Extraction: Combining Semi-Markov Extraction Processes and Data Integration Methods, Cohen & Sarawagi
.
• (Optional) Playing Biology's Name Game: Identifying Protein Names in Scientific Text Hanisch et al
• (Optional) Comparative Experiments on Learning Information Extractors for Proteins and their Interactions, Bunescu et al.

  This was also assigned the first week, but we'll probably understand a lot more of it now.

Information Integration: Learning Distance Metrics

Readings:

• Learning String Edit Distance, Ristad and Yianilos
• Adaptive Duplicate Detection Using Learnable String Similarity Measures, Bilenko and Mooney
• Learning to Match and Cluster Large High-Dimensional Data Sets For Data Integration, Cohen and Richman
• (Optional) Felligi and Sunter, "A theory for record linkage", Journal of the American Statistical Society, 64:1183--1210, 1969. Available on-line as part of the background material provided with the Record Linkage Techniques - 1985 Workshop.
• (Optional) Data Cleaning Methods, Winkler (invited talk - slides are also available.
• (Optional)Unsupervised learning of name structure from coreference data, Charniak.
• (Optional)Preparation of name and address data for record linkage using hidden Markov models, Churches et al.

Information Integration: Reasoning with Uncertain Objects and/or Extracting Facts

• Identity Uncertainty and Citation Matching, Pasula et al
• Hardening Soft Information Sources, Cohen, MacAllister, & Kautz.
• (Optional) A Novel Use of Statistical Parsing to Extract Information from Text, Miller et al.
• (Optional) Probabilistic Reasoning for Entity & Relation Recognition, Roth and Yi
• (Optional) A Theory-Refinement Approach to Information Extraction