Online Learning from Capricious Data Streams: A Generative Approach

1 Introduction

To date, many online learning approaches have been developed to handle streaming data [Zinkevich, 2003; Crammer et al., 2006; Nguyen et al., 2017]. Most of them assume that each data stream has a fixed feature space. Only a few recent studies have explored to learn from a dynamic feature space, yet they all make strong assumptions on the feature space dynamics, such as monotonically increasing, where later data instances should include increasingly more features [Zhang et al., 2016a], or batchly evolving, where a few consecutive data instances must include all possible features from the feature space [Hou et al., 2017]. Unfortunately, these assumptions do not always hold in real applications. For example, in a smart healthcare platform [Baig and Gholamhosseini, 2013], features describing the symptoms of patients vary across IoT devices (thermometers, pulse monitors, respiratory sensors,

. . .

. . .

Figure 1: Na¨ıve way of learning from a varying feature space. The weight coefficient wi (marked in dark gray) of the corresponding new feature is initialized as zero.

etc.) and service providers (hospitals, labs, insurance companies, etc.). This means that the patient data are streaming with an arbitrarily varying feature space. We refer to such data streams as capricious data streams.

At the first glance, one may think to adapt existing algorithms, such as Online Convex Optimization (OCO) [Zinkevich, 2003], for handling capricious data streams. Figure 1 depicts such a learning paradigm. The learner is trained on an observable feature space which comprises the features carried by an arriving instance at the tth iteration. Alas, this approach does not work well and is limited in two aspects. First, although the new features (e.g., features 2 and 3 at the second iteration in Figure 1) enlarge the dimension of the learner's hypothesis set, they may not be described by a sufficient number of instances, leading to the curse of dimensionality [Duda et al., 2012]. Second, when the features that have been observed by the learner become unavailable in latter iterations, the learned patterns regarding these features are ignored [Hou et al., 2017]. As a result, the learner does not exert its full power to achieve the best prediction performance.

To overcome these limitations, we in this paper propose the Online learning from Capricious Data Streams (OCDS) algorithm by training a learner based on a universal feature space that includes the features appeared at each iteration. Introducing a universal feature space provides several advantages over an observable feature space. In the training phase, since the newly appeared features at the tth iteration are maintained in the universal feature space in all following iterations, the learner could benefit from being continuously provided information from them. In the predicting phase, the universal feature space is wider than the observable one, conveying additional information, so that the learner's prediction performance is improved.

The question, then, is how to obtain the universal feature space. On capricious data streams, an instance may not carry some features that are already included in the universal feature space. Taking the second iteration in Figure 1 as an example, the universal feature 1 is missing in the arriving instance. We call such missing features unobservable features, and the problem of obtaining the universal feature space is thus recast as reconstructing them.

We build upon a key insight that enables OCDS to infer unobservable features from observable ones: in practice there exist relatednesses among features [Zhang et al., 2013; Zhang et al., 2016b; Chen et al., 2005]. Specifically, OCDS uses a graph to capture feature relatednesses. Each vertex in the graph denotes a feature in the universal feature space, and all out-edges of a vertex together represent the relationship between the corresponding feature and the others. We embed the graph learning process into the online learning task. The effectiveness of OCDS is validated in three scenarios: trapezoidal data streams [Zhang et al., 2016a], feature evolvable streams [Hou et al., 2017], and capricious data streams.

Specific contributions in this paper are as follows:

1. This is the first work to learn with capricious data streams where data come with an arbitrarily varying feature space. We want to emphasize that our learning task does not make any assumption on the feature space dynamics, which is different from existing studies.
2. We introduce a generative graphical model, which takes the observable feature space as the input and outputs a universal feature space. We prove that the obtained universal feature space can effectively improve the learning performance of OCDS.
3. We analyze the performance bound of OCDS.

Due to the page limitation, we present the detailed proofs (derivations), time complexity analysis, and complete experimental results in the supplementary material [He et al., 2019].

2 RelatedWork

In this paper, we focus on learning data streams from a varying feature space. It is worthy pointing out that though concept-drift happens in streaming data where the underlying data distribution keeps changing [Gama and Rodrigues, 2009], the number of features carried by each instance is fixed in concept-drift, which is different from our learning task.

The studies related to our learning task include online learning from a fixed feature space [Zinkevich, 2003; Nguyen et al., 2017], from an incremental feature space [Zhou et al., 2012; Zhang et al., 2016a; Beyazit et al., 2018], and from an evolvable feature space [Masud et al., 2013; Hou et al., 2017]. Those approaches tackling the streaming data problem under different settings, however, rely on the assumptions that the feature space is fixed or changes by following explicit regularities. Thus, they cannot handle an arbitrarily varying feature space. A recent work by [Beyazit et al., 2019] lifted these assumptions, but it makes an implicit assumption that there are overlapping features among arriving instances. Our work makes no such assumption and thus has its own technical challenges and solutions.

The key idea of OCDS is to learn a reconstructive mapping by exploiting feature relatednesses. In this regard, our work is also related to the feature space reconstruction-based approaches [Li et al., 2017; Huang et al., 2018]. However, most of them focus on feature selection and extraction and to our best knowledge, none of them consider the varying of feature space during the learning process.

3 Preliminaries

We focus on binary classification in this paper. Multiclass problems could be decomposed to multiple binary classification subproblems, using One vs Rest [Xu, 2011] or One vs One [S´aez et al., 2014] strategies.

Learning Task Setup

Let {(xt, yt)|t = 1, 2, . . . , T} denote a sequence of arriving instances with labels, where xt = [x1, x2, . . . , xdt ]⊤ ∈ Rdt is a dt-dimensional vector and yt ∈ {-1,+1} represents the class label. At tth iteration, the learner observes the instance xt and then returns its prediction. The true label yt is revealed thereafter, and the learner suffers an instantaneous loss reflecting the discrepancy between the prediction and the groundtruth.

We define feature space as a set of features. Let Ut = {Rd1 ∪ Rd2 ∪ . . . ∪ Rdt } denote the universal feature space at the tth iteration where the features of x1, x2, . . . , xt are included. We in this paper restrict the discussion to a linear classifier wt based on a vector of weight coefficients, which is a common setting in online learning. If new features appear in xt, their corresponding weight coefficients in wt are initialized as zeros. As a result, the dimension of wt matches that of Ut, namely wt ∈ R|Ut| .

Generative Graphical Model

A generative graph is to embed a reconstructive mapping ψ: Rdt ↦→ Ut. Let G denote the graph whose vertices represent the features in Ut. The weight of each edge in G encodes a feature-wise relatedness. We define vertex approximator Φi as a vector containing the weights of all out-edges of a vertex i. The graph G thus can be represented by a matrix that comprises a set of vertex approximators, namely G = [Φ1, . . . , Φ|Ut|]⊤ ∈ R|Ut|×|Ut| .

We define the desired reconstruction of xt in the universal feature space as ut = [x1, . . . , xdt , ˜xdt+1, . . . , ˜x|Ut|]⊤ ∈ R|Ut| , where xi and ˜xj represent an original observable feature and a reconstructed unobservable feature, respectively. We infer ut by maximizing a log-likelihood function:

The features in Ut are inferred independently by given a vertex i and the corresponding Φi:

where uj denotes the j th feature in ut.

Without loss of generality, we let P(uj|xi,Φi) follow a Laplacian distribution [Liu et al., 2014; Park and Lee, 2005]:

where σ is a fixed variance [Gerven et al., 2009], and E(uj) is approximated based on ψ given xi and Φi (see Section 4.1).

4 Our Proposed Approach

The objective function of OCDS takes the form:

where the first term as a supervised loss function is minimized for classification purpose. The second term, a reconstruction error function, indicates the approximation between the desired ut and the reconstructed ψ(xt). The parameter α is introduced to absorb the different scales between the first two terms. The third term bounds the maximal dimension of the learning model by penalizing its complexity, with a regularization parameter λ.

In the rest of this section, we first present the building blockings of OCDS by elaborating the components in the objective function (4). The updating rules are derived thereafter. We finally discuss the prediction strategy in OCDS.

4.1 Learning fromReconstruction Error

In capricious data streams, the feature spaces between any two consecutive instances could be different, leading to a highly dynamic environment. Learning a complex reconstructive mapping based on existing methods [Pan et al., 2010; Sun, 2013] is thus unrealistic. We restrict our interest in finding a linear mapping relationship between two features. Specifically, we define E(uj) = Gi,jxi in (3), where Gi,j represents the weight of the out-edge from vertex i to j. Accordingly, maximizing (1) is equivalent to minimizing the following optimization problem w.r.t. G:

where Gr = ItG. It ∈ Rdt×|Ut| is an indicator matrix that represents which features in Ut are carried by xt. ‖ · ‖2 is an ℓ2-norm, and ΠRdt (·) is an operator that orthogonally projects ut and Gr⊤xt onto the Rdt feature space. Surprisingly, we can observe that the reconstruction error is minimized by (5) if the reconstructive mapping is defined as ψ(xt) = (1/dt)(Gr⊤xt). In Algorithm 1, we show how Gr is retrieved for solving (5), such that ψ(xt) is obtained. The main procedure of our retrieval strategy is to update G at each iteration. To improve the learning performance and save the computational cost, we reuse Φi of xi if xi has already been observed before. For any new feature xj carried by xt, we first build the out-edges between xj and the others, representing the relatednesses among features. The weights of these edges are then randomly initialized, comprising Φj.

Input: An arriving instance xt, It, and G 1 foreach feature xi ∈ xt do 2 if Φi exists in G then 3 foreach feature fj ∈ Ut do 4 if xj ∈ xt and Gi,j not exists then 5 Gi,j ← a random number r; 6 else if Φi not exists in G then 7 Initialize Φi = [ ]; 8 while |Φi| < |Ut| do 9 Φi.append (a random number r); 10 G.append (Φi); 11 returnGr ← ItG;

4.2 Learning from Supervised Loss

The accuracy of the universal feature space recovered by minimizing (5) may be affected when xt does not convey sufficient information, for example, xt only carries new features or the number of features in xt is few. To address this issue, we utilize the class label, an abstract representation of the reconstructed features, to provide extra supervised information for learning a better mapping ψ.

We train the learner by minimizing the supervised loss jointly along with the reconstruction error. With ψ(xt) = (1/dt)(Gr⊤xt), the supervised loss function is:

The dimension of wt will go infinite as the data keep streaming with new features. To bound the maximum dimension, penalizing the classifier with an ℓ1-norm regularizer is a common choice. This is because it encourages a sparse solution of wt in which the values of many weight coefficients are forced to be small or even zero. The dimension of wt could thus be bounded by truncating the smallest weight coefficients, with a ratio of γ.

The drawback of using the ℓ1-norm regularizer is that, since the feature space of capricious data streams varies arbitrarily, the generated solution becomes sensitive to the sequence of arriving instances. To obtain a robust solution, we take the structure of graph G, which represents the relationship between different features, into consideration. When a pair of features show strong dependency, the weight of the edge between them, i.e., Gi,j, is large, and their feature coefficients, i.e., wi and wj, should be similar. To achieve this, we add a graph regularizer onto ℓ1-norm. The formulation is:

where L is the graph Laplacian of G and β is a tradeoff parameter.

4.3 Updating Rules

By plugging (5), (6), and (7) into (4), our learning task is reduced to solve the Empirical Risk Minimization problem as below:

where ψ(xt) = (1/dt)((ItG)⊤xt), β1 = λβ, and β2 = 2λ(1-β). We prove that the main function (denoted by F) in (8) is bi-convex, providing a theoretical guarantee for convergence. To solve (8), we follow the common steps of solving a bi-convex optimization problem: (i) We divide (8) into two convex optimization subproblems, which are with respect to wt and G, respectively. (ii) The two subproblems are simultaneously solved at each iteration.

In this paper, we use Coordinate Gradient Descend [Tseng and Yun, 2009] as the optimizer for the subproblems. The updating rules for wt and G are defined accordingly: wt+1 = wt - τ∇wt F and G = G- τ∇GF, where τ = √1/t is a varied step size. In the updating rules, the partial derivatives (gradients) of F w.r.t. wt and G are calculated as below.

where ∂‖ · ‖1 denotes an entry-wise subdifferential operator.

4.4 Ensemble Prediction

Given ψ(xt) and the corresponding learner wt, conventionally the prediction is defined in an inner product form, namely 〈wt, ψ(xt)〉. To further improve the prediction performance, we can combine two base predictions based on xt, which contains the original observable features, and ˜xt = [˜xdt+1, . . . , ˜x|Ut|]⊤ ∈ R|Ut|-dt , which contains the reconstructed unobservable features:

where ¯wt and ˜wt, together forming wt, are the weight coefficients of xt and ˜xt, respectively. The value of p decides the impact of xt and ˜xt in making predictions. Such an ensemble prediction can eliminate the prediction errors caused by potential noises in the reconstructed observable features, which is likely to happen in the initial iterations when few data instances have been seen.

The prediction loss function ℓ(·) is convex in its first argument. In the implementation, we choose logistic loss for classification task, namely ℓ(y, ˆ y) = (1/ ln2) ln(1 + exp(-y ˆ y)). Let Lobs T = ∑Tt=1 ℓ(yt, 〈 ¯wt, xt〉) and Lrec T = ∑Tt=1 ℓ(yt, 〈 ˜wt, ˜xt〉) denote the cumulative losses suffered by making predictions on xt and ˜xt over T iterations, respectively. At the iteration T + 1, we update the parameter p in (11) based on exponential of the cumulative loss [CesaBianchi and Lugosi, 2006].

where η is a tuned parameter and its value assignment is discussed in Section 5. Intuitively, when Lobs T (or Lrec T ) is larger

Algorithm 2: The OCDS algorithm

• 2 Receive instance xt, and Ut = Ut-1 ∪Rdt ;
• 3 Retrieve Gr using Algorithm 1;
• 4 Predict the label as sign(ˆ yt) using (11);
• 5 Lobs T += ℓ(yt, 〈 ¯wt, xt〉), Lrec T += ℓ(yt, 〈 ˜wt, ˜xt〉);
• 6 Reweight the parameter p using (12) where η = 8√1/ lnT;
• 7 Update wt+1 andG using (9) and (10), respectively;
• 8 Truncate wt+1 based on γ;

than Lrec T (or Lobs T ), the impact of xt (or ˜xt) is negatively rewarded by our learning system.

The details of OCDS are presented in Algorithm 2. The running time complexity of OCDS is O(d2t × |Ut|). To fully capture the feature relatednesses without being affected by the data scale, we in the implementation update Gr since G can be easily restored based on it.

5 Theoretical Analysis

In this section, we borrow the the regret from online learning to measure the performance of OCDS. We derive a cumulative loss bound and show that the recovered feature space effectively enhances the performance. For the sake of soundness, the proofs of this section are provided in Section 3 of supplementary material.

Theorem 1. Denoted by LT = ∑Tt=1 ℓ(yt, ˆ yt) the overall cumulative loss of OCDS over T iterations. LT with parameter η = 8√1/ ln T satisfies:

Let ∆ = T/√lnT + (ln2/8)√lnT, which is linearly bounded by the number of iterations. Theorem 1 indicates that LT is comparable to the minimum of Lobs T and Lrec T . Furthermore, we have the following theorem.

Theorem 2. If ¯wt is better than ˜wt over T iterations, then LT is bounded as:

where C is a constant, and C ≪ ∆.

Theorem 1 and 2 offer our learning algorithm a nice property as follows.

Corollary 1. The learning performance is improved by making use of the recovered universal feature space.

Proof. On the one hand, when ¯wt is better than ˜wt over T iterations, Theorem 2 tells that the cumulative loss LT of OCDS is comparable to Lobs T and is bounded to a constant. On the other hand, when ˜wt is better than ¯wt over T iterations, it is obvious that the recovered unobservable feature space is helpful. Furthermore, if ˜wt is better than ¯wt to certain degree, satisfying Lobs T - Lrec T > ∆, it is easy to verify that LT < Lobs T . To conclude, the learner with the assistance from the universal feature space achieves better performance than that without the assistance.

6 Experiments

We use 15 UCI datasets [Dua and Karra Taniskidou, 2017] and 1 real-world IMDB dataset [Maas et al., 2011] to evaluate the performance of OCDS. The task in IMDB dataset is to classify the movie reviews into positive and negative sentiments. Each individual word in the reviews is considered as a feature. Since the words used in each and every user review could be different, we formulate the task as learning from an arbitrarily varying feature space. In UCI datasets, we simulate capricious data streams by randomly removing features from each arriving instance xt. The ratio of the maximal removed features is denoted as VI . For example, VI = 0.5 means that at most 50% of features in xt are randomly removed. The default value of VI is 0.5 in our experiments. The details of the used datasets are provided in Table 1.

To find the best settings of the parameters α, β1 and β2, we use grid searches ranging from 10-5 to 1. For memory and running time efficiency, we let |Ut| ≤ 150 by setting γ in different datasets.

6.1 Comparisons with State-of-the-arts

Table 2 presents the results of performance comparison in terms of classification accuracy. Three baseline algorithms, OLSF [Zhang et al., 2016a], FESL [Hou et al., 2017], and OCO [Zinkevich, 2003], as well as the proposed OCDS algorithm are evaluated in this section. In particular, OLSF can only handle trapezoidal data streams where the feature space monotonically augments as data flow in, while FESL can only handle feature evolvable streams where feature space batchly evolves by following an explicit pattern - both new and old features exist in an overlapping time period. The trapezoidal and feature evolvable data streams are the special cases of capricious data streams, and we simulate these two kinds of data streams by following the methods provided in the respective work. We compare OCDS with OLSF and FESL on trapezoidal data streams and feature evolvable streams, respectively. On capricious data streams, OCDS is compared with OCO, which, as mentioned in Section 1, is a na¨ıve online learning algorithm that makes prediction based on the observable feature space only.

On trapezoidal data streams, the average accuracy of OCDS and OLSF are 86.69% and 75.40%, respectively, and OCDS statistically achieves better results on 13 out of 16 datasets. Moreover, on 12 out of 16 datasets, the classification variances of OCDS are smaller than those of OLSF. The main reason is that OCDS considers the feature relatednesses in model penalty while OLSF does not, and therefore the classification accuracy of OCDS is more robust.

On feature evolvable streams, OCDS and FESL achieve 87.98% and 77.12% accuracy on average, respectively, and OCDS outperforms FESL on 11 datasets. This is because FESL trains a learner mainly with the help of the time period in which old and new features exist simultaneously, while OCDS can keep updating the learned reconstructive mapping over all iterations. The way that OCDS learns the mapping suggests that the classification accuracy could be improved when a large number of instances flow in, and the results support it. For example, we observe that the average accuracy of OCDS is 19.78% higher than that of FESL on large scale datasets such as splice and HAPT.

On capricious data streams, the average accuracy of OCDS is 91.02%, while that of OCO is only 65.44%. In addition, OCDS wins over OCO on 15 datasets. We also find out that the classification result of OCDS is stable across different datasets. The results indicate that OCDS could effectively handle arbitrarily varying feature spaces.

6.2 Impact of Universal Feature Space

In this section, we compare OCDS with three approaches. One is OCO, which could work on capricious data streams, as a baseline algorithm. The other two are the variants of OCDS, named OCDS-o(bservable) and OCDS-r(econstructed), respectively. The difference between them is that, when making prediction, OCDS-o uses the observable features while OCDS-r uses the reconstructed features. To investigate the impact of universal feature space, we aim to answer the following two questions:

Q1. How effectively can the universal feature space capture feature relatednesses?

The smaller reconstruction error the universal feature space has, the better the feature relatednesses are captured. In addition, due to the bi-convexity of our objective optimization function (8), the reconstruction error is positively correlated to the prediction loss. Therefore, the prediction loss could be used in turn to measure the accuracy of the captured feature relatednesses.

Here we present the trend of average cumulative loss (acl) in Figure 2. At the iteration T , acl = LT /T . Based on the results, we find that although the curve of OCDS-r may increase during the beginning iterations, it decreases as more data flow in and eventually converges. This intuitively makes sense because the more arriving instances the learner receives, the better the feature relatednesses are learned, reducing the value of acl. Moreover, the average cumulative losses of OCDS and OCDS-r both drop to small values after convergence. Thus, the reconstruction error in general is small, which suggests that the feature relatednesses are captured accurately.

Q2. Can the universal feature space help improve learning performance?

From Figure 2, we make the following observations. (i) After convergence, the average cumulative loss of OCDS is significantly smaller than that of OCO, especially on large datasets. OCDS enjoys better performance because the universal feature space can provide more information. (ii) OCO may surpass OCDS-o when the number of instances is small, but the average cumulative loss of OCDS-o becomes smaller than that of OCO after convergence. This means that a better learner is obtained based on the universal feature space. (iii) The average cumulative loss of OCDS is comparable to the best of OCDS-o and OCDS-r, and is smaller than them when the number of instances is large. The result validates Corollary 1 in Section 5.

7 Conclusions

In this paper, we focus on a general and challenging setting - learning from an arbitrarily varying feature space. By utilizing the relatednesses among features, we learn a mapping from the observable feature space to a universal feature space in which both old and new features can be used for prediction. A learner is trained on the universal feature space, and theoretical results show that it can achieve better performance with strong guarantees. We carry out extensive experiments and the results demonstrate that our approach is effective.

Acknowledgments

We thank IJCAI 2019 reviewers for their constructive feedback. This work is supported by the US National Science Foundation (NSF) under grants IIS-1652107, IIS-1763620, and CCF-1750886.