Game AI

Decision Learning(1) - Naive Bayes Classifiers

tsyang 2023. 11. 12. 00:18

개요

의사 결정 학습 중 가장 먼저 시도해야봐야 할 것은 나이브 베이즈 분류기(Naive Bayes Classifiers)이다. 

 

이건 구현하기도 쉽고 성능도 좋아서 학문적인 연구에서도 sanity check용으로 씀. 심지어는 많은 머신 러닝 연구들이 얘보다 못하기도 하다.

 

 

데이터

운전 중 코너링을 할 때 브레이크를 어디서 밟을지 학습하는 경우를 생각해보자. 이 때 AI는 플레이어의 실제 주행 데이터를 가지고 학습할 수 있다. 

 

플레이어의 실제 주행에서 (브레이크 여부 / 코너까지 거리 / 현재 속도)를 기록할 수 있고, 다음과 같은 데이터가 나왔다고 가정해보자.

 

brake? distance speed
ON 2 11
ON 4 70
OFF 65 80
ON 86 84
OFF 8.2 12.5
OFF 81 14.4
ON 5.6 64.9

 

 

위 데이터를 한번 더 단순화 해줄 수 있다. 다음과 같이

 

brake? distance speed
ON 가까움 느림
ON 가까움 빠름
OFF 멂 빠름
ON 멂 빠름
OFF 가까움 느림
OFF 멂 느림
ON 가까움 빠름

 

대충 거리가 10미만이면 '가까움', 아니라면 '멂'이라고 했으며, 현재 속도가 15미만이면 '느림' 아니라면 '빠름'으로 분류했다.

 

이런 단순화 작업은 학습을 빠르게 해주고 불필요한 데이터를 거를 수 있다. 가령, 위 데이터를 기록한 사람도 현재 속도가 '느리네', 혹은 '빠르네' 라고 생각하고 브레이크를 밟을지 말지 정하지 '현재 속도가 84만큼 빠르네'라고 생각하고 의사결정을 하지는 않았을 것이기 때문이다. (물론 현실적으로는 조금빠름, 매우빠름 이렇게 더 분류하겠지만..)

 

 

 

베이즈 정리 

자 그러면 AI가 코너까지의 거리와 속도로 브레이크를 밟을지 말지를 조건부 확률로 표현할 수 있다. 

 

$$P(brake? | distance, speed)$$

 

자 그러면 여기에 베이즈 정리를 적용할 수 있다.

 

$$ P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$

 

여기서 $\frac{1}{P(B)} = \alpha$ 라고 한다면 

 

$$ P(A|B) = \alpha{P(B|A)P(A)}$$ 

 

로 쓸 수 있다. ($\alpha$는 나중에 최적화를 위해서 따로 빼두었다.)

 

자, 그러면 브레이크를 밟을 조건부 확률을 다시 다음과 같이 정리할 수 있다.

 

$$P(brake? | distance, speed) = \alpha P(distance,speed | brake?)P(brake?)$$

 

근데 distance와 speed는 독립적이라고 볼 수 있으므로, 다음과 같이 정리할 수 있다.

 

$$ P(distance,speed | brake?) = P(distance | brake?)P(speed | brake?)$$

 

최종적으로 다음과 같은 식이 완성된다.

 

$$P(brake? | distance, speed) = \alpha P(distance | brake?)P(speed | brake?) P(brake?)$$

 

 

의사 결정

자 이제 현재 거리가 72고 속도가 12라고 해보자. 위에서 데이터를 단순화 한 조건에 따르면 거리는 '멂' 속도는 '느림'이다.

 

거리는 '멂', 속도는 '느림'일때 브레이크를 밟을 확률은 다음과 같이 표현할 수 있다.

 

$$P(brake? = ON | far , slow)$$

 

이걸 베이즈 정리를 이용한 식에 대입하면...

 

$$P(brake? = ON | far , slow) = \\ \alpha P(far | brake? = ON)P(slow | brake? = ON) P(brake? = ON) $$

 

여기에 이제 확률을 넣어볼 수 있는데,

 

브레이크를 밟았을 때, 거리가 멀 확률은 $\frac{2}{5}$ 브레이크를 밟았을 때 속도가 느릴 확률도 $\frac{2}{5}$ 이다.

 

그냥 브레이크를 밟을 확률은 $\frac{5}{7}$인데, 이런 값들은 'prior'라고 부르기도 한다. 조건부 확률이 얼마인가에 상관 없이 그냥 이 값이 엄청 낮다면 나머지 값들은 계산할 필요도 없이 그냥 0으로 가정해도 무방할 것이다. (최적화)

 

아무튼 정리하면 거리가 멀고, 속도는 느린 경우에 브레이크를 밟을 확률은...

 

$$P(brake? = ON | far , slow) = \alpha \frac{4}{35}$$

 

마찬가지로, 거리가 멀고 속도는 느린 경우에 브레이크를 밟지 않을 확률도 다음과 같이 구할 수 있다.

 

$$P(brake? = OFF | far , slow) = \alpha \frac{1}{14}$$

 

이제 이 두 확률을 비교하는데 $\alpha$는 어쩌피 상쇄되어 없어지므로 따로 계산할 필요가 없다. 이로써 거리가 멀고 속도는 느린 경우에는 브레이크를 밟는 것이 좋다는 판단을 내릴 수 있게 되었다. 

 

 

주의사항

실제 구현할 때는 나눗셈이 빈번하게 나타나서 부동소수점 정확도때문에 값이 부정확해질 수 있음. 이런 경우에는 로그를 쓰는 게 나음

 

 

 

참고 : Ian Millington, AI for GAMES 3rd edition, CRC press, [chapter 7]