This appendix is a companion to Chapter 9. In particular, it discusses two case studies that illustrate the evaluation framework laid out in that chapter and whose details were discussed all throughout the book. The first case study focuses on a practical (albeit semiartificial) domain; the second uses datasets from the UCI Repository for Machine Learning. The two studies are now discussed in turn.

Illustrative Case Study 1

In this case study, we used the dataset generated by Health Canada for the 2008 ICDM Data Contest. The purpose of the data is to serve as a basis for construction of automated learning systems able to monitor the amount of a few particular xenon isotopes (radioxenon) released in the atmosphere in an effort to verify compliance of the global ban on nuclear tests (the Comprehensive Nuclear Test Ban Treaty or (CTBT). These isotopes, when released in some given pattern, are characteristic of nuclear explosions. What makes the problem difficult, however, is that the monitoring stations are typically not located at the site of the explosion. Instead, the isotopes are transported, over days or weeks, through various weather systems, toward these stations and, in the process, lose their characteristic pattern. This is further complicated by the fact that xenon isotopes in various quantities are present in the atmosphere at the sites of the monitoring stations. This is due to the release of such gases by perfectly legal civil nuclear plants such as medical isotope production facilities and nuclear power plants.

We saw in Chapters 3 and 4 the concerns that arise from having to choose appropriate performance measures. Once a performance measure is decided upon, the next obvious concern is to find a good method for testing the learning algorithm so as to obtain as unbiased an estimate of the chosen performance measure as possible. Also of interest is the related concern of whether the technique we use to obtain such an estimate brings us as close as possible to the true measure value.

Ideally we would have access to the entire population and test our classifiers on it. Even if the entire population were not available, if a lot of representative data from that population could be obtained, error estimation would be quite simple. It would consist of testing the algorithms on the data they were trained on. Although such an estimate, commonly known as the resubstitution error, is usually optimistically biased, as the number of instances in the dataset increases, it tends toward the true error rate. Realistically, however, we are given a significantly limited-sized sample of the population. Areliable alternative thus consists of testing the algorithm on a large set of unseen data points. This approach is commonly known as the holdout method. Unfortunately, such an approach still requires quite a lot of data for testing the algorithm's performance, which is relatively rare in most practical situation.

Our discussion in the last chapter focused on performance measures that relied solely on the information obtained from the confusion matrix. Consequently it did not take into consideration measures that either incorporate information in addition to that conveyed by the confusion matrix or account for classifiers that are not discrete. In this chapter, we extend our discussion to incorporate some of these measures. In particular, we focus on measures associated with scoring classifiers. A scoring classifier typically outputs a real-valued score on each instance. This real-valued score need not necessarily be the likelihood of the test instance over a class, although such probabilistic classifiers can be considered to be a special case of scoring classifiers. The scores output by the classifiers over the test instances can then be thresholded to obtain class memberships for instances (e.g., all examples with scores above the threshold are labeled as positive, whereas those with scores below it are labeled as negative). Graphical analysis methods and the associated performance measures have proven to be very effective tools in studying both the behavior and the performance of such scoring classifiers. Among these, the receiver operating characteristic (ROC) analysis has shown significant promise and hence has gained considerable popularity as a graphical measure of choice. We discuss ROC analysis in significant detail. We also discuss some alternative graphical measures that can be applied depending on the domain of application and assessment criterion of interest.

Grammatical inference is concerned with learning language representations from information, which can be text, examples and counter-examples, or anything really that should provide us insight about the elements of the language being sought. If the problem can sometimes be stated in such an informal way and there are many papers presenting heuristics and ideas allowing us to extract some grammar or automaton from all types of information, theoretical properties of convergence of the algorithms are usually desired. This therefore requires more precise definitions.

Introductory discussion

Convergence is defined by not just finding some grammar but the grammar, which means considering that the problem is about searching for a hidden grammar, i.e. one defined a priori, or at least one equivalent to this ideal one. Obviously, in practice, such a hidden grammar may not exist, but the assumption is needed to study the convergence of the algorithms.

Yet, apart from very special cases, the information the learner gets is about the language generated, recognised or represented by the grammar, not about the grammar itself.

Context-free languages correspond to the second ‘easiest’ level of the Chomsky hierarchy. They comprise the languages generated by context-free grammars (see Chapter 4).

All regular languages are context-free but the converse is not true. Among the languages that are context-free but not regular, some ‘typical’ ones are:

• {anbn: n ≥ 0}. This is the classical text book language used to show that automata cannot count in an unrestricted way.

Let us suppose we are given a sample and an automaton. By automaton we mean the structure or at least some constraints on the number of states and some restrictive syntactical conditions on the transitions we are allowed to use. We are interested in finding a systematic way of converting the automaton into a probabilistic generator such as those we studied in Chapter 5. It would also be interesting to be able to do something similar for grammars instead of automata.

Learning from text consists of inferring from a presentation of examples that all come from the target language. The learner is asked to somehow generalise from the data it sees while not having counter-examples that would help it refrain from over-generalising.

Identification in the limit from text

Learning from text is considered by many to be the essence of language learning. It is in a sense the initial problem, the one with least constraints, and the one that, once we show it cannot be solved, allows us to consider making the problem easier by adding some helpful information like negative examples, knowledge about the structure or the possibility to interrogate an Oracle.

There are several situations where the learning algorithm can actively interact with its environment. Instead of using given data, the algorithm may be able to perform tests, create new strings, and find out how far he may be from the solution. The mathematical setting to do this is called active learning, where queries are made to an Oracle.

In this chapter we cover positive and negative aspects of this important paradigm in grammatical inference, but also in machine learning, with again a special focus on the case of learning deterministic finite automata.

About learning with queries

In Section 7.5 we introduced the model of learning from queries (or active learning) in order to produce negative results (which could then also apply to situations where we have less control over the examples) and also to find new inference algorithms in a more helpful but credible learning setting.

Why learn with queries?

Active learning is a paradigm first introduced with theoretical motivations but that for a number of reasons can today be considered also as a pragmatic approach.

Strings are a very natural way to encode information: they appear directly with linguistic data (they will then be words or sentences), or with biological data. Computer scientists have for a long time organised information into tree-like data structures. It is reasonable, therefore, that trees arise in a context where the data has been preprocessed. Typical examples are the parse trees of a program or the parse trees of natural language sentences.

Graphs will appear in settings where the information is more complex: images will be encoded into graphs, and first-order logical formulae also require graphs when one wants to associate a semantic.

Grammatical inference is a task where the goal is to learn or infer a grammar (or some device that can generate, recognise or describe strings) for a language and from all sorts of information about this language.

Grammatical inference consists of finding the grammar or automaton for a language of which we are given an indirect presentation through strings, sequences, trees, terms or graphs.

As what characterises grammatical inference is at least as much the data from which we are asked to learn, as the sort of result, we turn to presenting some possible examples of data.

When ending this manuscript, the author decided that a certain number of things had been left implicit in the text, and could perhaps be written out clearly in some place where this would not affect the mathematical reading of the rest.

Let us discuss these points briefly here.

About convergence

Let us suppose, for the sake of argument, that the task we were developing algorithms for was the construction of random number generators. Suppose now that we had constructed such a generator, that given a seed s would return an endless series of numbers. Some of the questions we may be faced with might be:

1. • Is 25 more or less random than 17?

2. • Is 23 random?[…]

Learning languages requires, for the process to be of any practical value, agreement on a representation of these languages. We turn to formal language theory to provide us with such meaningful representations, and adapt these classical definitions to the particular task of grammatical inference only when needed.

Automata and finite state machines

Automata are finite state machines used to recognise strings. They correspond to a simplified and limited version of Turing machines: a string is written on the input tape, the string is then read from left to right and, at each step, the next state of the system is chosen depending only on the previous state and the letter or symbol being read. The fact that this is the only information that can be used to parse the string makes the system powerful enough to accept just a limited class of languages called regular languages. The recognition procedure can be made deterministic by allowing only one action to be possible at each step (therefore for each state and each symbol). It is usually nicer and easier to manipulate these deterministic machines (called deterministic finite automata) because parsing is then performed in a much more convenient and economic way, and also because a number of theoretical results only apply to these.