Ganho cumulativo descontado - Discounted cumulative gain

O ganho cumulativo descontado ( DCG ) é uma medida de qualidade de classificação. Na recuperação de informações , é frequentemente usado para medir a eficácia dos algoritmos do mecanismo de pesquisa da web ou aplicativos relacionados. Usando uma escala de relevância graduada de documentos em um conjunto de resultados de mecanismo de pesquisa, o DCG mede a utilidade, ou ganho , de um documento com base em sua posição na lista de resultados. O ganho é acumulado do topo para a parte inferior da lista de resultados, com o ganho de cada resultado descontado nas classificações inferiores.

Visão geral

Duas suposições são feitas ao usar DCG e suas medidas relacionadas.

1. Documentos altamente relevantes são mais úteis quando aparecem no início de uma lista de resultados de mecanismo de pesquisa (têm classificações mais altas)
2. Documentos altamente relevantes são mais úteis do que documentos marginalmente relevantes, que por sua vez são mais úteis do que documentos não relevantes.

DCG se origina de uma medida anterior, mais primitiva, chamada de ganho cumulativo.

Ganho Cumulativo

Ganho cumulativo (CG) é a soma dos valores de relevância classificados de todos os resultados em uma lista de resultados de pesquisa. Este predecessor do DCG não inclui a classificação (posição) de um resultado na lista de resultados na consideração da utilidade de um conjunto de resultados. O CG em uma determinada posição de classificação é definido como: ${\ displaystyle p}$

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

Onde está a relevância graduada do resultado na posição . ${\ displaystyle rel_ {i}}$${\ displaystyle i}$

O valor calculado com a função CG não é afetado por alterações na ordem dos resultados da pesquisa. Ou seja, mover um documento altamente relevante acima de um documento com classificação superior, menos relevante, não altera o valor calculado para CG (assumindo ). Com base nas duas suposições feitas acima sobre a utilidade dos resultados da pesquisa, (N) DCG é geralmente preferido em vez de CG. ${\ displaystyle d_ {i}}$${\ displaystyle d_ {j}}$${\ displaystyle i, j \ leq p}$

O ganho cumulativo é às vezes chamado de precisão graduada, pois é idêntico à métrica de precisão se a escala de classificação for binária.

Ganho Cumulativo Descontado

A premissa do DCG é que documentos altamente relevantes que aparecem em uma posição inferior em uma lista de resultados de pesquisa devem ser penalizados, pois o valor de relevância classificado é reduzido logaritmicamente proporcional à posição do resultado.

A fórmula tradicional de DCG acumulada em uma determinada posição de classificação é definida como: ${\ displaystyle p}$

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

Anteriormente, não havia nenhuma justificativa teoricamente sólida para usar um fator de redução logarítmica além do fato de que ele produz uma redução suave. Mas Wang et al. (2013) deram garantia teórica para o uso do fator de redução logarítmica em DCG Normalizado (NDCG). Os autores mostram que para cada par de funções de classificação substancialmente diferentes, o NDCG pode decidir qual é a melhor de maneira consistente.

Uma formulação alternativa de DCG coloca maior ênfase na recuperação de documentos relevantes:

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

A última fórmula é comumente usada na indústria, incluindo grandes empresas de pesquisa na web e plataformas de competição de ciência de dados, como Kaggle.

Essas duas formulações de DCG são as mesmas quando os valores de relevância dos documentos são binários ; . ${\ displaystyle rel_ {i} \ in \ {0,1 \}}$

Observe que Croft et al. (2010) e Burges et al. (2005) apresentam o segundo DCG com um log de base e, enquanto ambas as versões de DCG acima usam um log de base 2. Ao calcular NDCG com a primeira formulação de DCG, a base do log não importa, mas a base de o log afeta o valor de NDCG para a segunda formulação. Claramente, a base do log afeta o valor de DCG em ambas as formulações.

DCG normalizado

As listas de resultados da pesquisa variam em comprimento dependendo da consulta . Comparar o desempenho de um mecanismo de pesquisa de uma consulta para a próxima não pode ser alcançado de forma consistente usando DCG sozinho, portanto, o ganho cumulativo em cada posição para um valor escolhido de deve ser normalizado nas consultas. Isso é feito classificando todos os documentos relevantes no corpus por sua relevância relativa, produzindo o máximo DCG possível por meio da posição , também chamado de DCG Ideal (IDCG) por meio dessa posição. Para uma consulta, o ganho cumulativo descontado normalizado , ou nDCG, é calculado como: ${\ displaystyle p}$${\ displaystyle p}$

${\ displaystyle \ mathrm {nDCG_ {p}} = {\ frac {DCG_ {p}} {IDCG_ {p}}}}$,

onde IDCG é o ganho cumulativo com desconto ideal,

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

e representa a lista de documentos relevantes (ordenados por relevância) no corpus até a posição p. ${\ displaystyle REL_ {p}}$

Os valores nDCG para todas as consultas podem ser calculados para obter uma medida do desempenho médio do algoritmo de classificação de um mecanismo de pesquisa. Observe que, em um algoritmo de classificação perfeita, o será o mesmo que produzir um nDCG de 1,0. Todos os cálculos do nDCG são então valores relativos no intervalo de 0,0 a 1,0 e, portanto, são comparáveis ​​à consulta cruzada. ${\ displaystyle DCG_ {p}}$${\ displaystyle IDCG_ {p}}$

A principal dificuldade encontrada no uso do nDCG é a indisponibilidade de uma ordenação ideal dos resultados quando apenas o feedback de relevância parcial está disponível.

Exemplo

Apresentado com uma lista de documentos em resposta a uma consulta de pesquisa, um participante do experimento é solicitado a avaliar a relevância de cada documento para a consulta. Cada documento deve ser julgado em uma escala de 0-3, com 0 significando irrelevante, 3 significando altamente relevante e 1 e 2 significando "em algum lugar no meio". Para os documentos ordenados pelo algoritmo de classificação como

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

o usuário fornece as seguintes pontuações de relevância:

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

Ou seja: o documento 1 tem uma relevância de 3, o documento 2 tem uma relevância de 2, etc. O ganho cumulativo desta lista de resultados de pesquisa é:

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

Alterar a ordem de quaisquer dois documentos não afeta a medida CG. Se e forem trocados, o CG permanece o mesmo, 11. DCG é usado para enfatizar documentos altamente relevantes que aparecem no início da lista de resultados. Usando a escala logarítmica para redução, o DCG para cada resultado na ordem é: ${\ displaystyle D_ {3}}$${\ displaystyle D_ {4}}$

${\ 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

Portanto, o desta classificação é: ${\ displaystyle DCG_ {6}}$

${\ displaystyle \ mathrm {DCG_ {6}} = \ sum _ {i = 1} ^ {6} {\ frac {rel_ {i}} {\ log _ {2} (i + 1)}} = 3+ 1,262 + 1,5 + 0 + 0,387 + 0,712 = 6,861}$

Agora, uma troca de e resulta em um DCG reduzido porque um documento menos relevante é colocado em uma posição superior na classificação; ou seja, um documento mais relevante é descontado mais por ser colocado em uma posição inferior. ${\ displaystyle D_ {3}}$${\ displaystyle D_ {4}}$

O desempenho desta consulta para outra é incomparável nesta forma, pois a outra consulta pode ter mais resultados, resultando em um DCG geral maior que pode não ser necessariamente melhor. Para comparar, os valores DCG devem ser normalizados.

Para normalizar os valores DCG, uma ordem ideal para a consulta fornecida é necessária. Para este exemplo, essa ordem seria o tipo monotonicamente decrescente de todos os julgamentos de relevância conhecidos. Além dos seis deste experimento, suponha que também saibamos que existe um documento com grau de relevância 3 para a mesma consulta e um documento com grau de relevância 2 para essa consulta. Então, a ordem ideal é: ${\ displaystyle D_ {7}}$${\ displaystyle D_ {8}}$

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

Sem o D7 e o D8, o pedido ideal é:

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

O DCG desta ordem ideal, ou IDCG (Ideal DCG) , é calculado para a classificação 6:

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

E assim o nDCG para esta consulta é fornecido como:

${\ displaystyle \ mathrm {nDCG_ {6}} = {\ frac {DCG_ {6}} {IDCG_ {6}}} = {\ frac {6,861} {7,141}} = 0,961}$

Limitações

1. A métrica DCG normalizada não penaliza por documentos incorretos no resultado. Por exemplo, se uma consulta retornar dois resultados com pontuações 1,1,1 e 1,1,1,0 respectivamente, ambos serão considerados igualmente bons, mesmo que o último contenha um documento inválido . Para os julgamentos de classificação Excelente, Regular, Ruim, pode-se usar pontuações numéricas 1,0, -1 em vez de 2,1,0 . Isso faria com que a pontuação diminuísse se resultados ruins fossem retornados, priorizando a precisão dos resultados em relação ao recall. Observe que essa abordagem pode resultar em uma pontuação geral negativa que mudaria o limite inferior da pontuação de 0 para um valor negativo.
2. O DCG normalizado não penaliza por documentos faltantes no resultado. Por exemplo, se uma consulta retornar dois resultados com pontuações 1,1,1 e 1,1,1,1,1 respectivamente, ambos seriam considerados igualmente bons, assumindo que o DCG ideal é calculado para classificar 3 para o primeiro e classificar 5 para o último. Uma maneira de levar em conta essa limitação é impor um tamanho de conjunto fixo para o conjunto de resultados e usar pontuações mínimas para os documentos ausentes. No exemplo anterior, usaríamos as pontuações 1,1,1,0,0 e 1,1,1,1,1 e citaríamos nDCG como nDCG @ 5.
3. O DCG normalizado pode não ser adequado para medir o desempenho de consultas que muitas vezes podem ter vários resultados igualmente bons. Isso é especialmente verdadeiro quando essa métrica é limitada apenas aos primeiros resultados, como é feito na prática. Por exemplo, para consultas como "restaurantes" nDCG @ 1 seria responsável apenas pelo primeiro resultado e, portanto, se um conjunto de resultados contiver apenas 1 restaurante da área próxima enquanto o outro contém 5, ambos acabam tendo a mesma pontuação, embora o último é mais abrangente.

Veja também

• Medidas de avaliação (recuperação de informação)
• Aprendendo a classificar

Referências