Shattered set
વિખેરાયેલા સમૂહોનો ખ્યાલ વાપનિક-ચેર્વોનેન્કિસ સિદ્ધાંતમાં મહત્વપૂર્ણ ભૂમિકા ભજવે છે, જેને વીસી-સિદ્ધાંત તરીકે પણ ઓળખવામાં આવે છે. શેટરિંગ અને વીસી-થિયરીનો ઉપયોગ પ્રયોગમૂલક પ્રક્રિયાઓના અભ્યાસમાં તેમજ આંકડાકીય કોમ્પ્યુટેશનલ લર્નિંગ થિયરીમાં થાય છે. વ્યાખ્યા ધારો કે A એ સમૂહ છે અને C એ સમૂહોનો વર્ગ છે. વર્ગ C સમૂહ A ને તોડી નાખે છે જો A ના દરેક સબસેટ a માટે, C નું કોઈ તત્વ c એવું હોય કે જ્યારે તેમનું આંતરછેદ A ના પાવર સેટની બરાબર હોય ત્યારે સમાનરૂપે, C A ને તોડી નાખેઃ P (A) = {c ≤ A | c ≤ C}. આપણે વાપનિક-ચેર્વોનેન્કિસ વર્ગ (વી. સી.-વર્ગ) ની જેમ સમૂહના "વર્ગ" અથવા "સંગ્રહ" નો સંદર્ભ આપવા માટે સી અક્ષરનો ઉપયોગ કરીએ છીએ. સમૂહ A ને ઘણીવાર મર્યાદિત માનવામાં આવે છે કારણ કે, પ્રયોગમૂલક પ્રક્રિયાઓમાં, આપણે ડેટા બિંદુઓના મર્યાદિત સમૂહોના શેટરિંગમાં રસ ધરાવીએ છીએ. ઉદાહરણ આપણે બતાવીશું કે સમતલમાં તમામ ડિસ્કનો વર્ગ (દ્વિ-પરિમાણીય જગ્યા) એકમ વર્તુળ પરના ચાર બિંદુઓના દરેક સમૂહને વિખેરતો નથી, તેમ છતાં સમતલમાં તમામ બહિર્મુખ સમૂહોનો વર્ગ એકમ વર્તુળ પરના બિંદુઓના દરેક મર્યાદિત સમૂહને વિખેરતો હોય છે. ધારો કે A એ એકમ વર્તુળ પર ચાર બિંદુઓનો સમૂહ છે અને C એ તમામ ડિસ્કનો વર્ગ છે. C એ ક્યાં તૂટી પડે છે તે ચકાસવા માટે, આપણે A માં બિંદુઓના દરેક સબસેટની આસપાસ ડિસ્ક દોરવાનો પ્રયાસ કરીએ છીએ. પ્રથમ, આપણે દરેક અલગ બિંદુના ઉપગણની આસપાસ એક ડિસ્ક દોરીએ છીએ. આગળ, આપણે બિંદુ જોડીઓના દરેક સબસેટની આસપાસ ડિસ્ક દોરવાનો પ્રયાસ કરીએ છીએ. આ નજીકના બિંદુઓ માટે શક્ય હોવાનું બહાર આવ્યું છે, પરંતુ વર્તુળની વિરુદ્ધ બાજુઓ પરના બિંદુઓ માટે અશક્ય છે. નીચે દર્શાવ્યા મુજબઃ કારણ કે ત્યાં અમુક પેટા સમૂહ છે જેને સીમાં કોઈપણ ડિસ્ક દ્વારા અલગ કરી શકાતો નથી, તેથી આપણે નિષ્કર્ષ કાઢીએ છીએ કે A એ C દ્વારા વિખેરાયો નથી. અને, થોડો વિચાર કરીને, આપણે સાબિત કરી શકીએ છીએ કે આ C દ્વારા ચાર બિંદુઓનો કોઈ સમૂહ વિખેરાયો નથી. જો કે, જો આપણે C ને તમામ લંબગોળ ડિસ્કના વર્ગ તરીકે પુનઃવ્યાખ્યાયિત કરીએ, તો આપણે શોધી કાઢીએ છીએ કે આપણે હજી પણ ઉપરથી તમામ પેટા સમૂહોને અલગ કરી શકીએ છીએ, તેમજ તે બિંદુઓ કે જે અગાઉ સમસ્યારૂપ હતા. આમ, 4 બિંદુઓનો આ ચોક્કસ સમૂહ લંબગોળ ડિસ્કના વર્ગ દ્વારા વિખેરાઈ જાય છે. નીચે દર્શાવેલઃ થોડો વિચાર કરીને, આપણે સામાન્ય કરી શકીએ કે એકમ વર્તુળ પરના મર્યાદિત બિંદુઓના કોઈપણ સમૂહને તમામ બહિર્મુખ સમૂહોના વર્ગ દ્વારા વિખેરવામાં આવી શકે છે (બિંદુઓને જોડવાની કલ્પના કરો). વિખેરણ ગુણાંક સમૂહના C સંગ્રહની સમૃદ્ધિને માપવા માટે, આપણે વિખેરણ ગુણાંકની વિભાવનાનો ઉપયોગ કરીએ છીએ (જેને વૃદ્ધિ કાર્ય તરીકે પણ ઓળખવામાં આવે છે). સમૂહોના સંગ્રહ C માટે, કોઈપણ જગ્યા હોવાથી, ઘણીવાર નમૂનાની જગ્યા હોવાથી, આપણે C ના nમા શેટરિંગ ગુણાંકને વ્યાખ્યાયિત કરીએ છીએ જ્યાં સમૂહની મુખ્યતાને સૂચવે છે અને તે n બિંદુઓનો કોઈપણ સમૂહ છે. તે n બિંદુઓના કોઈપણ સમૂહ A ના સબસેટ્સની સૌથી મોટી સંખ્યા છે જે સંગ્રહ C માં સેટ સાથે A ને છેદે છે. અહીં કેટલીક હકીકતો છેઃ બધા n માટે કારણ કે કોઈપણ માટે. જો, તેનો અર્થ એ કે કાર્ડિનાલિટી n નો સમૂહ છે, જે C દ્વારા વિખેરાઈ શકે છે. જો કેટલાક માટે તો બધા માટે. ત્રીજા ગુણધર્મનો અર્થ એ છે કે જો C કાર્ડિનાલિટી N ના કોઈપણ સમૂહને તોડી ન શકે તો તે મોટા કાર્ડિનાલિટીના સમૂહને તોડી ન શકે. વર્ગ C ના VC પરિમાણને અથવા, વૈકલ્પિક રીતે, તરીકે વ્યાખ્યાયિત કરવામાં આવે છે નોંધ લો કે જો કોઈ પણ n માટે કાર્ડિનાલિટી n નો સમૂહ હોય જેને C દ્વારા વિખેરાઈ શકાય છે, તો પછી આ વર્ગ C ના તમામ n અને VC પરિમાણ માટે અનંત છે. મર્યાદિત વીસી પરિમાણ ધરાવતા વર્ગને વાપનિક-ચેર્વોનેન્કિસ વર્ગ અથવા વીસી વર્ગ કહેવામાં આવે છે. જો અને માત્ર જો તે વી. સી. વર્ગ હોય તો જ વર્ગ સી "એકસમાન રીતે ગ્લિવેન્કો-કેન્ટેલી છે. સોઅર-શેલાહ લેમ્મા પણ જુઓ, જે સમૂહના પરિવારની મુખ્યતાને તેના સૌથી મોટા વિખેરાયેલા સમૂહ સંદર્ભોના કદ સાથે સંબંધિત કરે છે. . બાહ્ય કડીઓ જે. સ્ટીલ પ્રયોગમૂલક પ્રક્રિયા કોમ્પ્યુટેશનલ લર્નિંગ થિયરી દ્વારા "શેટર્ડ સેટ્સ" પરિભાષાની ઉત્પત્તિ