While probabilistic models such as Markov random elds can be highly bene cial for spatio-temporal data, they often su er from overtting and have limited use in memory-constrained systems. We present a novel method to compress trained models based on temporal parameter sharing, which reduces redundancies in the parameters.
Our world is constantly changing, and machine learning provides certain insight into these interesting procedures. Capturing states of a process at di erent spatial sites results in spatio-temporal datasets, and creates demand for accordingly tailored and theoretically well-based methods.
Spatio-temporal random eld (STRF) models, an extension of the widely
investigated Markov random eld s (MRFs), allow to further analyze such processes
with undirected graphical models. STRFs have been experimentally used in
trafc routing [
Parameter sharing based on quantization was recently used for hard
parameter tying in MRF training [
Spatio-Temporal Models A MRF represents a process in form of a
multivariate random variable X = (X1; X2; : : : ; Xn), with dependencies between
components being represented via the conditional independence structure (CIS)
G = (V; E). The concept of exponential families [
The STRF approach [
The parameters of any STRF can be subdivided into spatial and temporal parameter groups, if the replica nodes in G share the same state space. The temporal edges are then represented by parameters temp(vi; vj ; t) 2 which describe temporal transitions from t to t+1 between replicas of nodes vi; vj 2 V0. Each parameter spat(vi; vj ; t) 2 of a spatial edge describes a state transition between replicas of vi; vj 2 V0 at time 1 t T . Accordingly each parameter belongs to a set of parameters temp(vi; vj ) or spat(vi; vj ), which describe the same transition at di erent temporal sections of the model. This understanding is exemplary displayed in Figure 1. We call each set spat(vi; vj ) or temp(vi; vj ) a parameter series. We denote the number of di erent parameter series in the model with st = j tempj and ss = j spatj.
Compression of parameter series In most models the parameter series at
di erent spatial sections will probably show analogies and thus redundancies.
As an example, a street network model might represent crossings which behave
similarly over time. We therefore propose to quantize the set of parameter series,
meaning that each series spat(vi; vj ) or temp(vi; vj ) is replaced by a speci ed
centroid ~spat(vi; vj ) or ~temp(vi; vj ). As parameter series are essentially T
or (T 1)-dimensional vectors, vector quantization methods such as k-means
clustering [
The compression rate r determines the number of temporal and spatial cluster centroids ct and cs that need to be found, depending on the number of original series r = sctt++csss . The space savings s can be computed with s = 1 sctt++csss As an example, a model with st = 1024 di erent temporal parameter series and no spatial parameters, which are being replaced by ct = 128 clustered centroids, would be compressed with r = 1024=128 = 8, i.e. a rate of 8:1, 1 (128=1024) = 87:5% of its original memory space could be saved. 0:5
0 0:5
G0: 1 1 c a 2 t t b 3 2 G: f spat(a; c; 1)g f spat(a; c; 2)g
f spat(a; c; 3)g f temp(b; b; 1)g f temp(b; b; 2)g 0:5 f temp(a; a)g
It is important to understand that our approach does not modify the CIS, as compression only a ects the parameters. This allows nodes in the model to behave similarly, but does not enforce them to act totally equal. PSCS drastically decreases memory requirements and thus facilitates the resource-constrained use of STRFs. It also generalizes the model, which might alleviate over tting. 3
Experimental Settings We chose the INSIGHT Dublin city data for our
experiments [
An extensive framework for probabilistic computations with belief
propagation and gradient descent allowed us to work with STRF models1, we slightly
adadapted it to extract the parameter series. Python scripts were run to cluster
the series with scikit-learn's MiniBatchKMeans implementation2 [
We prepared a 5-fold cross validation, i.e. 20% of the full data was used for testing in each split, providing averaged results and standard deviation (SD). As our experiment dataset is fully observed, we arti cially concealed 50% of the test data. The STRF is used to predict the most likely values based on the remaining observations, and comparison with the originally measurements allows us to compute the prediction accuracy. We came up with three realistic scenarios why measurements might be missing: some SCATS sensors break down on single days (A1), only the beginning of the days are recorded (i.e. future prognosis) (A2), or all tra c sensors have random malfunctions (A3). Accordingly we prepared three di erent versions of the test data, and obtain the accuracy values A1-A3. Experimental Results We used PSCS for compressing the models to 80, 60, 40, 20, and 1% of their original size. The quality of the compressed models in terms of the prediction accuracy is shown in Table 1.
First thing to notice is that our future prognosis scenario (A2) has a signi cantly lower accuracy, for which the lack of local information is the most plausible explanation. Predicting data for full break down of some sensors Fig. 2. Placement of tra c sensors. scores a similar accuracy (A1) to predicting randomly missing data (A1).
Probably the local spatial information is more important for predictions then temporally available data.
As expected A1 and A3 decrease with rmer compression (i.e. higher value of r), however the performance only signi cantly drops after a rate of 5:1. In the second scenario (A2) a compression is even able to increase the prediction accuracy, which might indicate that the original model slightly out tted the training data. One can also see that compression increases the robustness of the model, as the SD is decreases with strong compression. Our novel PSCS approach allows to compress spatio-temporal Markov models. The method eliminates parameter redundancies in the STRF, without a ecting the CIS. Our experiments show that even drastically compressed models still perform well and are even able to outperform the original model, while requiring way less memory storage.
PSCS also holds potential for future work, which we want to shortly discuss here. Firstly one could incorporate a-priori knowledge of cluster assignments into the training routine. With adding a regularizing term one could enforce a soft temporal parameter series tying. By only training the centroid values (i.e. parameter sharing instead of regularization) it would also be possible to establish a hard tying of parameter series, which reduces the complexity during training. Acknowledgement This research has been funded by the Federal Ministry of Education and Research of Germany as part of the competence center for machine learning ML2R (01jS18038A).