Die Mathe-Redaktion - 28.03.2020 15:14 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps für den MP

Werbung

Bücher zu Naturwissenschaft und Technik bei amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 545 Gäste und 16 Mitglieder online

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 

Antworte auf:  Schätzung einer binären Funktion von AnnaKath
Forum:  Stochastik und Statistik, moderiert von: Kleine_Meerjungfrau Monkfish epsilonkugel

[Zur Forum-Gliederung] [Wie man Fragen beantwortet]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Eingabehilfen (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-Bereich] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-Bereich][show-Bereich] [Quelltext [num.]][?]
 Zeige Vorschau      Schreibe im fedgeoFormeleditor oder mit Latex.

Smilies für Deine Nachricht:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3264
Herkunft: hier und dort (s. Beruf)
 Beitrag No.27, eingetragen 2020-02-06 02:24    [Diesen Beitrag zitieren]

Huhu,

tatsächlich kennt der Decoder die Wahrscheinlichkeiten nicht; tatsächlich ist es spannender, wenn man weniger Stopp-Bits hat (sonst reichen auch ziemlich schwache Modelle, wie sämtliche Bits als Stopp-Bits zu schätzen).

lg, AK.


raptrix
Aktiv
Dabei seit: 18.01.2020
Mitteilungen: 23
Herkunft:
 Beitrag No.26, eingetragen 2020-02-04 10:57    [Diesen Beitrag zitieren]

Den Wert von 1250 "im Leerlauf"kann ich reproduzieren, unser Verständnis von dem Modell scheint also zu passen.

Der Decoder kennt P(G) und P(S) nicht? Sonst wäre es ja auch langweilig.


AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3264
Herkunft: hier und dort (s. Beruf)
 Beitrag No.25, eingetragen 2020-02-04 01:02    [Diesen Beitrag zitieren]

Huhu gonz,

*** challenge accepted ***
stdout
Average costs: 57,03 vs. 1250, which is a reduction of 95,4376%

$k=50, n=100, m=50$ und $f$ randomly ($P(S)=0.2, P(G)=0.4$) sampled ($25000$ Runden).

lg, AK.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.24, eingetragen 2020-02-03 17:13    [Diesen Beitrag zitieren]
ASCII
binFunc 1.04 by gonz
Runden 300000 - mittleres Budget 16.12

Wobei es sicher noch besser geht... (Dies ist noch immer nicht der generische "Über-Decoder", von dem wir neulich gesprochen haben, der immer noch nicht läuft, sondern eine verbesserte Version des "ursprünglichen" Modells)

(da dies ja die "Baby Funktion" ist, sollte es an sich möglich sein, den tatsächlich optimalen Decoder zu finden)

Gutgelaunte Grüße
aus dem Binärfunktionen-Labor im dunklen Tann im Tiefen Tal -

Gerhard/Gonz


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.23, eingetragen 2020-02-02 08:21    [Diesen Beitrag zitieren]

Huhu :)

So, immerhin bin ich dann bei 19.6 angekommen, ich denke, die Herausforderung wird angenommen :)

Grüße aus dem Harz
Gonz


AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3264
Herkunft: hier und dort (s. Beruf)
 Beitrag No.22, eingetragen 2020-02-01 22:04    [Diesen Beitrag zitieren]

Huhu zusammen,

ich habe einen Decoder gebaut, der für $n$ Inputs und eine Funktion $f$, die aus einer unbekannten Anzahl Stopper- und Go-Bits besteht, m.E. recht gut abschneidet...

Vielleicht sollten wir das doch einmal als "Spiel" implementieren.

lg, AK.

PS. Für die konkrete Aufgabenstellung komme ich auf Kosten von $18.7$ (im Mittel).


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.21, eingetragen 2020-02-01 21:51    [Diesen Beitrag zitieren]

Ich habe einen decoder gebaut, der mit ziemlich einfachen Tests arbeitet, und auf ein mittleres Budget von unter 22 kommt (für die Aufgabenstellung aus #20)

Eher um den Programmrahmen zu testen. Es geht sicherlich deutlich besser mit einem generischen Ansatz.


raptrix
Aktiv
Dabei seit: 18.01.2020
Mitteilungen: 23
Herkunft:
 Beitrag No.20, eingetragen 2020-02-01 12:44    [Diesen Beitrag zitieren]

Ich habe inzwischen etwas programmiert (python ist ok) und spiele mit einer "Baby-Version" herum, wie folgt:

n = 5 Eingänge
alpha = 0.1 Wahrscheinlichkeit der Verfälschung eines Experiments in Phase I

m = 6 zufällige Testfälle in Phase II
k = 33 Preis einer falschen Antwort in Phase II

Ziel ist es, das "Gesamtbudget" aus Phase I und II zu minimieren.

Die Funktion f wird folgendermaßen definiert:

ist Eingang a_stop gesetzt, ist das Ergebnis immer 0,

ist Eingang a_stop nicht gesetzt, aber einer der Eingänge a_go_1 oder a_go_2 gesetzt, ist das Ergebnis 1,

andernfalls ist es null.

Zwei der Eingänge haben also keinen Einfluss auf das Ergebnis.

Dieses Modell hat den Vorteil, dass man tatsächlich noch alle Fälle betrachten kann, und ähnlich wie von Kitaktus in Post  #9 beschrieben vorgehen... (oder einfachere Überlegungen finden).


Falls jemand einen "Decoder" hierfuer bauen will, wären Funktionen vorzugeben, die

decoder_init

decoder_phase_I
- ggf. die Ergebnisse des vorhergehenden Testfalls mitgeteilt bekommt
- Entscheidet, ob Phase I verlassen werden soll,
- andernfalls neue Testdaten für das nächste Experiment liefert,

decoder_phase_II
- einen Testfall mitgeteilt bekommt und eine Antwort darauf zurückliefert

Wollen wir es eher als Rätsel betrachten, oder soll ich gelegentlich mal mein VOrgehen und die ersten Ergebnisse so in den Raum stellen?


 




gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.19, eingetragen 2020-01-30 11:16    [Diesen Beitrag zitieren]

Hallo Raptrix (und andere Interessierte!),

wie besprochen würde ich vorschlagen, auf m=1000 übergehen (einfach damit man nicht darauf spielen kann, dass in dem Sample in Phase II alle Eingaben die Ausgabe "0" ergeben). Da wir bei n=8192 die Folgen nicht einfach mal so posten können, würde ich sie per Datei übertragen.

Hier mal die Frage in die Runde: Hat noch jemand Interesse daran, das mal an diesem konkreten Beispiel durchzuspielen? Ich bin gedanklich ziemlich weit mit einem passenden "Decoder", aber... vielleicht habe ich irgendwo Denkfehler gemacht, und vielleicht geht es wesentlich effizienter.

Falls wir uns darauf einschießen, das Ganze in Form von Software zu gießen, wären aktuell C oder Python für mich das Mittel der Wahl (wobei man auch Encoder und Decoder getrennt als Programme bauen könnte, und eben die Daten austauschen, und ich im übrigen da auch recht flexibel bin).  

Lasst doch mal hören - so einfach im Sinne einer "Interessenbekundung"...


raptrix
Aktiv
Dabei seit: 18.01.2020
Mitteilungen: 23
Herkunft:
 Beitrag No.18, eingetragen 2020-01-27 12:00    [Diesen Beitrag zitieren]

Klar. Gesucht der Mindestwert für k, ab dem man besser spielen kann als in Phase I sofort zu passen und dann in der Phase II stehts auf "0" zu wetten.

Bisher alles Theorie, ich würde gerne mal eine der bisher diskutierten varianten praktisch durchspielen.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.17, eingetragen 2020-01-27 10:02    [Diesen Beitrag zitieren]

Hallo Raptrix,

Wenn du die Testfälle für Phase II so aussuchst, dass jeder Eingang unabhängig von den anderen in 50% der Fälle gesetzt ist, dann sind in den Ergebnissen bei deinem Modell deutlich weniger Vorkommnisse von "1" zu erwarten als die hier bisher diskutierten 50%, ist das berücksichtigt?

Bzw. gilt die Formel Budget = m*k/2 sicher nicht mehr, da man durch Antworten von durchgängig "0" in der Phase II deutlich besser abschneidet (und das sogar im Vorhinein weiß, also gar nicht erst durch Experimente in Phase I herausfinden muss)


raptrix
Aktiv
Dabei seit: 18.01.2020
Mitteilungen: 23
Herkunft:
 Beitrag No.16, eingetragen 2020-01-26 10:23    [Diesen Beitrag zitieren]

Ich biete folgendes an:

N = 8192 Eingänge
M = 100 Tests in Phase II
Alpha = 7.5 Prozent

Die Funktion, die ich gebastelt habe, entspricht den Vorgabe aus #6 - ich verrate aber mehr: relevant sind nur 12 Eingänge, davon sind 6 "Inhibitoren" und 6 sind "Katalysatoren". Sie wirken nach folgendem Schema:

- ist irgendein Inhibitor gesetzt, ist die Ausgabe immer "0"
- ist kein Inhibitor aber irgendeiner der Katalysatoren gesetzt, ist die Ausgabe "1"
- ist weder irgendein Inhibitor noch irgendein Katalysator gesetzt, kommt ebenfalls die "0".

Vorschläge erwünscht, für welches Budget ihr in die Versuchsreihe einsteigen würdet (also wie groß das k minimal sein sollte, damit man sinnvollerweise Versuche macht).

Bin Gespannt!

R.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.15, eingetragen 2020-01-25 12:30    [Diesen Beitrag zitieren]

Immer her damit. Funktionen habe ich reichlich :)
Per PN? Oder wollen wir einen Thread dafür aufmachen?


raptrix
Aktiv
Dabei seit: 18.01.2020
Mitteilungen: 23
Herkunft:
 Beitrag No.14, eingetragen 2020-01-25 12:22    [Diesen Beitrag zitieren]

Ich habe einen Algorithmus ausgeknobelt. Mag jemand sich passende Funktionen ausdenken, um ihn zu testen?


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.13, eingetragen 2020-01-25 10:24    [Diesen Beitrag zitieren]

2020-01-25 09:53 - raptrix in Beitrag No. 12 schreibt:

Wäre eine verallgemeinerung des modells aus #7 wie folgt:  

ist x die anzahl der für die funktion erlaubten bauteile, dann ist 2^x = n ? Oder passt das nur zufällig hier? Andersherum, ist die erwartete anzahl der relevanten eingänge der zweierlogarithmus der gesamtzahl der eingaenge?

Ich würde mal sagen - "das macht Sinn" :)


raptrix
Aktiv
Dabei seit: 18.01.2020
Mitteilungen: 23
Herkunft:
 Beitrag No.12, eingetragen 2020-01-25 09:53    [Diesen Beitrag zitieren]

ich glaube so wie beschrieben würde ich einsteigen und hoffen, 10 Taler aus dem budget einsparen zu können

Wäre eine verallgemeinerung des modells aus #7 wie folgt:  

ist x die anzahl der für die funktion erlaubten bauteile, dann ist 2^x = n ? Oder passt das nur zufällig hier? Andersherum, ist die erwartete anzahl der relevanten eingänge der zweierlogarithmus der gesamtzahl der eingaenge?



Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6274
Herkunft: Niedersachsen
 Beitrag No.11, eingetragen 2020-01-24 18:49    [Diesen Beitrag zitieren]

@AnnaKath:

Falls Dich das Problem aus praktischen Gründen interessiert.
Ein wirkungsvolles Mittel zur Modellierung unbekannter Funktionen ist der Gauß-Prozess.
Frage mich bitte nicht nach Details, ich bin da kein Fachmann.

Ich kann Dir z.B. nicht sagen, wie gut die Methode für diskrete Probleme geeignet ist.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.10, eingetragen 2020-01-24 18:13    [Diesen Beitrag zitieren]

Schön da kommt ja Bewegung in die Sache :) Ich muß zugeben, dass es Spass macht, sich gedanklich damit auseinanderzusetzen.

2020-01-24 17:41 - Kitaktus in Beitrag No. 9 schreibt:
Den von gonz in (***) erwähnten Ansatz, dass Alice die in Phase II abgefragten Ergebnisse verwenden kann, um ihr Modell weiter zu verbessern, würde ich gerne verwerfen. Mir ist klar, dass das in der Praxis wertvolle Informationen sind, aber im Interesse der Einfachheit, würde ich diese Möglichkeit gerne weglassen.

Das können wir gerne machen.

Für die Begrenzung der "Komplexität" der Funktion f ist das ggf. auch ein etwas verspiel/komplizierter Ansatz, ich bin darauf gekommen, weil AK ja immer mal von der "OR Verknüpfung" sprach, und weil man sich das ganz gut vorstellen kann. Natürlich könnte man auch sagen "maximal x der Eingänge tragen zum Ergebnis bei, das durch eine frei wählbare (und bei kleinem x dann wirklich per Tabelle definierbare) x-stellige logische Funktion ermittelt wird.  

Wenn man es eh programmiert, ist aber auch die Anzahl der Schaltungen, die man mit max. zB eben drei solcher Bausteine aufbauen kann, recht überschaubar. Also würde ich gerne dabei bleiben.

Genauso wie Alice in Phase I auch "on the fly" über weitermachen oder aufhören entscheiden kann (alternativ hätte man ihr natürlich auch vorab eine Angabe der Testzahl und eine Liste der Testfälle abverlangen können).

Was es aber auch weniger spannend macht, wie ich finde.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6274
Herkunft: Niedersachsen
 Beitrag No.9, eingetragen 2020-01-24 17:41    [Diesen Beitrag zitieren]

Den von gonz in (***) erwähnten Ansatz, dass Alice die in Phase II abgefragten Ergebnisse verwenden kann, um ihr Modell weiter zu verbessern, würde ich gerne verwerfen. Mir ist klar, dass das in der Praxis wertvolle Informationen sind, aber im Interesse der Einfachheit, würde ich diese Möglichkeit gerne weglassen.


Wenn ich Alice wäre und beliebige (Speicher- und Rechen-)Ressourcen hätte, würde ich folgendes machen:
a) Auflistung aller möglichen Funktionen (es sind ja nur $2^{(2^8)}$) und a priori Bewertung ihrer Wahrscheinlichkeit. In gonz' Beispiel würden bspw. alle Funktionen, die sich nicht mit 3 Logik-Bausteinen darstellen lassen, den Wert 0 bekommen.
b) Durchführung der / eines Tests (Wobei allein die Auswahl der Tests alles andere als trivial ist.)
c) Neuberechnung der bedingten Wahrscheinlichkeiten für die in a) ermittelten Funktionen.
d) Für jede mögliche Eingabe: Bewertung (gemäß der Wahrscheinlichkeitsverteilung aus c)) welche Ausgabe am wahrscheinlichsten ist [Wohlgemerkt: Ich muss nicht entscheiden, welche Funktion die wahrscheinlichste ist, sondern welches Ausgabeergebnis!(*)]
e) Die konkreten Wahrscheinlichkeiten aus d) liefern mir auch eine Schätzung, wie erfolgreich mein Modell sein wird. Die kann ich verwenden, um zu entscheiden, ob weitere Tests sinnvoll sind und sie gibt mir eine Basis für die Auswahl der Tests in b).

Puh, das ist ein ganz schöner Brocken.

(*) Beispiel: Wir haben drei Variablen und wissen nur, dass die Funktion genau zwei dieser Variablen Oder-verknüpft. Sind 0, 2 oder 3 der Eingangsgrößen gleich 1, dann können wir das Ergebnis exakt vorhersagen.
Ist dagegen genau eine Eingangsgröße gleich 1, so würden wir in allen drei Fällen optimalerweise auf die Ausgabe 1 tippen, obwohl uns klar ist, dass eine Funktion, die in allen drei Fällen das Ergebnis 1 liefert, garantiert falsch ist.


Übrigens: Die ganze Frage erinnert mich an einen (eher populärwissenschatlichen) Artikel, den ich als Student geschrieben haben.
Man hat eine Reihe von (gleichgroßen, gleichvollen) Kisten mit Gold- und Silbermünzen. Eine Kiste enthält nur Gold, bei allen anderen ist Gold und Silber 1:1 gemischt.
Man hat nun in eine begrenzte Anzahl von Versuchen. Dabei darf man in eine beliebige Kiste blind hineingreifen, eine Münze ziehen und sich anschauen (**). Die Münze wird danach zurückgelegt.
Am Ende soll man sich entscheiden, welche Kiste nur Gold-Münzen enthält.
Die optimale Strategie entsprach dabei nicht der (naiven) Intuition, was ich damals ganz nett fand und was mich dann zum Schreiben des Artikels veranlasste.

(**) Ja, ok, man könnte beim Tasten versuchen das spezifische Gewicht der Münzen zu vergleichen ... Also gut, die Münzen liegen einzeln in kleinen Schachteln und wir dürfen nur auf eine Schachtel zeigen, die dann geöffnet wird.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.8, eingetragen 2020-01-24 14:25    [Diesen Beitrag zitieren]

2020-01-21 20:33 - AnnaKath in Beitrag No. 2 schreibt:
Derzeit vermute ich, dass man mit $2n/(1-\alpha)^2$ Schätzungen sinnvoll sind, wenn $f$ keine Gestalt hat, die sich bereits frühzeitig "erahnen" lässt.
lg, AK.


Das wären hier 2*8/(0.925)² < 20. Es sollte also selbst bei k=5 und m=10 lohnen zu testen. Ich habe die Beschreibung oben mal angepasst.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.7, eingetragen 2020-01-24 12:39    [Diesen Beitrag zitieren]

Achtung - jetzt die zweite, editierte Version. Es hatte sich ein Dreher in den Konstantenbezeichnern eingeschlichen und ich habe noch Erläuterungen eingefügt.

Und - dritte Version - den Wert für k renormiert nach der von AK vermuteten Formel aus Beitrag #2


Ich schlage mal folgendes Minimalmodell vor (konkrete Werte der Parameter können gerne noch angepasst werden - insbesondere kenne ich den "Wert des Spiels" nicht, weiß also nicht, ob es lohnt hier "Messungen vorzunehmen", aber wir können uns daran ja vielleicht mal abarbeiten).

Wir betrachten eine "Experimentierbox".

Es sei n=8, das heißt der Experimentator, nennen wir ihn mal Alice, sieht 8 Eingänge, die genau den Wert "0" oder "1" zulassen (wollten wir es in Hardware bauen, würde an jedem Eingang ein Schalterchen sein, das zwei Stellungen einnehmen kann). Es gibt einen Ausgang, an dem am Anfang (sagte ich, daß wir uns in Phase I des Experiments befinden?) eine Lichtlein angeschlossen ist, das (um zu wissen, dass es nicht kaputt ist) in den beiden Farben "weiß" oder "rot" leuchten kann, aber erst einmal aus ist.

Außerdem gibt es einen freundlichen einladenden grünen "GO" Taster an der Box, durch den Alice jetzt beliebig viele Experimente ausführen kann, bevor sie die Phase I für beendet erklärt. Sei es, weil sie meint nun genug über die Box zu wissen, sei es, weil sie meint, dass weitere Experimente sich nicht mehr lohnen. Damit sie den Überblick behält, ist an der Box eine Leuchtziffernanzeige angebracht, die die Anzahl der durchgeführten Experimente mitzählt.

Jedes Experiment kostet einen Taler (*) (es kann genau ein Taler sein, da wir damit den Wert der "Geldeinheit" eichen). Es läuft so ab: Alice stellt die acht Schalter auf einen beliebigen Wert ein (faktisch, für Informatiker, gibt sie damit eine beliebige 8-bit Zahl vor) und drückt dann GO. Damit wird der Experimentzähler um eins erhöht (wie logisch) und die Lampe an der Ausgabe leuchtet entweder "weiß" oder "rot" auf (lange genug, damit Alice es sich notieren kann).

Alice weiß folgendes über den inneren Aufbau der Box: Die Eingänge sind intern über eine Logik zu einem "wahren Wert" verschaltet. Sie bilden also eine Funktion f:{0|1}^8 -> {0|1} aus.

Alice weiß, dass diese Funktion in gewissen Sinne einfach ist, nämlich dass sie aus insgesamt nur drei der Elemente AND, OR, XOR (jeweils zweistellig) oder NOT (einstellig) aufgebaut ist. Damit können auch nur maximal vier der Eingänge überhaupt etwas zu dem Experiment beitragen.

Außerdem ist aber in Phase I ein Randomizer nachgeschaltet. Dieser invertiert in 7.5% der Experimente den Output (und ist von den Eingängen unabhängig).

Nun kommen wir zur Phase II. Hier kann es teuer werden. Die Box wird nun umgeschaltet, und Alice muss Tests der folgenden Form durchführen. Diesmal ist die Box anders herum beschaltet:

Box-intern wird für jeden Test eine beliebige zufällige Belegung der Eingänge vorgenommen, die außen in Form von n Lämpchen abgelesen werden kann. Die Box erzeugt mit diesen Werten intern einen nicht sichtbaren Output mit der auch in Phase I verwendeten Schaltung, allerdings ist der Randomizer jetzt ausgeschaltet. Alice kann über Schalter "Weiß" oder "Rot" wählen, welchen Wert sie erwartet. Wird dann "GO" gedrückt, wird dieser Wert mit dem internen Wert verglichen und das Ergebnis ausgegeben (sowie der Testzähler erhöht).

Dieser Test in Phase II muss von Alice m=10 mal ausgeführt werden (um nicht  wieder die Zahl acht anzuführen), und für jeden der Tests, in dem das Ergebnis nicht zur Eingabe passt, wird eine Summe von k=5 Talern fällig. (**)

Je nachdem kann die Phase II also Alice etwas zwischen 0 und 50 Talern kosten. Da sie mit "Raten" wahrscheinlich um die 50% Treffer erzielt, wird sie diese Phase, wenn sich ihre Erkenntnisse aus Phase I als nutzlos erweisen,  etwa 25 Taler kosten (***). Damit haben wir auch 25 als oberste Grenze dafür, wieviele Tests man sinnvollerweise überhaupt in Phase I ausführt.

Deshalb hat Alice ein Budget von 25 Talern (es soll für sie ja irgendeinen Anreiz geben).

Habe ich das so richtig verstanden? Wenn ja könnten wir
a) darüber theoretisieren, und/oder
b) dieses Modell (in Form von Software!) bauen, um daran mal Dinge auszuprobieren....

oder herausfinden, ab welchem Wert von k es lohnt, für ein Budget von m*k/2 Talern die Forschungsarbeiten aufzunehmen...

Unverbindliche Grüße aus dem Oberharz
Gerhard/Gonz

(*) Alice braucht nicht vorab zu entscheiden, wieviele Experimente sie machen will, sondern kann nach jedem Experiment entscheiden, weiterzumachen oder aufzuhören. Das stellt einen gewissen Nutzen für sie dar, ich weiß aber noch nicht, wie groß der Vorteil dadurch für sie ist.
 
(**) Es macht die Konstruktion der Box einfacher, wenn die Eingangswerte für jeden Test zufällig neu ermittelt werden - damit können auch bei zwei oder mehr Tests dieselben Werte abgefragt werden.

(***) Da Alice das Ergebnis mitgeteilt bekommt, bevor sie den nächsten Test startet, kann sie in diesem Fall sicher punkten und damit macht sie auch bei einem Budget von k*m/2 im Mittel ein kleines Plus, wenn sie nur rät. Hat sie mehrere mögliche Theorien darüber, wie f funktioniert, kann sie ggf. ihre Vorstellung von der Box auch noch während der Phase II nachjustieren.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6274
Herkunft: Niedersachsen
 Beitrag No.6, eingetragen 2020-01-24 00:31    [Diesen Beitrag zitieren]

Als konstruktiven Beitrag werfe ich mal den Suchbegriff "Design of Experiments (DoE)" in den Raum.
Da beschäftigt man sich mit genau solchen Fragen.
Dein Problem ist ja praktisch hochgradig relevant.

Ansonsten grüble ich noch etwas, ob sich irgend eine Formalisierung des Problems finden lässt, die man mathematisch angehen kann.


AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3264
Herkunft: hier und dort (s. Beruf)
 Beitrag No.5, eingetragen 2020-01-23 20:48    [Diesen Beitrag zitieren]

Huhu Kitaktus,

wir haben ein wenig über das Problem gesprochen; und ja, sollte $f$ völlig "zufällig" (in welchem Sinne auch immer) sein, so wäre es sinnlos, zuvor zu testen.

Tatsächlich ist es eine Frage des Wissens (bzw. der Vermutung) über $f$. ich habe nicht viel über das praktische Problem verraten, aber (durch den kleinen Zusatz "physikalisch realisiert") angedeutet, dass mein praktisches Problem zumindest die gut begründete Vermutung zulässt, dass $f$ eine gewisse Struktur ausweist (also durch weniger Information - in welchem Sinne auch immer - zu beschreiben ist als eine Tabelle mit $2^n$ Einträgen benötigt).

Praktisch vermute ich, dass etwa 90% der Inputgrößen keinerlei Einfluss auf das Ergebnis hat und die restlichen einen recht einfach strukturierten: Teils im Sinne einer XOR-Verknüpfung, teils als Summanden, die einen Output von $1$ erzeugen, wenn eine gewisse Schwelle überschritten wird .

Setzen wir gedanklich eimal $\alpha=0$. Dann wäre die Schätzphase sinnvoll, wenn die a-priori-Wahrscheinlichkeit ("belief") $\beta$, dass $f$ irgendwie "einfach" ist, groß gegenüber dem potentiellen Verhältnis zusätzlicher Kosten ist. Dies genauer zu spezifizieren ist meine eigentliche Motivation. Praktisch gehe ich von $\beta>0.95$ aus.

Nun ist die Beobachtung von $f(x)$ verrauscht, und mit steigendem $\alpha$ wird die Schätzphase zunehmend unsinnig (für $\alpha> 0.5-2^{-n}$ sogar völlig sinnlos). Das erschwert die Überlegung aber m.E. nur unwesentlich.

lg, AK.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6274
Herkunft: Niedersachsen
 Beitrag No.4, eingetragen 2020-01-23 12:38    [Diesen Beitrag zitieren]

Ich habe das Problem noch nicht ganz verstanden, was vielleicht auch an dem mehrfach vorkommenden k liegt.

Verstehe ich das richtig, Du hast einen riesigen Raum mit 2n Elementen. Einige wenige davon kannst Du durch ein Experiment testen (und die Ergebnisse sind auch noch fehlerbehaftet) und sollst danach einen Tipp für m zufällig gewählte Elemente abgeben?

Ich schreibe davon, dass man nur einige wenige Elemente testen kann. Führt man kein Experiment durch (Kosten 0), dann sind die maximalen Kosten in der zweiten Phase m*k. Macht man also mehr als m*k Experimente, dann ist man nicht kostenoptimal. m*k ist in Deinem Beispiel aber klein im Verhältnis zu 2n.
Die Antwort hängt also sehr von der Struktur von f ab und davon, wie viel ich von der Struktur vorab weiß. Ist f mehr oder weniger zufällig, dann sollte ich gar keine Experimente machen, weil mir die wenigen Datenpunkte wahrscheinlich gar nichts nützen, ist f dagegen "gutmütig" (z.B. f(x)=1, wenn mindestens r Koordinaten von x gleich 1 sind), dann können einige Experimente sehr lohnend sein.



gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.3, eingetragen 2020-01-21 20:36    [Diesen Beitrag zitieren]

Ich meinte die Schätzphase. Durch das Abgeben von Zufallswerten in der _Testphase_ trifft man ja in 50% der Fälle und kann wenigstens die Kosten in etwa halbieren...

Ok, ich muß da nochmal nachgrübeln :)


AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3264
Herkunft: hier und dort (s. Beruf)
 Beitrag No.2, eingetragen 2020-01-21 20:33    [Diesen Beitrag zitieren]

Huhu Gonz und Danke für Deine Anmerkung,

die "Testphase" ist ja nicht optional. Diese erfolgt in jedem Falle (und man dürfte wahrscheinlich recht spürbare Kosten erleiden, wenn mann kann keine Schätzung abgibt; um die Aufgabenstellung zu präzisieren: man würde dann $mk$ "Bestrafung" erleiden - ein nicht abgegebener Test gilt also als falsch!).

Derzeit vermute ich, dass man mit $2n/(1-\alpha)^2$ Schätzungen einen vernünftigen Plan hat, wenn $f$ keine Gestalt hat, die sich bereits frühzeitig "erahnen" lässt.

lg, AK.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3404
Herkunft: Harz
 Beitrag No.1, eingetragen 2020-01-21 11:01    [Diesen Beitrag zitieren]

Hallo AK,

das ist eine schöne Aufgabenstellung (wir hatten ja schon im chat darüber geplaudert). Für die angegebenen Beispielparameter würde ich aktuell tippen, daß es überhaupt nicht lohnt zu testen, es sei denn, man kann irgendwelche zusätzlichen Annahmen über die Funktion f treffen. Das ließe sich m.M.n auch vorrechnen oder am Beispiel demonstrieren.

Grüße
und ich bin gespannt auf weitere Ideen

Gerhard/Gonz


AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3264
Herkunft: hier und dort (s. Beruf)
 Themenstart: 2020-01-20 23:11    [Diesen Beitrag zitieren]

Hallo zusammen,

ich habe ein praktisches Problem, bei dem mir vielleicht jemand einen Hinweis geben kann. Bis auf ein paar Simulationen und einfache Spezielfälle habe ich leider keinen rechten Ansatz, wie man das Ganze umfassend angehen soll.

Man betrachte eine (sagen wir physikalisch realisierte) Abbildung $f:Z^n\rightarrow Z$ (mit $Z=\{0,1\}$).
Ziel ist es, diese Funktion im folgenden Sinne optimal zu schätzen: Es wird zufällig ein $m$-dimensionaler Vektor mit $x^{(j)}\in Z^n$ für $1\leq j\leq m$ gezogen und dann eine Schätzung $y\in Z^m$ verlangt. Es entstehen "Kosten" für den Schätzenden in Höhe von $k\sum|y^{(j)}-f(x^{(j)})|$ mit $k>1$. Wir nennen diese Phase "Testphase".

Für die Schätzung (also eine vorgelagerte Phase) darf der Experimentator eine beliebige Anzahl von Realisationen $f(x^{(k)})$ für von ihm gewählte Inputs $x^{(k)}$ ermitteln (lassen). Aufgrund des Aufwands des physikalischen Experiments entstehen dabei Kosten in Höhe von $1$ je Durchführung.
Allerdings ist das Ergebnis "verrauscht", d.h. für ein in dieser ersten ("Schätz-")Phase durchgeführtes Experiment mit Input $x$ kann nicht $f(x)$ beobachtet werden, sondern eine Zufallsvariable $Y_x$, für die $P(Y_x=f(x))=1-\alpha$ mit $\alpha\in(0,0.5)$ gilt.

Die Frage ist nun, welche Strategie man nutzen soll, um in der Schätzphase ein Modell für $f$ zu ermitteln, so dass die Gesamtkosten (also die Schätzkosten in der erste Phase zuzüglich der anfallenden Kosten für die Abweichung der Prognose in der Testphase) möglichst minimal (im Erwartungswert) sind.

Als konkretes Beispiel habe ich eine Situation in der etwa $n=10000, m=300, \alpha=0.075$ sowie $k=100$ gilt.

Für jede Anregung dankbar,
AK.


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]