Distributionsinlärningsteori

Den fördelningsmässiga inlärningsteorin eller inlärning av sannolikhetsfördelning är ett ramverk inom beräkningslärandeteori . Det har föreslagits från Michael Kearns , Yishay Mansour, Dana Ron , Ronitt Rubinfeld , Robert Schapire och Linda Sellie 1994 och det var inspirerat av PAC-ramverket som introducerades av Leslie Valiant .

I detta ramverk är indata ett antal stickprov från en distribution som tillhör en specifik klass av distributioner. Målet är att hitta en effektiv algoritm som utifrån dessa stickprov med stor sannolikhet bestämmer fördelningen från vilken stickproven har tagits. På grund av dess generella karaktär har detta ramverk använts inom ett stort antal olika områden som maskininlärning , approximationsalgoritmer , tillämpad sannolikhet och statistik .

Den här artikeln förklarar de grundläggande definitionerna, verktygen och resultaten i detta ramverk utifrån beräkningsteorin.

Definitioner

Låt $\textstyle X$ vara stödet för fördelningarna av intresse. Som i originalverket av Kearns et al. om $\textstyle X$ är ändlig kan det utan förlust av generalitet antas att $\textstyle X=\{0,1\}^{n}$ där ${\ displaystyle \textstyle n}$ är antalet bitar som måste användas för att representera någon $\textstyle y\in X$ . Vi fokuserar på sannolikhetsfördelningar över $\textstyle X$ .

Det finns två möjliga representationer av en sannolikhetsfördelning $\textstyle D$ över $\textstyle X$ .

• sannolikhetsfördelningsfunktion (eller utvärderare) en utvärderare $\textstyle E_{D}$ för $\textstyle D$ tar som indata någon $\textstyle y\in X$ och matar ut en reella tal $\textstyle E_{D}[y]$ som anger sannolikheten för $\textstyle y$ enligt $\textstyle D$ , dvs $\textstyle E_{D}[y]=\Pr[Y=y]$ om $\textstyle Y\sim D$ .
• generera en generator $\textstyle G_{D}$ för $\textstyle D$ tar som indata en sträng med verkligt slumpmässiga bitar $\textstyle y$ och matar ut $\textstyle G_{D}[y]\in X$ enligt fördelningen $\textstyle D$ . Generator kan tolkas som en rutin som simulerar sampling från distributionen $\textstyle D$ givet en sekvens av rättvisa myntkast.

En fördelning $\textstyle D$ kallas för att ha en polynomgenerator (respektive evaluator) om dess generator (respektive evaluator) finns och kan beräknas i polynomtid.

Låt $\textstyle C_{X}$ en klass av distribution över X, det vill säga $\textstyle C_{X}$ är en mängd så att varje $\textstyle D \in C_{X}$ är en sannolikhetsfördelning med stöd $\textstyle X$ . C $\textstyle C_{X}$ kan också skrivas som $\displaystyle \textstyle C}$ för enkelhetens skull.

Innan man definierar inlärningsbarhet är det nödvändigt att definiera bra approximationer av en distribution $\textstyle D$ . Det finns flera sätt att mäta avståndet mellan två distributioner. De tre vanligaste möjligheterna är

• Kullback-Leibler divergens
• Total variationsavstånd för sannolikhetsmått
• Kolmogorov avstånd

Det starkaste av dessa avstånd är Kullback-Leibler-divergensen och det svagaste är Kolmogorov-avståndet . Detta betyder att för alla distributionspar $\textstyle D$ , $\textstyle D'$ :

${\text{KL-distance}}(D,D')\geq { \text{TV-avstånd}}(D,D')\geq {\text{Kolmogorov-distans}}(D,D')$

Därför, till exempel om $\textstyle D$ och $\textstyle D'$ är nära med avseende på Kullback-Leibler-divergensen så är de också nära med avseende på alla andra avstånd.

Nästa definitioner gäller för alla avstånd och därför anger symbolen $\textstyle d(D,D')$ avståndet mellan fördelningen $\textstyle D$ och fördelningen $\textstyle D'$ med ett av avstånden som vi beskriver ovan. Även om inlärningsförmågan för en klass av distributioner kan definieras med någon av dessa avstånd, hänvisar applikationer till ett specifikt avstånd.

Den grundläggande input som vi använder för att lära oss en distribution är ett antal stickprov som dras av denna distribution. För beräkningssynpunkt är antagandet att ett sådant sampel ges under en konstant tidsperiod. Så det är som att ha tillgång till ett orakel $\textstyle GEN(D)$ som returnerar ett sampel från distributionen $\textstyle D$ . Ibland är intresset, förutom att mäta tidskomplexiteten, att mäta antalet sampel som måste användas för att lära sig en specifik distribution $\textstyle D$ i distributionsklassen $\textstyle C$ . Denna kvantitet kallas provkomplexitet för inlärningsalgoritmen.

För att problemet med distributionsinlärning ska bli tydligare, överväg problemet med övervakat lärande enligt definitionen i. I denna ram för statistisk inlärningsteori är en träningsuppsättning ${\displaystyle \textstyle S=\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}} och målet är att hitta en$ målfunktion $\textstyle f:X\rightarrow Y$ som minimerar någon förlustfunktion, t.ex. kvadratförlustfunktionen. Mer formellt $f=\arg \min _{g}\int V(y,g(x))d \rho (x,y)$ , där $V(\cdot ,\cdot )$ är förlustfunktionen, t.ex. $V(y,z)=(yz)^{2}$ och $\rho (x,y)$ sannolikhetsfördelningen enligt vilken elementen i träningsuppsättningen samplas. Om den villkorliga sannolikhetsfördelningen $\rho _{x}(y)$ är känd så har målfunktionen den slutna formen $f(x)=\int _{y}yd\rho _{x}(y)$ . Så mängden $S$ är en uppsättning sampel från sannolikhetsfördelningen $\rho (x,y)$ . Nu är målet för fördelningsinlärningsteori om att hitta $\rho$ givet $S$ som kan användas för att hitta målfunktionen $f$ .

Definition av lärbarhet

En klass av distributioner $\textstyle C$ kallas effektivt inlärbar om för varje $\textstyle \epsilon >0$ och $\textstyle 0<\delta \leq 1$ ges åtkomst till $\textstyle GEN(D)$ för en okänd distribution $\textstyle D\in C$ , det finns en polynomisk tidsalgoritm $\textstyle A$ , kallad inlärningsalgoritm för $\textstyle C$ , som matar ut en generator eller en utvärderare av en distribution $\textstyle D'$ så att

$\Pr[d(D,D')\leq \epsilon ]\geq 1-\delta$

Om vi ​​vet att $\textstyle D'\in C$ så kallas ${\displaystyle \textstyle A} för$ korrekt inlärningsalgoritm , annars kallas den felaktig inlärningsalgoritm .

I vissa inställningar är distributionsklassen $\textstyle C$ en klass med välkända distributioner som kan beskrivas med en uppsättning parametrar. Till exempel $\textstyle C$ vara klassen för alla gaussfördelningarna $\textstyle N(\mu ,\sigma ^{2})$ . I detta fall bör algoritmen $\textstyle A$ kunna uppskatta parametrarna $\textstyle \mu ,\sigma$ . I det här fallet kallas $\textstyle A$ parameterinlärningsalgoritm .

Uppenbarligen är parameterinlärningen för enkla distributioner ett mycket väl studerat område som kallas statistisk uppskattning och det finns en mycket lång bibliografi om olika skattare för olika typer av enkla kända distributioner. Men distributionslärandeteori handlar om inlärningsklass av distributioner som har en mer komplicerad beskrivning.

Första resultaten

I deras framstående arbete, Kearns et al. ta itu med fallet där $\textstyle A$ beskrivs i termen av en krets med ändlig polynomstorlek och de bevisade följande för vissa specifika distributionsklasser.

• $\textstyle OR$ grinddistributioner för denna typ av distributioner finns det ingen utvärderare av polynomstorlek, såvida inte $\textstyle \#P\subseteq P/{\text{poly}}$ . Å andra sidan är den här klassen effektivt lärbar med generator.
• Paritetsgrinddistributioner denna klass är effektivt lärbara med både generator och utvärderare.
• Blandningar av Hamming Balls denna klass är effektivt lärbara med både generator och utvärderare.
• Probabilistic Finite Automata denna klass är inte effektivt lärbar med utvärderare under Noisy Parity Assumption som är ett omöjlighetsantagande i PAC-inlärningsramverket.

$\textstyle \epsilon -$ Omslag

En mycket vanlig teknik för att hitta en inlärningsalgoritm för en klass av distributioner $\textstyle C$ är att först hitta en liten $\textstyle \epsilon -$ omslag till $\textstyle C$ .

Definition

En uppsättning $\textstyle C_{\epsilon }$ kallas $\textstyle \epsilon$ -omslag av $\textstyle C$ om för varje $\textstyle D\ i C$ finns en $\textstyle D'\in C_{\epsilon }$ så att $\textstyle d(D,D')\ leq \epsilon$ . Ett $\textstyle \epsilon -$ omslag är litet om det har polynomstorlek med avseende på parametrarna som beskriver $\textstyle D$ .

När det väl finns en effektiv procedur som för varje $\textstyle \epsilon >0$ hittar en liten $\textstyle \epsilon -$ omslag $\textstyle C_{\epsilon }$ av C då är den enda kvarvarande uppgiften att välja från $\textstyle C_{\epsilon }$ fördelningen $\textstyle D'\in C_{\epsilon }$ som är närmare distribution $\textstyle D\in C$ som måste läras in.

Problemet är att givet $\textstyle D',D''\in C_{\epsilon }$ är det inte trivialt hur vi kan jämföra $\textstyle d(D,D')$ och $\textstyle d(D,D'')$ för att avgöra vilken som är närmast $\textstyle D$ , eftersom $\textstyle D$ är okänd. Därför måste samplen från ${\displaystyle \textstyle D} användas för att göra dessa jämförelser.$ Uppenbarligen har resultatet av jämförelsen alltid en sannolikhet för fel. Så uppgiften är liknande med att hitta minimum i en uppsättning element med hjälp av bullriga jämförelser. Det finns många klassiska algoritmer för att uppnå detta mål. Den senaste som uppnår de bästa garantierna föreslogs av Daskalakis och Kamath. Denna algoritm sätter upp en snabb turnering mellan elementen i $\textstyle C_{\epsilon }$ där vinnaren $\textstyle D ^{*}$ i denna turnering är elementet som är $\textstyle \epsilon -$ nära $\textstyle D$ (dvs $\textstyle d(D^{*},D)\leq \epsilon$ ) med sannolikhet minst $\textstyle 1-\delta$ . För att göra det använder deras algoritm $\textstyle O(\log N/\epsilon ^{2})$ sampel från $\textstyle D$ och körs i $\textstyle O(N\log N/\epsilon ^{2})$ tid, där $\textstyle N=|C_{\epsilon }|$ .

Lärande summor av slumpvariabler

Att lära sig enkla välkända distributioner är ett väl studerat område och det finns många estimatorer som kan användas. En mer komplicerad klass av distributioner är fördelningen av en summa av variabler som följer enkla distributioner. Dessa inlärningsförfaranden har ett nära samband med gränssatser som den centrala gränssatsen eftersom de tenderar att undersöka samma objekt när summan tenderar till en oändlig summa. Nyligen finns det två resultat som beskrivs här inkluderar inlärningsPoissons binomialfördelningar och inlärningssummor av oberoende heltalsslumpvariabler. Alla resultat nedan gäller med det totala variationsavståndet som ett avståndsmått.

Att lära sig Poissons binomialfördelningar

Betrakta $\textstyle n$ oberoende Bernoullis slumpvariabler $\textstyle X_{1},\dots ,X_{n}$ med sannolikheter för framgång ${ \displaystyle \textstyle p_{1},\dots ,p_{n}}$ . En Poisson Binomial Fördelning av ordning $\textstyle n$ är fördelningen av summan $\textstyle X=\summa _{i}X_{i}$ . För att lära sig klassen $\textstyle PBD=\{D:D~{\text{ är en Poisson-binomialfördelning}}\}$ . Det första av följande resultat handlar om fallet med felaktig inlärning av $\textstyle PBD$ och det andra med korrekt inlärning av $\textstyle PBD$ .

Sats

Låt $\textstyle D\in PBD$ så finns det en algoritm som ger ${\displaystyle \textstyle n} ,$ ϵ $\displaystyle \textstyle \epsilon >0}$ , ${ \displaystyle \textstyle 0<\delta \leq 1}$ och tillgång till $\textstyle GEN(D)$ hittar ett $\textstyle D'$ så att $\textstyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta$ . Exempelkomplexiteten för denna algoritm är $\textstyle {\tilde {O}}((1/\epsilon ^{3})\log( 1/\delta ))$ och körtiden är $\textstyle {\tilde {O}}((1/\ epsilon ^{3})\log n\log ^{2}(1/\delta ))$ .

Sats

Låt $\textstyle D\in PBD$ så finns det en algoritm som ger ${\displaystyle \textstyle n} ,$ ϵ $\displaystyle \textstyle \epsilon >0}$ , ${ \displaystyle \textstyle 0<\delta \leq 1}$ och tillgång till $\textstyle GEN(D)$ hittar en $\textstyle D'\in PBD$ så att $\textstyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta$ . Exempelkomplexiteten för denna algoritm är $\textstyle {\tilde {O}}((1/\epsilon ^{2}))\log (1/\delta)$ och körtiden är $\textstyle (1/ \epsilon )^{O(\log ^{2}(1/\epsilon ))}{\tilde {O}}(\log n\log(1/\delta ))$ .

En del av resultaten ovan är att provkomplexiteten för inlärningsalgoritmen inte beror på ${\displaystyle \textstyle n} ,$ även om beskrivningen av $\textstyle D$ är linjär i $\textstyle n$ . Även det andra resultatet är nästan optimalt med avseende på provets komplexitet eftersom det också finns en nedre gräns för $\textstyle O(1/\epsilon ^{2})$ .

Beviset använder ett litet $\textstyle \epsilon -$ omslag av $\textstyle PBD$ som har producerats av Daskalakis och Papadimitriou, för att få denna algoritm.

Inlärningssummor av oberoende heltals slumpmässiga variabler

Betrakta $\textstyle n$ oberoende slumpvariabler $\textstyle X_{1},\dots ,X_{n}$ som var och en följer en godtycklig fördelning med stöd för $\textstyle \{0,1,\dots ,k-1\}$ . A $\textstyle k-$ summan av oberoende heltals slumpvariabel av ordningen $\textstyle n$ är fördelningen av summan $\textstyle X=\summa _{ i}X_{i}$ . För att lära sig klassen

$\textstyle k-SIIRV=\{D:D{\text{är en k-summa av oberoende heltalsslumpmässig variabel }}\}$

det är följande resultat

Sats

Låt $\textstyle D\in k-SIIRV$ så finns det en algoritm som ger ${\displaystyle \textstyle n} ,$ ϵ $\displaystyle \textstyle \epsilon >0}$ och åtkomst till $\textstyle GEN(D)$ hittar ett $\textstyle D'$ så att ${ \displaystyle \textstyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta }$ . Exempelkomplexiteten för denna algoritm är $) {\displaystyle \textstyle { \text{poly}}(k/\epsilon )}$$\displaystyle \textstyle {\text{poly}}(k/\epsilon )}$ och körtiden är också .

En annan del är att samplet och tidskomplexiteten inte beror på $\textstyle n$ . Det är möjligt att sluta detta oberoende för föregående avsnitt om vi sätter $\textstyle k=2$ .

Inlärningsblandningar av Gausser

Låt slumpvariablerna $\textstyle X\sim N(\mu _{1},\Sigma _{1})$ och $\textstyle Y\sim N(\mu _{2},\Sigma _{2})$ . Definiera slumpvariabeln $\textstyle Z$ som tar samma värde som $\textstyle X$ med sannolikhet $\textstyle w_{1}$ och samma värde som $\ textstil Y$ med sannolikhet $\textstyle w_{2}=1-w_{1}$ . Sedan om $\textstyle F_{1}$ är densiteten för $\textstyle X$ och $\textstyle F_{2}$ är densiteten för $\textstyle Y$ densiteten för $\textstyle Z$ är $\textstyle F=w_{1}F_{1}+w_{2}F_{2}$ . I detta fall sägs ${\displaystyle \textstyle Z} följa en blandning av Gausser.$ Pearson var den första som introducerade begreppet blandningar av Gausser i sitt försök att förklara sannolikhetsfördelningen från vilken han fick samma data som han ville analysera. Så efter att ha gjort många beräkningar för hand anpassade han äntligen sina data till en blandning av gausser. Inlärningsuppgiften i detta fall är att bestämma parametrarna för blandningen $\textstyle w_{1},w_{2},\mu _{ 1},\mu _{2},\Sigma _{1},\Sigma _{2}$ .

Det första försöket att lösa detta problem var från Dasgupta. I detta verk antar Dasgupta att Gaussernas två medel är tillräckligt långt från varandra. Det betyder att det finns en nedre gräns för avståndet $\textstyle ||\mu _{1}-\mu _{2}||$ . Med detta antagande kunde Dasgupta och många forskare efter honom lära sig parametrarna för blandningen. Inlärningsproceduren börjar med att gruppera proverna i två olika kluster, vilket minimerar en viss metrik. Med antagandet att Gaussernas medel är långt borta från varandra med hög sannolikhet motsvarar samplen i det första klustret sampel från det första Gaussian och samplen i det andra klustret till samples från det andra. Nu när proverna är partitionerade kan $\textstyle \mu _{i},\Sigma _{i}$ beräknas från enkla statistiska estimatorer och $\textstyle w_{i}$ genom att jämföra storleken på klustren.

Om $\textstyle GM$ är mängden av alla blandningar av två Gausser, kan man med hjälp av ovanstående procedursatser som följande bevisas

Sats

Låt $\textstyle D\in GM$ med $_{max}(\Sigma _{2}))}}} , där c >$${\displaystyle \textstyle ||\mu _{1}-\mu _{2}||\geq c{\ sqrt {n\max(\lambda _{max}(\$$\ textstyle c>1/2}$ 1/2 och $\textstyle \lambda _{max}(A)$ det största egenvärdet av $\textstyle A$ , då finns det en algoritm som ger $\textstyle \epsilon >0$ , $\textstyle 0<\delta \leq 1$ och tillgång till $\textstyle GEN(D)$ hittar en approximation $\textstyle w'_{i},\mu '_{i},\Sigma '_{i}$ av parametrarna så att ${\displaystyle \textstyle \Pr[||w_{i}-w'_{i}||\leq \epsilon ]\geq 1-\delta } (respektive för μ$ i $mu _{i}}$$displaystyle \textstyle$$\displaystyle \textstyle M=2^{O(\log ^{2}(1/(\epsilon \delta )))}}$ och $\textstyle \Sigma _{i}$$.$ Exempelkomplexiteten för denna algoritm är och körtiden är $\textstyle O(M^{2}d+Mdn)$ .

Ovanstående resultat kan också generaliseras i $\textstyle k-$ blandning av Gausser.

För fallet med blandning av två Gausser finns det inlärningsresultat utan antagande om avståndet mellan deras medel, som den följande som använder den totala variationsdistansen som ett avståndsmått.

Sats

Låt $\textstyle F\in GM$ så finns det en algoritm som ger $\textstyle \epsilon >0$ , $\textstyle 0<\delta \leq 1$ och åtkomst till $\textstyle GEN(D)$ hittar $\textstyle w'_{i},\mu '_{ i},\Sigma '_{i}$ så att om $\textstyle F'=w'_{1}F'_{1} +w'_{2}F'_{2}$ , där $\textstyle F'_{i}=N(\mu '_{i },\Sigma '_{i})$ sedan $\textstyle \Pr[d(F,F')\leq \epsilon ]\geq 1-\delta$ . Provkomplexiteten och körtiden för denna algoritm är $\textstyle { \text{poly}}(n,1/\epsilon ,1/\delta ,1/w_{1},1/w_{2},1/d(F_{1},F_{2}))$ .

Avståndet mellan $\textstyle F_{1}$ och $\textstyle F_{2}$ påverkar inte kvaliteten på resultatet av algoritmen utan bara provets komplexitet och körtiden.