작년에 Gmail에 도입된 유용한 서비스가 Priority Inbox입니다. 작년에 구글이 Buzz 및 Wave등으로 한창 삽질(?)을 하고난 이후라서 처음에는 그 유용성에 대해 반신반의했었지만, 처음에 몇개의 Email을 Important / Not Important로 레이블링 해주고 난 후에는 거의 100% 올바른 분류를 하는 것을 확인하고 놀랐습니다.

오늘 연구실 동료의 트윗에서 Gmail Priority Inbox의 알고리즘을 소개한 Technical Paper를 발견하고 읽어 보았습니다. 그동안 저처럼 궁금하셨을 분들께 간단히 소개합니다. 평소 기계학습이 '주어진 알고리즘을 갖다 쓰는 것'이라고 여겼던 분들이라면, 단순한 Regression Model을 주어진 Learning Problem에 적용하는 과정에도 굉장히 많은 고려가 필요함을 알 수 있습니다. 

The Learning Problem

잘 아시겠지만, Regression은 주어진 Feature를 가지고 실수값을 갖는 Label을 예측하는 기법입니다. 우선 메일의 중요도를 나타내는 Label을 살펴보면, 메일 도착 후 일정시간 이내에 사용자가 특정한 액션(open, reply 등)을 취하는 경우를 중요한 메일로, 사용자가 보고도 아무 조치도 취하지 않은 경우 중요하지 않은 것으로 간주하는 것을 알 수 있습니다. 즉, 사용자의 Explicit Label과 함께 Implicit Action을 모두 학습에 활요하는 것입니다. 

또한 아래와 같은 다양한 Feature가 학습에 활용됩니다. 이메일의 기본 Feature에 Label까지 활용하는군요. 
Social features are based on the degree of interaction between sender and recipient, e.g. the percentage of a sender’s mail that is read by the recipient. 
Content features attempt to identify headers and recent terms that are highly correlated with the recipient acting (or not) on the mail, e.g. the presence of a recent term in the subject. 
Thread features note the user’s interaction with the thread so far, e.g. if a user began a thread. 
Label features examine the labels that the user applies to mail using filters

다음은 실제 학습 알고리즘입니다. 기본적으로는 Logistic Regression을 사용하지만, 모든 유저의 데이터에서 학습한 내용과 개별 유저로부터의 학습 내용을 모두 학습에 사용하기 위하여 Transfer Learning을 사용합니다. Transfer Learning은 모델을 학습한 도메인과 적용할 도메인이 다를 경우 사용하는 기법입니다. 다음 다이어그램은 이러한 학습 과정을 시각화합니다.


알고리즘에서 또 하나 이채로운 점은, 각 메일에 대한 Important / Not Important의 결정을 내리는 기준(threshold)을 사용자의 Explicit Label을 사용해 개인화한다는 점입니다. 각 사용자 별로 중요한 메일의 비율이 다르기 때문에, 이는 자동화하기 힘든 부분입니다.

Production

개발된 알고리즘을 수백만의 사용자가 매일 사용하는 시스템에 적용하는 것은 또다른 문제입니다. 논문에서는 구글 컴퓨팅 클러스터의 기본 데이터 구조인 BigTable이 어떻게 활용되는지 자세히 밝히고 있습니다. 사용자별 학습 알고리즘 수행의 부하를 각 Core에 나누는 과정도 흥미롭습니다.

Result

논문에서는 위에서 설명한 Global Model과 Per-user Model의 조합, 그리고 사용자별 중요도 기준의 개인화를 통해서 에러율을 상당부분 낮출 수 있었다는 결론을 내고 있습니다. 또한 Industry Paper답게 Priority Inbox의 도입이 Gmail사용자들의 메일 사용을 어떻게 효율적으로 만들었는지를 다음과 같이 밝히고 있습니다. 

The ultimate goal is to help Gmail users. We analyzed the time Google employees spent on email with and without Priority Inbox. Averaging over Googlers that receive similar volumes of mail, Priority Inbox users (approx. 2000 users) spent 6% less time reading mail overall, and 13% less time reading unimportant mail. They are also more confident to bulk archive or delete email.

마치며

겨우 4장짜리 논문이지만, 기계학습 알고리즘을 실제 문제에 적용하는 과정에서 발생하는 수많은 문제를 간결하면서도 명쾌하게 기록하고 있습니다. 한때 기계학습이 알고리즘의 인풋과 아웃풋만 알면 블랙박스처럼 활요할 수 있을 것이라고 생각한 때도 있었지만, 위 논문만 읽어 보아도 학습 기법의 실전 활용에는 상당한 지식이 필요함을 알 수 있습니다. 기타 재미있는 디테일이 많으니 관심있으신 분들꼐 일독을 권합니다.

교과서를 가지고 씨름하다 혹시나 해서 도서관에 가 보았는데, 역시 쓸만한 책이 많더군요. 교과서보다 훨씬 생생한 사례를 가지고 알기쉽게 설명한 책을 찾았습니다. 지난 시간에 소개한 '통계는 성공의 나침반'이라는 책을 추천합니다. 다음 구절이 인상적이어서 옮겨 보았습니다.
"인간의 두뇌는 확률문제를 푸는 데 별로 적합하지 않다." - 책 '확률의 함정'에서
위 말처럼 인간의 사고 및 판단의 대부분을 차지하는 휴리스틱(Heuristic)은 오류투성이여서, 정신이 온전한 상태에서도 수많은 실수를 범하게 됩니다. 오늘은 확률과 관련하여 자주 범하는 오류를 살펴보도록 합시다.


부분의 합은 전체가 아니다? - 심슨의 역설


직관과 어긋나는 사례로 자주 언급되는 것이 '심슨의 역설(Simpson's Paradox)'입니다. 이는 발견자인 에드워드 심슨 박사의 이름을 딴 것으로, 통계 조사에서 부분적인 결과와 이를 합친 전체의 결과가 어긋나는 결과나 종종 관찰된다는 점을 지적합니다. 다음 기사는 어떤 대학의 남학생 합격률이 더 높았는데, 단과대별로는 여학생의 합격률이 높다는 모순적인 현상을 다룬 것입니다. 원인은 남학생은 대부분 합격률이 높은 단과대에 지원했으며, 여학생은 그 반대이기 때문입니다. 전체 합격자 비율은 단대별 합격률의 단순 평균이 아니라 전체 합격자 수를 전체 지원자 수로 나눈 것이므로, 합격자 절대수가 많으면 합격률이 높아지는 겁니다.

어떤 블로그에는 이를 빌어 한의학과 서양 의학을 비교하는 사례가 있군요. 과학자가 아니더라도 직관을 맹신하는 것은 위험합니다.

암검사 결과를 믿을 수 없다? - 베이즈 룰

많은 기계학습 이론의 기초가 되는 베이즈 규칙(Bayes' Rule)도 직관의 함정을 피하도록 도와줍니다. 다음 웹페이지는 어떤 암 발병확률이 1%이고, 발병자 80%가 양성 반응을, 비 발병자 9.6%가 양성 반응을 보이는 암검사에서 양성판정을 받은 환자가 암을 가졌을 확률이 몇%인지 묻고 있습니다. 실제 의사들에게 질문을 했을때도 대부분이 80%로 대답했다고 합니다만, 위 페이지의 계산결과를 보면 실제 확률은 7.8%라고 합니다. 이처럼 베이즈 규칙은 결과적인 사건(암검사)이 주어졌을 때 원인이 되는 사건의 확률을 추론할 수 있는 수단을 제공한다는 데 의의가 있습니다.

베이즈 규칙에서는 아래 식처럼 사건의 원래 발생확률(A - prior)과 그 사건이 발생을 가정할때 현상이 나타날 조건부 확률(B|A likelihood - 해당 사건이 현상을 설명하는 정도)를 곱해서, 현상이 주어졌을때 예측하고자 하는 사건의 발생 확률(A|B posterior)을 계산합니다. 앞의 사례로 돌아가면, 암(사건)의 발병확률이 1%로 워낙 낮기 때문에, 양성판정(현상)으로 높아진 확률도 7.8%에 머무는 것입니다.

        

기계학습의 주제인 분류(classification)작업에서는 현상에 대한 학습자의 가설(hypothesis)이 사용되기에,  주어진 현상(B)을 가장 잘 설명하는 가설(A)을 찾는데 베이즈 규칙을 사용합니다. 베이즈 룰을 사용한 스팸 필터를 생각해보면 메일에 포함된 단어(B)를 종합하여 스펨인지 아닌지(A)를 판단해 내는 것입니다.

마치며

베이즈 규칙은 기계학습 알고리즘 대부분의 이론적 기초를 제공하는 중요한 이론이지만 그 함의를 완전히 이해하는 것은 쉬운 일이 아닙니다. 제 이해가 부족한 모양인지, 이 부분을 보통 대학생이 이해할 수 있을 정도로 설명했다는 확신이 서지 않네요. 공부를 더 쌓으며 보충하도록 하겠습니다. 다음에는 확률 분포를 다룰까 합니다.

참고자료

심프슨의 역설

심프슨의 역설 관련 기사

http://en.wikipedia.org/wiki/Simpson's_paradox


베이즈룰

http://en.wikipedia.org/wiki/Bayes_rule

An Intuitive Explanation of Bayesian Reasoning