DATA-DRIVEN DECISION MAKING IN SPATIAL TEMPORAL TASKS

Abstract

With the emerging of pervasive data-collecting technologies and devices, we are collecting a large amount of data to describe human society and nature, e.g., human mobility, water quality, and climate change. Recently, people have been working on revealing the underlying patterns contained in the data, and predicting the future trends of the data. Though these studies may provide important insights of the situations that people are facing, they cannot provide actionable policies to change the situation. For instance, traffic-related problems in metropolitan cities, e.g., traffic demand prediction and traffic congestion, have been intensively investigated both in data mining and transportation communities. However, given the known congestion and demand-supply mismatch, a meaningful question is to investigate how to take actions to mitigate the congestion and fulfill the demand. We call these problems decision-making problems.

Making decisions has been a heated research area in different domains. For instance, in the transportation domain, people have applied methods from transportation engineering and control theories to control the traffic signals. These methods assume the arrivals of vehicles follow some pre-defined traffic models, and convert the decision problem to an optimization problem. However, these simplified assumptions might deviate from the real-world data observations, and hence lead to sub-optimal decisions. Recently, reinforcement learning approaches achieve great success in the decision-making problems in virtual environments, e.g., Go game and Atari game. They directly learn from the data via a trial-and-error search. However, these methods require a decent number of interactions with the environment before the algorithms converge. In real-world problems, every interaction means real cost (e.g., traffic congestion, traffic accidents). Hence, a more data-efficient method is necessary for use in the real world.

In this dissertation, I will show the four stages along the pipeline of data-driven decision making, including identifying a problem (e.g., traffic congestion, environmental pollution), objective design, learning a policy (e.g., traffic signal control policy), and transferring policies to the real world. I have developed innovative solid techniques to tackle the tasks in each stage. In addition, I have applied the developed methods in different domains, including urban traffic prediction, traffic signal control, news recommendation, and pollution detection and control. We have achieved significant improvement over the state-of-the-art or currently employed methods, which will provide us with promising solutions to improve real-world situations.

 

Chapter 1 | Introduction – Data-driven Decision Making

1.1 Making Decisions from Data

With the prevalence of various data-collecting devices and services, our life is being recorded by massive data every day. For instance, human mobility data and social media posts can vividly describe what is happening in the cities. Recent data mining and machine learning research have made significant progress on utilizing the big data to yield insightful observations (e.g., traffic anomaly detection, POI clustering), and predict unknown variables (e.g., traffic prediction). Here, we use two examples of environmental data and traffic data to show how big data can serve the aforementioned two functions (i.e., yielding insightful observations and predicting unknown variables).

Example 1.1.1. The improvements in extraction technologies have stimulated fast development in the energy industry. In recent years, shale gas is becoming an important energy source in the United States. However, one of the major extraction technology for shale gas, high volume hydraulic fracturing, i.e., “fracking”, has caused controversy about potential impacts on greenhouse gas emissions and water quality. Specifically, people are concerned whether the fracking activity will allow the escape of methane into surface and ground waters, which may affect the quality of homeowner wells and accelerate global warming.

Motivated by this real-world environmental concern, we can develop data mining techniques to discover the underlying patterns of the water quality samples and detect the anomalous samples. Given a dataset of 1,645 water quality analyses for groundwaters sampled in one county in Pennsylvania, we have developed a spatial anomaly detection techniques to detect the water samples with abnormally high methane values. This technique has successfully found water samples that are believed to be related to methane leakage according to the geoscientists.

Example 1.1.2. Traffic congestions have slowed down the speed of city development and caused large economic loss. People have made many efforts in understanding the cause of traffic jams and predicting traffic demand using historical traffic and environmental features (e.g., POI, road network). These studies can help people accurately project future traffic and take action accordingly.

As discussed by [3] , these studies enable people to better describe the faced problems or conduct accurate future predictions. They are referred to as descriptive tasks and predictive tasks respectively (as shown in Figure 1.1). However, these problems will not be solved until real actions are executed. Therefore, in this dissertation, I propose to take one further step to learn a solution (i.e., a prescriptive task) that can improve the current situation to a desired one (e.g., mitigate traffic congestion).

Mathematically, suppose we have observed some data from the real world represented as X. The descriptive tasks propose to describe the data distribution P(X). The prediction tasks use X as features to predict unknown variables Y . In contrast, the prescriptive tasks aim to find a solution a that can change the current situation (represented as X) to a more desirable situation (represented as X⁰).

 

1

 Descriptive tasks              

2

 Predictive tasks            

3

 Prescriptive tasks

Observations X ! P(X) Traffic anomaly detection < latexit sha1_base64=”8KcjPK43O8SIrEqj6ij5PEsvSE8=”>AAAB+3icbVBNT8JAEJ3iF+JXxaOXjcQEL6RFEz0SvXjERKAJNGS7bGHDdtvsblXS8Fe8eNAYr/4Rb/4bF+hBwZdM8vLeTGbmBQlnSjvOt1VYW9/Y3Cpul3Z29/YP7MNyW8WpJLRFYh5LL8CKciZoSzPNqZdIiqOA004wvpn5nQcqFYvFvZ4k1I/wULCQEayN1LfLHupJNhxpLGX8iJpV76xvV5yaMwdaJW5OKpCj2be/eoOYpBEVmnCsVNd1Eu1nWGpGOJ2WeqmiCSZjPKRdQwWOqPKz+e1TdGqUAQpjaUpoNFd/T2Q4UmoSBaYzwnqklr2Z+J/XTXV45WdMJKmmgiwWhSlHOkazINCASUo0nxiCiWTmVkRGWGKiTVwlE4K7/PIqaddr7nmtfndRaVzncRThGE6gCi5cQgNuoQktIPAEz/AKb9bUerHerY9Fa8HKZ47gD6zPH8A2k5k=</latexit > Water pollution discovery

Predictions X Y Traffic prediction! Crime inference

Solutions X,X0 ! a Traffic signal control < latexit sha1_base64=”vQaMX4dYBMmKfM+b39IblWGi4m4=”>AAAB/HicbVBNS8NAEJ3Ur1q/oj16WSyiBylJFfRY9OKxgm0DbSib7bZdutmE3Y0SQv0rXjwo4tUf4s1/47bNQVsfDDzem2FmXhBzprTjfFuFldW19Y3iZmlre2d3z94/aKkokYQ2ScQj6QVYUc4EbWqmOfViSXEYcNoOxjdTv/1ApWKRuNdpTP0QDwUbMIK1kXp22TtD3gnqSjYcaSxl9Ihwz644VWcGtEzcnFQgR6Nnf3X7EUlCKjThWKmO68Taz7DUjHA6KXUTRWNMxnhIO4YKHFLlZ7PjJ+jYKH00iKQpodFM/T2R4VCpNAxMZ4j1SC16U/E/r5PowZWfMREnmgoyXzRIONIRmiaB+kxSonlqCCaSmVsRGWGJiTZ5lUwI7uLLy6RVq7rn1drdRaV+ncdRhEM4glNw4RLqcAsNaAKBFJ7hFd6sJ+vFerc+5q0FK58pwx9Ynz8u/ZPW</latexit >

Figure 1.1: Three different stages of investigating a problem.

We use the following example to illustrate what is a prescriptive task.

Example 1.1.3. One major reason for the traffic congestion in the city is the unintelligent traffic signal. Currently, the most widely used traffic signal control methods are still based on predefined timing plans, or fixed rules derived from expert experience. These signal control policies will not adjust according to the traffic need. Hence, we propose to learn a traffic signal policy from the data that can adapt correspondingly to the changing traffic (e.g., find a traffic signal policy that can speed up the traffic the most).

I propose to learn the decisions (i.e., policies) from data due to the following motivations:

• Making decisions from data does not require any assumption. _{Traditional decision-}

making process usually makes strong assumptions to simplify the problem. For instance, traditional traffic signal control methods assume a fixed traffic model (i.e., how vehicles arrive and run on the roads) and convert the signal control problem into a static optimization. The signal control policies optimized under this assumption can not reach optimal under dynamic traffic. In contrast, directly learning the decisions from data does not rely on any assumption, and hence will be more generic and robust (e.g., data-driven signal policies can apply to different traffic).

• The policies learned from data can be updated in time automatically. _{For instance,} the traffic situations in the real world are changing rapidly w.r.t. time. Therefore, it is important that the policies can adjust correspondingly. Compared with traditional decision-making strategies, data-driven decision making can update in real time by training the policy with data continuously.

1.2 Challenges

Generally, data-driven decision-making problems have the following three challenges.

• The way of discovering problems from domain-specific data varies among datasets. Before making the decision, we first need to discover the problems that are highlighted by the data (e.g., polluted water quality samples, traffic congestion in certain areas). However, data in different domains have significantly different meanings and formats. It is challenging to come up with a universal way to reveal the problem under these data.
• Setting a proper objective for decision-making problems can be tricky. In real-world problems, the evaluation metrics for improving a situation or solving a problem can be diverse. For instance, people use different measurements to evaluate traffic congestion, e.g., travel time, waiting time, and the number of stops. However, in order to learn the best policy, a proper objective has to be chosen from these measurements (or the combination of them). In addition, in some cases, although certain measurement can serve as the objective, it can not directly guide policy learning. For instance, travel time is a good measurement for traffic congestion, while it is an aggregated effect of several consecutive traffic signal operations. Therefore, it is difficult to use travel time to directly provide feedback to each traffic signal operation.
• Deploying decisions will induce cost in the real world. Hence, the developed method needs to learn better decisions while keeping the cost low during the learning process. This requires the developed method to learn from as few data samples as possible.

1.3 Overview

1 Identify a problem Descriptive tasks Predictive tasks

Objective design 2 Extract proper objective from domain problems

Develop a policy 3 Learn policies from simulation and offline data

4 Transfer policies to the real world Minimize the gap between simulator and real world

Figure 1.2: The pipeline of data-driven decision making.

In view of the aforementioned goal and challenges, I will introduce the data-driven decision making in the following four steps as shown in Figure 1.2.

• Identify a problem. The first step before making decisions is to identify the problem. This step covers the descriptive tasks and predictive tasks discussed before. In Chapter 2, we use one example of discovering spatial anomalies to show how to identify a problem from data. We develop a general anomaly detection method that can apply to diverse domains and datasets.
• Objective design. Given the identified problem, we aim to set an appropriate objective, which can be directly optimized by data-driven decision-making methods (e.g., reinforcement learning). In Chapter 3, we use an example in traffic signal control to illustrate the importance of objective design. A correct objective with theory guidance will guarantee the data-driven methods to obtain good policies.
• Develop a policy. Given the carefully designed objective, we aim to learn a policy from data to optimize the objective (in Chapter 4). This process requires the environment (either real world or a simulator) to provide feedback for each action, so that the algorithm can learn to choose the best actions. The large exploration space (i.e., combinations of state and action values) makes this problem challenging. We incorporate the domain knowledge to reduce the exploration space which enables the algorithm to converge with much fewer trials. This means much less data and lower real-world cost.
• Transfer policies to the real world. Due to the high risk and cost of learning the policy in the real world, policy-learning tasks are usually conducted in a simulator. Hence, in order to make the policy learned in simulators directly applicable to the real world, the simulator should be similar to the real world (e.g., actions will have similar effects in the simulator and the real world). Therefore, in Chapter 5, we propose a learning-to-simulate technique to learn a traffic simulator that produces driving behaviors close to the real world. This simulator will make it possible for the learned traffic policies to transfer to the real world with low cost (i.e., less traffic congestion).

In the end, I will discuss some possible future work.

DATA-DRIVEN DECISION MAKING IN SPATIAL TEMPORAL TASKS

Sharing is caring!