Data as voters: instance selection using approval-based multi-winner voting

Overview

• Presents a new approach to the instance selection problem in machine learning and data mining
• Leverages recent research on proportional representation in approval-based multi-winner elections
• Instances play a dual role as both voters and candidates in the model
• Selects "election winners" as the reduced training set instances

Plain English Explanation

The paper introduces a novel way to reduce the size of a machine learning training dataset while trying to maintain the accuracy of the model. The key idea is to treat the data instances (e.g., individual data points) as both "voters" and "candidates" in an approval-based multi-winner election.

Each instance in the original training set acts as a "voter" and defines its "approval set" based on a concept called the "local set" (which is already known in the literature). Then, a voting rule is used to select the "winners" of this election, and those winners become the instances that are kept in the reduced training set.

The researchers found that for K-Nearest Neighbors (KNN) models, a particular voting rule called "Simple 2-EJR" outperformed other state-of-the-art algorithms in terms of accuracy versus the amount of reduction in the training set size. For Support Vector Machines (SVMs), they saw slight increases in average accuracy by using voting rules that satisfy certain properties like Extended justified representation (EJR) or Proportional justified representation (PJR).

Technical Explanation

The paper proposes a novel approach to the instance selection problem, which aims to reduce the size of a machine learning training dataset while preserving its quality. The key idea is to leverage recent results on proportional representation in approval-based multi-winner elections.

In the proposed model, each instance in the training set plays a dual role as both a "voter" and a "candidate" in an approval-based election. The "approval set" of each instance (acting as a voter) is defined based on the concept of a "local set", which is already established in the literature.

The researchers then use a representative voting rule to select the "winners" of this election, and these winners become the instances that are kept in the reduced training set.

The paper presents experimental results for two common machine learning models: K-Nearest Neighbors (KNN) and Support Vector Machines (SVMs). For KNN, the researchers found that a variant of the "Simple EJR" voting rule, called "Simple 2-EJR", outperformed other state-of-the-art algorithms and baselines in terms of accuracy versus reduction. For SVMs, they obtained slight increases in average accuracy by using voting rules that satisfy the EJR or PJR properties.

Critical Analysis

The paper presents a novel and intriguing approach to the instance selection problem, but it does not address several important considerations. The authors do not provide a detailed analysis of the computational complexity of their proposed method, which could be a significant factor, especially for large-scale datasets. Additionally, the paper does not explore the sensitivity of the results to the choice of the "local set" definition or the specific voting rules used.

Another potential limitation is the reliance on accuracy as the primary evaluation metric. In many real-world applications, other performance measures, such as interpretability or robustness, may be equally or more important. The paper would benefit from a more comprehensive evaluation of the proposed method's impact on these other relevant metrics.

Further research could also investigate the theoretical properties of the instance selection approach, such as its convergence guarantees or the optimality of the selected instances under different assumptions or constraints.

Conclusion

The presented research offers a novel perspective on the instance selection problem in machine learning, drawing inspiration from the field of approval-based multi-winner elections. By treating data instances as both voters and candidates, the authors develop a unique approach to reducing the size of training datasets while attempting to preserve model accuracy.

The experimental results demonstrate promising performance, especially for KNN models, and suggest that voting rules satisfying certain properties can be beneficial for SVMs as well. However, the paper also highlights the need for further investigation into the computational complexity, sensitivity to design choices, and broader performance implications of the proposed method.

Overall, this work represents an interesting contribution to the ongoing efforts to develop efficient and effective data selection techniques in the field of machine learning and data mining.