データサイエンス設計マニュアル

100 4 章 スコアとランキング

最大値を重みとして与えることになる。こうすれば、ランク最上位の要素の間では大きな差が現れるのに対

し、ランク末尾の要素の間では大した差がつかない。

ここでどのような重み関数を選ぶかは、分野次第なので、対象となる問題に最も適していると思うものを

選ぶようにしよう。最良のコスト関数を見つけたいと思うのは、本末転倒だ。完璧な選挙制度を設計しよう

とすると、4.6 節で示すように、問題が起こる。

4.4.3 有向グラフによるランキング

「A は B よりも上位である」という形式の選択については、ネットワーク理

論を使って別の考え方ができ

る。個々の要素を頂点に対応させ、「A は B よりも上位である」という個々の選択を有向辺 (A, B) に対応

させると、有向グラフまたは有向ネットワークができる。

最終的なランキングの順列 P で B が A よりも前に来る場合、順列 P は (A, B) に違反すると表現する

場合、最適なランキングは、違反する辺の数が最も少なくなるように頂点を並べた順列 P である。

選択に完全な整合性がある場合、最適な順列が違反する辺はゼロになる。これは、グラフ内に有向閉路が

含まれないときでもある。(A, C), (C, E), (E, A) のような有向閉路があると、どのような順序を選んだと

しても満たされない辺が生まれるので、このような順位には本質的な矛盾があるということになる。

閉路のない有向グラフは、有向非巡回グラフと呼ばれる。アルゴリズムの知識が ...