In the subject of Machine Learning, there is a classical classification model called perceptron, defined as follows:
Assuming we get a set of training samples: D={(x1,y1),(x2,y2),...,(xN,yN)}, with their inputs x∈Rd, and outputs y∈{−1,1}. We will try to find a function
f(x)=sign(∑di=1wi⋅xi+b)=sign(wT⋅x+b) so that f(xi)=yi,i=1,2,...,N.
w,x mentioned above are all d-dimensional vectors, i.e. w=(w1,w2,...,wd), x=(x1,x2,...,xd). To simplify the question, let w0=b, x0=1, then f(x)=sign(∑di=0wi⋅xi)=sign(wT⋅x). Therefore, finding a satisfying function f(x) is equivalent to finding a proper w.
To solve the problem, we have a algorithm, PLA(Popcorn Label Algorithm).
Accoding to PLA, we will randomly generate w.
If f(x)=sign(wT⋅x) fails to give
any element (xi,yi)∈D the right classification, i.e. f(xi)≠yi, then we will replace w with another random vector. We will do this repeatedly until all the samples ∈D are correctly classified.
As a former-JBer, Tom excels in programming and quickly wrote the pseudocode of PLA.
w := a random vector
while true do
flag:=true
for i:=1 to N do
if f(x[ i ]) != y[ i ] then
flag:=false
break
if flag then
break
else
w := a random vector
return w
But Tom found that, in some occasions, PLA will end up into an infinite loop, which confuses him a lot. You are required to help Tom determine, when performed on a given sample set D, if PLA will end up into an infinite loop. Print Infinite loop! if so, or Successful! otherwise.
We only consider cases when d=2 for simplification.
Note: