인종 차별

1968년 주요 학생 시위 중 하나는 샌퍼낸도 밸리 주립대학(현 캘리포니아 주립대 노스리지)에서 일어났으며, 많은 아프리카계 미국인 학생이 소수자 학생에 대한 불평등한 대우에 항의했다. 인종, 성별, 그 밖의 차별은 오늘날에도 널리 퍼져 있다. 이를 맞서는 데에는 두 가지 어려움이 있다. 첫째, 실수로 차별하기 쉽다. 둘째, 그 결과 어떤 사람이나 기관이 의도적으로 차별했다는 사실을 입증하기 어렵다. 알고리즘과 기계 학습 기법이 중요한 결정을 내리거나 이끄는 데 점점 더 자주 쓰이면서, 차별이란 무엇인지, 그리고 그것에 어떻게 맞설지 정확히 이해하는 것이 시급하다.

의도적 차별이 있었을 가능성을 시사하는 쉬운 방법은 어떤 보호 범주들을 제시하여 결정이 그 범주에 따른 구분과 (거의) 완벽하게 일치함을 보이는 것이다. 예를 들어, 데이터가 백인 남성을 제외한 모든 성적 우수 장학금 신청이 거부되었음을 보여 준다면, 이는 차별 가능성을 높인다. 반면 차별 혐의에서 자신을 변호하려면, 결정을 (거의) 완벽하게 설명하는 비보호 범주를 가리킬 수 있다. 예를 들어, 성적 우수 장학금이 정확히 학점 3.8 이상이면서 교내 단체에 3개 이상 가입한 학생에게 주어졌다면, 이는 불법적인 선택이 없었음을 시사한다.

여기서는 관측된 데이터가 몇 개의 작은 수 c개의 범주만 보고 얼마나 쉽게 설명될 수 있는지 계산한다. n명의 개인과 m개의 범주에 대해, 각 개인이 그 범주에 속하는지와 그 개인이 장학금 대상으로 선정되었는지를 입력으로 받는다. 그런 다음, c개의 범주만 볼 수 있을 때 잘못 분류할 수 있는 개인의 최소 수를 결정해야 한다. 이 c개의 범주를 바탕으로 어떤 규칙이든 사용할 수 있다는 점에 유의하라. 예를 들어, 백인 남성과 아프리카계 미국인 여성 지원자는 모두 장학금을 받았고, 아프리카계 미국인 남성은 아무도 받지 못했으며 백인 여성은 한 명만 받았다면, "백인 남성, 아프리카계 미국인 여성, 그 외에는 아무도"라는 규칙으로 한 명(백인 여성)만 잘못 분류하게 된다. 즉, m개 중에서 c개의 범주를 임의로 고르고 그 c개의 범주를 임의로 조합하여 어떤 "장학금" 규칙이든 만들 수 있을 때, 그런 최선의 규칙을 사용하여 장학금 수혜 여부를 잘못 판정하게 되는 학생의 최소 수는 얼마인가?

첫 줄에는 파일에 들어 있는 입력 데이터 세트의 수 K ≥ 1이 주어진다. 그 뒤에 다음과 같은 형식의 데이터 세트 K개가 이어진다.

데이터 세트의 첫 줄에는 세 정수 n, m, c가 주어진다. 1 ≤ n ≤ 200은 개인의 수, 1 ≤ m ≤ 10은 범주의 수, 0 ≤ c ≤ m은 규칙에 사용할 수 있는 범주의 수이다.

그 뒤에 n개의 줄이 이어지며, 각 줄에는 m + 1개의 비트가 들어 있다. 처음 m개의 비트 ai,j는 i가 범주 j에 속하는지를 나타내며, 속하면 ai,j = 1이다. 마지막 비트는 개인 i가 장학금 대상으로 선정되었는지를 나타낸다.

각 데이터 세트에 대해 먼저 "Data Set x:"를 한 줄에 단독으로 출력한다. 여기서 x는 데이터 세트의 번호이다. 그런 다음, c개의 범주만 사용하는 어떤 규칙으로도 잘못 분류할 수 있는 개인의 최소 수를 출력한다.