Feltolerans (PAC-inlärning)

I PAC-inlärning hänvisar feltolerans till förmågan hos en algoritm att lära sig när de mottagna exemplen har skadats på något sätt. I själva verket är detta en mycket vanlig och viktig fråga eftersom det i många applikationer inte är möjligt att komma åt brusfri data. Brus kan störa inlärningsprocessen på olika nivåer: algoritmen kan ta emot data som ibland har felmärkts, eller indata kan ha en del falsk information, eller klassificeringen av exemplen kan ha förfalskats av uppsåt.

Notation och Valiant-inlärningsmodellen

Låt i det följande $X$ vara vårt $n$ -dimensionella inmatningsutrymme. Låt ${\mathcal {H}}$ vara en klass av funktioner som vi vill använda för att lära oss en $\{0,1\}$ -värderad målfunktion ${\ displaystyle f}$ definierad över $X$ . Låt ${\mathcal {D}}$ vara fördelningen av indata över $X$ . Målet med en inlärningsalgoritm ${\mathcal {A}}$ är att välja den bästa funktionen $h\in {\mathcal {H}}$ så att den minimerar $error(h)=P_{x\sim {\mathcal {D}}}(h(x)\neq f(x) ))$ . Låt oss anta att vi har en funktion $size(f)$ som kan mäta komplexiteten hos $f$ . Låt ${\text{Oracle}}(x)$ vara ett orakel som, närhelst det anropas, returnerar ett exempel $x$ och dess korrekta etikett $f(x) )$ .

När inget brus korrumperar data, kan vi definiera inlärning i Valiant-inställningen :

Definition: Vi säger att $f$ är effektivt lärbar med ${\mathcal {H}}$ i Valiant -inställningen om det finns en inlärningsalgoritm ${\mathcal {A}}$ som har tillgång till ${\text{Oracle}}(x)$ och ett polynom $p(\cdot ,\cdot ,\cdot ,\cdot )$ så att den för alla $0<\varepsilon \leq 1$ och $0<\delta \leq 1$ matar ut, i ett antal anrop till oraklet som begränsas av $p\left({\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,{\ text{size}}(f)\right)$ , en funktion $h\in {\mathcal {H}}$ som uppfyller sannolikheten minst $1-\delta$ den villkorsfel ${\displaystyle {\text{error}}(h)\leq \varepsilon$ .

I det följande kommer vi att definiera inlärningsbarheten för $f$ när data har modifierats.

Klassificeringsljud

I klassificeringsbrusmodellen introduceras en brushastighet ${\displaystyle 0\leq \eta <{\frac {1}{2}}}.$ Sedan, istället för ${\text{Oracle}}(x)$ som alltid returnerar den korrekta etiketten för exempel $x$ , algoritm ${\mathcal {A}}$ kan bara anropa ett felaktigt orakel ${\text{Oracle}}(x,\eta )$ som kommer att vända etiketten för $x$ med sannolikhet $\eta$ . Liksom i Valiant-fallet är målet med en inlärningsalgoritm ${\mathcal {A}}$ att välja den bästa funktionen $h\in {\mathcal {H}}$ så att den minimerar $error(h)=P_{x\sim {\mathcal {D}}}(h(x )\neq f(x))$ . I applikationer är det svårt att ha tillgång till det verkliga värdet av $\eta$ , men vi antar att vi har tillgång till dess övre gräns $\eta _{B}$ . Observera att om vi tillåter brushastigheten att vara ${\displaystyle 1/2} , blir$ under vilken beräkningstid som helst, eftersom varje etikett inte förmedlar information om målfunktionen.

Definition: Vi säger att $f$ är effektivt lärbar med ${\mathcal {H}}$ i klassificeringsbrusmodellen om det finns en inlärningsalgoritm ${\mathcal {A}}$ som har tillgång till ${\text{Oracle}}(x,\eta )$ och ett polynom $p(\cdot ,\cdot ,\cdot ,\cdot )$ så att för alla $0\leq \eta \leq {\frac {1}{2}}$ , $0\leq \ varepsilon \leq 1$ och $0\leq \delta \leq 1$ den matar ut, i ett antal anrop till oraklet som begränsas av $p\left({\frac {1}{1-2\eta _{B}}},{\frac {1}{\varepsilon }},{\ frac {1}{\delta }},n,size(f)\right)$ , en funktion $h\in {\mathcal {H}}$ som uppfyller sannolikheten minst $1-\delta$ villkoret $error(h)\leq \varepsilon$ .

Statistisk frågeinlärning

Statistical Query Learning är ett slags aktivt inlärningsproblem där inlärningsalgoritmen ${\mathcal {A}}$ kan bestämma om den vill begära information om sannolikheten $P_{f(x) }$ att en funktion $f$ korrekt etiketterar exempel ${\displaystyle x} ,$ och får ett svar korrekt inom en tolerans $\alpha$ . Formellt, närhelst inlärningsalgoritmen ${\mathcal {A}}$ anropar oraklet ${\displaystyle {\text{Oracle}}(x,\alpha )} ,$ får den som återkopplingssannolikhet $Q_{f(x)}$ , så att $Q_{f(x)} -\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha$ .

Definition: Vi säger att $f$ är effektivt inlärningsbar med ${\mathcal {H}}$ i den statistiska frågeinlärningsmodellen om det finns en inlärningsalgoritm ${\mathcal {A}}$ som har tillgång till ${\text{Oracle}}(x,\alpha )$ och polynom $p(\cdot ,\cdot ,\ cdot )$ , $q(\cdot ,\cdot ,\cdot )$ och $r(\cdot ,\cdot ,\cdot )$ så att för någon $0<\varepsilon \leq 1$ gäller följande:

${\text{Oracle}}(x,\alpha )$ kan utvärdera $P_{f(x)}$ i tiden $q\left({\frac {1}{\varepsilon }},n,size(f)\right)$ ;
${\frac {1}{\alpha }}$ begränsas av $r\left({\frac {1}{\ varepsilon }},n,size(f)\right)$
${\mathcal {A}}$ matar ut en modell $h$ så att $err(h)<\varepsilon$ , i ett antal anrop till orakel avgränsat av $p\left({\frac {1}{\varepsilon }},n,size(f)\right)$ .

Observera att konfidensparametern $\delta$ inte förekommer i definitionen av inlärning. Detta beror på att huvudsyftet med $\delta$ är att tillåta inlärningsalgoritmen en liten sannolikhet för misslyckande på grund av ett icke-representativt urval. Sedan nu ${\text{Oracle}}(x,\alpha )$ alltid att uppfylla approximationskriteriet ${\displaystyle Q_{f(x)}-\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha } , felsannolikheten behövs inte längre$ .

Den statistiska frågemodellen är strikt svagare än PAC-modellen: varje effektivt SQ-lärbar klass är effektivt PAC-lärbar i närvaro av klassificeringsbrus, men det finns effektiva PAC-lärbara problem såsom paritet som inte är effektivt SQ- lärbara .

Skadlig klassificering

I den skadliga klassificeringsmodellen genererar en motståndare fel för att förhindra inlärningsalgoritmen. Den här inställningen beskriver situationer med felskur , som kan uppstå när överföringsutrustningen under en begränsad tid inte fungerar som den ska. Formellt anropar algoritm ${\mathcal {A}}$ ett orakel ${\text{Oracle}}(x,\beta )$ som returnerar ett korrekt märkt exempel ${\ displaystyle x}$ ritad, som vanligt, från fördelningen ${\mathcal {D}}$ över inmatningsutrymmet med sannolikheten $1-\beta$ , men den returnerar med sannolikheten $\ beta$ ett exempel från en distribution som inte är relaterad till ${\mathcal {D}}$ . Dessutom kan detta uppsåtligt valda exempel strategiskt valts av en motståndare som har kunskap om $f$ , $\beta$ , ${\mathcal {D}}$ , eller den aktuella utvecklingen av inlärningsalgoritm.

Definition: Givet en gräns $\beta _{B}<{\frac {1}{2}}$ för $0\leq \beta <{\frac { 1}{2}}$ säger vi att $f$ är effektivt inlärningsbar med ${\mathcal {H}}$ i den skadliga klassificeringsmodellen, om det finns en inlärningsalgoritm ${ \mathcal {A}}$ som har tillgång till ${\text{Oracle}}(x,\beta )$ och ett polynom $p(\cdot ,\cdot ,\cdot ,\cdot ,\cdot )$ så att för någon $0<\varepsilon \leq 1$ , $0<\ delta \leq 1$ den matar ut, i ett antal anrop till oraklet som begränsas av $p\left ({\frac {1}{1/2-\beta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,storlek(f )\right)$ , en funktion $h\in {\mathcal {H}}$ som uppfyller med sannolikhet minst $1-\delta$ villkoret $error(h)\leq \varepsilon$ .

Fel i ingångarna: ojämnt slumpmässigt attributbrus

I den oenhetliga brusmodellen för slumpmässiga attribut lär algoritmen in en boolesk funktion , ett skadligt orakel ${\text{Oracle}}(x,\nu )$ kan vända varje $i$ -th biten av exemplet $x=(x_{1},x_{2},\ldots ,x_{n})$ oberoende med sannolikhet $\nu _{i}\leq \nu$ .

Denna typ av fel kan irreparabelt förhindra algoritmen, i själva verket gäller följande teorem:

I den olikformiga brusinställningen för slumpmässigt attribut kan en algoritm ${\displaystyle {\mathcal {A}}} mata ut en funktion$ $h\in {\mathcal {H}}$ så att $error(h)<\varepsilon$ endast om $\nu <2\varepsilon$ .

Se även