우리가 늘 사용하는 구글 검색은 인터넷에 존재하는 수조개의 문서중 우리가 필요한 문서를 찾아내는 실로 엄청난 작업입니다.

90년대 초 인터넷 초장기에는 필요한 문서를 조회하는데 주로 디렉터리 서비스를 이용했습니다.

디렉터리 서비스란, 인터넷 사이트를 주제별로 일목요연하게 정리한 서비스를 말합니다. 대표적으로 야후, 과거의 네이버 등이있습니다.

예를들어 아래 과거의 네이버 처럼, 교육 이라는 카테고리안에 대학, 시험 등등의 소 카테고리를 갖고 그 안에 관련된 사이트를 매칭시켜주는 방식이지요.

이러한 작업은 모두 사람이 직접 했었기 때문에 웹에 사이트가 많지 않은 예전에는 가능했으나 시간이 지남에 따라 유지하기 불가능한 방식이었습니다.

그 시절 스텐포드 두 괴짜 대학원생은 새로운 검색엔진을 개발하게 되는데, 그것이 오늘날의 구글 검색이었습니다.

1. 기본 방식

구글 검색시스템의 기본적인 방식은 웹에 존재하는 엄청난 문서를 색인(Index)하는데 있습니다.

색인이란 인터넷에 있는 문서를 수집하여 검색에 적합하도록 보관하는 작업인데, 구글에서는 2013년에만 30조개, 16년에 100조개 이상의 문서를 색인작업했다고 하죠.

구글은 이러한 엄청난 데이터를 저장하기 위해 무거운 컴퓨터 한대보다는 가벼운 컴퓨터 수백 수천대에 나눠 저장하는 방식을 도입하였고, 이를 구글 파일 시스템 (GFS) 라고 명명하였습니다.

이러한 방식은 초기 빅데이터 플랫폼의 원형이 되어 본격적인 빅데이터 플랫폼이 등장하고, 나아가 인공지능의 시대를 여는 초석이 되기도 하였습니다.

2. 검색 엔진

구글은 이처럼 빅데이터 플랫폼을 구축해 막대한 양의 문서를 저장할 수 있었습니다.

그런데 구글은 저장한 수많은 문서중 우리가 입력한 쿼리에 딱 적합한 10개의 문서를 찾아낼 수 있고, 거기에 걸리는 시간은 0.5초가 채 걸리지 않습니다.

검색 엔진은 어떻게 이런 일을 할 수 있는 것일까요?

a. 크롤러

이를 위해서 가장먼저 필요한 것은 문서를 수집하는 일입니다.

문서를 수집하기 위해서는 인터넷 곳곳을 돌아다녀야 할텐데요. 크롤러(Crwaler, spider)라 불리는 프로그램은 여러 웹 페이지를 방문 하며 색인 DB에 정보를 추가합니다.

이와 동시에 방문한 사이트에 존재하는 모든 URL 정보를 방문 큐에 추가하여 다음 행선지를 결정합니다.

거미가 가까운 줄을 타고 이동하듯 웹 곳곳을 돌아다니며 정보를 수집하는 것이지요.

다음 방문지를 선정하는 알고리즘은 선택 정책(Select Policy)이라 불리며 오늘날에도 좋은 연구주제입니다.

과거 이러한 크롤러의 방문 때문에 과도한 트래픽을 견디지 못하는 업체들에서 반발이 심했다고하네요.

b. 색인

문서를 수집했으니 그다음으로 색인을 생성해야합니다. 그럼 색인이란 정확하게 무엇일까요?

새로 구입한 냉장고의 사용 설명서를 읽는다고 가정해보겠습니다.

냉장고 청소 방법을 찾기위해 우리는 설명서의 처음부터 끝까지 모든 내용을 정독하지 않습니다. 대신 맨 앞장에 있는 색인을 참고해 청소 방법이 어느 페이지에 있는지 먼저 알아보죠.

이처럼 색인은 우리가 필요한 데이터의 위치를 정리해둔 또다른 데이터입니다.

검색엔진에서도 이와 마찬가지로, 항목을 먼저 정리해두는 색인 구축과정을 거치게됩니다.

그렇다면 검색엔진은 이러한 색인을 사용하여 어떻게 결과를 가져올까요?

‘파란색 나무 단추’를 검색한다 생각하였을 때 위 그림처럼 각 단어를 포함하는 페이지에 대한 색인 데이터가 존재하고, 각 단어를 모두 포함하고 있는 11번 페이지를 보여주는 방식입니다.

그러나, 위 예시처럼 단 하나의 문서만 검색되는 경우는 거의 없고, 수백 수천 문서들이 검색되는 경우가 대부분입니다.

따라서 우리는 어떤 문서를 가장 먼저 노출할 지에 대한 고민이 필요합니다.

그렇지 않으면 우리는 필요한 사이트보다는 이를 악용한 광고, 스팸사이트만 잔뜩 노출되게 될테니까요.

c. 줄세우기

그렇다면 어떻게해야 스팸을 줄이고 사용자가 필요한 사이트를 제공할 수 있을까요?

이를 위해 구글은 Pecking order 즉 줄세우기 방식을 사용합니다.

Pecking order는 닭이 서열 순서에 따라 모이를 쪼듯, 불필요한 경쟁을 없이개 위해 우선순위를 정하는 일입니다.

이를 통해 사용자에게 보다 적합한 우선순위가 높은 정보를 제공할 수 있죠.

그러나 문제가 하나 있습니다.

서로 다른 특성을 가진 대상을 비교할 때 순위 부여는 간단한 문제가 아닙니다.

만약 소와 참새중 어떤 동물이 크냐라는 질문에 우리는 소가 크다고 손쉽게 답할 수 있지만, 소와 말중에 어떤 동물이 크냐라는 질문에 우리는 쉽게 답할 수 없죠.

한가지 기준으로 비교할 수 없는 대상이기 때문입니다.

대신 우리는 두가지 기준을 사용해 말은 소보다 키는 크지만 몸통은 작다라고 답을 할 수 있을 것입니다.

구글에서는 말과 소를 두가지 기준으로 비교한 것처럼 다양한 면을 모두 고려하여 우선순위 점수를 부여합니다.

대략 200개의 기준을 사용한다고해요.

• 쿼리가 문서 제목에 포함되어 있는가?

• 긴 문서인가?

• 문서 로딩이 빠른가?

• 사이트에 접솔할 수 없는 상황이 자주 발생하는가?

• 모바일에서 잘 보이는가?

• 문서 내에 쿼리가 많이 포함되어 있는가?

• 동일한 사이트에 중복으로 나오는 콘텐츠인가?

• 다른 문서에서 복사한 내용인가?

• 본문 내용의 수준이 지적인 내용인가? 욕설로 가득한가?

• 저작권이 정식으로 표기되어 있는가?

• SNS에 링크가 걸려있는가?

• …

  d. 쿼리에 딱 맞는 문서 찾기

앞선 기준중 긴 문서인가? 문서 로딩이 빠른가 등등 문서의 질에 대한 기준은 사용자가 쿼리를 입력하기 전 미리 계산할 수 있는 값입니다.

그러나 쿼리에 딱 맞는 문서를 찾는 작업은 사용자가 검색 버튼은 클릭한 순간 빠르게 처리해야하는 작업이지요. 가히 검색 엔진의 핵심이라 할 수 있습니다.

먼저 사용자가 입력한 쿼리가 문서 어디쯤 위치하는지가 중요합니다.

제목에 위치하는 것이 본문에 위치하는 것보다 더 높은 점수를 받습니다.

또, 순서대로 매칭되어있는지도 중요합니다.

예를들어 쿼리가 ‘갤럭시 노트 신제품’일 경우 단어 사이의 간격이 좁을 수 록 높은 점수를 받습니다. 이를 근접도(Proximity)라고 합니다.

예를 들어 아래와 같이 두가지 문서가 있다고 가정해보겠습니다.

• 얼마 전 삼정전자에서 갤럭시 노트의 신제품을 출시했습니다. 새로운 기능에 대한 고객들의 기대가 큽니다.
• 신제품이 나온지 벌써 1년여가 지났지만 노트에 글을 쓰는 느낌을 주는 갤럭시는 아직 등장하지 않고있습니다.

위 문서처럼 단어 사이의 근접도가 높은경우 사용자가 찾고자 하는 문서일 확률이 높습니다.

이에 반해 아래 문서와 같이 근접도가 매우 떨어지는 경우 그렇지 않을 확률이 높죠.

다음으로 TF-IDF 알고리즘을 사용합니다. (Term frequency inverse document frequency)

정보 검색 분야에서 가장 중요한 발명품이라 불리는 TF-IDF 알고리즘은 업계 시장 83%를 장악하고 있습니다.

그럼 먼저 TF-IDF란 무었일까요?

여기서 TF는 한 문서내 단어의 출현 빈도를 의미하고, IDF는 다른 문서내 출현 빈도의 역수를 의미합니다. IDF는 다른 문서에서 출현 빈도가 높을 수록 낮은 값이 되는것이지요.

TF-IDF는 아래와 같은 공식으로 계산합니다. (IDF는 로그로 계산하지만 임의로 분수로 취급)

아래 간단한 예시를 통해 해당 알고리즘을 이해해보도록 하겠습니다.

쿼리: 갤럭시 노트 신제품

1. 갤럭시 노트 신제품 출시
2. 갤럭시 노트 신제품 출시 새로운 노트 만나보세요.
3. 갤러시 노트 과연 기존 노트 시리즈와 차별화된 노트 될까
4. 갤럭시 전용 케이스 얇아진 두께에 따라 더욱 도드라져 보이는 디자인
5. 삼성전자 역대 최고 실적 기록 반도체의 힘 파운드리 상반기 최대 매출.

먼저 쿼리 단어 하나씩 TF-IDF 점수를 계산하고 그를 합산하여 문서에 최종 점수를 산정합니다.

1번 문서만 계산해보도록 하겠습니다.

먼저 ‘갤럭시’라는 단어는 1번 문서에 1회 등장함으로 TF값은 1이 될것입니다. ‘갤럭시’가 등장하는 문서는 1, 2, 3, 4 로 총 4회가 되어 IDF 값은 1/4되어 최종적으로 1번 문서에서 ‘갤럭시’의 TF-IDF 값은 TF * IDF로 0.25가 되겠습니다.

다음으로 '노트'라는 단어의 TF값은 1, IDF 값은 1/3으로 TF-IDE 값은 0.33 입니다.

마지막으로 '신제품'이라는 단어의 TF값은 1, IDF 값은 1/2으로 TF-IDE 값은 0.5 입니다.

결과적으로 1번 문서에서 갤럭시 노트 신제품이라는 쿼리의 TF-IDF 점수는 1.08점이 되겠습니다.

이처럼 각 문서별로 각 단어의 TF-IDF 점수를 계산하여 합산하면 아래와 같은 표를 얻을 수 있습니다.

문서	갤럭시 TF-IDF	노트 TF-IDF	신제품 TF-IDF	갤럭시 노트 신제품 TF-IDF
1. 갤럭시 노트 신제품 출시	0.25	0.33	0.5	1.08
2. 갤럭시 노트 신제품 출시 새로운 노트 만나보세요.	0.25	0.66	0.5	1.41
3. 갤러시 노트 과연 기존 노트 시리즈와 차별화된 노트 될까	0.25	1	0	1.25
4. 갤럭시 전용 케이스 얇아진 두께에 따라 더욱 도드라져 보이는 디자인	0.25	0	0	0.25
5. 삼성전자 역대 최고 실적 기록 반도체의 힘 파운드리 상반기 최대 매출.	0	0	0	0

2번 문서는 1.41점으로 가장 먼저 노출됩니다.

반대로 5번 문서는 0점으로 쿼리와 전혀 관련없는 문서입니다. 최종적으로 2, 3, 1, 4, 5 순으로 노출되게 되겠네요.

이것이 바로 TF-IDF 점수의 핵심입니다. 물론 사실 실무에서는 이보다 훨씬더 복잡한 계산을 사용합니다.

BM25 (BestMatching 25) 알고리즘은 TF-IDF의 방언격인 점수로 이와 마찬가지로 다른 문서에 출현하지 않은 단어가 해당 문서에 출현 할 경우 높은 우선순위를 부여합니다.

여기에 몇가지 최적화를 덛붙여 좀 더 정밀한 우선순위를 부여하죠.

위 식은 실제 실무에서 사용하는 BM25의 계산 식입니다.

우리가 유일하게 컨트롤 할 수 있는 k1과 b 값은 통계학자들이 세심하게 실험해 결정하는 값이라고해요.

3. 검색 결과의 개선

구글은 앞서 말한 유사도, 문서의 품질, 최신문서 여부 등등 수많은 조건로 문서들의 우선순위를 산정합니다.

그렇다면 이렇게 줄세운 결과가 과연 사용자에게 적합한 결과인지 어떻게 확인할까요?

구글은 A/B 테스트를 적극 활용합니다.

A/B 테스트란 하나의 집단을 비슷한 비율로 무작위로 A그룹과 B그룹으로 나눈 후, 각 그룹에게 서로 다른 옵션을 제공한 뒤 두 집단의 반응을 살펴 좀 더 좋은 옵션을 선택하는 실험입니다.

구글은 2011년 한 해에만 7,000건의 A/B 테스트를 진행했을 많큼 이를 통해 검색엔진의 정확도를 높히려 노력하고있습니다.

우리가 이따금씩 같은 쿼리에 대한 결과가 친구와 다른 경우 우리는 알게 모르게 이 A/B테스트에 참여하고있는 것이지요.

4. 딥러닝의 등장

우리는 새로운 게임기를 사기위해 “플레이스테이션” 이라고 검색하지만, 이따금씩 “소니에서 개발한 회색 게임기” 라고 검색하기도 합니다.

실제로 위 쿼리로 검색하면 구글은 플레이스테이션1에 대한 정보를 제공하는데요.

이것은 단순히 쿼리 단어를 포함하는지에 대한 판단을 넘어 단어와 단어간의 관계를 파악하고 문장의 의미를 정확하게 이해해야만 가능한 일입니다.

딥러닝은 이러한 문장의 의미를 이해하고 이에 맞는 정답을 찾아주는 역할을합니다.

딥러닝을 활용하여 비슷한 의미를 가진 단어를 비슷한 숫자로 표현할 수 있고, 유사한 의미를 지닌 단어로 판별할 수 있게됩니다.

서로 다른 성질을 가진 물건을 화폐라는 동일한 기준으로 비교하는 것 처럼 말이지요.

예컨데 딥러닝은 ‘갤럭시 노트 신제품’과 ‘삼성 핸드폰 신상’이라는 단어에 가중치를 줄 수 있습니다.

워드 투벡, 언어를 숫자로 바꾸다.

2013년 구글은 단어의 의미를 벡터로 표현하는 매우 획기적인 방법을 발표합니다.

워드투벡(word2Vec)이라 이름붙은 이 알고리즘은 단어 각각의 특징을 추출해 수치화할 수 있습니다.

예를 들어 ‘단맛’, ‘크기’, ‘둥근정도’ 라는 세가지 특징으로 단어를 표현해 보겠습니다.

각 특징에 0.01점 부터 0.99점까지 가중치를 부여하겠습니다.

단어	단맛	크기	둥근 정도
캐러멜	0.92	0.06	0.02
호박	0.23	0.26	0.62
태양	0.01	0.99	0.99

이렇게 각각 특징에 부여된 가중지를 좌표 평면에 나타내면 아래와 같은 그림을 얻을 수 있습니다.

비로서 우리는 이제 호박은 캐러멜보다는 태양과 더 비슷하다는 것을 알 수 있죠.

여기서 핵심은 어떤 특징을 어떤 값으로 추출할 것인가입니다.

워드 투벡은 이 값을 수동으로 설정하지 않습니다.

대신 엄청난 문장을 학습한 딥러닝으로 하여금 이 값을 자동으로 찾도록 하고있죠.

워드투벡이 등장한 2013년까지만 하더라도 딥러닝 연구가 활발하지 않던 시절이었습니다. 또한 워드투벡은 지금의 딥러닝에 비해 매우 얕은 구조에 불과했죠.

그러나 문장에서 특징을 자동으로 선별하여 유사도를 비교적 정확하게 비교할 수 있다는 점에서 매우 혁신적인 기술이었습니다.

---

Ref 도서. 비전공자도 이해할 수 있는 AI지식 - 구글이 세상을 검색하는법