Chúng ta tiếp tục chuỗi bài về đề tài “Học máy từ góc nhìn của lý thuyết tính toán”. Các bài trước là:
- HM1 — Giới thiệu học máy và mô hình nhất quán
- HM2 — Một số ví dụ trong mô hình nhất quán
- HM3 — Mô hình PAC và ví dụ
- HM4 — Độ phức tạp mẫu và VC dimension.
Hai mô hình (nhất quán và PAC) chúng ta thấy cho đến nay đều không thực tế lắm. Trên thực tế dữ liệu thường có nhiễu, việc tìm một giả thuyết nhất quán với nhiều mẫu trở nên khó khăn. Đôi khi không tồn tại giả thuyết nào nhất quán với dữ liệu, hoặc cho dù có tồn tại thì nhiễu cũng làm cho không tồn tại. Vả lại, nhất quán với dữ liệu bị nhiễu thì cũng không hay ho gì. Đó là chưa kể việc đi tìm một giả thuyết nhất quán với dữ liệu có thể là bài toán NP-khó, và thậm chí có thể trên thực tế không tồn tại cái khái niệm mà mình đang muốn học.
(Từ giờ trở đi, tôi sẽ dịch “learner” là “học giả”. Học giả ở đây là một thuật toán máy tính chứ không phải là một gã hói đầu. “Học giả như hòa như đạo. Bất học giả như cảo như thảo.”)
Như vậy chúng ta cần một mô hình cho phép học giả trả về một giả thuyết không nhất quán với mẫu, và phải tìm cách đo chất lượng học giả — kể cả khi không có cái khái niệm mà mình muốn học. Bài này kết thúc bằng chứng minh định lý Vapnik-Chervonenkis, một trong những định lý quan trọng nhất của lý thuyết học máy thống kê (statistical learning theory).
thành viên — cỡ khoảng 519 quintillion. (Cho nên đừng mong chạy thuật toán Dijkstra tìm God’s number.)
đồng xu, 
cái cân, 
đồng xu giả, có thể biết hoặc không biết trước là nặng hay nhẹ hơn các đồng thật; phép thiết kế chiến lược cân có được “adaptive” hay không, vân vân. Thật ra câu này hỏi bác Văn là thích hợp nhất. Bác Văn có 
đồng giả không biết nặng hay nhẹ hơn các đồng thật thế nào, và một cái cân. Tìm số lần cân 
ít nhất để chỉ ra đồng giả (nếu có) và chỉ ra luôn là nó nặng hay nhẹ hơn các đồng thật.
lần cân thì không đủ để chỉ ra đồng giả. Ta sẽ tìm liên hệ giữa
20 vạn dặm dưới đáy biển