  We introduce online probabilistic label trees (OPLTs), an algorithm that
trains a label tree classifier in a fully online manner without any prior
knowledge about the number of training instances, their features and labels.
OPLTs are characterized by low time and space complexity as well as strong
theoretical guarantees. They can be used for online multi-label and multi-class
classification, including the very challenging scenarios of one- or few-shot
learning. We demonstrate the attractiveness of OPLTs in a wide empirical study
on several instances of the tasks mentioned above.
