直交表の数理 ~ MOLSの構築編 ~
世の中には実験計画法というものがある。実験計画法そのものに対して私は特段知見があるわけではないが、これがソフトウェア等のテストパターンを効率的に削減するのに役立つということは以前からなんとなく知っていた。考え方としては、全部のテスト条件の組み合わせをテストするのはパターンが多すぎてやりきれないので、その中から可能な限り互いに異なるものを選別することで、テストのバリエーションを確保しつつ項目数を削減しようというわけだ。
その選別方法にはいくつか手法があるが、その1つが直交表を用いた方法である。直交表の詳細な定義は後述するが、これはある種の制約を持ったテーブルであり、その制約を満たすパターンを見つけるのが難しい。私は当初この生成方法に興味を持ってなんとなく調べていたのだが、その背後には組み合わせ数学、代数学、幾何学など様々な数学との関連があることが分かった。
しかし、実験計画法というのがどちらかといえば実用寄りの話であり、(単なる推測だが)数学的な話題が主眼ではないためか、あまり直交表の数理的側面について詳しく解説された日本語の記事*1をインターネット上で見つけることができなかった。
そこで、本稿から続くいくつかの記事の中で、直交表の数理的側面について自分が理解したことをまとめてみようと思う。手始めに、本稿では直交表の基本的な説明を行った後、直交表を生成するために必要なmutually orthogonal Latin squares (MOLS) と呼ばれるテーブル群の生成方法について説明する。
直交表とは
定義
直交表の定義を日本語版のWIkipedia[1]から引用する。
これはちょっと定義がいまいちである。というのも、列数を2つに限定しているが、実際には3つ以上ということもあり得るからだ。英語版のWikipedia[2]ではこの点も含めた定義になっているので、そちらも引用する。
直交表を決めるパラメータ
直交表にはいくつかパターンがある。そのパターンを決めるためのパラメータが複数あるのだが、それを明示するために直交表をという記号で表す。これは英語版Wikipedia[2]の流儀であり、他にも記法は存在するが、本稿ではこれを採用する。
それぞれのパラメータの意味を以下に示す。
- : 水準数
- : 因子数
- : 強さ
- : 指数
このとき、 テストケース数はとなる。つまり、直交表は行列のテーブルとなる。
これだけだと分かりづらいので例を挙げよう。あるソフトウェアのテストをすることを考える。テスト条件は以下のようであったとする。
ここではテスト条件の項目が4つあるが、これが因子数である。また、各因子について選択肢が3つずつあるが、これが水準数となる。また、4つある因子の各水準の組み合わせとして、例えば異なる2つの組み合わせを網羅したいのであれば、強さは2となる。さらに、直交表ではそれらの組み合わせは必ず同じ回数ずつ出現するが、その回数を表すのが指数となる。例えば各組み合わせを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以上の直交表の構築方法は現時点では難しくて分からないので、しばらくは強さ2で考えることにする。
また、指数は増やすことはできても、ある一定の値以下にすることが不可能な場合があり、実質的には調整可能なパラメータにならないように思われる。例えば[3]で例示されている (本稿の記法では) については、因子数が多いのでどう足掻いてもにすることはできない。
Mutually orthogonal Latin squares (MOLS)
強さ2の直交表を構築するために、まずはmutually orthogonal Latin squares (MOLS) というものを構築する必要がある。以下ではこれについて説明する。
定義
MOLSを理解するためには、先にLatin squareとは何かを知っておく必要がある。Latin squareの定義を英語版Wikipedia[4]より引用する。
これは例を見たほうが早い。以下に次数3のLatin squareの例を示す。
1 | 2 | 3 |
2 | 3 | 1 |
3 | 1 | 2 |
これを見ると、任意の行・任意の列について、1~3の数字がちょうど一回ずつ表れていることが分かる。
Latin squareは同じ次数に対して複数存在する。その中である条件を満たしたものを集めた集合がMOLSである。MOLSの定義を英語版Wikipedia[5]より引用する。
要するに互いに「直交する」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の標準形の定義を以下に示す。
要するに、標準形とは全ての表の最初の行が自然な順序で並んでおり、かつある1つの表については最初の列もその順序で並んでいるようなMOLSのことである。先ほど示したMOLS(4)の例は標準形になっている。
MOLS()の要素数
MOLS()の標準形の要素数はどうなるだろうか?の場合は自明なので、として考える。このとき、(2, 1)成分の値を考えると、標準形であることから1にはなり得ない。そのため、2〜の通りの値が考えられる。
ここで、(2, 1)成分の値がになるようなLatin squareが2つ以上あると仮定する。すると、それらのうちの2つの表から得られる(2, 1)成分の順序対はとなる。しかし、これは成分の順序対と一致しているため、MOLSであるということに矛盾する。
そのため仮定は誤りで、(2, 1)成分の値がになるようなLatin squareは高々1つ存在する。すなわち、MOLS()の要素数は以下となる。
MOLSの構築方法
準備が整ったので、いよいよMOLSの構築方法について説明する。本稿では次数が素数冪の場合にMOLSの完全集合を求める方法について説明する。内容は[5]を参考にした。なお、記述をシンプルにするため、これ以降は行・列の番号は0始まりとする。
を素数、を1以上の整数、とする。このとき、MOLS()を求める。有限体の乗法群は巡回群であるため (例えば青雪江[6]の命題1.11.38に証明がある) 、ある生成元が存在して、の元は以下のように書ける。
なお、である。
ここで、MOLSの要素に番号をつけてと表す。また、の成分をと表記する。このとき、を以下のようにしてやればMOLSの完全集合が得られる。
正しくMOLSが構築できることの証明
上で示した方法はあまりにもシンプルなのだが、本当に正しいのだろうか?残念ながら英語版Wikipedia[5]に証明がないので、自力で考えてみた。
MOLSの定義に従い、以下を示せばよい。
- 任意のについてはLatin squareであること
- 相異なるを任意に固定したとき、任意のについてとの各セルからなる順序対は互いに異なること
1点目について、まず行を固定する。あるについてであるとすると、両辺からを引いてとなる。よってとなる他ない。
次に列を固定する。あるについてであるとすると、両辺からを引いてとなる。なのでさらに両辺をで割るととなる。よってとなる他ない。
以上により、同一行・同一列の値はすべて異なることが分かったので、はLatin squareである。
2点目について、任意のに対して順序対がすべて異なっていればよい。そこで、ある, ()について2つの順序対およびが等しいと仮定して矛盾を導く。仮定より以下の2つの等式が成立する。
上の式から下の式を引いて整理すると以下のようになる。
もしとすると、同じ行に同じ値が2つ現れることになるため、これはがLatin squareであることに反する。よってであり、これよりが分かる。は体なので零元以外での除算を考えることができる。そこで、上式の両辺をで割るとが得られる。これはに矛盾する。よって順序対およびは異なる。
以上により、前述の方法で得られるテーブル群は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
コマンドライン引数で次数を受け取っているが、確かにサイズのMOLSが構築できた。次数6のケースで異常終了しているが、6は素数冪ではないためこれは期待通りである。
余談だが、sageは本当に万能で惚れ惚れする。今回は自分のPC (Windows10のWSL2で動作するUbuntu20.04) にインストールしたsageを使用したが、最近ではそんなことしなくてもブラウザ上で実行できたりするようである[7]。興味のある方は試してみるとよい。
まとめ
本稿では直交表の基本的な事項について説明した後、直交表の生成に必要となるMOLSの構築方法について述べた。具体的には有限体の性質をうまく使ってMOLSが構築できることを説明した。また、説明した手法を実際にsageで動かして正しさを実証した。
次回はMOLSを用いて直交表を生成する方法について書きたいと思う。恐らく今回ほどのボリュームにはならないだろう。さらにその次は有限射影幾何との関連についても考えてみたいが、こちらは現時点ではさっぱり見通しがない。頑張って勉強しようと思う。
参考
[1] 直交表 - Wikipedia
[2] Orthogonal array - Wikipedia
[3] www.ipros.jp
[4] Latin square - Wikipedia
[5] Mutually orthogonal Latin squares - Wikipedia
[6]
- 作者:雪江 明彦
- 発売日: 2010/12/07
- メディア: 単行本(ソフトカバー)