Comment tromper l'heuristique d'inspection des parcelles?

23

Au cours ici , Dave Clarke a proposé que pour comparer la croissance asymptotique vous devez tracer les fonctions à portée de main. En tant qu'informaticien théoriquement enclin, j'appelle (ed) ce vodoo comme un complot n'est jamais une preuve. Après réflexion, je dois convenir qu'il s'agit d'une approche très utile qui est même parfois sous-utilisée; une intrigue est un moyen efficace d'obtenir des premières idées, et parfois c'est tout ce dont vous avez besoin.

Lors de l'enseignement du TCS, il y a toujours l'étudiant qui demande: "Pourquoi ai-je besoin d'une preuve formelle si je peux juste faire X qui fonctionne toujours?" C'est à son ou ses professeurs de souligner et d'illustrer l'erreur. Il existe un ensemble brillant d'exemples de modèles apparents qui finissent par basculer à math.SE, mais ce sont des scénarios assez mathématiques.

Alors, comment trompez-vous l'heuristique d'inspection des parcelles? Dans certains cas, il est difficile de distinguer les différences, par exemple

Exemple Exemple Exemple
^{[ source ]}

Faites une supposition, puis vérifiez la source pour les fonctions réelles. Mais celles-ci ne sont pas aussi spectaculaires que je l'espère, en particulier parce que les vraies relations sont faciles à repérer à partir des seules fonctions, même pour un débutant.

Existe-t-il des exemples de croissance asymptotique (relative) où la vérité n'est pas évidente à partir de la définition de la fonction et l'inspection des parcelles pour un raisonnablement grand vous donne une idée complètement fausse? Les fonctions mathématiques et les ensembles de données réels (par exemple, l'exécution d'un algorithme spécifique) sont tous deux les bienvenus; veuillez toutefois vous abstenir de fonctions définies par morceaux. $n$

asymptotics didactics Raphael
la source

2

En fait, je l'ai proposé comme astuce pour comprendre le problème.

Dave Clarke

@DaveClarke: Je sais; J'ai utilisé votre formulation initiale simplement comme une ouverture provocante. Aucune infraction prévue.

Raphael

23

Par expérience, en essayant de comprendre le taux de croissance d'une fonction observée (par exemple, le temps de mélange de la chaîne de Markov ou le temps d'exécution de l'algorithme), il est très difficile de distinguer les facteurs de de . Par exemple, ressemble beaucoup à : $(\log n)^a$ $n^b$ $O(\sqrt{n} \log n)$ $O(n^{0.6})$

terrain
^{[ source ]}

$[0,1]$ $n^{0.6}$ $n^{0.7}$ $n^{1/2}\log^{3/4}n$ $n^{2/3}$

Peter Shor
la source

15

Voici un autre exemple (certes plutôt construit), mais je le trouve encore remarquable. Il est destiné à montrer que les parcelles peuvent être très trompeuses pour juger de la croissance asymptotique.

$f$ $g$

Pouvez-vous deviner laquelle des fonctions croît (asymptotiquement) plus rapidement?

tracé de f et g jusqu'à 2000 tracé de f et g jusqu'à 10 000 tracé de f et g jusqu'à 200 000

$f\sim g$

f (x) = x^{2}

$f(x) = x^2$

g (x) = \iint \sin (\log (x)) + 1 d x d x = x^{2} (1 - \frac{3}{5} \cos (\log (x)) + \frac{1}{5} \sin (\log (x))) .

$g(x) = \iint \sin(\log(x))+1 \;dx\,dx = x^2\Bigl(1 - \tfrac{3}{5} \cos(\log(x)) + \tfrac{1}{5} \sin(\log(x)) \Bigr)\;.$

Donc est essentiellement , c'est-à-dire la même chose que , mais sa dérivée seconde n'est pas uniformément , mais oscille entre et avec une période de croissance exponentielle. Cette oscillation n'est pas visible dans les parcelles ordinaires. $g$ $x^2$ $f$ $2$ $0$ $4$

Pour cet exemple, nous pouvons démasquer les oscillations en considérant un log-log-plot:

log-log-plot de f et g jusqu'à 200 000

Bien sûr, cela n'aide pas, en général; par exemple, nous pourrions avoir une période doublement exponentielle ...

Sébastien
la source

12

Un bel exemple est l'algorithme DFA minimal et profondément magique de Brzozowski. Étant donné un automate fini , nous pouvons en calculer un automate fini déterministe minimal: $N = (Q, S \subseteq Q, F \subseteq Q, R \subseteq Q \times \Sigma \times Q)$

M i n i m i z e : N F A \to D F A = D e t e r m i n i z e \circ R e v e r s e \circ D e t e r m i n i z e \circ R e v e r s e

$\mathrm{Minimize} : \mathrm{NFA \to DFA} = \mathrm{Determinize\circ Reverse \circ Determinize \circ Reverse}$

Il s'agit évidemment d'un algorithme de temps exponentiel dans le pire des cas, car il peut prendre un automate non déterministe et vous en donner un déterministe (ou encore plus évidemment, il appelle deux fois la construction du sous-ensemble).

Cependant, si vous attribuez à l'algorithme de Brzozowski un DFA en entrée, sur de nombreux types courants, il peut concurrencer et souvent surpasser les algorithmes spécialisés de minimisation DFA (qui sont généralement ou si vous êtes hard-core et implémentez l'algorithme de Hopcraft). $O(n^2)$ $O(n \log(n))$

Cela touche la partie "plot" de "l'heuristique d'inspection de plot" --- nous devons choisir les points à échantillonner lors du dessin du plot, et vous pouvez tromper un plot naïf si vous ne choisissez pas vos points avec soin. Cela est également vrai pour d'autres exemples, tels que Quicksort et l'algorithme Simplex, mais pour la pédagogie, je préfère cet algorithme à ces deux.

La différence de Quicksort est "seulement" quadratique par rapport à log-linéaire, ce qui est moins spectaculaire qu'une différence polynomiale / exponentielle. L'algorithme simplex a une différence tout aussi spectaculaire, mais son analyse est considérablement plus compliquée que l'algorithme de Brzozowski.

(De plus, je pense que l'algorithme de minimisation DFA de Brzozowski est beaucoup moins bien connu qu'il ne devrait l'être, mais bien sûr, c'est une question de goût.)

Neel Krishnaswami
la source

Désolé, mais je ne vois pas vraiment le lien avec l'interprétation des tracés de fonctions.

Raphael

3

Je suppose que vous feriez quelque chose comme les performances du tracé par rapport à la taille de l'instance pour un échantillon d'instances - et l'algorithme de Brzozowski "ressemblerait" à un polynôme à moins que vous ne choisissiez des instances pour en faire un temps exponentiel.

Neel Krishnaswami

1

Je vois. C'est certainement un problème lors de l'analyse comparative des algorithmes et du traçage des durées d'exécution moyennes, c'est-à-dire un problème de traçage des bonnes données . Quand j'ai posé la question, je ne pensais qu'à interpréter correctement l'intrigue , qui est une autre bête entièrement. Pouvez-vous ajouter cette perspective à la réponse?

Raphael

Vous auriez le même problème pour tous les algorithmes dont le comportement moyen et le pire des cas sont différents; Quicksort et Simplex viennent à l'esprit.

Raphael

8

La technique mathématique de l' ajustement de courbe peut être utilisée pour fournir un nombre infini de réponses à votre question. Étant donné une courbe et une plage, on peut facilement trouver un polynôme qui s'adapte à la courbe à n'importe quel degré de précision. Cet exemple de Wikipédia montre comment une onde sinusoïdale peut être assez précisément ajustée avec un polynôme de quatrième ordre (la courbe bleue).

entrez la description de l'image ici

Je pourrais utiliser des polynômes d'ordre supérieur et tromper l'heuristique d'inspection de tracé encore mieux que ce graphique.

Dave Clarke
la source

2

C'est vrai. Il a également un goût artificiel. Bien sûr, je peux générer des contre-exemples pour les étudiants de cette façon, mais je ne pense pas que les plus sceptiques en soient convaincus. Y a-t-il des occurrences "naturelles" de ce phénomène (c'est-à-dire des fonctions polynomiales de degré supérieur qui peuvent être confondues avec d'autres fonctions) où une mauvaise interprétation est "fatale"?

Raphael

Je sais que ce n'est pas la réponse que vous cherchez.

Dave Clarke

Comment tromper l'heuristique d'inspection des parcelles?

Réponses: