Diversifying Multi-aspect Search Results Using Simpson’s Diversity Index

Prior research on search diversification focused on the richness of the results (Simpson, 1949). Richness quantifies the number of different types the dataset of interest contains, while evenness considers the uniformity of the distribution of these types. However, evenness is also important for search diversification. Importantly for the e-commerce setting, it can affect users’ online shopping experience. For example, consider a product catalog with 1000 A items, 500 B items, and 500 C items. Suppose, we attempt to retrieve 12 results as diverse as possible to fit on the first page of the results. Without considering evenness, the expected search results might be 6 A items, 3 B items, and 3 C items. While considering evenness, the expected results are all 4. The richness of the two versions of the results is identical. However, the information entropy of the second set of results is higher, meaning that higher evenness could increase the information that the users receive in a limited space. In multi-aspect search, evenness is even more important. In multi-aspect search, the search results are the combination of many independent single-aspect searches. In prior research, (Simpson, 1949) shows that the combinations of the even results are the most diverse. Therefore, evenness affects the richness of multi-aspect search as well.

The above discussion shows that evenness is significant for diversity analysis. However, vast majority of the diversity models for search do not consider results’ evenness. Therefore, we propose to use a model considering evenness to enrich the diversity model for search. We propose to adopt the Simpson’s diversity index (SDI) method from biology for this task (Simpson, 1949). But first, we formally introduce the DPP-based algorithms for result diversification and then introduce our new SDI method.

Determinantal Point Processes (DPPs) are useful in domains where repulsive effects or diversity are important aspects to model. In recommender systems and information retrieval domains, where the discovery of documents and items are significant, DPPs can be used to diversify results. In search problems, DPPs are a subset selection problem. We define the search space as a set $S$, whose size is $N$, and the search results are a subset $S^{\prime}$, whose size is $k$. $B_{S^{\prime}}$ represents the selected items in $S^{\prime}$. DPPs can be formulated as:

$X=\underset{S^{\prime}\subseteq S}{\operatorname{argmax}}$ det$({B^{T}_{S^{\prime}}B_{S^{\prime}}}))$

$X$ is the volume of a parallelepiped spanned by the vectors of $B$. It is determined by the vectors’ length (relevance) and their cosine similarity (similarity). By maximizing $X$, we can obtain the best subset of $S$, considering both diversity and relevance.

However, DPPs are a richness-greedy diversification method, because $X$ does not change when we apply linear transformations to revise the evenness of $B$. Therefore, the evenness of the obtained subset of each aspect is not promised. In multi-aspect search, the results are the combination of every aspect. As we mentioned in Section 2.1, this can lead to weaker diversity of the combination.

Simpson’s Diversity Index (SDI) was originally introduced in biology to measure both the evenness and richness of a habitat (Simpson, 1949), and aims to estimate the probability that two randomly selected individuals from a sample will be the same. Apparently, if the habitat has more species (Diversity), this probability is smaller. Based on Jensen’s inequality, if the total number of the animals in the habitat is a constant, this probability is also smaller when the numbers of each species are the same (Evenness).

More formally, SDI is defined as the probability that two items are chosen at random and independently from a set is the same:

$D=\frac{\sum_{i=1}^{R}{(n_{i}(n_{i}-1))}}{N(N-1)}$

Where $R$ is the number of classes. $n_{i}$ is the number of items of the $i$th class. $N$ is the total number of all items. Smaller $D$ means higher diversity. SDI considers both richness and evenness, according to Section 2.1, it is more suitable to diversify search results over multi-aspect items.

In multi-aspect search, items are labeled by many aspects. We first consider the SDI of an aspect. In addition to the equation in Section 2.2, we have another way to calculate SDI.

In a set, we denote the number of items in this set as $N$. $R$ is the number of items’ classes. $n_{i}$ is the number of items of the $i$th class.

When we randomly select two items as a pair, there are $\frac{1}{2}N(N-1)$ pairs. For each pair, they belong to the same class or not. The total number of pairs belonging to the same class is $\sum_{i<j\leq N}{(a_{i}\&a_{j})}$. Where $a_{i}$ is the Item $i$. If two items are the same $(a_{i}\&a_{j})=1$, else $(a_{i}\&a_{j})=0$. If we also count the item itself, we have:

Where $p$ is the aspect, $P$ is the aspect set, $S^{\prime}$ is the selected set, $S$ is the whole set, $|S|$ is the size of $S$. $a_{p,i}$ is the Aspect $p$ of Item $i$.

If we consider all the aspects at the same time, we have:

In this equation, we first normalize each aspect’s SDI, because different aspects’ SDI may have different scales. Then, we weigh every aspect with $\omega_{p}$. If we only consider diversification, $\omega_{p}=1$. However, in the search problem, relevance is also very important. When the item is highly relevant to some aspects. For example, when users search ’blue shoe’, it is not necessary to present other colors’ shoes anymore. Therefore, the ’color’ aspect should be penalized. In this paper, $\omega_{p}=1-\frac{k_{p}-1}{|S^{\prime}|-1}$, Where $k_{p}$ is the number of the most common aspect of Aspect $p$ in top $|S^{\prime}|$ relevant results. For convenience, we let $\phi_{p}=\frac{\omega_{p}}{D(p,S)}$.

This transformation of SDI helps us organize it to a more efficient form to be optimized $--$ the binary quadratic program (BQP).

In this section, we transfer the SDI optimization to a BQP problem, which has thorough previous research to systematically be approximated and optimized (Ma, 2010)(Clarkson, 2010)(Springer, 2002). Since $H(S^{\prime})$ is pairwise, it can be computed in an easy way. Let’s expand $H(S^{\prime})$.

$H(S^{\prime})=\sum_{i,j\in S^{\prime},i\leq j}{\frac{2}{|S^{\prime}|(|S^{\prime}|+1)}\sum_{p\in P}{\phi_{p}(a_{p,i}\&a_{p,j})}}$

Let $Q_{i,j}={\frac{2}{|S^{\prime}|(|S^{\prime}|+1)}\sum_{p\in P}{\phi_{p}(a_{p,i}\&a_{p,j})}}$, we can reformulate $H(S^{\prime})$ as $H(S^{\prime})=\frac{1}{2}x^{T}Qx$, $x$ is a vector representing $S^{\prime}$. The length of $x$ equals to $|S|$. Each entry is an item of $S$. The entry of the chosen item is 1, or it is 0. If we further consider the relevance, we have:

Where $b$ is the relevance vector. Consequently, it becomes a binary quadratic program problem, whose constraints are: s.t. $x_{i}\in\{0,1\},\sum_{k=1}^{|S|}{x_{k}}=|S^{\prime}|$, where $x_{i}$ is the entry of $x$.

Equation 2 is a classical BQP problem. In this paper, we first relax it to a convex optimization problem (Ma, 2010). Then we use the Frank–Wolfe algorithm to optimize it (Clarkson, 2010). Finally, we use Goemans and Williamson procedure for the approximate solutions (Springer, 2002). Such a procedure guarantees that the solution is a close approximation that $T\in[T_{min},\frac{\pi}{2}T_{min}]$.

We experiment with two datasets: a publicly available Kaggle benchmark for the searching items dataset, and a complementary dataset constructed using publicly available Amazon Web Search engine interface for the queries dataset.

Kaggle Shoes Price Competition Dataset (Kaggle): Kaggle shoe price dataset is a list of shoes and their associated information, containing 19046 women shoes and 19387 men shoes. However, the items of this dataset also contain clothes, gloves, jewelry, and so on. Some items do not have features. To focus on the diversity problem, we remove items without features, clothes items, jewelry items, gloves items, trousers items, and toys items. At last, we have 14609 items. Besides, even though the items have many aspects, they do not have the values of many aspects. Therefore, we only choose 21 most commonly used features: ’Season’, ’Material’, ’Gender’, ’Shoe Size’, ’Color’, ’Brand’, ’Age Group’, ’Heel Height’, ’Fabric Material’, ’Shoe Width’, ’Occasion’, ’Shoe Category’, ’Casual & Dress Shoe Style’, ’Shoe Closure’, ’Assembled Product Dimensions (L x W x H)’, ’Fabric Content’, ’Shipping Weight (in pounds)’, ’prices.offer’, ’prices.amountMin’, ’prices.amountMax’ and ’prices.isSale’.

Amazon Queries Suggestions Dataset (AQS): To complement the Kaggle queries dataset, we created a new dataset automatically constructed for the “shoes” category using the query suggestions provided by the Amazon Web Search engine. Specifically, we collected the queries suggestions for the top-level category ’shoes’. This process resulted in 384 queries, such as ’fur lined winter coat women’. The AQS dataset is available at the URL https://docs.google.com/spreadsheets/d/17DMU5pMSiNxi05yu5pdEvrUf3b0mIAF1rYn2ypruS7A/edit?usp=sharing.

We now summarize the metrics used to compare the methods.

Coverage Rate(CR): The coverage rate measures the diversity of the subset (Castells et al., 2011). For each aspect of the item, they have at most 10 features or the number of this aspect’s features in this set. The coverage rate is a diversity metric.

$CR(S^{\prime})=\frac{1}{|P|}\sum_{p\in P}{\frac{|A^{\prime}_{p}|}{\min(|S^{\prime}|,|A_{p}|)}}$

Where $S^{\prime}$ is the selected set, $P$ is the set of all aspects, $A^{\prime}_{p}$ is the features of Aspect $p$ in the selected set and $A_{p}$ is the features of Aspect $p$ .

NDCG@10: We use normalized discounted cumulative gain (NDCG) to measure ranking results of the relevance. Since both results of DPPs and the proposed method do not have the order, we rank the selected subset based on the items’ relevance before computing the NDCG@10 (Castells et al., 2011).

$\alpha$-NDCG: A variations of NDCG, which can measure both relevance and diversity (Castells et al., 2011).

Variance: We use averaged variance of every aspect’s number of features to measure the evenness (Ricotta, 2017).

The results of diversity, evenness, and relevance are presented in Figure 1. The result of the computing time is illustrated in Table 1. In Figure 1, the trade-off parameter $\theta$ ranges from 0 to 1, whose step size is 0.1. For CR(a), NDCG@10(b), and $\alpha$-NDCG(c), the larger their value, the better the performance of the model is. For variance(d), a lower line means the model is evener. In Table 1, less computing time means the model is faster. Generally, the proposed method outperforms the baselines in terms of relevance, diversity, and evenness, especially when $\theta$ ranges from 0.3 to 0.7. The improvement is up to more than 15%. In terms of computing time, the proposed method spends less time than most of the baselines.

We use CR to measure the richness of the multi-aspect results in Figure 1 (a), which shows the proposed method outperforms the baselines when $\theta$ ranges from 0.2 to 0.8. In terms of relevance, the NDCG@10 scores from Figure 1 (b) show that the proposed method has closed performances. We further use $\alpha$-NDCG to measure the relevance and diversity at the same time in Figure 1 (c), which demonstrates that the proposed approach has the best performance while $\theta$ ranges from 0.4 to 0.7. Figure 1 (d) further applies the Variance to measure the evenness of the returned results. In this figure, we find that when the model emphasizes diversity ($\theta$ closes to 0), the variance of SDI is smaller than all the baselines. We further test the computing time of the proposed method and summarize the results in Table 1, revealing that the proposed method is slower than k-DPPs but faster than other baselines.