Lý thuyết học máy III

Bài đọc tham khảo

CS 5966/6966: Theory of Machine Learning (Lecture 6: Rademacher Complexity)

Understanding Machine Learning: From Theory to Algorithms (Chapter 26 + 8)

Hôm nay:

Độ phức tạp mẫu cho xấp xỉ hàm. Lựa chọn mô hình.

Hai khía cạnh cốt lõi của học máy

Tính toán

Thiết kế thuật toán. Làm thế nào để tối ưu hóa?

Tự động tạo các quy tắc hoạt động tốt trên dữ liệu được quan sát.

• Ví dụ: hồi quy logistic, SVM, Adaboost, v.v.

Dữ liệu (được gắn nhãn)

Giới hạn tin cậy, khái quát hóa

Độ tin cậy cho hiệu quả của quy tắc đối với dữ liệu trong tương lai.

Các mô hình PAC/SLT cho phân loại được giám sát

Các mô hình PAC/SLT cho Học có giám sát

• X – không gian đối tượng/đặc trưng; phân phối D trên X
  • ví dụ: X = R^d hoặc X = {0,1}^d
• Thuật toán xem mẫu huấn luyện S: (x₁,c*(x₁)),…, (x_m,c*(x_m)), x_i i.i.d. từ D
  • các mẫu được gắn nhãn – i.i.d. được rút ra từ D và được gắn nhãn bởi đích c^*
  • nhãn ∈ {-1,1} – phân loại nhị phân
• Thuật toán tối ưu hóa trên S, tìm giả thuyết ℎ.
• Mục tiêu: h có lỗi nhỏ trên D.
  • 𝑒𝑟𝑟_𝐷 (ℎ) = Pr_𝑥~ 𝐷 (ℎ(𝑥) ≠ 𝑐^∗(𝑥))
• Cố định không gian giả thuyết H [có độ phức tạp không quá lớn]
  • Khả thi: 𝑐^∗ ∈ 𝐻.
  • Bất khả tri: 𝑐^∗ “gần với” H.

Độ phức tạp của mẫu đối với học có giám sát

Trường hợp có thể thực hiện được

Người học nhất quán

• Đầu vào: S: (x₁,c*(x₁)),…, (x_m,c*(x_m))
• Đầu ra: Tìm h trong H phù hợp với S (nếu tồn tại).

Tuyến tính trong 1/𝜖

Xác suất trên các mẫu khác nhau của m mẫu huấn luyện

Độ phức tạp của mẫu: Không gian giả thuyết vô hạn

Trường hợp có thể thực hiện được

Ví dụ: H= dấu phân cách tuyến tính trong R^d

VCdim(H)= d+1

Độ phức tạp của mẫu tuyến tính theo d

Vì vậy, nếu nhân đôi số lượng tính năng, thì tôi chỉ cần gấp đôi số lượng mẫu để hoạt động tốt.

Nếu c^∗ ∉ H thì sao?

Độ phức tạp của mẫu: Hội tụ đồng nhất

Trường hợp bất khả tri

Tối thiểu hóa rủi ro theo kinh nghiệm (ERM)

• Đầu vào: S: (x₁,c*(x₁)),…, (x_m,c*(x_m))
• Đầu ra: Tìm h trong H với err_S(h) nhỏ nhất

1/𝜖² phụ thuộc [ngược lại với 1/𝜖 để có thể thực hiện được]

Hoeffding bounds

Xét đồng xu thiên vị p lật m lần.

Gọi N là # mặt ngửa được quan sát. Rõ ràng E [N⁄m] = p.

[N = X₁ + X₂ + … + X_m, X_i = 1 với xác suất p, 0 với xác suất 1-p.]

Bất đẳng thức Hoeffding

Cho 𝛾 ∈ [0,1].

𝑃 [|𝑁⁄𝑚 − 𝑝| ≥ 𝛾] ≤ 𝑒^{−2𝑚𝛾2}

Đuôi giảm theo cấp số nhân

Bất đẳng thức đuôi: khối lượng xác suất giới hạn ở đuôi phân phối (mức độ tập trung của một biến ngẫu nhiên xung quanh kỳ vọng của nó).

Độ phức tạp của mẫu: Giả thuyết hữu hạn Không gian

Trường hợp bất khả tri

Chứng minh: Hoeffding & ràng buộc hợp.

• Cố định h; theo Hoeffding, xác suất rằng |err_S (h) − err_D (h)| ≥ ϵ tối đa là 2e^−2mϵ2
• Bằng hợp bị chặn trên mọi ℎ ∈ 𝐻, xác suất rằng ∃h s.t. |err_S (h) − err_D (h)| ≥ ϵ nhiều nhất là 2|H|e^−2mϵ2. Đặt thành 𝛿. Giải quyết.

Thực tế:

W.h.p. ≥ 1 − 𝛿,err_D (ℎ^{^}) ≤ err_D (h^∗) + 2ϵ, h^{^} là đầu ra ERM, h^∗ là hyp. với tỷ lệ sai số thực nhỏ nhất .

Độ phức tạp của mẫu: Không gian giả thuyết hữu hạn

Trường hợp bất khả tri

1) Có bao nhiêu mẫu đủ để có được UC whp (vì vậy thành công cho ERM).

sự phụ thuộc 1/𝜖² [ngược lại với 1/𝜖 cho khả thi], nhưng nhận được thứ gì đó mạnh hơn.

2) Phong cách Lý thuyết học thống kê:

Với xác suất ít nhất 1 − 𝛿, với mọi h ∈ H:

err_D (h) ≤ err_S (h) + √1⁄2m(ln(2|H|) + ln(1⁄𝛿)).

√1⁄𝑚 trái ngược với 1⁄𝑚 đối với có thể thực hiện được

Độ phức tạp mẫu: Không gian giả thuyết vô hạn

Trường hợp bất khả tri

1) Có bao nhiêu mẫu đủ để có được UC whp (vì vậy thành công cho ERM).

2) Phong cách Lý thuyết học thống kê:

Với xác suất ít nhất 1 − 𝛿, với mọi h ∈ H:

err_D (h) ≤ err_S (h) + O (√1⁄2m(VCdim(H) ln(em⁄VCdim(H)) + ln(1⁄δ))).

Giới hạn khái quát hóa chiều VC

Ví dụ, err_D (h) ≤ err_S (h) + O (√1⁄2m(VCdim(H) ln(em⁄VCdim(H)) + ln(1⁄δ))).

Giới hạn VC: giới hạn độc lập phân phối

• Generic: giữ cho bất kỳ lớp khái niệm và bất kỳ phân phối. [gần như chặt chẽ trong WC so với lựa chọn D]

• Có thể phân phối cụ thể rất lỏng lẻo. lành tính hơn trường hợp xấu nhất… .
• Giữ chỉ để phân loại nhị phân; chúng ta muốn giới hạn cho xấp xỉ fns nói chung (ví dụ: phân loại và hồi quy đa lớp).

Giới hạn độ phức tạp Rademacher

[Koltchinskii & Panchenko 2002]

• Phụ thuộc vào phân phối/dữ liệu. Chặt chẽ hơn cho các bản phân phối đẹp.
• Áp dụng cho các lớp chung của các hàm có giá trị thực & có thể được sử dụng để khôi phục VCbounds cho phân loại được giám sát.
• Kỹ thuật nổi bật về giới hạn tổng quát hóa trong thập kỷ qua.

Xem “Giới thiệu về lý thuyết học thống kê”

O. Bousquet, S. Boucheron và G. Lugosi.

Độ phức tạp Rademacher

Thiết lập vấn đề

• Một không gian Z và một distr. D_|Z
• F là một lớp các hàm từ Z đến [0,1]
• S = {z₁, … , z_m} là i.i.d. từ D_|Z

Muốn có xác suất cao. Giới hạn hội tụ đều, tất cả f ∈ F thỏa mãn:

E_D [f(z)] ≤ E_S [f(z)] + số hạng(độ phức tạp của F, độ đẹp của D/S)

Thước đo độ phức tạp nào?

Ví dụ, Z = X × Y, Y = {−1,1}, H = {h: X → Y} không gian hyp. (ví dụ: lin. sep)

Y rời rạc tổng quát

F = L(H) = {l_h: X → Y}, trong đó l_h(𝑧 = (x, y)) = 1_{{h(x)≠𝑦}}

[Hàm mất fnc do h và mất 0/1]

Khi đó E_𝑧~𝐷 [l_h(z)] = err_D (h) và E_S [l_h(z)] = err_S (h).

err_D [h] ≤ err_S [h] + số hạng(độ phức tạp của H, độ đẹp của D/S)

Độ phức tạp Rademacher

Không gian Z và một distr. D_|Z; F là một lớp các hàm từ Z đến [0,1]

Cho S = {z₁, … , z_m} là i.i.d từ D_|Z.

Độ phức tạp Rademacher theo kinh nghiệm của F là:

R^{^}_m(F) = E_σ1,…,σm [sup_f∈F 1⁄m∑_iσ_if(z_i)]

trong đó 𝜎_𝑖 là i.i.d. biến Rademacher được chọn thống nhất từ {−1,1}.

Độ phức tạp Rademacher của F là: R_m (F) = E_S[R^{^}_m(F)]

sup đo lường cho bất kỳ tập S và véc tơ Rademacher 𝜎 đã cho, tương quan cực đại giữa f(z_i) và 𝜎_𝑖 với mọi f ∈ F

Vì vậy, lấy kỳ vọng trên 𝜎 điều này đo lường khả năng của lớp F phù hợp với nhiễu ngẫu nhiên.

Độ phức tạp Rademacher

Không gian Z và một distr. D_|Z; F là một lớp các hàm từ Z đến [0,1]

Cho S = {z₁, … , z_m} là i.i.d từ D_|Z.

Độ phức tạp Rademacher theo kinh nghiệm của F là:

R^{^}_m(F) = E_σ1,…,σm [sup_f∈F 1⁄m∑_iσ_if(z_i)]

trong đó 𝜎_𝑖 là i.i.d. các biến Rademacher được chọn thống nhất từ {−1,1}.

Độ phức tạp Rademacher của F là: R_m (F) = E_S[R^{^}_m(F)]

Định lý:

Whp mọi f ∈ F thỏa mãn:

Hữu ích nếu nó phân rã theo m.

Độ phức tạp Rademacher

Không gian Z và một distr. D_|Z; F là một lớp các hàm từ Z đến [0,1]

Cho S = {z₁, … , z_m} là i.i.d từ D_|Z.

Độ phức tạp Rademacher theo kinh nghiệm của F là:

R^{^}_m(F) = E_σ1,…,σm [sup_f∈F 1⁄m∑_iσ_if(z_i)]

trong đó 𝜎_𝑖 là i.i.d. các biến Rademacher được chọn thống nhất từ {−1,1}.

Độ phức tạp Rademacher của F là: R_m (F) = E_S[R^{^}_m(F)]

Ví dụ:

1) F={f}, thì R^{^}_m(F) = 0

[Tính tuyến tính của kỳ vọng: mỗi σ_if(z_i) riêng lẻ có kỳ vọng 0.]

2) F={all 0/1 fnc}, thì R^{^}_m(F) = 1/2

[Để cực đại hóa tập hợp f(z_i) = 1 khi σ_i = 1 và f(z_i) = 0 khi σ_i = −1. Khi đó đại lượng bên trong kỳ vọng là #1′𝑠 ∈ 𝜎, là m/2 theo độ tuyến tính của kỳ vọng.]

Độ phức tạp Rademacher

Không gian Z và một distr. D_|Z; F là một lớp các hàm từ Z đến [0,1]

Cho S = {z₁, … , z_m} là i.i.d từ D_|Z.

Độ phức tạp Rademacher thực nghiệm của F là:

R^{^}_m(F) = E_σ1,…,σm [sup_f∈F 1⁄m∑_iσ_if(z_i)]

trong đó 𝜎_𝑖 là i.i.d. biến Rademacher được chọn thống nhất từ {−1,1}.

Độ phức tạp Rademacher của F là: R_m (F) = E_S[R^{^}_m(F)]

Ví dụ:

1) F={f}, thì R^{^}_m(F) = 0

2) F={all 0/1 fnc}, thì R^{^}_m(F) = 1/2

3) F=L(H), H=phân loại nhị phân thì:

H hữu hạn:

Giới hạn độ phức tạp Rademacher

Không gian Z và một distr. D_|Z; F là một lớp các hàm từ Z đến [0,1]

Cho S = {z₁, … , z_m} là i.i.d từ D_|Z.

Độ phức tạp Rademacher thực nghiệm của F là:

R^{^}_m(F) = E_σ1,…,σm [sup_f∈F 1⁄m∑_iσ_if(z_i)]

trong đó 𝜎_𝑖 là i.i.d. biến Rademacher được chọn thống nhất từ {−1,1}.

Độ phức tạp Rademacher của F là: R_m (F) = E_S[R^{^}_m(F)]

Định lý:

Whp tất cả f ∈ F thỏa mãn:

Dữ liệu phụ thuộc ràng buộc!

Kỳ vọng có giới hạn của từng f xét về giá trị trung bình theo kinh nghiệm của nó & RC của F

Proof sử dụng Thủ thuật đối xứng và lấy mẫu ma! (giống như đối với giới hạn VC)

Tổ hợp Rademacher: Phân loại nhị phân

Thực tế: H = {h: X → Y} không gian hyp. (ví dụ: lin. sep) F= L(H), d=VCdim(H):

Vì vậy, theo bổ đề Sauer, 

Định lý: Với mọi H, mọi distr. D, whp ≥ 1 − 𝛿 mọi h ∈ H thỏa mãn:

tổng quát hóa ràng buộc

Còn nhiều công dụng nữa!!! Giới hạn lề cho SVM, tăng cường, giới hạn hồi quy, v.v.

Chúng ta có thể sử dụng giới hạn của mình để lựa chọn mô hình không?

True Error, Training Error, Overfitting

Lựa chọn mô hình: cân bằng giữa việc giảm lỗi đào tạo và giữ cho H đơn giản.

err_D (h) ≤ err_S (h) + R_m (H) +…

Tối thiểu hóa rủi ro cấu trúc (SRM)

𝐻₁ ⊆ 𝐻₂ ⊆ 𝐻₃ ⊆ ⋯ ⊆ 𝐻_𝑖 ⊆…

Điều gì xảy ra nếu chúng ta tăng m?

Đường cong màu đen sẽ ở gần đường cong màu đỏ lâu hơn, mọi thứ dịch chuyển sang phải…

Giảm thiểu Rủi ro Cấu trúc (SRM)

𝐻₁ ⊆ 𝐻₂ ⊆ 𝐻₃ ⊆ ⋯ ⊆ 𝐻_𝑖 ⊆…

Giảm thiểu Rủi ro Cấu trúc (SRM)

• 𝐻1 ⊆ 𝐻2 ⊆ 𝐻3 ⊆ ⋯ ⊆ 𝐻𝑖 ⊆…
• h^{^}_k = argmin_h∈Hk {err_S(h)}
  • Khi k tăng, err_S (h^{^}_k) giảm nhưng số hạng phức tạp. tăng lên.
• 𝑘^{^} = argmin_k≥1{err_S (h^{^}_k) + độ phức tạp(H_k)}
  • Đầu ra ℎ^{^} = ℎ^{^}_𝑘^{^}

Yêu cầu: W.h.p., err_D (h^{^}) ≤ min_k^∗min_{h^∗∈Hk^∗}[err_D (h^∗) + 2complexity (H_k^∗)]

Chứng minh:

• Chúng ta chọn h^{^} s.t. err_s (h^{^}) + độ phức tạp (H_k^{^}) ≤ err_S (h^∗) + độ phức tạp (H_k^∗).
• Whp, err_D (h^{^}) ≤ err_s (h^{^}) + độ phức tạp (H_k^{^}).
• Whp, err_S (h^∗) ≤ err_D (h^∗) + độ phức tạp (H_k^∗).

Các kỹ thuật để xử lý khớp quá mức

• Giảm thiểu rủi ro cấu trúc (SRM). 𝐻₁ ⊆ 𝐻₂ ⊆ ⋯ ⊆ 𝐻_𝑖 ⊆…
  Giảm thiểu chung chung. ràng buộc: ℎ^{^} = argmin_k≥1{err_S (h^{^}_k) + complexity(H_k)}
  • Thường khó tính toán….
  • Trường hợp tốt nếu có thể: M. Kearns, Y. Mansour, ICML’98, “A Fast, Bottom-Up Decision Tree Pruning Algorithm with Near-Optimal Generalization”
• Chính quy hóa: họ chung có liên quan chặt chẽ với SRM
  • Ví dụ: SVM, hồi quy logistic chính quy, v.v.
  • giảm thiểu các biểu thức có dạng: 
    • Chuẩn nào đó khi H là một không gian vectơ; ví dụ, chuẩn L2
    • Được chọn thông qua xác nhận chéo
• Xác thực chéo:
  • Giữ lại một phần dữ liệu huấn luyện và sử dụng nó làm đại diện cho lỗi tổng quát hóa

Những điều bạn nên biết

• Khái niệm về độ phức tạp của mẫu.
• Hiểu lý do đằng sau độ phức tạp của mẫu đơn giản giới hạn cho H [câu hỏi thi!].
• Sự phá vỡ, thứ nguyên VC như thước đo độ phức tạp, bổ đề Sauer, dạng giới hạn VC (giới hạn trên và giới hạn dưới).
• Độ phức tạp Rademacher.
• Lựa chọn mô hình, giảm thiểu rủi ro cấu trúc.

Chính quy hóa L2 so với L1