Phương pháp hàm nhân trong học máy

Tóm tắt nhanh về Perceptron và Margins

Mô hình Học tập Trực tuyến

• Mẫu đến tuần tự.
• Chúng ta cần đưa ra dự đoán.

Sau đó quan sát kết quả.

Với i=1, 2, …, :

Mô hình ràng buộc sai lầm

• Phân tích khôn ngoan, không đưa ra giả định phân phối.
• Mục tiêu: Giảm thiểu số lần mắc lỗi.

Thuật toán Perceptron trong mô hình trực tuyến

Bộ tách tuyến tính đồng nhất WLOG [w₀ = 0].

• Đặt t=1, bắt đầu với véc tơ toàn 0 𝑤₁.
• Cho mẫu 𝑥, dự đoán + iff 𝑤_𝑡 ⋅ 𝑥 ≥ 0
• Nếu sai, cập nhật như sau:
  • Sai về dương, 𝑤_𝑡+1 ← 𝑤_𝑡 + 𝑥
  • Sai về âm, 𝑤_𝑡+1 ← 𝑤_𝑡 − 𝑥

Lưu ý 1: w_t là tổng trọng số của các mẫu được phân loại không chính xác 𝑤_𝑡 = 𝑎_𝑖1𝑥_𝑖1 +⋯+ 𝑎_𝑖𝑘𝑥_𝑖𝑘

Vì vậy, 𝑤_𝑡 ⋅ 𝑥 = 𝑎_𝑖1𝑥_𝑖1 ⋅ 𝑥 + ⋯+ 𝑎_𝑖𝑘𝑥_𝑖𝑘 ⋅ 𝑥

Lưu ý 2: Số lần mắc lỗi chỉ phụ thuộc vào lề hình học của các mẫu đã thấy.

• Bất kể dãy dài bao nhiêu hoặc chiều n cao như thế nào!

Lề hình học

Định nghĩa: Lề của mẫu 𝑥 w.r.t. một sep. tuyến tính 𝑤 là khoảng cách từ 𝑥 đến mặt phẳng 𝑤 ⋅ 𝑥 = 0.

Lề của mẫu 𝑥1

Lề của mẫu 𝑥2

Nếu ||𝑤|| = 1, lề của x w.r.t. w là |𝑥 ⋅ 𝑤|.

Lề hình học

Định nghĩa: Lề của mẫu 𝑥 w.r.t. một sep. tuyến tính 𝑤 là khoảng cách từ 𝑥 đến mặt phẳng 𝑤 ⋅ 𝑥 = 0.

Định nghĩa: Lề 𝛾_𝑤 của một tập mẫu 𝑆 wrt một dấu phân cách tuyến tính 𝑤 là lề nhỏ nhất trên các điểm 𝑥 ∈ 𝑆.

Định nghĩa: Lề 𝛾 của một tập hợp các mẫu 𝑆 là 𝛾_𝑤 lớn nhất trên tất cả các dấu phân cách tuyến tính 𝑤.

Perceptron: Giới hạn sai lầm

Định lý: Nếu dữ liệu có thể phân tách tuyến tính theo lề 𝛾 và chỉ bên trong một quả cầu có bán kính 𝑅, thì Perceptron mắc ≤ (𝑅/𝛾)² sai lầm.

• Cho dù dãy n có chiều dài bao nhiêu đi chăng nữa!

Margin: khoảng trống khả dụng cho một giải pháp.

(Lề chuẩn hóa: nhân tất cả các điểm với 100 hoặc chia tất cả các điểm cho 100, không làm thay đổi số lượng lỗi; thuật toán là bất biến đối với tỷ lệ.)

Phần mở rộng của Perceptron

• Có thể sử dụng nó để tìm một dấu phân cách nhất quán với một tập S đã cho có thể phân tách tuyến tính theo lề 𝛾 (bằng cách quay vòng dữ liệu).
• Cũng có thể chuyển đổi bảo đảm ràng buộc sai lầm thành bảo đảm phân phối (đối với trường hợp các 𝑥_𝑖 đến từ một phân phối cố định).
• Có thể thích ứng với trường hợp không có dải phân cách hoàn hảo miễn là cái gọi là suy hao bản lề (nghĩa là tổng khoảng cách cần thiết để di chuyển các điểm để phân loại chúng theo lề lớn một cách chính xác) là nhỏ.
• Có thể được nhân hóa để xử lý các ranh giới quyết định phi tuyến tính!

Định lý: Nếu dữ liệu có thể phân tách tuyến tính theo lề 𝛾 và chỉ vào bên trong một quả cầu có bán kính 𝑅, thì Perceptron mắc ≤ (𝑅/𝛾)² sai lầm.

Ngụ ý rằng các bộ phân loại lề lớn có độ phức tạp nhỏ hơn!

Độ phức tạp của Sep. tuyến tính lề lớn

• Biết rằng trong Rⁿ chúng ta có thể phá vỡ n+1 điểm bằng các dấu phân cách tuyến tính, nhưng không phải là n+2 điểm (VC-dim của sep tuyến tính là n+1).
  • Điều gì sẽ xảy ra nếu chúng ta yêu cầu các điểm được phân tách tuyến tính bằng lề 𝛾?
  • Có thể có tối đa (^𝑅⁄_𝛾)² điểm bên trong quả cầu bán kính R có thể bị phá vỡ ở lề 𝛾 (có nghĩa là mọi cách ghi nhãn đều có thể đạt được bằng dấu phân cách có lề 𝛾).
• Vì vậy, các bộ phân loại lề lớn có độ phức tạp nhỏ hơn!
  • Ý nghĩa tốt đẹp cho môi trường học tập phân bổ thông thường.
  • Các bộ phân loại ít phải lo lắng về điều đó sẽ trông tốt đối với mẫu, nhưng lại xấu đối với tất cả….
• Ít bị khớp quá mức!!!!

Chủ đề quan trọng lề trong ML.

Cả độ phức tạp mẫu và hàm ý thuật toán.

Độ phức tạp của giới hạn mẫu/lỗi:

• Nếu lề lớn, # lỗi mà Peceptron mắc phải là nhỏ (không phụ thuộc vào dim của không gian)!
• Nếu lề lớn 𝛾 và nếu alg. tạo ra một bộ phân loại lề lớn, thì lượng dữ liệu cần thiết chỉ phụ thuộc vào R/𝛾 [Bartlett & Shawe-Taylor ’99].
  • Đề xuất tìm kiếm một bộ phân loại lề lớn…

Ý nghĩa của thuật toán:

• Perceptron, Kernels, SVMs…

Cho đến nay, chúng ta đã nói về lề trong ngữ cảnh của (gần như) bộ dữ liệu có thể phân tách tuyến tính

Điều gì xảy ra nếu không thể phân tách tuyến tính

Vấn đề: dữ liệu không thể phân tách tuyến tính trong biểu diễn đối tượng tự nhiên nhất

Không có dấu tách tuyến tính tốt trong biểu diễn pixel

Giải pháp:

• “Tìm hiểu một lớp hàm phức tạp hơn”
  • (ví dụ: cây quyết định, mạng thần kinh, tăng tốc).
• “Sử dụng hàm nhân” (một giải pháp gọn gàng thu hút nhiều sự chú ý)
• “Sử dụng mạng sâu”
• “Kết hợp hàm nhân và mạng sâu”

Tổng quan về các phương pháp hàm nhân

Hàm nhân là gì?

Kernel K là một def hợp pháp của tích vô hướng: tức là tồn tại một ánh xạ ẩn Φ s.t. K( , ) =Φ( )⋅ Φ( )

Chẳng hạn, K(x,y) = (x ⋅ y + 1)^d

Φ: (không gian n chiều) → n^d-không gian thứ nguyên

Tại sao Kernel lại quan trọng?

• Nhiều thuật toán chỉ tương tác với dữ liệu thông qua tích.
• Vì vậy, nếu thay x ⋅ z bằng K(x, z) thì chúng hoạt động hoàn toàn như thể dữ liệu ở trong không gian Φ chiều cao hơn.
• Nếu dữ liệu có thể phân tách tuyến tính bằng lề lớn trong không gian Φ, thì độ phức tạp của mẫu tốt.
  [Hoặc các thuộc tính chính quy khác để kiểm soát dung lượng.]

Hàm nhân

Định nghĩa

K(⋅,⋅) là một hàm nhân nếu có thể xem nó như một định nghĩa hợp pháp của tích trong:

• ∃ ϕ: X → R^N s.t. K(x, z) = ϕ(x) ⋅ ϕ(z)
  • Phạm vi của ϕ được gọi là Không gian Φ.
  • N có thể rất lớn.
• Nhưng hãy coi ϕ là hàm ý, không rõ ràng!!!!

Ví dụ

Với n=2, d=2, nhân K(x, z) = (x ⋅ z)^d tương ứng với

(𝑥₁, 𝑥₂) → Φ(𝑥) = (𝑥₁ ², 𝑥₂ ², √2𝑥₁𝑥₂)

Ví dụ

ϕ:R² → R³, (x₁, x₂) → Φ(x) = (x₁ ², x₂ ², √2x₁x₂)

ϕ(x) ⋅ ϕ(𝑧) = (x₁ ², x₂ ², √2x₁x₂) ⋅ (𝑧₁ ², 𝑧₂ ², √2𝑧₁𝑧₂)

= (x₁𝑧₁ + x₂𝑧₂) ² = (x ⋅ 𝑧) ² = K(x, z)

Hàm nhân

Định nghĩa

K(⋅,⋅) là hàm nhân nếu có thể xem nó như một định nghĩa hợp pháp của tích trong:

• ∃ ϕ: X → R^N s.t. K(x, z) = ϕ(x) ⋅ ϕ(z)
  • Phạm vi của ϕ được gọi là không gian Φ.
  • N có thể rất lớn.
• Nhưng hãy coi ϕ là hàm ý, không rõ ràng!!!!

Ví dụ

Lưu ý: không gian đặc trưng có thể không phải là duy nhất.

ϕ:R² → R³, (x₁, x₂) → Φ(x) = (x₁ ², x₂ ², √2x₁x₂)

ϕ(x) ⋅ ϕ(𝑧) = (x₁ ², x₂ ², √2x₁x₂) ⋅ (𝑧₁ ², 𝑧₂ ², √2𝑧₁𝑧₂)

= (x₁𝑧₁ + x₂𝑧₂) ² = (x ⋅ 𝑧) ² = K(x, z)

ϕ:R² → R⁴, (x₁, x₂) → Φ(x) = (x₁ ², x₂ ², x₁x₂, x₂x₁)

ϕ(x) ⋅ ϕ(𝑧) = (x₁ ², x₂ ², x₁x₂, x₂x₁) ⋅ (z₁ ², z₂ ², z₁z₂, z₂z₁)

= (x ⋅ 𝑧) ² = K(x, z)

Tránh mở rộng rõ ràng các tính năng

Không gian tính năng có thể phát triển rất lớn và rất nhanh….

Điều quan trọng là phải coi ϕ là ẩn chứ không phải rõ ràng!!!!

• Hàm nhân đa thức bậc 𝑑, 𝑘(𝑥, 𝑧) = (𝑥^⊤𝑧) ^𝑑 = 𝜙(𝑥) ⋅ 𝜙(𝑧)

– 𝑥₁ ^𝑑 , 𝑥₁𝑥₂…𝑥_𝑑 , 𝑥₁ ²𝑥₂…𝑥_𝑑−1

– Tổng số đặc trưng đó là (^{𝑑 + 𝑛 − 1} _𝑑) = ^{(𝑑 + 𝑛 − 1) !}⁄ _{𝑑! (𝑛 − 1) !}

– 𝑑 = 6, 𝑛 = 100, có 1,6 tỷ số hạng

𝑘(𝑥, 𝑧) = (𝑥^⊤𝑧) ^𝑑 = 𝜙(𝑥) ⋅ 𝜙(𝑧)

𝑂(𝑛) 𝑐𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛!

Hàm nhân hóa một thuật toán học

• Nếu tất cả các tính toán liên quan đến các thể hiện là về các tích bên trong thì:
  • Về mặt khái niệm, hoạt động trong một không gian diml rất cao và hiệu suất của thuật toán chỉ phụ thuộc vào khả năng phân tách tuyến tính trong không gian mở rộng đó.
  • Về mặt tính toán, chỉ cần sửa thuật toán bằng cách thay mỗi x ⋅ z bằng K(x, z).
• Ví dụ về các thuật toán có thể nhân:
  • phân loại: Perceptron, SVM.
  • hồi quy: tuyến tính, hồi quy sườn núi.
  • phân cụm: k-means.

Hàm nhân hóa thuật toán Perceptron

• Đặt t=1, bắt đầu với vectơ 0 𝑤₁.
• Cho mẫu 𝑥, dự đoán + iff 𝑤_𝑡 ⋅ 𝑥 ≥ 0
• Khi có lỗi, cập nhật như sau:
  • Lỗi ở giá trị dương, 𝑤_𝑡+1 ← 𝑤_𝑡 + 𝑥
  • Lỗi ở giá trị âm, 𝑤_𝑡+1 ← 𝑤_𝑡 − 𝑥

Dễ dàng để hàm nhân vì 𝑤_𝑡 tổng trọng số của các mẫu được phân loại không chính xác 𝑤_𝑡 = 𝑎_𝑖1𝑥_𝑖1 +⋯+ 𝑎_𝑖𝑘𝑥_𝑖𝑘

Thay thế 𝑤_𝑡 ⋅ 𝑥 = 𝑎_𝑖1𝑥_𝑖1 ⋅ 𝑥 + ⋯+ 𝑎_𝑖𝑘𝑥_𝑖𝑘 ⋅ 𝑥 bằng

𝑎_𝑖1 𝐾(𝑥_𝑖1 , 𝑥) + ⋯+ 𝑎_𝑖𝑘𝐾(𝑥_𝑖𝑘 , 𝑥)

Lưu ý: cần lưu trữ tất cả các sai lầm cho đến nay.

Hàm nhân hóa thuật toán Perceptron

• Cho trước 𝑥, dự đoán + iff

𝑎_𝑖1 𝐾(𝑥_𝑖1 , 𝑥) + ⋯+ 𝑎_𝑖𝑡−1𝐾(𝑥_𝑖𝑡−1 , 𝑥) ≥ 0

• Ở lỗi thứ 𝑡, cập nhật như sau:
  • Lỗi về dương, đặt 𝑎_𝑖𝑡 ← 1; trữ 𝑥_𝑖𝑡
  • Sai về âm, 𝑎_𝑖𝑡 ← −1; Lưu trữ 𝑥_𝑖𝑡

Perceptron 𝑤_𝑡 = 𝑎_𝑖1𝑥_𝑖1 +⋯+ 𝑎_𝑖𝑘𝑥_𝑖𝑘

𝑤_𝑡 ⋅ 𝑥 = 𝑎_𝑖1𝑥_𝑖1 ⋅ 𝑥 + ⋯+ 𝑎_𝑖𝑘𝑥_𝑖𝑘 ⋅ 𝑥 → 𝑎_𝑖1 𝐾(𝑥_𝑖1 , 𝑥) + ⋯+ 𝑎_𝑖𝑘𝐾(𝑥_𝑖𝑘 , 𝑥)

Hành vi/quy tắc dự đoán giống hệt như thể ánh xạ dữ liệu trong không gian 𝜙 và chạy Perceptron ở đó!

Làm điều này ngầm, vì vậy tiết kiệm tính toán!!!!!

Tổng quát hóa tốt nếu lề tốt

• Nếu dữ liệu có thể phân tách tuyến tính theo lề trong không gian 𝜙, thì ràng buộc lỗi nhỏ.
• Nếu lề 𝛾 trong không gian 𝜙 thì Perceptron mắc (^𝑅⁄_𝛾)² sai lầm.

Hàm nhân: Thêm ví dụ

• Tuyến tính: K(x, z) = x ⋅ 𝑧
• Đa thức: K(x, 𝑧) = (x ⋅ 𝑧) ^d hoặc K(x, 𝑧) = (1 + x ⋅ 𝑧) ^d
• Gaussian: K(x, 𝑧) = exp[ − ^{||𝑥−𝑧|| 2}⁄ _{2 𝜎²}]
• Nhân Laplace: K(x, 𝑧) = exp[ − ^{||𝑥−𝑧||}⁄ _{2 𝜎²}]
• Hàm nhân cho dữ liệu phi véc tơ, ví dụ: đo độ tương tự giữa các chuỗi.

Tính chất của hàm nhân

Định lý (Mercer)

K là hàm nhân khi và chỉ khi:

• K đối xứng
• Với mọi tập điểm huấn luyện 𝑥₁, 𝑥₂, … , 𝑥_𝑚 và với mọi 𝑎₁, 𝑎₂, … , 𝑎_𝑚 ∈ 𝑅, ta có:

∑_𝑖,𝑗 𝑎_𝑖𝑎_𝑗𝐾(𝑥_𝑖, 𝑥_𝑗) ≥ 0

𝑎^𝑇𝐾𝑎 ≥ 0

Tức là, 𝐾 = (𝐾 (𝑥_𝑖 , 𝑥_𝑗) )_{𝑖,𝑗=1,…,𝑛} là nửa xác định dương.

Kernel Methods

• Cung cấp mô-đun tuyệt vời.
• Không cần phải thay đổi thuật toán học cơ bản để phù hợp với một lựa chọn hàm nhân cụ thể.
• Ngoài ra, chúng ta có thể thay thế một thuật toán khác trong khi vẫn duy trì cùng một kernel.

Hàm nhân, Thuộc tính đóng

Dễ dàng tạo hàm nhân mới bằng cách sử dụng các hàm nhân cơ bản!

Dữ kiện: Nếu K₁ (⋅,⋅) và K₂ (⋅,⋅) là các hàm nhân c₁ ≥ 0, 𝑐₂ ≥ 0,

thì K(x, z) = c₁K₁(x, z) + c₂K₂(x, z) là nhân.

Ý tưởng chính: nối các khoảng cách 𝜙.

ϕ(x) = (√c₁ ϕ₁(x) , √c₂ ϕ₂(x))

ϕ(x) ⋅ ϕ(z) = c₁ ϕ₁(x) ⋅ ϕ₁(z) + c₂ ϕ₂(x) ⋅ ϕ₂(z)

Hàm nhân, Thuộc tính đóng

Dễ dàng tạo nhân mới bằng các nhân cơ bản!

Dữ kiện: Nếu K₁ (⋅,⋅) và K₂ (⋅,⋅) là hàm nhân,

khi đó K(x, z) = K₁(x, z) K₂(x, z) là một nhân.

Ý chính: ϕ(x) = (ϕ_1,i(x) ϕ_2,j(x)) _{𝑖∈{1,…,𝑛},𝑗∈{1,…,𝑚}}

ϕ(x) ⋅ ϕ(z) = ∑_𝑖,𝑗 ϕ_1,i(x) ϕ_2,j(x) ϕ_1,i(z) ϕ_2,j(z)

= ∑_𝑖 ϕ_1,i(x) ϕ_1,𝑖(z) (∑_𝑗 ϕ_2,𝑗(x) ϕ_2,j(z))

= ∑_𝑖 ϕ_1,i(x) ϕ_1,𝑖(z) K₂(x, z) = K₁(x, z) K₂(x, z)

Kernels, Discussion

• Nếu tất cả các tính toán liên quan đến các thể hiện là về các tích bên trong thì:
  • Về mặt khái niệm, hoạt động trong không gian diml rất cao và hiệu suất của thuật toán chỉ phụ thuộc vào khả năng phân tách tuyến tính trong không gian mở rộng đó.
  • Về mặt tính toán, chỉ cần sửa thuật toán bằng cách thay mỗi x ⋅ z bằng K(x, z).
• Rất nhiều thuật toán Machine Learning có thể kernel hóa được:
  • phân loại: Perceptron, SVM.
  • hồi quy: hồi quy tuyến tính.
  • phân cụm: k-means.

Kernels, Discussion

• Nếu tất cả các tính toán liên quan đến thể hiện đều là tích bên trong thì:
  • Về mặt khái niệm, làm việc trong không gian có diml rất cao và hiệu suất của thuật toán chỉ phụ thuộc vào khả năng phân tách tuyến tính trong không gian mở rộng đó.
  • Về mặt tính toán, chỉ cần sửa thuật toán bằng cách thay mỗi x ⋅ z bằng K(x, z).

Cách chọn kernel:

• Nhân thường mã hóa kiến thức miền (ví dụ: nhân chuỗi)
• Sử dụng Cross-Validation để chọn tham số, ví dụ: 𝜎 cho Gaussian Kernel K(x, 𝑧) = exp[ − ^{||𝑥−𝑧|| 2}⁄ _{2 𝜎²}]
• Học một hàm nhân tốt; ví dụ: [Lanckriet-Cristianini-Bartlett-El Ghaoui- Jordan’04]