4. Hãy giải thích khái niệm xác suất lỗi của giả thuyết h xét trên khái niệm c và học gần đúng PAC.

Khái niệm lỗi đúng (True error): Lỗi đúng chính là lỗi của giả thuyết h với khái niệm đích c và một phân bố các thể hiện (D) đã biết trước. (chú ý: D ở đây không phải là tập training).

Định nghĩa: Lỗi đúng của một giả thuyết h xét trên khái niệm đích c, với một phân bố thể hiện D, kí hiệu là errorD(h), là xác suất mà giả thuyết h là sai trên thể hiện x (lấy theo phân bố D) so với c(x). Hay: errorD (h) = Pr[c(x) khác h(x)] mọi x thuộc D

PAC:

Việc đi tìm số lượng các ví dụ đào tạo để có được lỗi đúng trên nó bằng 0: tức là errorD(h) =0 là không thể. Vì thế ta không yêu cầu bộ học phải đúng lần lượt với mọi tập ví dụ đào tạo được sinh ngẫu nhiên, mà ta chỉ yêu cầu xác suất thất bại của nó là luôn giới hạn bởi một số thực δ nào đó, và tương tự δ cũng được lấy đủ nhỏ. Hay nói ngắn gọn hơn ta chỉ yêu cầu bộ học thực hiện với một xác suất nào đó trên một giả thuyết gần đúng. Do đó có sự xuất hiện của khái niệm học gần đúng xác suất. (PAC)

Định nghĩa: Xét một lớp các khái niệm C trên một tập các thể hiện trong X có độ dài n và một bộ học L sử dụng không gian giả thuyết H. Khi đó C là có thể học PAC bởi L có sử dụng H nếu với mọi c  C, phân bố D trong X, một hằng số ε sao cho: 0< ε <1/2, và một hằng số δ sao cho 0< δ <1/2, thì bộ học L với xác suất nhỏ nhất là (1- δ) đưa ra một giả thuyết h, h € H sao cho errorD(h) ≤ ε, về mặt thời gian là đa thức theo 1/ε, 1/δ, n và kích thước của c (size(c)).