ABSTRACT
There is a rapid intertwining of sensors and mobile devices into the fabric of our lives. This has resulted in unprecedented growth in the number of observations from the physical and social worlds reported in the cyber world. Sensing and computational components embedded in the physical world constitute a Cyber-Physical System (CPS). Current science of CPS is yet to effectively integrate citizen observations in CPS analysis. We demonstrate the role of citizen observations in CPS and propose a novel approach to perform a holistic analysis of machine and citizen sensor observations. Specifically, we demonstrate the complementary, corroborative, and timely aspects of citizen sensor observations compared to machine sensor observations in Physical-Cyber-Social (PCS) Systems.
Physical processes are inherently complex and embody uncertainties. They manifest as machine and citizen sensor observations in PCS Systems. We propose a generic framework to move from observations to decision-making and actions in PCS systems consisting of: (a) PCS event extraction, (b) PCS event understanding, and (c) PCS action recommendation. We demonstrate the role of Probabilistic Graphical Models (PGMs) as a unified framework to deal with uncertainty, complexity, and dynamism that help translate observations into actions. Data driven approaches alone are not guaranteed to be able to synthesize PGMs reflecting real-world dependencies accurately. To overcome this limitation, we propose to empower PGMs using the declarative domain knowledge.
Specifically, we propose four techniques: (a) Automatic creation of massive training data for Conditional Random Fields (CRFs) using domain knowledge of entities used in PCS event extraction, (b) Bayesian Network structure refinement using causal knowledge from Concept Net used in PCS event understanding, (c) knowledge-driven piecewise linear approximation of nonlinear time series dynamics using Linear Dynamical Systems (LDS) used in PCS event understanding, and (d) transforming knowledge of goals and actions into a Markov Decision Process (MDP) model used in PCS action recommendation. We evaluate the benefits of the proposed techniques on real-world applications involving traffic analytics and Internet of Things (IoT).
RELATED WORK
We summarize the related research thrusts under three topics: (a) event extraction in Physical- Cyber-Social Systems (PCS), (b) event understanding in PCS, and (c) action recommendation in PCS.
Event Extraction in PCS
There are two orthogonal factors that influence the event extraction techniques: formal/informal text and open/closed domain nature of events. For both formal and informal textual data, we organize the related work into (a) open domain event extraction, where, the types of events are not known a priori and (b) closed domain event extraction, where, the types of events are known a priori.
PROBABILISTIC GRAPHICAL MODELS
Figure 3.1: Dependencies (or independences) captured by a Bayesian Network for estimating the risk of asthma attacks
Formally, a BN is a directed acyclic graph (DAG) with nodes representing random variables and edges representing dependencies (or independences) between them. The parameters of a BN is specified using a conditional probability table (CPT) for discrete random variables. For continuous random variables, the parameters are specified using a conditional probability distribution (CPD). Figure 3.1 contains parameters of the BN in the form of CPTs. The values in the CPTs of Figure 3.1 are for demonstration purposes only and this can be gleaned from real-wold data if available.
Figure 3.3: A Conditional Random Field (CRF) model with observed variables X and the target variables Y
Conditional Random Fields (CRFs) have been extensively used in text processing specifically for part-of-speech tagging and named entity recognition. CRFs are a type of undirected probabilistic graphical models containing two types of variables; observed variables denoted by X and the target variables denoted by Y. The nodes in the CRF graph corresponds to X∪Y. A CRF models the conditional distribution p (Y|X) factorizing over the graph shown in Figure 3.3. A CRF model does not allow the probability distribution over the observed variables X alone.
Figure 3.5: A Linear Dynamical System for T time points with hidden nodes h1:T and observed nodes s1:T.
Linear Dynamical Systems (LDS), also known as Kalman Filters in the context of signal processing, are widely utilized in applications spanning astronomy, physics, control systems, econometric system modeling, surveillance, and object tracking. Time series data with hidden and observed variables naturally occur in these domains. A LDS model incorporates both hidden and observed variables as shown in Figure 3.5 with T hidden nodes h1:T and T observed nodes s1:T respectively for modeling observations at T time points.
EVENT EXTRACTION
Figure 4.1: Relationship between components of OODA-loop and components of PCS-Analytic framework
As explained earlier in the introduction, PCS event extraction aligns with the observe step of OODA-loop as shown in Figure 4.1. We address the following research questions in this chapter: How do we extract city traffic infrastructure related events from tweets? How can we exploit event and location knowledge-bases for event extraction? How well can we extract city traffic events? How can we extract traffic related events from SMS messages?
Figure 4.6: Architecture for extracting city infrastructure related events from social stream such as tweets
The tweet processing pipeline is shown in Figure 4.6 and the details of each solution component is presented here. Location and time are crucial components for city related event extraction. We are exploiting spatio-temporal context/coherence for city event extraction from informal text.
Figure 4.19: System architecture with event extraction and reasoning components
Figure 4.19 depicts the overall system architecture of the multimodal dynamic update system. We use the SMSGupShup API 15 to get all the SMS alerts on an hourly basis (setup as a cron job). For each message, we extract the event related metadata – location (from,to,on), time, and event (type). Event metadata such as location name and time are used to find the affected stops using stop names and trip information. Trip information is time stamped route for a public transport vehicle and it has a direction.
EVENT UNDERSTANDING
Figure 5.5: City traffic events (textual data) used to explain anomalies in traffic dynamics (sensor data)
For every city traffic event collected from textual data, we detect anomalies in traffic pattern as outlined in Figure 5.5. We examine the city traffic events using their location, start time, and end time. Based on the location of the event, we select links within a radius r km from the event. We run the anomaly detection step on the temporally selected data points from these links. If an event from the textual stream has a corresponding anomaly in the link data, we hypothesize that the event explains the anomaly and the anomaly is explained by the event.
Figure 5.9: Top part of the figure depicts the structure extracted from traffic observations and the bottom part has the enriched structure (using declarative knowledge)
Figure 5.9 shows the structure extracted using observations 〈Os ,Ov ,Ot ,Ea ,Es, D week, T day, O delay〉 timestamp. There are undirected links which need to be converted to directed links before the parameters are learned. We explored many structure extraction approaches including constraint-based, score-based, and hybrid algorithms. Constraint-based learning algorithms verify the conditional independence between variables with ideas derived from. Score-based learning algorithms evaluate the structure and compute the goodness-of-fit score.
ACTION RECOMMENDATION
Figure 6.2: Architecture for the Action Recommendation Engine
A task recommendation engine should be able to provide an optimal action to the user based on the available resources and known user skills. We need three important components to develop a task recommendation engine as shown in Figure 6.2: i) A language to represent tasks. ii) An algorithm to recommend optimal action. iii) An evaluation environment for task recommendation.
The task store in Figure 6.2 contains tasks represented in machine readable and interchangeable format. Semantic web technologies provide standards for knowledge representation such as Resource Description Framework (RDF), RDF Schema (RDFS), and Web Ontology Language (OWL). We utilize RDFS description for representing tasks. Given a user goal, G, task representation, which may contain a sequence of actions, is retrieved from the task store.
Figure 6.4: Nature of the action recommendation problem and its connection to Markov Decision Process (MDP)
First, we will consider the nature of the problem we are trying to solve for action recommendation. A user is performing a task and we need to provide the optimal action to the user given the current world state to accomplish the task. In a realistic setting, a user may fail at performing a task (e.g., charred bread toast) resulting in stochastic transitions between various intermediate world states.
The problem of optimal action recommendation is depicted in Figure 6.4. Action recommendation has to be performed at every step over a sequence of states. Hence, it is a sequential decision problem. The best possible action recommendation at the current state depends on the current world state alone and not on the way in which the current state is attained.
CONCLUSION
Understanding real-world event interactions and their dynamics from observational data in PCS systems is a challenging problem. Some of the challenges include uncertainty, incompleteness, heterogeneity, and dynamism of real-world events and their manifestations in observational data. We demonstrated that probabilistic graphical models are a natural fit to deal with these challenges in PCS systems.
PGMs utilize probability as a calculus for dealing with uncertainty and graph structure to capture complex event interactions and event dynamics. We demonstrated the use of temporal probabilistic graphical models in modeling dynamism of PCS events. While utilizing PGMs for addressing these challenges, we discovered that the declarative domain knowledge can complement learning structure and parameters of PGMs. The incompleteness and heterogeneity challenges were dealt by integrating observations from people and machine sensors.
Our solution has three components: i) Event extraction, ii) Event understanding, and iii) Action recommendation for processing observational data from PCS systems. As mentioned earlier, these three solution components correspond to the John Boyd’s OODA-loop operations of observe, orient, and decide & act respectively. The three solution components are grounded in a variety of PGMs enumerated in Figure 7.1.
Figure 7.1: Relationship between PGMs, declarative knowledge, and PCS system along with the publications indicating the topic of contribution with respect to the overall thesis idea of supporting PGMs with declarative knowledge
Interactions between observational data, declarative knowledge, PGMs, three solution components, and PCS applications introduced earlier are presented here for clarity. As noted earlier, PGMs are specified using structure and parameters. Each of the publication mentioned in Figure 7.1 utilizes the indicated method of deriving structure and parameters. PCS event extraction work discussed in Chapter 4 addresses annotation of raw data and learning parameters of a CRF model.
The PCS event understanding work discussed in Chapter 5 deals with learning parameters for an LDS model utilizing domain knowledge for specifying the structure. We presented declarative knowledge enabled BN structure extraction to uncover event interactions from data in Chapter 5. Chapter 6 introduced the ideas for initializing parameters of a MDP model utilizing declarative knowledge. We demonstrated that both top-down and bottom-up techniques enable specification of PGMs, and specifically, declarative domain knowledge can support both structure and parameter specification of PGMs.
Source: Wright State University
Author: Pramod Anantharam
>> 200+ IoT Led Projects for Final Year Students