Maschinelles Lernen
Tim Frink
ich stehe vor einem Problem, das ich vermutlich sehr effizient mit
Maschinellem Lernen lösen könnte. Da ich auf diesem Gebiet ein völliger
Anfänger bin, würde ich mich freuen, wenn Ihr meine Idee kommentieren
könntet.
Das Problem ist folgendes: Ich möchte für C-Programme die Laufzeit
abschätzen. Dazu benutze ich einen Parser, der mit das C-Programm in
seine modularen Bestandteile (also C-Anweisungen) zerlegt. Über die
Datenstrukturen, in die das zerteilte C-Programm abgelegt wird, kann
ich dessen Eingenschaften abfragen. Nun wird das Programm simuliert
und über mehrere Umwege erfahre ich, wie lange jedes C-Construkt
für seine Ausführung gebraucht hat. Mit diesem Aufbau möchte ich mein
System für verschiedende Benchmarks lernen lassen, so dass ich in Zukunft
für ein neues Programm, das nicht für das Training benutzt wurde, in
der Lage bin, die gelernten Daten abzufragen, um mir für die Konstrukte
des neues Benchmarks die Laufzeitheit "vorhersagen" zu lassen. Damit würde
ich die aufwändige Simulation sparen.
Bei dieser Problemstellung ergeben sich noch zwei Probleme:
a) Ich muß vor dem Lernen die C-Konstrukte klassifizieren. Wie gehe ich
bei so einer Mustererkennung vor? Ich vermute, dass die Wahl der Kriterien,
die ein C-Konstrukt beschreiben, von großer Wichtigkeit ist. Aber wie
finde ich diese Kriterien? Gibt es dafür irgendwelche Richtlininen/Tools?
b) Angenommen, a) sei gelöst. Dann ist mir noch unklar, wie so ein System
mit verschiedenen Laufzeiten für Konstrukte aus der gleichen Klasse umgeht.
Es kann ja passieren, dass zwei Konstrukte relativ ähnlich sind und damit
derselben Klasse zugeordnet werden. Diese können aber trotzdem
unterschiedliche Laufzeiten haben. Was macht das System in dem Fall? Wird
ein Mittel über die Laufzeiten gebildet oder wie funktioniert diese
"Verschmelzung"?
Denkt Ihr, dass das Maschinelle Lernen dafür geeignet ist? Falls ja, könnt
Ihr mir frei C++-Bibliotheken empfehlen. Falls Ihr irgendwelche
Paper/Bücher kennt, die sich ausführlich mit diesem Thema beschäftigen,
dann wäre das auch schon sehr hilfreich.
Vielen Dank.
Schöne Grüße,
Tim
Joachim Pimiskern
> Das Problem ist folgendes: Ich möchte für C-Programme die Laufzeit
> abschätzen. Dazu benutze ich einen Parser, der mit das C-Programm in
> seine modularen Bestandteile (also C-Anweisungen) zerlegt. Über die
> Datenstrukturen, in die das zerteilte C-Programm abgelegt wird, kann
> ich dessen Eingenschaften abfragen. Nun wird das Programm simuliert
> und über mehrere Umwege erfahre ich, wie lange jedes C-Construkt
> für seine Ausführung gebraucht hat. Mit diesem Aufbau möchte ich mein
> System für verschiedende Benchmarks lernen lassen, so dass ich in Zukunft
> für ein neues Programm, das nicht für das Training benutzt wurde, in
> der Lage bin, die gelernten Daten abzufragen, um mir für die Konstrukte
> des neues Benchmarks die Laufzeitheit "vorhersagen" zu lassen. Damit würde
> ich die aufwändige Simulation sparen.
Gestalte Dein Programm so, daß es, wenn die Laufzeit des
Eingabeprogramms länger als eine Stunde ist, sofort terminiert,
und im Falle, daß die Laufzeit des Eingabeprogramms kleinergleich
eine Stunde laufen würde, in eine Verzögerungsschleife springt,
die siebeneinhalb Millionen Jahre läuft.
Schreibe Dein Programm in C, und gib ihm
es selbst als Eingabe.
Grüße,
Joachim
Joachim Pimiskern
> Das Problem ist folgendes: Ich möchte für C-Programme die Laufzeit
> abschätzen. Dazu benutze ich einen Parser, der mit das C-Programm in
> seine modularen Bestandteile (also C-Anweisungen) zerlegt. Über die
> Datenstrukturen, in die das zerteilte C-Programm abgelegt wird, kann
> ich dessen Eingenschaften abfragen. Nun wird das Programm simuliert
> und über mehrere Umwege erfahre ich, wie lange jedes C-Construkt
> für seine Ausführung gebraucht hat. Mit diesem Aufbau möchte ich mein
> System für verschiedende Benchmarks lernen lassen, so dass ich in Zukunft
> für ein neues Programm, das nicht für das Training benutzt wurde, in
> der Lage bin, die gelernten Daten abzufragen, um mir für die Konstrukte
> des neues Benchmarks die Laufzeitheit "vorhersagen" zu lassen. Damit würde
> ich die aufwändige Simulation sparen.
Gestalte Dein Programm so, daß es, wenn die Laufzeit des
Eingabeprogramms länger als eine Stunde ist, sofort terminiert,
und im Falle, daß die Laufzeit des Eingabeprogramms kleinergleich
eine Stunde ist, in eine Verzögerungsschleife springt,
Kalle07
> Das Problem ist folgendes: Ich möchte für C-Programme die Laufzeit
> abschätzen.
Fehleranfaelligkeit von Code automatisch zu klassifizieren. Prof.
Adriano Oliveira macht sowas, ueblicherweise wird dabei Bezug genommen
auf ein Softwareprojekt von der NASA, wozu Code-Metriken publiziert
wurden:
http://mdp.ivv.nasa.gov/
Eventuell kannst Du ausgehend von den Referenzen was finden. Ist glaub
ich ein sehr wenig erforschtes Gebiet, aber man hoert, dass es gar
nicht so schlechte Erfolge produziert. Ob man die Ergebnisse dann auf
Performanz uebertragen kann ist allerdings nur schwer vorherzusagen,
aber sicher einen Versuch wert (den Hinweis auf das Halteproblem
kannst Du getrost als neunmalklug abtun).
Klaus Stein
> On 3 Jun., 14:23, Tim Frink <plfr...@yahoo.de> wrote:
> > Das Problem ist folgendes: Ich möchte für C-Programme die Laufzeit
> > abschätzen.
> Ob man die Ergebnisse dann auf
> Performanz uebertragen kann ist allerdings nur schwer vorherzusagen,
> aber sicher einen Versuch wert (den Hinweis auf das Halteproblem
> kannst Du getrost als neunmalklug abtun).
Das denke ich nicht. Sie zeigt genau den wunden Punkt.
Die Laufzeit von:
WHILE bedingung(a,b,c,d)
tuWasMit(a,b,c,d)
abzuschätzen ist syntaktisch einfach nicht möglich, dazu muß ich verstehen,
was die Funktionen bedingung(a,b,c,d) und tuWasMit(a,b,c,d) machen, d.h.
ihre Semantik verstehen, dann kann ich ggf. Invarianten bestimmen und
Hüllkurven angeben, in denen die Zeiten liegen müssen.
Nur wenn ich eine sehr beschränkte Sprache betrachte (keine while- und nur
echte for-schleifen (d.h. welche, in denen die Laufvariable im Gegensatz zu C
nicht innerhalb der Schleife manipulierbar ist), keine Rekursion, keine
Gotos oder Comefroms[1]), kann ich die Laufzeit mit Anzahl Schritte mal
Schleifendurchläufe abschätzen. Für manche Webapplikationen mag dies
reichen, für komplexere Algorithmen dagegen nicht.
Außerdem sind Laufzeiten natürlich stark von den Eingabedaten abhängig, wie
man sich an einfachen Beispielen wie der Laufzeit des bekannten
Taschenrechnerspiels überlegen kann:
def to_one(n)
if n != 1
if odd(n)
return to_one(3*n+1)
else
return to_one(n/2)
fi
fi
end
(hier rekursiv notiert, geht mit while natürlich genauso).
Oder noch schlimmer:
def a(n,m)
if n == 0
return n+1
elsif m == 0
return a(n-1,1)
else
return a(n-1, a(n, m-1))
fi
end
Das hat für a(1,1) eine durchaus andere Laufzeit als für a(5,5).
D.h. ob Laufzeitabschätzungen durch rein syntaktische Betrachtung von
Befehlsfolgen möglich sind, hängt von der Domäne ab. Geht es um irgendwelche
linearen Sequenzen, die irgendwelches HTML erzeugen, also letztlich nur um
Folgen von print-Anweisungen, dann kann das gehn. Geht es um Algorithmen
(und hier wird die Sache finde ich erst interessant), kann es faktisch nicht
gehen.
Klaus
[1] siehe z.B. Intercal
--
http://lapiz.istik.de/
The Answer is 42. And I am the Answer. Now I am looking for the Question.
Kalle07
> Kalle07 <kall...@live.com> wrote:
> > aber sicher einen Versuch wert (den Hinweis auf das Halteproblem
> > kannst Du getrost als neunmalklug abtun).
> Das denke ich nicht. Sie zeigt genau den wunden Punkt.
1. Was hat das mit Maschinenlernen zu tun?
2. Wieviel entscheidbarer ist die Praesenz von Fehlern als die
Laufzeit von Code?
Klaus Stein
> On 4 Jun., 17:32, Klaus Stein <use...@istik.de> wrote:
> > Kalle07 <kall...@live.com> wrote:
> > > aber sicher einen Versuch wert (den Hinweis auf das Halteproblem
> > > kannst Du getrost als neunmalklug abtun).
> > Das denke ich nicht. Sie zeigt genau den wunden Punkt.
> Deine Ausfuehrungen sind sehr ueberzeugend. Nur zwei Fragen:
> 1. Was hat das mit Maschinenlernen zu tun?
unter welchen Bedingungen das prinzipiell geht. Maschinelles Lernen wäre ein
mögliches Verfahren, _wenn_ es geht. Insofern hätte ich früher das Topic
ändern sollen.
> 2. Wieviel entscheidbarer ist die Praesenz von Fehlern als die
> Laufzeit von Code?
>
Soweit ich die Ansätze kenne (ich bin zu faul, jetzt nochmal im Detail
nachzulesen), wird schlicht versucht zu erkennen, in welchen Kontexten
häufig welche Fehler auftreten, das sind die üblichen
Buffer-Overflow-Geschichten oder irgendwelche falschen Typisierungen etc.
Das kann unter Umständen einfacher sein. In C sind Fehler möglich, die in
vielen anderen Programmiersprachen prinzipbedingt nicht auftreten können
(buffer overflows in Ada? Lisp? ...?), und solche Fehler können ggf. auch
lokal auffindbar sein. Aber da bin ich kein Fachmann und darob vorsichtig
mich auf irgendwas festlegen zu lassen.
Klaus