## 2 The Skeptical Learning Algorithm
### The Main Algorithm  
The pseudocode of SkeL is reported in Algorithm 1. To keep the description simple, and without a loss of generality, we assume below that there is a single property of interest \(P\), e.g., the location or the transportation means of the user at a certain time. We represent by \(\mathcal{Y}\) the set of possible values for this property. SkeL can be in one of three modalities that, for simplicity, we assume are activated sequentially, namely: _Train_ mode performed in usual supervised learning, _Refine_ mode, where it checks the quality of the user answers and, under certain conditions, it challenges them, and the _Regime_ mode, where it starts being autonomous and only queries the user for particularly ambiguous instances. The algorithm takes as an input a confidence threshold \(\theta\). It starts by initializing the user confidence \(\mathbf{c}^{\mathrm{u}}\) to one and the predictor confidence \(\mathbf{c}^{\mathrm{P}}\) to zero for all classes (\(|\mathbf{c}^{\mathrm{u}}|=|\mathbf{c}^{\mathrm{P}}|=|\mathcal{Y}|\)). Then, the training phase begins. The algorithm collects sensor readings (\(\mathbf{x}_{t}\)) to be used as an input for the predictor. The system then asks the user for a label (\(y_{t}\)), with the goal of using it as ground truth. The input-output pair trains the predictor by following the train procedure. This can be carried out either via batch learning (where the predictor is retrained from scratch) or via an online learning step [13], where the new input-output pair is used to refine the current predictor. The choice between these learning modalities depends on the specific implementation and constraints, e.g., the storage capacity; see the experiment described below. After training, the confidence of the predictor is modified via the update procedure, which takes as an input the ground truth label and the one predicted _before_ the training step. The update procedure takes as an input a confidence vector, a tentative label (\(\hat{y}_{t}\)), and a ground truth label (\(y_{t}\)), and updates the confidence vector according to the relationship between the two labels. The new confidence vector computed is as a label-wise running average accuracy over the current and past predictions, for a certain window size \(d\). Notice that the confidence updates are applied not only to the predicted and ground truth label pair, but also to all implied label pairs according to the SK, i.e., those from the root to the predicted (respectively) ground truth label. The training stage stops when the system is confident enough to challenge the user label. Equation (1) shows the computation of the confidence in a prediction label \(y\). \(c_{y}^{\mathrm{P}}\) is the confidence that the predictor has in label \(y\). Since the predictor is implemented as a set of classifiers matching the hierarchy shown in Figure 2 (the details of the predictor will be introduced in the next section), we use function \(f_{\textsc{parent}(y)}(\mathbf{x},y)\) to present the score of the prediction label \(y\) generated by the classifier on \(y\)'s parent node. \[\textsc{Conf}(\mathbf{x},y,c_{y}^{\mathrm{P}}):=c_{y}^{\mathrm{P}}\cdot f_{ \textsc{parent}(y)}(\mathbf{x},y) \tag{1}\]  
when a predicted label is compared with a user-provided label, care must be taken in making a sensible comparison. If the two labels belong to different branches of the hierarchy (e.g., _Train_ and _On foot_ in Figure 2), they cannot be directly compared, as confidences are normalized across siblings. Therefore, the system recovers all of the labels in the hierarchy up to the first common root, i.e., _the least common subsumer_[8], and compares them instead of the original ones. Thus, for instance, in the previous example, _Train_ implies _In vehicle_, which is then compared to _On foot_, as they are both children of _On the move_.