Sometimes we may wonder where we can obtain semantic frames to be used in a computational model of Conceptual Blending. The frames can be handmade, adapted from existing frame libraries or, as we suggest in this document, discovered by mining conceptual graphs. The idea we summarise here depicts our proposed computational mechanism to explore the knowledge base containing the conceptual graphs for recurring semantic patterns representing potential frames.
A general issue in Computational Creativity (CC) arises from the need of having data
crucial to build models. With the ambition of going beyond simple toy problems we are
currently looking forward for the CC prototype system we have been developing to be
capable of handling larger amounts of data. That system is comprised of various modules:
a fast mapping module [
The mapping module is implemented as a Genetic Algorithm (GA) that extracts
mappings from large-scale conceptual graphs such as ConceptNet [
Fauconnier and Turner [
wing partOf purpose fly
Various forces act to connect and blend different parts of knowledge present in two or
more input spaces, including a generic space containing elements common to both the
input spaces and representing a shared conceptual structure between them [
A CB framework as the one shown in Fig. 1 requires at least two input mental spaces containing the source of information to be processed. These input spaces could correspond to semantic networks comprised of relations between concepts, i.e. Knowledge Bases (KBs). One of the steps CB does - named composition - is using an alignment of concepts of each input mental space as a guide of which concepts are to be used in the blend space. In the end, a new mental space emerges from the CB process containing its “output”.
For the guiding alignment stated above, some CB implementations, including our
Blender, use a graph isomorphism between the input spaces to align concepts with a
similar structure (Left Fig. 1). Thanks to that alignment, part (or all) of the structure
present in the input spaces is also present in the blend space (shown in the right Fig.
1). The structures describing the alignment of concepts are termed mappings and are
comprised of sets of concepts. Many tools have been developed for that purpose, such
as the Structure Mapping Engine [
In addition to the composition step, additional steps are executed to complete and
elaborate the blend, namely, completion and elaboration [
It is in this step that we observe the importance of frames - to give the blend a
recognisable meaning such as an event or an entity, e.g., the journey of someone in the
Buddhist Monk example [
In this work we discuss our approach for solving some of the issues reported on [
We have been using a large subset of ConceptNet V5 processed by us and
representing the conceptual spaces described above. We added various new facts and removed
what we found as irrelevant or controversial information including biased relations as
purposeOf(woman,cook). Some of these were also noted by [
The idea makes use of a GA to find repeating structures in the KB resembling frames. Currently, these structures ignore specific concepts (such as bird or plant) and are only based on the type of relation. They can be seen as depicting geometric structures in the semantic graph. Based on our previous experience with handling large-scale semantic graphs and the complexity of this problem, we think that the best strategy to find acceptable solutions in a useful time is to use stochastic algorithms such as GAs. Additionally, our GA is mostly concurrent, makes use of multi-core processors and is able to search the KB for patterns almost in real-time.
Frames are stated as Prolog queries and are applied to the relations stored in the KB. An example of a frame used by the CB module is the idea of some entity A containing a part B whose purpose is to C, hence A gains the C ability. If variable C = ’fly’ this frame could represent the idea of an entity with a part granting it the ability to fly. This frame can be stated as the rule:
ability(A,C), purpose(B,C), partOf(B,A).
This is equivalent to a three edge, three concept semantic graph in the form of a closed triangle. With a querying engine (i.e., Prolog or Datalog based), the KB can be searched for solutions for the above frame and thus if it is a prevalent pattern or not. Solutions are counted as different instantiations of variables. An example of the depicted pattern and of a small semantic graph containing six occurrences of the same pattern is shown in Fig. 2. entity isa ability A think
purpose
As with all GAs, ours evolves a population of chromosomes during multiple epochs. The idea is to examine, traverse and scale different regions of the KB by distributing this process amongst multiple individuals. In each epoch, a chromosome is mutated, has its fitness evaluated and possibly selected for inclusion in the next epoch. The selection procedure is a simple binary tournament between two members of the population of the same epoch.
A potential pattern (i.e. frame) is stored in an individual chromosome of the population as a directed semantic graph. This graph is mapped to the corresponding query by replacing each concept present in the chromosome’s semantic graph by a unique variable (e.g. bird ! B). It is important to note that the graph stored in the chromosome contains concepts and not variables, as concepts are required to match the chromosome’s graph to a region of the KB when applying the mutation operator.
In the first epoch, the chromosomes are small regions extracted from the KB with two-three connected relations (on average). The reason for this is that, in our opinion, frames with one relation do not seem to be useful for the blending process of the blender module. For a similar reason, there is no need to use such a tool as this one to check for the most present relation in the KB if single relation frames are allowed en masse.
The stochastic search of the GA is implemented with a mutation operator, which adds or removes relations to the semantic graph stored in the chromosome. New relations are copied from the KB according to common concepts between the chromosome’s graph and the KB. Hence, an addition chooses a random concept in the pattern, checks its relations in the KB and adds one of these at random to the pattern. Relation removal is simpler, they are randomly removed from the pattern with no specific criteria and in the case the pattern gets fragmented, only a single random component of the pattern’s graph is maintained.
Given the stochastic nature of the mutation operator, each evolving pattern may degenerate into multiple graph components, that is, it may transform into various disconnected sets of relations. The mutation is always followed by a repairing operation which guarantees that the pattern is composed of at most one graph component. The repairing algorithm is simple, it remove all except one of the graph components. This remaining component is randomly chosen in order to maximise the randomness of the GA.
We use a fast querying tool named querykb provided by Aaron Bembenek which at this moment is temporarily unavailable. It was developed to strictly count all possible solutions to a given query and does not instantiate variables. However, for its purpose of counting solutions, it is exceptionally fast and efficient. It is invoked whenever the GA evaluates a chromosome’s fitness function. The number of pattern matches can reach extremely high numbers and therefore are returned by the tool as Java BigIntegers.
The score of each evolved pattern is calculated with the fitness function, applied to every chromosome in the current GA population and thus, every pattern has an individual score. As the GA is (currently) implemented as a single objective optimisation task, we had to combine k multiple objectives in a single fitness function f using a weighted sum of individual components fi (a linear aggregation). The weights are scalars and are manually chosen to fine-tune the GA and its results towards showing aspects we want the patterns to exhibit. At the moment, we have the following four objectives (k = 4): 1. f1 is the logarithm to the base 10 of the number of matches of the pattern in the
KB; 2. f2 is the number of relations (edges) the pattern has; 3. f3 is the number of different (unique) relation labels the pattern has; 4. f4 is the standard deviation of the histogram of relations the pattern has.
The first objective, f1, drives the optimisation towards finding the most recurring pattern within the KB, without any regard to the pattern’s structure. Because of the colossal amount of matches for many patterns, to include this objective in the fitness function (stored as a double floating number) the code returns the logarithm to the base 10 of the total matches (a BigInteger number) returned by the querykb tool. We decided on base 10 to be easier to deduce from the logarithm the number of digits the pattern match count has.
In addition, we include structural information regarding the pattern as three more objectives. Within those, objectives f2 and f3 guide the optimisation towards finding larger patterns. Objective f2 has more impact on that purpose compared to f3 but does not guarantee that the pattern has a diverse amount of relations, an aspect controlled by the latter objective.
Objective f4 reflects the count of relations of each type (label) contained in the pattern, i.e., four relations with the label partof, two relations with the causes label, etc. a
a X5 a
b X0 b
b X6 a
a X5 a
a X0 a
b X6 X4
X1
X4
X1
X1 a
X0
X2 b Relations not existing in the pattern are not included in the histogram calculation. The purpose of this objective is to force the pattern to have a balanced amount of relations of different labels (Fig. 3). Adjusting this weight in the opposite sense will compel the pattern to have a majority of relations of the same label. Hence, this objective controls the generalisation of patterns: generic patterns are easily or more commonly instantiated. Using Fig. 3 as a reference, structures matched by the pattern on the left are also matched by the pattern on the right. The opposite is not true, as the left pattern requires six distinct relations and seven distinct concepts when compared to two relations and three concepts in the right pattern. Therefore, the leftmost pattern is a specialisation of the rightmost pattern. Although objective f4 helps in this regard, it will only drive the GA towards generic frames given a constant f3, that is, they must have the same relation types (i.e. two in Fig. 3).
We removed from ConceptNet V5 four relations that in our opinion will not be very fruitful in the Conceptual Blending process: isa, derivedfrom, synonym and similarto. These relations are very generic and the remaining 35 relations contain more specific information regarding the concepts they are related to.
Problematic concepts with non-ASCII characters were also removed because of incompatibilities with some Java libraries and the handling of Unicode characters. Consequently, the complexity of the mining problem was reduced and the working KB had 377719 relations and 278921 concepts.
The querykb tool allows the user to set a time limit to the query/pattern match counting process, something we had to set at 30 minutes per pattern to have results within an acceptable time limit. The tool by itself is concurrent and forces our GA to be sequential when calculating the fitness function for all the chromosomes. This sets a limit that in the worst case only one chromosome would be evaluated per 30 minutes and hence, a maximum number of epochs to be processed by the GA in a given time. Unless otherwise specified, the weights used in balancing the four objectives were the following: weights values
We ran 10 experiments with an execution time of 48 24 hours and 70 30 epochs per experiment. The population size (number of chromosomes/patterns) was constant per epoch at 64 elements. The GA used a binary selection tournament with the winning probability of the strongest candidate being 75%. The machine used in the experiments had two eight-core Xeon E5-2667 v2 processors (total 16 cores) working at 3.6 GHz, 64 GB of RAM and the Microsoft Windows 7 SP1 operating system. The querykb tool used a block size of 256 and 32 threads. motivatedbygoal
Fig. 4 contains twelve of the patterns we found interesting. Changing the weight of objective f2 had an influence on the number of relations in the patterns, which can be seen by watching the top to bottom ordering of the patterns in Fig. 4. Objective f4 had the effect of lowering the presence of multiple relations of the same type, although it does not guarantee the lowest amount as seen in the last pattern containing two hasproperty relations.
We were not able to extract graph structures with cycles similar to the triangle pattern shown in Fig. 2. The search algorithm does not have any reason to find those types of structures and therefore they do not emerge during the GA’s execution. It is our opinion that this may be solved with some changes in the mutation and with one or more additional objective function(s).
As we are currently lacking semantic quality measures to evaluate the patterns, except for the four objectives stated before we can not firmly conclude if any one of the patterns is better or worse than the others either in the CB process either for any other purpose.
We presented a mechanism to mine for repeating patterns in a KB. The purpose is to find potential frames in semantic graphs that are used by Conceptual Blending modules. At the moment we have a working prototype that finds recurring patterns representing prototypes of frames. The prototype is ready to be evaluated semantically and to see whether it matches the creative requirements expected to arise ahead in our future work. We will also study other objectives to guide the quality of the emerging patterns according to whatever requirements we think the frames should have. This will require further understanding of frames and their impact on the resulting blends of the CB module.
Acknowledgements. Joa˜o Gonc¸alves is funded by Fundac¸a˜o para a Cieˆncia e Tecnologia (FCT), Portugal, under the PhD grant SFRH/BD/133107/2017. We greatly acknowledge Aaron Bembenek for his impressive querykb tool and his availability for matching the tool to the needs of our project. To a truly generous person, a sincere thanks.