Zouqing Cai

Wei Pei
email: peiweidl@gmail.com

Yongying Zhu

Lei Mingyu Lu

Lei Wu

{zouqing Cai

Wu

Inferring and Analysis Drivers Violation Behavior through Trajectory

Keywords: trajectory data mining, violation driving behavior, violation movements, driver classification

In this paper, we present an algorithm for inferring violation movements and categorizing levels of driving behavior. With this algorithm we extract the speeding and retrograde behavior from the real trajectories datasets of Xinjiang, analyze the changing regulation of six streets in the working day and day off on the overall and explore the driving characteristics which is very dangerous(level 4). The results of this study can not only be used for early warning of drivers violations, but also provide the data support and decision basis for the traffic management department to master the situation of traffic violations and formulate the traffic management counter measures.

Introduction

The global status report on road safety 2015 indicates that worldwide the total number of road traffic deaths has plateaued at 1.25 million per year [1]. In 2015, the number of all kinds of production safety accident deaths has plateaued at 66182 in our country and 54% of the deaths are caused by traffic accidents. Drunk driving, speeding, retrograde, running the red light and other illegal operations account for more than 60% of the proportion of traffic accidents [2]. Due to a rising trend in vicious traffic accidents, the study of violation driving behavior has been a hot spot in recent years.

Several works have been proposed for driving behavior analysis in simulation systems [START_REF] Xu | Dynamic Modeling of Driver Control Strategy of Lane-Change Behavior and Trajectory Planning for Collision Prediction[END_REF][START_REF] Kedar-Dongarkar | Driver Classification for Optimization of Energy Usage in a Vehicle[END_REF][START_REF] Hu | Distinguish method of fatigue state based on driving behavior wavelet analysis[END_REF][START_REF] Shi | Evaluating Driving Styles by Normalizing Driving Behavior Based on Personalized Driver Modeling[END_REF][START_REF] Xu | Establishing Style-Oriented Driver Models by Imitating Human Driving Behaviors[END_REF]. For instance, sensors and simulators are used to recognize the fatigue driving state [START_REF] Hu | Distinguish method of fatigue state based on driving behavior wavelet analysis[END_REF].

With the popularity of mobile devices such as GPS and cell phones, large amounts of real driving traces are available to analyze the behavior of drivers [START_REF] Guo | TripVista: Triple Perspective Visual Trajectory Analytics and its application on microscopic traffic data at a road intersection[END_REF][START_REF] Carboni | Inferring Drivers Behavior through Trajectory Analysis[END_REF][START_REF]Analysis on the Safety of Bus Driving Using Vehicle GPS Track Data[END_REF][START_REF] Dueholm | Trajectories and Maneuvers of Surrounding Vehicles with Panoramic Camera Arrays[END_REF][START_REF] He | WhozDriving: Abnormal Driving Trajectory Detection by Studying Multifaceted Driving Behavior Features[END_REF][START_REF] Chen | iBOAT: Isolation-Based Online Anomalous Trajectory Detection[END_REF].

By inferring violation behavior and sum up the law of the illegal driving behavior, the traffic management departments can grasp the situation of traffic violations and take effective measures to reduce or even avoid major traffic accidents. At the same time, it has a warning effect on the drivers who often break the rules. In this paper, we focus on real trajectories of drivers, propose an efficient algorithm to identify the violation behaviors of drivers based on individual trajectories and classify the drivers according to the risk weights. According to the different function area, six roads including four one-way streets are picked up to demonstrate the algorithm. The first two steps of the algorithm extract the speeding and retrograde behavior, analyze the change regulation of illegal driving behaviors either workday or rest day and discuss the place where the driver often has retrograde behaviors. Furthermore the violation behavior of drivers is evaluated with the last two steps of the algorithm and the very dangerous drivers'(level 4)personality characteristics is analyzed.

The rest of the paper is organized as follows. Section2 introduces the related work in illegal driving behavior analysis. Section3 presents the main definitions used in this paper, experiments with real data and proposes a method to find speeding and retrograde behavior. Section4 shows and discusses the experiments results and Section5 concludes the paper.

RELATED WORK

Several works have been done to study the driver behaviors in simulation systems. Kedar-Dongarkar and Das presented a new method of driver classification for optimizing energy usage [START_REF] Kedar-Dongarkar | Driver Classification for Optimization of Energy Usage in a Vehicle[END_REF]. Vehicle acceleration, braking, speed, and throttle pedal were used to classify the drivers into three categories: aggressive, moderate and conservative. Hu presented a new identification method of fatigue driving state, which is obtained from driving behavior data analysis both about normal driving state and the fatigues one [START_REF] Hu | Distinguish method of fatigue state based on driving behavior wavelet analysis[END_REF]. Quantitative evaluation of driving styles by normalizing driving behavior was studied in [START_REF] Shi | Evaluating Driving Styles by Normalizing Driving Behavior Based on Personalized Driver Modeling[END_REF].

Some works which analyze driving behavior using real GPS trajectories will be introduced as follows. For example, Carboni was interested in abnormal behaviors of individual trajectories of drivers, and presented an algorithm for finding anomalous movements and categorizing levels of driving behavior [START_REF] Carboni | Inferring Drivers Behavior through Trajectory Analysis[END_REF]. Li proposed a method to realize the safety analysis of vehicle driving behavior by using GPS vehicle trajectory data [START_REF]Analysis on the Safety of Bus Driving Using Vehicle GPS Track Data[END_REF]. They studied the proportion of the bus over-speed time in entire driving time. Dueholm J V presented a method of latent semantic information mining for trajectory data [START_REF] Dueholm | Trajectories and Maneuvers of Surrounding Vehicles with Panoramic Camera Arrays[END_REF]. He M proposed WhozDriving to solve the issues of detecting abnormal driving trajectory in driver's history trajectories [START_REF] He | WhozDriving: Abnormal Driving Trajectory Detection by Studying Multifaceted Driving Behavior Features[END_REF]. Chen and Zhang focused on abnormal trajectories of taxis that deviated the standard route from origin and destination, where the standard route represented the path followed by the majority of taxis [START_REF] Chen | iBOAT: Isolation-Based Online Anomalous Trajectory Detection[END_REF].

Although the previous detailed works analyze several illegal characteristics of driving, most of them have not been developed with real trajectories. Some works used the real trajectory analysis of dangerous driving behavior, but they concentrated on how to judge the abnormal behavior such as rapid change, sharp turn speeding etc. They rarely conduct a comprehensive analysis of illegal behavior and summarize the rules of violation driving. In this paper we focus on real trajectories of drivers, propose an algorithm to identify violation behavior and classify drivers into different levels of danger. The effectiveness of the algorithm is greatly proved by experiments.

Discover Traffic Violation

In this section we firstly present some basic definitions and formulas (Section3.1). Secondly, filter trajectories will be introduced in Section3.2. Finally, an algorithm will be proposed to find and evaluate violation driving behavior in Section3.3.

Main Definitions

The basic definitions for trajectories are described as follows.

Definition 1. Point. A point is defined as p =(id, x ,y ,t ,s ,h), where id is a vehicle ID represents a driver, x and y are the latitude and longitude that represent space ,t is the timestamp in which the point has been collected and h is a direction angle that represents the driving direction.

Definition 2. Trajectory. A trajectory is expressed as T={ , … }, where ={ , … }, =( id, , , , , ), < <…< .A trajectory includes one or several roads, and r represents a road. Definition 3. Subtrajectory. A subjectory s of T is a series of points < , ,…,< , where ⊂ T and 1≤k≤j and j≤n. (In this paper, subtrajectory division is based on road. A road of trajectory is corresponds to a subtrajectory.) Definition4. Trajectories. A trajectories is ={ , … }, where ={ , … }, pi=( id, , , , , ) , < <…< . Definition 5. Violation movement. A trajectory has violation movements when it has at least one subtrajectory with violation s such as the driving speed exceeds the road speed limit, the driving direction is contrary to the normal driving direction.

The case which meets the equation ( 1) is judged as the over speed and the one meeting the equation (2) is retrograde. v is the speed of the point, and h stands for the direction of the point. r represents a road ,and r=1 presents a one-way street. v' represents the maximum value of road speed limit, and h' is the direction of road restrictions.

(1)

(2)

After defining the violation movement, the movements are analyzed deeply. Some characteristics are found to evaluate driving behavior. In this analysis we mainly consider three features: F1: The driver only has a violation movement in a road. F2: Continuous illegal behaviors in a road. F3: Continuous illegal behaviors in different roads.

Based on these three features, we defined four levels of drivers: Level 1(Careful driver): A careful driver is without any violation behavior. Although someone may complain that it makes no sense to discover careful drivers, it is very useful for the company to give a reward or compliment to the good drivers.

Level 2(Distract driver): A distract driver is with feature F1. The driver is distracted while driving with the performance of many secondary tasks, including texting and dialing cell phones and so on.

Level 3(Dangerous driver): A dangerous driver is someone with feature F2. Such as a driver continues to over-speed on the road.

Level 4(Very dangerous driver): A very dangerous driver is someone with features F3. For example, the driver has a continuous speeding or retrograde driving behavior in different roads.

Filter Trajectories

We get real trajectories of taxis collected at February 2016 in the city of Xinjiang, China. The dataset has about 300 million data with points collected at intervals of 30 second, including vehicleid, gettime, storetime, speed, direction, latitude and longitude. The taxi dataset is for a city scale but we just focus on several specific routes, so we implement filter trajectories which has the same origin and the same destination on a road [START_REF] He | WhozDriving: Abnormal Driving Trajectory Detection by Studying Multifaceted Driving Behavior Features[END_REF]. Using this method, trajectories are filtered in six routes where close to different function area.

Discover Speeding Or Retrograde

In this paper an algorithm is proposed to discover violation driving behaviors. Firstly it identifies violation movements based on over-speed and retrograde driving behavior. Secondly it evaluates the driving behavior according to the formulas which we define.

Because the violations driving behavior is very transitory, the subtrajectories with violations behavior are normally only a few points. If considering the violation movements of each point, noise can be introduced. If considering too many points (three or more) the violation movement may not be captured. So after some analysis and experiments on real trajectory data, it consider that at least two consecutive points should have violation movements for a subtrajectory to characterise the violation behavior. Violation behavior can be captured well for trajectories with frequently sampled points, like 1 or 2 seconds. A dataset with sampling rate as 30 seconds, for instance, can also reveal violation behavior.mm. The algorithm of findViolation is as follows. findViolation:

Ts={ , … }.For each trajectory , using the length of the road to overlap violations, ={ , … }, vio( )=vio( )+vio( )+…+vio( ). ={ , … }. For each point , and can be computed according to equation (1)and(2).

The count of subtrajectories violations movments can be computed according to the road .. violation( )= ∑( * + * ) (3) The violation behavior of drivers is evaluated using formulal(4)

(4)
In findViolation, the first two steps are used to discover the violation movements, which named fv-1. The last two steps of the algorithm are used to divide the drivers into different levels of violation, which named fv-2.

Experiental Results and Dicussion

In this section our algorithm is demonstrated and the experimental results are analyzed with the real-world GPS trajectory dataset. The real dataset is processed in Section4.1. We analyzed the different change laws of different roads in working days and day off in Section4.2. The violation behavior of drivers is evaluated and the characteristics of the very dangerous driver are analyzed in Section4.3.

Processing

The dataset that mentioned in Section4.2 is used in the experiment. Firstly, the error points are removed. Such as the latitude or the longitude is null, or the value of speed is less than zero. Secondly, a day is divided into 24 time periods. Thirdly, all the tracks are adapted to the spatial division and established the index to speed up the search. Finally, the trajectory points are matched with the map using AMAP API.

Part one

The superscript numeral used to refer to a footnote appears in the text either directly after the word to be discussed or -in relation to a phrase or a sentence -following the punctuation mark (comma, semicolon, or period). Footnotes should appear at the bottom of the normal text area, with a line of about 5cm set immediately above them .

In this section we use February 1 st , 2016 (Monday) as the example of working day and February 27th, 2016(Saturday) as the example of day off to explore the temporal and spatial evolution of speeding and retrograde on the same roads. We pick up a region which has a large number of taxis. Fig. 1 shows the heatmap of the area on Monday. Based on the color change, it is clear to show where the number of operation taxis is the largest. According to the heatmap, we choose six busy roads and use the method which is mentioned in section 3.2 to filter trajectories. The relevant information of the roads is shown in Table 1. As we all known that roads can cross over different functional areas. In order to expediently discuss the relationship between the distribution of the taxi and the different functional areas, the roads are divided into four groups according the main utilization of land along the roads. For example, although there are two top grade residences nearby Zhongshan Rd, it is defined as a commercial road because there are several supermarkets and shopping malls on both sides of the road. Table 2 shows the results of the division. Fig. 2 and Fig. 3 show the changing laws of the operation taxis in February 1 st , 2016 (workday) and February 27 st , 2016 (rest day). The changing rules of operating taxis during the two days have similar characteristics. For example, the number of the operation taxis gradually decreases from 00:00:00 to 07:00:00 and there are lots of taxis from 10:00:00 to 17:00:00. The distribution of operating vehicles between weekdays and rest days are different. For example, there are more operation taxis on workday than the rest day, the rest day only has a low peak and the proportion of vehicles in the night are bigger. From the micro perspective, Zhongshan Rd has a large amount of vehicles at 10:00:00-12:00:00 and 13:00:00-17:00:00 on Saturday which is related to the commercial character of this road .The character of Jianshe Rd is a residence community. The variation of the number of vehicles on Monday is quite similar to the one of Saturday, which has more vehicles on Monday at 10:00:00-12:00:00 and 16:00:00-18:00:00. This period is the peak of commuting. By comparing the trends of the two graphs, we find a strange phenomenon that the Renmin Rd on Monday at 12: 00: 00-14:00:00 has a peak valley but on Saturday is a trough. The reason for it is that there are many office buildings near the Renmin Rd, and more staff go out to eat or go home at the lunch time of 12: 00: 00-14: 00: 00 on Monday (working day) etc. The retrograde behavior is extracted from the real dataset by fv-1. Fig. 4 and Fig. 5 show the changing law of the retrograde vehicles. In Fig. 4 we find that there are many vehicles with retrograde behavior from 10:00:00 to 19:00:00. The number of the retrograde taxis gradually decreases from 00:00:00 to 07:00:00 because of the reducing total number of vehicles. Comparing the trend of each road in Fig. 2 and Fig. 4 we find that the general trend of illegal vehicles and operating vehicles is similar. Of course, it also has individual differences. For example, On Monday, the overall trend of operating vehicles in Zhongshan Rd from 12: 00: 00 to 14: 00: 00 is a peak valley and reaches its maximum at 13:00:00, but the trend of retrograde vehicles is a trough and drops to the lowest at 13:00:00. Owing to the trips of day off are random, the retrograde vehicles are also distributed randomly in Fig. 5. The statistics show that in addition to Xignfu Rd, the numbers of retrograde vehicles of the other three roads in the working days are more than the rest day. On Xingfu Rd there are 234 drivers with retrograde behavior on working day and there are 342 on rest day. The Xingfu Rd is used for Health and Education. There are a primary school, a secondary school and a vocational college near the road. The reason for the number of violation vehicles in the working day less than the rest day is that the students and their parents can comply with the traffic rules. Fig. 6 shows the heatmap of retrograde vehicles. We find that retrograde behavior occurs at the crossroads with a higher frequency. So it suggest that the traffic management department should increase the supervision on the intersection.

0
The speeding behavior is extracted from the real dataset by the fv-1. Through analyzing Fig. 7 and Fig. 8 we find that the number of over-speed vehicles at night is higher than the one at the daytime. The number of serious over-speed vehicles in workday is more than that in the rest day. At 9: 00: 00-10: 00: 00 the number of speeding vehicles is very small. According to Fig. 2 and Fig. 3 we find that the traffic flow during this period is very large, so we speculate that in the absence of speeding vehicles during the period, the road may be in a congested state. The low-level overspeed behavior that no more than 20% is the top of the over-speed ranking .Severe speeding more than 50% is the least.

Part two

In this section 20 vehicles trajectories are picked up randomly from Section4.2 to find violation behaviors of individual trajectories of drivers and categorize levels of driving behavior with the algorithm. The results are shown in Table 3. In order to illustrate the violations trajectories in detail, we show a trajectory of a very dangerous driver. Fig. 9 shows the part of a very dangerous driver's trajectory, where the red line represents the trajectories with violation subtrajectories, the blue line represents the normal trajectory and the red point represents the driver with violation behavior in this position. As mentioned in section 3.3, at least two consecutive points with the violation movement can be characterized with violation behavior for a subtrajectory. So we draw red lines to match the consecutive points with the same violation behavior. It is easy to find that the driver has violation movements on different roads.

The driver's trajectories for a whole day are shown in Fig. 10. It can find that many discontinuous trajectory points have violation behavior and some of points are located at the intersection. Due to the dataset with sampling rate as 30 seconds and having few taxis in the area at the same time, it can infer that the drivers may have illegal behavior such as running a red light. It is not only very dangerous to passengers and themselves, but also to other cars on the road.

Conclusions and Future Works

Trajectory behavior analysis is becoming very useful in our life. In this paper we presented an algorithm to measure the violation behavior of drivers. Firstly, the algorithm finds violation movements such as speeding and retrograde. Secondly, the driver is divided into different danger levels according to the characteristics values related to the violation movements. Experiments show that this algorithm can correctly detect the violation movement and mark the violation trajectory. Through the experimental analysis, we suggest that the traffic management departments increase supervision at intersections. At the same time, we remind that the drivers do not have violation driving behavior to guarantee the safety of yourself and others.

Tens millions of taxis information are generated every day and it is difficult for us to deal with large amounts of data so we just analysis two days' information. In the future, we will intent to perform more analysis with more real data, to explore speeding, retrograde and other illegal driving behavior such as running a red light.

Fig. 1 .

 1 Fig. 1. The thermodynamic chart of the area.

Fig. 2 .Fig. 3 .

 23 Fig. 2. The regulation of taxis on Monday. Fig. 3. The regulation of taxis on Monday.

Fig. 4 .

 4 Fig. 4. The retrograde taxis on Monday.

Fig. 5 .

 5 Fig. 5. The retrograde taxis on Saturday.

Fig. 6 .

 6 Fig. 6. The heat map of retrograde taxis on Monday.

Fig. 7 .

 7 Fig. 7. The level of speeding taxis on Monday. Fig. 8. The level of speeding taxis on Saturday.

Fig. 9 .Fig. 10 .

 910 Fig. 9. The very dangerous driver. Fig.10. The very dangerous driver for a whole day.

Table 1 .

 1 THE INFORMATION OF THE SIX STREETS

TABLE 2 .

 2 FONT SIZES OF HEADINGS.

TABLE CAPTIONS

 CAPTIONS

		SHOULD BE POSITIONED ABOVE
	THE TABLES.
	Character	Streets
	Commercial	Zhongshan Rd, Democracy Rd
	Health and Education	Liberation Rd, Xingfu Rd
	Administrative office	Renmin Rd
	Residence Community	Jianshe Rd

Table 3 .

 3 THE RESULTS OF PART TWO

	Level	Results
	Precise driver	15
	Imprecise driver	2
	Dangerous driver	0
	Very dangerous driver	1

Acknowledgment

The work was supported by the National Natural Science Foundation of China (No. 61001158, 61272369 and 61370070), Liaoning Provincial Natural Science Foundation of China (Grant No. 2014025003), Scientific Research Fund of Liaoning Provincial Education Department (Grant No. L2012270), Specialized Research Fund for the Doctoral Program of Higher Education (SRFDP no 200801511027), and Fundamental Research Funds for the Central Universities (Grant No. 3132015084).


Binbin Hu
email: hubinbin@bupt.edu.cn

Chuan Shi
email: shichuan@bupt.edu.cn

Jian Liu

Playlist Recommendation based on Reinforcement Learning

Keywords: music recommendation, reinforcement learning, Markov decision process

Recently, there is a surge of recommender system to alleviate the Internet information overload. A number of recommendation techniques have been proposed for many applications, among which music recommendation is a kind of popular Internet services. Unlike other recommendation services, music recommendation needs to consider the interaction and content information, as well as the inherent correlation and feedback among music playlist. Thus, in this paper, we model music recommendation as a Markov Decision Process, and consider the music recommendation as a playlist recommendation task. Along this line, we propose a novel reinforcement learning based model, called RLWRec, to exploit the optimal strategy of playlist. Two novel strategies are designed to solve the curse of state space and efficient music recommendation. Experiments on real dataset validate the effectiveness of our proposed method.

Introduction

With the rapid development of information technology and Internet, human society has gradually entered the era of information overload, where users have more and more difficulties in accessing information in Interest. Thus recommender systems [START_REF] Resnick | Recommender systems[END_REF] arise at the historic moment, which utilize user-item interaction and/or content information associated with users and items [START_REF] Shi | Integrating heterogeneous information via flexible regularization framework for recommendation[END_REF] to help users to predict preference and make reasonable recommendation.

Recommender systems have been widely used in various applications [START_REF] Shani | An mdp-based recommender system[END_REF][START_REF] Mobasher | Integrating web usage and content mining for more effective personalization[END_REF][START_REF] Konstan | Recommender systems: A grouplens perspective[END_REF]. Among them, the music recommendation is a very popular web service, which recommends songs from huge corpus by matching songs with user preference [START_REF] Wang | Exploration in interactive personalized music recommendation: a reinforcement learning approach[END_REF]. Existing recommendation techniques, such as collaborative filtering, matrix factorization and so on [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF][START_REF] Wang | Exploration in interactive personalized music recommendation: a reinforcement learning approach[END_REF][START_REF] Song | A survey of music recommendation systems and future perspectives[END_REF][START_REF] Schedl | Location-aware music artist recommendation[END_REF][START_REF] Yoshii | Hybrid collaborative and content-based music recommendation using probabilistic model with latent user preferences[END_REF], typically utilize ratings of users on items (may also include some additional information, e.g., social relations and geography) to infer user preference and make proper recommendation. In these methods, there are weak ties among adjacent items. Moreover, there are rare feedbacks of users on items, and these feedbacks have little swift effects on subsequent items. We think these methods may not be suitable for music recommendation, since there are some specific characteristics in the process of listening to music. We know that people listen to music that reflect their feelings. And the music playlist has the inherent and consistent feelings. In addition, there are many meaningful feedbacks of users on songs, such as "skip","listen","download" and "collect". These feedbacks reflect different preferences of users on songs.

In order to consider the song correlation, advanced methods introduce Markov decision process [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF] and reinforcement learning [START_REF] Sutton | Reinforcement learning: An introduction[END_REF], and regard the recommendation task as decision problem. Chi et al. [START_REF] Chi | A reinforcement learning approach to emotion-based automatic playlist generation[END_REF] models the automatic playlist generation problem as Markov decision process and learns the user preference with reinforcement learning. Furthermore, considering the influence between songs, Liebman et al. [START_REF] Liebman | Dj-mc: A reinforcement-learning agent for music playlist recommendation[END_REF] relate learning individual preferences with holistic playlist generation and propose a novel reinforcement-learning framework DJ-MC to recommend song sequences. Moreover, Wand et al. present a reinforcement learning framework based on Bayesian model to balance the needs to explore user preferences and to exploit this information for recommendation [START_REF] Wang | Exploration in interactive personalized music recommendation: a reinforcement learning approach[END_REF].

In this paper, similarly, we model the recommender system as Markov decision process, and employ reinforcement learning to solve it. However, our research differs from state-of-the-art models in several ways: [START_REF] Chi | A reinforcement learning approach to emotion-based automatic playlist generation[END_REF] We integrate the user feedback into model as well as considering the influence between songs. [START_REF] Konstan | Recommender systems: A grouplens perspective[END_REF] We propose a state compression method to capture enormous state space of MDP. Meanwhile, we design a recommendation strategy to make a trade-off between accuracy and coverage of recommendation. With these two designs, we propose the RLWRec model based on Q-learning with -greedy strategy. The experiments on real music datasets show the effectiveness of our model. Meanwhile, we analyze the influence of user listening frequency and the window size on our model.

Preliminary

In this section, we describe notations used in the paper and present some preliminary knowledge.

Markov decision process is a expansion of Markov chain, whose difference is the actions and rewards to join. In general, MDP is defined as a quintuple form M =< S, A, T, R, γ >, where S is the set of states, A is the set of actions, T : S × S × A → R depicts the function of state transition, representing that state s will transfer to state s in probability P r(s |s, a) when performing action a, R : S × S × A → R is the reward function, representing that the rewards of performing action a in state s and reaching state s is R(s , s, a). γ(0 ≤ γ ≤ 1) depicts the attenuation of rewards, the smaller γ means the more importance of immediate rewards. The key of MDP is to find a optimal strategy π : S → A, representing a mapping of states to actions, i.e. the optimal action a = π(s) in each state.

Reinforcement learning is the name of a set of methods and algorithms for controlling agents to automatically improve their performance by tying to maximize the rewards received from environment. After modeling the real problem as MDP, we can apply reinforcement learning technology to estimate optimal strategy. Q-learning [START_REF] Watkins | Learning from delayed rewards[END_REF] and SARSA [START_REF] Rummery | On-line Q-learning using connectionist systems[END_REF] are the most widely employed in actual problems, which are both primarily concerned with estimating the value of performing any action in each state and dynamically update the learned strategy.

Reinforcement Learning based Playlist Recommendation Model

In this section,we describe our recommendation problem and model the recommendation task as MDP, and then propose the Reinforcement Learning with W indow for Recommendation (called RLWRec).

Problem Description

Listening music on the music platform is actually an interactive process: the music platform recommends a song for us, and we can choose a series of actions as feedback for the music platform, such as skip, listen, download, collect and so on. As a consequence, we can obtain the sequence of interaction between music platform and users, which can be considered as a MDP. Therefore, the recommendation task can be summarized as follows: based on a music corpus and the interactive records, we train the recommender system to recommend songs which will follow user preferences.

Recommendation Framework based on Reinforcement Learning

In this section, we model the recommendation task as MDP. Concretely, we will model states, actions and reward function.

Modeling States and Actions

In order to learn user preferences from interactive process, we have to model user's states to reflect his or her listening history.

Inspired by the N -Gram model, which predicts the next word while knowing last N words, we model user's states as sliding window of size K, which preserves the K songs recently listened. And we approximatively regard the state as user's listening history on the music platform. Thus, we concretely define the music corpus M = {m 1 , m 2 , ..., m n }, and then the state space of our model can be represented as

S = {(m i , m i+1 , ..., m i+K-1 )|∀j ∈ [i, i + K -1], m j ∈ M }.
With the definition of states, we regard each song as an action. Therefore, each time our model executes an action a (recommending a song) once, user's state will transfer, the sliding window of state s will slide a step backward, and take the song recommended into window, thus reach a new state s . For an example, we assume user's current state s = (m 1 , m 2 , ..., m K ), the recommender system recommends a song m K+1 for the user according to the past strategy, then the user's state will transfer to s = (m 2 , m 3 , ..., m K+1 ). Thus, the action space of our model can be represented as A = M .

Modeling Reward Function The basis of reinforcement learning lies in the rewards the agent receives, and how it updates state and action values [START_REF] Taghipour | Usage-based web recommendations: a reinforcement learning approach[END_REF].

As for our recommender system, users will express their feelings via a series of implicit or explicit feedback when a song is recommended. Hence, we need to construct a reward function to integrate user's various feedback and measure the achievement to the recommendation goal. In this paper, in consideration of real dataset, we only extract three feedback information: listen, collect and download. Thus, we design a reward function as follows:

R(f ) = 3 i=1 w i * I(f == F i ), (1)
F = {listen, collect, download},
where F is a feedback set, I is boolean function, w i is weight, mapping user's feedback to discrete numerical space.

With the definition of the elements of MDP, we can summarize our model as Fig. 1.

Model Challenges

Although we have modeled the recommendation task as MDP, how to solve is not a trivial problem. We will still face the following challenges.

State Space Challenge Our model preserve user's latest K songs with sliding window of size K, which approximates to user's listening history. However, the model will face a serious problem -the curse of state space. Each state of MDP is composed of K songs, so that our model's state space is |M | K (|M | represents the size of song set). In terms of time and space complexity, the exponential state space cannot be accepted. Hence, we present a state compression algorithm to transform individual songs to song clusters for further model learning.

Recommendation Challenge We apply reinforcement learning algorithm in MDP problem, which will estimate a series of strategy for recommender system. Thus, it is necessary to select a proper strategy for a recommendation. In addition, picking a song from a song cluster is another important issue we have to consider. Therefore, we design a novel recommendation strategy based on tree structure to improve the recommendation performance.

4 Model Learning

State Compression based on Collaborative Filter

In order to reduce the dimensionality of state space for efficient training and predicting, we propose a state compression algorithm based on collaborative filter. The basic idea is that it clusters songs according to the similar user's performance, and then replaces songs to song clusters in the model learning process.

User Clustering Our model is mainly used for personalized recommendation of single user. Hence, we extract a user's listening logs from dataset for model training, we name this user as su. We construct each user's feature vector, consisting of user's feedback (listen, download and collect) for all songs in dataset, which reflects user's music preference. Then, we measure similarity between su and each user in dataset. After similarity measure, we extract top k similar users, whose feedback will be feature for song clustering later.

sim(u) = su • u |su| * |u| , ( 2
)
where u is arbitrary user except su, sim(u) depicts music preference similarity between u and su.

Learning Algorithm

We choose Q-learning as our learning algorithm. This method, combining dynamic programming and Monte Carlo's idea, is an efficient model-free reinforcement learning algorithm. Moreover, we bring -greedy strategy in learning process, which can make a trade-off between exploration and exploitation.

Q-learning Q-learning is primarily concerned with estimating an evaluation of performing specific actions in each state, known as Q-values, which not only consider action's immediate rewards but also takes accumulative rewards into account. We denote the Q-value of performing specific action a in state s as Q(s, a). And we design the Q-value update rule as follows:

Q n (s, a) = (1 -α n )Q n-1 (s, a) + α n [R(s, a) + γ max a Q n-1 (s , a )] (3)
with

α n = 1 1 + V isitCount(s, a) , (4)
where R(s, a) represents the immediate reward of performing action a in state s, s , a are next state and action of s, γ controls the attenuation of accumulative rewards. Moreover, we bring in α n , related to the count of performing same action in same state. This rule can partly reveal user's music preference and accelerate the coverage with the decreasing value of α n .

-greedy Strategy The training of reinforcement learning is a process of trying. So when we choose an action in a state, we should consider two aspects: (1) knowing the rewards of each action. (2) choosing the action of most reward recently. Thus, reinforcement learning has two strategies: exploration strategy (trying as many actions as possible) and exploitation strategy(choosing the best action given current information). Obviously, the two strategies are conflicting. Hence, we take advantage of -greedy strategy, which is an eclectic collection of above two strategies. -greedy strategy guarantees the trade-off between exploration and exploitation based on a probability : exploring in the probability of and exploiting in the probability of 1-.

Recommendation Strategy

As mentioned above, Q-learning can evaluate the true rewards of performing each action in each state, knowing as Q-value. Thus, we can get the list of Qvalue of actions in each state. Thus, we need design a recommendation strategy to choose a song cluster and then recommend a song for the specific user. First of all, for the specific user su, we let him set a score for each song in the dataset, representing the preference of song of su, denoted as pref erence(m). We give the calculation rule as follows:

pref erence(m) = f ∈F count f * w f , (5)
F = {listen, collect, download},
where count f represents the count of user performing feedback f for song m, w f is the preference weight of user performing feedback f for song m. Meanwhile, in the process of recommendation, we also can update user's preference with the timely feedback, as follows:

pref erence n (m) = pref erence n-1 (m) + w f . (6)
Based on user's preference score, our model can recommend for user by serval strategies. One naive idea is recommending by the maximal Q-value and preference score. However this strategy will seriously bring down the coverage of recommendation. Moreover, we can combine this strategy with -greedy strategy to improve the coverage of recommendation. In order to get better performance further, we design a recommendation strategy based on tree structure: recommending song cluster according to the probability of Q-value and recommending song according to the probability of preference score, as shown in Fig. 2. For example, assume in the state s, the recommender system has the probability of P 12 to choose the song cluster c 2 and further recommends the song s 2 with the probability of P 22 . Recommending based on probability can not only guarantee accuracy of recommendation but also improve the coverage of recommendation.

Experiment

In this section,we will validate the effectiveness and traits of our model by conducting a series of experiments.

Dataset

In this paper, we use a real music dataset for experiment, including song data and user interaction record of six months. This music dataset consists of 349949 users, 10842 songs and 5652232 feedback (listen, collect, download). Meanwhile, this music dataset includes song's essential features, such as artist, publish time, initial popularity and so on. Based on the raw data, we cut the dataset into three smaller dataset according to user's listening frequency. These three datasets are as follows: low frequency dataset (the frequency of songs listened by users is smaller than 300), medium frequency dataset (between 400 and 700), and high frequency dataset(larger than 800). And in these datasets, we filter out some special users (listen too many or too few) and guarantee the number of users at around 600 and the number of songs at around 10000.

Comparison Methods and Metrics

Because there are few methods integrating user feedback for music recommendation, and advanced methods based on reinforcement learning [START_REF] Chi | A reinforcement learning approach to emotion-based automatic playlist generation[END_REF][START_REF] Liebman | Dj-mc: A reinforcement-learning agent for music playlist recommendation[END_REF][START_REF] Shani | An mdp-based recommender system[END_REF] don't use quantitative indicators to measure the recommendation performance, we design the following methods as baselines.

• RandRec. Randomly choose songs from user's listening history and recommend for user.

• CFRec. Recommend songs for user according to other users with similar music preference.

• PopRec. Calculate song's popularity and randomly recommend the topk popular songs for user.

In the experiment, we set the sliding window size k = 3, the attenuation factor and the exploration probability in Q-learning γ=0.8 and =0.7. Meanwhile, optimal parameters are set for other algorithms.

In this paper, we calculate the accuracy and coverage of recommendation. Similar with the traditional F 1 score, we combine the accuracy and coverage and use the Score to evaluate the performance of list prediction.

Accuracy = |{s ∈ L p and s ∈ L t }| |L p | , (7)
Coverage = set(L p ) ∩ set(L t ) |L t | , (8)
Score list = 2 * Accuracy * Coverage Accuracy + Coverage , (9)
where L p is the song list predicted by models, and L t is the actual listening list.

A lager Score means a better performance.

Effectiveness Experiments

In order to validate the effectiveness of our model, we will compare RLWRec to other baselines. For each dataset, we use 90% of data as training and the rest of the dataset for testing. Moreover, the random selection is carried out 10 times independently and the average results are illustrated in Fig. 3. It is clear that our RLWRec model achieves significant performance improvements compared to other algorithms. It indicates the benefits of recommendation with reinforcement learning. It also shows that RLWRec is more stable with the growth of song list length. Moreover, as the increment of song list length, the performance of RLWRec will gradually converge and tend to be steady, which reveals that the stabilization of users performance of music in a period of time.

Low

Influence of user's listening frequency

In the above experiments, comparing different frequent datasets, we can find that most methods are affected by the listening frequency. In this section, we further study the influence of user's listening frequency to the prediction performance. We do the same experiments, and compare the performances of predicting the song list of length 20.

As illustrated in Fig. 4, it is clear that most of models will be influenced by user's listening frequency. The performance of RLWRec will slightly decrease as the growth of user's listening frequency. It can be inferred that our model's training state space will increase as the growth of user's listening frequency, which leads to the difficulty of choosing the right action in a specific state. As for the recommendation methods base on other users' behaviors, such as CFRec and PopRec, the influence is more slight. 5.5 Influence of the window size RLWRec, based on reinforcement learning, models the recommendation task as a MDP, where we use the sliding window of size K to preserve the K songs user recently listened as user's current listening history. In this section we design a experiment to analyze the influence of the window size K. Due to the restriction of computing ability and memory space, we set K as 1, 2, 3 respectively for experiments and other parameters remain unchanged. The result is shown in Fig. 5.

The result shows that the siding window size can affect our model to some extent. It is obvious that the best result is achieved when the size of window is 3. The reason lies in the window of smaller size (i.e. less listening history) will not hold enough information in memory to make better recommendation. Meanwhile, a large window tend to provide our model a longer memory and achieve a significant performance. However, it will cause a larger state space and need more computing time.

Influence of different recommendation strategies

In the section 5.3, we show three recommendation strategies in our model: native recommendation strategy, recommendation with -greedy strategy and our recommendation strategy based on tree structure. In this section, we do experiments in the medium frequency dataset to show the influence of the three recommendation strategies. The result is shown in the Fig. 6.

It is clear that our recommendation strategy based on tree structure well outperforms other recommendation strategies. It indicates that our recommendation strategy can balance the accuracy and coverage of recommendation and improve the performance of the recommender system. Moreover, it also shows that the performance of our recommendation is more stable with the growth of the length of song list. Because the native recommendation strategy will restrict the coverage of the recommender system and the -greedy strategy will bring in the uncertainty and decrease the accuracy of the recommender system.

Conclusion

In this paper, we integrate the user feedback and influence between songs in recommender system and model it as Markov decision process. Then we design a novel reinforcement learning framework RLWRec to generate music playlist. Moreover, we propose the state compression method based on collaborative filter

Fig. 1 .

 1 Fig. 1. Model recommender system as MDP.

Fig. 2 .

 2 Fig. 2. Recommendation strategy based on tree structure.

Fig. 3 .

 3 Fig. 3. Performance comparisons on three datasets

Fig. 6 .

 6 Fig. 4. Performance on different frequency

  Song Clustering In the song clustering process, we transform songs to feature vector of k + k dimensions consisting of user's feedback feature and song's own feature. User's feedback feature has k dimensions, which are top k similar users' performance (0: never listened, 1: listened, 2: collected, 3: downloaded) for the song. Song's own feature has k dimensions, including singer, release time, popularity, language, gender and so on. Consequently, we use k-means for clustering, resulting in N song clusters.RLWRec adopts state compression based on collaborative filter, consisting of user clustering and song clustering, transforms |M | songs to N song clusters (N << |M |). Thus, song clusters can replace songs to construct state space in modeling and training, which tend to immensely reduce the size of state space.

for the dimensionality reduction and design a recommendation strategy based on tree structure to improve the accuracy and coverage of recommendation. Experiments on real datasets verifies the effectiveness of our model.


Kai Zhang
email: zhangkai8816@foxmail.com

Xuan Geng
email: xuangeng@shmtu.edu.cn

Power control in D2D network based on Game Theory

Keywords: D2D, Nash equilibrium, power control, game theory

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With the requirement for high speed and efficiency of data transmission, the limited spectrum resource brings great challenges for mobile network communication. D2D communication is a new wireless technology, where two devices can communicate with each other without exchanging information from base station, so that it cannot only reduce the burden of base station, but also improve communication quality of cellular users [START_REF] Fodor | Design aspects of network assited device-to-device communications[END_REF]. However, the D2D users will be suffered from interference of other users in cellular system. Therefore, the interference elimination has been investigated in recent years [START_REF] Doppler | Device-to-Device communication as an underly to LTE-advance networks[END_REF].

In [START_REF] Yu | Device-to-device communication underlaying cellular communications systems[END_REF], the authors studied that the D2D users and the cellular users use the same channel resources by multiplexed mode. Although it can improve spectrum utilization, it will introduce a new kind of interference. The authors in [START_REF] Yu | Power optimization of device-to-device communication underlaying cellular communication[END_REF] investigated a power control method for single cellular system containing one cellular link and one D2D link. The algorithm can reduce the interference significantly between D2D users and cellular users. In [START_REF] Belleschi | Performance analysis of a distributed resource allocation scheme for D2D communications[END_REF], the authors studied the interference elimination problem of multi-cell D2D network, where the cellular users are communicated by base station schedule and the D2D link communication is guaranteed by power control.

The previous work mainly focused on the centralized power control method for D2D network, while the distributed implementation is less concerned. Therefore, we studied distributed power control method in this paper by use of game theory. We first establish a static game model in hybrid multi-cell D2D network, and then prove the existence and uniqueness of the Nash equilibrium. Finally, the distributed power control method is iteratively implemented to obtain the optimal state of Nash equilibrium. Simulation results show that the game model designed in this paper can converge quickly to Nash equilibrium, and the system can get better balance by adjusting the residual energy factor.

2

System Model

The system model of D2D network is shown in Figure 1. We consider a multi-cell system containing D2D links, and the adjacent cells use the same frequency band for multiplexing communication. Assume there are N cellular and D2D links in the sys- tem to use the same frequency resource. To eliminate the co-channel interference among the different cellular links and the interference between the cellular links and the D2D links, we propose a power control method based on game theory with pricing mechanism. (2) Strategy: Assume one communication link is denoted by jN  , where the trans- mit power is j j P p  . Here j P is the available transmit power region of the link j , i.e. the strategy space of the game player. All the strategies constitute

  2 2 1, , log |1 | j j j j j j j j j N kk k k j hp u p p h p hp          
, where j u is the utility func- tion of user j and it represents the payoff obtained by the game players after making decision. j h is the channel gain of the link j and 2

 is the variance of the additive white Gaussian noise. Unlike [START_REF] Hua-Liang | Non-cooperative game power control method in D2D network[END_REF], we introduce a user residual energy factor  in the utility function, which is defined as

max / jj EE   (1)
where j E  is the residual energy transmitted by link j , and its maximum valve is max j E . The energy factor  describes a price law. On one hand, when the supply ex- ceeds the demand, the payment for the price of energy consumption is low and the user can consume more energy to obtain better performance. On the other hand, when the demand exceeds supply, the energy consumption should pay more prices. Therefore, adjusting  can make the performance and energy consumption in a reasonable trade- off state. Note that  is regarded as a control factor in the simulation.

Here we formulate the problem to establish a non-cooperative power control game model with pricing mechanism, which is

  max , , jj j j j pP u p p j N    (2)
In this paper, we use Nash equilibrium to solve the problem. We define the policy combination  

N j P p p p u p p u j j j j j j j j       , ), , ( ) , ( * * * (3)
If the game players adopt the strategy combination * p , they cannot leave and change the strategy combination, so that the Nash equilibrium will be the optimal solution.

Non-cooperative Power Control Game Analysis

According to the model in eq.( 2) , we prove the existence and uniqueness of Nash equilibrium in this section. After that, we use a distributed iterative power algorithm to solve the Nash equilibrium point.

Existence

j j j j j jj N j k k j j j k k j u p p h h p h p h p                      (4)
Therefore, ( , ) j j j u p p  is quasi-concave for j p of the j th player [7]. Accord- ing to the game existence theorem in [START_REF] Glecksberg | A further generalization of the kakutani fixed point theorem with application to Nash points points[END_REF], the game G has Nash equilibrium.

Uniqueness

Theorem 2: The iterative game algorithm can converge to the unique equilibrium point.

Proof: If we want to prove there is Nash equilibrium point in the game, the iterative function should meet the positive   0 rp , monotonic    

All the players   jj rp  form the vector as , 20

            1 1 2 2 , , , , , j j N
j j j jj j j j N j k k j j j k k j u p p h ph p h p h p             (7)
and we obtain

  2 22 ~~1, 1, 2 2 NN k k k k j j k k j k k j j j j jj h p h p h p p p h                             (Negative solution) (8)
Therefore, the optimal response strategy is

The optimal response strategy vector is rp . If all the elements of a vector are not less than the corresponding elements of another vector, the former one will be greater than or equal to the latter vector.

          * * * 1 1 2
(2) Monotonicity:

If ' pp  , then     ' r p r p  . Proof: If ' pp  , then 2 2 ' 1, 1, NN k k k k k k j k k j h p h p          (11) Let 2 1, N kk k k j x h p     , we have 2 2 () 2 jj jj x x h fx h       (12) and obtain 2 ( ) 1 1 0 22 2 j j j j jj df x x dx h h xh        (13)
The function is a monotonically decreasing function, i.e.     ' r p r p  , so that the optimal response strategy vector satisfies the monotonicity.

(3) Extensibility:

If 1 T , then     1 r Tp r p T  . Proof: We have   2 2 2 ~1, 1, 2 2 N N k k k k j j k k j k k j j j jj T h p T h p h p Tp h                              (14)   2 2 2 ~1, 1, 2 1 1 2 N N k k k k j j k k j k k j jj jj h p h p h T T h                              (15) so that     2 2 2 ~1, 1, ~2 2 2 1, 1, 2 1 2 N N k k k k j j k k j k k j j j N N j j k k k k j j k k j k k j T h p T h p h p Tp T pp h p h p h T                                                         2 2 2 1, 1, 2 2 2 1, 1, 2 1 2 N
N k k k k j j k k j k k j N N k k k k j j k k j k k j h p h p h T T h p T h p h                                                   (16)
and we obtain

    1 r Tp r p T  (17)
It means that the optimal response strategy vector can be extended.

According to the Ref. [START_REF] Sung | A generalized framework for distributed power control in wireless networks[END_REF], we can conclude that the non-cooperative power control game has a unique Nash equilibrium point, which can be simply expressed by

        * * * 1 1 2 2 , , , NN p p p p p p p     (18)

Distributed iterative game algorithm

Based on the proofs in section 3.2, we present a distributed iterative algorithm to solve the Nash equilibrium. The realization is summarized below.

Step 1: Define the number of iteration M , and the stop criteria

U . Set 0 m  .
Set the initial value of the strategy combination Update the strategy via Eq.( 9) to obtain new strategy Note that the players only know their own channel gain j h and the corresponding energy factor j  when the Nash equilibrium point is calculated, so that the algorithm is implemented by distributed way.

Simulation Results

In this section, we perform the proposed non-cooperative power control game algorithm in D2D network by matlab simulation. The wireless system in simulation composes four cells 14 cc , and each cell has single cellular link and single D2D link, so that 8  N . The game player set is expressed as

  8 , 2 1  , ,  N
. Assume all the links use the same frequency band. The link gains j h of the four cellular links are as- sumed to be 0.5, 0.7, 0.9, 1.1, and the other four D2D links gains are 1.2, 1.6, 2.0, 2. The variance of additive white Gaussian noise is unit. The maximum transmit power max p of the D2D link and the cellular link is also unit. The compared algorithm comes from Ref [START_REF] Sung | A generalized framework for distributed power control in wireless networks[END_REF].

Figure 2 shows the valves of utility function varied with the iteration number. The control factor is set to be 2. Note the control factor in Ref [START_REF] Sung | A generalized framework for distributed power control in wireless networks[END_REF] represents power coefficient. From the simulation, it can be seen that our algorithm converges to the stable state within six times, while the compared algorithm in Ref [START_REF] Sung | A generalized framework for distributed power control in wireless networks[END_REF] needs eight times. Therefore, our method can converge more quickly than the compared one. Besides, we find that the valve of utility function of our method is bigger than the compared method, which means our method is more stable. 4 gives the transmit power results for all of users in Nash equilibrium state. It observed that all of transmit power of users tend to be stable. Hence the proposed price function can make the system achieve the equilibrium stable state.

NE transmit power

From the simulations, we conclude that the power control algorithm based on pricing mechanism can effectively improve the performance of the system if pricing factor is adjusted reasonably.

Conclusion

In this paper, we investigate the power control problem in D2D network. A non-cooperative game model based on pricing mechanism is established to eliminate the interference in complex environment. We design a price function and prove its existence and uniqueness, and then propose a distributed iterative algorithm which can converge to Nash Equilibrium point. From the simulation, it can be observed that our algorithm improve the system performance compared with the conventional method.

Fig. 1 .

 1 Fig. 1. D2D network system model

  rpis the optimal response strategy set.Given the strategies j p  , the optimal response strategy set of game players is

p

   , then   0

Fig. 2 .

 2 Fig. 2. Utility function value comparison for two algorithms

Fig. 3 .

 3 Fig. 3. Comparison of iteration number for two algorithms

Figure

  Figure4gives the transmit power results for all of users in Nash equilibrium state. It observed that all of transmit power of users tend to be stable. Hence the proposed price function can make the system achieve the equilibrium stable state.

Fig. 4 .

 4 Fig. 4. Transmit power of each user in Nash equilibrium

Acknowledgement. This work was supported by the National Nature Science Foundation of China (No. 61401270, 61601283).


Yang Yadong
email: yangyadong03@stu.shmtu.edu.cn

Wang Xiaofeng

Improved CNN based on Super-pixel Segmentation

Keywords: convolutional neural network, super-pixel segmentation, superpixel average pooling, super-pixel max pooling, super-pixel smooth pooling

Convolutional neural network has unique superiority in images processing, it can effectively extract features and reduce data dimensions by convolution and pooling. But it takes the "violent segmentation" method in the process of pooling. This method cannot guarantee the final selected pixel value can be a good representative of the partial features, neither average pooling nor max pooling. Therefore, three pooling methods based on super-pixel segmentation are proposed, called "super-pixel average pooling", "super-pixel max pooling" and "super-pixel smooth pooling". Firstly, the super-pixel segmentation is performed on the feature images, and then the value of the point which has the smoothest gradient in each super pixel is selected to represent the feature of the local area. Compared to the violent segmentation pooling operation, this method exhibits more stable characterization ability, it can retain image features perfectly while reduce the data dimensions. Experiments show that the improved convolutional neural network achieved better results than normal algorithm in the standard data sets.

Introduction

Convolutional neural network (CNN) is a deep neural network model with convolution structure. It can effectively reduce the number of weights and lower the complexity of the network. This model has some invariance for scaling and other forms of deformation. Each neuron only needs to perceive the local image area, The network obtain global information by combining these neurons that perceive different local regions at higher levels. In 1989, LeCun Y et al. proposed a CNN model "LeNet-5 [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] " for character recognition. LeNet-5 consists of convolutional layers, sub-sampling layers and fully connected layers. The system achieves good results in small-scale handwritten numeral recognition. In the ImageNet contest, "AlexNet [START_REF] Krizhevsky | ImageNet classi-fication with deep convolutional neural networks[END_REF] ", a new network architecture of CNN, designed by Krizhevsky et al. won the 2012 championship. AlexNet and OverFeat [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF] are quite powerful CNN models trained on large natural image datasets. By improving the network performance, Girshick R et al. proposed R-CNN [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF] (Regions with CNN) can complete the target detection task effectively. He K M utilize spatial pyramid pool-ing (SPP) to deal with different size and aspect ratio of the input images, this new network called SPP-Net [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] . In recent years, more and more popular method to optimize CNN models is to develop deeper and more complex network structures, and then to train them with massive training data. VGG [START_REF] Szegedy | Going deeper with convolutions[END_REF] (visual geometry group), a 19-layer depth network, mainly explores the importance of depth for the network. GoogLeNet [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] is the particular incarnation for ILSVRC14 submit by Szegedy C et al., a 22 layers deep network, the quality of which is evaluated in classification and detection.In order to improve the performance of CNN, the researchers not only discuss the structure of CNN and its applications, but also improve the design of the network layers, the loss function, activation function, regular items and many other aspects of the existing network. They achieved a series of results, for example, Inception network [START_REF] Szegedy | Going deeper with convolutions[END_REF] , stochastic pooling, ReLU [START_REF] Krizhevsky | ImageNet classi-fication with deep convolutional neural networks[END_REF] , Leakly ReLU [START_REF] Maas | Rectier nonlinearities improve neural network acoustic models[END_REF] , Cross entropy loss, Batch normalization [START_REF] Ioffe | Batch normalization: accelerating deep network training by reducing internal covariate shift[END_REF] , etc.

2

Related work

Convolutional neural network

In a typical CNN model, the beginning layers are usually alternating between the convolution layer and the sub-sampling layer. The last few layers of the network near the output layer are usually fully connection networks. The four basic elements of CNN are convolutional layers, sub-sampling layers, all connected layers and back propagation (BP) algorithm.

The convolutional layers receive the input images or the feature maps from the previous layer, they carry out the convolution operation through the N convolution cores and activate operation using the activation function, then N new feature maps are generated and directed into the next sub-sampling layer. The function of convolution is defined by (1) where l denotes the convolution layer, j is the j-th channel, l j x is the output value from the j-th channel of convolution layer l, f(• ) is the activation function, M j represents the subset of feature maps, l ij k is the convolution kernel matrix, * is the convolution operation, l j b is offset of l. The sub-sampling layers perform sub-sampling operations on the input feature maps, which can effectively reduce the computational complexity and extract more representative local features. The function of sub-sampling is defined by (2) where l j  denotes is the sub-sampling weight coefficient, down(• ) is sub-sampling function.

) * ( 1      j M i l j l ij l i l j b k x f x ) ) ( ( 1 l j l j l j l j b x down f x    
The fully connected layers consist of an input layer, several hidden layers and an output layer. The upper layer's feature maps is spliced into one-dimensional vector as input data, and the final outputs is obtained by weighting and activating.

(3) where l  is the neural network weight.

The BP algorithm is a common neural network method in supervised learning. For the convolutional neural network, the main job is to optimization the convolution kernel parameters, the sub-sampling layers weights, the network weights of the full connection layer and the bias parameters of all layers. The essence of the BP algorithm is to allow us to calculate each network layer's effective errors and to derive the learning rules of network parameters, and then drive the actual network outputs are closer to the target values.

Super-pixel Segmentation

Super pixels are divided a pixel-level image into district-level image or sets of pixels by image segmentation. The goal of super pixel segmentation is to change or simplify the representation of an image into something that is more convenient and significant to analyze. The super pixel segmentation method has been under intensive study, now there are many super pixel segmentation algorithms.

Super pixels are obtained by using NCut [START_REF] Shi | Motion segmentation and tracking using normalized cuts[END_REF] and SLIC [START_REF] Jung | Bandwidth Allocation for Iterative Data-Dependent E-science Applications[END_REF] algorithm has a high compactness. Using SLIC and Watershed algorithm for ultra-pixel segmentation is very productive. But if you put more emphasis on edge accuracy and regional merging, you can choose Marker-based Watershed and Meanshift algorithm.

Improved CNN

CNN have been substantiated to provide a powerful approach for image processing. In this work, we focus on the pooling part of the CNN.

The common CNN pooling methods include average pooling, max pooling and multi-scale mixing pooling. These methods have achieved some good results, they calculate a value representing the local region feature in the pre-divided local area of feature maps. However, those violent segmentation methods have their own unreasonable place, including ignore some local features or neutralize some salient features. This paper presents three pooling methods based on super pixel segmentation. Firstly, take super-pixel segmentation action on the feature maps, and the pixel feature values in each local region (ie, super pixels) we got are similar. Then three kinds of pooling methods are come up with super pixel segmentation.

1) Calculate the average value of pixels within each super pixel called super pixel average pooling.

2) Get the max value of pixels within each super pixel, that is, super pixel max pooling.

) (

1 l l l l b x f x    
3) And super pixel smooth pooling trying to take the value of the point which has the smoothest gradient in each super pixel.

This paper only considers the super pixel level, does not deal with regional merger after image segmentation. Based on SLIC has the low time complexity and high compactness, we choose to use SLIC algorithm for super pixel segmentation.

Results

The structure of CNN we used in experiment for MNIST has 7 layers. The network is composed of 2 convolutional layers, 2 pooling layers and 3 fully connected layers. The experiment for CIFAR-10 use AlexNet. While the convolutional layers are followed by rectified linear operator (ReLU) layers and the pooling layers take the value of local regions with two-pixel strides, the dropout layers having a 0.5 dropout ratio. The last fully connected layer employ softmax function as a multi-class activation function.

Because of the MNIST data have relatively simple characteristics. Here divide the MNIST test set into six parts randomly, each part is transformed into different scales or angles, and then normalize the images in 28*28 pixels to get a new test set. The training set remains the same. Test on data sets MNIST, New MNIST.

Fig. 2. Part of the New MNIST test images

In the following tables: "max", "avg", "sps", "sp-max", "sp-avg" each representing max pooling CNN method, average pooling CNN method, super-pixel smooth pooling CNN method, super-pixel max pooling CNN method and super-pixel average pooling CNN method. The results are shown as follows. Based on the above results it can be seen that: the average pooling method is better than the max pooling methods, because of the local regions average values are more representative. Super-pixel pooling method is better than the standard pooling method, which is due to better image segmentation. The super pixel smooth pooling method gets the best results, because this method can find the most representative values.

Conclusions

A neoteric and universal approach is proposed for improving CNN performance through using the super-pixel pooling to train the network. This approach makes the models have more stable characterization and better generalization, and it can be used for different CNN network structures. Extensive experiments on several standard data sets for the image classification prove that using the super-pixel pooling in the training process can significantly enhance performance of CNN models, in comparison with the same model trained without employing this method.

The super-pixel segmentation technique may be further used for the convolution operation. By introducing the fuzzy segmentation method, adjust the number of extra pixels and the number of pixels per super-pixel contains after segmentation. This method

Fig. 1 .

 1 Fig. 1. The super-pixel pooling schematic diagram These segmentation methods can not only extract the necessary features, but also the local stability of the images has no destruction at all.

Table 1 . Test results of the five methods on the Mnist dataset.

 1

	Table

  suitable for convolution of large-size images, and convolution of image sets containing different sizes of images. Moreover, we can use the improved CNN to resolve many practical problems such as pedestrian detection, ship classification, text recognition or medical images processing.

	Methods	Training error(%)	Test error(%)
	max	0.01	0.8
	avg	0.06	0.9
	sps	0.04	0.7
	sp+max	0.05	0.8
	sp+avg	0.06	0.8
	Methods	Training error(%)	Test error(%)
	max	0.04	10.7
	avg	0.1	9.8
	sps	0.06	4.7
	sp+max	0.06	8.9
	sp+avg	0.08	6.6
	Methods	Training error(%)	Test error(%)
	max	2.67	29.5
	avg	12.50	28.8
	sps	5.65	24.2
	sp+max	6.54	26.4
	sp+avg	8.26	25.1

is


Shenyi Ding

Guangxiao Song

Zhijie Wang
email: wangzj@dhu.edu.cn

Transfer Learning for Music Genre Classification

Keywords: music genre classification, transfer learning, deep learning

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Music genre is important to many applications, such as music recommender system and information retrieval. Automatic genre classification system has been developed using machine learning technique recent years. Most of these systems have the ability of cataloguing different music genres from raw music contents [START_REF] Song | Content-based information fusion for semi-supervised music genre classification[END_REF][START_REF] Meng | Temporal feature integration for music genre classification[END_REF][START_REF] Lampropoulos | Music genre classification based on ensemble of signals produced by source separation methods[END_REF].

Mel-frequency cepstral coefficient (MFCC) and Mel-spectrogram are widely used in genre classification task. Because they can extract variant features from raw data for the learning process. But the performance of genre classification benefits from features over long-time scale (>500ms) while MFCC is efficient around time scale of 25ms, and enlarging the time scale leads the information loss when using mel-spectrogram [START_REF] Mcdermott | Sound texture perception via statistics of the auditory periphery: evidence from sound synthesis[END_REF][START_REF] Lee | Automatic music genre classification based on modulation spectral analysis of spectral and cepstral features[END_REF]. Differently, scattering transform can recover the information loss by wavelet decompositions, meanwhile, extract long-time scale features by lowpass filters [START_REF] Mallat | Group invariant scattering[END_REF][START_REF] Andén | Deep scattering spectrum[END_REF].

Deep learning makes massive of success in different areas, for instance, computer vision [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF], speech recognition [START_REF] Mohamed | Acoustic modeling using deep belief networks[END_REF][START_REF] Feng | Speech feature denoising and dereverberation via deep autoencoders for noisy reverberant speech recognition[END_REF], and natural language processing [START_REF] Sutskever | Generating text with recurrent neural networks[END_REF][START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. These algorithms can extract high-level features automatically layer by layer, different from traditional machine learning classifiers, such as Support Vector Machine (SVM), Nearest Neighbors, and Decision Trees, which are heavily dependent on the result of feature extraction. Among its several typical models, Recurrent Neural Network (RNN) is widely used for sequential data. And RNN is good at learning the relationship through time [START_REF] Hochreiter | Long short-term memory[END_REF]. But in purpose of achieving good performance, deep neural network needs large amount of data. In condition of the target dataset need to be classified is not enough, we can use a large data, which is the same or similar to the target dataset, to pre-train the deep neural network, then replace the connections to classifier according to the target classification number and fine-tune the parameters of the pre-trained network. This process is called transfer learning [START_REF] Pan | A survey on transfer learning[END_REF]. In this paper, we use Magnatagatune dataset [START_REF] Berenzweig | A large-scale evaluation of acoustic and subjective music-similarity measures[END_REF] and GTZAN dataset [START_REF] Tzanetakis | Musical genre classification of audio signals[END_REF] as the large and the target dataset respectively. 5-layer RNN using Gated Recurrent Unit (GRU) [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF] and softmax classifier are used. Additionally, for reducing the input of deep RNN, we use scattering transform as its preprocessing.

The results of the experiment show that the proposed 5-layer RNN reaches a high accuracy when using transfer learning, and the same architecture using random initialization converges more slowly to a lower accuracy.

Transfer Learning Process

The architecture of the proposed method is shown in Figure 1. The overall process consists of two parts. One part is deep RNN training on a large musical dataset (Magnatagatune dataset is used in this paper). The other part is genre classification process after fine-tuning the previous trained deep RNN by target dataset (GTZAN dataset is used in this paper). Specifically, scattering transform is applied at the beginning of each part, in order to reduce the raw music data and to extract features preliminarily for the next process of neural network training. 5-layer RNN with GRU and softmax classifier are trained with tagged music clips as the deep RNN we mentioned. At last, we use the target genre classification dataset (GTZAN) to fine-tune the trained parameters of RNN.

Scattering transform

In genre classification task, large time scale (>500ms) invariant signal representation is important. As widely used methods in audio processing, mel-spectrogram can enlarge the time scale but remove information which is crucial to genre For an audio signal x, scattering transform defined as S n x, where n represent the order. S 0 x = x φ(t) has locally invariant property because of the time averaging operation, but it leads to high frequency information loss which can be retrieved by the wavelet modulus coefficients |x ψ λ1 (t)|. To make the wavelet modulus coefficients invariant to translation, a time averaging is applied. The first layer of scattering transform defined as:

S 1 x(t, λ 1 ) = |x ψ λ1 | φ(t) (1)
J. Andén [START_REF] Andén | Deep scattering spectrum[END_REF] indicates that if wavelets filter-bank ψ λ1 have the same frequency resolution as the mel-windows, then S 1 x coefficients can be approximate to the mel-filter-banks coefficients. The difference is that applying a bank of higher frequency wavelet filters ψ λ2 with a modulus to the wavelet modulus coefficients can recover the lost information. The same as previous operation, adding a lowpass filter φ(t) make the coefficients translation invariant. Then the second layer of scattering transform defined as:

S 2 x(t, λ 1 , λ 2 ) = ||x ψ λ1 | ψ λ2 | φ(t) (2)

Deep Recurrent Neural Network

RNNs have an aptitude for handling sequential information, such as speech recognition and NLP. RNN structure can be described as transitions from previous to current states. For classical RNN, this transition is formulized as:

h t = f (W h [x t , h t-1 ] + b h ) (3)
In order to solve the problem of vanishing gradients of RNN. Gated structure named LSTM introduced by Hochreiter [START_REF] Hochreiter | Long short-term memory[END_REF]. The LSTM unit allows that information of more timesteps can be memorized. And the memories are stored by memory cells. Then the LSTM can decide to forget, output, or change the saved memories. As a popular variant of LSTM, GRU is simpler and effective as well. It uses gate Zt and gate Rt to update the hidden state. Theses gates are given by:

z t r t = σ(W z [x t , h t-1 ] + b z ) σ(W r [x t , h t-1 ] + b r ) g t = f (W g [x t , r t * h t-1 ] + b g ) h t = (1 -z t ) * h t-1 + z t * g t (4)
We use 5-layer GRU neural network which is constructed by stacking each hidden layer on the top of previous layer, in order to improve the ability of representation of our architecture in this paper. Additionally, generalization of the proposed deep RNN is improved by applying dropout between each layer [START_REF] Zaremba | Recurrent neural network regularization[END_REF].

Datasets and Experiment Setup

Magnatagatune and GTZAN dataset are used as the large and target dataset respectively. All the clips are transformed to mono and sampled by 16kHZ. Magnatagatune has 25863 clips and each clip is annotated with 188 different musical tags such as genre, mood, and instrument. We use the last 2105 clips (distributed in folder 'f') for validation, others for training. We use 512 hidden states in each layer. Dropout is set as 0.7. Learning rate is 0.00001. And we use AUC-ROC score [START_REF] Davis | The relationship between precision-recall and roc curves[END_REF] to evaluate the performance of our model to avoid imbalance of the dataset. When the AUC-ROC score is stable, we stop the training and save the model. GTZAN dataset has 1000 clips of 10 genres and each genre contains 100 clips evenly. As the target dataset, it is randomly shuffled and the mean accuracy of 10 times of 10-fold cross validation is used for the final test accuracy. Among the 10 folds in total, we use 1 fold for testing, and the others for training. Each time of 10-fold cross validation, we change the output number of the softmax classifier to 10 (the genre number of GTZAN dataset), then fine-tune the parameters of pre-trained model from Magnatagatune dataset.

Experiment Results and Analysis

As shown in fig. 3, both random initialization and transfer learning models (pretraining process is shown in fig. 2) of 5-layer RNN with GRU using scattering transform preprocessing converge to quite high accuracy in training. And the models using transfer learning need about 100 epochs to be stable. But the random initialed models need more. This phenomenon not only appears in the three random picked training processes, but also in the unpicked to be shown. It indicates that the transfer learning initials the model better, and improves the speed of convergence.

Comparing with other works of recent years in Tab. 1, our approach shows a competitive accuracy (95.8%) in genre classification task on GTZAN dataset. Even the model using random initialization can also reach a high accuracy (93.5%) relatively. The combination of scattering transform and deep RNN has been evaluated, and by using this architecture, it performs well in music genre classification.

Conclusion

In this paper, we use transfer learning in music genre classification by using 5-layer RNN with GRU and scattering coefficients as its input. When applying the transfer learning from a large music dataset (Magnatagatune is used in this paper), our model shows a faster convergence and higher average accuracy than the same model of random initialization on the target dataset (GTZAN is used in this paper). And the accuracy of transfer learning approach is competitive comparing with the state-of-the-art models as well. The effectiveness of deep RNN combined with scattering transform and transfer learning has been verified in music genre classification task.

Fig. 1 .

 1 Fig. 1. The architecture of the proposed transfer learning process

Fig. 2 .

 2 Fig. 2. Validation AUC-ROC score of 5-layer GRU neural network using scattering transformed input

Fig. 3 .

 3 Fig. 3. Three random picked training processes of 10-cross validation, Blue lines represent the RNN using random initialization, and the orange lines represent the RNN using transfer learning. And the accuracy is tested by a random batch of training data

Table 1 .

 1 Average test accuracy of different models on GTZAN dataset

	Model	Average test accuracy
	Panagakis and Kotropoulos [22] 92.4%
	Andén and Mallat [7] 91.6%
	Lee, Shih and Yu [5] 90.6%
	Dai and Liu [23] 93.4%
	Random initialization 93.5%
	Transfer learning 95.8%

6 Acknowledgements This work was supported by the National Natural Science Foundation of China (Grants nos. 11572084, 11472061, 71371046), the Fundamental Research Funds for the Central Universities and DHU Distinguished Young Professor Program (No.16D210404).