Concur: a Newton machine learning application

Larry Bugbee


This is the final report for Concur, a development project completed by Larry Bugbee as partial fulfillment of the requirements for the degree of Master of Science in Computer Science.

Concur is an experimental machine learning application to assist Newton users in the scheduling of meetings. It uses case-based reasoning to learn the user's meeting scheduling preferences and acts on behalf of the user when confidence in the recommendation is high. Concur operates in a low-power real-time environment and strives for a minimum of verbal negotation between the parties influencing many design decisions. A procedure to assist designers in the choice of case base indices and a simple scheme to overcome the pitfalls of poorly chosen indices are proposed.

Committee:
   Dr. J. C. Schlimmer (Chair)
   Dr. D. J. Lynch
   Dr. C. S. Raghavendra

Washington State University, Tri-cities Campus

May 5, 1995



Table of Contents

Introduction
  An Overview of Concur
  Development and Runtime Environments

Key Technologies
  Newton Technology
  Machine Learning
  Case-based Reasoner Indexing Concepts

Implementation Concepts
  Concur's Features
  IR Connection mode arbitration
  Calculation of Mutually Agreeable Meeting Times
  Case-based Reasoner and Choice of Indices

Implementation Details
  Summary of User Procedures
  Program Description
  Coding Strategy

Observations

Conclusions

References

Appendices
  User Instructions
  Sources

Download a compiled version of Concur (a 35K zipped .pkg file). Install on two Newtons.




 



"The best way to predict the future is to invent it."

-- Alan Kay


Introduction

Computers and software have made significant advances over the years. Computing power that used to require whole buildings to house now resides on desktops and in briefcases. Computers are faster, smaller, cheaper and increasingly more capable. Their software has increased in functionality, complexity and sophistication. Today's technology even permits significant capabilities to be operated from the palm of the hand.

One such device is the Apple MessagePad. It is a one pound, programmable, pen-based, handheld computer that recognizes cursive handwriting and sells for about $600. Its advanced Newton technology supports pen-based input, a preemptive, multi-tasking operating system and numerous communication options for applications programmed with an object-oriented dynamic language. This makes the MessagePad arguably the lowest cost AI engine commercially available.

This is the final report for Concur, an experimental program to enhance the capabilities of the Apple MessagePad by assisting the user in the scheduling of meetings. The program learns the user's scheduling preferences using case-based machine learning technology to present schedule options most likely acceptable to the user.

The goal of this project is to experiment with an implementation of machine learning in a portable, real-time environment with a minimum of verbal negotiation between the parties. This required the use of low power devices which, in turn, mandated the use of frugal algorithms, the judicious use of pre-calculated variables, static programming and machine learning. Besides providing a cost-effective platform for this exercise, the use of Newton technology afforded an opportunity to learn a new and significantly different development environment.


An Overview of Concur

Concur makes use of peer-to-peer communications protocols, infrared (IR) communications and case-based reasoning to allow two MessagePad, or Newton, users to arrive at a mutually convenient meeting time without having to go through the process of verbal negotiation. Concur only requires that one or both of the users decide for how long they want to meet, approximately when and then aim their Newtons at each other tapping a single connect button. Figure 1 illustrates the primary human interface view.

Figure 1. Concur's Human Interface

Concur calculates valid meeting times, beams them to the other MessagePad using infrared communications and presents a valid meeting time to the user. If the user does not accept the proposed time, a new one is calculated, communicated and presented. This process continues until both users concur at which time the meeting will be automatically added to each MessagePad's calendar ready for use by the built-in Dates application.

Through this process of accepting and rejecting proposed times, Concur's case-based reasoner learns the preferences of its user and eventually has the confidence to act on the user's behalf. This is, of course, at the user's discretion.

Concur uses case-based reasoning as its machine learning component. This application of CBR technology relies heavily on a weighted nearest neighbor calculation and an indexing scheme to reduce the time to find the best exemplar.


Concur's Development and Runtime Environments

Concur is written in NewtonScript, an object-oriented dynamic language. The development environment is the Newton Tool Kit (NTK) version 1.0.1 running on a Macintosh IIci under System 7.1. The NTK compiles programs to packages on the Macintosh which are subsequently downloaded to two MessagePad 100s for testing. Packages are downloaded by either the NTK or the Newton Connection Kit (NCK) using a serial or network connection to a tethered MessagePad.

The runtime environment is, of course, on an Apple MessagePad. The application has been compiled to byte code and is interpreted. While byte codes are smaller than native codes, they are interpreted and are, therefore, slower. So long as there is sufficient speed, the Apple designers sought to conserve memory requirements.

Continue


Original paper: Copyright 1995 by Larry Bugbee
This HTML rendering: Copyright 1997 by Larry Bugbee
All rights reserved.