T 1849/17 (Search engine with user feedback/PINTEREST) 12-02-2019
Download and more information:
SEARCH ENGINE THAT APPLIES FEEDBACK FROM USERS TO IMPROVE SEARCH RESULTS
Clarity - auxiliary request 2 (no)
Alleged technical effect not established
Inventive step - all requests (no)
I. The appeal is against the decision of the examining division, with reasons dated 27 March 2017, to refuse European patent application No. 06 738 810, because the claimed invention lacked inventive step over the document
D1: Eske V., "User Profile Management in a Web Search Engine", Master's thesis, Universität des Saarlandes, 2004.
II. Notice of appeal was filed on 26 May 2017, the appeal fee being paid on the same day. A statement of grounds of appeal was received on 26 July 2017. The appellant requested that the decision be set aside and that a patent be granted on the basis of claims according to a main request or one of five auxiliary requests as filed with the grounds of appeal. The appellant argued that its right to be heard was violated by the examining division because the division did not identify, before issuing its decision, the board of appeal decisions it had relied upon.
III. In an annex to a summons to oral proceedings, the board informed the appellant of its preliminary opinion that no substantial procedural violation had occurred that would require immediate remittal under Article 11 RPBA and that the claimed invention lacked inventive step, Article 56 EPC. Clarity objections were also raised.
IV. In response to the summons, with a submission dated 22 November 2018, the appellant filed amended claims 1-46 according to a main and an auxiliary request 1 replacing all requests on file.
V. Oral proceedings were held on 12 February 2019, during which the appellant also filed amended claims 1-46 according to an auxiliary request 2.
VI. Claim 1 of the main request reads as follows:
"A method of ranking documents in a results list of documents presented to a user in response to a search query comprising:
a. receiving and storing feedback from the user u regarding a relevance of a document d to the user u, from the search query q, the feedback being represented as a query-document feature (q, d, u) = s, where s is the rating as a number of stars assigned by the user u, and discarding any previous rating for the query-document feature (q, d, u);
b. associating the user feedback s with the search query q and the document d;
c. determining a relevance score for the document d for the query q, for a vector of a plurality of features X of the document d and a vector of the parameters theta for a model for a group of users combined with a specific vector of weighted feedback of a vector of the parameters psi for each user u according to the expression
u(X) = 1/[1 + e**(-(theta+psi)*X)]; and
d. ranking the document based on the relevance score."
Claim 1 of auxiliary request 1 differs from that of the main request in that the phrase "from the search query q" in step a has been replaced by "in response to a search query q", that the parameter psi in the relevance formula is replaced by psiu and that the following text is added at the end of the claim:
"... wherein the ranking includes
e. organizing the vector of the parameters psiu for each user u into a coordinate system, and
f. clustering the vector of the parameters psiu for each user u, and
g. adapting the ranking of the documents after clustering."
Claim 1 of auxiliary request 2 differs from claim 1 of the main request in that it reads, from step c onwards, as follows:
"...
c. determining a weight U(q,d)u,s based on the user feedback s for the query-document feature (q,d,u),
d. determining a vector of a plurality of features X of the document d,
e. augmenting the feature vector X with the weight U(q,d)u,s from the user u to form a user specific feature vector of weighted parameters psi,
f. augmenting the feature vector X with the weight U(q,d)u,s from other users u to form a global feature vector of weighted parameters theta for a group of users,
g. determining a relevance score for the document d for the query q, for the vector of the plurality of features X of the document d and the vector of the parameters theta for the group of users combined with the specific vector of weighted feedback of the vector of the parameters psi for the user u according to the expression
u(X) = 1/[1 + e**(-(theta+psi)*X)]; and
h. ranking the document based on the relevance score."
VII. At the end of the oral proceedings, the chairman announced the decision of the board.
Article 11 RPBA
1. The appellant argues that its right to be heard was violated by the examining division because the division did not identify, before issuing its decision, the board of appeal decisions it had relied upon (see the grounds of appeal, paragraph bridging pages 1 and 2).
1.1 The examining division is not required to cite board of appeal decisions in support of its arguments. It must provide reasons for its decisions, after having given the applicant the opportunity to comment on them, Article 113(1) and Rule 68(1) EPC 1973. In its reasons, the examining division may adopt considerations expressed by the boards of appeal in other cases.
1.2 However, for the purposes of the applicant's right to be heard, it is immaterial whether the examining division relied upon decisions by the boards of appeal - except, of course, those few by which it is bound, see Article 111(2) EPC 1973 - and, therefore, it is not required that examining divisions cite any, unless such reference is required to understand the reasons themselves (see also T 575/15, point 3.2 of the reasons, and T 1205/12, catchword).
1.3 In the board's judgment, the examining division's reasons were understandable on their own without any express reference to a decision by the boards of appeal. Therefore, the board does not find it objectionable that the examining division stated during the oral proceedings that its reasons were based on "established case law" without identifying the cases relied upon.
1.4 In particular, it does not amount to a fundamental deficiency of the examination proceedings in the sense of Article 11 RPBA, so that the question of whether the case should be remitted without consideration of its merits did not arise.
The invention
2. The application relates to search engines, typically on the Internet, and is concerned with the problem of improving the perceived quality of the search results. More specifically, the application addresses the problem of making search results more "relevant" for the user. This is difficult because search queries are rather imprecise, as users have different tastes, interests and understandings of search terms, and because users may carry out searches in different "modes" (e.g. shopping or reading news; see page 1, last paragraph, and page 2, paragraph 3).
2.1 In prior art solutions, discussed in the application, the relevance of a document was assessed on the basis of the content of that document, of links between web pages or the feedback of test users (see page 1, paragraph 4, and page 2, paragraph 2).
2.2 The invention proposes to allow direct relevance feedback by users on individual results returned in response to a query (see figure 1, no. 170). Based on this feedback, a relevance model is adjusted.
2.3 More specifically, it is disclosed to "log" feedback as a "query-document feature (q,d,u)=s, where s is the number of stars assigned by user u" to document d. Only the most recent such feedback is kept (see page 13, lines 8-13).
2.4 The application proposes modeling the "probability" that a given document is relevant (i.e., its relevance score) by "logistic regression" based on features X of the document (such as, in the board's understanding, binary values, each indicating the presence or absence of a feature) and "parameters" theta (effectively weights; see page 12, line 30, to page 13, line 7). This model is modified in view of the user feedback, especially the weighted parameter psiu per user u (see page 14, lines 8 to 15). Users' feedback may be clustered, for instance in view of groups of users, (see page 3, lines 21-25) or in order to detect and exclude search engine optimizers and spammers as outliers due to the "eccentricities in their parameters". Additional parameters gammac determined per cluster c (see page 14, line 26, to page 15, line 10) may be used to adapt the relevance model (see, in particular, page 16, line 9).
The prior art
3. D1 concerns "relevance feedback in multicriteria web search engines" based on machine learning techniques (see page 6, paragraph 1; page 7, paragraph 2; and page 9, paragraph 2, to page 10, paragraph 2). The models being considered are disclosed in chapter 2 (page 12 et seq.), an example being discussed on page 44 et seq. The advantages of the proposed algorithm are listed on page 46, and the system architecture is depicted on page 79. Specifically, it is disclosed that "distinct" user profiles derived from individual user's feedback can improve search quality, provided the feedback quality is good (see page 47, section 2.3).
Claim construction
4. Claim 1 of the main request specifies that the user gives query and document-specific "ratings" in terms of a number of stars ("(q,d,u) = s"). The relevance score for a document d with features X and an individual user depends on "parameters" theta and psi (or psiu) representing, respectively, a "model for a group of users" and a model "for each user".
4.1 The claim language does not specify if and how the model parameters theta and psi are determined on the basis of the user ratings. More specifically, it does not define how the user rating per document d is translated into a model parameters per feature X of a document.
4.2 Options come readily to mind. For instance, all document features (say, length and type of, and number of search term occurrences in a document may simply inherit the user rating of the entire document. This is, however, neither claimed nor necessarily useful. Users might find a document very relevant because it mentions a search term frequently and in the right context, even though they might dislike the document type (because they prefer, say, pdf over doc).
4.3 The claim language also does not specify how the groups are determined.
4.4 Again, there are obvious options such as groups of colleagues or members of the same sports club. However, while it may be plausible to assume that a user shares preferences with colleagues when it comes to work-related matters, this is not the case for private matters such as music, art or sports.
Clarity, Article 84 EPC 1973
5. Claim 1 of auxiliary request 2 specifies in step c that "a weight U(q,d)u,s" is determined "based on the user feedback" and in step d that a "feature vector X" is augmented with a "weight U(q,d)u,s" in order "to form a user specific feature vector of weighted parameters".
5.1 However, parameters and features must be clearly distinguished. Although the parameters correspond, as weights, to the individual features X, they are still separate. Documents have features irrespective of any rating or relevance score.
5.2 For that reason, it is unclear to say that a feature vector is "augmented with" a weight so that claim 1 of auxiliary request 2 is rendered unclear, Article 84 EPC 1973.
Technical effect
6. In its decision (point 11 of the reasons), the examining division stressed that "features relating to feedback of users for search results [were] not considered as technical". Following this, it found that the distinguishing features of all requests over D1 did not "have a technical purpose", "contribute to the technical character of the invention", or "make a technical contribution over the teaching of D1" (see points 14.2-14.5, 16.1-16.5, 18.1-18.5, 20.2, 24-25, 28.1-29 and 31.1-32 of the reasons).
7. The appellant argued that the claimed invention provided a "faster and more efficient execution of a search" and a "faster and more efficient ranking" of search results "on a computer", which had to be considered as technical problems. In particular, the features of "discarding" previous user feedback (see claim 1, step a, last phrase) and that of eliminating "bias" by reference to a "group model" contributed to these effects (see the grounds of appeal, page 2, paragraph 5, and page 5, paragraph 2).
7.1 The board does not accept that the search itself executes any "faster" or "more efficient[ly]" due to the claimed relevance feedback, in particular because the search results are ranked after retrieval. Likewise, the ranking itself cannot be said to be determined any "faster" or "more efficient[ly]", inter alia because the reference for this comparison is not indicated ("faster and more efficient" than what?).
7.2 Generally speaking, the invention is meant to produce relevant search results quicker (or higher up on the list of results) and thus to reduce the time until a user finds a "hit" in the search results. A relevance feedback that would reliably achieve this effect might save the user certain work, such as clicking through a long list of search results or having to repeat a search. The board does not wish to exclude the possibility that this may be considered as a technical effect by analogy to the ratio of T 0643/00, which is that providing a technical tool for efficient search, retrieval and evaluation of images may be considered a technical problem solved (see also the grounds of appeal, page 2, paragraph 5).
7.3 This issue need not be decided, however, because it cannot be established that the invention does indeed reliably and reproducibly have the alleged effect. Without knowing any details about how the relevance models are computed from (or based on) the user feedback and how the groups are determined (see section 4 above), there is no basis for assessing even the probability that - or in which situations - the relevance feedback would actually be pertinent for an individual user.
7.4 The board therefore concludes that the claimed invention cannot be said to have the effect of saving the user work in the above-mentioned sense.
8. Likewise, it cannot be established that discarding a previous user rating has this effect. For instance, it is not guaranteed that the last user feedback on a particular document is relevant for the next search. The user might, for instance, in one instance search for holiday destinations and rate highly a document mentioning the country Turkey, and in the next instance look for Thanksgiving recipes and be interested in documents mentioning turkey, the bird.
9. The appellant did not propose any other technical effect than those mentioned above that the claimed invention might have.
9.1 Hence, the board must conclude that the relevance formula (in step c of claim of the main request and auxiliary request 1 or step g of auxiliary 2) is just any mathematical formula - and, as such, excluded from patentability by analogy to the exclusion of Article 52(2)(a) and (3) EPC 1973 - which does not contribute to the technical character of the claimed invention and, therefore, cannot contribute to inventive step (see T 641/00, headnote 1).
9.2 The same applies to the way in which user feedback is provided ("(q,d,u)=s") or that only the latest user rating is kept (see step a in all requests), or that, in some way, the models are derived from or "augmented with" the user rating.
9.3 As a consequence, even though the board does not agree with the unconditional statement by the examining division as recited above (point 6), the board does agree with the conclusion of the examining division that the claimed invention (according to all three requests) must be considered as the mere implementation of an abstract - and thus given (see T 641/00, headnote 2) - method, and which is obvious in view of for instance D1, and therefore lacks inventive step, Article 56 EPC 1973.
For these reasons it is decided that:
The appeal is dismissed.