Как обмануть сюжетную проверку эвристики?

23

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

При обучении TCS всегда есть студент, который спрашивает: «Зачем мне нужны официальные доказательства, если я могу просто сделать X, который всегда работает?» Его учитель (и) должны указать и проиллюстрировать ошибку. Существует блестящий набор примеров очевидных паттернов, которые в конечном итоге переходят на другой уровень по математике. Но это довольно математические сценарии.

Итак, как вы дурачите сюжетную проверку эвристики? В некоторых случаях трудно различить различия, например

пример пример пример
[ источник ]

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

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

Рафаэль
источник
2
На самом деле, я предложил это в качестве подсказки для понимания проблемы.
Дейв Кларк
@DaveClarke: я знаю; Я использовал вашу первоначальную формулировку просто как провокационный нож. Без обид.
Рафаэль

Ответы:

23

Исходя из опыта, при попытке выяснить скорость роста некоторой наблюдаемой функции (скажем, времени смешивания цепей Маркова или времени работы алгоритма) очень трудно отличить факторы от . Например, очень похоже на :n b O ( (журналN)aNбO(n 0.6 )О(NжурналN)О(N0.6)

сюжет
[ источник ]

Например, в «Некоторых неожиданных ожидаемых результатах поведения для упаковки бинов» Бентли и др. Скорость роста пустого пространства для алгоритмов упаковки бинов Best Fit и First Fit при упаковке предметов, однородных по была оценена эмпирически как и , соответственно. Правильные выражения: и .п 0,6 л 0,7 л 1 / 2 Журнал 3 / 4 п п 2 / 3[0,1]N0.6N0.7N1/2журнал3/4NN2/3

Питер Шор
источник
15

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

ег

Можете ли вы угадать, какая из функций растет (асимптотически) быстрее?

сюжет Ф и Г до 2000 участок f и g до 10000 участок f и g до 200 000

е~г

е(Икс)знак равноИкс2
г(Икс)знак равногрех(журнал(Икс))+1dИксdИксзнак равноИкс2(1-35соз(журнал(Икс))+15грех(журнал(Икс))),

Таким образом, по существу , то есть то же самое, что и , но его вторая производная не является равномерно , но колеблется между и с экспоненциально растущим периодом. Это колебание не видно на обычных графиках.гИкс2е204

В этом примере мы можем демаскировать колебания, рассматривая log-log-plot:

log-log-график f и g до 200 000

Конечно, это не помогает, в целом; например, у нас может быть вдвое экспоненциальный период ...

Себастьян
источник
12

Хорошим примером является глубоко волшебный алгоритм минимального DFA Бжозовского. Для конечного автомата можно вычислить минимальный детерминированный конечный автомат:Nзнак равно(Q,SQ,FQ,рQ×Σ×Q)

MяNямяZе:NFADFAзнак равноDеTермяNяZереvерsеDеTермяNяZереvерsе

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

О(N2)О(Nжурнал(N))

Это касается части «сюжета» «эвристики проверки графика» - мы должны выбрать, какие точки отбирать при рисовании графика, и вы можете обмануть наивный график, если не будете тщательно выбирать точки. Это также верно для других примеров, таких как быстрая сортировка и алгоритм Simplex, но для педагогики я предпочитаю этот алгоритм этим двум.

Разница в быстрой сортировке является «только» квадратичной по сравнению с логарифмической, что является менее впечатляющим, чем разность полиномиальная / экспоненциальная. Симплексный алгоритм имеет столь же впечатляющую разницу, но его анализ значительно сложнее, чем алгоритм Бжозовского.

(Кроме того, я чувствую, что алгоритм минимизации DFA Бжозовского гораздо менее известен, чем заслуживает, но, конечно, это дело вкуса.)

Нил Кришнасвами
источник
Извините, но я не совсем вижу связь с интерпретацией графиков функций.
Рафаэль
3
Я предполагаю, что вы сделаете что-то вроде производительности графика в зависимости от размера экземпляра для выборки экземпляров - и алгоритм Бжозовского будет «выглядеть» полиномом, если вы не выберете экземпляры, чтобы сделать его экспоненциальным по времени.
Нил Кришнасвами
1
Понимаю. Это, безусловно, проблема при сравнении алгоритмов и построении графиков среднего времени выполнения, то есть при построении правильных данных . Когда я задавал вопрос, я думал только о правильной интерпретации сюжета , а это совершенно другой зверь. Можете ли вы добавить эту перспективу в ответ?
Рафаэль
У вас будет одна и та же проблема для всех алгоритмов, которые имеют различное среднее и худшее поведение; На ум приходят быстрые сортировки и симплекс.
Рафаэль
8

Математическая техника подбора кривой может быть использована для предоставления бесконечного количества ответов на ваш вопрос. Учитывая кривую и диапазон, можно легко найти многочлен, который соответствует кривой с любой степенью точности. Этот пример из википедии показывает, как синусоидальная волна может быть достаточно точно согласована с полиномом четвертого порядка (синяя кривая).

введите описание изображения здесь

Я мог бы использовать полиномы более высокого порядка и обмануть эвристику проверки графика даже лучше, чем этот график.

Дэйв Кларк
источник
2
Это правда. У этого также есть искусственный вкус, все же. Конечно, я могу создать контрпримеры для студентов таким образом, но я не вижу более скептического убеждения в этом. Существуют ли «естественные» случаи этого явления (т.е. полиномиальные функции более высокой степени, которые могут быть ошибочно приняты за другие функции), где неправильное толкование является «фатальным»?
Рафаэль
Я знаю, что это не тот ответ, который вы ищете.
Дейв Кларк