Conformal Group Recommender System

In this section, we offer a concise overview of the conformal prediction principle, presenting relevant information for a comprehensive understanding. Let $z_{i}=(x_{i},y_{i})$ be a training instance (or an example), where $x_{i}\in\mathbb{R}^{d}$ is a $d$-dimensional attribute vector and $y_{i}\in\{Y_{1},Y_{2},\dots,Y_{c}\}$ is the associated class label. Given a dataset, $S=\{z_{i}\}_{i=1}^{n}$, which contains $n$ training instances, the aim of the classification task is to produce a classifier $h:x\rightarrow y$, anticipating that $h$ predicts $y_{n+k}$ well on any future example $x_{n+k}$, $k\geq 1$, by optimizing some specific evaluation function. A conformal predictor, on the other hand, associates precise levels of confidence in predictions. Given a method for making a prediction, the conformal predictor offers a set of predicted class labels for an unseen object $x_{n+k}$ such that the probability of the correct label not present within this set is no greater than $\varepsilon$, called $(1-\varepsilon)-$prediction region. We assume that the set of all possible labels $\{Y_{1},Y_{2},\dots,Y_{c}\}$ is known a prior, and all $z_{i}^{\prime}s$, are in i.i.d. fashion (independently and identically distributed).

The conformal predictor uses a (non)conformity measure designed based on the underlying algorithm to evaluate the difference between a new (test) instance and a training data set. Let $z_{n+1}=(x_{n+1},Y_{j})$, where $Y_{j}$ is tentatively assigned to $x_{n+1}$. The nonconformity measure for an example $z_{i}\in\{S\cup z_{n+1}\}$ is a measure of how well $z_{i}$ conforms to $\{S\cup z_{n+1}\}\setminus z_{i},\forall i\in[1,n+1]$. In other words, the nonconformity measure assesses the likelihood that the label $Y_{j}$ is the correct label for our new example, $x_{n+1}$. The difference in $S$’s predicted behaviour when $z_{i}$ is replaced with $z_{n+1}$ is then calculated. Let $p$-value be the proportion of $z_{i}\in S$ with a nonconformity score worse than $z_{n+1}$ for all possible values of $y_{n+1}$ (all class labels). The $(1-\varepsilon)$-prediction region is formed by labels with $p$-values greater than $\varepsilon$. Intuitively, the prediction behavior is observed by employing any of the conventional predictors that utilize the training set $S$.

The precedence mining (PM) based recommendation model is a type of collaborative filtering (CF) technique that captures the temporal patterns in the user profiles and provides recommendations to the target user based on the sequence of items they have consumed [20]. For example, if a user has seen Toy Story 1, the PM-based CF can recommend Toy Story 2 if it has been seen previously by users who have seen the Toy Story 1. The PM model uses precedence statistics, i.e., the precedence count of item pairs, to estimate the probability of future consumption based on past behavior. It estimates the relevance score of each candidate item for recommendation using precedence statistics.

Let $O=\{o_{1},o_{2},\ldots,o_{nitem}\}$ be the set of items, $U=\{u_{1},u_{2},\ldots,u_{nuser}\}$ be the set of users and $O_{j}$ be the set of items consumed by $u_{j}$. The items for recommendation are chosen based on the criteria that they are not present in the target user’s profile and are likely to be preferred by the target user compared to other items. The PM-based approach keeps $Support(\cdot)$ and $PrecedenceCount(\cdot)$ statistics for each item $o_{i}$ to calculate the recommendation score of an item.  $Support(o_{i})$ is the number of users who has consumed the $i$th item, and the $PrecedenceCount(o_{i},o_{h})$ is the number of users who consumed item $o_{i}$ before item $o_{h}$. We use a notation $PP(o_{i}|o_{h})$ to denote the precedence probability of consuming an item $o_{i}$ preceding $o_{h}$. We define $PP(o_{i}|o_{h})$, and $Score(o_{i},u_{j})$ as follows.

Although the temporal pattern is important in some real-world applications, the associations of item consumption are more important than strict precedence relationships. For instance, in household product recommendations, device recommendations, or Youtube video recommender systems, more than the sequence, it is crucial to analyze the set of items consumed together. Consider the table given in Example 1 where some movies, such as Minions and Toy Story, are watched together but not necessarily in a particular order. Out of the six users who have watched the movie Minions, five of them have also watched Toy story either before or after it. The opposite is also true. This could be because, while Minions and Toy Story are not as closely related as Godfather I and II, they are both animated children’s films, and it is likely that if a person enjoys Minions, he or she will enjoy Toy Story as well. We consider the number of profiles that consumed two items (say, $o_{i}$ and $o_{j}$) together in this work rather than the number of profiles that consumed $o_{2}$ after $o_{1}$. In other words, instead of taking the precedence probability of $o_{j}$ given $o_{i}$ ($P(o_{j}\mid o_{i})$), we take the probability of $o_{i}$ given $o_{j}$ ($P(o_{i}\mid o_{j})$) while estimating the relevance score of an item to the target user. Thus, Equation 2 is rewritten as

where $P(o_{i}|o_{h})=\frac{Support(o_{i},o_{h})}{Support(o_{h})}$ and $Support(o_{i},o_{h})$ is the number of users having consumed item $o_{i}$ and $o_{h}$ together. $Support(o_{i})$ represents the number of users who have consumed item $o_{i}$, which is also equal to $Support(o_{i},o_{i})$. $P(o_{i}|o_{h})$ denotes the probability of consuming an item $o_{i}$ given that an item $o_{h}$ is already consumed. Items with high scores are subsequently recommended to a user. Conversely, if the score is low, it is implausible that the item would interest the user.

We call this formulation as Association Mining based Recommender System. We now consider an example which illustrates the working of the Association Mining based recommender system.

Recommender systems that employ Association Mining focus on discovering associations among items that users have consumed. These systems then utilize support statistics to compute a high relevance score for recommending new items. The major advantage of the current model over a traditional CF approach is its ability to account for the frequent pairwise relations among all users. After identifying a subset of similar users, the traditional CF approach narrows down its search to items consumed by the users within the neighborhood. Consequently, certain consumption patterns of items by the entire user group are excluded due to this restriction. The nicety and novelty of this approach lie in its utilization of pairwise relations between items. The current approach is also different from the association rule mining [21] that derives if-then rules using user transactions. In contrast, the present method estimates the relevance score as the likelihood of consuming a candidate item given a set of commodities consumed by a user.

The virtual user approach for GRS creates a virtual profile representing the group preferences and utilizes this profile to build the recommendation set [19]. A virtual user profile is created by computing the weight that indicates the group preferences for each item consumed by at least one group member. We compute the weight of an item $o_{i}$ for a group $G$ as follows:

In our previous work, after determining the group weight for all the group items, we proposed two different ways of creating a virtual user profile: 1)Threshold-based virtual user $-$  A virtual user profile is made up of items whose weight exceeds a certain threshold. 2) Weighted virtual user $-$ The virtual user profile comprises all the items each group member consumes and their weights. This paper adapts both of these techniques and proposes an hybrid approach that relieves the items with significantly less weight and forms a weighted virtual user profile with the remaining items.

Let $V(G)$ be the virtual user representing the group $G$ profile and $O_{V(G)}$ be the set of weighted items in the virtual user profile. We randomly divide the virtual user profile $O_{V(G)}$ into $O_{V(G)}^{1}=\{o_{1}:w_{1},o_{2}:w_{2},\ldots,o_{n}:w_{n}\}$ and $O_{V(G)}^{2}=\{o^{\prime}_{1},o^{\prime}_{2},\ldots,o^{\prime}_{k}\}$, where $O_{V(G)}^{1}$ is the training set that holds items known to be consumed and $O_{V(G)}^{2}$ contains the candidate set of items that are consumed by the user but are not part of the training dataset. Given a new candidate item $o_{n+1}\in O_{V(G)}^{2}$, CGRS measures its strangeness with respect to the items in the training set. We define the nonconformity of an item $o_{i}\in O_{V(G)}^{1}$ as the relevance score of a candidate item $o^{\prime}_{j}\in O_{V(G)}^{2}$ with a profile excluding $o_{i}$. We compute the nonconformity value for each item in the extended training set $O_{V(G)}^{3}=O_{V(G)}^{1}\cup\{o_{n+1}:1\}$. To compute the nonconformity score of an item $o_{i}$, we use the profile $O_{V(G)}^{4}=O_{V(G)}^{3}\setminus\{o_{i}:w_{i}\}$. The nonconformity value of $o_{i}$, indicated as $\alpha^{i}$, concerning the recommendability of an item $o^{\prime}_{j}$ is defined as follows.

The $p$-value of a new item $o_{n+1}$ is defined as the proportion of $o_{i}$’s in $O_{V(G)}^{4}$ such that the score $\alpha^{i}(o^{\prime}_{j})$ is greater than or equal to $\alpha^{n+1}(o^{\prime}_{j})$.

Hence, comparing the weighted probabilities is better choice than comparing the scores directly to streamline the computation. Thus we redefine $p(o_{n+1},o^{\prime}_{j})$ given in Equation 6 as follows.

The property of validity ensures that the probability of committing an error will not surpass $\varepsilon$ for the recommendation set $\Gamma^{\varepsilon}$. This indicates that the possibility of not recommending user’s interesting item $o$ is bounded to $\varepsilon$, i.e., $P(p(o\leq\varepsilon))\leq\varepsilon$. Lemma 1 discussed in the previous subsection forms the basis for proving the validity of the proposed approach. The following lemma establishes the fulfillment of the validity property by the proposed CGRS by employing the line of reasoning provided by Vovk et al. [22].

Apart from meeting the validity property, possessing an efficient recommendation set is desirable. Within the conformal framework, an efficient set is characterized by narrower intervals and higher confidence levels. We experimentally investigate the efficiency aspects in Section 5 using standard performance metrics.

In this section, we analyze the time complexity of the proposed approach. The time complexity of creating the virtual user profile is $O(nitem\times n_{i}\times\lvert G\rvert)$, where $nitem$ is the total number of items, $\lvert G\rvert$ is the group size, and $n_{i}$ is the number of items in each group member¹¹1If each member has consumed a different number of items, $n_{i}$ in the time complexity expression will be maximum among all the individual profile sizes.. Assuming $(n+k)$ items in the virtual user profile, $n$ items in $O^{1}_{V(G)}$ and k items in $O^{2}_{V(G)}$, the time complexity of the $p$-value computation for each item is $O(nk)$. To make a recommendation set, we need to compute $p$-value for all the candidate items. Hence, the total complexity is $O(n\times k\times nitem+nitem\times n_{i}\times\lvert G\rvert).$

This section reports the experimental analysis to study the performance of CGRS. The experiments are conducted on standard benchmark datasets mentioned in Table 1. The evaluation is based on traditional metrics such as Precision, Recall, F1-score, NDCG, RR, AP, and AUC. We also analyze the proposed approach by varying the group sizes. All the results reported here are the average of 500 randomly generated instances.