PCA – Intuition and Maths

Trong bài trước, ta đã trình bày các bước của thuật toán  PCA, nhưng phần giải thích và các công thức chi tiết chưa được làm rõ. Bài này giải thích một cách nôm na ý tưởng chính của PCA, đồng thời chứng minh rằng ý tưởng này dẫn đến việc sử dụng trị riêng trong PCA, lí giải tại sao trong PCA, trị riêng lại đóng vai trò đẹp đẽ đến như thế.

1. Ý tưởng chính của PCA

Như đã nói trong bài trước, mục tiêu của  PCA là tìm trục cho không gian mới sao cho nó biểu diễn tốt nhất mức độ biến thiên của dữ liệu.

Giả sử có ma trận \mathbf{X}\in\mathbb{R}^{m\times n}

{\displaystyle \mathbf{X}=\left[x_1\vert x_2\vert \cdots \vert x_i\vert \cdots\vert x_n\right]}

Trong đó x_i \in \mathbb{R}^m là các điểm trong không gian ban đầu. Nhiệm vụ của PCA là đi tìm không gian mới với số chiều nhỏ hơn m, sao cho biểu diễn tốt n điểm trong X.

Hình sau minh họa trọn vẹn ý tưởng của PCA.

Minh họa ý tưởng của PCA

Trong hình trên, gọi  \alpha \in \mathbb{R}^m,\;\parallel \alpha\parallel=1 là một trục trong không gian mới cần tìm. Khi đó tọa độ của x_i trên trục \alpha chính là tích vô hướng \varphi_i = \alpha^\top x_i (xem thêm ý nghĩa hình học của tích vô hướng).

Mục tiêu của PCA là tìm \alpha sao cho nó biểu diễn x_i tốt nhất, nghĩa là sao cho \varphi_i lớn nhất. Hơn nữa, điều này còn phải đúng cho tất cả n điểm trong X, nên mục tiêu của PCA là tìm \alpha sao cho tất cả các \varphi_i = \alpha^\top x_i, \;i = 1\cdots n là cực đại. Rõ ràng khi \varphi_i cực đại thì trục \alpha biểu diễn tốt nhất tất cả các vector cột trong X.

Nói cách khác, mục tiêu của PCA là cực đại tổng \sum_{i=1}^n \varphi_i^2. Mà:

{\displaystyle \sum_{i=1}^n \varphi_i^2 = \sum_{i=1}^n \left(\alpha^\top x_i\right)\left(x_i^\top\alpha\right) = \sum_{i=1}^n \alpha^\top \left[x_i x_i^\top\right]\alpha = \alpha^\top XX^\top\alpha}

nên mục tiêu của PCA là:

{\displaystyle \max_{\alpha\in\mathbb{R}^m,\;\parallel \alpha\parallel = 1} \alpha^\top XX^\top\alpha}    (1)

Vậy vấn đề còn lại là làm thế nào để giải bài toán tối ưu này.

Ta nhận xét rằng XX^\top\in\mathbb{R}^{n\times n} là ma trận đối xứng và positive semidefinite nên tất cả các trị riêng của  XX^\top đều không âm:

\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_p \geq 0

và các vector riêng tương ứng là:

u_1, u_2,\cdots u_p

Gọi \lambda_1 là trị riêng lớn nhất của XX^\top, khi đó người ta chứng minh được \alpha làm cực đại (1) chính là vector riêng tương ứng với \lambda_1.

Như vậy chỉ bằng cách tính XX^\top ta sẽ tính được các trị riêng và các vector riêng. Các vector riêng còn được gọi là principal axis, do đó phương pháp này mới gọi là principal component analysis. Việc còn lại là chọn k vector riêng ứng với k trị riêng lớn nhất, sau đó thực hiện phép nhân Xu_1, Xu_2,\cdots , Xu_k để tính tọa độ của  X trong không gian k chiều mới, như đã trình bày trong bài trước.

Như vậy ta đã thực hiện xong PCA trên không gian \mathbb{R}^m tạo bởi các cột của  X. Bằng cách chuyển vị X^\top và thực hiện các phép phân tích như trên, ta cũng được kết quả tương tự cho không gian \mathbb{R}^n, nhưng khi đó các trị riêng cần tìm là trị riêng của X^\top X. Một điểm đẹp mắt là các trị riêng của  X^\top X cũng chính là trị riêng của  XX^\top, do đó bằng một phép phân tích trị riêng, ta có thể thực hiện PCA trên cả 2 chiều của X. Trong ML nói chung việc này không thú vị lắm, nhưng trong ngành thống kê thì kĩ thuật này rất hay được sử dụng.

2. Kết luận

Bài này kết nối giữa motivation và thuật toán PCA. Từ motivation, ta đi đến việc mô hình hóa PCA bằng bài toán tối ưu, và thay vì giải bài toán tối ưu này một cách võ biền, ta có cách giải đẹp hơn rất nhiều, dựa vào nhận xét về trị riêng.

Thực chất trong PCA, có thể chứng minh rằng trị riêng của XX^\top chính là “lượng thông tin” có thể phân bố được trên các trục u_1,\cdots ,u_p (gọi là inertia), theo đó để chọn k thích hợp, ta chọn sao cho

{\displaystyle \frac{\sum_{i=1}^k\lambda_i}{\sum_{i=1}^p\lambda_i}\geq 90\%}

nghĩa là chọn k trị riêng lớn nhất sao cho tổng của chúng lớn hơn 90% tổng của tất cả các trị riêng. Tổng của tất cả các trị riêng chính là tất cả lượng thông tin ta có thể phân bố, do đó heuristic này muốn chọn k sao cho nó biêảu diễn được ít nhất 90% lượng thông tin ban đầu.

Để ngắn gọn, tôi không trình bày về inertia, định lí  Huyghen v.v… nhưng tài liệu về những khái niệm này, và kể cả PCA, có thể tìm được dễ dàng.

Advertisements

23 comments

  1. Hi em,
    1. Ma trận X\in\mathbb{C}^{m\times m} gọi là positive semidefinite nếu với mọi vector \alpha\in\mathbb{C}^m thì \alpha^* X \alpha \geq 0.
    2. Đúng và không đúng. Đúng vì ma trận nxn bất kì có n trị riêng nếu tính cả trị riêng bội và các trị riêng phức nếu có. Không đúng vì nếu chỉ đếm các trị riêng phân biệt thì số trị riêng của ma trận nxn là nhỏ hơn hay bằng n.
    Trong trường hợp này, do XX^\top là positive semidefinite nên các trị riêng đều không âm, nhưng không chắc là nó có n trị riêng phân biệt. Ví dụ ma trận [1 0; 0 1] là +semidefinite nhưng có trị riêng bội 2 \lambda_1 = \lambda_2 = 1.

  2. Em nghe thầy giảng là nếu trong trường hợp số chiều n của X quá lớn, mình ko nên nên suy ra từ X.X^T mà nên tìm eigenvalue và eigenvector F’ của X^T.X rồi từ đó mới suy ra eigenvector F của X.X^T (F=X.F’). Anh có thể giải thích giúp em chỗ này được ko ?

    Em đọc ở PCA (giảm chiều từ X->Y)ở link này http://models.life.ku.dk/~movies/PCA_story/ thấy có khái niệm là score và loading, theo em hiểu thì Y là score, ko biết loading là gì ?

    Em cảm ơn anh 🙂

  3. 1/ Tùy ở cách định nghĩa của X. Thông thường trong hầu hết ứng dụng, ma trận X\in\mathbb{R}^{n\times m} biểu diễn n observation (dân thống kê gọi là individual, dân ML gọi là sample) trên m feature. Em có thể đọc thêm ở đây: https://phvuresearch.wordpress.com/2011/09/21/multivariate_data_analysis_intro/

    Anh không biết em đang nói trong ngữ cảnh nào nên cứ giả sử là ứng dụng PCA trong KHMT. Khi đó thông thường n >> m (số sample rất lớn so với số feature). Mà XX^\top \in \mathbb{R}^{n\times n}, còn X^\top X \in \mathbb{R}^{m\times m}. Do đó tìm trị riêng của XX^\top phức tạp hơn so với trị riêng của X^\top X.

    Tuy nhiên ý tưởng sâu xa hơn của PCA không dừng lại ở đó. Trong thống kê, khi phân tích PCA sử dụng XX^\top là ta tìm không gian mới hình thành từ không gian các feature cũ để biểu diễn các observation, còn dùng X^\top X là tìm không gian mới hình thành từ không gian các observation cũ để biểu diễn các feature.

    2/ loading là ma trận các eigenvector.

  4. Trong trường hợp anh nói thì n là dòng, m là cột đúng ko anh ? Nếu mình sắp n là cột, m là dòng thì sẽ ngược lại ?

    Nếu số feature nhiều hơn số sample thì sao ? Ý em hỏi là từ vector riêng của của X^T.X => vector riêng của X.X^T mình phải hiểu như thế nào

    Cảm ơn anh.

  5. Anh Vu ơi cho em hỏi chỗ công thức :
    (α^T)Xi = (Xi^T)α ???
    Vì ở trên anh có ghi φi^2 = (α^T)Xi (Xi^T)α
    Anh giải thích chỗ đó vì sao lại bằng nhau vậy anh . Cảm ơn anh

  6. @Phạm Đăng Khoa: ” Ý em hỏi là từ vector riêng của của X^T.X => vector riêng của X.X^T mình phải hiểu như thế nào”

    Với (\lambda, v) là trị riêng và vector riêng của X^TX ta sẽ kiểm tra một cách trực tiếp, có được v' = \frac{1}{\sqrt{\lambda}} X v.. Thay trực tiếp vào, ta có XX^tv = \lambda \frac{Xv}{\sqrt{\lambda}} =\lambda v'.

    Mình cũng đang làm lại cái này nhưng có vẻ không tài nào áp dụng d9u77oc5 vào bài toán mình đang quan tâm.

  7. hi anh,
    Anh cho em hỏi, trong phần đầu anh nói là tìm alpha sao cho x(i) biểu diễn tốt nhất, nghĩa là dẫn đến hình chiếu (phi) là lớn nhất. Em thấy cách giải thích này không ổn lắm. Vì khi giá trị hình chiếu (phi) lớn nhất thì chỉ đảm bảo là các điểm này khi chiếu xuống sẽ cách xa gốc tọa độ, chứ không đảm bảo là các điểm được phân tách tốt nhất. Mà theo em hiểu, thì một không gian biểu diễn dữ liêu tốt nhất phải là một không gian mà các điểm khác nhau thì tách xa nhau. Hy vọng anh reply và chém qua lại chút đê hiểu rõ hơn về thằng cu PCA này ah 🙂 Thanks anh.

    1. Hi em,

      Sorry em vì hình minh hoạ làm em hiểu nhầm.
      Do \varphi là tích vô hướng của \alphax_i nên \varphi là độ dài hình chiếu của vector x_i lên trục \alpha, chứ không phải là khoảng cách từ điểm x_i đến gốc toạ độ như em nói.
      Trong hình minh hoạ, O là gốc của hệ tọa độ ban đầu. Gốc của hệ tọa độ mới không nhất thiết trùng với O. Nếu em vẽ lại hình đó, nhưng trục tạo bởi \alpha không đi qua O, mà dịch xuống 1 khoảng nhỏ, thì ý nghĩa minh họa vẫn không thay đổi, và em sẽ không hiểu nhầm như vậy nữa.

  8. Hi anh,
    Anh có chắc là gốc tọa độ mới của không gian mới không trùng với gốc tọa độ ban đầu không ah?
    (Sr pak, nếu bác không phiền thì cho em email, anh em mình trao đổi chút được không ah? Em ko muốn post quá nhiều lên trên này sợ làm anh em rối rắm.Với lại em toàn hỏi ngu :), post lên mang tiếng chết :). Mail của em thì như thông tin trên post này chắc pak đã biết. Email là facebook141.nguyen@gmail.com. Em muốn hiểu bản chất của thằng này một chút ah :). Chắc tại đầu em hơi abc nên có khá nhiều vấn đề chưa thông, mong dc bác chỉ bảo ah :))

    1. Tuỳ em gọi “không gian cũ” là không gian nào.

      Lưu ý rằng bước đầu tiên của PCA là chuẩn hoá dữ liệu sao cho các feature đều có mean là 0 và standard deviation là 1. Xét về hình học, đây thực chất là một phép chuyển các điểm trong X từ không gian ban đầu (K0) về một không gian mới (K1) mà trong đó các điểm được phân bố “tối ưu” nhất trên các trục. Ở đây “tối ưu” có nghĩa là xét 1 dimension bất kì, các điểm đều phân bố xung quanh gốc tọa độ (mean = 0) với standard deviation = 1. Như vậy gốc của K1 có thể không trùng với gốc của K0.
      Sau đó, thuật toán PCA tìm cách tạo một không gian mới K2, mà gốc của K2 trùng với gốc của K1, nhưng phương của các trục được chọn sao cho variance trên các dimension là lớn nhất có thể. Lưu ý là các dimension bị ràng buộc với nhau bởi các điểm trong X, nên không thể kéo hết tất cả các điểm trên các dimension ra vô cực được.

      Nếu không có bước chuẩn hoá thì gốc của K2 trùng với K0. PCA khi đó thực chất chỉ là một phép tối ưu để “quay” hệ trục toạ độ cũ thành hệ trục tọa độ mới sao cho variance trên các trục là cực đại.

      Hình vẽ đúng nhưng comment trước của anh là sai.

  9. Trong Matlab,

    Cho em hỏi làm thế nào để chọn k trị riêng lớn nhất sao cho tổng của chúng lớn hơn 90% tổng của tất cả các trị riêng

    khi mà các trị riêng chứa giá trị âm, Nếu cộng tất cả các trị riêng với trị tuyệt đối của giá trị âm nhỏ nhất.Em nghĩ không vấn đề ?

    Nhưng em gặp trường hợp trị riêng là số phức vậy làm sao để sort các trị riêng. Kết quả có còn đúng hay sai thuật toán ở đây

    VD :

    K>> eig(rand(7))

    ans =

    3.9488 + 0.0000i
    -0.1658 + 0.9695i
    -0.1658 – 0.9695i
    -0.6231 + 0.0000i
    0.5358 + 0.1245i
    0.5358 – 0.1245i
    0.2322 + 0.0000i

    1. Về trường hợp trị riêng là số phức , có thể áp dụng thế này được không ạ

      for i=n:-1:1
      if(V(i)>0)
      V(i) = abs(V(i));
      else
      V(i) = -abs(V(i));
      end
      end

      Cảm ơn về bài viết

  10. Nếu lamda là

    262772.254974822
    214434.462653869
    200464.540997182
    135227.822750248
    59677.9234605614
    4.50894768873831e-09
    3.80245432957533e-09
    3.32405676173579e-09
    3.32405676173579e-09
    2.94514909401158e-09
    2.94514909401158e-09
    2.70936343362458e-09
    2.47392648621396e-09
    2.47392648621396e-09
    2.36697695712681e-09
    …..

    thì 90% chưa hẳn là tốt, có thể là 99,9999%

    1. PCA tìm eigenvalues và eigenvectors của ma trận XX^T, chứ không phải ma trận X.
      Do XX^T là positive semidefinite nên các trị riêng lúc nào cũng \geq 0, em không cần lo lắng.

  11. Cho mình hỏi xíu, hàm PCA trong matlab về xử lý ảnh thì nó tính về cái gì vậy ạ. Mình ko hiểu dòng này “[m,WPCA,yO]=my_pca(T,’simple’);” . Theo mình tinh thì m là ảnh trung bình, WPCA là các vecto riêng đã đc chuẩn hóa. Còn lại thì mình ko hiểu. Nhờ bạn chỉ cho mình với.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s