💻 computer science

PhaseWin: An Efficient Search Algorithm for Faithful Visual Attribution

PhaseWin एक कुशल सबसेट-सर्च एल्गोरिदम है जो निष्ठावान विजुअल एट्रिब्यूशन (faithful visual attribution) के लिए ग्रीडी सिलेक्शन को एक फेज़्ड विंडो-सर्च प्रक्रिया में पुनर्गठित करता है ताकि विभिन्न विजन कार्यों में उच्च निष्ठा बनाए रखते हुए कम्प्यूटेशनल जटिलता को द्विघात $O(n^2)$ से घटाकर रैखिक $O(n)$ किया जा सके।

मूल लेखक: Zihan Gu, Ruoyu Chen, Junchi Zhang, Li Liu, Xiaochun Cao, Hua Zhang

प्रकाशित 2026-06-17

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Zihan Gu, Ruoyu Chen, Junchi Zhang, Li Liu, Xiaochun Cao, Hua Zhang

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास एक बहुत ही बुद्धिमान लेकिन रहस्यमय रोबोट (एक AI मॉडल) है जो एक तस्वीर को देखता है और एक निर्णय लेता है, जैसे कि यह कहना, "यह एक बिल्ली है," या एक वाक्य लिखना जैसे, "एक कुत्ता गेंद का पीछा कर रहा है।"

समस्या यह है कि रोबोट आपको यह नहीं बताता कि उसने वह चुनाव क्यों किया। वह बस आपको उत्तर दे देता है। विजुअल एट्रिब्यूशन (Visual attribution) वह उपकरण है जिसका उपयोग हम रोबट से यह पूछने के लिए करते हैं: "किस हिस्से की वजह से तुमने यह कहा?"

पुराना तरीका: थकाऊ जासूस (The Exhaustive Detective)

पारंपरिक रूप से, उत्तर खोजने के लिए शोधकर्ताओं ने ग्रीडी सर्च (Greedy Search) नामक एक विधि का उपयोग किया। कल्पना कीजिए कि आप एक कमरे में 100 वस्तुओं के बीच सबसे महत्वपूर्ण सुराग खोजने की कोशिश कर रहे हैं एक जासूस के रूप में।

चरण 1: आप हर एक वस्तु को एक-एक करके उठाते हैं और रोबोट से पूछते हैं, "यदि मैं तुम्हें केवल यह वस्तु दिखाऊं, तो क्या वह अभी भी इसे बिल्ली समझेगा?" आप यह सभी 100 वस्तुओं के लिए करते हैं।
चरण 2: आप सबसे अच्छी वस्तु चुनते हैं। अब, आपके पास 99 वस्तुएं बची हैं। आपको यह देखने के लिए फिर से सभी 99 का परीक्षण करना होगा कि अगली सबसे महत्वपूर्ण वस्तु कौन सी है।
चरण 3: आप दूसरी सबसे अच्छी वस्तु चुनते हैं। अब आप शेष 98 का परीक्षण करते हैं।

यह एक टीम के सर्वश्रेष्ठ खिलाड़ी को खोजने के लिए हर एक खिलाड़ी से एक चक्कर लगाने को कहने जैसा है, फिर शेष खिलाड़ियों से फिर से चक्कर लगाने को कहना, और फिर से। यह सत्य खोजने के लिए पूरी तरह से काम करता है, लेकिन इसमें बहुत लंबा समय लगता है। यदि आपके पास 1,000 क्षेत्र (regions) हैं, तो आपको लाखों प्रश्न पूछने पड़ सकते हैं। यह वही है जिसे पेपर में "क्वाड्रेटिक कॉस्ट" ( $O(n^2)$ ) कहा गया है—यह बहुत तेज़ी से धीमा होता जाता है।

नया तरीका: फेज़विन (PhaseWin - द स्मार्ट स्काउट)

इस पेपर के लेखक, फेज़विन (PhaseWin) कहते हैं, "हमें हर बार हर किसी का परीक्षण करने की आवश्यकता नहीं है।" वे बिना सटीकता खोए महत्वपूर्ण सुराग खोजने का एक स्मार्ट और तेज़ तरीका प्रस्तावित करते हैं।

फेज़विन को एक स्मार्ट स्काउट (Smart Scout) के रूप में सोचें जो "फेज़्ड विंडो" (Phased Window) रणनीति का उपयोग करता है:

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

जादू: 100, फिर 99, फिर 98 का परीक्षण करने के बजाय... फेज़विन 100 का परीक्षण कर सकता है, फिर जल्दी से 20 तक फ़िल्टर कर सकता है, फिर उन 20 को एक छोटे समूह में परीक्षण कर सकता है, फिर 5 तक फ़िल्टर कर सकता है। यह खराब उम्मीदवारों के उबाऊ, दोहराव वाले परीक्षण को छोड़ देता है।

उन्होंने क्या सिद्ध किया?

पेपर तीन दावे करता है:

यह तेज़ है: उन्होंने गणितीय रूप से सिद्ध किया कि यह विधि बहुत तेज़ है। क्षेत्रों की संख्या के वर्ग (जैसे $100 \times 100$ ) के अनुपात में समय लेने के बजाय, इसमें केवल क्षेत्रों की संख्या (जैसे $100 \times 1$ ) के अनुपात में समय लगता है। यह एक विशाल गति वृद्धि है।
यह ईमानदार है (Faithful): आमतौर पर, जब आप किसी चीज़ को तेज़ करते हैं, तो आप सटीकता खो देते हैं। लेखकों ने सिद्ध किया कि फेज़विन "फिथफुल" (Faithful) रहता है। यह धीमी, व्यापक विधि की तरह ही महत्वपूर्ण क्षेत्रों को खोज लेता है, बस कम प्रश्नों के साथ। यह कोई "सस्ता नुस्खा" नहीं है; यह एक "स्मार्ट शॉर्टकट" है।
यह हर जगह काम करता है: उन्होंने इसे इन पर टेस्ट किया:
- इमेज क्लासिफिकेशन (क्या यह बिल्ली है या कुत्ता?)।
- ऑब्जेक्ट डिटेक्शन (बिल्ली कहाँ है?)।
- भाषा की समझ (चित्र का कौन सा हिस्सा "पीछा करने" शब्द से मेल खाता है?)।
- कैप्शन जनरेशन (AI ने "धूप वाला दिन" क्यों लिखा?)।

इन सभी परीक्षणों में, फेज़विन धीमी, पूर्ण विधि के लगभग बराबर था, लेकिन इसने कंप्यूटर की आधी से एक-तिहाई शक्ति का उपयोग किया।

मुख्य निष्कर्ष (The Bottom Line)

यदि पुराना तरीका एक पुस्तकालय में सबसे अच्छे वाक्य को खोजने के लिए हर एक किताब को पढ़ने जैसा है, तो फेज़विन एक ऐसे लाइब्रेरियन की तरह है जिसे पता है कि किस शेल्फ की जांच करनी है, किन किताबों को छोड़ना है, और केवल सबसे आशाजनक वाली किताबों के पहले कुछ पन्ने ही पढ़ने हैं। यह आपको वही उत्तर प्राप्त कराता है, लेकिन बहुत कम समय में।

पेपर निष्कर्ष निकालता है कि यह "फेज़-विंडो" दृष्टिकोण एक सामान्य समाधान है जो सत्यता से समझौता किए बिना बड़े, जटिल मॉडलों के लिए उच्च-गुणवत्ता वाले AI स्पष्टीकरणों को व्यावहारिक बनाता है।

तकनीकी सारांश: PhaseWin - एक कुशल दृश्य एट्रिब्यूशन के लिए खोज एल्गोरिदम

1. समस्या विवरण

विजुअल एट्रिब्यूशन (दृश्य एट्रिब्यूशन) का लक्ष्य यह समझाना है कि किसी मॉडल का निर्णय इनपुट छवि के स्थानीय क्षेत्रों पर कैसे निर्भर करता है। निष्ठावान (faithful) एट्रिब्यूशन विधियाँ अक्सर इसे एक क्रमित उपसमुच्चय-खोज समस्या (ordered subset-search problem) के रूप में देखती हैं: दिए गए $n$ उम्मीदवार क्षेत्रों में विभाजित एक छवि के लिए, एक ऐसा क्रम खोजने का लक्ष्य है जिससे प्रगतिशील रूप से शीर्ष-रैंक्ड क्षेत्रों को सम्मिलित करने पर लक्षित मॉडल प्रतिक्रिया यथाशीघ्र प्राप्त हो सके।

जबकि ग्रीडी सर्च (greedy search) विधियों (जैसे LIMA, VPS) ने पर्याप्तता-अनिवार्यता (sufficiency–necessity) प्रॉक्सी को अनुकूलित करके उच्च निष्ठा प्रदर्शित की है, वे दो मौलिक सीमाओं से ग्रस्त हैं:

सैद्धांतिक सीमा: विजुअल एट्रिब्यूशन में उपयोग किया जाने वाला मानक पर्याप्तता-अनिवार्यता प्रॉक्सी एक गैर-डिजेनरेट सबमॉड्यूलर फलन (non-degenerate submodular function) नहीं है। फलस्वरूप, शास्त्रीय सबमॉड्यूलर-ग्रीडी सन्निकटन गारंटी लागू नहीं होती हैं, जिससे ग्रीडी एट्रिब्यूशन का सैद्धांतिक औचित्य अधूरा रह जाता है।
गणनात्मक सीमा: मानक ग्रीडी सर्च प्रत्येक चयन चरण में ग्लोबल रीस्कोरिंग (global rescoring) की आवश्यकता होती है। एक क्षेत्र चुनने के बाद, अगले सर्वोत्तम क्षेत्र को निर्धारित करने के लिए शेष $n-1$ उम्मीदवारों का पुनर्मूल्यांकन करना पड़ता है। इसके परिणामस्वरूप $O(n^2)$ की द्विघाती मूल्यांकन जटिलता (quadratic evaluation complexity) होती है, जो बड़े विजन-लैंग्वेज मॉडल्स (VLMs), उच्च-रिज़ॉल्यूशन वाली छवियों, या सघन विभाजनों के लिए अत्यधिक महंगी हो जाती है।

यह शोध पत्र प्रस्तावित करता है कि मौजूदा समाधान एक ट्रेड-ऑफ का सामना करते हैं: विस्तृत खोज (exhaustive search) उच्च निष्ठा प्रदान करती है लेकिन गणनात्मक रूप से अव्यवहार्य है, जबकि तेज़ विकल्प अक्सर उस निष्ठा का त्याग कर देते हैं जो व्यवधान-आधारित (perturbation-based) एट्रिब्यूशन को उपयोगी बनाती है।

2. कार्यप्रणाली: PhaseWin

लेखक PhaseWin का प्रस्ताव करते हैं, जो एक फेज़्ड विंडो-सर्च (phased window-search) एल्गोरिदम है जिसे रैखिक मूल्यांकन जटिलता के साथ लगभग-ग्रीडी निष्ठा प्राप्त करने के लिए डिज़ाइन किया गया है।

2.1 सैद्धांतिक पुनर्गठन

सबमॉड्यूलरिटी पर भरोसा करने के बजाय, लेखक विजुअल एट्रिब्यूशन को क्रमित साक्ष्य संचय (ordered evidence accumulation) के रूप में पुनर्गठित करते हैं। वे स्पष्ट साक्ष्य-संचय स्थितियों के तहत पर्याप्तता-अनिवार्यता प्रॉक्सी का विश्लेषण करते हैं।

संरचनात्मक धारणा: खोज उद्देश्य $F(X)$ को छवि के "सिमेंटिक ब्लॉक्स" (विभाजन) पर एक मोनोटोन सबमॉड्यूलर फलन $\Phi$ और एक अवशेष पद (residual term) $R(X)$ के योग के रूप में मॉडल किया गया है।
मुख्य अंतर्दृष्टि: उद्देश्य में प्रमुख लाभ पहले से सक्रिय किए गए सिमेंटिक ब्लॉक्स को सक्रिय करने से आता है, जबकि पहले से सक्रिय ब्लॉक के भीतर अतिरिक्त तत्व केवल मामूली सुधार में योगदान देते हैं।

2.2 एल्गोरिदम वर्कफ़्लो

PhaseWin विस्तृत ग्लोबल रीस्कोरिंग के स्थान पर एक फेज़्ड कोर्स-टू-फाइन (phased coarse-to-fine) रणनीति का उपयोग करता है। एल्गोरिदम चरणों (phases) में कार्य करता है, प्रत्येक चरण में चार चरण होते हैं:

ग्लोबल एंकर चयन: एल्गोरिदम कैश किए गए लाभों (cached gains) की गणना करने के लिए वर्तमान उम्मीदवार पूल $R$ पर एक एकल वैश्विक स्कैन करता है। उच्चतम लाभ वाले उम्मीदवार को फेज़ एंकर ( $\alpha^\star$ ) के रूप में चुना जाता है, और इसका लाभ एक संदर्भ मान ( $\Delta_{ref}$ ) निर्धारित करता है।
अनुकूली छंटनी (Adaptive Pruning): $\Delta_{ref}$ $Δ_{r e f}$ से प्राप्त निश्चित-अनुपात थ्रेसहोल्ड का उपयोग करते हुए, एल्गोरिदम शेष उम्मीदवारों को तीन समूहों में विभाजित करता है:
- उच्च-क्षमता पूल ( $P$ ): वे उम्मीदवार जिनके लाभ एक चयन थ्रेसहोल्ड से ऊपर हैं।
- विलंबित सेट (Deferred set): मध्यम लाभ वाले उम्मीदवार, जिन्हें अगले चरण के लिए रखा जाता है।
- परित्याग सेट (Discarded set): कम लाभ वाले उम्मीदवार, जिन्हें पुनर्मूल्यांकन से बचने के लिए हटा दिया जाता है।
लोकल विंडो रिफाइनमेंट: पूरे पूल का पुनर्मूल्यांकन करने के बजाय, एल्गोरिदम उच्च-क्षमता वाले पूल $P$ पर ध्यान केंद्रित करता है। यह $P$ को उनके कैश किए गए लाभों द्वारा सॉर्ट करता है और शीर्ष $\omega$ उम्मीदवारों को एक स्लाइडिंग लोकल विंडो $W$ में रखता है। एक विशिष्ट विंडो नीति (जैसे, Local-Greedy, Beta-Adaptive) सटीक पुनर्मूल्यांकन के लिए इस विंडो के भीतर से उम्मीदवारों के एक उपसमुच्चय का चयन करती है।
स्वीकार करें या विलंबित करें: यदि विंडो से सर्वश्रेष्ठ उम्मीदवार एक फेज़-एग्जिट मानदंड को पूरा करता है, तो उसे स्वीकार किया जाता है; अन्यथा, स्थानीय अन्वेषण को प्रोत्साहित करने के लिए इसे विलंबित किया जा सकता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि लक्षित संख्या में क्षेत्र चयनित न हो जाएं या पूल समाप्त न हो जाए।

2.3 जटिलता और गारंटी

जटिलता: निश्चित फेज़ और विंडो सेटिंग्स के तहत, PhaseWin रैखिक मूल्यांकन जटिलता $O(n)$ प्राप्त करता है, जो मानक ग्रीडी सर्च की $O(n^2)$ की तुलना में एक महत्वपूर्ण कमी है।
सैद्धांतिक गारंटी: मोनोटोन साक्ष्य संचय और फीचर-स्तरीय घटते प्रतिफल (diminishing returns) की धारणाओं के तहत, लेखक सिद्ध करते हैं कि PhaseWin ग्रीडी सर्च के प्रमुख रैंकिंग व्यवहार को बनाए रखता है। वे लक्षित-कार्डिनैलिटी खोज और पूर्ण-क्रम प्रीफिक्स/AUC मेट्रिक्स दोनों के लिए लगभग-ग्रीडी निष्ठा गारंटी स्थापित करते हैं।

3. मुख्य योगदान

सैद्धांतिक आधार: यह शोध पत्र दर्शाता है कि मानक पर्याप्तता-अनिवार्यता प्रॉक्सी सबमॉड्यूलर नहीं है, जो शास्त्रीय सबमॉड्यूलर-ग्रीडी औचित्य को अमान्य करती है। यह क्रमित साक्ष्य संचय पर आधारित एक नया सैद्धांतिक ढांचा पेश करता है जो वर्गीकरण (classification), डिटेक्शन, ग्राउंडिंग और कैप्शनिंग पर समान रूप से लागू होता है।
PhaseWin एल्गोरिदम: एक नवीन खोज एल्गोरिदम जो द्विघाती ग्लोबल रीस्कोरिंग को एंकर चयन, अनुकूली छंटनी और स्थानीय विंडो रिफाइनमेंट वाले फेज़्ड स्ट्रैटेजी से बदल देता है। यह रैखिक मूल्यांकन जटिलता के साथ लगभग-ग्रीडी निष्ठा प्राप्त करने वाला पहला तरीका है।
व्यापक अनुभवजन्य सत्यापन: लेखक चार अलग-अलग कार्यों में PhaseWin का सत्यापन करते हैं:
- इमेज क्लासिफिकेशन (CLIP और ResNet के साथ ImageNet)।
- ऑब्जेक्ट डिटेक्शन और रेफरिंग एक्सप्रेशन कॉम्प्रिहेन्शन (Grounding DINO और Florence-2 के साथ MS COCO, LVIS, RefCOCO)।
- इमेज कैप्शनिंग (Qwen-2.5-VL)।
  परिणाम दर्शाते हैं कि PhaseWin लगातार गैर-ग्रीडी बेसलाइन्स से बेहतर प्रदर्शन करता है और बहुत कम मॉडल मूल्यांकनों के साथ ग्रीडी सर्च के करीब पहुँचता है।

4. प्रयोगात्मक परिणाम

शोध पत्र विभिन्न बैकबोन और कार्यों में ग्रेडिएंट-आधारित (जैसे, Grad-CAM), व्यवधान-आधारित (जैसे, RISE, HSIC), और मानक ग्रीडी सर्च बेसलाइन्स के विरुद्ध PhaseWin की तुलना करते हुए व्यापक प्रयोग रिपोर्ट करता है।

निष्ठा (Faithfulness): PhaseWin विभिन्न बैकबोन और कार्यों में विस्तृत ग्रीडी सर्च द्वारा प्राप्त Insertion AUC का 92–96% और औसत उच्चतम स्कोर (Average Highest score) का 96–98% सुरक्षित रखता है।
दक्षता (Efficiency): PhaseWin कार्य और मॉडल के आधार पर, ग्रीडी सर्च की तुलना में औसत मॉडल मूल्यांकन (MEC) को 1.73× से 29.0× के कारक से कम कर देता है।
- वर्गीकरण (Classification): ~1.91× गति वृद्धि।
- ऑब्जेक्ट डिटेक्शन/ग्राउंडिंग: 29× तक गति वृद्धि (उदाहरण के लिए, 100 क्षेत्रों के साथ Grounding DINO पर)।
- कैप्शनिंग (Captioning): ~2.8× गति वृद्धि।
ट्रेड-ऑफ: एक्यूरेसी-कॉस्ट (A-C) अनुपात काफी बेहतर होता है, जो यह दर्शाता है कि PhaseWin स्पष्टीकरण की गुणवत्ता और गणनात्मक लागत के बीच एक बेहतर संतुलन प्रदान करता है।
विफलता विश्लेषण: नैदानिक सेटिंग्स (जैसे, गलत वर्गीकृत छवियां या अनडिटेक्टेड ऑब्जेक्ट्स) में, PhaseWin उच्च निष्ठा बनाए रखता है जहाँ अन्य विधियाँ विफल रहती हैं, जो मॉडल व्यवहार की जांच (debugging) के लिए इसकी उपयोगिता को सिद्ध करता है।

5. महत्व और दावे

शोध पत्र का दावा है कि PhaseWin केवल एक हीयूरिस्टिक (heuristic) त्वरण नहीं है, बल्कि द्विघाती से रैखिक-जटिलता एट्रिब्यूशन की ओर एक वैधता-संरक्षण मार्ग (validity-preserving route) है।

सामान्यीकरण (Generalizability): यह विधि किसी विशिष्ट मॉडल आर्किटेक्चर, डेटासेट या स्कोरिंग फंक्शन तक सीमित नहीं है। यह भेदभावपूर्ण (classification, detection) और जनरेटिव (captioning) कार्यों के लिए उच्च-निष्ठा विजुअल एट्रिब्यूशन हेतु एक सामान्य त्वरण रणनीति के रूप में कार्य करती है।
व्यावहारिक प्रभाव: गणनात्मक बाधा को कम करके, PhaseWin बड़े पैमाने के मॉडल्स और उच्च-रिज़ॉल्यूशन इनपुट के लिए विस्तृत-शैली के निष्ठावान एट्रिब्यूशन को संभव बनाता है, जिससे आधुनिक विजन और विजन-लैंग्वेज सिस्टमों का अधिक कठोर ऑडिटिंग और डायग्नोसिस सक्षम होता है।
मामूली दावे: लेखक स्वीकार करते हैं कि हालांकि PhaseWin अत्यधिक प्रभावी है, "रैंकिंग-अस्थिर" (ranking-unstable) मामलों (जैसे वर्गीकरण के लगभग 13% नमूने) में ग्रीडी सर्च के साथ मामूली विसंगतियां मौजूद हैं, जहाँ शुरुआती क्षेत्र स्कोर बाद के योगदान के विश्वसनीय संकेतक नहीं होते हैं। हालाँकि, अधिकांश नमूनों के लिए, निष्ठा का अंतर नगण्य (<2%) है।