METHOD FOR PSEUDO-RECURRENT PROCESSING OF DATA USING A FEEDFORWARD NEURAL NETWORK ARCHITECTURE

[0001] The present invention relates to method for implementing a recurrent neural network algorithm.

[0002] Classification of incomplete data is an important problem in machine learning that has been previously tackled from both the biological and computational perspectives. The proposed solutions to this problem are closely tied to the literature on inference with incomplete data, generative models for classification problems and recurrent neural networks.

[0003] Recurrent Neural Networks (RNNs) are connectionist computational models that utilize distributed representation and nonlinear dynamics of its units. Information in RNNs is propagated and processed in time through the states of its hidden units, which make them appropriate tools for sequential information processing. There are two broad types of RNNs: stochastic energy based RNNs with symmetric connections, and deterministic ones with directed connections.

[0004] RNNs are known to be Turing complete computational models and universal approximators of dynamical systems. They are especially powerful tools in dealing with the long-range statistical relationships in a wide variety of applications ranging from natural language processing, to financial data analysis. Additionally, RNNs are shown to be very successful generative models for data completion tasks.

[0005] Despite their immense potential as universal computers, difficulties in training RNNs arise due to the inherent difficulty of learning long-term dependencies and convergence issues. However, recent advances suggest promising approaches in overcoming these issues, such as using better nonlinear optimizers or utilizing a reservoir of coupled oscillators. Nevertheless, RNNs remain to be computationally expensive in both the training as well as the test phases. The idea in the disclosed method of this patent is, to imitate recurrent processing in a network and exploit its power while avoiding the expensive energy minimization in training, or computationally heavy sampling in test. Generative models are used to randomly generate observable data, using the learnt probabilistic structure encoded in its hidden variables. In contrast to the discriminative models, generative models specify a joint probability distribution over the observed data and the corresponding class labels. For an example, Restricted Boltzmann Machines are generative RNN models. Mixture models are perhaps the most widely used generative tools and Expectation Maximization has become the standard technique for estimating the corresponding statistical parameters, i.e., the parameters of a mixture of subpopulations in the training data. Given the parameters of subpopulation distributions, new data can be generated through sampling methods.

[0006] Classification under incomplete data conditions is a well studied problem. Imputation is commonly used as a pre-processing tool, before the standard classification algorithms are applied. The Mixture of Factor Analyzer approach assumes multiple clusters in the data, estimates the statistical parameters of these clusters and uses them for filling-in the missing feature dimensions. Thus, in imputation stage, the missing feature values are filled-in with sampled values from a pre-computed distribution. Here, multiple imputation assumes that the data come from a mixture of distributions, and is capable of capturing variation in the data. Sampling from a mixture of factor analyzers and filling-in the data is effectively very similar to the feedback information insertion in a neural network from a higher layer of neurons onto a lower layer of neurons.

[0007] Previously, both feedforward and recurrent neural network methods were proposed for denoising of images, i.e. recovering original images from corrupted versions. Multi-layer perceptrons were trained using backpropagation for denoising tasks, as an alternative to energy based undirected recurrent neural networks Hopfield models). Recurrent neural networks were trained for denoising of images, by forming continuous attractors. A convolutional neural network was employed which takes an image as input and outputs the denoised image. The weights of the convolutional layers were learned through backpropagation of reconstruction error. Denoising was used as a means to design a better autoencoder recurrent neural network. Pseudo-likelihood and dependency network approaches solve data completion problem by learning conditional distributions that predict a data component using the rest of the components. These two approaches show similarities to the method disclosed in this patent, due to the maximum likelihood estimation approach of the missing data components, i.e. k-means clustering and imputation of cluster center. However, none of the prior art propose an iterative procedure that roots from a high level class decision at the backend of a neural network and propagates this information back into the network for choosing the optimum sample, in a maximum likelihood sense from a mixture of distributions. Patent discloses a method for imputing unknown data components in a data structure using statistical methods. Tensor factorization method is used in patent to perform multiple imputation in retail sales data. Neural network method is disclosed in patent to denoise images that are compressed and decompressed.

[0008] The object of the invention is a method for implementing a recurrent data processing. The disclosed method, based on mixture models and multiple imputation, is applied onto a specific neural network's hidden layer activities. The disclosed multiple imputation approach can be considered as a pseudo-recurrent processing in the network as if it is governed by the dynamical equations of the corresponding hidden layer activities. This framework provides a shortcut into the recurrent neural network computation, which is suitable for real-time operation. The disclosed method successfully performs classification for incomplete data in which the missing data components are completely unknown or some of the data components are largely distorted.

[0010] Recent work on feedforward networks has proven the importance of dense sampling and number of the hidden layer units. The question is how a successful feedforward network can be transformed into a computationally not so intense pseudo-recurrent one, with occlusion/incomplete data handling capability. In the disclosed method, Coates et al.'s network is adopted and modified to fill-in incomplete (occluded) visual representations (hidden layer activities). The nonlinear dynamical equations to construct the attractors in the high dimensional space are replaced with linear distance comparators. And costly sampling operations such as MCMC are replaced with averaging and binary decision operations. In Hopfield networks and Boltzmann machines, “hidden memories” are interpretations of the sensory input, and they are formed by iterative energy minimization procedures. In our algorithm, hidden memories are formed using K-means clustering and linear filtering.

[0011] In a recurrent network, the hidden layer activity at time t is given as a function (parameterized over θ) of the hidden layer activity at t−1 and the current input as

h^t=F_θh^t−1,x^t.

[0012] In leaky integration approach, t<t−1, activity is added for smoother changes,

h^t=γht−1+(1−γ)F_θ(h^t−1,x^t).

[0013] In our framework, for computational efficiency, F_θ is replaced with H^t i.e.,

h^t=γh^t−1+(1−γ)H^t,

where H^t is the cluster center, which is the minimum distance cluster center to the previous hidden layer activity h^t−1,

H^t=argmin_k(h^t−1−_γ^kH)².

[0014] Here, H is the set of the cluster centers, having K2 number of clusters for each class. The closest cluster center H^t computation is based on the previous decision on the class label using support vector machines (SVM). Therefore, the network uses its class decision to narrow down the set of candidate probability distributions for sampling hidden layer activity. Therefore, high level information is used to sample hidden layer activity that is merged with the current hidden layer activity. Repeating this procedure in a loop emulates the behavior of a dynamical system, i.e. RNN.

[0015] The disclosed method (100) comprises of, a feedforward neural network (101), training stage (200) for forming memories in hidden layers, and test stage (300) for exploiting memories in data completion tasks. In 101, network architecture is shown as that:

• • [0016] it has one hidden layer 104, which performs Analysis (103) or dimensionality expansion on the presented multi-dimensional data (102)
  • [0017] a subsequent hidden layer (106) computed by Pooling (105) the first hidden layer's activities in separate spatial regions (eg. quadrants in images)
  • [0018] an SVM mimics the output layer of the network and performs multi-class Classification (107) on Layer 2 activity, and outputs class label (108).

[0019] For details of the feedforward network method, [9] should be visited.

[0020] During the training phase, a set of data (102) with known labels are used for training classifiers (205). There are 3 stages that are introduced for pseudo-recurrent processing:

• • [0021] 4. Filter and Store (201): The first and second hidden layer activities of every training input data is low pass filtered and stored in data structures, called hidden layer memories (202):

{dot over (H)}₁={h₁¹, h₁², h₁² . . . h₁^N}, for N training examples and Layer 1.

{dot over (H)}₂={h₂¹, h₂², h₂² . . . h₂^N}, for N training examples and Layer 2.

• • [0022] 5. K-Means Clustering (203): Memory formation in an RNN through costly energy minimization is replaced with clustering. The second hidden layer activities (106) are vectorized and clustered using K-means with K2 number of clusters per class or K2*(# of Classes) number of clusters for non-class specific processing (cf. section 3.1.3). Therefore the hidden layer activities of each class are quantized into K2 bins, or the hidden layer activities of the whole data is quantized into K2*(# of Classes) number of bins. Hidden Layer 2 memory (204):

H₂^y={h₂¹, h₂², h₂³ . . . h₂^K2}, K2 cluster centers for each class y or

H₂={h₂¹, h₂², h₂³ . . . h₂^C×K2}, K2*(# of Classes) cluster centers for the whole data.

• • [0023] 6. Multi-Hypotheses SVM Training (205): In an RNN, multiple hypotheses can form and compete with each other to explain sensory data. A cascaded, multi hypotheses classification framework is constructed to imitate this feature. The training is repeated for a subset of data in order to allow multiple hypotheses of the network. This is achieved by excluding a specific single class (eg. Class 1) or a pair of classes (eg. Class 1 and Class 2), and training an SVM for the rest of the data. In the case of single class exclusion, the trained SVM can be used for supplying a second hypothesis. For example, if Class 1 is the first choice of the network that is decided by the “full SVM classifier”, the classifier trained by leaving out Class 1 data is used to give a second hypothesis. In the case of a pair of class exclusions, for example both Class 1 and Class 2 data are left out, the trained SVM gives a third hypothesis, where the first choice is Class 1 and the second choice is Class 2. This collection of classifiers is used during test, to decide which cluster centers of hidden Layer 2 activities will be used for feedback insertion. The classifier memory (206) consists of:
    • [0024] S is the SVM classifier for the first choice of the network
    • [0025] S^p is the SVM classifier for the second choice when the first choice was class p.
    • [0026] S^pq is the SVM classifier for the third choice when the first choice was class p and second q.

[0027] During test phase an unknown labeled and possibly incomplete (i.e. occluded, sub-sampled etc.) test data instance (102) is presented. The test phase has following iterative stages for recurrent processing:

• • [0028] 8. Pooling (105): Test phase starts with the algorithm provided by Coates et al. [9] and computes hidden Layer 2 activity (106) via pooling Layer 1 activity (104). For test data instance i, at time=t:

h₂^i,t=P(h₁^i,t),

• •  where P is the pooling operation (105) over hidden Layer 1 (104) activity.
  • [0029] 9. Multi-Hypotheses SVM Testing (301): First, second and third class label choices of the network are extracted using the corresponding SVM in the classifier memory (206). The multiple hypotheses (302) of the system are:

y¹=S(h₂^i,t)

• •  where S( ) is the classification operation (107) and y¹ is the class label of the first choice.

y²=S^y1(h₂^i,t) and y³=S^y1y2(h₂^i,t).

• • [0030] 10. Cluster Selection (303): For each class hypothesis, the cluster centers in the hidden Layer 2 memory (204) which are closest (Euclidian distance) to the test data hidden Layer 2 activity (106) are computed. These are hidden layer hypotheses of the network. 3 cluster centers (one for each class hypothesis) that are closest to the test data instance Layer 2 activity (106) are computed as follows:

{tilde over (h)}_2,1^i,t=argmin_k(h₂^i,t−H₂^y2,k)², the first class hypothesis cluster center,

{tilde over (h)}_2,2^i,t=argmin_k(h₂^i,t−H₂^y2,k)², the second class hypothesis cluster center,

{tilde over (h)}_2,3^i,t=argmin_k(h₂^i,t−H₂^y3,k)², and third class hypothesis cluster center.

• •  In a “winner-takes-all” configuration, the closest of the clusters (min distance to the test hidden layer activity) computed above is chosen as the Layer 2 hidden activity sample (304), and for the “average” configuration, the average of the three clusters is assigned as the sample (304):

{tilde over (h)}_2,A^i,t=argmin_m({tilde over (h)}_2,m^i,t−h₂^i,t)

• •  assigned Layer 2 sample for “winner-takes-all”.

${\tilde{h}}_{2,A}^{i,t}=\frac{1}{m}\sum _1^m\left({\tilde{h}}_{2,m}^{i,t}\right)$

• •  assigned Layer 2 sample for “average” scheme.
  •  For non-class specific configuration, instead of computing 3 closest centers for each of the class hypotheses, 3 closest clusters are computed regardless of class hypotheses. Another set of hidden Layer 2 memory (see training phase, stage 203) is used:

{tilde over (h)}_2,A^i,t=argmin_k(h₂^i,t−H₂^k)².

• • [0031] 11. Feedback (305, Layer 2): The Layer 2 sample is merged (feedback magnitude, α) with the test data instance Layer 2 activity (106), to generate hidden layer activity at time t+1

h₂^i,t+1=(h₂^i,t+α{tilde over (h)}_2,A^i,t)/(1+α).   (109)

• • [0032] 12. Layer 1 Sampling (306): The modified hidden Layer 2 activity (109) is used to compute the most similar training set data instance, using the Euclidean distance.

L^i,t=argmin_k(h₂^i,t+1−{dot over (H)}₂^k),

• •  is the index of the most similar training data. The hidden Layer 1 activity of the most similar training data is fetched from the Layer 1 memory (202), as the Layer 1 sample (307) of the network:

{tilde over (h)}_1,A^i,t={dot over (H)}₁^L.

• • [0033] 13. Feedback (308 Layer 1): The Layer 1 sample (307) is merged (feedback magnitude β) with the test data instance Layer 1 activity (104), to generate hidden layer activity at time t+1.

h₁^i,t+1=(h₁^i,t+β{tilde over (h)}_1,A^i,t)/(1+β).   (110)

• • [0034] 14.Pooling (105, second run): Modified Layer 1 activity (110) is pooled (105) to compute the most recent Layer 2 activity (111) in the iterative loop. Then, this activity is averaged (feedback ratio, τ) with previously computed Layer 2 activity (109) coming from Layer 2 feedback (305). The updated Layer 2 activity (112) with feedback is:

h₂^i,t+1:=[h₂^i,t+1+τP(h₁^i,t+1)]/(1+τ).   (309)

• •  Update rule (309) for the Layer 2 activity (112) can be rewritten using the references in FIG. 1 and text as:

(112):=[(109)+τ(111)]/[1+τ]

[0035] This procedure is repeated for multiple iterations starting from the second stage (301) and output Layer 2 activity (112). The feedback magnitude is halved at each iteration. for simulated annealing purposes.

[0036] The perspective adopted in the disclosed method binds three distinct approaches to the data generation: RNNs, mixture models and incomplete data classification. An intuitive and real-time operable method is disclosed. Imputation and mixture of factor analyzers in the disclosed method are used as a part of the pseudo-recurrent processing. In the method disclosed in this patent, a feedforward neural network makes a class decision at its output layer and selects an appropriate cluster to estimate selected model's hidden layer activities. After this sampling stage, the algorithm inserts the cluster center as if it is a feedback from a higher layer. As opposed to the case in classical imputation technique, in our network, the incomplete hidden layer activities can't be isolated due. to spatial pooling, thus it is assumed that the missing dimensions are not known a priori. Since the missing data dimensions are unknown, the sample and the test data hidden layer activities are merged in all dimensions. This procedure is repeated multiple times to emulate the feedforward-feedback iterations in an RNN. Other related concepts such as multi-hypotheses feedback and winner-takes-all are also applied. We suggest this method as a shortcut into feedback processing and a baseline for the performance of RNNs in data completion tasks.