The purpose of our work is to achieve creative knowledge processing. In this paper, we focus on the formulation of concept generation and its use in problem solving. We propose a method for solving a problem by generating new concepts that have never appeared in existing knowledge. We propose Creative Problem Solving, which can derive a goal state by using a creative leap invoked by concept generation.
Our work seeks to achieve creative knowledge processing. Some studies have been
conducted on computational creativity and theory invention in the AI
community[
This paper proposes a formulation of problem solving by generating new concepts that have never appeared in existing knowledge, and we con rm that such knowledge processing is implementable. We call this kind of processing Creative Problem Solving, and consider it is a part of creative knowledge processing. 2.1
We are concerned with rst-order logic as representing Knowledge. Any logical formulae can be transformed to the formulae include no functions and no individual constants. We may regard concept generation as predicate generation.
In this paper, knowledge is de ned as a set of logical formulae with no functions and no individual constants. A relation structure is de ned as a logical formula that has at least one predicate variable. A relation structure also has no functions and no individual constants.
For example, Let S1 = f8x; y : :P1(x) _ P2(x; y)g , S2 = f8x; y : :X1(x) _ P2(x; y)g. When P1; P2 are predicate constants and X1 is a predicate variable, S1 is knowledge, and S2 is a relation structure. 2.2
We de ne the substitution replace predicate variables with predicate constants.
Let Pvn be a universal set of free predicate variables of arity n, and let Pcn be a universal set of invariable predicate of arity n. If satis es Pv1 Pc1 [ [ Pvi Pci , and each variable and constant that occurs in is distinct, then we say is a simple substitutionD The element of is written in a manner similar to the style of the general substitution, v=c. Here, v is the variable and c is the constant.
For example, relation structure S1 = f8x : X1(x; y) ^ X2(x)g and simple substitution 1 = fX1=A; X2=Bg are given, then S1 1 = f8x : A(x; y) ^ B(x)g. 3 3.1
When knowledge , relation structure RS, and a predicate variable X (which occurs in RS) are given, we de ne new knowledge SNEW that holds a new predicate. If a simple substitution has all predicate variables that occur in RS except X, then SNEW is de ned as follows : SNEW = RS( [ fX=N EW g).
The new predicate N EW is obtained by generating new knowledge SNEW . Here, the generated SNEW is determined uniquely by , RS, X, , and new symbol N EW . Therefore we can regard predicate generation in terms of sets of these ve tuple ( ; RS; X; ; N EW ). 3.2
Novelty Novelty is a property representing whether new knowledge is obtained as a logical conclusion based on existing knowledge or not. If SNEW satis es the condition that : for all s such that SNEW j= s and s includes N EW and 6j= s, then the predicate generation is said to possess novelty.
Consistency Consistency is the property by which new knowledge and existing knowledge are not in contradiction. With consistent predicate generation, we can take on [ SNEW as new knowledge instead of SNEW .
Soundness To be sound means that [ SNEW is consistent with all logical formulae which are consistent with and has no new predicates. If this condition is true, then we say that the predicate generation is sound or SNEW is sound. 3.3 Let
be knowledge and RS be a relation structure as follows:
= f8x : :bird(x) _ ab(x) _ f ly(x)g ; RS = <8 8x : :X0(x) _ X1(x) _ X2(x) 9
= 8x : :X3(x) _ X0(x) : 8x : :X3(x) _ :X2(x) ; 1 = fX0=bird; X1=ab; X2=f lyg 2 = fX0=f ly; X1=bird; X2=abg knowledge describes that birds y if not ab. See predicate variable X3, and consider two simple substitutions for predicate generation.
SN1 = <8 8x : :bird(x) _ ab(x) _ f ly(x) 9
8x : :N EW1(x) _ bird(x) = : 8x : :N eW1(x) _ :f ly(x) ; SN2 = <8 8x : :f ly(x) _ bird(x) _ ab(x) 9
= 8x : :N EW2(x) _ f ly(x) : 8x : :N EW2(x) _ :ab(x) ;
N EW1 is a new concept means such as " ightless bird", N EW2 means "not ab and f ly". SN1 has novelty and are consistent and sound. SN2 has novelty and is consistent but not sound. In fact, if l = :(8x : :f ly(x) _ bird(x) _ ab(x)), then ^ l is consistent, but ( [ SN2 ) ^ l is not. 4
Even if the predicate generation is inconsistent, it can be useful in expanding the knowledge dimension. For example, consider adding a concept describing imaginary numbers to real-number knowledge. The rule "the square of any number greater than or equal to 0" is inconsistent with the new knowledge, but serves to expand the dimension of real numbers to complex numbers, making it possible to regard new knowledge as consistent knowledge. This is a method for expanding the knowledge dimension naturally by predicate generation
Now, if C and ( C ) [ SNEW is consistent and C [ SNEW is inconsistent, consider C0 as follows.
>8 :inD(x11) _ C0 = < .
.
. >: :inD(xn1) _ _ :inD(x1l1 ) _ s01 9>
= _ :inD(xnln ) _ s0n ;> inD is a new predicate prepared here. s1; ; sn are elements of C , and xj1; ; xjlj are all bind variables occuring in sj. s01; ; s0n are formulae obtained by transforming s1; ; sn to prenex normal form and cutting out the head part. Each formula for C0 has a head part qj1xj1 qjl1 xjl1 that is the head part of the corresponding sj, although these are omitted here. qjk is 9 or 8, equal to a quali er of sj. We can imagine that inD(x) means x is in a dimension of former knowledge. ( C ) [ C0 [ SNEW is then consistent.
Theorem 1. For predicate generation ( ; RS; X; ; N EW ), if consistent then 0 = ( C ) [ C0 [ SNEW is consistent. and RS are 5
For predicate generation, it is important to consider whether the new knowledge represents a leap or not. The leap enable us to achieve our creative goal.
In de ning a creative leap, it is important to consider whether new predicates occur in generated consequence from the conjunction of new knowledge and existing knowledge. Formulae that have new predicates, cannot belong to unknown facts, so they are not appropriate as leap conclusions, because a new predicate is made by the system on its own.
Therefore, we de ne a Creative Leap as the case where there exist logical formulae not having N EW , such that [ SNEW j= s and 6j= s. Then, we say the predicate generation leaps.
Theorem 2. If predicate generation is not sound, then it leaps. 6
When a goal state, which is not derived from existing knowledge and it's negation is not derived either, is given, predicate generation with a creative leap can lead to the goal state as a consequence. Even if existing knowledge derives the negation of the goal state, expanding of dimensions enable to lead to the goal state. We call such problem solving Creative Problem Solving.
For example, human kind had wanted to y like a bird. And known that birds can y and the wing enables them, so create new concept like a wing. Example 1.
>8> 8x9y : Bird(x) ! Ha(sy(x:; Hy)a^s(Wx;iyn)g^(yW) ing(y)) =>>9 f = < 8x : Human(x) ! : 9
>:> 88xx;:yW: Hinags((xx); !y) ^W WinignBgeBheahvaiovrio(rx()y) ! F ly(x) >>; is given, and goal Gf = 8x : Human(x) ! F ly(x). Then f cannot lead to Gf as a consequence. Then we consider RS as follows:
RSf = 8< 8x9y : X1(x) ! X2(x; y) ^ X3(y) 9
= 8x; y : X2(x; y) ^ X4(y) ! X5(x) : 8x : X3(x) ! X4(x) ; The simple substitution f as follows:
f = fX1=Human; X2=Has; X4=W ingBehavior; X5=F lyg Predicate generation ( f ; RSf ; X3; f ; N EWf ) then generates SNEWf as follows :
SNEWf = 8< 8x9y : Human(x) ! Has(x; y) ^ N EWf (y)
8x; y : Has(x; y) ^ W ingBehavior(y) ! F ly(x) : 8x : N EWf (x) ! W ingBehavior(x) 9 = ; SNEWf possesses novelty and is consistent but not sound. SNEWf derives Gf . Gf was not obtained by f , therefore, a new predicate is generated to derive the goal state by using a creative leap. N EWf was not generated randomly, and may ful ll W ingBehavior like a bird's wing. 6.1
When a goal state is given, what prepared for generation is f only. The important topic is how to prepare a relation structure and which simple substitutions and predicate variables to choose. The problem of what predicate should be generated and what relation structure should be prepared is di ers for each purpose and each case. We show a general method of extracting relation structures from knowledge, and present one of the methods for preparing RS, , and X.
The relation structure can be gained by generalizing knowledge. Concretely, replacing all or some predicate constants occurring in knowledge (or a subset) with free predicate variables.
Next, the point is which RS, , and X are chosen. The destination is to derive G from [ SNEW . We propose a method of extracting relation structure from an explanation structure inherent in existing knowledge.
Now, for a knowledge , let RS( ) be a relation structure obtained by replacing all of the predicate constants in with each independent predicate variables.
If there exists such that : 9 : RS( ) j= RS(G) , then we can consider predicate generation using RS( ) as a relation structure. This RS( ) is an explanation structure that derives a result with the same structure as G. New knowledge possossing the same explanation structure may be obtained by using another simple substitution to derive G. It can be thought this method is based on analogy as common structure.
Example 2. Only knowledge f8x : X1(x) ! X2(x)g, and f and goal state Gf are given. Here, RS(Gf ) = f including RS(Gf ), can be taken : so we can obtain RS( f ) in concert with RS(Gf ) as : RS( f ) = RSf .
Let = fX1=Bird; X2=F ly; X3=Has; X4=W ing; X5=W ingBehaviorg, then RS( f ) j= RS(Gf ) . De ne simple substitution 0 as follows : 0 = f . Then, predicate generation ( f ; RS( f ); 0; X4; N EWf ) produces SN0EW : SN0EW = SNEWf . Leap is realized and goal state Gf is derived from SN0EW . 7
This paper proposed a formulation of concept generation, and an approach to creative problem solving. A creative leap shows the new predicate is not a mere paraphrase but achieves a new result.
We may note here that creative problem solving is similar to abduction in the sense that it is a method of deriving a goal by generating new knowledge. If the goal state is observed facts, we can regard creative problem solving as abduction accompanied by concept generation. However, creative problem solving is a more general method.
Our example of creative problem solving was the simulation of the invention of something like an airplane. Though not every invention can be described using this frame, it is very interesting that creative problem solving can simulate a part of human's creative knowledge processing and invention.
However, many problems need to be solved to develop a practical system with creative problem solving. The problem of calculating of new-knowledge consistency, determining which structures and predicate variables are important, and selecting simple substitutions, among other factors, are important for practical systems. Some of these problems (perhaps most of them) are depend on speci c systems.
We showed logically that concept generation may achieve creative knowledge processing. We expect to achieve a fully creative system in future work.