4. "Kompakte" Linearkombination

"Kompakte" Linearkombination

  • ?

    C14 schrieb:

    Verstehe nicht, wie das gehen soll.
    Kannst du das genauer erklären?
    Bsp m=4, n=2,
    Gauss-Elimination ->
    1 * * * | *
    0 1 * * | *
    Und nun?

    Nun kommt es darauf an, ob (a) oder (b) gleich 0 sind
    1 0 * * | (a)
    0 1 * * | (b)

    0
  • C

    Helfer in der Not schrieb:

    C14 schrieb:

    Verstehe nicht, wie das gehen soll.
    Kannst du das genauer erklären?
    Bsp m=4, n=2,
    Gauss-Elimination ->
    1 * * * | *
    0 1 * * | *
    Und nun?

    Nun kommt es darauf an, ob (a) oder (b) gleich 0 sind
    1 0 * * | (a)
    0 1 * * | (b)

    Bist du in der Lage den vollständigen Algorithmus zu skizzieren oder einen Link zu posten?
    Ich sehe es wie gesagt nicht und habe keine Lust auf seitenlange Kaffeesatzleserei.
    Hat noch jemand ne Idee?

    0
  • O

    Ich würde das als ein optimierungsproblem modellieren:

    minαλ∣α∣+(Aα−v)2min_{\alpha} \lambda|\alpha| + (A\alpha-v)^2
    wobei λ >0 ein lagrange multiplier ist, den du tunen musst und A dein erzugendensystem. Da du hier die 1-norm und nicht die 0-norm optimierst, ist das nicht das Selbe. Aber in der Praxis gibt dies ziemlich gute Ergebnisse. Soweit ich weiß, gibt es für die 0-norm-Lösung keine geschlossene Lösung (und ist wahrscheinlich NP vollständig) und die 2-norm gibt dir kein spärliche Lösung. bleibt die 1-Norm als Mittelding. Ist ein wenig ätzend zu optimieren, aber das läuft dann unter dem Namen Lasso-Regression.

    //edit ich würde vermuten, dass in deinem Fall ein sehr kleines lambda reicht, weil du ja keine Darstellung kleiner als n haben willst.

    0
  • M

    Willst du eine optimale Lösung oder darfs auch eine Approximation sein?

    0
  • C

    Ok, die 1-Norm Optimierung werd ich mir mal anschauen.
    Ich will schon eine Darstellung kleiner als n haben wenn möglich (bis runter zu 1) und eigentlich wollte ich eine exakte Lösung aber die 1-Norm als Optimierungskriterium macht vielleicht auch Sinn.
    Bei meinem konkreten Problem ist n=8 und m~20.
    (es geht um die optimale Darstellung von Einheiten, so soll z.B. "kg2*m/s2" über diese Optimierung in "kg*N" übersetzt werden)

    0
  • ?

    C14 schrieb:

    (es geht um die optimale Darstellung von Einheiten, so soll z.B. "kg2*m/s2" über diese Optimierung in "kg*N" übersetzt werden)

    So sieht das eher nach diskreter Optimierung aus, z.B. "Integer program" (wobei man die ja wiederum oft durch ein LP approximiert). Bist du Dir sicher, dass deine Konstruktion ein Vektorraum ist? Was ist der Nullvektor, was ist die skalare Eins?

    0
  • K

    Und hier wieder das typische Problem von "wie setze ich meine bescheuerte Loesung um" im Gegensatz zum eigentlichen Problem:

    (es geht um die optimale Darstellung von Einheiten, so soll z.B. "kg2*m/s2" über diese Optimierung in "kg*N" übersetzt werden)

    Wie waers denn mit Patternmatching und einfachen Transformationsregeln um die Einheiten zu kuerzen. Ich verstehe ganz und garnicht, wie man auf Linearkombination oder Kompaktheit als Loesung kommt.

    Man hat den String "kg2*m/s2", parst ihn und expandiert in Einzelkomponenten/Basiseinheiten: "[(kg, kg, m), (s, s)]. Dabei steht in der ersten Liste alles ueber dem Bruchstrich und in der zweiten alles unter dem Bruchstrich. Dann wendet man Transformationsregeln an:

    Beispiel Newton:
    [(kg, m) ,( s, s)] -> [(N) , ()]
    [(s,s), (kg, m)] -> [(), (N)]
    oder:
    [(s), (s)] -> [(), ()]
    genereller:
    [(_n), (_n)] -> [(), ()] wobei _n ein Platzhalter ist.

    Mit der Annahme, dass jeder Transformationsschritt, die Groesse verringert (bzw. Kompaktheit vergroesser), gibt es endlich viele "Blattknoten". Daraus den kuerzesten auszuwaehlen ist trivial. Die Annahme ist leicht an den gewaehlten Transformationen ueberpruefbar. Weiterhin halte ich nichts davon, wenn m/s^2 durch N/kg ersetzt wird, was einem Erweitern mit kg und dann einem Ersetzen entspricht, obwohl letzterer kompakter ist.

    Ist genauso wie Brueche kuerzen. Beim Bruch a / b( geschrieben: [(a), (b)] werden a und b in Primfaktoren zerlegt [(...) , (...)] und dann synchron aus beiden Teilen entfernt bis nichts mehr zu entfernen geht.

    Das ist DIE Loesung, ausser du hast uns noch mehr wesentliche Details verschwiegen.

    0
  • ?

    Das Problem ist, dass man zum Finden der kürzesten Darstellung evtl. einen Bruch zuerst mal erweitern muss. Mit anderen Worten: greedy ist nicht optimal.

    0
  • K

    Kenner des Problems schrieb:

    Das Problem ist, dass man zum Finden der kürzesten Darstellung evtl. einen Bruch zuerst mal erweitern muss. Mit anderen Worten: greedy ist nicht optimal.

    Darauf bin ich eingegangen, weiterhin besteht der erste Schritt, alles in Basiseinheiten auszudruecken. Also Expand!

    greedy ist nicht optimal

    Formuliere bitte das Optimalitaetskriterium. Was ist optimal ?m/s^2 vs N/kg.

    0
  • ?

    Kannst du beweisen, dass man nur durch Verkürzen zum optimalen Ergebnis kommt?

    0
  • K

    Kenner des Problems schrieb:

    Kannst du beweisen, dass man nur durch Verkürzen zum optimalen Ergebnis kommt?

    1.) Was ist optimal?
    2.) Es gibt mehrere Minima bei manchen Ausdruecken.
    3.) Moeglichst optimal reicht mir.

    Und beweisen ... werde ich einem Klugscheisser nix.

    0
  • ?

    1. minimale Länge
    2. und?
    3. was soll das heißen?
    0
  • K

    Kenner des Problems schrieb:

    was soll das heißen?

    Das alles von deinem Regelset abhaengt. Beispielsweise um die Transformation m/s^2 nach N/kg durchzufuehren:

    Mit Erweiterung:
    [(_n, ...) , (_m, ...)] -> [(_k, _n, ...), (_k, _m, ...)]
    [(kg, m), (s,s)] -> [(N), ()]

    Ohne Erweiterung:

    [(m), (s,s)] -> [(N), (kg)]

    Und ich bin mir fast sicher, dass ein Regelsystem ueber endlich viele Basiseinheiten konstruiert werden kann, dass nur kuerzt, um einen optimalen Ausdruckt abzuleiten. Da Erweiterungsregeln implizit in Kuerzungsregeln einfliessen koennen. Beweisen werde ich das nicht. Weiterhin ist die Anzahl der noetigen Erweiterungen nach oben sicher beschraenkt (abhaengig von Basisausdruck), um mittels greedy zum optimalen Ausdruck zu finden.

    0
  • J

    knivil schrieb:

    Und hier wieder das typische Problem von "wie setze ich meine bescheuerte Loesung um" im Gegensatz zum eigentlichen Problem:

    (es geht um die optimale Darstellung von Einheiten, so soll z.B. "kg2*m/s2" über diese Optimierung in "kg*N" übersetzt werden)

    Wie waers denn mit Patternmatching und einfachen Transformationsregeln um die Einheiten zu kuerzen. Ich verstehe ganz und garnicht, wie man auf Linearkombination oder Kompaktheit als Loesung kommt.

    da kommt man drauf wenn man seine problemstellungen sauber modelliert und nicht einfach irgendwelche ad-hoc-ansätze draufballert. 😉

    0
  • C

    Danke für die Ideen.
    Ich will auch rationale Exponenten unterstützen, weswegen ich mich gleich dazu entschieden habe, die Exponenten als Vektoren im R^n zu modellieren.
    Allerdings stimmt es natürlich, dass man wenn möglich ganzzahlige Exponenten bevorzugen sollte, was aktuell nicht passiert.
    Vielleicht wäre es sinnvoll je nach input anders vorzugehen.

    0
  • K

    die Exponenten als Vektoren im R^n zu modellieren

    Kannst du immer noch, gibt sogar schon ne Bibliothek dafuer: http://www.boost.org/doc/libs/1_54_0/libs/mpl/doc/tutorial/dimensional-analysis.html. Nur hat das mit der kuerzesten Darstellung nix mehr zutun. Dargestellt wird erst, wenn die Einheiten schon ausgerechnet sind.

    0
Anmelden zum Antworten