3
$\begingroup$

I am trying to build a simple linear classifier. I have two classes A and B each with two features [x, y] and hence a 2d dataset. Now, I need to find the equation of the line that separates the two classes.

y = $\vec w \vec x - b$

I know exactly what $\vec w$ is. $\vec w$ is vector that is perpendicular to the line that separates the two classes, and b is the bias that shifts the line along $\vec w$. When b is 0, line is exactly at the origin.

I created the algorithm exactly as mentioned in this link. https://en.wikipedia.org/wiki/Perceptron#Learning_algorithm

But, in some cases it doesn't work properly. I've understood intuitively what the algorithm does. At each step, it takes a misclassified point, and tries to make correct classification by rotating the current line segment, and shifting it so that point is more closer to correct class.

I need an algorithm that helps me find $ \vec w $ and $ b $.

Here's my algorithm in ES6.

const learn = (target, learning_rate = .00001) => {
const { featureVector } = target;
// shift towards object
// const nm = math.norm(lineConfig.normal);
// lineConfig.normal = math.divide(lineConfig.normal, nm);
// lineConfig.bias /= nm;
const observedFeatureVector = featureVector.concat(1);
const wc = lineConfig.normal.concat(-lineConfig.bias);
const boundaryValue = math.dot(wc, observedFeatureVector);
const curOutput = boundaryValue >= 0 ? 1 : -1;
// lineConfig.bias += learning_rate * -target.cls;
// [w -b] [x, 1]
const dv = math.multiply(observedFeatureVector, learning_rate * (target.cls - curOutput));
const w = math.add(wc, dv);
lineConfig.bias = -w.pop();
lineConfig.normal = w;

};

I transform my input 2 dimensional data set into 3d by adding 1 [x 1] is our input vector. Then, all we need to do is to find $ \vec w $ only since bias is automatically adjusted. For every misclassification, I add the training point vector to the $ \vec w $ so that classification moves closer to the goal.

My training set is this:

[200, 200, 1]
[227, 347, 1]
[399, 237, 1]
[358, 344, 1]
[265, 263, 1]
[60, 20, -1]
[26, 100, -1]
[126, 95, -1]
[145, 58, -1]
[51, 141, -1]
[49, 186, -1]
$\endgroup$
  • $\begingroup$ you could add the source code of what you've already tried so far $\endgroup$ – nairboon May 14 '19 at 8:16
1
$\begingroup$

But, in some cases it doesn't work properly.

As you did not provide your data, I can only make a bold assumption. The perceptron can only classify linear separably data and will not converge for not-linearly separable data. Thus, this could be a reason for the unintended behaviour.

Cheers!

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have 2d points that I draw. Each points' class is either 1 or -1. The points coordinates can have any range [-inf, inf], but they are also linearly classifiable. Now, I need to find the equation of the line that does that. $\endgroup$ – uttamkhanal May 14 '19 at 8:58
  • $\begingroup$ Also, I'd be happy to see a working implementation for any kind of 2d data. $\endgroup$ – uttamkhanal May 14 '19 at 9:00
  • $\begingroup$ I've added training set to the question. $\endgroup$ – uttamkhanal May 14 '19 at 9:06
0
$\begingroup$

Turns out that my implementation was correct but was taking too long to arrive at the solution because of the large range of input values. So, after I normalized using range normalization, the perceptron algorithm converged pretty fast.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.