Proportionally Representative Clustering

तकनीकी सारांश: आनुपातिक रूप से प्रतिनिधि क्लस्टरिंग (Proportionally Representative Clustering)

समस्या विवरण
यह शोध पत्र सेंट्रॉइड क्लस्टरिंग (centroid clustering) में निष्पक्षता की समस्या को संबोधित करता है, जो अनसुपरवाइज्ड मशीन लर्निंग का एक मौलिक कार्य है जहाँ लक्ष्य $n$ डेटा बिंदुओं (एजेंटों) के एक सेट के लिए $k$ केंद्रों (सेंट्रॉइड्स) के एक उपसमुच्चय का चयन करना है। जबकि मानक उद्देश्य जैसे $k$-means, $k$-medians, और $k$-center वैश्विक कल्याण (global welfare) को अनुकूलित करते हैं, वे अक्सर आनुपातिक प्रतिनिधित्व निष्पक्षता (proportional representational fairness) को पकड़ने में विफल रहते हैं। क्लस्टरिंग में मौजूदा निष्पक्षता अवधारणाएं, जैसे कि प्रोपोर्शनल फेयरनेस (PF) और कोर फेयरनेस (Core Fairness), की सीमाएं हैं: वे प्रत्येक इंस्टेंस के लिए प्राप्त करने योग्य नहीं हो सकती हैं, और वे एक न्यूनतम सहज आवश्यकता को पूरा करने में विफल रहती हैं जिसे "सर्वसम्मत आनुपातिकता" (unanimous proportionality) कहा जाता है (जहाँ एक ही स्थान पर स्थित एजेंटों के समूह को उनके आकार के अनुपात में केंद्रों की संख्या पाने का अधिकार होता है)। मौजूदा निष्पक्ष क्लस्टरिंग एल्गोरिदम अक्सर पूर्व-निर्धारित संरक्षित गुणों (protected attributes) पर निर्भर करते हैं, जबकि यह कार्य उन निष्पक्षता गुणों की खोज करता है जो डेटा वितरण द्वारा अंतर्जात (endogenously) रूप से निर्धारित समूहों पर लागू होते हैं।

कार्यप्रणाली
लेखक एक स्वयंसिद्ध दृष्टिकोण (axiomatic approach) अपनाते हैं, और एक नई निष्पक्षता अवधारणा प्रस्तावित करते हैं जिसे प्रोपोर्शनल रिप्रेजेंटेटिव फेयरनेस (PRF) कहा जाता है। यह अवधारणा अनियंत्रित (continuous) और असतत (discrete) क्लस्टरिंग सेटिंग्स दोनों के लिए डिज़ाइन की गई है।

1. स्वयंसिद्ध परिभाषा (PRF):

   • अनियंत्रित सेटिंग (Unconstrained Setting): एक परिणाम $X$ तब PRF को संतुष्ट करता है यदि, $\ell n/k$ आकार के किसी भी एजेंट सेट $S$ के लिए, जिसकी अधिकतम युग्म दूरी (pairwise distance) $y$ है, $X$ में कम से कम $\ell$ केंद्र $S$ के कम से कम एक एजेंट की दूरी $y$ के भीतर हों।
   • असतत सेटिंग (Discrete Setting): परिभाषा को उम्मीदवार सेट $M$ की खुरदरापन (coarseness) को ध्यान में रखते हुए अनुकूलित किया गया है। यदि $S$ के सभी एजेंटों (जहाँ $|S| \ge \ell n/k$) की दूरी $y$ के भीतर $M$ में $\ell'$ उम्मीदवार हैं, तो परिणाम में कम से कम $\ell'$ केंद्र $S$ के किसी एजेंट की दूरी $y$ के भीतर होने चाहिए।

2. एल्गोरिदम डिज़ाइन (SEAR):
   लेखक SEAR (स्पेशियल एक्सपैंडिंग अप्रूवल रूल) पेश करते हैं, जो मल्टी-विनर वोटिंग से प्रेरित 'एक्सपैंडिंग अप्रूवल्स रूल' (EAR) का एक रूपांतर है, जिसे स्थानिक डेटा (spatial data) के लिए अनुकूलित किया गया है।

   • तंत्र (Mechanism): एल्गोरिदम एजेंटों और उम्मीदवारों के बीच क्रमबद्ध दूरियों के आधार पर पड़ोस की त्रिज्याओं (neighborhood radii) का विस्तार करता है। एजेंटों को प्रारंभिक भार (weights) दिए जाते हैं। जब एक उम्मीदवार केंद्र चुना जाता है जो एजेंटों के ऐसे समूह को कवर करता है जिसका कुल भार $n/k$ से अधिक है, तो उस केंद्र को समाधान में जोड़ा जाता है, और कवर किए गए एजेंटों के भार को $n/k$ से कम कर दिया जाता है।
   • कार्यान्वयन (Implementation):
     • एल्गोरिदम 1 (Unconstrained): उम्मीदवारों को एजेंटों के स्थानों तक सीमित किया गया है। यह $O(n^2 \log n + kn^2)$ में चलता है।
     • एल्गोरिदम 2 (Discrete): उम्मीदवार एक परिमित सेट $M$ से लिए जाते हैं। यह $O(|M|n \log n + k|M|n)$ में चलता है।

प्रमुख योगदान और परिणाम

• PRF की उपस्थिति और गुण: यह शोध पत्र सिद्ध करता है कि अनियंत्रित और असतत दोनों सेटिंग्स में एक PRF परिणाम का अस्तित्व सुनिश्चित है। PRF कई वांछनीय गुणों को संतुष्ट करता है: यह सर्वसम्मत आनुपातिकता को निहित करता है, आउटलेर्स (outliers) के प्रति सुदृढ़ है, स्केल-इनवेरिएंट है, और इसके लिए पूर्व-निर्धारित संरक्षित समूहों की आवश्यकता नहीं होती है।
• प्रोपोर्शनल फेयरनेस (PF) का सन्निकटन (Approximation):
  • अनियंत्रित सेटिंग: अनियंत्रित सेटिंग के लिए SEAR एल्गोरिदम प्रोपोर्शनल फेयरनेस का 3-अनुमान (3-approximation) प्रदान करता है। यह सामान्य मीट्रिक स्पेस में PF के लिए ज्ञात पहला बहुपद-समय (polynomial-time) सन्निकटन एल्गोरिदम है। शोध पत्र PF के संबंध में PRF परिणामों के सामान्य अस्तित्व के लिए $\frac{3+\sqrt{17}}{2} \approx 3.56$ का एक कड़ा (tight) बाउंड भी स्थापित करता है।
  • असतत सेटिंग: असतत सेटिंग के लिए SEAR एल्गोरिदम PF के लिए $(1+\sqrt{2})$-अनुमान प्रदान करता है, जो कि असतत सेटिंग में PF के लिए सर्वोत्तम ज्ञात सन्निकटन कारक से मेल खाता है, साथ ही यह अधिक मजबूत PRF स्वयंसिद्ध को भी संतुष्ट करता है।
• असंभवता के परिणाम (Impossibility Results):
  • शोध पत्र प्रदर्शित करता है कि मानक क्लस्टरिंग एल्गोरिदम ($k$-means, $k$-median, $k$-center) और पिछले निष्पक्ष क्लस्टरिंग एल्गोरिदम (जैसे ग्रीडी कैप्चर) PRF को संतुष्ट नहीं करते हैं।
  • रणनीति-सिद्धता (Strategyproofness): लेखक PRF और स्ट्रैटेजीप्रूफनेस के बीच एक असंगति सिद्ध करते हैं। विशेष रूप से, ऐसा कोई एल्गोरिदम नहीं है जो ऑर्डर-सांख्यिकी स्ट्रैटेजीप्रूफ (order-statistic strategyproof) हो और साथ ही PRF को संतुष्ट करता हो, यहाँ तक कि असतत सेटिंग में $k=2$ के लिए भी। इसे अप्रूवल-आधारित कमेटी वोटिंग से रिडक्शन के माध्यम से दिखाया गया है, जो PRF को प्रोपोर्शनल जस्टिफाइड रिप्रेजेंटेशन (PJR) स्वयंसिद्ध से जोड़ता है, जो स्ट्रैटेजीप्रूफनेस के साथ असंगत है।

महत्व
शोध पत्र तीन प्राथमिक क्षेत्रों में महत्व का दावा करता है:

1. वैचारिक प्रगति: यह PRF को एक सुदृढ़, स्वयंसिद्ध निष्पक्षता अवधारणा के रूप में पेश करता है जो मौजूदा प्रोपोर्शनल फेयरनेस परिभाषाओं की कमियों को दूर करती है, विशेष रूप से सर्वसम्मत आनुपातिकता को सुनिश्चित करने में विफलता को।
2. एल्गोरिद्मिक सफलता: यह सामान्य मीट्रिक स्पेस में प्रोपोर्शनल फेयरनेस (अनियंत्रित सेटिंग) के लिए पहला बहुपद-समय सन्निकटन एल्गोरिदम प्रदान करता है और अधिक मजबूत PRF स्वयंसिद्ध को संतुष्ट करते हुए असतत सेटिंग के लिए सर्वोत्तम-ज्ञात सीमाओं से मेल खाता है।
3. सैद्धांतिक सीमाएँ: यह निष्पक्षता (विशेष रूप से PRF) और प्रोत्साहन अनुकूलता (स्ट्रैटेजीप्रूफनेस) के बीच ट्रेड-ऑफ को कठोरता से स्थापित करता है, यह दिखाते हुए कि प्रोपोर्शनल रिप्रेजेंटेशन स्वयंसिद्धों को संतुष्ट करना स्वाभाविक रूप से सेंट्रॉइड चयन में हेरफेर को रोकने के साथ संघर्ष करता है।

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