Model drzewa decyzyjnego - Decision tree model

W złożoności obliczeniowej modelu drzewo decyzyjne jest model obliczeń , w której algorytm jest uważana za w zasadzie drzewo decyzyjne , czyli ciąg zapytań lub badań , które wykonywane są w sposób adaptacyjny, więc wyniki poprzednich badań mogą wpływać test jest wykonywane dalej.

Zazwyczaj testy te mają niewielką liczbę wyników (takich jak pytanie tak-nie) i można je wykonać szybko (powiedzmy, z jednostkowym kosztem obliczeniowym), więc złożoność czasowa najgorszego przypadku algorytmu w modelu drzewa decyzyjnego odpowiada głębokość odpowiedniego drzewa decyzyjnego. To pojęcie złożoności obliczeniowej problemu lub algorytmu w modelu drzewa decyzyjnego nazywa się jego złożonością drzewa decyzyjnego lub złożonością zapytania .

Model decyzyjny drzewa są instrumentalne w tworzeniu dolnych granic dla teorii złożoności dla pewnych klas problemów obliczeniowych i algorytmów. Wprowadzono kilka wariantów modeli drzew decyzyjnych, w zależności od modelu obliczeniowego i typu algorytmów zapytań, które mogą być wykonywane.

Na przykład drzewo decyzyjne argumentem jest używany, aby pokazać, że porównanie sort z elementów musi podjąć porównań. W przypadku sortowania porównawczego zapytanie jest porównaniem dwóch elementów , z dwoma wynikami (przy założeniu, że żadne elementy nie są równe): albo lub . W tym modelu sortowania porównawcze mogą być wyrażone jako drzewo decyzyjne, ponieważ takie algorytmy sortowania wykonują tylko tego typu zapytania. ${\ Displaystyle n}$${\displaystyle n\log(n)}$${\displaystyle a\,b}$${\displaystyle a<b}$${\displaystyle a>b}$

Drzewa porównawcze i dolne granice do sortowania

Drzewa decyzyjne są często wykorzystywane do zrozumienia algorytmów sortowania i innych podobnych problemów; po raz pierwszy zrobili to Ford i Johnson.

Na przykład, wiele algorytmów sortowania są rodzaju porównania , co oznacza, że tylko zyskać informacje o sekwencji wejściowej poprzez lokalne porównań: testowanie czy , lub . Zakładając, że wszystkie elementy do posortowania są różne i porównywalne, można to sformułować jako pytanie tak lub nie: jest ? ${\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}}$

Algorytmy te mogą być modelowane jako binarne drzewa decyzyjne, gdzie zapytania są porównaniami: węzeł wewnętrzny odpowiada zapytaniu, a dzieci węzła odpowiadają następnemu zapytaniu, gdy odpowiedź na pytanie brzmi tak lub nie. W przypadku węzłów liści dane wyjściowe odpowiadają permutacji, która opisuje, w jaki sposób sekwencja wejściowa została zaszyfrowana z w pełni uporządkowanej listy elementów. (Odwrotność tej permutacji, , zmienia kolejność sekwencji wejściowej.) ${\displaystyle \pi}$${\ Displaystyle \ pi ^ {-1}}$

Można pokazać, że sortowania porównawcze muszą używać porównań za pomocą prostego argumentu: aby algorytm był poprawny, musi być w stanie wypisać każdą możliwą permutację elementów; w przeciwnym razie algorytm nie powiedzie się dla tej konkretnej permutacji jako danych wejściowych. Tak więc odpowiadające mu drzewo decyzyjne musi mieć co najmniej tyle liści, ile permutacji: liści. Każde drzewo binarne z co najmniej liśćmi ma głębokość co najmniej , więc jest to dolna granica czasu działania algorytmu sortowania porównawczego. W tym przypadku, istnienie licznych porównawczych algorytmów sortowania o złożoności tego czasu, jak mergesort i sortowanie przez kopcowanie , pokazuje, że granica jest napięty. ${\ Displaystyle \ Omega (n \ log (n))}$${\ Displaystyle n}$${\displaystyle n!}$${\displaystyle n!}$${\ Displaystyle \ log _ {2} (n!) = \ Omega (n \ log _ {2} (n))}$

Argument ten nie używa niczego o typie zapytania, więc w rzeczywistości stanowi dolną granicę dowolnego algorytmu sortowania, który można zamodelować jako binarne drzewo decyzyjne. W istocie jest to przeformułowanie argumentu teorii informacji, że poprawny algorytm sortowania musi nauczyć się przynajmniej bitów informacji o sekwencji wejściowej. W rezultacie działa to również w przypadku losowych drzew decyzyjnych. ${\displaystyle \log_{2}(n!)}$

Inne dolne granice drzewa decyzyjnego używają tego, że zapytanie jest porównaniem. Rozważmy na przykład zadanie polegające na używaniu tylko porównań w celu znalezienia najmniejszej liczby spośród liczb. Zanim będzie można określić najmniejszą liczbę, każda liczba z wyjątkiem najmniejszej musi „przegrać” (porównać większą) w co najmniej jednym porównaniu. Tak więc potrzeba przynajmniej porównań, aby znaleźć minimum. (Argument teorii informacji podaje tutaj tylko dolną granicę .) Podobny argument działa dla ogólnych dolnych granic przy obliczaniu statystyk porządkowych . ${\ Displaystyle n}$${\displaystyle n-1}$${\ Displaystyle \ log (n)}$

Liniowe i algebraiczne drzewa decyzyjne

Liniowe drzewa decyzyjne uogólniają powyższe porównania drzew decyzyjnych do funkcji obliczeniowych, które jako dane wejściowe przyjmują wektory rzeczywiste . Testy w liniowych drzewach decyzyjnych są funkcjami liniowymi: dla konkretnego wyboru liczb rzeczywistych , wypisz znak . (Algorytmy w tym modelu mogą zależeć tylko od znaku wyniku). Drzewa porównania są liniowymi drzewami decyzyjnymi, ponieważ porównanie między i odpowiada funkcji liniowej . Liniowe drzewa decyzyjne ze swojej definicji mogą jedynie określać funkcje, których włókna można skonstruować, biorąc sumy i przecięcia półprzestrzeni. ${\ Displaystyle x \ w \ mathbb {R} ^ {n}}$${\displaystyle a_{0},\kropki,a_{n}}$${\ Displaystyle a_ {0}+ \ textstyle \ suma _ {i = 1} ^ {n} a_ {i} x_ {i}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}-x_{j}}$${\displaystyle f}$

Algebraiczne drzewa decyzyjne są uogólnieniem liniowych drzew decyzyjnych, które pozwalają funkcjom testowym być wielomianami stopnia . Geometrycznie przestrzeń podzielona jest na zbiory półalgebraiczne (uogólnienie hiperpłaszczyzny). ${\displaystyle d}$

Te modele drzew decyzyjnych, zdefiniowane przez Rabina i Reingolda, są często używane do dowodzenia dolnych granic w geometrii obliczeniowej . Na przykład Ben-Or wykazał, że unikalność elementu (zadanie obliczania , gdzie wynosi 0 wtedy i tylko wtedy, gdy istnieją odrębne współrzędne, takie jak ) wymaga algebraicznego drzewa decyzyjnego o głębokości . Zostało to po raz pierwszy pokazane dla liniowych modeli decyzyjnych przez Dobkina i Liptona. Pokazują również dolną granicę dla liniowych drzew decyzyjnych w problemie plecakowym, uogólnioną do algebraicznych drzew decyzyjnych przez Steele'a i Yao. ${\ Displaystyle f: \ mathbb {R} ^ {n} \ do \ {0,1 \}}$${\displaystyle f(x)}$${\displaystyle ja,j}$${\ Displaystyle x_ {i} = x_ {j}}$${\ Displaystyle \ Omega (n \ log (n))}$${\displaystyle n^{2}}$

Złożoność drzew decyzyjnych typu Boole'a

W przypadku drzew decyzyjnych typu Boolean zadaniem jest obliczenie wartości n-bitowej funkcji logicznej dla input . Zapytania odpowiadają odczytaniu fragmentu danych wejściowych , a wyjściem jest . Każde zapytanie może zależeć od poprzednich zapytań. Istnieje wiele typów modeli obliczeniowych wykorzystujących drzewa decyzyjne, które można rozważyć, dopuszczając wiele pojęć złożoności, zwanych miarami złożoności . ${\ Displaystyle f: \ {0,1 \} ^ {n} \ do \ {0,1 \}}$${\ Displaystyle x \ w \ {0,1 \} ^ {n}}$${\displaystyle x_{i}}$${\displaystyle f(x)}$

Deterministyczne drzewo decyzyjne

Jeśli wyjściem drzewa decyzyjnego jest , dla wszystkich , mówi się, że drzewo decyzyjne "oblicza" . Głębokość drzewa to maksymalna liczba zapytań, które mogą wystąpić przed osiągnięciem liścia i uzyskaniem wyniku. , złożoność deterministycznego drzewa decyzyjnego jest najmniejszą głębokością spośród wszystkich deterministycznych drzew decyzyjnych . ${\displaystyle f(x)}$${\ Displaystyle x \ w \ {0,1 \} ^ {n}}$${\displaystyle f}$${\ Displaystyle D (f)}$${\displaystyle f}$${\displaystyle f}$

Losowe drzewo decyzyjne

Jednym ze sposobów zdefiniowania losowego drzewa decyzyjnego jest dodanie do drzewa dodatkowych węzłów, z których każdy jest kontrolowany przez prawdopodobieństwo . Inną równoważną definicją jest zdefiniowanie go jako rozkładu nad deterministycznymi drzewami decyzyjnymi. W oparciu o tę drugą definicję, złożoność drzewa randomizowanego jest definiowana jako największa głębokość spośród wszystkich drzew wspierających rozkład bazowy. definiuje się jako złożoność losowego drzewa decyzyjnego o najniższej głębokości, którego wynik jest z prawdopodobieństwem przynajmniej dla wszystkich (tj. z ograniczonym błędem dwustronnym). ${\displaystyle p_{i}}$${\displaystyle R_{2}(f)}$${\displaystyle f(x)}$${\displaystyle 2/3}$${\ Displaystyle x \ w \ {0,1 \} ^ {n}}$

${\displaystyle R_{2}(f)}$jest znany jako złożoność randomizowanego drzewa decyzyjnego Monte Carlo , ponieważ wynik może być niepoprawny z ograniczonym błędem dwustronnym. Las Vegas decyzja drzewa złożoność mierzy oczekiwaną głębokość drzewa decyzyjnego, które muszą być prawidłowe (czyli ma zero błędów). Istnieje również wersja jednostronnego błędu ograniczonego, oznaczona przez . ${\displaystyle R_{0}(f)}$${\displaystyle R_{1}(f)}$

Niedeterministyczne drzewo decyzyjne

Niedeterministyczna złożoność drzewa decyzyjnego funkcji jest powszechnie znana jako złożoność certyfikatu tej funkcji. Mierzy liczbę bitów wejściowych, na które algorytm niedeterministyczny musiałby się przyjrzeć, aby ocenić funkcję z pewnością.

Formalnie złożoność certyfikatu at jest rozmiarem najmniejszego podzbioru indeksów, tak że dla wszystkich , jeśli dla wszystkich , to . Złożoność certyfikatu to maksymalna złożoność certyfikatu . Analogiczne pojęcie, w którym wymaga się jedynie, aby weryfikator był poprawny z prawdopodobieństwem 2/3, jest oznaczane . ${\displaystyle f}$${\displaystyle x}$${\displaystyle S\podzbiór [n]}$${\ Displaystyle y \ w \ {0,1 \} ^ {n}}$${\ Displaystyle y_ {i} = x_ {i}}$${\ Displaystyle i \ w S}$${\ Displaystyle f (y) = f (x)}$${\displaystyle f}$${\displaystyle x}$${\ Displaystyle RC (f)}$

Kwantowe drzewo decyzyjne

Złożoność kwantowego drzewa decyzyjnego to głębokość najmniejszego kwantowego drzewa decyzyjnego, które daje wynik z prawdopodobieństwem przynajmniej dla wszystkich . Inna wielkość, , jest zdefiniowana jako głębokość najmniejszego kwantowego drzewa decyzyjnego, które daje wynik z prawdopodobieństwem 1 we wszystkich przypadkach (tj. oblicza dokładnie). i są powszechnie znane jako kwantowe złożoności zapytań , ponieważ bezpośrednia definicja kwantowego drzewa decyzyjnego jest bardziej skomplikowana niż w przypadku klasycznym. Podobnie jak w przypadku losowym, definiujemy i . ${\displaystyle Q_{2}(f)}$${\displaystyle f(x)}$${\displaystyle 2/3}$${\ Displaystyle x \ w \ {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)}$

Pojęcia te są zazwyczaj ograniczone pojęciami stopnia i przybliżonego stopnia. Stopień z oznaczoną jest najmniejszym stopniu dowolnym wielomianem zgodnej dla wszystkich . Przybliżeniu stopień z oznaczoną jest najmniejszym stopniu dowolnym wielomianem zgodnej gdy i kiedy . ${\displaystyle f}$${\ Displaystyle \ stopnie (f)}$${\displaystyle p}$${\ Displaystyle f (x) = p (x)}$${\ Displaystyle x \ w \ {0,1 \} ^ {n}}$${\displaystyle f}$${\displaystyle {\widetilde {\deg}}(f)}$${\displaystyle p}$${\ Displaystyle p (x) \ w [0,1/3]}$${\ Displaystyle f (x) = 0}$${\displaystyle p(x)\w [2/3,1]}$${\ Displaystyle f (x) = 1}$

Beals i in. ustalił, że i . ${\ Displaystyle Q_ {0}(f) \ geq \ stopni (f)/2}$${\displaystyle Q_{2}(f)\geq {\widetilde {\deg}}(f)/2}$

Związki między miarami złożoności funkcji logicznych bo

Wynika natychmiast z definicji, że dla wszystkich bitowych funkcji logicznych , oraz . Znalezienie najlepszych górnych granic w odwrotnym kierunku jest głównym celem w dziedzinie złożoności zapytań. ${\ Displaystyle n}$${\displaystyle f}$${\ Displaystyle Q_ {2} (f) \ równoważnik R_ {2} (f) \ równoważnik R_ {1} (f) \ równoważnik R_ {0} (f) \ równoważnik D (f) \ równoważnik n}$${\ Displaystyle Q_ {2} (f) \ równoważnik Q_ {0} (f) \ równoważnik D (f) \ równoważnik n}$

Wszystkie te typy złożoności zapytań są powiązane wielomianowo. Blum i Impagliazzo, Hartmanis i Hemachandra oraz Tardos niezależnie odkryli, że ... Noam Nisan odkrył, że złożoność randomizowanego drzewa decyzyjnego Monte Carlo jest również wielomianowo związana ze złożonością deterministycznego drzewa decyzyjnego: . (Nisan również to pokazał .) Ściślejszy związek jest znany między modelami Monte Carlo i Las Vegas: . Ta zależność jest optymalna do czynników polilogarytmicznych. Jeśli chodzi o złożoność kwantowych drzew decyzyjnych , to granica ta jest ścisła. Midrijanis wykazał, że poprawiając wiązanie kwarcowe dzięki Bealsowi i in. ${\ Displaystyle D (f) \ równoważnik 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})}$

Należy zauważyć, że te relacje wielomianowe są poprawne tylko dla funkcji logicznych total . W przypadku częściowych funkcji logicznych , które mają dziedzinę podzbiór , możliwa jest separacja wykładnicza między i ; pierwszy przykład takiego problemu odkryli Deutsch i Jozsa . ${\ Displaystyle \ {0,1 \} ^ {n}}$${\displaystyle Q_{0}(f)}$${\ Displaystyle D (f)}$

Przypuszczenie wrażliwości

Dla logicznego funkcji The wrażliwość na określa się czułość najwyżej w stosunku do wszystkich , w których czułość przy jest wiele zmian pojedynczych bitów w zmieniających wartość . Czułość jest związana z pojęciem całkowitego wpływu z analizy funkcji Boole'a , który jest równy średniej wrażliwości na całość . ${\ Displaystyle f: \ {0,1 \} ^ {n} \ do \ {0,1 \}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle x}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle x}$

Wrażliwość przypuszczenie jest przypuszczenie, że czułość jest wielomianowo związane złożoność zapytań; oznacza to, że istnieje wykładnik taki, że dla wszystkich , i . Można pokazać prostym argumentem, że , więc przypuszczenie dotyczy w szczególności znalezienia dolnej granicy wrażliwości. Ponieważ wszystkie omówione wcześniej miary złożoności są powiązane wielomianowo, dokładny typ miary złożoności nie ma znaczenia. Jest to jednak zwykle sformułowane jako kwestia powiązania wrażliwości z wrażliwością blokową. ${\displaystyle c,c'}$${\displaystyle f}$${\ Displaystyle D (f) = O (s (f) ^ {c})}$${\ Displaystyle s (f) = O (D (f) ^ {c'})}$${\ Displaystyle s (f) \ równoważnik D (f)}$

Wrażliwość blok z oznaczoną , określa się czułość maksymalna bloku w stosunku do wszystkich . Czułość bloku at to maksymalna liczba rozłącznych podzbiorów, tak że dla dowolnego z podzbiorów odwrócenie bitów odpowiadających zmienia wartość . ${\displaystyle f}$${\displaystyle bs(f)}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle x}$${\displaystyle t}$${\displaystyle S_{1},\ldots,S_{t}\podzbiór [n]}$${\displaystyle S_{i}}$${\displaystyle x}$${\displaystyle S_{i}}$${\displaystyle f(x)}$

Ponieważ czułość bloku przyjmuje maksimum w przypadku większej liczby podzbiorów, . Co więcej, wrażliwość bloku jest wielomianowo związana z wcześniej omówionymi miarami złożoności; na przykład artykuł Nisana wprowadzający wrażliwość na bloki pokazał, że . Tak więc, można by przeformułować przypuszczenie czułości jak pokazano, że dla niektórych , . W 1992 roku Nisan i Szegedy doszli do wniosku, że to wystarczy. To byłoby ciasne, ponieważ Rubinstein w 1995 roku wykazał kwadratowy rozdział między wrażliwością a wrażliwością blokową. ${\displaystyle s(f)\leq bs(f)}$${\ Displaystyle bs (f) \ równoważnik D (f) = O (bs (f) ^ {4})}$${\displaystyle c}$${\ Displaystyle bs (f) = O (s (f) ^ {c})}$${\displaystyle c=2}$

W lipcu 2019 r., 27 lat po początkowym przypuszczeniu, Hao Huang z Emory University udowodnił hipotezę wrażliwości, pokazując, że . Dowód ten jest szczególnie zwięzły, udowadniając to stwierdzenie na dwóch stronach, gdy wcześniejszy postęp w kierunku hipotezy wrażliwości był ograniczony. ${\ Displaystyle bs (f) = O (s (f) ^ {4})}$

Podsumowanie znanych wyników

Najbardziej znane separacje dla miar złożoności według stanu na październik 2020 r.

	${\ Displaystyle D}$	${\displaystyle R_{0}}$	${\displaystyle R_{2}}$	${\ Displaystyle C}$	${\ Displaystyle RC}$	${\displaystyle bs}$	${\displaystyle s}$	${\displaystyle Q_{0}}$	${\ Displaystyle \ stopnie}$	${\displaystyle Q}$	${\displaystyle {\widetylda {\stopni}}}$
${\ Displaystyle D}$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
${\displaystyle R_{0}}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
${\ Displaystyle R}$	1	1		2	2, 3	2, 3	3, 6	1,5, 3	2, 3	3, 4	4
${\ Displaystyle C}$	1	1	1, 2		2	2	2,22, 5	1.15, 3	1,63, 3	2, 4	2, 4
${\ Displaystyle RC}$	1	1	1	1		1,5, 2	2, 4	1.15, 2	1,63, 2	2	2
${\displaystyle bs}$	1	1	1	1	1		2, 4	1.15, 2	1,63, 2	2	2
${\displaystyle s}$	1	1	1	1	1	1		1.15, 2	1,63, 2	2	2
${\displaystyle Q_{0}}$	1	1,33, 2	1,33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
${\ Displaystyle \ stopnie}$	1	1,33, 2	1,33, 2	2	2	2	2	1		2	2
${\displaystyle Q}$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
${\displaystyle {\widetylda {\stopni}}}$	1	1	1	2	2	2	2	1	1	1

Ta tabela podsumowuje wyniki dotyczące separacji między miarami złożoności funkcji Boole'a. Miary złożoności to kolejno: deterministyczny, zrandomizowany z zerowym błędem, zrandomizowany z dwustronnym błędem, certyfikat, randomizowany certyfikat, czułość blokowa, czułość, kwant dokładny, stopień, kwant i przybliżony stopień złożoności.

Liczba w -tym wierszu i -tej kolumnie oznacza granice na wykładniku , który jest dolną granicą wszystkich spełniających wszystkie funkcje logiczne . Na przykład wpis w D-tym wierszu i s-tej kolumnie to „3, 6”, więc dla all , a istnieje funkcja taka, że . ${\ Displaystyle A}$${\ Displaystyle B}$${\displaystyle c}$${\displaystyle k}$${\ Displaystyle A (f) = O (B (f) ^ {k})}$${\displaystyle f}$${\ Displaystyle D (f) = O (\ Operator {s} (f) ^ {6 + O (1)})}$${\displaystyle f}$${\displaystyle g}$${\ Displaystyle D (g) = \ Omega (\ nazwa operatora {s} (g) ^ {3-o (1)})}$

Zobacz też

• Sortowanie porównawcze
• Drzewo decyzyjne
• przypuszczenie Aanderaa-Karpa-Rosenberga
• Minimalne drzewo rozpinające#Drzewa decyzyjne

Bibliografia

Ankiety

• Buhrmana, Harry'ego; de Wolf, Ronald (2002), "Miary złożoności i złożoność drzewa decyzyjnego: ankieta" (PDF) , Informatyka teoretyczna , 288 (1): 21-43, doi : 10.1016/S0304-3975(01)00144-X