# Analysis & Implimentation of the Perceptron Algorithm: Capabilities & Limits

---

## Table of Contents
1. Perceptron Algorithm Introduction & Notation
     - Hypothesis form
     - Hyper-plane definition
2. The actual Algorithm
3. Convergence Theorem with Proof
4. Implimentation in Python
5. Final Notes

<br />

---

## Perceptron Algorithm Introduction & Notation

The Rosenblatt Perceptron Algorithm is an algorithm for supervised learning of a binary classifier. It trains a linear classifier that makes a prediction $ h(x ; \theta, \theta_{0}) $ given a point $x$ and weights $\theta$ and $\theta_0$. Specifically, this prediction is:

<br />

$$ \begin{equation}
h\left(x ; \theta, \theta_{0}\right)=\operatorname{sign}\left(\theta^{\top} x+\theta_{0}\right)=\left\{\begin{array}{ll}
+1 & \text { if } \theta^{\top} x+\theta_{0}>0 \\
-1 & \text { otherwise }
\end{array}\right.
\end{equation} $$

<br />


These weights, $\theta$ and $\theta_{0}$, define a hyper-plane. This hyper-plane then acts as our decision boundry. Think of a hyper-plane as a line in 2D, a plane in 3D, and so on. Technically, this hyper-plane takes the form $\theta_0 + \theta_1x_1 + ... + \theta_dx_d = 0$. This means the vector $<\theta_1, ... , \theta_d>$ is a normal to the hyper-plane pointing in the positive direction. To add a graphical explanation of this: 

<br />



<br />

---

## The Algorithm

Now I have explained the notation and given some intuition about how the Perceptron Algorithm makes hypothesis and how the hyper-plane is defined. The Perceptron Algorithm is as follows: 



<br />

One important note about the Perceptron Algorithm is that if a dataset is linear seperable, then the Perceptron Algorithm will ALWAYS find a $\theta$ and $\theta_0$ seperating the dataset.

---

## Convergence Theorem



This screenshot was taken from: https://phillipi.github.io/6.882/2020/notes/6.036_notes.pdf. The proof to this can be found on page 19 of the linked pdf.






<br />


---

## The Implimentation


```python
# IMPORTS

from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import numpy as np

```


```python
# DEFINING DATA USING SKLEARN BLOBS

# How many data points of dx1 dimensions to train algorithm on
sample_size = 100

X, y = make_blobs(n_samples = sample_size, centers = 2, random_state = 1)
X = np.transpose(np.array(X))
y = np.array(y)

# By default sklearn blobs are classified with {0, 1} but we want {-1, 1} for *already explained reasons*
y[y == 0] = -1

```


```python
# THE PERCEPTRON ALGORITHM 

def perceptron(t, D, y):
    th0s = np.array([0])
    ths = np.array([[0], [0]])

    for t in range(t):
        for i in range(sample_size):
            if (y[i] * (np.dot(D[:, i], ths) + th0s) <= 0):
                ths = ths + np.transpose(np.expand_dims((y[i]) * D[:, i], axis = 0)) 
                th0s = th0s + y[i]

    return ths, th0s

# Calling Perceptron Algorithm
theta1, theta0 = perceptron(10000, X, y)

```


```python
# PLOTTING POINTS

# Green for +1 and Blue for -1
for i in range(sample_size):
    if (y[i] == 1):
        plt.scatter(X[0][i], X[1][i], color="green") 
    else:
        plt.scatter(X[0][i], X[1][i], color="blue")

        
# *CHANGE NAMES* 
x = np.linspace(-10, 10, 10)
hyperplane = ((-1)*(theta1[0][0] / theta1[1][0]) * x) - (theta0[0]/theta1[1][0])

plt.plot(x, hyperplane, '-')

plt.show()

```

<br />

## Final Notes

As you can see the Perceptron Algorithm found a $\theta$ and $\theta_{0}$ that seperates our data. But, becuase the algorithm stops the moment it find a working hyper-plane that seperates our data it often leads to non-margin maximizing hyper-planes. We can clearly see that the line is leaning more towards the blue points when we would like a line more in the middle. This dillema will lead to the foundation for Support Vector Machines (SVM's) which I cover here: https://github.com/ryanirl/ml-basics/blob/main/svm/SVM.ipynb

<br />

<br />

---

Author: Ryan P.

---

<br />



```python

```

51c771eabca9881823040e02daa2e9d20c572dab
ipynb
Jupyter Notebook
perceptron_algorithm/perceptron_algorithm_guide.ipynb
ryanirl/ml-basics
e143eacf6338877d8111d1c0ee56853475efa914
MIT
perceptron_algorithm/perceptron_algorithm_guide.ipynb
ryanirl/ml-basics
e143eacf6338877d8111d1c0ee56853475efa914
MIT
perceptron_algorithm/perceptron_algorithm_guide.ipynb
ryanirl/ml-basics
e143eacf6338877d8111d1c0ee56853475efa914
MIT
Qwen/Qwen-72B
1. YES
2. YES