JSAI2014行けないし、せめて個人的に面白そうなタイトルリストでも作るか
タイトルだけで読んでみたいものをまとめておく。少しずつ読んで行く。
ソーシャルメディアの情報統合によるエキスパート検索エンジンに関する研究
Twitter における候補者の情報拡散に着目した 国政選挙当選者予測
マイクロブログへの投稿に基づく政治家の立場推定
Twitter における集団的感性のモデリング
データ研磨手法を用いた Twitter ユーザの関係構造変化の検出
SNS の共有行動を用いたユーザーの興味のモデル化に対する考察 -2013 年参議院議員選挙を題材として-
- プライバシー保護データマイニング
医療データ利用におけるプライバシ保護の課題とその解決策の提案
匿名化の実社会での利用に向けての技術課題
- 複雑ネットワーク
有向ネットワークの構造が情報拡散に与える影響の分析
単語のコミュニティ性に基づいた専門用語の抽出
分散表現を用いたコミュニティにおける単語使用傾向の分析
- 位置情報
読んだ:Modeling and Predicting the Growth and Death of Membership-based Websites(WWW2014)
Modeling and Predicting the Growth and Death of Membership-based Websites
FacebookやHuffington Postのようなインターネットのスタートアップが成功する要因を突き止めるために、成功、失敗の成功メカニズムを解明する。22のメンバーシップベースのwebサイトのデイリーのユーザ数(DAU)を6年間にわたって収集。
サイトの成長・衰退パラメータと、成長法(口コミ・メディア)についてのパラメータを用意してモデル作成。
※定義(tは任意の時刻)
...アクティブユーザ(DAU)
...ノンアクティブユーザ
...メンバーでないユーザ
...WebSiteのキャパシティ
...アクティブメンバーの影響力パラメータ。ノンアクティブユーザをアクティブへ遷移させる率。
...衰退率。アクティブユーザがアクティブでなくなる率。
...口コミによる新規ユーザの加入パラメータ。アクティブユーザの行動により新規ユーザがサービスにjoinする。
...メディアやマーケティングによる新規ユーザ加入パラメータ。加入済みのユーザ以外の情報によりサービスにjoinする。
これらの動作をふまえたアクティブユーザとノンアクティブユーザの増加数を以下のように定義
4つのパラメータが持つ意味
...DAUが長期にわたって継続して存在する状態(成功)
...DAUが時間の経過とともに衰退(失敗)
...初期の段階から順当にユーザ数を増やし、ある程度の段階で落ち着く
...最初は全くユーザ数が増えないが、時間の経過とともに急激に増加する
上記の式とパラメータを、各WebSiteのDAUに対して調整していく。パラメータの推定にはレーベンバーグ・マーカート法を利用。学習に利用するデータは最初の3-6ヶ月の間。
※結果
との値から各サービスを成功と失敗に分類。ここで言う成功とは「持続性がある」こと。
代表的なものだとlinkdinやfacebookなどがここに属する。失敗だと、memolane,12seconds(知らない)などがここに当てはまる。
続いてこれらのSiteの成長についてみてみると、多くのサイトがユーザの口コミで成長していることがわかる。mediaの影響を大きく受けている中にはebayなどがあった。
上記の結果から、成功パターンと失敗パターンを以下のようにパラメータを調整して長い期間で予測する。
-
- -
成功:
持続型かつ口コミによって成長する
失敗1:
持続性がなく、主にメディアによって成長する
失敗2:
持続性がなく、主に口コミによって成長する
酷いイメージ図だ・・・
すると、サイトにもよるが多くの場合数年レベルでのDAUの予測がそこそこうまく出来ている。データの中には大きなイベント(アメリカ大統領選)が含まれているものもあり、さすがにそれを予測するのは難しい。
貢献としては、DAUという情報のみを利用して、その予測がうまくできるモデルを提案している点。
実際に結果を見てみると、うまく予測できているとしている部分もなかなかに外している所もある...
サービスレベルでここまでやった論文は見たことないので、その部分も貢献も大きそう
読んだ:Adscape:Hervesting and Analyzing Online Display Ads(WWW2014)
Adscape:Hervesting and Analyzing Online Display Ads
ディスプレイアドに関する多角的な分析。特にターゲティング広告に関する分析になっている。
Adscape:ゲーム内に広告を配信する技術を開発している会社。大正義G社によって買収。
今回の論文ではデータの収集部分にもかなり力が入っており、クリエイティブ(広告の制作物)やランディングページ(広告のクリック先のページ)に関しても収集する。
分析の結果、ターゲティングは広く利用されているが、配信される広告がユーザのプロファイルに依存しない多くの例があることがわかった。
さらに、ターゲティングが使われる際に、特定のタイプのアドはユーザのプロファイルの詳細や、ユーザの訪問パターンと一致することがわかった。
※adscapeの考え方
ユーザがWebページに時刻tでアクセスする。の配信者はアド集合をにみせる。さらに配分関数を定義。この関数は、以下のものに依存。
1)ユーザのデモグラ
2)サイトwの内容
3)時刻t、ユーザの過去の行動やwの過去のコンテンツ
4)アド集合
5)インセンティブや市場の状況
最終的な目標は、これらをクローリングして追跡することでユーザターゲティングの様相を理解すること。
データの収集の方法がかなりしっかり書かれていた。(カット)
●データの収集
314Webサイト(主要Webサイト)と340カテゴリ(Google独自の技術)を準備。
2日間でおよそ80万のimpsと17.5万のアドを収集。3700の広告主と106のアドサーバから成る。
●分析
・Webページとプロファイルの重要性
ユニークアドの90%は、世の中の2%のWebページで表示されている。(GとかYとかBとか)
・ページに対する広告数
1pageに対して大体2-4くらい広告がつく。そしてその広告はたいてい異なった広告主で構成される。
・各ページのターゲティング比率
50%以上のWebサイトが80%の広告の在庫をプロファイルターゲティングに使用している。その中でも性別と年齢を属性として利用しているサイトが多い。
・カテゴリに対するimps数
金融関係の広告が一番多い。ショッピング、コンピュータ、ビジネスと続いて行く。
・プロファイルとアドのカテゴリの関係
impsを使ってプロファイルとカテゴリの相関関係をヒートマップ化
1)ゲームや健康、ショッピングはプロファイルとアドのカテゴリが一致する傾向がつよい。
2)いくつかのプロファイルは関連性のあるカテゴリからターゲティングされていて、美と健康のプロファイルはショッピングやトラベルと、ペットは家と関係が強い。
3)アート、エンターテイメント、ビジネス、コンピュータ、ショッピングのカテゴリの広告はターゲティングされる傾向が小さい。どのプロファイルにも平均的に広告が配信されている。
注:2と3の結果に若干の矛盾を感じる...ショッピングはターゲティングされていないと言っているのに...
4)興味深いことに、プロファイルのついていないimpsはレストランカテゴリの広告がよくあたっている
いくつか面白いものもあったけど、衝撃的な発見!という感じではないっぽい。こういうのを先頭切ってやるって言うのが大事な感じがする。
ざっと読んだ:Partner Tiering in Display Advertising(WSDM2014)
ざっと見たときにグラフ系+広告の話と思って読んでみたけど、グラフという程ではなかった感じ。これは広告に詳しい人の解説がほしいなぁ
ディスプレイ広告に関する論文。
広告配信システムは、契約を満たすように広告主の代理としてページに広告を配信し、配置の質を最大化することを試みている。
一般に、このようなものをモデル化する際には、オンライン上の配置問題として考えられる。
しかし、広告主と発行者の間の契約の常用な部分のほとんどが、これまでの数式では考慮されていない。それは、発行者が決まって媒介者(配信システム)として表され、広告主は媒介者から在庫を購入するからである。
発行者は質、重要性ともに様々であり、かつ広告の在庫は限られているので、広告配信システムとしては高品質の発行者を選んで行きたい。
そこで、この問題をそれぞれのimpressionがその重要性から導かれたレベルを持った、オンライン上の配置問題として定式化する。
広告配信の話
一般的には、プレミアムパートナーの在庫を抑えたとしても、広告主
の需要と比べてパートナーからの在庫が余る。
プラットフォームの目的
1)広告主の需要を満たす
2)プレミアムパートナーに対する高水準を保証する
3)在庫は、広告主毎に価値が異なるので、配分されたimpressionの価値を最大化する
具体的な在庫と広告のマッチングの例
x)プレミアムパートナーの広告を当てる。一方で広告主に対してプラットフォーム生成した総クリック数が最適でなくなる
y)CTRの高い広告を当てる。総クリック数は最大化されるが、CTRの低いプレミアムパートナーを捨てることになる
z)どちらも平等に当てる。
●定義
広告主:
広告主は回impressionしてほしい
それに対してm人のパートナーが媒介者(配信システム)となる
パートナーにはプライオリティに基づいて1-Lまでのレベルがつく
オンライン上の設定ではj回めのimpressionをとする。
そしてimpressionはパートナーのレベルを引き継ぎそれをとする。
と間のCTRを とする。
●アルゴリズム
※DUAL-SCALEアルゴリズム
...広告主に割り当てられたレベルlのimpressionの総重み
が与えられたときにスコアが最大に成るのは以下の式を満たす広告主i
は高水準なimpressionによって導かれるコブ(?)のようなもの。
の時、レベルl+1以上のweightを完全に無視する。
の時、各レベルを計算する一方ですべてのimpressionが広告社に平等に割当られる
この2つの特殊ケースに対する理論保証のはなしがつらつら。
※EW-SCALINGアルゴリズム
スケールファクター:
...広告主A_iに割り当てられる、impressionの平均重み
が与えられたときにスコアが最大に成るのは以下の式を満たす広告主i
●実験
3つの匿名の発行者を準備。各々の発行者に関して完全なimpressionのセットを収集。
各々のimpsに対して興味を持った広告主、CTR、impsのタイプがついている。また、
広告主に対して配信契約もついている。
impsのレベルに関しては1-10の間で3つの付け方を準備
1)impsのタイプ
2)80%の確率でimpsのタイプ、残りはランダム
3)ランダム
今回は1を採用
データセットも3タイプあって、impsの重複具合が異なる。
a)広告主が狙うimpsが1-わずかなレベルに分布
b)中間くらい
c)広告主が狙うimpsのレベルが各レベルでほぼ同じくらい
※評価
Fill-Rate...広告主に割り当てられたimpsの比率
Under-Delivery...全広告主の未処理のデマンド数
Over-Delivery...前広告主のあふれてしまったimps数
Total Weight of Matching...グラフの重み->広告主の総クリック数に成るはず
パラメータやデータセットを色々かえて実験しているが、評価指標やデータセット
ごとにそれぞれの提案手法が良かったりベースラインの方が良かったりしている。
結論もないので結局どれが良かったのかがよくわからない...!
読んだ:Modeling Opinion Dynamics in Social Networks(WSDM2014)
Modeling Opinion Dynamics in Social Networks
かいつまんで読んだので適当。
ネットワーク上のユーザが周辺のユーザを参考にして意見を繰り返しかえたり、世論の構造を理解することはバイラルマーケティングや情報拡散において重要。
本稿のモデルは周辺ユーザを参考にして意見を変化させるモデルをベーストしたものでBIASEDVOTERMODELと呼ぶ。
このモデルを利用することで、意見の同意や対立が自然に表現できることを示す。
社会心理学者のAscy氏らが提唱している、”white is black”
という現象に基づいている。これは、もし周りの人間が同じことを
言うと、自分の意見が真逆でも高確率で揺らぐというもの。
※Ascyらが行った実験
被験者がある部屋におかれる。その際数人の引き立て役を用意する。
彼らは真であることが自明である質問に対して必ず偽の回答をする。
その結果
1)協調の限界はグループの大きさに依存する
2)一人でも引き立て役が味方になると協調性が顕著に下がる
という知見を得ている。
※Deutsch,Geraedの実験
協調を2つのタイプに分類した
1)normative...被験者が社会的受容を得るかのように協調する
2)informational...被験者が他の人に自分のevidenceを答えた後、最終的に周りの決定に合わせる
・contribution
上記の現象をオンライン上のユーザで実験することで、その結果を取り込んだモデルを提案する。隣人のサイズだけでなく意見の分布、被験者とその意見との距離感も考慮する。意見の質/量を取り入れる。
●オンラインユーザを利用した調査を行った結果、ユーザが最初の意見をもってから最後の意見を決めるまでの振る舞いは、votermodel的に任意の隣人の意見を採用するパターンと、DEGROOT的に周辺のユーザの意見の平均を採用するパターンと最初の自分の意見から曲げないStubbornパターンが存在することがわかった。
さらに、votermodelの部分に関しては、ユーザの最初の意見に近い人の意見を採用しやすいというバイアスがかかっていることがわかった。
これらを考慮したモデルBIASEDVOTERMODELを提案する。
これはDEGROOTモデルとVOTERMODELを組み合わせたもので、そこにStubbornパラメータとバイアスパラメータを用意する。
モデルのダイナミクスについて確認するため、ランダムグラフとPower-lawグラフを用いたシミュレーションにより、モデル(特に今回導入された二つのパラメータの効果)について述べている。
個人的にはあまり刺さらなかった。Opinion Dynamicsを考えるときに何を持って人の意見と言っていいのか知りたかったので、そこらへんに言及しているかなぁと期待して読んだ感じだったが、そういう論文ではなかった。正解データがないのが大変な感じがする。
読んだ:Learning Social Network Embeddings for Predicting Information Diffusion(WSDM2014)
情報拡散の分析・モデル化は既知のグラフや近接的な構造の上で扱われる。
しかし、複数のアクターとメディアの相互関係による潜在的な現象は複雑であり、
既存のモデルや限られた仮説だけでは説明できない。
我々は、この問題に対する新たなアプローチとして、連続的な空間上に
観測された時間的なダイナミクスをマッピングする。
拡散カスケードに関係するノードは潜在的に表現された空間に投影される。
これは、投影空間内ノードの近接性をカスケード内の感染時間の近接性に
反映した拡散カーネルを学習することになる。
提案手法はいくつかのこれまでにない特徴を持っていて、
・パラメータはカスケードサンプルから直接学習し、それまでの拡散構造には従わない
・等式が投影空間内に閉じた形で表されることから、離散的なモデルに比べて予測に対する推定が早い
本手法の拡散予測の精度並びに推定スピードが既存のものより優れていることを示す。
カスケードからユーザ間の情報拡散における距離感を潜在空間に写像してあげるイメージ。
●定義とモデリング
N人のユーザ集合U
Cカスケード集合
...学習用のカスケード集合
...テスト用のカスケード集合
...カスケードの情報源
...カスケードcに含まれるユーザ集合
...カスケード内でユーザがアクションを行った時刻
...カスケードcの特徴ベクトル
Qは特徴空間の大きさ
「アプローチ」
観測された拡散過程を連続(ユークリッド)空間に配置すること。
そのために、カスケード集合からダイナミクスをとらえることが出来る拡散カーネルを学習する。
...n次元ユークリッド空間で定義される潜在空間
カーネルの学習は、今回で言えば空間Zの特定位置にノードを配置することであり、
潜在空間は学習用のカスケードから得られた感染時刻を表す。
「この手法の利点」
- 連続空間への配置問題は従来からある最適化法で容易に解ける
- グラフ構造や拡散傾向の仮説を作らなくてよい
- シミュレーションの必要がない
- 他の情報との統合が容易
「拡散カーネル」"CDK"
幾何学的多様体を定義する。
その際、拡散カーネルをと表現する。
カスケードの情報源yと時刻tと位置x
ただし、のとき
はディラックのデルタ関数
n次元のユークリッド空間に対して、拡散カーネルは以下のように書く
「潜在空間内の拡散カーネルの学習」
ベストな拡散カーネルを学習する問題。
拡散カーネル関数を以下のように置き換える。
情報源が与えられた時の時刻tでのの感染スコアを返す。
潜在空間ないのユーザの位置。
最終的にこんな感じ
この問題は、どのように情報が拡散したかをモデル化すること、すなわち
各カスケードcに対して最適なZを見つける問題となる。
このときの経験誤差(標本誤差)を以下のように定義する。
は、情報源が与えられた時の、拡散カーネルと
観測されたcとの差異。最終的には、経験誤差を最小にするようなZを推定
する問題となる。
また、2つの制約条件を与える。
1.任意のユーザとがあるカスケードcに存在し、の方が早くアクションをとった、すなわちの時、は以下のように定義される。
2.任意のユーザとが、はカスケードcに存在しは存在しないとき、
は以下のように定義される
[Zの学習]
学習には確率的勾配降下法を使う。潜在空間上のユーザ間の位置関係を学習率を使って修正して行く。
[感染過程の算出]
情報源から各ノードの距離を計算するだけ
これらの操作から、既存の手法よりの高速に処理が可能になる。
※実験部分では速度の向上には全く触れられていない...
「属性を使った拡散カーネル」"CSDK"
情報の内容によって拡散の仕方を変える。contentsを表す特徴ベクトルを拡散カーネルに導入して、ユーザ間の位置関係がcontentsにも引っ張られるようにする。
●実験
データは3つのWebデータ。
ブログの投稿関係グラフ、Memetracker、Digg(Facebookのシェアみたいな感じ?)
ベースラインではユーザ間の関係を表したグラフを使うが、提案手法では当然
使わない。
評価手法はMean Average PrecisionとPrecision-Recall Curve
情報源を与えたときに、早く伝わるユーザから順番に並べていく。
そのランキングが実際のカスケードで伝わった順番とどれだけ合っているか。
ベースラインとして5つ用意
1学習データで影響を受けた回数をそのままスコアにしたもの
2学習データで早く感染しやすいユーザ程感染スコアを高くする
3ICモデル...グラフ構造と拡散確率
4Netrate...グラフ構造を必要としない
5GraphDiffusion...グラフ構造を利用したカーネル法
提案手法がほとんどの場合で良いスコアが出る。
contentsを導入した手法CSDKが最も性能が良かった。
●所感
内容としては普通に面白いけど、自分が期待していた期待影響度最大化とかそういう話ではなかった。実際のソーシャルネットワークでの、グラフ構造上でのユーザ間の関係と、情報拡散上でのユーザ間の関係は実はこんなに違うんですよ的な話のほうがしっくりくる感じがした。
読んでる途中で"これ最終的に伝わった人数とかどういう風に推定するんだ?"と思ったけど、評価の部分でようやくそういう問題設定じゃないんだなと納得できた感じだった。問題設定の部分とかちゃんと読めてなかったのかな。
メモ:Visualizing Brand Associations from Web Community Photos(WSDM2014)
Visualizing Brand Associations from Web Community Photos
見た目が大変良くて読み始めたけど途中で完全に沈没した。
アウトプットはものすごくビジネス受けしそうな感じはある。
1st autherがdisneyの人
・ブランドアソシエーション...マーケティングにおける主要な発想のひとつで、
ブランドに対する消費者のtop-of-mindな属性や感性を表現すること。
・top-of-mind..."〜と言えば?"と訪ねたときにまず最初に思い浮かぶもの
伝統的に、ブランドアソシエーションは消費者の反応のテキストデータや、
オンライン上の会話ログを分析することで行われていた。
本稿では、オンライン上の大規模な写真群を活用することを提案する。
技術的なステップ
1)ブランドと関連づける核となる抽出・可視化の発想
2)イメージ内でブランドの領域を局所化する
48ブランドの500万の画像をオンライン画像共有サイトから収集。
提案手法のブランドアソシエーションがテキストからではほとんど
得ることが出来ないようなブランドの補完的な見方を発見できる
ことを示す。
図を見るのが一番早い
((eg:http://www.cs.cmu.edu/~gunhee/publish/wsdm14_brandassoci.pdf fig1(a)))
1)ネットワークもしくはマップでブランドに関連づけた重要な概念
を視覚化する。画像群をクラスタリングして低次元空間に射影する。
2)教師なしの方法で、最もブランドに関連づけられる部分画像を抽出
する。
○問題の定式化
・データ収集
4つのカテゴリ(高級品、スポーツ、ビール、ファーストフード)計
48カテゴリ500万の画像をFLICKER等の4サービスから収集。
・アプローチの流れ
a)各ブランドの画像集合を準備
b)画像の類似度に基づいてKNNグラフを構築
c)グラフから標本として代表的な画像の集合を発見する、そして
画像集合を標本集合に基づいて分割する。
d)ブランドの局所化を画像分割の研究で活発に議論されている
cosegmentation問題として扱う。
○アプローチ詳細
・画像間の類似度行列からKNNグラフを作成する
画像のメタデータ(同様の所有者・同時間に投稿された)も類似度
として利用する。
・KNNグラフを利用して標本を抽出する。ダイバーシティランキング
アルゴリズムというものを利用してL個の標本を抽出。
続いて、ランダムウォークを利用したクラスタリング手法によって
画像群をいずれかの標本グループに属するようにクラスタリング。
・ブランド局所化
上述の処理によってL個のクラスタが作成される。
各々のクラスタに対し、MFCアルゴリズムというものを利用し、
各画像を前景と背景に分離する。
○ブランドアソシエーションマップ
ラジアル距離と角距離を利用してクラスタを円形の図面上に描画する。
Nielsenのアルゴリズムを今回のアソシエーションマップに適用できる
ように改良。目的としては、各クラスタの極座標
を求めること。
○実験
・クラスタリングの妥当性とブランド局所性を、いくつかのイメージに
手動でアノテーションしたものを準備しておいて評価に使う。
クラスタリングではスペクトラルクラスタリングやK-means、ブランド
局所性ではLDAなどをベースラインとして利用し、提案手法の妥当性
を示している。