Låt C vara en klass av sannolikhetsfördelningar över den diskreta domänen [n] = {1,..., n}. Vi visar att om C uppfyller ett ganska allmänt villkor - väsentligen, att varje distribution i C kan väl-tillnärmas av en variabel-bredd histogram med få bins - då finns det en mycket effektiv (både i fråga om körtid och prov komplexitet) algoritm som kan lära sig någon blandning av k okända distributioner från C. Vi analyserar flera naturliga typer av distributioner över [n], inklusive log-konkav, monoton riskfrekvens och unimodala distributioner, och visar att de har den nödvändiga strukturella egenskapen att vara väl approximerad av ett histogram med få bins. Genom att tillämpa vår allmänna algoritm får vi nästan optimalt effektiva algoritmer för alla dessa blandningslärande problem som beskrivs nedan. Mer exakt, • Log-concave distributioner: Vi lär oss någon blandning av k log-concave distributioner över [n] med k ·Õ(1/ε 4 ) prover (oberoende av n) och kör i tid Õ(k log(n)/ε 4 ) bitoperationer (observera att läsa ett enda prov från [n] tar  på (log n) bit operationer). För specialfallet k = 1 ger vi en effektiv algoritm med Õ(1/ε 3 ) prover; detta generaliserar huvudresultatet av [DDS12b] från klassen av Poisson Binomial distributioner till den mycket bredare klassen av alla log-concave distributioner. Våra övre gränser är inte långt ifrån optimala eftersom någon algoritm för detta inlärningsproblem kräver  och (k/ε 5/2 ) prover. • Monoton riskfrekvens (MHR) fördelningar: Vi lär oss varje blandning av k MHR fördelningar över [n] med hjälp av O(k log(n/ε)/ε 4 ) prover och körs i tid Õ(k log 2 (n)/ε 4 ) bit-operationer. Alla algoritmer för detta inlärningsproblem måste använda  och (k log(n)/ε 3 ) prover. • Unimodal distribution: Vi ger en algoritm som lär sig någon blandning av k unimodal distribution över [n] med hjälp av O(k log(n)/ε 4 ) prover och kör i tid Õ(k log 2 (n)/ε 4 ) bit-operationer. Alla algoritmer för detta problem måste använda proverna  och (k log(n)/ε 3 ).
(Det dokumentet handlade om distributioner över den diskreta domänen [N] = {1,.., N}, men för enkelhetens skull översätter vi REF-resultaten till den kontinuerliga domänen.
Learning mixtures of structured distributions over discrete domains
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}