할인누적차익

할인 누적 이득(DCG)은 순위 품질의 척도다.정보 검색에서는 웹 검색 엔진 알고리즘이나 관련 응용 프로그램의 효과를 측정하는 데 자주 사용된다.검색 엔진 결과 집합에 있는 문서의 단계별 관련성 척도를 사용하여 DCG는 결과 목록에서 문서의 위치를 기준으로 문서의 유용성 또는 이득을 측정한다.이득은 결과 목록의 맨 위에서 맨 아래로 누적되며, 각 결과의 이득은 하위 등급에서 할인된다.^[1]

개요

DCG와 관련 조치를 사용할 때 두 가지 가정을 한다.

1. 관련성이 높은 문서는 검색 엔진 결과 목록에 더 일찍 나타날 때 더 유용하다(등급이 높음)
2. 관련성이 높은 문서는 관련성이 적은 문서보다 유용하며, 관련성이 없는 문서보다 유용하다.

DCG는 누적 이득이라 불리는 더 초기, 더 원시적인 측정에서 비롯된다.

누적 이득

누적 이득(CG)은 검색 결과 목록에 있는 모든 결과의 등급화된 관련성 값의 합이다.DCG의 이 전임자는 결과의 순위(위치)를 결과 집합의 유용성에 대한 고려에 포함시키지 않는다.특정 순위 위치 $p{\displaystyle }$ ${\displaystyle p}$의 CG는 다음과 같이 정의된다$$.

${\displaystyle \mathrm{CG_{p}} =\sum _{i=1}^{p}rel_{i}}}}}$

여기서 $r{\displaystyle }$ ${\displaystyle e}$ l ${\displaystyle i_{}}$ ${\$은(는) 위치 $i{\displaystyle }$ ${\displaystyle$ i$}$에서 결과의 등급 관련성이다$.$

CG 함수로 계산된 값은 검색 결과 순서의 변경에 영향을 받지 않는다.즉,관련성이 높은 문서 나는상위 순위{\displaystyle d_{나는}(를)d,하위관련 문서 dj{\displaystyle d_{j}위로 이동해도 CG에값은 변경되지 않는다(나는, j, j, j,displaystyle i,j\leq p})계산 대한.검색 결과의 유용성에 대해 위에서 제시한 두 가지 가정을 바탕으로, (N)DCG는 보통 CG보다 선호된다.

누적 이득은 등급 척도가 이항인 경우 정밀도 측정기준과 동일하기 때문에 그라데이드 정밀도라고도 한다.

할인 누적 이득

DCG의 전제는 검색 결과 목록에서 낮은 것으로 보이는 관련성이 높은 문서는 등급화된 관련성이 결과의 위치에 비례하여 로그적으로 감소함에 따라 불이익을 받아야 한다는 것이다.

특정 순위 위치 $p{\displaystyle }$ ${\displaystyle p}$에서 누적된 DCG의 전통적인 공식은 다음과 같이 정의된다$$.^[1]

${\displaystyle \mathrm{DCG_{p}} =\sum _{i=1}{p}{frac {rel_{i+1}}{2}(i+1)}=rel_{1}+}sum _{i=2}^{p}{frac_{{i+1}}}}}}}}}}}}}}}}}}}.$

이전에는 로그 감소 계수를^[2] 사용하는 것이 원활한 감소를 산출한다는 사실 이외에는 이론적으로 타당한 이유가 없었다.그러나 Wang 외 연구진(2013년)^[3]은 NDCG(Normalized DCG)에서 로그 감소계수를 사용하는 이론적 보증을 제공했다.저자들은 실질적으로 다른 순위 함수의 모든 쌍에 대해 NDCG가 일관된 방식으로 어떤 것이 더 나은지 결정할 수 있다는 것을 보여준다.

DCG의^[4] 대체 공식은 관련 문서 검색에 더욱 중점을 둔다.

${\displaystyle \mathrm {DCG_{p} =\sum _{i=1}^{p}{\frac {2^{rel_{i}-1}{\log _{2}(i+1)}}}}$

후자의 공식은 주요 웹 검색 업체와^[5] 카글과 같은 데이터 과학 경쟁 플랫폼을 포함한 산업에서 흔히 사용된다.^[6]

DCG의 이 두 공식은 문서의 관련성 값이 2진수일 때 같다;^{[2]: 320} $r{\displaystyle }$ ${\displaystyle e}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$∈${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1}$} ${\displaystyle rel_{i}\in \{0,1$

주의할 점은 크로프트 외 연구진(2010)과 버지 외 연구진이다.(2005) 위의 두 가지 버전의 DCG는 모두 베이스 2의 로그를 사용하는 반면, 두 번째 DCG는 베이스 e의 로그로 표시한다.DCG의 첫 번째 제형으로 NDCG를 계산할 때, 로그의 베이스는 중요하지 않지만, 로그의 베이스는 두 번째 제형의 NDCG 값에 영향을 미친다.분명히, 로그의 베이스는 두 공식의 DCG 값에 영향을 미친다.

정규화된 DCG

이 섹션은 검증을 위해 추가 인용구가 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 비소싱 소재에 도전하여 제거할 수 있음(2020년 2월) (이 템플릿 메시지 제거 방법 및 시기 학습)

검색 결과 목록은 쿼리에 따라 길이가 다르다.검색 엔진의 성능을 한 쿼리에서 다음 쿼리로 비교하는 것은 DCG만을 사용하여 일관성 있게 달성할 수 없으므로, 선택된 $값{\displaystyle }$ p$${\$displaystyle p$}에 대한 각 위치의 누적 이득은 쿼리에 걸쳐 정규화되어야$$ 한다.이것은 말뭉치의 모든 관련 문서를 상대적 관련성에 따라 분류하여, 위치 $p{\displaystyle }$ ${\displaystyle p}$을 통해 가능한 최대 DCG를 생성하며$,$ 이 위치를 통해 이상적인 DCG(IDCG)라고도 한다.쿼리의 경우 정규화된 할인 누적 이득(nDCG)은 다음과 같이 계산된다.

${\$$$$IDCG_{p$

여기에서 IDCG는 이상적인 할인 누적 이득이다.

${\displaystyle \mathrm {IDCG_{p} =\sum _{i=1}^{{p}{\frac {rel_{i}}{\log _{2}(i+1)}}}}$

및 $R{\displaystyle }$ ${\displaystyle E}$ ${\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\$은(는) 말뭉치에서 p 위치까지의 관련 문서 목록을 나타낸다$$.

모든 쿼리의 nDCG 값을 평균하여 검색 엔진의 순위 알고리즘의 평균 성능을 측정할 수 있다.완벽한 순위 알고리즘에서 $D{\displaystyle }$ ${\displaystyle C}$ G ${\displaystyle p_{}}$ ${\$는 1.0의 nDCG를 생성하는$$ I D ${\displaystyle C}$ ${\displaystyle {}_{}}$ ${\displaystyle p}$ {\$displaystyle IDCG_{p}$와 동일하다는 점에 유의하십시오$.$모든 nDCG 계산은 0.0~1.0 구간에서 상대 값이 되며 교차 쿼리가 비교 가능하다.

nDCG를 사용할 때 발생하는 주요 어려움은 부분적 관련성 피드백만 사용할 수 있는 경우 이상적인 결과 순서를 사용할 수 없다는 것이다.

예

검색 질의에 응답하는 문서 목록과 함께 제시된 실험 참가자는 질의에 대한 각 문서의 관련성을 판단하도록 요청 받는다.각 문서는 0-3의 척도로 판단되며 0의 의미는 관련이 없다는 의미, 3의 의미는 매우 관련이 깊다는 의미, 1과 2의 의미는 "어느 정도"이다.순위 알고리즘이 명령한 문서의 경우

${\displaystyle D_{1},D_{2},D_{3},D_{4},D_{5},D_{6}}$

사용자는 다음과 같은 관련성 점수를 제공한다.

${\displaystyle 3,2,3,0,1,2}$

즉, 문서 1의 관련성은 3, 문서 2의 관련성은 2 등이다.이 검색 결과 목록의 누적 이득:

${\displaystyle \mathrm {CG_{6} =\sum _{i=1}^{6}rel_{i}=3+2+3+0+1+2=11}$

두 문서의 순서를 변경해도 CG 측정에 영향을 미치지 않는다.$D{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$ 스타일 $D_{3}$와 $D{\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$ 스타일 $D_{4}$를 전환하면 CG는 그대로 유지되며, 11. DCG는 결과 목록의 초기에 나타나는 관련성이 높은 문서를 강조하기 위해 사용된다.감소를 위해 로그 척도를 사용하면 각 결과의 DCG는 다음과 같다.

$(\displaystyle i}$	${\displaystyle rel_{i}}$	${\displaystyle \log _{2}(i+1)}$	${\displaystyle {\frac {rel_{i}}{\log_{2}(i+1)}}}$
1	3	1	3
2	2	1.585	1.262
3	3	2	1.5
4	0	2.322	0
5	1	2.585	0.387
6	2	2.807	0.712

따라서$$ 이 순위의 $D{\displaystyle }$ ${\displaystyle C}$ ${\displaystyle {}_{}}$ ${\displaystyle {6\mathrm{}}_{}}$ ${\$은(는) 다음과 같다.

${\displaystyle \mathrm{DCG_{6} =\sum _{i=1}^{6}{\frac {rel_{i}}}{\log_{2}(i+1)}}}=3+1.262+1.5+0+0+0+0.387+0.712=6.861}$

이제 D ${\$과 ${\displaystyle {D\mathrm{}}_{}}$ ${\$의 스위치를 바꾸면 관련성이 낮은 문서가 더 높은 순위에 배치되기 때문에 DCG가 감소한다$$. 즉, 보다 관련성이 높은 문서는 낮은 순위에 배치되어 더 할인된다.

다른 쿼리에 대한 이 쿼리의 성능은 다른 쿼리의 결과가 더 많을 수 있기 때문에 이 형태에서는 비교할 수 없다. 그 결과 전체 DCG가 더 큰 결과를 얻을 수 있기 때문이다.비교를 위해 DCG 값은 정규화되어야 한다.

DCG 값을 정규화하려면 주어진 질의를 위한 이상적인 순서가 필요하다.이 예에서, 그러한 순서는 알려진 모든 관련성 판단의 단조롭게 감소하는 종류가 될 것이다.이 실험의 6개 외에도, 동일한 질의에 대한 관련 등급 3의 문서$$ ${\displaystyle {D\mathrm{}}_{}}$ 7 ${\$과(와) 관련 등급 2의 문서$$ ${\displaystyle {D\mathrm{}}_{}}$ 8 ${\$이(가) 있다는 것도 알고 있다고 가정합시다.그렇다면 이상적인 순서는 다음과 같다.

${\displaystyle 3,3,3,2,2,2,1,0}$

이상적인 랭킹은 순위 분석의 깊이와 일치하도록 다시 길이 6으로 절단된다.

${\displaystyle 3,3,3,2,2,2}$

이 이상적인 주문의 DCG 또는 IDCG(이상 DCG)는 6위로 계산된다.

${\displaystyle \mathrm {IDCG_{6} = 8.740}$

따라서 이 쿼리에 대한 nDCG는 다음과 같이 제공된다.

${\displaystyle \mathrm{nDCG_{6} ={\frac {DCG_{6}}{{6}}}}{{\fracIDCG_{6}}}={\frac {6.861}{8.740}=0.785}$

제한 사항

1. 정규화된 DCG 메트릭은 결과의 불량 문서에 대해 불이익을 주지 않는다.예를 들어, 쿼리가 각각 1,1,1과 1,1,1,0으로 두 개의 결과를 반환하는 경우, 후자가 나쁜 문서를 포함하더라도 둘 다 동등하게 좋은 것으로 간주될 것이다.순위 판단의 경우, 2,1.0 대신 1,0-1의 숫자 점수를 사용할 수적 점수를 매길 수 있다.이로 인해 불량 결과가 반환될 경우 점수가 낮아져 리콜보다 결과의 정밀도를 우선시하게 된다.이 접근방식은 점수의 하한을 0에서 음의 값으로 전환하는 전체 음의 점수를 초래할 수 있다는 점에 유의하십시오.
2. 정규화된 DCG는 결과에서 누락된 문서에 대해 불이익을 주지 않는다.예를 들어, 이상적인 DCG가 전자의 3위, 후자의 5위까지 계산된다고 가정할 때, 쿼리가 각각 1,1,1과 1,1,1,1로 두 결과를 반환하는 경우, 둘 다 동등하게 좋은 것으로 간주된다.이러한 제한을 고려하는 한 가지 방법은 결과 집합에 대해 고정된 세트 크기를 적용하고 누락된 문서에 대해 최소 점수를 사용하는 것이다.이전의 예에서는 1,1,1,0,0,1,1 점수를 사용하고 nDCG를 nDCG@5로 인용할 것이다.
3. 정규화된 DCG는 종종 몇 가지 동일한 좋은 결과를 가질 수 있는 쿼리의 성능을 측정하기에 적합하지 않을 수 있다.이것은 특히 이 측정지표가 실제로 수행되는 것처럼 처음 몇 개의 결과에만 제한될 때 더욱 그러하다.예를 들어, "레스토랑" nDCG@1과 같은 쿼리의 경우 첫 번째 결과만 설명하므로, 한 결과 집합이 인근 지역의 레스토랑을 1개만 포함하고 다른 세트는 5개를 포함하는 경우, 두 결과 집합 모두 더 포괄적이더라도 동일한 점수를 받게 된다.

참고 항목

• 평가조치(정보검색)
• 순위 매기기

참조