3.1.1 Uniform Cost Function and Minimum Error Rate

A uniform cost function is obtained if a unit cost is assumed when an object is misclassified and zero cost when the classification is correct. This can be written as

(3.9)

where δ(i, k) is the Kronecker delta function. With this cost function the conditional risk given in Equation (3.4) simplifies to

(3.10)

Minimization of this risk is equivalent to maximization of the posterior probability . Therefore, with a uniform cost function, the Bayes decision function (3.8) becomes the maximum a posteriori probability classifier (MAP classifier):

(3.11)

Application of Bayes’ theorem for conditional probabilities and cancellation of irrelevant terms yield a classification equivalent to a MAP classification but fully in terms of the prior probabilities and the conditional probability densities:

(3.12)

The functional structure of this decision function is given in Figure 3.6.

Suppose that a class is assigned to an object with measurement vector z. The probability of having a correct classification is . Consequently, the probability of having a classification error is . For an arbitrary decision function , the conditional error probability is

(3.13)

This is the probability of an erroneous classification of an object whose measurement is z. The error probability averaged over all objects can be found by averaging e(z) over all the possible measurement vectors:

(3.14)

The integral extends over the entire measurement space. E is called the error rate and is often used as a performance measure of a classifier.

The classifier that yields the minimum error rate among all other classifiers is called the minimum error rate classifier. With a uniform cost function, the risk and the error rate are equal. Therefore, the minimum error rate classifier is a Bayes classifier with a uniform cost function. With our earlier definition of MAP classification we come to the following conclusion:

The conditional error probability of a MAP classifier is found by substitution of Equation (3.11) in (3.13):

(3.15)

The minimum error rate E_min follows from Equation (3.14):

(3.16)

Of course, phrases like ‘minimum’ and ‘optimal’ are strictly tied to the given sensory system. The performance of an optimal classification with a given sensory system may be less than the performance of a non-optimal classification with another sensory system.

Example 3.5 MAP classifier for the mechanical parts application Figure 3.5(c) shows the decision function of the MAP classifier. The error rate for this classifier is 4.8%, whereas the one of the Bayes classifier in Figure 3.5(a) is 5.3%. In Figure 3.5(c) four objects are misclassified. In Figure 3.5(a) that number is five. Thus, with respect to the error rate, the MAP classifier is more effective compared with the Bayes classifier of Figure 3.5(a). On the other hand, the overall risk of the classifier shown in Figure 3.5(c) and with the cost function given in Table 3.2 as −$0.084, this is a slight impairment compared with the –$0.092 of Figure 3.5(a).

3.1.2 Normal Distributed Measurements; Linear and Quadratic Classifiers

A further development of Bayes’ classification with the uniform cost function requires the specification of the conditional probability densities. This section discusses the case in which these densities are modelled as normal. Suppose that the measurement vectors coming from an object with class ω_k are normally distributed with expectation vector µ_k and covariance matrix C_k (see Appendix C.3):

(3.17)

where N is the dimension of the measurement vector.

Substitution of Equation (3.17) in (3.12) gives the following minimum error rate classification:

(3.18)

We can take the logarithm of the function between braces without changing the result of the argmax{} function. Furthermore, all terms not containing k are irrelevant. Therefore Equation (3.18) is equivalent to

(3.19)

Hence, the expression of a minimum error rate classification with normally distributed measurement vectors takes the form of

(3.20)

where

(3.21)

A classifier according to Equation (3.20) is called a quadratic classifier and the decision function is a quadratic decision function. The boundaries between the compartments of such a decision function are pieces of quadratic hypersurfaces in the N-dimensional space. To see this, it suffices to examine the boundary between the compartments of two different classes, for example ω_i and ω_j. According to Equation (3.20) the boundary between the compartments of these two classes must satisfy the following equation:

(3.22)

or

(3.23)

Equation (3.23) is quadratic in z. In the case where the sensory system has only two sensors, that is N = 2, then the solution of (3.23) is a quadratic curve in the measurement space (an ellipse, a parabola, a hyperbola or a degenerated case: a circle, a straight line or a pair of lines). Examples will follow in subsequent sections. If we have three sensors, N = 3, then the solution of (3.23) is a quadratic surface (ellipsoid, paraboloid, hyperboloid, etc.). If N > 3, the solutions are hyperquadrics (hyperellipsoids, etc.).

If the number of classes is more than two, K > 2, then (3.23) is a necessary condition for the boundaries between compartments, but not a sufficient one. This is because the boundary between two classes may be intersected by a compartment of a third class. Thus, only pieces of the surfaces found by (3.23) are part of the boundary. The pieces of the surface that are part of the boundary are called decision boundaries. The assignment of a class to a vector exactly on the decision boundary is ambiguous. The class assigned to such a vector can be arbitrarily selected from the classes involved.

As an example we consider the classifications shown in Figure 3.5. In fact, the probability densities shown in Figure 3.4(b) are normal. Therefore, the decision boundaries shown in Figure 3.5 must be quadratic curves.

3.1.2.1 Class-Independent Covariance Matrices

In this subsection, we discuss the case in which the covariance matrices do not depend on the classes, that is C_k = C for all ω_k ∈ Ω. This situation occurs when the measurement vector of an object equals the (class-dependent) expectation vector corrupted by sensor noise, that is . The noise n is assumed to be class-independent with covariance matrix C. Hence, the class information is brought forth by the expectation vectors only.

The quadratic decision function of Equation (3.19) degenerates into

(3.24)

Since the covariance matrix C is self-adjoining and positive definite (Appendix B.5) the quantity can be regarded as a distance measure between the vector z and the expectation vector µ_k. The measure is called the squared Mahalanobis distance. The function of Equation (3.24) decides for the class whose expectation vector is nearest to the observed measurement vector (with a correction factor − 2ln P(ω_k) to account for prior knowledge). Hence, the name minimum Mahalonobis distance classifier.

The decision boundaries between compartments in the measurement space are linear (hyper) planes. This follows from Equations (3.20) and (3.21):

(3.25)

where

(3.26)

A decision function that has the form of Equation (3.25) is linear. The corresponding classifier is called a linear classifier. The equations of the decision boundaries are w_i − w_j + z^T (w_i − w_j) = 0.

Figure 3.7 gives an example of a four-class problem (K = 4) in a two-dimensional measurement space (N = 2). A scatter diagram with the contour plots of the conditional probability densities are given (Figure 3.7(a)), together with the compartments of the minimum Mahalanobis distance classifier (Figure 3.7(b)). These figures were generated by the code in Listing 3.3.

Listing 3.3 PRTools code for minimum Mahalanobis distance classification

mus = [0.2 0.3; 0.35 0.75; 0.65 0.55; 0.8 0.25];
C = [0.018 0.007; 0.007 0.011];<b></b> z<b></b> = gauss(200,mus,C);
w = ldc(z); % Normal densities, identical covariances
figure(1); scatterd(z); hold on; plotm(w);
figure(2); scatterd(z); hold on; plotc(w);

3.1.2.2 Minimum Distance Classification

A further simplification is possible when the measurement vector equals the class-dependent vector corrupted by class-independent white noise with covariance matrix C = σ²I:

(3.27)

The quantity is the normal (Euclidean) distance bet-ween z and . The classifier corresponding to Equation (3.27) decides for the class whose expectation vector is nearest to the observed measurement vector (with a correction factor − 2σ²log P(ω_k) to account for the prior knowledge). Hence, the name minimum distance classifier. As with the minimum Mahalanobis distance classifier, the decision boundaries between compartments are linear (hyper) planes. The plane separating the compartments of two classes ω_i and ω_j is given by

(3.28)

The solution of this equation is a plane perpendicular to the line segment connecting and . The location of the hyperplane depends on the factor σ²log (P(ω_i)/P(ω_j)). If P(ω_i) = P(ω_j), the hyperplane is the perpendicular bisector of the line segment (see Figure 3.8).

Figure 3.9 gives an example of the decision function of the minimum distance classification. PRTools code to generate these figures is given in Listing 3.4.

Listing 3.4 PRTools code for the minimum distance classification

mus = [0.2 0.3; 0.35 0.75; 0.65 0.55; 0.8 0.25];
C = 0.01*eye(2);<b></b> z<b></b> = gauss(200,mus,C);
% Normal densities, uncorrelated noise with equal variances
w = nmsc(z);
figure (1); scatterd (z); hold on; plotm (w);
figure (2); scatterd (z); hold on; plotc (w);

3.1.2.3 Class-Independent Expectation Vectors

Another interesting situation is when the class information is solely brought forth by the differences between covariance matrices. In that case, the expectation vectors do not depend on the class: for all k. Hence, the central parts of the conditional probability densities overlap. In the vicinity of the expectation vector, the probability of making a wrong decision is always largest. The decision function takes the form of

(3.29)

If the covariance matrices are of the type σ²_kI, the decision boundaries are concentric circles or (hyper) spheres. Figure 3.10(a) gives an example of such a situation. If the covariance matrices are rotated versions of one prototype, the decision boundaries are hyperbolae. If the prior probabilities are equal, these hyperbolae degenerate into a number of linear planes (or, if N = 2, linear lines). An example is given in Figure 3.10(b).

3.2.1 Minimum Error Rate Classification with Reject Option

The minimum error rate classifier can also be extended with a reject option. Suppose that the cost of a rejection is C_rej regardless of the true class of the object. All other costs are uniform and defined by Equation (3.9).

We first note that if the reject option is chosen, the risk is C_rej. If it is not, the minimal conditional risk is the e_min (z) given by Equation (3.15). Minimization of C_rej and e_min (z) yields the following optimal decision function:

(3.31)

The maximum posterior probability max {P(ω|z)} is always greater than or equal to 1/K. Therefore, the minimal conditional error probability is bounded by (1 – 1/K). Consequently, in Equation (3.31) the reject option never wins if C_rej ≥ 1 − 1/K.

The overall probability of having a rejection is called the reject rate. It is found by calculating the fraction of measurements that fall inside the reject region:

(3.32)

The integral extends over those regions in the measurement space for which C_rej < e(z). The error rate is found by averaging the conditional error over all measurements except those that fall inside the reject region:

(3.33)

Comparison of Equation (3.33) with (3.16) shows that the error rate of a classification with a reject option is bounded by the error rate of a classification without a reject option.

Example 3.6 The reject option in the mechanical parts application In the classification of bolts, nuts, rings and so on, discussed in the previous examples, it might be advantageous to manually inspect those parts whose automatic classification is likely to fail. We assume that the cost of manual inspection is about $0.04. Table 3.3 tabulates the cost function with the reject option included (compare with Table 3.2).

The corresponding classification map is shown in Figure 3.11. In this example, the reject option is advantageous only between the regions of the rings and the nuts. The overall risk decreases from –$0.092 per classification to –$0.093 per classification. The benefit of the reject option is only marginal because the scrap is an expensive item when offered to manual inspection. In fact, the assignment of an object to the scrap class is a good alternative for the reject option.

Listing 3.5 shows the actual implementation in Matlab^®. Clearly it is very similar to the implementation for the classification including the costs. To incorporate the reject option, not only does the cost matrix need to be extended but clabels has to be redefined as well. When these labels are not supplied explicitly, they are copied from the dataset. In the reject case, an extra class is introduced, so the definition of the labels cannot be avoided.

Listing 3.5 PRTools codes for a minimum risk classification including a reject option

prload nutsbolts;
cost=[ −0.20        0.07      0.07       0.07; …
        0.07        −0.15     0.07       0.07; …
        0.07        0.07      −0.05      0.07; …
        0.03        0.03      0.03       0.03; …
       −0.16        −0.11     0.01       0.07];
clabels=str2mat (getlablist(z),‘reject’);
w1=qdc(z);     % Estimate a single Gaussian per class
scatterd(z);
               % Change output according to cost
w2=w1*classc*costm([],cost’,clabels);
plotc(w1);     % Plot without using cost
plotc(w2);     % Plot using cost

The detection problem is a classification problem with two possible classes: K = 3. In this special case, the Bayes decision rule can be moulded into a simple form. Assuming a uniform cost function, the MAP classifier, expressed in Equation (3.12), reduces to the following test:

(3.34)

If the test fails, it is decided for ω₂, otherwise for ω₁. We write symbolically:

(3.35)

Smaller type for ω₁ and ω₂ in 3.35 and 3.39 at top and bottom (see 3.36).

Rearrangement gives

(3.36)

Regarded as a function of ω_k the conditional probability density p(z|ω_k) is called the likelihood function of ω_k. Therefore, the ratio

(3.37)

is called the likelihood ratio. With this definition the classification becomes a simple likelihood ratio test:

(3.38)

The test is equivalent to a threshold operation applied to L(z) with the threshold P(ω₂)/P(ω₁).

Even if the cost function is not uniform, the Bayes detector retains the structure of (3.38); only the threshold should be adapted so as to reflect the change of cost. The proof of this is left as an exercise for the reader.

In case of measurement vectors with normal distributions, it is convenient to replace the likelihood ratio test with a so-called log-likelihood ratio test:

(3.39)

For vectors drawn from normal distributions, the log-likelihood ratio is

(3.40)

which is much easier than the likelihood ratio. When the covariance matrices of both classes are equal (C₁ = C₂ = C) the log-likelihood ratio simplifies to

(3.41)

Two types of errors are involved in a detection system. Suppose that is the result of a decision based on the measurement z. The true (but unknown) class ω of an object is either ω₁ or ω₂. Then the following four states may occur:

	ω = ω1	ω = ω2
	Correct decision I	Type II error
	Type I error	Correct decision II

Often a detector is associated with a device that decides whether an object is present (ω = ω₂) or not (ω = ω₁), or that an event occurs or not. These types of problems arise, for instance, in radar systems, medical diagnostic systems, burglar alarms, etc. Usually, the nomenclature for the four states is then as follows:

	ω = ω1	ω = ω2
	True negative	Missed event or false negative
	False alarm or false positive	Detection (or hit) or true positive

Sometimes, the true negative is called ‘rejection’. However, we have reserved this term for Section 3.2, where it has a different denotation.

The probabilities of the two types of errors, that is the false alarm and the missed event, are performance measures of the detector. Usually these probabilities are given conditionally with respect to the true classes, that is and . In addition, we may define the probability of a detection .

The overall probability of a false alarm can be derived from the prior probability using Bayes’ theorem, for example . The probabilities P_miss and P_fa as a function of the threshold T follow from (3.39):

(3.42)

In general, it is difficult to find analytical expressions for P_miss(T) and P_fa(T). In the case of Gaussian distributed measurement vectors, with C₁ = C₂ = C (see Figure 3.12), expression (3.42) can be further developed. Equation (3.41) shows that Λ(z) is linear in z. Since z has a normal distribution, so has Λ(z) (see Appendix C.3.1). The posterior distribution of Λ(z) is fully specified by its conditional expectation and its variance. As Λ(z) is linear in z, these parameters are obtained as

(3.43)

Likewise

(3.44)

and

(3.45)

With that, the signal-to-noise ratio is

(3.46)

The quantity is the squared Mahalanobis distance between and with respect to C. The square root, is called the discriminability of the detector. It is the signal-to-noise ratio expressed as an amplitude ratio.

The conditional probability densities of Λ are shown in Figure 3.13. The two overlapping areas in this figure are the probabilities of false alarm and missed event. Clearly, these areas decrease as d increases. Therefore, d is a good indicator of the performance of the detector.

Knowing that the conditional probabilities are Gaussian, it is possible to evaluate the expressions for P_miss(T) and P_fa(T) in (3.42) analytically. The distribution function of a Gaussian random variable is given in terms of the error function erf ():

(3.47)

Figure 3.13(a) shows a graph of P_miss, P_fa and P_det = 1 − P_miss when the threshold T varies. It can be seen that the requirements for T are contradictory. The probability of a false alarm (type I error) is small if the threshold is chosen to be small. However, the probability of a missed event (type II error) is small if the threshold is chosen to be large. A trade-off must be found between both types of errors.

The trade-off can be made explicitly visible by means of a parametric plot of P_det versus P_fa with varying T. Such a curve is called a receiver operating characteristic curve (ROC curve). Ideally, P_fa = 0 and P_det = 1, but the figure shows that no threshold exists for which this occurs. Figure 3.13(b) shows the ROC curve for a Gaussian case with equal covariance matrices. Here, the ROC curve can be obtained analytically, but in most other cases the ROC curve of a given detector must be obtained either empirically or by numerical integration of (3.42).

In Listing 3.6 the Matlab^® implementation for the computation of the ROC curve is shown. To avoid confusion about the roles of the different classes (which class should be considered positive and which negative) in PRTools the ROC curve shows the fraction false positive and false negative. This means that the resulting curve is a vertically mirrored version of Figure 3.13(b). Note also that in the listing the training set is used to both train a classifier and to generate the curve. To have a reliable estimate, an independent dataset should be used for estimation of the ROC curve.

Listing 3.6 PRTools code for estimation of a ROC curve

z = gendats(100,1,2);               % Generate a 1D dataset
w = qdc(z);                         % Train a classifier
r = roc(z*w);                       % Compute the ROC curve
plotr(r);                           % Plot it

The merit of an ROC curve is that it specifies the intrinsic ability of the detector to discriminate between the two classes. In other words, the ROC curve of a detector depends neither on the cost function of the application nor on the prior probabilities.

Since a false alarm and a missed event are mutually exclusive, the error rate of the classification is the sum of both probabilities:

(3.48)

In the example of Figure 3.13, the discriminability d equals . If this indicator becomes larger, P_miss and P_fa become smaller. Hence, the error rate E is a monotonically decreasing function of d.

Example 3.7 Quality inspection of empty bottles In the bottling industry, the detection of defects of bottles (to be recycled) is relevant in order to assure the quality of the product. A variety of flaws can occur: cracks, dirty bottoms, fragments of glass, labels, etc. In this example, the problem of detecting defects of the mouth of an empty bottle is addressed. This is important, especially in the case of bottles with crown caps. Small damages of the mouth may cause a non-airtight enclosure of the product which subsequently causes an untimely decay.

The detection of defects at the mouth is a difficult task. Some irregularities at the mouth seem to be perturbing, but in fact are harmless. Other irregularities (e.g. small intrusions at the surface of the mouth) are quite harmful. The inspection system (Figure 3.14) that performs the task consists of a stroboscopic, specular ‘light field’ illuminator, a digital camera, a detector, an actuator and a sorting mechanism. The illumination is such that in the absence of irregularities at the mouth, the bottle is seen as a bright ring (with fixed size and position) on a dark background. Irregularities at the mouth give rise to disturbances of the ring (see Figure 3.15).

The decision of the inspection system is based on a measurement vector that is extracted from the acquired image. For this purpose the area of the ring is divided into 256 equally sized sectors. Within each sector the average of the grey levels of the observed ring is estimated. These averages (as a function of the running arc length along the ring) are made rotational invariant by a translation invariant transformation, for example the amplitude spectrum of the discrete Fourier transform.

The transformed averages form the measurement vector z. The next step is the construction of a log-likelihood ratio Λ(z) according to Equation (3.40). Comparing the likelihood ratio against a suitable threshold value gives the final decision.

Such a detector should be trained with a set of bottles that are manually inspected so as to determine the parameters , etc. (see Chapter 6). Another set of manually inspected bottles is used for evaluation. The result for a particular application is shown in Figure 3.16.

It seems that the Gaussian assumption with equal covariance matrices is appropriate here. The discriminability appears to be d = 4.8.