더북(TheBook)

마르코프 연쇄 랜덤 서퍼의 행동을 설명하는 과정은 마르코프 연쇄(Markov chain)로 알려져 있다. 마르코프 연쇄는 20세기 초 이 개념을 개발한 러시아 수학자 안드레이 마르코프(Andrey Markov)의 이름을 따서 붙여졌으며, 다양한 분야에 적용할 수 있고, 연구가 많이 이루어졌으며, 유용한 성질을 많이 지니고 있다. 예를 들어 randomsurfer.py가 페이지 0이 아닌 무작위 페이지에서 시작하면 어떨까 하는 생각이 들 수 있다. 마르코프 연쇄의 기본 제약 이론에 따르면 랜덤 서퍼는 어디서든 시작할 수 있다. 랜덤 서퍼가 결국 어느 페이지에 도달할 확률은 어느 페이지에서 시작하든 똑같기 때문이다! 이 과정은 랜덤 서퍼가 어디에서 시작하든 더 많이 서핑해도 더 많은 정보를 제공하지 않는 상태에 마침내 도달한다. 이런 현상을 혼합(mixing)이라고 하는데, 처음에는 직관적으로 와 닿지 않을 수도 있지만 혼합은 혼란스러워 보이는 상황에서 일관된 행위를 설명해준다. 우리가 지금 알아보고 있는 예제에서 보면 혼합은 서퍼가 충분히 오래 서핑한 후 모든 사람에게 웹이 비슷해 보인다는 개념을 설명한다.

마르코프 연쇄가 꼭 혼합 특성을 가지는 건 아니다. 예를 들어 우리 모델에서 URL을 직접 입력하지 못하게 하면 랜덤 서퍼에게 문제가 생기게 할 수 있는 웹 페이지를 만들 수 있다. 사실 웹 페이지 집합에는 거미 덫(spider trap)이라고 하는 페이지가 존재한다. 거미 덫은 자신에게 들어오도록 링크를 유도하지만 밖으로 나가는 링크를 가지고 있지 않다. URL을 직접 입력해 이동하지 않으면 랜덤 서퍼가 거미 덫에 빠질 수 있다. 90-10 규칙의 가장 큰 목적은 혼합을 보장하고 거미 덫 같은 문제를 제거하기 위한 것이다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.