情報検索における潜在意味解析

前回はユーザーベースの協調型推薦を実装したのですが、このようなシンプルな協調フィルタリングには大きな問題があります。 それはスパースな行列に対してうまくレコメンドができないことです。システムが巨大になるほど、ユーザーが利用していないアイテムが増えたり、 あまりシステムを利用しないユーザーが増えていくため、行列が非常にスパースになっていきます。

https://leisurelab.hatenablog.com/entry/2019/02/21/073842leisurelab.hatenablog.com

潜在的意味解析の意義

協調的型推薦は主にメモリベースとモデルベースの２つに分類されます。

• メモリベース ユーザーが評価した評価値をデータベースとして保持した評価値データベースをすべてのメモリの中に格納し、推薦を行うために直接用いる手法。

• モデルベース 生のデータをあらかじめオフラインで処理して、推薦実行時にはオフラインで処理した前処理結果や学習済みのモデルを評価値予測のために使用する手法。

理論上、メモリベースのように存在するデータをすべて用いるほうが正確ですが、データの規模が大きくなるにつれて計算量と計算コストの問題が出てくると考えられます。

こういった実務的な要請があるために、モデルベース推薦が注目されてきたと背景があります。

モデルベース推薦において、潜在的な"意味"を表現する因子を利用するという考えが一般的です。 例えば、Google検索などの情報検索においてユーザーが入力したクエリに対して、文書とクエリそれぞれに含まれる単語の重複によって評価するという単純な手法を利用することはもちろん可能です。 しかし、この手法には問題があって"車"や"自動車"などの同義語や、"モデル"などに複数の意味を表しうる多義語が含まれる場合、うまく機能しません。

この問題を解決するために、潜在的意味解析(latent semantic analysis; LSA)という技術が発展してきました。 LSAは、すべての文書の背後に意味の構造が存在すると考え、これを行列の形に表現して、分解することが特徴です。 行列として表現することにより、多変量海鮮の考えを適用でき、文書や語句を数学的・統計的に分析することが可能になります。 また、LSAでは表現としては豊かすぎる語句・文書を、行列分解という形で除外し、複数の語句の背後に共通して存在する意味構造を抽出することを考えます。 これにより、大規模な文書ベクトルの行列に対して単語間の高い相関や共起語を１つの因子として捉えて、より小さな階数(ランク)の行列による近似に縮約することで、 生データの情報をできるだけ損なわずに、規模の問題を解決しようとしています。

LSAで使われる行列分解のうち、特異値分解(singular value decomposition; SVD)について考えてみたいと思います。

特異値分解(SVD)

特異値分解の概要

特異値分解は簡略的には以下のように表現されます。 これは与えられた行列Mを以下のように３つの行列に分割している操作です。

は左特異ベクトル、は右得意ベクトル、の対角成分は特異値といいます。

仮に行列がの行列でランクがの場合、行列には冗長な要素が含まれているといえます。 以下のように、上の式を変換することで行列をr次元データで表現できるようになります。

この分解で重要なポイントは、n次元行列をr次元行列に変換できるだけでなく、 ユークリッドノルムの大きなベクトル、つまり行列を構成する上で影響力の強いベクトルから順に列ベクトルに割り当てられることです。

SVDを使った次元削減

上述したように、は対角行列なので、対角要素が大きければ、行列に与える影響も大きくなります。 そこで上位k個のを抽出することで、次元を削減します。この手法は低ランク近似と呼ばれます。 小さな特異値から削減することで、オリジナルの行列と低ランク近似した行列の各要素の２乗誤差が最小になることが知られています。

Pythonでの実装

情報検索の例

以下のデータベースにおいてSVDを試してみます。 例は以下のサイトから引用しています。

	drive	automobile	car	play	music
document1	2	3	0	0	0
document2	2	0	2	0	0
document3	0	0	0	2	2
document4	0	0	0	3	1

この例だとdocument1にはcarの出現頻度が0であり、この文書でcarを検索してクエリと文書の重複を見ても、重複がないためdocument1を見つけることはできないということが言えます。 同様に、automobileで検索してもdocument2を得ることはできないということが言えます。 しかし、carとautomobileは同義語だと言えるため、検索で見つけられるようになる必要があると考えられます。 そこで、特異値分解(SVD)を用いることで、潜在的共起性を抽出します。

import numpy as np
import pandas as pd


arr = np.array([[2, 3, 0, 0, 0],
                [2, 0, 2, 0, 0],
                [0, 0, 0, 2, 2],
                [0, 0, 0, 3, 1]])

numpyを用いて特異値分解を行います。

u, sigma, v = np.linalg.svd(arr, full_matrices=True)

上位k個を抽出し低ランク近似を行います。 最後は結果を解釈しやすいように、小数点第3位で四捨五入しています。

k = 2
u2 = u[:, :k]
sigma2 = sigma[:k]
v2 = v[:k, :]

arr2 = np.round(np.dot(np.dot(u2, np.diag(sigma2)), v2), 2)

これによって得られた結果を以下に示します。

	drive	automobile	car	play	music
document1	2.38	2.29	0.85	0	0
document2	1.32	1.27	0.47	0	0
document3	0	0	0	2.36	1.37
document4	0	0	0	2.68	1.55

以上の結果より、document1とdocument2ともにautomobileとcarの要素が正の値を取っており、 それぞれが検索として潜在的共起性を抽出できていることがわかります。

推薦システムの例

追記予定。

まとめ

次元削減に関しては、主成分分析(PCA)や非負値行列因子分解(NMF)などもあり、今後これらも比較していきたいです。 何か間違いなどを発見されましたら、コメントいただけるとありがたいです。

情報推薦システム入門 -理論と実践-