Integer Programming Problem Formulation Essay Example for Free

Integer Programming Problem Formulation Essay This approach is advantageous compared to SVMs with Gaussian kernels in that it provides a natural construction of kernel matrices and it directly minimizes the number of basis functions. Traditional approaches for data classi? cation , that are based on partitioning the data sets into two groups, perform poorly for multi-class data classi? ca- tion problems. The proposed approach is based on the use of hyper-boxes for de? ning boundaries of the classes that include all or some of the points in that set. A mixed-integer programming model is developed  ¤Computer Scientist, Defence RD Org. , Min of Defence, Delhi-110054. email:[emailprotected] drdo. in, dhamija. [emailprotected] com, a k [emailprotected] com. Home- page:www. geocities. com/a k dhamija/ for representing existence of hyper-boxes and their boundaries. In addition, the relationships among the discrete decisions in the model are represented using propositional logic and then converted to their equivalent integer constraints using Boolean algebra. Image Contrast Enhancement and Image Recon- struction are being used for extracting knowledge from satellite images of the battle? ld or other terrains. This method has already been described in LP problem formulation in I semester assignment. Keywords: Integer linear Programming ,Pattern Classi? cation ,Multi Class data classi? cation , Image Reconstruction ,radial basis function (RBF) classi? ers , sigmoid function , SVM , Kernel and propositional logic 1 Pattern Classification Via Integer linear Programming Given the space in which objects to be classi? ed are represented, a classi? er partitions the space into dis- joint regions and associates them with di ®erent classes. If the underlying distribution is known, an optimal artition of the space can be obtained according to the Bayes decision rule. In practice, however, the underlying distribution is rarely known, and a learning algorithm has to generate a partition that is close to the optimal partition from the training data. The RCE network (1) is a learning algorithm that constructs a set of regions, e. g. , spheres, to represent each pattern class. It is easy to see that, with only a few spheres, there is a great chance that the training error will be high. With an excessively large number of spheres, however, the training error can be reduced, but at the expense of over? ting the data and degrading the performance on future data. Similar problems also exist in the radial basis function (RBF) networks and multi-layer sigmoid function networks. Therefore, a good learning algorithm has to strike a delicate balance between the training error and the complexity of the model. Existing Methods Used Various existing methods like Simulated Annealing , Neural Networks , Genetic algorithms and other classi- ?cation methods of supervised as well as unsupervised learning are being used. 1. 2 Proposed Method : ILP Problem Formulation Given a set of training examples, the minimum sphere overing approach seeks to construct a minimum num- ber of spheres (3) to cover the training examples cor- rectly. Let us denote the set of training examples by D = f(x1; y1); :::; (xn; yn)g where xi 2 Rd and yi 2 f? 1; 1g: For notational simplicity, we only consider the binary classi? cation problem. The task is to ? nd a set of class-speci? c spheres S = S1; :::; Sm such that xi 2 [ y(Sj)=yi Sj and xi =2 [ y(Sj )6=yi Sj ; 8i = 1; :::; n (1) where each sphere Si is characterized by its center c(Si), its radius r(Si) and its class y(Si). An exam- ple xi is covered by a sphere Sj , i. e. , xi 2 Sj , if d(xi; c(Sj))  · r(Sj ). A set of spheres S that satis? es the conditions in Eqn. (1) is called a consistent sphere cover of the data D. A sphere cover is minimal if there exists no other consis- tent sphere cover with a smaller number of spheres. We restrict ourselves to constructing a consistent sphere cover with spheres that are centered on training ex- amples, although in general spheres do not have to be centered on the training examples. In order to mini- mize the number of spheres in the sphere cover S, each sphere in S should cover as many training examples as possible without covering a training example belonging to a di ®erent class.