Multidimensional data classification with chordal distance based kernel and Support Vector Machines
Introduction
Majority of the classical pattern recognition methods operate on vector spaces (Duda et al., 2000). This reflects basic properties of simple measurements which stack different feature values of measurements into one-dimensional (1D) vectors, which are then assigned to predefined classes. However, many phenomena lead to measurements, which change specifically depending on a chosen dimension or a coordinate. Well known examples are video sequences, which are composed of two-dimensional frames containing three-valued pixels, displayed a number of times per second. Naturally, they are four-dimensional data which become even five-dimensional considering sound. Such examples arise in many domains when measuring signals which vary depending on a number of factors higher than one. These are called multidimensional data and are well represented with tensors, recently introduced to the signal processing and machine learning community (De Lathauwer, 1997, Kolda and Bader, 2009, de Lathauwer et al., 2000). However, they do not fit well into the classical 1D vector based frameworks. Although there are many ways to vectorize multidimensional data, it has been observed that such operation usually leads to significant loss of important information, since some values which were in local vicinity (in terms of a chosen metric) become differently arranged if data are arbitrarily linearized into a vector. Therefore in recent years much attention gained development of pattern recognition methods which inherently consider multidimensionality of the classified data (Cyganek, 2013b, Signoretto et al., 2011, Vasilescu and Terzopoulos, 2002, Vasilescu and Terzopoulos, 2007). On the other hand, one of the newest and highly appreciated achievements in pattern recognition of recent two decades are Support Vector Machines (SVMs) which, operating on vector spaces, successively classify different types of data with support of the kernel functions (Cortes and Vapnik, 1995, Duda et al., 2000).
In this paper we analyze properties of the SVMs employed to a multidimensional data classification task. More specifically, we consider classification of the monochrome, color, and hyperspectral images directly treated as 2D and 3D tensors, and with help of the recently proposed chordal kernel for tensor data (Signoretto et al., 2011). The kernel is employed to different versions of SVMs, trained with Sequential Minimal Optimization (SMO) algorithm (Platt, 1998) as well as with the Least-Squares (LS) method (Suykens et al., 2002). The purpose of this work is to verify usefulness of such approach to the common image classification problem, as well as to scrutinize its basic properties and implementation issues. To the best of our knowledge this is a first research that directly shows properties of the chordal tensor and SMO trained SVMs. Also, the obtained results lead us to the important conclusions on favor of such approach which we believe can be successively employed to many systems requiring image classification with significant improvement to the classification accuracy. We also discuss implementation issues, as well as we analyze computational costs of this new approach.
The main contributions of this work are as follows:
- •
Proposal of an efficient classification method for complex and multidimensional data (e.g., color, hyperspectral images or video sequences), represented as tensors, with the SVM with chordal distance-based kernel and trained with the SMO algorithm. Also, we compare this approach with the LS version of the SVM.
- •
Detailed information and solutions to the implementation issues considered with efficient running of the described tensor kernel.
- •
Comprehensive experimental evaluation and statistical assessment of the proposed system, carried out on a number of multidimensional image classification datasets from various domains, in both binary and multi-class scenarios. Examination of the properties of different models of SVMs according to accuracy, training complexity, classification speed and the required number of support vectors.
The rest of this paper is organized as follows. In the next section works related to representation and classification of multidimensional data, as well as SVM based classifiers, are discussed. Then, the chordal distance-based kernel is presented, with all of the required details for its efficient implementation. Section 4 contains experimental study, while the last section concludes the paper.
Section snippets
Related works
Let us briefly review recent works which were influential to our work. Kernel design is still an active research topic. However, there is a gap between the kernel methods and multidimensional data which stems from the fact that kernel functions in their basic definition accept two vector arguments, whereas tensor data frequently are not identical with vectors. Thus, a common practice when classifying objects with SVM is to vectorize image patterns before applying them to a classifier. However,
Chordal distance between pattern tensors
In this section, we will discuss the basis of tensors applied in pattern recognition and machine learning, as well as methodology for computing the chordal distance for tensor-based kernels.
Experimental investigations
In this section, we will present the experimental evaluation of the SVM classifier with the chordal distance based (CDB) kernel for analysis of complex multidimensional data. We want to establish, if the tensor representation of complex data can boost the quality of the kernel classifier. We compare the proposed method with a three popular SVM models that are widely used in many practical applications. We run two kinds of experiments:
- •
Binary classification task, in which we analyse the
Conclusions
In this paper, we have presented a novel approach for handling complex and multidimensional data. It was based on data representation and processing with tensors and classifying them with a Support Vector Machine endowed with the chordal distance-based kernel. By handling data as tensors, we were able to process multidimensional data (such as color images) as single objects, preserving the mutual relations between features (i.e. pixels in this case). The used kernel allowed us to efficiently
Acknowledgments
The financial support from the Polish National Science Centre NCN in the year 2014, Contract no. DEC-2011/01/B/ST6/01994, is greatly acknowledged.
References (49)
- et al.
An overview of ensemble methods for binary classifiers in multi-class problemsexperimental study on one-vs-one and one-vs-all schemes
Pattern Recognit.
(2011) - et al.
Dynamic classifier selection for one-vs-one strategyavoiding non-competent classifiers
Pattern Recognit.
(2013) - et al.
Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data miningexperimental analysis of power
Inf. Sci.
(2010) - et al.
A kernel-based framework to tensorial data analysis
Neural Netw.
(2011) Combined 5×2 cv f test for comparing supervised classification learning algorithms
Neural Comput.
(1999)- et al.
Tensor Analysis on Manifolds. Dover Books on Mathematics
(2012) - et al.
LIBSVMa library for support vector machines
ACM Trans. Intell. Syst. Technol.
(2011) - et al.
Nonnegative Matrix and Tensor FactorizationsApplications to Exploratory Multi-way Data Analysis and Blind Source Separation
(2009) - et al.
Packing lines, planes, etc. packings in Grassmannian spaces
Exp. Math.
(1996) - et al.
Support-vector networks
Mach. Learn.
(1995)
Object Detection and Recognition in Digital Images: Theory and Practice
On the best rank-1 and rank-(r1,r2,…,rn) approximation of higher-order tensors
SIAM J. Matrix Anal. Appl.
Solving multiclass learning problems via error-correcting output codes
J. Artif. Intell. Res.
Tensor Analysis and Nonlinear Tensor Functions
Pattern Classification
Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences
Decomposing the tensor kernel support vector machine for neuroscience data with structured labels
Mach. Learn.
Classification by pairwise coupling
Ann. Stat.
A database for handwritten text recognition research
IEEE Trans. Pattern Anal. Mach. Intell.
Cited by (34)
Nonlinear fault detection for batch processes via improved chordal kernel tensor locality preserving projections
2020, Control Engineering PracticeOLLAWV: OnLine Learning Algorithm using Worst-Violators
2018, Applied Soft Computing JournalCitation Excerpt :This section defines the notation that will be used throughout the paper, describes the support vector machine problem, and reviews related works on current popular solvers and online learning algorithms aimed at training support vector machines. Although support vector machines represent a major development in machine learning algorithms, in the case of large-scale problems (hundreds of thousands to several millions of samples), the design of SVM training algorithms still has room for improvement [23,24]. So far, there have been several different approaches for tackling large-scale SVM classification problems.
Approximately symmetrical face images for image preprocessing in face recognition and sparse representation based classification
2016, Pattern RecognitionCitation Excerpt :Zhang et al. [35] proposed to use gradientfaces (GRF) and Šrtuc and Pavešić [36] presented a non-local means based normalization method (NLM) as image preprocessing techniques for robust face recognition. Cyganek et al. [37] proposed a very impressive method, which used Support Vector Machines with specific tensor kernel and achieved high accuracy for processing multidimensional images (among which are face datasets) without any need for sophisticated pre-processing or posing restrictions on the face pose. In addition, the Lambertian reflectance model also has received much attention in remedying the problems caused by unbalanced illuminations [39].
Explainable artificial intelligence as a reliable annotator of archaeal promoter regions
2023, Scientific Reports