3.1

Introduction

Support Vector Machine SVM is a useful technique for data classification [1,2,3,4,5,6,23,25,26]. The SVM machine in the Polish literature on the subject is most often called the SVM network due to its simple interpretation using neural networks. First, basic information explaining the principles of data classification using SVM in the case of binary (two-class) classification will be presented. This technique will then be extended to the problem of multi-class classification.

3.2

Binary classification

The SVM classifier belongs to the set of classifiers that maximize the separation margin [1,2,3] The SVM classifier belongs to the set of classifiers that maximize the separation margin. These classifiers recognize patterns belonging to two classes by specifying a decision surface that provides maximum distance to the nearest points in the training set called support vectors.

Let us assume that a set of training pairs is given (x_i, y_i) for i = 1,…, p, wherein each point x_i ∈ ℜⁿ belongs to one of two classes of patterns identified by labels y_i = +1 (class 1) or y_t = – 1 (class 2). Assuming a linear separability of classes, the equation of the separating hyperplane can be written using the formula

where w = [w₁, w₂,…,w_N]^T is an N-dimensional weight vector and x = [x₁, x₂,…,x_N]^T is a vector of the distinctive features values of the object. The b value specifies the hyperplane offset relative to the origin of the coordinate system.

Decision equations of classification take the following form:

The distance of any point x from the hyperplane (2) is

Intuitively, one can say that the greater the distance (4) of point x from the hyperplane (2), the greater the reliability of the classification.

Because the assumption of the linear separability of the training data has been made, so no training data satisfies the equation w^Tx_i + b = 0. It follows that the width of the separation margin is greater than zero, what means that inequalities (3) after their normalization can be written in the following form

One can write these two inequalities in one formula

If a pair (x_i, y_i) satisfies in (6) equality, then the vector x_i is called a support vector SV.

Assuming a linear separability of training data, these vectors only decide on the location of the optimal separation hyperplane and the width of the separation margin, which has a value

Optimal separating hyperplane (2) and separating margin in SVM in a two-dimensional space are presented in Figure 1.

Figure 1.

Optimal separating hyperplane and separating margin in SVM in a two-dimensional space.

The task of optimal separation margin design is to find such a margin, which has a maximum width. The problem of optimal selection of the separation hyperplane and the separation margin width comes down to solving the quadratic programming task in the following form

with constraints

This is a quadratic programming task with constraints that can be solved by the Lagrange multipliers method with α = [a₁,α₂,…,α_N]^T ≥0 multipliers using Karush-Kuhn-Tucker conditions [28]. Lagrange function is as follows

The solution to this optimization task is as follows [1,2,3]

wherein non-zero Lagrange multipliers correspond only to support vectors.

To determine the constant value b, one can use the fact that, according to Karush-Kuhn-Tucker conditions at the saddle point of the Lagrange function, the product of the multiplier by the constraint associated with the support vector x_sv is zero [28] α_sv(w^Tx_sv + b±1)=0, α_sv > 0. From here one can receive

The equation of the optimal separation hyperplane is as follows

while the decision function is as follows

More complex models of SVM linear networks include the possibility of incompletely linearly separable training data. Suitable formulas can be found in [1,2,3,6].

In the above considerations, a linear separability of training data was assumed. The linear inseparability of training data does not mean a lack of their separability at all. A common solution is the non-linear projection of original data into another functional space in which transformed patterns are linearly separable or the probability of their separability is very high. The condition is the use of non-linear transformation with a sufficiently high dimension K ≫ N of the feature space. The above-mentioned construction of the separation hyperplane and decision rule can be applied in a new space that is specified by the projection function Φ. The key property of the projection function Φ is that the scalar product of vectors Φ(x_i)^T · Φ(x) in the result space can be represented as a certain kernel function K (x_i, x). The basic kernel functions are following:

The values of α, β, γ, r and d are the parameters of the kernels.

In [4] there are some guidelines regarding situations in which a linear kernel can be used and in which an RBF radial kernel can be used. If the number of patterns in the training set is much smaller than the number of distinctive features of the patterns, a linear kernel can be used. In this paper, a linear kernel was used, because the number of training patterns was 35 (5 images for 7 types of patterns), and the length of the distinctive features vector was 640.

The equation of the separating hyperplane after applying the transformation of the primary space of distinctive features by means of the kernel function is as follows

while the decision function is as follows

3.3

Multiclass classification

SVM networks divide data into two classes. Unlike classic neural networks, where we can have multiple outputs (each output is associated with one class), recognition of multiple classes requires the implementation of multiple classification tasks using multiple SVM networks. The best-known strategies for solving the problem of multi-class classification are “one - against – one” and “one - against – all” methods [1,24,26]. Suppose the training base has M types of patterns.

In the case of the “one-against-one” method, M(M-1)/2 SVM classifiers are constructed. They distinguish sequentially two classes from the training set. One can receive a decision function for each pair of classes i and j

After training all SVM networks, you can proceed to classify objects from the test set. If sgn(f_ij (x)) indicates the i-th class, one should increase by 1 the counter of this class indications, in the opposite case it should be increased by 1 the counter of the j-th class. Finally, we choose the class whose counter has reached the highest value.

In the case of the “one - against - all” method, M SVM classifiers are constructed, each network being trained on a different training set. Suppose we train the m-th SVM two-class network. Class 1 includes m-th type patterns, while class 2 includes other types. Finally, we receive a decision function for each network

After training all SVM networks, one can proceed to classify objects from the test set. If sgn(f_ij (x)) indicates the m-th class, one should increase the number of indications in this class by 1, and in the opposite case one should increase the number of indications by 1 for all classes in the combined class. Finally, we choose the class whose counter achieved the highest value of wins. The authors [26] prefer the “one - against - all” method because of the linear dependence of the number of SVM networks on the number of pattern types in the training set.

The possibility of another extended interpretation of the results obtained by the “one - against - all” method is presented in [24]. According to [26], the higher the value of the function f_m (x) (18), the more reliable the classification result is. In the case of a linear kernel, such a criterion of reliability may be the distance of the recognized object from the separation plane, which is equal

In point 5.3 of the paper, the value of the f_m (x) decision function was used to construct the basic belief assignment on the results of the SVM multi-class classification.

In SVM multi-class classification, each m-th classifier determines the value of its decision function f_m(x).

Considering the classification results as a whole, one of three situations may occur:

5.1

The process of fusion of information from two classifiers

Each classifier used in the work transfers to the fusion module a vector of measures of reliability distribution on a set of types of objects in the training set. In this paper, it was assumed that both classifiers have the same training set. The set of possible hypotheses related to individual types of objects is as follows

wherein the index i numbers the type of the maritime object whose images are stored in a training set. PTN is the number of pattern types.

The hypotheses are mutually exclusive, i.e.

Each classifier sends its decisions in the form of a bba measure vector (bba - basic belief assignment).

wherein the index i = 1 determines the bba measure vector calculated by the SVM classifier and the index i = 2 determines the bba measure vector calculated by the DTW classifier.

The information fusion procedure is described by the following formula:

wherein m_F is a vector of the vector of bba masses determined by the R_F information fusion rule based on the vectors m₁ and m₂ of bba masses.

In the further part of the paper the Dempster’s rule [22] is described as a combination of the bba masses vectors. It has been used to implement the information fusion of two classifiers SVM and DTW.

5.2

The Dempster’s rule of combination of bba vectors

The Dempster’s rule of the bba measure vectors m_i sent by the classifiers is described for each θ_j ∈ Θ by the following formula [22]:

wherein the k₁₂ degree of conflict is defined by the formula:

while

Formula (28) makes sense if the denominator of expression (28) is nonzero, i.e. the degree of conflict k₁₂ is less than 1.

5.3

The method of determining the bba for the SVM classifiers

The procedure of image recognition by means of the SVM method “one - against – all” in accordance with the content of point 3.3 and [24.26] allows to determine the basic belief assignment bba on a set of pattern types. Each k-th pattern type is associated with one SVM and the identification process determines the value of the decision function

The value of this function can be used to determine the value of the degree of belief that the recognized object belongs to the class with the number k (k = 1, …, PTN). In [3] it was proposed to use the logistic regression function in accordance with the following formula

In the formula (32) k numbers SVMs. As one can see 0 < m(x, k) < 1.

The above measure is not standardized, therefore it should be transformed in the following way

One should note that the above method of mass determination is simplified, because it does not take into account the lack of the type of image pattern corresponding to the recognized image.

5.4

The method of determining the bba for the DTW classifiers

The DTW image recognition procedures determines the distance between the values of the distinctive features of the recognized image and the values of the distinctive features of the image pattern types stored in the training set.

By accepting the designations in Chapter 4, one can determine the value of the degree of belief that the recognized object belongs to the class with the number k (k = 1, …, PTN) as follows

From formula (34), it follows that if , then m(LV, k) = 1, while if , then 0 < m(LV, k) < 1.

The above measure is not standardized, therefore it should be transformed in the following way

One should note that the above method of mass determination is simplified, because it does not take into account the lack of the type of image pattern corresponding to the recognized image.

An extended version of determining the basic belief assignment can also be considered. The image recognition classifier compares the distance with the permissible distance δ from the center of the cluster of the k-th type of image pattern. The distance δ defines the recognition area of the k-th image pattern. The set of image patterns will be divided into two subsets: patterns that meet the classification condition in relation to the recognized image and patterns that do not meet the condition of classification in relation to the recognized image .

The value of the basic belief assignment is then determined by the formula

The sum of the measures assigned to the images whose distinctive features lie outside the boundary will be treated as the measure assigned to the new hypothesis “unrecognized object”.

6.1

Results of maritime objects recognition for SVM classifier

Research on the efficiency of maritime object recognition based on FLIR images using SVM classifiers was preceded by the process of teaching two-class SVM networks in accordance with the “one - against - all” strategy. The study consisted in selecting different images from the test database, and then performing as many classification tasks for each recognized object as the number of pattern types contained in the training set. The choice of the recognized type was carried out in accordance with the principles described in section 3.3 and the formula (20). It was also possible to obtain a result indicating that the object type was not recognized (point 3 therein), which was treated as an error, because all object types from the test set belonged to the set of object types from the training set. The results are shown in the Table 1.

Table 1.

The results of recognition of maritime object images using the SVM classifier.

6.2

Results of maritime objects recognition for DTW classifier

The recognition procedure examined subsequently various images from the test data set. A cluster of such type of pattern images was chosen, which had the smallest DTW distance from the recognized object. If the type of image selected was consistent with the type of image recognized, one can assume that the image was recognized correctly, otherwise the image was recognized incorrectly. The results are presented in the Table 2

Table 2.

The results of recognition of maritime object images using the DTW classifier.