決定木モデル

計算複雑性理論において、決定木モデルは、アルゴリズムを決定木、つまり適応的に実行される一連のクエリまたはテストと見なすことができる計算モデルであり、以前のテストの結果が次に実行されるテストに影響を与える可能性があります。

通常、これらのテストは結果の数が少なく（はい/いいえの質問など）、迅速に実行できるため（つまり、単位計算コストで）、決定木モデル内のアルゴリズムの最悪の場合の時間計算量は、対応するツリーの深さに対応します。決定木モデルの問題またはアルゴリズムの計算計算量の概念は、決定木計算量またはクエリ計算量と呼ばれます。

決定木モデルは、特定のクラスの計算問題とアルゴリズムの複雑さの下限を確立するのに役立ちます。計算モデルと実行できるクエリ アルゴリズムの種類に応じて、決定木モデルのいくつかのバリエーションが導入されています。

たとえば、決定木の議論は、項目の比較ソートでは比較を行う必要があることを示すために使用されます。比較ソートの場合、クエリは 2 つの項目の比較であり、結果はまたは の2 つになります (どの項目も等しくないと仮定) 。比較ソートは、このモデルでは決定木として表現できます。このようなソート アルゴリズムは、このような種類のクエリのみを実行するためです。 ${\displaystyle n}$${\displaystyle n\log(n)}$${\displaystyle a,b}$${\displaystyle a<b}$${\displaystyle a>b}$

決定木はソートやその他の同様の問題のアルゴリズムを理解するためによく使用されます。これはフォードとジョンソンによって最初に行われました。^[1]

たとえば、多くのソート アルゴリズムは比較ソートです。つまり、、 、 のいずれであるかをテストするローカル比較を通じてのみ、入力シーケンスに関する情報を取得します。ソートされる項目がすべて異なっており比較可能であると仮定すると、これは「 ですか?」 か「いいえ」の質問として言い換えることができます。${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$${\displaystyle x_{i}$${\displaystyle x_{i}=x_{j}}$${\displaystyle x_{i}>x_{j}}$${\displaystyle x_{i}>x_{j}}$

これらのアルゴリズムは、クエリが比較であるバイナリ決定木としてモデル化できます。つまり、内部ノードはクエリに対応し、ノードの子は、質問の答えが「はい」または「いいえ」の場合の次のクエリに対応します。リーフノードの場合、出力は、入力シーケンスが完全に順序付けられた項目のリストからどのようにスクランブルされたかを説明する順列 に対応します。(この順列の逆である は、入力シーケンスを並べ替えます。) ${\displaystyle \pi}$${\displaystyle \pi^{-1}}$

比較ソートでは比較を使わなければならないことは、単純な議論で示せる。アルゴリズムが正しいためには、要素のあらゆる可能な順列を出力できなければならない。そうでなければ、その特定の順列を入力としてアルゴリズムが失敗する。したがって、対応する決定木には、順列の数と同じ数の葉が少なくともなければならない。葉。少なくとも 個の葉を持つ二分木は、深さが少なくとも 個であるため、これが比較ソートアルゴリズムの実行時間の下限となる。この場合、マージソートやヒープソートなど、この時間計算量を持つ比較ソートアルゴリズムが多数存在することは、この下限が厳しいことを示している。^{[2] : 91}${\displaystyle \Omega (n\log(n))}$${\displaystyle n}$${\displaystyle n!}$${\displaystyle n!}$${\displaystyle \log _{2}(n!)=\オメガ (n\log _{2}(n))}$

この議論はクエリの種類については何も使用しないため、実際にはバイナリ決定木としてモデル化できるソート アルゴリズムの下限を証明しています。本質的には、これは、正しいソート アルゴリズムは入力シーケンスに関する少なくともビットの情報を学習する必要があるという情報理論の議論を言い換えたものです。結果として、これはランダム化された決定木にも適用できます。 ${\displaystyle \log_{2}(n!)}$

他の決定木の下限では、クエリが比較であることを使用します。たとえば、比較のみを使用して数値の中で最小の数値を見つけるタスクを考えてみましょう。最小の数値を決定する前に、最小の数値以外のすべての数値が少なくとも 1 回の比較で「負ける」(大きい数値と比較する) 必要があります。したがって、最小値を見つけるには少なくとも 回の比較が必要です。(ここでの情報理論的議論は、 の下限のみを示します。) 同様の議論は、順序統計を計算するための一般的な下限にも適用されます。^{[2] : 214}${\displaystyle n}$${\displaystyle n-1}$${\displaystyle \log(n)}$

線形決定木は、上記の比較決定木を、実数ベクトルを 入力として受け取る関数を計算するように一般化します。線形決定木のテストは線形関数です。つまり、特定の実数 に対して、 の符号を出力します。(このモデルのアルゴリズムは、出力の符号にのみ依存します。) と の比較は線形関数 に対応するため、比較木は線形決定木です。定義から、線形決定木は、半空間の和集合と積集合を取ることによってファイバーを構築できる関数のみを指定できます。 ${\displaystyle x\in \mathbb {R} ^{n}}$${\displaystyle a_{0},\dots ,a_{n}}$${\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}-x_{j}}$${\displaystyle f}$

代数決定木は、テスト関数を次数の多項式にすることができる線形決定木の一般化です。幾何学的には、空間は半代数集合（超平面の一般化）に分割されます。 ${\displaystyle d}$

^ラビン[3]とラインゴールド^[4]によって定義されたこれらの決定木モデルは、計算幾何学における下限を証明するためによく使用されます。^[5]たとえば、ベン・オールは、要素の一意性（ を計算するタスク、ただし となる異なる座標が存在する場合に限り が 0 となる）には、深さ の代数決定木が必要であることを示しました。^[6]これは、ドブキンとリプトンによって線形決定モデルに対して初めて示されました。^[7]彼らはまた、ナップサック問題における線形決定木の下限を示しており、スティールとヤオによって代数決定木に一般化されました。^[8]${\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}}$${\displaystyle f(x)}$${\displaystyle i,j}$${\displaystyle x_{i}=x_{j}}$${\displaystyle \Omega (n\log(n))}$${\displaystyle n^{2}}$

ブール決定木の場合、タスクは入力 に対するn ビットのブール関数 の値を計算することです。クエリは入力 のビットの読み取りに対応し、出力は です。各クエリは、以前のクエリに依存している可能性があります。決定木を使用する計算モデルには多くの種類があり、複雑性尺度と呼ばれる複数の複雑性の概念が認められています。 ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle x_{i}}$${\displaystyle f(x)}$

決定木の出力が の場合、すべての に対して、決定木は を「計算する」と言われます。 木の深さは、葉に到達して結果が得られるまでに実行できるクエリの最大数です。 の場合、の決定木複雑度は、を計算するすべての決定木の中で最小の深さです。 ${\displaystyle f(x)}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle f}$${\displaystyle D(f)}$${\displaystyle f}$${\displaystyle f}$

ランダム化決定木を定義する 1 つの方法は、各ノードを確率 で制御する追加のノードをツリーに追加することです。もう 1 つの同等の定義は、決定論的決定木上の分布として定義することです。この 2 番目の定義に基づくと、ランダム化ツリーの複雑さは、基礎となる分布のサポート内のすべてのツリーの中で最大の深さとして定義されます。 は、結果が少なくともすべてに対して確率 である(つまり、制限された両側誤差を持つ) 最も深さの低いランダム化決定木の複雑さとして定義されます。${\displaystyle p_{i}}$${\displaystyle R_{2}(f)}$${\displaystyle f(x)}$${\displaystyle 2/3}$${\displaystyle x\in \{0,1\}^{n}}$

${\displaystyle R_{2}(f)}$は、両側誤差が制限された誤った結果が許されるため、モンテカルロランダム決定木の複雑度として知られています。ラスベガス決定木の複雑度は、正しいはずの（つまり、誤差がゼロの）決定木の予想される深さを測定します。 で表される片側誤差制限バージョンもあります。 ${\displaystyle R_{0}(f)}$${\displaystyle R_{1}(f)}$

関数の非決定論的決定木の複雑さは、その関数の証明書の複雑さとしてよく知られています。これは、関数を確実に評価するために 非決定論的アルゴリズムが確認する必要がある入力ビットの数を測定します。

正式には、における の証明書の複雑さは、すべての に対して であれば となるようなインデックスの最小のサブセットのサイズです。 の証明書の複雑さは、すべての にわたる最大の証明書の複雑さです。検証者が 2/3 の確率で正しいことだけを要求する類似の概念は と表されます。 ${\displaystyle f}$${\displaystyle x}$${\displaystyle S\subset [n]}$${\displaystyle y\in \{0,1\}^{n}}$${\displaystyle y_{i}=x_{i}}$${\displaystyle i\in S}$${\displaystyle f(y)=f(x)}$${\displaystyle f}$${\displaystyle x}$${\displaystyle RC(f)}$

量子決定木の複雑度は、すべての に対して少なくとも の確率で結果を返す、最も深さの低い量子決定木の深さです。もう 1 つの量 は、すべての場合に確率 1 で結果を返す (つまり、 を正確に計算する)、 最も深さの低い量子決定木の深さとして定義されます。および は、量子決定木の直接的な定義が古典的な場合よりも複雑であるため、より一般的には量子クエリ複雑度として知られています。ランダム化の場合と同様に、および を定義します。 ${\displaystyle Q_{2}(f)}$${\displaystyle f(x)}$${\displaystyle 2/3}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle Q_{E}(f)}$${\displaystyle f(x)}$${\displaystyle f}$${\displaystyle Q_{2}(f)}$${\displaystyle Q_{E}(f)}$${\displaystyle Q_{0}(f)}$${\displaystyle Q_{1}(f)}$

これらの概念は、通常、次数と近似次数の概念によって制限されます。の次数( と表記) は、すべてのに対して を満たす任意の多項式の最小次数です。の近似次数 (と表記)は、 および のときはいつでもを満たす任意の多項式の最小次数です。 ${\displaystyle f}$${\displaystyle \deg(f)}$${\displaystyle p}$${\displaystyle f(x)=p(x)}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle f}$${\displaystyle {\widetilde {\deg }}(f)}$${\displaystyle p}$${\displaystyle p(x)\in [0,1/3]}$${\displaystyle f(x)=0}$${\displaystyle p(x)\in [2/3,1]}$${\displaystyle f(x)=1}$

Bealsらは、およびを確立した。^[9]${\displaystyle Q_{0}(f)\geq \deg(f)/2}$${\displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}$

定義から、すべての- ビット ブール関数、、およびについて、 が成り立つことが直ちにわかります。逆方向の最適な上限を見つけることは、クエリの複雑さの分野における主要な目標です。 ${\displaystyle n}$${\displaystyle f}$${\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}$${\displaystyle Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n}$

これらすべての種類のクエリ複雑度は多項式で関係している。Blum と Impagliazzo、^[10] Hartmanis と Hemachandra、^[11] Tardos ^{[12] は}それぞれ独立に を発見した。Noam Nisan は、モンテ カルロ ランダム決定木の複雑度も決定論的決定木の複雑度と多項式で関係していることを発見した: 。^[13] (Nisan は であることも示した。) モンテ カルロ モデルとラスベガス モデルの間にはより密接な関係があることがわかっている: 。^[14]この関係は、多重対数因数まで最適である。^[15]量子決定木の複雑度に関しては、であり、この境界は密である。^{[16] [15]} Midrijanis は であることを示した。^{[17] [18]}これは Beals らによる 4 次境界を改善している。^[9]${\displaystyle D(f)\leq R_{0}(f)^{2}}$${\displaystyle D(f)=O(R_{2}(f)^{3})}$${\displaystyle D(f)=O(R_{1}(f)^{2})}$${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$${\displaystyle D(f)=O(Q_{2}(f)^{4})}$${\displaystyle D(f)=O(Q_{0}(f)^{3})}$

これらの多項式関係は、全ブール関数に対してのみ有効であることに注意することが重要です。のサブセットを定義域とする部分ブール関数の場合、と の間に指数分離が発生する可能性があります。このような問題の最初の例は、Deutsch と Jozsaによって発見されました。 ${\displaystyle \{0,1\}^{n}}$${\displaystyle Q_{0}(f)}$${\displaystyle D(f)}$

ブール関数 の場合、の感度は全体にわたるの最大感度として定義されます。ここで、におけるの感度は、の値を変更するにおける 1 ビットの変更の数です。感度は、ブール関数 の解析からの全影響の概念に関連しており、全体にわたる平均感度に等しくなります。 ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle x}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle x}$

感度予想とは、感度がクエリの複雑さと多項式的に関係しているという予想です。つまり、すべての、およびに対して、 となる指数が存在します。簡単な議論で であることが示せるため、この予想は特に感度の下限を見つけることに関係しています。これまでに説明した複雑さの尺度はすべて多項式的に関係しているため、複雑さの尺度の正確なタイプは関係ありません。ただし、これは通常、感度とブロックの感度の関係に関する質問として表現されます。 ${\displaystyle c,c'}$${\displaystyle f}$${\displaystyle D(f)=O(s(f)^{c})}$${\displaystyle s(f)=O(D(f)^{c'})}$${\displaystyle s(f)\leq D(f)}$

のブロック感度は と表記され、全体にわたるの最大のブロック感度として定義されます。におけるのブロック感度は、任意のサブセット について、に対応するのビットを反転するとの値が変化するような、互いに素なサブセットの最大数です。^[13]${\displaystyle f}$${\displaystyle bs(f)}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle x}$${\displaystyle t}$${\displaystyle S_{1},\ldots ,S_{t}\subset [n]}$${\displaystyle S_{i}}$${\displaystyle x}$${\displaystyle S_{i}}$${\displaystyle f(x)}$

2019年、ハオ・ホアンは感度予想を証明し、次のことを示しました。^{[19] [20]}${\displaystyle bs(f)=O(s(f)^{4})}$

• 比較ソート
• 決定木
• アデラー・カープ・ローゼンバーグ予想
• 最小全域木 § 決定木

• Buhrman, Harry; de Wolf, Ronald (2002)、「複雑性測定と決定木の複雑性: 調査」(PDF)、理論計算機科学、288 (1): 21– 43、doi : 10.1016/S0304-3975(01)00144-X