App Download Forecasting: An Evolutionary Hierarchical Competition Approach

1 Introduction

Predicting and understanding products' future sales is an essential task for companies to follow users' satisfaction level and improve business revenue. It also enables investors to estimate a company's value and allows users to follow the trends of a market.

Usually, there is intense competition in a product market. Similar to the competition in the natural world (among animals and plants), which plays an irreplaceable role in natural selection, the competition in a product market also greatly affects the development and sales of products. As illustrated by Figure 1, there is often a three-level hierarchy in a typical market, where the top-level is users, bottom-level is products (here we use apps as an example), and in-between is various categories of user demands, e.g., the demands for having food, staying healthy, and playing games. Normally, the overall amount of these categories of demands from users is relatively stable. When users' engagement in one category of demand increases, their time spent on other demand categories will decrease, which leads to the competition among different categories of demands (in the middle level in Figure 1). In a lower level, each product normally serves several categories of user demands [Radosavljevic et al., 2016]. For example, as shown in Figure 1, Wechat is mainly used for social activities, while its step count function caters to users' health demands. These products compete with each other by providing engaging functions to cater to various categories of demands, and this forms the competition among products (in the bottom level in Figure 1). Therefore, there exists a twolevel competition in a typical product market.

It is challenging to model such hierarchical competition among products. Traditional sales forecasting methods, such as ARIMA [Brockwell and Davis, 2016], Recurrent Neural Networks [Chandra and Zhang, 2012], do not consider such hierarchical competition and often only analyze the sales time series of a single product. There are also several sales prediction methods using side information, e.g., reviews [Yu et al., 2010] or spatial information [Garber et al., 2004], to improve accuracy. The side information, however, cannot effectively model the competition pattern among products. Although a few models try to use the interactions among items, such as MLDS [Rogers et al., 2013] and Trimine [Matsubara et al., 2012], they also lack the capabilities to describe the hierarchical competition patterns.

Therefore, we propose an Evolutionary Hierarchical CompetitionModel (EHCM) to model the time-evolving hierarchical competition among products and to provide more accurate product sales forecasting. Specifically, EHCM considers the competition patterns at two levels: the product level and demand category level, and exploits a linear dynamic system to model the evolutionary competition and interactions among the two competition levels. For the first time, EHCM

organically integrates the hierarchical competition analysis with time series analysis for forecasting. Since the app market is a typical product market with a large amount of products and users (where the sales of an app is the download amount), in this paper we investigate EHCM with the specific application of app download amount forecasting. In summary, this paper offers the following main contributions:

• We propose a novel evolutionary hierarchical competition relationship among products, and investigate a two-level competition hierarchy (product level and demand category level) for sales forecasting.
• We systematically integrates evolutionary hierarchical competition analysis with multi-scale time series forecasting, which can effectively detect long-term competition patterns among products.
• We use a real-world app download data for over 20 thousands apps in the Chinese market to evaluate our model. The results shows that EHCM significantly ourperforms the baseline methods.

2 Background for Hierarchical Competition

In biology, species co-existing in the same environment will compete with each other for resources, and the ones that are less competitive will gradually die out [Begon et al., 2005; Sahney et al., 2010]. Competition in the natural world is hierarchical. The food resources that each species relies on establish the relations among different species, forming the food chain [Briand and Cohen, 1987]. The position of a species in a food chain represents its trophic level. Typically, trophic level 1 is the producers (or autotrophs in biology) who absorb nutrients and water from the natural world and manufacture organism using photosynthesis. Trophic level 2 is the primary consumers (or herbivores) who consume producers as food. Species occupying the same trophic level will compete for food resources obtained from the lower trophic level (or natural resources, like water, soil, and sunshine)

Similar to the competition pattern among species, products in a free market also compete with others vigorously for survival [Johnson et al., 2013]. Users, the fundamental assets in a market, are similar to natural resources in the environment. Users have various categories of demands in their daily life, e.g., demands for food, entertainment, and health. For the sake of analysis convenience, assuming that the total demands of a number of users are stable (at least within a certain period), each category of demand competes with others for more user "resources", which is analogous to producers' competition for resources in biology. For example, when users' total demands for games increase (e.g., when games like Pokemon Go rapidly become popular), their demands for reading or exercising will decrease simultaneously. Various products in the market compete with others for these categories of demands, which are their "food", by providing various functions to cater to these demands. Such hierarchical competition relations are illustrated in Figure 1.

3 Method

3.1 ProblemDefinition

Assume there are M demand categories of users for app services: C = {c1, c2, ..., cM}, such as entertainment, social, etc. Different apps can cater to users' different demands. Assume that there are N apps in an app system, represented as A = {a1, a2, ..., aN}, each of which is at the service of at least one demand category (more than one category for most apps). The collected download amounts of these apps form the download matrix X ∈ RN×T , where T is the number of time steps. The download amount of app an in time t is Xt,n.

The problem is defined as forecasting the amount of download of each app. Specifically, given the download amount of all the N apps in the past T time steps, our goal is to forecast the download amount of each app an in future ˆ T time steps, which is represented as ˆXn ∈ R1× ˆ T .

3.2 Model Formulation

Model Overview

To solve this problem, we propose a forecasting model which systematically integrates evolutionary hierarchical competition patterns with time series analysis. Specifically, we first split time series matrix X into several stable segments, within each of which the competition among apps is relatively steady and the trends of number of downloads are almost unchanged. Then, we exploit an evolutionary matrix trifactorization method to explore the hierarchical competition in each segment, obtaining the app service factor, demand category competition factor, and user demand time series factor, and we investigate the evolution of the first two competition factors. Next, we adapt wavelet transform method to decompose user demand time series into different scales and apply a multi-scale autoregression algorithm for forecasting.

Hierarchical Competition in EHCM

In a constant environment, the system approaches a stable equilibrium after a period of competition among different species [Huisman and Weissing, 1999]. We assume that the competition among apps will also lead to a temporary stabilization over a period of time. During that time, the download amount of each app has a stable fluctuation pattern. For example, Figure 2 shows the download amounts of two apps over one year in the "Entertainment" category on the iOS platform. We can see that the competition relation between these two apps can be roughly segmented into 4 sections (illustrated by dotted lines). In each segment, the fluctuations of the two sequences have stable patterns, e.g, in Segment 1, download amount of app 1 has a steady increasing trend, while the download amount of app 2 continuously decreases at a stable speed as well.

According to the stabilization in different continuous time periods, we can divide the T time steps into L stabilization segments. In each segment, the competition among apps approaches to a stable equilibrium, and the download trends of these apps have minor changes. The way we find these stabilization segments is to find the segments that minimize the intra-segment variance of download matrix X [Himberg et al., 2001; Fu, 2011]. When we segment X into L sub-segments X = {X1 , X2 , ..., XL}, the total intra-segment variance of the L matrices is computed as Ω(X) = 1 T ∑Ll=1 ∑sl t=1 ‖Xlt -µl‖2F , where ‖ · ‖F is the Frobenius norm of a matrix, µl ∈ RN×1 is the mean vector of segment Xl , and S = {s1, s2, ..., sL} is segment length list (∑Ll=1 sl = T ). Here we adopt the Global Iterative Replacement (GIR) method [Himberg et al., 2001] to segment matrix X into L sub-segments. The main idea is that we first randomly divide matrix X into L segments, and then iteratively merge adjacent segments and search for a new division position that minimizes Ω(X).

As mentioned before, the competition in a market is hierarchical. To obtain a compact competition model and hence retain effective prediction performance, we assume that in each stabilization segment l, the bulk of interactions among apps and number of downloads can be represented hierarchically by three levels of factors: app service factor, demand category competition factor, and user demand time series factor:

where

• Gl ∈ RN×M is the app service factor for segment l. We assume that an app can cater to users' more than one demand categories. Gln,m represents the demand amount that app an can serve for category cm in segment l. App service factor is time-evolving among the L segments, representing the app competition evolution.
• Bl ∈ RM×M is the demand category competition factor for segment l. In Bl we obtain M latent demand categories, and each demand category dynamically competes with others for limited user "resources". Blm1,m2 denotes the demand proportion that category cm1 takes from cm2 in segment l. Demand competition factor is also time-evolving, reflecting the demand category competition evolution.
• Zl ∈ RM×sl is the user demand time series factor for M categories in segment l. We assume that user demands

can be quantified and will influence app download quantity with the joint leverage of the app service and demand category competition factors.

We can obtain these factors and matrices through matrix tri-factorization [Zhuang et al., 2013], which can be obtained by optimizing the following objective function:

Competition Evolution

Next, we consider the competition evolution among the L stabilization segments. From the above analysis, we can see that each app competes with each other for limited demand resources. To enable efficient evolution-modeling, we assume that the app competition transferring from segment l to l + 1 can be represented as linear transfer matrix AG. To further simplify this dynamic system, we propose a method in which the common structures of all the demand transfers are represented as the same transfer matrix AG. Here, given Gl , l = 1, ..., L - 1, we can generate Gl+1 according to the conditional distribution:

where Q is the conditional covariance shared by all Gl . Similarly, we can generate demand category competition factor Bl+1 according to the conditional distribution:

where AB is the transfer matrix which describes the dynamics of evolving demand competition factors B1 , ..., BL, and R is the conditional covariance shared by all Bl . Although the assumed linear transformation might cause information loss for the true competition progression, it provides a valid approximation which reduces the model complexity and can be computed deterministically and efficiently.

In a nutshell, our goal now is to estimate the parameters {Gl , Bl , Zl , AG, AB}, for l = 1, ...,L that minimize the objective function:

User Demand Forecasting

We then consider the demand time series evolution. Different from the above two types of competition factors, time series matrices Zl , l = 1, ...,L, contain temporal information themselves. To obtain the complete time series information, we assemble the L time series of each demand category into a whole sequence, obtaining a new time series matrix Z ∈ RM×T . We aim to predict the future demands of the M time series from Z.

In time series forecasting, a significant challenge is that: learning too much noise may cause overfitting while neglecting fast dynamic components may cause underfitting [Soltani, 2002]. To tackle this problem, we decompose a series into different scales and capture the dynamic components at each scale to avoid both overfitting and underfitting. Here we adopt the Wavelet Transform method [Percival and Walden, 2006] to decompose a time series Zi ∈ R1×T into multi-scale components {Wi1 , ...,WiJ }, where the decomposition level is J - 1. Unlike traditional discrete wavelet transform, which picks up every second data point in a sequence at each level, we apply a non-decimated transform. This means that all the series obtained from the decomposition have the same size as the initial series, i.e., Wij ∈ R1×T for each j. Figure 3(b) shows a 3-level non-decimated decomposition of an app download time series, where A represents approximation and D represents detail. The original signal passes through a low-pass and a high-pass filter to get one high-frequency component "D 1" and low-frequency component "A 1", and then using the same method the sequence "A 1" is futher decomposed into "D 2" and "A 2", and so forth. Since "A n" is the sum of "D n + 1" and "A n + 1", the original time series Zi can be represented by J - 1 detail sequences and 1 approximation sequence.

After the wavelet transform, we forecast the future value for each detail series and the approximation series. We apply the multi-scale autoregressive method [Renaud et al., 2005; Ernst et al., 2007] to perform such forecasts. Specifically, for each time series Zi, we have:

where (2 + 2J (K - 1)) ≤ t ≤ T and (Wi1 , ...,WiJ ) are the wavelet transform results of time series Zi, i = 1, ...,M, in which (Wi1 , ...,WiJ-1 ) are the detail series and WiJ is the approximation series. K is a constant (e.g., 2). After we obtain the parameters Yi,ˆ t for each i ∈ (1, ...,M) and each ˆ t ∈ (1, ..., ˆ T), we can forecast the future ˆ T values of each time series Zi.

3.3 Optimization

We first estimate parameters {Gl , Bl , Zl , AG, AB} for l = 1, ...,L in Equation (5) with stochastic gradient descent (SGD), where the main task is to obtain the gradient of each parameter. We compute their gradients as follows:

• Gradient of Gl :

where λ equals 1 for l = 2, ..., L and equals 0 otherwise, β

equals 1 for l = 1, ..., (L - 1) and equals 0 otherwise.

where λ and β have the same definitions as above.

• Gradient of AG:

• Gradient of AB has the same form with AG.

Next we estimate parameters Yi,ˆ t with the least square method. For each time series Zi, i = 1, ...,M, and each ˆ t ∈ (1, 2, ..., ˆ T), we can rewrite Equation (6) as Z = WY + ǫ, where Z ∈ R ¯ T×1 , ( ¯ T = (T - 2J (K - 1) - 1)), W ∈ R ¯ T×JK , Y ∈ RJK×1 , ǫ ∈ R ¯ T×1 is the error vector. The approximation of Y (represented as ˜ Y) is given by ˜ Y = (W⊤W)-1W⊤Z.

With all the learned parameters, we can obtain future app service factor ˆG through Equation (3), obtain future demand competition factor ˆB through Equation (4), and obtain demand time series matrix ˆZ through Equation (6). Then, we apply Equation (1) to forecast download amount of each app.

4 Experiment

4.1 Set-up

Dataset

From a commercial app analysis platform, we collect the download amount data for over 20 thousand apps on the iOS platform from Jul. 10th 2015 to Jan. 9th 2017 (550 days) in the Chinese market. The dataset consists of the daily download amount and the category of each app. On the iOS platform, the apps are classified into 25 categories: Entertainment, Games, Books, Medical, etc. Considering each day as one time step and filtering the apps that have zero download for 2 continuous months during the last 250 days, we obtain a download matrix X′′ ∈R20,781×550 for 20,781 apps. We apply a moving window with a 365-day length and a 37-day moving step on X′′ and obtain 6 sub-matrices X′ ∈R20,781×365 .

Since app developers or app investors may be interested in the future prospect of marketing in different granularities, we forecast the future app download amount in one week, half a month, and a month, respectively.. We divide each sub-matrix X′ into a training matrix and testing matrix at different positions for such settings. For example, when we need to evaluate the forecasting accuracy of half a month in the future, we divide each X′ into X ∈ R20,781×350 as the training data and ˆX ∈ R20,781×15 as testing data.

Table 1: Errors of EHCM when forecasting length is 15 days

Comparing Methods

The methods we compare with EHCM include:

• ARIMA. ARIMA [Brockwell and Davis, 2016] is an effective single time series analysis algorithm. Here we apply the automatic ARIMA approach proposed in [Hyndman et al., 2007].
• ERNN. Elman Recurrent Neutal Networks (ERNN) [Chandra and Zhang, 2012] is a widely used three-layer recurrent neural network, which is capable of processing sequentially ordered stimuli.
• Wavelet. Wavelet Transform Prediction (Wavelet) [Renaud et al., 2005] is a wavelet-based multi-scale autoregressive prediction method introduced in Section (3.2).
• MLDS. Multilinear Dynamical System (MLDS)[Rogers et al., 2013] models a time series tensor as a multilinear projection from certain latent tensors. Here we set the dimension of the input tensor as two.

We also add two more compared methods in our experiment: HCM and ECM. HCM is the EHCM model without temporal evolution, in which we set the segment amount L=1 to investigate the importance of modeling evolution in app competition. ECM is the EHCM model only having a onelevel competition, in which we only apply a traditional nonnegtive matrix factorization method (cf. Section 3.2) to investigate the effect of hierarchical competition.

Metric

The metric we use to evaluate the app download forecasting error is Relative Euclidean Distance [Rogers et al., 2013]:

where ˆX and ˜X are the app download matrix and forecasting matrix, respectively.

4.2 Results

We first present the results of EHCM compared with various methods. Figure 4(a) shows the average RED results of 6 test windows in three different forecasting granularities: 7 days (one week), 15 days (half a month), and 30 days (one month). We can observe that errors increase when the forecasting period becomes longer (from 7 days to 30 days) for all the models. When the granularity is 15 days and 30 days, EHCM has the best performance compared with other methods. When the granularity is 7 days, EHCM outperforms all the other methods except ARIMA. To investigate the underlying reason, we plot Figure 5, which shows the daily results (15 days) of one test window. We can see that ARIMA has the lowest error in the first 3 days, while EHCM has dominantly low errors afterwards. This shows that EHCM has a big advantage for long-term forecasting than short-term forecasting. ARIMA converges quickly to the mean of test data, as its error converges to 0.5 as shown in Figure 5(a). Moreover, Figure 5(a) also shows that ERNN's performance gradually becomes worse when the forecasting period is longer, which is also reflected in Figure 4(a). We can also oberve that HCM has worse performance than ECM, which demonstrates that capturing the competition evolution is more crucial than hierarchical patterns in forecasting, especially when forecasting period is longer (Figure 5(b)).

Next, we evaluate the performances of EHCM with different parameters. We vary the demand category amount M from 5 to 30, and vary the stabilization segment amount L from 7 to 27. Table 1 presents the average results for this experiment when the forecasting period is 15 days (where training period is 350 days). We can see that EHCM has the best performance when M=20 and L=19 or 23. When we fix L, EHCM has the lowest error when M=20. This indicates that classifying all the apps into 20 categories according to the demand they cater to should be sufficient for the 25 categories used in the App Store. Moreover, we can also observe that EHCM perfoms better when L=19 or 23 for a fixed M. This indicates that EHCM have a better performance when the average length of each segment (18.5 or 15.2 days for L=19 or 23 respectively) is close to the test period (15 days).

The competition evolution pattern is crucial in EHCM, since it detects the time-varying competition relationships at both the app level and demand category level. Figure 6 shows the evolution of demand category competition matrix Bl along one year when M=20 and L=23, where we plot 4 matrices: B1 , B8 , B15 , and B23 . We normalize the elements in these matrices into the range of [0, 1], making it easier for observation. These figures show that the competition among the 20 latent categories is evolving during the year, and the highlights of the diagonal lines represent each demand category inheriting most of its own demands during competition. To illustrate the latent demand categories more clearly, we show representative apps within several categories (here we assume app an mainly serves demand category m if Gn,m is the largest value in row Gn averaged over all segments. The competitiveness of latent categories 13 to 20, mainly containing readers, English learning, English dictionary, weather, urban environment, stock-market, and exercise related apps, has a noteworthy decrease, while the advantage of latent category 8, consisting of apps on financial management, hospital check-in, flea market etc., fluctuates throughout the year.

In the App Store, apps are classified into 25 categories, e.g, Social, Health, Travel, etc. Empirically, apps in the same category will satisfy users' similar demand categories. To validate this intuition, we exploit the Pearson's Correlation (PC) among these apps' service patterns. Specifically, we compute the PC between each two apps in matrix Gl , which is the app service factor, and show the correlation in Figure 4(b). We add dotted lines to divide apps into different categories. We can observe that there are no apparent correlations among apps in each category. This means that the classification for these apps in the App Store is not rational enough if only considering how they cater to user demands. When we assume that app an belongs to category m if Gln,m has the largest value in row Gln, , we can compute the correlations among these apps, which is shown in Figure 4(c). The obvious highlights along the diagonal clearly show a higher app service correlation with their categories defined in this approach.

5 RelatedWork

5.1 Time Series Evolution

The investigation of time series evolution is a fundamental task of weather forecasting, market analysis, user mobility prediction, and so on [Berrocal et al., 2010; Kahn, 2010; Sadilek and Krumm, 2012]. Some state-of-the-art time series analysis methods, like ARIMA [Brockwell and Davis, 2016], Markov chain [Liao et al., 2012], Recurrent Neural Networks [Chandra and Zhang, 2012], and Wavelet Transform based prediction [Renaud et al., 2005], are widely applied in evolution analysis. All of these methods only focus on the analysis of a single series, neglecting the interactions among a group of series.

To resolve this disadvantage and explore the connections among a group of time series, [Dunlavy et al., 2011; Matsubara et al., 2012] combine matrix factorization with time series analysis for time-evolving datasets. They firstly decompose a matrix into latent factors and then apply time series forecasting methods on the temporal factor. [Rogers et al., 2013] present a multilinear dynamical system, which decomposes the tensor in each time step and utilizes the evolutionanalysis of core tensor to predict future values. Nevertheless, these methods only consider one-level relationships among time series, ignoring the hierarchical interactions.

5.2 Product Forecasting

Products are the lifeblood of business and markets. Forecasting the sales of products helps to understand customer satisfaction and control product inventory, thus continuously improving the business in question. Therefore, product forecasting is always a crucial task in business management. [Yu et al., 2010] propose a regression model for sales prediction, considering the quality factors of online reviews of products. [Wu and Brynjolfsson, 2014] utilize a seasonal autoregressive method to model the relationship between queries submitted to Google's search engine and housing market indicators to predict housing prices and sales. For new product sales forecasting, a spatial divergence approach is applied in [Garber et al., 2004], taking into account both sales amount and spatial information of existing products. However, these methods neglect competition relationship among products.

6 Conclusion

We have proposed EHCM, a systematic method to integrate hierarchical competition evolution analysis with time series forecasting, and applied an evolutionary matrix trifactorization method to exploit hierarchical competition interactions among products. We have also explored the temporal patterns through a multi-scale wavelet prediction approach. Extensive experiments using a real-world dataset validate that EHCM outperforms state-of-the-art approaches in various forecasting granularities. Although EHCM is based on a dataset of app download amounts, we believe that the hierarchical competition evolution method can be easily generalized to other product sales forecasting applications.