Qualitative Reasoning(QR)

Presentation on theme: "Qualitative Reasoning(QR)"— Presentation transcript:

1 Qualitative Reasoning(QR)
권순현

2 outline Introduction to qualitative reasoning
Qualitative representation and reasoning Qualitative spatial reasoning Summary

3 Example What can happen when you leave a tea kettle on a stove unattended for an hour?

4 Example What can happen when you leave a tea kettle on a stove unattended for an hour?

5 Qualitative Reasoning(QR)#1
정성적 추론(QR) 초기 연구 주로 물리학(physics)에서 시작 물리학은 복잡한 물리공식에 의해 여러 현상을 표현하고 결과를 ‘계산＇해 내는 ‘정량적 수치＇가 중요 QR은 정성적 표현(Qualitative Representation)과 정성적 추론(Qualitative Reasoning) 을 위해 ‘-, +, 0’ 등의 state 값이나 ‘비례관계‘와 같은 abstract한 표현으로 물리현상을 설명하고 결과를 ‘예측’하려 시도 물리적 공식 없이 인과관계 모델(causal model) 만으로 추론 Stove 온도 상승 -> 주전자에 담긴 물의 온도 상승(기화) -> 주전자 온도 상승 -> 주전자 연소

6 Qualitative Reasoning(QR)#2
Entity: 상태가 변화되는 주체 Quantity: 수치가 아닌, quantity value space로 표현되는 abstract한 개념의 quantity State: entity가 quantity가 변해서 특정 point(또는 landmark)에 이른 상태 QR 어떤 entity의 quantity가 변화되면 특정 state에 이르게 되고, state의 변화경로를 예측하는 것. 변화경로는 state graph, behavior path 등으로 불림. 변화경로는 정확한 수치에 의해 계산된 것이 아니기 때문에, 여러 entity가 참여하게 되면 다양한 경우의 수가 만들어짐 변화경로가 다양하게 생성되기 때문에, 여러 정성적 추론 결과 (state endpoint)가 만들어짐 이러한 이유로 모순(ambiguity)이 발생하기도 함

7 QR definition A means to express conceptual knowledge such as the physical system structure, causality, start and end process, assumption and conditions which facts are true, qualitatively distinct behavior, etc. (Bredeweg et. al. 2009) Motivated by human congnition

8 Examples(a two-tank system)
A simple two-tank system, with tanks of equal width, for which it is known that both tanks contain amount of oil and that the oil-column is higher on the left-hand side(LHS) Let us assume that the relative heights of the two tanks are unknown. Now suppose that two tanks are connected via pipe with a valve, at the bottom of the container. When the valve closing this pipe is opened, what behaviors may happen?

9 Possible behaviors of two-tank system

10 Garp3, DynaLearn#1 OR 연구배경
정성적 추론 연구는 1990년대 중반까지 Forbus를 중심으로 활발히 연구가 진행됨 1990년대 말에서 2000년대 초반까지 연구논문 수가 급감하는 양상을 보임 => Logic과 관련한 연구가 DL(Description Logic)을 중심으로 술어논리(Predicate Logic), 온톨로지 지식표현 등으로 진행됨(개인적 생각) 본격적으로 다시 연구가 시작된 것은 EU FP6 지원을 받은 NaturNet-Redime Project의 Garp3와 EU FP7으로 이어지는 DynaLearn 프로젝트임. 두개의 프로젝트들은 암스테르담 대학의 Bert Bredweg을 중심으로 진행 QR을 위한 Modeling, Simulation을 수행할 수 있는 프로그램을 만들고, 이를 교육에까지 사용하고자 시도했음 두개의 프로그램(Garp3, DynaLearn)은 Prolog를 기반으로 QR 알고리즘과 UI를 구현했음 추론 내에서 사용되는 개념과 관계를 온톨로지를 이용하는 시도가 있음

11 Garp3, DynaLearn#2

12 Garp3, DynaLearn#3 Entity간의 관계 및 Quantity 변화에 대한 규칙을 시나리오로 작성

13 Garp3, DynaLearn#4 State endpoint(2, 3, 6, 8, 10)
앞의 시나리오 대한 시뮬레이션 수행(추론) 결과 = State Graph State endpoint(2, 3, 6, 8, 10)

14 Garp3, DynaLearn#5 각각의 endpoint에 이르기 quantity의 value history

15 Applications Monitoring, diagnosis, failure modes and effects analysis, creating control software, explanation generation, tutoring…

16 Principles of Qualitative Representation
Discretization Represent continuous quantities using entities that can be reasoned symbolically providing a way to do abstraction Instead of using a numerical value for rate of change, consider whether it is increasing, decreasing or constant Relevance Choose qualitative values based on relevance to a task If temperature is changing, boiling point may be important If temperature is constant, boiling point may be irrelevant Ambiguity Abstraction leads to ambiguity Instead of providing one answer, provide a range of answers

17 outline Introduction to qualitative reasoning
Qualitative representation and reasoning Qualitative spatial reasoning Summary

18 Qualitative Process (Representation and Reasoning)
Structure Behavior Aggregate Simulation We will consider each of these in more detail with examples The detailed definitions of these can also be viewed as an ontology of qualitative reasoning

19 Structure Entities Agent Assumptions Configurations
Physical objects or abstract concepts that constitute the system Their relevant properties are represented as quantities that may change under the influence of processes Agent Entities outside the modelled system Agents can have quantities that influence system Such quantities are called exogenous quantities Assumptions Conditions that are presumed to be true Configurations Relations between instances of entities and agent

20 Example

21 Behaviour Quantity Direct influence Proportionality Correspondence
Quantity Space Magnitude and derivative Direct influence Proportionality Correspondence Inequality

22 Quantity Quantities represent changeable features of entities and agents. Represented by their quantity value which consists of magnitude and derivative Quantity space specifies the range of possible values for a quantity Magnitude indicates the current value of a quantity Derivative indicates how the quantity is changing(can be +, -, 0)

23 Quantity The quantity space representation needs to be chosen based on the application needs Need to introduce landmarks The quantity space for the temperature of a substance

24 Direct Influence Directed relations between two quantities
Can be either positive(I+) or negative(I-) Cause of change within a model, and there, a model processes Magnitude of influencing quantity determines the rate of change of affected quantity

25 Proportionality Directed relations between two quantities
Propagate effects of processes Set the derivative of the target quantity depending on the target of the source quantity

26 Correspondence Relations between qualitative values to different quantities and can be either directed or undirected Directed: When value A of quantity X corresponds to value of quantity Y, we can derive that Y has value B when X has has value A Example: When size of population is zero, the birth rate is also zero. When size of population is large, the biomass is large.

27 Inequality Inequalities specify (<, ≤, =, ≥, >) an ordinal relation between items Between magnitude A quantity and a value from quantity space The temperature is at boiling point Magnitude of two quantities Temperature of substance A > Temperature of substance B Values from the quantity spaces of two quantities Boiling point of water < boiling point of oil Between derivatives

28 Inequality example

29 Aggregate Scenario Model fragment

30 Scenario Describe the initial state of the system

31 Model Fragment Describe part of the structure and behavior of the system in a general way Can be thought of as rule Can be represented as conditions or consequences Three kinds of fragments Static: Structure of the system and proportionalities Process: Contain at least one direct influence Agent: Contain an agent, ie, an element external to the system may not be influence by the system but could influence it

32 Static Model Fragment

33 Process Model Fragment

34 Qualitative Simulation
State Describes a particular situation of a modeled system reflecting qualitatively unique behavior State-graph A set of states and the possible transitions among time Value history Shows how quantity values change Equation history Show how the ordinal relations change Causal model Describes how quantities are causally related

35 State Graph

36 Quantity value history

37 Qualitative Causal Model

38 Qualitative Reasoning

39 Qualitative Reasoning
Three main elements Find states Find transitions Inequality Reasoning

40 Find States Select and apply model fragments Determine state dynamics
Compare states

41 Select and Apply Model Fragments
Ingredients Structural(entities, agents, …) Behavioral(value, inequality, …) Causal(influence, …) Check behavioral conditions Known: apply Contradiction: reject Unknown: check later Assumptions can be made Consequences are applied

42 Determine State Dynamics
Account for exogenous effects Influence resolution 𝐼+ rel 𝐼− (where rel 𝜀 { >, ≥, =, ≤, <, ?}) 𝑃+ rel 𝑃− (where rel 𝜀 { >, ≥, =, ≤, <, ?}) Assumes that the processes involved have comparable effects

43 Find State Transitions
Find model ingredients that may change and lead to termination of the state transition of value to adjoining value in quantity space, etc Combine changes to assess the order in which terminations may happen and determine valid combinations Apply continuity rules to each combination to procedure a complete transition scenario

44 Inequality Reasoning Based on Examples: algebraic simplification
(sum1 + V) rel (sum2 + V) → sum1 rel sum2 anti-symmetry (sum1 ≥ sum2) & (sum2 ≥ sum1) → sum1 = sum2 transitivity Examples:

45 Inequality Reasoning Triggered any time we
Add a new inequality relation or a new correspondence Inequality reasoning infers new relations and checks if it is simplifiable Not circular Not derivable Not evident Not invalid If it passes all the tests, it is added to the set of known relations

46 Example Conclusions If we keep heating the kettle, it will eventually burn For two containers connected by a tube, there are 6 possible states Too much ran leads to mosquitoes if there is insufficient drainage

47 Summary of Qualitative Process Representations
Qualitative representations Proportionality, influence, correspondences, inequalities Qualitative reasoning Simulation of states, influence calculus, inequality reasoning Captures important aspects of human reasoning Can use partial and incomplete information Support causal reasoning

48 outline Introduction to qualitative reasoning
Qualitative representation and reasoning Qualitative spatial reasoning Summary

49 Qualitative Spatial Reasoning
Two approaches Purely qualitative spatial relationships Topology, orientation, direction Spatial representations needed for visual representations diagrams

50 Topological Spatial Relations
Jointly exhaustive pair wise disjoint relationships(JEPD)

51 Transitive Reasoning

52 Visual Reasoning There are situations when the input is available qualitatively Verbal descriptions Route descriptions Shape descriptons

53 Visual Reasoning Place vocabulary

54 outline Introduction to qualitative reasoning
Qualitative representation and reasoning Qualitative spatial reasoning Summary

55 Summary Qualitative representation and reasoning provides techniques that aim to model how people understand the continuous aspects of the world Formalize everyday notions of causality and provide accounts of how ground symbolic relational representation in perceptual processes Qualitative processes, spatial relations, visual reasoning Numerous applications in education, ecology, diagnosis, engineering

56 Thank you SoonHyun Kwon