Reactive Control of Dynamic Progressive Processing

1 Introduction

This paper is concerned with the design and implementa­ tion of an effective computational model for information retrieval search engines that can tradeoff computational resources against the quality of the result . Our approach is based on run-time monitoring of the information re­ trieval process and on dynamic selection of information retrieval techniques so as to maximize the quality of the answer produced with limited computational resources. Information retrieval from a large collection involves un­ certainty regarding the duration of the process and the quality of the result. In addition, there may be large variability in the number of requests that require a re­ sponse at any given time. By taking a context depen­ dent, dynamic approach to the problem we can signif­ icantly improve the average quality of service provided by such systems.

A typical search engine is composed of several informa­ tion retrieval modules that perform such tasks as query formation, query optimization, query evaluation, preci- sion improvement, recall improvement, clustering, and results visualization. For each one of these phases, there are a wide variety of techniques that have been devel­ oped in recent years [Jones and Willett , 1997]. Cur­ rently, search engines are built by choosing and integrat- . ing a fixed set of modules and techniques. The choices are made off-line by the designer of the system. This

Abdel-Illah Mouaddib

CRIL-IUT de Lens-Universite d'Artois Rue de l'universite, S. P. 16 62307 Lens Cedex France mouaddib@cril.univ-artois.fr

static approach excludes techniques that work well in special situations. In addition, current information re­ trieval systems are optimized for a particular load; they cannot respond dynamically to varying load, availability of computational resources, and to the specific charac­ teristics of a given query.

The ability to dynamically adjust computational ef­ fort based on the availability of computational resources has been studied extensively by the AI community since the mid 1980's. These efforts have led to the develop­ ment of a variety of techniques such as anytime algo­ rithms [Dean and Boddy, 1988; Zilberstein and Russell, 1996], design-to-time [Gravey and Lesser, 1993], flexible computation [Horvitz, 1988], imprecise computation [Liu et al. , 1991], and progressive reasoning [Mouaddib, 1993; Mouaddib and Zilberstein, 1997].

We adopt the progressive processing framework to for­ malize and solve the meta-level control problem of a real­ time information retrieval application. The technique maps each task to a progressive processing unit (PRU). Each PRU is composed of a set of modules that can con­ tribute to the quality of the result. This offers a natural framework to describe the set of information retrieval techniques available to the system. Figure 1 shows a simple task structure whose input is a query composed of a list of keywords. The task structure has three process­ ing levels. The first level includes three alternative tech­ niques to improve the initial query: (a) scan the query using concept recognizers to identify company names, dates, locations, personal names, and so on; (b) examine the query for pairs of words that have high statistical likelihood of being related and enhance the query with that information; (c) perform part-of-speech analysis to identify noun phrases within the query. The second level includes two alternative techniques that can improve the query's recall ability by expanding it to include related words and phrases: (d) use of Local Context Analysis (LCA), a statistical method for expanding queries that relies upon in-context analysis o( word co-occurrence; (e) use of InFinder, an association thesaurus that is faster than LCA and does not capture context as well. Finally, the third level performs the actual query evaluation and returns the results. Quality in this application is mea­ sured by the number of relevant documents within the top n documents retrieved (i.e., precision in the retrieved set).

The information retrieval application and the resulting task structure raise several fundamental issues that have not been previously addressed.

1. Handling the duration uncertainty and quality un­ certainty associated with each technique.
2. Handling the dependency of quality and duration on the quality of intermediate results.
3. Handling a rich task structure in which some lev­ els include several alternatives or optional compu­ tational steps; optional steps can be skipped under time pressure, leading to direct evaluation of the input query.
4. Selecting the "best" set of retrieval techniques in a dynamic environment taking into account the entire set of queries waiting for execution.

The rest of this paper offers an efficient solution to the meta-level control problem. Section 2 gives a formal definition of the problem. We then solve the problem in two steps. In Section 3, we develop an optimal solu­ tion for a single PRU, ignoring the fact that additional tasks are waiting for processing. Section 4 shows how to handle multiple PRUs using the approach developed in Section 3 and summarizing the effect of the waiting requests using the notion of an opportunity cost. In section 5 we address the issue of reactive control in a highly dynamic environment by estimating the oppor­ tunity cost and pre-compiling the control policies. We conclude with a summary of the results and a brief de­ scription of related work.

2 The meta-level control problem

This section describes more formally the problem of meta-level control of the (enhanced) progressive process­ ing model. Each information retrieval request is mapped to a task structure described below.

Definition 1 A progressive processing unit (PRU) is composed of a sequence of processing levels, (l 1 , l2, ... , lL). The first level receives the input query and the last one produces the result.

Definition 2 Each processing level, li, is composed of a set of Pi alternative modules, { mf, m~, ... , mf;}.

Each module can perform the logical function of levelli, but it has different computational characteristics defined below.

Definition 3 The module descriptor, P/ ((q', o)lq), of module m{ is the probability distribution of output quality and duration for a given input quality.

Note that q is a discrete variable representing quality and o is a discrete variable representing duration. The module descriptor specifies the probability that module m{ takes o time units and returns a result of quality q' when the quality of the previously executed module is q. Module descriptors are similar to conditional per­ formance profiles of anytime algorithms [Zilberstein and Russell , 1996]. They are constructed empirically by col­ lecting performance data for a sample set of inputs.

When the search engine responds to a particular re­ quest, it receives an immediate reward defined as follows.

Definition 4 A time-dependent utility function, U(q, t), measures the utility of a solution of quality q if it is returned t time units after the arrival time of the request.

We assume that there is a given constant T such that 'Vq, t > T U(q, t) = 0. That is, responding to a request more than T time units after its arrival has no value.

Suppose that a system maintains a set of information retrieval requests, W, with arrival times {a1 , a2 , ... , an}· The set of requests is updated dynamically as new re­ quests arrive. The system processes the requests in a first-in-first-out order using a progressive processing unit to handle each request.

Given a set of requests, the module descriptors of all the components of the progressive processing unit, and a time-dependent utility function, we define the following control problem.

Definition 5 The reactive control problem is the problem of selecting a set of alternative modules so as to maximize the expected utility over the set of information retrieval requests.

The meta-level control is "reactive" in the sense that we assume that the module selection mechanism is very fast, largely based on off-line analysis of the problem. The rest of the paper provides a solution to this problem.

3 Optimal control of a single PRU

We begin with the problem of meta-level control of a single progressive processing unit corresponding to a sin­ gle task. This problem can be formulated as a simple Markov decision process (MDP) with states representing the current state of the computation. The state includes the current level of the PRU, the quality produced so far, and the elapsed time since the arrival of the request. The rewards are defined by the utility of the solution which depends on both quality and time. The possible actions are to execute a module of the next processing level or to skip that processing level. The transition model is defined by the descriptor of the module selected for exe­ cution. The rest of this section gives a formal definition of the MDP and the reactive controller produced by solv­ ing it.

3.1 State representation

The execution of a single progressive processing unit, u, can be seen as an MDP with a finite set of states S = {(l;,q,t]ll; E u}U{[failure,t]} where 0::; i::; Lin­ dicates the last executed (or skipped) level, 0 ::; q ::; 1 is the quality produced by the last executed module, and 0 ::; t ::; T is the elapsed time since the arrival time, au, of the request. Note that quality is discretized and nor­ malized to be in the range [0 .. 1]. All the intermediate modules use a uniform representation of input and out­ put (a "query" in our application). Note also that T is the maximum delay after which we consider the response to be useless. When the system is in state [l;, q, t], one module of the i-th level has been executed. (The first level is i = 1; i = 0 is used to indicate the fact that no level has been executed.) The states [failure, t] represent termination at time t without any useful result. We dis­ tinguish between different failure states because failure can occur before the deadline leaving some remaining time for the execution of other requests in the queue.

3.2 Transition model

The initial state of the MDP is [lo, Qinit, t], where t is the elapsed time since the arrival of the request (t = current time - au) and Qinit is the initial quality of the request (0 in otir application) . The initial state indicates that the system is ready to start executing a module of the first level of the PRU. The terminal states are all the states of the form [lL, q, t] or [failure, t]. The for­ mer set represents finishing execution of the last level and the latter set represents failure. Other states such as [l;, Qmax, t] (reaching maximal intermediate quality) or [l;, q, T] (reaching the deadline before the execution of the last level) are not considered terminal states. A terminal state can be reached from state [l;, q, T] by ex­ ecuting a series of skip actions until a failure state is reached. Similarly skip actions take the automaton from state [l;, Qmax, t] to the last level because no execute ac­ tion can improve the intermediate quality.

In every nonterminal state the possible actions are: E{+1 (execute the j-th JllOdule of the next level) and S (skip the next level). To complete the transition model, we need to specify the probabilistic outcome of these actions. Equations 1-4 define the transition probabilities for a given nonterminal state [l;, q, t].

The S action is deterministic. It skips the next level without affecting the quality or elapsed time. (It can be implemented as an additional "dummy" module whose execution takes no time and has no effect on quality.)

Skipping the last level results in failure.

The E{+l action is probabilistic. Duration and qual­ ity uncertainties define the new state. Equation 3 deter­ mines the transitions following successful execution and Equation 4 determines the transition to the failure state when the deadline, T, is reached.

3.3 Rewards and the value function

Rewards are determined by the given time-dependent utility function applied to the final result (produced by the last level of the PRU). The utility depends on the quality of the result and the elapsed time. Keep in mind that in our application the intermediate results are use­ less and therefore have no direct rewards associated with them. We now define a value function (expected reward­ to-go) over all states. The value of terminal states is defined as follows.

The value of nonterminal states of the MDP is defined as follows.

The value function is defined as maximum over all ac­ tions with the top expression representing the value of a skip action for any levell; such that 0 ::; i ::; L- 1, the middle expression representing the value of a skip action for level l£_1, and the bottom expression representing the value of an execute action.

This concludes the definition of an MDP. This MDP is a finite-horizon MDP with no cycles. It can be solved easily using standard dynamic programming algorithms or using search algorithms such as AO*.

Theorem 1 Given one progressive processing unit u and a time-dependent utility function U(q, t), the optimal policy for the corresponding MDP is an optimal reactive control for u.

Proof: Because there is a one-to-one correspondence between the reactive control problem and the MDP (in­ cluding the fact that the PRU transition model satisfies the Markov assumption), and because of the optimal­ ity of the resulting policy, we conclude that it provides optimal reactive control for the progressive processing problem. D

We note that the number of states of the MDP is bounded by the product of the number of levels L, the maximum number of alternative modules per level maxipi, the number of discrete quality levels, and the maximum execution time. While the maximum execu­ tion time can be quite large, the time unit used for the purpose of meta-level control is an arbitrary system pa­ rameter. A small time unit leads to a more effective con­ trol at the expense of a larger state-space. The choice of a unit of quality has a similar effect. These units in­ troduce a tradeoff between the size of the policy and its effectiveness. Further empirical evaluation is needed to determine the best choice of time and quality units in practice.

4 Optimal Control of multiple PRUs using opportunity cost

Suppose now that we need to schedule the execution of multiple PRUs. We assume that there are n + 1 requests whose arrival times are ao :::; a1 :::; ... :::; an. One ap­ proach to construct an optimal schedule is to generalize the solution presented in the previous section. We can construct a larger MDP for the combined sequential de­ cision problem including the entire set of n + 1 PRU s (as illustrated in Figure 2). To do that, each state must also include i, the request number, leading to a general state represented as (i, l, q, t]. Note that t is the elapsed time since the arrival of the first request.

This rather complex MDP is still a finite-horizon MDP with no loops. Moreover, the only possible transitions between different PRUs are from a terminal state of one PRU to an initial state of a succeeding PRU. Therefore, we can solve this MDP by computing an optimal policy for the last PRU for any starting time between 0 and T + an+I - ao, then use the value of its initial states to compute an optimal policy for the previous PRU and so on .

Theorem 2 Given a set, W, of progressive processing units and a time-dependent utility function U(q, t), the optimal policy for the corresponding MDP is an optimal reactive control for W .

This is an obvious generalization of Theorem 1. The complete proof, by induction on the number of PRUs, is omitted.

We now show how to reformulate the effect of the re­ maining n requests on the execution of the first task. This reformulation preserves the optimality of the solu­ tion, but it suggests a more efficient control structure developed in Section 5.

Definition 6 Let V/(t) = V([i,l0 ,q0 ,t]) denote the ex­ pected value of the optimal policy for the last n - i + 1 PRUs.

To compute the optimal policy for the i-th PRU, we can simply use the following reward function.

In other words, the reward for responding to the i-th request is composed of the immediate reward (defined by the time-dependent utility function) and the reward­ to-go (defined by the remaining PRUs). Alternatively, the reward can be represented as follows.

Therefore, the best policy for the first PRU can be cal­ culated if we use the following reward function for final states:

Definition 7 Let OC(t) = Vt(O)- Vt(t) be the oppor­ tunity cost at time t.

The opportunity cost measures the loss of expected value due to delay in the starting point of executing the last n tasks (all the tasks except the first one).

Definition 8 Let the OC-policy for the first PRU be the policy computed with the following reward function:

The OC-policy is the policy computed by deducting from the actual reward for the first task the opportunity cost of its execution time.

Theorem 3 Controlling the first PRU using the OC­ policy is optimal.

Proof: From the definition of OC(t) we get:

To compute the optimal schedule we need to use the re­ ward function defined in Equation 9 that can be rewrit­ ten as follows .

But this reward function is the same as the one used to construct the OC-policy, except for the added constant Vt(O). Because adding a constant to a reward function does not affect the policy, the conditions of Theorem 2 are met and the resulting policy is optimal. D

Theorem 3 suggests an optimal approach to scheduling the entire n + 1 requests by first using an OC-policy for the first request that takes into account the opportunity cost of the remaining n requests. Then the OC-policy for the second request is used taking into account the opportunity cost of the remaining n - 1 tasks and so on. To be able to implement this approach we need to have the control policies readily available. This issue is addressed in the following section.

5 Reactive control based on estimated opportunity cost

In the previous section, we presented an optimal solu­ tion to the control problem of multiple progressive pro­ cessing units without accounting for its computational complexity. In particular, the opportunity cost must be computed and revised quickly each time a new request arrives. Once the opportunity cost is revised, a new pol­ icy for the current PRU must be constructed. Finding the exact opportunity cost requires the construction of an optimal policy for the entire set of tasks. In practice, this may slow down the operation of the information re­ trieval search engine.

In order to provide an effective reactive controller for dynamic progressive processing, it is necessary to:

1. use a fast approximation scheme to estimate the op­ portunity cost; and
2. use pre-compiled policies for different opportunity cost functions.

The rest of this section explains this method in more detail.

5.1 Estimating the Opportunity Cost

The opportunity cost is defined in terms of the func­ tion Vt which represents the value of an optimal policy for the remaining tasks in the queue. Thus, it can be estimated by approximating this function. One way to approximate the cumulative value of the remaining tasks is to add the value of each task without taking into ac­ count the opportunity cost. In this calculation, the start time of each task is the expected end time of the previ­ ous one. The following set of equations summarizes this approximation scheme.

where V[l, q, t] is the value function defined in Section 3 for a single PRU. Therefore, Vt can be approximated as follows .

The expected duration of task i, Ti, depends on the du­ ration of the previous tasks. Let r(t) be the expected duration of the optimal single-PRU policy when start­ ing at timet (relative to the arrival time of the request). Then Ti is computed using T with the expected starting time of task i relative to its arrival time.

The function T (expected duration) can be computed for any finite-horizon MDP once the optimal policy is avail­ able by simply using durations as rewards. The function can be computed once off-line, making it easy to revise the opportunity cost when a new request is added.

We are also examining an alternative learning tech­ nique to approximate the opportunity cost function based on such features as total queue size and total wait­ ing time. Standard functic;m approximation techniques can be used resulting in a compact representation of the opportunity cost. It is not clear at this point which ap­ proximation technique works better in practice. This will be determined based on empirical evaluation.

5.2 Pre-compiled control policies

To make the meta-level control truly reactive for large task structures, one may want to avoid computing a new policy (for a single PRU) each time the opportunity cost is revised. To avoid this, the space of opportunity cost can be divided into a small set of regions representing typical situations. For example, there could be just three regions that capture low, medium, and high loads. For each region, an optimal policy would be computed off­ line and stored in a library. At run-time, the system will first estimate the opportunity cost and then use the appropriate pre-compiled policy from the library. These policies remain valid as long as the overall task struc­ ture and the utility function are fixed. Because the de­ pendency of the control decisions on the opportunity cost is monotonic (higher costs imply less time for ex­ ecution), we anticipate that a small set of classes that correspond to qualitatively different action selection will be sufficient.

Another advantage of the use of pre-compiled policies is the ability to react quickly to dynamic changes. Con­ trol policies can be switched during the execution of a single request if the opportunity cost changes. This is possible because the policies share the same state space.

6 Conclusion

We present an innovative approach to meta-level control of progressive processing based on reformulating it as a Markov decision problem. It is shown that an optimal policy for a set of tasks can be constructed by controlling a single PRU, taking into account the opportunity cost of the remaining tasks. To apply this model to control the operation of an information retrieval search engine, a fast approximation of the opportunity cost is developed. Finally, a highly reactive controller is described that uses a library of pre-compiled control policies to operate in a dynamic environment.

A less complex model of progressive processing that re­ lies on heuristic scheduling has been developed [Mouad­ dib and Zilberstein, 1997]. The task structure, however, is limited to a linear set of levels with one module per level and no quality uncertainty or quality dependency. The heuristic scheduler is fast, but it cannot solve the more complex task structure presented in this paper and it does not provide optimal control. Heuristic scheduling of computational tasks has also been studied by Garvey and Lesser [1993] for the design-to-time problem-solving framework. The latter framework represents explicitly non-local interactions between sub-tasks.

The progressive processing framework relates to a large body of work within the systems community on imprecise computation [Liu et al., 1991]. Each task in that model is decomposed into a mandatory subtask and an optional subtask. A variety of scheduling al­ gorithms have been developed for imprecise computa­ tion under different assumptions about the optional part. Our model allows for a richer representation of quality and duration uncertainty and quality dependency. Un­ like imprecise computation, the schedule constructed by the MDP scheduler is a conditional schedule; the selec­ tion of modules is conditioned on the actual execution time and outcome of previous modules.

The application of dynamic programming to solve meta-level control problems have been previously used by Hansen and Zilberstein [1996] to control interruptible anytime algorithms. Optimal monitoring of progressive processing tasks using a corresponding MDP has been studied by Mouaddib and Zilberstein [1998] with respect to a simpler task structure. and without the notion of quality uncertainty and quality dependency.

The notion of opportunity cost is borrowed from eco­ nomics. It has been used previously in meta-level rea­ soning by Russell and Wefald [1991]. Horvitz [1997] uses a similar notion to develop a model of continual com­ putation in which idle time is used to solve anticipated future problems.

The use of pre-compiled control policies to construct a highly reactive real-time system has been studied by several researchers. For example, Greenwald and Dean [1998] show how a real-time avionics control system can use a library of schedules that cover all possible situa­ tions. Each schedule is conditioned on the state of the flight operation.

In collaboration with the Information Retrieval Cen­ ter at UMass we are currently developing the stochastic module descriptors for the components of the search en­ gine. By definition, IR tasks involve large collections and a substantial amount of test data allowing us to test the applicability and scalability of this resource-bounded reasoning technique.

Acknowledgments

We thank James Allan and Victor Lavrenko for their contribution to the problem formulation and to the con­ struction of the information retrieval testbed.

This work was supported in part by the National Sci­ ence Foundation under grants No. IRI-9624992, IRI9634938, and INT-9612092, by the Ganymedell Project of Plan Etat/Nord-Pas-De-Calais, and by IUT de Lens.