Learning Value Predictors for the Speculative Execution of Information Gathering Plans

1 Introduction

The performance of Web information gathering plans can suffer because of I/0 latencies associated with the remote sources queried by these plans. A single slow Web source can bottleneck an entire plan and lead to poor execution time. When a plan requires multiple queries (either to the same source or to multiple sources), performance can be even worse, where the overhead is a function of the slowest sequence of sources queried.

When multiple queries are required, speculative plan execution (Barish and Knoblock 2002b) can be used to dramatically reduce the impact of aggregate source laten­ cies. The idea involves using data seen early in plan exe­ cution as a basis for issuing predictions about data likely to be needed during later parts of execution. This allows data dependency chains within the plan to be broken and parallelized, leading to significant speedups.

To maximize the utility of speculative execution, a good value prediction strategy is necessary. The basic problem involves being able to use some hint h as the basis for issuing a predicted value v. One approach in­ volves caching: we can note that particular hint hx corresponds to a particular value vy so that future receipt of hx can lead to prediction of vy. As a result, a plan that nor­ mally queries source S1 with hx and subsequently source S2 with Vy can be parallelized SO that both S1 and S2 are queried in parallel, the latter speculatively. Unfortu­ nately, caching has two major drawbacks. First, it does not scale well when the domain of hints is large. A sec­ ond drawback is the inability to deal with novel (previ­ ously unseen) hints, even when an obvious relationship exists between hint and predicted value.

In this paper, we present an alternative to caching that involves automatically learning predictors that combine classification and transduction in order to generate pre­ dictions from hints. Our approach succeeds where cach­ ing fails: the predictors learned usually consume less space than that demanded by caching and they are capa­ ble of making reasonable predictions when presented with novel hints, the latter leading to better speedups. Specifically, our work contributes the following:

• An algorithm that learns efficient transducers capa­ ble of a variety of string transformations.
• An algorithm that combines classification and trans­ duction to learn value predictors

The rest of this paper is organized as follows. The next section briefly reviews information gathering and pro­ vides a motivating example for speculative execution. In Section 3, we describe how classification and transduc­ tion can be used to build efficient and intelligent predic­ tors. Section 4 describes our learning algorithms that combine both techniques. Section 5 describes experimen­ tal results of using our approach. Finally, Section 6 de­ tails the related work.

2 Preliminaries

Web information gathering plans retrieve, combine, and manipulate data located in remote Web sources. Such plans consist of a partially-ordered graph of operators 0 1 .. On connected in a producer/consumer fashion. Each operator 0; consumes a set of inputs a1 .. aP, fetches data or performs a computation based on that input, and pro­ duces one or more outputs b1 .. bq. The types of operators used in information gathering plans vary, but most either retrieve or perform computations on data.

To better illustrate a Web information gathering plan, we consider the example plan Carlnfo, shown in Figure 1. Given constraints on car type and pricing, Carlnfo lo­ cates the make and model which has a median price clos­ est to that specified and then retrieves the full review of that car from the Web site ConsumerGuide.com. The plan consists of four Wrapper operators that fetch and extract data from various parts of the remote source. Specifically, the plan involves: (a) querying CarsDi­ rect.com for the car make and model having a median price closest to that specified, (b) querying Consumer­ Guide for the resulting make and model, (c) retrieving the link to the summary page for that car (using the link provided in the search results), and (d) retrieving the full review using the link provided on the summary page. (Sedan, $1900 OJ (hnp :1/cg.co m/sum m/22 89.h tm)

For example, for the input (Sedan, $19000), the car re­ turned is (Honda Accord), the summary URL for this car is (http://cg.com/summ/2289.htm) and the full review URL (http://cg.com/full/2289.htm). 1 Once at the full re­ view URL, the review text can be extracted.

Existing research on information agent executors (Barish and Knoblock 2002a) and network query engines (Hellerstein et a/. 2000, Naughton eta/. 2001, Ives eta/. 2002) has suggested a number of techniques for the effi­ cient execution of information gathering plans. Most of these systems work on the principle of streaming data­ flow, which executes plan operators as fast as their data dependencies allow and supports the pipelining of data between operators. Despite the benefits of streaming dataflow, plan execution can still be slow if there are many binding pattern relationships between sources in the plan. For example, notice that since steps (b), (c), and (d) are dependent on the steps that precede them, the plan in Figure 1 must be executed sequentially and prof­ its little from the benefit of streaming dataflow. Thus, if each source in Figure 1 has an average latency of 2s, than the average plan execution time is the summation of source latencies, or ( 4 *2s =) 8s.

2.1 Speculative Plan Execution

Speculative execution is one technique that can be used to overcome the effects of aggregate latencies in informa­ tion gathering plans containing multiple binding patterns.

As described in (Barish and Knoblock 2002b ), a plan is transformed into one capable of speculative plan exe­ cution by the insertion of two additional operators - Speculate and Confirm - at various points the plan, based on an iterative analysis of the most expensive path to execute within that plan. For example, one possible result of transforming the plan in Figure 1 for speculative execution is shown in Figure 2.

1 For the sake of brevity, we have abbreviated the URLs asso­ ciated with ConsumerGuide.com (although we retain the key aspects of its structure).

As shown, the Speculate operator receives copies of data sent to operators executing earlier in the plan. Based on the hints it receives, Speculate can. generate predicted values for later operators that can be transmit­ ted immediately to those operators. Thus, the earlier and later parts of the plan can be parallelized. After the ear­ lier operators finish executing, Speculate can assess whether or not its initial predictions were correct and forward the results onto a Confirm operator, which en­ sures that speculative data does not prematurely exit the plan or cause some other irreversible action to occur. Finally, notice that Figure 2 shows that speculation can be cascading: speculation about one operator can drive the speculation of another operator, leading to greater degrees of parallelism and thus arbitrary speedups.

As a result of the transformation shown in Figure 2, execution would then proceed as follows. Input data, such as (Sedan, $19000), would result in the retrieval of the initial search results in parallel with the predicted make and model - which would drive the predictions of summary and full-review URLs so that all four retrievals (three speculative) were executed at once. If all predic­ tions are correct, the resulting execution time can be re­ duced to only 2s plus the overhead to speculate, a maxi­ mum speedup of about 4. However, the average speedup depends on the average accuracy of prediction: the greater this accuracy, the higher the average speedup.

3 Value Prediction Strategies

Caching can be used to implement value prediction when speculatively executing plans such as Carlnfo. Unfortu­ nately, caching does not allow predictions to be issued for unseen hints. As a result, the average accuracy of prediction can be low when the domain of possible hints is large. Further, trying to achieve better accuracy under these conditions can require significant amounts of mem­ ory. In this section, we describe how a hybrid approach, consisting of classification and transduction, results in a more intelligent and space-efficient prediction strategy.

3.1 Classification

Classification involves extracting knowledge from a set of data (instances) that describes how the attributes of those instances are associated with a set of target classes. Given a set of instances, classification rules can be learned so that future instances can be classified correctly. Once learned, a classifier can also make reason­ able predictions about new instances - a combination of attribute values that had not previously been seen. The ability for classification to accommodate new instances is intriguing for the speculative execution of information gathering plans because, unlike with caching, it is possi­ ble to make predictions about novel hints.

For example, consider the prediction of the make and model of a car in the Carlnfo plan. It turns out that CarsDirect.com returns the same answer (Honda Accord) for "Sedan" as it does for other types (such as "All" and "Coupe") in the same price range. The association of the same make and model to multiple criteria combinations occurs somewhat frequently on CarsDirect.com.

To see why classification is a more effective technique than caching for the prediction of the make and model, consider prediction of a car based on type and price:

The data above IS what a cache would contain. In con­ trast, a classifier like Id3 (Quinlan 1986) would induce the following decision tree:

pri <= 18000 : Saturn S Series (2 . 0 ) pri > 18000 : I pri <= 19000 : Honda Accord (2.0) pri > 19000 : VW Beetle (2.0 )

When presented with an instance previously seen, such as (Sedan, 1 9000) , both the cache and the classifier would result in the same prediction: (Honda Accord). However, when presented with a new instance, such as (Coupe, 18500), the cache would be unable to make a prediction. In contrast, the classifier would issue the cor­ rect prediction of (Honda Accord) . Any errors made by classification would be caught automatically later in exe­ cution by the Confirm operator.

The decision tree above is also more space efficient than a cache for the same data. The cache requires stor­ ing 8 unique values. The decision tree above requires only storing 5 values Uust those shown) plus the informa­ tion required to describe tree structure and attribute value conditions (i.e. , pri <= 1 8000).

In short, classifiers such as decision trees can function as better, more space-efficient predictors. And in the worst case, where each instance corresponds to a unique class, a classifier simply emulates a cache.

3.2 Transduction

Transducers are finite state machines that transform input to output by using the former to iteratively proceed through a series of states that progressively produce the latter. One type of transducer is a string-to-string se­ quential transducer, defined by (Mohri 1997) as T = (Q, i, F, :E, !l, 8, cr), where Q is the set of states, i E Q is the initial state, Fr;;Q is the set of final states, :E and /l are finite sets corresponding to input and output alphabets, 8 is the state-transition function that maps Q x :E to Q, and cr is the output function that maps Q x /l to /l*. We are interested in a particular type of sequential transducer called a p-subsequential transducer that allows at most p output symbols to be appended to the output (i.e. , exist on the final state transition arc) .

Value prediction by transduction makes sense for Web information gathering plans primarily because of how Web sources organize information and how Web requests (i.e., HTTP queries) are standardized. In the case of the former, Web sources often use predictable hierarchies to catalog information. For example, in the Carlnfo exam­ ple, the summary URL for the 1999 Honda Accord was http://cg.com/summ/2289.htm and the full review was http://cg.com/full/2289.htm. Notice that both URLs use the same piece of dynamic information (2289) , but in different ways. By learning this transduction, we can then predict future full review URLs for corresponding sum­ mary URLs we have never previously seen. Transducers can also allow us to predict HTTP queries. For example, an HTTP GET query for the IBM stock chart is http://finance.yahoo. com/q?s=ibm&d=c. By exploiting the regularity of this URL structure, the system can pre­ dict the URL for the Cisco Systems (CSCO) chart.

In this paper, we define two new types of transducers that extend the traditional definition of p-subsequential transducers. The first is a high-level transducer, called a value transducer that describes how to construct the pre­ dicted value based on the regularity and transformations observed in a set of examples of past hints and values. Value transducers build the predicted value through sub­ string-level operations {Insert, Classify, and Transduce }. Insert constructs the static parts of predicted values. Classify categorizes hint information into part of a pre­ dicted value. Finally, Transduce transforms hint infor­ mation into part of a predicted value. Transduce uses a second type of special transducer, a hint transducer, in which the operations {Accept, Copy, Replace, Upper, Lower} all function on individual characters of the hint and perform the same transformation as their name im­ plies, with respect to the predicted value.

To illustrate, consider the transducers shown in Figure 3, for predicting the full-review URL in the Carlnfo ex­ ample. Figure 3 shows the value transducer performs high-level operations- the insertion of substrings and the call to a lower-level transduction. The second transducer (in abbreviated form) uses the Accept and Copy operations to transform the part of the hint value into its proper point in the predicted value. Thus, the first step builds the "http://cg.com/full!' part, the second step copies the "2289" part and the third step appends the ".htm" part.

In short, transducers lend themselves to value predic­ tion because of the way information is stored by and que­ ried from Web sources. They are a natural fit because URLs are strings that are often the result of simple trans­ formations on earlier input. Transducers are also space efficient: once learned, they occupy a finite size and can be applied to an endless number of inputs. Overall, for Web content that cannot be queried directly (instead re­ quiring an initial query and then further navigation), transducers serve as compact predictors that capitalize on the regularity of Web queries and source structure.

4 A Unifying Learning Algorithm

In this section, we present algorithms that induce value transducers (VTs), which combine classification and transduction, as predictors for the speculative execution of information gathering plans. The predictors learned represent not only a hybridization of classification and transduction, but also of caching, since classifiers default to caches when there is no feature of the key that is a particularly good indicator of the resulting value.

To learn a VT, the general approach consists of:

1. For each attribute of the answer tuple, identify an SD Template that distinguishes static from dynamic parts of the target string by analyzing the regularity between values of this attribute for all answers.
2. For each static part, add an Insert arc to the VT.
3. For each dynamic part, determine if transduction can be used; if so, add a Transduce arc to VT.
4. If no transducer can be found, classify the dynamic part based on the relevant attributes of the hint and add a Classify arc to the VT.

We implemented this in the algorithm LEARN-VALUE­ TRANSDUCER, shown below. The algorithm takes a set of hints, a set of corresponding answers, and returns a VT that fits the data:

1 Function LEARN-VALUE-TRANSDUCER returns ValueTransducer 2 Input: the set of hints H, the set of answers A 3 VT~0 4 tmp/ ~ LEARN-SD-TEMPLATE (A); 5 Foreach element e in tmpl 6 If e is a static element 7 Add Insert (e. value) arc to VT 8 Else if e is a dynamic element 9 DA ~ the set of dynamic strings in A for this tmpl element 10 HT~ LEARN-HINT-TRANSDUCER (H, DA) 11 IfHT !=0 12 Add Transduce (H7) arc to VT 13 else 14 c ~ LEARN-CLASSIFIER (H, DA) 15 Add Classify (C) arc to VT 16 Return VT 17 End /*LEARN-VALUE-TRANSDUCER*/

In this algorithm, learning a classifier can be achieved by decision tree induction algorithms such as Id3 (Quinlan 1986). Learning the SO template and the hint transform­ ing transducer, however, require unique algorithms.

4.1 Learning templates of string sets

Learning a VT requires first identifying a template for the target value that describes what parts are static and what parts are dynamic. Next, each static part is replaced with Insert operations and each dynamic part becomes a candidate for either transduction or classification.

To identify an SO template, we use an approach based on the longest common subsequence (LCS) between a set of values. First, an LCS identification algorithm similar to the one described by (Hirschberg 1975) is applied to the set of answer values. We then iterate through the LCS on each answer value to determine the set of possi­ ble static/dynamic templates that fit that answer. Only those templates common to all are kept - from this, one of the set is returned (though all are valid). The algo­ rithm that implements this, LEARN-SO-TEMPLATE, is shown below.

1 Function LEARN-SD-TEMPLATE returns Template 2 Input: set of strings S 3 tmpl~ 0 4 /cs ~ GET-LCS(S) 5 If seq!= 0 6 tmp/Set ~ 0 7 Foreach string s in S 8 curTmp/Set ~EXTRACT-TEMPLATES (s, /cs) 9 tmp/Set ~ tmp/Set n curTmp/Set 10 If tmp/Set != 0 11 tmpl ~ choose any member of tmp/Set /* all are valid */ 12 Return tmpl 13 End /* LEARN-SD-TEMPLATE */

4.2 Learning hint transducers

To learn a hint transducer (HT), we also make use of SO­ template identification. However, instead of identifying a template that fits all answers, we identify templates that fit all hints. Based on this template, we then construct an HT that accepts the static parts of the hint string and per­ forms the character-level transformation on the dynamic parts. A sketch of the algorithm that implements this, LEARN-HINT-TRANSDUCER, is shown below.

1 Function LEARN-HINT-TRANSDUCER returns HintTransducer 2 Input: the set of hints H, the set of resulting strings S 3 Use LCS to identify static parts between all H 4 Foreach H,S pair (h, s) 5 h '+-- extraction of h replacing static chars with token 'A' 6 A +-- Align (h: s) based on lowercased string edit distance 7 Annotate A with character level operations 8 End 9 RE +-- Build a reg expr that fits all annotations (using LCS) 10 IfRE !=0 11 Return general predictive transducer based on RE that accepts static sequences of H where necessary and transduces dynamic sequences. 12 Else 13 Return 0 14 End /* LEARN-HINT-TRANSDUCER*/

For example, suppose prior hints {Dr. Joe Smith, Dr. Jane Thomas} corresponded to values {joe_s,jane_t} . The algo­ rithm would first identify the static part of the hints and re­ write the hints using the Accept operation, i.e., { AAAAJoe Smith, AAAA!ane Thomas } where A refers to the operation Accept. It would then align each hint and value based on string edit distance and annotate with character operations required for transformation to the observed values, resulting in { AAAAALCCRLDDDD, AAAAALCCCRLDDDDD}. Next, it would use the LCS to build the regular expression {A *LC*RLD*} fitting these examples and, from this, the HT (partial form shown) in Figure 4:

5 Experimental Results

To evaluate our approach to value prediction, we com­ pared it with caching on three sample plans that can benefit from speculative execution. These plans were chosen because all query multiple sources and/or multi­ ple times within a source in order to retrieve information that is not possible to query directly. These plans nor­ mally require sequential execution; however, with specu­ lative execution, significant speedup is possible.

These plans included Carlnfo (which we have already described) , Replnfo, and Phonelnfo. Replnfo, based on the plan described in (Barish and Knoblock 2002b), que­ ries the site Vote-Smart.org for the issue positions of U.S. federal representatives for a particular nine-digit zip code. Its plan involves three queries: one for the list of representatives in the desired zip code, navigation to the profile page for each member, and navigation to their corresponding issue positions page. Phonelnfo is a simi­ lar plan that takes a U.S. phone number, does a reverse lookup of that number (on SuperPages.com) to find the state of origin and then queries the US Census (Quick­ Facts.census.gov) about demographics for that state. When querying the Census, additional navigation is re­ quired to get from the initial summary page about the state to the corresponding demographics details page.

All three were modified for speculative execution, with results similar to that shown in Figure 2. We then learned predictors for each, based on the data observed during execution. The learning was done offline, after each execution, so that future executions could benefit from the resulting predictors. The Carlnfo predictors, as described, involved classification (make/model/year to car summary page) and transduction (summary to full review page). Replnfo required classification (nine-digit zip to political district page) and transduction (district to issue positions page). Finally, Phonelnfo required classification (phone number to state) and transduction (initial state facts page to detailed demographics page).

When learning the predictors, instances were drawn from typical distributions for that domain; for example, instances for Rep Info were drawn from a list of addresses of individuals that contributed to presidential campaigns (obtained from the FEC)- a distribution that closely ap­ proximates the U.S. geographic population distribution. Similarly, the phone numbers used in Phonelnfo came from a distribution of numbers for common last names.

We implemented speculative execution in Theseus, a streaming dataflow system for Web information gather­ ing. Since our tests involved thousands of requests, we ran our plans using Theseus on local copies of the rele­ vant data and simulated network latencies during re­ trieval. In doing so, we assumed each source had a la­ tency of 2 seconds (note that the particular latency cho­ sen does not matter - speedups will be the same).

Our results focus on three measurements. The first, shown in Table 1, show the average number of examples required in order to learn the correct transducer required by each of the plans. Notice, that Rep Info required more than Phonelnfo or Carlnfo because there was a higher likelihood of the examples sharing some part of their dy­ namic data in common - and this was extracted by the LCS-based algorithm as a static element.

The second set of results, shown in Figure 5, focuses on the accuracy of classification, as measured over a 10fold cross-validation sample of the data (where no data in the test fold was in any of the training folds). As ex­ pected, domains with larger sets of discrete target classes (such as Replnfo) required many more examples than those with smaller numbers of classes (like Phonelnfo ).

The final set of results show how the learning we have described resulted in better average plan execution speedups than did caching. Due to space constraints, we show results from only one of the plans - Carlnfo - in Figure 6. This figure shows that, while the benefit of caching degrades significantly as the composition of fu­ ture requests contains a greater number of unseen exam­ ples, the learning allows accurate predictions to be made - even for a mix containing entirely new requests. Fur­ thermore, as the number of examples increases, speedup from learning increases and the accuracy of speculation (even on 100% unseen instances) gradually increases. Though omitted here, these same general trends hold for both Rep!nfo and Phonelnfo as well (although to different degrees).

6 Related Work

Learning to speculatively execute programs has been well-studied in computer science. Historically, however, computer architecture research has focused mostly on predicting control (e.g., branch prediction), not data. While hardware-level value prediction has recently be­ come an active area of research, the type of data being predicted (e.g., memory locations) is different.

At a high-level, this work could be considered a form of speedup learning. In speedup learning, the goal is to improve problem solving performance through experi­ ence. Past r{!search has focused on a number of areas, including learning sequences of operators (Fikes et a/. 1972) and learning control knowledge to aid in choosing what operators to execute next (Minton 1988). Although the use of learning in this work is for the purpose of value prediction (i .e., how to execute), the goal of using learned knowledge to improve performance is the same.

There has not been any previous work on value predic­ tion for information gathering systems. (Hull et a/. 2000) proposed speculation in a decision flow framework, but one in which only control predictions were necessary. There has also been past work on information gathering with partial results (Hellerstein et a/. 1997; Shanmuga­ sundaram et a!. 2000), but these systems do not predict data values and instead use approximate values from in­ termediate aggregate operators in order to obtain ap­ proximate final results.

Surprisingly, there has been little work on the learning of subsequential transducers. One existing algorithm is

Execution scenario OSTIA (Oncina et a/. 1993 ), which is able to induce tra­ ditional subsequential transducers capable of automating translations of decimal to Roman numbers or English word spellings of numbers to their decimal equivalents. Our work differs from OSTIA mainly in that the trans­ ducers we learn capture the general process of a regular class of string transformations. After learning from only a few examples, our algorithm can achieve a high-degree of accuracy on such classes. In contrast, while OSTIA can learn more complex types of subsequential transduc­ ers, it can require a very large number of examples before it can learn the proper rule (Gildea and Jurafsky 1996).

Figure 6: Learning vs. caching in Car Info

The transducer learning algorithm suggested by (Hsu and Chang 1999) viewed transduction as a means for in­ formation extraction. Our use is similar in that one part of our approach involves extracting dynamic values from hints. However, the transducers we describe go beyond extraction - they transform the source string so that it can be integrated into a predicted value. In doing so, our transduction process also makes use of classification.

Finally, while our use of classification applies to pre­ dicting any type of data value in an information gathering plan, our typical use of transduction is for the prediction of URLs. Other approaches have explored point-based (Zukerman et a/. 1999) or path-based (Su et a/. 2000) methods of URL prediction, attempting to understand request models based on either time, the order of re­ quests, or the associations between requests. However, unlike our approach, these techniques do not try to un­ derstand very general patterns in request content and thus cannot predict URLs that have not been previously requested.

7 Conclusions

Successful speculative execution of information gather­ ing plans is fundamentally linked with the ability to make good predictions. In this paper, we have described how a hybrid approach based on two simple techniques- classi­ fication and transduction - can be combined and applied to the problem. The approach we describe represents a hybridization of not only classification and transduction, but also of caching, since classifiers effectively function as caches when no classification is possible.

Our experimental results show that learning such pre­ dictors can lead to significant speedups when gathering information that must be queried indirectly. We believe that a bright future exists for data value prediction at the information gathering level, primarily because of the po­ tential speedup enabled by speculative execution and because of the availability of resources (i.e., memory) that exist at higher levels of execution, enabling more sophisticated machine learning techniques to be applied.

8 Acknowledgements

We wish to thank Steven Minton and Cenk Gazen for very helpful and inspiring discussions related to tech­ niques for template induction.

This material is based upon work supported in part by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory under con­ tract/agreement numbers F30602-0 1-C-0 197 and F3060200-l-0504, in part by the Air Force Office of Scientific Research under grant numbers F49620-0 1-1-0053 and F49620-02-l-0270, in part by the United States Air Force under contract number F49620-02-C-O 103, in part by gifts from the Intel and Microsoft Corporations. The U.S.Government is authorized to reproduce and distribute reports for Governmental purposes notwithstanding any copy right annotation thereon. The views and conclu­ sions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of any of the above organizations or any person connected with them.