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

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

परिभाषा

अगर $\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}\}$ कुछ matroid के उपसमुच्चय का संग्रह बनें $\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$ अन्यथा।

निरंतर Restriction_(mathematics)#Extension_of_a_function का $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))$ किसी भी गैर घटते अवतल फ़ंक्शन के लिए सबमॉड्यूलर है $h$.
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