# Profit-Efficient Elastic Allocation of Cloud Resources Using Two-Stage Adaptive Workload Prediction
## 4 Prediction Method  
### Introduction of Workload Prediction  
Workload prediction can be modeled as a regression and fitting problem for a time-series signal. The historical signal is used to calculate the signal value at the next time slot. Let \(X=[x(t),x(t-1),\ldots,x(t-(n-1))]\) be the historical workload values from the \((t-n-1)\)th time slot to the \(t\)th time slot. The prediction value at the \((t+1)\)th time slot can be presented as follows:  
\[x^{\prime}(t+1)=fun([x(t),x(t-1),\ldots,x(t-(n-1))]), \tag{1}\]  
where \(fun(\cdot)\) is a regression and fitting function that represents the relationship between historical and predicted values.  
As mentioned in Section 2, the LSTM was shown to outperform other methods in short-term single-task time-series forecasting in previous research. In an LSTM, the output value of each gate is determined by the weighted sum of the current input and past state values. The weighted information can be updated in a self-loop, according to the structure of LSTM. Thus, LSTM becomes more effective in accessing past information. In the self-loop structure, each unit can receive previous information to perform a specific operation and output the results to the next unit. An LSTM unit is shown in Figure 3.  
In an LSTM, each gate can be presented as an activation function, \(\sigma(\cdot)\), such as the sigmoid, ReLU, or tanh function. Let \(x_{t}\) and \(h_{t-1}\) be the current input and past state output, respectively. The LSTM can be expanded following the time-series as a sequential connection from a past state to the current state. The key component of an LSTM is a cell, which is used to store the past state and determine the amount of past state information. According to Figure 2, the value of input gate \(i_{t}\) and block input \(k_{t}\) in an LSTM can be calculated as follows:  
\[i_{t}=\sigma_{g}(b_{i}+U_{i}\!\cdot\!x_{t}+W_{i}\!\cdot\!h_{t-1}), \tag{2}\]  
\[k_{t}=\sigma_{h}(b_{k}+U_{k}\!\cdot\!x_{t}+W_{k}\!\cdot\!h_{t-1}), \tag{3}\]  
where \(b_{i}\), \(U_{i}\), and \(W_{i}\) are the bias, weight of the input, and recurrent state weight in the input gate, respectively; similarly, \(b_{k}\), \(U_{k}\), and \(W_{k}\) are the bias, weight of the input, and recurrent state weight in the block input, respectively. In an LSTM, the output of the forget gate controls the recurrent memory state of the cell, which is influenced by \(\sigma_{g}(\cdot)\) and \(\sigma_{h}(\cdot)\). The output of the forget gate can be calculated as follows:  
\[f_{t}=\sigma_{g}\Big{(}b_{f}+U_{f}\!\cdot\!x_{t}+W_{f}\!\cdot\!h_{t-1}\Big{)}. \tag{4}\]  
Figure 3: Architecture of a long short-term memory unit.  
According to the calculations above, the state of the cell is updated as follows:  
\[c_{t}=f_{t}\cdot c_{t-1}+k_{t}\cdot i_{t} \tag{5}\]  
The value of the output gate can be calculated as follows:  
\[o_{t}=\sigma_{g}(b_{o}+U_{o}\cdot x_{t}+W_{o}\cdot h_{t-1}). \tag{6}\]  
Finally, the output of the LSTM can be calculated as follows:  
\[h_{t}=o_{t}\cdot\sigma_{h}(c_{t}). \tag{7}\]  
A prediction model based on an LSTM is shown in Figure 4. In this model, the LSTM layer is used to extract time-series features, which capture both past and present temporal information. The output layer of the LSTM is a fully connected structure, and its output can be calculated as follows:  
\[x^{\prime}(t+1)=\sum_{i=1}^{n}h_{t}^{i}\cdot W_{h}+b_{h}, \tag{8}\]  
where \(W_{h}\) and \(b_{h}\) denote the weight and bias of the output layer, respectively.  
To prevent the gradient from becoming large and to accelerate the training process, the input of the network needs to be normalized. Max-min normalization is as follows:  
\[x^{*}(t)=\frac{x(t)-min}{max-min} \tag{9}\]  
where \(x(t)\) and \(x^{*}(t)\) are the original workload data and normalized value at the \(t\)th time slot, respectively, and \(min\) and \(max\) denote the minimum and maximum values in the input data set, respectively.