Frage zu Algorithmus: "Finde ähnlichste Paare"

[Jester]

TGGC schrieb:

Jester schrieb:

Der Hauptunterschied zum TSP ist, dass man hier nicht fordert, dass die ausgewählten Verbindungen (Paare) einen zusammenhängenden Graphen ergeben... und das macht alles leichter.

Ja, wenn man eine Methode findet, die zeigt, das der zusammenhaengene Graph nicht die beste Loesung sein wird.

Nein, es sagt niemand, dass die Lösung für ein einfacheres Problem nicht auch mal zufällig eine Lösung für ein schwierigeres Problem sein darf.

Hier tritt aber selbst dieser Fall nicht auf, da ja nur Paare gebildet werden und damit kein Knoten zweimal vorkommt -- also können auch keine Kreise entstehen.

[TGGC]

Jester schrieb:

Nein, es sagt niemand, dass die Lösung für ein einfacheres Problem nicht auch mal zufällig eine Lösung für ein schwierigeres Problem sein darf.

Ja, das stimmt. Ich hatte mir das so vorgestellt, das ich die Paare dann aneinanderhaenge und sich so ein Kreis ergibt, fuer den Fall das zufaelligerweise genau diese restlichen Kosten 0 waeren.

[Jester]

@happystudent: Versuch mal zu beweisen dass man Paare nicht verdrehen sollte. Also wenn ich a<b in Liste A und c<d in Liste B habe, dass dann die Paare ac und bd immer genauso gut oder besser als die Paarung ad und bc ist.

Wenn das gilt, löst es direkt das Problem wenn die Listen gleich lang sind, weil Du einfach nur sortieren musst und den kleinsten Eintrag aus A mit dem kleinsten Eintrag aus B paaren musst usw.

[happystudent]

Jester schrieb:

@happystudent: Versuch mal zu beweisen dass man Paare nicht verdrehen sollte. Also wenn ich a<b in Liste A und c<d in Liste B habe, dass dann die Paare ac und bd immer genauso gut oder besser als die Paarung ad und bc ist.

Ok. Sei

$a < b, c < d \text{ und } a,b,c,d \neq 0$

Dann folgt daraus für die Summe der Abstandsquadrate:

(a - c)^2 + (b - d)^2 \leq (a - d)^2 + (b - c)^2 \\ a^2 - 2ac + c^2 + b^2 - 2bd + d^2 \leq a^2 - 2ad + d^2 + b^2 - 2bc + c^2 \\ -2ac - 2bd \leq -2ad - 2bc \\ ac + bd \geq ad + bc \\ ac - ad \geq bc - bd \\ a(c -d) \geq b(c - d) \\ a \geq b \\

und damit ein Widerspruch zu unserer ursprünglichen Annahme dass a < b.
Die Bedingung ist somit nicht erfüllt und zwar für allgemeine a, b, c, d.

Hilft es vielleicht dass die vectoren streng monoton sind?

[Jester]

Und jetzt finde den Fehler. Tipp: was ist das Vorzeichen von (c-d)?

[happystudent]

Jester schrieb:

Und jetzt finde den Fehler. Tipp: was ist das Vorzeichen von (c-d)?

Hm, ungünstig ungeformt. Wie wärs damit:

\vdots \\ ac + bd \geq ad + bc \\ bd - ad \geq bc - ac \\ d(b - a) \geq c \underbrace{(b - a)}_{b - a > 0} \\ d \geq c\\

was widerum ein Widerspruch wäre, da c < d gefordert war.

[Nathan]

happystudent schrieb:

d \geq c\\
was widerum ein Widerspruch wäre, da c < d gefordert war.

Wenn c < d, ist d > c...

[Jester]

Wo genau findet sich der Widerspruch zwischen c<=d und c<d?

edit: mit anderen Worten, eigentlich hast Du die Aussage bewiesen. Es kommt nämlich eine Bedingung heraus, die nach Eingangsvoraussetzung erfüllt ist.

[happystudent]

Nathan schrieb:

Wenn c < d, ist d > c...

Jester schrieb:

Wo genau findet sich der Widerspruch zwischen c<=d und c<d?

edit: mit anderen Worten, eigentlich hast Du die Aussage bewiesen. Es kommt nämlich eine Bedingung heraus, die nach Eingangsvoraussetzung erfüllt ist.

Oh verdammt, ihr habt recht

Gut, dann ist das jetzt bewiesen, aber das bringt ja nur was bei gleichlangen Listen, richtig? Weil meistens sind die Listen halt unterschiedlich lang (die Länge ist zwar ungefähr gleich, aber fast nie identisch).

[xgrif]

Das bringt viel! Jetzt ist die Frage nur noch, welche Elemente du aus der langen Liste rausschmeißt. Welche Paare zusammen gehören ergibt sich dann von ganz alleine. Und die Aufgabe ist ratz fatz mit einem dynamischen Programm gelöst.

OE sei A die längere Liste. Entweder A[1] spielt mit, und (A[1], B[1]) ist das erste Paar und du musst nur noch den Rest A[2...] und B[2...] prüfen, oder A[1] fliegt raus und du vergleichst A[2...] gegen B[1...]. Das ganze bricht ab, wenn A und B gleich lang sind, dann müssen alle Paare rein. Da in jedem Schritt A ein Element kürzer wird, bricht der Algorithmus auch schnell ab.

happystudent schrieb:

Das Ganze ist Teil einer Kostenfunktion für einen Optimierungsalgorithmus [...]

Meinst du nicht, dass die Kostenfunktion ein wesentlicher Teil des Problems ist, und du genau mit der mal rausrücken solltest? Und zwar am besten schon im Anfangspost!

Obiger Algorithmus funktioniert auch nur mit der Summe der quadratischen Abstände als Kostenfunktion, denn du hast ja eine Eigenschaft der quadratischen Abstände in deinem letzten Beweis genutzt, um zu diesem Algorithmus zu kommen.

Wenn du jetzt endlich mal mit der Kostenfunktion rausrückst und es dann nicht die Summe der quadratischen Abstände ist, war u. U. bisher alles für die Katz.

[happystudent]

xgrif schrieb:

Wenn du jetzt endlich mal mit der Kostenfunktion rausrückst und es dann nicht die Summe der quadratischen Abstände ist, war u. U. bisher alles für die Katz.

Naja, also der Algorithmus ist eigentlich schon die Kostenfunktion. Man hat halt zwei unterschiedlich lange Vektoren, die möglichst "ähnlich" zueinander gemacht werden sollen.

Da sie unterschiedlich lang sind, läuft das in zwei Schritten: Zuerst werden die ähnlichsten Paare bestimmt. Das ergibt dann zwei gleich lange Vektoren, die auf klassische Art und Weise verglichen werden können und einen Kostenwert x liefern.

Im zweiten Schritt wird dann mittels einer Heuristik noch ein zusätzlicher Kostenwert y bestimmt, der berücksichtigt wie unterschiedlich die Länge der beiden Vektoren ist. Die Gesamtkosten ergeben sich dann als z = x + y. Am besten wäre nämlich, wenn die beiden Vektoren genau gleich lang wären und identische Einträge hätten.

Es handelt sich dabei um eine physikalisches Model, das so parametriert werden soll, dass die von ihm produzierten Outputs einem vom Benutzer vorgegebenen Wunsch-Output entsprechen (bei gleichem Input). Im Prinzip sieht das so aus:

input = user input 1 // Model input
x_set = user input 2 // Gewünschter Model output

while (error is big)
    p = determine new parameters // Irgendeine Optimierungsmethode
    x_cur = ModelFunction(p, input) // Output des Models mit den aktuellen Parametern p
    error = CalculateErrorBetween(x_cur, x_set) // Fehlerberechnung
endwhile

Problem ist eben dass die Länge des Outputs des Modells (also die Länge des Vektors x_cur ) abhängig von den Parametern p ist.

Mit der oben beschriebenen Methode funktioniert es in einigen Fällen schon ziemlich gut, in anderen aber schlecht bis gar nicht. Außerdem ist die Laufzeit sehr hoch.

So, ich hoffe das waren dann alle relevanten Infos. Letztendlich sollte das Grundproblem sich dadurch aber nicht ändern?

[xgrif]

happystudent schrieb:

Das ergibt dann zwei gleich lange Vektoren, die auf klassische Art und Weise verglichen werden können

Und warum sagst du nicht einfach, wie du sie genau vergleichst? Das ist immerhin das entscheidende Kriterium und macht den Unterschied aus, ob der Algorithmus passt oder nicht. Ich hab zwar eine Kristallkugel, die mir zu "auf klassische Art und Weise" ein trübes Bild liefert, aber das tut doch nun wirklich nicht Not hier auf so nebulöse Angaben aufzubauen.

Im zweiten Schritt wird dann mittels einer Heuristik noch ein zusätzlicher Kostenwert y bestimmt, der berücksichtigt wie unterschiedlich die Länge der beiden Vektoren ist.

Eine Heuristik wovon? Von dem Kostenwert der unterschiedlich langen Listen? Wenn du direkt an den ran kommst, wozu der Umweg?

Mit der oben beschriebenen Methode funktioniert es in einigen Fällen schon ziemlich gut, in anderen aber schlecht bis gar nicht.

Was kommt bei einem Beispiel raus, bei dem es nicht gut funktioniert? Und woher weißt du, dass es nicht gut funktioniert hat?

[parrybear]

komplex schrieb:

Wieso ist der Greedy n^2 log n? Für mich ist der n^2...

Ich wende std::sort auf die O(n^2) lange Liste an.

@happystudent: Wie gesagt, ich schreibe nur einmal den Algorithmus für dich auf. Wenn du meine Frage nicht korrekt beantworten konntest, Pech gehabt. Für das andere Problem steht die Lösung auch schon hier im Thread, du musst sie nur noch richtig implementieren. Laufzeit sollte O(n*d) sein, wobei d die Differenz der Länge der Listen ist und vorausgesetzt, die Listen sind vorsortiert.

Aber wie gesagt, wahrscheinlich optimierst du sowieso am falschen Ort.

[happystudent]

xgrif schrieb:

Und warum sagst du nicht einfach, wie du sie genau vergleichst? Das ist immerhin das entscheidende Kriterium und macht den Unterschied aus, ob der Algorithmus passt oder nicht.

Mit der Summe der Abstandsquadrate.

xgrif schrieb:

Eine Heuristik wovon? Von dem Kostenwert der unterschiedlich langen Listen? Wenn du direkt an den ran kommst, wozu der Umweg?

Das ist nur dafür da um unterschiedliche Längen der Vektoren zu bestrafen. Die Vektoren sollten idealerweise gleich lang sein und den gleichen Inhalt haben.

Deswegen such ich mir die besten Paare und bestimme mit der Summe der Abstandsquadrate deren Kosten. Danach addiere ich zu diesen Kosten den Längenunterschied der Vektoren.

xgrif schrieb:

Was kommt bei einem Beispiel raus, bei dem es nicht gut funktioniert?

Ein Vektor der sich stark von dem Vorgabe-Vektor unterscheidet.

xgrif schrieb:

Und woher weißt du, dass es nicht gut funktioniert hat?

Das Model kann auch mit anderen, bereits existierenden Verfahren (die andere Ansätze verfolgen) optimiert werden. Daher hat man einen Vergleich.

[Jester]

Kriegst Du das dynamische Programm hin oder brauchst Du dafür noch Hilfe?

[happystudent]

Jester schrieb:

Kriegst Du das dynamische Programm hin oder brauchst Du dafür noch Hilfe?

Habs inzwischen hingekriegt, danke

[Jester]

Das freut mich. Können wir dann vereinbaren, dass Du meine Hinweise nächstes mal von Anfang an ernst nimmst?

[happystudent]

Jester schrieb:

Das freut mich. Können wir dann vereinbaren, dass Du meine Hinweise nächstes mal von Anfang an ernst nimmst?

Hm, keine Ahnung wie du darauf kommst dass ich deine Hinweise nicht ernst genommen hätte. Hatte nen Vorzeichenfehler in dem Beweis (und in der Verbesserung dann nen Denkfehler^^), aber das war ja nicht mit Absicht?

Naja, trotzdem Danke und so