IDK Cascades for Time-Series Input Streams

An IDK classifier is a software component that attempts to categorize each input provided to it into one of a fixed set of classes, returning IDK (“I Don’t Know”) if it is unable to do so with the required level of confidence. Several different IDK classifiers may be available for the same classification problem, each offering a different trade-off between execution duration and the likelihood of successful classification. Algorithms have been obtained for determining the order in which such classifiers should be called such that the expected duration to successfully classify an input is minimized-such an ordering of classifiers is called an IDK cascade. Cascade-synthesis algorithms make the assumption that each input to be classified is drawn from the same underlying distribution. We derive runtime algorithms that seek to further reduce the expected response time of IDK cascades upon input sequences for which successive inputs are ‘similar’ in the following sense: if a particular classifier successfully classifies some input it is likely to also be able to classify the next input. We evaluate the effectiveness of our algorithms in the context of the algorithms using predictions framework by showing that it significantly reduces expected response time when the desired similarity between successive inputs exists, while suffering only a minor increase in expected response time in the absence of such similarity. We describe how our algorithm is able to learn during runtime whether similarities exist (and if so, to what degree) amongst its inputs.