문제의 난이도를 모델링 할 수 있을까?

Introduction

최근 들었던 확률과 통계에 대한 수업과,  AI&Data수업을 듣고 
평소에 궁금했던 부분에 대하여, 친숙한 예제를 가지고 사고 실험이라고 해야할까요. 
생각만 하지 말고 남겨보자 싶어 적어봤습니다.
흥미가 있으신 분은 같이 고민해보면 좋을것 같습니다.
키워드는 베이즈 정리($Bayes`\,\,\, Rule$)입니다.
 

평소 공부하다가  모르는 난관에 부딪혔을때, 이러쿵 저러쿵 고민해봐도 해결이 안되면 주위 사람에게 SOS신호를 보냅니다. 
쿡쿡 찔러서 아느냐 모르느냐를 묻는 식이죠. 
한번 더 확인을 거치는것은, 혹시나 간단히 해결되기를 기대하는 마음에서 일겁니다.
저는 모르지만 , 다른이는 알고 있어 해결이 된다면
다시말해, A=0, B=1이라면
->참인 상황이죠. 
->논리게이트로 치면 논리합/OR GATE라고 말할 수 있겠네요!
둘중 한명만 알아도 해결이 가능하니까요.
 

그런데 웬걸, 둘다 모르는 상황이 발생합니다.
A=0, B=0
이러한 상황에서는 
'아 어려운 문제인가?' 둘로는 해결이 안되나? 하고는 
이따금씩 쉬는시간에 강사님께 찾아가곤 합니다. 강사님은 항상1일테니까요!

"저(A)도 모르고 쟤(B)도 몰라요, 어려운 문제여서 질문하러 왔어요."
B를 거쳐간 것은 
문제가 정말 어렵다고 이야기하는, 겸손함 한 스푼을 더 얹기 위함이라고 말할 수도 있을것 같습니다.

그러면 겸손함의 추가를 위해 단번에 강사님에게 찾아가지 않고 여러명에게 물어 볼수도 있을것 같습니다.
A,B... 또 다른 동료 C,D...
이 과정은 진짜 문제가 어려운게 맞구나를 철저히 확인하려고 한다고 말할 수 있을 것 같습니다.
달리 표현하면 , $P_\hat{data}$ 가 $underlying\,\,distribution$를 모사하는 과정, 찾는 과정이라고 말할 수도 있을것 같습니다.
 

그런데 , 나 이외에 한 사람 더 모르는것을 확인하는것이 왜
나 혼자 모르는거 보다도 더 어려운 문제가 되는걸까요? 
나 말고도 다른 동료들, B가, C가... D가 모두 모른다면
왜 문제가 더 어려울것이라는 $confidence$가 증가하는걸까요?
이것을 수학적으로 어떻게 표현할 수 있을까요? 
'우리의 머신러닝 모델에는 이것을 어떻게 다룰 수 있을까?' 하는 궁금증이 생겼습니다.

MLE vs MAP

 
최근 수업시간에 확률을 바라보는 두가지 관점, MLE와 MAP에 대하여 배웠습니다.
서로 확률의 $best \,\,candidate$라고 씨름하는 두 녀석에 대하여,
머신러닝에서는 주어진 데이터의 분포가 $underlying\,\, distribution$이 되었으면 좋겠다. 
그래서 그놈을 통해서, 우리의 가설 함수 $h$가 $h^*_{real\,true}$에 $function \,\,approximiation$ 했으면 좋겠다. 라고배운것 같습니다.
흔히 우리가 하는 $task$들은 데이터를 통해 최적의 파라미터를 찾고, 
얻은 파라미터로 부터 $for\,\,unseen\,\,data$에 대하여 예측을 시도하는,
철저히 $MLE$ 관점이라고 까지 배운것 같습니다. (∵ $P(Data|θ)$ )

그러면 위와 같은 상황은 머신러닝의 통상적인 관점인 $MLE$로 모델링 할 수 있을까요? 
우선 해볼 수 있는 생각은 어떤 특정 문제에 대하여 각 사람이 해결할 확률을 $P(x_i)$라고하면
각 사람의 문제 해결능력은 모두 독립적으로 구성되어있다! 라고 가정하는 순간,
다음의 곱셈법칙이 성립하는것을 압니다. 

두 사람이 모두 문제를 해결할 확률
$$P(x_1∩x_2) = P(x_1) * P(x_2) $$
그러나 이러한 등식은 
4가지의 케이스 $(x_1={1,0} ,x_2={1,0})$ 에 대하여 
두사람의 문제해결력, 문제에 대한 접근 방법 등이 철저히 독립적이여야 가능한 식일겁니다. 
($MLE$는 사건들이 독립이라는 가정하에 계산 가능 합니다. ($\because$ $log\,\,likelihood$를 이용한 계산))
또한 이 식은 문제 자체의 어려움을 평가 하기보다,  
두 사람이 어려운 문제를 마주 쳤을때, 모두 문제를 해결 할 확률이 한사람이 해결할 확률 보다 낮아짐을 의미할 뿐입니다.
 
 

정답률과 오답률

 
또 다른 방법으로는 ,해결 정도의 지표로서 , 정답률과 오답률의 표현방법이 있는것 같습니다.
우리는 흔히 5지 선다 문제에서 정답률이 40%다 30%다.  어려운 문제 였다. 하는 이야기를 자주 들을 수 있습니다.
 
선지가 5개임으로  찍어도 20%는 맞는데 ,
심지어 어떤 문제의 정답률이 20%에 못미치는 상황은 사람의 문제 해결력이 개입해서 더 좋지 못한 결과를 내놓을리 없다.
문제가 잘못되었다. 이러한 주장도 종종 들립니다.
 
여기서 정답률이 40%라는것은 참가자 중에 문제를 맞춘 인원의 비율을 이야기 하는것일 겁니다.
$$정답률=P(\frac{count_{정답자}}{count_{정답자}+count_{오답자}})$$
그런데 각자의 문제 해결능력,
소위말해 수학 문제라면 수학실력이 다르고, 코딩테스트라면 코딩 실력이 다른데,
단순 $count$의 비율인 정답률과 오답률로 문제의 난이도를 평가 해도 괜찮은걸까요?
 

베이즈 정리

다음으로 베이즈 정리의 방법으로 다시 한번 생각해보겠습니다.
사후 확률을 계산하는 베이즈 정리는 다음과 같습니다.
 
$$P(D | \theta) = \frac{P(\theta | D) P(D)}{P(\theta)}$$

우리는 이 두사람 A,B의 평소의 문제 해결확률을 알고 있다고 가정합시다.
위 식의 $Data_{instance}$는 각 A,B 두사람이 될 것입니다.
또한 모델 $\theta$는 문제의 난이도에 따른 해결을 의미한다고 합시다.
 
A,B 이 두사람의 실력은 뛰어나서,
두 사람이 평소 주장하는 해결책이 올바른 해결책일 확률이 70%나 된다고 가정합시다.
그러면 틀린 해결책을 말하는 확률이 30%가 되고, 이는 사전확률, ($prior$) 이 됩니다.

70%라는 확률에 대해 조금 더 이야기 해보면,
평소 70%나 옳은 답을 뱉는 두사람이(어떤 문제에서든, 다시 말해 수학실력,코딩실력을 의미할 수 있겠습니다.)
특정 문제에 대해 모른다면 꽤 어려운 문제 겠구나! 하는 직관과 나름 일치합니다. 

이 두 사람이 올바른 해결책을 찾을 확률이 각각 70%라는 것은, 
해결책이 올바르다면 그들이 그것을 정확하게 판단할 확률이 70%라는 뜻과 상통합니다.
이를 $P(A|올바름)=0.7$과 $P(B|올바름)=0.7$으로 표현할 수 있습니다.

또한, $Marginal\,\,probabilty$ ,$P(올바름)$을 미리 알고 있다고 가정합시다. 
이는 우리가 아무런 정보 없이, 개인의 판단 없이 문제에 대한 특정한 해결책이 올바르다고 할 수 있는 확률입니다. 
여기서는 간단하게 50%라고 가정하겠습니다.
 (A나 B의 문제 해결력이 개입하지 않은 상태를 의미 합니다.)
 
여기까지의 가정을 통해, 앞선 베이즈 룰을 정리해보겠습니다.
 
$$P(D | \theta) = \frac{P(\theta | D) P(D)}{P(\theta)}$$
$$P(x_i | 올바름) = \frac{P(올바름 |x_i)P(x_i )}{P(올바름)}$$
여기서 $x_i$는 각 A또는 B입니다.

그러면 첫 번째 사람, A가 올바른 해결책을 찾았다고 주장한 후의 해결책이 올바를 업데이트된 확률을 구해봅시다. A가 올바른 해결책을 찾았다고 주장하는것은, $P(올바름|A)$을 의미합니다. (A가 올바른 해결책이라고 제시(주장)했고, 그것이 진짜 올바른 해결책)

이는 위의 식을 이항하면
$$P(올바름|A) = \frac{P(A|올바름) * P(올바름)} {P(A)}$$
이 됩니다.

여기서,
$P(A)$는 $A$가 해결책이 올바르다고 단순 주장하는 확률로, 
$P(A) = P(A|올바름) * P(올바름) + P(A|틀림) * P(틀림)$
으로 계산할 수 있습니다. (전확률 공식)
여기서 $P(틀림)$은 $1 - P(올바름)$이므로 50%입니다.
$ P(A|틀림)$은 해결책이 틀렸음에도 불구하고 A가 그것을 올바르다고 판단하는 확률이므로 30%입니다.

$P(A) = 0.7 * 0.5 + 0.3 * 0.5 = 0.5$
그러므로
$P(올바름|A) = \frac{0.7 * 0.5}{0.5} = 0.7$ 입니다.

 
 

B에 관한 정보 추가

다음으로, 두 번째 사람 B가 올바른 해결책을 찾았다고 주장한 후, 그 해결책이 올바를 확률을 업데이트 해봅시다.
$$P(올바름|B, A) = \frac{P(B,A|올바름) * P(올바름)} {P(B,A)}$$
를 계산해야 할것 같습니다.
$P(B,A)$는 A,B가 모두 제시한 해결책이 올바르다고 주장하는 확률로, 앞선 곱셈 정리를 이용하면 다음과 같이 계산 할 수 있습니다.
$$P(B,A)= P(B∩A) = P(B)*P(A)$$
A와 B는 모두 동일한 가정을 하고 있음으로 P(B)역시 0.5일 것입니다.
$$P(B,A)= P(B∩A) = P(B)*P(A) = P(B)*0.5 = 0.5*0.5=0.25$$

그러므로
$$P(올바름|B, A) = \frac{P(B,A|올바름)*0.5}{0.25}$$
 
마지막으로,
$P(B,A|올바름)$을 구하면 원하는 확률을 구할 수 있음을 압니다.
A와 B는 독립임으로 
$$P(B,A|올바름)=P(B|올바름)P(A|올바름)=0.7*0.7=0.49$$
$$P(올바름|B,A) = \frac{P(B,A|올바름) * 0.5}{0.25}$$
$$ = 0.49 * 0.5 /0.25 = 0.98 $$
 
 
 
따라서 올바른 해결책을 찾았다고 주장하면
그 해결책이 실제로 올바를 확률이 처음의 50%에서 한사람의 주장으로 70%, 다음 사람의 주장으로 98%로 증가합니다.
이는 베이지안 추론을 통해 신뢰도를 업데이트하는 방법을 보여주는 예입니다.

Application

우리는 단 2명으로도 주장의 신뢰도를 98%까지 표현할 수 있음을 알았습니다.
원래의 motivation대로 반대 연산을 생각해보면,
여러명의 사람이 문제에 대해 해결하지 못하면, 문제가 어려운 것이었을  "확률" 즉 신뢰도가 증가함을 알 수 있습니다.
 

그럼 더 나아가 이러한 문제 상황(이 문제가 얼마나 어려운가? )을 머신러닝 모델로 어떻게 구현해볼 수 있을지에 대한 질문과 
난이도를 어떻게 이야기 할 수 있는가? 에 대하여 풀기위해서는 결국
$x_{instance}$들의 문제 해결력에 관한 $feature$는 어떻게 구성 되어야 하는가?
 
우리는 간단한 예제를 풀기위해 많은 가정을 덧붙였지만
어떤 데이터로, 즉 어떤 $feature$가 문제해결력 70%를 구성할 수 있을까?
Marginal probabilty ,$P(올바름)$ ,  $P(D)$ 는 어떤 데이터로 구할 수 있을까? 
 
지금은 베이즈룰로 해결하려는 시도를 하였지만,
더 나은 모델은 무엇일까?
 
하는 꼬리 질문이 생기는 와중입니다.
모델에의 적용은 고민점들이 아직은 많이 남은것 같습니다.