Neural Network based Continuous Conditional Random Field for Fine-grained Crime Prediction

1 Introduction

Works on smart city applications related to mobile computing [Wang et al., 2017; Liu et al., 2019; Yu et al., 2015], social economics [Yu et al., 2016; Liu et al., 2016; Fu et al., 2014] and public safety [Yu et al., 2018; Yi et al., 2018] have inspired the implementation of advanced technologies in crime prevention [Wang et al., 2013; Du et al., 2016]. Specifically, the consideration of spatial correlation among different regions has been proved effective, where [Wang et al., 2016] studied the taxi trajectory-based region relationship and [Zhao and Tang, 2017] modeled a distance-based region similarity for spatial-temporal crime prediction. However, the complexity of different type of spatial correlation between regions would eventually make the fine-grained crime prediction a difficult problem.

As discussed in [Qin et al., 2009], CCRF is a powerful model that is typically designed to model effects of interactions among instances. And we could leverage this advantage in modeling region relationship for crime prediction by regarding each region in a city as an instance. However, traditional CCRF would face problems like complex gradient derivation and capacity for large-scale dataset when pairwise interactions across instances are all considered [Ristovski et al., 2013]. To solve these problems, we take advantages from back-propagation algorithm in model training by introducing neural network components into CCRF model. Specifically, mean-field theory [Koller and Friedman, 2009] has proved that the inference process of CCRF model could be transferred into an iterative procedure, and we further reformulate it into neural network layers and propose a Neural Network based CCRF model (NN-CCRF) in our work.

Inspired by recent works [Zheng et al., 2015; Xu et al., 2017] on incorporating CRF with neural network for discrete labeling problems, we proceed to alleviate the limit of integrating CCRF with neural network for structured regression problems. In details, traditional CCRF model consists of two parts, the unary potential and the pairwise potential. Commonly, unary potential models relationship between inputs and outputs of each instance, and pairwise potential constraints outputs of each instance according to a predefined correlation matrix calculated by some kernel functions (e.g., Gaussian kernel, RBF kernel). Existing works only transform pairwise potential into neural network framework, and adopt predefined kernel functions to calculate the correlation matrix for pairwise interaction modeling. In our work, the proposed NN-CCRF model not only formulates pairwise potential into neural network, but also reformulates the unary potential into a Long Short-Term Memory (LSTM) neural network. Furthermore, we propose to learn the correlation matrix between instances using Stacked Denoising AutoEncoder (SDAE) rather than predefined kernel functions, which is more effective to understand the spatial correlation between regions in a data-driven manner. And our work mainly makes the following contributions:

• We propose a Neural Network based Continuous Conditional Random Field (NN-CCRF) model for fine-grained crime prediction, which applies Long Short-Term Memory (LSTM) as the unary potential and leverages Stacked Denoising AutoEncoder (SDAE) to learn spatial correlations across regions.

• We formulate the inference process of NN-CCRF model into a sequential neural network, which helps us to train the whole model in an end-to-end manner leveraging the advantages of back-propagation algorithm.
• We conduct experiments on two real-world crime records collected from Chicago and New York respectively. Considering different types of criminal incidences and disjointed grids in the city as fine-grained regions, our NN-CCRF model outperforms the state-ofthe-art approaches with respect to crime prediction and ranking accuracy.

By achieving the above contributions, our work is of great importance for researchers to understand the mechanism of fusing/transforming traditional CCRF model into neural networks for crime prediction.

2 NN-CCRFModel for Crime Prediction

2.1 ProblemFormulation

In our work, we propose to learn a neural network based nonlinear mapping model M : I → O from the input historical crime number I to the output future crime number O. More formally, let Q = {(Hi,Fi)}qi=1 be a training set of q pairs, where Hi ∈ I represents the historical crime numbers and Fi ∈ O donates the corresponding future crime numbers. To deal with fine-grained crime prediction, we divide city landscape into many small regions. Therefore, Hi is a N × T matrix and Fi forms as a N × 1 vector, where N donates the number of disjointed regions in a city and T represents the length of historical time steps (e.g., T days, weeks, or months). That is, our model aims to predict future crime numbers leveraging historical T time steps of data records. Further, considering a N ×N correlation matrix that can potential influence the crime distribution across all regions, our model is also required to capture spatial relationship for crime prediction.

2.2 Neural Network Based CCRFModel

The proposed Neural Network based Continuous Conditional Random Field (NN-CCRF) model is illustrated in Figure 1, which takes advantages from both CCRF model and NN algorithms. Specifically, we demonstrate a conventional CCRF model in the middle, where each gray node tagged with xi represents the historical crime numbers with T time steps and white node in yi donates the corresponding future crime numbers of i-th region. The unary feature function and correlation matrix learning components are proposed based on neural network algorithms to solve CCRF model, and we define our NN-CCRF model as:

where ψu(y, x, h∗ ) is the unary potential function, and we adopt LSTM [Hochreiter and Schmidhuber, 1997; Gers et al., 1999] with hidden states h∗ to represent the mapping from input x to output y as follows:

where R(x, h∗ ) is the preliminary estimations on y without considering the pairwise spatial correlations, σ(·) is the Sigmod function, and W∗ and U∗ are weight matrices, and b∗ donate the bias vectors within LSTM components that are specified as follows in iteratively updating h∗t :

Besides, the pairwise potential function provides a spatialdependent smoothing term that encourage correlated regions to have similar crime numbers as defined:

where K∗i,j represents the spatial-dependent correlation between yi and yj, which constraints and smooths the preliminary estimations (e.g., R(xi, h∗ ) and R(xj, h∗ ) ) to have better overall results. And one critical problem is how to deduce K∗i,j for each pair of yi and yj . In our work, we leverage a modified SADE [Vincent et al., 2010] framework to learn the spatial correlation matrix K∗ used in pairwise potential function.

Specifically, SDAE is a feedforward neural network that matches the corrupted input and output (ground-truth) by encoding and decoding raw input data in a sequential manner. In our work, suppose we have corrupted input ˆy (inferred by unary potential function) and ground-truth y, SDAE first encodes ˆy into image z and then decodes z to produce y′ as predictions on y as follows:

and the objective function of conventional SDAE is shown as:

where W donate the weight matrices mapping ˆy to y, which can be regarded that W achieves the goal of measuring correlation between yi and yj. And if we adopt each encoding or decoding layer with a same weight matrix, which indicates that our modified SDAE would have n identical layers, we will eventually learn the spatial correlation matrix K∗ similarly by minimizing the following objective function:

where σn(K∗R(x, h∗ )) is the n times encode-decode results of unary predictions in replace of y′ according to n identical layers of modified SDAE, and K∗ is exactly identical to W used in conventional SDAE, and we just replace it in each layer. Finally, our proposed NN-CCRF model manages to maximize the following function according to aforementioned LSTM and SDAE components:

In general, solving such a probability density function that contains neural network component requires a lot mathematical derivation, even there is only a simple one layer neural network as discussed in [Baltruˇsaitis et al., 2014], not to mention that in our work we will consider a LSTM model with many layers and a SDAE. And the main contribution of our work is to reformulate this function into a neural network framework and learn the parameters in an end-to-end manner, instead of manually deducing the gradients of every parameters, which reduces a lot gradient derivation as well as mathematical analysis.

2.3 End-to-EndModel Inferencing

To avoid complicated gradient derivation as discussed in [Ristovski et al., 2013; Qin et al., 2009] for learning CRF models, CRFasRNN [Zheng et al., 2015] is proposed to transfer part of CRF into neural network for fast learning in an end-toend training manner. However, CRFasRNN is limited in only transforming pairwise potential in a RNN manner with a predefined kernel function for inferring pairwise correlation matrix. In our work, we not only reformulate unary and pairwise potential into neural networks, but also simultaneously learn the pairwise correlation matrix instead of adopting a predefined kernel function.

Directly solving the probability dense function in Equation (8) is impractical and complex. We turn to apply meanfield theory [Koller and Friedman, 2009] to approximate this distribution P(y|x). The objective of mean-field inference is to approximate distribution P (y|x) with distribution Q(y|x) that can be expressed as a product of independent marginals Q(y|x) = ∏Ni=1 Qi(yi|x), where N represents the total number of regions in our work. To achieve this, we have to minimizes the Kullback-Leibler (KL) divergence between these two distributions P and Q:

Algorithm 1 Mean-field inference for CCRF

1: for i in N do

2:

y∗

i ←R(xi|h∗ )

• 3: end for

4: for i in Iter do

5:

6:

ˆ

y∗

i ← ∑i̸=j K∗i,j y∗

y∗

j

▷ Unary estimation

▷ Pairwise interaction

y∗

i ←R(xi|h∗ ) + ˆ

7: end for i ▷ Adding unary estimation

where h∗ and K∗ donate the parameters in our model. Following derivations discussed in [Zheng et al., 2015; Kr¨ahenb¨uhl and Koltun, 2011], we are able to solve above function and obtain the following compact update functions for model inference:

where y∗ i is the estimated crime number for i-th region. And the goal of mean-field approximation for regression problem is to iteratively update each y∗ i according to Equation (10) to minimize the mean absolute error between estimated y∗ i and ground truth yi. Specifically, the mean-field approximation inference algorithm is illustrated in Algorithm 1.

There are two main stages during the whole mean-field inference according to Algorithm 1. To begin with, the algorithm first gives estimations on each region using unary feature function. After that, the algorithm passes the estimated values across all regions considering their pairwise interactions. The final estimation of each region is the combination of unary estimation and pairwise interaction. To learn parameters in unary feature function and the corresponding correlation matrix K∗ , we transform the mean-field inference into a sequential neural network framework as illustrated in Figure 2, in which there are two distinct neural networks include a LSTM block for unary potential and SDAE block for learning correlation matrix used in pairwise potential.

In specific, the LSTM block is used in replacement of unary potential, which aims to learn relationship between input features X and output Y and we consider three layers in LSTM in our work. Besides, since there are totally N regions, the model has to apply a N × N pairwise correlation matrix to constraint the values on each yi and yj, and we leverage SDAE to learn such N × N matrix which is used in pairwise potential. Particularly, we notice that the correlation K∗ i,j remains invariant when iteratively updating Y ∗ u , therefore, in our work, each layer in SDAE should be the identically same and forms as a N × N matrix to keep the consistency to Algorithm 1. Further, the number of SDAE layers should be identical to the number of iterations in stage two of meanfield inference (the pairwise interaction phase). Hence, by changing the number of SDAE layers, we could control the iteration numbers for mean-field inference thus influencing the degree of applying the pairwise interaction in our model. Besides, in order to balance the importance of unary and pairwise estimations, we add a linear combination in the end of the procedure. Since we apply neural networks in mean-field inference for CCRF, we are able to learn the model's parameters in an end-to-end manner.

Algorithm 2 gives a detailed procedure of the end-to-end model training for our NN-CCRF according to the proposed neural network based mean-field inference. Specifically, the hyper-parameter η, λ, N, and epoch represent the number of hidden states in LSTM block, the number of layers in SDAE block, the number of regions, and the number of iterations for training respectively. The whole procedure could be divided into two steps, line 3 to line 11 contain the procedure of initialing a NN-CCRF model according to neural network based mean-field inference, and line 12 to line 19 are the end-to-end training procedure of NN-CCRF model. Without calculating any parameters' gradients and considering mathematical constraints, this end-to-end parameter learning algorithm is simple but efficient. We implement this algorithm using a popular deep learning toolkit Pytorch [Chollet, 2017].

3 Experiments

3.1 Data Preprocessing

We totally collect 1,072,208 crime records in Chicago city from Jan. 1 2013 to Dec. 31 2015, and 1,417,083 in New York City from Jan.1 2015 to Dec. 31 2016. Specifically, each crime record is attached with timestamp, location, and crime type information. In order to predict a fine-grained crime number across the city, we first divide the whole city landscape into N disjointed regions, and each region is a 1km×1km grid resulting in 35 (7 × 5) and 63 (7 × 9) grids for Chicago and New York respectively. Then, we select one day as the minimum time step, and aggregate the crime incidence into different regions in different time steps. Knowing that it is also acceptable to select different length (e.g., 500m, 200m) for regions and different time step (e.g., week, month).

Noticing that data sparsity could become an issue in our work for predicting specific crime types, we manage to aggregate similar crime types into classes (crime against person or property) to solve such data sparsity problem. For example, in Chicago dataset, the ratio of non-zeros counts is 0.07, 0.16, 0.04, 0.4 and 0.05 for crime types assault, battery, robbery, theft, and burglary respectively, while that becomes 0.24 and 0.43 for crime against person and property after we aggregate them.

Algorithm 2 End-to-End model training for NN-CCRF

1: Input: hyper-parameters η, λ, N, epoch, and training set Q = {(Hi, Fi)}qi=1 2: Output: NN-CCRF modelM 3: M← nn.Sequential() ▷ create a NN-CCRF 4: lstm←nn.LSTM(η) ▷ create a LSTM block 5: sdae ←nn.Sequential() ▷ create a SDAE block 6: kernel ←nn.Linear(N,N) ▷ create a SDAE layer 7: for i in λ do 8: sdae.append(kernel) ▷ fill in SDAE block 9: end for 10: linear ←nn.Linear(2, 1) ▷ create a linear layer 11: M.append([lstm, sdae, linear]) ▷ fill in NN-CCRF 12: for i in epoch do 13: F ∗ ←M.forward(H) 14: loss ← MSELoss(F ∗ , F) 15: if loss is minimized then 16: break 17: end if 18: loss.backward() 19: end for 20: returnM

3.2 Experiment Setup

In our work, we do not only evaluate the prediction precision, but also try to measure the ranking performance. Hence, we apply the following two metrics. The averaged Root Mean Square Error (RMSE):

and the averaged Hitting Rate@K (HR@K):

where N is the number of regions, t is the number of testing days, such that t = 5 represents we totally conduct experiments on distinct 5 days. And list∗ and list are the ordered region sequence according to Y ∗ and Y respectively, I(·) donates a binary function which outputs 1 when the inputs are identical otherwise 0. Specifically, smaller RMSE represents better performance on prediction precision, and higher HR@K values indicate better performance the model could rank all regions in the same order identical to the real ranking list. We list the following methods for comparison in our work in details.

• History: This method is the baseline method in our work, which simply regards crime numbers in time tk-1 as the predicted future crimes in time tk.
• LR[Montgomery et al., 2012]: Linear Regression model is applied to the whole dataset merged from all regions, and it assumes that future crime numbers are linearly related to historical crime numbers.

• LSTM[Gers et al., 1999]: Long Short-Term Memory is one type of Recurrent Neural Network (RNN) that is widely used in time-series modeling and prediction. It introduces hidden states to capture the dynamic of time-series and usually provide reasonable results. In our work, we build a three layers LSTM with predefined hidden state η with H dimensions.
• CRFasRNN[Zheng et al., 2015]: This model is pro-
• posed for classification tasks, and we reformulate its object function to suit for regression problem. CRFasRNN only transform pairwise updating into RNN framework, and still adopts predefined kernel functions to calculate the correlation matrix between regions. Here we adopt two kernels exp(- ||pi-pj||2 2θ2α ) and exp(- ||fi-fj ||2 θ2β ), where pi and pj are the location of ith and j-th region, fi and fj donate the corresponding Point-Of-Interest (POI) feature vector of these regions.
• TCP[Zhao and Tang, 2017]: Temporal-spatial Correlation for Crime Prediction is a multi-task learning framework that considers both parametric temporal and spatial constraints in crime prediction. Its spatial correlation is predefined using power law exponential function that Ki,j = d-φ i,j , where di,j is the distance between i-th and j-th region, φ is a predefined regularization parameter controlling the degree of spatial correlation.
• NN-CCRF: Our proposed Neural Network based Continuous Conditional Random Field model regards traditional CCRF model as sequential neural network, which applies LSTM and SDAE in unary feature function and pairwise interaction learning. Using mean-field inference, the model is trained in an end-to-end manner. And the correlation matrix K∗ is simultaneously learned from SDAE instead of predefined using some kernel functions.

3.3 Prediction Performance

We test prediction accuracy on different subsets from our collected data, including CHI{13-15} and NY{15,16} representing dataset from different years of Chicago (e.g., CHI13 is the dataset from year 2013 of Chicago) and New York respectively. The detailed experimental results from our proposed NN-CCRF model and other models are demonstrated in Table 1.

Before further analysis on model performances, we observe that as a simple inference model, History based method outperforms LR with respect to crime against property, which indicates that only using yesterday's crime number would be more effective than combining last few days crime numbers for property criminal prediction. While for predicting crime against person, LR outperforms History and History performs the worst as expected. Among all compared approaches, our proposed NN-CCRF model performs the best on all datasets and crime types. Specifically, LR and LSTM models mainly focus on temporal correlations alone for crime prediction, while CRFasRNN, TCP and NN-CCRF additionally take spatial correlation across regions into consideration.

Comparing to LR and LSTM that only take temporal factor into account, CRFasRNN and TCP are more likely to achieve better performance due to the consideration of spatial correlation between regions. However, there are still negative effects, such as results in CHI15 and NY15,16 for crime against person or property where they perform worse than LR or LSTM, one possible reason is that the spatial correlation considered in these two methods are all predefined, which may not always be suitable for different situations. Different from CRFasRNN and TCP, our proposed NN-CCRF model applies SDAE to learn the pairwise spatial correlation in a data-driven manner, which is more likely to capture the dynamics of spatial correlation under various situations. Hence providing better and more robust results.

We further analysis the running time across different models as shown in Figure 3. Our proposed NN-CCRF model costs reasonable running time comparing to other models. Specifically, our model costs equally comparing with LSTM and a little longer than TCP and CRFasRNN models. Both neural network based models, including NN-CCRF and LSTM, grow linearly but faster than other two models when increasing the training data size.

3.4 Ranking Performance

Apart from evaluating the prediction accuracy, we also conduct experiments on each subset to judge if the model could rank the most "dangerous" regions as demonstrated in Figure 4 and Figure 5. Specifically, each figure contains the ranking performance for two different crime types (person and property), and a higher value indicates better performance. According to the results, we observe that the performance of comparison models (e.g., LSTM, TCP, or CRFasRNN) fluctuates a lot under different situations, for example, LSTM performs the fourth place when evaluating on crime against person from New York dataset as shown in Figure 4(a), while it performs the second place as shown in Figure 4(b) and becomes the worst when testing on Chicago dataset as illustrated in Figure 5. Similarly, spatial-based models with predefined kernel functions like TCP and CRFasRNN also perform differently under different situations, which indicating that a static spatial correlation is insufficient for various conditions. However, our data-driven based NN-CCRF model could learn dynamic spatial correlations through SDAE component under different situations, achieving more robust performance in all conditions. Noticing that TCP performs better than ours when testing on crime against person from New York dataset with Hitting Rate at 10 as shown in Figure 4(a).

3.5 Hyper-parameters Effects

We test two major hyper-parameters (η for LSTM and λ for SDAE) as illustrated in Table 2 and 3, and the results are averaged from two crime types. We discover that the parameter setting for best prediction and ranking performance are not consistent. For example, our model achieves its best performance when η = 32 and λ = 4 for prediction with Chicago dataset, while that is η = 128 and λ = 8 for its best ranking performance. Besides, we discover that λ impacts more on model's performance when η is small, showing that spatial correlation plays an important role when temporal influence is weak, while its influence vanishes when η grows larger. In our work, considering the trade-off between accuracy and computational complexity, we take η = 32 and λ = 4 for training model using Chicago dataset, and that is η = 64 and λ = 4 for New York dataset.

4 Conclusion

In this work, we proposed to exploit the effectiveness of formulating conventional CCRF model into neural network framework for spatial correlation learning in fine-grained crime prediction. Specifically, we first reformulated the unary potential of CCRF into LSTM, and applied SDAE to learn pairwise interaction between instances. After that, we transformed the inference of CCRF model into an iterative process based on mean-field approximation theory. By achieving these, a Neural Network based CCRF (NN-CCRF) model was proposed, which is able to deal with large-scale and finegrained crime prediction. Specifically, the proposed SDAE component made it much more effective and convenient to capture spatial correlation between disjointed regions, comparing to traditional predefined kernel functions for calculating the correlation matrix. Furthermore, we reformulated the inference process of NN-CCRF model into a sequential neural network, which could help us to train NN-CCRF in an end-to-end manner using back-propagation algorithm. Experiments conducted on two real-world datasets validated the superiority of our model compared to several state-of-the-art approaches with respect to prediction and ranking accuracy.

Acknowledgments

This work was supported in part by the National Science Fund for Distinguished Young Scholars (No. 61725205), the National Key R&D Program of China (No. 2017YFB1002000), and the National Natural Science Foundation of China (No. 61772428, 61773361, U1836206).