Description
Title: Optimal Transport for the Naive Bayes Model
Teams link: https://teams.microsoft.com/meet/3151860015933142?p=kS3Gofw97RmLauWmVp
Abstract:
The naïve Bayes model represents a high-dimensional discrete distribution as a mixture of separable measures, that is, as a constrained canonical polyadic decomposition of its probability tensor; this makes estimation feasible, the number of parameters growing linearly rather than exponentially with the dimension $M$. Comparing two such models is a different matter: the $2$-Wasserstein distance between their tensors is a transport problem with $I^M$ sources and as many sinks. We restrict the admissible couplings to mixtures of separable transport plans, which yields the distance $\MSW_2$ computable from the CPD factors alone, at a cost of $O(MR_0R_1I)$ plus a transport problem of size $R_0\times R_1$ independent of $I$ and $M$. We show that $\MSW_2$ is a metric on mixtures of separable measures, that the resulting space is geodesic with an explicit geodesic, and that it exceeds $W_2$ by at most a term controlled by the variances of the components alone. A stability analysis gives the plug-in error from $N$ samples, with the conditioning of each estimation approach appearing explicitly in the constant. The construction is illustrated on flow cytometry data, where the components are cell populations and the transport plan describes how they evolve between acquisitions.
