In the last few years there have been very significant developments in the theoretical understanding of Support Vector Machines (SVMs) as well as algorithmic strategies for implementing them, and applications of the approach to practical problems. We believe that the topic has reached the point at which it should perhaps be viewed as its own subfield of machine learning, a subfield which promises much in both theoretical insights and practical usefulness. Despite reaching this stage of development, we were aware that no organic integrated introduction to the subject had yet been attempted. Presenting a comprehensive introduction to SVMs requires the synthesis of a surprisingly wide range of material, including dual representations, feature spaces, learning theory, optimisation theory, and algorithmics. Though active research is still being pursued in all of these areas, there are stable foundations in each that together form the basis for the SVM concept. By building from those stable foundations, this book attempts a measured and accessible introduction to the subject of Support Vector Machines.

The book is intended for machine learning students and practitioners who want a gentle but rigorous introduction to this new class of learning systems. It is organised as a textbook that can be used either as a central text for a course on SVMs, or as an additional text in a neural networks, machine learning, or pattern recognition class.

In this chapter I will introduce two new important ideas. The first is poly-morphism, the ability to consider entire families of types as one. Polymorphic data types are one source of this concept, which is then inherited by functions defined over these data types. The already familiar list is the most common example of a polymorphic data type, and it will be discussed at length in this chapter.

The second concept is the higher-order function, which is a function that can take one or more functions as arguments or return a function as a result (functions can also be placed in data structures, making the data constructors higher-order too). Together, polymorphic and higherorder functions substantially increase our expressive power and our ability to reuse code. You will see that both of these new ideas naturally follow the foundations that we have already built. (A more detailed discussion of polymorphic functions that operate on lists can be found in Chapter 23.)

Polymorphic Types

In previous chapters we have seen examples of lists of many different kinds of elements integers, floating-point numbers, points, characters, and even 10 actions. You can well imagine situations requiring lists of other element types as well. Sometimes, however, we don't wish to be so particular about the precise type of the elements. For example, suppose we want to define a function length, which determines the number of elements in a list. We don't really care whether the list contains integers, characters, or even other lists. We imagine computing the length in exactly the same way in each case. The obvious definition is:

This definition is self-explanatory. We can read the equations as saying: “The length of the empty list is 0, and the length of a list whose first element is x and remainder is xs, is 1 plus the length of x.s”

But what should the type of length be? Intuitively, what we'd like to say is that, for any type a, the type of length is [a] → Integer.

In this chapter I will use ideas developed in the last chapter to extend the functionality of geometric shapes defined in Chapter 2. In particular, we will consider the problem of combining shapes into larger, possibly overlapping, regions. We will not be interested in computing the area or perimeter of these regions (no easy task, by the way, with the shapes allowed to overlap in arbitrary ways), but rather we will want to know whether a particular point lies within a region. Regions are thus located on a two-dimensional (i.e., Cartesian) plane.

The functionality that we develop will be encapsulated in a module called Region:

Note that this module imports the Shape module, and exports a data type called Region, functions containsS and containsR, and the entire Shape module.

The Region Data Type

Our first task will be to define a data type that captures the various kinds of regions that interest us:

We have so far only scratched the surface of the many kinds of useful data types that can be created in Haskell In this chapter I will introduce the use of recursive and tree-shaped data types. In the process we will look at a few motivating examples of trees, but will use them more concretely in the next chapter when we create a data type of geometric regions.

A Tree Data Type

In Chapter 2 we defined a data type called Shape:

Note that every value created of this type has the same relative size, except that the list of vertices in a polygon can be arbitrarily long. In fact, lists are an example of a data type whose elements can be of any size, from [ ] to a conceptually infinite list. Lists are built-in to the Haskell language, but if they weren't, we could easily define a data type that would behave in the same way:

There are two things different about this data type from ones we've defined earlier. First, it is polymorphic. This is indicated by the fact that the name of the type, List, takes a type as an argument. In other words, the principal types of the constructors are:

which are in direct correspondence with the types of Haskell's built-in list constructors:

The second important aspect of the List data type definition is that it is recursive. That is, the type List a is defined in terms of List a. This recursive structure is what allows lists to be arbitrarily long (or even infinite), just as a recursive function may be called an arbitrary number of times (or even loop forever).

In this chapter I will introduce a powerful proof technique based on mathematical induction. With it we will be able to prove complex and important properties of programs that cannot be accomplished with proof-by-calculation alone. The inductive proof method is one of the most powerful and common methods for proving program properties.

Induction and Recursion

Induction is very closely related to recursion. In fact, in certain contexts the terms are used interchangeably; in others, one is preferred over the other primarily for historical reasons. I like to think of them as being duals of each other: Induction is used to describe things starting with something very simple, and building up from there, whereas recursion describes the whole thing first, working backward to the simple case.

For example, although I have previously used the phrase recursive data type, in fact data types are often described inductively, such as a list:

On the other hand, we usually describe functions that manipulate lists, such as map and foldr, as being recursive. This is because when you apply a function such as map, you apply it initially to the whole list, and work backwards toward [ ]. But these differences between induction and recursion run no deeper: They are really just two sides of the same coin.

This chapter is about inductive properties of programs (but based on the above argument could just as rightly be called recursive properties) that are not usually proven via calculation alone. Proving inductive properties usually involves the inductive nature of data types and the recursive nature of functions defined on the data types.

As an example, suppose that P Is an inductixe property of a list. In other words, P(l) for some list l is either true or false (no middle ground here!), To prove this property inductively, we do so based un the length of the list: Starting with length 0, we first prove P([]), (using our standard method of proof-by-calculation).

In Chapter 2 a shape data type and a function for computing the area of shapes were defined. In the last chapter you learned about basic graphics programming in Haskell. In this chapter I will define another function of shapes, namely one that converts a shape into a graphics value that can then be drawn in a graphics window. Conceptually, this function is no different from the area function defined in Chapter 2. In both cases, a shape is turned into some other kind of value; in the case of area, that value has type Float, and in the case of the function to be defined in this chapter, that value has type Graphic.

In order to perform graphics IO, we need to import the graphics library, as discussed in the last chapter. Additionally, we need to import the Shape module. Calling our new module Draw, we therefore write:

where the list of names contains those functions and values, inchToPixel, pixelToInch, etc., that we choose to export from the module, and that are defined in the remainder of this chapter.

Dealing With Different Coordinate Systems

Before proceeding, let's define a couple of coercion functions that we will use to convert, or “coerce,” the coordinates of a graphics window into ones that we are more familiar with (and vice versa).

In our discussions of shapes, we have always assumed floating-point numbers for all dimensions, presumably in inches or some similar dimensional units. But the Graphics Library uses pixel coordinates, so first we need a function to convert from the former to the latter. Let's assume that the floating-point numbers are in inches, and that there are 100 pixels per inch. Thus, to convert from inches to pixel coordinates, we can apply the following function:

In Chapter 13 you learned how to progam dynamic, graphical animations in a highly abstract, declarative manner. But there is one thing missing: reactivity. That is, the ability of our animations to react to user input or other external stimuli. In Chapter 10 you learned how user input could alter a graphics image, so at first blush, doing so for animations would seem to be just as easy. The problem is, we have lifted our thought processes and programming style to a level where we are manipulating continuous, never-ending animations, and the notion of a discrete event, such as a mouse press, does not fit in so well. For example, try to write a program, at the level of Behaviors, for a simple ball that changes color from red to blue when the mouse is pressed. I think that you will find this to be quite difficult.

In solving this problem I will borrow some ideas from a (nonstandard) Haskell library called Fran, which is short for functional reactive animation. Fran, and the version of it that we will develop in this chapter, are examples of domain specific languages, or DSLs. A DSL is a language that is designed for a specific application domain, in this case reactive animations. Haskell is an excellent vehicle for directly implementing DSLs without having to create a new language from scratch. In this way we say that the DSL is embedded in Haskell, or that Haskell is the host language for the DSL. To distinguish our language from Fran, I will call it FAL, for functional animation language.

I will begin by describing FAL by example. I will then describe a partial implementation of FAL based on streams which, because of its simplicity, can also serve as its specification. Once this foundation is established, I will describe various extensions to FAL, culminating in a final example, a twenty-line program to play the game of paddleball.

In Chapter 3 you learned enough about IO programming in Haskell to handle the graphics tasks encountered in Chapters 4, 10, and 13. In this chapter we will take a closer look at IO programming in Haskell, including more examples of file operations, and several new ideas: file handles, exceptions, channels, and concurrency. Then in the next chapter I will show how these ideas can be put to use in defining the reactimate function introduced in Chapter 15 for rendering reactive animations.

The Standard Prelude contains the most basic IO commands, with more advanced ones found in the IO Library, the SOEGraphics Library that we have already seen, and several others. The IO Library contains quite a few useful operations for file manipulation. Rather than trying to remember which is in the Standard Prelude and which is in the IO Library, it's easier to always import the library if you are doing anything beyond the most basic 10 tasks.

Files, Channels, and Handles

The first new idea is the concept of a handle to a file. A file handle is not unlike the Window value returned from the openWindow command, where several windows maybe opened simultaneously, using the Window value to specify in which window subsequent actions are to take place. File handles work the same way. There may be more than one file that is open at the same time, and thus we need a way to distinguish among them.

To obtain a handle (of type Handle) to a file there is an operation for opening the file for use in subsequent IO operations. There is also an operation for closing a file via reference to its handle.

MIDI is shorthand for “Musical Instrument Digital Interface,” and is a standard protocol for describing electronic music. In this chapter I will describe how to convert an abstract performance as defined in Chapter 21 into a MIDI file that can be played on any modern PC with a standard sound card.

As mentioned in Chapter 20, Haskore is a library for computer music that is more extensive than MDL, and I will borrow much of the basic MIDI data types defined there, as well as the low-level function outputMidiFile, to be described later.

An Introduction to MIDI

MIDI is a standard adopted by most, if not all, manufacturers of electronic instruments. At its core Is a protocol for communicating musical events (such as note on, note off, key press, pedal press) as well as socalled meta events (such as select synthesizer patch, change volume). Beyond the logical protocol, the MIDI standard also specifies electrical signal characteristics and cabling details. In addition, it specifies what is known as a Standard MIDI File, which any MIDI-compatible software package should be able to recognize.

Over the years musicians and manufacturers decided that they also wanted a standard way to refer to common or general instruments such as “acoustic grand piano,” “electric piano,” “Violin,” and “acoustic bass,” as well as more exotic ones such as “chorus aahs,” “voice oohs,” “bird tweet,” and “helicopter.” A simple standard known as General MIDI was developed to fill this role, It is nothing more than an agreed-upon list of instrument names along with a program patch number for each, a parameter in the MIDI standard that is used to select a MIDI instrument's sound. The constructor names in the IName data type (see Fig. 20.1. In Chapter 20) come directly from this standard.

The functional animation language FAL was defined in Chapter 15. In this chapter we will explore a method to render FAL programs in a graphics window. The fundamental challenge will be interfacing FAL, arguably the most abstract programming style introduced in this textbook, to the relatively low-level interface to graphics windows provided by the Graphics Library.

Preliminaries

Analogous to the function animate in Chapter 13, our goal is to define a function, which I will call reactimate, having type:

Before doing this, however, there is an important secondary task to be carried out. We need a mechanism to extract a stream of time-stamped user actions (lifted into the Maybe data type) from the operating system. We want the stream of user actions to be infinite, and return Just ua if there is a user action ua present at the time we ask for it, and Nothing if there is not. The problem is the phrase “at the time we ask for it.” How can we make a stream dependent on the execution time of a program? Surely we will need to go through the IO monad to achieve this dependency, and, in fact, I will use the Channel abstraction discussed in Chapter 16 to do so. For now, however, let's assume that we have a function:

which behaves as follows. Executing the command:

in a particular window environment yields a user action stream us and time stream ts. In addition, it yields an IO action addEvents that causes the operating system to update us with whatever user actions happen to be pending at that time, followed by a Nothing to indicate that there are no more user actions pending.

The first high-level languages developed for general purpose programming were Fortran (Backus, 1978) and Lisp (McCarthy, 1978), developed in the late 1950s by John Backus and John McCarthy, respectively. From Fortran grew many of today's modern imperative languages, most of which did not improve significantly on the fundamental ideas found in the language Algol (de Morgan, Hill and Wichmann, 1976), which shortly followed Fortran. The Lisp family was less fecund, perhaps because it was so far ahead of its time, but was the seed for the family of functional languages about which this textbook was written. The most radical in this class of languages is probably Haskell, originally designed in the late 1980s (Hudak, Wadler, 1988) based on, at that point, a good ten years of experience designing and implementing similar languages, most notably a series of languages developed by David Turner in the late 1970s and early 1980s (Turner, 1976; 1985). Although research continues on the design of Haskell, the version used in this textbook, Haskell 98 (Augustsson, et al., 1999), is the latest and most stable version of the language and its libraries.

Haskell was named after the logician Haskell B. Curry who, along with Alonzo Church, established the theoretical foundations of functional programming back when computers themselves were only a gleam in researchers' eyes. A curious historical fact is that Haskell Curry's father, Samuel Silas Curry, helped to found and direct a school in Boston called the School of Expression. Because pure functional programming centers around the notion of an expression, I thought that The Haskell School of Expression would be a good title for this book.

A Brief Account of Language Success Stories

It's hard to predict just how it is that a language becomes popular. Fortran became popular because it was the first high-level language and a welcome alternative to assembly language, and ultimately because it was a good vehicle for coding numerical algorithms in the domain of scientific computing.

In this chapter I will describe a module for expressing musical structures in the same high-level, declarative style of functional programming that we have been using for graphics, animation, and other applications. These musical structures consist of primitive entities (such as notes and rests), operations to transform musical structures (such as transpose and tempo-scaling), and operations to combine musical structures to form more complex ones (such as concurrent and sequential composition). From these simple roots, much richer musical ideas can be easily developed.

For convenience, and in the style of Chapters 15 and 19 (where I defined the languages FAL and IRL, respectively), I will refer to the ideas described in this chapter as MDL, for music description language. MDL is a simplified version of a more complete computer music library called Haskore. In Chapter 21a module will be developed for interpreting an MDL program as an abstract performance, and in Chapter 22 these performances will be converted into MIDI files, which are a standard way of interchanging electronic music and can be played on any PC with a standard sound card.

The Musk Data Type

I will assume that you are familiar with very basic musical concepts such as notes, rests, scales, and chords. Nothing more will be needed to understand what is going on, but of course the richer your musical background, the more applications of the ideas will be apparent to you.