Category Translation: Learning to Understand Information on the Internet

1 Introduction and Motivation

The number and diversity of information sources on the Internet is increasing rapidly. A number of tools such as Gopher, WAIS, and Web Crawlers are available to help people search for the information they need. How­ ever, these tools are unable to interpret the results of their searches and are unable to use multiple informa­ tion sources in concert. A number of more sophisticated AI systems have emerged, including SIMS [Knoblock et al. , 1994], the Information Manifold at AT&T [Kirk et al., 1995], and the Internet softbot [Etzioni and Weld, 1994]. However, each of these AI systems requires so­ phisticated models of the different information sources it is able to access. As a result, there are two barriers that prevent AI approaches from keeping up with the explosion of information sources on the Internet. First, effort has to be devoted to hand coding a model of each source. Second, sources unknown to the programmers associated with each AI system cannot be modeled. To enable the AI approaches to scale with the growth of the Internet, we explore the problem of automatically learning models of information sources. This learning problem raises four fundamental questions:

*We thank Dayne Freitag, Craig Knoblock, and Tom Mitchell for inspiring discussions that contributed to our problem formulation. We thank Dymitr Mozdyniewicz for his assistance with experiments, and Anchana Kullavanijaya for her transcription help. This research was funded in part by Office of Naval Research grant 92-J-1946 and by National Science Foundation grant IRI-9357772. Mike Perkowitz is supported, in part, by an NSF graduate fellowship.

• Discovery: how does the learner find new and un­ known information sources? (e.g., a web page repre­ senting the Brown phone ·directory has recently come on-line.)
• Protocol: what are the mechanics of accessing an in­ formation source and parsing the response into tokens? (the Brown directory is searched by sending a string such as "kaelbling" to the Brown server, and receiving back a string.)
• Semantics: how does the learner come to understand the information available at the source? (the tokens de­ scribe Kaelbling's e-mail address, phone number, depart­ ment, etc.)
• Quality: What is the accuracy, reliability, and scope of the information source? (the directory contains accu­ rate information about people at Brown, not elsewhere.)

Satisfactory answers to all of these questions would enable us to construct an autonomous Internet learn­ ing agent able to discover and use information resources effectively. As a first step, this paper -investigates the question of learning semantics.

Our learning method is based on the following idea, due to St. Augustine [Wittgenstein, 1958]. Consider how you might learn the Latin term uxor by example. Sup­ pose I tell you "George Washington's uxor was Martha." You might reason that, because "Martha" was the name of Washington's wife, perhaps "uxor" means "wife" . If, however, you knew that Washington also had a sister named "Martha", you might wait until you saw another example, perhaps asking "Who was Jefferson's uxor?" This method of learning relies on three key assumptions. First, you are familiar with George Washington. Second, you have a concept corresponding to uxor, e.g. wife. Third, you are willing to establish a general correspon­ dence between your concept wife and the concept uxor based on the example given. As we show below, this leap of faith can be viewed as an inductive bias and formal­ ized as a determination. We refer to this determination as the correspondence heuristic.

This paper is organized as follows. In the next sec­ tion, we define the category translation problem. We then present the Internet Learning Agent (!LA) and ex­ plain its learning method. Following that, we describe experiments in a simple Internet domain and present re­ sults. We then describe a probabilistic model of !LA that bounds its sample complexity. We conclude with a critique and directions for future work.

2 The Category Translation Problem

Below, we present both a concrete example and a gen­ eral formulation of the category translation problem. Suppose, for example, the agent queries the University of Washington staff directory with the token Etzioni and gets the response Oren Etzioni 685-3035 FR35. Based on its knowledge about Etzioni, we'd like the agent to come up with the general model of the directory shown at the bottom of Table 1 under "Response" .

To solve the category translation problem, an agent has to generalize from the observed queries and re­ sponses to a logical expression made up of model at­ tributes. To generalize effectively, the agent has to em­ ploy some inductive bias. !LA has to assume that the information source (IS) is (roughly) invariant when re­ sponding to queries about different individuals. It would be difficult to learn a model of an IS that responded with random facts about each individual queried - the phone number for one person, the birth date of a second, and the social security number for a third.

As with St . Augustine's method, !LA requires an over­ lap between its world model and the information re­ turned by the source. First, !LA and the IS must share some individuals. If the agent is only familiar with UW faculty, and the IS contains information about current Brown undergraduates, learning will prove problematic. Second, !LA and the IS must share some categories. If !LA is familiar with people and the IS is a catalog of stellar constellations, there is no basis for learning. Of course, !LA is not limited to people and their phone numbers. The same method could be used to learn about movie databases, product catalogs, etc.

We formalize the learning problem as follows. Let I be an IS that contains k fields . We represent I with the functions h(o) .. . h(o) , where each Ij(o) re­ turns the jth field in the output when I is queried with object o. For the example in Table 1, we would say that staffdir4 (Pl) = FR-35. In standard con­ cept learning terms, !LA is trying to learn or approxi­ mate the functions h .. h, based on examples of the form h(o) = T1, I2(o) = T2, .. . , Ik(o) = Tk .

The correspondence heuristic has two components. First, a match of tokens between the agent's model and the IS indicates a match of categories. For example, when !LA queries with Etzioni and sees 685-3035 in the third field, it explains this response as Etzioni's phone-number. Second, a category match on one indi­ vidual suggests a match on all individuals- the meaning of the IS field is consistent across individuals. Contin­ uing the previous example, !LA would now hypothesize that the third field was phone-number, for every individual in the IS. In order to find a hypothesis for which this generalization holds, we must test hypotheses on multiple observations and choose the best hypothesis.

More formally, let S(I, o) be true if o is an object in I. If two objects o1 and o2 are both in an IS, then we believe that, for some attribute M·, if we query the IS with o1 and the jth field is M· ( o1) then, when we query with 02, the jth field will be M·(o2), where M· is an arbitrary composition of model attributes.

We can state the correspondence heuristic as the fol­ lowing determination:

The equation Ij ( o!) = M· ( o!) encodes the assumption that the jth element of l's response can be described as a logical expression M·, which is composed of model at­ tributes. The implication encodes the assumption that , for some M·, the equality observed for one individual holds for all others for which S is true. The existential quantifier suggests that we need to search for the ap­ propriate M· . The next section describes !LA's search strategy, and its use of multiple queries to track down M· .

3 Algorithm

In essence, !LA queries the IS with known objects and searches for token correspondences between its model and information returned by the IS. !LA generates hy­ potheses based on these correspondences and ranks them with respect to how often they accord with observations. To flesh out this algorithm sketch we have to answer sev­ eral questions:

1. Which object in its internal model should !LA query the IS with?
2. What is the appropriate mapping from that inter­ nal object to a query string? (in the case of a person, the IS might be queried with the person's last name, full name, social security number, etc.)
3. What are possible explanations (denoted by M· in our determination) for each token in the response?
4. How should !LA evaluate competing explanations? We consider each question in turn.

Initially, !LA may use any object in its internal model to query the IS: a person, a tech report, a movie, etc. To constrain the set of possible queries, !LA utilizes any information it has about the IS. This knowledge could be expressed as a constraint on the type of object that can be in the IS or as an attribute that is only true of objects likely to be found in the IS. For example, if it knows that the IS is a personnel directory, !LA will not query the IS with movie titles.

In addition, !LA employs several heuristics to reduce the number of queries necessary to converge to a satis­ factory model of the IS. Most important , !LA attempts to discriminate between two competing hypotheses by choosing an object for which the hypotheses make dif­ ferent predictions ( cf. [Rajamoney, 1993]) . For exam­ ple, if !LA has seen the record Oren Etzioni 685-3035 FR-35, it will consider both lastname and userid as

Given:

1. Incomplete internal world model:
2. Objects (e.g., persons: P1, P2, ... , Pn) .
3. Attributes of the objects (e.g., lastname( Pl)=Etzioni, department( P1)=CS, userid( P1)=Etzioni, mail-stop(CS)=FR-35, . .. ).
4. An external information source (IS) that responds to queries. e.g. staffdir, the University of Washington personnel directory: Query: Etzioni

Response: Oren Etzioni 685-3035 FR-35

Determine: A set of logical expressions composed of model attributes which explains the observed query /response pairs. e.g. Query: lastname(person)

Response:

first field = firstname(person)

second field = lastname(person)

third field = phone-number(person)

fourth field = mail-stop(department(person))

Note that the explanation may involve compositions of model attributes, as in the case of mail-stop, and that we seek to minimize the number of queries made.

Table 1: The Category Translation Problem.

hypotheses for the second field because Etzioni's userid is his last name. To discriminate between the two hy­ potheses, !LA will attempt to query with someone whose userid is different from her last name. If no discriminat­ ing query is possible, !LA will attempt to find an object that has the potential to disconfirm the leading hypoth­ esis. In the above example, if !LA hypothesizes that the third field is phone-number, it will choose a per­ son whose phone number is known over a person whose phone number is not. Finally, if neither a discriminat­ ing nor a disconfirming query is possible, !LA will query with an object about which it has much information, in order to increase the likelihood of recognizing some token in the response. Discriminating queries typically accelerate !LA's ability to converge on a satisfactory hy­ pothesis; in the case of staffdir, for example, when !LA does not make use of discriminating queries, it requires 50% more queries to converge on the same hypotheses.

Once a particular object is chosen, !LA has to decide which query string to actually send to the IS. Initially, !LA will try all known facts about the object as possible query strings, attempting to learn the appropriate query string for the IS. The learning mechanism used is, in essence, the same as the one described below for learning to interpret the IS's output.

Once !LA obtains a response from the external IS, it attempts to explain each token in the response. An ex­ planation is a chain of one or more model attributes com­ posed into a relation between the object and the token seen. For example, in !LA's model, people are associated with departments and departments associated with mail­ stops. The relation between a person and her mail-stop, then, is a composition of department and mail-stop­ the mail-stop of Pis mail-stop(department(P)) .

We employ a variant of relational pathfinding [Richards and Mooney, 1992] to discover a relation between the query object and each response token. Richards and Mooney's pathfinding technique performs a bidirectional breadth-first search in which constants are nodes in the graph and attributes on constants are edges between nodes. We use a fuzzy matcher to compare tokens from the IS to constants in !LA's model. Our current matching function ignores punctuation and spac­ ing and can allow substring matches (e.g., the learner can recognize "(206) 616-1845" and "616.1845" as being the same token). Consequently, our pathfinding is uni­ directional, proceeding from the query object to fuzzily­ matched tokens. 1

Suppose the agent starts with the model shown in Ta­ ble 1. It queries the IS with the last name of object P1 and gets the response Oren Etzioni 685-3035 FR35. It will now try to explain each response token in turn. For example, in order to explain "FR-35", !LA will start with P1 and spread out one step through the model, e.g., to CS and Etzioni. Since neither matches the target token "FR-35", !LA will continue spreading out from the current frontier, retaining the path to each current node (e. g., the attribute path from P1 to CS is department(x)). From CS, !LA will get to FR-35. Thus, the path to FR-35 is mail-stop(department(x)) . Since FR-35 matches the target, this path will be returned as an explanation.

Next, !LA evaluates the hypothesized explanation. With respect to a particular query, a hypothesis may be explanatory (it predicted the output actually seen), inconsistent (it predicted something else), or consistent (it made no prediction). Thus, a hypothesis h parti­ tions the set of responses to queries into Explanatory, Inconsistent, and Consistent subsets. We denote the number of elements in each subset by the ordered triple (E(h), I( h), C(h)). We refer to the triple as the score of the hypothesis h. Since a hypothesis is only generated when it successfully explains some response, we know that, for any h, E(h) 2: 1.

1 To perform bidirectional pathfinding, we would have to find the set of matching tokens in !LA's model, an expensive computation due to the size of the model.

The predictions of a new hypothesis are compared against old responses to compute the hypothesis's score. Overall, !LA compares each hypothesis against each re­ sponse exactly once, so learning time is linear in both the number of responses and the number of hypothe­ ses. To determine whether one hypothesis is better than another, !LA compares the number of inconsistent pre­ dictions by the two hypotheses. If the number of incon­ sistent predictions is equal, !LA compares the number of explanatory predictions. More formally, we say that the hypothesis h is better than the hypothesis h' if and only if:

That is, !LA chooses the hypothesis with the lowest I score and uses E scores to break ties. This is a good pol­ icy when incomplete information is more common than incorrect information because the I score (how often the hypothesis was inconsistent) is a better indicator of the accuracy of the hypothesis. An inconsistency arises ei­ ther when the hypothesis is inaccurate or when the in­ formation is incorrect. Because incorrect information is rare in our domain, a bad (high) I score indicates an inaccurate hypothesis. A hypothesis may fail to explain an observation due to incomplete information, because if we lack the relevant fact, the hypothesis makes no pre­ diction. Since incomplete information is relatively com­ mon, a bad (low) E score does not necessarily indicate low accuracy of the hypothesis. Therefore, I( h) is a bet­ ter indicator of the quality of h than E(h). Suppose !LA knows everybody's last name but only a few peo­ ple's userid. When trying to learn the userid field, the userid hypothesis will explain only a few observations (because it will make very few predictions) but will never be inconsistent. In contrast, lastname will explain many observations but will be inconsistent on others. Because !LA prefers low I scores, it makes the right choice.

!LA terminates the learning process when one of two conditions occur. One, it has run out of objects with which to query the IS. Two, its leading hypothesis is "significantly" better than its other hypotheses. The dif­ ference in I scores that is deemed significant is controlled by a parameter to !LA. Although !LA's running time is exponential in the depth of the relational pathfind­ ing search for an explanatory hypothesis, the maximal search depth is typically set to a small constant, keep­ ing !LA fast. As mentioned earlier, the running time is linear in the number of queries made and the number of explanatory hypotheses generated. In fact, as the exper­ iments in Table 2 show, !LA's running time is dominated by Internet transmission time.

4 Experimental Results

In this section, we report on preliminary experiments designed to test whether our approach is viable in a real­ world domain. We find that !LA is able to learn models of simple information sources on the Internet.

To factor out the issues of protocol (which we do not address in this paper), !LA is provided with an interface that standardizes the interaction with the information sources used. Each interface takes query strings as input and outputs a list of tokens which !LA attempts to un­ derstand. In our first experiment, !LA is provided with complete and correct models offaculty in the University of Washington's (UW) Computer Science Department, and is asked to learn a model of staffdir, the UW per­ sonnel directory. The first line of Table 2 shows the results of this experiment. We see that in 16 queries !LA was able to learn a correct model of staffdir. !LA spent 19 seconds interacting with staffdir and 24 CPU seconds searching for, and evaluating, hypotheses.

Below, we show the final scores of the leading hypothe­ ses for interpreting the second field of staffdir's output:

staffdir2(x) = lastname(x) Expl: 11 Incons: 0

staffdir2(x) = userid(x)

Expl: 8

Incons: 3

We see that for eight people, both the lastname and userid hypotheses correctly explained the second field in the output of staffdir. However, for three people, the userid hypothesis failed, leading !LA to consider lastname to be the correct hypothesis.

A general problem that arises in relying on token cor­ respondence to infer type correspondence is the occur­ rence of puns. A pun occurs when matching tokens are not actually instances of the same concept. A hypoth­ esis arising from a pun amounts to finding an incorrect composition of model attributes - one that is not true for all x and y. A pun is an instance of the general problem of an incorrect hypothesis resulting in a correct classification of a training example. One type of pun is entirely coincidental; a person's area code turns out to be the same as his office number. A spurious hypothesis resulting from a coincidental pun is easy to reject - it is unlikely to prove explanatory for more than a single example. However, we also encounter semi-regular puns - where there is a correlation between the two concepts which gives rise to the pun. As pointed out above, many people's userids are also their last names. Semi-regular puns may require many more queries to converge on the correct hypothesis, because both the correct and spuri­ ous hypotheses will make accurate predictions in many cases. Discriminating queries aim to address this prob­ lem by finding examples where the correct and spurious hypotheses make different predictions.

No matter how regular a pun, there must eventually be a difference between the correct hypothesis and the competitor.2 How hard it is to choose the best hypoth­ esis is a function of the learner's knowledge and the reg­ ularity of the pun. The system faces a tradeoff: it must balance time spent learning against confidence in the re­ sult. If !LA collects more examples, it can be more con­ fident in the correctness of its conclusions. The learner can never be fully certain it is not the victim of a partic­ ularly regular pun, but it will have some estimate of the likelihood that it has the right solution. We provide a quantitative analysis of this intuition in the next section.

One possible criticism of !LA is that it relies on an overlap between the individuals in its model and individ­ uals in the IS it is trying to learn. However, !LA ben­ efits from the presence of spanning information sources on the Internet. A spanning information source is one that contains objects from a wide variety of information sources. For example, the Internet service called whois reports information on individuals from a wide range of sites on the Internet and will, for example, return people from a particular school when queried with that school's name. !LA relies on its knowledge of local individuals to learn a model of whois, and then leverages its model of whois to learn models of a wide variety of remote sites on the Internet. Instead of relying on individuals from its model, !LA will query whois for new individuals at the target site. For example, when trying to learn the Brown directory, !LA will query whois with "Brown" to get information about people at Brown and use its learned model of whois to interpret the output. Our second experiment demonstrates this process (Table 2). The second line of the table shows the results of learn­ ing whois from knowledge of local people. Given the learned model of who is, we report on-!LA's performance in learning models of the personnel directories available at Berkeley, Brown, Cal-Tech, Cornell, Rice, Rutgers, and UCI. As the results in Table 2 demonstrate, !LA is able to learn fairly accurate models of these informa­ tion sources averaging fewer than 40 queries per source, most taking less than 15 minutes each, where the bulk of that time is spent in Internet communication. The processing time for !LA is less than three CPU minutes in most cases. Slow network connections contributed to the unusually large Internet times for who is and Cornell. The size of the Cornell directory and the generality of its matching contributed to the large processing time for that directory.

2 1£ there is no difference in extension between the two hy­ potheses, then they are equally good solutions to the learning problem.

5 Theoretical Analysis

We would like to understand how the accuracy of (and confidence in) !LA's hypotheses scale with the number of queries it makes, the size of its hypothesis space, the correctness of its information, and so on. We consider both Valiant's PAC model and an alternative probabilistic model of !LA. !LA is not a standard concept-learning program - !LA is learning a function from the query it issues to the response of the IS. Furthermore, the or­ acle used by !LA is a generalized membership oracle. However, learnability results in function learning the­ ory are specific to classes of functions learned, such as polynomial, or real-valued [Auer et a/., 1995]. Similariy, although specific concept classes have been shown to be learnable under the membership oracle [Angluin, 1988], we are not aware of any sample complexity results that apply directly to !LA. For this reason, we chose to make a number of strong simplifying assumptions and analyze !LA under the PAC model.

The PAC model provides a convenient framework for analyzing !LA's behavior, under the simplifying assump­ tion that queries to the IS are random. IHI is the size of the hypothesis space explored by !LA. We posit a probability distribution P over queries to the informa­ tion source I. The error E of a hypothesis his the prob­ abilistic weight of the queries on which the hypothesis h disagrees with the actual behavior of I:

For simplicity, we consider an IS with a single output field, where I(o) is the token returned by the IS, and h(o) is the value predicted by h. Haussler [Haussler, 1988] derives a lower bound on the number of exam­ ples necessary for PAC learning. If h is any hypoth­ esis that agrees with at least n queries from I, where n ::=: : ln( t!p. ), then we have the following: P(E(h, I) ::=: t:) ~ 1- 8.

To apply this bound to !LA, we have to assume that the information in I and in !LA's model is error free, that a perfect model of I can be found in !LA's hypothesis space, and that token matching is working perfectly. We can model the violation of these assumptions as random classification noise and use the bound due to [Angluin and Laird, 1988]: n :::: e1 ( 1 ! 211 b)1 lne 1 ~ 1 ), where TJb is an upper bound on the frequency of noisy classifications, and the learner chooses the hypothesis that is correct most often. Unfortunately, the number of queries sug­ gested by the bound is very large. For example, if we set 8 = 0.1, T}b = 0.05, and IHI = 2, we see that the number of queries necessary to guarantee c: ~ 0.05 exceeds 3,000. How does /LA get away with relying on far fewer queries in our experiments?

The PAC bounds are overly conservative for two rea­ sons. First, the bounds presuppose randomly distributed queries, whereas /LA makes discriminating queries which enhance its ability to converge quickly. Second, the PAC bounds are based on a worst case analysis where there is at least one hypothesis whose accuracy is just less than 1- c: , where the accuracy of a hypothesis h with respect to an IS I is 1- E(h, I) . The learning algorithm has to observe enough examples to rule it out and find . a hypothesis whose accuracy is at least 1 - c: with prob­ ability 1 - 8. Typically, puns are not as pernicious as this worst-case analysis would suggest . In the case of the lastname-userid pun in staffdir, for example, the best hypothesis (lastname) has accuracy of 1.0 and the next best hypothesis (userid) has accuracy 0.37. Only 2 queries are required to have 90% confidence that /LA will prefer the better hypothesis. Below, we derive a general bound that yields this observation.

Instead of asking how likely a learner is to find a hy­ pothesis whose accuracy is at least 1 - c:, we ask how likely the .learner is to pick the best hypothesis in its hypothesis space based on its observations. We can no longer guarantee that the hypothesis chosen has accu­ racy 1- c:. However, we can guarantee that the learner is likely to perform as well as possible, given its hypoth­ esis space. Furthermore, when the best hypothesis is much better than the other hypotheses in the space, relatively few queries are required to converge on the best hypothesis with high confidence. Below, we formal­ ize this intuition using elementary probability theory.

If a hypothesis has probability p of making a correct prediction, then the probability that the hypothesis will yield x correct predictions on n independent queries is the binomial distribution: px (1-p)n-x ( ~ ) . For simplicity and brevity, we analyze the case where the space contains exactly two hypotheses, and the learner chooses the hypothesis that makes fewest incorrect predictions. 3 Thus, if we consider the hypothesis g, with accuracy Ag, and the hypothesis b, with accuracy Ab, then the proba­ bility that after n queries /LA will prefer the hypothesis g is at least:

This formula sums the probability, under the binomial distribution, of the different states where g results in more correct predictions than b. 4 We can use the above formula to determine the number of queries n necessary to guarantee, with confidence at least c, that /LA will choose the hypothesis with accuracy at least Ag over the hypothesis with accuracy at most Ab . To do so, we choose the desired confidence level c, set the above formula equal to c, and solve for n .

Figure l(a) shows the number of queries required to choose hypothesis g over hypothesis b with a given con­ fidence, as a function of /, the difference in accuracy between g and b. The accuracy of g is fixed at 0.95. Curves are shown at various confidence levels. For ex­ ample, when 1 = 0.50, /LA must perform 3 queries in order to have 90% confidence of choosing g.

3 In our model, if the two hypotheses have equal scores, they have equal probability of being chosen.

4 We assume independence between the errors of g and b. Also, under the worst-case assumption that n- 1 hypotheses all have accuracy Ab, a similar formula can be derived for a hypothesis space of size n [Etzioni and Perkowitz, 1995] .

As 1 shrinks, !LA requires more queries to achieve high confidence. Note though that when 1 is very small , discriminating between g and b is less important. Fur­ thermore, discriminating queries enable !LA to converge on the high-accuracy hypothesis quickly even for small,. To demonstrate the advantage of discriminating queries over random queries, Figure 1(b) shows the number of random and discriminating queries necessary to achieve at least 90% confidence that the learner will prefer hy­ pothesis g over hypothesis b, again as a function of I · The accuracy of g is fixed at 0.95. The random­ queries curve is derived from Equation 1. Due to lack of space, we omit the derivation and assumptions under­ lying the discriminating-queries curve, but see [Etzioni and Perkowitz, 1995]. When Ag = 0.95 and 1 = 0.50, !LA requires only a single discriminating query to have 90% confidence that it has found the better hypothesis. In essence, it is so unlikely for g to be wrong and for b to be right on the same query that one query is sufficient for !LA to choose a hypothesis with high confidence.

In short, if there is a large gap between the best hy­ pothesis and its closest competitor, or we are able to perform discriminating queries, our probabilistic model shows that relatively few queries are necessary to have high confidence in choosing the best hypothesis. The model helps to explain how, using a small number of queries, !LA was able to learn accurate models of infor­ mation sources in the experiments summarized in Table 2.

6 Critique and Future Work

Our contributions include: formulating the Category Translation problem, developing !LA's algorithm, and formalizing its bias as a determination. We have tested !LA experimentally on a simple Internet domain, and analyzed its sample complexity within the PAC frame­ work and using a specialized probabilistic model.

We have identified several problems that !LA does not yet address. Category mismatch occurs when !LA fails to find categories corresponding to those of the external information source [Wiederhold, 1992] . For example, the IS records fax numbers, of which !LA is ignorant. To­ ken mismatch occurs when, despite having appropriate categories, !LA fails to find matching tokens due to a dif­ ference in representation. For example, !LA may record prices in dollars, but a Japanese information source may store prices in yen. Finally, !LA's conjunctive bias can prevent it from learning a category that corresponds to a disjunction of !LA's categories. In future work we expect to test !LA on substantially more complex Internet do­ mains, explore solutions to the above problems, and in­ vestigate the discovery and quality problems mentioned in the introduction.