Acceleration of cognitive domain ontologies

Date of Award

2016

Degree Name

Ph.D. in Electrical Engineering

Department

Department of Electrical and Computer Engineering

Advisor/Chair

Advisor: Tarek Taha

Abstract

This thesis examined several acceleration efforts of knowledge mining from Cognitive Domain Ontologies (CDOs), which is a knowledge repository in the Cognitively Enhanced Complex Event Processing (CECEP) architecture. The CECEP architecture was developed at US Air force research laboratory. This is an autonomous decision support tool that reasons and learns like a human and enables enhanced agent-based decision-making. This architecture has applications in both military and civilian domains. Real time agents require massively linked knowledge databases to be searched using a large set of constraints to generate intelligent decisions in run time. One of the most computationally challenging aspects of CECEP is mining the domain knowledge captured in CDOs. The CDO mining process employed in the CECEP architecture is cast as a constraint-satisfaction problem (CSP). It falls into the category of NP-complete problems, which are very likely to require massive computing to solve. Even a small instance of an NP-complete problem in some cases could take years of computing to solve. Typically searching is a ubiquitous procedure to solve CSP problems, but sometimes constraint consistency is good enough to find a valid solution without performing a search.This thesis explored several CSP algorithms and deployed two different algorithms on heterogeneous hardware platform in order to mine CDOs. We initially examined the Exhaustive depth first search (EDFS) algorithm on a cluster of GPGPUs and Intel Xeon Phi co-processors. We achieved around 100 times speedup on a GPGPU compare to single CPU. Since the search space grows exponentially with the EDFS algorithm, this study explored an intelligent search algorithm that can prune the search space according to the constraints. We modified the conventional Forward Checking (FC) algorithm and introduced a novel path-based forward checking algorithm to mine CDOs and compared with a commonly utilized CSP solver. Conventional single step forward checking algorithm is highly serial in nature. This thesis developed a three-step forward checking algorithm that enabled parallelism. The serial version of the proposed path-based forward checking algorithm provides a million times speedup compared to a conventional CSP solver. Furthermore we have parallelized this novel algorithm on a cluster environment and achieved approximately 200 times speed up over a serial implementation.This path-based forward checking algorithm was deliberately designed to enable the listing of the solutions in a highly compact and efficient manner. This compact representation does not generate actual solutions but represents them as a set. In real-world applications, exact solutions are required to make decisions. Typically CDOs generate all equally weighted solutions; it is impossible to find the best one from this solution set without imposing relative importance of certain criteria. This thesis implemented several optimization conditions through objective functions and processed as Multiple Constraint Optimization Problems (MCOPs) using modified Branch and Bound algorithm to rank solutions. Additionally we parallelized this optimization procedure on a GPGPU and ended up achieving 85-100 times speedup. This amount of speedup would allow autonomous agents to make decision in real time based on massive knowledge bases.

Keywords

Constraints (Artificial intelligence), Parallel algorithms, Ontologies (Information retrieval), Computer Science, Computer Engineering, Cognitive Psychology, Electrical Engineering, Acceleration of constraint satisfaction problem, parallel CSP, Parallel forward checking algorithm, parallel DFS, cognitive agent, knowledge mining, data mining

Rights Statement

Copyright © 2016, author

Link to Full Text

Share

COinS