โปรแกรมเมอร์คนหนึ่งได้สร้าง K-means clustering algorithm บนคอมพิวเตอร์ Apple II โดยใช้ APPLESOFT BASIC สำเร็จ ทำให้เกิดการพูดคุยเกี่ยวกับวิวัฒนาการของ machine learning และข้อจำกัดในการเขียนโปรแกรม โครงการนี้แสดงให้เห็นว่าแนวคิดพื้นฐานของ machine learning สามารถทำงานได้บนฮาร์ดแวร์จากปลายทศวรรษ 1970 พร้อมด้วยการแสดงผล decision boundaries และการทำซ้ำของ algorithm แบบเรียลไทม์
ขั้นตอนของอัลกอริทึม K-Means
- การเริ่มต้น: สร้างจุดศูนย์กลางของคลัสเตอร์ k จุด โดยการสุ่มเลือกข้อมูล k ตัวจากชุดข้อมูล
- ขั้นตอนที่ 1 - การจัดกลุ่ม: กำหนดข้อมูลแต่ละตัวให้เข้าคลัสเตอร์ที่ใกล้ที่สุด โดยใช้ระยะทาง Euclidean
- ขั้นตอนที่ 2 - การอัปเดต: คำนวณจุดศูนย์กลางใหม่จากข้อมูลที่ถูกจัดกลุ่ม ทำซ้ำจนกว่าจะลู่เข้า
ความคิดถึงผสานกับ Machine Learning สมัยใหม่
การสร้างนี้แสดง K-means clustering พร้อมการแสดงผลแบบโต้ตอบ วาด decision boundaries ขณะที่ algorithm บรรจบกันบนจุดข้อมูล โปรแกรมเมอร์ลดขนาด dataset เพื่อเพิ่มความเร็วในการประมวลผลและจัดการกับข้อจำกัดด้านการคำนวณของฮาร์ดแวร์เก่า โครงการนี้ได้ความแม่นยำ 90% ในปัญหาการจัดกลุ่มสองคลาสแบบง่าย พิสูจน์ว่าหลักการพื้นฐานของ machine learning สามารถทำงานได้แม้บนระบบที่มีข้อจำกัดอย่างมาก
สมาชิกในชุมชนแบ่งปันความทรงจำของการผจญภัยในการเขียนโปรแกรมยุคแรก นักพัฒนาคนหนึ่งเล่าถึงการสร้าง genetic algorithms ใน Pascal ในช่วงทศวรรษ 1990 ขณะที่อีกคนหนึ่งกล่าวถึงการสร้าง perceptron บน Apple II ในปี 1984 ที่ใช้เวลา 20 นาทีต่อการรู้จำหนึ่งครั้ง เรื่องราวเหล่านี้เน้นย้ำว่าข้อจำกัดในการเขียนโปรแกรมมักนำไปสู่วิธีแก้ปัญหาที่สร้างสรรค์และประสบการณ์การเรียนรู้ที่สำคัญ
รายละเอียดการใช้งานทางเทคนิค
- แพลตฟอร์ม: คอมพิวเตอร์ Apple II พร้อม APPLESOFT BASIC
- ชุดข้อมูล: ลดลงเหลือ 5 ตัวอย่างต่อคลาสเพื่อการประมวลผลที่เร็วขึ้น
- ความแม่นยำ: 90% (การจำแนกผิด 1 จาก 10 การสังเกต)
- การคำนวณระยะทาง: ระยะทาง Squared Euclidean (หลีกเลี่ยงการคำนวณรากที่สองที่มีต้นทุนสูง)
- ค่าความคลาดเคลื่อนในการลู่เข้า: 0.001
ความท้าทายทางเทคนิคและวิธีแก้ปัญหาที่สร้างสรรค์
การสร้างบน Apple II เผชิญกับอุปสรรคทางเทคนิคหลายประการที่เป็นเอกลักษณ์ของการคำนวณแบบเก่า ข้อจำกัดด้านหน่วยความจำต้องการการจัดการ array อย่างระมัดระวัง เนื่องจาก APPLESOFT BASIC จะแสดง error เมื่อพยายามประกาศ array ที่มีอยู่แล้วใหม่ โปรแกรมเมอร์ต้องปรับปรุงการคำนวณระยะทางโดยหลีกเลี่ยงการดำเนินการรากที่สองที่มีราคาแพง ใช้ squared Euclidean distances สำหรับการเปรียบเทียบแทน
ส่วนการแสดงผลพิสูจน์ว่าท้าทายเป็นพิเศษ การวาด decision boundaries ต้องการการคำนวณทางเรขาคณิตที่ซับซ้อนเพื่อให้แน่ใจว่าเส้นอยู่ภายในขอบเขตหน้าจอ โค้ดจัดการกับกรณีพิเศษเช่น vertical slopes และ centroids ที่อยู่นอกหน้าจอ แม้ว่าโปรแกรมเมอร์จะสังเกตว่ายังมีข้อจำกัดบางอย่างสำหรับสถานการณ์ที่มีมากกว่าสองกลุ่ม
ข้อจำกัดของฮาร์ดแวร์ Apple II
- ข้อจำกัดด้านหน่วยความจำที่ต้องการการจัดการอาร์เรย์อย่างระมัดระวัง
- ไม่สามารถประกาศอาร์เรย์ที่มีอยู่แล้วใหม่ใน APPLESOFT BASIC ได้
- การดำเนินการทางคณิตศาสตร์ที่มีต้นทุนสูง (ฟังก์ชัน SQR)
- ความละเอียดหน้าจอที่จำกัดสำหรับการแสดงผลกราฟิก
- การทำงานแบบเธรดเดียวโดยไม่มีการปรับปรุงประสิทธิภาพแบบสมัยใหม่
การถกเถียงเรื่องการจำแนก Machine Learning
โครงการนี้จุดประกายการถกเถียงเกี่ยวกับสิ่งที่ถือว่าเป็น machine learning สมาชิกในชุมชนบางคนตั้งคำถามว่าเทคนิค regression แบบง่ายสมควรได้รับป้ายกำกับ machine learning หรือไม่ ขณะที่คนอื่นโต้แย้งว่าการแก้ปัญหาที่ซับซ้อนทางการคำนวณบนฮาร์ดแวร์ที่จำกัดถือเป็นดินแดนของ ML อย่างแน่นอน การพูดคุยสะท้อนคำถามที่กว้างขึ้นเกี่ยวกับวิธีที่สาขานี้ได้พัฒนาและขยายตัวตลอดหลายทศวรรษ
เมื่อคุณพบว่าตัวเองกำลังแก้ปัญหา NP-hard บน Apple II โอกาสสูงที่คุณได้เข้าสู่ดินแดน machine learning แล้ว
โปรแกรมเมอร์วางแผนที่จะสำรวจ algorithm ที่ก้าวหน้ากว่าเช่น Expectation Maximization ซึ่งสามารถจัดการกับลักษณะ Gaussian ของข้อมูลทดสอบได้ดีกว่า อย่างไรก็ตาม การสร้าง neural networks ด้วย backpropagation บน APPLESOFT BASIC จะนำเสนอความท้าทายเพิ่มเติมอย่างมาก
การฟื้นฟูการเขียนโปรแกรมฮาร์ดแวร์เก่า
โครงการนี้เข้าร่วมกับแนวโน้มที่เพิ่มขึ้นของการสร้าง algorithm สมัยใหม่บนคอมพิวเตอร์เก่า การผสมผสานระหว่างความคิดถึงและความท้าทายทางเทคนิคดึงดูดโปรแกรมเมอร์ที่สนใจในการทำความเข้าใจทั้งข้อจำกัดของการคำนวณในอดีตและแนวคิด algorithm พื้นฐาน การทำงานภายใต้ข้อจำกัดที่รุนแรงมักให้ความเข้าใจที่ลึกซึ้งยิ่งขึ้นเกี่ยวกับวิธีการทำงานของ algorithm จริงๆ
การสร้างบน Apple II ทำหน้าที่เป็นทั้งแบบฝึกหัดทางการศึกษาและการเตือนใจเกี่ยวกับความก้าวหน้าของการคำนวณ สิ่งที่ครั้งหนึ่งต้องการการปรับปรุงอย่างระมัดระวังและวิธีแก้ปัญหาที่สร้างสรรค์ ตอนนี้สามารถทำงานได้อย่างง่ายดายบนสมาร์ทโฟนที่มีพลังมากกว่าฮาร์ดแวร์ต้นฉบับหลายพันเท่า
อ้างอิง: K-Means By Another Means