책소개
★ 이 책의 대상 독자 ★
전산학, 컴퓨터 공학, 소프트웨어 엔지니어링 또는 여타 관련 전공의 학부 과정 수준의 지식이 있다고 가정하고 설명한다. 다시 말해 (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 문서를 대상으로 한 정보 검색이다. 각 장 끝부분에는 더 읽어볼 만한 자료와 연습 문제를 제공한다. 연습 문제는 대체로 각 장에서 소개한 개념을 시험하고 확장해본다. 종이와 연필만 있으면 몇 분 안에 풀 수 있기도 하고 제법 복잡한 프로그래밍 프로젝트 문제도 있다. 참고 자료와 연습 문제를 통해 각 장의 본문에서 다루지 못한 중요한 개념을 배울 수 있다.
목차
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 파이프라인 실행과 분기 예측
저자소개
스테판 버처