Closed kacky24 closed 5 years ago
大規模な複雑ネットワークにおけるノードの分散表現を獲得するための手法LINEの提案． 有向，無向や重み付きかどうかに関わらず，適用可能． ネットワークの1次，2次の近接性を保つ．
ノードvi, vjの結合確率 (uが求めたい分散表現) 目的関数 ここで，p^はリンクijと全リンクの重みの和の比 距離関数dはKLダイバージェンスを使う 整理すると， これらは，無向グラフにのみ適用可能
2次近接性は有向，無向どちらにも適用可能で，無向の場合は，双方向の重みの等しい有向グラフに置き換えて考える． ノードを'context'としてもとらえ，似た'contexts'の分布を持つノードは似ているとする． よって，各ノードは，ノードとして扱われた時の分散表現uと，contextとしての分散表現u'を持つとする． ノードviからcontext vjが生成される確率 目的関数 ここで，p^はリンクijの重みとノードiのout degreeの比 lamdaは各ノードの重要度（次数やPageRankなどで求められる）で今回はout degree 距離関数dはKLダイバージェンス 整理すると，
1次近接性と2次近接性の結合はシンプルに分散表現をconcat 目的関数を組み合わせて学習させるのは今後の課題
2次近接性の目的関数を最適化するのは計算量多い⇒negative sampling 目的関数 最適化には asynchronous stochastic gradient algorithm(ASGD)を用いる． 更新式
上の更新式では，単語の共起などwのばらつきが非常に大きい場合，適切な学習率の設定が難しくうまく学習できない． これを解決するために，重みは一律として，元の重みに比例する確率でリンクをサンプリングして学習を行う．
https://arxiv.org/pdf/1503.03578.pdf
Jian Tang1 , Meng Qu2∗ , Mingzhe Wang2 , Ming Zhang2 , Jun Yan1 , Qiaozhu Mei3 1Microsoft Research Asia, {jiatang, junyan}@microsoft.com 2School of EECS, Peking University, {mnqu, wangmingzhe, mzhang_cs}@pku.edu.cn 3School of Information, University of Michigan, qmei@umich.edu
2015
short summary
大規模な複雑ネットワークにおけるノードの分散表現を獲得するための手法LINEの提案． 有向，無向や重み付きかどうかに関わらず，適用可能． ネットワークの1次，2次の近接性を保つ．
1次近接性の学習
ノードvi, vjの結合確率 (uが求めたい分散表現)
目的関数
ここで，p^はリンクijと全リンクの重みの和の比
距離関数dはKLダイバージェンスを使う
整理すると，
これらは，無向グラフにのみ適用可能
2次近接性の学習
2次近接性は有向，無向どちらにも適用可能で，無向の場合は，双方向の重みの等しい有向グラフに置き換えて考える． ノードを'context'としてもとらえ，似た'contexts'の分布を持つノードは似ているとする． よって，各ノードは，ノードとして扱われた時の分散表現uと，contextとしての分散表現u'を持つとする． ノードviからcontext vjが生成される確率
目的関数
ここで，p^はリンクijの重みとノードiのout degreeの比
lamdaは各ノードの重要度（次数やPageRankなどで求められる）で今回はout degree
距離関数dはKLダイバージェンス
整理すると，
1次近接性と2次近接性の結合はシンプルに分散表現をconcat 目的関数を組み合わせて学習させるのは今後の課題
optimization
2次近接性の目的関数を最適化するのは計算量多い⇒negative sampling 目的関数
最適化には asynchronous stochastic gradient algorithm(ASGD)を用いる．
更新式
上の更新式では，単語の共起などwのばらつきが非常に大きい場合，適切な学習率の設定が難しくうまく学習できない． これを解決するために，重みは一律として，元の重みに比例する確率でリンクをサンプリングして学習を行う．
URL
https://arxiv.org/pdf/1503.03578.pdf
author
Jian Tang1 , Meng Qu2∗ , Mingzhe Wang2 , Ming Zhang2 , Jun Yan1 , Qiaozhu Mei3 1Microsoft Research Asia, {jiatang, junyan}@microsoft.com 2School of EECS, Peking University, {mnqu, wangmingzhe, mzhang_cs}@pku.edu.cn 3School of Information, University of Michigan, qmei@umich.edu
year
2015