On The Storage Economy Of Error-Tolerating Question-Answering Systems

1. Introduction

Loosely speaking a question-answering (QA) system is any mechanical system which accepts data of a specified type and at a later time produces output symbols in response to queries from some ad­ missible set. The output symbols are interpreted as answers to the queries about the specific data­ set and are expected to conform to some acceptable test of correctness. Practically all question­ answering systems in operation today are deductive in nature. When a query is presented concerning an assertion not derivable from the data, either the query is declared inadmissible, or the data is declared incomplete.

It is apparent that human information proces­ sing is not confined to deductive reasoning; quali­ fiers such as 'probably', 'perhaps', 'doubtfully', and many more are very common in everyday language. People quite often assert or deny propositions which are either themselves incomplete, concern in­ complete data, or are too complicated to be compu­ ted within the available time constraint. We usu­ ally interpret such behavior as an attempt to econ­ omize some computational resource (e.g., data spe­ cificity, storage space, search time) at the ex­ pense of answer accuracy. Correspondingly, it has been suggested that a substantial amount of compu­ tational resources could be gained if one allowed computerized QA systems to make occasional errors via approximate representations of data or world­ models. Zadeh [1] has proposed the use of fuzzy­ sets to cope with the "incompatibility principle." In Zadeh's words: "the essence of this principle is that as the complexity of a system increases, our ability to make precise and yet significant statements about its behavior diminishes until a threshold is ~ached beyond which precision and significance (or relevance) become almost mutually exelusive chQl'aeteristies." Rabin [2] conjectured

Judea Pearl

School of Engineering and Applied Science University of California, Los Angeles Los Angeles, California, U.S.A.

that the disparity between the super-exponential complexity of proofs in even the simplest algebras , and the apparent simplicity of everyday human plan­ ning behavior can perhaps be explained by man's willingness to tolerate a small amount of error.

These notion, while in harmony with one's in­ tuition and experience, have not yet been submitted to a careful quantitative analysis. This paper should be considered as a step toward such analy­ sis. It concerns the economY of storage space and establishes absolute bounds on the amount of stor­ age that can be saved by tolerating a specified percentage of errors in certain simple, yet typi­ cal, QA tasks. As a starting point, we ignore the question of computational-complexity or search­ time, thus allowing the QA system any required (but finite) amount of time for organizing and filing data into storage, as well as for computing the answers from the condensed data. A more recent work [3] demonstrates that the relative savings of most complexity measures in use are asymptotically bounded by the relative savings of storage space. Hence, the latter should be considered a fundamen­ tal characteristic of error-tolerating computation~

Four question-answering tasks are analyzed : data-retrieval, pattern-classifications, position­ matching and pair-ordering. The first and second tasks are concerned with the economical description of one-place predicates, while the third and fourth concern the description of an order relation .

Data-retrieval QA systems accept as data an arbitrary subset of individuals (from some uni­ verse), and respond to queries of the type "has this individual been observed before?" A typical example would be the task of determining whether a certain node in a game tree has been expanded be­ fore, or whether it has been recognized before as a "forced-win" position. A pattern-classificatioo system accepts data in the form of a subset of in­ dividuals classified into t mutually exclusive ca­ tegories (property-values). It responds to queries demanding the proper classification of a given in­ dividual from the observed list, permitting an ar­ bitr·ary classification of unobserved individuals .

Both position-matching and pair-orderin~ sys ­ tems accept data in the form of an ordered l1st of individuals. Position-matching systems admit quer­ ies of the type "What individual stands in the kth position?" or "Who is the irrmediate successor of individual x?" Pair-ordering systems respond to queries of the type "Does x precede y?". The num­ erical encoding of the order in position-matching tasks is known as a nominal scale (e.9., the num­ ber on the shirts of footbalT]pf.ayers) and that of pair-ordering tasks as ordinal scale (e.g., rank­ ing of players in order of abil~

In all these tasks it is possible to answer all queries correctly if an exact replica of the original data is kept in storage. In many cases, however, the memory required to hold such a replica would be prohibitively large. Consider, for exam­ ple, the task of deciding which member of a given pair of chess configurations has proven more prom­ ising in past games. Such tasks are never handled by complete enumeration but rather by employing approximate models which allow the computation of an order-preserving scale from some aspects of the configurations. The memory space needed for stor­ ing these imprecise models is expected to be smal­ ler than that required for storing the scale itself, and much smaller than that required to store the primary observational data from which the scale w~ deduced. Naturally, the amount of damage caused by impreciseness depends on the purpose served by the model, as reflected by the type of task-related queries that the model is expected to resolve. We therefore define the measure of the task-related damage (or distortion) as the fraction of queries in the admissible set which are answered incor­ rectly.

This paper demonstrates that the conversion of a small error allowance into a significant memory saving requires highly redundant query sets, and that such conversion is not feasible for the tasks of data-retrieval, pattern-classification and posi­ tion-matching unless, perhaps, the data is highly structured.

2. Background and Nomenclature

The model chosen for defining QA systems is represented by the block diagram of figure 1*. It consists of three parts: a storage procedure Bfil , a retrieval procedure Bfind' and a memory S. Dur-e ing the 'filing' phase, Bfile examines the elements of a data set and files a summary' in S for use by another procedure BfinQ" later, in the 'finding' phase, Bfind uses the 1nforma~ion in the memory to make dec1sions about the queries. Our aim is to calculate the minimum quantity of data that Bfile must store in S in order to guarantee a minimally acceptable performance standard.

The model is made precise using the following formulations: let M be a collection of data-sets, M = {~1'~ 2 .···~M}, and Q a set of admissible quer­ ies on~. Q = {q 1 ,q 2 · ··q 0 }. A QA system is a fin­ ite state machine QA with input alphabet~ U Q, output alphabet AU+= {a 1 ,···aK} U +· a finite state-set i = {a 1 ,a 2 ,···a 5 }, and a pair of characterizing functions: an output function (~ U Q) x i .... (AU +), and a next-state f 5 : (~ U Q) xi .... i satisfying

We are using here the terminology of Minsky and Papert, Reference 4, Chapter 12.

The output symbol + represents the system's output during the data-filing process. (2.la) and (2.lb) express the fact that during the data-filing pro­ cess we ignore the system output, while during the query process we wish the output to represent an answer to the query. (2 .2a) constrains the mirlline from changing its state in response to a query, while (2.2b) forces the machine to clear its state before the application of a new data. The storage capacity of the machine is defined to be the size of the state-space S.

It is now necessary to define a measure of ma­ chine performance. let a( 11,q)E~ represent the an­ swer selected by the machine in response to query qEQ, with 11EM being the most recently examined data. We define~ real-valued distortion function o: A x M x Q .... Re so that o[a.~.q] would measure the-degree of damage caused by answering 'a' to query 'q' about the data ·~·· We may assume with­ out loss of generality that every (~.q) pair pos­ sesses at least one aTf~ for which o[aT,~.q] = 0, representing a "correct" answer to a query. The overall system performance is judged by the mean distortion measure:

where P(~,q) is the joint probability that data ~ would be presented followed by query q.

When no a pr-iori knowledge is avail ab 1 e on the statistical properties of M and Q. it is reasonable to assume that all queries -and data are equiprob­ able and independent of each other, thus making P(~ ,q) = (MQ)-1, and:

let a(IJ) = a(IJ, q 1 ).···, a{IJ, q 0 ) stand for the answer-string obtained when an ordered sequence of queries q 1 .··· .q 0 is applied after data-s:t 11 was examined. The mean distortion can be wr1tten as:

where:

Throughout this paper we will consider only the symmetrical distortion function whereby all deviations from the set of true answers AT( 11 ,q) = {aT: oCaT' 11 · q) = 0} have equal weights.

For the purpose of calculating the minimum size of S it is convenient to regard a QA system as a communication channel which receives at its input the data-set ~ and reproduces at its output the answer-string a. Thus, the source alphabet is M, and the reproducing alphabet, ~. is theQcollec­ tion of all possible answer-strings, ~ = ~.

Let i designate an input data and j an output answer-string, and let dij be the (per letter) distortion measure between the two. Shannon's rate-distortion function for this source is de­ fined by [5]:

where I is the average mutual information between M and A, and P is the set of all conditional pro­ babilities yie~ding a mean distortion not exceed­ ing D:

Shannon's source-coding theorem states that it is not possible with any coding scheme to transmit the source information through any channel of cap­ acity less than R(D) with average distortion less than D. Conversely, the positive form of the the­ orem states that given any channel with capacity C > R(D), coding schemes exist which result in an average distortion arbitrarily close to D when used over this channel. If one regards Bfile [in figure 1] as the source encoder, Bfind as the de­ coder, and the memory S as a noise ess channel with capacity S, then Shannon's source-coding theorem implies that in order for a QA system to exhibit a mean distortion not exceeding D, it must be provi­ ded with a memory space at least as large as R(D). Conversely, the theorems guarantee that it is pos­ sible to realize a mean error arbitrarily close to D with an average memory space not exceeding R(D). The latter is true only if coding very long blocks of data is permitted, such as would be required for serving many users. If a code is to be as­ signed to each separate data-set as demanded by (2.2b), then R(D) only provides a lower bound on the memory space required.

To obtain the rate-distortion function for a QA system one needs to minimize expression (2.8) with P. = 1/M and d . . given by (2.6). Shannon has shown that R(D) is ~Jcontinuous, strictly decreas­ ing, convex U function for 0 2 D 2 Dmax' where Dmax is the minimum distortion achievable with zero memory:

and

The slope R'(D) is always infinitely negative at D = 0 but may be discontinuous at D = Dmax·

* A natural logarithm is used in the definition of R(D). Consequently memory sizes will be given in nats. A division by loge2 is required for conver­ S'TOri" into bits.

The calculation of the rate-distortion func­ tion for an arbitrary distortion matrix is, in general, a difficult task. For our purposes, how­ ever, it would be sufficient to derive bounds on R(D) using well known methods of rate-distortion theory [6J. The derivations of these are omitted in this paper and can be consulted in references [8], [9] and [10].

3. Predicate-Related QA Systems

Data-Retrieval Systems

Consider a collection C of m objects from which a subset C of n objec~s is selected and presented to a Q~ system during the filing phase. At a later time queries of the type "has object x(x€C ) been observed?" are presented to the sys­ tem ~r confirmation or rejection. An error is committed when either a member in c 0 is declared "unobserved" or an object in Cm-Cn 1s declared "observed".*

It is clear that if no error at all can be tolerated, then at least log 2 (~) bits of storage must be devoted to describe the observation set. When memory size is 1 Mmi .ted a2g (~) large (a typical example: m = 2 n = 2 ), one is tempted to "summarize" the data at the expense of accuracy. The most straightforward way to reduce storage would be to simply ignore a portion of the data, and produce arbitrary answers to queries referring to the missing objects. We shall call this scheme "data-erasure", and wi 11 use it to gauge the per­ formance of more sophisticated description schemes.

The Pattern-Recognition literature [7] may provide many ideas for such schemes. One may be tempted, for instance, to store only 'representa­ tive' samples of the observed set, and base the de­ cisions on the 'proximity' between the query object x and the stored 'representatives'. Another possi ­ bility is to approximate the binary representation of the observed sample by a Boolean expression of a limited length, store this expression, and use it in the decision phase. A more popular method is provided by the so-called "Statistical Pattern Re­ cognition". Here the data-set is merely used to calculate a set of parameters governing certain statistical models; the parameters are stored and subsequently used to generate the answer with the highest probability of correctness. An even more sophisticated description" method can be devised, based on the so-called "Linguistic Pattern Recogn~ tion" philosophy. The names of the observed ob­ jects are regarded as sentences in some language, a grammar generating this language is inferred and stored by Bfile' while Bfind parses the query sen­ tences and decides whether it is in the language. It will be shown that in the absence of any spec­ ial structures underlying the selection of the subsets C and for large m, all such schemes pos­ sess memo~y vs. error characteristics equal or in­ ferior to those obtained by data-erasure.

The data-set space, for this problem, consis~ of all subsets of Cm which contain exactly n objects, while the query set is isomorphic to em. Therefore:

*A discussion of the storage vs. se~rch-time tradeoff for such tasks is given by Minsky and Papert [4].

Every answer string constitutes a dichotomY of Cm' so ~ is simply the power set of em. The distor­ tion measure d . . is given by 1/m times the number of objects in ~ita-set i(M which are misclassified by answer-string j(~ . -

The rate-distortion function governing this system was found to be [9]:

where D stands for the fraction of mislabeled ob­ jects. R(D) is depicted in Figure 2 for several values of n, and m = 106

It demonstrates that as the ratio m/n increases, the rate-distortion function approaches the data­ erasure line 1 - D/Dmax at a logarithmic rate. Thus, no amount of error (below the trivial level of D = n/m obtainable by answering all queries in the affirmative) aan make memory demands grCAJJ s ZCAJJe r than n Zog m/n.

The implications of these results for the prospects of finding a general language that simp­ lifies descriptions of subsets are rather discour­ aging. They essentially imply that no fiZing saheme exists whiah performs app~aiabZy better than one whiah simpZy ignores a aertain fraation of the observed data. Only for sample sizes on the order of m/10 can the statistical dependence among the samples be utilized for achieving a somewhat higher memory saving.

This does not mean, however, that more sophis­ ticated schemes cannot provide better storage-error characteristics under special circumstances. If, for instance, there exists a strong a priori know­ ledge that the observed sample is in some sense compact, then it becomes quite reasonable to store only descriptions of its boundaries, not the en­ tire sample. The results obtained here refer to query sets and data sets which are uniformly and independently distributed. They are valid in cases where no structural knowledge exists (except the sample size n); any combination of n objects from C could constitute a data set and any member of m em could represent a query.

Preliminary investigation of the effect of structure (using Markovian model) shows that the essential features of the memory vs. error charac­ teristics remain unaltered with the introduction of structure into the data. While the memory required to achieve zero error is substantially reduced, tne additional percentage reduction in memory require­ ment induced by error-tolerance remains close to that of structureless data.

Pattern Classification Systems

Consider a collection C of objects (or pat­ terns) which is partitioned Tnto three classes: n objects are in class c+, n in C, and the rema1n1rg m-2n objects in class co. During the filing eha~e a QA system is shown the elements of C and C W1t11 their proper class identity. During the query phase an arbitrary object from em is presented, and the system is asked to classify it either as c+ or c-. An error is counted whenever an element of C+ or c- is misclassified, but not when an element of c 0 is labeled (+) or (-). c+ and c- stand for what is commonly called the "training-set", while c 0 represents unobserved patterns. The neutrality of c 0 reflects our commitment to evaluate system performance strictly on the basis of observed data, leaving aside considerations of inductive-power .

It is clearly possible to answer all queries correctly if we store the identities of the n elements of c+. We simply label every query (+) if it is in storage and (-) if it is not. This scheme requires on the order of n log~ m bits of memory and thus could become prohibit1vely large for prac­ tical values of the samgle-size and the data dimensionality (e.g. m = 2 10 n = 2 20 ). Most pattern classification methods, however, are motivated by the belief that classification systems lend them­ selves to a greater storage economY. It is promp­ ted by noting that unlike data-retrieval systems the exact reconstruction of the data is not re­ quired; only information pertaining to the differ­ ence between the classes need be stored. It fol­ lows that one can always add any number of elemen~ from c 0 to either c+ or c- at no extra cost, and so simplify the description of the separating rule. It wili be shown that this argument is justified; the number of dichotomies needed for correct sep­ aration of all pairs of classes is much smaller than the number of all possible choices of C . Thus, storing the description of any one such di­ chotomY could be made more economical than storing + the exact description of C .

Consider the multi-category classification problems whereby a description of an t-chotomY is to be found, and the sample set contains n objects in each class Ci, i = 1, 2, ···, t, and m- tni objects in C . The rate-distortion function for 0 this problem is given by [9]:

where dis the number of misclassification errors per sample:

It is depicted in Figure 3; as the number of cate­ gories increases the normalized rate-distortion curves approach the line 1-d.

In particular, for t = 2 we obtain:

Note that the memory required for classification is linear with n, the sample size, but is independent of the size of the sample space, m.

It is not at all obvious that storage require­ ments should remain finite as m ~ ~· Consider, for instance, the requirement ford= 0, the zero er­ ror condition. The straightf~rward scheme of stor­ ing one complete class, say C , requires a storage capacity of log 2 (~) ~ n log2m bits, while equation (3.5) claims a storage of 2n bits, which amounts to only 1 bit per sample. Indeed, the complete storage scheme is far from optimal, and schemes such as decision trees could achieve a perfect classification with a ~storage of only 1 bit per sample. ·

For a simple demonstration of such schemes consider n = 1, where two binary sequences each N bits long (N = log 2 m) are presented with their (+) and (-) labels. At a later time an arbitrary bin­ ary N-sequence is presented for classification with the requirement that if the third sequence is identical to any of the original two, it must be classified correctly. Rather than storing one of the ori9inal samples (which requires N bits of storage), a more economical scheme can be employed: one need store only the index of the bit where the two samples first disagree, and the content of that bit. This requires at most only 1 + log 2 N bits of storage. Moreover, if the two samples are arbitrary, the probability is quite high 'that dis­ agreement would occur in the first few bits of the sequences leading (e.g., using Huffman Code) to a mean storage requirement of about three bits - slightly more than the two bits predicted by (3.5).

4. Order-Related QA Systems

Position-Matching Systems

Here we will consider systems which accept data-sets in the form of ordered lists of m dis­ tinct items, and respond to queries of the type: "What item stands in the kth position?" In such systems the admissible queries can be represented by the set of integers from 1 to m, the answer­ vocabulary~ is the set of items {a 1 , a 2 , ···am}, and M is the set of permutations of the a's. Thi s leads to: M = m!, Q am, and K = m. Since every m-tuple from Am can represent an answer-string, ~ = ~m. and lal = mm. The distortion measure dij is given by the mean number of symbols in answer­ string j which are not matched to their correspond- ­ ing symbols in i. Clearly, a mean error of 1-1/m is achievable with no memory at all simply by pro­ ducing an answer-string with one repeated symbol , thus, Dmax = 1-1/m .

The rate-distortion function of this system can be shown to satisfy [9]:

where

For large m one may use Stirling's log ml ~ m log m, and obtain: approximat i on

Thus, as m becomes very large the lower bound on R(D)/R(O) approaches the data-erasure line 1-D at a logarithmic rate.

These results can be summarized by the follow­ ing conclusions . As the siae of the data increa­ ses, the amount of storage needed to represent an ordered sequence of m items with a per-query error D is given by {Z-D) m 'log m. Thus, no amount of . error (be Zow uni ty) oan make memory demands grow sl-ower than m 'log m, and no data-reduction scheme exists which achieves a memory economy higher than that of data-erasure.

Note that the mathematical structure of pos i­ tion-matching systems remains essentially unaltered if Q. is rep 1 aced by queries of the type, "Who i s the immediate successor of a 1 ?" The only change required would be the inclusion of a null symbol ~ in the answer vocabulary to represent the answe r "no successor". With this modification we have K = m+l instead of K = m, which for large m indu­ ces only a slight change in R(D). We thus con­ clude that successor-finding tasks are subject t o the same basic memory vs. error limitations as those limitations found for position-matching tasks .

Pair-Ordering Systems

Let us consider a question-answering system which examines an ordered array of m items (a 1 , a 2 , ··· a) during the filing phase, and later responds to qu~ries of the type, "Does ai precede a.?". The data-space M is again the set of permuJ - tat ions on ( a 1 · a 2 · · · · am) . The set of queries. however, is homomorphic to the set of all m(2-l ) pairs of elements, and the answer vocabulary ~i s {0, 1}, with 1 and 0 standing for affirmation and denial of the query respectively. We assume that only one of the two queries: a 1 ~ aj' aj ~ a 1 is in Q.. Thus, we have :

An answer-s~ring can be any binary Q-tuple, and so, IAI = 2 . The distortion measure d .. , between data-~et i and answer-string j, is simpl~ given by l/Q times the number of pairs in i whose relative order conflicts with that stated by j. Clearly, if no information at all is retained in storage, any arbitrary answer-string would leave (on the 1 average) 50% of the answers in error, so, D = ~· max .:

The lower bound on R(D), obtained [10] by the method leading to (4.1), gives:

For large m this becomes:

Thus, given any non-zero D, there is always an m sufficiently large to make the bound zero. This can be attributed either to the fact that the sys­ tem permits increasing amounts of memory savings, or simply to the looseness of the bound. We will later demonstrate that the former is true, by using an upper bound on R(D).

Note that the essential difference in the be­ havior of equations (4.1) and (4.5) comes from the increased size of the query set Q_. The two are special cases of a general bound-raJ:

which holds for all question-answering systems with symmetric distortion measure (2.7). We may con­ clude that in order for R(D)/R(O) to vanish for all D > 0 it is necessary that Q increases (with m) faster than log M. This can be expressed by the general statement: a neaessary aondition to enable a QA system to aonvert any smaU error toZeranae into a s Zower growth of memory demand is that its query set be inareasingZy ~dUndant. Position­ matching, for instance, has a query set with only a slight redundancy; one must know the position of m-1 items before the position of the remaining mth item can be deduced wi ttl certainty. In pair-order­ ing systems, on the other hand, knowing the correct precedence of only a small fraction (m-1) of selec­ ted pairs may be sufficient to deduce (by transi­ tivity) precedence in all the remaining (m-l)(m-2)/2 pairs.

We now derive an upper bound on R(D) and dem­ onstrate that a small error tolerance can reduce memory demands by a factor of log m. To that end we calculated the rate-distortion function Rr(D) of a restricted system where only transitivity-preser­ ving answer-strings are allowed. This yields a parametric representation for Rr(D) [10]:

where z is the tween 0 and 1 . the sunmations ting numerical independent parameter varying be­ For values of z not too close to 1 in (4.8) converge rapidly, permit­ computations of Rr(D) even for very large values of m. Equation (4.8) is depicted by the solid lines of Figure 4 form= 100, 1000, and 10,000. It is seen that the (normalized) curves undergo a sharp drop in R near D = 0, and that this drop continues to grow with increasing m.

For large m, the asymptotic behavior of Rr(d) is given by:

Thus, whi Ze the memory requi~d to answer aZZ que~ ies ao1'1'eatZy grows as m Zog m, onZy a Zinear in­ arease with m is ~qui~d when a smaZZ but finite error rate is tolerated.

Recalling that Shannon's theorems guarantee only the existence of codes for very long data blocks, it remains to show that a memory reduction similar to (4.9) could also be achieved by schemes which encode each data-set separately. This can be demonstrated using the popular filing scheme known as "clustering". Assume that the sequence (a 1 , a 2 , ··· ~) represents the correct order of elements. Divide the sequence into t groups each containing exactly m/t consecutive elements, and retain in memory the name of each item coupled with its group name. In the answering phase, adopt. the following strategy: if a 1 and aj belong to two different groups, use the group label to decide precedence; if a; and aj belong to the same group, choose an arbitrary answer. It is easily shown that the memory vs. error characteristics of this scheme are governed by:

implying a linear memory growth similar to that predicted by the restricted rate-distortion func­ tion Rr(D). The two are compared in Figure 4.

It is tempting to relate these results to fuzzy-sets representation [1] schemes. Here too, only a fixed number of linguistic labels such as "very small", "medium", "large", and "extremely 1 arge" are used to characterize 1 i near orders of any size. Equation (4 .10) indicates that for the purpose of pair-ordering the scheme is close to op­ timal. However, clustering methods employ sharp partitioning of the element-set into non-fuzzy sub­ sets. It is not clear whether additional memory gain could be achieved by the use of numerical in­ dicators for 'the degree of set membership'. It is conceivable that the computational advantage of fuzzy-set coding schemes can only be demonstrated in more complex data structures such as those con­ taining relations among several orders.

5. Conclusions and Relations to Computational Complexity

Four question-answering tasks were analyzed to test the conjecture that significant memory savings could be materialized with only a slight tolerance for errors. It was shown that the tasks of data­ retrieval and pattern-classification, which in the past have absorbed considerable efforts toward ec­ onomy of descriptions, are subject to a basic lim­ itation . No data-reduction scheme exists which ex­ ploits error-allowances in an appreciably more ef­ fective way than a straightforward data-erasure . Position-matching, namely, the task of representing a linear order for the purpose of rank identifica­ tion (or successor identification}, is subject to a similar limitation. In applications where the basic decision unit served by the order is the de­ termination of prPcedences on pairs of elements, a more substantial reduction in memory size can be achieved when a small but finite error is permitted This difference in behavior is attributable to the fact that in pair-ordering applications the elemen­ tary decision tasks are highly interdependent (via transitivity), whereas those in position-match ing applications are almost independent.

In a more recent work [3] it was found that the results reported in this paper go beyond our origi­ nal intent of 1 imiting the storage-error exchange. The work demonstrates that many complexity measures on a variety of computation models can be effec­ tively bounded using the rate-distortion function. Given a computational ta~k (e.g., sorting, function computation, sequence generation), a class of algor­ ithms for accomplishing that task (e.g., straight line algorithms, finite state machines) and a com­ plexity measure o~ the class (e.g., program length, time or space complexity, combinational complexity}, there exists a characteristic function C[R(D)] whictt provides a lower bound on the mean complexity neces­ sary to produce a mean distortion not exceeding D. Moreover, in almost all interesting cases the func­ tion approaches a straight line C[R(D)]% a R(D) as the task ~ize becomes very large. This implies t~t the relative reduction in the mean complexity in­ duced by tolerating a mean distortion 0 cannot ex­ ceed the relative change of the rate-distortion function R(D).

Typi cal results obtained by this method are:

1. The mean number of binary comparisons re­ quired for sorting N-sequences is bounded by

where Ds is the fraction of terms in the output se­ quence which are followed by wrong successors. It implies that no sorting scheme exists which matches a fixed percentage of the term with their correct successors and which requires less than O(N log N) comparisons.

1. If 0 is the fraction of pairs in the out­ put sequence ehich are out of order, then the mean number of comparisons is bounded by

Equation (5.2) allows for the possibility of sort­ ing N sequences in linear time if one permits any finite fraction of pairs to remain out of order. Such a sorting scheme indeed exists using QUICKSORT.­ with a predetermined number of iterations.

1. The mean combinational complexity of Bool­ ean functions in N variables is bounded by

where 0 is the probability of output errors.

1. The average number of states over the en ­ semble of minimal-state sequential machines needed to reproduce binary N-sequences with probability of errors not exceeding 0 is bounded by:

It is conjectured that the relative insens i ti­ vity of R(D) to errors of the type treated in this paper will also limit the complexity vs. error ex­ change of language-recognition and theorem-proving. It appears that if inexactness could permit drastic computational savings the effect may surface only in cases where the data is highly structured and/or the queries are highly redundant.

Acknowledgment

This work was supported by the National Sci­ ence Foundation under Grant No. GJ 42732.