रियायती संचयी लाभ: Difference between revisions

From Vigyanwiki
No edit summary
 
(17 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Measure of ranking quality}}
{{Short description|Measure of ranking quality}}
रियायती संचयी लाभ (DCG) रैंकिंग गुणवत्ता का परिमाण है। सूचना पुनर्प्राप्ति में, इसका उपयोग अधिकतर [[वर्ल्ड वाइड वेब]] [[खोज इंजन]] [[कलन विधि]] या संबंधित अनुप्रयोगों की प्रभावशीलता को मापने के लिए किया जाता है। खोज-इंजन परिणाम संग्रह में दस्तावेजों के श्रेणीबद्ध [[प्रासंगिकता (सूचना पुनर्प्राप्ति)]] परिणाम का उपयोग करते हुए डीसीजी परिणाम सूची में दस्तावेज़ की स्थिति के आधार पर उसकी उपयोगिता या लाभ को मापता है। लाभ परिणाम सूची के शीर्ष से नीचे तक संचित होता है प्रत्येक परिणाम के लाभ को निचले श्रेणीयों पर छूट दी जाती है।<ref name="jarvelin_2002_cumulated">Kalervo Järvelin, जाना Kekäläinen: IR तकनीकों का संचयी लाभ-आधारित मूल्यांकन। सूचना प्रणाली पर एसीएम लेनदेन 20(4), 422-446 (2002)
रियायती संचयी लाभ (DCG) श्रेणी    गुणवत्ता का परिमाण है। सूचना पुनर्प्राप्ति में इसका उपयोग अधिकतर [[वर्ल्ड वाइड वेब]] [[खोज इंजन]] [[कलन विधि]] या संबंधित अनुप्रयोगों की प्रभावशीलता को मापने के लिए किया जाता है। खोज-इंजन परिणाम सेट      में दस्तावेजों के श्रेणीबद्ध [[प्रासंगिकता (सूचना पुनर्प्राप्ति)]] परिणाम का उपयोग करते हुए डीसीजी परिणाम सूची में दस्तावेज़ की स्थिति के आधार पर उसकी उपयोगिता या लाभ को मापता है। लाभ परिणाम सूची के शीर्ष से नीचे तक संचित होता है प्रत्येक परिणाम के लाभ को निचले श्रेणीयों पर छूट दी जाती है।<ref name="jarvelin_2002_cumulated">Kalervo Järvelin, जाना Kekäläinen: IR तकनीकों का संचयी लाभ-आधारित मूल्यांकन। सूचना प्रणाली पर एसीएम लेनदेन 20(4), 422-446 (2002)
</ref>
</ref>


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


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


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


===संचयी लाभ===
===संचयी लाभ===


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


:<math> \mathrm{CG_{p}} = \sum_{i=1}^{p} rel_{i} </math>
:<math> \mathrm{CG_{p}} = \sum_{i=1}^{p} rel_{i} </math>
जहाँ <math>rel_{i}</math> स्थान <math>i</math> पर परिणाम की श्रेणीबद्ध प्रासंगिकता है।
जहाँ <math>rel_{i}</math> स्थान <math>i</math> पर परिणाम की श्रेणीबद्ध प्रासंगिकता है।


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


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


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


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


एक विशेष रैंक स्थिति <math>p</math> पर संचित DCG के पारंपरिक सूत्र को इस रूप में परिभाषित किया जाता है:
विशेष पद स्थिति <math>p</math> पर संचित DCG के पारंपरिक सूत्र को इस रूप में परिभाषित किया जाता है:


:<math> \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)} </math>
:<math> \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)} </math>
पहले लॉगरिदमिक रिडक्शन फैक्टर का उपयोग करने के लिए सैद्धांतिक रूप से कोई ठोस औचित्य नहीं था<nowiki><ref name=CMS2009></nowiki>{{cite book | title=Search Engines: Information Retrieval in Practice |author1=B. Croft |author2=D. Metzler |author3=T. Strohman |year=2010 | publisher=Addison Wesley}}<nowiki></ref></nowiki> इस तथ्य के अलावा कि यह एक सहज कमी पैदा करता है, लेकिन वांग एट अल (2013)<ref>Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Wei Chen, [[Tie-Yan Liu]]. 2013. A Theoretical Analysis of Normalized Discounted Cumulative Gain (NDCG) Ranking Measures. In Proceedings of the 26th Annual Conference on Learning Theory (COLT 2013).</ref> ने सामान्यीकृत डीसीजी (एनडीसीजी) में लघुगणकीय कमी कारक का उपयोग करने के लिए सैद्धांतिक आश्वासन दिया। लेखक बताते हैं कि प्रत्येक जोड़ी के अलग-अलग रैंकिंग कार्यों के लिए एनडीसीजी यह तय कर सकता है कि कौन सा सुसंगत तरीके से बेहतर है।
पहले लघुगणक कमी कारक का उपयोग करने के लिए सैद्धांतिक रूप से कोई ठोस औचित्य नहीं था<ref name=CMS2009>{{cite book | title=Search Engines: Information Retrieval in Practice |author1=B. Croft |author2=D. Metzler |author3=T. Strohman |year=2010 | publisher=Addison Wesley}}<nowiki></ref></nowiki> इस तथ्य के अलावा कि यह एक सहज कमी पैदा करता है, लेकिन वांग एट अल (2013)<ref>Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Wei Chen, [[Tie-Yan Liu]]. 2013. A Theoretical Analysis of Normalized Discounted Cumulative Gain (NDCG) Ranking Measures. In Proceedings of the 26th Annual Conference on Learning Theory (COLT 2013).</ref> ने सामान्यीकृत डीसीजी (एनडीसीजी) में लघुगणकीय कमी कारक का उपयोग करने के लिए सैद्धांतिक आश्वासन दिया। लेखक बताते हैं कि प्रत्येक जोड़ी के अलग-अलग श्रेणी कार्यों के लिए एनडीसीजी यह तय कर सकता है कि कौन सा सुसंगत तरीके से बेहतर है।


डीसीजी का एक वैकल्पिक सूत्रीकरण<ref>Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005. Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning (ICML '05). ACM, New York, NY, USA, 89-96. DOI=10.1145/1102351.1102363 http://doi.acm.org/10.1145/1102351.1102363</ref> प्रासंगिक दस्तावेजों को पुनः प्राप्त करने पर अधिक जोर देता है:
डीसीजी का वैकल्पिक सूत्रीकरण<ref>Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005. Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning (ICML '05). ACM, New York, NY, USA, 89-96. DOI=10.1145/1102351.1102363 http://doi.acm.org/10.1145/1102351.1102363</ref> प्रासंगिक दस्तावेजों को पुनः प्राप्त करने पर अधिक जोर देता है:


:<math> \mathrm{DCG_{p}} = \sum_{i=1}^{p} \frac{ 2^{rel_{i}} - 1 }{ \log_{2}(i+1)} </math>
:<math> \mathrm{DCG_{p}} = \sum_{i=1}^{p} \frac{ 2^{rel_{i}} - 1 }{ \log_{2}(i+1)} </math>
बाद वाला सूत्र आम तौर पर प्रमुख वेब खोज कंपनियों<ref name="stanfordireval">{{cite web|title=सूचना पुनर्प्राप्ति का परिचय - मूल्यांकन|url=http://www.stanford.edu/class/cs276/handouts/EvaluationNew-handout-6-per.pdf|publisher=Stanford University|accessdate=23 March 2014|date=21 April 2013}}</ref>  और डेटा साइंस प्रतियोगिता प्लेटफॉर्म जैसे कागल सहित उद्योग में उपयोग किया जाता है।
बाद वाला सूत्र सामान्य तौर पर प्रमुख वेब खोज कंपनियों<ref name="stanfordireval">{{cite web|title=सूचना पुनर्प्राप्ति का परिचय - मूल्यांकन|url=http://www.stanford.edu/class/cs276/handouts/EvaluationNew-handout-6-per.pdf|publisher=Stanford University|accessdate=23 March 2014|date=21 April 2013}}</ref>  और डेटा विज्ञान प्रतियोगिता मंच जैसे कागल सहित उद्योग में उपयोग किया जाता है।


डीसीजी के ये दो सूत्रीकरण समान हैं जब दस्तावेजों के प्रासंगिक मूल्य [[बाइनरी फ़ंक्शन|द्विआधारी]] हैं <ref name="CMS2009" />{{rp|320}} <math>rel_{i} \in \{0,1\}</math>.
डीसीजी के ये दो सूत्रीकरण समान हैं जब दस्तावेजों के प्रासंगिक मूल्य [[बाइनरी फ़ंक्शन|द्विआधारी]] हैं <ref name="CMS2009" />{{rp|320}} <math>rel_{i} \in \{0,1\}</math>.


ध्यान दें कि क्रॉफ्ट एट अल (2010) और बर्गेस एट अल (2005) बेस ई के लॉग के साथ दूसरा डीसीजी (DCG) प्रस्तुत करते हैं, जबकि ऊपर डीसीजी के दोनों संस्करण बेस 2 के लॉग का उपयोग करते हैं। डीसीजी के पहले सूत्रीकरण के साथ एनडीसीजी की गणना करते समय लॉग का आधार कोई मायने नहीं रखता लेकिन इसका आधार लॉग दूसरे सूत्रीकरण के लिए एनडीसीजी के मूल्य को प्रभावित करता है। स्पष्ट रूप से लॉग का आधार दोनों योगों में डीसीजी के मान को प्रभावित करता है।
ध्यान दें कि क्रॉफ्ट एट अल (2010) और बर्गेस एट अल (2005) बेस ई के लॉग के साथ दूसरा डीसीजी (DCG) प्रस्तुत करते हैं, जबकि ऊपर डीसीजी के दोनों संस्करण बेस 2 के लॉग का उपयोग करते हैं। डीसीजी के पहले सूत्रीकरण के साथ एनडीसीजी की गणना करते समय लॉग का आधार कोई मायने नहीं रखता लेकिन इसका आधार लॉग दूसरे सूत्रीकरण के लिए एनडीसीजी के मूल्य को प्रभावित करता है, स्पष्ट रूप से लॉग का आधार दोनों योगों में डीसीजी के मान को प्रभावित करता है।
<!-- Not very clear, does it affect or no the value of DCG? Answer: It affects the DCG, but not the NDCG in the first formulation. -->
<!-- Not very clear, does it affect or no the value of DCG? Answer: It affects the DCG, but not the NDCG in the first formulation. -->




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


:<math> \mathrm{nDCG_{p}} = \frac{DCG_{p}}{IDCG_{p}} </math>,
:<math> \mathrm{nDCG_{p}} = \frac{DCG_{p}}{IDCG_{p}} </math>,
Line 51: Line 51:


:<math> \mathrm{IDCG_{p}} = \sum_{i=1}^{|REL_p|} \frac{ rel_{i} }{ \log_{2}(i+1)} </math>
:<math> \mathrm{IDCG_{p}} = \sum_{i=1}^{|REL_p|} \frac{ rel_{i} }{ \log_{2}(i+1)} </math>
और <math>REL_p</math> कॉर्पस में स्थिति p तक प्रासंगिक दस्तावेज़ों की सूची (उनकी प्रासंगिकता के अनुसार क्रमित) का प्रतिनिधित्व करता है।
और <math>REL_p</math> मानवशरीर में स्थिति p तक प्रासंगिक दस्तावेज़ों की सूची (उनकी प्रासंगिकता के अनुसार क्रमित) का प्रतिनिधित्व करता है।


खोज इंजन के रैंकिंग एल्गोरिथम के औसत प्रदर्शन का माप प्राप्त करने के लिए सभी प्रश्नों के लिए nDCG मानों का औसत निकाला जा सकता है। ध्यान दें कि एक पूर्ण रैंकिंग एल्गोरिथम में <math>DCG_p</math> के समान होगा <math>IDCG_p</math> 1.0 का nDCG उत्पन्न करता है। सभी एनडीसीजी गणना तब अंतराल 0.0 से 1.0 पर सापेक्ष मान हैं इसलिए क्रॉस-क्वेरी तुलनीय हैं।
खोज इंजन के श्रेणी कलन विधि के औसत प्रदर्शन का माप प्राप्त करने के लिए सभी प्रश्नों के लिए nDCG मानों का औसत निकाला जा सकता है। ध्यान दें कि एक पूर्ण श्रेणी कलन विधि में <math>DCG_p</math> के समान होगा <math>IDCG_p</math> 1.0 का nDCG उत्पन्न करता है। सभी एनडीसीजी गणना तब अंतराल 0.0 से 1.0 पर सापेक्ष मान हैं इसलिए प्रति-प्रश्न तुलनीय हैं।


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


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


:<math> D_{1}, D_{2}, D_{3}, D_{4}, D_{5}, D_{6} </math>
:<math> D_{1}, D_{2}, D_{3}, D_{4}, D_{5}, D_{6} </math>
Line 108: Line 108:
| 0.712
| 0.712
|}
|}
इतना <math>DCG_{6}</math> इस रैंकिंग का है:
<math>DCG_{6}</math> इस श्रेणी का है:


:<math> \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</math>
:<math> \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</math>
अब <math>D_3</math> और <math>D_4</math> के स्विच से डीसीजी कम हो जाता है क्योंकि एक कम प्रासंगिक दस्तावेज़ को रैंकिंग में ऊपर रखा जाता है अर्थात्, एक अधिक प्रासंगिक दस्तावेज़ को कम श्रेणी में रखकर अधिक छूट दी जाती है।
अब <math>D_3</math> और <math>D_4</math> के स्विच से डीसीजी कम हो जाता है क्योंकि न्यूनतम प्रासंगिक दस्तावेज़ को श्रेणी में ऊपर रखा जाता है अर्थात्, अधिक प्रासंगिक दस्तावेज़ को न्यूनतम श्रेणी में रखकर अधिक छूट दी जाती है।


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


डीसीजी मूल्यों को सामान्य करने के लिए दी गई क्वेरी के लिए एक आइडियल क्रम की आवश्यकता होती है। इस उदाहरण के लिए, वह आदेश सभी ज्ञात प्रासंगिक निर्णयों का नीरस रूप से घटता क्रम होगा। इस प्रयोग से छः के अलावा, मान लीजिए कि हम यह भी जानते हैं कि एक दस्तावेज है <math>D_7</math> जिसकी प्रासंगिकता ग्रेड 3 है और एक दस्तावेज़ के लिए <math>D_8</math> उस क्वेरी के लिए प्रासंगिकता ग्रेड 2 हैं, तब आइडियल क्रम है:
डीसीजी मूल्यों को सामान्य करने के लिए दिए गए प्रश्न के लिए एक आइडियल क्रम की आवश्यकता होती है। इस उदाहरण के लिए, वह क्रम सभी ज्ञात प्रासंगिक निर्णयों का नीरस रूप से घटता क्रम होगा। इस प्रयोग से छः के अलावा, मान लीजिए कि हम यह भी जानते हैं कि एक दस्तावेज है <math>D_7</math> जिसकी प्रासंगिकता ग्रेड 3 है और दस्तावेज़ <math>D_8</math> उस प्रश्न के लिए प्रासंगिकता ग्रेड 2 हैं तब आइडियल क्रम है:
:<math> 3, 3, 3, 2, 2, 2, 1, 0 </math>
:<math> 3, 3, 3, 2, 2, 2, 1, 0 </math>
रैंकिंग के विश्लेषण की गहराई से मिलान करने के लिए आइडियल रैंकिंग को फिर से लंबाई 6 में काट दिया जाता है:
श्रेणी के विश्लेषण की गहराई से मिलान करने के लिए आइडियल श्रेणी        को फिर से लंबाई 6 में काट दिया जाता है:
:<math> 3, 3, 3, 2, 2, 2 </math>
:<math> 3, 3, 3, 2, 2, 2 </math>
इस आइडियल क्रम के DCG या IDCG (आइडियल DCG) की गणना 6 श्रेणी पर की जाती है:
इस आइडियल क्रम के DCG या IDCG (आइडियल DCG) की गणना 6 श्रेणी पर की जाती है:
Line 128: Line 128:


== सीमाएं ==
== सीमाएं ==
# सामान्यीकृत डीसीजी मीट्रिक परिणाम में खराब दस्तावेज़ों के लिए दंडित नहीं करता है। उदाहरण के लिए, यदि कोई क्वेरी क्रमशः {{math| 1,1,1 }} और {{math| 1,1,1,0 }} अंक के साथ दो परिणाम देती है तो दोनों को समान रूप से अच्छा माना जाएगा, भले ही बाद वाले में खराब दस्तावेज़ हो। उत्कृष्ट, उचित, खराब रैंकिंग निर्णयों के लिए 2,1,0 के बजाय संख्यात्मक अंक 1,0, -1 का उपयोग किया जा सकता है। यदि खराब परिणाम लौटाए जाते हैं तो इससे अंक कम हो जाएगा, प्रत्याह्वान पर परिणामों की सटीकता को प्राथमिकता दी जाएगी। ध्यान दें कि इस दृष्टिकोण के परिणामस्वरूप समग्र नकारात्मक अंक हो सकता है जो अंक की निचली सकता को {{math|0}} से नकारात्मक मान में बदल देगा।
# सामान्यीकृत डीसीजी मापीय परिणाम में खराब दस्तावेज़ों के लिए दंडित नहीं करता है। उदाहरण के लिए, यदि कोई प्रश्न क्रमशः {{math| 1,1,1 }} और {{math| 1,1,1,0 }} अंक के साथ दो परिणाम देती है तो दोनों को समान रूप से अच्छा माना जाएगा, भले ही बाद वाले में खराब दस्तावेज़ हो। उत्कृष्ट, उचित, खराब श्रेणी निर्णयों के लिए 2,1,0 के बजाय संख्यात्मक अंक 1,0, -1 का उपयोग किया जा सकता है। यदि खराब परिणाम लौटाए जाते हैं तो इससे अंक कम हो जाएगा, प्रत्याह्वान पर परिणामों की सटीकता को प्राथमिकता दी जाएगी। ध्यान दें कि इस दृष्टिकोण के परिणामस्वरूप समग्र नकारात्मक अंक हो सकता है जो अंक की निचली सकता को {{math|0}} से नकारात्मक मान में बदल देगा।
# सामान्यीकृत डीसीजी परिणाम में लापता दस्तावेजों के लिए दंडित नहीं करता है। उदाहरण के लिए, यदि कोई प्रश्न क्रमशः 1,1,1 और 1,1,1,1,1 अंक के साथ दो परिणाम देता है, तो दोनों को समान रूप से अच्छा माना जाएगा, यह मानते हुए कि आइडियल डीसीजी की गणना पूर्व के लिए श्रेणी 3 और बाद के लिए श्रेणी 5 पर की जाती है। इस सीमा को ध्यान में रखने का एक तरीका परिणाम संग्रह के लिए निश्चित संग्रह आकार को लागू करना और लापता दस्तावेज़ों के लिए न्यूनतम अंक का उपयोग करना है। पिछले उदाहरण में, हम अंक 1,1,1,0,0 और {{math| 1,1,1,1,1 }} का उपयोग करेंगे और nDCG को nDCG@5 के रूप में उद्धृत करें।<!-- Wouldn't 1,1,1 and 1,1,1,1,1 return different scores if you plug them into the provided formula, assuming a constant iDCG? Further, wouldn't adding extra 0's have no influence on the score, as per the previous point? -->
# सामान्यीकृत डीसीजी परिणाम में लापता दस्तावेजों के लिए दंडित नहीं करता है। उदाहरण के लिए, यदि कोई प्रश्न क्रमशः 1,1,1 और 1,1,1,1,1 अंक के साथ दो परिणाम देता है तो दोनों को समान रूप से अच्छा माना जाएगा, यह मानते हुए कि आइडियल डीसीजी की गणना पूर्व के लिए श्रेणी 3 और बाद के लिए श्रेणी 5 पर की जाती है। इस सीमा को ध्यान में रखने का एक तरीका परिणाम सेट के लिए निश्चित सेट आकार को लागू करना और लापता दस्तावेज़ों के लिए न्यूनतम अंक का उपयोग करना है। पिछले उदाहरण में अंक 1,1,1,0,0 और {{math| 1,1,1,1,1 }} का उपयोग करेंगे और nDCG को nDCG@5 के रूप में उद्धृत करें।<!-- Wouldn't 1,1,1 and 1,1,1,1,1 return different scores if you plug them into the provided formula, assuming a constant iDCG? Further, wouldn't adding extra 0's have no influence on the score, as per the previous point? -->
# सामान्यीकृत डीसीजी उन प्रश्नों के प्रदर्शन को मापने के लिए उपयुक्त नहीं हो सकता है जिनके ज्यादातर समान रूप से कई अच्छे परिणाम हो सकते हैं। यह विशेष रूप से सच है जब यह मीट्रिक केवल पहले कुछ परिणामों तक ही सीमित है जैसा कि व्यवहार में किया जाता है। उदाहरण के लिए "रेस्टोरेंट" जैसे प्रश्नों के लिए nDCG@1 केवल पहले परिणाम के लिए जिम्मेदार होगा इसलिए यदि एक परिणाम सेट में पास के क्षेत्र से केवल 1 रेस्टोरेंट सम्मिलित है जबकि दूसरे में 5 हैं, तो दोनों का अंक समान होगा भले ही उत्तरार्द्ध अधिक व्यापक है।
# सामान्यीकृत डीसीजी उन प्रश्नों के प्रदर्शन को मापने के लिए उपयुक्त नहीं हो सकता है जिनके ज्यादातर समान रूप से कई अच्छे परिणाम हो सकते हैं। यह विशेष रूप से सच है जब यह मापीय केवल पहले कुछ परिणामों तक ही सीमित है जैसा कि गतिविधि में किया जाता है। उदाहरण के लिए "रेस्टोरेंट" जैसे प्रश्नों के लिए nDCG@1 केवल पहले परिणाम के लिए जिम्मेदार होगा इसलिए यदि एक परिणाम सेट में पास के क्षेत्र से केवल 1 रेस्टोरेंट सम्मिलित है जबकि दूसरे में 5 हैं, तो दोनों का अंक समान होगा भले ही उत्तरार्द्ध अधिक व्यापक है।


== यह भी देखें ==
== यह भी देखें ==
Line 141: Line 141:
[[Category:Collapse templates]]
[[Category:Collapse templates]]
[[Category:Created On 21/03/2023]]
[[Category:Created On 21/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes| ]]
Line 149: Line 150:
[[Category:Sidebars with styles needing conversion]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]

Latest revision as of 17:35, 17 April 2023

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

सिंहावलोकन

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

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

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

संचयी लाभ

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

जहाँ स्थान पर परिणाम की श्रेणीबद्ध प्रासंगिकता है।

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

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

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

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

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

पहले लघुगणक कमी कारक का उपयोग करने के लिए सैद्धांतिक रूप से कोई ठोस औचित्य नहीं था[2]</nowiki> इस तथ्य के अलावा कि यह एक सहज कमी पैदा करता है, लेकिन वांग एट अल (2013)[3] ने सामान्यीकृत डीसीजी (एनडीसीजी) में लघुगणकीय कमी कारक का उपयोग करने के लिए सैद्धांतिक आश्वासन दिया। लेखक बताते हैं कि प्रत्येक जोड़ी के अलग-अलग श्रेणी कार्यों के लिए एनडीसीजी यह तय कर सकता है कि कौन सा सुसंगत तरीके से बेहतर है।

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

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

डीसीजी के ये दो सूत्रीकरण समान हैं जब दस्तावेजों के प्रासंगिक मूल्य द्विआधारी हैं [2]: 320  .

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


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

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

,

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

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

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

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

उदाहरण

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

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

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

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


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

इस श्रेणी का है:

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

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

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

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

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

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


सीमाएं

  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 हैं, तो दोनों का अंक समान होगा भले ही उत्तरार्द्ध अधिक व्यापक है।

यह भी देखें

संदर्भ

  1. Kalervo Järvelin, जाना Kekäläinen: IR तकनीकों का संचयी लाभ-आधारित मूल्यांकन। सूचना प्रणाली पर एसीएम लेनदेन 20(4), 422-446 (2002)
  2. 2.0 2.1 B. Croft; D. Metzler; T. Strohman (2010). Search Engines: Information Retrieval in Practice. Addison Wesley.<nowiki>
  3. Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Wei Chen, Tie-Yan Liu. 2013. A Theoretical Analysis of Normalized Discounted Cumulative Gain (NDCG) Ranking Measures. In Proceedings of the 26th Annual Conference on Learning Theory (COLT 2013).
  4. Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005. Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning (ICML '05). ACM, New York, NY, USA, 89-96. DOI=10.1145/1102351.1102363 http://doi.acm.org/10.1145/1102351.1102363
  5. "सूचना पुनर्प्राप्ति का परिचय - मूल्यांकन" (PDF). Stanford University. 21 April 2013. Retrieved 23 March 2014.