« 2011年6月 | トップページ | 2011年11月 »

2011年7月

国際会議WWW2010論文感想 その9(社会ネットワーク,エッジ重み推定)

Rongjing Xiang, Jennifer Neville, Monica Rogati: Modeling Relationship Strength in Online Social Networks, Proc. WWW2010, 2010.
ソーシャルネットワーク,社会ネットワーク,エッジ重み推定
http://portal.acm.org/citation.cfm?id=1772790

ソーシャルネットワークにおいて,プロフィールの類似性と,ユーザ間のインタラクション情報に基づき,エッジの重み(関係性の強さ)を推定している.重みは連続値で推定される.推定のために教師なし学習モデルを提案している.具体的には,つながりの強さを表す潜在変数モデルを考案し,変数推定のために座標上昇最適化法(coordinate ascent optimization procedure)を提案している.

本論文では,提案手法は数式で示されており,それの言語的表現は難しいため,このまとめでも論文中の式を参照しながら要約する.根本的な考えとしては,つながりが強いほど,より多くのインタラクションを発生させるというものである.図1に示されるように,ユーザiとユーザj間の関係は,プロフィールx_iとプロフィールx_jが,潜在変数Z_ijに影響し,潜在変数(モデル)Z_ijがユーザi,j間のインタラクションy1_ij, y2_ij, ..., ym_ijを発生させる.mはインタラクションの個数である.

xが与えられたときにZが導き出され,その結果yが導き出される確率は式(1)のように表される.潜在モデルZが与えられたときに発生するインタラクションの起こる確率(P(Z|X))とxが与えられたときに潜在モデルZが導き出される確率(P(Y|Z))の積で与えられる.P(Y|Z)は,ユーザプロフィールx_i, x_j間の類似度に重みを付けたものを引数としたガウス分布の確率密度関数で表される.インタラクションymは,バイナリ変数である.

さらに図2に示されるように,各インタラクションtに補助変数ベクトルatを導入している.これは,元々投稿回数が多いユーザ(インタラクションが投稿したか否かであれば)は,出力yも大きくなるような工夫である.zとatが与えられたときのytの確率をモデル化するためにロジスティック関数を用いている(式(3))
.ここで,重みθはatへの重みであるが,これを学習で推定する(学習は,w, θ, Zを同時に推定するものである).(7)式により,ユーザi, j間のつながりの強さを表す.Dは歯科位置が決まっており,これを最大化するw, θを求める.

推定では,結合尤度(P(y, z, w, θ |x))を最大化するパラメータw, θ, zを座標上昇最適化法にて行う.座標上昇最適化法は,収束するまで,パラメータw, θ, zを更新する.更新は,Newton-Raphson法を用いる.各更新パラメータの偏微分を求め,それぞれが零になる点が推定されるパラメータである.

評価実験では,まずLinkedInを対象にしている.LinkedInのユーザ100人をシードノードとしてランダムに選び,2リンク以内の全ての近傍を抽出した.その中のペアを対象に実験している.プロフィールは表2にあるように,iとjが同じ学校に通っていたかどうかなどである.インタラクションは,iとjがコネクションを張っているか否かや,iがjのために推薦を行ったかどうかなどである.推定は,同じ仕事をしているか否か,同じ職能領域で働いているか否か,同じ地域に住んでいるか否かを,6つの簡単な推定手法と比較している.また,第三者がユーザiとjのプロフィールを両方とも見たか否かを評価基準として,6つの簡単な推定手法と比較している.その結果,提案手法が最も良いことを示している.

また,実験は,他のソーシャルネットワークとしてFacebookも対象として,Purdue大学の学生5人をシードノードとして実験をし,良い結果を示している.

(総評)
ユーザプロファイルとインタラクションを利用して,ソーシャルネットワークのエッジの重みを推定するというアイディアには新規性があると思われる.また,ユーザ間の社会的つながりの強さに関連する潜在変数を仮定し,プロファイル間の重みと,上記潜在変数,ユーザ間のインタラクションの関係をモデル化するという手法にも新規性があると考えられる.インタラクションに対する補助変数ベクトルも工夫の一つであるが,これがどれだけ寄与しているのかは明らかではない.評価もLinkedInとFacebookの二種類を用いてる点も評価できる.

|

国際会議WWW2010論文感想その8 (SNS,プライバシー,機械学習,UI)

国際会議WWW2010論文感想その8 (SNS,プライバシー,機械学習,UI)

Lujun Fang, Kristen LeFevre : Privacy Wizards for Social Networking Sites, Proc. WWW'10, 2010.
ソーシャルネットワーキングサービス(SNS),プライバシー,機械学習,ヒューマンインタフェース
http://portal.acm.org/citation.cfm?id=1772727

SNSにおけるプライバシー設定を,半自動で設定してくれるプライバシーウィザード(プライバシーを設定するインタフェース)を提案している.

SNSにはプロフィールを記述するのに,属性ー属性値のデータがある(職業,性別,年齢,政治的信条,宗教的信条,・・・).これをいちいち友人ごとに,公開/非公開を設定するのは労力がかかる.これを半自動で設定してくれるインタフェースを提案している.具体的には,基本的には従来のSNSサービスでのプライバシー設定のように,友人ごとに,そして属性ごとに個別に設定していくが,いつ止めても問題がない.その後は,自動で設定してくれる.そして自動で設定してくれるルールを分かりやすい形で表示することにしている.

自動設定は,機械学習に基づいている.その学習では,友人を特徴ベクトルで表す.特徴ベクトルは,2種類存在する.一つはコミュニティで,コミュニティG1に属すれば1,そうでなければ0である.もう一つは,ユーザプロフィール(属性ー属性値のデータ)である.個別のプロフィール(一組の属性ー属性値)ごとに,判別器を学習する.判別器は,決定木によって学習している.

コミュニティは,あらかじめユーザを,ユーザプロフィール(属性ー属性値のデータ)を特徴ベクトルとして,Newmanのモジュール性に基づく階層型クラスタリングで抽出している.

実験は,Facebookを対象に行っている.評価では,判別器の性能を評価している.評価対象は,デフォルト設定との比較である.デフォルト設定とは,ユーザプロフィールの各属性に対して「全ての人」,「友人とネットワーク内の人」,「友人の友人」,「友人のみ」の4択から選択させて適用するものである.実験結果としては,提案の判別器の方が優れていることを示している.

<総評>
論文としてはかなり未熟な印象である.機械学習の論文としては,決定木を用いただけであり(コミュニティ抽出は行っているが),しかも評価実験での比較手法が一つの手動の公開ルールに基づくものだけであり,提案手法が考えられる様々な手法の中で最も優れているのかは判定できない.コミュニティ抽出との組み合わせに工夫があるとは言えるが,コミュニティ抽出はユーザプロフィールの属性ー属性値に基づいており,公開/非公開を判別する決定木の学習でももう1回ユーザプロフィールの属性ー属性値(とコミュニティ抽出結果)を用いており,効率の悪さを感じる.

ヒューマンインタフェースの論文としては,ユーザ経験に関する実験が全くない.ユーザは学習データの入力で疲れなかったのか?,予測結果に満足したのか?,抽出ルールである決定木を見てとった行動は?と言ったことが全く評価されていない.

機械学習の論文としても,ヒューマンインタフェースの論文としても中途半端.しかし,これらを組み合わせたところが,うまいところである.

|

« 2011年6月 | トップページ | 2011年11月 »