BAMBOO: A Multi-instance Multi-label Approach Towards VDI User Logon Behavior Modeling

1 Introduction

Virtual Desktop Infrastructure (VDI) is a technology and software system that can run user desktops on top of a virtual machine hosted on a physical server in the remote datacenter. Recently, the technology of hosting VDI on public cloud is gaining more adoption which is also called DaaS (Desktop as a Service). Compared with on-premise customers, cloud customers care more about the running cost. The public cloud vendors bill for resources usage per minute or even per second. The powered off virtual machines are only charged for storage where the much higher computation cost is saved. As a result, a well-performed power management system can bring significant customer value and competitiveness for a DaaS offering.

∗Corresponding author

VDI systems usually manage virtual desktops in two ways. Non-persistent pool shares desktops among users for cost saving where power management only needs to handle the overall number of desktops. On the contrary, persistent pool allocates dedicated desktop for each user to guarantee the prime user experience which is more difficult for power management because each of the individual desktops needs to be powered on or off specifically for the dedicated user. Consequently, nowadays desktops in the persistent pool are barely powered off which makes the cost much higher especially for cloud customers. The existing VDI power management systems work by configuring power on/off schedules manually. However, manual scheduling is usually time-consuming and error-prone and tends to cause poor user experience and unnecessary cost. To build a proactive VDI power management system which can power-off spare desktops without impacting user experience, accurate user logon prediction based on intelligent VDI user behavior modeling is required.

Previous works on VDI user logon modeling include CAFE [Zhang et al., 2019] and SOUP [Fan et al., 2019]. CAFE does not focus on specific user but aims at aggregating user logon modeling at the pool level. SOUP is an ensemble learning model to predict the specific user logon behavior based on tailored multi-grained features extracted from logon state sequence. Generally, earlier attempts towards user logon behavior modeling employ traditional supervised learning techniques under the single-instance single-label (SISL) setting, where the input and output to the predictive model correspond to single instance of user features and single label of user behavior respectively. Nonetheless, this SISL practice may lead to suboptimal performance as the strong relationships among pool-sharing VDI users are not properly exploited in the modeling framework.

In light of the above observations, we propose to utilizing the Multi-Instance Multi-Label (MIML) learning framework [Zhou and Zhang, 2006; Zhou et al., 2012] for VDI user logon behavior modeling, which naturally fits the need of relationship exploitation among pool-sharing VDI users. Specifically, a novel approach for VDI user logon prediction named BAMBOO (BAlanced MimlBOOst) is proposed in this paper. To induce the predictive model for each user, its supporting users identified in the same pool will be jointly modeled in the input space as a bag of multi-instance feature vectors and in the output space with multi-label prediction. The MIML formulation is optimized by adapting the popular MIML boosting procedure via balanced error-rate minimization. To enable effective multi-instance bag generation of users, BAMBOO identifies the group of supporting users based on logon frequency statistics and validation performance evaluation. Comparative studies on real VDI customer data sets evidently show that BAMBOO achieves highly competitive performance against other state-of-the-art methods.

The rest of this paper is organized as follows. Section 2 gives technical details of the proposed BAMBOO model. Section 3 discusses related researches. Section 4 introduces the collected real-world data sets for VDI user logon prediction and the experimental results of comparative studies, followed by conclusion in Section 5.

2 The Proposed Approach

In this section, we firstly give the MIML formulation for VDI user logon behavior modeling. After that, technical details of the proposed BAMBOO model are introduced.

2.1 The MIML Formulation

In many real-world tasks, a complicated object can be represented naturally by multiple instances and associated by multiple class labels. Multi-instance Multi-label [Zhou and Zhang, 2006; Zhou et al., 2012] provides a framework to address such tasks. The MIML task can be formulated as following. Let X denote the instance space and Y the set of labels. The task is to learn a function f : 2X ↦→ 2Y from training data set D = (X1, Y1), (X2, Y2), ...(Xm, Ym), where Xi ⊆ X is a set of instances {xi1, xi2, ..., xi,ni }, xij ∈ X (j = 1, 2, ..., ni), and Yi ⊆ Y is a set of labels {yi1, yi2, ..., yi,li }, yik ∈ Y (k = 1, 2, ..., li). Here ni denotes the number of instances in Xi and li denotes the number of labels in Yi.

In user logon behavior prediction, the complicated inherent patterns among pool sharing users could be modeled by the MIML learning framework. For a specific VDI user to model, given the supporting user group, the logon behavior prediction can be formulated as a MIML task. Formally speaking, for any user, let st,p = (st; st-1...; st-p+1) be the logon state sequence where p is the sequence length and st is the logon state in time range 1 [t - 1, t) defined as follows:

Then we can use xt = µ(st,p) to represent the user logon behavior in the feature space where µ is the multi-grained feature description function described in SOUP [Fan et al., 2019]. Based on the user group with size n2 , the corresponding instance set of user logon behavior features can be constructed as Xt = {xt,1, xt,2, ..., xt,n}.

1 In this paper, we use half an hour (30 minutes) as the unit of t.

2 In this paper, n is set to 2 because higher n has much higher training cost but can not bring significant performance improvement.

Correspondingly, we define Yt = {y|syt+1 = 1, 1 ≤ y ≤ n} as the label of instance set Xt. Here syt+1 denotes the logon state of user y in time range [t, t +1), thus Yt is the set of users that logon in the period. After that, the training data set D can be defined as:

Here, l is the minimum feasible starting time of st,p and T is the ending time of the logon state sequence. For each user in the pool, our target is to learn a MIMLmodel fMIML : 2X ↦→ 2Y from D where X is the instance space and Y is the label space.

2.2 The BAMBOOModel

Bag Generation

In a VDI pool, not all users are suitable as supporting users especially those having very few or even no logon. To learn fMIML for a specific user, the first step is to select supporting users to form the user group and then the MIML bags can be generated. Initially, given the complete user set Y of the VDI pool, we define the total logon count for each y ∈ Y as:

Here, syt is the logon state of user u in time range [t - 1, t). Then we sort Y in a descending order of the value of every user's lcnt and select the first ζ ∗ |Y| users to construct the candidate supporting user set U where 0 ≤ ζ ≤ 1 is the candidate selection rate. 3 Finally, given the user to model y∗ ∈ Y, we can generate the correspondent supporting user group Y ′ by grouping y∗ and the randomly selected n - 1 users from U \ {y∗ }.

The BAMBOO Algorithm

Notice that in the above section, the supporting user group Y ′ and the MIML bags (Xt, Yt) are specifically generated for the prime user y∗ . Therefore, the resulting MIML model should be optimized more towards reducing the prediction error-rate on the label for y∗ . Accordingly, we propose a novel MIML learning method via balanced error-rate minimization. As indicated in [Zhou et al., 2012], the idea of solving MIML problem is to identify its equivalence in the traditional supervised learning framework, using multi-instance learning or multilabel learning as the bridge. In BAMBOO, multi-instance learning is chosen as it focuses more on modeling relationship of users historical logon behavior. The pseudo-code of BAMBOO is summarized in Algorithm 1.

At the beginning, BAMBOO transforms each MIML sample (Xt, Yt) into n multi-instance bags {[(Xt, y1), ψ(Xt, y1)], ..., [(Xt, yn), ψ(Xt, yn)]} where ψ is a function ψ : 2X × Y ′ ↦→ {+1, -1} defined as:

3 In this paper, ζ is set to 0.5.

Algorithm 1: The pseudo-code of BAMBOO

Input: Y, y∗ , l, T, n, {st,j}(l ≤ t ≤ T - 1, j = 1, 2, ..., n), µ, ζ, ν, V, eval(., .), R Output: f ∗MIML 1 Let xt,j = µ(st,j)(l ≤ t ≤ T - 1, j = 1, 2, ..., n). 2 Initialize the candidate resulting MIML model set F = {} 3 For each y ∈ Y, compute lcnt(y) = ∑T-1 t=l I(syt+1 > syt ) and select top ζ × |Y| users to form the candidate set U. 4 for r = 0, ...,R do 5 Randomly pick n-1 users fromU \ {y∗ } and group themwith y∗ to generate Y ′ where |Y ′ | = n. Then compose MIML samples {(Xt, Yt)} = {({xt,1, xt,2, ..., xt,n}, {y1, y2, ...yn})|l ≤ t ≤ T - 1}. 6 Transform each MIML sample (Xt, Yt) into n multi-instance samples, thus the original data set is transformed into (T - l) × n multi-instance bags, where each bag Bt,k = [(Xt, yk), ψ(Xt, yk)](l ≤ t ≤ T - 1, k = 1, 2, ...n) 7 Initialize the each bag's weight as: Wt,k = 1 (T-l)×n (l ≤ t ≤ T - 1, k = 1, 2, ..., n). 8 for i = 1, 2, ...I iterations do 9 For Bt,k, assign the label ψ(Xt, yk) to its each instances (xt,j , yk)(j = 1, 2, ...n) with weight Wt,k/n. 10 Build an instance-level predictor ht[(xt,j , yk)] ∈ {-1, +1}. 11 Compute the error rate et,k ∈ [0, 1] of Bt,k by et,k = 1n ∑nj=1 [[hi[(xt,j , yk)] ̸= ψ(Xt, yk)]] 12 if et,k < 0.5 for all l ≤ t ≤ T -1, k = 1, 2, ...n then break; 13 Compute ci = argminci {ν × ∑T-1 t=l ∑nk=2 Wt,kexp[(2et,k -1)c] + ∑T-1 t=l Wt,1exp[(2et,1 -1)c]} 14 if ci ≤ 0 then break; 15 Update Wt,k = Wt,kexp[(2et,k - 1)ci] and re-normalize such that ∑T-1 t=l ∑nk=1 Wt,kexp[(2et,k - 1)ci] = 1. 16 end 17 Obtain fMIML where fMIML(X∗ ) = {y|sign(∑j ∑i cihi[(x∗j , y)]) = +1}(x∗j is the j-th instance of X∗ ) 18 F = F ∪ fMIML 19 end 20 Return the model f ∗MIML = argmaxfMIML {eval(fMIML, V )|fMIML ∈ F}

For simplicity, y1 is used to represent the prime user.

Thus, the original training data set is transformed into (T - l) × n multi-instance bags: [(Xt, yk), ψ(Xt, yk)](l ≤ t ≤ T -1, k = 1, 2, ...n). Then a multi-instance learning function fMIL can be derived with which the resulting MIML function can be accomplished by:

Then we obtain fMIL with the following boosting procedure. Let (B, g) denote the bag [(X, y), ψ(X, y)],B ∈ B, g ∈ G and E denote the expectation. The ultimate goal is to learn a function F(B) with which the bag-level exponential loss EBEG|B[exp(-gF(B))] is minimized. The target of each boosting iteration is adding a new weak classifier to expand F(B) to F(B) + cf(B) where f(B) can be learned by:

Here, h(·) is the instance-level classifier and h(bj) ∈ {-1, +1} denotes its prediction for the bag B's j-th instance. Given the bag-level weight W = exp(-gF(B)), the best f (B) to be added can be fulfilled by learning h(·) which minimizes the weighted instance-level classification error where the instance-level weight is set toW/n. After f(B) is found, the bag's error rate can be computed as: e = 1n ∑j [[(h(bj ̸= g)]]. Then the best multiplier c with the balanced error rate can be computed by optimizing the exponential loss as:

Here, Wt,k and et,k are the weight and error rate of bag [(Xt, yk), ψ(Xt, yk)]. Specifically, Wt,1 and et,1 are the weight and error rate of the bag with the label of the prime user y∗ . The balance parameter ν (0 < ν < 1) is applied on the bags with non prime user labels to make the optimization focus more on the label of the prime user. Lastly, the baglevel weights are updated as Wt,k = Wt,kexp[(2et,k - 1)c] and renomalized.

Furthermore, to minimize the effect of randomness, we generate multiple supporting user groups and train the same number of MIML learners. Given the validation set V and the performance evaluation function eval(fMIML, V )4 , the resulting MIML model f ∗MIML is obtained by:

In the testing phase, f ∗MIML is applied on the new bag X∗ of y∗ to predict the future user logon behavior.

3 RelatedWork

In many real-world problems, the objects have complicated inherent patterns. They can be represented as multi-instance bags and associated with multiple labels. For example, an image can be represented by multiple sub-images and associated with several high level concepts. A formalized multiinstance multi-label learning (MIML) framework [Zhou and Zhang, 2006; Zhou et al., 2012] was introduced to solve such tasks and many successful researches and applications ([Yang et al., 2017; Ma et al., 2019]) have been proposed in recent years. [Briggs et al., 2012] introduced Rank-Loss Support Instance Machines for MIML instance annotation. [Wu et al., 2014] proposed EnMIMLNN, a novel ensemble MIML learning framework for genome-wide protein function prediction. [Huang et al., 2014] proposed a fast MIML approach by optimizing the approximated ranking loss and utilizing label relations in a shared space and perceiving sub-concepts for complicated labels. [Pham et al., 2015] presented probabilistic MIML model in the presence of novel class instances and introduced an efficient computational method for inference. [Xie et al., 2016] explored the application of using MIML for the classification of frog species. [Feng and Zhou, 2017] proposed DeepMIML, a general deep MIML model that can automatically learn the instance description as well as disclosing the relation between input patterns and output labels. [Gao et al., 2018] presented a deep MIML network which successfully separates object-level sounds by automatically linking audio bases to object categories and using the disentangled bases to supervise non-negative matrix factorization.

4 In this paper, CSAG is used as performance evaluation function.

To the best of our knowledge, BAMBOO is the first study that applies the MIML algorithm to the VDI domain. Considering the fact that VDI user logon behavior modeling is a complicated time-series prediction task ([Solow, 1994]) where many researches have been done in this area. [Chatfield, 1978] introduced Holt-Winters which is widely used for time-series data prediction. [Taylor and Letham, 2017] proposed Prophet for large-scale time-series data prediction which is based on additive model and fits non-linear trends with seasonalities. It was shown that RNN ([Elman, 1990]) outperforms conventional learning algorithms on many time series tasks in [Connor et al., 1994; Ho et al., 2002]. [Yin et al., 2017] applies RNN on intrusion detection and proves its capacity to distinguish binary data. But its validity on VDI user logon prediction has not been demonstrated. Recently, a few successful researches were applied in VDI domain. [Zhang et al., 2019] proposed a multi-grained features based ensemble learning model to solve the VDI non-persistent pool user logon prediction problem. [Fan et al., 2019] introduced an encoded multi-granularity feature based model to predict

(c) Atlantic user logon activities. Whilst existing approaches on VDI user logon behavior modeling are all single-instance singlelabel learning models, BAMBOO solves this problem with a MIML approach by incorporating the advantage of discovering pattern-label relation among different users.

4 Experiments

4.1 Comparing Algorithms

To evaluate the performance of BAMBOO, four state-of-theart methods are selected for comparison.

• SOUP ([Fan et al., 2019]) is an ensemble learning model based on encoded multi-granularity description to predict single user logon activities. In our configuration, the feature extraction sequence length is set to 3600 (120 days).
• MIMLBoost ([Zhou and Zhang, 2006]) is a multiinstance multi-label algorithm using multi-instance learning as the bridge to degenerate MIML problem to MISL problem. In our configuration, the boosting rounds is set as 30 and GBDT ([Friedman, 2001;

2002]) is used as instance-level learner.

• RNN-IDS ([Yin et al., 2017]) is a deep learning approach for intrusion detection and it shows RNN's capability to make prediction on binary time-series which is similar to user logon scenario. In our configuration, the input shape of 3D tensor (batch size, timesteps, input dim) is set as (256, 72, 1).
• DeepMIML ([Feng and Zhou, 2017]) exploits deep neural network formation to generate instance representation for MIML. In our configuration, it shares the same training set as MIMLBOOST and the sub-concept number is set as 2.

For BAMBOO, the algorithm parameters are set as following. The feature extraction sequence length is the same as SOUP. The supporting user group size n is set to 2. The boosting rounds R is set to 30. GBDT is used as instancelevel learner. The candidate selection rate ζ is set to 0.5. The error-rate balance parameter ν is set to 0.8.

4.2 Data Sets

The experiments are conducted on five real VDI customers data sets where the logon behavior granularity interval is set to 30 minutes. Each of the data set is from one of the customer's persistent desktop pools. We divide the training data into two division: D1 training data period is from Sept. 17th 2018 to Mar. 4th 2019, D2 training data period is from Nov. 5th 2018 to Apr. 22th 2019, both of which are 24 weeks data. BAMBOO is tested on two separated test data sets: D1 test set is selected from March 26th to April 21st 2019 and D2 test set is selected from Jun. 3rd 2019 to Jul. 1st 2019. We name the five customers data sets as: Pacific, Antarctic, Arctic, Indian , Atlantic. Then the six test sets in D1 is named as Pacific-T1, Pacific-T2, Antarctic-T1, Antarctic-T2, Arctic-T1, Arctic-T2 and six test sets in D2 is named as as Pacific-T3, Pacific-T4, Indian-T3, Indian-T4, Atlantic-T3, Atlantic-T4, ˙Table 1 contains the statistics of the data sets.

The typical real-world data sets are illustrated in Figure 1. The darker the hexagon is, the more logon happened at that time. We can see that all the data sets show a common daily pattern that most of the user logon activities happen on working day and also have specific patterns. Data set Pacific has the biggest number of user count and the longest session duration. Most of its logon happen between 6am to 8am and the peak is around 7am for all the working days. The logon distribution of Pacific looks similar to a Gaussian distribution. Furthermore, it has notable logon activities on weekend. Whereas, data set Antarctic has two remarkable logon peaks at 7am and 11am respectively, and it has the smallest logon time entropy being most centralized. To be noted that the users in Antarctic have seldom logon after working day noon and on weekend. Different to Pacific and Antarctic, Atlantic has a rather long session duration average (154 hours), the session keeps alive for nearly one week. The pattern is seen in some call-center customers where three shifts provide 24-hour service.

Evaluation Metrics

By modeling the user logon behavior to a zero-one serial, the prediction is actually a binary classification task. We use one common classification performance metric (AUC) and one VDI domain specific metric (CSAG, defined in [Fan et al., 2019]) for comparison. AUC is one of the most important evaluation metrics for validating a classification model's performance. It describes how much the model can distinguish between classes. CSAG is a VDI domain specific metric to measure the algorithm's effectiveness on cost-efficiency. CSAG is computed by Equation 9 where a denotes the cost saving factor of powering off unnecessary desktops and b the penalty cost factor of the incorrect prediction. The configuration details are listed in Table 3.

4.3 Experimental Results

Table 2 reports the detailed performance metric of each comparing algorithm where the bold number means the 1st rank, ∗ means the 2nd rank and · means BAMBOO outperforms MIMLBOOST. Furthermore, a post-hoc Bonferroni- Dunn test [Dunn, 1961] is performed to compare the relative performance among the comparing approaches. The CD diagrams are presented in Figure 2, where the average rank of each approach is marked along the axis (the smaller the better).

It is impressive to observe that 1) On the most important VDI specific metric: CSAG, BAMBOO achieves 1st rank on

58% data sets and 2nd rank on 42% data sets. On the AUC metric, BAMBOO ranks 1st on 42% data sets and 2nd on 42% data sets. 2) It is remarkable that BAMBOO achieves the lowest average rank in terms of both CSAG and AUC metric. 3) 67% 1st ranks are from MIML methods. This is the clear evidence that leveraging MIML framework obtains notable performance improvement and we believe the driving force here is the hidden relation between users in the pool. In the cases where SOUP outperforms BAMBOO, we observe an apparently common logon behavior pattern. It makes sense as SOUP model is trained with samples from all the users in the pool, the common pattern is strengthened. 4) Among all the data sets, BAMBOO outperforms MIMLBOOST in 75% cases which clearly demonstrates the effectiveness of the balance parameter introduced in BAMBOO.

5 Conclusion &FutureWork

In this paper, we propose BAMBOO, a novel MIML approach towards VDI user logon behavior modeling which serves as the key enabling-technique to build intelligent VDI power management systems. Specifically, each user to model is grouped with supporting users selected in the same pool to construct the MIML bags so that the strong relationship among pool-sharing users is incorporated. After that, an innovative MIML learner with class error rate balance parameter is derived for future user logon prediction. The effectiveness of BAMBOO is validated through comprehensive experiments on real DaaS customer data sets. With a rough computation, about $660 can be saved per week for a persistent pool with 100 VDI desktops which equals to reducing the infrastructure cost over 50%. 5

In the future, we will explore the possibility of optimizing the efficiency of BAMBOO with the technique in [Huang et al., 2014] and also try to group users from different pools to see if more user relationship can be discovered.

Acknowledgements

The authors wish to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Key R&D Program of China (2018YFB1004300), and the China University S&T Innovation Plan Guided by the Ministry of Education.

5 We use the AWS EC2 instance t3.medium ($0.06/hour) as the virtual machine of VDI desktops to calculate the infrastructure cost.