Cuckoo Feature Hashing: Dynamic Weight Sharing for Sparse Analytics
著者
Abstract
Feature hashing is widely used to process large scale sparse features for learning of predictive mod-els. Collisions inherently happen in the hashing
process and hurt the model performance. In this paper, we develop a new feature hashing scheme called Cuckoo Feature Hashing (CCFH), which
treats feature hashing as a problem of dynamic weight sharing during model training. By lever-aging a set of indicators to dynamically decide the weight of each feature based on alternative hash lo-cations, CCFH effectively prevents the collisions between important features to the model, i.e. pre-dictive features, and thus avoid model performance degradation. Experimental results on prediction tasks with hundred-millions of features demon-strate that CCFH can achieve the same level of per-formance by using only 15%-25% parameters com-pared with conventional feature hashing.
メモ
既存hashing schemeの課題
説明変数が異なる重みを想定されるが同じハッシュバケットにはいり、同じパラメータを共有してしまいパフォーマンスに影響
モデルのスパース性にも影響
予測に効かない変数も予測に効く変数と同じハッシュ化されて重みがゼロで無くなる
多変量ハッシングは衝突による不正確性を減らすためのものだが、モデルのvarianceを増やし、スパース性を損なわせる
オーバーフィッティングやパフォーマンス悪化につながる
Cuckoo Feature Hashingの提案
学習の間、局所的な予測性を考え、衝突を避ける
Cuckoo hashingを用いる
二つのハッシュ関数を、各変数に対して二つの異なる局所性を提供
データの衝突が起きた際には、一方の局所性に移る
提案手法のメリット
ハッシングの構造が損失を減少させるための学習時に適応的
同レベルのパフォーマンスを出すモデルのハッシュテーブルとしては小さくなる
衝突を避けながらスパース性を保つ