Förekomsten av undandragande attacker under testfasen av maskininlärning algoritmer utgör en betydande utmaning för både deras installation och förståelse. Dessa attacker kan utföras genom att lägga omärkliga perturbationer till ingångar för att generera kontradiktoriska exempel och hitta effektiva försvar och detektorer har visat sig vara svårt. I detta dokument går vi bort från angreppsförsvarets kapprustning och försöker förstå gränserna för vad som kan läras i närvaro av en undanflyktsmotståndare. I synnerhet utökar vi ramen Sannolikt Ungefärlig Korrekt (PAC)-lärande för att redogöra för närvaron av en motståndare. Vi definierar först korrumperade hypotesklasser som uppstår från standard binära hypotesklasser i närvaro av en undvikande motståndare och härleda Vapnik-Chervonenkis (VC)-dimensionen för dessa, betecknad som den kontradiktoriska VCdimensionen. Vi visar sedan att prov komplexitet övre gränser från den grundläggande teorem av statistisk inlärning kan utvidgas till fallet med undvikande motståndare, där provet komplexitet kontrolleras av den kontradiktoriska VCdimension. Vi härleder sedan uttryckligen den kontradiktoriska VC-dimensionen för halvrymdsklassificeringar i närvaro av en provvis normkonstruerad motståndare av den typ som vanligen studeras för undanflyktsattacker och visar att den är densamma som standard VC-dimensionen och avslutar en öppen fråga. Slutligen bevisar vi att den kontradiktoriska VC-dimensionen kan vara antingen större eller mindre än standard VC-dimensionen beroende på hypotesklassen och motståndaren, vilket gör den till ett intressant studieobjekt i sig.
I ett senare arbete REF, Cullina et al. studera PAC-lärande garantier för binära linjära klassificeringar i den kontradiktoriska inställningen via VCdimension, och visa att VC-dimensionen inte ökar i närvaro av kontradiktoriska attacker.
PAC-learning in the presence of evasion adversaries
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}