Revision as of 22:09, 6 April 2008 by Srudolph (Talk | contribs)

Parametric Methods

Two applications:

  • Parametric Density Estimation: Using sample data, we estimate probabilities $ P(\omega_i) $, $ p(\vec{X}|\omega_i) \forall i $ etc using estimation methods like MLE_OldKiwi and BPE_OldKiwi. Then from these estimated probabilities (and not true probabilities, which are unknown; only their parametric form was known) we can use Bayes classification rule to build a classifier.
  • Parametric Classifiers_OldKiwi: We find parametric decision boundaries to approximate true decision boundaries between classes. This is very different approach from approximating the probabilities with their estimates, as in previous method.


Example:

Lecture9 parametric decion boundary OldKiwi.JPG .. image:: Lecture9_parametric_decion_boundary.JPG

True decision boundary: $ \{\vec{X}|P(\omega_1|\vec{X})-P(\omega_2|\vec{X})=0\} $ can be approximated by $ \{\vec{X}|g(\vec{X})=0\} $. Note that 'g' is not an estimate of the difference in probabilities as in true decision boundary, but it is just an approximate parametric form for the true decision boundary. Choice of 'g' depends on whether it is analytic, and hence easy to handle computationally.

E.g. 'g' can be a degree-2 polynomial, or it can be a degree-1 polynomial (resulting in a linear classifier).

If 'g' is linear, it can be written as $ g(\vec{X})=\vec{V}\cdot \vec{X}+V_0=(\vec{V},V_0)\cdot (\vec{X},1) $ or $ g(1,\vec{X})=\vec{c}\cdot(1,\vec{X}) $.

Extension of Feature Space: This trick justifies the importance of studying linear classifiers even though they do not occur so often in practice directly. Actually, many non-linear classifiers can be seen as linear.

Example 1: Consider g to be a polynomial parametric form of a classifier in $ \mathbb{R}^2 $.

$ g(x,y)=c_0+c_1x+c_2y+c_3xy+c_4{x}^2+c_5{y}^2 $

Here g is not a linear classifier in $ \mathbb{R}^2 $. Let us define $ \tilde{g}:\mathbb{R}^5 \to \mathbb{R} $

$ \tilde{g}(u_1,u_2,u_3,u_4,u_5)=c_0+c_1u_1+c_2u_2+c_3u_3+c_4u_4+c_5u_5 $

where $ u_1=x; u_2=y; u_3=xy; u_4={x}^2; u_5={y}^2 $. Here we have defined a parametric from of the classifier in extended feature space. This form is linear. Hence "Decision boundary defined by 'g' is linear in extended feature space."

Example 2: Consider another polynomial,


$ g(x)={x}^2+{y}^2-2{y} = {x}^2+{(y-1)}^2 -1 $

This is a circle centred at (0,1):

Circle OldKiwi.jpg

This non-linear function can be transformed into linear function in extended feature space like below.

$ \{ (x, y, x^2, y^2) \mid (0, -2, 1, 1) \cdot (x, y, x^2, y^2) = 0 \} $

Lec9 embedd OldKiwi.jpg

Example 3: 1D example

Jinha 1D Example01 OldKiwi.jpg

As we can see from above figure, decision boundary is not linear (region is not connected). From this, we can construct an extended [feature vector] space.

$ x \rightarrow (x, x^2) \in R^2 $

Jinha 1D Example02 OldKiwi.jpg

This red line (which is a hyperplane in this case) can separate these two classes. This can be expressed as below mathematical form.

$ p(x \mid w_1) \rightarrow p(x, x^2 \mid w_1) $

Taylor Series: If true $ \vec{g} $ is analytic e.g $ g(\vec{X})=\sum_{i=1}^{n}{\lambda}_{i}{e}^{{c}_{i}\vec{x}} $

then, $ g(\vec{x}) $ = Taylor Series --> infinite polynomial in powers

because we can approximate with Taylor polynomial of degree n (i.e as n get higher, approximation gets better)

Poly2 OldKiwi.jpg

However, there are issues on this approach. It gets complex with the increase of the dimension of the [feature vector].

If $ \vec{x} = (x_1, x_2, \cdots, x_d) $

A degree 2 polynomial in $ \vec{x} = (x_1, x_2, \cdots, x_d) $ has $ \frac{1}{2} (d+1) (d+2) \approx d^2 $ monomials

A degree n polynomial in $ \vec{x} = (x_1, x_2, \cdots, x_d) $ has $ \approx d^n $ monomials.

How to find decision hyperplane given training data

In the best of all cases, data is "linearly separable", meaning there exists a vector c such that for all y training data: c * y > 0 if y belongs to class w1. (where * is a dot product) c * y < 0 of u belongs to class w2.

Trick: replace all y's in the training data belonging to class w2 by -y, then look for vector c such that c * y > 0 for all y.

Example: 1D feature space

x->(1,x)=:y

Lecture9 1D yi -yi OldKiwi.JPG

First component is +1 for all of class 1 training data

First component is -1 for all of class 2 training data

Lecture9 1D yi -yi 2 OldKiwi.JPG

Observe: c is not unique

To make $ \vec{c} $ unique, introduce 'margin' b>0 and ask that c be the minimum length vector such that $ \vec{c} \cdot y_{i} \geq b $, for all i

Geometric Interpretation of margin

If $ \vec{c} \cdot y_{i} = b $, then $ \vec{c} $ belongs to hyperplane with normal vector $ y_{i0} $ which is at distance $ \displaystyle \frac{b} {\displaystyle ||y_{i0} ||} $ from the origin.


$ \vec{c} \cdot y_{i} \geq b $, for all i means that $ \vec{c} $ is always at least a distance $ \displaystyle \frac{b} {\displaystyle ||y_{i0} ||} $ from the origin for all i

In general, it is impossible to satisfy $ \vec{c} \cdot y_{i} \geq 0 $, for all i

Perhaps, we could try to minimize number of misclassfied training samples

Let $ J(\vec{c})=\{ y_{i} | \vec{c} \cdot y_{i} \leq 0 \} $ -> Too hard to minimize.

Perceptron_OldKiwi Criterion function

$ J_{p}(\vec{c})=\displaystyle \sum_{y_i, missclassified} (- \vec{c} \cdot y_{i} ) $

Lec9 percept OldKiwi.JPG

Measure how 'far away' you are from bias right. distance from |y_i| to hyperplane defined by |vec_c| is $ ||\vec{y_i} \cdot \frac{\vec{c}}{||\vec{c}||} ||=\frac{1}{|| \vec{c} ||} \vec{y_i} \cdot \vec{c} $

Since $ \vec{c} \cdot \vec{y} $ is proportional to distance from $ y_{i} $ to hyperplane

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett