CLASSLESS ASSOCIATION USING NEURAL NETWORKS
The goal of this paper is to train a model based on the relation between two instances that represent the same unknown class. This scenario is inspired by the Symbol Grounding Problem and the association learning in infants. We propose a novel model called Classless Association. It has two parallel Multilayer Perceptrons (MLP) that uses one network as a target of the other network, and vice versa. In addition, the presented model is trained based on an EM-approach, in which the output vectors are matched against a statistical distribution. We generate four classless datasets based on MNIST, where the input is two different instances of the same digit. In addition, the digits have a uniform distribution. Furthermore, our classless association model is evaluated against two scenarios: totally supervised and totally unsupervised. In the first scenario, our model reaches a good performance in terms of accuracy and the classless constraint. In the second scenario, our model reaches better results against two clustering algorithms.
1 INTRODUCTION
Infants are able to learn the binding between abstract concepts to the real world via their sensory input. For example, the abstract concept ball is binding to the visual representation of a rounded object and the auditory representation of the phonemes /b/ /a/ /l/. This scenario can be seen as the Symbol Grounding Problem (Harnad, 1990). Moreover, infants are also able to learn the association between different sensory input signals while they are still learning the binding of the abstract concepts. Several results have shown a correlation between object recognition (visual) and vocabulary acquisition (auditory) in infants (Balaban & Waxman, 1997; Asano et al., 2015). One example of this correlation is the first words that infants have learned. In that case, the words are mainly nouns, which are visible concepts, such as, dad, mom, ball, dog, cat (Gershkoff-Stowe & Smith, 2004). As a result, we can define the previous scenario in terms of a machine learning tasks. More formally, the task is defined by learning the association between two parallel streams of data that represent the same unknown class (or abstract concept). Note that this task is different from the supervised association where the data has labels. First, the semantic concept is unknown in our scenario whereas it is known in the supervised case. Second, both classifiers needs to agree on the same coding scheme for each sample pair during training. In contrast, the coding-scheme is already pre-defined before training in the supervised case. Figure 1 shows an example of the difference between a supervised association task and our scenario.
Usually, classifiers requires labeled data for training. However, the presented scenario needs an alternative training mechanism. One way is to train based on statistical distributions. Casey (1986) proposed to solve the OCR problem using language statistics for inferring form images to characters. Later on, Knight et al. (2006) applied a similar idea to machine translation. Recently, Sutskever et al. (2015) defined the Output Distribution Matching (ODM) cost function for dual autoencoders and generative networks.
In this paper, we are proposing a novel model that is trained based on the association of two input samples of the same unknown class. The presented model has two parallel Multilayer Perceptrons (MLPs) with an Expectation-Maximization (EM) (Dempster et al., 1977) training rule that matches the network output against a statistical distribution. Also, both networks agree on the same classification because one network is used as target of the other network, and vice versa. Our model has some
similarities with Siamese Networks proposed by Chopra et al. (2005). They introduced their model for supervised face verification where training is based on constraints of pairs of faces. The constraints exploit the relation of two faces that may or may not be instances of the same person. However, there are some differences to our work. First, our training rule does not have pre-defined classes before training, whereas the Siamese Network requires labeled samples. Second, our model only requires instances of the same unknown class, whereas the Siamese network requires two types of input pairs: a) instances of the same person and b) instances of two different persons. Our contributions in this paper are
• We define a novel training rule based on matching the output vectors of the presented model and a statistical distribution. Note that the output vectors are used as symbolic features similar to the Symbol Grounding Problem. Furthermore, the proposed training rule is based on an EM-approach and classified each sample based on generated pseudo-classes (Section 2.1).
• We propose a novel architecture for learning the association in the classless scenario. Moreover, the presented model uses two parallel MLPs, which require to agree on the same class for each input sample. This association is motivated by the correlation between different sensory input signals in infants development. In more detail, one network is the target of the other network, and vice versa. Also, note that our model is gradient-based and can be extended to deeper architectures (Section 2.2).
• We evaluate our classless association task against two cases: totally supervised and totally unsupervised. In this manner, we can verify the range of our results in terms of supervised and unsupervised cases since our model is neither totally supervised nor totally unsupervised. We compare against a MLP trained with labels as the supervised scenario (upper bound) and two clustering algorithms (K-means and Hierarchical Agglomerative) as the unsupervised scenario (lower bound). First, our model reaches better results than the clustering. Second, our model shows promising results with respect to the supervised scenario (Sections 3 and 4).
2 METHODOLOGY
In this paper, we are interested in the classless association task in the following scenario: two input instances x(1) and x(2) belong to the same unknown class c, where x(1) ∈ X(1) and x(2) ∈ X(2) are two disjoint sets, and the goal is to learn the output classification of x(1) and x(2) is the same c(1) = c(2), where c(1) and c(2) ∈ C is the set of possible classes. With this in mind, we present a model that has two parallel Multilayer Perceptrons (MLPs) that are trained with an EM-approach that associates both networks in the following manner: one network uses the other network as a target, and vice versa. We explain how the output vectors of the network are matched to a statistical distribution in Section 2.1 and the classless association learning is presented in Section 2.2.
2.1 STATISTICAL CONSTRAINT
One of our constraint is to train a MLP without classes. As a result, we use an alternative training rule based on matching the output vectors and a statistical distribution. For simplicity, we explain our training rule using a single MLP with one hidden layer, which is defined by
z = network(x;θ) (1)
where x ∈ Rn is the input vector, θ encodes the parameters of the MLP, and z ∈ Rc is the output vector. Moreover, the output vectors (z1, . . . ,zm) of a mini-batch of size m are matched to a target distribution (E[z1, . . . ,zm] ∼ φ ∈ Rc), e.g., uniform distribution. We have selected a uniform distribution because it is an ideal case to have a balanced dataset for any classifier. However, it is possible to extend to different distribution. We introduce a new parameter that is a weighting vector γ ∈ Rc. The intuition behind it is to guide the network based on a set of generated pseudo-classes c. These pseudo-classes can be seen as cluster indexes that group similar elements. With this in mind, we also propose an EM-training rule for learning the unknown class given a desired target distribution. We want to point out that the pseudo-classes are internal representations of the network that are independent of the labels.
The E-step obtains the current statistical distribution given the output vectors (z1, . . . ,zm) and the weighting vector (γ). In this case, an approximation of the distribution is obtained by the following equation
ẑ = 1
M M∑ i=1 power(zi,γ) (2)
where γ is the weighting vector, zi is the output vector of the network, M is the number of elements, and the function power1 is the element-wise power operation between the output vector and the weighting vector. We have used the power function because the output vectors (z1, . . . , zm) are quite similar between them at the initial state of the network, and the power function provides an initial boost for learning to separate the input samples in different pseudo-classes in the first iterations. Moreover, we can retrieve the pseudo-classes by the maximum value of the following equation
c∗ = arg maxc power(zi,γ) (3)
where c∗ is the pseudo-class, which are used in the M-step for updating the MLP weights. Also, note that the pseudo-classes are not updated in an online manner. Instead, the pseudo-classes are updated after a certain number of iterations. The reason is the network requires a number of iterations to learn the common features.
The M-step updates the weighting vector γ given the current distribution ẑ. Also, the MLP parameters (θ) are updated given the current classification given by the pseudo-classes. The cost function is the variance between the distribution and the desired statistical distribution, which is defined by
cost = (ẑ − φ)2 (4) 1We decide to use power function instead of zγi in order to simplify the index notation
where ẑ is the current statistical distribution of the output vectors, and φ is a vector that represent the desired statistical distribution, e.g. uniform distribution. Then, the weighting vector is updated via gradient descent
γ = γ − α ∗ ∇γcost (5)
where α is the learning rate and ∇γcost is the derivative w.r.t γ. Also, the MLP weights are updated via the generated pseudo-classes, which are used as targets in the backpropagation step.
In summary, we propose an EM-training rule for matching the network output vectors and a desired target statistical distribution. The E-Step generates pseudo-classes and finds an approximation of the current statistical distribution of the output vectors. The M-Step updates the MLP parameters and the weighting vector. With this in mind, we adapt the mentioned training rule for the classless association task. Figure 2 summarizes the presented EM training rule and its components.
2.2 CLASSLESS ASSOCIATION LEARNING
Our second constraint is to classify both input samples as the same class and different from the other classes. Note that the pseudo-class (Equation 3) is used as identification for each input sample and it is not related to the semantic concept or labels. The presented classless association model is trained based on a statistical constraint. Formally, the input is represented by the pair x(1) ∈ Rn1 and x(2) ∈ Rn2 where x(1) and x(2) are two different instances of the same unknown label. The classless association model has two parallel Multilayer Perceptron MLP (1) and MLP (2) with training rule that follows an EM-approach (cf. Section 2.1). Moreover, input samples are divided into several mini-batches of size m.
Initially, all input samples have random pseudo-classes c(1)i and c (2) i . The pseudo-classes have the same desired statistical distribution φ. Also, the weighting vectors γ(1) and γ(2) are initialized to one. Then each input element from the mini-batch is propagated forward to each MLP. Afterwards, an estimation of the statistical distribution for each MLP (ẑ(1) and ẑ(2)) is obtained. Furthermore, a new set of pseudo-classes (c(1)1 , . . . , c (1) m and c (2) 1 , . . . , c (2) m ) is obtained for each network. Note that this first part can be seen as an E-step from Section 2.1. We want to point out that the pseudo-classes are updated only after a number of iterations.
The second part of our association training updates the MLP parameters and the weighting vector (γ(1) and γ(2)). In this step, one network (MLP (1)) uses pseudo-classes (c(2)1 , . . . , c (2) m ) obtained from the other network (MLP (2)), and vice versa. In addition, the weighting vector is updated
between the output approximation (ẑ(1) and ẑ(2)) and the desired target distribution (φ). Figure 3 shows an overview of the presented model.
3 EXPERIMENTS
In this paper, we are interested in a simplified scenario inspired by the Symbol Grounding Problem and the association learning between sensory input signal in infants. We evaluated our model in four classless datasets that are generated from MNIST (Lecun & Cortes, 2010). The procedure of generating classless datasets from labeled datasets have been already applied in (Sutskever et al., 2015; Hsu & Kira, 2015). Each dataset has two disjoint sets input 1 and input 2. The first dataset (MNIST) has two different instances of the same digit. The second dataset (Rotated-90 MNIST) has two different instances of the same digit, and all input samples in input 2 are rotated 90 degrees. The third dataset (Inverted MNIST ) follows a similar procedures as the second dataset, but the transformation of the elements in input 2 is the invert function instead of rotation. The last dataset (Random Rotated MNIST) is more challenging because all elements in input 2 are randomly rotated between 0 and 2π. All datasets have a uniform distribution between the digits and the dataset size is 21,000 samples for training and 4,000 samples for validation and testing.
The following parameters turned out being optimal on the validation set. For the first three datasets, each internal MLP relies on two fully connected layers of 200 and 100 neurons respectively. The learning rate for the MLPs was set to start at 1.0 and was continuously decaying by half after every 1,000 iterations. We set the initial weighting vector to 1.0 and updated after every 1,000 iterations as well. Moreover, the best parameters for the fourth dataset were the same forMLP (1) and different for MLP (2), which has two fully connected layers of 400 and 150 neurons respectively and the learning rate stars at 1.2. The target distribution φ is uniform for all datasets. The decay of the learning rate (Equation 5) for the weighting vector was given by 1/(100+epoch)0.3, where epoch was the number of training iterations so far. The mini-batch size M is 5,250 sample pairs (corresponding to 25% of the training set) and the mean of the derivatives for each mini-batch is used for the back-propagation step of MLPs. Note that the mini-batch is quite big comparing with common setups. We infer from this parameter that the model requires a sample size big enough for estimating the uniform distribution and also needs to learn slower than traditional approaches. Our model was implemented in Torch.
MLP(1) MLP (2) Association Matrix (%) Purity (%)
10.9 10.9 __________Initial State
Epoch 1,000
0 1 2 3 4 5 6 7 8 9 MLP (2)
0 1 2 3 4 5 6 7 8 9 M LP (1 ) 0.7 0.6 2.4 0.4 3.0 2.2 1.0 1.4 1.2 0.6
0
2
4
6
8
10
12
14
16
18
20
24.8 22.6
Epoch 3,000
0 1 2 3 4 5 6 7 8 9 MLP (2)
0 1 2 3 4 5 6 7 8 9 M LP (1 ) 0.1 1.7 2.8 0.0 5.7 8.9 0.3 10.0 8.1 0.1
0
2
4
6
8
10
12
14
16
18
20
64.4 65.8
Epoch 49,000
0 1 2 3 4 5 6 7 8 9 MLP (2)
0 1 2 3 4 5 6 7 8 9 M LP (1 ) 9.8 8.9 9.4 9.0 9.6 9.6 9.7 9.6 9.6 9.0
0
2
4
6
8
10
12
14
16
18
20
95.5 95.6
Figure 4: Example of the presented model during classless training. In this example, there are ten pseudo-classes represented by each row of MLP (1) and MLP (2). Note that the output classification are randomly selected (not cherry picking). Initially, the pseudo-classes are assigned randomly to all input pair samples, which holds a uniform distribution (first row). Then, the classless association model slowly start learning the features and grouping similar input samples. Afterwards, the output classification of both MLPs slowly agrees during training, and the association matrix shows the relation between the occurrences of the pseudo-classes.
To determine the baseline of our classless constraint, we compared our model against two cases: totally supervised and totally unsupervised. In the supervised case, we used the same MLP parameters and training for a fair comparison. In the unsupervised scenario, we used k-means and agglomerative clustering to each set (input 1 and input 2) independently. The clustering algorithm implementation are provided by scikit-learn (Pedregosa et al., 2011).
4 RESULTS AND DISCUSSION
In this work, we have generated ten different folds for each dataset and report the average results. We introduce the Association Accuracy for measuring association, and it is defined by the following equation
Association Accuracy = 1
N N∑ i=1 1(c (1) i = c (2) i ) (6)
where the indicator function is one if c(1)i = c (2) i , zero otherwise; c (1) i and c (2) i are the pseudo-classes for MLP (1) and MLP (2), respectively, and N is the number of elements. In addition, we also reported the Purity of each set (input 1 and input 2). Purity is defined by
Purity(Ω, C) = 1 N k∑ i=1 maxj |ci ∩ gtj | (7)
where Ω = {gt1, gt2, . . . , gtj} is the set of ground-truth labels and C = {c1, c2, . . . , ck} is the set of pseudo-classes in our model or the set of cluster indexes of K-means or Hierarchical Agglomerative clustering, and N is the number of elements.
Table 1 shows the Association Accuracy between our model and the supervised association task and the Purity between our model and two clustering algorithms. First, the supervised association task performances better that the presented model. This was expected because our task is more complex in relation to the supervised scenario. However, we can infer from our results that the presented model has a good performance in terms of the classless scenario and supervised method. Second, our model not only learns the association between input samples but also finds similar elements covered under the same pseudo-class. Also, we evaluate the purity of our model and found that the performance of our model reaches better results than both clustering methods for each set (input 1 and input 2).
Figure 4 illustrates an example of the proposed learning rule. The first two columns (MLP (1) and MLP (2)) are the output classification (Equation 3) and each row represents a pseudo-class. We have randomly selected 15 output samples for each MLP (not cherry picking). Initially, the pseudo classes are random selected for each MLP. As a result, the output classification of both networks does not show any visible discriminant element and the initial purity is close to random choice (first row). After 1,000 epochs, the networks start learning some features in order to discriminate the input samples. Some groups of digits are grouped together after 3,000 epochs. For example, the first row of MLP (2) shows several digits zero, whereas MLP (1) has not yet agree on the same digit for that pseudo-class. In contrast, both MLPs have almost agree on digit one at the fifth row. Finally, the association is learned using only the statistical distribution of the input samples and each digit is represented by each pseudo-class.
Best Results
Worst Results
MLP (1) MLP (2) Association Matrix (%)
0 1 2 3 4 5 6 7 8 9 MLP (2)
0 1 2 3 4 5 6 7 8 9 M LP (1 ) 9.7 8.9 9.0 8.7 9.7 9.0 9.2 9.1 9.4 8.5
0
2
4
6
8
10
12
14
16
18
20
Purity (%)
0 1 2 3 4 5 6 7 8 9 MLP (2)
0 1 2 3 4 5 6 7 8 9 M LP (1 ) 9.7 7.9 5.1 4.5 0.0 5.1 9.2 0.0 10.3 12.8
0
2
4
6
8
10
12
14
16
18
20
95.9 95.2
72.9 59.4
Figure 5: Example of the best and worst results among all folds and datasets. It can be observed our model is able to learn to discriminate each digit (first row). However, the presented model has a limitation that two or more digits are assigned to the same pseudo-class (last row of MLP (1) and MLP (2)).
Figure 5 shows the best and worst results of our model in two cases. The first row is the best result from MNIST dataset. Each row of MLP (1) and MLP (2) represent a pseudo-class, and it can be observed that all digits are grouped together. In addition, the association matrix shows a distribution per digit close to the desired uniform distribution, and the purity of each input is close to the supervised scenario. In contrast, the second row is our worst result from Random Rotated MNIST dataset. In this example, we can observe that some digits are recognized by the same pseudo-class, for example, digit one and seven (first two rows). However, there two or more digits that are recognized by the samepseudo-class. For example, the last row shows that nine and four are merged. Our model is still able to reach better results than the unsupervised scenario.
5 CONCLUSION
In this paper, we have shown the feasibility to train a model that has two parallel MLPs under the following scenario: pairs of input samples that represent the same unknown classes. This scenario was motivated by the Symbol Grounding Problem and association learning between sensory input signal in infants development. We proposed a model based on gradients for solving the classless association. Our model has an EM-training that matches the network output against a statistical distribution and uses one network as a target of the other network, and vice versa. Our model reaches better performance than K-means and Hierarchical Agglomerative clustering. In addition, we compare the presented model against a supervised method. We find that the presented model with respect to the supervised method reaches good results because of two extra conditions in the unsupervised association: unlabeled data and agree on the same pseudo-class. We want to point out that our model was evaluated in an optimal case where the input samples are uniform distributed and the number of classes is known. However, we will explore the performance of our model if the number of classes and the statistical distrubtion are unknown. One way is to change the number of pseudo-classes. This can be seen as changing the number of clusters k in k-means. With this in mind, we are planning to do more exhaustive analysis of the learning behavior with deeper architectures. Moreover, we will work on how a small set of labeled classes affects the performance of our model (similar to semi-supervised learning). Furthermore, we are interested in replicating our findings in more complex scenarios, such as, multimodal datasets like TVGraz (Khan et al., 2009) or Wikipedia featured articles (Rasiwasia et al., 2010). Finally, our work can be applied to more classless scenarios where the data can be extracted simultaneously from different input sources at the same time. Also, transformation functions can be applied to input samples for creating the association without classes.
ACKNOWLEDGMENTS
We would like to thank Damian Borth, Christian Schulze, Jörn Hees, Tushar Karayil, and Philipp Blandfort for helpful discussions.
The paper explores a new technique for classless association, a milder unsupervised learning where we do not know the class labels exactly, but we have a prior about the examples that belong to the same class. Authors proposed a two stream architecture with two neural networks, as streams process examples from the same class simultaneously. Both streams rely on the target (pseudo classes or cluster indices) of each other, and the outputs an intermediate representation z, which is forced to match with a statistical distribution (uniform in their case). The model is trained with EM where the E step obtains the current statistical distribution given output vectors z, and M step updates the weights of the architecture given z and pseudo-classes. Experimental results on re-organized MNIST exhibits better performance compared to classical clustering algorithms (in terms of association accuracy and purity). The authors further provide comparison against a supervised method, where proposed architecture expectedly performs worse but with promising results.
The basic motivation of the architecture apparently relies on unlabeled data and agreement of the same pseudo-labels generated by two streams. But the paper is hard to follow and the motivation for the proposed architecture itself, is hidden in details. What is trying to be achieved by matching distributions and using the pseudo-targets of the each other? Perhaps the statistical distribution of the classes is assumed to be uniform but how will it extend to other priors, or even the case where we do not assume that we know the prior? The current setup needs justifications. 
What would be very interesting is to see two examples having the same class but one from MNIST, the other from Rotated-MNIST or Background-MNIST. Because it is hard to guess how different the examples in two streams. 
At the end, I feel like the authors have found a very interesting approach for classless association which can be extended to lots of many-to-one problems. This is a good catch. I would like to see the idea in the future with some extensive experiments on large scale datasets and tasks. But the current version lacks the theoretical motivations and convincing experiments. I would definitely recommend this paper to be presented in ICLR workshop.
Few more points:
Typo: Figure1. second line in the caption "that" -> "than"
Necessity of Equation 2 is not clear
Batch size M is enormous compared to classical models, there is no explanation for this
Why uniform? should be clarified (of course it is the simplest prior to pick but just a few words about it would be good for completeness)
Typo: Page 6, second paragraph line 3: "that" -> "than"