# Linear Discriminant Functions
Linear Discriminant Functions distinguish (in the simple case) two different classes from each other (assuming they are linear seperable). For the twodimensional case (N = 2), we want to find a line $d(x) = w_1x_1+w_2x_2+w_3 = 0$ which outputs a value $>0$ for the first class and a value $<0$ for the second class. If the value is 0 (and thus the point lies on the decision line), we reject the decision*. 

The goal is to learn the weights ($w_1$ and $w_2$) as well as the bias to discriminate the two classes. There are many algorithms to achieve this. In the lecture by Prof. Jiang two different approaches were shown: The perceptron algorithm and the pseudoinverse algorithm. 

## Perceptron Algorithm
The perceptron algorithm minimizes the number of misclassified training examples by using the gradient descend approach. This is done by using the model of a perceptron which has (in the twodimensional case) two inputs and a bias. The output of the perceptron is the sum of the inputs combined with some weights which need to be learned. For learning we use our initial solution and compute for every training example the output of the neuron. Every misclassified sample causes a slight change to the weights until no misclassification happens.

$$
\begin{align}
J(w) &= \sum_{y \in \text{misclassified examples}}(-wy^t)\\
\nabla J(w) &= \sum_{y \in \text{misclassified examples}}(-y)\\
w_{k+1} &= w_k - \sum_{y \in \text{misclassified examples}}(-y)\\
w_{k+1} &= w_k + \sum_{y \in \text{misclassified examples}}(y)
\end{align}
$$

#### Example
Consider the following data (I already added the bias)

| x | y | bias | class  | $d(w)$ shall be... |
|---|---|------|--------|--------------------|
| 0 | 0 | 1    |  $C_1$ | $>0$               |
| 0 | 1 | 1    | $C_1$  | $>0$               |
| 1 | 0 | 1    | $C_2$  | $<0$               |
| 1 | 1 | 1    | $C_2$  | $<0$               |

For simplicity reasons we multiply the values of the second class * -1 so we get

| x  | y  | bias | class  | $d(w)$ shall be... |
|----|----|------|--------|--------------------|
| 0  | 0  | 1    |  $C_1$ | $>0$               |
| 0  | 1  | 1    | $C_1$  | $>0$               |
| -1 | 0  | -1   | $C_2$  | $>0$               |
| -1 | -1 | -1   | $C_2$  | $>0$               |

Let's imagine we initialize with $w_0 = (0,0,0)$. Now we can find out if an example is correctly classified or not, by multiplying the sample with the weight.

| x  | y  | bias | class  | $d(w)$ shall be... | $d(w_0)$ is be... |
|----|----|------|--------|--------------------|-----------------|
| 0  | 0  | 1    |  $C_1$ | $>0$               | $\leq 0$        |
| 0  | 1  | 1    | $C_1$  | $>0$               | $\leq 0$        |
| -1 | 0  | -1   | $C_2$  | $>0$               | $\leq 0$        |
| -1 | -1 | -1   | $C_2$  | $>0$               | $\leq 0$        |

As we can see, all four values are misclassified. Thus we can sum up all x's and y's and biases and we get as a $\delta_0 = (-2,0,0)$. Now we calculate $w_1 = w_0 + p * \delta_0 = (0,0,0) + 1*(-2,0,0) = (-2,0,0)$, assuming a learning rate $p$ of $1$.

For the second iteration we use the new weight and get...


| x  | y  | bias | class  | $d(w)$ shall be... | $d(w_1)$ is be... |
|----|----|------|--------|--------------------|-------------------|
| 0  | 0  | 1    |  $C_1$ | $>0$               | $\leq 0$          |
| 0  | 1  | 1    | $C_1$  | $>0$               | $\leq 0$          |
| -1 | 0  | -1   | $C_2$  | $>0$               | $> 0$             |
| -1 | -1 | -1   | $C_2$  | $>0$               | $> 0$             |

Now there are only two misclassified examples (the first and the second one). If we now add up the two misclassified examples, we get $\delta_1=(0,0,1)+(0,1,1)=(0,1,2)$. Secondly, we get $w_2 = w_1 + p * \delta_1 = (-2,0,0) + 1 * (0,1,2) = (-2,1,2)$. The algorithm continues until it converges to $(-4,1,2)$.

## Pseudoinverse Algorithm
The pseudoinverse algorithm works by introducing a vector $b$, so that
$$
wX = b
$$
with $b$ having positive values. Thus, we replace the requirement to be greater than zero with concrete values.

$X$ is a matrix with the trainingsdata, i.e.

$$
X=
  \begin{pmatrix}
    0 & 0 & -1 & -1 \\
    0 & 1 & 0 & -1 \\
    1 & 1 & -1 & -1
  \end{pmatrix}
$$

In this case the first column corresponds to the first example, the second to the second example etc. The third and the forth example are again multiplied with -1 since they belong to class 2 (just as before).

To calculate the corresponding $w$ we need to have the inverse of $X$, however there is no exact solution, so instead we calculate.

$$
w = bX^t(XX^t)^{-1}
$$

The challenge here is to determine a suitable b. You might need mulitple trials or another optimization strategy for b.

# Code-Part
### Perceptron Algorithm


```python
# First we import the required packages

import numpy as np

import matplotlib.pyplot as plt
from matplotlib import animation, rc

from IPython.display import HTML

from numpy.linalg import inv # For pseudoinverse algorithm
```

Now we set the data and the learning rate.


```python
# Two classes
c1 = np.array([[0,0],[0,1]])
c2 = np.array([[1,0],[1,1]])
learning_rate = 1

# Assertion check, some kind of input validation
assert c1[0].shape == c2[0].shape
```

Now we ...
* initialize the weights vector w with (0,0,0)
* add the bias terms to the samples
* multiply the samples of class 2 with -1 as explained above.


```python
# Initialize w (i.e. with zeros)
w = np.zeros(c1[0].shape[0] + 1) #+1 for bias

# Add bias-term for classes
_c1 = np.append(c1, np.repeat(1,c1[0].shape[0]).reshape((c1[0].shape[0], 1)), axis=1)
_c2 = np.append(c2, np.repeat(1,c1[0].shape[0]).reshape((c1[0].shape[0], 1)), axis=1)

# Multiply _c2*-1 so we can check if > 0 more conveniently
_c2 = _c2*-1
```

Now this is the main loop. The main functionality is described above, not more magic is happening here. We save each weight in weights, so we can visualize the progress of the linear discriminant function later.


```python
# Main loop

weights = [w] # We save the weights, so we can display the line fitting later

while True:
    
    # Test which samples are wrong classified
    wrong_classified = []
    
    for sample in _c1:
        # Calculate the function value (i.e. w0 + w1*x1 + w2*x2 + ...)
        # It is correctly classified if the value is > 0, thus wrongly if it is <= 0
        if sum(sample*w) <= 0:
            wrong_classified.append(sample)
            
    for sample in _c2:
        # Same for _c2
        if sum(sample*w) <= 0:
            wrong_classified.append(sample)
    
    # Break if no samples were wrong classified
    if len(wrong_classified) == 0:
        break
    
    # Otherwise calculate delta
    delta = np.sum(wrong_classified, axis=0)
    
    # Add delta to weight
    w = w + learning_rate*delta
    weights.append(w)
```

This part is just for creating the visualization of the data and the discriminant function. It creates a fancy animation. This works by using the weights which have been previously saved.


```python
fig, ax = plt.subplots()
ax.plot(c1[:,0], c1[:,1], 'ro')
ax.plot(c2[:,0], c2[:,1], 'bo')
line, = ax.plot([], [])

ax.set_xlim(( -2, 2)) # Set x axis here
ax.set_ylim((-2, 2)) # Set y axis here

def init():
    return (line,)

def animate(i):
    x = np.linspace(*ax.get_xlim(), 1000)
    weight = weights[i]
    #w0x1 + w1x2 + w2 = 0
    # w1x2 = -w2 - w0x1
    # x2 = (-w2 -w0*x1) / w1
    if weight[1] == 0: # This would be a divide by zero.
        y = [0] * len(x)
    else:
        y = (-weight[0]*x-weight[2])/weight[1]
    line.set_data(x, y)
    return (line,)

anim = animation.FuncAnimation(fig, animate, init_func=init,
                               frames=len(weights), interval=1000, 
                               blit=True)
HTML(anim.to_jshtml()) # Print the animation
```





<link rel="stylesheet"
href="https://maxcdn.bootstrapcdn.com/font-awesome/4.4.0/
css/font-awesome.min.css">


<div class="animation" align="center">
    
    <br>
    <input id="_anim_slider2b16e4dfcbd3421daf4aa278a03bd82b" type="range" style="width:350px"
           name="points" min="0" max="1" step="1" value="0"
           onchange="anim2b16e4dfcbd3421daf4aa278a03bd82b.set_frame(parseInt(this.value));"></input>
    <br>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.slower()"><i class="fa fa-minus"></i></button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.first_frame()"><i class="fa fa-fast-backward">
        </i></button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.previous_frame()">
        <i class="fa fa-step-backward"></i></button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.reverse_animation()">
        <i class="fa fa-play fa-flip-horizontal"></i></button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.pause_animation()"><i class="fa fa-pause">
        </i></button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.play_animation()"><i class="fa fa-play"></i>
        </button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.next_frame()"><i class="fa fa-step-forward">
        </i></button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.last_frame()"><i class="fa fa-fast-forward">
        </i></button>
    <button onclick="anim2b16e4dfcbd3421daf4aa278a03bd82b.faster()"><i class="fa fa-plus"></i></button>
  <form action="#n" name="_anim_loop_select2b16e4dfcbd3421daf4aa278a03bd82b" class="anim_control">
    <input type="radio" name="state"
           value="once" > Once </input>
    <input type="radio" name="state"
           value="loop" checked> Loop </input>
    <input type="radio" name="state"
           value="reflect" > Reflect </input>
  </form>
</div>







### Pseudoinverse Part
This is the part where we calculate the pseudoinverse. However, we do not optimize b. This is part of other algorithms, i.e. Ho-Kashyap algorithm. Instead, we set $b$ to a vector of ones.


```python
## Define X

#(_c1.shape[0] + _c2.shape[0]) = Number of training examples
X = np.array([_c1,_c2]).reshape((_c1.shape[0] + _c2.shape[0]),3).T
b = np.ones((1,(_c1.shape[0] + _c2.shape[0]))) # Just fill b with ones (one 1 per training example)

# Calculate the w with the pseudoinverse
# We need to use the dotproduct, so we cannot write X*X.T, but i.e.
# np.dot(X,X.T)
w = np.dot(b, np.dot(X.T, inv(np.dot(X,X.T))))

# For simplicity reasons we flatten the matrix to a vector
w = w.flatten()
```

Here we just visualize again


```python
plt.clf()
fig, ax = plt.subplots()
ax.plot(c1[:,0], c1[:,1], 'ro')
ax.plot(c2[:,0], c2[:,1], 'bo')
line, = ax.plot([], [])

ax.set_xlim(( -2, 2)) # Set x axis here
ax.set_ylim((-2, 2)) # Set y axis here

x = np.linspace(*ax.get_xlim(), 1000)
y = (-w[0]*x-w[2])/w[1]
line.set_data(x, y)
plt.show()
```

#### Literature
* Haykin, Simon S., et al. Neural networks and learning machines. Vol. 3. Upper Saddle River, NJ, USA:: Pearson, 2009.
* Duda, Richard O., Peter E. Hart, and David G. Stork. Pattern classification. John Wiley & Sons, 2012.

834b2fc6ac10f63e40c7ec309693944f282c2fc9
ipynb
Jupyter Notebook
Linear Discriminant Functions.ipynb
hija/DeepLearningNotebooks
d95377c95a41369562e13d03b8fb0fcb34900f26
MIT
Linear Discriminant Functions.ipynb
hija/DeepLearningNotebooks
d95377c95a41369562e13d03b8fb0fcb34900f26
MIT
Linear Discriminant Functions.ipynb
hija/DeepLearningNotebooks
d95377c95a41369562e13d03b8fb0fcb34900f26
MIT
Qwen/Qwen-72B
1. YES
2. YES