Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列(推移行列、遷移行列) 固有値と固有ベクトル W大学

Slides:



Advertisements
Similar presentations
シミュレーション演習 G. 総合演習 ( Mathematica 演 習) システム創成情報工学科 テキスト作成: 藤尾 光彦 講義担当: 尾下 真樹.
Advertisements

データベースと情報検索 情報検索 ( 5 ) 検索エンジンの仕組み 教員 岩村 雅一. 日程(情報検索:担当 岩村)  12/9 検索エンジンを使ってみる  12/16 メディア検索を使ってみる  12/25 ウェブアプリケーションを 使ってみる  1/9 検索エンジンを用いた演習  1/20.
データモデリング Web ページの検索とランキン グ Google, Yahoo はこんなことをして いる.
2015 年度 有限幾何学 期末試験 次の各問に答えよ.( (1), (2), (3), (4), (5), (7), (8), (10) は答えだけでよい) (1) 有向閉路が存在しない位数 4 のトーナメントを描け. (2) 内点の個数が 10 個の正則 2 分木の葉の個数を求めよ. (3) グラフ.
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
0章 数学基礎.
第1章 場合の数と確率 第1節 場合の数  2  場合の数 (第2回).
計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
シミュレーション論Ⅰ 第6回 待ち行列のシミュレーション.
黒澤 馨 (茨城大学) 情報セキュリティ特論(4) 黒澤 馨 (茨城大学) 2017/3/4 confidential.
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第4回 配列(2) 情報・知能工学系 山本一公
第1回レポートの課題 6月19日出題 今回の課題は1問のみ 第2回レポートと併せて本科目の単位を認定 第2回は7月に出題予定
確率・統計Ⅰ 第11回 i.i.d.の和と大数の法則 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
プログラミング演習Ⅱ 第12回 文字列とポインタ(1)
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
Extremal Combinatorics 14.1 ~ 14.2
検索エンジンに関して The Anatomy of a Large-Scale Hypertextual Web Search Engine
早稲田大学 理工学術院 基幹理工学部 情報理工学科 後藤滋樹
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
【第三講義】 1次元写像の軌道と安定性.
PageRankの仕組 林晋.
データ構造と アルゴリズム 知能情報学部 新田直也.
透視投影(中心射影)とは  ○ 3次元空間上の点を2次元平面へ投影する方法の一つ  ○ 投影方法   1.投影中心を定義する   2.投影平面を定義する
情報検索演習 第8回 パソコンを起動しておくこと 前から4列目までに着席すること 2005年11月30日 後期 水曜5限
第 1 章 : 直流回路 1.3 抵抗の接続 合成抵抗,等価回路, キーワード : 電圧の分配則,電流の分配則
3次元での回転表示について.
離散数学I 第6回 茨城大学工学部 佐々木稔.
Ver.2 再掲:講義資料の所在 (URL) 下のURLは「情報数学」シラバスの「履修上の注意」に掲載されています。
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
2017年度 経済史入門 第1回 ガイダンス 経済学部 准教授 菅原歩 水4 C200.
データモデリング Webページの検索とランキング
形式言語とオートマトン Formal Languages and Automata 第4日目
【第四講義】接空間と接写像.
Result of a Search ※キーワード検索の結果
プリムのアルゴリズム 重み付きグラフG=(V,E)の任意の点集合 U⊂Vに対して一方の端点がUの中にあり、他方の端点がV-Uの中にあるような枝の中で最小の重みを持つものをlとすれば、枝lを含むような最小木が存在する。
1. 集合 五島 正裕.
関係 (relation) 集合Aの要素aとBの要素bとが、ある条件Rを満たすとき「Rの関係にある」といい、aRb と書く。
補遺:質問への解答(1) 順序対と非順序対(1回目の授業)
デザイン情報学科 メディア情報設計 河原英紀
デザイン情報学科 メディア情報設計 河原英紀
第13 最終課題発表 2009年07月14日(火曜日) 第4時限目 λ11教室
3次元での回転表示について.
高次システムのボード線図 周波数応答によるシステムの同定
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
主成分分析 Principal Component Analysis PCA
2. 関係 五島 正裕.
2. 関係 五島 正裕.
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
TA (teaching assistant) :尾関 伸之
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
様々な情報源(4章).
Ver.2 再掲:講義資料の所在 (URL) 後にレポートを回収した時に、提出者の学籍番号を、ここに掲載する予定です。
2007年 4 月~7 月( 合計12回予定) 講義資料: 上田 和紀 原著 後藤 滋樹 三訂
レポート課題 レポートの提出は による。 提出期間を厳守する。 締切は2010年1月12日(火)
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
4. システムの安定性.
電気回路学I演習 2012/11/16 (金) I1 I2 問1 Z0 V1 V2 問2 I1 I2 V1 Z0 V2 Z,Y,K行列の計算
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
行列式 方程式の解 Cramerの公式 余因数展開.
計算の理論 I ー正則表現とFAの等価性ー 月曜3校時 大月 美佳.
d b c e a f 年度 有限幾何学 中間試験 問1 次の用語の定義をそれぞれ述べよ.
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
情報検索(4) 検索エンジンを用いた演習 教員 岩村 雅一
博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
レポート課題(2班、偶数班) このスライドで課題の内容を説明する レポートの提出は による
形式言語とオートマトン Formal Languages and Automata 第5日目
プログラミング言語論 プログラミング言語論 演習7 解答と解説 演習7 解答と解説 1.
第11回 最終課題制作(2) 2009年06月30日(火曜日) 第4時限目 λ11教室
Presentation transcript:

Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列(推移行列、遷移行列) 固有値と固有ベクトル W大学 基本的な仕組は数学的 グラフの行列による表現  隣接行列(推移行列、遷移行列) 固有値と固有ベクトル W大学 S学部 C学科 G研究室 WEBページのリンクの関係 行列の上と左のW, S, C, Gは注釈 であり行列に含まれない

隣接行列を転置する 隣接行列       を転置する リンクを「出す」側から「受ける」側へ W大学 S学部 C学科 G研究室 WEBページのリンクの関係

隣接行列から推移確率行列へ 列(column)の総和が1または0になるように調整 ページの評価値をリンク先に渡す W大学 S学部 C学科 G研究室 WEBページのリンクの関係 1 1/3

推移確率行列の固有値と固有ベクトル 固有値λと固有ベクトルr 行列 M を掛ける(乗算)ということは、グラフの 辺に沿って(確率的に)推移するということである 固有ベクトルの各要素は M を掛けても定数倍 しか変化しない。(安定している) 固有ベクトルの各要素がランクになる (ただし要素の和が1となるように正規化する)

固有ベクトルの具体例 GNU Octaveを使って計算する。固有値λ=1が最大の固有値であり、固有ベクトルは下の左のようになる。 これを正規化したページランクは上の右である。 W大学 S学部 C学科 G研究室 1 1/3 2/9 ページランクを記入した図 1/9

Googleにおける工夫 サイズの大きな 疎(sparse)行列の 固有ベクトルの計算 ユーザがランダムにページを渡り歩くと仮定 W大学 C学科 G研究室

Googleにおけるページランク 次の行列の固有ベクトルを求めて、要素の和が1になるように正規化する。 W大学 S学部 C学科 G研究室

より深く調べるために 本資料の例題は簡単にするために4つのサイトに閉じていた。 現実のPageRankは早稲田大学(8/10)、理工学部(6/10)、CS学科(5/10)、後藤研(4/10)。 次の資料が参考になる http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html 本資料は上記を参考にした。ただしOctaveのスクリプトは若干改良した。 Googleの創始者による論文も入手できる。 Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998, http://www-db.stanford.edu/~backrub/pageranksub.ps Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999, http://dbpubs.stanford.edu:8090/pub/1999-31

特集:情報数学の演習問題 2005年度の定期試験問題の解答を解説します。 2006年度の諸君の勉強の参考にして下さい。 次の事実に注意してください。 2004年度の金曜日(前半)の担当は上田和紀教授、2005年度から担当を交代して後藤滋樹です。 本日の授業では3題を解説します。残り2題は来週以降に解説する予定。

問1.集合 A={ 2, 3, 4, 5 }, 集合 B={ 1, 3, 5, 7 }とするとき、次の(1-1)~(1-6)の集合を外延的に表現せよ。 ヒント: 記号の意味を覚えておく必要がある

問1.解答 ヒント: 各集合の要素の数を考えてみる

問2.自然数の集合 N は無限集合である。このとき集合 N 2 が可算無限集合 (enumerable set, countable set) であることを示せ。

問2.解答         は自然数の集合の直積である。      の要素<x,y>に自然数 を対応づける関数は全単射である。よって  と          とは対等で同じ濃度をもつ。 集合  が可算無限集合であるから   も可算 無限集合である。

問3.次の(3-1)~(3-3)で定義する各々の二項関係は、(a)反対称律、(r)反射律、(s)対称律、 (t)推移律のどれを満たすか? (3-1)~(3-3)の各々について、満たす性質すべてを記号(a, r, s, t)で答えよ。

問3. (3-1) A は2次元平面上のすべての点の集合で、関係 R は「点 x は点 y よりも原点より遠くない」と定義される。 (3-2) A は2次元平面上のすべての直線の集合で、関係 R は「直線 x と直線 y が平行である」と定義される。 (3-3) 有限集合 A={0, 1, 2, 3, 4} の上でRは   R={<0,0>,<1,1,>,<2,2>,<3,3>,<4,4>}というグラフで定義される。

問3.解答 (3-1) r, t (3-2) r, s, t (3-3) a, r, s, t

レポートの提出方法 (2006年度 後藤担当) レポート用紙を下記のURLからプリントする レポートの提出方法 (2006年度 後藤担当) レポート用紙を下記のURLからプリントする http://www.goto.info.waseda.ac.jp/~goto/infomath.html 1班 (奇数班), と2班 (偶数班) で用紙が異なる 提出場所は、60号館2階の CS学科事務所前のBOX BOX番号は掲示による 締切厳守のこと 提出期間は、2006年5月22日(月)~26日(金)の間

問1 集合の要素 次の集合に属するすべての要素を列挙せよ。 例: [1-1] (または P (P (f g )) ) [1-2] 問1 集合の要素 次の集合に属するすべての要素を列挙せよ。 例: [1-1] (または  P (P (f g ))  ) [1-2] ヒント: [1-2]では+の左と右の集合の要素の数を、まず数えてみる。      これは有限集合である。

問2 関数 次の集合に属する要素を具体的に一つ挙げよ。 N{0,1}×{2,3} 問2 関数 次の集合に属する要素を具体的に一つ挙げよ。   N{0,1}×{2,3} ヒント: まず集合 {0, 1}×{2, 3} の要素を具体的に書いてみる。

問3 集合の濃度(可算集合) 自然数の集合 N={0,1,2,…}の直積 N2=N×Nから N への関数 f(x,y)={(x+y)2+3x+y}÷2 を考える。 (3-1) f(0,0), f(0,1), f(1,0) ,f(0,2), f(1,1), f(2,0)の値を計算せよ。 (3-2) N2は可算集合であることを説明せよ。

問4 二項関係の反射推移的閉包 集合A = {p, q, r, s} 上の二項関係 R = {<p, q>, <q, r>, <r, s>, <r,r>} の 反射推移閉包(すなわち R * )を求めよ. ヒント p q r s R0 R1 R2 R3 R4 p q r r,s s