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:
jest członkiem pewnej klasy funkcji
jest -far z każdej funkcji w klasie .
Zakres funkcji jest czasem wartością logiczną: , ale nie zawsze.
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ą.
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?
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.
źródło
źródło