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

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

परिभाषा

अगर $\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$ CONSTRUCT $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