Thuật ngữ PAC - (Probability Approximately Correct  - Xác suất xấp xỉ đúng) đã được Valiant đề xuất vào năm 1984.

• Độ phức tạp của mẫu và độ phức tạp tính toán định lượng khái niệm về độ khó của một vấn đề học tập và thành công của phương pháp học, dựa trên dữ liệu thực nghiệm.

• Thuật ngữ PAC đã được Valiant đề xuất vào năm 1984. Khái niệm học PAC tương ứng với khái niệm học tập nhất quán trong Lý thuyết của Vapnik và khái niệm về học tập nhất quán bắt nguồn từ khái niệm về tính nhất quán của ước tính thống kê đã được Ronald Fisher giới thiệu vào năm 1922.

• Có nhiều phiên bản của lý thuyết học nhất quán và học PAC giải quyết các không gian giả thuyết khác nhau, hàm mất mát, loại thuật toán.

Chúng ta sẽ đi vào các khái niệm chi tiết.

1. Học PAC

Để định lượng mức độ thành công của thuật toán học A, chúng ta cần ước tính sai số (rủi ro kỳ vọng) của dự báo $A(S) \in H$, trong đó $S \in Z^n$ là một mẫu ngẫu nhiên. Trong phương pháp học PAC, chúng ta xem xét các ước lượng cho sai số của một dự đoán với độ chính xác $\varepsilon$ (xấp xỉ) đến độ tin cậy (1 - $\delta$) (có thể) trong phép đo xác suất đối với $S \in Z^n$.

• Với $D \in P (Z)$, ta đặt $P_{S \sim D^m} [f (S)] := D^m (\{S \in Z^m | f (S)\text{ giữ}\})$.

Quan hệ $f(S)$ thường được biểu diễn dưới dạng bất đẳng thức.

$E_{S\sim D^m} f : = \int_{\Omega^m} f dD^m$.

• Chúng ta viết $P [f (S)], E (f)$, nếu $m = 1$ và D đã biết (và do đó có thể bỏ qua). 

Chúng ta nói rằng $H$ là PAC-khả học ứng với. hàm rủi ro (kỳ vọng) $R^L$, nếu tồn tại một hàm phức tạp mẫu $m_H: (0, 1)^2 \rightarrow R$ và một thuật toán học A với đặc tính sau. Với mọi $(\epsilon, \delta) \in (0, 1)^2$, với mọi phân phối D trên Z, khi chạy thuật toán học A trên $m ≥ m_H(\epsilon, \delta)$ i.i.d. ví dụ được tạo bởi D, thuật toán trả về $h_S \in H$ sao cho 

$P_{S\sim D^m} [(R^L_D (h_S) - \underset{h'\in H}{inf} R^L_D (h') ) \leq \epsilon] \geq 1 - \delta$.

Độ phức tạp mẫu $m_H: (0, 1)^2 \rightarrow N$ của lớp giả thuyết H là hàm của độ chính xác ($\epsilon$) và độ tin cậy ($\delta$), được coi là các biến của hàm $m_H$, xuất hiện trong định nghĩa của PAC- khả năng học của H sao cho với mỗi ($\epsilon, \delta$) độ phức tạp mẫu $m_H (\epsilon, \delta)$ là số nhỏ nhất xuất hiện trong Định nghĩa khả năng PAC.

Định lý 1. Cho Z là miền, H là lớp giả thuyết hữu hạn và $L: Z × H \rightarrow [0, 1]$ là hàm mất mát. Khi đó, H là PAC khả học bằng cách sử dụng thuật toán ERM với độ phức tạp mẫu $m_H (\epsilon, \delta) \leq \frac{2 log (2 \sharp (H) / \delta)}{\epsilon^2}$.

Định lý 1 ngụ ý rằng việc overfitting không bao giờ xảy ra nếu chúng ta có một số hữu hạn giả thuyết có thể có và hàm mất mát có giá trị nhị phân tùy ý.

Giải thích Định lý 1. Cho một lớp giả thuyết $H$ và một ví dụ huấn luyện S, quy tắc ERM chọn một bộ tối thiểu $h_S \in H$ của rủi ro thực nghiệm $\hat{R}^L_S (h)$. Để đảm bảo rằng mức tối thiểu h của rủi ro thực nghiệm với lần tương ứng đến S là mức giảm thiểu rủi ro kỳ vọng ​​(hoặc có rủi ro kỳ vọng ​gần với mức tối thiểu) đối với phân phối xác suất dữ liệu thực, nó đủ để đảm bảo rằng đồng nhất trên tất cả các giả thuyết trong H, rủi ro thực nghiệm sẽ gần với rủi ro thực sự (kỳ vọng).

Nếu H là hữu hạn, thì xấp xỉ thống nhất có thể thu được nếu chúng ta có thể chỉ ra rằng đối với bất kỳ giả thuyết cố định $h \in H$, khoảng cách giữa rủi ro thực tế và theo thực nghiệm, $|\hat{R}_S (h) - L_D (h) |$ sẽ trở nên khá nhỏ. Định luật yếu về số lớn, phát biểu rằng khi m tiến tới vô cùng, các giá trị trung bình thực nghiệm hội tụ về xác suất so với kỳ vọng thực sự của chúng. Tuy nhiên, vì luật số lớn chỉ là một tiệm cận nên kết quả là nó không cung cấp thông tin về khoảng cách giữa sai số ước tính theo thực nghiệm và giá trị thực của nó đối với bất kỳ cỡ mẫu nào, hữu hạn hay đã cho trước.

Thay vào đó, chúng ta sẽ sử dụng thước đo bất bình đẳng về độ đo do Hoeffding đề suất để định lượng khoảng cách giữa giá trị trung bình thực nghiệm và giá trị kỳ vọng của chúng. Bắt đẳng thức Hoeffding được phát biểu như sau:

Gọi $\theta = (\theta_1, · · ·, \theta_n)$ là một dãy i.i.d. biến ngẫu nhiên và giả sử rằng với mọi i, $E_{\theta_i \sim D} (\theta_i) = \mu$ và $P_{\theta_i \sim D} [a_i \leq \theta_i \leq b] = 1$. Khi đó với $\varepsilon > 0$ bất kỳ ta có:

 $P_{\theta \sim D^m}[|\frac{1}{m} \Sigma^m_{i = 1} \theta_i| - \mu > \varepsilon_i] \leq 2 exp(\frac{ −2m\varepsilon^2}{ (b - a)^2})$.

2. Không-có-bữa-trưa-miễn-phí và số chiều-VC

Định lý No-Free-Lunch:

Cho X là tập miền vô hạn. Khi đó lớp giả thuyết $H: = \{0, 1\}^X$ không phải là PAC khả học. Chính xác hơn, hãy gọi m là bất kỳ số nào đó nhỏ hơn $(1/2) \sharp X$, đại diện cho kích thước tập huấn luyện. Khi đó tồn tại một phân phối D trên X và $f \in \{0, 1\}^X$ sao cho $P_{S \sim [(\Gamma_f) ∗ D]^m} [R_{(\Gamma_f) ∗ D} A(S) \geq 1/8] \geq 1 / 7$.

Nếu không hạn chế thêm về H, máy móc không thể học, việc overfitting có thể xảy ra.

• Điều kiện đủ để có thể học được một vấn đề học máy ($Z, H, R^L, A$) là gì?

Khsi niệm về chiều-VC (VapnikChervonenkis) có thể giúp chúng ta trả lời một phần nào đó.

Chều VC là thước đo năng lực (độ phức tạp, sức biểu đạt, độ phong phú hoặc tính linh hoạt) của một không gian H của các hàm có thể học được bằng thuật toán phân loại thống kê. Nó được định nghĩa là bản số của tập hợp điểm lớn nhất mà thuật toán có thể phá vỡ.

Định nghĩa: Lớp giả thuyết $H \subset \{0, 1 \}^X$ được gọi là phá vỡ một tập con hữu hạn $C \subset X$ nếu $\sharp H |_C = 2^{\sharp C}$.

Ví dụ. Một lớp giả thuyết H phá vỡ một tập hợp một điểm $x0 \in X$ nếu và chỉ khi có hai hàm $f, g \in H$ sao cho $f(x_0) \neq g(x_0)$.

Lưu ý rằng bất kỳ hàm nhị phân nào $h: X \rightarrow \{0, 1 \}$ được xác định duy nhất là tập con $h^{− 1}(1)$. Do đó, một lớp giả thuyết $H \subset \{ 0, 1 \}^X$ có thể được xác định với một tập hợp cũng được ký hiệu là H của các tập con của X. Do đó Định nghĩa về tập con hữu hạn bị vỡ có thể được viết lại như sau.

Định nghĩa (M. Steele, Ph.D. Thesis 1975, xuất bản năm 1978) Cho tập hợp H gồm các tập con của tập X, chúng ta nói rằng tập con hữu hạn C của X bị phá vỡ bởi H nếu mọi tập con B chứa trong C đều có thể được viết là giao điểm của C với một phần tử của H.

Định nghĩa. Chiều-VC, ký hiệu là VC dim (H), là kích thước lớn nhất của một tập $C \subset X$ có thể bị phá vỡ bởi H. Nếu H có thể phá vỡ các tập hợp có kích thước lớn tùy ý, chúng ta nói rằng H có vô hạn chiều-VC.

Ví dụ Gọi H là lớp các khoảng trong tập số thực, cụ thể là $H =\{h_{(a, b)}: a <b ∈ R \}$, trong đó $h_{(a, b)}: R \rightarrow \{0, 1 \}$ là hàm biểu thị của $h_{(a, b)}$. Lấy tập hợp $C = \{ 1, 2 \}$. Khi đó, H phá vỡ C tất cả các hàm $\{1, 2 \}^{(0,1)}$ có thể nhận được là giới hạn của một số hàm từ H đến C. Do đó VC dim(H) $\geq$ 2.

Bây giờ lấy một tập tùy ý $C = \{c_1 <c_2 <c_3 \}$ và gán nhãn tương ứng $(1, 0, 1)$. Rõ ràng là không thể ghi nhãn này bằng một khoảng: Bất kỳ khoảng $h_{(a, b)}$ nào chứa $c_1$ và $c_3$ (và do đó nhãn $c_1$ và $c_3$ với giá trị 1) phải chứa $c_2$ (và do đó nó gắn nhãn $c_2$ với 0). Do đó H không phá vỡ C. Do đó ta kết luận rằng VC dim(H) = 2. Chú ý rằng H có vô số phần tử.

Định lý cơ bản của phân loại nhị phân

Gọi $H \subset \{0, 1 \}^X$ là một lớp giả thuyết với rủi ro đúng. Hai điều sau đây là tương đương:

1. Bất kỳ quy tắc ERM nào là việc học PAC thành công đối với H, tức là H là người học được PAC với quy tắc ERM.

2. VC $dim(H) < \infty$.

Ý tưởng chính của việc chứng minh định lý cơ bản của phân loại nhị phân bao gồm việc thiết lập rằng tính hữu hạn của chiều-VC của H là đủ và cần thiết cho sự hội tụ đồng nhất (nghĩa là không phụ thuộc vào $D \in P (X × Y)$ và với $S \in (X × Y)^m$), sai số ước lượng của bộ giảm thiểu thực nghiệm $R^L_D(h_S) - min_{h \in H} R^L(h)$ bằng không, khi m tiến tới vô cùng. Khi chúng ta có sự hội tụ đồng nhất, bất đẳng thức Hoeffding ngụ ý bất đẳng thức PAC bắt buộc.

3. Độ phức tạp của các bài toán hồi quy

Trong thiết lập học PAC, chiều-VC là đặc tính tổ hợp của lớp giả thuyết H, không mang cấu trúc liên kết.

Thiết lập học PAC là thỏa đáng cho bài toán phân loại, trong đó chúng ta không có cấu trúc liên kết trên tập nhãn Y. Đối với bài toán hồi quy, trong đó Y = R, chúng ta thiết lập hàm mất bậc hai và MSE cho một dự báo $h \in H$.

Sự phức tạp của các bài toán hồi quy đã được Cucker và Smale xem xét và bài báo của họ “Về cơ sở toán học của việc học” vào năm 2001. Họ đã chứng minh khả năng học được (hoặc khả năng tổng quát hóa) của bài toán hồi quy dưới tính làm nhẹ giả thiết của lớp giả thuyết H. Tính gọn nhẹ liên quan đến tôpô trên không gian Banach C(X) của hàm liên tục với $C^0$-chuẩn $|| f ||_{C^0} = sup_{x\in X} |f (x)|$.

• Đối với hàm $f: X \rightarrow Y = R$ cho $f_Y: X × Y \rightarrow Y, (x, y) \rightarrow f (x) - y$.

Khi đó $MSE (f) = E_{\rho} (f^2_Y)$.

• Đối với $g: X × Y \rightarrow Y$ phương sai của nó $V_{\rho}(g)$ là $V_{\rho}(g): = E_{\rho}(g - E_{\rho}(g))^2 = E_{\rho}(g^2) - (E_{\rho}(g))^2$.

• Đối với một $H \subset C (X)$ và $f \in H$ 

$MSE_H (f): = MSE (f) - MSE (f_H)$,

trong đó $f_H = \text{arg }min_{f\in H} MSE (f)$.

• $MSE_H (f)$ được (gọi là) sai số ước lượng của f, hay sai số mẫu của f.

• Với $S = (z_1, · · ·, z_m) \in Z_m = (X × Y)^m$ ký hiệu là $f_S$ là cực tiểu của MS thực nghiệm 

$MSE_S(f):= \frac{1}{m}  \Sigma_{i=1}^m (f (x_i) - y_i)^2$.

Sự tồn tại của $f_S$ xuất phát từ tính thu gọn của H và tính liên tục của hàm $MSE_S$ trên H.

Định lý 2: Gọi H là tập con thu gọn của C(X). Giả sử rằng với mọi $f \in H$ ta có $| f (x) - y | ≤ M_{\rho}$- a. e., và đặt $V_{\rho}(H): = sup_{f\in H} V_{\rho}(f_Y)$.

Với mọi $\varepsilon > 0$, 

$P_{S \sim \rho^m} [MSE_H (f_S) \leq \varepsilon] \geq 1 - N(H, \frac{\varepsilon}{16M}2e^{\frac{− m\varepsilon^2}{8(4V_{\rho} (H) +\frac{1}{3}M^2\varepsilon)}}$, 

trong đó với $s \in R$, số phủ $N( H,s)$ là l nhỏ nhất sao cho tồn tại l đĩa trong H có bán kính s bao phủ H.

Sơ lược về cách chứng minh định lý Cucker-Smale. Chứng minh của định lý Cucker-Smale tương tự như chứng minh về khả năng học PAC của một lớp giả thuyết hữu hạn. Đầu tiên chúng ta thiết lập bất đẳng thức PAC cho một hàm. Sau đó, sử dụng tính thu gọn của H, chúng ta thiết lập bất đẳng thức PAC cho H. Ở đây chúng ta cần số phủ của H có thể được coi như là một phần tương tự của chiều-VC trong trường hợp phân loại nhị phân.

Định lý 2 ngụ ý một giới hạn trên cho độ phức tạp của mẫu để học một bài toán hồi quy với một tập nhỏ gọn $H \subset C(X)$. Cụ thể cho $(\varepsilon, \sigma)\in (0, 1)$ đã cho để đảm bảo rằng rủi ro kỳ vọng của rủi ro thực nghiệm giảm thiểu $f_S$ nhỏ hơn $\varepsilon$ đối với hầu hết mọi $S \in Z^m $ với độ tin cậy $1 - \sigma$ đủ để m thỏa mãn 

$m \geq \frac{8(4V_{\rho} (H) +\frac{1}{3}M^2\varepsilon)}{\varepsilon^2} × (ln(2N(H, \frac{\varepsilon}{16M})) + ln (\frac{1}{\sigma}))$.

• Nếu lớp giả thuyết H trong Định lý 2 là một tập con lồi trong H thì Cucker-Smale đã cải thiện ước lượng độ tin cậy $1−\sigma$ cho độ chính xác cho trước $\varepsilon$ (CS2001).

Kết bài: Trong bài giảng này, chúng ta học rằng khi có sự không chắc chắn, độ phức tạp của một vấn đề học tập, được xác định thông qua tổn thất dự kiến $​​R^L$ trên lớp giả thuyết H, cũng như sự thành công của một thuật toán học tập phải được đo lường theo thành phần xác suất. Khả năng học PAC của lớp giả thuyết H thỏa mãn tất cả các yêu cầu này. Trong bài toán phân loại nhị phân, một lớp giả thuyết là PAC có thể học được nếu và chỉ khi chiều VC VC dim(H) là hữu hạn.

Lý thuyết học PAC cũng ngụ ý rằng Không có Bữa trưa miễn phí, tức là không có thuật toán học PAC cho lớp giả thuyết phổ quát của tất cả các giả thuyết. Trong bài toán hồi quy, vì hàm tổn thất được xác định theo khoảng cách giữa giá trị thực và giá trị dự đoán, nên cấu trúc liên kết của một lớp giả thuyết là quan trọng. Thay vì chiều VC, là một độ phức tạp của mẫu tổ hợp, số bao trùm của một lớp giả thuyết sẽ định lượng độ phức tạp của nó.

Nhận xét cuối cùng Chúng ta cần lưu ý rằng ước lượng PAC trong định lý Cucker-Smale phụ thuộc vào phân phối chưa biết bên dưới một tập dữ liệu, được xác định bằng số $V_{\rho}(H)$. Mặt khác và khái niệm PAC khả học trong lý thuyết Vapnik-Chervonenkis là không có phân phối, tức là nó không phụ thuộc vào phân phối chưa biết bên dưới một tập dữ liệu được gắn nhãn. Ngày nay, có nhiều khái niệm về độ phức tạp của mẫu phụ thuộc vào sự phân phối cơ bản của một tập dữ liệu được gắn nhãn, trong đó đáng chú ý nhất là độ phức tạp Rademacher.

Nói chung, để ước tính độ phức tạp mẫu của một lớp giả thuyết là rất khó nhưng chúng ta đừng bao giờ sử dụng dữ kiện thực nghiệm để đi đến kết luận.

Như một ví dụ, chúng ta thử nghiệm với Giả thuyết Riemann ($\zeta (s) = \Sigma^{\infty}_{n = 1} \frac{1}{n^s}$ có không điểm của nó chỉ ở số nguyên chẵn âm và số phức với phần thực 1/2). Có một số cách để kiểm tra giả thuyết Riemann. Một phiên bản tương đương là sử dụng hàm Mobius $\mu (i)$ ($\mu (n) = 0$ nếu n chia hết cho bình phương một số nguyên tố, $\mu (n) = −1$ nếu n là một số lẻ các số nguyên tố phân biệt, $\mu (n) = 1$ nếu n là tích của một số chẵn của các số nguyên tố riêng biệt) và chứng minh / bác bỏ rằng với mọi $n > n_0$, $\Sigma^n_{i = 1} \mu (i) | \leq n{1/2 + \varepsilon}$.

Với n> 200 giá trị $|\Sigma \mu (i) | < 1/2\sqrt{n}$ nhưng đột nhiên đối với n = 7, 725, 038, 629 thì nó vượt quá $1 / 2\sqrt{n}$. Năm 1985, một ví dụ ngược lại cho giả thuyết Mertens $| \Sigma \mu (i) | <\sqrt{n}$ được tìm thấy với giới hạn tốt nhất hiện tại là n <e^{1,5910^40}.

Do đó, phỏng đoán của Mertens là sai, bất chấp tất cả các bằng chứng thực nghiệm mà chúng ta có cho đến nay.

Thank Ms LHV for material.