Ian H. Witten: Resume

Ian H. Witten

Citizenship	British, Canadian, and New Zealand
Family Status	Married, two children

Qualifications

1976	Ph.D.	University of Essex, England (Electrical Engineering Science)
1973	M.A. (unearned)	University of Cambridge, England
1970	M.Sc.	University of Calgary, Canada (Mathematics, Statistics, and Computer Science)
1969	B.A. (First Class Honours)	University of Cambridge, England (Mathematics)
1976	Chartered Engineer	Institute of Electrical Engineers, London

Employment

1991-present	Professor	Department of Computer Science University of Waikato, New Zealand
1980-1991	Professor	Department of Computer Science University of Calgary, Canada
1982-1985	Head	Department of Computer Science University of Calgary, Canada
1979-1980	Senior Lecturer	Department of Electrical Engineering Science University of Essex, England
1970-1979	Lecturer	Department of Electrical Engineering Science University of Essex, England
1969-1970	Graduate Assistant	Department of Mathematics, Statistics, and Computer Science, University of Calgary, Canada

Visiting appointments and scholarships

1989, Jun-Jul	SERC Visiting Fellow	University of Stirling, Scotland
1986, Jan-Apr	Erskine Fellow	University of Canterbury, New Zealand
1985, Jul-Sep	Visiting Professor	Technical University of Graz, Austria
1977, Sep-Dec	Visiting Consultant	Bell-Northern Research, Montreal, Canada
1977, May-Sep	Visiting Professor	University of Calgary, Canada
1977, Jan-May	Erskine Fellow	University of Canterbury, New Zealand
1969-1970	Commonwealth Scholar	University of Calgary, Canada
1968-1969	College Scholar	Gonville and Caius College, Cambridge, England
1966-1968	College Exhibitioner	Gonville and Caius College, Cambridge, England

Thesis supervision

1974	Angela Corbett	M.Sc	A telephone enquiry service using synthetic speech
1974	Stephen Crocker	M.Sc	A personal computer terminal using packet switching
1978	John Abbess	M.Sc	A microprocessor-based speech synthesis by rule system
1979	Rod Cuff	M.Sc	Database query systems for the casual user
1980	John Foster	M.Sc	A C cross-compiler for the 8086
1980	Franklin Ha	M.Sc	Low bit-rate facsimile transmission of handwriting
1981	John Yardley	Ph.D	Word identification in speech by phonetic analysis
1982	Rod Cuff	Ph.D	Database query using menus and natural language fragments
1984	Saul Greenberg	M.Sc	User modeling in interactive computer systems
1985	Mike Bonham	M.Sc	Viewing and formatting documents on-line
1985	Adrian Zissos	M.Sc	Generating advice by monitoring user behaviour
1985	Roy Masrani	M.Sc	Conceptual analysis in Prolog
1988	John Darragh	M.Sc	Adaptive predictive text generation and the Reactive Keyboard
1988	David Maulsby	M.Sc	Inducing procedures interactively: adventures with Metamouse
1988	Saul Greenberg	Ph.D	Tool use, re-use, and organization in command-driven interfaces
1989	Thong Phan	M.Sc	The equal-value search: accelerating search in function induction
1989	Dan Mo	M.Sc	Learning text editing procedures from examples
1990	Darrell Conklin	M.Sc	Prediction and entropy of music
1990	Antonija Mitrovic	M.Sc	Interactive induction of procedures (in Serbo-Croat), University of Nis, Yugoslavia
	(Research performed under my supervision on a World University Service Scholarship)
1992	Anja Haman	M.Sc	Deformation-based modeling
	(Thesis written under my supervision, although I did not direct the research)
1992	Brent Krawchuk	M.Sc	Inductive theorem generation
1993	Tony Smith	M.Sc	Language inference from function words
1993	Abdul Saheed	MCMS	Processing textual images
1994	David Maulsby	Ph.D	Instructible agents
1994	Thong Phan	Ph.D	Function induction
1995	Brent Martin	M.Sc	Instance-based learning: nearest neighbour with generalisation
current	Jamie Littin	MCMS	Learning relational ripple-down rules
current	Matt Humphrey	D.Phil	A graphical notation for the design of information visualisations
current	Craig Nevill-Manning	D.Phil	Detecting sequential structure
current	Stuart Inglis	D.Phil
current	Tony Smith	D.Phil	Inference of systemic grammar based on function words and inflectional morphemes
current	Yong Wang	M.Phil

External examining

1980	John Cleary	Ph.D	Elec Eng Dept, University of Canterbury, NZ
1984	Bruce MacDonald	Ph.D	Elec Eng Dept, University of Canterbury, NZ
1986	Robert Biddle	Ph.D	Computer Science Dept, University of Canterbury, NZ
1987	Tim Bell	Ph.D	Computer Science Dept, University of Canterbury, NZ
1988	John Koegel	Ph.D	Computer Science Dept, Technical Univ of Graz, Austria
1990	Norma Fuller	Ph.D	Computer Science Dept, University of Regina, Canada
1991	Pui-Wing Wong	Ph.D	Systems Eng Dept, University of Waterloo, Canada
1992	Alison Lee	Ph.D	Computer Science Dept, University of Toronto, Canada
1992	Phil Ngan	Ph.D	Computer Science Dept, Massey University, New Zealand
1993	Chris Phillips	Ph.D	Computer Science Dept, Massey University, New Zealand
1994	David Andreae	Ph.D	Computer Science Dept, Victoria University, New Zealand
1993	Paul Anderson	Ph.D	Computer Science Dept, Massey University, New Zealand

Membership in professional societies and editorial boards

Fellow	Association for Computing Machinery (ACM)
Member	American Society for Information Science (ASIS)
	Institute of Electrical Engineers (IEE)
	Institution of Electrical and Electronic Engineers (IEEE)
	New Zealand Computer Society (NZCS)
	Society for Artificial Intelligence and Simulation of Behaviour (AISB)
Editorial Boards	Applied Intelligence
	Encyclopedia of Computer Science
	International Journal of Human-Computer Studies
	Journal of Experimental and Theoretical Artificial Intelligence
	Journal of Universal Computer Science
	McGraw Hill International Book Series in Human-Computer Systems

Refereeing and reviewing

Journals	Applied Intelligence
	Automatica
	Communications of the ACM
	Computer Graphics International
	Computer Journal
	Computer Processing of Chinese and Oriental Languages
	Computing Reviews
	Computing Surveys
	Electronics Letters
	Future Computing Systems
	Fuzzy Sets and Systems
	IEE Journal on Communication, Speech and Vision
	IEE Journal on Computers and Digital Techniques
	IEE Journal on Software and Microsystems
	IEEE Computer
	IEEE Transactions on Acoustics, Speech and Signal Processing
	IEEE Transactions on Communications
	IEEE Transactions on Image Processing
	IEEE Transactions on Information Theory
	IEEE Transactions on Systems, Man and Cybernetics
	Information and Software Technology
	Information Processing and Management
	Information Processing Letters
	International Journal of Control and Computers
	International Journal of General Systems
	International Journal of Man-Machine Studies
	Journal of Experimental and Theoretical Artificial Intelligence
	Journal of the Acoustical Society of America
	Journal of the ACM
	Knowledge Engineering
Grant applications	Australian Research Council
	British Columbia Science Council
	Hong Kong Research Grants Council
	Israel Science Foundation
	National Science Foundation (US)
	Natural Sciences and Engineering Research Council of Canada
	New Zealand Foundation for Research, Science and Technology
	Social Sciences and Humanities Research Council of Canada
Book manuscripts	Academic Press
	MacMillan
	Oxford University Press
	Prentice Hall
	Thomas Nelson
	Van Nostrand Reinhold

Seminars

Asian Institute of Technology	Thailand
Auckland University	New Zealand
Birmingham University	England
Bonn University	Germany
Brigham Young University	USA
Brighton Polytechnic	England
British Computer Society	England
Brunel University	England
Calgary University	Canada
California University, Santa Cruz	USA
Canterbury University	New Zealand
Crete University	Greece
Ecole Nationale Superieure de Telecommunications	France
Essex University	England
IBM, Hursley	England
IEE Southern Branch	England
IEE London	England
IEEE Southern Alberta Chapter	Canada
Information Technology Institute	Singapore
Institute of Posts and Telecommunications	China
Keele University	England
Lincoln University	New Zealand
Malaysia University at Sarawak	Malaysia
Massey University	New Zealand
Memorial University of Newfoundland	Canada
Nanjing University	China
New South Wales University	Australia
Newcastle University	England
Nis University	Yugoslavia
Open University	England
Otago University	New Zealand
Prague Technical University	Czechoslovakia
Queen Mary College	England
Queen's University	Canada
Queensland University	Australia
Queensland University of Technology	Australia
Regina University	Canada
Royal Society	New Zealand
Stanford University	USA
Telekom Malaysia	Malaysia
Toronto University	Canada
Victoria University	Canada
Victoria University	New Zealand
Waikato University	New Zealand
Waterloo University	Canada
Wuhan Technical University	China
York University	England

CONTRIBUTIONS TO RESEARCH

The underlying theme of my research is the exploitation of information about a user's past behavior to expedite their interaction in the future. In pursuit of this theme I have been drawn into adaptive text compression (using information about past text to encode upcoming characters), machine learning (seeking ways to summarize, re-structure, and generalize past experience), and user modeling (characterizing user behavior). The work represents the continuation of a substantial research effort which has already borne fruit in areas as diverse as computer speech, user modeling, adaptive interfaces, documentation browsing systems, data compression, machine learning, and knowledge acquisition.

Theory of adaptive systems

This is the subject of my Ph.D. thesis (1976). It encompasses the so-called ``two-armed bandit'' problem, of which I published a major survey (Journal of the Franklin Institute, 1976), resulting in an invitation by Professor Cover, the world's leading authority in the area, to give a seminar at Stanford University (1977).

The two-armed bandit problem epitomizes the conflict between system identification and control, where the cost of exploratory activity must be balanced against the cost of poor system knowledge. In bald form, it concerns an experimenter who is given two biased coins, whose biases are unknown, and must make tosses of either coin with the promise of getting $1 for heads but nothing for tails. His dilemma is that on the basis of a finite sample he can guess which coin is favored, but he may be wrong, and to increase confidence in his guess he must choose the apparently inferior coin sometimes. Constraints of finite time, finite memory (in the sense of remembering the results of the last few tosses only), and finite state make the problem an interesting system-theoretic study, with potential application to any man-machine system which demands simultaneous exploration and control.

It also includes adaptive control systems, the study of which led to an important theoretical paper in Information and Control (1977), an invited paper in the Journal of Cybernetics and Systems Science (1977), the award of an Erskine Fellowship to study in New Zealand (1977), and an invitation to contribute to the International Conference on Mathematical Learning Models (Germany, 1982).

Speech synthesis

My contributions to this field have been diverse. I have worked on the design of speech synthesizers, for which I was consultant to the Essex Electronics Centre (1973-1974) and attracted an SRC research grant (1975-1977). My major contribution has been in the area of synthesis of prosodic features, which led to a key paper in Language and Speech (1977) and attracted another SRC grant (1979). Much of this work has proceeded in collaboration with the Phonetics Department at the University of Edinburgh, the Department of Computer Science at the University of Calgary, Bell-Northern Research at Montreal, the Polish Academy of Sciences in Poznan, and the Department of Experimental Psychology at the University of Sussex. A major research book, Principles of Computer Speech (Academic Press, 1982), contains the results of my own studies, as well as those of others. One of my papers was selected for inclusion in an IEEE Computer Society collection entitled End user facilities in the 1980's (1982).

Digital signal processing

Work on speech synthesis naturally brought me into contact with speech analysis in the form of digital processing of signals. As well as developing special-purpose architectures for speech analysis, for which I was awarded a grant from the Government Communications Headquarters (1979-1981), I have worked on novel algorithms for signal processing, with a major paper in IEEE Transactions on Circuits and Systems (1981); and on new techniques for picture display using space-filling curves (IEEE Computer Graphics and Applications, 1982).

Linear and non-linear identification techniques

My separate interests in adaptive systems and speech converge in the area of identification of time series. I have applied linear techniques to unusual problems such as the identification of curves used in handwriting. As well as contributing to the development and analysis of algorithms for non-linear behavior sequence identification (International Journal of General Systems, 1979, 1980), I have used the techniques in human-computer interfaces which predict user entries (see below). A survey of methods for modeling behavior sequences appears in Future Computer Systems (1987).

Adaptive user interfaces

Out of work on adaptive systems and behavior sequence identification sprang a strong interest in the potential of adaptation to simplify the user interface. A series of theoretical and experimental investigations demonstrated that (contrary to popular belief) interfaces can be designed to adapt automatically and successfully to the needs of individual users (reported in International Journal of Man-Machine Studies, 1984, and Behaviour and Information Technology, 1985). Out of this developed a general interest in user interface interaction styles (Oxford Surveys in Information Technology, 1985). A notable adaptive interface is the ``Reactive Keyboard,'' a device that accelerates typewritten communication with a computer system by predicting what the user is going to type next (reported in Interacting with Computers, 1991). Macintosh (reported in IEEE Computer, 1990), PC, and Unix versions have been distributed worldwide as a computer interface for disabled people, and, according to users, have dramatically altered the way they use computers. A monograph on the system (The Reactive Keyboard,\c 1992) has been published by Cambridge University Press.

Programming by example

Programming by example is the inference of programs from examples of their execution. We have created a novel system called ``Metamouse,'' a user interface agent that learns to perform editing tasks within a drawing program (reported in Computer Graphics, 1989). The user specifies a procedure by supplying an example execution trace, manipulating objects directly on the screen and creating graphical tools where necessary to help make constraints explicit. Metamouse induces the procedure, identifying key features of individual program steps and disregarding coincidental events, and uses it to predict upcoming actions and perform them for the user, thereby reducing the tedium of repetitive graphical editing. The scheme has attracted a good deal of interest, including, for example, unsolicited donations from Apple computer to further the research. We have extended the idea to repetitive text editing, and have developed a theoretical approach to evaluating programs formed by example.

Machine learning

A number of technical advances in machine learning have been made, including a new algorithm for similarity-based learning (reported in the 1988 Machine Learning conference); a simplified presentation of explanation-based learning that removes it from its rather specialized niche and places it in the context of expert systems, problem-solving, and planning (Journal of Experimental and Theoretical Artificial Intelligence, 1989); and a new scheme for accelerating search in function induction which gives several orders of magnitude performance increase over the standard search technique (Journal of Experimental and Theoretical Artificial Intelligence, 1990). Contributions have also been made towards the rapprochement of knowledge acquisition and machine learning (reported in International Journal of Man-Machine Studies, 1988, and IEEE Transactions on Systems, Man and Cybernetics, 1989).

Documentation systems

In 1980 my book Communicating with Microcomputers was published by Academic Press from camera-ready copy. During the production process I became intrigued with the manifest problems of existing document preparation systems and have developed a strong interest not only in batch document formatting languages and typography (papers in Software\(emPractice and Experience, 1982, and International Journal of Man-Machine Studies, 1985), but also in on-line document browsing and dynamic books (Communications of the Association for Computing Machinery, 1985). This interest has extended to interactive systems which select documentation or ``advice'' appropriate to each individual user's needs, based on long-term observations of their behavior, in the manner of an automated coach (International Journal of Man-Machine Studies, 1985).

Text compression

Data compression is modeling and prediction at work (see article in Abacus, 1986). In 1982/83, Dr Cleary and I discovered some fundamental results concerning adaptive modeling for data compression (published in IEEE Transactions on Information Theory, 1984), and invented a text compression method which outperforms virtually all known techniques by a large margin\(emit typically takes only 2.2 bits/character for mixed-case English modeling (IEEE Transactions on Communications, 1984). We have also published an influential study of arithmetic coding in Communications of the ACM (1987), a survey of modeling for text compression (Computing Surveys, 1989), and a major research book on adaptive text compression (Text Compression, Prentice Hall, 1990). Much of this work is with Dr Bell of the University of Canterbury, New Zealand, a former postdoctoral fellow at Calgary, with whom I have worked on models for natural language text (International Journal of Man-Machine Studies, 1990) and the zero-frequency problem (IEEE Transactions on Information Theory, 1991).

Compressed information retrieval systems and digital libraries

Our work in text compression has led to advances in compressed full-text retrieval systems. We developed new techniques for compressing a concordance (reported in the Journal of Information Science, 1991), which is an inverted index of all words in a text, and it transpired that a compressed concordance gives substantial advances over the method of signature files, which represent the previous state of the art in compressed information systems (Journal of the American Society for Information Science, 1993). Along with research on the compression of document images (Proceedings of the IEEE, 1994), this work has culminated in a major book, Managing Gigabytes: compressing and indexing documents and images. This is a substantial (430 pp.) research text, along with a public-domain software system, which is already having a major impact on the area of information retrieval systems. Current directions are in investigating the design and construction of digital libraries, with papers presented at several international Digital Libraries conferences.

Other research areas

These include a (serious, SRC-funded) project on positional play in chess (International Journal of Man-Machine Studies, 1975, 1976), which has excited considerable interest; Chinese-language computer systems, funded by Monotype International (1979); semiotics and computers; and text processing. An interesting accomplishment was the development of a hand-controlled speech toy (published in Wireless World, 1978, 1979) which attracted a large number of requests for circuit cards by would-be constructors and has been used by a developmental psychologist as a stimulus for autistic children. During 1982-1985 I was heavily involved in Jade, a large group project at Calgary which aimed to construct an environment for the development of distributed software (ACM Operating Systems Review, 1983). I took an early interest in computer viruses (see article in Abacus, 1987), and in 1989 co-invented a scheme called ``Liveware'' which enables the distribution of databases, and the maintenance of distributed databases, using the transmission technique of computer viruses (reported in International Journal of Man-Machine Studies, 1991). I have also worked on adaptively formed models for music prediction (Interface: Journal of New Music Research, 1990).

Research support

1975-1977	9,250 pounds	A programmable speech output peripheral SRC (UK Science Research Council)
1979	8,600 pounds	Synthesis of suprasegmental features using Votrax SRC
1979	3,200 pounds	Interactive computer system using the Chinese language Monotype International
1979-1981	22,200 pounds	LPC vocoder implementation UK Government Communications Headquarters
1980	37,300 pounds	Synthesis of prosodic features of speech UK Joint Speech Research Unit (awarded but not taken up because of move to Canada)
1981-1982	$ 26,000	Advanced tools for man-computer interaction NSERC (Canadian Natural Sciences and Engineering Research Council) Individual Operating Grant
1981-1982	$ 5,000	Document preparation systems University of Calgary
1982-1983	$ 37,000	Advanced tools for man-computer interaction NSERC Individual Operating grant
1982	$ 60,000	Distributed office information system research computer NSERC Equipment grant (joint application)
1982-1984	$ 304,969	A computer network for the development of distributed software NSERC Strategic Equipment grant (group application)
1982-1985	$ 146,363 pa	An environment for the development of distributed software NSERC Strategic Operating grant (group application)
1982-1985	$ 274,000	A local computing network for research in distributed environments NSERC Major Equipment grant (group application)
1982-1985	$ 31,000 pa	University of Calgary programming environment project NSERC Infrastructure grant (group application)
1983-1986	$ 50,875 pa	Advanced tools for man-computer interaction NSERC Individual Operating grant
1985-1988	$ 43,500 pa	JADE distributed programming environment NSERC Infrastructure grant (group application)
1986-1989	$ 56,000 pa	Advanced tools for human-computer interaction NSERC Individual Operating grant
1988-1991	$ 88,000 pa	JADE distributed programming environment NSERC Infrastructure grant (group application)
1989-1992	$ 83,360 pa	Advanced tools for human-computer interaction NSERC Individual Operating grant
1989	$ 53,880	KSI Research Computer Facility NSERC Equipment grant (group application)
1989	$ 30,000	Equipment to support programming-by-example research Apple Computer (unsolicited donation)
1989-1993	$ 20,000 pa	Grant to support programming-by-example research Apple Computer (unsolicited donation)
1991	$ 49,726	Computer support for real-time collaboration NSERC Equipment grant (joint application)
1991	$ 1,800	Applying information-theoretic principles to user interface design NSERC International Scientific Exchange Award
1991-1994	$ 88,000 pa	The Calgary distributed programming facility NSERC Infrastructure grant (group application)
1992-1993	$ 83,360 pa	Advanced tools for human-computer interaction NSERC Individual Operating grant
1993-1994	$ 39,000 pa	Prediction, compression, and machine learning NSERC Individual Operating grant
1993-1994	$ 40,000 pa	Development of RADEC product and paradigm FRST (New Zealand Foundation for Research Science and Technology)
1993-1994	$ 240,000	Development, integration, and application of machine learning FRST (group application)
1994-1997	$ 192,000 pa	Development, integration, and application of machine learning FRST (group application)
1995	$ 20,000 pa	NZ Digital library for computer science NZ Lottery Grants Board (group application)

Research prize

1990

Received the University of Calgary Faculty of Science Award of Excellence for ``consistently outstanding contributions in research.''

Publications in

Abacus
ACM Operating Systems Review
ACM SIGOA Newsletter
AI and Society
Behaviour and Information Technology
Byte
Canadian Artificial Intelligence
Communications of the ACM
Computer Bulletin
Computer Graphics
Computer Journal
Computer Music Journal
Computer Science Education
Computers and Security
Computing Surveys
Digital Processes
Electronics Letters
Future Computing Systems
Human-Computer Interaction
IEE Proceedings
IEE Transactions on Computers and Digital Techniques
IEE Journal on Software and Microsystems
IEEE Computer
IEEE Computer Graphics and Applications
IEEE Transactions on Circuits and Systems
IEEE Transactions on Communications
IEEE Transactions on Computers
IEEE Transactions on Information Theory
IEEE Transactions on Systems, Man and Cybernetics
Infor
Information and Control
Information Processing and Management
Interacting with Computers
Interface: Journal of New Music Research
International Journal of General Systems
International Journal of Intelligent Systems
International Journal of Man-Machine Studies
Journal of Cybernetics and Information Science
Journal of Experimental and Theoretical Artificial Intelligence
Journal of Information Science
Journal of the Acoustical Society of America
Journal of the American Society for Information Systems
Journal of the Association for Computing Machinery
Journal of the Franklin Institute
Language and Speech
Leonardo Music Journal
Literary and Linguistic Computing
Machine Learning
New Zealand Journal of Computing
Software\(emPractice and Experience
Wireless World