Icke-negativ matrisfaktorisering (NMF) är problemet med sönderdelning av en given icke-negativ n × m-matris M till en produkt av en icke-negativ n × d-matris W och en icke-negativ d × m-matris H. Begränsad NMF kräver dessutom att kolumnutrymmena för M och W sammanfaller. Att hitta den minimala inre dimensionen d är känt för att vara NP-hård, både för NMF och begränsad NMF. Vi visar att begränsad NMF är nära relaterat till en fråga om karaktären av minimal probabilistic automata, som poserades av Paz i hans seminal 1971 lärobok. Vi använder detta samband för att besvara Paz fråga negativt och på så sätt förfalska ett positivt svar som påstods 1974. Dessutom undersöker vi om en rationell matris M alltid har en begränsad NMF av minimal inre dimension vars faktorer W och H också är rationella. Vi visar att detta håller för matriser M av rank högst 3 och vi uppvisar en rank-4 matris som W och H kräver irrationella poster.  ACM Subject Classification Nonnegative matris factorization (NMF) är uppgiften att faktorisera en matris av ickenegativa reella tal M (därför en icke-negativ matris) som en produkt M = W · H sådan att matriserna W och H också är icke-negativa. Den minsta inre dimensionen av någon sådan faktorisering kallas den icke-negativa rangen av M, skriftlig rank + (M ). Inom maskininlärning populariserades NMF av Lee och Seung [14] som ett verktyg för att hitta funktioner i ansiktsbildsdatabaser. Sedan dess har NMF funnit ett brett spektrum av tillämpningar, inklusive dokumentklustring, ämnesmodellering, datorseende, rekommendationssystem, bioinformatik och akustisk signalbehandling [5, 4, 7, 19, 21, 22]. I tillämpningar kan matris M normalt ses som en matris av datapunkter: varje kolumn M motsvarar en datapunkt och varje rad en funktion. Därefter, beräkning av en icke-negativ faktorisering M = W · H motsvarar att uttrycka datapunkter (kolumner av M ) som konvexa kombinationer av latenta faktorer (kolumner av W ), dvs linjära kombinationer av latenta faktorer med icke-negativa koefficienter (kolumner av H). * Nuvarande adress: Institutionen för datavetenskap, University of Oxford, UK. 43rd International Colloquium on Automata, Languages, and Programmering (ICALP 2016 Ur ett beräkningsperspektiv, kanske det mest grundläggande problemet med NMF är om en given icke-negativ matris av rationella tal M medger en NMF med inre dimension som mest ett givet antal k. Formellt frågar NMF problemet om rank + (M ) ≤ k. I praktiska tillämpningar, olika heuristik och lokala-sök algoritmer används för att beräkna en ungefärlig icke-negativ faktorisering, men lite är känt i termer av sina teoretiska garantier. NMF-problemet under det separata antagandet av Donoho och Stodden [9] är dragbart: en NMF M = W · H kallas separat om varje kolumn av W också är en kolumn av M. År 2012, Arora et al. [2] visade att det är decidable i polynomial tid om en given matris medger en separat NMF med en given inre dimension. Ytterligare framsteg gjordes nyligen, med flera effektiva algoritmer för beräkning nära-separata NMFs [13, 12]. Vavasis [20] visade att problemet med att avgöra om rankningen av en icke-negativ matris är lika med dess icke-negativa rank är NP-hård. Detta resultat innebär att generaliseringar av detta problem, såsom ovannämnda NMF-problem, problemet med att beräkna faktorerna W, H (i både exakta och ungefärliga versioner), och icke-negativa rankning, är också NP-hård. Det är inte känt om något av dessa problem finns i NP. Vavasis [20] konstaterar att svårigheten att bevisa medlemskap i NP ligger i det faktum att ett certifikat för ett positivt svar på NMF-problemet verkar kräva de önskade faktorerna: ett par icke-negativa matriser W, H sådan att M = W · H. Relaterat till detta, Cohen och Rothblum [8] ställde frågan om det, med tanke på en icke-negativ matris av rationella tal M, alltid finns en NMF M = W · H av inre dimension lika med rank + (M ) så att både W och H är också matriser av rationella tal. En naturlig väg till att bevisa medlemskap i NMF-problemet i NP skulle vara att ge ett positivt svar på frågan om Cohen och Rothblum (samt ett polynom som är bundet till bitlängden av faktorerna W och H). Frågan är dock fortfarande öppen. För närvarande är den bästa komplexiteten bundet till NMF-problemet medlemskap i PSPACE, vilket uppnås genom översättning till existentiella teorin om verkligt slutna fält [2]. En sådan översättning visar att man alltid kan välja poster i W och H för att vara algebraiska tal. I detta arbete fokuserar vi på det så kallade begränsade NMF (RNMF) problemet, som infördes av Gillis och Glineur [11]. RNMF-problemet definieras som NMF-problemet, förutom att kolumnrymderna för M och W måste sammanfalla. (Observera att för alla NMF, kolumnen utrymme av M är en subrymd av kolumnen utrymme av W.) Detta problem har en naturlig geometrisk tolkning som den nästade polytop problem (NPP): problemet med att hitta en minimal-vertex polytop häckade mellan två givna konvexa polytoper. Mer i detalj, för en rank-r matris M, att hitta en RNMF med inre dimension d är känd för att exakt motsvara att hitta en häckad polytop med d hörn i en (r − 1)-dimensionell NPP. Våra bidrag är som följer. Vi etablerar en tät koppling mellan NMF och täckningsförhållandet i märkta Markov-kedjor (LMCs). (i, j) e inträde. Kolumnrymden (sp., radutrymme) av M, skriven Col(M ) (sp., Rad(M )), är vektorrymden spänns av kolumnerna (sp., rader) av M. En matris kallas nonnegative (sp., noll eller rationell) om så är alla dess poster. En icke-negativ matris är kolumn-stokastisk (sp., rad-stokastisk) om elementet summan av var och en av sina kolumner (sp., rader) är en. Låt F vara en beställd fält, såsom reals R eller rationella Q. Eftersom en icke-negativ matris M  på F sådan att M är lika med deras summa. Den icke-negativa rangen över R kommer hädanefter helt enkelt att kallas icke-negativ rank, och kommer att betecknas med rank + (M ). För alla icke-negativa matris M  på R n×m +, Det är lätt att se att rank, Genom att ta bort noll kolumner av M och dividera varje återstående kolumn med summan av dess element, Vi får en kolumn-stokastisk matris M med lika icke-negativa rank. På samma sätt, om M = W · H sedan efter att ha avlägsnat nollkolonner i W och multiplicerat med en lämplig diagonal matris D, H är kolumn-stokastisk också. Utan förlust av allmängiltighet kan man därför betrakta NMF:er av kolonn-stokastiska matriser till kolonn-stokastiska matriser [8, Theorem 3.2]. NMF-problemet är NP-hård, även för k = rank(M ) (se [20] ). Å andra sidan är det reducerbart för den existentiella teorin om reals, alltså genom [6, 16] det är i PSPACE. För en matris M  på Q n×m +, dess icke-negativa rank över Q är tydligt minst rank + (M ). Medan dessa led är lika om rank(M ) ≤ 2, en långvarig öppen fråga av Cohen och Rothblum frågar om de alltid är lika [8]. Med andra ord är det tänkbart att det finns en rationell matris M  på Q n×m + med rank + (M ) = d som inte har någon rationell NMF med inre dimension d. Nyligen visade Shitov [17] en icke-negativ matris (med irrationella poster) vars icke-negativa rang över ett delfält av R skiljer sig från dess icke-negativa rank över R. om rank(M ) = rank(W ). Som vi vet Col(M )  och Col(W ) innehar för alla NMF fall, är villkoret rank(M ) = rank(W ) sedan motsvarande Col(M ) = Col(W ). Den begränsade icke-negativa rankning över F av M är det minsta antalet d N 0 sådan att det finns en d-dimensionell begränsad icke-negativ faktorisering över F av M. Om inte annat anges, hädanefter kommer vi att anta F = R när man talar om den begränsade icke-negativa rank av M, och betecknar den med rrank + (M ). Vi har följande grundläggande egenskaper. Med ovannämnda NP-hårdhetsresultat följer således att RNMF-problemet också är NP-hårdt och i PSPACE. För en matris M  på Q n×m +, är dess begränsade icke-negativa rank över Q klart minst rrank + (M ). Som med icke-negativ rang, i allmänhet är det inte känt om de begränsade icke-negativa leden av M över R och över Q är lika. Av [8, Theorem 4.1] och Lemma 1, är detta sant när rank(M ) ≤ 2. RNMF har följande geometriska tolkning. För en dimension N, konvex kombination av en uppsättning {v 1,. Ett set är en polytop om och endast om det är en avgränsad polyhedron. En polytop är fulldimensionell (dvs. har volym) om matrisen (A b) R n×( +1) har rang + 1. Låt S P vara en full-dimensionell polytop beskrivs av spännpunkter. Den häckade polytop problem (NPP) frågar, med tanke på A, b, S och ett antal k  på N, om det finns k punkter som spänner en polytope Q med S. En sådan polytope Q kallas häckad mellan P och S. Följande förslag visas som Theorem 1 i [11]. Förslag 2. RNMF-problemet och NPP är interreducerbara i polynom tid. Närmare bestämt är minskningarna följande. 1. Vad är det för fel på dig? Med tanke på en icke-negativ matris M  på Q n×m + av rank r, kan man beräkna i polynom tid A  på Q n× (r-1) och b på Q n sådan att P = { x  på R-1  på Ax + b ≥ 0 } är en heldimensionell polytop, och m rationella punkter som spänner över en heldimensionell polytope S  och P sådan att a) någon d-dimensionell RNMF (rationell eller irrationell) av M bestämmer d punkter som spänner över en polytope Q med S  och Q-P, och b) någon d-punkter (rationell eller irrationell) som spänner över en polytope Q med Viktigt, korrespondenserna (a) och (b) bevara rationalitet. I bilaga A beskriver vi minskningen från punkt 2 ovan och fyller därmed i en liten lucka i beviset för [11]. Med hjälp av den geometriska tolkningen av begränsad icke-negativ rank följer det lätt att vi i allmänhet kan ha rank(M ) < rank + (M ) < rrank + (M ). Låt 3D-cube NPP vara NPP instansen där den inre och yttre polytopen är standard 3D kuben, dvs, Den enda häckade polytopen är Q = P. Motsvarande begränsade NMF problem består av följande matris M  på R n×n specificerar övergångsmatriser och är sådan att σ på μ(σ) är en rad-stokastisk matris. Det intuitiva beteendet hos LMC M är följande: När M är i tillstånd i  på [n], det avger etikett σ och flyttar till state j, med sannolikhet μ(σ) i,j. Vi utökar funktionen μ till ord genom att definiera μ(ε) := I n och μ(σ 1...., det avger w och flyttar till tillstånd j i steg, med sannolikhet μ(w) i, j. För i... [n] och w... *, vi skriver pr för sannolikheten att, med början i tillstånd i, M avger ord w. Till exempel, i figur 1 vi har pr Mer allmänt, för en given första distribution π på uppsättningen stater [n] (ses som en stokastisk rad vektor), vi skriver pr (n) för sannolikheten att M avger ord w med början från tillstånd distribution π. Vi utelämnar överskriften M från pr LMCs kan ses som ett specialfall av stokastiska sekventiella maskiner, en klass av probabilistic automata infördes och studerades av Paz [15]. Mer specifikt, de är stokastiska sekventiella maskiner med en singleton ingång alfabet och  och som utgång alfabet. Om vi antar Proposition 6 kan vi bevisa Theorem 5: 6×8 vara matrisen från Exempel 3. Låt M = (10,  på, μ) vara den associerade LMC från Proposition 6. Eftersom M = I 6 · M är en NMF med inre dimension 6, genom Proposition 6 (a) finns det en LMC M = (8,  på, μ ) med M ≥ M. Mot en motsägelse, anta att svaret på fråga 4 var ja. Då M också omfattas av några n * -state LMC M *, där n * ≤ 9, sådana att M * och M har samma rang. Den sista meningen i Proposition 6 innebär då att rrank + (M ) ≤ 7. Men detta motsäger jämlikheten rrank + (M ) = 8 från Exempel 3. Svaret på fråga 4 är därför nej. För att bevisa Proposition 6 anpassar vi en minskning från NMF till problemet med spårraffinering i Markovs beslutsprocesser [10]. Bevis skiss av Proposition 6. Låt M  på Q n×m + vara en icke-negativ matris av rank r. Som hävdas i Avsnitt 2.1, utan förlust av generalitet kan vi anta att M är kolumn-stokastisk och överväga faktoriseringar av M i kolumn-stokastiska matriser endast. Vi definierar en LMC M = (m + 2,  och μ) med m + 2 tillstånd {0, 1,..., m, m + 1}. Alfabetet är = {a 1,. ..................................................................................................... .., b n } { } och funktionen μ, för alla i... [m] och alla j... [n], definieras av: och alla andra poster av μ(a i ), μ(b j ), och μ( ) är 0. Se figur 1 för ett exempel. Vi har: och alla andra poster av μ (a i ), μ (b j ), och μ ( ) är 0. Från NMF M = W · H det följer att vi kan faktor tillbaka M så här: där den vänstra faktorn är rad-stokastisk (som H är kolumn-stokastisk), och den högra faktorn är Back M. Det följer att M ≥ M. I detta avsnitt anser vi rationella matriser av rang högst 3. Vi visar att för sådana matriser de begränsade icke-negativa leden över R och Q är lika och vi ger en polynom-tid algoritm som beräknar en minimal-dimension RNMF över Q.  Med hjälp av reduktion 1 av Proposition 2, kan vi minska i polynom tid RNMF problemet för rank-3 matriser till den 2-dimensionella NPP, dvs., bo polygon problem i planet. Som påpekas i avsnitt 2.2 bevarar överensstämmelsen mellan begränsade icke-negativa faktoriseringar och nästlade polygoner rationaliteten. Således för att bevisa Theorem 7 räcker det att bevisa: Theorem 8. Eftersom polygoner S  med rationella hörn finns det ett minimumvertex polygon Q inbäddat mellan P och S som också har rationella hörn. Dessutom finns det en algoritm som, med tanke på P och S, beräknar en sådan polygon i polynom tid i Turing maskinmodellen. Aggarwal m.fl. [1] ge en algoritm för det 2-dimensionella NPP och visa att det körs i polynom tid i RAM-modellen med enhetskostnad aritmetisk. De använder dock fritt trigonometriska funktioner och tar inte upp rationaliteten i algoritmens utgång och inte heller dess komplexitet i Turing-modellen. För att bevisa Theorem 8 visar vi att algoritmen i [1], genom att anta en lämplig representation av hörnen av en inhägnad polygon, kan anpassas så att den löper i polynom tid i Turing modellen. Vi använder dessutom denna representation för att bevisa att den minimal-vertex häckade polygon som identifieras av den resulterande algoritmen har rationella hörn. Resten av sektionen ägnas åt beviset för Theorem 8. Vi minns först lite terminologi från [1] och beskriver deras algoritm. En stödjande linje segment är en riktad linje segment, med sina inledande och sista punkter på gränsen till den yttre polygon P, som berör den inre polygon S till vänster. En häckad polygon med hörn på gränsen av P sägs stödja om alla utom på de flesta av dess kanter är stödjande linjesegment. En polygon inbäddad mellan P och S kallas minimal om den har det minsta antalet hörn bland alla polygoner inbäddade mellan P och S. Det visas i [1, Lemma 4] att det alltid finns en stödjande polygon som också är minimal, och algoritmen som ges däri ger en sådan polygon. Låt k vara antalet hörn av en minimal inbäddad polygon. Eftersom en vertex v på gränsen till P, Det finns en unikt definierad stöd polygon Q v med som mest k + 1 hörn. För att bestämma Q v en beräknar de stödjande linjesegment v 1 v 2,. .., v k v k+1, där v 1 = v; se figur 2. Sedan Q v är antingen polygon med hörn v 1,. .., v k eller polygon med hörn v 1,. .., v k+1. I det första fallet är Q v minimal. Tanken bakom algoritmen [1] är att söka längs gränsen för P efter en initial vertex v sådan att Q v är minimal. Som en central ingrediens för vårt bevis på Theorem 8, väljer vi en bekväm representation av hörn av stödjande polygoner. I detta syfte antar vi att kanterna på P är orienterade moturs, och vi representerar en vertex v på en kant pq av P av den unika λ  och [0, 1] sådan att v = (1 − λ)p + λq. Vi kallar detta konvex representation av v. Liknar [1], vi associerar med varje stödjande linje segment uv en ray funktion r, så att om λ är konvex representation av u då r (λ) är konvex representation av v. Samma ray funktion gäller för stöd linje segment u v med u i ett litet tillräckligt intervall som innehåller u. I det följande, när vi säger polynom tid, menar vi polynom tid i Turing modellen. För att få en polynom tid bunden, nyckel lemma är följande: Nästa vi visar att om en sådan lösning finns, då finns det en rationell lösning, som dessutom kan beräknas i polynom tid. För detta ändamål, låt λ * Jag vara sådan att s (λ * ) ≥ 0. Om λ * är på gränsen till I, då λ *  på Q. Om λ * inte är på gränsen och inte är en isolerad lösning, då finns det en rationell lösning i dess grannskap. Slutligen, låt λ * vara en isolerad lösning inte på gränsen. Sedan, λ * är en rot av både s och dess derivata s. För varje λ I, vi har tagit derivatan av ovanstående ekvation med avseende på λ, vi får sedan s (λ * ) = s (λ * ) = 0, från (1) Begränsade NMF Kräver Irrationalitet Här visar vi att de begränsade icke-negativa leden över R och Q är i allmänhet olika. Eftersom rank(M ) = rank(W ) = 4, är NMF M = W · H begränsad. Denna RNMF har erhållits genom att, enligt Proposition 2, reducera en NPP instans, som vi nu beskriver. Figur 3 visar den yttre 3-dimensionella polytopen P med 6 sidor. Polytop P är skärningspunkten mellan följande halvrymder: y ≥ 0 (blå), z ≥ 0 (brun), x ≥ 0 (rosa), −x + figur 4 Detaljerad vy av xy-planet. Den yttre fyrsidiga är en av 6 ansikten av P, det bruna ansiktet i figur 3. Poängen s1, s2, s3 är bland de 6 poäng som spänner den inre polytopen S. Poängen q * 1, q * 2, q * 3 är bland de 5 poäng som spänner över den häckade polytopen Q. Området runt q * 1 zoomas in på höger sida. Bilden illustrerar att q * 1 inte kan flyttas vänster på x-axeln utan att öka antalet hörn av den häckade polytopen: En prickad ray från en punkt något till vänster om q * 1 dras genom s1. Dess skärningspunkt med linjen x = 1 är något under q * 2. Efter algoritmen [1], fortsätter den prickade strålen på ett liknande sätt, "plastar runt" s2 och s3, och slutar på x-axeln runt x  på 0,2, längst till vänster om utgångspunkten. Å andra sidan illustrerar den streckade raden att q * 1 kunde flyttas till höger (med tanke på bara detta ansikte). (genomskinlig front). Figuren anger också en interiör polytope S spänner med 6 poäng (svarta punkter): s 1 = ( ). I följande diskuterar vi möjliga platser av 5 punkter q 1, q 2, q 3, q 4, q 5 som spänner över en häckad polytop Q. Eftersom s 1, s 2, s 3 alla ligger på (brun) ansikte på xy-planet, men inte på en gemensam linje, minst 3 av q jag måste ligga på xy-planet. Ett liknande uttalande innehåller för s 4, s 5, s 6 och xz-planet. Så minst en q i, säger q 1, måste ligga på x-axeln. Antag en annan q i, säger q 2, ligger på x-axeln. Utan förlust av generalitet kan vi ta q 1 = (0, 0, 0) och q 2 = (1, 0, 0), eftersom alla punkter i P på x-axeln är inneslutna av dessa q 1, q 2. Figur 4 ger en detaljerad bild av xy-planet. För att bifoga s 2 måste vissa q 3, q 4, q 5 } också ligga på xy-planet och till höger om linjen som ansluter q 2 = (1, 0, 0) och s 2. För att bifoga s 3 måste några q 3, q 4, q 5 } också ligga på xy-planet och till vänster om linjen som ansluter q 1 = (0, 0, 0) och s 3. Om q och q var identiska skulle de ligga utanför P-a-motsättningen. Därför 4 poäng (nämligen q 1, q 2, q, q ) är på xy-planet. Detta lämnar bara en punkt, säger q, som inte är på xy-planet. För att bifoga s 4 (se figur 9 i tillägg D) måste punkt q ligga på xz-planet och ligga till höger om den linje som förbinder q 2 = (1, 0, 0) och s 4. För att bifoga s 6, punkt q måste ligga till vänster om linjen som ansluter q 1 = (0, 0, 0) och s 6. Därför ligger q utanför P-a-motsättningen. Därför har vi visat att bara en punkt, säger q 1, ligger på x-axeln, och två punkter förutom q 1, säger q 2, q 3, ligger på xy-planet, och två punkter förutom q 1, säger q 4, q 5, ligger på xz-planet. att x-koordinaten för q * 1 måste vara minst 2 − ε 2. Figur 5 illustrerar hur man kan bevisa samma faktum mer formellt, med hjälp av begreppet slackfunktion (se avsnitt 4): Slackfunktionen s(λ) för intervallet som innehåller 2 − 2 har en nolla vid λ = 2 − ε 2, med en teckenförändring från negativt till positivt. En inspektion av intervallen (av partitionen I från avsnitt 4) till "vänster" av 2 − ε 2 visar att ingen av motsvarande slack funktioner uppfyller (λ) ≥ 0 för λ < 2 − ε 2. På samma sätt måste x-koordinaten för q * 1 vara högst 2 − 6 Vi har visat att en optimal begränsad icke-negativ faktorisering av en rationell matris kan kräva faktorer som har irrationella poster. Ett enastående öppet problem är om samma sak gäller allmänna icke-negativa faktoriseringar. Ett svar på denna fråga kommer sannolikt att belysa frågan om huruvida den icke-negativa rangen kan beräknas i NP. Ett annat bidrag av tidningen har varit att utveckla kopplingar mellan icke-negativ matris factorization och probabilistic automata och därmed svara på en gammal fråga om den senare. Fortsätta detta samband, och nära relaterade till ovan nämnda öppna problem, kan man fråga om man, med tanke på en probabilistisk automaton med rationella övergångssannolikheter, alltid kan hitta en minimal motsvarande probabilistisk automaton som också har rationella övergångssannolikheter. Tackar. Författarna vill tacka Michael Benedikt för stimulerande diskussioner och anonyma domare för deras hjälpsamma förslag.
I REF visade vi en rationell matris vars begränsade icke-negativa led över R och Q skiljer sig.
On Restricted Nonnegative Matrix Factorization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}