# Nonnegative Signal Decomposition with Supervision

Authors: Teng Li; Huan Chang; Jun Wu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper presents a novel algorithm to numerically decompose mixed signals in a collaborative
way, given supervision of the labels that each signal contains. The decomposition is formulated as an
optimization problem incorporating nonnegative constraint. A nonnegative data factorization solution is
presented to yield the decomposed results. It is shown that the optimization is efficient and decreases the
objective function monotonically. Such a decomposition algorithm can be applied on multilabel training
samples for pattern classification. The real-data experimental results show that the proposed algorithm
can significantly facilitate the multilabel image classification performance with weak supervision.


---

## Body

## 1. Introduction

Signal decomposition, which separates a mixed source signal into its constitutive pure components, is an important step in many practical engineering problems. For example, in image classification or speech recognition, a single training or test sample we collected usually contains multiple additive signals from several classes. The decomposition of the mixed signals can yield pure feature representations for better classes model training and recognition. Figure1 illustrates the decomposition for an image containing three object classes. From the given mixed signal on the top, we aim to derive a specific representation for each of its associated labels, which reflects a corresponding pure region in the image. The decomposed representation can be more accurate and informative for describing object categories.Figure 1
Illustration of the proposed decomposition with an example of an image: given the top image with multiple labels, from its holistic feature representation shown right to it, for each of its associated labels, we aim to derive a label-specific representation, which reflects its actual region in the image. It is more informative to model individual labels compared to the holistic representation.Unsupervised signal decomposition, for example, blind source separation in signal processing, is a fundamental problem which has been well explored in the past decades [1, 2]. Various methods have been proposed for different tasks, including Independent Component Analysis (ICA) for speech signal [3] and Null Space Pursuit (NSP) for electricity consumption and global surface temperature [4]. In image processing, a straightforward way to decompose the image representation into label-pure representations is manual labeling. It is tedious and impractical in most cases. Most conventional approaches to automatic image decomposition focused on clustering based on low-level visual cues, such as the bottom-up image segmentation in which pixels are locally grouped on the basis of their appearances [5] and the top-down image parsing in which primitives (e.g., rectangles, sketches, and edges) are correlated based on a few grammar rules [6]. However, all these methods have not taken the supervision information into consideration. In a practical case, online images from internet are usually associated with the textual labels on the webpage, which can be utilized to guide the decomposition.In this paper, we focus on the signal decomposition problem with label supervision; that is, given a set of mixed signals each with class labels it contains, we decompose each signal to the specific labels. To this aim; the fundamental principle in pattern classification is utilized that signals of the same label should be close to each other while those of different labels should be relatively separated in feature space. Based on this assumption, a novel algorithm to numerically decompose mixed signals with labels in a collaborative way is proposed. The decomposition is formulated as an optimization problem incorporating nonnegative constraint for practical consideration, due to the nonnegative property of most real-life signals. Furthermore, we present a nonnegative data factorization solution, which is shown to be efficient and can decrease the objective function monotonically. Such a decomposition can be applied on multi-label training samples for pattern classification. The real-data experimental results show that the proposed algorithm can significantly facilitate the multi-label image classification with weak supervision.


## 2. Notation

In the following, we will use these rules to facilitate presentation: for any matrixA, Ai means the ith row vector of A, its corresponding lowercase version ai means the ith column vector of A, and Aij denotes the element of A at the ith row and jth column. Throughout this paper we will also use the following notation:       N:
number of total training samples,N~:
number of valid tags in the training set,li:
label vector of theith training sample,vi:
mixed signal representation vector of theith training sample,V:
mixed signal representations of all training samples (V=[v1,v2,…,vN]),ric:
decomposed signal representation of thecth label in ith training sample,ri:
decomposed representation of theith valid tag in the full training set,R:
decomposed signal representations from all training samples (R=[r1,r2,…,rN~]),αij:
coefficient of normalizedrj vector in reconstructing vi,H:
reconstruction coefficients matrix (Hij=αji),Y:
membership matrix denoting relation between tags and samples, defined in (5).Here a label represents a class, and a tag is a specific label instance. For a specific samplei∈{1,…,N}, its signal representation can be calculated as a K-dimensional normalized vector vi with ∥vi∥1=1, where ∥·∥1 represents the ℓ1-norm operator. The labels of this sample are denoted in a vector li∈ℛC with only 0 or 1 elements:
(1)lic={1if labelcis contained in samplei,0if there is no labelcin samplei,
where C denotes the number of labels. Let a K-dimensional vector ric denote the representation of the corresponding part for the cth label in the ith sample. For a set of training samples, we collect the representations for all nonzero label instances, that is, “tag”s, and reindex as vectors {ri}, i∈{1,…,N~}, where N~ is the number of valid tags in the set obtained by N~=∑i=1N‍∑c=1C‍lic. Note that {ri} are unknown as the objective to be computed.


## 3. Problem Formulation

In this section, the above decomposition problem is solved by nonnegative data factorization. The presented solution appears to be efficient. Furthermore, the monotonic decrease of the objective function can be proved regarding the convergence properties.WithN training samples, to formulate the decomposition problem, we use such representations as follows: a matrix V=[v1,v2,…,vN] to enclose the input holistic signal representations in columns; a K×N~ matrix R=[r1,r2,…,rN~] to enclose the decomposed representations for all the tags, which are also arranged in columns, where N~ is the total number of tags in the training set. The decomposition problem formulation consists of the following two parts.(1) The first part is minimizing the error of reconstruction from the decomposed representations to the additive signal representations; that is, for alli∈{1,…,N},
(2)min∥vi-∑jrj∥2,miinifthejthtagisassociatedwiththeithsample.Considering that, in the above formulation,{rj} are not normalized, we introduce the coefficients and yield:
(3)min∥vi-∑jαijrj∥2,miinifthejthtagisassociatedwiththeithsample,whereαij represents the coefficient of rj in the reconstruction of vi. Using matrix form and an N~×N matrix H with elements Hij=αji to enclose the information of coefficients, the reconstruction error minimization can be formulated as argminR,H∥V-RH∥2.Note that a mixed holistic representation should be reconstructed only from representations of the associated labels. Therefore, some elements ofH matrix must be 0; that is,
(4)Hij=0,iftheithtagisnotassociatedwithiiiiiiiiiiiiiiiithejthsample.This information can be derived from the training labels. Here we release the0-elements constraint for H matrix and introduce a membership matrix Y:
(5)Yij={1ifriis associated tovj,0otherwise.Then the minimization problem becomes(6)argminR,H∥V-R(H•Y)∥2.Note thatY matrix will be abandoned later in the proposed solution when the 0-elements constraint for H matrix is already considered.(2) The second part is minimizing intralabel distance between the decomposed signal representations of the same label. Here we useS matrix to denote the intralabel information with
(7)Sij={1ifi≠j,riandrjcorrespond to the same label;0otherwise.To force the decomposed representations belonging to the same label to be similar to each other, we will minimize∑ij‍∥ri-rj∥2Sij (here for convenience {ri} are assumed as normalized, which will be described later), and we can derive in the matrix form
(8)∑ij∥ri-rj∥2Sij∑ij(riTri+rjTrj-2riTrj)Sij=2∑ijriTri-2∑ijriTSijrj=2Tr(RDRT)-2Tr(RSRT)=2Tr(RLRT),
where
(9)L=D-S,Dij={∑kSikifi=j,0otherwise.Representing the context among the decomposed local representations in a graph as shown in Figure2, L matrix is therefore the Laplacian matrix for the graph, based on which graph preserving energy [7] (similar to (8)) can be derived.Figure 2
An illustration showing the graph based representation which encodes the context among decomposed signals of multiple labels: each node represents the decomposed representation to be obtained for a specific tag; tags belonging to the same label are linked with edge weight 1, while edge weights between those of different labels are set to 0.Note thatR may not be normalized. When measuring distance between different {ri} in the graph based representation, we introduce Q for normalizing R. Since V is known to be normalized in column, by minimizing the reconstruction error with (6), R(H•Y) can be considered to be approximately normalized. Thus Q is designed as a diagonal matrix:
(10)Q=diag(YHTe),
where e=[1,…,1,…,1] is a N~ dimensional vector; that is,
(11)Qij={∑k‍YikHikifi=j;0otherwise.Multiplying{ri} with {Qii}, respectively, we can see that RQ can be approximately columnwise normalized. If we take into account the normalization factor Q, the second factor of the objective function minimizing intralabel distance is then yielded as
(12)minTr(RQLQTRT).Based on the above two parts, the presented decomposition problem can be formulated as a regularized nonnegative data factorization problem as(13)argminR,H∥V-R(H•Y)∥2+λTr(RQLQTRT)iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiis.t.R,H≥0,
where λ is a weight to be empirically set in the experiments. The constraints show that R and H should be nonnegative to satisfy the reconstruction assumption, since in many real applications only when the signal representations and the reconstruction coefficients are nonnegative, can the proposed decomposition be physically meaningful. The decomposed label representations R can be obtained from the fission of V by solving (13). The solution will be given in the following. In the formulation, the given V is normalized, but there is no constraint that R or H matrix should be normalized. In the following optimization process we will normalize H.


## 4. Optimizing Solution

The problem of (13) falls into the framework of nonnegative matrix factorization (NMF) [8] for its nonnegative constraints. NMF has shown its effectiveness in practical signal processing for image classification [9]. Here similar to the optimization strategy adopted in the previous work by Lee and Seung [8], we optimize the objective function of (13) in an iterative way with a multiplicative updating rule, which guarantees the non-negativity. For initialization, to get an original guess of the target decomposed representations, we initialize ric=vi•(v¯c/∑c′=1,lic′=1C‍v¯c′). Note that “•” stands for dot product in this paper, and v¯c is the average representation of cth class from training samples associated with label c.Most iterative procedures for solving high-order optimization problems transform the original intractable problem into a set of tractable subproblems and finally obtain the convergence to a local optimum. The proposed iterative procedure also follows this philosophy and optimizesH and R alternately. The proposed iteration rules can be proved to monotonically decrease the objective function value, and the theoretical proof is given in Section 5. In fact, although stationary is the necessary condition for achieving local minima, it is difficult to justify that any limit points are the stationary point. Lin [10] has slightly modified the original iterative algorithm of NMF to achieve the convergence safely. Their modification, however, will increase the computational complexity while achieving his similar performance, as reported in [10]. Therefore, in this work, we do not adopt that the modification and experiment results show that the proposed solution could usually converge to local minima. We give the iterative procedure as follows.(
1)  Optimize
H
for Given
R. For a fixed R, the objective function in (13) with respect to H can be written as
(14)F(H)=∥V-RH∥2iiiiiiiiiii+λTr(Rdiag(YHTe)Ldiag(YHTe)RT)iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiis.t.H≥0.
Let Φij be the Lagrange multiplier for constraint Hij≥0; the Lagrange factor is ∑ij‍ΦijHij=Tr(ΦH) and  the Lagrange function ℒ is
(15)ℒ=∥V-RH∥2+λTr(Rdiag(YHTe)Ldiag(YHTe)RT)ℒ=+Tr(ΦHT)ℒ=Tr(VVT)-2Tr(VHTRT)+Tr(RHHTRT)ℒ=+λTr(Rdiag(YHTe)Ldiag(YHTe)RT)ℒ=+Tr(ΦHT).The partial derivation ofℒ with respect to H is
(16)∂ℒ∂H=-2RTV+2RTRH+2λ(L(RTR))eeTHYTY+Φ,
where we have used the following deductions:
(17)O=Rdiag(YHTe)Ldiag(YHTe)RT=R(L(YHTeeTHYT))RT=∑iRi(L(YHTeeTHYT))RiT,(18)∂O∂H=∑i(LT(RiTRi))2eeTHYTY=2(L(RTR))eeTHYTY.Using the KarushKuhnTucker (KKT) condition [11] ΦijHij=0, from (16), the following equations can be obtained for Hij:
(19)-(RTV)ijHij+(RTRH)ijHij+λ((L·(RTR))eeTHYTY)ijHij=-(RTV)ijHij+(RTRH)ijHij+λ((D(RTR))eeTHYTY)ijHij-λ((S(RTR))eeTHYTY)ijHij=0,
which leads to the update rule
(20)Hij⟵Hij[RTV+λ((S(RTR))eeTHYTY)]ij[RTRH+λ((D(RTR))eeTHYTY)]ij.Remember thatHij(t)=0 if Yij=0, where t means the tth iteration. Note that it could be satisfied by initializing Hij(0)=0 if Yij=0; therefore Y actually can be neglected without any influence. It is obvious that the updated H(t+1) is still nonnegative if the matrices R and H(t) are nonnegative. After getting H(t+1), we normalize the column vectors of H(t+1) and consequently convey the norms to the basis matrix; namely,
(21)R⟵Rdiag(YHTe),(22)H⟵Hdiag(1HTe).
The above updating of R and H does not change the value of the objective function in (13).(
2)  Optimize
R
for Given Normalized
H. Then based on the normalized H in (22), the objective function in (13) with respect to R for given H can be written as
(23)F(R)=∥V-R(H•Y)∥2+λTr(RLRT)F(R)=∥V-RH∥2+λTr(RLRT).LetΨij be the Lagrange multiplier for constraint Rij≥0, the Lagrange function ℒ is
(24)ℒ=∥V-RH∥2+λTr(RLRT)+Tr(ΨRT)ℒ=Tr(VVT)-2Tr(VHTRT)+Tr(RHHTRT)ℒ=+λTr(RLRT)+Tr(ΨRT).The partial derivation ofℒ with respect to R is
(25)∂ℒ∂R=-2VHT+2RHHT+2λRL+Ψ.Using the KKT conditionΨijRij=0, from (25), we obtain the following equations for Rij:
(26)-(VHT)ijRij+(RHHT)ijRij+λ(RL)ijRij=0,
which leads to the following update rule:
(27)Rij⟵Rij(VHT+λRS)ij(RHHT+λRD)ij.


## 5. Convergence Proof of the Proposed Solution

Definition 1.
FunctionG(A,A′) is an auxiliary function for function F(A) if the conditions
(28)G(A,A′)≥F(A),G(A,A)=F(A)
are satisfied.Theorem 2.
IfG is an auxiliary function, then F is nonincreasing under the update
(29)A(t+1)=argminAG(A,A(t)),
where t means the tth iteration.


### 5.1. Convergence of the Update Rule forH

Firstly let us go back to (14) and consider one element Hab of matrix H. Using Fab to denote the part of F(H) relevant to Hab, we can get
(30)Fab′=[-2RTV+2RTRH+2λ(L(RTR))eeTHYTY]ab;Fab′′=2(RTR)aa+2λ[(L(RTR)eeT]aa(YTY)bb.The auxiliary function ofFab is designed as
(31)G(Hab,Hab(t))=Fab(Hab(t))+Fab′(Hab(t))(Hab-Hab(t))=+(RTRH)ab+λ[(D(RTR))eeTHYTY]abHabT=×(Hab-Hab(t))2.Lemma 3.
Equation (32) is an auxiliary function for Fab, the part of F(H) only relevant to Hab.Proof.
SinceG(Hab,Hab)=Fab(Hab) is obvious, we need only show that G(Hab,Hab(t))≥Fab(Hab).
To this aim, we compare the Taylor series expansion ofFab(Hab)(32)Fab(Hab)=Fab(Hab(t))+Fab′(Hab(t))(Hab-Hab(t))+Fab(Hab)l+12Fab′′(Hab-Hab(t))2
with (32) to find that G(Hab,Hab(t))≥Fab(Hab) is equivalent to
(33)(RTRH)ab+λ[(D(RTR))eeTHYTY]abHabT≥(RTR)aa+λ[(L(RTR))eeT]aa(YTY)bb,
where(34)(RTRH)ab=∑k(RTR)akHkb(t)≥(RTRH)aaHab(t),λ[(D(RTR))eeTHYTY]ab=λ∑k‍[(D(RTR))eeT]akHkb(YTY)bb≥λ[(D(RTR))eeT]aaHab(YTY)bb≥λ[((D-S)(RTR))eeT]aaHab(YTY)bb=λ[(L(RTR))eeT]aaHab(YTY)bb.
Thus, (33) holds and G(Hab,Hab(t))≥Fab(Hab).Lemma 4.
Equation (20) could be obtained by minimizing the auxiliary function G(Hab,Hab(t)).Proof.
By setting∂G(Hab,Hab(t))/∂Hab=0, we have
(35)∂G(Hab,Hab(t))∂Hab=Fab′(Hab(t))+2[RTRH+λ((D(RTR))eeTYTY)]abHab(t)×(Hab-Hab(t))=0.
Then the update rule for H in (20) can be obtained.


### 5.2. Convergence of the Update Rule forR

Let us go back to (23) and consider any element Rab of matrix R. Now Fab is used to denote the part of F(R) relevant to Rab. It is easy to check that
(36)Fab′=(-2VHT+2RHHT+2λRL)ab,Fab′′=2(HHT)bb+2λLbb.The auxiliary function ofFab is designed as
(37)G(Rab,Rab(t))=Fab(Rab(t))+Fab′(Rab(t))(Rab-Rab(t))G(Rab,Rab(t))=+(RHHT)ab+λ(RD)abRabT(Rab-Rab(t))2.Lemma 5.
Equation (37) is an auxiliary function for Fab, the part of F(R) only relevant to Rab.Proof.
SinceG(Rab,Rab)=Fab(Rab) is obvious, we need only show that G(Rab,Rab(t))≥Fab(Rab). To do this, we compare the Taylor series expansion of Fab(Rab)(38)Fab(Rab)=Fab(Rab(t))+Fab′(Rab(t))(Rab-Rab(t))Fab(Rab)=+12Fab′′(Rab-Rab(t))2
with (37), and G(Rab,Rab(t))≥Fab(Rab) is equivalent to
(39)(RHHT)ab+λ(RD)abRabT≥(HHT)bb+λLbb,
where
(40)(RHHT)ab=∑kRak(t)(HHT)kb≥Rab(t)(HHT)bb,λ(RD)ab=λ∑k‍Rak(t)Dkb≥λRab(t)Dbb≥λRab(t)(D-S)bb=λRab(t)Lbb.
Thus, (39) holds and G(Rab,Rab(t))≥Fab(Rab).Lemma 6.
Equation (27) could be obtained by minimizing the auxiliary function G(Rab,Rab(t)).Proof.
By setting∂G(Rab,Rab(t))/∂Rab=0, we can get
(41)∂G(Rab,Rab(t))∂Rab=Fab′(Rab(t))∂G(Rab,Rab(t))∂Rab=+2(RHHT+λRD)abRab(t)(Rab-Rab(t))=0.
Then the update rule for R in (27) can be obtained.


## 5.1. Convergence of the Update Rule forH

Firstly let us go back to (14) and consider one element Hab of matrix H. Using Fab to denote the part of F(H) relevant to Hab, we can get
(30)Fab′=[-2RTV+2RTRH+2λ(L(RTR))eeTHYTY]ab;Fab′′=2(RTR)aa+2λ[(L(RTR)eeT]aa(YTY)bb.The auxiliary function ofFab is designed as
(31)G(Hab,Hab(t))=Fab(Hab(t))+Fab′(Hab(t))(Hab-Hab(t))=+(RTRH)ab+λ[(D(RTR))eeTHYTY]abHabT=×(Hab-Hab(t))2.Lemma 3.
Equation (32) is an auxiliary function for Fab, the part of F(H) only relevant to Hab.Proof.
SinceG(Hab,Hab)=Fab(Hab) is obvious, we need only show that G(Hab,Hab(t))≥Fab(Hab).
To this aim, we compare the Taylor series expansion ofFab(Hab)(32)Fab(Hab)=Fab(Hab(t))+Fab′(Hab(t))(Hab-Hab(t))+Fab(Hab)l+12Fab′′(Hab-Hab(t))2
with (32) to find that G(Hab,Hab(t))≥Fab(Hab) is equivalent to
(33)(RTRH)ab+λ[(D(RTR))eeTHYTY]abHabT≥(RTR)aa+λ[(L(RTR))eeT]aa(YTY)bb,
where(34)(RTRH)ab=∑k(RTR)akHkb(t)≥(RTRH)aaHab(t),λ[(D(RTR))eeTHYTY]ab=λ∑k‍[(D(RTR))eeT]akHkb(YTY)bb≥λ[(D(RTR))eeT]aaHab(YTY)bb≥λ[((D-S)(RTR))eeT]aaHab(YTY)bb=λ[(L(RTR))eeT]aaHab(YTY)bb.
Thus, (33) holds and G(Hab,Hab(t))≥Fab(Hab).Lemma 4.
Equation (20) could be obtained by minimizing the auxiliary function G(Hab,Hab(t)).Proof.
By setting∂G(Hab,Hab(t))/∂Hab=0, we have
(35)∂G(Hab,Hab(t))∂Hab=Fab′(Hab(t))+2[RTRH+λ((D(RTR))eeTYTY)]abHab(t)×(Hab-Hab(t))=0.
Then the update rule for H in (20) can be obtained.


## 5.2. Convergence of the Update Rule forR

Let us go back to (23) and consider any element Rab of matrix R. Now Fab is used to denote the part of F(R) relevant to Rab. It is easy to check that
(36)Fab′=(-2VHT+2RHHT+2λRL)ab,Fab′′=2(HHT)bb+2λLbb.The auxiliary function ofFab is designed as
(37)G(Rab,Rab(t))=Fab(Rab(t))+Fab′(Rab(t))(Rab-Rab(t))G(Rab,Rab(t))=+(RHHT)ab+λ(RD)abRabT(Rab-Rab(t))2.Lemma 5.
Equation (37) is an auxiliary function for Fab, the part of F(R) only relevant to Rab.Proof.
SinceG(Rab,Rab)=Fab(Rab) is obvious, we need only show that G(Rab,Rab(t))≥Fab(Rab). To do this, we compare the Taylor series expansion of Fab(Rab)(38)Fab(Rab)=Fab(Rab(t))+Fab′(Rab(t))(Rab-Rab(t))Fab(Rab)=+12Fab′′(Rab-Rab(t))2
with (37), and G(Rab,Rab(t))≥Fab(Rab) is equivalent to
(39)(RHHT)ab+λ(RD)abRabT≥(HHT)bb+λLbb,
where
(40)(RHHT)ab=∑kRak(t)(HHT)kb≥Rab(t)(HHT)bb,λ(RD)ab=λ∑k‍Rak(t)Dkb≥λRab(t)Dbb≥λRab(t)(D-S)bb=λRab(t)Lbb.
Thus, (39) holds and G(Rab,Rab(t))≥Fab(Rab).Lemma 6.
Equation (27) could be obtained by minimizing the auxiliary function G(Rab,Rab(t)).Proof.
By setting∂G(Rab,Rab(t))/∂Rab=0, we can get
(41)∂G(Rab,Rab(t))∂Rab=Fab′(Rab(t))∂G(Rab,Rab(t))∂Rab=+2(RHHT+λRD)abRab(t)(Rab-Rab(t))=0.
Then the update rule for R in (27) can be obtained.


## 6. Experiment

A typical application of the proposed decomposition in real life is as follows: for a set of images related to a scene such as campus and each associated with multiple labels, we can decompose the image feature representations to pure label representations, to provide better label samples for modeling object categories, which therefore can facilitate object recognition, detection, and so on. It leads to a useful tool for automatic labeling of  online images or personal photo album. There are two main reasons that the proposed decomposition is necessary here. First, with limited training samples, it is difficult to learn good label models using the original image presentations directly without decomposition. Since each sample is a mixture of several labels and the background for each label is various, it is better to decompose the image representation to labels optimally. Second, instances of the same label related to a scene usually have short intrasubspace distance, which supports the assumption of the proposed decomposition and guarantees the effectiveness.To demonstrate a practical application of the proposed decomposition in automatic image annotation, we manually crawled images of “KAIST campus” from the Flickr photo sharing website [12], excluded the irrelevant images, and obtained 183 images (we share the data at http://rcv.kaist.ac.kr/~tengli/Teng_resource.html). They are labeled with nine concepts: “sky,” “plant (grass/tree/flower),” “water,” “ground,” “man-made (building/sign/road),” “car/bus,” “bicycle,” “person,” and “animal.” 150 images are used for training samples, which are used for class models training and can be applied to the proposed decomposition, and the rest are used for testing. Labels are highly mixed in the images.In the implementation, the images and regions are represented using the Bag-of-Words (BoW) feature [13], where the number of visual words is set as 500 in the experiments for the tradeoff of classification accuracy and computational cost, and the feature dimension is therefore 500. With the decomposed label representations from the N training images, that is, normalized R matrix, a typical classifier, support vector machine (SVM) [14] is applied to learn label models and classify the testing samples. In the experiment of multilabel image classification, we adopted the area under ROC curve (AUC) measurement [15].Table1 gives the performance comparison between the image classification adopting the proposed nonnegative signal decomposition and the classic BoW method [13]. To further examine the performance, except for the well-known SVM, we also apply a recent popular Sparse Representation Classification (SRC) [16] as the classifier. To train using the original BoW image representations without applying decomposition yield AUC as low as around 0.5, whereas, to train label models using the decomposed results, the AUCs on the test samples are 0.77 and 0.76, in combination with SVM and SRC, respectively. Figure 3 gives the multi-label classification results for some sample images of KAIST campus Flickr dataset. The results appear to be promising.Table 1
Comparison of classification performance (AUC) on the KAIST campus images.
Method
BoW + SVM
Proposed + SVM
Proposed + SRC
AUC
0.5
0.77
0.76Figure 3
Exemplar results of multilabel image classification on the KAIST campus images using the proposed decomposed training samples: corresponding regions of the correctly detected labels are marked in the images.


## 7. Conclusion

A new technique for the nonnegative signals decomposition considering the supervised additive label information has been developed in this paper, with the assumption that intralabel signals should be relatively closer to each other than interlabel signals. The nonnegative constraint makes it applicable for many practical cases. We formulated it as an optimization problem and proposed an efficient iterative solution based on nonnegative data factorization. Convergence analysis showed that the solution guarantees monotonic decrease of the objective function.



---

*Source: 620537-2013-09-26.xml*