LHRM: A LBS based Heterogeneous Relations Model for User Cold Start Recommendation in Online Travel Platform

Most current recommender systems used the historical behaviour data of user to predict user' preference. However, it is difficult to recommend items to new users accurately. To alleviate this problem, existing user cold start methods either apply deep learning to build a cross-domain recommender system or map user attributes into the space of user behaviour. These methods are more challenging when applied to online travel platform (e.g., Fliggy), because it is hard to find a cross-domain that user has similar behaviour with travel scenarios and the Location Based Services (LBS) information of users have not been paid sufficient attention. In this work, we propose a LBS-based Heterogeneous Relations Model (LHRM) for user cold start recommendation, which utilizes user's LBS information and behaviour information in related domains and user's behaviour information in travel platforms (e.g., Fliggy) to construct the heterogeneous relations between users and items. Moreover, an attention-based multi-layer perceptron is applied to extract latent factors of users and items. Through this way, LHRM has better generalization performance than existing methods. Experimental results on real data from Fliggy's offline log illustrate the effectiveness of LHRM.

forms: (1) new user cold start problem (2) new item cold start problem [7]. In new user cold start problem, a new user has just registered to the system and RS has no behaviour information about the user except some basic attributes [15]. In new item cold start problem, a new item is presently added to the online recommendation platform and RS has no ratings on it [15]. Compared with new item cold start problem, the new user cold start problem is more difficult and has been attracting greater interest [1]. In this paper, we focus on user cold start problem. Existing methods, including cross-domain recommendation algorithms [17,20,6,9,19], Lowrank Linear Auto-Encoder (LLAE) [11] have been proposed and achieved great success for user cold start problem.
User cold start recommendation over online travel platforms (e.g., Fliggy) are more challenging, thus existing methods cannot work well. LLAE [11] can reconstruct user behavior from user attributes, but even for active user, travel is a low-frequency demand and user behaviour is quite sparse. Therefore, the generalization performance of LLAE is limited by the sparse behaviour of users. Cross-domain algorithms try to utilize explicit or implicit feedbacks from multiple auxiliary domains to improve the recommendation performance in the target domain [6]. Unfortunately, it is hard to find a cross-domain that user has similar behaviour with travel scenarios and the LBS information of users have not been paid sufficient attention. Unconditional fuse the user behaviour information from other domains may introduce much noise. More importantly, user's travel intention is strongly related to user' LBS information. The intuition is that, users who are geographical situation closer may have similar travel intention.
To alleviate the user cold start problem in travel scenarios, we propose a LBS based Heterogeneous Relations Model (LHRM) for user cold start recommendation in online travel platform. LHRM firstly constructs heterogeneous relations between users and items and then apply an attention-based multi-layer perceptron to learn the latent factors of users and items. Heterogeneous relations is proposed in [2], which include user-user couplings, item-item couplings, and user-item couplings. It is increasingly recognized that modeling such multiple heterogeneous relations is essential for understanding the non-IID nature and characteristics of RSs [2,3]. In order to relieve the problem of data-sparse, user behaviour information in a specific category of items in related domains is used to learn the embedding representation of user. The background is that, more than 80% of Fliggy users have Taobao platform account 1 , and most of them are cold start users in Fliggy, but they have rich behaviours on Taobao. Then LBS information and user behaviour information in a specific category of items in Taobao domain are concatenated to construct the heterogeneous relations between users. User behaviour information in Fliggy domain is used to construct the heterogeneous relations between items. Meanwhile, user attributes are mapped into the space of user behaviour in Fliggy domain. After obtaining the side information and the embedding representation of user and items, an attention-based multi-layer perceptron is applied to extract higher level features and make the recommendation results more accurately for cold start user in Fliggy.
In summary, the contributions of this paper are multi-fold: -We propose a LBS-based Heterogeneous Relations Model (LHRM) for user cold start recommendation in travel scenarios, which utilize the LBS information and fuses user behaviour information in specific category in Taobao domain to improve the recommendation performance. -A new heterogeneous relations between users and items is proposed in LHRM, which can represent the relationship between users who with similar preference better. -Comprehensive experimental results on real data demonstrate the effectiveness of the proposed LHRM model.
The rest of this paper is organized as follows: Section 2 review the related work. Section 3 describe the proposed model in detail. Section 4 focus on the experimental results about the proposed model, including performance evaluation on real data from Fliggy's offline log. At last, we conclude the paper in Section 5.

Related Work
The main issue of the cold start problem is that, there is no available information can be required for making recommendations [7]. There has been extensive research on cold start problem in recommender systems. In the section, we mainly review the related work about user cold start problem.
Cross domain [6,17,9,8,5,19] recommendation algorithms have attracted much attention in recent years, which utilize explicit or implicit feedbacks from multiple auxiliary domains to improve the recommendation performance in the target domain. [6] proposed a Review and Content based Deep Fusion Model (RC-DFM), which contains four major steps: vectorization of reviews and item contents, generation of latent factors, mapping of user latent factors and crossdomain recommendation. Through this way, the learned user and item latent factors can preserve more semantic information. [8] proposed the collaborative cross networks (CoNet), which can learn complex user-item interaction relationships and enable dual knowledge transfer across domains by introducing cross connections from one base network to another and vice versa. [19] combine an online shopping domain with information from an ad platform, and then apply deep learning to build a cross-domain recommender system based on shared users of these two domains, to alleviate the user cold start problem. Servel recent works model the relationship between user attributes and user behaviour. With the assumption that people with the similar preferences would have the similar consuming behavior, [11] proposed a Zero-Shot Learning (ZSL) method for user cold start recommendation. Low-rank Linear Auto-Encoder (LLAE) consists of two parts, a low-rank encoder maps user behavior into user attributes and a symmetric decoder reconstructs user behavior from user attributes. LLAE takes the efficiency into account, so that it suits large-scale problem.
A non-personalized recommendation algorithm is proposed in [16]. The authos hypothesize that combining distinct non-personalized RSs can be better to conquer the most first-time users than traditional ones. [16] proposed two RSs to balance the recommendations along the profile-oriented dimensions. Max-Coverage and Category-Exploration aims to explore user coverage to diversify the items recommended and conquer more first-time users.

Problem Statement
Most current Recommender Systems (RSs) based on the intuition that users' interests can be inferred from their historical behaviours (such as purchase and click history) or other users with similar preference. However, it is difficult to recommend items to new users accurately. User cold start problem is a longstanding problem in recommender systems. In this work, we define the cold start user as the user who have not any behaviours on Fliggy in the past one month. Specifically, more than 20% of users are cold start users in Fliggy everyday and the optimization task of user cold start is becoming very important in Fliggy. The problem can be summarized as follows: Problem: Given a target domain D t , and a source domain D s , user u is new for D t , but it has interactions in D s , recommend top k items for u in D t .

Notations
In this paper, we use lowercase and uppercase letters to represent vector and matrix, respectively. We denote active users in two domain intersection as the target users {u t }. For every target u t , we denote the basic attributes as x ut = {x 1 , x 2 , x 3 , ..., x k }, the heterogeneous relation of user-user as E ug = {e u1 , e u2 , e u3 , ..., e un ; e ut }, each e un is the representation vector of u n . We denote the items that target users have interacted as the target items {i t }. For every target i t , we denote the basic attributes as .., e im ; e it }, each e im is the representation vector of i m . We use U to denote the target user matrix, and I to denote the target item matrix, Y ∈ {0, 1} |U| * |I| be the relationship matrix between U and I, where Y u,i = 1 means u n clicked i m .

Geohash Algorithm
In order to map user' LBS information (such as latitude and longitude) to a range, we use the Geohash algorithm [18]. Geohash is a public domain geocode system invented in 2008 by Gustavo Niemeyer and G.M. Morton, which encodes a geographic location into a short string of letters and digits (e.g., geo-hash6(31.1932993, 121.4396019) = wtw37q). Length of different Geohash strings represent different area of region, for example, geohash5 means a square area of about 10 square kilometers.

LBS based Heterogeneous Relations Model
It is worth noting that users' interests can be inferred from historical behaviours or other users with similar preference and benefited from heterogeneous relations. Moreover, user's travel intention is strongly related to user' LBS information (such as latitude and longitude), which based on the intuition that users who are geographical situation closer may have similar travel intention. To active this, we propose LBS based Heterogeneous Relations Model (LHRM), in which LBS information is used to construct the heterogeneous relation between users. The framework of LHRM illustrated in Fig.1. LHRM contains two modules: heterogeneous relations construction module and representation learning module.  Heterogeneous relations construction module The detailed process of constructing the heterogeneous relations between users and items is shown in Fig.2. We can see that user's historical behaviours sequence and LBS sequence in Taobao domain are concatenated and input into a embedding layer, which pretrained by skip-gram algorithm [13]. Specifically, items not related to travel are filtered out and user's latitude and longitude information is mapped to a string with the length of 5 by the geohash5 algorithm. After the embedding layer, we adopt average-pooling to generate the corresponding vector representation of user. In order to generate different user groups, we utilize K-means algorithm to cluster users according to their representation vectors. For each user group, any user can be regarded as the target user, and the other users are regarded as the friends of the target user.
User behaviour sequence in Taobao domain ...

Embedding Layer
User embedding  Each item that the target user has interacted in Fliggy domain is regarded as the target item. The whole candidate items set contains two part: items recalled by target item through item-item (i2i) and items interacted by all users in user group. Finally, the items in candidate set are filtered according to the topic of the target item and generate the item group. In this way, all items in item group are more related, and which can be represented by a pre-trained item embedding vector in Fliggy domain.
Representation learning module An attention-based multi-layer perceptron is used to learn the latent factors of users and items. After the process of heterogeneous relations construction, E ug and E ig are generated. Then we adopt an attention layer to focus on the relevant parts of E ug and E ig . The implementation of attention for sequence-to-one networks on E ug is shown in Eq.(1) and Eq. (2): where: W a is the learnable parameters in attention layer, and the output of attention layer is computed as Eq. (3): Similarly, attention layer is implemented on E ig , and the output is a i . The MultiLayer Perceptron (MLP) layer is a feed-forward neural network, which can generalize better to unseen feature combinations through low-dimensional dense embeddings learned for the sparse features [4]. We denote the input of MLP layer as v u and v i , the output of MLP layer as s u and The output of LHRM is the preference score of u t for i t , we denoteŷ as the output of dot layer.ŷ is computed as Eq. (4): y is binary labels with y = 1 or y = 0 indicating whether click or not. The logistic loss of LHRM is shown in Eq. (5): For clarity, we show the key steps of our algorithm in Algorithm 1.

Experiment
In this section, we conduct experiments on Fliggy and Taobao's offline log dataset to evaluate the performance of LHRM and some baseline models.

Algorithm 1 LBS based Heterogeneous Relations Model
Input: User's behaviour sequence in Taobao domain ST , user's LBS sequence in Taobao domain LT , user's behaviour sequence in Fliggy domain SF , user attributes Xu, item attributes Xi Output: Latent factors of users Su, latent factors of items Si 1: ST and LT are used to construct heterogeneous relation between users by K-means, and output Eu g 2: SF is used to construct heterogeneous relation between items, and output Ei g 3: Eu g and Ei g are input into attention layer, and output au, ai 4: the concatenation vector of [au, xu t ] and [ai, xi t ] are input into MLP layer, and output su, si 5: su, si are input into dot layer, and outputŷ 6: update all parameters according to L(y, y) = −ylog( y) − (1 − y)log(1 − y) 7: Cold start: 8:ŷnew = su new · si 9: Recommendation: 10: Computing the similarity score between the new user and all candidate items, and recommend the top-k items

Compared Methods
In the experiments, we compare the following methods.
-Hot: Hot is a non-personalized recommendation algorithm, which recommends items to new users according to the popularity score of item in Fliggy domain.

-HERS: Heterogeneous relations-Embedded Recommender System (HERS)
is proposed in [9], which based on ICAUs to model and interpret the underlying motivation of user-item interactions by considering user-user and item-item influences and can handle the cold start problem effectively. -MaxCov: Max-Coverage (MaxCov) [16] is a non-personalized recommendation algorithm, which aims to explore user coverage to diversify the items recommended and conquer more first-time users. -LHRM: Lbs based heterogeneous relations model proposed in this paper.
Popularity score of items is very important factor in cold start recommendation, therefore, when implementing LHRM and HERS in experiments, we fuse the popularity score of items with the score of LHRM and HERS's output. Then, final preference score of u t for i t calculated in Eq. (6):

Implementation Details
We set the maximum length of user group and item group to 10. The number of cluster center is set to 1000. The dimension of latent factors of user and item is a hyper parameter, we set it to 32, 64, 128 and 256 in the experiments. In order to evaluate the performance of proposed methods, we adopt two evaluation metrics, i.e., Hit Rate (HR@30,@50,@100,@200), Normalized Discounted Cumulative Gain (NDCG@30,@50,@100,@200). HR is a metric of shotting accurately at target items. NDCG is a cumulative measure of ranking quality, which is more sensitive to the relevance of higher ranked items.

Datasets
During our survey, no public datasets for user cold start recommendation in travel scenarios. To evaluate the proposed approach, we collect the offline log data from Fliggy and Taobao domain in the past one month as the dataset. Generally, impression and click sample as positive samples, impression but not click samples as negative samples. All the data have been de-identified, and the algorithm training and application related to cold start do not involve the identification of users, so as to fully protect the privacy of users. The statics of dataset is illustrated in table 1.

Results
We show the experimental results of different models in Table 2. Among all methods, LHRM achieves the best performance in terms of all metrics. Specifically, when the dimension of latent factors of user and item is set to 32, the HR and NDCG are the highest. Table 2 shows the HR and NDCG on target items, and all existing methods did not work well on cold start users. Generally, in practical applications, we not only care whether the recommended items will be clicked, but also whether the recommended items are related to the target items. Therefore, we evaluate the hit rate of different models under different degree of relevance with target items. Experimental results are shown in Fig.3. We can see that, LHRM-32 is very competitive, MaxCov performs best when calculating hit rate according to whether the destination same as the target items.

Conclusion
In this paper, we point out two challenges of user cold start recommendation in travel platform: i) it is hard to find a cross-domain that user has similar behaviour with travel scenarios ii) LBS information of users have not been paid sufficient attention. To address this problem, we propose LBS based heterogeneous relations model. LHRM utilizes user's LBS information and behaviour information in Taobao domain and user's behaviour information in Fliggy domain to construct the heterogeneous relations between users and items. Moreover, an attentionbased multi-layer perceptron is applied to extract latent factors of users and items. Experimental results on real data from Fliggy's offline log illustrate the effectiveness of LHRM.


A Stochastic Max Pooling Strategy for Convolutional Neural Network Trained by Noisy Samples

The deep convolutional neural network (CNN) has made remarkable progress in image classification. However, this network performs poorly and even cannot converge in many actual applications, where the training and test samples contain lots of noises. To solve the problems, this paper puts forward a network training strategy based on stochastic max pooling. Unlike the traditional max pooling, the proposed strategy first ranks all the values in each receptive field, and then selects a random value from the top-n values as the pooling result. Compared with common pooling methods, stochastic max pooling can limit the pooling selection to a larger value that represents the main information of the pooling area which reduces the chance of introducing noises into the network, and enhances the robustness of extracting noisy image features. Experimental results show that the CNN used stochastic max pooling Strategy can converge better than traditional CNN and classified noisy images much more accurately than traditional pooling methods.

Introduction
In recent years, deep learning has become a research hotspot of artificial intelligence (AI). This technology has been successfully applied in various field, such as image classification [1,2,9], object detection [3,7,10,11], and image segmentation [4,5]. One of the most important deep learning models is the deep convolutional neural network (CNN) [6]. With special structural elements (e.g. pooling, convolution and receptive field), the deep CNN enjoys immense popularity in image processing. Many scholars have attempted to further improve the excellent performance of the deep CNN in terms of function and structure.
The functional improvement either modifies or increases network functions, enhancing the network ability to achieve specific functions. For instance, Nair [8] replaced the traditional sigmoid function with rectified linear unit (ReLU) function, leading to better network convergence. Srivastava [13] put forward the dropout function, which greatly suppresses network overfitting than traditional methods. Wen [14] designed and implemented the intermediate loss function, and realized more accurate classification based on sample correlations than the traditional softmax loss function.
The structural improvement aims to express features in a better way through structural adjustment to the network. Currently, many scholars strive to obtain richer feature information by increasing the depth and width of the network. For example, Krizhevsky [6] proposed an eight-layer CNN called the AlexNet, which won the Large Scale Visual Recognition Challenge (ILSVRC) 2012. Simonyan [12]further increased the number of network layers to 19, and achieved 92.7% top-5 test accuracy in ImageNet, 55% higher than that of AlexNet. In ILSVRC 2015, the 152-layer ResNet [5] further improved the top-5 test accuracy to 95.7%.
However, the deep CNN provides no specific solution to problems like noisy images. In actual engineering, both the training and test samples contain lots of noises under the effects of lighting or imaging device. Despite being capable of processing images, the special structure of the CNN cannot eliminate the effects of noises on the network. If the deep CNN is directly applied to feature extraction, it will be inevitable for the extracted features to contain noises.
In the deep CNN, the key to feature extraction is the pooling layer. This layer extracts features for the second time, making them invariant to displacement, scaling and deformation. The most popular pooling method is max pooling, which takes the maximum value in each receptive field. Many experiments have found that this method can easily retain the noise (usually the maximum value) of the original image, and amplify the noise effects. This phenomenon is particularly obvious in max pooling of a highly noisy image. Unable to differentiate between noises and normal signals, max pooling does not apply to processing noisy images.
To solve the above problem, this paper puts forward a deep CNN based on stochastic max pooling. Unlike max pooling, the stochastic max pooling ranks the values in each receptive field and selects one from the top-n values as the pooling result. This approach reduces the chance of taking a noise as the feature. Like dropout structure, the network structure based on stochastic max pooling can be viewed as a set of n sub-models, and thus have a high accuracy.
The rest of the paper is organized as follows. Section 2 reviews recent pooling methods. Section 3 introduces our method of stochastic max pooling. Experiments are discussed and evaluated in Section 4. A summary in Section 5 concludes this paper.

Literature review
In the deep CNN, the pooling layer plays a critical role in feature extraction. In this layer, the convoluted features are further extracted and reduced dimensionally. Meanwhile, their invariance to displacement, scaling and deformation is enhanced.
There are three commonly used pooling methods, including average pooling, max pooling and stochastic pooling [15]. The average pooling outputs the average of all values in each receptive field. This pooling method reflects the overall features of the receptive field.
The max pooling takes the maximum value in the respective field as its result, highlighting the most salient feature of each receptive field. Many experiments have confirmed the superiority of max pooling over average pooling. However, max pooling only considers the value with the strongest response, ignoring all the other values. Thus, the effects of the low-response values on the network are neglected in max pooling.
To solve the problem, Zeiler [15] presented the stochastic pooling on International Conference on Learning Representations (ICLR) 2013. This pooling method randomly selects a value from each receptive field at a certain probability. With such randomness, the network structure based on stochastic pooling is equivalent to a set of multiple sub-models, similar to that of dropout [13]. Each sub-model is a network that outputs a value of the corresponding receptive field. Nevertheless, a stochastic pooling network may treat a small value in the receptive field as the pooling result. Such a small value cannot reflect the typical features of the receptive field. What is worse, the small value could become a noise in feature transmission, and suppress the network performance.
In practical applications, the images often contain a lot of noises. When the image contains a lot of noise, noise pixels may appear in the pooled area, and these pixels are often very large. Therefore, noise may be introduced into the network through maximum pooling, thus reducing the performance of the network. In this case, the stochastic pooling result might be a small value, which is not a good reflection of the essential characteristics of this region. To solve the problem, this paper combines the max pooling and stochastic pooling into a hybrid strategy called the stochastic max pooling. If applied to a noisy image, the proposed strategy can extract the primary features by selecting the value with high response and filtering out the small values, and enhance the stochasticity of the network, turning the network into a set of sub-models. In this way, the network performance can be enhanced despite the noises in the training samples.

Deep CNN
The CNN is a deep learning model that can automatically learn and extract features from data. The model greatly outshines the traditional methods in generalization. It has been successfully applied in the fields of pattern classification, object detection and object recognition. Being a multi-layer supervised learning network, the CNN mainly consists of input layer, hidden layers and output layer. The network structure is optimized through error backpropagation to solve unknown parameters. The hidden layers, including alternating layers of convolution and down-sampling modules, are the cornerstone of the CNN. During the operation, the original image is imported to the CNN via the input layer, subjected to convolution and pooling, and then outputted via the output layer.
In each convolution layer, every neuron in the feature map is connected to a local receptive field on the previous layer, and the local features are extracted through convolution. In general, the convolution operation can be expressed as: where, l is the serial number of the layer; k is the convolutional kernel; M j is a receptive field of the input layer; b is bias.
In each pooling layer, the pooled feature map has the same number of neurons as the inputted feature map, but its size is only 1/n of the former (n is the pooling size). The pooling operation mainly reduces the resolution and feature dimensions of the feature map, while enhancing the network robustness to displacement, scaling and distortion. The pooling operation can be defined as: where down()is the pooling function, β is the weight coefficient.

Deep CNN based on stochastic max pooling
The proposed stochastic max pooling first ranks all the values in each receptive field, and then randomly selects one of the top-n values as the pooling result. This strategy is different from average pooling, max pooling and stochastic pooling. However, it can be viewed as the integration between max pooling and stochastic pooling. To describe our strategy clearly, the first step is to define the three common pooling methods.
The max pooling, which outputs the maximum value in each receptive field, can be defined as: where y max is the pooled maximum value, r is all the values in each receptive field. In the pooling area (i.e. receptive field) of Figure 1, the maximum value in that area is 9, that is, y max = 9.
The average pooling, which takes the average of all the values in each receptive field, can be defined as: where y mean is the result of average pooling. In Figure 1, the average of all the values in the pooling area is 3.1. In this case, y mean = 3.1.
The stochastic pooling selects a value from each receptive field at a certain probability. The probability p i for the value a i at position i in the receptive field can be defined as: Then, the stochastic pooling operation can be defined as: where y stochastic is the result of stochastic pooling. In the proposed strategy, i.e. the stochastic max pooling, the pooling result is selected from the top-n values of each receptive field. Thus, all the values in the receptive field should be ranked to determine the top-n values. Then, a value is randomly taken from the n values. Hence, the stochastic max pooling can be defined as: where random is a function that randomly selects a value; s n is the top-n values in the receptive field. If n=3, then the gray values in Figure 1 are the top-3 values in the receptive field. Then, one of the three values will be selected as the result of stochastic max pooling.

Discussion
The pooling layers are of great significance to the deep CNN. These layers both transmit and reduce the dimensions of features, making the network invariant to displacement, scaling and deformation. The value selection from each receptive field directly bears on the effects of feature extraction and transmission in the pooling layers.
Among the three common pooling methods, the max pooling often outperforms the average pooling, and enjoys greater popularity than the other two methods. In general, the maximum value in a receptive field can represent the features of that field. However, max pooling was found not suitable for two cases.
The first case is that the original image contains a lot of noises. In this case, the maximum value in a receptive field might be noise. Through max pooling, the noise will be mistaken for feature and introduced to the network. As shown in Figure 2, the value of 50 is possibly a noise, and will be selected by max pooling as the result. However, the pixel value represented by 50 is just noise, which obviously does not conform to the principle of feature extraction.
In the second case, there are many values in the receptive field that are close to the maximum value. As shown in Figure 1, the value 9 will be selected by max pooling. However, the other values (e.g. 8.7 and 8.5) are close to 9 and also reflect the features of the field. The slight differences between these values could be magnified through the layer-by-layer transmission and the processing by thousands of neurons in the network, exerting a huge impact on the network performance. In this case, max pooling eliminates the chance for other values to be selected, which might otherwise enhance network performance.
In stochastic pooling, any value in a receptive field has a chance to be selected. Compared to max pooling, stochastic pooling allows a great diversity in pooling result. However, some small values from pooling areas may be introduced to the network, and disturb the feature extraction. As shown in Figure 1, the value 0.1 might be selected as the result of stochastic pooling. This value does not reflect the typical features of the field and will affect network accuracy.
Our strategy of stochastic max pooling overcomes the above defects. Figure 3 shows the process of stochastic maximum pooling method. We can see that Stochastic max pooling can select a representative value from each receptive field and randomize the pooling result. Similar to stochastic pooling, the randomized network can be considered as a set of multiple sub-models, each of which operates based on a unique pooling result. The set of sub-models outperforms any individual sub-model, which is proved by the research of the dropout mechanism. In addition, stochastic max pooling also enjoys a high robustness in processing highly noisy images.

Experiments and results analysis 4.1 Experimental verification of stochastic max pooling
This subsection aims to verify the effectiveness and superiority of the deep CNN based on stochastic max pooling. The deep CNN model was extended from LightNet [1], a versatile, standalone Matlab-based environment for deep learning. The extension only adjusts the parameters of the pooling layers. As shown in Figure 4, the pooling size is 3x3. For comparison, four models were developed, respectively based on max pooling (model A), average pooling (model B), stochastic pooling (model C) and stochastic max pooling (model D).
Two datasets were selected for our experiments, including the Street View House Numbers (SVHN) and CIFAR-10 dataset (Canadian Institute for Advanced Research). The SVHN dataset was divided into a training set of 73,257 images and a test set of 26,032 images. The CIFAR-10 dataset contains 60,000 images in 10 categories. Here, 50,000 images are used for training and 10,000 for test. All the images in the two datasets are of the size 32x32, and not preprocessed.
The four models were applied to the two datasets. The number of top-values n was set to 3 and the number of network trainings to 40. The final results are displayed in Table 1 below. Model A (max pooling) and model B (average pooling) had basically the same accuracies. Model C (stochastic pooling) realized a lower error than models A and B, but the error was higher than that of model D.
The experiment shows that the n value has a great impact on the final results. To find the best n value, a series of experiments were conducted on model D by adjusting the n value from 1 to 9. According to the experimental results in Figure 5, the error gradually increased with the growth in  n value. When n increased to 9, the model acted the same as model C (stochastic pooling) and introduced noises into the network, pushing up the error.

Noisy image experiments based on stochastic max pooling
This subsection attempts to verify if stochastic max pooling is robust in processing noisy images. For this purpose, the heads images were extracted from surveillance videos on public places. These highly noisy images, all of which are 32x32 in size, were collected into a head dataset, including 10,000 training samples and 2,000 test samples. Several images from the head dataset are given in Figure 6.
For comparison, Gaussian noises were added to SVHN and CIFAR-10. Then, the four models in subsection 4.1 were applied to the head dataset, the noisy SVHN and the noisy CIFAR-10. The results ( Table 2) show that model D (stochastic max pooling) outperformed the other models in processing noisy images [17, 18]. Next, the intensity of the additive Gaussian noise was increased, and the resulting noisy datasets were processed by the four models again. Figure 7 displays the convergence curves of the four models on the CIFAR-10 dataset added with high-intensity Gaussian noise (mean: 0; variance: 0.1). With the growing intensity of the additive Gaussian noise, models A, B and C could not converge to the optimal solution (the curve A, B, C are coincident in Figure 7), while model D (stochastic max pooling) continued to converge to that solution. It can be seen from the Figure 7 that stochastic max pooling can continue to converge at this time, but the error rate is high. This kind of limit experiment on the other hand shows the processing ability of the stochastic max pooling proposed in this paper. The comparison further verified the robustness of stochastic max pooling to noises.

Conclusions
The deep CNN has achieved remarkable results in image processing, thanks to its special structure. To further improve its performance, this paper optimizes the deep CNN both in function and structure. The stochastic max pooling was proposed to solve the problem that many training and test samples contain a lot of noises. Stochastic max pooling limits the selection range of pooling to a larger value that can represent the main information of the pooling area, reduces the possibility of introducing features, increases the randomness of the network, and enhances the generalization ability of the network. The proposed method can extract representative features through the pooling layer, and enhance the network randomness. The randomized network has a better performance in processing noisy images. The proposed method was verified on a self-designed head dataset and two public datasets (SVHN and CIFAR-10), and proved to be effective, superior and robust to noises.


extfieldsofstudy:
Computer Science
Medicine

text:
See before you see: Real-time high speed motion prediction using fast aperture-robust event-driven visual flow

Optical flow is a crucial component of the feature space for early visual processing of dynamic scenes especially in new applications such as self-driving vehicles, drones and autonomous robots. The dynamic vision sensors are well suited for such applications because of their asynchronous, sparse and temporally precise representation of the visual dynamics. Many algorithms proposed for computing visual flow for these sensors suffer from the aperture problem as the direction of the estimated flow is governed by the curvature of the object rather than the true motion direction. Some methods that do overcome this problem by temporal windowing under-utilize the true precise temporal nature of the dynamic sensors. In this paper, we propose a novel multi-scale plane fitting based visual flow algorithm that is robust to the aperture problem and also computationally fast and efficient. Our algorithm performs well in many scenarios ranging from fixed camera recording simple geometric shapes to real world scenarios such as camera mounted on a moving car and can successfully perform event-by-event motion estimation of objects in the scene to allow for predictions of upto 500 ms i.e. equivalent to 10 to 25 frames with traditional cameras.

Introduction
Optical flow is the measure of motion of an object projected on to the image plane of a camera. It is one of the fundamental steps needed for understanding a dynamic visual scene and has taken an even important role with newer applications such as autonomous driving vehicles [16], drones, action perception during user interactions [14] in robots and traditional applications like video editing [15] and stabilization. Because the visual sensing has traditionally been based on image acquisition at fixed time intervals, the computation of optical flow has been based on finding features that move across two or more consecutive images. Since the intensity of light received on the sensor is the most basic feature, the first principle approach for measurement of optical flow is given by the 'brightness constancy assumption' that assumes that the brightness of an object moving across the camera remains constant over short internal of time. Ideally this time interval should be infinitesimal, but practically, for the traditional cameras, this means the time between two recorded frames. This constant instantaneous brightness assumption forms the basis for the earliest algorithms such as those proposed by Horn and Schunk [4] and the Lucas-Kanade (LK) algorithm [5]. This has been further expanded to 'constant feature assumption' where complex features or descriptors are extracted [6] and tracked over multiple spatial scales [19]. With the advancements in convolution and deep neural networks, a number of new algorithms using these approaches have been proposed to compute visual flow [20,17,18]. Some of these methods even propose tackling optical flow computation as a learning problem [21]. While these approaches intend to achieve high accuracy using the improving computational power of GPUs and FPGAs, the fundamental problem of fast sensing and image processing still poses a hinderance towards using such techniques as part of a larger perceptive autonomous system. The new generation of dynamic visual sensors [1,2,3] might be able to fill in this niche application space by virtue of their fast, accurate sensing of light with high temporal precision. In this paper, we propose an algorithm designed for use with one such type of sensor [3]. Event-driven sensors have evolved over the last few years as possible succes-D R A F T sors to frame based classical cameras, especially for visual sensing in research areas that require high precision over a large temporal dynamics range like robotics [23,25,22,24], autonomous vehicles [26] and navigation in drones [27]. As these sensors provide precise motion information due to the inherent design of the pixels, they are ideal for fast visual flow computations. A number of methods have been proposed to compute visual flow using event based sensors. As events in the event-driven sensors are essentially encoding the light intensity captured by the pixels, algorithms based on the original image based Lucas-Kanade method have been proposed [7]. While these event-driven derivatives are fast, they cannot achieve the same accuracies as the frame-based variants due to the loss of information in conversion from intensity to events. Several algorithms are designed specifically to take advantage of the temporal nature of event-driven paradigm [8,9]. These algorithms use the spatiotemporal structure of events to estimate the flow by fitting a surface (usually a plane) and compute the normal of this surface as flow estimate. These algorithms maybe classified under the label of 'plane-fitting algorithms'. While these algorithms have improved accuracy of event flow, they are limited to computations of local dense flow. Further, the flow obtained is always computed as orthogonal to the edge irrespective of the direction of true motion. Thus, the flow computation is susceptible to the gradient of the edge. This problem is referred to as the aperture problem. The only way to tackle the aperture problem with a traditional plane-fitting method is to increase the size of the spatial neighborhood around the events when fitting the plane but this can lead to errors as the true size of the object is unknown and the shape of object may not be remain linear. A recent algorithm has been able to avoid this problem using constrained statistical properties of the object but it is computationally too intense to be used in real time and is only valid for object with closed form [10]. Another recent method for computing event-driven visual flow uses a spatio-temporal window of events and performs histogram matching of the event clusters to estimate the direction and speed of object. Thus, the current state-of-the-art algorithms lose the temporal dynamics of the input sensor events as they require pooling of events over a temporal and spatial window to avoid aperture problem.
Here we propose a new event-driven algorithm to solve aperture problem using multi-scale spatial pooling that uses the local erroneous flows computed at the lowest scales and corrects their direction towards the true direction of motion of the object. We mathematically prove that because of the specific properties of the plane fitting algorithms, pooling the fast but erroneous local flows over an appropriate spatial scale can correctly estimate the true direction of the object. Further, the estimation of this spatial scale can be computed at every event independently without any a-priori knowledge about the shape and size of the objects in the scene and is independent of any global motion of the camera. The proposed algorithm can perform in myriad of scenarios. Finally, this flow rectification allows us to perform very low-level event predictions i.e. when and where should new events appear according to the observations. We show via experiments that we can estimate on the fly, locations and velocities of moving objects up upto 500ms ahead in the future. Such prediction can be implemented for solving visual tasks such as collision avoidance and tracking.

Methods
The algorithm proposed in this paper uses multiscale pooling found in biological visual system in higher animals for hierarchical object recognition. The basic idea here is to perform local, fast flow measurements which might be incorrect in their direction estimations but are relatively reliable in amplitude estimates and then correct the direction estimates using global amplitude information. Figure 1 shows the principle idea motivating the correction procedure explained in the next section. Let us assume the most ideal case suited for the plane fitting method: a single bar moving in front of the camera generating a perfect event plane in the [x, y, t] space. If the bar is oriented orthogonal to its direction of motion Fig 1(a), the estimate of the velocity computed using the plane fitting method [8] (Fig 1(d)) would be equal to the true velocity U. But, if the bar is now rotated (b) by an angle θ, the velocity estimate of the flow from plane fitting is U n = U T n.n, n being the unit normal to the bar. The signed magnitude of this flow can be given by:

Multiscale pooling
This shows that the plane-ftting based estimated flow is equal to true direction of motion when the magnitude of the estimate is maximum, i.e. the cosine is maximum in Eq. (1). It is important to note that the normal n, without additional assumption, can have two directions -D R A F T Figure 1: (a) and (b) show an oriented edge moving across the sensor in true direction U and the predicted local flow U T n by fitting the plane over events in [x, y, t] space as in (d) and (e). The magnitude of the normal velocity component estimated by the plane fitting method is related to the orientation of the edge and true motion direction as U T n = |U| cos (θ). This relationship can be extended to a larger complex shaped object by linearizing it using multiple small edges (c) over small spatial region and performing plane fitting over each local edge (f). (c) The true flow direction can be estimated by finding the correct spatial size σ corresponding to the maximum mean magnitude |U n |.
namely either one of the two directions along the line orthogonal to the bar. However, if we are considering the temporal surface defined in [8] (as shown in figure 1(d-f)) as a bi-dimensional function t of (x, y), where the gradient of t allows us to define n as its unit direction vector then t is always increasing in the direction of the motion (i.e. the directional derivative of t along U is increasing) and we always have θ ∈ [− π 2 , π 2 ] or equivalently U t .n ≥ 0. We can generalize the observation in Eq (1) to more complex objects using this property of the plane-fitting flow computation. Figure 1(c and f) shows one such example case: let us consider a contour of a random shape moving with velocity U. We can approximate this shape as a set of line segments. For each pixel/event of each segment, the plane fitting method is estimating U n . If we consider a spatial neighborhood σ around a random pixel (example : green dot in (c) ) -for which we have estimated its normal velocity, the mean speed (i.e. the amplitude of the mean velocity) computed within σ is defined as: where K i is the length of the i th segment in pixels within σ and with the assumption that all the pixels are contributing in the mean flow estimation. If we assume that within this spatial neighborhood there lies a line segment j such that it is oriented relatively closest to the true motion direction (i.e. θ is minimal and ideally θ j = 0 when it is oriented orthogonal to the true velocity), we can find an upper bound for |U n |: Since the local mean speed is upper bounded by the amplitude of the velocity that is "most" collinear to U, the larger the |U n | we get from a given σ, the closer we are to U i.e. the σ leading to the largest |U n | is the "right spatial scale" for which |U − U n | is minimized. As we do not know the true velocity U, U m becomes our next best reference for U. According to this observation, for a given flow estimate, we define the problem of correction as the minimization problem of finding the neighborhood scale, σ, for which the cluster of flow estimates whose mean magnitude is close to the theoretical maximum |U| ≈ U m as described previously. Thus, for given neighborhood σ, we define the error function as: We then have according to (3): Since 0 ≤ |U n | ≤ U m , the problem of finding the right σ is equivalent to the minimization problem The above equations show that finding the scale with maximum mean magnitude is equivalent to finding the scale which best estimates the direction of true global flow. Thus, we only require to compute the flow over the smallest scale once, and perform the above maximization over larger spatial scales to get the true global motion direction. The proposed algorithm can therefore be divided into three steps. First, we compute local flow for each event using plane fitting. Second, we search for a spatial scale for which the mean magnitude of these local flows is maximized. Third, we calculate the mean direction for the flows in this scale and assign the direction to all the local flow events within this scale.

Implemented Algorithm
The steps involved in the implementation of the flow are described in Algorithm 1. The local flow was computed using an iterative implementation of the plane fitting flow as in [12]. Some minor changes are introduced to the original implementation in in [12] to improve performance. Firstly, to improve the accuracy of the flow and remove noise, we add an error correction step to ensure better accuracy of the plane fitting by computing the number of inliers (events that are within a certain distance from the fitted plane). If the number of inliers is more than half the total points used to fit the plane, we consider the fitting to be good and the flow estimate to be reliable. This improves overall efficiency and noise robustness as the rectification is only performed on valid flow events. To further avoid older events from corrupting flow estimates, we added a temporal history limit such that the correction was performed using events that occurred within a certain time (t past ) from current event. Table 1 lists the parameters values used to estimate flow for datasets used the experiments and results in Section 4.
Algorithm 1 Multi-scale aperture robust optical flow 1: for each event x, y, t do 2:

COMPUTE LOCAL FLOW (EDL):
3: Apply the plane fitting algorithm as in [8] to estimate the plane parameters [a, b, c] within a neighborhood of (x, y, t). for each (x i , y i ) in the neighborhood N do 7:t = (ax i − x) + (by i − y) 8: if |t i −t| <v 2 then

Parameter
Value Local flow Filter size N 5 pixels Inlier percentage 50% Rectification Spatial range σ 0 to 100 pixels in steps of 10 Temporal limit t past 5 msec

Experiments and results
The performance of the algorithm was measured in different scenario to test its effectiveness over the plane fitting method. The results is divided into two D R A F T  The EDL flow (red) however leads to a larger variance and almost a uniform distribution. Even with only one object in the scene (bottom row), EDL flow gives rise to two modalities but ARMS gives a single peak at 3π/2.

Camera fixed, multiple objects
Next, we tested the robustness of the multi-scale pooling in case when more than one object moving in front of the camera. To do this, we recorded two simple objects (two squares) moving across the camera in opposite directions. We also have a stationary object in the scene that may lead to noisy events. The experiment shows that the spatial pooling is not affected by multiple objects and the algorithm can find the correct scales for each object independently. Further, when the objects cross each other close by, the algorithm is robust enough to recover the correct directions. directions. This, is corrected by ARMS so that we get two distinct peaks in the direction histograms. As the objects collide and cross each other, the EDL becomes slightly worse and the peaks shift whereas the ARMS flow distribution remains invariant (Fig 3  [middle row]). Finally, as the objects move further, and we only have one object, the distributions becomes similar to the one in Exp 4.1.1 with single moving object. Again, while EDL gives two peaks for each of the edge orientations, we get a single peak from ARMS indicating the global motion direction.

Real world scene -Camera mounted on moving car
The flow rectification is also assessed through a real world scene in which the event-based camera was mounted on a car moving through traffic along the streets of Paris. The flow obtained from algorithm corrects the local perpendicular flow to provide a better global flow especially when the car is making turns, where the whole scene should have the same global flow direction. The optical flow corrections can improve the flow directions when the car is turning, making all events predicting the correct direction of the global motion. Further, the combination of speed and flow directions can easily segment objects moving independently from the car. Figure 4 D R A F T shows the EDL and ARMS flow for different traffic conditions. The bottom row shows interesting points (marked by black rectangles) in the scene where the ARMS flow successfully corrects erroneous directions of the EDL. These show that the spatial scale estimation works correctly even in a cluttered environment and large motion events. Further, direction estimates of independent moving objects such as cars is not affected by the global motion.

Event based prediction using ARMS flow 4.2.1 Trivial Case
The corrected direction estimates using ARMS flow can greatly improve the prediction of rigid object over traditional plane fitting methods. Figure 5 shows the actual future events (green) and the predicted events for EDL (red) and ARMS (blue) flow using events that occurred 250 msec in the past. The figure shows that using ARMS flow, all the predicted events of the square form another square but if the directions are not the same as in case of the EDL, the predicted shape is not rigid anymore and does not form a square. To quantify the performance of the two flows, we compute how well the predicted events from local and corrected flow maintain the rigidness of the object. That is, we compute the affine transformation needed to map the predicted events to the actual events. To simplify, we assume zero rotation and perform only translation and scaling. The graphs in figure 5 show the scaling and translation needed for the EDL and ARMS flow for a sequence of 360 msec broken into event clusters of 20 msec each. A perfect prediction would imply no scaling (i.e. scaling correction = 1) and no translation (translation correction = 0). The mean translation error for ARMS flow was 6.52 pixels per event vs 8.70 pixels per event for EDL flow. More importantly the scaling error in ARMS was only 0.085 compared to 0.141 in case of EDL. These results show that our proposed ARMS flow reduces the translation error and requires almost no scaling corrections showing that this flow can be used successfully to perform predictions on moving rigid objects.

Real world scenario
We placed the ATIS on a street corner and recorded pedestrians passing by. As in the previous case, for every event, we make prediction on where the event will occur after 500msec using the optical flow computed with local plane fitting or the rectification algorithm. We performed the transformation estimation for clusters of 50msec windows. While the direction component of the flow for each event is used as it is, the speed component of the flow is normalized by the mean speed i.e., each event i in the event-cluster has speed M and direction θ i , where M is the mean speed of all events and θ i is individual flow directions. Using these predictions, a reconstruction of the motion is made based on local and corrected flow as shown in figure 6 by red and blue dots respectively. The figure shows that the ARMS flow can predict the position of the man upto next 500msec very accurately. This is equivalent to about 20 frames from a traditional 25 fps camera. We used the transformation metric as used in the previous experiment to compare the performance of the two methods. The graphs show that the ARMS method outperforms the EDL through the sequence of recording for both scaling and translation corrections. The mean translation error for EDL was 7.1240 pixels while that for ARMS was 4.7558 pixels while the scaling error was 0.297 and 0.167 for EDL and ARMS respectively. Qualitatively, the cluster formed by the predictions based on the ARMS-Flow is less noisy and more compact and is much closer to the real events. This shows that our algorithm can maintain the shape on a rigid moving object even when the predictions are made on an event by event basis and therefore at very high temporal rates. The images shows the actual events (green), predicted events using EDL (red) and predicted events using ARMS (blue) over grayscale images obtained from ATIS. The predictions from ARMS clearly show much better fit with the actual events while the predictions from EDL tend to create inflated shapes. This is quantified in the graphs showing the transformation required to fit the predicted events to the true events. The EDL required larger corrections in both scaling and translation compared to ARMS predictions.

Conclusion
Event driven sensors provide an efficient sampling method to solve computer vision problems with scope for developing novel algorithms in temporal domain. Optical flow is an important feature for most vision based open problems and estimating fast yet robust flow is a crucial step. While some interesting algorithms have been developed to estimate visual flow using the event-driven sensors, they either fail to solve the aperture problem due to the emphasis on local spatio-temporal computation or are inefficient and do not really use the high event speeds of these sensors. In this paper, we have presented a novel visual flow algorithm that not only solves the aperture problem but also performs on an eventby-event basis justifying the use of event-driven sensors. In fact, we exploit the intrinsic property of the event based optical flow algorithm, that allows for correcting the directions of erroneous local flow estimates. We have shown here that the algorithm works in real world scenarios, in case of both stationary and moving camera. The algorithm is invari-ant to the number of objects or their size and does not require additional processing steps such as object detection and tracking. This fast implementation allows us to perform truly event based prediction of moving objects from 250 to 500 msec in future without affecting the shape and size of the object. This is equivalent to around 10-25 frames in traditional frame-based cameras. To the best of our knowledge , we could not find any methods using event-driven sensors that have attempted to perform such accurate predictions without any temporal binning of events. Further these predictions are invariant to the size and number of independent objects in the scene. These predictions can allow higher order recognition and tracking layers to perform at the high temporal rates at which events are generated. Indeed, our future goals are to use this algorithm as part of an autonomous driving car sensor system to allow for fast collision detection and detect abnormal driver and pedestrian behavior. Our algorithm does have certain short comings, as it only corrects the direction of individual flow but does not perfectly correct the magnitude of the flow. An im-D R A F T proved prediction of the magnitude of flow could allow us to make predictions at even longer durations of upto a few seconds. A possible solution to improve the magnitude estimates could be by using the gray scale information provided by the ATIS. A new algorithm to use this information is currently being developed by the authors. Regarding the memory and computation aspects, we implemented the algorithm in C++ on a traditional computer such that it requires very small amount of memory that only increases linearly with respect to the number of pixels in the sensor. While the traditional CPU is good for a QVGA sensor, a parallel neuromorphic hardware implementation could make the algorithm independent of the sensor resolution and allow real time motion based visual processing.