When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?青石板街
David Donoho
Department of Statistics
Stanford University
Stanford,CA94305 donoho@stat.stanford.edu
Victoria Stodden
Department of Statistics
Stanford University
Stanford,CA94305
vcs@stat.stanford.edu
Abstract
We interpret non-negative matrix factorization geometrically,as the
problem offinding a simplicial cone which contains a cloud of data
points and which is contained in the positive orthant.We show that under
certain conditions,basically requiring that some of the data are spread
across the faces of the positive orthant,there is a unique such simpli-
cial cone.We give examples of synthetic image articulation databas
which obey the conditions;the require parated support and facto-
班尼路什么档次rial sampling.For such databas there is a generative model in terms
of‘parts’and NMF correctly identifies the‘parts’.We show that our
theoretical results are predictive of the performance of published NMF
海南岛天气code,by running the published algorithms on one of our synthetic image
articulation databas.
1Introduction
In a recent article in Nature[4],Lee and Seung propod the notion of non-negative matrix factorization(NMF)as a way tofind a t of basis functions for reprenting non-negative data.They claimed that the notion is particularly applicable to image articulation libraries made up of images showing a composite object in many articulations and pos.They suggested(in the very title of the article)that when ud in the analysis of such data,NMF wouldfind the intrinsic‘parts’underlying the object being pictured.
NMF is akin to other matrix decompositions which have been propod previously,such as positive matrix factorization(PMF)of Juvela,Lehtinen,and Paatero[3],[2]and various minimum-volume transforms ud in the analysis of remote-nsing data[1].Numerous applications of the methods have been attempted[6],[7],[9].
Despite all the literature and discussion of this method,two fundamental questions appear not to have been pod clearly,let alone answered:
•Under what assumptions is the notion of non-negative matrix factorization well-defined,for example is the factorization in some n unique?
•Under what assumptions is the factorization correct,recovering the‘right an-swer’?
In this paper,we develop a geometric view of the tting underlying NMF factorization and derive geometric conditions under which the factorization is esntially unique,so NMF makes n no matter what algorithm is being employed.We then consider tho conditions in the tting of image articulation libraries.We describe a class of image li-braries which are created by an NMF-style generative model,where different parts have parate support,and where all different combinations of parts are exhaustively sampled. Our theory shows that,in such Separable Factorial Articulation Families,non-negative fac-torization is effectively unique.In such libraries,NMF will indeed successfully‘find the parts’.We construct such a library,showing a stickfigure with four limbs going through a range of various motions,and verify that our theoretical analysis is predictive of the actual performance of the Lee and Seung algorithm on this image library.Our viewpoint also explains relations between NMF and other ideas for obtaining non-negative factorizations and explains why uniqueness and stability may fail under other conditions.
We note that Plumbley[5]has in some n already validated NMF for datats which are not only non-negative but which obey an independent components model.However, in our view,this is actually a result about independent components analysis,not NMF.For example,for the kinds of image articulation families where each part is viewed in one of many positions,the underlying exclusion principle–that a certain part can only be prent in one particular articulation–guarantees that an ICA model does not apply.And this parts-bad tting is exactly the tting for NMF envisioned by Seung and Lee.
2Non-Negative Matrix Factorization
NMF eks to decompo a non-negative n×p matrix X,where each row contains the p pixel values for one of the n images,into
X=AΨ(1) where A is n×r andΨis r×p,and both A andΨhave non-negative entries.The rows of Ψ,denoted(ψj)r j=1,are basis elements in R p and the rows of A,(αi)n i=1,belong to R r and
can be thought of as coefficient quences reprenting the images in that basis.Recalling that the rows of X,(x i),are individual images stored as row vectors,the reprentation
takes the form
作风建设提升年
x i=
r
j=1
αi jψj.
Indexing the pixels by k=1,...,p,non-negativity ofαi andψj can be written as:ψj(k)≥0,j=1,...,r,k=1,...,p;αi j≥0,j=1,...,r,i=1,...,n.(2) It is clear that as a generative model,this approach makes n;each of us can think of some admittedly very simple imaging ttings where the scene is compod out of‘standard parts’in a variety of positions,where the are reprented by theψj and each image is made by superposing some of tho‘parts’.In this tting each part is either prent or abnt,and the corresponding coefficient is thus positive or zero.An example of this kind will be given in Section4below.
What is less clear is whether,when the generative model actually holds and we generate a synthetic datat bad on that model,the NMF matrix factorization of the datat will yield underlying basis elements which have some connection to the true generative elements.In this paper we investigate t
his question and exhibit conditions under which NMF will in fact successfully recover the true generative elements.
3Geometric Interpretation of the NMF Setting
We now describe a geometric viewpoint which will help explain the issues involved. Each image in our databa of images can be thought of as a point in a p-dimensional space, who p coordinates are given by the intensity values in each of the p pixels.The fact that image data are non-negative means that every such point lies in the positive orthant P of R p.
The factorization X=AΨsays that there are vectorsψj in R p such that all the data points x i have a reprentation as non-negative linear combinations of theψj.This algebraic characterization has a geometric counterpart.
Definition.The simplicial cone generated by vectorsΦ=(φj)r j=1is
Γ=ΓΦ={x:x= jαjφj,αj≥0}.
The factorization(1)tells us geometrically that the(x i)all lie in the simplicial coneΣΨgenerated by the(ψj).
Now in general,for a given datat(x i),there will be many possible simplicial cones containing the points in that datat.Indeed,ifΓΨis a simplicial cone containing the data, andΓΦis another cone containing thefirst,so that
ΓΨ⊂ΓΦ,
then the corresponding vectorsΦ=(φj)also can furnish a reprentation of the datat (x i).Now for any simplicial cone,there can always be another cone containing it strictly, so there are an infinite number of factorizations X=AΨwith non-negative A,and various Ψwhich are nontrivially different.Hence the constraint A≥0is not enough to lead to a well-defined notion.
However,the geometric viewpoint we are developing does not so far include the positivity constraintΨ≥0on the generating vectors of the simplicial cone.Geometrically,this constraint demands that the simplicial coneΓΨlies inside the positive orthant P.Can we obtain uniqueness with this extra constraint?
Not if the data values are strictly positive,so that
X i,k≥ǫ>0∀i,k.(3) Geometrically,this condition places the data points x i well inside the interior of the p
ositive orthant P.It is then evident by visual inspection that there will be many simplicial cones containing the data.For example,P itlf is a simplicial cone,and it contains the data points.However,many other cones will also contain the data points.Indeed,forδ>0 consider the collection of vectorsΦδwith individual vectors
φδj=e j+δ1
where e j denotes the usual vector in the standard basis,and1denotes the vector of all ones.Then,forδ<ǫ,the coneΓΦδalso contains all the data points.GeometricallyΓΦδis a dilation of the positive orthant that shrinks it slightly towards the main diagonal.Since the positivity constraint(3)places all the data well inside the interior of the positive orthant, for slight enough shrinkage it will still contain the data.
It follows from the geometric-algebraic correspondence that under the strict positivity con-dition(3),there are many distinct reprentations X=AΨwhere A≥0andΨ≥0.
In short,we must look for situations where the data do not obey strict positivity in order to have uniqueness.
4An Example of Uniqueness
When we take the non-negativity constraint on the generating elements(the extreme rays of the simplicial cone)into account,it can happen that there will only be one simplicial cone containing the data.This is completely clear if the data somehow‘fill out’the positive orthant.What is perhaps surprising is that uniqueness can hold even when the data only ‘fill out’a proper subt of the positive orthant.
Here is an example of how that can occur.Consider the‘ice-cream cone’
C={x:x′1≥ p−1||x||}
where p is again the dimensionality of the dataspace.
Lemma1.There is a unique simplicial cone which both contains C and is itlf contained in the positive orthant.绿色星球
Indeed that unique cone is P itlf;no simplicial cone contained inside P contains all of C!课堂管理
To give a full proof,we introduce notions from the subject of convex duality[8].Associated with the primal domain of points x we have been dealing with so far,there is also the dual domain of linear functionalsξacting on points x viaξ′x.If we have a convex t C,its dual C∗is defined as a collection of
linear functionals which are positive on C:
C∗={ξ:ξ′x≥0∀x∈C}
The following facts are easily verified:
Lemma2.
•If K is clod and convex then(K∗)∗=K.
•The dual of a simplicial cone with p linearly independent generators,is another simplicial cone with p generators.
•The positive orthant is lf-dual:P∗=P.
•Duality revers t inclusion:
B⊂C=⇒C∗⊂B∗.(4) We also need
Definition.Given a pointt(x i),its conical hull is the simplicial hull generated by the vectors(x i)themlves.
Let X be the conical hull of a pointt.An abstraction of the NMF problem is:
Primal-Simplicial-Cone(r,X)Find a simplicial cone with r generators contained in P and containing X.
Consider now a problem in the dual domain,pod with reverd inclusions:
Dual-Simplicial-Cone(r,Ξ)Find a simplicial cone with r generators contained inΞand containing P.
The two problems are indeed dual:
Lemma3.Every solution to Primal-Simplicial-Cone(r,X)is dual to a solution of Dual-Simplicial-Cone(r,X∗),and vice-versa.
Proof.This is effectively the invocation of‘reversal of inclusion under duality’(4).Sup-po wefind a simplicial coneΓobeying
X⊂Γ⊂P.
Then(4)says that
P∗⊂Γ∗⊂X∗,
and so a solution to the primal solves the dual.In the other direction,if wefind a simplicial coneΓ∗obeying
P∗⊂Γ∗⊂X∗
then we have by(4)
(X∗)∗⊂(Γ∗)∗⊂(P∗)∗;
we simply apply(K∗)∗=K three times to e that a solution to the dual corresponds to a solution to the primal.QED
Our motivation in introducing duality is to e something we couldn’t in the primal:we can e that even if X is properly contained in P,there can be a unique simplicial hull for X which lies inside P.
This follows from a simple obrvation about simplicial cones contained in convex cones. Definition.An extreme ray of a convex coneΓis a ray R x={a x:a≥0}where x∈Γcannot be reprented as a proper convex combination of two points x0and x1 which belong toΓbut not R x.
For example,a simplicial cone with r linearly independent generators has r extreme rays; each ray consists of all positive multiples of one generator.
Lemma4.Suppo thatΓand G are convex cones,thatΓ⊂G⊂R r,thatΓis a simplicial cone with r generators and that G interctsΓin exactly r rays which are extreme rays of G. Then(a)the rays are also extreme rays ofΓand(b)no simplicial cone with r generators Γ′=Γcan satisfyΓ⊂Γ′⊂G.
Proof.(a)Since the rays in question are extreme rays of G,which containsΓ,they are also extreme rays ofΓ.(b)Any simplicial coneΓ′with r generators and lying‘in between’Γand G would have to also interct G in the same r rays asΓdoes.Tho r rays would also have to be extreme rays forΓ′,becau they are extreme rays for G,which by hypothesis containsΓ′.But a simplicial cone with r generators is completely determined by its r extreme rays.AsΓandΓ′have the same extreme rays,Γ=Γ′.QED
We can now prove Lemma1.Recall the cone C defined above.Its dual is
C∗={ξ:ξ′1≥||ξ||}
Note(a)that every boundary ray of C∗is extreme;and(b)that C∗intercts P∗on the n unit vectors e j.So by Lemma4,P∗uniquely solves the Dual-Simplicial-Cone(n,C∗) problem and P solves the Primal-Simplicial-Cone(n,C)problem uniquely.QED.
5Uniqueness for Separable Factorial Articulation Families
We now describe families of articulated images which have at least a few‘realistic’features, and which,becau of the relevant convex geometry,offer an esntially unique NMF. The families of images we have in mind consist of black-and-white images with P parts, each exercid systematically through A articulations.As an illustration,Figure1shows some sample images from the Swimmer datat,which depicts afigure with four moving parts(limbs),each able to exhibit four articulations(different positions).
Definition.A Separable Factorial Articulation Family is a collection X of points x obeying the rules:
[R1]Generative Model.Each image x in the databa has a reprentation
鞭成语
x=
P
q=1
A
a=1
αq,aψq,a
where the generatorsψq,a∈R p obey the non-negativity constraintψq,a≥0 along with the coefficientsαq,a≥0.We speak ofψq,a as the q’th part in the ‘a’-th articulation.
[R2]Separability.For each q,a there exists a pixel k q,a such that
ψq′,a′(k q,a)=1{a=a′,q=q′}(5)
a certain pixel associated to that pair.
[R3]Complete Factorial Sampling.The datat contains all A P images in which the P parts appear in all combinations of A
所得税公式
articulations.
Figure1:Sample images from the Swimmer databa depicting four stickfigures with four limbs;the panels illustrate different articulations of the limbs.
The Swimmer datat obeys the rules except for one disagreement:every image contains an invar
iant region(the torso).As it turns out this is of small importance.
We note that assumption[R2]forces the generatorsψq,a to be linearly independent,which forces p>A·P.Conquently,the linear span of the generators is some subspace V⊂R p. Theorem1.Given a databa obeying rules[R1]-[R3],there is a unique simplicial hull with r=A·P generators which contains all the points of the databa,and is contained in P∩V.
Since the generative model[R1]implies that a particular simplicial hull with a specific choice of r generators contains the datat,and a successful application of NMF also gives a simplicial hull with r generators containing the datat,and the theorem says the must be the same hull,in this tting NMF recovers the generative model.Formally,
