Ian H. Witten


CitizenshipBritish, Canadian, and New Zealand
Family StatusMarried, two children

Qualifications

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

Employment

1991-presentProfessorDepartment of Computer Science
University of Waikato, New Zealand
1980-1991ProfessorDepartment of Computer Science
University of Calgary, Canada
1982-1985HeadDepartment of Computer Science
University of Calgary, Canada
1979-1980Senior LecturerDepartment of Electrical Engineering Science
University of Essex, England
1970-1979LecturerDepartment of Electrical Engineering Science
University of Essex, England
1969-1970Graduate AssistantDepartment of Mathematics, Statistics, and
Computer Science, University of Calgary, Canada

Visiting appointments and scholarships

1989, Jun-JulSERC Visiting FellowUniversity of Stirling, Scotland
1986, Jan-AprErskine FellowUniversity of Canterbury, New Zealand
1985, Jul-SepVisiting ProfessorTechnical University of Graz, Austria
1977, Sep-DecVisiting ConsultantBell-Northern Research, Montreal, Canada
1977, May-SepVisiting ProfessorUniversity of Calgary, Canada
1977, Jan-MayErskine FellowUniversity of Canterbury, New Zealand
1969-1970Commonwealth ScholarUniversity of Calgary, Canada
1968-1969College ScholarGonville and Caius College, Cambridge, England
1966-1968College ExhibitionerGonville and Caius College, Cambridge, England

Thesis supervision

1974Angela Corbett M.ScA telephone enquiry service using synthetic speech
1974Stephen CrockerM.ScA personal computer terminal using packet switching
1978John AbbessM.ScA microprocessor-based speech synthesis by rule system
1979Rod CuffM.ScDatabase query systems for the casual user
1980John FosterM.ScA C cross-compiler for the 8086
1980Franklin HaM.ScLow bit-rate facsimile transmission of handwriting
1981John YardleyPh.DWord identification in speech by phonetic analysis
1982Rod CuffPh.DDatabase query using menus and natural language fragments
1984Saul GreenbergM.ScUser modeling in interactive computer systems
1985Mike BonhamM.ScViewing and formatting documents on-line
1985Adrian ZissosM.ScGenerating advice by monitoring user behaviour
1985Roy MasraniM.ScConceptual analysis in Prolog
1988John DarraghM.ScAdaptive predictive text generation and the Reactive Keyboard
1988David MaulsbyM.ScInducing procedures interactively: adventures with Metamouse
1988Saul GreenbergPh.DTool use, re-use, and organization in command-driven interfaces
1989Thong PhanM.ScThe equal-value search: accelerating search in function induction
1989Dan MoM.ScLearning text editing procedures from examples
1990Darrell ConklinM.ScPrediction and entropy of music
1990Antonija MitrovicM.ScInteractive induction of procedures (in Serbo-Croat), University of Nis, Yugoslavia
(Research performed under my supervision on a World University Service Scholarship)
1992Anja HamanM.ScDeformation-based modeling
(Thesis written under my supervision, although I did not direct the research)
1992Brent KrawchukM.ScInductive theorem generation
1993Tony SmithM.ScLanguage inference from function words
1993Abdul SaheedMCMSProcessing textual images
1994David MaulsbyPh.DInstructible agents
1994Thong PhanPh.DFunction induction
1995Brent MartinM.ScInstance-based learning: nearest neighbour with generalisation
currentJamie LittinMCMSLearning relational ripple-down rules
currentMatt HumphreyD.PhilA graphical notation for the design of information visualisations
currentCraig Nevill-ManningD.PhilDetecting sequential structure
currentStuart InglisD.Phil
currentTony SmithD.PhilInference of systemic grammar based on function words and inflectional morphemes
currentYong WangM.Phil

External examining

1980John ClearyPh.DElec Eng Dept, University of Canterbury, NZ
1984Bruce MacDonaldPh.DElec Eng Dept, University of Canterbury, NZ
1986Robert BiddlePh.DComputer Science Dept, University of Canterbury, NZ
1987Tim BellPh.DComputer Science Dept, University of Canterbury, NZ
1988John KoegelPh.DComputer Science Dept, Technical Univ of Graz, Austria
1990Norma FullerPh.DComputer Science Dept, University of Regina, Canada
1991Pui-Wing WongPh.DSystems Eng Dept, University of Waterloo, Canada
1992Alison LeePh.DComputer Science Dept, University of Toronto, Canada
1992Phil NganPh.DComputer Science Dept, Massey University, New Zealand
1993Chris PhillipsPh.DComputer Science Dept, Massey University, New Zealand
1994David AndreaePh.DComputer Science Dept, Victoria University, New Zealand
1993Paul AndersonPh.DComputer Science Dept, Massey University, New Zealand

Membership in professional societies and editorial boards

FellowAssociation for Computing Machinery (ACM)
MemberAmerican 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 BoardsApplied 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

JournalsApplied 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 applicationsAustralian 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 manuscriptsAcademic Press
MacMillan
Oxford University Press
Prentice Hall
Thomas Nelson
Van Nostrand Reinhold

Seminars

Asian Institute of TechnologyThailand
Auckland UniversityNew Zealand
Birmingham UniversityEngland
Bonn UniversityGermany
Brigham Young UniversityUSA
Brighton PolytechnicEngland
British Computer SocietyEngland
Brunel UniversityEngland
Calgary UniversityCanada
California University, Santa CruzUSA
Canterbury UniversityNew Zealand
Crete UniversityGreece
Ecole Nationale Superieure de TelecommunicationsFrance
Essex UniversityEngland
IBM, HursleyEngland
IEE Southern BranchEngland
IEE LondonEngland
IEEE Southern Alberta ChapterCanada
Information Technology InstituteSingapore
Institute of Posts and TelecommunicationsChina
Keele UniversityEngland
Lincoln UniversityNew Zealand
Malaysia University at SarawakMalaysia
Massey UniversityNew Zealand
Memorial University of NewfoundlandCanada
Nanjing UniversityChina
New South Wales UniversityAustralia
Newcastle UniversityEngland
Nis UniversityYugoslavia
Open UniversityEngland
Otago UniversityNew Zealand
Prague Technical UniversityCzechoslovakia
Queen Mary CollegeEngland
Queen's UniversityCanada
Queensland UniversityAustralia
Queensland University of TechnologyAustralia
Regina UniversityCanada
Royal SocietyNew Zealand
Stanford UniversityUSA
Telekom MalaysiaMalaysia
Toronto UniversityCanada
Victoria UniversityCanada
Victoria UniversityNew Zealand
Waikato UniversityNew Zealand
Waterloo UniversityCanada
Wuhan Technical UniversityChina
York UniversityEngland

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

Research prize

1990Received 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