답 후보와 질의단어 간 근접도 분석을 통한 인명 웹 질의응답시스템 답 후보와 질의단어 간 근접도 분석을 통한 인명 웹 질의응답시스템 2003. 7. 15 박 갑 식 한국과학기술원 전산학과

차례 서론 관련 연구 시스템 구성 평가 결론 웹 문서 추출 질의와 무관한 단락 삭제 인명 태깅 근접도 분석 투표 및 정답 목록 출력 평가 결론 / 15

서론 인명 웹 질의응답시스템 연구 동기 웹 문서들을 자료로 인명을 물어보는 질문에 답변하는 시스템 방식 질문을 웹 질의로 변환하여 웹 검색 결과로 나온 앞 순위의 문서들을 분석하여 정답을 추출 연구 동기 인명 웹 질의응답시스템 구현을 통하여 다음 가설을 검증하고자 함 가설 문서에서 정답 주변에 질의 단어가 밀집되어 나타남 특히, 인명 질문에서 근접도 정보가 정답여부를 판단하는 훌륭한 정보임 / 15

웹 질의응답 관련 연구 질의단어 밀집 단락 추출 방식 [Kwok 2001] 문제해결 방안 출현 질의단어 간의 근접도와 중요도(IDF)를 통하여 점수를 계산, 40 단어의 단락 추출 → 질의단어가 적게 나타나면서 정답이 있는 주위 단락이 배제될 수 있음 단락 내에서 답후보의 좌측 또는 우측 질의패턴과의 거리를 계산하여 가까운 것을 정답으로 추출 → 좌측과 우측을 따로 고려함으로써 주변 정보를 충분히 활용 못함 → 각 개별 질의단어와의 거리를 고려하지 못함 문제해결 방안 단락을 추출하여 단락 단위로 답을 찾는 것이 아니라 의미없는 단락만 삭제하고 문서 단위로 분석 답후보와 개별 질의단어들 간의 근접도를 직접 고려 / 15

인명 웹 질의응답시스템의 구조 문서 추출 문서별 정답후보 추출 정답 선정 질문 웹 질의 형태로 변환 웹 검색 투표 및 문서 취합 질의와 관련없는 단락 삭제 웹문서 가져오기 인명 태깅 정답 텍스트 변환 근접도 분석 / 15

문서 추출 질문을 웹질의 형태로 변환 질문에서 매칭이 의미없는 단어 및 물음표 제거 검색 URL 작성 웹문서 가져오기 Who, What is the name of, ? 검색 URL 작성 예. Who invented paper clip? → http://search.yahoo.com/bin/search?p=invented+paper+clip 웹문서 가져오기 웹검색을 실행하여 상위 20개 문서를 가져옴 텍스트 변환 HTML 태그 제거 일부 태그는 공백라인으로 변환하여 단락 분리에 활용 예. <P>, <td>, <option>, <li> 단락 : 공백라인으로 구분되는 문자열 / 15

질의와 무관한 단락 삭제 질의 단어가 적게 출현하는 단락은 삭제하여 문서 재구성 인명 태깅 및 분석 부담 절감 질의단어의 출현횟수를 기준으로 단락 삭제 단락 배제 기준 예) q : 단락 내 출현 질의 단어 수(중복출현은 카운트 않음) Q : 질문의 단어 수(content word) 원 문서 단락 삭제후 문서 질의 단어가 많은 단락 질의 단어가 적은 단락 / 15

인명 태깅 인명인식 방법 휴리스틱 이용 인명 사전 활용 비 고유명사 사전 활용 대소문자 룰 인접 단어를 증거로 활용 긍정적인 증거 : 인명 접두어(Mr.), 인명 미들네임 표기(W.), 접미어 (Jr.), 직위명(President), 인접 인명 단어(James Xxxx) 등 부정적인 증거 : 조직명 성분(Company), 위치 전치사, 정관사 인명 사전 활용 미 Census Bureau 자료(미국인 90% 차지하는 first name, last name : 9만건) 비 고유명사 사전 활용 워드넷 형용사, 부사는 인명후보에서 배제 엠파스 사전의 중,고교 수준 단어 중 인명만 삭제하여 구축 (5,760건) / 15

근접도 분석 (1/2) 문서별로 인명과 질의단어간 근접도 분석 인명과 질의단어들 간의 거리의 합을 계산 동일 질의단어가 중복 출현할 때는 가장 가까운 것과의 거리로 계산 거리의 합이 가장 작은 인명을 그 문서의 정답후보로 선정 근접도 계산식 distk : 문서 내 k번째 인명의 질의 단어 근접도 ak : 문서 내 k번째 인명의 위치 qij : 문서에 출현한 i번째 질의 단어의 j번째 위치 Cnc : 출현하지 않은 질의단어 중 실질어 개수 Cns : 출현하지 않은 질의단어 중 불용어 개수 proximityl : 문서의 대표근접도 / 15

근접도 분석 (2/2) 질문 : 문서 26 2 10 / 15 Who invented paper clip ? paper James invented John clip Richard / 15

정답 선정 (1/2) 투표 및 정답 목록 출력 문서간에 중복되는 정답에 표를 몰아줌 정답 목록 출력 인명 구성 단어 중 한 단어만 일치해도 중복으로 보고, 긴 단어를 대표 인명으로 채택 예. Thomas Edison vs. Edison 점수 산정 방법(근접도순위에 따라 가중치 부여) 정답 목록 출력 점수, 근접도 순으로 정렬 대표인명, 문서별 해당 단락 표시 ri : 동일 대표인명 l 에 속한 i번째 문서의 근접도 기준 순위 / 15

정답 선정 (2/2) 각 문서의 정답후보 근접도순위(x) 21-x 최종 점수 최종 순위 Edison 1 1. Edison 20 57 Edison 2 19 Edison 3 18 Newton 4 17 17 2. Euler Euler 5 16 31 Euler 6 15 3. Newton / 15

평가 TREC-9 질문 중 인명 질문 96개에 대하여 실험 평가 평가 방법 평가 결과 TREC-9 에서 사용된 패턴매칭 스크립트로 역순위평균(Mean Reciprocal Rank) 평가 평가 결과 ranki : i번째 질문에 대한 정답의 순위 n : 질문 갯수 역순위평균 0.624 첫 번째 답이 정답인 질문 53개 (55.2%) 5개 답 중 정답이 없는 질문 26개 (27.1%) / 15

구성요소별 기여도 실험 제안 방식에 변화를 주어서 실험 방법 역순위평균 하락률 제안 방식 0.624 A. 단락 배제 없이 문서전체로 근접도 분석 0.576 7.7% B. 상위 10개의 문서만 활용 0.555 11.1% C. 투표하지 않고 근접도만으로 순위산정 0.549 12.0% D. 키워드간 근접도 활용 단락 추출 방식 (Kwok 계산식 적용) 0.477 23.6% / 15

결론 답 후보(인명)와 질의단어 간 근접도 분석이 효과적임 웹 검색을 통해 나온 중복된 정답의 활용이 효과적임을 확인 질의단어가 밀집한 단락을 먼저 추출하고, 인명 좌우측의 질의패턴 출현을 고려하는 방법과 비교하여 30.8%의 성능 향상을 보임 역순위평균 0.477 -> 0.624 웹 검색을 통해 나온 중복된 정답의 활용이 효과적임을 확인 중복된 답에 대한 투표 적용으로 역순위평균 13.7% 향상 개체명 관련 질의응답에 적용 가능 향후 과제 성능 개선 인명 인식 성능 제고 형태소분석, 파싱 활용 (질문 내 단어의 구문관계 활용) 질문 타입의 확장 한국어 적용 실험 / 15

Who played the teacher in Dead Poet's Society? 참고 1 : 검색 화면의 예 http://gensum.kaist.ac.kr:8020/~kspark/nq.html Who played the teacher in Dead Poet's Society?

참고 2 : 오류 분석 첫번째 답이 정답이 아닌 43개 질문을 분석 유형 개수 예시 오답이라고 할 수 없는 것 8개 첫번째 답이 정답이 아닌 43개 질문을 분석 유형 개수 예시 오답이라고 할 수 없는 것 8개 Who is Secretary-General of the United Nations? - Kofi Annan (현직) vs. Boutros-Ghali (전직; TREC의 정답) Who is the richest person in the world? (Bill Gates가 정답임) 인명 인식 오류 16개 Czolgosz, Canon, Plant, Waters, Leonov (인명인식 실패) Giza, Commons, Cosby Show, Usher, Domino (인명으로 오인식) 의미 이해 필요 11개 Who is the fastest swimmer in the world? Her goal is to be the fastest swimmer in the world. Helen Nezdropa … CNN is owned by whom? Fox News which pulls in a larger audience now than CNN, is owned by Rupert Murdoch … The Twenty First President (21st와 같음을 인식 못함) 자료의 차이 전직 대통령이 정답으로 추출됨 Scrooge 캐릭터에 관한 질문이 애니메이션에 대한 것으로 해석됨 부적절한 웹정보로 오답 Who found Hawaii? -> Who discovered Hawaii? 로 검색하면 됨

키워드 밀집 단락 추출 방식 참고 3 : 웹 질의응답 관련 연구 [Kwok 2001] [Kwok 2001] 질의단어 간의 근접도를 계산, IDF 반영 답후보와 질의단어그룹과의 거리를 분석 좌, 우측을 따로 계산하여 Max 선택 평가 : User effort 를 척도로 도입. 역순위평균 없음 di : (i-1)번째 출현 키워드와 i번째 출현 키워드간의 거리 n : 단락 s 내 키워드 출현 횟수 wi : i번째 키워드의 IDF(10만개 문서에서 계산) 키워드 일반단어 정답후보

키워드 밀집 단락 추출 방식 참고 4 : 웹 질의응답 관련 연구 [Radev 2002] [Radev 2002] 질의단어를 N-gram(N=1,2,3)으로 변환하여 N-gram의 출현빈도를 계산 질의단어가 많이 포함되어 있는 Phrasal chunk, 또는 그에 가까운 Phrasal chunk에 높은 점수를 부여, 이 점수와 그 chunk가 답변타입일 확률을 곱하여 최종 점수 계산 평가 TREC-8 의 질문으로 웹검색 실험 역순위평균 : 0.151

N-gram 직접 추출 방식 [Brill 2001] 평가 참고 5 : 웹 질의응답 관련 연구 [Brill 2001] 검색결과 요약에서 N-gram(N=1,2,3) 추출 질의를 확장한 패턴(query rewrite)과의 매칭을 통한 정답 추출 평가 TREC-9의 500개 질문에 대해 웹 검색 실험 역순위평균 : 0.507

참고 6 : 비교 평가 비교 평가 (Clarke et al. 2001) TREC-9 인명을 정답으로 하는 질문 87개 대상 TREC 100GB VLC2 Corpus 이용(문서건수 : 1,857만건) 정답(인명)만 추출하여 평가 (Moldovan et al. 2003) TREC-8,9,2001 질문 실험 3GB 콜렉션, 50바이트 길이의 단락을 추출하여 평가 Clarke 2001 본 연구 역순위평균 0.463 0.624 상위 5개 답에서 정답이 없는 질문 43.7% (38/87) 27.1% (26/96) 첫 번째 답이 정답인 질문 39.1% (34/87) 55.2% (53/96) Answer type 질문 갯수 역순위평균 Author 13 0.769 Person 225 0.499 Overall 1460 0.469

참고 7 : Kwok 방식에서 놓친 정답의 예 Kwok 방식에서 놓친 정답의 예. 제안방식 답 Kwok방식 답 All three of the Great Pyramids are amazing but only the Great Pyramid of Khufu is considered a wonder. King Khufu of the Fourth Dynasty built the monument so he had a tomb to be buried in. Kwok방식 답 ground provides the illusion that Khafre 's pyramid is taller. After the death of Khafre, his son Menkaure built his smaller pyramid at Giza, eventually completing the last of the famous pyramids at Giza. By Andrew Bayuk 제안방식의 답단락에 대한 Kwok방식 처리 문제점 좌우측을 따로 보는 문제 중복되는 단어 출현 고려 못함, IDF 과대평가

TREC-9, 2001, 2002 인명 질문 실험 평가 평가 방법 평가 결과 타입 A : 정답이 없는 질문(Nil이 정답) 제외하고 평가 타입 B : 정답이 없는 질문 포함하여 평가 평가 결과 TREC-9 TREC 2001 TREC 2002 A B 역순위평균 0.624 0.632 0.576 0.597 0.522 첫 번째 답이 정답인 질문 53 / 96 (55.2%) 24 / 41 (58.5%) 24 / 45 (53.3%) 25 / 49 (51.0%) 25 / 56 (44.6%) 5개 답 중 정답이 없는 질문 26/96 (27.1%) 12 / 41 (29.3%) 16 / 45 (35.6%) 14 / 49 (28.6%) 21 / 56 (37.5%)