กลับไปหน้าบทความ

อ่าน 9 นาที

ทฤษฎีบทการแยกไฮเปอร์เพลน

ในทางเรขาคณิตทฤษฎีบทการแยกด้วยระนาบไฮเปอร์เพลนเป็นทฤษฎีบทเกี่ยวกับเซตเว้าที่ไม่ทับซ้อนกัน ในปริภูมิยูคลิดnมิติมีหลายเวอร์ชันที่ค่อนข้างคล้ายกัน ในเวอร์ชันหนึ่งของทฤษฎีบทนี้

ทฤษฎีบทการแยกไฮเปอร์เพลน

ทฤษฎีบทการแยกไฮเปอร์เพลน
ภาพประกอบแสดงทฤษฎีบทการแยกไฮเปอร์เพลน
พิมพ์ทฤษฎีบท
สนาม
คาดการณ์โดยเฮอร์มันน์ มินคอฟสกี
ปัญหาที่ยังเปิดอยู่เลขที่
การสรุปโดยทั่วไปทฤษฎีบทการแยกของฮาห์น-บานาค

ในทางเรขาคณิตทฤษฎีบทการแยกด้วยระนาบไฮเปอร์เพลนเป็นทฤษฎีบทเกี่ยวกับเซตเว้าที่ไม่ทับซ้อนกัน ในปริภูมิยูคลิดnมิติมีหลายเวอร์ชันที่ค่อนข้างคล้ายกัน ในเวอร์ชันหนึ่งของทฤษฎีบทนี้ ถ้าเซตทั้งสองนี้เป็นเซตปิดและอย่างน้อยหนึ่งเซตเป็นเซตกระชับ (compact set ) แล้วจะมีระนาบไฮเปอร์เพลนอยู่ระหว่างเซตทั้งสอง และอาจมีระนาบไฮเปอร์เพลนขนานกันสองระนาบอยู่ระหว่างเซตทั้งสองโดยมีช่องว่างคั่นอยู่ ในอีกเวอร์ชันหนึ่ง ถ้าเซตเว้าที่ไม่ทับซ้อนกันทั้งสองเป็นเซตเปิด แล้วจะมีระนาบไฮเปอร์เพลนอยู่ระหว่างเซตทั้งสอง แต่ไม่จำเป็นต้องมีช่องว่าง แกนที่ตั้งฉากกับระนาบไฮเปอร์เพลนที่แยกเซตนั้นเรียกว่าแกนที่แยกเซตเนื่องจากภาพฉาย ตั้งฉาก ของทรงเว้าบนแกนนั้นจะไม่ทับซ้อนกัน

ทฤษฎีบทการแยกไฮเปอร์เพลนเป็นผลงานของเฮอร์มันน์ มินคอฟสกีทฤษฎีบทการแยกฮาห์น-บานาคได้ขยายผลลัพธ์ดังกล่าวไปสู่ปริภูมิเวกเตอร์เชิงทอพอโลยี

ผลลัพธ์ที่เกี่ยวข้องอีกประการหนึ่งคือทฤษฎีบท ระนาบรองรับ

ในบริบทของเครื่องสนับสนุนเวกเตอร์ระนาบแยกที่เหมาะสมที่สุดหรือระนาบขอบสูงสุดคือระนาบที่แยกชุดจุดสองชุดและเพิ่มระยะห่างสูงสุดให้กับทั้งสองชุด[ 1 ] [ 2 ] [ 3 ]

คำแถลงและหลักฐาน

ทฤษฎีบทการแยกไฮเปอร์เพลน[ 4 ]ให้และเป็นเซตย่อยนูนที่ไม่ว่างเปล่าและไม่ทับซ้อนกันของแล้วจะมีเวกเตอร์ที่ไม่เป็นศูนย์และจำนวนจริง อยู่ เช่นนั้น

สำหรับทุกสิ่งในและใน; กล่าวคือ ระนาบไฮเปอร์เวกเตอร์ปกติ แยกและ ออกจาก กัน

ถ้าเซตทั้งสองเป็นเซตปิด และอย่างน้อยหนึ่งเซตเป็นเซตกระชับ การแยกเซตก็จะสามารถเข้มงวดได้ กล่าวคือสำหรับบางค่า

ในทุกกรณี ให้ถือว่าเซตย่อยของ เป็นเซตที่ไม่ซ้ำกัน ไม่ว่างเปล่า และเป็นเซตแบบนูนสรุปผลลัพธ์ได้ดังนี้:

ตารางสรุป
ปิดกระชับ ปิด กับ
ปิด ปิดกระชับ กับ
เปิด
เปิด เปิด

จำนวนมิติจะต้องมีจำกัด ในปริภูมิอนันต์มิติจะมีตัวอย่างของเซตปิด นูน และไม่ทับซ้อนกันสองเซตซึ่งไม่สามารถแยกออกจากกันได้ด้วยระนาบปิด (ระนาบที่ ฟังก์ชันเชิงเส้น ต่อเนื่องเท่ากับค่าคงที่บางค่า) แม้ในความหมายที่อ่อนซึ่งความไม่เท่าเทียมกันไม่เข้มงวดก็ตาม[ 5 ]

ในที่นี้ ความกะทัดรัดในสมมติฐานไม่สามารถผ่อนปรนได้ ดูตัวอย่างในส่วน ตัวอย่างค้านและความเป็นเอกลักษณ์ทฤษฎีบทการแยกนี้สามารถขยายไปสู่มิติอนันต์ได้ การขยายนี้เป็นที่รู้จักกันทั่วไปในชื่อ ทฤษฎีบทการแยก ของ ฮาห์น-บานาค

การพิสูจน์นี้อาศัยบทพิสูจน์ย่อยต่อไปนี้:

บทตั้งให้และเป็นเซตย่อยปิดที่ไม่ทับซ้อนกันของและสมมติว่าเป็นเซตกระชับ (compact set) แล้วจะมีจุดและ ที่ทำให้ระยะห่างระหว่างและ มีค่าน้อย ที่สุด

การพิสูจน์บทตั้ง

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

ภาพประกอบการพิสูจน์
การพิสูจน์ทฤษฎีบท

เราจะพิสูจน์กรณีที่สองก่อน (ดูแผนภาพประกอบ)

โดยไม่เสียความเป็นทั่วไป เซตนี้เป็นเซตกระชับ ตามบทพิสูจน์ย่อย จะมีจุดและที่มีระยะห่างน้อยที่สุดระหว่างกัน เนื่องจากและไม่ทับซ้อนกัน เราจึงได้ทีนี้ สร้างระนาบไฮเปอร์สองระนาบที่ตั้งฉากกับส่วนของเส้นตรงโดยที่และข้ามผ่านเราอ้างว่าทั้ง และไม่เข้าไปในปริภูมิระหว่างและดังนั้นระนาบไฮเปอร์ที่ตั้งฉากกันจึงเป็นไปตามข้อกำหนดของทฤษฎีบท

ใน ทาง พีชคณิต ระนาบไฮเปอร์ถูกกำหนดโดยเวกเตอร์และค่าคงที่สองค่าโดยที่ข้ออ้างของเราคือและ

สมมติเพื่อพิสูจน์ข้อขัดแย้งว่ามีจุดบางจุดที่ทำให้ . เนื่องจากเกรเดียนต์ของฟังก์ชันกำหนดโดย ดังนั้นอนุพันธ์ทิศทางจึงมีเครื่องหมายเดียวกับซึ่งก็คือลบ ดังนั้นสำหรับค่า ที่เล็กพอจุดนั้นจะสอดคล้องกับ ซึ่งขัดแย้งกับการเลือกเนื่องจากคุณสมบัติความนูน การให้เหตุผลในทำนองเดียวกันแสดงให้เห็นว่า.

มาเริ่มกันที่คดีแรกเลยครับ

พิจารณาทั้งจากภายในโดยและโดยที่แต่ละเซตปิดและกะทัดรัด และผลรวมของเซตเหล่านั้นคือเซตภายในสัมพัทธ์(ดู รายละเอียดเพิ่มเติมได้ที่หน้า เซต ภายในสัมพัทธ์ )

ในกรณีที่สอง สำหรับแต่ละคู่จะมีเวกเตอร์หน่วยและจำนวนจริง บางค่า ที่ ทำให้

เนื่องจากทรงกลมหน่วยเป็นทรงกลมกระชับ เราจึงสามารถเลือกอนุกรมย่อยลู่เข้าได้ ดังนั้น. ให้. เราอ้างว่าดังนั้นจึงแยก.

สมมติว่าไม่ใช่เช่นนั้น ก็จะมีอยู่บางค่าที่ทำให้แล้วเนื่องจากสำหรับค่า ที่มากพอเราจะได้ซึ่งขัดแย้งกัน

เนื่องจากระนาบแยกไม่สามารถตัดกับส่วนภายในของเซตแบบนูนเปิดได้ ดังนั้นเราจึงได้ข้อสรุปดังนี้:

ทฤษฎีบทการแยก I ให้และเป็นเซตเว้าสองเซตที่ไม่ทับซ้อนกันและไม่ว่าง ถ้าเป็นเซตเปิด แล้วจะมีเวกเตอร์ที่ไม่เป็นศูนย์และจำนวนจริง อยู่จริงโดยที่

สำหรับทุกค่าในและในถ้าทั้งสองเซตเป็นเซตเปิด จะมีเวกเตอร์ที่ไม่เป็นศูนย์และจำนวนจริง อยู่ เช่นนั้น

สำหรับทุกคน ในและใน

กรณีที่มีจุดตัดที่เป็นไปได้

ถ้าเซตเหล่านั้นมีจุดตัดที่เป็นไปได้ แต่ส่วนภายในสัมพัทธ์ ของเซตเหล่านั้น ไม่ทับซ้อนกัน การพิสูจน์ในกรณีแรกยังคงใช้ได้โดยไม่มีการเปลี่ยนแปลงใดๆ ซึ่งจะได้ผลลัพธ์ดังนี้:

ทฤษฎีบทการแยกส่วนที่ 2 ให้และเป็นเซตย่อยนูนที่ไม่ว่างสองเซตของโดยที่ส่วนภายในสัมพัทธ์ไม่ทับซ้อนกัน แล้วจะมีเวกเตอร์ที่ไม่เป็นศูนย์และจำนวนจริงอยู่จริง ที่ทำให้

โดยเฉพาะอย่างยิ่ง เรามี ทฤษฎีบทไฮเปอร์เพล น สนับสนุน

ทฤษฎีบทระนาบรองรับถ้าเป็นเซตเว้าในและเป็นจุดบนขอบของแล้วจะมีระนาบรองรับของที่บรรจุอยู่

การพิสูจน์

ถ้าปริภูมิเชิงเส้นของไม่ใช่ทั้งหมดของแล้วให้ขยายปริภูมิเชิงเส้นนั้นไปยังระนาบรองรับ มิฉะนั้นจะไม่ทับซ้อนกับดังนั้นให้ใช้ทฤษฎีบทข้างต้น

บทกลับของทฤษฎีบท

โปรดทราบว่า การมีอยู่ของระนาบไฮเปอร์เพลนที่ "แยก" เซตแบบนูนสองเซตในความหมายแบบอ่อนๆ ของอสมการที่ไม่เข้มงวดนั้น ไม่ได้หมายความว่าเซตทั้งสองจะไม่มีส่วนร่วมกัน เซตทั้งสองอาจมีจุดอยู่บนระนาบไฮเปอร์เพลนก็ได้

ตัวอย่างค้านและความเป็นเอกลักษณ์

ทฤษฎีบทนี้ใช้ไม่ได้หากวัตถุชิ้นใดชิ้นหนึ่งไม่ใช่รูปทรงนูน

ถ้าAหรือB ตัวใดตัวหนึ่ง ไม่ใช่รูปนูน ก็จะมีตัวอย่างค้านที่เป็นไปได้มากมาย เช่นAและBอาจเป็นวงกลมร่วมศูนย์กลาง ตัวอย่างค้านที่ซับซ้อนกว่านั้นคือกรณีที่AและBเป็นเซตปิดทั้งคู่ แต่ไม่มีเซตใดเป็นเซตกระชับ เช่น ถ้าAเป็นระนาบครึ่งปิด และ B ถูกล้อมรอบด้วยแขนข้างหนึ่งของไฮเปอร์โบลา ก็จะไม่มีระนาบแยกที่ชัดเจน:

(ถึงแม้ว่าตามตัวอย่างหนึ่งของทฤษฎีบทที่สอง จะมีระนาบไฮเปอร์เพลนที่แยกส่วนภายในของทั้งสอง) ตัวอย่างค้านอีกประเภทหนึ่งมีAเป็นเซตกระชับและBเป็นเซตเปิด ตัวอย่างเช่น A อาจเป็นสี่เหลี่ยมจัตุรัสปิดและ B อาจเป็นสี่เหลี่ยมจัตุรัสเปิดที่สัมผัสกับ A

ในทฤษฎีบทฉบับแรก เห็นได้ชัดว่าระนาบแบ่งแยกไม่เคยมีเพียงหนึ่งเดียว ในทฤษฎีบทฉบับที่สอง ระนาบแบ่งแยกอาจมีเพียงหนึ่งเดียวหรือไม่ก็ได้ ในทางเทคนิคแล้ว แกนแบ่งแยกไม่เคยมีเพียงหนึ่งเดียว เพราะสามารถเลื่อนได้ ในทฤษฎีบทฉบับที่สอง แกนแบ่งแยกอาจมีเพียงหนึ่งเดียวได้ ยกเว้นกรณีการเลื่อน

มุมฮอร์นเป็นตัวอย่างคัดค้านที่ดีสำหรับการแยกไฮเปอร์เพลนหลายอย่าง ตัวอย่างเช่น ในดิสก์หน่วยแยกออกจากช่วงเปิดแต่เส้นเดียวที่แยกพวกมันออกจากกันนั้นครอบคลุมทั้งหมดของสิ่งนี้แสดงให้เห็นว่าถ้าเป็นปิดและเปิดสัมพัทธ์กัน ก็ไม่จำเป็นต้องมีการแยกที่เข้มงวดสำหรับอย่างไรก็ตาม ถ้าเป็นรูปทรงหลายเหลี่ยมนูนปิด การแยกดังกล่าวจะมีอยู่[ 6 ]

ตัวเลือกเพิ่มเติม

ทฤษฎีบทของ Farkasและผลลัพธ์ที่เกี่ยวข้องสามารถเข้าใจได้ว่าเป็นทฤษฎีบทการแยกไฮเปอร์เพลนเมื่อทรงนูนถูกกำหนดโดยอสมการเชิงเส้นจำนวนจำกัด

อาจพบผลลัพธ์เพิ่มเติม[ 6 ]

ใช้ในการตรวจจับการชน

ในการตรวจจับการชนกัน ทฤษฎีการแยกไฮเปอร์เพลนโดยทั่วไปจะใช้ในรูปแบบต่อไปนี้:

ทฤษฎีแกนแยกวัตถุปิดนูนสองชิ้นจะไม่ทับซ้อนกัน หากมีเส้นตรง ("แกนแยก") ที่ฉายภาพของวัตถุทั้งสองลงบนเส้นนั้นโดยไม่ทับซ้อนกัน

ไม่ว่าจะอยู่ในมิติใด แกนแบ่งแยกก็จะเป็นเส้นตรงเสมอ ตัวอย่างเช่น ใน 3 มิติ พื้นที่ถูกแบ่งแยกด้วยระนาบ แต่แกนแบ่งแยกจะตั้งฉากกับระนาบแบ่งแยกนั้น

ทฤษฎีแกนแยกสามารถนำไปใช้ในการตรวจจับการชนกัน อย่างรวดเร็ว ระหว่างรูปทรงเรขาคณิตหลายเหลี่ยมได้ โดยใช้ทิศทาง ตั้งฉากของ แต่ละ หน้าหรือทิศทางคุณลักษณะอื่นๆ เป็นแกนแยก โปรดทราบว่าผลลัพธ์ที่ได้คือแกนแยกที่เป็นไปได้ ไม่ใช่เส้น/ระนาบแยก

ใน 3 มิติ การใช้เวกเตอร์ปกติของหน้าเพียงอย่างเดียวจะไม่สามารถแยกกรณีขอบชนขอบที่ไม่ชนกันได้บางกรณี จำเป็นต้องใช้แกนเพิ่มเติมซึ่งประกอบด้วยผลคูณไขว้ของคู่ขอบ โดยแต่ละขอบนำมาจากวัตถุแต่ละชิ้น[ 7 ]

เพื่อให้มีประสิทธิภาพมากขึ้น สามารถคำนวณแกนขนานเป็นแกนเดียวได้

ดูเพิ่มเติม

หมายเหตุ

  1. ^ Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2008). องค์ประกอบของการเรียนรู้ทางสถิติ: การขุดค้นข้อมูล การอนุมาน และการทำนาย (PDF) (ฉบับพิมพ์ครั้งที่สอง). นิวยอร์ก: Springer. หน้า  129–135 . เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2019-04-10.
  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. หน้า  253–254 . ISBN 9780128043578.
  3. ^ Deisenroth, Marc Peter; Faisal, A. Aldo; Ong, Cheng Soon (2020). คณิตศาสตร์สำหรับการเรียนรู้ของเครื่องจักร . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. หน้า  337–338 . ISBN 978-1-108-45514-5.
  4. บอยด์ แอนด์ แวนเดนเบิร์ก 2547 , แบบฝึกหัด 2.22.
  5. ^ Haïm Brezis ,การวิเคราะห์เชิงฟังก์ชัน, ปริภูมิโซโบเลฟ และสมการเชิงอนุพันธ์ย่อย , 2011, หมายเหตุ 4, หน้า 7.
  6. ^ a b Stoer, Josef; Witzgall, Christoph (1970). ความนูนและการหาค่าเหมาะสมที่สุดในมิติจำกัด เล่ม 1. Springer Berlin, Heidelberg. (2.12.9). doi : 10.1007/978-3-642-46216-0 . ISBN 978-3-642-46216-0.
  7. ^ "คณิตศาสตร์เวกเตอร์ขั้นสูง "
  • การตรวจจับและการตอบสนองต่อการชน
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Hyperplane_separation_theorem&oldid=1336990606 "

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ ทฤษฎีบทการแยกไฮเปอร์เพลน

ในทางเรขาคณิตทฤษฎีบทการแยกด้วยระนาบไฮเปอร์เพลนเป็นทฤษฎีบทเกี่ยวกับเซตเว้าที่ไม่ทับซ้อนกัน ในปริภูมิยูคลิดnมิติมีหลายเวอร์ชันที่ค่อนข้างคล้ายกัน ในเวอร์ชันหนึ่งของทฤษฎีบทนี้

คำแถลงและหลักฐาน

ทฤษฎีบทการแยกไฮเปอร์เพลน [ 4 ] — ให้และเป็นเซตย่อยนูนที่ไม่ว่างเปล่าและไม่ทับซ้อนกันของแล้วจะมีเวกเตอร์ที่ไม่เป็นศูนย์และจำนวนจริง อยู่ เช่นนั้น เอ {\displaystyle A} บี {\displaystyle B} อาร์ n {\displaystyle \mathbb {R} ^{n}} วี {\displaystyle v} ค...

กรณีที่มีจุดตัดที่เป็นไปได้

ถ้าเซตเหล่านั้นมีจุดตัดที่เป็นไปได้ แต่ ส่วนภายในสัมพัทธ์ ของเซตเหล่านั้น ไม่ทับซ้อนกัน การพิสูจน์ในกรณีแรกยังคงใช้ได้โดยไม่มีการเปลี่ยนแปลงใดๆ ซึ่งจะได้ผลลัพธ์ดังนี้: A , B {\displaystyle A,B}

บทกลับของทฤษฎีบท

โปรดทราบว่า การมีอยู่ของระนาบไฮเปอร์เพลนที่ "แยก" เซตแบบนูนสองเซตในความหมายแบบอ่อนๆ ของอสมการที่ไม่เข้มงวดนั้น ไม่ได้หมายความว่าเซตทั้งสองจะไม่มีส่วนร่วมกัน เซตทั้งสองอาจมีจุดอยู่บนระนาบไฮเปอร์เพลนก็ได้