Label shift, which investigates the adaptation of label distributions between the fixed source and target domains, has attracted significant research interests and broad applications in offline settings. In real-world scenarios, however, data often arrives as a continuous stream. Addressing label shift in online learning settings is paramount. Existing strategies, which tailor traditional offline label shift techniques to online settings, have degraded performance due to the inconsistent estimation of label distributions and violation of convex assumption for theoretical guarantee. In this paper, we propose a novel method to ensure consistent adaptation to online label shift. We construct a new convex risk estimator that is pivotal for both online optimization and theoretical analysis. Furthermore, we enhance an optimistic online algorithm as the base learner and refine the classifier using an ensemble method. Theoretically, we derive a universal dynamic regret which achieves minimax optimal. Extensive experiments on both real-world datasets and human motion task demonstrate the superiority of our method comparing existing methods.

Applying current machine learning algorithms in complex and open environments remains challenging, especially when different changing elements are coupled and the training data is scarce. For example, in the activity recognition task, the motion sensors may change position or fall off due to the intensity of the activity, leading to changes in feature space and finally resulting in label noise. Learning from such a problem where the dynamic features are coupled with noisy labels is crucial but rarely studied, particularly when the noisy samples in new feature space are limited. In this paper, we tackle the above problem by proposing a novel two-stage algorithm, called Adaptive Learning for Dynamic features and Noisy labels (ALDN). Specifically, optimal transport is first modified to map the previously learned heterogeneous model to the prior model of the current stage. Then, to fully reuse the mapped prior model, we add a simple yet efficient regularizer as the consistency constraint to assist both the estimation of the noise transition matrix and the model training in the current stage. Finally, two implementations with direct (ALDN-D) and indirect (ALDN-ID) constraints are illustrated for better investigation. More importantly, we provide theoretical guarantees for risk minimization of ALDN-D and ALDN-ID. Extensive experiments validate the effectiveness of the proposed algorithms.

Learning from data streams collected sequentially over time are widely spread in real-world applications. Previous methods typically assume that the data stream has a feature space with a fixed or clearly defined evolution pattern, as well as a balanced class distribution. However, in many practical scenarios, such as environmental monitoring systems, the frequency of anomalous events is significantly imbalanced compared to normal ones and the feature space dynamically changes due to ecological evolution and sensor lifespan. To alleviate this important but rarely studied problem, we propose the Adaptive Learning in Imbalace data streams with Unpredictable feature evolution (ALIU) algorithm. As data streams with imbalanced class distribution arrive, ALIU first mitigates the model's bias for the majority class by reweighting the adaptive gradient descent magnitudes between different classes. Then, a new loss function is proposed that simultaneously focuses on misclassifications and maintains model robustness. Further, when imbalanced data streams arrive with feature evolutions, we reuse the previously learned model and update the incomplete and augmented features by adopting the adaptive gradient strategy and ensemble method, respectively. Finally, we utilize the projected technique to build a sparse yet efficient model. Based on a few common and mild assumptions, we theoretically analyze that the ALIU satisfies a sub-linear regret bound under both convex and strong convex loss functions and the performance of model can be improved with the assistance of old features. Besides, extensive experimental results further demonstrate the effectiveness of our proposed algorithm.

Multi-instance Learning (MIL) is a popular learning paradigm arising from many real applications. It assigns a label to a set of instances, which is called a bag, and the bag’s label is determined by the instances within it. A bag is positive if and only if it has at least one positive instance. Since labeling bags is more complicated than labeling each instance, we will often face the mislabeling problem in MIL. Furthermore, it is more common that a negative bag has been mislabeled to a positive one, since one mislabeled instance will lead to the change of the whole bag label. This is an important problem that originated from real applications, e.g., web mining and image classification, but little research has concentrated on it as far as we know. In this article, we focus on this MIL problem with one side label noise that the negative bags are mislabeled as positive ones. To address this challenging problem, we propose, to the best our our knowledge, a novel multi-instance learning method with one side label noise. We design a new double weighting approach under traditional framework to characterize the “faithfulness” of each instance and each bag in learning the classifier. Briefly, on the instance level, we employ a sparse weighting method to select the key instances, and the MIL problem with one size label noise is converted to a mislabeled supervised learning scenario. On the bag level, the weights of bags, together with the selected key instances, will be utilized to identify the real positive bags. In addition, we have solved our proposed model by an alternative iteration method with proved convergence behavior. Empirical studies on various datasets have validated the effectiveness of our method.

In many real-world applications, data may dynamically expand over time in both volume and feature dimensions. Besides, they are often collected in batches (also called blocks). We refer this kind of data whose volume and features increase in blocks as blocky trapezoidal data streams. Current works either assume that the feature space of data streams is fixed or stipulate that the algorithm receives only one instance at a time, and none of them can effectively handle the blocky trapezoidal data streams. In this article, we propose a novel algorithm to learn a classification model from blocky trapezoidal data streams, called learning with incremental instances and features (IIF). We attempt to design highly dynamic model update strategies that can learn from increasing training data with an expanding feature space. Specifically, we first divide the data streams obtained on each round and construct the corresponding classifiers for these different divided parts. Then, to realize the effective interaction of information between each classifier, we utilize a single global loss function to capture their relationship. Finally, we use the idea of ensemble to achieve the final classification model. Furthermore, to make this method more applicable, we directly transform it into the kernel method. Both theoretical analysis and empirical analysis validate the effectiveness of our algorithm.

With the emergence of new data collection ways in many dynamic environment applications, the samples are gathered gradually in the accumulated feature spaces. With the incorporation of new type features, it may result in the augmentation of class numbers. For instance, in activity recognition, using the old features during warm-up, we can separate different warm-up exercises. With the accumulation of new attributes obtained from newly added sensors, we can better separate the newly appeared formal exercises. Learning for such simultaneous augmentation of feature and class is crucial but rarely studied, particularly when the labeled samples with full observations are limited. In this paper, we tackle this problem by proposing a novel incremental learning method for Simultaneous Augmentation of Feature and Class (SAFC) in a two-stage way. To guarantee the reusability of the model trained on previous data, we add a regularizer in the current model, which can provide solid prior in training the new classifier. We also present the theoretical analyses about the generalization bound, which can validate the efficiency of model inheritance. After solving the one-shot problem, we also extend it to multi-shot. Experimental results demonstrate the effectiveness of our approaches, together with their effectiveness in activity recognition applications.

Online learning is a fundamental paradigm for learning from continuous data stream. Tradition online learning approaches usually assume that the feature space of data stream is fixed and the incoming instance can always get the true label after making its prediction. However, in many real-world applications, such as the personalized recommender systems, the feature space may keep expanding due to the accumulation of user behaviors. Besides, we may only get bandit feedback, i.e., we only know whether the prediction is correct or not. To solve this important but rarely studied problem, we propose a novel algorithm LIFBF, together with its two variants LIFBF-I and LIFBF-II, to learn from data stream with incremental feature space and bandit feedback. Specifically, when an instance arrives with augmented features, we first utilize the exploration-exploitation strategy to guess its best label, then, a new loss function considering both bandit feedback and guessed label is proposed. Finally, we design a highly dynamic multi-class classifier, which updates the shared and augmented features by adopting the passive-aggressive rule and structural risk minimization principle, respectively. We theoretically analyze the cumulative loss bound of LIFBF. Besides, empirical studies on various datasets further validate the effectiveness of our proposed algorithms.

Recently, learning and mining from data streams with incremental feature spaces have attracted extensive attention, where data may dynamically expand over time in both volume and feature dimensions. Existing approaches usually assume that the incoming instances can always receive true labels. However, in many real-world applications, e.g., environment monitoring, acquiring the true labels is costly due to the need of human effort in annotating the data. To tackle this problem, we propose a novel incremental Feature spaces Learning with Label Scarcity (FLLS) algorithm, together with its two variants. When data streams arrive with augmented features, we first leverage the margin-based online active learning to select valuable instances to be labeled and thus build superior predictive models with minimal supervision. After receiving the labels, we combine the online passive-aggressive update rule and margin-maximum principle to jointly update the dynamic classifier in the shared and augmented feature space. Finally, we use the projected truncation technique to build a sparse but efficient model. We theoretically analyze the error bounds of FLLS and its two variants. Also, we conduct experiments on synthetic data and real-world applications to further validate the effectiveness of our proposed algorithms.