Hierarchical Partial-Order Models for Ranking

तकनीकी सारांश: रैंकिंग के लिए पदानुक्रमित आंशिक-क्रम मॉडल (Hierarchical Partial-Order Models for Ranking)

समस्या विवरण

रैंक एकत्रीकरण (Rank aggregation) विविध स्रोतों से प्राप्त क्रमबद्ध सूचियों को एक सर्वसम्मत संरचना में संयोजित करने का लक्ष्य रखता है। शास्त्रीय पैरामीट्रिक मॉडल, जैसे कि मलोस (Mallows) और प्लैकेट-लूस (Plackett–Luce), यह मानते हैं कि प्राथमिकताएँ एक या अधिक पूर्ण सर्वसम्मत रैंकिंग (पूर्ण क्रम/total orders) के इर्द-गिर्द केंद्रित होती हैं। हालाँकि, कई अनुप्रयोगों में, यह धारणा कि वास्तविक प्राथमिकता संरचना एक पूर्ण क्रम (total order) है, अनुचित है; मूल्यांकनकर्ता कुछ वस्तुओं को तुलनीय नहीं (incomparable) मान सकते हैं। इसके अतिरिक्त, प्राथमिकता डेटा अक्सर समूह संरचनाओं (जैसे, विभिन्न मूल्यांकनकर्ता, विशिष्ट परिदृश्य, या समय-श्रृंखला खंड) को प्रदर्शित करता है, जिन्हें मौजूदा मॉडल आंशिक-क्रम संरचनाओं को संरक्षित करते हुए समायोजित करने में संघर्ष करते हैं।

जबकि हालिया कार्यों ने आंशिक क्रमों (posets) की अनुमति देने के लिए पूर्ण-क्रम की धारणा को शिथिल किया है, और अन्य कार्यों ने पूर्ण क्रमों के लिए पदानुक्रमित विस्तार पेश किए हैं, पदानुक्रमित समूहीकरण (hierarchical grouping) को आंशिक-क्रम सर्वसम्मति के साथ संयोजित करने वाले एक एकीकृत ढांचे की कमी है। आंशिक क्रमों के लिए मौजूदा पदानुक्रमित मॉडल (जैसे, Arcagni et al., 2022) जेनेरेटिव बेयस अनुमान (generative Bayesian inference) के बजाय लॉस-आधारित पॉइंट अनुमानों पर निर्भर करते हैं।

कार्यप्रणाली (Methodology)

यह शोध पत्र Hierarchical Partial-Order (HPO) मॉडल और उनके अनसुपरवाइज्ड क्लस्टरिंग विस्तार (HCPO) को प्रस्तुत करता है।

1. HPO ढांचा (The HPO Framework)

HPO मॉडल को लेबल किए गए समूहों (जैसे, $A$ मूल्यांकनकर्ता) से आने वाले रैंक-ऑर्डर डेटा के लिए डिज़ाइन किया गया है। इसे एक वृक्ष (tree) के रूप में संरचित किया गया है जहाँ रूट नोड एक "वैश्विक" (global) आंशिक क्रम को दर्शाता है और लीफ नोड्स मूल्यांकनकर्ता-विशिष्ट आंशिक क्रमों को दर्शाते हैं।

• अव्यक्त चर निर्माण (Latent Variable Construction): मॉडल निरंतर अव्यक्त चरों (continuous latent variables) का उपयोग करके आंशिक क्रमों को पैरामीट्रिक बनाता है। विकल्पों के ब्रह्मांड में प्रत्येक वस्तु $j$ के लिए, प्राथमिकता भार का एक वेक्टर $U_j \in \mathbb{R}^K$ होता है। एक आंशिक क्रम इन भारों से प्राप्त $K$ पूर्ण क्रमों के प्रतिच्छेदन (intersection) द्वारा बनता है।
• जेनेरेटिव प्रक्रिया (Generative Process):
  • वैश्विक स्तर (Global Level): एक वैश्विक अव्यक्त भार मैट्रिक्स $U^{(0)}$ को $\rho$ द्वारा नियंत्रित सहसंबंध संरचना के साथ एक मल्टीवेरिएट नॉर्मल वितरण से खींचा जाता है।
  • स्थानीय स्तर (Local Level): प्रत्येक मूल्यांकनकर्ता $a$ के लिए, अव्यक्त भार $U^{(a)}$ को $U^{(0)}$ पर सशर्त रूप से एक मल्टीवेरिएट नॉर्मल वितरण के माध्यम से $\tau$ सहसंबंध पैरामीटर के साथ खींचा जाता है। यह पैरामीटर $\tau \in (0, 1]$ वैश्विक पोसेट (poset) की ओर मूल्यांकनकर्ता-विशिष्ट पोसेट्स के "श्रिंकेज" (shrinkage) को नियंत्रित करता है।
  • पोसेट्स में मैपिंग (Mapping to Posets): प्राथमिकता स्कोर $\eta$ उत्पन्न करने के लिए अव्यक्त भारों को गम्बल निर्माण (Gumbel construction) के माध्यम से रूपांतरित किया जाता है (नॉर्मल CDF पर गम्बल के इनवर्स CDF का उपयोग करके)। आंशिक क्रम $h^{(a)}$ इन स्कोरों से प्राप्त क्रमों के प्रतिच्छेदन द्वारा परिभाषित होता है।
• अवलोकन मॉडल (Observation Models): यह पेपर एक पोसेट $h$ दिए जाने पर रैंकिंग $y$ को देखने के लिए तीन संभावनाओं (likelihoods) का प्रस्ताव करता है:
  1. शोर-मुक्त (Noise-free): रैखिक विस्तार (linear extensions) से यूनिफॉर्म सैंपलिंग (बड़े $M$ के लिए गणनात्मक रूप से महंगा)।
  2. क्यू-जम्पिंग (Queue-jumping): एक दोहरा चयन मॉडल जहाँ, प्रायिकता $p$ के साथ, एक वस्तु को यादृच्छिक रूप से चुना जाता है (शोर), और अन्यथा पोसेट बाधाओं के आधार पर चुना जाता है।
  3. वेटेड क्यू-जम्पिंग (Weighted Queue-jumping): एक विस्तार जहाँ यादृच्छिक चयन $\eta$ द्वारा भारित होते हैं, जिससे बड़े अंतराल वाली वस्तुओं के लिए त्रुटियां कम होने की संभावना होती है।
  4. फ्रंटियर-सॉफ्टमैक्स (Frontier-softmax): एक यूटिलिटी-आधारित मॉडल जहाँ वस्तुओं को शेष उप-क्रम के "फ्रंटियर" (अधिकतम तत्व) से चुना जाता है, जो उनके द्वारा डोमिनेट की गई वस्तुओं की संख्या द्वारा भारित होता है। यह गणनात्मक रूप से कुशल ($O(M)$ प्रति चरण) है और बड़े डेटासेट के लिए उपयुक्त है।

2. HCPO ढांचा (The HCPO Framework)

जब समूह लेबल अज्ञात होते हैं, तो यह पेपर HPO को Hierarchical Clustering Partial-Order (HCPO) मॉडल में विस्तारित करता है।

• क्लस्टरिंग (Clustering): सूचियों (या मूल्यांकनकर्ताओं) के $G$ गुप्त समूहों में विभाजन पर पिटमैन-योर प्रोसेस प्रायर (Pitman-Yor process prior) रखा जाता है।
• अनुमान (Inference): समूहों की संख्या $G$ और क्लस्टर असाइनमेंट का अनुमान पोसेट पदानुक्रम के साथ संयुक्त रूप से MCMC का उपयोग करके लगाया जाता है।
• मूल्यांकता बनाम सूची क्लस्टरिंग (Assessor vs. List Clustering): मॉडल व्यक्तिगत सूचियों को क्लस्टर कर सकता है या पूरे मूल्यांकनकर्ताओं को (सभी सूचियों को एक साथ ले जाकर)।

3. बेयसियन अनुमान (Bayesian Inference)

अनुमान MCMC का उपयोग करके किया जाता है। पोस्टीरियर वितरण सहसंबंध मापदंडों ($\rho, \tau$), अव्यक्त भार मैट्रिक्स ($U$), रिग्रेशन गुणांक ($\beta$), और विभाजन ($C$) पर होता है। अव्यक्त स्थान का आयाम $K$ भी रिवर्सिबल जंप MCMC का उपयोग करके निकाला जा सकता है।

मुख्य योगदान (Key Contributions)

1. HPO और HCPO मॉडल: वर्गीकृत रैंक डेटा के लिए एक जेनेरेटिव बेयस फ्रेमवर्क का परिचय जो स्पष्ट रूप से आंशिक-क्रम सर्वसम्मति संरचनाओं को मॉडल करता है, जो प्लैकेट-लूस मॉडल को पोसेट डोमेन तक विस्तारित करता है।
2. सैद्धांतिक गुण (Theoretical Properties):
   • यह प्रमाण कि प्लैकेट-लूस मॉडल और उनके पदानुक्रमित संस्करण HPO के विशेष मामले हैं (जब $K=1$ हो)।
   • यह प्रदर्शन कि मॉडल मार्जिनली कंसिस्टेंट (marginally consistent) है, जो सुनिश्चित करता है कि उप-क्रमों पर प्रायर, पूर्ण ब्रह्मांड पर प्रायर के साथ सुसंगत है।
   • यह प्रमाण कि मॉडल किसी भी पदानुक्रमित पोसेट का प्रतिनिधित्व कर सकता है यदि $K \ge \lfloor M/2 \rfloor$ हो।
3. नवीन अवलोकन मॉडल: वेटेड क्यू-जम्पिंग और फ्रंटियर-सॉफ्टमैक्स संभावनाओं का विकास, जो जेनेरेटिव व्याख्या बनाए रखते हुए शोर और गणनात्मक दक्षता की अनुमति देते हैं।
4. अनसुपरवाइज्ड क्लस्टरिंग: अज्ञात रैंक डेटा में गुप्त समूह संरचनाओं और क्लस्टर-विशिष्ट पोसेट्स को खोजने के लिए HCPO के रूप में विस्तार।

प्रयोगात्मक परिणाम (Experimental Results)

पेपर सिंथेटिक और वास्तविक दुनिया के डेटासेट पर मॉडलों का मूल्यांकन करता है:

• सिंथेटिक डेटा (HPO): लेबल किए गए समूहों वाले सेटिंग्स में, HPO सफलतापूर्वक गुप्त पदानुक्रमित पोसेट्स को रिकवर करता है। रिकवरी सटीकता मुख्य रूप से देखी गई सूचियों की लंबाई (चॉइस सेट आकार) और कपलिंग स्ट्रेंथ ($\tau$) द्वारा संचालित होती है। फ्रंटियर-सॉफ्टमैक्स संभावना, सटीक रैखिक-विस्तार विधियों की तुलना में महत्वपूर्ण गणनात्मक गति प्रदान करती है (जो $M \ge 50$ के लिए टाइम आउट हो जाती है)।
• सिंथेटिक डेटा (HCPO): अनलेबल सेटिंग्स में, HCPO दोनों गुप्त क्लस्टरिंग संरचना और क्लस्टर-विशिष्ट पोसेट्स को सटीक रूप से रिकवर करता है। क्लस्टरिंग का लाभ तब सबसे अधिक होता है जब समूहों के बीच कपलिंग कमजोर (उच्च विषमता) होती है।
• क्लाउड प्रोविजनिंग ट्रेसेस (LLM एजेंट्स): LLM एजेंटों (Aliyun Cloud-IaC-6) के निष्पादन ट्रेसेस पर लागू किया गया। HPO मॉडल ने, विभिन्न परिदृश्यों को समूहों के रूप में मानते हुए, अंतर्निहित डिपेंडेंसी ग्राफ (वर्कफ़्लो संरचनाओं) को रिकवर करने में स्वतंत्र सिंगल-पोसेट बेसलाइन से बेहतर प्रदर्शन किया। पदानुक्रमित पूलिंग ने प्रीसीडेंस बाधाओं (precedence constraints) की रिकवरी में सुधार किया, विशेष रूप से स्पार्स डेटा वाले परिदृश्यों में।
• मानव प्राथमिकता डेटा (3D साउंड): युग्म-आधारित (pairwise) ध्वनिक प्राथमिकता डेटा पर लागू किया गया जहाँ श्रोताओं ने चक्रीय पैटर्न प्रदर्शित किए (जो टोटल ऑर्डर का उल्लंघन करते हैं)। HCPO मॉडल ने प्रेडिक्टिव फिट (WAIC) में टोटल-ऑर्डर बेसलाइन्स (Plackett–Luce और Mallows मिश्रण) की तुलना में काफी बेहतर प्रदर्शन किया। महत्वपूर्ण रूप से, HCPO सारांशों ने व्याख्या योग्य संरचनाओं को प्रकट किया जहाँ क्लस्टर्स में तुलनीय वस्तुओं की एक विस्तृत "टॉप लेयर" थी, एक ऐसी विशेषता जिसे टोटल-ऑर्डर मॉडल बिना मनमाने सख्त रैंकिंग को थोपे बिना प्रदर्शित नहीं कर सकते थे।

महत्व और दावे (Significance and Claims)

पेपर दावा करता है कि प्रस्तावित HPO और HCPO फ्रेमवर्क वर्गीकृत रैंक डेटा को संभालने के लिए एक सिद्धांतपूर्ण तरीका प्रदान करते हैं जहाँ प्राथमिकताएँ अपूर्ण या तुलनीय नहीं हो सकती हैं।

• संरचनात्मक व्याख्यात्मकता (Structural Interpretability): ये मॉडल आंशिक-क्रम संरचनाओं को रिकवर करने की अनुमति देते हैं जो वास्तविक अतुलनीयता (incomparabilities) को दर्शाते हैं, जिससे उन आर्टिफैक्ट्स से बचा जा सकता है जो डेटा को पूर्ण क्रम में जबरदस्ती फिट करने से उत्पन्न होते हैं।
• सूचना साझाकरण (Information Sharing): पदानुक्रमित संरचना समूहों के बीच सिद्धांतपूर्ण सूचना साझाकरण (shrinkage) को सक्षम करती है, जिससे कम-डेटा वाले परिदृश्यों में अनुमान में सुधार होता है जबकि समूह-विशिष्ट बारीकियों को सुरक्षित रखा जाता है।
• गणना की व्यवहार्यता (Computational Feasibility): फ्रंटियर-सॉफ्टमैक्स संभावना इन मॉडलों को बड़े आइटम सेट पर लागू करने में सक्षम बनाती है जहाँ सटीक रैखिक-विस्तार गणना कठिन है।
• व्यापकता (Generality): फ्रेमवर्क मौजूदा पदानुक्रमित प्लैकेट-लूस मॉडलों को समाहित करता है और उन्हें आंशिक-क्रम डोमेन तक विस्तारित करता है, जो लेबल किए गए और अनलेबल वर्गीकृत रैंकिंग डेटा के लिए एक एकीकृत दृष्टिकोण प्रदान करता है।

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