Wie man herausfindet, ob eine Black-Box polynomiell oder exponentiell ist

Question

Ich habe ein Problem, das im Wesentlichen auf Folgendes reduziert werden kann:

1. Sie haben eine Black-Box-Funktion, die Eingaben der Länge n akzeptiert.
2. Sie können die Zeit messen, die die Funktion benötigt, um die Antwort zurückzugeben, aber Sie können nicht genau sehen, wie sie berechnet wurde.
3. Sie müssen bestimmen, ob die Zeitkomplexität dieser Funktion polynomial oder exponentiell ist.

Den Weg, den ich gegangen bin, war, Tausende von zufälligen Beispieleingaben unterschiedlicher Länge durch die Funktion laufen zu lassen, sie dann in einem Streudiagramm mit den Zeiten auf der y-Achse und der Eingabelänge auf der x-Achse darzustellen.

Ich habe das Streudiagramm mit numpy geplottet, aber wie zeichne ich jetzt die Polynomial- und Exponential-Anpassungslinien? Und welche Metriken kann ich berechnen, um zu bestimmen, welche Anpassungslinien am besten passen?

(Ich habe eine ähnliche Frage, jedoch theoretisch und ohne Schwerpunkt auf einer bestimmten Sprache, in der Informatik gestellt: https://cs.stackexchange.com/questions/23686/how-to-determine-if-a-black-box-is-polynomial-or-exponential)

Answer 1

Nehmen Sie den Logarithmus aller Ihrer Y-Werte. Die polynomiale Ergebnisse werden immer noch logarithmisches Wachstum aufzeigen (da log x^n = n * log x), aber die exponentielle Kurve wird sich in eine ordentliche Gerade verwandeln (log exp(x) = x).

Wenn Sie nun genügend der Ergebnispunkte mit linearer LSQ approximieren, dann können Sie ziemlich sicher sein, dass der Algorithmus exponentiell ist, wenn er gut passt (lassen Sie jedoch etwas Unterschied zu -- ich schlage vor, ein vernünftiges Epsilon empirisch zu bestimmen, indem Sie einen Algorithmus untersuchen, dessen Komplexität Sie kennen!), und sonst polynomial ist.

Sie können auch das Vertrauensniveau etwas erhöhen, indem Sie die Abweichung von der Regressionslinie untersuchen: Wenn die meisten Werte darunter liegen, dann waren die Daten höchstwahrscheinlich logarithmisch (d. h. das Programm lief in polynomialer Zeit).

Answer 2

Wenn die Zeitkosten t Ihres Algorithmus polynomial in Bezug auf die Größe n sind, d.h. t = k*nm annähert, dann sollte ein Log-Log-Diagramm, ein Diagramm von log t gegen log n eine Gerade mit der Steigung m (und Achsabschnitt log k) sein.

Wenn die Zeitkosten t Ihres Algorithmus exponential in Bezug auf die Größe n sind, d.h. t = k_em_n, dann sollte ein Halblogarithmisches Diagramm, ein Diagramm von log t gegen n eine Gerade mit der Steigung m (und Achsabschnitt log k) sein.

Weil diese Diagramme gerade Linien sind, können Sie einfache lineare Regression verwenden, um die Parameter abzuschätzen.

Wie zeichne ich polynomiale und exponentielle Best-Fit-Linien?

Sobald Sie die Parameter haben, die Steigung m und den Achsenabschnitt c der geraden Linie in Log-Log oder Halblogarithmischem Raum, können Sie m und c zurück in Ihren originalen Koordinatenraum umwandeln, um die Best-Fit-Kurve in Bezug auf Ihre originalen Daten zu erhalten (die Details sind im untenstehenden Beispielprogramm gezeigt).

Welche Metriken kann ich berechnen, um zu bestimmen, welche Best-Fit-Linien am besten passen?

Das _R_2 der Regression gibt einen numerischen Hinweis auf die Anpassungsgüte, wobei eine Näherung an 1 eine bessere Anpassung bedeutet. Dies kann jedoch ein wenig irreführend sein, da es die Anpassung im transformierten Raum widerspiegelt (log t gegen log n oder log t gegen n). Daher ist es einfacher, sich einfach die resultierenden Gleichungen anzusehen und die Kurven abzuschätzen. Eine alternative quantitative Maßnahme wäre die Summierung der Fehler zwischen Ihren originalen Daten und den entsprechenden Punkten auf der Best-Fit-Kurve.

Diese Technik wird mit den folgenden Datenreihen demonstriert (die jeweils Rauschen enthalten)

• Reihe 0: t = 3n
• Reihe 1: _t = 5n_2
• Reihe 2: _t = 7e_n
• Reihe 3: _t = 9e_2n

In der folgenden Abbildung können Sie sehen, dass die polynomial Form für Reihe 0 und 1 wiederhergestellt wurde (grüne gestrichelte Linie), und die exponentielle Form für Reihe 2 und 3 wiederhergestellt wurde (rote gestrichelte Linie). In jedem Fall korrespondieren höhere _R_2s mit der besten Anpassung, und der Parameter m wurde ziemlich genau wiederhergestellt.

Der Code befindet sich unten

importieren Mathematik, Numpy als np, Matplotlib.pyplot als plt
von der sklearn importieren lineares Modell

N = 100
lo = 2
hi = 25
n = np.linspace(lo,hi,num=N)
D = 4
T = np.maximum(np.random.normal(scale=hi / 25.0, size=(N,D)),0.01)
T[:,0] = 3*(T[:,0] + n)
T[:,1] = 5*(T[:,1] + n)**2
T[:,2] = 7*np.exp(T[:,2]/5.0 + n)
T[:,3] = 9*np.exp(2*(T[:,3]/5.0 + n))

logn = np.log(n)
logT = np.log(T)

für ich im Bereich(D):
    # passen Sie das Log-Log-Modell an
    loglogmod = lineares Modell.LineareRegression()
    x=np.reshape(logn,(N,1))
    y=logT[:,i]
    loglogmod.fit(x, y)
    loglogmod_rsquared = loglogmod.score(x, y)
    # passen Sie das Log-Modell an
    logmod = lineares Modell.LineareRegression()
    x=np.reshape(n,(N,1))
    logmod.fit(x, y)
    logmod_rsquared = logmod.score(x, y)
    # Ergebnisse plotten
    plt.subplot(2,2,i+1)
    plt.plot(n, T[:,i], label='Reihe {}'.format(i),lw=2)
    m = loglogmod.coef_[0]
    c = loglogmod.intercept_
    polynomial = math.exp(c)*np.power(n,m)
    plt.plot(n, polynomial,
                label='$t={0:.1f}n^{{{1:.1f}}}$ ($r^2={2:.2f}$)'.format(math.exp(c),m,loglogmod_rsquared),
                ls='dashed',lw=3)
    m = logmod.coef_[0]
    c = logmod.intercept_
    exponential = np.exp(n * m) * math.exp(c)
    plt.plot(n, exponential,
                label='$t={0:.1f}e^{{{1:.1f}n}}$ ($r^2={2:.2f}$)'.format(math.exp(c),m,logmod_rsquared),
                ls='dashed',lw=3)
    plt.legend(loc='oben links', prop={'Größe':16})

plt.show()

(Dokumentation, die ich verwendet habe: sklearn.lineares Modell.LineareRegression Referenz und Matplotlib Tutorial)