Patent Valuation Using Di erence in ALE N

Abstract

In this paper we present an approach for patent claim comparison based on the di erence operator in description logics. The claims are represented using ALEN . An algorithm computing the di erence between two ALEN concept descriptions is proposed and its usefulness for patent application valuation is described by means of some simple examples.

Introduction

More and more, patent material is made available in electronic format, and most of the time in textual form. Examples of such services are the European patent O ce (EPO) [ 1 ] and the United States Patent and Trademark O ce (USPTO) [ 3 ]. The need for a formal speci cation of the patent content arose recently to help retrieval, examination and classi cation of patent applications.

In this context one needs to evaluate the innovative degree of a patent appli

cation. A claim is the part of a patent application where the inventor speci es the invention attributes and its features, de ning what can be protected by the patent law. The aim is to show the non-obviousness to a person with basic domain skills and the novelty of the application compared to the state of the art.

Patent claims are described in natural language. Terms used in the claims

must nd clear support in the preceding description part of the patent application such that the meaning of a term is clearly speci ed. Previous work had attempted to represent patent material using OWL ontologies [ 7, 15 ].

Statistical tools performing patent application evaluation are based on a set

of parameters provided by the user. Based on those parameters, the overall score of a patent application is calculated.

In this paper we present a more formal approach for patent claim comparison based on description logics1. Patent application claims are formally represented as concept descriptions. When comparing two applications, the di erences need to be pinpointed in order to prove the novelty. We compute this di erence by using the di erence operator and return the result to the user. The result must be intuitive and easy to understand in order to help the user construct his argumentation. 1 This work has been partially supported by the Fact Screening and Transformation Project (FSTP) funded by the Teles Pri AG: www.fstp-expert-system.com

The di erence operator computes the part of a concept that is not contained

into another one. The di erence operator has been de ned in [ 14 ] as being the most general description that can be added to the second operand to obtain equivalence with the rst. A second de nition of the di erence involving a syntactic criteria for minimality has been introduced in [ 4 ].

In our context we need to describe existential, universal and numerical re

strictions. The di erence operator has been investigated for description logics allowing either numerical restrictions [ 12 ] or existential restrictions [ 4 ]. We propose an algorithm for ALE N based on the structural characterization of subsumption for ALE N [ 10, 11 ].

The paper is organized as follows: in section 2, we give the formal de nitions of the di erence operator and discuss the motivation for our choice. Section 3 recalls useful results for ALE N and introduces some notations. In section 4 we provide an algorithm for computing the di erence in ALE N . Some examples of patent claims comparison are given in section 5 and Section 6 concludes the paper. 2

Operator Choice

The need for providing parts of a description that are not contained in another one has been motivated by di erent applications and di erent de nitions exist with their advantages and drawbacks.

Informally speaking, the di erence between two concept descriptions is the

information contained in the rst description and not in the second. The difference operator allows to remove from a given description all the information contained in another description. The di erence operation between two concept descriptions was rst introduced by Teege [ 14 ].

De nition 1. (semantic di erence) The di erence between two concept descriptions C and D with C v D is given by

C

D := maxfE j E u D

Cg where max is de ned with respect to subsumption.

Later, the work in [9, 4] proposed a re nement of this de nition by allow

ing the di erence between incomparable descriptions (i.e. D is not required to subsume C) and taking the syntactic minimum (w.r.t. a subdescription ordering

d) instead of a semantic maximum.

De nition 2. (syntactic di erence) The di erence between two incomparable concept descriptions C and D is de ned as

C

D := minfE j E u D

C u Dg where min is de ned with respect to a so-called subdescription ordering (denoted by d), used to compare syntactical structures that we recall in the next de nition.

De nition 3. (Subdescriptions) Let C be an ALE N -concept description, Cb is a subdescription of C ( Cb d C) i , 1. Cb = ?; or 2. Cb is obtained by removing from the top-level of C: >, concept names, number restrictions, value restrictions, existential restrictions. For the remaining restrictions 8r:E or 9r:E, replace the concept description E with a subdescription of E.

As an example, consider the ALE N -concept description C:

P u P u 8r:P u 9r:(P u 9r:Q)u 3r

A possible subdescription:

Cb = P u 8r:P u 9r:(9r:Q)u 3r is obtained from C by removing P from the top-level of C and P from the subexpression 9r:(P u 9r:Q). Note that Cb is equivalent to C and there exists no subdescription of Cb owning this property. Cb is the minimal subdescription which is equivalent to C.

In [12], the authors de ned a semantic di erence for ALN . They also compare

the semantic and syntactic variants and state that the two approaches di er mainly on the bottom handling. Indeed, the bottom decomposition leads to more than one result for the semantic di erence. On the other hand, the syntactic di erence always generates a unique result that is a subdescription of the input description and hence more intuitive and comprehensive for the user.

Another operator called \concept abduction\ has been introduced to provide

an explanation for matchmaking results in an e-marketplace. Abduction was rst de ned for ALN [ 5 ] and has been recently extended to a more expressive DL

SH, using tableau calculus [13].

This operator does not require subsumption between the concept descriptions

neither and thus is more general than the semantic di erence. As stated in [ 6 ], the result of the di erence is included in the set of solutions of a CAP.

In our context, we chose to use the syntactic di erence for three reasons: 1. It does not require subsumption between the concept descriptions being compared, which is more realistic in real world applications,

2. it generates a unique result which is a syntactic variation of the input and

hence more intuitive for the user,

3. when the inputs are free from insatis able subexpressions the result is equivalent to the semantic di erence.

Preliminaries

In this section we recall some results for subsumption in ALE N and de ne some notations that will be useful to derive the di erence algorithm.

The normal form of an ALE N concept description is obtained by applying the following transformation rules: { ( mr) u ( nr) ! ( nr) if n { ( mr) u ( nr) ! ( nr) if n { 8r:C u 8r:D ! 8r:(C u D).

m, m, and

To access the di erent component of a concept description, we will use the following notations: { prim(C) denotes the set of concept names and the bottom concept occurring on the top-level of C, { infr(C) = ( nr) if there exists a number restriction of the form ( nr) on the top-level of C, infr(C) = > otherwise, { supr(C) = ( nr) if there exists a number restriction of the form ( nr) on the top-level of C, supr(C) = > otherwise, { minr(C) = maxfk j C v ( kr)g, { maxr(C) = minfk j C v ( kr)g, { 8r(C) = E if there exists a value restriction 8r:E on the top-level of C; 8r(C) = > otherwise, { 9r(C) = fC0 j 9r:C0occurs on the top-level of Cg.

For the sake of clarity, we will assume that the set NR is reduced to the role r.

The algorithm can be easily generalized to arbitrary sets of role names.

The di erence algorithm is based on the structural characterization of sub

sumption in ALE N given in [ 10 ]. In the sequel we present the intuitions used to compute induced concept descriptions and recall the structural subsumption characterization. We also introduce some notations that we will use in the difference algorithm.

The main issue when dealing with ALE N is to compute the "non-trivial"

concept descriptions subsuming a concept description C; such concepts do not appear in the top-level of C and are called "induced". Let us recall this process by means of examples.

Number restrictions: They can be induced if two existential restrictions involve disjoint concepts. For example, if C := 9r:P u 9r::P then 2r is induced by C.

Let us note the induced number restrictions as follows: minr (C). Note that if minr (C) = k, we have C v kr which means that minr (C) is taken into account in minr(C) de ned above.

Existential restrictions: Due to -number restrictions, if the number of existential restrictions in the toplevel of a concept C is greater than the -number restriction, those existential restrictions must be merged.

For example, if we have:

C := 9r:(P u A) u 9r:(P u B) u 9r:(:P u A) u 9r:Q u 9r::Qu 2r; the merging process results in new concepts descriptions where the only consistent ones are: 9r:(P u Q u A u B) u 9r:(:P u :Q u A) 9r:(P u :Q u A u B) u 9r:(:P u Q u A) 2r; and 2r: In [ 10 ], each merging is represented by a mapping leading to a concept C and the set of mappings is denoted by r(C). The mappings in r(C) are required to obey the following conditions: 1. (i) 6= ; for all 1 i n; 2. S1 i n (i) = f1; :::; mg and (i) \ 3. dj2 (i) Cj u 8r(C) 6 ? for all 1 i (j) = ; for all 1 n, i < j n; where n := minfmaxr(C); j 9r(C) jg and m :=j 9r(C) j.

In our example, this set consists of two mappings 1 and

two concepts C 1 and C 2 above with C C 1 t C 2 .

The set of C0 such that 9r:C0 in C for all mappings is noted as follows:

2 leading to the

9r (C) := [ 2 r(C) 9r(C )

For our example we obtain:

9r (C) := fP u Q u A u B; :P u :Q u A; P u :Q u A u B; :P u Q u Ag In case 9r(C) = ; (there is no existential restriction on the top level of C) one needs to take into account the -restrictions together with value restrictions to deduce non-trivial existential restrictions. Let us illustrate the case on the following concept:

D := ( 2r) u 8r:(A u B): The instances of D have at least two r-successors and due to the value restriction we can deduce that D v 9r:(A u B).

This concludes the existential restrictions case.

Value restrictions: It is clear from the former example that every instance of C has exactly two r-successors, in that case one can deduce from the existential restrictions in C 1 and C 2 that all r-successors belong to A and thus that the value restriction

8r:A is induced by C.

This deduction can be performed only when all r-successors are known and it is represented by the condition:

maxr(C) = minr (C):

The second case where a value restriction can be induced is when maxr(C) = 0 then C v 8r:?.

Syntactic Di erence between ALE N -Concept

Descriptions

The algorithm computing the di erence between two ALEN -concept descriptions C and D is depicted in gure 1. We extended the algorithm proposed in [ 9 ] to compute the di erence between two ALE-concept descriptions.

Before going into detail about the algorithm, and as it is based on the structural characterization of the subsumption [10], let us recall the conditions for each kind of conjunct occurring on the top level of the concept descriptions.

Theorem 1. Let C, D be two ALEN -concept descriptions with 9r(C) = fC1; :::; Cng. Then C v D i C ?, or D >, or the following conditions hold: 1. prim(C) prim(D), 2. maxr(C) maxr(D), 3. minr(C) minr(D), 4. for all D0 2 9r(D) it holds that (a) 9r(C) = ;; minr(C) 1, and 8r(C) v D0; or (b) 9r(C) 6= ;; and for each 2 r(C), there exists C0 2 9r(C ) such that

C0 u 8r(C) v D0. 5. if 8r(C) 6 >, then (a) maxr(C) = 0; or (b) minr(C) < maxr(C) and 8r(C) v 8r(D); or (c) 0 < minr(C) = maxr(C) and 8r(C) u C0 v 8r(D) for all C0 2 9r(C).

According to the de nition of the di erence (c.f De nition 2), the output of the algorithm must verify:

ComputeDi (C; D) u D C u D

Let start with concept names and numerical restrictions. One can easily verify conditions 1. 3. of Theorem 1:

The set of primitive concepts prim(ComputeDi (C; D) u D) is equal to prim(ComputeDi (C; D)) [ prim(D), which by de nition is equal to (prim(C)nprim(D)) [ prim(D). This is again equal to prim(C) [ prim(D), the set of primitive concepts of (C u D).

For maxr(ComputeDi (C; D) u D), we distinguish two cases: it is equal to maxr(D), when maxr(C) maxr(D) and to maxr(infr(C) u D), when maxr(C) < maxr(D). Both cases are equal to maxr(C u D).

Analogously to the precedent case, for minr(ComputeDi (C; D) u D) we have

two cases: equal to minr(D) when minr(C) minr(D) and to minr(supr(C)u

D) when minr(C) > minr(D). Which again are equal to minr(C u D).

Require: Two ALEN -concept descriptions C and D in ALEN -normal form Ensure: ComputeDi (C; D) 1: if C u D ? then 2: ComputeDi (C; D) := ? 3: else 4: ComputeDi (C; D) := uA2prim(C D)A u infr(C D) u supr(C D) u 8r:ComputeDi (8r(C); 8r(D) u 8r(C u D)) u dE2Er0 9r:E, where the value restriction is omitted in case ComputeDi (8r(C); 8r(D) u 8r(C u D)) > and: prim(C-D) := prim(C)nprim(D); infr(C-D) = >; maxr(C) maxr(D);

infr(C); maxr(C) < maxr(D); supr(C-D) = >; minr(C) minr(D);

supr(C); minr(C) > minr(D); 8r(E) = <8 ?>;; maxr(E) = 0; minr(E) < maxr(E); : lcs(f8r(E) u E0 j E0 2 9r(E)g); 0 < minr(E) = maxr(E);

Er0 is computed as follows: Let Er := 9r(C) = fC1; :::; Cng and we de ne CnE as being C without the conjunct 9r:E. 5: for i = 1 to n do 6: if (i) r(CnCi u D) 6= ; and there exists D0 2 9r((CnCi u D) ) forall 2 r(CnCi u D) with 8r(C) u 8r(D) u D0 v Ci; or (ii) r(CnCi u D) = ; and minr(C u D) 1 and 8r(C) u 8r(D) v Ci, then 7: Er := ErnfCig; 8: end if 9: end for 10: Er0 = fE j E 2 Erg where E := ComputeDi (E; 8r(C) u 8r(D)). 11: end if Let us now consider the value restrictions. In case 0 < minr(C u D) = maxr(C u D), a value restriction 8r(C u D) can be deduced from C u D, which is the least common subsumer of all the existential restrictions appearing in 9r(C u D).

Let us illustrate this case by an example.

Cex1 := 9r:(P u A) u 9r:(P u B) u 9r::Q u 8r:(A u B);

Dex1 := 9r:(:P u A) u 9r:Q u ( 2r): As demonstrated in section 3, the merging of existential restrictions in Cex1 u Dex1 induces the value restriction 8r:A. The value restriction of the di erence

C D is then

ComputeDi (8r(C); 8r(D) u 8r (C u D)) = ComputeDi (A u B; A) = B One can verify condition 5(c) of Theorem 1, namely that B u C0 v A u B for all C0 in the set of merged existential restrictions 9r (Cex1 u Dex1) (c.f. the example in Section 3).

Let us now illustrate the two cases for existential restrictions by means of examples.

To illustrate case (i) let us take the following descriptions:

Cex2 := 9r:(P u A u B)u

2r;

Dex2 := 9r:(P u A) u 9r:(P u B) u 9r:(:P u A) u 9r:Q u 9r::Q: from (CenxC21 u Dex2) 2. We then have C1 = P uAuB subsumes P uQuAuB from (CenxC21 uDex2) 1 and P u:QuAuB ComputeDi (Cex2; Dex2) = 2r:

Finally we illustrate case (ii) with the following example

Cex3 := P u 9r:(A1 u A2) u ( Dex3 := 8r:(A1 u A2 u A3): 3r); ComputeDi (Cex3; Dex3) = P u ( 3r)

While 9r:(A1 u A2 u A3) can be induced from 8r:(A1 u A2 u A3) u (

one can verify that 3r), ComputeDi (Cex3; Dex3) u Dex3 P u ( 3r) u 8r:(A1 u A2 u A3) v P u ( v P u ( 3r) u 9r:(A1 u A2 u A3) u 8r:(A1 u A2 u A3) 3r) u 9r:(A1 u A2) u 8r:(A1 u A2 u A3) Cex3 u Dex3

The case w is obvious.

The next lemma proves that the algorithm returns a di erence that respects the condition of the di erence operator (Section 2). The proof can be found in our technical report [8].

Lemma 1. Let C, D be two ALE N -concept descriptions in ALE N normal form. Then, ComputeDi (C; D) u D C u D.

Application to Patent Claims Comparison

In this section we are going to illustrate the di erence on some simple patent examples.

Example 1. Suppose we have an application for a chair with only one leg having a seat made only from a light material. The corresponding concept description is the following:

= 1hasLeg u 9hasSeat:(8hasM aterial:Light); that we need to compare to a previous patent describing a chair with three legs and having one seat made of light wood, given by the description = 3hasLeg u 9hasSeat:(8hasM aterial:(W ood u Light)):

The algorithm returns

the application.

1hasLeg which corresponds to the speci c part of

Example 2. Let us consider a patent application for a watch with two types of displays or more that are all bright. The corresponding description is: >= 2hasDisplay u 8hasDisplay:Bright; to compare to a watch with an analogue and a non analogue display described as:

9hasDisplay:Analogical u 9hasDisplay::Analogical:

The di erence is 8hasDisplay:Bright. Indeed, we can deduce the numeri

cal restriction >= 2hasDisplay from the second concept description while the existential restrictions involve disjoint concepts. 6

Conclusion

In this paper, we have investigated the problem of computing the syntactic difference in ALE N . This work was motivated by an application in the context of patent applications valuation. In this context one needs to compare the claims of the patent with previous patents solving a similar problem. The textual descriptions of the claims can be described in a formal way using ALE N -concept descriptions. The di erence operator provides the user with the parts that are contained in his application and not in the state of the art. Our aim is not to provide a decision-making tool regarding the novelty of a patent application, but rather a tool that can help in pinpointing the di erences and assist the user in constructing his argumentation.

We are implementing a prototype of the di erence algorithm based on the DL reasoner HermiT [2] for the subsumption test. A direction for Future work would be to investigate the decision making process based on the results returned by the di erence and empirical rules derived from experts decisions.

References

1. The European Patent O ce website: http://www.epo.org

2. The Hermit OWL Reasoner website: http://hermit-reasoner.com

3. The United States Patent and Trademark O ce website : http://www.uspto.gov/

4. Brandt , S. , Kusters , R. , Turhan , A.Y. : Approximation and di erence in description logics . In: T.Dean (ed.) Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR2002) . pp. 203 { 214 . Morgan Kaufmann, San Francisco, CA ( 2002 )

5. Colucci , S. , Noia , T.D., Sciascio , E.D. , Donini , F.M. , Mongiello , M. : Concept abduction and contraction in description logics . In: Description Logics ( 2003 )

6. Di Noia , T. , Di Sciascio , E. , Donini , F.M.: Semantic matchmaking as nonmonotonic reasoning: a description logic approach . J. Artif. Int. Res . 29 ( 1 ), 269 { 307 ( 2007 ), http://dl.acm.org/citation.cfm?id= 1622606 . 1622615

7. Giereth , M. , Koch , S. , Kompatsiaris , Y. , Papadopoulos , S. , Pianta , E. , Sera ni , L., Wanner , L. : A modular framework for ontology-based representation of patent information . In: JURIX ( 2007 )

8. Karam , N. , Paschke , A. : Patent valuation using di erence in ALEN . Tech. rep., Freie Universitat Berlin, Germany ( 2012 ), http://www.csw.inf.fu-berlin.de/publications/TR-Di Alen.pdf

9. Kusters , R.: Non-standard inferences in description logics , vol. 2100 of Lecture Notes in Arti cial Intelligence . Springer-Verlag ( 2001 )

10. Kusters , R. , Molitor , R.: Computing least common subsumers in ALEN . In: Proceedings of the 17th international joint conference on Arti cial intelligence - Volume 1 . pp. 219 { 224 . Morgan Kaufmann Publishers Inc., San Francisco, CA, USA ( 2001 ), http://portal.acm.org/citation.cfm?id= 1642090 . 1642120

11. Kusters , R. , Molitor , R. : Structural subsumption and least common subsumers in a description logic with existential and number restrictions . Studia Logica 81 ( 2 ), 227 { 259 ( 2005 )

12. Leger , A. , Rey , C. , Toumani , F. : Semantic di erence in ALN . In: Description Logics ( 2007 )

13. Noia , T.D., Sciascio , E.D. , Donini , F.M.: A tableaux-based calculus for abduction in expressive description logics: preliminary results . In: Description Logics ( 2009 )

14. Teege , G.: Making the di erence: a subtraction operation for description logics . In: Doyle, J. , Sandewall , E. , Torasso , P. (eds.) KR'94: Principles of Knowledge Representation and Reasoning , pp. 540 { 550 . Morgan Kaufmann, San Francisco, California ( 1994 )

15. Wanner , L. , Baeza-Yates , R. , Brugmann, S. , Codina , J. , Diallo , B. , Escorsa , E. , Giereth , M. , Kompatsiaris , Y. , Papadopoulos , S. , Pianta , E. , Piella , G. , Puhlmann , I. , Rao , G. , Rotard , M. , Schoester , P. , Sera ni , L., Zervaki , V. : Towards contentoriented patent document processing . World Patent Information 30 ( 1 ), 21 { 33 ( 2008 )