  Classification with a large number of classes is a key problem in machine
learning and corresponds to many real-world applications like tagging of images
or textual documents in social networks. If one-vs-all methods usually reach
top performance in this context, these approaches suffer from a high inference
complexity, linear w.r.t the number of categories. Different models based on
the notion of binary codes have been proposed to overcome this limitation,
achieving in a sublinear inference complexity. But they a priori need to decide
which binary code to associate to which category before learning using more or
less complex heuristics. We propose a new end-to-end model which aims at
simultaneously learning to associate binary codes with categories, but also
learning to map inputs to binary codes. This approach called Deep Stochastic
Neural Codes (DSNC) keeps the sublinear inference complexity but do not need
any a priori tuning. Experimental results on different datasets show the
effectiveness of the approach w.r.t baseline methods.
