Эмпирические результаты в статьях CS

31

Я новичок в области CS и заметил, что во многих прочитанных мной документах нет эмпирических результатов (нет кода, только леммы и доказательства). Почему это? Учитывая, что информатика - это наука, разве она не должна следовать научному методу?

тото
источник
26
Короткий ответ: «информатика» - это много вещей. Некоторые части, такие как (некоторые) ИИ, на самом деле являются наукой. Другие части являются инженерными, и теоретическая сторона (прикладная) математика. Части HCI больше похожи на искусство. Информатика - это широкая палатка.
Аарон Рот
6
Если у вас есть доказательства, зачем вам даже эмпирические результаты?
Арьябхата
2
@ Морон: Как вы можете доказать, что алгоритм реализуем без его реализации?
Юкка Суомела
8
Теоретическая CS, похоже, похожа на математическую физику, которая также избегает эмпирических результатов. Если вы хотите что-то вроде экспериментальной физики, вы можете взглянуть на исследования в области программной инженерии, верификации программ, систем баз данных и т. Д.
Ярослав Булатов,
4
придирки: « научный метод»?
Каве

Ответы:

21

Математика - это тоже наука, и вам придется долго искать, чтобы найти опубликованные эмпирические результаты в этой области (хотя, я думаю, они должны быть). Существуют и другие научные области, в которых «леммы и доказательства» ценятся за опыт, например квантовая физика. Тем не менее, большинство наук сочетают теорию и практику (с различными соотношениями), и информатика не является исключением.

Информатика имеет свои корни в математике (см. Биографию Тьюринга, например, http://en.wikipedia.org/wiki/Alan_Turing ), и поэтому многие результаты (обычно называемые как в области «теоретической информатики») состоят из доказательств что компьютеры в некоторой вычислительной модели могут решить некоторую проблему в заданном количестве операций (например, конференции, такие как FOCS, STOC, SODA, SoCG и т. д.). Тем не менее, многие другие результаты информатики касаются применимости этих теорий к практической жизни посредством анализа экспериментальных результатов (например, таких конференций, как WADS, ALENEX и т. Д.).

Часто полагают, что идеал - это хороший баланс между теорией и практикой, как в «Естествознании», где наблюдение за экспериментами побуждает к генерации новых теорий, которые, в свою очередь, предлагают новые эксперименты, чтобы подтвердить или опровергнуть те из них, как и многие другие. конференции пытаются принять как экспериментальные, так и теоретические результаты (например, ESA, ICALP, LATIN, CPM, ISAAC и т. д.). Подполе «Алгоритмы и структуры данных» в информатике может страдать от дисбаланса в том смысле, что «теоретические» конференции обычно имеют более высокий рейтинг, чем экспериментальные. Я считаю, что это не так в других областях компьютерной науки, таких как HCI или AI.

Надеюсь, это поможет?

Джереми
источник
Спасибо, это очень помогает. В последнее время меня интересует теория графов, и в статьях, которые я читал, почти ни у одного из них не было кода или экспериментальных результатов. Вот почему я спросил. Когда вы делаете чистую математику, вы не можете получить экспериментальные результаты, поэтому доказательства - это все. Но в теории графов нет ничего сложного в кодировании вашего алгоритма и получении полезных экспериментальных результатов! Давайте возьмем проблему MST. Текущие реализации в отрасли - это Prim / Kruskal и Boruvska, и все же, более мощные алгоритмы описаны в статьях, но они не используются, так как никто никогда не кодировал их.
до
1
NP
1
@ toto Конечно, то, что вы говорите, относится к некоторым проблемам, но для проблемы MST вы можете увидеть результаты (возможно, несколько устаревшие) реализации некоторых мощных алгоритмов в books.google.com/…
Абель Молина,
1
O(n)O(nlogn)
24

Хорошая реализация алгоритмов - это навык, который требует другого набора инструментов, чем просто доказательство теорем. Многие алгоритмы, которые были обнаружены теоретическим сообществом, действительно были реализованы на практике (хотя я хотел бы, чтобы теоретическое сообщество играло более важную роль в этом процессе). Физика не просит тех же исследователей проводить теорию и экспериментировать, хотя ожидается, что две группы общаются. Почему бы вам не ожидать такого же разрыва в информатике?

ДОБАВЛЕНО В РЕДАКТИРОВАНИЕ:

В продолжение моего комментария в ответ на вопрос Суреша о том, что я имел в виду под «ролью» в Bell Labs и AT & T Labs, исследователям алгоритмов было предложено поговорить с людьми, находящимися в разработке. Я сделал не так много, как следовало бы, но я вытащил из этого хотя бы одну статью , и я думаю, что было бы хорошо, если бы в университете было больше общения между людьми в теории и практиками , Это не значит, что я думаю, что каждый, кто придумывает алгоритм, должен его кодировать (даже если он практичен).

С другой стороны, алгоритмы кодирования (или написание кода студентом), которые, по вашему мнению, могут быть практичными, могут быть полезны для их адаптации специалистами-практиками. Рассмотрим один пример. Лемпель и Зив написали две технические статьи в 1977 и 1978 годах о новых алгоритмах сжатия данных. Все их игнорировали. В 1984 году Уэлч написал гораздо менее техническую статью, в которой описан небольшой поворот LZ78, который несколько улучшил его производительность, и дал результаты небольшого исследования, сравнивающего его производительность с другими методами сжатия данных. Он был опубликован в журнале, который читали многие программисты, а алгоритм был представлен несколькими строками псевдокода. Этот метод был быстро адаптирован в ряде мест, что в итоге привело к печально известному спору в области интеллектуальной собственности.

Конечно, один из лучших способов общения исследователей алгоритмов с практикой - это подготовка аспирантов, которые уходят и работают в Google, IBM или других компаниях, и мы уже делаем это. Другой способ - ответить на вопросы практикующего на этом форуме. Надеемся, что мы делаем разумную работу в этом направлении.

Питер Шор
источник
4
То есть, вы говорите, что, хотя в физике не ожидается, что один и тот же человек будет делать оба, в теории CS мы должны делать оба? потому что модели вычислений гораздо ближе к реальности, чем физические модели?
Суреш Венкат
10
Я говорю, что теоретики должны больше разговаривать с практикующими. Если вы посмотрите на историю физики, плохие вещи начнут происходить, когда теоретики перестанут общаться с экспериментаторами. Я действительно думаю, что у нас есть разумное количество общения между этими двумя группами прямо сейчас, но это не мешало бы иметь еще немного.
Питер Шор
3
Я не буду обобщать, но я думаю, что многие исследователи просто не могут кодировать / не любят, и они предпочли бы, чтобы практическая работа была сделана одним из их студентов. Это касается меня и моего наставника.
до
Напряжение, связанное с формальной спецификацией и практическими вычислениями, восходит к истории STEM. Иногда формальные спецификации приводят (фон Неймана «О теории стационарных детонационных волн» [1948] против последующих вычислительных симуляций), а иногда - практические вычисления приводят («Новый американский практический навигатор» Боудича [1807] против Гаусса «Disquisitiones generales circ superficies curvas»). [1827]). Величайшие математики (Гаусс и фон Нейман в приведенных выше примерах) часто объединяли формальные спецификации с практическими вычислениями.
Джон Сидлес
3
История Lempel-Ziv и просмотр постов в StackOverflow только что заставили меня сформулировать очень простую заповедь, которая могла бы помочь теоретикам алгоритмов придумать реализованных практиков: если вы думаете, что ваш алгоритм может быть практичным, поместите псевдокод в свой бумага.
Питер Шор
17

Одна область исследования, которая использует эмпирические методы и методы Теоретической Информатики, является областью, названной "Экспериментальная Алгоритмика" или "Разработка Алгоритма". Как упоминал Крис, высокопроизводительные вычисления в значительной степени зависят от этого, поскольку современные системы имеют сложные проблемы с кешем и задержками, которые нам сложно моделировать.

Герт Бродал и Питер Сандерс являются хорошими примерами исследователей, которые держат ногу как в «доказательной», так и в «эмпирической» сферах.

- Обновление 1/20 / 2013-- Я бы также упомянул отличную презентацию Роберта Седжвика .

Чад Brewbaker
источник
4
И ALENEX, и ESA поощряют работу прикладных алгоритмов, а также существует конференция (SAE) на эту тему.
Суреш Венкат
Что такое SAE? Это TLA не для Google. У вас есть URL для этого?
Питер Бут
5
SAE - это опечатка для SEA, Симпозиум по экспериментальным алгоритмам.
Дэвид Эппштейн
1
Вы также можете выполнять Алгоритм Инжиниринг более строгим образом, то есть дорабатывать теоретические модели, чтобы они соответствовали реальности, но все же проводили точный анализ. Хотя это сложно.
Рафаэль
O(CubeRoot(n))
12

Это зависит от дисциплины, в которой вы находитесь; как утверждает Джереми, существует спектр теории и практики.

Такие темы, как сложность, имеют тенденцию быть взвешенными в сторону теории, так как часто цель состоит в том, чтобы найти границу для пространства или времени выполнения. Реализация алгоритма в C ++ и последующее его выполнение несколько раз не докажут, что проблема является NP-полной.

Как полярная противоположность, высокопроизводительные вычисления (с такими конференциями, как суперкомпьютеры ) являются эмпирическими; Никто никогда не предоставит доказательства публикации HPC, поскольку существует слишком большая изменчивость в отношении иерархии памяти и нагрузки на ядро.

Итак, к тому же вопросу (как долго нужно что-то бегать?) Можно подойти двумя совершенно разными способами, в зависимости от целей, методов, сообщества и т. Д. См. Пример Poul-Henning Kamp « Ты делаешь это неправильно» диссонанс.

chrisaycock
источник
10

В исследованиях языков программирования многие идеи относительно новых конструкций языка программирования или новых механизмов проверки типов основаны на теории (возможно, основанной на практическом опыте, а может и нет). Часто пишут о таких механизмах с формальной / теоретической / концептуальной точки зрения. Это относительно легко сделать. Далее следует первое препятствие: реализация новых конструкций в контексте существующего компилятора и эксперименты с ним с точки зрения эффективности или гибкости. Это тоже относительно легко.

Но можем ли мы тогда сказать, что конструкт программирования представляет собой прогресс в науке программирования? Можно ли сказать, что это облегчает написание программ? Можно ли сказать, что это делает язык программирования лучше?

Ответ - нет. Чтобы ответить на такие вопросы, потребовалась бы правильная эмпирическая оценка, включающая множество опытных программистов за большие промежутки времени. Это исследование вряд ли когда-либо сделано. Единственным судьей о значении языка программирования (и его конструкций) является популярность языка. А для пуристов языка программирования это противоречит тому, что говорят нам наши гипотезы.

Дэйв Кларк
источник
7

Возможно, мне не хватает мотивации для вашего вопроса, но есть много примеров эмпирических результатов, мотивирующих исследования, алгоритмы и другие результаты.

MP3 использует психоакустику для оптимизации алгоритма кодирования человека.

π

В том же духе Бэйли и Борвейн являются большими сторонниками экспериментальной математики. См. «Компьютер как тигель: введение в экспериментальную математику» , «Вычислительные экскурсии в теории чисел» и другие . Можно утверждать, что это более экспериментальная математика, но я бы сказал, что на этом уровне обсуждение различие семантическое.

Фазовые переходы задач NP-Complete - еще одна область, в которой интенсивно используются эмпирические результаты. См Monasson, Zecchina, Киркпатрик, Зельман и ТРОЯНСКИЙ и Гент и Walsh для начала, хотя есть много, много больше (см здесь для краткого обзора).

Хотя не совсем на уровне теоретической информатики и математики, есть обсуждение здесь о том , как в среднем биения случае во время выполнения в UNIX утилита Grep оптимизировали наихудшие алгоритмы так , потому что она опирается на тот факт , что ищет читаемый текст человека (Grep делает как плохое или худшее на файлах со случайными символами в них).

Даже Гаусс использовал экспериментальное доказательство, чтобы выдвинуть свою гипотезу о теореме простого числа.

Добыча данных ( решение Bellkor о премии Netflix для создания лучшей системы рекомендаций) может рассматриваться как теория, полностью основанная на эмпирических данных. Искусственный интеллект (генетические алгоритмы, нейронные сети и т. Д.) В значительной степени опирается на эксперименты. Криптография находится в постоянном напряжении между создателями кода и взломщиками кода. На самом деле я назвал лишь несколько из них, и если вы ослабите свое определение эмпирического, то вы можете создать еще более широкую сеть.

Мои извинения за то, что я так рассеянно отвечаю на ваш вопрос, но я надеюсь, что привел хотя бы несколько полезных примеров.

user834
источник