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

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

परिभाषा

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

1. सभी के लिए $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)$.
2. सभी के लिए $S,T\subseteq \Omega$ हमारे पास वह है $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$.
3. सभी के लिए $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$ बजट योगात्मक कहा जाता है।; कवरेज फलन: चलो $\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|शैनन की असमानता के रूप में जाना जाता है। एन्ट्रॉपी फलन के लिए और भी असमानताएँ बनी रहने के लिए जानी जाती हैं, एन्ट्रोपिक वेक्टर देखा जाता है।

मैट्रोइड रैंक फलन

$\Omega =\{e_{1},e_{2},\dots ,e_{n}\}$ वह ग्राउंड समुच्चय हो जिस पर मैट्रोइड को परिभाषित किया गया है। फिर मैट्रोइड का रैंक फलन एक उपप्रतिरूपक फलन होता है।

नॉन - मोनोटोन

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

सममित

एक नॉन-मोनोटोन उपप्रतिरूपक फलन $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)$.

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

उदाहरण

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

इस विस्तार का नाम गणितज्ञ लास्ज़लो लोवाज़ के नाम पर रखा गया है।किसी भी सदिश पर विचार करें $\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$ उपप्रतिरूपक होता है.

गुण

1. उपप्रतिरूपक फलन का वर्ग गैर-ऋणात्मक रैखिक संयोजन के तहत सिमित (गणित) होता है। किसी भी उपप्रतिरूपक फलन पर विचार करें $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)$ उपप्रतिरूपक होता है.
2. किसी भी उपप्रतिरूपक फलन के लिए $f$, द्वारा परिभाषित फलन $g(S)=f(\Omega \setminus S)$ उपप्रतिरूपक होता है.
3. कार्यक्रम $g(S)=\min(f(S),c)$, जहाँ $c$ एक वास्तविक संख्या है, जब भी उपप्रतिरूपक होता है $f$ मोनोटोन उपप्रतिरूपक है. सामान्यतौर पर अत्यधिक, $g(S)=h(f(S))$ किसी भी गैर घटते अवतल फलन के लिए उपप्रतिरूपक होता है .
4. एक यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय $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})$.

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

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

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

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

1. उपप्रतिरूपक फलन को न्यूनतम करने की अप्रतिबंधित समस्या बहुपद समय में गणना योग्य होता है,और जहाँ तक ​​कि दृढ़-बहुपद समय में भी होता है।ग्राफ़ में न्यूनतम कटौती की गणना करना इस न्यूनतमकरण समस्या का एक विशेष स्थितियां होता है।
2. कार्डिनैलिटी निचली सीमा के साथ एक उपप्रतिरूपक फलन को कम करने की समस्या एनपी कठिन होता है, सन्निकटन कारक पर बहुपद कारक निचली सीमा के साथ होता है।

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

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

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

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

संबंधित अनुकूलन समस्याएँ

उपप्रतिरूपक न्यूनतमकरण और अधिकतमीकरण के अतिरिक्त, उपप्रतिरूपक फलन से संबंधित कई अन्य प्राकृतिक अनुकूलन समस्याएं होता हैं।

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

अनुप्रयोग

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

यह भी देखें

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

संदर्भ

• 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