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, [Equatinn (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),W/ -)).
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": "fU5X0EEpV-", "reviewer": "Reviewer_ppBZ", "summary": "This paper proposes a matrix factorization approach for time-series forecasting when data arrives in streams. The key claimed distinguishing factor from the previous approaches is the ability to account for seasonal and regime changes. This is done by keeping multiple \"seasonal\" diagonal matrices diag(w_i) in the factorization X = U diag(w_i) V^T, and introducing an heuristic based on MDL to decide which w_i to use for each time step and when to introduce a new w_i. Based on 3 datasets, the authors show that this approach outperforms 3 other matrix-factorization-based forecasting methods from the literature. ", "questions": "", "limitations": "", "rating": 4, "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: This paper is heavy-based on the work in:\n- Hooi, B., Shin, K., Liu, S., & Faloutsos, C. (2019, May). Smf: Drift-aware matrix factorization with seasonal patterns. In Proceedings of the 2019 SIAM International Conference on Data Mining (pp. 621-629). Society for Industrial and Applied Mathematics.\nThe methodology is very similar (essentially an extension of it), 2 of the 3 case studies considered are the same, even some of the figures are remarkably similar. Therefore, unfortunately, the novelty is rather low. The proposed approach can essentially be regarded as an extension of the work by Hooi et al. (2019) to include multiple matrices W_i in order to account for regime changes, and introducing an heuristic to determine which to use at given time and when to introduce a new matrix/regime. I recommend the author to make their contributions more clear in the paper and, in particular, the how the proposed approach differs from the work in Hooi et al. (2019).\n\nQuality: The empirical results indeed show that the proposed approach outperforms 3 other approaches based on matrix factorization for time-series forecasting on the 3 case studies considered, however, I have a few concerns regarding the experimental analysis that I think the author should consider:\n- The results are interesting but, at the same time, they are not that surprising. Essentially, 2 of the 3 datasets considered (Taxi demand and bike sharing demand in NYC) contain one massive regime change due to covid. It would be interesting to see whether this is the only regime change that the proposed algorithm is picking up on, and most of the improvements are simply due to a \"lockdown/no lockdown\" mode, or whether the proposed approach is identifying other more interesting regime changes that would less trivial to identify and account for. In other words, a detailed analysis of the regime changes detected is missing for the remaining case studies. \n- Related to the previous point, since this paper focuses on the problem of time series forecasting, simpler traditional forecasting methods should be included for comparison, and in order to understand the scale of the improvements. Additionally, the author should consider simple baselines that, for example, just copy the values of the previous week and use them as the prediction.\n- The authors should provide error bars (or ideally a statistical significance analysis) for the results in Figure 2, as done in Hooi et al. (2019). Additionally, the authors should consider providing these results also in a table format, perhaps in appendix. \n\nClarity: Overall, the paper is clear, but it contains several typos and grammatical mistakes that should be address. I encourage the authors to perform a careful revision, as well as to consider changing the titles of sections \"3 Proposed Model\" and \"4 Proposed Algorithm\" to something more concrete and informative, and Section \"4.3 Theoretical Analysis\" to \"Complexity Analysis\", since the former is misleading. \n\nSignificance: Time-series forecasting is a topic with a very large audience, but, since the contribution is small in terms of methodology, I'm not sure whether this paper advances the state of the art in significant way. My previously mentioned concerns regarding the experimental analysis further aggravate this issue. I would encourage the authors to work on improving the experimental analysis in order to increase the significance of their work. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, the authors have not addressed the limitations and potential negative societal impact of their work. I would encourage the authors to include a dedicated section in the paper for discussing these.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "IpwRuC-ujxV", "reviewer": "Reviewer_fpwd", "summary": "In this paper, the authors propose a matrix factorization method when the matrices evolve over time. For each matrix at time (t), the authors factorize it as a product of factors as well as a \"seasonality tensor\" that captures specifics about the time series at time (t). The proposed method is online, and can be employed in a streaming fashion. They use an MDL principle to determine whether the seasonality tensor needs to be updated. Experiments on 3 datasets show that the method outperforms baselines. \n\nEdit: R2 pointed out similarities to an existing work that I was unaware of. Given that and the authors not responding, I'm changing my score. ", "questions": "", "limitations": "", "rating": 5, "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 paper is somewhat easy to follow, but there are a few places where it can be improved (mentioned in the comments). Overall, the authors consider a pretty important problem, and propose a principled way to solve it. The experimental results are compelling. There is a section on theory, but that just analyzes the computational and memory complexity, so I'd not really call those theoretical results.\n\nComments:\n- in the definition of W, is s a user defined parameter?\n\n- Problem 2: Why do you want to maintain a factor U, V per time period? What happens if the matrices are always factored into the same U and V, but only W captures the time variability? Presumably this is easier to train since you have fewer parameters to learn. It will be good to know experimentally or via a theoretical argument whether this would be suboptimal. \n\n- Line 129: this statement is not clear. What does error thresholds mean in this context?\n\n- line 143: provide --> provided\n\n- line 154: what does a smooth update mean?\n\n- what is the loss function that leads to the gradient updates in (8) and (9)?\n\n- line 178: is there a reason you want the parameters to be non negative?\n\n- Figure 2 should have error bars. Hard to know if these results are significant.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No\n\nboth limitations and societal impact have not been addressed. \n\nLimitations: what is the reason for having nonnegative factors? is it merely interpretability? some of the baseline methods don't have that constraint. Similarly, does your method require a minimum number of samples observed per time instant? these questions should be answered. \n\nImpact: time series forecasting is a pretty broadly applicable problem, and has the potential for large impact in various important applications. The authors have not considered addressing this and should definitely do so. ", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DIxXSadQuGE", "reviewer": "Reviewer_Mjyk", "summary": "This paper proposes the Shifting Seasonal Matrix Factorization approach, SSMF, to adaptively learn multiple (dynamic) regimes and the model chooses the best regime automatically. The idea of remembering multiple regimes is very novel and can be effective especially if the temporal patterns change such as pattern A -> pattern B -> pattern A. The authors use the taxi case during Covid-19, which is a suitable case to show the effectiveness of their model.  ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "\nIn general, I like the idea proposed in the paper, which is neat and really interesting, while there are still a lot of issues that may help improve the paper:\n\n1) I have to say I am struggling to understand the benefits of the paper's main idea of remembering historical regimes (I prefer using a phrase like 'regime memory' to name the W tensor, which will help to understand the tensor's purpose easily). Apparently, if without remembering the historical regimes (and selecting the best of them), this paper has no advantage compared to SMF (Table 1). Actually, until I read the case study of Covid-19 NYC Taxi, I have not understood the purpose (This case study is really nice). I strongly suggest that the authors use the Covid-19 taxi as a motivation example to put at the beginning of the paper, so as to illustrate the necessity of using regime memory.\n\n2) While the authors only increase the regime memory size g if the new regime performs better than all the previous ones, this still will always increase the regime memory. Hence, if the algorithm runs for a long time, g would still be large (I also would like to see the increase of g in the experiments). I suggest that authors discuss when certain regimes can be deleted from the memory W (e.g., some regimes not used for a very long time).\n\n3) I understand that matrix factorization is the focus of the paper. However, deep learning (neural networks)  has been a very popular method for traffic prediction today. The authors should discuss the advantage/disadvantages of their proposed methods with deep learning-based methods in traffic forecasting. Besides, adding some representative deep learning methods as benchmark methods in the experiments is also necessary. I understand that SSMF has certain advantages that can deal with sparse data and better explanation in the regime, but the authors should explicitly discuss these issues in the paper.\n\n4) Some experiment settings are not clear. What is the data sparsity in the experiments? If the data is not sparse, I think the authors should also add the experiments to add sparsity (e.g., randomly deleting some records from the historical records) to check the effectiveness of their methods in the sparse setting.\n\n5) If real traffic prediction problems, context factors (weather, hour of day) play important roles. However, how to add these context factors into the current model is unclear.\n\n6) Many typos and notation mistakes in the paper. For example, W^(i) in Eq. (6) should be W^(1)? W^(i)_ts in Eq. (13) should be W^(z)_ts? There are also many grammar errors. The authors please carefully proofread the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper should add a limitation discussion paragraph.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a matrix factorization approach for time-series forecasting for streaming data. The reviewers identified novelty as a main concern; indeed there is substantial overlap with a paper that has already been published. In addition, there were concerns about the experimental analysis.
Decision: Accept (Poster)