UNREALIZABLE LEARNING IN FEEDFORWARD NEURAL NETWORKS

Statistical mechanics is used to study unrealizable generalization in two large feed-forward neural networks with binary weights and output, a perceptron and a tree committee machine. The student is trained by a teacher being larger, i.e. having more units than the student. It is shown that this is the same as using training data corrupted by Gaussian noise. Each machine is considered in the high temperature limit and in the replica symmetric approximation as well as for one step of replica symmetry breaking. For the perceptron a phase transition is found for low noise. However the transition is not to optimal learning. If the noise is increased the transition disappears. In both cases $\epsilon _{g}$ will approach optimal performance with a $(\ln\alpha /\alpha)^k$ decay for large $\alpha$. For the tree committee machine noise in the input layer is studied, as well as noise in the hidden layer. If there is no noise in the input layer there is, in the case of one step of repl! ica symmetry breaking, a phase tra nsition to optimal learning at some finite $\alpha$ for all levels of noise in the hidden layer. When noise is added to the input layer the generalization behavior is similar to that of the perceptron. For one step of replica symmetry breaking, in the realizable limit, the values of the spinodal points found in this paper disagree with previously reported estimates \cite{seung1},\cite{schwarze1}. Here the value $\alpha _{sp} = 2.79$ is found for the tree committee machine and $\alpha _{sp} = 1.67$ for the perceptron.

Introduction
A Feed-forward neural network can be used to estimate an unknown rule from random examples [3] by adaption of its weights. Using methods from statistical mechanics of disordered systems [4] the performance of a student network trained on examples obtained from a teacher network of the same architecture has been studied (for a review see [5]). In this case the rule is said to be realizable since it is possible for the student to develop the same weights as the teacher.
One way to construct an unrealizable rule is to allow for a teacher that is larger (more units) than the student. This will be shown to be equivalent to adding Gaussian noise to the training set. The noisy data scenario has been investigated for networks with continuous weights [6], [7], [8]. In the limit where the teacher is infinitely larger than the student (large noise limit) the only thing the student can do is to learn each example by heart, and in this limit the problem reduces to that of storage capacity.
In this paper the generalization behavior of two different types of binary neural networks with binary weights is studied, a perceptron (section 2) and a tree committee machine (section 3), in the limit where the number of units is large. The rule is defined by a teacher of the same type but having more units than the student, making the task unrealizable.
The training of the student, having N units, is based on αN examples obtained by picking inputs ξ µ and assigning outputs τ µ as given by the teacher. With σ µ being the µth output of the student, a training energy E = µ θ(−σ µ τ µ ) is defined, which leads to a probability density with Boltzmann weight e −βE , where β = 1/T is the inverse temperature. First the high temperature limit is considered for each type of network, the perceptron in section (2.1) and the tree committee machine in section (3.1). Then, in sections (2.2) and (3.2), the replica trick is used, assuming replica symmetry (RS), to study the average over all training sets of the free energy, βf . In sections (2.3) and (3.3) the corrections given by one step of replica symmetry breaking (RSB) are discussed. Since, in the noiseless limit, the value of the spinodal point found in the RSB-case disagrees with previously reported estimates [1], [2], some time is spent on the saddle point equations in appendix A. Finally, in appendix B, the procedure for finding the asymptotic generalization behavior for large α is given.

A Large Binary Perceptron with Ising weights.
Let the student and the teacher have N and M input units respectively with N ≤ M.
Presented an input, s, the teacher evaluates, τ ( s) = sgn( v · s), while the student computes, σ( s 0 ) = sgn( w 0 · s 0 ), given the input s 0 . Here s and v are elements of R M , while vectors having a zero subscript are elements of R N . When the student is presented the same input vector, ξ, as the teacher, it only considers the N first components, ξ 0 . Thus the target rule will be, where v 0 is constructed from the first N components of v. Effectively this means that the student will be given the task τ ′ ( ξ 0 ) = sgn( v 0 · ξ 0 ) with noise on the input vector ζ 0 = ξ 0 + κ 0 and/or on the weight vector J 0 = v 0 + ω 0 . Since η is constructed from independent Gaussian random variables, v j and ξ j (j = N + 1, ..., M) with unit variance, η will also be Gaussian with variance, where γ = N/M . γ has the simple interpretation of the relative size of the student to the teacher. If γ = 1 the student and the teacher are of the same size, i.e. there is no noise. If γ = 0 the teacher is infinitely larger than the student, i.e. the data will be completely noisy.
The generalization error, ǫ g , obtained by taking the average of θ(−στ ) over normal distributed inputs, s j (j = 1, ..., M), is where R is the overlap between w 0 and v 0 . For R = 1 we obtain the optimal value, ǫ opt , of ǫ g .
First the high temperature limit is considered. Then by using the replica method, the RS approximation is studied, and finally the corrections given by one-step RSB are discussed.

High Temperature Limit
In previous work [1] the high temperature limit has proven to be interesting since it is both computationally easy and gives the general behavior of learning. It is defined so that both α and T approach infinity while αβ remains constant. The free energy is simply The qualitative behavior of the learning curves can be divided into two types depending on whether the noise level is above or below a particular value γ 0 . For γ 0 < γ < 1 there is, as in the realizable case, a range (αβ) sp1 < αβ < (αβ) sp2 , for which βf has two minima. In between (αβ) sp1 and (αβ) sp2 there is a transition point (αβ) tr at which the global properties of the minima change. In contrast to the noiseless case, (αβ) sp1 > 0 and thus for 0 ≤ αβ ≤ (αβ) sp1 there is only one minimum. The minimum persisting also for αβ ≥ (αβ) sp2 is close to R = 1 and approaches optimal performance as αβ increase. Note that in contrast to the realizable case there is no solution at R = 1. Typically (αβ) tr , (αβ) sp1 and (αβ) sp2 increase with decreasing γ and merge at γ = γ 0 . This is illustrated in figure (??).
The two minima of βf must be separated by a maximum, implying that ∂ 2 βf ∂R 2 = 0 at the spinodal points. Using the saddle point equation, to eliminate αβ from ∂ 2 βf ∂R 2 = 0, gives For γ = 1, (2.1.3) has one solution, R sp = 0.83 resulting in (αβ) sp = 2.08 in agreement with [1]. In the region γ 0 < γ < 1 (2.1.3) has two solutions giving (αβ) sp1 and (αβ) sp2 . At γ = γ 0 the two solutions merge and the two curves R and g(R, γ) are tangent to each other. Thus γ 0 can be found by solving, giving γ 0 = 0.965. For γ < γ 0 , βf has only one minimum (for all αβ) which moves towards R = 1 as αβ approaches infinity. Note that fairly small amounts of noise will change the qualitative behavior from phase transition to no transition.
In weight space this behavior can be understood as follows. In the noiseless case there are, for small α, two regions in weight space corresponding to the minima of βf , one with poor generalization and one with good. If α is small enough the "poor" region has the lowest free energy. As α increase the "poor" region moves towards the "good" and for α > α tr the "good" region has the lowest free energy. Since for α = α tr the "poor" and "good" regions are separated, there will be a phase transition.
If noise is added, the sizes of these regions will increase. For low α there is only one region in weight space corresponding to a minimum of βf . It will have poor generalization.
At α = α sp1 another region corresponding to a free energy minimum appears. This region gives better generalization. Again as α increase the "poor" region moves towards the "good" and for α > α tr the "good" region has the lowest free energy. Since for α = α tr the "poor" and "good" regions are separated there will be a phase transition. If the noise is increased the "poor" region is so large that when the "good" region is created it will overlap with the "poor". Thus there is only one region, moving towards better generalization and there is no phase transition.

Replica Symmetric Theory
Using the same methods as in [1] the RS approximation to the free energy is obtained, The saddle point equations generated by the extremal condition in (2.2.1) is given in appendix A. Here q is the typical overlap between two different w 0 . R, γ and α have the interpretation given above. Using the saddle point equations we can, given γ and β, eliminate the auxiliary variablesR andq, and find the dependence of R (and ǫ g ) on α.
First consider the zero temperature case. This corresponds to only allowing students that answers all questions correctly. If γ < 1 the training data is noisy and there is a maximum size of the training set α c N beyond which no student can perform optimally. α c (γ) and R c (γ) are plotted in figure (??). For γ = 0 the known result of Gardner [9] is reproduced.
Note that the curves do not give α c → ∞ as γ → 1. However this may not be expected since the curves only give correct predictions for states that are stationary points of βf RS and in the realizable case the state R = 1 is not stationary as was shown in [1]. For γ = 1 both the transition and the spinodal points agrees with the values found in [1]. A learning curve for At T > 0 the learning behavior is the same as for the high temperature limit but with a different γ 0 , depending on T , and with ǫ g and q having the asymptotic form, for large α. For details on how to compute the asymptotic form see appendix B. For some range of γ, γ A < γ < 1, there is a phase transition already at zero temperature while in a range γ B < γ < γ A there is no transition at low temperature. As the temperature is increased a transition develops which is illustrated in figure (??) for γ = 0.99. Finally when γ < γ B there seems to be no phase transition no matter how high the temperature.

Replica Symmetry Breaking
In the RS approximation the entropy will always turn negative at some finite α and therefore a region in αT -space for which the system exhibits replica symmetry breaking (RSB) is expected, see figure (??). Analogous to [1] one step of RSB gives, where the extremum is taken over R,R, q 0 ,q 0 , q 1 ,q 1 , and m. As in [1] the limit q 1 → 1, q 1 → ∞ is considered, implying that the stationary points of f RSB are given by the stationary points of f RS having zero entropy (see appendix A for details).
The learning behavior is analogous to the high temperature limit but with γ 0 = 0.995.
In appendix B the asymptotic form of ǫ g and q is computed, When 0.999 ≤ γ < 1, α tr occurs in between α sp1 and α sp2 while for 0.996 ≤ γ ≤ 0.998, α tr = α sp1 , i.e. the state with better generalization is stable as soon as it appears.
For the case γ = 0.05 the critical capacity, α c = 0.83 (q c = 0.56) is found which is compatible with the known results for γ = 0 [10]. Some values are given in table (??) and some typical learning curves are given in figure (??).
In the noiseless limit the result, α sp = 1.67, correcting a previous result by Seung et. al.
[1] (α sp = 1.63). The reason for this is given in appendix A.
It is also interesting to compare with some recently reported upper bounds for the Ising perceptron [11]. In this article the asymptotical behavior was found to be the same as (2.3.5). The authors found that the phase transition disappeared below γ = 0.998 thus not only predicting the correct qualitative behavior but also giving a tight quantitative bound on γ 0 . Also, at γ = 0.998, they found α tr = 2.6136 whereas α tr = 1.83 is obtained at γ 0 given above and using the replica method.

A Binary Committee Machine with Ising weights.
as the kth perceptron in the student is given the input s Analogous to the simple perceptron we find that this is equivalent to learning a noisy target rule, where η and η k are independent Gaussian random variables with variance, Using these parameters the generalization error is found, where the effective order parameter is given by R e = 2 π γ arcsin(δR) and R is the typical overlap between w k . Here, analogous to Schwarze and Hertz [2], it is assumed that R is independent of the hidden unit index k.
As for the perceptron case the high temperature limit is considered first. Then by using the replica method, the RS approximation is studied and finally the corrections given by one step of RSB are discussed.

High Temperature Limit.
Taking the limits T → ∞ and α → ∞ while keeping αβ fixed the free energy is found, If the noise level is low enough, there exists two spinodal points, α sp1 and α sp2 , with a phase transition in between. In contrast to the perceptron one find that if there is no input noise (δ = 1) there is a phase transition to optimal performance at a finite α for all values of γ.
Given a γ and that δ 0 (γ) < δ a transition to a state approaching optimal learning in the large α limit is found. For δ < δ 0 (γ) the transition vanishes and ǫ g approaches ǫ opt as α tends to infinity. Especially if δ > δ A = δ 0 (0) there is always a phase transition while for δ < δ B = δ 0 (1) there is no phase transition independent of the hidden noise. By the same procedure as in section (2.1) one find δ A = 0.965, δ B = 0.924 and δ 0 (γ) as shown in figure   (??). Also here α sp1 , α tr and α sp2 increase with increasing noise.

Replica Symmetric Theory.
Analogous to Schwarze and Hertz [2] the RS estimate to the free energy is found, where R e is given above and q e = 2 π arcsin q. The value of q is the typical correlation between two w (0) k which are assumed to be independent of the perceptron index k. The interpretations of R, γ, δ and α are as given above. By using the equations generated by the extremal condition in (3.2.1) to eliminateR andq we can find the dependence of R (and ǫ g ) on α given γ, δ and β.
For T = 0 one should, as for the perceptron, find a critical capacity, α c , beyond which the student can not perform optimally on the training set. However, this is not the case implying that the RS-approximation is bad. In the realizable case the values of both the transition and the spinodal point agree with [2] At T > 0 the behavior is much the same as in the high temperature limit with the exception that for δ = 1 the transition is not to an optimal state but to a state approaching optimal learning as α tends to infinity. The asymptotical form of ǫ g and q for large α can be found for δ = 1, γ < 1, and for δ < 1, γ ≤ 1, The asymptotic behavior can be found by the same method used in appendix B. As for the perceptron there is a range of noise levels for which there is no phase transition at low temperature but one is developed as the temperature is increased. One such example (γ = 1, δ = 0.99) is used in the phase diagram (??). If the noise is increased above some value there seems to be no phase transition no matter how high the temperature.

Replica Symmetric Breaking.
As was said in the previous section the RS-approximation fails in predicting a critical capacity. Also, the entropy will turn negative at some finite α and thus RSB is expected. In figure (??) a phase diagram for γ = 1, δ = 0.99 shows the RSB region. For one step of RSB, in the limit q 1 → 1,q 1 → ∞, the free energy is,

3.4)
For reasons analogous to those given in [1] for the perceptron the stationary points of f RSB are given by the stationary points of f RS having zero entropy.
In contrast to the RS-case, but analogous to the high temperature limit, a transition to optimal learning is found for all γ if δ = 1. Using the same notation as in section (3.1) the values of δ A and δ B are 0.9995 and 0.9847 respectively, and δ 0 (γ) is given in figure (??).
As α → ∞ the asymptotic forms of ǫ g and q are, Appendix B gives details of how to compute the asymptotic behavior, using the perceptron as an example. In the realizable limit (δ = γ = 1) the result α sp = 2.79, correcting the value found in [2] (α sp = 2.58). The reason for the correction is given in appendix A, where the perceptron is used as an example.

Summary.
In summary we have studied unrealizable learning in two large feed-forward neural network, a perceptron and a tree committee machine within the replica symmetric ansatz as well as for one step of replica symmetry breaking. The average generalization error has been calculated as a function of the load parameter α.
For the perceptron it was shown that using a noisy training set results in a generalization error approaching optimal learning with increasing α according to a power law of (ln α/α) k with k = 2 in the RSB-case. If the noise is low enough there is a phase transition at some finite α to a state which is close to R = 1. Increasing the noise makes the transition go away.
For the tree committee machine a similar generalization behavior was found, the main difference being that there is always a transition to optimal learning at some finite α if there is no noise in the input layer. Typically, noise in the input layer gives worse generalization behavior than noise in the hidden layer. For one step of RSB and with noise in the input layer as well as in the hidden layer the asymptotic form of ǫ g was found to be (ln α/α) k with k = 2/3.
In the realizable cases the values of α sp correct previously reported results [1], [2], for the RSB spinodal point in the two machines. Here α sp = 1.67 was found for the perceptron and α sp = 2.79 for the tree committee machine.
I thank J. Hertz for his valuable advice and direction and R. Urbanczik for many useful discussions. Also, I would like to thank H. Schwarze for sharing the code written in connection to ref. [2] which made it possible to sort out the disagreement on the spinodal points.

A. The Saddle Point Equations
In the limit q 1 → 1,q 1 → ∞ the one step RSB free energy (2.3.1), of the perceptron, is  At this point we could try to solve forq andR given α. However since ǫ g is a many-valued function of α it is more economical to eliminate α. This will give the equation, which can be solved forq givenR. α can be evaluated using (A.6) or (A.7). The advantage is that ǫ g is a single valued function ofR. In the RSB-case this will be helpful since more than one solution for each α has to be considered as we show below.
Once a stationary point has been found its second order properties has to be checked by computing the determinant of the Hessian matrix, H. Assume that the correct sign of det H, atR > 0, is given by the sign atR = 0. AsR is increased, the sign of det H will change first atR sp2 and then again atR sp1 . Note thatR sp2 <R sp1 whereas α sp1 < α sp2 . In the regimeR sp2 <R <R sp1 , βf has a stationary point but it has the incorrect curvature.
Even though the RSB-case is solved by using the RS-equations the determinant of the Hessian matrix of βf RSB , det H RSB , has to be used to determine the second order properties.
det H RSB consists of the second derivatives of βf RSB with respect to R, q,R,q and m whereas det H RS is computed from the second derivatives of βf RS with respect to R, q,R andq. Using det H RS = 0 as the criterion to determine the spinodal point (at γ = 1) would result in the values of α sp as given in [1] and [2]. Moreover, insisting on this RS-criterion will, for some γ, result in regions of α where no solution exist. Thus this procedure fails in a disastrous way.
However the correct condition, det H RSB = 0, will cure this problem and give α sp as given in this paper.
In the RSB-case det H RS will have the wrong sign close to α sp . This will correspond to points on ǫ g not considered in the RS-case since there exists another solution (with s > 0) at the same α but with det H RS having the correct sign. This is illustrated (for γ = 1) in and since 0 < m < 1, det H RSB has the same sign as F .

B. Asymptotics
For large α the saddle point equations (A.2) implies that q, R are close to 1 andq,R are large. From this the asymptotic form of the free energy (2.2.1) for non-zero temperatures can be found, βf RS = extr R,R,q,q G r (R, q, α, γ, β) + G s (R,R, q,q) , (B.1) The first two of these can be combined into, The asymptotic form of R, q and ǫ g is now found from (B.15) and (B.16) giving, For the tree committee machine the asymptotic forms of R, q and ǫ g can be found by the same procedure but using the asymptotic form of the free energy (3.2.1).


The Use of Knowledge Preconditions in Language Processing

If an agent does not possess the knowledge needed to perform an action, it may privately plan to obtain the required information on its own, or it may involve another agent in the planning process by engaging it in a dialogue. In this paper, we show how the requirements of knowledge preconditions can be used to account for information-seeking subdialogues in discourse. We first present an axiomatization of knowledge preconditions for the SharedPlan model of collaborative activity (Grosz&Kraus, 1993), and then provide an analysis of information-seeking subdialogues within a general framework for discourse processing. In this framework, SharedPlans and relationships among them are used to model the intentional component of Grosz and Sidner's (1986) theory of discourse structure.

Introduction
For an agent 1 to be able to perform an action, it must satisfy both the physical and knowledge preconditions of that action [Moore, 1985;Morgenstern, 1987]. For example, for an agent to pick up a particular tower of blocks, it must (1) know how to pick up towers in general, (2) be able to identify the tower in question, and (3) have satisfied the (physical) preconditions or constraints associated with picking up towers (e.g., it must have a free hand). These conditions must hold whether the agent is planning an action on its own or is involved in a collaborative planning effort with other agents.
In this paper, we provide an axiomatization of knowledge preconditions for the SharedPlan model of collab- * This work was done as part of my dissertation research at Harvard University, and was supported by a Bellcore graduate fellowship and by U S WEST Advanced Technologies. I would like to thank Barbara Grosz, Stuart Shieber, and Candy Sidner for their helpful comments, discussions, and insights on this work.
1 Unless otherwise indicated, we will use the term "agent" to refer to both individual agents and sets of agents. orative activity Lochbaum et al., 1990;Grosz and Kraus, 1993]. This model draws upon past work [Moore, 1985;Morgenstern, 1987], but adapts it to the collaborative situation. We briefly describe the SharedPlan framework in Section 2, and then, in Section 3, present our axiomatization of knowledge preconditions. In Section 4, we demonstrate the use of knowledge preconditions in accounting for informationseeking subdialogues, such as those in Figure 1. We then compare our approach to the alternative accounts [Litman and Allen, 1987;Lambert and Carberry, 1991;Ramshaw, 1991].
(1) E: First you have to remove the flywheel.
(2) A: How do I remove the flywheel?
(3) E: First, loosen the two allen head setscrews holding it to the shaft, then pull it off.
(5) I can only find one screw. Where's the other one?
(6) E: On the hub of the flywheel.
Figure 1: Information-Seeking Subdialogues [Grosz, 1974] 2 SharedPlans The SharedPlan formalism is a mental-state model of collaborative plans with roots in Pollack's [1990] work on single-agent plans. For a group of agents GR to have a full SharedPlan (FSP) for an act α, they must satisfy the requirements given in Figure 2. When the agents have satisfied only a subset of these requirements, they are said to have a partial SharedPlan (PSP). 2 The bracketed terms in Figure 2 indicate the operators used by Grosz and Kraus [1993] to formalize each requirement. Requirement (1) in Figure 2 refers to the agents' recipe [Pollack, 1990]   Kraus's definitions as sets of constituent acts and constraints. To perform an act α, an agent must perform each constituent act in α's recipe according to the constraints of that recipe. Actions themselves may be further decomposed into act-types and parameters. We will represent an action α as a term of the formᾱ(p 1 , . . . , p n ) whereᾱ represents the act-type of the action and the p i its parameters. Grosz and Kraus [1993] use the operators BCBA (read "believes can bring about") and MBCBAG (read "mutually believe can bring about group") to formalize respectively requirements (2b) and (3a) in Figure 2. Although these operators are intended to specify the conditions under which an agent is able to perform an action, their definitions explicitly require only that an agent satisfy the physical preconditions or constraints associated with an action to be able to perform it. Because an agent is not truly capable of performing an act unless it possesses the appropriate knowledge, the definitions of BCBA and MBCBAG must be augmented with an axiomatization of knowledge preconditions. The following observations made by Morgenstern [1987], but recast in our terminology, must be represented in such an axiomatization:

Knowledge Preconditions
1. Agents need to know recipes for the acts they perform.
2. All agents have some primitive acts in their repertoire.
3. Agents must be able to identify the parameters of the acts they perform.
4. Agents may know only some descriptions of an act.
5. Agents know that the knowledge necessary for complex acts derives from that necessary for their component acts.
Our axiomatization of knowledge preconditions is based on Morgenstern's observations, but adapted to the requirements of individual and shared mental-state plans. 3 We use the predicates has.recipe and id.params to represent explicitly observations (1) and (3) above. The remaining observations are implicitly represented by the way in which these two knowledge precondition relations are defined. Observation (2) is modeled as the base case of has.recipe, and observation (5) is modeled by the use of has.recipe within the recursive plan definitions.
Observation (4) requires that the knowledge precondition relations be intensional, rather than extensional; within their scope it should not be possible to freely substitute one representation of an action for another. We thus define has.recipe and id.params to hold of action descriptions, rather than actions. Action descriptions are intensional objects; one action description can be substituted for another only if the descriptions are the same. For example, although 555-1234 and phonenumber(speech-lab) may be extensionally equivalent, the descriptions 555-1234 and phone-number(speechlab) are not. By convention, we will omit the corner quote notation in what follows and simply take the appropriate arguments of the predicates to represent action descriptions rather than actions.
Although Morgenstern's observations are most naturally expressed informally in terms of knowledge, we formalize them using belief to allow for the possibility of an agent's being incorrect. Although it is true that an agent cannot successfully act unless its beliefs about recipes and parameters are correct, having to know the recipes and parameters is too strong a requirement for collaborating agents [Lochbaum, 1994].

Determining Recipes: has.recipe
For an agent to be able to perform an act α, it must know how to perform α; i.e., it must have a recipe for the act. The relation has.recipe(G, α, R, T ) is used to represent that agent G has a recipe R for an act α at time T . It is formalized as follows: Clause (1) of the definition models Morgenstern's second observation, namely that agents do not need a recipe to perform a basic-level action, i.e., one executable at will [Pollack, 1990]. 4 For non-basic-level actions (Clause (2)), the agent of α (either a single agent (2a1) or a group of agents (2a2)) must believe that some set of acts, β i , and constraints, ρ j , constitute a recipe for α.

Identifying Parameters: id.params
An agent must also be able to identify the parameters of an act α to be able to perform it. For example, if an agent is told "remove the flywheel," as in the dialogue of Figure 1, the agent must be able to identify the flywheel in question. The relation id.params(G, α, T ) is used to represent that agent G can identify the parameters of act α at time T . If α is of the formᾱ(p 1 , ..., p n ), then id.params(G, α, T ) is true if G can identify each of the p i . To do so, G must have a description of each p i that is suitable forᾱ. The relation id.params is defined as follows: The ability to identify an object is highly context dependent. For example, as Appelt points out [1985, pg. 200], "the description that one must know to carry out a plan requiring the identification of 'John's residence' may be quite different depending on whether one is going to visit him, or mail him a letter." The function F in the above definition is an oracle function intended to model the context-dependent nature of parameter identification. This function returns a suitable identification constraint [Appelt and Kronfeld, 1987] for a parameter p i in the context of an act-typeᾱ. For example, in the case of sending a letter to John's residence, the constraint produced by the oracle function would be that John's residence be described by a postal address.
The relation has.sat.descr(G, P, C, T ) holds of an agent G, a parameter description P , an identification constraint C, and a time T , if G has a suitable description, as determined by C, of the object described as P at time T . To formalize this relation, we utilize Kronfeld's [1986] notion of an individuating set. An agent's individuating set for an object is a maximal set of terms such that each term is believed by the agent to denote that object. For example, an agent's individuating set for John's residence might include its postal address as well as an identifying physical description such as "the only yellow house on Cherry Street." To model individuating sets, we introduce a function IS(G, P, T ); the function returns an agent G's individuating set at time T for the object that G believes can be described as P . This function is based on similar elements of the formal language that Appelt and Kronfeld [1987] introduce as part of their theory of referring. The function returns a set that contains P as well as the other descriptions that G has for the object that it believes P denotes.
For an agent to suitably identify a parameter described as P , the agent must have a description, P ′ , of the parameter such that P ′ is of the appropriate sort. For example, for an agent to visit John's residence, it is not sufficient for the agent to believe that the description "John's residence" refers to the place where John lives. Rather, the agent needs another description of John's residence, one such as "the only yellow house on Cherry Street," that is appropriate for the purpose of visiting him. To model an agent's ability to identify a parameter (described as P ) for some purpose, we thus require that the agent have an individuating set for the parameter that contains a description P ′ such that P ′ satisfies the identification constraint that derives from the purpose. The definition of has.sat.descr is thus as follows: 5 The predicate suff.for .id (C, P ′ ) is true if the constraint C applies to the parameter description P ′ . The oracle function F (ᾱ, p i ) in id.params produces the appropriate identification constraint on p i givenᾱ.

The Role of Knowledge Preconditions in Language Processing
We now show how the requirements of knowledge preconditions can be used in discourse processing. Our model of discourse processing is based on the theory of discourse structure proposed by Grosz and Sidner [1986]. According to their theory, discourse structure consists of three interrelated components: a linguistic structure, an attentional state, and an intentional structure. The linguistic structure consists of discourse segments 6 and an embedding relationship among them; the bold rule in Figure 1 indicates the linguistic structure of that discourse. Attentional state is an abstraction of the discourse participants' focus of attention; it serves as a record of those entities that are salient at any point in the discourse. Intentional structure is comprised of discourse segment purposes and their interrelationships, particularly that of dominance. A discourse segment purpose, or DSP, is a Gricean-like [1969] intention that leads to the initiation of a discourse segment. One DSP is dominated by another if the satisfaction of the first provides part of the satisfaction of the second. Intentional structure plays a central role in discourse processing; an agent's comprehension of the utterances in a discourse relies on the recognition of this structure [Grosz and Sidner, 1986].  proposed SharedPlans to provide a basis for recognizing intentional structure. They argued that discourses are fundamentally collaborative, and hence that a model of shared plans provides a more appropriate basis for discourse processing than a model of single-agent plans. However, the connection between SharedPlans and intentional structure was never specified.

SharedPlans as Intentional Structure
We have developed a model of discourse processing that provides that connection [Lochbaum, 1994]. Figure 3 illustrates the role of SharedPlans in modeling intentional structure. Each segment of a discourse has an associated SharedPlan. The purpose of the segment is taken to be intention that (Int.Th [Grosz and Kraus, 1993]) the discourse participants form that plan. This intention is held by the agent who initiates the segment. In what follows, we will refer to that participant as the initiating conversational participant or ICP; the other participant is the OCP [Grosz and Sidner, 1986]. Dominance relationships between DSPs are modeled using subsidiary relationships between SharedPlans. One plan is subsidiary to another if the completion of the first plan contributes to the completion of the second. Subsidiary relationships are discussed in more detail in Section 4.2 The utterances of a discourse are understood in terms of their contribution to the SharedPlans associated with the segments of the discourse. Those segments that have been completed at the time of processing an utterance have a full SharedPlan (FSP) associated with them (e.g., segment (2) in Figure 3), while those that have not have a partial SharedPlan (PSP) (e.g., segments (1) and (3) in Figure 3). For each utterance of a discourse, an agent must determine whether the utterance begins a new segment of the discourse, contributes to the current segment, or completes it [Grosz and Sidner, 1986]. For an utterance to begin a new segment, it must indicate the initiation of a subsidiary plan. This case is described in further detail below. For an utterance to contribute to the current segment, it must advance the partial SharedPlan associated with the segment towards completion. That is, it must establish one of the beliefs or intentions required for the discourse participants to have a full SharedPlan, but missing from their current partial SharedPlan. For an utterance to complete the current segment, it must indicate that the purpose of that segment has been satisfied. For that to be the case, the SharedPlan associated with the segment must be an FSP rather than a PSP. That is, all of the beliefs and intentions required of an FSP, as indicated in Figure 2, must have been established over the course of the segment.
A detailed description of the implemented algorithms used in modeling each of these cases can be found elsewhere [Lochbaum, 1994]. Here, we focus on the use of knowledge preconditions in accounting for the initiation of information-seeking subdialogues. We use the dialogue in Figure 1 as an example and assume the role of the Expert (participant "E") in analyzing the discourse. 7 The dialogue in Figure 1 was extracted from a larger discourse in which the Expert and Apprentice (participant "A") are collaborating on removing the pump of an air compressor. We thus take the purpose of the larger discourse to be DSP1=Int.T h(e,F SP ({a,e},remove(pump(ac1), {a}))) 8 where ac1 represents the air compressor the agents are working on.

Accounting for the Initiation of New Discourse Segments
To make sense of an utterance, an agent must provide an explanation for it in the form of an answer to the question, "Why did the speaker say that to me?" [Sidner and Israel, 1981]. An OCP must provide a similar explanation for an ICP's initiation of a new discourse segment. This explanation takes the form of an answer to the question "Why does the ICP want to engage in a segment with purpose DSP j at this point in our discourse?"; i.e., "How is DSP j related to what we were talking about before?" Subsidiary relationships between SharedPlans provide the basis for modeling the OCP's reasoning. One plan is subsidiary to another if the completion of the first plan contributes to the completion of the second. The most basic example of this relationship occurs within the FSP definition itself. As indicated in Figure 2, a full plan for an act α includes full plans for each subact in α's recipe as components (requirements (2c) and (3b)). The plans for the subacts thus contribute to the plan for α and are therefore subsidiary to it.
Subsidiary relationships may also arise in response to the other requirements of the FSP definition. For example, as discussed in Section 3, the BCBA operator used to model requirement (2b) specifies that to be able to perform an act α, an agent must (1) have a recipe for α (has.recipe), (2) be able to identify the parameters of α (has.sat.descr), and (3) have satisfied the constraints associated with performing α. The first of these requirements provides an explanation for the first subdialogue in Figure 1.
The purpose of this subdialogue is represented as 9 DSP2=Int.T h(a, F SP ({a, e}, Achieve(has.recipe(a, remove(f lywheel(ac1), {a}), R)))) and can be glossed as "the Apprentice intends that the agents collaborate on his obtaining a recipe for the act of removing the flywheel of the air compressor." To account for the Apprentice's initiation of this subdialogue, the Expert must determine the relationship of DSP 2 to the purpose of the agents' preceding discourse, namely DSP 1 . In this case, the Expert can reason that the Apprentice wants to engage in the subdialogue to obtain a recipe for the act of removing the flywheel so that he will be able to perform that act as part of the agents' SharedPlan to remove the pump. The plan in DSP 2 is thus subsidiary to that in DSP 1 by virtue of a knowledge precondition requirement of the latter plan. Figure 3 illustrates this analysis. Each box in the figure corresponds to a discourse segment and contains the SharedPlan used to model the segment's purpose. The SharedPlans are labeled so as to be co-indexed with the DSPs discussed above. The arrows indicate subsidiary relationships between SharedPlans, as explained by the text that adjoins them. When plan Pj is subsidiary to plan Pi, DSP j is dominated by DSP i .
The information represented within each SharedPlan in Figure 3 is separated into two parts. Those beliefs and intentions that have been established at the time of the analysis are shown above the dotted line, while those that remain to be established, but that are used in determining subsidiary relationships, are shown below the line. The index in square brackets to the right of each constituent indicates the FSP requirement from which the constituent arose.
As indicated in Figure 4, the initiation of the second subdialogue in Figure 1 is explained similarly. This time, however, it is the need to identify parameters of acts (requirement (2) above) that leads to the initiation of the subdialogue. In addition, the parameter in question is a parameter of an act in a subsidiary individual plan of the Apprentice's.

Discussion
In this paper, we have shown that information-seeking subdialogues may be explained on the basis of knowledge precondition requirements. Our account of such subdialogues fits within a general framework for discourse 9 We describe a method for recognizing DSPs of this form elsewhere [Lochbaum, 1994]. processing in which the purpose of a subdialogue is modeled using a SharedPlan and is related to the purposes of other subdialogues based on the requirements of the FSP definition. Elsewhere [Lochbaum, 1994], we show that correction and subtask subdialogues, among others, may also be accounted for in this manner.
In contrast, alternative plan-based accounts of dialogue understanding introduce multiple types of plans to account for the utterances in a discourse. For example, Litman and Allen [1987], propose the use of two types of plans to model clarification and correction subdialogues: discourse plans and domain plans. Domain plans represent knowledge about a task, while discourse plans represent conversational relationships between utterances and plans. Litman and Allen provide operators for the following discourse plans: Under our approach, the recognition of discourse plans is unnecessary. The fact that a speaker is using an utterance to, for example, introduce a plan, or track a plan, or identify a parameter, need not be explicitly recognized for the purposes of utterance interpretation. Furthermore, we would argue that such facts are not intended to be recognized (cf. Grice [1969]). Rather, they simply fall out of recognizing the relationship of an utterance to the current discourse structure, i.e., the currently active SharedPlans. For example, INTRODUCE-PLAN corresponds to initiating a new discourse segment, CONTINUE-or TRACK-PLAN to contributing to the current segment, and IDENTIFY-PARAMETER to initiating a new segment to satisfy a has.sat.descr knowledge precondition requirement. Although the initiation of a new SharedPlan corresponds to the initiation of a new discourse segment under our approach, it is the SharedPlan that must be recognized and not a discourse plan that refers to that SharedPlan. Lambert and Carberry [1991] have extended Litman and Allen's approach by introducing a third type of plan. Problem-solving plans, such as BUILD-PLAN and INSTANTIATE-VARS, are used to model the process by which agents construct domain plans. Under our approach, the need to explicitly recognize problemsolving plans is also avoided. The fact that an agent is PSP({a,e},Achieve(has.sat.descr(a, Screw,F(loosen,Screw)))) P4 Utterance (6) Figure 1 building a plan or instantiating a variable is a byproduct of understanding an utterance by relating it to the current discourse structure. BUILD-PLAN corresponds to initiating a new discourse segment to satisfy a has.recipe knowledge precondition requirement, while INSTANTIATE-VARS corresponds to initiating one to satisfy a has.sat.descr requirement. Unlike Lambert and Carberry's approach, however, and Litman and Allen's as well, our approach actually recognizes this structure. The other approaches are essentially utteranceto-utterance based and thus do not recognize discourse segments as separate units.
Ramshaw [1991] has added a different third type of plan, exploration plans, to Litman and Allen's two types. Exploration plans are intended to model the process by which agents explore courses of actions. Although we have not yet incorporated such reasoning into our model, we hypothesize that the exploration of plans can be modeled, without the introduction of a new plan type, by reasoning about an agent's potential intentions and the process by which they become full-fledged intentions [Grosz and Kraus, 1993;Bratman et al., 1988].
These alternative approaches share an important property that distinguishes them from our approach; they take a data-structure view of plans, rather than a mental phenomenon view [Pollack, 1990]. Whereas data-structure plans are essentially "recipes-for-action," mental phenomenon plans are a "structured collection of beliefs and intentions" [Pollack, 1990, pg. 77]. 10 Datastructure plans thus describe what an agent is doing with an utterance, but not why the agent is doing it. For example, although the constraints of Litman and Allen's IDENTIFY-PARAMETER discourse plan force the plan to be related to another plan that involves the parameter to be identified, IDENTIFY-PARAMETER does not explain why this information is desired; it does not capture that agents need to know parameters to be able to perform acts involving them. 11 It thus fails to model the essential knowledge precondition nature of identifying a parameter. Although it is possible to impose a mental phenomenon interpretation on top of a data-structure plan, doing so does not result in a mental phenomenon plan [Pollack, 1990]. Saying that G1 intends to IDEN-TIFY a PARAMETER fails to address why G1 intends to do so.
The need to explain an utterance is not unique to interpretation. Moore and Paris [1993] have shown that a similar need exists in generation. In particular, they have argued that RST-based text plans must be augmented with intentional structure. Otherwise, a system has no record of why it said what it did and is thus unable to respond effectively if a hearer does not understand or accept its utterances.

Conclusion
In this paper, we have presented an axiomatization of knowledge preconditions for the SharedPlan model of collaborative activity [Grosz and Kraus, 1993]. We have also shown how the requirements of knowledge preconditions can be used to account for information-seeking subdialogues in discourse. Our account of this phenomenon fits within a general framework for discourse processing in which SharedPlans and relationships among them are used to model the intentional component of Grosz and Sidner's [1986] theory of discourse structure. Unlike the alternative approaches, our approach recognizes and makes use of discourse structure. In addition, it does not require the introduction of new plan types.