Bài giảng Máy học nâng cao - Chương 9: Dimensionality reduction and feature selection - Trịnh Tấn Đạt

Trịnh Tấn Đạt Khoa CNTT – Đại Học Sài Gòn Email: trinhtandat@sgu.edu.vn Website: https://sites.google.com/site/ttdat88/ Contents  Introduction: dimensionality reduction and feature selection  Dimensionality Reduction  Principal Component Analysis (PCA)  Fisher’s linear discriminant analysis (LDA)  Example: Eigenface  Feature Selection  Homework Introduction  High-dimensional data often contain redundant features  reduce the accuracy of data classification algorithms  slow down the classification process  be a problem in storage and retrieval  hard to interpret (visualize)  Why we need dimensionality reduction???  To avoid “curse of dimensionality”  To reduce feature measurement cost  To reduce computational cost https://en.wikipedia.org/wiki/Curse_of_dimensionality Introduction  Dimensionality reduction is one of the most popular techniques to remove noisy (i.e., irrelevant) and redundant features.  Dimensionality reduction techniques: feature extraction v.s feature selection  feature extraction: given N features (set X), extract M new features (set Y) by linear or non- linear combination of all the N features (i.e. PCA, LDA)  feature selection: choose a best subset of highly discriminant features of size M from the available N features (i.e. Information Gain, ReliefF, Fisher Score) Dimensionality Reduction Principal component analysis (PCA) ❖ Variance v.s. Covariance  Variance : phương sai của một biến ngẫu nhiên là thước đo sự phân tán thống kê của biến đó, nó hàm ý các giá trị của biến đó thường ở cách giá trị kỳ vọng bao xa.  Covariance: hiệp phương sai là độ đo sự biến thiên cùng nhau của hai biến ngẫu nhiên (phân biệt với phương sai - đo mức độ biến thiên của một biến) 1 ( )(y ) Cov( , ) (N 1) N i i i x x y X Y = − − = −  Low variance High variance Principal component analysis (PCA)  Mean (expected value): giá trị “mong muốn”, biểu diễn giá trị trung bình của một biến.  Standard Deviation: Độ lệch chuẩn đo tính biến động của giá trị mang tính thống kê. Nó cho thấy sự chênh lệch về giá trị của từng thời điểm đánh giá so với giá trị trung bình. Principal component analysis (PCA)  Representing Covariance between dimensions as a matrix e.g. for 3 dimensions:  cov(x,y) = cov(y,x) hence matrix is symmetrical about the diagonal  N-dimensional data will result in NxN covariance matrix Principal component analysis (PCA)  What is the interpretation of covariance calculations? e.g.: dữ liệu 2 chiều x: số lượng giờ học một môn học y: điểm số của một môn học covariance value ~ 104.53 what does this value mean? -> số lượng giờ học tăng  , điểm số  Principal component analysis (PCA)  Exact value is not as important as it’s sign.  A positive value of covariance indicates both dimensions increase or decrease together (e.g. as the number of hours studied increases, the marks in that subject increase.)  A negative value indicates while one increases the other decreases, or vice-versa (e.g. active social life v.s performance in class.)  If covariance is zero: the two dimensions are independent of each other (e.g. heights of students vs the marks obtained in a subject.) Principal component analysis (PCA) Principal component analysis (PCA)  Principal components analysis (PCA) là một phương pháp để đơn giản hóa một tập dữ liệu (simplify a dataset) , chằng hạn giảm số chiều của dữ liệu. “It is a linear transformation that chooses a new coordinate system for the data set such that  the greatest variance by any projection of the data set comes to lie on the first axis (then called the first principal component),  the second greatest variance on the second axis  and so on. ”  PCA có thể được dùng để giảm số chiều bằng cách loại bỏ những thành phần chính không quan trọng. Principal component analysis (PCA)  Ví dụ: khi thực hiện các phân tích đa biến mà trong đó các biến có tương quan với nhau gây nhiều khó khăn loại bỏ sự tương quan này bằng cách xoay trục (cơ sở) dữ liệu trên trục mới đã giảm sự tương quan đáng kể (biến Y1 và Y2 gần như không tương quan) sự thay đổi của dữ liệu phụ thuộc phần lớn vào biến Y1 giảm số chiều dữ liệu mà không làm giàm quá nhiều “phương sai” của dữ liệu Principal component analysis (PCA)  Note:  Giúp giảm số chiều của dữ liệu;  Thay vì giữ lại các trục tọa độ của không gian cũ, PCA xây dựng một không gian mới ít chiều hơn, nhưng lại có khả năng biểu diễn dữ liệu tốt tương đương không gian cũ. Principal component analysis (PCA)  Ví dụ: Khám phá liên kết tiềm ẩn nhờ đổi hệ trục tọa độ, cách nhìn khác nhau về cùng một dữ liệu. Principal component analysis (PCA)  Ví dụ: Notice that "the maximum variance" and "the minimum error" are reached at the same time, namely when the line points to the magenta ticks Principal component analysis (PCA)  How to find the optimal linear transformation A ( where y = Ax) -1. Origin of PCA coordinate  mean of samples -2. Maximize projected variance -3. Minimize projection cost min x y− Principal component analysis (PCA) https://hadrienj.github.io/posts/Deep-Learning-Book-Series-2.12-Example-Principal-Components- Analysis/ Principal component analysis (PCA)  Note:  The eigenvectors of the covariance matrix define a new coordinate system  Eigenvector with largest eigenvalue captures the most variation among training vectors x  eigenvector with smallest eigenvalue has least variation  The eigenvectors are known as principal components https://hadrienj.github.io/posts/Deep-Learning-Book-Series-2.12-Example-Principal-Components-Analysis/ Principal component analysis (PCA)  Algorithm: 7 steps  Input : N mẫu input 1. Tính vector trung bình của toàn bộ dữ liệu: 2. Trừ mỗi điểm dữ liệu đi vector trung bình của toàn bộ dữ liệu: Note: subtracting the mean is equivalent to translating the coordinate system to the location of the mean Principal component analysis (PCA) 3. Tính covaricance matrix 4. Perform the eigendecomposition : tìm eigenvectors và eigenvalues của S và sắp xếp theo thứ từ giảm dần của eigenvalues . 5. Chọn K eigenvectors với K trị riêng lớn nhất để xây dựng ma trận UK (projection matrix) có các cột tạo thành một hệ trực giao. K vectors này, còn được gọi là các thành phần chính, tạo thành một không gian con gần với phân bố của dữ liệu ban đầu đã chuẩn hoá. Principal component analysis (PCA) 6. Chiếu dữ liệu ban đầu đã chuẩn hoá xuống không gian con tìm được. 7. Dữ liệu mới chính là toạ độ của các điểm dữ liệu trên không gian mới. Dữ liệu ban đầu có thể tính được xấp xỉ theo dữ liệu mới như sau: PCA Principal component analysis (PCA) Principal component analysis (PCA) Principal component analysis (PCA) Principal component analysis (PCA) Principal component analysis (PCA) Principal component analysis (PCA) PCA  Ví dụ: Principal component analysis (PCA)  Problem: In the case of the data in the two classes, after projection along the first principal eigenvector, remain well separated. In the case of the data in the two classes, after projection along the first principal eigenvector, is not well separated because the mean of the two classes are too close Principal component analysis (PCA)  Disadvantage of PCA Principal Component Analysis •higher variance •bad for discriminability Fisher Linear Discriminant Linear Discriminant Analysis •smaller variance •good discriminability Fisher’s linear discriminant analysis  The objective of LDA is to perform dimensionality reduction while preserving as much of the class discriminatory information as possible.  Assume we have a set of l-dimensional samples , N1 of which belong to class 1 , and N2 to class 2 . We seek to obtain a scalar y by projecting the samples x onto a line: }x,,x,{x 21 N xwy T= Fisher’s linear discriminant analysis ❖ Case: TWO CLASSES  Of all the possible lines we would like to select the one that maximizes the separability of the scalars. This is illustrated for the two-dimensional case in the following figures The two classes are not well separated when projected onto this line This line succeeded in separating the two classes and in the meantime reducing the dimensionality of our problem from two features (x1,x2) to only a scalar value y. Fisher’s linear discriminant analysis  The Fisher linear discriminant is defined as the linear function that maximizes the criterion function: xwT 2 2 2 1 2 21 ）-（   + =FDR where  1,  2 are the mean values of y, and 1 ,  2 are the variances of y in the two classes, respectively. LDA...two classes  In order to find the optimum projection w*, we need to express FDR as an explicit function of w.  For two equiprobable classes ➢ SW is known as the within-class scatter matrix, with S1 , S2 being the respective covariance matrices.  Now, the scatter of the projection y can then be expressed as a function of the scatter matrix in feature space x. )( 2 1 21w SSS += T ii i i mxmxN S i )()( 1 x −−=   wSw T w 2 2 2 1 =+  LDA...two classes  Sb is known as the between-class scatter matrix ➢ m0 is the overall mean of the data x in the original l-dimensional space and m1 , m2 are the mean values in the two classes, respectively  Similarly, the difference between the projected means (in y-space) can be expressed in terms of the means in the original feature space (x-space). TT mmmmmmmmS ))(( 2 1 ))(( 2 1 02020101b −−+−−= ww）-（ b 2 21 S T= LDA...two classes  We can finally express the Fisher criterion in terms of SW and Sb as: wS wS FDR w T b T w w）-（ 2 2 2 1 2 21 = + =   LDA...two classes  First method：eigen-decompostition  Second method： 0 w w dw d =        wS wS w T b T wwSS bw = −1 scalarFDR == )( w w maxargmaxarg 21 1* mmS wS wS FDRw w w T b T ww −=        == − where Fisher’s linear discriminant analysis  Case: C-classes Principal component analysis (PCA)  PCA vs. LDA LDA PCA Principal component analysis (PCA)  PCA vs. LDA Principal component analysis (PCA)  Improvements of PCA  Probabilistic PCA  Kernel PCA  Robust PCA ( - low rank matrix recovery) Linear Discriminant Analysis (LDA)  Improvements of LDA  Probabilistic LDA  Kernel Fisher Discriminant Analysis Example: Eigenface  Dùng PCA như một phương pháp rút trích đặc trưng (feature extraction) cho hình ảnh khuôn mặt (facial images).  Eigenface là một trong các phương pháp phổ biến nhất trong bài toán nhận dạng khuôn mặt.  Ý tưởng của Eigenface là đi tìm một không gian có số chiều nhỏ hơn để mô tả mỗi khuôn mặt, từ đó sử dụng vector trong không gian thấp này như là feature vector cho việc thực hiện classification.  Điều đáng nói là một bức ảnh khuôn mặt có kích thước khoảng 200 × 200 sẽ có số chiều là 40k - là một số cực lớn, trong khi đó, feature vector thường chỉ có số chiều bằng vài trăm.  Các Eigenfaces chính là các eigenvectors ứng với các trị riêng lớn nhất của ma trận hiệp phương sai. Eigenface  Face Identification using PCA  An image is a point in a high dimensional space  An N x M image is a point in RNxM  We can define vectors in this space as we did in the 2D case Eigenface: Training  Get 𝑀 training samples with variances Images are in same size Eigenface: Training  Step 0: Convert all the images in vector form.  Step 1: Calculate the mean (Average Face) Eigenface: Training  Step 2: Normalize vectors  Step 3: Form the covariance matrix Eigenface: Training  Step 4: We calculate the Eigen vectors of Covariance Matrix  Step 5: So, we choose k eigenvectors corresponding to k largest eigenvalues to construct a projection matrix Very high dimension So, we compute Eigenface: Training  Step 6-7: Training Images projected to face space. Eigenface: Training Eigenface: Test  Take query image t  Substact mean image : y = t –   Project y into eigenface space and compute projection  Compare projection I with all N training projections  Simple comparison metric: Euclidean  Classifier: multiclass-logistic regression, SVM, Eigenface Eigenface  Pros  Ease of implementation  No knowledge of geometry or specific feature of the face required  Cons  Sensitive to head scale  Applicable only to front view  Good performance only under controlled background (not including natural scenes) State-of-the-art face recognition performance  OpenFace  FaceNet embedding  InsightFace  Feature Selection Introduction: Feature Selection  Need for a small number of discriminative features  To avoid “curse of dimensionality”  To reduce feature measurement cost  To reduce computational burden  Feature selection algorithms can be categorized  Supervised: filter models, wrapper models, and embedded models  Unsupervised  Semi-supervised Introduction  A feature selection method consists of four basic steps  subset generation  subset evaluation  stopping criterion  result validation Introduction Feature Selection for Classification Introduction  Feature selection for classification attempts to select the minimally sized subset of features according to the following criteria:  the classification accuracy does not significantly decrease; and  the resulting class distribution, given only the values for the selected features, is as close as possible to the original class distribution, given all features. Introduction  Feature selection is an optimization problem.  Search the space of possible feature subsets.  Pick the subset that is optimal or near-optimal with respect to a certain criterion. Search strategies Evaluation strategies - Optimum - Filter methods - Heuristic - Wrapper methods - Randomized Introduction Algorithms for Flat Features  Three groups:  filter models  wrapper models  embedded models  Features are assumed to be independent Algorithms for Flat Features 1. Filter Models  Filter models evaluate features without utilizing any classification algorithms  The objective function evaluates feature subsets by their information content, typically interclass distance, statistical dependence or information- theoretic measures.  Performance criteria : Fisher score, Mutual information, ReliefF Algorithms for Flat Features ❖ Fisher Score  Features with high quality should assign similar values to instances in the same class and different values to instances from different classes.  The score for the i-th feature Si will be calculated by Fisher Score as Algorithms for Flat Features ❖ Mutual Information based on Methods  Information gain is used to measure the dependence between features and labels  Calculates the information gain between the i-th feature fi and the class labels C as  A feature is relevant if it has a high information gain Algorithms for Flat Features Algorithms for Flat Features 2. Wrapper Models  It utilize a specific classifier to evaluate the quality of selected features, and offer a simple and powerful way to address the problem of feature selection, regardless of the chosen learning machine  A typical wrapper model will perform the following steps:  Step 1: searching a subset of features,  Step 2: evaluating the selected subset of features by the performance of the classifier,  Step 3: repeating Step 1 and Step 2 until the desired quality is reached.  Search strategies: hill-climbing, best-first, GA, Algorithms for Flat Features Algorithms for Flat Features Algorithms for Flat Features 3. Embedded Models  Embedded Models embedding feature selection with classifier construction, have the advantages of (1) wrapper models — they include the interaction with the classification model and (2) filter models—and they are far less computationally intensive than wrapper methods.  Three types of embedded methods  Pruning methods: that first utilize all features to train a model and then attempt to eliminate some features by setting the corresponding coefficients to 0, while maintaining model performance such as recursive feature elimination using a support vector machine.  The second are models with a built-in mechanism for feature selection such as ID3 and C4.5.  The third are regularization models with objective functions that minimize fitting errors and in the meantime force the coefficients to be small or to be exactly zero. Features with coefficients that are close to 0 are then eliminated. Methods: Lasso Regularization, Adaptive Lasso, Bridge regularization, Elastic net regularization. Algorithms for Flat Features ❖ Regularization methods  Classifier induction and feature selection are achieved simultaneously by estimating w with properly tuned penalties.  Feature selection is achieved and only features with nonzero coefficients in w will be used in the classifier  Lasso Regularization: Lasso regularization is based on l1-norm of the coefficient of w and defined as l1 regularization can generate an estimation of w with exact zero coefficients. In other words, there are zero entities in w, which denotes that the corresponding features are eliminated during the classifier learning process. Therefore, it can be used for feature selection. Algorithms for Structured Features  For many real-world applications, the features exhibit certain intrinsic structures, e.g., spatial or temporal smoothness, disjoint/overlapping groups, trees, and graphs.  Incorporating knowledge about the structures of features may significantly improve the classification performance and help identify the important features.  We focus on linear classifiers with structured features to minimize a empirical error penalized by a regularization term as where G denotes the structure of features, and α controls the trade-off between data fitting and regularization Research ▪ Algorithms for Structured Features ▪ Algorithms for Streaming Features Discussions and Challenges 1. Scalability  With the growth of dataset sizes, the scalability of current algorithms may be in jeopardy, especially with these domains that require an online classifier.  The scalability of feature selection algorithms is a big problem. Usually, they require a sufficient number of samples to obtain, statically, adequate results. Discussions and Challenges 2. Stability  It is defined as the sensitivity of the selection process to data perturbation in the training set.  The underlying characteristics of data can greatly affect the stability of an algorithm.  These characteristics include dimensionality m, sample size n, and different data distribution across different folds, and the stability issue tends to be data dependent Discussions and Challenges 3. Linked Data  Linked data has become ubiquitous in real-world applications such as tweets in Twitter (tweets linked through hyperlinks), social networks in Facebook (people connected by friendships), and biological networks (protein interaction networks).  Linked data is patently not independent and identically distributed (i.i.d.).  Feature selection methods for linked data need to solve the following immediate challenges:  How to exploit relations among data instances; and  How to take advantage of these relations for feature selection.  Two attempts to handle linked data w.r.t. feature selection for classification are LinkedFS and FSNet Homework 1) Apply feature selection for Boston dataset recognition. Ref: https://datasciencebeginners.com/2018/11/26/using-scikit-learn-in- python-for-feature-selection/ Homework 2) Apply PCA as dimension reduction for iris recognition Ref : https://towardsdatascience.com/pca-using-python-scikit-learn- e653f8989e60