Hierarchical Data Representation Model - Multi-layer NMF
Authors: Hyun-Ah Song, Soo-Young Lee
ICLR 2013

Abstract: Understanding and representing the underlying structure of feature hierarchies present in complex data in intuitively understandable manner is an important issue. In this paper, we propose a data representation model that demonstrates hierarchical feature learning using NMF with sparsity constraint. We stack simple unit algorithm into several layers to take step-by-step approach in learning. By utilizing NMF as unit algorithm, our proposed network provides intuitive understanding of the learning process. It is able to demonstrate hierarchical feature development process and also discover and represent feature hierarchies in the complex data in intuitively understandable manner. We apply hierarchical multi-layer NMF to image data and document data to demonstrate feature hierarchies present in the complex data. Furthermore, we analyze the reconstruction and classification abilities of our proposed network and prove that hierarchical feature learning approach excels performance of standard shallow network. By providing underlying feature hierarchies in complex real-world data sets, our proposed network is expected to help machines develop intelligence based on the learned relationship between concepts, and at the same time, perform better with the small number of features provided for data representation.

Hierarchical Data Representation Model -
Multi-layer NMF
Hyun Ah Song
Department of Electrical Engineering
KAIST
Daejeon, 305-701
hyunahsong@kaist.ac.kr
Soo-Young Lee
Department of Electrical Engineering
KAIST
Daejeon, 305-701
sylee@kaist.ac.kr
Abstract
In this paper, we propose a data representation model that demonstrates hierarchi-
cal feature learning using nsNMF. We extend unit algorithm into several layers.
Experiments with document and image data successfully discovered feature hier-
archies. We also prove that proposed method results in much better classiﬁcation
and reconstruction performance, especially for small number of features.
1 Introduction
In order to understand complex data, hierarchical feature extraction strategy has been used [1]. One
best known algorithm is Deep Belief Network (DBN) introduced in 2006 [2]. With the success of
training deep architectures, several variants of deep learning have been introduced [3]. Although
these multi-layered algorithms take hierarchical approaches in feature extraction and provide efﬁ-
cient solution to complex problems, they do not provide us the relationships of features in form of
hierarchies that are learned throughout the hierarchical structure.
In this paper, we propose a hierarchical data representation model, hierarchical multi-layer non-
negative matrix factorization. (Similar approach has been introduced in [4].) We extend a variant
of NMF algorithm [5], nsNMF [6] into several layers for hierarchical learning. Here, we demon-
strate intuitive feature hierarchies present in the data set by learning relationships between features
across layers. We also prove that instead of one step learning, hierarchical approach learns more
meaningful and helpful features, which leads to better distributed representations, and results in bet-
ter performance in classiﬁcation and reconstruction for small number of features, which guarantees
reduced loss of performance, even when representing data in small dimensions.
2 Non-smooth non-negative matrix factorization (nsNMF)
Proposed network is constructed by stacking nsNMF [6] into several layers. Non-smooth non-
negative matrix factorization (nsNMF) is a variant of NMF that restricts sparsity constraint. Basic
NMF decomposes non-negative input dataX into non-negativeW and H, which are features and cor-
responding coefﬁcients or data representation respectively. It aims to reduce error between original
data X and its reconstruction WH: C = 1
2 ∥X −WH∥2 = 1
2
∑m
i=1
∑n
j=1(Xij−∑l
k=1 WikHkj)2.
To apply sparsity constraint to standard NMF, a sparsity matrix S is introduced in [6]: S = (1 −
θ)I(k) + θ
kones(k).k is number of features, and θis parameter for smoothing effect, in range of 0
to 1. I(k) is identity matrix of size k x k, and ones(k) is a matrix of size k x k with all components
of 1s. We smooth a matrix by multiplying it with S. The closer θis to 1, more smoothing effect is
applied. During alternative update, we smooth H matrix by multiplying S and H during iterations
as H=SH. To compensate the loss of sparsity,W becomes sparse.
1
arXiv:1301.6316v3  [cs.LG]  18 Mar 2013
Figure 1: Concept hierarchies in Reuters. (a) Experimental results, and (b) diagram of result in (a).
3 Multi-layer architecture
The proposed hierarchical multi-layer NMF structure comprise of several layers of unit algo-
rithm. We ﬁrst train each layer separately. We process outcome of each layer H(l) to get K(l).
K(l)
kj = f
(
H(l)
kj
M(l)
kj
)
, where M(l)
kj = ∑n
j′=1
H(l)
kj′
n , f( ·) is nonlinear function, and l denotes in-
dex of layer, l = 1,2,...L. The superscript of each term denotes layer index. Processed data
representation of K(l) is used as input to next layer. Using nsNMF, K(l) is decomposed into
W(l+1) and H(l+1):K(l) ≈ W(l+1)H(l+1). Then, we use outcome of separate training as ini-
tialization, and train the whole network jointly. The cost function for joint training is described:
C = 1
2
∑m
i=1
∑n
j=1(Xij −∑l
k=1 W(1)
ik
˜H(1)
kj )2, where ˜H(l)
kj is the reconstruction of H(l)
kj, which
can be computed via back propagation of errors from the last layer to the lth layer: ˜H(L−1) ≈
M(L−1) ⊙f−1
(
W(L) ˜H(L)
)
,..., ˜H(1) ≈M(1) ⊙f−1
(
W(2) ˜H(2)
)
, where ˜H(L) = H(L). f−1(·)
is inverse nonlinear function. (more details on the actual update computation is described in Ap-
pendix A). After training until the last layer, ﬁnal data representation H(L) is acquired. This is
the activation information of complex features, which is the integration of features throughout the
layers, W(1)W(2)...W(L).
For more detailed explanation, refer to the pseudo-code for the training procedure in Appendix B.
4 Document data feature hierarchies
We applied our proposed network to document database. We used ”Reuters-21578 collection, distri-
bution 1.0”1 as database. We sorted top 10 categories from ModApte split, conducted pre-processing
of removing stop-words, and reduced dimension to 1000. There are 5786 and 2587 document sam-
ples for training data, and test data. We constructed two-layered network with number of hidden
neurons as 160.
We observed how concepts form hierarchies in document data in Figure 1 (a). First, second, and third
W(1) features contain words related to ’oil production’ (exploration, pipeline, production, industry),
’oil contract’ (contract, purchase, barrel, prices), and ’oil reﬁnery processing’ (reﬁnery, reserves,
pipeline, petroleum), respectively. These sub-class topic features are combined together and develop
into one broader topic ’oil.’ With this combination relationship of features, we can ﬁgure out that
those three seemingly independent features can be re-categorized under the same broader topic. (The
1The Reuters-21578, Distribution 1.0 test collection is available from David D. Lewis professional home
page, currently: http://www.research.att.com/∼lewis
2
Figure 2: Reconstruction error (left) and classiﬁcation rate (right) of (a) Reuters and (b) MNIST.
Figure 3: (a) Reconstruction by shallow network (ﬁrst row) and proposed network (third row),
with original input (second row). (b) Final data representation (visualized by PCA) comparison of
shallow network (middle) and proposed network (right), in comparison to raw data (left)
concept hierarchy learned in Reuters: sub-categories of ’oil production’, ’contract’, and ’reﬁnery
processing’ exist under ’oil’ category.)
Furthermore we analyzed reconstruction and classiﬁcation performance as shown in Figure 2 (a).
The proposed hierarchical feature extraction method results in much better classiﬁcation and recon-
struction, especially for small number of features, compared to extracting features at one step. This
proves the efﬁciency and effectiveness of our proposed approach in learning of features.
We also applied our network to handwritten digit image MNIST2. The ﬁnal data representation HL
displayed distinct activation patterns for samples of the different classes, as a result of successful
learning of feature hierarchy, which determines the combination of low level features in forming
of distinct class features. In Figure 2 (b), the reconstruction error and classiﬁcation performance
also demonstrate better performance of our proposed method in small number of dimensions. In
Figure 3 (a), we can observe sparser and clear reconstruction of our proposed network. The Fisher
discriminant values of ﬁnal data representation of the shallow network and our proposed network
were 0.51 and 0.61 respectively. We can infer that proposed network learns more meaningful and
helpful features so that it results in better distributed (clustered) representation of data. We can also
check this via the visualization of H(L) to 2-D domain shown in Figure 3 (b).
5 Conclusion
In this paper, we proposed a hierarchical data representation model, hierarchical multi-layer NMF
by stacking nsNMF into several layers. We demonstrated hierarchical approach in learning of the
features. There are mainly two ﬁndings of our research. Taking hierarchical learning by stack-
ing NMFs: 1.reveals intuitive feature hierarchies (subcategories) by learning feature relationships
throughout the layers, and 2.learns more meaningful features compared to one-step learning. (as a
result, our proposed method results in much better classiﬁcation and reconstruction performance,
provided small number of dimensions for data representation.) We expect our proposed method to
be applied to various types of data for discovering underlying feature hierarchies and at the same
time, maintain reconstruction and classiﬁcation performance even with small number of features for
data representation.
2Available at: http://yann.lecun.com/exdb/mnist/
3
References
[1] Bengio, Y . (2007). Learning Deep Architectures for AI. Foundations and Trends in Machine Learning, 2(1),
1-127.
[2] Hinton, G. E., Osindero, S., and Teh, Y . (2006). A fast learning algorithm for deep belief nets. Neural
Computation, 18, 1527-1554.
[3] Bengio, Y ., Lamblin, P., Popovici, D., and Larochelle, H. (2007). Greedy Layer-Wise Training of Deep
Networks. NIPS,153-160.
[4] Ahn, J., Choi, S., Oh, J. (2004). A Multiplicative Up-Propagation Algorithm. Proceedings of the 21st
International Conference on Machine Learning.
[5] Lee, D. D., and Seung, H. S. (1999). Learning the parts of objects by non-negative matrix factorization.
Nature, 401, 788-791.
[6] Pascual-Montano, A., Carazo, J. M., Kochi, K., Lehmann, D., and Pascual-Marqui, R. D. (2006). Non-
Smooth Nonnegative Matrix Factorization (nsNMF). IEEE Trans. Pattern Anal. Machine Intell, 403-415.
4
A Appendix: Actual update computation
Continued from Section 3, the actual computation is done as described in (1).
W(l)
ik ←W(l)
ik
(
Nu(l) ˜H(l)T
)
ik(
De(l) ˜H(l)T
)
ik
, andH(l)
kj ←H(l)
kj
(
W(l)T
Nu(l)
)
kj(
W(l)T
De(l))
kj
, where (1a)
Nu(l) =
{
X if l = 1(
W(l−1)T
Nu(l−1)
)
⊙
(
M(l−1)f−1′(
W(l)H(l)
))
otherwise (1b)
De(l) =
{˜X if l = 1(
W(l−1)T
De(l−1)
)
⊙
(
M(l−1)f−1′(
W(l)H(l)
))
otherwise (1c)
Here, ˜X = W(1) ˜H(1). ˜H(l)
kj is the reconstruction of H(l)
kj , which can be computed via back propagation of
errors from the last layer to the lth layer as shown in (2).
˜H(l) =
{H(l) if l = L
M(l) ⊙f−1
(
W(l+1) ˜H(l+1)
)
if l = L −1, ...,1 (2)
M(l) is a matrix of column-wise mean of H(l), and f−1(·) is inverse nonlinear function.
5
B Appendix: Pseudo-code for training procedure of proposed network
%% Separate training of layers in extending mode
for l = 1 :L do
Randomly initialize W(l) and H(l)
if l = 1then
K(l−1) = X
end if
for iteration = 1 : (untilconvergence) do
W(l)
ik ←W(l)
ik
(K(l−1)H(l)T
)ik
(W(l)H(l)H(l)T )ik
H(l)
kj ←H(l)
kj
(W(l)T
K(l−1))kj
(W(l)T W(l)H(l))kj
end for
M(l)
kj = ∑n
j′=1 H(l)
kj′/n
K(l)
kj = f
(
H(l)
kj
M(l)
kj
)
end for
%% Joint training the whole network
Use W(l) and H(l), and use M(l) acquired from above
for iteration = 1 : (untilconvergence) do
for l = 1 :L do
if l = L then
˜H(l) = H(l)
else
˜H(l) = M(l) ⊙f−1
(
W(l+1) ˜H(l+1)
)
which can be written in full length as:
˜H(l) = M(l) ⊙f−1(W(l+1)(M(l+1) ⊙f−1(W(l+2)(...(M(L−1) ⊙f−1(W(L)H(L))))))
end if
if l = 1then
Nu(l) = X
De(l) = ˜X
which can be written in full length as:
˜X = W(1) ˜H(1) = W(1)(M(1) ⊙f−1(W(2)(M(2) ⊙f−1(W(3)(...
M(L−1) ⊙f−1(W(L)H(L)))))))
else
Nu(l) =
(
W(l−1)T
Nu(l−1)
)
⊙
(
M(l−1)f−1′(
W(l)H(l)
))
De(l) =
(
W(l−1)T
De(l−1)
)
⊙
(
M(l−1)f−1′(
W(l)H(l)
))
end if
W(l)
ik ←W(l)
ik
(
Nu(l) ˜H(l)T
)
ik(
De(l) ˜H(l)T
)
ik
H(l)
kj ←H(l)
kj
(
W(l)T
Nu(l)
)
kj(
W(l)T De(l)
)
kj
end for
end for
6


Peer review:
[Review]:
The paper proposes to stack NMF models on top of each other. At each level, a non-linear function of normalized decomposition coefficients is used and decomposed using another NMF.

This is essentially an instance of a deep belief network, where the unsupervised learning part is done using NMF, which, to the best of my knowledge had not been done before.

The new method is then applied to document data where a hierarchy of topics seems to be discovered. Applications are also shown on reconstructing digits.

The extended abstract however does not give many details on all the specifics of the method.

Comments:
-It would have been nice (a) to relate the hierachy to existing topic models [A,B], and (b) to see more topics.
-On Figure 2, why are reconstruction errors decreasing with the number of features? 
-On the digits, the differences between shallow and deep networks are not clear.

[A] D. Blei, T. Griffiths, and M. Jordan.   The nested Chinese restaurant process and Bayesian nonparametric inference of topic hierarchies.   Journal of the ACM, 57:2 1–30, 2010.  

[B] R. Jenatton, J. Mairal, G. Obozinski, F. Bach. Proximal Methods for Hierarchical Sparse Coding. Journal of Machine Learning Research, 12, 2297-2334, 2011.

Pros:
-Interesting idea of stacking NMFs.

Cons:
-Experimental results are interesting but not great. What is exactly achieved is not clear.