Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Dimensionality Reduction

    Uploaded by

    madsilveratrest
    The document discusses dimensionality reduction techniques for simplifying complex high-dimensional data into a lower dimensional representation. It introduces principal component analysis (PCA) as a method to find vectors that maximize the variance when projecting the data. PCA finds the directions along which the data varies the most, allowing it to compress the data with minimal information loss. The document provides examples of using PCA to reduce the dimensions of image data for compression purposes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Dimensionality Reduction

    Uploaded by

    madsilveratrest
    28 views35 pages
    The document discusses dimensionality reduction techniques for simplifying complex high-dimensional data into a lower dimensional representation. It introduces principal component analysis (PCA) as a method to find vectors that maximize the variance when projecting the data. PCA finds the directions along which the data varies the most, allowing it to compress the data with minimal information loss. The document provides examples of using PCA to reduce the dimensions of image data for compression purposes.

    Original Description:

    part of data science

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses dimensionality reduction techniques for simplifying complex high-dimensional data into a lower dimensional representation. It introduces principal component analysis (PCA) as a method to find vectors that maximize the variance when projecting the data. PCA finds the directions along which the data varies the most, allowing it to compress the data with minimal information loss. The document provides examples of using PCA to reduce the dimensions of image data for compression purposes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    28 views35 pages

    Dimensionality Reduction

    Uploaded by

    madsilveratrest
    The document discusses dimensionality reduction techniques for simplifying complex high-dimensional data into a lower dimensional representation. It introduces principal component analysis (PCA) as a method to find vectors that maximize the variance when projecting the data. PCA finds the directions along which the data varies the most, allowing it to compress the data with minimal information loss. The document provides examples of using PCA to reduce the dimensions of image data for compression purposes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 35

    Dimensionality Reduction

    Fereshteh Sadeghi
    CSEP 546
    Motivation

    ● Clustering
    ○ One way to summarize a complex real-valued data point with a single categorical variable
    ● Dimensionality reduction
    ○ Another way to simplify complex high-dimensional data
    ○ Summarize data with a lower dimensional real valued vector
    Motivation

    ● Clustering
    ○ One way to summarize a complex real-valued data point with a single categorical variable
    ● Dimensionality reduction
    ○ Another way to simplify complex high-dimensional data
    ○ Summarize data with a lower dimentional real valued vector

    • Given data points in d dimensions


    • Convert them to data points in r<d dimensions
    • With minimal loss of information
    Data Compression
    Reduce data from
    (inches)

    2D to 1D

    (cm)

    Andrew
    Data Compression
    Reduce data from
    (inches)

    2D to 1D

    (cm)

    Andrew
    Data Compression
    Reduce data from 3D to 2D

    Andrew
    Principal Component Analysis (PCA) problem formulation

    Reduce from 2-dimension to 1-dimension: Find a direction (a vector )


    onto which to project the data so as to minimize the projection error.
    Reduce from n-dimension to k-dimension: Find vectors
    onto which to project the data, so as to minimize the projection error.

    Andrew
    Covariance
    ● Variance and Covariance:
    ○ Measure of the “spread” of a set of points around their center of mass(mean)
    ● Variance:
    ○ Measure of the deviation from the mean for points in one dimension
    ● Covariance:
    ○ Measure of how much each of the dimensions vary from the mean with respect to each other

    • Covariance is measured between two dimensions


    • Covariance sees if there is a relation between two dimensions
    • Covariance between one dimension is the variance
    Positive: Both dimensions increase or decrease Negative: While one increase the other
    together decrease
    Covariance

    ● Used to find relationships between dimensions in high dimensional data sets

    The Sample
    mean
    Eigenvector and Eigenvalue
    Ax = λx
    A: Square Matirx
    λ: Eigenvector or characteristic vector
    X: Eigenvalue or characteristic value
    • The zero vector can not be an
    eigenvector
    • The value zero can be eigenvalue
    Eigenvector and Eigenvalue
    Ax = λx
    A: Square Matirx
    λ: Eigenvector or characteristic vector
    X: Eigenvalue or characteristic value

    Example
    Eigenvector and Eigenvalue
    Ax - λx = 0
    Ax =
    (A – λI)x = 0
    λx
    If we define a new matrix B:
    B=A–
    λI
    Bx = 0 BUT! an
    If B has an x = B-10 = 0 eigenvector cannot
    inverse:
    be zero!!
    x will be an eigenvector of A if and only if B does
    not have an inverse, or equivalently det(B)=0 :
    det(A – λI) = 0
    Eigenvector and Eigenvalue
    Example 1: Find the eigenvalues of

    two eigenvalues: −1, − 2


    Note: The roots of the characteristic equation can be repeated. That is, λ1 = λ2 =…=
    λk. If that happens, the eigenvalue is said to be of multiplicity k.
    Example 2: Find the eigenvalues of

    λ = 2 is an eigenvector of multiplicity 3.
    Principal Component Analysis

    Input
    :
    Set of basis
    vectors:
    Summarize a D dimensional vector X with K dimensional
    feature vector h(x)
    Principal Component Analysis

    Basis vectors are


    orthonormal

    New data representation


    h(x)
    Principal Component Analysis

    New data representation


    h(x)

    Empirical mean of the data


    SIFT feature visualization

    • The top three principal components of SIFT descriptors from a set of images are computed
    • Map these principal components to the principal components of the RGB space
    • pixels with similar colors share similar structures
    Application: Image compression

    Original
    Image

    • Divide the original 372x492 image into patches:


    • Each patch is an instance that contains 12x12 pixels on a grid
    • View each as a 144-D vector
    PCA compression: 144D 🡪 60D
    PCA compression: 144D 🡪 16D
    16 most important eigenvectors
    PCA compression: 144D ) 6D
    6 most important eigenvectors
    PCA compression: 144D 🡪 3D
    3 most important eigenvectors
    PCA compression: 144D 🡪 1D
    60 most important eigenvectors

    Looks like the discrete cosine bases of JPG!...


    2D Discrete Cosine Basis

    http://en.wikipedia.org/wiki/Discrete_cosine_transform
    Dimensionality reduction
    ● PCA (Principal Component Analysis):
    ○ Find projection that maximize the variance
    ● ICA (Independent Component Analysis):
    ○ Very similar to PCA except that it assumes non-Guassian features
    ● Multidimensional Scaling:
    ○ Find projection that best preserves inter-point distances
    ● LDA(Linear Discriminant Analysis):
    ○ Maximizing the component axes for class-separation
    ●…
    ●…

    You might also like