-Analysts in many areas of national security face a massive (high volume), dynamically changing (high velocity) flood of possibly relevant information. Identifying reasonable suspects confronts a tension between data that is too atomic to be diagnostic and knowledge that is too complex to guide search. D2REEM (Dynamic Data Relevance Estimation by Exploring Models) is a knowledge-based metaheuristic that uses stochastic search of a graph-based semantic model to guide successive queries of high-volume, high-velocity data. We motivate D2REEM by considering the nature of knowledge-based search in highvolume, high-velocity data and reviewing current tools. We then outline the D2REEM metaheuristic and describe the state of progress in applying it to a range of model types, including geospatial movement, behavioral models, discourse models, narrative generators, and social networks. Finally, we outline work that needs to be done to advance the D2REEM agenda.
Analysts in many areas of national security face a massive, dynamically changing flood of possibly relevant information. “Big data” is typically described in terms of Volume (the amount of data), Velocity (how fast it changes), and Variety (the diversity of data formats); our concern here focuses on high-volume, high-velocity data. Activities of crucial interest can be expected to leave many “footprints” in available data, but identifying reasonable suspects confronts a tension between data that is too atomic to be diagnostic and knowledge that is too complex to guide search.
The data problem is that no single data item is diagnostic of an attack. Any one data item that might be part of an attack could also be part of a benign scenario. For example, a purchase of fermentation equipment might be a precursor to anthrax cultivation...or to opening a microbrewery. A new dissertation on gene splicing in microbes might point to a potential perpetrator...or just a promising new assistant professor. In data retrieval terms, static single-item queries give very low precision in identifying the overall event.
The knowledge problem is that while we can capture
overall patterns of behavior that are diagnostic, matching them
against massive data is combinatorially prohibitive.
Representations that are available include discourse models
that capture the different forms a conversation in social media
might take [
This paper describes D2REEM (Dynamic Data Relevance Estimation by Exploring Models), a knowledge-based metaheuristic that uses stochastic search of a semantic model to guide successive queries of high-volume, high-velocity data. Section II explores the challenge that D2REEM addresses and the current state of the art. Section III outlines the D2REEM metaheuristic. The heart of D2REEM is a knowledge-based model of the domain, and Section IV reviews several classes of models to which D2REEM may be applied and documents our success so far. D2REEM is a work in progress. Section V identifies a series of next steps for advancing this approach to semantic-driven search of big data. Section VI concludes.
II.
Figure 1 summarizes the challenge that D2REEM addresses. Static single-record queries are simple, but can be efficiently applied to high-volume high-velocity data. Conventional matching methods are too inefficient to apply knowledge-rich patterns to such data. D2REEM is a novel way to match complex patterns to big data.
For years, the staple of information retrieval has been the record-oriented query, in which the analyst describes single data items that might be of interest. Static queries can be matched very efficiently, but their relevance depends on the state of knowledge about the world, which changes with each new piece of information.
The last 25 years have produced an explosion in graph databases, that is, databases that capture semantic relationships among data items in a graph structure. Graph databases can be
+ a t a D + f o + y t i c o l e V + & + e m u l o V
Graphs are a natural way to capture a knowledge model, but classical graphical query languages have several disadvantages for knowledge-based subgraph matching. • • • •
They are generic to any graph-structured data, and do not take advantage of specific semantics in various kinds of graphical models. We wish to exploit the knowledge in a model.
They require the entire query to match a subset of the data. We would like to search the data against a graphical structure (such as a hierarchical task network [HTN]) that expresses a range of possibilities, and identify coherent subsets of the pattern that the data support.
In general, graph matching is intractable [
Graph databases require the data to be represented as a graph. We address high-volume high-velocity data streams (such as social media) where such preprocessing is not feasible.
III.
THE D2REEM METAHEURISTIC
D2REEM is a metaheuristic, a high-level procedure that guides a lower-level process (in this case, record-level querying). Like many metaheuristics (e.g., genetic algorithms, ant-colony optimization, swarm optmization, artificial immune systems), its methods are strongly inspired by biological models.
D2REEM shifts the focus of computation in doing knowledge-based exploration of big data. It moves computation away from matching the model against the data, and toward executing a process over the model that embodies the distinctive semantics of the model. Table I summarizes the differences between D2REEM and subgraph matching in a graph database.
Because D2REEM works with data as a stream of records, rather than a pre-processed graph, it must issue many recordlevel queries in order to match a knowledge model. It does this by executing a continuous cycle (Figure 2). Repeatedly, D2REEM • • • • explores the current state of the model, updates the priority for learning more about each node in the model, adaptively generates a query for the highest-priority node, and updates the model with what is learned from that query. The queries can be posed to any data source, and do not
require predefining relationships among separate data items.
The relationships among retrieved nodes are computed by
exploring the model, not by a complex matching process, a
strategy similar to graph simulation [
Figure 1 shows the result. Static single-record queries can be applied to big data, but cannot capture complex patterns among records. Graphical databases can express patterns, but computational complexity forces the patterns to be smaller than a realistic behavioral model, and the data must be small enough and stationary enough to preprocess into a graph. By taking advantage of model semantics, D2REEM can match very large knowledge-rich patterns (with thousands of nodes) against high-volume, high-velocity data streams that are not in graphical form.
Figure 3 shows the D2REEM architecture. The heart of D2REEM is a Graphical Knowledge Model (GKM) with two characteristics: •
Edges in the graph represent causal or other sequential dependencies between nodes, so that a trajectory is a possible evolution of the world, and The likelihood of visiting a given node can be modulated by evidence attached to the node.
The Polyagent Sampling Engine (PSE) continuously samples alternative trajectories through the GKM to generate a distribution over possible trajectories reflecting current knowledge of the domain. The Evidence Prioritizer and Marshaller (EPM) examines these distributions to identify nodes about which more information would be useful, issues queries to retrieve that information, and updates the GKM with the results. The PSE’s ongoing exploration takes account of this new information, modifying the distributions over trajectories, and thus leading to new rounds of queries, implementing the processing cycle shown in Figure 2. B. Polyagent Sampling Engine
By construction, each trajectory through a GKM corresponds to a possible instance of the dynamics implicit in the graph. Evidence currently on each node of the graph modulates the probability assigned to trajectories involving that node. We wish to construct a distribution over all possible trajectories. An approach we have found particularly tractable over many types of GKM is polyagent sampling.
A polyagent is a set of agents that collectively explore possible trajectories for a single entity or behavioral instance of interest. It consists of a single persistent coordinating agent (the “avatar”), which continuously generates a stream of simple agents (“ghosts”), each exploring a single trajectory. Figure 4 shows a polyagent sampling possible paths through a geospatial domain.
Ghosts have three biologically-inspired characteristics: they are manifold, apoptotic, and tropistic. “Manifold” means that many of them explore the domain in parallel, like multiple ants in an ant, or multiple chromosomes in genetic evolution, or multiple antibodies in an immune system, or agents in swarm Ghosts&
Analyst(
While the immediate inspiration of the PSE is biological,
its mathematical underpinnings are based on Monte-Carlo tree
search (MCTS) [
C. Evidence Prioritizer and Marshaller
The EPM has three functions: • •
Based on the distribution of trajectories through the GKM determined by the PSE, identify the nodes for which additional information would be most valuable. Formulate and execute queries that will provide more information on the selected nodes Avatar& •
Update evidence on the selected nodes based on the results of the queries.
We consider these in turn.
Identify nodes to guide queries.—Intuitively, D2REEM estimates the relevance of candidate queries based on the nodes for which additional information would be most valuable. The precise sense of “valuable” depends on the kind of GKM that is guiding the search, and the decisions that it is guiding. Here are some alternatives that are useful in different settings. In the next section, we give further examples of each of these.
In sparse environments, the most valuable query is one most likely to yield a hit. In our PROPS system, polyagent sampling over a geospatial lattice generates candidate trajectories for adversaries, and the most probable trajectory guides the decision of where to deploy scarce surveillance assets to increase the probability of detecting an adversary.
One might try to maximize some global measure over the
GKM. One use for an HTN in D2REEM is to model a potential
adversary’s behavior (e.g., mounting a biological attack). In an
HTN (using the rTÆMS dialect [
In some cases, the nodes about which we want to learn more are those for which more information would sharpen the distribution over alternative trajectories. We estimate the effect of this choice by changing the evidence levels for various nodes in copies of the GKM and run the PSE on them, then compare the resulting distributions.
Formulate and Execute Queries.—The EPM submits queries to external data sources for those nodes that have been identified as of highest priority. Currently, we construct queries for each node manually in the course of formulating the GKM, and the EPM retrieves the specified query and submits it.
Update Node Evidence.—The EPM updates the evidence supporting the node on the basis of the response to the query. This change modulates the ongoing execution of the PSE, potentially changing the highest priority nodes in the next invocation of the EPM and directing the search process to the most relevant potential data.
IV.
EXAMPLES OF D2REEM MODELS
The heart of D2REEM is a semantic model of some facet of the real world. We have identified numerous such models, and demonstrated various facets of D2REEM on them. This section outlines these examples. For each, it discusses • how the model supports the two requirements identified in Section III.A (trajectories represent possible evolutions of the world; evidence on nodes modulates probability of trajectory) • how it supports the PSE and EPM (in particular, what makes a node “relevant”), and •
what aspects of D2REEM have been implemented in it. A. Movement on Geospatial Maps
The most mature class of GKM for polyagent sampling is
the geospatial lattice, whose nodes correspond to tiles of the
environment and whose edges represent adjacency among tiles
[
A trajectory represents the movement of a target, and the probability that a trajectory visits a node depends on externally-provided information such as terrain, presence of friendly or adversarial forces, and combat activity. The cumulative distribution of presence pheromone thus reflects the probability of encountering the target as a function of location.
In the DARPA RAID project, we applied the PSE on such a
model to urban combat. Figure 5 shows the close correlation of
predictions of red force movement in a human-commanded
wargame, compared with the actual movement of troops.
Quantitatively, the PSE produced more accurate forecasts than
both experienced human observers and game-theoretic or
Bayesian reasoners [
In the ARL PROPS project, we used the PSE on a geospatial lattice to direct collection management. The relevance criterion in this case is to give priority to queries (intelligence requests) on areas most likely to generate a hit.
PROPS is the most mature implementation of the D2REEM metaheuristic to date, including ongoing PSE exploration of the knowledge model, dynamic query formulation, and updating of the knowledge model.
B. Hierarchical Task Networks
Goal-oriented behavior by intelligent agents is often
represented with a hierarchical task network (HTN) [
Forces w/ 15 min tails t = 140 + 900 sec
Load Trojan on target Load Trojan via Game
Load Trojan via
Hacked Site Post bogus game
Pgm on target opens port
Scan site for banner,
version Invite & Load Pgm on target beacons out Retrieve Data
Prepare Slides
List Available
Files
Key: Upload hacked front end
Retrieve File Decomposable
Task
Atomic
Action
“and”
subtask
sequence
carry it out, and sequence edges (dashed) that reflect
precedence constraints. These precedence constraints
are inherited by the leaves of the HTN. The graphical
language in the figure is a simplification; our full
formalism, derived from the TÆMS language [
Polyagent sampling explores alternative trajectories through the leaf tasks. Each trajectory reflects a sequence of actions that an agent might execute in the world. The probability that an agent’s next step will move to a given task depends on the task’s feasibility (the satisfaction of its prerequisites), its desirability (based on the degree to which higherlevel tasks have been achieved), and evidence for the task from the external world (provided by the EPM).
The HTN is an example of a GKM for which the
value of generating a query for a node depends on a global
characteristic of the model, namely, the change in the quality
of the root node that a response to the query might generate.
We have demonstrated the PSE on HTNs [
C. Social Networks
We represent a social network [
A trajectory in a social network indicates a sequential transfer of social capital. For example, one may seek evidence for a money laundering operation that moves a financial payment makes its way through a series of organizations. Evidence of a specific transaction increases the likelihood of a transition from one agent to another.
Our current PSTK system explores possible flows using specialized processes residing on each agent, not the PSE. We have not implemented a EPM for social networks. If one is seeking to identify sequences of transactions, the relevance of a node to generate a query is measured by the degree to which additional information on that node would sharpen the distribution over alternative trajectories. For example, a node that is shared by several emerging trajectories would not rank as high as one that is unique to a single candidate trajectory.
A Narrative Space Model (NSM) captures a set of many
possible narratives that could explain the evolution of a
situation [
Each trajectory through an NSM represents a coherent narrative about how the world might evolve from the origin to the destination. Figure 8 shows an abbreviated NSM that captures ways that al-Assad might stay in power or lose power in Syria. The ‘????’ notation on edges between nodes are placeholders for edge weights that the PSE fits based on evidence on the nodes. In an NSM, external evidence for (against) an individual node increases (decreases) the probability of trajectories including that node.
We have implemented the PSE on NSMs, and modulated its behavior by attaching external evidence to nodes in the NSM. In our work so far, this evidence has been attached by a human analyst, not by the EPM. Since our interest is in identifying the most likely narrative given the evidence available to date, the EPM for a NSM would weight nodes based on how much evidence for a given node would sharpen the distribution over emerging narratives.
E. Discourse Models
Dooley Graphs [
There are a number of ways one could graph a sequence of utterances, depending on what one chooses as the nodes.
The nodes could represent specific utterances, and edges would reflect the sequences among them. This representation loses critical information about who issues each utterance.
One might analyze the conversation to characterize different states that it could assume, and then represent each state as a node, with edges representing possible state transitions. A state model, like an utterance model, deemphasizes the participants, and in addition makes it difficult to distinguish specific conversations. We could represent participants as nodes, with edges representing utterances from the source to the target. Like the state model, the participant model does not 1.#rfq# 4.#bid# 5.#accept#
B1# 2.#query# 3.#answer#
A2# 1.#propose#
7.#no?fy# A1#
C1# 3.#prefer# 1.#propose# 6.#prefer# 7.#no?fy# 2.#check# 4.#confirm# B1#
E1# UFerance# Character# • • • D1# D1# 1.#rfq# 1.#rfq# A1#
C1# 1.#propose# 7.#prefer# 5.#no?fy#
A Dooley graph (e.g., Figure 9) is a bipartite graph. One class of nodes (circles in Figure 9) represents characters, which are participants at distinguished stages of the discourse, based on the notions of resolution and completion. Thus participant A may appear as nodes A1 and A2. The other class of nodes (squares in Figure 9) represents utterances, which are characterized by type of speech act. Utterances that resolve or complete one another tend to form tightly-connected components of the graph, while those that take off in new directions spawn new components. A trajectory through the Dooley graph represents a realization of a conversation. Retrieving a tweet from (say) A to B adds evidence to Acharacters and B-characters; recognizing the tweet as a specific speech act adds evidence to utterance nodes requiring that speech act.
We have not yet implemented either the PSE or the EPM on Dooley Graphs. In using a Dooley Graph for surveillance of social media, one would seek to identify well-formed conversations and classify them (e.g., meeting organization, viral propagation of opinion, purchase activities). For this purpose, the EPM should prefer nodes based on their potential for sharpening the distribution over alternative trajectories.
Four main avenues for extension of D2REEM provide a range of challenging and important research opportunities: multiple model types, model management, query generation, and model linking.
Multiple Model Types: Our most complete example of D2REEM is the PROPS system, which treats the geospatial domain. The NSM is the next most mature, demonstrating the effectiveness and computational efficiency of modulating the state of a non-geospatial knowledge model by external evidence. In addition to refining these applications, we seek to extend the complete D2REEM cycle to other model types. As we configure the PSE and EPM to different model types, we gain valuable insights into how the underlying mechanisms of the metaheuristic can be generalized.
Model Management: As noted in Section II.A, an important difference between D2REEM and graph DBs is how knowledge is expressed. Graph DBs construct a small graphical query using the same graph syntax that governs the data, and seek to match the entire query graph against the data graph. D2REEM uses a large GKM that captures a range of hypotheses, and then explores this model in the light of the data to identify high-priority record-level queries. The use of a complex knowledge model is a strength, in that it externalizes analysts’ internal mental models, facilitating collaborative review and enhancement. But it is also a weakness, since constructing such models is itself a labor-intensive process.
For many long-standing problems, model construction is
integral to the analytic effort [
A strength of the PSE approach to model exploration is the locality of ghost movement and pheromone-based interaction. This locality means that GKMs can be extended incrementally, and encourages the notion of a persistent library of dynamically updated models as a central resource in analysis. Development of mechanisms for managing such a library will considerably advance the analytic enterprise.
Query Generation: One task of the EPM is formulating queries that can provide additonal information on GKM nodes that it identifies as highly relevant. In our current implementations, these queries are manually constructed along with the GKM. Given the description of a node in a model and schemata for external data sources, one would like to generate queries automatically, a task that will rely heavily on research in ontological reasoning and semantic web technologies.
Model Linking: The same analytic tasking can be viewed
through the lens of multiple model types, and we would like to
facilitate the flow of information between these model types by
defining mappings between nodes in different model types.
Like the previous topic, this one depends on advances in
ontological reasoning, as well as model theory and other
formal tools [
VI.
CONCLUSION
Matching knowledge-rich patterns against high-volume, high-velocity data is combinatorially prohibitive. The D2REEM metaheuristic is a new approach to such retrieval problems that shifts the computational burden from graph matching (a NP-complete problem) to iteratively exploring a knowledge model and issuing focused queries for the data that is most relevant in the light of current knowledge (a process that is linear in the size of the knowledge model). D2REEM can be applied to any graphical knowledge model in which edges represent causal or or other sequential dependencies and in which adding data to individual nodes can change the probability of a trajectory.