決定木モデル

Model of computational complexity

決定木モデル

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

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

決定木モデルは、特定の種類の計算問題やアルゴリズムの複雑さの下限を設定するのに役立ちます。計算モデルと実行可能なクエリアルゴリズムの種類に応じて、いくつかの種類の決定木モデルが導入されています。

例えば、決定木の議論は、アイテムの比較ソートでは必ず比較が行われることを示すために使用されます。比較ソートの場合、クエリは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}<x_{j}}$ ${\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!)=\Omega (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}$

ランダム化決定木

ランダム化決定木を定義する一つの方法は、各ノードを確率 で制御する追加ノードを木に追加する方法です。もう一つの同等の定義は、決定論的決定木上の分布として定義することです。この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\subseteq [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で結果を返す（つまり、 を正確に計算する） 最も深さの低い量子決定木の深さとして定義されます。およびは、量子決定木の直接的な定義が古典的な場合よりも複雑であるため、より一般的には量子クエリ複雑度として知られています。ランダム化の場合と同様に、およびを定義します。 ${\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 ら[9]}による 4 次上限を改善している。 ${\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)}$

感度予想

ブール関数 の場合、の感度は全体にわたるの最大感度と定義されます。ここで、におけるの感度は、の値を変えるにおける単一ビットの変化の数です。感度は、ブール関数 の解析から得られる総影響の概念と関連しており、これは全体にわたる平均感度に等しくなります。 ${\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}\subseteq [n]}$ ${\displaystyle S_{i}}$ ${\displaystyle x}$ ${\displaystyle S_{i}}$ ${\displaystyle f(x)}$

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

参照

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

参考文献

1. フォード, レスター・R・ジュニア; ジョンソン, セルマー・M. (1959年5月1日). 「トーナメント問題」 .アメリカ数学月刊誌. 66 (5): 387– 389. doi :10.1080/00029890.1959.11989306. ISSN  0002-9890.
2. アルゴリズム入門. コーメン, トーマス・H. (第3版). ケンブリッジ, マサチューセッツ州: MIT 出版. 2009. ISBN 978-0-262-27083-0. OCLC  676697295。{{cite book}}: CS1 maint: others (link)
3. ラビン, マイケル・O. (1972年12月1日). 「線型形式の同時正値性の証明」.コンピュータとシステム科学ジャーナル. 6 (6): 639– 650. doi : 10.1016/S0022-0000(72)80034-5 . ISSN  0022-0000.
4. ラインゴールド, エドワード M. (1972-10-01). 「いくつかの集合アルゴリズムの最適性について」. Journal of the ACM . 19 (4): 649– 659. doi : 10.1145/321724.321730 . ISSN  0004-5411. S2CID  18605212.
5. Preparata, Franco P. (1985).計算幾何学入門. Shamos, Michael Ian. ニューヨーク: Springer-Verlag. ISBN 0-387-96131-3. OCLC  11970840。
6. ベン＝オー、マイケル (1983年12月1日). 「代数的計算木の下限値」.第15回ACM計算理論シンポジウム議事録 - STOC '83 . ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  80– 86. doi : 10.1145/800061.808735 . ISBN 978-0-89791-099-6. S2CID  1499957。
7. Dobkin, David; Lipton, Richard J. (1976-06-01). 「多次元探索問題」 . SIAM Journal on Computing . 5 (2): 181– 186. doi :10.1137/0205015. ISSN  0097-5397.
8. Michael Steele, J; Yao, Andrew C (1982-03-01). 「代数的決定木の下限値」 . Journal of Algorithms . 3 (1): 1– 8. doi :10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
9. Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). 「多項式による量子下限値」. Journal of the ACM . 48 (4): 778– 797. arXiv : quant-ph/9802049 . doi :10.1145/502090.502097. S2CID  1078168.
10. Blum, M.; Impagliazzo, R. (1987). 「ジェネリックオラクルとオラクルクラス」. Proceedings of 18th IEEE FOCS . pp.  118– 126.
11. Hartmanis, J.; Hemachandra, L. (1987)、「NP完全集合の一方向性関数、堅牢性、非同型性」、技術報告書 DCS TR86-796、コーネル大学
12. Tardos, G. (1989). 「クエリの複雑さ、あるいはランダムオラクルAによってNP A∩coNP A^をP  A から^分離することがなぜ難しいのか？」Combinatorica . 9 (4): 385– 392. doi :10.1007/BF02125350. S2CID  45372592.
13. Nisan, N. (1989). 「CREW PRAMと決定木」.第21回ACM STOC会議録. pp.  327– 335.
14. Kulkarni, R. および Tal, A. 分数ブロック感度について. 計算複雑性に関する電子コロキウム (ECCC). 第20巻. 2013年.
15. アンバイニス、アンドリス;バロディス、カスパール。ベロフス、アレクサンドルス。リー、トロイ。サンサ、ミクロス。スモトトロフス、ジュリス (2017-09-04)。 「ポインタ関数に基づくクエリの複雑さの分離」。ACM のジャーナル。64 (5): 32:1–32:24。arXiv : 1506.04719。土井：10.1145/3106234。ISSN  0004-5411。S2CID  10214557。
16. Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2020-10-23). 「次数と近似次数、そしてHuangの感度定理の量子的意味合い」arXiv : 2010.12629 [quant-ph].
17. Midrijanis, Gatis (2004)、「全ブール関数の正確な量子クエリ複雑度」、arXiv : quant-ph/0403168
18. Midrijanis, Gatis (2005)、「ランダム化および量子クエリ複雑性について」、arXiv : quant-ph/0501142
19. Huang, Hao (2019). 「超立方体の誘導部分グラフと感度予想の証明」Annals of Mathematics . 190 (3): 949– 955. arXiv : 1907.00847 . doi :10.4007/annals.2019.190.3.6. ISSN  0003-486X. JSTOR  10.4007/annals.2019.190.3.6. S2CID  195767594.
20. Klarreich, Erica (2019年7月25日). 「数十年前のコンピュータサイエンスの予想が2ページで解決」. Quanta Magazine . 2019年7月26日閲覧。

調査

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Decision_tree_model&oldid=1323415418"