《LearningAgentsLaboratoryComputerScience》由会员分享，可在线阅读，更多相关《LearningAgentsLaboratoryComputerScience（73页珍藏版）》请在金锄头文库上搜索。
1、 2002, G.Tecuci, Learning Agents Laboratory1Learning Agents LaboratoryComputer Science DepartmentGeorge Mason UniversityProf. Gheorghe TecuciLearning by analogyLearning by analogy 2002, G.Tecuci, Learning Agents Laboratory2OverviewOverviewLearning by analogy: definitionDesign issuesThe structure map
2、ping theoryProblem solving by analogyDeterminationsRecommended readingExercises 2002, G.Tecuci, Learning Agents Laboratory3Learning by analogy: definitionLearning by analogy: definitionLearning by analogy means acquiring new knowledge about an input entity by transferring it from a known similar ent
3、ity. Which is the central intuition supporting the learning by analogy paradigm?One may infer, by analogy, that hydraulics laws are similar to Kirchoffs laws, and Ohms law. 2002, G.Tecuci, Learning Agents Laboratory4DiscussionDiscussionCentral intuition supporting learning by analogy:If two entities
4、 are similar in some respects then they could be similar in other respects as well. Examples of analogies:Pressure Drop is like Voltage DropA variable in a programming language is like a box.Provide other examples of analogies. 2002, G.Tecuci, Learning Agents Laboratory5Learning by analogy: illustra
5、tionLearning by analogy: illustrationIllustration: The hydrogen atom is like our solar system.The Sun has a greater mass than the Earth and attracts it, causing the Earth to revolve around the Sun. The nucleus also has a greater mass then the electron and attracts it.Therefore it is plausible that t
6、he electron also revolves around the nucleus. 2002, G.Tecuci, Learning Agents Laboratory6Learning by analogy: illustrationLearning by analogy: illustrationIllustration: The hydrogen atom is like our solar system.The Sun has a greater mass than the Earth and attracts it, causing the Earth to revolve
7、around the Sun. The nucleus also has a greater mass then the electron and attracts it.Therefore it is plausible that the electron also revolves around the nucleus. 2002, G.Tecuci, Learning Agents Laboratory7Learning by analogy: the learning problemLearning by analogy: the learning problemGiven: A pa
8、rtially known target entity T and a goal concerning it. Background knowledge containing known entities.Find: New knowledge about T obtained from a source entity S belonging to the background knowledge.Partially understood structure of the hydrogen atom under study.Knowledge from different domains, i
9、ncluding astronomy, geography, etc.In a hydrogen atom the electron revolves around the nucleus, in a similar way in which a planet revolves around the sun. 2002, G.Tecuci, Learning Agents Laboratory8Learning by analogy: the learning methodLearning by analogy: the learning method ACCESS: find a known
10、 entity that is analogous with the input entity. MATCHING: match the two entities and hypothesize knowledge. EVALUATION: test the hypotheses. LEARNING: store or generalize the new knowledge.Store that, in a hydrogen atom, the electron revolves around the nucleus. By generalization from the solar sys
11、tem and the hydrogen atom, learn the abstract concept that a central force can cause revolution.In the Rutherfords analogy the access is no longer necessary because the source entity is already given (the solar system).One may map the nucleus to the sun and the electron to the planet, allowing one t
12、o infer that the electron revolves around the nucleus because the nucleus attracts the electron and the mass of the nucleus is greater than the mass of the electron.A specially designed experiment shows that indeed the electron revolves around the nucleus. 2002, G.Tecuci, Learning Agents Laboratory9
13、DiscussionDiscussionHow does analogy help?Why not just study the structure of the hydrogen atom to discover that new knowledge?We anyway need to perform an experiment to test that the electron revolves around the hydrogen atom. 2002, G.Tecuci, Learning Agents Laboratory10OverviewOverviewLearning by
14、analogy: definitionDesign issuesThe structure mapping theoryProblem solving by analogyDeterminationsRecommended readingExercises 2002, G.Tecuci, Learning Agents Laboratory11Learning by analogy: Design issuesLearning by analogy: Design issues ACCESS: find a known entity that is analogous with the inp
15、ut entity. MATCHING: match the two entities and hypothesize knowledge. EVALUATION: test the hypotheses. LEARNING: store or generalize the new knowledge.How to learn?Given a target, how to identify a few potential sources in a very large storage?Given a potential source, how to identify the knowledge
16、 to hypothesize?Why and how to test the hypothesized knowledge? 2002, G.Tecuci, Learning Agents Laboratory12Learning by analogy: Design issuesLearning by analogy: Design issues ACCESS: find a known entity that is analogous with the input entity. MATCHING: match the two entities and hypothesize knowl
17、edge. EVALUATION: test the hypotheses. LEARNING: store or generalize the new knowledge.How to learn?Given a target, how to identify a few potential sources in a very large storage?Given a potential source, how to identify the knowledge to hypothesize?Why and how to test the hypothesized knowledge? 2
18、002, G.Tecuci, Learning Agents Laboratory13Learning by analogy: FormalizationLearning by analogy: FormalizationGiven: - a target entity T; - a universe of potential sources U; - an access function f1 with a threshold value f1; - a matching function f2 with a threshold value f2. Find: - new knowledge
19、 about T (using analogical learning). 2002, G.Tecuci, Learning Agents Laboratory14Learning by analogy: AccessLearning by analogy: AccessFind potential sources for T in U :f1(Sk, T) f1This should result in S1, , Sn 2002, G.Tecuci, Learning Agents Laboratory15Learning by analogy: MatchingLearning by a
20、nalogy: MatchingFind the best match between one of S1, , Sn and T.Let:Sk = A & B & C, T = A & Dwhere f2(Sk, T) f2 gives the best match.A and A are the parts of Sk and T that make them analogous:f2(Sk, T) = f2(A, A)B, C and D are the other parts of Sk and T.As a side effect of partially matching Sk w
21、ith T (or totally matching A with A), one obtains a correspondence (substitution) list s = ( o1 o1, . , on on) where oi is an element of A and oi is the corresponding element from A.By applying the substitution s to Sk one obtains:s(Sk) = s(A) & s(B) & s(C) = A & s(B) & s(C) = A & B & C.By analogy w
22、ith Sk one concludes that T might also have the features B & C. 2002, G.Tecuci, Learning Agents Laboratory16Learning by analogy: Evaluation and learningLearning by analogy: Evaluation and learningBy analogy with Sk one concludes that T might also have the features B & C. However, the evaluation phas
23、e shows that T has the features B but it does not have the features C. Therefore:- B represents the part of Sk that is transferred to T because of the similarity between A and A;- C is the part of Sk that is not transferred to T;- D represents the features that are specific to T. 2002, G.Tecuci, Lea
24、rning Agents Laboratory17Case study discussion: Rutherfords analogyCase study discussion: Rutherfords analogyIn this case, the fact that S and T are analogous is already known. Therefore, the access part is solved and the only purpose of the matching function remains that of identifying the correct
25、correspondence between the elements of the solar system and those of the hydrogen atom.This is an example of a special (simpler form of analogy):“A T is like an S.”This is useful mostly in teaching based on analogy.The hydrogen atom is like our solar system. 2002, G.Tecuci, Learning Agents Laborator
26、y18Case study discussion: Rutherfords analogyCase study discussion: Rutherfords analogyIn this case, the fact that S and T are analogous is already known. Therefore, the access part is solved and the only purpose of the matching function remains that of identifying the correct correspondence between
27、 the elements of the solar system and those of the hydrogen atom.This is an example of a special (simpler form of analogy):“A T is like an S.”This is useful mostly in teaching based on analogy.The hydrogen atom is like our solar system. 2002, G.Tecuci, Learning Agents Laboratory19Case study discussi
28、on: potential matchingsCase study discussion: potential matchingsWhich are the possible matchings between the elements of S and the elements of T?sunplanetyellowmassmasstemperaturegreatercolorrevolves-aroundattractsTsunTplanetMsunMplanetcausestemperaturegreatermassmassattractsMnucleusgreaternucleuse
29、lectronMelectronsunplanetyellowmassmasstemperaturegreatercolorrevolves-aroundattractsTsunTplanetMsunMplanetcausestemperaturegreatermassmassattractsMnucleusgreaternucleuselectronMelectron 2002, G.Tecuci, Learning Agents Laboratory20Case study discussion: potential matchingsCase study discussion: pote
30、ntial matchingsThere are several possible matchings between the elements of S and the elements of T and one has to select the best one:Matching1:sun nucleus, planet electron, Msun Mnucleus, Mplanet Melectron, which is supported by the following correspondencesmass(sun, Msun) mass(nucleus, Mnucleus)m
31、ass(planet , Mplanet ) mass(electron, Melectron)greater(Msun, Mplanet) greater(Mnucleus, Melectron),attracts(sun, planet) attracts(nucleus, electron)Matching2:sun nucleus, planet electron, Tsun Mnucleus, Tplanet Melectron, that is supported by the following correspondencesgreater(Tsun, Tplanet) grea
32、ter(Mnucleus, Melectron),attracts(sun, planet) attracts(nucleus, electron)Matching3:sun electron, planet nucleus, Msun Melectron, Mplanet Mnucleus 2002, G.Tecuci, Learning Agents Laboratory21Similarity estimation issues and sample solutionsSimilarity estimation issues and sample solutions4. How to d
33、efine the similarity threshold ?The similarity of two entities is the sum of the similarity of their elements.Other solutions?Exhaustive search.Other solutions?Two elements are similar if they represent the same concept or are subconcepts of the same concepts. In such a case their similarity may be
34、considered 1 (on a 0-1 scale).Other solutions?Similarity threshold defined by the designer (a hard critical issue).Other solutions?1. How to search the space of all possible matchings ?2. How to measure the similarity of two elements ?3. How to combine the estimated similarities of the parts in orde
35、r to obtain the similarity between S and T ? 2002, G.Tecuci, Learning Agents Laboratory22Case study discussion: Matching resultCase study discussion: Matching resultThe best matching is Matching1 (because it leads to the highest number of common features of the solar system and the hydrogen atom) th
36、at gives the following substitution:s = (sun nucleus, planet electron, Msun Mnucleus, Mplanet Melectron)The features in light color are those that could be transferred to the hydrogen atom as a result of the analogy with the solar system: color(nucleus, yellow) temperature(nucleus, Tn) temperature(e
37、lectron, Te) greater(Tn, Te) revolves-around(nucleus, electron) causes( (attracts(nucleus,electron), greater(Mnucleus, Melectron),revolves-around(nucleus, electron)yellowmassmasstemperaturegreatercolorrevolves-aroundattractsTsunTplanetcausestemperaturegreaterMnucleusnucleuselectronMelectronyellow-Tn
38、ucleusTelectrontemperatureelectronBy applying the substitution to the solar system, one obtains the following structure: 2002, G.Tecuci, Learning Agents Laboratory23Case study discussion: EvaluationCase study discussion: EvaluationThe evaluating phase shows thatThe hydrogen atom has the features: re
39、volves-around(nucleus, electron) causes(attracts(nucleus,electron), greater(Mnucleus, Melectron), revolves-around(nucleus, electron)The hydrogen atom does not have the features: color(nucleus, yellow) temperature(nucleus, Tn) temperature(electron, En) greater(Tn, En)Which is, in your opinion, the mo
40、st critical issue in analogical learning? 2002, G.Tecuci, Learning Agents Laboratory24Case study discussion: EvaluationCase study discussion: EvaluationThe evaluating phase shows thatThe hydrogen atom has the features: revolves-around(nucleus, electron) causes(attracts(nucleus,electron), greater(Mnu
41、cleus, Melectron), revolves-around(nucleus, electron)The hydrogen atom does not have the features: color(nucleus, yellow) temperature(nucleus, Tn) temperature(electron, En) greater(Tn, En)Which is, in your opinion, the most critical issue in analogical learning? 2002, G.Tecuci, Learning Agents Labor
42、atory25DiscussionDiscussionWhat kind of features may be transferred from the source to the target so as to make sound analogical inferences ?Which is the most critical issue in analogical learning? 2002, G.Tecuci, Learning Agents Laboratory26Case study discussion: transfer of causal relationCase stu
43、dy discussion: transfer of causal relation 2002, G.Tecuci, Learning Agents Laboratory27Case study discussion: LearningCase study discussion: LearningStore the new acquired knowledge about the hydrogen atom: revolves-around(nucleus, electron) causes(attracts(nucleus,electron), greater(Mnucleus, Melec
44、tron), revolves-around(nucleus, electron)By generalization from the solar system and the hydrogen atom one may learn the abstract concept that a central force can cause revolution: causes(attracts(x, y), greater(Mx, My), revolves-around(x, y)Question:When to store the acquired knowledge and when to
45、generalize it? 2002, G.Tecuci, Learning Agents Laboratory28Analogy in DiscipleAnalogy in Disciplesimilar exampleexplains?similarIdentify and test a strategic COG candidate for a force The force is Germany_1943I need to Therefore I need to Identify and test a strategic COG candidate corresponding to
46、a member of a force The force is European_Axis_1943 initial exampleexplanationexplainsIdentify and test a strategic COG candidate for a force The force is US_1943I need to Therefore I need to Identify and test a strategic COG candidate corresponding to a member of a force The force is Allied_Forces_
47、1943 US_1943has_as_memberAllied_Forces_1943similar explanationless general thanAnalogycriterionless general than?O2has_as_member?O1forcemulti_member_forceinstance_ofinstance_ofGermany_1943has_as_memberEuropean_Axis_1943similar 2002, G.Tecuci, Learning Agents Laboratory29The basic scheme of analogyCa
48、usal networks of relationsCausal networks of relationsAn important result of the learning by analogy research is that the analogy involves mapping some underlying causal network of relations between analogous situations.By causal network of relations it is generally meant a set of relations related
49、by special higher order relations such as physical-cause(ri, rj), logically-implies(ri, rj), enables(ri, rj), justifies(ri, rj), determines(ri, rj) etc.The idea is that similar causes are expected to have similar effects: 2002, G.Tecuci, Learning Agents Laboratory30The basic scheme of analogyCausal
50、networks of relationsCausal networks of relationsAn important result of the learning by analogy research is that the analogy involves mapping some underlying causal network of relations between analogous situations.By causal network of relations it is generally meant a set of relations related by sp
51、ecial higher order relations such as physical-cause(ri, rj), logically-implies(ri, rj), enables(ri, rj), justifies(ri, rj), determines(ri, rj) etc.The idea is that similar causes are expected to have similar effects: 2002, G.Tecuci, Learning Agents Laboratory31OverviewOverviewLearning by analogy: de
52、finitionDesign issuesThe structure mapping theoryProblem solving by analogyDeterminationsRecommended readingExercises 2002, G.Tecuci, Learning Agents Laboratory32Gentners structure mapping theoryGentners structure mapping theoryThe main claim of this theory is that relations between objects, rather
53、than attributes of objects, are mapped from source to target. Moreover, a relation that belongs to a mappable system of mutually interconnecting relationships is more likely to be imported into the target than is an isolated relation (the systematicity principle).See:Gentner D., The mechanisms of an
54、alogical reasoning, in J.W.Shavlik, T.G.Dietterich (eds), Readings in Machine Learning, Morgan Kaufmann, 1990. 2002, G.Tecuci, Learning Agents Laboratory33Gentners structure mapping theory (cont.)Gentners structure mapping theory (cont.)Analogy maps the objects of the source onto the objects of the
55、target: s1 t1, . , sn tn These object correspondences are used to generate the candidate set of inferences in the target domain. Predicates from the source are carried across to the target, using the node substitutions dictated by the object correspondences, according to the following rules: 1. Disc
56、ard attributes of objects A(si) -/- A(ti)For instance, the yellow color of the sun is not transferred to the hydrogen nucleus. 2. Try to preserve relations between objects R(si, sj) -?- R(ti, tj)That is, some relations are transferred to the target, while others are not. 3. The systematicity princip
57、le: the relations that are most likely to be transferred are those belonging to systems of interconnected relations R(R1(si,sj), R2(sk,sl) R(R1(ti,tj), R2(tk,tl) 2002, G.Tecuci, Learning Agents Laboratory34Literal similarity, analogy, and abstractionLiteral similarity, analogy, and abstractionGentne
58、rs theory distinguishes between literal similarity, analogy, and abstraction.One says that a target T is literally similar with a source S if and only if a large number of predicates is mapped from source to target, relative to the number of nonmapped predicates and, also, the mapped predicates incl
59、ude both attributes of objects and relations between objects.For instance, kool-aid is literally similar with water since it has most of the features of water (both attributes of objects and relations between objects).Give other examples of literally similar entities. 2002, G.Tecuci, Learning Agents
60、 Laboratory35Literal similarity, analogy, and abstractionLiteral similarity, analogy, and abstractionOne says that a target T is analogous with a source S if and only if relations between objects, but few or no attributes of objects, can be mapped from source to target.For instance, heat is analogou
61、s to water.Give other examples of abstractions.One says that a source S is an abstraction of a target T if and only if the source is an abstract relational structure and each predicate (a relation between objects or an attribute of an object) from the abstract source is mapped into a less abstract p
62、redicate of the target; there are no nonmapped predicates.For instance, through-variable is an abstraction of heat, where by through-variable we mean something that flows across a difference in potential. 2002, G.Tecuci, Learning Agents Laboratory36Literal similarity, analogy, and abstractionLiteral
63、 similarity, analogy, and abstractionOne says that a target T is analogous with a source S if and only if relations between objects, but few or no attributes of objects, can be mapped from source to target.For instance, heat is analogous to water.Give other examples of abstractions.One says that a s
64、ource S is an abstraction of a target T if and only if the source is an abstract relational structure and each predicate (a relation between objects or an attribute of an object) from the abstract source is mapped into a less abstract predicate of the target; there are no nonmapped predicates.For in
65、stance, through-variable is an abstraction of heat, where by through-variable we mean something that flows across a difference in potential. 2002, G.Tecuci, Learning Agents Laboratory37Similarity, analogy, and abstraction: discussionSimilarity, analogy, and abstraction: discussionGiven that two enti
66、ties overlap in relations, they are more literally similar to the extent that their object attributes also overlap. Therefore, literal similarity might be seen as a particular case of analogy.Abstraction may also be seen as a special case of analogy in which all the predicates of the source entity a
67、re mapped into the target entity. What could we conclude from these observations? 2002, G.Tecuci, Learning Agents Laboratory38Similarity, analogy, and abstraction: discussionSimilarity, analogy, and abstraction: discussionThe contrast between literal similarity, analogy, and abstraction is a continu
68、um.What could we conclude from these observations?Overlap in relations is necessary for any perception of similarity, analogy or abstraction. 2002, G.Tecuci, Learning Agents Laboratory39Gentners theory: implementation and discussionGentners theory: implementation and discussionAn implementation of t
69、he Structure-Mapping theory is the Structure-Mapping Engine (Falkenhainer, Forbus & Gentner, 1989: The Structure-mapping Engine. Algorithms and Examples, Artificial Intelligence, 41:1-63. Also in Readings in Knowledge Acquisition and Learning).Given the descriptions of a source and a target, the Str
70、ucture-Mapping Engine constructs all syntactically consistent analogical mappings between them. Each mapping consists of pairwise matches between predicates and objects in the source and target, plus a list of predicates which exist in the source but not the target. This list of predicates is the se
71、t of candidate inferences sanctioned by the analogy. The Structure-Mapping Engine evaluates syntactically each possible analogy to find the best one. 2002, G.Tecuci, Learning Agents Laboratory40Gentners theory: implementation and discussionGentners theory: implementation and discussionThe Structure-
72、Mapping Engine needs to be given the descriptions of a source and a target. This requires the ACCESS problem to be solved first:How do we find potential sources for a target?MAC/FAC (Forbus, Gentner, Law, 1995: “MAC/FAC: A model of similarity-based retrieval,” Cognitive Science, 19(2):141-205) is a
73、system that addresses the access problem.The MAC stage uses a simple, nonstructural matcher to filter our a few promising candidates from a large memory of structured descriptions.The FAC stage evaluates each candidate using SME to provide a structural match.MAC/FAC was scaled-up in the DARPAs HPKB
74、and RKF programs.What is, however, a problem with Gentners theory? 2002, G.Tecuci, Learning Agents Laboratory41Gentners theory: discussionGentners theory: discussionGentners interpretation rules depend only on the syntactic properties of the knowledge representation, and not on the specific content
75、of the domain.What is a problem with Gentners theory?Why is this a problem?Consider these equivalent representations:Book1-on-TableOn(Book1, Table)causes(attracts(nucleus,electron), greater(Mnucleus, Melectron),revolves-around(nucleus, electron)Could you think of a different representation where the
76、 following expression is no longer a second order relation? 2002, G.Tecuci, Learning Agents Laboratory42Gentners theory: discussionGentners theory: discussionGentners interpretation rules depend only on the syntactic properties of the knowledge representation, and not on the specific content of the
77、domain.What is a problem with Gentners theory?Why is this a problem?Consider these equivalent representations:Book1-on-TableOn(Book1, Table)causes(attracts(nucleus,electron), greater(Mnucleus, Melectron),revolves-around(nucleus, electron)Could you think of a different representation where the follow
78、ing expression is no longer a second order relation? 2002, G.Tecuci, Learning Agents Laboratory43OverviewOverviewLearning by analogy: definitionDesign issuesThe structure mapping theoryProblem solving by analogyDeterminationsRecommended readingExercises 2002, G.Tecuci, Learning Agents Laboratory44De
79、terminations: DefinitionDeterminations: DefinitionInstead of giving a general criterion for the validity of analogical knowledge transfer (high order relations or causal network of relations), Russel and Davis propose to specify explicitly what knowledge can be transferred. The rules for specifying
80、this are called determination rules.P(x, y) - Q(x, z) (P plausibly determines Q) meaningS, T If $y P(S, y) & P(T, y) then it is probably true that $z Q(S, z) & Q(T, z) where P and Q are first order logical expressions. 2002, G.Tecuci, Learning Agents Laboratory45Determinations: Definition (cont.)Det
81、erminations: Definition (cont.)A determination rule is an expression of the following form:U(x1,.,xn,y1,.,ym) - V(x1,.,xn,z1,.,zp)One says that U determines V. That is, whenever the arguments of U have certain values, the arguments of V are very likely to have corresponding values.Example: Rainfall(
82、x, y) - Water-in-soil(x, z)Rainfall(Philippine, heavy), Water-in-soil(Philippine, high) 2002, G.Tecuci, Learning Agents Laboratory46Given:Rainfall(x, y) - Water-in-soil(x, z)Rainfall(Philippine, heavy), Water-in-soil(Philippine, high)Rainfall(Vietnam, heavy)Conclude:Water-in-soil(Vietnam, high)Analo
83、gical reasoning based on determinationsAnalogical reasoning based on determinationsWhat is the difference between a determination rule and a deductive rule? 2002, G.Tecuci, Learning Agents Laboratory47Determinations: DiscussionDeterminations: DiscussionA determination rule is different from a deduct
84、ive rule.The form of a deductive rule is:U(x1,.,xn,y1,.,ym) - V(x1,.,xn,y1,.,ym)That is, the variables which appear in the left hand side of a rule also appear in the right hand side. Therefore, if we know that U(a1,.,an,b1,.,bm) is true, we could apply modus ponens to infer that V(a1,.,an,b1,.,bm)
85、is also true.This type of reasoning is not possible in the case of a determinationU(x1,.,xn,y1,.,ym) - V(x1,.,xn,z1,.,zp)because we do not know the values of the variables z1,.,zp. In order to apply a determination rule, one would need a source entity, as will be illustrated in the following. 2002,
86、G.Tecuci, Learning Agents Laboratory48Determinations: DiscussionDeterminations: DiscussionA determination rule is different from a deductive rule.The form of a deductive rule is:U(x1,.,xn,y1,.,ym) - V(x1,.,xn,y1,.,ym)That is, the variables which appear in the left hand side of a rule also appear in
87、the right hand side. Therefore, if we know that U(a1,.,an,b1,.,bm) is true, we could apply modus ponens to infer that V(a1,.,an,b1,.,bm) is also true.This type of reasoning is not possible in the case of a determinationU(x1,.,xn,y1,.,ym) - V(x1,.,xn,z1,.,zp)because we do not know the values of the v
88、ariables z1,.,zp. In order to apply a determination rule, one would need a source entity, as will be illustrated in the following. 2002, G.Tecuci, Learning Agents Laboratory49The basic procedure for answering the query V(T, ?z) by analogy:1. Find a determination such that U(?x, ?y) - V(?x, ?z)(i.e.
89、decide which determinations could be relevant for T: U(T, ?y) - V(T, ?z)2. Find a such that U(T, a) (i.e. find how the facts are instantiated in the target)3. Find a source S such that U(S, a) (i.e. find a suitable source)4. Find b such that V(S, b) (i.e. find the answer to the query from the source
90、: U(S, a) - V(S, b)5. Return b as the solution to the query(U(T, a) - V(T, b)U(S,a) U(T,a)V(S,b) V(T,?z)bAnalogy based on determinations: MethodAnalogy based on determinations: Method 2002, G.Tecuci, Learning Agents Laboratory50Let us consider the following targetNationality (Jack, UK), Male(Jack),
91、Height(Jack, 6), .and the problem of answering the following question by analogy What is the native language of Jack ? (i.e. Native-language(Jack, ?z)1. Find a determination such that U(x, y) - Native-language(x, z)Such a determination is: Nationality (x, y) - Native-language(x, z)2. Find a such tha
92、t Nationality (Jack, a)Nationality (Jack, UK)a = UK3. Find a source S such that Nationality (S, UK)Nationality (Jill, UK), Female(Jill) , Height(Jill, 510),Native-Language(Jill, English)S = Jill4. Find b in S such that NativeLanguage(Jill, b)Native-Language(Jill, English)b = English5. Return English
93、 as the solution to the queryNative-language(Jack, English)Analogy based on determinations: IllustrationAnalogy based on determinations: Illustration 2002, G.Tecuci, Learning Agents Laboratory51Determinations: DiscussionDeterminations: DiscussionConsider the determination rule:U(x1,.,xn,y1,.,ym) - V
94、(x1,.,xn,z1,.,zp)Should U and V be terms or could they be arbitrary logical expressions? Why?What if we cannot find a source S for applying the determination? 2002, G.Tecuci, Learning Agents Laboratory52Determinations: DiscussionDeterminations: DiscussionU and V may be an logical expressions. Exampl
95、e:The rainfall of a flat area determines the quantity of water in the soil of the areaRainfall(x, y) & Terrain(x, flat) - Water-in-soil(x, z)Rainfall(Philippines, heavy), Terrain(Philippines, flat), Water-supply(Philippines, high)Rainfall(Vietnam, heavy), Terrain(Vietnam, flat)Water-in-soil(Vietnam,
96、 ?t) 2002, G.Tecuci, Learning Agents Laboratory53Determinations: DiscussionDeterminations: DiscussionWhat if we cannot find a source S for applying the determination?Sometimes there is no source S such that U(S, a) is true, but one may find S such that U(S, a) is true. In such a situation one needs
97、a way to decide whether a and a are similar enough to infer V(T, b). Therefore, even in the case of determinations one may need a matching function.Example:Latitude of an area determines the climate of the areaLatitude(x, y) - Climate(x, z)Latitude(Romania, 45), Climate(Romania, temperate)Latitude(F
98、rance, 47) 2002, G.Tecuci, Learning Agents Laboratory54Determinations: DiscussionDeterminations: DiscussionWhat if we cannot find a source S for applying the determination?Sometimes there is no source S such that U(S, a) is true, but one may find S such that U(S, a) is true. In such a situation one
99、needs a way to decide whether a and a are similar enough to infer V(T, b). Therefore, even in the case of determinations one may need a matching function.Example:Latitude of an area determines the climate of the areaLatitude(x, y) - Climate(x, z)Latitude(Romania, 45), Climate(Romania, temperate)Lati
100、tude(France, 47) 2002, G.Tecuci, Learning Agents Laboratory55OverviewOverviewLearning by analogy: definitionDesign issuesThe structure mapping theoryProblem solving by analogyDeterminationsRecommended readingExercises 2002, G.Tecuci, Learning Agents Laboratory56Problem solving by analogyProblem solv
101、ing by analogyAnalogy means deriving new knowledge about an input entity by transferring it from a known similar entity. How could we define problem solving by analogy? 2002, G.Tecuci, Learning Agents Laboratory57Problem solving by analogy: definitionProblem solving by analogy: definitionProblem sol
102、ving by analogy is the process of transferring knowledge from past problem-solving episodes to new problems that share significant aspects with corresponding past experience and using the transferred knowledge to construct solutions to the new problems.What could be the overall structure of a proble
103、m solving by analogy method? 2002, G.Tecuci, Learning Agents Laboratory58The problem solving by analogy methodThe problem solving by analogy methodLet P be a problem to solve.First, look into the knowledge base for a previous problem solving episode which shares significant aspects with the problem
104、to solve.Next transform the past episode to obtain a solution to the current problem.What it means for problems to share significant aspects?How is the past problem solving episode transformed so as to obtain the solution to the current problem?What questions need to be answered to develop such a me
105、thod? 2002, G.Tecuci, Learning Agents Laboratory59The derivational analogy method (Carbonell)The derivational analogy method (Carbonell)Two problems share significant aspects if they match within a certain threshold, according to a given similarity metric. The solution to the retrieved problem is pe
106、rturbed incrementally until it satisfies the requirements of the new problem. 2002, G.Tecuci, Learning Agents Laboratory60The derivational analogy method (Carbonell)The derivational analogy method (Carbonell)Two problems share significant aspects if they match within a certain threshold, according t
107、o a given similarity metric. The solution to the retrieved problem is perturbed incrementally until it satisfies the requirements of the new problem. 2002, G.Tecuci, Learning Agents Laboratory61The derivational analogy method: illustrationThe derivational analogy method: illustration 2002, G.Tecuci,
108、 Learning Agents Laboratory62The derivational analogy method: discussionThe derivational analogy method: discussionHow does analogy facilitate the problem solving process?How does the derivational analogy method relates to the generally accepted idea that the relations which are usually imported by
109、analogy from a source concept S to the target concept T are those belonging to causal networks? 2002, G.Tecuci, Learning Agents Laboratory63The derivational analogy method: discussionThe derivational analogy method: discussionHow does this method relates to the generally accepted idea that the relat
110、ions which are usually imported by analogy from a source concept S to the target concept T are those belonging to causal networks?Intuition: The relation between a problem and its solution is a kind of cause-effect relationship.Fermats last theorem: There is no integer solutions of xn + yn = zn for
111、n2 Previously solved problem: Find integer solutions of the problem x2 + y2 = z2Problem: Find integer solutions of the problem x3 + y3 = z3Consider the following problem solving situation:What does this example suggests? 2002, G.Tecuci, Learning Agents Laboratory64DiscussionDiscussionExcept for the
112、trivial problems, a solution does not emerge immediately from the problem formulation, as would be the case in a cause-effect relation. What other relation from the problem solving process might be closer to a cause-effect relation? 2002, G.Tecuci, Learning Agents Laboratory65What other relation fro
113、m the problem solving process might be closer to a cause-effect relation? The relation between a problem and its derivation trace (i.e. solution process).What is transferred from a past problem solving episode is not a problem solution but the problem solving process itself, what questions have been
114、 asked, what factors have been considered, etc. One would try to repeat the same process in the context of the new problem.With this interpretation we retrieve the derivational analogy method:DiscussionDiscussion 2002, G.Tecuci, Learning Agents Laboratory66What other relation from the problem solvin
115、g process might be closer to a cause-effect relation? The relation between a problem and its derivation trace (i.e. solution process).What is transferred from a past problem solving episode is not a problem solution but the problem solving process itself, what questions have been asked, what factors
116、 have been considered, etc. One would try to repeat the same process in the context of the new problem.With this interpretation we retrieve the derivational analogy method:DiscussionDiscussion 2002, G.Tecuci, Learning Agents Laboratory67The transformational analogy method (Carbonell)The transformati
117、onal analogy method (Carbonell)Two problems are considered to share significant aspects if their initial analysis yields the same reasoning steps, that is, if the initial segments of their respective derivations start by considering the same issues and making the same decisions;The derivation of the
118、 solved problem may therefore be transferred to the new problem by reconsidering the old decisions in the light of the new problem situation, preserving those that apply, and replacing or modifying those whose supports are no longer valid in the new situation.Derivational analogy gives better result
119、s than transformational analogy. However, it has the disadvantage to manipulate complex structures representing derivational traces. 2002, G.Tecuci, Learning Agents Laboratory68OverviewOverviewLearning by analogy: definitionDesign issuesThe structure mapping theoryProblem solving by analogyDetermina
120、tionsRecommended readingExercises 2002, G.Tecuci, Learning Agents Laboratory691. Compare explanation-based learning, empirical inductive learning, and learning by analogy from the point of view of input information, background knowledge needed, and outcome of learning.2. Define learning by analogy a
121、nd give an example of analogy.3. Describe the four stages of learning by analogy.4. Illustrate learning by analogy with the help of the following example:ExercisesExercises 2002, G.Tecuci, Learning Agents Laboratory70Let us consider a learning by analogy system having the following background knowle
122、dge:Facts:Economy-type (Germany, highly-industrial), Location(Germany, Europe)Population(Germany, 70), Economy-type (Vietnam, agricultural), Location(Vietnam, Asia)Population(Vietnam, 70), Economic-state(Vietnam, poor), Economy-type (Japan, highly-industrial), Location(Japan, Asia),Population(Japan,
123、 100), Economic-state(Japan, excellent), Determination:Economy-type (x, y) - Economic-state (x, z)(the economy-type of a country determines the economic state of the country)Write a detailed trace of the reasoning of the system for answering the following question:What is the economic state of Germa
124、ny ? (i.e. Economic-state (Germany, ?z)ExerciseExercise 2002, G.Tecuci, Learning Agents Laboratory71Provide an example of a successful application of the transformational analysis method.Provide an example where the transformational analysis method does not apply, but the derivational analogy method
125、 does apply.What is the difference between a determination rule and a deductive rule?Illustrate the difference with an example.ExercisesExercises 2002, G.Tecuci, Learning Agents Laboratory72Provide an example of a successful application of the transformational analysis method.Provide an example wher
126、e the transformational analysis method does not apply, but the derivational analogy method does apply.What is the difference between a determination rule and a deductive rule?Illustrate the difference with an example.ExercisesExercises 2002, G.Tecuci, Learning Agents Laboratory73Recommended readingR
127、ecommended readingGentner D., Holyoak K.J., Kokinov B.N. (eds.), The Analogical Mind: Perspectives from Cognitive Science, The MIT Press, 2001.Carbonell J.G., Learning by analogy: formulating and generalizing plans from past experience, Machine learning I, 1983. Carbonell J.G., Derivational analogy:
128、 a theory of reconstructive problem solving and expertise acquisition, in Shavlik J. and Dietterich T. (eds), Readings in Machine Learning, Morgan Kaufmann, 1990. Also in Readings in Machine Learning and Knowledge Acquisition.Davies T.R., Russell S.J., A logical approach to reasoning by analogy, in
129、Shavlik J. and Dietterich T. (eds), Readings in Machine Learning, Morgan Kaufmann, 1990.Gentner D., The mechanisms of analogical reasoning, in J.W.Shavlik, T.G.Dietterich (eds), Readings in Machine Learning, Morgan Kaufmann, 1990.Winston P.H., Learning and reasoning by analogy, Communications of the
130、 ACM, 23, pp.689-703, 1980.Forbus K.D., Exploring Analogy in the Large, in Gentner D., Holyoak K.J., Kokinov B.N. (eds.), The Analogical Mind, 2001Tecuci, Building Intelligent Agents: An Apprenticeship Multistrategy LearningTheory, Methodology, Tool and Case Studies, Academic Press, 1998, pp: 101-108.
