印象評価への組合せ構造の応用
理学専攻・情報科学コース
辻有万里

1

研究目的

現代の世の中では，あらゆる評価が他との比較によってなされる．芸術の審査などの主観に依存する印象評
価を行う際，審査対象がある程度多い場合には，演奏順や展示の配置等の影響により公平な審査を行うことが困難な場合もある．本研究では，組合せ構造を用いて，審査対象を少数に分割して評価を行うことで全体の評価を与える方法を提案する．

2組合せ構造

ここでは，組合せ構造のうちグラフとブロックデザインを用いた配置について述べる．

2.1

グラフを用いた配置

どの対象のペアも順序を除き 1 度以上連続するように並べることができれば，審査員はそれぞれの対象をその 1 つ前と比較することですべてのペアの比較結果を得ることができる．この配置は，同時に複数の対象を鑑賞できない楽器演奏などの審査に特に有効であるが，出場者 1 人あたりの演奏回数が複数になることの負担は否定できない．そのため，列の長さをできるだ
け短くしたい．

2.1.1

ブロックデザインを用いた配置

2.2.1

ブロックデザインの定義v ≥ k ≥ t ≥ 0，λ ≥ 1 とする．v 点集合を P ，そのk-部分集合（ブロックという）の集まりを B とする．
どの t 点集合 T についても，T のすべての点を含むブロックがちょうど λ 個存在するとき，(P, B) を v ，k ，λ 上の t-デザインといい，t-(v, k, λ) デザインと表す．
2.2.2n −n+2．
22例）審査対象の数を 5 とすると，以下のような列は条件を満たす．
12345135241
審査対象が偶数の場合

偶数点の完全グラフはオイラー閉路が存在しないため，どの対象のペアも順序を除きちょうど 1 度ずつ連続するような並べ方はない．各対象がいずれかの対象
1 つとだけ 2 度連続することを許せば，必要な列を得ることができる．これは，完全グラフにすべての点の次数が偶数になるように最少数の辺を加えたグラフのオイラー閉路を見つけることで実現できる．この方法により得られる列の長さは

n2 + 2．
2例）審査対象の数を 6 とすると，以下のような列は条件を満たす．

1236543612462541351
これは，1 と 2，3 と 6，4 と 5 が 2 度ずつ連続している以外は，1 度ずつ連続する列になっている．

印象評価の例

審査対象が多数の場合，一度にすべてを比較するのは困難である．そこで，対象を少数ずつのグループに分け，各グループ内での比較を行うことで，評価をしやすくすることを考える．なるべく少ないグループ数で，どの対象のペアも比較されるように分割をするために，ブロックデザインを用いることにする．
例 え ば ，絵 画 の コ ン テ ス ト に お い て ，7 作 品{x1 , x2 , x3 , x4 , x5 , x6 , x7 } を対象に評価を行うことを考える．どの 2 作品も 1 度以上同じグループになるように，3 作品ずつ比較したい．このとき，2-(7, 3, 1)
デザインにしたがってグループを作れば，どの 2 作品もちょうど 1 度ずつ同じグループになる．
以下がグループ分けの例である．

審査対象が奇数の場合

奇数点の完全グラフはオイラー閉路が存在するため，どの対象のペアも順序を除きちょうど 1 度ずつ連続するように並べることができる．このとき列の長さは最短であり，その長さは

2.1.2

2.2

(x1 , x2 , x4 )，(x3 , x4 , x6 )，(x2 , x3 , x5 )，(x1 , x3 , x7 )，(x1 , x5 , x6 )，(x2 , x6 , x7 )，(x4 , x5 , x7 )

順序の決定

3

想定される比較結果のばらつきを考慮し，比較結果が部分的にしか得られない場合であっても，対象どうしの比較結果から全体を並べる方法を提案する．
提案手法

3.1

すべての対象のペアについて比較結果が得られた場
合，評価者全員の選好が一致していれば，各対象について，自身より上位のものの数の合計に 1 を足した値が全体での順位になる．一致していなくても，同様の計算をし，得た値の大小により全体の順序を決めることができる．
しかし比較結果が部分的にしか得られない場合には，比較されていない対象のペアの選好を補完する必要がある．各ペアについての評価人数と比較結果が得られていないペアが同時に把握できるものとして，重み付
き有向グラフを用いることにした．
以下に，検討したアルゴリズムを示す．

3.1.1

重み更新アルゴリズム

1. 準備
対象を点とする完全有向グラフを用意する．
点 i，j を比較した評価者の人数を重み z(ij)，このうち i ≺ j と評価した人数を重み w(ij) として辺 ij に付す．

逆方向の重みは，3.1.2w(ji) = z(ij) − w(ij),z(ji) = z(ij)となる．

2. 重みの更新

人数 n の決め方

人数 n の決め方によって，間接的に比較されている部分の影響の度合いが変わってくる．評価者の多いデータほど結果の信頼性が担保されると考えるのが自然であるため，n = min(m1 , m2 )とする．

間接的に比較されている部分を反映させるため，
距離 2 でたどれるすべての辺について，以下の手順で重みを更新する．

2 辺 v1 x，xv2 の重みをそれぞれw(v1 x) = r1 ,z(v1 x) = m1 ,w(xv2 ) = r2 ,z(xv2 ) = m2とする．
逆方向の重みはそれぞれw(xv1 ) = m1 − r1 ,z(xv1 ) = m1 ,w(v2 x) = m2 − r2 ,z(v2 x) = m2となる．

2 辺 v1 x，xv2 でたどれる辺 v1 v2 の重みについて，以下を計算する．人数 n の決め方については後述
する．
r1 r2u(v1 x, xv2 ) =× n,m1 m2v(v1 x, xv2 ) =(m1 − r1 )(m2 − r2 )
× n.
m1 m2

3.2

更新後も重み 0 の辺がある場合

比較結果が得られている対象どうし，すなわちもとのグラフで重み z が 0 でない辺は，更新後の重み z も0 でない値が得られる．
もとのグラフで重み z が 0 の辺は，更新において他の辺からの重みの加算がない場合には，更新後も 0 のままとなってしまう．このような場合には，更新後の新しい重みに対して，再度重み更新アルゴリズムを適用することとする．すると，もとのグラフ上での距離3 または距離 4 の辺についても重みを影響させることができる．2 回目の更新後も重み z が 0 の辺がある場
合には，3 回目の更新を行うというように，すべての辺の重み z が 0 でない値になるまで繰り返し更新を行うこととする．ただし，何度更新を行っても重み z が 0でない値にならない辺が含まれる場合には補完が完了しないため，不足している比較結果を得る必要がある．
重み更新アルゴリズムは，すべての辺の重みを同時に更新することで，更新順や部分的な更新による他の辺からの影響の偏りを排除し公平性を保っている．更新を何度繰り返してもこの性質を保持したいと考え，
重み z が 0 である辺のみの更新などは行わないこととしている．これは，恣意性を排除するためともいえる．

ただし，m1 = 0 または m2 = 0 の場合は，u = 0，v = 0 とする．

4

点 v1 から点 v2 へ距離 2 でたどれるすべての辺のペア（これらの辺に含まれる点の集合を X とする）について u と v を求め，u の合計を
∑u(v1 x, xv2 ),U=組合せ構造による配置と重み付き有向グラフを用いて，審査対象が多数であっても公平かつ効率的な順位付けを行う方法を考案した．提案手法によれば，間接的な比較結果を全体の順序に反映させることができ，比較結果が得られていない対象どうしの選好の補完や，評価人数の偏りによる不平等さの排除が実現できる．

x∈X\{v1 ,v2 }v の合計をV =

∑

まとめ

参考文献
v(v1 x, xv2 )x∈X\{v1 ,v2 }とする．

w(v1 v2 ) + U
を新しい重み w(v1 v2 )，z(v1 v2 ) + U + V
を新しい重み z(v1 v2 ) とする．

3. 順序の決定
各点 i について，入ってくる辺の重み w の合計を in(i)，出て行く辺の重み w の合計を out(i) とする．
in(i)out(i)を計算し，その大小によってすべての点を並べる．

[1] I. Anderson and I. Honkala, A Short Course in
Combinatorial Designs. Internet edition, 1997.
[2] R. Brüggemann and G. P. Patil, Partial order andHasse diagrams. In Ranking and Prioritization
for Multi-indicator Systems, pp. 13-23. Springer,2011.
[3] P. Dukes, E. Lamken, and R. Wilson, Combinatorial design theory. 2008.
[4] M. Meszka, Combinatorial designs. 2014 PhD
Summer School in Discrete Mathematics.
[5] D. R. Stinson, Combinatorial Designs: Constructions and Analysis. Springer, 2004.
[6] J. H. van Lint and R. M. Wilson, A Course in
Combinatorics. Cambridge University Press, second edition, 2001.