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 ${\displaystyle f}$ với tham số ${\displaystyle \theta }$ phá vỡ một tập hợp điểm ${\displaystyle (x_{1},x_{2},\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 ${\displaystyle \theta }$ sao cho ${\displaystyle 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 ${\displaystyle f}$ là ${\displaystyle h'}$ trong đó ${\displaystyle h'}$ là số ${\displaystyle h}$ lớn nhất sao cho tồn tại tập hợp kích thước ${\displaystyle h}$ bị phá vỡ bởi ${\displaystyle 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.

phá vỡ 3 điểm			không thể phá vỡ 4 đ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á

lỗi luyện tập${\displaystyle +{\sqrt {h(\log(2N/h)+1)-\log(\eta /4) \over N}}}$

với xác suất ${\displaystyle 1-\eta }$, trong đó ${\displaystyle h}$ là chiều VC của mô hình phân loại và ${\displaystyle N}$ là kích thước dữ liệu vào (công thức này chỉ đúng khi ${\displaystyle h\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ỉ.

Tham khảo

• Hướng dẫn về chiều VC Lưu trữ 2005-05-11 tại Wayback Machine của Andrew Moore
• V. Vapnik và A. Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities." Theory of Probability and its Applications, 16(2):264–280, 1971.
• A. Blumer, A. Ehrenfeucht, D. Haussler, và M. K. Warmuth. "Learnability and the Vapnik–Chervonenkis dimension." Journal of the ACM, 36(4):929–865, 1989.
• Hướng dẫn về SVM cho nhận dạng mẫu của Christopher Burges (có chứa thông tin về chiều VC)

Tham khảo