(Lecture 29, 30– Linear and Logistic Regression; Dimensionality Reduction;

CS460/626 : Natural Language

Processing/Speech, NLP and the Web

(Lecture 29, 30– Linear and Logistic Regression; Dimensionality Reduction;

Principal Component Analysis)

Pushpak Bhattacharyya CSE Dept.,

IIT Bombay

26

and 27

March, 2012

Least Square Method: fitting a line

(following Manning and Schutz, Foundation of Statistical NLP, 1999)

Given set of N points (x

,y

), (x

,y

),…, (x

,y

)

Find a line f(x)=mx+b that best fits the data

m m and b are the parameters to be found and b are the parameters to be found

W: <m, b> is the weight vector

The line that best fits the data is the one that minimizes the sum of squares of the

distances

Values of m and b

Partial differentiation of SS(m,b) wrt b

and m yields respectively

Example

(Manning and Schutz, FSNLP, 1999)

Implication of the “line” fitting

A B

C D

1 2

3

4

O

•1, 2, 3, 4: are the points

•A, B, C, D: are their projections on the fitted line

•Suppose 1, 2 form a class and 3, 4 another class

•Of course, it is easy to set up a hyper plane that will separate 1 and 2 from 3 and 4

•That will be classification in 2 dimension

•But suppose we form another attribute of these points, viz., distances of their

•projections On the line from “O”

•Then the points can be classified by a threshold on these distances

•This effectively is classification in the reduced dimension (1 dimension)

Dimensionality Reduction

- is the process of reducing the number of Attributes

- reducing does not mean discarding, but to combine attributes to form new attributes

-Let <p_i, q_i> be the points on 2-dim plane. There are TWO attributes of each point

-If we take the projection of these points on the best fitting line and CHARACTERISE them based on their distance from a specified pt on the line, the dimensionality has been reduced

Y X Class D(x,y,O) Class

f(p ,q ,m,c) 1

q₁ p₁ 1

q2 p2 2

q₃ p₃ 2

… … …

q_n p_n 1

f(p₁,q₁,m,c) 1 f(p₂,q₂,m,c) 2 f(p₃,q₃,m,c) 2

… …

f(p_n,q_n,m,c) 1 Systematic Approach to Dimensionality Reduction

• Principal Component Analysis

• Singular Value Decomposition

•Latent Semantic Analysis (Latent Semantic Indexing)

When the dimensionality is more than 2

Let X be the input vectors: M X N (M input vectors with N features)

Yj=w ₀ +w ₁ .x _j1 +w ₂ .x _j2 +w ₃ .x _j3 +…+w _n .x _jn

find the weight vector W:<w , w , w ,

find the weight vector W:<w ₀ , w ₁ , w ₂ , w ₃ , …, w _n >

It can be shown that

The multivariate data

f ₁ f ₂ f ₃ f ₄ f ₅ … f _n

x ₁₁ x ₁₂ x ₁₃ x ₁₄ x ₁₅ … x _1n y ₁

x ₂₁ x ₂₂ x ₂₃ x ₂₄ x ₂₅ … x _2n y ₂

x x x x x … x y

x ₃₁ x ₃₂ x ₃₃ x ₃₄ x ₃₅ … x _3n y ₃ x ₄₁ x ₄₂ x ₄₃ x ₄₄ x ₄₅ … x _4n y ₄

…

x _m1 x _m2 x _m3 x _m4 x _m5 … x _mn y _m

Logistic Regression

Linear regression: predicting a real- valued outcome

Classification: Output takes a value from a small set of discrete values from a small set of discrete values

Simplest classification: Two classes (0/1 or true/false)

Predict the class and also give the

probability of belongingness to the

class

Linear to logistic regression

P(y=true |x)= Σ _i=0,n w _i f _i = w.f

But, not a legal probability value! Value from –∞ to +∞

Predict the ratio of the probability of being in the class to the probability of not being in the class to the probability of not being in the class

Odds Ratio:

If an event has probability 0.75 of occurring and

probability 0.25 of not occurring, we say the odds

of occurring is 0.75/0.25 = 3.

Odds Ratio (following Jurafski and Martin, Speech and NLP, 2009)

Ratio of probabilities can lie between 0 and ∞. But the RHS is between Ratio of probabilities can lie between 0 and ∞. But the RHS is between -∞ and + ∞.

Introduce log. Then get the expression for p(y=true|x)

Logistic function for p(y=true|x)

The form of p(.)= is called the logistic function

It maps values from –∞ to +∞ to lie

It maps values from –∞ to +∞ to lie

between 0 and 1

Classification using logistic regression

For belonging to the true class

This gives

In other words, Equivalent to placing a

Hyperplane to separate the Two classes

Learning in logistic regression

In linear regression we used minimizing the sum square error (SSE)

In Logistic regression, we use maximum likelihood estimation

Choose the weights such that the

Choose the weights such that the conditional probability p(y|x) is

maximized

Steps of learning w

For a particular <x,y>

For all <x,y> pairs

Working with log

Substituting the values of Ps This can be converted to

Principal Component Analysis

Example: IRIS Data (only 3 values out of 150)

ID Petal

Length (a

)

Petal Width (a

)

Sepal Length (a

)

Sepal Width (a

)

Classific ation

001 5.1 3.5 1.4 0.2 Iris-

001 5.1 3.5 1.4 0.2 Iris-

setosa

051 7.0 3.2 4.7 1.4, Iris-

versicol or

101 6.3 3.3 6.0 2.5 Iris-

virginica

Training and Testing Data

Training: 80% of the data; 40 from each class: total 120

Testing: Remaining 30

Do we have to consider all the 4 attributes for

Do we have to consider all the 4 attributes for classification?

Less attributes is likely increase the generalization

performance (Occam Razor Hypothesis: A simpler

hypothesis generalizes better)

The multivariate data

X ₁ X ₂ X ₃ X ₄ X ₅ … X _p

x ₁₁ x ₁₂ x ₁₃ x ₁₄ x ₁₅ … x _1p

x x x x x … x

x ₂₁ x ₂₂ x ₂₃ x ₂₄ x ₂₅ … x _2p x ₃₁ x ₃₂ x ₃₃ x ₃₄ x ₃₅ … x _3p x ₄₁ x ₄₂ x ₄₃ x ₄₄ x ₄₅ … x _4p

…

…

x _n1 x _n2 x _n3 x _n4 x _n5 … x _np

Some preliminaries

Sample mean vector: <µ

, µ

, µ

,…, µ

>

For the i

variable: µ

= (Σ

x

)/n

Variance for the i

variable:

σ = [Σ (x - µ ) ]/ [n-1]

σ

= [Σ

(x

- µ

)

]/ [n-1]

Sample covariance:

c

= [Σ

((x

- µ

)(x

- µ

))]/ [n-1]

This measures the correlation in the data In fact, the correlation coefficient

r

= c

/ σ

σ

Standardize the variables

For each variable x

Replace the values by

y

= (x

- µ

)/σ

Correlation Matrix

 

 







 

 







=

1 1

1

3 2

1

2 23

21

1 13

12

L M

L K

p p

p

p p

r r

r

r r

r

r r

r

R

Short digression: Eigenvalues and Eigenvectors

AX=λX

a

x

+ a

x

+ a

x

+ … a

x

=λx

a x + a x + a x + … a x =λx a

x

+ a

x

+ a

x

+ … a

x

=λx

…

…

a

x

+ a

x

+ a

x

+ … a

x

=λx

Here, λs are eigenvalues and the solution

<x

, x

, x

,… x

>

For each λ is the eigenvector

Short digression: To find the Eigenvalues and Eigenvectors

Solve the characteristic function det(A – λI)=0

Example:

-9 4 7 -6

Verify:

-9 4 -1 -1

= -13

Characteristic equation (-9-λ)(-6- λ)-28=0 Real eigenvalues: -13, -2 Eigenvector of eigenvalue -13:

(-1, 1)

Eigenvector of eigenvalue -2:

(4, 7)

= -13 7 -6 1 1

λ 0 I=

0 λ

Next step in finding the PCs

 

 

 

 

 

 

=

1 1

1

2 23

21

1 13

12

L M

L K

p p

r r

r

r r

r

r r

r R

 

 





L 1

p p

p

r r

r

Find the eigenvalues and eigenvectors of R

Example

49 birds: 21 survived in a storm and 28 died.

5 body characteristics given

X1: body length; X2: alar extent; X3: beak and head length X₄: humerus length; X₅: keel length

Could we have predicted the fate from the body charateristic

 

 

 





 

 

 





=

000 .

1 607 .

0 526 .

0 529 .

0 605 .

0

000 .

1 763 .

0 769 .

0 645 .

0

000 .

1 674 .

0 662 .

0

000 .

1 735 .

0

000 .

1

R

Eigenvalues and Eigenvectors of R

Component Eigen value

First Eigen- vector: V₁

V₂ V₃ V₄ V₅

1 3.612 0.452 0.462 0.451 0.471 0.398

2 0.532 -0.051 0.300 0.325 0.185 -0.877

2 0.532 -0.051 0.300 0.325 0.185 -0.877

3 0.386 0.691 0.341 -0.455 -0.411 -0.179

4 0.302 -0.420 0.548 -0.606 0.388 0.069

5 0.165 0.374 -0.530 -0.343 0.652 -0.192

Which principal components are important?

Total variance in the data=

λ ₁ + λ ₂ + λ ₃ + λ ₄ + λ ₅

= sum of diagonals of R= 5

First eigenvalue= 3.616 ≈ 72% of total

First eigenvalue= 3.616 ≈ 72% of total variance 5

Second ≈ 10.6%, Third ≈ 7.7%, Fourth

≈ 6.0% and Fifth ≈ 3.3%

First PC is the most important and sufficient for studying the

classification

Forming the PCs

Z

= 0.452X

+0.462X

+0.451X

+0.471X

+0.398X

Z

= -0.051X

+0.300X

+0.325X

+0.185X

-0.877X

For all the 49 birds find the first two For all the 49 birds find the first two principal components

This becomes the new data

Classify using them

For the first bird

X

=156, X

=245, X

=31.6, X

=18.5, X

=20.5 After standardizing

Y

=(156-157.98)/3.65=-0.54, Y

=(245-241.33)/5.1=0.73, Y =(31.6-31.5)/0.8=0.17, Y

=(31.6-31.5)/0.8=0.17, Y

=(18.5-18.46)/0.56=0.05, Y

=(20.5-20.8)/0.99=-0.33 PC

for the first bird=

Z

= 0.45X(-0.54)+

0.46X(0.725)+0.45X(0.17)+0.47X(0.05)+0.39X(-0.33)

=0.064

Similarly, Z

= 0.602

Reduced Classification Data

Instead of X

X

X

X

X

49

Use

49 rows

Z

Z

49 rows