갑자기 블로그를 처음 시작했던 2013년 1월달이 생각납니다. 그 때는 처음 시작하는 마음이라 거의 하루에 한개씩 글을 올렸던 것 같습니다 ^^. 새해가 되어서 그런걸까요.. 그때만큼은 아니지만 요즘 비교적 자주 글을 올리고 있습니다. 하지만 요즘에는 댓글들로 인해서 쓰게 되는 글도 많습니다. 댓글을 주고 받으면서 떠오른 생각들, 댓글에는 간략히 답하였지만 글로 정리해서 공유해도 좋겠다 싶은 내용이 생기면 글을 쓰게 됩니다. 이 글도 그런 글의 하나입니다.

Bayesian(베이지언) 확률...

외국의 왠만한 논문을 읽다보면 거의 빠지지 않고 나오는 확률모델. 어떤 문제를 확률적으로 결정할 때 빠지지 않고 나오는 모델인데 사실 논문에 있는 그대로 따라 이해하기도 벅찬 경우가 많습니다. 하물며 자신이 직접 문제에 맞게 그러한 수학적 모델을 만들고 식을 세워나간다고 생각해 보면 참 대단하다는 생각과 함께 한숨이 나오기도 합니다.

예전에 쓴 "베이즈 정리, ML과 MAP, 그리고 영상처리" 글에서는 classification 문제에 확률이 활용되는 대표적인 두 가지 접근방법(ML & MAP)에 대해 설명했었고, "Ferns를 이용한 영상 Object Detection" 글에서는 글 말미에 pure Bayesian, semi-naive Bayesian, naive Bayesian에 대해 간략히 언급한 적이 있습니다.

이번 글에서는 pure, semi-naive, naive 이러한 구분에 대해서 그리고 Bayesian 확률에 대해서 좀더 직관적으로 이해해 보고자 합니다.

1. ML & MAP

눈 앞에 한명의 사람이 서 있습니다. 그런데 이 사람은 커튼에 가려져 있으며 우리가 볼 수 있는 것은 커튼에 비친 그 사람의 형상뿐입니다.

이 사람이 누구일까요? 철수일까요 아닐까요? 아니면 철수일까요 영희일까요 아니면 설까치일까요? 아니면 남자일까요 여자일까요? 이러한 모든 문제들은 결국 확률적 classification 문제로 볼 수 있으며 Bayesian 확률이 사용되는 전형적인 예가 됩니다.

조건부 확률로 생각해 보면 P(눈앞의사람|철수)와 P(철수|눈앞의사람)의 2가지 확률을 생각할 수 있습니다.

P(눈앞의사람|철수)는 철수가 눈앞의사람의 형상을 나타낼 확률이고 P(철수|눈앞의사람)은 눈앞의사람의 형상을 나타내는 사람이 철수일 확률입니다. 얼핏 비슷한 것 같지만 사실은 서로 다른 확률을 나타내는 것임에 주의해야 합니다. 여기서 P(눈앞의사람|철수)는 보통 likelihood라 부르고 P(철수|눈앞의사람)은 posterior 확률이라고 부릅니다.

눈앞의 사람이 누구인지를 확률적으로 알아내는 방법은 크게 ML(Maximum Likelihood) 방법과 MAP(Maximum A Posteriori) 방법이 있는데, ML은 가능한 사람들에 대해서 P(눈앞의사람|철수), P(눈앞의사람|영희), ... 등을 각각 계산해서 그중 likelihood가 가장 높은 사람을 선택하는 방식이고 MAP는 posterior 확률 P(철수|눈앞의사람), P(영희|눈앞의사람), ... 을 계산해서 가장 확률이 높은 사람을 선택하는 방식입니다.

그런데, likelihood P(눈앞의사람|철수)는 철수가 가질 수 있는 다양한 형상들 중에서 눈앞의 형상이 나올 확률을 구하는 문제이므로 비교적 직관적인 이해가 가능합니다. 그러나 posterior 확률 P(철수|눈앞의사람)은 대체 어떻게 계산해야 하는 걸까요?

여기서 그 유명한 Bayes 정리가 나옵니다.

 --- (1)

식 (1)에서 P(눈앞의사람)은 그 값이 무엇이든지간에 고정된 상수값이기에 MAP에서는 결국 P(눈앞의사람|철수)P(철수), P(눈앞의사람|영희)P(영희), ... 들 중에서 가장 높은 값을 나타내는 사람을 선택하는 것이 됩니다. 즉, 결과적으로 ML와 MAP의 차이는 뒤에 P(철수), P(영희), ... 과 같은 확률을 곱하느냐 곱하지 않느냐의 차이가 되는데, P(철수), P(영희), ... 와 같이 클래스 고유의 확률값을 prior 확률이라고 부릅니다 (만일 눈앞의 사람형상이 남자인지 여자인지를 구분하는 문제라고 생각해 보면 prior 확률이 어떤 의미를 갖는지 알 수 있음).

☞ P(눈앞의사람)도 사실 계산이 가능한 상수값인데, 만일 가능한 사람이 철수, 영희, 까치라고 한다면 P(눈앞의사람) = P(눈앞의사람|철수)P(철수) + P(눈앞의사람|영희)P(영희) + P(눈앞의사람|까치)P(까치) 로 계산됩니다.

ML와 MAP 중 어느것이 보다 정확한 방법이냐고 물으면 대답은 MAP이 보다 정확한 방법이다 입니다. 커튼에 비친 사람의 형상을 보고 그 사람이 누구인지 맞춘다고 했을 때, P(철수|눈앞의사람), P(영희|눈앞의사람), ... 가 가장 높은 사람을 선택하는 것이 원래의 문제를 있는 그대로 푸는 것입니다. 그리고 ML로 문제를 푸는 것은 모든 prior 확률이 같다는 가정(P(철수)=P(영희)=...)하에 일종의 근사적인 해를 구하는 것입니다. 하지만 MAP로 문제를 풀더라도 식(1)에 의해서 likelihood 식으로 변환하여 계산하기 때문에 어느 경우나 결국은 likelihood의 계산이 필요하게 됩니다.

ML과 MAP classification 문제를 식으로 정리해 보면 다음과 같습니다 (c: 클래스, z: 관측값).

2. pure, naive, semi-naive Bayesian

그러면 두번째 주제로 넘어가서 이 likelihood를 어떻게 계산하는지, pure, naive, semi-naive Bayesian이 어떻게 다른지에 대해 살펴보겠습니다.

likelihood P(눈앞의사람|철수)를 직접 계산하기 위해서는 철수에 대한 사진 수만장을 찍고 여기서 나온 형상들의 확률 분포를 구해야 합니다. 그러나 이러한 접근은 상당히 비효율적이며 형상의 같고 다름에 대한 기준도 모호할 뿐더러 이렇게 구한 확률분포가 철수라는 사람이 가지고 있는 형상의 특징을 효과적으로 표현할 수 있을지도 의문이 됩니다.

따라서, 대부분의 실제 문제에 있어서는 사람의 형상에 대한 주요 특징(키, 머리크기, 허리둘레 등)만을 선별하여 이 특징들에 대한 확률분포를 이용하는 것이 일반적입니다. 즉, 원래의 P(철수|눈앞의사람), P(눈앞의사람|철수) 대신에 P(철수|키,머리크기,허리둘레,...), P(키,머리크기,허리둘레,...|철수)를 이용하여 classification 문제를 풀게 됩니다.

이 때 이 특징(feature)들에 대한 likelihood P(키,머리크기,허리둘레,...|철수)를 어떤 식으로 계산하느냐에 따라서 pure Bayesian, naive Bayesian, semi-naive Bayesian이 구분됩니다.

먼저 가장 단순한 방법인 naive Bayesian 방식은 사람의 키, 머리크기, 허리둘레가 서로 상관관계가 없는 독립변수라는 가정하에 키의 확률분포, 머리크기의 확률분포, 허리둘레의 확률분포를 각각 구한 후 각각의 확률을 서로 곱하여 최종 결합확률을 계산합니다.

 --- (2)

반면에 pure Bayesian 확률은 사람이 가질 수 있는 모든 (키,머리크기,허리둘레) 조합에 대하여 확률분포를 계산한 값을 사용합니다. 즉, naive Bayesian은 키만을 고려한 확률분포, 머리크기만을 고려한 확률분포, 허리둘레만을 고려한 확률분포 이렇게 3개의 확률분포로부터 나온 값들을 곱하여 결합확률을 계산하고 pure Bayesian은 키, 머리크기, 허리둘레를 동시에 고려한 3차원의 확률분포에서 계산된 값을 이용하는 것입니다.

이제 naive Bayesian 확률과 pure Bayesian 확률이 어떻게 달라지는지 간단한 예를 통해 살펴보겠습니다.

예를 들어 사람의 키는 0 또는 1의 값을 가지고, 머리크기도 0 또는 1의 값만을 가지며 철수의 키와 머리크기의 확률분포가 다음과 같다고 가정하겠습니다 (철수 형상에 대한 다수 샘플을 수집한 후 각 샘플에서 계산된 키, 머리크기의 값에 대한 히스토그램을 구하여 합이 1이 되도록 정규화한 값).

<표1> P(키,머리크기|철수)의 확률분포

그런데, 만일 동일한 샘플에 대해 키, 머리크기의 확률분포를 독립적으로 구했다면 그 결과는 다음과 같을 것입니다.

<표2> P(키|철수)의 확률분포

<표3> P(머리크기|철수)의 확률분포

이제 P(키=0, 머리크기=0 | 철수)를 pure Bayesian으로 구해보면 0.3이고 naive Bayesian으로 구해보면 0.5*0.4 = 0.2가 되어서 서로 다른 값이 나옴을 확인할 수 있습니다.

어떤 값이 올바른 값일까요?

당연히 pure Bayesian으로 계산한 0.3이 올바른 확률값입니다. naive Bayesian에서 잘못된(오차가 있는) 값이 나오는 이유는 feature간의 상관관계(키와 머리크기가 가지는 상관관계)를 무시하고 확률을 계산했기 때문입니다. 물론 정말로 상관관계가 없다면 naive Bayesian으로 계산된 확률값도 맞는 값이 될 것입니다.

그러나 실제 문제에 있어서는 pure Bayesian이 당연히 가장 정확한 확률모델임에도 불구하고 naive Bayesian이 사용되는 경우도 많습니다. 그 이유는 pure Bayesian 확률분포는 구하기가 어렵기 때문에 오차를 감수하고 간단한 naive Bayesian으로 문제를 단순화시켜서 풀기 때문입니다. 예를 들어, feature의 개수가 10개이고 각각의 feature가 가질 수 있는 값의 종류가 각각 3개씩이라면 pure Bayesian 방식으로는 3^10 = 59,049 가지 경우에 대한 확률을 계산해야 하지만 naive 방식으로는 3*10 = 30개의 확률값만 계산하면 되기 때문입니다.

마지막으로 pure Bayesian과 naive Bayesian의 중간 단계에 있는 semi-naive Bayesian에 대해 살펴보겠습니다.

semi-naive Bayesian은 feature들을 먼저 소그룹으로 그룹핑(grouping)을 한 후에 각 그룹 내에서는 feature들 간의 상관관계를 풀(full)로 계산하되, 그룹과 그룹 사이에서는 상관관계가 없는 것으로 확률을 계산하는 방식입니다. 만일 feature들을 실제 상관관계가 있는 것끼리 잘 그룹핑할 수만 있다면 semi-naive Bayesian 방식이 가장 효율적인 확률모델이 될 것입니다.

예를 들어, f1, f2, ..., f9 9개의 feature를 순서대로 3개씩 묶어서 그룹(F1={f1,f2,f3}, F2={f4,f5,f6}, F3={f7,f8,f9})을 만들고 각 그룹내에서는 풀로 가능한 모든 조합에 대해 확률분포를 계산했다면 semi-naive Bayesian 확률은 다음과 같이 계산됩니다.

 --- (3)

마지막으로 이상의 3가지 Bayesian 확률 모델을 정리해 보면 다음과 같습니다.

☞ 사실 저도 베이지언에 대해 정리가 된 건 최근입니다. 논문 등을 볼때마다 그런 것 같긴 한데 뭔가 마음에 와 닿지는 않았던 적이 있습니다. 아마도 수식적인 부분에 너무 얽매였던 것 같습니다. 조금만 멀리 떨어져서 생각해 보면 사실 그렇게 어려운 개념이 아닌데.. 아마도 이제는 그런 모호함이 적겠지요. 그래서 개념이 중요함을 다시 한번 느낍니다.

by 다크 프로그래머

오늘 아침 한 시사 프로에서 어렸을 때 천재라는 소리를 들었던 신한대 김웅용 교수와의 인터뷰 내용을 듣고 왠지 여운이 남아서 몇자 적어본다.

4살에 4개국어를 하고 5살에 미적분학 문제를 풀고.. 8살에 미국 NASA의 초청으로 미국에서 연구원 생활을 한.. 분명 일반인의 범주를 벗어난 것은 분명하다.

하지만 오늘 아침 그 당사자의 인터뷰 내용을 들으면서 내가 느낀 감정은 천재성에 대한 내용이 아닌 한 개인으로서의 삶에 대한 안타까움이다.

김웅용 교수는 8살 나이에 혼자 낯선 미국에 건너가 또래 친구 하나 없이 20살 이상 차이나는 동료들과 연구원 생활을 하며 느꼈던 감정들을 담담하게 얘기한다.

크기가 맞지 않는 책상, 마실 수 없었던 맥주와 와인, 다른 문화, 낯선 땅, ...

김웅용 교수는 8살 나이에 그런 낯선 곳에서 홀로 5년이나 버티다 돌연 한국으로 돌아왔고 그 뒤로 평범한 삶을 살아왔다고 한다.

아직은 보호가 필요한 어린 나이에 시간을 건너뛴 성인의 삶은 감당하기 힘들었을 것이다.

딱히 누구 탓이라고 할 수는 없겠지만 김웅용 교수의 입장에서는 돌이켜보면 많은 회한이 남는 시간이었을 것 같다.

현재의 삶은 어쩌면 그가 선택한 삶의 방식은 아닐는지...

그림 출처: http://www.spitzer.caltech.edu/

무엇을 위한 그리고 누구를 위한 천재인지 묻기 전에 한 평범한 삶으로써 누려야할 어쩌면 당연한 삶의 과정 그런 것들에 대해 다시 한번 생각해 본다.

by 다크 프로그래머

이 글은 1D 선형보간법(linear interpolation)을 2D로 확장한 bilinear interpolation과 3D로 확장한 trilinear interpolation이 어떤 식으로 이루어지는지와 이러한 interpolation 기법이 히스토그램(histogram)을 생성할 때 어떻게 적용되는지에 대한 글입니다.

그리고 보통 interpolation하면 직사각형이나 직육면체 내에서의 보간을 생각하기 쉬운데, 알려진 데이터 점들이 직사각형, 직육면체가 아닌 임의의 사각형 또는 임의의 육면체를 이룰 때 보간 방법에 대해서도 소개합니다.

1. Interpolation과 Extrapolation

Interpolation(인터폴레이션, 보간)이란 알려진 지점의 값 사이(중간)에 위치한 값을 알려진 값으로부터 추정하는 것을 말한다.

Interpolation과 대비되는 용어로 extrapolation이 있는데, extrapolation은 알려진 값들 사이의 값이 아닌 범위를 벗어난 외부의 위치에서의 값을 추정하는 것을 말한다.

예를 들어, 어떤 사람이 20살일때 키와 40살에서의 키를 보고 30살에서의 키를 추측하는 것은 interpolation이고 과거 1살때부터 현재 나이까지의 키를 보고 앞으로 10년 후의 키를 예측하는 것은 extrapolation이다. 또한 최근 한달간의 주가 동향을 보고 내일의 주가를 예측하는 것도 extrapolation이며 extrapolation은 interpolation에 비해 훨씬 안정성이 떨어지는 (위험한) 예측 방법이다.

아래 그림에서 x1, x2에서 데이터 값을 알고 있을 때 x1<=xi<=x2에서 값을 추정하는 것은 interpolation이고 범위 밖인 xj에서 값을 추정하는 것은 extrapolation:

<그림 1>

2. 1D Linear Interpolation

두 지점을 보간하는 방법은 polynomial 보간, spline 보간 등 여러 가지가 있으나 그 중 선형 보간법(linear interpolation)은 두 지점 사이의 값을 추정할 때 그 값을 두 지점과의 직선 거리에 따라 선형적으로 결정하는 방법이다.

두 지점 x1, x2에서의 데이터 값이 각각 f(x1), f(x2)일 때, x1, x2 사이의 임의의 지점 x (x1≤x≤x2)에서의 데이터 값 f(x)는 선형보간법을 사용할 경우 다음과 같이 계산된다.

--- (1)

단, d1은 x에서 x1까지의 거리, d2는 x에서 x2까지의 거리.

<그림 2>

☞ 원래는 f(x) = f(x1) + d1/(d1+d2)*(f(x2)-f(x1)) 인데, 이를 정리하면 식 (1)이 나온다.

만일 거리의 비를 합이 1이 되도록 정규화하면 즉, α = d1/(d1+d2), β = d2/(d1+d2)라 잡으면 식 (1)은 다음과 같이 좀더 단순화될 수 있다 (α + β = 1).

 --- (2)

3. Bilinear Interpolation

Bilinear interpolation은 우리 말로 적자면 쌍선형 보간법, 또는 이중선형 보간법 정도가 되며 1차원에서의 선형 보간법을 2차원으로 확장한 것이다.

Bilinear interpolation 방법을 설명하기 위해 아래 그림과 같이 직사각형의 네 꼭지점에서의 값이 주어져 있을 때, 이 사각형의 변 및 내부의 임의의 점에서의 값을 추정하는 문제를 생각해 보자.

<그림 3>

그림과 같이 점 P에서 x축 방향으로 사각형의 변까지의 거리를 w1, w2, y축 방향으로 거리를 h1, h2라 하고, 알려진 네 점에서의 데이터 값을 A, B, C, D라 할 때, P에서의 데이터 값은 bilinear interpolation에 의해 다음과 같이 계산된다 (단, α=h1/(h1+h2), β=h2/(h1+h2), p=w1/(w1+w2), q=w2/(w1+w2)).

 --- (3)

계산 원리는 쉽게 짐작할 수 있듯이 A, B를 보간하여 M을 얻고 C, D를 보간하여 N을 얻은 후에 M, N을 보간하여 P를 얻는 방식이다. 또는 그 순서를 바꾸어 U와 V를 먼저 얻은 후에 U, V를 보간해도 동일한 결과를 얻을 수 있다.

그런데, 위의 보간 방법은 원래의 데이터의 위치가 직사각형을 이룰 경우에만 적용할 수 있는 방법이다. 만일 아래 그림처럼 임의의 형태의 사각형에서 사각형 내부를 보간하고자 할 때에는 어떻게 해야 할까?

<그림 4>

이 경우에는 아래 그림처럼 원래의 사각형을 어떤 직사각형으로 워핑(warping)시킨 후 워핑된 사각형에서 보간(interpolation)을 수행하면 된다.

워핑할 사각형은 임의의 직사각형이 가능하지만 편의상 네 꼭지점의 좌표가 (0,0), (0,1), (1,1), (1,0)인 단위 정사각형으로 워핑시킨다고 하자.

<그림 5>

이 경우 보간 방법은 원래 사각형의 네점 ABCD를 A'B'C'D'으로 변환시키는 선형변환(linear transformation) T를 구한 후, 구한 T를 이용하여 P를 변환시킨 P'를 구하고 단위 정사각형에서 bilinear interpolation을 수행하면 된다. 선형변환 T는 2D homography ([영상 Geometry #3] 2D 변환 (Transformations) 글 참조)를 이용하여 구할 수 있다.

4. Trilinear Interpolation

삼선형 보간법 정도로 번역할 수 있겠으며 1차원에서의 선형보간법을 3차원으로 확장한 것이다.

Trilinear interpolation 방법은 3차원 공간에서 8개의 꼭지점으로 이루어진 육면체의 변 및 내부의 임의의 점에서의 데이터 값을 선형적으로 보간하는 방법을 일컫는 말이다.

<그림 6>

Trilinear interpolation 방법은 위 그림과 같이 bilinear interpolation과 원리는 동일하며 P에서의 보간값을 구하기 위해 먼저 M, N에서의 값을 보간하고 이로부터 R에서의 값을 보간한다. 마찬가지로 U, V에서의 값을 보간한 후 이로부터 S에서의 값을 보간한다. 마지막으로 R, S로부터 P를 보간한다.

만일 원래의 데이터 점들이 직육면체를 이루지 않을 경우에는 bilinear interpolation에서 설명한 방법과 마찬가지로 원래의 육면체를 임의의 직육면체로 매핑(워핑)한 후 워핑된 직육면체에서 보간값을 계산하는 방법을 사용한다.

5. 히스토그램의 보간(interpolation)

Hough 변환을 위해 히스토그램을 구할 때, 또는 영상 feature를 추출하기 위해 히스토그램을 구할 때 등 다양한 히스토그램(histogram) 변환 작업에는 설정한 히스토그램의 bin 크기에 따라 필연적으로 계단현상(aliasing, 히스토그램의 bin과 bin 경계에 위치한 값이 어떤 bin에 떨어지느냐에 따라 히스토그램 결과값이 크게 달라지는 현상)이 발생하게 된다.

이러한 히스토그램 계단현상을 완화하기 위해서 앞서 설명한 보간 방법들이 주로 사용되는데, 예를 들어 HOG(Histogram of Oriented Gradient)에서는 gradient의 방향 히스토그램을 구할 때 trilinear interpolation 방법이 적용된다 (http://lear.inrialpes.fr/people/dalal/NavneetDalalThesis.pdf의 Appendix D).

먼저 1D 히스토그램을 생성할 때 선형보간법을 적용하는 방법을 설명하면, 어떤 데이터 x에 대해 가장 가까운 인접한 두 히스토그램 bin을 b1, b2라 하고 x에서 b1까지의 거리를 d1, b2까지의 거리를 d2라 하면 b1의 값은 d2/(d1+d2)만큼 증가시키고 b2의 값은 d1/(d1+d2)만큼 증가시키는 방식이다.

만일 2D 히스토그램을 생성하는 경우라면 하나의 입력 데이터에 대해서 해당 데이터와 가장 가까운 인접한 4개의 bin 값을 bilinear interpolation 방식에 의해 증가시킨다. 예를 들어, 어떤 데이터에서 추출한 feature 값이 (f, g)이고 (f, g)와 가장 가까운 서로 인접한 4개의 히스토그램 bin을 (f1, g1), (f2, g1), (f1, g2), (f2, g2), f와 f1의 거리를 d1, f와 f2의 거리를 d2, g와 g1과의 거리를 k1, g2와의 거리를 k2라 하면 각각의 bin 값들은 다음과 같이 증가된다.

(f1, g1) : d2/(d1+d2) * k2/(k1+k2) 만큼 증가

(f1, g2) : d2/(d1+d2) * k1/(k1+k2) 만큼 증가

(f2, g1) : d1/(d1+d2) * k2/(k1+k2) 만큼 증가

(f2, g2) : d1/(d1+d2) * k1/(k1+k2) 만큼 증가 --- (4)

식 (4)는 하나의 데이터에 대해 bin의 값을 1 증가시키는 경우의 증가량 식이며 만일 어떤 데이터에 대해 증가시켜야 할 bin의 값이 1이 아니라 v라면 v에 식 (4)의 값을 가중치로 하여 곱한 값만큼씩 증가시키면 된다.

만일 3D 히스토그램을 생성하는 경우라면 데이터에 가장 가까우면서도 서로 인접한 8개의 bin을 찾아서 trilinear interpolation 방식으로 bin 값을 증가시키면 된다. 참고로 HOG의 경우를 예로 들면, HOG에서는 영상 영역을 8 x 8 픽셀 크기의 셀(cell)들로 분할한 후 각 셀마다 gradient 방향 히스토그램을 구하는데 HOG 히스토그램은 셀의 x좌표, y좌표, 그리고 gradient 방향 이렇게 3개의 축에 대해 히스토그램을 구하는 3D 히스토그램으로 볼 수 있다. 이후 HOG에서는 영상의 각 픽셀에 대해 가장 가까운 인접한 4개의 셀을 선택하고 또한 해당 픽셀에서의 gradient 방향값과 가장 가까운 2개의 bin을 선택함으로써 총 8개의 bin을 선택(각 셀의 히스토그램마다 2개씩의 bin을 선택)하여 bin 값을 update시킨다.

☞ 기본적인 내용이긴 하지만 막상 trilinear interpolation이 뭐지? 하면 햇갈릴 수 있고 또한 임의의 사각형이나 육면체, 히스토그램에 보간법을 적용하는 것은 국내에는 거의 정보가 없어서 정리를 해 보았습니다.

by 다크 프로그래머