3.1. 검색 성능 평가
색인 / 검색 모델을 평가하는 방법은 크게 두 가지를 판단합니다.
하나는 “만족도”(Effectiveness) : 정보들을 잘 분별하였는가? 이고,
나머지 하나는 “효율성”(Efficiency) : 색인과 검색의 시간, 공간 비용이 적절한가? 입니다.
“검색 성능 평가 지표”(Contingency table) 는 검색 여부와 관계 여부 두 가지만을 고려하여
총 4가지로 분류하여 평가하는 지표입니다.
관계가 있으면서 검색된 것을 \(TP\)(True Positives) ,
관계가 없으면서 검색된 것을 \(FP\)(False Positives) ,
관계가 있으면서 검색되지 않은 것을 \(TN\)(True Negatives) ,
관계가 없으면서 검색되지 않은 것을 \(FN\)(False Negatives) 라고 표현합니다.
| Relevant | Not Relevant | |
| Retrieval | \(TP\) | \(FP\) |
| Not Retrieval | \(TN\) | \(FN\) |
“정밀도”(Precision) 는 \(\frac{TP} { TP + FP }\) , “재현율”(Recall) 은 \(\frac{TP} { TP + TN }\) ,
“정확도”\(\frac{TP + FN} { TP + FP + FN + TN }\) 의 평가 방법이 존재합니다.
여기서 정확도가 가장 “정확”해서 자주 사용 할 것 같지만,
극단적인 분류 상황에 대해서는 효과가 없어 사용되지 않습니다.
( 쉬운 예로 \(FN\)이 매우 큰 모델이라고 할 때, \(TP\)를 하나도 못 맞춰도 대부분의 \(FN\)을 맞추기만 하면
높은 정확도가 나오게 됩니다. )
정밀도 100%는 관계가 있는 확실한 몇 개만 검색으로 나오면 되고,
재현율 100%는 관계여부에 상관없이 모두 검색 되게 하면 되기 때문에,
결국, 정밀도와 재현율 둘 다 고려해서 성능 평가가 이루어져야 합니다.
“\(F\)지표”(F measure)는 정밀도 \(P\) 와 재현율 \(R\)을 조화 평균형태에 가중치를 부여 한 것입니다.
\(F = \frac{1} { \frac{c} {P} + \frac{(1 – c)} {R} } = \frac{(C + 1)PR} {C(P + R)} : ( C = \frac{1 – c} {c} )\)여기서 \(c > \frac{1}{2}\) 이면, \(R\)(재현율)에 더 강조한 모델이고, \(c < \frac{1}{2}\) 이면, \(P\)(정밀도)에 더 강조한 모델입니다.
만약, \(c = \frac{1}{2}\) 이면, \(F = \frac{2PR} {P + R}\) 이고, 이를 “\(F1\)지표”(F1 measure)라고 표현합니다.
\(F1\) 지표는 좋은 성능의 평가지표 이지만, “순위화된 형태”(Ranked Retrieval)로 문서를 찾아야 한다면,
\(F1\) 같은 형태의 평가지표는 의미가 없을 수도 있습니다. ( 우선순위는 고려되지 않기 때문입니다. )
3.2. 순위를 고려한 검색 성능 평가(1)
그렇다면. 순위화 된 형태의 검색문서를 찾을 때는 어떤 평가방식이 적합 할까요?
기존의 F지표를 사용한 “PRC”(Precision-Recall Curve) 그래프는 순위에 관계없이 모든 점을 그리기 위해
재현율 -> 정밀도 순이나 정밀도 -> 재현율 순으로 그려야 하는데,
이 때, 그래프가 우하향 , 미분 불가능 하면서 뾰족한 부분들이 생기면서 그려지게 되는데
(이를 톱니모양(sawtooth) 그래프라고 표현합니다.) 해당 그래프는 분석하기가 난감해집니다.
이를 보완하기 위해 “보간 정밀도”(Interpolated Precision)를 사용하며, 정의는 다음과 같습니다.
Precision_Interpolated( \(r_k\) ) = \(r_t ≥ r_k\) ? Precision( \(r_t\) ) : Precision( \(r_k\) ) : ( \(m > t > k\) )
( 현재 지점 이후의 값들 중에 재현률이 보다 큰 것이 있으면, 현재 지점이 톱니 지점이므로,
보다 큰 지점 중에서 가장 큰 값의 정밀도로 해당 지점의 정밀도를 조절합니다. )
그 결과, 여전히 미분 불가능 하지만, 계단식의 그래프가 그려지게 됩니다.
조금 더 단순화 하기 위해 for( \(R\) = 0.0 ; \(R\) ≤ 1.0 ; \(R\)+= 0.1 ) : ( 0.0 부터 1.0 까지 0.1 단위로 “총 11개” ) 의 재현율 구간을 나누고
각 구간에서의 보간 정밀도를 구한 다음, 같은 재현율이면서 다른 질의들의 보간 정밀도 평균을 사용하는 그래프인
“Averaged 11-point Precision/Recall” 그래프 방식도 있습니다.
3.3. 순위를 고려한 검색 성능 평가(2)
“평균정밀도”(mean Average Precision 또는 mAP)의 정의는 다음과 같습니다.
\(mAP( Q ) = \frac{1}{|Q|}\sum_{i=1}^{Q}{AP( i )} \) 라고 정의 할 수 있습니다.
AP 는 “Average Precision” 로 정의는 다음과 같습니다.
\(AP( k ) = \frac{1}{|k|}\sum_{i=1}^{k}{Precision( i )} \) 라고 정의 할 수 있습니다.
식으로 보면 복잡하지만, AP는 Curve 그래프의 아래 넓이 혹은,
\(Precision( x )\) 의 \([\) 처음 정의 구간 \(1\) \(\ldots\) 끝 정의 구간 \( k\) \(]\)까지 정적분 값이 AP가 됩니다.
또한, \(mAP\)는 \(AP\)의 정의된 구간 전체 평균이 됩니다.
그래서 보간정밀도나 Averaged 11-point를 사용한다면, 조금 더 수월하게 구할 수 있어 많이 사용됩니다.
실제로 사용할 때를 중점으로 평가하는 방법도 존재합니다.
“상위 문서 정밀도”(Precision at K 또는 Pre@K)은 상위 K개의 문서 중에서
실제 적합문서의 개수의 비율로 평가하는 방법입니다.
(즉, 상위 K 번째 까지의 정밀도를 유의미하게 보고 나머지를 무시하는 방법입니다. )
실제로 웹서핑 할 때, 보통 10개에서 20개 이하로만 검색 내용을 찾아보기 때문에 유의미한 방법일 수도 있습니다.
얻는 이점으로는 고정된 소량(K개)의 문서만을 검사 해도 되지만, 그렇기에 평가지표들 중에서는 가장 불안정 합니다.
“R-precision”은 모든 실제 적합문서 수를 R이라고 할 때,
상위 R개의 문서 중에서의 실제 적합 문서의 개수의 비율로 평가하는 방법입니다.
결국, 값은 Pre@R와 같아서 위와 동일한 개념이라 생각하기 쉽지만,
상위 문서 정밀도는 상위 K개 문서 중( \(TP + FP\) ) 실제 적합문서( \(TP\) ) 비율(“정밀도”의 정의)이고,
R-precision은 모든 실제 적합문서( \(TP + TN\) ) 수 \(R\)이 있을 때,
상위 R개 중에서의 실제 적합 문서( \(TP\) ) 비율(“재현율”의 정의)로 의미가 다릅니다.
그렇다면, R-precision은 “정밀도의 정의”(Precision at K)로 재현율을 정의했기 때문에,
“정밀도인 동시에 재현율”이라 표현하고 이를 “break-even point 지점”이라고도 표현합니다.
다중 적합도가 부여되는 상황에서는 “NDCG”(Normalized Discounted Cumulative Gain)을 사용합니다.
“NDCG”는 이진 적합( 예: 적합하면 1, 아니면 0 ) 또는 다중 적합( 예: 적합도에 따라 0부터 3까지 차등한 적합 점수 )
평가에 사용됩니다. NDCG의 정의는 다음과 같습니다.
“CG”(Cumulative Gain)은 “사용자 만족도”라고 표현하며,
순위에 관계없이 상위 K개의 검색문서의 다중 적합도를 더한 값입니다.
즉, CG@K = \(\sum_{i=1}^{K} { RS_i }\) : ( \(RS_i\) 은 \(i\)번 째 검색문서의 Relevance Score(적합 점수) 입니다. )
“DCG”(Discounted Cumulative Gain)은 “차감누적 사용자 만족도”라고 표현하며,
DCG@K = \(\sum_{i=1}^{K} { \frac{ 2^{RS_i} – 1 } {\log_2{ (1 + i) } } }\) 로 정의됩니다.
“NDCG”(Normalized Discounted Cumulative Gain)은 “정규 차감누적 사용자 만족도”라고 표현하며,
NDCG@K = \(\frac{DCG@K} {IDCG@K}\) ( \(IDCG\)는 \(RS\)가 모두 이상적(Ideal)으로 점수를 받았다는 전제의 점수입니다.
즉, 가능한 모든 검색 결과의 DCG들 중에서 최대 DCG 값을 의미합니다. )
점보검색 성능 평가용 표준 프로그램을 “trec_eval” 이라고 표현합니다.
검색 성능 평가를 위한 테스트 데이터 셋의 구성 요소로는
1). “문서 집합” ( a document collection )
2). “질의 집합” ( a set of queries )
3). “질의-문서 간 적합성 판단 자료” (relevance judgements)
가 존재해야 합니다.
대표적인 테스트 컬렉션(데이터 셋)으로
1). 한국어로는 KTSET , HANTEC 2.0 이 있습니다.
2). 영어로는 The Cranfield collection , CACM collection , AP collection , GOV2 collection 이 있습니다.