Chap. 19 Information Retrieval (정보검색)

소개(Introductions)

• IR

- 2차 저장장치에 있는 비구조적(unstructured) 텍스트 데이터에 대한 저장/질의

	대상자료	연산	DB 크기
관계형데이터베이스(DB) 정보검색(IR) 인공지능(AI)	테이블 문헌 논리문장	검색(결정적) 검색(확률적) 추론(reasoning)	다양(small ～ big) 다양(small ～ big) 보통(small)

ex) 교원대도서관(lib.knue.ac.kr): 여러 사이트들 연결

교육연구정보서비스(ERIS, eris.knue.ac.kr)

한국교육학술정보원(www.riss4u.net), 국회도서관 학위논문(www.nanet.go.kr)

교육학전문 문헌정보(www.eric.ed.gov),

IEEE Digital Library(http://computer.org/publications/dlib/), …

http://was0.knue.ac.kr:7780/knueportlet/main.jsp

- 문헌/기사 온라인 도서관(digital library)

1. 저장: 문서의 분석, 분류, 색인

2. 질의: 키워드 기반 질의, 불리언 연산 (and, or, not), 유사검색, 문서의 연관도/순위, 관련도 측정(용어빈도/hyperlink 정보 등 사용)

⇒ Dialog 등

⇒ ‘HTML 문서들’의 집합인 웹에서도 사용됨

- 전문(full text) 검색: 각 문서의 ‘모든’ 단어들이 키워드로 고려됨.

⇒ 문서 내의 각 단어들은 ‘용어(term)’라고 불리워짐.

- '확률적' 검색: 검색된 문헌들이 사용자가 필요로 하는 정보라고 확신할 수 없다.

⇒ IR에 있어서는 ‘관련된’ 문헌들이 누락되고 ‘관련없는’ 문헌들이 검색될 수 있다.

⇒ ‘관련성’(relevance)의 문제, Why?

⇒ Syntactics/Expression (computer, visible) ← Semantics/Purpose (human, invisible)

ex) Art, Science : Is it possible for us to know the 'meaning' of that?

⇒ Syntactics/Expression(the world)으로부터 Semantics/Purpose를 알 수 있는가?

• 정보검색 시스템 분류

- 정보검색 시스템 분류를 위한 속성(facet)들과 속성값(term, 용어)

개념모델	질의연산	파일구조	용어연산	문헌연산	하드웨어
문자열탐색 불리언 확장 불리언 확률성 벡터공간	파스 피드백 불리언 클러스터	플랫파일 역파일 요약파일 PAT 트리 그래프 해싱	스템 절단 시소러스 불용어목록 가중치	식별자할당 파스 디스플레이 클러스터 배치 정렬 필드마스크	폰노이만 병렬 정보검색전용 광학디스크 자기디스크

- 절단: 용어가 여러 개의 단어와 부합되도록 하기 위해 wildcard 문자를 사용하여 용어들을 인위적으로 융합시키는 것.

ex) '절단?‘을 입력하면 ’절단하다‘, ’절단된‘, ’절단‘과 같은 용어들을 산출

• 일반적인 IR 수행과정

- 문헌 저장

1. 문헌들을 하나씩 받아들여 유일한 식별자(ID)가 주어지고, 텍스트들은 단어들로 분해된다.

2. 단어들은 색인이 '불필요한' 단어의 집합인 ‘불용어(stop word) 목록’에 대해 비교된다.

⇒ 관사, 전치사 등 (the, of, and, to, …)

⇒ 전형적인 English 텍스트에서 20-30% 차지

3. 단어들이 불용어목록에 없으면 다음으로 어간(stem)이 구분된다.

⇒ 용어 대신 어간을 저장함 (user, users, used, using, … → 'use')

⇒ 단일 어간을 ‘다수의’ 용어와 일치시킴

⇒ 50% 이상의 압축비율을 달성

4. 단어들의 빈도수가 계산되며, 문헌, 문헌 내의 항목, 총 단어수와 같은 관련정보와 단어들이 DB로 입력된다.

5. 색인(index)은 키워드와 문헌식별자의 쌍으로 구성된다.

⇒ 역파일 (inverted file)

- 문헌 탐색

1. 사용자는 불리언 연산자로 연결된 ‘키워드’를 입력시킨다.

2. 용어는 역파일에서 찾게 되고, 용어에 대응하는 문헌식별자의 ‘목록’ 집합이 연산자에 따라서 결합된다.

3. 만약 빈도수 정보가 있다면 검색된 집합은 ‘관련성’의 순서대로 보여진다.

⇒ 순위화(ranking)

⇒ 관련성 순서대로 문헌을 정렬하여 순위화

4. 검색성능을 향상시키기 위한 여러 가지 방법들이 있다.

⇒ 동의어를 출력하는 시소러스(thesaurus) 사용 등

검색 유효성 검사

• 저장공간을 줄이기 위해 인덱스는 검색의 정확도가 좀 떨어지게 저장됨

①거짓누락(false drop)/거짓부재(false negative): 일부 관련 문서들이 검색되지 않음.

②거짓실재(false positive): 일부 관련 없는 문서들이 검색됨.

⇒ 좋은 인덱스 구조란 ‘거짓누락’을 가지지 않으며, ‘거짓실재’는 일부 허용하는 것.

• IR 시스템의 평가

① 조회율(recall): 질의가 주어졌을 때 ‘DB 내’의 관련 문헌수에 대한 ‘검색된’ 관련 문헌수의 비율 (재현율이라고도 함)

⇒ 질의와 관련된 문서 중 몇 %가 검색되었는가?

⇒ 일반적으로 정확한 ‘분모’를 알 수 없으며, 표본추출 등의 방법을 통하여 예측.

② 정확도(precision): ‘검색된’ 문헌의 총수에 대한 ‘관련’ 문헌수의 비율

⇒ 검색된 문서 중 몇 %가 실제로 질의와 관련이 있는가?

- 문제점: 사용자의 ‘질의의도’와 실제 ‘해당문서’가 관련성이 어느 정도인가를 판단하는 문제

- 조회율-정확도 그래프: 역관계가 성립,  P∝1/R

문서의 인덱스 작업 - 역색인(Inverted Index)/역파일(Inverted File)

• 색인형태의 역파일의 개념

- 키워드의 ‘정렬된’ 색인: e.g., 찾아보기

⇒ 각 해당 키워드가 포함된 문헌으로 연결할 수 있는 링크를 가짐

⇒ 각 키워드 Ki와 ‘Ki를 포함하는 문서들의 리스트’ Si 간의 대응관계 제공

⇒ 특정 키워드(Ki)를 포함하는 문헌들(Si)을 효율적으로 검색

- 포스팅(posting): 문헌정보들을 ‘등기’

• 역파일의 구현: 정렬된 배열, B+-트리, 트라이/패트리샤(PAT) 트리, 해싱 등

- B+-트리

- 장점: 검색시간이 빠름, 갱신이 용이, 메모리 대신 보조기억장치를 사용했을 때 효율이 좋음.

- 단점: 정렬된 배열보다 구현이 복잡.

• 역파일의 생성

1. 파싱: 입력되는 문헌의 용어들을 텍스트문서 내의 위치에 따라 용어목록으로 분할

⇒ 연관성 순위를 지원하기 위해서 해당 키워드가 나타나는 ‘문서 내의 위치(record no.)’ 제공  e.g., record #1: 제목/초록, record #2: 서론 ...

2. 정렬: 위치순서 목록으로부터 ‘순서화된’ 목록으로 변경

⇒ 도치(inverting) - 중복된 용어들을 그대로 정렬

3. 후처리: 항목에 가중치를 주거나 재배열, 압축 등

⇒ 순위화를 위해 '용어빈도수'를 유지

• 불리언 검색

- AND 연산: 키워드들 ‘모두를’ 포함하는 문서들 검색

① 지정된 키워드 집합 K1, K2, …, Kn 각각을 포함하는 문서식별자 집합 검색

⇒ S1, S2, …, Sn

② 해당 집합들의 '교집합' 산출

⇒ S1 ∩ S2 ∩ … ∩ Sn

- OR 연산: 키워드들 중 ‘적어도 하나를’ 포함하는 문서들 검색

① 지정된 키워드 집합 K1, K2, …, Kn 각각을 포함하는 문서식별자 집합 검색

⇒ S1, S2, …, Sn

② 해당 집합들의 '합집합' 산출

⇒ S1 ∪ S2 ∪ … ∪ Sn

- NOT 연산: 키워드를 ‘포함하지 않는’ 문서들 검색

① 지정된 키워드 Ki를 포함하는 문서식별자 집합 Si 검색

② 전체문서 식별자 집합 S와의 '차집합' 산출

⇒ S - Si

용어를 이용한 연관성 순위화

• History

- 질의 표현식을 만족시키는 문서들의 집합은 매우 클 수 있음.

⇒ 웹 상의 수십억 개의 문서들 중 '수십만 건'의 문서 집합.

- '질의(query)'에 대한 '문서(document)'의 '연관성'을 측정하여 높은 순위의 문서들을 반환하는 IR 시스템

⇒ 검색된 문헌들을 사용자 질의와 관련있는 ‘순서(ranking)’로 제공하는 ‘사용자 위주’ 검색시스템의 필요성

1. 벡터공간 모델

- n개의 서로 다른 용어들, (t1, t2, …, tn)을 사용하는 문헌데이터 '집합(DB)'

⇒ 그 중 하나의 '문헌'은 하나의 벡터, (v1, v2, …, vn)으로 표현 가능

⇒ '질의'도 같은 방식으로 표현 가능

ex) 7개의 용어들을 갖는 문헌 집합

① 단순한 방법 (simple match)

② 가중치 사용 (weighted match)

⇒ 용어가중치 부여방식은 순위부여에 있어서 상당한 성능향상을 제공

ex) 다음 문헌 1에서 ‘factors'는 2번, ’information'은 3번 나타남

- ‘유사성’ 기반 검색: 문헌 및 질의 vector를 n차원 vector 공간의 좌표로 간주

⇒ n: 데이터 집합에 있는 용어의 수

⇒ 유사성을 사용한 순위부여 방식

- 코사인 유사도(cosine similarity): 두 vector가 이루는 각의 cosine값을 계산

⇒ 모든 용어가 일치하면 1, 어떠한 용어도 공유하지 않으면 0

td(term document), tq(term query)

c.f. 유클리디안 디스턴스(Euclidean distance)

= √ ∑ni=1 (tdij - tqik)2
⇔ 코사인 디스턴스(cosine distance)

- SMART 시스템에서 사용 (Salton, 1964): 최초의 IR 시스템

⇒ Salton's Magical Automatic Retrieval of Text (Gerald Salton)

⇒ TREC(Text Retrieval Conference)이 시작됨

2. 확률 모델

- 연관성 있는 용어들은 ‘많이’ 언급될 것이라는 가정

⇒ 문서 d내의 용어 t의 ‘빈도수’를 연관성의 척도로 사용

⇒ 빈도수를 사용한 순위부여 방식

- 질의키워드 용어 t에 대한 문서 d의 연관성 척도, TF(term frequency)

TF(d,t) = log{1 + n(d,t)/n(d)}

where n(d): 문서 d의 용어의 개수	(문서의 크기)

n(d,t): 문서 d에서 용어 t의 빈도수

- 부가정보에 의한 TF의 '보정'

ex)	용어 t가 제목이나 초록에 나타나는 경우

용어 t가 본문의 뒷부분보다 앞부분에 나타나는 경우

- 여러 키워드를 가지는 질의의 경우: 각 키워드에 대한 문서의 연관성들을 결합.

⇒ 단순히 더함.

⇒ 그러나, 키워드 용어가 모두 동등한 것은 아님.

ex) 'database' and 'data warehouse'

⇒ ‘database': 흔한 용어, 'data warehouse': 흔치 않은 용어

document #1: ‘database'는 없고 ’data warehouse'는 있는 문서

document #2: ‘database'는 있고 ’data warehouse'는 없는 문서

⇒ document #1이 더 연관성이 있다고 판단.

- Salton & Yang (1973): 장서에 '자주 쓰이지 않는' 문헌용어와 일치하는 질의용어에 더 큰 가중치를 부여

⇒ 역문헌빈도수(inverted document frequency, IDF)

IDF(t) = 1/n(t)

n(t): DB내에 용어 t를 포함하는 문서들의 개수

- TF-IDF 방법: 키워드용어 집합 Q에 대한 문서 d의 연관성

r(d,Q) = Σt∈Q {TF(d,t) * IDF(t)} ; Term Freq.에 역가중치를 부여.

정보검색과 구조적 데이터

• Idea

- Unstructured 문서들로부터 Structured 정보들을 추출

⇒ Structured 정보들을 바탕으로 문서 질의를 처리

• 정보추출

ex1) 부동산 광고문

“Queens에 있는 침실 2개이며 욕실 3개인 집이 가격은 ＄1,000,000입니다“

⇒	지역: Queens

침실: 2

욕실: 3

가격: 1,000,000

ex2) 신문 기사 monitoring

주요 기업 인사의 신임/사임 등 인사관련 정보

• 구조적 데이터에 대한 (키워드기반) 질의

- Relational DB: SQL

- XML DB: XQuery

- 키워드기반 질의형식 사용

ex) "Smith Queens"

'Queens' 지점과 거래하는 'Smith' ‘고객’ 정보

⇒ (Branch ∞ Customer)

'Queens' 지점과 거래하는 'Smith' ‘예금’ 정보

⇒ (Branch ∞ Depositor)

…

- 질의가 완전히 명시되지 않음

⇒ 다양한 질의 결과들을 순위화하여 사용자에게 제시

디렉토리(Directory)

• Idea

- 도서관에서는 서로 ‘관련 있는’ 서적들을 가깝게 배치

⇒ 찾은 책 근처에 있는 다른 관련 서적들도 검색 가능

⇒ 분류계층(classification hierarchy) 사용

• IR 시스템

- 브라우징을 위해서 ‘논리적으로’ 문서들을 조직화할 필요성

⇒ 도서관과 같이 ‘분류계층’을 사용

⇒ 특정문서에 가까운 문서들을 부가적으로 표시 가능함

- 계층(hierarchy)에서 '순환'(cycle)이 가능

⇒ graph (not tree)

⇒ 한 문서가 ‘두 개 이상’의 영역에 속할 수 있음

• Directory 사용 검색

- 디렉토리의 루트에서 시작

⇒ ‘원하는’ 주제를 나타내는 노드에 이르기까지 계층의 아래 방향으로 검색

⇒ 그 과정에서 관심주제 문서 뿐만이 아니라 관련문서나 관련분류들도 참고 가능

• Web Directory:

ex) Yahoo: 웹을 directory 구조로 계층화함

1993년: 최초의 웹 브라우저인 모자이크 출시

1994년: 야후의 기본틀이 된 ‘제리와 데이비드의 월드와이드웹 가이드’ 공개

(구글스토리, 랜덤하우스중앙, 2005)

웹 검색엔진(Web Search Engine)

• History

(구글스토리, 랜덤하우스중앙, 2005)

(구글스토리, 랜덤하우스중앙, 2005)

• 구조

1. 웹 수집기(Crawler)

- 웹상의 문서들을 찾아주는 ‘정보수집’ 프로그램

⇒ ‘주어진 문서’(root)로부터 하이퍼링크를 재귀적으로(recursively) 따라가며 연결된 다른 문서들을 찾음

⇒ 브라우저처럼 웹 사이트들에 요청을 보냄

- 문서를 검색한 후 ‘문서정보’를 인덱스에 추가

⇒ 더 많은 사이트를/더 자주, ‘크롤’할수록 인덱스는 더욱 완벽해질 수 있음

⇒ 크롤러가 감당하고 있는 모든 페이지들을 다시 수집하는데 수주/수개월이 걸림

⇒ 문서자체가 저장되지는 않음

- 수집을 위해 다수의 장비와 다수의 프로세스들이 존재

⇒ 크롤러 DB는 수집해야할 사이트들의 집합을 저장

⇒ (서로 다른 기계에 있는) 각 수집 프로세스에 링크들이 할당됨

⇒ 병렬 수행 (parallel processing)

2. 인덱스 시스템(Indexer)

- 거대한 인덱스를 관리

⇒ 크롤러로부터 수집된 페이지들에 관한 ‘정보’들을 분석

⇒ 용어들, 링크들, 앵커(anchor) 텍스트들 (링크 내/주변에 있는 용어) 등

⇒ 역전환(inverting), 즉 ‘URL의 페이지’로부터 ‘용어와 관련된 URL 목록’을 만듬

⇒ 어떤 ‘순위화’ 알고리듬을 사용할 것인가?

- 분산(distributed) 인덱스 사용의 경우

⇒ 삽입/삭제시 병행제어(concurrency control) 처리가 필요함

- 두 개의 인덱스 사용

⇒ 하나는 ‘질의처리’에, 하나는 새로 수집한 페이지들의 ‘갱신작업’에 사용

⇒ 주기적으로 서로 바꾸어서 사용

3. 질의 처리기(Query Processor)

- 응답시간(response time)을 줄이기 위해 인덱스를 여러 기계의 '주기억장치'에 적재

⇒ 부하조절

- Crawler/Indexer/Query Processor: 수만 대의 기계가 필요

ex) Google의 경우: 175,000대 이상의 기계를 사용

⇒ 2,400만개의 웹페이지들을 크롤

- 연관성 피드백(relevance feedback): 주어진 질의 키워드들을 포함하는 방대한 양의 문서들 중에서 관련 문서들을 찾는데 사용

⇒ 시스템이 반환한 문서들 중에서 하나, 또는 몇 개의 관련문서들을 선택

⇒ 유사도를 측정하여 다른 유사한 문서들을 반환

⇒ 키워드들을 더 ‘추가’하도록 하여 질의를 ‘수정’하는 방법도 가능

- 개념기반 질의: 사용자가 찾는 ‘개념’을 기술하고 있는 문서들을 반환

⇒ 사용자에게 몇 개의 개념들을 제시하고, 사용자가 그 중 하나를 지정하도록 함

ex)	테이블: 데이터 (표), 테이블: 가구 (탁자)

Jaguar:동물,	Jaguar:자동차

하이퍼링크를 이용한 연관성

• History

- 초기의 웹 검색엔진: TF-IDF에 기반한 연관성 순위화 방식 사용

⇒ 텍스트만을 고려

⇒ 문제점: IR과 Web은 다름.

“IR 분야의 첫 번째 벤치마킹 대상인 TREC은 규모가 작고, 통제가 제대로 이루어지고 있는 검색자료 집합을 대상으로 하고 있다. 따라서 TREC에서 잘 작동하는 방식들이 웹에서는 좋은 결과를 산출하지 못한다.

…

전통적으로 잘 통제되고 있는 IR과 Web의 또 다른 큰 차이점은 사람들이 웹에 올릴 수 있는 것에 대해서는 사실상 통제할 수가 없다는 점이다. 그러다보니, 트래픽을 전송하는 검색엔진들의 '엄청난 영향력'과 무엇이든 올릴 수 있는 융통성을 이용해서 수익을 내기위해 정교하게 검색엔진들을 조작하는 기업들이 심각한 문제가 되고 있다.

이것은 전통적인 폐쇄형 IR 시스템에서는 다루어지지 않은 문제이다.“

<래리 페이지 & 세르게이 브린, 1997>

• 인기도 순위화 (popularity/prestige ranking)

- 키워드를 포함하는 해당 문서들 중에서 ‘인기있는’ 문서들이 높은 순위를 가짐

⇒ 대부분의 검색은 인기있는 문서들로부터 정보를 얻기 위한 것임을 가정

- ‘인기도’를 어떻게 정의할 것인가?

⇒ 해당 사이트/페이지에 대한 액세스 횟수?

⇒ 해당 사이트의 협조 없이는 불가능

- 웹은 IR과는 다른 ‘하이퍼링크‘(hyperlink)라는 아주 중요한 정보를 가지고 있음

⇒ 많은 사용자들이 자신들이 즐겨찾는 웹 페이지들을 링크하는 웹 페이지들을 가지고 있음

⇒ 문서를 ‘가리키는’ 하이퍼링크를 더 나은 연관성 순위화를 얻는데 사용

⇒ ‘인기도’

- 웹의 수학적 특성: 그래프(graph)

⇒ BackRub: 웹에 있는 모든 링크를 모아서 역추적하는 것

⇒ 1,000만개의 페이지와 1억개의 링크가 존재 (1995년, 웹의 초기)

⇒ 누가 누구에게 링크되어 있는가를 파악

ex) Google

(구글스토리, 랜덤하우스중앙, 2005)

① 방법 #1: 해당 페이지를 링크하고 있는 페이지들의 ‘갯수’ 사용

⇒ 문제점: 외부 링크들은 흔히 사이트의 ‘루트 페이지’만을 가리키고, 루트 페이지가 ‘하부 페이지’들을 가리키고 있음

⇒ 하부 페이지들은 루트 페이지에 비해 인기가 없다는 결론?

② 방법 #2: 인기도를 페이지 단위가 아니고 ‘사이트 단위’로 평가

⇒ 한 사이트의 ‘모든 페이지’들이 그 사이트의 인기도를 가짐

⇒ 문제점: 거의 관련이 없는 사이트들을 ‘호스팅'(hosting)하는 페이지의 경우

③ 방법 #3: ‘인기있는 페이지’가 가리키는 다른 페이지에 인기도를 ‘전이’(transfer)

⇒ '인기있는 페이지 x'에서 페이지 y로의 링크 > '인기없는 페이지 z'에서 페이지 y로의 링크

ex) 인기 모델들의 광고

ex) 사회적 관계망(social network): 1950년대 사회학자들이 사람들의 ‘명성’ (prestige)을 어떻게 정의할 것인가를 연구

⇒ 대통령은 '많은' 사람들이 알고있기 때문에 명성이 높다.

⇒ 또한, 여러 명의 '명성있는 사람'들에 의해 알려져 있다면 비록 ‘많은’ 사람들에 의해 알려져 있지 않아도 그 역시 높은 명성을 갖는다.

- 1996년 8월, Google의 첫 번째 버전이 Stanford 대학 웹 사이트에 올려짐

⇒ BackRub crawler는 Stanford 대학 전체 대역폭의 절반 가까이를 사용

ex) 학술논문(paper)의 인용(citation) 지수

과학기술논문 인용색인(Science Citation Index, www.thomsonscientific.co.kr)

- 미국 과학정보연구소(ISI: Institute for Scientific Information)가 과학기술분야 학술잡지에 게재된 논문의 색인을 수록한 데이타베이스.

- ISI사는 1958년 설립된 학술정보전문 민간기관. 매년 학술적 기여도가 높은 학술지를 엄선하고, 동 학술지에 수록된 논문의 색인 및 인용정보를 데이터베이스(SCI DB)화하여, 이를 필요로 하는 수요자에게 제공.

- SCI에는 ISI설립초기부터 현재까지 구축한 천만건 이상의 과학기술정보가 수록되어 있으며, 특정 논문이나 책 등이 '얼마나 많이' 인용되었는지, 또 '어떤 다른 논문에' 인용되었는지 알 수 있음.

- ISI는 매년 전 세계에서 출판되고 있는 과학기술저널 중에 자체 기준과 전문가의 심사를 거쳐 등록 학술지를 결정. 따라서 SCI의 등록여부는 세계적으로 그 권위를 인정받고 있는 학술지 평가기준이 됨.

- ISI에서 선정한 학술지에 수록된 논문은 세계적 권위를 인정받고 있으며, SCI의 인용도에 따라 과학논문의 질 평가가 가능. 따라서 SCI의 수록 논문수 및 인용도는 국가 및 기관간의 과학기술 연구 수준을 비교하거나 연구비 지원, 학위인정 및 학술상(award) 심사 등의 반영자료로도 활용됨.

- 한편, ISI는 SCI외에 '사회과학논문 인용색인(SSCI:Social Science Citation Index),', '예술 및 인문과학논문 인용색인(A&HCI:Art and Humanities Citation Index)' 등도 제공. <terms.naver.com>

• 페이지랭크 (page rank)

- 임의보행 모델(random walk model)

① 임의의 다른 페이지로 건너 뜀 (점프 확률): δ의 확률

② 현재의 페이지에 있는 링크들 중 하나를 임의로 따라감: (1-δ)의 확률

⇒ 어떤 페이지의 페이지랭크: '임의보행' 사용자가 어떤 시점에 그 페이지를 방문할 ‘확률’을 계산

⇒ ① ‘많은’ 페이지가 가리키는 페이지는 방문될 확률이 높음 +

② '높은 페이지랭크를 가지는 페이지'가 가리키는 페이지는 방문될 확률이 높음

- 페이지들의 페이지랭크: 선형 연립 방정식(simultaneous linear equation)으로 정의

⇒ 순환적(recursive): 한 페이지의 인기도(P[j])는 그 페이지를 가리키는 다른 페이지의 인기도(P[i])에 의해 정의

⇒ 반복적인(iterative) 행렬처리 기법으로 ‘해’를 구함

- 페이지 식별자: i, j

확률 행렬: T[i, j] // i에서 j로 링크를 따라갈 확률

⇒ i로부터의 각 링크가 동등한 확률을 가지고 있다고 가정, T[i,j]=1/Ni

T[i,j]=1/Ni

페이지 i

페이지 j

Ni

P[j] = δ*1/Nj // j를 가리키는 링크 수, 즉, 다른 페이지에서 페이지 j로 점프될 확률

+(1-δ)*∑Nii=1 (T[i,j]*P[i]) // 페이지랭크 P[i]를 가진 페이지에서 j로 따라올 확률

- 특정 사이트로 이어진 링크의 수(Nj)와 그 링크를 담고 있는 사이트에 연결된 링크의 수(Ni) 모두를 고려

• 다른 인기도 측정 방법들

- Pagerank 문제점: 인기도가 질의 ‘키워드’와는 무관하게 결정됨

ex)  IF pagerank(google.com) >  pagerank(stanford.edu)

⇒ 'Stanford' 단어가 google.com 페이지에도 있는 경우

⇒ ‘Stanford' 키워드에 대해서 google.com 페이지가 stanford.edu 페이지 보다 우선순위로 결정됨

- 해결책: 연결문(anchor text)에 해당 키워드가 사용된 페이지가 연관성이 더 높다고 판단함.

ex)  <a href="http://stanford.edu"> Stanford University </a>

- Pagerank 방식은 연결문 기반 방식, TF-IDF 등과 함께 사용 가능

⇒ 대부분의 검색엔진은 ‘어떤 연관성 순위화 방식’을 사용하는가를 밝히지 않음

⇒ 검색엔진 스패밍 방지

• 검색엔진 스패밍(spamming)

- 실제로 인기있지 않은 사이트를 ‘고의로’ 높은 연관성 순위를 갖도록 만드는 수법

ex) TF-IDF 방식의 경우

‘여행’ 단어를 많이 넣으면 ‘여행’ 키워드에 대해 높은 순위를 가질 수 있음

⇒ 반복되는 단어들을 흰 배경색에 흰 글꼴로 작게하여 보이지 않도록 함

ex) pagerank 방식의 경우

서로를 가리키는 웹 페이지들의 집합을 많이 생성

- 검색엔진 스패머와 검색엔진과의 싸움은 ‘현재진행형’

(구글스토리, 랜덤하우스중앙, 2005)

(구글스토리, 랜덤하우스중앙, 2005)

(구글스토리, 랜덤하우스중앙, 2005)

동의어, 동음이의어, 온톨로지

• 시소러스(thesaurus): 용어 사전

- 용어들의 ‘동의어’와 ‘유사어’를 분류하고, 상호간의 '관계'와 '계통'을 생성

⇒ 색인과 검색 과정에서 ‘가장 적절한 용어’를 선정할 수 있도록 하여줌.

⇒ 특정 ‘주제영역’(domain)을 대상으로 설계되며, 분야에 따라 다름.

- 질의의 확장/수정에 사용: 가장 적절한 검색 전략을 설계

① 충분한 문헌을 수집하지 못한 경우: 시소러스는 용어들 사이의 다양한 연결을 통하여 질의를 '확장'

ex) 키워드 'motocycle AND maintenance'의 제목을 갖는 문헌들 검색

⇒ ‘Motocycle Rapair'라는 문헌은 검색되지 않음

⇒ 시소러스의 동의어를 사용하여 질의를 확장

motocycle and (repair or maintenance)

② 너무 많은 문헌이 검색된 경우: 시소러스는 보다 '특정한' 검색 문구를 제시

ex) 날 수 있는 ‘동물’ ⇒ 날 수 있는 ‘포유류’

- ‘계층적인’ 집합

⇒ 분야 내의 최상위 레벨을 나타내는 ‘루트’ 용어(TT: Top Term)로부터 각 계층이 만들어짐.

ex) INSPEC 시소러스: 물리학/전자공학/전자학/컴퓨터와제어 분야

UT: 대체집합으로부터 선택된 형태

NT: 보다 특정한 용어

BT: 보다 일반적인 용어

RT: 관련된 용어, [부분-전체]/[객체-특성] 등

CC/FC: INSPEC 분류 설계로부터 형성, 용어가 사용되는 주제영역을 나타냄

⇒ 수작업에 의한 시소러스의 생성은 상당히 개념적이고 지식집적도가 높은 ‘노동집약적’인 특성을 가짐

• 용어관련성(term relationship)

- 의미론적(semantic): 용어 간에 존재하는 ‘개념적인’ 상호작용

- 세 가지 범주

① ‘동등한’ 관련성

동의어(synonym)

준동의어(quasi-synonym): 검색의 목적 하에서 동의어로 간주될 수 있는 용어

ex) 유전현상(genetics) - 유전형질(heredity)

반의어(antonym): 동일한 특성에서 ‘상반된’ 관점

ex) 거칠음(harshness) - 유연함(tenderness)

② ‘계층적인’ 관련성

종의 분류(genus - species)

ex) 개(dog) - 경찰견(shepherd)

③ ‘비계층적’ 관련성

전체 - 부분	ex) 버스(bus)  - 좌석(seat)

개체 - 속성	ex) 장미(rose) - 향기(fragance)

• 시소러스 생성: 'Art' +'Science'

- 수작업 처리과정

① ‘주제영역’을 정의함

핵심/주변 주제분야 선정

세부영역으로 분할

② 각각의 세부영역에 대한 ‘용어’를 수집

색인/백과사전/편람/교과서/잡지/초록 등과 같은 다양한 자원이 사용됨

이미 존재하는 적절한 문구시스템과 시소러스 참조

③ 용어들은 동의어/광의어/협의어 등을 포함한 ‘용어관련성’에 대해서 분석됨

각각의 세부영역 내에서 계층도와 같은 구조로 조직화

④ 전체 시소러스의 ‘일관성’ 검사

구절형태와 단어형태 등을 재검사하고 정제함

⑤ 전체 시소러스의 ‘도치’ (inverting)

계층적으로 구조된 시소러스를 알파벳순으로 정렬

⑥ 시소러스의 '유지관리'

지속적인 생존성과 효율성을 보장

해당영역 내에서 술어(terminology)들의 변화를 반영

갱신된 시소러스는 이전의 정보를 유지하여야 함 (consistency)

• 온톨로지(ontology)

- 개념들 간의 ‘관계’를 반영하는 계층구조

-	is-a 관계:	(표범 is-a 포유류), (포유류 is-a 척추동물) 등

part-of 관계:	(방향타 part-of 꼬리날개), (꼬리날개 part-of 비행기) 등

ex) Wordnet (wordnet.princeton.edu)

단어와 관련된 개념들을 정의: 동의어군(synset)

기타 다른 관계들: 동음이의어, is-a, part-of 등

⇒ 결과적으로 온톨로지를 형성

- 언어를 나타내는 온톨로지 외에도 ‘특정 분야’(domain)에서 사용되는 용어들을 ‘표준화’하기 위해 만들어질 수 있음.

⇒ 기업 간의 주문을 처리

⇒ 조직 간의 데이터 흐름에 대한 ‘표준’(standard)을 구축

ex) Oracle의 경우

“Semantic Data Integration for the Enterprise” (Mar. 2006)

- C. C. Liu, et. al., "Portfolio Search Engine Based on Personal Construct System", IEEE ICALT '05

Traditional search engines use 'keywords' to retrieve documents from database, and then the query result only shows documents having these keywords. However, these search engines can NOT retrieve documents including 'implicit' concepts, because these words of implicit concepts will NOT show in documents.

For instance, a student enters the keywords "Good User Interface" for searching documents in Data Structure learning web. If these documents do NOT have the keywords, the traditional search engine will NOT retrieve any documents, although these documents have the characteristics of 'Good User Interface' such as 'Clean Interface'.

- 다중언어 온톨로지: 여러 언어들을 연결하는 온톨로지

⇒ 언어들 간의 공통개념들을 연결

⇒ 문서 번역에 사용 가능

⇒ 여러 언어 문서들을 대상으로 하여 검색할 수 있는 개념기반 검색 구현

- 추론(reasoning) 온톨로지

ex) Cyc 프로젝트 (http://en.wikipedia.org/wiki/Cyc)

- An artificial intelligence project that attempts to assemble a comprehensive ontology and database of 'everyday common sense knowledge'

- Enabling AI applications to perform 'human-like reasoning'.

- Started in 1984 by Doug Lenat as part of Microelectronics and Computer Technology Corporation.

- "Cyc" (from "encyclopedia", pronounced like 'psych') is a registered trademark owned by Cycorp, Inc. in Austin, Texas

- More recently, Cyc has been made available to AI researchers under a research-purposes license as ResearchCyc.

- The Knowledge Base (KB) contains over 'a million' human-defined assertions, rules or common sense ideas.

- Formulated in the language CycL, which is based on predicate calculus and has a syntax similar to that of the Lisp programming language.

- The most important predicates are '#$isa' and '#$genls'.

- The first one describes that one item is an 'instance' of some collection, the second one that one collection is a 'subcollection' of another one.

- Facts about concepts are asserted using certain CycL sentences. Predicates are written before their arguments, in parentheses:

(#$isa #$BillClinton #$UnitedStatesPresident)

"Bill Clinton belongs to the collection of U.S. presidents"

(#$genls #$Tree-ThePlant #$Plant)

"All trees are plants".

(#$capitalCity #$France #$Paris)

"Paris is the capital of France."

- Sentences can also contain variables, strings starting with "?". These sentences are called "rules". One important rule asserted about the #$isa predicate reads

(#$implies

(#$and

(#$isa ?OBJ ?SUBSET)

(#$genls ?SUBSET ?SUPERSET))

(#$isa ?OBJ ?SUPERSET))

"If OBJ is an instance of the collection SUBSET and SUBSET is a subcollection of SUPERSET, then OBJ is an instance of the collection SUPERSET".

(#$relationAllExists #$biologicalMother #$ChordataPhylum #$FemaleAnimal)

"For every instance of the collection #$ChordataPhylum (i.e. for every chordate), there exists a female animal (instance of #$FemaleAnimal) which is its mother (described by the predicate #$biologicalMother)."

Lab. #1: Structured Data on the Web

• XML

Lab. #2: Search Engine

• Lucene

Lab. #3: Semantic Web

• RDF