구독상품안내
미래를 내다보는 수학
미래를 알기 위해서는 과거와 현재를 알아야 한다. 미래에 일어날 사건의 원인은 대부분 과거와 현재에 있기 때문이다. SF영화에서 주인공이 미래의 문제를 해결하기 위해 타임머신을 타고 과거로 돌아간다는 사실을 보면 이를 쉽게 이해할 수 있다.
수학자들도 과거와 현재를 알면 미래를 예측할 수 있을 것이라고 생각했다. 뉴턴과 동시에 미적분학을 만든 수학자 고트프리트 라이프니츠는 함수와 미적분학을 통해 현재 어떤 물체의 위치와 속도를 알면 미래를 예측할 수 있을 것이라고 생각했다. 수학자 피에르 라플라스도 우주의 모든 원자의 정확한 위치와 운동량을 알고 있다면 과거와 현재의 모든 현상을 설명하고, 미래까지 예언할 수 있다고 생각했다.
러시아의 수학자 안드레이 마르코프도 과거를 통해 미래를 예측하려고 노력했다. 하지만 그는 라이프니츠가 미적분학 같은 대수학을 이용한 것과 달리 확률적인 방법을 썼다.
오늘 오후 수업시간에 잠을 잔 이유에 대해 생각해 보자. ‘수업이 지루해서?’, ‘오전 체육시간에 너무 열심히 운동해서?’, ‘어젯밤 늦게 자서?’ 등의 원인이 있을 것 같다. 마르코프는 수업이 지루하면 잘 확률 30%, 열심히 운동하면 잘 확률 50%, 늦게 자면 잘 확률 40% 등 과거의 행동으로 인해 오늘 잠 잘 확률을 계산했다. 그리고 이런 행동들의 확률을 연속적인 수열로 만들어 다음에 어떤 행동이 일어날 확률을 구하는 ‘마르코프 연쇄’를 만들었다.
그는 마르코프 연쇄를 이용해 1913년 푸쉬킨의 극시 ‘예프게니 오네긴’에 나타나는 자음과 모음의 분포를 분석했다. 책의 첫 2만 자에서 모음과 자음의 기호를 열로 만든 뒤, 이 연쇄에서 자음과 모음이 등장할 확률을 계산했다. 이는 이후 음성인식이나, 문장인식 등과 같은 패턴 인식에 있어 기초가 됐다.
내일 수업 시간에 잠 잘 확률은?
마르코프 연쇄를 조금 더 자세히 알아보자. 앞서 말했듯이 오늘 어떤 일이 일어나는 이유는 전날에 일어난 일 때문이다. 마르코프는 어떤 사건은 그 일이 일어나기 전에 있었던 일과 관련이 있고, 그 둘 사이를 확률로 나타낼 수 있다고 생각했다. 그런데 내가 조는 이유가 한 둘이 아닐 수 있어 무한히 많은 사건을 모두 고려하려면 너무 복잡해져 확률을 구하기 어렵다.
따라서 마르코프는 시간이 연속적이라고 생각하지 않고, 단절적이라고 가정했다. 또한 과거의 무한히 많은 일 때문에 오늘 수업시간에 잤다고 생각하는 대신, 과거의 유한한 몇몇 일 때문에 오늘의 일이 일어났다고 생각했다. 이를 ‘마르코프의 가정’이라고 하는데, 마르코프 연쇄는 이 가정을 따른다.
오늘 수업 시간에 존 이유는 바로 전날의 행동에 따라서 좌우된다. 오늘 잤거나, 쉬었거나, 공부했거나 등의 상태에 따라 내일의 행동이 결정된다는 얘기다. 바꾸어 말하면 오늘의 상태에서 일정한 확률로 계산되어 내일의 상태가 결정된다는 것이다. 이렇게 바로 앞의 상황만이 뒤에 영향을 끼치는 것을 ‘1차 마르코프 연쇄’라고 한다.
‘2차 마르코프 연쇄’는 어제는 물론 그제의 일까지 오늘의 상태에 직접적으로 영향을 끼치는 것을 말한다. 어제 졸았고 오늘도 졸았다면, 내일 졸 확률은 몇 퍼센트라고 계산할 수 있다는 것이다.
그런데 1년 전의 상태가 내일 졸지 여부에 영향을 미칠까? 실제 계산에서는 직접적인 영향을 미치지 않는다. 하지만 전날의 상태는 전전날에 영향을 받고, 전전날의 상태가 전전전날의 영향을 받으니, 결국 연쇄적으로 따진다면 내일 조는지 여부는 태어날 때의 상태와 간접적으로 마치 사슬처럼 관련이 있다. 물론 1차 마르코프 연쇄에서는 내일 졸지 여부는 오늘의 상태만 알면 된다.
직접 보지 않아도 예측할 수 있다
마르코프 연쇄를 이용하면 현재의 상태를 정확히 알지 못해도 내일의 상태를 짐작할 수 있다. 만약 어느 외딴 집에 갇혀 있다고 생각해 보자. 창이 가려져 있어 날씨를 직접적으로 아는 방법은 전혀 없다. 매일 집을 찾는 사람이 우산을 갖고 있거나, 갖고 있지 않거나 여부로 오늘
날씨를 짐작할 수 있다.
이때 아래 표와 같이 확률을 정할 수 있다. 날씨가 맑으면 방문자가 우산을 갖고 올 확률이 0.1이고, 비가 오면 갖고 올 확률이 0.8, 흐린 날씨면 그 확률이 0.5라고 정하자.
이런 식으로 날씨에 대해서는 알 수 없지만, 우산의 여부에 따라 확률적으로 날씨를 알게끔 만든 것을 ‘은닉 마르코프 모델’이라고 한다. 은닉 마르코프 모델은 직접적인 관찰이 불가능하지만 특정한 지표를 나타낼 확률이 정해져 있는 경우에 쓸 수 있다.
예를 들어 생물학에서 단백질 서열이나 염기서열에서 숨겨진 정보를 이용해 그 기능을 추측할 때 사용된다. 이 밖에도 음성인식과 같이 기계학습이 필요한 부분에서 많이 쓰인다. 기계학습은 컴퓨터가 어떤 문제를 푸는 과정에서 얻은 경험을 학습해, 다음에 그 문제를 풀 때 활용하는 능력을 말한다. 은닉 마르코프 모델은 이런 기계학습을 이용하는 음성인식이나 패턴 인식, 신호처리, 데이터 마이닝 등에서도 많이 사용되고 있다.
최강의 타순 찾는 마르코프 연쇄
마르코프 연쇄는 야구에 활용되기도 한다. 야구는 다른 운동과 달리 계속 움직이지는 않는, 단절적인 운동이다. 야구에서 타자는 안타, 2루타, 3루타, 홈런, 볼넷, 아웃을 당할 확률을 갖고 있다. 이에 따라 아웃 카운트나, 루상의 주자의 위치가 달라지는데, 이를 24가지 상태로 나눌 수 있다.
위 그림과 같은 1아웃 주자 3루 상황에서의 상태 변화를 보자. 동그라미 안의 왼쪽 숫자는 주자 상황을 뜻하고, 오른쪽 숫자는 아웃 카운트이다. 홈런이 나오면 득점이 2점 나오며, 1아웃 주자가 없는 상태로 변한다. 여기서 3루타가 나오면 득점이 1점 나오고, 상태는 그대로 이어진다. 만일 2아웃일 때 아웃이 나오면 3아웃이 돼 이닝이 끝난다. 이를 마르코프 연쇄로 만들어 반복적으로 시뮬레이션하면 타자의 득점 기여도를 알 수 있다.
KAIST의 장영재 교수의 연구팀은 2010시즌 모든 구단의 매 경기별 선수의 타격과 주루 플레이 데이터를 모아 어떤 팀이 가장 효율적으로 타순을 짰는지 알아봤다. 마르코프 연쇄로 모델을 만든 뒤, 이 모델을 검증하기 위해 2010년 각 팀의 실제 점수와 모델이 예측한 점수 분포를 비교했다. SK는 예상 점수가 평균 5.218점이었는데 비해 실제는 5.293점이 나왔다. 오차가 1.4%로 어느 정도 신뢰할 수 있는 모델이었다.
모델이 검증된 뒤에는 이 모델을 바탕으로 가능한 모든 타순 조합의 예상 점수를 계산해 가장 효율적인 타순을 구성한 팀을 구했다. 그 결과 2010년 국내 야구팀 중 효율적인 타순을 구성한 팀은 이대호가 있던 롯데와 그 해 우승팀 SK였다. 롯데는 거포타자들이 대거 포진해 타순 구성이 그리 어렵지 않았다. 반면 SK는 김성근 감독이 선발 투수에 따라 매번 타순을 바꾸는 방식을 추구했다. 이런 많은 변화 속에서도 다른 팀에 비해 효율적인 타순을 구사할 수 있었던 것은 김성근 감독이 추구한 데이터 야구의 결과라고 할 수 있다.
가장 중요한 웹페이지 찾는 마르코프 연쇄
‘구글’의 검색 원리인 페이지랭크에도 마르코프 연쇄의 아이디어가 사용됐다. 래리 페이지와 세르게이 브린은 1995년 미국 스탠퍼드대에 다니던 중 페이지랭크를 개발해, 이를 바탕으로 구글을 설립했다.
페이지랭크는 웹페이지의 상대적 중요도에 따라 10단계로 순위를 나눈다. 그 뒤 높은 순위의 페이지를 가장 먼저 검색 페이지에 나타나게 한다. 그런데 단순히 많은 사람들이 다녀갔거나 많은 링크를 받은 것이 아닌, 중요한 사이트에서 많이 링크돼야 높은 순위를 받을 수 있다. 따라서 페이지랭크는 해당 페이지만이 아니라 그것과 링크된 페이지의 중요도 역시 고려한다.
이런 중요성을 판단하기 위해 페이지랭크는 지구상에 존재하는 모든 웹페이지와 그 페이지 간에 걸려 있는 링크들을 오른쪽의 다이어그램에 그린다. 그리고 어떤 한 웹페이지에서 링크를 따라 무작위로 페이지를 따라가는 일종의 로봇 ‘랜덤 서퍼’를 만들었다. 이때는 각 링크를 따라갈 확률 값을 대충 준다. 어떤 페이지에 링크가 2개면 각 링크를 따라 다른 페이지로 갈 확률은 각각 50%, 50%라고 하고, 10개면 10%, 10%, 10%라는 식으로 그냥 정하는 것이다.
이렇게 웹을 단순한 구조로 그린 뒤, 각 단계에서 다음 단계로 넘어갈 확률을 구해 마르코프 연쇄에 적용한다. 이런 마르코프 연쇄 위에서 랜덤 서퍼가 마구 이동을 하다가 갑자기 멈췄을 때, 이 랜덤 서퍼가 웹페이지에 있을 확률을 구한다. 이 확률이 가장 높은 웹페이지가 인터넷 상에서 가장 영향력 있는 페이지라고 생각해, 높은 순위로 정한다.
래리 페이지와 세르게이 브린은 페이지랭크를 만들 때 마르코프 연쇄를 몰랐다고 한다. 실제 검색의 원리를 만들고 나서 보니, 그 원리가 마르코프 연쇄였던 것이다. 현재 마르코프 연쇄는 구글 검색 원리 이외에도 최적화 문제, 통신과 금융에서의 의사 결정 시스템 등에서 널리 쓰이고 있다. 갈수록 미래를 예측하는 것이 중요해지고 있는 만큼 마르코프 연쇄도 날이 갈수록 더 많이 사용될 것으로 보인다.
