✨Chiều VC

Trong lý thuyết học thống kê, còn gọi là lý thuyết học tính toán, chiều VC (viết tắt của chiều Vapnik–Chervonenkis) là một độ đo của khả năng phân loại của các thuật toán học máy. Nó được định nghĩa là lực lượng của tập hợp lớn nhất bị phá vỡ bởi thuật toán. Đây là một khái niệm cốt lõi trong lý thuyết Vapnik–Chervonenkis, đưa ra bởi Vladimir Vapnik và Alexey Chervonenkis.

Nói một cách đơn giản, khả năng phân loại của một thuật toán chính là độ phức tạp của thuật toán đó. Chẳng hạn xét thuật toán dựa trên dấu của đa thức bậc cao như sau: nếu giá trị của đa thức tại dữ liệu vào là dương thì thuật toán đưa ra kết quả dương tính, nếu giá trị đa thức là âm thì thuật toán đưa ra kết quả âm tính. Một đa thức có bậc càng cao thì càng có khả năng đổi dấu ở nhiều chỗ và càng phù hợp với dữ liệu hơn.

Phá vỡ

Một mô hình phân loại $f$ với tham số $\backslash theta$ phá vỡ một tập hợp điểm $(x\_1,x\_2,\backslash ldots,x\_n)$ nếu với mọi cách gán nhãn dương tính/âm tính cho các điểm này, tồn tại $\backslash theta$ sao cho $f$ cho kết quả hoàn toàn đúng tại tất cả n điểm.

Chiều VC của mô hình $f$ là $h\text{'}$ trong đó $h\text{'}$ là số $h$ lớn nhất sao cho tồn tại tập hợp kích thước $h$ bị phá vỡ bởi $f$.

Ví dụ, xét mô hình sử dụng bởi thuật toán perceptron trong không gian 2 chiều là các đường thẳng. Đường thẳng được dùng để tách rời các điểm dương tính và âm tính. Tồn tại tập hợp 3 điểm bị phá vỡ bởi mô hình này(mọi tập hợp 3 điểm không thẳng hàng đều bị phá vỡ). Tuy nhiên, không tồn tại tập hợp 4 điểm nào bị phá vỡ vì theo định lý Radon, mọi tập hợp 4 điểm đều có thể được chia thành hai tập hợp có bao lồi giao nhau. Vì vậy, chiều VC của mô hình này là 3. Dưới đây là minh họa cho 2 trong số 2³ = 8 cách gán nhãn cho 3 điểm.

Ứng dụng

Chiều VC được sử dụng rộng rãi trong lý thuyết học thống kê. Nó cho một chặn trên của xác suất sai của mô hình phân loại.

Nếu dữ liệu kiểm tra được chọn độc lập, cùng phân bố như nhau và như dữ liệu luyện tập, thì lỗi kiểm tra là không quá

: $+\; \backslash sqrt\{h(\backslash log(2N/h)+1)-\backslash log(\backslash eta/4)\backslash over\; N\}$

với xác suất $1-\backslash eta$, trong đó $h$ là chiều VC của mô hình phân loại và $N$ là kích thước dữ liệu vào (công thức này chỉ đúng khi $h\; \backslash ll\; N$). Có thể tìm ra chặn trên tương tự bằng độ phức tạp Rademacher, nhưng độ phức tạp Rademacher đôi khi cung cấp cái nhìn sâu sắc hơn chiều VC về các phương pháp thống kê, chẳng hạn như những phương pháp sử dụng hàm hạt nhân.

Trong hình học tính toán, chiều VC là một tham số quan trọng của kích thước lưới ε. Kích thước này quyết định tốc độ nhiều thuật toán cũng như độ chính xác của nhiều thuật toán xấp xỉ.