WWW2015でポスター発表した
WWW2015でポスター発表してきた。WWWは以前聴講だけで参加したことがあって、今回はポスターだったので、次回はフルペーパーで発表したい。今回のポスターのタイトルは"Why Do You Follow Him? Multilinear Analysis on Twitter"。キャッチーなタイトルにしたいなーと思ってあれこれ考えた結果結局ありがちなタイトルになった笑
今回の発表はTwitterにおいてユーザが他のユーザをフォローする理由を分析しましょうというもの。以前から@ceekzさんと一緒にTwitterのデータ使った研究しましょうと言ってたのでようやく一つ発表できた。基本的には@ceekzさんにデータの収集と基本的な分析をしてもらって、僕が持ってたちょっとしたアイデア（テンソル分解）を試してみた感じ。
この発表に関するリソースは以下のとおり。
データ：http://dx.doi.org/10.5281/zenodo.13966
コード：yamaguchiyuto/tagf · GitHub
ポスター：http://www.kde.cs.tsukuba.ac.jp/~yuto/resources/www2015/www15_poster.pdf
論文：http://www.www2015.it/documents/proceedings/companion/p137.pdf
概要
目的はユーザAがBをフォローした時の理由を明らかにすること。
これをリストデータを使って分析する。Twitterユーザは他のユーザのリストを作ることができるんだけど、この発表ではそれをタグ付けと捉える。つまり、例えばユーザAが「スポーツ」っていうリストを作ってユーザBをそのリストに加えた時、AはBを「スポーツ」というタグでタグ付けしたとみなす。
この「タグ付け関係」を表すグラフを考える。ノードはユーザで、エッジはタグ付け関係。それぞれのタグには対応するタグ（単語）がラベルとして付いている。またそれに加えてユーザの「フォロー関係」のグラフも用意する。同様にノードはユーザで、エッジはフォロー関係。エッジのラベルはない。
んで、グラフをテンソルにする。タグ付け関係のグラフは３階テンソル、フォロー関係のグラフは２階テンソル、つまり行列になる。タグのテンソルは（ユーザ、ユーザ、タグ）という三つ組を表し、フォロー行列は（ユーザ、ユーザ）のペアを表す。
ここからが（ちょっと）新しいんだけど、これらのテンソルと行列の軸を合わせて貼り合わせる。ここではユーザの二軸が対応してるので、その軸に合わせて貼り合わせる。イメージは図の通り。そしてこの張り合わさったテンソルと行列に対してテンソル分解をかけて潜在パターンを見つけ出す。
出てきた潜在パターンがあら不思議！ユーザがユーザをフォローしてる理由になってますね。すごーい。というお話でした。詳細は論文を読んでね！２ページだけだし。
貢献
- ユーザ間のタグ付け（リスト）関係、フォロー関係のデータを収集、公開した（こちらは@ceekzさんの成果）
- フォローの理由を分析するためにタグ付けおよびフォロー関係をテンソルで表して分解するという手法を提案した
- 上記のデータをつかって実験をして、結果として出てきたいろんな潜在パターンを定性的に評価した
PAKDD2015で発表し（てもらっ）た
PAKDD2015に論文が通っていたので発表した。タイトルは"SocNL: Bayesian Label Propagation with Confidence"。自分で参加して発表したかったんだけどちょうど同じ日程でWWW2015が開催されていて、そっちでの発表もあったので、PAKDDには参加できなかった。残念。なので共著のFaloutsos教授の知り合いの方にかわりに発表してもらった。大変お世話になりました。
前回のAAAI2015に引き続き、今回の発表もグラフ上でのノード分類アルゴリズムの提案。やっぱりアルゴリズムを考えていろいろ解析するのは楽しい。今後もこういう研究をしていきたい。
概要
今回の発表はグラフ上でのノード分類アルゴリズムをベイズ推定から導いて、推定結果に確信度を付与するというもの。ノード分類アルゴリズムはたくさんあるんだけど推定結果に確信度を付与できるものは（なぜか？）なかった。
提案したアルゴリズムは全てのラベルなしノードのラベルについて事前分布を仮定して、隣接ノードのラベルを手がかりとして事後分布を推定する。ただ、隣接ノードにもまたラベルなしノードが存在する（ことが多い）ので、事後分布を再帰的に計算する。
結果としてノードのラベルの事後分布を出力する。これを使えば推定結果の確信度を求めることができる。基本的には隣接ノードが多いほど事後分布はシャープな形状になる。なぜなら手がかりが多いから。逆に隣接ノードが一つとかだと手がかりが少なすぎるので分布は平たくなり、確信度は小さい。これは直感にも合っていると思う。
貢献
以下の長所を持つアルゴリズムを提案した。
Confidence: 推定結果に確信度を付与
Simple: アルゴリズムは簡単な線形システムを解くだけ
Fast: 必ず収束するし、計算量は入力サイズに線形
結果
アルゴリズムの理論的解析と実験的解析をした。
理論的解析では収束性とか、計算量とか、他のアルゴリズムとの等価性とかを示した。
実験的解析では三つのネットワークデータセットを使ってLabel Propagationと提案アルゴリズムの亜種と比較した。
Predicting the Demographics of Twitter Users from Website Traffic Data (AAAI'15) を読んだ
AAAI2015のOutstanding paper award honorable mention。発表聞いた時は何でこれが賞とったのかな？と思ったけど実際論文読んだら結構面白かった。
概要
Twitterユーザのいろいろな属性（年齢、性別、人種、収入、学位、子持ち）を推定する。面白いのはQuantcastのデータを使うところ。QuantcastはあるWebページに訪れる人の年齢とか性別とかの割合を出してる。例えば「LinkedInに訪れる人達の何％は男性です」とか。ここから得られるWebページとTwitterのアカウントを結びつけて、それをフォローしてる人たちの属性を推定する。
具体的には、「あなたはespnとwiredをフォローしてるから男性ですね？」とか、「あなたはPlayStationとsteam_gamesをフォローしてるから18-24歳ですね？」とかいう推定をする。
Research questions
- Twitterユーザの属性はQuantcastのデータから推定できるか？
- あるユーザの属性を推定するのにどれくらいの数のfriends（フォローしてるユーザ）が必要か？
提案手法
- Quantcastから取ってきたWebページに関する情報と、Twitterアカウント (A) とを結びつける。
- Quantcastからは例えば「LinkedIn -> {男性:60%, 女性:40%, 18-24歳: 20%, 24-34: 30%, ...}」みたいなデータがWebページに対して一つ得られる。
- 得られたTwitterアカウント (A) それぞれについて、特徴ベクトル (neighbors vector) を構成。
- neighbors vectorを入力として、Quantcastから取ってきた情報を出力する回帰モデルを作る。
- 入力のneighbors vectorが高次元なのと、たくさんある出力を同時にモデル化したいため、Multi-taskのElastic netを使ってる
- 作ったモデルで学習した結果として、係数βikが得られる。
- 係数βikの値は、ユーザ i をフォローするユーザが属性 k である度合いみたいなのを表す。
- この係数βikを用いてユーザの属性を推定する。
- ユーザ j の属性を推定したい時、j がフォローしてるユーザ i についてβikを合計する。その値が大きければユーザ j は属性 k を持つ可能性が高いとする。
考えはシンプルなんだけど手法の細かいところは結構ごちゃごちゃしててわかりづらい気がする。あと提案モデルで学習した係数をこういうふうに使うのって何か理論的な背景があるのかどうか分からない。
実験
neighbors vectorからQuantcastのデータは回帰できるのか
できた。
Quantcastから得たデータ（例えばLinkedInを訪れる人の60%は男性）と、neighbors vectorから回帰した結果の相関係数は大きかった。
また、各属性 k について、係数βikが大きい上位5ユーザを見てみたら人目でみてわかりやすい結果が出た。
属性推定の精度はどれくらいか
提案手法と、単にあるユーザがフォローしてるユーザをベクトル化してロジスティック回帰する手法を比較したら提案手法が勝った。
属性を推定するのに必要なfriends数はどれくらいか
ランダムに大体10人くらい使えばかなりいい精度で属性推定できた。
感想
着眼点が面白い。誰をフォローしてるかで属性推定する話はまぁよくあるけど、Webページのトラフィックデータを使うとは。提案手法も細かいところはごちゃごちゃしてるけどわかりやすく書かれてた。結果も面白い。
On the Accuracy of Hyper-local Geotagging of Social Media Content (WSDM'15) を読んだ
WSDM2015から。ちょうど開催中なので。
概要
簡単なアルゴリズムは提案しているが、主に分析しました論文。ツイートのジオタグを推定する。主にやったことは
あとはResearch questionに直接結びつかないようなことを細々やってみた感じ。
提案手法
ジオタグ付きツイートから地理的な局所性を持つn-gram (n=1,2,3) を抽出し、ジオタグなしツイートに抽出したn-gramが含まれていればそれを手がかりにジオタグを推定する。Hyper-localというタイトルになってるけど、特にそれといった工夫はしてない。超シンプルなので詳しくは論文を。
実験
ジオタグ付きツイートを使う。投稿したソース (Foursquare, Instagram, iPhone, Android) によって四つのデータセットに分ける。対象地域はニューヨークだけ。提案手法を使ってこれらのツイートのジオタグを推定した。
結果
- 提案手法のパラメータをいじるとAccuracyとCoverageのトレードオフが観測された。
- 投稿したソースによって精度が大きく異なった。Foursquare, Instagramから投稿されたツイートは精度よく推定できたが、iPhone, Androidから投稿されたツイートの推定精度は低かった。
- ツイートが多く投稿される場所から投稿されたツイートのジオタグはうまく推定できるが、あまり投稿されない場所から投稿されたものについてはあまりうまく推定できなかった。
感想
個人的な感想としては、残念な感じだった。批判したい点がけっこうある。
- 既存研究ガン無視。Related workで触れてはいるけどその後は全く触れない。比較なし。まぁ貢献として精度向上をうたってるわけじゃないからいいのかもしれないけど気になる。
- Research questionが狭い。多分提起してかつ分析もしっかりやったのは「ツイート投稿のソースの違いによって推定結果は異なるか」という点だけ。
- Research questionに直接つながらない細々とした分析が多い。
読み込めてない点も多々あるとは思うけど主に得られた知見は「FoursquareとかInstagramを通じて投稿されたツイートのジオタグは推定しやすいよ」っていうことくらいだった。設定したResearch questionと結果が一致してないと非常に読みづらいし質も低く見えるという良い反面教師だった。
AAAI2015で発表した
AAAI2015で発表してきた。タイトルは"OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation"。必殺チェアーからの質問による時間稼ぎは出ずにちゃんと聞いてくれてる人たちから質問が出たから良かったかな。
今回はソーシャルネットワークにデータを限らずに出来るだけ広範囲のグラフに適用できるアルゴリズムを提案した。話を一般的にしようとすればするほど大変だといういい経験が出来た。ドメインに特化した問題を解くアルゴリズムももちろん重要だけど、やっぱりいろんなデータに対して適用できるアルゴリズムを提案するってのはその分野の発展にも寄与できるしもっと重要だと思う。
概要
グラフ上のノード分類問題を解くアルゴリズムを提案した。一部のノードにラベルが付いたグラフを入力として、ラベルがついていないノードのラベルを推定して出力する。ラベルってのは例えばソーシャルネットワークだったらユーザの年齢、性別とか。共著ネットワークだったら著者の研究分野とか。これを解くアルゴリズムはゴマンとあると思うけど、提案手法は 隣接ノード間のラベルの相関がどんなのでも適用可 であるところが新しい。
隣接ノード間のラベル相関としては代表的なものにHomophilyやHeterophilyがある。Homophilyは「類は友を呼ぶ」的な現象で、隣接ノードは同じラベルを持ちやすいという性質。一方Heterophilyはその逆で隣接ノードは別（逆）のラベルを持ちやすいという性質。他にもこの２つが混ざってるグラフとかいろいろある。
既存のアルゴリズムはこのラベル相関の どれか一つ（もしくはいくつか）のみに対してしか適用できない。また、どれにでも適用できるアルゴリズムもあるが、そのアルゴリズムは あらかじめそのグラフにある相関が何であるかをパラメータとして与えなくてはならない。これに対して提案手法は どんなラベル相関にも適用できて、かつ それを指定するパラメータも必要ない という長所がある。
基本アイデア
以下の仮定を置く。
あるノードの隣接ノード集合の大部分が互いに同じラベルを持つならば、残りの隣接ノードも同じラベルを持つ可能性が高い
つまり、あるノードAの隣接ノードB,C,Dのラベルが1だったとき、残りの隣接ノードEのラベルが分からなかったとしても多分同様に1だろうという考え。この考えのいいところはHomophily, Heterophily, これらが混ざってる時のどんな場合でも適用可能なところ。またもう一つのいいところは、隣接ノード集合の大部分が高いに同じラベルを持つという条件が満たされなければ、何もしないという選択ができるところ。
このアイデアをノード間のメッセージパッシングとして定式化した。この例だと、まずB,C,Dが自分の隣接ノードであるAに対して「僕らのラベルは1だよ」というメッセージを送る。そうするとAは「自分の隣接ノードはみんなほとんどラベル1だな」という事がわかり、Eに対して「君も多分ラベル1だよ」というメッセージを送る。
アルゴリズムの詳細に興味があれば是非論文を。
貢献
以下の長所を持つアルゴリズムを提案した。
- Seamless and Accurate：任意のラベル相関を持つグラフに適用可能で、高い精度を実現
- Fast：アルゴリズムに含まれる反復計算の各ステップは入力グラフサイズに線形。またどんな構造のグラフ上でも収束を保証
- Quasi-parameter free：アルゴリズムは一つだけパラメータを持つが、デフォルト１に設定すれば問題なし。つまりパラメータフリーと考えて差し支えない
結果
アルゴリズム解析
- 反復計算の各ステップの計算量は入力グラフサイズに線形
- どんな構造のグラフ上でも収束を保証
- 提案アルゴリズムの特殊ケースがLabel propagation [ICML,2013]と一致
- グラフ上のランダムウォークとして解釈可能
実験
以下の５個のグラフを使って既存手法と比較した。カッコ内はラベルが表す属性。
- blog citation network (political leaning)
- co-authorship network (research field)
- Facebook network (gender)
- Pokec network (gender)
- Pokec network (home location)
以下の２つの既存研究と比較した。
- Label propagation：Homophilyにしか適用できない
- Belief propagation：どんなラベル相関にも適用可能だが、ラベル数の二乗個のパラメータが必要
勝ったッ！第3部完！
