Loading article…
数学において、直交配列（より具体的には、固定レベル直交配列）とは、固定された有限個の記号（例えば、{1,2,..., v }）から要素が抽出された表（「配列」）であり、ある整数tが存在して、表の任意のt列の選択に対して、これらの列に限定された各行の要素から構成される、順序付けられたt個の記号の組がすべて同じ回数だけ出現するように配列されている。この数tは、直交配列の強度と呼ばれる。以下に2つの例を示す。
左の例は、シンボルセット {1,2} と強度 2 を持つ直交配列の例です。最初の列と 3 番目の列に制限された行によって形成される 4 つの順序対(2 タプル)、すなわち (1,1)、(2,1)、(1,2)、(2,2) は、2 つの要素セットのすべての可能な順序対であり、それぞれがちょうど 1 回ずつ出現していることに注目してください。2 番目の列と 3 番目の列では、(1,1)、(2,1)、(2,2)、(1,2) が得られます。これもまた、すべての可能な順序対がそれぞれ 1 回ずつ出現しています。最初の列と 2 番目の列を使用した場合でも、同じことが言えます。したがって、これは強度 2 の直交配列です。
右側の例では、[ 1 ]最初の3列に限定された行には、0と1からなる8つの可能な順序付き3つ組が含まれており、それぞれが1回ずつ出現します。他の3列の選択でも同様です。したがって、これは強度3の直交配列です。
混合レベル直交配列とは、各列のシンボル数が異なる配列のことです。以下に例を示します。
直交配列は、互いに直交するラテン方陣の概念を表形式で一般化したものです。これらの配列は、他の組み合わせ設計と多くの関連性があり、実験計画法、符号理論、暗号理論、および様々な種類のソフトウェアテストに応用されています。
t ≤ kの場合、 ( N, k, v, t )型の直交配列(略してOA ( N , k, v, t ))は、v 個の点 ( vセット)を持つ集合Xからエントリが選択されたN × k配列であり、配列のt列の任意の部分集合において、 Xの点のt組がそれぞれ同じ回数繰り返されます。繰り返し回数は通常 λ で表されます。
多くのアプリケーションでは、これらのパラメータには次のような名前が付けられています。
強度の定義はパラメータ関係につながる
直交配列は、重複する行を含まない場合、単純であると言えます。（ただし、このセクションに示されているOA(18, 7, 3, 2)の例のように、 t列のサブ配列には重複する行が含まれる場合があります。）
直交配列は、X が位数q ( q は素数のべき乗)の有限体F qであり、配列の行がベクトル空間( F q ) kの部分空間を形成する場合に線形である。[ 2 ] 序論の右側の例は体F 2上で線形である。すべての線形直交配列は単純である。
混合レベル直交配列では、列のシンボルは、次の例のように、異なる数の点を持つ異なるセットから選択できます。[ 3 ]
この配列の強度は2です。
したがって、以下で説明するように、OA(8, 5, 2 4 4 1 , 2)と表記できます。式2 4 4 1は、 4つの因子が2つのレベルを持ち、1つの因子が4つのレベルを持つことを示しています。
この例のように、強度tの混合レベル直交配列には単一の「インデックス」または繰り返し番号 λ はありません。t 列の各サブ配列は異なるλ を持つことができます。
対称と非対称という用語は、固定レベルと混合レベルを表す際に用いられることがあります。ここでいう対称性とは、すべての因子が同じ数のレベルを持つという性質を指し、配列の「形状」を指すものではありません。対称直交配列は、ほとんどの場合、対称行列ではありません。
表記 OA( N, k, v, t ) は、テキストで明示されていないパラメータ値が明確である限り、たとえば単に OA( k, v ), [ 4 ]と書くことができるように、省略されることがあります。反対に、混合レベルの配列の場合は展開できます。この場合、列iにv iレベルの値がある場合、OA( N, k, v 1 ···v k , t ) と書きます。この表記は、値vが繰り返される場合に通常短縮され、最後のセクションの最後の例では、OA(8, 5, 2·2·2·2·4, 2) ではなく OA(8, 5, 2 4 4 1 , 2) と書きます。同様に、固定レベルの配列の場合は、OA( N, k, v, t ) を OA( N, v k , t ) に短縮できます。
この OA 表記法ではインデックス λ は明示的に含まれていませんが、λ は関係式N = λ v tを介して他のパラメータから復元できます。これは、パラメータがすべて特定の数値を持つ場合には有効ですが、直交配列のクラスを意図している場合はあまり有効ではありません。たとえば、強度t = 2、インデックス λ = 1 の配列のクラスを示す場合、表記 OA( N, k, v, 2 ) だけでは λ を決定するには不十分です。これは通常、代わりに OA( v 2 , k, v, 2) と記述することで解決されます。パラメータ λ を明示的に含む表記法ではこの問題は発生しませんが、混合レベルの配列を表すように簡単に拡張することはできません。
OA( N, k, v, t )をN × kではなくk × Nと定義する著者もいます。このような場合、配列の強さは列ではなくt行のサブセットによって定義されます。
接頭辞OAを除けば、表記OA( N, k, v, t )はRaoによって導入されたものと同じである。[ 5 ] この表記法は非常に一般的だが、普遍的ではない。Hedayat、Sloane、Stufken [ 6 ]はこれを標準として推奨しているが、文献に見られる8つの代替表記法を挙げており、他にも存在する。[ 8 ]
OA(16, 5, 4, 2)の例。これは、強度2、4水準、インデックス1、実行回数16回の実験計画です。
OA(27, 5, 3, 2) の例 (見やすくするために転置行列として記述)： [ 9 ]
この例では、インデックスλ = 3です。
vセットのすべてのkタプルから構成され、 kタプルが行になるように配置された配列は、自動的に（ 「自明に」）強度kを持ち、したがって OA( v k , k, v, k ) となります。このような配列は、 vセットのすべてのkタプルを λ 回列挙するだけで簡単に構築できるため、任意の OA( N, k, v, k ) は自明であると考えられます。
OA( n 2 , 3, n , 2) は、次数nのラテン方陣に相当します。k ≤ n +1の場合、OA( n 2 , k, n , 2) は、次数nのk − 2個の互いに直交するラテン方陣の集合に相当します。このようなインデックス 1、強度 2 の直交配列は、統計学の文献ではハイパー グレコ ラテン方陣設計としても知られています。
A を、自然数の集合 {1,..., n } と同一視されるn個の要素の集合上の、強度 2、インデックス 1 の直交配列とします。Aの 2 つの列を、インデックス列と呼ばれる順に選択して固定します。強度が 2 でインデックスが 1 であるため、1 ≤ i , j ≤ n を満たすすべての順序対 ( i , j ) は、インデックス列の行にちょうど 1 回出現します。ここで、iとj は、 n × nの正方形の行と列を順にインデックスします。A の他の任意の列を取り、この正方形の( i , j ) セルを、この列のAと、インデックス列に ( i , j ) が含まれるAの行の両方に含まれるエントリで埋めます。結果として得られる正方形は、n次ラテン方陣です。たとえば、次の OA(9, 4, 3, 2) を考えてみましょう。
インデックス列として3列目と4列目（この順序で）を選択すると、最初の列でラテン方陣が生成されます。
2列目はラテン方陣を生成する
さらに、これら2つの正方形は互いに直交しています。一般に、このようにして直交配列から生成されるラテン方陣は直交ラテン方陣となるため、インデックス列以外のk - 2列は、 k - 2個の互いに直交するラテン方陣 のセットを生成します。
この構成は完全に可逆的であるため、互いに直交するラテン方陣の集合から強度2、指数1の直交配列を構築することができる。[ 10 ]
直交配列は、実験の統計的設計において関心のあるこれらの多様な対象を記述するための統一的な方法を提供する。
前のセクションで述べたように、 n次ラテン方陣はOA( n 2 , 3, n , 2) と考えることができます。実際には、異なる列の任意の順序ペアをインデックス列として使用できるため、直交配列は 6 つのラテン方陣につながります。ただし、これらはすべて同位であり、同等とみなされます。具体的には、常に最初の 2 つの列を自然な順序でインデックス列として使用するものとします。
統計学の文献では、ラテンキューブは、 n層からなるn × n × nの3 次元行列であり、各層はn行n列を持ち、出現するn個の異なる要素がn 2回繰り返され、キューブの 3 組の対向する面のそれぞれに平行な各層で、n個の異なる要素すべてが現れ、各要素がその層でちょうどn回繰り返されるように配置されている。[ 11 ]
この定義では、ラテンキューブの層はラテン方陣である必要はないことに注意してください。実際、行、列、ファイル（異なる層の特定の位置のセル）は、n個の記号の順列である必要はありません。[ 12 ]
n次ラテン立方体はOA( n 3 , 4, n , 2) と同等である。[ 9 ]
n次ラテン立方体の 2 つは、対応するセルから選択されたn 3組の要素のうち、異なる順序の要素のペアがそれぞれちょうどn回出現する場合に直交する。n次ラテン立方体の k − 3 個の相互に直交する集合は、 OA ( n 3 , k, n , 2) と同等である。[ 9 ] 3次ラテン立方体の相互に直交するペアの例は、上記の例のセクションで OA(27, 5, 3, 2) として示されている。
ラテン方陣の場合とは異なり、制約はなく、ラテン立方体の直交配列表現のインデックス列は、OA( n 3 , 3, n , 3)を形成するように選択する必要があります。
次数nのr次クラスの m 次元ラテン超立方体は、n r個の異なる要素を持ち、各要素が n m − r 回繰り返され、各要素がn個の平行な( m − 1)次元線形部分空間 (または「層」) のmセットのそれぞれにちょうどn m − r − 1回出現するようなn × n × ... × n m 次元行列である。次数nでクラスr が同じ 2 つのラテン超立方体で、一方を他方に重ね合わせたときに、一方のすべての要素が他方のすべての要素とちょうどn m − 2 r回出現するという性質を持つものは、直交していると言われる。[ 13 ]
次数nの互いに直交するk − m 個のm次元ラテン超立方体の集合はOA( n m , k, n, 2) と同等であり、インデックス列は OA( n m , m, n, m ) を形成します。
ラテン方陣と相互直交ラテン方陣の概念は、 Kishen (1942)によってラテン立方体と超立方体、直交ラテン立方体と超立方体に一般化された。[ 14 ] Rao (1946)はこれらの結果を強度tの配列に一般化した。伝説的な科学者CR Raoによるこれらのアイデアの一般化としての直交配列の現在の概念はRao (1947)に登場し、[ 15 ] 1973 年に混合レベル配列への一般化が発表された。[ 16 ]
Rao は当初、「配列」という用語を修飾語なしで使用し、それを単にすべての治療組み合わせの部分集合、つまり単純な配列と定義しました。治療組み合わせを行列の行にすると、非単純な配列の可能性が自然に生じました。Hedayat、Sloane、および Stufken [ 17 ]は、「直交配列」という用語をK. Bush [ 18 ]に帰しています。
OA( 4λ, 4λ − 1, 2, 2) が存在するのは、 4λ次数のアダマール行列 が存在する場合に限る。[ 19 ] 一方の方向に進むために、H を標準化された形式 (最初の行と列の要素がすべて +1) の4m次数のアダマール行列とする。最初の行を削除し、転置して目的の直交配列を得る。[ 20 ]次の例がこれを示している。(逆の構成も同様である。)
下記の8次標準化アダマール行列（±1エントリは符号のみで示されている）
OA(8, 7, 2, 2)を生成する：[ 21 ]
1列目、2列目、4列目をインデックス列として使用すると、残りの列から次数2の互いに直交する4つのラテン立方体が生成されます。
C ⊆ ( F q ) nを最小距離dを持つ次元mの線形コードとする。このとき、C ⊥ (ベクトル部分空間Cの直交補空間) は (線形) OA( q n-m , n, q, d − 1)であり、λ = q n − m − d + 1である。[ 22 ]
秘密分散（秘密分割とも呼ばれる）とは、秘密を参加者グループに分配する方法であり、各参加者には秘密の一部が割り当てられます。秘密は、種類が異なる場合もある十分な数の共有された秘密が組み合わされた場合にのみ復元可能であり、個々の共有された秘密は単独では何の役にも立ちません。秘密分散方式が完全であるのは、秘密を取得するための基準を満たさない参加者の集合が、秘密を共有していない個人よりも秘密について追加の知識を持たない場合です。
ある種の秘密分散方式では、ディーラーが1人、プレイヤーがn 人います。ディーラーは秘密の断片をプレイヤーに分配しますが、特定の条件が満たされた場合にのみ、プレイヤーは秘密を復元できます。ディーラーは、t人（閾値）以上のプレイヤーのグループであれば秘密を復元できますが、 t人未満のグループでは復元できないように、各プレイヤーに断片を分配します。このようなシステムは、（t , n）閾値方式と呼ばれます。
OA( v t , n+1, v, t ) は、完全な ( t , n )-閾値スキームを構築するために使用できます。[ 23 ]
要因実験は、複数の要因（灌水レベル、抗生物質、肥料など）を各実験単位に有限個のレベルで適用する統計的に構造化された実験であり、レベルは定量的または定性的である可能性がある。[ 24 ]完全要因実験では、要因のレベルのすべての組み合わせをテストする必要があります。部分要因計画では、処理の組み合わせのサブセットのみが使用されます。
直交配列は、一部実施要因実験の設計に使用できます。列はさまざまな要因を表し、エントリは要因が観測される水準を表します。実験ランは直交配列の行、つまり要因水準の特定の組み合わせです。配列の強度は、一部実施要因設計の分解能を決定します。これらの設計のいずれかを使用する場合、処理単位と試行順序は、設計が許容する限りランダム化する必要があります。たとえば、適切なサイズの直交配列を利用可能なものからランダムに選択し、次に実行順序をランダム化することが推奨されます。
混合水準デザインは、統計学の分野では自然に発生する。
直交配列は、1950年代初頭に田口玄一がインド統計研究所を訪れた際に田口メソッドが開発された際に中心的な役割を果たしました。彼のメソッドは日本とインドの産業界で成功裏に適用され採用され、その後、いくつかの留保付きではあるものの米国産業界にも受け入れられました。田口のカタログ[ 25 ]には、固定レベル配列と混合レベル配列の両方が含まれています。
直交配列テストは、ソフトウェアテストの体系的かつ統計的な方法であるブラックボックステスト手法です。[ 26 ] [ 27 ]システムへの入力数が比較的少ないが、システムへのすべての可能な入力を網羅的にテストするには多すぎる場合に使用されます。 [ 26 ]コンピュータソフトウェアシステム内の欠陥のあるロジックに関連するエラーを見つけるのに特に効果的です。[ 26 ]直交配列は、ユーザーインターフェイステスト、システムテスト、回帰テスト、およびパフォーマンス テストに適用できます。単一の処理を構成する因子レベルの順列は、応答が相関しないように選択され、したがって各処理は固有の情報を提供します。このような処理で実験を編成することによる正味の効果は、同じ情報が最小限の実験数で収集されることです。
ソフトウェアおよびシステムテストに直交配列を利用することに関する多数の記事。
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
この記事には、米国国立標準技術研究所（NIST）のパブリックドメイン資料が含まれています。