Fully Understanding the Hashing Trick

Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen

Publikation: KonferencebidragPosterForskningpeer review

20 Citationer (Scopus)
62 Downloads (Pure)

Abstract

Feature hashing, also known as the hashing trick, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix A : R n → R m (where m n) in order to reduce the dimension of the data from n to m while approximately preserving the Euclidean norm. Every column of A contains exactly one non-zero entry, equals to either −1 or 1. Weinberger et al. showed tail bounds on kAxk 2 2. Specifically they showed that for every ε, δ, if kxk /kxk 2 is sufficiently small, and m is sufficiently large, then Pr[ | kAxk 2 2 − kxk 2 2 | < εkxk 2 2 ] ≥ 1 − δ . These bounds were later extended by Dasgupta et al. (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters kxk /kxk 2, m, ε, δ remained an open question. We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants “hiding” in the asymptotic notation are, in fact, very close to 1, thus further illustrating the tightness of the presented bounds in practice.

OriginalsprogEngelsk
Publikationsdatonov. 2018
Antal sider1
StatusUdgivet - nov. 2018
BegivenhedNeural Information Processing Systems Conference - Montreal, Canada
Varighed: 2 dec. 20188 dec. 2018
Konferencens nummer: 32
https://nips.cc/

Konference

KonferenceNeural Information Processing Systems Conference
Nummer32
Land/OmrådeCanada
ByMontreal
Periode02/12/201808/12/2018
Internetadresse

Fingeraftryk

Dyk ned i forskningsemnerne om 'Fully Understanding the Hashing Trick'. Sammen danner de et unikt fingeraftryk.

Citationsformater