Flexible Matching for Noisy Structural Descriptions

1 Introduction

The nature of the problem solving task performed by most expert systems is classification, that is, mapping entities of the world into a set of predetermined solutions or recommendations [Clancey, 1985; Weiss and Kulikowski, 1984]. Typically, . expert systems for diagnosis are concerned with selecting an answer from an existing set of diagnoses (solution elements) given the description of a situation. Classification is equally fundamental in nearly all know ledge-based pattern recognition systems, which have to assign appropriate interpretations to objects within a scene [Chandrasekaran and Keuneke, 1987]. Independently from the direction of reasoning, either forward or backward, such systems operate with a description of the current state in the working memory and a description of the conditions to be satisfied in order to select the rule.

Unfortunately, in real applications the descriptions may be both incomplete and also affected by noise. The latter problem is especially felt in those applications in which data are directly detected through sensors or transducers. A scribble on a document or a voice in the background are two common forms of noise. In addition, humans can also introduce errors in the data due to misunderstanding or lack of attention. Another form of noise in a measurement occurs when the measuring instrument shows a poor accuracy. Finally, information may be incomplete due to either human inadequacy or malfunctioning equipment.

When acquiring knowledge from humans, the problem could be solved by multi-expert knowledge acquisition and by applying a cross-validation technique to the rules provided by the experts. In automatic knowledge acquisition the problem is approached by making the machine learning techniques more robust as regards noisy and/or incomplete data [Quinlan, 1986].

Bergadano et al. [1988] proposed an approach to learning human concepts which are inherently imprecise and context dependent. The method uses a two-tiered representation of learned concepts and a flexible matching, based on a numerical estimation of the typicality or certainty that an instance is a member of a concept, so providing a form of probabilistic inferential extension of a concept In this case, both concept metaknowledgeconcerning the importance of concept attributes as well as the (joint) probability distributions of these attributes are essential.

To sum up, noisy, imprecise, context-dependent and incomplete descriptions demand a more flexible matching process, also called partial matching in [Hayes-Roth, 1979], where two descriptions are compared in order to identify their similarities rather than their equality. Generally, the term best match is also used when the rule which maximizes the similarities and minimizes the differences against the current state is selected. The result of a flexible matching should produce a number indicating how well two descriptions match. The number can be a value in the unit interval [0,1] such that 1 indicates a perfect match, 0 no match at all, and any real number r, re (0,1), denotes our confidence in matching. The definition of such a similarity measure is strictly connected to the most common concept of distance, as the more distant two objects are, the less similar they can be considered.

Several distance measures, or conversely, several similarity measures, have been proposed in the fields of pattern recognition [Sanfeliu and Fu, 1983; Wong and You, 1985; Shapiro and Haralick, 1981] and machine learning [Michalski et al., 1984; Kodratoff and Tecuci, 1988]. They differ in a variety of respects:

• representation language: propositional logic, first-order predicate logic, feature vectors, attributed relational graphs;
• type of problem the distance measures are applied to: pattern matching in knowledge-based systems, concept acquisition, pattern classification, discriminant analysis, conceptual clustering, numerical taxonomy;
• theoretical approach: geometrical, syntactical, probabilistic, entropical, fuzzy, hybrid;
• type of corrected deformations: local or structural. This last point requires further explanation. Generally, an object (or situation) can be decomposed by successive

refmements until atomic parts, called primitives, are defmed. Once these subparts and their mutual relationships are identified, the structure is obtained [Stepp, 1987]. The complete description of the object is given by:

• the attributes of the entire structure (global attributes);
• the attributes of some subpart (local attributes);
• the attributes of the interrelationships between parts (relations).

When the differences between the two matching descriptions concern the global/local attributes it is said that local deformations occur, while when the differences are at the level of relations then deformations are called structural. Not all distance measures take into accountstructwal deformations, particularly those adopting a representation language which does not allow us to represent structwal descriptions.

This paper introduces a definition of distance measure suitable for dealing with structural deformations which is based on a probabilistic interpretation of the matching predicate. The three basic characteristics of our definition_ are: 1) the possibility of dealing with rules whose conditions are not stated as exact descriptions of a particular situation but describe (complex) properties that the situations must have; 2) the necessity to defme, objective! y or subjectively, the probability density functions of the features (attributes or relations) used to describe a situation; 3)the possibility of dealing with rules whose conditions are incomplete structural descriptions.

In the following, Section 2 introduces the definition of a flexible matching function for evaluating the goodness of any match between noise-affected structural descriptions. The problem of matching (or unifying) two expressions with commutative andassociativeoperators is NP-<:omplete [Garey and Johnson, 1979; Siekmann, 1990], moreover the computational cost of a flexible matching procedure increases with the need to calculate the similarity measure. Consequently, we can either try to find algorithms that perform quickly on average or try to find approximate algorithms that produce acceptable answers in an acceptable amount of time. In Section 3 we describe how a branch-and-bound algorithm can be used for reducing the average computational time of the actual similarity between two structural descriptions. Furthermore, for those applications involving complex descriptions and requiring an answer in relatively short time, we discuss the possibility ofintroducing a heuristic rule which allows us to find an approximate value of similarity. Finally, in Section 4, an application of the proposed distance measure to the recognition of office documents in digital form according to their page layout is illustrated.

2 A distance measure for flexible matching between wff' s

Let ii denote the space of all the possible descriptions (or well formed formulas (wff's)), complying with the syntax of the representation language and built according to a given vocabulary of attributes and relations. Here we are interested in defining a flexible matching function:

which could be considered as an extension of the canonical (strict) matching predicate:

By extension we mean that

The function Flex_Match(s,t) represents a degree of similarity between two descriptions s,tE ii, or even the degree of fitness of son t. The definition of such a function should be based on a theory which is able to quantify the degree of similarity between two descriptions. As probability theory fulflls such requirements, we can assign to each pair of wff 's in 6 the probability of precisely matching the two formulas provided that a change is made in the description t; formally:

Such a definition marks the transition from syntactic to probabilistic matching. Consequently, it is possible to defme a probabilistic distance measure, .:1, between s and t as follows:

A more detailed definition of distance measure requires a rather more specific description of the representation language than we have given up to now. In particular, the representation formalism we have chosen is inspired to VL 21 [Michalski, 1980]. The basic component of the VL 21 is the selector or relational statement, written as:

where:

• L, called referee, is a function symbol with its arguments;
• R, called reference, is a set of values of the referee's domain;

Function symbols, called descriptors, are n-adic functions (n2:1) mapping onto one of three different kinds of domains: nominal,linear and tree-structured.

Selectors can be combined by applying different operators, such as AND (A), OR (v) and decision operator(::>) in order to define wff 's like:

where d-formula is a disjunction of or-atoms (selector conjunctions), while c-formula is a conjunction of selectors. This formalism is adequate to express classification rules in many knowledge-based pattern recognition systems dealing with structural descriptions.

Since the main application of the proposed distance measure is noise-affected concept recognition, from now on s will denote the description of a concept and t the observation to be classified. Moreover, the specializing isomorphism (s­ isomorphism) [Larson, 1977] rather than the simple isomorphism is used in concept recognition, therefore the match of s and t consists in searching for a substitution a such that

Flex_match is computed according to the following top­ down evaluation scheme:

I) sis a disjunction of conjuncts: s = Or_atom 1 v Or_atom 2 v ... v Or_atom 0 · Then the formulation of the flexible matching is given as follows:

This definition corresponds to the idea that when a concept is polymorphic (i> 1 ), we are usually interested in finding the "best" matching between one of its morphisms and the observation t. For instance, if s = [length(s1)=10 .. 100] v [width(s2)=5 . .30] and t = [length(s1)=9]" [width(s1)=45], we say that t "nearly" satisfies s simply because it is "near" to the first morphism of s. When correlations occur among the different morphisms expressed by s, the definition above has to be extended so as to take them into account.

m sis a conjunction of selectors: s = SellASel:l' ... ASelk(k>O). Thus the computation of the flexible matching is affected by the consistent substitution cr. of the variables ins. As we are looking for the best matching between s and t, we define:

where Flex Match. denotes the flexible matching function with the tie of the shbstitutions fixed by CJ ..

lll) sis a selector: s = [f(v 1 ,v 2 , ··· , v 1 )= g 1 , ~ ···· , gM], wheref is a 1-adic descriptor and {gl' ~· ... , gM} is a subset of the domain Doff. Flex_Match.(SeV) is determined by evaluating the degree o_f similarity be~een the selector CJ/s) = Sel, and the correspondmg selector oft, Sel,= [J(w 1 ,w 2 , · ·· , w 1 )= e 1 , e 2 , · · · , em], which has the same referee as Sel,. Consequently:

Flex_Match.(s,t) = Flex_Match(Sel,,Sel,) (3) and Flex_Matcb(Sel,,Sel,) computes the degree of similarity between the references of Sel, and Sel 1 ·

Since we are searching for an s-isomorphism, the similarity between the references of Sel, and Sel, is equal to 1 if and only if the reference of Sel, is more specific than that of Sel,. The notion of specialization is intended as set inclusion, if the descriptor f is a nominal or linear one. This interpretation can be easily extended to tree-structured descriptors: each single element in the reference of two selectors is replaced by all the values representing the leaves of the subtree having that particular element as its root

The presence of multiple values in the reference of Sel, actually means that the value of an attribute is not known exactly, but it ranges over a subset of the attribute domain. This is a form of uncertainty in data [Dubois and Prade, 1988] and its management, together with the problem of incomplete descriptions, has been extensively described in [Esposito et al., 1991a]. Henceforth, we will assume that m=l, that is we are sure about the value e taken by f in Sel,.

Let EQUAL(x,y) denote the matching predicate defined on any two values x and y of the same domain. Since we are looking for the best mapping from { e} into {g 1 , g 2 , ··· , gM}, then the definition of flexible matching depends on the maximum probability of two matching selectors computed over the set of all possible correspondences between the elements of { e} and { gl' ~· ... , gM}, that is:

Such a defmition takes into account the goal of classification by means of event covering, thus when e e {gl' ~· ... , gM} then MF(Sel,, Sel 1 ) = 1 because there is a perfect match, otherwise MF(Sel,, Sel,) represents the maxim urn probability that the value in the reference of Sel, equals one of the M values in the reference of Sel,.

The probability of the event EQUAL(g 1 ,e) can be defined as the probability that an observation e could be a distortion of gi, that is:

where:

• X is a random variable assuming values in the domain D of f;
• ~ is a distance defined on the domain itself.

In other words, the probability that any two values of the domain D match is defined as the probability that a random variable X defined on D takes a value farther than e from ~· given that gi is the centroid. In Figure 1, a geometrical interpretation of this definition is provided.

The defmition of o must take into account the type ofVL 21 descriptor. In particular we propose the discrete metrics for nominal descriptors:

for linear not numerical descriptors:

where ord( x) denotes the ordinal number given to xeD, and for linear numerical descriptors:

It should be observed that other reasonable choices of o are possible; nevertheless the value ofP(EQUAL(gi,e)) does not change since we compute the probability over distance and not merely geometrical distance. This key point also allows us to ignore problems with scaling when the similarity is computed over the whole set of features.

Of course, the computation ofP(EQUAL(gi,e)) must take into account the probability density function of X. When no information is available on the probability distribution of X we assume X to have a uniform probability distribution, that is:

for the descriptors with a finite domain (here Cis the cardinality ofD), while

if the domain Dis an interval [a,b] (here f 0 denotes the density function).

Having made such assumptions it can be proved that for nominal descriptors we have:

while for linear not-numerical descriptors we get:

where:

A proof of fonnulas (9) and (10) is given in Appendix A. For the descriptors with tree-structured domain the computation of P(EQUAL(gi,e)) makes use of the previous fonnulas. Each element in the references of Sel and Se~ is replaced by the values representing the leaves ol the subtree which has that element as its root. The fonnulas (9) and (10) are adopted, depending on whether the generalization hierarchy for the descriptor is unordered or ordered, respectively. The only changes to be made both in (9) and (10) consist in replacing C with the number of leaves of the tree-structured domain.

3 Coping with complexity of matching

The computation of the flexible matching when s is a conjunction of selectors requires the evaluation of the maximum conditional probability as in fonnula (2) as cr. varies. Unfortunately, if p and q (p~ q) are the number of vaHables in s and t respectively, the number of possible substitutions cr. is given by the pennutation of p elements taken from a set cif q elements, i.e. P(q,p). Consequently, the computation of Flex_Match(s,t) has a combinatorial cost which should be reduced in some way, particularly when P(q,p) is very large.

In order to prevent an exponential growth of the computational time, two alternative techniques are presented in the following. Each of them requires that s and t were connected conjunctions of selectors (for a definition of connected fonnulas see [Larson, 1977]).

Firstly, we can make use of a branch-and-bound algorithm which perfonns quickly on average. The search space can be represented by a tree where:

• the nodes are variable pairs, (vi,wJr.), representing the substitution vi+-- wJr. of a variable vi appearing ins with a variable w appearing in t;
• a branch from a node N1 to a node N2 represents the instantiation of a variable of s which has not yet been instantiated in any node along the path from the root to Nl.

When all the variables ins have been instantiated, the node of the tree representing the last instantiation can by no means branch (i.e. it is a leaf), and the set of the substitutions along the path from the root represents one possible substitution cr. (see Figure 2). J

Each node of the tree can be labeled with a pair of numbers. The fiCSt number represents the partial measure of fitness computed only on those selectors of s whose variables have already been instantiated along the path to the node. The second number represents the exact number of selectors ins which gave a contribution to the computation of the partial measure offitness.lf there is a branch from a node N1 to a node N2 then the value of the partial measure of fitness in N2 must be less or equal to that associated with N 1, due to the definition of flexible matching. In other words, walking along a path from the root towards a leaf of the tree, the partial distance measure associated with each node can only decrease or remain the same. A similar (but increasing) monotonic property is also true for the second value reported in node labels. These considerations suggest how a branch-and-bound algorithm can help in finding the best substitution more quickly. In fact, it is sufficient to consider a function cost composed by the partial distance measure and the opposite of the number of selectors in s which contributed to the computation of the partial distance. Minimizing the function cost while the tree is extended allows us to find the best substitution without necessarily exploring all the possible alternatives. When sis a disjunction of or-atoms, the algorithm proceeds exploring alternative consistent instantiations of variables belonging to all the or-atoms, otherwise it could spend too much time trying to evaluate the distance measure concerning a single "bad" or­ atom.

As second alternative, it is possible to decomposes into two parts:

• s' = Sel 1 ASe~A ... ASel,, r ~ k, is a conjunction of selectors such that the referee of Seli, i = 2, 3, ... , r, contains the maximum non-null number of variables not appearing in the referees of Sell' Se~ ·... ,Seli- 1 ;

so that:

• s" is a conjunction of the remaining selectors in s.

The constraint of connection upon s ensures that all the distinct variables in s were ins'. As a consequence, the search for a substitution cr such that t =>cr(s) can be weakened into:

Under such a hypothesis the events Flex_Match.(SeV ), i=r+ 1, r+ 2, ... , k, become independent since the subsrltution cr that verifies ( 11) has already bounded the variables ins'. As a result, we have:

This fonnula must be interpreted as follows: while varying the considered substitution cr., the flexible matching between s and t is computed as thd highest value given by the product of the degree of similarity between each selector of s" and t.

When it is not possible to find a substitution satisfying ( 11) then we can set Flex_Match(s,t) = 0, since s and t have no similarities, not even at a level of variables (components). This interpretation corresponds to the heuristic thats' is a conjunction of Must-relations [Winston, 1984], thus the computation of (12) is perfonned only if a perfect matching can be detected between s' and t Sometimes the choice of s' is not unique, in that case a simple preference criterion based on the sum of weights of the selectors in s' may help to select the best alternative.

4 Application to Document Recognition

The flexible matching algorithm has been employed and tested as a partofPLRS,a system for digitized office document recognition based upon the page layout [Esposito et al., 1990]. Within the scope of the ODNODIF standards [Horak, 1985], a document presents two hierarchical structures: both the layout (or geometric) and the logical structure. The former concerns the internal organization of the document, i.e. the areas containing text and images, and some components are: set of pages, pages, frames and basic blocks. The logical struc~ associates the content of a document with a hierarchy of logtcal components, such as articles, summaries, sections, paragraphs, page numbers, logotypes, and so on. Furthermore, documents can be grouped into classes according to a specific criterion, such as the kind of processing or the common subject.

PLRS classifies single page documents using only on the page layout structure, i.e. the invariant geometrical characteristics shared by documents belonging to the same class, due to underlying printing standards or writing style. An extension of PLRS exploits the results of the document classification process in order to identify the logical components of a document again using the page layout structure. However, this problem, named document understanding, is still under study and it will not be dealt with in this paper.

The rules used for the page layout recognition are produced by means of a process of inductive learning, in which some meaningful examples of document classes, relevant for a specific office, are used to train the system. This allows the "in field" customization of the system, thus avoiding the definition of user-handwritten classification rules for a specific office. The form of a recognition rule is:

<condition> ::> <decision>

where:

• <condition> is a VL 21 wff in disjunctive normal form;
• <decision> refers to a document class.

. The ~ge layout of a document is automatically described m symbolic form, as a VL 21 conjunctive formula, by a document processing system performing the following steps:

• preprocessing of the digitized document;
• segmentation into basic blocks through the Run Length Smoothing Algorithm (RLSA);
• layout analysis, that groups together blocks satisfying some predefined requirements, such as closeness, alignment, and so on, into larger blocks, called frames, and produces numerical tables describing each frame;
• tran~lation of the numerical tables produced by the previous step mto VL 21 symbolic descriptions.

The descriptors used in the document description are:

CONT AIN_IN_POS(Doc,Block), WIDTH(Block), HEIGHT(Block), TO _RIGHT(Blockl,Block2),

ON_ TOP(Blockl,Block2), ALIGN (Block l,Block2) and a page layout description of a training document is reported in the following:

[contain_in_pos(xl,x2)=north] 1\

[ contain_in_pos(x l,x3)=north_ west] 1\

[contain_in_pos(xl,x4)=centre] 1\ [width(x2)=large] 1\

[ wi?th(x3)=medium] 1\ [ width(x4 )=medium_large) 1\ [hetght(x2)=medium] A [height(x3)=medium_small] 1\ [height(x4)=very_very_large] 1\ [on_top(x2,x3)] 1\ [on_top(x2,x4)] A [to_right(x3,x4)] 1\ [align( x2,x3)=beginning_ column] 1\ [align(x2,x4)=last_column] 1\ [align(x3,x4)=beginning_row] ::> [class=three]

The classification of a new document consists of two steps. Firstly ~e conditio~ part of each recognition rule generated by the learnmg system ts matched against the symbolic description of the new document. Secondly, the document is assigned to the class specified in the decision part of the matching rule. Due to the presence of noise affecting the VL descriptions of documents, such as a scribble on a docJ:.Oent or sensing problems, it is not possible to use a canonical (strict) matching procedure for classifying test documents, therefore the proposed flexible matching is adopted.

. In ?rder to tes.t our approaches to coping with complexity m flextble matchmg, we organized an experiment in which a set of 72 single page documents, belonging to nine different classes, has been considered. Four classes are letters, each cla~s containing generic printed letters of the same company, whtle other four classes are magazine indexes; the ninth class ~s a reject class, representing the rest of the world. Fifty ms~c~s were selected as training examples, leaving the remammg 22 documents for the testing process.

The results of the application of both branch-and-bound algorithm and the heuristic method in the flexible matching procedure applied to the test documents are reported in Table 1 and 2, respectively. In Table 1 entries containing a"*" mean that the value of the flexible matching (FM) is not known since the search has been interrupted. This happens when the partial similarity measure becomes lower than a fixed threshold (0.3 in our experiment). In Table 2 null "FM" values indicate that a strict matching on s' is not possible (see formula (12) ). In ~t? tables, an FM value 1.0 in the column denoted by rulei mdtcates the presence of a perfect matching between the test document and the rule generated for the i-th class. The results concerning a full comparison between the canonical matching procedure and the flexible matching have been reported in [Esposito et al., 199lb in press].

As we could theoretically expect, entries in Table 1 are never less than the corresponding ones in Table 2, since the branch-and-bound algorithm fmds the highest similarity. It should be observed that the classification results do not change at all if the heuristic method is used and the class corresponding to the highest value of similarity is taken as the membership class. The correct class is reported in the first column of Table ~· Both the tables also present the throughput time, expressed m seconds, for each flexible matching and the total time per document(lastcolumn)orperclass(lastrow). We can conclude from a comparison of these time entries that the branch-and­ bound method needs much more time than the heuristic method, and this is a great limitation for a real-time document handling system.

5 Conclusions

. ~n the paper a definition of a flexible matching is presented: tt ts ~ased on a probabilistic interpretation of the matching predtcate and proves useful to cope both with noisy data and with structural deformations. Unfortunately, computing the similarity of two descriptions is computationally impractical, therefore two distinct methods are adopted to reduce the complexity: frrstly, branch-and-bound algorithm, and secondly, a heuristic method. The flexible matching has been applied to the recognition of digitized office documents and the results of both the algorithms are presented.

A Proof of formulas (9) and (10)

g instead of gr As already said, formula (IB) takes into account both the type of domain which g and e belong to and the probability distribution of the domain values.

By assuming that the probability distribution is uniform, and remembering the defmition of~ for nominal domains, we have:

where C is the number of elements of the domain. For ordinal domains, (IB) becomes:

P(EQUAL(g,e)) = P(lord(g)-ord(X)I2: l<>rd(g)-ord(e)l) = which can be rewritten in a simpler form by denoting ord(g), ord(e) and ord(X) with g,e, and X, respectively:

2nd case: g > e

P(lg-XI ~ lg-el) = P( g-X<e-g u g-X=g-e u g-X>g-e u g-X=e-g )=

= P(g-X<e-g) + P(g-X=g-e) + P(g-X=e-g) + P(g-X>g-e) =

= P(X>2g-e) + P(X=e) + P(X=2g-e) + P( X<e) =

= P(X2:2g-e) + P(X~) =

3rd case: g < e

P(lg-XI ~ lg-ej) = P( g-X<g-e u g-X=e-g u g-X>e-g u g-X=g-e )= = P(g-X<g-e) + P(g-X=e-g)+ P(g-X>e-g) + P(g-X=g-e) =

= P( X>e) + P(X=2g-e) + P(X<2g-e) + P(X=e) =

= P(~2g-e) + P(X2:e) =

= [(2g-e+ 1)·step(2g-e) + C- e]/C (6B)

where step(x) is the following function:

Finally, resubstistuting ord(g) and ord(e) to g and e, respectively, we have formula (10).