Máy Vectơ hỗ trợ (SVM)

• Máy Vectơ hỗ trợ (SVM).
• Học bán giám sát.
  • SVM bán giám sát.

Máy Vectơ hỗ trợ (SVM).

Một trong những thuật toán phân loại có động lực tốt nhất về mặt lý thuyết và thực tế hiệu quả nhất trong học máy.

Được thúc đẩy trực tiếp bởi Margins và Kernels!

Lề hình học

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

Đị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 𝑤.

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/Sai lầm:

• Nếu lề lớn, # lỗi 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].

Ý nghĩa thuật toán

• Đề xuất tìm kiếm một bộ phân loại lề lớn … SVM

Máy vectơ hỗ trợ (SVM)

Tối ưu hóa trực tiếp cho dấu tách lề tối đa: SVM

Đầu tiên, giả sử chúng ta biết cận dưới của lề 𝛾

Đầu vào: 𝛾, S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tìm: một số w trong đó:

• ||w|| ² = 1
• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 𝛾

Đầu ra: w, dấu tách lề 𝛾 trên S

Trường hợp có thể thực hiện được, trong đó dữ liệu có thể phân tách tuyến tính bằng lề 𝛾

Máy vectơ hỗ trợ (SVM)

Tối ưu hóa trực tiếp cho dấu tách lề tối đa: SVM

Ví dụ: tìm kiếm 𝛾 tốt nhất có thể

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tìm: một số w và tối đa 𝛾 trong đó:

• ||w|| ² = 1
• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 𝛾

Đầu ra: dấu tách lề tối đa trên S

Máy vectơ hỗ trợ (SVM)

Tối ưu hóa trực tiếp cho dấu tách lề tối đa: SVM

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Cực đại hóa 𝛾 theo ràng buộc:

• ||w|| ² = 1
• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 𝛾

Máy vectơ hỗ trợ (SVM)

Tối ưu hóa trực tiếp cho dấu tách lề tối đa: SVM

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Cực đại hóa 𝛾 dưới ràng buộc:

• ||w|| ² = 1
• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 𝛾

hàm mục tiêu

ràng buộc

Đây là bài toán tối ưu có ràng buộc

• Ví dụ nổi tiếng về tối ưu hóa có ràng buộc: lập trình tuyến tính, trong đó hàm mục tiêu là tuyến tính, các ràng buộc là (bất) đẳng thức tuyến tính

Support Vector Machines (SVM)

Tối ưu hóa trực tiếp cho dấu tách lề tối đa: SVM

Dữ liệu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Cực đại hóa 𝛾 theo ràng buộc:

• ||w|| ² = 1
• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 𝛾

Ràng buộc này là phi tuyến.

Thực chất là không lồi

Máy vectơ hỗ trợ (SVM)

Tối ưu hóa trực tiếp cho dấu tách lề tối đa: SVM

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tối đa hóa 𝛾 dưới ràng buộc:

• ||w|| ² = 1
• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 𝛾

𝑤’ = 𝑤/𝛾 thì max 𝛾 tương đương. để giảm thiểu ||𝑤’||² (vì ||𝑤’||² = 1/𝛾²).

Vì vậy, chia cả hai vế cho 𝛾 và viết dưới dạng w’ ta được:

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Cực tiểu hóa ||𝑤′|| ² theo ràng buộc:

• Với mọi i, 𝑦_𝑖𝑤′ ⋅ 𝑥_𝑖 ≥ 1

Máy vectơ hỗ trợ (SVM)

Tối ưu hóa trực tiếp cho dấu tách lề tối đa: SVM

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

argmin_w ||𝑤|| ² s.t.:

• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 1

Đây là bài toán tối ưu có ràng buộc

• Mục tiêu là lồi (bậc hai)
• Tất cả các ràng buộc là tuyến tính
• Có thể giải quyết hiệu quả (trong thời gian đa thức) bằng cách sử dụng phần mềm quy hoạch toàn phương tiêu chuẩn (QP)

Máy vectơ hỗ trợ (SVM)

Câu hỏi: nếu dữ liệu không thể phân tách tuyến tính một cách hoàn hảo thì sao?

Vấn đề 1: hiện có hai mục tiêu

• tối đa hóa lề
• giảm thiểu # phân loại sai.

Trả lời 1: Hãy tối ưu hóa tổng của chúng: giảm thiểu ||𝑤|| ² + 𝐶(# phân loại sai)

trong đó 𝐶 là một số hằng số đánh đổi.

Vấn đề 2: Đây là vấn đề khó tính toán (NP-hard).

[ngay cả khi không quan tâm đến lề và giảm thiểu # sai lầm]

NP-hard [Guruswami-Raghavendra’06]

Máy vectơ hỗ trợ (SVM)

Câu hỏi: nếu dữ liệu không thể phân tách tuyến tính một cách hoàn hảo thì sao?

Thay “#sai lầm” bằng cận trên gọi là “hàm mất bản lề”

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Cực tiểu hóa ||𝑤′|| ² với điều kiện:

• Với mọi i, 𝑦_𝑖𝑤′ ⋅ 𝑥_𝑖 ≥ 1

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tìm argmin_{w,𝜉1,…,𝜉𝑚} ||𝑤|| ² + 𝐶 ∑_𝑖 𝜉_𝑖 s.t.:

• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 1 − 𝜉_𝑖 𝜉_𝑖 ≥ 0

𝜉_𝑖 là “biến bù”

Máy vectơ hỗ trợ (SVM)

Câu hỏi: nếu dữ liệu không thể phân tách tuyến tính một cách hoàn hảo thì sao?

Thay “#sai lầm” bằng cận trên gọi là “hàm mất bản lề”

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tìm argmin_{w,𝜉1,…,𝜉𝑚} ||𝑤|| ² + 𝐶 ∑_𝑖 𝜉_𝑖 s.t.:

• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 1 − 𝜉_𝑖 𝜉_𝑖 ≥ 0

𝜉_𝑖 là “biến bù”

C kiểm soát trọng số tương đối giữa hai mục tiêu là làm cho ||𝑤|| ² nhỏ (lề lớn) và đảm bảo rằng hầu hết các mẫu đều có biên hàm ≥ 1.

Support Vector Machines (SVM)

Câu hỏi: nếu dữ liệu không thể phân tách tuyến tính một cách hoàn hảo thì sao?

Thay “# lỗi” bằng cận trên gọi là “hàm mất bản lề”

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tìm argmin_{w,𝜉1,…,𝜉𝑚} ||𝑤|| ² + 𝐶 ∑_𝑖 𝜉_𝑖 s.t.:

• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 1 − 𝜉_𝑖 𝜉_𝑖 ≥ 0

Thay số lỗi bằng hàm mất bản lề

||𝑤|| ² + 𝐶(# phân loại sai)

Máy vectơ hỗ trợ (SVM)

Câu hỏi: nếu dữ liệu không thể phân tách tuyến tính hoàn toàn thì sao?

Thay “# lỗi” bằng cận trên gọi là “hàm mất bản lề”

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tìm argmin_{w,𝜉1,…,𝜉𝑚} ||𝑤|| ² + 𝐶 ∑_𝑖 𝜉_𝑖 s.t.:

• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 1 − 𝜉_𝑖 𝜉_𝑖 ≥ 0

Tổng số lượng phải di chuyển các điểm để đưa chúng về đúng phía của các đường 𝑤 ⋅ 𝑥 = +1/−1, trong đó khoảng cách giữa các đường 𝑤 ⋅ 𝑥 = 0 và 𝑤 ⋅ 𝑥 = 1 được tính là “1 đơn vị”.

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

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

Triết lý SVM: “Sử dụng hàm nhân”

Máy vectơ hỗ trợ (SVM)

Đầu vào: S={(x₁, 𝑦₁), …,(x_m, 𝑦_m)};

Tìm argmin_{w,𝜉1,…,𝜉𝑚} ||𝑤|| ² + 𝐶 ∑_𝑖 𝜉_𝑖 s.t.:

• Với mọi i, 𝑦_𝑖𝑤 ⋅ 𝑥_𝑖 ≥ 1 − 𝜉_𝑖 𝜉_𝑖 ≥ 0

Dạng nguyên hàm

Tương đương với:

Đầu vào: S={(x₁, y₁), …,(x_m, y_m)};

Tìm argmin_α ¹⁄₂ ∑_i∑_j y_iy_j α_iα_jx_i ⋅ x_j − ∑_i α_i s.t.:

• Với mọi i, 0 ≤ α_i ≤ C_i

∑_i y_iα_i = 0

Lagrangian Dual

SVM (Lagrangian Dual)

Đầu vào: S={(x₁, y₁), …,(x_m, y_m)};

Tìm argmin_α ¹⁄₂ ∑_i∑_j y_iy_j α_iα_jx_i ⋅ x_j − ∑_i α_i s.t.:

• Với mọi i, 0 ≤ α_i ≤ C_i

∑_i y_iα_i = 0

• Bộ phân loại cuối cùng là: w = ∑_i α_iy_ix_i
• Các điểm x_i mà α_i ≠ 0 được gọi là “vectơ hỗ trợ”

Kernelizing Dual SVM

Dữ liệu vào: S={(x₁, y₁), …,(x_m, y_m)};

Tìm argmin_α ¹⁄₂ ∑_i∑_j y_iy_j α_iα_jx_i ⋅ x_j − ∑_i α_i s.t.:

• Với mọi i, 0 ≤ α_i ≤ C_i

∑_i y_iα_i = 0

Thay x_i ⋅ x_j bằng K(x_i, x_j).

• Bộ phân loại cuối cùng là: w = ∑_i α_iy_ix_i
• Các điểm x_i mà α_i ≠ 0 được gọi là “vectơ hỗ trợ”
• Với kernel, phân loại x bằng cách sử dụng ∑_i α_iy_iK(x, x_i)

Máy Vectơ hỗ trợ (SVM).

Một trong những thuật toán phân loại có động lực tốt nhất về mặt lý thuyết và thực tế hiệu quả nhất trong học máy.

Được thúc đẩy trực tiếp bởi Margins và Kernels!

Những điều bạn nên biết

• Tầm quan trọng của lề trong học máy.
• Dạng nguyên sơ của bài toán tối ưu SVM
• Dạng đối ngẫu của bài toán tối ưu SVM.
• Nhân hóa SVM.
• Nghĩ xem nó liên quan như thế nào đến Hồi quy Logistic Chính quy.

Học máy được giám sát (một phần) hiện đại

• Sử dụng dữ liệu chưa được gắn nhãn và tương tác để học

Mô hình cổ điển Ngày nay không đủ

Các ứng dụng hiện đại: số lượng lớn dữ liệu thô.

Chỉ một phần rất nhỏ có thể được chú thích bởi các chuyên gia con người.

Trình tự protein

Hàng tỷ trang web

Hình ảnh

Học bán giám sát

Chuyên gia Dán nhãn

Dữ liệu thô

Dữ liệu được gắn nhãn

Bộ phân loại

Học tập tích cực

chuyên gia dán nhãn

Dữ liệu thô

Bộ phân loại

Học bán giám sát

Mô hình nổi bật trong 15 năm qua trong Học máy.

• Hầu hết các ứng dụng có nhiều dữ liệu không được gắn nhãn, nhưng dữ liệu được gắn nhãn rất hiếm hoặc đắt tiền:
  • Phân loại trang web, tài liệu
  • Thị giác máy tính
  • Sinh học tính toán,
  • ….

Học bán giám sát

Thuật toán học tập

Chuyên gia / Oracle

Nguồn dữ liệu

Các mẫu không được gắn nhãn

Thuật toán đưa ra một bộ phân loại

Các mẫu không được gắn nhãn

Các mẫu được gắn nhãn

S_l={(x₁, y₁), …,(x_ml , y_ml)}

x_i rút ra i.i.d từ D, y_i = c^∗ (x_i)

S_u={x₁, …,x_mu} i.i.d được rút ra từ D

Mục tiêu: h có lỗi nhỏ hơn D.

err_D (h) = Pr_{x~ D} (h(x) ≠ c^∗(x))

Học bán giám sát:

không truy vấn. Chỉ cần có nhiều dữ liệu bổ sung chưa được gắn nhãn.

Một chút bối rối vì không rõ dữ liệu chưa được gắn nhãn có thể làm gì cho bạn….

Key Insight

Dữ liệu chưa được gán nhãn hữu ích nếu chúng ta có niềm tin không chỉ về hình thức của mục tiêu, mà còn về mối quan hệ của nó với phân phối cơ bản.

Kết hợp dữ liệu được gắn nhãn và không được gắn nhãn

• Một số phương pháp đã được phát triển để cố gắng sử dụng dữ liệu không được gắn nhãn để cải thiện hiệu suất, ví dụ:

– SVM truyền dẫn [Joachims ’99]

– Đồng đào tạo [Blum & Mitchell ’98]

– Các phương pháp dựa trên đồ thị [B&C01], [ZGL03]

Kiểm tra thời gian trao thưởng tại ICML!

Hội thảo [ICML ’03, ICML’ 05, …]

Sách:

• Học bán giám sát, MIT 2006 O. Chapelle, B. Scholkopf và A. Zien (eds)
• Giới thiệu về học bán giám sát, Morgan & Claypool, 2009 Zhu & Goldberg

Ví dụ về giả định “điển hình”: Lề

• Dải phân cách đi qua các vùng có mật độ thấp của không gian/lề lớn.

– giả sử chúng ta đang tìm kiếm dấu phân cách tuyến tính

– niềm tin: nên tồn tại một dấu phân cách lớn

Chỉ dữ liệu được dán nhãn

SVM truyền dẫn

Máy Vectơ hỗ trợ truyền dẫn

Tối ưu hóa cho dấu phân cách với dữ liệu được gắn nhãn và không được gắn nhãn có lề lớn. [Joachims ‘99]

Đầu vào: S_l={(x₁, y₁), …,(x_ml , y_ml)}

S_u={x₁, …,x_mu}

argmin_w ||w|| ² s.t.:

• y_i w ⋅ x_i ≥ 1, với mọi i ∈ {1, … ,m_l}
• y^{^}_u w ⋅ x_u ≥ 1, với mọi u ∈ {1,… ,m_u}
• y^{^}_u ∈ {−1, 1} với mọi u ∈ {1,… ,m_u}

Tìm nhãn của mẫu không nhãn và 𝑤 s.t. 𝑤 phân tách cả mẫu có nhãn và không nhãn dữ liệu với lề tối đa.

Máy vectơ hỗ trợ truyền dẫn

Tối ưu hóa cho dấu phân cách với dữ liệu được gắn nhãn và không được gắn nhãn có lề lớn. [Joachims ’99]

Đầu vào: S_l={(x₁, y₁), …,(x_ml , y_ml)}

S_u={x₁, …,x_mu}

argmin_w ||w|| ² + 𝐶 ∑_𝑖 𝜉_𝑖 + 𝐶 ∑_𝑢 𝜉^{^}_𝑢

• y_i w ⋅ x_i ≥ 1-𝜉_𝑖, với mọi i ∈ {1, … ,m_l}
• y^{^}_i w ⋅ x_u ≥ 1 − 𝜉^⌃_𝑢, với mọi u ∈ {1,… ,m_u}
• y^{^}_u ∈ {−1, 1} với mọi u ∈ {1,… ,m_u}

Tìm nhãn của mẫu không nhãn và 𝑤 s.t. 𝑤 phân tách cả mẫu có nhãn và không nhãn dữ liệu với lề tối đa.

Máy vectơ hỗ trợ truyền dẫn

Tối ưu hóa cho bộ phân tách với dữ liệu được gắn nhãn và không được gắn nhãn có lề lớn.

Đầu vào: S_l={(x₁, y₁), …,(x_ml , y_ml)}

S_u={x₁, …,x_mu}

argmin_w ||w|| ² + 𝐶 ∑_𝑖 𝜉_𝑖 + 𝐶 ∑_𝑢 𝜉^{^}_𝑢

• y_i w ⋅ x_i ≥ 1-𝜉_𝑖, với mọi i ∈ {1, … ,m_l}
• y^{^}_i w ⋅ x_u ≥ 1 − 𝜉^⌃_𝑢, với mọi u ∈ {1,… ,m_u}
• y^{^}_u ∈ {−1, 1} với mọi u ∈ {1,… ,m_u}

NP-hard…. .Chỉ lồi sau khi bạn đoán các nhãn… có thể đoán quá nhiều…

Máy vectơ hỗ trợ truyền dẫn

Tối ưu hóa cho bộ phân tách với dữ liệu được gắn nhãn và không được gắn nhãn có lề lớn.

Ý tưởng cấp cao Heuristic (Joachims):

• Đầu tiên tối đa hóa lề trên các điểm được gắn nhãn
• Sử dụng điều này để gán nhãn ban đầu cho các điểm chưa được gắn nhãn dựa trên dấu tách này.
• Hãy thử lật nhãn của các điểm chưa được gắn nhãn để xem liệu làm như vậy có thể tăng lề hay không

Tiếp tục cho đến khi không còn cải tiến nào nữa. Tìm một giải pháp tối ưu cục bộ.

Thử nghiệm [Joachims99]

Máy vectơ hỗ trợ truyền dẫn

Phân phối hữu ích

Phân phối không hữu ích

Tương thích cao

¹⁄_𝛾² cụm, tất cả các phân vùng có thể phân tách bằng lề lớn

Học bán giám sát

Mô hình nổi bật trong 15 năm qua về Học máy.

Thông tin chi tiết chính

Dữ liệu chưa được gắn nhãn hữu ích nếu chúng ta có niềm tin không chỉ về hình thức của mục tiêu mà còn về mối quan hệ của nó với phân phối cơ bản.

Các kỹ thuật nổi bật

– SVM truyền dẫn [Joachims ’99]

– Đồng đào tạo [Blum & Mitchell ’98]

– Các phương pháp dựa trên đồ thị [B&C01], [ZGL03]