DEIM Forum 2016 F2-4
推薦システムにおける文脈適応及び計算時間短縮を実現する
切り出し法と構成モジュールの自動合成方式
福田 正向
†清木 康
††慶應義塾大学環境情報学部 〒252-0882 神奈川県藤沢市遠藤 5322
E-mail: †{t13504yf, kiyoki}@sfc.keio.ac.jp
あらまし E コマース市場の拡大に伴い, Web 上に流通する商品数が増大し, 限られた時間で多数の商品の中から ユーザーの嗜好や文脈にマッチした商品を探索することが困難になる情報過多問題が深刻化している。その解決策 として推薦システムの研究開発が行われているが, ユーザーの嗜好や文脈に合わせた推薦システムを行うためには 計算量が非常に膨大になってしまうという問題がある. 本研究ではこうした問題を解決するために, ユーザーが置 かれた文脈に合わせて動的に部分空間選択を行い, ユーザーの文脈に適応した推薦システムを実現し, さらに計算 時間を大幅に削減することを可能にする切り出し法という手法を実装し, 実験の結果として大幅に短い計算時間で より高い精度を示した.さらにユーザーの嗜好類型及び状況に合わせて動的に推薦システムの構成モジュールを自 動合成するアーキテクチャーを提案する. 切り出し法は他の様々な推薦システム手法と組み合わせて用いることが 可能な汎用的なものであり, 今後の推薦システム開発の基盤として活用可能なものである. キーワード 推薦システム, レコメンド, 意味の数学モデル, 文脈, 部分空間選択, 計算量削減
1. は じ め に
現 在 , 情 報 化 の 進 展 に 伴 い , 個 人 の 嗜 好 は 多 様 化 し , 従 来 の マ ス マ ー ケ テ ィ ン グ に よ る 画 一 的 な ア プ ロ ー チ で は 顧 客 の ニ ー ズ に 訴 求 し 販 売 促 進 を 行 う こ と が 難 し く な っ て い る .顧 客 個 人 の ニ ー ズ を 的 確 に 把 握 し , そ れ に 合 わ せ て 最 適 な 商 品 を 推 薦 す る 必 要 が あ る .い わ ば 潜 在 需 要 の 発 掘 が 社 会 的 な 課 題 と な っ て い る . ま た , EC 市 場 や デ ジ タ ル コ ン テ ン ツ 市 場 の 成 長 に 伴 い , イ ン タ ー ネ ッ ト 上 の 商 品 や コ ン テ ン ツ の 量 は 飛 躍 的 に 増 大 し て い る . こ れ は , イ ン タ ー ネ ッ ト で 様 々 な モ ノ が 買 え る と い う 意 味 で ユ ー ザ ー に 利 便 性 を も た ら す 一 方 , 商 品 数 の 急 増 に 対 し , ユ ー ザ ー が 購 買 の た め の 商 品 探 索 に 使 え る 時 間 は 限 ら れ て い る の で 本 当 に ユ ー ザ ー が 求 め る 商 品 に 出 会 い に く く な る と い う 情 報 過 多 問 題 を 生 み 出 し つ つ あ る .こ う し た 背 景 か ら 推 薦 シ ス テ ム の 研 究 が 進 ん で い る が , 大 規 模 EC サ イ ト な ど に お い て ,文 脈 適 応 性 な ど の 高 度 な 性 質 を 持 つ 推 薦 シ ス テ ム が 十 分 に 普 及 し て い る と は 言 い 難 い .推 薦 を 行 う 対 象 ユ ー ザ ー を 行 に , 対 象 ア イ テ ム の 列 と す る 行 列 を 仮 定 す る と , 大 規 模 EC サ イ ト の 場 合 は 数 千 万 ユ ー ザ ー と 1 億 点 以 上 の ア イ テ ム か ら な る 極 め て 巨 大 な 行 列 と な る . さ ら に こ れ は ス パ ー ス な 行 列 で あ る こ と が 知 ら れ て お り , 一 般 的 な 推 薦 手 法 を 適 用 す る と 非 常 に 膨 大 な 計 算 時 間 及 び 計 算 資 源 を 要 す る . こ れ に 対 す る 解 決 策 と し て , 本 稿 で は 切 り 出 し 法 と 構 成 モ ジ ュ ー ル の 自 動 合 成 方 式 と い う 二 つ の 手 法 を 提 案 す る .一 つ 目 の ,切 り 出 し 法 は , ク ラ ス タ リ ン グ と 部 分 空 間 選 択 を 組 み 合 わ せ て 推 薦 シ ス テ ム の 計 算 時 間 を 大 幅 に 短 縮 し , か つ 文 脈 に 適 応 し た 推 薦 を 可 能 に す る 手 法 で あ り ,協 調 フ ィ ル タ リ ン グ 等 の 推 薦 ア ル ゴ リ ズ ム の 前 処 理 と し て 用 い る こ と が で き る .二 つ 目 の , 推 薦 シ ス テ ム の 構 成 モ ジ ュ ー ル の 自 動 合 成 方 式 は , 推 薦 シ ス テ ム の 機 能 ・ 特 性 を 決 定 す る 各 種 構 成 モ ジ ュ ー ル を そ の 役 割 ご と に 階 層 化 し , 処 理 手 順 を レ シ ピ と し て 生 成 し , ユ ー ザ ー の 嗜 好 類 型 や 置 か れ た 条 件 に よ っ て 最 適 な レ シ ピ を 決 定 す る 方 式 で あ る .こ れ に よ り , 多 様 な 嗜 好 類 型 や 変 化 す る 条 件 に 柔 軟 に 対 応 で き る .2. 提 案 手 法
本 稿 に お け る 提 案 手 法 で あ る,切 り 出 し 法 と 構 成 モ ジ ュ ー ル の 自 動 合 成 方 式 の そ れ ぞ れ に つ い て,そ の 概 要 と 具 体 的 手 順 と 期 待 で き る 効 果 を 示 す.2.1. 切 り出 し法
ユ ー ザ ー が 置 か れ た 文 脈 に 即 し た 推 薦 を 大 幅 に 少 な い 計 算 時 間 で 行 う こ と を 可 能 に す る 前 処 理 手 法 と し て, 切 り 出 し 法 を 提 案 す る . 切 り 出 し 法 は 現 在 広 く 採 用 さ れ て い る 推 薦 手 法 で あ る 協 調 フ ィ ル タ リ ン グと 特 に 親 和 性 が 高 く , 協 調 フ ィ ル タ リ ン グ を 用 い た 推 薦 ア ル ゴ リ ズ ム に 文 脈 適 応 性 を 付 加 し , 計 算 時 間 を 短 縮 で き る . 図 1.空 間 に お け る 切 り 出 し 法 の イ メ ー ジ 切 り 出 し 法 の 概 要 を 説 明 す る. 図 1.に あ る よ う に , 前 処 理 と し て ユ ー ザ ー の 嗜 好 を ク ラ ス タ リ ン グ し た 上 で, 推 薦 対 象 ユ ー ザ ー の 嗜 好 と 最 も 近 い 嗜 好 ク ラ ス タ (嗜 好 類 型 )を 特 定 し , さ ら に 直 近 期 間 に お い て 購 買 ・ 閲 覧 し た ア イ テ ム の メ タ デ ー タ(ジ ャ ン ル 等 )を 次 元 と す る 部 分 空 間 を 文 脈 に マ ッ チ し た 部 分 空 間 と み な し, そ の 部 分 空 間 内 で 推 薦 手 法 の 処 理 を 実 行 す る こ と で 計 算 対 象 の デ ー タ 量 が 大 幅 に 削 減 さ れ る. 文 脈 に 応 じ て 部 分 空 間 選 択 を 行 い,文 脈 に 適 応 し た 検 索 を 可 能 に し , 計 算 量 の 削 減 も 可 能 な 方 式 と し て 意 味 の 数 学 モ デ ル [1]が 提 案 さ れ て い る 。 ま た ,意 味 の 数 学 モ デ ル と ク ラ ス タ リ ン グ を 組 み 合 わ せ ,部 分 空 間 選 択 の 後 に ク ラ ス タ リ ン グ を 行 う こ と で 意 味 的 知 識 発 見 を 行 う 研 究 [2]も あ る .切 り 出 し 法 は 意 味 の 数 学 モ デ ル と ク ラ ス タ リ ン グ の 組 み 合 わ せ を 推 薦 シ ス テ ム の 前 処 理 手 法 と し て 応 用 し た も の で あ る .従 来 の 意 味 の 数 学 モ デ ル と ク ラ ス タ リ ン グ の 組 み 合 わ せ を 行 う 研 究 と の 処 理 的 , 機 能 的 な 大 き な 違 い は,従 来 の 手 法 が 部 分 空 間 選 択 を し た 上 で ク ラ ス タ リ ン グ を 行 う の に 対 し, 切 り 出 し 法 は ク ラ ス タ リ ン グ を 行 っ た 上 で 文 脈 に 合 わ せ て 動 的 に 部 分 空 間 選 択 を 行 う と い う 処 理 の 順 序 の 違 い に よ り,推 薦 処 理 ご と に 毎 回 ク ラ ス タ リ ン グ を 実 行 す る 必 要 が な く,迅 速 な 推 薦 処 理 が 可 能 な 点 が 挙 げ ら れ る ． 図 2.対 象 ク ラ ス タ と 対 象 部 分 空 間 で 区 画 さ れ る デ ー タ 領 域 を 計 算 対 象 と し て 切 り 出 す 図 2.の よ う に ユ ー ザ ー を 行 に , ア イ テ ム を 列 と す る 嗜 好 行 列 か ら 計 算 対 象 と な る 領 域 が 切 り 出 さ れ る イ メ ー ジ か ら 「 切 り 出 し 法 」 と 名 付 け る . 一 般 的 な ユ ー ザ ー ベ ー ス 協 調 フ ィ ル タ リ ン グ で は 過 去 の 嗜 好 デ ー タ(例 え ば 各 ア イ テ ム へ の 評 価 値 ベ ク ト ル)が 類 似 し て い る ユ ー ザ ー の 嗜 好 を 基 に 対 象 ユ ー ザ ー の 嗜 好 を 推 定 す る.こ の 類 似 し て い る と い う の は 嗜 好 を 表 現 す る 多 次 元 空 間 で の 距 離 的 な 近 さ と 考 え る こ と が で き る.こ の 近 さ を 計 算 す る と き に 従 来 手 法 の 多 く は 全 ユ ー ザ ー 集 合 と の 嗜 好 空 間 上 の 距 離 計 算 を 行 っ た. 一 方 , 切 り 出 し 法 は 距 離 が 近 い と 思 わ れ る ユ ー ザ ー 集 合 を 求 め て そ の ユ ー ザ ー 集 合 の 中 だ け で 距 離 計 算 を 行 う. さ ら に , ユ ー ザ ー が 直 近 の 利 用 履 歴 を 文 脈 と し て 部 分 空 間 選 択 を 行 っ た 上 で 距 離 計 算 を 行 う た め に 計 算 量 が さ ら に 削 減 さ れ,さ ら に ,よ り 文 脈 に 即 し た 推 薦 が 可 能 で あ る. 例 え て 言 え ば , あ る 人 が 咳 や 熱 な ど の 症 状 を 認 識 し 病 院 を 探 す と き , 全 国 の 病 院 の 中 か ら 探 す の で は な く 住 ん で い る 都 道 府 県 の 病 院 を 探 す は ず で あ る . ま た , 咳 や 熱 と い う 症 状 は い わ ば 文 脈 で あ り そ れ ら と 関 連 の 低 い 診 療 科 は 考 慮 か ら 外 し て 病 院 を 探 す で あ ろ う. 切 り 出 し 法 に お い て も ま ず は 自 分 に 近 い ク ラ ス タ を 探 す . そ の 際 に ク ラ ス タ の 重 心 と の 距 離 計 算 を 行 う の は い わ ば 都 道 府 県 の 県 庁 所 在 地 と 自 宅 と の 距 離 を 計 算 す る の に 似 て い る . さ ら に 文 脈 に 即 し た 部 分 空 間 選 択 を 行 う の は 病 気 の 症 状 に 照 ら し て 診 療 科 を 絞 る の と 似 て い る. つ ま り , 切 り 出 し 法 は 人 間 が 探 索 行 動 を 取 る 際 の 思 考 処 理 の 流 れ と よ く 似 た, 自 然 な 手 法 で あ る と 言 え る . 切 り 出 し 法 の ベ ー ス と な る 洞 察 に つ い て こ こ で 触 れ て お く と,人 間 の 嗜 好 に は 長 期 に 渡 っ て 変 化 し に く い 嗜 好 と,短 期 的 に 文 脈 に 応 じ て 変 化 す る 嗜 好 が あ り ,そ の 二 層 構 ︎の 嗜 好 に 基 づ い て 購 買 意 思 決 定 が 行 わ れ て い る と 仮 定 し て い る.こ の 長 期 に お い て 変 化 し に く い 嗜 好 を 計 算 す る の が 嗜 好 空 間 の 全 空 間 上 で の ク ラ ス タ リ ン グ に 対 応 し,短 期 的 に 変 化 す る 文 脈 に 応 じ た 嗜 好 の 計 算 に 必 要 な 処 理 が 直 近 の 閲 覧・使 用 履 歴 等 に 基 づ く 部 分 空 間 選 択 で あ る.人 間 の 嗜 好 の 本 質 に つ い て 考 え,そ れ に 基 づ い て 考 案 し た の が 切 り 出 し 法 で あ り,極 め て 自 然 な 方 法 で あ る と 考 え る . 自 然 で あ る が ゆ え に シ ン プ ル で あ り,実 装 コ ス ト も 比 較 的 低 く , ま た , 他 の 手 法 と 柔 軟 に 組 み 合 わ せ る こ と が で き る と 考 え る. 以 下 で は 説 明 の 便 宜 上 , ユ ー ザ ー ベ ー ス の 協 調 フ ィ ル タ リ ン グ を ベ ー ス と し て 具 体 的 な 手 法 の 手 順 を 説 明 す る . Step1: サ ン プ リ ン グ 過 去 の ユ ー ザ ー と ア イ テ ム に 対 す る 評 価 値 を 蓄 積 し た デ ー タ ベ ー ス か ら, 一 定 数 の ユ ー ザ ー を サ ン プ ル と し て ラ ン ダ ム に 抽 出 す る.
Step2: ク ラ ス タ リ ン グ ユ ー ザ ー を 行 と し, ア イ テ ム の メ タ デ ー タ (本 稿 で は 映 画 の ジ ャ ン ル を 用 い る)を 列 と し 、 評 価 値 を 成 分 と す る 嗜 好 行 列 を 仮 定 す る. ア イ テ ム の ジ ャ ン ル 等 の メ タ デ ー タ を 列 す る こ と で 行 列 の ス パ ー ス 性 が 抑 え ら れ る. さ ら に , 嗜 好 行 列 に 対 し て ク ラ ス タ リ ン グ を 実 行 し,各 ユ ー ザ ー ク ラ ス タ の 重 心 ベ ク ト ル を 取 得 し 保 存 す る. Step3: 対 象 ユ ー ザ ー の 最 近 傍 ク ラ ス タ の 特 定 推 薦 を 行 う 対 象 の ユ ー ザ ー の 映 画 の 評 価 値 の ジ ャ ン ル ご と の 平 均 を 成 分 と す る 嗜 好 ベ ク ト ル を 求 め , Step2 で 求 め た ユ ー ザ ー ク ラ ス タ の 重 心 と の 距 離 を 算 出 し, 最 近 傍 ク ラ ス タ を 特 定 す る . Step4: 対 象 ユ ー ザ ー の 文 脈 抽 出 と 部 分 空 間 選 択 対 象 ユ ー ザ ー の 最 近 見 た 映 画 の ジ ャ ン ル の 集 合 を ユ ー ザ ー の 映 画 鑑 賞 に お け る 文 脈 と み な す. 対 象 ユ ー ザ ー が 直 近 n 週 間 鑑 賞 し た 映 画 の ジ ャ ン ル を 次 元 と す る 部 分 空 間 と し て 選 択 す る. こ の 部 分 空 間 は ユ ー ザ ー の 文 脈 に 対 応 し た も の で あ る. 選 択 さ れ た 部 分 空 間 内 に お い て,協 調 フ ィ ル タ リ ン グ な ど の 既 存 の 推 薦 手 法 を 適 用 す る. 以 上 の , 切 り 出 し 法 に よ り,文 脈 に 適 応 し た 推 薦 が 大 幅 に 少 な い 計 算 量 で 可 能 に な る. Step5: 部 分 空 間 上 に お い て 協 調 フ ィ ル タ リ ン グ な ど の 推 薦 手 法 を 適 用 選 択 さ れ た 部 分 空 間 内 に お い て,協 調 フ ィ ル タ リ ン グ な ど の 既 存 の 推 薦 手 法 を 適 用 す る. 以 上 の , 切 り 出 し 法 に よ り,文 脈 に 適 応 し た 推 薦 が 大 幅 に 少 な い 計 算 量 で 可 能 に な る.
2.1.1. 切 り 出 し 法 の 効 果
1) 文 脈 に 適 応 し た 推 薦 を 可 能 に す る 2) デ ー タ 領 域 を 絞 り 込 む こ と で ,計 算 時 間 を 短 縮 す る 切 り 出 し 法 を 推 薦 シ ス テ ム の 前 処 理 部 に 組 み 込 む こ と で , 推 薦 シ ス テ ム が 文 脈 適 応 可 能 な も の と な り, ま た 計 算 時 間 も 大 幅 に 短 縮 さ れ る . 多 様 な ア ル ゴ リ ズ ム と 柔 軟 に 組 み 合 わ せ て 使 う こ と が で き, シ ン プ ル な 構 成 な の で 実 装 コ ス ト も 比 較 的 低 い た め 費 用 対 効 果 の 高 い 手 法 だ と 言 え る .2.2. 推 薦 システムの構 成 モジュールの自 動 合 成 方
法
推 薦 シ ス テ ム を 構 成 す る モ ジ ュ ー ル を 自 動 的 に 合 成 し, ユ ー ザ ー の 嗜 好 類 型 や 置 か れ た 状 況 や 条 件 に 適 し た 推 薦 シ ス テ ム の 構 築 の 自 動 化 手 法 を 提 案 す る. 従 来, 単 一 の 推 薦 シ ス テ ム を あ ら ゆ る ユ ー ザ ー や そ の 状 況 に 対 し て 適 用 さ れ て き た. し か し , ユ ー ザ ー の 嗜 好 の 多 様 化 や 急 な 変 化 , ま た グ ロ ー バ ル 化 に よ る 市 場 の 拡 大 に 伴 う ユ ー ザ ー の 国 籍 や 民 族, 文 化 的 多 様 性 の 増 大 に よ り , そ れ ら 多 様 な ユ ー ザ ー の 嗜 好 類 型 や ユ ー ザ ー の 置 か れ た 状 況 や 条 件 に 適 応 し て 柔 軟 に 推 薦 シ ス テ ム 自 体 の 機 能 や 構 を 変 化 さ せ る 必 要 が 生 じ て い る. 推 薦 自 体 の 自 動 化 が 推 薦 シ ス テ ム で あ る の に 対 し , 本 手 法 は 推 薦 シ ス テ ム 自 体 の 構 成 変 化 を 自 動 化 す る. 図 3 推 薦 シ ス テ ム の レ シ ピ 探 索 図 3 は 本 手 法 の イ メ ー ジ を 示 し て い る .推 薦 シ ス テ ム の 手 法 や 処 理 の 流 れ を 階 層 化 し,各 レ イ ヤ ー は 機 能 的 に は 同 一 ま た は 類 似 し た 性 質 を 持 つ 手 法 及 び モ ジ ュ ー ル で あ り,レ イ ヤ ー ご と に 手 法 及 び モ ジ ュ ー ル の 選 択 を 行 い ,そ れ ら 手 法 及 び モ ジ ュ ー ル の 組 み 合 わ せ の パ ス を レ シ ピ と 呼 ぶ ． こ の ア ー キ テ ク チ ャ ー は 人 工 知 能 の 研 究 の プ ラ ン ニ ン グ 領 域 の 手 法 と し て 知 ら れ る 階 層 的 タ ス ク ネ ッ ト ワ ー ク [5] に 近 い 考 え 方 を 推 薦 シ ス テ ム 構 築 に 応 用 し た も の だ と 言 え る. レ シ ピ に よ っ て 推 薦 シ ス テ ム の 性 質 や 特 徴 が 異 な り,ユ ー ザ ー の 嗜 好 類 型 ご と, ま た 置 か れ た 条 件 や 状 況 ご と に 最 適 な レ シ ピ を 探 索 す る 手 法 を 示 す. 以 下 に 本 手 法 の 具 体 的 な 手 順 を 示 す. Step1:推 薦 シ ス テ ム を 構 成 す る 処 理 を 実 行 す る モ ジ ュ ー ル を 実 装 す る. 推 薦 シ ス テ ム を 構 成 す る モ ジ ュ ー ル,例 え ば 類 似 度 計 算 や 回 帰 分 析 の よ う な 機 能 を 有 す る モ ジ ュ ー ル を 複 数 個 実 装 す る.類 似 度 計 算 に は 内 積 や ユ ー ク リ ッ ド 距 離 や 相 関 係 数 な ど 複 数 の 手 法 が 考 え ら れ る が,そ れ ぞ れ を モ ジ ュ ー ル と し て 他 の 処 理 が 可 能 な モ ジ ュ ー ル と 組 み 合 わ せ ら れ る 形 で 実 装 す る. Step2:役 割 的 に 共 通 す る モ ジ ュ ー ル を 整 理 し て 処 理 の 順 に 階 層 化. 図 3 の よ う に ,役 割 的 に 共 通 す る モ ジ ュ ー ル を ま と め て,順 に 並 べ た 木 構 造 を 形 成 す る . Step3:モ ジ ュ ー ル を 組 み 合 わ せ て レ シ ピ を 生 成 す る. 多 重 ル ー プ な ど の 方 法 で 各 階 層 か ら モ ジ ュ ー ル を 選 択 し レ シ ピ と し て 一 連 の パ ス を 作 る. Step4:ユ ー ザ ー の 類 型 や 条 件 の そ れ ぞ れ に 対 し て 各レ シ ピ を テ ス ト. 性 別 や 年 齢,ま た は ユ ー ザ ー の 嗜 好 ク ラ ス タ な ど で 分 類 で き る ユ ー ザ ー の 類 型 や,あ る ジ ャ ン ル か ら 商 品 を 探 そ う と し て い る な ど の 条 件 の 組 み 合 わ せ に 対 し て 各 レ シ ピ で 推 薦 を 行 う テ ス ト を 実 行 す る Step5:ユ ー ザ ー の 類 型 や 条 件 に 対 し て 最 も 精 度 の 良 い レ シ ピ を 記 録 し,今 後 は 同 じ 類 型 同 じ 条 件 の ユ ー ザ ー に そ の レ シ ピ を 適 用 す る. テ ス ト の 結 果 と し て 最 も 精 度 の 良 か っ た レ シ ピ を 対 象 の ユ ー ザ ー の 類 型 や 条 件 に 対 し て 最 適 な レ シ ピ だ と し て 記 録 す る.今 後 ,同 じ 類 型 の ユ ー ザ ー が 同 じ 条 件 に あ る 場 合 に 最 適 な レ シ ピ に 基 づ く 推 薦 シ ス テ ム で 推 薦 を 行 う.
