Shattered set
विखंडित समुच्चय की अवधारणा वैपनिक-चेरवोनेन्किस सिद्धांत में एक महत्वपूर्ण भूमिका निभाती है, जिसे वीसी-सिद्धांत के रूप में भी जाना जाता है। शेटरिंग और वी. सी.-सिद्धांत का उपयोग अनुभवजन्य प्रक्रियाओं के अध्ययन के साथ-साथ सांख्यिकीय कम्प्यूटेशनल शिक्षण सिद्धांत में भी किया जाता है। परिभाषा मान लीजिए कि ए एक समुच्चय है और सी समुच्चय का एक वर्ग है। वर्ग सी समूह ए को चकनाचूर कर देता है यदि ए के प्रत्येक उपसमुच्चय ए के लिए, सी का कुछ तत्व सी ऐसा है कि समान रूप से, सी ए को चकनाचूर कर देता है जब उनका प्रतिच्छेदन ए के पावर सेट के बराबर होता हैः पी (ए) = {सी। सी। सी। सी। हम सी अक्षर का उपयोग सेटों के "वर्ग" या "संग्रह" को संदर्भित करने के लिए करते हैं, जैसा कि वैपनिक-चेरवोनेन्किस वर्ग (वीसी-वर्ग) में होता है। सेट ए को अक्सर परिमित माना जाता है क्योंकि, अनुभवजन्य प्रक्रियाओं में, हम डेटा बिंदुओं के सीमित सेटों के टूटने में रुचि रखते हैं। उदाहरण हम दिखाएँगे कि समतल (द्वि-आयामी स्थान) में सभी डिस्कों का वर्ग इकाई वृत्त पर चार बिंदुओं के प्रत्येक सेट को नहीं तोड़ता है, फिर भी समतल में सभी उत्तल सेटों का वर्ग इकाई वृत्त पर बिंदुओं के प्रत्येक परिमित सेट को तोड़ता है। मान लीजिए कि ए इकाई वृत्त पर चार बिंदुओं का एक समूह है और सी को सभी डिस्क का वर्ग माना जाता है। यह जाँचने के लिए कि सी ए को कहाँ तोड़ता है, हम ए में बिंदुओं के प्रत्येक उपसमुच्चय के चारों ओर एक डिस्क खींचने का प्रयास करते हैं। सबसे पहले, हम प्रत्येक पृथक बिंदु के सबसेट के चारों ओर एक डिस्क खींचते हैं। इसके बाद, हम बिंदु जोड़े के प्रत्येक सबसेट के चारों ओर एक डिस्क खींचने की कोशिश करते हैं। यह निकटवर्ती बिंदुओं के लिए करने योग्य साबित होता है, लेकिन वृत्त के विपरीत पक्षों के बिंदुओं के लिए असंभव है। जैसा कि नीचे देखा जा सकता हैः क्योंकि कुछ उपसमुच्चय हैं जिन्हें सी में किसी भी डिस्क द्वारा अलग नहीं किया जा सकता है, इसलिए हम निष्कर्ष निकालते हैं कि ए को सी द्वारा विघटित नहीं किया जाता है और, थोड़े से विचार के साथ, हम यह साबित कर सकते हैं कि चार बिंदुओं का कोई भी समूह इस सी द्वारा विघटित नहीं होता है। हालाँकि, यदि हम सी को सभी अण्डाकार डिस्क के वर्ग के रूप में फिर से परिभाषित करते हैं, तो हम पाते हैं कि हम अभी भी ऊपर से सभी उपसमुच्चय को अलग कर सकते हैं, साथ ही उन बिंदुओं को भी जो पहले समस्याग्रस्त थे। इस प्रकार, 4 बिंदुओं के इस विशिष्ट समूह को अण्डाकार डिस्क के वर्ग द्वारा तोड़ दिया जाता है। नीचे कल्पना की गई हैः थोड़े से विचार के साथ, हम सामान्यीकृत कर सकते हैं कि एक इकाई वृत्त पर सीमित बिंदुओं के किसी भी सेट को सभी उत्तल सेटों के वर्ग द्वारा तोड़ा जा सकता है (बिंदुओं को जोड़ने की कल्पना करें)। विखंडन गुणांक समुच्चयों के संग्रह सी की समृद्धि की मात्रा निर्धारित करने के लिए, हम विखंडन गुणांक (जिसे विकास फलन के रूप में भी जाना जाता है) की अवधारणा का उपयोग करते हैं। सेटों के संग्रह सी के लिए, कोई भी स्थान होने के नाते, अक्सर एक नमूना स्थान होने के नाते, हम सी के nवें शेटरिंग गुणांक को परिभाषित करते हैं जहां सेट की कार्डिनलिटी को दर्शाता है और एन अंकों का कोई भी सेट है। यह n बिंदुओं के किसी भी समुच्चय A के सबसे बड़ी संख्या है जिसे संग्रह C में समुच्चयों के साथ A को काटकर बनाया जा सकता है। यहाँ इस बारे में कुछ तथ्य दिए गए हैंः सभी n के लिए क्योंकि किसी के लिए। यदि, इसका मतलब है कि कार्डिनलिटी एन का एक समूह है, जिसे सी द्वारा तोड़ा जा सकता है। यदि कुछ के लिए तो सभी के लिए। तीसरे गुण का अर्थ है कि यदि सी कार्डिनलिटी एन के किसी भी सेट को तोड़ नहीं सकता है तो यह बड़ी कार्डिनलिटी के सेट को तोड़ नहीं सकता है। वैपनिक-चेरवोनेन्किस वर्ग एक वर्ग सी के वी. सी. आयाम को या, वैकल्पिक रूप से, के रूप में परिभाषित किया गया है, ध्यान दें कि यदि किसी भी एन के लिए कार्डिनलिटी एन का एक सेट है जिसे सी द्वारा विघटित किया जा सकता है, तो सभी एन के लिए और इस वर्ग सी का वी. सी. आयाम अनंत है। परिमित वी. सी. आयाम वाले वर्ग को वैपनिक-चेरवोनेन्किस वर्ग या वी. सी. वर्ग कहा जाता है। एक वर्ग सी "समान रूप से ग्लिवेंको-कैन्टेली है यदि और केवल अगर यह एक वीसी वर्ग है। सॉयर-शेलाह लेम्मा को भी देखें, जो सेटों के एक परिवार की प्रधानता को इसके सबसे बड़े टूटे हुए सेट संदर्भों के आकार से संबंधित करता है। .. बाहरी लिंक जे. स्टील अनुभवजन्य प्रक्रिया कम्प्यूटेशनल लर्निंग थ्योरी द्वारा "खंडित समुच्चय" शब्दावली की उत्पत्ति