We identify a new information retrieval task for eCommerce that we call the high accuracy recall task. That task is to identify as many relevant documents, and as few non-relevant documents as possible, such that regardless of the rank ordering, the precision remains high. We demonstrate a need to investigate this problem, we propose metrics to measure the quality of the results, and we suggest how a document collection might be built and queries might be generated.
• Information systems → Retrieval efectiveness ;
eCommerce search engines often provide multiple rank orders of the results. Amazon, for example, ofers the user 6 orders ranging from “Relevance” to “Avg. Customer Review” and “Price: Low to High”, Trademe ofers the user a choice of 10 rank orders.
Search engine evaluation has traditionally been based on measuring the ability of the search engine to place relevant documents at the top of a results list. The working hypothesis is the probabilistic ranking principal – documents in a results list should be ranked in order of most probably relevant to the user, to least probably relevant to the user. For an eCommerce search engine its necessary to diverge from this principal because of the multiple rank orders.
In this short opinion piece we explore how we might evaluate the quality of an eCommerce search engine ofering multiple rank orderings using Amazon and Trademe as running examples.
First we explore the search interface of these two sites and show that they, indeed, provide the user with the ability to re-sort the results of their query. We then examine the quality of the first page of results for a single query and show that the quality varies for diferent rank orderings. Indeed, when we examine the multiple Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
SIGIR 2018 eCom, July 2018, Ann Arbor, Michigan, USA © 2018 Copyright held by the owner/author(s). orders for a single query we show that these search engines find it dificult to identify documents that are relevant to that one query.
We believe that the problem is a consequence of the quality of the set of documents1 retrieved by the search engine (and then ranked). If this recall base contains many false positives then it is inevitable that some rank order (either known now, or future rank order) will place a non-relevant document high in the results list.
There are two ways we might measure the quality of the results. The first is to make no assumptions on the rank order and to measure the quality of the retrieved documents as a set – which we show is infeasible in a large collection. The second is to evaluate using the rank ordering the sites provide and we propose a metric to accomplish this.
The probabilistic ranking principal also fails for eCommerce because it assumes the user is trying to find a relevant document. In the case of a user browsing an eCommerce site to, for example, get a “feel” for the going price and quality of a used book, they are trying to compare the top few (k) results. We examine this search modality as a case of invested efort – something that has previously been examined as the expected search length (ESL) and tolerance to irrelevance (T2I). We introduce a metric that measures the proportion of non relevant documents the user will see when they reach the kth relevant document. 2
Modern Internet search engines consist of a document collection
and a sophisticated search engine that, given a user query, resolves
the query against the collection to produce a list of results. The
probabilistic ranking principal [
The probabilistic ranking principal has been examined and
questioned many times. Fuhr [
The probabilistic ranking principal is directly questioned by the
user interfaces to many eCommerce sites. Figure 1 (left) shows
the 6 diferent sort orders on Amazon, ranging from “Relevance”
to “Price: Low to High” to “Newest Arrivals”. Of these 6, only 1
(Relevance) could be considered to be applying the probabilistic
1In eCommerce it is usual to use the term document to refer to a product listing –
which may or may not contain reviews, ratings, and so on.
2https://en.wikipedia.org/wiki/Apple_(disambiguation), visited: 23 April 2018
ranking principal. Figure 1 (right) shows the sort orders for Trademe,
an Australasian eCommerce site and its 10 sort orders which, while
not dissimilar to those of Amazon, also include “Most Bids”, and
“Title”, neither of which are ordered by the probabilistic ranking
principal. We note that title ordering has been examined by Sherlock
& Trotman [
If most of the available rank orderings of eCommerce sites are not “Relevance”, then evaluation of the search engine cannot be done on the assumption that it is. That is, the ability to put the most relevant document at the top of the results list is only one facet of rank orderings to be evaluated when measuring the quality of a site. 3
It has been posited that if the ranking function is efective enough
then a few false positive documents in the results lists is acceptable
because the ranking function will place those documents at the
bottom of the list and no-one will see them [
To illustrate this point we searched for “iPhone X” on both Amazon and Trademe, and ranked using price low to high – something we consider entirely reasonable for a user to do and quite likely a high frequency (or head) query. While using a single query is far from evidence of a systematic problem, it can be considered to be a proof, by example, of the existence of a problem.
Figure 2 left shows the results for Amazon while Figure 2 right shows the results for Trademe. On Amazon, neither of the first two listings are for phones (and neither is the advertising). On Trademe, two are for a stylus, and two are for cases (but not for the iPhone X). On both Amazon and Trademe none of the results on the first page are for an iPhone X. When ordered by relevance, the top 4 results on both sites (the first page) are all iPhone X.
To demonstrate that this problem is not unique to “price low to high”, we issued the same query on Amazon and looked at the top document of each of the sort orders and examined the top result. Of the 6 sort orders on Amazon, 3 failed to place an iPhone X at position 1. On Trademe only 2 of the 10 sort orders placed an iPhone X at position 1. A single query is insuficient to draw robust conclusions, but demonstrates the existence of a problem.
It is reasonable to conclude that the found document set (the recall base) contains false positives which in “Relevance” order are pushed low down in the results list, but in other sort orders these false positives can be presented to the user. 4
The comparison between Amazon and Trademe shows that not only are there several possible sort orders, but that those orders are diferent between diferent sites. This suggests that it might not be possible to close the list of sort orders – in other words, Amazon might adopt some new sort orders in the future.
This raises the question how to evaluate the quality of a search engine in light of sort orders that have not yet been proposed, as well as those that have. We believe that this can be achieved by measuring the quality of the recall base rather than the ranking. The obvious measure is the F1 of precision and recall, at least as far a buying is concerned. We explore this in section 4.1.
Information retrieval metrics are, in essence, models of users. We
are aware of very little work examining user interaction on
eCommerce sites (but see Sharma et al. [
When browsing the user wants to see k relevant documents to compare (for example) their colour, quality, age, and price. We explore metrics for browsing in section 4.3. 4.1
The accuracy of a search engine irrespective of the rank order of the documents in the results list is given by the set-wise precision. Precision is defined as the proportion of documents that the search engine returns that are relevant.
p = fr , (1) f where fr is the number of known-relevant documents retrieved by the search engine, and f is the number of documents in the results list. Problematically, a strategy for scoring high in set-wise precision is to return only one relevant document – which is clearly not in the interests of the user (unless there is only 1 relevant document in the collection).
A solution is to measure the recall, the proportion of the known relevant documents in the collection that the search engine returns to the user, c = fr (2) r where c is the recall, fr is the number of known-relevant documents retrieved by the search engine, and r is the number of knownrelevant documents in the collection. Problematically, a strategy for scoring high in recall is to return all documents – which is not in the interests of the user because the precision can be expected to be low.
If both set-wise precision and recall are very high then the search engine has returned a large proportion of the relevant documents and putting them in any order should nearly satisfy the probability ranking principle. This is usually measured using the F1 score, the harmonic mean of precision and recall. The F1 score is rank-order invariant. That is, it is a good indicator of quality before the rank order is known. To compute F1, its necessary to know r .
In a large document collection such as those at Amazon (about 550 million listings)3 and Trademe (about 6 million listings)4, for a given query, it isn’t possible to know the number of relevant documents in the collection (items for sale that the user might want to purchase or browse). So computing set-wise recall is infeasible. We propose three solutions to this: random sampling, reordering, and pooling.
A random sample taken from the document collection could be used. We observe that there are two possible outcomes of a randomly selected document – either it is relevant or it is not – so the distribution is binomial and each randomly selected document is a Bernoulli trial.
Assuming the search engine is perfect (precision = recall = 1), we have an estimate of the number of relevant documents in the collection is given by: pˆ = fr , (3)
N where pˆ is the estimated proportion of the collection that is relevant, fr is the number of found documents, and N is the collection size.
The confidence we have in that estimate is
rpˆ(1 − pˆ) pˆ ± zα /2 N Allowing for a confidence interval of 10% of pˆ,
δ = |pˆ − (1.1 ∗ pˆ)| and for convenience sake we set pˆ0 = pˆ, and pˆ1 = 1.1 ∗ pˆ. We can now compute n, the number of samples we need to take from the entire collection to validate that the results list contains at least the number of documents that are relevant.
Since δ = z1−α /2 rpˆ0(1 − pˆ0) + z1−β rpˆ1(1 − pˆ1) n n z1−α /2ppˆ0(1 − pˆ0) + z1−β ppˆ1(1 − pˆ1) ).
δ
Assuming a document collection of 550 million documents, and about 400 relevant documents5, pˆ = 7 × 10−7. For a one-tailed 3https://www.scrapehero.com/many-products-amazon-sell-january-2018/ 4https://www.Trademe.co.nz/About-trade-me/Site-stats 5Roughly what we observe on Amazon today (mid 2018) for the query “iPhone X” (4) (5) (6) (7) 95% confidence level, z1−α /2 = 1.645. For 10% confidence interval, z1−β = 1.282, so n >= (
In other words, tens of thousands of documents in the collection would need to be sampled.
Assuming this was possible, having determined that the result set contains at least the number of documents that are relevant, it is next necessary to randomly sample the results set to determine the proportion of it that is relevant. The same binomial equations can be applied. In this case the expected proportion of document that are relevant, pˆ is near 1 (so we use 0.9), the confidence interval and confidence level might remain the same, so n is very small (about 7). From this the F1 measure can be computed (i.e. we know f , r and fr ).
However, since such a large number of documents must be sampled to determine the number of relevant documents for a given query, this approach is infeasible.
The second approach, and an alternative to sampling the entire document collection, is to permute the results list and compute the precision (for example, p@10) of all possible orderings. In the case of 2000 results the number of permutations is 2000! = 6.4 × 10868 which is too large to compute. However, with no recall component its not possible to know whether the recall base contains the best items (e.g. the lowest priced item). This is akin to known item ifnding where the known item is not known in advance and then measuring based on the assumption that the results list contains it. We do not believe this is valid way to measure quality.
The third approach, an approach used by Zobel [
Each of the three ways we propose for computing the score for a single query’s results list and irrespective of the results ordering are infeasible. We now turn our attention to the orderings a site provides rather than all possible orderings. A more viable approach to measuring performance is to directly use the rank orderings ofered by the site. In the case of Amazon, this would be the 6 orderings listed in Section 2, or the 10 orderings for Trademe. The obvious way is to compute the score for each list and to linearly combine and average.
We assume the user is interested in comparing k items, so we measure the efort required to find those k items. More precisely, we measure the inverse of that efort.
The efort to find one relevant document in one results list is simply the position of that item in the results list, rank1. The inverse of which is the reciprocal rank for the query, RR, the mean over a number of queries, |Q | is the mean reciprocal rank, MRR, MRR =
|Q | Generalizing this, to k relevant documents, RRk , Í|Q | 1
i=1 r ank1 RRk = Ík i i=1 r anki
k MRRk =
RRk (13) (14) (15) p = Õ|A| λapa
(10) a=1 |A| where p is the precision and pa is the precision score for ordering a of the A possible orderings, |A| is the number of orderings, and λa is a weight for ordering a, and Ía|A=|1 λa = 1. If all rank orders are of equal importance, 1 ∀a, λa = |A| . (11)
However, it is highly unlikely that all rank orderings are of equal importance to a site. On Trademe, “Best match” is the default, and “lowest price” appeals to bargain hunters, so we expect these to be weighted higher (more important) than “Title” or other orders.
One way to compute the λa weights is to compute the relative proportion of results lists presented in order a, others include the proportion of clickthroughs that come from the given list type, another is the proportion of sales from that list type, There are a multitude of possibilities, and most would require on-going observation as the proportions are likely to change based on the quality of the results, time, user location, and client device. In other words, there is a feedback loop.
The individual precisions, pa , could be computed using any of
the standard information retrieval metrics – that do not require
an estimate of the recall. This might include P@n, Rank Biased
Precision [
A browsing user is interested in comparing the characteristics of multiple items. This might be obvious eCommerce features such as price, or delivery time, or it might be more esoteric such as whether a certain edition of a book is on the market.
We believe that a metric similar to Tolerance to Irrelevance, T2I
[
k+ε ESL = Õ reli
(12) i=1 where k is the number of relevant documents we’re looking for and ε is the maximum number of non-relevant documents we’re prepared to tolerate (stopping after k relevant documents are found).
reli is 1 if the document at position i in the results list is not relevant, and 0 if it is relevant. ELS is the absolute number of irrelevant documents the user must view in order to see k relevant documents for a given query, which is then averaged over a number of queries. It also does not fall in the range [0..1]. and the mean of this, |Q | is the inverse of the efort the user must expend in order to observe k relevant documents. MRRk is in the range [0..1] where 1 is best.
We observe that MRRk is exactly equivalent to MAP @kr where kr is the position in the results list of the kth relevant document (rather than the more usual kth position in the results list). An obvious extension is MAP @kr %
We also note the similarity to r-precision [
It is pertinent to ask what relevance means in the context of an
eCommerce site. Goldberg et al. [
We believe that the definition of relevance for browsing is even more dificult to define – but it is clearly an item from an item set that the user wants to compare for some purpose. The purpose could be spelled out in a TREC-like topic definition. The set might be mined from user behaviour. 6
We showed in Section 2 that both Amazon and Trademe support multiple rank orderings of the results sets, and in Section 3 that those rank orders are not of equal quality. In order to measure the quality of the site we proposed in Section 4.1 that it is not feasible to measure F1 as the number of relevant documents cannot be known, and instead propose to measure a weighted average of the precision scores of each of the ofered results orderings. In this section we provide more details on our proposed task. We propose to take a dump of a large-scale online eCommerce site such as Amazon or Trademe. This might be achieved either by agreement with the site, by crawling the site, or by extracting documents from a preexisting crawl. There are several reasons such a site might choose to participate in such a dump. First, none of the data is proprietary, the data is already public facing and free. Second, providing a dump of the data to the research community is a marketing opportunity. Third, the results of research on such a document collection would be directly applicable by the group that makes data available, rather than requiring “porting” to a new document collection.
Acquiring a query log may be dificult as query data is proprietary, but a set of queries could be mined from a proxy log of a large institute that has not blocked eCommerce sites. The query is embedded in the URL of result page of both Amazon and Trademe, and extracting the query from that appears to be straightforward.
Values for λa could be estimated from a proxy log (although this might introduce bias). Both Amazon and Trademe embed the sort order in the URL. Either the proportions of queries using each sort order, or the proportion that lead to a buy, could be used.
Trademe and Amazon both support list and grid result presentation – and we believe that they should be measured diferently. Set-wise evaluation appears, at the onset, to be a better metric for grids whereas rank-biased metrics appear to be better suited to lists. The quality of both presentation formats should be measured.
Both Trademe and Amazon support rank orderings that are direct inversions of each other. For example, the results list for “Highest price” should be directly computable from the results list for “Lowest price” by simply inverting the results list, but many not be because of tie breaks.
We believe that a well performing search engine that returns high quality documents irrespective of the rank order must be good at identifying relevant documents, and have both a low false positive rate and a low false negative rate. Hence, we believe that it will be a high accuracy search engine.
High accuracy recall identification is an interesting problem for
many reasons. First, many years of assumptions about the ranking
function pushing low quality results down the results lists no longer
apply – the learning-to-rank pipelines in web search engines may
not be applicable. Second, to be usable online, high accuracy with
low latency is important. This raises new problems for IR eficiency
research which generally uses algorithms such as WAND [
The similarity between some of the rank orderings (e.g. price low to high) and known entity search does not escape us. In the proposed task, however, the known entity is known to exist, but which document it is is not. Indeed, knowing whether or not any search engine has found the lowest priced relevant document does not appear to be easy. We only know that the lowest priced item amongst those assessed has been placed at the top of the list. The metrics we have proposed do not account for whether or not the most-relevant item is in the recall base. We leave for further work the development of metrics that account for this in absolute orderings. An obvious way to address this is to consider non-recalled but relevant documents as non-relevant documents. That is, if there are 3 relevant documents lower in price than the search engine returns then count that as 3 misses before the results returned by the search engine – however these might be weighted as a missing cheapest item is a greater mistake than a missing 25th cheapest item.
In this short paper we examined two eCommerce sites and showed that they support diferent sort orders of the results list. We then showed that they are not equally good at ranking when using these sort orders and hypothesized that the problem is the quality of the recall set, those documents the search engine returns.
We suggested measuring the quality of the recall base irrespective of the presentation order and suggested that this as infeasible as it wasn’t possible to known the number of relevant documents in the collection – and it wasn’t possible to compute it.
We then proposed a weighted precision score as a metric and proposed methods of computing the weights – for buying. For browsing we developed a measure not dissimilar from tolerance to irrelevance, but based on MAP.
Finally we proposed the high accuracy recall task. For this task the search engine must identify as many relevant documents as it can without forfeiting precision – so that regardless of the presentation order the quality of the results is high.
We believe this is an interesting problem to tackle because it raises new questions about ranking, eficiency, and performance measurement. In future work we hope to build the collection and to launch the task.