| Zeige Beiträge 1 bis 15 von 18 Treffern |
Seiten (2): [1] 2 nächste » |
 Thema: Entscheidungsbaeume - Klassifizierung bei Widerspruch |
|
|
Hallo!
Ich beschaeftige mich gerade ein wenig mit Decision Trees und bin mir dabei nicht ganz sicher, wie ich ein Beispiel einsortieren soll, wenn sich meine Trees "widersprechen".
Aalso, folgende Situation:
Ich moechte 6 Decision Trees auswerten, die Gesichtsausdruecke erkennen. Jeder der Decision Trees ist auf eine Emotion trainiert, beispielsweise "Aerger". Die Attribute beziehen sich auf Muskelkontraktionen im Gesicht.
Wenn ich jetzt ein Beispiel habe, e1, in dem Muskel A1,A2 und A3 aktiv sind und zwei (oder keiner) meiner Decision Trees sagen, dass das ihre Emotion sei, wie soll ich dann mit dem Beispiel fuer die Statistiken wie ConfusionMatrix etc umgehen?
Einfach rausschmeissen oder vielleicht zufaellig eine der zutreffenden Emotionen waehlen?
Gibts da eine Standardvorgehensweise?
Dankeschoen!
PS. Entschuldigt die vielen englischen Begriffe, aber studiere das gerade auf Englisch...
|
|
| Thema: dnf knf... |
|
|
hallo jo!
Musst du aus so einer Formel wirklich "nur" die Wertetabelle erstellen?
Dann ist das eigentlich nicht weiter schwierig.
![[latex] \begin{vmatrix} a & b & c & a \cdot \bar{b} & \bar{a} \cdot b & abc & alle drei & negiert\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \\0 & 1 & 1 & 0 & 1 & 0 &1\\1 & 1 & 1 & 0 & 0 & 1 & 1 \end{vmatrix} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \begin{vmatrix} a & b & c & a \cdot \bar{b} & \bar{a} \cdot b & abc & alle drei & negiert\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \\0 & 1 & 1 & 0 & 1 & 0 &1\\1 & 1 & 1 & 0 & 0 & 1 & 1 \end{vmatrix} )
Das heißt du versuchst einfach deine Formel ein wenig aufzudröseln, machst dann die Tabelle für die Teile einzeln und fügst dann zusammen.
Du musst natürlich wissen, was die Negation ist, was UND, ODER und so bedeuten.
Aber sonst dürfte das doch so hinhauen, oder? 
|
|
| Thema: Komplexitätsbeweis |
|
|
ähm...ich bin ein Meister darin mich im nachhinein nochmal zu verwirren:
Aber...jetzt denke ich auf einmal, dass du genau die falsche Implikation als richtig voraussetzt.
Meiner Meinung nach gilt:
![[latex] \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Rightarrow g \in O(f) \mbox{ ohne } \Theta(f) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Rightarrow g \in O(f) \mbox{ ohne } \Theta(f) )
aber
![[latex] \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Leftarrow g \in O(f) \mbox{ ohne } \Theta(f) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Leftarrow g \in O(f) \mbox{ ohne } \Theta(f) )
gilt nicht.
Da zieht doch auch ein Beispiel:
g(n) = f(n) , dann ist ![[latex] g(n) \in O(f(n)) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? g(n) \in O(f(n)) ) aber ![[latex]\lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 1)
|
|
| Thema: Komplexitätsbeweis |
|
|
du hast recht, danke dir! 
Ist aber schade, wäre ein schönes Werkzeug gewesen 
|
|
| Thema: Komplexitätsbeweis |
|
|
Hallo!
Zeigen Sie: ![[latex] e^{f(n)} \in O(e^{g(n)}) \Rightarrow f(n) \in O(g(n)) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? e^{f(n)} \in O(e^{g(n)}) \Rightarrow f(n) \in O(g(n)) )
f(n) und g(n) sind monoton steigend und größer null.
Ich könnte das über die Definition beweisen.
Jetzt frage ich mich aber, ob es auch mit dem limes geht.
Ist folgendes äquivalent?
![[latex] e^{f(n)} \in O(e^{g(n)}) \stackrel{?}{\Leftrightarrow} \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0[/latex]](http://www.matheboard.de/latex2png/latex2png.php? e^{f(n)} \in O(e^{g(n)}) \stackrel{?}{\Leftrightarrow} \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0)
Dann würde ja nach Voraussetzung gelten:
![[latex] \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0 [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0 )
Jetzt ist die Frage, welche Voraussetzungen ich genau brauche, damit ich:
![[latex] \lim_{n \to \infty} \frac{f(n)}{g(n)}=0 [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty} \frac{f(n)}{g(n)}=0 ) folgern kann.
Überhabt irgendwelche? Ich kann ja einfach im Zähler und Nenner die ln Funktion anwenden....
Danke für eure Hilfe!
|
|
| Thema: Algorithmus für maximalen Pfad gesucht |
|
|
Hallo!
Vielleicht hat ja jemand mal Lust darüber nachzugrübeln.
Also gesucht ist ein Alogrithmus der in einem Baum mit positiv gewichteten Kanten die zwei Knoten sucht, die den maximalen Abstand voneinander haben und sich diesen Abstand auch merkt.
Die Laufzeit soll O(|V|) sein (V ist die Menge der Knoten).
Der Algorithmus ist zu beschreiben und begründen, muss also nicht unbedingt wirklich in einer Programmiersprache geschrieben werden.
Mein bisheriger Ansatz:
Wobei ich nicht ganz sicher bin, ob das O(|V|) ist? Was ist eig. der Unterschied zu O(V)?
Also, man muss für jeden Knoten seine 2 größten Kinder suchen. Kinder, die nicht eines der zwei größten sind, können mit eventuellem Unterbaum fallen gelassen werden (z.B. aus einer Liste gelöscht werden).
Die Werte der zwei größten Kinder und die Namen der Kinder müssen im Vater gespeichert werden.
Als Größe eines Knotens bezeichne ich die die maximal 2 Zahlen, die in ihm stehen + die verbindene Kante zum Papa.
Blätter haben also den Wert 0, mit ihnen fängt man an und aus ihnen baut man am Anfang eine Liste, aus der gestrichen wird.
Am Ende stehen die beiden gesuchten Knoten in der Wurzel und die SUmme der beiden Werte der Wurzel ist der gesuchte Abstand.
Ist das verständlich?
Was sagt ihr dazu?
|
|
| Thema: Kontextsensitive Grammatik finden |
|
|
Hallo!
Ich möchte eine kontextsensitive Grammatik zu dieser Sprache finden:
![[latex] L = \{ a^{2^k} | k \geq 0 \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? L = \{ a^{2^k} | k \geq 0 \} )
Schwierigkeiten macht mir vor allem die Bedingung, dass linke Regelseiten höchstens so lang wie rechte Regelseiten sein dürfen.
Hier meine Idee:
S -> VXaH | a
Xa -> aaX
XH -> YH
aY -> Ya
VY -> VX
V -> epsilon
XH->epsilon
Erläuterung:
Die Grammatik basiert auf der Idee, dass ich jedes a, was schon vorhanden ist, verdoppeln muss, "um auf die nächste Stufe zu kommen".
Die Terminalsymbole V,H bezeichnen "Vorne" und "Hinten" im Wort, und sollen dafür sorgen, dass die Grammatik eindeutig ist.
Die Variable X wandert immer von links nach rechts und verdoppelt dabei alle as. Die Variable Y wandert nur zurück, falls man eine Ebene weiter will.
Das Problem ist, dass ich diese beiden Regeln mit Epsilon unten habe und ich dabei eine Bedingung von kontextsensitiven Sprachen verletze.
Jemand eine Idee, wie ich die wegkriege?
|
|
| Thema: Beweis zur Komplexität |
|
|
hi!
ja, vielleicht sollten wir die Beträge weglassen.
Obere Schranke verstehe ich, hatte ich ja auch so.
Zur unteren Schranke:
Wieso soll denn ![[latex] c \cdot f(n) \leq c \cdot f(n) + h(n) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? c \cdot f(n) \leq c \cdot f(n) + h(n) ) gelten?!
Ich behaupte das ist falsch, weil wir ja nun h(n)>0 annehmen (vgl. beträge)...
|
|
| Thema: Beweis zur Komplexität |
|
|
| Zitat: |
Original von Tobias
Du darfst sogar annehmen, dass |h(n)| echt kleiner als c'*|g(n)| ist, denn h ist in o(g) und nicht bloß in O(g)
|
okay, stimmt, aber ich dachte das mir die Erkenntnis keinen Vorteil bringt.
Zu den Beträgen:
Ich bin gerade leider etwas verwirrt. Wieso ist es mir bei der oberen Schranke egal? Sollte ich hier nicht nach oben abschätzen statt nach unten um "auf der sicheren Seite" zu sein?
Ich weiß, dass ich da schonmal Schwierigkeiten hatte sowas nachzuvollziehen..
Und wie kriege ich nun die jeweils andere Seite in den Griff?
Außerdem:
Mit den Beträgen hast du natürlich recht. Die tauchen bei unserer Definition nicht auf, aber da wurden die Funktionen f und g auch positiv definiert. Da nun davon nichts in der Aufgabe steht, muss ich das wohl jetzt berücksichtigen.
|
|
| Thema: Beweis zur Komplexität |
|
|
Hallo!
Folgendes ist zu zeigen oder widerlegen:
![[latex] f \in \Theta(g) \wedge \lim_{n \to \infty} {\frac{h(n)}{g(n)}}=0 \Rightarrow f+h \in \Theta(g)[/latex]](http://www.matheboard.de/latex2png/latex2png.php? f \in \Theta(g) \wedge \lim_{n \to \infty} {\frac{h(n)}{g(n)}}=0 \Rightarrow f+h \in \Theta(g))
Also die gegebenen Voraussetzungen dürften sich ja wie folgt übersetzen lassen:
![[latex]\exists c>0 \exists n_0>0 \forall n \geq n_o : g(n)/c \leq f(n) \leq cg(n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\exists c>0 \exists n_0>0 \forall n \geq n_o : g(n)/c \leq f(n) \leq cg(n))
![[latex]\exists c'>0 \exists n_0'>0 \forall n \geq n_o' : h(n) \leq g(n) \cdot c'[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\exists c'>0 \exists n_0'>0 \forall n \geq n_o' : h(n) \leq g(n) \cdot c')
Daraus folgt:
![[latex] h(n)+g(n)/c \leq f(n)+h(n) \leq g(n)c+g(n)c' [/latex]](http://www.matheboard.de/latex2png/latex2png.php? h(n)+g(n)/c \leq f(n)+h(n) \leq g(n)c+g(n)c' )
Wenn ich jetzt abschätze, dann käme ich doch auf:
![[latex] g(n)c' + g(n)/c \leq f(n)+h(n) \leq g(n) \cdot (c+c') [/latex]](http://www.matheboard.de/latex2png/latex2png.php? g(n)c' + g(n)/c \leq f(n)+h(n) \leq g(n) \cdot (c+c') )
Dann müsste doch gelten:
![[latex] c' + \frac{1}{c} = \frac{1}{c+c'} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? c' + \frac{1}{c} = \frac{1}{c+c'} )
Was ich zu einer Beziehung zwischen c und c' auflösen kann, und sehen kann, dass c' >= 2 sein muss.
Wenn das dann gilt, dürfte die Aussage stimmen, oder?
Hoffe auf Antwort!
aRo
|
|
| Thema: Grammatik für Sprache |
|
|
wie genau meinst du das?
für irgendeine Sprache?
Das ist oft nicht möglich, vielleicht möchtest du deine Frage etwas präzisieren?
Hier ein kleines Beispiel, bei dem es geht:
Aufgabe:
Finde eine kontextfreie Grammatik, die folgende Sprache erzeugt:
![[latex] L = \{a^i b^i | i > 0 \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? L = \{a^i b^i | i > 0 \} )
Die Grammatik sähe dann einfach so aus:
![[latex] S \to aSb | ab [/latex]](http://www.matheboard.de/latex2png/latex2png.php? S \to aSb | ab )
okay?
|
|
| Thema: Realisierung eines Schaltnetzes ausschließlich mit NOR |
|
|
Hallo!
Die Aufgabe ist die Funktion:
![[latex] f(x_1,x_2,x_3)=(x_1+x_2+\bar{x_3}) \cdot (x_1+\bar{x_2}+x_3) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? f(x_1,x_2,x_3)=(x_1+x_2+\bar{x_3}) \cdot (x_1+\bar{x_2}+x_3) ) mit möglichs wenigen NOR Gattern zu realisieren.
Die Lösung findet ihr im Anhang. Diese Lösung gefällt mir jedoch nicht, bzw. ich kann sie gerade nicht nachvollziehen. Ich hätte 13 NOR-Gatter gebraucht.
Ich weiß leider grad nicht, wie ich euch meine Lösung präsentieren soll.
Aber vielleicht könnt ihr mir ja schon so erklären, warum das anscheinend schon so funktioniert.
Danke.
Hier ist die Lösung (sorry, wie geht das hier nochmal im Board direkt?)
|
|
|
| Zeige Beiträge 1 bis 15 von 18 Treffern |
Seiten (2): [1] 2 nächste » |
|
|
