TWI755941B - Hierarchical time-series prediction method - Google Patents

Abstract

A hierarchical time-series prediction method is adapted to a plurality of reconciled prediction values of a plurality of nodes of a hierarchical structure, wherein the plurality of nodes respectively has a plurality of time-series, the plurality of reconciled prediction values corresponds to the plurality of time-series, and the plurality of nodes comprises a plurality of bottom-level nodes. The method comprises generating a plurality of individual prediction values corresponding to the plurality of time-series by a plurality of prediction models, generating a plurality of bottom-level prediction values corresponding to the plurality of bottom-level nodes according to the plurality of individual prediction values and an encoder network, and generating the plurality of reconciled prediction values according to the plurality of bottom-level prediction values and a decoder associated with the hierarchical structure, wherein the number of the plurality of individual prediction values is greater than that of the plurality of bottom-level prediction values and is identical to that of the plurality of reconciled prediction values, and the individual prediction value and the reconciled prediction values which correspond to the same time-series are continuous in time.

Description

Hierarchical Time Series Forecasting Methods

The present invention relates to the prediction of time series, especially a hierarchical time series prediction method.

A hierarchical time-series is a collection of observations that change over time in a hierarchical structure. Hierarchical time series often appear in business and economics, where quantities that change over time need to be predicted at different levels of granularity. In a supply chain, for example, it may be necessary to forecast demand at the country, city or store level to organize logistics. In many applications, forecasts need to be generated for multiple time series at different hierarchical levels. Due to the constraints of the hierarchical structure, independent predictions often do not add up correctly, thus requiring a reconciliation step.

The forecasting of hierarchical time series is usually divided into two stages. The first stage is to forecast all or part of the time series. The second stage is that these predictions are reconcile to enforce compliance with class constraints. Existing ways to reconcile time series such as bottom-up, top-down, optimal-combination and trace-minimization, etc. Insufficient flexibility, in other words, these approaches cannot be optimized for the specific metric used to evaluate the predictive model.

With the rise of deep learning in the past few years, there are also attempts to impose soft constraints on the loss function and use a hierarchical structure to regulate the training process, hoping to improve the prediction performance and reduce the reconciliation gap. (gap). However, this approach does not guarantee correct reconciliation, i.e. does not satisfy the class constraints.

In view of this, the present invention proposes a reconciliation strategy based on an encoder-decoder model, which is versatile, flexible, and easy to implement. By testing on real-world datasets, the proposed hierarchical time-series forecasting method can meet or exceed the performance of existing methods in a reconciliation setting.

A hierarchical time series prediction method according to an embodiment of the present invention is suitable for generating a plurality of harmonic prediction values of a plurality of nodes in a hierarchical structure, wherein the nodes respectively have a plurality of time series, the harmonic prediction values correspond to the time series, and The node includes a plurality of underlying nodes, and the method includes: generating a plurality of independent forecasting values corresponding to the time series with a plurality of forecasting models; generating a plurality of underlying forecasting values according to the independent forecasting values and the coding network; Predictors and decoders associated with the hierarchy produce harmonic predictors; where the number of independent predictors is greater than the number of underlying predictors and equal to the number of harmonic predictors; independent predictors and harmonic predictors corresponding to the same in the time series Values are continuous in time.

The above description of the present disclosure and the following description of the embodiments are used to demonstrate and explain the spirit and principle of the present invention, and provide further explanation of the scope of the patent application of the present invention.

10: Conditioner

P: Code Network

S: decoder

S1, S2, S3: Steps

FIG. 1 shows an example of a hierarchical structure; FIG. 2 is a flowchart of a hierarchical time series prediction method proposed by an embodiment of the present invention; FIG. 3 is a schematic structural diagram corresponding to the hierarchical time series prediction method proposed by an embodiment of the present invention 4A is a schematic diagram of a standard fully connected network; and FIG. 4B is a schematic diagram of a simplified version of a fully connected network.

The detailed features and characteristics of the present invention are described in detail in the following embodiments, and the content is sufficient to enable any person skilled in the relevant art to understand the technical content of the present invention and implement accordingly, and according to the content disclosed in this specification, the scope of the patent application and the drawings , any person skilled in the related art can easily understand the related concepts and features of the present invention. The following examples further illustrate the viewpoints of the present invention in detail, but do not limit the scope of the present invention in any viewpoint.

Please refer to FIG. 1, which shows an example of a hierarchical structure. This hierarchical structure has multiple nodes A~G, including multiple bottom nodes D, E, F and G. Each node A~G has a time series At _{~ Gt} . A time-series, for example, presents the monthly output of a producer in a serial manner. The hierarchical structure shown in Figure 1 describes the dependencies between these time series. A practical example is as follows: a factory a includes a production line b and a production line c, wherein the production line b has a machine d and a machine e, and Production line c has machine f and machine g. The time series D _t , E _t , F _t and G _t represent the monthly output of machines d, e, f and g respectively, the time series B _t and C _t represent the monthly output of production lines b and c respectively, and the time series A _t represent The monthly output of factory a. The production amounts A _t to G _t of these producers a to g satisfy the relationships of “A _t =B _t +C _t ”, “B _t =D _t +E _t ”, and “C _t =F _t +G _t ”.

In addition to the above examples, multiple time series can be used to describe, for example, the monthly budget of various departments in government agencies, the daily temperature and humidity in weather forecasts, and the monthly turnover of various products in convenience stores. The present invention does not particularly limit the field of time series application.

The hierarchical structure described is used to describe the dependencies between multiple time series. Taking the previous example, the monthly output of production line b is affected by the monthly output of machine d and machine e this month. In some cases, the monthly production of line b this month may be affected by the monthly production of machine d and machine e over the past few months. The hierarchical time series forecasting method proposed by the present invention can select some or all of the data from the data of a large number of dimensions, such as the past actual output and predicted output of the time series At ~ G _{t ,} to generate the respective data of At ~ G _{t .} In the future forecast value (such as the estimated monthly output), at the same time satisfy the mutual dependence of A _t ~ G _t . For example: the sum of the estimated production of B _t and C _t will not exceed the estimated monthly production of A _t .

FIG. 2 is a flowchart of a hierarchical time series prediction method proposed by an embodiment of the present invention. FIG. 3 is a schematic structural diagram corresponding to a hierarchical time series prediction method proposed by an embodiment of the present invention. In FIG. 3, an independent prediction vector composed of a plurality of independent prediction values is input to a reconciler 10 (reconciler). The blender 10 includes a trainable encoding network P and a fixed decoder S. The output of the blender 10 is a plurality of harmonic forecast values, which respectively correspond to time series. The implementation details of the architecture of FIG. 3 will be described in detail below according to the flow of FIG. 2 .

所示。其中A _t ,B _t ,...,G _t 的每一者代表一個時間序 列。在本發明一實施例中，獨立預測向量中的每個獨立預測值代表時間序列的下一個預測值。即

,

,...,

例如是下個月的產量。但本發明不限於上述範例，在另一實施例中，

,

,...,

中的每一者亦可代表連續多個預測週期(例如下兩個月)的多個預測值。 Step S1 is "obtaining an independent prediction vector with the prediction model". Specifically, a plurality of independent forecast values corresponding to a plurality of time series are respectively generated by a plurality of forecast models. The independent prediction vector contains the prediction values of multiple time series, as shown in Figure 3

shown. where each of A _t , B _t ,...,G _t represents a time series. In an embodiment of the present invention, each independent prediction value in the independent prediction vector represents the next prediction value of the time series. which is

,

,...,

For example, next month's output. However, the present invention is not limited to the above examples. In another embodiment,

,

,...,

Each of the may also represent multiple forecast values for multiple consecutive forecast periods (eg, the next two months).

In step S1, the forecast model is used to generate the next forecast value of the time series. This prediction model has been trained before step S1. For example, for the time series A _t , the historical forecast production A _HP of factory a in the past several months and the actual production A _HR of factory a in the past several months are collected as the input for the training of the prediction model.

Regarding the multiple prediction models described in step S1, the present invention adopts one of the following two strategies. The first strategy is to use an independent forecasting model for each time series, and the second strategy is to use a common (global) forecasting model for all time series.

In the first strategy, the present invention employs a linear autoregressive model with lagged time series values as input. In this strategy, the hyperparameters in the forecasting model corresponding to each time series are adjusted independently. For example, hyperparameter tuning of time series A _t does not affect hyperparameter tuning of time series B _t . In the first strategy, the present invention performs a grid search to optimize the number of predicted lag values.

In the second strategy, for a data set with a large number of time series, such as a data set with more than 500 time series, the present invention adopts a single general prediction model to predict all the time series. This method allows to exploit the similarity between time series and build a complex forecasting model. The present invention adopts a light-weight boosting tree (Light Gradient Boosting, Light GBM) model, and uses the scaled lag time-series values, time-series specific features and temporal features. For the same reason as the input, in the training phase of the prediction model, the historical prediction data and the historical actual data of the above-mentioned types are also used as the training data. Assuming that the prediction model is used to predict the sales volume of beverages in the next month, the time series specific features such as temperature, humidity or season can be used, and the time features can be used such as the number of sunny days in the last month. In this strategy, the hyperparameters in the forecasting model corresponding to each time series can be cross-referenced or inherited from each other. For example, the hyperparameter settings for time series C _t may be the same as the hyperparameter settings for time series B _t . In the second strategy, the present invention performs a grid search to optimize the number of leaf nodes in the tree built by Light GBM and the minimum number of observations in each leaf node hyperparameter, and for Other parameters maintain default values, among which hyperparameters are used to represent the structure and branch status of the tree. As long as the optimal hyperparameter configuration is found, the present invention uses multiple models for training during cross-validation in order to validate the parameters of the blender 10. The blender 10 revises the prediction result of the prediction model to be more accurate according to the hierarchical constraints. The above grid search can also be replaced by random search to reduce the search time.

For the above two strategies, the present invention performs ten-fold blocked cross-validation, that is, the validation sets are located in the same time window, thereby selecting the best hyperparameter combination. The verification techniques described above have been shown to be effective for time series.

In real-world prediction models, it is often necessary to minimize a given metric, such as mean absolute scaled error (MASE) or mean absolute error (MAE), and the prediction model's The choice depends on the selected indicator.

In order to demonstrate the flexibility of the present invention, an embodiment of the present invention adopts the following two indicators: the first one is Mean Absolute Scaled Error (MASE), and the second one is Mean Logarithm of Absolute Error (Mean Logarithm of Absolute Error, MLAE). The present invention trains multiple prediction models with different loss functions based on these two indicators. For example, MASE is used as the loss function for the MASE indicator, and MLAE is used as the loss function for the MLAE indicator. Selecting a loss function corresponding to the metric for the metrics of the predictive model is an intuitive and convenient approach.

In another embodiment of the present invention, for an almost constant time series, the present invention does not use MASE as a loss function to avoid generating unstable prediction results. In this alternative embodiment, the loss function is, for example, doubling the error plus the original error within the average sample.

In yet another embodiment of the present invention, in the training stage or the verification stage of the prediction model, different weights may be set for the difference between the predicted value and the actual value. For example, if the predicted yield is greater than the actual yield, the output value of the loss function is multiplied by the first weight as the prediction error; if the predicted yield is less than or equal to the actual yield, the output value of the loss function is multiplied by the second weight as the second weight. error, where the first weight is greater than the second weight. In practice, considering that the production volume is greater than the sales volume, the inventory rate will increase, so different error values are generated by setting different weights to reflect the actual situation.

In yet another embodiment of the present invention, the index adopted by the prediction model of each time series can be determined according to the importance of each node in the hierarchical structure. For example, if in Figure 1, node A is more important than nodes D and E, MASE is used as the loss function in the prediction model of time series A _t , and the prediction of time series D _t and E _t is used as the loss function. In the model, the Mean Absolute Error (MAE) is used. Conversely, if the importance of nodes D and E is greater than that of node A, MLAE is used as the loss function in the prediction model of the time series D _t and E _t , and MAE is used as the loss function in the prediction model of the time series A _t . function.

Please refer to FIG. 2 , step S2 is “generating an underlying vector according to the independent prediction vector and an encoding network”. To be more specific, according to the plurality of independent predicted values generated in step S1 and the encoding network P shown in FIG. 3 , a plurality of low-level predicted values corresponding to the bottom-level nodes are generated, and these low-level predicted values constitute a bottom-level vector. The number of independent predicted values in step S1 is greater than the number of underlying predicted values in step S2.

In an embodiment of the present invention, the encoding network P is, for example, an encoding matrix. The encoding matrix is used to map independent prediction vectors to bottom level vectors.

In an embodiment of the present invention, a generic function P: R ^N → R ^M represented by a neural network is used to generalize the M×N matrix, where N represents the number of all nodes in the hierarchical structure , M represents the number of leaf nodes in the hierarchical structure.

轉換為4維的底層向量

。底層預設值

分別對應於圖1的底層節點D、E、F及G。 Based on the hierarchical example of Fig. 1, please refer to Fig. 3, the encoding network P converts the 7-dimensional independent prediction vector

Convert to 4-dimensional underlying vector

. low-level default

They correspond to the underlying nodes D, E, F and G of FIG. 1, respectively.

For the encoding network P in the blender 10, the present invention adopts a feed-forward network with a Rectified Linear Unit (ReLU) as an activation function, and uses the output layer of the feed-forward network. Size is set to the number of underlying presets.

The present invention proposes the following two architectures to implement a feedforward network: the first is a standard fully connected network, as shown in FIG. 4A . The second is the simplified version of the full connection connected to the network, as shown in Figure 4B. The second architecture allows the output of a given underlying time series to depend only on itself and the forecasts of the previous level at all levels.

受所有層級的時間序列預測值影響，即

。在圖4B簡化版的全連接網路中，

只受本身，其父節點及其祖父節點的影響，即

。由於圖1中節點B的預測值並不受節點F及G的預測值的影響，因此，在全連接網路中節點B與F的連線以及節點B與G的連線可被移除。簡化版的全連接網路雖然在表示能力(representative power)弱於全連接網路，然而其仍保留自下而上、自上而下、自中向上下(middle-out)以及上述組合的表示空間。 Please refer to the hierarchical relationship shown in FIG. 1 and illustrate as follows: In the fully connected network shown in FIG. 4A , the bottom prediction value corresponding to the bottom node D

is affected by the time series forecast values at all levels, i.e.

. In the fully connected network of the simplified version of Figure 4B,

is only affected by itself, its parent and its grandparents, i.e.

. Since the predicted value of node B in FIG. 1 is not affected by the predicted value of nodes F and G, the connection between nodes B and F and the connection between nodes B and G can be removed in the fully connected network. Although the simplified version of the fully connected network is weaker than the fully connected network in terms of representation power, it still retains the representations of bottom-up, top-down, middle-out, and combinations of the above. space.

For a given number of levels of hierarchy, as the number of time series grows, the number of parameters required to train grows quadratically in the case of a fully connected network and linearly in a simplified version of a fully connected network growing up. In order to reduce the risk of overfitting, in an embodiment of the present invention, when the number of time series exceeds 10 times its own length, the coding network P adopts a simplified version of the fully connected network. In addition, the option to use a simplified version can also be used as a hyperparameter that can be adjusted.

Step S3 is "generating a harmonic prediction vector according to the underlying vector and a decoder". Specifically, a plurality of harmonic predictors are generated according to a plurality of underlying predictors and decoders associated with the hierarchical structure. As shown in Figure 3, the decoder S takes the low-level harmonic predictions as input and reconstructs the predictions of all levels. Both the harmonic prediction vector and the independent prediction vector have the same dimension, that is, the number of independent prediction values in step S1 is equal to the number of harmonic prediction values in step S3.

Referring to FIG. 3 , in an embodiment of the present invention, the decoder S is a fixed 0-1 matrix, as shown below.

轉換為7維的調和預測向量

。 The decoder S converts the 4-dimensional underlying vector according to the hierarchical structure constraints as shown in Figure 1.

Convert to a 7-dimensional harmonic prediction vector

.

Each element of the harmonic prediction vector corresponds to a prediction value. In other embodiments of the present invention, the decoder S may also be a linear or nonlinear function.

In an embodiment of the present invention, the structure of FIG. 3 may correspond to the following equation:

為獨立預測向量，

為調和預測向量，S為解碼器S對應的0-1矩陣，P為編碼網路對應的0-1矩陣。因此，在最佳組合及跡最小化等方式中，P矩陣為一個稠密矩陣(dense matrix)。在自上而下方式中，將P矩陣中的第一行填入多個總和為1的數值，其餘元素則設置為0。換言之，本發明提出的架構中涵蓋傳統用來預測階層式時間序列的方式。 in

is an independent prediction vector,

is the harmonic prediction vector, S is the 0-1 matrix corresponding to the decoder S, and P is the 0-1 matrix corresponding to the encoding network. Therefore, in the best combination and trace minimization, the P matrix is a dense matrix. In a top-down approach, the first row of the P matrix is filled with values that sum to 1, and the remaining elements are set to 0. In other words, the framework proposed by the present invention covers the traditional methods used to predict hierarchical time series.

The present invention has two main advantages: generalization and flexibility. The generalization advantage means that the model of the present invention has a broad representation space, which covers and extends past prediction methods, and allows for nonlinearity. The elasticity advantage means that the present invention allows the use of an appropriate loss function in the training phase to achieve a specified target performance. Existing methods are simple heuristics (such as bottom-up, top-down) or under different assumptions that estimate Coefficient error minimization (eg optimal harmonic, trace minimization). For example, if the target is Mean Logarithm of Absolute Error (MLAE), use MLAE as the loss function. Alternatively, if you are interested in a specific level in the hierarchy, you can assign a higher weight to the corresponding loss function term. Similarly, if the importance of the error depends on the metric or asymmetry, the present invention can change the loss function accordingly to optimize towards the goal.

Furthermore, the model proposed by the present invention has the advantage of being practically easy to implement and easily accessible to the rapidly growing deep learning community. Complex statistical models such as optimal binding or trace minimization are employed relative to traditional approaches. Furthermore, if the predictive model can be expressed in a deep learning framework, the present invention allows stacking a reconciler network on top of the predictive model and simultaneously train the reconciler and fine-tune the predictive model.

The present invention has the following contributions and effects: The reconciliation method proposed by the present invention is built on top of any prediction method that takes time series as input. The easy-to-implement reconciliation method proposed by the present invention is more versatile and flexible than existing methods. The traditional method can be regarded as a special case in the architecture proposed by the present invention. The present invention allows for distinct loss functions for various practical considerations.

In conclusion, based on the neural network of the encoder-decoder model, the present invention proposes a new method to reconcile the prediction of hierarchical time series. The encoder is a trainable neural network that takes as input the independent predictions and outputs the reconciled predictions at the bottom layer. The decoder is a fixed matrix that accurately reconstructs the predictions of all levels from the underlying encoded predictions. The present invention encompasses and extends the representation space of existing methods, is extremely flexible, and is easy to implement.

Although the present invention is disclosed in the foregoing embodiments, it is not intended to limit the present invention. Changes and modifications made without departing from the spirit and scope of the present invention belong to the present invention the scope of patent protection. For the protection scope defined by the present invention, please refer to the attached patent application scope.

S1, S2, S3: Steps

Claims (10)

A hierarchical time series forecasting method is suitable for generating a plurality of harmonic forecast values of a plurality of nodes in a hierarchical structure, wherein the nodes respectively have a plurality of time series, the harmonic forecast values correspond to the time series, and the Some nodes include multiple underlying nodes, and the method includes: generating a plurality of independent forecast values corresponding to the time series using a plurality of forecast models; generating a plurality of underlying predicted values corresponding to the underlying nodes according to the independent predicted values and an encoding network; and generating the harmonic predictors according to the underlying predictors and a decoder associated with the hierarchy; wherein The number of independent predictors is greater than the number of underlying predictors and equal to the number of harmonic predictors; The independent predictor and the reconciled predictor corresponding to the same one of the time series are consecutive in time. The hierarchical time series prediction method according to claim 1, wherein the encoding network is a feed-forward neural network, and the training data of the encoding network includes a plurality of historical prediction values and a plurality of historical actual values value. The hierarchical time series forecasting method of claim 1, wherein each of the forecasting models is a linear autoregressive model, and hyperparameters of each of the forecasting models are independently adjusted in the training phase. The hierarchical time series forecasting method as claimed in claim 1, wherein the forecasting models are lightweight boosted tree models, and hyperparameters of the forecasting models are referred to each other in the training phase. The hierarchical time series prediction method according to claim 1, wherein when the number of the time series is greater than a threshold, the prediction models are lightweight boosted tree models. The hierarchical time series forecasting method according to claim 1, wherein the loss function of each of the forecasting models corresponds to the verification index of the forecasting model. The hierarchical time series prediction method according to claim 1, wherein the loss function corresponding to the time series located at the upper layer in the hierarchical structure is the mean absolute proportional error, and the loss function corresponding to another time series located at the lower layer is mean absolute error. The hierarchical time series prediction method according to claim 1, wherein the loss function corresponding to the time series located at the lower layer in the hierarchical structure is the mean logarithmic absolute error, and the loss function corresponding to another time series located at the upper layer is mean absolute error. The hierarchical time series forecasting method according to claim 1, wherein the forecasting model is used to output a forecast value and a forecast error, and when the forecast value is greater than an actual value, multiply the loss function by a first weight as For the prediction error, when the predicted value is not greater than the actual value, the loss function is multiplied by a second weight as the second error, wherein the first weight is greater than the second weight. The hierarchical time series prediction method according to claim 2, wherein the feedforward network has a fully connected layer, and each element of the fully connected layer in the independent prediction vector is based on each element in the underlying vector The hierarchical relationship determines whether there is a connection.

Images