A FORMAL SYSTEMS APPROACH TO SOLVER DESIGN HILL CLIMBING METHOD WITH PUSH DOWN STACK Yasuhiko TAKAHARA1
Yongmei LIU2
Yoshio YANO1
1
Depertment of Management Information Science,
Chiba Institute of Technology, 2-17-1 Tsudanuma, Narashino, Chiba, Japan 2
College of Business, Central South University, Changsha, 410083, P.R. China
[email protected]
[email protected]
[email protected]
Abstract This paper presents a formal approach to design of a solver of an intelligent management information system and its implementation. The approach implies set theoretic modeling based on the general systems concepts and implementation in the extProlog. There are research efforts which attack (optimization) problems using the set theory and logics. Furthermore, they use logic programming languages for their implementation. Although their methods look quite similar to the approach of this paper, there are clear differences between them. This paper is interested in exploration of the solving system rather than algorithms. The paper first presents a design and implementation procedure of a solver. Then, classification of problems is discussed. The least structured class of the classification is the target of this paper. A data mining system is an example of the class. Formal theories are derived for the design procedure assuming the least structured case. A solving strategy, which is called a hill climbing method with a push down stack, is proposed on the theories. A data mining system is used as an example to illustrate the results. Finally, a full implementation in extProlog is presented for the data mining system. Keywords: Solver, hill climbing, push down automaton, systems approach, set theory, Prolog
1. Introduction Let us start from explaining why we will discuss a solver in this paper and what we mean by a formal systems approach. Our research interest is in an MIS (management information system) in general and in developing a formal systems theory for an intelligent MIS in particular. Since an MIS is a system, there must be a proper system theory for ISSN 1004-3756/03/1202/138 CN11- 2983/N ©JSSSE 2003
it. Figure 1 shows our specific model of an intelligent MIS. The solver of this paper constitutes a significant part of this model. The model consists of three parts, TPS (transaction processing system), problem solving system and data transformation system. In the model the TPS is represented as an automaton model where the DB (data base) saves the current state while DPS (data processing system) presents the state transition JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING Vol. 12, No.2, pp138-158 June, 2003
TAKAHARA, LIU and YANO
function (Takahara and Kubota 1988). The data transformation system transforms data of the TPS into information in two ways, abstraction (aggregation) and data mining (Takahara, Shiba, et al. 1988, Takahara, Liu, et
al. 2002). The information is, then, used by the problem solving system. The problem solving system consists of three layers, problem solving layer, adaptive layer and user layer (Takahara and Shimizu 1996).
problem/self-organization
user
request/supplementary information
secondary solution
problem solving system adaptation
ADPS primary solution
PSE
extSLV mined rules
aggregated data
secondary data
abstraction
TPS
data mining data transformation system
primary data DB
response transaction input
DPS
Figure 1 Model of intelligent MIS The problem solving layer is further The output of the extSLV is a solution. The decomposed into two components, PSE solver of this paper is the extSLV. (problem specification environment) and extSLV Our research program is to establish a formal (extended solver). The PSE specifies parameters and “usable” systems theory for the MIS of or a structure of a problem to be solved. In Figure 1. Since the TPS is modeled as an general the PSE does not specifies a problem. A automaton, Ref. (Takahara and Kubota 1988) problem is identified and solved in the extSLV, derived a formal theory for it. Ref. (Takahara, whose function is an extension of a usual solver. Shiba, et al. 1988) illustrated how the data
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
139
A Formal Systems Approach to Solver Design
mining system can be handled in accordance with the research program. It is, then, a natural step to proceed to try to develop a formal systems theory for the problem solving layer. Since the extSLV is a principal component of the problem solving layer, this paper will investigate design and its
implementation of the extSLV as an initial trial of the research.
2. Development Methodology for Solver Design Figure 2 shows the scheme of the systems approach to a solver design of this paper. extProlog
Input output specification of extSLV
Automaton (generator) formulation of solving process
Implementation in extProlog
MGST methodology: goal seeking system; set theory Figure 2 Systems approach to extSLV the extProlog, which our group is developing by As Figure 2 shows, the development method extending the conventional Prolog to meet includes implementation as a part of its theory in requirements caused from the implementation. order to make itself a “usable” theory. There are research efforts which look similar The input of the approach is an input output to this paper. Since Ref. (Cantone and Onodeo, specification of an extSLV whose input is a et al. 1996) deals with discrete systems in the set problem specification environment and whose theory, it develops an automaton model for the output is a solution. The input output systems engineering. But it is mainly concerned specification is transformed into an automaton with the process of Figure 4. Our approach (generator) formulation. The transformation is addresses the goal seeking (problem solving) carried out by the MGST (mathematical general aspect as well as the process behavior. systems theory) methodology, whose model Furthermore, implementation is a part of the building is done using the set theory and GST theory in our case. Ref. (Hooker 2002) attack concepts. As the subsequent discussions show, (optimization) problems using the set theory and various functions must be defined to build an logics. Furthermore, they use logic extSLV. The set theory of this paper includes the programming languages for their function definitions by the primitive recursion implementation. Then, their methods and the and the minimization of the recursive function approach of this paper look same but there are theory as well as the conventional function also clear differences between them. First, the composition. former researches are concerned with mainly a Implementation of the design is addressed by
140
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
problem itself or an algorithm to solve the problem while the latter is concerned with exploration of the structure of a solving system of a problem. This is a fundamental difference. Second, then, classification of problems is different between them. In the algorithm oriented theories problems are supposed to be defined on numerical spaces (say Euclidean spaces) and are classified as linear or non-linear problems or convex problems. The classification of the latter approach, as will be introduced
below, depends on the structure of a problem. Then, third, it is natural that a solving algorithm should be different between them. Since the latter approach tries to reveal the structure of a solving system, its algorithm is typically procedural, which clearly distinguish it from the constraint programming where a declarative treatment of a problem is emphasized. The approach shown in Figure 2 is expanded as a more detailed procedure in Figure 3. 1
input-output block diagram
6
2 input-output specification in set theory
implementation in extProlog
3 5 generator formulation by unified goal seeker
4
process specification as automaton
dynamic optimization formulation
Figure 3 Design and implementation procedure It consists of 6 stages, input-output block the generator formulation of Figure 3 diagram, input-output specification in the set [Mesarovic and Takahara 1989]. Figure 4 shows theory, process specification as automaton, the goal seeking system. dynamic optimization formulation, generator The goal seeking system consists of two formulation and implementation in extProlog. components, process and goal seeker. The These stages will be discussed in detail in Chap. process component is not a physical model as 4 and Chap. 5. the case of the control engineering but an The approach of this paper is based on the abstract model of a problem solving process. It goal seeking system of the GST. It is a basis of will be represented as an automaton model. The
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
141
A Formal Systems Approach to Solver Design
process has two inputs, a problem specification input and a parameter. They are external and internal inputs, respectively. Since the problem specification is supposed to be fixed during the problem solving activity, the total system behaves as a generator. The parameter is a control variable or a decision action. The output of the process is a state. The goal seeker specifies a value for the control parameter a to achieve a given goal g using the state information c. It yields a solution y.
The goal seeker will be determined by a solving activities of a dynamic optimization problem. A basic solving strategy of the problem is designed in two ways in our research, hill climbing method in a push down automaton and DP (dynamic programming) method. Since these techniques may be compared to the depth first and the width first techniques on a tree search, respectively, they can be considered to cover the whole basic strategies in general.
generator g:goal goal seeker
a
solution y∈Y;output
c
problem spec. state transition fixed
process δ state
Figure 4 Generator model by goal seeking system
data set, constraints
extSLV for data mining system problem
class of rules
Figure 5 Data mining system problem
3. Formal Representation of extSLV for I-O-O Case This chapter will discuss a formal presentation of the development stages of Figure 3.
142
3.1 Input-Output Block Diagram This stage presents a conceptual description of a target extSLV specifying the PSE (problem specific environment) and the solution (output). Figure 5 illustrates an input-output block
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
diagram of the data mining system problem. A data mining system is to discover a class of rules which describes implications of a given data set. The constraints of the input are used to specify meaningful rules.
3.2 Input-Output Specification in the Set Theory At this stage the input PSE and the output solution are described in the set theoretic terms. It is usual that the PSE is represented by a structure rather than simple sets. The output set is a set of solution candidates. Then, Input structure:
Output set: Y. Sometimes, a structure, for instance, a preference relation ≤ is assumed on Y, i.e., . Chap. 5 will show a set theoretic representation of the input and the output for the data mining system problem.
3.3 Process Specification as Automaton At this stage the process δ of the goal seeking system of Figure 3 is determined as an automaton. For a problem of implicit solving activity δ:Y×A→Y is defined in the following way: Let A⊂{a|a:Y→Y} such that δ(y,a)=a(y). We will use a symbol C for a state set or C=Y in the current situation. δ is in general a partial function. In order to assure that δ behaves properly, two functions will be used. genA:C→℘(A) and constraint:C→{T,F}
where ℘(A) is the power set of A. genA specifies allowable or relevant activities for a given state while constraint determines whether a state is permissible. genA(c) is assumed a finite set for each c. An effectiveness of a solver is strongly affected by definition of genA. For the knapsack problem any jewel can be put into the knapsack but the generated state may be prohibited due to the problem restriction. The constraint is used to check this situation. δ must satisfy δ(c,a)=c'→a∈genA(c)and constraint(c')=T. The output function λ:C×A→Y is given by λ(y,a)=y. Let the initial state be c0∈C. Usually, a trivial state is used to specify c0. Obviously, constarint(c0)=T. In the case of I-O-O targets states are not given a priori. If they are specified by some heuristics, they will be denoted as Cf ⊂ C. In many cases of I-O-O including the data mining case Cf can be specified as Cf={c|(∀a∈A)(δ(c,a) is undefined)}. The automaton specification of the process is, then, given as automaton specification of process=< A, C,Y,δ, λ, genA, constraint, c0, Cf >
3.4 Dynamic Optimization Formulation Since a state transition function is a discrete state space representation, if an evaluation function g:Y→Re is introduced, we have a dynamic optimization problem, where Re is the set of reals. Since the current problem is of the I-O-O type, there is no legitimate goal for the problem.
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
143
A Formal Systems Approach to Solver Design
We assume, however, that some goal g is introduced from a heuristic consideration. We assume also that a goal g is specified in the way that g(y) is more desirable if it is larger. If Y has a preference relation, it is desirable that the following compatibility relation holds: y≤y' → g(y) ≤ g(y'). Naturally, this relation cannot be always satisfied in practices. A dynamic optimization formulation of the process is, then, given as below. dynamic optimization formulation=< A, C,Y,δ, λ,g, genA, constraint, c0, Cf > where δ:C×A→C; state transition function, λ:C×A→Y; output function, g:Y→Re; g→maximization, genA:C→℘(A); allowable activity function, constraint:C→{T, F}; constraint, c 0 ∈ C ; initial state, Cf⊂C; set of final states.
4. Generator Formulation by Unified Goal Seeker– Decomposition of extSLV This chapter will develop a goal seeker for the structure < A, C,Y,δ, λ, g, genA, constraint, c0, Cf >. Since the goal seeker developed for the structure can be applicable to any problem if it is formalized into the structure, the goal seeker will be called a unified one. This fact shows a decomposition theory for an extSLV because it is a combination of a formalized problem and a unified goal seeker. In general, a goal seeker is a mapping σ:C → A. Then, combining σ and δ we have πσ:C → C where πσ(c)=δ(c,σ(c)).
144
π σ is an expression of the total system, extSLV, which is called generator because it does not have an external input. A goal seeker cannot be obtained in a simple way for an information system because of its ill-structured constraint. If πσ takes the extSLV to a state c where no feasible action is available, i.e., genA(c)=φ, the system cannot proceed anymore. For instance, the situation is clear if we imagine a maze problem. Sometimes such a dead lock situation implies a solution (target) state, which is an exceptional case while in general it is not a desirable situation. This chapter will investigate a general case of the goal seeker. One way to avoid such a dead lock situation is to equip the strategy with a push down stack for back tracking. If the system meets a dead lock situation, it must return to a previous state to proceed in another direction. A strategy can be designed using combination of the hill climbing method and a push down stack. This is the strategy of the unified goal seeker of this paper. Figure 6 illustrates the structure of an extSLV by the hill climbing method with a push down stack. Let us start from introducing necessary concepts to investigate Figure 6. Definition 1 legalAs: C→℘(A*) Let us define a function legalAs:C→℘(A*): For c∈C a1a2...ap∈legalAs(c) iff δ(c,a1)=c1 & a1∈genA(c) & constraint(c1)=true & δ(c1,a2)=c2 & a2∈genA(c1) & constraint(c2)=true & δ(cp-1,ap)=cp & ap∈genA(cp-1) & constraint(cp)=true.
M
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
extSLV goal seeker σ problem specification
process δ
goal
a
strategy
µ
c γ*
solution
γ
push down stack
decomposition Figure 6 extSLV by hill climbing method with push down stack Definition 2 Solvable state and unsolvable defined as follows: Let c∈∪Ck. Since state i≠j→Ci∩Cj=φ, there is a unique p such that c∈C is called a solvable state iff c∈Cp. Then, (∃α∈legalAs(c))(δ(c,α)∈Cf). genA*(c)={a|a∈genA(c) & δ(c,a)∈Cp+1}. c∈C is called an unsolvable state iff c is genA* will be called restricted allowable not solvable, i.e., (∀α∈legalAs(c))(δ(c,α)∉ Cf). activity function. Definition 6 Solution path and efficient Definition 3 Layer structure {Cp}p on C solution path A class of subsets, {Cp}p, Cp⊂C (p=0,1,2,…) α ∈ legalAs(c0) is called a solution path iff will be defined recursively. Let C0={c0}; δ(c0,α)∈Cf ⊂ C. Cp+1={c'|(∃c∈Cp)(∃a∈A)(a∈genA(c) α =a1a2...ap ∈ legalAs(c0) is called an & δ(c,a)=c' & constraint(c')=true)}- ∪{Cr| efficient solution path iff α is a solution r≤p}. path and satisfies the following relations: The class {Cp}p will be called layer structure δ(c0,a1)=c1∈C1 on C. δ(c1,a2)=c2∈C2 Definition 4 Linear order relation ≤ on ∪ Ck M Let c, c'∈∪Ck be arbitrary. Then, there are p δ(cp-1,ap)=cp ∈Cp=Cf and q uniquely such that c∈Cp and c'∈Cq. Let where for i
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
145
A Formal Systems Approach to Solver Design
that for any solvable c∈C a∈backtrack(c) iff a∈genA(c) and δ(c,a) is a solvable state. The goal g will be used to select an action among genA(c) for a state c. Then, it need not be compatible with the order of C. However, if it is compatible, it will be shown to derive stronger results. We use the following compatibility condition. Definition 8 Compatibility condition for g A goal is said to satisfy a compatibility condition iff it satisfies the following relation: For c,c'∈∪Cp g(c) ≤g(c')↔c≤c'. Notice that Y=C and since ≤ on C is a linear order, y≤y' →g(y) ≤g(y') implies y≤y' ↔g(y) ≤g(y'). Definition 9 Strategy of the hill climbing method with push down stack:σpd:∪Cp→A Let σpd:∪Cp→A be σpd(c)=a* where a* ∈backtrack(c) and satisfies max{g(δ(c,a))|a∈backtrack(c)}=g(δ(c,a*)). Then, σpd will be called strategy of the hill climbing method with push down stack. The goal seeker of this paper is characterized by σpd. It should be noticed that σpd can be defined even if g is not compatible. σpd is not a simple feedback law because it requires a backtrack operation to assure δ(c, σpd(c)) is a solvable state. The following concept is already introduced informally. Definition 10 Dynamical mapping: πσ:C→C Let σ:C→A be a strategy. Then, let πσ:C→C be πσ(c)=δ(c,σ(c)). πσ is called dynamical mapping of σ. Definition 11 Loop free strategy
146
A strategy σ:C→A is called loop free if it satisfies (∀p,q)(p≠q →πσp(c0)≠ πσq(c0)). The following is an obvious but a fundamental fact for problem solving. Theorem 1 Suppose C is finite and the initial state is solvable. Then, if a strategy σ is loop free, there is p such that πσp(c0)∈Cf or it yields a solution. Proof. Let Cp={c0, πσ(c0),…, πσp(c0)}. Since σ is loop free, C1⊊C2⊊…⊊Cp. Since C is finite, Cp∩Cf≠φ for some p. Q.E.D. The following is also intuitively clear. Proposition 1 Let c∈Cp be arbitrary. Then (∀α)(∃q)(α∈legalAs(c) & δ(c,α)=c'→c'∈Cq). Proof. We use the mathematical induction. (i) Suppose α=a∈legalAs(c). Then, a∈genA(c) and constraint(δ(c,a))=true. Let c'=δ(c,a). Due to the definition of Cp+1 c'∈ Cp+1 ∨ c'∈∪{Cr| r≤p}. If c'∉Cp+1, then (∃r)(c'∈Cr). (ii) Suppose if length(α) ≤ l, δ(c,α)∈Cq for some q. Let β=αa and length(β)=l+1 where a∈genA(δ(c,α)) is arbitrary. The induction hypothesis implies δ(c,α)∈Cq for some q. Then, the argument (i) implies that δ(δ(c,α),a)∈Cq+1 or δ(δ(c,α),a)∈Cr for some r. Q.E.D. The following is also a fundamental fact for the methodology of this paper. Proposition 2 Let α∈legalAs(c0) be arbitrary. Let c'=δ(c0, α). Then, (∃α'∈legalAs(c0))(α'=a1...ak & δ(c0,a1,..,ai)∈Ci for each i & δ(c0,α')=c'). Proof. Because of Prop. 1 there is k such that δ(c0,α)=c'∈Ck. Since c'∈ Ck={c'|a∈genA(c) &
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
δ(c,a)=c' & c∈Ck-1 & constraint(c')=true}}∪{Cr| r≤k-1}, c'=δ(ck-1,ak) & ck-1∈Ck-1 & ak∈genA(ck-1) & constraint(c')=true. Since ck-1∈Ck-1, there exist ck-2 and ak-1 such that ck-1=δ(ck-2,ak-1) & ck-2∈Ck-2 & ak-1∈genA(ck-2) & constraint(ck-1)=true. In this way we can find a1,a2,...,ak, c1,...,ck-1 such that δ(c0,a1)=c1∈C1 & a1∈genA(c0) & constraint(c1)=true, δ(c1,a2)=c2∈C2 & a2∈genA(c1) & constraint(c2)=true,
M
δ(ck-1,ak)=c'∈Ck & ak∈genA(ck-1) & constraint(c')=true. Consequently, α'=a1...ak∈legalAs(c0), δ(c0,a1...ai)∈Ci and δ(c0,α')=c'. Q.E.D. Then, Theorem 2 There is a solution path iff an efficient solution path exists. Proof. The if part is obvious. The only if part comes from Prop. 2 where c'∈Cf. Q.E.D. We will characterize an efficient solution path. The following should be obvious. Corollary 1 Suppose α =a1a2...ap ∈ legalAs(c0) is a solution path. Suppose α satisfies the following relations. δ(c0,a1)=c1∉C0, δ(c1,a2)=c2∉C0∪C1,
M
δ(cp-1,ap)=cp ∉∪{Ck|k
order of C) on the way to a target state. The following should be also obvious. Corollary 2 Suppose α =a1a2...ap ∈ legalAs(c0) is a solution path. Suppose α satisfies the following relations. a1∈genA*(c0), a2∈genA*(c1) where δ(c0,a1)=c1, a3∈genA*(c2) where δ(c1,a2)=c2,
M
ap∈genA*(cp-1) where δ(cp-2,ap-1)=cp-1. Then, α is an efficient solution path. Q.E.D. When g is compatible, we have strong results for σpd,. Proposition 3 Let c∈Cp is solvable. Suppose g is compatible. Let a*∈σpd(c) where σpd is a strategy of the hill climbing method with a PD stack. Then, δ(c,a*)∈ Cp+1. Proof. Since c is a solvable state, Prop.2 asserts that there is α=a1…ak∈legalAs(c) such that δ(c,a1)=c1∈Cp+1, δ(c1,a2)=c2∈Cp+2,
M
δ(ck-1,ak)=ck∈Cf. Since a1∈genA(c) and δ(c,a1) is a solvable state, c<δ(c,a1) implies g(c)
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
147
A Formal Systems Approach to Solver Design
Finally,
it may indicate that the goal seeker has reached a
Theorem 3 σpd of the hill climbing method
final state. (Refer to the definition of Cf in Chap.
with a push down stack always yields an
5.) In either case the operation of the goal seeker
efficient solution path if the initial state is a
must finish. If the trial is successful, the goal
solvable state and g is compatible.
seeker gets (c,As,H), current state, set of
In practices there are two ways to derive an
available actions ⊂ genA(c) and history of the
efficient solution path. The first is to use Cor. 1.
visited states as the top information. It then
Cor. 1 says that an efficient solution path is
selects (a*,RA) where a*=σ(c) and RA=As-{a*}.
produced if a next state ci is found outside of
a* is assumed to satisfy the relation
∪{Cp|p
max{g(δ(c,a))|a∈As}=g(δ(c,a*)).
memorize ∪{Cp|p
δ(c,a*) must not be equal to an element of H
of memory, it may yield difficulty with respect
(Refer to Th. 1). If c is a dead lock state, a*=[] is
to computation and memory. Then, if we use a
assumed. In this case the goal seeker must do the
heuristic that the history H of the visited states
back track operation, that is, pops up the next
may cover an essential part of ∪{Cp|p
information.
used, H may be substituted for ∪{Cp|p
Notice that it can be proved by the
general, this heuristics may be helpful because H
mathematical induction that if a0*a1*...ap* is a
must be used in order to make a strategy loop
solution generated by the extSLV, the following
free.
property holds:
The second is to use Th. 3. In that case the goal g is required to be compatible. Although the
max{g(δ(ci,a))|a∈backtrack(ci)}=g(δ(ci,ai*)) where ci+1=δ(ci,ai*).
compatibility condition might be considered to
If a* is a regular action (a*≠[]), the goal
hold only in an exceptional case, it is not
seeker applies a* to the process δ to get the next
necessarily true. If a target problem belongs to
state cc=δ(c,a*). It generates the set of available
the class of implicit solving action and a:Y→Y
activities As2 for the next state cc. If cc∈Cf or
is selected as an action to improve an output y
st(cc)=true
and if the goal g is defined to reflect the degree
process must finish. If cc∉Cf, the goal seeker
of improvement, the compatibility condition
saves (push down) two information, (c,RA,H)
holds.
and (cc,As2,H2) where H2=H⋅c, i.e., the current
The
data
mining
system
problem
corresponds to this case. Figure 7 shows the total process of a unified goal seeker based on Cor. 1 and Th. 3. Every information to yield an action σ(c) is stored in a push down stack. The goal seeker,
(stopping
condition),
the
total
state c is appended to H. The former information (c,RA,H) will be used when the goal seeker does back track to the state c. The latter information is used at the next state cc. Then, it goes to the pop up stage.
first, tries to pop up the top information. If the
The total system, extSLV, which consists of
trial fails, in general it indicates failure of the
the goal seeker and the process δ, is formalized
goal seeker. However, in the case of open target,
as a generator:
148
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
extSLV
yes stack = [ ]?
end/fail
no (y, As, H) ← popup(stack)
(a * , RA) ← µ(c, As, H) yes
goal: g(c)
a* = [ ]?
(back track)
no cc← δ(c, a*)
As2 ← genA(cc), H2 ←H·c
st(cc) = true ?
yes
no pushdown((c, RA, H)(cc, As2, H2))
end
Figure 7 extSLV by unified general goal seeker based on Cor. 1 and Th. 3 extSLV= where Stack is the state set and (c0,genA(c0),[],[]) is an initial state. Stack, solProc:Stack→Stack and st:C→{true,false} are defined in the following way. Let Γ=C×℘(A)×H×Sol; stack element, H=C*; history of states, Sol=S*; history of actions,
Stack=Γ*, where Sol is used as an auxiliary variable for error checking. Then, µ:Γ→A×℘(A) is (a*,As-{a*}) if max{goal(δ(c,a))| µ (c,As,ϕ,α) = a ∈ As & constraint(δ(c,a)) = true}= goal(δ(c,a*)) ([],[]) o.w. In the definition of µ the condition a*∈backtrack(c) is not required because the
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
149
A Formal Systems Approach to Solver Design
condition “δ(c,a*) is a solvable state” is supported by the back tracking as mentioned above. solProc:Stack→Stack is γ*γn'γn+1 solProc(γ*γn)= if µ (γn)=(a*, RA) and a*≠[] γ* o.w. where γn=(c,As, ϕ,α), γn'=(c,As-{a*}, ϕ,α), γn+1=(δ(c,a*),genA(δ(c,a*)), ϕ⋅c,α⋅a*). st:C→{true,false} is st(c)=true↔c∈Cf. The extSLV is actually a push down automaton without input. ID code D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 D15 D16 D17 D18 D19 D20 D21 D22 D23 D24
lenses none, soft, none, hard, none, soft, none, hard, none, soft, none, hard, none, soft, none, none, none, none, none, hard, none, soft, none, none,
age young, young, young, young, young, young, young, young, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic,
A part of the corresponding output is as follows: If age=pre_presbyopic then lenses=none with confidence 6.2500e-01 and support
150
5. Example by Data Mining System Problem The general design procedure mentioned in Chap. 4 will be illustrated by using the data mining system problem. Although a data mining system problem is very important in practice, it is a rather simple problem in theory as will be shown below. The example is, however, selected in order to emphasize practicality of the method of this paper. (i) Input-Output Block Diagram Figure 5 shows an input output block diagram of the data mining system problem. In particular, the following data set will be used as an example (Witten and Frank 1999). prescription myope, myope, myope, myope, hypermetrope, hypermetrope, hypermetrope, hypermetrope, myope, myope, myope, myope, hypermetrope, hypermetrope, hypermetrope, hypermetrope, myope, myope, myope, myope, hypermetrope, hypermetrope, hypermetrope, hypermetrope,
astigmatism no, no, yes, yes, no, no, yes, yes, no, no, yes, yes, no, no, yes, yes, no, no, yes, yes, no, no, yes, yes,
tear reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal
5.000000 If age=presbyopic then lenses=none with confidence 7.5000e-01 and support 6.000000 If prescription=hypermetrope then
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
lenses=none with confidence 6.6667e-01 and support 8.00000 If astigmatism=yes then lenses=none with confidence 6.6667e-01 and support 8.00000 If tear=reduced then lenses=none with confidence 1.0000e+00 and support 12.00000 If age=young and tear=reduced then lenses=none with confidence 1.0000e+00 and support 4.000000 If age=pre_presbyopic and prescription =hypermetrope then lenses=none with
input:
confidence 7.5000e-01 and support 3.000000 If age=pre_presbyopic and astigmatism=yes then lenses=none with confidence 7.5000e-01 and support 3.000000 The confidence level=0.6 and the support level=2 are used. (ii) Input-Output Specification in the Set Theory Figure 8 illustrates Stage 2 of the data mining system problem.
SLV for
output: y∈Y
data mining Figure 8 Input-output specification in the set theory of the data mining system problem The input is given by a structure V=∪VLst , and whose components are specified below. V+= V2∪…∪Vn. a. Let the attribute list of the given data be: c. Let ALst={ai|i ∈ Ia} (Ia={1,2,…,n}) X=℘(V1 ×…×Vn) (the power set of V1 where a1 is a conclusion or the output ×…×Vn) attribute and a2,…,an are input attributes. and D0 ∈ X: input data set of data mining. Ia is ordered with respect to the usual order. D0 is a given target data set to which data Let mining is applied. + Ia = Ia−{1} The output set Y is a class of sets of rules. Let a rule r be represented as and + + ALst ={ai|i ∈ Ia }. r ∈((ALst+×V)*×V1×Re×Int). b. Let If r=((a',v')…(a",v"),v1,r,n), it implies the Vi=dom (ai): domain of ai or value set of ai following rule: where if a'=v' and…and a"=v" then a1=v1 with i Vi={vij| j ∈ Iv }. confidence r and support n. Then, since y∈Y is a set of rules, Let VLst={V1,...,Vn}. y∈℘((ALst+×V)*×V1×Re×Int), Let or
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
151
A Formal Systems Approach to Solver Design
Y⊂℘((ALst+×V)*×V1×Re×Int). (iii) Process Specification as Automaton Although the input set A was defined as a subset of {a|a:Y→Y} or a∈A is a mapping, a will be represented as a parameter to specify a mapping from Y to Y. Let A=℘(ALst+), or a∈A is a subset of ALst+. In order to avoid confusion an element of A will be typically denoted by As∈A. The fact that As∈A is a set rather than a simple element makes a representation of the data mining system complicated although its structure is simple. If As∈A is applied to y∈Y, As creates new rules from y refining elements of y or the number of total rules increases. This is the desired improvement of the output. Roughly speaking, the rule creation is done as follows: Suppose a'∈As⊂ALst+ and r is a rule. a' is an attribute. Then, application of a' to r creates a new class of rules whose conditional parts are extended to include the attribute a'. In this creation stage the confident condition is ignored. Let us consider the following example: Let r be “If age=pre_presbyopic then lenses=none with support 5”. Notice that the confidence part of the rule is neglected. If a'=“prescription”, one of the created rules may be: “If age=pre_presbyopic and prescription=hypermetrope then lenses=none with support 3”. Since dom(prescription)={myope, hypermetrope}, two rules may be created from r (prescription=myope or prescription=hypermetrope ) if they satisfy the support level.
152
Let the new rule be denoted by (a',v')(r). In the above example v'= hypermetrope. Then, the class of rules created by As⊂ALst for each y is represented as follows: create(As,y)=∪{∪{{(a',v')(r)|v'∈dom(a')}|r ∈y}|a'∈As}. Then, As(y), the total rule set generated by As, is given by As(y)=y∪create(As,y). Let us represent the idea formally. Since a nested set definition is not implemented in the current extProlog, δ:C×A→C is given by the following three functions, δ1, δ2 and δ3: δ1:C×ALst+→℘(C), δ2:Rule×ALst+→℘(Rule), δ3:Rule×(ALst+×V)→Rule where Rule= ((ALst+×V)*×V1×Re×Int). Then, δ(y,As)=∪{δ1(y,a)|a∈As}∪y; δ1(y,a)=∪{δ2(r,a)|r∈y}; δ2(r,a)={r'|δ3(r,(a,v))=r' & v∈dom(a)}; ( α(a,v),v1, conf,n') δ3((α,v1,conf,n),(a,v))= if a∉dom(α) and n'≥supL Λ o.w. where As∈A, α∈(ALst+×V)*, dom(α)={a|(∃v)((a,v)∈α)} and n' is the number of entries in D0, which satisfy α, a=v and a1=v1. Notice that the confidence conf is dummy because the confidence condition is ignored at the rule creation stage. The confidence condition is taken care of by λ:C×A→Y. Let λ1:Rule→Rule be (α,v1,conf',n) λ1(α,v1,conf,n)= if conf'≥confL Λ o.w.
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
conf' is the real confidence value of the rule (α,v1). Then λ (c,As)={λ1(r)|r∈c}. genA is given as genA(c)={ALst+}. The above definition of genA comes from the fact that the data mining is an exceptional case where since As⊂As'→δ(y,As)⊂δ(y,As') for any y, an optimal solution of the hill climbing strategy with respect to the goal given below is explicitly known as {ALst+} from the beginning. constraint:C→{true,false} is given by constraint(y)=true iff no duplication in y & (∀r∈y)(no duplication in attr(r)) & (∀r∈y)(support(r)≥supL and confidence(r) ≥ confL) where support(α,v1,conf',n)=n and confidence(α,v1,conf',n)=conf'. The last constraints are included in δ3 and λ1. The initial state c0∈C is given by the most trivial situation; c0=φ; empty set. Finally, let target states Cf⊂C be specified as y∈Cf↔(a∈A)(δ(y,a) is undefined). In other words, the dead lock situation is a target state where the largest set of rules is created, which comes from the specification of genA. This is another peculiarity of the data mining system example. The process of the data mining system problem is given by an automaton . In the current formulation c≤c' iff |y|≤ |y'| . (iv) Dynamic Optimization Formulation Since a goal of the data mining system problem can be assumed to produce the
maximum set of rules, the goal g:C→Re is specified by the following: g(y)=|y|. Due to the definition of ≤ on C the following relation hold: c ≤ c'↔g(c)≤g(c'). That is, the goal satisfies the compatibility condition. (v) Generator Formulation The generator is independent of a problem.
6. Implementation An extSLV for the data mining system problem is obtained by implementing the formulation in Chap. 5 in extProlog. A detailed discussion about the extProlog is presented in Ref. (Takahara and Liu 1999). Appendix presents a complete list of an extSLV of the data mining system problem except the implementation of λ. The following comments may be helpful to understand the implementation. (i) Rule: The extProlog allows a frame representation of a data structure. A rule is represented by a frame where the real data set is stored in dlist instead of the support number, which makes processing of δ efficient. (ii) State: Since genA(c)={ALst+} is a singleton set, Cp={cp} is also a singleton set. cp is a set of rules whose conditional part has the length of p. That is, if r∈c1, r takes the form: if a'=v' then a1=v1 with confidence conf' and support n. Then, y or state c is layered as c=c0∪c1∪…∪ck and cp+1 is obtained by applying ALst+ to cp. In the implementation, then, the state is trivially represented by c=[k, k–1,…,0], where p
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
153
A Formal Systems Approach to Solver Design
corresponds to cp, and cp is by the predicate “state(p,[r1,…,rs])” where ri is the identifier of a rule in cp or the identifier of the frame of the rule. (iii) Goal Seeker: Figure 7 is faithfully implemented for the goal seeker except that the back track path is neglected because there is no back track due to the special form of genA. (iv) Relation: A relation is represented as a predicate or a set of facts. (v) Function: A function is represented as a relation. Although a conventional Prolog cannot admit a function, the extProlog allows a relation to be used as a function. The “function” declaration illustrated in Appendix specifies which predicates can be used as functions. For instance, the predicate “element” is declared as a function. Then, it can be used as a function although it is defined as a predicate. (vi) Set: A set is represented as a list. Only problem with the convention is that a list has an order among its elements although a set does not have. Then, the equality check between sets cannot be made simply. A program always sorts lists before making the equality check of sets. (vii) Generator: A generator, which is nothing but a function definition by the primitive recursion, is implemented simply by a recursive call. For instance, let , delta:C→C, be a generator whose stopping condition is st:C→{T,F}. Then, it is implemented as process(C,C2):delta(C,CC), if st(CC)=T then C2:=CC else process(CC,C2) end; (viii) Minimization: If the minimization is used,
154
it can be easily implemented in Prolog because a set is represented as a list, “ordered” set. For example, suppose f(X)=min{Y| h(X,Y)=T and Y∈Ys}. Then, f is given by the following program: f(X,Y):assign(regY,[]), sortmin(Ys,Ys0), assign(regZ,Ys0), repeat, regZ([Z|Zs]), if h(X,Z) then assign(regY,Z), Done:=1 else Done:=0 end, assign(regZ,Zs), Done=1 or Zs=[],!, regY(Y); (ix) Quantifier: A difficult problem of the implementation in the extProlog is how to handle a predicate with a quantifier. When a predicate has a quantifier (existential or universal), we have to scan the domain of a quantified variable. For instance, if X={x1, ...,xn}, (∀x)(P(x)) is examined by checking the formula P(x1)&...&P(xn). Similarly, (∃x)(P(x)) is checked by the formula P(x1)∨...∨P(xn). Then, since the checking is certainly time consuming, it requires some trick. The extProlog has special system defined predicates written in C to handle the case.
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
7. Concluding Remark This paper shows a formal systems theoretic approach to development of a solver for a problem solving type information system. The approach implies set theoretic modeling based on systems concepts and implementation in the extProlog. According to the approach problems are classified into the 8 cases. This paper deals with the least structured case. A solver is modeled as a goal seeking system. A hill climbing method with a push down stack is used for design of the strategy of the solver and is characterized by the concept of efficient solving path. The data mining system problem is used as an example. This research clearly shows at least three advantages of the formal system approach. (i) It has been said that the systems approach can reveal a structure of a target. In the current research that advantage can help us 1. To classify problems. 2. To decompose a problem structure into two parts, problem dependent part and problem independent part. Although the current problem classification is at a preliminary stage, it can still give us a clue how to handle a new problem. The decomposition can make a big contribution to rapid systems development. Since the problem independent part, i.e., goal seeker part, is the most difficult part, it is quite helpful that we do not have to design it but can use a standard one for it. (ii) It is obvious that the formal approach makes arguments operational. Discussions can be deepened and precise, which enables us to present results in the mathematical style
(definition-theorem-proof) and to find errors in implementation. (iii) Due to the narrow semantic gap between a set theoretic description and Prolog implementation the set theory oriented formal approach results in rapid systems development.
Appendix /*dataminingPD.p*/ frame(rule,[[alist,[]],[vlist,[]],[dlist,[]]]); element(Dlist,I,V,U,D):procC("getelement",[Dlist,I,V,U],[D]); q():function([ aLst, attrN, element, support, confidence, ]), /*data set*/ D0:=[ [none,young,myope,no,reduced], [soft,young,myope,no,normal], [none,young,myope,yes,reduced], [hard,young,myope,yes,normal], [none,young,hypermetrope,no,reduced], [soft,young,hypermetrope,no,normal], [none,young,hypermetrope,yes,reduced], [hard,young,hypermetrope,yes,normal], [none,pre_presbyopic,myope,no,reduced], [soft,pre_presbyopic,myope,no,normal], [none,pre_presbyopic,myope,yes,reduced], [hard,pre_presbyopic,myope,yes,normal], [none,pre_presbyopic,hypermetrope,no,reduced], [soft,pre_presbyopic,hypermetrope,no,normal], [none,pre_presbyopic,hypermetrope,yes,reduced], [none,pre_presbyopic,hypermetrope,yes,normal], [none,presbyopic,myope,no,reduced], [none,presbyopic,myope,no,normal], [none,presbyopic,myope,yes,reduced], [hard,presbyopic,myope,yes,normal], [none,presbyopic,hypermetrope,no,reduced], [soft,presbyopic,hypermetrope,no,normal], [none,presbyopic,hypermetrope,yes,reduced], [none,presbyopic,hypermetrope,yes,normal]], /*support level;confidence level*/ assign(supL,2), assign(confL,0.6),
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
155
A Formal Systems Approach to Solver Design
/*auxiliary relations*/ ALst:=[lenses,age,prescription,astigmatism,tear], assign(aLst,ALst), VLst:=procC("getcategory",[D0,ALst]), assign(vLst,VLst), Iap:=procC("createindex",[2,strlen(ALst)-1]), assign(iap,Iap), /*initial state*/ getID(ID), defFrame(rule,ID,[]), concat([rule,".",ID],Fr), Fr->dlist:=D0, C0:=[0], assert(state(0,[ID]):-!), /*initial statck valiue*/ genA(C0,As0), assign(regStack,[[C0,As0]]), /*initialize display of goal behavior*/ goal(C0,R), assign(regG,[R]), /*start solution*/ assign(regC,[]), goalseeker(CC), /*end of solution*/ project(CC,1,K), xwriteln(0,"end of goalseeker:final K=",K), Sts:=procC("createindex",[1,K]), /*output*/ assign(rNum,0), appendf("dmrules2","w",""), lambda(Sts); ?-q(); delta([K|Ks],As,C2):state(K,SL), //xwriteln(0,"sigma:state=",[K,SL]),stop, C:=[K|Ks], assign(regA,As), assign([state,K+1],[]), repeat, regA([X|Xs]), delta1(C,X,CC), assign(regA,Xs), Xs=[],!, state(K+1,SL2), if SL2=[] then C2:=[] else append([K+1],C,C2) end;
156
state
index
delta1([K|Ks],A,CC):state(K,FIndex), assign(regFI,FIndex), assign(regCC,[]), repeat, regFI([I|Is]), concat([rule,".",I],Fr), As:=Fr->alist, append(As,[A],As2), sortmin(As2,As20), if As<>[] then Min:=min(As) else Min:=100000 end, if Min>A then delta2([K|Ks],I,A,CC0), assign(regCC,CC0) else assign(regCC,[]) end, assign(regFI,Is), Is=[],!, regCC(CC), retract([regFI,regCC]); delta2([K|Ks],I,A,CC):dom(A,Vs), assign(regV,Vs), assign(regfin,0), repeat, regV([V|Vs2]), if delta3(I,[A,V],I2) then assign(regfin,1), state(K+1,L), if I2<>[] then append(L,[I2],L2) else L2:=L end, assign([state,K+1],L2) end, assign(regV,Vs2), Vs2=[],!, regfin(F), retract([regV,regfin]), if F=1 then C:=[K|Ks], append([K+1],C,CC) else CC:=[] end; delta3(I,[A,V],I2):/*get frame of I*/ concat([rule,".",I],Fr), As:=Fr->alist,
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
TAKAHARA, LIU and YANO
append(As,[A],As2), D:=Fr->dlist, D2:=element(D,A,V,"*"), supL(SupL), if strlen(D2)vlist,[V],Vs2), Fr2->alist:=As2, Fr2->vlist:=Vs2, Fr2->dlist:=D2 end; dom(A,Vs):vLst(VLst), project(VLst,A,Vs); genA(C,As):iap(Iap), As:=Iap; goal([0],0):-!; goal([K|Ks],V):state(K,L), goal(Ks,V2), V:=strlen(L)+V2; goalseeker(CC):xwriteln(0,"pop up,stack"), regG(V), show1(V,plot), if regStack([[C,As]|Stacks]) then assign(regStack,Stacks), sigma(C,As,A,RA,C2), if A<>[] then xwriteln(0,"push down stack2"), goal(C2,V2), append(regG,[V2],regG), genA(C2,As2), append([[C2,As2]],regStack,regStack), else assign(regC,C), end, goalseeker(CC) else regC(CC) end; sigma(C,As,A,RA,C2):delta(C,As,C2), if C2=[] then A:=[],
RA:=[] else A:=a, RA:=[] end; support
getID(ID):currentID(N), ID:=N+1, assign(currentID,ID);
currentID(0);
References [1] Cantone, D., E. Onodeo, A. Policriti, Set Theory for Computing, Springer, 2001. [2] Hooker,
J.
Logic-Based
Method
for
Optimization, John-Wiley, 2002. [3] Mesarovic M. D., Y. Takahara, Abstract Systems Theory, Springer, 1989. [4] Takahara,Y., H. Kubota, “A Framework of Conceptual Design of Data Processing System”, Office Automation, Vol. 10, No. 1, 1988 (in Japanese). [5] Takahara, Y., N. Shiba, Y. Liu, “General system theoretic approach to data mining”, International Journal of General Systems, 2002. [6] Takahara, Y., Y. Liu, J. Hu, H. Shimazu, M. Okada, “Intelligent data mining system”, Proceedings of International Conference on E-Business, Beijing, 2002. [7] Takahara, Y., A. Shimizu, “A foundation of problem
solving
EUD-conceptual
framework”, J. of JASMIN, Vol. 5, No. 3. 3, 1996 (in Japanese). [8] Takahara, Y., Y. Liu, “An extended prolog for end user development”, Proceedings of World Multiconference on Systems, Cybernetics and Informatics, Orlando, 1999. [9] Witten, I., E. Frank, Data Mining, Morgan Kaufmann, 1999.
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003
157
A Formal Systems Approach to Solver Design
Yasuhiko Takahara received his B.S. from the University of Tokyo in 1959, his M.S. and his Ph.D. from Case Institute of Technology in 1964 and in 1976, respectively. From 1967 to 1971 he served as a research associate and an assistant professor at Case Western Reserve University. From 1971 to 1979 he was an associate professor of the Department of Industrial Engineering and Management, Tokyo Institute of Technology and since then has been a professor emeritus of Tokyo Institute of Technology. From 1995, he moved to Chiba Institute of Technology and since then has been a professor emeritus of Tokyo Institute of Technology. His research interest is primarily in general systems theory, cybernetic systems and management information system.
and 1994, respectively. From 1994 to 1999 she was an assistant and lecturer at the School of Business and Administration, Central South University of Technology. Since 1999 she has been a Ph.D. Candidate of Department of Management of Information Science, Chiba Institute of Technology. Her major interests are systems theory and management information systems. Yoshio Yano received his B.S. and M.S. from Chiba Institute of Technology in 2000 and 2003, respectively. Since 2003 he has been a Ph.D. Candidate of Department of Management of Information Science, Chiba Institute of Technology. His major interests are systems theory and management information systems.
Yongmei Liu received her B.S. and M.S. from Central South University of Technology in 1991
158
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003