Forskning på distribuerade maskininlärningsalgoritmer har främst fokuserat på en av två extremalgoritmer som lyder strikta konvergensbegränsningar eller algoritmer som lyder få eller inga sådana begränsningar. Vi överväger ett mellanalternativ där algoritmer optimistiskt antar att konflikter är osannolika och om konflikter uppstår ett protokoll för konfliktlösning åberopas. Vi anser att detta paradigm för "optimistisk konvergenskontroll" är särskilt lämpligt för storskaliga algoritmer för maskininlärning, särskilt i oövervakad miljö. Vi demonstrerar vår strategi inom tre problemområden: klusterbildning, funktionsinlärning och plats för onlinefaciliteter. Vi utvärderar våra metoder genom storskaliga experiment i en klusterdatormiljö. Önskan att tillämpa maskininlärning för allt större dataset har drivit maskininlärning gemenskapen att ta itu med utmaningarna med distribuerad algoritm design: partitionering och samordna beräkning över bearbetningsresurserna. I många fall, när man beräknar statistik över iid-data eller omvandlar funktioner, krävs endast beräkningsfaktorerna enligt data och samordning under aggregering. För dessa pinsamt parallella uppgifter, maskininlärning gemenskapen har anammat kartan-reduce paradigm, som ger en mall för att bygga distribuerade algoritmer som är feltoleranta, skalbara, och lätt att studera. Men i jakten på rikare modeller introducerar vi ofta statistiska beroenden som kräver mer sofistikerade algoritmer (t.ex. kollapsade Gibbs provtagning eller koordinat stigning) som utvecklades och studerades i den seriella inställningen. Eftersom dessa algoritmer iterativt omvandlar ett globalt tillstånd, kan parallellisering vara utmanande och ofta kräver frekvent och komplex samordning. Nya insatser för att distribuera dessa algoritmer kan delas in i två primära strategier. Den ömsesidiga uteslutningsmetoden, som antogs av [12] och [16], 1 arXiv:1307.8049v1 [cs.LG] 30 jul 2013 garanterar en seriellt betydande utförande som bevarar de teoretiska egenskaperna hos den seriella algoritmen men på bekostnad av parallellism och dyr låsning overhead. Alternativt, i det samordningsfria tillvägagångssättet, som föreslås av [21] och [1], processorer kommunicerar ofta utan samordning minimerar kostnaden för tvist men leder till stokasticitet, data-korruption, och kräver potentiellt komplexa analyser för att bevisa algoritmens korrekthet. I detta dokument utforskar vi ett tredje tillvägagångssätt, optimistisk konvergenskontroll (OCC) [14], som erbjuder resultatvinsterna av det samordningsfria tillvägagångssättet och samtidigt säkerställer ett seriellt genomförande och bevarar de teoretiska egenskaperna hos den seriella algoritmen. Precis som det samordningsfria tillvägagångssättet utnyttjar OCC infrekvensen av datakonrupterande operationer. I stället för att tillåta tillfällig datakorruption upptäcker OCC dock datakorruption och korrigerar beräkningen. Som en följd av detta säkerställer OCC automatiskt korrekthet, och analysen är bara nödvändig för att garantera optimal skalprestanda. Vi tillämpar OCC för distribuerad icke-parametrisk oövervakad inlärning inklusive men inte begränsat till kluster-och implementera distribuerade versioner av DP-Means Vi visar hur man analyserar OCC i samband med DP-Means algoritm och utvärdera den empiriska skalbarheten av OCC-metoden på alla tre föreslagna algoritmer. De viktigaste bidragen i detta dokument är: 1. Konkurskontroll för att distribuera oövervakade inlärningsalgoritmer. 2. Utgångspunkten är följande: Omtolkning av icke-parametrisk klustring online i form av anläggningslokalisering med approximativa garantier. 3. Vad är det som händer? Analys av optimistisk konvergenskontroll för oövervakat lärande. 4. Vad är det som händer? Applicering till funktionsmodellering och klusterbildning. Många maskininlärningsalgoritmer omvandlar iterativt något globalt tillstånd (t.ex. modellparametrar eller variabelt uppdrag) vilket ger illusionen av serieberoenden mellan varje operation. Men på grund av sparsamhet, utbytbarhet och andra symmetrier är det ofta så att många, men inte alla, av de statstransformerande operationerna kan beräknas samtidigt och samtidigt bevara serialiserbarheten: motsvarigheten till vissa serieutföranden där enskilda operationer har beställts om. Denna möjlighet till serievis konvergens utgör grunden för distribuerade databassystem. Till exempel, två kunder kan samtidigt göra inköp uttömma inventeringen av icke-relaterade produkter, men om de försöker köpa samma produkt då kan vi behöva serialisera sina inköp för att säkerställa tillräcklig inventering. En lösning (ömsesidig uteslutning) associerar lås med varje produkttyp och tvingar varje köp av samma produkt att bearbetas serievis. Detta kan fungera för en impopulär, sällsynt produkt men om vi är 2 intresserade av att sälja en populär produkt för vilken vi har en stor inventering serialiseringen overhead kan leda till onödigt långsamma svarstider. För att ta itu med detta problem har databasgemenskapen antagit optimistisk konvergenskontroll [14] där systemet försöker tillgodose kundernas önskemål utan att låsa och korrigera transaktioner som kan leda till negativ inventering (t.ex. genom att tvinga kunden att checka ut igen). Optimistisk konvergenskontroll utnyttjar situationer där de flesta operationer kan utföras samtidigt utan konflikt eller brott mot serieinvarianter i vårt program. Till exempel, med tillräcklig inventering den ordning i vilken kunderna är nöjda är oväsentlig och samtidig verksamhet kan utföras seriellt för att ge samma slutresultat. Men i den sällsynta händelse att inventeringen nästan uttöms två samtidiga inköp kanske inte seriellt eftersom inventeringen aldrig kan vara negativ. Genom att flytta kostnaden för konvergenskontroll till sällsynta händelser kan vi tillåta dyrare mekanismer för konvergenskontroll (t.ex. omräkning) i utbyte mot ett effektivt, enkelt, samordningsfritt genomförande för majoriteten av händelserna. Formellt, för att tillämpa OCC måste vi definiera en uppsättning transaktioner (dvs. operationer eller samlingar av operationer), en mekanism för att upptäcka när en transaktion kränker serialiseringsinvarianter (d.v.s. inte kan utföras samtidigt), och en metod för att korrigera (t.ex. upprullning) transaktioner som kränker serialiseringsinvarianter. Optimistisk konvergenskontroll är mest effektiv när kostnaden för att validera samtidiga transaktioner är liten och konflikter förekommer sällan. Maskininlärningsalgoritmer är idealiska för optimistisk konvergenskontroll. Den villkorliga självständighetsstrukturen och sparsamheten i våra modeller och data leder ofta till glesa parameteruppdateringar som avsevärt minskar risken för konflikter. Likaså ger symmetrin i våra modeller ofta flexibiliteten att omordna seriella operationer samtidigt som algoritminvarianter bevaras. Eftersom beroendestrukturen är kodad i modellen kan vi lätt upptäcka när en operation bryter serieinvarianter och korrigera genom att avvisa förändringen och köra om beräkningen. Alternativt kan vi utnyttja verksamhetens semantik för att lösa konflikten genom att acceptera en ändrad uppdatering. Som en följd av detta tillåter OCC oss att enkelt konstruera bevisligen korrekta och effektiva distribuerade algoritmer utan att behöva utveckla nya teoretiska verktyg för att analysera kaotisk konvergens eller icke-deterministiskt distribuerat beteende. Optimistisk konvergenskontroll kan destilleras till ett enkelt mönster (metaalgoritm) för utformning och genomförande av distribuerade maskininlärningssystem. Vi börjar med att jämnt dela upp N-datapunkter (och motsvarande beräkning) över P tillgängliga processorer. Varje processor upprätthåller en replikerad bild av det globala tillståndet och seriellt tillämpar inlärningsalgoritmen som en sekvens av operationer på dess tilldelade data och det globala tillståndet. Om en operation muterar den globala staten på ett sätt som bevarar serialiseringen invarianter så accepteras operationen lokalt och dess effekt på den globala staten, om någon, så småningom replikeras till andra processorer. Men om en operation potentiellt skulle kunna strida mot verksamheten på andra processorer skickas den till en unik serialiserande processor där den avvisas eller korrigeras och den resulterande globala statsförändringen så småningom replikeras till resten av processorn. Under tiden accepterar den ursprungliga förädlaren antingen preliminärt den statliga förändringen (om en rollbackoperatör definieras) eller fortsätter som om transaktionen har skjutits upp till någon punkt i framtiden. Även om det är möjligt att utföra detta mönster asynkront med minimal samordning, antar vi för enkelhetens skull den bulksynkrona modellen [23] och delar upp beräkningen i epoker. Inom en epok t, b datapunkter B(p, t) är jämnt fördelade på var och en av P-processorerna. Alla tillståndsförändringar eller serialiseringsoperationer överförs i slutet av epoken och bearbetas före nästa epok. Medan potentiellt långsammare än en asynkron körning, bulksynkron körning är deterministisk och kan enkelt uttryckas med hjälp av befintliga system som Hadoop eller Spark [25]. Mycket av den befintliga litteraturen om distribuerade maskininlärningsalgoritmer har fokuserat på klassificerings- och regressionsproblem, där den underliggande modellen är kontinuerlig. I detta papper använder vi OCC mönster för maskininlärning problem som har en mer diskret, combinatorial smak-i synnerhet oövervakade kluster och latent funktion inlärningsproblem. Dessa problem uppvisar symmetri via sin invariant till både data permutation och kluster eller funktion permutation. Tillsammans med det glesa samspelet mellan verksamheten i deras befintliga seriealgoritmer erbjuder dessa problem en unik möjlighet att utveckla OCC-algoritmer. Den K-means algoritmen ger ett paradigmexempel; här är det inferentiella målet att partitionera data. I stället för att enbart fokusera på K-medel har vi dock inspirerats av det senaste arbetet där en allmän familj av K-medel-liknande algoritmer har erhållits genom att ta Bayesian nonparametric (BNP) modeller baserade på kombinatoriska stokastiska processer som Dirichlet processen, betaprocessen, och hierarkiska versioner av dessa processer, och utsätta dem för små variationer asymptotik där den bakre sannolikheten under BNP-modellen omvandlas till en kostnadsfunktion som kan optimeras [4]. De algoritmer som hittills ansetts i denna litteratur har utvecklats och analyserats i den seriella inställningen; vårt mål är att utforska distribuerade algoritmer för optimering av dessa kostnadsfunktioner som bevarar strukturen och analysen av deras seriella motsvarigheter. Vi först överväga DP-means algoritm (Alg. 1) infördes genom [13]. Liksom K-means algoritm växlar DP-Means mellan att uppdatera klustertilldelningen z i för varje punkt x i och att räkna om centroiderna C = {μ k } K=1 associerad med varje kluster. DP-Means skiljer sig dock åt genom att antalet kluster inte fastställs på förhand. Istället, om avståndet från en given data pekar till 4 Algoritm 1: Serial DP-means Utgång: Godkända kluster centra C Algoritm 2: DPValidate Input: Uppsättning av föreslagna kluster centrer av utdata: Godkända kluster centra C Figur 1 : Den Serial DP-Means algoritm och distribuerat genomförande med hjälp av OCC mönster. 5 alla befintliga kluster centroider är större än en parameter λ, sedan skapas ett nytt kluster. Medan den andra fasen är trivialt parallell, processen att införa kluster i den första fasen är i sig seriell. Kluster tenderar dock att införas sällan, och därmed ger DP-Means en möjlighet för OCC. I Alg. 3 presenterar vi en OCC parallellisering av DP-Means algoritm där varje iteration av den seriella DP-Means algoritmen är uppdelad i N/(P) bulk-synkrona epoker. Datan är jämnt fördelad {x i} i-B(p,t) över processor-epocher till block av storlek b = -B(p, t)-. Under varje epok t, varje processor p utvärderar kluster medlemskap i sina tilldelade data {x i} i påb (p,t) med hjälp av klustercentra C från föregående epok och optimistiskt föreslår en ny uppsättning kluster centra. Vid slutet av varje epok är de föreslagna klustercentren serievaliderade med hjälp av Alg. 2. Utgångspunkten är följande: Valideringsprocessen accepterar kluster centra som inte omfattas av (dvs. inte inom λ av) redan accepterade kluster centra. När ett klustercenter förkastas uppdaterar vi dess referens till peka på det redan accepterade centrum, vilket korrigerar den ursprungliga punkttilldelningen. DP-Means mål visar sig vara likvärdigt med den klassiska anläggningen Location (FL) mål: som väljer uppsättningen kluster centra (facilities) μ  på C som minimerar det kortaste avståndet x − μ till varje punkt (kund) x samt den bestraffade kostnaden för kluster λ 2  på C. Samtidigt som DP-Means gör det möjligt för kluster att vara godtyckliga punkter (t.ex., C  till R D ), FL begränsar kluster att vara punkter C  på en uppsättning kandidat platser F. Därför får vi en länk mellan combinatorial Bayesian modeller och FL gör att vi kan tillämpa algoritmer med kända approximations gränser till Bayesian inspirerade icke-parametriska modeller. Som vi kommer att se i Avsnitt 3, vår OCC algoritm ger konstant-faktor approximationer för både FL och DP-medel. Anläggningens läge har studerats intensivt. Vi bygger på algoritmen online anläggning (OFL) som beskrivs av Meyerson [17]. OFL-algoritmen behandlar varje datapunkt x seriellt i ett enda pass genom att antingen lägga till x i uppsättningen kluster med sannolikhet min(1, min μ skaC x − μ 2 /λ 2 ) eller tilldela x till närmaste befintliga kluster. Med hjälp av OCC kan vi konstruera en distribuerad OFR-algoritm (Alg. 4) som är nästan identisk med OCC DP-Means algoritm (Alg. 3) men som ger starka approximationsbegränsningar. OCC OFL-algoritmen skiljer sig endast åt genom att kluster införs och valideras stochastically valideringsprocessen säkerställer att de nya klusteren accepteras med sannolikhet lika med den seriealgoritmen. BP-medel är en algoritm för att lära sig samlingar av latent binära funktioner, vilket ger ett sätt att definiera grupperingar av datapunkter som inte behöver vara ömsesidigt 6 Algoritm 4: Parallellt OCL Input: Samma som DP-Means Utgång: Godkända kluster centra C Input: Uppsättning av föreslagna kluster centrers utgång: Godkända kluster centra C Figur 2: OCC algoritm för Online Facility Plats (OFL). Exklusiva eller uttömmande liknande kluster. Som med serie-DP-medel finns det två faser i serie-BP-medel (Alg. 7) och av följande skäl: I den första fasen är varje datapunkt x i märkt med binära uppdrag från en samling funktioner (z ik = 0 om x i inte hör till funktionen k; annars z ik = 1) för att skapa en representation x i. k z ik f k. I den andra fasen, parametervärden (funktionen betyder f k) uppdateras baserat på uppdragen. I det första steget ingår också möjligheten att införa ytterligare ett inslag. Medan den andra fasen är trivialt parallell, den inneboende seriella karaktären av den första fasen i kombination med sällan införande av nya funktioner pekar på nyttan av OCC på detta område. OCC-parallaliseringen för BP-medelvärden följer samma grundläggande struktur som OCC DP-medelvärden. Varje transaktion fungerar på en datapunkt x i i två faser. I den första analysfasen finns den optimala representationen k z ik f k. Om x i inte är väl representerad (dvs. x i − k z ik f k > λ), föreslås skillnaden som en ny funktion i den andra valideringsfasen. I slutet av epoken t, de föreslagna funktionerna {f Slutligen, för att uppdatera funktionen betyder, låt F vara K-radsmatrisen av funktionsmedel. Funktionen innebär uppdatering F ← (Z T Z) −1 Z T X kan utvärderas som en enda transaktion genom att beräkna beloppen parallellt. Vi presenterar pseudokoden för OCC parallellisering av BP-medel i bilaga A. Vi fastställer nu riktigheten och skalbarheten av de föreslagna OCC-algoritmerna. I motsats till det samordningsfria mönstret där skalbarheten är trivial och korrektheten ofta kräver starka antaganden eller håller bara i förväntan, leder OCC-mönstret till enkla bevis på korrekthet och utmanande skalbarhetsanalys. I många fall är det dock att föredra att ha algoritmer som är korrekta och troligen snabba snarare än snabba och möjligen korrekta. Vi etablerar först serializability: Theorem 3.1 (Serializability). De distribuerade DP-medel, OCL, och BP-medel algoritmer är seriellt likvärdiga med DP-medel, OCL och BP-medel, respektive. Beviset (bilaga B) i Theorem 3.1 är relativt enkelt och erhålls genom att konstruera en permutationsfunktion som beskriver en motsvarande serieutförande för varje distribuerat utförande. Beviset kan enkelt utökas till många andra maskininlärningsalgoritmer. Serializability gör det möjligt för oss att enkelt utöka viktiga teoretiska egenskaper hos den seriella algoritmen till den distribuerade inställningen. Till exempel, genom att åberopa serializability, kan vi fastställa följande resultat för OCC-versionen av online anläggningen plats (OFL) algoritm: Lemma 3.2. Om datan är slumpmässigt beställd ger OCC OFIL-algoritmen en approximation med konstant faktor för DP-medelvärdena. Om uppgifterna är kontradiktoriskt beställda, ger OCC OFL en log-faktor approximation till DP-medelmålet. Beviset (tillägg B) för Lemma 3.2 härleds först i serieinställningen och utvidgas sedan till den distribuerade inställningen genom serialisering. I motsats till system med uppdelning och konverger, vars approximationsgränser ofta är beroende av antalet nivåer [18], påverkas Lemma 3.2 inte av distribuerad bearbetning och har ingen kommunikation eller grövre avräkningar. Dessutom, för att behålla samma faktorer som en batch algoritm på den fullständiga data, splitter-och-konquer system behöver ett stort antal preliminära centra på lägre nivåer [18, 2]. I så fall kan kommunikationskostnaderna vara höga, eftersom alla föreslagna kluster skickas samtidigt, i motsats till OCC-metoden. Vi tar upp kommunikationen overhead (antalet avslag) för vår plan nästa. Skalbarhet Skalbarheten hos OCC-algoritmerna beror på antalet transaktioner som avvisas under valideringen (dvs. avstötningsfrekvensen). Även om en allmän skalbarhetsanalys kan vara utmanande, är det ofta möjligt att få viss insikt i de asymptotiska beroendena genom att förenkla antaganden. I motsats till den samordningsfria metoden kan vi fortfarande säkert tillämpa OCC-algoritmer i avsaknad av skalbarhetsanalys eller vid förenkling av antaganden inte hålla. För att illustrera de tekniker som används i OCC skalbarhetsanalys studerar vi DP-Means algoritm. Den skalbarhetsbegränsande faktorn för DP-Means algoritm 8 bestäms av antalet punkter som måste valideras serievis. I följande teorem visar vi att kommunikationskostnaden endast beror på antalet kluster och bearbetningsresurser och inte direkt beror på antalet datapunkter. Beviset finns i App. C. Teorem 3.3 (DP-Means skalbarhet). Antag N datapunkter genereras iid för att bilda ett slumpmässigt antal (K N ) av välrymda kluster av diameter λ: λ är en övre gräns på avstånden inom kluster och en lägre gräns på avståndet mellan kluster. Därefter begränsas det förväntade antalet serievisa validerade punkter ovan av P b + E [K N] för P-processorer och b-punkter per epok. Under separation antaganden av teorem, antalet kluster som finns i N datapunkter, K N, är exakt lika med antalet kluster som finns av DP-Means i N datapunkter; kalla denna senare kvantitet k N. De experimentella resultaten i Figur 3 tyder på att gränsen av P b + k N kan hålla mer allmänt bortom antagandena ovan. Eftersom mästaren måste bearbeta minst k N-poäng, är de overhead som orsakas av avstötningar P b och oberoende av N. För att analysera den totala körtiden, noterar vi att efter var och en av N/(P b) epokerna måste mästaren och arbetarna kommunicera. Varje arbetstagare måste bearbeta N/P-datapunkter, och befälhavaren ser högst k N + P b-punkter. Den totala förväntade körtiden är alltså O(N/(P b) + N/P + P b). För våra experiment genererade vi syntetisk data för kluster (DP-medel och OCL) och funktionsmodellering (BP-medel). Klustret och dess proportioner genererades på ett icke-parametriskt sätt enligt beskrivningen nedan. Alla datapunkter genererades i R 16-rymden. Tröskelparametern λ fastställdes till 1. Kluster: Klustret proportioner och indikatorer genereras samtidigt med stick-brytande förfarande för Dirichlet processer-"sticks" är "brutna" i farten för att generera nya kluster när och när det behövs. 1 För våra experiment använde vi en fast koncentrationsparameter  och = 1. Cluster medel provtogs μ k  på N (0, I 16 ), och datapunkter genererades vid x i  på N (μ zi, 1 4 I 16 ). Feature modellering: Vi använder stick-breaking procedur av [20] för att generera funktionsvikter. Till skillnad från Dirichlet processer, kan vi inte utföra stickbrytande on-the-fly med Beta processer. Istället genererar vi tillräckligt med funktioner så att de återstående icke-genererade funktionerna med hög sannolikhet (> 0, 9999) kommer att ha försumbara vikter (< 0, 0001). Koncentrationsparametern har också fastställts till  till = 1. Vi genererade funktionen innebär f k  till N (0, I 16 ) och datapunkter För att testa effektiviteten av våra algoritmer, simulerade vi den första iterationen (en komplett passera över alla data, där de flesta kluster / funktioner skapas och därmed störst samordning behövs) av varje algoritm i MATLAB. Antalet datapunkter, N, varierade från 256 till 2560 i intervaller på 256. Vi varierade också P b, antalet datapunkter som behandlats i en epok, från 16 till 256 i makter på 2. För varje värde av N och P b, mätte vi empiriskt k N, antalet accepterade kluster / funktioner, och M N, antalet föreslagna kluster / funktioner. Detta upprepades 400 gånger för att erhålla den empiriska averagê, antalet avslag. För OCC DP-medel, observerar vi Ê[M N − k N ] avgränsas ovan av P b (Fig. 3a), och att denna gräns är oberoende av datamängden storlek, även när antagandena i Thm 3.3 kränks. (Vi verifierade också att liknande empiriska resultat erhålls när antagandena inte överträds; se bilaga C.) Som visas i bild. 3b och Fig. 3c samma beteende observeras för OCC OFIL och OCC BP-means algoritmer. Vi har också implementerat de distribuerade algoritmerna i Spark [25], ett klustersystem med öppen källkod. DP-medel och BP-medel algoritmer var bootstrappade genom förbehandling av ett litet antal datapunkter (1/16 av de första P b-punkter)-detta minskar antalet datapunkter som sändes till befälhavaren på den första epoken, samtidigt som serialiserbarheten av algoritmerna bevaras. Våra Spark implementationer testades på Amazon EC2 genom att bearbeta en fast datauppsättning på 1, 2, 4, 8 m2.4xlarge (minnesoptimerad, fyrdubbla extra stora, med 8 virtuella kärnor och 64.8GiB minne) instanser. 1 Vi valde att använda stick-breaking förfaranden eftersom den kinesiska restaurangen och indiska bufféprocesser är i sig sekventiella. Stick-breaking procedurer kan distribueras antingen genom trunkering, eller med hjälp av OCC! divideras med detta med hjälp av 1 maskin (P = 8). Helst ska drifttiden med 2, 4, 8 maskiner (P = 16, 32, 64) vara 1/2, 1/4, 1/8 av drifttiden med hjälp av 1 maskin. OCC DP-medel och BP-medel få nästan perfekt skalning för alla iterationer. OCC OFL avvisar en hel del initialt, men blir snabbt bättre i senare epoker. Helst, att bearbeta samma mängd data, en algoritm och genomförande med perfekt skalning skulle ta halva tiden på 8 maskiner som det skulle på 4, och så vidare. Tomterna i figur 4 visar denna jämförelse genom att dividera alla körtider med körtiden på en maskin. DP-medel: Vi körde den distribuerade DP-medel algoritm på 2 27  på 134M datapunkter, med hjälp av λ = 2. Blockstorleken b valdes för att hålla P b = 2 23 8M konstant. Algoritmen kördes för 5 iterationer (fullständigt passera över alla data i 16 epoker). Vi kunde få perfekt skalning (Figur 4a ) i alla utom den första iteration, när befälhavaren måste utföra den mest synkronisering av föreslagna centra. OFL: Den distribuerade OFL-algoritmen kördes på 2 20  på 1M datapunkter, med hjälp av λ = 2. Till skillnad från DP-medel och BP-medel utförde vi inte bootstraping. OFL är också en algoritm för ett enda pass (en iteration). Blockstorleken b valdes så att P b = 2 16  på 66K datapunkter behandlas varje epok, vilket ger oss 16 epoker. Figur 4b visar att vi inte får någon skalning under den första epoken, där allt arbete utförs av mastern som behandlar alla P b datapunkter. Under senare epoker minskar masterns arbetsbörda när färre datapunkter föreslås, men arbetarnas arbetsbörda ökar när det totala antalet centra ökar. På så sätt förbättras skalningen under senare epoker. BP-medelvärden: Distribuerade BP-medelvärden kördes på 2 23 8M datapunkter, med λ = 1; blockstorlek valdes så att P b = 2 19 0.5M är konstant. Fem iterationer drevs, med 16 epoker per iteration. Som med DP-medel kunde vi uppnå nästan perfekt skalning; se figur 4c. Andra har föreslagit alternativ till ömsesidig uteslutning och samordningsfri parallellism för maskininlärning algoritmdesign. Newman [19] föreslog att trans-11 skulle bilda den underliggande modellen för att exponera ytterligare parallellism samtidigt som den marginella bakre. Sådana konstruktioner kan dock vara utmanande eller ogenomförbara och många hindrar blandning eller konvergens. På samma sätt föreslog Lovell [15] en reparameterisering av den underliggande modellen för att exponera ytterligare parallellism genom villkorligt oberoende. Ytterligare arbete som liknar i andemening med hjälp av OCC-liknande tekniker inkluderar Doshi-Velez et al. [9] som föreslog en ungefärlig parallell provtagningsalgoritm för IBP som görs exakt genom att införa ytterligare en MetropolisHastings steg, och Xu och Ihler [24] som föreslog en look-ahead strategi där framtida prover beräknas optimistiskt baserat på de sannolika resultaten av nuvarande prover. En stor mängd arbete behandlar skalbara kluster algoritmer [8, 7, 10]. Många algoritmer med bevisbara approximativa faktorer är strömmande algoritmer [18, 22, 6] och i sig använda hierarkier, eller relaterade uppdelning-och-konquer metoder [2]. De approximativa faktorerna i sådana algoritmer multiplicerar sig med nivåerna [18], och kräver en noggrann avvägning mellan kommunikation och approximation kvalitet som är förbisedd i vårt ramverk. Andra metoder använder kärnuppsättningar [5, 11]. En hel del metoder [2, 3, 22] först samla en uppsättning av centra och sedan återklustra dem, och därför måste kommunicera alla mellanliggande centra. Vårt tillvägagångssätt undviker detta, eftersom ett centrum inte orsakar några avvisanden under epokerna efter det att det har etablerats: avvisandet ökar inte med K. Ändå, som våra exempel visar, kan vårt ramverk för OCC enkelt integrera och utnyttja många av idéerna i de citerade verken. I detta dokument har vi visat hur optimistisk konvergenskontroll kan användas på ett användbart sätt vid utformningen av distribuerade maskininlärningsalgoritmer. I motsats till tidigare tillvägagångssätt bevarar detta korrektheten, i de flesta fall till en liten kostnad. Vi etablerade ekvivalensen av våra distribuerade OCC DP-medel, OCL och BP-medel algoritmer till deras seriella motsvarigheter, vilket bevarar deras teoretiska egenskaper. Särskilt de starka approximationsgarantierna för serie OCL översätter omedelbart till den distribuerade algoritmen. Vår teoretiska analys säkerställer att OCC DP-medel uppnår hög parallellism utan att offra korrekthet. Vi implementerade och utvärderade alla tre OCC-algoritmerna på en distribuerad datorplattform och demonstrerade en stark skalbarhet i praktiken. Vi anser att det finns mycket mer att göra i detta avseende. I själva verket, maskininlärning algoritmer har många egenskaper som skiljer dem från klassiska databasoperationer och kan tillåta att gå utöver den klassiska formuleringen av optimistisk konvergenskontroll. I synnerhet kan vi delvis eller probabilistiskt acceptera icke-serialiseringsbara operationer på ett sätt som bevarar underliggande algoritminvarianter. Lagar av stort antal och koncentration teorem kan ge verktyg för att utforma sådan verksamhet. Dessutom kan konfliktdetekteringsmekanismen behandlas som en styrknapp, vilket gör att vi mjukt kan växla mellan stabila, teoretiskt ljudalgoritmer och potentiellt snabbare koordinationsfria 12 algoritmer.
Nyligen, förslag har dykt upp för att utnyttja optimistisk konvergenskontroll (OCC) från databasen serializability teori för funktionssynkronisering i samband med maskininlärning problem såsom oövervakad klusterbildning REF.
Optimistic Concurrency Control for Distributed Unsupervised Learning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}