読んだ：Search Engine Click Spam Detection Based on Bipartite Graph Propagation（WSDM2014）

論文

殴り書いていくスタイル。

Search Engine Click Spam Detection Based on Bipartite Graph Propagation

クリックの情報は文書のランキングにおいて重要な要素である。
結果、いくつかのWebサイトは彼らのページへの不正なクリックの増加に
よって高ランクを得る。これはクリックスパムと呼ばれている。
不正なクリックの特徴に関する分析をベースに、
1.ユーザのセッションを行動だけでなく、セッションの目的とセッション間の
間隔もまた考慮に入れた３つの連鎖によってモデリングする
2.より不正を働いているセッションを発見するため、不正を働くユーザに有効になる
ように２部グラフの伝搬アルゴリズムを使用する
3.高precision,recallに達するような不正なセッションパターンを得るために、
パターンセッションの２部グラフ伝搬アルゴリズムを用いる
中国の一日あたり8000万クリックのデータを用いて、97％のprecisionで全体
の2.6%のクリックがスパムとして検出された。

・現実でのクリックスパムの例
a.クエリを要求した後同じURLを繰り返しクリックする
b.異なったクエリを要求した後同じドメインのURLを繰り返しクリックする

・データの収集
中国のコマースサイトから１日8000万の検索ログをランダムに収集。
時間、検索クエリ、クリックタイプ、クリックしたURLを収集
クリックログにはタグと呼ばれるものがついていて、どのタイプの検索をしたのか
わかるようになっている（画像検索とか動画検索）
ここで、検索タグとクリックされたURLに不一致が起きた場合、それはクリック
スパムだと言える。動画タグの検索なのにクリックしたURLが動画タグの結果には
存在しないなど。さらに、クリックされたURLとタグが合致しなかった場合も
スパムとする。
この処理により、収集したデータの0.54%に不正の疑いがあった。

・ユーザのセッションモデリング
セッションの定義・・・ユーザが最初のクエリを検索エンジンに要求してから
３０秒間とする。
ユーザの行動をいくつか定義
Q_i…クエリの要求。iは異なったクエリを区別するのに使う。
W_i…webの結果のクリック
O_i…スポンサーのついた結果をクリック
N…新しいページのロード
T…ページのスクロール
A_i…その他のクリック（タブのクリックなど）

また、前章とは異なり、異なったクエリや異なったリンクをクリックした場合に
別IDを与えることにする。　別クエリや別リンクのクリックは自然だが、同一
クエリの連発やリンクのクリックは不正の疑いがある。

・時間間隔
セッション内の行動が過度に頻繁であればbot的な動きである疑いがある
前のアクションから次のアクションに動くまでの時間を各ユーザの行動
毎にプロットしてやると、大体どの行動も同じくらいの時間間隔になっている。

この知見を利用してtime_intervalを4つのセグメントに分解
0秒
1-10秒
11-30秒
31秒-
すると、ユーザのセッションをモデリングできる
例：(Q0,0),(T,1),(Q0,1),(Q0,0),(W2,1),(Q1,3)...
クエリの送信->1-10秒後、ページスクロール->1-10秒後同じクエリ再送信

  • >連続で全く同じクエリ送信->1-10秒後、3つ目のページをクリック->

30秒以上経過後、別のクエリを送信->...

・セッションレベルでのクリックスパム認識
1.マルコフ遷移確率を用いた不正セッション検出
※今回の比較対象と成るベースラインの方法。
次のイベントへの遷移はその前のイベントに強く依存しているはず。
なので、ユーザのセッションをマルコフ遷移モデルで表現する。
Q_{i,j}...状態jから状態iに遷移する確率変数
Q_i...\sum_{j}Q_{i,j}
Pr(i,j)...状態iからjへの遷移確率

ここで、ユーザの各セッションにはセッション内の個々の状態遷移確率の
かけ算によって尤度スコアが与えられる。
高い尤度を持ったセッションは通常の振る舞いであるといえるし、低い尤度
であればレアな振る舞いと言える。
実際には尤度が非常に小さく成るので対数尤度＋セッション数での正規化
を行ってaverage Marcovian Loglikelihood(MLH_avg)を得る。
従った、小さなMLH_avgはセッションが正常でないことを表す尤度と成る。

この手法を１日分の5000万のユーザセッションデータで試したところ、
99.6%のセッションのMLH_avgが(-4,0]に収まっていた。従って、-4より
小さいセッションを不正なセッションと定義する。

2.不正セッション元を発見する
ラベル伝搬アルゴリズムを用いて不正セッションの元を発見、不正ユーザ、
連鎖パターンを検出する。
ここで検出された不正セッションをseedとして後述のグラフ伝搬アルゴリズム
に適用して行く。

5つの不正セッション形式を定義。
・(QAi)*:異なったクエリを投げ、同じドメインのWebページを繰り返し
クリック
・(QiT)*:同一クエリを投げ、繰り返しページスクロールを行う
・(Qi)*:キーワードの頻度を上げるため同じクエリを繰り返し投げる
・Q(Wi)*:クエリを投げた後、Webページを短い間隔で繰り返しクリックする
・Q(Ai)*:クエリを投げた後、同じドメインのページを短い間隔で繰り返しクリックする

上記の形式を一日分のユーザセッションデータで検出してみた。
その際、ユーザのセッション全体の50%以上の部分的な連鎖とマッチしたものを検出する。
各５つの形式に対して、100こずつランダムにセッションを抽出し、人為的にアノテーション
とpresicionの評価を行う。
すると、98.6%という極めて高いprecisionで不正なセッションを検出できた。

3.ユーザとセッションからなる２部グラフの伝搬アルゴリズム
何人かのユーザのセッションが不正であることがわかれば、そのユーザの他のセッションも
同様に不正なものであるという考えをベースにする。
先述の方法で検出した不正ユーザをこの方法で一気に検出する。
２部グラフを作ってみると、一日で4000万のユーザと100万のセッションから成るグラフが
構築できた。

                    • -

アルゴリズム

                    • -

sscore...セッションスコア
uscore...ユーザスコア
w_{ij}...ユーザをセッション間の重み。ユーザiがjのセッションを行った頻度。
(1)セッションにスコアをつける。2の方法によって不正判定されたセッションに1、そうで
なければ0をつける
(2)ユーザのスコアを計算。usore(u_i) = \sum_{i}w_{ij}*sscore(s_j)
(3)セッションのスコア計算。不正なセッションは再び1に設定。そうでないものは
ssore(s_j) = \sum_{j}w_{ij}*uscore(u_i)
(4)2-3の操作を|sscore_n-sscore_n-1|が指定したしきい値より小さくなるまで繰り返し

4.パターンとセッションからなる２部グラフの伝搬アルゴリズム
3によって不正ユーザのリストと不正なセッションの連鎖を得ることができる。これを
使ってすべての不正な連鎖パターンを検出する。
一定数の不正なセッションパターンとマッチするセッションがあれば、その他のセッション
も不正であるという仮定に基づく。
基本的な考えは、頻繁な連鎖パターンを求め、不正スコアをグラフに拡散させ、不正な
連鎖パターンのリストを得る。
頻繁な連鎖パターンは、連鎖データベースDを用意しておき、任意の連鎖パターン\alphaが
\alpha > \theta|D|を満たすときの\alphaとして定義される。（\thetaはユーザ指定）

                    • -

アルゴリズム

                    • -

C...不正セッション連鎖集合
P...高頻度連鎖パターン集合
S...セッション連鎖集合
w_{i,j}...セッションとパターン間の重み
sscore...セッションスコア
pscore...パターンスコア
(1)セッションにスコアをつける。先述のアルゴリズムと同様
(2)pscoreを計算。リンクがあるセッションのsscoreの値と重みのかけ算
(3)sscoreの計算。リンクがあるパターンのpscoreの値と重みのかけ算
(4)2-3の操作を|sscore_{n}-sscore_{n-1}|が指定したしきい値より小さくなるまで繰り返し

・評価
1.ユーザとセッションから成る２部グラフ伝搬アルゴリズム
アルゴリズムを一日分のデータに試してみる。
不正スコアの高かった(>0.5)セッションをサンプリングして0.1区切りでprecisionを
手動で評価する。当然スコアが高ければ高い程precisionが高くなるはず。結果としても
(0.9,1]のスコアでprecisionが0.966と成った。そして全体のログの約2.1%がこのレンジ内に
入っている、すなわちクリックスパムであった。
一週間単位で一日ずつ評価してみると、月曜、火曜、水曜でクリックスパムが多く検出された
。どうやらこういった業者やユーザは週始めにアクティブになりやすいらしい。

2.セッションとパターンから成る２部グラフ伝搬アルゴリズム
\thetaの適切な値
0.005-0.01で動かしてみると、0.01が最も良く、precisionが97%だった。1と比較すると、
クリックスパムとして検出されるセッション数が多くなる。

3.３つのアプローチの比較
上述の２つの方法+ベースライン
ベースラインのprecisionが90%に対し提案アルゴリズムはどちらも97%という高いprecision
をたたき出している。
さらに、セッションとパターンから成る伝搬アルゴリズムを使うことで、より多くの不正な
セッションを検出することが出来るようになる。
さらに、検索結果の妥当性を評価できるNDCGを利用する。
クリック数が1000以上かつクリックスパム率が10%以上のクエリを抽出し、CTRの高い順に
検索結果をソートする。
CTRを計算する際、
・そのまま
・クリックスパムによるクリックを取り除く
の2パターンを用意しておき、NDCGの値を比較する。
その結果、クリックスパムをのぞいたNDCGの方がのぞかないよりも高くなった。すなわち、
クリックスパムにより上位にきたURLがクリックスパムをのぞいたことで妥当な順番に
下がったと言える。

MACにPCをかえてバックスラッシュが打ちづらくなって初めて不便だと思った。

読んだ本とか＠2013_01

読書

仕事に追われて借りた本を中途半端なまま返す日々が続いている。

広告に近い本を２冊

アトリビューションという新しい広告指標の話。

アトリビューション 広告効果の考え方を根底から覆す新手法

アトリビューション 広告効果の考え方を根底から覆す新手法

”現状の広告効果指標では、コンバージョン（購入etc）につながった広告というのはその寸前にクリックした一つの広告に限られるが、実際にはそれまでにみたりクリックしたりしてきた関連広告もコンバージョンに寄与しているはずだ。”という考えに基づいて、他の広告にも貢献度を配分する手法を紹介している。
広告配信会社としては
・売れにくい広告の価値を上げる
・コンバージョンに至るルートの解明
などのメリットがある。
はやりのDMPなんかと繋がってくると現実味が出てきそうですね。


米国では既に取り組まれているらしいニューロマーケティングと呼ばれるものの紹介。

なぜ脳は「なんとなく」で買ってしまうのか? ニューロマーケティングで変わる5つの常識

なぜ脳は「なんとなく」で買ってしまうのか? ニューロマーケティングで変わる5つの常識

簡単に言えば、人の本音に迫ったマーケティングをもっとしていきましょうよという話でした。
現代のマーケティングでは、アンケートや大量のデータを統計解析した定量的な結果を
使って行われることが当たり前になってる。
その結果、会社ごとに差別化された商品が作られなければならないにもかかわらず、アンケートでは消費者の需要が同じような結論になることから、にたような商品しか出せなくなっていると言う主張。
そして、人間の本音は文章やアンケートではなく、脳波に顕著に現れることを説明してます。
ここでは、中国のカメラCMを例に上げていて、
アンケートでCMの印象に残った部分を被験者に聞いてみると、
・出演していたタレント
という意見が大半だったが、脳波では全く別の部分に顕著な反応が見られた。それは、
・被写体となる自然の風景が代わる代わる映し出される場面
だった。タレントが出てくる場面ではむしろ脳波の反応は弱くなっていた。
こんな感じで、建前と本音は違いますよという感じ。

あと、
・会社の名前のごり押し
・商品を隅から隅まで説明しきってしまう
・隙がない完璧な商品を作る
とかいう王道やめろ！というはなしもあって、商品にはスリルがあるくらいが実はいいみたいなことも書いてある。
ここではIKEAの例を引き合いに出して、
・わざわざ車で来させる
・自分で組み立てる
・部品に欠陥があることがある
みたいな普通なら面倒でマイナスになりそうなことが、成功の一因になっていることを紹介している。

このような脳の仕組みを利用したマーケティングをニューロマーケティングと呼ぶ。
導入には、
・ニューロマーケティングの専門家が少ない
・ビジネス側とニューロマーケティングどちらにも理解のある人がいない
・評価が定性的なものになるので、それを加味してくれる環境がないといけない

などの障害がある。

専門家が少ないとか実問題とビジネスがわかるスーパーマンが少ないというのはやや収束気味のデータサイエンティストもにたような感じですかね。

2013年終了

社会人になった。
理想と現実の差は必ずあるものという認識だったので、その辺はそこまで強くは感じなかった。
むしろ、この一年過ごした環境は自分の予想していた物よりかなりいいものだったと思う。予想がネガティブすぎただけかもしれないが。*1
個人的にはもっとじっくりやりたい仕事も多いものの、かなり短い周期でがんがんやって行くような印象なので、それについて行くだけの基礎能力が必要だなというのを強く感じた。
同期は国際会議があるたびに読み会を出来るようないい仲間に巡り会うことが出来た。

学術を現実問題に落とすことはまだ出来ていないので、それが今後の一つの目標になりそう。

来年はとりあえず残業を減らすことと、基礎能力を固めるところに重点を置きたい。
・・・といいつつ休日は部屋でぐだぐだしているでしょう。

社会人が人生で一番楽しくなりそうな気がしているみたいなことを回りに言うと”こいつ大丈夫か？”みたいな雰囲気になるのつらい。

*1:結局のところ、自分の近くにいるチームのメンバーや上長に強く依存するということだと思います。

CIKM読み回やりましたが発表しなかった

タイトルの通りです。

スライドは作ってました。無駄になりましたが・・(´・ω・`)

他の発表としては、

アクティブラーニングの話やバイオ分野でのデータ解析のLT、ディープラーニングなど、７人で開催したとは思えない濃い内容でした。

@がNIPSやろうと言ってましたが僕には読むのが困難になりそうな分野なのでWSDMまで待ちたいところですね。

読んだ：Unsupervised Social Network Spam Detection（CIKM2013)

Unsupervised Social Network Spam Detection
http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-13-6.pdf

若干読みきれてないが・・・

intro
ソーシャルネットワーク上でのスパムアカウントが増加している。
スパムアカウント抽出に関して、教師付きの学習コストを抑える
観点から、教師なしの手法が望ましい。
まず、SD2という、ソーシャルネットワーク上の関係を織り込んだ
スパム検出の手法を提案する。さらに、より高いレベルのスパム攻撃に
大して高い頑健性を持たせるために、UNIKという教師なしスパム抽出
手法を提案する。



2:データに関して
2009年のあるソーシャルブログサイトの10ヶ月分のユーザのつながりと投稿を収集
一度以上URL付きポストをしたユーザは176000人。合計で200万のURL付き
ポストがあった。
スパマーに関しては教師あり学習によって誤差1-2%程度に抽出できているらしい。
新規スパマーの増加数は極めて小さいが、投稿数は裾野広いロングテールに
なる傾向。

2.3AutoREの適用
まずはemailのスパマー検出手法を適用してみる(AutoRE)。
この手法は、URL付きのメールのポストがバーストした日数をしきい値
にしてスパマーを抽出するもの。
しきい値を小さくすると、スパマーでない人を抽出してしまい、逆に
大きくするとスパマーをうまく抽出できない。
要因として、スパマーがバースト性を持たなくなりつつあるのが原因そう。

2.4FBClusterの適用
ソーシャルネットワーク上のスパムクラスタを抽出する。
同じURLや投稿内容の類似度グラフを作成する。
この手法の場合、スパマーはうまく抽出できるが、スパマーでないひとを
スパマーだと判定してしまう結果となった。
原因として、スパマーの投稿URLの中にスパムURL以外のものを混ぜ込んで
いることがあるようだ。

3:Sylib defenseアルゴリズムの適用
Sybil attack...SNS上で大量のアカウントを作って不正行為を行うこと
3.1 SD2の提案
FBClusterがうまくいかなかったのは、スパマーがスパマーでない人と
つながってしまっているのが問題だった。これは、SybilAttackの特徴
と非常に似ている。
とはいえ、SybilDefenseの手法をそのまま適用するにはいくつが問題
がある。それは、ソーシャルネットワークがないといけないことと、
スパマーがネットワーク上に存在しているとは限らないということで
ある（なぜなら、スパマーはスパマーでない人と友達になるのは難しいから）。
そこで、SD2を提案する。これは、ソーシャルネットワークとURLの共有
関係で構築されたユーザリンクグラフを利用したものである。
・SD2のながれ
1.ソーシャルネットワーク作成
2.URLの共起で結ばれたユーザ間エッジを1に追加
3.次数３以下のノードを前処理として取り除く
4.sybilノードを低順位になるようにするために、sybil defenseを基盤とした
コミュニティ抽出法を適用する
5.sybilノードをセパレートするために、順位付けされたノードをカットする
ここで重要なのは5のカットポイントを決定することなので、今回はコンダクタンス
を基盤とした指標を使う。
あるコミュニティをAとし、その差集合をBとしたとき、コンダクタンスをA,B
間のエッジ数とする。0のとき、コミュニティA内のつながりが強く、1のとき
A内のつながりが弱いことになる。
このアルゴリズムは、スパマーでないnodeから始まり、コンダクタンスを最小化するように隣接ノードから一つ選び追加していく。

今回の方法だと最適なカットポイントが解析的に得られないのでデータから発見する。
あるノードを選んだときのコンダクタンスに対してその次のノードを選んだときのコンダクタンスの比をとると、ある程度のところまではなだらかに下がっていき、その後鋭く振動する部分が見つかるので、そこを分割点とする。
SD2は非常に高パフォーマンスをたたき出す。理由として、ソーシャルグラフの
コミュニティからスパマートそうでない人をうまく分離でき、ソーシャルグラフ
にはいなくてユーサリンクグラフにいるスパマーを抽出できているからだといえる。
しかし、SD2はsybil attackが増加するとパフォーマンスが低下する。実際に10%
のスパマーでない人をスパマーと入れ替えるとスパマーなのにスパマーと判定
できないユーザが10%増加する。

4.UNIKの提案
UNsupervised socIal networK span detection
ソーシャルグラフとユーザリンクグラフを個別に探索することでSD2の課題を
解決する。
・流れ
1.URLの共起によって作成されたユーザリンクグラフとソーシャルグラフを作成
2.ソーシャルグラフにSD2を適用し、スパマーでない人を検出する。さらに、
そのユーザらが共有するURLをホワイトリストとして登録する
3.ユーザリンクグラフをホワイトリストでトリミングし、その後残った高次数
ユーザがスパマーとなる
・ホワイトリスト作成
あるURLがあったとき、ホワイトリスト内でシェアしたユーザ数が全体のユーザ数の半数をこしていればホワイトリストに入れる。なるべくドメインやホストで構築する。
※短縮URLはどうするのだろうと思ったら、直近ですぐ解決する方法はないっぽい
・次数のしきい値決定
スパマーの方がURLを活発にシェアしやすい
リンクの重みをURLをシェアしたユーザの半数に設定
重みの設定は少量のスパマとスパマでない人を比較すればわかる。

5.評価
・ホワイトリストの作りかたについて評価。
いくつかのタイプを作ったが、domain、host、host+1path(ホストネームがホワイトリストに入っていたら、ホワイトリスト+一階層下の部分までカット対象とする)が性能が良かった。
・エッジのしきい値について
256で切るのが最も良かった。
・次に手法の性能について評価。
UNIKとSD2は非常にいい性能というかほぼ同じ性能。

ここからはUNIKの頑健性に関する評価
・sybil attackの効果
スパマーを1,2割程ネットワーク内に仕込ませても、UNIKは性能にそれほど影響は出ない。
Whitelistを使う際にHost+1Pathが最も性能がいい。hostだけだと結構性能落ちる。
・スパマーに正常なURLをもっと仕込ませたときの性能チェック
host,host+1pathともにロバストな結果

6.スパマーの分析
スパマーというか、botっぽい連投しまくるタイプのものもいれば、普通のユーザのような行動をしているものもいるように見える。そういうスパマーもうまく抽出できている。

読んだ：Predicting User Activity Level in Social Networks（CIKM2013）

論文

ソーシャルメディア上でのユーザの振る舞いに関する重要な指標は、ユーザの週次の活動レベルやアクティブかディアクティブかをクラス分類するようなアクティビティレベルである。この予測問題はSocialCRM(ソーシャル上のユーザの関係管理)を密接に関係している。

CRMの一例
誰かがある期間からインアクティブになるとき、それをその前の期間から潜在的インアクティブユーザとして予測すること


　SocialCRMは普通のCRMとは違う特徴がある。
・ユーザの多様性
・ソーシャル上の影響力
・ソーシャルネットワークのダイナミクス
　ユーザのソーシャル上の多様性からなる特徴量は、包括的な予測モデルがすべてのユーザに対して適正ではないかも知れない。しかし、おのおののユーザの過去のデータはスパースすぎて質の高いパーソナライズなモデルは出来ない。
　ユーザの影響力という特徴は、ユーザ間の関係が個々のユーザの予測結果をより大きく後押しするために埋め込まれることを提案する。　
　最後に、ソーシャルネットワークのダイナミクスはユーザの振る舞いの変化を意味する。
　本稿では、ユーザのアクティビティレベルを正確に予測するために、パーソナライズかつソーシャルに一般化された時間遅れモデルを発展させる。RENRENデータを使用し、提案モデルが一般的な教師ありモデルと比較して優れたパフォーマンスをあげることを示す。

２章：この論文の貢献は大きく分けて二つ
1.ユーザのアクティビティレベルを予測するために、統一化された最適化の枠組みの中に影響力とダイナミクスを取り入れた、ユーザのパーソナライズにエンコードした学習モデルを提案する。
2.現実の大規模ソーシャルメディアを使って提案手法がいくつかのベースラインより効果的であることを明らかにする。さらに、このソーシャルメディアに対して、利便性のある特徴量の３つのカテゴリを構築し、アクティビティレベルの予測に役立つことを示す。

数式的にやること
　グラフGと総ユーザ数Nを定義。時刻tのユーザの特徴量ベクトルをp次元のベクトルx_i^(t)であらわす。そのときのactive,inactiveをy_i含まれる{1,-1}で表す。
　時刻tでのユーザの特徴ベクトルから次のactive（y_i^(t+1)）を表す。

f:id:A_Koide0519:20131117222330p:plain

　またネットワークを重み付き隣接行列で表す。重みは友人全体のinteractionに対するのあるユーザ間のinteractionで表す。
ここでのinteractionは友人へのメッセージや写真投稿の閲覧。

f:id:A_Koide0519:20131117215720p:plain

３章：提案手法に関して
ロジスティック回帰を基盤としたモデルを構築。重みベクトルの推定式。lは損失関数。二項は正則化項

f:id:A_Koide0519:20131117215724p:plain

f:id:A_Koide0519:20131117215730p:plain

ただし、通常のロジスティック回帰モデルでは今回の問題を解くにあたり
ユーザの多様性、振る舞いのダイナミクス、ソーシャルの影響という３つの
特性を埋め込めていない。

3.1パーソナライズ
それぞれのユーザの行動は異なるのだから、モデルだってユーザごとに異なる
はずだ。なので、今の学習モデルでは正確な予測は出来ない。

そこでマルチタスク学習の手法を応用して、学習モデルを拡張。

※マルチタスク学習
学習データが少ないが似た学習タスクがある場合は情報共有することで推定精度
を向上させることが出来る。

各パラメータのを分解。正則化。
一般重みとユーザ単位の重みで学習。
ユーザ重み側のγを小さくするとパーソナライズの影響が大きくなるが過学習
することになる。

f:id:A_Koide0519:20131117220850p:plain

3.2ダイナミクスのモデル化
時間遅れパラメータの導入
損失関数項に時間遅れパラメータを導入。
昔の学習データを考慮しないように。

f:id:A_Koide0519:20131117220856p:plain

3.3ソーシャル的な正則化
ソーシャルネットワーク上では個々人のアクティビティレベルが友人の
アクティビティに影響を受ける。
フレンドリストから特に仲良しのユーザを選んで、その予測値の差分を
考慮する。ここで、C_iは友人の中でも、messageの返信や写真の閲覧を友人全体の15%以上している友達の集合。
つまりS_{i,j}^(t)>=0.15を満たすj

f:id:A_Koide0519:20131117220902p:plain

3.4最適化問題
命名：SocTiPerLR
Personalized Time-Decay Logistic Regression with Social Regularization

f:id:A_Koide0519:20131117220907p:plain

各重みは勾配降下法を使う

f:id:A_Koide0519:20131117220913p:plain

各イテレーションでは、まずw_1...w_Nを固定してw_0を最適化し、w_0を固定して
w_1...w_Nを最適化する。このとき、w_1...w_Nは独立に計算できるので並列計算
して計算コストを下げる。

4実験
データセット：RenRen中国版Facebookみたいなもの
ユーザの関係は無向グラフで表現される。
そこからサブグラフ抽出（26,418Users）。
20週間分のいろんなデータを収集。
これらのユーザの各週でのアクティビティの変化。

f:id:A_Koide0519:20131117221039p:plain

週３回以上動きがあればその週がアクティブだったとしているが、それだと
ユーザ数のバランスが悪いので、平等に扱えるようにコストb_inactive,b_activeを損失関数に加える。
※どんな風に加えるのかよくわからない

特徴ベクトル
３つのカテゴリ
action feature(28)
投稿数、写真アップロード数など
time series feature(7)
ある週のアクティブな日
平均アクティブ日など
social feature(3)
友人の数、アクティブな友人数など

比較手法
1.単純なロジスティック回帰とランダムフォレスト
2.ノード分類モデル

指標
Percision...実際の非アクティブユーザに対するうまく分類できたユーザ数
Recall...非アクティブと分類されたユーザに対するうまく分類できたユーザ数
F1score

f:id:A_Koide0519:20131117221043p:plain

20週間でパラメータのチューニングを行い、21-25週を予測する。このとき
各パラメータはどの週でも固定。


結果
比較手法に比べて提案手法はすべての週で勝っている
recallの良さが効いてる

コストb_inactive,b_active
b_active=1に対してb_inactive=4位のところが一番効果的。これ以降の所はprecisionが大幅に下がる

時間遅れ係数αは0.01がベスト。それ上大きくしすぎると近日の少量データ
に引っ張られて精度が落ちる。

βは0.1がベスト。それ以上にすると比較手法より精度が落ちる

γは1がベスト。また、この指標が極めて効いていることがわかる。
さらに友人定義のしきい値を調べたところ、S_{i,j}^(t)>=15%が最も良い

収束スピードとしては、15回程度のイテレーションで落ち着く。最初の段階で
急激に収束していることについては、パーソナライズ化が学習誤差を小さく
していることが要因だと考えてる。

CIKM読みたいリスト（読める奴だけ）

タイトルだけで選びました。はい。
DB系もグラフ関係多くて面白そうだけどとりあえずIRとKMだけから選択。

Content Coverage Maximization on Word Networks for Hierarchical Topic Summarization
CQARank Jointly Model Topics and Expertise in Community Question Answering
Estimating the Relative Utility of Networks for Predicting User Activities
Parallel Motif Extraction from Very Long Sequences
Predicting User Activity Level in Social Networks
Unsupervised Social Network Spam Detection

そのうち知り合いで読み会やるのでここから2本くらい読みます。