रियायती संचयी लाभ

रियायती संचयी लाभ (DCG) रैंकिंग गुणवत्ता का परिमाण है। सूचना पुनर्प्राप्ति में, इसका उपयोग अधिकतर वर्ल्ड वाइड वेब खोज इंजन कलन विधि या संबंधित अनुप्रयोगों की प्रभावशीलता को मापने के लिए किया जाता है। खोज-इंजन परिणाम संग्रह में दस्तावेजों के श्रेणीबद्ध प्रासंगिकता (सूचना पुनर्प्राप्ति) परिणाम का उपयोग करते हुए डीसीजी परिणाम सूची में दस्तावेज़ की स्थिति के आधार पर उसकी उपयोगिता या लाभ को मापता है। लाभ परिणाम सूची के शीर्ष से नीचे तक संचित होता है प्रत्येक परिणाम के लाभ को निचले श्रेणीयों पर छूट दी जाती है।

सिंहावलोकन

डीसीजी और उससे संबंधित उपायों का उपयोग करने में दो धारणाएं बनाई जाती हैं।

1. खोज इंजन परिणाम सूची में पहले प्रदर्शित होने पर अत्यधिक प्रासंगिक दस्तावेज़ अधिक उपयोगी होते हैं (उच्च रैंक वाले)
2. अत्यधिक प्रासंगिक दस्तावेज मामूली प्रासंगिक दस्तावेजों की तुलना में अधिक उपयोगी होते हैं, जो बदले में गैर-प्रासंगिक दस्तावेजों की तुलना में अधिक उपयोगी होते हैं।

डीसीजी पहले के, अधिक आदिम, संचयी लाभ नामक उपाय से उत्पन्न होता है।

संचयी लाभ

संचयी लाभ (सीजी) एक खोज परिणाम सूची में सभी परिणामों के श्रेणीबद्ध प्रासंगिकता मूल्यों का योग है। DCG के इस पूर्ववर्ती परिणाम सेट की उपयोगिता के विचार में परिणाम सूची में परिणाम के रैंक (स्थिति) को शामिल नहीं करता है। एक विशेष रैंक की स्थिति में सीजी $p$ परिभाषित किया जाता है:

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

कहाँ $rel_{i}$ स्थिति पर परिणाम की श्रेणीबद्ध प्रासंगिकता है $i$.

CG फ़ंक्शन के साथ परिकलित मान खोज परिणामों के क्रम में परिवर्तन से अप्रभावित रहता है। यानी एक अत्यधिक प्रासंगिक दस्तावेज़ को स्थानांतरित करना $d_{i}$ उच्च रैंक के ऊपर, कम प्रासंगिक, दस्तावेज़ $d_{j}$ CG के लिए परिकलित मान नहीं बदलता है (यह मानते हुए $i,j\leq p$). खोज परिणामों की उपयोगिता के बारे में ऊपर की गई दो मान्यताओं के आधार पर, (N)DCG को आमतौर पर CG से अधिक पसंद किया जाता है।

संचयी लाभ को कभी-कभी ग्रेडेड प्रेसिजन कहा जाता है क्योंकि यह सटीक मीट्रिक के समान होता है यदि रेटिंग स्केल बाइनरी है।

रियायती संचयी लाभ

DCG का आधार यह है कि खोज परिणाम सूची में नीचे दिखाई देने वाले अत्यधिक प्रासंगिक दस्तावेज़ों को दंडित किया जाना चाहिए क्योंकि श्रेणीबद्ध प्रासंगिकता मान परिणाम की स्थिति के लिए लघुगणकीय रूप से आनुपातिक रूप से कम हो जाता है।

DCG का पारंपरिक सूत्र एक विशेष रैंक की स्थिति में संचित होता है $p$ परिभाषित किया जाता है:

$\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)}}$

पहले लॉगरिदमिक रिडक्शन फैक्टर का उपयोग करने के लिए सैद्धांतिक रूप से कोई ठोस औचित्य नहीं था<ref name=CMS2009>B. Croft; D. Metzler; T. Strohman (2010). Search Engines: Information Retrieval in Practice. Addison Wesley.</ref> इस तथ्य के अलावा कि यह एक चिकनी कमी पैदा करता है, लेकिन वांग एट अल (2013) ने सामान्यीकृत डीसीजी (एनडीसीजी) में लॉगरिदमिक कमी कारक का उपयोग करने के लिए सैद्धांतिक आश्वासन दिया। लेखक बताते हैं कि प्रत्येक जोड़ी के अलग-अलग रैंकिंग कार्यों के लिए एनडीसीजी यह तय कर सकता है कि कौन सा सुसंगत तरीके से बेहतर है।

डीसीजी का एक वैकल्पिक सूत्रीकरण प्रासंगिक दस्तावेजों को पुनः प्राप्त करने पर अधिक जोर देता है:

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

प्रमुख वेब खोज कंपनियों सहित उद्योग सामान्यतौर पर बाद वाले सूत्र और डेटा विज्ञान प्रतियोगिता मंच जैसे कागल का उपयोग किया जाता है।

डीसीजी के ये दो सूत्रीकरण समान हैं जब दस्तावेजों के प्रासंगिक मूल्य द्विआधारी फ़ंक्शन हैं $rel_{i}\in \{0,1\}$.

ध्यान दें कि क्रॉफ्ट एट अल (2010) और बर्गेस एट अल (2005) बेस ई के लॉग के साथ दूसरा डीसीजी (DCG) प्रस्तुत करते हैं, जबकि ऊपर डीसीजी के दोनों संस्करण बेस 2 के लॉग का उपयोग करते हैं। डीसीजी के पहले सूत्रीकरण के साथ एनडीसीजी की गणना करते समय लॉग का आधार कोई मायने नहीं रखता लेकिन इसका आधार लॉग दूसरे सूत्रीकरण के लिए एनडीसीजी के मूल्य को प्रभावित करता है स्पष्ट रूप से लॉग का आधार दोनों योगों में डीसीजी के मान को प्रभावित करता है।

सामान्यीकृत डीसीजी

वेब खोज क्वेरी के आधार पर खोज परिणाम सूचियां लंबाई में भिन्न होती हैं। खोज इंजन के प्रदर्शन की तुलना एक क्वेरी से अगली तक लगातार डीसीजी का उपयोग करके प्राप्त नहीं किया जा सकता है इसलिए $p$ के चुने हुए मान के लिए प्रत्येक स्थान पर संचयी लाभ को सभी प्रश्नों में सामान्यीकृत किया जाना चाहिए। यह कॉर्पस में सभी प्रासंगिक दस्तावेजों को उनकी सापेक्ष प्रासंगिकता के आधार पर क्रमबद्ध करके किया जाता है, जिससे स्थिति के माध्यम से अधिकतम संभव डीसीजी का उत्पादन $p$होता है, जिसे आइडियल डीसीजी (आईडीसीजी) भी कहा जाता है। किसी क्वेरी के लिए सामान्यीकृत छूट प्राप्त संचयी लाभ या nDCG की गणना इस प्रकार की जाती है:

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

जहां IDCG आइडियल बट्टाकृत संचयी लाभ है,

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

और $REL_{p}$ कॉर्पस में स्थिति p तक प्रासंगिक दस्तावेज़ों की सूची (उनकी प्रासंगिकता के अनुसार क्रमित) का प्रतिनिधित्व करता है।

खोज इंजन के रैंकिंग एल्गोरिथम के औसत प्रदर्शन का माप प्राप्त करने के लिए सभी प्रश्नों के लिए nDCG मानों का औसत निकाला जा सकता है। ध्यान दें कि एक पूर्ण रैंकिंग एल्गोरिथम में $DCG_{p}$ के समान होगा $IDCG_{p}$ 1.0 का nDCG उत्पन्न करता है। सभी एनडीसीजी गणना तब अंतराल 0.0 से 1.0 पर सापेक्ष मान हैं इसलिए क्रॉस-क्वेरी तुलनीय हैं।

एनडीसीजी का उपयोग करने में आने वाली मुख्य कठिनाई परिणामों के आइडियल क्रम की अनुपलब्धता है जब केवल आंशिक प्रासंगिक प्रतिक्रिया उपलब्ध होती है।

उदाहरण

खोज क्वेरी के जवाब में दस्तावेजों की एक सूची के साथ प्रस्तुत किया गया एक प्रयोग प्रतिभागी को क्वेरी के लिए प्रत्येक दस्तावेज़ की प्रासंगिकता का न्याय करने के लिए कहा गया। प्रत्येक दस्तावेज़ को 0-3 के पैमाने पर आंका जाता है, जिसमें 0 का अर्थ प्रासंगिक नहीं है, 3 का अर्थ अत्यधिक प्रासंगिक है तथा 1 और 2 का अर्थ कहीं बीच में है। रैंकिंग एल्गोरिथम द्वारा क्रम किए गए दस्तावेज़ों के लिए

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

उपयोगकर्ता निम्नलिखित प्रासंगिकता अंक प्रदान करता है:

$3,2,3,0,1,2$

अर्थात्: दस्तावेज़ 1 की प्रासंगिकता 3 है, दस्तावेज़ 2 की प्रासंगिकता 2 है आदि। इस खोज परिणाम प्रविष्टि का संचयी लाभ है:

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

किन्हीं दो दस्तावेज़ों के क्रम को बदलने से CG माप प्रभावित नहीं होता है। अगर $D_{3}$ और $D_{4}$ स्विच किए जाते हैं तो सीजी वही रहता है, 11 डीसीजी का उपयोग परिणाम सूची में जल्दी दिखाई देने वाले अत्यधिक प्रासंगिक दस्तावेजों पर सूची को जोर देने के लिए किया जाता है। कमी के लिए लघुगणकीय आकड़े का उपयोग करते हुए क्रम में प्रत्येक परिणाम के लिए डीसीजी है:

$i$	$rel_{i}$	$\log _{2}(i+1)$	${\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

इतना $DCG_{6}$ इस रैंकिंग का है:

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

अब $D_{3}$ और $D_{4}$ के स्विच से डीसीजी कम हो जाता है क्योंकि एक कम प्रासंगिक दस्तावेज़ को रैंकिंग में ऊपर रखा जाता है अर्थात्, एक अधिक प्रासंगिक दस्तावेज़ को कम श्रेणी में रखकर अधिक छूट दी जाती है।

इस क्वेरी का प्रदर्शन दूसरे के लिए इस रूप में अतुलनीय है क्योंकि अन्य क्वेरी के अधिक परिणाम हो सकते हैं, जिसके परिणामस्वरूप एक बड़ा समग्र डीसीजी हो सकता है जो जरूरी नहीं कि बेहतर हो। तुलना करने के लिए, डीसीजी मूल्यों को सामान्यीकृत किया जाना चाहिए।

डीसीजी मूल्यों को सामान्य करने के लिए दी गई क्वेरी के लिए एक आइडियल क्रम की आवश्यकता होती है। इस उदाहरण के लिए, वह आदेश सभी ज्ञात प्रासंगिक निर्णयों का नीरस रूप से घटता क्रम होगा। इस प्रयोग से छः के अलावा, मान लीजिए कि हम यह भी जानते हैं कि एक दस्तावेज है $D_{7}$ जिसकी प्रासंगिकता ग्रेड 3 है और एक दस्तावेज़ के लिए $D_{8}$ उस क्वेरी के लिए प्रासंगिकता ग्रेड 2 हैं, तब आइडियल क्रम है:

$3,3,3,2,2,2,1,0$

रैंकिंग के विश्लेषण की गहराई से मिलान करने के लिए आइडियल रैंकिंग को फिर से लंबाई 6 में काट दिया जाता है:

$3,3,3,2,2,2$

इस आइडियल क्रम के DCG या IDCG (आइडियल DCG) की गणना 6 श्रेणी पर की जाती है:

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

इसलिए इस प्रश्न के लिए एनडीसीजी इस प्रकार दिया गया है:

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

सीमाएं

1. सामान्यीकृत डीसीजी मीट्रिक परिणाम में खराब दस्तावेज़ों के लिए दंडित नहीं करता है। उदाहरण के लिए, यदि कोई क्वेरी क्रमशः 1,1,1 और 1,1,1,0 अंक के साथ दो परिणाम देती है तो दोनों को समान रूप से अच्छा माना जाएगा, भले ही बाद वाले में खराब दस्तावेज़ हो। उत्कृष्ट, उचित, खराब रैंकिंग निर्णयों के लिए 2,1,0 के बजाय संख्यात्मक अंक 1,0, -1 का उपयोग किया जा सकता है। यदि खराब परिणाम लौटाए जाते हैं तो इससे अंक कम हो जाएगा, प्रत्याह्वान पर परिणामों की सटीकता को प्राथमिकता दी जाएगी। ध्यान दें कि इस दृष्टिकोण के परिणामस्वरूप समग्र नकारात्मक अंक हो सकता है जो अंक की निचली सकता को 0 से नकारात्मक मान में बदल देगा।
2. सामान्यीकृत डीसीजी परिणाम में लापता दस्तावेजों के लिए दंडित नहीं करता है। उदाहरण के लिए, यदि कोई प्रश्न क्रमशः 1,1,1 और 1,1,1,1,1 अंक के साथ दो परिणाम देता है, तो दोनों को समान रूप से अच्छा माना जाएगा, यह मानते हुए कि आइडियल डीसीजी की गणना पूर्व के लिए श्रेणी 3 और बाद के लिए श्रेणी 5 पर की जाती है। इस सीमा को ध्यान में रखने का एक तरीका परिणाम संग्रह के लिए निश्चित संग्रह आकार को लागू करना और लापता दस्तावेज़ों के लिए न्यूनतम अंक का उपयोग करना है। पिछले उदाहरण में, हम अंक 1,1,1,0,0 और 1,1,1,1,1 का उपयोग करेंगे और nDCG को nDCG@5 के रूप में उद्धृत करें।
3. सामान्यीकृत डीसीजी उन प्रश्नों के प्रदर्शन को मापने के लिए उपयुक्त नहीं हो सकता है जिनके ज्यादातर समान रूप से कई अच्छे परिणाम हो सकते हैं। यह विशेष रूप से सच है जब यह मीट्रिक केवल पहले कुछ परिणामों तक ही सीमित है जैसा कि व्यवहार में किया जाता है। उदाहरण के लिए "रेस्टोरेंट" जैसे प्रश्नों के लिए nDCG@1 केवल पहले परिणाम के लिए जिम्मेदार होगा इसलिए यदि एक परिणाम सेट में पास के क्षेत्र से केवल 1 रेस्टोरेंट सम्मिलित है जबकि दूसरे में 5 हैं, तो दोनों का अंक समान होगा भले ही उत्तरार्द्ध अधिक व्यापक है।

यह भी देखें

• मूल्यांकन उपाय (सूचना पुनर्प्राप्ति)
• रैंक करना सीखना