Qualitative Reasoning(QR) 2016. 09. 21 권순현 kwonshzzang@etri.re.kr

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

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

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

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

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)이 발생하기도 함

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

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?

Possible behaviors of two-tank system

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를 구현했음 추론 내에서 사용되는 개념과 관계를 온톨로지를 이용하는 시도가 있음

Garp3, DynaLearn#2

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

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

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

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

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

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

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

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

Example

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

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)

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

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

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

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.

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

Inequality example

Aggregate Scenario Model fragment

Scenario Describe the initial state of the system

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

Static Model Fragment

Process Model Fragment

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

State Graph

Quantity value history

Qualitative Causal Model

Qualitative Reasoning

Qualitative Reasoning Three main elements Find states Find transitions Inequality Reasoning

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

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

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

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

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:

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

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

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

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

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

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

Transitive Reasoning

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

Visual Reasoning Place vocabulary

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

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

Thank you kwonshzzang@etri.re.kr SoonHyun Kwon