First-Order Logic Horn clauses are a powerful representation formalism for domains where relations among objects must be expressed to fully capture the relevant information. While the predicates that make up the description language are handled only syntactically by the interpreters, they sometimes express information that can be properly exploited only with reference to a speci c background knowledge in order to capture unexpressed and underlying relationships. Two prototypical examples are taxonomic information (e.g., coming from the words found in a text) and numerical information (e.g., coming from measurements and acceptable ranges), for which simple syntactic matching is not sufcient. This work proposes an extension of an existing framework for similarity assessment between First-Order Logic Horn clauses for these two cases. The viability of the solution is demonstrated on sample problems.
First-Order Logic (FOL for short) is a powerful representation language that
allows to express relationships among objects, which is often an fundamental
requirement in real-world and complex domains. Logic Programming [
The predicates that make up the description language are usually de ned by the knowledge engineer, and are handled as purely syntactic (uninterpreted) entities by the systems. The knowledge engineer can also provide a background knowledge to be exploited in order to improve performance or e ectiveness of the results. However, the use of uninterpreted predicates and terms (meaning by `interpretation' their mapping onto meaningful objects, concepts and relationships) is often too limiting for an e ective application of this kind of techniques to real-world problems, where there are a huge number of implicit connections and inter-relationships between items that would be ignored by the system. For limited and simple domains, only a few of these relationships are actually significant, and must be expressed not to prevent nding a solution. In these cases, they can be provided in the form of a background knowledge. However, if the amount of relevant information to be expressed as background knowledge grows, this becomes infeasible manually and requires the support of readily available resources in the form of explicit knowledge items or computational procedures.
This paper builds on an existing (uninterpreted) framework for similarity assessment between FOL Horn clauses, and extends it with novel and general approaches to handle two particular kinds of information that often need to be expressed in the descriptions: taxonomic information, conveying implicit relationships among the concepts described, and numeric one, involving single values and/or intervals. The next Section introduces the basic formula and framework for the overall assessment of similarity between Horn clauses. Section 3 proposes a solution to compute the taxonomic similarity between two concepts or words, and shows sample experiments. Section 4 does the same for numeric similarity. Section 5 presents experiments on the e ectiveness of introducing the new similarity components in the overall First-Order Logic framework. Lastly, Section 6 concludes the paper and outlines future work directions. 2
The framework for computing the similarity between two Datalog [
l + 1 l + n + 2 + 0:5
l + 1
l + m + 2
(1)
It exploits both information that is common to the two items, which increases
similarity, and information of each item that are not owned by the other (the
residual of the former with respect to the latter), which decreases similarity [
In FOL representations, usually terms denote objects, unary predicates
represent object properties and n-ary predicates express relationships between
objects; hence, the overall similarity must consider and properly mix all such
components. The similarity between two clauses C0 and C00 is guided by the similarity
between their structural parts, expressed by the n-ary literals in their bodies,
and is a function of the number of common and di erent objects and
relationships between them, as provided by their least general generalization C = l0
:l1; : : : ; lk. Speci cally, we refer to the OI generalization model [
The similarity between two compatible n-ary literals l0 and l00, in turn, depends on the multisets of n-ary predicates corresponding to the literals directly linked to them (a predicate can appear in multiple instantiations among these literals), called star, and on the similarity of their arguments:
sfs(l0; l00) = sf(ns; ls; ms) + avgfsfo(t0; t00)gt0=t002 where is the set of term associations that map l0 onto l00 and S0 and S00 are the stars of l0 and l00, respectively:
ns = jS0 n S00j ls = jS0 \ S00j ms = jS00 n S0j Lastly, the similarity between two terms t0 and t00 is computed as follows: sfo(t0; t00) = sf(nc; lc; mc) + sf(nr; lr; mr) where the former component takes into account the sets of properties (unary predicates) P 0 and P 00 referred to t0 and t00, respectively:
nc = jP 0 n P 00j lc = jP 0 \ P 00j mc = jP 00 n P 0j and the latter component takes into account how many times the two objects play the same or di erent roles in the n-ary predicates (a role being an argument position in a predicate); in this case, since an object might play the same role in many instances of the same relation, the multi sets R0 and R00 of roles played by t0 and t00, respectively, are to be considered:
nr = jR0 n R00j lr = jR0 \ R00j mr = jR00 n R0j
Since we aim at extending this general similarity framework by considering various kinds of interpreted information, for compatibility and smooth integration in the following we will exploit the same function (1).
A lot of research has been devoted to develop and test similarity measures for
concepts in a taxonomy (a survey for WordNet can be found in [
Consider now two natural language words w0 and w00 associated, respectively, to the sets of concepts C0 and C00 in the taxonomy (due to the problem of polysemy, a word may express many concepts). Their similarity assessment must somehow combine the similarities between each pair of concepts underlying them (e.g., taking the average or maximum similarity among such pairs, or exploiting the domain of discourse). We propose the following strategy: sft(w0; w00) =
max
c02C0;c002C00
sf(c0; c00)
1 In hierarchical taxonomies, that are tree-shaped, the path connecting any node
(concept) to the root r (the most general concept) is unique. Given two concepts c0 and
c00, let < r = p01; : : : ; p0n0 = c0 > and < r = p010; : : : ; p0n000 = c00 > be their paths
to the root. Now, their closest common ancestor is uniquely identi ed, as the last
element in common in the two paths, say pk (i.e., 8i = 1; : : : ; k : p0i = p0i0 = pi). This
determines three sub-paths: the sub-path in common (< p1; : : : ; pk >) and the two
trailing sub-paths (< p0k+1; : : : ; p0n0 > and < p0k0+1; : : : ; p0n000 >). The former can be
interpreted as the common information, and the latter as the residuals, and hence
their lengths (n0 k; k; n00 k) can serve as arguments (na; la; ma) to apply the
similarity formula [
Let us now show the e ectiveness of the proposed approach. Clearly, we need
a taxonomy to be used as a background knowledge. Since manually setting up a
general taxonomy is a hard work, here we will exploit the most famous taxonomy
available nowadays, WordNet (WN) [
The proposed technique might be usefully exploited as a support to
further processing such as logic deductions or Natural Language Processing. For
instance, assuming consistency of domain among the words used in a same
context [
Real-world problems, and the corresponding descriptions, often involve numeric features, that are to be expressed in the problem formalization and handled by the inferential procedures. For instance, when describing a bicycle we would like to say that the front wheel diameter is 28 inches, or when de ning the title block in a scienti c paper we would like to say that it must be placed in a range going from 5% to 20% of the page height from the top. Let us call this kind of features (such as size, height in the above examples) numeric attributes. Clearly, to be properly handled such a kind of information needs to be suitably interpreted according to a background knowledge consisting of the mathematical models of numbers and their ordering relationships. Unfortunately, the purely logical setting ignores such a background knowledge, and considers each single value as completely unrelated to all other values. This problem has been traditionally tackled in two di erent ways. Plugging the ability to handle numeric information directly in the inference engine somehow `spoils' its behavior and adds complexity (reducing e ciency). Another solution aimed at keeping the purely logical setting, to preserve applicability of the logical representation and inference techniques, consisted in a discretization of the range of numeric values allowed for a given attribute into pre-de ned intervals, associated to corresponding symbolic descriptors (e.g., size small, size large, . . . ; position top, position middle, . . . ).
The latter option requires a pre-processing of the original descriptions to turn
all instances of numeric attributes into the corresponding discretized descriptors.
But, what is the correct number of intervals in which splitting the range of values
allowed for a numeric attribute? How to choose the cut points between intervals?
Both choices are crucial, since once it is determined even points that are very
close to each other (e.g., 4.999 and 5.001 for a cut point placed at 5) will be
considered as two completely di erent entities. Although techniques for
(semi)automatic de nition of the intervals have been proposed (e.g., [
A further, general problem is that the speci c way in which numeric information is to be handled is strictly domain-dependent: Are values 15 and 300 close or distant (and how much are they)? This question cannot be answered in general (a di erence of 285 meters might be meaningful when comparing two elds, but completely insigni cant when comparing planets according to their size). All these considerations show that, in an extended framework considering interpreted predicates and constants in addition to simple syntactic entities, the ability to handle numeric information is fundamental.
Numeric information can take the form of a single value (e.g., a speci c measurement in an observation) or of an interval (e.g., a range of allowed values in a model). Thus, the comparison technique must apply to all possible combinations thereof: two intervals, an interval and a value, two values. Let us start our discussion from the case of two intervals, say I0 = [i01; i02] and I00 = [i010; i020]. Two intuitive approaches are available to extract parameters l, n and m for numeric comparisons (assume, without loss of generality, that i01 i020): 1. considering the distance between the interval extremes: n = ji010 i01j, m = ji020 i02j and l = min(i02; i020) max(i01; i010) if non-negative (or 0 otherwise)3. 2. considering the intervals as sets, and exploiting set operators: l = jjI0 \ I00jj would be the width (expressed as jj jj) of the overlapping part, and n = jjI0 n I00jj; m = jjI00 n I0jj their symmetric di erences, respectively.
The behavior of the two candidate approaches on a set of sample intervals is shown in Table 2. Overall, both approaches seem reasonable. As expected, their outcome is the same for partially overlapping intervals, so that case is not a discriminant to prefer either over the other. Di erent behavior emerges in the cases of disjoint intervals or of inclusion of intervals. In the former, the extreme-based approach ensures more distinction power, because the distance between the intervals is taken into account. While this behavior seems intuitive (the farther two intervals, the more di erent they are), on the other hand, in the case of an interval being a sub-interval of the other it is not. Indeed, the set-based approach charges the whole di erence to the residual of the larger interval, which complies with the intuition that it has more `di erent stu ' that the other does not have; conversely, the extreme-based approach splits such a di erence on both parameters n and m, resulting in a smaller similarity value.
Both strategies can be straightforwardly applied also to the comparison of an interval to a single value, considered as an interval in which the two extremes coincide. In this case one gets always l = 0, and partial overlapping never happens. Thus, the features of the two approaches become more evident, as shown in 3 This solution does not take into account the actual distance between the two intervals when they are disjoint, but modifying the function to take into account this distance as a negative value would spoil uniformity of the approach and make the function de nition more complex.
When comparing two values, the set-based approach returns maximum uncertainty about their similarity (0.5) due to all parameters being zero, and hence it is not applicable. The extreme-based approach evaluates their similarity according to how close to each other they are on the real-valued axis, but loses expressive power (because any pair of values yields n = m), and has the additional drawback that when comparing a value to itself it yields n = l = m = 0 and hence similarity 0.5 (whereas we would expect to get 1 as a perfect matching). Thus, a di erent approach is needed, that should be independent of the di erent ranges of values used in the speci c domain (e.g., the range for describing the length of a pen is incomparable to that for describing the height of a It is clearly symmetric. When the di erence between the two values approaches zero it approaches 1, and becomes actually 1 for v1 = v2, as expected (di erently from the general case, one is sure that two equal values denote exactly the same entity). As long as the di erence increases, the function monotonically approaches 0, but never reaches that value (according to the intuition that a larger di erence can be always thought of, requiring a smaller similarity value). The rate at which 0 is approached decreases as long as the di erence takes larger and larger values, consistently with the intuition that for very large distances one does not care small variations. Of course, if the descriptions are consistent, only values referred to the same kind of entities/attributes will be compared to each other, and hence the corresponding ranges of similarities should be consistent and comparable to each other. Some sample comparisons between single values are reported in Table 4 (both the speci c strategy and the extreme-based one are symmetric). As desired, identity of values yields similarity 1, and wider distances among the two values result in smaller similarity values (independently of the actual values).
Summing up, a speci c strategy is needed when comparing two values, while (1) can be used when at least an interval is involved. The set-based strategy is better in the case of an interval or value being included in another interval, because it better ts the spirit of the similarity function parameters. Conversely, in the case of disjoint intervals the extreme-based strategy is able to consider the actual distance from the interval and/or value extremes, which a ects the residual parameters. Both strategies are equivalent in the case of partially overlapping intervals. Overall, a cooperation of the three strategies is desirable: a deeper empirical study is planned as future work, to establish if and how a smooth combination thereof can be obtained, ensuring comparable similarity assessments among the di erent approaches (e.g., the similarity for two distinct values should not be larger than the similarity between a value and an interval it belongs to).
We can now discuss where to embed the new similarity perspectives in the overall First-Order Logic similarity framework. Since taxonomic and numeric predicates represent further information about the objects involved in a description, in addition to their properties and roles, term similarity is the proper component to be extended:
sfo(t0; t00) = sf(nc; lc; mc) + sf(nr; lr; mr) + sft(t0; t00) + sfn(t0; t0) where the components can be weighted di erently if needed, and the additional components express the taxonomic and numeric similarity associated to the two terms, as speci ed above. Of course, we assume that there is some way to distinguish taxonomic and numeric predicates from ordinary ones, so that they can be speci cally handled by the procedures. 5.1
To the best of our knowledge, there is no other attempt in the literature to mix in
a single similarity framework all these di erent kinds of information (relational,
taxonomic, and numeric). As to each kind taken separately:
{ There are a few proposals to assess similarity between rst-order logic
descriptions, which were compared in [
Motivations for developing the taxonomic and numeric similarity techniques proposed in this paper came both from the above mentioned advantages over previous proposals, and from the need to adopt the same similarity formula as the general framework for the sake of consistency. Di erently from the taxonomic case, the solution for numeric information required di erent approaches, depending on the overlapping situation between intervals, and a speci c formula for the case of single values, to suitably capture the peculiarities of each possible case.
In the proposed solution, the structural information conveyed by the relationships in the rst-order logic descriptions is exploited to constrain possible terms associations, and then the similarity between terms is used to ne-tune such associations and determine the overall similarity between those descriptions. Speci cally, taxonomic and numeric information takes the form of additional attributes of the terms (representing objects) in the rst-order logic descriptions under comparison, and hence contributes (along with their properties and roles as expressed by traditional logic predicates) to assess their similarity. 5.2
As an example involving taxonomic similarity, consider Natural Language Processing. Although much more computationally demanding than traditional simple bag-of-word approaches, techniques that take into account the syntactic structure of sentences are fundamental to fully capture the information they convey. Reporters know very well that, swapping subject and object in a sentence like \The dog bit the man", dramatically changes the appeal of the underlying news. The syntactic structure and relationships among discourse components in sentences can be represented by atoms in FOL Horn clauses, but it is not su cient. For instance, the following sentences: 1. \The boy wants a small dog" 2. \The girl desires a yellow canary" 3. \The hammer hits a small nail" structurally share the same grammatical pattern, thus no hint is available to assess which is more similar to which. Even worse, sentence 1 would appear to be closer to sentence 3 than to sentence 2, due to the presence of word `small', while it is clear that 1 and 2 are conceptually the most similar to each other as soon as one considers that `boy' and `girl' are two young persons, `to want' and `to desire' are synonyms and `dog' and `canary' are two pets. But taxonomic information is needed to know this.
For demonstration purposes, let us consider a simpli ed structural description language for natural language sentences: subj(X,Y) : Y is the subject of sentence X pred(X,Y) : Y is the predicate of sentence X dir obj(X,Y) : Y is the direct object of sentence X ind obj(X,Y) : Y is the in direct object of sentence X noun(X,Y) : Y is a noun appearing in component X of the sentence verb(X,Y) : Y is a verb appearing in component X of the sentence adj(X,Y) : Y is an adjective appearing in component X of the sentence adv(X,Y) : Y is an adverb appearing in component X of the sentence prep(X,Y) : Y is a preposition appearing in component X of the sentence Additionally, each noun and verb in the sentence is described by a taxonomic predicate expressing the corresponding concept (or word), while other properties (including adjectives and adverbs) are expressed by ordinary unary predicates4. For the three sentences reported above one gets: 4 WordNet de nes heterarchies for noun and verbs, but adopts di erent representation structures for adjectives and adverbs. We are currently working to extend the proposed similarity strategy to handle those structures, as well. s1 = sentence(s1) :- subj(s1,ss1), pred(s1,ps1), dir obj(s1,ds1), noun(ss1,nss1), boy (nss1), verb(ps1,vps1), want (vps1), adj(ds1,ads1), small(ads1), noun(ds1,nds1), dog (nds1). s2 = sentence(s2) :- subj(s2,ss2), pred(s2,ps2), dir obj(s2,ds2), noun(ss2,nss2), girl (nss2), verb(ps2,vps2), desire (vps2), adj(ds2,ads2), yellow(ads2), noun(ds2,nds2), canary (nds2). s3 = sentence(s3) :- subj(s3,ss3), pred(s3,ps3), dir obj(s3,ds3), noun(ss3,nss3), hammer (nss3), verb(ps3,vps3), hit (vps3), adj(ds3,ads3), small(ads3), noun(ds3,nds3), nail (nds3). where taxonomic predicates are shown in italics.
Syntactically, the generalization between s2 and both s1 and s3 is: sentence(X) :- subj(X,Y), noun(Y,Y1), pred(X,W), verb(W,W1), dir obj(X,Z), adj(Z,Z1), noun(Z,Z2). while the generalization between s1 and s3 is: sentence(X) :- subj(X,Y), noun(Y,Y1), pred(X,W), verb(W,W1), dir obj(X,Z), adj(Z,Z1), small(Z1), noun(Z,Z2). so that the latter pair, having in the generalization an additional literal with respect to the former pairs, would get a larger similarity value, in spite of the very di erent content. Using WordNet, the similarity between words is: boy-girl = 0.75 boy-hammer = 0.436 girl-hammer = 0.436 want-desire = 0.826 want-hit = 0.361 desire-hit = 0.375 yellow-small = 0.563 small-small = 1 dog-canary = 0.668 dog-nail = 0.75 canary-nail = 0.387 which, embedded in the overall clause similarity computation, overcomes the wrong similarity assessment according to syntactic comparisons only, and xes it neatly assigning to the rst two sentences the largest similarity value (also in spite of the odd `dog'-`nail' similarity)5:
fs(s1,s2) = 1.770 fs(s1,s3) = 1.739 fs(s2,s3) = 1.683 5.3
As regards numeric information, the values/intervals appearing as predicate arguments are by themselves su cient to identify it. Without loss of generality we can assume that numeric attributes (those associating a numeric value to a given entity) apply to single terms in the overall description, and are represented by binary predicates a(t; v) meaning that \object t has (numeric) value v for attribute a". The case of relationships associated with numeric information (e.g., the weight of arcs in a graph), can be handled by reifying the relationship in a term and then associating the value to the new term (e.g., arc weight(n1; n2; v) would become arc(n1; n2; a); weight(a; v)). 5 All similarities agree with intuition, except the pair dog-nail that gets a higher similarity value than dog-canary. This is due to the interpretations of `dog' as \a hinged catch that ts into a notch of a ratchet to move a wheel forward or prevent it from moving backward" and `nail' as \a thin pointed piece of metal that is hammered into materials as a fastener".
A full evaluation of the numeric similarity strategy would require a dataset involving numeric attributes and including both intervals and speci c values. Unfortunately, the available datasets usually ll each numeric attribute with a single number expressing its value for the object being described, while intervals are typically exploited in general models rather than in observations. Thus, in this work we will evaluate only the comparison of speci c values embedded in the overall structural similarity. We are currently working at building datasets including both intervals and speci c values, and an extended evaluation of the full- edged numeric similarity strategy is planned as future work. A good testbed for assessing numeric similarity performance is the supervised clustering task: after hiding the class speci cation from the examples, we provide the resulting observations to a standard k-means algorithm and ask it to split the whole dataset into di erent groups based on the similarity measure described in previous sections. Then, the performance of the resulting clusters is checked according to the purity measure (i.e., the percentage of correct association in the best overlapping between the clusters and the actual classes that were hidden), that can be considered as the counterpart of accuracy in supervised learning.
Our experiment concerns the problem of distinguishing documents according
to their layout description, using a dataset made up of 353 examples of
scienti c papers from 4 di erent series: Elsevier journals, Springer-Verlag Lecture
Notes (SVLN), Machine Learning Journal (MLJ), Journal of Machine Learning
Research (JMLR). The descriptions involve both relational predicates (for the
mutual position and alignment among layout blocks) and attribute-value
descriptors for each layout block. In particular, 4 numeric attributes are present:
horizontal/vertical position of the block in the page, and width/height thereof.
The expectation is that these descriptors are very signi cant to class
discrimination. Previous applications on this dataset [
It clearly emerges which clusters represent which classes, due to a
predominance of the corresponding elements: Cluster 1 corresponds to Elsevier,
including 50 out of its 61 correct elements (plus 2 wrong elements from other classes),
Cluster 2 corresponds to MLJ, Cluster 3 corresponds to JMLR and Cluster 4
to SVLN. Given this correspondence, the purity of each cluster with respect to
the associated class can be computed, as the ratio of elements from that class
over the total elements in the cluster. There are 51 errors overall, yielding an
overall 85.55% accuracy, that increases to 87.61% taking the average accuracy
of the various classes/clusters. Compared to the 92.35% purity reported in [
Results of additional clustering tasks, each pairwise involving two of the four classes in the dataset, show purity values ranging between 81.25% (for the MLJSVLN pair) and 98.82% (for the JMLR-SVLN pair), with an average of 89.99%. 6
Horn clause Logic is a powerful representation language for automated learning and reasoning in domains where relations among objects must be expressed to fully capture the relevant information. While the predicates in the description language are de ned by the knowledge engineer and handled only syntactically by the interpreters, they sometimes express information that can be properly exploited only with reference to a taxonomic (concepts or words) or numeric (intervals and/or single values) background knowledge in order to capture unexpressed and underlying relationships among the concepts described.
This paper de ned speci c strategies for assessing similarity between these two kinds of information, discussed their integration as an extension of a general framework for assessing the similarity between Horn clauses, and reported experimental results that show the e ectiveness of the proposal. Experiments on the taxonomic component concerned Natural Language Processing using a state-of-the-art taxonomy as a background knowledge, while experiments on the numeric component concerned a clustering task on a typical dataset mixing relational and numeric information.
As to the taxonomic component, future work will concern ne-tuning of the similarity computation methodology by exploiting additional taxonomic relationships (other than hypernymy). As to the numeric component, future work will concern deeper empirical evaluation of the proposed approaches in the case of intervals, and the smooth cooperation of the di erent sub-strategies de ned in this paper. As to the integration of the new components in the general similarity framework, we plan to study the relative importance of the single components for term similarity evaluation (properties, roles, taxonomy, numeric), to determine suitable weighting schemes for them. Then, experiments on the application of the framework to other real-world problems are planned. Finally, another research direction concerns the exploitation of the proposed technique as a support to re nement operators for incremental ILP systems.