Rule lists, one of the best-known rule-based models, have been intensively studied in recent years because its high interpretability is desirable for use in important decision-making tasks. Although rule lists often achieve relatively higher accuracy than other rule-based models such as decision trees, they still have considerably lower accuracy than complex, uninterpretable models such as deep neural networks or large tree ensembles. In this paper, in order to improve the accuracy of rule lists, we propose a new model called a top-k rule list. In contrast to the traditional rule list, which makes a prediction by using the first rule in the list whose conditions are satisfied by the input, the top-k rule list utilizes an ensemble of the first k rules instead of just the first one. The top-k rule list can be viewed as a generalization of the traditional rule list, which is a special case with \(k=1\) , and this generalization enables the user to obtain a preferable trade-off between accuracy and interpretability by selecting different values of k. Learning the traditional rule list is known as a computationally hard combinatorial optimization problem, and learning the top-k rule list can be even harder because multiple rules must be considered for each prediction. To enable efficient learning, we propose an integer linear programming formulation for learning the top-k rule list, and effectively reduce the number of variables and constraints by introducing an assumption that the rules are ordered by certainty score. The experimental results show that the top-k rule list learned with the ILP formulation for \(k>1\) outperformed the traditional rule list in accuracy for most datasets.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Top-k Rule List Learning via Integer Linear Programming

  • Yoichi Sasaki,
  • Yuzuru Okajima

摘要

Rule lists, one of the best-known rule-based models, have been intensively studied in recent years because its high interpretability is desirable for use in important decision-making tasks. Although rule lists often achieve relatively higher accuracy than other rule-based models such as decision trees, they still have considerably lower accuracy than complex, uninterpretable models such as deep neural networks or large tree ensembles. In this paper, in order to improve the accuracy of rule lists, we propose a new model called a top-k rule list. In contrast to the traditional rule list, which makes a prediction by using the first rule in the list whose conditions are satisfied by the input, the top-k rule list utilizes an ensemble of the first k rules instead of just the first one. The top-k rule list can be viewed as a generalization of the traditional rule list, which is a special case with \(k=1\) , and this generalization enables the user to obtain a preferable trade-off between accuracy and interpretability by selecting different values of k. Learning the traditional rule list is known as a computationally hard combinatorial optimization problem, and learning the top-k rule list can be even harder because multiple rules must be considered for each prediction. To enable efficient learning, we propose an integer linear programming formulation for learning the top-k rule list, and effectively reduce the number of variables and constraints by introducing an assumption that the rules are ordered by certainty score. The experimental results show that the top-k rule list learned with the ILP formulation for \(k>1\) outperformed the traditional rule list in accuracy for most datasets.