Perform

(Perceptron Classifier in Inform)

Introduction ... About Machine Learning ... Machine Learning and IF
Paper about Perform

Introduction

Perform is a toolkit that allows authors/developers to use one statistical AI approach — a machine learning technique — in interactive fiction that they create. Specifically, it implements a perceptron classifier in Inform and provides code needed to train that classifier, that is, to determine the weight vector it will use. The kit contains code in Perl, Octave, and Inform. The paper about Perform goes into further detail, but, briefly the contents are a supervised learning system including:

the Inform module xclass.h (ready for your trained weight vector),
the example mfclass.h which demonstrates a particular classification that can be done,
the ready-to-compile program mltest.inf which shows the previous library in use, along with compiled versions mltest.z5 and mltest.ulx, and
Perl and Octave code which can be used to train this binary classifier, a perceptron; that is, to learn a weight vector. After a weight vector has been learned, that vector is fixed as a constant in the Inform code:
1. feature.pl is first used to convert negative and positive text files of words into features.
2. train.m or train.pl (much slower, but does not require installation of Octave or purchase of Matlab) can then used to learn the weight vector; however, this only works on linerarly separable data, so it is suggested that you use...
3. pocket.m (available in Octave/Matlab only) to do the training, as described in the comments at the beginning of xclass.h.
4. test.m or test.pl can be used to check the performance of the classifier on set of data reserved for testing.
5. rubsamp.pl is available to allow you to randomly subsample lines from a file, which is handy when you're splitting data into training and test sets.

About Machine Learning

A machine learning system essentially just one that improves its performance on some task, or class of tasks, as it gains experience. The one additional detail, as Tom Mitchell's 1997 text explains, is that a well-defined learning problem must include an objective measure of performance.

A spam filter that notes when you read and reply to messages marked as "spam", and can become better at filtering spam because it notes this, provides a good example of a machine learning system. The US Postal Service employs a system to recognize handwritten ZIP codes which is also a machine learning system. The system can distinguish between the digits 0-9 not because anyone typed in rules about which digit is which, but because it was trained on a large number of labeled examples. The difference is that the USPS system doesn't learn "on the job," but is trained and set up beforehand. The USPS system is a supervised learning system, while the spam filter that learns as you sort your email is doing unsupervised learning.

Supervised Learning

Perceptrons are simple, but often effective, systems trained using supervised learning. These classifiers are the simplest sort of neural network or "connectionist" systems, which are detailed in Christopher Bishop's 1996 book. Perceptrons are neural nets with no hidden layers; the features of the data are multiplied by weights and a classification based on whether the sum exceeds a threshold.

If provided with a set of binary vectors, labeled as positive and negative examples that are linearly separable, the simple perceptron training algorithm is guaranteed to find a separator for the data. Two-dimensional data that is linearly separable is simply data that, if plotted, could be split into positive and negative examples by a line.

The perceptron has some important limitations, as Marvin Minsky and Seymour Papert discussed in their 1969 book Perceptrons. The perceptron learning algorithm will never converge at all when given features that are not linearly separable, much less provide an approximate separator of some sort. However, there is still some separator that is optimal. Stephen Gallant's pocket algorithm (1990) provides a way to learn an optimal separator with high probability, even when the feature vectors provided are not linearly separable.

Use in Interactive Fiction

Perceptrons are binary classifiers and can be used to make a decision about any sort of data that can be expressed as a vector of binary features. For instance, a perceptron could be trained to distinguish dinosaur names from other words, to distinguish English words from other strings of text, or to distinguish whether a word has a positive or negative connotation. In IF, a perceptron could also classify the current situation based on the game state, determining, for instance, whether the interactor is currently goal-oriented and pursuing a task or not.

Perform contains a script to extract features from a word list; this can be modified so you can select different features. There is also a script to train a perceptron, using the pocket algorithm, on the features files that are generated. (An implementation of the perceptron learning algorithm is also included, although it is not likely to be very useful in practice.) Finally, an example classifier is implemented in Inform. It classifies first names as male or female. It can be used as is or modified to implement a weight vector trained on different data so as to make a different classification of words.

Unsupervised Learning

For the sake of completeness: Supervised learning systems are not the only possibilities. Reinforcement learning systems do unsupervised learning, determining a course of action based on the rewards an agent received for previous actions. Richard Sutton and Andrew Barto's 1998 book provides an excellent introduction to reinforcement learning.) A RL library for Inform would be a nice thing, although the author does not know of one. It might enable hints to be deployed on the fly in a way that seems best, given what commands the player has typed so far.

Machine Learning and IF

Why use machine learning in IF? When the use of AI in interactive fiction is discussed, the topic is often taken up with enthusiasm. When it comes to focusing on specific ideas, though, the discussion sometimes begins to sound like someone desperately, fruitlessly typing >USE AI over and over.

Artificial intelligence can almost certainly be brought to bear on tasks more important than ones conventionally imagined, such as path-finding for NPCs. At a high level, the problem of interactive fiction is to create a pleasurable experience for the interactor by providing a simulated world and generated narrative; often, this involves offering an overarching riddle that the author tries to make as complete, consistent, reactive, and appropriately challenging an experience as possible. The completeness and consistency of the world, and the overall riddle, is probably not the best task for machine learning, but such techniques seem like they could help authors make sure that IF is appropriately difficult and that it reacts well to the input of the interactor.

The idea of Perform is really not to provide ready-made "solutions" that authors can drop into their works in progress. Instead, the hope is to offer a starting point for those who want to experiment with new ways of reacting to language, or with changing behaviors of characters or the environment over time in response to interactor input. It is offered a provocation, and for those who want to probe the possibilities of IF.

Paper about Perform

License

Copyright (c) 2005 Nick Montfort

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in 
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

References

Bishop, Christopher M. Neural Networks for Pattern Recognition. Oxford University Press, 1996.
Gallant, Stephen I. "Perceptron-based Learning Algorithms." IEEE Transactions on Neural Networks 1. 2 (June 1990): 179-191.
Minsky, Marvin and Papert, Seymour. Perceptrons. The MIT Press, Cambridge, 1969.
Mitchell, Tom M. Machine Learning. McGraw-Hill, New York, 1997.
Sutton, Richard S. and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, Cambridge, 1998.

Credits

Perform is by Nick Montfort, <http://nickm.com>. It was developed as a class project for an AI seminar led by Lawrence Saul and Fernando Pereira at the University of Pennsylvania.

2005-11