Managing Information Extraction SIGMOD 2006 Tutorial AnHai Doan

Managing Information Extraction SIGMOD 2006 Tutorial AnHai Doan

Managing Information Extraction SIGMOD 2006 Tutorial AnHai Doan UIUC UW-Madison Raghu Ramakrishnan UW-Madison Yahoo! Research Shiv Vaithyanathan IBM Almaden Tutorial Roadmap Introduction to managing IE [RR] Motivation Whats different about managing IE? Major research directions Extracting mentions of entities and relationships [SV] Uncertainty management

Disambiguating extracted mentions [AD] Tracking mentions and entities over time Understanding, correcting, and maintaining extracted data [AD] Provenance and explanations Incorporating user feedback 2 The Presenters 3 AnHai Doan Currently at Illinois Starts at UW-Madison in July

Has worked extensively in semantic integration, data integration, at the intersection of databases, Web, and AI Leads the Cimple project and builds DBLife in collaboration with Raghu Ramakrishnan and a terrific team of students Search for anhai on the Web 4 Raghu Ramakrishnan Research Fellow at Yahoo! Research, where he moved from UW-Madison after finding out that

AnHai was moving there Has worked on data mining and database systems, and is currently focused on Web data management and online communities Collaborates with AnHai and gang on the Cimple/DBlife project, and with Shiv on aspects of Avatar See www.cs.wisc.edu/~raghu 5 Shiv Vaithyanathan Shiv Vaithyanathan manages the Unstructured Information Mining group at IBM Almaden where he moved after stints in DEC and Altavista.

Shiv leads the Avatar project at IBM and is considering moving out of California now that Raghu has moved in. See www.almaden.ibm.com/software/projects/avatar/ 6 Introduction 7 Lots of Text, Many Applications! Free-text, semi-structured, streaming Web pages, email, news articles, call-center text records, business reports, annotations, spreadsheets, research papers, blogs, tags, instant messages (IM), High-impact

applications Business intelligence, personal information management, Web communities, Web search and advertising, scientific data management, e-government, medical records management, Growing rapidly Your email inbox! 8 Exploiting Text Important Direction for Our Community Many other research communities are looking at how to exploit text Most actively, Web, IR, AI, KDD Important

direction for us as well! We have lot to offer, and a lot to gain How is text exploited? Two main directions: IR and IE 9 Exploiting Text via IR (Information Retrieval) Keyword search over data containing text (relational, XML) What should the query language be? Ranking criteria? How do we evaluate queries? Integrating IR systems with DB systems

Architecture? See SIGMOD-04 panel; Baeza-Yates / Consens tutorial [SIGIR 05] Not the focus of our tutorial 10 Exploiting Text via IE (Information Extraction) Extract, then exploit, structured data from raw text: For years, Microsoft Corporation CEO Bill Gates was against open source. But today he appears to have changed his mind. "We can be open source. We love the concept of shared source," said Bill Veghte, a Microsoft VP. "That's a

super-important shift for us in terms of code access. Richard Stallman, founder of the Free Software Foundation, countered saying Select Name From PEOPLE Where Organization = Microsoft PEOPLE Name Bill Gates Bill Veghte Richard Stallman Bill Gates Bill Veghte Title Organization CEO Microsoft

VP Microsoft Founder Free Soft.. 11 (from Cohens IE tutorial, 2003) This Tutorial: Research at the Intersection of IE and DB Systems We can apply DB approaches to Analyzing and using extracted information in the context of other related data, as well as The process of extracting and maintaining structured data from text A killer app for database systems? Lots of text, but until now, mostly outside DBMSs

Extracted information could make the difference! Lets use three concrete applications to illustrate what we can do with IE 12 A Disclaimer This tutorial touches upon a lot of areas, some with much prior work. Rather than attempt a comprehensive survey, weve tried to identify areas for further research by the DB community. Weve therefore drawn freely from our own experiences in creating specific examples and articulating problems. We are creating an annotated bibliography site, and we hope youll join us in maintaining it at http://scratchpad.wikia.com/wiki/Dblife_bibs Application 1: Enterprise Search T.S. Jayram Rajasekar Sriram Krishnamurthy Raghavan Huaiyu Zhu

Avatar Semantic Search @ IBM Almaden http://www.almaden.ibm.com/software/projects/avatar/ (and Shiv Vaithyanathan) (SIGMOD Demo, 2006) 14 Overview of Avatar Semantic Search Incorporate higher-level semantics into information retrieval to ascertain userintent Interpreted as Conventional Search Return emails that contain the keywords Beineke and phone It will miss Avatar Semantic Search engages the user in a simple dialogue to ascertain user need

True user intent can be any of Query 1: return emails FROM Beineke that contain his contact telephone number Query 2: return emails that contain Beinekes signature Query 3: return emails FROM Beineke that contain a telephone number More . 15 E-mail Application Keyword query Interpretations 16 Results of the Semantic Optimizer 17 Blog Search Application

Two Interpretations of hard rock 18 How Semantic Search Works Semantic Search is basically KIDO (Keywords In Documents Out) enhanced by text-analytics During offline processing, information extraction algorithms are used to extract specific facts from the raw text At runtime, a semantic optimizer disambiguates the keyword query in the context of the extracted information and selects the best interpretations to present to the user 19 Partial Type-System for Email zip String

Author Address String state String Direction Instructions Introduction Meeting ConferenceCall String doc Agenda String

phone doc Telephone doc Email doc date to value String subject String email

doc String Signature phone person doc email URL AuthorPhone name org street person String NumberPattern

type String value String String url String 20 Translation Index person Person `barbara `phone address USAddress {callin, dialin, concall, conferencecall} ConferenceCall {phone, number, fone} {PhoneNumber, AuthorPhone.phone,

PersonPhone.phone, Signature.phone} {address, email} Email Typesystem index tammie { Person.name, Author.name} michael Person.name barbara {Author.name, Person.name, Signature.person.name, AuthorPhone.person.name} Index matches Index matches 1. 1. 2. 2. 3. 3.

4. 4. 5. 5. type [PhoneNumber] value [Person.name] path[Signature.phone] value[Signature.person.name] path[AuthorPhone.phone] value[AuthorPhone.person.nam path[PersonPhone.phone] value[Author.name] keyword keyword eap {Abbreviation.abbrev} Value Index 21 rson barbara

thor barbara yword barbara Concept tagged matches barbara matches 1. 2. 3. 4. 5. value [Person.name] value[Signature.person.name] value[FromPhone.person.name] value[Author.name] keyword phone matches X

type[PhoneNumber] concept phone path[FromPhone.phone] path[Signature.phone] path[NamePhone.phone] keyword phone keyword Concept tagged interpretations 1. that contain a Person with name matching In documents the Enron E-mail connection the keyword query 'barbara and a type PhoneNumber barbara phone has a total of 78 interpretations rson barbara

2. documents that contain a Signature.person whose name matches barbara and a path Signature.phone thor barbara 3. documents that contain an Author with name matching barbara and a path FromPhone.phone 4. documents that contain an Author with name matching barbara and a type PhoneNumber concept phone 22

Application 2: Community Information Management (CIM) Fei Chen Pedro DeRose Yoonkyong Lee Warren Shen The DBLife System @ Illinois / Wisconsin (and AnHai Doan, Raghu Ramakrishnan) 23 Best-Effort, Collaborative Data Integration for Web Communities

There are many data-rich communities Database researchers, movie fans, bioinformatics Enterprise intranets, tech support groups Each community = many disparate data sources + many people By integrating relevant data, we can enable search, monitoring, and information discovery: Any interesting connection between researchers X and Y? Find all citations of this paper in the past one week on the Web What is new in the past 24 hours in the database community? Which faculty candidates are interviewing this year, where? What are current hot topics? Who has moved where?

24 Cimple Project @ Illinois/Wisconsin Researcher Homepages Jim Gray Web pages ** Conference Pages * * Group pages * * * **

Jim Gray ** * SIGMOD-04 give-talk SIGMOD-04 ** * Text documents SQL querying Question answering Browse Mining DBworld

mailing list Import & personalize data DBLP Keyword search Modify data, provide feedback Alerts, tracking News summary 25 Prototype System: DBLife Integrate data of the DB research community 1164 data sources Crawled daily, 11000+ pages = 160+ MB / day

26 Data Extraction 27 Data Cleaning, Matching, Fusion Raghu Ramakrishnan co-authors = A. Doan, Divesh Srivastava, ... 28 Provide Services DBLife system 29 Explanations & Feedback All capital letters and the

previous line is empty Nested mentions 30 Mass Collaboration Not Divesh! If enough users vote not Divesh on this picture, it is removed. 31 Current State of the Art Numerous domain-specific, hand-crafted solutions imdb.com for movie domain citeseer.com, dblp, rexa, Google scholar etc. for publication techspec for engineering domain

Very difficult to build and maintain, very hard to port solutions across domains The CIM Platform Challenge: Develop a software platform that can be rapidly deployed and customized to manage data-rich Web communities Creating an integrated, sustainable online community for, say, Chemical Engineering, or Finance, should be much easier, and should focus on leveraging domain knowledge, rather than on engineering details 32 Application 3: Scientific Data Management AliBaba @ Humboldt Univ. of Berlin 33 Summarizing PubMed Search Results PubMed/Medline Database of paper abstracts in bioinformatics 16 million abstracts, grows by 400K per year

AliBaba: Summarizes results of keyword queries User issues keyword query Q AliBaba takes top 100 (say) abstracts returned by PubMed/Medline Performs online entity and relationship extraction from abstracts Shows ER graph to user For more detail Contact Ulf Leser System is online at http://wbi.informatik.hu-berlin.de:8080/ 34 Examples of Entity-Relationship Extraction

We show that CBF-A and CBF-C interact with each other to form a CBF-A-CBF-C complex and that CBF-B does not interact with CBF-A or CBF-C individually but that it associates with the CBF-A-CBF-C complex. CBF-A CBF-B interact comple x associates CBF-C CBF-A-CBF-C complex 35 Another Example Z-100 is an arabinomannan extracted from Mycobacterium tuberculosis that has various immunomodulatory activities, such as the induction of interleukin 12, interferon gamma (IFN-gamma) and beta-chemokines. The effects of Z-100 on human immunodeficiency virus type 1 (HIV-1) replication in human monocyte-derived macrophages (MDMs) are investigated in this paper. In MDMs, Z-100 markedly suppressed the replication of not

only macrophage-tropic (M-tropic) HIV-1 strain (HIV-1JR-CSF), but also HIV-1 pseudotypes that possessed amphotropic Moloney murine leukemia virus or vesicular stomatitis virus G envelopes. Z-100 was found to inhibit HIV-1 expression, even when added 24 h after infection. In addition, it substantially inhibited the expression of the pNL43lucDeltaenv vector (in which the env gene is defective and the nef gene is replaced with the firefly luciferase gene) when this vector was transfected directly into MDMs. These findings suggest that Z-100 inhibits virus replication, mainly at HIV-1 transcription. However, Z-100 also downregulated expression of the cell surface receptors CD4 and CCR5 in MDMs, suggesting some inhibitory effect on HIV-1 entry. Further experiments revealed that Z-100 induced IFN-beta production in these cells, resulting in induction of the 16-kDa CCAAT/enhancer binding protein (C/EBP) beta transcription factor that represses HIV-1 long terminal repeat transcription. These effects were alleviated by SB 203580, a specific inhibitor of p38 mitogen-activated protein kinases (MAPK), indicating that the p38 MAPK signalling pathway was involved in Z-100-induced repression of HIV-1 replication in MDMs. These findings suggest that Z-100 might be a 36 useful immunomodulator for control of HIV-1 infection. Query Extracted info PubMed visualized Links to databases

37 Feedback mode for community-curation 38 So we can do interesting and useful things with IE. And indeed there are many current IE efforts, and many with DB researchers involved AT&T Research, Boeing, CMU, Columbia, Google, IBM Almaden, IBM Yorktown, IIT-Mumbai, Lockheed-Martin, MIT, MSR, Stanford, UIUC, U. Mass, U. Washington, U. Wisconsin, Yahoo! 39 Still, these efforts have been carried out largely in isolation. In general, what does it take to build such an IE-based application? Can we build a System R for IEbased applications?

40 To build a System R for IE applications, it turns out that (1) It takes far more than what classical IE technologies offer (2) Thus raising many open and important problems (3) Several of which the DB community can address The tutorial is about these three points 41 Tutorial Roadmap Introduction to managing IE [RR] Motivation Whats different about managing IE? Major research directions

Extracting mentions of entities and relationships [SV] Uncertainty management Disambiguating extracted mentions [AD] Tracking mentions and entities over time Understanding, correcting, and maintaining extracted data [AD] Provenance and explanations Incorporating user feedback 42 Managing Information Extraction Challenges in Real-Life IE, and Some Problems that the Database Community Can Address 43 Lets Recap Classical IE Entity and relationship (link) extraction

Typically, these are done at the document level Entity resolution/matching Done at the collection-level Efforts have focused mostly on Improving the accuracy of IE algorithms for extracting entities/links Scaling up IE algorithms to large corpora Real-world IE applications need more! Complex IE tasks: Although not the focus of this tutorial, there is much work on extracting more complex concepts Events Opinions Sentiments

44 Classical IE: Entity/Link Extraction For years, Microsoft Corporation CEO Bill Gates was against open source. But today he appears to have changed his mind. "We can be open source. We love the concept of shared source," said Bill Veghte, a Microsoft VP. "That's a superimportant shift for us in terms of code access. Richard Stallman, founder of the Free Software Foundation, countered saying Select Name

From PEOPLE Where Organization = Microsoft PEOPLE Name Bill Gates Bill Veghte Richard Stallman Bill Gates Bill Veghte Title Organization CEO Microsoft VP Microsoft founder Free Soft.. 45 Classical IE: Entity Resolution (Mention Disambiguation / Matching)

contact Ashish Gupta at UW-Madison (Ashish Gupta, UW-Madison) A. K. Gupta, [email protected] ... Same Gupta? (A. K. Gupta, [email protected]) (Ashish K. Gupta, UW-Madison, [email protected]) Common, because text is inherently ambiguous; must disambiguate and merge extracted data 46 IE Meets Reality (Scratching the Surface) 1) Complications in Extraction and Disambiguation Multi-step, user-guided workflows In practice, developed iteratively

Each step must deal with uncertainty / errors of previous steps Integrating multiple data sources Extractors and workflows tuned for one source may not work well for another source Cannot tune extraction manually for a large number of data sources Incorporating background knowledge (e.g., dictionaries, properties of data sources, such as reliability/structure/patterns of change) Continuous extraction, i.e., monitoring Challenges: Reconciling prior results, avoiding repeated work, tracking real-world changes by analyzing changes in extracted data 47 IE Meets Reality (Scratching the Surface) 2) Complications in Understanding and Using Extracted Data Answering queries over extracted data, adjusting for extraction uncertainty and errors in a principled way Maintaining provenance of extracted data and generating understandable user-level explanations Incorporating user feedback to refine extraction/disambiguation

Want to correct specific mistake a user points out, and ensure that this is not lost in future passes of continuous monitoring scenarios Want to generalize source of mistake and catch other similar errors (e.g., if Amer-Yahia pointed out error in extracted version of last name, and we recognize it is because of incorrect handling of hyphenation, we want to automatically apply the fix to all hyphenated last names) 48 Workflows in Extraction Phase Example: extract Persons contact PhoneNumber I will be out Thursday, but back on Friday. Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007. A Sarahs number is 202-466-9160 possible workflow

contact relationship annotator person-name annotator phone-number annotator I will be out Thursday, but back on Friday. Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007. Hand-coded: If a personname is followed by can be reached at, then followed by a phonenumber output a mention of the contact relationship 49 Workflows in Entity Resolution Workflows

also arise in the matching phase As an example, we will consider two different matching strategies used to resolve entities extracted from collections of user home pages and from the DBLP citation website The key idea in this example is that a more liberal matcher can be used in a simple setting (user home pages) and the extracted information can then guide a more conservative matcher in a more confusing setting (DBLP pages) 50 Example: Entity Resolution Workflow d1: Gravanos Homepage d2: Columbia DB Group Page d3: DBLP L. Gravano, K. Ross. Text Databases. SIGMOD 03 Members

L. Gravano K. Ross J. Zhou Luis Gravano, Kenneth Ross. Digital Libraries. SIGMOD 04 L. Gravano, J. Sanz. Packet Routing. SPAA 91 L. Gravano, J. Zhou. Text Retrieval. VLDB 04 Luis Gravano, Jingren Zhou. Fuzzy Matching. VLDB 01 d4: Chen Lis Homepage C. Li. Machine Learning. AAAI 04 s1 C. Li, A. Tung. Entity Matching. KDD 03 union

s0 d3 union d1 d2 s0 d4 Luis Gravano, Jorge Sanz. Packet Routing. SPAA 91 Chen Li, Anthony Tung. Entity Matching. KDD 03 Chen Li, Chris Brown. Interfaces. HCI 99 s0 matcher: Two mentions match if they share the same name. s1 matcher: Two mentions match if they share the same name and at least one co-author name.

51 Intuition Behind This Workflow s1 Since homepages are often unambiguous, we first match homepages using the simple matcher s0. This allows us to collect co-authors for Luis Gravano and Chen Li. union s0 d3 union d1 s0 So when we finally match with tuples in d4 DBLP, which is more ambiguous, we (a) already have more evidence in the form

(b) of co-authors, and (b) can use the more conservative matcher s1. d2 52 Entity Resolution With Background Knowledge contact Ashish Gupta at UW-Madison (Ashish Gupta, UW-Madison) Entity/Link DB A. K. Gupta D. Koch Same Gupta? [email protected] [email protected] (A. K. Gupta, [email protected]) cs.wisc.edu UW-Madison

cs.uiuc.edu U. of Illinois Database of previously resolved entities/links Some other kinds of background knowledge: Trusted sources (e.g., DBLP, DBworld) with known characteristics (e.g., format, update frequency) 53 Continuous Entity Resolution What Can if Entity/Link database is continuously updated to reflect changes in the real world? (E.g., Web crawls of user home pages) use the fact that few pages are new (or have changed) between updates. Challenges: How much belief in existing entities and links? Efficient organization and indexing Where there is no meaningful change, recognize this and minimize repeated work 54 Continuous ER and Event Detection The

real world might have changed! And we need to detect this by analyzing changes in extracted information Affiliated-with Yahoo! Research Raghu Ramakrishnan University of Affiliated-with Wisconsin Gives-tutorial SIGMOD-06 Raghu Ramakrishnan Gives-tutorial

SIGMOD-06 55 Real-life IE: What Makes Extracted Information Hard to Use/Understand The extraction process is riddled with errors How should these errors be represented? Individual annotators are black-boxes with an internal probability model and typically output only the probabilities. While composing annotators how should their combined uncertainty be modeled? Semantics for queries over extracted data must handle the inherent ambiguity Lots of work

Classics: Fuhr-Rollecke; Imielinski-Lipski; ProbView; Halpern; Recent: See March 2006 Data Engineering bulletin for special issue on probabilistic data management (includes Green-Tannen survey/discussion of several proposals) Dalvi-Suciu tutorial in Sigmod 2005, Halpern tutorial in PODS 56 2006 Some Recent Work on Uncertainty Many representations proposed, e.g., Confidence scores; Or-sets; Hierarchical imprecision Lots of recent work on querying uncertain data E.g., Dalvi-Suciu identified classes of easy (PTIME) and hard (P#) queries and gave PTIME processing algorithms for easy ones E.g., Burdick et al. (VLDB 05) considered single-table aggregations and showed how to assign confidence scores to hierarchically imprecise data in an intuitive way E.g., Trio project (ICDE 06) considering how lineage can constrain

the values taken by an imprecisely known object E.g., Deshpande et al. (VLDB 04) consider data acquisition E.g., Fagin et al. (ICDT 03) consider data exchange 57 Real-life IE: What Makes Extracted Information Hard to Use/Understand Users want to drill down on extracted data We need to be able to explain the basis for an extracted piece of information when users drill down. Many proof-tree based explanation systems built in deductive DB / LP /AI communities (Coral, LDL, EKS-V1, XSB, McGuinness, ) Studied in context of provenance of integrated data (Buneman et al.; Stanford warehouse lineage, and more recently Trio) Concisely explaining complex extractions (e.g., using statistical models, workflows, and reflecting uncertainty) is hard

And especially useful because users are likely to drill down when they are surprised or confused by extracted data (e.g., due to errors, uncertainty). 58 Provenance, Explanations A. Gupta, D. Smith, Text mining, SIGMOD-06 System extracted Gupta, D as a person name Incorrect. But why? System extracted Gupta, D using these rules: (R1) David Gupta is a person name (R2) If first-name last-name is a person name, then last-name, f is also a person name. Knowing this, system builder can potentially improve extraction accuracy. One way to do that:

(S1) Detect a list of items (S2) If A straddles two items in a list A is not a person name 59 Real-life IE: What Makes Extracted Information Hard to Use/Understand Provenance becomes even more important if we want to leverage user feedback to improve the quality of extraction over time. Maintaining an extracted view on a collection of documents over time is very costly; getting feedback from users can help In fact, distributing the maintenance task across a large group of users may be the best approach E.g., CIM 60 Incorporating Feedback A. Gupta, D. Smith, Text mining, SIGMOD-06

System extracted Gupta, D as a person name User says this is wrong System extracted Gupta, D using rules: (R1) David Gupta is a person name (R2) If first-name last-name is a person name, then last-name, f is also a person name. Knowing this, system can potentially improve extraction accuracy. (1) Discover corrective rules such as S1S2 (2) Find and fix other incorrect applications of R1 and R2 A general framework for incorporating feedback? 61

IE-Management Systems? In fact, everything about IE in practice is hard. Can we build a System R for IE-inpractice? Thats the grand challenge of Managing IE Key point: Such a platform must provide support for the range of tasks weve described, yet be readily customizable to new domains and applications 62 System Challenges Customizability to new applications Scalability Detecting broken extractors

Efficient handling of previously extracted information when components (e.g., annotators, matchers) are upgraded 63 Customizable Extraction Cannot afford to implement extraction, and extraction management, from scratch for each application. What tasks can we abstract into a platform that can be customized for different applications? What needs to be customizable? Schema level definition of entity and link concepts

Extraction libraries Choices in how to handle uncertainty Choices in how to provide / incorporate feedback Choices in entity resolution and integration decisions Choices in frequency of updates, etc. 64 Scaling Up: Size is Just One Dimension! Corpus size Number of corpora Rate of change Size of extraction library Complexity of concepts to extract Complexity of background knowledge Complexity of guaranteeing uncertainty semantics when querying or updating extracted data 65 OK. But Why Now is the Right Time? 66

1. Emerging Attempts to Go Beyond Improving Accuracy of Single IE Algorithm Researchers are starting to examine How to make blackboxes run efficiently [Sarawagi et al.] How to integrate blackboxes Combine IE and entity matching [McCallum etc.] Combine multiple IE systems [Alpa et. al.] Attempts to standardize API of blackboxes, to ensure plug and play GATE, UIMA, etc. Growing

awareness of previously mentioned issues Uncertainty management / provenance Scalability Exploiting user knowledge / user interaction Exploit extracted data effectively 67 2. Multiple Efforts to Build IE Applications, in Industry and Academia However, each in isolation Citeseer, Cora, Rexa, Dblife, what else? Numerous systems in industry Web search engines use IE to add some semantics to search (e.g., recognize place names), and to do better ad placement Enterprise search, business intelligence We should share knowledge now

68 Summary Lots of text, and growing IE can help us to better leverage text Managing the entire IE process is important Lot of opportunities for the DB community 69 Tutorial Roadmap Introduction to managing IE [RR] Motivation Whats different about managing IE? Major research directions

Extracting mentions of entities and relationships [SV] Uncertainty management Disambiguating extracted mentions [AD] Tracking mentions and entities over time Understanding, correcting, and maintaining extracted data [AD] Provenance and explanations Incorporating user feedback 70 Extracting Mentions of Entities and Relationships 71 Popular IE Tasks Named-entity extraction Identify named-entities such as Persons, Organizations etc.

Relationship extraction Identify relationships between individual entities, e.g., Citizen-of, Employed-by etc. e.g., Yahoo! acquired startup Flickr Event detection Identifying incident occurrences between potentially multiple entities such Company-mergers, transfer-ownership, meetings, conferences, seminars etc. 72 But IE is Much, Much More .. Lesser known entities

Identifying rock-n-roll bands, restaurants, fashion designers, directions, passwords etc. Opinion / review extraction Detect and extract informal reviews of bands, restaurants etc. from weblogs Determine whether the opinions can be positive or negative 73 Email Example: Identify emails that contain directions From: Shively, Hunter S. Date: Tue, 26 Jun 2001 13:45:01 -0700 (PDT) I-10W to exit 730 Peachridge RD (1 exit past Brookshire). Turn left on Peachridge RD. 2 miles down on the right--turquois 'horses for sale' sign From Fromthe theEnron Enronemail

emailcollection collection 74 Weblogs: Identify Bands and Reviews .I went to see the OTIS concert last night. T was SO MUCH FUN I really had a blast .there were a bunch of other bands . I loved STAB (.). they were a really weird ska band and people were running around and 75 Intranet Web: Identify form-entry pages [Li et al, SIGIR, 2006] Link to Federal Student Aid Application Form 76 Intranet Web: Software download pages along with Software Name [Li et al, SIGIR, 2006] Link to download Citrix ICA Client

77 Workflows in Extraction I will be out Thursday, but back on Friday. Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007. Sarahs phone is 202-466-9160 Single-shot extraction Multi-step Workflow Saras phone Sarah can be reached at 202-466-9160 78 Broadly-speaking two types of IE systems: hand-coded and learning-based. What do they look like?

When best to use what? Where can I learn more? Lets start with hand-coded systems ... 79 Generic Template for hand-coded annotators Document d Previous annotations on document d Procedure Annotator (d, Ad) Rf is a set of rules to generate features Rg is a set of rules to create candidate annotations Rc is a set of rules to consolidate annotations created by R g

1. Features = Compute_Features(Rf, d) 2. foreach r Rg Candidates = Candidates U ApplyRule (r, Features, Ad) 3. Results = Consolidate (Rc, Candidates) return Results 80 Simplified Real Example in DBLife Goal: build a simple person-name extractor input: a set of Web pages W, DB Research People Dictionary DBN output: all mentions of names in DBN Simplified DBLife Person-Name extraction Obtain Features: HTML tags, detect lists of proper-names Candidate Generation: for each name e.g., David Smith generate variants (V): David Smith, D. Smith, Smith, D., etc. obtain candidate person-names in W using V

Consolidation: if an occurrence straddles two proper-names then drop it 81 Compiled Dictionary . . . . . . . Renee Miller R. Miller Miller, R Candidate Generation Rule: Identifies Miller, R as a potential persons name D. Miller, R. Smith, K. Richard, D. Li Detected List of Proper-names Consolidation Rule: If a candidate straddles two elements of the list then drop it 82

Example of Hand-coded Extractor [Ramakrishnan. G, 2005] Rule 1 This rule will find person names with a salutation (e.g. Dr. Laura Haas) and two capitalized words INITIAL DOT CAPSWORD CAPSWORD Rule 2 This rule will find person names where two capitalized words are present in a Person dictionary PERSONDICT, CAPSWORD PERSONDICT, CAPSWORD CAPSWORD : Word starting with uppercase, second letter lowercase E.g., DeWitt will satisfy it (DEWITT will not) \p{Upper}\p{Lower}[\p{Alpha}]{1,25} DOT : The character . Note that some names will be identified by both rules 83

Hand-coded rules can be artbitrarily complex Find conference name in raw text ############################################################################# # Regular expressions to construct the pattern to extract conference names ############################################################################# # These are subordinate patterns my $wordOrdinals="(?:first|second|third|fourth|fifth|sixth|seventh|eighth|ninth|tenth|eleventh|twelfth|thirteenth|fourteenth|fifteenth)"; my $numberOrdinals="(?:\\d?(?:1st|2nd|3rd|1th|2th|3th|4th|5th|6th|7th|8th|9th|0th))"; my $ordinals="(?:$wordOrdinals|$numberOrdinals)"; my $confTypes="(?:Conference|Workshop|Symposium)"; my $words="(?:[A-Z]\\w+\\s*)"; # A word starting with a capital letter and ending with 0 or more spaces my $confDescriptors="(?:international\\s+|[A-Z]+\\s+)"; # .e.g "International Conference ...' or the conference name for workshops (e.g. "VLDB Workshop ...") my $connectors="(?:on|of)"; my $abbreviations="(?:\\([A-Z]\\w\\w+[\\W\\s]*?(?:\\d\\d+)?\\))"; # Conference abbreviations like "(SIGMOD'06)" # The actual pattern we search for. A typical conference name this pattern will find is # "3rd International Conference on Blah Blah Blah (ICBBB-05)" my $fullNamePattern="((?:$ordinals\\s+$words*|$confDescriptors)?$confTypes(?:\\s+$connectors\\s+.*?|\\s+)?$abbreviations?)(?:\\n|\\r|\\.| <)"; ############################## ################################ # Given a , look for the conference pattern ############################################################## lookForPattern($dbworldMessage, $fullNamePattern);

######################################################### # In a given , look for occurrences of # is a regular expression ######################################################### sub lookForPattern { my ($file,$pattern) = @_; 84 Example Code of Hand-Coded Extractor # Only look for conference names in the top 20 lines of the file my $maxLines=20; my $topOfFile=getTopOfFile($file,$maxLines); # Look for the match in the top 20 lines - case insenstive, allow matches spanning multiple lines if($topOfFile=~/(.*?)$pattern/is) { my ($prefix,$name)=($1,$2); # If it matches, do a sanity check and clean up the match # Get the first letter # Verify that the first letter is a capital letter or number if(!($name=~/^\W*?[A-Z0-9]/)) { return (); } # If there is an abbreviation, cut off whatever comes after that if($name=~/^(.*?$abbreviations)/s) { $name=$1; } # If the name is too long, it probably isn't a conference if(scalar($name=~/[^\s]/g) > 100) { return (); }

# Get the first letter of the last word (need to this after chopping off parts of it due to abbreviation my ($letter,$nonLetter)=("[A-Za-z]","[^A-Za-z]"); " $name"=~/$nonLetter($letter) $letter*$nonLetter*$/; # Need a space before $name to handle the first $nonLetter in the pattern if there is only one word in name my $lastLetter=$1; if(!($lastLetter=~/[A-Z]/)) { return (); } # Verify that the first letter of the last word is a capital letter # Passed test, return a new crutch return newCrutch(length($prefix),length($prefix)+length($name),$name,"Matched pattern in top $maxLines lines","conference name",getYear($name)); } return (); } 85 Some Examples of Hand-Coded Systems FRUMP [DeJong 82] CIRCUS / AutoSlog [Riloff 93] SRI FASTUS [Appelt, 1996] OSMX [Embley, 2005] DBLife [Doan et al, 2006] Avatar [Jayram et al, 2006]

86 Template for Learning based annotators Procedure LearningAnnotator (D, L) D is the training data L is the labels 1. Preprocess D to extract features F 2. Use F,D & L to learn an extraction model E using a learning algorithm A (Iteratively fine-tune parameters of the model and F) Procedure ApplyAnnotator(d,E) 1. Features = Compute_Features (d) 2. results = ApplyModel (E,Features, d) 3. return Results 87 Real Example in AliBaba Extract Use

gene names from PubMed abstracts Classifier (Support Vector Machine - SVM) Tokenized Training Corpus Vector Generator SVMlight New Text Vector Generator SVM Model driven Tagger

Post Processor Tagged Text Corpus of 7500 sentences 140.000 non-gene words 60.000 gene names SVMlight on different feature sets Dictionary compiled from Genbank, HUGO, MGD, YDB Post-processing for compound gene names 88 Learning-Based Information Extraction Naive

Bayes SRV [Freitag-98], Inductive Logic Programming Rapier [Califf & Mooney-97] Hidden Markov Models [Leek, 1997] Maximum Entropy Markov Models [McCallum et al, 2000] Conditional Random Fields [Lafferty et al, 2000] For an excellent and comprehensive view [Cohen, 2004] 89 Semi-Supervised IE Systems Learn to Gather More Training Data Only a seed set 1. Use labeled data to learn an extraction model E 2. Apply E to find mentions in document collection. 3. Construct more labeled data T is the new set. 4. Use T to learn a hopefully better extraction model E. 5. Repeat. Expand the seed set

[DIPRE, Brin 98, Snowball, Agichtein & Gravano, 2000] 90 So there are basically two types of IE systems: hand-coded and learning-based. What do they look like? When best to use what? Where can I learn more? 91 Hand-Coded Methods Easy to construct in many cases e.g., to recognize prices, phone numbers, zip codes, conference names, etc. Easier to debug & maintain

especially if written in a high-level language (as is usually the case) e.g., [From Avatar] ContactPattern RegularExpression(Email.body,can be reached at) PersonPhone Precedes(Person Precedes(ContactPattern, Phone, D), D) Easier to incorporate / reuse domain knowledge Can be quite labor intensive to write 92 Learning-Based Methods Can work well when training data is easy to construct and is plentiful Can capture complex patterns that are hard to encode with hand-crafted rules e.g., determine whether a review is positive or negative

extract long complex gene names [From AliBaba] The human T cell leukemia lymphotropic virus type 1 Tax protein represses MyoD-dependent transcription by inhibiting MyoD-binding to the KIX domain of p300. Can be labor intensive to construct training data not sure how much training data is sufficient Complementary to hand-coded methods 93 Where to Learn More Overviews Wendy Lehnert [Comm of the ACM, 1996]

Appelt [1997] Cohen [2004] Agichtein and Sarawai [KDD, 2006] Andrew McCallum [ACM Queue, 2005] Systems / tutorials / codes to try OpenNLP MinorThird Weka Rainbow 94 So what are the new IE challenges for IE-based applications?

First, lets discuss several observations, to motivate the new challenges 95 Observation 1: We Often Need Complex Workflow What we have discussed so far are largely IE components Real-world IE applications often require a workflow that glue together these IE components These workflows can be quite large and complex Hard to get them right! 96 Illustrating Workflows Extract persons contact phone-number from e-mail I will be out Thursday, but back on Friday.

Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007. A Sarahs contact number is 202466-9160 possible workflow Contact relationship annotator person-name annotator Phone annotator I will be out Thursday, but back on Friday. Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007. Hand-coded: If a personname is followed by can be reached at, then followed by a phonenumber

output a mention of the contact relationship 97 How Workflows are Constructed Define the information extraction task e.g., identify peoples phone numbers from email Identify the text-analysis components E.g., tokenizer, part-of-speech tagger, Person, Phone annotator Compose different text-analytic components into a workflow Several open-source plug-and-play architectures such as UIMA, GATE available

Build domain-specific text-analytic component 98 How Workflows are Constructed Define the information extraction task E.g., identify peoples phone numbers from email Identify the generic annotator components E.g., tokenizer, part-of-speech tagger, Person, Phone annotator Compose different text-analytic components into a workflow Several open-source plug-and-play architectures such as UIMA, GATE available

Build domain-specific text-analytic component Generic text-analytic tasks. Use available components 99 How Workflows are Constructed Define the information extraction task E.g., identify peoples phone numbers from email Identify the text-analysis components E.g., tokenizer, part-of-speech tagger, Person, Phone annotator Compose different text-analytic components into a workflow Several open-source plug-and-play architectures such as UIMA, GATE available

Build domain-specific text-analytic component 100 How Workflows are Constructed Define the information extraction task E.g., identify peoples phone numbers from email Identify the generic text-analysis components E.g., tokenizer, part-of-speech tagger, Person, Phone annotator Compose different text-analytic components into a workflow Several open-source plug-and-play architectures such as UIMA, GATE available

Build domain-specific text-analytic component which is the contact relationship annotator in this example 101 UIMA & GATE -Tokens -Parts of Speech -PhoneNumbers -Persons Tokenizer Part of Speech Person And Phone Annotator

Aggregate Analysis Engine: Person & Phone Detector Extracting Persons and Phone Numbers 102 UIMA & GATE -Tokens -Parts of Speech -PhoneNumbers -Persons Tokenizer Part of Speech Person And Phone Annotator -Tokens -Parts of Speech -PhoneNumbers

-Persons - Persons Phone Relation Annotator Aggregate Analysis Engine: Person & Phone Detector Aggregate Analysis Engine: Persons Phone Detector Aggregate Analysis Engine: Persons Phone Detector Identifying Persons Phone Numbers from Email 103 Workflows are often Large and Complex In DBLife system between 45 to 90 annotators the workflow is 5 level deep this makes up only half of the DBLife system (this is counting only extraction rules)

In Avatar 25 to 30 annotators extract a single fact with [SIGIR, 2006] Workflows are 7 level deep 104 Observation 2: Often Need to Incorporate Domain Constraints GRAND CHALLENGES FOR MACHINE LEARNING Jaime Carbonell School of Computer Science Carnegie Mellon University 3:30 pm 5:00 pm 7500 Wean Hall start-time < end-time Machine learning has evolved from obscurity in the 1970s into a vibrant and popular

time annotator if (location = Wean Hall) start-time > 12 location annotator meeting(3:30pm, 5:00pm, Wean Hall) meeting annotator 105Hall Meeting is from 3:30 5:00 pm in Wean Observation 3: The Process is Incremental & Iterative During development Multiple versions of the same annotator might need to compared and contrasted before the choosing the right one (e.g., different regular

expressions for the same task) Incremental annotator development During deployment Constant addition of new annotators; extract new entities, new relations etc. Constant arrival of new documents Many systems are 24/7 (e.g., DBLife) 106 Observation 4: Scalability is a Major Problem DBLife example 120 MB of data / day, running the IE workflow once takes 3-5 hours Even on smaller data sets debugging and testing is a timeconsuming process stored data over the past 2 years magnifies scalability issues write a new domain constraint, now should we rerun system from day

one? Would take 3 months. AliBaba: query time IE Users expect almost real-time response Comprehensive tutorial - Sarawagi and Agichtein [KDD, 2006] 107 These observations lead to many difficult and important challenges 108 Efficient Construction of IE Workflow What would be the right workflow model ? Help write workflow quickly Helps quickly debug, test, and reuse

UIMA / GATE ? (do we need to extend these ?) What is a good language to specify a single annotator in this workfow An example of this is CPSL [Appelt, 1998 ] What are the appropriate list of operators ? Do we need a new data-model ? Help users express domain constraints. 109 Efficient Compiler for IE Workflows What

are a good set of operators for IE process? Span operations e.g., Precedes, contains etc. Block operations Constraint handler ? Regular expression and dictionary operators Efficient implementation of these operators Inverted index constructor? inverted index lookup? [Ramakrishnan, G. et. al, 2006] How to compile an efficient execution plan? 110 Optimizing IE Workflows Finding

a good execution plan is important ! Reuse existing annotations E.g., Persons phone number annotator Lower-level operators can ignore documents that do NOT contain Persons and PhoneNumbers potentially 10-fold speedup in Enron e-mail collection Useful in developing sparse annotators Questions ? How to estimate statistics for IE operators? In some cases different execution plans may have different extraction accuracy not just a matter of optimizing for runtime 111 Rules as Declarative Queries in Avatar Person can be reached at PhoneNumber Person followed by ContactPattern followed by PhoneNumber Declarative Query Language

ContactPattern RegularExpression(Email.body,can be reached at) PersonPhone Precedes ( Precedes (Person, ContactPattern, D), Phone, D) 112 Domain-specific annotator in Avatar Identifying peoples phone numbers in email I will be out Thursday, but back on Friday. Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007. Generic pattern is Person can be reached at PhoneNumber

113 Optimizing IE Workflows in Avatar An IE workflow can be compiled into different execution plans E.g., two execution plans in Avatar: Person can be reached at PhoneNumber ContactPattern RegularExpression(Email.body,can be reached at) Stored annotations PersonPhone Precedes ( Precedes (Person, ContactPattern, D), Phone, D) ContactPattern RegularExpression(Email.body,can be reached at) PersonPhone

Precedes(Person Precedes(ContactPattern, Phone, D), D) 114 Alternative Query in Avatar ContactPattern RegularExpression(Email.body,can be reached at) PersonPhone Contains ( Precedes (Person, Phone, D), ContactPattern) 115 Weblogs: Identify Bands and Informal Reviews .I went to see the OTIS concert last night. T was SO MUCH FUN I really had a blast .there were a bunch of other bands . I loved STAB (.). they were a really weird ska band and people were running around and

116 Band INSTANCE PATTERNS lead singer sang very well Danny Sigelman played drums ASSOCIATED CONCEPTS energetic music

attended the Josh Groban concert at the Arrowhead DESCRIPTION PATTERNS (Ambiguous/Unambiguous) MUSIC, MUSICIANS, INSTRUMENTS, CROWD, Real challenge is in optimizing such complex workflows !! 117 OTIS Band instance pattern (Un)ambiguous pattern (Un)ambiguous pattern Unambiguous pattern (Un)ambiguous pattern

(Un)ambiguous pattern Continuity Review 118 Tutorial Roadmap Introduction to managing IE [RR] Motivation Whats different about managing IE? Major research directions Extracting mentions of entities and relationships [SV] Uncertainty management Disambiguating extracted mentions [AD]

Tracking mentions and entities over time Understanding, correcting, and maintaining extracted data [AD] Provenance and explanations Incorporating user feedback 119 Uncertainty Management 120 Uncertainty During Extraction Process Annotators make mistakes ! Annotators provide confidence scores with each annotation Simple named-entity annotator C = Word with first letter capitalized D = Matches an entry in a person name dictionary

Annotator Rules 1. [CD] [CD] 2. [CD] Precision 0.9 0.6 Last evening I met the candidate Shiv Vaithyanathan for dinner. We had an interesting conversation and I encourage you to get an update. His host Bill can be reached at X-2465. Text-mention Probability Shiv Vaithyanathan 0.9 Bill

0.6 [CD] [CD] [CD] 121 Composite Annotators [Jayram et al, 2006] Persons phone Person Contact pattern Phone Person can be reached at PhoneNumber Question: How do we compute probabilities for the output of composite annotators from base annotators ? 122

With Two Annotators Person Table ID Text-mention 1 Shiv Vaithyanathan 0.9 2 Bill 0.6 Telephone Table ID Text-mention 1

(408)-927-2465 0.95 2 X-2465 0.3 These annotations are kept in separate tables 123 Problem at Hand Person Table Last evening I met the candidate Shiv Vaithyanathan for dinner. We had an interesting conversation and I encourage you to get an update. His host Bill can be reached at X-2465. Person can be reached at PhoneNumber

ID Text-mention 1 Shiv Vaithyanathan 0.9 2 Bill 0.6 Telephone Table ID Text-mention 1 (408)-927-2465

0.95 2 X-2465 0.3 ID Person Telephone 1 Bill X-2465 ? What is the probability ?

124 One Potential Approach: Possible Worlds [DalviSuciu, 2004] Person example ID Text-mention 1 Shiv Vaithyanathan 2 Bill 0.9 0.6 0.54 ID Text-Mention

1 Shiv Vaithyanathan 2 Bill 0.36 0.06 ID Text-Mention 2 Bill ID Text-Mention 1

Shiv Vaithyanathan 0.04 ID Text-Mention 125 Possible Worlds Interpretation [Dalvi-Suciu, 2004] (408)-888-0829 (408)-888-0829 4088880829 Shiv Vaithyanathan Bill Shiv Vaithyanathan (408)-888-0829 4088880829 X-2465 X-2465 X-2465 ShivShiv Vaithyanathan

Bill Bill Persons X Phone Numbers X-2465 appears in 30% of the possible worlds Bill appears in 60% of the possible worlds (Bill, X-2465) (Bil, X-2465) (Bill, X-2465) (Bill, X-2465) Persons Phone (Bill, X-2465) appears

in at most 18% of the possible worlds 126 Annotation (Bill, X-2465) can have a probability of at most 0.18 But Real Data Says Otherwise . [Jayram et al, 2006] With Enron collection using Person instances with a low probability the following rule Person can be reached at PhoneNumber produces annotations that are correct more than 80% of the time Relaxing independence constraints [Fuhr-Roelleke, 95] does not help since X-2465 appears in only 30% of the worlds More powerful probabilistic database constructs are needed to capture the dependencies present in the Rule above ! 127

Databases and Probability Probabilistic DB Fuhr [F&R97, F95] : uses events to describe possible worlds [Dalvi&Suciu04] : query evaluation assuming independence of tuples Trio System [Wid05, Das06] : distinguishes between data lineage and its probability Relational Learning Bayesian Networks, Markov models: assumes tuples are independently and identically distributed Probabilistic Relational Models [Koller+99]: accounts for correlations between tuples Uncertainty in Knowledge Bases [GHK92, BGHK96] generating possible worlds probability distribution from statistics [BGHK94] updating probability distribution based on new knowledge

Recent work MauveDB [D&M 2006], Gupta & Sarawagi [G&S, 2006] 128 Disambiguate, aka match, extracted mentions 129 Once mentions have been extracted, matching them is the next step Researcher Homepages Jim Gray Web pages ** Conference

Pages * * Group Pages DBworld mailing list DBLP Text documents * * * ** Jim Gray ** * SIGMOD-04 ** *

give-talk SIGMOD-04 Keyword search SQL querying Question answering Browse Mining Alert/Monitor News summary 130 Mention Matching: Problem Definition Given extracted mentions M = {m1, ..., mn} Partition M into groups M1, ..., Mk

All mentions in each group refer to the same real-world entity Variants are known as Entity matching, record deduplication, record linkage, entity resolution, reference reconciliation, entity integration, fuzzy duplicate elimination 131 Another Example Document 1: The Justice Department has officially ended its inquiry into the assassinations of John F. Kennedy and Martin Luther King Jr., finding ``no persuasive evidence'' to support conspiracy theories, according to department documents. The House Assassinations Committee concluded in 1978 that Kennedy was ``probably'' assassinated as the result of a conspiracy involving a second gunman, a finding that broke from the Warren Commission 's belief that Lee Harvey Oswald acted alone in Dallas on Nov. 22, 1963. Document 2: In 1953, Massachusetts Sen. John F. Kennedy married Jacqueline Lee Bouvier in Newport, R.I. In 1960, Democratic presidential candidate John F. Kennedy confronted the issue of his Roman Catholic faith by telling a Protestant group in Houston, ``I do not speak for my church on public matters, and the church does not speak for me.' Document 3: David Kennedy was born in Leicester, England in 1959. Kennedy coedited The New Poetry (Bloodaxe Books 1993), and is the author of New Relations: The

Refashioning Of British Poetry 1980-1994 (Seren 1996). [From Li, Morie, & Roth, AI Magazine, 2005] 132 Extremely Important Problem! Appears in numerous real-world contexts Plagues many applications that we have seen Citeseer, DBLife, AliBaba, Rexa, etc. Why so important? Many useful services rely on mention matching being right If we do not match mentions with sufficient accuracy errors cascade, greatly reducing the usefulness of these services 133 An Example

Discover related organizations using occurrence analysis: J. Han ... Centrum voor Wiskunde en Informatica DBLife incorrectly matches this mention J. Han with Jiawei Han, but it actually refers to Jianchao Han. 134 The Rest of This Section To set the stage, briefly review current solutions to mention matching / record linkage a comprehensive tutorial is provided tomorrow Wed 2-5:30pm, by Nick Koudas, Sunita Sarawagi, & Divesh Srivastava Then focus on novel challenges brought forth by IE over text developing matching workflow, optimizing workflow, incorporating domain knowledge tracking mentions / entities, detecting interesting events

135 A First Matching Solution: String Matching m11 = John F. Kennedy m12 = Kennedy sim(mi,mj) > 0.8 mi and mj match. m21 = Senator John F. Kennedy m22 = John F. Kennedy sim = edit distance, q-gram, TF/IDF, etc. m31 = David Kennedy m32 = Kennedy A recent survey: Adaptive Name Matching in Information Integration, by M. Bilenko, R. Mooney, W. Cohen, P. Ravikumar, & S. Fienberg, IEEE Intelligent Systems, 2003.

Other recent work: [Koudas, Marathe, Srivastava, VLDB-04] Pros & cons conceptually simple, relatively fast often insufficient for achieving high accuracy 136 A More Common Solution For each mention m, extract additional data transform m into a record Match the records leveraging the wealth of existing record matching solutions Document 3: David Kennedy was born in Leicester, England in 1959. Kennedy co-edited The New Poetry (Bloodaxe Books

1993), and is the author of New Relations: The Refashioning Of British Poetry 1980-1994 (Seren 1996). first-name last-name birth-date birth-place David Kennedy 1959 Leicester D. Kennedy 1959 England 137 Two main groups of record matching solutions - hand-crafted rules - learning-based which we will discuss next 138 Hand-Crafted Rules If R1.last-name = R2.last-name R1.first-name ~ R2.first-name R1.address ~ R2.address

R1 matches R2 [Hernandez & Stolfo, SIGMOD-95] sim(R1,R2) = alpha1 * sim1(R1.last-name,R2.last-name) + alpha2 * sim2(R1.first-name,R2.first-name) + alpha3 * sim3(R1.address, R2.address) If sim(R1,R2) > 0.7 match Pros and cons relatively easy to craft rules in many cases easy to modify, incorporate domain knowledge laborious tuning in certain cases may be hard to create rules manually 139 Learning-Based Approaches

(t1, u1, +) (t2, u2, +) (t3, u3, -) ... (tn, un, +) Learn matching rules from training data Create a set of features: f1, ..., fk each feature is a function over (t,u) e.g., t.last-name = u.last-name? edit-distance(t.first-name,u.first-name) Convert each tuple pair to a feature vector, then apply a machine learning algorithm (t1, u1, +) (t2, u2, +) (t3, u3, -) ...

(tn, un, +) ([f11, ..., f1k], +) ([f21, ..., f2k], +) ([f31, ..., f3k], -) ... ([fn1, ..., fnk], +) Decision tree, Naive Bayes, SVM, etc. Learned rules 140 Example of Learned Matching Rules Produced by a decision-tree learner, to match paper citations [Sarawagi & Bhamidipaty, KDD-02]

141 Twists on the Basic Methods Compute transitive closures [Hernandez & Stolfo, SIGMOD-95] Learn all sorts of other thing (not just matching rules) e.g., transformation rules [Tejada, Knoblock, & Minton, KDD-02] Ask users to label selected tuple pairs (active learning) [Sarawagi & Bhamidipaty, KDD-02] Can

we leverage relational database? [Gravano et. al., VLDB-01] 142 Twists on the Basic Methods Record matching in data warehouse contexts Tuples can share values for subsets of attributes [Ananthakrishna, Chaudhuri, & Ganti, VLDB-02] Combine mention extraction and matching [Wellner et. al., UAI-04] And many more

e.g., [Jin, Li, Mehrotra, DASFAA-03] TAILOR record linkage project at Purdue [Elfeky, Elmagarmid, Verykios] 143 Collective Mention Matching: A Recent Trend Prior solutions assume tuples are immutable (cant be changed) often match tuples of just one type Observations can enrich tuples along the way improve accuracy often must match tuples of interrelated types can leverage matching one type to improve accuracy of matching other types This leads to a flurry of recent work on collective mention matching which builds upon the previous three solution groups

Will illustrate enriching tuples Using [Li, Morie, & Roth, AAAI-04] 144 Example of Collective Mention Matching 1. Use a simple matching measure to cluster mentions in each document. Each cluster an entity. Then learn a profile for each entity. m1 = Prof. Jordam m2 = M. Jordan e2 m3 = Michael I. Jordan m4 = Jordan m5 = Jordam m6 = Steve Jordan m7 = Jordan e3

e4 e1 m8= Prof. M. I. Jordan (205) 414 6111 CA e5 first name = Michael, last name = Jordan, middle name = I, can be misspelled as Jordam 2. Reassign each mention to the best matching entity. m1 m2 m3 m4 m5 e1 m6 m7 m8

e4 e3 m8 now goes to e3 due to shared middle initial and last name. Entity e5 becomes empty and is dropped. 3. Recompute entity profiles. 4. Repeat Steps 2-3 until convergence. m3 m4 m5 m1 m2 e3 m6 m7 m8 e4 145

Collective Mention Matching 1. Match tuples 2. Enrich each tuple with information from other tuples that match it; or create super tuples that represent groups of matching tuples. 3. Repeat Steps 1-2 until convergence. Key ideas: enrich each tuple, iterate Some recent algorithms that employ these ideas: Pedro Domingos group at Washington, Dan Roth group at Illinois, Andrew McCallum group at UMass, Lise Getoor group at Maryland, Alon Halevy group at Washington (SEMEX), Ray Mooney group at TexasAustin, Jiawei Han group at Illinois, and more 146 What new mention matching challenges does IE over text raise? 1. Static data: challenges similar to those in extracting mentions. 2. Dynamic data: challenges in tracking mentions / entities 147 Classical Mention Matching

Applies just a single matcher Focuses mainly on developing matchers with higher accuracy Real-world IE applications need more 148 We Need a Matching Workflow To illustrate with a simple example: d1: Luis Gravanos Homepage d2: Columbia DB Group Page Only one Luis Gravano L. Gravano, K. Ross. Text Databases. SIGMOD 03 Members L. Gravano K. Ross J. Zhou d3: DBLP

Luis Gravano, Kenneth Ross. Digital Libraries. SIGMOD 04 L. Gravano, J. Sanz. Packet Routing. SPAA 91 L. Gravano, J. Zhou. Text Retrieval. VLDB 04 Luis Gravano, Jingren Zhou. Fuzzy Matching. VLDB 01 d4: Chen Lis Homepage Two Chen Li-s Luis Gravano, Jorge Sanz. Packet Routing. SPAA 91 C. Li. Machine Learning. AAAI 04 Chen Li, Anthony Tung.

Entity Matching. KDD 03 C. Li, A. Tung. Entity Matching. KDD 03 Chen Li, Chris Brown. Interfaces. HCI 99 What is the best way to match mentions here? 149 A liberal matcher: correctly predicts that there is one Luis Gravano, but incorrectly predicts that there is one Chen Li s0 matcher: two mentions match if they share the same name. d1: Luis Gravanos Homepage d2: Columbia DB Group Page L. Gravano, K. Ross. Text Databases. SIGMOD 03 Members L. Gravano K. Ross J. Zhou d3: DBLP

Luis Gravano, Kenneth Ross. Digital Libraries. SIGMOD 04 L. Gravano, J. Sanz. Packet Routing. SPAA 91 L. Gravano, J. Zhou. Text Retrieval. VLDB 04 Luis Gravano, Jingren Zhou. Fuzzy Matching. VLDB 01 d4: Chen Lis Homepage Luis Gravano, Jorge Sanz. Packet Routing. SPAA 91 C. Li. Machine Learning. AAAI 04 Chen Li, Anthony Tung. Entity Matching. KDD 03 C. Li, A. Tung.

Entity Matching. KDD 03 Chen Li, Chris Brown. Interfaces. HCI 99 150 A conservative matcher: predicts multiple Gravanos and Chen Lis s1 matcher: two mentions match if they share the same name and at least one co-author name. d1: Luis Gravanos Homepage d2: Columbia DB Group Page L. Gravano, K. Ross. Text Databases. SIGMOD 03 Members L. Gravano K. Ross J. Zhou d3: DBLP Luis Gravano, Kenneth Ross. Digital Libraries. SIGMOD 04 L. Gravano, J. Sanz. Packet Routing. SPAA 91

L. Gravano, J. Zhou. Text Retrieval. VLDB 04 Luis Gravano, Jingren Zhou. Fuzzy Matching. VLDB 01 d4: Chen Lis Homepage Luis Gravano, Jorge Sanz. Packet Routing. SPAA 91 C. Li. Machine Learning. AAAI 04 Chen Li, Anthony Tung. Entity Matching. KDD 03 C. Li, A. Tung. Entity Matching. KDD 03 Chen Li, Chris Brown. Interfaces. HCI 99 151

Better solution: apply both matchers in a workflow d1: Luis Gravanos Homepage d2: Columbia DB Group Page L. Gravano, K. Ross. Text Databases. SIGMOD 03 Members L. Gravano K. Ross J. Zhou d3: DBLP Luis Gravano, Kenneth Ross. Digital Libraries. SIGMOD 04 L. Gravano, J. Sanz. Packet Routing. SPAA 91 L. Gravano, J. Zhou. Text Retrieval. VLDB 04 Luis Gravano, Jingren Zhou. Fuzzy Matching. VLDB 01 d4: Chen Lis Homepage

s1 union s0 d3 union d1 C. Li. Machine Learning. AAAI 04 Chen Li, Anthony Tung. Entity Matching. KDD 03 C. Li, A. Tung. Entity Matching. KDD 03 Chen Li, Chris Brown. Interfaces. HCI 99 s0 d4

d2 Luis Gravano, Jorge Sanz. Packet Routing. SPAA 91 s0 matcher: two mentions match if they share the same name. s1 matcher: two mentions match if they share the same name and at least one co-author name. 152 Intuition Behind This Workflow s1 We control how tuple enrichment happens, using different matchers. union s0 d3

union d1 s0 d4 d2 Since homepages are often unambiguous, we first match homepages using the simple matcher s0. This allows us to collect co-authors for Luis Gravano and Chen Li. So when we finally match with tuples in DBLP, which is more ambiguous, we (a) already have more evidence in form of co-authors, and (b) use the more conservative matcher s1. 153 Another Example Suppose

distinct researchers X and Y have very similar names, and share some co-authors e.g., Ashish Gupta and Ashish K. Gupta Then s1 matcher does not work, need a more conservative matcher s2 union s1 s2 union s0 d3 union d1 s0 All mentions with

last name = Gupta d4 d2 154 Need to Exploit a Lot of Domain Knowledge in the Workflow [From Shen, Li, Doan, AAAI-05] Type Aggregate Example No researcher has chaired more than 3 conferences in a year Subsumption If a citation X from DBLP matches a citation Y in a homepage, then each author in Y matches some author in X Neighborhood If authors X and Y share similar names and some coauthors, they are likely to match Incompatible

Layout No researcher exists who has published in both HCI and numerical analysis If two mentions in the same document share similar names, they are likely to match Uniqueness Mentions in the PC listing of a conference refer to different researchers Ordering If two citations match,then their authors will be matched in order Individual The researcher named Mayssam Saria has fewer than five mentions in DBLP (e.g. being a new graduate student with fewer than five papers) 155 Need Support for Incremental update of matching workflow We

have run a matching workflow E on a huge data set D Now we modified E a little bit into E How can we run E efficiently over D? exploiting the results of running E over D Similar to exploiting materialized views Crucial for many settings: testing and debugging expansion during deployment recovering from crash 156 Research Challenges Similar to those in extracting mentions Need right model / representation language Develop basic operators: matcher, merger, etc. Ways to combine them match execution plan Ways

to optimize plan for accuracy/runtime challenge: estimate their performance Akin to relational query optimization 157 The Ideal Entity Matching Solution We throw in all types of information training data (if available) domain constraints and all types of matchers + other operators SVM, decision tree, etc.

Must be able to do this as declaratively as possible (similar to writing a SQL query) System automatically compile a good match execution plan with respect to accuracy/runtime, or combination thereof Easy for us to debug, maintain, add domain knowledge, add patches 158 Recent Work / Starting Point SERF project at Stanford Develops a generic infrastructure

Defines basic operators: match, merge, etc. Finds fast execution plans Data cleaning project at MSR Solution to match incoming records against existing groups E.g., [Chaudhuri, Ganjam, Ganti, Motwani, SIGMOD-03] Cimple project at Illinois / Wisconsin SOCCER matching approach Defines basic operators, finds highly accurate execution plans Methods to exploit domain constraints [Shen, Li, Doan, AAAI-05] Semex project at Washington Methods to expoit domain constraints [Dong et. al., SIGMOD-05] 159

Mention Tracking day n John Smiths Homepage day n+1 John Smiths Homepage John Smith is a Professor at Foo University. John Smith is a Professor at Bar University. Selected Publications: Databases and You. A. Jones, Z. Lee, J. Smith. Selected Publications: Databases and That One Guy. J. Smith. ComPLEX. B. Santos, J. Smith. Databases and You. A. Jones, Z. Lee, J.

Smith. Databases and Me: C. Wu, D. Sato, J. Smith. ComPLEX: Not So Simple. B. Santos, J. Smith. Databases and Me. C. Wu, D. Sato, J. Smith. How do you tell if a mention is old or new? Compare mention semantics between days How do we determine a mentions semantics? 160 Mention Tracking Using fixed-width context windows often works

John Smiths Homepage John Smith is a Professor at Foo University. John Smiths Homepage John Smith is a Professor at Bar University. But not always. Databases and You. A. Jones, Z. Lee, J. Smith. ComPLEX. B. Santos, J. Smith. Databases and You. A. Jones, Z. Lee, J. Smith. ComPLEX: Not So Simple. B. Santos Even intelligent windows can use help with semantics Databases and Me: C. Wu, D. Sato, J.

Smith. Databases and Me. C. Wu, D. Sato, J. Smith. 161 Entity Tracking Like mention tracking, how do you tell if an entity is old or new? Entities are sets of mentions, so we use a Jaccard distance: Day k Entity E1 m1 m2 Entity E2 m3 m4

m5 entity-1 entity-? = 0.6 entity-1 entity-? Day k+1 Entity F1 n1 n2 n3 entity-2 entity-? entity-2 entity-? = 0.4 Entity F2 m3 m4 m5 162 Monitoring and Event Detection The

real world might have changed! And we need to detect this by analyzing changes in extracted information University of Affiliated-with Wisconsin Affiliated-with Research Raghu Ramakrishnan Raghu Ramakrishnan Gives-tutorial Yahoo! SIGMOD-06

Gives-tutorial SIGMOD-06 Infer that Raghu Ramakrishnan has moved to Yahoo! Research 163 Tutorial Roadmap Introduction to managing IE [RR] Motivation Whats different about managing IE? Major research directions Extracting mentions of entities and relationships [SV] Uncertainty management Disambiguating extracted mentions [AD] Tracking mentions and entities over time

Understanding, correcting, and maintaining extracted data [AD] Provenance and explanations Incorporating user feedback 164 Understanding, Correcting, and Maintaining Extracted Data 165 Understanding Extracted Data Jim Gray Web pages ** * * * * * **

Jim Gray ** * SIGMOD-04 give-talk SIGMOD-04 ** * Text documents Important in at least three contexts Development developers can fine tune system Provide services (keyword search, SQL queries, etc.) users can be confident in answers Provide feedback

developers / users can provide good feedback Typically provided as provenance (aka lineage) Often a tree showing the origin and derivation of data 166 An Example System extracted contact(Sarah, 202-466-9160). Why? contact(Sarah, 202-466-9160) contact relationship annotator person-name annotator phone-number annotator I will be out Thursday, but back on Friday. Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007.

This rule fired: person-name + can be reached at + phonenumber output a mention of the contact relationship Used regular expression to recognize 202466-9160 as a phone number 167 In Practice, Need More than Just Provenance Tree Developer / user often want explanations why X was extracted?

why Y was not extracted? why system has higher confidence in X than in Y? what if ... ? Explanations thus are related to, but different from provenance 168 An Example contact(Sarah, 37007) contact relationship annotator person-name annotator Why was 202-466-9160 not extracted? phone-number annotator

I will be out Thursday, but back on Friday. Sarah can be reached at 202-466-9160. Thanks for your help. Christi 37007. Explanation: (1) The relationship annotator uses the following rule to extract 37007: person name + at most 10 tokens + can be reached at + at most 6 tokens + phone number contact(person name, phone number). (2) 202-466-9160 fits into the part at most 6 tokens. 169 Generating Explanations is Difficult Especially for why was A not extracted? why does system rank A higher than B? Reasons many possible causes for the fact that A was not extracted

must examine the provenance tree to know which components are chiefly responsible for causing A to be ranked higher than B provenance trees can be huge, especially in continuously running systems, e.g., DBLife Some work exist in related areas, but little on generating explanations for IE over text see [Dhamankar et. al., SIGMOD-04]: generating explanations for schema matching 170 System developers and users can use explanations / provenance to provide feedback to system (i.e., this extracted data piece is wrong), or manually correct data pieces This raises many serious challenges. Consider the case of multiple users providing feedback ... 171 Motivating Example

172 The General Idea Many real-world applications inevitably have multiple developers and many users How to exploit feedback efforts from all of them? Variants of this is known as collective development of system, mass collaboration, collective curation, Web 2.0 applications, etc. Has been applied to many applications open-source software, bug detection, tech support group, Yahoo! Answers, Google Co-op, and many more Little has been done in IE contexts

except in industry, e.g., epinions.com 173 Challenges If X and Y both edit a piece of extracted data D, they may edit the same data unit differently How would X and Y reconcile / share their edition? E.g., the ORCHESTRA project at Penn [Taylor & Ives, SIGMOD-06] How to entice people to contribute? How to handle malicious users? What types of extraction tasks are most amenable to mass collaboration? E.g., see MOBS project at Illinois [WebDB-03, ICDE-05] 174 Maintenance As

data evolves, extractors often break Some Country Codes Congo 242
Egypt 20
Belize 501
Spain 34
Some Country Codes Congo Africa 242
Egypt Africa20
Belize N. America 501
Spain Europe34
(Congo, 242) (Egypt, 20) (Belize, 501) (Spain, 34) (Congo, Africa)

(Egypt, Africa) (Belize, N. America) (Spain, Europe) 175 Maintenance: Key Challenges Detect if an extractor or a set of extractors is broken Pinpoint the source of errors Suggest repairs or automatically repairs extractors Build semantic debuggers? Scalability issues 176 Related Work / Starting Points Detect broken extractors Nick Kushmerick group in Ireland, Craig Knoblock group at ISI, Chen

Li group at UCI, AnHai Doan group at Illinois Repair broken extractors Craig Knoblock group at ISI Mapping maintenance Renee Miller group at Toronto, Lucian Popa group at Almaden 177 Summary: Key Points of Tutorial Lot of future activity in text / Web management To build IE-based applications must go beyond

developing IE components, to managing the entire IE process: Manage the IE workflow, manage mention matching Provide useful services over extracted data Manage uncertainty, understand, correct, and maintain extracted data Solutions here + IR components can significantly extend the footprint of DBMSs Think System R for IE-based applications! 178 How Can You Start We are putting pointers to literature, tools, & data at http://scratchpad.wikia.com/wiki/Dblife_bibs (all current DBLife bibliographies also reside here) Please contribute! Also watch that space

Tutorial slides will be put there Data will be available from DBLife, Avatar project, and Yahoo, in significant amount Will be able to navigate there from our homepages 179

Recently Viewed Presentations