🚀 go-pugleaf

From: wrobel@gmdzi.uucp
To: mod-ki@unido.informatik.uni-dortmund.de
Date: Thu, 10 May 90 19:09:56 +0100
Subject: Change of Representation Workshop (report, long)
Keywords: Berichte

mod-ki message 0461
************************************************************************
                  Report about the 2nd Workshop on
        Change of Representation and Problem Reformulation

                           Stefan Wrobel
       GMD (German Natl. Research Center for Computer Science)
                   Research Group Expert Systems
                        wrobel @ gmdzi.uucp

                            10. 5. 1990
 
### 1. Introduction ###

The *2nd Workshop on Change of Representation and Problem  Refor-
mulation*  was  competently  organized  by  Jeffrey van Baalen of
Price Waterhouse, an international business consulting firm,  and
took  place  at their research center in Menlo Park, CA, on March
24 and 25, 1990. Even though a public call for  papers  had  been
posted,  attendance  was  by  invitation  only based on submitted
research summaries and/or extended paper abstracts. The resulting
audience  of 34 researchers was very qualified and focused on the
topic of the workshop, even though  not  all  groups  working  on
representation  adjustment  were  represented.  European partici-
pance was very low as well.
 
The sessions themselves were divided into 2 or 3 plenary talks of
35  minutes  including discussion, augmented by special 30 minute
discussion periods that concluded a group of related talks.  This
organization provided sufficient discussion time, even though the
summary discussions were often used for questions  to  individual
presenters. This suggests that longer question periods might have
been beneficial. Since meals were  served  ``on  location'',  the
small  size  of  the  workshop  allowed for good interaction both
within and between sessions.
 
The research presented at the workshop reflects a subdivision  of
the  Change of Representation field into three lines of work, two
of which are oriented towards problem solving, and one  which  is
oriented  towards Machine Learning. A fourth group of researchers
was presenting their theoretically oriented work  on  representa-
tion  change  based on category theory.  In the following we sum-
marize the talks in each of those groups. Notably absent from the
workshop  was  any  work  on the emergence of representation from
perceptual information.  There are no  official  proceedings,  so
papers should be obtained by contacting the authors directly.
 
### 2. Reformulation for problem solving ###
 
The first group, which we might call ``reformulation for  problem
solving'',  is  concerned  with  transformations  of  a problem's
search space in order to make it simpler, smaller, or more  effi-
cient  to  work with.  Those reformulations are usually predeter-
mined and carried out automatically, i.e., here, the focus is not
(yet)  on  automating  the  process  of designing reformulations.
*Saul Amarel's  (Rutgers)* classical work on the Missionaries and
Cannibals  problem  is  a good  example.  At the workshop, Amarel
discussed this work and its continuations  in an invited talk.
 
*Jeffrey van Baalen (Price Waterhouse) * showed  how  a   theorem
prover  can  operate  much more efficiently if the constraints of
the  problem are moved from general logical axioms into  special-
ized   representations which reflect the constraints syntactical-
ly, eg.  by changing the   representation  of  a  predicate  with
functional  properties  into  a  function,  or   creating special
representational objects that locally enforce eg.  symmetry  (cf.
hybrid reasoners).
 
*Craig Knoblock (CMU)*  presented  a  way  of  learning  problem-
specific  abstraction hierarchies for hierarchical planning.  His
ALPINE  system   determines  classes  of  literals  that  can  be
achieved  without interfering with  classes higher in the hierar-
chy based on the operators' pre- and postconditions;  since  con-
dition  arguments/instantiations  are ignored, the granularity of
the  classes is relatively coarse.
 
The work of *David Zhu  Jean-Claude  Latombe  (Stanford)*   dealt
with  reformulation in robot motion path planning.  From the ini-
tial representation of the robot as a rectangle and the shapes of
the  obstacles,   their  system  computes ``grown'' shapes of the
obstacles that allow the  representation of the robot as a point,
making path computations a lot easier.
 
Finally, *Daniel Weld (Univ. of Washington)*  examined how a sys-
tem  can select  an appropriate model for a prediction task based
on a given set of models, i.e.,  the focus of the work is on  how
to  compare  two models, and estimate how  their differences will
affect the predictions.
 
### 3. Compilation for problem solving ###
 
The second group, which we might call ``compilation  for  problem
solving'',  is  concerned with the generation of efficiently exe-
cutable forms of an available general model.  In contrast to  the
first  group,  this  usually does not involve the introduction of
new representation elements (as in eg. van  Baalen's  work),  but
consists  instead of determining which parts of the general model
are relevant for a particular solution, and  expressing  them  in
operational  terms to yield a problem solving rule.  Explanation-
based learning is of this general type.
 
At the workshop, the work of *Giuseppe Cerbone and  Tom  Dietter-
ich* dealt with the problem of how to deal with numeric models in
compilation, presenting  a  compilation-based  solution  for  the
non-linear  optimization  task  of  2-d structural design.  Their
system analyzes numerically-derived  designs  to  detect  general
geometric  patterns  that can act as constraints in future design
task; new geometric features are created when necessary.
 
*Nick Flann (also Oregon State  Univ.)*  presented a  method  for
dealing  with  intractable proofs in EBL as they occur eg. in op-
ponent planning, where one needs to  operationalize  proofs  that
include  universal quantification over operators.  By employing a
more abstract representation of the  influence  of  operators  on
goals,  the  proofs  can be restricted to the relevant operators,
allowing an operationalization that  is  incomplete  (applies  to
only part of the problem domain), but guaranteed correct.
 
In short presentations during a special session  on  ``Reformula-
tion  for  engineering  problem  solving'',  *Brian  Falkenhainer
(Xerox PARC)*, *Mark  Shirley (Xerox PARC)*, and *Richard  Keller
(NASA  Ames)* discussed the general  issues in (qualitative) rea-
soning from general models. With respect to  representation, they
emphasized  the  necessity of using multiple models at  different
levels  of  granularity  and  with  different  viewpoints  (Falk-
enhainer),   and  being  able  to  combine  them into specialized
models with less coverage but  better efficiency (Keller).
 
### 4. Inductive change of representation ###
 
The third line of research,  ``inductive  change  of  representa-
tion'', seeks to automate the process of Change of Representation
by introducing new terms or selecting a better  formalism.   Most
of  the  presented  work  was within the ``traditional'' symbolic
learning framework.
 
*Ruediger Wirth (UC Irvine)*  presented  the  inverse  resolution
``G''  operators   that are used in his LFP2 system.  They intro-
duce new terms based on the  inversion  of  resolution  steps  in
several  (failed)  proofs.  This restricts the search  space com-
pared  to  inverse  resolution  based  on  one  example  (as   in
Muggleton's   CIGOL) and allows the relaxation of the unit clause
restriction, but requires that  all relevant facts are  known  to
prevent overgeneralization.
 
*Kevin Thompson  and  Pat  Langley  (NASA  Ames)*  described  LA-
BYRINTH, an extension of existing  conceptual clustering programs
(particularly COBWEB) to inputs  using   structured  (relational)
information.  The  key  idea in the approach is to regard  struc-
tured objects as trees based on the  ``part-of''  relation.   The
system  then  first  clusters the leaves of this tree (the atomic
parts of the structured object). It then  replaces  those  leaves
by their now-known class names, which means the next  higher lev-
el in the tree is now described by non-structured attributes, and
thus   be  clustered by repeated application of the same process.
This reuse of  discovered terms is new in  search-based  cluster-
ing.
 
*Stefan Wrobel (GMD)*  presented  the  representation  adjustment
method used in MOBAL, which also uses structured information, but
introduces terms in a demand-driven fashion,  thus  avoiding  the
resource  allocation problem between rule  discovery and new term
introduction. The approach exploits rule exception  sets  as  the
basis  for  forming  new concepts, checks the quality of new con-
cepts, and reuses them for restructuring the rule base and future
learning.
 
*Raj Seshu (Univ. of Illinois)* showed  how the  introduction  of
new  features can overcome the ``parity problem'' that  occurs in
decision-tree induction (TDIDT)  systems  (ID3  and  successors):
they fail  to learn concepts that are defined by the n-ary parity
operation.  Seshu's system  introduces a small number  of  parity
features,  resulting in improved learning  on the parity problem,
but only at the price  of  required  ``bias''  training,  and  of
slightly  worse  performance on some other problems.  Also, there
was some  discussion in the audience as to how important the par-
ity problem is in  practice.
 
*Sharad Saxena (Univ.  of  Massachusetts  Amherst)*  addressed  a
presently  completely  open problem in representation change: how
to evaluate  a given representation.  To tackle the  problem,  he
restricted  it  to the case of  decision tree learning from exam-
ples, and proposed to  measure  representation   quality  by  the
length  of  an  approximate DNF description of the target concept
that is generated from the examples before  the  actual  learning
algorithm  is  run.   At present, computing this approximate con-
cept description is  more  expensive   than  running  the  actual
learning  algorithm  ($n^2$ vs. $n  be able to reduce the cost to
linear in the future.
 
*Craig Shaefer  (Rowland Inst. for Science)*  was  the  sole  ex-
ponent  of  another  learning  paradigm, genetic algorithms.  His
ARGOT system improves the quality of  genetic algorithm  learning
by  changing the representation employed for the  chromosomes, so
that the GA sampling is restricted to parts of the  total   solu-
tion  space.   To that end, ARGOT employs several heuristics that
either  narrow or widen the space based on the characteristics of
payoff evolution.
 
### 5. Theoretical Foundations ###
 
The field of representation change does not have a solid theoret-
ical  foundation  yet.   One  approach that is being favored by a
number of people is category theoretic models.  To introduce  the
rest of the community to this mathematical theory, one session of
the workshop was devoted to a category theory tutorial  given  by
*Paul  Benjamin  (Philips)*,  *Mike  Lowry  (Kestrel  Inst.)* and
*Robert  Zimmer (Brunel Univ.)*, who also presented a theoretical
investigation  of   Rubik's  cube  representations (Benjamin) and
some  theoretical  results  about  the   nature  of   homomorphic
representation change as defined by Korf (Lowry).

--------------------------------------------------------
Stefan Wrobel
Gesellschaft fuer Mathematik und Datenverarbeitung (GMD)
F3/XPS
Pf. 1240
D-5205 St. Augustin 1
Tel.: 02241/14-2093          E-mail: wrobel @ gmdzi.uucp
--------------------------------------------------------
************************************************************************