Testowanie właściwości w innych metrykach?

20

Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}nR

  1. f jest członkiem pewnej klasy funkcjiC

  2. f jest -far z każdej funkcji w klasie .εC

Zakres funkcji jest czasem wartością logiczną: , ale nie zawsze.RR={0,1}

Tutaj, -far jest ogólnie rozumiany jako odległość Hamminga: ułamek punktów który musiałby zostać zmieniony, aby umieścić w klasie . Jest to naturalna metryka, jeśli ma zakres boolowski, ale wydaje się mniej naturalna, jeśli powiedziano, że zakres ma wartość rzeczywistą.εffCf

Moje pytanie: czy istnieje nić literatury na temat testowania właściwości, która testuje bliskość niektórych klas w odniesieniu do innych metryk?C

Aaron Roth
źródło

Odpowiedzi:

19

Tak jest! Podam trzy przykłady:

  1. Biorąc pod uwagę zbiór S i „tablicę mnożenia” przez S x S, rozważ problem ustalenia, czy dane wejściowe opisują grupę abelową, czy też jest daleka od niej. Friedl, Ivanyos i Santha w STOC '05 pokazał, że nie jest testerem nieruchomość z kwerendy złożoności polylog (| S |), gdy odległość jest miarą stosunku do odległości edycji mnożenia tabel, które umożliwia dodawanie i usuwanie wierszy i kolumn z tabliczka mnożenia. Ten sam problem został również rozważony w modelu odległości Hamminga przez Erguna, Kannana, Kumara, Rubinfelda i Viswanathana (JCSS '00), gdzie wykazali złożoność zapytań O ~ (| S | ^ {3/2}).

  2. Dużo pracy wykonano na testowaniu właściwości wykresów, gdzie wykresy są reprezentowane za pomocą list przyległości, a stopień każdego wierzchołka jest ograniczony. W tym przypadku model odległości nie jest dokładnie odległością Hamminga, ale raczej liczbą krawędzi, które można dodać lub usunąć, zachowując stopień ograniczenia.

  3. W ściśle powiązanym badaniu testowania właściwości rozkładów badano różne pojęcia odległości między rozkładami. W tym modelu dane wejściowe są rozkładem prawdopodobieństwa dla pewnego zestawu, a algorytm uzyskuje do niego dostęp poprzez próbkowanie ze zbioru zgodnie z nieznanym rozkładem. Algorytm jest następnie wymagany do ustalenia, czy rozkład spełnia jakąś właściwość, czy też jest „daleki” od niej. Badano tutaj różne pojęcia odległości, takie jak L_1, L_2, robot ziemny. Badano także rozkłady prawdopodobieństwa w nieskończonych domenach ( Adamaszek-Czumaj-Sohler, SODA '10 ).

arnab
źródło
4
Aby rozwinąć zagadnienie # 1, bardziej naturalnym (IMHO) bardziej naturalnym problemem jest testowanie monotoniczności, gdzie odległość jest liczbą pozycji, które należy obliczyć w permutacji, aby uzyskać monotonię. Zostało to zbadane we wspomnianym powyżej artykule JCSS'00 (prowadzącym do najnowszego artykułu FOCS'10 autorstwa Comandur-Saks).
Alex Andoni
jeśli nie jest to zbyt duży problem, czy możesz połączyć się z odnośnymi dokumentami? najlepiej wersja doi / acm.
Suresh Venkat
7

Zwykle nie jest to nazywane testowaniem właściwości (a tak naprawdę nie jest), ale istnieje duży wysiłek w podejmowaniu decyzji o właściwościach macierzy poprzez spojrzenie na małą, indukowaną nieletnią. Jest to bardzo podobne do celu w testowaniu nieruchomości. Zobacz na przykład artykuł Rudelsona i Vershynina:

http://portal.acm.org/citation.cfm?id=1255449

Istnieją wcześniejsze artykuły Frieze-Kannana. Chodzi o to, że zazwyczaj stosowaną miarą jest pewna norma matrycowa, taka jak norma widmowa, norma Frobeniusa lub norma cięcia. Jeśli chcesz, możesz pomyśleć o niektórych z tych wyników jako algorytmach testowania właściwości w metrykach innych niż odległość Hamminga.

Moritz
źródło
4

f:[n]dRLpp1Lp

Lp

L1L1L1n1


Lp

k

Klemens C.
źródło