Improving scalability and efficiency of ILP-based and graph-based concept discovery systems

Mutlu, Alev
Concept discovery is the problem of finding definitions of target relation in terms or other relation given as a background knowledge. Inductive Logic Programming (ILP)-based and graph-based approaches are two competitors in concept discovery problem. Although ILP-based systems have long dominated the area, graph-based systems have recently gained popularity as they overcome certain shortcomings of ILP-based systems. While having applications in numerous domains, ILP-based concept discovery systems still sustain scalability and efficiency issues. These issues generally arose due to the large search spaces such systems build. In this work we propose memoization-based and parallelization-based methods that modify the search space construction step and the evaluation step of ILP-based concept discovery systems to overcome these problem. In this work we propose three memoization-based methods, called Tabular CRIS, Tabular CRIS-wEF, and Selective Tabular CRIS. In these methods, basically, evaluation queries are stored in look-up tables for later uses. While preserving some core functions in common, each proposed method improves e_ciency and scalability of its predecessor by introducing constraints on what kind of evaluation queries to store in look-up tables and for how long. The proposed parallelization method, called pCRIS, parallelizes the search space construction and evaluation steps of ILP-based concept discovery systems in a data-parallel manner. The proposed method introduces policies to minimize the redundant work and waiting time among the workers at synchronization points. Graph-based approaches were first introduced to the concept discovery domain to handle the so called local plateau problem. Graph-based approaches have recently gained more popularity in concept discovery system as they provide convenient environment to represent relational data and are able to overcome certain shortcomings of ILP-based concept discovery systems. Graph-based approaches can be classified as structure-based approaches and path-finding approaches. The first class of approaches need to employ expensive algorithms such as graph isomorphism to find frequently appearing substructures. The methods that fall into the second class need to employ sophisticated indexing mechanisms to find out the frequently appearing paths that connect some nodes in interest. In this work, we also propose a hybrid method for graph-based concept discovery which does not require costly substructure matching algorithms and path indexing mechanism. The proposed method builds the graph in such a way that similar facts are grouped together and paths that eventually turn to be concept descriptors are build while the graph is constructed.


Policy-based memoization for ILP-based concept discovery systems
Mutlu, Alev; Karagöz, Pınar (2016-02-01)
Inductive Programming Logic (ILP)-based concept discovery systems aim to find patterns that describe a target relation in terms of other relations provided as background knowledge. Such systems usually work within first order logic framework, build large search spaces, and have long running times. Memoization has widely been incorporated in concept discovery systems to improve their running times. One of the problems that memoization brings to such systems is the memory overhead which may be a bottleneck. I...
Improving the efficiency of graph-based concept discovery systems
Abay, Nazmiye Ceren; Karagöz, Pınar; Department of Computer Engineering (2014)
Concept discovery is a process for finding hidden relations from the given set of experiences named as background knowledge [27]. Concept discovery problems are investigated under Inductive Logic Programming (ILP)-based approaches and graph-based approaches [28]. Although ILP-based systems dominate the area, these systems have some problems such as local maxima and local plateaus [15]. Recently, graph based system becomes more popular due to its flexible structure, clear representation of data and ability o...
A Counting-Based Heuristic for ILP-Based Concept Discovery Systems
Mutlu, Alev; Karagöz, Pınar; Kavurucu, Yusuf (2013-09-13)
Concept discovery systems are concerned with learning definitions of a specific relation in terms of other relations provided as background knowledge. Although such systems have a history of more than 20 years and successful applications in various domains, they are still vulnerable to scalability and efficiency issues - mainly due to large search spaces they build. In this study we propose a heuristic to select a target instance that will lead to smaller search space without sacrificing the accuracy. The p...
Modeling complex nonlinear responses of shallow lakes to fish and hydrology using artificial neural networks
Tan, Can Ozan; Beklioğlu, Meryem (Elsevier BV, 2006-07-10)
Mathematical abstractions may be useful in providing insight that is otherwise very difficult to obtain due to complex interactions in the ecosystems. The difficulty associated with the nonlinearity and complexity of ecological processes and interactions can be avoided with artificial neural networks (ANN) and generalized logistic models (GLMs) which are practically ANNs without hidden layer. An ANN and a GLM were developed to determine the probability of submerged plant occurrence in five shallow Anatolian...
Time Constrained Temporal Logic Control of Multi Affine Systems
Aydın Göl, Ebru (2012-01-01)
In this paper, we consider the problem of controlling a dynamical system such that its trajectories satisfy a temporal logic property in a given amount of time. We focus on multiaffine systems and specifications given as syntactically co-safe linear temporal logic formulas over rectangular regions in the state space. The proposed algorithm is based on the estimation of time bounds for facet reachability problems and solving a time optimal reachability problem on the product between a weighted transition sys...
Citation Formats
A. Mutlu, “Improving scalability and efficiency of ILP-based and graph-based concept discovery systems,” Ph.D. - Doctoral Program, Middle East Technical University, 2013.