Scheduling of Processes in a Speech Understanding System Based on Approximate Reasoning

1. INTRODUCTION

Searchine for control strategies and methods for scheduling interpretation processes is among the most difficult tasks involved in designing Speech, Languag~ and Image Understanding Sys­ tems. Remarkable efforts have been ma­ de in the area of Speeeh Understanding Systems (SUS), whose state of the art has been the object of a recent review by De lf.ori [1). Sophisticated control strategies and scheduling polices are required when the world to be interpre­ ted is very complex (for example for large protocols with big dictionaries in a sus). For such cases, a paradigm of the type "hypothesize-and-test" and knowledge representation by rules of the type "precondition ..... action" have been proposed (2]. The first attempts to design and evaluate control strate­ gies in such a conceptual framework and in an environment where the input informations are corrupted and redun­ dant appear in papers by Woods et al. [3], Lesser and Imyes-Roth (4] and in the Ph. D. Thesis by Paxton (5]. They mostly use numerical probabilities or heuristic scores to evaluate the hypo­ theses emitted by the system and to as­ sign priorities to the processes that have to be executed to verify new hy­ potheses or theories. Valuable as they are, all these approaches leave room for improvements.

On the other hand, control strategies of systems designed for understanding non corrupted input messages are mostly based on non-numerical rules. The con­ tent of this paper tries to establish a connection between the numeri~ and the non-numeric approach to the de­ sign of control strategies.

An attempt has been made for evaluating interpretations of the speech signal by a-posteriori probabilities, using the Bayes theorem (3]. But, in these evalua­ tions, a high degree of imprecision is involved, owing to the approximations made in extracting acoustic features and in evaluating a-priori probabilities . llloreover, an increase of the complexity of an interpretation corresponds very often to having more heuristic and sub­ jective simplification introduced in the computation of probabilities. Thus the a-posteriori probabilities obtained by the Bayes theorem are affected by a degree of imprecision. There is little hope that this imprecision can be remo­ ved by refinements involving a practi­ cally impossible experimental work. The most realistic position is that of accep­ ting imprecisions and representing a­ posteriori probabilities by linguistic variables. A mathematical framework in which linguistic probabilities can be treated is the theory of fuzzy lin­ guistie variables [6-9]. This theory not only allows one to deal with impre­ cise concepts, as the linguistic proba­ bilities are, but also to combine proba­ bilistic concepts with concepts of other types, using inference rules for dave­ lopping an approximate reasoning. Fur­ thermore, a-posteriori probabilities are not the only parameters on which scheduling of further interpretation actions have to be based. In fact, a control system should be designed on the basis of inference rules which ta­ ke into account also considerations of action importance and suitability, that are not probabilistic in nature.

2. ASSIGNMENT OF LINGUISTIC PROBABILITIES

Let ..S'l. be a portion of the input data to be interpreted. System knowledge is sha­ red a~ong levels and each level may have a knowledge source associated with it. The lowest phonetic features of the sys ­ tem are "Vocalic", "Non vocalic" and "Sonorant", "Non-sonorant".The latter two features are applicable, in the system, only to consonants. The assignment of linKuistic probabilities to interpreta­ tions of Jl be,Q;ins wi lh the context-inde­ pendent phonetic features, given the evi­ dence of the acoustic features. For ex­ ample, the assignment of the phonetic features "sonorant" and "non-sonorant" to ~is controlled by two fuzzy grammars Gl and GN, described in details in [11]. Parsing the input string under the con­ trol of Gs and �~ leads to the evalua­ tion of the compatibility values)Ws<~) and }t~ (A) between A and the start sym­ bols of G.$ and � ~ respectively. Ra ther than on the exact values ofjA$(Jl.) and ~~(Jl), schedulinK of.subse~uent pro­ cesses depends on cons1dcrat1ons that may be expressed by !"uzzy propositions like the fo1lowins!;: "}As<SL) and Jit~<fL) are approximately equal'' or "JAs<I't) is much larger than ~,. (.A)"' etc .. n~~s~ . fuzzy propositions lead lo the def1n1t1on of fuzzy sets on the int e rval (-1,+1] of the variable:

Let A E Q, be one of such fuzzy sets. Let J be the cardinality of 8, ; the evidence of the features "sonorant" and "non-sana­ rant" in A will be represented by the fuzzy linguistic variable A such that:

Let HS and HH be the hypotheses: ltis a sonorant consonant andJlis a non-sono­ rant consonant respectively. By the Bayes theorem one gets:

The evaluation of Pr(llt,l A) is rather com­ plex because A is a fuzzy event instead of a precisely defined event. Given the probability density p(xiH~) and the defi­ nition of A on the interval [-1,+1] of the variable x and applying the extension principle and the definition of fuzzy in­ tegrals [10] it is possible to compute a possibility value .)o'Pr(l"'iiA) (z) for eve-

ry value zfW,ljof the probability Pr(I-\,IA). This possibilitylprobability distribution can be compared with lin.v;uistic probabili­ ties, defined as fuzzy sets o~ the inter­ val [o,l]. Such definitions can be found in (l o]. Let P~) be the fuzzy set ob­ tained with the (3) and Al n linguistic probability value: the value,\~ (jct(l,J]) that best approximates P(H.~) is retained instead of an exact value of the left si­ de probability in (3). The problem of lin­ guistic approximation is treated in details by Bellman and Zadeh (13].

The computations mentioned so far are per­ formed once forever and the results are represented by tables giving the best lin­ guistic approximation for a probabilityf possibility distribution, given the evi­ dence of the features in lt represented by fuzzy sets Ait& ~.

3. PRIORITY ASSIGNMENT

A Speech Understanding System is organized by levels; let(£., , f~) be the set of such levels. The knowledge of the system strategy may be represented in procedura l form by rules of the type:

~recondition .. action) . For example, in the project referred to in this paper, the lexical knowledge is represented by fr ames, whose composition is described in another paper (14]. Each frame w~ con­ tains a set of preconditions P~ and a set of actions A~. A precondition P;tt.6 P 1 · , that allows the action A&"'C!l Ai to be requested, is expressed in terms of items correspon­ ding to hypotheses already verified.Com­ bining the probability values of these items, it is possible to evaluate the lin­ guistic probability value of the precon­ dition P~w, ; let 1\\w. be such value. The a s­ signment corresponds to the following pro­ position:

Priority assignment is performed by the understanding controller on the basis of two types of evaluation. The first refers to the possibility of the succes of an ac­ tion, given the probability of the precon­ ditions. The second refers to the suitabi· lity of the action with respect to a know­ lcd~c like computational complexity and goal satisfaction. The latter evaluation is based on a proposition of the follow­ ing type:

P'" i s A , " ( 4 l

IF Prw. is lik_ely THEN A["is suitable (5) whereMsuitabl~ is a fuzzy linguistic va­ riable belonging to a dictionary £ . Tne (5) is an example of the rules of in­ ference of the understanding controller. Such rules may be learned by experiments or they may be initially settled by the designer. During the understanding pro­ cess, the controller will assign a lin­ s;~;uistic value to the process executing the action Al~ according to the result of the following approximate reasoning:

Execution of At~ is Gi-suitable (conclusion) When more actio~ compete for execution with different degrees of local suitability, the priority have to be assigned to them on the basis of a few general inference rules of the control strategy. Such rules establish general degrees of importance of possible actions, given premises that are assumed to be true or false.

4. AN EXAMPLE OF APPLICATION

We def'ined the f'our fuzzy sets: As ~ " f's(.tl) and ft,.(A) app roximative l y equal"; Al~ "/A~(Jl) s li ghtly higher than ji,(A)"; A,.~ ·~N(A) much higher than )As(ft.)"; ~=· )Ai(.A) much higher than )lll(.n,)". By the method described in (10] we computed the possibilitylprobability distrubution of the a -posteriori proba­ bilities Pr(HiiAJl((i =S ,N), .i6[1,4j),whi we approximated by standard linguistic

variables.

Table I and II show the results obtained By using suitability values as priority values f'or the competing processes "so­ norant" "non-sonorant" the right action is scheduled with higher priority in 84.6% of the c ases and in the 14% of the cases the two acti ons have been schedu­ led with e~ual priority. Using a Bayes decision we obtained , in t~e most favora ble case a n error r ate of 0.8% with 22%

un d "d d AC":~ e ca cs.