2. Linear Discriminant Analysis cho bài toán với 2 classes 3. Linear Discriminant Analysis cho multi-class classification problems 3.1. Xây dựng hàm mất mát 4. Ví dụ trên Python
1. Giới thiệu
Trong hai bài viết trước, tôi đã giới thiệu về thuật toán giảm chiều dữ liệu được sử dụng rộng rãi nhất – Principle Component Analysis (PCA). Như đã đề cập, PCA là một phương pháp thuộc loại unsupervised learning, tức là nó chỉ sử dụng các vector mô tả dữ liệu mà không dùng tới labels, nếu có, của dữ liệu. Trong bài toán classification, dạng điển hình nhất của supervised learning, việc sử dụng labels sẽ mang lại kết quả phân loại tốt hơn.Bạn đang xem: Lda là gì
Nhắc lại một lần nữa, PCA là phương pháp giảm chiều dữ liệu sao cho lượng thông tin về dữ liệu, thể hiện ở tổng phương sai, được giữ lại là nhiều nhất. Tuy nhiên, trong nhiều trường hợp, ta không cần giữ lại lượng thông tin lớn nhất mà chỉ cần giữ lại thông tin cần thiết cho riêng bài toán. Xét ví dụ về bài toán phân lớp với 2 classes được mô tả trong Hình 1.
Đang xem: Linear discriminant analysis là gì
Hình 1: Chiếu dữ liệu lên các đường thẳng khác nhau. Có hai lớp dữ liệu minh hoạ bởi các điểm màu xanh và đỏ. Dữ liệu được giảm số chiều về 1 bằng cách chiếu chúng lên các đường thẳng khác nhau (d_1) và (d_2). Trong hai cách chiều này, phương của (d_1) gần giống với phương của thành phần chính thứ nhất của dữ liệu, phương của (d_2) gần với thành phần phụ của dữ liệu nếu dùng PCA. Khi chiếu lên (d_1), các điểm màu đỏ và xanh bị chồng lấn lên nhau, khiến cho việc phân loại dữ liệu là không khả thi trên đường thẳng này. Ngược lại, khi được chiếu lên (d_2), dữ liệu của hai class được chia thành các cụm tương ứng tách biệt nhau, khiến cho việc classification trở nên đơn giản hơn và hiệu quả hơn. Các đường cong hình chuông thể hiện xấp xỉ phân bố xác suất của dữ liệu hình chiếu trong mỗi class.
Trong Hình 1, ta giả sử rằng dữ liệu được chiếu lên 1 đường thẳng và mỗi điểm được đại diện bởi hình chiếu của nó lên đường thẳng kia. Như vậy, từ dữ liệu nhiều chiều, ta đã giảm nó về 1 chiều. Câu hỏi đặt ra là, đường thẳng cần có phương như thế nào để hình chiếu của dữ liệu trên đường thẳng này giúp ích cho việc classification nhất? Việc classification đơn giản nhất có thể được hiểu là việc tìm ra một ngưỡng giúp phân tách hai class một cách đơn giản và đạt kết quả tốt nhất.
Xét hai đường thằng (d_1) và (d_2). Trong đó phương của (d_1) gần với phương của thành phần chính nếu làm PCA, phương của (d_2) gần với phương của thành phần phụ tìm được bằng PCA. Nếu ra làm giảm chiều dữ liệu bằng PCA, ta sẽ thu được dữ liệu gần với các điểm được chiếu lên (d_1). Lúc này việc phân tách hai class trở nên phức tạp vì các điểm đại diện cho hai classes chồng lấn lên nhau. Ngược lại, nếu ta chiếu dữ liệu lên đường thẳng gần với thành phần phụ tìm được bởi PCA, tức (d_2), các điểm hình chiếu nằm hoàn toàn về hai phía khác nhau của điểm màu lục trên đường thẳng này. Với bài toán classification, việc chiếu dữ liệu lên (d_2) vì vậy sẽ mang lại hiệu quả hơn. Việc phân loại một điểm dữ liệu mới sẽ được xác định nhanh chóng bằng cách so sánh hình chiếu của nó lên (d_2) với điểm màu xanh lục này.
Qua ví dụ trên ta thấy, không phải việc giữ lại thông tin nhiều nhất sẽ luôn mang lại kết quả tốt nhất. Chú ý rằng kết quả của phân tích trên đây không có nghĩa là thành phần phụ mang lại hiệu quả tốt hơn thành phần chính, nó chỉ là một trường hợp đặc biệt. Việc chiếu dữ liệu lên đường thẳng nào cần nhiều phân tích cụ thể hơn nữa. Cũng xin nói thêm, hai đường thằng (d_1) và (d_2) trên đây không vuông góc với nhau, tôi chỉ chọn ra hai hướng gần với các thành phần chính và phụ của dữ liệu để minh hoạ. Nếu bạn cần đọc thêm về thành phần chính/phụ, bạn sẽ thấy Bài 27 và Bài 28 về Principal Component Analysis (Phân tích thành phần chính) có ích.
Linear Discriminant Analysis (LDA) được ra đời nhằm giải quyết vấn đề này. LDA là một phương pháp giảm chiều dữ liệu cho bài toán classification. LDA có thể được coi là một phương pháp giảm chiều dữ liệu (dimensionality reduction), và cũng có thể được coi là một phương pháp phân lớp (classification), và cũng có thể được áp dụng đồng thời cho cả hai, tức giảm chiều dữ liệu sao cho việc phân lớp hiệu quả nhất. Số chiều của dữ liệu mới là nhỏ hơn hoặc bằng (C-1) trong đó (C) là số lượng classes. Từ ‘Discriminant’ được hiểu là những thông tin đặc trưng cho mỗi class, khiến nó không bị lẫn với các classes khác. Từ ‘Linear’ được dùng vì cách giảm chiều dữ liệu được thực hiện bởi một ma trận chiếu (projection matrix), là một phép biến đổi tuyến tính (linear transform).
Trong Mục 2 dưới đây, tôi sẽ trình bày về trường hợp binary classification, tức có 2 classes. Mục 3 sẽ tổng quát lên cho trường hợp với nhiều classes hơn 2. Mục 4 sẽ có các ví dụ và code Python cho LDA.
2. Linear Discriminant Analysis cho bài toán với 2 classes
2.1. Ý tưởng cơ bản
Mọi phương pháp classification đều được bắt đầu với bài toán binary classification, và LDA cũng không phải ngoại lệ.
Quay lại với Hinh 1, các đường hình chuông thể hiện đồ thị của các hàm mật độ xác suất (probability density function – pdf) của dữ liệu được chiếu xuống theo từng class. Phân phối chuẩn ở đây được sử dụng như là một đại diện, dữ liệu không nhất thiết luôn phải tuân theo phân phối chuẩn.
Độ rộng của mỗi đường hình chuông thể hiện độ lệch chuẩn của dữ liệu. Dữ liệu càng tập trung thì độ lệch chuẩn càng nhỏ, càng phân tán thì độ lệch chuẩn càng cao. Khi được chiếu lên (d_1), dữ liệu của hai classes bị phân tán quá nhiều, khiến cho chúng bị trộn lẫn vào nhau. Khi được chiếu lên (d_2), mỗi classes đều có độ lệch chuẩn nhỏ, khiến cho dữ liệu trong từng class tập trung hơn, dẫn đến kết quả tốt hơn.
Tuy nhiên, việc độ lệch chuẩn nhỏ trong mỗi class chưa đủ để đảm bảo độ Discriminant của dữ liệu. Xét các ví dụ trong Hình 2.
Hình 2: Khoảng cách giữa các kỳ vọng và tổng các phương sai ảnh hưởng tới độ discriminant của dữ liệu. a) Khoảng cách giữa hai kỳ vọng là lớn nhưng phương sai trong mỗi class cũng lớn, khiến cho hai phân phối chồng lấn lên nhau (phần màu xám). b) Phương sai cho mỗi class là rất nhỏ nhưng hai kỳ vọng quá gần nhau, khiến khó phân biệt 2 class. c) Khi phương sai đủ nhỏ và khoảng cách giữa hai kỳ vọng đủ lớn, ta thấy rằng dữ liệu discriminant hơn.
Hình 2a) giống với dữ liệu khi chiếu lên (d_1) ở Hình 1. Cả hai class đều quá phân tán khiến cho tỉ lệ chồng lấn (phần diện tích màu xám) là lớn, tức dữ liệu chưa thực sự discriminative.
Hình 2b) là trường hợp khi độ lệch chuẩn của hai class đều nhỏ, tức dữ liệu tập trung hơn. Tuy nhiên, vấn đề với trường hợp này là khoảng cách giữa hai class, được đo bằng khoảng cách giữa hai kỳ vọng (m_1) và (m_2), là quá nhỏ, khiến cho phần chồng lấn cũng chiếm môt tỉ lệ lớn, và tất nhiên, cũng không tốt cho classification.
Xem thêm: Lập Và Phê Duyệt Lệnh Chuyển Tiền Là Gì, Tại Sao Có Lệnh Chuyển Tiền
Có thể bạn đang tự hỏi, độ lệch chuẩn và khoảng cách giữa hai kỳ vọng đại diện cho các tiêu chí gì:
Như đã nói, độ lệch chuẩn nhỏ thể hiện việc dữ liệu ít phân tán. Điều này có nghĩa là dữ liệu trong mỗi class có xu hướng giống nhau. Hai phương sai (s_1^2, s_2^2) còn được gọi là các within-class variances.
Khoảng cách giữa các kỳ vọng là lớn chứng tỏ rằng hai classes nằm xa nhau, tức dữ liệu giữa các classes là khác nhau nhiều. Bình phương khoảng cách giữa hai kỳ vọng ((m_1 – m_2)^2) còn được gọi là between-class variance.
Hai classes được gọi là discriminative nếu hai class đó cách xa nhau (between-class variance lớn) và dữ liệu trong mỗi class có xu hướng giống nhau (within-class variance nhỏ). Linear Discriminant Analysis là thuật toán đi tìm một phép chiếu sao cho tỉ lệ giữa between-class variance và within-class variance lớn nhất có thể.
2.2. Xây dựng hàm mục tiêu
Giả sử rằng có (N) điểm dữ liệu (mathbf{x}_1, mathbf{x}_2, dots, mathbf{x}_N) trong đó (N_1 &=&mathbf{w}^T underbrace{sum_{k=1}^2 sum_{n in mathcal{C}_k} (mathbf{x}_n – mathbf{m}_k)(mathbf{x}_n – mathbf{m}_k)^T}_{mathbf{S}_W} mathbf{w} = mathbf{w}^Tmathbf{S}_W mathbf{w}~~~~~(6)end{eqnarray}>(mathbf{S}_W) còn được gọi là within-class covariance matrix. Đây cũng là một ma trận đối xứng nửa xác định dương vì nó là tổng của hai ma trận đối xứng nửa xác định dương.
Trong ((5)) và ((6)), ta đã sử dụng đẳng thức:với (mathbf{a}, mathbf{b}) là hai vectors cùng chiều bất kỳ.
Như vậy, bài toán tối ưu cho LDA trở thành:
2.3. Nghiệm của bài toán tối ưu
Nghiệm (mathbf{w}) của ((7)) sẽ là nghiệm của phương trình đạo hàm hàm mục tiêu bằng 0. Sử dụng chain rule cho đạo hàm hàm nhiều biến và công thức (
abla_{mathbf{w}}mathbf{w} mathbf{A}mathbf{w} = 2mathbf{Aw}) nếu (mathbf{A}) là một ma trận đối xứng, ta có:
Lưu ý: Trong ((10)), ta đã giả sử rằng ma trận (mathbf{S}_W) là khả nghịch. Điều này không luôn luôn đúng, nhưng có một trick nhỏ là ta có thể xấp xỉ (mathbf{S}_W) bởi ( ar{mathbf{S}}_W approx mathbf{S}_W + lambdamathbf{I}) với (lambda) là một số thực dương nhỏ. Ma trận mới này là khả nghịch vì trị riêng nhỏ nhất của nó bằng với trị riêng nhỏ nhất của (mathbf{S}_W) cộng với (lambda) tức không nhỏ hơn (lambda > 0). Điều này được suy ra từ việc (mathbf{S}_W) là một ma trận nửa xác định dương. Từ đó suy ra (ar{mathbf{S}}_W) là một ma trận xác định dương vì mọi trị riêng của nó là thực dương, và vì thế, nó khả nghịch. Khi tính toán, ta có thể sử dụng nghịch đảo của (ar{mathbf{S}}_W).
Kỹ thuật này được sử dụng rất nhiều khi ta cần sử dụng nghịch đảo của một ma trận nửa xác định dương và chưa biết nó có thực sự là xác định dương hay không.
Quay trở lại với ((10)), vì (J(mathbf{w})) là một số vô hướng, ta suy ra (mathbf{w}) phải là một vector riêng của (mathbf{S}_W^{-1}mathbf{S}_B) ứng với một trị riêng nào đó. Hơn nữa, giá trị của trị riêng này bằng với (J(mathbf{w})). Vậy, để hàm mục tiêu là lớn nhất thì (J(mathbf{w})) chính là trị riêng lớn nhất của (mathbf{S}_W^{-1}mathbf{S}_B). Dấu bằng xảy ra khi (mathbf{w}) là vector riêng ứng với trị riêng lớn nhất đó. Bạn đọc có thể hiểu phần này hơn khi xem cách lập trình trên Python ở Mục 4.
Từ có thể thấy ngay rằng nếu (mathbf{w}) là nghiệm của ((7)) thì (kmathbf{w}) cũng là nghiệm với (k) là số thực khác không bất kỳ. Vậy ta có thể chọn (mathbf{w}) sao cho ((mathbf{m}_1 – mathbf{m}_2)^Tmathbf{w} = J(mathbf{w}) = L =) trị riêng lớn nhất của (mathbf{S}_W^{-1}mathbf{S}_B) . Khi đó, thay định nghĩa của (mathbf{S}_B) ở ((5)) vào ((10)) ta có:
Điều này có nghĩa là ta có thể chọn:với (alpha
eq 0) bất kỳ.
Biểu thức ((11)) còn được biết như là Fisher’s linear discriminant, được đặt theo tên nhà khoa học Ronald Fisher.
3. Linear Discriminant Analysis cho multi-class classification problems
3.1. Xây dựng hàm mất mát
Trong mục này, chúng ta sẽ xem xét trường hợp tổng quát khi có nhiều hơn 2 classes. Giả sử rằng chiều của dữ liệu (D) lớn hơn số lượng classes (C).
Giả sử rằng chiều mà chúng ta muốn giảm về là (D’ (mathbf{X}_k, mathbf{Y}_k = mathbf{W}^Tmathbf{X}_k) lần lượt là ma trận dữ liệu của class (k) trong không gian ban đầu và không gian mới với số chiều nhỏ hơn.
(mathbf{m}_k = frac{1}{N_k}sum_{n in mathcal{C}_k}mathbf{x}_k in mathbb{R}^{D}) là vector kỳ vọng của class (k) trong không gian ban đầu.
(mathbf{e}_k = frac{1}{N_k}sum_{n in mathcal{C}_k} mathbf{y}_n = mathbf{W}^Tmathbf{m}_k in mathbb{R}^{D’}) là vector kỳ vọng của class (k) trong không gian mới.
Xem thêm: Trà Giảm Cân Tiếng Anh Là Gì ? Các Từ Vựng Giảm Mỡ Trong Tiếng Anh
Một trong những cách xây dựng hàm mục tiêu cho multi-class LDA được minh họa trong Hình 3.