De vanligaste begreppen om rättvisa i maskininlärning är statistiska definitioner: de fastställer en liten samling av hög nivå, fördefinierade grupper (såsom ras eller kön), och ber sedan om ungefärlig paritet av viss statistik av klassificeringen (som positiv klassificeringsfrekvens eller falsk positiv frekvens) i dessa grupper. Restriktioner av denna form är mottagliga för (avsiktlig eller oavsiktlig) rättvisa gerrymandering, där en klassificeringsgivare verkar vara rättvis för varje enskild grupp, men allvarligt bryter mot rättvisebegränsningen för en eller flera strukturerade undergrupper som definieras över de skyddade attributen (t.ex. vissa kombinationer av skyddade attributvärden). Vi föreslår istället att kräva statistiska begrepp om rättvisa i exponentiellt (eller oändligt) många undergrupper, definierade av en strukturerad funktionsklass över de skyddade attributen. Detta interpolerar mellan statistiska definitioner av rättvisa, och nyligen föreslog enskilda begrepp om rättvisa, men det ger upphov till flera beräkningsutmaningar. Det är inte längre klart hur man ens ska kontrollera eller granska en fast klassificering för att se om den uppfyller en så stark definition av rättvisa. Vi bevisar att det beräkningsmässiga problemet med att granska undergruppen rättvisa för både jämlikhet av falska positiva tal och statistisk paritet är likvärdigt med problemet med svagt agnostiskt lärande - vilket innebär att det är beräknings svårt i värsta fall, även för enkla strukturerade underklasser. Men det tyder också på att gemensamma heuristiker för lärande kan tillämpas för att framgångsrikt lösa revisionsproblemet i praktiken. Vi härleder sedan två algoritmer som tydligt konvergerar till den bästa rättvisa fördelningen över klassificeringar i en viss klass, givet tillgång till orakel som optimalt kan lösa det agnostiska inlärningsproblemet. Algoritmerna är baserade på en formulering av subgrupp rättvisa som en två-spelare nollsummespel mellan en Learner (den primära spelaren) och en Auditor (den dubbla spelaren). Båda algoritmerna beräknar en jämvikt av detta spel. Vi får vår första algoritm genom att simulera spel av spelet genom att låta Learner spela en instans av no-regret Följ Perturbed Leader algoritm, och ha Auditor spela bästa respons. Denna algoritm konvergerar tydligt till en ungefärlig Nash-jämvikt (och därmed till en ungefär optimal subgrupp-fair fördelning över klassificerare) i ett polynom antal steg. Vi får vår andra algoritm genom att simulera spel av spelet genom att ha båda spelarna spela Facticious Play, som har bara bevisligen asymptotic konvergens, men har fördelen av enkelhet och snabbare per steg beräkning. Vi implementerar den fiktiva Play-versionen med linjär regression som ett heuristiskt orakel, och visar att vi effektivt både kan granska och lära oss rättvisa klassificeringar på verkliga datauppsättningar.
REF minskar också problemet med att lära sig en klassificerare som uppfyller paritetsbaserade begrepp om rättvisa mellan undergrupper till problemet med revision; det skulle vara intressant om deras uppfattning om revision kan användas av människor som ett sätt att diagnostisera systematisk diskriminering.
Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}