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はその逆で隣接ノードは別(逆)のラベルを持ちやすいという性質。他にもこの2つが混ざってるグラフとかいろいろある。
既存のアルゴリズムはこのラベル相関の どれか一つ(もしくはいくつか)のみに対してしか適用できない。また、どれにでも適用できるアルゴリズムもあるが、そのアルゴリズムは あらかじめそのグラフにある相関が何であるかをパラメータとして与えなくてはならない。これに対して提案手法は どんなラベル相関にも適用できて、かつ それを指定するパラメータも必要ない という長所がある。
基本アイデア
以下の仮定を置く。
あるノードの隣接ノード集合の大部分が互いに同じラベルを持つならば、残りの隣接ノードも同じラベルを持つ可能性が高い
つまり、あるノード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:アルゴリズムは一つだけパラメータを持つが、デフォルト1に設定すれば問題なし。つまりパラメータフリーと考えて差し支えない
結果
アルゴリズム解析
- 反復計算の各ステップの計算量は入力グラフサイズに線形
- どんな構造のグラフ上でも収束を保証
- 提案アルゴリズムの特殊ケースがLabel propagation [ICML,2013]と一致
- グラフ上のランダムウォークとして解釈可能
実験
以下の5個のグラフを使って既存手法と比較した。カッコ内はラベルが表す属性。
- blog citation network (political leaning)
- co-authorship network (research field)
- Facebook network (gender)
- Pokec network (gender)
- Pokec network (home location)
以下の2つの既存研究と比較した。
- 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)
機械学習でロボットを動かすには2つ重要な事がある。
- 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
夜8時から10時くらいまで参加したい人だけ集まってクイズとかパズルとかいろんなゲームをした。景品たくさんあり。最初はゲームに勝ったら景品が貰えてたのに、景品の数が多すぎて最後は全員取り放題になってて笑った。ちなみに結構参加者いたのに名前呼ばれて壇上でクイズに答えさせられたりした。
AAAI2015一日目&二日目
AAAI2015に参加中(TASAは何なのか知らない)。1,2日目はワークショップとチュートリアルと招待講演があった。例のごとくワークショップはパスしていくつかチュートリアルと招待講演を聞いて回った。
いろいろ聞いた感じだと、AIコミュニティはホントにいろんな分野の融合になっていて、扱う範囲が広すぎると思った。自分は元々AIの人間ではないので、知らない単語とか分野がかなり合って、いろいろ知れただけでも参加してよかったと思った。レセプションで話した人たちもみんな結構バラバラの分野から来てて面白かった。
以下参加したチュートリアルと招待講演のメモ。
The Future of (Artificial) Intelligence - Stuart Russell
最近シンギュラリティやばいとかニュースで話題になったりしてるから、しょうがないそれに対して答えてやろうという招待講演。
色々例を挙げて話してたけど、メディア(?)への答えとしてはこれ。
- response
- it'll never happen
- too late to stop
- そんなことは起こらないと言いながらのこれ
- can't control research
- このセリフはカッコ良かった
あと、「お前ら勘違いしてるぜ」と言ってた。
- misconception
- machines have IQs
- 尺度はたくさんあるしなんでIQ?
- general intelligenceはまだまだ先
- It's right around the corner
- いや、breakthroughはunpredictableだから。
- armies on robots
- ないない。
- machines have IQs
良いAIを作る提案。
- Proposal: provably "beneficial" AI
それにはこれが重要。
- Value alignment
- learn reward functions by other agents
- 人へのrewardを学習するAI
- values differ across individuals and contries
その他言ってたこと。
- AI = making computers do the right thing
- progress is accelerating
- Once performance crosses the usability threshold, small improvements are worth billions
Constraint-Based Temporal Reasoning
時間の表し方には
- qualitative
- quantitative
の2つがある。例えば、
「朝食中に新聞を読んで、朝食の後にオフィスに歩いて向かった」
というのはqualitativeで、
「朝6時に起きて、その後朝食中に30分間新聞をよんで、朝食後にオフィスに向かった。8時にオフィスに着いた」
というのがquantitative。要するに、時間の表現の中に数値が出てくるかどうかの違い。qualitativeだと各事象の「前後関係」しか表せない。こういう 時間制約 をうまく表現する方法を考える。んで何らかの方法で表現したら、与えられた情報から推論することで、例えば以下の様なクエリに答える。
「オフィスについた時に新聞を呼んでいたか?」 「朝食を食べ始めた時刻のupper boundは?」
時間の表現方法についてはたくさん紹介してたんだけど、基礎的なところとしてはpoint algebraとinterval algebraっていうのが有名らしい。Interval algebraについては聞いたことあったかも。Point algebraは「朝食を食べ始めた時刻」見たいなTime pointの前後関係を代数的に表現する方法で、Interval algebraは「朝食を食べていた時間」の前後関係を代数的に表現する方法。これらはqualitativeな表現方法だけど、前後関係に数値を入れることでquantitativeに拡張していた。
その後はこういう時間関係にpreferenceを入れるとどうなるか見たいな話。例えば、
「火星探査機に火星の写真を取って分析してもらいたいからそのスケジューリングをする。もちろん分析するのは写真を取ったあとなんだけど、出来るだけ写真を取るタイミングは遅くしたい。どの時刻に写真を取って、どの時刻に分析を開始して、終了すればいいか。」
という問題を扱う。「写真を撮るタイミングを遅くしたい」みたいなのがpreference。事象の前後関係の制約を満たしたまま、preferenceを最大化(?)するにはどうしたらいいかっていう話だったんだけど細かいところはついていけなかった。
こんな分野全然知らなかったからすごく面白かった。たぶんAIコミュニティでもあんまりメジャーな分野じゃなかったみたいで、ものすごい基礎的な話から始まったのですごくわかりやすかった。
Voting Rules for AI
何かを決めるときの投票方法についてのチュートリアル。
3部構成だった。
- 1部:「選挙みたいに、いくつかの候補の中からひとつ選ぶときにどうしたら良いか」
- 2部:「レストランのコースメニューみたいに、いくつかの要素が絡み合ってる場合どう選んだらいいか」
- 3部:「マッチングの話」
1部
いくつかの候補の中からひとつ選ぶやりかたにも色々あるけど、それぞれ違う性質を持ってる。一般的に、voting ruleは以下の三つの性質を持っていることが望まれる。
- anonymous: 全ての投票者は等しく扱われなくてはならない。つまり、ある二人の投票者の投票を入れ替えても、同じ結果になる。
- neutral: 全ての候補は等しく扱われなくてはならない。つまり、候補Aに入った全ての票をBに変えて、候補Bに入った全ての票をAに変えると、AとBの結果が入れ替わる(Aが当選してたならBが当選するし、逆もまたしかり)。
- monotone: 候補Aが当選していた時、Aの票を更に増やすことでAが落選してはいけない。また同様に、A以外の票を減らすことでAが落選してはいけない。
一番良く使われるのはもちろん「多数決」なんだけど、候補者が二人の時はMay's theoremによって多数決は上の三つの性質を持つことが示されている。
当たり前だろうが!と思うかもしれないけど、候補が3個以上ある時はそうも行かない。Arrow's theoremによって、候補が三つ以上ある(かついくつかの条件を満たす)時は、上記の三つの性質を全て満たすvoting ruleは存在しないことが示されている。
2部
こういう問題を考える。
「5人が夕食のメニューを考えている。メインはバジルペストパスタかトマトパスタのどちらか、ワインは白か赤かのどちらかから選びたい。それぞれの投票者はそれぞれ別の嗜好を持っている。どうやって決めたらいいか。」
ここで複雑なのは、単に「白か赤なら白がいいな」というものではなく、「基本的には白が好きだけど、トマトパスタなら赤がいいな。でもバジルペストパスタならやっぱり白がいいかな。」というように、それぞれの項目に依存関係がある。
こういうふうに、選ぶ対象が複数あって、かつそれぞれに依存関係がある時にどうやって選ぶかという問題。依存関係を全部考慮してたら組み合わせが爆発するので、いかに効率的に評価するかっていう話がされてた。
3部
Gale-shapleyアルゴリズムでは、どちら側からプロポーズするかによってman optimalになるかwoman optimalになるかが変わる。man optimalってのは男性側の嗜好の観点からは最適なマッチング担ってるけど、女性側の嗜好の観点からはそうはなっていないということ。
面白いのが、man optimalの時(男性側からプロポーズする時)には、女性側が自分らの嗜好(どの男性が好みか)において嘘を着くことでより良いけっかを得られる。つまり、女性は正直に好みの男性を言わないほうが、好みの男性と結婚できる確率が高いということ。
大体wikipediaに載ってる話だったかな。
Natural Language Processing in Watson
IBMWATSONのチュートリアル。
WATSONの仕組みからどういう応用をやっているかまで話してた。いままで何度か聞いてたけどまた聞きに来てしまった。
導入部では、既存の研究論文とか他人のコード(他のプロジェクトに使われていた)とかを自分のプロジェクトに適用するのはとても難しいから、IBMがやってるようなグランドチャレンジが重要なんだよと言ってた。
WATSONの仕組みについてはもう散々話されてるから他のソース(例えばこことか)に頼るとして、面白かった点を幾つか。
質問の型が大事
jeopardy!ではこういう問題文が出される。
「米国が外交関係を持たない世界の4カ国のうち、この国は最も北にある」
つまり、疑問文になってない。そのため、そもそも何が聞かれてるのかを知る必要がある。そこで、質問の型が重要になってくる。この場合の型は「国」で、問題文に整合する国を答えなくてはならない。
質問の型を導入した時とそうでない時で、精度が10%も変わったんだとか。
実際のアプローチとしては、単に型で限定してから答えを見つけ出すのではなく、いろんな候補解を列挙してから、型に合う答えにより大きなスコアを割り当てるというようにしてるらしい。これを"generate-and-type" principleと呼んでた。
Spatial and temporal reasoning
問題文には場所とか年代に関する記述が多く存在するため、それを手がかりにする必要がある。単純に「1980年」っていう記述が出てきたらそれでキーワードマッチすれば良いじゃんと思うかもしれないけど、「1980年で400周年となる○○」みたいな問題文を出されてしまうと、単純なキーワードマッチだとうまくいかない。○○に関する情報には「1980年」というキーワードはまず出てこないため。