Một lập trình viên đã thành công trong việc triển khai thuật toán phân cụm K-means trên máy tính Apple II sử dụng APPLESOFT BASIC, tạo ra những cuộc thảo luận về sự phát triển của machine learning và các ràng buộc lập trình. Dự án này chứng minh rằng các khái niệm machine learning cơ bản có thể chạy trên phần cứng từ cuối thập niên 1970, hoàn chỉnh với các ranh giới quyết định trực quan và lặp thuật toán theo thời gian thực.
Các bước của thuật toán K-Means
- Khởi tạo: Tạo k tâm cụm bằng cách chọn ngẫu nhiên k quan sát từ tập dữ liệu
- Bước 1 - Phân nhóm: Gán mỗi quan sát vào cụm gần nhất bằng cách sử dụng khoảng cách Euclidean
- Bước 2 - Cập nhật: Tính toán lại các tâm cụm dựa trên các điểm đã được phân nhóm, lặp lại cho đến khi hội tụ
Hoài niệm gặp gỡ Machine Learning hiện đại
Việc triển khai này thể hiện phân cụm K-means với phản hồi trực quan, vẽ các ranh giới quyết định khi thuật toán hội tụ trên các điểm dữ liệu. Lập trình viên đã giảm kích thước tập dữ liệu để tăng tốc độ thực thi và xử lý các hạn chế tính toán của phần cứng cổ điển. Dự án đạt được độ chính xác 90% trên bài toán phân cụm hai lớp đơn giản, chứng minh rằng các nguyên lý machine learning cốt lõi có thể hoạt động ngay cả trên các hệ thống bị hạn chế nghiêm trọng.
Các thành viên cộng đồng đã chia sẻ những kỷ niệm của riêng họ về những cuộc phiêu lưu lập trình thời kỳ đầu. Một nhà phát triển nhớ lại việc tạo ra các thuật toán di truyền bằng Pascal trong thập niên 1990, trong khi một người khác đề cập đến việc triển khai perceptron trên Apple II vào năm 1984 mất 20 phút cho mỗi lần nhận dạng. Những câu chuyện này làm nổi bật cách các ràng buộc lập trình thường dẫn đến các giải pháp sáng tạo và những trải nghiệm học tập quan trọng.
Chi tiết Triển khai Kỹ thuật
- Nền tảng: Máy tính Apple II với APPLESOFT BASIC
- Tập dữ liệu: Giảm xuống còn 5 mẫu cho mỗi lớp để thực thi nhanh hơn
- Độ chính xác: 90% (1 trong 10 quan sát bị phân loại sai)
- Tính toán khoảng cách: Khoảng cách Euclidean bình phương (tránh phép tính căn bậc hai tốn kém)
- Ngưỡng hội tụ: 0.001
Thách thức kỹ thuật và giải pháp sáng tạo
Việc triển khai Apple II phải đối mặt với một số trở ngại kỹ thuật điển hình của máy tính cổ điển. Hạn chế bộ nhớ đòi hỏi quản lý mảng cẩn thận, vì APPLESOFT BASIC báo lỗi khi cố gắng khai báo lại các mảng đã tồn tại. Lập trình viên phải tối ưu hóa các phép tính khoảng cách bằng cách tránh các phép toán căn bậc hai tốn kém, thay vào đó sử dụng khoảng cách Euclidean bình phương để so sánh.
Thành phần trực quan tỏ ra đặc biệt thách thức. Vẽ các ranh giới quyết định đòi hỏi các phép tính hình học phức tạp để đảm bảo các đường thẳng nằm trong ranh giới màn hình. Mã xử lý các trường hợp đặc biệt như độ dốc thẳng đứng và các trọng tâm ngoài màn hình, mặc dù lập trình viên lưu ý vẫn còn một số hạn chế cho các tình huống có nhiều hơn hai cụm.
Các ràng buộc phần cứng của Apple II
- Hạn chế về bộ nhớ đòi hỏi phải quản lý mảng một cách cẩn thận
- Không có khả năng khai báo lại các mảng đã tồn tại trong APPLESOFT BASIC
- Các phép toán học tốn kém (hàm SQR)
- Độ phân giải màn hình hạn chế cho hiển thị đồ họa
- Thực thi đơn luồng không có tối ưu hóa hiện đại
Tranh luận về phân loại Machine Learning
Dự án đã tạo ra cuộc tranh luận về điều gì được coi là machine learning. Một số thành viên cộng đồng đặt câu hỏi liệu các kỹ thuật hồi quy đơn giản có xứng đáng với nhãn machine learning hay không, trong khi những người khác lập luận rằng việc giải quyết các vấn đề phức tạp về mặt tính toán trên phần cứng hạn chế chắc chắn thuộc lãnh thổ ML. Cuộc thảo luận phản ánh những câu hỏi rộng lớn hơn về cách lĩnh vực này đã phát triển và mở rộng qua nhiều thập kỷ.
Khi bạn thấy mình đang giải quyết các bài toán NP-hard trên Apple II, khả năng cao là bạn đã bước vào lãnh thổ machine learning.
Lập trình viên có kế hoạch khám phá các thuật toán tiên tiến hơn như Expectation Maximization, có thể xử lý tốt hơn bản chất Gaussian của dữ liệu thử nghiệm. Tuy nhiên, việc triển khai mạng neural với backpropagation trên APPLESOFT BASIC sẽ đặt ra những thách thức bổ sung đáng kể.
Phục hưng lập trình phần cứng cũ
Dự án này tham gia vào xu hướng ngày càng tăng của việc triển khai các thuật toán hiện đại trên máy tính cổ điển. Sự kết hợp giữa hoài niệm và thách thức kỹ thuật thu hút các lập trình viên quan tâm đến việc hiểu cả các ràng buộc máy tính lịch sử và các khái niệm thuật toán cơ bản. Làm việc trong các hạn chế nghiêm trọng thường cung cấp những hiểu biết sâu sắc hơn về cách các thuật toán thực sự hoạt động.
Việc triển khai Apple II vừa là một bài tập giáo dục vừa là lời nhắc nhở về việc máy tính đã tiến bộ đến mức nào. Những gì từng đòi hỏi tối ưu hóa cẩn thận và các giải pháp sáng tạo giờ đây có thể chạy một cách dễ dàng trên các smartphone mạnh gấp hàng nghìn lần so với phần cứng gốc.
Tham khảo: K-Means By Another Means