機械学習処理におけるカテゴリ変数の扱い方(Feature hashingについて)

こんにちは！機械学習エンジニアの桶原です。
業務では主に機械学習処理を用いた広告効果予測と改善をテーマとしています。
今回は機械学習処理におけるカテゴリ変数の扱い方の中でもあまり触れられることのない、Feature hashingを利用した方法についてお話できればと思っています。

カテゴリ変数の取り扱い

カテゴリ変数の扱う方法として多くの教科書ではOne hot encodingが紹介されていると思います。
簡単におさらいしてみましょう。

上図左上のようなURLに対してその種別が振られたようなデータを考えます。これを各カテゴリの水準ごとに分解し、その存在の有無(有：1、無：0)を値として持つようにデータの表現方法を変換するのがOne hot encodingです。このような変換により、数値としてカテゴリ変数を表現できるようになるため、機械学習処理の入力データとして利用できるようになります。

One hot encodingを利用したモデル生成には解釈がしやすいというメリットがある一方で、下記のようなデメリットがあります。

• カテゴリ変数とその水準が多い場合に入力特徴量の次元数が爆発する
• モデル生成時の入力データに存在しないカテゴリ変数について表現することができない

Web広告の分野では、上記2つの条件に当てはまってしまうようなカテゴリ変数を頻繁に扱います。たとえば、サイトの更新等により日々大量に新しく生成されるURLや、ユーザのCookie情報などがあげられます。これらの変数に対してOne hot encodingを用いた広告効果予測モデルの生成等を行ってしまうと、下記のような問題が実際に出てきます。

• カテゴリ変数の水準数に従い必要なメモリが増加する
• モデル生成時に存在しなかったデータの活用ができない

このような状況になったとき、Feature hashingを利用するとハードウェアを増強したりすることなく、いい感じに上記の問題を回避できたりします。

Feature hashingとは

Hashing Trickとも呼ばれる手法です。今はどうかわかりませんが、以前はYahooのスパムメール分類システム*1で利用されていたりしたそうです 。 基本的なイメージは下図の通りです。

上図では前例におけるURLをFeature hashingする場合の状態を示しています。まず上図中心にある箱(index)の数dを決めます。これはn種類あるURLを最終的に表現する際に利用する次元数になります。これが定まったらhash関数を利用して、どの箱(index)にどのような値が入るかを決定します。この定め方に関しては後ほど説明します。全ての入力データに対して値が求まったら、これをモデル生成の入力データとして利用します。

上記からFeature hashingでは下記のような性質があることが簡単にわかると思います。

• 最終的な入力データの次元数をdの値で調整が可能
• モデル生成時に含まれていないデータにもhash関数が適用されindexの取得と値の設定がされるため利用が可能

ただ、いいことばかりでもありません。 基本的にd<nとなるように値が設定されるため、1つのindexに対して複数の入力データ、上図の例におけるURLが紐づいてしまうことになります。この状況を衝突と呼びます。衝突が起きてしまった場合、そのindexが複数の意味を持つことになります。1つ、2つの衝突であればまだ解釈もできるかもしれませんが、100、1000と大きくなってきたらどうでしょう？そのため、ある程度大きいdを検討する、特定のindexでの衝突が増えてしまわないようにindexが均等に求まるhash関数を利用するといった工夫がなされます。

上述のような衝突があるので、下記のようなカテゴリ変数の性質を考慮した上で適用を検討するのがいいのではないかと思います。

• 変動の大きいカテゴリ変数
  • 定期的に新しくなるようなユーザID等のカテゴリ。それぞれの水準自体を保持することより、効率的なデータ保持が求められるため適している
• 変動が小さく、全てのカテゴリを保持することが重要な変数
  • 性別(男性、女性、その他)のようなカテゴリ。それぞれの水準自体に意味があり、欠損による影響が大きいカテゴリは適さない

実際利用するデータでは上記が混在していることが多いです。その場合は、One hot encodingと併用するというのが適切な利用方法になります。ただ、簡単のために衝突が起きることを許容して一括でFeature hashingをかけてしまうことも多いです。

Feature hashingの種類

上図の例ではURLという1つのカテゴリ変数を扱いましたが、実際にモデルを生成する際には複数のカテゴリ変数を利用します。このとき、全てのカテゴリで共通の空間(上図のd)を利用するか、異なる空間を利用するかで大まかな種類を分けることができます。この空間のことをhashing spaceと呼びます。それぞれの方法と特徴を下記に示します。

• Global hashing space
  • 全ての特徴量で同一のhashing spaceを利用する方法。利用するパラメータがhashing spaceの次元ひとつのため、シンプルな記述が可能
• Per-field hashing space
  • 各特徴量ごとにhashing spaceを構成する方法。各特徴量ごとにhashing spaceの次元を構成するため、国やドメインといった異なる複数の特徴量のhashing結果が混ざることがない

また、衝突が起きた際にindexに設定する値をどうするかで、Feature hashingの手法は大きく分類することができます。名前が見つからなかったので、この場では第一著者の名前をとって呼ぶことにします。それぞれの内容が紹介された論文については注釈からとぶことが可能です。 それぞれの手法の説明については実装部分で説明します。

• Shi's hash function*2
• Weinberger's hash function*3

hashing functionの比較

概要

概念的な話ばかりというのも退屈なので実際のデータを用いて、性能比較をしてみましょう。 Global hashing spaceでShi's hash functionとWeinberger's hash functionを用いてカテゴリ変数を変換した際の性能を比較してみようと思います。テーマとしてはWeb広告のクリック確率予測を扱います。さまざまな種類のカテゴリ変数を扱えるため都合がよいと思い、テーマとして選びました。 データはCriteo社が公開している下記のTerabyte Click Logを用います。下記からダウンロードできます。

labs.criteo.com

上記データは1レコードが1回の広告表示を表しています。そして、その表示1つ1つに対してクリックが発生したかどうかのフラグ、13種の連続値特徴量、26のカテゴリ特徴量(変数)が付与されています。今回のメインのテーマはカテゴリ変数の変換なので、連続値特徴量もkmeansで離散化、ID化してカテゴリ変数として扱ってしまおうと思います。(そのほか、データの詳しい内容については付属のREADMEに記載されてあるのでそちらをご覧ください)

上記のデータを用いて各レコードがクリックするかしないかを判定する分類問題をロジスティック回帰で解き、その予測精度を比較することでカテゴリ変数変換方法の違いがもたらす性能の変化を比較していこうと思います。

注意事項

今回の内容はカテゴリ変数の変換方法の違いがどの程度分類問題の予測精度に影響するかを確認する内容です。そのため、基本的にカテゴリ変数の変換以外の条件は全てあわせます。また、モデル間での差異をなくすため、特徴量選択やチューニングは行っていません。

実装

全てを記載すると長くなってしまうので、hash関数部分のみの実装を記載します。
今回、簡単のためにFeature hashingを利用する場合には全てのカテゴリ変数に対して一括でFeature hashingをかける実装になっています。

1. Shi's hash function

下記がShi’s hash functionの実装です。

import numpy as np
import hashlib
def shi_hashing_function(dat):
　#Feature hashing後の次元数を設定
    d = 50000
　#indexと対応する値の初期化
    x = np.zeros((dat.shape[0],d),dtype=int)
    for row in range(dat.shape[0]):
        for col in range(dat.shape[1]):
            #hash関数を利用した文字列の数値化+剰余演算によりindexを求める
            index = int(hashlib.md5(str(dat[row,col]).encode('utf8')).hexdigest(), 16) % d + 1
            #値の設定
            x[row, index] += 1
    return x

まずは、Feature hashing後の次元数を設定します。その後、hash関数を利用した文字列の数値化とFeature hashing後の次元数を利用した剰余演算でindexを求めます。最後に該当indexの値を設定します。Shi’s hash functionでは、得られたindexの値に1を追加していきます。そのため、衝突が起こった場合にはindexの値が衝突の回数になります。

2. Weinberger's hash function

下記がWeinberger's hash functionの実装です。

import numpy as np
import hashlib
import random
def weinberger_hashing_function(dat):
　#Feature hashing後の次元数を設定
    d = 50000
　#indexと対応する値の初期化
    x = np.zeros((dat.shape[0],d),dtype=int)
    for row in range(dat.shape[0]):
        for col in range(dat.shape[1]):
            #hash関数を利用した文字列の数値化+剰余演算によりindexを求める
            index = int(hashlib.md5(str(dat[row,col]).encode('utf8')).hexdigest(), 16) % d
            #追加する値を別のhash関数を利用して決定する
            binary_score = int(hashlib.md5(str(dat[row,col]).encode('utf8')).hexdigest(), 16) % 2
            if  binary_score== 0:
                x[row, index] -= 1
            else:
                x[row, index] += 1
    return x

Weinberger's hash functionの実装きたないですね。。。すみません。。。

基本的な流れはShi’s hash functionの実装と同じです。異なる点は求められたindexに対する値の設定方法です。Shi’s hash functionでは1を追加していくだけでしたが、Weinberger's hash functionでは追加する値を、もうひとつ別のhash関数を用いて1と-1から選択し追加していきます。そのため、indexの値が衝突の回数を表しません。(もともと１だったindexに対して次に-1 が選択されてしまった場合、打ち消されて値が0になってしまいます。)　

こちらのメリットについてはWikipedia*4にわかりやすく記載されているので、興味のある方はご覧ください。

上記で利用している文字列のhash化に利用している関数や、文字列からindexを求める方法、表現する次元数などはチューニングできる項目です。利用される際はこのあたりの調整をされると精度に変化があると思います。(今回、文字列のhash化に利用したMD5やFeature hashing後の次元数はデータを確認して適当に決めました。)

結果

上記の2つhashingの関数を利用したモデルと、One hot encodingを利用したモデルを比較対象として生成しました。

評価指標としては、過去にCriteoが類似データを用いて開催したコンペで利用していたloglossを採用しました。データは時系列にそって格納されているため、学習用データとして最初の10万件を、検証用データとして次の10万件のデータを用いました。また、モデル生成時には学習用データをアンダーサンプリングし、クリック有りのサンプルサイズとクリック無しのサンプルサイズが1:1になるよう調整したうえでモデルを生成しました。

下記が各モデルによる予測結果です。

One hot encodingの予測精度よりも、Shi's hash functionとWeinberger's hash functionの予測精度が良いことが確認できます。これは、おそらくモデル生成時に存在しなかったカテゴリ変数の利用が可能になったことによる改善だと思われます。また、Weinberger's hash functionと比較してShi's hash functionの予測精度が良かったのは、衝突した場合においても情報が残されていたことにより、情報の欠損を防げたためではないかと想定されます。

上記の結果は一側面でしかないので結論づけるのは難しいですが、カテゴリ変数をFeature hashingで変換することの有用性の一端を示せたのではないかと思います。カテゴリ変数を扱う際は、変換方法のひとつの選択肢として、是非試してみてください！

次元圧縮手法としてのFeature hashing

ここまでは、Hashing後の特徴量の次元数を十分大きくしておくことで衝突を可能な限り抑えるというスタンスで話を進めてきました。しかし、１つのindexが複数の意味を持つという衝突を特徴量を集約しているととらえ、次元圧縮と考えることも可能です。Kaggle等のコンペでFeature hashingがよく利用されるのは、この点が大きいと思われます。

ちょっとこの点に関しても確認してみましょう。
下記にFeature hashing後の次元を調整したときの予測精度の変化を示します。評価指標と利用データ件数は同じものを利用しています。

1. Shi's hash function

2. Weinberger's hash function

Shi’s hash function、Weinberger's hash functionともに10000次元まで次元を落としても大して予測精度は変化せず、それ以上次元を落とすと大きく悪化しはじめることがわかります。

両方の手法ともに10000次元程度までは、予測精度を落とさずに機械学習処理にかける入力データの次元を圧縮できていることがわかります。これは、機械学習処理への入力データ次元をおよそ1/5まで圧縮できることを意味しています。

今回はそれほど大きな次元を扱っていないので、それほどインパクトも感じられないかも知れませんが、入力データが増えたとき、特徴量の次元が大きいときには、大きな違いを生み出します。上記のような問題にお困りの方は、一度試されてみることをおすすめします。

このあたりに興味のある方は衝突の件数と予測精度の変動に関してはこちら*5に詳しく記載されておりますのでご覧ください。

まとめ

今回はカテゴリ変数の扱い方、次元圧縮の手法としてのFeature hashingという手法を紹介しました。 有用性についてうまく示せたかわかりませんが、参考にしていただけますと幸いです。

今後もマイクロアドの機械学習エンジニアがどんなことをしているのか、どんなことに興味を持っているのか定期的にこの場で共有していこうと思っています。興味をもっていただけましたら、次回も是非読みに来てください！

ここまで記事を読んでくださり、ありがとうございました！！

*1:https://www.researchgate.net/publication/210342009_Collaborative_Email-Spam_Filtering_with_the_Hashing_Trick

*2:http://proceedings.mlr.press/v5/shi09a.html

*3:https://arxiv.org/abs/0902.2206

*4:https://ja.wikipedia.org/wiki/Feature_Hashing

*5:https://www.researchgate.net/publication/210342009_Collaborative_Email-Spam_Filtering_with_the_Hashing_Trick