Regularized Latent Semantic Indexing

機械学習 論文

最近勉強会で発表する予定のものと仕事関係の論文しか読んでなかったのでこのブログにはあんまり書けなかったんだけど、久々に書いてみる。

紹介する論文はSIGIR 2011のLSIを語彙数が大きい時にも効率的に並列化できるようにしたという論文[1]。

論文概要

PLSIやLDAみたいなトピックモデルは情報検索においても性能向上で重要であるが、語彙数が多い時スケールしないという問題点がある(文章数に関しては効率的な実装が知られている。例えば[2])。このためよく行われるのが語彙数を1万とかに制限する方法ですが、情報検索への応用を考えるとこのアプローチは問題がある(文章分類やクラスタリングへの応用であればこれで問題ない)。

このため著者らはRLSIという方法を提案した。これにより160万文章、語彙数700万のデータセットに対して16台のマシンでトピック数500のとき1時間半で処理できた(おそらく1イテレーションの時間、トータルのイテレーション回数の記述は見つけられなかった)。

既存手法について

情報検索におけるトピックモデルの手法としては、まずLSI(潜在意味解析)がある。しかしこの方法では直交制約などがあるためSVD(特異値分解)を利用する必要があり、スケーラビリティに欠ける。また確率的な手法としてPLSI, LDAがあるが、これらは単語トピック確率行列を保持しておく必要があり単語数が大きいときにスケーラビリティに欠ける。

提案手法

今文章数をN、語彙数をM、トピック数をKと書く。このとき文章はM次元のベクトルdとして表される。このとき文章行列をD=[d_1,...,d_N]と書く。

また各トピックごとのM次元の単語ベクトルをuと書く(PLSIであれば各トピックにおける単語出現確率に相当)。単語トピック行列をU=[u_1,...,u_K]と書く。

ここで各文章ベクトルをu_iの線形和で近似する。すなわちd≒Σ v_k u_k。ここで文章nに関する係数ベクトルをv_nとし、トピック文章行列をV=[v_1, ... , v_N]と書く。

ここまでは既存手法も同様の定式化となっているがRLSIではこの先の制約条件が異なってくる。既存の手法であればuやvに関してLSIでは直交しているという制約を、PLSIやLDAであれば確率分布としての制約(非負かつ和が1)を入れている。

RLSIではu,vに関してL1,L2正則化を入れる。すなわち以下の目的関数を最小化する。

\sum_{n=1}^N |d_n - Uv_n|^2_2 + \lambda_1 \sum_k |u_k|_1 + \lambda_2 \sum_n |v_n|_2^2

ここでuに関してL1正則化を入れて、vに関してL2正則化を入れているのはトピック中の単語に関して可読性を高めることと情報検索への応用の際に実験的なパフォーマンスが向上するためである。

最適化手法

最適化に関してはNMFなどと同様にVを固定してUを最適化、Uを固定してVを最適化という処理を繰り返す。
更新式についてはVに関しては解析解がもとまり、Uに関してはcoordinate descentで最適化する。(詳細は[1]参照)

また並列化に関しては更新式の形が行列演算の繰り返しで書かれており、このような演算をmapreduceで効率化する方法はすでに知られている[3]。

さらに並列化時のプロセッサ数によらない部分をみるとLDAの並列化の場合は空間効率がO(MK)に対して、RLSIの場合はO(K^2)であり、語彙数が多くてもスケールする手法になっている。

他手法との関係

RLSIやPLSI,LSIにおいて最適化する式は以下のような一般の式でかける。
\min_{(U,V)\in C} B(D || UV) + \lambda R(U,V)

ここでCは制約条件、Bは何らかの距離尺度、Rは正則化項。LSIやPLSIは正則化項がなくて制約条件をつけた最適化を行うが、RLSIでは制約条件がなくて、代わりに正則化項が存在する。

またコンピュータビジョンの分野などでよく使われているSparse codingの手法はRLSIに近いが、スケーラビリティを考慮してない+応用先が異なる。

実験結果

文章検索においてBM25の値だけではなく、トピック空間での類似性も加味してランキングを行った時の精度(NDCG)を見た。また並列計算のフレームワークとしてはSCOPE[4]を用いた。

結果の要約としては

  • 正則化の部分はUにL1,VにL2制約を入れたものがもっとも精度が高かった+解釈もしやすい
  • LSI,PLSI,LDAと比較するとRLSIが若干性能が高かった
  • 大規模データ(単語数 7014881, 文章数 1562807, トピック数 500)に対してRLSIを適応して、MLR(LambdaRank[5])の特徴量に追加したところ有意な精度向上がみられた。

結論

トピックモデリングにおいてRLSIという、正則化項を使った手法を提案した。このような手法はComputer Visionとかでは類似のものがみられるが、トピックモデルに明確に適応したのは著者らが知るかぎり本論文が初である。

RLSIはMapredcueのような並列環境で効率的に実装でき、かつ既存のトピックモデルよりも情報検索に応用した時の精度が若干高いことを示した。

参考文献

[1] Regularized Latent Semantic Indexing, SIGIR 2011
[2] PLDA+: Parallel Latent Dirichlet Allocation with Data Placement and Pipeline Processing, TIST 2010
[3] Distributed Nonnegative Matrix Factorization for Web-Scale Dyadic Data Analysis on MapReduce, WWW 2010
[4] Scope: Easy and efficient parallel processing of massive data sets, VLDB 2008
[5] Learning to rank with nonsmooth cost functions, NIPS 2007