Multidimensional data classification with chordal distance based kernel and Support Vector Machines

https://doi.org/10.1016/j.engappai.2015.08.001Get rights and content

Abstract

In contemporary machine learning multidimensional rather than pure vector like data are frequently encountered. Traditionally, such multidimensional objects, such as color images or video sequences, are first transformed to a vector representation, and then processed by the classical learning algorithms operating with vectors. However, such multi-to-one dimension transformations usually lead to loss of important information. Thus, proposing novel methods for representing and learning with complex and multidimensional data is in focus of current machine learning research. In this paper, we propose a new method for efficient classification of multidimensional data based on a tensor-based kernel applied to the Support Vector Machines. We represent data as tensors, in order to preserve data dimensionality and to allow for processing of complex structures. To allow for an effective classification, we augment a Support Vector Machine (SVM) trained with Sequential Minimal Optimization (SMO) procedure with a chordal distance-based kernel for efficient classification of tensor-like objects. We also discuss different optimization methods for SVM, as well as present implementation details with computational time analysis. The proposed method is evaluated in both binary and multi-class classification problems. Comprehensive experimental analysis carried on a number of multidimensional benchmarks shows high usefulness of the proposed approach.

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)

  • Cyganek, B., 2013a. Pattern recognition framework based on the best rank–(r1,r2,...,rk) tensor approximation. In:...
  • B. Cyganek

    Object Detection and Recognition in Digital Images: Theory and Practice

    (2013)
  • Cyganek, B., 2013c. DeRecLib....
  • De Lathauwer, Lieven, 1997. Signal Processing Based on Multilinear Algebra (Ph.D. thesis). Katholike Universiteit...
  • Lieven De Lathauwer et al.

    On the best rank-1 and rank-(r1,r2,…,rn) approximation of higher-order tensors

    SIAM J. Matrix Anal. Appl.

    (2000)
  • Thomas G. Dietterich et al.

    Solving multiclass learning problems via error-correcting output codes

    J. Artif. Intell. Res.

    (1995)
  • Y.I. Dimitrienko

    Tensor Analysis and Nonlinear Tensor Functions

    (2002)
  • Richard O. Duda et al.

    Pattern Classification

    (2000)
  • Goel, Navin, Bebis, George, Nefian, Ara, 2005. Face recognition experiments with random projection. In: Proceedings of...
  • G.H. Golub et al.

    Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences

    (2013)
  • Hamm, Jihun, Lee, Daniel D., 2008. Grassmann discriminant analysis: a unifying view on subspace-based learning. In:...
  • David Hardoon et al.

    Decomposing the tensor kernel support vector machine for neuroscience data with structured labels

    Mach. Learn.

    (2010)
  • T. Hastie et al.

    Classification by pairwise coupling

    Ann. Stat.

    (1998)
  • J. Hull

    A database for handwritten text recognition research

    IEEE Trans. Pattern Anal. Mach. Intell.

    (1994)
  • Cited by (34)

    • OLLAWV: OnLine Learning Algorithm using Worst-Violators

      2018, Applied Soft Computing Journal
      Citation 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 Recognition
      Citation 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].

    View all citing articles on Scopus
    View full text