Towards PAC Multi-Object Detection and Tracking
  Accurately detecting and tracking multi-objects is important for
safety-critical applications such as autonomous navigation. However, it remains
challenging to provide guarantees on the performance of state-of-the-art
techniques based on deep learning. We consider a strategy known as conformal
prediction, which predicts sets of labels instead of a single label; in the
classification and regression settings, these algorithms can guarantee that the
true label lies within the prediction set with high probability. Building on
these ideas, we propose multi-object detection and tracking algorithms that
come with probably approximately correct (PAC) guarantees. They do so by
constructing both a prediction set around each object detection as well as
around the set of edge transitions; given an object, the detection prediction
set contains its true bounding box with high probability, and the edge
prediction set contains its true transition across frames with high
probability. We empirically demonstrate that our method can detect and track
objects with PAC guarantees on the COCO and MOT-17 datasets.
