Boosting the kernelized shapelets: Theory and algorithms for local features
This work addresses the lack of theoretical understanding and reliance on heuristics in local feature-based classification, offering a more robust approach for applications like time-series analysis.
The paper tackles the problem of binary classification using local features, particularly in time-series classification, by formulating a class of hypotheses with kernel-controlled feature richness and deriving exponentially better generalization bounds for sparse ensembles. The resulting method achieves competitive accuracy with state-of-the-art algorithms on time-series datasets with reduced parameter-tuning cost.
We consider binary classification problems using local features of objects. One of motivating applications is time-series classification, where features reflecting some local closeness measure between a time series and a pattern sequence called shapelet are useful. Despite the empirical success of such approaches using local features, the generalization ability of resulting hypotheses is not fully understood and previous work relies on a bunch of heuristics. In this paper, we formulate a class of hypotheses using local features, where the richness of features is controlled by kernels. We derive generalization bounds of sparse ensembles over the class which is exponentially better than a standard analysis in terms of the number of possible local features. The resulting optimization problem is well suited to the boosting approach and the weak learning problem is formulated as a DC program, for which practical algorithms exist. In preliminary experiments on time-series data sets, our method achieves competitive accuracy with the state-of-the-art algorithms with small parameter-tuning cost.