Self-certified Tuple-Wise Deep Learning

Tuple-wise learning maps a tuple of input points to a label. A typical application is object re-identification, for which empirically successful algorithms have been recently proposed. However, individual tuples do not bring independent information, as their component points participate in multiple tuples. Hence, one may expect needing a larger sample size to learn effectively. To make the most of the available labelled tuples, we turn to the idea of learning with self-certification based on PAC-Bayes bounds. While existing results are not applicable directly to our case, we generalize the self-certified learning paradigm to tuple-wise neural networks, by using U-statistics. The obtained new PAC-Bayes bound confirms the increasing sample complexity for tuple-wise learning as a function of the tuple size. We then conduct an empirical study to evaluate the tuple-wise objective functions obtained from the bound. As an illustrative example, we train the PAC-Bayes posterior distribution of a stochastic neural network using pairwise stochastic gradient descent. Our results demonstrate non-vacuous risk bounds in tuple-wise deep learning on the task of person re-identification (Re-ID), using several real-world datasets.