Wyniki empiryczne w artykułach CS

31

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ą?

Toto
źródło
26
Krótka odpowiedź brzmi: „informatyka” to wiele rzeczy. Niektóre części, takie jak (niektóre) AI, faktycznie są nauką. Pozostałe części to inżynieria, a stroną teoretyczną jest (stosowana) matematyka. Części HCI bardziej przypominają sztukę. Informatyka to szeroki namiot.
Aaron Roth,
6
Jeśli masz dowody, dlaczego potrzebujesz wyników empirycznych?
Aryabhata
2
@ Moron: Jak udowodnić, że algorytm można wdrożyć bez jego wdrożenia?
Jukka Suomela
8
Teoretyczna CS wydaje się być podobna do fizyki matematycznej, która również unika wyników empirycznych. Jeśli chcesz czegoś takiego jak fizyka eksperymentalna, możesz spojrzeć na badania w inżynierii oprogramowania, weryfikacji programu, systemach baz danych itp.
Jarosław Bułatow
4
nitpicking: „ metoda naukowa”?
Kaveh

Odpowiedzi:

21

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?

Jeremy
źródło
Dzięki, to naprawdę bardzo pomaga. Ostatnio interesowałem się teorią grafów i artykułami, które czytałem, prawie żaden z nich nie miał kodu ani wyników eksperymentalnych. Właśnie dlatego zapytałem. Kiedy robisz matematykę, nie możesz uzyskać wyników eksperymentalnych, dlatego dowody są wszystkim. Ale w teorii grafów nie jest tak trudne zakodowanie algorytmu i uzyskanie użytecznych wyników eksperymentalnych! Weźmy problem MST. Obecne wdrożenia branżowe to Prim / Kruskal i Boruvska, a jednak bardziej zaawansowane algorytmy opisano w artykułach, ale nie są one stosowane, ponieważ nikt ich nigdy nie kodował.
toto
1
Tak, możesz zaimplementować algorytmy z teorii grafów. Jednak w przypadku wielu interesujących problemów w teorii grafów, czyli co najmniej twardości , byłoby to bezużyteczne, ponieważ tylko bardzo małe dane wejściowe byłyby (akceptowalne) obliczalne ze względu na złożoność algorytmów wykładniczo-czasowych. N.P.
Mathieu Chapelle,
1
@ toto Z pewnością to, co mówisz, dotyczy niektórych problemów, ale w przypadku problemu MST możesz zobaczyć wyniki (być może nieco nieaktualne) implementacji niektórych potężnych algorytmów w books.google.com/…
Abel Molina
1
@toto. Nie jest to jedyny powód, dla którego stosuje się starsze algorytmy. Dla perspektywy TCS jest zawsze lepsze niż . Ale big-oh może ukryć dużą stałą, która sprawia, że ​​algorytm jest niepraktyczny w praktyce. Taka praca ma na celu ludzi z TCS, a kodowanie algorytmu nie zapewni żadnego zysku, a nawet dezorientuje czytelnika. O(n)O(nlogn)
chazisop
24

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ę.

Peter Shor
źródło
4
Więc mówisz, że chociaż w fizyce nie oczekuje się, że ta sama osoba zrobi obie rzeczy, teoretycznie CS powinniśmy robić obie te rzeczy? czy to dlatego, że modele obliczeń są bardziej zbliżone do rzeczywistości niż modele fizyczne?
Suresh Venkat
10
Mówię, że teoretycy powinni więcej rozmawiać z praktykami. Jeśli spojrzysz na historię fizyki, zaczną się dziać złe rzeczy, gdy teoretycy przestaną rozmawiać z eksperymentalistami. Myślę, że mamy teraz rozsądną komunikację między obiema grupami, ale nie zaszkodzi mieć więcej.
Peter Shor
3
Nie będę generalizować, ale myślę, że wielu badaczy po prostu nie umie kodować / nie lubi i woleliby, aby praktyczna praca została wykonana przez jednego z ich uczniów. Tak jest w przypadku mnie i mojego mentora.
toto
Napięcie związane ze specyfikacją formalną w porównaniu z obliczeniami praktycznymi sięga daleko w przeszłość w STEM. Czasami prowadzi formalne specyfikacje (von Neumanna „O teorii stacjonarnych fal detonacyjnych” [1948] kontra kolejne symulacje obliczeniowe), a czasem praktyczne praktyczne obliczenia (Bowditch „New American Practical Navigator” [1807] kontra Gaussa ”„ Disquisitiones generales circa superficies curvas ” [1827]). Najwięksi matematycy (Gauss i von Neumann w przytoczonych przykładach) często łączą specyfikacje formalne z praktycznymi obliczeniami.
John Sidles
3
Historia Lempel-Ziv i przeglądanie postów na StackOverflow doprowadziły mnie do sformułowania bardzo prostej zasady, która może pomóc w opracowaniu teorii teoretycznych algorytmów zaimplementowanych przez praktyków: jeśli uważasz, że Twój algorytm może być praktyczny, umieść pseudokod w swoim papier.
Peter Shor,
17

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 .

Chad Brewbaker
źródło
4
Zarówno ALENEX, jak i ESA zachęcają do stosowania algorytmów stosowanych, a także na temat tego tematu odbywa się konferencja (SAE).
Suresh Venkat
Co to jest SAE? TLA jest niepodlegająca dyskusji. Czy masz do tego adres URL?
Peter Boothe,
5
SAE to literówka dla SEA, Sympozjum na temat Algorytmów Eksperymentalnych.
David Eppstein,
1
Możesz także wykonać Algorytm Inżynierii w bardziej rygorystyczny sposób, tj. Udoskonalić modele teoretyczne, aby pasowały do ​​rzeczywistości, ale nadal wykonują precyzyjne analizy. Ale to trudne.
Raphael
O(doubmiRoot(n))
12

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.

chrisaycock
źródło
10

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.

Dave Clarke
źródło
7

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.

π

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.

użytkownik834
źródło