PCA, Kernel PCA, ICA – Học biểu diễn – Giảm số chiều

Dữ liệu lớn & dữ liệu có chiều cao

• Số chiều cao = Nhiều tính năng

Phân loại tài liệu

Các tính năng trên mỗi tài liệu = hàng nghìn từ/unigram hàng triệu bigram, thông tin theo ngữ cảnh

Khảo sát – Netflix

480189 người dùng x 17770 phim

Dữ liệu lớn và có chiều cao

• Dữ liệu có chiều cao = Nhiều tính năng

MEG Brain Imaging

120 vị trí x 500 điểm thời gian x 20 đối tượng

Hoặc bất kỳ dữ liệu hình ảnh có chiều cao nào

Dữ liệu lớn và có chiều cao

• Hữu ích để học các biểu diễn chiều thấp hơn của dữ liệu.

Học biểu diễn

PCA, Kernel PCA, ICA: Các kỹ thuật học tập không giám sát mạnh mẽ để trích xuất cấu trúc ẩn (có khả năng là chiều thấp hơn) từ bộ dữ liệu chiều cao.

Hữu ích cho:

• Trực quan hóa
• Sử dụng tài nguyên hiệu quả hơn (ví dụ: thời gian, bộ nhớ, giao tiếp)
• Thống kê: ít thứ nguyên hơn → tổng quát hóa tốt hơn
• Loại bỏ nhiễu (cải thiện chất lượng dữ liệu)
• Xử lý thêm bằng thuật toán học máy

Phân tích thành phần chính (PCA)

PCA là gì: Kỹ thuật giải nén không giám sát cấu trúc phương sai từ bộ dữ liệu chiều cao.

• PCA là một phép chiếu trực giao hoặc chuyển đổi dữ liệu thành một không gian con (có thể là chiều thấp hơn) sao cho phương sai của dữ liệu được chiếu là tối đa.

Phân tích thành phần chính (PCA)

Câu hỏi: Chúng ta có thể chuyển đổi các tính năng để chỉ cần giữ lại một tính năng tiềm ẩn không?

Phân tích thành phần chính (PCA)

Trong trường hợp dữ liệu nằm trên hoặc gần tuyến tính d-chiều thấp không gian con, các trục của không gian con này là một biểu diễn hiệu quả của dữ liệu.

Việc xác định các trục được gọi là Phân tích thành phần chính và có thể thu được bằng cách sử dụng các công cụ tính toán ma trận cổ điển (Phân tích giá trị riêng hoặc số ít).

Phân tích thành phần chính (PCA)

Thành phần chính (PC) là các hướng trực giao thu được hầu hết sự khác biệt trong dữ liệu.

• PC đầu tiên – hướng dữ liệu thay đổi nhiều nhất.
• Phép chiếu các điểm dữ liệu dọc theo PC đầu tiên phân biệt dữ liệu nhiều nhất dọc theo bất kỳ hướng nào (điểm trải rộng nhất khi chúng ta chiếu dữ liệu theo hướng đó so với bất kỳ hướng nào khác).

Nhắc nhanh:

||v||=1, Điểm x_i (Vectơ chiều D)

Hình chiếu của x_i lên v là v ⋅ x_i

Phân tích thành phần chính (PCA)

Thành phần chính (PC) là các hướng trực giao nắm bắt hầu hết sự khác biệt trong dữ liệu.

• PC thứ nhất – hướng dữ liệu thay đổi nhiều nhất.
• PC thứ 2 – Hướng trực giao tiếp theo (không tương quan) có độ biến thiên lớn nhất (loại bỏ tất cả độ biến thiên theo hướng đầu tiên, sau đó tìm hướng tiếp theo có độ biến thiên lớn nhất)
• Và cứ tiếp tục như vậy …

Phân tích thành phần chính (PCA)

Đặt v₁, v₂, …, v_d biểu thị d thành phần chính.

vi ⋅ vj = 0, i ≠ j và vi ⋅ vi = 1, i = j

Giả sử dữ liệu được căn giữa (chúng ta đã trích xuất giá trị trung bình của mẫu).

Đặt X = [x₁, x₂, … , x_n] (các cột là các điểm dữ liệu)

Tìm vectơ tối đa hóa phương sai mẫu của dữ liệu dự kiến

Đưa các ràng buộc vào hàm mục tiêu

Phân tích thành phần chính (PCA)

(X X^T) v = λv , vì vậy v (PC đầu tiên) là vectơ riêng của ma trận tương quan/hiệp phương sai mẫu 𝑋 𝑋^𝑇

Phương sai mẫu của phép chiếu v^𝑇𝑋 𝑋^𝑇v = 𝜆v^𝑇v = 𝜆

Do đó, giá trị riêng 𝜆 biểu thị lượng biến thiên bị bắt dọc theo chiều đó (còn gọi là lượng năng lượng dọc theo chiều đó).

Giá trị riêng 𝜆₁ ≥ 𝜆₂ ≥ 𝜆₃ ≥ ⋯

• PC thứ nhất 𝑣₁ là vector riêng của ma trận hiệp phương sai mẫu 𝑋 𝑋^𝑇 liên kết với giá trị riêng lớn nhất
• PC thứ 2 𝑣₂ là vectơ riêng của ma trận hiệp phương sai mẫu 𝑋 𝑋^𝑇 gắn với giá trị riêng lớn thứ hai
• Và cứ thế …

Phân tích thành phần chính (PCA)

• Như vậy, các trục mới là vector riêng của ma trận tương quan mẫu 𝑋 𝑋^𝑇 của dữ liệu.
• Các đặc trưng được biến đổi không tương quan với nhau.

• Về mặt hình học: định tâm theo sau là xoay.

– Biến đổi tuyến tính

Tính toán chính: phân tích riêng của 𝑋𝑋^𝑇 (liên quan chặt chẽ đến SVD của 𝑋).

Hai cách giải thích

Cho đến nay: Không gian con phương sai cực đại. PCA tìm các vectơ v sao cho các phép chiếu trên các vectơ thu được phương sai tối đa trong dữ liệu

Quan điểm thay thế: Lỗi tái tạo tối thiểu. PCA tìm các vectơ v sao cho phép chiếu lên các vectơ mang lại khả năng tái tạo MSE tối thiểu

Hai cách diễn giải

Ví dụ: đối với thành phần đầu tiên.

Hướng phương sai tối đa: PC thứ nhất một vectơ v sao cho phép chiếu lên vectơ này thu được phương sai tối đa trong dữ liệu (trong số tất cả các phép chiếu một chiều có thể có)

Lỗi tái tạo tối thiểu: PC thứ nhất một vectơ v sao cho phép chiếu lên vectơ này mang lại MSE tối thiểu xây dựng lại

Tại sao? Định lý Pythagore

Ví dụ: đối với thành phần đầu tiên.

Hướng phương sai tối đa: PC thứ nhất một vectơ v sao cho phép chiếu lên vectơ này thu được phương sai cực đại dữ liệu (trong số tất cả các phép chiếu một chiều có thể)

Lỗi tái tạo tối thiểu: PC thứ nhất một véc tơ v sao cho phép chiếu lên véc tơ này mang lại khả năng tái tạo MSE tối thiểu

blue² + green² = black²

black² là cố định (chỉ là dữ liệu)

Vì vậy, tối đa hóa blue² tương đương với giảm thiểu green²

Giảm số chiều bằng cách sử dụng PCA

Giá trị riêng 𝜆 biểu thị lượng biến thiên thu được dọc theo kích thước đó (hay còn gọi là lượng năng lượng dọc theo kích thước đó).

Giá trị riêng bằng 0 cho thấy không có sự thay đổi dọc theo các hướng đó => dữ liệu nằm chính xác trên một không gian con tuyến tính

Chỉ giữ các phép chiếu dữ liệu lên các thành phần chính có giá trị riêng khác 0, chẳng hạn như v₁, … , v_k, trong đó k=rank(𝑋 𝑋^𝑇)

Giảm số chiều bằng cách sử dụng PCA

Trong các bài toán nhiều chiều, dữ liệu đôi khi nằm gần một không gian con tuyến tính, vì nhiễu gây ra biến thiên nhỏ

Chỉ giữ phép chiếu dữ liệu lên các thành phần chính có giá trị riêng lớn

Có thể bỏ qua các thành phần có ý nghĩa nhỏ hơn.

Có thể mất một số thông tin, nhưng nếu giá trị riêng nhỏ, đừng mất nhiều

Example: faces

Có thể biểu diễn cho một hình ảnh khuôn mặt chỉ bằng 15 số!

• PCA đã được chứng minh là hữu ích trước khi thực hiện phân cụm k-means và cũng hữu ích về mặt kinh nghiệm. Ví dụ,

Thảo luận PCA

Điểm mạnh

Phương pháp vectơ riêng

Không điều chỉnh các tham số

Không tối ưu cục bộ

Điểm yếu

Giới hạn đối với thống kê bậc hai

Giới hạn đối với các phép chiếu tuyến tính

Kernel PCA (Phân tích thành phần chính của hàm nhân)

Hữu ích khi dữ liệu nằm trên hoặc gần một không gian con tuyến tính d- chiều thấp của không gian 𝜙 được liên kết với nhân

Tính chất của PCA

• Cho tập 𝑛 quan sát có tâm 𝑥_𝑖 ∈ 𝑅^𝐷, PC thứ nhất là hướng làm cực đại phương sai

– 𝑋 = (𝑥₁, 𝑥₂, … , 𝑥_𝑛)

– 𝑣₁ = 𝑎𝑟𝑔𝑚𝑎𝑥_||𝑣||=1 ¹⁄_𝑛∑_𝑖 (𝑣^⊤𝑥_𝑖) ²

= 𝑎𝑟𝑔𝑚𝑎𝑥_||𝑣||=1 ¹⁄_𝑛 𝑣^⊤𝑋𝑋^⊤𝑣

• Ma trận hiệp phương sai 𝐶 = ¹⁄_𝑛 𝑋𝑋^⊤
• 𝑣₁ có thể được tìm thấy bằng cách giải bài toán giá trị riêng:

– 𝐶𝑣₁ = 𝜆𝑣₁(tối đa 𝜆)

Các tính chất của PCA

• Cho một tập 𝑛 quan sát có tâm 𝑥_𝑖 ∈ 𝑅^𝐷, PC thứ nhất là hướng mà tối đa hóa phương sai

– 𝑋 = (𝑥₁, 𝑥₂, … , 𝑥_𝑛)

– 𝑣₁ = 𝑎𝑟𝑔𝑚𝑎𝑥_||𝑣||=1 ¹⁄_𝑛∑_𝑖 (𝑣^⊤𝑥_𝑖) ²

= 𝑎𝑟𝑔𝑚𝑎𝑥_||𝑣||=1 ¹⁄_𝑛 𝑣^⊤𝑋𝑋^⊤𝑣

• Ma trận hiệp phương sai 𝐶 = ¹⁄_𝑛 𝑋𝑋^⊤ là một ma trận DxD . Mục nhập (i,j) của 𝑋𝑋^⊤ là tương quan của tọa độ thứ i của các mẫu với tọa độ thứ j của các mẫu
• Để sử dụng hàm nhân, cần sử dụng ma trận tích trong 𝑋^𝑇𝑋.

Biểu thức thay thế cho PCA

• Thành phần chính nằm trong dải dữ liệu

𝑣₁ = ∑_𝑖 𝛼_𝑘𝑥_𝑖 = 𝑋𝛼

Tại sao? PC thứ nhất là hướng có phương sai lớn nhất và đối với bất kỳ hướng nào nằm ngoài khoảng dữ liệu, chỉ nhận được nhiều phương sai hơn nếu chúng ta chiếu hướng đó vào khoảng dữ liệu.

• Thế lại ta có

𝐶𝑣₁ = ¹⁄_𝑛 𝑋𝑋^⊤𝑋𝛼 = 𝜆 𝑋𝛼

• Bây giờ, nhân trái LHS và RHS với 𝑋^𝑇.

¹⁄_𝑛 𝑋^⊤𝑋𝑋^⊤𝑋𝛼 = 𝜆𝑋^⊤𝑋𝛼

Chỉ phụ thuộc vào ma trận tích trong

Kernel PCA

• Ý tưởng chính: Thay thế ma trận tích trong bằng ma trận nhân
  • PCA: ¹⁄_𝑛 𝑋^⊤𝑋𝑋^⊤𝑋𝛼 = 𝜆𝑋^⊤𝑋𝛼
  • Đặt 𝐾 = [𝐾( 𝑥^𝑖 , 𝑥^𝑗 )]_𝑖𝑗 là ma trận của tất cả các tích vô hướng trong không gian 𝜙
  • Hàm nhân PCA: thay thế “𝑋^𝑇𝑋” bằng 𝐾.

¹⁄_𝑛 𝐾𝐾𝛼 = 𝜆𝐾𝛼, hoặc tương đương, ¹⁄_𝑛 𝐾𝛼 = 𝜆 𝛼

• Tính toán then chốt: tạo ma trận nhân 𝑛 theo 𝑛 𝐾, sau đó thực hiện phân tách riêng trên 𝐾.

Ví dụ Kernel PCA

• Gaussian RBF kernel exp( − ^{||𝑥−𝑥′|| 2} ⁄_2𝜎² ) trên không gian 2 chiều
• Vectơ riêng được đánh giá tại một điểm kiểm tra 𝑥 là một hàm

𝑤^⊤𝜙(𝑥) = ∑_𝑖 𝛼_𝑖 < 𝜙(𝑥^𝑖) , 𝜙(𝑥) > = ∑_𝑖 𝛼_𝑖𝑘(𝑥^𝑖 , 𝑥)

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

• Phân tích thành phần chính (PCA)
  • PCA là gì, có ích gì.
  • Cả không gian con phương sai cực đại và quan điểm sai số tái tạo cực tiểu.
• Kernel PCA

Tài liệu bổ sung về tính toán các thành phần chính và ICA

Phương pháp Power để tính toán PC

Cho ma trận 𝑋 ∈ 𝑅^𝐷×𝑛, tính toán vectơ riêng trên cùng của 𝑋 𝑋^𝑇

Khởi tạo với 𝑣^ ∈ 𝑅^𝐷 ngẫu nhiên

Lặp lại

v^ ← X X^Tv^

v^ ← v^ /||v^ ||

Yêu cầu

Với bất kỳ 𝜖 > 0, whp trên lựa chọn của vectơ ban đầu, sau 𝑂( ¹⁄_𝜖 log ^𝑑⁄_𝜖) lặp lại, ta có 𝑣^ ^𝑇𝑋𝑋^𝑇𝑣^ ≥ (1 − 𝜖) 𝜆₁.

Sau đó có thể trừ đi thành phần 𝑣^ của mỗi mẫu và lặp lại để lấy phần tiếp theo.

Phân tích riêng

Bất kỳ ma trận đối xứng nào 𝐴 = 𝑋𝑋^𝑇 đều được đảm bảo có phân tích riêng với các giá trị riêng thực: 𝐴 = 𝑉 Λ 𝑉^𝑇 .

Ma trận Λ chéo với các giá trị riêng 𝜆1 ≥ 𝜆2 ≥ ⋯ trên đường chéo. Ma trận V có các vectơ riêng là các cột.

Phân tích giá trị kỳ dị (SVD)

Eigendecomp của 𝑋𝑋^𝑇 có liên quan chặt chẽ với SVD của 𝑋.

Cho một ma trận 𝑋 ∈ 𝑅^𝐷×𝑛, SVD là một phân tích: 𝑋^𝑇 = 𝑈𝑆𝑉^𝑇

• 𝑆 là ma trận đường chéo với các giá trị kỳ dị 𝜎₁, … , 𝜎_𝑑 của 𝑋.
• Các cột của 𝑈, 𝑉 trực giao, đơn vị độ dài.
• Vậy, 𝑋𝑋^𝑇 = 𝑉𝑆𝑈^𝑇𝑈𝑆𝑉^𝑇 = 𝑉𝑆²𝑉^𝑇 = phân tích riêng của 𝑋𝑋^𝑇.

Vì vậy, 𝜆_𝑖 = 𝜎_𝑖 ² và có thể đọc đáp án từ SVD.

Phân tách giá trị số ít (SVD)

Eigendecomp của 𝑋𝑋^𝑇 có liên quan chặt chẽ với SVD của 𝑋.

Cho một ma trận 𝑋 ∈ 𝑅^𝐷×𝑛, SVD là một phân tích: 𝑋^𝑇 = 𝑈𝑆𝑉^𝑇

• Thực tế, có thể xem các hàng của 𝑈𝑆 là tọa độ của từng mẫu dọc theo các trục được cho bởi 𝑑 vectơ riêng.

Vì vậy, 𝜆_𝑖 = 𝜎_𝑖 ² và có thể đọc được nghiệm từ SVD.

Phân tích thành phần độc lập (ICA)

Tìm phép biến đổi tuyến tính

𝒙 = 𝑉 ∙ 𝒔

mà các hệ số 𝒔 = (𝑠₁, 𝑠₂, … , 𝑠_𝐷) ^𝑇 là độc lập thống kê

𝑝 (𝑠₁, 𝑠₂, … , 𝑠_𝐷) = 𝑝₁(𝑠₁) 𝑝₂(𝑠₂) …𝑝_𝑛(𝑠_𝐷)

Về mặt thuật toán, chúng ta cần xác định ma trận V và các hệ số s, s.t. với điều kiện 𝒙 = 𝑉^𝑇 ∙ 𝒔 thông tin lẫn nhau giữa 𝑠₁, 𝑠₂, … , 𝑠_𝐷 là cực tiểu:

𝐼 (𝑠₁, 𝑠₂, … , 𝑠_𝐷) = ∑_𝑖=1^𝐷 𝐻 (𝑠_𝑖) − 𝐻 (𝑠₁, 𝑠₂, … , 𝑠_𝐷)

PCA tìm hướng biến thiên lớn nhất,

ICA sẽ tìm hướng “phù hợp” nhất với dữ liệu.