読んだ：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)）を表す。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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本くらい読みます。

ダイエットを宣言した話

会社でダイエットを宣言した。

詳細
・リミットは3月末まで
・評価（痩せた量）　S:15kg以上　A:10kg以上　B:5kg以上　C:0kg以上　D：マイナス
・評価がC以下だった場合、ハーフマラソンに参加する
・C以上だった場合、なんとも言えない達成感が得られそう
・断食等無理なことはしない
・一週間ごとに体重を晒す

つらそう

本を読んだ話

本を読むのはいいが論文読め！数学の勉強しろ！コードかけ！という話

パソコンができるまでの話

CODE コードから見たコンピュータのからくり

研究やビジネスのやり方の話

イシューからはじめよ―知的生産の「シンプルな本質」

CODEは読み切れなかったのが悔やまれるのでまた借りたいと思う。
慣れない内容かつページ数も500Pでさらに仕事もｳﾎﾞｧだったのでちょっときつかった。
内容としてはモールス信号の考え方から、加算器、記憶装置と進んで最後にはコンピュータができあがるというもので、この辺に詳しくないと理解するのに時間がかかる感じがする。

イシューの方は確かに仕事できる人ほどこの本で書かれていることができていると感じる。
ただ、仕事の取捨選択ってのは組織にいる上簡単にできないと思うので、そこらへんをどう考えているのかなぁとは思う。
内容としては大変参考になる。

読書とか仕事とか

読んだ本とか

孫正義とか

孫正義　リーダーのための意思決定の極意

広告とかデータマイニングとか

クリック!「指先」が引き寄せるメガ・チャンス

孫さんの方は経営にあたって重要な判断に迫られた時どうしたか、それはなぜかというのがひたすら書いてある感じ。個人的にはあまり刺さらなかったかなぁ。それはなぜかという肝心なところが薄くて、読んで得するような感じではなかったように思う。

クリックはなかなかいい本だったように思う。広告まわりとか、データマイニングとかやっている人には薦めていきたい。色々な案件において、どんな仮説でどんなアプローチの分析をしてどんなことが分かったかというのが割りとしっかり書いてある。
なによりなんでこんなにデータ持ってるの…という感じ。

仕事は思ったより忙しい。修士の時とそんな変わらない生活してた。いいものではない。

読んだ本とか何とか

本を読む習慣をつけるために、図書館に行って本を借りることにした。

数字力とか

20代で絶対に身につけたい数字力のルール

ホンネを引き出すとか

「ホンネ」を引き出す質問力 (PHP新書)

ジョブズ系の本とか

スティーブ・ジョブズ 神の交渉術―独裁者、裏切り者、傍若無人…と言われ、なぜ全米最強CEOになれたのか

ゲーム理論とか

ゲーム理論を読みとく (ちくま新書)

数字力の本は、研究でやってきたようなことがより簡潔にまとめられている内容だった。再確認の意味でよかったと思う。

本音の本は特別刺さる言葉もなかったけど、色々まっとうなことが書いてあった。遠慮なく話せる場を作るにはどうしたらよいかという話。

ジョブズの本は、元アップルの人が著者なだけに、やや偏った内容になっていると思う。また、時系列がグッチャグチャで個人的には読みにくかった。

ゲーム理論の本は期待していた（中立的な立場からゲーム理論を述べると書かれていたし）けど、読ませる気がないくらい難しい言葉を並べ尽くしているので、数十ページで読む気がなくなった。