Abstrakt. I detta dokument studerar vi inlärningsproblemet i närvaro av klassificeringsbuller i Valiants probabilistiska inlärningsmodell och dess varianter. För att identifiera klassen av "robust" inlärningsalgoritmer på det mest allmänna sättet formaliserar vi en ny men relaterad modell för lärande från statistiska frågor. Intuitivt, i denna modell, är en inlärningsalgoritm förbjuden att undersöka enskilda exempel på den okända målfunktionen, men ges tillgång till ett orakel som ger uppskattningar av sannolikheter över urvalet utrymme slumpmässiga exempel. Ett av våra viktigaste resultat visar att alla typer av funktioner som kan läras av statistiska frågor i själva verket är inlärbara med klassificeringsbuller i Valiants modell, med en bullerhastighet som närmar sig den informationsteoretiska barriären på 1/2. Vi visar sedan den statistiska frågemodellens allmängiltighet och visar att praktiskt taget varje klass som är lärbar i Valiants modell och dess varianter också kan läras i den nya modellen (och därmed kan läras i närvaro av buller). Ett anmärkningsvärt undantag från detta uttalande är den klass av paritetsfunktioner, som vi visar inte kan lära sig av statistiska frågor, och för vilka ingen bullertolerant algoritm är känd.
visade att kraften i den lokala modellen är likvärdig med den statistiska frågemodellen REF från inlärningsteori.
Efficient noise-tolerant learning from statistical queries
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}