Matroids Matheplanet Forum Index
Moderiert von Kleine_Meerjungfrau Monkfish epsilonkugel
Mathematik » Stochastik und Statistik » Schätzung einer binären Funktion
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Schätzung einer binären Funktion
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3338
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-01-20


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-01-21


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


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3338
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-01-21


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-01-21


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 :)


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6554
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-01-23


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.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3338
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-01-23


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6554
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-01-24


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-01-24


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.



-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-01-24


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.


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6554
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-01-24


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-01-24


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.



-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6554
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-01-24


@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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
raptrix
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.01.2020
Mitteilungen: 29
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-01-25


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?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-01-25


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" :)


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
raptrix
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.01.2020
Mitteilungen: 29
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2020-01-25


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2020-01-25


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


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
raptrix
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.01.2020
Mitteilungen: 29
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2020-01-26


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2020-01-27


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)


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
raptrix
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.01.2020
Mitteilungen: 29
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2020-01-27


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2020-01-30


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"...



-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
raptrix
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.01.2020
Mitteilungen: 29
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2020-02-01


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?


 





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2020-02-01


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.


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3338
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, vom Themenstarter, eingetragen 2020-02-01


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).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2020-02-02


Huhu :)

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

Grüße aus dem Harz
Gonz


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3608
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2020-02-03

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



-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3338
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, vom Themenstarter, eingetragen 2020-02-04


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
raptrix
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.01.2020
Mitteilungen: 29
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2020-02-04


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3338
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, vom Themenstarter, eingetragen 2020-02-06


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]