Ranking Structured Documents: A Large Margin Based Approach for Patent Prior Art Search

1 Introduction

Patents protect intellectual property rights by granting the invention's owner (or his/her assignee) the right to exclude others frommaking, using, selling, or importing the patented invention for a certain number of years, usually twenty years, in exchange for the public disclosure of the details of the invention. Like any property right, patents may be transacted (e.g., sold, licensed, mortgaged, assigned or transferred) and therefore they have economic value. For a patent to be granted, the patent application must meet the legal requirements related to patentability. In particular, in order for an invention to be patentable, it must be novel. Patent applications are subject to official examination performed by a patent examiner to judge its patentability, and in particular its novelty. In most patent systems prior art constitutes information that has been made available to the public in any form before the filing date that might be relevant to a patent's claims of originality. Previously patented inventions are to a great extent the most important form of prior art, given that they have already been through the patent application scrutiny.

The decision by an applicant to cite a prior patent is arguably "tricky" [Lampe, 2007]: on one hand, citing a patent can increase the chance of a patent being accepted by the United States Patent and Trademark Office (USPTO), if it shows a "spillover" from the previously granted patent; on the other hand, citing a prior patent may invalidate the new patent if it shows evidence of intellectual property infringement. As a result, some applicants choose to cite only remotely related patents, even if they are aware of other more similar patents. It is thus part of the responsibility of the USPTO examiner to add patent citations, beyond those provided by the applicant. This is important since more than 30% of all patent applications granted from 2001 to 2007 actually have zero applicant citations. However, this is also a tedious procedure often resulting in human error, considering the huge amount of patents to be possibly cited and the fact that different examiners with different expertise backgrounds are likely to cite different sets of patents for the same application. Furthermore, while applicants tend to cite patents that facilitate their invention, denoting to some extent spillovers from a patent invention, examiners tend to cite patents that block or limit the claims of later inventions, better reflecting the patent scope and therefore representing a better measure of the private value of a patent.

We focus on the problem of automatically ranking patent citations to previously granted patents: given a new patent application, we are interested in identifying an ordered list of previously granted patents that examiners and applicants would consider useful to include as prior art patent citations.

In recent years several margin based methods for document ranking have been proposed, e.g., [Herbrich et al., 2000; Nallapati, 2004; Cao et al., 2006; Joachims, 2002; Chapelle et al., 2007; Yue et al., 2007]. For example, in the approach by [Herbrich et al., 2000; Nallapati, 2004] the ranking problem is transformed into a binary classification problem and solved by SVM. [Cao et al., 2006] considers different loss functions for misclassification of the input instances, applied to the binary classification problem; [Joachims, 2002] uses click through data from search engines to construct pair-wise training examples. In addition, many other methods learn to optimize for a particular performance measure such as accuracy [Morik et al., 1999], ROC area [Herschtal and Raskutti, 2004; Carterette and Petkova, 2006], NDCG [Burges et al., 2005; 2006; Chapelle et al., 2007] and MAP [Yue et al., 2007].

Note that the patent prior art search problem differs from the traditional learning to rank task in at least two important ways. Firstly, in learning to rank we measure the relevance of query-document pairs, where a query is usually a short sentence-like structure. In patent ranking, we are interested in patent-patent relevance, where a patent is a full document much longer in length than a normal query. We will also see in the experiment section that treating a document as a long query often results in inferior performance. Secondly, in the case of patent prior art search, we have two entities, namely the examiner and applicant, who decide what patents to cite for a new application. As we mentioned above, the differences in their citation behaviors are not only a matter of level of relevance, but also of strategy.

To address the various issues concerning patent prior art search, we propose a large-margin based method, SVM Patent Ranking (SVMPR), with constraint set directly capturing the different importance between citations made by examiners and citations made by applicants. Our approach combines patent-based knowledge features with meta-score features, based on several different ad-hoc Information Retrieval methods. Our experiments on a real USPTO dataset show that SVMPR performs on average 30%-40% better than other state-of-the-art ad-hoc Information Retrieval methods on a wireless technology patent dataset, in terms of the NDCG measure. To the best of our knowledge, this is the first time a machine learning approach is used for automatically generating patent prior art citations, which is traditionally handled by human experts.

2 Numerical Properties of Patent Citations

From January 1, 2001 to the end of 2007, the USPTO has granted 1,263,232 patents. The number of granted patents (per year) is displayed in the left plot of Figure 1. We observe a steady and slow increase in the number of patents granted per year from 2001 (∼180,300 patents) to 2003 (∼187,132 patents), and then a steep decrease until the all-time low of ∼157,866 in 2005. Interestingly there is a sharp increase in the number of patents in 2006, achieving the highest number to date with ∼196,593 patents.

There are obvious differences between examiner and applicant citations. (See e.g., [Alcacer and Gittelman, 2006; Sampat, 2004].) The average number of patent citations added by the examiner and applicant is presented in the middle plot of Figure 1. The average number of patent citations added by the examiner is relatively stable, ranging from 5.49 to 6.79 , while the average number of applicant citations increases significantly from 8.69 in 2001 to 15.11 in 2007. In addition, the distribution of patent citations by the applicant is extremely uneven: ∼372,372 (29.5%) patents have no applicant citations, and ∼19,388 (1.5%) patents have more than 100 applicant citations, while the number of patents with more than 100 examiner citations is only 40. The rightmost plot of Figure 1 compares the number of patents with no more than 20 citations made by the examiner, versus that made by the applicant. As clearly displayed, a large portion of the patents have 0 applicant citation, and the mode number of examiner citation is 3, with ∼134,323 patents.

3 SVMPR for Patent Ranking

3.1 Some Notations

We denote the set of patents whose citations are of interest by μ; and the set of patents that patents in μ cite, by ν.

In addition, ∀pi ∈ μ and ∀pj ∈ ν, we define the citation matrix Cwith entries Cij to be

The numerical values seem to be arbitrary here but the reason for such choices will be clear in the next section. Moreover, we denote Φ(pi, pj) as the feature map vector constructed from patents pi and pj. Details of Φ are presented in section 3.3.

3.2 SVMPR Formulation

Our model is called SVMPatent Ranking (SVMPR). It is formulated as the following large margin quadratic optimization problem with the constraint set directly capturing the specificities of patent ranking:

OPTIMIZATION PROBLEM I

where

Here Δ(pi, pj, pk) is the loss function when Cij - Cik > 0 and the learned w parameter scores less with Φ(pi, pj) than Φ(pi, pk). The magnitude of Cij -Cik represents the severity of the loss: a mistake of ranking an uncited document higher than a document cited by an examiner is more serious than ranking the same uncited document higher than some applicant cited document. If Cij - Cik ≤ 0, no loss will be incurred, and we set Δ(pi, pj , pk) to -∞ to invalidate the constraint.

The objective function (1) is the usual minimization that trades off between ‖w‖2 , the complexity of the model, and ∑ ξijk , the upper bound of the total training loss defined by Δ. λ is the tradeoff constant.

The above formulation considers all tuples (i,j,k) to ensure that examiner cited patents are ranked higher than applicant cited patents, which are again ranked higher than uncited patents, by an absolute margin "1" using the linear discriminant score wT Φ. The drawback is that it contains O(|μ||ν|2 ) constraints, which poses a challenge for any reasonable training process. In fact, we do not need to include all tuples as constraints, but rather only consider the extreme values of the ranking scores of the three different citation groups (by examiner, by applicant and not cited). Therefore, we can construct the following alternative formulation:

It is not difficult to see that the constraint set of Optimization Problem 1 implies the constraint set of Optimization Problem 2, and vice versa, since in the latter case we made the changes that the constraints only need to be satisfied at the extreme values. The advantage is obvious because this leads to a convex quadratic optimization problem with only O(|μ|) constraints. Our training algorithm will be based on this formulation.

We note that if the distinction between examiner citations and applicant citations is ignored, i.e, Cij=1 iff patent pi cites pj, OPTIMIZATION PROBLEM I can be transformed into the ordinal regression formulation in [Herbrich et al., 2000] in a straightforward way. The ordinal regression formulation would require O(|μ|2 |ν|2 ) constraints, treating each Φ(pi, pj) as an individual example; or O(|μ||ν|2 ) constraints if the examples Φ(pi, pj) are first grouped by pi. In order to differentiate examiner and applicant citations we applied the SVM multi-rank ordinal regression in [Chu and Keerthi, 2005] to our transformed problem with O(|μ||ν|) examples. Unfortunately the ordinal regression method could not handle the scale of the problem, as it fails to complete the training process within 48 hours of runtime. In contrast, our approach, SVMPR, exploits the important distinction between examiner and applicant citations, leading to the efficient formulation and training process.

After the optimization phase, we use the linear discriminant function wT Φ(p, q) to rank a new patent p against any patent q to be considered for the prior art citation. Our target ranking for p is that all examiner-cited patents are ranked higher than all applicant-cited patents, and all cited patents are ranked higher than all patents not cited. We evaluate our learned patent ranking with the target ranking by NDCG.

It is worthwhile to note that our approach is also related to the margin based methods for label ranking [Shalev-Shwartz and Singer, 2006], in which the goal is to learn an ordered preference list of labels for each instance by learning local weight vectors for each class label. In contrast, our approach is to learn a global weight vector and differentiate class labels (cited by examiner, or applicant, or not cited) by the linear discriminant score, using the patent specific feature map vectors.

3.3 Feature Map Construction

One major difference between assessing patent similarity and query-document similarity, a traditional task in IR, is that patents are full documents, which are usually significantly longer than an average query. Of course we can treat one patent as a long query, but this will not result in good performance for our task as we will see in the experiment section.

A key step in our approach for the training and testing procedure is the construction of a feature map for pairs of patents pi and pj. Intuitively, Φ(pi, pj) represents information we know about how similar pi and pj are. In our approach, Φ(pi, pj) is a column vector composed of two parts: the domain knowledge patent pair features and the meta score features.

Domain Knowledge Patent Pair Features

The domain knowledge features between patents pi and pj come from the study of patent structure without any citation information of either pi or pj. Here applicants and inventors are used interchangeably. We have 12 binary features in Φ(pi, pj) as follows:

1. Both patents are in the same US patent class; 2. Both patents have at least one common inventor (defined by same surname and first name); 3. Both patents are from the same assignee company (e.g., Microsoft, HP etc.); 4. Both patents are proposed by independent applicants (i.e, no assignee company); 5-7. First inventors of the two patents come from the same city, state or country; 8. pi's patent date is later than pj's patent date (so pi can possibly cite pj); 9-12. Both patents made 0 claims, 1-5 claims, 6-10 claims or more than 10 claims.

Meta Score Features

We also make use of ad-hoc IR methods to score the patent pairs. The scores are then changed into feature vector representation in Φ.

We used the Lemur information retrieval package 1 to obtain the scores on patent pairs by six ad-hoc IR methods: TFIDF, Okapai, Cosine Similarity and three variations of the KL-Divergence ranking method. Additional descriptions of these methods can be found in Section 4.3. Each method is essentially a scoring function ψ(q, d) ∈ Q × D ↦→ R where Q is a set of queries and D is a set of documents whose relevance to the queries is ranked by the real-valued scores. We use the patents' titles and abstracts available from the USPTO patent database to obtain the meta score features.

We can view each sentence of a patent pi ∈ μ as a query whose relevance with respect to a patent pj ∈ ν is to be evaluated. Let S be the set of all sentences from all patents in μ. We associate a binary vector ts of length 50 with each s ∈ S according to ψ(s, pj), following the representation in [Yue et al., 2007]:

where Pt(x) is the xth percentile of {ψ(q, pj) : q ∈ S}. The ts vector is a binary representation of how relevant sentence s is with respect to pj, compared to all other sentences in S. We repeat this procedure for all six ad-hoc IR methods and concatenate the results to obtain the vector ts of length 300.

Let (s1, s2, . . . , smi ) be the mi sentences of pi sorted in non-increasing order according to ψTF-IDF(s, pj). The meta score feature vector between pi and pj is defined as

In other words, Equation (3) is a weighted sum of ts from each sentence s, discounting sentences that are ranked as less relevant exponentially by ψTF-IDF . We also tried other alternative weighting schemes, such as harmonic discounting, but none of them performed empirically as well as the exponential weight discount.

Hence, the feature map Φ(pi, pj) for any pi ∈ μ and pj ∈ ν is the concatenation of the 12 knowledge domain features and Ψ(pi, pj), with a total of 312 features.

3.4 The Training Algorithm

The training algorithm of SVMPR that optimizes (2) with respect to w is an extension of Pegasos [Shalev-Shwartz et al., 2007]. Pegasos is an SVM training algorithm that alternates between a gradient descent step and a projection step. It operates solely in the primal space, and has proven error bounds. Our training algorithm is presented in Algorithm 1.

Among the four input parameters, μ and ν have the same meaning as in the previous sections; T is the total number of iterations; λ is the constant in the SVMPR formulation. In our experiments T and λ are fixed at 200 and 0.1. In general

1 Lemur Toolkit v4.5, copyright (c) 2008 University of Massachusetts and Carnegie Mellon University

Algorithm 1 SVMPR Training Algorithm

1: Input: μ, ν, T, λ 2: w0=0 3: for t = 1, 2, . . ., T do 4: A=∅ 5: for i = 1, 2, . . ., |μ| do 6: pemin=argminpj∈ν∧Cij=2wT t-1Φ(pi, pj ) 7: pamax=argmaxpj∈ν∧Cij=1wT t-1Φ(pi, pj ) 8: pamin=argminpj∈ν∧Cij=1wT t-1Φ(pi, pj ) 9: pnmax=argmaxpj∈ν∧Cij=0wT t-1Φ(pi, pj ) 10: if wT t-1(Φ(pi, pemin) - Φ(pi, pamax)) < 1 then 11: A=A ∪ (pemin, pamax) 12: end if 13: if wT t-1(Φ(pi, pamin) - Φ(pi, pnmax)) < 1 then 14: A=A ∪ (pamin, pnmax) 15: end if 16: end for 17: wt=(1- 1t )wt-1+ 1 λt|μ| P(pj ,pk)∈A(Φ(pi, pj ) - Φ(pi, pk)) 18: if ‖wt‖ > 1 √λ then 19: wt= 1 √λ wt ‖wt‖ 20: end if 21: end for 22: Output: wt with the minimum validation error.

the performance is not sensitive to any reasonable λ setting. Lines 6-9 calculate the extreme values of the discriminant function wT Φ(pi, pj) for patents pj grouped by their citation relation with pi in order O(|ν|). The set A is the set of violated constraints with respect to OPTIMIZATION PROBLEM II, or equivalently the most violated constraints of OPTIMIZATION PROBLEM I. Line 17 updates w using the violated constraints in A. This step is in order O(|μ|) as |A| ≤ 2|μ|. Lines 18-20 ensure the 2-norm of w is not too big, which is a condition used in [Shalev-Shwartz et al., 2007] to prove the existence of an optimal solution. Line 22 outputs the final w parameter with the best validation set performance. The performance measure is described in Section 4.2. In summary, the runtime for each iteration is O(|μ||ν|), so the runtime for SVMPR training is O(T |μ||ν|), given precalculated mapping Φ.

Theoretically, we can show that the number of iterations needed for SVMPR to converge to a solution of accuracy ϵ from an optimal solution is ˜O( R2 λϵ ) where R=maxpi∈μ,pj∈ν 2‖Φ(pi, pj)‖. This result follows from Corollary 1 of [Shalev-Shwartz et al., 2007]. In practice, our training algorithm always completes within five hours of runtime in the experiments.

4 Empirical Results

4.1 Dataset

For our experiments we focused on Wireless patents granted by the USPTO. We started with data from 2001 since this is the first year USPTO released data differentiating examiner and applicant citations. We used a list of Essential Wireless Patents (EWP), a set of patents that are considered essential for the wireless telecommunication standard specifications being developed in 3GPP - Third Generation Partnership Project - and declared in the associated ETSI (European Telecommunications Standards Institute) database. We considered three versions of the dataset: the original patent files, the patent files after applying a Porter stemmer [Porter, 1980], and the patent files after applying a Porter stemmer and common stopwords removal. The Porter stemmer reduces different forms of the same word to its original "root form", and the stopword removal eliminates the influence of common but non-informativewords, such as "a" and "maybe", in the ranking algorithms.

In our experiment, μ is the set of essential wireless patents (2001-2007) that made at least one citation to any other patent in 2001-2007, and ν is the set of patents from 2001-2007 that has been cited by any patent in μ. This dataset currently contains ∼197,000 patent-pair citation judgements. This is significantly larger in scale than the OHSUMED dataset widely used as a benchmark dataset for information retrieval tasks, which contains 16,140 query-document pairs with relevance judgement [Hersh et al., 1994]. Our goal is to learn a good discriminant function wT Φ(pi, pj) for pi ∈ μ and pj ∈ ν. We randomly split the patents in μ into 70% training, 10% validation and 20% test set in 10 independent trials to assess the performance of SVMPR and other benchmark methods.

4.2 Performance Measure

Given a patent in μ, we rank all patents in ν by the score of wT Φ, and evaluate the performance using the Normalized Discounted Cumulative Gain (NDCG) [J¨arvelin and Kek¨al¨ainen, 2000].

NDCG is a widely used performance measure for multilevel relevance ranking problems. NDCG incorporates not only the position but also the relevance level of a document in a ranked list. In our problem, there are three levels of relevance between any two patents pi and pj, as defined by Cij , with 2 the most relevant and 0 the least. In other words, if pj is cited by an examiner in pi, it has a relevance value of 2, and so on. Given an essential wireless patent pi, and a list of patents π from ν, sorted by the relevance scoring function, the NDCG score for pi at position k (k ≤ |ν|) is:

Npi is the normalization factor so that the perfect ranking function, where patents with higher relevance values are always ranked higher, will have a NDCG of 1. The final NDCG performance score is averaged over all essential patents in the test set.

4.3 BenchmarkMethods

In this section, we briefly describe the six ad-hoc IR methods implemented by the Lemur IR package (with default parameters) that we used as benchmarks, and how they are used to rank the patent citations. Given a query q and a document d, each of the six methods can be described as a function ψ(q, d) whose value, a real number, is often regarded as the measure of relevance. The six methods are presented in Table 1. Details of the last three KL-Divergence methods with different smoothing priors can be found in [Zhai and Lafferty, 2001].

For each of the six ranking methods, given a wireless essential patent pi ∈ μ, we score it with all patents in ν, by treating pi as the query and ν as the pool of documents. The methods are evaluated using NDCG with the ranked patent lists. Since we used the patent date feature in SVMPR which effectively indicates that certain citations are impossible, to be fair for the benchmark methods, we set all returned scores ψ(pi, pj) from the benchmark methods to -∞, if patent pi is an earlier patent than pj.

4.4 NDCGResults

We evaluate the NDCG at positions 3, 5, 10, 20, and 50. The NDCG score is averaged using 10 independent trials. For SVMPR, the maximum number of iterations is 200, and the test performance is evaluated when the best validation performance is achieved within the iteration limit. For the benchmark methods, the performance is reported on the same test sets as SVMPR. The results are presented in Figure 2. First of all, SVMPR outperforms the benchmark methods by a significant margin for all five positions. Referring to Table 2 for the numerical comparison with the best performance of any benchmark method, SVMPR outperforms the best result of the benchmark methods by 16% to 42%. Among all benchmark methods, the KL-Divergence with Dirichlet prior scored the highest, with more than 60% of all tests. Comparing the different document pre-processing procedures, we found that applying the Porter stemmer alone actually hurts the performance of SVMPR by a significant 10% to 17% in comparison to using the original patent documents, while the influence on the benchmark methods is marginal. The overall best performance is achieved with SVMPR when applying the stemming and stopword removal, as highlighted in Table 2. All the performance differences between SVMPR and the best alternative benchmark are significant by a signed rank test at the 0.01 level.

4.5 Results on ARandomDataset

We repeated the experiments on a non-homogeneous random dataset to understand better whether SVMPR learns and benefits from the internal structure of the patent set μ, and justify our decision to group homogeneous patents together during training.

We randomly sampled the set μ, and among the patents cited by patents in μ, we randomly selected the set ν, while keeping the same number of patent-pair citation judgments as before. We then repeated the experiments described above with the Porter stemmer and stopword removal applied. Now

K

instead of a structured essential patent set, μ is an arbitrary set with little internal similarities among its members. Because the patents in μ are quite unrelated, the patents they cite in ν are non-homogeneous too. In other words, this is an easier task than the previous one since we are learning to rank patents in ν that are more distinguishable than before.

The results are presented in Figure 3. We observed that the new performance differences among SVMPR and other benchmark methods are largely indistinguishable (best alternative method performance is within 5% of SVMPR). This follows from our intuition that the random dataset lacks a homogeneous citation structure to be learned, and the reasonable methods would perform comparably well, although the learned ranking is less informative as it only differentiates irrelevant patents.

5 Conclusion

In this paper we focused on the problem of patent prior art search which is traditionally a tedious task requiring significant expert involvement. Our proposed approach based on large margin optimization incorporates constraints that directly capture patent ranking specificities and ranks patent citations to previously granted patents by a linear discriminant function wT Φ, where w is the learned parameter and Φ is the feature map vector consisting of patent domain knowledge features and meta score features. Experiments on a wireless technology patent set show that SVMPR consistently outperforms other state-of-the-art general IR methods, based on the NDCG performance measure.

Acknowledgments

We thank Bill Lesser and Aija Leiponen for useful discussions about patents and Aija Leiponen for her suggestions concerning wireless patents as well as for providing us with the essential wireless patent data. We thank Thorsten Joachims for the discussions on ranking with margin based methods. We also thank the reviewers for their comments and suggestions. This research was supported by AFOSR grant FA9950-08-1-0196, NSF grant 0713499 and NSF grant 0832782.