sh.

Regression and Model Interpretation

2015-01-16T00:00:00+00:00

$m = b_0 + b_1 x_1 + b_2 x_2 + \ldots + b_p x_p$

Do you see? We model the $m$; we say the $m$ is a function of various things, the $x$'s. Maybe one of the $x$'s is age, another is sex, a third is income, a fourth is BMI, a fifth is height, a sixth is presence of some gene, a seventh is whether the individual is a science major, an eighth is whether the individual is Caucasian, a ninth is high school GPA, a tenth is SAT score, an eleventh, a twelfth, thirteenth, and on and on and so on some more. You'd never make it as a sociologist unless you can think of at least two dozen entries.

Consider that the $x$ which represents whether the individual is Caucasian increases m. That does not therefore mean whites have higher GPAs than non-whites. No no no no no. No. It says, very indirectly and after manipulation most people forget to or don’t do, that given this model and these $x$'s, the probability whites have higher GPAs than non-whites is greater than 50%. (The exact probability can be calculated.)¹

흔히 선형 모델을 만들고 각 요소의 regression weight로 현실을 해석하려 한다. 위의 인용에서 사용된 예를 살펴보자. 만약 코카시언의 여부가 GPA의 선형 모델의 피쳐로 들어가고 그 weight가 양수라고 하자. 이를 백인이, 백인이 아닌 사람보다 GPA가 높다고 해석해서는 안 된다. 위의 인용에서 볼 수 있다시피 이는 무척 많은 가정을 깔고 들어간 후에야 백인의 GPA가 백인이 아닌 사람의 GPA보다 높을 확률이 50% 이상이라는 설명을 할 수 있다.

Bayesian의 관점에서 생각해보면 regularization은 우리가 세상에 대해 갖고 있는 prior knowledge를 반영한 것이다. 단순히 predictive accuracy를 높이기 위해 다양한 방법으로 이런 prior를 검증을 해보고 이를 바탕으로 예측을 하는 것은 괜찮을 수 있다. 하지만 모델로부터 세상을 해석하려고 할 때의 문제를 살펴보자. Sparse linear model을 생각해보면 아예 subset selection 문제로 접근하는 것도 가능하고 ridge나 lasso 등의 regularization 문제로 모델링 하는 것도 가능하다.

위의 예에서는 Lasso가 가장 좋은 predictive accuracy를 내지만 이는 문제의 특성에 따라 달라질 수 있다. 가령 위의 예에서 best subset과 ridge만 비교한다면 best subset이 더 예측력이 높기 때문에 이게 현실을 해석하는 용도로 사용되어도 괜찮은 것일까? 그렇다면 svi는 암 발병에 영향을 전혀 주지 않는 요소라고 말해도 괜찮은 것일까? 반대로 best subset과 lasso를 비교해보면 svi가 양의 weight를 가지므로 svi가 암 발병의 원인이 된다고 말할 수 있는 것일까?

같은 방법이라도 regularization의 강도를 얼마나 주느냐에 따라 다른 결과를 얻을 수 있다. CV를 거쳐서 hyper parameter를 결정했기 때문에 이것으로부터 현실을 해석해도 되는 것일까? 이런 종류의 모델 읽기 실수는 무척 저지르기 쉽다. 언제나 이런 해석에는 주의를 기울여야 한다.²

Regression Isn’t What You Think ↩
이런 종류의 문제로 신뢰 구간, 유의 수준 등등도 있다. 진지한 연구자들조차 늘상 틀리는 개념들이다. ↩

확률과 대칭성

2014-10-04T00:00:00+00:00

Introduction

수학 문제를 풀 때 유용한 전략 중 하나는 문제에 숨어있는 대칭성을 찾아서 이를 활용하는 것이다.

어떤 여행자가 강의 한쪽 편에서 맞은 편으로 가고자 한다. 밤새 심한 폭풍이 몰아쳐서 각 다리가 독립적으로 50%의 확률로 끊어졌을 수 있다. 이런 상황에서 여행자가 여전히 맞은 편으로 갈 수 있는 확률은 얼마인가?

제일 먼저 떠오르는 것은 각 경우를 모두 세보는 것이다. 다리가 무너지지 않은 것을 1, 무너진 것을 0으로 표현하면 총 32가지의 경우가 있다. 이를 잘 세보면 총 16가지 경우에 다리를 건널 수 있는 것을 쉽게 확인할 수 있다. 그러므로 여행자가 강을 건널 수 있을 확률은 50%이다.

조금 다른 접근 방법으로 문제의 대칭성을 활용할 수 있다.

보트가 강을 따라서 지나가는 것을 상상해보자. 이 보트는 다리가 무너졌다면 거길 지나갈 수 있다고 가정하자. 이렇게 문제를 생각해보면 이는 위의 여행자 문제와 같은 구조를 지녔음을 알 수 있다. 다만 다리가 무너진 경우에만 지나갈 수 있는 것으로 문제가 변했을 뿐이다.

즉, 여행자가 다리를 건널 수 있는 확률과 보트가 강을 지나갈 수 있는 확률이 같다.

$p(여행자) = p(보트)$

또한 여행자가 다리를 건널 수 있다면 보트는 지날 수 없고, 그 반대의 경우도 성립한다.

$p(여행자) = 1 - p(보트)$

이를 바탕으로 여행자가 강을 건널 수 있는 확률은 50%임을 쉽게 확인할 수 있다.

Principle of Symmetry

위에서 본 것처럼 확률 문제에서 대칭성을 활용하여 문제에 쉽게 접근할 수 있는 경우가 종종 있다. 가장 대표적인 것이 선 위에 점이 떨어질 때의 대칭성을 활용하는 것이다.

어떤 구간에 $n$개의 점이 임의로 떨어지면, 생성되는 $n+1$개의 작은 구간은 평균적으로 같은 분포를 갖게 된다.¹

이를 받아들이는 것은 약간의 상상력이 필요할 수도 있지만 여기서는 그냥 받아들이도록 하자. 이제 이런 대칭성의 법칙을 활용해서 몇 가지 문제에 적용해보자.²

The First Ace

Q: 트럼프를 섞어서 뒷면이 보이도록 순서대로 한 장씩 나열하자. 이때, 처음으로 에이스를 만날 때까지 평균적으로 몇 장의 카드를 뒤집어야 할까?

총 카드가 52장인데, 그중 에이스가 네 장이므로 이를 제외하면 총 48장의 카드가 있다. 이를 하나의 구간으로 생각하면 에이스 네 장은 이를 총 다섯 개의 구간으로 나누게 된다. 대칭성의 법칙을 적용해보면 각 구간은 평균적으로 같은 분포를 가지므로 하나의 구간은 평균적으로 $\frac{1}{5} \times 48$의 길이를 갖게 된다. 이는 9.6이고 에이스를 뒤집기 위해 한 번 더 뒤집어야 하므로 평균적으로 10.6장의 카드를 뒤집어야 한다.

The Little End of the Stick

Q: 막대기 하나를 임의의 점을 잡아서 두 토막을 낸다. 작은 조각의 평균 크기는 얼마일까?

임의의 위치를 하나 정하는 것은 막대기 위에 점이 하나 떨어지는 것으로 생각할 수 있다. 점이 떨어지는 곳은 왼쪽 절반 혹은 오른쪽 절반으로 각 위치에 떨어질 확률은 50%로 같다. 만약 왼쪽 절반에 점이 떨어졌다면, 대칭성의 법칙에 의해 점이 구간을 절반으로 나누므로 전체 막대기의 절반의 절반이 작은 조각의 크기가 된다. 오른쪽 절반도 같은 논리로 계산할 수 있다. 그러므로 평균적으로 작은 조각의 크기는 막대기 길이의 $\frac{1}{4}$이다.

German Tank Problem

Q: 주축군에서 탱크를 만들면 각각의 탱크에 일련번호를 부여한다. 이는 만들어진 순서에 따라 1부터 순서대로 매겨진다. 어느 날 연합군이 60번의 일련번호가 붙여진 탱크를 포획했다. 주축군은 총 몇 대의 탱크를 만들었을까? 연합군은 60번 탱크 한 대만 관찰하고 다른 탱크의 존재 여부는 전혀 모른다고 가정하자.

이 문제는 당연히 맞는 답이 존재하지 않는다. 하지만 여러 가지 방법으로 접근해 볼 수 있는데, 그중 하나가 대칭성의 법칙을 적용하는 것이다. 60이라는 숫자가 1 ~ N까지의 구간에 떨어진 하나의 점이라고 생각하면 이는 평균적으로 이 구간을 절반으로 나눌 것이다. 그렇다면 왼편으로 59의 작은 구간이 생기므로 오른쪽으로 59의 구간이 있을 것이라고 가정하고 총 119대의 탱크가 있다고 할 수 있다.³

Discussion

변수에 대한 사전 확률이 균등 분포를 이룬다면 위의 법칙을 활용해서 꽤 복잡한 문제에 쉽게 접근할 수 있는 것을 살펴보았다.

사실 확률의 대칭성을 고민하는 것은 위에 언급된 것보다 훨씬 심오한 의미가 있다. 위의 예제에서는 어떤 확률변수가 균등한 분포를 가짐을 가정하였지만, 이런 사전확률을 알지 못할 때에도 비슷한 가정을 하고 문제에 접근하는 전략을 예전부터 많은 수학자가 활용하였다. 이는 일견 잘 동작하지만 여러 패러독스를 만들어냈고, 이를 잘 이해하기 위한 이론적 발전이 있었다. 이와 관련된 내용은 따로 다루지는 않겠다. 관심 있는 분들은 probability와 symmetry에 대해 찾아보면 다양한 자료를 접할 수 있을 것이다.

이를 혹자는 principle of symmetry라 부른다. ↩
다음의 문제는 Fifty Challenging Problems in Probability with Solutions에 나온 것들이다. ↩
다른 접근 방법으로 maximum likelihood (MLE) 계산을 하는 방법이나 uniform distribution의 conjugate prior로 Pareto distribution을 가정하고 베이지안 접근을 취하는 방법이 있다. 후자의 경우 본문에 푼 방법과 같은 결과를 얻을 수 있다. ↩

버스 대기 시간에 따른 전략

2014-03-26T00:00:00+00:00

Introduction

지난 글에서 버스를 기다릴 때 length time bias가 생기는 것을 살펴보았다. 이번 글에서는 지난 번에 논한 것을 바탕으로 시뮬레이션을 해서 최적의 전략이 무엇인지 찾아보도록 하자.

이번 글에서 다루는 버스 대기 시간과 거의 유사한 문제인 지하철 대기 시간과 관련된 문제가 Think Bayes에서 Red Line problem으로 소개 되고 있다. 문제의 큰 구조는 닮아 있고 세부적인 조건이 다르니 위의 내용도 함께 참고하면 도움이 될 것이다.

TL;DR 가장 좋은 전략은 빠른 버스는 무조건 타되 느린 버스는 한 대는 무조건 보내고 다음 버스를 타는 것이다. 이렇게 하면 평균적으로 약 3분의 이익을 보게된다.

Length Time Bias의 효과

Length time bias는 여러 관측치 중 "길이"가 긴 관측치가 관측될 확률이 더 높아지는 현상을 말한다. 이런 현상은 비단 버스 대기 시간 뿐만 아니라 여성의 유방암 검출 테스트의 효능이나 간헐천의 분출 시간에도 적용된다.

유방암 검출 실험의 효능도 length time bias에 의해 체감 효능과 실제 효능이 다를 수 있다. Credit: Wikipedia

이 분포에서 어떤 값이 뽑힐 확률은 관측되는 현상의 크기에 정비례한다. 이를 확률식으로 나타내보자. PDF가 $f(x)$ 인 분포에서 위와 같은 length time bias 현상을 관측한다면 새로운 PDF는 $g(x) = \frac{xf(x)}{\mu}$ 가 된다. 이제 새롭게 정의된 PDF에서 샘플링을 해보면 length time bias의 효과를 명확하게 확인할 수 있을 것이다.

각 버스의 조건을 명시해보자. 우선 버스의 배차 간격은 정규 분포를 따른다고 가정하자. 전에도 이야기했지만 이는 엄밀하게는 틀린 가정이지만 무시하도록 하겠다. 혹시 음의 값이 샘플링 된다면 절대값을 취하거나 버리도록 하자. 애초에 음의 값이 아주 가끔 나오기 때문에 이렇게 하여도 결과에 차이를 주지는 않는다. 느린 버스인 버스 A는 평균 3, 분산 0.5를 갖는다고 하고, 빠른 버스인 버스 B는 평균 15, 분산 2를 갖는다고 하자.² 아래 실험에서 샘플링은 PyMC의 MCMC를 사용하였다.

위의 차트는 평균이 3이고 분산이 0.5인 정규 분포와 length time bias가 된 정규 분포를 보여주고 있다. 여기에서 unbiased는 실제 버스 배차 간격의 분포를 의미하고, biased는 승객이 체감하는 버스 배차 간격의 분포를 뜻한다. 약간이지만 분명히 후자가 우로 편향된 경향이 있음을 알 수 있다. 보통 이렇게 히스토그램 혹은 PDF로 된 차트를 통해서 두 분포를 비교하는 것이 익숙하겠지만 이는 분포 사이의 차이를 명확하게 보기 어렵다. 더 좋은 방법은 CDF를 비교하는 것이다.¹

확연하게 차이가 있음을 알 수 있다.

같은 분석을 버스 B에 대해 해보자. 버스 B는 평균이 15이고 분산이 2이다.

버스 A에 비하면 미묘하지만 역시 차이가 있음을 확인할 수 있다.

위의 두 예로부터 실제 배차 간격과 승객이 느끼는 배차 간격에 차이가 있음을 확실히 볼 수 있었다.

이제 승객의 입장에서 실제 대기 시간은 어떨지 생각해보자. 승객이 버스를 타러 오는 것은 푸아송 분포라고 가정해도 무방할 것이다. 즉, 어떤 시점이든 다음 승객이 도착하는 것은 항상 일정하다는 것이다. 이는 한 명의 승객 입장에서 본인이 버스를 타러 오는 시간이 대체로 일정하다면 납득할 수 있는 가정이다. 그렇다면 승객이 도착하는 것은 버스의 배차 간격 사이에 균등한 확률로 일어나게 된다. 이를 살펴보면 다음과 같다.

버스 A는 약 3 ~ 4분을 기점으로 확률이 줄어들고, 버스 B는 대체로 균일한 분포를 유지하다가 15분이 넘어가면 확률이 줄어드는 모습을 보인다.

전략

이제 승객이 취할 수 있는 전략을 생각해보자. 가장 생각하기 쉬운 건 먼저 오는 버스를 타는 것이다.

이 전략의 간략한 통계를 내보자.

도착 시간의 평균: 15.8322420979
도착 시간의 표준편차: 2.20404813293
도착 시간의 중앙값: 16.2538419701

약 16분 가량이 걸림을 알 수 있다.

또 다른 전략으로 이전 글에서 언급한 전략을 사용할 수도 있다.

버스 B가 먼저 오면 버스 B를 탄다
버스 A가 먼저 오면 기다린 시간에 따라 다르게 행동한다
- 버스가 오기까지 기다린 시간이 $k$ 분이 안 되었으면 버스 A를 바로 탄다
- $k$ 분이 지났으면 기다렸다가 버스 B를 탄다

가장 좋은 $k$ 값은 grid search를 통해 쉽게 찾을 수 있다. 아래에서는 이 전략의 최적값인 $k$ 가 3분 15초인 경우의 분석 결과를 나타낸 것이다.

이 전략의 통계치는 다음과 같다.

도착 시간의 평균: 15.8198826852
도착 시간의 표준편차: 2.33185267677
도착 시간의 중앙값: 16.1961368496

기본 휴라스틱에 비해 아주 약간의 이득이 있다. 하지만 만족스러운 정도는 아니다.

조금 더 좋은 전략을 고민해보자. 방금 적용했던 전략은 구멍이 있는데, 버스 A를 한 번 보내더라도 다음에 오는 버스가 다시 버스 A일 수도 있다는 점이다. 이를 고려해서 일단 두 개의 시간 인자를 통해 첫 대기 시간과 두 번째 대기 시간을 변화 시키면서 결과를 비교해보자.

위의 차트는 살짝 보기 어렵지만 2차원 데이터를 1차원에 풀어 놓은 것이다. 코드로 표현하면 2중 루프를 도는데 외부 루프에는 첫 번째 인자를 놓고 내부 루프는 두 번째 인자를 변화 시킨 것이다. 그렇기 때문에 눈에 띄는 주기성이 생기게 된다. 의미 있는 부분만 따로 살펴보자.

첫 번째 대기 시간은 각기 다른 선으로 나타나 있고 두 번째 대기 시간은 $x$ 축에 나타나 있다. 이를 보면 첫 번째 대기 시간은 짧은 것이 좋고 두 번째 대기 시간은 긴 것이 좋음을 알 수 있다. 위의 결과대로 전략을 짜보자.

버스 B가 먼저 오면 버스 B를 탄다.
버스 A가 먼저 온 경우 그냥 보낸다.
- 두 번째 대기에는 먼저 온 버스를 탄다.

히스토그램만 봐도 이 전략이 앞의 두 전략보다 더 좋은 결과임이 자명하다. 이 전략의 통계를 내보면 다음과 같다.

도착 시간의 평균: 12.8397689782
도착 시간의 표준편차: 1.96981428863
도착 시간의 중앙값: 12.8200249915

앞서 논한 두 전략에 비해 약 3분 정도의 이득이 있었다.

Discussion

최종 전략을 다시 살펴보자. 이를 간단하게 말해보면 첫 버스가 B라면 그냥 타고 A라면 그냥 보낸다. 그 다음에 오는 버스는 A, B에 무관하게 무조건 타면 된다. 마지막 전략은 기본적인 휴리스틱에 비해 약 3분 가량의 득이 있다. 두 번째 버스는 무조건 타는 편이 기다리는 것에 비해 이득이기 때문에 이 전략이 아마 이 프레임에서는 최적이 아닐까 싶다.

이전 글과 이 글을 작성하는데 사용된 코드는 다음의 주소에서 찾아 볼 수 있다.

http://nbviewer.ipython.org/gist/shurain/d4b4790d011db914e608

Think Bayes의 저자도 같은 논지의 이야기를 한다. ↩
분산의 크기는 문제의 조건으로 주어지지 않았으므로 임의로 설정하였다. ↩

버스 대기 시간

2014-03-24T00:00:00+00:00

Introduction

얼마 전 지인 중 한 명이 다음의 문제를 페이스북에 공개하였다. 흥미로운 부분이 있기에 이를 논해보고자 한다.

학교에서 집까지 가는 방법은 버스 A를 타고 10분 동안 이동한 뒤 내려서 5분 동안 걸어가는 방법과 버스 B를 타고 8분 동안 이동한 뒤 내려서 1분 동안 걸어가는 방법이 있다. 버스 A의 배차간격은 3분이고 버스 B의 배차간격은 15분이라고 알려져 있다. (위의 상수는 임의의 숫자로 변경될 수 있음) SeoulBus나 버스정류장의 전광판 등 버스의 도착 예정 시간을 알 수 있는 방법이 없다고 할 때, 어떤 기준으로 버스를 타야 도착 시간의 기대값을 가장 빠르게 할 수 있을까?

문제가 조금은 복잡해 보이지만 정리해보면 다음과 같다.

버스 A: 배차 3분 이동 15분
버스 B: 배차 15분 이동 9분

얼핏 생각해보면 평균적으로 버스 A를 기다리는 시간은 1.5분이고 버스 B는 7.5분으로 각각 더하면 16.5분의 같은 값을 갖는 걸로 보인다. 그렇다면 나의 전략은 가장 먼저 오는 버스를 타는 것일 터이다. 과연 그럴까?

문제 설명에 주어진 것만으로는 이 문제를 풀 수 없다. 몇 가지 추가적인 가정이 필요한데, 가령 배차 간격의 분포 등이 필요하다. 그리고 그 가정에 의해 문제의 복잡도가 달라지는데 이는 length time bias 때문이다.

Length Time Bias

만약 버스가 정확하게 15분 혹은 3분의 배차 간격을 두고 운행이 된다면, 평균적으로 내가 버스를 기다리는 시간은 각각 7.5분과 1.5분이 된다. 하지만 정확하게 시간을 지키지 않고 평균적으로 그 정도의 시간만 지키면서 조금씩 달라질 수 있다면 결과가 달라지게 된다. 왜냐하면 버스 배차 간격이 긴 경우에 내가 정류장에 도달할 확률이 그렇지 않은 경우보다 높기 때문이다.

앞서 지나간 버스와 이를 뒤따르는 버스 사이의 시간 간격을 배차 간격이라 하자. 배차 간격이 주어진 경우에 승객이 정류장에 도달하는 것은 균등 분포를 따른다. 그러므로 기대 대기 시간은 배차 간격의 절반이 된다. 하지만 승객이 정류장에 도착하는 것이 균등하다면 더 큰 배차 간격에 떨어질 확률이 높다.

Credit: Mahalonobis

위의 이미지에서 $X_i$ 는 배차 간격, $\bar{W}$ 는 평균 대기 시간이다. 이는 위의 삼각형으로 이루어진 함수의 평균 값이 된다. $$\bar{W} = \frac{1}{t} \sum_{i=1}^n \frac{1}{2} X_i^2$$ 평균 대기 시간은 전체 시간인 $t$ 를 버스의 총 개수인 $n$ 으로 나눈 값이므로, $$\bar{W} = \frac{1}{2}\frac{\bar{X^2}}{\bar{X}}$$ 이다.

Poisson/Exponential 분포

만약 버스가 도달하는 사건이 푸아송 분포를 따른다면, 그 배차 간격은 지수 분포를 따를 것이며 다음의 수식을 만족한다.

$$Var(X) = \bar{X}^2$$

그리고 분산은 제곱의 평균 - 평균의 제곱이므로,

$$\bar{X^2} = 2\bar{X}^2$$

이를 활용하면,

$$ \bar{W} = \bar{X}$$

가 된다. 사실 이런 방법을 쓰지 않더라도 지수 분포는 memoryless 성질이 있어서 승객의 도착 시간과 무관하게 평균 대기 시간은 항상 같으므로 $\bar{W} = \bar{X}$ 임을 알 수 있다.

정규 분포

$$Var(X) = \sigma^2$$

위와 같은 방법을 사용하면,

$$\bar{X^2} = \sigma^2 + \bar{X}^2$$

이를 똑같이 대입하면,

$$\bar{W} = \frac{1}{2}\frac{\sigma^2 + \bar{X}^2}{\bar{X}}$$

이다.

만약 배차 간격이 정확하게 지켜진다면 분산은 0이 되고 그렇다면 $\bar{W} = \frac{1}{2} \bar{X}$ 가 될 것이다.

엄밀하게 말하자면 정규 분포는 음의 값을 가질 수 있으므로 배차 간격을 모델링하기에 적합하지 않다. 하지만 현실에서는 버스 사이의 배차 간격을 운전수들이 조절하려고 노력하기 때문에 (표준 편차가 현실적이라면) 배차 간격이 지수 분포를 따르지 않는 경우를 모델링 할 수 있을 것이다.

전략

버스 배차 간격이 지수 분포를 따른다면 자명하게 먼저 오는 버스를 타는 것이 가장 좋은 전략이다. 버스 B가 먼저 도착한다면 당연히 버스 B를 타는 것이 좋고, 버스 A가 먼저 도착하더라도 버스 B가 도착하기까지의 기대 대기 시간이 15분이기 때문이다.

만약 버스 배차 간격이 정규 분포를 따른다면 어떨까?

버스 B가 먼저 도착하면 당연히 버스 B를 타면 된다. 버스 A가 먼저 도착한다면 다음 버스 B가 도달하는 시간을 추론해 볼 수 있다. 내가 버스 A를 $\alpha$ 분 만큼 기다렸다면 버스 B가 도착하기까지 평균적으로 $\frac{\sigma^2 + 225}{30} - \alpha$ 분 남았다고 생각할 수 있다.¹ (분산이 충분히 작아서 무시할 수 있다고 가정하면) 남은 평균 대기 시간은 $7.5 - \alpha$ 분이다. 지금 당장 버스 A를 타면 15분 후에 집에 도착하게 되고, 버스 B를 기다렸다가 타면 평균적으로 $7.5 - \alpha +9 = 16.5 - \alpha$ 분 후에 집에 도착하게 된다. 결국 내가 1.5분 이상 버스 A를 기다렸다면, 버스 B가 오기를 기다렸다가 버스 B를 타고 내려가는 것이 평균적으로 집에 더 빠르게 도착하는 방법이 된다.

Discussion

이번 글에서는 아주 간략하게 length time bias를 소개하고 이에 따른 버스 대기 시간의 변화에 대해 논하였다. 그리고 아주 단순한 전략을 소개하였는데, 다음 글에서는 최적 전략이 무엇인지 알아보도록 하겠다.

다만 이미 $\alpha$ 분 만큼의 시간이 지나는 동안 버스 B가 오지 않았으므로 이에 대한 부분은 확률 계산에서 빼주어야 정확한 계산이 된다. 하지만 정확한 계산은 쉽지 않다. 일단은 이 부분에 대한 고민은 무시한다. ↩

StumbleUpon Evergreen Classification Challenge

2013-11-08T00:00:00+00:00

Introduction

지난 8월 Kaggle에서 StumbleUpon Evergreen Classification Challenge가 있었다. 이번 대회는 사용자에게 웹 문서를 추천해주는 서비스인 StumbleUpon에서 주최한 대회였다. StumbleUpon이 서비스를 제공하면서 어떤 종류의 글은 발행 후 시간이 어느 정도 지나면 사람들에게 추천해주기 좋지 않은 반면 어떠한 글은 발행 후 시간과 무관하게 사람들에게 추천할 가치가 있는, 서로 다른 성격을 지닌 글이 있음을 알게 되었다. 이를 각각 "ephemeral"과 "evergreen"이라고 이름 지었는데, 대회의 목표는 웹 문서를 수집한 그 시점에 ephemeral과 evergreen의 여부를 가리는 것이었다.

자연어 처리와 관련된 프로젝트를 제대로 해 본적이 없어서 이번 대회에 도전하게 되었다. 처음 목표는 상위 20%에 드는 것이었는데 최종 결과는 기대보다 훨씬 좋아서 총 625팀 중 22위를 하게 되었다. 1위가 AUC 점수 0.88906이었고, 내가 0.88495였으니 아주 큰 차이가 있지는 않았다고 생각한다. 사용한 방법도 크게 다르지 않았던 것으로 보인다.

Details

분류를 할 수 있도록 주어진 데이터는 크롤러가 수집한 HTML 웹 문서와 후처리를 통해 이로부터 뽑아낸 다양한 정보였다. 후처리로 뽑아낸 정보로는 URL, HTML 문서에 포함된 텍스트 정보 등의 기본적인 정보 외에도 문서 압축률, 링크 개수 등의 다양한 정보를 포함하고 있었다. 자세한 내용은 Get the Data 페이지의 표를 참고하면 된다.

채점 기준은 area under the ROC curve였으며 늘 그러하듯 답안을 csv로 만들어서 제출하도록 하였다.

My Approach

처음에는 기본적인 data exploration을 수행하였다. 우선 주어진 데이터를 살펴보면 boilerplate 라는 이름의 피쳐가 있었는데, 여기에 HTML 문서에서 뽑아낸 텍스트 데이터가 있었다. 이 피쳐와 문서의 URL 등 몇 가지 당연히 유의미할 것으로 추정되는 피쳐가 있었으나 반대로 다른 다양한 피쳐들은 과연 쓸모가 있을지 의심스러웠는데, 실제로 몇 가지 실험을 해보니 거의 의미 없는 피쳐였다. 간단한 실험 후에 문서의 제목, URL, 본문을 주된 베이스로 사용해서 분류를 시도하기로 하였다. 이런 종류의 문제에 적합하게 TF/IDF 피쳐를 뽑아서 사용하였는데, 위에서 언급한 피쳐를 한데 모아 사용하였다. 학습은 Stochastic gradient descent를 시작점으로 사용했다. 기본적인 사항이 결정된 뒤의 실험은 꽤 지루했는데, 다양한 조합의 피쳐와 다양한 학습 알고리즘을 사용해서 결과가 어떻게 변하는지 cross validation을 통해서 확인하였다.

최종적으로 제출한 모델은 다음과 같다. 우선 주어진 HTML 문서로부터 boilerpipe를 사용하여 본문의 텍스트만 뽑아내고, 이를 word2vec으로 의미 있는 phrase 단위로 묶도록 하였다. 이렇게 해서 만들어진 데이터와 URL, 제목, 본문을 합쳐서 TF/IDF 벡터를 만들어서 피쳐로 삼았다. 이 피쳐를 bagging을 3,000회 반복해서 총 3천 벌의 데이터를 생성하고, 각 데이터를 SGD로 학습시켰다. 이렇게 만들어진 3천 개의 모델의 예측치를 평균내어 이를 제출하였다.

Post-mortem

이번 대회에서는 활용해본 기법이 꽤 다양했다. Naive Bayes, logistic regression, SVM, kNN 등 기본적으로 활용할 수 있는 분류기는 전부 한 번 씩은 써본 것 같다. 대체로 random forest가 여러 도메인에서 아주 훌륭한 성능을 보이지만 내가 사용한 scikit-learn은 sparse한 데이터를 다루는 random forest 구현이 없었다. 차원 감소를 해서 몇 가지 시도를 해보았는데, PCA, K-means clustering 등으로 접근해 보았지만 득을 보지는 못하였다. 우승자는 PCA한 것을 random forest로 학습시키고 logistic regression 결과와 앙상블을 하였다고 하니 나의 접근 방향이 잘못된 것은 아니었던 것으로 보인다. Boosting을 잘 활용하면 좋은 결과를 얻을 수 있지 않을까 싶었지만 큰 소득은 없었다.

피쳐 생성도 신경을 조금 써봤는데, word2vec 등을 활용한 phrase 생성도 있었고, 휴리스틱 기반으로 글의 댓글만 떼어내어 이를 활용한 것도 있었다. 나중에는 잘못 분류된 데이터를 살펴보며 시간을 꽤 보냈는데, 사람이 직접 만든 레이블이라 오류도 적지 않게 있는 것으로 보였다. 대회 시작 후 2주 정도 되었을 때 흥미가 확 떨어진 계기가 있었는데, 잘못된 분류를 자주 하는 데이터를 살펴보니 스포츠일러스트레이티드 사이트의 문서가 몇 개 트레이닝 데이터로 끼어 있고 이를 제대로 분류하지 못하고 있었다. 실제 웹 페이지를 보니 사진만 잔뜩 있고 글이 거의 없는 페이지들이었다. 이런 식으로 사실상 유의미한 분류가 불가능해 보이는 도메인이 여럿 있었다. 그리고 당연히 트레이닝 데이터와 테스트 데이터에 그런 도메인의 분포가 달랐다. 결국 이런 관찰은 나의 CV 결과를 얼마나 신뢰할 수 있는지에 대한 의구심으로 이어졌다. 퍼블릭 리더보드 점수를 높이려고 노력하다가 오버피팅하기 십상이라는 결론을 내리고 그 시점 이후로 더 점수를 올리려고 시도하지 않았다.

이런 대회에 참가하면 늘 느끼는 것 중 하나가 빠른 분류기의 중요성이다. 실험 한 번이 너무 오래 걸리면 흥미도 떨어지고 흐름도 끊기게 마련이다. 요즘은 그래서 가능하면 속도가 빠른 리니어 러너를 활용하고 차선으로 트리 기반의 기법을 애용한다. 빠르게 실험을 할 수 있으면 무엇보다 흐름이 덜 끊기고 다양한 아이디어를 실험해 볼 수 있어서 특히 이런 대회에서 매우 좋다.

평소에 늘 이런 기회가 생기면 새로운 도구를 하나씩 손에 익히려고 시도를 해보곤 하는데, 이번 대회에서는 sofia-ml를 그럭저럭 사용해볼 수 있었다. Deep learning을 활용해보고 싶어서 pylearn2를 살펴보긴 하였는데 실제로 활용할 수 있는 수준까지는 익히지 못하였다.

처음 시도해본 NLP 프로젝트였는데, 생각보다 성적이 좋아서 기분이 좋았다. 지난번 Kaggle 대회 시도 이후 느낀 바가 있어 계속해서 이런저런 공부를 하였는데 그 결과가 보이는 것 같다.

Naive Bayes Classifier

2013-10-31T00:00:00+00:00

Introduction

스팸 문서 판별에 가장 쉽게 사용할 수 있는 기계 학습 기법으로 나이브 베이즈 분류기가 있다. 최근에 이와 관련된 간단한 발표를 할 일이 있어서 관련 자료를 만들어 보았다. 대부분의 내용은 Mathematicalmonk의 Naive Bayes classification 영상을 참고하였다.

Naive Bayes

자세한 이야기는 발표 자료를 참고하기로 하고, 몇 가지 언급하고 싶은 것들만 짚어보도록 하겠다.

Conditional Independence

나이브 베이즈에서 "나이브"라는 이름이 붙은 이유는 레이블이 이미 주어졌다고 가정하면 (conditional), 피쳐들이 서로 독립이라는 (independence) 가정 때문이다. 이는 패러미터를 유추하는 작업을 쉽게 만들기 위해서 도입되었다고 생각되는데, 다행히도 문서를 다룰 때에는 이러한 독립성 가정이 잘 동작하는 편이다.

Bayes Theorem & Bayesian Inference

나이브 베이즈의 "베이즈"는 베이즈 정리를 사용한 부분에서 나온 것이다. 그저 베이즈 정리를 사용할 뿐이지 딱히 베이지안 추론 기법은 아니라는 점을 이해하는 것이 중요하다. 베이지안 추론 기법은 모델의 패러미터를 전부 고려하여 이를 적분해버리는 것이 골자이지 베이즈 정리를 사용하는 것이 핵심이 아니다. 대부분의 나이브 베이즈 구현은 모델 패러미터를 maximum likelihood estimate을 사용하여 추정하는데, 이는 point estimate에 불과하고 진정한 의미의 베이지안은 아니다. 베이지안에 대해 더 알고 싶다면 이를 잘 정리한 WHAT IS BAYESIAN/FREQUENTIST INFERENCE?를 참고하기 바란다. 위의 글에서 Nate Silver의 책 Signal and the Noise 혹은 Sharon McGrayne의 책 The Theory That Would Not Die 등에서 행하는 흔한 실수에 대해 논한다.[1]

[1]: 이에 대한 더 자세한 글로 동일 저자의 글인 Nate Silver Is A Frequentist도 있다.

Code Sprint 2013 Round 2 Post-mortem

2013-08-27T00:00:00+00:00

Introduction

지난 글에서 내가 어떤 방법을 사용해서 Code Sprint 라운드 2에서 우승을 할 수 있었는지 설명하였다. 이번엔 지난 글에서 못다 한 이야기와 만약 나에게 주어진 시간이 충분했더라면 어떤 식의 접근을 했을지를 논하는 일종의 post-mortem을 이야기해보자.

Bayesian Story

기존 대회에서는 주어진 데이터를 posterior sample이라고 가정하고 문제에 접근하였다. 하지만 이는 제대로 된 베이지안 방식의 접근이 아니다. 조금 더 세련된 베이지안 접근을 취해보자.

Prior distribution을 만든다.
Likelihood 계산을 위한 모델을 만든다.
Bayes' theorem을 사용하여 posterior distribution을 계산한다.
Posterior distribution에 대한 expected loss를 최소화한다.

Data Generation Model

우리는 예측에 앞서 각 데이터를 생성하는 분포에 관심이 많다. 이는 만약 데이터를 생성하는 분포를 정확하게 알 수 있다면 우리가 원하는 만큼 데이터를 생성하고 이를 활용하여 예측에 사용할 수 있기 때문이다. 데이터가 어떤 방식으로 생성 되었는지에 대한 직관은 데이터를 살펴보면 얻을 수 있는 경우가 많다.

위의 차트는 1번 도로 하행선의 08:00의 4월 데이터이다. 살펴보면 대부분의 경우는 시속 20km 정도의 평균 시속을 보이지만 간혹 시속 80km에 가깝게 튀는 데이터들이 있다. 이는 주말에 차가 몰리지 않아서 생기는 현상이라고 결론짓고 넘어갈 수도 있지만 자세히 보면 그런 데이터의 절반은 평일에 일어난 데이터이다. 이를 토대로 다음과 같은 가설을 세울 수 있다.

하루하루 도로의 시간대별 평균 속도를 생성하는 분포는 두 개 있다.

즉, 평균적인 데이터를 생성하는 분포와 (1번 모델) 이상한 데이터를 생성하는 분포 (2번 모델) 두 개가 있다는 가정을 하는 것이다. 이제 데이터 생성 스토리를 만들어보자.[1]

For each road
1. Choose p ~ Uniform(0, 1)
2. Choose assignment ~ Bernoulli(p)
3. for each timepoint t:
    a. Choose μ[1](t), μ[2](t) ~ Uniform(0, 120)
    b. Choose σ[1](t), σ[2](t)~ Uniform(0, 100)
    c. μ(t) = μ[1](t) if assignment = 0 else μ[2](t)
    d. σ(t) = σ[1](t) if assignment = 0 else σ[2](t)
    e. Generate data d ~ Normal(μ(t), σ(t))

간단히 말해서, 임의의 확률로 두 모델 중 하나가 선택이 되고, 그에 맞는 정규 분포로부터 데이터가 생성된다는 이야기이다. 위의 생성 프로세스를 잘 살펴보면 기존의 접근 방법에서 취하던 각 시간별 데이터의 독립성이 사라졌음을 알 수 있다. 각 시간은 assignment에 의해 서로 연관이 되어 있다.

Posterior Distribution and Expected Loss Minimization

Prior distribution과 likelihood 계산을 위한 모델은 위의 데이터 생성 스토리에 모두 나타나 있다. 이제 이를 사용해서 μ(t)와 σ(t)의 posterior 분포를 계산해보는 것이 가능하다. Posterior distribution을 구하는 방법은 여러 가지가 있지만 나는 MCMC 기법을 활용하였다. 앞서 본 4월 데이터를 살펴보자.

μ와 σ의 posterior distribution p의 분포

위의 posterior 분포를 보면 1번 모델은 대체로 20 정도의 μ를 중심으로 하고 있으며 2번 모델은 약 82 가량의 μ를 중심으로 하고 있음을 알 수 있다. 이는 위의 차트에서 확인할 수 있는 결과와 잘 맞아 떨어진다. 즉, 이를 통해 학습이 어느 정도 그럴싸하게 되었다는 것을 알 수 있다.

모델의 Posterior distribution을 얻어내면 이를 사용해서 데이터를 내가 원하는 만큼 생성할 수 있다. 이렇게 생성한 데이터가 진짜 분포로부터 생성된 데이터라고 가정하고 expected loss minimization을 행하면 된다. 기존 접근에서는 각 시간이 독립이므로 바로 중앙값을 취하면 그것이 최적해였지만 이제 한 번에 예측해야 하는 것이 벡터이므로 바로 중앙값을 계산하는 것은 불가능하다. 그러므로 임의의 해를 생성하여 그 해의 expected loss를 계산하고 이 해를 더 나은 해로 고치는 방식의 최적화를 통해서 expected loss를 minimize 한다. 이런 optimization을 위한 각종 최적화 라이브러리들이 많이 있으므로 이를 활용하면 된다.

Result

위의 예에서는 08:00의 데이터만 사용하였지만 위의 데이터 생성 스토리대로 각 도로의 24시간이 전부 연결되도록 한 번에 posterior를 생성할 수 있다. 하지만 예측해야 하는 변수가 도로별로 총 1,152개 (288개 시간 구간, μ, σ 각 두 개씩) 이므로 굉장히 많은 연산이 필요하다. 이를 쉽게 수행할 방법이 없어서 한 번에 두 시간 구간만 서로 연결이 되어 있다고 가정하고 학습을 하였다. 즉, 시간 t와 t+1이 공통의 p를 공유한다는 가정하에서 μ와 σ의 분포를 구해보았다.

학습 시간이 매우 오래 걸려서 MCMC의 iteration 회수를 많이 줄여서 학습시켰다. 이렇게 되면 통계적으로 안정적인 분포를 구할 수 없게 되므로 iteration 회수를 높이면 더 나은 결과를 얻을 수 있을 것이라는 기대를 할 수 있다. 시간적인 문제로 모든 도로에 대한 학습은 하지 못하고 몇 개의 도로만 뽑아서 결과를 비교해 보았다.

도로 1 하행선
중앙값 사용 12.38968749999999
새 모델 사용 12.438159722222231

도로 10 하행선
중앙값 사용 2.760173611111111
새 모델 사용 2.9523258511926551

중앙값을 사용했을 때 전체 도로의 평균 loss가 4.7263이었음을 고려하면 도로 1은 예측과 크게 빗나간 예이고 도로 10은 예측과 아주 잘 맞아떨어진 예이다. 결과를 보면 여전히 중앙값을 사용한 모델이 더 좋지만 새 모델도 그에 근접하는 결과를 내는 것을 알 수 있다. 이 기법이 충분한 학습 시간을 할당 받지 못한 것을 고려하면 매우 고무적인 결과라 할 수 있다.

Model Averaging

중앙값을 사용했던 기존 결과보다 더 나은 결과를 내는 방법이 있다. 바로 모델 간의 평균을 사용하는 것이다. 즉, 중앙값을 사용한 모델과 위의 베이지안 접근 방법을 통해 얻은 모델의 결과를 평균 내는 것이다. 이 간단한 기법이 놀랍게도 더 나은 결과를 가져다준다.

도로 1 하행선
12.387465277777775

도로 10 하행선
2.8562497311518831

아예 예측치가 매우 정확한 경우에는 (이미 예측이 충분히 좋으므로) 별 소득을 얻지 못했지만 그렇지 못했던 도로 1을 보면 두 모델보다 더 나은 결과를 얻어 내었다. 이는 bias-variance tradeoff[2] 때문이다. 서로 다른 두 모델을 평균 내면서 variance가 떨어져서 예측의 정확도가 높아지는 것이다.

Future Works

아직도 더 나은 예측을 위해 개선할 여지는 많이 남아 있다.

요일별 median 분포의 차이

위의 차트를 보면 명백한데, 주중 데이터에도 도로마다 요일별 차이가 큰 경우가 많다. 우리가 예측하고자 했던 것은 화요일이니 화요일의 분포에서 크게 벗어나는 부분은 제거하는 것이 더 나은 결과를 내는데 도움이 될 것이다.

다른 한 가지 개선 방법은 더 나은 데이터 생성 프로세스를 생각해내는 것이다. 가령 위의 예에서는 정규 분포에서 데이터가 생성된다고 가정하였는데 이는 거짓말이다. 평균 시속은 절대 음수가 나올 수 없는데 위의 모델에 따르면 음수의 속도가 뽑힐 확률이 존재하기 때문이다. 더 그럴싸한 이야기를 만들 수 있으면 더 나은 결과를 얻을 수 있을 것이다. 그 밖에도 cross validation을 통해 어떤 데이터에 대해 좋지 않은 결과를 내는지 파악해보고 이를 해결할 수 있는 방법을 고민해보면 계속해서 예측을 개선해 나갈 수 있을 것이다.

Conclusion

Base model 보다 더 낫거나 최소한 그와 비슷한 결과를 내는 방법을 대회 참가 때에는 내놓지 못해서 아쉬움이 남았었는데 이번 분석을 통해서 그 아쉬움을 조금 달래보았다. 데이터 분석 및 base model과 MCMC를 활용한 모델의 소스 코드는 Github의 저장소에 공개해두었다.

[1]: 보통 plate notation을 많이 사용하지만 개인적으로는 모델의 이해에 큰 도움이 되지는 않는다고 생각한다. 이와 같은 의견은 여기에서 볼 수 있다.

[2]: Bias/Variance Tradeoff를 참고하기 바란다.

Code Sprint 2013 Round 2

2013-07-20T00:00:00+00:00

Introduction

SK planet에서 정기적으로 Code Sprint라는 프로그래밍 경진 대회를 주최한다. 얼마 전에 Code Sprint 2013의 라운드 2 결과가 나왔는데 운이 좋게도 내가 1위를 할 수 있었다. 이번 대회의 목표는 과거의 교통정보 데이터를 사용하여 미래의 교통정보를 예측하는 것이었다.

대회 페이지의 설명을 그대로 옮겨보면,

코드스프린트 Round2 문제에서는 2013년 4월부터 6월까지 3개월간의 T map 경부고속도로 교통정보를 제공하고 개발자는 이를 분석하여 7월 16일 24시간의 교통정보를 예측합니다.

자세한 내용은 공식 페이지를 방문하면 확인할 수 있다.

Exploratory Data Analysis

이런 식의 문제를 접하면 먼저 해야 하는 것이 몇 가지 있다. 가장 중요한 것 중 하나가 데이터를 살펴보는 것이다. 흔히 exploratory data analysis라고 하는데, 데이터를 살펴보고 이를 토대로 적절한 가설을 세우거나 앞으로의 진행 방향 등을 결정하기 위해서 반드시 필요한 작업이다.

전체 데이터를 한 눈에 보는 것은 쉽지 않지만 개별 도로의 정보는 상대적으로 시각화하기 쉽다. 다음의 차트는 1번 도로의 일별 데이터를 시간축으로 자른 차트로, x축은 날짜를 (4월 1일부터 6월 30일까지) y축은 평균 시속을 (km/s) 의미한다. 빨간 선은 일요일을 의미하며 녹색 선은 공휴일이다 (현충일, 석가탄신일).

01:15의 데이터 19:20의 데이터

전체 데이터 애니메이션 보기

위의 애니메이션을 보면 쉽게 알 수 있는데, 도로의 평균 속도는 매우 빠르다가 (약 100 km/h) 시간이 지나면서 매우 느려졌다가 (약 20 km/h) 다시 빨라지는 양태를 띄는 것을 알 수 있다. 또한 데이터를 가만히 살펴보면 주중과 주말의 양상이 많이 다른 것을 알 수 있다. 반면 주중의 움직임 끼리는 간혹 서로 다른 경우가 있지만 대체로 비슷한 것을 알 수 있다. 이를 토대로 다음과 같은 가설을 세울 수 있다.

주말의 데이터와 주중의 데이터를 따로 처리하는 편이 더 나은 예측을 하는데 도움을 줄 것이다.

더 데이터를 자세히 살펴보면 얻어 갈 수 있는 것이 많겠지만 대회에 참가할 때는 시간적 여유가 별로 없어서 이 정도만 살펴보고 바로 모델 생성에 들어갔다.

Statistical Model

많은 것들이 그러하듯 문제를 설명하는 모델을 만드는 작업도 매우 단순한 것을 만들어서 이를 baseline으로 삼고 조금씩 전진하는 것이 옳다. 가장 직관적으로 떠오르는 방법 중 하나가 과거의 데이터의 평균치 등을 미래의 예측치로 바로 사용하는 것이다. 매우 직관적이고 구현도 쉬운 방법이다. 실제 구현은 평균이 아니라 중앙값(median)을 사용하였는데, 이는 문제에서 주어진 loss function이 MAE (mean absolute error) 이었기 때문이다. 그리고 앞서 살펴보았듯, 전체 데이터를 사용하지 않고 주중의 데이터만 뽑아서 사용하였다. 놀랍게도 이번 대회의 우승 모델이 바로 이 방법이었다. 이러한 단순한 모델도 몇 가지 가정하에서 매우 그럴싸한 선택임을 보일 수 있다. 이를 설명하기 전에 문제를 Bayesian framework에서 접근해보자.

우리가 원하는 것은 하루하루 도로의 시간대별 평균 속도를 생성하는 분포를 모델링하는 것이다. 우리는 이 분포가 어떻게 생겼는지는 잘 모르지만 적어도 그 분포로부터 뽑아낸 샘플이 있다 (문제에서 주어진 데이터). 이는 Bayesian framework에서 보면 우리에게 posterior sample이 있는 셈이다. 이제 expected loss를 최소화하는 "답"을 우리의 예측치로 내놓으면 된다. 헌데 하나의 "답"이 추정해야 하는 변수가 72,576개나 된다 (상행/하행 * 126개 도로 * 288개 시간). 이상적이라면 이 모든 것을 한 번에 예측하는 것이 좋겠지만 상대적으로 많은 변수에 비해 우리가 가진 샘플의 개수는 고작 90여 개 (주중 데이터만 놓고 보면 60여 개) 밖에 되지 않는다 (4 ~ 6월 데이터). 이는 필연적으로 overfitting 문제로 귀결된다.

Overfitting 문제를 피하기 위해 모델을 단순화하는 가정을 추가해볼 수 있다. 가령 각 시간대별 데이터는 서로 독립이라고 가정해보자. 실제로는 앞 시간대의 교통 상황에 이후의 도로 상황이 큰 영향을 받겠지만 이를 무시하면 문제가 훨씬 접근하기 쉬워진다. 이제 우리는 동시에 72,576개의 변수를 추정해야 하는 것이 아니라 한 번에 한 개의 변수만 추정하면 되고 이를 72,576회 반복하면 되는 것이다. 그런데 이렇게 놓고 보니 주어진 posterior sample에 대한 expected loss를 최소화하는 답은 각 시간대별 중앙값이 되어버린다. 결국 시간대별 데이터의 독립을 가정하면 중앙값을 취하는 것이 최적의 선택이라는 결론을 얻을 수 있다.

Thoughts

실제 대회에 참가할 때 위의 모델을 만드는 것은 얼마 걸리지 않았다. 그리고 이를 더 개선하는 방법을 고민해보았는데 뾰족한 수가 별로 없었다. 일단 가장 큰 문제는 예측을 해야 하는 날이 주어진 데이터로부터 보름가량 이후의 일이라는 것이었다. 상식적으로 생각해봐도 보름 전의 도로 상황이 보름 후의 도로 상황에 영향을 줄 것이라고 생각하기 힘들다. 결국 평범한 regression 문제로 접근하는 것은 잘못된 방법이라고 판단을 내렸다. 결국 더 나은 예측을 위해서는 baseline 모델에서 가정한 것을 더 완화해야 했는데 이는 쉽지 않았다. 가장 큰 문제는 데이터의 부족이었다. 예측해야 하는 변수를 2개로 한정 짓고 Gibbs sampling을 해보려고 하였으나 간단한 테스트 결과 overfitting 문제에 빠지기 십상임이 판별되었다. 지금 와서 드는 생각이지만 데이터를 더 면밀하게 살펴보는 쪽으로 일찌감치 생각을 돌리고 더 현실적인 posterior sample을 골라내는 방법을 생각해봤어야 했다. 아쉽게도 실제 대회에서는 그쪽으로 생각이 미치기 전에 대회가 마감되었다.

대회에 세 개의 예측치를 제출할 수 있었는데 고민하다가 Gradient boosting regression을 활용한 방법을 두 개 추가로 제출하였다. Regression이 개념적으로는 틀린 접근 방법이라고 생각했지만 지푸라기 잡는 심정의 접근이었다고 고백한다. 마감 시간이 얼마 남지 않아서 패러미터 튜닝조차 제대로 하지 못하고 제출하였기에 예상대로 결과는 중앙값을 사용한 모델의 결과에 미치지 못하였다.

대회 자체에 대한 몇 가지 아쉬움이 있다. 많은 사람들이 생각했겠지만 단 하루의 데이터를 예측하는 것은 결코 통계적인 안정성을 보장할 수 없다. 내가 1위를 하게 된 것도 많은 부분 운이 따라줬기 때문이라고 생각한다. 그리고 과거 데이터도 더 많이 제공했더라면 좋지 않았을까 하는 아쉬움도 남는다. 실제로 어떻게 될지는 모르겠지만 이렇게 했더라면 overfitting 문제가 약간은 해결되지 않았을까 기대하기 때문이다. 또한 보름 후의 데이터 예측이라는 측면도 논란의 여지가 있다고 여기는 사람들이 꽤 있을 것으로 생각한다. 그리고 마지막으로 서로의 결과를 비교해 볼 수 있는 과정이 있었으면 좋았을 것 같다. 내가 얼마나 잘 했는지 전혀 평가가 되지 않는 상황이라 많은 사람들이 흥미를 금방 잃었을 것으로 생각한다.

어찌 되었든 참가를 마음먹고 문제에 대해 고민한 3, 4일간 매우 즐거웠다. Baseline model보다 더 나은 것을 만들어보려고 고민하는 과정은 고통스럽지만 즐거운 경험이다. 이런 멋진 대회를 준비하고 진행한 SK planet 에게 감사를 표한다. 아마 다음 포스팅은 정답 세트를 놓고 기존에 사용한 접근 방법 및 새로운 방법들의 비교를 하는 일종의 postmortem이 되지 않을까 생각한다.

Text Segmentation

2013-05-02T00:00:00+00:00

Introduction

모든 기계학습 기법이 그렇듯 CRF도 주어진 데이터에 따라 체감할 수 있는 성능 차이가 크다. 기계학습은 데이터를 바탕으로 어떤 모델을 만들어내는 방법이라고 생각할 수 있는데, 주어진 데이터가 우리가 원하는 모델을 만들어 내는데 필요한 정보를 갖고 있지 않으면 이는 불가능하다.

Pedro Domingos는 기계학습을 정원을 가꾸는 것에 비유했다. [1]

Seeds = Algorithms
Nutrients = Data
Gardener = You
Plants = Program

기계학습의 엄청난 강점은 굉장히 많은 일을 데이터가 대신 해준다는 것이다. 기존의 프로그래밍을 생각해보면 프로그래머가 모든 프로그램을 작성해야 했다. 그러나 기계학습에서는 어떤 특정한 일을 하는 프로그램을 만들기 위해서 기본적인 기계학습 알고리즘에 데이터를 잔뜩 부어 넣어서 목표로 하는 프로그램을 만들어낸다. 이는 마치 정원사가 정원에 씨앗을 심고 약간만 신경을 써주면 거의 대부분의 일을 자연이 해주는 것과 유사하다. 하지만 이는 결국 데이터가 아주아주 중요하다는 것을 알 수 있다. 쓰레기 데이터를 넣으면 쓰레기 결과가 나올 수 밖에 없다. [2]

Text Segmentation

지난 글에서 CRF를 개략적으로 살펴보고 이를 한국어 띄어쓰기에 적용한 예를 살펴보았다. 지난 예에서는 한국어 위키백과의 데이터를 사용하여 띄어쓰기를 위한 CRF를 학습하였다. 이 모델은 표준어를 띄어 쓰는 것은 꽤 잘한다. 그러나 구어체 혹은 비속어 및 비문, 오타 등을 마주치게 되면 잘 처리하지 못하는 모습을 보여준다.

원본: 아근데어무리생가해도이주인격같에
기존 교정: 아근데어_무리생가해도_이주_인격같에

이는 당연한 현상인데, 한국어 위키백과에 구어체, 비속어 및 비문 등은 거의 없을 것이기 때문이다. 데이터가 힘든 일을 대신 해줘야 하는데, 데이터가 이를 못하는 상황인 것이다. 이를 해결하기 위해서 구어체 등을 포함한 데이터를 넣어줄 필요가 있다.

지난 글에서 각주에 언급했지만 사실 좋은 데이터를 구하는 것은 어려운 일이다. 대규모 서비스를 운영하는 입장에서는 그런 데이터가 충분히 있겠지만 재미삼아 하는 입장에서는 데이터 획득이 만만한 일이 아니다. 지난 번에는 한국어 위키백과 자료를 활용했는데, 이번에는 엔하위키의 데이터를 추가하였다. [3] 엔하위키는 위키백과에 비해 상대적으로 덜 딱딱하고 구어체에 가까운 문법을 사용하는 것을 볼 수 있으며, 많은 종류의 인터넷 용어도 포함하고 있다.

실질적으로 지난번과 달라진 것은 크게 없다. 대용량 처리를 위해 다양한 라이브러리를 시도해보긴 했으나 [4] 모두 CRF를 사용하고 비슷한 종류의 최적화 기법을 바탕으로 학습을 하게 되어 있어서 큰 차이는 없다고 보면 된다. 사실상 달라진 부분은 데이터를 한국어 위키백과만 사용하던 것에서 엔하위키의 데이터를 포함한 것뿐이라고 생각하면 된다. 그러나 데이터만 달라져도 결과의 품질은 크게 달라진다.

단적인 예를 좀 보면,

원본: 아근데어무리생가해도이주인격같에
기존 교정: 아근데어_무리생가해도_이주_인격같에
새 교정: 아_근데_어무리_생가해도_이주인격_같에

원본: 먹는거조심하슝곧중간이자나ㅠㅠ
기존 교정: 먹는_거조심하슝_곧_중간이자나_ㅠㅠ
새 교정: 먹는거_조심하슝_곧_중간이자나ㅠㅠ [5]

결과물이 극적으로 좋아졌는데, 이는 새로 추가한 말뭉치가 이러한 종류의 데이터를 잘 소화할 수 있는 모델을 만드는 데 큰 도움을 준 것임을 쉽게 유추할 수 있다.

[1]: Machine Learning by Pedro Domingos

[2]: Garbage in, garbage out

[3]: 엔하위키

[4]: CRF 학습에 필요한 메모리가 꽤 커서 AWS를 활용하였다.

[5]: 트위터에서 임의로 수집한 테스트 케이스이다.

Conditional Random Field

2013-04-16T00:00:00+00:00

Introduction

Conditional random field는 (CRF) 레이블의 인접성에 대한 정보를 바탕으로 레이블을 추측하는 기계학습 기법이다. CRF를 활용하여 여러 가지 재미있는 것들을 할 수 있는데, 이를 활용하는 방법에 대해 이야기하겠다. [1]

하지만 그래도 CRF가 어떤 식으로 동작하는 지 대충은 알아야 하니 대략적인 설명을 해보도록 하자. 보통 품사 태깅을 (Part-of-speech tagging) 예로 많이 드니, 이를 예로 들도록 하겠다. [2]

Part-of-Speech Tagging

다음과 같은 문장이 주어졌다고 가정하자.

"Bob drank coffee at Starbucks"

각 단어에 품사를 붙여보면 다음과 같다.

"NOUN VERB NOUN PREPOSITION NOUN"

전통적인 supervised learning 기법을 적용한다고 생각해보면 트레이닝 데이터가 있을 것이고 데이터로부터 의미 있는 특징을 (feature) 뽑아내는 과정이 있을 것이다.

CRF에서는 특징 함수를 (feature function) 정의하여 사용한다. 특징 함수는 문장과 해당 문장을 구성하는 단어들의 위치 및 레이블 정보를 입력으로 받아서 어떤 실수를 (주로 0, 1) 출력하게 된다. 각 특징 함수는 개별적인 가중치를 갖는데, 결국 어떤 문장이 주어지면 어떤 레이블이 얼마나 적합한 레이블인지를 weighted feature sum으로 계산하게 된다.

특징 함수의 장점은 임의의 특징을 표현하는 것이 가능하다는 점이다. 몇 가지 특징 함수의 예를 들어보면 다음과 같다.

만약 i 번 레이블이 ADVERB 이고 "-ly"로 해당 단어가 끝나면 1, 아니면 0을 리턴하는 함수
만약 i 번 레이블이 VERB 이고 문장이 물음표로 끝나면 1, 아니면 0을 리턴하는 함수
만약 i-1 번 레이블이 ADJECTIVE이고 i번 레이블이 NOUN이면 1, 아니면 0을 리턴하는 함수

보는 바와 같이 특징 함수는 매우 자유로운 형태를 띌 수 있다. CRF는 이처럼 자유롭게 특징 함수를 만들고, 각각의 특징 함수에 가중치를 부여하고 그 합을 구해서 사용하게 된다. 최종적으로 문장이 주어졌을 때, 특정한 레이블이 얼마나 그럴싸한지는 해당 레이블의 점수를 (weighted feature sum) 모든 가능한 레이블의 점수로 나눠주면 된다.

가중치를 어떤 식으로 학습하는지, 다른 종류의 더 복잡한 CRF에 대한 설명은 생략하기로 하고 이런 CRF를 어떻게 다른 용도로 활용하는 것이 가능한지 살펴보자.

Different Uses

CRF는 특징 함수를 매우 자유롭게 설정할 수 있기 때문에 다른 유용한 것들을 할 수 있다. 가령 띄어쓰기가 되어 있지 않은 문장을 자동으로 띄어쓰기 해주는 것이 가능하다. 어떤 문장이 주어졌을 때, 레이블로 각 문자마다 여기서 띄어쓰기를 해야 하는지 아닌지 정보를 0/1로 주는 것을 상상할 수 있다. 가령,

CRF로띄어쓰기를해보자

라는 문장이 주어진 경우, 올바른 형태는

CRF로_띄어쓰기를_해보자

일 것이다. 여기에 레이블을 붙여보면,

C/0
R/0
F/0
로/1
띄/0
어/0
쓰/0
기/0
를/1
해/0
보/0
자/1

정도로 붙여보는 것이 가능하다. 이런 식으로 레이블이 붙어 있을 때, 이로부터 유용한 띄어쓰기 정보를 뽑아내는 특징 함수만 만들어 주면 CRF를 사용해서 이를 학습할 수 있다. 가령 어떤 문자가 나타난 경우 그 앞의 문자와의 관계 등을 특징 함수에 넣어주는 것을 쉽게 상상할 수 있다. 한국어 위키피디아 등의 데이터를 활용하면 쉽게 트레이닝 데이터를 만들 수 있고, 바로 CRF로 학습을 하면 끝이다. [3]

[1]: 자세한 이야기는 매우 복잡하지만 남들이 쌓아둔 개념/도구를 가져다 사용하는 것은 공학자의 미덕이다.

[2]: Edwin Chen의 Introduction to Conditional Random Fields를 참고하였다.

[3]: 사실 우리말로 된 유용한 말뭉치 집합을 얻는 것은 매우 어렵다. 그런 맥락에서 한국어 위키피디아 문서는 아주 좋은 데이터셋이다.

Bayesian Approach to the Price is Right's Showdown

2013-03-12T00:00:00+00:00

지난 글에서 Observing Dark Worlds 대회에 1, 2위가 사용한 방법을 설명하면서 Bayesian 방식으로 문제에 접근하는 이야기를 했었다. 이런 Bayesian 방식을 쉽게 잘 설명한 글로 How to solve the Price is Right's Showdown이라는 블로그 글이 있다.

이 글은 The Price Is Right이라는 TV 쇼의 마지막 대결 The Showcase를 Bayesian 방식으로 풀어보는 시도에 대한 이야기하고 있다. 문제에 대한 자세한 정보는 원문을 참고하길 바란다.

전체적으로는 prior belief를 설정하고 likelihood 계산을 위한 모델 설정 뒤에 PyMC 라이브러리를 사용하여 MCMC 계산을 한다. 그리고 loss function을 정의하여 그에 따른 expected loss optimization을 수행하는 전통적인 구조를 잘 보여준다. 같은 기법이 다른 문제에 적용된 사례이니 지난 글의 내용이 잘 이해가 되지 않았던 분들은 한 번 읽어보시면 도움이 될 것이다.

글의 내용은 오픈 소스 책인 Probabilistic Programming and Bayesian Methods for Hackers in Python의 내용을 따와서 많이 수정하여 만들었다고 한다.[1] 아직 책의 내용을 살펴볼 기회는 없었지만 기초적인 Bayesian 기법에 대해 실제로 사용해보는 것을 위주로[2] 쓰여 있다고 하니 이런 내용에 관심 있는 사람들은 한 번 보면 좋을 것이다.

[1]: 책 저자가 블로그 글쓴이

[2]: 사람들이 질려 할만한 수학은 가능하면 2순위로 미루고

Dark World Part II

2013-02-20T00:00:00+00:00

Introduction

지난 글에 이어 Observing Dark Worlds 대회에 대한 이야기를 계속하겠다. 이번에는 1, 2위가 사용한 방법의 큰 그림을 그리면서 가능하면 자세하게 설명을 하고자 한다.

본인들이 직접 자신들의 방법을 설명한 글은 다음의 링크에서 볼 수 있다.

Decision Theory

1, 2위의 전략에 대한 설명에 앞서 decision theory에 대한 이야기를 간단하게 하도록 하겠다.

어떤 선택이 얼마나 좋은 선택이었는지 판단하기 위해서 우리는 선택의 성과를 측정할 수 있어야 한다. 보통 이런 때에는 loss function이라는 개념을 도입하여 이를 설명한다. 직관적으로, loss function은 선택의 결과와 관련된 "비용"을 나타내게 된다. 적은 비용이 드는 선택이 큰 비용이 드는 선택에 비해 좋은 것은 자명하다.

이제 우리는 선택의 성과를 측정하는 방법이 생겼으니 좋은 선택과 나쁜 선택을 구분할 수 있다. 이런 설정에서 앞으로 나아갈 자연스러운 방향은 loss의 기대값을 최소화하는 방향으로 이어지게 된다. 즉, 우리는 미리 정해진 loss function이 주어지면 expected loss를 최소화하는 어떤 선택 전략을 찾아서 이를 사용하면 된다. 그래서 실제로 expected loss를 최소화하는 문제를 푸는 시도를 하게 되는데, 이 문제를 풀다 보면 결국 posterior distribution의 계산을 해야 하는 문제에 당면하게 된다. 즉, posterior distribution의 계산이 우리의 관심사가 되게 된다.

Decision theory와 관련된 내용은 Mathematicalmonk의 decision theory 관련 동영상을 참고하기 바란다.

Bayesian Approach

전에도 언급했지만 1, 2위가 사용한 기법은 전통적인 베이지안 접근 방법이었다. 베이지안 접근 방법은 다음과 같다.

Prior distribution을 만든다.
Likelihood 계산을 위한 모델을 만든다.
Bayes' theorem을 사용하여 posterior distribution을 계산한다.
Posterior distribution에 대한 expected loss를 최소화한다.

이게 도대체 무슨 뜻인지 이야기를 해보자.

베이지안 접근 방법은 결국 세상 모든 것을 어떠한 확률식으로 표현하는 것으로 생각해볼 수 있다.[1] 우리가 보통 궁금해하는 것은, 앞 절에서도 설명하였지만, posterior distribution이다. 이는 주어진 데이터와 모델을 설명하는 모델 패러미터에 대한 식으로 나타날 수 있다.

위의 수식에서 D는 우리가 관측할 수 있는 데이터이고 θ는 모델을 설명하는 모델 패러미터라고 하자. Posterior distribution은 좌변을 가리키고 likelihood는 우변의 좌측에 있는 항이며 prior distribution은 우변의 우측에 있는 항이다.

우리는 보통 어떤 데이터를 가지고 있고, 이를 토대로 모델에 대한 것을 알고 싶어 한다. 하지만 posterior distribution을 바로 계산하기는 쉽지 않다. 그렇지만 어떤 모델과 데이터가 있을 때, 그 likelihood를 계산하는 것은 상대적으로 쉬운 문제이다. 그리고 prior distribution은 결국 우리가 데이터를 관측하기 전에 각 모델이 어떤 분포를 이루고 있는지에 대한 믿음을 확률식으로 표현한 것이다. 이 두 값을 활용하여 posterior distribution을 계산하는 것이 가능하다. [2]

위의 접근 방법을 거꾸로 따라가 보자. 우리는 expected loss를 최소화하고 싶은데 이는 결국 posterior distribution을 얻는 문제로 귀결된다고 하였다. Posterior distribution을 얻는 것은 바로 위에서 설명하였다시피 likelihood와 prior distribution이 있으면 Bayes' theorem을 사용하여 계산할 수 있다. 그러므로 우리에게 필요한 것은 likelihood 계산을 위한 모델과 prior distribution이다. 이 두 확률 분포를 결정할 수 있으면 위의 방법을 순차적으로 적용하여 우리가 원하는 대로 expected loss를 최소화할 수 있다.

Bayesian Approach for Dark World

이제 실제로 대회에서 사용된 방법을 차근차근 살펴보도록 하자. 문제 자체를 생각해보면 우리가 알고 싶은 것은 각 헤일로의 위치이다. 그리고 우리가 들고 있는 데이터는 은하의 위치와 그 ellipticity 값이다. 이 두 가지를 가지고 베이지안 접근을 취해보자.

Prior Distribution

Prior distribution은 우리가 데이터를 보기 전에 각 모델에 대해 갖는 믿음의 확률 분포이다. 이 문제의 경우에는 우리가 데이터(은하의 정보)를 보기 전에 헤일로의 위치가 어떤 식으로 분포하고 있을 것인지에 대한 분포가 될 것이다. 문제의 가정에 포함되어 있었는지는 기억이 나지 않지만, 이는 자연스럽게 uniform distribution이 된다. 이는 데이터를 살펴보고 편향이 있는지 검사하여 확인할 수도 있을 것이다.

Model and Likelihood

매우 좋은 모델을 만드는 것은 사실 어려운 문제이다. 그러나 본 문제는 이미 벤치마크 코드에 어느 정도 동작하는 모델이 있었다. 주어진 모델은 완벽하지는 않지만 이를 조금만 확장하면 그럭저럭 괜찮은 모델을 만들 수 있다.

우선 가장 처음 해야 하는 것은 ellipticity에 대한 가정이다. 만약 헤일로가 없다면 각 은하의 ellipticity는 어떤 분포를 띌 것인가? 이 질문에 답할 수 있어야 모델을 만들 수 있다. 우리는 결국 각 헤일로가 은하에 미치는 영향을 ellipticity를 통해서 계산할 것이기 때문이다.

다행히도 각 은하의 ellipticity는 문제의 가정에서 특정한 편향이 없다고 주어졌다. 즉, 평범하게 평균이 0인 정규 분포를 가정하면 된다. 이 정규 분포를 설명하는 데 필요한 표준편차는 우리에게 주어진 데이터를 살펴보고 얻을 수 있다.

이제 모델을 만들어보자. 벤치마크 코드로 주어진 모델은 하나의 헤일로가 어떤 은하에 가하는 힘은 거리에 반비례하는 접선 방향의 ellipticity 계산을 통해 알 수 있다 하였다. 이는 더 정교한 모델로 바꿀 여지가 많이 있다.

우선 각 헤일로에 질량을 부여하도록 하자. 질량이 큰 헤일로가 더 큰 영향을 주는 것은 자연스러워 보인다. 은하의 질량 분포는 데이터를 살펴보아서 추측할 수 있을 것이다. 앞선 글에서도 언급하였지만, 데이터를 살펴보면 하나의 큰 헤일로와 작은 헤일로가 있으므로 이를 고려하여 질량의 분포를 예측하면 될 것이다.

그리고 데이터를 살펴보면 힘이 거리에 반비례하지만은 않는 것을 볼 수 있다. 헤일로가 은하에 가하는 힘은 단순히 거리에 반비례하기보다는 어떤 한계점이 있어서 일정 거리 이상으로 멀어지기 전에는 고정되어 있음을 알 수 있다.

아직 더 정교화할 여지가 남아 있지만 [3] 이 정도만 하더라도 꽤 훌륭한 모델이 된다. 이를 수식으로 표현하면 다음과 같다.

즉, 모델 (헤일로의 위치) x가 주어졌을 때, 그 모델에 의해 지금의 데이터 (은하의 ellipticity) e가 관측될 likelihood는 우리가 가정한 모델이 가하는 힘을 평균으로 갖는 정규 분포를 따른다는 것이다. 이는 바꿔 말하면 우리가 가정한 모델이 가하는 힘을 제거하고 나면 은하의 ellipticity는 평균이 0인 정규분포를 따를 것이라는 말이 된다.

여기에 더해서 2위를 차지한 사람은 헤일로의 중심에 가까워지면 노이즈가 심해져서 표준편차가 바뀔 것이라는 가정을 더하였다. 어찌 되었든 양쪽 다 모델의 모양은 거의 유사하다.

이렇게 만들어진 likelihood는 어떤 임의의 헤일로 위치와 그에 상응하는 은하의 정보가 있을 때 그런 상황이 얼마나 그럴싸한지를 표현하게 된다.

Posterior Distribution

Bayes' theorem 자체는 간단해 보이지만 실제로 posterior distribution을 계산하는 것은 어려운 문제이다. 왜냐하면 분모의 계산이 무척 어렵기 때문이다. 보통 이런 꼴의 식은 어떤 다른 패러미터에 대해 적분/덧셈을 하면 풀어낼 수 있는데, 적분 혹은 덧셈은 미천한 인간이 풀어내기 어려운 경우가 대부분이다.

비록 posterior distribution을 해석적으로 풀어낼 수는 없지만 다른 방법을 써서 이를 근사하는 것이 가능하다. 그중 한 가지 방법이 샘플링이다. 우리가 알고 싶은 분포에서 샘플을 뽑아낼 수 있으면, 그 샘플을 사용하여 원래 알고 싶었던 분포를 근사하는 것이 가능하다. 하지만 사실 이 또한 어려운 문제이다. 그러나 목표로 하는 분포의 값을 정규화하는 상수를 제외한 나머지 부분을 계산할 수 있으면 (target distribution is known up to a normalizing constant) 샘플링을 할 수 있는 Monte Carlo Markov Chain(MCMC)이라는 기법이 있다. 우리는 likelihood와 prior distribution의 값을 계산할 수 있으므로 결국 MCMC를 사용하여 원하는 대로 posterior distribution으로부터 샘플링하는 것이 가능하다.

MCMC에 대한 자세한 이야기는 나중에 다른 글에서 더 소개할 기회가 있을 것으로 여겨진다. 더 자세한 설명이 궁금하다면 Mathematicalmonk의 MCMC 설명을 참고하길 바란다.

1위는 아주 기본적인 Metropolis-Hastings 기법을 사용하였고, 2위는 그보다 더 세련된 Slice sampler를 사용하였는데 둘 다 원하는 분포에서 샘플링을 한다는 본질에는 차이가 없다. MCMC 자체가 왜 동작하는지 이해하는 것은 꽤 많은 설명이 필요하지만 그 구현 자체는 무척 간단하다.[4] 간단히 Metropolis-Hastings 기법을 이번 문제에 적용하면 다음과 같다.

Choose random halo position x[0]
for i in range(1, n+1):
    for j in range(number of halos):
       Sample x by randomly moving jth halo of x[i]
       Calculate L(x), the likelihood of x
       Sample u from uniform(0, 1)
       if u < log L(x) - log L(x[i]):
           x[i+1] = x
       else:
            x[i+1] = x[i]
Output x[1], ..., x[n]

알고리즘 자체는 아주 단순한 것을 알 수 있다. 놀랍게도 이렇게 출력된 x들이 우리가 원하던 posterior distribution으로부터 샘플한 값들이 된다.

Minimizing Expected Loss

Loss function은 문제로부터 주어져 있고 posterior distribution에서 뽑은 샘플도 있으므로 이제 expected loss를 구할 수 있다. 임의의 헤일로 배치 x가 주어지면 이 x의 expected loss는 각 posterior distribution에서 뽑은 샘플 하나하나를 매번 정답이라고 가정하고 구한 loss의 평균이 된다. 우리의 목표는 이를 최소화하는 x를 찾는 것이다. 이는 간단하게는 랜덤하게 많은 수의 x를 만들어보고 그 중 가장 좋은 것을 선택하는 방식을 취할 수 있을 것이다.

1위를 차지한 사람은 expected loss를 계산하면서 gradient를 계산할 수 있도록 짜서 local optimization이 가능하도록 하였다. 그리고 지역 최적점에서 빠져나올 수 있도록 random multi-start를 수행하게 하였다.

Discussion

그동안 긴 시간 공부를 하였고 소프트웨어 엔지니어로서 일도 꽤 하였는데, 그런 경험을 통해 배운 것이 하나 있다면 그건 바로 내 생각에는 구멍이 많다는 것이다. 내가 앞뒤로 모든 것을 꿰고 있는 주제가 아니라면 당연해 보이는 것들에도 늘 구멍이 있었다. 내가 프로그래머가 되어서 좋다고 생각하는 점 중 하나는 그런 구멍의 존재를 깨달을 수 있었던 부분이다. 어떤 개념/생각을 구현하는 것은 나로 하여금 생각을 아주 구체화하도록 강제한다. 논문을 읽는 동안은 전부 이해한 것 같지만 막상 구현하고자 하면 벽에 부딪히는 부분이 한둘이 아니다. 이번 대회를 통해서 실제로 베이지안 접근 방법을 적용하는 것을 보았고, 그걸 구현한 구현체도 살펴보니 많은 부분이 체화되는 것을 느낄 수 있었다. 그런 측면에서 아주 얻은 것이 많다고 할 수 있다.

[1]: 단순하게 말해서 그렇다는 것이다.

[2]: 사실 우변의 분모도 계산해야 하고 그 자체는 어려운 문제이다. 하지만 이는 데이터 D에 의해서만 결정되는 값이므로 불변이다. 그러므로 이 문제를 우회할 수 있는 방법이 있다.

[3]: 실제로는 암흑 물질의 영향을 받아서 은하의 관측 위치가 바뀌는 등 훨씬 더 복잡한 현상들이 일어난다고 한다.

[4]: 그러므로 무척 강력한 도구이다. 최초의 MCMC 기법인 Metropolis 알고리즘은 20세기 10대 알고리즘으로 선정되기도 하였다.

Dark World Part I

2013-02-18T00:00:00+00:00

Introduction

2012년 겨울에 Kaggle에 Observing Dark Worlds라는 대회가 열렸다. 대회의 목표는 하늘 사진을 찍고 어떤 위치에 암흑 물질이 있는지 찾아내는 것이었다.

암흑 물질은 빛과 상호작용하지 않으면서 질량을 가지는 물질이다. 자체적으로 빛을 내뿜거나 흡수하지는 않지만 질량을 갖기 때문에 그 중력에 의한 영향으로 주변의 빛에 영향을 줄 수가 있다.

위의 이미지에서는 암흑 물질의 영향에 의해 은하가 내뿜는 빛이 호(arc)를 그리는 것을 볼 수 있다. 이런 효과에 의해 암흑 물질을 직접 관측할 수는 없지만 그 위치를 짐작하는 것이 가능하다.

Credit: Observing Dark Worlds Kaggle Competition

만약 빛을 내는 은하들이 만약 모두 원형이라면 암흑 물질에 의해 타원형으로 관측되는 모습이 바뀔 것이므로 이를 통해 쉽게 암흑 물질의 위치를 추측할 수 있다. 하지만 현실은 그렇게 만만하지 않아서 애초에 은하들이 타원형을 띄고 있다. 그렇기 때문에 은하들이 애초에 그런 모양인지 암흑 물질의 영향으로 뒤틀린 것인지 알아내는 것은 쉬운 문제가 아니다.

Details

문제를 풀기 위해 주어진 데이터는 암흑 물질의 위치가 주어진 training set 300개와 과 암흑 물질의 위치가 주어지지 않은 test set 120개였다. 각 데이터는 시뮬레이션으로 생성된 하늘 데이터로서 각 하늘에는 1~3개의 암흑 물질과 300~740개의 은하가 존재하도록 만들어졌다. 각 은하는 x, y 좌표와 타원의 정도인 ellipticity를 나타내는 값 e1과 e2가 주어졌다.

데이터와 함께 두 개의 벤치마크 코드가 주어졌다. 각각 시그널 기반의 방법과 모델 기반의 방법인데 접근 방법이 비슷해 보이지만 실제로는 꽤 다른 접근 방법이다. 양쪽 다 하늘을 적당한 크기의 격자로 나누고 암흑 물질이 한 격자의 중심에 위치해 있다고 가정한다. 시그널 기반의 방식은 이제 위의 가정하에 해당 암흑 물질이 모든 은하에 미치고 있는 시그널이 얼마나 되는지 계산하여 그 합이 가장 큰 격자를 선택하는 방법이다. 모델 기반의 방식은 암흑 물질이 각 은하에 가하는 힘의 크기가 1/r로 줄어들 것이라는 모델을 가정하고 해당 모델이 얼마나 잘 들어맞는지를 계산하여 가장 그럴싸한 격자를 선택하는 식으로 구현되어 있었다.

데이터 및 벤치마크와 관련된 자세한 내용은 대회 공식 페이지인 Observing Dark Worlds 및 Kaggle tutorial 블로그에 가면 얻을 수 있다.

Approach

내가 접근한 방식을 설명하기 전에 몇 가지 이야기를 꺼내보자. 일단 나는 고득점을 하지는 못했다. 그리고 내가 작업했던 많은 부분을 실제로 제출하지도 못한 채로 대회를 마감해야 했다. 그렇기에 내가 서술하는 기법들이 얼마나 좋은지는 실제로 판단해보지는 못하였다. 이런 첨언을 미리 해두고 내가 어떤 식으로 문제에 접근하였는지 설명해보자.

Visualization

어떠한 문제든 다루는 데이터가 어느 정도 복잡하다면 통계를 내고 시각화를 통해 직관을 키우는 것이 중요하다. 그래서 시각화를 위한 노력을 어느 정도 하였다.

위의 그림은 시그널 기반의 벤치마크 코드에 약간 수정을 가한 코드로 얻어낸 답을 시각화한 것이다. 히트맵을 통해 각 위치가 얼마나 그럴싸한지 나타내도록 하였다.

비슷한 방식으로 기존의 모델 기반의 벤치마크 코드에 약간의 수정을 가미한 코드로 얻어낸 결과이다.

시각화를 통해서 많은 것을 쉽게 얻을 수가 있다. 시각화는 내가 만들어낸 기법이 얼마나 말이 되는 결과를 내고 있는지를 직관적으로 판단할 수 있는 좋은 기법이며 예상치 못했던 사실을 발견할 수 있는 매체이기도 하다. 위의 그림을 보면 모든 데이터의 가장 확률이 높은 곳 근처에 1이라는 숫자가 쓰여있는 것을 알 수 있다. 이는 실제 암흑 물질의 위치를 찍은 것인데, 암흑 물질 하나의 위치만 판별하도록 만들어진 코드가 여러 암흑 물질이 있는 경우에도 하나의 암흑 물질의 위치를 아주 잘 찾아낸다는 것을 알 수 있었다. 달리 말하자면 암흑 물질은 질량의 차이가 있고 모든 데이터에는 다른 암흑 물질보다 압도적으로 질량이 큰 암흑 물질 하나가 언제나 존재하는 것을 이를 통해 쉽게 알 수 있었다.

Other Approaches

다른 접근 방법으로는 물리학적인 모델을 찾아보려고 하였으나 관련 논문들의 내용을 도무지 이해할 수가 없어서 포기하게 되었다. 또한 기본 벤치마크 코드를 조금씩 수정해보고 "느낌"을 얻어보려고 노력하였다.

Data Mining

누군가 포럼에 문제를 순수하게 데이터 마이닝의 관점에서 보고 모델 등과 무관한 접근 방법을 취하는 이야기를 쓰고 관련된 피쳐를 조금 공개하였다. 이를 살펴보고 적용해보았는데 그럭저럭 괜찮은 결과를 얻을 수 있었지만 더 확장할 수는 없었다. 참고로 관련 글을 포럼에 적었던 사람은 최종적으로 대회 3위를 차지하게 되었다.

Evolutionary Algorithms

모델을 잘 만들어서 이를 활용하는 방법을 생각하게 되었는데 우선은 두 개의 헤일로가 존재하는 경우의 문제만 시도하였다. 첫 번째 암흑 물질의 위치는 쉽게 알 수 있으므로 이를 가지고 두 번째 헤일로의 위치를 찾는 방법을 고민해보았다.

첫 번째 암흑 물질의 위치를 알고 있을 때, 이 헤일로가 모든 은하에 가하는 접선 방향의 힘을 각각 은하로부터 제외한 값이 최대한 정규 분포에 가깝게 하는 모델을 찾고자 하였다. 모델 자체는 거리에 반비례, 거리의 제곱에 반비례, 거리의 0.5승에 반비례, 거리의 0.75승에 반비례하는 항들의 합으로 주어지게 하였는데, 각 항은 질량 요소를 갖는 것으로 하였다. 나중에 돌아보니 이는 큰 의미 없이 문제만 어렵게 모델링 한 꼴이 되었지만 당시에는 더 나은 접근 방법을 딱히 떠올리지 못하였다.

m, s = norm.fit(e1 - e1_pred); fitness = m**2 + s**2

위와 같은 적합도 식을 만들고 이를 Pearson/Spearman correlation coefficient 등과 함께 사용하여 조금씩 변형을 가하기는 하였으나 기본적인 형태는 그대로 유지하였다.

이렇게 찾아야 하는 모델 패러미터와 적합도 식을 만들고 particle swarm optimization으로 최적 모델 패러미터를 찾도록 하였다.

위의 그림은 두 번째 헤일로의 위치를 예측하도록 한 모델의 결과를 나타낸 것이다. 실제 두 번째 헤일로는 초록색 별로 표시되었고 모델이 예측한 위치는 하얀색 별로 표시하였다. 물론 실제로는 이렇게까지 결과가 훌륭하지 않은 경우들도 여럿 있었다.

스스로 적용해본 기법은 여기까지가 끝이다. 실제로 대회에 제출한 결과는 벤치마크 코드를 조금 수정해본 것이 다였고, POS 등을 적용한 방법 등의 결과를 제출해보지 못하였다.

Discussion

대회 자체는 나에게 꽤 큰 자극이 되었다. 일차적으로 다른 사람들과 겨룬다는 것 자체가 큰 자극이 된다. 그 밖에도 평소에 연구하는 동안은 잘 활용하지 않는 도구들을 꺼내어 사용하게 되었는데 그 점도 매우 좋았다.

한가지 느낀 점은 망치를 들고 있으면 모든 것이 못으로 보이기 십상인데 이를 잘 극복해야 할 것이라는 점이다. 내가 아무래도 늘 진화 연산 기법들을 접하다 보니 모든 문제가 단순히 최적화 문제로만 보이고 그렇게 접근하게 되기 쉬웠다. 이는 내가 앞으로 극복하고 포용해야 하는 문제가 될 것이다.

그리고 마지막으로 대회 1,2위 및 3위가 모두 통계적인 접근 방법을 취했다는 점이 나로 하여금 계속해서 기계학습/데이터 마이닝을 공부하게 하는 자극이 되었다. 1,2위는 조금은 뻔한 베이지안 시각에서 문제에 접근하였고, 3위는 놀랍게도 리니어 모델만 사용한 것으로 보인다. 1,2위는 코드 및 관련 정보를 공개하였으나 3위는 안타깝게도 공개한 것을 찾을 수 없었다. 어찌 되었든 이들의 접근 방법을 보면서 느낀 바도 있고, 여러모로 얻은 것이 많은 대회였다. 다음 글에서는 1,2위가 사용한 베이지안 시각의 접근 방법을 소개하고자 한다.