구글맵의 현재 위치에 대한 정확도를 몹시나 흠모하고 있는 한 청년 입니다.
다름이 아니라 현재위치를 가져오는 과정중에 실내 실외에 대한 현재위치 정확도에 의문이 생겨 이것저것 검색을
해봐서 찾게된 내용이 있습니다.
찾은 내용으로 구글맵에서는 MLE (maximum likelyhood estimation) 기반의 알고리즘을 사용한다는 사실입니다.
기존에 사용하던 centroid-based technology 알골을 버리고 이 알골을 사용하면서 정확도가 30m 가량이 좋아졌다고 합니다.
그래서 바로 MLE 에 대해서 검색을 해 보았죠.. 그랬더니 최우추정법 이라고 나오고 그 아래에 이것에 대한 설명이라고 나와있는데
영 이해가 안가서 이렇게 글을 올립니다....
혹시 이 알골에 대해서 아시는분이 있으시다면 쉽게~쉽~게 설명좀 해주신 다면 감사 드리겠습니다. ^^
솔직히 이론만 말하면 이해가 잘 안가실테니 예제를 하나 들어드릴게요.
Exponential 분포를 가지는 함수에 대해서 설명해드리겠습니다.
이 바로 exponential함수의 pdf입니다.
f(x1 | 세타) * f(x2 | 세타) .... * f(xn | 세타)을 정리하면 아마 이런 값이 나올겁니다
(세타)^n * e ^((-x1-x2-x3....-xn)*세타)
여기에 자연로그를 취하면 다음과 같죠
n * ln(세타) + (-x1...-xn) * 세타
이걸 미분하면 다음과 같습니다.
(n / 세타) + (-x1 -x2 .... -xn)
이것을 0으로 하는 세타값이 최대값입니다. (n / 세타) + (-x1 -x2 .... -xn) = 0 을 계산하면
세타 = n / (x1+....+xn)입니다.
저 세타값은 평균값이고, 조금만 더 살펴보신다면 평균값이 1/세타임을 아실 수 있을 겁니다 !
(왜냐하면 x1+...+xn / n이 세타이기 때문이죠)
결론적으로 n개의 표본만 가지고도 알아내고자 하는 모집단의 평균을 구할 수 있게 됩니다.
구글맵도 아마 사용자 주위에 있는 몇 가지 spot을 가지고 MLE를 통해 답을 찾는것 같군요.
문제는 어떤 함수를 가정했을지 모른다는 것입니다. 그래서 저 기법을 사용한다는 것을 알고도 구글맵을 따라하긴 쉬울것 같지 않네요
결론 : 통계학과 수학을 전공하는 친구를 만드세요 ! (석사급 이상)
통계학에서 사용되는 알고리즘이네요.
정확히는 Maximum-Likelihood Estimation이라고, 추정기법 중에 하나입니다 !
말 그대로 Likelihood를 최대로 하는 추정인데요, 여기에는 미적분 기법이 들어가게 됩니다
여기서의 최대값을 통해서 가장 가능성이 높은 값을 도출해 내는 것이죠 !
예를 들어서 기린의 평균키를 알고 싶을 때, 시간과 비용의 문제 때문에 모든 기린의 키를 잴 수는 없습니다.
음 기린의 키 분포는 정규함수를 따르게 되겠죠?
근데 보통 이런 경우 기린 개개인의 키는 정규분포(또는 Gaussian)를 따른다고 가정하게 됩니다. 여기서 MLE를 사용하면 기린의 평균 키를 구할 수 있게 되는 것이죠.
좀 더 수학적으로 들어가보도록 하겠습니다.
서로 독립인 n번의 observation이 있다고 해봅시다. 기린의 키는 다른 기린들의 키에 영향을 당연히 안 줄 것이기 때문에 (가족이라던가 이런 유전적인 요소는 애초에 영향을 주지 않도록 실험군을 추출합니다) 서로 '독립'입니다.
기린이 어떤 키를 나타낼지 보여주는 밀도함수 f(x)가 있다고 했을 때, 사건 n번들이 모두 모여서 이루어지는 joint density function은 다음과 같습니다.
f(x1,x2,x3,....,xn | 세타)
그런데 앞에서 독립이라고 되어있었기 때문에 다음과 같은 공식이 성립합니다
f(x1,x2,x3,....,xn | 세타) = f(x1 | 세타) * f(x2 | 세타) .... * f(xn | 세타)
이 함수들은 모두 세타를 변수로 가지는 함수입니다. 양변에 자연로그를 취한 뒤 세타로 미분합니다.
그러면 다음과 같은 답이 나오는데 http://en.wikipedia.org/wiki/Maximum_likelihood 여기의 principles를 참고해주세요.
저 값을 최대로 하는 것을 찾는것이 바로 MLE입니다.