直交表の数理～ MOLSの構築編～ - ペンギンは空を飛ぶ

世の中には実験計画法というものがある。実験計画法そのものに対して私は特段知見があるわけではないが、これがソフトウェア等のテストパターンを効率的に削減するのに役立つということは以前からなんとなく知っていた。考え方としては、全部のテスト条件の組み合わせをテストするのはパターンが多すぎてやりきれないので、その中から可能な限り互いに異なるものを選別することで、テストのバリエーションを確保しつつ項目数を削減しようというわけだ。

その選別方法にはいくつか手法があるが、その1つが直交表を用いた方法である。直交表の詳細な定義は後述するが、これはある種の制約を持ったテーブルであり、その制約を満たすパターンを見つけるのが難しい。私は当初この生成方法に興味を持ってなんとなく調べていたのだが、その背後には組み合わせ数学、代数学、幾何学など様々な数学との関連があることが分かった。

しかし、実験計画法というのがどちらかといえば実用寄りの話であり、（単なる推測だが）数学的な話題が主眼ではないためか、あまり直交表の数理的側面について詳しく解説された日本語の記事*1をインターネット上で見つけることができなかった。

そこで、本稿から続くいくつかの記事の中で、直交表の数理的側面について自分が理解したことをまとめてみようと思う。手始めに、本稿では直交表の基本的な説明を行った後、直交表を生成するために必要なmutually orthogonal Latin squares (MOLS) と呼ばれるテーブル群の生成方法について説明する。

直交表とは

定義

直交表の定義を日本語版のWIkipedia[1]から引用する。

直交表

直交表（ちょっこうひょう）とは、どの2列をとっても、その水準のすべての組み合わせが同数回現れる配列(表)のことである。これを「その2列はバランスしている」あるいは「直交している」と呼ぶ。この性質を使って、実験計画法において因子と水準の割り付け表に用いられる。

これはちょっと定義がいまいちである。というのも、列数を2つに限定しているが、実際には3つ以上ということもあり得るからだ。英語版のWikipedia[2]ではこの点も含めた定義になっているので、そちらも引用する。

Orthogonal array

In mathematics, an orthogonal array is a "table" (array) whose entries come from a fixed finite set of symbols (typically, $\{1,2,...,n\}$ ), arranged in such a way that there is an integer $t$ so that for every selection of $t$ columns of the table, all ordered $t$ -tuples of the symbols, formed by taking the entries in each row restricted to these columns, appear the same number of times.

直交表を決めるパラメータ

直交表にはいくつかパターンがある。そのパターンを決めるためのパラメータが複数あるのだが、それを明示するために直交表を $t\text{-}(v,k,\lambda)$ という記号で表す。これは英語版Wikipedia[2]の流儀であり、他にも記法は存在するが、本稿ではこれを採用する。

それぞれのパラメータの意味を以下に示す。

$v$ : 水準数
$k$ : 因子数
$t$ : 強さ
$\lambda$ : 指数

このとき、テストケース数は $\lambda v^t$ となる。つまり、直交表は $\lambda v^t$ 行 $k$ 列のテーブルとなる。

これだけだと分かりづらいので例を挙げよう。あるソフトウェアのテストをすることを考える。テスト条件は以下のようであったとする。

OS：Windows、Linux、MacOS
CPU：Intel、AMD、ARM
データベース：MySQL、SQLite、Oracle DB
ブラウザ：IE、Chrome、firefox

ここではテスト条件の項目が4つあるが、これが因子数である。また、各因子について選択肢が3つずつあるが、これが水準数となる。また、4つある因子の各水準の組み合わせとして、例えば異なる2つの組み合わせを網羅したいのであれば、強さは2となる。さらに、直交表ではそれらの組み合わせは必ず同じ回数ずつ出現するが、その回数を表すのが指数となる。例えば各組み合わせを1回ずつテストしたいとすると、上記のテストのための直交表は $2\text{-}(3,4,1)$ となる。

実際の直交表がどうなるかも見ておこう。以下の例はTech Note[3]というWebサイトを参考に作成してみた。

#	OS	CPU	データベース	ブラウザ
1	1	1	1	1
2	1	2	2	2
3	1	3	3	3
4	2	1	2	3
5	2	2	3	1
6	2	3	1	2
7	3	1	3	2
8	3	2	1	3
9	3	3	2	1

ただし、各水準に適当に1～3の数値を割り当てて考えるものとする。例えば、WIndows: 1、Linux: 2、MacOS: 3という感じで考えればよい。

直交表を用いない場合、テスト条件の組み合わせ数は $3^4 = 81$ 通りとなる。それに比べると大幅にテストケース数を削減できていることが分かるだろう。

強さのパラメータは直交表構築手法に重大な影響を与える。強さ3以上の直交表の構築方法は現時点では難しくて分からないので、しばらくは強さ2で考えることにする。

また、指数は増やすことはできても、ある一定の値以下にすることが不可能な場合があり、実質的には調整可能なパラメータにならないように思われる。例えば[3]で例示されている $L_8(2^7)$ (本稿の記法では $2\text{-}(2,7,2)$ ) については、因子数が多いのでどう足掻いても $\lambda =1$ にすることはできない。

Mutually orthogonal Latin squares (MOLS)

強さ2の直交表を構築するために、まずはmutually orthogonal Latin squares (MOLS) というものを構築する必要がある。以下ではこれについて説明する。

定義

MOLSを理解するためには、先にLatin squareとは何かを知っておく必要がある。Latin squareの定義を英語版Wikipedia[4]より引用する。

Latin square

In combinatorics and in experimental design, a Latin square is an $n \times n$ array filled with $n$ different symbols, each occurring exactly once in each row and exactly once in each column.

これは例を見たほうが早い。以下に次数3のLatin squareの例を示す。

1	2	3
2	3	1
3	1	2

これを見ると、任意の行・任意の列について、1～3の数字がちょうど一回ずつ表れていることが分かる。

Latin squareは同じ次数に対して複数存在する。その中である条件を満たしたものを集めた集合がMOLSである。MOLSの定義を英語版Wikipedia[5]より引用する。

Mutually orthogonal Latin squares

In combinatorics, two Latin squares of the same size (order) are said to be orthogonal if when superimposed the ordered paired entries in the positions are all distinct. A set of Latin squares, all of the same order, all pairs of which are orthogonal is called a set of mutually orthogonal Latin squares.

要するに互いに「直交する」Latin squareの集合がMOLSである。引用した定義の中に記載されているが、Latin squre同士が直交するというのは独特の用語であり、ベクトルの直交なんかとはあまり関連がないので注意されたい。

以下に次数4のMOLSの例を示す。これをMOLS(4) のように表記する。

1	2	3	4
2	1	4	3
3	4	1	2
4	3	2	1

1	2	3	4
4	3	2	1
2	1	4	3
3	4	1	2

1	2	3	4
3	4	1	2
4	3	2	1
2	1	4	3

これらのうち2つを選ぶと、それらは互いに「直交」している。例えば、1つ目と2つ目の表について、同じセル同士の数字で順序対を形成すると、各セルに対応する順序対は全て異なる。具体的には以下のようになる。

(1, 1)	(2, 2)	(3, 3)	(4, 4)
(2, 4)	(1, 3)	(4, 2)	(3, 1)
(3, 2)	(4, 1)	(1, 4)	(2, 3)
(4, 3)	(3, 4)	(2, 1)	(1, 2)

標準形

MOLSにはある種の自由度がある。例えば、属する全ての表について、行や列の入れ替えを行ってもやはりMOLSとなる。このような本質的でない自由度を排除するため、MOLSの標準形というものを考える[5]。

MOLSの標準形の定義を以下に示す。

Standard form

any set of MOLS can be put into standard form, meaning that the first row of every square is identical and normally put in some natural order, and one square has its first column also in this order

要するに、標準形とは全ての表の最初の行が自然な順序で並んでおり、かつある1つの表については最初の列もその順序で並んでいるようなMOLSのことである。先ほど示したMOLS(4)の例は標準形になっている。

MOLS( $n$ )の要素数

MOLS( $n$ )の標準形の要素数はどうなるだろうか？ $n = 1$ の場合は自明なので、 $n \ge 2$ として考える。このとき、(2, 1)成分の値を考えると、標準形であることから1にはなり得ない。そのため、2〜 $n$ の $n-1$ 通りの値が考えられる。

ここで、(2, 1)成分の値が $m (2, 3, \cdots , n)$ になるようなLatin squareが2つ以上あると仮定する。すると、それらのうちの2つの表から得られる(2, 1)成分の順序対は $(m, m)$ となる。しかし、これは $(1, m)$ 成分の順序対と一致しているため、MOLSであるということに矛盾する。

そのため仮定は誤りで、(2, 1)成分の値が $m$ になるようなLatin squareは高々1つ存在する。すなわち、MOLS( $n$ )の要素数は $n-1$ 以下となる。

MOLSの完全集合

MOLS( $n$ )の要素数がちょうど $n-1$ になるとき、それをMOLSの完全集合と呼ぶ。完全集合は $n$ が素数冪のときには存在することが知られている。存在性の証明は単純明快で、完全集合を具体的に構築する手法 (詳細は後述) が存在する。

ちなみに、一般の $n$ について完全集合が存在するかどうかは不明らしい[5]。ちょっと気になったことを調べていると簡単に未解決問題にぶち当たるので、数学というのは案外分かっていないことが多いのだなぁと思った。

MOLSの構築方法

準備が整ったので、いよいよMOLSの構築方法について説明する。本稿では次数が素数冪の場合にMOLSの完全集合を求める方法について説明する。内容は[5]を参考にした。なお、記述をシンプルにするため、これ以降は行・列の番号は0始まりとする。

$p$ を素数、 $k$ を1以上の整数、 $q = p^k$ とする。このとき、MOLS( $q$ )を求める。有限体 $\mathbb{F}_q$ の乗法群は巡回群であるため (例えば青雪江[6]の命題1.11.38に証明がある) 、ある生成元 $\gamma$ が存在して、 $\mathbb{F}_q$ の元は以下のように書ける。

$\displaystyle{ a_0=0, a_1=1, a_2=\gamma, a_3=\gamma^2, \cdots , a_{q-1}=\gamma^{q-2} }$

なお、 $\gamma^{q-1} = 1$ である。

ここで、MOLSの要素に番号をつけて $L_r (r = 1, 2, \cdots , q-1)$ と表す。また、 $L_r$ の $(i, j)$ 成分を $L_r(i, j)$ と表記する。このとき、 $L_r(i, j)$ を以下のようにしてやればMOLSの完全集合が得られる。

$\displaystyle{ L_r(i, j) = a_j + a_r a_i }$
*2

正しくMOLSが構築できることの証明

上で示した方法はあまりにもシンプルなのだが、本当に正しいのだろうか?残念ながら英語版Wikipedia[5]に証明がないので、自力で考えてみた。

MOLSの定義に従い、以下を示せばよい。

任意の $r$ について $L_r$ はLatin squareであること
相異なる $r, s$ を任意に固定したとき、任意の $i, j$ について $L_r(i, j)$ と $L_s(i, j)$ の各セルからなる順序対は互いに異なること

1点目について、まず行 $i$ を固定する。ある $j, j'$ について $a_j + a_r a_i = a_{j'} + a_r a_i$ であるとすると、両辺から $a_r a_i$ を引いて $a_j = a_{j'}$ となる。よって $j = j'$ となる他ない。

次に列 $j$ を固定する。ある $i, i'$ について $a_j + a_r a_i = a_j + a_r a_{i'}$ であるとすると、両辺から $a_j$ を引いて $a_r a_i = a_r a_{i'}$ となる。 $a_r \ne 0$ なのでさらに両辺を $a_r$ で割ると $a_i = a_{i'}$ となる。よって $i = i'$ となる他ない。

以上により、同一行・同一列の値はすべて異なることが分かったので、 $L_r$ はLatin squareである。

2点目について、任意の $i, j$ に対して順序対 $(a_j + a_r a_i, a_j + a_s a_i)$ がすべて異なっていればよい。そこで、ある $(i, j)$ , $(i', j')$ ( $i \ne i' \vee j \ne j'$ )について2つの順序対 $(a_j + a_r a_i, a_j + a_s a_i)$ および $(a_{j'} + a_r a_{i'}, a_{j'} + a_s a_{i'})$ が等しいと仮定して矛盾を導く。仮定より以下の2つの等式が成立する。

$\displaystyle{ \begin{eqnarray} a_j + a_r a_i &=& a_{j'} + a_r a_{i'} \\ a_j + a_s a_i &=& a_{j'} + a_s a_{i'} \end{eqnarray} }$

上の式から下の式を引いて整理すると以下のようになる。

$\displaystyle{ \begin{eqnarray} a_r a_i - a_s a_i = a_r a_{i'} - a_s a_{i'} \\ a_r a_i - a_r a_{i'} = a_s a_i - a_s a_{i'} \\ a_r(a_i - a_{i'}) = a_s (a_i - a_{i'}) \end{eqnarray} }$

もし $i = i'$ とすると、同じ行に同じ値が2つ現れることになるため、これは $L_r, L_s$ がLatin squareであることに反する。よって $i \ne i'$ であり、これより $a_i \ne a_{i'}$ が分かる。 $\mathbb{F}_q$ は体なので零元以外での除算を考えることができる。そこで、上式の両辺を $a_{i} - a_{i'}$ で割ると $a_r = a_s$ が得られる。これは $r \ne s$ に矛盾する。よって順序対 $(a_j + a_r a_i, a_j + a_s a_i)$ および $(a_{j'} + a_r a_{i'}, a_{j'} + a_s a_{i'})$ は異なる。

以上により、前述の方法で得られるテーブル群はMOLSになっていることが分かった。

数値への変換

前述の方法で得られたテーブルの要素は $\mathbb{F}_q$ の元となっている。このままだと使いにくいので、これを数値に変換しておくとよいだろう。これは簡単で、以下のような写像 $f$ によって $\mathbb{F}_q$ の元を自然数に対応付ければよい。

$\displaystyle{ \begin{eqnarray} f: a_i \mapsto i+1 \end{eqnarray} }$

こうすることで自然とMOLSの標準形が得られる。

MOLSを構築してみよう

MOLSの構築方法が分かったので、実際に構築してみよう。以下に本手法のsageによる実装例を示す。

#!/usr/bin/env sage

import sys
from sage.all import *

def isOrthogonal(ls1, ls2):
    orderedPairs = set()
    for row in range(len(ls1)):
        for col in range(len(ls1)):
            orderedPair = (ls1[row][col], ls2[row][col])
            if orderedPair in orderedPairs:
                return False
            orderedPairs.add(orderedPair)
    return True

def calcMOLS(q):
    gf = GF(q, name="a", modulus="primitive")
    gamma = gf.gen()
    orderedGf = [0] + [gamma**(val) for val in range(q-1)]

    mols = []
    for r in range(1, q):
        latinSquare = [[0 for i in range(q)] for j in range(q)]
        for row in range(q):
            for col in range(q):
                latinSquare[row][col] = orderedGf[col] + orderedGf[r] * orderedGf[row]
        mols.append(latinSquare)

    # Hasmap to convert elements of GF(q) to corresponding integers
    gfToInt = {}
    for i, val in enumerate(orderedGf):
        gfToInt[val] = i+1

    for i, latSq in enumerate(mols):
        for j, line in enumerate(latSq):
            mols[i][j] = [gfToInt[val] for val in line]

    return mols

def main(argc, argv):
    if argc != 2:
        print("usage: " + argv[0] + " order")
        return

    q = int(argv[1])

    print("=== Calc MOLS ===")
    mols = calcMOLS(q)
    for i, latSq in enumerate(mols):
        print("Latin square#{}:".format(i+1))
        for line in latSq:
            print(line)

    print("=== Sanity check ===")
    for r in range(len(mols)-1):
        for s in range(r+1, len(mols)):
            if not isOrthogonal(mols[r], mols[s]):
                print("The result is wrong.")
                return
    print("Correct MOLS.")

if __name__ == "__main__":
    main(len(sys.argv), sys.argv)

実行例を以下に示す。

shinya@DESKTOP-Q1NSEEU:~/programs/blog/2021% ./mols.py 2
=== Calc MOLS ===
Latin square#1:
[1, 2]
[2, 1]
=== Sanity check ===
Correct MOLS.
shinya@DESKTOP-Q1NSEEU:~/programs/blog/2021% ./mols.py 3
=== Calc MOLS ===
Latin square#1:
[1, 2, 3]
[2, 3, 1]
[3, 1, 2]
Latin square#2:
[1, 2, 3]
[3, 1, 2]
[2, 3, 1]
=== Sanity check ===
Correct MOLS.
shinya@DESKTOP-Q1NSEEU:~/programs/blog/2021% ./mols.py 4
=== Calc MOLS ===
Latin square#1:
[1, 2, 3, 4]
[2, 1, 4, 3]
[3, 4, 1, 2]
[4, 3, 2, 1]
Latin square#2:
[1, 2, 3, 4]
[3, 4, 1, 2]
[4, 3, 2, 1]
[2, 1, 4, 3]
Latin square#3:
[1, 2, 3, 4]
[4, 3, 2, 1]
[2, 1, 4, 3]
[3, 4, 1, 2]
=== Sanity check ===
Correct MOLS.
shinya@DESKTOP-Q1NSEEU:~/programs/blog/2021% ./mols.py 5
=== Calc MOLS ===
Latin square#1:
[1, 2, 3, 4, 5]
[2, 3, 5, 1, 4]
[3, 5, 4, 2, 1]
[4, 1, 2, 5, 3]
[5, 4, 1, 3, 2]
Latin square#2:
[1, 2, 3, 4, 5]
[3, 5, 4, 2, 1]
[4, 1, 2, 5, 3]
[5, 4, 1, 3, 2]
[2, 3, 5, 1, 4]
Latin square#3:
[1, 2, 3, 4, 5]
[4, 1, 2, 5, 3]
[5, 4, 1, 3, 2]
[2, 3, 5, 1, 4]
[3, 5, 4, 2, 1]
Latin square#4:
[1, 2, 3, 4, 5]
[5, 4, 1, 3, 2]
[2, 3, 5, 1, 4]
[3, 5, 4, 2, 1]
[4, 1, 2, 5, 3]
=== Sanity check ===
Correct MOLS.
shinya@DESKTOP-Q1NSEEU:~/programs/blog/2021% ./mols.py 6
=== Calc MOLS ===
/usr/lib/python3/dist-packages/apport/report.py:13: DeprecationWarning: the imp module is deprecated in favour of importlib; see the module's documentation for alternative uses
  import fnmatch, glob, traceback, errno, sys, atexit, locale, imp, stat
Traceback (most recent call last):
  File "./mols.py", line 63, in <module>
    main(len(sys.argv), sys.argv)
  File "./mols.py", line 48, in main
    mols = calcMOLS(q)
  File "./mols.py", line 17, in calcMOLS
    gf = GF(q, name="a", modulus="primitive")
  File "sage/structure/factory.pyx", line 367, in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2162)
  File "/usr/lib/python3/dist-packages/sage/rings/finite_rings/finite_field_constructor.py", line 566, in create_key_and_extra_args
    raise ValueError("the order of a finite field must be a prime power")
ValueError: the order of a finite field must be a prime power

コマンドライン引数で次数 $q$ を受け取っているが、確かにサイズ $q-1$ のMOLSが構築できた。次数6のケースで異常終了しているが、6は素数冪ではないためこれは期待通りである。