The Moment-SOS hierarchy for classification based on volume computation

Thời gian: 9h30 thứ Tư ngày 18/10/2023

Địa điểm: Phòng seminar tầng 5 nhà A6, Viện Toán học

Tóm tắt: We rely on the volume computation developed by Dabbene and Henrion to build up a probabilistic Moment-SOS hierarchy for classification. More precisely, we minimize the integral of an unknown polynomial $q$ on a given semialgebraic set $\Omega$, subject to a positivity certificate of $q$ on $\Omega$ and the positivity of $q-1$ on a set of uniformly random samples $(\mathbf X^{(j)})_{j=1}^t$ in a subset $A\subset Omega$. Under mild conditions, the sequence of values returned by this hierarchy converges to the volume of $A$. We also prove that with probability near one, the sequence of polynomials returned by our SOS hierarchy converges to the indicator function $\chi_A$ when the sample size $t$ is sufficiently large. Consequently, with probability near one and a sufficiently large number of uniformly random samples in each class $A_r\subset \Omega$, for almost all points $\mathbf a$ in $\Omega$, we can determine which class $A_r$ the point $\mathbf a$ belongs to under mild conditions. This result is proved using Friedrichs' mollifiers, Weierstrass' theorem, Putinar's Positivstellensatz, and Korda's $\epsilon$ net. This is based on joint work with Jean-Bernard Lasserre, Victor Magron, and Srecko Durasinovic.