A Latent Source Model for Nonparametric Time Series Classification
For classifying time series, a nearest-neighbor approach is widely used in practice with performance often competitive with or better than more elaborate methods such as neural networks, decision trees, and support vector machines. We develop theoretical justification for the effectiveness of nearest-neighbor-like classification of time series. Our guiding hypothesis is that in many applications, such as forecasting which topics will become trends on Twitter, there aren't actually that many prototypical time series to begin with, relative to the number of time series we have access to, e.g., topics become trends on Twitter only in a few distinct manners whereas we can collect massive amounts of Twitter data. To operationalize this hypothesis, we propose a latent source model for time series, which naturally leads to a "weighted majority voting" classification rule that can be approximated by a nearest-neighbor classifier. We establish nonasymptotic performance guarantees of both weighted majority voting and nearest-neighbor classification under our model accounting for how much of the time series we observe and the model complexity. Experimental results on synthetic data show weighted majority voting achieving the same misclassification rate as nearest-neighbor classification while observing less of the time series. We then use weighted majority to forecast which news topics on Twitter become trends, where we are able to detect such "trending topics" in advance of Twitter 79% of the time, with a mean early advantage of 1 hour and 26 minutes, a true positive rate of 95%, and a false positive rate of 4%.
The authors examine theoretically and empirically 
      properties of the k=1-nearest neighbor classification (NN) and a trivial 
      variant of the kernel density classification, called “weighted majority 
      voting”, in a time-series binary classification problem. For theoretical 
      analysis, a simplified generative model for time-series is introduced. 
      Under this model, they provide non-asymptotic performance guarantees in 
      terms of how large of a training dataset and how much of the time-series 
      length to be classified. Although the theoretical analysis is 
      technically sound, the empirical work will be incomplete. In the 
      experiments, the weighted majority voting and the NN are just tested while 
      data analysts would at least use the k-NN, rather than the NN, with a 
      tuned ‘k’ by cross-validation or so. I think the authors should apply k-NN 
      as a baseline. Otherwise, I feel that they evaluate the presented results 
      only from advantageous viewpoint. Also there exist several methods [i, ii, 
      iii] similar to the (proposed) weighted majority voting. The 
      linkage between theoretical and empirical parts seems to be week. While 
      the presented upper error-bound of the NN seems to be always lower than or 
      equal to that of the weighted majority voting, the weighted majority 
      voting outperformed the NN in the experiments. Some careful discussion 
      about this will be needed for the final version. Minors: - It 
      would be better to explain why the summations over time shifts need to be 
      replaced by the minimums in Eq. (7). - To understand the claims such 
      in lines 284~286, where the constant factor of (\theta + 1/\theta) in Eq. 
      (10) can be replace by 1, Remark in the supplementary material is 
      essential. The authors should introduce the content in the remark in the 
      main paper. - It would be helpful for readers if the bounds of Eq (10) 
      and (13) are plotted with respected to G with various settings of \gamma 
      and \sigma. - There is no conclusion or summary section. [i] 
      Sahibsingh A. Dudani: The distance-weighted k-nearest neighbor rule, IEEE 
      Transactions on System, Man, and Cybernetics, 6 (1976), 325-327. 
      [ii]Thanh N. Tran, Ron Wehrens, Lutgarde M. C. Buydens: KNN-kernel 
      density-based clustering for high-dimensional multivariate data. 
      Computational Statistics & Data Analysis 51(2): 513-525 (2006). 
      [iii] Jianping Gou, Taisong Xiong, Yin Kuang: A Novel Weighted Voting 
      for K-Nearest Neighbor Rule. JCP 6(5): 833-840 (2011)