Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case -- multitask learning with hundreds of thousands of tasks.
Submitted 12 Feb 2009 to Artificial Intelligence
Published 13 Feb 2009
Updated 27 Feb 2010
Author comments: Fixed broken theoremhttp://arxiv.org/abs/0902.2206http://arxiv.org/pdf/0902.2206.pdf