Classification with costly features as a sequential decision-making problem
- PDF / 2,199,044 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 238 Views
Classification with costly features as a sequential decision‑making problem Jaromír Janisch1 · Tomáš Pevný1 · Viliam Lisý1 Received: 5 April 2019 / Revised: 29 January 2020 / Accepted: 17 February 2020 © The Author(s), under exclusive licence to Springer Science+Business Media LLC, part of Springer Nature 2020
Abstract This work focuses on a specific classification problem, where the information about a sample is not readily available, but has to be acquired for a cost, and there is a per-sample budget. Inspired by real-world use-cases, we analyze average and hard variations of a directly specified budget. We postulate the problem in its explicit formulation and then convert it into an equivalent MDP, that can be solved with deep reinforcement learning. Also, we evaluate a real-world inspired setting with sparse training datasets with missing features. The presented method performs robustly well in all settings across several distinct datasets, outperforming other prior-art algorithms. The method is flexible, as showcased with all mentioned modifications and can be improved with any domain independent advancement in RL. Keywords Sequential classification · Costly features · Adaptive feature acquisition · Datum-Wise classification · Prediction on budget
1 Introduction Classification with Costly Features (CwCF) is a family of classification problems with a cost of acquiring information. This cost can appear in many forms. Usually, it is about money or time, but it is present in any domain with limited resources. We view the problem as a sequential decision-making problem. At each step, based on the information acquired so far, the algorithm has to decide whether to acquire another piece of information (a feature) or to classify. Think about a doctor who is about to make a diagnosis for their patient. There are a number of examinations, tests or analysis which can be made, but each of them has a cost. Editor: Hendrik Blockeel. * Jaromír Janisch [email protected] Tomáš Pevný [email protected] Viliam Lisý [email protected] 1
Artificial Intelligence Center, Department of Computer Science, Faculty of Electrical Engineering, Czech Technical University in Prague, Prague, Czech Republic
13
Vol.:(0123456789)
Machine Learning
As much as the doctor wants to make a reliable prediction, they are bound by their average budget they should not exceed. Naturally, patients with complicated diseases require more complicated and expensive tests, while trivial problems can be diagnosed with much fewer resources. Here, we use the medical domain only as an example, but there are several publications analyzing the use of CwCF in medicine, i.e., Peng et al. (2018) and Bayer-Zubek and Dietterich (2005). As another motivating example, imagine an online service that analyzes computer files potentially infected with malware. The service is bound by a service-level agreement and has to provide a decision in a specified time, and this time cannot be exceeded. This is an example of a hard budget. The process ca
Data Loading...
