The knowledge engineering e ort associated with de ning grammar systems can become a barrier for the practical use of such systems. Existing grammar and rule induction algorithms o er rather limited support for discovering context-sensitive graph grammar rules as required by some applications in the domain of engineering design. For this task the present work proposes a rule induction method grounded on Genetic Programming. Specializations regarding the representation and evaluation of rule candidates are discussed. Results from preliminary experiments with a prototype implementation demonstrate the feasibility of the suggested approach.
There is a growing interest in using grammar-based systems in the eld of
computer-aided design. Sridharan and Campbell [
In this paper focus is put on learning an additional grammar rule pi in presence of an existing but incomplete rule set [p]A (sets are depicted in square brackets). The new rule set [p]B = [p]A [ pi will be used in a graph-rewriting system that shall be capable of reproducing a set of desired design graphs [Gbn] by means of derivation from an initial graph G0. All rules are allowed to be context-sensitive, i.e. left-hand side (LHS) and right-hand side (RHS) may contain both terminal and non-terminal (NT) elements. Considering the practical application for engineering two additional restrictions apply:
Restriction 1: There is no explicit information available on how the rules of [p]A are de ned (LHS and RHS are hidden from the learner). This restriction stems from an application scenario where di erent engineering organizations, each working on di erent subsystems or disciplines, contribute to a commonly used graph-rewriting system. It is likely that these organizations want to share results with their partners, whilst being reluctant to reveal insight on how these results were established, i.e. their design rationale should be kept secret.
Restriction 2: As training data we are only given the initial graph G0 (input) and desired design graphs [Gbn] (output). The data does not provide any negative examples of undesired graph-rewriting behavior. This restriction suits common engineering practice where positive milestones and nal results are more likely to be documented than un nished states and failures.
In light of this, a machine learning process based on Genetic Programming (GP) is proposed and studied using the following methodology: First, the feasibility of using GP for rule induction in the given context is validated by constructing a prototype implementation. Then, its applicability is tested with respect to an existing graph grammar from engineering design (pilot case) and a comparative study with an existing rule induction algorithm is undertaken.
Accompanying materials, including an application example and a discussion on extending the proposed method to iteratively learn multiple rules, are provided online at http://ouky.de/accompanying-materials/ruleml-2015. 2
Besides various contributions addressing the induction of context-free string
grammars, there only has been relatively little research on learning
contextsensitive graph-grammars [
In order to address these limitations, machine learning can be conceptualized
as search over a space of possible hypotheses [
This section describes a GP-based rule induction algorithm for learning rules that comply with an existing context-sensitive graph grammar. The learner's task is to determine de nitions for rule pi in order to enable a graph-rewriting system to produce the desired design graphs [Gbn] from the initial black-box design G0.
Consider a prede ned rule sequence S = p1; p2; :::; pi 1; pi; pi+1; :::; pn 1; pn of length n that can be used to derive [Gbn] from G0. Subsequences S1 = p1; :::; pi 1 and S2 = pi+1; :::; pn are known to the graph-rewriting system (reasoning process) but unknown to the learner, and pi is unknown to both. The proposed learner is capable of learning de nitions for the LHS and RHS of pi given the following is provided: G0, [Gbn], and access to the graph-rewriting system in order to gather answer sets [Gi+1]; [Gi+2]; :::; [Gn] for possible candidate de nitions of pi.
The proposed learner's main procedure (see algorithm 1) learns a rule candidate for one desired design graph at a time and tests if the found candidate is applicable to more than one graph of the desired answer set. Its sub-procedure evolve is a GP algorithm specially con gured for the rule induction task. Algorithm 1 Main procedure of proposed GP-based rule induction algorithm.
Load G0 and [Gbn] Initialize graph-rewriting system with rules p1; p2; :::; pi 1 and pi+1; :::; pn 1; pn while [Gbn] is not empty do
Get next Gbn;j from [Gbn] S Use evolve to learn a rule pi;j that enables derivations G0 =) Gbn;j
where S = p1; p2; :::; pi 1; pi;j ; pi+1; :::; pn 1; pn Remove Gbn;j and all graphs of [Gbn] that can be derived using pi;j
Add pi;j to the set of learned rules [pi] end while return [pi]
During GP, candidates for pi are sampled from the space of possible rule de nitions by means of evolutionary principles. Initially, the set of considered candidates, called population, is chosen randomly. Then, with each GP iteration, a new generation of this population is produced by applying mutation, crossover and selection operators. The selection operator ranks every produced candidate with respect to evaluation criteria and determines what candidates are considered for the next generation (survival of the ttest). Mutation and crossover are used to produce new candidates from the members of the current population. Crossover recombines parts of two candidates to form a new candidate, whereas mutation randomly changes parts of an existing candidate.
As a preparatory step, all possible host graphs [Gi 1], on which pi may be applied, are computed. Then, from this set a subset [Gbi 1] is formed that only contains host graphs which are feasible for deriving the current desired design graph Gbn. This is realized by a lter that checks whether all monotonic elements present in Gi 1 are also present in Gbn. In this case only NTs are non-monotonic. Once added, terminal nodes and edges are preserved throughout the remaining direct derivations. Hence, there must be a subgraph isomorphism that maps all terminal nodes and edges of Gi 1 to Gn. If this is given, then Gi 1 2 [Gbi 1]. 3.1
The representation of candidates is crucial for the rule induction task. In this case a candidate denotes, which host graph Gi 1 is chosen from [Gbi 1], and what graph operations will be performed on Gi 1 to yield Gi:
Regarding the rst point, all graphs in [Gbi 1] are considered as possible bases for deriving Gbn. Since the learner is not allowed to inspect the LHS of the following rules, di erent Gi 1 2 [Gbi 1] need to be tested by executing the graph-rewriting system in a manner of trial-and-error. Which Gi 1 is chosen is re ected by an index parameter within the rule candidate representation that is subject to the evolutionary optimization.
The second point addresses the RHS of the rule. Essentially each rule candidate is a tree structure (the standard representation for GP individuals) that speci es how the chosen Gi 1 will be modi ed. The tree consists of operation nodes and index nodes. Operation nodes represent the graph operations used for modifying Gi 1. For the problem at hand the considered operations are add-node, add-edge, add-non-terminal, and remove-non-terminal. Index nodes parametrize these operations with respect to Gi 1 and Gbn. Further, every operation has a cost factor associated that is used for evaluation.
In order to evaluate a rule candidate, the set of considered host graphs [Gbi 1] is passed to the GP-tree's root node. Using an index node attached to the root, some Gi 1 2 [Gbi 1] is chosen. Then, Gi is initialized as a copy of this graph and passed to the root's children in order to be propagated through the whole tree. At each operation node the graph is modi ed with respect to the parameter de ned by its index node child (see list below). An operation is bypassed if it is not applicable. Having passed this way through all nodes of the tree, the modi ed graph Gi is considered to be the direct derivation result of rule candidate pi, just as if it had been applied in the graph-rewriting system.
Add-node: For all terminal nodes in Gbn that are not yet present in Gi, add the one speci ed by the index node to Gi. The operation is not applicable if the set of addable nodes is empty. The cost for this operation is 2.
Add-edge: For all edges in Gbn that are not yet present in Gi, add the one speci ed by the index node to Gi. Incident nodes that are not present in Gi are added as well. The operation is not applicable if the set of addable edges is empty. Adding an edge costs 2 and each added node adds up with an extra 2.
Add-non-terminal: For all edges in Gbn that are not yet present in Gi, but where exactly one incident terminal node already exists in Gi, select the edge speci ed by the index node. Add a NT and the selected edge to Gi, where one end of the edge marks the existing terminal node, and the other is the newly added NT. The operation is not applicable if the set of edges to be considered is empty. The cost for this operation is 1.
Remove-non-terminal: For all NTs in Gi, remove the one speci ed by the index node. The operation is not applicable if the set of NTs is empty. The cost for this operation is 1. 3.2
Three criteria, termed match, brevity, and variety, are considered for determining the tness of a candidate. Match targets the main goal of nding an applicable rule that enables the derivation of Gbn under consideration of the remaining rule sequence pi+1; :::; pn 1; pn. The other criteria have corrective purposes for improving the quality of the produced rule candidates.
Match: After Gi has been prepared, the learner tries to apply the remaining
rule sequence S2 using the graph-rewriting system. The graphs produced during
derivation are compared with Gn in terms of similarity. Match is considered at
maximum (1) if one of the produced graphs is isomorphic to Gbn, or if Gbn is
completely \included" in one of the produced graphs (subgraph isomorphism).
Otherwise match is measured using a graph similarity algorithm which compares
the topology and labeling of both graphs and returns a value within [0; 1]. The
most similar graph is taken as reference for the rule candidate's match. This has
been implemented using the Neighbor Matching algorithm proposed by [
During the GP's evolutionary search the rule candidates are allowed to contain operations that are not directly needed to achieve the goal of producing the desired design graph: First, there may be operations that are not applicable. These are simply ignored during the generation of Gi. Second, it is su cient if the desired graph could be matched in terms of a subgraph isomorphism, i.e. super uous operations do not prevent from reaching maximum match. Leaving these elements in the rule candidates is a deliberate design choice, as it increases the genetic variation in the population. Thereby, a once super uous or inapplicable operation of one candidate actually can become useful when it is passed to an individual of a later generation. In consequence of crossover and mutation this operation (or gene) may be put into a di erent context where it is mandatory for derivation. Just at the very end of the GP search process all unnecessary operations are removed from the best rule candidate.
Brevity: Taking only match into account could lead to the undesired behavior of discovering a rule that replaces existing rules of the following rule sequence instead of enabling their use. In order to penalize such rules brevity is de ned as the inverted sum of costs of all applicable operations. The associated costs are also used to rank di erent strategies for graph manipulation. For instance, consider a speci c edge that can be added either directly by the candidate or by advising a following rule to do so using a NT. Here, the second strategy is preferable, since it does not compromise the concerns of that existing rule. This is re ected by the lower score of add-non-terminal compared to add-edge. Start
Prepare host graphs
Randomly generate initial rule candidates
Use rule candidates together with existing rules for derivation Select individuals based on fitness Make random changes (crossover/mutation)
Fitness of best No matching rule converged?
Yes
Compare derived graphs with target graphs (match) and compute fitness
End Reduce and return best rule
Variety: This score targets special semantic properties of our application domain. Typically, a rule focuses on the conversion of some speci c types of ows (edges) through functions (nodes). It would be atypical if a wide variety of ows were subject the modi cation by the rule candidate. Hence, variety is de ned as the inverse number of distinct ow labels used by the rule.
Match, brevity and variety are multiplied to gain an overall tness score for each rule candidate. These tnesses are the basis for selecting individuals that will be used for \breeding" the next generation. Separately from the GP selection process, for each generation, individuals achieving maximum match (1) are ranked with respect to their tnesses. If the tness of the best candidate from this set converges, the best candidate found so far is reduced to its necessary operations and returned as result of the procedure evolve. The LHS and RHS of the rule are deduced from the remaining operations. Fig. 1 provides a summarizing ow chart for the evolve procedure. 4
The hereinafter described preliminary experiments were conducted with a
prototype implementation. The system uses a rule set consisting of 11 rules. These
rules largely correspond to those of a graph grammar for functional engineering
design, which was hand-crafted by a group of experts [
In each experiment one rule was taken out of graph-rewriting system and the learner was given the task to learn it. The learned rule was compared to the original rule with respect to the nodes and edges each rule added to the produced graphs. Every node or edge of a desired graph in [Gbn] is classi ed as follows. True positive: node/edge is both added by the learned and the original rule. False positive: node/edge is only added by the learned rule. True negative: Neither learned nor original rule add the node/edge. False negative: node/edge is only added by the original rule. Accuracy (ACC) and the F1 score { two common measures for classi er evaluation { have been employed to measure the similarity of learned rules with original rules. Accuracy denotes the relative amount of correctly assigned nodes/edges. F1 puts a stronger bias on the elements that should not have been part of the learned rule. It is the harmonic mean of precision (PRC) and recall (RCL). PRC: How many added nodes/edges of the learned rule are also part of the original rule? RCL: How many added nodes/edges of the original rule are also added by the learned rule?
As a baseline, another rule induction algorithm based on the Subdue method
[
Table 1 shows the mean ACC, PRC, RCL, F1 score for the learned rules. Since Subdue is a deterministic method, it is only executed once, and its mean scores are computed over the graphs of [Gbn]. The proposed GP method is nondeterministic, thus every test run, i.e. the execution of the main procedure, has been repeated 25 times. The mean has then been computed over every nal rule candidate of evolve. GEN and MIN denote the mean number of generations and minutes needed by evolve to converge (tested on a PC with 2.5 GHz 4-core CPU and 16 GB RAM).
The rules learned by the GP approach generally show a high similarity with the original ones. As expected they most often outperform Subdue's rules, as the rules used in the preceding sequence S1 are kept and the learner tries to avoid replacing rules of S2. Subdue's strategy is to make the rules' RHSs as large as possible. Hence, parts of multiple original rules are covered by the induced rule resulting in a PRC-drop.
A drawback of the GP method is that the trial-and-error evaluation a ords signi cantly more computational resources than the Subdue method. On the test machine (see above), Subdue computes the new ruleset within seconds. Depending on the complexity of the rule and its position in the rule sequence, an execution of evolve takes several minutes. Further, in its current form the GP method may learn rules that produce graphs which are only subgraph isomorphic to the target graphs [Gbn]. The results show the principle feasibility of inducing rules by means of GP in context of an existing rule set. Further, it has been shown that the proposed method is applicable to a concrete example from the eld of engineering design. It is capable of learning rules that are considerably similar to those of an existing graph grammar for functional decomposition. In comparison with a state-of-theart rule induction algorithm that learned the complete ruleset from scratch, the proposed method achieves a higher similarity with the original rule de nitions.