ブログではないです

ブログでなくはないです

KB系 (link prediction) まとめ

NLP paper まとめ

最近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 { \displaystyle \rightarrow_{appos}} co-founder { \displaystyle \rightarrow_{prep}} of { \displaystyle \rightarrow_{pobj}} OBJECT" というトークン列をCNNでエンコードして得たベクトルからスコアと確率を得る。 従来のスコア関数で推測した確率による損失との重み付け和に対して最適化することで従来手法との共存が可能であり、既存のスコア関数であるmodelF, modelE, distMultなどに対して実験。結果はfiltered(後述)の条件でFB15k-237に対して最高でMRRが0.424, HITS@10が61.1。

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

確率を { \displaystyle 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))}}} }
損失を { \displaystyle 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が好まれるのだろう・・・？逆順位って直観的にどの程度良いのか分かりにくくないか？

Learning Symmetric Collaborative Dialogue Agents with Dynamic Knowledge Graph Embeddings [He+, ACL'17]

https://nlp.stanford.edu/pubs/he2017collaborative.pdf

概要

それぞれが異なる知識を持つ対話エージェントについての研究。タスクが面白く、２つのエージェントは自分の友人のリスト（友人の名前、学校、会社などが書かれている）を渡される。 その中に共通する友人が存在しそれが誰かを対話によって情報交換をしながら特定する、というタスクをクラウドソーシングによって人間に解かせた上で、それを学習データとして用いている。 全体的にモデルがわちゃわちゃしているし正直論文が超読みにくいけどやってることの新しそう感が凄い。

渡される情報や対話は下図のような感じ。 一行をitem, 各セルをentity (or attiribute) と呼ぶ。

f:id:jack_and_rozz:20170717172411p:plain:w250

モデル

タイトルにDynamic Knowledge Graph Embeddingとあるように、DynoNetと呼ばれる提案手法では入力として与えられたリストをグラフとして処理し、相手のentityへの言及を元にグラフを動的に更新した上で、自身の知識グラフにattentionを貼る形で発話生成をする。 研究室の論文紹介でスライド作ってしまって力尽きたので詳しい数式を追っていくのは省略。

f:id:jack_and_rozz:20170717172655p:plain

AutoExtend: Extending Word Embeddings to Embeddings for Synsets and Lexemes [Rothe+, ACL'15]

paper NLP incomplete

http://www.aclweb.org/anthology/P15-1173

概要

一回ちゃんと書いたやつが保存し忘れで消えてしまったので簡単にモデルの構成だけメモ。訓練済みのword embeddingsとWordnetのデータを使ってsynsetとlexemeについてもembeddingsを獲得するという研究。モデルの概要図は以下。

f:id:jack_and_rozz:20170711154620p:plain:w600
全体としてはlexemeを介して word <-> synset 間の変換を行うautoencoder的なモデルになっている。

以下、論文中の数式のうち重要なところを追っていく。（式番号は論文準拠） 単語{ \displaystyle w^{(i)}}についてsynset { \displaystyle s^{(j)}} に属するlexemeを{ \displaystyle l^{(i, j)}} （存在しない場合は{ \displaystyle l^{(i, j)}} = 0） とした時，wordとsynsetはそれぞれlexemeの集合なので
(1) { \displaystyle w^{(i)} = \sum_j l^{(i, j)}}
(2) { \displaystyle s^{(j)} = \sum_i l^{(i, j)}}

とする。その上でword -> lexemeに変換する行列を{ \displaystyle E^{(i, j)}} とおく。　（ここでは計算量削減のためEを対角行列としている）
(3) { \displaystyle l^{(i, j)} = E^{(i, j)} w^{(i)} }

すると (2), (3) 式より
(5) { \displaystyle s^{(j)} = \sum_i E^{(i, j)} w^{(i)} }
となり，この式を単語とsynset全体に拡張するとシンプルなテンソル積の形で書ける。 (7) { \displaystyle S = \textbf E \otimes W}
S, W はsynset / word embedding を並べた行列，{ \displaystyle \textbf E}は { \displaystyle E^{(i, j)} } を並べた4階のテンソル。

これがAutoextendのEncoderにあたり、Decoder側については逆にsynset -> word の変換を同様に考えると
(14) { \displaystyle \overline{W} = \textbf D \otimes S}
と、synset -> wordの変換もまたテンソル積の形で書ける。全体としては
(17） { \displaystyle \min_{\textbf E, \textbf D} || |\textbf D \otimes \textbf E \otimes W - W|| }
の形でautoencoderのようなencode -> decode でWを復元するモデルとなっている。 このようにモデルを設計した上で最終的な目的関数として

  1. wordをencode + decodeして元に戻した時の誤差を小さくする項 { \displaystyle || D^{(d)} E^{(d)} w^{(d)} - w^{(d)} ||}
  2. word -> lexeme と synset -> lexemeの誤差を小さくする項 { \displaystyle || E^{(i, j)} w^{(i)} - D^{(j, i)} s^{(j)} ||}
  3. 上位語・同義語などの関係があるsynsetどうしを近づける項 { \displaystyle || RE^{(d)} w^{(d)} ||}

をハイパーパラメータ{ \displaystyle \alpha, \beta, 1-\alpha-\beta }で重み付け和を取って最小化する形で{ \displaystyle E^{(i,j)}, D^{(j,i)} }の訓練を行う。

1. の{ \displaystyle D^{(d)}, E^{(d)}, w^{(d)}} は { \displaystyle D^{(j, i)} E^{(i, j)} w^{(i)}} の{ \displaystyle d }次元目を集めたもの。（{ \displaystyle D^{(j, i)} E^{(i, j)}}　については{ \displaystyle d}番目の対角成分） { \displaystyle D^{(j, i)} E^{(i, j)}}は対角行列なので各成分を独立に計算できるためこのような形になっている。

3. は1つのlexemeしか所属しないようなsynsetについてもちゃんとembeddingを獲得する事を目的とした項で、 { \displaystyle R} は関係のある2つのsynsetのペアを1行として縦に並べたもの。例えばAがBの上位語である、という情報はAに相当する列を1, Bに相当する列を-1, それ以外は0である1行で表現される。つまりこの例だと{ \displaystyle RE^{(d)} w^{(d)}} は { \displaystyle ||s_a - s_b|| } を計算していることになる。
しかし論文を読む限りこのやり方だとペアの間にある関係ごとの違いは一切考慮されておらず、何かの関係があれば問答無用で近いsynsetとなるような制約になってしまっていると思うのだけど・・・？

対話のデータセットと評価指標

memo NLP

以前教えて貰ったサーベイ記事。忘れないようにメモ。

対話のデータセットいろいろ https://breakend.github.io/DialogDatasets/

対話の評価指標について https://github.com/pmineiro/ldlmd2016/blob/master/NIPSDec2016H.Hastie.pdf

The Ubuntu Dialogue Corpus: A Large Dataset for Research in Unstructure Multi-Turn Dialogue Systems [Lowe+, SIGDIAL'15]

paper dialogue dataset

http://www.sigdial.org/workshops/conference16/proceedings/pdf/SIGDIAL40.pdf

概要

Ubuntu forumのチャットルームの会話を使ってデータセットを作った＆それを用いて応答選択タスクをやってみたという論文。 データセットは長めのターン数（平均7.7ターン）のデータセットであんまり無いタイプ。似たようなものに The Ubuntu Chat Corpus for Multiparticipant Chat Analysis [Uthus+, AAAI'13] があるがこっちは多人数間の会話そのままのコーパス、こっちは1対1の会話になっている部分を抜き出している。

データセットを作るにあたってinitial question/message (ある会話の始まりとなる発話)とmessage（それへの返信）を特定してそれが1対1になっている部分を切り出す必要がある。 手順としてはチャットルームの発言の後ろからmessageを探し，そこからそのmessageの3分以内の発話についてbackwardに辿っていく形を取るが，その際元々のデータは誰に向けて話しているのかが明示されていない事が問題になる。しかし慣例的に多くの場合文の冒頭にユーザ名を書いてメッセージを送る（ user_name : message ）ため、文の冒頭の単語を見てそれが一般的な単語 (GNU Aspell spell checking dictionary に登録されていない) であった場合にユーザ名と判断している。また，

また，
<RC> “dell: you can’t move the drives”
<RC> “this is the problem with RAID”
のように後で発話を付け加える場合など，message形式になっていないものにも文脈を保つ上で重要なものが存在している一方、複数人で会話している場合は並行して違うユーザに向けた発話がmessage形式を取らずに行われる場合があるため取扱いが難しい。 そのためあるユーザが複数人に対してmessageを送っているかをチェックして、送っていない場合は途中の発話も繋げ，そうでない場合は弾いている。

応答選択モデルはコンテクスト（複数の発話を __EOU__ などの区切りトークンで繋げたもの。最長160単語まで）と応答をそれぞれ（TF-IDF, RNN, LSTM）でエンコードしたベクトルc, rを用いて{ \displaystyle p= \sigma (c^{\mathrm T} M r + b)} として応答の適切さを推定。[Wu+, Coling'16]のように発話１つをエンコードするネットワークとその系列をエンコードするネットワークのように分けることはしていない。まあLSTMが一番良い。

Modeling Relational Data with Graph Convolutional Networks [Schlichtkrull+, arXiv'17]

paper

https://arxiv.org/pdf/1703.06103.pdf

概要

Graph Convolutional Network(GCN) を関係ラベル付き有向グラフも扱えるように拡張して、ノードのタイプの推定や欠けたエッジの補完を行う話。 Quitaの解説記事 がとてもわかりやすいのであまり自分で書くことがない・・・。

思ったこと

R-GCNの式(1)での重みについて，

{ \displaystyle W_{r}^{(l)} = \sum_{b=1}^{B} a_{rb}^{(l)} V_{b}^{(l)} }
のように基底変換を重み付け和するやり方と

{ \displaystyle W_{r}^{(l)} = \bigoplus_{b=1}^{B} Q_{br}^{(l)} }
のように小さな基底変換のdirect sumを取る、つまり{ \displaystyle W_{r}^{(l)}}をブロック対角行列の形で表す方法の二種類を取っている。これはrelationが多くて全部について行列を学習するのが大変だからということだと思うんだけど一方でLink Predictionの方では{ \displaystyle R_r} として別個に学習してるように見えるがそこは良いのか？？

DistMult単体で用いた場合との違いはentityのベクトルをR-GCNを使って作るか，それともembeddingとして同時最適化しているかの違い？ グラフ系のNN，もしくはそれ以外の既存手法あまり知らないので関連研究辿る。

テストでは同様にtriple (subject, relation, object) が与えられ、 subject/object のどちらかを抜いた状態（両方やる）で全entityについてそのtripleに入るかどうかのスコアを算出する。正解のentityのMRR (平均逆順位)と Hit@k (上位k位に正解がいる割合) で評価。

メモ

ここ にDistmult含め既存研究のグラフKBに関する研究をまとめたスライドがあった。

Unsupervised Domain Adaptation by Backpropagation [Ganin+, ICML'15]

概要

Adversarial Multi-task Learning for Text Classification [Liu+, arXiv'17] の中で使われていたgradient reversal layerとは何だ？という事で読んだ．手法の部分しか読んでないので細かい実験結果などは省略．

文脈としてはMulti-task learningというよりDomain adaptationで，大まかなやりたいことは↑の論文と同じ． 入力から抽出した特徴量がf， fを入力として推定するソースドメインにおけるラベルをy， 同じくｆを入力として推定する現在のドメインをdとして，y，d に関する損失を { \displaystyle L_y， L_d} とする．
y, d についてのパラメータ{ \displaystyle \theta_y, \theta_d}はそれぞれの損失{ \displaystyle L_y, L_d} を最小化するように，fについてのパラメータ{ \displaystyle \theta_f}は{ \displaystyle L_y}を最小化し，かつ欲しいのはドメイン不変な特徴量であるため{ \displaystyle L_d}を最大化するように学習したい．つまり，以下が更新式になる．

{ \displaystyle \theta_f \leftarrow \theta_f - \mu ( \frac{\partial L^i_y}{\partial \theta_f} - \lambda \frac{\partial L^i_d}{\partial \theta_f}) }

{ \displaystyle \theta_y \leftarrow \theta_y - \mu \frac{\partial L^i_y}{\partial \theta_y} }

{ \displaystyle \theta_d \leftarrow \theta_d - \mu \frac{\partial L^i_d}{\partial \theta_d} }

この { \displaystyle \theta_f}の第二項目にあたる符合の逆転を誤差逆伝搬時に上手いことやっているのがgradient reversal layer．
{ \displaystyle R_{\lambda} (\textbf{x}) = \textbf{x}}
{ \displaystyle \frac{dR_{\lambda}}{d\textbf{x}} = - \lambda \textbf{I}}
となる関数がf -> d の間にあると考えれば良いとのこと。
DL系のフレームワークの内部で自動微分をどうやっているか詳しくないので何とも言えないが、関数を定義する時に順方向・逆方向の処理をそれぞれ持っておくような形になっているんだろうか？ ここにCaffe実装のコードと補足資料があったのでどうやってるか今度確認・・・．

しかしこういうのがあるならなんでGANとかではDiscriminatorとGeneratorを交互に訓練するようなことをやっているんだろう？同じ理屈で一括で出来そうな気もする・・・。 （話は少し変わるが，過去に読んだGANのコードではGeneratorの訓練時にDiscriminatorのパラメータを固定していなかったのだが、これは一般的な実装？Discriminatorの方のパラメータをわざわざ悪い方向に動かす理由がないと思うのだが・・・。）