วิกิพีเดียภาษาไทย
กลับไปหน้าบทความ

อ่าน 4 นาที

หมายเลขครอบคลุม

เรขาคณิตเมตริก/โทโพโลยี

ในทางคณิตศาสตร์จำนวนปกคลุม (covering number)คือจำนวนลูกบอลที่มีขนาดที่กำหนดซึ่งจำเป็นต้องใช้ในการปกคลุมพื้นที่ที่กำหนดอย่างสมบูรณ์ โดยอาจมีการทับซ้อนกันระหว่างลูกบอลได้

หมายเลขครอบคลุม

ในทางคณิตศาสตร์จำนวนปกคลุม (covering number)คือจำนวนลูกบอลที่มีขนาดที่กำหนดซึ่งจำเป็นต้องใช้ในการปกคลุมพื้นที่ที่กำหนดอย่างสมบูรณ์ โดยอาจมีการทับซ้อนกันระหว่างลูกบอลได้ จำนวนปกคลุมนี้บ่งบอกถึงขนาดของเซตและสามารถนำไปใช้กับปริภูมิเมตริก ทั่วไปได้ แนวคิดที่เกี่ยวข้องอีกสองอย่างคือจำนวนการบรรจุ (packing number ) ซึ่งเป็นจำนวนลูกบอลที่ไม่ซ้ำกันที่สามารถบรรจุลงในพื้นที่ได้ และเอนโทรปีเมตริก (metric entropy ) ซึ่งเป็นจำนวนจุดที่สามารถบรรจุลงในพื้นที่ได้เมื่อถูกจำกัดให้อยู่ห่างกันอย่างน้อยที่สุดตามค่าคงที่

คำนิยาม

ให้ ( M , d ) เป็นปริภูมิเมตริกให้Kเป็นเซตย่อยของMและให้rเป็นจำนวนจริงบวก ให้Br ( x ) แทนลูกบอล ปิด รัศมีr มีจุดศูนย์กลางอยู่ที่xเซตย่อยCของMเป็นการคลุมภายนอกแบบ rของKถ้า:

เค⊆⋃x∈ซีบีร(x){\displaystyle K\subseteq \bigcup _{x\in C}B_{r}(x)}.

กล่าวอีกนัยหนึ่งคือ สำหรับทุกๆy∈เค{\displaystyle y\in K}มีอยู่จริงx∈ซี{\displaystyle x\in C}โดยที่ง(x,y)≤ร{\displaystyle d(x,y)\leq r}.

นอกจากนี้ ถ้าCเป็นเซตย่อยของKแล้ว C ก็จะเป็นการคลุมภายในแบบ rด้วย

จำนวนการปกคลุมภายนอกของKซึ่งแสดงด้วยสัญลักษณ์เอ็นรภายนอก(เค){\displaystyle N_{r}^{\text{ext}}(K)}คือจำนวนสมาชิก ขั้นต่ำ ของการครอบคลุมภายนอกใดๆ ของKจำนวนการครอบคลุมภายในจะใช้สัญลักษณ์ แทนเอ็นรอินท์(เค){\displaystyle N_{r}^{\text{int}}(K)}คือจำนวนสมาชิกขั้นต่ำของการครอบคลุมภายในใดๆ

เซตย่อยPของKเป็นเซตบรรจุถ้าพี⊆เค{\displaystyle P\subseteq K}และชุด{บีร(x)}x∈พี{\displaystyle \{B_{r}(x)\}_{x\in P}}คือเซตที่ไม่ทับซ้อนกันจำนวนการบรรจุของKซึ่งแสดงด้วยเอ็นรหีบห่อ(เค){\displaystyle N_{r}^{\text{pack}}(K)}คือจำนวนสมาชิกสูงสุดของการบรรจุK ใด ๆ

เซตย่อยSของKเรียกว่าr - separatedถ้าแต่ละคู่ของจุดxและyในSสอดคล้องกับd ( x , y ) ≥ rเอนโทรปีเมตริกของKจะถูกแทนด้วยเอ็นรพบกัน(เค){\displaystyle N_{r}^{\text{met}}(K)}คือจำนวนสมาชิกสูงสุดของเซตย่อยใดๆ ของKที่ คั่นด้วย r

ตัวอย่าง

  1. ปริภูมิเมตริกคือเส้นจำนวนจริงอาร์{\displaystyle \mathbb {R} }.เค⊂อาร์{\displaystyle K\subset \mathbb {R} }คือเซตของจำนวนจริงที่มีค่าสัมบูรณ์ไม่เกินเค{\displaystyle k}จากนั้นก็มีวัสดุหุ้มภายนอก⌈2เคร⌉{\textstyle \left\lceil {\frac {2k}{r}}\right\rceil }ช่วงความยาวร{\displaystyle r}ครอบคลุมช่วงเวลา[−เค,เค]{\displaystyle [-k,k]}. เพราะฉะนั้น:
    เอ็นรภายนอก(เค)≤2เคร{\displaystyle N_{r}^{\text{ext}}(K)\leq {\frac {2k}{r}}}
  2. ปริภูมิเมตริกคือปริภูมิยุคลิดอาร์ม{\displaystyle \mathbb {R} ^{m}}โดยใช้เมตริกแบบยุคลิดเค⊂อาร์ม{\displaystyle K\subset \mathbb {R} ^{m}}คือเซตของเวกเตอร์ที่มีความยาว (นอร์ม) ไม่เกินเค{\displaystyle k}. ถ้าเค{\displaystyle K}ตั้งอยู่ใน ปริภูมิย่อย dมิติของอาร์ม{\displaystyle \mathbb {R} ^{m}}จากนั้น: [ 1 ] : 337
    เอ็นรภายนอก(เค)≤(2เคงร)ง{\displaystyle N_{r}^{\text{ext}}(K)\leq \left({\frac {2k{\sqrt {d}}}{r}}\right)^{d}}.
  3. ปริภูมิเมตริกคือปริภูมิของฟังก์ชันค่าจริง โดยมี เมตริก เป็น ℓ-อนันต์จำนวนปกคลุมเอ็นรอินท์(เค){\displaystyle N_{r}^{\text{int}}(K)}เป็นจำนวนที่น้อยที่สุดเค{\displaystyle k}เช่นนั้นจึงมีอยู่ชม.1,…,ชม.เค∈เค{\displaystyle h_{1},\ldots ,h_{k}\in K}โดยที่สำหรับทุก ๆชม.∈เค{\displaystyle h\in K}มีอยู่จริงฉัน∈{1,…,เค}{\displaystyle i\in \{1,\ldots ,k\}}โดยที่ระยะห่างสูงสุดระหว่างชม.{\displaystyle h}และชม.ฉัน{\displaystyle h_{i}}มากที่สุดร{\displaystyle r}ขอบเขตข้างต้นไม่เกี่ยวข้อง เนื่องจากพื้นที่คือ∞{\displaystyle \infty }มิติ อย่างไรก็ตาม เมื่อเค{\displaystyle K}เป็นเซตกระชับ (compact set)ดังนั้น การคลุมทุกเซตนี้จึงมีเซตย่อยที่จำกัดจำนวน ดังนั้นเอ็นรอินท์(เค){\displaystyle N_{r}^{\text{int}}(K)}มีค่าจำกัด[ 2 ] : 61

คุณสมบัติ

  1. จำนวนการครอบคลุมภายในและภายนอก จำนวนการบรรจุ และเอนโทรปีเมตริกล้วนมีความสัมพันธ์กันอย่างใกล้ชิด ลำดับอสมการต่อไปนี้ใช้ได้กับเซตย่อยK ใดๆ ของปริภูมิเมตริกและจำนวนจริงบวกr ใด ๆ [ 3 ]
    เอ็น2รพบกัน(เค)≤เอ็นรหีบห่อ(เค)≤เอ็นรภายนอก(เค)≤เอ็นรอินท์(เค)≤เอ็นรพบกัน(เค){\displaystyle N_{2r}^{\text{met}}(K)\leq N_{r}^{\text{pack}}(K)\leq N_{r}^{\text{ext}}(K)\leq N_{r}^{\text{int}}(K)\leq N_{r}^{\text{met}}(K)}
  2. ฟังก์ชันทุกฟังก์ชัน ยกเว้นจำนวนการครอบคลุมภายใน จะไม่เพิ่มขึ้นตามrและไม่ลดลงตามKส่วนจำนวนการครอบคลุมภายในจะเป็นฟังก์ชันเอกภาคตามrแต่ไม่จำเป็นต้องเป็นฟังก์ชันเอกภาค ตาม K

คุณสมบัติต่อไปนี้เกี่ยวข้องกับการครอบคลุมจำนวนในปริภูมิยูคลิดมาตรฐานอาร์ม{\displaystyle \mathbb {R} ^{m}}: [ 1 ] : 338

  1. ถ้าเวกเตอร์ทั้งหมดในเค{\displaystyle K}ถูกแปลโดยเวกเตอร์คงที่เค0∈อาร์ม{\displaystyle k_{0}\in \mathbb {R} ^{m}}ดังนั้นจำนวนการครอบคลุมจึงไม่เปลี่ยนแปลง
  2. ถ้าเวกเตอร์ทั้งหมดในเค{\displaystyle K}คูณด้วยค่าสเกลาร์เค∈อาร์{\displaystyle k\in \mathbb {R} }, แล้ว:
    สำหรับทุกคนร{\displaystyle r}:เอ็น|เค|⋅รภายนอก(เค⋅เค)=เอ็นรภายนอก(เค){\displaystyle N_{|k|\cdot r}^{\text{ext}}(k\cdot K)=N_{r}^{\text{ext}}(K)}
  3. ถ้าเวกเตอร์ทั้งหมดในเค{\displaystyle K}ดำเนินการโดยฟังก์ชันลิปชิตซ์ϕ{\displaystyle \phi }ด้วยค่าคงที่ของลิปชิตซ์เค{\displaystyle k}, แล้ว:
    สำหรับทุกคนร{\displaystyle r}:เอ็น|เค|⋅รภายนอก(ϕ∘เค)≤เอ็นรภายนอก(เค){\displaystyle N_{|k|\cdot r}^{\text{ext}}(\phi \circ K)\leq N_{r}^{\text{ext}}(K)}

การประยุกต์ใช้กับการเรียนรู้ของเครื่องจักร

อนุญาตเค{\displaystyle K}เป็นปริภูมิของฟังก์ชันค่าจริง โดยมี เมตริก เป็น ℓ-อนันต์ (ดูตัวอย่างที่ 3 ด้านบน) สมมติว่าฟังก์ชันทั้งหมดในเค{\displaystyle K}ถูกจำกัดด้วยค่าคงที่จริงเอ็ม{\displaystyle M}จากนั้น จำนวนการครอบคลุมสามารถใช้เพื่อจำกัดข้อผิดพลาดในการวางนัยทั่วไป ของฟังก์ชันการเรียนรู้จากเค{\displaystyle K}เมื่อเทียบกับการสูญเสียกำลังสอง: [ 2 ] : 61

ความน่าจะเป็น⁡[จีบชม.∈เค|ข้อผิดพลาดทั่วไป(ชม.)−ข้อผิดพลาดเชิงประจักษ์(ชม.)|≥ϵ]≤เอ็นรอินท์(เค)2เอ็กซ์⁡−มϵ22เอ็ม4{\displaystyle \operatorname {Prob} \left[\sup _{h\in K}{\big \vert }{\text{GeneralizationError}}(h)-{\text{EmpiricalError}}(h){\big \vert }\geq \epsilon \right]\leq N_{r}^{\text{int}}(K)\,2\exp {-m\epsilon ^{2} \over 2M^{4}}}

ที่ไหนร=ϵ8เอ็ม{\displaystyle r={\epsilon \over 8M}}และม{\displaystyle m}คือจำนวนตัวอย่าง

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Covering_number&oldid=1326919535 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ หมายเลขครอบคลุม

ในทางคณิตศาสตร์จำนวนปกคลุม (covering number)คือจำนวนลูกบอลที่มีขนาดที่กำหนดซึ่งจำเป็นต้องใช้ในการปกคลุมพื้นที่ที่กำหนดอย่างสมบูรณ์ โดยอาจมีการทับซ้อนกันระหว่างลูกบอลได้

คำนิยาม

ให้ ( M , d ) เป็น ปริภูมิเมตริก ให้ K เป็นเซตย่อยของ M และให้ r เป็น จำนวนจริง บวก ให้ Br ( x ) แทน ลูกบอล ปิด รัศมี r มีจุดศูนย์กลางอยู่ที่ x เซตย่อย C ของ M เป็นการ คลุมภายนอกแบบ r ของ K ถ้า:

ตัวอย่าง

ปริภูมิเมตริกคือเส้นจำนวนจริง อาร์ {\displaystyle \mathbb {R} } .

คุณสมบัติ

คุณสมบัติต่อไปนี้เกี่ยวข้องกับการครอบคลุมจำนวนใน ปริภูมิยูคลิด มาตรฐาน อาร์ ม {\displaystyle \mathbb {R} ^{m}} : [ 1 ] : 338