Support vector machines with monomial feature maps (part II)

Thời gian: 09h00, thứ năm, ngày 12/10/2023.

Địa điểm: Phòng 507, nhà A6.

Tóm tắt: We prove the theoretical guarantee of the kernel trick for bi-class support vector machine in cases where the feature maps are vectors of monomials. To establish this guarantee, we present a hierarchy of linear systems of increasing sizes that return a sequence of polynomials. Moreover, with probability near one and sufficiently large sizes of linear systems, the resulting polynomials determine algebraic hypersurfaces which separate two disjoint sets with given uniformly random samples.

Next we aim to generalize the result for bi-class support vector machine to handle $s$ classes. This can be achieved by considering a hierarchy of linear systems that grow in size, where the $k$-th system produces a sequence of $s$ polynomials $(p_{k,r})_{r=1}^s$. We also demonstrate that when uniformly random samples are taken from each class, for a sufficiently large $k$, the set of indices $argmaxlimits_{r=1,dots,s} p_{k,r} (mathbf a)$ can accurately determine the class to which a given point $mathbf a$ belongs, with a probability close to one.

This is based on joint work with Jean-Bernard Lasserre, Victor Magron, and Srecko Durasinovic.