.. SPDX-FileCopyrightText: 2019-2020 Intel Corporation .. .. SPDX-License-Identifier: CC-BY-4.0 .. highlight:: cpp .. default-domain:: cpp .. _alg_pca: =================================== Principal Components Analysis (PCA) =================================== Principal Component Analysis (PCA) is an algorithm for exploratory data analysis and :capterm:dimensionality reduction. PCA transforms a set of feature vectors of possibly correlated features to a new set of uncorrelated features, called principal components. Principal components are the directions of the largest variance, that is, the directions where the data is mostly spread out. .. |t_math| replace:: Training _ .. |t_cov| replace:: Covariance _ .. |t_svd| replace:: SVD _ .. |t_input| replace:: train_input _ .. |t_result| replace:: train_result _ .. |t_op| replace:: train(...) _ .. |i_math| replace:: Inference _ .. |i_cov| replace:: Covariance _ .. |i_svd| replace:: SVD _ .. |i_input| replace:: infer_input _ .. |i_result| replace:: infer_result _ .. |i_op| replace:: infer(...) _ =============== ============= ============= ======== =========== ============ **Operation** **Computational methods** **Programming Interface** --------------- --------------------------- --------------------------------- |t_math| |t_cov| |t_svd| |t_op| |t_input| |t_result| |i_math| |i_cov| |i_svd| |i_op| |i_input| |i_result| =============== ============= ============= ======== =========== ============ ------------------------ Mathematical formulation ------------------------ .. _pca_t_math: Training -------- Given the training set :math:X = \{ x_1, \ldots, x_n \} of :math:p-dimensional feature vectors and the number of principal components :math:r, the problem is to compute :math:r principal directions (:math:p-dimensional eigenvectors [Lang87]_) for the training set. The eigenvectors can be grouped into the :math:r \times p matrix :math:T that contains one eigenvector in each row. .. _pca_t_math_cov: Training method: *Covariance* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This method uses eigenvalue decomposition of the covariance matrix to compute the principal components of the datasets. The method relies on the following steps: #. Computation of the covariance matrix #. Computation of the eigenvectors and eigenvalues #. Formation of the matrices storing the results Covariance matrix computation shall be performed in the following way: #. Compute the vector-column of sums :math:s_i = \sum_{j=1}^n x_{i,j}, \quad 1 \leq i \leq p. #. Compute the cross-product :math:P = X^TX - s^Ts. #. Compute the covariance matrix :math:\Sigma = \frac{1}{n - 1} P. To compute eigenvalues :math:\lambda_i and eigenvectors :math:\upsilon_i, the implementer can choose an arbitrary method such as [Ping14]_. The final step is to sort the set of pairs :math:(\lambda_i, \upsilon_i) in the descending order by :math:\lambda_i and form the resulting matrix :math:T = (\upsilon_{i,1}, \cdots, \upsilon_{i,r}), \quad 1 \leq i \leq p. Additionally, the means and variances of the initial dataset shall be returned. .. _pca_t_math_svd: Training method: *SVD* ~~~~~~~~~~~~~~~~~~~~~~ This method uses singular value decomposition of the dataset to compute its principal components. The method relies on the following steps: #. Computation of the singular values and singular vectors #. Formation of the matrices storing the results To compute singular values :math:\lambda_i and singular vectors :math:u_i and :math:v_i, the implementer can choose an arbitrary method such as [Demmel90]_. The final step is to sort the set of pairs :math:(\lambda_i, v_i) in the descending order by :math:\lambda_i and form the resulting matrix :math:T = (v_{i,1}, \cdots, v_{i,r}), \quad 1 \leq i \leq p. Additionally, the means and variances of the initial dataset shall be returned. Sign-flip technique ~~~~~~~~~~~~~~~~~~~ Eigenvectors computed by some eigenvalue solvers are not uniquely defined due to sign ambiguity. To get the deterministic result, a sign-flip technique should be applied. One of the sign-flip techniques proposed in [Bro07]_ requires the following modification of matrix :math:T: .. math:: \hat{T}_i = T_i \cdot \mathrm{sgn}(\max_{1 \leq j \leq p } |{T}_{ij}|), \quad 1 \leq i \leq r, where :math:T_i is :math:i-th row, :math:T_{ij} is the element in the :math:i-th row and :math:j-th column, :math:\mathrm{sgn}(\cdot) is the signum function, .. math:: \mathrm{sgn}(x) = \begin{cases} -1, & x < 0, \\ 0, & x = 0, \\ 1, & x > 0. \end{cases} .. note:: The sign-flip technique described above is an example. oneDAL spec does not require implementation of this sign-flip technique. Implementer can choose an arbitrary technique that modifies the eigenvectors' signs. .. _pca_i_math: Inference --------- Given the inference set :math:X' = \{ x_1', \ldots, x_m' \} of :math:p-dimensional feature vectors and the :math:r \times p matrix :math:T produced at the training stage, the problem is to transform :math:X' to the set :math:X'' = \{ x_1'', \ldots, x_m'' \}, where :math:x_{j}'' is an :math:r-dimensional feature vector, :math:1 \leq j \leq m. The feature vector :math:x_{j}'' is computed through applying linear transformation [Lang87]_ defined by the matrix :math:T to the feature vector :math:x_{j}', .. math:: :label: x_transform x_{j}'' = T x_{j}', \quad 1 \leq j \leq m. .. _pca_i_math_cov: .. _pca_i_math_svd: Inference methods: *Covariance* and *SVD* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Covariance and SVD inference methods compute :math:x_{j}'' according to :eq:x_transform. ------------- Usage example ------------- Training -------- .. onedal_code:: oneapi::dal::pca::example::run_training Inference --------- .. onedal_code:: oneapi::dal::pca::example::run_inference --------------------- Programming Interface --------------------- All types and functions in this section shall be declared in the oneapi::dal::pca namespace and be available via inclusion of the oneapi/dal/algo/pca.hpp header file. Descriptor ---------- .. onedal_class:: oneapi::dal::pca::descriptor Method tags ~~~~~~~~~~~ .. onedal_tags_namespace:: oneapi::dal::pca::method Task tags ~~~~~~~~~ .. onedal_tags_namespace:: oneapi::dal::pca::task Model ----- .. onedal_class:: oneapi::dal::pca::model .. _pca_t_api: Training :expr:train(...) -------------------------------- .. _pca_t_api_input: Input ~~~~~ .. onedal_class:: oneapi::dal::pca::train_input .. _pca_t_api_result: Result ~~~~~~ .. onedal_class:: oneapi::dal::pca::train_result Operation ~~~~~~~~~ .. onedal_func:: oneapi::dal::pca::train .. _pca_i_api: Inference :expr:infer(...) ---------------------------- .. _pca_i_api_input: Input ~~~~~ .. onedal_class:: oneapi::dal::pca::infer_input .. _pca_i_api_result: Result ~~~~~~ .. onedal_class:: oneapi::dal::pca::infer_result Operation ~~~~~~~~~ .. onedal_func:: oneapi::dal::pca::infer