A Nonlinear Tensor-Based Machine Learning Algorithm for Image Classification

Machine learning is a research hotspot in recent years. Data representation is an important problem in machine learning. The data from different sources should be expressed in a form that facilitates the application of machine learning techniques. Traditionally, the data are inputted as vectors for machine learning. In real-world scenarios, however, it is more accurate to represent data in tensor form. As a result, the tensor representation of data has become a new research direction in the field of data mining and machine learning [1-5]. Recent years has seen a growing attention being paid to tensor representation and its application in fields like image classification, face recognition, scene classification and bioinformatics [6-15].

In 2006, Cai et al. [16] proposed the support tensor machine (STM), a novel machine learning method based on tensor data. Since then, great progress has been made in the theories and learning models that solve machine learning problems based on tensor data. Compared with vector-based machine learning, the tensor-based machine learning has two unique advantages: the ability to preserve the spatiotemporal information, allowing full utilization of the data, and the suitability for solving high-dimensional problems with a small sample size. Therefore, the tensor-based machining learning can be applied well in classical high-dimensional, small-sample problems like face recognition and image classification.

Considering the nonlinearity of many real-world data, many scholars have adopted kernel methods for tensor representation. For example, Signoretto et al. [17] elaborated on a possible framework that extends the flexibility of tensor-based models with kernel-based techniques, which provides a constructive definition of the infinite dimensional tensor feature space. He et al. [18] developed a brand-new design of structure-maintaining kernels for supervised tensor learning. If the order of tensors is specified, tensor representation can be achieved by some very simple and convenient kernel methods, namely, the matrix kernel function of second-order tensor [19-22] and the K3rd kernel function for third-order tensor [23, 24].

This paper probes into the nonlinear classification problem with tensor representation, and designs a tensor-based nonlinear classification algorithm, namely, the kernel-based STM (KSTM). Since images can naturally be represented by tensor data [25-28], the proposed KSTM was applied to solve image classification problems. Through numerical experiments, it is proved that the KSTM achieved better classification accuracy than the linear method, especially for the high-dimensional problem with a small sample size.

Let $\left\{\mathbf{X}_{i}, y_{i}\right\}$, i=1,…,m be a set of training samples, where $\mathbf{x}_{i} \in \mathbb{R}^{\mathrm{n}_{1}} \otimes \mathbb{R}^{\mathrm{n}_{2}}$ is a sample (data point) in a 2^nd order tensor space ($\mathbb{R}^{{n}_{1}}$ and $\mathbb{R}^{{n}_{2}}$ are two vector spaces), and $y_{i} \in\{-1,1\}$ is the label of $\mathbf{X}_{i}$. The KSTM mainly aims to find a decision hyperplane by mapping the tensor data into a high-dimensional tensor feature space, such that the data points can be separated by the maximum margin from each class. Hence, the KSTM can be described as the following optimal quadratic programming problem:

$\min _{\boldsymbol{u}, \boldsymbol{v}, \boldsymbol{b}, \boldsymbol{\xi}} \frac{1}{2}\left\|\mathbf{u} \mathbf{v}^{T}\right\|^{2}+C \sum_{i=1}^{m} \xi_{i}$  

s.t. $y_{i}\left(\mathbf{u}^{T} \Phi\left(\mathbf{X}_{i}\right) \mathbf{v}+b\right) \geq 1-\xi_{i}$      (10)

$\xi_{i} \geq 0, i=1, \dots, m$

Meanwhile, the decision function of a nonlinear classifier in the tensor space can be established as:

$f(\mathbf{X})=\operatorname{sgn}\left(\left(\mathbf{u v}^{T} \cdot \Phi(\mathbf{X})\right)+b\right) \quad \mathbf{u} \in \mathbb{R}^{n_{1}}, \mathbf{v} \in \mathbb{R}^{n_{2}}$  (11)

where, $\Phi$ is the function that maps the data from the original tensor space to a tensor feature space.

According to Gao’s kernel function for tensor representation [20], a nonlinear mapping function $\Phi\left(\mathbf{X}_{\mathbf{i}}\right)$ can be adopted to map $\mathbf{X}_{\mathbf{i}}$ into a high-dimensional tensor feature space:

$\Phi\left(\mathbf{X}_{i}\right)=\left[\begin{array}{c}{\varphi\left(z_{i 1}\right)} \\ {\varphi\left(z_{i 2}\right)} \\ {\vdots} \\ {\varphi\left(z_{i n_{1}}\right)}\end{array}\right]$          (12)

where, ${z}_{i p}$ is the p-th row of $\mathbf{X}_{i}$. Thus, the new kernel function for tensors can be constructed as:

$K\left(\mathbf{X}_{i}, \mathbf{X}_{j}\right)=\Phi\left(\mathbf{X}_{i}\right) \Phi\left(\mathbf{X}_{j}\right)^{T}=\left[\begin{array}{c}{\varphi\left(z_{i 1}\right)} \\ {\varphi\left(z_{i 2}\right)} \\ {\vdots} \\ {\varphi\left(z_{i n_{1}}\right)}\end{array}\right]\left[\begin{array}{c}{\varphi\left(z_{j 1}\right)} \\ {\varphi\left(z_{j 2}\right)} \\ {\vdots} \\ {\varphi\left(z_{j n_{1}}\right)}\end{array}\right]^{T}$$=\left(\begin{array}{ccc}{\varphi\left(z_{i 1}\right) \varphi\left(z_{j 1}\right)^{T}} & {\cdots} & {\varphi\left(z_{i 1}\right) \varphi\left(z_{j n_{1}}\right)^{T}} \\ {\vdots} & {\ddots} & {\vdots} \\ {\varphi\left(z_{i n_{1}}\right) \varphi\left(z_{j 1}\right)^{T}} & {\cdots} & {\varphi\left(z_{i n_{1}}\right) \varphi\left(z_{j n_{1}}\right)^{T}}\end{array}\right)$   (13)

For example, if Gaussian kernel function is employed, the ij-th element of the kernel matrix can be expressed as:

$\varphi\left(z_{i p_{1}}\right) \varphi\left(z_{j p_{1}}\right)^{T}=e^{\frac{\left\|z_{i p_{1}}-z_{i p_{2}}\right\|^{2}}{2 \sigma^{2}}}$     (14)

Obviously, the kernel function for tensors differs from that for vectors. The result of kernel function is a scalar in the vector space and a kernel matrix in the tensor space.

3.1 Optimal projection based on the KSTM

Tao et al. [1] provided a simple yet effective computing method to solve the optimization problem (10). First, it is assumed that u is a constant, $\mu_{1}=\|\mathbf{u}\|^{2}$ and $\mathbf{x}_{i}=\Phi\left(\mathbf{X}_{i}\right)^{\mathrm{T}} \mathbf{u}$. Then, the optimization problem (10) is identical to the standard SVM optimization problem with variable v:

$\min _{\boldsymbol{v}, \boldsymbol{b}, \boldsymbol{\xi}} \frac{1}{2} \mu_{1}\|\mathbf{v}\|^{2}+C \sum_{i=1}^{m} \xi_{i}$

s.t. $y_{i}\left(\mathbf{v}^{T} \mathbf{x}_{i}+b\right) \geq 1-\xi_{i}$       (15)

$\xi_{i} \geq 0, i=1, \dots, m$

Thus, the following dual problem can be obtained:

$\min _{\alpha} \frac{1}{2 \mu_{1}} \sum_{i, j=1}^{m} \alpha_{i} \alpha_{j} \mathbf{u}^{T} K\left(\mathbf{X}_{i} \cdot \mathbf{X}_{j}\right) \mathbf{u}$  

s. $t .0 \leq \alpha_{i} \leq C$         (16)

$\sum_{i=1}^{m} \alpha_{i}=1, i=1, \dots, m$

Solving formula (16), it is possible to obtain the Lagrangian multiplier $\alpha_{i}^{*}$. Then, v and $\|\mathbf{v}\|^{2}$ can be respectively derived from:

$\mathbf{v}=\frac{1}{\mu_{1}} \sum_{i=1}^{m} \alpha_{i}^{*} \Phi\left(\mathbf{X}_{i}\right)^{T} \mathbf{u}$        (17)

$\|\mathbf{v}\|^{2}=\mathbf{v}^{T} \mathbf{v}=\frac{1}{\mu_{1}^{2}} \sum_{i, j=1}^{m} \alpha_{i}^{*} \alpha_{j}^{*} \mathbf{u}^{T} K\left(\mathbf{X}_{i}, \mathbf{X}_{j}\right) \mathbf{u}$    (18)

Let $\mu_{2}=\|\mathbf{v}\|^{2}$ and $\tilde{\mathbf{x}}_{i}=\Phi\left(\mathbf{X}_{i}\right) \mathbf{v}=\frac{1}{\mu_{1}} \sum_{i=1}^{m} \alpha_{i}^{*} K\left(\mathbf{X}_{i}, \mathbf{X}_{j}\right) \mathbf{u}$. Then, optimal quadratic programming problem can be constructed to solve u and $\|\mathbf{u}\|^{2}$:

$\min _{\boldsymbol{u}, b, \boldsymbol{\xi}} \frac{1}{2} \mu_{2}\|\mathbf{u}\|^{2}+C \sum_{i=1}^{m} \xi_{i}$  

s.t. $y_{i}\left(\mathbf{u}^{T} \tilde{\mathbf{x}}_{i}+b\right) \geq 1-\xi_{i}$        (19)

$\xi_{i} \geq 0, i=1, \dots, m$

Solving formula (19), the quadratic program can be solved as a dual problem:

$\min _{\alpha} \frac{1}{2 \mu_{2}} \sum_{i, j=1}^{m} \alpha_{i} \alpha_{j}\left(\tilde{\mathbf{x}}_{i} \cdot \tilde{\mathbf{x}}_{j}\right)$

s. $t .0 \leq \alpha_{i} \leq C$              (20)

$\sum_{i=1}^{m} \alpha_{i}=1, i=1, \dots, m$

Thus, u and v can be obtained by iteratively solving formulas (16) and (20). The value of u can be empirically set to the vector of all ones.

The optimal normal vector from optimization problem (19) can be expressed as $\mathbf{u}=\frac{1}{\mu_{2}} \sum_{i=1}^{m} \tilde{\alpha}_{i}^{*} \tilde{\mathbf{x}}_{i}$, where $\tilde{\alpha}_{i}^{*}$ is the result of dual problem (20). Then, the optimal boundary can be determined through support vector expansion:

$f(\mathbf{X})=\operatorname{sgn}\left(\mathbf{u}^{T} \Phi(\mathbf{X}) \mathbf{v}+b\right)$$=\operatorname{sgn}\left(\frac{1}{\mu_{1}} \sum_{i=1}^{m} \alpha_{i}^{*} \mathbf{u}^{T} K\left(\mathbf{X}, \mathbf{X}_{i}\right) \mathbf{u}+b\right)$         (21)

The parameter b can be calculated by:

$b=\frac{1}{\mu_{1}} \sum_{i=1}^{m} \alpha_{i}^{*} \mathbf{u}^{T} K\left(\mathbf{X}_{i}, \mathbf{X}_{j}\right) \mathbf{u}$       (22)

3.2 The KSTM algorithm

Input: The training sample $\mathbf{x}_{i} \in R^{n_{1}} \otimes R^{n_{2}}(i=1, \ldots, m)$, parameter u, and testing samples $\mathbf{Xt}_{j} \in R^{n_{1}} \otimes R^{n_{2}}(j=1, \ldots, t)$.

Output: The optimal parameter variables in the decision function ($\mathbf{u} \in R^{n_{1}}$  and $\mathbf{v} \in R^{n_{2}}$) and b, the class label of the testing sample.

Step 1. Initialization: Let $\mathbf{u}=(1, \ldots, 1)^{T}$;

Step 2. Calculation of v: Let $\mu_{1}=\|\mathbf{u}\|^{2}$, obtain the optimal solution $\alpha^{*}$ by solving optimization problem (16), and then calculate:

$\|\mathbf{v}\|^{2}=\mathbf{v}^{T} \mathbf{v}=\frac{1}{\mu_{1}^{2}} \sum_{i, j=1}^{m} \alpha_{i}^{*} \alpha_{j}^{*} \mathbf{u}^{T} K\left(\mathbf{X}_{i}, \mathbf{X}_{j}\right) \mathbf{u}$

$\tilde{\mathbf{x}}_{i}=\Phi\left(\mathbf{X}_{i}\right) \mathbf{v}=\frac{1}{\mu_{1}} \sum_{i=1}^{m} \alpha_{i}^{*} K\left(\mathbf{X}_{i}, \mathbf{X}_{j}\right) \mathbf{u}$

Step 3. Calculation of u: Let $\mu_{2}=\|\mathbf{v}\|^{2}$, obtain the optimal solution $\alpha^{*}$ by solving optimization problem (20), and then calculate:

$\mathbf{u}=\frac{1}{\mu_{2}} \sum_{i=1}^{m} \tilde{\alpha}_{i}^{*} \tilde{\mathbf{x}}_{i}$

Step 4. Repeat Steps 2~3 until the termination condition (the maximum number of iterations or the convergence condition) is met:

$\left\|\mathbf{u}_{i}-\mathbf{u}_{i-1}\right\| \leq$ tolerance        (23)

Step 5. Get the discriminant function and calculate the class label of the test sample:

$f\left(\mathrm{Xt}_{j}\right)=\operatorname{sgn}\left(\mathbf{u}^{T} \Phi\left(\mathrm{Xt}_{j}\right) \mathbf{v}+b\right)$     (24)

Step 6. End.

This paper proposes a kernel-based support tensor machine (KSTM) based on tensor representation, and applies it to classify real-world images. To verify its performance, the KSTM was tested through classification experiments on the YALE face image datasets. The greatest advantage of our algorithm is the ability to maintain the integrity of tensor data, especially for high-dimensional problems with a small sample size. The KSTM also has better classification accuracy than linear algorithms.

Of course, there are some limitations with our algorithm. Despite having fewer decision variables than the vector classifier, the tensor classifier adopts the alternating projection algorithm in its STL framework, i.e. its training time depends on the iteration times of the alternating projection algorithm, which is often much higher than the vector model. Hence, the future research will try to optimize the KSTM algorithm and improve its training efficiency. Furthermore, further research will be carried out on the high-order KSTM.