A quasi-physical algorithm for solving the linear separation problem in n-dimensional space

Abstract

A quasi-physical algorithm was proposed for solving the linear separation problem of point set in n-dimensional space. The original idea of the quasi-physical algorithm is to find an equivalent physical world for the primitive mathematical problem and to observe the vivid images of the motion of matter in it so as to be inspired to obtain an algorithm for solving the mathematical problem. In this work, the electrostatics with two kinds of matter is found to be the equivalent physical world. As a result, the proposed algorithm is evidently more efficient and robust than the famous LMS algorithm and ETL algorithm. The efficiency of the quasiphysical algorithm is about 10 – 50 times of the LMS algorithm’s for representative instances. A typical Boolean-valued instance shows that it is hard for ETL algorithm but very easy for the quasi-physical algorithm. In this instance, point set A and B is {000, 010, 011, 111} and {001, 100}, respectively.

Keywords

linear separation problem / neural network / algorithm / quasi-physical method / electrostatics

References

[1] WidrowB, WalachE. On the statistical efficiency of the LMS algorithm with nonstationary inputs [J]. IEEE Trans, IT, 1984, 3(2): 211-221

[2] KimJ H, ParkS K. The geometrical learning of binary neural networks [J]. IEEE Transactions on Neural Networks, 1995, 6(1): 237-247

[3] HuangWen-qi. A quasi-physical method for solving the covering problem—an approach to tackling NP-hard problems [J]. Abstracts of Papers Presented to the American Mathematical Society, 1988, 9(3): 275-275

[4] HuangWen-qi, ZhanShu-hao. A quasi-physical method of solving packing problems[J]. Mathematical Reviews of American Mathematical Society, 1982, 82h: 52002-52002

[5] HuangWen-qi, WangGang-qiang. A quasi-mechanical method for solving the rectangle covering problem—an approach to tackling NP-hard problems [J]. Graphical Models and Image Processing, 1994, 56(3): 267-271

[6] HuangWen-qi, ZhanShu-hao. A quasi-physical method for solving the packing problem [J]. Acta Math Appl Sinica, 1979, 2(2): 176-180(in Chinese)

[7] HuangWen-qi. A quasi-physical method for solving the covering problem—an approach to tackling NP-hard problems [J]. Chinese Journal of Computers, 1989, 12(8): 610-616(in Chinese)

[8] LiWei, HuangWen-qi. A mathematic-physical approach to the satisfiability problem [J]. Science in China (series A), 1995, 38(1): 116-128