four methods above can handle all the challenges co-currently raised in our work. First, all of these assume the testing instances to have fully observed feature pro les. They don't consider coping with incomplete testing instances by design. Second, all of them are designed speci cally for multi-label learning and adapting them to multi-class classi cation is not straightforward.
More recently, methods based on Deep Latent Variable Models (DLVM) have been proposed to deal with missing data. In [MF19], the Variational Autoencoder [KW14] has been adapted to be trained with missing data and a sampling algorithm for data imputation is proposed. Other approaches based on Generative Adversarial Networks (GAN) by [GPAM+14] are proposed in [YJvdS18] and [LJM19]. Impressive results on image datasets are displayed for these models, at the price of a rather high model complexity and the need for a large training set. In addition these works are focused on features reconstruction, and additional speci cations and ne-tuning are required to be able to take partially observed labels into account. The models speci cations are quite involved and any new speci city of the dataset may increase both the cost and the di culty in training (especially for the approaches based on GANs).
In this paper we choose to address this problem in a more economical and robust manner. We consider the old and simple architecture of the Restricted Boltzmann Machine and adapt it to the multi-output learning context (RBM-MO) with missing data. The RBM-MO method serves as a generative model which collaboratively learns the marginal distribution of features and label assignments of input data instances, despite the incomplete observations. Building on the ideas expressed in [NK94, GJ94] we adapt the approach to the more e ective contrastive divergence training procedure [Hin02] and provide results on various real-world datasets. The advantage of the RBM-MO model is that of providing a robust and exible method to deal with missing data, with little additional complexity with respect to the classic RBM. Indeed, the trained model can be naturally applied to both transductive and inductive scenarios, achieving superior multi-output classi cation performance then state-of-the-art baselines. Moreover, it works seamlessly with multi-class and multi-label tasks, providing a uni ed framework for multi-output learning. 2
An RBM is a Markov random eld with pairwise interactions de ned on a bipartite graph formed by two layers of non-interacting variables: the visible nodes represent instances of the input data while the hidden nodes provide a latent representation of the data instances. V and H will denote respectively the sets of visible and hidden variables. In our setting, the visible variables will further split into two subsets Vf and V` corresponding respectively to features and labels, such that V = Vf + V`. The visible variables form an explicit representation of the data and are noted v = fvi; i 2 Vg. The hidden nodes h = fhj ; j 2 Hg serve to approximate the underlying dependencies among the visible units.
In this paper, we will work with binary hidden nodes hj 2 f0; 1g. The variables corresponding to the visible features will be either real with a Gaussian prior or binary, depending on the data to model, and labels variables will always be binary (vi 2 f0; 1g). The joint probability distribution over the nodes is de ned through an energy function e E(v;h)
Z P (v; h) = pprior(v);
E(v; h) =
X i2V;j2H viwij hj
i2V
X bj hj j2H where ai and bj are biases acting respectively on the visible and hidden units and wij is the weight matrix that couples visible and hidden nodes. pprior is in product form and encodes the nature of each visible variable, either with a Gaussian prior pprior = N (0; v2) or a binary prior pprior(v) = (s2 s). Z = Pv;h pprior(v)e E(v;h) is the partition function. The classical training method consists in maximizing the marginal likelihood over the visible nodes P (v) = Ph P (v; h) by tuning the RBM parameters = fwij ; ai; bj g via gradient ascent of the log likelihood L(v; ).
The tractability of the method relies heavily on the fact that the conditional probabilities P (vjh) and P (hjv) are given in closed forms. In our case these read:
P (vjh) = Y i2Vf ePj2H viwijhj+aivi pprior(vi)
Y Pvi ePj2H viwijhj+aivi pprior(vi) i2V`
j2H P (hjv) = Y
j2H i2V (1) (2) (3)
Taking the log-likelihood and then computing the gradient with respect to the weight matrix element wij (also similarly for the elds ai and bj ), we obtain two di erent expressions for i 2 O and i 2 M. = vi X hj p(hj jvo) i 2 O; hj
X Z = hj dvivihj p(vi; hj jvo) i 2 M (4) (5) (6) 3
The RBM is a generative model able to learn the joint distribution of some empirical data given as input. As such, it is intrinsically able to encode the relevant statistical properties found in the training data instances that relate features and labels, and this makes the RBM particularly suitable to be used in the multi-output setting in the presence of incomplete observations. In this sense, the most natural way to deal with incomplete observations is to marginalize over the missing variables; in this section we show how the contrastive divergence algorithm can be adapted to compute such marginals.
Given a partially-observed instance v, we have a new partition of the visible space V = O + M, where O is a subset of observed values of v that can correspond both to features and labels. vo = fvi; i 2 Og and vm = fvi; i 2 Mg denote respectively the observed and missing values of v. The probability over the observed variables vo is given by ( representing the parameters of the model)
P (vo) = = hvihj p(hj jv)idata hvihj iRBM where the brackets hidata and hiRBM respectively indicate the average over the data and over the distribution (1). The positive term is directly linked to the data and can be estimated exactly with (3), while the negative term is intractable. Many strategies are used to compute this last term: the contrastive divergence (CD) approach [Hin02] consists in estimating the term over a nite number of Gibbs sampling steps, starting from a data point and making alternate use of (2) and (3); in its persistent version (PCD) the chain is maintained over subsequent mini-batches; using mean- eld approximation [MTK15] the term is computed by means of a low-couplings expansion.
= D
Io(i)vi X hj p(hj jvo) hj
E data + D 1
X Z hj Io(i) dvivihj p(hj jvo)
hvihj iRBM E data where Io is the indicator function of the samples dependent set O. The observed variables vi; i 2 O are pinned to the values given by the training samples. In terms of our model, the pinned variables play the role of an additional bias over the hidden variables of a RBM where the ensemble of visible variables is reduced to the missing ones.
With respect to the non-lossy case where p(hj jv) is given in closed form, here we need to sum over the missing variables in order to estimate p(hj jvo). This means that also the positive term of the gradient (6) is now intractable and we need to approximate it. For CD training, we can simply perform Gibbs sampling over the missing variables (keeping xed the observed variables). Details are reported in Alg. 1.
We note that the extra computational burden of Lossy-CD with respect to standard CD is due only to the extra Gibbs sampling steps in the positive term. Given that the observed variables strongly bias the sampling procedure speeding up convergence, only few sampling steps are needed to compute this term. Indeed, in our experiments we observed that a single sampling step (Lossy-CD1) is enough, making the additional complexity minimal. Finally, we note that the same method can be applied to PCD and mean- eld training procedures. In the rst case, it is su cient to keep track of an additional persistent chain, which requires little extra memory and no extra computational complexity. In the second case, we only need to substitute Gibbs sampling with iterative mean- eld equations.
As a generative model, the trained RBM can be used to sample new data. For imputation of missing features and labels we just need to use the observed portions of our data to bias the sampling procedure in the same way as for the computation of the positive term in Alg. 1. Namely, we estimate p(vmjvo) by pinning the observed variables and iterating CD/PCD or mean- eld to approximate the equilibrium values of the missing variables. In case of a high percentage of missing observations, however, we might expect the observed variables to be correlated to many di erent equilibrium con gurations, such that the sampling could be biased towards the wrong sample. To overcome this problem, we simply average over multiple mean- eld imputations for each incomplete data instance.
More in details, let fpi; i 2 V`g and fqj ; j 2 Hg be the marginal probabilities respectively of visible labels and hidden variables to be activated and fmi; i 2 Vf g the marginal expectation of the visible features variables. Mean- eld equations at lowest order (O(1=N ), N being the size of the system) express self-consistent relations among these quantities mi = qj =
X wij qj + ai j2H 2 v 8i 2 Vf nO pi =
X wij qj + ai j2H 8i 2 V`nO X wij mi + X wij pi + bj i2Vf i2V` (7) (8) Higher order terms corresponding to TAP equations are discarded [M17]. These equations can be e ciently solved by iteration starting from random con gurations until a xed point is reached. Observed variables are simply introduced by pinning their corresponding probabilities (0 or 1 for label variables) or their marginal expectation (for feature variables) to the observed values. In practice we run these xed-point equations Nf 10 times and the imputations are obtained by simple average m^ i = 1 XNf m(n)
i Nf n=1 pi = 1 XNf pi(n): Nf n=1 In the multi-label setting, the predictor is the indicator function p^i = (pi > t) (t is learned, it is chosen to maximize the accuracy for known labels), while for class labels we have p^i = 1 if i = argmaxk(pk)
Experimental con guration To evaluate the e ciency of RBM-MO we compare its performance against CLE, NoisyIMC and MC-1, which provide state-of-the-art baselines.
For the transductive experiments we randomly hide features and labels of the whole dataset to generate incomplete data for training, and we compute appropriate scores for the reconstruction of missing features and labels. In the inductive test, instead, we split the whole dataset into non-overlapping training and testing sets. Concerning the training set the same protocol is used as in the transductive test. For the test set the di erence is that now all labels are hidden. Once the classi er is trained, it is applied on the test set to predict the labels. We still randomly hide the entries of test features vectors, so as to form an incomplete testing set. Finally, in the splitting we use 70% of the data instances for training and the remaining 30% for testing.
We denote by qfea, qml and qmc the percentage of masked features, labels and classes labels respectively. Note that a masked class label means that all binary variables attached to the classes of a given label are masked together. These rates of masking are kept identical in the learning and test sets.
In the transductive test, we compute the Root Mean Squared Error (RMSE) to measure the reconstruction accuracy with respect to the missing feature values. Furthermore, for the reconstructed labels we calculate Micro-AUC scores and Hamming-accuracy [GKG12] in the multi-label scenario, and Averaged AUC plus Accuracy [LY15] in the multi-class case. In the tables, we de ne Hamming-accuracy as 1-Hamming loss to keep a consistent variation tendency with the AUC scores. In the inductive test we only compute the scores on the reconstructed labels, since reconstructing missing features is not the goal of inductive classi cation.
We run the test as described 10 times with di erent realizations of the missing features and labels. Average and Model qmc% RBM-MO(qfea% =50%)
CLE(qfea% =50%) NoisyIMC(qfea% =50%) RBM-MO(qfea% =80%)
CLE(qfea% =80%) NoisyIMC(qfea% =80%) standard deviation of the computed scores are recorded to compare the overall performances. In the tables, we use red fonts to denote the best reconstruction and classi cation performances among all the algorithms involved in the empirical study. The bold black font is used to highlight the performance of the proposed RBM-MO method.
For the baselines, we used grid search to choose the optimal parameter combination following the suggested ranges of parameters as in [HSSZ18].
The RBM-MO is trained following the guidelines in [Hin10]. We always use binary variables for the hidden layer, while in the visible layer we use binary variables for MNIST and Gaussian variables for the other datasets. In all the simulations, we x the number of hidden nodes to 100. The learning rate is xed to 0.001 and the size of the mini-batches to 10. During training the number of Gibbs steps is set to k = 1 while for imputation we iterate the mean- eld equations 10 times. As a stopping condition, we considered the degradation of the transductive AUC scores with a look-ahead of 500 epochs 5.2
Summary of datasets We consider 3 publicly available datasets related to image processing. These datasets cover both multi-label and multi-class learning tasks, and they are popularly used as benchmark datasets in multi-output learning research.
In addition, we consider the challenging scenario of abnormality detection on IoT devices. The relevant dataset, that we call EventCat, consists in security telemetry data collected from various network appliances (e.g. smart watches, smartphones, driving assistance systems...), each reporting a features vector whose entries indicate the occurring frequency of a speci c type of alert (e.g. downloading suspicious les, login failures, un xed vulnerabilities...). Multiple labels are assigned to each device in the collected dataset, corresponding to a variety of categories of security threats.
Some details about the datasets are reported in Table.5. 5.3
Qualitative results on MNIST A qualitative evaluation of the performance of the RBM-MO model is given by looking at features reconstruction for the MNIST dataset, as reported in Fig. 1. The model at hand has been trained over a dataset in which 50% of the features were missing. To assess the robustness of the method, we computed the reconstructions in the highly challenging case in which 80% of the features were missing. Apart from some smoothing due to the employment of mean- eld imputations, the reconstructed samples look reasonably realistic. In general, from the qualitative point of you the results are comparable to those obtained with more complex and expensive DLVMs like MIWAE and MisGAN [MF19, LJM19]. 5.4
Empirical results The transductive results for MNIST (multi-class) and Scene (multi-label) datasets are reported in tables 1 and 2. Going into the details, we rst observe that RBM-MO is by a large margin more e cient than all of the baselines for the inference of class labels (table 1), probably because it is able to encode more complex statistical properties.
On the multi-label problems, the situation is still in favour of RBM-MO but with less margin (table 2), in particular at a larger percentage of missing features.
Now if we look at the reconstruction error on these datasets we observe that RBM-MO generally achieves a higher reconstruction accuracy than the other opponents, especially on the MNIST dataset. The results verify empirically the basic motivation of using a generative model such as the RBM: incomplete features and labels can provide complementary information to each other, so as to better recover the missing elements. The variance of the results is omitted in the tables by lack of space. For RBM-MO the standard deviation of the derived RMSE, AUC and accuracy scores is not larger than 0:01 over the di erent datasets. Although the RMSE scores reported by the baseline methods look comparable to the RBM-MO ones, and in certain cases they are better, they also come with a slightly higher variance, such that the RBM-MO seems to be more e cient and robust for features reconstruction.
Except MC-1, all the baseline methods are used for inductive learning. As in the transductive test, we show only the mean of the derived metrics in the tables. Nevertheless, we have similar variance ranges for the computed scores as reported in the transductive test. Clearly RBM-MO is much better adapted to this setting than the baseline methods both for multi-class (table 3) and multi-label learning. The baseline inductive methods CLE and NoisyIMC are speci cally designed for multi-label learning and their performance deteriorates signi catively in the multi-class scenario. By comparison, RBM-MO can be adapted seamlessly to multi-class and multi-label learning, producing consistently good performances.
For the EventCat dataset, inductive results are reported in table 4. Even with highly incomplete training data, RBM-MO produces the best predictions over partially observed testing data instances. 6
Machine learning is witnessing a race to high complexity models eager for large data and computational power. In the context of multi-output classi cation in a challenging scenario - (i) learning with highly incomplete features and partially observed labels; ii) applying the learnt classi er with incomplete testing instances) we advocate instead for simple probabilistic and interpretable models. After re ning the learning of the RBM model, we give empirical evidences that it can be e ciently adapted to this context on a great variety of datasets. Experiments are conducted on both public databases and a real-world IoT security dataset, showing various sizes of training sets as well as features and labels vectors. Our approach consistently outperforms the state-of-the-art robust multi-class and multi-label learning approaches with imperfect training data, indicating good usability for practical applications. [CHS15]
Kai-Yang Chiang, Cho-Jui Hsieh, and Inderjit S.Dhillon. Matrix completion with noisy side information. In Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS'15, pages 3447{3455, Cambridge, MA, USA, 2015. MIT Press.
R. Cabral, F. D. l. Torre, J. P. Costeira, and A. Bernardino. Matrix completion for weaklysupervised multi-label image classi cation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(1):121{135, Jan 2015.
Zoubin Ghahramani and Michael I. Jordan. Supervised learning from incomplete data via an em approach. In Advances in Neural Information Processing Systems 6, pages 120{127. Morgan Kaufmann, 1994.
G.Madjarov, D. Kocev, and D. Gjorgjevikj. An extensive experimental comparison of methods for multi-label learning. Pattern Recognition, pages 3083{3104, 2012. [Hin02]
Geo rey Hinton. A practical guide to training restricted Boltzmann machines. Momentum, 2010. Yufei Han, Guolei Sun, Yun Shen, and Xiangliang Zhang. Multi-label learning with highly incomplete data via collaborative embedding. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '18, pages 1494{1503, 2018.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations (ICLR), pages 4413{4423, 2014.
Steven Cheng-Xian Li, Bo Jiang, and Benjamin Marlin. Learning from incomplete data with generative adversarial networks. In International Conference on Learning Representations, 2019. Yue Wu Li, Lin and Mao Ye. Experimental comparisons of multi-class classi ers. Informatica, 2015. Xin Li, Feipeng Zhao, and Yuhong Guo. Conditional Restricted Boltzmann Machines for Multi-label Learning with Incomplete Labels. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Arti cial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 635{643, San Diego, California, USA, 09{12 May 2015. PMLR.
M. Mezard. Mean- eld message-passing equations in the Hop eld model and its generalizations. Phys. Rev. E, 95:022117, 2017.
Pierre-Alexandre Mattei and Jes Frellsen. MIWAE: Deep generative modelling and imputation of incomplete data sets. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4413{4423, Long Beach, California, USA, 09{15 Jun 2019. PMLR.
G. Marylou, E.W. Tramel, and F. Krzakala. Training restricted Boltzmann machines via the Thouless-Anderson-Palmer free energy. In Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS'15, pages 640{648, 2015.
M. J. Nijman and Kappen. Using boltzmann machines to ll in missing values, 1994.