वासेरस्टीन मेट्रिक
गणित में, वेसरस्टीन दूरी या कांटोरोविच-रुबिनस्टीन मापीय एक दूरी का फलन है जो किसी दिए गए मापीय समष्टि पर संभाव्यता वितरण के मध्य परिभाषित किया गया है। इसका नाम लियोनिद वेसरस्टीन के नाम पर रखा गया है।
सहज रूप से, यदि प्रत्येक वितरण को पर पुंजित पृथ्वी (मिट्टी) की एक इकाई मात्रा के रूप में देखा जाता है, मापीय एक ढेर को दूसरे में बदलने की न्यूनतम ''लागत'' है, जिसे पृथ्वी की वह मात्रा माना जाता है जिसे स्थानांतरित करने के लिए औसत दूरी से गुणा करने की आवश्यकता होती है। इस समस्या को पहली बार 1781 में गैसपार्ड मोंगे द्वारा औपचारिक रूप दिया गया था। इस समानता के कारण, मापीय को कंप्यूटर विज्ञान में अर्थ स्थानांतरित की दूरी के रूप में जाना जाता है।
स्वचल प्ररूप (रूसी, 1969) की बड़ी प्रणालियों का वर्णन करने वाली मार्कोव प्रक्रियाओं पर लियोनिद वेसरस्टीन के काम में इसे सीखने के बाद, 1970 में आर. एल. डोब्रुशिन द्वारा ''वासेरस्टीन दूरी'' नाम गढ़ा गया था।[1] हालांकि मापन को पहली बार प्रदार्थ और सामग्रियों की इष्टतम परिवहन योजना के संदर्भ में उत्पादन योजना और संगठन की गणितीय विधि (रूसी मूल 1939) में लियोनिद कांटोरोविच द्वारा परिभाषित किया गया था[2] । कुछ विद्वान इस प्रकार ''कांटोरोविच मापीय'' और ''कांटोरोविच दूरी'' शब्दों के उपयोग को प्रोत्साहित करते हैं। अधिकांश अंग्रेजी भाषा के प्रकाशन जर्मन वर्तनी ''वासेरस्टीन'' का उपयोग करते हैं (जर्मन मूल के होने के कारण ''वासेरस्टीन'' नाम दिया गया)।
परिभाषा
अनुमान एक मापीय समष्टि है जो एक राडोण समष्टि है। के लिए, परिमित -क्षण के साथ पर दो प्रायिकता उपायों और के मध्य वासरस्टीन -दूरी है
कहाँ और के सभी युग्मन (संभाव्यता) का समुच्चय है। एक युग्मन , पर एक संयुक्त संभाव्यता उपाय है, जिसके सीमान्त क्रमशः पहले और दूसरे कारकों पर और है। अर्थात,
अंतर्ज्ञान और इष्टतम परिवहन के लिए संबंध
उपरोक्त परिभाषा को समझने का प्रकार इष्टतम परिवहन समस्या पर विचार करना है। यानी समष्टि पर द्रव्यमान के वितरण के लिए, हम द्रव्यमान को इस तरह से परिवहन करना चाहते हैं कि यह वितरण में परिवर्तित हो जाए; 'पृथ्वी के ढेर' को ढेर में बदलना है। यह समस्या केवल तभी समझ में आती है जब बनाए जाने वाले ढेर का द्रव्यमान उतना ही हो जितना ढेर को स्थानांतरित किया जाना है; इसलिए व्यापकता के हानि के बिना यह मान लें कि और संभाव्यता वितरण हैं जिनका कुल 1 द्रव्यमान है। यह भी मान लें कि कुछ लागत फलन दिया गया है
यह एक इकाई द्रव्यमान को बिंदु से बिंदु तक ले जाने की लागत देता है। को ले जाने की एक परिवहन योजना को एक फलन द्वारा वर्णित किया जा सकता है जो से तक जाने के लिए द्रव्यमान की मात्रा देता है। आप फलन की कल्पना कर सकते हैं कि आकृति की जमीन में छेद करने के लिए आकार की पृथ्वी के ढेर को स्थानांतरित करने की आवश्यकता है, जैसे कि अंत में, मिट्टी का ढेर और जमीन में छेद दोनों पूरी तरह से गायब हो जाते हैं। इस योजना के सार्थक होने के लिए, इसे निम्नलिखित गुणों को पूरा करना होगा
अर्थात्, के आसपास एक अतिसूक्ष्म क्षेत्र से बाहर चला गया कुल द्रव्यमान के समान होना चाहिए और के आसपास एक क्षेत्र में स्थानांतरित कुल द्रव्यमान होना चाहिए। यह आवश्यकता के समान है कि सीमांत और के साथ एक संयुक्त संभाव्यता वितरण हो। इस प्रकार, से तक पहुँचाया गया अतिसूक्ष्म द्रव्यमान है, और लागत फलन की परिभाषा के बाद चलने की लागत है। इसलिए, परिवहन योजना की कुल लागत है
योजना अद्वितीय नहीं है; इष्टतम परिवहन योजना सभी संभावित परिवहन योजनाओं में से न्यूनतम लागत वाली योजना है। जैसा कि उल्लेख किया गया है, एक योजना के वैध होने की आवश्यकता यह है कि यह सीमांत और के साथ एक संयुक्त वितरण है; पहले खंड के रूप में ऐसे सभी उपायों के समुच्चय को दर्शाता है, इष्टतम योजना की लागत है
यदि एक चाल की लागत केवल दो बिंदुओं के मध्य की दूरी है, तो इष्टतम लागत दूरी की परिभाषा के समान है।
उदाहरण
बिंदु द्रव्यमान
नियतात्मक वितरण
अनुमान और में बिंदुओं और पर स्थित दो पतित वितरण (अर्थात डायराक डेल्टा वितरण) बनें। इन दो मापों का केवल एक संभावित युग्मन है, अर्थात् बिंदु द्रव्यमान पर स्थित है। इस प्रकार, किसी भी के लिए, पर दूरी फलन के रूप में सामान्य निरपेक्ष मान फलन का उपयोग करते हुए, और के मध्य -वासेरस्टीन की दूरी है
इसी तरह के तर्क से, यदि और में बिंदुओं और पर स्थित बिंदु द्रव्यमान हैं, और हम दूरी फलन के रूप में पर सामान्य यूक्लिडियन मानदंड का उपयोग करते हैं, तब
आनुभविकबंटन
एक आयाम
अगर प्रतिदर्श के साथ एक अनुभवजन्य माप है और प्रतिदर्श के साथ एक अनुभवजन्य माप है, तो दूरी क्रम के आँकड़ों का एक सरल फलन है:
उच्च आयाम
यदि और अनुभवजन्य वितरण हैं, प्रत्येक अवलोकन पर आधारित है, तब
जहां तत्वों के सभी क्रमपरिवर्तन पर सबसे कम है। यह एक रेखीय समनुदेश समस्या है, और हंगेरियन कलनविधि द्वारा घन समय में हल किया जा सकता है।
सामान्य वितरण
अनुमान और पर दो गैर-पतित गॉसियन मापक (यानी सामान्य वितरण) होने दें, संबंधित अपेक्षित मूल्यों के साथ और और सममित सकारात्मक अर्ध-निश्चित सहप्रसरण आव्यूह और । तब,[3] पर सामान्य यूक्लिडियन मानदंड के संबंध में, और के मध्य 2-वासेरस्टीन की दूरी है
ध्यान दें कि दूसरा शब्द (ट्रेस निहीत) यथार्थतः (असामान्यीकृत) और के मध्य मापीय है। यह परिणाम दो बिंदु द्रव्यमानों के मध्य वासेरस्टीन दूरी के पहले के उदाहरण को सामान्यीकृत करता है (कम से कम प्रकरण में ), क्योंकि एक बिंदु द्रव्यमान को सामान्य वितरण के रूप में माना जा सकता है, जिसमें सहसंयोजक आव्यूह शून्य के समान होता है जिस प्रकरण में ट्रेस (रैखिक बीजगणित) शब्द लुप्त हो जाता है और केवल साधनों के मध्य यूक्लिडियन दूरी को सम्मलित करने वाला शब्द रहता है।
एक आयामी वितरण
अनुमान पर संभाव्यता मापक हैं, और और द्वारा उनके संचयी वितरण फलन को निरूपित करते हैं। फिर परिवहन समस्या का एक विश्लेषणात्मक समाधान है: इष्टतम परिवहन संभाव्यता द्रव्यमान तत्वों के क्रम को संरक्षित करता है, इसलिए के विभाजक पर द्रव्यमान के विभाजक में चला जाता है। इस प्रकार और के मध्य -वासेरस्टीन की दूरी है
कहाँ और मात्रात्मक फलन (उलटा सीडीएफ) हैं। के प्रकरण में, चर के परिवर्तन से सूत्र की ओर जाता है
- .
अनुप्रयोग
वासेरस्टीन मापीय दो चर X और Y के प्रायिकता वितरण की तुलना करने का एक स्वाभाविक प्रकार है, जहां एक चर दूसरे से छोटे, गैर-समान क्षोभ (यादृच्छिक या नियतात्मक) द्वारा प्राप्त किया जाता है।
कंप्यूटर विज्ञान में, उदाहरण के लिए, मापीय W1 का व्यापक रूप से असतत वितरणों की तुलना करने के लिए उपयोग किया जाता है, उदाहरण दो अंकीय प्रतिबिंब का रंग आयतचित्र; अधिक विवरण के लिए अर्थ स्थानांतरित की दूरी देखें।
अपने काग़ज़ 'वासेरस्टीन जीएएन' में, अरजोव्स्की एट अल[4] और अन्य प्रजनन विरोधात्मक संजाल (GAN) के मूल संरचना में सुधार करने के प्रकार के रूप में वासेरस्टीन-1 मापीय का उपयोग करते हैं, ताकि लुप्त होने वाले प्रवणता और प्रकार के पतन के मुद्दों को कम करने के लिए। सामान्य वितरण के विशेष प्रकरण का उपयोग फ़्रेचेट स्थापना दूरी में किया जाता है।
वासेरस्टीन मापीय का प्रोक्रिस्ट्स विश्लेषण के साथ एक औपचारिक श्रंखला है, जिसमें इंगिता मापक के लिए आवेदन और विश्लेषण को आकार देने के लिए।[5] [6]
अभिकलन जीव विज्ञान में, वासेरस्टीन मापीय का उपयोग साइटोमेट्री आँकड़ा समुच्चय के दृढ़ता आरेखों के मध्य तुलना करने के लिए किया जा सकता है।[7]
भूभौतिकी में व्युत्क्रम समस्याओं में वासेरस्टीन मापीय का भी उपयोग किया गया है।[8]
वासेरस्टीन मापीय का उपयोग एकीकृत सूचना सिद्धांत में अवधारणाओं और वैचारिक संरचनाओं के मध्य अंतर की गणना करने के लिए किया जाता है।[9]
गुण
मापीय संरचना
यह दिखाया जा सकता है कि Wp, Pp(M) पर एक मापीय (गणित) के सभी सिद्धांतों को संतुष्ट करता है। इसके अलावा, Wp के संबंध में अभिसरण माप के सामान्य दुर्बल अभिसरण और पहले pth क्षणों के अभिसरण के समान है।[10]
डब्ल्यू का दोहरा प्रतिनिधित्व1
W1 का निम्नलिखित दोहरा प्रतिनिधित्व कांटोरोविच और रुबिनस्टीन (1958) के द्वैत प्रमेय का एक विशेष प्रकरण है: जब μ और ν का परिबद् आश्रय होता है,
जहां लिप(f) f के लिए न्यूनतम लिप्सचिट्ज़ स्थिरांक को दर्शाता है।
इसकी तुलना रैडॉन मापीय की परिभाषा से करें:
यदि मापीय d कुछ स्थिर C से परिबद्ध है, तब
और इसलिए रैडॉन मापीय में अभिसरण (कुल भिन्नता अभिसरण के समान जब 'M' एक पोलिश समष्टि है) का तात्पर्य वासरस्टीन मापीय में अभिसरण से है, लेकिन इसके विपरीत नहीं है।
प्रमाण
निम्नलिखित एक सहज प्रमाण है जो तकनीकी बिंदुओं पर छोड़ देता है। पूर्णतः कठोर प्रमाण मिलता है।[11] असतत प्रकरण: कब असतत है, 1-वासेरस्टीन दूरी के लिए समाधान करना रैखिक क्रमादेशन में एक समस्या है:
उपरोक्त समीकरणों को सावधानीपूर्वक आव्यूह समीकरणों के रूप में लिखने पर, हमें इसकी द्विरेखीय समस्या प्राप्त होती है[12]:
सामान्य प्रकरण के लिए, योगों को अभिन्न में परिवर्तित करके दोहरी समस्या पाई जाती है:
मान लीजिए कि आप खानों से कुछ कोयले को के रूप में वितरित करना चाहते हैं, कारखानों को, के रूप में वितरित करना चाहते हैं। परिवहन का लागत फलन है। अब एक शिपर आता है और आपके लिए परिवहन प्रस्तुत करता है। आप उसे पर कोयला लोड करने के लिए प्रति कोयला भुगतान करेंगे, और पर कोयले को उतारने के लिए उसे प्रति कोयला भुगतान करेंगे।
आपके लिए सौदा स्वीकार करने के लिए, मूल्य अनुसूची को पूरा करना होगा . कांटोरोविच द्वैत कहता है कि शिपर एक मूल्य अनुसूची बना सकता है जो आपको लगभग उतना ही भुगतान करता है जितना आप स्वयं शिप करेंगे।इस परिणाम को प्राप्त करने के लिए आगे दबाया जा सकता है:
Theorem (Kantorovich-Rubenstein duality) — When the probability space is a metric space, then for any fixed ,
It suffices to prove the case of . Start with
Thus,
संभाव्यता समष्टि होने पर दो अनौपचारिक दृढ़ संकल्प चरण स्पष्ट रूप से स्पष्ट होते हैं .
सांकेतिक सुविधा के लिए, आइए अनंत कनवल्शन ऑपरेशन को निरूपित करें।
पहले चरण के लिए, जहाँ हमने प्रयोग किया , का वक्र आरेखित करें , फिर प्रत्येक बिंदु पर, ढलान 1 का एक शंकु बनाएं, और शंकु के निचले लिफाफे को इस प्रकार लें , जैसा कि आरेख में दिखाया गया है, तब 1 से अधिक ढलान के साथ नहीं बढ़ सकता है। इस प्रकार इसके सभी छेदकों में ढलान है .
दूसरे चरण के लिए, शिशु कनवल्शन को चित्रित करें , तो यदि सभी सेकेंट अधिकतम 1 पर ढलान है, फिर का निचला लिफाफा इस प्रकार, केवल शंकु-शीर्ष हैं .
1डी उदाहरण। कब दोनों वितरण कर रहे हैं , फिर भागों द्वारा एकीकरण देते हैं
डब्ल्यू की द्रव यांत्रिकी व्याख्या2
बेनमौ और ब्रेनियर को इसका दोहरा प्रतिनिधित्व मिला द्रव यांत्रिकी द्वारा, जो उत्तल अनुकूलन द्वारा कुशल समाधान की अनुमति देता है।[14][15] पर दो प्रायिकता बंटन दिए गए हैं घनत्व के साथ , तब
डब्ल्यू की समानता2 और एक नकारात्मक-क्रम सोबोलेव मानदंड
उपयुक्त धारणाओं के तहत, वासेरस्टीन दूरी ऑर्डर दो का लिप्सचिट्ज़ नकारात्मक-क्रम सजातीय सोबोलिव अंतरिक्ष के समान है।[16] अधिक सटीक, अगर हम लेते हैं एक सकारात्मक माप से लैस एक जुड़ा हुआ समष्टि रीमैनियन कई गुना होना , तो हम के लिए परिभाषित कर सकते हैं सेमिनोर्म
और एक हस्ताक्षरित उपाय के लिए पर दोहरा मानदंड
तब किन्हीं दो प्रायिकता मापों को और पर ऊपरी सीमा को संतुष्ट करें
दूसरी दिशा में यदि और प्रत्येक में वॉल्यूम फॉर्म के संबंध में घनत्व होता है जो दोनों कुछ से ऊपर बंधे हुए हैं , और गैर-नकारात्मक रिक्की वक्रता है, तब
पृथक्करणीयता और पूर्णता
किसी भी p ≥ 1 के लिए मापीय समष्टि ('P'p(एम), डब्ल्यूp) वियोज्य समष्टि है, और पूर्ण समष्टि है यदि (M, d) वियोज्य और पूर्ण है।[17]
यह भी देखें
- हचिंसन मापीय
- लेवी मापीय
- लेवी-प्रोखोरोव मापीय
- फ्रेचेट दूरी
- संभाव्यता उपायों की कुल भिन्नता दूरी
- परिवहन सिद्धांत (गणित)
- पृथ्वी स्थानांतरित की दूरी
- वासेरस्टीन जीएएन
संदर्भ
- ↑ Vaserstein LN (1969). "मार्कोव ऑटोमेटा की बड़ी प्रणालियों का वर्णन करते हुए रिक्त स्थान के अगणनीय उत्पादों पर प्रक्रिया करता है" (PDF). Problemy Peredači Informacii. 5 (3): 64–72.
- ↑ Kantorovich LV (1939). "उत्पादन के आयोजन और योजना के गणितीय तरीके". Management Science. 6 (4): 366–422. doi:10.1287/mnsc.6.4.366. JSTOR 2627082.
- ↑ 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.
- ↑ Arjovsky M, Chintala S, Bottou L (July 2017). "वासेरस्टीन जनरेटिव एडवरसैरियल नेटवर्क". International Conference on Machine Learning 214-223: 214–223.
- ↑ Petitjean M (2002). "चिरल मिश्रण" (PDF). Journal of Mathematical Physics. 43 (8): 4147–4157. Bibcode:2002JMP....43.4147P. doi:10.1063/1.1484559.
- ↑ 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.
- ↑ 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) - ↑ Frederick, Christina; Yang, Yunan (2022-05-06). "इष्टतम परिवहन की सहायता से चट्टान के आर-पार देखना". Snapshots of Modern Mathematics from Oberwolfach. doi:10.14760/SNAP-2022-004-EN.
- ↑ 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.
- ↑ Clement P, Desch W (2008). "वासरस्टीन मीट्रिक के लिए त्रिभुज असमानता का एक प्रारंभिक प्रमाण". Proceedings of the American Mathematical Society. 136 (1): 333–339. doi:10.1090/S0002-9939-07-09020-X.
- ↑ Villani, Cédric (2003). "Chapter 1: The Kantorovich Duality". इष्टतम परिवहन में विषय. Providence, RI: American Mathematical Society. ISBN 0-8218-3312-X. OCLC 51477002.
- ↑ 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
- ↑ Villani, Cédric (2003). "1.1.3. The shipper's problem.". इष्टतम परिवहन में विषय. Providence, RI: American Mathematical Society. ISBN 0-8218-3312-X. OCLC 51477002.
- ↑ 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.
- ↑ 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.
- ↑ 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.)
- ↑ 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.
अग्रिम पठन
- Ambrosio L, Gigli N, Savaré G (2005). Gradient Flows in Metric Spaces and in the Space of Probability Measures. Basel: ETH Zürich, Birkhäuser Verlag. ISBN 978-3-7643-2428-5.
- Jordan R, Kinderlehrer D, Otto F (January 1998). "The variational formulation of the Fokker–Planck equation". SIAM Journal on Mathematical Analysis. 29 (1): 1–17 (electronic). CiteSeerX 10.1.1.6.8815. doi:10.1137/S0036141096303359. ISSN 0036-1410. MR 1617171. S2CID 13890235.
- Rüschendorf L (2001) [1994], "Wasserstein metric", Encyclopedia of Mathematics, EMS Press
- Villani C (2008). Optimal Transport, Old and New. Springer. ISBN 978-3-540-71050-9.