[NLP] Information Retrieval(1): Evaluation Metrics

- Week 3 Contents -

1. Keyword-based Retrieval

2. Evaluation Metrics ☜

3. Vector-based Retrieval

전반적인 정보 검색(Information Retrieval) Domain에 대한 내용을 다루고 있습니다.

2번의 평가 지표관련 내용을 먼저 정리하고, 1& 3번은 코드와 함께 다음 포스팅에서 같이 정리하려고 합니다.

---

< Evaluation Metrics for Information Retrieval >

정보 검색 도메인에서 평가 지표로 어떤 것들이 쓰이는지 알아보도록 하겠습니다. 

그 전에, 각 상황에 따라 사용 가능한 평가 지표는 다양하며, 정해진 완벽한 정답은 없습니다.

[1] Precision

정밀도(Precision)은 검색된 문서(retrieved documents) 중에서 사용자의 정보 요구와 관련된 유의미한(relevant) 문서의 비율을 나타냅니다.

정보 검색 분야에서 정밀성의 의미와 용례는 통계학과 다른 분야에서의 정확성과 정밀성의 정의와 다르다는 것에 유의해야 합니다.

 

 

[2] Recall

재현율(Recall)은 성공적으로 검색된 쿼리와 관련된 문서의 비율입니다. 

어떤 질의에 응답하여 모든 문서를 반환하여 100% Recall을 달성하는 것은 매우 어려운 일입니다. 따라서 리콜만으로는 충분하지 않지만, 예를 들어 Precision을 같이 계산해서 관련이 없는 문서의 수를 측정해야 합니다.

 

[3] Average Precision

평균 정밀도는 PR-Curve(정밀도-재현율 곡선) 아래의 면적입니다. 정보 검색 모델에서 재현율이 덜 중요한 메트릭인 경우에, 다음 공식을 사용하여 AP를 계산할 수 있습니다. 

Notation의미를 보려면 [더보기]를 누르세요.

RD= 쿼리와 관련된 유의미한(relevant douments)문서의 수,

n = 문서의 총 갯수,

P(k) = k번째 문서에서의 정밀도,

r(k) = k번째 검색된 문서의 관련성(관련성이 없는 경우 0, 있는 경우 1)

 

[4] Mean Average Precision(MAP)

각 쿼리(질의)에 대해 AP를 계산하는 것을 반복하고, 이 query집합에서 평균을 계산한 것이 MAP입니다.

 

[5] Culmulative Gain(CG)

CG(Culmulative Gain)은 검색 결과 목록에 있는 모든 결과의 위치마다의 관련성(relevance)값의 합입니다.

이때 관련성 값(rel)은 예시로 tf-idf값과 같은 scoring을 사용할 수 있습니다. (다음 포스팅에 자세히 나옴)

결과 목록에 있는 결과의 순위(rank)를 고려하지 않는다는 것이 특징입니다. 

찾고자 하는 단어가 특정위치 p에 존재할 때의 다음과 같이 정의됩니다 :

rel_i= i번째 위치에 있는 결과의 rank(등급)별 관련성을 의미

 

[5-1] Discounted Culmulative Gain(DCG)

DCG는 주어진 query에 대한 품질을 순위매긴 척도를 의미합니다. 그래서 ranking results에 일반 CG보다 상대적으로 더 예민하게 반응합니다.

분모 term이 discount factor이고, 분자term만 보면 일반 Culmulative Gain(CG)

 

[5-2] Normalized DCG(NDCG)

NDGC(Normmalized DCG)는 DCG를 ideal DCG(IDCG)로 나누어 정규화된 Culmulative Gain을 계산해줍니다.

Ideal Discounted Culmulative Gain

 

[6] Mean Reciprocal Rank(MRR)

평균 역수 순위는 쿼리 표본에 대한 가능한 응답 목록을 생성하는 모든 프로세스를 평가하기 위한 통계적 측도입니다.

Notation의미를 보려면 [더보기]를 누르세요.

|Q| = # of queries,

rank_i = the rank position of the first relevant document for i-th query

 

[7] Okapi BM25 

BM25는 문서 내 근접성에 관계없이 각 문서에 나타나는 쿼리 용어를 기반으로 문서 집합의 순위를 매기는 단어 묶음 검색 기능으로, 구성 요소와 매개 변수가 조금씩 다른 스코어링 지표함수입니다.

-> 수정 @ 지표함수라기보단, 스코어링 알고리즘이라고 생각하는 것이 맞습니다.

즉, 주어진 쿼리에 대해 문서와의 연관성을 평가하는 랭킹 함수로 사용되는 알고리즘이고,Retrieval분야에서 sparse vector technique(Vector Based Search)로 사용된다. 후에 QA(Quesiton Answering) System 논문에서 많이 언급됨.

 

키워드 q1,..., q_n을 포함하는 쿼리 Q가 주어질 때 문서 D에 대한 BM25 점수는 다음과 같이 구한다.

Notation의미를 보려면 [더보기]를 누르세요.

f = term frequency(TF) -> Key-based Retrieval에서 등장하는 개념입니다. 다음시간에 정리

IDF(qi) = Inverse Document Frequency(다음시간에 정리)

|D| = document length

avgdl = average length

k1 = [1.2, 2.0]

b = 0.75

 

---

References

• https://en.wikipedia.org/wiki/Evaluation_measures_(information_retrieval)
• What is the mean average precision in information retrieval? (educative.io)
• https://en.wikipedia.org/wiki/Discounted_cumulative_gain Mean reciprocal rank - Wikipedia
• Mean reciprocal rank - Wikipedia
• Okapi BM25 - Wikipedia [Python] IR 검색 알고리즘 - BM25 / 엘라스틱서치 랭킹 알고리즘 / 파이썬 rank_bm25 모듈로 문서 검색 구현하기 (tistory.com)