特徴ハッシング（フィーチャーハッシング）は、ハッシングトリックとも呼ばれ、機械学習において高次元でスパースなカテゴリ特徴を、コンパクトで固定サイズのベクトル表現に変換するための手法である。各特徴名（またはトークン）にハッシュ関数を適用して出力ベクトル内のインデックスを決定し、任意で2つ目のハッシュ関数を用いて寄与の符号を決定する。この方法は、個別の特徴辞書を保持する必要をなくし、メモリと計算のオーバーヘッドを削減する一方で、ハッシュ衝突を導入し、モデルの性能をわずかに低下させる可能性がある。
この手法は、オンライン広告、テキスト分類、レコメンデーションシステムなど、ユニークな特徴の数が数百万から数十億に及ぶ大規模学習タスクで特に有用である。特徴を、例えば1万から100万次元の空間にマッピングすることで、特徴ハッシングは線形モデルやニューラルネットワークを用いた効率的な学習を可能にし、多くの場合、精度の損失は無視できる程度である。
歴史と起源
特徴ハッシングの概念は2000年代初頭に遡り、自然言語処理とカーネル法において独立に発展した。最も初期の公表された利用例の1つは、2007年にジョン・ラングフォードらがスパム検出のための大規模学習に適用したものである。この手法は、2009年にキリアン・ワインバーガーらによる論文「Feature Hashing for Large Scale Multitask Learning」で広く認知されるようになり、このアプローチを体系化し、複数のタスクでの有効性を示した。
それ以前にも、2007年にアリ・ラヒミとベンジャミン・レヒトによるランダム特徴に関する研究など、カーネル近似のためのハッシングの文脈で類似のアイデアが登場していた。特徴ハッシングはまた、ラングフォードがYahoo!リサーチで開発したVowpal Wabbit学習システムで使用される「ハッシングトリック」と密接に関連している。
仕組み
特徴ハッシングは主に2つのステップで動作する。まず、各特徴名（例えば単語やカテゴリ値）がハッシュ関数（通常は32ビットまたは64ビットのハッシュ）に通され、整数が生成される。その整数は次に、目的の出力次元でモジュロ演算され、特徴の値（存在を示す場合は多くの場合1）が累積されるインデックスが得られる。衝突によるバイアスを減らすために、2つ目のハッシュ関数が寄与の符号（+1または-1）を決定し、衝突が平均的に打ち消されるようにする。
例えば、テキスト分類では、文書内の各単語が、例えば10万のサイズのベクトルのインデックスにハッシュされる。そのベクトルは、線形分類器やニューラルネットワークへの入力として使用される。ハッシュ関数は決定的であるため、同じ特徴は常に同じインデックスにマッピングされ、学習と推論の間の一貫性が保証される。
主な利点は、特徴辞書を保存する必要がないことであり、これは特徴空間がメモリに収まらないほど大きい場合に重要である。しかし、異なる特徴が同じインデックスにマッピングされる衝突が発生し、干渉を引き起こす可能性がある。出力次元が特徴数に対して十分に大きければ、その影響は通常小さい。
機械学習における応用
特徴ハッシングは、特にオンライン学習や分散コンピューティングの文脈で、大規模機械学習システムで広く使用されている。これは、広告におけるクリック率予測に使用されるVowpal Wabbitライブラリの核となるコンポーネントである。また、自然言語処理におけるbag-of-words表現にも使用され、各文書がハッシュ化されたベクトルに変換され、大規模なテキストコーパス上での分類器の効率的な学習を可能にする。
レコメンデーションシステムでは、特徴ハッシングはユーザーIDやアイテムID、および文脈特徴をコンパクトな表現にエンコードでき、明示的なルックアップテーブルなしで数百万のユーザーとアイテムを処理するモデルを可能にする。また、XGBoostやLightGBMなどの勾配ブースティングマシンの特徴エンジニアリングにも使用され、カテゴリ特徴がメモリ使用量を削減するためにハッシュ化されることが多い。
最近では、特徴ハッシングは深層学習の埋め込み層にも適用されており、特に稀なカテゴリや未知のカテゴリに対して、学習された埋め込みの固定サイズの代替として機能する。このアプローチは「ハッシング埋め込み」と呼ばれることもあり、新しい特徴が頻繁に出現するオンライン学習シナリオで有益である。
利点と限界
特徴ハッシングの主な利点はメモリ効率である。辞書が不要なため、ハッシュ出力次元が固定されていれば、無制限の数の特徴を持つデータでモデルを学習できる。これは、特徴がその場で発見される可能性があるストリーミングや分散設定で特に有用である。
もう1つの利点は単純さである。実装は簡単で、複雑な前処理を必要としない。また、各特徴を独立にハッシュできるため、並列化が容易である。
しかし、特徴ハッシングには限界がある。ハッシュ衝突は、特に出力次元が小さすぎる場合にモデルの精度を低下させる可能性がある。また、この手法は解釈可能性を失う。ハッシュ化されたインデックスを元の特徴名にマッピングするには、個別のマッピングを保存する必要があり、これは目的を無効にするためである。さらに、ハッシュ関数と出力次元の選択にはチューニングが必要であり、衝突率とメモリ使用量の間にはトレードオフがある。
代替手法との比較
特徴ハッシングは、ワンホットエンコーディング、ラベルエンコーディング、学習された埋め込みなど、他の次元削減手法としばしば比較される。ワンホットエンコーディングは簡単であるが、辞書が必要であり、高カーディナリティの特徴では非常にメモリ集約的になる可能性がある。ラベルエンコーディングは整数IDを割り当てるが、任意の順序を課すため、カテゴリデータにとって誤解を招く可能性がある。ニューラルネットワークで使用されるような学習された埋め込みは、意味的関係を捉えることができるが、学習と固定語彙が必要である。
特徴ハッシングはこれらのアプローチの間に位置する。ワンホットエンコーディングよりもメモリ効率が良く、ラベルエンコーディングの順序問題を回避し、学習や語彙を必要としない。しかし、埋め込みができるような特徴間の関係を捉えることはできない。
実際には、特徴ハッシングは、スケールのために他の方法が実行不可能な場合のベースラインやフォールバックとしてよく使用される。また、データ拡張やモデルプルーニングなどの他の手法と組み合わせて、本番システムの効率を向上させることもある。
最近の展開と研究
特徴ハッシングの研究は、特に深層学習と大規模システムの文脈で続いている。研究では、ハッシュ衝突がモデル性能に与える影響が分析され、出力次元を選択するためのガイドラインが導き出されている。一部の研究では、データ分布に適応し、衝突を潜在的に減らす学習されたハッシュ関数が提案されている。
大規模言語モデルの時代では、これらのモデルは通常、トークン化と学習された埋め込みを使用するため、特徴ハッシングはあまり目立たない。しかし、表形式データのカテゴリ特徴を処理し、機械学習パイプラインで効率的な特徴エンジニアリングを行うために、依然として関連性がある。
最近の研究では、連合学習やプライバシー保護設定での特徴ハッシングの使用も探求されており、ハッシュが特徴難読化の一形態として機能する可能性がある。さらに、AWS TrainiumやGoogle Cloud TPUなどのハードウェアアクセラレータは、特徴ハッシングが提供するメモリフットプリントの削減の恩恵を受けることができる。
全体として、特徴ハッシングは成熟した手法であり、大規模でリソースが制約された環境で新たな応用を見出し続けている。