Search

Label ranking tasks are concerned with the problem of ranking a finite set of labels for each instance according to their relevance. Boosting is a well-known and reliable ensemble technique that was shown to often outperform other learning algorithms. While boosting algorithms were developed for a multitude of machine learning tasks, label ranking tasks were overlooked. Herein, we present a novel boosting algorithm, $BoostLR$ , that was specifically designed for label ranking tasks. Similarly to other boosting algorithms, $BoostLR$ , proceeds in rounds, where in each round, a single weak model is trained over a sampled set of instances. Instances that were identified as harder to predict in the current round, receive a higher (boosted) weight, and therefore also a higher probability to be included in the sample of the forthcoming round. Extensive evaluation of our proposed algorithm on 24 semi-synthetic and real-world label ranking datasets concludes that our algorithm significantly outperforms the current state-of-the-art label ranking methods.

Label ranking is a machine learning task that deals with mapping an instance to a ranking of labels, representing the labels’ ordered relevance to the instance. Three recent studies have suggested the use of ensembles to improve the performance of simple label ranking models. However, none of them has explicitly inspected the question of how should the results obtained by simple models be aggregated into a single combined output. While classification tasks and regression tasks typically employ trivial aggregation techniques (i.e., majority voting and averaging, respectively), the case of label ranking tasks is not straightforward. The contribution of this paper is twofold. First, we propose to apply voting rules, typically used in the field of social choice, as the aggregation technique for label ranking ensembles. Our evaluation reveals that there is no single rule that consistently outperforms all other voting rules, and that under different settings different voting rules perform the best. Second, we propose a novel aggregation method for label ranking ensembles that learns the best voting rule to be used in a given setting. An extensive evaluation of the proposed method on semi-synthetic as well as real-world datasets shows that it obtains prediction performance that is significantly higher than that of the aggregation techniques currently used by state-of-the-art label ranking ensembles.

We propose a secure voting protocol for score-based voting rules, where independent talliers perform the tallying procedure. The protocol outputs the winning candidate(s) while preserving the privacy of the voters and the secrecy of the ballots. It offers perfect secrecy, in the sense that apart from the desired output, all other information – the ballots, intermediate values, and the final scores received by each of the candidates – is not disclosed to any party, including the talliers. Such perfect secrecy may increase the voters’ confidence and, consequently, encourage them to vote according to their true preferences. The protocol is extremely lightweight, and therefore it can be easily deployed in real life voting scenarios.

Group decisions are often complicated by a deadline. For example, in committee hiring decisions the deadline might be the next start of a budget, or the beginning of a semester. It may be that if no candidate is supported by a strong majority, the default is to hire no one - an option that may cost dearly. As a result, committee members might prefer to agree on a reasonable, if not necessarily the best, candidate, to avoid unfilled positions. In this paper we propose a model for the above scenario—Consensus Under a Deadline (CUD)—based on a time-bounded iterative voting process. We provide convergence guarantees and an analysis of the quality of the final decision. An extensive experimental study demonstrates more subtle features of CUDs, e.g., the difference between two simple types of committee member behavior, lazy vs. proactive voters. Finally, a user study examines the differences between the behavior of rational voting bots and real voters, concluding that it may often be best to have bots play on the voters’ behalf.

Sometimes voters are required to reach a joint decision and find an item that best suits the group’s preferences. Voters may wish to state preferences only when necessary, particularly in cases where there are many available options, therefore it is unpractical to assume that all voter preferences are known at all times. In order to elicit voter preferences at a minimal cost, a preference elicitation process is required. We introduce a general approach for reaching a joint decision with minimal elicitation of voter preferences. The approach is probabilistic and uses voting rules to find a necessary winning item which is presented to the group as their best option. We propose computing a voter-item probability distribution and developing methods based on this distribution that can then determine which voter-item pair to query. Computing the optimal minimal set of voter-item queries is computationally intractable; therefore we propose novel heuristic algorithms, named DIG and ES, which proceed iteratively until the identification of a winning item. The probabilistic voting distribution is updated as more information is revealed. Experiments on simulated data examine the benefits of each of the algorithms under different settings. Experiments with the real-world Netflix data show that the proposed algorithms reduce the required number of ratings for identifying the winning item by more than 50%.

Group Recommendation Systems (GRS) aim at recommending items that are relevant for the joint interest of a group of users. Voting mechanisms assume that users rate all items in order to identify an item that suits the preferences of all group members. This assumption is not feasible in sparse rating scenarios which are common in the recommender systems domain. In this paper we examine an application of voting theory to GRS. We propose a method to accurately determine the winning item while using a minimal set of the group members ratings, assuming that the recommender system has probabilistic knowledge about the distribution of users' ratings of items in the system. Since computing the optimal minimal set of ratings is computationally intractable, we propose two heuristic algorithms that proceed iteratively that aiming atto minimizing the number of required ratings, until identifying a "winning item". Experiments with the Netflix data show that the proposed algorithms reduce the required number of ratings for identifying the "winning item" by more than 50%.