Re:ゼロから始めるML生活

どちらかといえばエミリア派です

推薦システム入門(その1:古典的手法)

最近こちらの本を購入しました。

推薦システム: 統計的機械学習の理論と実践

推薦システム: 統計的機械学習の理論と実践

レコメンデーションの勉強で、推薦システムとは何ぞやという基礎の基礎から勉強することにしました。 この本、確かにちゃんと書いてあるので非常におすすめなんですが、めちゃくそ難しかったので全部頭で理解するには時間かかりそうです。

まあ、ゆるーく勉強していくので、ゆっくりなのは許してくださいな。

推薦システム is 何?

この本でいう推薦システムはこんなふうに紹介されてます。

推薦システムはさまざまな文脈においてユーザに「最良」のアイテムを推薦するコンピュータプログラムである。 何をもって良い推薦とするかは、総クリック数、総収益、売り上げ総計などの最適化の目的に依存する。 推薦システム: 統計的機械学習の理論と実践

わかりやすい例としては、やはりECサイトやWebページの端についているような広告がこれらに該当します。

このようなシステムの最もシンプルな構成としてはこんな感じになるかと思います。

f:id:nogawanogawa:20190921071716j:plain:w500

ブラウザでの操作を蓄積し、それを学習してモデルを更新します。更新されたモデルを推薦システムに適用し、実際のWebページ配信ときに推薦システムを呼び出して推薦するアイテムを決定します。

アイテムの寿命などの特性によって、モデルの更新頻度は考慮する必要があります。頻繁にアイテムが変更される場合には、数分単位でモデルの更新が必要になったりするようです。

推薦システム内部でやっていること

じゃあ内部的にはどんなことしてるかって言うと、ざっくりとはこんな感じになってます。

f:id:nogawanogawa:20190921071734j:plain:w500

  1. コンテンツのフィルタリングと理解
    • コンテンツの素性などからコンテンツを分類し、品質の低いコンテンツをフィルタリングしていく
  2. ユーザー特性モデルの構築
    • ユーザーの特性(年齢、性別、行動履歴など)から"ユーザーはこういう人"だと定義
  3. スコアリング
    • 機械学習によって、対象ユーザーに対する各コンテンツの評価値を計算
  4. ランキング
    • スコアリングに加えてビジネスルール(大人の事情的なやつ)を踏まえてコンテンツをランキングする

推薦システムの評価

推薦システムを作ったら、システム自体を評価して改善していくことが求められます。

  • オフライン評価
    • ユーザーに使用して貰う前に、過去の実績を元にしたシステムの評価
  • オンライン評価
    • ユーザーに使用してもらった、実際の評価
  • スコアリングの評価
    • スコアリングが期待通りに行われているかの評価
  • ランキングの評価
    • ランキングが期待通りに行われているかの評価

この辺を行うので、目的関数は事前に注意して決めておく必要がありますよって話です。

古典的手法

まずは、古典的な推薦システムの中心となる考え方を確認します。

アイテムの表現

まず、アイテムを数値として表現することを考えます。 アイテムが何をさすかによって、素性は画像だったり単語だったりいろいろですが、それらを組み合わせて、アイテムを、ベクトル表現していきます。

タクソノミ

あまり聞き慣れない用語だったので調べてみると、

対象領域に含まれる事物について、その性質や特性の違いによって異同を定め、領域全体を体系的に分類・秩序立てていくこと。あるいはそのような分類を行う方法や規準を考察する研究分野、ないし結果として得られる分類体系をいう。 ITmedia エンタープライズ

だそうです。要するに、人間がカテゴリを決めてあげて、アイテムをそのカテゴリにマッピングしてあげることでone-hot的にアイテムをベクトル表現化するみたいですね。

いろいろ細かい技法はあるようですが、アイテムをカテゴライズすることでベクトル化してくようです。

Bag of Words (BoW)

BoWは「アイテムはそのアイテムに含まれる単語によって特徴づけられる」という予想に基づいたやり方になります。 コーパス内の単語をすべてベクトル表現し、アイテムはそれらの単語の分散表現で識別します。

単語ベクトルはどうやって取るんじゃい?ってなるかと思いますが、ベースは単語にIDを降ってあげてるようです。 それをone-hotにしたものを単語ベクトルとして使うようです。あくまで最も単純な方法ではですけどね。

作った単語ベクトルは

  • 2値表現
  • tf
  • tf-idf

らへんから選んでBoW化していくようです。

その他、one-hot表現だと次元がとんでもないことになるので、次元圧縮等がポイントになります。 イメージは、w2vの分散表現にして、バカみたいに大きい次元をそこそこ大きい次元の空間に落とし込んでいくんだと思っていただければ。 今だと学習済みのw2vモデルがあったりするのでそのへんもうまいこと使っていくんだと予想してます。

www.nogawanogawa.com

トピックモデル

トピックモデルとは、文書が複数の潜在的なトピックから確率的に生成されると仮定したモデルです。

www.albert2005.co.jp

トピックモデルでは、アイテムは複数のトピックから生成されると考えます。 含まれる単語が各トピック内で出現する確率分布をもち、それらを合算すると、アイテムとしてどのようなトピックで構成してるかを表現できるようになります。

これにより、確率の高い上位数件のトピックがアイテムを強く表現してると推測できます。

ユーザーの表現

ユーザーの表現には、

  • プロファイルの利用
  • アイテムとの相互作用の記録をもとに算出

などが考えられます。 扱うデータの種類こそ違えど、あとはアイテムの表現と似たような感じでベクトル表現にしたりします。←適当

推薦の方法

上で、アイテムとユーザーをそれぞれベクトル化できたので、これらを使って推薦する仕組みについて見ていきます。

素性ベクトルベースの手法

教師なし

アイテムとユーザーの素性ベクトルが得られれば、それを多次元空間にマッピングする事で教師なしとして推薦が可能です。

この場合、アイテムとユーザーは同一ベクトル空間の点で表すことになります。アイテムとユーザーが同じbowで表現されることでこれが実現できます。

教師あり

ユーザーとアイテム間のレイティングを教師データとし、未知のレイティングを予想します。

例として、

  • バイナリレイティング
    • ユーザーがアイテムに与える影響を0,1で表現する(クリックの有無など)
  • 数値型レイティング
    • ユーザーがアイテムに与える影響を数値で表現する(ユーザーからの点数評価など)
  • 順序レイティング
    • ユーザーがアイテムに与える影響を順序で表現する(人気上位何位に位置するかなど)
  • 共起嗜好性スコア
    • ユーザーがアイテムAをアイテムBより好む度合い

などが

これらのレイティングは正則化すると過学習の恐れが低下するらしい。です。。。

協調フィルタリング is 何?

協調フィルタリングのモチベーションはこんな感じです。

f:id:nogawanogawa:20190921074132j:plain:w500

前提として、

  • ユーザーの特性がわかっている
  • アイテムの特性がわかっている
  • 過去のユーザー-アイテム間の行動の履歴が残っている

とすると、それらを元に、

  • 似たユーザーは同じものを欲しがる
  • 同じユーザーは似たアイテムを欲しがる

という期待を元に推薦していくことになります。

ユーザーが未知のアイテムに対して影響があるかどうかは、似たユーザーの既知の影響結果の荷重平均で表現できると言います。 似たユーザーがどんな振る舞いを起こしたかから、未知のアイテムに対する影響を予想します。

このとき、"似たユーザー"や"似たアイテム"の度合いの数値化には類似度関数が使われる。ユーザー間の類似度関数は、この本ではピアソン相関が一般的だそうです。 そして、近傍をどこまでにするかは、実証的評価が必要だとしています。

加重平均の係数は、類似度関数の出力に応じて重み付けしてあげます。

こうして、全ユーザーと全アイテムの影響を表したマトリクスが出来上がります。 この行列の要素のうちいくつかは既知であるので、それを教師データとしてロスを最小化するように学習させることで最終的な影響の確率を得ます。

探索と活用

根っこにある基本的なアイデアについてはすでに書いたので、推薦システムを構築するということに頭を傾けてると、一つ問題が出てくるのでそれを見ていきます。 いわゆる多腕バンディット問題と呼ばれるやつです。

多腕バンディット問題 is 何?

多腕バンディット問題は強化学習関係の話でよく出てくるテーマですね。

広告Aと広告Bの2つがあって、それらのどちらを推薦するか悩んでるとします。 なるべくたくさんのクリックを集めることが目的関数となっていますが、AとBの広告がどれだけの確率でクリックされるかわかりません。(←ココ重要)

今、10回試行してAが6回クリックされてBが2回クリックされたとします。 ところが、実際にはBは2回に1回クリックされる品質の広告で、Aは10回に1回クリックされる品質の広告でした。

この状況で正直にやると、広告会社は試行の上では優秀そうに見える品質の低いAの広告を打ち続ける問題があります。(多腕バンディット問題)

これを防ぐためには、すべての広告を全体的に引く必要があり、予測者は良いアルゴリズムに従って情報の活用と探索をバランスする必要があります。

(参考)

www.ai-gakkai.or.jp

ということで、実際には多腕バンディット問題を解くために、一見よくなさそうなアイテムであっても一定のアルゴリズムに則って推薦されないといけないってことになります。

  • ベイジアンアプローチ
    • 事前分布と事後分布を踏まえた上で最適解を求めるらしいです(←イマイチ実感が湧いてないです)
  • min-maxアプローチ
    • 最良の手を引き続けたときと実際の差分(リグレット)をもとに、最悪の手を引き続けたときのパフォーマンスを最小にする
  • ヒューリスティックなバンディット戦略

この辺が、戦略として有望らしいです。

感想

むっっっっっっっっず。

いやはや、レベルが違いました。バリバリ数式出てくるし、わけわかんないっすね。 なるべく数式使わない記事にまとめようとおもいました。