Die Mathe-Redaktion - 14.11.2019 07:36 - 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

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit 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 598 Gäste und 4 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Kleine_Meerjungfrau Monkfish epsilonkugel
Mathematik » Stochastik und Statistik » Numerisch robuste lineare Regression OHNE kleinste Quadrate mit Integerarithmetik
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Numerisch robuste lineare Regression OHNE kleinste Quadrate mit Integerarithmetik
merck89x8
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.07.2019
Mitteilungen: 1
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-31


Ich habe ein System, welches das Ziel hat, die Uhr eines entfernten Senders (mit dem Kontakt über ein eigenes Zeitsynchronisier-Netzwerkprotokoll besteht) lokal nachzubilden. D.h.: Wenn $t_s$ der aktuelle Zeitstempel der Uhr des Senders ist, und $t_r$ der aktuelle Zeitstempel der Uhr des Empfängers ist, dann soll $t_s^{'}$ eine Rekonstruktion von $t_s$ sein auf Basis von Information aus den Netzwerkdaten und aus $t_r$. Anders gesagt: wenn man zum exakt demselben Zeitpunkt $t_s$ und $t_s^{'}$ misst bzw. berechnet, dann ist der Fehler $e = |t_s - t_s^{'}|$ idealerweise 0. Eine Implementierung hat nun das Ziel, daß $e$ so klein wie möglich ist, und so "ruhig" wie möglich, d.h. sich nicht dauernd rasch ändert.

Dazu ist es notwendig, den Offset zwischen den beiden Uhren und den Geschwindigkeitsunterschied der beiden Uhren feststellen zu können. (Quartzkristalle zweier Uhren laufen nie 100%ig gleich schnell.) Das läuft auf eine simple Lineargleichung hinaus:

$t_s^{'} = a + t_r * b$

$a$ und $b$ müssen nun ermittelt werden. $a$ bildet dabei den Offset ab, $b$ den Geschwindigkeitsunterschied (1,0 = beide Uhren exakt gleich; 2,0 = Uhr des Senders ist 2x so schnell wie die des Empfängers usw.)

Über das Netzwerkprotokoll ist es nun möglich, zu ermitteln, wie $t_s$ zu einem bestimmten $t_r$ war. (Die Details des Protokolls lasse ich mal aus, damit es nicht zu lange wird.) Diese Ermittlung erfolgt in 100ms-Intervallen. D.h. alle 100ms kriegt man ein Wertepaar: ein $t_s$ und ein assoziiertes $t_r$. D.h. jedes Paar bezeichnet ein $t_s$, welches zum selben Zeitpunkt aktuell war wie $t_r$.

Mein Gedanke ist nun, daß das beste Voraussetzungen für eine lineare Regression sind. $t_r$ wäre dabei die unabhängige, $t_s$ die abhängige Variable.

Es liegt nun nahe, die übliche Methode der kleinsten Quadrate zu nutzen. Es gibt aber einen Haken, wenn man das implementieren will: die Zeitstempel ($t_r$ usw.) sind 64-bit Integer. Die Methode der kleinsten Quadrate involviert die Berechnung von Varianzen und Kovarianzen, d.h. Multiplikationen von 64-bit Integern. Multipliziert man zwei solche Integer, dann entsteht ein 128-bit Integer (nicht immer, aber das ist der Worst Case). Mehr noch, in einem späteren Schritt müßte man so ein 128-bit Integer mit einem 64-bit Integer multiplizieren. Wir reden da also schlimmstenfalls von einem 192-bit Integer!

Das wird besonders kompliziert, wenn man beachtet, daß diese Berechnungen ca. 10-20 mal pro Sekunde stattfinden müssen, auf kleinen Geräten, die eine 32-bit Architektur haben, d.h. schon die 64-bit Integer intern vom Prozessor nicht in einem Schritt verarbeitet werden. Diese Plattformen haben idR keine 128-bit Integer als Variablentypen zur Verfügung (von 192-bit ganz zu schweigen). Die Bibliotheken für Integerzahlen beliebiger Präzision/Länge sind eine Option, aber sehr langsam.

Eine Alternative ist es, für die (Ko)varianzen statt 64-bit Integer 64-bit Floating Point zu nutzen ("double" in C und C++). Da kommt aber das numerische Problem ins Spiel. Die (Ko)varianzen können schnell zu sehr sehr riesigen Zahlen wachsen. Es ist ein bekanntes Problem, daß die Division von 2 riesigen Floating Point Zahlen numerisch instabil ist. Daher bevorzuge ich ein Weg, der komplett nur mit Integer-Zahlen auskommt.

Kern des Übels sind die Multiplikationen für die (Ko)varianzen. Die sind aber essentiell bei dieser Methode. Und hier ist nun endlich meine Frage.

Ich finde keine Alternativen zu den kleinsten Quadraten! Ist das wirklich die einzige Methode für eine einfache Linearregression, die ohne Iterationen auskommt? Könnte man zB irgendwie statt kleinste Quadrate kleinste absolute Differenzen nutzen? Bei der Methode der kleinsten Quadrate bekommt man ja auch neben den Koeffizienten $a$ und $b$ auch noch den Korrelationskoeffizienten $r$. Der ist mir aber egal, von daher ist es OK, wenn eine Alternative den nicht hat. Oder kennt vlt. jemand eine besondere Variante für reine integerbasierte Rechnung?



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1377
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-08-03


Hallo merck89x8!

Willkommen auf dem Matheplaneten!

Wenn Dir kleinste Quadrate unsympatisch sind, kannst Du auch 2 Ansätze mit linearer Optimierung verfolgen:
(a) bilde eine Ausgleichsgerade mit Minimierung des maximalen Abstandes eines Punktes von dieser Geraden
(b) bilde eine Ausgleichsgerade mit Minimierung des summierten Abstandes der Punkte von dieser Geraden.

Ich weiß nicht, ob das viel schneller ist, lineare Optimierung ist aber meist recht schnell.

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
hgseib
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.04.2019
Mitteilungen: 172
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-08-03


2019-07-31 21:08 - merck89x8 im Themenstart schreibt:
Eine Implementierung hat nun das Ziel, daß e so klein wie möglich ist, und so "ruhig" wie möglich, d.h. sich nicht dauernd rasch ändert.

Für mich hört sich das nach 'Mess- und Regelungstechnik' an.
Regelungstechnik
PID-Regler

mfg



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6070
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-08-06


2019-08-03 01:02 - Delastelle in Beitrag No. 1 schreibt:
Ich weiß nicht, ob das viel schneller ist, lineare Optimierung ist aber meist recht schnell.

Lineare Optimierung ist schnell, aber ...
Für die Methode der kleinsten Fehlerquadrate braucht man pro Messwert ein paar Multiplikationen, ein paar Additionen und zum Schluss eine Division. Viel weniger Aufwand kann man kaum haben, wenn man alle Messwerte mit in die Betrachtung einfließen lassen möchte.
Die Alternative wäre dann, genau das nicht zu tun. Man könnte immer aus zwei möglichst weit auseinanderliegenden Messwerten jeweils Anstieg und Absolutglied berechnen. Wenn man Angst hat, dass das aufgrund der Messungenauigkeiten zu stark streut, könnte man dann noch einen (Mittelwerts-)Filter draufsetzen.



  Profil  Quote  Link auf diesen Beitrag Link
merck89x8 wird per Mail über neue Antworten informiert.
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-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]