वासेरस्टीन मेट्रिक

From Vigyanwiki
Revision as of 18:28, 27 April 2023 by alpha>Soumyabisht (TEXT)

गणित में, वेसरस्टीन दूरी या कांटोरोविच-रुबिनस्टीन मापीय एक दूरी का फलन है जो किसी दिए गए मापीय समष्टि पर संभाव्यता वितरण के मध्य परिभाषित किया गया है। इसका नाम लियोनिद वेसरस्टीन के नाम पर रखा गया है।

सहज रूप से, यदि प्रत्येक वितरण को पर पुंजित पृथ्वी (मिट्टी) की एक इकाई मात्रा के रूप में देखा जाता है, मापीय एक ढेर को दूसरे में बदलने की न्यूनतम ''लागत'' है, जिसे पृथ्वी की वह मात्रा माना जाता है जिसे स्थानांतरित करने के लिए औसत दूरी से गुणा करने की आवश्यकता होती है। इस समस्या को पहली बार 1781 में गैसपार्ड मोंगे द्वारा औपचारिक रूप दिया गया था। इस समानता के कारण, मापीय को कंप्यूटर विज्ञान में अर्थ स्थानांतरित की दूरी के रूप में जाना जाता है।

स्वचल प्ररूप (रूसी, 1969) की बड़ी प्रणालियों का वर्णन करने वाली मार्कोव प्रक्रियाओं पर लियोनिद वेसरस्टीन के काम में इसे सीखने के बाद, 1970 में आर. एल. डोब्रुशिन द्वारा ''वासेरस्टीन दूरी'' नाम गढ़ा गया था।[1] हालांकि मापन को पहली बार प्रदार्थ और सामग्रियों की इष्टतम परिवहन योजना के संदर्भ में उत्पादन योजना और संगठन की गणितीय विधि (रूसी मूल 1939) में लियोनिद कांटोरोविच द्वारा परिभाषित किया गया था[2] । कुछ विद्वान इस प्रकार ''कांटोरोविच मापीय'' और ''कांटोरोविच दूरी'' शब्दों के उपयोग को प्रोत्साहित करते हैं। अधिकांश अंग्रेजी भाषा के प्रकाशन जर्मन वर्तनी ''वासेरस्टीन'' का उपयोग करते हैं (जर्मन मूल के होने के कारण ''वासेरस्टीन'' नाम दिया गया)।

परिभाषा

अनुमान एक मापीय समष्टि है जो एक राडोण समष्टि है। के लिए, परिमित -क्षण के साथ पर दो प्रायिकता उपायों और के मध्य वासरस्टीन -दूरी है

कहाँ और के सभी युग्मन (संभाव्यता) का समुच्चय है। एक युग्मन , पर एक संयुक्त संभाव्यता उपाय है, जिसके सीमान्त क्रमशः पहले और दूसरे कारकों पर और है। अर्थात,

अंतर्ज्ञान और इष्टतम परिवहन के लिए संबंध

दो एक आयामी वितरण और , x और y कुल्हाड़ियों पर प्लॉट किया गया है, और एक संभावित संयुक्त वितरण जो उनके मध्य एक परिवहन योजना को परिभाषित करता है। संयुक्त वितरण/परिवहन योजना अद्वितीय नहीं है

उपरोक्त परिभाषा को समझने का एक तरीका इष्टतम परिवहन समस्या पर विचार करना है। यानी द्रव्यमान के वितरण के लिए एक समष्टि पर , हम द्रव्यमान को इस तरह से परिवहन करना चाहते हैं कि यह वितरण में परिवर्तित हो जाए एक ही समष्टि पर; 'पृथ्वी के ढेर' को बदलना ढेर के लिए . यह समस्या केवल तभी समझ में आती है जब बनाए जाने वाले ढेर का द्रव्यमान उतना ही हो जितना ढेर को समष्टिांतरित किया जाना है; इसलिए व्यापकता के नुकसान के बिना यह मान लें और प्रायिकता बंटन हैं जिनका कुल द्रव्यमान 1 है। यह भी मान लें कि कुछ लागत फलन दिया गया है

जो एक इकाई द्रव्यमान को बिंदु से ले जाने की लागत देता है मुद्दे पर . समष्टिांतरित करने के लिए एक परिवहन योजना में एक समारोह द्वारा वर्णित किया जा सकता है जो समष्टिांतरित करने के लिए द्रव्यमान की मात्रा देता है को . आप कल्पना कर सकते हैं कि आकार की पृथ्वी के ढेर को समष्टिांतरित करने की आवश्यकता के रूप में कार्य आकार की जमीन में छेद करने के लिए ऐसा कि अंत में, मिट्टी का ढेर और जमीन में छेद दोनों पूरी तरह से गायब हो जाते हैं। इस योजना के सार्थक होने के लिए, इसे निम्नलिखित गुणों को पूरा करना होगा

यही है, कि कुल द्रव्यमान एक असीम क्षेत्र से बाहर चला गया के बराबर होना चाहिए और कुल द्रव्यमान आसपास के क्षेत्र में चला गया होना चाहिए . यह उस आवश्यकता के बराबर है मार्जिन के साथ एक संयुक्त संभाव्यता वितरण हो और . इस प्रकार, अपरिमेय द्रव्यमान से पहुँचाया गया को है , और चलने की लागत है , लागत समारोह की परिभाषा के बाद। इसलिए, एक परिवहन योजना की कुल लागत है

योजना अद्वितीय नहीं है; इष्टतम परिवहन योजना सभी संभावित परिवहन योजनाओं में से न्यूनतम लागत वाली योजना है। जैसा कि उल्लेख किया गया है, एक योजना के वैध होने की आवश्यकता यह है कि यह सीमांत के साथ एक संयुक्त वितरण है और ; दे ऐसे सभी उपायों के सेट को निरूपित करें, जैसा कि पहले खंड में, इष्टतम योजना की लागत है

यदि एक चाल की लागत केवल दो बिंदुओं के मध्य की दूरी है, तो इष्टतम लागत की परिभाषा के समान है दूरी।

उदाहरण

बिंदु द्रव्यमान

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

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

इसी तरह के तर्क से, अगर और बिंदुओं पर स्थित बिंदु द्रव्यमान हैं और में , और हम सामान्य यूक्लिडियन मानदंड का उपयोग करते हैं दूरी समारोह के रूप में, तब


अनुभवजन्य वितरण

एक आयाम

अगर नमूने के साथ एक अनुभवजन्य उपाय है और नमूने के साथ एक अनुभवजन्य उपाय है , दूरी आदेश आँकड़ों का एक सरल कार्य है:


उच्च आयाम

अगर और अनुभवजन्य वितरण हैं, प्रत्येक पर आधारित है अवलोकन, फिर

जहां infimum सभी क्रमपरिवर्तन से अधिक है का तत्व। यह एक रेखीय असाइनमेंट समस्या है, और हंगेरियन एल्गोरिथम द्वारा घन समय में हल किया जा सकता है।

सामान्य वितरण

होने देना और दो गैर-पतित गॉसियन उपायों (यानी सामान्य वितरण) पर हो , संबंधित अपेक्षित मूल्यों के साथ और और सममित सकारात्मक निश्चित | सममित सकारात्मक अर्ध-निश्चित सहप्रसरण मैट्रिक्स और . तब,[3] सामान्य यूक्लिडियन मानदंड के संबंध में , 2-वासेरस्टीन के मध्य की दूरी और है

ध्यान दें कि दूसरा शब्द (ट्रेस शामिल) ठीक (असामान्यीकृत) के मध्य मापीय है और . यह परिणाम दो बिंदुओं के द्रव्यमान (कम से कम मामले में) के मध्य वासेरस्टीन दूरी के पहले के उदाहरण को सामान्य करता है ), चूंकि एक बिंदु द्रव्यमान को सहप्रसरण मैट्रिक्स के साथ सामान्य वितरण के रूप में शून्य के बराबर माना जा सकता है, जिस स्थिति में ट्रेस (रैखिक बीजगणित) शब्द गायब हो जाता है और केवल साधनों के मध्य यूक्लिडियन दूरी को शामिल करने वाला शब्द रहता है।

एक आयामी वितरण

होने देना संभाव्यता उपायों पर हो , और उनके संचयी वितरण समारोह को निरूपित करें और . फिर परिवहन समस्या का एक विश्लेषणात्मक समाधान है: इष्टतम परिवहन संभाव्यता द्रव्यमान तत्वों के क्रम को संरक्षित करता है, इसलिए मात्रा पर द्रव्यमान का क्वांटाइल में जाता है का . इस प्रकार -वासेरस्टीन के मध्य की दूरी और है

कहाँ और मात्रात्मक समारोह (उलटा सीडीएफ) हैं। के मामले में , चरों का परिवर्तन सूत्र की ओर ले जाता है

.

अनुप्रयोग

वासेरस्टीन मापीय दो चर X और Y के प्रायिकता वितरण की तुलना करने का एक स्वाभाविक तरीका है, जहां एक चर दूसरे से छोटे, गैर-समान गड़बड़ी (यादृच्छिक या नियतात्मक) द्वारा प्राप्त किया जाता है।

कंप्यूटर विज्ञान में, उदाहरण के लिए, मापीय W1 असतत वितरणों की तुलना करने के लिए व्यापक रूप से उपयोग किया जाता है, उदा। दो डिजिटल छवियों का रंग हिस्टोग्राम; अधिक विवरण के लिए अर्थ स्थानांतरित की दूरी देखें।

उनके पेपर 'वासेरस्टीन जीएएन' में, अरजोव्स्की एट अल।[4] वासेरस्टीन -1 मापीय का उपयोग जनरेटिव प्रतिकूल नेटवर्क (GAN) के मूल ढांचे को बेहतर बनाने के तरीके के रूप में करें, ताकि लुप्त हो रही ढाल की समस्या और मोड के पतन के मुद्दों को कम किया जा सके। सामान्य वितरण के विशेष मामले का उपयोग फ़्रेचेट स्थापना दूरी में किया जाता है।

वासेरस्टीन मेट्रिक का प्रोक्रिस्ट्स विश्लेषण के साथ एक औपचारिक लिंक है, जिसमें चिरायता उपायों के लिए आवेदन किया गया है,[5] और विश्लेषण को आकार देने के लिए।[6] कम्प्यूटेशनल जीव विज्ञान में, साइटोमेट्री डेटासेट के लगातार समरूपता के मध्य तुलना करने के लिए वासेरस्टीन मापीय का उपयोग किया जा सकता है।[7] भूभौतिकी में व्युत्क्रम समस्याओं में वासेरस्टीन मापीय का भी उपयोग किया गया है।[8] वासेरस्टीन मापीय का उपयोग एकीकृत सूचना सिद्धांत में अवधारणाओं और वैचारिक संरचनाओं के मध्य अंतर की गणना करने के लिए किया जाता है।[9]

गुण

मापीय संरचना

यह दिखाया जा सकता है कि डब्ल्यूp पी पर एक मापीय (गणित) के सभी सिद्धांतों को संतुष्ट करता हैp(एम)। इसके अलावा, डब्ल्यू के संबंध में अभिसरणp उपायों के सामान्य कमजोर अभिसरण और पहले pth क्षणों के अभिसरण के बराबर है।[10]

डब्ल्यू का दोहरा प्रतिनिधित्व1

W का निम्नलिखित दोहरा प्रतिनिधित्व1 लियोनिद कांटोरोविच और रुबिनस्टीन (1958) के द्वैत प्रमेय का एक विशेष मामला है: जब μ और ν में घिरा हुआ सेट सपोर्ट (माप सिद्धांत) होता है,

जहां लिप (एफ) एफ के लिए न्यूनतम लिप्सचिट्ज़ निरंतरता को दर्शाता है।

इसकी तुलना रैडॉन मापीय की परिभाषा से करें:

यदि मापीय d कुछ स्थिर C से घिरा है, तब

और इसलिए रैडॉन मापीय में अभिसरण ('एम' एक पोलिश समष्टि होने पर कुल भिन्नता अभिसरण के समान) का तात्पर्य वासरस्टीन मापीय में अभिसरण से है, लेकिन इसके विपरीत नहीं।

प्रमाण

निम्नलिखित एक सहज प्रमाण है जो तकनीकी बिंदुओं पर छोड़ देता है। में पूर्णतः कठोर प्रमाण मिलता है।[11] असतत मामला: कब असतत है, 1-वासेरस्टीन दूरी के लिए हल करना रैखिक प्रोग्रामिंग में एक समस्या है:

कहाँ एक सामान्य लागत फलन है।

उपरोक्त समीकरणों को सावधानीपूर्वक मैट्रिक्स समीकरणों के रूप में लिखने पर, हमें इसका द्विरेखीय कार्यक्रम प्राप्त होता है[12]:

और दोहरे रेखीय कार्यक्रम # मजबूत द्वैत द्वारा, चूंकि मूल समस्या संभव और बंधी हुई है, इसलिए दोहरी समस्या है, और पहली समस्या में न्यूनतम दूसरी समस्या में अधिकतम के बराबर है। अर्थात्, समस्या युग्म प्रबल द्वैत प्रदर्शित करता है।

सामान्य स्थिति के लिए, योगों को अभिन्न में परिवर्तित करके दोहरी समस्या पाई जाती है:

और मजबूत द्वैत अभी भी कायम है। यह 'कांटोरोविच द्वैत प्रमेय' है। सेड्रिक विलानी ने लुइस कैफरेली से निम्नलिखित व्याख्या की गणना की:[13] <ब्लॉककोट> मान लीजिए कि आप खानों से कुछ कोयले को भेजना चाहते हैं, के रूप में वितरित किया गया , कारखानों को, के रूप में वितरित किया गया . परिवहन का लागत फलन है . अब एक शिपर आता है और आपके लिए परिवहन करने की पेशकश करता है। आप उसे भुगतान करेंगे कोयले को लोड करने के लिए प्रति कोयला , और उसे भुगतान करें कोयले को उतारने के लिए प्रति कोयला .

आपके लिए सौदा स्वीकार करने के लिए, मूल्य अनुसूची को पूरा करना होगा . कांटोरोविच द्वैत कहता है कि शिपर एक मूल्य अनुसूची बना सकता है जो आपको लगभग उतना ही भुगतान करता है जितना आप स्वयं शिप करेंगे।इस परिणाम को प्राप्त करने के लिए आगे दबाया जा सकता है:

Theorem (Kantorovich-Rubenstein duality) — When the probability space is a metric space, then for any fixed ,

where is the Lipschitz norm.

Proof

It suffices to prove the case of . Start with

Then, for any choice of , one can push the term higher by setting , making it an infimal convolution of with a cone. This implies for any , that is, .

Thus,

Next, for any choice of , can be optimized by setting . Since , this implies .

एक वक्र के साथ एक शंकु का अनंत कनवल्शन। ध्यान दें कि निचले लिफाफे में ढलान कैसे है , और निचला लिफाफा उन हिस्सों पर वक्र के बराबर कैसे है जहां वक्र में ही ढलान है .

संभाव्यता समष्टि होने पर दो अनौपचारिक दृढ़ संकल्प चरण स्पष्ट रूप से स्पष्ट होते हैं .

सांकेतिक सुविधा के लिए, आइए अनंत कनवल्शन ऑपरेशन को निरूपित करें।

पहले चरण के लिए, जहाँ हमने प्रयोग किया , का वक्र आरेखित करें , फिर प्रत्येक बिंदु पर, ढलान 1 का एक शंकु बनाएं, और शंकु के निचले लिफाफे को इस प्रकार लें , जैसा कि आरेख में दिखाया गया है, तब 1 से अधिक ढलान के साथ नहीं बढ़ सकता है। इस प्रकार इसके सभी छेदकों में ढलान है .

दूसरे चरण के लिए, शिशु कनवल्शन को चित्रित करें , तो यदि सभी सेकेंट अधिकतम 1 पर ढलान है, फिर का निचला लिफाफा इस प्रकार, केवल शंकु-शीर्ष हैं .

1डी उदाहरण। कब दोनों वितरण कर रहे हैं , फिर भागों द्वारा एकीकरण देते हैं

इस प्रकार

डब्ल्यू की द्रव यांत्रिकी व्याख्या2

बेनमौ और ब्रेनियर को इसका दोहरा प्रतिनिधित्व मिला द्रव यांत्रिकी द्वारा, जो उत्तल अनुकूलन द्वारा कुशल समाधान की अनुमति देता है।[14][15] पर दो प्रायिकता बंटन दिए गए हैं घनत्व के साथ , तब

कहाँ एक वेग क्षेत्र है, और द्रव घनत्व क्षेत्र है, जैसे कि
यही है, द्रव्यमान को संरक्षित किया जाना चाहिए, और वेग क्षेत्र को संभाव्यता वितरण को परिवहन करना चाहिए को समय अंतराल के दौरान .

डब्ल्यू की समानता2 और एक नकारात्मक-क्रम सोबोलेव मानदंड

उपयुक्त धारणाओं के तहत, वासेरस्टीन दूरी ऑर्डर दो का लिप्सचिट्ज़ नकारात्मक-क्रम सजातीय सोबोलिव अंतरिक्ष के बराबर है।[16] अधिक सटीक, अगर हम लेते हैं एक सकारात्मक माप से लैस एक जुड़ा हुआ समष्टि रीमैनियन कई गुना होना , तो हम के लिए परिभाषित कर सकते हैं सेमिनोर्म

और एक हस्ताक्षरित उपाय के लिए पर दोहरा मानदंड

तब किन्हीं दो प्रायिकता मापों को और पर ऊपरी सीमा को संतुष्ट करें

दूसरी दिशा में यदि और प्रत्येक में वॉल्यूम फॉर्म के संबंध में घनत्व होता है जो दोनों कुछ से ऊपर बंधे हुए हैं , और गैर-नकारात्मक रिक्की वक्रता है, तब

पृथक्करणीयता और पूर्णता

किसी भी p ≥ 1 के लिए मापीय समष्टि ('P'p(एम), डब्ल्यूp) वियोज्य समष्टि है, और पूर्ण समष्टि है यदि (M, d) वियोज्य और पूर्ण है।[17]

यह भी देखें

संदर्भ

  1. Vaserstein LN (1969). "मार्कोव ऑटोमेटा की बड़ी प्रणालियों का वर्णन करते हुए रिक्त स्थान के अगणनीय उत्पादों पर प्रक्रिया करता है" (PDF). Problemy Peredači Informacii. 5 (3): 64–72.
  2. Kantorovich LV (1939). "उत्पादन के आयोजन और योजना के गणितीय तरीके". Management Science. 6 (4): 366–422. doi:10.1287/mnsc.6.4.366. JSTOR 2627082.
  3. Olkin I, Pukelsheim F (October 1982). "दिए गए फैलाव मैट्रिक्स के साथ दो यादृच्छिक वैक्टर के बीच की दूरी". Linear Algebra and Its Applications. 48: 257–263. doi:10.1016/0024-3795(82)90112-4. ISSN 0024-3795.
  4. Arjovsky M, Chintala S, Bottou L (July 2017). "वासेरस्टीन जनरेटिव एडवरसैरियल नेटवर्क". International Conference on Machine Learning 214-223: 214–223.
  5. Petitjean M (2002). "चिरल मिश्रण" (PDF). Journal of Mathematical Physics. 43 (8): 4147–4157. Bibcode:2002JMP....43.4147P. doi:10.1063/1.1484559.
  6. Petitjean M (2004). "From shape similarity to shape complementarity: toward a docking theory". Journal of Mathematical Chemistry. 35 (3): 147–158. doi:10.1023/B:JOMC.0000033252.59423.6b. S2CID 121320315.
  7. Mukherjee S, Wethington D, Dey TK, Das J (March 2022). "लगातार होमोलॉजी का उपयोग करके साइटोमेट्री डेटा में नैदानिक ​​​​रूप से प्रासंगिक विशेषताओं का निर्धारण". PLOS Computational Biology. 18 (3): e1009931. arXiv:2203.06263. Bibcode:2022PLSCB..18E9931M. doi:10.1371/journal.pcbi.1009931. PMC 9009779. PMID 35312683. {{cite journal}}: zero width space character in |title= at position 60 (help)
  8. Frederick, Christina; Yang, Yunan (2022-05-06). "इष्टतम परिवहन की सहायता से चट्टान के आर-पार देखना". Snapshots of Modern Mathematics from Oberwolfach. doi:10.14760/SNAP-2022-004-EN.
  9. Oizumi, Masafumi; Albantakis, Larissa; Tononi, Giulio (2014-05-08). "From the Phenomenology to the Mechanisms of Consciousness: Integrated Information Theory 3.0". PLOS Computational Biology. 10 (5): e1003588. Bibcode:2014PLSCB..10E3588O. doi:10.1371/journal.pcbi.1003588. PMC 4014402. PMID 24811198.
  10. Clement P, Desch W (2008). "वासरस्टीन मीट्रिक के लिए त्रिभुज असमानता का एक प्रारंभिक प्रमाण". Proceedings of the American Mathematical Society. 136 (1): 333–339. doi:10.1090/S0002-9939-07-09020-X.
  11. Villani, Cédric (2003). "Chapter 1: The Kantorovich Duality". इष्टतम परिवहन में विषय. Providence, RI: American Mathematical Society. ISBN 0-8218-3312-X. OCLC 51477002.
  12. Matoušek, Jiří; Gärtner, Bernd (2007), Duality of Linear Programming, Universitext, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 81–104, doi:10.1007/978-3-540-30717-4_6, ISBN 978-3-540-30697-9, retrieved 2022-07-15
  13. Villani, Cédric (2003). "1.1.3. The shipper's problem.". इष्टतम परिवहन में विषय. Providence, RI: American Mathematical Society. ISBN 0-8218-3312-X. OCLC 51477002.
  14. Benamou, Jean-David; Brenier, Yann (2000-01-01). "Monge-Kantorovich मास ट्रांसफर समस्या के लिए एक कम्प्यूटेशनल द्रव यांत्रिकी समाधान". Numerische Mathematik (in English). 84 (3): 375–393. doi:10.1007/s002110050002. ISSN 0945-3245. S2CID 1100384.
  15. Finlay, Chris; Jacobsen, Joern-Henrik; Nurbekyan, Levon; Oberman, Adam (2020-11-21). "How to Train Your Neural ODE: the World of Jacobian and Kinetic Regularization". International Conference on Machine Learning (in English). PMLR: 3154–3164. arXiv:2002.02798.
  16. Peyre R (October 2018). "Comparison between W2 distance and −1 norm, and localization of Wasserstein distance". ESAIM: Control, Optimisation and Calculus of Variations. 24 (4): 1489–1501. doi:10.1051/cocv/2017050. ISSN 1292-8119. (See Theorems 2.1 and 2.5.)
  17. Bogachev VI, Kolesnikov AV (October 2012). "The Monge–Kantorovich problem: achievements, connections, and perspectives". Russian Mathematical Surveys. 67 (5): 785–890. Bibcode:2012RuMaS..67..785B. doi:10.1070/RM2012v067n05ABEH004808. S2CID 121411457.


अग्रिम पठन


बाहरी संबंध