Trị đặc trưng và vector đặc trưng

Eigenvalues và eigenvectors xuất hiện cực kỳ nhiều trong các ngành khoa học và kỹ thuật: Vật Lý, xác suất thống kê, KHMT, lý thuyết đồ thị, v.v. Để hiểu ý nghĩa của chúng, có hai hướng nhìn thông dụng, áp dụng được trong rất nhiều trường hợp.

1. Loại động cơ (motivation) thứ nhất.

Trong nhiều ứng dụng ta thường phải làm phép tính sau đây: cho trước một ma trận A và nhiều vectors x, tính A^kx với nhiều giá trị khác nhau của số mũ k. Ví dụ 1: nếu A là ma trận của một phép biến đổi tuyến tính (linear transformation) nào đó, như phép quay và co dãn trong computer graphics chẳng hạn, thì A^kx cho ra kết quả của phép BĐTT này áp dụng k lần vào x. Các games máy tính hay các annimations trong phim của Hollywood có vô vàn các phép biến đổi kiểu này. Mỗi một object trong computer graphics là một bộ rất nhiều các vector x. Quay một object nhiều lần là làm phép nhân A^kx với từng vectors x biểu diễn object đó. Khối lượng tính toán là khổng lồ, dù chỉ trong không gian 3 chiều. Ví dụ 2: nếu A là transition matrix của một chuỗi Markov rời rạc và x là distribution của trạng thái hiện tại, thì A^kx chính là distribution của chuỗi Markov sau k bước. Ví dụ 3: các phương trình sai phân (difference equation) như kiểu phương trình a_n = 4a_{n-1} + 3a_{n-2} - a_{n-3} cũng có thể được viết thành dạng A^kx để tính a_k với k tùy ý. Ví dụ 4: lũy thừa của một ma trận xuất hiện tự nhiên khi giải các phương trình vi phân, xuất hiện trong khai triển Taylor của ma trận e^{At} chẳng hạn.

Tóm lại, trong rất nhiều ứng dụng thì ta cần tính toán rất nhanh lũy thừa của một ma trận vuông, hoặc lũy thừa nhân một vector.

Mỗi ma trận vuông đại diện cho một phép BĐTT nào đó. Lũy thừa bậc k của ma trận đại diện cho phép biến đổi này áp dụng k lần. Ngược lại, bất kỳ phép BĐTT nào cũng có thể được đại diện bằng một ma trận. Có rất nhiều ma trận đại diện cho cùng một BĐTT, tùy theo ta chọn hệ cơ sở nào. Mỗi khi ta viết một vector dưới dạng x = (3, -2, 5)^T là ta đã ngầm định một hệ cơ sở nào đó, thường là hệ cơ sở trực chuẩn e_1 = (1,0,0)^T, e_2 = (0,1,0)^T, và e_3 = (0,0,1)^T. Các tọa độ 3, -2, 5 của x là tương ứng với tọa độ của x trong hệ cơ sở ngầm định này.

Hệ cơ sở e_1, \dots, e_n như trên thường được dùng vì ta “dễ” hình dùng chúng trong không gian n chiều, chúng là sản phẩm phụ của hệ tọa đồ Descartes cổ điển hay dùng trong không gian 2 chiều. Tuy nhiên, khi áp dụng một phép BĐTT thì các vectors e_1, \dots, e_n thường cũng bị biến đổi theo luôn, rất bất tiện nếu ta phải tính A^kx cho nhiều giá trị k và x khác nhau.

Bây giờ, giả sử ta tìm được n hướng độc lập tuyến tính và bất biến qua phép BĐTT đại diện bởi A. (Đây là giả sử rất mạnh, may mà nó lại thường đúng trong các ứng dụng kể trên.) Dùng vector u_i để biểu diễn hướng thứ i. Bất biến có nghĩa là áp dụng A vào hướng nọ thì hướng không đổi. Cụ thể hơn, BĐTT A làm hướng u_i “bất biến” nếu Au_i = \lambda_i u_i với \lambda_i là một con số (scalar) thực hoặc phức nào đó (dù ta giả sử A là thực). Do các hướng này độc lập tuyến tính, một vector x bất kỳ đều viết được dưới dạng

x = x_1u_1 + x_2u_2 + \dots + x_nu_n

Nếu ta lấy u_1,\dots, u_n làm hệ cơ sở thì cái hay là có áp dụng A bao nhiêu lần thì cũng không đổi hướng của các vectors trong hệ cơ sở! Điều này rất tiện lợi, bởi vì
A^kx = x_1A^ku_1 + \dots + x_nA^ku_n = x_1\lambda_1^ku_1 + \dots + x_n\lambda_n^ku_n

Như vậy, thay vì tính lũy thừa bậc cao của một ma trận, ta chỉ cần tính lũy thừa của n con số và làm một phép cộng vectors đơn giản. Các giá trị \lambda_i là các trị đặc trưng (eigenvalues) của A, và các vectors u_i là các vector đặc trưng (eigenvectors).

Tiếp tục với giả thiết rất mạnh là n eigenvectors độc lập tuyến tính với nhau. Nếu ta bỏ các vectors này vào các cột của một ma trận U, và các eigenvalues lên đường chéo của một ma trận \Lambda thì ta có \Lambda = U^{-1}AU. Trong trường hợp này ma trận A có tính diagonalizable (chéo hóa được). Diagonalizability và sự độc lập tuyến tính của n eigenvectors là hai thuộc tính tương đương của một ma trận. Ngược lại, ta cũng có A = U\Lambda U^{-1}, và vì thế lũy thừa của A rất dễ tính: A^k = U\Lambda^k U^{-1} do lũy thừa của một ma trận đường chéo rất dễ tính.

Cụm từ “khả năng đường chéo hóa được” (diagonalizability) nghe ghê răng quá, có bạn nào biết tiếng Việt là gì không?

Nếu ta biết được các eigenvectors và eigenvalues của một ma trận thì — ngoài việc tính lũy thừa của ma trận — ta còn dùng chúng vào rất nhiều việc khác, tùy theo ứng dụng ta đang xét. Ví dụ: tích các eigenvalues bằng với định thức, tổng bằng với trace, khoảng cách giữa eigenvalue lớn nhất và lớn nhì của transition matrix của một chuỗi Markov đo tốc độ hội tụ đến equilibrium (mixing rate) và eigenvector đầu tiên là steady state distribution, vân vân.

Quay lại với cái “giả thiết rất mạnh” ở trên. Có một loại ma trận mà giả thiết này đúng; và hơn thế nữa, ta có thể tìm được các eigenvectors vuông góc nhau, đó là các normal matrices. Rất nhiều ứng dụng trong khoa học và kỹ thuật cho ta các normal matrices. Các trường hợp đặc biệt thường thấy là các ma trận (thực) đối xứng và các ma trận Hermitian (đối xứng theo nghĩa phức).

Còn các ma trận không thỏa mãn “giả thiết rất mạnh” này, nghĩa là không diagonalizable, thì làm gì với chúng? Ta có thể tìm cách làm cho chúng rất “gần” với một ma trận đường chéo bằng cách viết chúng thành dạng chuẩn Jordan. Đề tài này nằm ngoài phạm vi bài đang viết.

2. Loại động cơ (motivation) thứ hai.

Trong rất nhiều ứng dụng, ta “được” làm việc với một ma trận đối xứng: nó có đủ bộ eigenvectors, do đó diagonalizable và vì thế có thể thiết kế các thuật toán hiệu quả cho các bài toán tương ứng. Không những đối xứng, chúng còn có một thuộc tính mạnh hơn nữa gọi là positive (semi) definite, nghĩa là các eigenvalues đều không âm. Ví dụ 1: bài toán least squares Ax \approx b có ứng dụng khắp nơi (linear regression trong statistics chẳng hạn) dẫn đến ma trận symmetric positive (semi) definite A^TA. Ví dụ 2: bài toán xác định xem một một điểm tới hạn của một hàm đa biến bất kỳ có phải là điểm cực tiểu hay không tương đương với xác định xem ma trận đối xứng Hessian của các đạo hàm bậc hai tại điểm này là positive definite. Ví dụ 3: ma trận covariance của một random vector (hoặc một tập hợp rất nhiều sample vectors) cũng là positive (semi) definite.

Nếu A là một ma trận symmetric positive definite thì ta có thể hiểu các eigenvectors và eigenvalues theo cách khác. Bất phương trình

x^TAx \leq c

trong đó c là một hằng số dương là một bất phương trình bậc 2 với n biến x_1, \dots, x_n (các tọa độ của vector x). Nghiệm của nó là các điểm nằm trong một hình e-líp trong không gian n chiều (Ellipsoid) mà n trục của ellipsoid chính là hướng của các eigenvectors của A, và chiều dài các trục tỉ lệ nghịch với eigenvalue tương ứng (tỉ lệ với nghịch đảo của căn của eigenvalue). Đây là trực quan hình học phổ biến thứ hai của eigenvectors và eigenvalues.

Trong trường hợp của Principal Component Analysis (PCA) như có bạn đã hỏi trong phần bình luận bài tư duy trừu tượng, thì ta có thể hiểu nôm na về sự xuất hiện của eigen-vectors/values như sau. Giả sử ta có một đống các sample vectors (data points) trên một không gian n chiều nào đó. Các tọa độ là exponentially distributed (Gaussian noise chẳng hạn). Thì đa số các vectors này tập trung trong một ellipsoid định nghĩa bởi covariance matrix (positive semi-definite). Trục dài nhất của ellipsoid là trục có variance cao nhất, nghĩa là SNR cao. Trục này chỉ cho ta hướng biến thiên quan trọng nhất của data. PCA lấy các trục của ellipsoid làm hệ cơ sở, sau đó lấy k trục dài nhất làm principal components để biểu diễn data. (Dĩ nhiên, ta phải shift cái mean về gốc tọa độ trước khi đổi hệ cơ sở.)

Chủ đề : Toán Ứng Dụng, Trí tuệ nhân tạo, Xác suất & thống kêBookmark the permalink. Trackbacks are closed, but you can post a comment.

18 Comments

  1. npson
    Posted 24/10/2007 at 2:58 pm | Permalink

    Bay gio moi duoc biet them cach dung moi qua motivation thu 2 cua bac Hung

  2. ana
    Posted 24/10/2007 at 9:37 pm | Permalink

    Cảm ơn anh Hưng về bài viết gần gũi, thiết thực. Giá ngày xưa học đại số tuyến tính (trong chương trình toán cao cấp ở đại học) mà hiểu được ý nghĩa áp dụng của trị riêng, vector riêng thay vì chỉ công thức, biến đổi, và chứng minh thuần túy.

    Em nảy ra ý nho nhỏ thế này. Có khi anh Hưng tạo/tập hợp một danh sách riêng các bài dạng như thế này (có thể người khác đóng góp nữa vì trên này cũng lắm cao thủ toán và KHMT) gọi là “Tản toán/khmt” giống như “Tản văn” của chị Vàng Anh (xịn) 🙂

  3. sloth
    Posted 25/10/2007 at 2:41 am | Permalink

    Cảm ơn bác Hưng, bài viết này tôi thấy ngắn gọn, dễ hiểu.
    Rất xin lỗi các bác, tôi có vài câu hỏi ngu xị không biết hỏi ai:
    – “SNR” là gì thế ạ?
    – bài toán “học” PCA trên tập dữ liệu lớn, incremental, khó như thế nào trên quan điểm “Machine Learning”?
    – Định lý Birkhoff: 1 ma trận “doubly stochastic” có thể phân tích thành tổ hợp lồi của ko quá (n**2 – 2*n +2) ma trận có những ý nghĩa gì?

  4. Posted 25/10/2007 at 5:31 am | Permalink

    @ana: ý tưởng “Tản Toán” rất hay. Các bác viết đi, gửi cho tôi đăng lên blog. Thật ra trên blog này tôi cũng viết Tản Toán khá nhiều.

    @sloth: câu 2 thì để các bác làm về ML trả lời.

    – SNR là Signal-to-Noise-Ratio.

    – Định lý Birkhoff-von Neumann, theo nghĩa hình học chỉ đơn giản là một điểm trong đa diện lồi là tổ hợp lồi của một số đỉnh đa diện.

    1. Với tôi, định lý Birkhoff là hệ quả đơn giản của fact sau đây: bất kỳ k-regular bipartite graph nào cũng là disjoint union của k perfect matchings. Nó tương đương với rất nhiều định lý khác trong graph theory (Hall’s matching condition hoặc định lý Konig chẳng hạn). Xem lecture note này tôi có viết sơ bộ về liên hệ của chúng.

    2. Tôi cho rằng câu hỏi quan trọng hơn là tại sao lại cần giảm thiểu số permutation matrices (đỉnh của đa diện). Có một ứng dụng rất cụ thể là thiết kế scheduling algorithms cho các input-queued switches trên Internet. Ma trận traffic của switch là (sub) doubly-stochastic. Mỗi permutation matrix tương ứng với một routing session. Hệ số của permutation matrix tỉ lệ thuận với duration của session. Ta không muốn router đổi trạng thái từ session này sang session khác nhiều, vì thế muốn giảm thiểu tổng số permutation matrices.

    Khi nào rảnh rỗi tôi sẽ viết kỹ hơn về 2 ý trên.

  5. npson
    Posted 25/10/2007 at 9:04 pm | Permalink

    Nhân nói về tản Toán có quyển Princeton companion to Mathematics đang được biên soạn khá hay. Các bác có hứng với Toán thì đọc cho vui.

  6. Minh Lê
    Posted 26/10/2007 at 2:25 am | Permalink

    Em đọc sách toán cao cấp thì thấy người ta dùng từ “chéo hoá” và “chéo hoá được”.

  7. Posted 26/10/2007 at 2:26 am | Permalink

    Cảm ơn Minh.

  8. dongta
    Posted 26/10/2007 at 3:54 pm | Permalink

    Thuật toán QR để tìm eigenvalues của 1 matrix được xem là 1 trong Top 10 algorithms of the 20th century (http://amath.colorado.edu/resources/archive/topten.pdf). Điều này giải thích một phần nào rằng mấy cái eigenthingies (mượn từ của Jonathan Shewchuck) này “are more important than they look”.

    Side note 1: nhớ lại lúc mình học Functional Analysis, ông thầy luôn bảo Hahn-Banach theorem is much more important than it looks. Mặc dù mấy các theorems bên Functional Analysis đều ultimately rely on Hahn-Banach theorem nhưng quả thật, đến giờ mình vẫn chưa bắt được cái thần của định lý này và cũng chưa đọc được bài nào diễn tả được cái thần đấy (ngoài việc claim rằng nó rất quan trọng).

    Side note 2: hôm nào bác Hưng mở một topic bàn về top algorithms of “the” century cho vui. Em (thực ra là adviser) nghĩ rằng danh sách này còn thiếu 4 ideas cũng revolutionary không kém khác:
    – Finite Element Method
    – Conjugate Gradient Method
    – Multigrid Method
    – Dynamic Programming

  9. abc_math
    Posted 06/05/2008 at 3:00 am | Permalink

    Chào anh Hưng, em hơi lười tra lại sách nên có thắc mắc sau:

    1 – Mọi normal operator đều chéo hóa trực giao (*) được hay chỉ mỗi symetric/ Hermititan operator là chéo hóa trực giao được, còn những normal operator khác như unitary operator, project operator chỉ chéo hóa được chứ không chéo hóa trực giao được.
    (* chéo hóa trực giao được tức là ma trận làm chéo là unitary matrix)

    2 – Phân loại các normal operator như thế nào ? Liệu
    {normal operators} = {symmetric/hermittian operators} + {orthogonal/unitary operators} + {project operators}
    (em thấy trong sách họ thường chỉ nói về 3 loại operators này, chúng đủ quét sạch hết các normal operators chứ ?)

  10. abc_math
    Posted 06/05/2008 at 3:06 am | Permalink

    PS: à mà câu hỏi 1- của em nó tương đương với việc: các không gian riêng của normal operators có luôn trực giao với nhau không nhỉ ?

  11. abc_math
    Posted 06/05/2008 at 3:12 am | Permalink

    PS ‘: à mà thêm nữa nếu câu 1 – đúng thì lớp operator nào chỉ chéo hóa được mà không chéo hóa trực giao được nhỉ hay là đã chéo hóa được thì luôn chéo hóa trực giao được.

  12. Minh
    Posted 12/09/2009 at 6:57 pm | Permalink

    Phần PCA theo ý nghĩa thống kê thì giúp làm giảm lượng tính toán sau khi xử lý các thông số có độ liên quan nhau cao (reduce number of variables according to highly correlated information) Thông qua PCA người ta có thể đi đến tìm pattern/structure của một tập dữ liệu (data set) với FA (Factor Analysis) với một số điều kiện (assumptions). Anh/chị có thể giải thích giúp em về các điều kiện đó không ạ? ^^

  13. Chanh
    Posted 30/03/2010 at 6:01 pm | Permalink

    Cho em hỏi : Có phương pháp nào giải quyết vấn đề tìm trị riêng, vector riêng cho ma trận đối xứng xác định riêng , mà không phải tính thông qua đa thức đặc trưng không ? Em cám ơn
    Em đang có nhu cầu , giải quyết vấn đề này để đối phó với ma trận cấp lớn

  14. Minh
    Posted 01/04/2010 at 12:46 pm | Permalink

    To Chanh,

    Với các ma trận lớn và rời rạc, người ta không dùng đa thức đặc trưng để tính giá trị và vector riêng, đơn giản là vì không hiệu quả và sai số tính toán sẽ lớn. Thông thường người ta sẽ dùng phương pháp lặp để tính toán, ở UofM có ông Saad (bạn của sư phụ Hưng) là một trong những người đi đầu về phương pháp này. Hầu như tất cả các phương pháp lặp này đều dựa trên conjugate gradient method (như dongta đã nói ở trên). Có rất nhiều open source library làm vấn đề này: taucs, OpenNL,… Cứ google là ra ngay. Ma trận cỡ lớn là bao nhiêu? Tôi đã từng có ma trận rời rạc cỡ khoảng 10^10 x 10^10, vẫn chạy ngon. Kinh nghiệm cho thấy khi dùng phương pháp lặp cộng với một preconditioner (Vietnamese?) thích hơp thì sẽ có lời giải nhanh hơn, cái này thì tùy thuộc vào cấu trúc của ma trận và bài toán bạn cần giải.

  15. Minh
    Posted 01/04/2010 at 4:21 pm | Permalink

    Chả hiểu sao tôi lại dịch “sparse” là “rời rạc”, đúng ra phải dịch là “thưa”. Sparse matrix = ma trận thưa.

  16. Posted 21/04/2010 at 5:34 am | Permalink

    Dạ, cám ơn.
    Em thấy thuật toán QR có độ phức tạp O(n^3)[\latex].
    Khi đem vào bài toán trị riêng thì độ phức tạp O(n^4)[\latex].
    Còn có thuật toán nào tốt hơn không ?

    Còn việc tính định thức của ma trận với độ phức tạp O(n^{2,..}) là thấp nhất chưa ?

  17. Thanh
    Posted 14/07/2010 at 6:39 am | Permalink

    Tôi mới nghiên cứu về PCA nên có 1 số thắc mắc rất mong được giải đáp:

    1/ Theo lý thuyết toán, ứng với mỗi eigenvalues sẽ có vô số eigenvector – tạo thành 1 không gian riêng ứng với eigenvalue đó. Vậy ta nên chọn eigenvector nào?

    2/ Ở bước cuối cùng của PCA, ta nên giữ lại bao nhiêu eigenvector của ma trận hiệp phương sai (covariance matrix)là thích hợp?

    3/ Trong giai đoạn nhận dạng (regconition), ta đi tìm phần tử trong tập mẫu có khoảng cách gần nhất với phần tử cần nhận dạng, và khoảng cách này phải “đủ bé”.

    Vậy ta nên chọn ngưỡng của khoảng cách này (face class distance) bao nhiêu là phù hợp?
    Tương tự như vậy cho việc chọn ngưỡng (face space distance) trong giai đoạn dò tìm (detection)?

    CÁM ƠN RẤT NHIỀU.

    • Tuấn
      Posted 12/09/2013 at 2:35 am | Permalink

      1/ Chọn eigenvector cơ sở, tức có độ dài = 1
      2/ Đủ để tổng bình phương những eigenvector đã chọn chiếm 90%, 95%…. trên tổng số tổng bình phương tất cả eigenvector.
      3/ Bé có nghĩa là sai số trên trị số, quy về phần trăm tự định nghĩa: 1%, 0,1%….. khai đại đi rồi thử chạy!. Tìm ra rồi tính lại thử match bao nhiêu % là được. Hiii

      Đây là cách hiểu của mình về pca, trên quan điểm thực tế nhất ^^

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*