Workshop on data structures processing

[Ah Chung Tsoi]

-- 
Ah Chung Tsoi                 Phone: +61 2 42 21 38 43
Dean                            Fax: +61 2 42 21 48 43
Faculty of Informatics        email: ah_chung_tsoi at uow.edu.au
University of Wollongong
Northfields Avenue
Wollongong NSW 2522
AUSTRALIA
-------------- next part --------------
Adaptive Processing of Structures

A Joint Australian and Italy Workshop

Friday, 7th August, 1998
Faculty of Informatics
University of Wollongong
Northfields Avenue
Wollongong
New South Wales
Australia

Many practical problems can be more conveniently modelled using
data structures, e.g., lists, trees. For example, in image understanding,
it is more conveniently to model the relationship among the objects in
the image by a tree structure. Similarly, for document understanding,
again it is more convenient to model various segments of the document 
using data structures. As another example, in Chemistry, often the structure
of molecules are easily expressed in terms of a tree depicting their 
structures. 

In these applications, there are a number of practical problems which 
need to be solved, viz., if there are many data structures describing the 
problem, is it possible

1. To classify an unknown structure as whether it is similar to any of the
previous data structure in the known set
2. To predict what the data structure may be.

For example, in an autonomous robot navigation problem, if the robot is
not endowed with a map of the environment, but instead rely on past traverse
of the environment to identify landmarks. One question is: how does the robot
know whether it has been visiting the same place before. Such a problem can be
formulated as a classification of the tree structures describing the past
experience in traversing the environment, i.e., in finding if the new tree
structure describing a particular experience has occurred before.

There are a number of methods in processing this type of classification problem.
For example, one may use syntactical pattern recognition to model the structure,
and to classify an unknown structure accordingly. Recently, there has been
a substantial amount of work done in using neural networks to model data
structures.

Neural networks have been used in modelling data structure. For example,
Jordan Pollock has applied a special case of a multilayer perceptron to
model data structures, commonly known as an auto--associator, or RAAM. 
In this, he used a multilayer perceptron with the same input and output 
variables, and the dimension of the hidden layer is smaller than the input. 
It is known that this MLP structure can form internal representation in the
hidden layer of the input variables. Pollock developed the RAAM
model for encoding tree structures with
labels on the leaves but this model cannot handle labels on the internal nodes.
This approach was extended to handle any labeled graphs by Alessandro
Sperduti.  Both RAAM and LRAAM can encode structures by using
a fixed size architecture, however they do not classify them. 

More recently, a number of groups have proposed the idea of using a
recursive neuron to model the data structures, e.g., by Alessandro
Sperduti and Antonina Starita (IEEE Transaction on Neural Networks, 1997),
Christoph Goller and Andreas Kuechler. These work allow us to tackle problems
in classifications and regression of structured objects, e.g., directed 
ordered acyclic graphs (DOAGs). 

In this workshop, we wish to introduce the audience to this exciting new
development, as it promises to be one of the major breakthroughs in the
representation of data structures, as well as in processing them. It can
be applied to wherever data structure is a convenient method for 
representing the underlying problem. These include, apart from molecular
chemistry, robot navigation, document processing, image processing, many
areas, e.g., internet user behaviour modelling, natural language processing.

This workshop will be given by the originators and developers of this 
approach, viz., Alessandro Sperduti, Marco Gori, Paolo Frasconi. There is
a group working on this problem in the Faculty of Informatics,
the University of Wollongong supported by an Australian Research Council
large grant. The visit of Alessandro Sperduti, and Marco Gori are supported
by an out-of-cycle large grant. The intention is to introduce Australian 
researchers to this exciting new methods, and to promote the application
of such techniques to a much wider setting.

The program of the workshop will be as follows:

9:30 - 9:45 Introduction Ah Chung Tsoi
9:45 - 10:45 Adaptive data structure modelling problems Alessandro Sperduti
10:45 - 11:15 Coffee break
11:15 - 12:15 General theory of data modelling by adaptive data structure methods Paolo Frasconi
12:15 - 1:15 Lunch
1:15 - 2:15 Properties of adaptive data structure modelling Marco Gori
2:15 - 3:15 Applications of adaptive data structure methods Alessandro Sperduti
3:15 - 3:45 Coffee break
3:45 - 5:00 Forum discussion Ah Chung Tsoi

As this is supported by an Australian Research Council grant, there will
be no registration fee for attending the workshop. However, attendants are
responsible for their own lunch. Intended participants are encouraged to
indicate their intention by emailing Professor Ah Chung Tsoi,
ahchung at uow.edu.au for morning and afternoon coffee/tea 
catering purposes.