उपप्रतिरूपक समुच्चय फलन: Difference between revisions

Latest revision as of 11:28, 21 August 2023

गणित में, एक उपप्रतिरूपक समुच्चय फलन (जिसे उपप्रतिरूपक फलन के रूप में भी जाना जाता है) एक समुच्चय फलन होता है, जिसका मूल्य,अनौपचारिक रूप से, यह गुण रखता है कि इनपुट समुच्चय में जोड़े जाने पर एकल तत्व जो फलन बनाता है, उसके वृद्धिशील मूल्य में अंतर इनपुट समुच्चय का आकार बढ़ने के साथ घटता जाता है। उपप्रतिरूपक फलन में एक प्राकृतिक ह्रासमान रिटर्न गुण होता है जो उन्हें कई अनुप्रयोगों के लिए उपयुक्त बनाता है, जिसमें सन्निकटन एल्गोरिदम, खेल सिद्धांत (उपयोगकर्ता प्राथमिकताओं को प्रतिरूपक करने वाले फलन के रूप में) और विद्युत नेटवर्क सम्मिलित होता हैं। हाल ही में, यंत्र अधिगम और कृत्रिम होशियारी में कई वास्तविक दुनिया की समस्याओं में उपप्रतिरूपक फलन को अत्यधिक उपयोगिता मिली है, जिसमें स्वचालित सारांशीकरण, बहु-दस्तावेज़ सारांशीकरण, फ़ीचर चयन, सक्रिय शिक्षण (मशीन लर्निंग), सेंसर प्लेसमेंट, छवि संग्रह सारांशीकरण और कई अन्य डोमेन सम्मिलित होता हैं।^[1]^[2]^[3]^[4]

परिभाषा

अगर $\Omega$ एक परिमित समुच्चय (गणित) है, उपप्रतिरूपक फलन एक समुच्चय फलन है $f:2^{\Omega }\rightarrow \mathbb {R}$ , जहाँ $2^{\Omega }$ पावर समुच्चय को दर्शाता है उपसमुच्चय को कार्यों के रूप में प्रस्तुत करना $\Omega$ , जो निम्नलिखित समकक्ष शर्तों में से एक को संतुष्ट करता है।^[5]

सभी के लिए $X,Y\subseteq \Omega$ साथ $X\subseteq Y$ और हर $x\in \Omega \setminus Y$ हमारे पास वह है $f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)$ .
सभी के लिए $S,T\subseteq \Omega$ हमारे पास वह है $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$ .
सभी के लिए $X\subseteq \Omega$ और $x_{1},x_{2}\in \Omega \backslash X$ ऐसा है कि $x_{1}\neq x_{2}$ हमारे पास वह है $f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)$ .

एक गैर-ऋणात्मक उपप्रतिरूपक भी एक सबएडिटिव समुच्चय फलन है, लेकिन एक सबएडिटिव फलन को उपप्रतिरूपक होने की आवश्यकता नहीं होता है।

अगर $\Omega$ यदि इसे परिमित नहीं माना जाता है, तो उपरोक्त स्थितियाँ समतुल्य नहीं होता हैं। विशेष रूप से एक समारोह

 $f$  द्वारा परिभाषित  $f(S)=1$  अगर  $S$  परिमित है और  $f(S)=0$  अगर  $S$  अनंत है

उपरोक्त पहली शर्त को संतुष्ट करता है, लेकिन दूसरी शर्त विफल हो जाती है $S$ और $T$ परिमित प्रतिच्छेदन वाले अनंत समुच्चय होता हैं।

उपप्रतिरूपक फलन के प्रकार और उदाहरण

मोनोटोन

एक समुच्चय फलन $f$ यदि प्रत्येक के लिए एकरस है $T\subseteq S$ हमारे पास वह है $f(T)\leq f(S)$ . मोनोटोन उपप्रतिरूपक फलन के उदाहरणों में सम्मिलित होता हैं:

रैखिक (प्रतिरूपक) फलन: प्रपत्र का कोई भी कार्य $f(S)=\sum _{i\in S}w_{i}$ एक रैखिक फलन कहलाता है। इसके अतिरिक्त यदि $\forall i,w_{i}\geq 0$ तब f एकस्वर होता है।
बजट-योगात्मक मूल्यांकन: प्रपत्र का कोई भी कार्य $f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}$ प्रत्येक के लिए $w_{i}\geq 0$ और $B\geq 0$ बजट योगात्मक कहा जाता है।^[6]; कवरेज फलन: चलो $\Omega =\{E_{1},E_{2},\ldots ,E_{n}\}$ कुछ मैंट्रोइड के उपसमुच्चय का संग्रह बनें $\Omega '$ . कार्यक्रम $f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|$ के लिए $S\subseteq \Omega$ कवरेज फलन कहा जाता है. इसे तत्वों में गैर-नकारात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
एन्ट्रॉपी (सूचना सिद्धांत): $\Omega =\{X_{1},X_{2},\ldots ,X_{n}\}$ यादृच्छिक चर का एक समुच्चय बना होता है। फिर किसी के लिए $S\subseteq \Omega$ हमारे पास वह है $H(S)$ एक उपप्रतिरूपक फलन होता है, जहां $H(S)$ यादृच्छिक चर के समुच्चय की एन्ट्रापी होता है $S$ , एक तथ्य जिसे एंट्रोपिक सदिश शैनन-प्रकार की असमानताएं और Γn|शैनन की असमानता के रूप में जाना जाता है।^[7] एन्ट्रॉपी फलन के लिए और भी असमानताएँ बनी रहने के लिए जानी जाती हैं, एन्ट्रोपिक वेक्टर देखा जाता है।
मैट्रोइड रैंक फलन: $\Omega =\{e_{1},e_{2},\dots ,e_{n}\}$ वह ग्राउंड समुच्चय हो जिस पर मैट्रोइड को परिभाषित किया गया है। फिर मैट्रोइड का रैंक फलन एक उपप्रतिरूपक फलन होता है।^[8]

नॉन - मोनोटोन

एक उपप्रतिरूपक फलन जो मोनोटोन नहीं है उसे नॉन-मोनोटोन कहा जाता है।

सममित

एक नॉन-मोनोटोन उपप्रतिरूपक फलन $f$ यदि प्रत्येक के लिए सममित कहा जाता है $S\subseteq \Omega$ हमारे पास वह है $f(S)=f(\Omega -S)$ .

सममित नॉन-मोनोटोन उपप्रतिरूपक फलन के उदाहरणों में सम्मिलित होता हैं:

ग्राफ़ कट्स: $\Omega =\{v_{1},v_{2},\dots ,v_{n}\}$ एक ग्राफ़ (अलग गणित) के शीर्ष बना होता है। शीर्षों के किसी भी समुच्चय के लिए $S\subseteq \Omega$ होने देना $f(S)$ किनारों की संख्या को निरूपित करें $e=(u,v)$ ऐसा है कि $u\in S$ और $v\in \Omega -S$ . इसे किनारों पर गैर-ऋणात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
आपसी जानकारी: $\Omega =\{X_{1},X_{2},\ldots ,X_{n}\}$ यादृच्छिक चर का एक समुच्चय बना होता है। फिर किसी के लिए $S\subseteq \Omega$ हमारे पास वह है $f(S)=I(S;\Omega -S)$ एक उपप्रतिरूपक फलन है, जहां $I(S;\Omega -S)$ आपसी जानकारी होता है.

असममित

एक नॉन-मोनोटोन उपप्रतिरूपक फलन जो सममित नहीं है, असममित कहलाता है।

निर्देशित कटौती: $\Omega =\{v_{1},v_{2},\dots ,v_{n}\}$ एक निर्देशित ग्राफ के शीर्ष बना होता है। शीर्षों के किसी भी समुच्चय के लिए $S\subseteq \Omega$ होने देना $f(S)$ किनारों की संख्या को निरूपित करें $e=(u,v)$ ऐसा है कि $u\in S$ और $v\in \Omega -S$ . इसे निर्देशित किनारों पर गैर-ऋणात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।

सतत विस्तार

परिभाषा

एक समुच्चय फलन $f:2^{\Omega }\rightarrow \mathbb {R}$ साथ $|\Omega |=n$ को फलन के रूप में भी दर्शाया जा सकता है $\{0,1\}^{n}$ , प्रत्येक को संबद्ध करके $S\subseteq \Omega$ एक बाइनरी सदिश के साथ $x^{S}\in \{0,1\}^{n}$ ऐसा है कि $x_{i}^{S}=1$ जब $i\in S$ , और $x_{i}^{S}=0$ अन्यथा।

निरंतर रेस्ट्रिक्शन_(गणित) विस्तार_का_एक_फलन का $f$ किसी भी सतत कार्य के रूप में परिभाषित किया गया है $F:[0,1]^{n}\rightarrow \mathbb {R}$ जैसे कि यह के मूल्य से मिलता हो $f$ पर $x\in \{0,1\}^{n}$ , अर्थात होता है। $F(x^{S})=f(S)$ .

उपप्रतिरूपक फलन के संदर्भ में, निरंतर विस्तार के कुछ उदाहरण हैं जो सामान्यतौर पर उपयोग किए जाते हैं, जिनका वर्णन इस प्रकार होता है।

उदाहरण

राइडर विस्तार

इस विस्तार का नाम गणितज्ञ लास्ज़लो लोवाज़ के नाम पर रखा गया है।^[9]किसी भी सदिश पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . तब राइडर विस्तार को इस प्रकार परिभाषित किया गया है $f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))$ जहां उम्मीद खत्म हो गई $\lambda$ अंतराल पर समान वितरण (निरंतर) से चुना गया $[0,1]$ . राइडर विस्तार एक उत्तल फलन है यदि $f$ एक उपप्रतिरूपक फलन होता है.

बहुरेखीय विस्तार

किसी भी सदिश पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . फिर बहुरेखीय विस्तार को इस प्रकार परिभाषित किया गया है $F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})$ .

उत्तल समापन

किसी भी सदिश पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . फिर उत्तल समापन को इस प्रकार परिभाषित किया गया है $f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)$ . किसी भी समुच्चय फलन का उत्तल समापन उत्तल होता है $[0,1]^{n}$ .

अवतल सिमित होना

किसी भी सदिश पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . फिर अवतल समापन को इस प्रकार परिभाषित किया गया है $f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)$ .

विस्तार के बीच कनेक्शन

ऊपर चर्चा किए गए विस्तार के लिए, यह दिखाया जा सकता है $f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )$ जब $f$ उपप्रतिरूपक होता है.^[10]

गुण

उपप्रतिरूपक फलन का वर्ग गैर-ऋणात्मक रैखिक संयोजन के तहत सिमित (गणित) होता है। किसी भी उपप्रतिरूपक फलन पर विचार करें $f_{1},f_{2},\ldots ,f_{k}$ और गैर-ऋणात्मक संख्याएँ $\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}$ . फिर फलन $g$ द्वारा परिभाषित $g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)$ उपप्रतिरूपक होता है.
किसी भी उपप्रतिरूपक फलन के लिए $f$ , द्वारा परिभाषित फलन $g(S)=f(\Omega \setminus S)$ उपप्रतिरूपक होता है.
कार्यक्रम $g(S)=\min(f(S),c)$ , जहाँ $c$ एक वास्तविक संख्या है, जब भी उपप्रतिरूपक होता है $f$ मोनोटोन उपप्रतिरूपक है. सामान्यतौर पर अत्यधिक, $g(S)=h(f(S))$ किसी भी गैर घटते अवतल फलन के लिए उपप्रतिरूपक होता है .
एक यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय $T$ प्रत्येक तत्व के साथ चुना जाता है $\Omega$ में सम्मिलित किया जा रहा है $T$ संभाव्यता के साथ स्वतंत्र रूप से $p$ . तब निम्नलिखित असमानता सत्य होता है $\mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )$ जहाँ $\varnothing$ शून्य समुच्चय है. आत्याधिक सामान्यतौर पर निम्नलिखित यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय $S$ निम्नानुसार निर्मित किया गया है। प्रत्येक के लिए $1\leq i\leq l,A_{i}\subseteq \Omega$ कंस्ट्रक्ट $S_{i}$ प्रत्येक तत्व को सम्मिलित करके $A_{i}$ स्वतंत्र रूप से $S_{i}$ संभाव्यता के साथ $p_{i}$ . इसके अतिरिक्त चलो $S=\cup _{i=1}^{l}S_{i}$ . तब निम्नलिखित असमानता सत्य होता है $\mathbb {E} [f(S)]\geq \sum _{R\subseteq [l]}\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})$ .

अनुकूलन समस्याएँ

उपप्रतिरूपक फलन में ऐसे गुण होते हैं जो उत्तल फलन और अवतल फलन के समान होते हैं। इस कारण से, एक अनुकूलन समस्या जो उत्तल या अवतल फलन को अनुकूलित करने से संबंधित है, उसे कुछ बाधाओं के अधीन एक उपप्रतिरूपक फलन को अधिकतम या छोटा करने की समस्या के रूप में भी वर्णित किया जा सकता है।

उपप्रतिरूपक समुच्चय फलन न्यूनतमकरण

उपप्रतिरूपक समुच्चय फलन को न्यूनतम करने की कठोरता समस्या पर लगाई गई बाधाओं पर निर्भर करती है।

उपप्रतिरूपक फलन को न्यूनतम करने की अप्रतिबंधित समस्या बहुपद समय में गणना योग्य होता है,^[11]^[12]और जहाँ तक कि दृढ़-बहुपद समय में भी होता है।^[13]^[14]ग्राफ़ में न्यूनतम कटौती की गणना करना इस न्यूनतमकरण समस्या का एक विशेष स्थितियां होता है।
कार्डिनैलिटी निचली सीमा के साथ एक उपप्रतिरूपक फलन को कम करने की समस्या एनपी कठिन होता है, सन्निकटन कारक पर बहुपद कारक निचली सीमा के साथ होता है।^[15]^[16]

उपप्रतिरूपक समुच्चय फलन अधिकतमकरण

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

एक गैर-ऋणात्मक उपप्रतिरूपक फलन को अधिकतम करने की समस्या 1/2 सन्निकटन एल्गोरिथ्म को स्वीकार करती है।^[17]^[18]ग्राफ़ के अधिकतम कट की गणना करना इस समस्या का एक विशेष स्थितियां होता है।
कार्डिनैलिटी बाधा के अधीन एक मोनोटोन उपप्रतिरूपक फलन को अधिकतम करने की समस्या स्वीकार करती है $1-1/e$ सन्निकटन एल्गोरिथ्म.^[19]^[20] अधिकतम कवरेज समस्या इस समस्या का एक विशेष स्थितियां होता है।
मैट्रोइड बाधा (जो उपरोक्त स्थितियां को समाहित करता है) के अधीन एक मोनोटोन उपप्रतिरूपक फलन को अधिकतम करने की समस्या भी स्वीकार करती है $1-1/e$ सन्निकटन एल्गोरिथ्म.^[21]^[22]^[23]

इनमें से कई एल्गोरिदम को एल्गोरिदम के अर्ध-विभेदक आधारित ढांचे के भीतर एकीकृत किया जा सकता है।^[16]

अनुप्रयोग

अर्थशास्त्र, गेम थ्योरी, मशीन लर्निंग और कंप्यूटर दृष्टि जैसे कई वास्तविक दुनिया के अनुप्रयोगों में उपप्रतिरूपक फलन स्वाभाविक रूप से होते हैं।^[4]^[27]घटती रिटर्न संपत्ति के कारण, उपप्रतिरूपक फलन स्वाभाविक रूप से वस्तुओं की लागत को प्रतिमान करते हैं, क्योंकि अधिकांशतः एक बड़ी छूट होती है, जो आइटम खरीदता है उसमें वृद्धि होती है। उपप्रतिरूपक फलन कठिन, समानता और सहयोग की धारणाओं को प्रतिमान करते हैं जब वे न्यूनतमकरण समस्याओं में दिखाई देते हैं। दूसरी ओर,अधिकतमीकरण समस्याओं में, वे विविधता, सूचना और कवरेज की धारणाओं को प्रतिमान करते हैं।

यह भी देखें

उपप्रतिरूपक फलन
मैट्रोइड, पॉलीमेट्रोइड
उपयोगिता अविभाज्य वस्तुओं पर कार्य करती है

उद्धरण

↑ H. Lin and J. Bilmes, A Class of Submodular Functions for Document Summarization, ACL-2011.
↑ S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.
↑ A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.
↑ ^4.0 ^4.1 A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008
↑ (Schrijver 2003, §44, p. 766)
↑ Buchbinder, Niv; Feldman, Moran (2018). "Submodular Functions Maximization Problems". In Gonzalez, Teofilo F. (ed.). Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications. Chapman and Hall/CRC. doi:10.1201/9781351236423. ISBN 9781351236423.
↑ "सूचना प्रसंस्करण और सीखना" (PDF). cmu.
↑ Fujishige (2005) p.22
↑ Lovász, L. (1983). "Submodular functions and convexity". Mathematical Programming the State of the Art: 235–257. doi:10.1007/978-3-642-68874-4_10. ISBN 978-3-642-68876-8.
↑ Vondrák, Jan. "Polyhedral techniques in combinatorial optimization: Lecture 17" (PDF).
↑ Grötschel, M.; Lovasz, L.; Schrijver, A. (1981). "The ellipsoid method and its consequences in combinatorial optimization". Combinatorica. 1 (2): 169–197. doi:10.1007/BF02579273. hdl:10068/182482. S2CID 43787103.
↑ Cunningham, W. H. (1985). "On submodular function minimization". Combinatorica. 5 (3): 185–192. doi:10.1007/BF02579361. S2CID 33192360.
↑ Iwata, S.; Fleischer, L.; Fujishige, S. (2001). "A combinatorial strongly polynomial algorithm for minimizing submodular functions". J. ACM. 48 (4): 761–777. doi:10.1145/502090.502096. S2CID 888513.
↑ Schrijver, A. (2000). "A combinatorial algorithm minimizing submodular functions in strongly polynomial time". J. Combin. Theory Ser. B. 80 (2): 346–355. doi:10.1006/jctb.2000.1989.
↑ Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing (2011).
↑ ^16.0 ^16.1 R. Iyer, S. Jegelka and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).
↑ U. Feige, V. Mirrokni and J. Vondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.
↑ N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.
↑ Nemhauser, George; Wolsey, L. A.; Fisher, M. L. (1978). "An analysis of approximations for maximizing submodular set functions I". Mathematical Programming. 14 (14): 265–294. doi:10.1007/BF01588971. S2CID 206800425.
↑ Williamson, David P. "Bridging Continuous and Discrete Optimization: Lecture 23" (PDF).
↑ G. Calinescu, C. Chekuri, M. Pál and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.
↑ M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).
↑ Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.
↑ M. Narasimhan and J. Bilmes, A submodular-supermodular procedure with applications to discriminative structure learning, In Proc. UAI (2005).
↑ R. Iyer and J. Bilmes, Algorithms for Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).
↑ R. Iyer and J. Bilmes, Submodular Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).
↑ J. Bilmes, Submodularity in Machine Learning Applications, Tutorial at AAAI-2015.

संदर्भ

Schrijver, Alexander (2003), Combinatorial Optimization, Springer, ISBN 3-540-44389-4
Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
Fujishige, Satoru (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0-444-82523-1
Oxley, James G. (1992), Matroid theory, Oxford Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5, Zbl 0784.05002

बाहरी संबंध

http://www.cs.berkeley.edu/~stefje/references.html has a longer bibliography
http://submodularity.org/ includes further material on the subject

[LB-1] H. Lin and J. Bilmes, A Class of Submodular Functions for Document Summarization, ACL-2011.

[TIWB-2] S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.

[KG1-3] A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.

[KG-4] 4.0 ^4.1 A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008

[5] (Schrijver 2003, §44, p. 766)

[BF-6] Buchbinder, Niv; Feldman, Moran (2018). "Submodular Functions Maximization Problems". In Gonzalez, Teofilo F. (ed.). Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications. Chapman and Hall/CRC. doi:10.1201/9781351236423. ISBN 9781351236423.

[7] "सूचना प्रसंस्करण और सीखना" (PDF). cmu.

[F22-8] Fujishige (2005) p.22

[L-9] Lovász, L. (1983). "Submodular functions and convexity". Mathematical Programming the State of the Art: 235–257. doi:10.1007/978-3-642-68874-4_10. ISBN 978-3-642-68876-8.

[JV2-10] Vondrák, Jan. "Polyhedral techniques in combinatorial optimization: Lecture 17" (PDF).

[GLS-11] Grötschel, M.; Lovasz, L.; Schrijver, A. (1981). "The ellipsoid method and its consequences in combinatorial optimization". Combinatorica. 1 (2): 169–197. doi:10.1007/BF02579273. hdl:10068/182482. S2CID 43787103.

[Cunningham-12] Cunningham, W. H. (1985). "On submodular function minimization". Combinatorica. 5 (3): 185–192. doi:10.1007/BF02579361. S2CID 33192360.

[IFF-13] Iwata, S.; Fleischer, L.; Fujishige, S. (2001). "A combinatorial strongly polynomial algorithm for minimizing submodular functions". J. ACM. 48 (4): 761–777. doi:10.1145/502090.502096. S2CID 888513.

[Schrijver-14] Schrijver, A. (2000). "A combinatorial algorithm minimizing submodular functions in strongly polynomial time". J. Combin. Theory Ser. B. 80 (2): 346–355. doi:10.1006/jctb.2000.1989.

[SF-15] Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing (2011).

[IJB-16] 16.0 ^16.1 R. Iyer, S. Jegelka and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).

[FMV-17] U. Feige, V. Mirrokni and J. Vondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.

[BFNS-18] N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.

[NVF-19] Nemhauser, George; Wolsey, L. A.; Fisher, M. L. (1978). "An analysis of approximations for maximizing submodular set functions I". Mathematical Programming. 14 (14): 265–294. doi:10.1007/BF01588971. S2CID 206800425.

[20] Williamson, David P. "Bridging Continuous and Discrete Optimization: Lecture 23" (PDF).

[CCPV-21] G. Calinescu, C. Chekuri, M. Pál and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.

[FNS-22] M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).

[FW-23] Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.

[NB-24] M. Narasimhan and J. Bilmes, A submodular-supermodular procedure with applications to discriminative structure learning, In Proc. UAI (2005).

[IBUAI-25] R. Iyer and J. Bilmes, Algorithms for Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).

[IB-26] R. Iyer and J. Bilmes, Submodular Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).

[JB-27] J. Bilmes, Submodularity in Machine Learning Applications, Tutorial at AAAI-2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

@@ Line 1: / Line 1: @@
 {{Short description|Set-to-real map with diminishing returns}}
-गणित में, एक  '''उपप्रतिरूपक''' '''समुच्चय फलन''' ('''सबमॉड्यूलर सेट फ़ंक्शन''') (जिसे '''सबमॉड्यूलर फलन''' के रूप में भी जाना जाता है) एक समुच्चय फलन होता है, जिसका मूल्य,अनौपचारिक रूप से, यह गुण रखता है कि इनपुट समुच्चय में जोड़े जाने पर एकल तत्व जो फलन बनाता है, उसके वृद्धिशील मूल्य में अंतर इनपुट समुच्चय का आकार बढ़ने के साथ घटता जाता है। सबमॉड्यूलर फलन में एक प्राकृतिक ह्रासमान रिटर्न गुण होता है जो उन्हें कई अनुप्रयोगों के लिए उपयुक्त बनाता है, जिसमें [[सन्निकटन एल्गोरिदम]], [[ खेल सिद्धांत | खेल सिद्धांत]] (उपयोगकर्ता प्राथमिकताओं को मॉडलिंग करने वाले फलन के रूप में) और [[विद्युत नेटवर्क]] सम्मिलित होता हैं। हाल ही में,[[ यंत्र अधिगम | यंत्र अधिगम]] और [[ कृत्रिम होशियारी | कृत्रिम होशियारी]] में कई वास्तविक दुनिया की समस्याओं में सबमॉड्यूलर फलन को अत्यधिक उपयोगिता मिली है, जिसमें [[स्वचालित सारांशीकरण]], [[बहु-दस्तावेज़ सारांशीकरण]], फ़ीचर चयन, [[सक्रिय शिक्षण (मशीन लर्निंग)]], सेंसर प्लेसमेंट, छवि संग्रह सारांशीकरण और कई अन्य डोमेन सम्मिलित होता हैं।<ref name="LB" /><ref name="TIWB" /><ref name="KG1" /><ref name="KG" />
+गणित में, एक '''उपप्रतिरूपक''' '''समुच्चय फलन''' (जिसे '''उपप्रतिरूपक''' '''फलन''' के रूप में भी जाना जाता है) एक समुच्चय फलन होता है, जिसका मूल्य,अनौपचारिक रूप से, यह गुण रखता है कि इनपुट समुच्चय में जोड़े जाने पर एकल तत्व जो फलन बनाता है, उसके वृद्धिशील मूल्य में अंतर इनपुट समुच्चय का आकार बढ़ने के साथ घटता जाता है। उपप्रतिरूपक फलन में एक प्राकृतिक ह्रासमान रिटर्न गुण होता है जो उन्हें कई अनुप्रयोगों के लिए उपयुक्त बनाता है, जिसमें [[सन्निकटन एल्गोरिदम]], [[ खेल सिद्धांत | खेल सिद्धांत]] (उपयोगकर्ता प्राथमिकताओं को प्रतिरूपक करने वाले फलन के रूप में) और [[विद्युत नेटवर्क]] सम्मिलित होता हैं। हाल ही में,[[ यंत्र अधिगम | यंत्र अधिगम]] और [[ कृत्रिम होशियारी | कृत्रिम होशियारी]] में कई वास्तविक दुनिया की समस्याओं में उपप्रतिरूपक फलन को अत्यधिक उपयोगिता मिली है, जिसमें [[स्वचालित सारांशीकरण]], [[बहु-दस्तावेज़ सारांशीकरण]], फ़ीचर चयन, [[सक्रिय शिक्षण (मशीन लर्निंग)]], सेंसर प्लेसमेंट, छवि संग्रह सारांशीकरण और कई अन्य डोमेन सम्मिलित होता हैं।<ref name="LB" /><ref name="TIWB" /><ref name="KG1" /><ref name="KG" />
 == परिभाषा ==
-अगर <math>\Omega</math> एक परिमित समुच्चय [[सेट (गणित)|(गणित)]] है, सबमॉड्यूलर फलन एक समुच्चय फलन है <math>f:2^{\Omega}\rightarrow \mathbb{R}</math>, जहाँ <math>2^\Omega</math> पावर समुच्चय को दर्शाता है उपसमुच्चय को कार्यों के रूप में प्रस्तुत करना <math>\Omega</math>, जो निम्नलिखित समकक्ष शर्तों में से एक को संतुष्ट करता है।<ref>{{Harvard citations|last = Schrijver|year = 2003|loc = §44, p. 766|nb = }}</ref>
+अगर <math>\Omega</math> एक परिमित समुच्चय [[सेट (गणित)|(गणित)]] है, उपप्रतिरूपक फलन एक समुच्चय फलन है <math>f:2^{\Omega}\rightarrow \mathbb{R}</math>, जहाँ <math>2^\Omega</math> पावर समुच्चय को दर्शाता है उपसमुच्चय को कार्यों के रूप में प्रस्तुत करना <math>\Omega</math>, जो निम्नलिखित समकक्ष शर्तों में से एक को संतुष्ट करता है।<ref>{{Harvard citations|last = Schrijver|year = 2003|loc = §44, p. 766|nb = }}</ref>
 # सभी के लिए <math>X, Y \subseteq \Omega</math> साथ <math> X \subseteq Y</math> और हर <math>x \in \Omega \setminus Y</math> हमारे पास वह है <math>f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)</math>.
 # सभी के लिए <math>S, T \subseteq \Omega</math> हमारे पास वह है <math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>.
 # सभी के लिए <math>X\subseteq \Omega</math> और <math>x_1,x_2\in \Omega\backslash X</math> ऐसा है कि <math>x_1\neq x_2</math> हमारे पास वह है <math>f(X\cup \{x_1\})+f(X\cup \{x_2\})\geq f(X\cup \{x_1,x_2\})+f(X)</math>.
-एक नॉननेगेटिव सबमोड्युलर भी एक [[सबएडिटिव सेट फ़ंक्शन|सबएडिटिव समुच्चय फलन]] है, लेकिन एक '''सबएडिटिव''' फलन को सबमॉड्यूलर होने की आवश्यकता नहीं होता है।
+एक गैर-ऋणात्मक उपप्रतिरूपक भी एक [[सबएडिटिव सेट फ़ंक्शन|सबएडिटिव समुच्चय फलन]] है, लेकिन एक सबएडिटिव फलन को उपप्रतिरूपक होने की आवश्यकता नहीं होता है।
 अगर <math>\Omega</math> यदि इसे परिमित नहीं माना जाता है, तो उपरोक्त स्थितियाँ समतुल्य नहीं होता हैं। विशेष रूप से एक समारोह
@@ Line 14: / Line 14: @@
 उपरोक्त पहली शर्त को संतुष्ट करता है, लेकिन दूसरी शर्त विफल हो जाती है <math>S</math> और <math>T</math> परिमित प्रतिच्छेदन वाले अनंत समुच्चय होता हैं।
-== सबमॉड्यूलर फलन के प्रकार और उदाहरण ==
+== उपप्रतिरूपक फलन के प्रकार और उदाहरण ==
 === मोनोटोन ===
-एक समुच्चय फलन <math>f</math> यदि प्रत्येक के लिए एकरस है <math>T\subseteq S</math> हमारे पास वह है <math>f(T)\leq f(S)</math>. मोनोटोन सबमॉड्यूलर फलन के उदाहरणों में सम्मिलित होता हैं:
+एक समुच्चय फलन <math>f</math> यदि प्रत्येक के लिए एकरस है <math>T\subseteq S</math> हमारे पास वह है <math>f(T)\leq f(S)</math>. मोनोटोन उपप्रतिरूपक फलन के उदाहरणों में सम्मिलित होता हैं:
-; रैखिक (मॉड्यूलर) फलन : प्रपत्र का कोई भी कार्य <math>f(S)=\sum_{i\in S}w_i</math> एक रैखिक फलन कहलाता है। इसके अतिरिक्त यदि <math>\forall i,w_i\geq 0</math> तब f एकस्वर होता है।
+; रैखिक (प्रतिरूपक) फलन: प्रपत्र का कोई भी कार्य <math>f(S)=\sum_{i\in S}w_i</math> एक रैखिक फलन कहलाता है। इसके अतिरिक्त यदि <math>\forall i,w_i\geq 0</math> तब f एकस्वर होता है।
 ; [[बजट-योगात्मक मूल्यांकन]]: प्रपत्र का कोई भी कार्य <math>f(S)=\min\left\{B,~\sum_{i\in S}w_i\right\}</math> प्रत्येक के लिए <math>w_i\geq 0</math> और <math>B\geq 0</math> बजट योगात्मक कहा जाता है।<ref name="BF" />; कवरेज फलन: चलो <math>\Omega=\{E_1,E_2,\ldots,E_n\}</math> कुछ मैंट्रोइड के उपसमुच्चय का संग्रह बनें <math>\Omega'</math>. कार्यक्रम <math>f(S)=\left|\bigcup_{E_i\in S}E_i\right|</math> के लिए <math>S\subseteq \Omega</math> कवरेज फलन कहा जाता है. इसे तत्वों में गैर-नकारात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
-; [[एन्ट्रॉपी (सूचना सिद्धांत)]]: <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> [[यादृच्छिक चर]] का एक समुच्चय बना होता है। फिर किसी के लिए <math>S\subseteq \Omega</math> हमारे पास वह है <math>H(S)</math> एक सबमॉड्यूलर फलन होता है, जहां <math>H(S)</math> यादृच्छिक चर के समुच्चय की एन्ट्रापी होता है <math>S</math>, एक तथ्य जिसे एंट्रोपिक वेक्टर शैनन-प्रकार की असमानताएं और Γn|शैनन की असमानता के रूप में जाना जाता है।<ref>{{Cite web|url = https://www.cs.cmu.edu/~aarti/Class/10704_Spring15/lecs/lec3.pdf|title = सूचना प्रसंस्करण और सीखना|publisher = cmu}}</ref> एन्ट्रॉपी फलन के लिए और भी असमानताएँ बनी रहने के लिए जानी जाती हैं, [[एन्ट्रोपिक वेक्टर]] देखा जाता है।
+; [[एन्ट्रॉपी (सूचना सिद्धांत)]]: <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> [[यादृच्छिक चर]] का एक समुच्चय बना होता है। फिर किसी के लिए <math>S\subseteq \Omega</math> हमारे पास वह है <math>H(S)</math> एक उपप्रतिरूपक फलन होता है, जहां <math>H(S)</math> यादृच्छिक चर के समुच्चय की एन्ट्रापी होता है <math>S</math>, एक तथ्य जिसे एंट्रोपिक सदिश शैनन-प्रकार की असमानताएं और Γn|शैनन की असमानता के रूप में जाना जाता है।<ref>{{Cite web|url = https://www.cs.cmu.edu/~aarti/Class/10704_Spring15/lecs/lec3.pdf|title = सूचना प्रसंस्करण और सीखना|publisher = cmu}}</ref> एन्ट्रॉपी फलन के लिए और भी असमानताएँ बनी रहने के लिए जानी जाती हैं, [[एन्ट्रोपिक वेक्टर]] देखा जाता है।
-; [[मैट्रोइड रैंक|मैट्रोइड रैंक फलन]] : <math>\Omega=\{e_1,e_2,\dots,e_n\}</math> वह ग्राउंड समुच्चय हो जिस पर मैट्रोइड को परिभाषित किया गया है। फिर मैट्रोइड का रैंक फलन एक सबमॉड्यूलर फलन होता है।<ref name=F22>Fujishige (2005) p.22</ref>
+; [[मैट्रोइड रैंक|मैट्रोइड रैंक फलन]] : <math>\Omega=\{e_1,e_2,\dots,e_n\}</math> वह ग्राउंड समुच्चय हो जिस पर मैट्रोइड को परिभाषित किया गया है। फिर मैट्रोइड का रैंक फलन एक उपप्रतिरूपक फलन होता है।<ref name=F22>Fujishige (2005) p.22</ref>
-=== गैर-नीरस ===
+=== नॉन - मोनोटोन ===
-एक सबमॉड्यूलर फलन जो मोनोटोन नहीं है उसे नॉन-मोनोटोन कहा जाता है।
+एक उपप्रतिरूपक फलन जो मोनोटोन नहीं है उसे नॉन-मोनोटोन कहा जाता है।
 ==== सममित ====
-एक गैर-मोनोटोन सबमॉड्यूलर फलन <math>f</math> यदि प्रत्येक के लिए सममित कहा जाता है <math>S\subseteq \Omega</math> हमारे पास वह है <math>f(S)=f(\Omega-S)</math>.
+एक नॉन-मोनोटोन उपप्रतिरूपक फलन <math>f</math> यदि प्रत्येक के लिए सममित कहा जाता है <math>S\subseteq \Omega</math> हमारे पास वह है <math>f(S)=f(\Omega-S)</math>.
-सममित गैर-मोनोटोन सबमॉड्यूलर फलन के उदाहरणों में सम्मिलित होता हैं:
+सममित नॉन-मोनोटोन उपप्रतिरूपक फलन के उदाहरणों में सम्मिलित होता हैं:
-; ग्राफ़ कट्स: <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> एक [[ग्राफ़ (अलग गणित)]] के शीर्ष बना होता है। शीर्षों के किसी भी समुच्चय के लिए <math>S\subseteq \Omega</math> होने देना <math>f(S)</math> किनारों की संख्या को निरूपित करें <math>e=(u,v)</math> ऐसा है कि <math>u\in S</math> और <math>v\in \Omega-S</math>. इसे किनारों पर गैर-नकारात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
+; ग्राफ़ कट्स: <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> एक [[ग्राफ़ (अलग गणित)]] के शीर्ष बना होता है। शीर्षों के किसी भी समुच्चय के लिए <math>S\subseteq \Omega</math> होने देना <math>f(S)</math> किनारों की संख्या को निरूपित करें <math>e=(u,v)</math> ऐसा है कि <math>u\in S</math> और <math>v\in \Omega-S</math>. इसे किनारों पर गैर-ऋणात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
-; [[आपसी जानकारी]]: <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> यादृच्छिक चर का एक समुच्चय बना होता है। फिर किसी के लिए <math>S\subseteq \Omega</math> हमारे पास वह है <math>f(S)=I(S;\Omega-S)</math> एक सबमॉड्यूलर फलन है, जहां <math>I(S;\Omega-S)</math> आपसी जानकारी होता है.
+; [[आपसी जानकारी]]: <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> यादृच्छिक चर का एक समुच्चय बना होता है। फिर किसी के लिए <math>S\subseteq \Omega</math> हमारे पास वह है <math>f(S)=I(S;\Omega-S)</math> एक उपप्रतिरूपक फलन है, जहां <math>I(S;\Omega-S)</math> आपसी जानकारी होता है.
 ==== असममित ====
-एक गैर-मोनोटोन सबमॉड्यूलर फलन जो सममित नहीं है, असममित कहलाता है।
+एक नॉन-मोनोटोन उपप्रतिरूपक फलन जो सममित नहीं है, असममित कहलाता है।
-; निर्देशित कटौती : <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> एक [[निर्देशित ग्राफ]] के शीर्ष बना होता है। शीर्षों के किसी भी समुच्चय के लिए <math>S\subseteq \Omega</math> होने देना <math>f(S)</math> किनारों की संख्या को निरूपित करें <math>e=(u,v)</math> ऐसा है कि <math>u\in S</math> और <math>v\in \Omega-S</math>. इसे निर्देशित किनारों पर गैर-नकारात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
+; निर्देशित कटौती : <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> एक [[निर्देशित ग्राफ]] के शीर्ष बना होता है। शीर्षों के किसी भी समुच्चय के लिए <math>S\subseteq \Omega</math> होने देना <math>f(S)</math> किनारों की संख्या को निरूपित करें <math>e=(u,v)</math> ऐसा है कि <math>u\in S</math> और <math>v\in \Omega-S</math>. इसे निर्देशित किनारों पर गैर-ऋणात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
 == सतत विस्तार ==
 === परिभाषा ===
-एक समुच्चय फलन <math>f:2^{\Omega}\rightarrow \mathbb{R}</math> साथ <math>|\Omega|=n</math> को फलन के रूप में भी दर्शाया जा सकता है <math>\{0, 1\}^{n}</math>, प्रत्येक को संबद्ध करके <math>S\subseteq \Omega</math> एक बाइनरी वेक्टर के साथ <math>x^{S}\in \{0, 1\}^{n}</math> ऐसा है कि <math>x_{i}^{S}=1</math> जब  <math>i\in S</math>, और <math>x_{i}^{S}=0</math> अन्यथा।
+एक समुच्चय फलन <math>f:2^{\Omega}\rightarrow \mathbb{R}</math> साथ <math>|\Omega|=n</math> को फलन के रूप में भी दर्शाया जा सकता है <math>\{0, 1\}^{n}</math>, प्रत्येक को संबद्ध करके <math>S\subseteq \Omega</math> एक बाइनरी सदिश के साथ <math>x^{S}\in \{0, 1\}^{n}</math> ऐसा है कि <math>x_{i}^{S}=1</math> जब  <math>i\in S</math>, और <math>x_{i}^{S}=0</math> अन्यथा।
 निरंतर रेस्ट्रिक्शन_(गणित) विस्तार_का_एक_फलन का <math>f</math> किसी भी सतत कार्य के रूप में परिभाषित किया गया है <math>F:[0, 1]^{n}\rightarrow \mathbb{R}</math> जैसे कि यह के मूल्य से मिलता हो <math>f</math> पर <math>x\in \{0, 1\}^{n}</math>, अर्थात होता है। <math>F(x^{S})=f(S)</math>.
-सबमॉड्यूलर फलन के संदर्भ में, निरंतर विस्तार के कुछ उदाहरण हैं जो सामान्यतौर पर उपयोग किए जाते हैं, जिनका वर्णन इस प्रकार होता है।
+उपप्रतिरूपक फलन के संदर्भ में, निरंतर विस्तार के कुछ उदाहरण हैं जो सामान्यतौर पर उपयोग किए जाते हैं, जिनका वर्णन इस प्रकार होता है।
 === उदाहरण ===
 ==== राइडर विस्तार ====
-इस विस्तार का नाम गणितज्ञ लास्ज़लो लोवाज़ के नाम पर रखा गया है।<ref name="L" />किसी भी वेक्टर पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. तब राइडर विस्तार को इस प्रकार परिभाषित किया गया है <math>f^L(\mathbf{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> जहां उम्मीद खत्म हो गई <math>\lambda</math> अंतराल पर [[समान वितरण (निरंतर)]] से चुना गया <math>[0,1]</math>. राइडर विस्तार एक उत्तल फलन है यदि <math>f</math> एक सबमॉड्यूलर फलन होता है.
+इस विस्तार का नाम गणितज्ञ लास्ज़लो लोवाज़ के नाम पर रखा गया है।<ref name="L" />किसी भी सदिश पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. तब राइडर विस्तार को इस प्रकार परिभाषित किया गया है <math>f^L(\mathbf{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> जहां उम्मीद खत्म हो गई <math>\lambda</math> अंतराल पर [[समान वितरण (निरंतर)]] से चुना गया <math>[0,1]</math>. राइडर विस्तार एक उत्तल फलन है यदि <math>f</math> एक उपप्रतिरूपक फलन होता है.
 ==== बहुरेखीय विस्तार ====
-किसी भी वेक्टर पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\ldots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. फिर बहुरेखीय विस्तार को इस प्रकार परिभाषित किया गया है <math>F(\mathbf{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>.
+किसी भी सदिश पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\ldots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. फिर बहुरेखीय विस्तार को इस प्रकार परिभाषित किया गया है <math>F(\mathbf{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>.
 ==== उत्तल समापन ====
-किसी भी वेक्टर पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. फिर उत्तल समापन को इस प्रकार परिभाषित किया गया है <math>f^-(\mathbf{x})=\min\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>. किसी भी समुच्चय फलन का उत्तल समापन उत्तल होता है <math>[0,1]^n</math>.
+किसी भी सदिश पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. फिर उत्तल समापन को इस प्रकार परिभाषित किया गया है <math>f^-(\mathbf{x})=\min\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>. किसी भी समुच्चय फलन का उत्तल समापन उत्तल होता है <math>[0,1]^n</math>.
 ==== अवतल सिमित होना ====
-किसी भी '''वेक्टर''' पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. फिर अवतल समापन को इस प्रकार परिभाषित किया गया है <math>f^+(\mathbf{x})=\max\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>.
+किसी भी सदिश पर विचार करें <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> ऐसा कि प्रत्येक <math>0\leq x_i\leq 1</math>. फिर अवतल समापन को इस प्रकार परिभाषित किया गया है <math>f^+(\mathbf{x})=\max\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>.
 === विस्तार के बीच कनेक्शन ===
-ऊपर चर्चा किए गए विस्तार के लिए, यह दिखाया जा सकता है <math>f^{+}(\mathbf{x}) \geq F(\mathbf{x}) \geq f^{-}(\mathbf{x})=f^L(\mathbf{x})</math> जब <math>f</math> सबमॉड्यूलर होता है.<ref name="JV2" />
+ऊपर चर्चा किए गए विस्तार के लिए, यह दिखाया जा सकता है <math>f^{+}(\mathbf{x}) \geq F(\mathbf{x}) \geq f^{-}(\mathbf{x})=f^L(\mathbf{x})</math> जब <math>f</math> उपप्रतिरूपक होता है.<ref name="JV2" />
 == गुण ==
-# सबमॉड्यूलर फलन का वर्ग गैर-नकारात्मक [[रैखिक संयोजन]] के तहत सिमित (गणित) होता है। किसी भी सबमॉड्यूलर फलन पर विचार करें <math>f_1,f_2,\ldots,f_k</math> और गैर-'''नकारात्मक''' संख्याएँ <math>\alpha_1,\alpha_2,\ldots,\alpha_k</math>. फिर फलन <math>g</math> द्वारा परिभाषित <math>g(S)=\sum_{i=1}^k \alpha_i f_i(S)</math> सबमॉड्यूलर होता है.
+# उपप्रतिरूपक फलन का वर्ग गैर-ऋणात्मक [[रैखिक संयोजन]] के तहत सिमित (गणित) होता है। किसी भी उपप्रतिरूपक फलन पर विचार करें <math>f_1,f_2,\ldots,f_k</math> और गैर-ऋणात्मक संख्याएँ <math>\alpha_1,\alpha_2,\ldots,\alpha_k</math>. फिर फलन <math>g</math> द्वारा परिभाषित <math>g(S)=\sum_{i=1}^k \alpha_i f_i(S)</math> उपप्रतिरूपक होता है.
-#किसी भी सबमॉड्यूलर फलन के लिए <math>f</math>, द्वारा परिभाषित फलन <math>g(S)=f(\Omega \setminus S)</math> '''सबमॉड्यूलर''' होता है.
+#किसी भी उपप्रतिरूपक फलन के लिए <math>f</math>, द्वारा परिभाषित फलन <math>g(S)=f(\Omega \setminus S)</math> उपप्रतिरूपक होता है.
-#कार्यक्रम <math>g(S)=\min(f(S),c)</math>, जहाँ <math>c</math> एक वास्तविक संख्या है, जब भी सबमॉड्यूलर होता है <math>f</math> मोनोटोन सबमॉड्यूलर है. सामान्यतौर पर अत्यधिक, <math>g(S)=h(f(S))</math> किसी भी गैर घटते अवतल फलन के लिए सबमॉड्यूलर होता है .
+#कार्यक्रम <math>g(S)=\min(f(S),c)</math>, जहाँ <math>c</math> एक वास्तविक संख्या है, जब भी उपप्रतिरूपक होता है <math>f</math> मोनोटोन उपप्रतिरूपक है. सामान्यतौर पर अत्यधिक, <math>g(S)=h(f(S))</math> किसी भी गैर घटते अवतल फलन के लिए उपप्रतिरूपक होता है .
-# एक यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय <math>T</math> प्रत्येक तत्व के साथ चुना जाता है <math>\Omega</math> में सम्मिलित किया जा रहा है <math>T</math> संभाव्यता के साथ स्वतंत्र रूप से <math>p</math>. तब निम्नलिखित असमानता सत्य होता है <math>\mathbb{E}[f(T)]\geq p f(\Omega)+(1-p) f(\varnothing)</math> जहाँ <math>\varnothing</math> '''खाली''' समुच्चय है. आत्याधिक सामान्यतौर पर निम्नलिखित यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय <math>S</math> निम्नानुसार निर्मित किया गया है। प्रत्येक के लिए <math>1\leq i\leq l, A_i\subseteq \Omega</math> कंस्ट्रक्ट <math>S_i</math> प्रत्येक तत्व को सम्मिलित करके <math>A_i</math> स्वतंत्र रूप से <math>S_i</math> संभाव्यता के साथ <math>p_i</math>. इसके अलावा चलो <math>S=\cup_{i=1}^l S_i</math>. तब निम्नलिखित असमानता सत्य होता है <math>\mathbb{E}[f(S)]\geq \sum_{R\subseteq [l]} \Pi_{i\in R}p_i \Pi_{i\notin R}(1-p_i)f(\cup_{i\in R}A_i)</math>.
+# एक यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय <math>T</math> प्रत्येक तत्व के साथ चुना जाता है <math>\Omega</math> में सम्मिलित किया जा रहा है <math>T</math> संभाव्यता के साथ स्वतंत्र रूप से <math>p</math>. तब निम्नलिखित असमानता सत्य होता है <math>\mathbb{E}[f(T)]\geq p f(\Omega)+(1-p) f(\varnothing)</math> जहाँ <math>\varnothing</math> शून्य समुच्चय है. आत्याधिक सामान्यतौर पर निम्नलिखित यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय <math>S</math> निम्नानुसार निर्मित किया गया है। प्रत्येक के लिए <math>1\leq i\leq l, A_i\subseteq \Omega</math> कंस्ट्रक्ट <math>S_i</math> प्रत्येक तत्व को सम्मिलित करके <math>A_i</math> स्वतंत्र रूप से <math>S_i</math> संभाव्यता के साथ <math>p_i</math>. इसके अतिरिक्त चलो <math>S=\cup_{i=1}^l S_i</math>. तब निम्नलिखित असमानता सत्य होता है <math>\mathbb{E}[f(S)]\geq \sum_{R\subseteq [l]} \Pi_{i\in R}p_i \Pi_{i\notin R}(1-p_i)f(\cup_{i\in R}A_i)</math>.
 == [[अनुकूलन समस्या]]एँ ==
-सबमॉड्यूलर फलन में ऐसे गुण होते हैं जो उत्तल फलन और अवतल फलन के समान होते हैं। इस कारण से, एक अनुकूलन समस्या जो उत्तल या अवतल फलन को अनुकूलित करने से संबंधित है, उसे कुछ बाधाओं के अधीन एक सबमॉड्यूलर फलन को अधिकतम या छोटा करने की समस्या के रूप में भी वर्णित किया जा सकता है।
+उपप्रतिरूपक फलन में ऐसे गुण होते हैं जो उत्तल फलन और अवतल फलन के समान होते हैं। इस कारण से, एक अनुकूलन समस्या जो उत्तल या अवतल फलन को अनुकूलित करने से संबंधित है, उसे कुछ बाधाओं के अधीन एक उपप्रतिरूपक फलन को अधिकतम या छोटा करने की समस्या के रूप में भी वर्णित किया जा सकता है।
-=== सबमॉड्यूलर समुच्चय फलन न्यूनतमकरण ===
+=== उपप्रतिरूपक समुच्चय फलन न्यूनतमकरण ===
-सबमॉड्यूलर समुच्चय फलन को न्यूनतम करने की कठोरता समस्या पर लगाई गई बाधाओं पर निर्भर करती है।
+उपप्रतिरूपक समुच्चय फलन को न्यूनतम करने की कठोरता समस्या पर लगाई गई बाधाओं पर निर्भर करती है।
-# सबमॉड्यूलर फलन को न्यूनतम करने की अप्रतिबंधित समस्या बहुपद समय में गणना योग्य होता है,<ref name="GLS" /><ref name="Cunningham" />और जहाँ तक कि दृढ़-बहुपद समय में भी होता है।<ref name="IFF" /><ref name="Schrijver" />ग्राफ़ में [[न्यूनतम कटौती]] की गणना करना इस न्यूनतमकरण समस्या का एक विशेष स्थितियां होता है।
+# उपप्रतिरूपक फलन को न्यूनतम करने की अप्रतिबंधित समस्या बहुपद समय में गणना योग्य होता है,<ref name="GLS" /><ref name="Cunningham" />और जहाँ तक कि दृढ़-बहुपद समय में भी होता है।<ref name="IFF" /><ref name="Schrijver" />ग्राफ़ में [[न्यूनतम कटौती]] की गणना करना इस न्यूनतमकरण समस्या का एक विशेष स्थितियां होता है।
-# कार्डिनैलिटी निचली सीमा के साथ एक सबमॉड्यूलर फलन को कम करने की समस्या [[ एनपी कठिन | एनपी कठिन होता]] है, सन्निकटन कारक पर बहुपद कारक निचली सीमा के साथ होता है।<ref name="SF" /><ref name="IJB" />
+# कार्डिनैलिटी निचली सीमा के साथ एक उपप्रतिरूपक फलन को कम करने की समस्या [[ एनपी कठिन | एनपी कठिन होता]] है, सन्निकटन कारक पर बहुपद कारक निचली सीमा के साथ होता है।<ref name="SF" /><ref name="IJB" />
-=== सबमॉड्यूलर समुच्चय फलन अधिकतमकरण ===
+=== उपप्रतिरूपक समुच्चय फलन अधिकतमकरण ===
-न्यूनतमकरण के स्थितियां के विपरीत, एक सामान्य सबमॉड्यूलर फलन को अधिकतम करना अप्रतिबंधित सेटिंग में भी एनपी-हार्ड होता है। इस प्रकार, इस क्षेत्र में अधिकांश कार्य बहुपद-समय सन्निकटन एल्गोरिदम से संबंधित हैं, जिनमें [[लालची एल्गोरिदम]] या [[स्थानीय खोज (अनुकूलन)]] सम्मिलित होता हैं।
+न्यूनतमकरण के स्थितियां के विपरीत, एक सामान्य उपप्रतिरूपक फलन को अधिकतम करना अप्रतिबंधित सेटिंग में भी एनपी-हार्ड होता है। इस प्रकार, इस क्षेत्र में अधिकांश कार्य बहुपद-समय सन्निकटन एल्गोरिदम से संबंधित हैं, जिनमें [[लालची एल्गोरिदम]] या [[स्थानीय खोज (अनुकूलन)]] सम्मिलित होता हैं।
-# एक गैर-नकारात्मक सबमॉड्यूलर फलन को अधिकतम करने की समस्या 1/2 सन्निकटन एल्गोरिथ्म को स्वीकार करती है।<ref name="FMV" /><ref name="BFNS" />ग्राफ़ के अधिकतम कट की गणना करना इस समस्या का एक विशेष स्थितियां होता है।
+# एक गैर-ऋणात्मक उपप्रतिरूपक फलन को अधिकतम करने की समस्या 1/2 सन्निकटन एल्गोरिथ्म को स्वीकार करती है।<ref name="FMV" /><ref name="BFNS" />ग्राफ़ के अधिकतम कट की गणना करना इस समस्या का एक विशेष स्थितियां होता है।
-# कार्डिनैलिटी बाधा के अधीन एक मोनोटोन सबमॉड्यूलर फलन को अधिकतम करने की समस्या स्वीकार करती है <math>1 - 1/e</math> सन्निकटन एल्गोरिथ्म.<ref name="NVF" /><ref>{{Cite web|last=Williamson|first=David P.|title=Bridging Continuous and Discrete Optimization: Lecture 23|url=https://people.orie.cornell.edu/dpw/orie6334/lecture23.pdf}}</ref> [[अधिकतम कवरेज समस्या]] इस समस्या का एक विशेष स्थितियां होता है।
+# कार्डिनैलिटी बाधा के अधीन एक मोनोटोन उपप्रतिरूपक फलन को अधिकतम करने की समस्या स्वीकार करती है <math>1 - 1/e</math> सन्निकटन एल्गोरिथ्म.<ref name="NVF" /><ref>{{Cite web|last=Williamson|first=David P.|title=Bridging Continuous and Discrete Optimization: Lecture 23|url=https://people.orie.cornell.edu/dpw/orie6334/lecture23.pdf}}</ref> [[अधिकतम कवरेज समस्या]] इस समस्या का एक विशेष स्थितियां होता है।
-# मैट्रोइड बाधा (जो उपरोक्त स्थितियां को समाहित करता है) के अधीन एक मोनोटोन सबमॉड्यूलर फलन को अधिकतम करने की समस्या भी स्वीकार करती है <math>1 - 1/e</math> सन्निकटन एल्गोरिथ्म.<ref name="CCPV" /><ref name="FNS" /><ref name="FW" />
+# मैट्रोइड बाधा (जो उपरोक्त स्थितियां को समाहित करता है) के अधीन एक मोनोटोन उपप्रतिरूपक फलन को अधिकतम करने की समस्या भी स्वीकार करती है <math>1 - 1/e</math> सन्निकटन एल्गोरिथ्म.<ref name="CCPV" /><ref name="FNS" /><ref name="FW" />
 इनमें से कई एल्गोरिदम को एल्गोरिदम के अर्ध-विभेदक आधारित ढांचे के भीतर एकीकृत किया जा सकता है।<ref name="IJB" />
 ===संबंधित अनुकूलन समस्याएँ===
-सबमॉड्यूलर न्यूनतमकरण और अधिकतमीकरण के अलावा, सबमॉड्यूलर फलन से संबंधित कई अन्य प्राकृतिक अनुकूलन समस्याएं होता हैं।
+उपप्रतिरूपक न्यूनतमकरण और अधिकतमीकरण के अतिरिक्त, उपप्रतिरूपक फलन से संबंधित कई अन्य प्राकृतिक अनुकूलन समस्याएं होता हैं।
-# दो सबमॉड्यूलर फलन के बीच अंतर को कम करना<ref name="NB" />एनपी न केवल कठिन है, बल्कि अप्राप्य भी होता है।<ref name="IBUAI" />
+# दो उपप्रतिरूपक फलन के बीच अंतर को कम करना<ref name="NB" />एनपी न केवल कठिन है, बल्कि अप्राप्य भी होता है।<ref name="IBUAI" />
-# सबमॉड्यूलर स्तर समुच्चय बाधा के अधीन एक सबमॉड्यूलर फलन का न्यूनतमकरण/अधिकतमीकरण (जिसे सबमॉड्यूलर कवर या सबमॉड्यूलर नैपसेक बाधा के अधीन सबमॉड्यूलर अनुकूलन के रूप में भी जाना जाता है) सीमित सन्निकटन गारंटी को स्वीकार करता है।<ref name="IB" />औसत कल्याण को अधिकतम करने के लिए एक सबमॉड्यूलर फलन के आधार पर डेटा को विभाजित करना सबमॉड्यूलर कल्याण समस्या के रूप में जाना जाता है, जो सीमित सन्निकटन गारंटी को भी स्वीकार करता है (कल्याण अधिकतमकरण देखें) ।
+# उपप्रतिरूपक स्तर समुच्चय बाधा के अधीन उपप्रतिरूपक फलन का न्यूनतमकरण/अधिकतमीकरण (जिसे उपप्रतिरूपक कवर या उपप्रतिरूपक नैपसेक बाधा के अधीन उपप्रतिरूपक अनुकूलन के रूप में भी जाना जाता है) सीमित सन्निकटन गारंटी को स्वीकार करता है।<ref name="IB" />औसत कल्याण को अधिकतम करने के लिए एक उपप्रतिरूपक फलन के आधार पर डेटा को विभाजित करना उपप्रतिरूपक कल्याण समस्या के रूप में जाना जाता है, जो सीमित सन्निकटन गारंटी को भी स्वीकार करता है (कल्याण अधिकतमकरण देखें) ।
 == अनुप्रयोग ==
-[[अर्थशास्त्र]], गेम थ्योरी, मशीन लर्निंग और [[कंप्यूटर दृष्टि]] जैसे कई वास्तविक दुनिया के अनुप्रयोगों में सबमॉड्यूलर फलन स्वाभाविक रूप से होते हैं।<ref name="KG" /><ref name="JB" />घटती रिटर्न संपत्ति के कारण, सबमॉड्यूलर फलन स्वाभाविक रूप से वस्तुओं की लागत को प्रतिमान करते हैं, क्योंकि अधिकांशतः एक बड़ी छूट होती है, जो आइटम खरीदता है उसमें वृद्धि होती है। सबमॉड्यूलर फलन जटिलता, समानता और सहयोग की धारणाओं को प्रतिमान करते हैं जब वे न्यूनतमकरण समस्याओं में दिखाई देते हैं। दूसरी ओर,अधिकतमीकरण समस्याओं में, वे विविधता, सूचना और कवरेज की धारणाओं को प्रतिमान करते हैं।
+[[अर्थशास्त्र]], गेम थ्योरी, मशीन लर्निंग और [[कंप्यूटर दृष्टि]] जैसे कई वास्तविक दुनिया के अनुप्रयोगों में उपप्रतिरूपक फलन स्वाभाविक रूप से होते हैं।<ref name="KG" /><ref name="JB" />घटती रिटर्न संपत्ति के कारण, उपप्रतिरूपक फलन स्वाभाविक रूप से वस्तुओं की लागत को प्रतिमान करते हैं, क्योंकि अधिकांशतः एक बड़ी छूट होती है, जो आइटम खरीदता है उसमें वृद्धि होती है। उपप्रतिरूपक फलन कठिन, समानता और सहयोग की धारणाओं को प्रतिमान करते हैं जब वे न्यूनतमकरण समस्याओं में दिखाई देते हैं। दूसरी ओर,अधिकतमीकरण समस्याओं में, वे विविधता, सूचना और कवरेज की धारणाओं को प्रतिमान करते हैं।
 == यह भी देखें ==
-* [[सुपरमॉड्यूलर फ़ंक्शन|सुपरमॉड्यूलर फलन]]
+* उपप्रतिरूपक [[सुपरमॉड्यूलर फ़ंक्शन|फलन]]
 * मैट्रोइड, [[पॉलीमेट्रोइड]]
 * [[उपयोगिता अविभाज्य वस्तुओं पर कार्य करती है]]
@@ Line 136: / Line 136: @@
 * http://www.cs.berkeley.edu/~stefje/references.html has a longer bibliography
 * http://submodularity.org/ includes further material on the subject
-[[Category: संयुक्त अनुकूलन| संयुक्त अनुकूलन]] [[Category: सन्निकटन एल्गोरिदम| सन्निकटन एल्गोरिदम]] [[Category: मैट्रोइड सिद्धांत|मैट्रोइड सिद्धांत]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 26/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:मैट्रोइड सिद्धांत|मैट्रोइड सिद्धांत]]
+[[Category:संयुक्त अनुकूलन| संयुक्त अनुकूलन]]
+[[Category:सन्निकटन एल्गोरिदम| सन्निकटन एल्गोरिदम]]

Anonymous

Search

उपप्रतिरूपक समुच्चय फलन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:28, 21 August 2023

Contents

परिभाषा