On the Foundations and Applications of Similarity Theory to Case-Based Reasoning
- 格式：pdf
- 大小：975.45 KB
- 文档页数：16
On the Foundations and Applications of Similarity Theory to Case-Based ReasoningStephan RudolphInstitute for Statics and Dynamics of Aerospace Structures University of Stuttgart,Pfaffenwaldring27,D-70569Stuttgart WWW:http://www.isd.uni-stuttgart.de/rudolphEMail:rudolph@isd.uni-stuttgart.depreprinted from:Proceedings of the12th International Conference for Applications of Artificial Intelligence in Engineering AIENG’977-9July1997,Capri(Naples),ItalyAbstractIn thefield of case-based reasoning in artificial intelligence,the general deriva-tion of so-called similarity measures is still an unresolved open question.In this work the theoretical framework of dimensional analysis is used to derive ap-propriate similarity measures for a case-based reasoning technique.For the sub-class of all case descriptions in engineering and physics consisting of real-valued quantities with physical units,it is shown how the Pi-Theorem of Buckingham can be used to construct similarity measures from these case descriptions.The necessary functional model assumptions are defined and the theoretical foun-dations are discussed.Within this functional model approach a proof for the correctness of the case-based and rule-based reasoning technique can be derived. An application of the case-based reasoning technique based on dimensionless groups is demonstrated using the reasoning on power efficiency in gas turbines and is compared to a conventional approach using a V oronoi-technique.1IntroductionIncreasing complexity in modern technology and production has risen the desire to understand and formalize the engineering and production task as much as pos-sible.This would allow to solve for at least some parts of the engineering and production problems with software tools.It is hoped for that by means of such software systems humans will work more efficiently and can concentrate on less formal and more creative tasks.As simple models for the complex reasoning techniques used by humans during processes such as engineering problem solv-ing,thefields of case-based and rule-based reasoning have emerged within the broaderfield of artificial intelligence[14].Case-based reasoning has most recently attracted much scientific inter-est[10,15],since the requirements for rule-based systems in terms of knowledge acquisition and knowledge structuring have been repeatedly reported difficult in the past.The current scientific understanding of case-based reasoning today es-tablishes four consecutive steps for the successful reuse and applicability of for-mer case knowledge to new unknown cases by means of the following process model[1,10],e.g.toretrieve,reuse,revise,andretainformer case knowledge.This process model also highlights the importance of the following three major and still unresolved problems in the area of case-based reasoning[15],such as the establishment ofsimilarity measures for cases,knowledge representation schemes,andefficient and stable retrieval methods.For the technically important subclass of case descriptions with consisting of real-valued parameters with physical dimensions SI of the SI-units system,it will be shown in the following how correct similarity measures can be derived.However,first one drawback of the current state of art of similarity measures is mentioned in the next section after the necessary explanation about the use of term in computer science and artificial intelligence versus in physics and engineering.1.1Disciplinary Usage of TermsThe usage of the term similarity in artificial intelligence,especially in the area of case-based reasoning,focuses on similarity as a fuzzy relation between two ob-jects or their respective representations,the so-called cases.Since it is intended to adapt available knowledge about old cases to solve problems in new ones,the similarity measures to be constructed depend on these intentions and both case representations.This leads to similarity measures with two casesas parameters,see section1.2.In physics the emphasis of the term similarity lies in the property of ab-straction,because dimensionless parameters are attributed to each physical ob-ject.In physics,the abstraction of an object to its dimensionless parameters is called similarity and leads to similarity measures and withone case representation only,see section2.3.If all dimensionless parameters of two different objects and are identical,the two objects are called completely physically similar.Then the properties of the second unknown case can be concluded from(i.e.reasoned)the known case.1.2State of ArtIn a recent thorough review of the state of art in case-based reasoning[15],the following M INKOWSKI norm with(1)and is cited among other possibilities to construct a similarity measure for the similarity of two cases and based on their case representations .For a choice of equation(1)with represents the E UCLIDEAN norm[9].It is important to realize that equation(1)defines forand one knownfixed case a uniform hyper-sphere in the-dimensional space spanned by the description parameters of case.This absence of specific preference directions means that a similarity measure derived from this norm will be isotropic.In contrary to that an anisotropic similarity mea-sure based on similarity considerations of physics[13]will be derived in a later section.2TheoryIn physics and engineering often functions of the typeserve as qualitative and quantitative models.In this respect they serve as knowl-edge representations for the description of the behavior of the real physical object or process under consideration.An explicit function can hereby always be written in the implicit form(to ease the mathematical notations later on,the symbol will be used for both explicit and implicit forms).Since in physics the formal correctness of any sequence of alge-braic operations on an equation can be falsified using the so-called dimensions check,it is clear that all possibly correct functions in physics have to belong to the so-called class of dimensionally homogeneous functions[5,8]which comply to this requirement of dimensional homogeneity[5,8].2.1Dimensional HomogeneityDue to the property of dimensional homogeneity of all possibly correct functions in their general implicit form,the Pi-Theorem of Bucking-ham[5,8]holds in all physics and is stated in the following:Theorem1(Pi-Theorem)From the existence of a complete and dimensionally homogeneous function of physical quantities follows the existence of a dimensionless function of only dimensionless quantities(2)(3)where is reduced by the rank of the dimensional matrix formed by the dimensional quantities.The dimensionless quantities(also called dimen-sionless products or dimensionless groups)have the form(4) for and with the as constants.The general definition of the dimensional matrix associated with the rele-vance list of variables is shown in the left hand side offigure1.This dimensional matrix has rows for the variables and up to columns for the representation of the dimensional exponents of the variables in the base dimensions of the employed unit system.In the current known SI-unit system seven dimensions(mass,length,time,temperature,current,amount of substance and intensity of light)are distinguished,thus.To calculate the dimension-variables“”variables“”Figure1:Definition of Dimensional Matrix[12,13]less products in equation(4),the dimensional matrix of the relevance list of variables as shown in the left hand side offigure1needs to be cre-ated.By rank preserving operations the upper diagonal form of the dimensionalmatrix as shown in the right hand side offigure1is obtained.This means that either multiples of matrix columns may be added to each other or that matrix rows can be interchanged.The unknown exponents of the dimensionless products in equation(4)are then automatically determined by negation of the values of the resulting matrix elements in the hatched part of the matrix on the lower right hand side offigure1.A typical example of such a dimensional matrix is shown in Table1in the application section.The restriction to positive values of the dimensional parameters can be satisfied by coordinate transforms and is common in physics.Additionally it can be shown that modern proofs of the Pi-Theorem impose no restriction on the specific kind of the operator and are thus valid for physical equations without exceptions[3,4].2.2Model BuildingIt is generally agreed on that inside our present world of physical thought con-structs every more general theory needs to include any less general theory as a special case.This formal embedding is expressed in the following corollary:Corollary1(Embedding)Any more general theory necessarily has to embed any other less general theory in the formal limit case,since otherwise the more general theory would immediately falsify the less general theory.As an example for corollary1the following example of the simplified(con-stant)mass of Newtonian physics and the variable mass in relativistic physics is given.Since the relativistic mass concept of E INSTEIN is more gen-eral than the concept of constant mass introduced by N EWTON,the following limit casetofive conventions,which are named definitions1to5in this work.Conse-quently,the statements derived with the help of these definitions are named corollaries1to4in this work.These naming conventions are adopted for the establishment of a formal function model approach for a case-based and rule-based reasoning technique as stated in the following two definitions1and2:Definition1From the existence on an implicit function it follows for a certain instantiation of that function,i.e.one specific case of the parameter set,thatPremise Conclusion Case(6)is valid.This is used to define the term case-based reasoning.In the terminology of artificial intelligence it is said that the conclusion(effect)will always occur when the premise(cause)is fulfilled.It might appearfirst neither straightforward nor necessary to define case-based reasoning just as the identity,i.e.the mapping of the premise of case onto the conclusion of case which just reflects the capability of repeating a certain experiment.From a theoretical point of view however this is necessary,since in the absence of any general knowledge about the completeness of the relevance list will together with the causality just guarantee that the experiment(premise) could be permanently repeated and would always yield the same result(conclu-sion).Case-based reasoning has therefore to be based on definition1.Without that one might be tempted to immediately think of case-based reasoning as the reasoning process from a known old case to a new case.However,it will turn out in definition3to be necessary to have made this definitional distinction, since up to now no similarity measures between two distinct cases and have been established which would allow for this reasoning process.Definition2If infinitely many instantiations,e.g.cases are known, then the cases can be condensed into the form of a continuous functionPremise Conclusion Rule(7)which is valid in the whole range of definition of the function parameters .This is used in the following to define the term rule-based reasoning.Both definitions1and2reflect a property of the chosen functional model approach,where for the whole class of real-valued case descriptions case-based reasoning is equivalent to the knowledge of just one single solutionof,while rule-based reasoning assumes the explicit knowledge of that function .This implies that correct case-based reasoning is a necessary condition for correct rule-based reasoning.With the help of definitions1and2the problem commonly seen central to the area of case-based reasoning,i.e.the reasoning process from a known old case to a new case by means of so-called similarity measuresand,can now be understood as the reasoning process inbetween two theoretical limit cases as shown infig.2.Premise ConclusionIdentity Rule Figure2:The two limit cases for similarity measures in case-based reasoning In the framework of the adopted function model it is evident that the simi-larity measures and need to fulfill as both limit cases the identity (i.e.the conclusion from to itself)as well as any arbitrary instantiation in the whole range of definition of the general rule(i.e.the conclusion from to itself in the whole range of definition).This however results in the fact that the solution to the problem of constructing appropriate similarity measures is central to the problem of case-based and rule-based reasoning.It has in this respect the mathematical character of a necessary and sufficient condition.This leads to the following definition:Definition3If the similarity measures,of two cases and with not necessarily identical case representations andturn out to be equal,then(8)Premise Conclusion(similar)holds and it can be reasoned from the conclusion of the known case to the conclusion of the unknown case.It is obvious that definition3neither explicitly contains how appropriate similarity measures and can be constructed from the case repre-sentations,nor it is stated what the exact form of the reasoning process does look like.By definition3it is just determined what properties (i.e.equality)need to be fulfilled by the similarity measures in terms of the com-pliance to and in between both limit cases on the left and right hand side infig2.Under what circumstances and how it canfinally be reasoned from a known case to an unknown case by means of the similarity measures is shown in the following section where appropriate similarity measures will be derived.2.3Similarity MeasuresTwo distinct cases(e.g.of a certain object or process behavior)possess necessarily non-identical case representations with at least partially distinct parameter values.For both cases and to be considered“similar”according to definition3,all evaluation criteria used to determine the similarity of the cases need to be equal.In this respect it becomes apparent that the suc-cessful establishment of an appropriate set of evaluation criteria lies at the heart of the case-based reasoning process.It is thus equivalent to the identification and construction of appropriate similarity measures.For the solution of such an eval-uation problem in engineering design there has already been proposed a solution strategy based on the Pi-Theorem.This solution is formulated in form of the so-called evaluation hypothesis[11,12]and states that“any minimal description in the sense of the Pi-Theorem is an evaluation.”Applying this evaluation hypothesis to case-based reasoning in physical problem domains such as engineering design(i.e.to cases descriptions which consist of real-valued case representations possessing physical dimensions)leads because of corollary1to the postulation of the following main result: Corollary2Any arbitrary general similarity measure of a case with a complete case description containing arbitrary parameters has for applications in physics(where the are real-valued and have physical SI-units,thus)in the limit case to be formally equal to(9)since in physics any case representation has to be dimensionally homogeneous and is thus invariant under transformations using the dimensionless groups with.From equation(9)follows that the similarity measures in physics are gen-erally anisotropic,since the parameters in the case description are combined non-linearly by the exponents.From a scientific point of view corollary2 represents the main result according to definition3.It shows the construction of similarity measures for the purpose of case-based and rule-based reasoning in physics,since the Pi-Theorem provides a theoretical proof for its validity based on the chosen functional model approach.As a consequence of this,the following corollaries3and4are valid in physics and can be shown to solve step by step for the remaining open questions in case-based reasoning according to definitions1and2.They can be stated as:Corollary3If in a certain case with the premise the conclu-sion holds,then the similarity transform of this conclusion in the formPremise Conclusion Case completely similar(10)does not only hold for this single case,but also holds for all cases which are completely similar to and possess therefore the same premise with identical .This represents the constructive proof for the correctness of case-based reasoning.Corollary3satisfies definition1and also highlights the fact why in def-inition1andfig.2left case-based reasoning had to be defined as the identity. Finally,by extension of corollary3onto the whole range of definition of,the sought after result for rule-based reasoning can be stated in the following form: Corollary4Let be the correct rule for all caseswith the premise,then the similarity transform of the conclusion of the rule in form ofPremise Conclusion Rule similarity transform(11)also holds,since is shown by the Pi-Theorem to be the similarity transformof.This represents the constructive proof for the correctness of rule-basedreasoning.Corollary4represents the solution to problem definition2.The valid-ity of corollary4can easily be explained in the following way.Any questionabout the behavior of the design object can be answered by the rule,otherwise would not represent the complete and correct physical model in terms of the required model precision.This means thatas in equation(3)represents the similarity transform of,which represents atransformation under which the physical content of the rule remains invariant(This can be checked by resubstituting the dimensionless groups of equation(4)into.By this operation is again obtained).Before showing now a numerical example of the case-based reasoningtechnique,it has to be explicitly stated how the set of all completely similarcases is defined based on the group transforms in equation(4).This can bedone in form of the following definitions4and5:Definition4The similarity transform of the space(consistingof physical variables with physical dimensions)into the dimensionless space(consisting of dimensionless variables)is defined according to equation(4)with as(12) and represents a surjective mapping,since the similarity transform of a space into a space with represents a dimensionality reduction.This dimensionality reduction has the property that different objects in may be mapped onto the very same object in.Definition5The inverse similarity transform of the dimension-less space into the dimensional space of physical variables withand is given as(13)and is not unique,since the inverse similarity transform maps a space into a space.This results in a dimensionality expansion which cannot be unique.Definition5represents atfirst sight a dilemma in the practical applicability of the new case-based reasoning method.However,as shown infigure3,it is just this fact which represents the key feature of the new similarity method for case-based reasoning.Infigure3first one single point with is mapped into its corresponding point in dimensionless space.The inverse transform leads to the whole set of all similar points in defined by the similarity condition.Figure3:Dimensionality expansion of one single case onto all physically completely similar cases toThe inverse mapping only leads to the previous result if and only if theformer numerical values of the premise in Gleichung(13)are stillknown.Otherwise the numerical values for the parameters) in equation(13)can be taken arbitrarily from the range of definition.This can be done by a random number generator.An example for this isfigure5,which is explained later in the next section.Mathematically the define a hypersurface in which contains all physically completely similar points.3Application ExampleThe theoretical model building for the thermodynamical processes of a gas tur-bine can be found in any reference book on the subject[7].In order to understand the very simple model considered infig.4it is sufficient to agree on the fact that,Introducing both dimensionless parameters and into equation(14)yields the following dimensionless equation(17) This change of variables from equation(14)to(17)is just a very simple example for the derivation of the similarity transform from,since accidentally had a very simple mathematical form.The Pi-Theorem however also applies to any complex but dimensionally homogeneous equations of physical variables,such as partial differential equations[3,4].From equation(17)the rule for rule-based reasoning on the power efficiency of gas turbines has the following form according to corollary4Premise Conclusion Rule(18)which is valid for all gas turbines for which the above made basic thermodynam-ical model assumptions apply.Numerical example of rule-based reasoning.The following numerical ex-ample may serve as an application of the rule-based reasoning technique.For a gas turbine with known and follows for the transformed premise according to equation(15).The rule in equa-tion(18)yields as the conclusion.By means of according to equation(13)follows for the sought after mechanical power.While this result may not be too surprising since it basically relies on the explicit knowledge of via its similarity transform,it is shown in the follow-ing why case-based reasoning based on similarity considerations can still be a valuable and powerful tool.Numerical example of case-based reasoning.The followingfigures5and6 will illustrate the advantage of the new similarity technique together with the following numerical example of case-based reasoning.For a gas turbine with known andfollows for the transformed premise according to equation(15).Since the rule in equation(18)is unknown,the conclusion needs to be determined using a completely similar case from the case database.If the database contains a premise-conclusion tuple with numerical values,the conclu-sion is.Such a completely similar case could stem from the value triplefor of a known gas turbine,which maps exactly to the numerical values for the value tuple.By means of according to equation(13)follows for the sought after mechanical power.Having these two examples in mind,the relationship between 1000se-lected equidistant points ofin the 2-dimensional -space and their correspondent points in in 3-dimensional -space is displayed in fig.5.The colors (grey values)of each point have thereby been chosen in such a way,that the same color (grey value)indicates the correct case-based reasoning result according to corollary 3.Same colors (grey values)thus indicate completely similar points.As a consequence of this,case-based rea-00.20.40.60.8100.20.40.60.810500100015000100050010001500Figure 5:Mapping of completely similar cases (same color)soning will be possible and correct on exactly that hyper-surface (here:a line of constant color)in -space of which the known case is of the very same color (grey value)in -space.The similarity measures used for case-based reasoning are thus anisotropic and depend on the shapes of the hyper-surfaces defined bythe.In between any points (i.e.cases)of different colors (grey val-ues)the case-based reasoning technique will not work and will even falsify any attempt of doing so,since this would not be conform to the Pi-Theorem.An ex-planation of this impossibility follows later in detail together with equation (19).00.20.40.60.8100.20.40.60.81024681005100246810Figure 6:“Similarity measure”based on isotropic V ORONOI -distanceThe failure of classical isotropic“similarity measures”to comply to the Pi-Theorem is shown infig.6.There all points inside the V ORONOI-polygon[15]of several known cases in3-dimensional-space were given the same color(grey values)and were mapped into the2-dimensional-space.In order to better visualize the wrong interlapping of the resulting mappings,each point set of the same color was slightly differently placed along the unused third axis and drawn as a perspective view.As can be easily seen fromfig.6,any isotropic“similarity measures”not conform to the Pi-Theorem will yield erroneous results in all case descriptions,to which the Pi-Theorem can be and has to be applied to.3.1DiscussionIt is advantageous that the dimensionless groups can be determined without explicit knowledge of if at least the relevance list of physical quantities of that unknown function is known or can be sufficiently well estimated(i.e.an engineers‘educated guess).After having established the so-called dimensional matrix infig.1,the parametric solutions of a simple homogeneous linear equa-tion set will yield a complete set of dimensionless groups[5,8].Once the di-mensionless groups are known,case-based reasoning is possible by mapping the available numerical values of the case description parameters according to the building laws of these dimensionless groups.Then the conclusion of any known case can be used for all unknown cases with identical premise .By means of these dimensionless groups,the case-based reason-ing process will always yield correct results for all completely similar points as shown infig.3without further knowledge on.In all other cases,where no completely similar case is contained in the case database,it can be shown to be impossible to do and prove correct case-based reasoning without further a priori knowledge on.This follows because from in its explicit notation as the general formula4SummaryIn thefield of case-based reasoning a general formal derivation of so-called sim-ilarity measures based on dimensional analysis of physics has been shown.It is used to derive appropriate similarity measures for a case-based reasoning tech-nique for the important subclass of such case representations consisting of real-valued quantities with physical units.It was shown how the Pi-Theorem of Buck-ingham can be used to construct and validate similarity measures based on these case descriptions.A proof for the correctness of the case-based and rule-based reasoning technique is derived within the used functional model approach.An application of the case-based reasoning technique based on dimensionless groups is demonstrated using the reasoning on power efficiency in gas turbines and is compared to a conventional approach using a V ORONOI-distance technique. Index:Pi-Theorem,isotropic similarity measures,anisotropic similarity mea-sures,case-based reasoning.References[1]Aamodt,A.und Plaza,E.:CBR:Foundational Issues,MethodologicalVariations and System Approaches.AI Communications7,1,39-59,1994.[2]Althoff,K.-D.und Aamodt,A.:Zur Analyse fallbasierter Probleml¨o se-und Lernmethoden in Abh¨a ngigkeit von Charakteristika gegebener Auf-gabenstellungen und Anwendungsdom¨a nen.K¨u nstliche Intelligenz KI,1, 10-15,1996.[3]Bluman,G.and Cole,J.:Similarity Methods for Differential Equations.Springer,New York,1974.[4]Bluman,G.and Kumei,S.:Symmetries and Differential Equations.Springer,New York,1989.[5]Buckingham,E.:On Physically Similar Systems:Illustration of the Use ofDimensional Equations.Phys.Review4,345-376,1914.[6]Bunge,M.:Causality.The place of the causal principle in modern science.Harvard University Press,Cambridge,Massachusetts,1957.[7]Frohn,A.:Einf¨u hrung in die technische Thermodynamik.AkademischeVerlagsgesellschaft,Wiesbaden,1977.[8]G¨o rtler,H.:Dimensionsanalyse.Springer,Berlin,1975.[9]Heuser,H.und Wolf,H.:Algebra,Funktionalanalysis und Codierung.Teubner,Stuttgart,1986.[10]Kolodner,J.:Case-Based Reasoning.Morgan Kaufmann,San Mateo,1993.[11]Rudolph,S.:Eine Methodik zur systematischen Bewertung von Kon-struktionen,VDI Fortschrittsberichte Reihe1,Nummer251,VDI-Verlag, D¨u sseldorf,1995.(An english version of this PhD thesis entitled“A methodology for the sys-tematic evaluation of engineering design objects”has been published by the Institute of Statics and Dynamics of Aerospace Structures at the Univer-sity of Stuttgart and is available on request by email from pigroup@isd.uni-stuttgart.de)[12]Rudolph,S.:On a Symbolic CAD-Front-End for Design Evaluation Basedon the Pi-Theorem.In:Gero,J.and Sudweeks,F.(eds.):Proceedings of the IFIP WG5.2Workshop on Formal Design Methods for Computer-Aided De-sign,June13-16th,1995,Mexico City,Mexico.Chapman and Hall,1996, London,165-179.[13]Rudolph,S.:On foundations and applications of similarity measures incase-based and rule-based reasoning.ISD Research Report,Verlag des Instituts f¨u r Statik und Dynamik der Luft-und Raumfahrtkonstruktionen, Universit¨a t Stuttgart,August1996,ISBN3-930683-17-2.Available also via:http://www.isd.uni-stuttgart.de/rudolph/in the subdirectory:case-basedr/casebr。
