คำสาปของมิติ
คำสาปของมิติ (Curse of dimensionality) เป็นคำที่เสนอโดยริชาร์ด เบลแมน[1][2] เพื่ออธิบายถึง การเพิ่มเชิงชี้กำลัง ของปริมาณการคำนวณในขั้นตอนวิธีของปัญหาเมื่อมิติของปริภูมิทางคณิตศาสตร์เพิ่มขึ้น
ตัวอย่างเช่น ในการสุ่มตัวอย่างในช่วงหน่วย [0,1] ให้วางจุด 100 จุดระยะห่างเท่ากันโดยมีระยะห่างไม่เกิน 0.01 ก็เพียงพอแล้ว หากเราพยายามทำการสุ่มตัวอย่างที่คล้ายกันบนไฮเปอร์คิวบ์หน่วย 10 มิติ จำนวนสุดที่ต้องการจะเป็น 1020 ดังนั้น ในแง่หนึ่ง ไฮเปอร์คิวบ์ 10 มิติสามารถกล่าวได้ว่าใหญ่เป็น 1018 เท่าของช่วงหน่วย
คำสาปของมิติในการวิเคราะห์เชิงตัวเลข
[แก้]ต่อไปนี้เป็นตัวอย่างของคำสาปของมิติในการวิเคราะห์เชิงตัวเลข นั่นคือ การที่เวลาในการคำนวณและข้อผิดพลาดเชิงตัวเลขเพิ่มสูงขึ้น
- การแก้ระบบสมการหลายมิติ เช่น พีชคณิตเชิงเส้นเชิงตัวเลข[3]
- การแก้สมการพีชคณิตอันดับสูงโดยใช้ ขั้นตอนวิธีการค้นหาราก[3]
- ปริพันธ์หลายชั้น (การหาปริพันธ์เชิงตัวเลขหลายมิติ)[4][5]
คำสาปของมิติในการเพิ่มประสิทธิภาพและการเรียนรู้ของเครื่อง
[แก้]คำสาปของมิติเป็นอุปสรรคร้ายแรงเมื่อพยายามแก้ปัญหาการหาค่าเหมาะที่สุดแบบไดนามิกด้วยมิติตัวแปรสถานะขนาดใหญ่ นอกจากนี้แล้ว ในปัญหาการเรียนรู้ของเครื่อง คำสาปของมิติทำให้ปัญหาซับซ้อนขึ้นเมื่อพยายามเรียนรู้สถานะของธรรมชาติจากตัวอย่างจำนวนจำกัดโดยใช้ ปริภูมิค่าแทนลักษณะหลายมิติ และ การค้นหาเพื่อนบ้านใกล้สุด ในปริภูมิมิติสูง ปริมาณข้อมูลที่จำเป็นต้องใช้อาจเพิ่มตามจำนวนมิติแบบเลขชี้กำลัง[6]
อ้างอิง
[แก้]- ↑ Bellman, Richard Ernest; Rand Corporation (1957). Dynamic programming. Princeton University Press. p. ix. ISBN 978-0-691-07951-6.,
Republished: Bellman, Richard Ernest (2003). Dynamic Programming. Courier Dover Publications. ISBN 978-0-486-42809-3. - ↑ Bellman, Richard Ernest (1961). Adaptive control processes: a guided tour. Princeton University Press. ISBN 9780691079011.
- ↑ 3.0 3.1 山本哲朗. 数値解析入門. サイエンスライブラリ 現代数学への入門 14 (増訂版 ed.). サイエンス社. ISBN 4-7819-1038-6.
- ↑ 手塚集、「数値多重積分に関する話題(<特集>数値計算)」 『応用数理』 1998年 8巻 4号 p.267-276, doi:10.11540/bjsiam.8.4_267, 日本応用数理学会
- ↑ Traub, J. F., & Woźniakowski, H. (1994). Breaking intractability. Scientific American, 270(1), 102-107.
- ↑ Udacity (2015-02-23). "Curse of Dimensionality - Georgia Tech - Machine Learning". YouTube (ภาษาอังกฤษ). สืบค้นเมื่อ 2022-06-29.