정보 검색의 이론과 실제(데이터 과학)

★ 이 책의 대상 독자 ★

전산학, 컴퓨터 공학, 소프트웨어 엔지니어링 또는 여타 관련 전공의 학부 과정 수준의 지식이 있다고 가정하고 설명한다. 다시 말해 (1) 연결 자료 구조, B-트리, 해시 함수와 같은 기초적인 자료 구조 개념 (2) 알고리즘과 시간의 복잡도 분석 (3) 운영체제, 디스크 장치, 메모리 관리, 파일 시스템 등에 익숙해야 한다는 뜻이다. 이와 더불어 확률 변수, 분포, 확률 질량 함수와 같은 기초적인 확률과 통계 이론도 알고 있다고 가정했다.


★ 이 책의 구성 ★

5부로 구성됐으며 각각 독자적인 구조를 가진다. 1부는 개론에 해당한다. 2부에서 4부까지는 각각 주요 영역인 색인, 검색, 평가를 다룬다. 각 장은 1부를 읽은 다음 순서에 상관없이 독자적으로 읽어도 된다. 5부는 그전까지 소개한 내용을 바탕으로 특정 응용 분야를 깊이 파고든다.
1부부는 정보 검색 기초를 소개한다. 1장에서는 정보 검색 시스템 구조, 용어, 문서의 특성, 문서 형식, 텀 분포, 언어 모델, 문서 모음을 비롯한 기초 개념을 설명한다. 2장은 세 가지 주요 주제인 색인, 검색, 평가의 기초를 설명한다. 각 주제마다 (2부에서 4부까지) 한 부를 할애해 자세히 다룰 것이다. 2장에서 각 주제를 독립적으로 바라볼 수 있는 토대를 마련할 것이다. 1부의 마지막인 3장에서는 1장에서 시작한 주제를 이어가는 동시에 2 장의 내용을 마무리한다. 여기서는 특정 자연어(사람의 언어 등)와 연관된 문제를 다루는데, 그 중에서도 토큰 생성, 즉 문서를 색인하고 검색하도록 일련의 텀으로 바꾸는 절차가 대표적이다. 검색 시스템은 여러 언어가 뒤섞인 문서를 적절히 처리할 수 있어야 하며, 이런 관점에서 여러 주요 언어가 갖는 중요한 특성을 논의할 것이다.

2부는 역색인을 만들고 읽고 유지하는 기술에 초점을 맞춘다. 4장에서 정적 색인을 구축하고 읽는 알고리즘을 살펴볼 것이다. 정적 색인은 문서 모음이 자주 바뀌지 않고, 바뀌었을 때 색인 전체를 재구축할 시간이 충분한 상황에 적합하다. 5장은 색인 읽기와 질의 처리 기법을 설명한다. 이 장에서는 문서 구조를 다루기 위한 경량 구조를 소개하고, 불리언 조건 검색에 이 경량 구조를 적용해본다. 6장은 색인 압축에 관한 내용이다. 7장은 동적 문서 모음을 유지하는 알고리즘을 소개한다. 동적 문서 모음은 질의에 비해서 문서 갱신이 잦고, 갱신을 곧바로 반영해야 하는 속성을 가진다.

3부는 검색 기법과 알고리즘을 다룬다. 8장과 9장은 문서 내용에 기반한 순위화 검색의 주요한 두 가지 기법을 소개, 비교하는데, 바로 확률적 기법과 언어 모델 기법이다. 이러한 순위화 검색 기법은 명시적인 적합도 관련 정보, 즉 문서 구조와 사용자 피드백과 질의 확장으로부터 얻는 정보를 도입하면 효과가 더 높아높아진다. 각 기법에 관련된 자세한 내용을 논의할 것이다. 10장은 문서를 분류하고 제한하는 기술을 소개하며, 문서 구분을 위한 기초적인 머신러닝 알고리즘도 설명한다. 11장에서는 메타 학습 알고리즘과 이를 순위화에 적용하는 방법과 더불어, 증거와 매개변수 조정을 어떻게 결합하는지 소개한다.

4부의 주제는 정보 검색 기법 평가다. 검색 유효성과 능률이라는 두 가지 개념을 개별 장에서 자세히 설명한다. 12장은 기초적인 검색 유효성 지표를 제시하고, 유효성을 측정하기 위한 통계적 기반을 탐구하며, 최근 십여 년 간 전통적인 정보 검색 평가 방법론을 넘어서 새로 제안된 지표들을 논의한다. 13장은 검색 시스템의 성능을 응답 시간과 처리량의 관점에서 평가하는 방법을 설명한다.

마지막 5부에서는 특정 검색 응용 분야 몇 가지를 선택해 4부까지 알아본 일반적인 지식과 개념을 세분화, 구체화한다. 병렬 검색엔진의 구조와 동작 방식은 14장에서 다룬다. 15장은 웹 검색엔진에 관한 내용이다. 여기에는 링크 분석, 문서 수집, 중복 탐지와 같은 내용이 포함된다. 16장은 XML 문서를 대상으로 한 정보 검색이다. 각 장 끝부분에는 더 읽어볼 만한 자료와 연습 문제를 제공한다. 연습 문제는 대체로 각 장에서 소개한 개념을 시험하고 확장해본다. 종이와 연필만 있으면 몇 분 안에 풀 수 있기도 하고 제법 복잡한 프로그래밍 프로젝트 문제도 있다. 참고 자료와 연습 문제를 통해 각 장의 본문에서 다루지 못한 중요한 개념을 배울 수 있다.

★ 옮긴이의 말 ★

오늘날 누구나 일상에서 검색 서비스를 사용한다. 하지만 비전공자는 물론이고 인터넷 서비스에 종사하는 개발자 대다수도 검색 시스템의 구조와 원리는 잘 모른다. 정보 검색은 데이터베이스와 같은 관련 분야와 공통점도 있지만, 그들과 구분되는 고유한 특성도 분명히 갖고 있기 때문이다. 검색 서비스에는 다양한 컴퓨터 시스템이 필요하지만 그 중 검색엔진은 특히 모든 검색 서비스의 공통 요소이자 핵심이다. 일반적으로 검색엔진이라고 말하면 대개 유명한 검색 서비스를 떠올린다. 그리고 검색엔진의 정의를 묻는다면 (검색업계 종사자조차) 저마다의 관점이나 관심사에 따라 다른 대답을 내놓을 것이다. 사견으로는 검색 서비스를 뜻하는 광의의 검색엔진과 문서를 색인하고 질의를 처리하는 시스템을 뜻하는 협의의 검색엔진으로 나눌 수 있을 것 같다. 다시 말해, 검색엔진(서비스)의 핵심에 검색엔진(시스템)이 자리한다. 이제는 수많은 인터넷 서비스에서 검색이 필수 기능으로 여겨진다. 여러분이 직접 검색엔진을 구현하지 않더라도, 어떤 방식으로든 검색에 엮인 일을 맡는다면 이 책이 도움이 될 것이다. 서두에서 언급한 정보 검색의 고유한 특성을 알면 더 효율적으로 목적을 달성할 수 있다. 동작 원리를 알면 좋은 활용법도 찾을 수 있으며, 새로운 아이디어를 구현하는 데도 밑거름이 될 수 있다. 어느 분야나 마찬가지지만, 기초가 탄탄하면 응용하기 쉬워진다. 이 책을 번역하면서 다양한 기술 용어를 되도록이면 우리말로 옮기고자 노력했다. 그 중 학계나 산업계에서 굳어진 원어도 있어서 망설이기도 했지만, 정보 검색 분야가 생소한 독자의 이해를 돕고 싶었다. 영문 용어가 익숙한 독자들은 다소 어색하게 느낄 수 있다. 이 점 너그러이 양해를 구한다.
임형준


인터넷 시대에 검색 엔진은 우리 삶에 없어서는 안 되는 기능이 됐다. 뉴스를 보거나, 모르는 단어를 찾거나, 물건을 사거나, 맛집을 가거나, 다른 사람의 의견을 읽을 때도 먼저 검색을 한다. 꼭 네이버나 구글 같은 검색 서비스를 이용하지 않더라도, 검색 기능은 SNS에도, 휴대폰 사진 앱에도, 서점의 책 검색대에도, 패스트푸드점의 키오스크에도 들어가 있어서 하루에 한 번 이상은 꼭 무언가를 검색하게 되는 것 같다.
이렇게 검색 기능이 여러 곳에서 다양하게 쓰이는 만큼 시중에는 편리하게 쓸 수 있는 검색엔진 솔루션 및 오픈소스 툴이 많이 나와 있다. 개발자들은 실제 검색엔진이 구체적으로 어떤 원리로 어떻게 작동하는지 잘 몰라도, 데이터를 준비한 후에 여러 검색 솔루션 중에 하나를 선택해서 약간 설정해주는 것만으로 검색엔진 기능을 자신의 서비스에 비교적 쉽게 추가할 수 있다.
하지만 모든 일이 그렇듯, 기초를 아는 것이 중요하다. 전반적인 원리를 이해하고 있으면 똑같은 문제를 더 빠르고 쉽게 풀 수도 있고, 새로운 아이디어를 적용해서 다른 방식으로 응용하는 것도 가능해진다. 이 책은 실제 검색 엔진을 연구하고 만들어온 저자들의 경험을 바탕으로 정보 검색론의 전반적인 내용을 한 번씩 다루고 있어서 정보 검색론의 기초를 배우는 데 많은 도움이 될 것으로 생각한다. 실제로 검색 순위화 로직을 오래 개발해온 나 역시 번역하면서 그동안 자세히 몰랐던 내용을 한 번 더 배울 기회를 가질 수 있었던 것 같다. 정보 검색론이 및 검색엔진 기술에 관심이 있거나, 관련 일을 하시는 분들은 참고서적으로 두고 읽어 보시면 좋으리라 생각한다.
김진홍

1부. 기초 지식

1장. 들어가며
1.1 정보 검색이란 무엇인가?
1.1.1 웹 검색
1.1.2 다른 검색 응용 프로그램
1.1.3 다른 정보 검색 응용 분야
1.2 정보 검색 시스템
1.2.1 정보 검색 시스템의 기본 구조
1.2.2 문서 갱신
1.2.3 성능 평가
1.3 전자 문서 다루기
1.3.1 본문 형식
1.3.2 영문에서 간단히 토큰 만들기
1.3.3 텀의 분포
1.3.4 언어 모델링
1.4 시험용 자료 모음
1.4.1 TREC 과업
1.5 오픈소스 정보 검색 시스템
1.5.1 루씬
1.5.2 Indri
1.5.3 Wumpus
1.6 더 읽을거리
1.7 연습 문제
1.8 참고문헌

2장. 검색 기초
2.1 역색인
2.1.1 심화 예제: 구문 검색
2.1.2 역색인 구현하기
2.1.3 문서와 그 밖의 요소들
2.2 문서 선택과 순위화
2.2.1 벡터 공간 모델
2.2.2 근접도 순위화
2.2.3 불리언 검색
2.3 평가
2.3.1 재현율과 정밀도
2.3.2 순위화 검색의 유효성 척도
2.3.3 시험용 자료 만들기
2.3.4 능률 척도
2.4 요약
2.5 더 읽을거리
2.6 연습 문제
2.7 참고문헌

3장. 토큰과 텀
3.1 영어
3.1.1 구두점과 대문자
3.1.2 어간 추출
3.1.3 불용어 제거
3.2 문자
3.3 문자 N-Gram
3.4 유럽 언어
3.5 한중일 언어
3.6 더 읽을거리
3.7 연습 문제
3.8 참고문헌

2부. 색인하기

4장. 정적 역색인
4.1 색인 요소와 생명 주기
4.2 사전
4.3 포스팅 목록
4.4 사전과 포스팅 목록 뒤섞기
4.5 색인 생성
4.5.1 메모리상의 색인 생성
4.5.2 정렬 기반 색인 생성
4.5.3 병합 기반 색인 생성
4.6 다른 색인 유형
4.7 요약
4.8 더 읽을거리
4.9 연습 문제
4.10 참고문헌

5장. 질의 처리하기
5.1 순위화 검색 질의 처리하기
5.1.1 문서 하나씩 질의 처리하기
5.1.2 텀 하나씩 질의 처리하기
5.1.3 점수 분포 미리 계산하기
5.1.4 영향도순 색인
5.1.5 정적 색인 잘라내기
5.2 경량 구조
5.2.1 일반화한 용어 색인 목록
5.2.2 연산자
5.2.3 연산자 예제
5.2.4 구현
5.3 더 읽을거리
5.4 연습 문제
5.5 참고문헌

6장. 색인 압축
6.1 범용 데이터 압축
6.2 심볼 기반 데이터 압축
6.2.1 모델링과 코딩
6.2.2 허프만 코딩
6.2.3 산술 코딩
6.2.4 심볼 기반 본문 압축
6.3 포스팅 목록 압축하기
6.3.1 비모수 기반 차이 압축
6.3.2 모수 기반 차이 압축
6.3.3 컨텍스트를 고려한 압축 방식
6.3.4 질의 처리 성능을 높이는 색인 압축 방식
6.3.5 압축 효과
6.3.6 복호화 성능
6.3.7 문서 재정렬
6.4 사전 압축하기
6.5 요약
6.6 더 읽을거리
6.7 연습 문제
6.8 참고문헌

7장. 동적 역색인
7.1 일괄 갱신
7.2 증분 색인 갱신
7.2.1 연속된 역색인 목록
7.2.1 불연속 역색인 목록
7.3 문서 삭제
7.3.1 무효화 목록
7.3.2 가비지 모음
7.4 문서 변경
7.5 논의점과 더 읽을거리
7.6 연습 문제
7.7 참고문헌

3부. 검색과 순위

8장. 확률적 검색
8.1 적합도 모델링
8.2 이진 독립 모델
8.3 로버트슨/스파크 존스 가중치 공식
8.4 텀 빈도
8.4.1 북스테인의 2-푸아송 모델
8.4.2 2-푸아송 모델의 근사
8.4.3 쿼리 텀 빈도
8.5 문서 길이: BM25
8.6 적합도 피드백
8.6.1 텀 선택
8.6.2 의사 적합도 피드백
8.7 필드 가중치: BM25F
8.8 실험적 비교
8.9 더 읽을거리
8.10 연습 문제
8.11 참고문헌

9장. 언어 모델링 및 관련 방법론
9.1 문서에서 질의 생성하기
9.2 언어 모델과 평활화
9.3 언어 모델로 순위 매기기
9.4 쿨백-라이블러 발산
9.5 무작위성 발산
9.5.1 무작위성 모델
9.5.2 엘리트성
9.5.3 문서 길이 정규화
9.6 구절 검색 및 순위 매기기
9.6.1 구절 점수 매기기
9.6.2 구현
9.7 실험 비교
9.8 더 읽을거리
9.9 연습 문제
9.10 참고문헌

10장. 분류 및 필터링
10.1 자세한 예제
10.1.1 주제 기반 배치 필터링
10.1.2 온라인 필터링
10.1.3 과거 예제에서 학습하기
10.1.4 언어 분류
10.1.5 온라인 적응형 스팸 필터링
10.1.6 이항 분류에서 문턱값 선택
10.2 분류
10.2.1 오즈와 오즈비
10.2.2 분류기 만들기
10.2.3 학습 방식
10.2.4 특성 엔지니어링
10.3 확률적 분류기
10.3.1 확률 추정치
10.3.2 확률 추정치 결합
10.3.3 현실적 고려 사항
10.4 선형 분류기
10.4.1 퍼셉트론 알고리즘
10.4.2 서포트 벡터 머신
10.5 유사도 기반 분류기
10.5.1 로치오 방법
10.5.2 기억 기반 방법
10.6 일반화 선형 모델
10.6.1 커널 방법
10.7 정보 이론 모델
10.7.1 모델 비교
10.7.2 순차 압축 모델
10.7.3 결정 트리와 스텀프
10.8 실험적 비교
10.8.1 주제 기반 온라인 필터링
10.8.2 온라인 적응 스팸 필터링
10.9 더 읽을거리
10.10 연습 문제
10.11 참고문헌

11장. 병합과 메타 학습
11.1 검색 결과 병합
11.1.1 고정 컷오프 집계
11.1.2 순위 및 점수 집계
11.2 스태킹 적응 필터
11.3 스태킹 배치 분류기
11.3.1 홀드아웃 검증
11.3.2 교차 검증
11.4 배깅
11.5 부스팅
11.6 다범주 순위화 및 분류
11.6.1 문서 대 범주 점수
11.6.2 문서 대 범주 순위 병합
11.6.3 다범주 방법들
11.7 순위 학습
11.7.1 순위 학습은 무엇인가?
11.7.2 순위 학습 방법들
11.7.3 무엇을 최적화하나?
11.7.4 분류에서 순위 학습
11.7.5 순위 검색 학습
11.7.6 LETOR 데이터 집합
11.8 더 읽을거리
11.9 연습 문제
11.10 참고문헌

4부 평가

12장. 유효성 측정
12.1 전통적 유효성 척도
12.1.1 재현율과 정밀도
12.1.2 k 개 문서에서 정밀도(P@k )
12.1.3 평균 정밀도
12.1.4 역순위
12.1.5 산술 평균 대 기하 평균
12.1.6 사용자 만족
12.2 텍스트 검색 학회
12.3 통계를 활용한 평가
12.3.1 기초 및 용어
12.3.2 신뢰 구간
12.3.3 비교 평가
12.3.4 유해한 가설 검정
12.3.5 짝의 차이와 짝이 아닌 차이
12.3.6 유의성 검정
12.3.7 타당성과 통계적 검정력
12.3.8 측정 정밀도 보고
12.3.9 메타분석
12.4 판정 노력 최소화하기
12.4.1 판정을 위한 문서 선택
12.4.2 풀 표본 추출
12.5 비전통적 유효성 척도
12.5.1 등급화 적합도
12.5.2 불완전하고 편향된 판정
12.5.3 참신성과 다양성
12.6 더 읽을거리
12.7 연습 문제
12.8 참고문헌

13장. 능률 측정
13.1 능률 기준
13.1.1 처리량과 지연 시간
13.1.2 집계 통계 및 사용자 만족
13.2 대기열 이론
13.2.1 켄달 표기법
13.2.2 M/M/1 대기열 모델
13.2.3 지연 시간 백분위 수와 평균 이용률
13.3 질의 스케줄링
13.4 캐싱
13.4.1 3단계 캐싱
13.4.2 캐시 정책
13.4.3 검색 결과 미리 불러오기
13.5 더 읽을거리
13.6 연습 문제
13.7 참고문헌

5부. 응용 및 확장

14장. 병렬 정보 검색
14.1 질의 병렬 처리
14.11 문서 분할
14.12 텀 분할
14.13 혼합 구조
14.14 서버 복제와 장애 허용
14.2 MapReduce
14.21 기본 프레임워크
14.22 결합기
14.23 이차 키
14.24 장비 장애
14.3 더 읽을거리
14.4 연습 문제
14.5 참고문헌

15장. 웹 검색
15.1 웹 구조
15.1.1 웹 그래프
15.1.2 정적 페이지와 동적 페이지
15.1.3 닿을 수 없는 웹
15.1.4 웹의 전체 규모
15.2 질의와 사용자
15.2.1 사용자 의도
15.2.2 클릭 행동 곡선
15.3 정적 순위화
15.3.1 기본 페이지랭크
15.3.2 확장한 페이지랭크
15.3.3 페이지랭크의 속성
15.3.4 기타 링크 분석 기법: HITS와 SALSA
15.3.5 기타 정적 순위화 기법
15.4 동적 순위화
15.4.1 앵커 텍스트
15.4.2 참신성
15.5 웹 검색 평가
15.5.1 특정 페이지 찾기
15.5.2 암묵적 사용자 피드백
15.6 웹 크롤러
15.6.1 크롤러 구성 요소
15.6.2 수집 순서
15.6.3 페이지 중복
15.7 요약
15.8 더 읽을거리
15.8.1 링크 분석
15.8.2 앵커 텍스트
15.8.3 암묵적 피드백
15.8.4 웹 크롤러
15.9 연습 문제
15.10 참고문헌

16장. XML 검색
16.1 XML의 기초
16.1.1 문서 형식 정의
16.1.2 XML 스키마
16.2 경로, 트리, FLWOR
16.2.1 XPath
16.2.2 NEXI
16.2.3 XQuery
16.3 색인과 질의 처리
16.4 순위 검색
16.4.1 요소 순위화
16.4.2 중복 요소
16.4.3 검색할 수 있는 요소
16.5 평가
16.5.1 시험용 자료 모음
16.5.2 유효성 척도
16.6 더 읽을거리
16.7 연습 문제
16.8 참고문헌

5부 부록

부록 A. 컴퓨터 성능
A.1 디스크 순차 접근과 임의 접근
A.2 RAM 순차 접근과 임의 접근
A.3 파이프라인 실행과 분기 예측

스테판 버처 구글의 소프트웨어 엔지니어며, 워털루 대학의 전산학과 교수다.