でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

AAAI2015本会議

conference

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がうまく言っているのかについての話。

うまく行かなかった理由

  1. 教師データが少なすぎた
  2. 計算機が遅すぎた
  3. 初期値を適当に決めすぎた
  4. 間違った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

夜８時から１０時くらいまで参加したい人だけ集まってクイズとかパズルとかいろんなゲームをした。景品たくさんあり。最初はゲームに勝ったら景品が貰えてたのに、景品の数が多すぎて最後は全員取り放題になってて笑った。ちなみに結構参加者いたのに名前呼ばれて壇上でクイズに答えさせられたりした。

AAAI2015一日目＆二日目

conference

f:id:yamaguchiyuto:20150127153004j:plain

AAAI2015に参加中（TASAは何なのか知らない）。１，２日目はワークショップとチュートリアルと招待講演があった。例のごとくワークショップはパスしていくつかチュートリアルと招待講演を聞いて回った。

いろいろ聞いた感じだと、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
      • ないない。

良い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

の２つがある。例えば、

「朝食中に新聞を読んで、朝食の後にオフィスに歩いて向かった」

というのはqualitativeで、

「朝６時に起きて、その後朝食中に３０分間新聞をよんで、朝食後にオフィスに向かった。８時にオフィスに着いた」

というのが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

何かを決めるときの投票方法についてのチュートリアル。

３部構成だった。

  • １部：「選挙みたいに、いくつかの候補の中からひとつ選ぶときにどうしたら良いか」
  • ２部：「レストランのコースメニューみたいに、いくつかの要素が絡み合ってる場合どう選んだらいいか」
  • ３部：「マッチングの話」

１部

いくつかの候補の中からひとつ選ぶやりかたにも色々あるけど、それぞれ違う性質を持ってる。一般的に、voting ruleは以下の三つの性質を持っていることが望まれる。

  • anonymous: 全ての投票者は等しく扱われなくてはならない。つまり、ある二人の投票者の投票を入れ替えても、同じ結果になる。
  • neutral: 全ての候補は等しく扱われなくてはならない。つまり、候補Aに入った全ての票をBに変えて、候補Bに入った全ての票をAに変えると、AとBの結果が入れ替わる（Aが当選してたならBが当選するし、逆もまたしかり）。
  • monotone: 候補Aが当選していた時、Aの票を更に増やすことでAが落選してはいけない。また同様に、A以外の票を減らすことでAが落選してはいけない。

一番良く使われるのはもちろん「多数決」なんだけど、候補者が二人の時はMay's theoremによって多数決は上の三つの性質を持つことが示されている。

当たり前だろうが！と思うかもしれないけど、候補が３個以上ある時はそうも行かない。Arrow's theoremによって、候補が三つ以上ある（かついくつかの条件を満たす）時は、上記の三つの性質を全て満たすvoting ruleは存在しないことが示されている。

２部

こういう問題を考える。

「５人が夕食のメニューを考えている。メインはバジルペストパスタかトマトパスタのどちらか、ワインは白か赤かのどちらかから選びたい。それぞれの投票者はそれぞれ別の嗜好を持っている。どうやって決めたらいいか。」

ここで複雑なのは、単に「白か赤なら白がいいな」というものではなく、「基本的には白が好きだけど、トマトパスタなら赤がいいな。でもバジルペストパスタならやっぱり白がいいかな。」というように、それぞれの項目に依存関係がある。

こういうふうに、選ぶ対象が複数あって、かつそれぞれに依存関係がある時にどうやって選ぶかという問題。依存関係を全部考慮してたら組み合わせが爆発するので、いかに効率的に評価するかっていう話がされてた。

３部

Stable machingの話。

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年」というキーワードはまず出てこないため。

Joint Inference of Multiple Label Types in Large Network (ICML'14) を読んだ

paper machine learning

ICML14から。数式とか書くのはめんどくさいからアイデアを中心に書く。

概要

ネットワーク上の ノード分類 の話で、各ノードは 複数のラベルタイプを持っている という設定。例えば論文中で使われている例だと、Facebookユーザの出身地、現住所、高校、大学、雇い主の５つのラベルタイプを同時に推定する。

アイデア

提案手法は接続されているノードペアの 多くが出来るだけラベルを共有する ようにノードのラベルを決定する。このやり方がうまくいくことを説明するために既存手法（ラベル伝搬法）がうまくいかない例を挙げる。下の図（論文中Fig. 1）に対してラベル伝搬法を適用すると、u のhometownとcurrent cityはそれぞれ多数決により H と C' と推定される。でもこれだと右の方にいる赤いやつらと u がどのタイプのラベルも共有しないため、 なぜ友達なのかが説明されない という状況になる。普通に考えればある人とある人が友達になるにはなにか理由があるはず。つまり なにかしらのラベルを共有するはず。

f:id:yamaguchiyuto:20141231092712p:plain

ラベル伝搬法と違って提案手法は なぜノードが接続されているか を最大限説明しようとするため、u のcurrent cityの推定結果を C' ではなく C であるとする。こうすることによって、左側のノード達はhometownラベルを共有してるから u と友達で、右側のノード達はcurrent cityラベルを共有してるから u と友達だという説明ができる。著者らはこうすることによってノード分類の精度が上がると考え、実際に精度が上がった。

貢献

  • ノード分類（ラベル推定）問題を、ノード間にエッジが張られている理由を説明する 問題に変換した。理由を説明するというのは、接続されているノードペアが共有しているラベルを見つけること。
  • スケーラブル（分散可）、高精度のノード分類手法を提案。
  • 10億ノードくらいのFacebookグラフを使った実験をし、ラベル伝搬法より精度が高いことを示した。

手法

（数式書くのはめんどくさいので概要だけ書いておく）

一言で言えば、ラベルを共有する接続されたノードペアの数を最大にするように、ノードのラベルを決める。

そういうノードペアの数が多いほど大きくなる目的関数を設計し、それを最大化する。目的関数は凸じゃないから最適化がめんどくさいんだけど、ノードごとに見てやると凸になってるので、ノードごとに目的関数を最大化し、その結果を使って別のノードについて最大化するってのをメッセージパッシング的に繰り返す。

実験

ラベル伝搬法と比較。Facebookのデータを使う（著者らはFacebookの人、ずるい！）。大体勝った（そんなに圧勝はしてない）。

感想

ICMLだけど数式こてこてしてないゆるふわな感じの論文だった。アイデアは面白いし手法もシンプルでよかったんだけど実験ではあんまり良い結果にはなってないように見えた。ICMLとかのガチ機械学習系の論文はあまり読むことはないんだけど、問題定義とかすごくシンプルにかかれてて良い。逆にデータマイニング系はまぁしょうがないとは思うんだけど背景から何からイントロでいろいろ説明しようとするからもうイントロ読むだけでお腹いっぱいになる。

Label propagationとLabel spreading

machine learning

グラフベース半教師あり学習 (SSL) のLabel propagation (LP) とLabel spreading (LS) の違いを説明している文献があまりなかったのでそれについてちょっと書いてみる。SSL自体とかLP、LSについては以下の記事にまとめた文献がいい感じなのでそちらを参照。

半教師あり学習のモデル仮定 - でかいチーズをベーグルする

LPの元論文はこれ (PDF)

"Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions", ICML2003

LSの元論文はこれ (PDF)

"Learning with Local and Global Consistency", NIPS2003

まとめ

  • LPとLSの超概要、ランダムウォークとしての解釈、最適化問題としての解釈を書いた
  • 軽い実験をした
    • 基本的にLSの方がLPより高精度っぽい
    • ラベル密度が小さい時は精度の差が開くっぽい
    • ラベルにノイズが有る時は精度の差が開くっぽい

Label propagation

超概要

データをノード、データ間の類似度をエッジとしてグラフを構築し、そのグラフ上でラベル付きノードからラベル無しノードへラベルを「伝播」させる。近くにラベル１が多いノードはラベル１に、近くにラベル２が多いノードはラベル２に分類される感じ。解としてはラベルなしノードiのラベルがkである確率 F_{ik}が全てのiとkについて得られる（つまり行列Fが得られる）。ちなみにパラメータはない*1。

ランダムウォークとしての解釈

データiのラベルを知りたいとき、グラフ上でデータiに対応するノードからランダムウォークをスタートする。このとき、ランダムウォークが初めにラベルがkであるラベル付きデータ（ノード）に到達する確率は、LPによって得られる解 F_{ik}と等しい。

最適化問題としての解釈

  1. ラベル付きデータのラベルは変化しないという制約のもと、
  2. グラフ上で隣接しているノードは同じラベルを持ちやすい

というコスト関数を最小化する Fを求める。これがLPの解と等しい。

Label spreading

超概要

LPと同様にデータ間の類似度からグラフを構築し、ラベル付きノードからラベル無しノードへとラベルを伝播させる。LPとの違いはラベル付きノードのラベルも同時に再推定する点。つまり、LSはラベル付きデータ i のラベルが変化することを許す。例えば、ラベルが k であるラベル付きデータ i がたくさんのラベル k' データと類似していれば、i のラベルは k ではなく実は k' である確率が高いと出力する。これがLSのキモ。

パラメータは\alpha \in (0,1)の一つで、どれだけ元のラベルを重視するかを表す。\alphaが大きいほどラベル付きデータのラベルは変わりやすくなる。パラメータのチューニングが必要という点ではLSの方が使いづらいのかな。ちなみに元論文では\alpha = 0.99と決め打ちされていた。

ランダムウォークとしての解釈

LPと同様に、データ i のラベルを知りたいとき、グラフ上でデータ i に対応するノードからランダムウォークをスタートする。ただし確率\alphaで隣接ノードのどれかに移動するが、確率(1-\alpha)でデータ i に対応するノードに戻る。これを無限ステップ繰り返した時、ウォークがラベル k のラベル付きノードにいる確率はLSの出力F_{ik}に等しい。

最適化問題としての解釈

  1. ラベル付きデータは元々の自分のラベルからは変わりづらく、
  2. グラフ上で隣接しているノードは同じラベルを持ちやすい

というコスト関数を最小化するFを求める。これがLSの解と等しい。パラメータ\alphaは(1)と(2)の重みとして働く。LPではラベル付きノードがもともとの自分のラベルから変わらないような 制約 を入れていたが、LSでは制約にはなっていない。

実験

LPとLSはどっちを使ったらいいんだ、どう使い分けたらいいんだ、さっぱり分からん！ということで軽く実験をしてみた。scikit-learnに入ってるLPとLSの実装とDigitsデータを使った。LPとLSの他にふつーのSVMも比較した。

実験設定

Digitsデータを分類した。入力は画像データそのもので、ラベルはその画像がどの数字か(0から9)。1000サンプルのうちからランダムで一定の割合のノードのラベルを隠して分類を30回繰り返した。LP、LS、SVMのカーネルはRBFカーネルを使った。パラメータ（バンド幅、SVMのC）はグリッドサーチで決定。LSの\alphaは元論文と同様に0.99に決め打ちした。

  1. ラベル密度を変えた実験：全体のデータ数に対するラベル付きデータの割合を1%から50%まで変化させてどう精度が変わるかを見た。
  2. ラベルにノイズを入れた実験：ラベル付きデータのラベルをランダムに変更してどう精度が変わるかを見た。ノイズを入れる割合は0%から50%、ラベル密度は5%にした。

コードはここに置いたので興味のある人だけどうぞ。

ラベル密度を変えた実験

結果

  • 期待通りラベル密度を小さくしていくとLPとLS共にSVMに勝った。
  • LPよりLSの方がちょっと精度が高い。
  • ラベル密度を小さくしていくとLPとLSの精度の差が少しずつ開いていく。

f:id:yamaguchiyuto:20141202235147p:plain

横軸はラベル密度、縦軸は精度、エラーバーは標準偏差。

考察（注意：個人の感想です）

ラベル密度が小さい時にSVMに勝てるのはまぁ周知の事実。と言うかそれが半教師あり学習の強み。 面白いのはラベル密度を小さくしていくとLPとLSの精度の差が開いたところ。なんでか考えたんだけど、多分LSのランダムウォークとしての解釈のところでランダムウォークが確率1-\alphaで始点に戻るところが効いてるのかな。ラベル密度が小さいとランダムウォークがラベル付きノードに到達せずにどんどん始点から遠ざかってしまう事が多くなるけど、LSでは一定確率で始点に戻ることでそれがある程度防げるとか。

ラベルにノイズを入れた実験

結果

  • ノイズを入れる割合を大きくしていくとLPとLSの差が顕著に開く。
  • SVMは悲惨な結果だけどLPとLSは高い精度を維持。

f:id:yamaguchiyuto:20141202235150p:plain

横軸はノイズの割合、縦軸は精度、エラーバーは標準偏差。

考察（注意：個人の感想です）

予想通りの結果になった。LSはもともとラベルがついてるデータのラベルを変更することも許してるから、ノイズでラベルが変わってしまったノードのラベルも正しく修正出来たってことだと思う。一方でLPとSVMはノイズで変わってしまったラベルも"信じきって"学習した結果精度が落ちてしまったって感じかな？ちょっとわからなかったのが、LPの精度もそこまで下がらなかったところ。ラベル密度も小さいし(1000サンプル中50個しかない）、そのうちの半分のラベルがランダムに変更されているのにこれだけ精度高いとは。。。

おわりに

今回実験した限りだとLSを使っとけば問題ないという結果になった。まぁでも「どんな場合でもLSの方が優れている」なんてことは無いしLPを使ったほうがいい場面も多分あるんだろうな。分からんけど。ちなみに今回の実験の設定ではSVMが悲惨な結果でLPとLSが圧勝してたけど、これは今回はLPとLSのモデル仮定（類似してるデータは同じラベルを持つ）が正しかったからであって、どんな場合でも（ラベル密度が小さければ）半教師ありがSVMとかの教師あり学習に勝てるわけじゃない。

*1:類似度の計算にRBFカーネルを使う場合が多いので、その場合はバンド幅のパラメータが必要になる。

Semantic Stability in Social Tagging Streams (WWW'14) を読んだ

paper

WWW14から。次のWWW15はイタリアフローレンス！参加したい！

概要

Social tagging systems（FlickrとかDeliciousとか）においてリソース（Flickrなら写真、DeliciousならWebページ）に付けられたタグがどのように "Stable" になっていくかを分析。

Social tagging systemsではいろんな人が何のルールもなしに好き勝手タグ付けをするので、結果として意味を成さないめちゃくちゃなタグ付けになってしまいそうだけど、（多くの人が経験上分かるように）そうはならない。時間を追ってどんどんタグ付けされていくわけだけど、一定時間経つとあるリソースに付けられたタグの "割合" は変化しなくなる。こういう状況を "Stable" であるという。

例えば、Deliciousでgoogle.comは多分"search engine"とかそういうタグを付けられてるんだけど、Stableな状態になるとその後みんながタグ付けを続けてもgoogle.comに付けられたタグの割合は変わらない。

この論文ではStableであるという状態を表す新しい指標を提案し、それを使って三つの異なるSocial tagging systemsの違いや、Stableになる原因について論じている。

貢献

  1. Social tagging systemsがStableであるかどうかを示す指標を提案。既存の指標のいくつかの問題点を解決している。
  2. 提案指標を使って三つのSocial tagging systems (Delicious, Librarything, Twitter lists) がStableであるかどうかを分析。
  3. 三つのシステムの違いや、Social tagging systemsがStableになる原因について議論。

提案指標

直感的には、付けられたタグの割合が変化しなくなったリソースが多いほどそのSocial tagging systemはStableであると言える。

実際には提案指標では付けられたタグの割合じゃなくて、付けられたタグの順位（google.comに付けられたタグで一番多いのは"search engine"とかそういうランキング）が変化しなくなるかどうかを見る。

Rank Biased Overlap

これはこの論文の提案した指標じゃないけど、これを使ってる。

あるリソース1に付けられたタグの頻度によるランキングを{ \sigma 1 }とし、２つのランキングの類似度を以下で測る。

{ RBO(\sigma 1, \sigma 2, p) = (1-p) \sum_{d=1}^{\infty} \frac{\sigma 1_{1:d} \cap \sigma 2_{1:d}}{d} p^{d-1} }

{ \sigma 1_{1:d} }はランキングの1からd位までという意味。RBOは[0,1]の範囲の値を取り、0は２つのランキングが全く異なることを意味し、1は完全で同じであることを意味する。

{0 \leq p \lt 1}はパラメータで、0にするとランキングの1位だけしか考慮されなくなり（互いの1位が同じならRBO=1、そうでないならRBO=0）、1に近づけるほど下位まで考慮することになる。

Rank-based Stability Method

同じリソースの時刻tでのランキングと時刻t+t'でのランキングについて上のRBOを計算する。で、その値が閾値kより大きいリソースの割合f(t,k)を計算する。それが大きいほどStableであると言える。これだけ。

この値はSocial tagging systemについて決まる値なので、それを各Social tagging systemについて計算して比較する。またランダムなタグ付けをシミュレートして、それについてもこの値を計算して比較する。

提案指標の特徴三つ

  1. あるリソースに付けられたタグの割合そのもの（google.comに付けられた全てのタグの内"search engine"は割合0.7とか）を使うんじゃなくてランキングを使う。
  2. いくつかの既存指標ではランダムなタグ付けもStableである事になってしまうが、この指標ではランダムなタグ付けはStableであると判定されない（後述）。
  3. 既存指標はいままで出現したことのなかったタグを扱えなかったがこの指標は扱える。

結果

（論文中 Fig.7）

f:id:yamaguchiyuto:20141224073615p:plain

なんかすごい見づらい図なんだけど、縦軸がパラメータkで、横軸が時刻t。線の色が各Social tagging systemsに対応してて、各線はf(t,k)の値の等高線になってる。

まぁ図を読む必要も特に無いので結果だけまとめると、

  • Social tagging systemsは三つともランダムなタグ付けよりもStableだった
  • Twitterは他の２つのSocial tagging systemsよりfの値が小さかったんだけど、これはTwitterでリストを作る時に「このユーザにはこういうタグ（リスト名）をつけたほうがいいですよ」っていう推薦がないから（と思われる）
  • この図から読み取れることではないけど、Stableになる原因としてはシステムからのタグの推薦と、ユーザ達が持ってるBackground knowledge（どういうタグを付けるべきか）が挙げられる。これはシミュレーションから得られた結果 (Fig. 8) で示している。

感想

サーベイが本気。論文中で何かを主張する時は大抵文献が参照されてるか実験結果があるかだった気がする。論文書く時はホントはそれくらいしないといけないね。すごい。結果はまぁ驚くもんでもなくて、直感に反しないんだけど。どこかで「当たり前の結果を出すことが大事」みたいなのを見たことがあるし最近そう思うので、この手の分析しました論文ではしっかりとした手順を踏んで直感的なことを "示す" ってのが重要なんだと思う。