CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Chiều VC (VC dimension) (1) – Khái niệm, lớp khái niệm

Posted by Trần Quốc Long on Tháng Bảy 1, 2009

Loạt bài này nói về một khái niệm quan trọng trong lý thuyết học máy. Đó là chiều VC (Vapnik-Chervonenkis dimension), mang tên hai giáo sư người Nga khám phá ra nó vào năm 1971. Chiều VC cho phép ta ước lượng được xác suất lỗi khi sử dụng hàm phân lớp.

Ta xét bài toán phân lớp các mẫu \displaystyle s thuộc không gian mẫu \displaystyle \mathbb{X} thành hai lớp \displaystyle \omega_1 = +1\displaystyle \omega_2 = -1. Như vậy, mỗi hàm phân lớp tương ứng 1-1 với một tập con \displaystyle \mathbf{c} \subset \mathbb{X} sao cho \displaystyle s thuộc lớp \displaystyle \omega_1 \Leftrightarrow s\in \mathbf{c}.

Định nghĩa (khái niệm – concept): Một tập con \displaystyle \mathbf{c} của \displaystyle \mathbb{X} gọi là một khái niệm.

Như vậy, cho trước một không gian mẫu \displaystyle \mathbb{X}, mỗi khái niệm cho ta biết lớp \displaystyle \omega_1 gồm những mẫu nào và lớp \displaystyle \omega_2 sẽ bao gồm các mẫu còn lại.

Định nghĩa (lớp khái niệm – concept class): Một tập các khái niệm gọi là một lớp khái niệm.

Lớp khái niệm cho phép ta khoanh vùng các khái niệm cần “học”. Khi đã có lớp khái niệm, “học” là việc chọn trong lớp khái niệm ra một khái niệm phù hợp với các thông tin đầu vào nhất (ví dụ: phù hợp với tập mẫu học).

Ví dụ:

  1. Giả sử không gian mẫu là trục số \displaystyle \mathbb{R}. Xét lớp khái niệm bao gồm các đoạn đóng trên \displaystyle \mathbb{R}:
    \displaystyle \mathcal{C}=\{[a,b]: a\leq b\}
    Drawing-concept-class-interval
  2. Giả sử không gian mẫu là mặt phẳng \displaystyle \mathbb{R}^2. Xét lớp khái niệm bao gồm các hình chữ nhật có cạnh song song với các trục:
    \displaystyle \mathcal{C}=\{[a,b]\times [c,d]:a\leq b, c\leq d\}
    Lớp khái niệm hình chữ nhật
  3. Giả sử không gian mẫu là \displaystyle \mathbb{R}^n. Xét lớp khái niệm bao gồm các hình cầu:
    \displaystyle \mathcal{C}=\{\mathrm{Ball}(a,r):a\in \mathbb{R}^n, r\geq 0\}
    Lớp khái niệm hình cầu

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: