KB系 (link prediction) まとめ - ブログではないです

最近KB周りがマイブームなので実装の参考も兼ねて KB + Text => Great KB な論文を多読してみたとそこから辿れる少し前の論文を斜め読み。基本的には (subject, relation, object) からなるtripleをグラフの2ノード間のラベル付きエッジとみなし、それぞれのノード・エッジのembeddingを元にそこにリンクが存在するか否かを推定するLink Predictionタスク。論文による違いは多くの場合tripleに対するスコア関数と、外部情報（グラフ構造や品詞による制約etc）をどう程度使うか。データセットは大体FreeBase(FB15k, FB15k-237, FB20k..)とWordNet。

ところでFB15kなんかは配布されている形ではentityが全部 /m/05qtj みたいなidの形になっている上に、すでにWikidataに移行してしまっているため具体的なentity名への変換APIがもう使えなくなってしまっている（Wikidataの記事との対応を取ったdumpはあるがFB15kの8割ちょいくらいしか網羅できていない）のだが、グラフ構造だけで完結する話はともかく他タスクと絡めて使いたい場合はどうしているんだろう・・・。

A Review of Relational Machine Learning forKnowledge Graphs [Nickel+, IEEE'16]

IEEEのinvited paper。長い。分野の相場観があまり分かってなかったので読んだ。特によく分かってなかった損失周りをどうするのが一般的なのかについて、既読の論文でもそうなっていたようにクロスエントロピー + L2正規化もしくは sigmoidを用いてスコアを確率にした上で ${ \sum_i \displaystyle 1 - p(triple_{neg_i}) + p(triple_{pos_i})}$ に同じく正規化項を加えたものが一般的なようだ（この場合正例と負例の数は同じにする）。

またあまり気にしていなかった負例の作り方についても少し議論があり、正例以外のtripleを全て負例とする、つまり完全にランダムに3つの要素を選択して（正例にない）負例を作るよりも (subject, relation, object)のうちsubject or object とrelationの2つは固定して1つだけ入れ替えることで、比較的plausibleな負例を作るというアプローチもあるとのこと。

Representing Text for Joint Embedding of Text and Knowledge Bases [Toutanova+, EMNLP'15]

グラフ間のrelationのtextualな要素に注目した研究。例えば「設立」という単語に関係するグラフであってもそのrelationとしてはco-founded, founder_of, with_founders_of, helped_establishなどたくさん存在する。そうしたrelationのうち低頻度のものは学習が難しくなるが、他のrelationにも出てくる"founder"という単語からなんとなくそのrelationの意味は推測出来る。

そこでConvと呼ばれる提案手法では例えばtripleを "SUBJECT co-founder of OBJECT" という文だとみなし，係り受け解析を行った結果の "SUBJECT $\rightarrow_{appos}$ co-founder $\rightarrow_{prep}$ of $\rightarrow_{pobj}$ OBJECT" というトークン列をCNNでエンコードして得たベクトルからスコアと確率を得る。従来のスコア関数で推測した確率による損失との重み付け和に対して最適化することで従来手法との共存が可能であり、既存のスコア関数であるmodelF, modelE, distMultなどに対して実験。結果はfiltered(後述)の条件でFB15k-237に対して最高でMRRが0.424, HITS@10が61.1。

確率と損失関数周りがよく分かっていない。彼らはtripleの集合 $\tau$ のtriple $(e_s, r, e_o) \in \tau$ に対して

確率を $p(e_o | e_s, r ; \Theta) = {{e^{f(e_s, r, e_o; \Theta)}} \over {\sum_{e' \in Neg_{(e_s, r, ?)}} e^{f(e_s, r, e' ; \Theta))}}}$
損失を $L(\tau, \Theta) = -\sum_{(e_s, r, e_o \in \tau)} log p (e_o | e_s, r; \Theta) -\sum_{(e_s, r, e_o \in \tau)} log p (e_s | e_o, r; \Theta)$
としている。

確率について、負例全部を使うと計算が辛くなるので既存研究（Chang+'14], [Yang+, '15], [Toutanova+, '15], [Chen+, '15]）にならってentityのtypeによって少なくともその関係を持ちうるものに絞っている。ところで確率の分母ってこれで良いんだろうか・・・？（別に総和が1になっている必要は無いからNegのスコアを下げられるならなんでもいい？）損失関数について、この形だと実質relationが常に双方向のグラフであるとして扱う事になると思うのだがそれは大丈夫なのか？（FreeBaseのrelationって全てそういうラベルなんだっけ？）

Translating Embeddings for Modeling Multi-relational Data [Bordes+, NIPS'13]

前述した論文で評価の際の条件として出て来るraw, filteredの設定について引用がここにあったので確認を兼ねて。テストの際にはあるtripleに対しsubject, relationを固定した状態で全通りのobjectについてスコアを計算し、その逆（subjectの方を入れ替え）についても計算。その上で実際のtripleが何位に来ているかの MRR (Mean Reciprocal Rank) やHITS@k (k位以内に正解がいる割合) で評価する。その際に、いまテストしているtripleとは異なる正解の（trainやvalidに存在した）tripleに対して高いスコアを付けてしまう事があるが、それをちゃんと抜くか抜かないかがraw/filteredの違いらしい。ちなみにあまり分かっていないのだがどうしてランキング系の評価はMean Rankより MRRが好まれるのだろう・・・？逆順位って直観的にどの程度良いのか分かりにくくないか？