SSMF: Shifting Seasonal Matrix Factorization
Authors: Koki Kawabata
Siddharth Bhatia
Rui Liu
Mohit Wadhwa
Bryan Hooi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Matrix Factorization
Seasonality
Regime Switching
Online Algorithm

Abstract: Given taxi-ride counts information between departure and destination locations, how can we forecast their future demands? In general, given a data stream of events with seasonal patterns that innovate over time, how can we effectively and efficiently forecast future events? In this paper, we propose Shifting Seasonal Matrix Factorization approach, namely SSMF, that can adaptively learn multiple seasonal patterns (called regimes), as well as switching between them. Our proposed method has the following properties: (a) it accurately forecasts future events by detecting regime shifts in seasonal patterns as the data stream evolves; (b) it works in an online setting, i.e., processes each observation in constant time and memory; (c) it effectively realizes regime shifts without human intervention by using a lossless data compression scheme. We demonstrate that our algorithm outperforms state-of-the-art baseline methods by accurately forecasting upcoming events on three real-world data streams.

SSMF: Shifting Seasonal Matrix Factorization
Koki Kawabata
Siddharth Bhatia
SANKEN Osaka University koki@sanken. osaka-u.ac.
National University Singapore
siddharth@comp. nus edu
Rui Liu
Mohit Wadhwa mailmohi www.hwa@gmaalll.coom
National University of Singapore xxliuruiabc@gmali com
Bryan Hooi
National University of Singapore thooi@comp nus, edu. sg
Abstract
Given taxi-ride counts information between departure and destination locations. how can we forecast their future demands? In general, given a data stream of events with seasonal patterns that innovate over time, how can we effectively and efficiently forecast future events? In this paper, we propose Shifting Seasonal Matrix Factorization approach, namely SSMF, that can adaptively learn multiple seasonal patterns (called regimes), as well as switching between them. Our pro- posed method has the following properties: (a) it accurately forecasts future events by detecting regime shifts in seasonal patterns as the data stream evolves; (b) it works in an online setting, i.e., processes each observation in constant time and memory; (c) it effectively realizes regime shifts without human intervention by using a lossless data compression scheme. demonstrate that our algorithm outperforms state-of-the-ar baseline methods by accurately forecasting upcoming events on three real-world data streams.
Introduction
The ubiquity of multi-viewed data has increased the importance of advanced mining algo- rithms that aim forecasting future events [Bai et al.) 2019 Wu et al., 2019 Deng et al.) 2020), such as forecasting taxi-ride counts based on their departure and destination loca- tions, and time information, where the events can be represented as stream of tuples (departure, destination, time; count). Infection spread rates during epidemics can also be repre- sented similar form as (location, disease, time; count), and the task forecast the infection count. Given such large data stream produced by user events, how can effectively forecast future events? How can we extract meaningful patterns to improve forecasting accuracy? Intuitively, the problem we wish to solve is follows:
Problem Given an event data stream that contains seasonal patterns. forecast the number future events between each pair of entities in streaming setting.
As natural periodicity occurs in several types of data, one of the promising directions to understand the vital dynamics of data stream is to consider seasonal phenomena. However, high-dimensional data
Equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Relative Advantages of SSMF
SVD/NMF++
RegimeCast
TRMF
SMF
SSMF
Sparse Data Regime Shifts
v
Seasonal Pattern
v
Drifting components
structures in sparse time-series pose many challenging tasks to uncover such valuable seasonal patterns (Chi and Kolda 2012], while modeling seasonality or periodic patterns has been a well-studied topic in literature [Takahashi et al., [201]]. Moreover, in streaming setting, data dynamics vary over time, and thus the models learned with historical data can be ineffective as we observe new data. Although online learning schemes, such as (Schaul et al. 2013 Jothimurugesan et al. 2018 Yang et al. 2018 Nimishakavi et al. 2018 Lu et al. 2019), provide solutions overcome this concern, disregarding all past dynamics fails capture re- occurring patterns in the subsequent processes. On non-stationary data streams, such approaches no longer converge to the optimal parameters but capture average patterns for several phenomena, which causes less accurate forecasting, Adequate methods should retain multiple patterns where each pattern is updated incrementally for prevailing tendencies and leveraged for forecasting.
In this paper, we focus on online matrix factorization for real-time forecasting with seasonality. Specifically, propose streaming method, Shifting Seasonal Matrix Factorization (SSMF), which allows the factorization to be aware of multiple smooth time-evolving patterns as well as abrupt innovations in seasonal patterns, which are retained as regimes. In summary, our contributions are:
1. Accuracy: Outperforms state-of-the-ar baseline methods by accurately forecasting 50-steps ahead of future events.
Scalability: Scales linearly with the number of regimes, and uses constant time and memory for adaptively factorizing data streams.
3. Effectiveness: Finds meaningful seasonal patterns (regimes) throughout the stream and divides the stream into segments based on incremenally selected patterns. SSMF uses a lossless data compression scheme determine the number of regimes.
Reproducibility: Our datasets and source code are publicly available at: https::/www thub com/kokikwbt/ssntt
2
Related Work
Table summarizes the relative advantages of SSMF, compared with existing methods for matrix factorization and time series forecasting. Our proposed method satisfies all the requirements. The following two subsections provide the details of related work matrix/tensor factorization and time series modeling.
2.1 Matrix Factorization
The major goal of matrix/tensor factorization, well known SVD, is to obtain lower-dimensional linear representation that summarizes important patterns (Chi and Kolda 2012), and it has wide range of applications (Hoang al. [2017] Yelundur et al. 2019 Tisijaric et | 2220)_ Non-negative constraint provides an ability to handle sparse data and find interpretable factors [Cichocki et al.
2009]. Takahashi al.) 2017 adapted tensor factorization to extract seasonal patterns in time series as well as the optimal seasonal period in an automatic manner. Yu et al., 2016) formulated the temporal regularized matrix factorization (TRMF), which designed for time series prediction. (Song et al. 2017 Najañi et al. 2019] addressed stream tensor completion but didn't 't extract seasonal patterns. Recently, SMF [Hooi et al. 2019 proposed an online method that incorporates seasonal factors into the non-negative matrix factorization framework, and outperforms CPHW (Dunlavy et al. 2011], which an offline matrix factorization method. However, SMF misses regime shifts which should be modeled individually.

---

2.2 Time Series Analysis
Statistical models, such as autoregression (AR) and Kalman filter (KF), learn temporal patterns for forecasting, thus a lot of their extensions have been proposed [Cai et al. 2015 Dabrowski et al. 2018). RegimeCast (Matsubara and Sakurai [016] focuses on regime detection to obtain compact factors from data streams effectively but it does not consider updating detected regimes. Also, note that they do not consider mining sparse data in the non-linear dynamical systems, while handling missing values has a significant role in time series analysis (Yi et al.] 2016] Abedin et al. [019]. Hidden Markov models are also powerful tools for change detection time series [Mongillo and
Deneve 2008 Montanez et al. 2015 Pierson et al. 2018 Kawabata et al. 2019), but these models represent only short temporal dependency and thus are ineffective for forecasting tasks. Detecting regime shifts in non-stationary data can be categorized in Concept Drift, and its theory and recent contributions are well-summarized in [Lu et al. 2019). In more detail, we consider incremental drift and reoccurring concepts simultaneously. [Wen et al. [019]] tried to decompose scasonality and trends in time series on the sparse regularization framework to handle fluctuation and abrupt changes in seasonal patterns, but this approach does not focus stream mining [Krempl et al. 2014).
3 Proposed Model
In this section, we propose model for shifting seasonal matrix factorization. A tensor we consider consists of timestamped series of (m X n) matrices X()...... X(r). which can be sparse, until the current time point r. We incrementally observe a new matrix X(r + 1) and r evolves (r = r + 1). Our goal is to forecast X(t) where t by uncovering important factors in the flow of data, whose characteristics can change over time. As we discussed the effectiveness of handling seasonal patterns, incorporate seasonal factors into switching model that adaptively recognize recent patterns in forecasting.
3.1 Modeling Shifting Seasonal Patterns
Figure I sshows an overview of our model. In matrix factorization, we assume that each attribute, e.g., a start station where we have a taxi ride, has k latent communities/actiittes, which is smaller than m and n, c.g., the number of stations. Considering such latent seasonal activities, input data stream is decomposed into the three factors: with shape (m x k) and with shape (n x k) for the row and columns of data X(t), respectively, and seasonal patterns W with period s, i.e., (s x k). where k is the number of components to decompose. The i-th row vector w; {wI..... wx } of W corresponds to the i-th season. Letting W, be (k x k) diagonal matrix (zeros on non non-diagonal entries) with diagonal elements as W, X(t) is approximated as follows.
X(t) UW.
More importantly, we extend W by stacking additional W to capture multiple discrete seasonal patterns regimes, which is shown as the red tensor in Figure I Letting g be the number of regimes, our model employs a seasonality tensor W (W(), ..... W where each slice ( captures the i-th seasonal pattern individually. By allowing all these components to vary over time, X(1) can be represented as follows.
X(1) & U (
where: = E (1,...,.9) 9g shows an optimal regime index represent X(I) in the i-th season. That is, our approach adaptively selects (*) as shown in the red-shaded vector in the figure, with regard to the current season and regime. Finally, the full parameter set we want to estimate is as follows.
Problem 2 (Shifting seasonal matrix factorization: SSMF) Given: a tensor stream X(1), ((r) that evolves at each time point, Maintain: community factors: Utt), (tt,, seasonal factors: ((t,, and the number of regime g in streaming fashion.
3.2 Streaming Lossless Data Compression
In the SSMF model, deciding the number of regimes, g. a crucial problem for accurate modeling because it should change we observe new pattern shift. It is also unreliable to obtain any error
3

---

( 1)
U(t 1)
V +
W1 (c) O
V(t)
X(t)
2
m
U(t)
0 (t)
(2) Regime
Selection
X
(1) RegimeExtraction
((t)
g
Figure An overview of model: smoothly updates all the components, U(),, V()). and W(L).
continuously describe data stream (t). required, (1) increases the number of regimes, 9. by extracting new scasonal pattern in the last season {X(t 8 1)...., X(t)). Then, (2) selects the hest (x(2(()) (t) in regimes describe (t)..
thresholds to decide the time when employing a new regime before online processing. Instead, we regime incrementally that it can keep concise yet effective to
want the model to employ summarize patterns. The minimum description length (MDL) principle (Grünwald and Grunwald 2007 realizes this approach, which is defined follows.
X;U.V,
U>> + < +<W>
X,U
Total
Model description cost
Data encoding cost
where
K,U.V is the total MDL cost of X when given set of factors, U, V and W.
Model description cost, < >, measures the complexity of a given model, based on the following equations.
U U (log(m) + log(k) + cp),
V
V (log(n) + log(k) + cr),
W W| (log(g) + log(s) log(k) cc),,
where I shows the number of nonzero elements in given matrix/tensor, OF is the float point cos
Data encoding cost, X| measures how well given model compress original data, for which the Huffman coding scheme add 2001] assigns a number of bits to each element X. Letting à E X be reconstructed data, the data encoding cost is represented by the negative log-likelihood under Gaussian distribution with mean μ and variance o² over errors, follows.
XUU.V
Σ xxX
logg (p.o(x f)
While we cannot compute the cost with historical data streaming setting, straightforward approach obtains the best number of regimes so that the total description cost is minimized. To compute the total cost incrementally and individually when provide with new data, we decompose W approximately into:
g. Σ
W
W
w (log(s) + log(k) cF).
(5)
When new matrix X arrives, decide whether the current W should increase the number g. by comparing the total costs for existing regimes with the total costs for estimated regime.
W best
arg min (WO ..... Wit
X.U.V,'>,
(6)
arg min Wo. W
<0>+2V3+<W><<XUUNW
We used 32 bits.

---

If W(++)) gives the minimum total cost of X. then it belongs to the full W for subsequent modeling. In other words, the size of W is encouraged be small unless we find significant changes seasonal patterns.
Proposed Algorithm
We propose an online algorithm for SSMF on large data streams containing seasonal patterns. Algo- rithm [ summarizes the overall procedure of our proposed method: first detects the best regime for the most recent season through two-step process, namely, RegimeSelcction and RegimeExtraction. Then smoothly updates the entire factors based on the selected regime with non-negative constraints. When deciding the number and assignment of regimes, the algorithm evaluates the cost, [Equation (6) for the most recent season, to ensure the smoothness of consecutive regime-swiie switchiin during season. Thus, the algorithm keeps sub-tensor X' which consists of the matrices from time point t 8 + 1 to t, as queue while receiving new (t). Given X, the best regime time point is obtained as follows.
RegimeSelection, which aims to choose the best regime W Rs that minimizes Equation (6) in {W(1),... ..... ,.... W(s)), }, using the two previous factors U(t 1) and V 1). We compute the total cost, CrS by using U(t - 1), V(t 1) and W RS for X.
RegimeEEttaaction which obtains new regime W RÆ. focuses current seasonality, by applying the gradient descent method to U(t 1), V (f) and W WRs over the whole X.
The intiialization with W Rs prevents W RE from overfitting X' because temporal data, X, can be sparse. It then computes CRE with U(t 1). V 1) and W WRE for X.
If CrS is less than CRE, the best regime index = becomes one of {1, (1.....g)
9). Otherwise, 9 W(g x x k) is extended to W((g + 1) x x k), and then is incremented.
4.1 Regime-Aware Gradient Descent Method
Given new observation ((), consider obtaining the current factors, U(I), V(),, W(I) via the previous ones U(L - 1), V(L 1), W(L ( by minimizing error with respect to ((). This allows the model fit current dynamics smoothly while considering the past patterns. Thus, our algorithm performs the gradient descent method with a small learning rate > O. The gradient step keeps the error with respect to X(t) low. Letting be the current regime index, and X(t) be the predicted matrix of (t) with the previous parameters:
((1) = U(L - ()
the gradient update to ui(() and vt( is given by:
(t(t) (t - (X))(X(()))))))) {(t))va(t 1) (t 8), A(1)) 1)w! (=) 5).
(8)
(9)
The updated (t) and vt) are projected such that
u (t) < max(0, u; (;())): v.)) + max(0, vi(t))
(10)
keep the parameters non-negative After all, the algorithm normalizes (t) and (t) by dividing by their norms [t]](t)] and [t)],, respectively:
(t( + (t(()/ (t:)/((, (f)l: v,(t) <- (1))
(11)
and then w/ multiplied by the two norms keeps the normalization constraint:
- m (t - s) [t)) Ivv(())).
(12)
which captures the seasonal adjustments for the i-th component.
5

---

Algorithm SSMF
Input: (a) New observation (() and previous factors U(1 1), () 1) -)).
Output: Updated factors: U(),, ((t), W(t)
I: / Update the queue keep the most recent season */
X 8 .)............................ (t)):
3: (1) RegimeSelection +/
4: Was f- arg min (WE(WW()....Ww
< <;; U(t ((-
5: (2) RegimeExtraction
6: W RÆ <- min < XI 1), V(L 1), W >;
W
7: CRS =< X;; -t)-)),, V(t 1), Wes 2; CRE =< N; UU 1), V(t Was 2;
CRR is less than CRR then
9: W diag( V RS (L)):
10: clse
11: W(=) diag W (t));;; W(t) Wit 1) WWRR WR 9=
12: end if
13: /* Perform gradient updates */
14: X(t) < U(t (= (t
V)
15: U(t) < 1) + (X(() -()
16: V(t) - V(t v(t-1)+a(X(()
5);
17: for 1:
18: 1 Project onto non-negative constraint */
19: (t( 6 max(0, (t)); (t) + max(0, (t))
20: 1* Renormalize all the factors */
21: w/ u (1 (1-s) s) [[]((]]] [|v[(]]];
22: (.(() (O)] v.(()
v:(l)llv..0]l::
23: end for
24: return U(t), ((t), W(t)
4.2 Forecasting
To forecast t-steps ahead values for a given f > r. we use the latest factors, U(r), V(r), and w (r). where fg is the most recent season observed before time r, which corresponds to the season time Namely, t, = r - (r - mod s). By choosing the best regime 2, which gives the minimum description cost in the last season, the predicted matrix for time f is thus computed as follows.
(t) = U(r) w/ (r))(r). (r)
(13)
4.3 Theoretical Analysis
We show the time and memory complexity of SSMF. The key advantage is that both the complexi- ties are constant with regard to given tensor length, even if it evolves without bound.
Lemma The time complexity of SSMF is O(skkmn + sk2 (m + n)) per time point.
Proof The algorithm first computes the model description cost between X(t) and X(t) using To obtain new regime, it performs Then, for a selected regimes,
regimes in Oggmmn), which is repeated over L= 1- the gradient descent update to X, which takes (e it performs the gradient descent update, which requires O(kmn + k2(m + n)). The projection to non-nege non-negative values and normalization require 0(m + n) for k loops, thus Okk(m + n)) in total. Overall, the time complexity of SSMF is Osskkmn + sk2 (m r2)) per time point.
Lemma 2 The memory complexity of SSMF is O(k(m + n + gs) + (2() per time point.
Proof 2 SSMF retains the two consecutive factors, U and V with shape (m x k) and (n x k), respectively, which requires Okk(m - a)). For seasonal factors in g regimes, maintains a tensor W with shape (g k). It also needs space to retain sparse tensor, |2',, which is the number of observed elements. Therefore, the total memory space required for SSMF O(kim + n + gs) + |x() per time point.

---

Table 2: Dataset Description
Name
Rows
Columns
Duration
Sparsity
Frequency
Tteat
NYC-YT
265
265
4368
98.3%
Hourly
168
500
NYC-CB
409
64
35785
96.2%
Hourly
168
500
DISEASE
57
36
3370
92.4%
Weekly
52
200
Experiments
In this section, show how our proposed method works real tensor streams. The experiments were designed to answer the following questions.
Q1. Accuracy: How accurately does it predict future events?
Q2. Scalability: How does it scale with input tensor length?
Q3. Effectiveness: How well does it extract meaningful latent dynamics/components?
We implemented our algorithm in Python (ver. 3.7.4) and all the experiments were conducted on an
Intel Xeon W-2123 6GHz quad-core CPU with 128GB of memory and running Linux. Table 2 shows the datasets used to evaluate method:
NYC-YT NYC Yellow Taxi trip records during the term from 2020-01-01 2020-06-30 in the pairs of 265 pick-up and drop-off locations.
NYC-CB NYC CitiBike ride trips from 2017-03-01 2021-03-01. We only considered stations that had at- leat 50k rentals during the term, and extracted 409 stations. We then categorized users by age from 17 to 80 and obtained the stream of ride counts the 409 stations.
DISEASE A stream of the weekly number of infections by 36 kinds of diseases at the 57 states/regions in the US, which were collected from 1950-01-01 to 2014-07-27.
5.1 Accuracy
We first describe comparison in terms of forecasting using Root Mean Square Error (RMSE). Since (Hooi et al. [019] outperforms several baselines including CPHW and TSVDCWT, we omit the baselines from our experiments. Our baseline methods include (1) matrix/tensor factorization approaches: NCP [Xu and Yin. 2013]: non-negative CP decomposition, optimized by block coordinate descent method for sparse data. (2) SMF [Hooi al.) 2019: an online algorithm for seasonal matrix factorization, which manages a single seasonal factor. (3) TRMF (Yu et 2016]: method to take into account temporal and seasonal patterns matrix factorization.
For each method, the initialization process was conducted on the first three seasons of an input tensor. For TRMF, searched for the best three regularization coefficients, \ λAR- XLgg in A = f0.0001, 0.001, 0.01, 0.1, 1, 10). Auto-cocfficients of TRMF are set for at time points ......."" [s/2] as well as at three time points s, (s + scasonality. For SSMF and SMF, we determined learning rate a in a = {0.1, 0.2, 0.3, 0.4) by coss-validation in each training data. The number of components was set to among all these methods for a fair comparison. After the initialization, each algorithm takes the first Ptrain time steps, and forecasts the next Ftest steps, as defined in Table 2 This procedure was repeated for every Ptest steps, for example, Ttrain (500, 1000, 1500, in NYC-YT dataset.
1). (s + 2) to consider
Figure 2 shows the results of RMSE on all three datasets, where SSMF consistently outperforms its baselines. We observe that our method shows a better improvement on (b) NYC-CB than (a) NYC-YT, whereas the two datasets have similar characteristies because detecting regime shifts is more effective in forecasting in a longer data duration. DISEASE dataset contains repetitive regime shifts caused by pandemics and developments of vaccines, therefore, SSMF performs forecasting effectively.
page
https://ww.ttyet http://wwcccc...tt..e////aa..t

---

NYC-YT
NYC-CB-U
DISEASE
Model
2.5
SSMF
RMMSE
2.0
TRMF
1.5
75
NGP
1.0
50
0.5
25
0.0
Figure 2: Forecasting performance in of RMSE: SSMF consistently outperforms the baselines therehy showing that regime shift detection adapts the model recent patterns more quickly and effectively than haselines.
5SMF
SMF
TRMF
SSMF
SMF
TRMF
NCP
10a
Wall Wall time clock (sec)
10
Wall clock time (sec)
10
20a
102
Wall clock time
10a
10a
10
10a
10a
109
10-
10-1
6:00
3.0-3-9-00
10000
20000 Time
30000
1000 1500 2000 2500 3000 3500
1000
Time
Time
(a) NYC-YT
(b) NYC-CB
(c) DISEASE
Figure 3: Wall clock time vs. data stream length: SSMF efficiently monitors data streams to find regimes.
5.2
Scalability
We discuss the performance of SSMF in terms of computational time the three datasets. Figure 3 shows the wall clock time vs. data stream length, where the experimental setting is same as of subsection 5.1 The figures show that our proposed method is scalable for mining and forecasting large sparse streams. Although the scalability of SSMF is linear along the number of regimes, the growth rate of its running time greatly less than that of the other offline baselines. This because the proposed method can summarize distinct seasonal patterns as regimes effectively. SMF is the fastest algorithm but does consider regime shifts in online processing. As described in the accuracy comparison section, our method is more effective when data streams have significant pattern shifts, which cannot be captured only with smooth updates on single, fixed component.
5.3 world Effectiveness
In this section, we show an example of the real-world effectiveness of our approach using the NYC- YT dataset. Figure 4 shows the overview of the two representative regimes detected by SSMF, where we selected two of the fifteen components to describe. The bottom bar represents the timeline of regime detection. SSMF kept using the initial regime during the blue term, while it generated new regimes during the red term. The three rows of plots are the visualization of W, U, V, where the first two columns correspond to the blue regimes, and the next two to the red.
In mid March 2020, New York City's governor issued stay-at-home orders, and SSMF detected the event as the regime shifts to adapt to the changed demands of taxi rides. Separating regimes and learning individual patterns help us interpret the results follows: Component of the blue regime shows a seasonal pattern that follows a weekday/weekend pattern. According to the above two maps, more taxi rides are concentrated around Manhattan before the pandemic. In the red regime, however, the strength of the seasonal component became about 10% weaker than the one before. Accordingly, the frequent piekup and dropoff' became smaller. This area has large number of bars and restaurants, suggesting that this component corresponds roughly to cenrttainmnn-rrllatte trips, whose demands

---

0.5
0.5
Components
Comporant
Comporent
Comparen:
Rickup
Pickup (2020-02-11)
Pickup
Pickup (2020-04-14)
Companents
Comparant
Companent
Dropoff location (2020-02-11)
Dropeff location (2020-02-11)
Dropoff lecation on (2020-04-14)
Dropoff location (2020-04-14)
14
Comouncnt 24
36
Companent:
10
Compunenti
12 d0
Compunent? x 5
5
2020-01-01
2020-01-11
2020-01-11
2020-02-01
2020-92-11
2020-02-22
2020-03-03
2020-03-13
2020-03-24
2020-04-03
2020-04-14
2020-44-44
2020-05-05
2020-05-15
2020-05-25
2020-06-05
2020-06-15 15
2020-08-26
Time (pe hour
Figure 4: SSMF can automatically detect regime shifts caused by a pandemic based on multiple seasonal factors:
Component 1, corresponding roughly to entertainment, decays in the pandemic, while component representing trips between Manhattan and Kennedy Airport, experiences shift toward trips from the airport wide of New York City.
are strongly affected by the pandemic. Component 2, in contrast, concentrated between Manhattan and Kennedy Airport, suggesting that this component captures trips to and fro the airport. Under the pandemic situation, this component shifted toward trips from the airport to destinations scattered around New York City. This observation could suggest that customers arrived at the airport, and then used a taxi to avoid public transit. After this phase, our method switched to the first regime again, returning to the previous seasonal pattern. The demand for taxi rides began recover, which roughly aligns with reopening in New York City, which began in early June. Consequently. regime shifts allow distinguish significant changes in seasonal behavior as well as contextual information between attributes. In online learning, the mechanism also supports for quick adaptation and updates, which contributes improving forecasting accuracy.
6 Conclusion
In this paper, we proposed Shifting Seasonal Matrix Factorization (SSMF) method, for effectively and efficiently forecasting future activities in data streams. The model employs multiple distinct seasonal factors to summarize temporal characteristics as regimes, in which the number of regimes adaptively increased based on lossless data encoding scheme. We empirically demonstrate that on three real-world data streams, our forecasting method SSMF has the following advantages over the baseline methods: (a) By using the proposed switching mechanism in an online manner, SSMF accurately forecasts future activities. (b) Scales linearly by learning matrix factorization in constant time and memory. (c) Helps understand data streams by effectively extracting complex time-varying patterns.

---

References
Lei Bai, Lina Yao, Salil S Kanhere, Xianzhi Wang, and Quan Z Sheng. STG2Seq: Spatial-Temporal graph sequence model for multi-step passenger demand forecasting. IJCAI, 2019.
Xunxian Wu, Tong Xu, Hengshu Zhu, I. Zhang, Enhong Chen, and Hui Xiong. Trend-aware tensor factorization for for job skill demand analysis. In IJCAI, 2019.
Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Dynamic knowledge graph based multi-event forccasting. In KDD, 2020.
Eric C Chi and Tamara G Kolda. On tensors, sparsity, and nonnegative factorizations. SIAM Journal on Matrix Analysis and Applicutions, 2012.
Tsubasa Takahashi, Bryan Hooi, and Christos Faloutsos. AutoCyclone: Automatic mining of cyclic online activities with robust tensor factorization, In WWW, 2017.
Tom Schaul, Sixin Zhang, and Yann LeCun. more pesky learning rates. ICML, 2013.
Ellango Jothimurugesan, Ashraf Tahmasbi, Phillip Gibbons, and Srikanta Tirthapura. Variance-reduced stochastic gradient descent on streaming data. In NIP,, 2018.
Bo Yang. Ahmed Zamzam, and Nicholas D Sidiropoulos. ParaSketch: Parallel tensor factorization via sketching. In SDM. 2018.
Madhav Nimishakavi, Bamdev Mishra, Manish Gupta, and Partha Talukdar. Inductive framework for multi aspect streaming tensor completion with side information. In C/KM, 2018.
J Lu, A Liu, F Dong, F Gu, J Gama, and G Zhang. Learning under concept drift: A review. TKDE, 2019.
Minh Hoang, Xuan-Hong Dang, Xiang Wu, Zhenyu Yan, and Ambuj Singh. Gpop: Scalable group-level popularity prediction for online content in social networks. In WWW, 2017.
Anil Yelundur, Vineet Chaoji, and Bamdev Mishra. Detection of review abuse via semi- cmi-supervised binary multi-target tensor decomposition. In KDD, 2019.
Leo Tišljarić, Sofia Fernandes, Tonči Carié, and João Gama. Spatiotemporal traffic anomaly detection urban road network using tensor decomposition method. In DS, 2020.
Andrzej Cichocki, Rafal 7dunek, Anh Huy Phan, and Shun-ichi Amari. Nonnegative matrix and tensor factorizations: applications exploratory multi-way data analysis and blind source separation. 2009.
Hsiang-Fu Yu, Nikhil Rao, and Inderjit Dhillon. Temporal regularized matrix factorization for high-dimensional time series prediction. In NIPS, pages 847 855, 2016.
Qingquan Song, Xiao Huang, Hancheng Ge, James Caverlee, and Xia Hu. Multi-Aspect streaming tensor completion. In KDD, 2017.
Mehrnaz Najafi, Lifang He, and S Yu Philip. Outlier-Robust Multi-Aspect streaming tensor completion and factorization. In ISCAI, 2019.
Bryan Hooi, Kijung Shin. Shenghua Liu, and Christos Faloutsos. Smf: Drift- aware matrix factorization with seasonal patterns. In SDM, 2019.
Daniel Dunlavy, Tamara Kolda, and Evrim Acar. Temporal link prediction using matrix and tensor factorizations. ACM Transactions on Knowledge Discovery from Data 522)-12,, 2011.
Yongjie Cai, Hanghang Tong, Wei Fan, Ping Ji, and Qing Hc. Facets: Fast comprehensive mining of coevolving high-order time series. In KDD, 2015.
Joel Janek Dabrowski, Ashfaqur Rahman, Andrew George, Stuart Arool, and John McCulloch. State space models forecasting water quality variables: an application aquaculture prawn farming. KDD, 2018.
Yasuko Matsubara and Yasushi Sakurai. Regime shifts in streams: Real-time forecasting of co-evolving time sequences. KDD, 2016.
Xiuwen Yi, Yu Zheng, Junbo Zhang, and Tianrui Li. St-mvl: filling missing values in geo-sensory time series data. In IJAAI, 2016.
Alireza Abedin. S Hamid Rezatofighi, Qinfeng Shi, and Damith C Ranasinghe. Sparsesense: human activity recognition from highly sparse sensor data-streams using set-based neural networks. In IJCAI, 2019.
10

---

Gianluigi Mongillo and Sophie Deneve. Online learning with hidden markov models. Neural computation. 2008.
George Montanez, Saeed Amizadeh, and Nikolay Laptev. Inertial hidden markov models: Modeling change in multivariate time series. In AAAI, 2015.
Emma Pierson, Tim Althoff, and Jure Leskovec. Modeling individual cyclic variation in human behavior. WWW, 2018.
Koki Kawahata, Yasuko Matsubara, and Yasushi Sakurai. Automatic sequential pattern mining in data streams. In CIKM, pages 1733-1742, 2019.
Qingsong Wen, Jingkun Gao, Xiaomin Song, Liang Sun, Huan Xu, and Shenghuo Zhu. Robuststl: A robust seasonal-trend decomposition algorithm for long time series. In AAAI, 2019.
Georg Krempl, Indre Zliobaite, and Dariusz al. Brzezinsski. Open challenges for data stream mining research. SIGKDD explorations newsletter, 2014.
Grünwald and Abhijit Grunwald. minimum description length principle. MIT press, 2007.
Towards compressing Web graphs. In Data Compression Conference, pages 203-212 2001.
Yangyang Xu and Wotao Yin. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal imaging sciences, 6(3): 1758-1789, 2013.


Reviews:
[{"review_id": "sO0COf0ZhLt", "reviewer": "Reviewer_ZNwm", "summary": "The authors develop a new online tensor factorization method for real-time forecasting. The propose approach is designed for dealing with seasonality patterns and automatically switch between different regimes. The authors have shown this method achieves better accuracy compared to existing methods in forecasting taxi/bike rides and infections. The method has shown to be scalable in terms of its memory and test costs. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think this is a well-organized paper and the content is solid. I just have a few comments\n1. The seasonality patterns are important for many real-world applications, especially in climate and environment modeling. It would be better if the authors could discuss how easy this proposed algorithm can be generally applied to other applications. \n2. The proposed method is shown to outperform several MF-based baselines. I am wondering if the authors can also compare it with deep learning-based algorithms. \n3. In many real-world scenarios, we may have access to when the regime shift occurs (e.g., based on seasonality, human interventions, or other separate analysis). Would the proposed method be able to leverage such information? Also, if we have already known such time partitions, would the proposed method outperform other algorithms, e.g., domain-adaptation?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have proposed a general matrix factorization method that can automatically identify and switch between different regimes. This is an important property for many time series data sets. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "PO2cgPW03DZ", "reviewer": "Reviewer_CeEZ", "summary": "The work aims to solve the problem of forecasting for incomplete highly-dynamic time-series data with evolving seasonal patterns (regimes). It uses clever techniques to detect whether seasonal shift occurred in new data and updates the model with the corresponding new regime if necessary. Model training is performed in an online fashion over a data stream and is based on an incremental matrix factorization with adaptive selection of the most appropriate regime. It utilizes minimum description length principle for the task. The authors provide a straightforward learning scheme and demonstrate advantages of the proposed approach on several realistic datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Originality*:  \nThe authors make a good work on positioning their approach among other works and describing the essential differences. The idea of adaptive regimes update/selection is both interesting and novel. The way the task of regime selection is solved with the MDL principle seems to be very appropriate. \n\n*Quality*:  \nThe proposed approach is clearly described and the all necessary part for its (re)implementation seem to be in place. Both time and space complexities are provided. The scalability analysis performed by the authors is convincing. However, there are a few issues.\n\nSection 3.2, equation between line 135 and 135: the formulation is based on the number of non-zero elements, which, I believe, implicitly assumes sparse matrices/tensors (with non-negative elements). However, eq. (4) seems to be free of such assumptions. Isn't there a contradiction? If there are additional assumptions on relaxation of any constraints, it would be good to have them explicitly described. Otherwise, the choice of a distribution should be different.\n\nSection 5.1, line 232: I'm not convinced that fixing the same number of components ensures fair comparison. Different methods are likely to require different values of k for achieving the best quality. If there are certain memory constraints, the number of components must be selected w.r.t. the space complexity of each method. If there are any technical limitations for this, then at least he trendline for different k should be demonstrated.\n\n*Clarity*:  \nSection 2.1 is named *Matrix Factorization*, but talks a lot about tensor factorization as well, which add to the impression of text inconsistency. The authors mix together these terms.\nMoreover, the term SVD is used quite broadly in the text (e.g., line 62). However, it is related to a very specific matrix decomposition method. The authors are probably influenced by the recommender systems literature, with many matrix factorization techniques carrying SVD in their names (e.g., FunkSVD, SVD++, AsySVD, etc.). I'd argue against such terminology as, in general, matrix factorization methods do not provide the same set of algebraic properties as in the case of SVD.\n\nIn Section 2.2, line 80, what does the term *non-linear dynamical system* refer to? It is not clear, why this term is used to contrast other approaches against the proposed one. I couldn't find any clarification on that further in the text.\n\nIn Section 3, Table 2 is not very helpful and creates a lot of whitespace. It is also excessive. The first two rows are describing the same object X(t). It would be probably better to just introduce proper notation directly in the text.\n\n*Significance*:  \nThe proposed approach open many perspective for further improvements and modifications. Given its relative simplicity, it may become a source for fruitful future research.\n\n*Minor issues*:  \n- line 98: \"and r evolves\" -> \"as r evolves\" ? The notation with r = r + 1 is also a bit cumbersome.\n- line 51: The link to Dropbox should be explicit, e.g., via footnote.\n- line 35: unless we talk about very special cases, they almost never converge to optimal parameters and are likely to find only a local optimum. I'd propose to rephrase the sentence. Probably, it's just enough to leave the second part saying about the lower accuracy.\n- line 137: compress -> compresses\n- line 134: provide -> provided", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe that the work doesn't possess any components that may directly lead to negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "C1RXfHsfFK", "reviewer": "Reviewer_gthx", "summary": "This paper aims to solve the problem of forecasting future events given a data stream of events. In order to achieve this, the authors propose a method called Shifting Seasonal Matrix Factorization, which can detect the regime shifts in seasonal patterns, and work in online settings. The authors claimed that, the advantages of the proposed method over previous methods are its capability to dealing with sparse data, regime shifts, seasonal patterns, and drifting components. \n\nThe authors conduct experiments on three datasets, NYC-YT, NYC-CB and DISEASE. All the methods are compared in their capability of predicting the events. The authors also show a case study in NYC to show the results of detected events.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The authors are working on an interesting problem. Considering data sparsity, seasonality and drifting is an interesting and important problem in the matrix factorization problem. \n2. The description of the method is clear and easy to follow. Readers can easily understand the algorithm through the descriptions in Section 3 and 4.\n3. The source code is provided, which can be used for replicating the results.\n\nWeakness:\n1. The compared methods are not comprehensive enough and out-of-dated. The authors have mentioned several more advanced baselines in the related work section, e.g., [Takahashi et al., 2017], [Song et al., 2017], [Najafi et al., 2019]. It is not clear why these methods are not compared. In addition, the investigated problem is also highly related to time series prediction. It is not clear why these methods are not compared.\n\n2. The illustration of the case study is not straightforward. For the maps, the authors may consider zooming in and showing more cases. The current examples can only show the changes around JFK area. The authors may also adjust the axis of the time series to better illustrate the change in volume.\n\n3. The authors claim the capability of dealing with data sparsity. Hence, it is preferred if some experiments can be conducted on dealing with different sparse levels.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No separate Limitations and Societal Impact part is provided.\n\nThe authors may consider how these event predictions can help with dealing with traffic congestion, reducing the time that people need to get a taxi, or pandemic intervention. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6WpwGlK7FT", "reviewer": "Reviewer_Fqt5", "summary": "This paper studies online tensor factorization for real-time event forecasting with seasonality. The key to solve the event forecasting problem here is to detect the seasonal pattern shift and adapt to the shift for an accurate  event forecasting. The closest related work is SMF [Hooi et al., 2019], which is an online forecasting model based on matrix factorization and taking as well seasonal patterns into account. SMF differs from the proposed SSMF by considering only a single seasonal factor, whereas SSMF model seasonal shifts (regimes) individually.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The designed regime selection and extraction mechanism enables the prediction model to have stronger adaptability to the seasonal shifts. The experimental results show that the proposed SSMF model outperforms all baselines. An interesting demonstration example is also provided to demonstrate the capability of SSMF on automatically detecting regime shifts caused by a pandemic.   In general, this work is a valuable contribution to the field of event forecasting. \n\nAuthors are suggested to carefully check the writing errors: “how well a given model compress ” and “a x” and so on.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies forecasting of seasonally varying time series using matrix factorisation of a shifting tensor stream. The proposed algorithm, SSMF, makes forecasts by identifying the current regime and applying the corresponding sub-model. SSMF is analysed with respect to time and memory complexity per time point. The approach is evaluated with respect to scalability and real-world effectiveness in a series of empirical experiments. 

The reviwers appreciated the novelty of the formulation and the importance of the problem. They deemed the paper well written and the results sound. Some concerns were raised regarding the clarity of the paper which were addressed in the author response. Finally, two reviewers asked for comparisons with additional baselines, but I understand the choice to focus on matrix factorisation methods in this setting. Overall, most of the reviewers were in favour of accepting the paper and no major issues remained after the discussion phase.
Decision: Accept (Poster)