推薦システム実践入門5章で深堀りしたことのまとめ
これは、ストックマーク Advent Calendar 2022 18日目の記事です。
概要
-
O'Reilly Japan 推薦システム実践入門 における(理論的な)メインパートとも言える第5章に関して、追加で調べたり、読書会で同僚と議論したこと等、深堀りした内容をまとめた
- ただし、実験データ(MovieLens)を用いて検証しているのが5.9章までなので、そこまでの範囲でまとめた
- まとめたと言っても、ただの参考リンク集になってしまった感は否めないが...
背景
ストックマークでは、 Anewsというニュース記事×推薦×NLPなSaaSと、Astrategyというニュース記事×検索×NLPなSaaSを提供しており、推薦・検索は日常的に話題にあがるトピックとなっています。それもあり、今年度ストックマーク社内でも有志を募り、評判の高い推薦システム実践入門の読書会をしました。
私自身はAstrategyメインで昨年度までは開発をしていたのですが、検索と推薦は大変近しい関係(ということは本書でも述べられていますね)でもあり、かつAnewsの推薦にも興味があり、また前職でも推薦の技術は触れていため、検索・推薦は今後のキャリアを通してスキルを磨いていきたいという思いからこの読書会に参加しました。
そしてタイトルにもあるように、本書の5章では特に同僚たちと議論したり、知識の再確認をしたりした部分があったので、思い出のまとめ、備忘録、そして本書をもしこれから読む人にひょっとしたら役に立つかもしれないという思いから、その時のメモをまとめてみました。
余談
- 本記事を推薦系のアドベントカレンダーに投稿しても良かったかもしれないですが、ニュース記事×SaaSという弊社のコンテクストがあっての読書会だったこともあり、会社のアドベントカレンダーもあったので、こちらに投稿してみました
- 読書会で同僚達と本書の誤りかも?となった箇所について、https://twitter.com/Shingo_KAMATA/status/1564058634748715008?s=20&t=Km8QhNnxKeTBLv4jvVRXvw のスレッドにまとめています
- メールでそのうち連絡しようかなと思います
- あと、弊社のメンバーが投稿した推薦に関する論文が国際会議にアクセプトされました
推薦システム実践入門と今回の深堀りについて
読書会に参加したメンバーからも、本書は大変素晴らしいという声がありました。良い点をまとめると以下の3点になるかなと思います。
- 話題の範囲が広い
- 各話題について、実践するには最低限の情報がある
- コードがあり、環境がローカルになくてもColabで実行ができる
本書はそもそも概略の把握と、実際に手を動かして実践できるようになることがメインであるため、今回の記事で書いたような深堀りはそういう意味では実践するのにそこまで重要ではない情報だと思います。別の言い方をすると、識者である筆者の方々があえて詳細を記述しなかったという事自体がそれはそれで意味があると思います。なので、今回の深堀りは私が気になったから調べたという程度であり、この本を読みたい方はマストではない話だと考えています。気軽に読めるのに実践力が身につくのが本書の魅力だと私は感じましたので。
深堀りをしたサブセクションには、以下の観点で深堀りしたこと書いてみました。
- ポイント: この観点を抑えておくと後から理解につながったということをまとめました
- 例: EDA をした結果を抑えておくと、なぜこの評価指標を使ったかの理解につながる 等
- 議論・雑談: 同僚と、これはこうなんじゃない?と議論したこと、雑談して盛り上がった話をまとめました
- 例: MovieLens での推薦アルゴリズムはあくまでもNetflixライクなビジネスモデルのところで有効であり、ECサイトなんかでは同じようなことするにしても、利益率とか別の因子もありそうだと話した 等
- 数学の確認: 数学的部分(特に線形代数、確率統計の基礎)の確認をした部分をまとめました
- 例: 固有値固有ベクトルの定義は... 等
数学的議論をしている箇所では、大体は実数上での議論だと考えてください、例えば、行列についての議論で特に明記がない箇所については、成分は実数だとみなしてください。
深堀り
5.2章 MovieLensのデータセットについて
ポイント
- EDA(探索的データ解析)の結果と推薦の評価方法について
- EDAの結果、4に最頻値があるような分布がわかった(図5-6)が、これが、ランキング指標(Pricision@K, Recall@k)で、4以上の評価値アイテムを正解データとすることとつながってそう
- 例えば、3が最頻値で、4と5合わせても全体の1%みたいな分布の場合、閾値が3以上みたいに変わった可能性もある
- 自社で5章と同じような解析を行う場合、おなじランキング指標を使うにしても、閾値等はEDAをしてから定める必要がありそう
- EDAの結果、任意にユーザを選んでも20本以上は評価アイテムがあることが保証されたので、RMSEで5本をテストデータとして用いてもワークすることがわかる
- これも、5本というのが恣意的ではなく、20本以上の評価があるということが保証されていることがある程度考慮された数字に思われる
- ここも自社でやる場合は同じ様に、3本になるかもしれないし、10本までテスト用に残しても十分ワークするかもしれないし、EDAをして決める必要がありそう
- また、5本が最新の5本であることについて、7章での以下の言及にある通り、時系列データ的観点があるので注意
ある時点を定め、 ある時点より前のデータからなる学習データセットと、ある時点より後のデータから なるテストデータに分割する等、適切なデータセットの構築が求められます。
- 一応5章でも詳細については7章参照とあるが、RMSEの式の詳細だけではなく、この分割についての理由も7章で述べられてるので注意
- EDAの結果、4に最頻値があるような分布がわかった(図5-6)が、これが、ランキング指標(Pricision@K, Recall@k)で、4以上の評価値アイテムを正解データとすることとつながってそう
- Colab のコードでは統一フォーマット(5.2.4章)は使われていないので注意
- おそらく、Colabだとファイルのimportまわりがめんどいため?
- アルゴリズムごとにDLやテスト分割、評価等を実装している(これはこれでわかりやすい)
議論・雑談
- KPI と 5章での推薦アルゴリズムの話
- この章でやるような、MovieLensを解析する推薦アルゴリズムは、とりあえずユーザの評価値に沿うアイテムを推薦できればサービス全体が嬉しいという前提の話である
- しかし、ECサイトの場合、実際には利益率が高い商品や、在庫の処分をしたい商品のほうを売りたいという欲求もあるのではないか? といった議論をした
- そのあたりは、KPI が重要という 2章 にある話でもあることであり、5章はNetflixの様に、サブスクリプション型でありユーザ趣向をつかむのが重要というビジネスが仮定な部分はある気がした
- もちろん、それは推薦の基本だし、あらゆる推薦を考えるにしてもベースとしてふさわしいものではありそう
- もし、利得等も踏まえた推薦をやるならば、3.3.2 にあるように、サービスの信頼性の話も重要になってくるという指摘が同僚からあった
- また、2.2.7 にあるように、推薦によって検索由来の売上が下がるみたいな状況もあるため、実践をする際にはサービス全体のKPIやガードレールメトリクス等が重要になることは間違いなさそう
- このあたりは、8章の Uplift でも同様の議論をした
- UpliftScore を上げることがKPIと多少乖離する可能性はあるかもしれないということを議論した
- 例えば、利益をKPIと考えるならば、すべての購入率を上げるよりも利益率の高い商品の購入率だけをあげたほうがいい可能性もある 等
5.3 ランダム推薦
ポイント
- なぜ、user_id と item_id に対して、0始まりのインデックス割り振りを行っているか?
- valid_user_ids を出力したらわかるが、1000個抽出した user_id には欠損がある
valid_user_ids [1, (中略) 19, 22, 23, 24, 26,
- itemも同様に思われる
- 一方で、ランダムで生成した評価値行列は、必要な評価数の数しか無いので、 unique_userd_idsサイズ × unique_item_idsサイズしか要素はない
- そのため、user_id と item_id から、今回生成したランダム行列の要素にアクセスするための紐付けとして、0はじまりのIndexが必要となる
5.4 統計情報や特定のルールに基づく推薦
議論・雑談
- 評価値が高いアイテムを推薦する際に、評価数の閾値を設定していたが、これは検索においてもすごく重要
- 某サイトにおいてアイテムの評価順ソートに評価数の閾値がなく、結果、そのソートが微妙なものにになっており多くの人のニーズを掴まないであろうものが上位に来ていた という話をした
- ただし、そのサイトにおいて、評価数順のソートは結構一般ニーズを捉えている感じがあり、これは8.2.1 のセレクションバイアスから考えると面白く、結果的に評価数順は評価値が高いもののニーズもつかめているのかもしれないと感じた
- 炎上を除いたYouTube動画を考えると、コメント数が多ければ高評価もそれなりに多そうな感じがあり、批判コメントの効果が薄いサービスでは炎上は起きにくそうではある
5.5 アソシエーションルール
数学の確認
本書でPMIについて言及があったので、PMIについて少しだけ確認をした。以下の内容は、[1] を参考にした。
- 独立性
- 2つの確率変数
とX を考えて、以下を満たすとき、Y とX は独立であるというY p(X=x, Y=y) = p(X=x)p(Y=y) -
を仮定すると、次も独立であることと同値であるp(y) \neq 0 p(x|y)p(y) = p(x)p(y) p(x|y) = p(x)
- 2つの確率変数
- PMI(自己相互情報量)について
-
と定義される{\rm PMI}(x;y) = \log\frac{p(x,y)}{p(x)\,p(y)} = \log\frac{p(x \mid y)}{p(x)} = \log\frac{p(y \mid x)}{p(y)} - ここで、PMI が
とx の関連性を表していることは、独立性の条件から考察できそうy - 独立性が成り立つ場合、PMIは分母も分子も同じ値、つまり log1 となり 0 となる
- 一方で、何かしら依存関係があると、PMIの絶対値は増加することがわかる(分母と分子の値が離れる)
- https://ja.wikipedia.org/wiki/自己相互情報量 にある単語の共起の例が面白い
-
5.6 ユーザー間型メモリベース法協調フィルタリング
ポイント
- P119にて、詳細は付録Bとあるが、P118のピアソンの相関係数における変数の説明も付録Bにあるので、先に付録Bを読んでおいたほうがよいかもしれない
5.7 回帰モデル
数学の確認
本書において、回帰について言及はあるが、そもそも回帰がどのようなものかについては言及がなかったので確認をした。また、線形回帰についても言及があったので、それも確認した。以下の内容は、[2] を参考にした。
- 回帰: 入力の次元を
として、入力n \in \mathbf{N} から、出力\mathbf{x} \in \mathbf{R}^n を予測するような関数y \in \mathbf{R} (つまり、f: \mathbf{R}^n \rightarrow \mathbf{R} )をデータから求めるタスクである。データは、データの数をy=f(\mathbf{x}) とすると、入力データはm \in \mathbf{N} 、結果(出力)データは\mathbf{X}: (\mathbf{R}^{n})^{m} = \{ \mathbf{x_1}, \mathbf{x_2}, ..., \mathbf{x_m} \} と表される\mathbf{Y} : \mathbf{R}^m = \{ y_1, y_2 , ..., y_m \} - つまり、観測された入力と結果
個からいい具合の関数m を構成するということf
- つまり、観測された入力と結果
- 線形回帰: ノイズ
、パラメータ\mathbf{α} \in \mathbf{R}^m を用いて、\mathbf{w} \in \mathbf{R}^n と表せるような回帰y_k = \mathbf{w}^T \mathbf{x}_k + α_k - パラメータ
が\mathbf{w} に依存しないこと、言い換えれば、任意の入力データk に対して、\mathbf{x} が\mathbf{w} をうまく表現できる必要があり、このような都合の良いy を見つけることが線形回帰の目標である\mathbf{w} - そもそも、関数
が線形であるとは、以下の公理を満たすことであり、線形回帰においては、 入力(説明)変数f 中の要素\mathbf{x} に関してではなく、パラメータのx の要素\mathbf{w} に関して線形(w を変数としてみた場合の一次結合w で表される)であるということであるy = w_1x_1 + w_2x_2+...+w_nx_n+β - 加法性:
f(x+y) = f(x) + f(y) - 在一斉:
f(αx) = αf(x)
- 加法性:
- 入力変数が
のような3次元のデータの場合、\mathbf{x} = ({\bf sin}(x), x, x^3) はf に関する一次結合にはならないが、既に述べたように線形回帰の線形はパラメータに対してのものであるため、このような場合も線形回帰に分類されうるので注意[1]x
- パラメータ
5.8 行列分解について
数学の確認
行列の基礎知識
特異値分解が可能であることを確認するために、行列について、本当に基礎の基礎から確認をした。以下の内容は、 https://mathlandscape.com/ を参考にした。
- 行列の積
-
型行列とp×q 型行列においてのみ行列積×が定義されているq×r -
型、A:p×q 型 とすると、B:q×r =(A×B)_{ij} で定義され、\Sigma^{q}_{k=1} {a_{ik}*b_{kj} } 型となるA×B:p×r - 特定の型同士でしか演算が定義されていないので、積は行列一般に関して全域的ではない演算である
- 入れ替えるとそもそも積が定義できない場合があるので、積は一般に可換ではない
- 積の結合則は成り立つ(多分、項の数に関する帰納法で証明できるはず)
-
- 正方行列
-
型の行列のことp×p
-
- 対角行列
- 対角行列は正方行列に関して定義される
- 対角成分(
) 以外が0 であるような正方行列のことa_{ii} - 命題: 対角行列の
乗は各対角成分をn 乗するだけで求まるn - 証明:
に関する帰納法n -
のとき自明n=1 -
を仮定、n=k-1 のとき:n=k -
型、A:m×m 、B=A^{k-1} とするC=A^k - このとき、
と表せるC=A×B -
に対して、0 < i,j \leq m -
のとき:i=j c_{ij} = a_{ij} * b_{ij} = a_{ij}^n -
となり、命題が成り立つi \neq j: c_{ij} = 0
-
-
- 命題: 対角行列の
- 単位行列
- 対角成分が1の対角行列
- つまり、正方行列でもある
- 逆行列
- 正方行列
に対して、A を満たすA×B=B×A=I 、当然行列の積の定義からB も正方行列B -
をB と表すA^{-1}
- 正方行列
- 転置行列
- これは一般の行列
に対して定義できるA - 行列
型の転置行列A:p×q 型は、B:q×p となる行列であるb_{ij}=a_{ji} -
をB と表すA^T
- これは一般の行列
- 固有ベクトル、固有値
- ともに、正方行列に対して定義される
- (正方行列)Aの固有ベクトル
:\mathbf{x} となるA \mathbf{x} = λ \mathbf{x} \mathbf{x} - (正方行列)Aの固有値: 上記の
λ -
が\mathbf{x} の解となれば、スカラー倍したA \mathbf{x} = λ \mathbf{x} も解となりうるので、長さ1に正規化(正規化の意味は後述)することがよく行われるc \mathbf{x}
-
- 対称行列
-
を満たす正方行列A^T=A A - 正方行列
に対して、A は(実)対称行列となる((A×A^T) の転置の性質と(A×B)^T=B^T×A^T の性質で証明できる)(A^T)^T = A - 実対象行列の異なる固有ベクトル同士は直行(内積が0)となる
-
- 直交行列
- 以下を満たす正方行列
A×A^T = A^T×A = I - 同値な定義として、すべての列ベクトルが正規直交基底をなすというものがある
- 正規直交基底: 基底であり、かつ正規直交系となること
- 正規直交系: 大きさが1であり、自分自身とは内積が1、自分以外とは内積が0になるベクトルの集合
- 上2つは、本当は線形空間Vとかいろいろ述べないといけないので、かなりラフに述べている
特異値分解ができることの証明(5.8.2)
本書では、SVD分割が可能なことの詳細(証明等)は述べられていなかった。https://qiita.com/sakami/items/d01fa353b4e1f48623a8 の記事がその点についてわかりやすく解説をしているため、こちらを参考にSVDの確認をした(この記事を読み解くためにも、上の基礎知識は最低ラインなので抑えておいた)。
- 上の記事を読むにあたって、行列の型が以下であることを確認しながら読むと良いかもしれない
-
型A: a×b -
型U: a×n -
型Σ: n×n -
型V: b×n -
型V^T: n×b -
型A^T: b×a
-
フロベニウスノルムについて(5.8.2)
131P にでてくる関数
- ノルムとはベクトルの長さに相当するものであり、以下が有名(他にもある)
- L1ノルム:
\| \mathbf{x} \|_1 = \| x_1 \| + \| x_2 \| + ... + \| x_n \| - L2ノルム:
\|\mathbf{x}\|_2 = \sqrt{\Sigma_{i=1}^n x_i^2 }
- L1ノルム:
- フロベニウスノルムは、ノルムを行列に拡張したものの1つ
- フロベニウスノルム以外にも行列ノルムは存在する
- フロベニウスノルムの定義は、P131 の通りであるが、トレース(正方行列に対して定義される、対角成分の和)を用いて次のようにも表現できる
\| A \|_{Fro}^2 = {\bf trace}(A×A^T) = {\bf trace}(A^T×A) -
もA×A^T も正方行列になることに注意すれば、この等式が成り立つのは、行列積の定義を考えれば明らかA^T×A
-
- 2つの行列が近似していると、その差のフロベニウスノルムが小さくなる(特に、2つが一致している場合 =
だとO )になることも明らか0 - ただし、実際の Scipy によるアルゴリズムが本書にあるような、
の最小化問題を解くものになっているかまでは確認ができなかった\| R- PSQ \|_{Fro} ^2 - Scipy のソースコードにアルゴリズムの概要がなく、またこのファイルには frobenius norm の文字が無いため、アルゴリズの詳細まで読み解く必要があったので、断念した
- ただし、実際の Scipy によるアルゴリズムが本書にあるような、
- https://en.wikipedia.org/wiki/Low-rank_approximation#Proof_of_Eckart–Young–Mirsky_theorem_(for_Frobenius_norm) にあるように、行列の低ランク近似を考える場合、Eckart-Young-Mirskyの定理から特異値分解した結果に基づく次元削減が、フロベニウスノルムの意味で最近似となることが示されてたりもする
正則項について(5.8.4)
正則化(項)について、本書で言及はあるがどのようなものか解説がなかったので、確認をした。
- 正則化: 過学習を防ぐ目的で、情報を追加する手法
- 正則化項は、正則化のために目的関数に追加される項であり、上で述べたノルムに正則化項の影響(割合)を決めるハイパーパラメータである係数をかけたもの
- 正則化の詳細については、 https://qiita.com/c60evaporator/items/784f0640004be4eefc51 の記事がわかりやすい
- 似た用語に正規化というものがあるが、異なる概念なので注意
- 正規化は、例えば、単位ベクトルに変換する等の操作を指す
- 正規化と正則化の違いについては https://qiita.com/ryouka0122/items/a7fbad253680bb7f815e の記事がわかりやすい
凸関数について(5.8.4)
「非凸であるため、解析的に解くのが難しい」旨が本文中にあるため、凸関数とは何かについて確認をした。ただし、凸関数の恩恵は凸計画問題に落とし込むところにあると考えるので、まずは凸計画問題に関して述べ、その後に凸集合、凸関数について述べる。以下の内容は、[1]を参考にした。
- 凸計画問題(凸最適化): 実行可能領域が凸集合でかつ、目的関数が凸関数であるもの
- 凸計画問題は、一般的な最適化問題よりも最適化しやすい性質があり、例えば、局所的最適解が大局的最適解でもある
- 局所最適化とは、例えば目的関数を
とした最小化問題を考える場合、f が実行可能領域にあり かつx をx の任意の近傍としたときに、\bar{x} となる場合に、f(x) \geq f(\bar{x}) を局所最小解とよび、\bar{x} を任意の実行可能領域とした場合には、x を大域最小解とよぶ\bar{x}
- 局所最適化とは、例えば目的関数を
- ざっくり言えば、凸計画問題は、目的関数の値を改善していく方向に従ってさえいれば、解にたどりつける という解きやすさがある
- 凸計画問題は、一般的な最適化問題よりも最適化しやすい性質があり、例えば、局所的最適解が大局的最適解でもある
- 凸集合: へこみがない集合のイメージであり、集合
(ここではA とする)が凸集合であるとは、以下を満たすことであるA \subseteq \mathbf{R}^n -
\forall \mathbf{x_1}, \mathbf{x_2} \in \mathbf{R}^n, \forall t \in [0,1] \ \ (1-t) \mathbf{x_1} + t \mathbf{x_2} \in A - ここで、
は2点の線分を表すことを注意t \in [0,1] \ \ (1-t)\mathbf{x_1} + t\mathbf{x_2} - 方向ベクトル
で点\mathbf{d} を通る直線は、\mathbf{x_1} となる(t\mathbf{d}+\mathbf{x_1} のときt=0 )ことを踏まえると、2点\mathbf{x_1} を通る場合、\mathbf{x_1}, \mathbf{x_2} を\mathbf{x_2}-\mathbf{x_1} に代入すれば、\mathbf{d} である(t(\mathbf{x_2}-\mathbf{x_1})+\mathbf{x_1} のとき、t=0 となり、\mathbf{x_1} のとき、t=1 となる)\mathbf{x_2}
- ここで、
- つまり、凸集合上の任意の2点を結ぶ線分上の任意の点もまた、凸集合に含まれているということである
-
- 凸関数: へこみがない関数のイメージであり、関数
(ここでは、f とする)が下に凸であるとは、以下を満たすことであるf: \mathbf{R}^n \rightarrow \mathbf{R} \forall \mathbf{x_1}, \mathbf{x_2} \in \mathbf{R}^n, \forall t \in [0,1] \ \ f((1-t) \mathbf{x_1} + t\mathbf{x_2}) \leq (1-t)f(\mathbf{x_1}) + tf(\mathbf{x_2}) - つまり、
のグラフは、グラフ上の任意の2点を結ぶ線分以下のとこに常に位置しているということであるf - https://ja.wikipedia.org/wiki/凸関数 の図にあるように、下に凸な二次関数を考えるとイメージがつきやすいかもしれない
- 今回のMFの式が凸関数ではないことを証明するには、凸関数の定義から確認することは難しそうに思われる(つまり、
で反証をするのは難しそう)\exists \mathbf{x_1}, \mathbf{x_2} \in \mathbf{R}^n, \exists t \in [0,1] \ \ f((1-t) \mathbf{x_1} + t \mathbf{x_2}) > (1-t)f(\mathbf{x_1}) + tf(\mathbf{x_2}) - 実は、関数の凸性の判定にはヘッセ行列を使った方法 https://ja.wikipedia.org/wiki/ヘッセ行列#凸性の判定条件 もあり、こちらを用いるのがベターかもしれない
- https://math.stackexchange.com/questions/393447/why-is-the-non-negative-matrix-factorization-problem-non-convex が参考になりそう(おそらく今回も同じ様に non convex(非凸性)を示せるものと思われる)
ロジスティック関数(5.8.6)
ロジスティック関数がなぜここで使われているかに関して考察をした。
- ロジスティック関数は、機械学習等でよく見かける関数で、シグモイド関数とも呼ばれる(こちらのほうが有名かもしれない)
- ただし、厳密には、これは標準シグモイド関数と呼ばれるべきものであるらしい(以下の記事を参考)
- 標準シグモイド関数は以下のようなグラフとなる(グラフは上記Wikipediaより引用)
- シグモイド関数は、ニューラルネットワーク研究における活性化関数(ニューロンの発火を模したもの)の1つであり、発火の閾値が連続的であり([0,1]であるため、確率的とも言える)、 微分が可能という特徴がある
- 同じ様にニューロンの発火を真似したもので、ステップ関数があるが、こちらは、微分不可能である
- シグモイド関数はステップ関数を連続的にしたものと見なすこともできる
- 機械学習の2値分類では、活性化関数にシグモイド関数が使われることが多い
- 学習によりパラメータを更新する際に、関数が微分可能であることが望まれるため、(ステップ関数ではなく)シグモイド関数が使われてる
- BPR においても、機械学習(の二値分類)と同様の理由で、シグモイド関数が使われていると推測する
FMの計算オーダー(5.8.7)
本書において、FM では、パラメータ数が特徴量の数の二乗ではなく線形に増える旨が述べられていたが、このあたりの確認をした。
- 本書で述べられていた特徴量の2乗というのは、おそらく二項係数から来ており、素朴に考えた場合(
のようなパラメータを考えた場合)、w_{j,k} 個の特徴量からn 個の組み合わせを考慮したパラメータ数は2 個になることを指しているのだと思われる\binom{n}{2} = \frac{n(n-1)}{2} - 一方で、今回のように パラメータを
のように素朴に用意せず、内積で計算を行うのであれば、パラメーはw_{j,k} のものしか増えないため、線形となるw_j
- 一方で、今回のように パラメータを
- さらに、FMの計算のオーダを落とす工夫が https://speakerdeck.com/kenjih/factorization-machines?slide=9 が述べられていたので確認をした
-
に分解する式変形が可能な理由(上記資料の式変形2行目)について1/2 -
が ともにi, j を動くとなると、元の(二項係数の)結果が倍になる+自分自身との計算が追加されるn - ベクトル内積、スカラー積は対称性が成り立つ
- よって、
がともにi,j を動いた場合を半分にした値(これは、自分自身との計算結果の半分が元の式より増えている)から、自分自身との計算結果の半分を引いてやれば、元の式と同じ値になるn
-
- あとは、オーダは(走査するデータの)ネストの深さに起因することを考慮すれば、ネスト不要な2乗計算に落とし込んで最大のオーダを減らしており、全体のオーダが削減されていることがわかる
-
議論・雑談
- SVD での行列分解のメリットがいまいち見えないという話があった
- 行列分解の例にある、ファンタジー度合い、アクション度合いの例はわかった
- 一方で、SVDの例では、評価値行列Rに最適化しようとしているが、これだと、結局穴埋めした評価値に寄せるだけなので、あまり意味がないのでは?となった
- あくまで行列分解の例として取り上げているだけでは? ということと、一応近似なので=とはならない(けどそれが意味のある値になるかは?)ということを話し合って、次に進んだ
- そもそも、MFのほうが実践的であるということなので、そちらを使えばよいともなった
- 誰かが MF を Netflix Like SVD と言及しているのみて面白いなと思った
- 適切な表現家はわからないが、わかりやすいと思った
-
https://twitter.com/mirucaaura/status/1570628629297795073?s=46&t=NjRCdmGf4eGv3lEQwcUkNQ でレコメンドの話が盛り上がってるのを観測!
- これでは、非負行列分解のほうがNetflixの手法と言及されており、本書とどこが違うか考えた
- 重要なのは
がどこを走るかだと思っていて、ここが本書での\Omega であれば本質的には本書のMFと同じなのかな?と思ったR^+ - これは、本書の注釈にあった、欠損のまま非負行列分解を扱える手法に該当する?
5.9 自然言語処理手法の推薦システム応用
数学の確認
確率統計の基礎
LDAの理解のため、こちらも線形代数と同様に、確率・統計の基礎知識を確認した。
以下は、[2]を参考にまとめた。
-
確率密度関数/確率質量関数
-
次元ベクトルM の各要素が連続か離散か?\mathbf{x} - 連続の場合: 次の2条件を満たす関数
を確率密度関数というp(\mathbf{x}): \mathbf{R}^M \rightarrow [0,1] p(\mathbf{x}) \leq 0 -
をp(\mathbf{x}) で積分した値が1に等しい\mathbf{x}
- 離散の場合: 次の2条件を満たす関数をこちらは確率質量関数という
p(\mathbf{x}) \leq 0 -
をp(\mathbf{x}) の各要素で和を取った値が1に等しい\mathbf{x}
-
-
確率分布
- 確率密度関数や確率質量関数で定義される分布
- 代表的な分布には名前がついている
- 分布はパラメータを取り、パラメータで分布のグラフが定まる
-
期待値
- 確率分布
と関数p に対して、以下のように定義されるものf <f(\mathbf{x})>_{p(\mathbf{x})} = \int f(\mathbf{x})p(\mathbf{x}){\rm d}\mathbf{x} - 期待値は、
が積分除去されるため、\mathbf{x} の関数にはならないことに注意\mathbf{x}
- 確率分布
-
平均
-
の期待値のことf(\mathbf{x})=\mathbf{x} - 余談: 期待値と平均は別の概念だと思った方いませんか(自分だけかも)?しかし、実は平均は期待値の一種だったのです
- 平均は合計を個数でわったもので、期待値は確率(割合)に量を掛けたものであるが、本質的には同じようなものを求めていると捉えると自分は納得いきました(離散の場合の話になりすが)
-
-
多項分布:
-
なる分布p(\mathbf{x};N;\mathbf{\pi}) = N! \Pi_{k=1}^{K} \frac{\pi_k^{x_k}}{x_k!} -
、N \in \mathbf{N} であり、\mathbf{x} \in \mathbf{N}^K \ \Sigma_{k=1}^K{x_k} = N は\mathbf{\pi} 次元の確率ベクトルであるK - wikipediaの記述のが直感的かもしれない?
-
- 多項分布の平均は
である<x_k> = N \pi_k - 多項分布は、試行回数
と各事象の確率(分布)N をパラメータとして、\mathbf{\pi} 回の施行でN 次元の事象がK となる場合の確率を返す関数\mathbf{X} - 例:サイコロを複数回投げたときの確率(例:3回投げて 1が2回、4が1回、残りは0回ずつでる
確率等)N=3, \mathbf{x} = (2,0,0,1,0,0) - (今回は触れていないが)カテゴリー分布の多施行版、二項分布の多次元版ともいえる
- 分母の階乗が、各事象の回数として同値類をまとめているのがわかる(回数が同じであれば出現順は無視している、1,2,1 と 1,1,2 は同じにしている)
-
-
ディレクリ分布:
-
なる分布p(\mathbf{\pi};\mathbf{\alpha})=\frac{1}{B(\mathbf{\alpha)}}\Pi_{k=1}^K \pi_k^{\alpha_k-1} -
であり、\mathbf{\alpha} \in \mathbf{R}^K は(多項分布のときの表記と同じ様に)\mathbf{\pi} 次元の確率ベクトルであるK - ディリクレ分布の平均は
である<x_k> = \frac{\alpha_k}{\sum_{i=1}^K\alpha_i} -
が自然数の場合を考えると、ある\alpha_k 個の事象についてK 番目の事象がk 回発生した場合に、その事象の生起確率が\alpha_k-1 である確率である\pi_k - つまり、パラメータ
から、確率ベクトル\mathbf{\alpha} を生成する確率を返す\mathbf{\pi} - サイコロで考えると、カテゴリー分布が出る目の分布に対して、ディリクレ分布は目のでやすさの分布と捉えることもできる
-
- ベータ関数:
B(\mathbf\alpha) =\frac{\prod_{k=1}^K\Gamma(\alpha_k)}{\Gamma(\sum_{k=1}^K\alpha_k)} - ガンマ関数:
\Gamma(x)=\int t^{x-1}e^{-t}\,{\rm d}t\qquad - 階乗を一般化したような関数である
-
-
共役事前分布について(参考まで)
- ディリクレ分布で生成される
が多項分布のパラメータ\pi であるように、分布間にある種の関係があり、共役事前分布とよばれる\pi - ベイズ推定においては、これからの関係は重要となってくる(が、難しすぎるので詳細は割愛)
-
https://machine-learning.hatenablog.com/entry/2016/03/26/211106 の記事がわかりやすい
- リンク先にあるように、多項分布の共役事前分布としてディリクレ分布がある
- ディリクレ分布で生成される
LDAについて(5.9.2)
本書では、LDAがどのように学習されるか(どのようなグラフィカルモデルとなるか)については触れられていなかった。 https://qiita.com/K_Noguchi/items/2f0579ca51f5329a4008 の記事がすごくわかりやすかったので、この記事を参考に確認をした(この記事を読み解くためにも、上の基礎知識は最低ラインなので抑えておいた)。
- 図の左側
- ディリクレ分布のパラメータ
から、ドキュメント\mathbf{\alpha} におけるトッピック数d 次元のトピックの確率ベクトルを生成K - 生成されたトピック確率ベクトルとドキュメント
の単語数d から、文章中のトピックの頻度(あるトピックに該当する単語がいくつあるか)を生成N
- ディリクレ分布のパラメータ
- 図の右側
- ディリクレ分布のパラメータ
から、トピック\mathbf{\beta} における語彙数k 次元の単語の確率ベクトルを生成V
- ディリクレ分布のパラメータ
- 図の中心
- ドキュメント中の単語数
と、文章中のトピック単語の頻度と、トピックごとの単語の分布から、BoW(単語の頻度)を生成N
- ドキュメント中の単語数
- グラフィカルモデルはわかりやすいが、実際には観測が最初でそこからパラメータを決めていくのが実際の流れになりそう
- つまり、観測が先であり、そこから文章のトピック分布や、トピックごとの単語の分布等を計算をする
- 参考: https://aiacademy.jp/media/?p=3063
- 観測の
をBoWという単語頻度ではなく、文章w_{d,n} 中のd 番目の単語n にすることで、多項分布のところを試行回数を落としたカテゴリ分布にしているような解説もあるw_{d,n} - https://en.wikipedia.org/wiki/Latent_Dirichlet_allocation#Generative_process とか
- 逐次学習すること考えるとこちらのグラフィカルモデルのほうがよかったりするのかな?
- LDAを協調フィルタリングに利用する手法について、最初見たときは驚きがあったが、ディリクレ分布がある有限次元の確率分布(確率ベクトル)を生成し、多項分布が、有限次元の有限回施行の分布を生成することから、生成対象がBoW(単語の頻度)ではなく item_id の頻度であっても、有限なものの生成という部分では変わらないということを踏まえれば、そういう発想に到れるのかなと思った
- 分布の知識があれば、それを応用できるものの発想が広がる
- 同じ item_id が一度しか現れないような系列の場合、 BoW みたいに回数の情報がなくなり最後の多項分布さがなくなりそうなので、複数登場するような履歴とかで適応するのが良さそう
W2Vについて(5.9.4)
前に https://speakerdeck.com/kamata_shingo/zi-ran-yan-yu-chu-li-toqing-bao-jian-suo-nituite-nlp-and-ir?slide=22 にまとめたので、これをもとに確認した。
その他の章で雑談・議論したこと
7章
- 評価の方法について
- 検索システムの本にもよく出てくる指標であった
- 同じタイミングで検索システム ― 実務者のための開発改善ガイドブックを読んでたのもあり、より理解が深まった
8章
- ニュース記事の類似記事集約大事めっちゃわかる
- 類似記事集約については弊社でもテックブログを書いている
- 文章ではなく、サムネ画像が類似記事集約に役立ちそう!と考えたこともあったけど、内容が違うけどサムネは同じ記事もあったり(例えば、コラムなどは回が違うけどサムネが同じだったり)して、それでは判断できないとわかるなど、奥深い
- 補完、キーワードサジェストも大事わかる
- 一方で、最近ではベクトル型の検索も流行っており、implicit にシノニム等対応するか、サジェストの様に explicit に対応するかというのは悩みどころでもある
他にも、弊社サービスならどうするべきか?等の話も読書会では出て盛り上がりました!
が、センシティブなものもあるのでここでは書けないのが残念です。。。
感想
- 本書はすごくバランスがいい本だと、記事を書きながら改めて感じさせられた
- 深堀り記事といいつつ、肝心な部分はだいたい外部記事におまかせしてしまったのは反省...
- とはいえ、すでによい解説があるのでそこの車輪の再発明的なことをするのはあまり意味がない気も
- そもそも、参考記事読むための前提知識が不足しているみたいな状況だったので、数学の確認でそのあたりをまとめられたのはよかった(けど、基礎力がないことはそれはそれで反省)
- 以下も深堀りをしたかったが、時間の都合上できなかったので、どこかでまとめたい
- 5.5.4 アソシエーションルール の アプリオリアルゴリズム による高速化について
- W2V と PMI の関係について触れられいた部分を理解したい
- 本書中で一番印象に残ったのは、TopicModelとW2Vの部分にあった、item_idを利用してNLPの手法を協調フィルタリングで応用するところだった
- 記事を書いていたら、自然言語処理と推薦も近しいなとも感じた
- 例えば、PMIもNLPでよく出るし、トピックモデル等もいわずもがな
- 以前に、情報検索とNLPについてまとめたけど、推薦とNLPについてもお互いの関係をまとめてみたいかも
- ただ、例えばディリクレイ分布が有限次元の確率ベクトルを生成できるという点から、単語の分布にもitem_idの分布にも応用できたように、ドライに見れば、有限集合、離散データ一般に用いられる数学的手法という意味での関連でしかないのかもしれないが...
読書会につきあってくださった同僚、時々推薦について一緒に雑談してくださっている同僚、確率統計の勉強会につきあってくれている友人達のおかげでいろいろ理解が深まりました、みなさん大切な仲間なのでこれからも仲良くしてください
参考文献
- [1]言語処理のための機械学習入門 高村大也著/奥村学監修
- [2]ベイズ推論による機械学習入門 須山敦志著/杉山将監修
(Web記事の記載は割愛)
-
にこのような自由な変換がされていると考えると、\mathbf{x} のグラフが必ずしも直線的なものに限られない。この様に、入力(説明)変数に何かしらの変換f を与えより表現力を拡張することもできる。この様な\phi を基底関数 とよび、基底関数は非線形なものも採用される。基底関数を用いて拡張した線形回帰の手法は 線形基底関数モデル とよばれる。 ↩︎\phi
Discussion