Learning with Previously Unseen Features

1 Introduction

We consider a setting where a machine learning system can access features that are previously unseen in the labeled training set. This often happens when machine learning systems are deployed in an open environment.

For example, consider a weather station equipped with a set of sensors measuring temperature, wind speed, pressure, etc. Suppose the station has a machine learning model that predicts humidity from the sensor readings. The prediction model is built on a training set containing historical sensor readings and the corresponding humidity. Now, the station plugs in a new sensor that measures dew point. Since dew point is strongly correlated with humidity, leveraging this new sensor could potentially improve the model.

As a second example, consider a model that predicts a job applicant's quality. It is built on a training set where each sample contains features from the resume of a previous applicant and the quality level labeled by HR. Now, for future applicants, the model is allowed to access applicants' social media such as Facebook and Twitter. Exploring new features

Craig A. Knoblock

Information Sciences Institute University of Southern California knoblock@isi.edu

extracted from social media may improve the prediction quality since social media data often reflect an applicant's personality and perspectives, which may not be revealed in resumes.

In the above examples, the new features are likely to provide complementary information over the original features in the labeled training set. Identifying and leveraging such features can potentially improve the underlying machine learning models. This is an important step towards developing intelligent systems that can interact and learn from an open environment. The challenge is that there is no labeled samples associated with those additional features. Collecting new labels can be costly and often requires human input. It is desirable to develop an approach that can automatically exploit previously unseen features.

This problem can be viewed in the framework of domain adaptation or transfer learning [Pan and Yang, 2010; Daume III and Marcu, 2006; Quionero-Candela et al., 2009], which aims to adapt machine learning models trained on a source domain to a related but different target domain. Our problem can be viewed as a special case of heterogeneous domain adaptation, where the feature space of the source domain is different from that of the target domain. Although being a special case, our problem setting actually poses unique challenge for existing domain adaptation approaches.

Previous work on heterogeneous domain adaptation mainly consists of two types of approaches. One type learns a transformation to map the features from one domain to the other [Dai et al., 2008; Socher et al., 2013; Zhou et al., 2014] by leveraging sample-level correspondences across domains (e.g., an image and its tag). This type of approach can be applied to our setting naturally since each target-domain sample provides a correspondence between the original and new features. However, learning a good transformation may not be possible when the dependency between the original and new features is weak. 1 In our context, the new features are expected to contain complementary information not available in the original features, making such transformation difficult to obtain. A second type of approach maps the source and target domains into a domain-invariant feature space in which they distribute similarly (in terms of the features in that space), and then learns a model in that space using labeled data [Kulis et al., 2011; Wang and Mahadevan, 2011; Argyriou et al., 2008; Duan et al., 2012; Shi et al., 2010; Harel and Mannor, 2010; Wei and Pal, 2011; Yeh et al., 2014]. These approaches are not applicable to our setting because the original features already provide a domain-invariant feature space, which would completely ignore new features in the target domain.

1 Weak dependency implies that there is no strong correspondence between original and new features. In other words, knowing original features is not very helpful when predicting new features.

Our problem can also be viewed as a special case of semisupervised learning [Zhu, 2005], with additional features associated with unlabeled data. To the best of our knowledge, such problem setting has not been explored before because existing semi-supervised learning algorithms focus on using unlabeled data from the same feature space of labeled data.

To address the challenge, we propose an approach named LUF (Learning with previously Unseen Features) that builds a machine learning model over both the original and new features. Intuitively, the desirable model should predict targetdomain labels consistent with the labels in the source domain. We express the consistency in the notion of the joint distributions over the original features and labels, and we enforce the two domains to have similar joint distributions. LUF minimizes k-nearest neighbor distances across domains in the joint space and can be solved by an efficient optimization algorithm. LUF can be simply extended to the case where there exist labeled samples with new features. We evaluate LUF extensively on benchmark regression and classification datasets and a sensor adaptation application in the weather domain. In most of the evaluation cases, LUF outperforms other baseline methods, with an average improvement of 11.2%.

Contributions. To summarize, we study a new machine learning setting involving features that are not available in the labeled training set. We then propose a novel approach as well as an efficient optimization algorithm. Our approach is applicable to both regression and classification tasks and can naturally leverage labels associated with these new features. Our empirical study highlights the efficacy of the proposed approach.

2 Approach

We are given N labeled samples {(xs, ys)}Ns=1 , where xs ∈ RD is the input features, and ys is the corresponding label. Additionally we are given M unlabeled samples {(xt, zt)}Mt=1 , where xt ∈ RD follows the same distribution of xs. zt ∈ RW are the additional features associated with xt. In the following, we refer to the set of labeled samples as the source domain, and the set of unlabeled samples as the target domain.

We are interested in learning a model for the target domain that maps (x, z) to y. In the following, we denote the model as fθ(x, z) where θ represents the model parameters, and the predicted label as ˆ y = fθ(x, z).

For each source-domain sample (xs, ys), if we could estimate its ˆzs reliably, we can simply train fθ(x, z) on the source domain. However, estimating z from x can be challenging when their dependency is weak, as observed in our empirical study. On the other hand, training on the target domain is very challenging as there are no labels available.

We tackle the challenge based on the following intuition: if our model predicts target-domain labels {ˆ yt} well, then {ˆ yt} should be consistent with the training labels. Such consistency can be expressed through some joint patterns between x and y, for instance, the joint distribution of (x, y). Ideally, our model fθ would make the joint distribution similar across domains, which motivates us to seek fθ such that {(xs, ys)} and {(xt, ˆ yt)} are mixed as much as possible. When this happens, each source-domain sample (xs, ys) becomes close to its k-nearest neighbors in the target domain, and vise versa. Therefore, we propose the following objective function to minimize the cross-domain k-nearest neighbor distances in the joint space of (x, y)

where dist is the distance function defined on (x, y). N k T (s) denotes the set of indices corresponding to (xs, ys)'s knearest neighbors in the target domain, and N k S (t) denotes the set of indices corresponding to (xt, yt)'s k-nearest neighbors in the source domain, where nearest neighbors are determined based on dist. ‖θ‖22 is the regularization term on θ with λ ≥ 0 as the regularization parameter.

For simplicity, we set dist to be the following weighted distance 2

where ∆(ys, ˆ yt) measures the distance between ys and ˆ yt , and γ > 0 is a weight balancing the scale of x and y. Let v2 st = ‖xs - xt‖22 , we can write (1) into

For regression tasks, we simply set ∆(ys, ˆ yt) = ‖ys-ˆ yt‖2 . For classification tasks with C classes, we use probabilistic classificationmodels (e.g. logistic regression [Bishop, 2006]) that can predict class probability for a given sample. In this case, ˆ yt is a C-dimensional vector representing the probability in each class, and ys is a C-dimensional binary vector. We can set ∆(ys, ˆ yt) = 1 - ∑Cc=1 ys(c)ˆ yt(c), so that a small ∆ corresponds to similar class assignment.

Note that N k T (s) and N k S (t) are dependent on θ, hence (3) is non-smooth and non-convex in θ. In the following, we present an efficient optimization algorithm for finding a local minimum of Eq. (3).

2 In our implementation, features are first normalized into similar scales.

2.1 Alternating Optimization

For the ease of optimization, we introduce a set of auxiliary variables to "decouple" the dependency of N k T (s) and N k S (t) on θ. Let V k T (s) index (xs, ys)'s any (not necessarily the nearest) k neighbors in the target domain, and V k S (t) index (xt, yt)'s any k neighbors in the source domain. It is easy to see

and the same relationship holds for V k S (t) and N k S (t). Thus (3) is equivalent to

(5) can be efficiently optimized via an alternating procedure. When θ is fixed, we update {V k T (s)} and {V k S (t)} based on nearest neighbor search. When {V k T (s)} and {V k S (t)} are fixed, we optimize θ by solving

which can be easier to optimize than (3) when fθ is smooth in θ. For regression tasks, if linear regression is used, θ can be solved analytically. For classification tasks, if logistic regression is used, a global optimum of θ can be solved using gradient descent techniques.

The above alternating procedure decreases (5) at each alternating step, and converges to a local minimum of (3). Empirically, the procedure converges quickly (usually within 50 iterations). The outline of the algorithm is described in Algorithm 1.

Algorithm 1 Optimization algorithm for LUF

Input: source-domain samples {(xs, ys)}Ns=1 and targetdomain samples {(xt, zt)}Mt=1 , neighbor size k, weight parameter γ, and regularization parameter λ.

Initialize θ by solving Eq. (8)

Fix {V k T (s)}, {V k S (t)}, optimize θ by solving Eq. (6)

Output: a local optimal solution θ∗ .

Initialization: The quality of the solution depends on how we initialize θ. Intuitively, if we could get a good estimate of ˆzs based on each source-domain sample xs, we can initialize θ by solving

However, estimating ˆzs can be very challenging when the dependency between x and z is weak. Nevertheless, we can estimate a candidate set of ˆzs based on target-domain data as follows: for each xs, we find a set of its nearest neighbors in {xt}, and use the corresponding zt to form a candidate set Zs. We then minimize the model error by optimizing both θ and {ˆzs}:

where ˆzs is allowed to be any element of Zs. (8) essentially relaxes the dependency between x and z, and uses the optimal θ for the relaxed setting as an initialization. By setting {Zs} to different sizes, we can get different initial solutions for θ.

Complexity analysis: In Algorithm 1, each iteration iter involves N updates on V k T (s) and M updates on V k S (t). Each update on V k T (s) takes O(MD2 ) and each update on V k S (t) takes O(ND2 ), where D is the dimensionality of original features. Therefore the complexity of updating {V k T (s)} and {V k S (t)} at each iteration is O(NMD2 ). Additionally, each iteration iter involves leaning a linear regression or logistic regression function, whose complexity is O((D +W)2 (N + M)) where W is the dimensionality of new features and we assume N > D +W. Further assuming W = O(D) and M = O(N), we have the overall complexity as O(D2N 2 ).

Hyper-parameter tuning and overfitting prevention:

When there are no labels in the target domain, tuning hyperparameters is often very difficult. We tune the neighborhood size k by reducing the error of a k-NN classifier or regressor on the source domain. To tune the weight γ and regularization parameter λ, we apply a leave-one-out cross validation strategy on the source domain to simulate our problem setting. Specifically, we consider each feature in the source domain as z, and the rest of the features as x. We then split sourcedomain samples into two disjoint sets: one set has only x, and the other set has both x and z. We treat the first set as a synthesized source domain and the second set as a synthesized target domain, and apply the proposed approach to pick the optimal γ and λ. To prevent overfitting, we adopt an early stopping strategy: train a model on {(xt, ˆ yt)} and apply it to source-domain data. If the prediction error on the source domain is larger than a certain threshold, we stop the learning process. We also terminate the optimization when the objective function decreases very slowly, which not only saves computational time but also reduces overfitting.

Leveraging labels in the target domain: LUF can naturally leverage labels in the target domain when they are available. Suppose a subset of target-domain samples are labeled, and let L denote their sample indicies. We can directly enhance LUF by adding a supervised term into the objective function

where µ ≥ 0 is a new weight parameter that can be tuned by cross validation on the target domain.

3 Experiments

We evaluate LUF on several regression and classification datasets and an application on sensor adaptation for weather stations. 3

We develop the following methods for comparison:

• R: kernel regression [Bishop, 2006] trained on the source domain. Polynomial kernel 4 k(xi, xj) = (xi Txj + c)d is used where c and d are kernel parameters.
• R-Z KR , R-Z NN . These are domain adaptation methods that explore the correspondences between x and z in the target domain. They first estimate ˆz for each sourcedomain sample, and then train a kernel regression model over {(xs, ˆzs)} on the source domain. Two strategies are explored for estimating ˆz:
• Z KR : train a kernel regression on the target domain to map xt to zt, and use that model to predict ˆzs for source-domain sample xs.
• Z NN : similar to Z KR except using a k-NN regression model .
• R-Z*: kernel regression directly trained on the target domain, using the target-domain labels ("cheating"). This method, though unrealistic in practice, provides an upper bound on the best possible performance. We apply ten-fold cross validation on the target domain and report the average error.
• C: logistic regression [Bishop, 2006] trained on the source domain. Since the dimensionality of the classification datasets is relatively high, we directly use input features and do not apply polynomial kernel.
• C-Z KR , C-Z NN , C-Z*. These methods are the same as R-Z KR , R-Z NN , R-Z* respectively, except that kernel regression is switched to logistic regression.

3 Our algorithms and datasets can be accessed from https://github.com/yuanshi/UnseenFeatures

4 We use polynomial kernel over other nonlinear kernels because it has explicit form for the nonlinear features. For most datasets, we find polynomial kernel performs comparably to Gaussian RBF kernel. Our focus is more on leveraging new features than choosing the best kernels.

• LUF: the proposed approach for learning with previously unseen features. For regression tasks, it trains a linear model based on the explicit feature mappings derived from polynomial kernel. For classification tasks, it trains a logistic regression based on input features.

The hyper-parameters of the above methods, including c and d in polynomial kernel, k in k-NN regression, the regularization parameter λ, are tuned on the source domain. For R-Z* and C-Z*, their regularization parameters are tuned on the target domain.

3.1 Results on Regression Datasets

We experiment with four regression datasets

• Abalone, 5 for predicting the age of abalone, contains 4,177 samples with 8 features.
• Bank, 6 which predicts the fraction of bank customers that are turned away due to queuing, contains 8,192 samples with 8 features.
• CPU, 7 for CPU running time prediction, contains 8,192 samples with 12 features.
• House, 8 for housing price prediction, contains 20,640 samples with 9 features.

In order to select a subset of features to be "unseen", we look at features with high predictive power, which enables a machine learning model to improve prediction performance by leveraging these features. 9 Specifically, we do the following check for each feature: if removing it increases the prediction error by more than 10 percent, then it is selected as an unseen feature. We then sort these unseen features based on their impact on the prediction errors in descending order. Table 1 shows the results when the top set of unseen features are explored.

For each dataset, we conduct experiments in 10 random trials. In each trial, we randomly split the dataset into the source/target domain, each with half the number of samples. We report the average root mean square error (RMSE) and standard error on the target domain. 10 As a preprocessing step, we normalize each feature to [0,1].

Table 1 summarizes the prediction error of different methods, where the improvement(%) is computed based on the best performing baseline. In most cases, LUF outperforms the other baselines, with an average improvement of 12.1%.

5 https://archive.ics.uci.edumldatasetsAbalone

6 http://www.cs.toronto.edu/∼delve/data/bank/desc.html

7 http://www.cs.toronto.edu/∼delve/data/comp-activ/desc.html

8 http://lib.stat.cmu.edu/datasets/

9 Our experimental policy selects unseen features useful for prediction, which is designed to evaluate LUF 's efficacy. We also conduct experiments on unseen features that are uninformative or noisy. We observe that LUF is quite robust to such features (performance drops less than 2%). LUF often stops using these features because either there is a minor decrease in the objective function or early stopping is triggered.

10 All target-domain data are used in the learning process. We also tested our methods on hold-out evaluation data from the target domain and observed consistent performance.

Note: the results of House are in the scale of 105 .

This demonstrates that LUF is able to exploit useful information in the additional features. In a few cases, LUF performs slightly worse than the best baseline, but the gap is much smaller than that in successful cases. This reveals that although LUF may overfit due to its unsupervised nature, it is quite robust.

It is interesting to study the improvement of LUF over baselines when the number of unseen features increases. With more unseen features, baselines tend to become worse but LUF has more useful features to leverage, which may lead to greater improvement, e.g. on Bank [1,2]. On the other hand, more unseen features makes the remaining ones less useful. LUF can suffer from this since the sample distances become less meaningful, e.g. on Bank [1,2,3] and CPU [1,2,3]. In practice, this may not be a severe problem because the features in the source domain are often reasonably good to begin with.

3.2 Results on Classification Datasets

We experiment with three classification datasets

• USPS, which recognizes handwriting digits from images, contains 9,298 samples from 10 classes [Hull, 1994].
• Books, which performs sentiment analysis on book reviews from Amazon, contains 4,000 samples from 2 classes [Blitzer et al., 2006].
• Webcam, which recognizes objects in low-resolution images taken by web cameras, contains 795 samples from 10 classes [Kulis et al., 2011].

For Books and Webcam, we split the data into the source/target domain, each with half the number of samples. For USPS, the source/target domain uses 1,500 samples each. For all datasets, we scale each feature to [0,1], and then use principal component analysis (PCA) to reduce the dimensionality to 100, which reduces computational cost and feature noise.

Similar to regression tasks, we check each feature as follows: if removing it increases the classification error by more than 10 percent, then it is selected as an unseen feature. Table 2 shows the results when the top 1 to 3 unseen features are explored. For each dataset, 10 random splits are used and averaged classification errors are reported. C-Z KR and C-Z NN perform better than C in all cases. This suggests that

ˆz can be estimated fairly well for these datasets. LUF outperforms C-Z KR and C-Z NN in most cases, with average improvement 3.6%. When the number of unseen features increases, LUF shows greater improvement over baselines as estimating z becomes harder.

3.3 Sensor Adaptation forWeather Stations

We apply our proposed approach to an application for sensor adaptation. In particular, we investigate how sensors at weather stations can be adapted when sensor failure happens. In a real-world environment, sensor failure often occurs at weather stations [Dereszynski and Dietterich, 2011] and can cause problems for system modules relying on the failed sensor. We aim to develop a robust system that automatically reconstructs the missing signal from the working ones.

Missing signal reconstruction can be cast as a regression task, and a regression model can be built based on historical sensor readings. The reconstruction quality depends a lot on the correlations between the missing signal and the remaining ones. For example, reconstructing temperature from dew point and humidity can be fairly accurate but reconstructing wind speed from dew point and humidity is very hard. Our system handles this challenge by allowing a weather station to access the sensors at a nearby station when a sensor failure is detected.

We conduct experiments with data from Weather Underground, 11 which contains sensor data from a large number of personal weather stations worldwide. Each station consists of 5-10 sensors and produces a sample (combined readings form all sensors) at a fixed time interval (e.g. every 10 minutes). We examine three stations in San Francisco, San Jose, and New York, respectively, as well as their nearby stations. For a given station, we use 3,000 samples randomly drawn from Jan. 2015 to Aug. 2015 as the source domain, and 3,000 random samples from Jan. 2016 to Aug. 2016 as the target domain.

Table 3 summarizes the results. The reported cases correspond to signals that are difficult to reconstruct using a weather station's own sensors. 12 LUF achieves positive im- Note: the results are reported in the following units: mph (wind speed), mph (wind gust), in (pressure), in (precipitation). The listed weather stations correspond to the following station IDs in Weather Underground: SF-A (KCASANFR142), SF-B (KCASANFR114), SJ-A (KCASANJO121), SJ-B (KCASANJO139), NY-A (KNYNEWYO139), NY-B (KNYNEWYO132).

11 http://www.wunderground.com

12 Note that precipitation data are not available for SF-A and SFB, and wind speed and wind gust data are not available for NY-A and NY-B.

provement in 8 out of 9 cases, with most significant improvement (66.7%) on reconstructing pressure for SF-A. Note that the amount of improvement is consistent with the gap between R-Z* and other baselines. When the gap is large, LUF leverages better features and outperforms other baselines with a large margin. When the gap is small (wind speed at SF-A), LUF performs worse than R due to overfitting, but with a fairly small performance drop.

Figure 1 visualizes the joint distributions over original features and predicted labels, where we choose wind speed as a representative feature and pressure as the label, on station SFA. As can be observed, R generates a significantly different joint distribution compared to the actual one, while LUF produces a much closer distribution. R-Z* performs even better but relies on the labels from the target domain.

4 RelatedWork

Our learning setting can be viewed as a special case of heterogeneous domain adaptation [Pan and Yang, 2010], which adapts a learning model across different feature spaces. The work of [Zhao and Hoi, 2010] and [Hou and Zhou, 2016] also consider new features in the target domain. However, their approaches require labels from the target domain, which does not work for our setting. A similar nearest-neighbor-based objective function is used in [Kulis et al., 2011]. However, their neighbors are fixed but ours are dynamically updated. More importantly, our approach computes distances over both features and labels.

Another way to address our setting is to treat it as a missing data problem: the additional features available in the target domain are completely missing in the source domain. The baselines in our empirical study are also approaches for missing value imputation [Grzymala-Busse and Hu, 2000; Lakshminarayan et al., 1996; Batista et al., 2002]. However, recovering these features in the source domain is very chalx-axis represents wind speed (feature), and y-axis represents pressure (label) given by different approaches. Ground truth corresponds to the actual pressure. Values are in normalized scales.

Figure 1: Visualization of wind speed and predicted pressure on weather station SF-A

lenging in nature.

Our setting is related to zero-shot learning [Larochelle et al., 2008; Farhadi et al., 2009] which explores unseen classes at test time, as well as to privileged information-based learning [Vapnik and Vashist, 2009] which leverages additional information only available in training. Although related, our setting is very different from theirs.

5 Conclusion

We presented a novel machine learning approach that leverages previously unseen features in the training set. The approach is applicable to both classification and regression tasks. Supported by our empirical results, the approach can be used to improve a learning model when new features are accessible. Our future work includes theoretical analysis and more real-world applications. We also plan to develop algorithms that can automatically determine when to explore new features and which features to select from a large pool of features in an open environment.

Acknowledgements

This material is based upon work supported by the United States Air Force and the Defense Advanced Research Projects Agency (DARPA) under Contract No. FA8750-16-C-0045. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Air Force and DARPA.