« 2010年12月 | トップページ | 2011年3月 »

2011年1月

匿名?実名?あなたはどっち?Twitterの落とし穴.

慶応大の折田明子氏が,日本ソフトウェア科学会 ネットワークが創発する知能研究会 JWEIN10の招待講演で触れられておられましたが,ネットの匿名性と到達可能性に関係する問題がちらほらと起こっているようです.

2011年1月19日付,朝日新聞の夕刊でその記事がありました.ホテルに有名人が来客したというつぶやきを従業員がTwitterにしたことから,ネット上で騒然となり,そのつぶやきをした従業員の個人情報が特定され,暴露されたというものです.その従業員はTwitterは匿名であったそうですが,別の交流サイトでは実名であったことから発覚したそうです.

それらのアカウントの間には直接のリンクがあったかなかったのかまでは書いていませんが,たとえなかったとしても,アカウント名が同一であるとか,類推可能であるとか,過去の記事から居住地域や勤め先が分かるとかで,本人が思っている以上に,個人に到達可能なものです.

40歳前後のユーザは実名の人も多いのですが,若者の多くは匿名が多いように思います.ネットでのプライバシー意識が高いのでしょうか?それとも初等教育の効果でしょうか?しかし,彼らの一部には特定可能性についてはあまり考えていない人もいるのかもしれません.

ネット上で絶対に特定不可能にするのが安全な使い方ですが,実はそれではおいしかったお店の紹介もできませんし,朝目撃した出来事の感想も述べることができず,仮想世界の住人としてしか振る舞うことができません.

ネットの面白みを享受しつつ,プライバシーを保つ.そんな相反する命題をバランスよく達成する使い方を模索しないといけないのかもしれません.

■折田明子氏HP
http://www.ako-lab.net/

■日本ソフトウェア科学会 ネットワークが創発する知能研究会 JWEIN10
http://www.ai.sanken.osaka-u.ac.jp/ndei/index.php?cmd=read&page=jwein_summer_2010

|

IBM 人工知能「ワトソン」,クイズ王と対戦

久々にワクワクするニュースが飛び出しました.IBMが開発した人工知能「ワトソン」(Watson)が,アメリカの人気クイズ番組のクイズ王と対戦するというのです.(個人的には「人工知能」という言葉は使いたくありませんでしたが,マスメディアの報道に倣ってみました.IBMのプレスリリースでは,「コンピュータシステム」と言っています.)

IBMは,1996年人間のチェスの王者を負かす人工知能ディープ・ブルー (Deep Blue) を開発し,世間を驚かせましたが,今度はクイズだそうです.

ちょっとコンピュータサイエンスをかじったことがある方なら分かると思いますが,チェスとクイズとでは,全く難しさが違います.チェスは,いわゆるトイ・プロブレム(Toy problem: 限られた世界で限られたルールに支配された問題)で,探索の幅が広くなりと深さが深くなりさえすれば,未来における評価関数の出力結果の最大値が得られる,パスを選択することができます.(探索とは,未来にどういう手を打つか(対戦相手の手も含めて)を試してみることを意味します.)

しかし,クイズになると,自然言語を理解する必要があります.自然言語は,例外の塊ですので,いまだコンピュータは完全に理解することができません.新語も続々出てきますし,世の中にある常識すべてを機械可読な因果関係で結ぶことも不可能です.

映画の脚本や百科事典から知識を組み込んだと言いますが,それだけでどれほど質問応答に答えることができるのでしょう?

私の予想は「ワトソン」の負けですが,ぜひ予想をひっくり返す結果になって欲しいものです.

■プレスリリース IBMのコンピューター・システム「ワトソン」がジョパディ!に挑戦
http://www-06.ibm.com/jp/press/2010/12/1702.html

|

異なるリスト間の順位相関係数

異なるリスト間の順位相関係数

2つのランキングリストの相関を測る指標としては,ケンドールの順位相関係数(Kendall tau rank correlation coefficient)が有名です.

Wikipediaの説明
http://ja.wikipedia.org/wiki/%E3%82%B1%E3%83%B3%E3%83%89%E3%83%BC%E3%83%AB%E3%81%AE%E9%A0%86%E4%BD%8D%E7%9B%B8%E9%96%A2%E4%BF%82%E6%95%B0

しかし,Kendallの順位相関係数は,2つのリストの構成要素が同じであることを前提としております.しかし,情報検索や情報推薦などの順位付けのでは,全てのアイテムを対象とするとリストが大きすぎて現実的でない場合があります.そこで,膨大な長さを持つリストから上位k個のみを使って相関を求める方法として,Faginら(IBM Almaden Research Center)による一般化された順位相関係数があります.

この方法では,二つのリストR1, R2から取り出した構成要素,r1, r2に対し,
(1) r1が1つのリストのみに存在し,r2が他方のリストのみに存在する
(2) r1が片方のリストにおいてr2より高い順位であるが,他方のリストではr2のみ存在する
(3) r1, r2が両方のリストに存在するが,順位の順序が逆である
という事象をランキングが異なるものとして扱うことで,上位k個で打ち切ることの一般化を試みています.

詳しくは,以下の論文をご参照ください.

Ronald Fagin, Ravi Kumar, D. Sivakumar: Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, ISBN:0-89871-538-5, 2003.
http://portal.acm.org/citation.cfm?id=644113

|

国際会議WWW2010論文感想その1

Haewoon Kwak, Changhyun Lee, Hosung Park, Sue Moon: What is Twitter, a social network or a news media?, Proc. of WWW'10, 2010.
ソーシャルネットワーク, Twitter, 複雑ネットワーク,べき則,スモールワールド,情報伝搬

Twitterの社会ネットワークとしての特徴,コンテンツであるツイートの特徴,話題の伝搬に関する特徴,ユーザのランキングなどを分析調査した研究である.これだけ,網羅的に詳細に調べた研究としては,本研究が初めてのものである.ツイッターの特徴を知るには,本研究が最も基本的な調査結果として利用できるであろう.

データはTwitterAPIを用いて3週間分集めている.ユーザは,ある一人のユーザから幅優先探索で41,700,00ユーザ分収集している.また,Twitter Search APIを用いて5分ごとに流行トピック(右サイドバーに出るやつ)を4262個取得している.また,それに対するツイートも収集している.

<複雑ネットワークとしての特徴>
・有向ネットワークの基本分析
まず,有向ネットワークの基本特性を分析している.図1は,フォローしている(Followings)とフォローされている(Followers)の数の相補累積分布関数(complementary cumulative distribution function, CCDF)を示している.結果は,100000Followings/Followersまでは,べき則に従うことを示している.また,100000人以上のFollowersのいる人は,べき則分布の予想よりも多くのフォロワーがいることを示している.有名人がツイッターをしているためであろう.これは,他のソーシャルネットワークでは報告されておらず,興味深い報告である.

・フォロワーの数とツイートの数の関係
多くのフォロワーを獲得するには,多くツイートする必要があると考えられる.図2はその関係を示している.フォロワー数が100までは急激に伸びているが,100を超えると横ばいになる.1000を超えるとほとんどツイートをしない人や非常に多くのツイートをする人など分散する.これも,有名人の影響であろう.

・相互関係(双方向リンク)
Twitterでは相互関係の度合いは低く,全ユーザの組の22.1%しかお互いにフォローし合っていないことを報告している.Twitterはソーシャルネットワークサイトというよりもむしろ情報源である.

・最短パス
ユーザ間の最短パスを調査.中央値と最頻値は4.平均パス長は4.12.90パーセンタイル(低い方から並べて90%のところ)は4.8.Twitterのネットワークに対し,平均パス長が4.12というのは非常に短い.単方向リンクの影響か?

・Homophily
Homophilyとは,似ている人々の間では似ていない人々の間よりも高い確率でコンタクトが起こること.フォローし合っているユーザ間の時差について調査.ユーザ数が2000人以下では,相互リンク数が多くなると時間差も増加.

<ユーザのランキング>
ユーザのランキングをフォロワー数上位ユーザ,PageRank,リツイートの合計数でランキングする.フォロワー数上位20ユーザとPageRank上位20位は,リストがほぼ一致する.しかし,リツイートの合計数上位20ユーザは,前者2つとはリストがあまり一致しない.リツイートが多いのはニュース機関となっている.

<流行トピック>
Twitterで取得した流行トピックとGoogle Trendでの流行トピックを比較している.Googleにおいては毎日平均95%が新しい流行トピックであるが,Twitterには72%しかない.Twitter内でのユーザ間のインタラクションが流行トピックが持続する原因となっているかもしれない.同じく,CNNでの流行トピックも取得.すると,多くのものがCNNで発生した流行トピックがTwitterに移っているが,スポーツや事故などは逆のものもある.

流行トピックについて言及したツイートを,singleton, リプライ,mention,リツイートに分けて分析したところ,流行トピックによりさまざまであった.

各流行トピックごとに,新規にツイートしたユーザ数を調べたところ,"apple (computer)"は,徐々にユーザ数が増えているが,"#iranelection"のようなハッシュタグでは,急に伸びたのち,ユーザ数はほとんど増えない.

<リツイートの分析>
フォロワー数とリツイートを受信したユーザ数との関係を調べている.その結果,フォロワー数が1000人までは受信者数の平均は,フォロワー数の影響を受けていない.
一度,リツイートが始まると,そのユーザのフォロワー数には寄らず,ある一定数のユーザに届く傾向があることを示している.

リツイート木を作成してみると,多くのつながりが1パスか2パスとなっている.
リツイートの半分は1時か担いに行われ,75%が1日以内にリツイートされている.

|

ACM RecSys2010 勉強会のノート(セッション9)

国際会議ACM Recommender Systems 2010 (RecSys 2010)の勉強会のノートです.論文紹介は,論文タイトル下の発表者がされ,下記は私が書いたノートです.今回でこの勉強会シリーズも終了です.紹介するのは,「Friends and lovers」のセッションです.みなさん,友達・恋人の関係には興味があるのでしょうか.4件中すべての論文が紹介されました.注目すべきは,9-3の論文でしょう.Twitterでの友人推薦です.ユーザのfolloweesのツイートでプロファイリングした場合と,followersのツイートでプロファイリングを比較しているのは価値があるでしょう.

Session 9: Friends and lovers
9-1 Transitive Node Similarity for Link Prediction in Social Networks with Positive and Negative Links
  高岡幸一(甲南大)
ソーシャルネットワーク
キーワードを入れてからそのキーワードに関連するユーザを推薦

経路の長さ
ノードとその経路のとの間の類似度
ポジティブ・ネガティブな関係(ポジティブは友達関係・ネガティブは敵関係)

基本ノード類似度,v1とv4の関係をみるのに,経路にあるv1とv2及び,v2とv4の類似度を計算している.

拡張ノード類似度を用いて推薦

9-2
友人推薦
個人プロファイル:電話帳
SM(ショートメッセージ)の余剰スペースに電話帳(スケッチ)を埋め込む
ユーザA, Bの間に友人関係がなくても,AとBと関係のあるCがA-Bの関係性が強いと考えれば,AにBを推薦

Jaccard係数を使ってリンク予測(共通の友人が多いほど友人になりやすい)

スケッチの直接交換は安全ではない.スケッチは暗号化.暗号化した情報同士を足し算することができる.なので,Jaccard係数を算出可能.

9-3 Recommending Twitter Users to Follow Using Content and Collaborative Filtering Approaches
  田村航弥(同志社大)
Twitterにおいてユーザにフォローすべきユーザを推薦
コンテンツベースと協調フィルタリングからユーザにフォローすべきユーザを推薦
 ユーザが与えたクエリによって,それに関連するユーザをランキング

ユーザのプロファイリング
(CBF)
 ターゲットユーザの直近の100ツイート
 ターゲットユーザのfollowers followeesの直近の100ツイート
(CF)
 ターゲットユーザのfollowers followees

CBF
ユーザ自身のツイートでプロファイリング
ユーザのfolloweesのツイートでプロファイリング
ユーザのfollowersのツイートでプロファイリング
上記の組み合わせ

CF
ユーザのfolloweesでプロファイル
ユーザのfollowersでプロファイル
上記の両方

オフライン
筆者の周りのユーザからリンクをたどって1000ユーザをテストセット
オンライン
30名の被験者に対して,推薦したユーザを実際にフォローしたいかどうか

FolloweesとFollowersには差がなかった.

9-4 RECON: A Reciprocal Recommender for Online‐Dating
  小林加織里(兵庫県立大)
互いに意気投合しそうな人間を推薦する
出会い系サイトをドメインにしている

出会い系サイトでの履歴からユーザ嗜好を取得
 自分からコンタクトを取った相手の特性
 自分がコンタクトに応じた相手の特性
ユーザ間の相性スコアを計算
自分の嗜好と相手の特性との一致度合い
最後に推薦

特性:性別,年齢,体型
自分が取った相手の特性を記録

xから見たyとの相性
yから見たxとの相性
を求め,相互スコアを上記の調和平均を取る.
これで推薦.

この研究でおもしろいのは,互いからの推薦スコアの調和平均を取ってそれをスコアにしていることか?調和平均をとることによって相互のスコアに差があるものはスコアを下げる工夫をしているのであろう.
ただ,技術的には,それだけ?という気もする.

===

ACM RecSys2010 勉強会ノート目次

http://e-biz.cocolog-nifty.com/blog/2010/12/acm-recsys201-1.html

ACM RecSys2010 勉強会 公式HP
http://qwik.jp/recsys-study/

ACM RecSys2010 公式HP
http://recsys.acm.org/2010/

 


|

ACM RecSys2010 勉強会のノート(セッション8)

国際会議ACM Recommender Systems 2010 (RecSys 2010)の勉強会のノートです.論文紹介は,論文タイトル下の発表者がされ,下記は私が書いたノートです.今回紹介するのは,「Recommending non‐standard items」のセッションです.non‐standard itemsとなっていますが,stanndard itemsは映画でそれ以外という感じでしょうか...8-1は最適化問題の論文です.推薦システムの一つの研究分野と言って良いと思います.8-2は,新規性がよく分かりませんでした.

Session 8: Recommending non‐standard items
8-1 Breaking out of the Box of Recommendations: From Items to Packages
  志甫谷匠(兵庫県立大)
予算を入れれば,Item recommender からアイテム(観光地)を推薦してもらい,それから旅行プランを作成して,それを推薦してくれる.
2近似アルゴリズムを改良.
ナップザック問題の制約付きの場合を扱っている
例えば
 観光地3つ以内
 半径10km以内
 2つ以上講演は含めない

制約を満たしつつ,最適なパッケージを作る.
最適とは何?

適用アルゴリズム
MaxValBound:予算内の上限値を決定する
InsOpt-CR:???
Greedy-CR-Topk:???

データセット
・Movielens
 映画の上映時間をコストとして扱う
 500分以内で映画のパッケージを作る
・TripAdvisor アメリカの10大都市のPOOIに対する評価データ
 1393地点のPOIの評価
 評価の値をコスト
 予算は

パッケージの推薦の質の評価(他のユーザが付けたratingの平均)

8-2 Automatically Building Research Reading Lists
  王元元(兵庫県立大)
ユーザに合う文献リストを自動生成
協調フィルタリング,内容に基づくフィルタリング,グラフランキングなどを適切に組み合わせる

混合アルゴリズム
CF->CBF CBF->CF CF + CBF
これを基本として,各アルゴリズムの中に何種類かあり,170種のアルゴリズムを比較

HITSが他のアルゴリズムより良い
グラフランキングも個人適用した推薦アルゴリズム?

19名の被験者で実験 5-10本
数々のハイブリッド手法と比較して新規性があるのかよく分からなかった.

===

ACM RecSys2010 勉強会ノート目次

http://e-biz.cocolog-nifty.com/blog/2010/12/acm-recsys201-1.html

ACM RecSys2010 勉強会 公式HP
http://qwik.jp/recsys-study/

ACM RecSys2010 公式HP
http://recsys.acm.org/2010/

 

|

ACM RecSys2010 勉強会のノート(セッション7)

国際会議ACM Recommender Systems 2010 (RecSys 2010)の勉強会のノートです.論文紹介は,論文タイトル下の発表者がされ,下記は私が書いたノートです.今回紹介するのは,「Recommending in social networks」のセッションです.今,一番ホットと言って良いテーマだと思います.

Session 7: Recommending in social networks
7-1 Interactive Recommendations in Social Endorsement Networks
  寺田健太郎(立命大)
ソーシャルネットワーク
ソーシャルネットワーク上でオブジェクトを推薦しているサービスが多い
上記のためのサーチエンジンを開発

ネットワーク内で人気のあるグループを抽出し,グループのタグをつけて,インデックスを付ける.
ユーザはクエリを投げて,上記インデックスと比較.

人気のあるマイニング手法(相関ルール)でグループを抽出
グループのタグは???
フィルタリングではタグが同じユーザを削除

グループと人,論文:両方ありえる

7-3 Who is Talking about What: Social Map‐based Recommendation for Content‐Centric Social Websites   
  中島伸介(京産大)
Social Web サイトのコンテンツをユーザの興味に応じて情報推薦する
 新しいユーザに対するコールドスタート問題
 推薦アルゴリズムが複雑なゆえに推薦結果への根拠が分からない問題
Social Mapに基づいた推薦システムを開発
Social Mapとは,IBM社内で開発された手法,ブログの内容をマップとして表示
潜在的なコミュニティを提示
システムはpopularな7つのコミュニティを表示
popularなブログエントリとactiveなブロガーを表示してくれる
その特定のブロガーが各コミュニティでどういうキーワードで貢献しているのかを色づけで表示してくれる.
SocialMapの構築方法
 community extractoin:LDA利用.今点t布潜在的トピックを抽出し,これに基づいたクラスタリング
 コンテンツや人のauthority度を算出

SocialMapに基づいてインタラクティブに情報探索していける点が利点


===

ACM RecSys2010 勉強会ノート目次

http://e-biz.cocolog-nifty.com/blog/2010/12/acm-recsys201-1.html

ACM RecSys2010 勉強会 公式HP
http://qwik.jp/recsys-study/

ACM RecSys2010 公式HP
http://recsys.acm.org/2010/

 

|

« 2010年12月 | トップページ | 2011年3月 »