お薦めの本 トピックス プログラム、シミュレーション

ループにはまらないように

投稿日:

基礎からわかるアルゴリズム」(著者:パノス・ルリダス 発行所:ニュートン新書)から「Google行列」について紹介します。Googleの検索は必ず結果を出してくれます。その理屈です。

資料をご覧ください → アルゴリズムその2

p.1 先ずページランクの定義です。検索ページが①~⑤ある場合、矢印が引用先を示しています。ページ2は、ページ3と5を引用(ここでは重要性としています)しています。ページ3の重要性は、ページ2,4および5からの投票あるいはリンク数によって決まります。

p.2 各ページのリンク状況を行列で表します。行がOUT列がINと考えれば、行列は直ぐ作れます。3行目は、ページ3がリンクを貼っているページを示しています。数字の1がリンクあり0がリンクなしです。3列目は、ページ3がリンクを受けているページを示しています。 各行の和で、その行の数値を割った行列が「ハイパーリンク行列」です。各行の和は1になります。ページ①のページランクは列1の数値を用いて表されます。

p.3 初期状態の各ページの重要性は、全て「1/n」としておきます。初期状態をベクトルで示します。このベクトルにハイパーリンク行列Hを掛けて、1回目のベクトルがπ、2回目がπ、3回目がπとなっていきます。 ページ1~3が図のようにリンクされている事例で計算してみます。先ず、ハイパーリンク行列Hを作成します。続いて、初期状態の各ページのベクトルを(1/3、1/3、1/3)とおいて、1回目~3回目のベクトルを計算した結果、3回目でベクトルの成分が全て0になってしまいます。これ以上、検索してもページ③で止まってしまうのです。飛び先がないためです。このノード③のことを「ぶら下りノード」と呼びます。わがままノード、ブラックホールとも呼びます。

p.4 ぶら下りノードのベクトル成分の計算結果を右上に示します。ここから抜け出すためには、全て0の行列に数値を等分に入れます。今回は1/3を入れます。ベクトル成分の再計算値を表にすると、値が収束することがわかります。ページ③の重要性は変わっていません。

p.5 左図のようなリンク状態の場合、ベクトルを計算すると、下表のようにページ①と④がになってしまいます。つまり、赤枠の中から抜け出せなくなってしまうのです。

p.6 行列の中に0があると抜け出せなくなるため、行の和は1として、数値を入れ込みます。この行列を「グーグル行列」と呼びます。この計算結果を表に示します。数値の入れ込み方は、数学的に求めますが、まだ理解できていないので省きます。

ループにはまってフリーズしないように、いろいろな手法が開発されているようです。最適解を求める際にも、極小ではなく最小値を求めるようにジャンプする方法がありましたね。

-お薦めの本, トピックス, プログラム、シミュレーション

Copyright© 進化するガラクタ , 2022 All Rights Reserved Powered by STINGER.