論文読んだ記録の記録 4 - 機械学習ぼっち論文読み

skip-gramモデル*1をwikipediaなり小説なり大量の文章に当てはめて，パラメータを最尤推定することで文章中の各単語にベクトル表現を与えることができます．skip-gramを用いて単語のベクトル表現を得る手法はword2vecとも呼ばれていて，数年前に一世を風靡しました*2. 色んな人が解説してるので興味ある人はこことかこことか見てください．

word2vecで得られた単語ベクトルでは加法演算ができるとかなんとかいう話があります．意味不明ですね．各単語のベクトルの加減算"King"-"Man"+"Woman"を計算したら"Queen"という単語が近傍に出て来るみたいな話は有名です．なんか足し算できるみたいな話がずっとされつつもその理屈はよく分かってなくて，途中でナレッジグラフを使ってsupervisedに足し算を学習しようぜみたいな話も出てきました

https://aokn-kytjp.tumblr.com/post/168455937397/liu-hanxiao-yuexin-wu-and-yiming-yang

これくらい明示的にsupervisedで学習すればそりゃ足し算できるのかな，という気持ちにもなりますが，word2vecはunsupervisedなのでなんで単語の足し算できるんやみたいなのは長年謎のままで，ACL2017で(それなりに強い仮定をおいた場合に)ちゃんと単語で足し算できるようになるよ，という話が出ていました．

https://aokn-kytjp.tumblr.com/post/168890960757/gittens-alex-dimitris-achlioptas-and-michael-w

(この文献は先輩に教えてもらいました，ありがとうございます)

私的には，word2vec自体には興味ないし*3足し算がどうこういう意味不明な話が解明されればもう満足なんですが，word2vecをグラフの表現学習に利用しようという話が出てきて無視できないという状況です．

グラフ $\mathcal{G}$ のノード $\mathcal{V}=\{v_i\}_{i=1}^{n}$ とそのエッジ $\mathcal{E}=\{e_{ij}\}$ が得られているときに，グラフ上でランダムウォークすることでノードの系列

$v_{i_1} \to v_{i_2} \to v_{i_3} \to \cdots \to v_{i_m}$

を作ります．ノード一つ一つを，例えば文章「I have a pen」の各単語I, have, a, penに対応付けることができ，word2vecと全く同様に各単語(各ノード)にベクトル表現を付与できるので，各ノード $v_i$ のベクトル表現 $\boldsymbol x_i \in \mathbb{R}^p$ を得ることができる，という仕組みです．この手法はDeepWalk*4と呼ばれています．ランダムウォークで系列を作ると，グラフの一部のノードにのみ集中して系列が作成されてしまうので，それを回避するためにランダムなノードからランダムウォークを何度も繰り返したDeepWalkの亜種がnode2vec*5として知られています．

Twitterなどでも何度か書いてますが，DeepWalkという名前には少し違和感があります．DeepWalkで用いられるskip-gramは1層のニューラルネットワークを使っているとみなすことができる*6ので，そこからDeep Learningを連想してDeepという名前という付けたのだと思いますが，流石に3層以下のものをDeepと呼ぶ人は極めて少ないだろうし，言葉の使い方としてあまりよろしくない．NeuralWalkなら(ちょっと気持ち悪いけど)まぁなんとか許容範囲に入っていなくもない・・・.

つまり，DeepWalkの名前の由来になっていたDeep Learning + Random Walkという2つの属性のうち，Deepのほうは詐称ということになります．最近は更に意味不明で，残ったRandom walk部分をグラフの隣接行列 $W$ を使って $W+W^2$ の行列分解で近似しようみたいなのが出てきました

https://aokn-kytjp.tumblr.com/post/168886063697/yang-cheng-et-al-network-representation

これは単にNeural Matrix Factorizationでは・・・という気がするのですが，Deep Matrix Factorizationも出ているので名前は今更変えられない

https://aokn-kytjp.tumblr.com/post/168768477142/xue-hong-jian-et-al-deep-matrix-factorization

Yang et al. (2015)は一応タイトルにはDeepWalkという単語を使わず苦心した結果が見える*7のですが，2016に出ている方はもうタイトルで思いっきりDeepWalkと言っています．

https://aokn-kytjp.tumblr.com/post/168887242172/tu-cunchao-et-al-max-margin-deepwalk

Deepでもないし，Random walkでもない，これはDeepWalkと読んでよいのか????というモヤモヤした気持ちが募るばかりです．このあたりの話は名前の使いあkたが本当は雑で，Deep Matrix Factorizationなんて行列分解せずにneural network使ってますからね．行列分解してる人がDeepとか言っていて，ニューラルネット使ってる人がMatrix Factorizationとか言っている．ややこしいので名前はちゃんと付けて欲しいです・・・・・．

追記: word2vecの研究の時系列についてはフォローしきれてないので，どれが最初とかどの時点でこれが言及されてたとかはよく知りません・・・．上で書いたやつ以外にも色々論文は出てるので興味ある人は自分でサーベイしてください

*1:Mikolov, Tomas, et al. "Distributed representations of words and phrases and their compositionality." Advances in neural information processing systems. 2013.

*2:伝聞です

*3:あと怖いオジサンがいっぱいいそうで迂闊なことが書けない

*4:Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.

*5:Grover, Aditya, and Jure Leskovec. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.

*6:より正確には，"できなくもない"

*7:手法名はText-Associated DeepWalkで思いっきりDeepWalkって言ってるけど