面白いデータを探して

適当に書く。間違えていたら教えてください。

Network Embeddingの主要な手法について2

Network Embeddingの主要な手法についてのメモ.
今回はGraRep, struc2vec, SiNE.
1はこちら.
netres-bigdata.hatenablog.com

GraRep

LINEではfirst-orderとsecond-orderに関して最適化を行なうが,k-orderに関しても最適化を使用という論文*1.
最適化に際して,skip-gramを行列式変形と解釈しなおし,それに関して最適化を行なう.
(GraRepについてはあまり理解できていないので,指摘・意見などがあればコメントなどいただけると幸いです.)

struc2vec

各ノードがネットワーク内で果たす役割に対応したベクトル表現を得る手法[1704.03165] struc2vec: Learning Node Representations from Structural Identity
ネットワークからコンテキストを作り,階層的ソフトマックスで最適化を行なう.
実験では飛行機の運行ネットワーク内で活発な飛行場とそうでない飛行場を4段階に分け,それらを分類することができるかで行っているが,ソーシャルネットワークとかで考えるとインフルエンサーを見つけると言ったタスクに近くなるのだろうか.

SiNE

正負重み付きグラフ(signed network)のエンベッディング手法*2.
通常の重み付きグラフではエッジの重みは正の値であるが,正負重み付きグラフではエッジの重みに負の値を許す.このようにすることで,友好関係と敵対関係,賛成と反対と言った正負の関係をモデル化することができる.
SiNEでは正の重みのエッジを持つノード対は負の重みのエッジを持つノード対より近くにあるという知見に基づき,ニューラルネットワークの出力に対してマージン最大化をlossとして学習を行なう.
実験ではエッジの正負の予測を行い,当時のSOTAを達成(現在は更新されているようだ.)

*1:Cao, Shaosheng, Wei Lu, and Qiongkai Xu. "Grarep: Learning graph representations with global structural information." Proceedings of the 24th ACM international on conference on information and knowledge management. ACM, 2015.

*2:Wang, Suhang, et al. "Signed network embedding in social media." Proceedings of the 2017 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2017.

Network Embeddingの主要な手法について1

研究のためにNetwork Embeddingでよく扱われる手法についてまとめていきます.
例によって備忘録的な感じなので,主に何がしたい論文なのかに焦点を当てたいと思います.詳細に関しては論文などを見てください.
今回はDeepWalk, Node2Vec, LINE, SDNEの4つについて.

DeepWalk

論文は[1403.6652] DeepWalk: Online Learning of Social Representationsです.
前に記事を書いています.
netres-bigdata.hatenablog.com

Node2Vec

DeepWalkの改良的な論文[1607.00653] node2vec: Scalable Feature Learning for Networks
DeepWalkでは学習データのサンプリングの際にランダムウォークを用いています.そのランダムウォークにいい感じにバイアスをかけてやることによっていい感じのサンプルを取ってこようという主題.
「いい感じ」とは幅優先探索深さ優先探索のバランスを考慮してサンプリングがしたいということです.幅優先探索を行なうとネットワーク上でハブになっているノードのようなネットワーク上でのそのノードの役割をよく考えることができますが,ネットワーク上で近いノードの情報しか獲得できません.一方で,深さ優先探索ではネットワークのより広い範囲のノードの情報を得ることができますが,サンプリングされるノードの分散が大きく,探索範囲が深すぎると問題になる.そこでこれらを調整するためにランダムウォークの次のノードの選び方にバイアスをかける.

LINE

DeepWalkやNode2Vecとはまた少し考え方が違う手法
[1503.03578] LINE: Large-scale Information Network Embedding
.時系列的にはDeepWalkの次でNode2Vecより前に発表された論文.
LINEでは次の2つの学習を行なう.

  • first-order proximity : エッジでつながっているノードは近くに
  • second-order proximity : 隣接ノードの組が近いノードは近くに

second-order proximityは隣接ノードの組が近いノードは近いベクトル表現を得るように学習させるが,これは直接エッジで繋がれてはいないが,隣接ノードが近いノード対は近い役割を持っているはずであるという考え方による.
同時に最適化するのは今後の課題として,これらを独立に学習させてconcatすると精度がいいらしい.

SDNE

考え方としてはLINEに近いが,学習器にautoencoderを用いている*1
LINEと同じくfirst-order proximityとsecond-order proximityを考えるが,ネットワークの構造は high non-linearityを持つ.したがって,これらを保持するためには表現力が高いモデルを用いた方がいいはずである.そのために,DNN(今回はautoencoder)を使おうという論文.
自分が試してみたところ,精度は割と出る(Node2Vecと同じか少しいいくらい)だが,大きいネットワークに使おうとすると計算時間が非常にかかる.DNNを使うため,最適化にかかるコストが大きいことがネックかなあという感じ.

最後に

次はGCN関係をまとめたい.(GCN, graphSAGEとか)

*1:Wang, Daixin, Peng Cui, and Wenwu Zhu. "Structural deep network embedding." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.

数独を解いてみる

パソコンの大掃除をしていたら大学1年の時に出された課題のプログラムが出てきました。
その時の課題が「数独を解くプログラムを作りなさい」という課題だったのですが、改めてコードを読んでみるとまあ汚いし効率悪いしで散々でした。
正月で少し暇してたし、それを作りなおしてみよう的なのりです。

続きを読む

Q学習で迷路を解く

自分の趣味は将棋なのですが、GoogleDeepmindが発表したAlphaZeroの棋譜を見て、自分でも試してみたいと思ったのがきっかけ。強化学習は詳しくないし、いきなりDQN(Deep Q-Network)とかよくわからないのでとりあえずQ学習やってみましょうということでやってみた。
具体的にやったことは

  1. 強化学習の手法の1つであるQ学習について勉強した
  2. せっかくなので、Q学習で迷路を解いてみた

強化学習はあまり詳しくないため、間違いがある可能性があります。もしも間違いなどを見つけたらコメントなどで指摘いただけると非常に助かります。

続きを読む

機械学習の指標いろいろ(1) 〜ROC曲線とAUC〜

機械学習の学習済みモデルの精度には色々あります。
自分でもよくわかっていない指標がときどきあるので、調べたものをまとめます。
今回はROC曲線とAUC。

続きを読む