Information Retrieval (Chapter 3: 검색 평가) 서정연교수 Office: 공학관 816 Tel: 705-8488 Email: seojy@sogang.ac.kr

소개 검색 시스템이 얼마나 정확하게 원하는 답을 검색하는가? 검색 평가를 위해서는 시험 참조 컬렉션(test reference collection)이 필요하다. 시험 참조 컬렉션의 구성 문헌의 컬렉션 사용자 정보요구 집합(질의 집합) 정보요구에 연관된 문헌 집합(answer set) TIPSTER/TREC, CACM, CISI, Cystic Fibrosis HANTEC

소개(계속) 검색 작업에 따른 평가 대화형 작업 (대화세션, 10장 참조) 일괄처리 작업 사용자의 노력, 인터페이스 설계의 특성, 시스템이 제공하는 안내, 세션의 길이 등이 중요한 평가 척도 일괄처리 작업 응답 집합의 Quality가 가장 중요한 척도 검색 성능 평가의 주류 실험실 수준의 평가가 반복적인 가능성과 확장 가능성 때문에 평가의 주류를 이루고 있음

소개(계속) 정보검색 시스템 평가 검색성능 평가 기능 평가 성능 평가(performance evaluation) 효율(efficiency): 시간 복잡도, 공간 복잡도 효과(effectiveness): 검색 성능 평가 질의 결과의 정확성 평가 실험 참조 컬렉션과 평가 척도 사용 검색성능 평가 재현율(recall) 정확률(precision)

재현율과 정확률 N 가장 널리 사용되는 평가 척도 both 컬렉션 |Ra| |A| |R| |Ra| =2 연관문헌 집합 |A|=8 시스템 결과 집합 both |Ra| =2 시스템 결과가 연관문헌에 포함된 문헌 N 컬렉션 검색된 연관 문헌 검색되지 않은 비연관 문헌 검색(O) 검색(X) 연관 (X) (O)

재현율과 정확률(계속) 재현율: 연관 문헌 집합(R) 중에서 연관된 문헌이 검색된 비율 R = |Ra| / |R| 예) P = |Ra| / |A| |A| - 질의에 의해서 검색된 문헌 수 예 ) P=2/8=0.2 이상적인 검색 결과: 재현율 100%, 정확률 100% 원하는 모든 문헌이 검색되고, 원하지 않는 모든 문헌이 검색되지 않는다.

재현율과 정확률(계속) 예) Rq={d3, d5, d9, d25, d39, d44, d56, d71, d389, d123} Rq : 질의 q에 대한 연관 문헌 집합. (1) 질의 q에 의해서 검색된 문헌의 순위 : d123, d84, d56 정확률 : 66 % (2 / 3) 재현율 : 20 % (2 / 10) 1. d123*! 6. d9! 11. d38 2. d84 7. d511 12. d48 3. d56*! 8. d129 13. d250 4. d6 9. d187 14. d113 5. d8 10. d25! 15. d3! (2) 질의 q에 의해서 검색된 문헌의 순위 : d123, d84, d56 ,d6, d8, d9 정확률 : 50 % (3 / 6) 재현율 : 30 % (3 / 10)

재현율과 정확률(계속) – 구체적인 계산 방법 가정: 전체 연관 문헌 = 5 R=1/5=0.2; p=1/1=1 R=2/5=0.4; p=2/2=1 R=2/5=0.4; p=2/3=0.67 R=5/5=1; p=5/13=0.38

질의 용어가 결과에 미치는 영향 과제: Information retrieval 초기 질의: Information and retrieval 넓은 질의(Broader query): Information or retrieval 높은 재현율, 낮은 정확률 좁은 질의(Narrower query) : Information adjacent Retrieval 높은 정확률, 낮은 재현율

재현율/정확율 그래프 정확률 재현율 재현율을 고정했을 때, 평균 정확률 그래프 이상적인 정확률 0 0.1 0.2 1 0 0.1 0.2 1 재현율 정확률 0 0.1 0.2 1 이상적인 정확률 재현율을 고정했을 때, 평균 정확률 그래프

평균정확률(Average Precision) 재현율 수준에 따른 평균 정확률 Nq : 질의 수 Pi(r) : i번째 질의에 대해 재현율 r에서 정확률 보간된 정확률(Interpolated precision) Pj(r):j번째 재현율 수준과 j+1번째 재현율 수준에서의 정확률의 최대값 8쪽에 있는 테이블의 보간된 정확률

평균정확률(계속) 0.4 0.8 1.0 0.6 0.2 1 2 3 4 5 6 7 12 13 200 recall precision

평균정확률(계속) 보간된 정확률(Interpolated precision) 1.0 0.8 0.6 0.4 0.2 x 보간된 원래

단일 요약 수치(Single value summary) 단일 정확률의 필요 질의에 대해서 검색 알고리즘의 검색 결과를 비교할 때, 재현율과 정확률의 두 수치로는 어느 시스템이 우수한지 알 수 없다. 재현율에 따른 평균 정확률 도표의 단점 여러 질의에 대한 정확률 평균 : 검색 알고리즘의 중요한 결점이 숨겨질 수 있다 각각의 질의에 대한 성능 검사 필요하다. 검색된 연관 문헌에서의 평균 정확률 (Average Precision) Pavg : 새로운 연관 문헌이 검색될 때, 정확률의 평균 예) 연관 문헌 수: 1 2 3 4 5 정확률 1 0.66 0.5 0.4 0.3 Pavg= (1 + 0.66 + 0.5 + 0.4 + 0.3) / 5 = 0.57 연관 문헌을 빨리 찾는 시스템이 좋은 성능을 갖는다

단일 요약 수치 (계속) R-정확률 : R 번째 검색 순위에서 정확률 R : 질의에 대한 연관 문헌의 전체 수 개별적인 질의에 대한 검색 성능을 관찰할 수 있다. 모든 질의에 대한 R-정확률의 평균도 구할 수 있다. 정확률 히스토그램(Precision histogram) : 두 알고리즘에 대한 R-정확률 차이를 그린 막대 그래프 RPA/B(i) = RPA(i) - RPB(i) RPA(i) : i번째 질의에 대한 검색 알고리즘 A의 R-정확률 RPB(i) : i번째 질의에 대한 검색 알고리즘 B의 R-정확률 두 알고리즘의 성능 차이를 시각적으로 확인할 수 있다.

단일 요약 수치 (계속) 요약 테이블 통계치(Summary table statistics) : 모든 질의들에 대한 단일 수치를 테이블로 작성 예) 검색 작업에 사용된 질의 수 전체 질의에 의해 검색된 문헌 수 전체 질의에 의해 검색될 수 있는 연관 문헌의 수 모든 질의를 고려할 때, 검색된 연관 문헌의 수

정확률과 재현율의 문제점 높은 재현율을 얻기 위해서 컬렉션에 있는 모든 문헌에 대한 지식이 필요하다. 대규모 컬렉션일 경우에는 불가능하다. 질의의 개별적인 특성은 관찰하기 위해서 재현율과 정확률을 사용하는 것은 적절하지 않다. 재현율과 정확률은 시스템의 전체 성능은 관찰할 수 있다. 단일 수치를 사용하는 것이 바람직하다. 대화형 검색에서 재현율과 정확률은 적합하지 못하다. 최근의 대부분 검색 시스템은 대화형 검색 시스템이다 검색 결과를 순위화하지 않을 때, 재현율과 정확률을 사용하는 것은 적합하지 않다.

다른 척도 조화 평균(Harmonic mean) F(j) r(j) : j번째 순위의 문헌의 재현율 p(j) : j번째 순위의 문헌의 정확률 F(j) = 0 : 연관된 문헌이 하나도 검색되지 않음 F(j) = 1: 연관된 문헌이 모두 검색됨. 재현율과 정확률이 모두 높아야 조화평균이 높다. E 척도(E-measure) E(j) b : 재현율과 정확률의 중요도를 조절하는 매개변수 b = 1 : F(j)의 보수(complement) b > 1 : 정확률을 강조 b < 1 : 재현율을 강조

다른 척도 - 사용자 중심의 척도들(User-oriented measure) 사용자에 따라 연관 문헌이 서로 다르다. 적용율(coverage ratio) = |Rk| / |U| 사용자에게 미리 알려진 연관문헌 중에서 실제로 검색된 연관 문헌의 비율 높은 적용율 : 검색 시스템이 사용자가 기대하는 대부분의 연관문헌을 검색 신문헌율(novelty ratio) = |Ru| / (|Ru| + |Rk|) 검색된 연관 문헌 중에서 사용자에게 미리 알려지지 않은 문헌의 비율 높은 신문헌율: 시스템이 사용자에게 미리 알려지지 않은 새로운 연관 문헌을 많이 검색 |R| |A| |U| |Rk| |Ru|

다른 척도 - 사용자 중심의 척도들(User-oriented measure) 상대 재현율(relative recall) 검색한 연관문헌 수와 사용자가 검색하기를 기대하는 연관문헌 수 사이의 비율 재현 노력도(recall effort) 사용자가 기대하는 수의 연관 문헌을 발견하기 위해 검사해야 하는 문헌 수 사이의 비율

다른 척도 - 예 검색 결과의 요약 사용자가 알고 있는 연관 문헌의 수 : 15 검색된 연관 문헌의 수: 10 검색된 연관 문헌의 수: 10 검색된 연관 문헌 중에 알고 있는 문헌의 수: 4 적용율 : 4 /15 신문헌율 : 6/ 10 (새로운 관련 문헌 수: 6)

참조 컬렉션 - TREC 정보 검색 연구에 대한 비판 객관적인 평가 기준이 없었다. 일관성 있는 테스트베드와 벤치마크가 없다 1990년 초: NIST(National Institute of Standard and Technology), Donna Harman이 학술회의 Text REtrieval Conference (TREC) 창설 TIPSTER/TREC 실험 컬렉션 또는 TREC 컬렉션 제1회 TREC 학술회의: 1992년 11월 NIST에서 개최 구성: 문헌집합, 정보요구(질의), 각 정보요구에 대한 연관문헌 집합 6 CD-ROM : 1GB, tagged with SGML

참조 컬렉션 – TREC-6 종류: WSJ : wall street Journal AP : Associated Press (news) ZIFF : Computer Selects (articles) FR : Federal Register DOE : US DOE Publications (abs) SJMN : San Jose Mercury News PAT : US Patents FT : Financial Times CR Congressional Record FBIS : Foreign Broadcast Information Service LAT : LA Times

TREC – 정보요구

TREC 연관문헌의 선정 방법 풀링 방법(pooling method) 작업 축적 검색(ad-hoc) : 주어진 질의에 대해 검색 시스템으로부터 검색된 문헌 중 상위 K의 문헌을 하나의 풀을 생성한다. 이들 풀에 속한 K개의 문헌을 전문가에 의해서 연관 여부를 결정한다. 가정: 연관문헌의 대부분은 풀에 포함될 것이다. 풀에 포함되지 않은 문헌은 비연관 문헌이다. 작업 축적 검색(ad-hoc) : 변하지 않는 문헌 컬렉션에 대해서 여러 질의를 적용하는 방법 라우팅(routing) : 사용자 요구인 질의는 고정되고 문헌 컬렉션이 변하는 경우이다. 같은 질의가 동적인 문헌 집합을 대상으로 실행되는 여과(filtering) 작업 (예, 뉴스 클립핑 서비스) 순수 여과 작업과는 달리 검색된 문헌은 순위화 실험 정보 요구와 2개의 서로 다른 문헌 컬렉션 제공 (검색 알고리즘의 학습과 튜닝, 튜닝된 알고리즘의 테스트)

TREC-6 - 보조 작업 중국어(Chinese): 문헌과 토픽 모두가 중국어로 된 축적 검색 작업 여과(filtering): 새로 도착한 문헌이 연관문헌인지 아닌지만 결정하는 라우팅 작업이며, 문헌 순위화하지 않고, 테스트 자료는 도착 순서대로 처리 대화(interactive): 탐색자가 문헌의 연관성을 평가하기 위하여 정보 검색 시스템과 대화적으로 작업하며, 문헌은 연관 혹은 비연관 문헌으로 구분(순위화 비제공). 자연언어 처리(natural language): 자연언어 처리에 기반을 둔 검색 알고리즘이 기존의 색인어를 이용한 검색 알고리즘에 비해 장점이 있는지 여부를 검증하기 위한 작업 다국어 축적 검색(cross language): 문헌은 하나의 언어를 사용하나 질의는 여러 가지 다른 언어를 사용

TREC - 보조 작업 높은 정확률(high precision): 정보 검색 시스템 사용자가 주어진 정보 요구(이전에 알려지지 않은)에 대한 응답으로 5분 이내에 10개의 문헌을 검색하도록 하는 작업 구어체 문헌 검색(Spoken document retrieval ): 라디오 방송의 뉴스 쇼를 기록한 문헌을 검색하는 작업이며, 구어체 문헌 검색 기술에 대한 연구를 촉진하기 위한 것임 대용량 코퍼스(Very large corpus): 축적 검색 작업으로 검색 시스템은 20 기가바이트(7500만 문헌) 크기의 컬렉션을 처리해야 함.

TREC – 평가 척도 요약 테이블 통계(summary table statistics): 주어진 작업에 대한 통계값들을 요약한 테이블. 작업에 사용된 토픽(정보 요구) 수, 전체 토픽에 대해 검색된 문헌의 수, 전체 토픽에 대해 효과적으로 검색된 연관 문헌의 수, 전체 토픽에 대해 검색했어야 할 문헌의 수 재현율-정확률 평균(recall-precision averages): 11 표준 재현율 수준에 있어서 평균 정확률을 표시하는 그래프나 표로 구성 문헌 수준 평균(document level averages): 전체 토픽에 대한 평균 정확률이 미리 정의된 문헌 컷오프에서 계산된다. 평균 정확률 히스토그램(average precision histogram): 각 토픽에 대한 단일 수치 척도를 포함하는 그래프.

CACM 컬렉션 3204 문헌으로 구성 부가 정보 52개의 정보요구 저자명 날짜 제목과 요약에서 추출된 키워드 계층적 분류 체계에서 추출된 범주(Computing Review의 범주 체계) 논문 사이의 직접 인용 정보 서지학적 연결(bibliographic coupling) 정보 두 문헌 사이에 상호 인용(co-citation) 빈도 52개의 정보요구 예) 1번 정보요구 What articles exist which deals with TSS(Time Sharing System), an operating system for IBM computers (IBM 컴퓨터 운영체제인 TSS(시분할 시스템)에 대한 논문은 어떤 것이 있는가?) 각 정보 요구에 대해, 두 개의 불리안 질의와 연관 문헌 집합을 포함한다. 각 정보 요구에 대한 연관 문헌의 평균 개수는 15개 정도로 비교적 작다. 정확률과 재현율 성능은 비교적 낮은 경향이 있다.

ISI 컬렉션 ISI(CISI) 의 1460개 문헌 ISI(Institute of Science Information)의 Small[731]에 의해 수집 부가정보 저자 이름 제목과 요약에서 추출된 키워드 각 논문 쌍에 대한 상호 인용 빈도 정보요구 35개의 불리안 질의 41개의 자연어 질의 각 질의에 대한 평균 연관 문헌 수: 약 50개 정확률과 재현율 성능은 비교적 낮은 경향이 있다.

Cystic fibrosis 컬렉션 1239개의 문헌 부가 정보 MEDLINE 병명 번호 저자, 제목, 출처 주요 주제, 보조 주제 요약 참고문헌, 인용 졍보요구: 100 연관 문헌의 수 : 10 ~ 30 연관도 0 : 연관성 없다. 1 : 연관성 중간이다. 2 : 연관성 높다 전문가에 의해서 직접 연관문헌과 연관도을 지정하였다.

한글 정보검색 실험 컬렉션 컬렉션 주 제 문헌수 질의수 한글 정보검색 평가 사이트(http://blue.skhu.ac.kr/~skhuir) 참고 컬렉션 주 제 문헌수 질의수 KTSET93 전산학, 정보학 1,000 30 KTSET95 KTSET93 확장(신문기사) 4,414 50 EKSET 계몽사 백과사전 23,000 46 KRIST 과학기술 연구 보고서 13,515 30 HANTEC 일반,사회과학,과학기술 120,000 50