엘로 평점 시스템 (Elo Rating System)

Elo Rating

• 각종 게임이나 바둑, 체스 등 실력을 점수화시키는 곳이라면 널리 쓰이는 평점
  • 승률 : E(A) = 1 / (1 + 10^((B - A) / 400))
• 경쟁 게임이나 스포츠에서 개인이나 팀의 상대적인 강도를 표현하는 데 사용되는 숫자
  • 주로 두 선수나 팀 간의 예상 승률을 계산하는 데 사용
  • 이 Rating은 그들의 상대적인 강도 → 높을수록 상대적으로 강하다고 간주
  • 경기 결과에 따라 업데이트 됨
    • 이기면 Rating 상승
      • Rating이 낮은 선수가 높은 선수를 이기면 크게 상승
    • 지면 Rating 하강

https://ko.wikipedia.org/wiki/%EC%97%98%EB%A1%9C_%ED%8F%89%EC%A0%90_%EC%8B%9C%EC%8A%A4%ED%85%9C

엘로 평점 시스템 - 위키백과, 우리 모두의 백과사전

 

---

적용

1. 학생의 역량(theta)과 문제의 난이도(beta)값을 추정

시작값은 0

learning_rate(학습율)은 이전에 푼 문제가 많을수록 높아짐 (최대 0.04)

 

# theta 갱신
# is_good_answer : 맞추면 1, 틀리면 0
# nb_previous_answers : 이 학생이 이전에 푼 문제 수
def get_new_theta(is_good_answer, beta, theta, nb_previous_answers):
        return theta + learning_rate_theta(nb_previous_answers) * (
            is_good_answer - probability_of_good_answer(theta, beta)
        )

1. 학생이 문제를 맞춘다 (1)
   1. 학생 역량이 문제 난이도보다 높다 → probability_of_good_answer(theta, beta)가 1에 가깝다
      1. (맞출 문제를 맞춘거니깐) theta에 약간 증가
   2. 학생 역량이 문제 난이도보다 낮다 → probability_of_good_answer(theta, beta)가 0에 가깝다
      1. (틀릴 문제를 맞췄다) theta가 크게 증가한다
2. 학생이 문제를 틀린다(0)
   1. 학생 역량이 문제 난이도보다 높다 → probability_of_good_answer(theta, beta)가 1에 가깝다
      1. (맞출 문제를 틀렸다) theta가 크게 떨어진다.
   2. 학생 역량이 문제 난이도보다 낮다 → probability_of_good_answer(theta, beta)가 0에 가깝다
      1. (틀릴 문제를 틀렸다) theta에 약간 감소

 

2. theta와 beta를 사용하여 ELO 공식에 따라 학생이 주어진 문항을 맞출 확률을 계산

전체 코드

# df에서 학생과 comparison의 elo_function 구하기, df[new_elo]에 저장
def elo(df,comparison,new_elo):
    # Elo 공식을 사용하여 갱신된 theta(학생의 역량) 값을 계산
    # 정답유무, beta, 0, theta, 이전까지 답변 수
    def get_new_theta(is_good_answer, beta, theta, nb_previous_answers):
        return theta + learning_rate_theta(nb_previous_answers) * (
            is_good_answer - probability_of_good_answer(theta, beta)
        )
        
    # Elo 공식을 사용하여 갱신된 beta(문항의 난이도) 값을 계산
    def get_new_beta(is_good_answer, beta, theta, nb_previous_answers):
        return beta - learning_rate_beta(nb_previous_answers) * (
            is_good_answer - probability_of_good_answer(theta, beta)
        )
        
    # theta 학습률을 계산
    def learning_rate_theta(nb_answers):
        return max(0.3 / (1 + 0.01 * nb_answers), 0.04)
    
    # beta 학습률을 계산
    def learning_rate_beta(nb_answers):
        return 1 / (1 + 0.05 * nb_answers)

    # 정답을 맞출 확률을 계산
    # 학생의 역량이 문제 난이도보다 좋다면 맞출 확률이 높다
    # 학생의 역량에 비해 문제 난이도가 높다면 맞출 확률이 낮다
    def probability_of_good_answer(theta, beta):
        return sigmoid(theta - beta)

    # 시그모이드 함수를 계산
    def sigmoid(x):
        return 1 / (1 + np.exp(-x))

    # 파라미터 추정
    def estimate_parameters(answers_df, granularity_feature_name=comparison):
        # 각 문항 elo 준비
        item_parameters = {
            granularity_feature_value: {"beta": 0, "nb_answers": 0}
            for granularity_feature_value in np.unique(
                answers_df[granularity_feature_name]
            )
        }
        # 각 학생
        student_parameters = {
            student_id: {"theta": 0, "nb_answers": 0}
            for student_id in np.unique(answers_df.userID)
        }

        print(f"{granularity_feature_name} 매개변수 추정 시작!", flush=True)

        # 학생 id, 문제 id, 정답
        for student_id, item_id, answered_correctly in tqdm(
            zip(
                answers_df.userID.values,
                answers_df[granularity_feature_name].values,
                answers_df.answerCode.values,
            ),
            total=len(answers_df),
        ):
            # 현재까지 학생의 역량과 문제의 난이도 구하기
            theta = student_parameters[student_id]["theta"]
            beta = item_parameters[item_id]["beta"]

            item_parameters[item_id]["beta"] = get_new_beta(
                answered_correctly,
                beta,
                theta,
                item_parameters[item_id]["nb_answers"],
            )
            student_parameters[student_id]["theta"] = get_new_theta(
                answered_correctly,
                beta,
                theta,
                student_parameters[student_id]["nb_answers"],
            )

            # 이전까지 푼 문항 수에 1 추가
            item_parameters[item_id]["nb_answers"] += 1
            student_parameters[student_id]["nb_answers"] += 1

        print(f"{granularity_feature_name} 매개변수 추정 끝")
        print('--------------------------------------')
        return student_parameters, item_parameters

    # 시그모이드
    def gou_func(theta, beta):
        return 1 / (1 + np.exp(-(theta - beta)))
    

    print(f"Dataset of shape {df.shape}")
    print(f"Columns are {list(df.columns)}")

    # 학생과 아이템(문제번호 or 태그 or 시험지)의 파라미터 추정
    # 파라미터 학생의 역량, 아이템의 난이도
    student_parameters, item_parameters = estimate_parameters(df)
    
    # 학생의 역량
    prob1 = [
        student_parameters[student]["theta"]
        for student, item in zip(df.userID.values, df[comparison].values)
    ]
    
    df['student_parameters'] = prob1
    
    # 문제 난이도
    prob2 = [
        item_parameters[item]["beta"]
        for student, item in zip(df.userID.values, df[comparison].values)
    ]

    df['item_parameters'] = prob2
    
    # 각 학생이 해당 (문제,태그,시험지)를 맞출 확률(시그모이드) 구하기
    prob = [
        gou_func(student_parameters[student]["theta"], item_parameters[item]["beta"])
        for student, item in zip(df.userID.values, df[comparison].values)
    ]

    df[new_elo] = prob
		
    return df

 

---

결론

elo rating은 원래 두 팀(선수)간의 승률을 계산하는 시스템이다.

dkt의 문제 난이도를 추정하기 위해 사용하려고 했다. (학생의 역량과 문제의 난이도를 각각 팀(선수)라고 생각해 사용)

학생의 역량은 학생의 평균 정답률과 문제의 난이도는 문제의 정답률과 비슷한 추이를 보였다. 하지만 elo rating은 학생의 역량과 문제의 난이도가 서로서로 영향을 주기 때문에 누가 먼저 그 문제를 풀었냐에 따라 결과가 달라질 수 있다. 

따라서 이 시스템을 dkt에 적용하는 것은 적합하지 않다고 생각해 사용하지 않기로 결정했다.