Dimensionality reduction

Today: Linear

​

Tomorrow: non-linear (t-SNE - Itay)

1

Dimensionality

Suppose we have a dataset of N observations with d attributes.

• Can think of data as N points or vectors in a d dimensional space.

​

Can also say the dimensionality of dataset is d.

​

2

2 dimensions

Dimensionality

Suppose we have a dataset of N observations with d attributes.

• Can think of data as N points or vectors in a d dimensional space.

​

Can also say the dimensionality of dataset is d.

​

3

3 dimensions

2 dimensions

Dimensionality

Consider the data shown.

​

Would you call this dataset:

• 1 dimensional?
• 2 dimensional?

4

? dimensions

Dimensionality

Consider the data shown.

​

Would you call this dataset:

• 1 dimensional?
• Personally I like this answer better.

5

1 dimension

Dimensionality

Consider the data shown.

​

How many dimensions does this data have?

6

? dimensions

Dimensionality

Consider the data shown.

​

How many dimensions does this data have?

• 3 because 2 weight columns are redundant.

In linear algebra terms, we’d observe that this matrix has rank 3.

​

More generally: Can think of a dataset’s dimensionality as the rank of the matrix representing the data.

7

3 dimensions

Note on Rank and Dimensionality

Note that in the dataset below, I’ve added one outlier point.

• Just this one outlier is enough to change the rank of the matrix to 2.
• But intuitively – we can approximate the data very well in 1 dimension

8

Matrix Multiplication Example

Consider the matrix multiplication example below.

• Each row of the fruits matrix represents one bowl of fruit.
• First bowl: 2 apples, 2 lemons, 2 melons.

Number of Fruits

Bowl 1

Bowl 2

# Apples

# Lemons

# Melons

Matrix Multiplication Example

Consider the matrix multiplication example below.

• Each row of the fruits matrix represents one bowl of fruit.
• First bowl: 2 apples, 2 lemons, 2 melons.
• Each column of the dollars matrix represents the cost of fruit at a store.
• First store: 2 dollars for an apple, 1 dollar for a lemon, 4 dollars for a melon.

Number of Fruits

Bowl 1

Bowl 2

Store 1

Store 2

Fruit Costs

# Apples

# Lemons

# Melons

$/Apple

$/Lemon

$/Melon

Matrix Multiplication Example

Consider the matrix multiplication example below.

• Each row of the fruits matrix represents one bowl of fruit.
• First bowl: 2 apples, 2 lemons, 2 melons.
• Each column of the dollars matrix represents the cost of fruit at a store.
• First store: 2 dollars for an apple, 1 dollar for a lemon, 4 dollars for a melon.
• Output is the cost of each bowl at each store.

Number of Fruits

Bowl 1

Bowl 2

Store 1

Store 2

Fruit Costs

# Apples

# Lemons

# Melons

$/Apple

$/Lemon

$/Melon

$/Bowl 1

$/Bowl 2

Matrix Multiplication Example

Consider the matrix multiplication example below.

• Each row of the fruits matrix represents one bowl of fruit.
• First bowl: 2 apples, 2 lemons, 2 melons.
• Each column of the dollars matrix represents the cost of fruit at a store.
• First store: 2 dollars for an apple, 1 dollar for a lemon, 4 dollars for a melon.
• Output is the cost of each bowl at each store.

Number of Fruits

Bowl 1

Bowl 2

Bowl 3

Store 1

Store 2

Fruit Costs

# Apples

# Lemons

# Melons

$/Apple

$/Lemon

$/Melon

$/Bowl 1

$/Bowl 2

$/Bowl 3

View 1: Matrices as Linear Operations

One view of matrix multiplication: Performs multiple linear operations on data.

• Left matrix are the data.
• Right matrix are the operations.

​

We used this view when building linear models.

13

Data

Operation

Bowl 1

Bowl 2

O

peration

(Note: You can also think of left matrix as operations and right as data. Figure not shown!)

View 2: Matrices as Coordinate Transformations

Another view is that matrix multiplication is a coordinate transformation.

• In the original vector space, we have the vector 2i + j + 4k.

• The vector 2i + j + 4k ends up at [14, 18].

• The matrix on the left tells us where i, j, and k “land” after the transformation.
• i ends up at [2, 5]
• j ends up at [2, 8]
• k ends up at [2, 0]

14

For more on this perspective see 3blue1brown.

This transform: From 3D to 2D!

Matrices Have Many Representations

Takeaway: a matrix can be interpreted many different ways. We discussed two today:

• Interpretation used in regression modeling:
• One matrix holds data, the other holds operations.
• Either left or right matrix can be data.
• Another interpretation that we’ll use today!
• One matrix holds coordinates, the other holds a transformation of coordinates.

​

See 3blue1brown’s Essence of Linear Algebra videos for more intuition.

• These videos give a fantastic overview of linear algebra concepts – if you like to refresh (/learn) linear algenra

Interpreting a Matrix Multiplication Operation in Context

Suppose we compute the matrix product below. Interpret the resulting matrix.

• How many rows are there? Columns? What does each row represent? Each column?
• Give your answer in English.

16

x

=

Interpretation of the Results of the Operation

Suppose we compute the matrix product below. Interpret the resulting matrix.

• Each row is an observation.
• Each column is attribute. The 3 attributes of the new matrix are:
• The two original attributes exactly as before.
• One of the original attributes now in a different unit (feet).

x

=

Interpretation of the Matrix Multiplication Process (View 1)

Suppose we compute the matrix product below. Interpret the resulting matrix.

• Provides original data along with new column giving height in different units.

​

Each column of the right matrix represents an operation that computes one column of the output.

18

x

=

Interpretation of the Matrix Multiplication Process (View 2)

Suppose we compute the matrix product below. Interpret the resulting matrix.

• Provides original data along with new column giving height in different units.

​

The right matrix transforms the data from 2D into 3D.

• Each column of right matrix represents a basis vector in the 3D space.

19

x

=

Reminder: Matrix Multiplication in Python

To multiply two matrices in Python, use the @ operator.

​

20

x

=

Matrix Decomposition

Matrix decomposition (a.k.a. Matrix Factorization) is the opposite of matrix multiplication, i.e. taking a matrix and decomposing it into two separate matrices.

• Just like with real numbers, there are infinitely many such decompositions.
• 9.9 = 1.1 * 9 = 3.3 * 3.3 = 1 * 9.9 = …

​

​

21

Matrix Decomposition

Matrix decomposition (a.k.a. Matrix Factorization) is the opposite of matrix multiplication, i.e. taking a matrix and decomposing it into two separate matrices.

• Just like with real numbers, there are infinitely many such decompositions.
• 9.9 = 1.1 * 9 = 2.2 * 4.5 = 3.3 * 3.3 = …
• The size of the two matrices isn’t even unique.
• 3x2 times 2x3 → 3x3

​

​

22

x

Matrix Decomposition

Matrix decomposition (a.k.a. Matrix Factorization) is the opposite of matrix multiplication, i.e. taking a matrix and decomposing it into two separate matrices.

• Just like with real numbers, there are infinitely many such decompositions.
• 9.9 = 1.1 * 9 = 2.2 * 4.5 = 3.3 * 3.3 = …
• The size of the two matrices isn’t even unique.
• 3x2 times 2x3 → 3x3
• 3x3 times 3x3 → 3x3

​

​

23

x

Matrix Decomposition

Matrix decomposition (a.k.a. Matrix Factorization) is the opposite of matrix multiplication, i.e. taking a matrix and decomposing it into two separate matrices.

• Just like with real numbers, there are infinitely many such decompositions.
• 9.9 = 1.1 * 9 = 2.2 * 4.5 = 3.3 * 3.3 = …
• The size of the two matrices isn’t even unique.
• 3x2 times 2x3 → 3x3
• 3x3 times 3x3 → 3x3
• 3x1 times 1x3 → 3x3

​

Why is this impossible?

​

​

24

x

Matrix Decomposition

Matrix decomposition (a.k.a. Matrix Factorization) is the opposite of matrix multiplication, i.e. taking a matrix and decomposing it into two separate matrices.

• Just like with real numbers, there are infinitely many such decompositions.
• 9.9 = 1.1 * 9 = 2.2 * 4.5 = 3.3 * 3.3 = …
• The size of the two matrices isn’t even unique.
• 3x2 times 2x3 → 3x3
• 3x3 times 3x3 → 3x3
• 3x1 times 1x3 → 3x3

​

Why is this impossible? Rank is greater than 1!

25

x

ax/bx = a/b = 182/399

ay/by = a/b = 28/30

Contradiction!

Matrix Decomposition

Matrix decomposition (a.k.a. Matrix Factorization) is the opposite of matrix multiplication, i.e. taking a matrix and decomposing it into two separate matrices.

• Just like with real numbers, there are infinitely many such decompositions.
• 9.9 = 1.1 * 9 = 2.2 * 4.5 = 3.3 * 3.3 = …
• The size of the two matrices isn’t even unique.
• 3x2 times 2x3 → 3x3
• 3x3 times 3x3 → 3x3
• 3x1 times 1x3 → 3x3
• 3x4 times 4x3 → 3x3

26

x

Can go higher than the size of the original matrix. No reason to do this though!

Rank Exercise

You measure the width, length, area, and perimeter of 100 rectangular backyards.

​

What is the rank of the given matrix?

27

...

100 x 4

Rank Exercise

The rank is 3. While area is redundant with width and length, it cannot be computed using linear operations.

​

...

100 x 4

Matrix Decomposition Exercise

You measure the width, length, area, and perimeter of 100 rectangular backyards.

​

Suppose we want to decompose this matrix into two matrices L and R of minimum size.

• What are the dimensions of L and R?

​

​

L: 100 x ??? R: ??? x 4

​

L times R to be 100 x 4

29

...

100 x 4

Matrix Decomposition Exercise

You measure the width, length, area, and perimeter of 100 rectangular backyards.

​

Suppose we want to decompose this matrix into two matrices L and R of minimum size.

• What are the dimensions of L and R?

​

L is 100 x 3, and R is 3 x 4.

30

...

100 x 4

Matrix Decomposition Exercise

You measure the width, length, area, and perimeter of 100 rectangular backyards.

​

Decompose the given matrix into two matrices of minimum size.

• Left matrix should be 100 x 3.
• Right matrix should be 3 x 4.

31

...

100 x 4

Most Natural Answer

Since the rank is three, we should decompose into 100 x 3 and 3 x 4 matrices.

​

There are many possible matrices we could multiply to get back full results.

• The most natural decomposition is given below.

...

...

x

=

100 x 4

100 x 3

3 x 4

Singular Value Decomposition

Singular value decomposition is an important concept in linear algebra.

• Will not explain in its entirety – just the gist for intuition

​

• Will provide an experimental look at how SVD works.
• Will give a better context for what SVD means in the context of data science.
• Will omit a lot of interesting deep theory and rationale.

Redundancy and Decomposition

Earlier, we saw that our rectangle data could be decomposed into two matrices:

• The data without the perimeter.
• A matrix that transforms the data from 3D into 4D, computing the perimeter in the process.

Required manual work on our part to identify the magical transformation matrix.

​

​

​

Interesting observation: Total amount of information stored is less!

34

Transformation matrix

Singular Value Decomposition

The “Singular Value Decomposition” technique will automatically do a similar transformation for us.

35

Same dimensions as the original matrix

Singular Value Decomposition Output

The “Singular Value Decomposition” technique will automatically do a similar transformation for us.

​

What is different about this decomposition from the one you did manually?

36

100 x 4 = 400

100 x 4 + 4 x 4 = 416

m x 4

=

x

UΣ

V^T

Singular Value Decomposition Output (Your Answers)

What is different about this decomposition from the one we did manually?

​

37

100 x 4 = 400

100 x 4 + 4 x 4 = 416

m x 4

=

x

X

UΣ

V^T

SVD Attendance Question

For this data, it is guaranteed that the last column of UΣ is all zeros. Suppose we simply delete it from the matrix. What else can we throw away?

A. First row of V^T. C. Last row of V^T.

B. First column of V^T. D. Last column of V^T.

38

100 x 4 = 400

100 x 4 + 4 x 4 = 416

m x 4

=

x

X

UΣ

V^T

SVD Attendance Question

For this data, it is guaranteed that the last column of UΣ is all zeros. Suppose we simply delete it from the matrix. What else can we throw away?

A. First row of V^T. C. Last row of V^T.

​

39

100 x 4 = 400

100 x 3 + 3 x 4 = 312

m x 3

=

x

X

UΣ

V^T

Matrix Decomposition Summary

Decomposing a MxN matrix X into two matrix factors of size MxQ and QxN does not yield a unique answer.

• The size of the smallest matrices are when Q = the rank R, i.e. MxR and RxN.

​

We manually performed a decomposition where:

• Left matrix was X with redundant columns removed.
• Example: Length, Width, and Perimeter. We removed Perimeter.
• Right matrix represented a transformation from lower dimensional space of left matrix to original dimensionality of X.
• Example: Computes Perimeter as 2 x Length + 2 x Width.

The “Singular Value Decomposition” decomposes X into matrices of size MxN and NxN.

• Left matrix is no longer the original matrix with some columns removed, totally separate.
• Right matrix transforms data from the
• If R < N, the N - R columns will be all zeroes.

40

• Left: “Data” matrix: Three dimensions (instead of four).
• Right: “Transform” matrix: Elevated 3D data matrix up to original 4D matrix.

​

Able to decompose into 100 x 3 and 3 x 4 matrices because rank of 4D matrix was 3.

41

...

100 x 4

??

Last Lecture’s Final Goal: Matrix Decomposition

At the end of last lecture, we did an exercise where I had you decompose the data matrix below into two matrices.

• Left: 100x3 “Data” matrix: Three dimensions (instead of four).
• Right: 3x4 “Transform” matrix: Elevated 3D data matrix up to original 4D matrix.

​

Can factorize (a.k.a. decompose) into infinite number of different matrices. Most natural is:

42

...

x

100 x 3

3 x 4

...

100 x 4

Last Lecture’s Final Goal: Matrix Decomposition

Other factorizations are possible, e.g.

• Leftmost column is W + L
• Middle column is 2W - L
• Right column is area

​

Left matrix can be any linear combination of original columns that allows reconstruction.

43

...

x

100 x 3

3 x 4

...

100 x 4

Desiderata

One possible goal: Find a procedure which can automatically decompose a rank R matrix into an R dimensional representation times some transformation matrix.

• Lower dimensional representation avoids redundant features.
• Imagine a 1000 dimensional dataset: If the rank is only 5, it’s much easier to do EDA after this mystery procedure.

44

...

100 x 4

R x 4

Approximate Factorization

If we go to a two dimensional left matrix, can no longer exactly reconstruct the 4D matrix.

• Rank of the 4D matrix is 3.

​

Still, some 2D matrices yield better approximations than others.

• Find a “reasonable” approximation.

45

...

x

100 x 2

2 x 4

...

100 x 4

≈

Approximate Factorization (My Answer)

There are infinite possible factorization. One intuitive choice (to me) is below.

• Gets area and perimeter perfectly correct.
• Width and length are wrong, but more accurate for squarish rectangles.
• Effectively, my model assumes all rectangles are square.

46

...

x

100 x 2

2 x 4

...

100 x 4

≈

Approximate Factorization (My Answer)

There are infinite possible factorization. One intuitive choice (to me) is below.

• Gets area and perimeter perfectly correct.
• Width and length are wrong, but more accurate for squarish rectangles.
• Effectively, my model assumes all rectangles are square.

47

...

x

100 x 2

2 x 4

...

100 x 4

actual

≈

Approximate Factorization Exercise That We Won’t Do!

If we go to a one dimensional left matrix, can no longer exactly reconstruct the 4D matrix.

• Rank of the 4D matrix is 3.

​

Still, some 1D matrices yield better approximations than others.

• Find a “reasonable” approximation. Let’s not actually try this by hand in lecture, but feel free to do so if you’re watching webcast.

48

...

x

100 x 1

1 x 4

...

100 x 4

≈

Desiderata

Revised goal: Find a procedure which automatically decomposes a matrix into a P dimensional representation times some transformation matrix.

• Here P is a free choice.
• Representation should be the “best” one.
• If P is at least the rank of the matrix, reconstruction should be perfect.

Our tool for this purpose will be “Singular Value Decomposition”.

49

...

100 x 4

P x 4

= or ≈

= when P ≥ R

≈ when P < R

​

Singular Value Decomposition

Singular Value Decomposition

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices:

• Left matrix UΣ will always be same dimensionality as the original data.
• Right matrix V^T will transform UΣ back into X.

51

m x 4

=

x

X

UΣ

100 x 4 = 400

...

Singular Value Decomposition Output

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

What do you notice about the left matrix?

52

=

x

UΣ

V^T

...

100 x 4

4 x 4

X

...

Singular Value Decomposition Output (Your Answer)

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices. What do you notice about the left matrix?

• Obviously last column is all zeroes.
• Other columns are mysterious.

53

=

x

V^T

...

100 x 4

4 x 4

X

...

UΣ

Singular Value Decomposition Output

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

Suppose we wanted a 3 dimensional decomposition, what would we do to UΣ and V^T?

​

54

=

x

V^T

...

100 x 4

4 x 4

X

...

UΣ

Singular Value Decomposition Output (My Answer)

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

Suppose we wanted a 3 dimensional decomposition, what would we do to UΣ and V^T?

• Eliminate last column of UΣ and last row of V^T.

55

=

x

First 3 rows of V^T

...

100 x 3

3 x 4

First 3 Columns of UΣ

X

...

Singular Value Decomposition Output

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

Suppose we wanted a 2 dimensional decomposition, what would we do to UΣ and V^T?

• Anybody want to guess? You don’t have enough info to make a confident answer, but make a suggestion.

56

=

x

...

First 3 rows of V^T

X

...

First 3 Columns of UΣ

Singular Value Decomposition Output (Your Answer)

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

Suppose we wanted a 2 dimensional decomposition, what would we do to UΣ and V^T?

• Drop another column.

57

=

x

...

First 3 columns of UΣ

First 3 rows of V^T

X

...

Singular Value Decomposition Output (My Answer)

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

Suppose we wanted a 2 dimensional decomposition, what would we do to UΣ and V^T?

• Use only the first 2 columns of UΣ and first 2 rows of V.

58

=

x

...

First 2 columns of UΣ

First 2 rows of V^T

X

...

Singular Value Decomposition Output

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

If we multiply the first 2 columns of UΣ by the first 2 rows of V^T will the reconstruction be perfect?

• In other words should the = be an ≈?

​

59

=

x

...

First 2 rows of V^T

X

...

First 2 columns of UΣ

Singular Value Decomposition Output

The “Singular Value Decomposition” automatically decomposes a matrix into two matrices.

​

If we multiply the first 2 columns of UΣ by the first 2 rows of V^T will the reconstruction be perfect?

• No! No matter what magic singular value decomposition uses, it still follows the laws of linear algebra. Since 2 < rank(X), the reconstruction cannot be perfect.

​

60

≈

x

...

First 2 rows of V^T

X

...

First 2 columns of UΣ

Multiplying Out the Result

We can multiply out UΣV^T and see how close the result is to our original matrix X.

• Rank 2 approximation: generally pretty good!

61

≈

x

...

First 2 rows of V^T

...

X

...

Note: If you try to carry out this matrix multiplication by hand, you’ll get different results because I had to round off the entries in UΣ and V^T so they’d fit on the slide.

​

First 2 columns of UΣ

Going Down to One Dimension

If we go all the way down to one dimension for UΣ, the results are better than you might expect.

• Rank 1 approximation: not totally bad!

62

≈

x

...

First column of UΣ

First row of V^T

X

...

Note: If you try to carry out this matrix multiplication by hand, you’ll get different results because I had to round off the entries in UΣ and V^T so they’d fit on the slide.

​

...

Going Down to One Dimension

If we go all the way down to one dimension for UΣ, the results are better than you might expect.

• Notice any patterns in the 1D approximation?

63

≈

x

...

First column of UΣ

First row of V^T

...

X

...

Going Down to One Dimension (Your Answer)

If we go all the way down to one dimension for UΣ, the results are better than you might expect.

• Notice any patterns in the 1D approximation?

64

≈

x

...

First column of UΣ

First row of V^T

...

X

...

Matrix Decomposition Summary

Decomposing a MxN matrix X into two matrix factors of size MxQ and QxN does not yield a unique answer.

• The size of the smallest matrices are when Q = the rank R, i.e. MxR and RxN.

​

We manually performed a decomposition where:

• Left matrix was X with redundant columns removed.
• Example: Length, Width, and Perimeter. We removed Perimeter.
• Right matrix represented a transformation from lower dimensional space of left matrix to original dimensionality of X.
• Example: Computes Perimeter as 2 x Length + 2 x Width.

The “Singular Value Decomposition” decomposes X into matrices of size MxN and NxN.

• Left matrix is no longer the original matrix with some columns removed, totally separate.
• If R < N, the N - R columns will be all zeroes.
• How to interpret the matrices returned by singular value decomposition?

65

Manual Decomposition

Before, we took our data and manually created a 3D to 4D transformation matrix.

​

Decomposed data into:

• Truncated data.
• Transformation matrix.

66

...

...

x

=

Transformation matrix

Singular Value Decomposition

Then we used SVD which automatically created a 3D to 4D transformation matrix.

​

Decomposed data into:

• Mysteriously rescaled data UΣ.
• Different transformation matrix V^T.

67

...

...

x

=

V^T

UΣ

Singular Value Decomposition

The truth about UΣ and V^T:

• Σ is a diagonal matrix. Contains the so-called “singular values” of X.
• The columns of U and V are each an orthonormal set.

​

Let’s define these bolded terms.

68

...