Learning from Group Comparisons: Exploiting Higher Order Interactions
We study the problem of learning from group comparisons, with applications in predicting outcomes of sports and online games. Most of the previous works in this area focus on learning individual effects-they assume each player has an underlying score, and the "ability" of the team is modeled by the sum of team members' scores. Therefore, current approaches cannot model deeper interaction between team members: some players perform much better if they play together, while some players perform poorly together. In this paper, we propose a new model that takes the player-interaction effects into consideration. However, under certain circumstances, the total number of individuals can be very large, and number of player interactions grows quadratically, which makes learning intractable. In this case, we propose a latent factor model, and show that the sample complexity of our model is bounded under mild assumptions. Finally, we show that our proposed models have much better prediction power on several E-sports datasets, and furthermore can be used to reveal interesting patterns that cannot be discovered by previous methods.
scores. Through the process, one can also rank a player by his or her score in the model. For example, [13] extends the Bradley-Terry model to the group comparison setting; [12] proposed a TrueSkill algorithm to learn individual scores using a Bayesian model, which has now been used by game companies and sport analysts.
However, a common weakness of previous methods is that they ignore the player-interaction effects. In a team challenge, the players work together and will always influence each other, and this player-interaction effect can significantly alter game results. To make the prediction more accurate, incorporating the player-interaction effects are demanding. On the other hand, people are also interested in the cooperation effects between players. Team coach can pair a better team based on both individual abilities and cooperation abilities; game designers such as Blizzard can use the results to design their heroes. This brings us to the questions we wish to answer in this paper:
• Can incorporating player-interaction effects improve the prediction accuracy of the model?
How to interpret those effects?
• If the total number of players is too large, how can our algorithm scale up and meanwhile maintain good generalization error and efficient computational time?
To answer the first question, we propose a new model that can incorporate pairwise effects, and show that the pairwise effects can be learned when there are not too many players. The player-interaction can not be fully modeled by pairwise effects. This is the first step, and investigating effects with order higher than two is our future work. As for the second question, we propose a latent factor model to describe pairwise interactions between players, and propose an efficient stochastic gradient descent algorithm to solve it. A theoretical bound of the sample complexity is provided under mild conditions.
In the experimental part, we test our model on online game datasets and show that our proposed models have much higher prediction accuracy than previous individual-score based models. For example, in Heroes of the Storm data our new models can get around 80% accuracy, while state-ofthe-art models such as Trueskill can only achieve 60% accuracy.
Summary: This paper develops a model that can capture player-interactions from group comparisons (team-play win/loss info). In an effort to address higher-order interactions with a reasonable size of data set, it then proposes a latent factor model and the sample complexity analysis for the model is done under certain scenarios. Experiments are conducted on real-world on-line game datasets, comparing the win/loss prediction accuracy of the proposed approach to the prior methods such as BTL [12] and Trueskill [11].  Detailed comments:  The paper studies an interesting problem, and investigates the role of player-interactions which has been out of reach in the literature. One noticeable observation found in the paper is that the proposed approach may be able to identify the best team members with good chemistry, as suggested in Table 3. Also it is clearly written. The main concerns of this reviewer lie in (a) the performance of the proposed methods with comparison to the prior works; (b) experiment settings; (c) the novelty of the proposed approach.  A1. (Accuracy performance, Table 1): It seems the accuracy performance of the proposed methods is not much better than prior methods, except for HotS Tournament (H) dataset, in which players are advanced. Wondering if the other datasets reflect the cases in which players are not professional and the team chemistry is not apparent. What if the team chemistry is apparent while players are not professional? It is not clear about the scope of scenarios in which the proposed approach is outstanding – wide or narrow?  A2. (Player-interaction ranking performance, Table 3): Wondering if the BTL and/or Trueskill yield similar top-5 and/or bottom-5 pairs (one can compute the team score as a simple aggregation of the estimated individuals' scores, and use them to rank player-interaction). If not, it would be good to emphasize this, as it reveals that the proposed methods can capture interaction effect which are not explored well in the prior approaches.   A3. (Individual ranking performance): Many literature have focused on the ranking performance for individuals (entire or a few significant, say top-K). Wondering if the proposed approach yields the good performance for individuals as well.   B1. (1st experiment setting – heroes (game characters) are individuals): This setting looks arguable because it does not capture the interaction between heroes and players – some players might be very good when playing with particular heroes. Perhaps this setting makes sense only when all players are professional and so are good enough in dealing with any character – but wondering if the setting is typical.   B2. (2nd experiment setting – players are individuals): Due to the similar reason above, this setting is not quite convincing – it still does not capture the chemistry between players and heroes. I believe a reasonable justification behind the two settings should be provided – otherwise, the performance results  which are based on the settings are shaking.  C. (Novelty of the proposed approach): A series of the proposed approaches seem to rely on Eq. (1) in which input vector x_t is ternary: taking +1/-1 for participating individuals; 0 otherwise. But a similar approach (except the regularization term) was already proposed in the following literature: Menke-Martinez, “A Bradley-Terry artificial neural network model for individual ratings in group competitions”. I understand the proposed latent model is distinct from this, but it may be viewed as a reasonable addition to the basic framework in Menke-Martinez.