1992-96 Working Papers

92/1

The typesetting language TEX [Knuth (1984)] is now available on a range of computers from mainframes to micros. It has an unequalled ability to typeset mathematical text, with its many formatting features and fonts. TEX has facilities for drawing diagrams using the packages <I>tpic</I>and PiCTEX. This paper describes a TEX preprocessor written in Pascal which allows a programmer to embed diagrams in TEX documents. These diagrams may involve straight or curved lines and labelling text. The package is provided for people who either do not have access to <I>tpic</I>or PiCTEX. Or who prefer to program in Pascal.

92/2

A computer program has been written which composes blues melodies to fit a given backing chord sequence. The program is comprised of an analysis stage followed by a synthesis stage. The analysis stage takes blues tunes and produces zero, first and second order Markov transition tables covering both pitches and rhythms. In order to capture the relationship between harmony and melody, a set of transition tables is produced for each chord in the analysed songs. The synthesis stage uses the output tables from analysis to generate new melodies; second order tables are used as much as possible, with fall back procedures, to first and zero order tables, to deal with zero frequency problems. Some constraints are encoded in the form of rules to control the placement of rhythmic patterns within measures, pitch values for long duration notes and pitch values for the start of new phrases. A listening experiment was conducted to determine how well the program captures the structure of blues melodies. Results showed that listeners were unable to reliably distinguish human from computer composed melodies.

92/3

Existing computer supported co-operative work (CSCW) systems for group communication typically require some amount of keyboard input, and this may limit their usefulness. A voice input prototype system for asynchronous (time separated transactions) group communication (AGC) with simulated conversion to text was developed and an experiment constructed to investigate if advantages over conventional keyboard input computer conferencing were possible for the information exchange task. Increases in words used and facts disclosed were higher for voice input compared to text input, which implies that voice input capability could be advantageous for future asynchronous group communication systems supporting information exchange.

92/4

The information content of each successive note in a piece of music is not an intrinsic musical property but depends on the listener's own model of a genre of music. Human listeners' models can be elicited by having them guess successive notes and assign probabilities to their guesses by gambling. Computational models can be constructed by developing a structural framework for prediction, and “training” the system by having it assimilate a corpus of sample compositions and adjust its internal probability estimates accordingly. These two modeling techniques turn out to yield remarkably similar values for the information content, or “entropy,” of the Bach chorale melodies.<P>

While previous research has concentrated on the overall information content of whole pieces of music, the present study evaluates and compares the two kinds of model in fine detail. Their predictions for two particular chorale melodies are analyzed on a note-by-note basis, and the smoothed information profiles of the chorales are examined and compared. Apart from the intrinsic interest of comparing human with computational models of music, several conclusions are drawn for the improvement of computational models.

92/5

As graduate programs in Computer Science grow and mature and undergraduate populations stabilize, an increasing proportion of our resources is being devoted to the training of researchers in the field. Many inefficiencies are evident in our graduate programs. These include undesirably long average times to thesis completion, students' poor work habits and general lack of professionalism, and the unnecessary duplication of having supervisors introduce their students individually to the basics of research. Solving these problems requires specifically targeted education to get students started in their graduate research and introduce them to the skills and tools needed to complete it efficiently and effectively.<P>

We have used two different approaches in our respective departments. One is a (half-) credit course on research skills; the other a one-week intensive non-credit “survival course” at the beginning of the year. The advantage of the former is the opportunity to cover material in depth and for students to practice their skills; the latter is much less demanding on students and is easier to fit into an existing graduate program.

92/6

Speech understanding systems (SUS's) came of age in late 1971 as a result of a five year development programme instigated by the Information Processing Technology Office of the Advanced Research Projects Agency (ARPA) of the Department of Defense in the United States. The aim of the programme was to research and develop practical man-machine communication systems. It has been argued since, that the main contribution of this project was not in the development of speech science, but in the development of artificial intelligence. That debate is beyond the scope of this paper, though no one would question the fact that the field to benefit most within artificial intelligence as a result of this programme is natural language understanding. More recent projects of a similar nature, such as projects in the United Kingdom's ALVEY programme and Europe's ESPRIT programme have added further developments to this important field.<P>

This paper presents a review of some of the natural language processing techniques used within speech understanding systems. In particular, techniques for handling syntactic, semantic and pragmatic information are discussed. They are integrated into SUS's as knowledge sources.<P>

The most common application of these systems is to provide an interface to a database. The system has to perform a dialogue with a user who is generally unknown to the system. Typical examples are train and aeroplane timetable enquiry systems, travel management systems and document retrieval systems.

92/7

Technology, in the form of personal computers, is making inroads into everyday life in every part of every nation. It is frequently assumed that this si `a good thing'. However, there is a need for the people in each cultural group in each nation to appropriate technology for themselves. Indigenous people, such as the Maori of New Zealand/Aotearoa, are in danger of losing their language because technology has a European face. Yet despite the fact that the Maori are currently experiencing a cultural renaissance, there are no commercially available products that are specifically designed for Maori-speaking people.

92/8

The apparent divergence between the research paradigms of text and image compression has led us to consider the potential for applying methods developed for one domain to the other. This paper examines the idea of “lossy” text compression, which transmits an approximation to the input text rather than the text itself. In image coding, lossy techniques have proven to yield compression factors that are vastly superior to those of the best lossless schemes, and we show that this a also the case for text. Two different methods are described here, one inspired by the use of fractals in image compression. They can be combined into an extremely effective technique that provides much better compression than the present state of the art and yet preserves a reasonable degree of match between the original and received text. The major challenge for lossy text compression is identified as the reliable evaluation of the quality of this match.

93/8

Textual image compression is a method of both lossy and lossless image compression that is particularly effective for images containing repeated sub-images, notably pages of text (Mohiuddin <I>et al.,</I>1984; Witten <I>et al.,</I>. The process comprises three main steps:

<UL>

<LI>Extracting all the characters from an image;

<LI>Building a library that contains one representative for each character class;

<LI>Compfressing the image with respect to the library.

94/11

The architecture for an optimistic, highly parallel, scalable, shared memory CPU - the WarpEngine - is described. The WarpEngine CPU allows for parallelism down to the level of single instructions and is tolerant of memory latency. Its design is based around time stamping executable instructions and all memory accesses. The TimeWarp algorithm [Jefferson 1985, 1989] is used for managing the time stamps and synchronisation. This algorithm is optimistic and requires that all computations can be rolled back. The basic functions required for implementing the control and memory system used by TimeWarp are described.<P>

The WarpEngine memory model presented to the programmer, is a single linear address space which is modified by a single thread of execution. Thus, at the software level there is no need for locks or other explicit synchronising actions when accessing the memory. The actual physical implementation, however, is multiple CPUs with their own caches and local memory with each CPU simultaneously executing multiple threads of control.<P>

Reads from memory are optimistic, that is, if there is a local copy of a memory location it is taken as the current value. However, sometimes there will be a write with an earlier time stamp in transit in the system. When it arrives it causes the original read and any dependent calculations to be re-executed.<P>

The proposed instruction set is a simple load-store scheme with a small number of op-codes and fixed width instructions. To achieve latency tolerance, instructions wait until their arguments are available and then dispatch the result to (a small number of) other instructions. The basic unit of control is a block of (up to 16) instructions. Each block, when executed, is assigned a unique time stamp and all reads and writes from within that block use that time stamp. Blocks are dispatched into the future so that multiple blocks can be simultaneously active.

94/13

Many techniques have been developed for abstracting, or “learning,” rules and relationships from diverse data sets, in the hope that machines can help in the often tedious and error-prone process of acquiring knowledge from empirical data. While these techniques are plausible, theoretically well-founded, and perform well on more or less artificial test data sets, they stand or fall on their ability to make sense of real-world data. This paper describes a project that is applying a range of learning strategies to problems in primary industry, in particular agriculture and horticulture. We briefly survey some of the more readily applicable techniques that are emerging from the machine learning research community, describe a software workbench that allows users to experiment with a variety of techniques on real-world data sets, and detail the problems encountered and solutions developed in a case study of dairy herd management in which culling rules were inferred from a medium-sized database of herd information.

94/14

Survival of the species vs survival of the individual

R. H. Barbour, K. Hopper

This paper examines the relationships between human and computing entities. It develops the biological ethical imperative towards survival into a study of the forms inherent in human beings and implied in computer systems. The theory of paradoxes is used to show that a computer system cannot in general make a self-referential decision. Based upon this philosophical analysis it is argued that human and machine forms of survival are fundamentally different. Further research into the consequences of this fundamental difference is needed to ensure the diversity necessary for human survival.

94/15

Data transformation: a semantically-based approach to function discovery

Thong H. Phan, Ian H. Witten

This paper presents the method of <I>data transformation</I>for discovering numeric functions from their examples. Based on the idea of transformations between functions, this method can be viewed as a semantic counterpart to the more common approach of formula construction used in most previous discovery systems. Advantages of the new method include a flexible implementation through the design of transformation rules, and a sound basis for rigorous mathematical analysis to characterize what can be discovered. The method has been implemented in a discovery system called “LIMUS,” which can identify a wide range of functions: rational functions, quadratic relations, and many transcendental functions, as well as those that can be transformed to rational functions by combinations of differentiation, logarithm and function inverse operations.

94/16

The architecture of an optimistic CPU: The WarpEngine

John G. Cleary, Murray Pearson, Husam Kinawi

The architecture for a shared memory CPU is described. The CPU allows for parallelism down to the level of single instructions and is tolerant of memory latency. All executable instructions and memory accesses are time stamped. The TimeWarp algorithm is used for managing synchronisation. This algorithm is optimistic and requires that all computations can be rolled back. The basic functions required for implementing the control and memory system used by TimeWarp are described. The memory model presented to the programmer is a single linear address space modified by a single thread of control. Thus, at the software level there is no need for explicit synchronising actions when accessing memory. The physical implementation, however, is multiple CPUs with their own caches and local memory with each CPU simultaneously executing multiple threads of control.

94/17

Providing integrated support for multiple development notations

John C. Grundy, John R. Venable

A new method for providing integrated support for multiple development notations (including analysis, design, and implementation) within Information Systems Engineering Environments (ISEEs) is described. This method supports both static integration of multiple notations and the implementation of dynamic support for them within an integrated ISEE. First, conceptual data models of different analysis and design notations are identified and modelled, which are then merged into an integrated conceptual data model. Second, mappings are derived from the integrated conceptual data model, which translate data changes in one notation to appropriate data changes in the other notations. Third, individual ISEEs for each notation are developed. Finally, the individual ISEEs are integrated via an integrated data dictionary based on the integrated conceptual data model and mappings. An environment supporting integrated tools for Object-Oriented Analysis and Extended Entity-Relationship diagrams is described, which has been built using this technique.

94/18

Proceedings of the First New Zealand Formal Program Development Colloquium

Steve Reeves

This volume gathers together papers presented at the first in what is planned to be a series of annual meetings which aim to bring together people within New Zealand who have an interest in the use of formal ideas to enhance program development.<P>

Throughout the World work is going on under the headings of “formal methods”, “programming foundations”, “formal software engineering”. All these names are meant to suggest the use of soundly-based, broadly mathematical ideas for improving the current methods used to develop software. There is every reason for New Zealand to be engaged in this sort of research and, of growing importance, its application.<P>

Formal methods have had a large, and growing, influence on the software industry in Europe, and lately in the U.S.A. it is being seen as important. An article in September's “Scientific American” (leading with the Denver Airport debacle) gives an excellent overview of the way in which these ideas are seen as necessary for the future of the industry. Nearer to home and more immediate are current speculations about problems with the software running New Zealand's telephone system.<P>

The papers in this collection give some idea of the sorts of areas which people are working on in the expectation that other people will be encouraged to start work or continue current work in this area. We also want the fact that this works is going on to be made known to the New Zealand computer science community at large.

95/3

We present an approach to the design of complex logic ICs, developed from four premises.<P>

First, the responsibilities of a chip's major components, and the communication between them, should be separated from the detailed implementation of their functionality. Design of this <I>abstract architecture</I>should precede definition of the detailed functionality.<I>

Secondly, graphic vocabularies are most natural for describing abstract architectures, by contrast with the conventional textual notations for describing functionality.<P>

Thirdly, such information as can be expressed naturally and completely in the idiom of the abstract architecture should be automatically translated into more complex, lower-level vocabulary.<P>

Fourthly, the notations can be integrated into a single, consistent design-capture and synthesis system.<P>

PICSIL is a preliminary implementation of a design environment using this approach. It combines an editor and a synthesis driver, allowing a design's abstract architecture to be created using a graphical notation based on Data Flow Diagrams and state machines, and its functionality to be designed using a more conventional textual hardware description language. On request, it also translates a design into appropriate input for synthesis software, and controls the operation of that software, producing CIF files suitable for fabrication.<P>

Thus computer systems become appropriate for <I>ab initio</I>design production rather than <I>post facto</I>design capture.

96/12

ATM has now been widely accepted as the leading contender for the implementation of broadband communications networks (Brinkmann, Lavrijsen, Louis, <I>et al,</I> 1995) ATM networks are no longer restricted to research laboratories, and commercial products such as switches and interfaces manufactured by well known computer and communications companies have started to appear in the market place. The main advantage seen in ATM over other broadband networking technologies such as Synchronous Transfer Mode (STM) is its ability to transmit a wide variety of traffic types, including voice, data and video efficiently and seemlessly.

96/16

Data compression is an eminently pragmatic pursuit: by removing redundancy, storage can be utilised more efficiently. Identifying redundancy also serves a less prosaic purpose-it provides cues for detecting structure, and the recognition of structure coincides with one of the goals of artificial intelligence: to make sense of the world by algorithmic means. This paper describes an algorithm that excels at both data compression and structural inference. This algorithm is implemented in a system call SEQUITUR that efficiently deals with sequences containing millions of symbols.

96/18

This document reports on an investigation conducted between November, 1995 and March, 1996 into the use of machine learning on 14 sets of data supplied by agricultural researchers in New Zealand. Our purpose here is to collect together short reports on trials with these datasets using the WEKA machine learning workbench, so that some understanding of the applicability and potential application of machine learning to simi8lar datasets may result.<P>

We gratefully acknowledge the support of the New Zealand agricultural researchers who provided their datasets to us for analysis so that we could better understand the nature and analysis requirements of the research they are undertaking, and whether machine learning techniques could contribute to other views of the phenomena they are studying. The contribution of Colleen Burrows, Stephen Garner, Kirsten Thomson, Stuart Yeates and James Littin and other members of the Machine Learning Group in performing the analyses was essential to the completion of this work.

96/19

The approach of combining theories learned from multiple batches of data provide an alternative to the common practice of learning one theory from all the available data (i.e., the data combination approach). This paper empirically examines the base-line behaviour of the theory combination approach in classification tasks. We find that theory combination can lead to better performance even if the disjoint batches of data are drawn randomly from a larger sample, and relate the relative performance of the two approaches to the learning curve of the classifier used.<P>

The practical implication of our results is that one should consider using theory combination rather than data combination, especially when multiple batches of data for the same task are readily available.<P>

Another interesting result is that we empirically show that the near-asymptotic performance of a single theory, in some classification task, can be significantly improved by combining multiple theories (of the same algorithm) if the constituent theories are substantially different and there is some regularity in the theories to be exploited by the combination method used. Comparisons with known theoretical results are also provided.

96/20

One powerful technique for supporting creativity in design is analogy: drawing similarities between seemingly unrelated objects taken from different domain. A case study is presented in which fractal images serve as a source for novel crochet lace patterns. The human designer searches a potential design space by manipulating the parameters of fractal systems, and then translates portions of fractal forms to lacework. This approach to supporting innovation in design is compared with previous work based on formal modelling of the domain with generative grammars.

96/23

Many problems encountered when applying machine learning in practice involve predicting a “class” that takes on a continuous numeric value, yet few machine learning schemes are able to do this. This paper describes a “rational reconstruction” of M5, a method developed by Quinlan (1992) for inducing trees of regression models. In order to accommodate data typically encountered in practice it is necessary to deal effectively with enumerated attributes and with missing values, and techniques devised by Breiman et al. (1984) are adapted for this purpose. The resulting system seems to outperform M5, based on the scanty published data that is available.

96/25

Identifying hierarchical structure in sequences: a linear-time algorithm

Craig G. Nevill-Manning, Ian H. Witten

This paper describes an algorithm that infers a hierarchical structure from a sequence of discrete symbols by replacing phrases which appear more than once by a grammatical rule that generates the phrase, and continuing this process recursively. The result is a hierarchical representation of the original sequence. The algorithm works by maintaining two constraints: every digram in the grammar must be unique, and every rule must be used more than once. It breaks new ground by operating incrementally. Moreover, its simple structure permits a proof that it operates in space and time that is linear in the size of the input. Our implementation can process 10,000 symbols/second and has been applied to an extensive range of sequences encountered in practice.

96/26

Dataset cataloging metadata for machine learning applications and research

Sally Jo Cunningham

As the field of machine learning (ML) matures, two types of data archives are developing: collections of benchmark data sets used to test the performance of new algorithms, and data stores to which machine learning/data mining algorithms are applied to create scientific or commercial applications. At present, the catalogs of these archives are ad hoc and not tailored to machine learning analysi8s. This paper considers the cataloging metadata required to support these two types of repositories, and discusses the organizational support necessary for archive catalog maintenance.

96/27

Timestamp representations for virtual sequences

John G. Cleary, J. A. David McWha, Murray Pearson

The problem of executing sequential programs optimistically using the Time Warp algorithm is considered. It is shown how to do this, by first mapping the sequential execution to a control tree and then assigning timestamps to each node in the tree.<P>

For such timestamps to be effective they must be finite, this implies that they must be periodically rescaled to allow old timestamps to be reused. A number of timestamp representations are described and compared on the basis of: their complexity; the frequency and cost of rescaling; and the cost of performing basic operations, including comparison and creation of new timestamps.

96/28

Teaching students to critically evaluate the quality of Internet research resources

Sally Jo Cunningham

The Internet offers a host of high-quality research material in computer science-and, unfortunately, some very low quality resources as well. As part of learning the research process, students should be taught to critically evaluate the quality of all documents that they use. This paper discusses the application of document evaluation criteria to WWW resources, and describes activities for including quality evaluation in a course on research methods.

96/29

OzCHI'96 Workshop on the Next Generation of CSCW Systems

John Grundy - Editor

This is the Proceedings of the OZCHI'96 Workshop on the Next Generation of CSCW Systems. Thanks must go to Andy Cockburn for inspiring the name of the workshop and thus giving it a (general) theme! The idea for this workshop grew out of discussions with John Venable concerning the Next Generation of CASE Tools workshop which he'd attended in 1995 and 1996. With CSCW research becoming more prominent within the CHI community in Australasia, it seemed a good opportunity to get people together at OZCHI'96 who share this interest. Focusing the workshop on next-generation CSCW system issues produced paper submissions which explored very diverse areas of CSCW, but which all share a common thread of “Where do we go from here?”, and, perhaps even more importantly “Why should be doing this?”

96/30

Reconstructing Minard's graphic with the Relational Visualisation Notation

Matthew C. Humphrey

Richly expressive information visualisations are difficult to design and rarely found. Few software tools can generate multi-dimensional visualisations at all, let alone incorporate artistic detail. The Relational Visualisation Toolkit is a new system for specifying highly expressive graphical representations of data without traditional programming. We seek to discover the accessible power of this notation-both its graphical expressiveness and its ease of use. Towards this end we have used the system to design and reconstruct Minard's visulisation of Napoleon's Russian campaign of 1812. The resulting image is very simi8lar to the original, and the design is straightforward to construct. Furthermore, the design is sufficiently general to be able to visualise Hitler's WWII defeat before Moscow.

96/31

Selecting multiway splits in decision trees

Eibe Frank, Ian H. Witten

Decision trees in which numeric attributes are split several ways are more comprehensible than the usual binary trees because attributes rarely appear more than once in any path from root to leaf. There are efficient algorithms for finding the optimal multiway split for a numeric attribute, given the number of intervals in which it is to be divided. The problem we tackle is how to choose this number in order to obtain small, accurate trees.<P>

We view each multiway decision as a model and a decision tree as a recursive structure of such models. Standard methods of choosing between competing models include resampling techniques (such as cross-validation, holdout, or bootstrap) for estimating the classification error; and minimum description length techniques. However, the recursive situation differs from the usual one, and may call for new model selection methods.<P>

This paper introduces a new criterion for model selection: a resampling estimate of the information gain. Empirical results are presented for building multiway decision trees using this new criterion, and compared with criteria adopted by previous authors. The new method generates multiway trees that are both smaller and more accurate than those produced previously, and their performance is comparable with standard binary decision trees.

96/32

Melody transcription for interactive applications

Rodger J. McNab, Lloyd A. Smith

A melody transcription system has been developed to support interactive music applications. The system accepts monophonic voice input ranging from F2 (87 HZ) to G5 (784 HZ) and tracks the frequency, displaying the result in common music notation. Notes are segmented using adaptive thresholds operating on the signal's amplitude; users are required to separate notes using a stop consonant. The frequency resolution of the system is ±4 cents. Frequencies are internally represented by their distance in cents above MIDI note 0 (8.176 Hz); this allows accurate musical pitch labeling when a note is slightly sharp or flat, and supports a simple method of dynamically adapting the system's tuning to the user's singing. The system was evaluated by transcribing 100 recorded melodies-10 tunes, each sung by 5 male and 5 female singers-comprising approximately 5000 notes. The test data was transcribed in 2.8% of recorded time. Transcription error was 11.4%, with incorrect note segmentation accounting for virtually all errors. Error rate was highly dependent on the singer, with one group of four singers having error rates ranging from 3% to 5%, error over the remaining 6 singers ranged from 11% to 23%.