Feature Acquisition using Monte Carlo Tree Search

Many machine-learning algorithms work with the assumption that all features have been observed and available during training and testing times or the missing data are disregarded as unacquired. Feature acquisition, a process in which further relevant data are acquired at variable costs, addresses this assumption to more closely align with some real-world applications, Huang [3]. For medical diagnostic tasks, from the basis of incomplete features, doctors sequentially obtain additional test results until they obtain sufficient information to make adequate diagnoses of the patients. Determining which features to acquire is dependent on the previous diagnostic observations and the sequence at which the features are obtained can vary from patient to patient. Although accurate diagnoses are more likely with additional features, acquiring them incurs variable costs and is balanced with the improvement in performance, Melville [1]. Previous studies on the feature acquisition problem address the trade-off between acquisition costs and performance improvement and the sequential decision making process, and are categorized into non-reinforcement learning and reinforcement learning (RL) approaches. Non-RL approaches focus on selecting the most informative features to acquire based on their utility values. These methods, Melville [1], desJardins [2], and Huang [3], estimate the expected utility of a feature for improving the model performance and acquire the feature with maximum expected utility.