सामान्यीकृत Top-k Mallows मॉडल रैंक किए गए विकल्पों के लिए

मूल जानकारी

• पेपर ID: 2510.22040
• शीर्षक: Generalized Top-k Mallows Model for Ranked Choices
• लेखक: Shahrzad Haddadan (Rutgers Business School), Sara Ahmadian (Google Research)
• वर्गीकरण: cs.LG, cs.DS, stat.ML
• प्रकाशन सम्मेलन: NeurIPS 2025 (39वां तंत्रिका सूचना प्रसंस्करण प्रणाली सम्मेलन)
• पेपर लिंक: https://arxiv.org/abs/2510.22040

सारांश

शास्त्रीय Mallows मॉडल उपयोगकर्ता वरीयताओं को मॉडल करने के लिए एक मौलिक उपकरण है, लेकिन वास्तविक परिस्थितियों को पकड़ने में सीमाएं हैं—उपयोगकर्ता आमतौर पर केवल सीमित वरीयता वाली वस्तुओं के समूह पर ध्यान केंद्रित करते हैं, शेष वस्तुओं के प्रति उदासीन होते हैं। यह पेपर सामान्यीकृत top-k Mallows मॉडल की कई चुनौतियों पर अनुसंधान करता है, क्रेता विकल्प विश्लेषण पर ध्यान केंद्रित करता है। मुख्य योगदान में शामिल हैं: (1) सामान्यीकृत top-k Mallows मॉडल के लिए अनुकूलित नई सैंपलिंग योजना; (2) इस मॉडल के तहत विकल्प संभावनाओं की गणना के लिए कुशल एल्गोरिदम; (3) अवलोकन किए गए विकल्प डेटा से मॉडल पैरामीटर का अनुमान लगाने के लिए सक्रिय शिक्षण एल्गोरिदम। ये योगदान महत्वपूर्ण निर्णय परिस्थितियों में विश्लेषण और भविष्यवाणी के लिए नए उपकरण प्रदान करते हैं, और कठोर गणितीय विश्लेषण और व्यापक सिंथेटिक और वास्तविक डेटा प्रयोगों के माध्यम से विधि की स्केलेबिलिटी और सटीकता को सत्यापित किया गया है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

इस पेपर द्वारा हल की जाने वाली मुख्य समस्या है: जब उपयोगकर्ता पूर्ण रैंकिंग के बजाय आंशिक रैंकिंग जानकारी (top-k सूची) प्रदान करते हैं, तो वास्तविक परिस्थितियों में उपयोगकर्ता वरीयताओं को प्रभावी ढंग से कैसे मॉडल किया जाए और उनके विकल्प व्यवहार की भविष्यवाणी कैसे की जाए।

समस्या की महत्ता

1. व्यापक व्यावहारिक अनुप्रयोग: सिफारिश प्रणाली, विज्ञापन प्लेटफॉर्म, खोज इंजन, समाचार एकत्रकर्ता आदि परिस्थितियों में, उपयोगकर्ता आमतौर पर सीमित संख्या में वस्तुओं के लिए वरीयता व्यक्त करते हैं
2. व्यावसायिक निर्णय मूल्य: ग्राहक विकल्प व्यवहार की सटीक भविष्यवाणी राजस्व प्रबंधन, उत्पाद पोर्टफोलियो अनुकूलन आदि निर्णयों के लिए महत्वपूर्ण है
3. सैद्धांतिक महत्व: शास्त्रीय संभाव्य रैंकिंग मॉडल को अधिक यथार्थवादी आंशिक रैंकिंग परिस्थितियों तक विस्तारित करना

मौजूदा विधियों की सीमाएं

1. शास्त्रीय Mallows मॉडल: केवल पूर्ण क्रमपरिवर्तन तक सीमित, आंशिक रैंकिंग को संभाल नहीं सकता
2. Multinomial Logit (MNL) मॉडल: सरल होने के बावजूद सीमित अभिव्यक्ति क्षमता, असंबंधित विकल्पों की स्वतंत्रता (IIA) धारणा को संतुष्ट करता है, जटिल विकल्प व्यवहार के मॉडलिंग को सीमित करता है
3. मौजूदा top-k एक्सटेंशन: Chierichetti et al. (2018) द्वारा प्रस्तावित top-k Mallows मॉडल में कुशल सैंपलिंग एल्गोरिदम और विकल्प संभावना गणना विधियों की कमी है
4. पैरामीटर सीखने की कठिनाई: पूर्ण रैंकिंग के बजाय विकल्प डेटा से मॉडल पैरामीटर सीखने में सैद्धांतिक गारंटी की कमी है

अनुसंधान प्रेरणा

लेखकों का मानना है कि Mallows मॉडल को top-k सूचियों तक विस्तारित करना उपयोगकर्ता वरीयता संरचना को अधिक यथार्थवादी तरीके से प्रतिबिंबित कर सकता है, लेकिन तीन महत्वपूर्ण एल्गोरिदमिक समस्याओं को हल करने की आवश्यकता है: कुशल सैंपलिंग, विकल्प संभावना गणना और पैरामीटर सीखना।

मुख्य योगदान

इस पेपर के मुख्य योगदान में शामिल हैं:

1. PRIM सैंपलिंग एल्गोरिदम: Profile-based Repeated Insertion Method (PRIM) प्रस्तावित करता है, TopKGMM वितरण से कुशल सैंपलिंग को सक्षम करता है, समय जटिलता को O(k²4^k + k²log n) से O(k2^k + k²log n) तक कम करता है
2. DYPCHIP विकल्प संभावना एल्गोरिदम: Dynamic Programming for Choice Probabilities (DYPCHIP) एल्गोरिदम डिज़ाइन करता है, जो top-k Mallows मॉडल के तहत विकल्प संभावनाओं की कुशलतापूर्वक गणना कर सकता है
3. BUCCHOI सक्रिय शिक्षण एल्गोरिदम: Build Center from Choices (BUCCHOI) सक्रिय शिक्षण एल्गोरिदम विकसित करता है, निर्दिष्ट आकार के उत्पाद संयोजन प्रस्तुत करके और विकल्प देखकर, वितरण केंद्र और केंद्र आकार k का अनुमान लगाता है, नमूना जटिलता Θ(r²log n) है
4. मॉडल सामान्यीकरण: Chierichetti et al. के top-k Mallows मॉडल को सामान्यीकृत संस्करण (TopKGMM) तक विस्तारित करता है, प्रत्येक उत्पाद के लिए वजन जोड़ता है
5. अनुभवजन्य सत्यापन: Sushi वरीयता डेटासेट पर साबित करता है कि top-k Mallows मॉडल MNL मॉडल की तुलना में काफी अधिक भविष्यवाणी सटीकता प्रदान करता है

विधि विवरण

कार्य परिभाषा

इनपुट:

• उत्पाद समूह N = n ∪ {∅} (n उत्पाद और "खरीद न करें" विकल्प सहित)
• उत्पाद संयोजन (assortment) A ⊆ n

आउटपुट:

• उपयोगकर्ता द्वारा संयोजन A से उत्पाद i चुने जाने की संभावना C_D(i, A)

मॉडल धारणाएं:

• उपयोगकर्ता वरीयता TopKGMM वितरण का पालन करती है
• उपयोगकर्ता विकल्प फ़ंक्शन: C_τ(A) = i यदि और केवल यदि i, τ के सापेक्ष A∪{∅} में सर्वोच्च रैंक वाला तत्व है

मॉडल आर्किटेक्चर

1. TopKGMM वितरण परिभाषा

केंद्र τ* ∈ T_{k,N} और पैरामीटर β ≥ 0, w ∈ R^{k+1}_{≥0}, p > 0 दिए गए, top-k सूची τ की संभावना है:

P_D[τ] ∝ exp(-β K_{p,w}(τ, τ*))

जहां दूरी माप को परिभाषित किया गया है:

K_{p,w}(τ, τ*) = w_0·p·Q(τ) + Σ_{i∈[k]} w_i·(I_i(τ) + p·P_i(τ))

मुख्य घटक:

• I_i(τ) (व्युत्क्रम वेक्टर): i से कम प्राथमिकता वाले लेकिन τ में अधिक रैंक वाले तत्वों की संख्या
• P_i(τ): मूल रूप से i से कम रैंक वाले लेकिन τ में तुलनीय नहीं तत्वों की संख्या
• Q(τ): τ* में अनुक्रमित तत्वों के बीच तुलनीय नहीं जोड़ी की संख्या
• w_i: तत्व वजन, विभिन्न तत्वों को विभिन्न महत्व की अनुमति देता है

2. Profile अवधारणा

Profile परिभाषा: S ⊆ k नमूना top-k सूची τ और केंद्र τ* के प्रतिच्छेदन को दर्शाता है, अर्थात् τ ∩ τ* = S

Profile संभावना (Lemma 3.3):

P_D[S] ∝ exp(-βf(S))·Z(S)

जहां:

f(S) = w_0·p·Q(S) + Σ_{j∈[k]\S} w_j(I_j(S) + p·P_j(S))

Z(S) = C(n-k, k-ℓ)·(k-ℓ)! · Π_{j=1}^ℓ Σ_{r=0}^{k-j} e^{-βw_{s_j}r}

यह अपघटन एल्गोरिदम डिज़ाइन का मुख्य नवाचार है, जटिल top-k सूची वितरण को profile चयन और सशर्त रैंकिंग के दो चरणों में विघटित करता है।

तकनीकी नवाचार बिंदु

1. PRIM सैंपलिंग एल्गोरिदम (Algorithm 3-5)

मुख्य विचार:

1. पहले P_DS के अनुसार profile S का नमूना लेता है
2. फिर S दिए गए, पुनरावृत्त सम्मिलन विधि के माध्यम से τ का निर्माण करता है

एल्गोरिदम प्रवाह:

1. सभी profile की संभावनाओं को पूर्वगणना करें (O(2^γk) समय, γ=min{k,n-k})
2. Profile S का नमूना लें
3. आरंभीकरण: [n]\[k] से समान रूप से यादृच्छिक रूप से k-ℓ तत्वों का नमूना लें
4. प्राथमिकता क्रम में S में तत्वों s को सम्मिलित करें, स्थिति j पर s सम्मिलित करने की संभावना:
   P(स्थिति j पर s सम्मिलित करें) ∝ exp(-βw_s·j)

नवाचार बिंदु:

• Chierichetti et al. द्वारा छोड़ी गई खुली समस्या को हल करता है (RIM जैसी सैंपलिंग विधि की कमी)
• Profile अपघटन के माध्यम से जटिलता में काफी कमी
• प्रीप्रोसेसिंग के बाद प्रत्येक नमूने की परिशोधित लागत केवल O(k log n) है

2. DYPCHIP विकल्प संभावना एल्गोरिदम (Section 4.1)

मुख्य विचार: गतिशील प्रोग्रामिंग के माध्यम से, दिए गए profile S के तहत विकल्प संभावना की गणना करता है

एल्गोरिदम संरचना:

• त्रि-आयामी DP तालिका π_S(i, j, q):
  • i: उत्पाद संयोजन A में i-वां तत्व
  • j: वर्तमान स्थिति
  • q: PRIM एल्गोरिदम का q-वां पुनरावृत्ति
  • अर्थ: q-वें पुनरावृत्ति के बाद, a_i A∅ में सर्वोच्च रैंक वाला और स्थिति j पर होने की संभावना

पुनरावृत्ति संबंध:

जब नया तत्व A में नहीं है:
π_S(i,j,q) = π_S(i,j,q-1)·P(सम्मिलित>j) + π_S(i,j-1,q-1)·P(सम्मिलित≤j-1)

जब नया तत्व A में है:
π_S(i,j,q) = π_S(i,j,q-1)·P(सम्मिलित>j)
π_S(cur,j,q) = P(सम्मिलित=j)·Σ_{i<cur}Σ_{j'≥j}π_S(i,j',q-1)

अंतिम विकल्प संभावना:

C_D(a,A) = Σ_{S⊆[k]} P_D[S]·(π_S(a) + π̄_S(a))

जटिलता: O(2^{min{k,n-k}}·k³·|A|²)

3. BUCCHOI सक्रिय शिक्षण एल्गोरिदम (Algorithm 2)

मुख्य विचार: उत्पाद संयोजन को सक्रिय रूप से चुनकर और विकल्प देखकर केंद्र τ* सीखता है

मुख्य उप-एल्गोरिदम FINDTOP (Algorithm 1):

• मैट्रिक्स X_ बनाए रखता है: उत्पाद i के चुने जाने और j के न चुने जाने की बार संख्या का अंतर
• निर्णय मानदंड: Y_ = X_/m, यदि कोई a मौजूद है जैसे कि Y_{aa'} > (1+|A|)/2 सभी a'∈A∅{a} के लिए, तो a शीर्ष तत्व है

सैद्धांतिक गारंटी (Lemma 5.2):

• जब β ≥ log(3)/w_ हो
• Θ(ζ(r+1)²log n) नमूनों का उपयोग करके
• संभावना कम से कम 1-o(n^{-ζ}) के साथ शीर्ष तत्व की सही पहचान करता है

BUCCHOI प्रवाह:

1. तीन समूह बनाए रखता है: T (τ* में निश्चित), B (τ̄* में निश्चित), U (अज्ञात)
2. दोहराता है: आकार r का संयोजन A चुनता है, FINDTOP को कॉल करता है
3. यदि शीर्ष तत्व मिलता है, T में स्थानांतरित करता है; अन्यथा पूरा A को B में स्थानांतरित करता है
4. अंत में T में तत्वों को क्रमबद्ध करने के लिए SORTCNTR को कॉल करता है

नमूना जटिलता: Θ(r²log n)

प्रयोग सेटअप

डेटासेट

1. Sushi वरीयता डेटासेट (वास्तविक डेटा)

• स्रोत: Kamishima et al. (2005)
• स्केल: 5000 उपयोगकर्ता वरीयताएं, प्रत्येक top-10 सूची के रूप में
• उत्पाद संख्या: 100 विभिन्न सुशी प्रकार
• विभाजन: 80% प्रशिक्षण समूह, 20% परीक्षण समूह
• उद्देश्य: मॉडल भविष्यवाणी क्षमता और MNL के साथ तुलना का मूल्यांकन

2. सिंथेटिक डेटा

• पैरामीटर श्रेणी:
  • n (उत्पाद संख्या): 200-20000
  • k (top-k आकार): 6-16
  • β (क्षय पैरामीटर): 0.01-5
  • p (Kendall's Tau पैरामीटर): 0.01-5
  • r (संयोजन आकार): k के अनुसार समायोजित
• उद्देश्य: एल्गोरिदम सटीकता और जटिलता का मूल्यांकन, सैद्धांतिक परिणामों का सत्यापन

मूल्यांकन मेट्रिक्स

1. भविष्यवाणी सटीकता

• परीक्षण त्रुटि: अनुभवजन्य विकल्प संभावना और भविष्यवाणी संभावना के बीच पूर्ण त्रुटि
• गणना विधि: परीक्षण समूह पर यादृच्छिक रूप से संयोजन नमूना लें, वास्तविक विकल्प रिकॉर्ड करें, DYPCHIP भविष्यवाणी के साथ तुलना करें

2. सीखने की सटीकता

• Kendall's Tau दूरी: सीखे गए केंद्र और वास्तविक केंद्र के बीच दूरी K_p(τ_learned, τ_true)
• FINDTOP सटीकता: शीर्ष तत्वों की सही पहचान की आवृत्ति

3. समय जटिलता

• PRIM: प्रीप्रोसेसिंग समय और प्रत्येक नमूने की परिशोधित समय
• DYPCHIP: सभी विकल्प संभावनाओं की गणना का कुल समय
• सीखने का एल्गोरिदम: निर्दिष्ट सटीकता तक पहुंचने के लिए आवश्यक नमूनों की संख्या

तुलना विधियां

1. Multinomial Logit (MNL): शास्त्रीय विकल्प मॉडल baseline
2. Chierichetti et al. का DP सैंपलिंग: पिछली top-k Mallows सैंपलिंग विधि
3. क्लस्टरिंग के बिना vs के साथ: एकल TopKGMM vs मिश्रित TopKGMM (2-5 क्लस्टर)

कार्यान्वयन विवरण

Sushi डेटासेट प्रयोग

• पैरामीटर ट्यूनिंग: ग्रिड खोज β∈{0.01,0.025,0.05,...,5}, p∈{0.05,0.1,...,2}
• क्लस्टरिंग विधि: K_p दूरी के आधार पर k-means, क्लस्टर संख्या ∈{2,3,5}
• सिल्हूट गुणांक: क्लस्टरिंग गुणवत्ता का मूल्यांकन करने के लिए
• केंद्र सीखना: top-10 सूची नमूनों को संभालने के लिए BUCCHOI-II (Algorithm 7) का उपयोग

सिंथेटिक डेटा प्रयोग

• दोहराव संख्या: प्रत्येक पैरामीटर समूह के लिए 10 बार चलाएं
• नमूना संख्या श्रेणी: 50-250 (कार्य के अनुसार समायोजित)
• वजन सेटिंग: w=2⃗1 या w=32222111 आदि
• कंप्यूटिंग वातावरण: MacBook Pro M1 Max, 32GB RAM

प्रयोग परिणाम

मुख्य परिणाम

1. TopKGMM vs MNL (वास्तविक डेटा)

क्लस्टरिंग के बिना (Table 1):

• सर्वोत्तम पैरामीटर: β=0.05, p=0.5
• TopKGMM परीक्षण त्रुटि: 0.0817
• MNL परीक्षण त्रुटि: 0.168
• सापेक्ष सुधार: 51.4% त्रुटि में कमी

मुख्य निष्कर्ष:

• छोटे β (0.01-0.1) पर बेहतर प्रदर्शन, अपेक्षाकृत समान वितरण दर्शाता है
• p=0.5 पर सर्वोत्तम प्रभाव, विभिन्न प्रकार की असंगतियों को संतुलित करता है
• TopKGMM MNL से काफी बेहतर, मॉडल अभिव्यक्ति क्षमता को सत्यापित करता है

क्लस्टरिंग के साथ (Table 2, 2 क्लस्टर):

• p=0.1, β=0.1: परीक्षण त्रुटि 0.0771
• p=1.25, β=0.05: परीक्षण त्रुटि 0.0788
• अवलोकन: क्लस्टरिंग के बाद प्रदर्शन में मामूली सुधार, लेकिन सिल्हूट गुणांक बहुत कम (<0.012), डेटा एकल वितरण से आ सकता है

2. DYPCHIP सटीकता (Figure 2a)

प्रयोग सेटअप: n=200, k=6, r=4, p=0.5, w=2⃗1

• PRIM का उपयोग करके नमूने उत्पन्न करें, अनुभवजन्य विकल्प आवृत्ति की गणना करें
• DYPCHIP भविष्यवाणी के साथ तुलना करें
• 20 यादृच्छिक संयोजनों पर दोहराएं

परिणाम:

• औसत पूर्ण त्रुटि <0.02
• मानक विचलन बहुत छोटा, भविष्यवाणी स्थिरता दर्शाता है
• DYPCHIP की सही्ता को सत्यापित करता है

3. PRIM समय जटिलता (Table 3)

प्रीप्रोसेसिंग समय (सेकंड):

प्रत्येक नमूने की परिशोधित समय (सेकंड):

अवलोकन:

• प्रीप्रोसेसिंग समय k के साथ घातीय रूप से बढ़ता है (O(k2^k) सिद्धांत के अनुरूप)
• परिशोधित समय बहुत छोटा, बड़े पैमाने पर सैंपलिंग कुशल
• n का प्रभाव बहुत छोटा (O(k log n) जटिलता को सत्यापित करता है)

4. DYPCHIP समय जटिलता (Figure 3)

प्रयोग पैरामीटर: β=0.6, p=0.5, w=2⃗1, r=k-2

• k=6 पर: लगभग 0.05 सेकंड
• k=8 पर: लगभग 0.5 सेकंड
• k=10 पर: लगभग 5 सेकंड
• k=12 पर: लगभग 50 सेकंड

अवलोकन:

• समय k के साथ घातीय रूप से बढ़ता है
• n का प्रभाव अपेक्षाकृत छोटा
• k>12 पर गणना लागत काफी बढ़ जाती है, व्यावहारिक अनुप्रयोग को सीमित करती है

विलोपन प्रयोग

1. FINDTOP नमूना जटिलता (Figure 2b, Figure 4)

पैरामीटर प्रभाव:

• β का प्रभाव (n=900, k=10, r=5, p=1):
  • β=0.2: 80% सटीकता तक पहुंचने के लिए 200+ नमूने आवश्यक
  • β=0.6: 95% सटीकता तक पहुंचने के लिए 100 नमूने आवश्यक
  • β=1.2: 100% सटीकता तक पहुंचने के लिए 50 नमूने आवश्यक
  • निष्कर्ष: β जितना बड़ा, वितरण उतना ही केंद्रित, सीखना उतना ही आसान
• k का प्रभाव:
  • k=12 vs k=14 (अन्य पैरामीटर समान): k जितना बड़ा, अधिक नमूने आवश्यक
  • O(r²log n) जटिलता के अनुरूप
• r का प्रभाव:
  • r=5 vs r=10: r जितना बड़ा, प्रत्येक अवलोकन से अधिक जानकारी, लेकिन शोर भी बढ़ता है

2. BUCCHOI नमूना जटिलता (Figure 2c-d, Figure 5)

प्रयोग 1 (n=500, k=10, p=0.5, w=2⃗1):

• 50 नमूने: Kendall's Tau दूरी ≈12
• 100 नमूने: दूरी ≈3
• 200 नमूने: दूरी ≈0 (पूर्ण पुनरुद्धार)

प्रयोग 2 (n=300, k=8, p=2, w=32222111):

• गैर-समान वजन सीखने की कठिनाई बढ़ाता है
• समान सटीकता तक पहुंचने के लिए अधिक नमूने आवश्यक
• लेकिन अभी भी Θ(r²log n) श्रेणी में

β का प्रभाव (Table 5, n=1000, k=12):

अवलोकन:

• β≥1 पर, 100 नमूने केंद्र को पूरी तरह से पुनः प्राप्त करने के लिए पर्याप्त
• β=0.4 पर 100 नमूनों के साथ भी त्रुटि बनी रहती है
• सैद्धांतिक आवश्यकता β≥log(3)/w_ को सत्यापित करता है

केस विश्लेषण

Sushi डेटासेट क्लस्टरिंग विश्लेषण

सकारात्मक सिल्हूट गुणांक वाली क्लस्टरिंग:

• p=0.1, 2 क्लस्टर: सिल्हूट गुणांक=0.0063
• p=1.25, 2 क्लस्टर: सिल्हूट गुणांक=0.0078
• p=5, 2 क्लस्टर: सिल्हूट गुणांक=0.0110
• p=5, 3 क्लस्टर: सिल्हूट गुणांक=0.0023

व्याख्या:

• अत्यंत कम सिल्हूट गुणांक क्लस्टर के भीतर बड़ी विविधता दर्शाता है
• एकल TopKGMM अधिक उपयुक्त हो सकता है
• यह क्लस्टरिंग के बिना कम त्रुटि के साथ सुसंगत है

प्रयोग निष्कर्ष

1. मॉडल अभिव्यक्ति क्षमता: TopKGMM वास्तविक डेटा पर MNL से काफी बेहतर, त्रुटि 50% से अधिक कम
2. एल्गोरिदम दक्षता:
   • PRIM प्रीप्रोसेसिंग के बाद सैंपलिंग कुशल
   • DYPCHIP k<12 के मामलों के लिए व्यावहारिक
   • सीखने का एल्गोरिदम लॉगरिदमिक स्तर की नमूना जटिलता
3. पैरामीटर संवेदनशीलता:
   • β महत्वपूर्ण पैरामीटर, वितरण केंद्रीकरण और सीखने की कठिनाई को प्रभावित करता है
   • p को डेटा विशेषताओं के अनुसार ट्यून करने की आवश्यकता
   • वजन गैर-समानता सीखने की जटिलता बढ़ाती है
4. सैद्धांतिक सत्यापन: प्रयोग परिणाम सैद्धांतिक जटिलता विश्लेषण के साथ अत्यधिक सुसंगत

संबंधित कार्य

1. विकल्प मॉडलिंग (Choice Modeling)

Multinomial Logit (MNL):

• Bradley & Terry (1952) द्वारा प्रस्तावित
• लाभ: सरल, व्याख्यायोग्य, IIA को संतुष्ट करता है
• नुकसान: सीमित अभिव्यक्ति क्षमता

मिश्रित MNL:

• McFadden & Train (2000) द्वारा विस्तारित
• सीखने की विधि: EM एल्गोरिदम (Dempster et al. 1977)
• सैद्धांतिक गारंटी: Chierichetti et al. (2018b), Oh & Shah (2014)

अन्य ढांचे:

• Mallows विकल्प मॉडल (Désir et al. 2021)
• मार्कोव श्रृंखला मॉडल (Blanchet et al. 2016)

2. Mallows मॉडल

शास्त्रीय Mallows मॉडल:

• Mallows (1957) मूल परिभाषा
• Kendall's Tau दूरी के आधार पर क्रमपरिवर्तन वितरण
• सामान्यीकरण स्थिरांक का बंद रूप समाधान

top-k एक्सटेंशन:

• Fligner & Verducci (1986), Lebanon & Mao (2008) प्रारंभिक कार्य
• Chierichetti et al. (2018a) TopKMM प्रस्तावित
• समस्या: बंद रूप सामान्यीकरण स्थिरांक और कुशल सैंपलिंग की कमी

सामान्यीकृत Mallows मॉडल:

• Fligner & Verducci (1986) वजन परिचय
• यह पेपर पहली बार top-k सूचियों तक विस्तारित करता है

3. Mallows मॉडल के विकल्प अनुप्रयोग

Désir et al. का कार्य:

• Désir et al. (2021) पहली बार Mallows का उपयोग विकल्प मॉडलिंग के लिए
• MNL की तुलना में बेहतर भविष्यवाणी साबित
• पूर्ण क्रमपरिवर्तन के लिए विकल्प संभावना DP एल्गोरिदम विकसित

बाद का अनुसंधान:

• राजस्व प्रबंधन और उत्पाद पोर्टफोलियो अनुकूलन (Désir et al. 2021, 2023; Feng & Tang 2022)
• सरलीकृत मॉडल (Feng & Tang 2022)

इस पेपर का योगदान: top-k सूचियों तक विस्तार, पूर्ण एल्गोरिदम उपकरण श्रृंखला प्रदान

4. पैरामीटर सीखना

पूर्ण क्रमपरिवर्तन से सीखना:

• Liu & Moitra (2018), Braverman & Mossel (2008)
• Awasthi et al. (2014), Seshadri et al. (2020)

आंशिक अवलोकन से सीखना:

• युग्मित तुलना (Lu & Boutilier 2014; Vitelli et al. 2018)
• विकल्प से सीखना: कम अनुसंधान, सैद्धांतिक गारंटी की कमी

इस पेपर का योगदान:

• विकल्प डेटा से top-k Mallows सीखने का पहला सक्रिय शिक्षण एल्गोरिदम
• सीमित नमूना जटिलता गारंटी Θ(r²log n) प्रदान

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. सैद्धांतिक योगदान:
   • सामान्यीकृत top-k Mallows मॉडल (TopKGMM) प्रस्तावित
   • Profile अपघटन के माध्यम से कुशल एल्गोरिदम डिज़ाइन
   • कठोर गणितीय विश्लेषण और जटिलता गारंटी प्रदान
2. एल्गोरिदम योगदान:
   • PRIM: O(k2^k + k²log n) सैंपलिंग एल्गोरिदम
   • DYPCHIP: O(2^{min{k,n-k}}k³|A|²) विकल्प संभावना एल्गोरिदम
   • BUCCHOI: Θ(r²log n) नमूना जटिलता की सक्रिय शिक्षण एल्गोरिदम
3. अनुभवजन्य योगदान:
   • वास्तविक डेटा पर TopKGMM की MNL से श्रेष्ठता सत्यापित (51% त्रुटि कमी)
   • एल्गोरिदम की सटीकता और दक्षता सत्यापित
   • पैरामीटर ट्यूनिंग मार्गदर्शन प्रदान

सीमाएं

1. कंप्यूटिंग जटिलता:
   • DYPCHIP का k पर घातीय निर्भरता बड़े k परिस्थितियों को सीमित करता है (k>15)
   • PRIM प्रीप्रोसेसिंग समय k के साथ घातीय रूप से बढ़ता है
   • व्यावहारिक अनुप्रयोग में k अपेक्षाकृत छोटा होना चाहिए
2. सैद्धांतिक धारणाएं:
   • BUCCHOI को β≥log(3)/w_ की आवश्यकता, कम β परिस्थितियों को सीमित करता है
   • ∅∉τ* की धारणा, अन्यथा केवल आंशिक केंद्र पुनः प्राप्त कर सकता है
3. मॉडल धारणाएं:
   • एकल TopKGMM बहु-प्रकार के उपयोगकर्ताओं को पकड़ने के लिए अपर्याप्त हो सकता है
   • मिश्रित मॉडल का पैरामीटर सीखना अभी भी खुली समस्या है
4. प्रयोग श्रेणी:
   • केवल एक वास्तविक डेटासेट पर सत्यापित
   • अधिक डोमेन के अनुप्रयोग सत्यापन की आवश्यकता

भविष्य की दिशाएं

1. मिश्रित TopKGMM सीखना:
   • विकल्प डेटा से कई ग्राहक प्रकार सीखना
   • मिश्रित MNL सीखने के एल्गोरिदम के समान
2. कंप्यूटिंग जटिलता कम करना:
   • k के घातीय निर्भरता को कम करने के लिए अनुमानित एल्गोरिदम
   • वितरित या समानांतर कंप्यूटिंग
3. मॉडल विस्तार:
   • संदर्भ जानकारी पर विचार (contextual Mallows)
   • गतिशील वरीयता मॉडलिंग
4. व्यावहारिक अनुप्रयोग:
   • राजस्व प्रबंधन और मूल्य निर्धारण
   • सिफारिश प्रणाली अनुकूलन
   • A/B परीक्षण डिज़ाइन

गहन मूल्यांकन

शक्तियां

1. सैद्धांतिक कठोरता:
   • सभी एल्गोरिदम के पास कठोर सही्ता प्रमाण हैं
   • जटिलता विश्लेषण पूर्ण (Theorems 3.1, 4.1, 5.1)
   • नमूना जटिलता में संभाव्य गारंटी
2. विधि नवाचार:
   • Profile अपघटन मुख्य नवाचार, जटिल वितरण को आसानी से संभालने योग्य भागों में विघटित करता है
   • Chierichetti et al. की खुली समस्या को हल करता है
   • पहली बार top-k Mallows के विकल्प संभावना गणना को लागू करता है
3. प्रयोग पूर्णता:
   • सिंथेटिक डेटा पैरामीटर स्पेस को व्यापक रूप से कवर करता है
   • वास्तविक डेटा व्यावहारिक प्रभाव सत्यापित करता है
   • विलोपन प्रयोग प्रत्येक पैरामीटर प्रभाव विश्लेषण करता है
   • कोड सार्वजनिक, पुनरुत्पादनीय
4. व्यावहारिक मूल्य:
   • वास्तविक डेटा पर MNL से काफी बेहतर
   • एल्गोरिदम उचित पैरामीटर श्रेणी में कुशल
   • पूर्ण उपकरण श्रृंखला (सैंपलिंग-अनुमान-सीखना) प्रदान
5. लेखन स्पष्टता:
   • संरचना स्पष्ट, तर्क कठोर
   • गणितीय प्रतीक परिभाषा सटीक
   • एल्गोरिदम छद्मकोड विस्तृत (परिशिष्ट)

कमियां

1. कंप्यूटिंग स्केलेबिलिटी:
   • k का घातीय निर्भरता मौलिक सीमा है
   • k>15 परिस्थितियों के लिए अव्यावहारिक
   • अनुमानित एल्गोरिदम चर्चा की कमी
2. प्रयोग सीमाएं:
   • केवल एक वास्तविक डेटासेट: Sushi डेटासेट सभी अनुप्रयोग परिस्थितियों का प्रतिनिधित्व नहीं कर सकता
   • अन्य top-k विकल्प मॉडल के साथ तुलना नहीं (जैसे top-k MNL वेरिएंट)
   • बड़े पैमाने पर डेटासेट प्रयोग की कमी
3. मॉडल धारणाएं:
   • ∅∉τ* की धारणा अनुप्रयोग श्रेणी को सीमित करती है
   • एकल वितरण धारणा क्लस्टरिंग प्रभाव स्पष्ट न होने पर अनुपयुक्त हो सकती है
   • मॉडल गलत निर्दिष्टता की मजबूती पर चर्चा की कमी
4. पैरामीटर चयन:
   • β और p का चयन ग्रिड खोज पर निर्भर
   • स्वचालित पैरामीटर चयन विधि की कमी
   • वजन w की सेटिंग मार्गदर्शन की कमी
5. सैद्धांतिक-व्यावहारिक अंतराल:
   • BUCCHOI की सैद्धांतिक आवश्यकता β≥log(3)/w_≈1.1, लेकिन प्रयोग में β=0.05 भी प्रभावी
   • सैद्धांतिक जटिलता सबसे खराब स्थिति है, व्यावहारिक बेहतर हो सकता है

प्रभाव

1. शैक्षणिक योगदान:
   • top-k Mallows विकल्प मॉडलिंग में रिक्तता भरता है
   • बाद के अनुसंधान के लिए आधार एल्गोरिदम प्रदान
   • अधिक Mallows-आधारित विकल्प मॉडल अनुसंधान को प्रेरित कर सकता है
2. व्यावहारिक मूल्य:
   • सिफारिश प्रणाली: top-k सिफारिशों के लिए उपयोगकर्ता वरीयता मॉडलिंग
   • ई-कॉमर्स: उत्पाद पोर्टफोलियो अनुकूलन
   • खोज इंजन: उपयोगकर्ता क्लिक व्यवहार समझना
3. पुनरुत्पादनीयता:
   • कोड सार्वजनिक: https://github.com/ShahrzadGit/topkmallows-choices
   • सार्वजनिक डेटासेट का उपयोग
   • एल्गोरिदम छद्मकोड विस्तृत
4. प्रभाव पर सीमाओं का प्रभाव:
   • k की सीमा बड़े पैमाने पर अनुप्रयोगों में अपनाने में बाधा डाल सकती है
   • व्यापक अनुप्रयोग के लिए अधिक वास्तविक डेटासेट सत्यापन की आवश्यकता

लागू परिस्थितियां

अत्यधिक लागू:

1. छोटे से मध्यम k की सिफारिश प्रणाली (k≤12):
   • शीर्ष-10 उत्पाद प्रदर्शित करें और उपयोगकर्ता विकल्प की भविष्यवाणी करें
   • समाचार सिफारिश, वीडियो सिफारिश
2. उत्पाद पोर्टफोलियो अनुकूलन:
   • खुदरा विक्रेता कौन से उत्पाद प्रदर्शित करें यह चुनता है
   • मेनू डिज़ाइन
3. A/B परीक्षण:
   • विभिन्न उत्पाद संयोजनों के आकर्षण की तुलना
   • सक्रिय शिक्षण एल्गोरिदम परीक्षण नमूने कम कर सकता है

सावधानीपूर्वक उपयोग:

1. बड़े k परिस्थितियां (k>15): कंप्यूटिंग लागत अधिक
2. वास्तविक समय प्रणाली: DYPCHIP गणना समय विलंबता आवश्यकता को पूरा नहीं कर सकता
3. चरम गैर-समान वजन: सीखने की जटिलता बढ़ता है

अनुपयुक्त:

1. पूर्ण क्रमपरिवर्तन ज्ञात: शास्त्रीय Mallows मॉडल का उपयोग करें
2. उपयोगकर्ता वरीयता पूरी तरह यादृच्छिक: MNL अधिक सरल प्रभावी हो सकता है
3. व्याख्यायोग्यता की आवश्यकता: Mallows मॉडल की पैरामीटर व्याख्या MNL जितनी अच्छी नहीं

संदर्भ (मुख्य साहित्य)

1. Mallows (1957): मूल Mallows मॉडल
2. Chierichetti et al. (2018a): Top-k Mallows मॉडल आधार
3. Désir et al. (2021, 2023): Mallows विकल्प मॉडल अग्रणी कार्य
4. Bradley & Terry (1952): MNL मॉडल आधार
5. McFadden & Train (2000): मिश्रित MNL मॉडल
6. Fligner & Verducci (1986): सामान्यीकृत Mallows मॉडल

सारांश

यह पेपर top-k Mallows मॉडल और विकल्प मॉडलिंग के क्रॉस-डोमेन में महत्वपूर्ण योगदान देता है। चतुर profile अपघटन के माध्यम से, लेखकों ने एक पूर्ण एल्गोरिदम उपकरण श्रृंखला डिज़ाइन की है और कठोर सैद्धांतिक विश्लेषण प्रदान किया है। प्रयोग विधि की प्रभावशीलता को सत्यापित करते हैं, विशेष रूप से वास्तविक डेटा पर MNL की तुलना में महत्वपूर्ण लाभ।

मुख्य मूल्य में शामिल हैं: (1) सैद्धांतिक रूप से महत्वपूर्ण खुली समस्या को हल करना; (2) व्यावहारिक रूप से उपयोगी उपकरण प्रदान करना; (3) भविष्य के अनुसंधान के लिए आधार स्थापित करना।

मुख्य सीमा k पर घातीय निर्भरता है, जो बड़े k परिस्थितियों में अनुप्रयोग को सीमित करती है। भविष्य के अनुसंधान में मिश्रित मॉडल सीखना और अनुमानित एल्गोरिदम विकसित करना इस विधि की व्यावहारिकता को और बढ़ाएगा।

आंशिक क्रमपरिवर्तन वरीयता मॉडल करने और विकल्प व्यवहार की भविष्यवाणी करने की आवश्यकता वाले अनुप्रयोगों के लिए, यह पेपर द्वारा प्रदान किया गया TopKGMM ढांचा और एल्गोरिदम मूल्यवान उपकरण हैं, विशेष रूप से k छोटे (≤12) और उच्च भविष्यवाणी सटीकता की आवश्यकता वाली परिस्थितियों में।