c
オペレーションズ・リサーチ■学生論文賞受賞論文 要約■
Nuclear ノルムを用いた行列ランク最小化手法の
協調フィルタリングへの応用
横尾 知孝
筑波大学大学院システム情報工学研究科社会工学専攻（現：（株）NTTデータ）
指導教員：吉瀬章子 筑波大学教授
1. はじめに
協調フィルタリングは蓄積された多数の情報をもと にユーザーの嗜好予測を行い，各人に合わせたアイテ ム（商品）の推薦を行うシステムの基盤技術として広 く活用されている．
協調フィルタリング手法の一つである特異値分解
(SVD)
を応用した協調フィルタリング手法[1]
は既 知の嗜好情報を格納した行列を特異値分解することで 行列を次元削減し未知の情報の予測を行う手法であり，低ランク近似された行列から比較的高い精度の予測を 得られることが知られている．先行研究
[2]
では，行 列の次元削減において行列ランク最小化問題を用いた モデルを提案しているが，具体的な問題を用いた十分 な検証はなされていないのが現状である．これを踏まえ，本研究では半正定値計画問題に帰着 される行列ランク最小化問題を協調フィルタリングに 応用したモデルを複数示し，具体的な問題例を用いて 計算機実験を行った．
2. 協調フィルタリング
まず協調フィルタリングにおける記号の定義として，
m
人のユーザーの集合U =
{1,2, . . . , m}, n
個のアイ テムの集合I =
{1,2, . . . , n}
を与える．またユーザー が各アイテムに対して与える数値化された評価のこと を「評価値」と呼び，既知の評価値が取りうる定義域を Dと表す．たとえば，評価値が5
段階評価(1-2-3-4-5)
で与えられる場合，定義域はD=
{1,2, 3, 4, 5}
と なる．協調フィルタリングでは各ユーザーの各アイテム に対する評価値を格納した行列のことを評価値行列
(rationg matrix)
と呼ぶ．表1
は評価値の定義域が D=
{1,2, 3, 4, 5}
であるときの評価値行列の例で ある．一般に評価値行列では評価値が得られていない 未評価のセルを空欄として表現し，この未知の評価値 を推定することが協調フィルタリングの目標である．表1 評価値行列の例
アイテム1 アイテム2 アイテム3 アイテム4
ユーザー1 4 5 5
ユーザー2 4 2 1
ユーザー3 3 2 4
ユーザー4 4 4
ユーザー5 1 3 5
3. Nuclear ノルムを用いた行列ランク最小化
手法
行列ランク最小化問題
(Rank Minimization Prob- lem)
は，ある凸制約が課せられたもとで変数行列の行 列ランクを最小化する最適化問題のことである．ここ で変数行列X
∈Rm×n，線形写像A:
Rm×n→Rp， 実定数ベクトルb
∈Rpとした上で，X
の行列ランクrank(X)
を最小化する行列ランク最小化問題の例は以 下の問題(RMP)
として表現できる．minimize rank(X) X
subject to A(X) =b.
(RMP)
行列のランク関数
rank(X )
は非凸であり，一般の行 列ランク最小化問題はNP-
困難であることが知られて いる[3]
．一方で[4]
は，行列の特異値の和に相当するNuclear
ノルムの最小化問題が行列ランク最小化問題 の緩和問題となることを示している．このことから，(RMP)
の緩和問題は次の(NMP)
となる．Nuclear
ノ ルムは · ∗:
Rm×n→Rと表記する．minimize X∗
X
subject to A(X) =b.
(NMP)
また
(RMP)
は新たな変数W
1 ∈ Rm×m, W
2 ∈ Rn×nを導入することで次の半正定値計画問題(NMP- SDP)
に等価に変形できる[2]
．800（
72
）Copyrightcby ORSJ. Unauthorized reproduction of this article is prohibited. オペレーションズ・リサーチmimimize 12{Tr(W1) + Tr(W2)} X, W1, W2
subject to
W1 X
XT W2
O A(X) =b.
(NMP-SDP)
4. 行列ランク最小化問題を応用した協調フィ ルタリングモデル
協調フィルタリングに対する次元削減手法の有効性 に着目し，行列の低ランク化の方法として行列ランク 最小化問題を適用することを考える．
先行研究
[2]
では，行列ランク最小化問題を応用し たモデルとして以下の(SDP)
が提案されている．こ こではM
∈R|U|×|I|を学習用データにあたる既知の評 価値行列とし，M
ijが空でない添字の組(i, j)
の集合をΩ =
{(i, j)|Mij =∅}と定義している. (SDP)
の解X ˆ
が予測評価値行列に対応する．minimization 12{Tr(W1) + Tr(W2)} X, W1, W2
subject to
W1 X
XT W2
O (SDP)
Xij=Mij (i, j)∈Ω.
後に記す計算機実験を行った結果，
(SDP)
の予測性 能は既存手法と比べると劣るものであった．これを踏 まえ，予測性能の向上を目指した新モデルを提案する．新モデルの提案に即し，学習用データから算出され る各ユーザー
i
∈U
の評価値平均を¯ u
i，定義域Dの 幅を示した定数をR = max{D} − min{D}
，制約の 許容域を設定する許容パラメータをとそれぞれ定義 する．
以下に示した提案モデル
(SDP
U1)
では，予測評価 値X
ijとユーザー平均評価値u ¯
iの絶対値誤差を定義域 の幅の(
％)
以内に抑える制約 が追加されている．minimize 12{Tr(W1) + Tr(W2)} X, W1, W2
subject to
W1 X
XT W2
O (SDPU1) Xij=Mij (i, j)∈Ω
|Xij−¯ui|R· (i, j)∈/Ω.
次の
(SDP
U2)
では許容パラメータをθ
と定義し，ユーザー
i
の予測評価値の平均と既知のユーザーi
の 平均評価値u ¯
iとの絶対誤差を定義域の幅のθ(
％)
以内 に抑える制約を設定している．minimize 12{Tr(W1) + Tr(W2)} X, W1, W2
subject to
W1 X
XT W2
O (SDPU2) Xij=Mij (i, j)∈Ω
j∈IXij
|I| −u¯iR·θ ∀i∈U.
5. 計算機実験
モデルの検証のため，
GroupLens [5]
が公開するデー タセット“movieLens100k”
を用いて計算機実験を行っ た．データセットから無作為抽出したデータを学習用 とテスト用に分割し，学習データを用いて得られた予 測値とテストデータを比較して予測を評価する．実験 で扱う評価値行列のサイズは50
×200
とした．行列ラ ンク最小化問題を応用した協調フィルタリングモデル の結果と，既存手法である相関分析協調フィルタリン グ[6]
，特異値分解協調フィルタリング[1]
による結果 を比較することで性能を検証する．(SDP), (SDP
U1)
および(SDP
U2)
の求解にはSDPA7.3.9 [7]
を使用し，既存手法では統計解析ソフト
R 3.1.2 [8]
を用いた．結果，
(SDP)
では十分な精度の予測が行えなかったものの，パラメータの適切な選択により
(SDP
U1), (SDP
U2)
では，特異値分解協調フィルタリングに匹敵 する精度の予測が，現実的な時間で求められることが わかった．参考文献
[1] B. Sarwar, G. Karypis, J. Konstan and J. Riedl, “Ap- plication of dimensionality reduction in recommender system-a case study,” No. TR-00-043, Minnesota Uni- versity Minneapolis Department of Computer Science, 2000.
[2] B. Recht, M. Fazel and P. A. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,”SIAM REVIEW,52, pp. 471–501, 2010.
[3] L. Vandenberghe and S. Boyd, “Semidefinite pro- gramming,”SIAM Review,38, pp. 49–95, 1996.
[4] M. Fazel, “Matrix rank minimization with applica- tions,” PhD thesis, Stanford University, 2002.
[5] GroupLens, http: //grouplens . org/（2015 年 12月 25日確認）
[6] P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom and J. Riedl, “GroupLens: An open architecture for collaborative filtering of netnews,” In Proceedings of the 1994 ACM conference on Computer supported co- operative work, ACM, 1994.
[7] SDPA, http://sdpa.sourceforge.net/index.html
（2015年12月25日確認）
[8] The R Project, http://www.r-project.org/（2015年 12月25日確認）
