\documentclass{article} %report?
%\usepackage{natbib} apa style etc.
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{subfigure}
\usepackage[pdftex]{graphicx}
\usepackage[english]{babel}
\usepackage[colorlinks=true, linkcolor=black, urlcolor=blue, pdfborder={0 0 0}]{hyperref}
%\usepackage{synttree}
%\usepackage[utf8x]{inputenc}

\title{Model Minimization in Qualitative Reasoning}
\author{Andreas van Cranenburgh \\ 0440949 \\ acranenb@science.uva.nl 
\and Hanne Nijhuis \\ 0364568 \\ hnijhuis@science.uva.nl}

\begin{document}
\maketitle

%perhaps picture here (something to do with minimization)

\vspace{4em}

\abstract{Qualitative Process theory provides a way of modeling causality in a
system on a qualitative level. Previous work has attempted to automatically
induce such qualitative models from behavior. We extend this work by turning
the resulting monolithic models into minimized, modular models, which makes
the induced models re-usable. The resulting minimization algorithm is general
enough to apply to user created models as well. We also sketch other possible
improvements for model induction, based on the exploitation of human
intuitions about systems rather than the current reliance on complete and
error-free data.}

\newpage

\tableofcontents

\newpage

\section{Introduction}

\section{Literature Review}

In this section we will review a few of the papers that have contributed
greatly to the definition of Qualitative Reasoning. We will give a short
summary of the papers and will conclude with an overview of the current field
of research and possible future work. 
%more text?

\subsection{Qualitative Reasoning}

The following papers describe the foundations of qualitative reasoning.
%more text

\subsubsection{A qualitative Physics based on confluences (de Kleer \& Brown)}

De Kleer et al. \cite{kleer} present a framework for formalizing physics in a
manner that is {\em qualitative} rather than {\em quantitative}. Whereas
physicists describe the world in terms of continuous differential equations,
the rest of the world uses an implicit psychological model of naive physics.
The framework of \cite{kleer} falls between these two extremes of precision and
informality. They employ confluences, which are qualitative differential
equations.  Although their framework is completely qualitative, as opposed to
standard physics, on the other hand their framework is formal in the sense of
explicitly defining causal and structural relations, as opposed to the
psychological models of humans (presumably). Moreover, their approach is based
on deriving qualitative physics from first principles, like normal physics, as
opposed to the contextual and tacit knowledge of mere mortals.

This approach is presented as being useful for physics education, expert
systems and even physics, in that it explicitly deals with causality. The
latter is in contrast with standard physics, in which laws are merely
exceptionless correlations with predictive value.

Advantages of this approach are that it works from first principles, so it is
grounded in science. Other advantages are that the models can be induced from
data, even when it contains noise. Disadvantages are that these constraint
models are less explanatory than process models (\cite{forbus}, p. 110), 
which we will review promptly.

\subsubsection{Qualitative Process Theory (Forbus)}

Around the same time as de Kleer \& Brown, another approach was introduced by
Forbus \cite{forbus}. The important points that set his work appart were,
among others, the \emph{quantity-spaces} and the \emph{sole mechanism
assumption}.

The principle of quantity spaces represents values by a set of ordinal
relationships. This enables the system to easily compare the different
quantities in terms of smaller, equal or larger. If such comparisons would
only occur between two values, then sign values would suffice (-,0,+), but for
many cases, the ordinal representation is more natural.

\vspace{0.8em}

Physical processes are viewed as the mechanisms through which change occurs.
To this end Forbus introduced the \emph{sole mechanism assumption} which
states that any behavior must be explainable by the direct or indirect effects
of some collection of physical processes.

\vspace{0.8em}

Forbus has reviewed his own work and the impact of his work in
\cite{forbus12}.
%more text

\subsubsection{Garp3 - Workbench for Qualitative Modelling and Simulation
(Bredeweg et al.)}

Garp is an implementation of Qualitative Process Theory with a focus on
educational uses.

1. Introduction
Qualitative Reasoning is an approach from AI that provides means to express
conceptual knowledge such as the physical system structure, causality, the
start and end of processes, the assumptions and conditions under which facts
are true, qualitative destinct behaviors, etc.  phenomena for which numerical
information is sparse or missing. Tools are being build to take a graphical
approach to building qualitative models. Out approacht want to preserve the
full expressiveness of the QR formalism and want to adreess domain experts and
support them in articulating and capturing their conceptual knowledge. The
software uses a diagrammatic approach for representing model content.

2. Background \& Characteristics
QR is a research area within AI that appeals to both fundamental reserach on
human cognition and to practical applications in indrustry. Humans are very
good in reasoning about the physical world using only fuzzy and qualitative
information (gentner and stevens 1983). Also experts refrain from using
numerical data but rather talk about cause-effect relationships. Ultimately a
robot should have the ability to understand this knowledge.

Conceptual models are defined as models that improce our understanding of
systems and their behaviour. in QR, quantities that describe the dynamic
features of a system typically hold qualitative information concerning the
current magnitude and direction of change, using an interval scale, consisting
of an ordered set of labels, eg {zero, low, medium, high}. such a set of labels
is called a quantity space. Landmarks are specific labels within this set
(acutally points) that refer to situations in which the behaviour of the system
changes significantly. For instance, a susbstance reaching its boiling
tempurature will stop getting hotter and start boiling.  in qualitative
simulations, the behavior of the system is represented as a graph of states
that reflect qualitatively distinct system behavior. There is a set of
dependencies that capture cause-effect relationships between quantities,
defined in such a way that they are both closely resembeling the conceptual
notions of human reasoning, as well as allowing automated computation because
they are grounded in mathematical formalisms. Two typical dependencies are
direct influences and proportionalities.
A QR engine has inference mechanisms to assemble the appropriate set of
dependencies that describes a system in a certain state of behaviour. Two
aspects are important for this approach: behaviour can be inferred from the
physical structure of the system, and knowledge about system behaviour is
stored in small fragments with conditional information detailing when such a
fragment is applicable (WE FOCUS ON THIS).

3. Representation and reasoning overview
Simulation is done by the Garp3 reasoning engine, using a state-by-state
strategy. Find-states constructs initial nodes in the state-graph based on the
scenario and model fragments. Then Find-transitions determines all possible
changes which form transition scenarios which are inputted into the find-states
procedure again.  
The reasoning process relies heavily on inequality reasoning.

4. Inequality reasoning: the mathematical engine
inequality relations typically change during the simulation, thereby
representing the dynamic aspects of the modelled system.  Points in a quantity
space are called landmarks and the intervals between are defined by these
landmarks. The core inequality reasoning only considers these landmarks and not
the intervals. Inequalities can specify the relation between several types of
model ingredients. The following five types of inequality relations are used in
Garp3: $Quantity \leftrightarrow Q$, $Q \leftrightarrow Landmark$, $L
\leftrightarrow L$, $Derivative \leftrightarrow D$, $D \leftrightarrow 0$.  at
the user-level representation, quantity values, landmarks and derivatives are
used, while at mathematical level, only landmarks exist and are used to
describe the others (for both magnitudes and derivative quantity spaces).

All the relations in the internal mathematical model of Garp3 have the
following form: Sum11  rel  Sum2 with $rel \rightarrow \{>,\ge,=\}$. The following
three basic principles are used to make inferences in the Garp3 inequality
reasoning engine:

- Bais algembraic simplification
- Anti-symmetry
- Transitivity

Example:

- $A>B$, $B>C$ (given)
- $(A>B)\&(B>C) \rightarrow A+B>B+C$ (transitivity)
- $A+B>B+C \rightarrow A>C$ (simplification)

7. Discussion
Garp3 does not discriminate explicitly between inequality statements that
should be treated as always true (e.g. inflow - outflow = net-flow), and those
that may change during simulation (eg. $Tx < Txboil \rightarrow Tx = Txboil$).
2nd order derivatives are important for sound simulations, but complete
validity cannot be guaranteed. This issue is in principle unsolvable, but does
not form a problem for the level of detail of models built in Garp3.  

Future work will focus mainly on improving usability of the software in terms
of GUI and debugging options.

8. Conclusions
The Garp3 workbench offers easy access to sphisticated qualitative simulation
software, providing users the possibility to use QR technology withou having to
understand low-level implementation details of such automated reasoners. An
increasing number of domain experts are using the workbench to capture
qualitative knowledge of system dynamics.  

Transitive inference is worth mentioning, because it computes a full transitive
closure of not a standard partial ordder but one that can be extended with new
nodes via additions and substractions. Heuristics are employed to keep the
search space within reasonable boundaries.

%more text

\subsubsection{Algal bloom in the Danube Delta (Cioca et al.)}

A Garp model of a system in the ecological domain, demonstrating its
applicability to the formalization of real-world problems.

%more to come

\subsubsection{Discussion}

The idea that Qualitative Reasoning can formalize actual common sense knowledge
and human understanding of physics is by now outdated. It is an instance of the
``Good Old Fashioned Artificial Intelligence'' (GOFAI) approach,
\cite{haugeland} and in line with the Symbol System hypothesis of Newell and
Simon \cite{newell}\footnote{``A physical symbol system has the necessary and
sufficient means of general intelligent action.''}.  Both of these have either
failed spectucularly or faded silently, often having been replaced by
stochastic and data-driven approaches \cite{russellnorvig}.  Claiming that
Qualitative Reasoning can provide a way to model actual common sense knowledge
or mental models is ostensively wrong -- the list of mismatches with human
intuitions is unmanageble, and among these mismatches are the parts where Folk
% cite examples from class/literature?
Physics is ostensively {\em wrong}. Specifically philosophers contend that
common sense is holistic at its core \cite{smith}, whereas explicit,
knowledge-based approaches are reductionistic in nature, because their aim is
to isolate context-free fragments. 

Therefore we submit that it is no longer useful to present it as a part of
Artificial Intelligence or having anything to do with common sense; while QR
models are certainly artificial, they are not in the least intelligent, nor are
they common or do they make sense to non-experts.  They are simply an explicit
formalization of a certain set of behaviors of interest. This does not mean
that Qualitative Reasoning is itself a fruitless enterprise -- it can be used
as an educational tool, where there is no need for bold philosophical claims.

With this educational focus in mind it makes sense to try to facilitate the
modeling process for non-experts for which QR is useful. To this end we turn
to the topic of model induction.

\subsection{Automated Modeling} %Automated or automatic?

To introduce the recent developments in the field of automated modeling we
will now review a few papers on this topic.

\subsubsection{Automated modeling in process-based qualitative reasoning
(Buisman)}

The concept of automated modeling for qualitative process theory was
introduced by Buisman \cite{buisman} in 2007. He motivates the research with
the goal to relieve the strain placed on experts and beginners, and to speed
up the modelling process. The approach he took however, does not attain these
goals yet, but is more of an exploration of the possibilities of using
Artificial Intelligence to induce models based on behavior graphs. We will
give a short overview of the algorithm he developed.

The input for the algorithm consists of:

\begin{itemize}

\item Behavior graph (states and state transitions) of a full envisionment

\item Scenario (partial information about structural relations between entities and their quantities)

\item ISA-hierarchy (full description of entity type hierarchy and quantities)

\end{itemize}

With this input, the algorithm produces models which are ready for simulation.
For each scenario they should give the same output as the original model.

There are certain constraints on the input. The \emph{full envisionment}
requirement means that the behavior is known for all possible initial values
for all quantities in the system. Also, the derivatives and amounts have to be
defined for every state. Finally, the input data cannot contain any noise,
ie., it should be perfect.

The algorithm starts with searching for so called \emph{naive dependencies},
which are dependencies that are consistent with the entire state-graph. They
are found by applying consistency rules on all pairs of quantities. These
consistency rules consider the amount and derivative values of the quantities
for all states, so as to induce possible dependencies. For example, a positive
influence between $Q_1$ and $Q_2$ could exist if for every state $A_s(Q_1) =
D_s(Q_2)$.  There will be redundancy in the set of naive dependencies which
has to be pruned by filtering out substitutionary groups, which are defined as
mutually exclusive possible disambiguations. 

%HAVE TO REWRITE THIS!!
%testing.. 

\subsubsection{Jochem}

Actuators

%more text

%less brute force, instead attempt to find the conceptually correct model
%immediately; added a knowledge base of actuators: common patters etc.

\subsubsection{Carsten}

%more text

Causal groups % feedback loops, interacting processes

\subsection{Overview}

%overview of what?


\newpage
%\chapter{Project} needs report document class

\section{Theory}

In the field of QR, models %( / scenario's / systems ?) 
consist of several smaller fragments which can be roughly divided in three
categories: static, process and agent. This categorization is not strict, but
gives a certain view on how things work. Static fragments are used to describe
the structure of a model, as well as proportionalities between quantities. A
static fragment cannot have any agents or influences in it. A \emph{process}
fragment should have at least one direct influence and is not restricted in
terms of dependencies. %(relations?)
Finally, \emph{agent} fragments should be used to describe any influences on a
system that are external, hence not part of the system itself.

Fragments can be useful to make the complete system more comprehensible --
ie., they are a form of chunking.  Also, while building these complex models,
fragments allow the user to focus on what happens in a small part of the
model, without having to worry about the other 'components'. For example in a
model describing a population, seperate fragments could describe processes
like birth, death, emigration, etc.

Recent work on automated modeling \cite{buisman, liem, vanweelden} has focused
on generating a correct model based on a full-envisionment behavior graph. The
current algorithms always produce a single model fragment which describes the
complete system. The implicit compositionality of a system is not revealed and
comprehending the output could become quite difficult with large models. We
therefore introduce a way of splitting and minimizing such monolithic models
into smaller fragments while preserving the exact same behavior.

\subsection{Interdisciplinary parallels}

\begin{itemize}

%\item Parsimony, Occam's razor (philosophy of science)
%wrong, parsimony refers to most simple explanation, not representation

\item Finite-State automaton miniminization, compression

	In automata theory there are well-known results regarding the
	minimization of grammars. For example there exists an algorithm to
	obtain a minimized version of a Finite-State automaton (FSA) which
	generates the exact same language with a minimum amount of states
	\cite{hopcroft}.

	Naturally this problem gets more difficult (no general purpose
	algorithms exist) higher up in the Chomsky hierarchy, so it would be
	an important result if it turned out that (a subset of) qualitative
	model simulation can be encoded as a Finite-State automaton that
	generates a regular language containing state-strings corresponding to
	behavior paths.

	A related but less hopeful result is that of Kolmogorov complexity,
	which states that given an arbitrary string, it is undecidable to
	verify whether a given program generating that string is the shortest
	one to do so (ie., highest compression), let alone to produce such a
	program given data.

	Determining the exact status of qualitative reasoning with respect to
	established results in automata theory or formal logic would shed light
	on the precise complexity and feasibility of model induction.
	%This is analogous to our goals.

\item Minimum Description Length principle 

	In Machine Learning there is the Minimum Description Length (MDL;
	\cite{mitchell}, p. 171, section 6.6)
	principle, which provides an inductive bias to choose among possible
	hypotheses for data, given a certain representation (the latter is
	crucial to success).  This provides a powerful heuristic because
	whenever a hypothesis is found that fits the data, all larger
	hypotheses can be discarded.
	
	If we apply this principle to qualitative model induction, then
	minimizing a model that fits the data will yield a better hypothesis
	according to the MDL principle.

\item Economy of Representation (Generative Linguistics)

	This principle states that representations are non-redundant. The
	abstract representation of a surface form like ``the boys walk'' will
	only contain the feature \textsc{plural} once, because agreement in
	number between the subject and verb is mandatory, and hence there is
	no point in storing the feature twice. 

	Similarly when a scenario in a qualitative model contains two trees,
	both should rely on one and the same dependency stating the relation
	between size and shade, not on two dependencies specific to their
	instances. 

\end{itemize}

\section{Approach}

In this section we describe our approach on minimizing, generalizing and
splitting single model fragments into modular and compositional fragments.

%more text

\subsection{Problem statement}

We take a monolithic model and divide it into several smaller fragments. To do
so, we need to comply to the following ranked list of
constraints:\footnote{Note that the terminology in this section of ranked
constraints, candidates and optimality is of course a nod to Optimality
Theory, FIXME cite smolensky.}

\begin{enumerate}
\item The model should be equivalent, that is, the resulting behavior should
	be exactly the same as the original given the same input (a scenario).

\item The output should be as parsimonious as possible, that is, fragments
	should be minimal.

\item General fragments are preferred over specific fragments; this entails a
	bias for smaller fragments and modularity.

\end{enumerate}

We make no claim as to the didactic and cognitive suitability of these
constraints, but it is not hard to imagine that these constraints will provide
an improvement when applied to any model lacking in modularity. It is well
known that modularity is a sound engineering approach, and there is no reason
to assume Qualitative Reasoning to be an exception. However, there are subtle
choices to be made as to the exact granularity of fragments, because these
constraints underdetermine the space of candidates, and because cognitive
optimality would demand empirical studies about chunking and comprehension
etc. We will gloss over these issues and apply the aforementioned constraints
without further claims of optimality.

\subsection{Algorithm}

Overview:

\begin{itemize}

\item Find a list of pivots, conditions on which the model fragments are
	based. Currently these are single structural relations.

\item For each pivot, find a set of dependencies which apply whenever the
	pivot is present, without exception

\item Generalize these dependencies into a single model fragment, several
	dependencies among instances may be collapsed into one

\end{itemize}

% fragments that can be generalized (ie., relations between quantity classes)
% collapes M into a set of sets containing generalized dependencies.
%
% incorrect definition (todo): fragments = smallest union of all possible sets
% { d | dependency(d) & d = generalized(di) & di in M } such that there is
% exactly one structural relation shared by them.
%
% where dependency is true for dependency triples, and generalized is a
% function that takes a dependency between instances of quantities and returns
% a dependency between the classes of those entities.

Sketch of the algorithm:

\begin{enumerate}

\item Input: take the set of dependencies, $M$, (as generated by eg. model
	induction or from a monolithic model fragment created by a user).  

\item Partition this set into equivalence classes according to the
	equivalence relation of the conditions under which each dependency
	holds.

\item Minimize each equivalence class by substituting 
	$Q_1 \overset{I+}{\rightarrow} Q_2 $ for a set such as 
	$ \{ Q_1^a \overset{I+}{\rightarrow} Q_2^b, Q_1^c \overset{I+}{\rightarrow} Q_2^d,  . . . \} $, 
	yielding elements of the set $MFs$

\item Dump the remaining dependencies in a single fragment, $UF$. 
	This set should be empty if the model is properly designed, ie., the
	model should not contain dependencies that apply to some instances but
	not to others.

\item Output: minimized model $ = MFs \cup \{ UF \} $

\end{enumerate}

This sketch can be formalized and instantiated into a definition with set
builder notation.\footnote{Note that the following definitions closely follow
our Prolog implementation, as such they include certain choices and
simplifications limiting the generality of the approach as previously
sketched.}  First two helper definitions. The first definition defines a
predicate for instances of structural relations and related quantities:

\begin{align*}
instance(R, E_1, E_2) :=
	\exists e_1, e_2 \; [ &struct\_rel(R, e_1, e_2) & \\
	\land \; &isa(e_1, E_1) \land isa(e_2, E_2) ]
\end{align*}
	
\begin{align*}
qinstance(R, Q_1, Q_2, q_1, q_2) :=
	\exists e_1, e_2 \; [ &struct\_rel(R, e_1, e_2) & \\
	\land \; &has(e_1, q_1) \land has(e_2, q_2)  \\
	\land \; &isa(q_1, Q_1) \land isa(q_2, Q_2) ]
\end{align*}

In this definition $q_n$ refers to an instance of a quantity $Q_n$, similarly
$e_n$ refers to an instance of an entity $E_n$; such pairs are related by the
$isa(a, b)$ predicate denoting that $a$ is an instance of $b$. Quantities and
entities are related by $has(e_n, q_m)$ denoting that $e_n$ has the quantity
$q_m$. Finally $struct\_rel(R, e_n, e_m)$ denotes the configuration that $e_n$
is structurally related to $e_m$ with relation $R$; for practical purposes
we assume that each entity has a reflexive relation called ``self,'' which
allows the isolation of dependencies between the quantities of a single
entity.\footnote{see the communicating vessels for an example with amount,
height and pressure of a container} %idea, besides implicit self relation,
%perhaps add unconditional relation holding between any two entities so that
%com.ves. can be splitted without an unfragment. but: relation is not unconditional, but a combination of two relations: vessel 1 and 2 are both connected to the same pipe, with from and to respectively.

The next definition defines an equivalence relation on these instances,
stating that their dependencies hold universally given their condition (which
is here restricted to a single structural relation):

\begin{align*}
samedeps(R, E_1, E_2, M) := \\
	\; \forall d, q_1, q_2 \; [ \; 
	(&dependency(d, q_1, q_2) \in M \\
	\land \; &qinstance(R, E_1, E_2, q_1, q_2, Q_1, Q_2)) \\
	%\land \; &isa(q_1, Q_2) \land isa(q_2, Q_2) \\ 
	%\land \; &has(q_1, e_1) \land has(q_2, e_2) \\
	%\land \; &isa(e_1, E_1) \land isa(e_2, E_2) ) \\
	& 	\rightarrow \forall e^\prime_1, e^\prime_2 \; [ \;
	 qinstance(R, E_1, E_2, q^\prime_1, q^\prime_2, Q_1, Q_2) \\
	%( isa(e^\prime_1, E_1) \land isa(e^\prime_2, E_2)  \\
	%&	\quad 	\land struct\_rel(r, e^\prime_1, e^\prime_2)  \\
	%&	\quad 	\land has(e^\prime_1, q^\prime_1) \land has(e^\prime_2, q^\prime_2) ) \\
	& \qquad \rightarrow dependency(d, q^\prime_1, q^\prime_2) \in M \; ] \; ]
\end{align*}

Here $dependency(d, a, b)$ denotes a directed relation $d$ between $a$
and $b$ (undirected relations can be expressed using two directed relations).
Possible values for $d$ correspond to influences, proportionalities,
correspondences and equalities. While $a$ and $b$ usually denote quantities,
note that they can also refer to an arithmetic operation between two
quantities, eg. $min(q_n, q_m)$.

These two predicates combined give us the set of pivots for a given
monolithic model:

\begin{align*}
pivots := \{ \; \langle R, Q_1, Q_2 \rangle \; | 
	\; instance(R, E_1, E_2) 
	\land samedeps(R, E_1, E_2, M) \} 
\end{align*}

After defining the pivots we simply map them to their dependencies to obtain
minimized, modular fragments:

\begin{align*}
fragments := \{ \; \{ \; dependency&(d, Q_1, Q_2) \; | \; \\
		& qinstance(R, E_1, E_2, q_1, q_2, Q_1, Q_2) \\
		\land \; & dependency(d, q_1, q_2)  \in M \\
	\; | \; \langle R, E_1, E_2 \rangle &\in pivots \lor 
	\langle R, E_2, E_1 \rangle \in pivots \; \}
\end{align*}

Note that while in this definiton pivots are restricted to single triples of a
relation and two quantities, the definition should be generalized so that
pivots can be merged into multiple triples when they are applicable under the
same conditions.

\section{Results}

The evaluation is based on a few well known example Garp models. 
We experienced some problems with the implementations of the AM algorithm.
The output of the automatic modeling implementations of \cite{buisman} and
\cite{vanweelden} is not easily accessible in a single prolog list, but rather
through a poorly documented Prolog database; the current implementation 
\cite{vanweelden} does not return equalities and arithmetic relations among
its output. The scenario and entity hierarchy is accessible through the Garp
API, but this is also less straightforward than it should be. 
%FIXME remove this whining and hack a garp interface together.

To avoid having to deal with these implementation matters we have based our
current proof of concept implementation on our own Prolog representation. Our
implementation expects as its input a flat list of dependencies, and as
background knowledge the scenario and entity hierarchy. Because of this the
evaluation had to be done manually.

The implementation of the algorithm previously described has certain
limitations which mean that the number of fragments is not as minimal as it
could be. This boils down to:

\begin{itemize}

\item not considering other conditions than structural relations as pivots

\item not considering multiple conditions for a single fragment

\item not considering merging the dependencies of multiple quantities
	belonging to the same entity in a single fragment

\end{itemize}

However, this seems to be largely an implemantion matter. The implementation
provides a proof of concept of the algorithm, more sophisticated
implementations can easily achieve more results.

%\subsection{Evaluated Models}

% paste some output here, take screenshots or save EPS files from Garp3
% todo: visual representation of results; either in Garp or Dia diagrams
% 	(whichever is least work).

\subsection{Tree and shade growth} 
% maybe show scenario with three trees, number of model fragments should stay the same! proof of concept.

When the tree \& shade model is splitted, the output remains a single model
fragment, because there is only one entity. If however one splits on the basis
of pairs of related quantities instead of on pairs of related entities, one
obtains the fragments as in figure \ref{ts_frags}, given the input as in figure
\ref{ts_mono}.

%Input in figure \ref{ts_mono} and output in figure \ref{ts_frags}.
%more text

\begin{figure}[ht]
\centering
\includegraphics[scale=0.5]{ts_mono-crop.pdf}
\caption{Monolithic model as input}
\label{ts_mono}
\end{figure}

\begin{comment}
\begin{verbatim}
Input: 
[dependency(inf_pos, growth_rate1, size1), 
dependency(prop_pos, size1,growth_rate1), 
dependency(prop_pos, size1, shade1),
dependency(q_correspondence, size1, shade1), 
dependency(q_correspondence, shade1, size1)]

Set of struct rels: 
[ (self, size, size), (self, shade, size), (self, shade, shade), 
(self, growth_rate, size), (self, growth_rate, shade), 
(self, growth_rate, growth_rate)]
\end{verbatim}
\end{comment}

\begin{figure}[ht]
\centering
\subfigure{
    \includegraphics[scale=0.5]{ts_growth-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{ts_sizeshade-crop.pdf}
}
\caption{After minimization: two model fragments for growth and size of shade}
\label{ts_frags}
\end{figure}

\begin{comment}
\begin{verbatim}
Fragments (2): 
[ (self, shade, size), 
	dependency(prop_pos, size, shade),
	dependency(q_correspondence, size, shade), 
	dependency(q_correspondence, shade, size)] 
[ (self, growth_rate, size),
	dependency(inf_pos, growth_rate, size),
	dependency(prop_pos, size, growth_rate)]

Unfragment: []
\end{verbatim}
\end{comment}

\subsection{Stacked bath tubs}

For the stacked bath tub model we changed the quantity space of flow to ZPM
(instead of ZP) because then we could replace the value-correspondences by a
single Q-correspondence.  For the input, see figure \ref{sb_mono}; for the
output, see figure \ref{sb_frags}.
%more text


\begin{comment}
\begin{verbatim}
Input: 
[dependency(inf_pos, flow12, level12), 
dependency(inf_pos, flow11, level11), 
dependency(inf_neg, flow12, level11), 
dependency(prop_pos, level11, flow12), 
dependency(q_correspondence, level11, flow12)]

Set of struct rels: 
[ (self, flow, flow), (self, level, level), (in, flow, level), 
(out, flow, level)]

Fragments (2): 
[ (in, flow, level), dependency(inf_pos, flow, level)]
[ (out, flow, level), 
	dependency(inf_neg, flow, level), 
	dependency(prop_pos, level, flow), 
	dependency(q_correspondence, level, flow)]

Unfragment: []
\end{verbatim}
\end{comment}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.5]{sb_mono-crop.pdf}
\caption{Monolithic bath tub model as input}
\label{sb_mono}
\end{figure}

% -----


\begin{figure}[ht]
\centering
\subfigure{
    \includegraphics[scale=0.5]{sb_in-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{sb_out-crop.pdf}
}
\caption{After minimization: two model fragments for flows going in and out respectively.}
\label{sb_frags}
\end{figure}

\subsection{Communicating vessels} 
%both two and three? maybe also the truly compositional one?

Inducing the communicating vessels model almost works, but the last two
equalities are not found, so they have been added manually. Also, the order of
arguments for proportionalities has been tweaked.  For the input, see
figure \ref{cv_mono}; for the output, see figure \ref{cv_frags}.

%FIXME: is this really true? or is it only because Carsten's equalities are
%asserted god knows where?
%more text


\begin{figure}[ht]
\centering
\includegraphics[scale=0.5]{cv2_mono-crop.pdf}
\caption{Monolithic model for two communicating vessels as input}
\label{cv_mono}
\end{figure}


\begin{figure}[ht]
\centering
\subfigure{
    \includegraphics[scale=0.5]{cv_amountflow-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{cv_amountheight-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{cv_flowamount-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{cv_pressureflow-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{cv_heightpressure-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{cv_flowpressure-crop.pdf}
}
\subfigure{
    \includegraphics[scale=0.5]{cv_unfragment-crop.pdf}
}

\caption{After minimization: seven model fragments for two communicating vessels.}
\label{cv_frags}
\end{figure}

\begin{comment}
Two communicating vessels:

\begin{verbatim}
Input: 
[dependency(inf_pos, flow3, amount5), 
dependency(inf_neg, flow3, amount4), 
dependency(prop_neg, flow3, pressure5), 
dependency(prop_pos, flow3, pressure4), 
dependency(prop_pos, height4, amount4), 
dependency(prop_pos, height5, amount5), 
dependency(prop_pos, pressure5, height5), 
dependency(prop_pos, pressure4, height4), 
dependency(q_correspondence, height5, amount5), 
dependency(q_correspondence, pressure4, height4), 
dependency(q_correspondence, pressure5, height5), 
dependency(q_correspondence, height4, amount4), 
dependency(equals, flow3, min(pressure4, pressure5)), 
dependency(equals, height4, pressure4), 
dependency(equals, height5, pressure5)]

Set of struct rels: 
[ (self, flow, flow), (self, amount, amount), (self, amount, height), 
(self, amount, pressure), (self, height, height), (self, height, pressure),
(self, pressure, pressure), (from, amount, flow), (from, height, flow), 
(from, pressure, flow), (to, flow, amount), (to, flow, height), 
(to, flow, pressure)]

Fragments (6):
[ (self, amount, height), 
	dependency(prop_pos, height, amount), 
	dependency(q_correspondence, height, amount)]
[ (self, height, pressure), 
	dependency(prop_pos, pressure, height), 
	dependency(q_correspondence, pressure, height), 
	dependency(equals, height, pressure)]
[ (from, amount, flow), dependency(inf_neg, flow, amount)]
[ (from, pressure, flow), dependency(prop_pos, flow, pressure)]
[ (to, flow, amount), dependency(inf_pos, flow, amount)]
[ (to, flow, pressure), dependency(prop_neg, flow, pressure)]

Unfragment: [dependency(equals, flow3, min(pressure4, pressure5))]
\end{verbatim}
\end{comment}

Three communicating vessels.
%more text

\begin{verbatim}
Input:
[dependency(inf_pos, flow3, amount5), 
dependency(inf_neg, flow3, amount4), 
dependency(prop_neg, flow3, pressure5), 
dependency(prop_pos, flow3, pressure4), 
dependency(prop_pos, height4, amount4), 
dependency(prop_pos, height5, amount5), 
dependency(prop_pos, pressure5, height5), 
dependency(prop_pos, pressure4, height4), 
dependency(q_correspondence, height5, amount5), 
dependency(q_correspondence, pressure4, height4), 
dependency(q_correspondence, pressure5, height5), 
dependency(q_correspondence, height4, amount4), 
dependency(equals, flow3, min(pressure4, pressure5)), 
dependency(equals, height4, pressure4), 
dependency(equals, height5, pressure5), 
dependency(inf_pos, flow4, amount6), 
dependency(inf_neg, flow4, amount5), 
dependency(prop_neg, flow4, pressure6), 
dependency(prop_pos, flow4, pressure5), 
dependency(prop_pos, height6, amount6), 
dependency(prop_pos, pressure6, height6), 
dependency(q_correspondence, height6, amount6), 
dependency(q_correspondence, pressure6, height6), 
dependency(equals, flow4, min(pressure5, pressure6)), 
dependency(equals, height6, pressure6)]

Set of struct rels: 
[ (self, flow, flow), (self, amount, amount), (self, amount, height), 
(self, amount, pressure), (self, height, height), (self, height, pressure),
(self, pressure, pressure), (from, amount, flow), (from, height, flow), 
(from, pressure, flow), (to, flow, amount), (to, flow, height), 
(to, flow, pressure)]

Fragments (6):
[ (self, amount, height), 
	dependency(prop_pos, height, amount), 
	dependency(q_correspondence, height, amount)]
[ (self, height, pressure), 
	dependency(prop_pos, pressure, height), 
	dependency(q_correspondence, pressure, height), 
	dependency(equals, height, pressure)]
[ (from, amount, flow), dependency(inf_neg, flow, amount)]
[ (from, pressure, flow), dependency(prop_pos, flow, pressure)]
[ (to, flow, amount), dependency(inf_pos, flow, amount)]
[ (to, flow, pressure), dependency(prop_neg, flow, pressure)]

Unfragment:
[dependency(equals, flow3, min(pressure4, pressure5)), 
dependency(equals, flow4, min(pressure5, pressure6))]
\end{verbatim}


\subsection{Population dynamics}
%single population? split into birth, migration etc.
%interacting populations? but ants garden is too much

%more text
TBD.

\section{Discussion}
We will now discuss several possible extensions both to model induction in
general and to model minimization in particular.
%more text

\subsection{Model minimization}

%more text

\subsubsection{Modular fragments as input}

Currently the implementation expects a single monolithic model as input, since
that is the output as given by the automated modeling algorithm. However, this
requirement could be lifted to allow partially modular fragments as input,
which is especially useful when the minimization algorithm is applied as part
of an interactive modeling assistant.

This could be implemented by finding a way to merge these fragments into a
monolithic fragment, while avoiding undergeneration by exploding all
dependencies to specific dependencies between instances. Such an extension is
fairly trivial but has not been implemented yet.

\subsubsection{Inheritance: hierarchy of fragments in output}

The output of our algorithm consists of a flat list of model fragments, but a
more advanced method would turn this into an inheritance hierarchy, to avoid
duplication and to increase re-use and clarity.

\subsection{Model induction}

\subsubsection{Conditions}

The induction algorithm has no support for conditions, except for
copying structural relations between entities as found in the scenario. This
severly limits the scope of models that can be induced. However, adding the
induction of conditions increases the complexity greatly. This is demonstrated
by an analogy to the Chomsky Hierarchy: with every addition of
context-sensitivity, the complexity increases, until it reaches Turing
equivalence in the unrestricted case. The Garp models that can currently be
induced are the subset of possible models such that only structural relations
can serve as conditions. 

On top of that, it only makes sense to add conditions to fragments, which
implies that splitting into fragments (but not minimizing) would need to be
integrated into the model induction algorithm itself instead of as a
transformation as has been presented in the current project.

\subsubsection{Interactivity}

The current requirement for the induction to have access to a perfect behavior
graph makes the algorithm virtually useless for practical purposes, because
such a behavior graph is very difficult to specify without already having a
qualitative model, which makes for a vicious circle. An alternative would be
to make the induction interactive. The algorithm would formulate a series of
maximally informative questions (comparable to automatic diagnosis
\cite{dekleerdiag}), employing the user as an informant. A series of
iterations can be performed, presenting the resulting behavior graph to the
user who can then highlight errors.

\subsubsection{Negative exemplars}

This brings us to the related problem of negative exemplars. Humans probably
have an idea not only of what a system does, but also what it does not do
(constraints). Negative exemplars are of course the very reason for the
problem of induction in philosophy \cite{hume, popper}.
However, since qualitative models are a formalization of human knowledge, not
induced from naturalistic data, negative exemplars are a resource that should
be exploited. Negative exemplars could be presented by the user in the form of
(in)equalities and as a list of impossible combinations of values.

\subsubsection{Inductive Logic Programming}

An alternative approach to model induction would be to use the general
framework of Inductive Logic Programming (ILP) \cite{mitchell}. This framework
provides a way to learn arbitrary Prolog programs based on background knowledge
and exemplars of predicates. In the case of inducing a Garp model this would
mean having the Garp engine as background, the behavior graph as the set of
exemplars, and model fragments represented as Prolog predicates (an encoding
would need to be defined) as output. In \cite{kuipers} (pp. 356 and on) a
method of axiomatizing qualitative models is discussed, in which state
transitions are first-order derivable theorems; this work could provide a good
starting point for an exploration of applying ILP to automated modeling.


% World domination etc.

\section{Conclusion}

Model minimization has been fruitfully applied to qualitative models. Our
approach is general enough that it applies both to Automatic Modeling and to
models made by beginners. From now on, minimizing qualitative models in Garp
can be done automatically, at least for the subset of models supported by the
proof of concept implementation. Further work on inducing models lies ahead
and given the results on inducing constraint models this work would seem to
have ample room for success.
%more text

\begin{thebibliography}{99}

% 1,5 - 2 pp. per artikel
\bibitem{newell} Allen Newell and Herbert A. Simon, ``Computer Science as
Empirical Inquiry: Symbols and Search,'' Communications of the ACM. vol. 19,
No. 3, pp. 113-126, March, 1976. \url{http://www.rci.rutgers.edu/~cfs/472
html/AI SEARCH/PSS/PSSH1.html}

%allebei
\bibitem{bredeweg-eco} Bredeweg, B. and Salles, P. (2009), Handbook of
Ecological Modelling, Chapter 19 - Mediating conceptual knowledge using
qualitative reasoning. In: J\/orgen, S.V., Chon, T-S., Recknagel, F.A. (Eds.),
Handbook of Ecological Modelling and Informatics. Wit Press, Southampton, UK,
pp. 351.398.

%allebei
\bibitem{bredeweg-garp} Bredeweg, B., Linnebank, F., Bouwer, A. and Liem, J.
(2009) 02 Bredeweg EtAl ECOINF 2009.pdf (598.325 Kb) Garp3 - Workbench for
Qualitative Modelling and Simulation. Ecological Informatics 4(5-6), 263-281.

%hanne
\bibitem{forbus} Forbus, K.D. (1984) Qualitative process theory. Artificial 
Intelligence, 24:85-168. 

\bibitem{forbus12} Forbus, K.D. (1993) Qualitative process theory: twelve years
after. Artificial Intelligence, 59:115-123. 

%andreas
\bibitem{kleer} Kleer, J. de and Brown J.S. (1984) deKleerBrown1984.pdf (4.005
Mb) A qualitative Physics based on confluences, Artificial Intelligence,
24:7-83 %(for the course you may ignore section 6)

%andreas
\bibitem{cioaca} Cioaca, Linnebank, Bredeweg, Salles 2009 Cioaca EtAlECOINF
2009.pdf (1,001.442 Kb) A qualitative reasoning model of algal bloom in the
Danube Delta Biosphere Resere (DDBR) in: \emph{ecological informatics 4} (2009)
p282-298

%hanne
\bibitem{buisman} Buisman, H., ``Automated modeling in process-based
qualitative reasoning''
\url{http://staff.science.uva.nl/~bredeweg/pdf/BSc/20062007/Buisman.pdf}

% (samenvatting van Buisman plus verbeteringen)
%hanne 
\bibitem{liem} Liem, J., Buisman, H. and Bredeweg, B., ``Supporting
Conceptual Knowledge Capture Through Automatic Modelling''

%hanne
\bibitem{vanweelden} van Weelden, C., ``Automated modeling of conceptual
knowledge'' \url{http://staff.science.uva.nl/~bredeweg/pdf/BSc/20082009/vanWeelden.pdf}

\bibitem{mitchell}
	Mitchell, Tom (1997), ``Machine Learning,'' McGraw Hill.

\bibitem{hopcroft}
	John Hopcroft and Jeffrey Ullman (1979). 
	``Introduction to Automata Theory, Languages, and Computation.'' Addison Wesley.

%\bibitem{russellnorvig}
%	Russell S, Norvig P (1995). 
%	``Artificial Intelligence: A Modern Approach,'' 
%	Prentice Hall Series in Artificial Intelligence. Englewood Cliffs, New Jersey

\bibitem{haugeland}
	Haugeland, John (1985), 
	``Artificial Intelligence: The Very Idea,''
	Cambridge, Mass.: MIT Press, ISBN 0-262-08153-9 .

\bibitem{smith}
	Barry Smith and Roberto Casati (1994)
	``Naive Physics: An Essay in Ontology.''
	{\em Philosophical Psychology}, 7/2, pp.\ 225-244.

\bibitem{dekleerdiag}
	De Kleer, J. and Williams, B. C. 1989. Diagnosis with behavioral modes.
	In \emph{Proceedings of the 11th international Joint Conference on Artificial
	intelligence - Volume 2} (Detroit, Michigan, August 20 - 25, 1989).
	International Joint Conference On Artificial Intelligence. Morgan
	Kaufmann Publishers, San Francisco, CA, 1324-1330. 

\bibitem{hume} 
	Hume, David (1910) [1748]. 
	``An Enquiry concerning Human Understanding.''
	P.F. Collier \& Son. 
	\url{http://18th.eserver.org/hume-enquiry.html#4}. 
	Retrieved 27 December 2007.

\bibitem{popper}
	Popper, Karl (1959). 
	``The Logic of Scientific Discovery.'' pp. Ch. 1. 
%	"...the theory to be developed in the following pages stands directly
%	opposed to all attempts to operate with the ideas of inductive logic."

\bibitem{kuipers}
	Kuipers, Benjamin (1994). ``Qualitative reasoning: modeling and simulation with incomplete knowledge,''
	MIT Press, ISBN	026211190X, 9780262111904

\end{thebibliography}

\end{document}

----------------------------------------------

Ideas

    * done: split code for model output into generation & garp adding
    * done: compositional model fragments 
    * deferred: (also: accept existing model fragments as input)
    * deferred: lift full envisionment requirement, accept negative input (eg. list of impossible value combinations).
    * deferred: user interaction: graphical dialog to choose best model in case of ambiguity

----------------------------------------------
Todos

    * done: fix influences
    * done: fix output of models to garp. deferred: each possible model should become a model fragment (too much ambiguity)
    * done: split into multiple model fragments: working code: qrsplit
    * done: collapse similar model fragments into generic model fragments (eg. Faucet1 =>I+ Bath1 and Faucet2 => I+ Bath2 becomes Faucet =>I+ Bath)
    * done: detect necessary structural relations / other conditions required to make a model fragment generic.
    * done: try other models listed in van Weelden & Buisman. notably, communicating vessels
    * distinguish between static (no influences) & process; filter current list of fragments and split them in a static and a process list.
    * integrate code with model induction (input) & garp (output)
	* input directly from AM database instead of coded by hand: hgp file is an XPCE object, look in /tmp (.pl source) 
	* output of minimized (split) models to garp.

    * report: 
	- Intro 
	- Summary per paper (literature review) 
	- Discussion 
	- Conclusion 
	- Project 
	- Theoretical / Practical / Technical Perspectives 
	* further details: blackboard

----------------------------------------------

Minutes
April 13th 2010

New plan:

    * Some sort of standard for what a well-formed fragment should be
    * -- Static vs process fragments?
    * -- Everything per entity 1 fragment?
    * -- Things like 'birth', 'death', 'emigration' and 'immigration'?
    * -- Influences?

    * We need some sort of evaluation to check our models against.

    * First run a the models we want to use and analyze their current output, compare them to our 'ideal' output.
    * We should not worry about intergration with the current Automatic Modeling code for now. First focus on hand-corrected input.
    * Recognizing duplicate (super)cluster could be a nice step to start with.. to get working on the code.

Notes:

    * Influences: now written to screen --> should be asserted
    * I's wrong direction? (inf-pos-a-b = b --> a)
    * naive dependencies: exponential
    * Communicating vessels: hack in causal groups: same entities (same_object_group/2)
    * Choose hacks for conceptually best model

    * Discussed with Floris that finding correspondences could be done faster by first looking for them without considering naive_dependencies yet.


----------------------------------------------

Requirements for the thesis:

 

1) The thesis consists of two parts, a literature review and a project report.

Both parts can be done in pairs or individually if this is preferred. In the
end each student should submit one integrated document. (Note that this makes
life easier: in your report you will be able to refer to concepts discussed in
the review.)

The total amount of pages should be around 30, figures included, with each part
taking about half. (Note that in general less pages may be better if all
arguments are still explicit and clear, but this is also harder in practice.
So, aim for making your points clearly and logically without unnecessary
words.)

2) The literature overview of the papers (or sections of papers) we've
discussed in class should be a scientific review, and it should show that
you've read and understood them.

A possible approach is to start with a general introduction, then summarize and
discuss each paper, and then end with a short conclusion of the papers.

The level of detail should be in between the paper itself and an abstract.
Saying state graphs are generated by a procedure is too general, listing the
steps in the procedure is too detailed. Instead give the general idea of the
procedure and discuss its properties, pros and cons.

(Hints, but not requirements: a) It is nice if you can link the papers together
in your discussion. b) It is also nice if you can use the review to introduce
the problem area of your project research. c) Note that the papers we've
discussed each have different perspectives: theoretical, technical,
application/modeling)

3) The report on your project should be like a scientific research paper and it
should be provide sufficient detail such that someone else could replicate your
work. Be sure to make all your assumptions, choices and reasoning steps
explicit.

4) If you want feedback you can submit initial versions of papers for feedback.
Allow for a couple of days for reading of course, and I will provide mainly
overall feedback on whether you're moving in the right direction or which other
approach you could take. Still this should save you time and effort, so take
the opportunity!

5) The final deadline for the thesis is Friday the 28th of May, 18:00 hours.

NB This deadline is solid as a rock, no exceptions, so evade Murphy's law and
plan in some reserve time.

Last but not least: Good Luck, Start in Time, & Have Fun!


