|
|
|
|
|
|
|
| | Zitat von PutzFrau
| | Zitat von Irdorath
Kann jemand ne Anleitung empfehlen zu numerischer Faltung?
Ich will
loesen, wobei (beispielhalber) f die Dichtefunktion und G die Verteilungsfunktion (verschiedener) Normalverteilungen seien.
Also ungefaehr so:
https://i.imgur.com/Kr1WlKz.png
Jetzt ist heuristisch klar: Fuer grosse x ist G ungefaehr 1, also
und fuer sehr kleine x ist G ungefaehr 0, also
Auch ist klar, da G < 1,
Insgesamt erwarte ich also fuer die Faltung ne leicht pervertierte, nach links verschobene Variante der orangenen Kurve.
Die numerischen Loesungen, d.h. scipy ( ) verlangen tendenziell eine Diskretisierung der zu faltenden Funktionen, schweigen sich aber leider darueber aus, wie diese (Diskretisierungs-)Vektoren interpretiert werden? 
| |
| Code: |
import numpy as np
import scipy.stats as st
from scipy.signal import fftconvolve
import matplotlib.pyplot as plt
def f(x):
return st.norm.pdf(x)
def G(x):
return st.norm.cdf(x, loc=3)
delta = 0.001
sym_grid = np.arange(-20, 20, delta)
grid = np.arange(-10, 20, delta)
long_grid = np.arange(-100, 200, delta)
sym_conv = fftconvolve(f(sym_grid), G(sym_grid), "same") * delta
conv = fftconvolve(f(grid), G(grid), "same") * delta
long_conv = fftconvolve(f(long_grid), G(long_grid), "same") * delta
fix, ax = plt.subplots(1, 3)
ax[0].plot(sym_grid, sym_conv)
ax[0].set_title("symmetric grid")
ax[1].plot(grid, conv)
ax[1].set_title("short grid")
ax[2].plot(long_grid, long_conv)
ax[2].set_title("long grid")
plt.show()
|
|
https://i.imgur.com/YFlBnz5.png
Wieso haengen die Loesungen von den Grenzen der gewaehlten Diskretisierung ab, irgendwas mach ich fundamental falsch.
/Das es fuer grosse x wieder gegen 0 geht ist mir egal, im Endeffekt will ich
 berechnen, sobald die Faltung mal 1 war, hoer ich eh auf.
| |
In diskteter Faltung hast du nicht unendlich Support, d.h. deine Randbedingung verändert das Resultat. Nimm Mal nur einen kleineren Definitionsbereich für und schau dir das Resultat nur für den Bereich an, in dem du vollen Support hast.
Cf, von der scipy Doc:
Gaussian blur implemented using FFT convolution. Notice the dark borders around the image, due to the zero-padding beyond its boundaries. The convolve2d function allows for other types of image boundaries, but is far slower.
http://pageperso.lif.univ-mrs.fr/~francois.denis/IAAM1/scipy-html-1.0.0/generated/scipy.signal.fftconvolve.html
| |
Ich hatte das so verstanden, dass ein Wert von 0 im Bild eben schwarz entspricht? Ich verstehe padding so, dass die eingegebenen Vektoren
eben noch links und rechts mit Nullen versehen werden.
In meinem Fall gilt aber doch sowieso,
fuer grosse z: 
fuer kleine z:  .
Idealerweise wuerde man den G Vektor mit Einsen verlaengern, aber eigentlich ist es egal?
Ich verstehe auch nicht, wieso das die Position beeinflusst, an der sich die Faltung f*G anfaengt von 0 zu unterscheiden.
Im Integrand kann ich mir G ja an der vertikalen Achse gespielt und um x nach links verschoben vorstellen, also
und damit
 .
Wenn ich jetzt mit einer breiteren domain (also der grossen Diskretisierung) anfange, erweitere ich halt die eingesetzten x, aber da  beschraenkt ist, sollte doch das Produkt  sich immer erst ab dem selben Wert fuer z anfangen von Null zu unterscheiden (und zum Integral, der Faltung, beitragen)?
Leider ist mein G wesentlich komplizierter (aber von aehnlicher Gestalt), deswegen kann ich nicht einfach raten, wo es anfaengt sich von Null zu unterscheiden. Bzw, ich habe tausende verschiedene Funktionen G, und brauch halt jedesmal eine relativ akkurate Faltung.
Alternativ baue ich es einfach selbst, aus der vorhandenen Diskretisierung von G die Diskretisierung von H_x zu erzeugen, sollte ja sehr schnell gehen. Dann numerische (sample based) Integration der Wahl und mal schauen. Das wird mich nicht daran hindern, im Paper zu schreiben, dass dieser Ausdruck eine Faltung ist und sehr schnell implementiert werden kann.
|
|
|
|
|
|
|
|
|
|
|
Und auf Metaebene, ohne von obigem Post (der mir sehr am Herzen liegt, halp!) abzulenken:
Gerade kam eine Email rein, dass unser Department dringend studentische Lehrkraefte sucht, weil ansonsten weitere 330 Lehrstunden (wenn ich das richtig verstehe pro Quartal) auf die Assistenten (=Doktoranden) abgewaelzt werden muessen. Ich bin so unglaublich froh, drittmittelfinanziert zu sein. 
|
|
|
|
|
|
|
|
|
|
|
Ich hoffe, duy hast den Artikel gelesen, Irdo!
Schau dir mal die Definition von diskreter Konvolution mit finite sequences an:
Bildlich gesprochen, schiebst du eine Funktion (umgedreht) über die andere und summierst dann an jeder Stelle das Produkt der Werte. Der Einfachheit halber nehmen wir an, du schiebst die pdf (umgedreht) über die cdf. In deinem zweiten Beispiel ist deine Sequenz nach rechts hin länger, d.h. wenn du die Sequenz umdrehst, ist die Mitte der Sequenz links vom Peak, d.h. der Peak das Resultat der Konvolution erfährt einen Linksruck (wie das Forum LOL).
Ich denke, die Verwrirrung kommt daher, dass
1. Ein numpy array kein Koordinatensystem hat (nur Indices von 0 bis n-1). Denke hier am besten immer in Indizes, nicht in reelen Zahlen.
2. Deine Intution für Konvolution nicht mit der tatsächlichen Ausführung von diskreter Konvolution übereinstimmt. Bildlich gesprochen, schiebst du in diskreter Konvoltuion einen Kernel (dein Array/Vektor) über die Funktion, und summierst an jeder Stelle über das elementweise Produkt des momentanen Überlappes (im Normalfall ist der Kernel deutlich kleiner als die eigentliche Funktion), und der Kernel ist normalerweise in der Mitte des Arrays zentriert, d.h. für die Konvolution am Index 0 (des Arrays das die Funktionswerte hält), ist die Hälfte des Kernels links außerhalb des Defintionsbereichs.
Wenn das alles keinen Sinn ergibt (ich habe mich schon lange nicht mehr mit Konvolutionen außeinander gesetzt und mein Vokabular ist etwas holprig), empfehle ich eine einfache Konvolution händisch durchzuführen, z.B.
Nimm den Kernel
![TeX: \frac{1}{4}[1, 2, 1]](http://chart.apis.google.com/chart?chco=FFFFFF&chf=bg,s,00000000&cht=tx&chl=%5Cfrac%7B1%7D%7B4%7D%5B1%2C+2%2C+1%5D)
und führe eine Konvolution durch über
![TeX: [0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0]](http://chart.apis.google.com/chart?chco=FFFFFF&chf=bg,s,00000000&cht=tx&chl=%5B0%2C+0%2C+0%2C+0%2C+0%2C+1%2C+2%2C+3%2C+0%2C+0%2C+0%5D)
(Kernel spiegeln, Kernel ist auf dem 2. Element zentriert, über die Funktion schieben, und über das elementweise Produkt summieren)
Das Ergbenis sollte so aussehen:
![TeX: [0, 0, 0, 0, \frac{1}{4}, 1, 2, 2, \frac{3}{4}, 0, 0]](http://chart.apis.google.com/chart?chco=FFFFFF&chf=bg,s,00000000&cht=tx&chl=%5B0%2C+0%2C+0%2C+0%2C+%5Cfrac%7B1%7D%7B4%7D%2C+1%2C+2%2C+2%2C+%5Cfrac%7B3%7D%7B4%7D%2C+0%2C+0%5D)
Jetzt nehmen wir einen zweiten Kernel
![TeX: \frac{1}{4}[0, 0, 1, 2, 1]](http://chart.apis.google.com/chart?chco=FFFFFF&chf=bg,s,00000000&cht=tx&chl=%5Cfrac%7B1%7D%7B4%7D%5B0%2C+0%2C+1%2C+2%2C+1%5D)
Die Nullen sehen auf den ersten Blick so aus als ob nichts machen würden, aber beachte: Der Kernel ist jetzt auf dem dritten Element (1) zentriert. Führe erneute eine Konvolution durch und du bekommst so etwas:
![TeX: [0, 0, 0, 0, 0, \frac{1}{4}, 1, 2, 2, \frac{3}{4}, 0]](http://chart.apis.google.com/chart?chco=FFFFFF&chf=bg,s,00000000&cht=tx&chl=%5B0%2C+0%2C+0%2C+0%2C+0%2C+%5Cfrac%7B1%7D%7B4%7D%2C+1%2C+2%2C+2%2C+%5Cfrac%7B3%7D%7B4%7D%2C+0%5D)
|
|
|
|
|
|
|
|
|
|
|
Ich bin zwar wiedermal spät dran, aber wie seit einer Weile jedes Jahr, ist auch dieses Jahr wieder Advent of Code. Wer es nicht kennt: Vom 1. bis zum 25. Dezember gibt es jeden Tag ein kleines Programmierrätsel, immer mit zwei aufeinander aufbauenden Aufgaben. Ist hübsch gemacht mit einer kleinen Geschichte die sich durch alle Aufgaben zieht, und vor allem sind die Aufgaben nicht einfach "nimm Algorithmus X und slappe ihn auf das Problem" wie so oft bei Hackerrank und Konsorten, sondern meist nette Denkaufgaben für Programmiere. Habe das immer mal wieder als Anlass genommen eine neue Sprache zu lernen, oder aber einfach kleine, elegante und kurze Lösungen zu finden. Macht mir auf jeden Fall Spass.
Als kleiner Einstieg, Tag 1 2020:
| |
| Code: |
#!/usr/bin/env python3
import sys
from itertools import product
from math import prod
def solution(ints):
result = {sum(x): x for x in ints}
return prod(result[2020])
if __name__ == "__main__":
with open(sys.argv[1]) as file:
ints = [int(i) for i in file.readlines()]
result = solution(product(ints, ints))
print(result)
result = solution(product(ints, ints, ints))
print(result)
|
|
|
|
|
|
|
|
|
|
|
|
|
Das ist ja alles schön und gut, aber warum Python statt Kotlin, du HondKatze!
|
|
|
|
|
|
|
|
|
|
|
|
Worauf ich gerade Lust habe . Dieses Jahr bisher eine Mischung aus Python, F# und C#.
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von SwissBushIndian am 12.12.2020 14:40]
|
|
|
|
|
|
|
|
|
Aber Python ist doch so langweilig  gerade für solche Aufgaben. Am Montag Invest in yourself day, werde evtl den Advent dann Mal starten, Sprache muss ich noch wählen
|
|
|
|
|
|
|
|
|
|
|
Naja, zugegebenermassen fand ich die Aufgabe auch nicht besonders spannend. Am coolsten finde ich immer die, wo man kleine VMs bauen muss oder so. Tag 8 dieses Jahr zum Beispiel.
Daher auch die Sprachwahl. Für die nicht so lustigen dann halt short and concise, für die coolen was anderes Finde aber auch das gerade schön, dass man mit der Lösung eigentlich völlig frei ist.
|
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von SwissBushIndian am 12.12.2020 14:53]
|
|
|
|
|
|
|
|
|
| | Zitat von SwissBushIndian
short and concise
| |
Mein Beileid
|
|
|
|
|
|
|
|
|
|
|
|
Immerhin ist die Laufzeit polynomiell.
|
|
|
|
|
|
|
|
|
|
|
Richtig fein, Putzfreund. Haben ja schon mal kurz im SWT geschrieben, aber nach vollendeter Implementierung moechte ich dann doch nochmal hier meinen Dank aussprechen.
Den Artikel hab ich uebrigens tatsaechlich gelesen und fuer wirklich wunderbar illustriert/animiert befunden, hat mein Seal of Approval (und findet damit sicherlich jetzt auch weitere Leser!)
Ein paar Bemerkungen zur diskreten Faltung, vielleicht ergoogle ich ja mal meinen Post in der Zukunft...
Die Unterscheidung in Funktion und darueber bewegten Kernel ist sehr sinnvoll, sowohl fuer Verstaendnis als auch die Implementierung.
Padding muesste bei mir fuer f und G verschieden sein, hab keine Implementierung dafuer gefunden aber mit ein paar Tricks konnte ich mir auch so das gewuenschte Resultat zusammenbauen:
Ich habe wie empfohlen die pdf f als Kernel auserkoren (ist immerhin schon symmetrisch) und auf einem endlichen Intervall [a,b] diskretisiert. Dabei a,b so ausgewaehlt, dass f(a)=f(b) fast 0 ist, in meinem Fall erfordert das sowas wie 99.999 der Masse (danke norm.interval).
G ist eine CDF, also G(-\infty)=0 und G(infty)=1. G auf grossem (diskretisierten) Interval evaluieren, dann einfach auf den Bereich, wo etwas passiert zusammenschneiden (epsilon<G<1-epsilon) und rechts noch ein paar Einsen anhaengen, damit das unerwuenschte "Abfallen" der (diskreten) Faltung nicht zu frueh kommt. Der fftconvolution sind diese
Einsen eh egal.
Faltung berechnen und auf die gewuenschte Domain (in meinem Fall interessieren mich nur indices die x>0 entsprechen) zurechtschneiden. Links war das bei mir eben der Index, der 0 entspricht, rechts einfach dann, wenn die Faltung wieder kleiner wird, ab da nehme ich dann fuer meine weiteren Berechnugnen einfach an, dass sie ihr supremum (1) erreicht hat.
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Irdorath am 13.12.2020 18:49]
|
|
|
|
|
|
|
|
|
Richtig geil, Ehrenirdo. Danke für die Rückmeldug!
Ich glaube, für das Verständnis ist es tatsächlich einfacher, wenn man ohne Ahnung von den mathematischen Grundlagen anfängt und z.B. Bilder/Signale smoothen will dann mit so einem einfachen Kernel wie [1, 1, 1] anfängt. Irgendwann lernt man dann über Faltung und den ganzen coolen Mathehintergrund dazu und wie man die Kernel im Fourierraum nicenstein analysieren kann. Aber man hat eben noch diese naive Unterscheidung zwischen Funktion und Kernel (trotz kommutativer Eigenschaft der Faltung) im Kopf, die eben auch in all den diskreten Implementierungen zu finden ist.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von SwissBushIndian
Immerhin ist die Laufzeit polynomiell.
| |
Von Tag 3 war ich doch eher enttäuscht. Hatte mir shortest path erhofft, aber war dann sehr trivial.
|
|
|
|
|
|
|
|
|
|
|
Nochmal ne kleine Python Frage, diesmal Performance.
Es geht um die pdf und cdf Implementierungen in Scipy und begegnet mir bei numerischer Simulation haeufig.
Beispiel:
Ich will viele normal cdfs F_0, ..., F_N in noch mehr Punkten auswerten, also sowas wie
F_0(x_0), ..., F_N(x_0)
... ...
F_0(x_M), ..., F_N(x_M)
Leider laesst sich
scipy.stats.norm.cdf(x, mean=[mu_0, ..., mu_N], scale[sig_0,...,sig_M])
nur an einem Skalar x (dann bekommt jede der Normalverteilungen den gleichen Punkt eingesetzt) oder an einer Vektor x von Laenge N (dann bekommt die i. Verteilung den i. Eintrag von x eingesetzt) auswerten.
Ich kann jetzt meinen Bedarf nem bisschen map Gefrickel (oder beliebiger Alternative loesen:
| |
| Code: |
import numpy as np
import scipy.stats as st
muvec = np.arange(10) # parameters
sigvec = np.arange(1,11)
cdf_func = lambda x: st.norm.cdf(x, muvec, sigvec)
xvec = np.linspace(0, 10, 10000) # evaluation points
result = np.array(list(map(cdf_func, xvec)))
|
|
Das ist aber unzufriedenstellend langsam, und ich kann mir einfach nicht vorstellen, dass es dafuer keine schnellere Implementierung gibt, vorallem, weil meine Googlesuche nach dem Problem seeeehr verdaechtig erfolglos bleibt. Beispielsweise in der Monte Carlo Simulation von nicht stationaeren Prozessen tritt diese Fragestellung ganz natuerlich auf, ich vermute also, dass ich etwas uebersehe. 
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Irdorath am 17.12.2020 17:56]
|
|
|
|
|
|
|
|
|
Ich kann später Mal in die Dokumentation schauen. Als quick fix, probabier Mal über die mus zu iterieren statt über x, das ist eine viel kürzere Schleife, die dann in Python ausgeführt wird
|
|
|
|
|
|
|
|
|
|
|
|
Die Loop Richtung zu ändern liegt natürlich nahe.
|
|
|
|
|
|
|
|
|
|
|
Willst du das?
| |
| Code: |
import scipy.stats as st
import numpy as np
X = np.mgrid[0.:1.:100j]
locs = np.mgrid[-1.:1.:50j]
norms = st.norm(loc=locs, scale=1.)
norms.cdf(X[..., None]).shape
Out:(100, 50)
|
|
Falls ja: Das verwendet Broadcasting. Die norms sind 50 eindimensionale Normalverteilungen (alle mit dem selben scale 1). Die cdf wird mit einem X[..., None].shape == (100, 1) Array ausgewertet (also 100 eindimensionale Inputs), also kommen (100, 50) Resultate raus.
e/ st.norm.cdf(X[..., None], loc=locs) tuts auch.
|
|
[Dieser Beitrag wurde 3 mal editiert; zum letzten Mal von B0rG* am 17.12.2020 20:02]
|
|
|
|
|
|
|
|
|
|
Wunderschoen! Genau das, richtig gut. x in Dimension (M,1) statt (M,) ist also der gewuenschte Unterschied, danke!
|
|
|
|
|
|
|
|
|
|
|
Borg natürlich mit 6 Stunden Vorsprung, wie unfair!
|
|
|
|
|
|
|
|
|
|
|
|
Gibts hier jemanden der sich mit Verilator (Verilog Simulator) auskennt?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nach dem LaTeX-Paket genau, was mir in meinem Leben fehlte.
I wish to plead incompetent.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Geht bei dir alles seinen (unterbestimmten) Gang, WoS?
|
|
|
|
|
|
|
|
|
|
|
Einmal Oli sperren, bitte. Kill the messenger!
|
|
|
|
|
|
|
|
|
|
|
Ich hab vor ca. 2 Wochen ein Studium in "Digitale Medien" begonnen.
Das Studium beinhaltet (leider) auch nen kleinen Matheblock, der mir mehr zu schaffen macht als ich ohnehin schon befürchtet hatte.
Jetzt hab ich mir in den 14 Tagen durch echt viel büffeln schon mehr Mathe beigebracht, als ich je für möglich gehalten hätte - dennoch ist es teilweise noch wirklich schwer für mich.
Grade hänge ich an der vollständigen Induktion. Das Prinzip dahinter verstehe ich, aber bei so mancher Übungsaufgabe fasse ich mir bei der Lösung an den Kopf und verstehe nicht, wieso bestimmte Dinge so gemacht werden.
Ein Beispiel:
und die Musterlösung:
Speziell der gelb markierte Teil "stört" mich. Mir ist schon klar dass das stimmt, aber ich wäre da nie im Leben von alleine drauf gekommen das so zu rechnen.
Meine Lösung war:
kann man das in ner Klausur so schreiben?
Zusatzfrage:
Gibt es empfehlenswerte Lektüre, die auf einfachem Niveau mit vielen Beispielen geschrieben ist für "Grundlagen der Mathematik"?
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von Apache
Zusatzfrage:
Gibt es empfehlenswerte Lektüre, die auf einfachem Niveau mit vielen Beispielen geschrieben ist für "Grundlagen der Mathematik"?
| |
Ich habe tatsächlich seit meinem jetzt schon etwas länger abgeschlossenen Informatik + Mathestudium alle drei Bände von Das gelbe Rechenbuch hier rumstehen, weil es für mich die besten Beispiele und Anwendungen hatte. Bei Bedarf melde dich per PM, da können wir mal bei der vollständigen Induktion reingucken.
Aber ich würde vermuten, hier hat jeder "sein" Lieblingsbuch für sowas, besonders da diese Beweismethode eine der "einfachsten" ist und eben in so ziemlich jedem Studiumbeginn-Mathebuch/-script am Anfang dran kommt.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von Apache
Speziell der gelb markierte Teil "stört" mich. Mir ist schon klar dass das stimmt, aber ich wäre da nie im Leben von alleine drauf gekommen das so zu rechnen.
Meine Lösung war:
https://abload.de/img/mathe3xtjez.png
kann man das in ner Klausur so schreiben?
| |
Ich versteh nicht ganz, was du mit dem Argument  bezweckst. Wieso folgt daraus die letzte Zeile, ich sehe die Verbindung nicht?
Einfacher, und halt leider genau das "stoerende" Argument, ist
 .
Wie man darauf kommt? In den meisten Faellen, hat man den Trick schonmal gesehen und kommt nicht original neu darauf. Bist also denke ich auf nem guten Dampfer! Solche Aufgaben sind immer mehr oder weniger die gleichen Tricks, wenn du dir einfach soviele Uebungsaufgaben wie moeglich reinziehst (und im Detail nachvollziehst, wie bei der obigen), wird das schon!
|
|
|
|
|
|
|
|
|
|
|
Visualisierung:
Haesslicher Vanilla Pyplot (nur doppelte Stichstaerke), ich will euch nicht mit meinen genialen Ideen beeinflussen. 
Ich will Curve 2 sichtbarer machen, potenziell in nem Greyscale Plot. Kurve mit Markern zupflastern die einzige Loesung?
|
|
|
|
|
|
|
|
|
|
|
Der Kontrast zwischen grün und blau ist zu niedrig, sowohl die Farbe als auch die Helligkeit. Versuch mal, orange und blau heller zu machen und blau durch eine andere Farbe zu ersetzen, das könnte helfen. Eben in Photoshop zusammengeklickt:
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Danzelot am 02.01.2021 21:27]
|
|
|
|
|
|
| Thema: pOT-lnformatik, Mathematik, Physik XXIII |
|
![AUP [smith] 29.07.2010](./avatare/upload/U1066026--zeratul.png)
