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部完！
AAAI2015本会議
AAAI2015本会議。論文発表だけじゃなくていろんなセッションがあって単純に楽しいイベントだった。ロボットがそこらじゅうを動きまわってたり、ゲームAIの展示がたくさんあったり。一般人にも公開されてて、子どもたちがたくさんロボットを見に来てた。ロボットとかAIとかは成果がわかりやすいからこういうところから一般向けに公開していくと興味を持ってくれる人たちが増えそうでいいね。
さすがAIの学会で、トピックはホントに多岐にわたってて自分が全然知らない分野ばっかりだった。自分の発表はAI and the Webっていうセッションだったんだけど、そのセッション以外のところに行くともう完全に分野違いで全然わからない有り様だった（自分のカバーしてる分野が小さすぎるかも・・・）。
会議自体はいろいろ頑張っててすごく充実してたんだけど、論文発表は相変わらず分かりづらいというか発表にすらなってないものが多くてとても残念だった。例えばでかいポスターをそのままPDFにして（もちろん文字が小さすぎて全く読めない）ポインタも使わず延々としゃべり続ける人とか、なぜかマイク使わないでぼそぼそ喋って何も聞こえない人とか、発表時間過ぎてるのに話すのをやめない人とか。自分もわかりやすい発表ができたかは客観的には分からないので偉そうなことは言えないけど、口頭発表がもっと重視されるようになってほしいと改めて思った。
Artificial Intelligence, Machine Learning and Robotics: Interplay and Interaction - Drew Bagnell (CMU)
機械学習でロボットを動かすには２つ重要な事がある。
- Speed
- Imitation learning
Speedについてはまあそうだろうという感じで、ロボットが行動を決定する時にいちいち時間がかかってたら全くうまくいかない。アプローチとしてはboosting + very fast weak learnersを使うと良いよって言ってた。
Imitation learningというのは、人の動きを真似しつつ行動を学習するというやり方。レースゲームとか、ヘリコプターの動きのシュミレーションが例に挙げられてたんだけど、そういうのをAIで動かすにはsupervised learningだけじゃうまくいかない。なんでかというと、学習データには失敗した時にリカバーするような動きに関するデータが十分に入ってないから。なので、テストの時に今まで直面したことのないような失敗をしそうになっても、学習したポリシーからはリカバー出来ない。そこでImitation learningが重要になってきて、ロボットが失敗したところを人がインタラクティブに教えてやって、リカバーする方法を学習する。
アナロジーとして、「人が運転しているところを見てるだけじゃ車を運転できるようにならない」と言っていて、確かになと思った。運転がうまい人のを見てても "異常な" 状態にならないから、もしそういう状態になった時にどうすればいいか分からない。
- Supervised learning is not good
- problem is overfitting
- can't recover with no such data
Deep Learning - Geoffrey Hinton (University of Toronto and Google)
1986年に何でback propagationがうまくいかなかったのか、なんで今Deep learningがうまく言っているのかについての話。
うまく行かなかった理由
- 教師データが少なすぎた
- 計算機が遅すぎた
- 初期値を適当に決めすぎた
- 間違ったnon-linearityを使ってた (logistic unit)
1と3について一番多く語ってた。要するに今のDeep learningではunlabeled dataをうまく使って初期値を決めることができてるのが大きい。教師データを使ってfine tuningする前に一層ずつ重ねていくところのこと。現実世界でもそうだけど、ラベル付きデータの数なんかよりもパラメータの数のほうが超超超多いんだから、ラベルなしデータを上手く使わなきゃいけないよねと言っていた。あと、ラベルなんかよりもラベルなし "データ" 自体の方がたくさん情報を含んでるよとかなり強調してた。
4はlogistic unitよりもlectified unitみたいなすごい単純なunitを使ったほうがいいよねってこと。
その後はRNNを使うと機械翻訳の精度がものすごい上がったよって話をしてたけど、あんまりついていけなかった。
Do Competitions help to advance AI? - Panel discussion
AIの分野ではいろんなコンペがやられてるんだけど、それでホントに研究が進むか？っていう議論。
良い点
- TheoryからPracticeに変換できる
- Empirical dataがたくさん手に入る
- いろんなアプローチを比較できる
- コミュニティ一体となって、ある問題に取り組める
問題点
- ただの開発になってないか？
- 単にコンペに勝つ以上の知見を得られるのか？
こうしたらいいよねっていう提案
- Long-term goalを設定する
- 短期的な始点で勝つことが難しくなるからみんな本質に取り組むようになる
- Shortcutとかsimplificationを禁止する
- ただ勝つことを目的とするのを防げる
- open for new teams
- いろんなチームが参加しないと新しい知見が生まれづらい
- 同じやり方に固執しない
- 一度うまく行ったやり方をみんなで真似しててもパフォーマンスが高いものは作れるけど新しい知見が生まれない
その他
論文発表、チュートリアル、キーノート以外にもいろんなイベントがあって楽しかった。
What's hot talk
いろんな他の学会（CVPRとかKDDとかホントに色々）ではどういうトピックがhotなのかをまとめて参加者に教えてくれるセッション。詳細は全くわからないけどどういう論文があるとか、何が出来るようになってるとかのインデックスを張るのにはいいなと思った。
Poster and demo session
他の国際会議と形式は同じだけど、さすがAIの会議、デモが面白かった。Angry birdのAIとか、最近話題になったテキサス・ホールデムのAIとかほんとに色々あって単純に楽しかった。
Video competition
ロボットとか、AIとか、作ったもののビデオを作ってそれの出来（？）を競うというセッション。ちょっと前に話題になったマリオAIがなんかの賞を受賞してた。成果をこういうふうに誰にでもわかりやすくまとめるってのはすごく重要だなと思った。マリオのAIなんかは一般の人にも多分わかりやすくて、こういうのを見てもらえば研究の世界でどういうことが起こってるかを知ってもらえそうだなと思った。
Games night
夜８時から１０時くらいまで参加したい人だけ集まってクイズとかパズルとかいろんなゲームをした。景品たくさんあり。最初はゲームに勝ったら景品が貰えてたのに、景品の数が多すぎて最後は全員取り放題になってて笑った。ちなみに結構参加者いたのに名前呼ばれて壇上でクイズに答えさせられたりした。
