印象評価における比較順序の提案
理学専攻・情報科学コース

1

はじめに比較対象に絶対的な順位があるわけではなく，人間の主観に基づいて対象の評価が行われるものを「印象評価」と呼ぶ．例えば，音楽や絵画といった芸術のコンクールでの審査や，より美味しいあるいはより使い心地の良い製品を作るためのユーザーテストなどには，印象評価が用いられることが多いだろう．印象評価による順位付けを行うときに用いられる手法のひとつに，一対比較法というものがある．これは，すべての対象同士を互いに比較しどちらのほうが良いかを選ばせるものであり，安定した評価結果を得られる手法であると言われているが，すべての対象を互いに比較する必要があるため，比較回数が多くなり，結果を得るのが難しくなってしまうという側面がある．そのため，一部のものの比較によって，全体の大まかな順位を求める手法が必要とされている．
ここでは，比較対象の集合に含まれる任意の 2 つの要素を特定の順序で比較できる状態にし，複数の評価者がそれぞれ任意のタイミングで一定時間にわたって評価を行い，その結果をもとに対象の順位を決定するという状況を仮定する．そのような状況には，連続して現れる 2 つのものを比較する場合と，同時に現れる2 つのものを比較する場合が考えられ，それぞれ例として以下のようなものが挙げられる．
連続して現れる 2 つのものを比較する例
CM コンテストの審査において，ある部屋のスクリーンに応募作品を特定の順序で流し，来場者は好きなタイミングでその部屋に出入りすることができるとする．このとき，各来場者はいくつかの作品を連続して見ることになるが，連続する 2 つの作品のうちどちらが気に入ったかというものをその都度投票してもらい，その結果を集計して応募作品を順位付けする．
同時に現れる 2 つのものを比較する例
あるウェブページ上にインターネット広告を 2 つ同時に表示し，表示されている広告は特定の順序で遷移するものとする．ユーザーには，そのページにアクセスしている間の任意のタイミングで，気に入った広告があればクリックしてもらう．ユー
ザーの選択を検出することにより，効果的な広告を順位付けする．
このような方法で印象評価における順位付けを行うとしたとき，考えられる問題点としては次のようなものがある．まず，来場者やオンラインユーザーといった評価者の数は時間帯によって差があり，極端に評価者が多い時間帯が存在する場合，その時間帯における特定の対象の出現数の多寡によって，得られるデータに偏りが生じてしまう．また，評価者個人に着目すると，その評価者は自身が見た一定時間に現れた対象についての評価を担うが，同じものが近い間隔で複数回現れてしまっては，評価結果に影響が出るという可能性もある．

野月 麻衣

上記の問題を避けるような順序で比較対象を出現させることができれば，バランスの良い評価データを取得し，より信頼性のある順位付けを行うことができるだろう．したがって，本研究では，すべての対象同士を同じ回数ずつ比較でき，かつ，同じ対象ができるだ
け近い間隔で出現しないような順序を提案する．

2

連続して現れる対象を比較する場合

要素数 n の集合のどの 2 つの要素もちょうど 1 回ずつ連続するような順列は，頂点数 n の完全グラフのオイラー閉路の頂点の列に一致する．n が奇数のとき，完全グラフ Kn は各点の次数が n − 1 で偶数なので，オイラーの定理より，必ずオイラー閉路が存在する．したがって，n が奇数の場合には，完全グラフ Kn のオイラー閉路で，同じ頂点の距離がなるべく近くならないようなものを求めればよいことになる．
グラフ G に対して，各頂点とその次の頂点が辺で結ばれているような頂点の列で，同じ辺は 1 回しか通らないものを G の小道という．連結グラフのすべての辺を通る閉じた小道をオイラー閉路という．小道 P 上に頂点 x が 2 つ以上含まれるとき， 任意の 2 つの x の間に通った辺の本数の最小値を，小道 P における頂点x の同頂点間距離と呼ぶ．小道 P における任意の頂点の同頂点間距離のうち最小のものを，小道 P の同頂点間距離の最小値と呼ぶ．n を奇数としたとき，頂点数が n の完全グラフのすべてのオイラー閉路の同頂点間距離の最小値のうち，最も大きいものを D(n) と定義する．
定理 2.1
5 以上のすべての奇数 n について，D(n) ≥ 3 が成立する．
定理 2.2
5 以上のすべての奇数 n について，D(n) ≤ n − 2 が成立する．
定理 2.1 と定理 2.2 より，D(5) の値が決定する．
系 2.3
D(5) = 3 が成立する．
一般の n については，[2] で次の定理 2.4，定理 2.5と予想 2.6 が紹介されている．
定理 2.4
7 以上のすべての奇数 n について，D(n) ≥ n − 4 が成立する．
定理 2.5
13 以上のすべての奇数 n について，D(n) ≤ n − 3が成立する．
予想 2.6
15 以上のすべての奇数 n について，D(n) = n − 4が成立する．

ここで，同頂点間距離の最小値が (n + 1)/2 となるようなオイラー閉路が存在するための条件を示す．
定理 2.7
長さ p = (n−1)/2 の列 A0 : a0 , a1 , a2 , . . . , ap−1 を考える．A0 が以下の条件をすべて満たすとき，Ak を，A0の各要素にぞれぞれ k を足して n で剰余をとった列とすると，n 個の列を順に並べた列 B : A0 , A1 , . . . , An−1
は同頂点間距離の最小値が p + 1 = (n + 1)/2 のオイ
ラー閉路をなす．
ただし |x| は，±x mod n の小さい方を表す．

• 条件 1|a0 −a1 |, |a1 −a2 |, . . . , |ap−2 −ap−1 |, |ap−1 −(a0 +1)|に 1 から p がすべて現れる．
• 条件 2a0 , a2 , . . . , ap−1 はすべて異なる．
• 条件 3i < j としたとき，aj ̸= ai + 1 である．
さらに，定理 2.7 の列 A0 の構成法を決定することにより，11 以上のすべての奇数 n で，同頂点間距離の最小値が (n + 1)/2 となるようなオイラー閉路が存在することを示した．

3

同時に現れる対象を比較する場合

要素数 n の集合に対して，互いに異なる 2 要素をペアとしたとき，そのすべてがちょうど 1 回ずつ現れる円順列を，すべてのペアの円順列と呼ぶ．ペアの円順列上で，ある要素 a を含むペア同士の距離の最小値を，要素 a の距離という．あるペアの円順列上での任意の要素の距離のうち最小のものを，同要素の最短距離と呼ぶ．
すべてのペアの円順列を考えるとき，明らかに同要素の最短距離は n/2 以下となる．よって，n が奇数のときは，同要素の最短距離は (n − 1)/2 以下である．nが偶数のときは，同要素の最短距離が n/2 となるすべてのペアの円順列は存在しないことはただちに示せる
ため，(n − 2)/2 以下としてよい．

以下では，要素数 n の集合を {0, 1, . . . , n − 1} とし，その要素は mod n で表記する．
定理 3.1
要素数 n の集合のすべてのペアの円順列で，同要素の最短距離が d であるものが存在するならば，同要素の最短距離が d − k 以上となるような要素数 n − k の集合のすべてのペアの円順列が存在する．ただし，kは d より小さい正の整数とする．

[証明]
要素数 n の集合のすべてのペアの円順列から，要素n − 1, n − 2, . . . , n − k が含まれているペアを取り除け
ば，明らか．!
定理 3.2
自然数 m について，頂点数 n = 4m + 3 の完全グ
ラフ Kn のオイラー閉路で，同頂点間距離の最小値がd であるものが存在するならば，同要素の最短距離が⌊d/2⌋ となるような要素数 n の集合のすべてのペアの円順列が存在する．

[証明]
まず，頂点数 n = 4m + 3 の完全グラフのオイラー閉路から，要素数 n の集合のすべてのペアの円順列が生成できることを示す．このオイラー閉路の長さは，完全グラフの辺の数と等しいので，n(n − 1)/2 = (4m +3)(2m + 1) である．p = n(n − 1)/2 とし，オイラー閉路上の各頂点を，辿ることのできる順番に ki (i =1, 2, . . . , p) とする．この順列を 2 回繋げ，先頭から 2個ずつをペアと見なし，{k1 , k2 }, {k3 , k4 }, . . . , {kp−2 , kp−1 }, {kp , k1 },{k2 , k3 }, {k4 , k5 }, . . . , {kp−1 , kp }のようにペアの順列をとれば，オイラー閉路の長さが奇数であるため，これはすべてのペアを網羅している．
次に，このようにして作ったペアの円順列の同要素の最短距離を調べる．オイラー閉路上で距離が d である任意の 2 頂点について，そのオイラー閉路を用いてペアにしたときの距離は，d の偶奇と 2 頂点の配置によって，d が奇数のとき (d − 1)/2 または (d + 1)/2 となり，d が偶数のとき d/2 となる．したがって，最小値は ⌊d/2⌋ である．!

定理 2.4，定理 3.1，定理 3.2 より，次のことがわかる．

系 3.3
7 以上のすべての n について，同要素の最短距離が次の値以上になるすべてのペアの円順列が存在する．

n = 4m + 3 のとき，(n − 5)/2,
n = 4m + 2 のとき，(n − 6)/2,
n = 4m + 1 のとき，(n − 7)/2,
n = 4m のとき，

4(n − 8)/2.

まとめ

連続して現れる 2 つのものを比較する場合と，同時に現れる 2 つのものを比較する場合それぞれについて，すべての対象同士を 1 回ずつ比較でき，かつ，同じ対象ができるだけ近い間隔で出現しないような順序を提案した．

[3] では，部分的な比較結果に加えて，各ペアについての評価人数も考慮して，全体の順序を決定する方法が提案されている．本研究で提案した比較順序を利用して得られた結果をもとに [3] の手法を適用すれば，より公平な順序付けを行うことができるだろう．

参考文献[1] 神保秀司, 乾勇治, 橋口攻三郎, オイラー小道上の同一点間の間隔について, 数理解析研究所講究録,
Vol.1106, 25–36, 1999
[2] 神保秀司, 丸岡章, 完全グラフのオイラー回帰長の上界と下界の改良, 情報処理学会研究報告, Vol.2014AL-146, No.3, 2014[3] 辻有万里, 印象評価への組合せ構造の応用, お茶の水女子大学大学院 人間文化創成科学研究科 修士論
文, 2016