Online Tensor-Based Learning for Multi-Way Data

Given a three-way tensor $\mathcal{X}\in\Re^{I\times J\times K}$, CP decomposes $\mathcal{X}$ into three matrices $A\in\Re^{I\times R}$, $B\in\Re^{J\times R}$and $C\in\Re^{K\times R}$, where $R$ is the latent factors. It can be written as follows:

where ”$\circ$” is a vector outer product. $R$ is the latent element, $A_{ir},B_{jr}$ and $C_{kr}$ are r-th columns of component matrices $A\in\Re^{I\times R}$, $B\in\Re^{J\times R}$and $C\in\Re^{K\times R}$. The main goal of CP decomposition is to decrease the sum square error between the model and a given tensor $\mathcal{X}$. Equation 2 shows our loss function $L$ needs to be optimized.

where $\|\mathcal{X}\|^{2}_{f}$ is the sum squares of $\mathcal{X}$ and the subscript $f$ is the Frobenius norm. The loss function $L$ presented in Equation 2 is a non-convex problem with many local minima since it aims to optimize the sum squares of three matrices. The CP decomposition often uses the Alternating Least Squares (ALS) method to find the solution for a given tensor. The ALS method follows the offline training process which iteratively solves each component matrix by fixing all the other components, then it repeats the procedure until it converges (Khoa et al., 2017). The rational idea of the least square algorithm is to set the partial derivative of the loss function to zero concerning the parameter we need to minimize. Algorithm 1 presents the detailed steps of ALS.

In online settings, it is a naive approach would be to recompute the CP decomposition from scratch for each new incoming $X^{(t+1)}$. Therefore, this would become impractical and computationally expensive as new incoming datum would have a minimal effect on the current tensor. Zhou et al. (Zhou et al., 2016) proposed a method called onlineCP to address the problem of online CP decomposition using the ALS algorithm. The method was able to incrementally update the temporal mode in multi-way data but failed for non-temporal modes (Khoa et al., 2017). In recent years, several studies have been proposed to solve the CP decomposition using the stochastic gradient descent (SGD) algorithm which will be discussed in the following section.

Stochastic gradient descent algorithm is a key tool for optimization problems. Assume that our aim is to optimize a loss function $L(x,w)$, where $x$ is a data point drawn from a distribution $\mathcal{D}$ and $w$ is a variable. The stochastic optimization problem can be defined as follows:

The stochastic gradient descent method solves the above problem defined in Equation 13 by repeatedly updates $w$ to minimize $L(x,w)$. It starts with some initial value of $w^{(t)}$ and then repeatedly performs the update as follows:

where $\eta$ is the learning rate and $x^{(t)}$ is a random sample drawn from the given distribution $\mathcal{D}$.

This method guarantees the convergence of the loss function $L$ to the global minimum when it is convex. However, it can be susceptible to many local minima and saddle points when the loss function exists in a non-convex setting. Thus it becomes an NP-hard problem. The main bottleneck here is due to the existence of many saddle points and not to the local minima (Ge et al., 2015). This is because the rational idea of gradient algorithm depends only on the gradient information which may have $\frac{\partial L}{\partial u}=0$ even though it is not at a minimum.

Recently, SGD has attracted several researchers working on tensor decomposition. For instance, Ge et al.(Ge et al., 2015) proposed a perturbed SGD (PSGD) algorithm for orthogonal tensor optimization. They presented several theoretical analysis that ensures convergence; however, the method does not apply to non-orthogonal tensor. They also didn’t address the problem of slow convergence. Similarly, Maehara et al.(Maehara et al., 2016) propose a new algorithm for CP decomposition based on a combination of SGD and ALS methods (SALS). The authors claimed the algorithm works well in terms of accuracy. Yet its theoretical properties have not been completely proven and the saddle point problem was not addressed. Rendle and Thieme (Rendle and Schmidt-Thieme, 2010) propose a pairwise interaction tensor factorization method based on Bayesian personalized rank. The algorithm was designed to work only on three-way tensor data. To the best of our knowledge, this is the first work that applies SGD algorithm augmented with Nesterov’s optimal gradient and perturbation methods for optimal CP decomposition of multi-way tensor data.

Given a set of training data $X=\{{x_{i}}\}_{i=1}^{n}$, with $n$ being the number of samples, OCSVM maps these samples into a high dimensional feature space using a function $\phi$ through the kernel $K(x_{i},x_{j})=\phi(x_{i})^{T}\phi(x_{j})$. Then OCSVM learns a decision boundary that maximally separates the training samples from the origin (Schölkopf et al., 2001). The primary objective of OCSVM is to optimize the following equation:

where $\nu$ $(0<\nu<1)$ is a user defined parameter to control the rate of anomalies in the training data, $\xi_{i}$ are the slack variable, $\phi(x_{i})$ is the kernel matrix and $w.\phi(x_{i})-\rho$ is the separating hyperplane in the feature space. The problem turns into a dual objective by introducing Lagrange multipliers $\alpha=\{\alpha_{1},\cdots,\alpha_{n}\}$. This dual optimization problem is solved using the following quadratic programming formula (Schölkopf and Smola, 2002):

where $\phi(x_{i},x_{j})$ is the kernel matrix, $\alpha$ are the Lagrange multipliers and $\rho$ known as the bias term.

The partial derivative of the quadratic optimization problem (defined in Equation 6) with respect to $\alpha_{i}$, $\forall i\in S$, is then used as a decision function to calculate the score for a new incoming sample:

The OCSVM uses Equation 8 to identify whether a new incoming point belongs to the positive class when returning a positive value, and vice versa if it generates a negative value.

The achieved OCSVM solution must always satisfy the constraints from the Karush-Khun-Tucker (KKT) conditions, which are described in Equation 12.

where $\alpha_{i}=0$ is referred to the non-support or reserve training vectors denoted by R, $\alpha_{i}=1$ represents non-margin support or error vectors denoted by E and $0<\alpha_{i}<1$ represents the support vectors denoted by S.

In an online setting, we need to ensure the KKT conditions are maintained while learning and adding a new data point to the previous solution. Several researchers address the problem of online SVM (Cauwenberghs and Poggio, 2000; Diehl and Cauwenberghs, 2003; Laskov et al., 2006) where all are based on the original method known as bookkeeping which proposed by Cauwenberghs et al.. The method computes the new coefficients of the SVM model while preserving the KKT conditions. This method made useful contributions to the incremental learning of two classes SVM (TCSVM), but it cannot be used for the one-class problem. Davy et al. (Davy et al., 2006) concluded that such incremental SVM methods cannot be directly applied to the one-class problem as they are dependent on the TCSVM margin areas which do not exist in OCSVM. Therefore, Davy et al.proposed an online OCSVM-based threshold value. In this method, the anomaly score is computed for each incoming datum and evaluated against a predefined threshold value. The new datum is added to the training data and the model coefficients are updated accordingly when its value is greater than the threshold. Similarly, Wang et al.(Wang et al., 2013) presented an online OCSVM algorithm for detecting abnormal events in real-time video surveillance. Their algorithm combines online least-squares OCSVM (LS-OCSVM) and sparse online LS-OCSVM. The basic model is initially constructed through a learning training set with a limited number of samples. Like (Davy et al., 2006) algorithm, the model is then updated through each incoming datum using threshold-based evaluation. Recently, Anaissi et al. (Anaissi et al., 2017b) propose another approach which measures the similarity between a new event and error support vectors to generate a self-advised decision value rather than using a fixed threshold. That was an effective solution but it is susceptible to include damage samples if the model keeps updated in the same direction as the real damage samples. Then the resultant updated model will start encountering damage samples in the training data. Thus this approach will start missing the real damage events.

We employ stochastic gradient descent (SGD) algorithm to perform CP decomposition in online manner. SGD has the capability to deal with big data and online learning models. The key element for optimization problems in SGD is defined as:

where $L$ is the loss function needs to be optimized, $x$ is a data point and $w$ is a variable.

The rational idea of GSD algorithm depends only on the gradient information of $\frac{\partial L}{\partial w}$. In such a non-convex setting, this partial derivative may encounter data points with $\frac{\partial L}{\partial w}=0$ even though it is not at a global minimum. These data points are known as saddle points which may detente the optimization process to reach the desired local minimum if not escaped (Ge et al., 2015). These saddle points can be identified by studying the second-order derivative (aka Hessian) $\frac{\partial L}{\partial w}^{2}$. Theoretically, when the $\frac{\partial L}{\partial w}^{2}(x;w)\succ 0$, $x$ must be a local minimum; if $\frac{\partial L}{\partial w}^{2}(x;w)\prec 0$, then we are at a local maximum; if $\frac{\partial L}{\partial w}^{2}(x;w)$ has both positive and negative eigenvalues, the point is a saddle point. The second order-methods guarantee convergence, but the computing of Hessian matrix $H^{(t)}$ is high, which makes the method infeasible for high dimensional data and online learning. Ge et al.(Ge et al., 2015) show that saddle points are very unstable and can be escaped if we slightly perturb them with some noise. Based on this, we use the perturbation approach which adds Gaussian noise to the gradient. This reinforces the next update step to start moving away from that saddle point toward the correct direction. After a random perturbation, it is highly unlikely that the point remains in the same band and hence it can be efficiently escaped (i.e., no longer a saddle point)(Jin et al., 2017). Since we are interested in the fast optimization process due to online settings, we further incorporate Nesterov’s method into the PSGD algorithm to accelerate the convergence rate. Recently, Nesterov’s Accelerated Gradient (NAG) (Nesterov, 2013) has received much attention for solving convex optimization problems (Guan et al., 2012; Nitanda, 2014; Ghadimi and Lan, 2016). It introduces a smart variation of momentum that works slightly better than standard momentum. This technique modifies the traditional SGD by introducing velocity $\nu$ and friction $\gamma$, which tries to control the velocity and prevents overshooting the valley while allowing faster descent. Our idea behind Nesterov’s is to calculate the gradient at a next position that we know our momentum will reach it instead of calculating the gradient at the current position. In practice, it performs a simple step of gradient descent to go from $w^{(t)}$ to $w^{(t+1)}$, and then it shifts slightly further than $w^{(t+1)}$ in the direction given by $\nu^{(t-1)}$. In this setting, we model the gradient update step with NAG as follows:

where

where $\epsilon$ is a Gaussian noise, $\eta^{(t)}$ is the step size, and $||A||_{L_{1}}$ are the regularization and penalization parameter into the $L_{1}$ norms to achieve smooth representations of the outcome and thus bypassing the perturbation surrounding the local minimum problem. The updates for $(B^{(t+1)},\nu^{(B,t)})$ and $(C^{(t+1)},\nu^{(C,t)})$ are similar to the aforementioned ones. With NAG, our method achieves a global convergence rate of $O(\frac{1}{T^{2}})$ comparing to $O(\frac{1}{T})$ for traditional gradient descent. Based on the above models, we present our NeSGD algorithm 2.

In this paper, we introduce a new criterion to trigger the update process when the online OCSVM model generates a negative decision value for a new sample $c^{t+1}$. Based on the information derived from the location component matrix $B^{(t+1)}$ which we obtain when we decompose a three-way tensor data $\mathcal{X}^{t+1}$, we generate an advised decision score for a new negative datum based on the average distance from a sensing location matrix (a row in (B)) to the k nearest neighbouring (knn) locations. A big change in this score of a sensing location indicates a change in sensor behaviour which might be due to occurred damage or environmental changes. If all the knn scores behave differently, then this indicates that the negative decision value is due to environmental changes. Therefore, we add this new datum to the training data and update the model coefficients accordingly. Otherwise, we report $c_{i}^{t+1}$ as an anomaly data point. This algorithm is described as follows: given the location matrix $B^{t+1}$, the unit vector of each point $b_{j}(j=1,\ldots,n)$ with its $k$ closest points $b_{k}$ is computed as follows:

Then we estimate the change occurred in sensors behaviors based on the absolute difference between $B^{t+1}$ and $B^{t}$ using the following equation

where $\mathcal{P}_{i}$ represents the probability of that negative decision value of $c_{i}^{t+1}$ is being related to environmental changes, and $\gamma$ is a small value represents acceptable change. In this work, we set-up a 90% confidence interval for $\mathcal{P}_{i}(C^{t+1})$ to judge whether a new datum $c_{i}^{t+1}$ belongs to the healthy sample or not. In fact, this confidence interval is based on the physical layout of the sensor instrumentation. Algorithm 3 illustrates the process of generating the tensor-based advised decision values:

The model solution of OCSVM is basically composed of two coefficients denoted by $\alpha_{i}$ and $\rho$. When a new datum $c_{i}^{t+1}$ arrives with an advised decision value $a(x_{c})>0$, the model coefficients must be updated to get the new solution $\alpha_{i+c}$ and $\rho*$, which should preserve the KKT conditions (see Equation 12). We initially assign a zero value to $\alpha_{c}$ and then start looking for the largest possible increment of $\alpha_{c}$ until its $g(x_{c})$ becomes zero, in this case $x_{c}$ is added to the support vectors set $S$. If $\alpha_{c}$ equals to $1$, $x_{c}$ is added to the set of the error vectors $E$.

The difference between the two states of OCSVM is shown in the following equation:

Since $g_{i}=0$ $\forall i\in S$, we can write Equation 21 in a matrix form as follows:

By substituting $\alpha_{s}$ in the partial derivate equation 21, we obtain:

where

The goal now is to determine the index of the sample $i$ that leads to the minimum $\Delta\alpha_{c}$. As in (Cauwenberghs and Poggio, 2000), five cases must be considered to manage the migration of the sample between the three sets $S$, $E$ and $R$, and calculate $\Delta\alpha_{c}$.

1. (1)

   $\Delta\alpha_{c}^{1}=\min_{i}\frac{1-\alpha_{i}}{\beta_{i}}$, $\forall i\in S$ and $\beta_{i}>0$.
   $\hskip 28.45274pt\Delta\alpha_{c}^{1}$ leads to the minimum $\Delta\alpha_{c}$ $\rightarrow$ Move $i$ from $S$ to $E$.

2. (2)

   $\Delta\alpha_{c}^{2}=\min_{i}\frac{-\alpha_{i}}{\beta_{i}}$, $\forall i\in S$ and $\beta_{i}<0$
   $\hskip 28.45274pt\Delta\alpha_{c}^{2}$ leads to the minimum $\Delta\alpha_{c}$ $\rightarrow$ Move $i$ from $S$ to $R$.

3. (3)

   $\Delta\alpha_{c}^{3}$ = $\min_{i}\frac{-g_{i}}{\gamma_{i}}$, $\forall i\in E$ and $\gamma_{i}>0$ or $\forall i\in R$ and $\gamma_{i}<0$.
   $\hskip 28.45274pt\Delta\alpha_{c}^{3}$ leads to the minimum $\Delta\alpha_{c}$ $\rightarrow$ Move $i$ from $E$ or $R$ to $S$.

4. (4)

   $\Delta\alpha_{c}^{4}=\frac{-g_{c}}{\gamma_{c}}$, $i$ is the index of $x_{c}$.
   $\hskip 28.45274pt\Delta\alpha_{c}^{4}$ leads to the minimum $\Delta\alpha_{c}$ $\rightarrow$ Move $x_{c}$ to $S$, terminate.

5. (5)

   $\Delta\alpha_{c}^{5}=1-\alpha_{c}$, $i$ is the index of $x_{c}$.
   $\hskip 28.45274pt\Delta\alpha_{c}^{5}$ leads to the minimum $\Delta\alpha_{c}$ $\rightarrow$ Move $x_{c}$ to $E$, terminate.

The next step after the migration is to update the inverse matrix $Q^{-1}$. Two cases to consider during the update: extending $Q^{-1}$ when the determined index $i$ joins $S$, or compressing when index $i$ leaves $S$. Similar to (Laskov et al., 2006), we applied the Sherman-Morrison-Woodbury formula to obtain the new matrix $\tilde{Q}$. We repeat this procedure until the  index $i$ is related to the new example $x_{c}$.

To further validate our model, we evaluate the performance of our Tensor-based advice decision values for incremental OCSVM when it is applied to SHM. The evaluation is based on real SHM data collected from two case studies namely (a) the Infante D. Henrique Bridge in Portugal and (b) AusBridge a major Bridge in Australia (the actual Bridge name cannot be published due to a data confidentiality agreement).