Skip to main content
Cross Validated

Return to Question

removed a "thanks", and added the perceptron tag
Source Link
edit approved Aug 14, 2018 at 7:17
Oren Milman
edit approved Aug 14, 2018 at 7:17
Oren Milman
  • 1.4k
  • 14
  • 28

I was trying to understand the following result more intuitively (for linearly separable data):

$$ k \leq \frac{R^2}{\gamma_g^2}$$

where:

k = is the number of mistakes the perceptron algorithm does

R = is the distance at which the data points are confined to.

$\gamma_g = \text{the smallest geometric margin for the current data set i.e.} = min_{1 \leq i \leq n}\{ \gamma(i) \}$

$\gamma(i) = \text{the perpendicular geometric distance from the decision boundary for data i .}$

The way I wanted to understand better is, I was thinking of assessing the level of difficulty of a data set according to the margin they could have or the distance from the origin they had. i.e. by the number of mistakes the algorithm could make. i.e. by looking at how big/small each upper bound is different for each training data set.

So for example, I currently think of this result as the following:

if we can achieve a large geometric margin (i.e. if there exists a large geometric margin) then we can have higher confidence of our classifier, thus, for large margins, the denominator for the above result will be larger, which means that the number of mistakes (k) will decrease, which in turn means that, if a higher margin is possible, then the classification task is "easier". Which makes sense, if there exists a decision boundary that can clearly distinguish +'s from -'s then, the classification task should be considered "easier".

However, I was having difficulties coming up with a similar explanation for the numerator. Obviously, the larger the numerator is, from the above equation, the classification task might have more mistakes (so one can consider the task "harder" for the current data set). However, I was not really sure why R has that effect on the number of mistakes nor did I have a good intuition on why R affect the perceptron the way it does.

Thanks in advance! :)

NOTE:

I know the number of mistakes perceptron makes depends on the initialization when it starts cycling. However, that is not what I care about. I care about just arguing the intuition for the number of mistakes soley on the upper bound of the perceptron. How to initilize it is a disscussion for a different quesiton.

I was trying to understand the following result more intuitively (for linearly separable data):

$$ k \leq \frac{R^2}{\gamma_g^2}$$

where:

k = is the number of mistakes the perceptron algorithm does

R = is the distance at which the data points are confined to.

$\gamma_g = \text{the smallest geometric margin for the current data set i.e.} = min_{1 \leq i \leq n}\{ \gamma(i) \}$

$\gamma(i) = \text{the perpendicular geometric distance from the decision boundary for data i .}$

The way I wanted to understand better is, I was thinking of assessing the level of difficulty of a data set according to the margin they could have or the distance from the origin they had. i.e. by the number of mistakes the algorithm could make. i.e. by looking at how big/small each upper bound is different for each training data set.

So for example, I currently think of this result as the following:

if we can achieve a large geometric margin (i.e. if there exists a large geometric margin) then we can have higher confidence of our classifier, thus, for large margins, the denominator for the above result will be larger, which means that the number of mistakes (k) will decrease, which in turn means that, if a higher margin is possible, then the classification task is "easier". Which makes sense, if there exists a decision boundary that can clearly distinguish +'s from -'s then, the classification task should be considered "easier".

However, I was having difficulties coming up with a similar explanation for the numerator. Obviously, the larger the numerator is, from the above equation, the classification task might have more mistakes (so one can consider the task "harder" for the current data set). However, I was not really sure why R has that effect on the number of mistakes nor did I have a good intuition on why R affect the perceptron the way it does.

Thanks in advance! :)

NOTE:

I know the number of mistakes perceptron makes depends on the initialization when it starts cycling. However, that is not what I care about. I care about just arguing the intuition for the number of mistakes soley on the upper bound of the perceptron. How to initilize it is a disscussion for a different quesiton.

I was trying to understand the following result more intuitively (for linearly separable data):

$$ k \leq \frac{R^2}{\gamma_g^2}$$

where:

k = is the number of mistakes the perceptron algorithm does

R = is the distance at which the data points are confined to.

$\gamma_g = \text{the smallest geometric margin for the current data set i.e.} = min_{1 \leq i \leq n}\{ \gamma(i) \}$

$\gamma(i) = \text{the perpendicular geometric distance from the decision boundary for data i .}$

The way I wanted to understand better is, I was thinking of assessing the level of difficulty of a data set according to the margin they could have or the distance from the origin they had. i.e. by the number of mistakes the algorithm could make. i.e. by looking at how big/small each upper bound is different for each training data set.

So for example, I currently think of this result as the following:

if we can achieve a large geometric margin (i.e. if there exists a large geometric margin) then we can have higher confidence of our classifier, thus, for large margins, the denominator for the above result will be larger, which means that the number of mistakes (k) will decrease, which in turn means that, if a higher margin is possible, then the classification task is "easier". Which makes sense, if there exists a decision boundary that can clearly distinguish +'s from -'s then, the classification task should be considered "easier".

However, I was having difficulties coming up with a similar explanation for the numerator. Obviously, the larger the numerator is, from the above equation, the classification task might have more mistakes (so one can consider the task "harder" for the current data set). However, I was not really sure why R has that effect on the number of mistakes nor did I have a good intuition on why R affect the perceptron the way it does.

NOTE:

I know the number of mistakes perceptron makes depends on the initialization when it starts cycling. However, that is not what I care about. I care about just arguing the intuition for the number of mistakes soley on the upper bound of the perceptron. How to initilize it is a disscussion for a different quesiton.

Source Link
Charlie Parker
Charlie Parker
  • 7.1k
  • 14
  • 77
  • 130

Intuition on upper bound of the number of mistakes of the perceptron algorithm and how to classify different data sets as "easier" or "harder"

I was trying to understand the following result more intuitively (for linearly separable data):

$$ k \leq \frac{R^2}{\gamma_g^2}$$

where:

k = is the number of mistakes the perceptron algorithm does

R = is the distance at which the data points are confined to.

$\gamma_g = \text{the smallest geometric margin for the current data set i.e.} = min_{1 \leq i \leq n}\{ \gamma(i) \}$

$\gamma(i) = \text{the perpendicular geometric distance from the decision boundary for data i .}$

The way I wanted to understand better is, I was thinking of assessing the level of difficulty of a data set according to the margin they could have or the distance from the origin they had. i.e. by the number of mistakes the algorithm could make. i.e. by looking at how big/small each upper bound is different for each training data set.

So for example, I currently think of this result as the following:

if we can achieve a large geometric margin (i.e. if there exists a large geometric margin) then we can have higher confidence of our classifier, thus, for large margins, the denominator for the above result will be larger, which means that the number of mistakes (k) will decrease, which in turn means that, if a higher margin is possible, then the classification task is "easier". Which makes sense, if there exists a decision boundary that can clearly distinguish +'s from -'s then, the classification task should be considered "easier".

However, I was having difficulties coming up with a similar explanation for the numerator. Obviously, the larger the numerator is, from the above equation, the classification task might have more mistakes (so one can consider the task "harder" for the current data set). However, I was not really sure why R has that effect on the number of mistakes nor did I have a good intuition on why R affect the perceptron the way it does.

Thanks in advance! :)

NOTE:

I know the number of mistakes perceptron makes depends on the initialization when it starts cycling. However, that is not what I care about. I care about just arguing the intuition for the number of mistakes soley on the upper bound of the perceptron. How to initilize it is a disscussion for a different quesiton.