Comments
Description
Transcript
Small WorldとAverage
Small World と Average-clicks 松尾 豊 東京大学 工学系研究科 [email protected] 概 要 本稿では２つの研究内容について紹介する。ひとつは、Small World 構造を利用した文書からのキーワード抽 出である。Small World とは、ノード がクラスタ化されているにも関わらず、ノード 間の平均パス長が短いグラ フ構造を指す。まず、文書（ WWW9 の論文５７篇）が Small World 構造を備えていることを述べた後、ある語 を取り除くことによって平均パス長が大きく短縮されるような語を取り出す。つまり、世界を小さくしているす るのに貢献している語は、離れたクラスタ（つまり概念）を橋渡ししている語であり、論文の主旨において重要 な語である可能性が高い。 もうひとつのテーマは、Web ページ間の距離の新しい定義である。従来は、Web ページ間の距離はクリッ ク数で測られるのが一般的であった。しかし、あるページに１００個リンクがあるときのリンク先のページへの 距離感と、３個しかリンクがないページにおけるリンク先ページへの距離感では、ユーザにとって後者の方が近 く感じるはずである。ここでは、Average-clicks という新しい Web ページ間の距離の単位を定義し、ユーザの距 離感がより的確に反映されることを示す。 Small World 構造を用いた文書からのキーワード 抽出 1 1.1 Small World とは Small World は、例えば飛行機でとなりに乗り合わせた人が共通の知人を発見し、 「せまい世界ですね」という あれである。S. Milgram が 1960 年代に行った以下の実験から、"six-degree of separation" として有名になった。 米国の大学講師がオマハの住民 160 人をランダムに選び、彼らに「ごく親しい人に転送してもらうことで、最 終的にボストンの株主仲買人までこの手紙を転送して欲しい」と書いた手紙を送付した。160 通の手紙の内、 42 通が仲買人の元に届き、1 通の手紙が届くまで平均 5.5 人が転送に関わったことが分かった。アメリカの 人口は２億人以上であり、数字は直観に反して小さい。 長い間、社会心理学的な考察対象であった Small World は、D. Watts が 1998 年に Nature 誌上で２つの特徴量 により定式化して以来、注目を集めるようになった。２つの特徴量とは、以下である。 Regular p=0 Small world Increasing randomness Random p=1 図 1: regular ring lattice のランダムなつなぎかえ. 1 表 1: Small World 構造を持つ様々なグラフの L,C , [7] (元データは [8]). Film actor Power grid C. elegans L Lrand C Crand 3.65 18.7 2.65 2.99 12.4 2.55 0.79 0.080 0.28 0.00027 0.005 0.05 2396 10.61 4.755 Film actor は、Hollywood の俳優についてのグラフで、2 人の俳優が同じ映画で共演していればリンクが張られる。Power grid は送電網に ついてのグラフで、ノード は発電機、変電所等を表し、リンクは高圧送電線を表す。C. ナプスもしくはギャップ結合でつながれたニューロン間にリンクが張られる。 elegans は、線虫のニューロンのネットワークで、シ L (characteristic path length) : グラフ中のすべてのノード の組についてのパス長の平均。パス長とは、最 短パスの長さである。 C (clustering coecient) : 近傍の cliqueness(派閥度) を表す。ひとつのノードが k 個のノード と隣接してい るとき、この k 個のノード 間に存在するリンク数を k C2 で割ったものを、すべてのノード について平均を とったものである。 Watts によると、Small World は L Lrand (または L Lrand ) かつ C Crand であるようなグラフとして 定義される。ここで、Lrand 、Crand は、同じノード 数、リンク数のランダムグラフにおける L と C である。図 1 に、規則的なグラフから、リンクをランダムにつなぎ変えていくと、途中の段階では、規則的でもランダムでも ないものができる。これが Small World である。 Walsh は、さらに small-worldliness という指標 を考案した。 = (C=L) = (Crand =Lrand) (1) p が 0 から増えていくと、少数のショートカットが L を急激に減らす。これらのショートカットは C にはほとん ど影響をおよぼさない。結果として が急激に大きくなり、グラフは Small World の特徴を持つようになる。さ らに p が 1 に近づくと、つなぎかえが L にほとんど影響を及ぼさなくなり、C と が低下する。こうして、再び Small Worl d の特徴を失うことになる。表 1 に Small World 構造を持つ様々なグラフの例と各特徴量の値を示す。 Small World がなぜ、自然界や人工物に存在するかは、以下の３つの要素から考えることができる。 1.2 信号の伝達効率：L が小さいことは情報（信号、電力、etc ）を伝搬する上で好ましい。 コスト最小：なるべくリンクを張る距離は短い方が好ましい。送電線、ニューロン、人間関係とも、近くの リンクを維持する方が簡単である。 ロバストネス：ひとつのノード やリンクが失われたとき、構造が大きく崩れない方が望ましい。 文書からの語の共起グラフ さて、文書の語の共起グラフは以下のように構成することができる。 stop word1 を取り除く。stemming2 を行う。n-gram により熟語を抽出する。 頻出数の上位語（熟語も含む）をノード として決められた数だけ選ぶ。 頻出語の共起（一文中での共起）の Jaccard 係数3 が決められた値を越えれば、リンクを張る。 1 \a","the","that" などのあらかじめ決められた不要語。ここでは、Salton の SMART System のリストを用いた。 2 語幹の形を得る処理。"1 1 1ing","1 1 1ed", 三単元の s などを取り除く。 3 (両方の語を含む文の数)=(少なくとも一方の語を含む文の数). 2 graph connect world node small document term structure important make length small world topology important term contribution path cluster characteristics average edge pair path length short find characteristic path length measure coefficient clustering coefficient sentence Watts 図 2: Small World の論文の Small World WWW9 の論文 57 篇 [1] について、得られたグラフが Small World であるかどうかを調べた結果を図 2 に示す。 は最小でも 4.2 、平均 15.3 と大きく、確かに Small World と言えそうである。この理由は次のように考えること ができる。論文の著者は、ひとつの概念を説明する際、いくつかの語を同時に用いて説明する。したがって、こ れらの語はよく共起することになり、クラスタを形成する。さらに、概念同士の関係を記述する際に、概念間のリ ンクすなわちショートカットが形成されることになる。 図 2 に Small World の論文 [5] から得た共起グラフを示す。 表 2: WWW9 の論文 57 篇についての統計データ Max. Ave. Min. L Lrand C Crand 4.99 5.36 8.13 3.58 | 2.94 0.38 0.33 0.31 0.012 | 0.027 22.81 15.31 4.20 論文中に 3 回以上出現する語をノードとした。最大連結サブグラフ（平均 89%のノードをカバーする）だけに着目した。最大連結サブグラフ がカバーするノードが 50%を下回る論文 3 篇については除外している。平均ケースの Lrand と Crand については論文により n と k が異な るため、表示していない。平均では、 n = 275, k = 5:04 であった。 3 表 4: Small World 論文の CBv 上位語. 表 3: Small World 論文の頻出語. Term graph small world term small world node paper length document edge 1.3 KeyWorld: Frequency 39 37 37 34 30 29 21 21 19 19 Term small term important term contribution node make cluster graph coecient average CBv 3.05 2.80 1.93 1.64 1.00 0.82 0.57 0.54 0.52 0.50 Frequency 37 34 7 6 29 6 15 39 8 8 キーワード の抽出法 ある語を取り除くことにより、L がどのくらい変化するかで、その語が世界を Small World にするのにどのく らい貢献しているかを計ることができる。具体的な計算については省略するが、あるノード v を取り除いたとき の Lv ともとの L の差を contribution として定義する。 CBv = Lv 0 L (2) CBv の上位の語をキーワード として抽出するシステムを KeyWorld と呼ぶ。表 3, 4w に Small World の論 文の頻出語と KeyWorld の出力の上位語を示す。頻出語には、論文の要素的な概念を表すような語（ "graph", \term", \node" など）が並んでいるのに対し、KeyWorld で得られた語は論文の重要な概念（ \important term", \contribution", \cluster" など）が得られており、これらの語がいくつかの話題をブリッジするような語になって いることが分かる。 KeyWorld の上位語には重要な語が多く含まれているものの、"make" などのゴミも含まれる場合が多い。その ため、実際にキーワード 抽出のアルゴリズムとして用いるときには、idf (inverse document frequency)4 と併せて 語 v の重みを CBv 2 idfv とするとよい結果が得られる 5 。 評価実験の結果を表 6 に示す。20 篇の論文に対し、著者に各手法の出力語をシャッフルして提示し、キーワード であるか否かの判定をしてもらうことにより評価を行った。precision は各手法が出した結果の中にキーワード と 認定された語がどのくらい含まれるか、coverage は著者に５つ（以上）選んでもらった必要キーワード のうちい くつが含まれているかを計算した。その結果、KeyWorld 単独では、ゴミが含まれてしまうために tf とほとんど 変わらない程度の評価しか出ない（しかしながら、数字に現われない結果の面白さはある）が、KeyWorld + idf により、これらのゴミを取り除くと tdf よりもかなりよい結果となる。 Average-click: Web ページ間の新しい距離の定義 2 Web ページは、各ページがリンクでつながれた有向グラフと考えることができる。実際に Web は Small World であり、Web 上の任意の 2 ページ間の平均パスは 19 クリックであるという報告もされている。ここで述べる Web ページ間の新しい距離 average-clicks[4] は、リンクの価値を Small World の考え方を用いて計れないかと試みて 失敗した際に副次的に生まれたものである。 4 logN=n で表される。ただし、N はコーパス中の文書数、nv は語 4 v が含まれる文書の数。 表 5: Small World 論文の CBv Term small world shortest path short cuts contractor rare co-occurrence sentence path length important term document CBv 2 idf 上位語 Frequency 37 34 7 6 29 6 15 39 8 8 2.58 1.76 0.94 0.90 0.80 0.73 0.63 0.50 0.48 0.15 表 6: Precision と Coverage precision coverage tf 0.53 0.48 KeyWorld 0.49 0.50 tdf 0.55 0.62 KeyWorld+idf 0.71 0.68 Web ページには多くのリンクがあるページ (Yahoo!トップページは現在 180 以上) もあれば、数個のリンクしか ないページもある。その場合、ユーザの１クリックの距離感は同じであろうか？Web 上からのコミュニティ発見 などの研究が行われているが、すべてのリンクの長さを等しく１と考えてよいのだろうか？ 2.1 ランダムサーファーモデル 本手法で元となるのは、ランダムサーファーモデルである。 ページ p が OutDegree(p) 個のリンクを持つとき、ランダムサーファーは =OutDegree(p) の確率で各リン クをクリックし、1 の確率で任意のページにジャンプする。 0 ランダムサーファーモデルは、Google5 で採用されている PageRank[3] というアルゴリズムにおいて、Web ペー ジのランキングの目的で用いられている。ここでは、このランダムサーファーモデルを援用し、ページの距離の 定義に用いる。 定義 2.1 ページ p におけるひとつのリンクの長さを以下で定義する。 0 logn (=OutDegree(p)) (3) 以下では、簡単のため = 1 とする。また log の底を 7 とする。平均的なページはページ内に 7 つのリンクを持 つという報告がされているためである [2] 。 （なお、最近の調査では、平均的なページは 1 つの外部リンクと 4 つ の内部リンクを持つという報告もされている [6] 。）上で定義された距離の単位を average-click と呼ぶことにする。 直観的には、あるページから他のページにいくのにいくつの「普通のクリック」が必要かを計るものである。リ 5 検索エンジンとして高い性能を持つ。http://www.google.com/ 5 1 -log7 -=1.0 -log7 C 7 B From A to C, 1.56 average-click, 2 clicks. 1 -=0.56 3 1.0 A 0.56 D E F 0 0.36 From A to D, 0.92 average-click, 2 clicks. 図 3: Average-clicks と従来のクリック数 表 7: 著者のホームページからの距離 To 松村くん（石塚研） Yahoo! 人工知能学会 IJCAI リーグ公式ページ 大相撲協会 J average-clicks 1.62 3.02 4.69 5.39 4.02 9.08 clicks 2 3 3 5 4 6 ンク数が多いページの１クリックは「普通のクリック」では１以上に相当し、リンク数が少ないページの１クリッ クは「普通のクリック」では１よりも小さくなる。 ２つのページ間の距離はクリック数と同様、最短パスの長さで決まる。図 3 に、従来のクリック数と average-click の関係を示す。ページ A は 3 つのリンクを持つため、各リンクの長さは log7 (1=3) 0:56 average-click である。 ページ B は 7 つのリンクを持つため、1 average-click であり、ページ A から C まで 1.56 average-click である。 A から D までは、従来のクリック数では 2 クリック (A → B → D) だが、0.92 average-click(A → E → F → D) で ある。 このようなモデルを用いることで、Yahoo!などのリンク集を経由するパスの長さは長く評価される。直観的に は、たとえ同じクリック数であったとしても、Yahoo!のトップページを経由するパスよりも、知り合いのページ を辿るパスの方が短く感じるであろう。このモデルは、その感覚にマッチしている。 0 6 表 8: 被験者の回答との相関係数 Participant 1 2 3 4 5 Clicks 0.524 0.696 0.517 0.325 0.471 図 4: 被験者１の回答と距離（ average-click ）の散布図 2.2 Average-clicks 0.836 0.715 0.699 0.804 0.685 図 5: 被験者１の回答と距離（ クリック数）の散布図 評価 例えば、筆者のホームページから、各サイトへの距離は表 7 のようになる。ユーザの距離感と average-click が 適合しているかどうか確かめるため、アンケートによる評価実験を行った。被験者のホームページから数クリック の距離にあるページを取ってきて、URL を被験者に提示し、それをどのくらい身近に感じるか１から５の５段階 で評価してもらった。ある被験者の回答とクリック数／ average-click の散布図を図 4, 5 に示す。被験者の回答と average-click で計った距離はかなり相関があるのに対し、従来のクリック数ではあまり相関はみられない。５人 の被験者に対しての、回答と従来のクリック数／ average-click の相関係数を表 8 に示す。サンプル数が少ないも のの、average-click はユーザの距離感をより適切に反映しているといえそうである。 2.3 定理 Average-click を用いると、以下のような定理も成り立ち、Web の crawler を走らせるときに便利である。 定理 2.1 ページ a から探索をはじめ 、ページ a に近い方から (a を含めて)n 個ページを訪問すれば 、少なくとも半径 log7 2=(n + 1)(average-click) の範囲のページは全て訪問したことになる。 0 7 3 まとめ ここに述べた２つのテーマを簡単に述べると、文書の概念構造から重要な語を見つける、Web ページ上のユー ザの距離感を適切に計る（ことによりユーザが意識していないリンクの価値を計る）という研究である。最近、私 は「情報の価値とは？」と考えており、いかにユーザに価値の高い情報を提示するかというテーマを持って取り組 んでいる。 ごく当たり前のことだが、情報の価値は現在持っている情報との対比により決まる。しかしながら、従来の AI や知識処理ではこれが忘れられている気がする。知識をコンピュータに載せてできることは限られている。コン ピュータの外には無限の実世界があり、モデルから捨象されていることのなかに、モデル精緻化・新しいモデルへ の質的な改善のための重要な情報が隠されている。エージェントにとって有用な情報とは、エージェント内にあ るモデルと異なる外界の振る舞いであり、それにいかにして気づくかが、すなわち、いかに価値のある情報を見 つけていくかが重要なのではないだろうか。 参考文献 [1] 9th international world wide web conference. http://www9.org/. [2] K. Bharat and A. Broder. A technique for measuring the relative size and overlap of public web search engines. In Proc. 7th WWW Conf., 1998. [3] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Proc. 7th WWW Conf., 1998. [4] Yutaka Matsuo, Yukio Ohsawa, and Mitsuru Ishizuka. Average-click: A new denition of distance on the world wide web. In Submitting to WI-2001, 2001. [5] Yutaka Matsuo, Yukio Ohsawa, and Mitsuru Ishizuka. A document as a small world. In Proc. SCI-2001, 2001. to appear. [6] B. Murray and A. Moore. Sizing the internet (a white paper). White paper, Cyveillance, Inc., 2000. (http://www.cyveillance.com). [7] T. Walsh. Search in a small world. In Proc. IJCAI-99, pp. 1172{1177, 1999. [8] D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, Vol. 393, , 1998. 8