Vi introducerar en ny modell för lärande i närvaro av buller, som vi kallar Nasty Noise-modellen. Denna modell generaliserar tidigare ansedda modeller för lärande med buller. Lärandeprocessen i denna modell, som är en variant av PAC-modellen, fortskrider enligt följande: Antag att inlärningsalgoritmen under dess utförande kräver m exempel. De exempel som algoritmen får genereras av en otäck motståndare som fungerar enligt följande steg. Först väljer motståndaren m exempel (oberoende) enligt xed (men okänd för inlärningsalgoritmen) distribution D som i PAC-modellen. Sedan får den mäktige motståndaren, när han ser de speciella c m exempel som valdes (och använder sin kunskap om målfunktionen, distributionen D och inlärningsalgoritmen), ta bort en bråkdel av de exempel som den väljer, och ersätta dessa exempel med samma antal godtyckliga exempel på sitt val; M modi ed exempel ges sedan till inlärningsalgoritmen. Den enda begränsningen för motståndaren är att antalet exempel som motståndaren tillåts att ändra bör fördelas enligt en binomial fördelning med parametrar (bullerhastigheten) och m. På den negativa sidan visar vi att ingen algoritm kan uppnå noggrannhet < 2 i att lära sig någon icke-trivial klass av funktioner. Vi ger också några lägre gränser på provet komplexitet som krävs för att uppnå noggrannhet = 2 +. På den positiva sidan, Vi visar att ett polynom (i de vanliga parametrarna, och i? 2 ) antal exempel su ce för att lära någon klass av nite VC-dimension med noggrannhet > 2. Denna algoritm kanske inte är effektiv, men vi visar också att en ganska bred familj av konceptklasser kan läras eektivt i närvaro av otäckt buller.
Bshouty m.fl. REF introducerar en variant av PAC-utbildningsmodellen för lärande i närvaro av otäckt buller.
PAC Learning with Nasty Noise
{'venue': 'Theoretical Computer Science', 'journal': None, 'mag_field_of_study': ['Computer Science']}