Chaitanya Manapragada

Chaitanya Manapragada, Laurent Decreusefond, Philippe Martins

It is critical to dimension (accurately estimate capacity of) a satellite system prior to deployment, as it is very expensive to reconfigure launched satellite systems that fail to meet demand or that waste capacity. The fundamental requirement is a dimensioning rule for resource blocks (RBs) given a satellite footprint and a target overload probability (target Quality-of-Service). The rule must be robust to the spatial covariance structure of signal attenuation, which is generally unknown both at the time of pre-deployment dimensioning and afterwards. Existing approaches address parts of this problem, but there does not yet exist a footprint-level RB dimensioning rule for the satellite context. We develop such a rule: starting with a Gaussian attenuation field that induces a covariance structure inspired by classical work on spatial covariance of attenuation, we sample users at random along with their field-based attenuation values, and estimate aggregate RB demand for a target overload probability. We do this in two complementary ways: a Monte Carlo route that gives a simulation-derived RB budget for a given target overload probability, and a concentration route that gives a conservative analytic upper bound on the target overload probability for a given RB budget (such as the one obtained through simulation). Taken together, these complementary approaches give a principled way to dimension RBs for a satellite footprint under spatially correlated attenuation.

Chaitanya Manapragada, Heitor M Gomes, Mahsa Salehi et al.

Decision tree ensembles are widely used in practice. In this work, we study in ensemble settings the effectiveness of replacing the split strategy for the state-of-the-art online tree learner, Hoeffding Tree, with a rigorous but more eager splitting strategy that we had previously published as Hoeffding AnyTime Tree. Hoeffding AnyTime Tree (HATT), uses the Hoeffding Test to determine whether the current best candidate split is superior to the current split, with the possibility of revision, while Hoeffding Tree aims to determine whether the top candidate is better than the second best and if a test is selected, fixes it for all posterity. HATT converges to the ideal batch tree while Hoeffding Tree does not. We find that HATT is an efficacious base learner for online bagging and online boosting ensembles. On UCI and synthetic streams, HATT as a base learner outperforms HT within a 0.05 significance level for the majority of tested ensembles on what we believe is the largest and most comprehensive set of testbenches in the online learning literature. Our results indicate that HATT is a superior alternative to Hoeffding Tree in a large number of ensemble settings.

Chaitanya Manapragada, Geoffrey I Webb, Mahsa Salehi et al.

Hoeffding trees are the state-of-the-art methods in decision tree learning for evolving data streams. These very fast decision trees are used in many real applications where data is created in real-time due to their efficiency. In this work, we extricate explanations for why these streaming decision tree algorithms for stationary and nonstationary streams (HoeffdingTree and HoeffdingAdaptiveTree) work as well as they do. In doing so, we identify thirteen unique unspecified design decisions in both the theoretical constructs and their implementations with substantial and consequential effects on predictive accuracy---design decisions that, without necessarily changing the essence of the algorithms, drive algorithm performance. We begin a larger conversation about explainability not just of the model but also of the processes responsible for an algorithm's success.

Chaitanya Manapragada, Geoff Webb, Mahsa Salehi

We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree---"Extremely Fast Decision Tree", a minor modification to the MOA implementation of Hoeffding Tree---obtains significantly superior prequential accuracy on most of the largest classification datasets from the UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in the limit, is naturally resilient to concept drift, and can be used as a higher accuracy replacement for Hoeffding Tree in most scenarios, at a small additional computational cost.