A simplex-cut method for nearest facets in Minkowski polytopes

Simple item page
dc.contributor.advisorBremner, David
dc.contributor.authorGao, Zhan
dc.date.accessioned2023-03-01T16:49:27Z
dc.date.available2023-03-01T16:49:27Z
dc.date.issued2014
dc.date.updated2016-11-01T00:00:00Z
dc.description.abstractThe Support Vector Machine algorithms are well known machine learning algorithms focused on classification and regression. The main idea of an SVM problem is to find a function to separate two data sets with a maximum margin. In this thesis, we focus on solving the linear SVM problem where the training sets cannot be separated by a linear function. We follow Cui’s thesis [6] which converts the problem into a Minkowski Norm Minimization problem. We first introduce the basic formulation of SVM problem and some theory. We also briefly introduce Cui’s geometric framework and show how the SVM problem can be view geometrically. In order to solve the Minkowski Norm Minimization problem, we propose to algorithms two trim the polytope. The implementation uses lrs [1] for enumeration and cdd [8] for linear programming; gmplib [7] is used for multi-precision calculation. The results of the experiments show that our methods have better performance than brute-force enumeration and that the cutting polytope method has better performance than cutting planes.
dc.description.copyrightNot available for use outside of the University of New Brunswick
dc.description.noteElectronic Only. (UNB thesis number) Thesis 9389. (OCoLC) 961810521.
dc.description.noteM.C.S., University of New Brunswick, Faculty of Computer Science, 2014.
dc.formattext/xml
dc.format.extentix, 66 pages
dc.format.mediumelectronic
dc.identifier.oclc(OCoLC) 961810521.
dc.identifier.otherThesis 9389
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/14531
dc.language.isoen_CA
dc.publisherUniversity of New Brunswick
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.subject.lcshSupport vector machines.
dc.subject.lcshAlgorithms.
dc.subject.lcshMinkowski geometry.
dc.titleA simplex-cut method for nearest facets in Minkowski polytopes
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.fullnameMaster of Computer Science
thesis.degree.grantorUniversity of New Brunswick
thesis.degree.levelmasters
thesis.degree.nameM.C.S.

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
item.pdf
Size:
1.13 MB
Format:
Adobe Portable Document Format
Download

Collections

Open Theses & Dissertations