हाइपरप्लेन पृथक्करण प्रमेय: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|On the existence of hyperplanes separating disjoint convex sets}} {{Infobox mathematical statement | name = Hyperplane separation theorem | image = Separat...")
 
No edit summary
 
(10 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{short description|On the existence of hyperplanes separating disjoint convex sets}}
{{short description|On the existence of hyperplanes separating disjoint convex sets}}[[ज्यामिति]] में, हाइपरप्लेन पृथक्करण प्रमेय, 'n'-आयामी [[यूक्लिडियन अंतरिक्ष|यूक्लिडियन स्पेस]] में [[उत्तल सेट|उत्तल समुच्चय]] पृथक्करण हेतु एक प्रमेय है। इसके कई संस्करण उपलब्ध है। प्रमेय के एक संस्करण में, यदि ये दोनों समुच्चय [[बंद सेट|संकुचित समुच्चय]] हैं और उनमें से कम से कम एक सघन समुच्चय है, तो उनके मध्य में एक हाइपरप्लेन है और उनके मध्य दो समानांतर हाइपरप्लेन भी किसी अंतराल से भिन्न हो गए हैं। दूसरे संस्करण में, यदि दोनों असंयुक्त उत्तल समुच्चय विवृत हैं, तो उनके मध्य एक हाइपरप्लेन है, परन्तु जरूरी नहीं कि कोई अंतराल हो। कोई अक्ष जो किसी अलग करने वाले हाइपरप्लेन के लिए अष्टभुजीय है, पृथक करने वाला अक्ष है, क्योंकि अक्ष पर उत्तल पिंडों के अष्टभुजीय प्रक्षेप असंयुक्त हैं।
{{Infobox mathematical statement
| name = Hyperplane separation theorem
| image = Separating axis theorem2008.png
| caption = Illustration of the hyperplane separation theorem.
| type = [[Theorem]]
| field = {{plainlist|
* [[Convex geometry]]
* [[Topological vector spaces]]
* [[Collision detection]]
}}
| statement =
| symbolic statement =
| conjectured by = [[Hermann Minkowski]]
| conjecture date =
| first stated by =
| first stated in =
| first proof by =
| first proof date =
| open problem = No
| known cases =
| implied by =
| equivalent to =
| generalizations = [[Hahn–Banach theorem#Hahn–Banach separation theorem|Hahn–Banach separation theorem]]
| consequences =
}}


[[ज्यामिति]] में, [[ hyperplane ]] पृथक्करण प्रमेय, 'एन'-आयामी [[यूक्लिडियन अंतरिक्ष]] में [[अलग करना सेट]] [[उत्तल सेट]] के बारे में एक प्रमेय है। कई समान संस्करण हैं। प्रमेय के एक संस्करण में, यदि ये दोनों सेट [[बंद सेट]] हैं और उनमें से कम से कम एक [[कॉम्पैक्ट सेट]] है, तो उनके बीच में एक हाइपरप्लेन है और उनके बीच दो समानांतर हाइपरप्लेन भी एक अंतर से अलग हो गए हैं। दूसरे संस्करण में, यदि दोनों असंयुक्त उत्तल सेट खुले हैं, तो उनके बीच एक हाइपरप्लेन है, लेकिन जरूरी नहीं कि कोई अंतराल हो। एक अक्ष जो एक अलग करने वाले हाइपरप्लेन के लिए ऑर्थोगोनल है, एक पृथक करने वाला अक्ष है, क्योंकि अक्ष पर उत्तल पिंडों के ऑर्थोगोनल प्रोजेक्शन (सेट सिद्धांत) असंयुक्त हैं।
हाइपरप्लेन पृथक्करण प्रमेय [[हरमन मिन्कोव्स्की]] के कारण है। हन-बनाक पृथक्करण प्रमेय स्थलीय सदिश स्थानों के परिणाम का सामान्यीकरण करता है।
 
हाइपरप्लेन पृथक्करण प्रमेय [[हरमन मिन्कोव्स्की]] के कारण है। हान-बनाक प्रमेय#हन-बनाक पृथक्करण प्रमेय|हन-बनाक पृथक्करण प्रमेय स्थलीय सदिश स्थानों के परिणाम का सामान्यीकरण करता है।


एक संबंधित परिणाम सहायक हाइपरप्लेन प्रमेय है।
एक संबंधित परिणाम सहायक हाइपरप्लेन प्रमेय है।


[[समर्थन वेक्टर यंत्र]] के संदर्भ में, ''सर्वश्रेष्ठ रूप से हाइपरप्लेन को अलग करना'' या ''अधिकतम-मार्जिन हाइपरप्लेन'' एक हाइपरप्लेन है जो बिंदुओं के दो उत्तल हल्स को अलग करता है और दोनों से [[समान दूरी]] पर है।<ref>{{cite book |first1=Trevor |last1=Hastie |author-link=Trevor Hastie |first2=Robert |last2=Tibshirani |author-link2=Robert Tibshirani |first3=Jerome |last3=Friedman |author-link3=Jerome H. Friedman |title=The Elements of Statistical Learning : Data Mining, Inference, and Prediction |location=New York |publisher=Springer |edition=Second |year=2008 |pages=129–135 |url=https://web.stanford.edu/~hastie/Papers/ESLII.pdf#page=148 }}</ref><ref>{{cite book |first1=Ian H. |last1=Witten |first2=Eibe |last2=Frank |first3=Mark A. |last3=Hall |first4=Christopher J. |last4=Pal |title=Data Mining: Practical Machine Learning Tools and Techniques |publisher=Morgan Kaufmann |year=2016 |edition=Fourth |pages=253–254 |isbn=9780128043578 |url=https://books.google.com/books?id=1SylCgAAQBAJ&pg=PA253 }}</ref><ref>{{cite book |first1=Marc Peter |last1=Deisenroth |first2=A. Aldo |last2=Faisal |first3=Cheng Soon |last3=Ong |title=मशीन लर्निंग के लिए गणित|publisher=Cambridge University Press |year=2020 |isbn=978-1-108-45514-5 |pages=337–338 }}</ref>
[[समर्थन वेक्टर यंत्र|समर्थन सदिश यंत्र]] के संदर्भ में, आदर्श पृथक्करण हाइपरप्लेन या अधिकतम-सीमा हाइपरप्लेन एक ऐसा हाइपरप्लेन होता है जो दो बिंदुगणित समूहों को पृथक्करण करता है और इन दोनों से समान दूरी पर स्थित होता है।<ref>{{cite book |first1=Trevor |last1=Hastie |author-link=Trevor Hastie |first2=Robert |last2=Tibshirani |author-link2=Robert Tibshirani |first3=Jerome |last3=Friedman |author-link3=Jerome H. Friedman |title=The Elements of Statistical Learning : Data Mining, Inference, and Prediction |location=New York |publisher=Springer |edition=Second |year=2008 |pages=129–135 |url=https://web.stanford.edu/~hastie/Papers/ESLII.pdf#page=148 }}</ref><ref>{{cite book |first1=Ian H. |last1=Witten |first2=Eibe |last2=Frank |first3=Mark A. |last3=Hall |first4=Christopher J. |last4=Pal |title=Data Mining: Practical Machine Learning Tools and Techniques |publisher=Morgan Kaufmann |year=2016 |edition=Fourth |pages=253–254 |isbn=9780128043578 |url=https://books.google.com/books?id=1SylCgAAQBAJ&pg=PA253 }}</ref><ref>{{cite book |first1=Marc Peter |last1=Deisenroth |first2=A. Aldo |last2=Faisal |first3=Cheng Soon |last3=Ong |title=मशीन लर्निंग के लिए गणित|publisher=Cambridge University Press |year=2020 |isbn=978-1-108-45514-5 |pages=337–338 }}</ref>
 
{{clear}}


== कथन और प्रमाण ==
== कथन और प्रमाण ==
सभी मामलों में मान लीजिए <math>A, B</math> असंयुक्त, अरिक्त और के उत्तल उपसमुच्चय होना <math>\R^n</math>. परिणामों का सारांश इस प्रकार है:
सभी स्थितियों में, मान लीजिए <math>A, B</math> असंयुक्त, अरिक्त और के उत्तल उपसमुच्चय <math>\R^n</math> है जिनके  परिणामों का सारांश इस प्रकार है:
{| class="wikitable"
{| class="wikitable"
|+summary table
|+summary table
Line 50: Line 21:
| <math>\leq c</math>               
| <math>\leq c</math>               
|-
|-
| closed compact
| संवृत तथा सघन
| closed
| संवृत
| <math>> c_1</math>             
| <math>> c_1</math>             
| <math>< c_2</math> with <math>c_2 < c_1</math>
| <math>< c_2</math> के साथ <math>c_2 < c_1</math>
|-
|-
| closed
| संवृत
| closed compact
| संवृत तथा सघन
| <math>> c_1</math>             
| <math>> c_1</math>             
| <math>< c_2</math> with <math>c_2 < c_1</math>
| <math>< c_2</math> के साथ <math>c_2 < c_1</math>
|-
|-
| open          
| विवृत          
|
|
| <math>> c</math>               
| <math>> c</math>               
| <math>\leq c</math>               
| <math>\leq c</math>               
|-
|-
| open          
| विवृत          
| open  
| विवृत  
| <math>> c</math>               
| <math>> c</math>               
| <math>< c</math>                   
| <math>< c</math>                   
|}
|}


{{math_theorem|name=Hyperplane separation theorem<ref>{{harvnb|Boyd|Vandenberghe|2004|loc=Exercise 2.22.}}</ref>|Let <math>A</math> and <math>B</math> be two disjoint nonempty convex subsets of <math>\R^n</math>. Then there exist a nonzero vector <math>v</math> and a real number <math>c</math> such that
{{math_theorem|name=Hyperplane separation theorem<ref>{{harvnb|Boyd|Vandenberghe|2004|loc=Exercise 2.22.}}</ref>|मान लीजिये की <math>A</math> and <math>B</math>  
<math>\R^n</math> का दो असम्बद्ध अरिक्त उत्तल उपसमुच्चय है तब एक ऐसा अशून्य सदिश <math>v</math> तथा एक वास्तविक संख्या <math>c</math> इस प्रकार उपलब्ध है की
:<math>\langle x, v \rangle \ge c \, \text{ and } \langle y, v \rangle \le c</math>
:<math>\langle x, v \rangle \ge c \, \text{ and } \langle y, v \rangle \le c</math>
for all <math>x</math> in <math>A</math> and <math>y</math> in <math>B</math>; i.e., the hyperplane <math>\langle \cdot, v \rangle = c</math>, <math>v</math> the normal vector, separates <math>A</math> and <math>B</math>.
सभी <math>x</math> में <math>A</math> तथा <math>y</math> में <math>B</math> के लिए समर्थित है; उदहारण हेतु एक हाइपरप्लेन <math>\langle \cdot, v \rangle = c</math>, <math>v</math> में सदिश <math>A</math> and <math>B</math> को पृथक करता है


If both sets are closed, and at least one of them is compact, then the separation can be strict, that is, <math>\langle x, v \rangle > c_1 \, \text{ and } \langle y, v \rangle < c_2</math> for some <math>c_1 > c_2</math>
यदि दोनों समुच्चय बंद हैं, और उनमें से कम से कम एक सघन है, तो पृथक्करण कठिन हो सकता है, उदाहरण के लिए, <math>\langle x, v \rangle > c_1 \, \text{और} \langle y, v \rangle < c_2</math> <math>c_1 > c_2</math> के लिए सत्य है
}}
}}


आयामों की संख्या परिमित होनी चाहिए। अनंत-आयामी स्थानों में दो बंद, उत्तल, असंयुक्त सेट के उदाहरण हैं जिन्हें एक बंद हाइपरप्लेन (एक हाइपरप्लेन जहां एक सतत रैखिक कार्यात्मक कुछ स्थिरांक के बराबर होता है) से अलग नहीं किया जा सकता है, यहां तक ​​कि कमजोर अर्थों में भी जहां असमानताएं सख्त नहीं हैं।<ref>[[Haïm Brezis]], ''Analyse fonctionnelle : théorie et applications'', 1983, remarque 4, p. 7.</ref>
आयामों की संख्या परिमित होनी चाहिए। अनंत-आयामी स्थानों में दो संवृत, उत्तल, असंयुक्त समुच्चय के उदाहरण हैं जिन्हें एक संवृत हाइपरप्लेन (एक हाइपरप्लेन जहां एक सतत रैखिक कार्यात्मक कुछ स्थिरांक के बराबर होता है) से अलग नहीं किया जा सकता है, यहां तक ​​कि कमजोर अर्थों में भी जहां असमानताएं सख्त नहीं हैं।<ref>[[Haïm Brezis]], ''Analyse fonctionnelle : théorie et applications'', 1983, remarque 4, p. 7.</ref>
यहाँ, परिकल्पना में सघनता को शिथिल नहीं किया जा सकता है; Hyperplane_separation_theorem#Counterexamples_and_uniqueness अनुभाग में एक उदाहरण देखें। पृथक्करण प्रमेय का यह संस्करण अनंत-आयाम का सामान्यीकरण करता है; सामान्यीकरण को आमतौर पर हैन-बनच_प्रमेय#Hahn.E2.80.93बनच_पृथक्करण_प्रमेय|हाह्न-बनाक पृथक्करण प्रमेय के रूप में जाना जाता है।
यहाँ, परिकल्पना में सघनता को शिथिल नहीं किया जा सकता है; इसका उदहारण आगे के अनुभाग में प्रदर्शित किया गया है। पृथक्करण प्रमेय का यह संस्करण अनंत-आयाम का सामान्यीकरण करता है; सामान्यीकरण को सामान्यतः हाह्न-बनाक पृथक्करण प्रमेय के रूप में जाना जाता है।


सबूत निम्नलिखित लेम्मा पर आधारित है:
जिसका प्रमाण निम्नलिखित लेम्मा पर आधारित है:


{{math_theorem|name=Lemma|Let <math>A</math> and <math>B</math> be two disjoint closed subsets of <math>\R^n</math>, and assume <math>A</math> is compact. Then there exist points <math>a_0 \in A</math> and <math>b_0 \in B</math> minimizing the distance <math>\|a - b\|</math> over <math>a \in A</math> and <math>b \in B</math>.}}
{{math_theorem|name=Lemma|Let <math>A</math> and <math>B</math> be two disjoint closed subsets of <math>\R^n</math>, and assume <math>A</math> is compact. Then there exist points <math>a_0 \in A</math> and <math>b_0 \in B</math> minimizing the distance <math>\|a - b\|</math> over <math>a \in A</math> and <math>b \in B</math>.}}
Line 94: Line 66:
For the second version of the theorem, suppose that A and B are disjoint, convex, and open.  Then they can be exhausted by sequences of compact, convex subsets <math>A^n</math> and <math>B^n</math>.  The first version of the theorem supplies a sequence of separating hyperplanes <math>H^n</math> which must have a subsequence that converges to a hyperplane <math>H</math>.  This hyperplane must separate <math>A</math> from <math>B</math>-->
For the second version of the theorem, suppose that A and B are disjoint, convex, and open.  Then they can be exhausted by sequences of compact, convex subsets <math>A^n</math> and <math>B^n</math>.  The first version of the theorem supplies a sequence of separating hyperplanes <math>H^n</math> which must have a subsequence that converges to a hyperplane <math>H</math>.  This hyperplane must separate <math>A</math> from <math>B</math>-->


[[File:Separating Hyperplanes Theorem.png|thumb|प्रमाण चित्रण।]]
{{Math proof|title=Proof of theorem|proof= We first prove the second case. (See the diagram.)
{{Math proof|title=Proof of theorem|proof= We first prove the second case. (See the diagram.)


Line 115: Line 86:
}}
}}


 
चूँकि एक पृथक्करण हाइपरप्लेन विवृत उत्तल समुच्चयों के आतंरिक भागों को नहीं काट सकता है, हमारे पास एक परिणाम है:
<!--The old proof:
{{Math proof|title=Proof of theorem|proof=
Given disjoint nonempty convex sets <math>A</math>, <math>B</math>, let
:<math>K = A + (-B) = \{ x - y \mid x \in A, y \in B \}.</math>
Since <math>-B</math> is convex and the [[Minkowski sum|sum]] of convex sets is convex, <math>K</math> is convex. By the lemma, the closure <math>\overline{K}</math> of <math>K</math>, which is convex, contains a vector <math>v</math> of minimum norm. Since <math>\overline{K}</math> is convex, for any <math>n</math> in <math>K</math>, the line segment
:<math>v + t(n - v), \, 0 \le t \le 1</math>
lies in <math>\overline{K}</math> and so
:<math>|v|^2 \le |v + t(n - v)|^2 = |v|^2 + 2 t \langle v, n - v \rangle + t^2|n-v|^2</math>.
For <math>0 < t \le 1</math>, we thus have:
:<math>0 \le 2 \langle v, n \rangle - 2 |v|^2 + t|n-v|^2</math>
and letting <math>t \to 0</math> gives: <math>\langle n, v \rangle \ge |v|^2</math>. Hence, for any x in <math>A</math> and <math>y</math> in <math>B</math>, we have: <math>\langle x - y, v \rangle \ge |v|^2</math>. Thus, if <math>v</math> is nonzero, the proof is complete since
:<math>\inf_{x \in A} \langle x, v \rangle \ge |v|^2 + \sup_{y \in B} \langle y, v \rangle.</math>
 
More generally (covering the case <math>v = 0</math>), let us first take the case when the interior of <math>K</math> is nonempty. The interior can be exhausted by a nested sequence of nonempty compact convex subsets <math>K_1\subset K_2\subset K_3\subset\cdots</math>  (namely, put <math> K_j \equiv [-j,j]^n \cap \{ x \in \text{int}(K) : d(x, (\text{int}(K))^c) \ge \frac{1}{j} \} </math>). Since 0 is not in <math>K</math>, each <math>K_n</math> contains a nonzero vector <math>v_n</math> of minimum length and by the argument in the early part, we have: <math>\langle x, v_n \rangle \ge 0</math> for any <math>x \in K_n</math>. We can normalize the <math>v_n</math>'s to have length one. Then the sequence <math>v_n</math> contains a convergent subsequence (because the [[n-sphere]] is compact) with limit <math>v</math>, which is nonzero. We have <math>\langle x, v \rangle \ge 0</math> for any <math>x</math> in the interior of <math>K</math> and by continuity the same holds for all <math>x</math> in <math>K</math>. We now finish the proof as before. Finally, if <math>K</math> has empty interior, the [[affine set]] that it spans has dimension less than that of the whole space. Consequently <math>K</math> is contained in some hyperplane <math>\langle \cdot, v \rangle = c</math>; thus, <math>\langle x, v \rangle \ge c</math> for all <math>x</math> in <math>K</math> and we finish the proof as before. <math>\square</math>
}}
-->
चूँकि एक अलग करने वाला हाइपरप्लेन खुले उत्तल सेटों के अंदरूनी हिस्सों को नहीं काट सकता है, हमारे पास एक परिणाम है:


{{math_theorem
{{math_theorem
Line 142: Line 96:
}}
}}


== संभावित चौराहों के साथ मामला ==
== संभावित प्रतिच्छेदन की स्थिति ==
अगर सेट करता है <math>A, B</math> संभावित चौराहे हैं, लेकिन उनके सापेक्ष इंटीरियर अलग हैं, तो पहले मामले का सबूत अभी भी बिना किसी बदलाव के लागू होता है, इस प्रकार उपज:
अगर समुच्चय करता है यदि समूह <math>A, B</math> में संभावित प्रतिच्छेदन होता है, परन्तु उनके सांदर्भिक आंतरिकों में पृथक्करण होता है, तो पहली स्थिति के प्रमाण, परिवर्तन के बिना ही लागू हो जाते है, जिससे निम्न परिणाम मिलता है:
{{math_theorem
{{math_theorem
| name = Separation theorem II|Let <math>A</math> and <math>B</math> be two nonempty convex subsets of <math>\R^n</math> with disjoint relative interiors. Then there exist a nonzero vector <math>v</math> and a real number <math>c</math> such that
| name = Separation theorem II|Let <math>A</math> and <math>B</math> be two nonempty convex subsets of <math>\R^n</math> with disjoint relative interiors. Then there exist a nonzero vector <math>v</math> and a real number <math>c</math> such that
Line 159: Line 113:
== प्रमेय का विलोम ==
== प्रमेय का विलोम ==


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


== प्रति उदाहरण और विशिष्टता ==
== प्रति उदाहरण और विशिष्टता ==
 
यदि A और B में से एक उत्तल नहीं है, तो कई संभावित प्रति उदाहरण हैं। उदाहरण के लिए, A और B संकेंद्रित वृत्त हो सकते हैं। एक अधिक सूक्ष्म प्रति उदाहरण वह है जिसमें ए और बी दोनों संवृत हैं परन्तु कोई भी सघन नहीं है। उदाहरण के लिए, यदि ए एक संवृत अर्ध समुच्चय है और बी हाइपरबोला के एक हाथ से घिरा हुआ है, तो कोई सख्ती से अलग करने वाला हाइपरप्लेन नहीं है:
[[File:Separating axis theorem2.svg|right|thumb|यदि निकायों में से एक उत्तल नहीं है तो प्रमेय लागू नहीं होता है।]]यदि ए या बी में से एक उत्तल नहीं है, तो कई संभावित प्रति उदाहरण हैं। उदाहरण के लिए, A और B संकेंद्रित वृत्त हो सकते हैं। एक अधिक सूक्ष्म प्रति उदाहरण वह है जिसमें ए और बी दोनों बंद हैं लेकिन कोई भी कॉम्पैक्ट नहीं है। उदाहरण के लिए, यदि ए एक बंद आधा विमान है और बी हाइपरबोला के एक हाथ से घिरा हुआ है, तो कोई सख्ती से अलग करने वाला हाइपरप्लेन नहीं है:


:<math>A = \{(x,y) : x \le 0\}</math>
:<math>A = \{(x,y) : x \le 0\}</math>
:<math>B = \{(x,y) : x > 0, y \geq 1/x \}.\ </math>
:<math>B = \{(x,y) : x > 0, y \geq 1/x \}.\ </math>
(हालांकि, दूसरे प्रमेय के एक उदाहरण से, एक हाइपरप्लेन है जो उनके आंतरिक भाग को अलग करता है।) एक अन्य प्रकार के प्रति उदाहरण में A कॉम्पैक्ट और B खुला है। उदाहरण के लिए, A एक बंद वर्ग हो सकता है और B एक खुला वर्ग हो सकता है जो A को छूता है।
यद्यपि, दूसरे प्रमेय के एक उदाहरण से, एक हाइपरप्लेन है जो उनके आंतरिक भाग को अलग करता है। एक अन्य प्रकार के प्रति उदाहरण में A सघन और B विवृत है। उदाहरण के लिए, A एक संवृत वर्ग हो सकता है और B एक विवृत वर्ग हो सकता है जो A को स्पर्श करता है।


प्रमेय के पहले संस्करण में, स्पष्ट रूप से अलग करने वाला हाइपरप्लेन कभी भी अद्वितीय नहीं होता है। दूसरे संस्करण में, यह अद्वितीय हो भी सकता है और नहीं भी। तकनीकी रूप से एक अलग करने वाली धुरी कभी भी अद्वितीय नहीं होती क्योंकि इसका अनुवाद किया जा सकता है; प्रमेय के दूसरे संस्करण में, एक अलग अक्ष अनुवाद तक अद्वितीय हो सकता है।
प्रमेय के पहले संस्करण में, स्पष्ट रूप से अलग करने वाला हाइपरप्लेन कभी भी अद्वितीय नहीं होता है। दूसरे संस्करण में, यह अद्वितीय हो भी सकता है और नहीं भी। तकनीकी रूप से एक पृथक्करण धुरी कभी भी अद्वितीय नहीं होती क्योंकि इसका अनुवाद किया जा सकता है; प्रमेय के दूसरे संस्करण में, एक अलग अक्ष अनुवाद तक अद्वितीय हो सकता है।


हॉर्न कोण कई हाइपरप्लेन अलगावों के लिए एक अच्छा प्रति उदाहरण प्रदान करता है। उदाहरण के लिए, में <math>\R^2</math>, यूनिट डिस्क खुले अंतराल से अलग है <math>((1, 0), (1,1))</math>, लेकिन उन्हें अलग करने वाली एकमात्र रेखा में संपूर्णता शामिल है <math>((1, 0), (1,1))</math>. इससे पता चलता है कि अगर <math>A</math> बंद है और <math>B</math> अपेक्षाकृत खुला है, तो जरूरी नहीं कि एक अलगाव मौजूद हो जो सख्त हो <math>B</math>. हालांकि, यदि <math>A</math> बंद [[polytope]] है तो ऐसा अलगाव मौजूद है।<ref name=":0" />
हॉर्न कोण कई हाइपरप्लेन पृथक्करणों के लिए एक अच्छा प्रति उदाहरण प्रदान करता है। उदाहरण के लिए, में <math>\R^2</math>, यूनिट डिस्क विवृत अंतराल से अलग है <math>((1, 0), (1,1))</math>, परन्तु उन्हें अलग करने वाली एकमात्र रेखा में संपूर्णता शामिल है <math>((1, 0), (1,1))</math>. इससे पता चलता है कि अगर <math>A</math> संवृत है और <math>B</math> अपेक्षाकृत विवृत है, तो जरूरी नहीं कि एक पृथक्करण उपलब्ध हो जो सख्त हो <math>B</math>. हालांकि, यदि <math>A</math> संवृत पालीटॉप है तो ऐसा पृथक्करण उपलब्ध है।<ref name=":0" />
== अन्य प्रकार ==
फ़ार्कस लेम्मा और संबंधित परिणामों को हाइपरप्लेन पृथक्करण प्रमेय के रूप में समझा जा सकता है, जब उत्तल पिंडों को सूक्ष्म रूप से कई रेखीय असमानताओं द्वारा परिभाषित किया जाता है तो और भी परिणाम मिल सकते हैं।<ref name=":0">{{Cite book |last=Stoer |first=Josef |url=https://link.springer.com/book/10.1007/978-3-642-46216-0 |title=परिमित आयामों में उत्तलता और अनुकूलन I|last2=Witzgall |first2=Christoph |publisher=Springer Berlin, Heidelberg |year=1970 |isbn=978-3-642-46216-0 |at=(2.12.9) |language=en |doi=10.1007/978-3-642-46216-0}}</ref>
== संघटन का पता लगाने में प्रयोग ==
संघटन का पता लगाने में, हाइपरप्लेन पृथक्करण प्रमेय सामान्यतः निम्न रूप में प्रयोग किया जाता है:


{{math_theorem
| name = अक्ष पृथक्करण प्रमेय|यदि एक रेखा ("पृथक्करण धारक ध्रुव") उपलब्ध होती है जिस पर दो सम्पूर्ण घनों के प्रक्षेपण अलगावपूर्ण होते हैं, तो दो बंद घन अलग होते हैं।
}}


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


और भी नतीजे मिल सकते हैं।<ref name=":0">{{Cite book |last=Stoer |first=Josef |url=https://link.springer.com/book/10.1007/978-3-642-46216-0 |title=परिमित आयामों में उत्तलता और अनुकूलन I|last2=Witzgall |first2=Christoph |publisher=Springer Berlin, Heidelberg |year=1970 |isbn=978-3-642-46216-0 |at=(2.12.9) |language=en |doi=10.1007/978-3-642-46216-0}}</ref>
उदाहरण के लिए, 3डी में, समष्टि को प्लेन द्वारा अलग किया जाता है, परन्तु अलग करने वाला अक्ष अलग करने वाले प्लेन के लंबवत होता है।


बहुभुज धुरी के मध्य तेजी से संघटन का पता लगाने के लिए पृथक अक्ष प्रमेय लागू किया जा सकता है। प्रत्येक फलक की [[सतह सामान्य]] या अन्य विशेषता दिशा का उपयोग पृथक करने वाले अक्ष के रूप में किया जाता है। ध्यान दें कि यह भिन्न-भिन्न अक्षों को अलग करता है तथा रेखा/प्लेन को अलग नहीं करता है।


== टक्कर का पता लगाने में प्रयोग करें ==
3डी में, फेस नॉर्म्स का उपयोग अकेले कुछ एज-ऑन-एज गैर-संघटन वाले स्थितियों को अलग करने में विफल होता है। अतिरिक्त अक्षों की आवश्यकता होती है, जिसमें  शीर्षों के युग्म के गुणन-उत्पाद सम्मिलित होते हैं।<ref>{{Cite web|url=https://docs.godotengine.org/en/stable/tutorials/math/vectors_advanced.html#collision-detection-in-3d|title = Advanced vector math}}</ref>
टकराव का पता लगाने में, हाइपरप्लेन अलगाव प्रमेय आमतौर पर निम्न रूप में प्रयोग किया जाता है:


{{math_theorem
प्रवर्धित दक्षता के लिए, समानांतर अक्षों की गणना एकल अक्ष के रूप में की जा सकती है।
| name = Separating axis theorem|Two closed convex objects are disjoint if there exists a line ("separating axis") onto which the two objects' projections are disjoint.
}}
 
आयाम के बावजूद, अलग करने वाली धुरी हमेशा एक रेखा होती है।
उदाहरण के लिए, 3डी में, अंतरिक्ष को विमानों द्वारा अलग किया जाता है, लेकिन अलग करने वाला अक्ष अलग करने वाले विमान के लंबवत होता है।
 
बहुभुज मेश के बीच तेजी से टकराव का पता लगाने के लिए पृथक अक्ष प्रमेय लागू किया जा सकता है। प्रत्येक फलक (ज्यामिति) की [[सतह सामान्य]] या अन्य विशेषता दिशा का उपयोग पृथक करने वाले अक्ष के रूप में किया जाता है। ध्यान दें कि यह अलग-अलग अक्षों को अलग करता है, लाइनों/विमानों को अलग नहीं करता है।
 
3डी में, फेस नॉर्म्स का उपयोग अकेले कुछ एज-ऑन-एज गैर-टकराव वाले मामलों को अलग करने में विफल होगा। अतिरिक्त कुल्हाड़ियों की आवश्यकता होती है, जिसमें किनारों के जोड़े के क्रॉस-उत्पाद शामिल होते हैं, प्रत्येक वस्तु से एक लिया जाता है।<ref>{{Cite web|url=https://docs.godotengine.org/en/stable/tutorials/math/vectors_advanced.html#collision-detection-in-3d|title = Advanced vector math}}</ref>
बढ़ी हुई दक्षता के लिए, समानांतर अक्षों की गणना एकल अक्ष के रूप में की जा सकती है।


== यह भी देखें ==
== यह भी देखें ==
Line 240: Line 189:
* [http://www.metanetsoftware.com/technique/tutorialA.html Collision detection and response]
* [http://www.metanetsoftware.com/technique/tutorialA.html Collision detection and response]


{{Functional analysis}}
{{DEFAULTSORT:Separating Axis Theorem}}  
{{Topological vector spaces}}
 
{{DEFAULTSORT:Separating Axis Theorem}}[[Category: उत्तल ज्यामिति में प्रमेय]] [[Category: हरमन मिन्कोव्स्की]] [[Category: रैखिक कार्य]]


[[fr:Séparation des convexes]]
[[fr:Séparation des convexes]]


 
[[Category:CS1 English-language sources (en)]]
 
[[Category:Created On 25/05/2023|Separating Axis Theorem]]
[[Category: Machine Translated Page]]
[[Category:Lua-based templates|Separating Axis Theorem]]
[[Category:Created On 25/05/2023]]
[[Category:Machine Translated Page|Separating Axis Theorem]]
[[Category:Pages with script errors|Separating Axis Theorem]]
[[Category:Templates Vigyan Ready|Separating Axis Theorem]]
[[Category:Templates that add a tracking category|Separating Axis Theorem]]
[[Category:Templates that generate short descriptions|Separating Axis Theorem]]
[[Category:Templates using TemplateData|Separating Axis Theorem]]
[[Category:उत्तल ज्यामिति में प्रमेय|Separating Axis Theorem]]
[[Category:रैखिक कार्य|Separating Axis Theorem]]
[[Category:हरमन मिन्कोव्स्की|Separating Axis Theorem]]

Latest revision as of 11:34, 8 June 2023

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

हाइपरप्लेन पृथक्करण प्रमेय हरमन मिन्कोव्स्की के कारण है। हन-बनाक पृथक्करण प्रमेय स्थलीय सदिश स्थानों के परिणाम का सामान्यीकरण करता है।

एक संबंधित परिणाम सहायक हाइपरप्लेन प्रमेय है।

समर्थन सदिश यंत्र के संदर्भ में, आदर्श पृथक्करण हाइपरप्लेन या अधिकतम-सीमा हाइपरप्लेन एक ऐसा हाइपरप्लेन होता है जो दो बिंदुगणित समूहों को पृथक्करण करता है और इन दोनों से समान दूरी पर स्थित होता है।[1][2][3]

कथन और प्रमाण

सभी स्थितियों में, मान लीजिए असंयुक्त, अरिक्त और के उत्तल उपसमुच्चय है जिनके परिणामों का सारांश इस प्रकार है:

summary table
संवृत तथा सघन संवृत के साथ
संवृत संवृत तथा सघन के साथ
विवृत
विवृत विवृत

Hyperplane separation theorem[4] — मान लीजिये की and

 का दो असम्बद्ध अरिक्त उत्तल उपसमुच्चय है तब एक ऐसा अशून्य सदिश   तथा एक वास्तविक संख्या  इस प्रकार उपलब्ध है की

सभी में तथा में के लिए समर्थित है; उदहारण हेतु एक हाइपरप्लेन , में सदिश and को पृथक करता है

यदि दोनों समुच्चय बंद हैं, और उनमें से कम से कम एक सघन है, तो पृथक्करण कठिन हो सकता है, उदाहरण के लिए, के लिए सत्य है

आयामों की संख्या परिमित होनी चाहिए। अनंत-आयामी स्थानों में दो संवृत, उत्तल, असंयुक्त समुच्चय के उदाहरण हैं जिन्हें एक संवृत हाइपरप्लेन (एक हाइपरप्लेन जहां एक सतत रैखिक कार्यात्मक कुछ स्थिरांक के बराबर होता है) से अलग नहीं किया जा सकता है, यहां तक ​​कि कमजोर अर्थों में भी जहां असमानताएं सख्त नहीं हैं।[5] यहाँ, परिकल्पना में सघनता को शिथिल नहीं किया जा सकता है; इसका उदहारण आगे के अनुभाग में प्रदर्शित किया गया है। पृथक्करण प्रमेय का यह संस्करण अनंत-आयाम का सामान्यीकरण करता है; सामान्यीकरण को सामान्यतः हाह्न-बनाक पृथक्करण प्रमेय के रूप में जाना जाता है।

जिसका प्रमाण निम्नलिखित लेम्मा पर आधारित है:

Lemma — Let and be two disjoint closed subsets of , and assume is compact. Then there exist points and minimizing the distance over and .

Proof of lemma

Let and be any pair of points, and let . Since is compact, it is contained in some ball centered on ; let the radius of this ball be . Let be the intersection of with a closed ball of radius around . Then is compact and nonempty because it contains . Since the distance function is continuous, there exist points and whose distance is the minimum over all pairs of points in . It remains to show that and in fact have the minimum distance over all pairs of points in . Suppose for contradiction that there exist points and such that . Then in particular, , and by the triangle inequality, . Therefore is contained in , which contradicts the fact that and had minimum distance over .


Proof of theorem

We first prove the second case. (See the diagram.)

WLOG, is compact. By the lemma, there exist points and of minimum distance to each other. Since and are disjoint, we have . Now, construct two hyperplanes perpendicular to line segment , with across and across . We claim that neither nor enters the space between , and thus the perpendicular hyperplanes to satisfy the requirement of the theorem.

Algebraically, the hyperplanes are defined by the vector , and two constants , such that . Our claim is that and .

Suppose there is some such that , then let be the foot of perpendicular from to the line segment . Since is convex, is inside , and by planar geometry, is closer to than , contradiction. Similar argument applies to .

Now for the first case.

Approach both from the inside by and , such that each is closed and compact, and the unions are the relative interiors . (See relative interior page for details.)

Now by the second case, for each pair there exists some unit vector and real number , such that .

Since the unit sphere is compact, we can take a convergent subsequence, so that . Let . We claim that , thus separating .

Assume not, then there exists some such that , then since , for large enough , we have , contradiction.

चूँकि एक पृथक्करण हाइपरप्लेन विवृत उत्तल समुच्चयों के आतंरिक भागों को नहीं काट सकता है, हमारे पास एक परिणाम है:

Separation theorem I — Let and be two disjoint nonempty convex sets. If is open, then there exist a nonzero vector and real number such that

for all in and in . If both sets are open, then there exist a nonzero vector and real number such that

for all in and in .

संभावित प्रतिच्छेदन की स्थिति

अगर समुच्चय करता है यदि समूह में संभावित प्रतिच्छेदन होता है, परन्तु उनके सांदर्भिक आंतरिकों में पृथक्करण होता है, तो पहली स्थिति के प्रमाण, परिवर्तन के बिना ही लागू हो जाते है, जिससे निम्न परिणाम मिलता है:

Separation theorem II — Let and be two nonempty convex subsets of with disjoint relative interiors. Then there exist a nonzero vector and a real number such that

विशेष रूप से, हमारे पास सहायक हाइपरप्लेन प्रमेय है।

Supporting hyperplane theorem — if is a convex set in and is a point on the boundary of , then there exists a supporting hyperplane of containing .

Proof

If the affine span of is not all of , then extend the affine span to a supporting hyperplane. Else, is disjoint from , so apply the above theorem.

प्रमेय का विलोम

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

प्रति उदाहरण और विशिष्टता

यदि A और B में से एक उत्तल नहीं है, तो कई संभावित प्रति उदाहरण हैं। उदाहरण के लिए, A और B संकेंद्रित वृत्त हो सकते हैं। एक अधिक सूक्ष्म प्रति उदाहरण वह है जिसमें ए और बी दोनों संवृत हैं परन्तु कोई भी सघन नहीं है। उदाहरण के लिए, यदि ए एक संवृत अर्ध समुच्चय है और बी हाइपरबोला के एक हाथ से घिरा हुआ है, तो कोई सख्ती से अलग करने वाला हाइपरप्लेन नहीं है:

यद्यपि, दूसरे प्रमेय के एक उदाहरण से, एक हाइपरप्लेन है जो उनके आंतरिक भाग को अलग करता है। एक अन्य प्रकार के प्रति उदाहरण में A सघन और B विवृत है। उदाहरण के लिए, A एक संवृत वर्ग हो सकता है और B एक विवृत वर्ग हो सकता है जो A को स्पर्श करता है।

प्रमेय के पहले संस्करण में, स्पष्ट रूप से अलग करने वाला हाइपरप्लेन कभी भी अद्वितीय नहीं होता है। दूसरे संस्करण में, यह अद्वितीय हो भी सकता है और नहीं भी। तकनीकी रूप से एक पृथक्करण धुरी कभी भी अद्वितीय नहीं होती क्योंकि इसका अनुवाद किया जा सकता है; प्रमेय के दूसरे संस्करण में, एक अलग अक्ष अनुवाद तक अद्वितीय हो सकता है।

हॉर्न कोण कई हाइपरप्लेन पृथक्करणों के लिए एक अच्छा प्रति उदाहरण प्रदान करता है। उदाहरण के लिए, में , यूनिट डिस्क विवृत अंतराल से अलग है , परन्तु उन्हें अलग करने वाली एकमात्र रेखा में संपूर्णता शामिल है . इससे पता चलता है कि अगर संवृत है और अपेक्षाकृत विवृत है, तो जरूरी नहीं कि एक पृथक्करण उपलब्ध हो जो सख्त हो . हालांकि, यदि संवृत पालीटॉप है तो ऐसा पृथक्करण उपलब्ध है।[6]

अन्य प्रकार

फ़ार्कस लेम्मा और संबंधित परिणामों को हाइपरप्लेन पृथक्करण प्रमेय के रूप में समझा जा सकता है, जब उत्तल पिंडों को सूक्ष्म रूप से कई रेखीय असमानताओं द्वारा परिभाषित किया जाता है तो और भी परिणाम मिल सकते हैं।[6]

संघटन का पता लगाने में प्रयोग

संघटन का पता लगाने में, हाइपरप्लेन पृथक्करण प्रमेय सामान्यतः निम्न रूप में प्रयोग किया जाता है:

अक्ष पृथक्करण प्रमेय — यदि एक रेखा ("पृथक्करण धारक ध्रुव") उपलब्ध होती है जिस पर दो सम्पूर्ण घनों के प्रक्षेपण अलगावपूर्ण होते हैं, तो दो बंद घन अलग होते हैं।

आयाम के अतिरिक्त, पृथक्करण धुरी सदैव एक रेखा होती है।

उदाहरण के लिए, 3डी में, समष्टि को प्लेन द्वारा अलग किया जाता है, परन्तु अलग करने वाला अक्ष अलग करने वाले प्लेन के लंबवत होता है।

बहुभुज धुरी के मध्य तेजी से संघटन का पता लगाने के लिए पृथक अक्ष प्रमेय लागू किया जा सकता है। प्रत्येक फलक की सतह सामान्य या अन्य विशेषता दिशा का उपयोग पृथक करने वाले अक्ष के रूप में किया जाता है। ध्यान दें कि यह भिन्न-भिन्न अक्षों को अलग करता है तथा रेखा/प्लेन को अलग नहीं करता है।

3डी में, फेस नॉर्म्स का उपयोग अकेले कुछ एज-ऑन-एज गैर-संघटन वाले स्थितियों को अलग करने में विफल होता है। अतिरिक्त अक्षों की आवश्यकता होती है, जिसमें शीर्षों के युग्म के गुणन-उत्पाद सम्मिलित होते हैं।[7]

प्रवर्धित दक्षता के लिए, समानांतर अक्षों की गणना एकल अक्ष के रूप में की जा सकती है।

यह भी देखें

टिप्पणियाँ

  1. Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2008). The Elements of Statistical Learning : Data Mining, Inference, and Prediction (PDF) (Second ed.). New York: Springer. pp. 129–135.
  2. Witten, Ian H.; Frank, Eibe; Hall, Mark A.; Pal, Christopher J. (2016). Data Mining: Practical Machine Learning Tools and Techniques (Fourth ed.). Morgan Kaufmann. pp. 253–254. ISBN 9780128043578.
  3. Deisenroth, Marc Peter; Faisal, A. Aldo; Ong, Cheng Soon (2020). मशीन लर्निंग के लिए गणित. Cambridge University Press. pp. 337–338. ISBN 978-1-108-45514-5.
  4. Boyd & Vandenberghe 2004, Exercise 2.22.
  5. Haïm Brezis, Analyse fonctionnelle : théorie et applications, 1983, remarque 4, p. 7.
  6. 6.0 6.1 Stoer, Josef; Witzgall, Christoph (1970). परिमित आयामों में उत्तलता और अनुकूलन I (in English). Springer Berlin, Heidelberg. (2.12.9). doi:10.1007/978-3-642-46216-0. ISBN 978-3-642-46216-0.
  7. "Advanced vector math".


संदर्भ

  • Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3.
  • Golshtein, E. G.; Tretyakov, N.V. (1996). Modified Lagrangians and monotone maps in optimization. New York: Wiley. p. 6. ISBN 0-471-54821-9.
  • Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Nondifferentiable and two-level mathematical programming. Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1.
  • Soltan, V. (2021). Support and separation properties of convex sets in finite dimension. Extracta Math. Vol. 36, no. 2, 241-278.


बाहरी संबंध