A Salient Ensemble of Trees using Cascaded Linear Classifiers with Feature-Cost Constraints

Abstract In many applications the classification model needs to utilize limited resources properly while predicting an instance, e.g. the limited response time for a real-time search engine. In order to satisfy the resource constraint, many researchers try to simplify the model structure or shrink the feature subset size. Because the informative features may take too much cost for the model, a common way is to build a model by considering the trade-off between performance and cost. However, most previous works assume that the cost of a feature is independent of the cost of another feature, which is not practical in reality. In the paper, we consider two categories of the feature cost, individual cost and group cost. The former is independent of the cost of any other feature whereas the latter regards the cost dependency between the other features in the corresponding group. We propose a two-stage framework that integrates the cost-sensitive feature selection and learning a model with a cost budget constraint. First, we propose the group-cost-sensitive random forest (GOAT) model to consider these two costs to select a proper feature subset. Second, we propose a salient ensemble of trees each of which uses cascaded linear classifiers (ETIC) with the satisfaction of the featurecost constraints using the derived features from the GOAT model. We conduct experiments on real-world datasets, including mobile-user preference data and object detection data. When the group cost dominates, GOAT-ETIC can gain a 10–30% improvement over the baselines. Even if the group cost is ignored, GOAT-ETIC can still get better performance than the state-of-the-arts.