Nâng lên Các chiều Cao hơn

XOR không tách biệt tuyến tính trong 2D. Giải pháp: ánh xạ dữ liệu vào không gian có chiều cao hơn nơi nó trở thành tách biệt tuyến tính. Đây là ý tưởng cốt lõi của thủ thuật kernel.

Bản đồ đặc trưng: một hàm số φ: ℝ^n → ℝ^m (m > n) biến đổi mỗi điểm đầu vào thành một biểu diễn có chiều cao hơn.

Đối với XOR, một bản đồ đặc trưng hữu ích: φ(x₁, x₂) = (x₁, x₂, x₁x₂)

Điều này thêm một chiều thứ ba z = x₁ × x₂. Các điểm XOR biến đổi thành:

- (0,0) → (0, 0, 0), lớp 0

- (1,0) → (1, 0, 0), lớp 1

- (0,1) → (0, 1, 0), lớp 1

- (1,1) → (1, 1, 1), lớp 0

Trong 3D: các điểm lớp 0 nằm tại (0,0,0) và (1,1,1); các điểm lớp 1 nằm tại (1,0,0) và (0,1,0). Bây giờ hãy tìm một mặt phẳng tách biệt.

Mặt phẳng tách biệt trong 3D

Sau bản đồ đặc trưng φ(x₁, x₂) = (x₁, x₂, x₁x₂), dữ liệu XOR sống trong 3D. Một siêu phẳng trong 3D có phương trình w₁x₁ + w₂x₂ + w₃z + b = 0.

Định lý Cover: Tại sao các chiều cao hơn Trợ giúp

Định lý Cover (1965): một vấn đề phân loại phức tạp được đặt trong không gian có chiều cao hơn có nhiều khả năng tách biệt tuyến tính hơn trong không gian có chiều thấp hơn, với điều kiện là không gian không được dân cư dày đặc.

Phát biểu không chính thức: nếu bạn ánh xạ n điểm dữ liệu sang không gian có chiều d >> n, xác suất gán nhãn ngẫu nhiên tách biệt tuyến tính tiến gần đến 1.

Phiên bản chính thức: đối với n điểm ở vị trí chung trong ℝ^d, số lượng dichotomies tách biệt tuyến tính (gán lớp) chính xác là 2 × Σ_{k=0}^{d} C(n−1, k) cho d < n, và bằng 2^n (tất cả dichotomies) cho d ≥ n − 1.

Hàm ý thực tế: bản đồ đặc trưng φ nâng XOR lên 3D là một trường hợp đặc biệt của nguyên tắc chung này. Nâng lên các chiều cao hơn tăng khả năng tách biệt. Chi phí: nhiều tham số hơn để phù hợp, rủi ro quá khớp cao hơn.

Sự cân bằng Thiên vị-Phương sai như một Hình học

Ranh giới quyết định có chiều thấp (ít tham số): thiên vị cao (không thể chụp các mẫu phức tạp), phương sai thấp (ổn định trên các mẫu). Ranh giới có chiều cao (nhiều tham số): thiên vị thấp, phương sai cao (có thể quá khớp với tiếng ồn trong dữ liệu đào tạo).

Thứ nguyên VC: Bộ phân loại có Biểu cảm bao nhiêu?

Thứ nguyên Vapnik-Chervonenkis (VC) của một lớp giả thuyết H đo độ phức tạp của lớp: số lượng lớn nhất của các điểm mà H có thể vỡ (phân loại chính xác trong tất cả 2^n nhãn có thể có).

Perceptron trong ℝ^d: thứ nguyên VC = d + 1. Một siêu phẳng d-chiều có thể vỡ d + 1 điểm (ở vị trí chung) nhưng không vỡ d + 2.

Thứ nguyên VC xác định độ phức tạp mẫu: để học một giả thuyết với lỗi tổng quát hóa ε với xác suất 1 − δ, bạn cần khoảng n ≥ (d × log(1/ε) + log(1/δ)) / ε mẫu, trong đó d là thứ nguyên VC.

Ranh giới Quyết định & Giới hạn Khả năng Máy

Hình học của các ranh giới quyết định liên kết trực tiếp với các giới hạn lý luận máy của Hamming.

Một perceptron một lớp (bộ phân loại siêu phẳng) không thể giải XOR. Đây là lời chỉ trích của Minsky & Papert về các perceptron ban đầu vào năm 1969. Lập luận hình học: XOR không tách biệt tuyến tính. Máy không thể giải quyết nó, không phải vì thiếu sức mạnh tính toán, mà vì một sự không tương thích hình học cơ bản giữa lớp giả thuyết và vấn đề.

Giải pháp: các mạng lưới đa lớp có thể biểu diễn các ranh giới phi tuyến tính. Các lớp ẩn thực hiện bản đồ đặc trưng φ — nâng dữ liệu lên các chiều cao hơn nơi tách biệt tuyến tính trở nên có thể. Mỗi nơ-ron ẩn tính toán một siêu phẳng; sự kết hợp của nhiều siêu phẳng xấp xỉ các đường cong.

Lịch sử này ánh xạ vào quan sát của Hamming: mọi giới hạn của lý luận máy có một cấu trúc hình học ở bên dưới. Nhiệm vụ không phải là tranh luận về việc máy có thể 'suy nghĩ' hay không mà là xác định các ràng buộc hình học và tìm cách vượt qua chúng.