Wyniki empiryczne w artykułach CS

Jestem nowy w dziedzinie CS i zauważyłem, że w wielu artykułach, które czytam, nie ma wyników empirycznych (bez kodu, tylko lematy i dowody). Dlaczego? Biorąc pod uwagę, że informatyka jest nauką, czy nie powinna podążać za metodą naukową?

Matematyka jest również nauką i trzeba by długo szukać, aby znaleźć opublikowane wyniki badań empirycznych w tej dziedzinie (choć myślę, że muszą być pewne). Istnieją inne dziedziny naukowe, w których „lematy i dowody” są cenione nad doświadczeniem, takie jak fizyka kwantowa. To powiedziawszy, większość nauk łączy teorię i praktykę (z różnymi stosunkami), a informatyka nie jest wyjątkiem.

Informatyka ma swoje korzenie w matematyce (patrz biografia Turinga, na przykład http://en.wikipedia.org/wiki/Alan_Turing ) i jako takie wiele wyników (ogólnie nazwanych tak jak w dziedzinie „teoretycznej informatyki”) składa się z dowodów że komputery w niektórych modelach obliczeniowych mogą rozwiązać pewien problem w danej ilości operacji (np. konferencje takie jak FOCS, STOC, SODA, SoCG itp.). Niemniej jednak wiele innych wyników informatyki dotyczy zastosowania tych teorii w życiu praktycznym poprzez analizę wyników eksperymentalnych (np. Konferencje takie jak WADS, ALENEX itp.).

Często sugeruje się, że ideałem jest dobra równowaga między teorią a praktyką, tak jak w „naukach przyrodniczych”, gdzie obserwacja eksperymentów skłania do generowania nowych teorii, które z kolei sugerują nowe eksperymenty, aby je potwierdzić lub osłabić: tak wielu konferencje próbują zaakceptować zarówno wyniki eksperymentalne, jak i teoretyczne (np. ESA, ICALP, LATIN, CPM, ISAAC itp.). W podpolu „Algorytmy i struktury danych” w informatyce może występować nierównowaga w tym sensie, że konferencje „teoretyczne” są generalnie wyżej oceniane niż konferencje eksperymentalne. Uważam, że nie jest to prawdą w przypadku innych dziedzin informatyki, takich jak HCI lub AI.

Mam nadzieję, że to pomoże?

Właściwe wdrażanie algorytmów to umiejętność, która wymaga innego zestawu narzędzi niż tylko dowodzenie twierdzeń. Wiele algorytmów odkrytych przez społeczność teorii zostało rzeczywiście zaimplementowanych w praktyce (chociaż chciałbym, aby społeczność teorii odgrywała większą rolę w tym procesie). Fizyka nie wymaga od tych samych badaczy teorii i eksperymentów, chociaż oczekuje się, że obie grupy się komunikują. Dlaczego nie powinieneś spodziewać się takiego samego podziału w informatyce?

DODANE W EDYCJI:

Rozwijając mój komentarz w odpowiedzi na pytanie Suresha o tym, co rozumiałem przez „rolę” powyżej, w Bell Labs i AT&T Labs, badaczy algorytmów zachęcano do rozmowy z osobami w fazie rozwoju. Nie zrobiłem tego tak dużo, jak powinienem, ale wyciągnąłem z tego co najmniej jeden artykuł i myślę, że byłoby dobrze dla tej dziedziny, gdyby komunikacja między ludźmi w teorii na uniwersytetach i praktykach była większa . Nie oznacza to, że uważam, że każdy, kto wymyśli algorytm, powinien go kodować (nawet jeśli jest to praktyczne).

Z drugiej strony algorytmy kodowania (lub kodowanie ich przez ucznia), które Twoim zdaniem mogą być praktyczne, mogą być przydatne w dostosowaniu ich przez praktyków. Rozważ jeden przykład. Lempel i Ziv napisali dwa artykuły techniczne w 1977 i 1978 roku na temat nowych algorytmów kompresji danych. Wszyscy je zignorowali. W 1984 r. Welch napisał o wiele mniej techniczny artykuł, który nieco poprawił LZ78, który nieco poprawił jego wydajność, i podał wyniki niewielkiego badania porównującego jego wydajność z innymi metodami kompresji danych. Został opublikowany w czasopiśmie czytanym przez wielu programistów, a algorytm podano w kilku wierszach pseudokodu. Metodę szybko zaadaptowano w wielu miejscach, co ostatecznie doprowadziło do niesławnego sporu dotyczącego własności intelektualnej.

Oczywiście jednym z najlepszych sposobów komunikowania się praktyków przez badaczy algorytmów jest przygotowanie studentów, którzy wyjeżdżają i pracują w Google, IBM lub innych firmach, a my już to robimy. Innym sposobem może być udzielenie odpowiedzi na pytania praktyka na tym forum. Mamy nadzieję, że wykonujemy również rozsądną robotę.

Jednym z obszarów badań wykorzystujących metody empiryczne i metody informatyki teoretycznej jest dziedzina zwana „algorytmem eksperymentalnym” lub „inżynierią algorytmiczną”. Jak wspomniał Chris, obliczenia o wysokiej wydajności w dużej mierze zależą od tego, ponieważ współczesne systemy mają skomplikowane problemy z pamięcią podręczną i opóźnieniami, które trudno nam modelować.

Gerth Brodal i Peter Sanders są dobrymi przykładami badaczy, którzy utrzymują stopę zarówno w sferze „dowodowej”, jak i „empirycznej”.

- Aktualizacja 1/20/2013 - Chciałbym również wspomnieć o świetnej prezentacji Roberta Sedgewicka .

To zależy od dyscypliny, w której się znajdujesz; jak twierdzi Jeremy, istnieje spektrum teorii i praktyki.

Tematy takie jak złożoność zwykle są ważone w stronę teorii, ponieważ często celem jest znalezienie granicy przestrzeni lub środowiska wykonawczego. Wdrożenie algorytmu w C ++, a następnie uruchomienie go kilka razy nie udowodni, że problem jest NP-zupełny.

Przeciwnie, obliczenia o wysokiej wydajności (z konferencjami takimi jak Superkomputer ) są empiryczne; nikt nigdy nie dostarczy dowodu do publikacji HPC, ponieważ istnieje zbyt duża zmienność w odniesieniu do hierarchii pamięci i obciążenia jądra.

Więc do tego, co wydaje się być tym samym pytaniem (jak długo trwa coś?) Można podejść na dwa zupełnie różne sposoby, w zależności od celów, technik, społeczności itp. Zobacz przykład nieprawidłowego działania Poul-Henning Kamp dysonans.

W badaniach języków programowania wiele pomysłów na nowe konstrukcje języka programowania lub nowe mechanizmy sprawdzania typów wynikają z teorii (być może oparte na doświadczeniu w praktyce, a może nie). Często pisze się o takich mechanizmach z perspektywy formalnej / teoretycznej / konceptualnej. To stosunkowo łatwe do zrobienia. Następnie pojawia się pierwsza przeszkoda: wdrażanie nowych konstrukcji w kontekście istniejącego kompilatora i eksperymentowanie z nim pod względem wydajności lub elastyczności. To też jest stosunkowo łatwe.

Ale czy możemy zatem powiedzieć, że konstrukcja programistyczna stanowi postęp w nauce programowania? Czy możemy powiedzieć, że ułatwia pisanie programów? Czy możemy powiedzieć, że poprawia język programowania?

Odpowiedź brzmi nie. Aby odpowiedzieć na tego rodzaju pytania, potrzebna byłaby właściwa ocena empiryczna obejmująca dziesiątki doświadczonych programistów przez długi czas. Badania te rzadko są przeprowadzane. Jedyną oceną wartości języka programowania (i jego konstrukcji) jest popularność tego języka. A dla purystów języków programowania jest to sprzeczne z tym, co mówią nam nasze hipotezy.

Być może brakuje mi motywacji do pytania, ale istnieje wiele przykładów wyników empirycznych motywujących badania, algorytmy i inne wyniki.

MP3 wykorzystuje psychoakustyczny do optymalizacji algorytmu kodowania przez człowieka.

$\pi$

W tej samej linii Bailey i Borwein są wielkimi zwolennikami matematyki eksperymentalnej. Patrz „komputer jako Crucible: Wprowadzenie do matematyki Doświadczalnej” , „obliczeniowa wycieczki w teorii liczb” pośród innych . Można by argumentować, że jest to bardziej eksperymentalna matematyka, ale twierdziłbym, że na tym poziomie rozróżnienie jest semantyczne.

Przejścia fazowe problemów NP-Complete to kolejny obszar, w którym intensywnie wykorzystuje się wyniki empiryczne. Zobacz Monasson, Zecchina, Kirkpatrick, Selman i Troyansky oraz Gent i Walsh na początek, choć istnieje wiele, wiele innych (patrz tutaj dla krótkiej ankiety).

Choć nie całkiem na poziomie teoretycznej informatyki lub matematyki, jest dyskusja tutaj o tym, jak średnie uderzeń przypadek wykonywalne UNIX użytkowego grep jest zoptymalizowany najgorsze algorytmy przypadków, ponieważ opiera się na fakcie, że jest to poszukiwanie człowieka czytelnego tekstu (grep robi jako zły lub najgorsze w plikach zawierających losowe znaki).

Nawet Gauss wykorzystał dowody eksperymentalne, aby sformułować hipotezę o twierdzeniu o liczbach pierwszych.

Eksploracja danych ( rozwiązanie Bellkora do nagrody Netflix w celu stworzenia lepszego systemu rekomendacji) może być argumentowane jako teoria całkowicie oparta na dowodach empirycznych. Sztuczna inteligencja (algorytmy genetyczne, sieci neuronowe itp.) W dużym stopniu opiera się na eksperymentach. Kryptografia nieustannie przesuwa się między twórcami i łamaczami kodów. Naprawdę wymieniłem tylko kilka, a jeśli rozluźnisz swoją definicję empiryczną, możesz rzucić jeszcze szerszą sieć.

Przepraszam, że jestem tak rozproszony w odpowiedzi na twoje pytanie, ale mam nadzieję, że podałem przynajmniej kilka przykładów, które są pomocne.