Sauer-Shelah lemma - Sauer–Shelah lemma

Pajor'un Sauer-Shelah lemma formülasyonu: Her sonlu küme ailesi için (yeşil), ikinci ailedeki her kümenin birinci aile tarafından parçalanacağı şekilde eşit derecede çok sayıda kümeden (mavi ana hatlar) oluşan başka bir aile vardır.

İçinde kombinatoryal matematik ve aşırı küme teorisi, Sauer-Shelah lemma şunu belirtir her set ailesi küçük ile VC boyutu az sayıda setten oluşur. Adını almıştır Norbert Sauer ve Saharon Shelah, 1972'de birbirinden bağımsız olarak yayınlayan.[1][2] Aynı sonuç, aynı zamanda, biraz daha erken ve tekrar bağımsız olarak yayınlandı. Vladimir Vapnik ve Alexey Chervonenkis, bundan sonra VC boyutu adlandırılır.[3] Shelah, lemma içeren makalesinde, Micha Perles ve bu nedenle lemma aynı zamanda Perles – Sauer – Shelah lemma.[4]

Buzaglo vd. bu lemma'yı "VC boyutundaki en temel sonuçlardan biri" olarak adlandırın,[4] ve birçok alanda uygulamaları vardır. Sauer'in motivasyonu, kombinatorik Shelah içerideyken model teorisi ve Vapnik ve Chervonenkis'inki İstatistik. Ayrıca uygulandı ayrık geometri[5] ve grafik teorisi.[6]

Tanımlar ve ifade

Eğer kümelerden oluşan bir ailedir ve başka bir set ise olduğu söyleniyor paramparça tarafından her alt kümesi (I dahil ederek boş küme ve kendisi) bir kavşak olarak elde edilebilir arasında ve ailede bir set. VC boyutu en geniş olanıdır kardinalite tarafından parçalanmış bir setin .

Bu tanımlar açısından, Sauer-Shelah lemma şunu belirtir: setlerden oluşan bir ailedir farklı unsurlar öyle ki, sonra bir dizi boyutu paramparça eder . Eşdeğer olarak, eğer VC boyutu dır-dir sonra en fazla olabilir setleri.

Lemmanın sınırı sıkıdır: Aile tüm alt kümelerinden oluşmalıdır daha küçük boyutta . Sonra boyutu tam olarak ama herhangi bir boyut kümesini parçalamıyor .[7]

Parçalanmış setlerin sayısı

Sauer – Shelah lemmasının güçlenmesi nedeniyle Pajor (1985), her sonlu küme ailesinin en azından paramparça eder setleri.[8] Bu hemen Sauer-Shelah lemma anlamına gelir, çünkü yalnızca alt kümelerinin -item evren, daha az kardinaliteye sahiptir . Böylece ne zaman , parçalanacak kadar küçük set yok, bu yüzden parçalanan setlerden birinin en azından kardinalitesi olmalı .

Sırayla parçalanmış küme adı verilen sınırlı bir parçalanmış küme türü için, parçalanmış kümelerin sayısı her zaman küme ailesinin önemine eşittir.[9]

Kanıt

Pajor'un Sauer – Shelah lemma varyantı şu şekilde kanıtlanabilir: matematiksel tümevarım; kanıt çeşitli şekillerde kredilendirilmiştir Noga Alon[10] ya da Ron Aharoni ve Ron Holzman.[9]

Baz: sadece bir setten oluşan her aile boş seti paramparça eder.

Adım: Lemmanın şu büyüklükteki tüm aileler için geçerli olduğunu varsayalım. ve izin ver iki veya daha fazla kümeden oluşan bir aile olun. İzin Vermek tüm setlere değil bazılarına ait olan . Bölünmüş içeren kümelerin iki alt ailesine ve içermeyen setler .

Tümevarım varsayımına göre, bu iki alt aile, boyutları en azından toplamı olan iki set koleksiyonunu parçalamaktadır. .

Bu parçalanmış setlerin hiçbiri , içeren bir setten beri tüm setlerin içerdiği bir aile tarafından parçalanamaz veya tüm setler içermiyor .

Parçalanan setlerin bazıları her iki alt aile tarafından parçalanmış olabilir. Bir set iki alt aileden yalnızca biri tarafından parçalanmışsa, hem alt ailenin parçalanmış kümelerinin sayısına hem de parçalanmış kümelerin sayısına bir birim katkıda bulunur. . Bir set her iki alt aile tarafından parçalanmış durumda ve tarafından paramparça edildi , yani alt ailelerin parçalanmış kümelerinin sayısına iki birim katkıda bulunur ve . Bu nedenle, parçalanmış setlerin sayısı en azından iki alt ailesinin parçaladığı sayıya eşittir , en azından .

Sauer-Shelah lemmanın orijinal haliyle farklı bir kanıtı: Péter Frankl ve János Pach, dayanır lineer Cebir ve içerme-dışlama ilkesi.[5][7]

Başvurular

Lemmanın orijinal uygulaması, Vapnik ve Chervonenkis tarafından, her olasılık dağılımının (belirli bir VC boyutunun olayları ailesine göre) sonlu bir örnek nokta kümesi ile tahmin edilebileceğini göstermekti. kardinalite yalnızca olaylar ailesinin VC boyutuna bağlıdır. Bu bağlamda, her ikisi de bir ε sayısıyla parametrelendirilmiş iki önemli yaklaşım kavramı vardır: bir küme S örneklem sayısı ve olasılık dağılımı S, her olayın olasılığı ile ilgili olarak orijinal dağılımın bir ε-yaklaşımı olduğu söylenir. S orijinal olasılığından en fazla ε farklıdır. Bir set S (ağırlıksız) numunelerin ε-net en az ε olasılığı olan her olay en az bir puan içeriyorsa S. Bir ε-yaklaşımı da bir net-net olmalıdır, ancak bunun tersi olması gerekmez.

Vapnik ve Chervonenkis, VC boyut sistemlerini belirlediğini göstermek için lemmayı kullandı. d her zaman ε-kardinalite yaklaşımı vardır . Daha sonra yazarlar dahil Haussler ve Welzl (1987)[11] ve Komlós, Pach ve Woeginger (1992)[12] benzer şekilde card-ağlarının her zaman var olduğunu gösterdi ve daha doğrusu en çok önem taşıyan .[5] Küçük ε-ağların varlığının kanıtının ana fikri, rastgele bir örnek seçmektir. x kardinalite ve ikinci bir bağımsız rastgele örnek y kardinalite ve olasılığını sınırlandırmak için x bazı büyük olay tarafından kaçırıldı E olasılıkla x kaçırılır ve eşzamanlı olarak y ile E medyan değerinden daha büyük. Herhangi bir özel Eolasılık x bir süre kaçırıldı y medyanından daha büyük olduğundan çok küçüktür ve Sauer – Shelah lemma ( ) sadece az sayıda farklı olayın E dikkate alınması gerekir, bu yüzden sendika sınırı sıfır olmayan olasılıkla, x bir ε-nettir.[5]

Buna karşılık, ε-ağlar ve ε-yaklaşımları ve yeterince büyük kardinaliteye sahip rastgele bir örneklemin bu özelliklere sahip olma olasılığı, makine öğrenme, alanında muhtemelen yaklaşık olarak doğru öğrenme.[13] İçinde hesaplamalı geometri, uygulandı menzil arama,[11] alay etme,[14] ve yaklaşım algoritmaları.[15][16]

Kozma ve Moran (2013) sonuçları kanıtlamak için Sauer-Shelah lemmanın genellemelerini kullanın grafik teorisi sayısının olduğu gibi güçlü yönelimler belirli bir grafiğin sayıları arasında bağlı ve 2 kenara bağlı alt grafikler.[6]

Ayrıca bakınız

Referanslar

  1. ^ Sauer, N. (1972), "Küme ailelerinin yoğunluğu üzerine", Kombinatoryal Teori Dergisi, Seri A, 13: 145–147, doi:10.1016/0097-3165(72)90019-2, BAY  0307902.
  2. ^ Shelah, Saharon (1972), "Kombinatoryal bir problem; sonsuz dillerde modeller ve teoriler için istikrar ve düzen", Pacific Journal of Mathematics, 41: 247–261, doi:10.2140 / pjm.1972.41.247, BAY  0307903, dan arşivlendi orijinal 2013-10-05 tarihinde.
  3. ^ Vapnik, V.N.; Červonenkis, A. Ja. (1971), "Olayların ortaya çıkış frekanslarının olasılıklarına tekdüze yakınsaması", Akademija Nauk SSSR, 16: 264–279, BAY  0288823.
  4. ^ a b Buzaglo, Sarit; Pinchasi, Rom; Rote, Günter (2013), "Topolojik hipergraflar", in Pach, János (ed.), Geometrik Grafik Teorisi Üzerine Otuz Deneme, Springer, s. 71–81, doi:10.1007/978-1-4614-0110-0_6.
  5. ^ a b c d Pach, János; Agarwal, Pankaj K. (1995), Kombinatoryal geometri, Ayrık Matematik ve Optimizasyonda Wiley-Interscience Serisi, New York: John Wiley & Sons Inc., s.247, doi:10.1002/9781118033203, ISBN  0-471-58890-3, BAY  1354145.
  6. ^ a b Kozma, László; Moran, Shay (2013), "Yıkıcı, Grafik Yönelimleri ve Bağlantı", Elektronik Kombinatorik Dergisi, 20 (3), S44, arXiv:1211.1319, Bibcode:2012arXiv1211.1319K.
  7. ^ a b Gowers, Timothy (31 Temmuz 2008), "Kombinasyonlarda boyut argümanları", Gowers's Weblog: Matematikle ilgili tartışmalar, Örnek 3.
  8. ^ Pajor, Alain (1985), Sous-espaces des espaces de Banach, Travaux en Cours [Devam Eden Çalışmalar], 16, Paris: Hermann, ISBN  2-7056-6021-6, BAY  0903247. Alıntı yaptığı gibi Anstee, Rónyai ve Sali (2002).
  9. ^ a b Anstee, R. P .; Rónyai, Lajos; Sali, Attila (2002), "Yıkıcı haberler", Grafikler ve Kombinatorikler, 18 (1): 59–73, doi:10.1007 / s003730200003, BAY  1892434.
  10. ^ Kalai, Gil (28 Eylül 2008), "Aşırı Kombinatorik III: Bazı Temel Teoremler", Kombinatorik ve Daha Fazlası.
  11. ^ a b Haussler, David; Welzl, Emo (1987), "ε-ağlar ve tek yönlü aralık sorguları", Ayrık ve Hesaplamalı Geometri, 2 (2): 127–151, doi:10.1007 / BF02187876, BAY  0884223.
  12. ^ Komlós, János; Pach, János; Woeginger, Gerhard (1992), "ε-ağlar için neredeyse sıkı sınırlar", Ayrık ve Hesaplamalı Geometri, 7 (2): 163–173, doi:10.1007 / BF02187833, BAY  1139078.
  13. ^ Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. (1989), "Öğrenilebilirlik ve Vapnik-Chervonenkis boyutu", ACM Dergisi, 36 (4): 929–965, doi:10.1145/76359.76371, BAY  1072253.
  14. ^ Chazelle, B.; Friedman, J. (1990), "Rastgele örneklemenin deterministik bir görünümü ve geometride kullanımı", Kombinatorik, 10 (3): 229–249, doi:10.1007 / BF02122778, BAY  1092541.
  15. ^ Brönnimann, H .; Goodrich, M. T. (1995), "Sonlu VC boyutunda neredeyse optimal set kapakları", Ayrık ve Hesaplamalı Geometri, 14 (4): 463–479, doi:10.1007 / BF02570718, BAY  1360948.
  16. ^ Har-Peled, Sariel (2011), "Karmaşıklık, örnekleme ve ε-ağlar ve ε-örnekler hakkında", Geometrik yaklaşım algoritmaları, Matematiksel Araştırmalar ve Monograflar, 173Providence, RI: American Mathematical Society, s. 61–85, ISBN  978-0-8218-4911-8, BAY  2760023.