Corpus-Based Knowledge Representation

1 Introduction

Declarative representation of knowledge has long been ac­ knowledged as a key building block of AI systems. A knowl­ edge base (KB) with associated reasoning mechanisms can serve as a backbone for tasks such as query answering, learn­ ing and diagnosis. One of the key challenges in deploy­ ing knowledge representation (KR) systems is the cost and the complexity of building the knowledge base, especially in cases where it needs to cover a broad domain. Building a KB is highly labor intensive for several reasons. First, the acquisition of domain knowledge and articulating it in a for­ mal language can be incredibly difficult. Second, since the KB needs to form a coherent logical whole, it is hard to dis­ tribute its creation of a knowledge base over multiple experts or knowledge engineers. Finally, no matter how broad the KB, it will be brittle at the edges of its knowledge - it can only be used for tasks whose knowledge needs have been an­ ticipated in advance. While all of the aforementioned diffi­ culties have received significant attention, together they still remain a fundamental challenge for knowledge representation technology.

This paper argues that there is an alternative approach to knowledge representation that has the potential of providing competitive functionality for a broad class of applications. In a nutshell, this approach, which we term corpus based representation, is based on collecting a large corpus of dis­ parate fragments of knowledge, and building a set of tools that are based on analyzing properties of the corpus. The

Jayant Madhavan

University of Washington Seattle, Washington, U.S.A. j ayant@cs. washington.edu

fragments of knowledge in the corpus can include individ­ ual KBs, database schemas with or without data instances of the schema, queries written over KBs and databases, and any form of meta-data associated with them. Unlike a KB that needs careful ontological design, the corpus is a set indepen­ dent uncoordinated contributions. The intuition is that if the corpus is large enough, then the patterns we identify in it can be of great use for knowledge intensive tasks.

Corpus-based knowledge representation is an outgrowth of our work on schema and ontology matching [Doan et a!., 2001; 2002]. The matching problem (which we elaborate on in Section 2), is to find a semantic mapping between two dis­ parate representations, be they database schemas or ontolo­ gies. While a detailed KB about the domain of the represen­ tations being matched could be of great value for the match­ ing task, such KBs rarely exist, and their construction is not cost effective. Instead, our approach to matching is based on analyzing the variations of representations in a corpus of schemas. This paper extends the idea of using a corpus to a general approach to knowledge representation. Specifically, we identify other tasks in which corpus-based representation can be useful, and then define preliminary version for the con­ tents of a corpus and the interfaces it should support.

We emphasize that corpus-based representation is not a re­ placement for traditional knowledge representation. There are many tasks in which very finely tuned reasoning is re­ quired, and such reasoning can only be done with a very well designed knowledge base (e.g., medical diagnosis, monitor­ ing spacecraft, and making sense of tax laws). Our goal is to explore the space of problems in which the laborious con­ struction of knowledge bases can be avoided.

2 A motivating application: matching disparate representations

The discussion in this paper spans many kinds of representa­ tions, ranging from database schema to ontologies in expres­ sive KR formalisms. Collectively, we use the term domain model to refer to representations in any of these formalisms. The term schema refers to intensional knowledge, such as the names of database tables and their respective columns, or to the terminological component of a KB. The ground facts (or, rows in a database) are called instance data.

Sharing data among multiple data sources and applications is a problem that arises time and again in large '.'!1terprises, 828 settings, coordination between government agencies, large-scale science projects, and on the World­ Wide Web. The problem has received significant attention in both the Al and Database communities, and over the years, several paradigms for data sharing have been imple­ mented, each appropriate for certain scenarios. Examples in­ clude data warehousing oriented architectures, data integra­ tion systems [Lenzerini, 2002; Draper et a!., 200 I], message passing systems (e.g., [MQSERIES, 2003]), web services, and peer-data management systems [Halevy et a!., 2003b; Kalnis eta!., 2002; Bernstein eta!., 2002]. 1

No matter what paradigm we employ to share the data, a key problem is the semantic heterogeneity between the do­ main models of data sources that were originally designed independently. Thus, to obtain meaningful interoperation, one needs a semantic mapping between the schemas. A semantic mapping is a set of expressions that specify how the data in one database corresponds to the data in another database [Madhavan eta!., 2002]. While languages for spec­ ifying semantic mappings have been developed and are well understood (see [Lenzerini, 2002; Halevy, 200 I] for surveys), the creation of semantic mappings has become a key bottle­ neck as it is labor intensive and error-prone.

The goal of schema matching is to assist a human to relate two domain models. Complete automation of the process is unlikely to be possible, but the goal is to significantly increase the productivity of human experts. The matching problem is difficult because it requires understanding the underlying se­ mantics of the domain models being matched. While a do­ main model (with its instance data) provides many clues on its intended semantics, it does not suffice in order to relate it to a different domain model.

The process of generating a semantic mapping has tradi­ tionally been divided into two phases. The first phase finds a match between the two schemas. The match result is a set of correspondences between elements in the two schemas, stating that these elements are somehow related. For ex­ ample, a correspondence may state that agent in one do­ main model corresponds to contact in another. The second phase builds on the correspondences by creating the mapping expressions. The mapping expressions, often expressed as queries or rules, enable translating data from one data source to another, or reformulating a query over one data source into a query on the other. A plethora of techniques have been pro­ posed for schema matching: see [Rahm and Bernstein, 200 I] for a survey, and [Noy and Musen, 2002; Doan eta!., 2002; Do and Rahm, 2002] for some work since then. Collectively, these techniques mirror the heuristics that a human designer may follow. For example, techniques have considered ex­ ploiting relationships between names of elements in the do­ main models, structural similarities between them, similari­ ties in data values, and even correlations between values in different attributes. Several recent works on schema match­ ing are based on combining multiple techniques in a prin­ cipled fashion [Madhavan eta!., 2001; Doan eta!., 2001;

1 This paper accompanies an invited talk at the conference that surveys the successes and challenges in data integration to date.

Do and Rahm, 2002].

Corpus-based matching

Conceivably, detailed knowledge about the domain in which the matching is being performed can be an important resource in a schema matching system. However, creating an appro­ priate KB is often hard, and furthermore, the result may be brittle in the sense it only helps on its domain of coverage, and only provides a single perspective on the domain.

We are pursuing an alternate approach in which knowledge is gleaned by analyzing a large corpus of database schemas and previously validated mappings. There are two types of knowledge that we can glean from such a corpus. First, we can learn the different ways in which words (or terms) are used in database structures (i.e., as relation names, attribute names and data values). Second, the validated mappings show how variations in term usages correspond to each other in disparate structures.

Although such a corpus is not easy to construct, it is a very different kind of activity than building a detailed and com­ prehensive knowledge base. It does not require the careful ontological design as a knowledge base does, nor the careful control on its contents, thereby removing the key bottlenecks present in the design of knowledge bases. The corpus of­ fers multiple perspectives on modeling a particular domain, including different coverages of the domain. Thereby, it is more likely to provide knowledge that is useful for matching two disparate schemas.

In our initial work on the LSD system [Do an eta!., 200 l ], we investigated the benefit of learning from previously val­ idated mappings. In [Doan et al., 200 I] we considered the case where multiple data sources are mapped to a single me­ diated schema, on which users pose queries. We provided LSD with the mediated schema and a set of training matches for some data sources. LSD used these matches to learn mod­ els of the elements of the mediated schema. Since no single learning algorithm captures all the cues from the domain, we used a multi-strategy approach that combined the predictions of several learners. We then asked LSD to predict matches be­ tween the mediated schema and a set of test schemas. Our ex­ periments showed that (I) it is possible to achieve high accu­ racy with multi-strategy learning, and (2) additional accuracy is obtained by considering domain constraints (i.e., a simple form of domain knowledge). Overall, LSD achieved match­ ing accuracy of 75-90% on small to medium sized schemas of data sources on the Web. We extended LSD to consider simple taxonomies of concepts in [Doan eta!., 2002].

In recent work [Madhavan eta!., 2003], we investigate the benefit of a corpus of schemas and matches, and the ability to use such a corpus to predict mappings between a pair of schemas that have not been previously seen. Like in LSD, we learn models for elements in the corpus, using both the infor­ mation available in the schema and validated matches that are provided in the corpus. Given two schemas, S1 and S2 , we calculate for each element in them a similarity vector w.r.t. the corpus, i.e., how similar each element in si is to each el­ ement in the corpus. Very roughly speaking, if the similarity vectors of two elements a1 E S 1 and a2 E S2 are similar to each other, then we predict that a1 matches a2 . The results of our experiments show that (1) even with a modest corpus of 10 schemas we are able to achieve good accuracy, and (2) the correct matches found by using the corpus and those found by other previously known techniques overlap, but have sig­ nificant differences. Hence, the use of the corpus is finding matches that would not have been predicted by other tech­ mques.

3 The corpus-based representation principle

This paper argues that using a corpus of domain models is a general technique that can be applied in many applications as an alternative or complement to traditional knowledge repre­ sentation. Section 3.1 describes a few such applications, and Section 3.2 presents the components of a corpus-based repre­ sentation system.

3.1 Applications of corpus-based representation

The following are classes of applications that can benefit from corpus-based representation.

Web search and query answering: the first class of ap­ plications concerns various information finding tasks on the Web (or intranet). The first application is query answering on the web (e.g., [Kwok et al., 2001; Radev et al., 2002]): a nat­ ural language query is posed to a web search interface, and rather than finding relevant pages, the search engine tries to find the answers to the query. A second, very related appli­ cation, is focused crawling (e.g., [Sizov et al., 2003]), where the search engine is given a particular topic, and it tries to find pages relevant to it by starting at a set of initial pages, and crawling from them in a focused fashion. In both of these ap­ plications, the presence of additional domain knowledge has been shown or argued to be useful. However, the cost of con­ structing knowledge bases with such wide domain coverage would be prohibitive.

Creating and querying structured knowledge: one of the greatest impediments to using database and knowledge base technology is the conceptual difficulty of dealing with struc­ tured data versus unstructured text (the so called structure chasm [Halevy et al., 2003a]). It is well known that creating domain models (whether for database schema or knowledge bases) is a conceptual effort. Querying requires a different kind of effort- understanding someone else's domain model. Hence, a significant challenge for the KR and Database com­ munities is to create tools that facilitate the creation and querying of structured data. [Halevy et al., 2003a] argues that a corpus of schemas enables building several tools for this purpose.

One such tool would be a schema design advisor, which assists in the authoring of structured data, much in the spirit of an auto-complete feature. A user of the such a tool cre­ ates a schema fragment and some data in a particular domain, and the tool then proposes extensions to the schema using the corpus. The user may choose a schema from the list and modify it further to fit the local context. Note that besides time savings, such a tool has other advantages, such as pos­ sibly resulting in better designs and helping users conform to certain standards, when these are applicable. One can also imagine using corpus-based representation during the phase of verifying the correctness of a knowledge base. Hence, corpus-based representation can be an aid in creating tradi­ tional knowledge-based systems.

On the querying side, corpus-based representation can fa­ cilitate the querying of unfamiliar data. Specifically, consider a tool that enables you to pose a query using your own termi­ nology to any database. The tool would then use the corpus to propose reformulations of the your query that are well formed w.r.t. the schemas of the database at hand. The tool may pro­ pose a few such queries (possibly with example answers), and let you choose among them or refine them.

General properties of candidate applications: the exact characterization of which applications lend themselves to corpus-based representation is a subject for future research. One property of such applications that immediately stands out is that they use the knowledge base as an aid in resolv­ ing ambiguity. That is, the applications use a set of tech­ niques to propose plausible answers to a task, and then use the knowledge base to help rank the answers, rule out certain ones, or guide the search for answers. Hence, beyond the ap­ plications mentioned above, corpus-based representation can be useful in learning tasks, natural language processing and interfaces [Popescu et al., 2003 ], and information retrieval. In fact, as we explain in Section 4, corpus-based representa­ tion was inspired by the use of corpora (of different kinds!) in natural language processing and information retrieval. In contrast, corpus-based representation would be of limited use in applications that require intricate logical inference on care­ fully designed domain models (e.g., medical diagnosis, con­ trol of spacecraft, or reasoning about income-tax rules).

3.2 Corpus-based representation systems

We now offer some specific details on how corpus-based rep­ resentation systems can be built and used. We describe the types of contents we may put in a corpus, and the interfaces that the corpus provides to an application (see Figure 1).

Contents of a corpus

A corpus can include any kind of information related to struc­ tured data. In particular, it includes the following.

1. Various forms of domain-model information: on the less expressive end, the corpus can include relational and object-oriented database schema or entity/relationship dia­ grams, XML DTDs or schemas, possibly with associated in­ tegrity constraints (e.g., functional dependencies). On the more expressive end, the corpus can include terminologies.
2. Instance data: we can include the actual rows of tables (or representative rows), XML documents, or the assertion (A-Box) component of a terminological knowledge base or Horn theory. In fact we can include data sets that do not have a schema (e.g., certain file formats) . Note that it is very often the case that elements in the schema of one model may be in­ stance data in another model. Hence, the distinction between schema and instance data is not clean cut.
3. Validated mappings: mappings can be given directly be­ tween pairs of domain models, or go through an intermediate domain model [Madhavan eta!., 2002].
4. Queries: queries (posed by users or applications) provide important information about how certain data is used. For ex­ ample, when a database query performs a join over attributes of two different tables, that indicates that the columns are modeling the same domain (and this often not evident from the schema that only specifies the data type).
5. Other meta-data: there are many forms of meta-data that accompany domain models. They range from text descrip­ tions of the meaning of different fields to statistics about ta­ ble cardinalities or histograms on the set of possible values within a column.

It is important to emphasize that a corpus is not a logi­ cally coherent universal database. Rather, it is a collection of disparate structures, and there is relatively little control on the logical design of elements of the corpus. We expect that the domain-model information of the corpus will be stored and accessed using tools for model management [Bernstein, 2003], which attempt to provide a set of operators for manip­ ulating models of data (as opposed to the data itself).

Statistics on the corpus

There is a plethora of possible analyses that can be performed on such a corpus, and finding the most effective ones is a long term research challenge. Below we describe certain kinds of statistics that can be computed over the corpus. We classify them according to whether they apply to individual words or terms, partial structures, or to elements of particular schemas.

Word and term statistics: these statistics are associated with individual words (in any language) and with noun or verb phrases. These statistics indicate how a word is used in dif­ ferent roles in structured data. For each of these statistics, we can maintain different versions, depending on whether we take into consideration only word stemming, synonym ta­ bles, inter-language dictionaries, or any combination of these three. The statistics include:

1. Term usage: How frequently the term is used as a relation name, attribute name, or in data (as a percent of all of its uses or as a percent of structures in the corpus).
2. Co-occurring schema elements: For each of the different uses of a term, which relation names and attributes tend to appear with it? What tend to be the names of related tables and their attribute names? What tend to be the join predicates on pairs of tables? Are there clusters of attribute names that appear in conjunction? Are there mutually exclusive uses of attribute names?
3. Similar names: For each of the uses of a term, which other words tend to be used with similar statistical characteristics?

Composite statistics: the same statistics can be applied to partial structures. Examples of partial structures are sets of data instances, relations with associated attribute names, a re­ lation with some data (possibly with missing values).

Clearly, we need to significantly limit the nurri.ber of par­ tial structures for which we keep statistics (e.g., use tech­ niques for discovering partial structures that occur frequently e.g., [Polyzotis and Garofalkis, 2002]). Given statistics for certain partial structures, we can estimate the statistics for other related structures.

Statistics for schema elements: the same word, used in dif­ ferent structures, can have different meanings. Hence, we may want to characterize the specific usages of terms in struc­ tures, and relate them to usage of terms in other structures. For example, in [Madhavan eta!., 2003] we learn a classifier for every relation and attribute name in the corpus. Follow­ ing [Doan et al., 2001], we use meta-strategy learning. The training data used for learning is gleaned from the schema to which the element belongs and the training data of elements that have been mapped to it by a validated mapping in the corpus. Intuitively, the classifier is meant to recognize the particular usage of the term, even if it appears differently in another structure.

Application interfaces to the corpus

Applications built on a corpus should be able to access di­ rectly the statistics computed on the corpus, and perform the obvious lookups and queries on the corpus. In addition, just as knowledge based systems provide a set of higher-level in­ terfaces (e.g., in the spirit of [Chaudhri eta!., 1998]), the same could be done for corpus-based representation systems. The following are examples of functions such an interface could support. Note that the implementation of these inter­ faces poses many research challenges.

We classify the interfaces on whether they ask for factual queries, or similarity queries. In all cases, we expect that the answers returned will be a ranked list of answers. In addition, as in traditional knowledge bases, we should be able to obtain an explanation for the answers. In the notation used below, variables are prefaced by$.

Factual information: in the simplest case, a query is a non­ ground formula, and the corpus should return the possible groundings of the formula. As a simple example, we can ask for the values of$x, where Killed($x, Elvis). A different ex­ ample would be a higher-order query, e.g., find all the $P, such that $P(Toyota, Honda).

A more complicated function would take as input a set of constants and return formulas that include all of these constants. Here, the goal is to find how two terms are related without specifying exactly what role they play in a for­ mula. For example, the input may be GPA and studentiD, and the answers could be GPA(studentiD, $value) and Stu­ dent(studentiD, GPA, address). Note that the two terms play different roles in the two answers, and that the answers are templates for formulas (i.e., schema description), rather than particular sets of formulas.

In both of these cases, one can also complement the query with background knowledge. The knowledge may eliminate some answers or result in a different ranking of answers.

Similarity information: one of the key imports of the cor­ pus is that it contains different ways of saying similar facts. Similarity queries try to get at these different perspectives. In the simplest case, a query can be a ground fact, and the cor­ pus will return similar ways of saying the same thing. For example, the input can be Class(Lexus, luxury), and the output could be LuxuryCar(Lexus, Toyota), or even Car­ Review(Lexus, LuxuryCiass, VeryGood, goodTires).

In a more complex case, the query would consist of two terms, and the answer would be sets of facts in which these terms tend to play similar roles. For example, the input could be Review and Referee, and the answer would be ljcaiReview(paper1, reviewer2, accept) and AIJournai­ Referees(round2, paper3, reviewer4, reject). The answer could also specify where the terms are used differently, such as refereeing a soccer game and reviewing a movie.

In summary, we note some of the fundamental challenges in building an interface to a corpus. First, unlike logical knowledge/databases, answers are ranked rather than defining a boolean condition on data. Second, we are often interested in similarity querying, looking for different ways of saying the same thing 2 . Third, the answers returned often summa­ rize sets of facts or describe schema fragments. Finally, it is often useful to tell the user what is not an answer.

4 Related work

The corpus-based representation approach stands in stark contrast to an approach like the Cyc Project [Lenat and Guha, 1990] that attempts to build a comprehensive knowledge base of all common sense. A corpus is a collection of any set of small domain models that are not centrally designed or co­ ordinated. Importantly, the corpus is likely to include sev­ eral models of the same domain. One of the key engineer­ ing challenges that arose in building Cyc was how to enable several knowledge engineers to add to such a large knowl­ edge base without having to understand the entire knowl­ edge base. Contexts (e.g., [ Guha, 1991; Nayak, 1994; Giunchiglia and Ghidini, 1998]) are a mechanism proposed to address this complexity, where each knowledge engineer can focus on a small knowledge base, and then a set of lifting rules makes sure the entire knowledge base is semantically re­ lated. Unlike a corpus, contexts are still logically coordinated through a set of lifting rules.

The use of a corpus of structured data was first proposed in [Halevy eta!., 2003a]. There, the goal was to create tools that facilitate the creation, querying and sharing of structured data. That work was partially inspired by the use of large corpora in information retrieval and in statistical natural lan­ guage processing (e.g. [ Charniak, 1997]).

2 There is a large literature on similarity querying in databases and content based image retrieval, but these focus on similarities between objects represented as points in multi-dimensional space.

Several works have considered creating knowledge bases by a large set of independent contributors. The Open Minds Project [Singh eta!., 2002] collects knowledge from contrib­ utors on the web and builds a KB of common sense. Al­ though the contributers are independent, the knowledge en­ try is guided by a set of templates, and hence the creation of a coherent KB is possible. [Richardson and Domingos, 2003] describe how to create a feedback loop by which con­ sumers of knowledge provide indirect feedback to contribu­ tors of knowledge as to the usefulness of their contributions, thereby ultimately filtering out the bad contributions.

5 Conclusions

The analysis oflarge corpora is the key to the success oflnfor­ mation Retrieval techniques and to recent progress on Natural Language Processing. Corpus-based representation is predi­ cated on the idea that large corpora of domain models can be leveraged to create novel tools in service of knowledge repre­ sentation. The key advantage of corpus-based representation is that it avoids the need for careful logical design of a single comprehensive ontology. In addition, since a corpus will con­ tain multiple ways of representing the same information, it opens up opportunities for exploring transformations on data and addressing problems related to representational hetero­ geneity. This paper laid the foundation for corpus-based rep­ resentation, by describing preliminary versions of the con­ tents of a corpus, the interfaces to it, some applications in which it would be a powerful representational tool, and an application from which the approach was inspired.

Corpus-based representation offers many exciting research challenges, not the least of which is actually collecting a large enough corpus to be of interest. In addition, there is a ques­ tion about how focused the corpus needs to be in order to be useful in a particular domain. That is, can it only have domain models in that domain? Can domains models in other (pos­ sibly related) domains be useful, or do they only introduce noise that degrades the performance? Finally, no matter how a corpus is constructed, it can probably be manually tuned to perform even better. What form does such tuning take? While the challenges for corpus-based representation are enormous, we believe the payoffs could be huge, and the results can pro­ foundly impact how we create and use structured knowledge.

Acknowledgments

Many colleagues have contributed to the ideas that led to corpus-based representation. We would like to thank Phil Bernstein, Anhai Doan, Pedro Domingos, Oren Etzioni, Zack Ives, Pradeep Shenoy, and Igor Tatarinov. Funding was pro­ vided by an NSF CAREER/PECASE Grant IIS-9985114, ITR Grant IIS-0205635, a Sloan Fellowship, and gifts from Microsoft Research Intel, NEC and NTT.