3장 검색 평가 3.1 소개 3.2 검색 성능 평가 3.3 참조 컬렉션 3.4 연구 동향 및 쟁점 3.5 참고 문헌 고찰

Presentation on theme: "3장 검색 평가 3.1 소개 3.2 검색 성능 평가 3.3 참조 컬렉션 3.4 연구 동향 및 쟁점 3.5 참고 문헌 고찰"— Presentation transcript:

1 3장 검색 평가 3.1 소개 3.2 검색 성능 평가 3.3 참조 컬렉션 3.4 연구 동향 및 쟁점 3.5 참고 문헌 고찰
최신정보검색론 Chapter3

2 3.1 소개 정보검색 시스템 평가 - 기능 평가 - 성능 평가 - 효율(efficiency): 처리 시간과 공간 복잡도
3.1 소개 정보검색 시스템 평가 - 기능 평가 - 성능 평가 - 효율(efficiency): 처리 시간과 공간 복잡도 - 효과(effectiveness): 검색 성능 평가 질의 결과의 정확성 평가 실험 참조 컬렉션과 평가 척도 사용 정보검색 성능 평가 - 실험 참조 컬렉션: 문헌 집합, 정보 요구 예제, 연관 문헌 집합 - 평가 척도: 검색된 문헌 집합과 제공된 연관 문헌 집합과의 유사도 최신정보검색론 Chapter3

3 3.2 검색 성능 평가 검색 작업에 따른 평가 - 사용자의 노력 - 응답 집합의 질 대화형 작업 (대화세션, 10장 참조)
- 인터페이스 특성 - 시스템 제공 안내 - 세션의 길이 일괄처리 작업 - 응답 집합의 질 - 검색 성능 평가의 주류 - 실험실 수준의 평가 - 반복과 확장 가능성 최신정보검색론 Chapter3

4 3.2.1 재현율과 정확률 재현율 정확률 연관 문헌 집합(R) 중 검색된 문헌의 비율
재현율과 정확률 Ra 재현율 연관 문헌 집합(R) 중 검색된 문헌의 비율 정확률 검색된 문헌 집합(A) 중 연관 문헌의 비율 R A 최신정보검색론 Chapter3

5 재현율- 정확률 곡선 (Recall-Precision Graph)
재현율-정확률 곡선 재현율- 정확률 곡선 (Recall-Precision Graph) - 정보 검색 평가의 표준 - 간단하면서 직관적 - 한 개의 곡선으로 표현 최신정보검색론 Chapter3

6 는 질의 수 예) Rq={d3, d5, d9, d25, d39, d44, d56, d71, d389, d123}
각 재현율 수준에 있어서 정확률 평균 는 질의 수 은 재현율 수준 에서 번째 질의의 정확률 최신정보검색론 Chapter3

7 : 번째 표준 재현율 수준 (즉, r5는 재현율 수준 50%)
11 표준 재현율 수준에서의 정확률 예) Rq={d3, d56, d129} d56 :재현율 33.3%(정확률 33.3%) d129 : 재현율 66.6%(정확률 25%) d3 : 재현율 100%(정확률 20%) 11 표준 재현율 수준에서의 정확률 보간 : 번째 표준 재현율 수준 (즉, r5는 재현율 수준 50%) 재현율 수준 0%, 10%, 20%, 30%에서 보간된 정확률은 33.3%(재현율 수준 33.3%에서의 정확률) 재현율 수준 40%, 50%, 60%에서 보간된 정확률은 25%(재현율 수준 66.6%에서의 정확률) 재현율 수준 70%, 80%, 90%, 100%에서 보간된 정확률은 20%(재현율 수준 100%에서의 정확률) 최신정보검색론 Chapter3

8 문헌 컷오프(cutoff)에 따른 평균 정확률
5, 10, 15, 20, 30, 50, 100 문헌 검색시 평균 정확률 순위화 검색 성능에 대한 추가적인 정보 제공 최신정보검색론 Chapter3

9 단일 요약 수치 재현율에 따른 평균 정확률 도표의 단점
여러 질의에 대한 정확률 평균 : 검색 알고리즘의 중요한 결점이 숨겨질 수 있다 각각의 질의에 대한 성능 검사 필요 검색된 연관 문헌에서의 평균 정확률 (AP: Average Precision) 그림 3.2의 예: 검색된 연관 문헌에서의 평균 정확률= ( )/5 = 0.57 연관 문헌을 빨리 검색하는(즉, 상위 순위로 검색하는) 시스템 선호 R-정확률 R 번째 검색 순위에서 정확률 R 은 현재 질의에 대한 전체 연관 문헌 수(집합 Rq 의 문헌 수) 예) 그림 R- 정확률은 0.4( R =10, 순위 10위까지 연관 문헌은 4개) 최신정보검색론 Chapter3

10 정확률 히스토그램 여러 개 질의에 대한 R-정확률 척도로 검색 이력 비교 0 : 두 알고리즘이 동일한 성능
와 를 각각 i번째 질의에 대한 검색 알고리즘 A, B의 R-정확률 0 : 두 알고리즘이 동일한 성능 양수 : A 알고리즘이 더 좋은 성능 [그림 3.5] 10개의 가상 질의에 대한 정확률 히스토그램 최신정보검색론 Chapter3

11 요약 테이블 통계치 정확률과 재현율의 적합성 단일 수치 척도들을 테이블 형태로 작성 예) 검색 작업에 사용된 질의 수
예) 검색 작업에 사용된 질의 수 전체 질의에 의해 검색된 문헌 수 모든 질의를 고려할 때 검색된 연관 문헌의 수 전체 질의에 의해 검색될 수 있는 연관 문헌의 수 정확률과 재현율의 적합성 최대 재현율 : 컬렉션 문헌 전체에 대한 지식 필요 (대규모 컬렉션의 경우 불가능) 2) 재현율과 정확률을 결합한 단일 척도 사용이 더 바람직 3) 대화성 검색 프로세스의 정보력(informativeness) 계산 척도가 더 적당 4) 약한 순서화(weak ordering)를 제공하는 시스템에서는 부적당 최신정보검색론 Chapter3

12 3.2.2 다른 척도들 조화 평균 는 번째 순위 문헌에서의 재현율, 는 정확률 는 와 의 조화 평균, [0,1] 사이의 값
다른 척도들 조화 평균 는 번째 순위 문헌에서의 재현율, 는 정확률 는 와 의 조화 평균, [0,1] 사이의 값 - 연관 문헌이 하나도 검색되지 않았을 경우: 0 검색된 문헌이 모두 연관 문헌일 경우 1 - 재현율과 정확률이 모두 높아야 값이 커짐 최신정보검색론 Chapter3

13 E 척도 - van Rijsbergen[785] 이 제안
- 사용자가 재현율에 더 관심이 있는지 정확률에 더 관심이 있는지를 명시 는 번째 순위 문헌에서의 재현율, 는 정확률, 는 와 에 대한 척도 b는 재현율과 정확률에 대한 상대적 중요도 이면 척도는 조화평균 의 보수 b 가 1보다 크면 사용자가 재현율보다 정확률에 더 관심이 있음 b 가 1보다 작으면 사용자가 정활률보다는 재현율에 더 관심이 있음 최신정보검색론 Chapter3

14 사용자 중심의 척도들 커버율(coverage) 사용자에게 미리 알려진 연관 문헌 중 실제로 검색된 연관 문헌의 비율
신문헌율(novelty) 검색된 연관 문헌 중에서 사용자에게 미리 알려지지 않은 문헌의 비율 높은 커버율 : 검색 시스템이 사용자가 기대하는 대부분의 연관 문헌을 검색 높은 신문헌율 : 사용자에게 미리 알려지지 않은 새로운 연관 문헌을 많이 검색 |A| |R| |U| |Rk | |Ru| 최신정보검색론 Chapter3

15 - 시스템이 검색한 연관 문헌 수와 사용자가 검색하기를 기대하는 연관문헌 수 사이의 비율
상대 재현율 - 시스템이 검색한 연관 문헌 수와 사용자가 검색하기를 기대하는 연관문헌 수 사이의 비율 - 사용자가 기대하는 수만큼의 연관 문헌을 발견 : 검색 중지, 상대 재현율은 1 재현율 노력도 - 사용자가 기대하는 수의 연관 문헌을 발견하기 위해 검사해야 하는 문헌 수 사이의 비율 다른 척도들 - 약한 순위화 문헌 집합을 다룰 때 편리한 예상 탐색 길이 - 연관 문헌만을 고려하는 만족도(satisfaction) - 비연관 문헌만을 고려하는 실패도(frustration) 최신정보검색론 Chapter3

16 3.3 참조 컬렉션 3.3.1 TREC 컬렉션 정보 검색 연구에 대한 비판 1) 기반으로서의 확고한 형식적 프레임워크가 없다
주관적 평가인 연관성에 의존 2) 강력하고 일관성 있는 테스트베드와 벤치마크가 없다 - 1990년대 초 : NIST(National Institute of Standard and Technology)의 Donna Harman이 연차 학술회의 Text REtrieval Conference (TREC) 창설 - TIPSTER/TREC 실험 컬렉션 또는 TREC 컬렉션 - 제 1 회 TREC 학술회의: 1992년 11월 NIST에서 개최 - 구성 문헌집합, 정보 요구 예제(TREC에서는 토픽), 각 정보 요구 예제에 대한 연관 문헌 집합 최신정보검색론 Chapter3

17 문헌 컬렉션 표 3.1 TREC-6 에 사용된 문헌 컬렉션. 불용어를 제거하지 않았으며, 스테밍도 하지 않았음 최신정보검색론
Chapter3

18 TREC 컬렉션 : 압축된 텍스트 형태로, 약 1기가바이트 CD-ROM 디스크 6장으로 배포
- 출처 WSJ → Wall Street Journal AP → Associated Press(news wire) ZIFF → Computer Selects(기사들), Ziff-Davis FR → Federal Register, DOE → US DOE Publications(요약) SJMN → San Jose Mercury News PAT → US Patents, FT → Financial Times CR → Congressional Records FBIS → Foreign Broadcast Information Service LAT → LA Times 최신정보검색론 Chapter3

19 문헌 번호(<DOCNO>), 문헌 텍스트를 위한 필드(<TEXT>)
- 컬렉션 문헌 : SGML로 태깅 문헌 번호(<DOCNO>), 문헌 텍스트를 위한 필드(<TEXT>) TREC 문헌의 한 예) Wall Street Journal 하위 컬렉션 중 문헌 번호 인 문헌 <doc> <docno> WSJ </docno> <hl> AT&T Unveils Services to Upgrade Phone Networks UnderGlobal Plan </hl> <author> Janet Guyon (WSJ Staff) </author> <dateline> New York </dateline> <text> American Telephone & Telegraph Co. introduced the first of a new generation of phone services with broad ... </text> </doc> 그림 3.7 WSJ TREC 문헌 최신정보검색론 Chapter3

20 정보 요구 예제(토픽) (자연언어로 기술) 예) 토픽 번호 168(TREC 3 학술회의)
새로운 순위화 알고리즘을 실험하기 위한 정보 요구 예제 집합을 포함 (자연언어로 기술) 예) 토픽 번호 168(TREC 3 학술회의) <top> <num> Number: 168 <title> Topic: financing AMTRAK <desc> Description: A document will address the role of the Federal Government in financing the operation of the National Railroad Transportation Cor- poration(AMTRAK). <narr> Narrative: A relevant document must provide information on the government's responsibility to make AMTRAK an economically viable entity. It could also discuss the privatization of AMTRAK as an alternative to continuing government subsidies. Documents com- paring government subsidies given to air and bus transportation with those provided to AMTRAK would also be relevant. </top> - 6회까지의 TREC 학술회의가 준비한 토픽 수는 350개 최신정보검색론 Chapter3

21 각 정보 요구 예제(토픽)에 대해 연관 가능성이 있는 문헌 집합 풀(pool)로 부터 선택
정보 요구 예제에 대한 적합 문헌 폴링 방법(Polling method) 각 정보 요구 예제(토픽)에 대해 연관 가능성이 있는 문헌 집합 풀(pool)로 부터 선택 1) 풀은 참여 시스템들이 생성한 순위화에서 (보통 =100)개의 상위 순위 문헌을 선택 2)풀의 문헌은 전문가에게 제시되고 그 전문가가 문헌의 연관성을 최종 결정 가정 1) 연관 문헌 대부분이 수집된 풀에 나타난다. 2) 풀에 나타나지 않는 문헌은 비연관 문헌이라고 간주할 수 있다. 최신정보검색론 Chapter3

22 1) 축적 검색(ad-hoc) : 여러 새로운 질의가 정적인 문헌 데이터베이스를 대상으로 수행
TREC 학술회의의(벤치마크) 작업 1) 축적 검색(ad-hoc) : 여러 새로운 질의가 정적인 문헌 데이터베이스를 대상으로 수행 2) 라우팅(routing) : 고정된 요구가 계속적으로 변하는 문헌 데이터베이스를 대상으로 수행 - 같은 질의가 동적인 문헌 집합을 대상으로 실행되는 여과(filtering) 작업 (예, 뉴스 클립핑 서비스) - 순수 여과 작업과는 달리 검색된 문헌은 순위화 - 실험 정보 요구와 2개의 서로 다른 문헌 컬렉션 제공 (검색 알고리즘의 학습과 튜닝, 튜닝된 알고리즘의 테스트) 최신정보검색론 Chapter3

23 중국어: 문헌과 토픽 모두가 중국어로 된 축적 검색 작업
TREC6에 8가지 보조 작업이 추가 중국어: 문헌과 토픽 모두가 중국어로 된 축적 검색 작업 여과: 새로 도착한 문헌이 연관 문헌인지 아닌지만 결정하는 라우팅 작업, 문헌 순위화는 필요 없고, 테스트 자료는 도착 순서(time-stamp)대로 처리 대화: 탐색자가 문헌의 연관성을 평가하기 위하여 정보 검색 시스템과 대화적으로 작업하며, 문헌은 연관 혹은 비연관 문헌으로 구분(순위화 비제공). 자연언어 처리: 자연언어 처리에 기반을 둔 검색 알고리즘이 기존의 색인어를 이용한 검색 알고리즘에 비해 장점이 있는지 여부를 검증하기 위한 작업 축적 검색: 문헌은 하나의 언어를 사용하나 질의는 여러 가지 다른 언어를 사용 높은 정확률: 정보 검색 시스템 사용자가 주어진 정보 요구(이전에 알려지지 않은)에 대한 응답으로 5분 이내에 10개의 문헌을 검색하도록 하는 작업 구어체 문헌 검색: 라디오 방송의 뉴스 쇼를 기록한 문헌을 검색하는 작업이며, 구어체 문헌 검색 기술에 대한 연구를 촉진하기 위한 것임 대용량 코퍼스: 축적 검색 작업으로 검색 시스템은 20 기가바이트(7500만 문헌) 크기의 컬렉션을 처리 해야 함. 최신정보검색론 Chapter3

24 요약 테이블 통계: 주어진 작업에 대한 통계값들을 요약한 테이블. 작업에
TREC 학술회의에서의 평가 척도 요약 테이블 통계: 주어진 작업에 대한 통계값들을 요약한 테이블. 작업에 사용된 토픽(정보 요구) 수, 전체 토픽에 대해 검색된 문헌의 수, 전체 토픽 에 대해 효과적으로 검색된 연관 문헌의 수, 전체 토픽에 대해 검색했어야 할 문헌의 수. 재현율-정확률 평균: 11 표준 재현율 수준에 있어서(전체 토픽에 대한) 평균 정확률을 표시하는 그래프나 표로 구성. 표준 재현율 수준에서의 정확률을 계 산하기 위해 보간법 사용. 또한 각 연관 문헌(전체 질의)에 대한 보간되지 않은 평균 정확률이 포함되기도 한다. 문헌 수준 평균: 전체 토픽에 대한 평균 정확률이 미리 정의된 문헌 컷오프에 서 계산된다. 예를 들면 평균 정확률을 5,10,20,100번째 연관 문헌에서 계산 하는 것이다. 또한 (전체 질의에 대한) 평균 R-정확률이 포함될 수도 있다. 평균 정확률 히스토그램: 각 토픽에 대한 단일 수치 척도를 포함하는 그래프. (어떤 토픽 에 대한) 대상 검색 알고리즘의(토픽 에 대한) R-정확률 값과 모든 참가 시스템의 결과를 평균한 (토픽 에 대한) 평균 R-정확률 사이의 차이 값 최신정보검색론 Chapter3

25 3.3.2 CACM 과 ISI 컬렉션 소형 테스트 컬렉션 CACM 컬렉션
- ’Communication of the ACM’ 1958년부터 1979년 까지 출간된 3204개의 논문 전부 구조적 하위 필드 포함 저자이름, 날짜 정보 제목과 요약에 추출된 단어 스템(stem) 계층적 분류 체계에서 추출된 법주(Computing Review의 범주 체계):5개 이하 논문 사이의 직접 인용 정보: [ , ] 를 직접 인용하는 문헌 에 대한 정보 서지학적 연결(bibliographic coupling) 정보: [ , , ] 과 가 동시에 어떤 문헌 를 직접 인용하고 있고, 또한 동시 인용하는 횟수가 두 문헌 사이에 상호 인용(co-citation) 빈도 : [ , , ] 가 동시에 어떤 문헌 에 의해 인용되고 있으며 그 동시 인용하는 횟수가 최신정보검색론 Chapter3

26 What articles exist which deals with TSS(Time Sharing System)
- 52개의 정보 요구 예제 예) 1번 정보 요구 What articles exist which deals with TSS(Time Sharing System) an operating system for IBM computers ? (IBM 컴퓨터 운영체제인 TSS(시분활 시스템)에 대한 논문은 어떤 것이 있는가?) 각 정보 요구에 대해, 두 개의 불리안 질의와 연관 문헌 집합을 포함 각 정보 요구에 대한 연관 문헌의 평균 개수는 15개 정도로 비교적 작다 - 따라서 정확률과 재현율 성능은 비교적 낮은 경향이 있다. 최신정보검색론 Chapter3

27 ISI 컬렉션 ISI(CISI) 의 1460개 문헌 ISI(Institute of Science Information)의 Small[731]에 의해 수집 저자이름 제목과 요약에서 추출된 단어 스템 각 논문 쌍에 대한 상호 인용 빈도 - 35개의 정보 요구(자연언어로 기술됨) : 불리안 질의 제공 - 불리안 질의가 없는 (즉, 자연언어 형태만 있는) 41개의 실험용 요구도 포함 - 각 질의에 대한 평균 연관 문헌 수 : 약 50개 - 정확률과 재현율 성능은 비교적 낮은 경향이 있다. 최신정보검색론 Chapter3

28 CACM과 ISI 컬렉션에 대한 통계 표 3.2 CACM과 ISI 컬렉션의 문헌 통계
최신정보검색론 Chapter3

29 관련 실험 컬렉션들 Virgina Polytechic Institute 와 state University
Fox가 아홉개의 소형 컬렉션을 한 개의 CD-Rom 에 수록 표 3.4 CACM,ISI 컬렉션과 연관된 실험 컬렉션들 최신정보검색론 Chapter3

30 한글 정보검색 실험 컬렉션 (http://blue.skhu.ac.kr/~skhuir)참고 한글 정보검색 평가 사이트
최신정보검색론 Chapter3

31 3.4 연구 동향 및 쟁점 대화형 사용자 인터페이스에 대한 연구 - 동기: 사용자로부터 적절한 피드백을 얻는 것이 검색
성능 개선에 매우 중요 - 1992년에 제안된 ‘정보력 (informativeness) 척도[754] 예 새로운 척도에 대한 제안, 연구 및 특성 규명 - 새로운 척도에 대한 제안, 연구 및 특성 규명 최신정보검색론 Chapter3

32 3.5 참고 문헌 고찰 Salton과 MaGill[698]: 검색 성능 평가에 대한 훌륭한 내용을 포함
Khorfage[451]: 검색 평가에 한 장 전체를 할애 Mizzaro[569]: 연관성에 관해 매우 철저한 조사를 제공 (약 160개의 논문을 언급) Shaw, Burgin, Howel[422, 423]:벡터, 클러스터 검색용 실험 컬렉션에 대한 표준과 평가 Raghavan, Bollmann, Jung[664, 663]: 약한 순서화를 제공하는 시스템에 대한 Tague-Sutcliffe[754]: 대화적 사용자 세션을 평가하기 위한 정보력’척도 제안 TREC 컬렉션: Harman[342]과 Vorhees와 Harman[794] CACM과 ISI 컬렉션: Fox[272] 교차 인용 패턴에 기반한 검색 알고리즘[94, 435, 694, 730, 732, 809] Cystic Fibrosis(CF) 컬렉션: Shaw, Wood, Wood, Tibbo[721] 최신정보검색론 Chapter3