Vi studerar kontradiktoriska perturbationer när instanserna är jämnt fördelade över {0, 1} n. Vi studerar både "inherenta" gränser som gäller för alla problem och alla klassificerare för ett sådant problem samt gränser som gäller för specifika problem och specifika hypotesklasser. Eftersom den nuvarande litteraturen innehåller flera definitioner av kontradiktorisk risk och robusthet, börjar vi med att ge en taxonomi för dessa definitioner baserat på deras direkta mål; vi identifierar en av dem som den som garanterar felklassificering genom att driva fallen till felregionen. Vi studerar sedan några klassiska algoritmer för att lära monotona associationer och jämför deras kontradiktoriska risk och robusthet under olika definitioner genom att attackera hypoteserna med hjälp av exempel hämtade från den enhetliga fördelningen. Vi konstaterar att dessa definitioner ibland leder till betydligt olika gränser. I denna studie förespråkas därför användningen av felregiondefinitionen, även om andra definitioner, i andra sammanhang med kontextberoende antaganden, kan sammanfalla med felregiondefinitionen. Med hjälp av fel-region definition av kontradiktoriska störningar, vi studerar sedan inneboende begränsningar på risk och robusthet för någon klassificering problem vars instanser är jämnt fördelade över {0, 1} n. Med hjälp av isoperimetrisk ojämlikhet för Booleska hyperkuben, visar vi att för initialt fel 0,01, finns det alltid en kontrarisär perturbation som ändrar O( ε n) bitar av fallen för att öka risken till 0,5, vilket gör klassifierns beslut meningslösa. Dessutom, genom att också använda den centrala gränsen teorem visar vi att när n → ❌, som mest c · ε n bitar av perturbationer, för en universell konstant c < 1.17, tillräckligt för att öka risken till 0,5, och samma c · ε n bitar av perturbationer i genomsnitt räcker för att öka risken till 1, vilket begränsar robustheten med c · ε n. * Detta är den fullständiga versionen av ett verk med samma titel som kommer att visas i NIPS 2018.
I synnerhet anser REF att monotona samband under den enhetliga fördelningen på booleska hyperkuben är robusta för detta riskbegrepp (däri kallas risken för felområde).
Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}