読んだ:Cross-Device Search(CIKM2014)

GWは風邪を引いてほぼ寝ていました。●畜なのか平日は風邪をひきません。

http://research.microsoft.com/en-us/um/people/ryenw/papers/montanezcikm2014.pdf

デバイスを跨いだ検索の理解(トピックなど)と、デバイス遷移予測モデルの構築。
デバイスの遷移が予測できれば、例えば、PCからスマホにデバイスを変更した検索した人に対して、スマホ向けの短い記事を優先的に提示するといったデバイスに特化した試作を打つ事が出来る。

・デバイスとして、PC,tablet,smart phone,game consoleの4つを選択。

-データセットと基本的な特徴

コマース系検索エンジンから数ヶ月分の検索クエリを取得。

・クエリベースの統計量

クエリ数がおよそ2億で、複数デバイスを利用しているユーザーが検索したクエリ数はおよそ16%だった。また、PCのクエリが全体の9割以上になっている。

・ユーザーとdeviceに関する統計量

デバイスのうち、2つ以上のデバイスを利用しているユーザーが5%(!?)、複数デバイスの組み合わせとしては、PC-Tabletの組み合わせが3%で最も多い。

・クエリとトピックの分布

独自のクラス分類方法で50程のカテゴリにクエリを分類。さらにカテゴリは高確率に出現した15トピック(TV&movie,TVなど)にグループ分けした。
また、デバイス間で特徴的に出現するクエリを調査するために、P(topic|device)とP(topic)のPMI(自己相互情報量)を利用する。
各トピックに適用した結果、GameConsoleにおいてGAMINGトピックのPMI値が高く(当たり前)、smartphoneにおいて、foodトピックのPMI値も高かった。
次に、時間の遷移を加味したPMIの遷移を見て行く。デバイスごとにPMIの変化が大きく出たtopicを見ると、game consoleが全デバイスの中で最も滑らかなPMIの変化をしている。topic目線で見るとadultとfoodが非常に特徴的で、adultgは労働時間帯はPMI値がnagative rateであるが、22-4時位にかけてhigh positive rateとなる。一方で、foodは昼時と夕方にspikeが出来る特徴がある。

-デバイス間遷移

Markov Graphの様な自己遷移も含めたデバイスの遷移グラフをかいてみる。なお、遷移として認めるのは3時間以内とする。
これだと自己遷移が99%以上になるので、他デバイスへの遷移だけを示したグラフをかいてみる。
これを見ると、各デバイスからの大多数の遷移がPCに向かっている事がわかる。また、PC-smartphoneとPC-Tabletには密接な関係(高密度な相互リンク)がある事がわかる。

・次のdeviceへの遷移と遷移前に検索したトピックの関係
基本的にはPCへの遷移に引っ張られる(全体で見たときの遷移率はPC-63.9%,SmartPhone-11.2%,Tablet-24.6%,Console-0.6%)が、一部のトピックではあるデバイスへの遷移確率が全体と比較して非常に高いものが見られる。例えば、Events-Nightlifeに関するクエリを検索した後に遷移するデバイスがGameConsoleである確率は、全体のものと比較して870%も増加する。

・過去の時刻と次のデバイスへの関係

PCは事前の検索時刻が午前7時から午後5時の時に遷移しやすい。SmartPhoneやTabletは早朝や深夜、GameConsoleは0-4に検索された後に遷移しやすかった。

・デバイス遷移時間差

クエリ間の時間差を、すべてのデバイス間遷移を考慮したサイト、クロスデバイスで遷移した際で比較してみる(時間差と比率のlog-log plot)。すると、クロスデバイス遷移時間差は、なだらかなベキ則分布となる。

-デバイス遷移予測

これまで見てきた特徴が遷移予測の精度にどのくらい影響するかを調べる。
予測タスクとして3つ用意。
task1.次に利用するデバイスを予測する
task2.2つのクエリ間でデバイスの遷移が起こったのかを予測する
task3.デバイスが変化したときに、次のデバイスを予測する

データセットは予測タスクに合わせて3つ用意
1.Main:すべての遷移情報を含んだもの
2.Balanced:同一デバイスへの遷移とクロスデバイス遷移を同量含んだもの
3.Cross-Device Only:別デバイスへの遷移だけを含んだもの

特徴量は177個用意(予測結果で必要なものだけ述べる)。
学習モデルとして、L1正則化ロジスティック回帰とGBDTを利用。
Baselineとしては、
1)データセット内で最瀕のものを選択
2)ランダム
3)学習中に出現した比率にそってランダム
を用意。

どの3つのタスクにおいてもベースラインと比較して25%以上の精度が向上した。
task2,task3ではそれぞれどの特徴量が効いているかを調べており、task2ではユーザー独自の情報(過去の遷移情報(遷移数とクロスでバイス遷移数)、過去のデバイス使用率、デバイス間遷移確率、遷移時間差)とデバイス遷移時間差が非常によく効いており、task3ではユーザー独自の情報だけですべての特徴量を突っ込んだものとほぼ同様の精度が出せる事がわかった。

読んだ:Reduce and Aggregate: Similarity Ranking in Multi-Categorical Bipartite Graphs(WWW2014)

数式追えてないのでざっくり。数式よまないとこの論文はいかんけど。

Reduce and Aggregate: Similarity Ranking in Multi-Categorical Bipartite Graphs

大規模な複数カテゴリからなる二部グラフから、ユーザの類似性をランキングする問題を扱う。
ここで言う二部グラフは、ユーザとアイテム(どちらも複数のカテゴリに分割される)
から構成される。
二つの挑戦
1.2部グラフは巨大でいびつ(数百万の広告にたいして数億のクエリが結びつくような)である
2.可能な限りのカテゴリの組み合わせを、結果ごとに再計算するのを防ぐ
グラフで類似度を測る際に一般的に利用されるCommonNeighborやPersonalizedPageRank(PPR)を使う。

●計算方法
今回のフレームワークはreduceオペレーターとaggregationオペレーターからなる。
reduceオペレータ(\odot)・・・actorとitemからなるグラフをactorの集合から成るグラフに落とす。
aggregateオペレータ(\oplus)・・・actor集合を類似度に応じてランキングする。

G=(A \cup B,E):重み(非負)付き無向グラフ
N(a,G):ノードaの隣接ノード集合
sim_{a}(b,G):aに対するbの類似度
ノードaのランキングはG(・,G)を降順ソートする事で得られる。
今回はitem集合Bが非常に巨大である事を想定しているので、そのままランキングしようとすると膨大な計算量がかかる。なので、reduceオペレータによってactorベースのグラフに落とし込むのが非常に重要になる。

reduceオペレータを構成する上での問題
問題1.二部グラフG=(A \cup B,E)が与えられたとき、類似度関数を新たな重み付きグラフG(A',E)に対して計算し、sim_{a}(b,G)=sim_{a}^{*}(b,\hat{G})とする。

  • >各itemのカテゴリC_{i}に対して、actor集合Aのみから構成されるグラフ\hat{G}_{i}[A \cup C_{i}]を計算。そして、任意の2ノードに対して類似度を計算する。

問題2.リアルタイムに複数カテゴリのaggregationを行わなければならない。任意のカテゴリ集合D={C'{1},\dots,C'_{c}}と削減済みグラフ\hat{G}_{i}[A \cup C_{i}]が与えられる。G'=G[A \cup C'_{1} \dots \cup C'_{c}]をGの誘導部分グラフとして定義し、すべてのaに対して類似度ランキングsim_{a}(・ ,G')を求める。

この二つの問題を解決するためのノードの類似度をはかる手法について考える。

[1]CommonNeighbors
[2]Jaccard係数
[3]Adamic-Adar
[4]Katz
[5]Personalized PageRank

それぞれの指標に関して、reduceとaggregationの方法について記載されている。
KatsとPersonalized PageRank、特にPersonalized PageRankは複雑。

●実験
データセット
・query-ads
アド(A)とクエリ(B)から成る二部グラフ
正解データ:google AdWordsチームより提供
・DLBP
著者(A)と論文(B)から成る二部グラフ
正解データ:論文のtitileのbi-gramをとってその類似度
・parent
特許?
正解データ:共通引用数?

presicion-recallCurveで評価。topKのランキング結果に対して評価。
結果を見ると、KatzとPPRが他の指標に比べてよい結果。DLBPデータに関しては正解データにそもそもノイズが多いので、Recallが低くなりがち。
Katzのパス長の深さを増やしても結果にそこまで影響はなかった。(l=5と7の比較)
PPRに関しては、aggregation部分のiteration数を増加してやる事で、より精度を上げられる。

JSAI2014行けなかったしいくつか読んでみる-Twitter-

足を痛めたので会社行きたくない

Twitter における候補者の情報拡散に着目した 国政選挙当選者予測

Twitterデータを利用して国政選挙の当選者を予測する。既存の手法で使われていたフォロワー数等の指標に加え、情報拡散の規模、多様度、忠誠度の3つ新たな指標を提案。

まず情報拡散支援者を定義。候補者のツイートをRetweetしやすいかつそれなりにフォロワー数が多いユーザ。
情報拡散規模・・・情報を受け取るユーザの期待値
多様度・・・情報拡散の際、情報支援者のなかで、相互関係にないユーザにどのくらい情報が伝わったかを加味する。支援者同士が同じコミュニティにいない方が多くの人に情報が伝わりやすいという仮定。
忠誠度・・・支援者がRTする全候補者のツイートのなかで、任意の候補者をRTする割合を考慮した指標。

分類モデルとしては、Random Forestを使用。
比較として、既存手法(候補者フォロワー数の推移)、本研究で収集したフォロワー数やツイート数などの基本指標のみを利用した予測、基本指標に比べ提案した3つの指標をプラスした予測で比較。
提案手法が既存手法に比べて約70%、さらに指標の追加で12%精度が上昇した(F値

※この手の予測問題、研究としてどのくらいすすんでいる
か把握できてないけど、H社のAKBやY社の議員予測が精度も高く、インパクトもあったのでデータ持っているところが強いのかなぁという感じがした。RTには善意も悪意もあるところを見極められると精度が上がりそうだろうか。ただそれをやるには大変手間がかかるし手間ほどの精度向上が見込めなさそうな感じはする。

Twitter における集団的感性のモデリング

Twitterにおける集団的感性の時系列変化をモデリングする。基本の感情6つ{怒り,恐れ,嫌悪,幸せ,悲しみ,驚き}を感情語とし、ツイートをスコアリングする。
(1)内分比
G検索で感情語を検索し、上位1000件の検索結果の概要にある名詞、動詞などをリストとして登録。ある単語tと特定の感情語リスト内の共起確率と、すべてのリスト内の共起確率の比を内分比S_i(t)とする。これをツイートないの単語を使って、ツイートを6次元の感情ベクトルに変換する。
(2)任意の感情語と単語の類似度をスコアとする。2つの単語をG検索し、出現の有無を素性としてコサイン類似度を求める。これをツイートないの単語を使って、ツイートを6次元の感情ベクトルに変換する。
(3)Weblioから類語を収集。各感情の類語ベクトルとツイートの単語ベクトルの積集合を要素とした6次元感情ベクトルを作成する。
収集期間内に集めたツイートを日付ごとにわけ、各日の集団感性とする。3つの手法で感情の相関係数をはかると、(3)が最も無相関に近かったので、この手法を利用する。6つの感情間の相関係数を見ると、悲しみと驚きの間は完全な無相関である事がわかった。嫌悪と怒りが最もせいの相関が強いなど、妥当な結果が得られている。
実際に感情の変遷を見てみると、クリスマスイブで恐れが低下し、幸せと悲しみが上昇している(!!)
悲しみの上昇は

クリスマスに対して悲観的な人々がいることを考えると妥当

とのこと。泣ける。

※感情の独立性を仮定しているので、無相関に近い手法で分析しているけど、現実的にはっきりしないので何とも言えない感じになっている。分析の結果としては妥当にみえるので問題なさそうだが・・・イベントと結びつけたコミュニティ単位での感情の遷移とかぜひ見てみたいですね。

データ研磨手法を用いた Twitter ユーザの関係構造変化の検出
育児に関するツイートの要約。ユーザの単語の類似構造の時系列変化視覚化して話題の変化を検知し、ツイートの単語類似度グラフからクラスタを抽出する事で単語クラスタ(要約)を出力。
グラフの研磨手法として、作成された類似度グラフにさらに任意の2頂点間の類似度があるしきい値を越えたときにリンクを加えて行き、グラフの密度の濃淡をはっきりさせた上で極大クリークを検出する。
このクリーク集合に出現した単語の遷移や有無を時系列で可視化する(Sankeyダイアグラム)ことで、構造変化を視覚化する。
安部首相の「育休3年」発言に対するツイートを収集。まず研磨手法を用いた手法(提案手法)と単純に類似度グラフからクラスタリングを行った手法を比較すると、提案手法はクラスタ数が減り、単語数も増えた。話題の差異をみると、
・安部首相の発言前には育児休暇の取得に関するツイートが多かったが、発言後には発言に対する意見表明が増えた
・男女間では、女性の方が大きく反応していた
・子供の有無でも社会保険や雇用の話しなど、それぞれで反応が違った

クラスタリング部分で

一般グラフのクラスタリングについては,ニューマンクラスタリング,グラフ分割,極大クリーク列挙など,これまでも様々な手法が提案されてきたが,どの手法も問題点を抱えており,決定打になっていないというのが現状である.

とあったが、個人的には今回の手法も「単語間類似度がユーザ指定のしきい値を越えたらグラフを張る」といったユーザ側で設定が必要な値が存在しており、クラスタ抽出という意味では他手法と比較してそこまで有用性を感じなかった。クラスタリング前提の報告なので、その有効性を示すなら他の手法との比較がメインになるような気がした。関連文献で十分にその辺りが示されているのかもしれないけど。

JSAI2014行けなかったしいくつか読んでみる-複雑ネットワーク-

昨日は読んでいたら3時回っていて、駅まで全力ダッシュするはめになったので平日は自重気味で行く。

有向ネットワークの構造が情報拡散に与える影響の分析

ネットワーク構造と情報拡散の関係を明らかにするため、ネットワーク関する13個の指標を用意。ある一つの指標だけを変化させ、そのネットワークで情報拡散シミュレーションを行う。指標の増減と情報が伝わったノード数(以下期待影響度)との相関を見る事で、情報拡散と関連の強い指標を検出する。
その結果、ノード内次数相関と期待影響度に極めて強い相関がある事がわかった。ノード内次数相関が高いということは、任意のノードの入次数と出次数がほとんど同じ本数だけあるという事になる。
そのほか、到達可能率(任意の2つのノードの組み合わせに対してリンクをたどって到達できる比率)や次数相関に関連した指標が相関が高く出ている。
これらの結果を考慮したネットワークを作成してみると、高い到達可能率・ノード内次数相関によって最大の期待影響度を得る事が出来た。

※出次数と入次数の高いノード(hub)が多く存在すると期待影響度が高いネットワークかと言われると、hub自体は多くなくてもノード内次数相関を高く保ちつつ期待影響度の高いネットワークは出来る気がする。そういう意味ではhubの数と影響度の関係なんかも気になる。


単語のコミュニティ性に基づいた専門用語の抽出

例えば学会における論文から専門用語の抽出を行う際、論文の題目と概要しかわからないという制約が与えられている事は多く、その場合既存の手法ではあまり良い結果が得られない。そこで、専門用語にコミュニティ性という新しい概念を導入する。

専門用語は少数の専門家コミュニティで頻繁に使われ、一般的な用語は多数コミュニティで広く使われていると仮定し、このようなコミュニティ性を利用して単語の専門性を定量化するICF(Inverse Community Frequency)と、それを用いた単語スコア計算方を提案。

単語-論文-著者からなる3部グラフを構築。共著ネットワークをコミュニティ分割し、全コミュニティ数に対する任意の単語が出現したコミュニティ数r(w_i)を求める。
この値の逆数の対数に定数を乗じたものをICFと定義
ICF(w_i)=(log(\frac{1}{r(w_i)}))^\alpha
単語スコアは以下の式で算出
TF-ICF(w_i)=TF(w_i)*ICF(w_i)

実際にJSAIのデータを利用してその他の手法と比較してみると、提案手法は特定の分野で使われるような専門語に高いスコアがつく傾向が見られた。

※TF-IDFに変わる単語のスコア付与に関しては、去年のCIKMあたりで単語間グラフを作成するようなアプローチであったような記憶がある。アイデアは個人的に面白いと思ったけどちょっと評価が寂しいのがもったいない感じがした。

分散表現を用いたコミュニティにおける単語使用傾向の分析

コミュニティにおけるHomophily(類友)を調査。
TwitterのmentionNWをコミュニティ分割。それぞれのコミュニティ内のプロファイルと投稿で使われる単語を利用する。
コミュニティ間の類似度を表す指標として、ネットワークベースのものと単語ベースのもを用意。
ネットワークベースの類似度は2つのコミュニティ間のリンク数、単語ベースの類似度は2つのコミュニティ間で利用される単語群のがどれだけ似ているかで定義される。

まず、プロファイルからコミュニティをタグ付けすると、同じor近隣高校、同じor近隣大学、趣味の3つに分ける事が出来る。
コミュニティごとに使われ方が違う単語についてみると、[ミート]という単語は、オンゲーコミュニティでは肉、ディズニーコミュニティでは会う事を意味していた。
最後にネットワーク的な類似度と言葉遣い的な類似度の相関を見ると、高校コミュニティではネットワークとしては遠いが、言葉遣いとしては近い、大学では両方近い、趣味ではネットワークは様々だが言葉遣いは遠いという結果が得られた。
以上の事から、Homophilyは属性の近さによって似る場合と趣味があるので友達に成る場合の2種類がある事が示唆される。

JSAI2014行けなかったしいくつか読んでみる-その1-

ソーシャルメディアの情報統合によるエキスパート検索エンジンに関する研究

目的の知識を有したエキスパートを検索する「エキスパート検索問題」に対し、ウェブ上のデータソースを用いた検索基板Social Expert Search Engineを提案。
Web上のデータソースから情報を取得し、その情報を統一されたメタ情報に変換してエキスパート知識データベースに格納。この情報利用してエキスパートの専門性をスコアリングして、ユーザの要求に合うエキスパートを提供する。
このシステムを応用してポートフォリオ生成エンジンを作成。データソースとしてGithubGoogle Playを利用した。
被験者9人の評価により、データソースの不足によるスキルの不一致や提供UIに不満が出た。

※素朴にLinkedInじゃダメなのかなぁと思う部分もあった。それこそLinkedInに成ってしまうが、人間関係をグラフとして持っておくとデータソースの不足を補完できるようになりそう。

医療データ利用におけるプライバシ保護の課題とその解決策の提案

医療においてプライバシ保護が必要になる事例を紹介。データとして利用する価値を残しつつ個人が特定されないよう、現状定められたガイドライン等に関して紹介されている。
医療データの応用先として、医療機関をネットワーク化し、医療情報を共有する取り組みがある。しかし、情報閲覧範囲の拡大により人為的ミスのリスクが高くなるので情報漏洩のリスクが高くなる問題がある。
これらの課題をまとめると「複数医療機関に分散するデータを患者プライバシを保護して共有するシステム設計,プライバシ漏洩リスク評価と低減,適切なアクセスコントロール」となる。
これらの課題を解決するための情報セキュリティ・匿名化技術の有用な利用法について提案する。

匿名化の実社会での利用に向けての技術課題

パーソナルデータに関する検討会として行われた技術検討ワーキングの報告書にそって、匿名化を実際に使うための問題点について述べている。
1.匿名化技術の一つであるk-匿名化を用いた完全な匿名化は不可能である
任意のデータ業者Aがこの技術を用いて匿名化を行っても、その他の業者Bのデータをつきあわせる事で個人が特定できる事がある。一方、すべての業者がすべての情報を匿名化した場合にはデータとしての精度が悪化して利用できなくなる。

2.個別データベースと個別応用による匿名化の可能性
a.疑似ID有無(デモグラ情報など)
b.外部可知/不可知(ID以外の情報がDBに保存されている事が第三者に知られうるかどうか)
それぞれの場合分けによって匿名化の可否も変わる
・疑似ID無+外部不可知
データが公開されても本人特定は極めて困難
・疑似ID有+外部不可知
疑似ID自体をk-匿名化する事が有効
・外部可知+疑似ID無
データと観察日時などから本人特定が可能。データ自体をk-匿名化しても、長期にわたってデータを収集して行くとそれだけで個別性が高まってしまう。
・外部可知+疑似ID有
二つのデータを紐付けしたデータを匿名化するため、データの精度を大幅に落とす必要がありデータの価値は下がる。

3.センシティブ情報
行動履歴、滞在情報、薬剤購入、宗教といった個人によって不都合かどうかが異なる情報。一律な扱いが難しい。

4.k-匿名化の濡れ衣
k-匿名化を用いる事で、ユーザが何らかの属性によってセグメントになったとき、その中のあるユーザが特徴的な行動を行っていると他のユーザとの識別が出来なくなっている状態なので、そのユーザも同じ行動をしていたと見なされる恐れがある。

5.自己情報コントロール
個人情報の利用のされ方について、開示要求に応える事。消去要求があった場合には速やかに削除する事を実現する

※こういった話、一番知らなければならない企業のデータ活用者にあまり届いてないのが現状な感じする。個人のデータはあくまで個人の裁量で扱われるべきである事を企業に浸透させるのはなかなか大変そう。