EBS 위대한 수업3 (모두를 위한 수학) 4강 최고의 검색 엔진 만들기

(2023.10.30 방송)

 

 

EBS 위대한 수업3 (모두를 위한 수학) 4강 최고의 검색 엔진 만들기

위대한 여든아홉 번째 강연 ' 모두를 위한 수학 '(시즌3 여덟 번째)

 

 

 

 

테렌스 타오 UCLA 수학과 교수

미국 대통령 과학기술 자문위원

IQ 230

최연소> 10살 국제 수학 올림피아드 동메달 수상

최연소> 11살 국제 수학 올림피아드 은메달 수상

최연소> 12살 국제 수학 올림피아드 금메달 최연소 수상

필즈상 (2006)

라마누잔상 (2006)

리만상 (2019)

 

 

 

 

 

 

 

4강  최고의 검색 엔진 만들기

 

 

 

 

< 인터넷 검색 엔진의 발전사 >

 

구글 검색 엔진의 핵심인 페이지랭크 알고리즘에

그래프 이론과 선형대수학이 쓰였다

월드 와이드 웹은 사실 역사가 오래되지 않았다

첫 웹페이지는 단순했고 별 내용도 없었다

하지만 월드 와이드 웹은 금세 유명해졌고

웹사이트 수도 순식간에 늘어났다

오늘날 전 세계의 웹사이트 수는 20억 개도 넘는다

 

월드 와이드 웹이 성장함에 따라

원하는 페이지를 찾을 수 있도록 교통정리가 필요해졌다

 

야후 같은 초기 검색 엔진은

월드 와이드 웹을 대분류로 나누려 했다

과학, 예술 등의 주제로 분류했다

하지만 웹페이지가 늘어나며 새로운 페이지들을

일일이 분류하는게 힘들어 한계에 부딪혔다

 

알타비스타 같은 검색 엔진은 키워드를 기준으로 삼았다

키워드를 입력하면 키워드를 포함한 웹사이트들을 보여 줬다

세상의 모든 웹 페이지에 대한 광범위한 색인표가 있었던 것이다

하지만 이런 검색 엔진은 그다지 효율적이지 않았다

 

초기 검색 엔진은 검색어를 입력하면

결과물들이 무작위 순서로 떴다

예를 들어 '유방암'을 검색하면

유방암 환자가 쓴 편지나 유방암 의학 논문이 나오고

유방암 검진 방법 같은 진짜 필요한 정보는 안 나왔다

 

당시의 검색 엔진으로는 좋은 정보를 찾기 힘들었다

유의미한 정보를 찾으려면 검색 결과를 끝없이 뒤져야 했다

당시 검색 엔진의 문제점은 유용성에 따라

웹페이지의 순위를 매기지 못했단 것이다

모든 웹 페이지가 공신력이 있진 않다

 

잡음이나 다름없는 웹 페이지는 밑으로 내려가야 하고

믿을 수 있는 좋은 정보 제공자가

검색 결과 상단에 떠야 한다

 

월드 와이드 웹 초창기엔 사람이 처리할 수 있었다

질이 좋은 웹사이트에는 높은 순위를 매기고

의심스러운 웹사이트는 거르는 것이다

하지만 웹이 성장하며 웹 페이지가 수없이 쏟아졌고

직접 순위를 매기는 건 불가능해졌다

자동으로 모든 웹 페이지에 순위를 매기는 알고리즘을 찾아야 했다

 

일단 현실의 문제를 수학 문제로 바꿔야 한다

당시 두 팀이 동시에 실용적인 해결책을 찾아냈다

1998년, 두 팀 모두 웹 페이지에 순위를 매기는 기술을 개발한다

 

월드 와이드 웹을 '그래프'라는 추상적인 수학 개념으로 바꾸는 것이다

에지는 인터넷 링크이다

페이지 A에 클릭했을 때 페이지 B로 이어지는 링크가 있다면

10억 개의 노드와 그 노드들을 잇는 수십억 개의 에지,

즉 링크가 있는 것이다

 

수학자들은 링크 정보를 이용해

중요한 페이지와 중요하지 않은 페이지를 구분하려 했다

단계 1. 그래프 만들기

수많은 노드와 화살표로 이루어진 그래프를 만들었으니

단계 2. 순위 매기기

중요도에 따라 웹페이지에 순위를 매겨야 한다

 

조금 안이한 접근법도 있다

단순히 웹 페이지로 들어가고 나가는 링크 수를 계산했다

웹 페이지의 중요도=링크 수

정말 중요한 페이지라면 다른 페이지에서

링크를 많이 건다고 생각한 것이다

 

예를 들어 위키피디아는 좋은 정보가 많아서

다른 사이트에서 링크가 잔뜩 걸려 있다

반대로 위키피디아도 수많은 페이지에 링크를 걸고 있다

그렇다면 위키피디아는 공신력 있는 사이트인 것이다

 

괜찮은 방법 같았지만 잘 안 통했다

링크마다 중요도가 다르기 때문이다

이미 공신력 있는 웹사이트가 링크를 걸었다고 해 보자

예를 들어 유방암에 관한 정부 사이트가 있는데

자세한 정보는 어떤 사이트에서 확인하라고 링크를 건 것이다

보건복지부 웹사이트에서 어떤 유방암 관련 사이트를 링크했고

그 링크는 중요한 링크이다

하지만 수많은 웹 피이지에 링크되어 있다 해도

링크한 곳들이 다 무작위로 생선 된, 아무도 모르는 무의미한 페이지라면

무명 사이트에서 건 링크 100개보다는

공신력 있는 사이트 한 곳의 링크가 더 중요하다

 

그러니까 링크마다 가중치를 다르게 줘야 한다

가장 자연스러운 방법은 링크를 건 웹사이트의 중요도에 따르는 것이다

이미 공신력이 확인된 웹사이트의 링크는 중요하고

들어 본 적도 없는 사이트의 링크는 무의미한 것이다

 

하지만 이런 방식은 순환적이란 문제가 있다

지금 문제는 어떤 웹 페이지의 중요도를 알아내는 것이다

즉, 답을 찾기 위해 답을 찾아야 하는 것이다

그래서 이 방법만으로는 문제를 해결할 수 없다

 

하지만 수학에서는 실패는 부분적 성공이다

 

거의 성공했던 방법을 수정하면 성공하는 방법이 되곤 한다

이 경우 성공하는 방법은 이전 방법을 반복하는 것이다

각각의 웹 페이지에 설정한 중요도 값을 계속 갱신하는 것이다

 

시작할 때는 똑같이 설정한 가중치를 사용해서

모든 웹페이지의 가중치를 갱신한다

그러면 웹 페이지의 중요도 값이 바뀐다

페이지에 걸린 링크가 많다면 

적어도 이번 판까지는 더 높은 가중치를 받게 된다

이 과정을 반복한다

 

갱신된 가중치로 가중치를 갱신하는 것이다

그렇게 한 판 더 갱신하면 

웹페이지 중요도를 더 정확하게 얻을 수 있다

이번에는 이전 판에 계산한 가중치를 이용해

모두 똑같은 가중치를 주지 않았다

가장 최근 갱신된 중요도 값을 이용해서

세상 모든 웹 페이지의 중요도를 갱신하는 것이다

 

수학적 증명도 가능하다

세상 모든 웹 페이지의 중요도 값은

하나의 거대한 벡터로 표현할 수 있다

※ 벡터(vector): 숫자를 순서대로 나열한 것

이런 갱신 과정은 행렬 곱셈과 똑같다

벡터에 거대한 행렬을 곱해서 새 벡터로 갱신하는 것이다

그리고 일반적인 상황에선 결과가 수렴한다

이 과정을 계속 반복하면

결국 중요한 웹페이지의 중요도 순위는 올라간다

그리고 덜 중요한 페이지의 중요도 순위는 내려간다

 

이론적으로도 가능하고 10~20개의 웹 페이지로 만들어진

작은 네트워크에서는 실험도 가능하다

하지만 대상이 인터넷 전체면 그리 쉽지 않다

웹 페이지가 수십억 개니까

수십억 차원 벡터에 수십억 차원 행렬을 곱해야 한다

그런 알고리즘엔 엄청난 연산력이 필요하다

현실적으로 불가능하다

 

이런 방식으로는 순식간에 검색 결과를 보여 줄 수 없다

인터넷 전체를 감시하는 대신 더 빠른 방법이 있다

'스파이더'라는 프로그램으로 링크를 타고

웹 페이지를 하나씩 돌아다니며 정보를 수집한 후

가중치를 하나씩 갱신하는 것이다

수십억 개의 페이지를 한 번에 갱신하는 것보다 빠르다

 

세르게이 브린과 래리 페이지는

이 알고리즘에 특허를 내고 '페이지랭크'라고 이름 붙인다

'페이지'는 웹 페이지를 뜻하는 동시에 개발자 중 하나의 성을 딴 말장난이다

두 사람은 차고에 작은 회사를 세우고 실제 검색 엔진을 만든다

그렇게 탄생한 구글은 오늘날 세계적인 회사가 됐다

 

수학을 현실 문제에 응용해 가장 큰 이득을 본 사례일 것이다

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

위대한 수업 (ebs.co.kr)

위대한 수업 Great Minds

 

EBS 1TV 월~금 23:40 ~ 24:00 (본방)

EBS 1TV 토 24:45 ~ 26:15 (종합)  /  EBS 2TV 금 24:00 ~ 26:00 (종합)