Wiki

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


{displaystyle f}

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




+




h
(
log

(
2
N

/

h
)
+
1
)

log

(
η

/

4
)

N





{displaystyle +{sqrt {h(log(2N/h)+1)-log(eta /4) over N}}}

với xác suất




1

η


{displaystyle 1-eta }

, trong đó




h


{displaystyle h}

là chiều VC của mô hình phân loại và




N


{displaystyle N}

là kích thước dữ liệu vào (công thức này chỉ đúng khi




h

N


{displaystyle hll 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 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) [1]

Tham khảo


—end—

Back to top button