Updates and Boundaries

When It Stops

A pass with no updates is a finite check on the shown rows. The run-table footer is part of the honesty contract: it only says separation when the final state really separates every displayed row.

highlighted = computed this step

A full pass with no updates

After 3 passes, the last pass through rows 0 through 3 has no updates.

last pass: no updates\text{last pass: no updates}
Stopping checkThe final pass has no updates.Exact perceptron runrule: y*a <= 0 updatestixyold w,bay*aupdnew w,b00(1,0)+1(0,0),000yes(1,0),111(1,1)+1(1,0),122no(1,0),122(0,1)-1(1,0),11-1yes(1,-1),033(-1,0)-1(1,-1),0-11no(1,-1),040(1,0)+1(1,-1),011no(1,-1),051(1,1)+1(1,-1),000yes(2,0),162(0,1)-1(2,0),11-1yes(2,-1),073(-1,0)-1(2,-1),0-22no(2,-1),080(1,0)+1(2,-1),022no(2,-1),091(1,1)+1(2,-1),011no(2,-1),0102(0,1)-1(2,-1),0-11no(2,-1),0113(-1,0)-1(2,-1),0-22no(2,-1),0final w=(2,-1), b=0; separates shown data

Why the footer matters

The footer is recomputed from the final state. It says the state separates shown data only because every displayed margin has the correct sign.

yi(wxi+b)>0 for all shown rowsy_i(w x_i+b)>0\text{ for all shown rows}
Stopping checkThe final pass has no updates.Exact perceptron runrule: y*a <= 0 updatestixyold w,bay*aupdnew w,b00(1,0)+1(0,0),000yes(1,0),111(1,1)+1(1,0),122no(1,0),122(0,1)-1(1,0),11-1yes(1,-1),033(-1,0)-1(1,-1),0-11no(1,-1),040(1,0)+1(1,-1),011no(1,-1),051(1,1)+1(1,-1),000yes(2,0),162(0,1)-1(2,0),11-1yes(2,-1),073(-1,0)-1(2,-1),0-22no(2,-1),080(1,0)+1(2,-1),022no(2,-1),091(1,1)+1(2,-1),011no(2,-1),0102(0,1)-1(2,-1),0-11no(2,-1),0113(-1,0)-1(2,-1),0-22no(2,-1),0final w=(2,-1), b=0; separates shown data

Summary

For this finite run, the final state is w=(2,-1), b=0. A shorter allowed run would render that it does not yet separate.

w=(2,−1),b=0w=(2,-1), b=0
Stopping checkThe final pass has no updates.Exact perceptron runrule: y*a <= 0 updatestixyold w,bay*aupdnew w,b00(1,0)+1(0,0),000yes(1,0),111(1,1)+1(1,0),122no(1,0),122(0,1)-1(1,0),11-1yes(1,-1),033(-1,0)-1(1,-1),0-11no(1,-1),040(1,0)+1(1,-1),011no(1,-1),051(1,1)+1(1,-1),000yes(2,0),162(0,1)-1(2,0),11-1yes(2,-1),073(-1,0)-1(2,-1),0-22no(2,-1),080(1,0)+1(2,-1),022no(2,-1),091(1,1)+1(2,-1),011no(2,-1),0102(0,1)-1(2,-1),0-11no(2,-1),0113(-1,0)-1(2,-1),0-22no(2,-1),0final w=(2,-1), b=0; separates shown data