Trong lĩnh vực machine learning, việc đánh giá độ phức tạp của một lớp hàm là vô cùng quan trọng để hiểu khả năng học và tổng quát hóa của mô hình. Bài viết này sẽ đi sâu vào phân tích các độ đo phức tạp như VC dimension (Vapnik–Chervonenkis dimension), fat-shattering dimension, và các độ đo entropy khác cho một lớp các hàm "gần như hằng số" (essentially constant). Chúng ta sẽ khám phá những giới hạn và ứng dụng của chúng trong việc xây dựng các bộ phân loại hiệu quả.
Giả sử chúng ta có một tập hợp trừu tượng X (có thể có cấu trúc metric, ví dụ Rd). Cho một giá trị α rất nhỏ (0 < α ≪ 1), chúng ta định nghĩa một lớp hàm Hα như sau:
Hα := {h: X → [0, 1] | ∃ ĥ ∈ [0, 1] sao cho |h(x) − ĥ| ≤ α ∀ x ∈ X}.
Nói cách khác, Hα là tập hợp các hàm số mà giá trị của nó luôn "gần" một giá trị hằng số ĥ trong khoảng [0, 1], với sai số không quá α. Câu hỏi đặt ra là: liệu một hàm số thuộc lớp này có thể là một bộ phân loại tốt trong machine learning hay không? Để trả lời câu hỏi này, chúng ta cần đánh giá độ phức tạp của lớp hàm Hα.
Việc tìm ra các giới hạn trên và dưới cho các độ đo này sẽ giúp chúng ta hiểu rõ hơn về khả năng biểu diễn và học của lớp hàm Hα.
Một kết quả quan trọng từ một nghiên cứu năm 1997 cho thấy mối liên hệ giữa metric entropy và fat-shattering dimension:
fatH(4ϵ)/32 ≤ maxP log2(N(ϵ, H, L1(dP))) ≤ c1 fatH(c2ϵ) (log2(1/ϵ))^2
Trong đó, fatH(γ) là fat-shattering dimension của H tại scale γ, N(ϵ, H, L1(dP)) là covering number của H, và c1, c2 là các hằng số tuyệt đối. Điều này có nghĩa là, nếu chúng ta có thể ước tính fat-shattering dimension của Hα, chúng ta có thể suy ra các giới hạn cho metric entropy của nó.
Trong trường hợp đơn giản X = [0, 1], việc tính toán fat-shattering dimension của Hα trở nên dễ dàng hơn. Tuy nhiên, kết quả này có thể không tổng quát hóa tốt cho các không gian có chiều cao hơn.
Một số ý kiến cho rằng lớp hàm Hα có thể không phù hợp cho mục đích phân loại vì nó quá "giàu" (rich). Trong trường hợp X = [0, 1], chúng ta có thể tìm thấy vô số hàm hτ ∈ Hα sao cho khoảng cách giữa hai hàm bất kỳ trong số chúng là α/2. Điều này dẫn đến việc covering number N(ε, Hα, L1([0, 1])) = ∞ khi ε ≤ α/2.
Điều này cho thấy rằng, ở mức độ chính xác ε ≃ α, lớp hàm Hα gần như chỉ là một điểm (bất kỳ hai hàm h ∈ Hα nào cũng không thể phân biệt được ở scale này).
Thay vì sử dụng định nghĩa "gần như hằng số" đơn giản, chúng ta có thể xem xét các lớp hàm khác, sử dụng các độ đo tinh tế hơn về sự biến thiên của hàm. Một số lựa chọn tự nhiên bao gồm:
Những lớp hàm này có thể nắm bắt được cấu trúc hình học của X tốt hơn, và do đó, có thể cung cấp các bộ phân loại hiệu quả hơn.
Việc đánh giá độ phức tạp của các lớp hàm là một bước quan trọng trong việc xây dựng các mô hình machine learning có khả năng tổng quát hóa tốt. Mặc dù lớp hàm "gần như hằng số" Hα có thể không phù hợp cho mục đích phân loại trong nhiều trường hợp, việc phân tích các độ đo như VC dimension và fat-shattering dimension cung cấp cho chúng ta những hiểu biết sâu sắc về khả năng biểu diễn và học của các lớp hàm này. Việc sử dụng các lớp hàm thay thế, như hàm BV hoặc hàm Hölder, có thể là một lựa chọn tốt hơn trong nhiều tình huống thực tế.
Bài viết liên quan