Technical Hedgehog

機械学習と気になる技術を語るはりねずみ

数えきれないほどの分類を行うExtreme Classification

本記事では分類タスクの一種であるExtreme Classificationの代表的な手法と特徴を紹介します。機械学習においてアヤメの分類など10数個までのラベルやクラスへの分類タスクはチュートリアルなどで多く取り上げられています。

一方で商品をカテゴリに分類したい場合など大量のラベルやクラスで分類したい場合、既存手法では計算量が膨大になるなど様々な問題に直面します。そこで大量のラベルやクラスを用いて分類を行うタスクをExtreme Classificationと呼び研究が進められています。

Extreme Classificationとは？

f:id:kamujun:20180622152814p:plain

Extreme Classificationは10万〜100万にも及ぶ膨大なラベルやクラスを用いて対象を分するタスクです。このタスクは少なくとも10年以上前から研究が行われており、学会のワークショップなどでも取り組まれています。直近ではNIPS Extreme Classification 2017 開催されています。日本からはYahooの田頭さんが既存手法を改善させたAnnexMLを発表されています。また、AnnexMLの論文紹介として、u++さんのこちらの記事が参考になります。

Extreme Classificationはマルチクラス(multi-class)とマルチラベル(multi-label)の2つの問題に分けて考えられます。

前者はExtreme Multi-class Classificationと呼ばれ、対象に対して一つのクラスを割り当てる問題を想定しています。後者の複数のラベルを割り当てるタスクはExtreme Multi-label Classification (XMCと略されることが多い)と呼ばれ、近年の研究ではこちらの問題に取り組んだものが多く見受けられます。これはマルチラベル問題はマルチクラス問題を包含しているためだと思います(マルチラベルでの推定結果1番目だけ採用すればマルチクラスと同等とみなせる)。

Extreme Multi-label Classification について興味があれば各手法の性能やデータセットについて紹介しているThe Extreme Classification Repositoryが参考になると思います。

以降はXMCの代表的なアプローチ方法であるEmbedding BasedとTree Based、Deep Basedの3つについて、それぞれ代表的な手法を交えながら紹介します。

Embedding Based

このアプローチの基本的な考え方は、分類したいラベルを減らして既存手法を適用可能にさせることをベースとしています。XMCが難しい原因はラベル数が多すぎるためであり、1-vs-Allなどの既存の手法が扱えないためです。そこでラベルを低ランクに近似させることで、扱えるラベル数にしようというわけです。このアプローチにおける手法の違いは、低ランクにするcompression(圧縮)処理や推定結果を得るために圧縮前の次元にdecompression(本記事では解凍と呼称)処理などに現れます。

このアプローチの利点としては仕組みとしてシンプルかつ理論的に説明が可能であり、実装が比較的容易である点です。問題点としては現実世界のデータにおいて、ラベル毎の訓練データが不均衡である場合など低ランクに仮定するのが困難な(圧縮の際に情報が落ちる)場合があるという点があります。

f:id:kamujun:20180622162311p:plain

代表的な手法としてはSLEECがあります。学習フェーズでは高次元(各値は0or1)で表現されるラベルベクトルを低次元へ圧縮(と同時に解凍)する方法を学習させます。次に入力である特徴ベクトルから低次元ラベルを推定させるモデルを学習させます。推論させる場合は低次元ラベルを求めた後、その結果を解凍することによって分類結果を得ることができます。

性能向上と計算量を減らすための工夫として、入力である特徴ベクトルをk-means法で大まかに分割させ、それぞれのクラスタで圧縮(解凍)方法を学習させています。推論時にはkNN(k近傍法)で所属するクラスタを求めてから低次元ラベルの推定と解凍を行います。

Tree Based

この方法では大量ラベルでの分類を決定木などの木構造を用いて推定させます。このアプローチではラベル数が多いことによる計算量の増加や性能の低下という問題に対して、既存手法を適応させるために改良したものが多く存在します。

このアプローチの利点は木構造のアルゴリズムと同様に、バランスのとれた構造を作れた場合に推定時の計算量がある程度で抑えられる点です。また、アンサンブルにしたり多くの特徴量と重みを用いることでロバスト性を獲得することができます。

f:id:kamujun:20180622162419p:plain

代表的なものとしてFastXMLがあります。これはランダムフォレストをマルチラベルに適応させた手法です。既存手法では各決定木を成長させる際に情報利得の目的関数としてジニ不純度(Gini impurity)やエントロピー(entropy)を用いていましたが、ラベルが多すぎるために計算量が膨大になってしまう問題があります。そこで目的関数にランキングの評価指標であるnDCG@kを用いる事で、計算量を抑えつつ大量ラベル分類の学習することができます。nDCG@kやこのタスクで良く用いられている評価指標についてはこちらで紹介しています。

Deep Based

近年注目を集めているDeep Learningを用いた手法も提案されており、NAACLなどの学会などでも採択されてきています。アプローチ方法は様々で、入力である特徴ベクトルをもとに複数層重ねたNeural Networkで学習させる方法や、分類ラベルをグラフとみなしてEmbeddingを求めて目標関数に用いる方法など研究が盛んになってきています。

f:id:kamujun:20180622162554p:plain

今回紹介するのは、文書特徴を畳み込んで分類を行うXML-CNNです。文書分類のタスクに対してCNNを用いる事は珍しくありませんが大量ラベルを扱うための工夫として、プーリングの方法、損失関数、次元数の少ない隠れ層の追加などでより対処しています。 それぞれの工夫については論文輪講にて紹介しました。

これから

これまでもExtreme Classificationは検索や広告などでも応用されてきたように、活用されるシーンが増えてくるのではないかと感じています。今後も研究は活発に行われると思いますので、引き続き注目していきたいと思います。

参考