Online Partitioned Local Depth for semi-supervised applications
This work addresses the need for efficient online learning in semi-supervised settings, particularly for health-care data, but it is incremental as it builds on existing PaLD methods with speed improvements.
The authors tackled the problem of adapting partitioned local depth (PaLD) for online semi-supervised applications by introducing an online PaLD algorithm that extends cohesion networks to new data points in O(n^2) time after an O(n^3) pre-computation step, with applications demonstrated in online anomaly detection and semi-supervised classification for health-care datasets.
We introduce an extension of the partitioned local depth (PaLD) algorithm that is adapted to online applications such as semi-supervised prediction. The new algorithm we present, online PaLD, is well-suited to situations where it is a possible to pre-compute a cohesion network from a reference dataset. After $O(n^3)$ steps to construct a queryable data structure, online PaLD can extend the cohesion network to a new data point in $O(n^2)$ time. Our approach complements previous speed up approaches based on approximation and parallelism. For illustrations, we present applications to online anomaly detection and semi-supervised classification for health-care datasets.