Gaspar van Wittel , View of Tivoli, 1700
The field of pattern recognition is a rich landscape offering large sets of tools and approaches. The traveler who enters this field for the first time may feel confused and will not find his way easily. He will be puzzled in understanding the tools that are offered to him and, after that, to find out for when they are needed. Different tools are designed for different problems, but it is not always clear from the tools themselves.
Before studying the tools in detail it may be better to start with recognizing the patterns in the problems. Here, one significant characteristics will be discussed.
We will focus on the original objects to be recognized, such as chairs, tables, pens, pictures, spoken words, a piece of text, an article in a newspaper, an amnesia used by a doctor, the set of commands given to a computer, and so on. These objects belong to different recognition problems, namely the classification of furniture, the detection of language or topic, diagnosis making or intrusion detection. These are different types of problems. One aspect that contributes to the difference between the problems is how easy an object can be modified such that its class membership remains the same.
Open classes
If we take a chair and modify it a little bit, for instance by a small scratch or a slight change of color, it still remains a chair. There is no minor change that will make it a table, a stool or any other non-chair. This seems to be true for most, if not for all real world objects. There are no small modifications by which its class will change, provided that they are sufficiently minor. This condition is significant and points us to the need of defining a distance measure. Otherwise, it would be difficult to clarify what minor is. If the distance is defined proportionally to the number of molecules that are removed, added or changed then our statement that any sufficiently minor change of a chair will produce another chair is valid.
There is a relation of this observation with the notion of open sets in topology. Under certain conditions for the distance measure there is always a finite, non-zero distance between any element in the set and any element outside the set. The border of such a set is not included in the set. In other words, there are no elements of the set on the border. An example is an open interval on the real axis. Consequently, a class of objects such as chairs can be understood as an open set if a distance measure is defined as discussed above. There is no such thing as the last chair that becomes a non-chair when we have changed one molecule. All chairs have only other chairs in their direct, small neighborhood. This is, of course, heavily related to our notion of what a chair is.
Closed classes
Are there examples of classes in pattern recognition problems that cannot be considered as open sets? Are there classes for which we can find minor modifications of an object that change the class memebrship of this object? The answer is ‘yes‘!
In applications such as medical diagnosis based on questionnaires or intruder detection in computer systems it is possible that a single change of an answer or observation, a single bit will change the class of the object. These are examples of classes that can be understood as closed sets if a distance measure is used for which a single bit of change is the smallest possible value. In these examples there exists objects on the border. In any non-zero neighborhood they have objects of another class. Such borders are comparable to the border numbers of a closed interval.
It makes a difference
The classification systems to be used for open classes versus closed classes may be entirely different. If a single bit of information matters, global procedures based on some continuous probability density model are definitely suboptimal. For such cases a carefully designed classifier that exactly follows the class border is needed. LDA, neural networks, or even support vector machines are wrong, similarly as any system in which the parameters are being continuously adapted during training.
What is needed in such a scenario is to model the class boundary exactly, at least the place where the border between classes lies. Decision trees, rule based systems or discrete probability functions are suitable in case closed classes are involved in the pattern recognition problem.
Filed under: Foundation
