4. Vier ineinander geschachtelte for-Schleifen beschleunigen, Polygone finden

Vier ineinander geschachtelte for-Schleifen beschleunigen, Polygone finden

  • L

    Ich verstehe auch nicht ganz was du da machst. Du willst doch Regression machen?

    Normalerweise ist Idee folgende:

    • Man hat eine Lineares Gleichungssystem w @ \phi(X) = Y, wobei X alle deine Datenpunkte sind und Y alle deine gegebenen echte Werte (Das @ ist ne Matrix bzw. Vectormultiplikation)
    • Phi ist ne Abbildung, die deine X in "features" umwandelt. Also z.B. aus jedem x ein [1, x, x^2, x^3, x^4] macht, sodass du eben dein gewünschtes Polynom hast
    • Dann wird das w gesucht, welche den squared error reduziert: w = \arg\min_w || w @ \phi(X) ||^2 => Das widerum hat eine geschlossene Form mit w = inv(\phi(X) @ \phi(X).T) @ \phi(X) * Y (Herleitung über Ableitung & Null setzen)

    Also keine verschachtelten Schleifen oder ähnliches. Eine Formel mit der du in Sekundenschnelle deine optimalen Weights berechnen kannst und fertig 🙂
    In Python kann man das in vlt. 10 Zeilen implementieren.

    Edit: Du kannst natürlich auch einen anderen Fehler nutzen, aber dann sehen deine Gleichungen anders aus und du findest ggf. keine geschlossene Formel dafür, sondern musst iterativ mit gradient descent o.ä. arbeiten.

    Edit 2: Selbst wenn es keine geschlossene Formel gibt, der Punkt auf den auch @john-0 rauswollte ist, dass man hier Vektor / Matrix Multiplikationen nutzt. Was nicht nur ein bisschen, sondern extrem viel schneller ist als manuell mit for schleifen drüber zu loopen.

    0
  • *

    @Fragender sagte in [Vier ineinander geschachtelte for-Schleifen beschleunigen, Polygone finden]

    … Und den Algo hab ich mir selber ausgedacht.

    Das ist die wesentliche Information! Es ist für solche Probleme absolut wichtig, dass man schreibt was für ein Verfahren man nutzt. Dann weiß man auch was bei der Implementation schief gelaufen ist.

    0
  • ?

    Bin nun auf einen grünen Zweig gekommen. 🙂 Schlussendlich hatte ich die Limits nicht richtig berechnet:

    package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class DataFit {
    public static double calcY(double i, Double[] d) {
        return d[0] * i * i * i + d[1] * i * i + d[2] * i + d[3];
    }

    public static double calcE(double[][] xys, Double[] d) {
        double sum = 0;
        for (double[] xy : xys) {
            sum += Math.abs(calcY(xy[0], d) - xy[1]);
        }
        return sum;
    }

    public static double check(double bestE, Double[] best, ArrayList<Double[]> bests, double[][] xys) {
        double e = calcE(xys, best);
        if (e < bestE) {
            bests.add(best);
            return e;
        }
        return 10000;
    }

    public static ArrayList<Double[]> fit(double[][] xys, int limit, int step, double[] startValues) {
        final double step1 = step;
        int[] starts = new int[startValues.length];
        for (int i = 0; i < starts.length; i++) {
            starts[i] = Math.max(0, (int) Math.round((startValues[i] - 1d / step1 * (limit / 2d)) * limit));
        }
        ArrayList<Double[]> bests = new ArrayList<>();
        double bestE = 10000;
        for (int i = starts[0]; i <= starts[0] + limit; i++) {
            for (int j = starts[1]; j <= starts[1] + limit; j++) {
                for (int k = starts[2]; k <= starts[2] + limit; k++) {
                    for (int l = starts[3]; l <= starts[3] + limit; l++) {
                        Double[] best1 = {-i / step1, -j / step1, -k / step1, -l / step1};
                        Double[] best2 = {-i / step1, -j / step1, -k / step1, l / step1};
                        Double[] best3 = {-i / step1, -j / step1, k / step1, -l / step1};
                        Double[] best4 = {-i / step1, -j / step1, k / step1, l / step1};
                        Double[] best5 = {-i / step1, j / step1, -k / step1, -l / step1};
                        Double[] best6 = {-i / step1, j / step1, -k / step1, l / step1};
                        Double[] best7 = {-i / step1, j / step1, k / step1, -l / step1};
                        Double[] best8 = {-i / step1, j / step1, k / step1, l / step1};

                        Double[] best9 = {i / step1, -j / step1, -k / step1, -l / step1};
                        Double[] best10 = {i / step1, -j / step1, -k / step1, l / step1};
                        Double[] best11 = {i / step1, -j / step1, k / step1, -l / step1};
                        Double[] best12 = {i / step1, -j / step1, k / step1, l / step1};
                        Double[] best13 = {i / step1, j / step1, -k / step1, -l / step1};
                        Double[] best14 = {i / step1, j / step1, -k / step1, l / step1};
                        Double[] best15 = {i / step1, j / step1, k / step1, -l / step1};
                        Double[] best16 = {i / step1, j / step1, k / step1, l / step1};

                        bestE = Math.min(bestE, check(bestE, best1, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best2, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best3, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best4, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best5, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best6, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best7, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best8, bests, xys));

                        bestE = Math.min(bestE, check(bestE, best9, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best10, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best11, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best12, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best13, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best14, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best15, bests, xys));
                        bestE = Math.min(bestE, check(bestE, best16, bests, xys));
                        if (bests.size() > 20) {
                            bests.sort(Comparator.comparingDouble(a -> calcE(xys, a)));
                            while (bests.size() > 10) {
                                bests.remove(bests.size() - 1);
                            }
                        }
                    }
                }
            }
        }
        bests.sort(Comparator.comparingDouble(a -> calcE(xys, a)));
        while (bests.size() > 10) {
            bests.remove(bests.size() - 1);
        }
        return bests;
    }

    public static ArrayList<Double[]> fit1(double[][] xys) {
        ArrayList<Double[]> bests1 = new ArrayList<>();
        ArrayList<Double[]> bests2 = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            bests1.addAll(fit(xys, 50, i, new double[4]));
        }

        bests1.sort(Comparator.comparingDouble(a -> calcE(xys, a)));
        while (bests1.size() > 10) {
            bests1.remove(bests1.size() - 1);
        }
        for (Double[] best : bests1) {
            System.out.println(Arrays.toString(best));
            System.out.println(calcE(xys, best));
        }
        System.out.println();

        for (Double[] best : bests1) {
            bests2.addAll(fit(xys, 50, 50, new double[]{best[0], best[1], best[2], best[3]}));
        }

        bests2.sort(Comparator.comparingDouble(a -> calcE(xys, a)));
        for (Double[] best : bests2) {
            System.out.println(Arrays.toString(best));
            System.out.println(calcE(xys, best));
        }
        System.out.println();

        return bests2;
    }

    public static void main(String[] args) {
        // fit1(new double[][]{{0, 4.5}, {4, 43}, {8, 80}, {10, 99}, {12, 100}});
        fit1(new double[][]{{0, 1}, {4, 30}, {8, 49}, {10, 64}, {12, 100}});
    }
}

    @john-0 Die Idee ist einfach, alle unterschiedlichen "Kombinationen" auszuprobieren, anstatt das LGS zu lösen ... Ich weiß nicht genau, wie der Algo heißt.

    0
  • ?

    Ich denke, das ganze Problem an der Sache könnte sein, dass die Messpunkte, die aus dem RL kommen, nicht immer auf einer idealen Kurve liegen müssen, sondern ggf. etwas von ihr abweichen können. Insofern gibt es vielleicht keine Formel, um das LGS (eindeutig) zu lösen... Aber, das weiß ich nicht genau, weil es da schon etwas/sehr in die Mathematik geht...

    0
    *
     1 Antwort
  • *

    @Fragender sagte in Vier ineinander geschachtelte for-Schleifen beschleunigen, Polygone finden:

    Ich denke, das ganze Problem an der Sache könnte sein, dass die Messpunkte, die aus dem RL kommen, nicht immer auf einer idealen Kurve liegen müssen, sondern ggf. etwas von ihr abweichen können. Insofern gibt es vielleicht keine Formel, um das LGS (eindeutig) zu lösen... Aber, das weiß ich nicht genau, weil es da schon etwas/sehr in die Mathematik geht...

    Nein, das Verfahren legt eine Kurve zwischen die Messpunkte bei denen die Abweichung der Messpunkte von dieser Kurve minimiert wird. Lies Dir dazu für den Einstieg einfach diesen Wikipedia Artikel durch.

    0
  • ?

    Ach so, das klingt ja noch recht simpel...

    E: Zumindest vordergründig ... Aber, was du, glaube ich, noch nicht verstanden hast, ist, Algorithmus ungleich geschlossene Formel.

    0
    L
     1 Antwort
  • L

    @Fragender sagte in Vier ineinander geschachtelte for-Schleifen beschleunigen, Polygone finden:

    Ach so, das klingt ja noch recht simpel...

    E: Zumindest vordergründig ... Aber, was du, glaube ich, noch nicht verstanden hast, ist, Algorithmus ungleich geschlossene Formel.

    Ein Programm, welches eine geschlossene Form nutzt, um ein Problem zu lösen, ist ein Algorithmus.

    @Fragender sagte in Vier ineinander geschachtelte for-Schleifen beschleunigen, Polygone finden:

    Ich denke, das ganze Problem an der Sache könnte sein, dass die Messpunkte, die aus dem RL kommen, nicht immer auf einer idealen Kurve liegen müssen, sondern ggf. etwas von ihr abweichen können. Insofern gibt es vielleicht keine Formel, um das LGS (eindeutig) zu lösen

    1. Es gibt vlt. keine Formel mit degree 4, die es genau lösen kann. Aber grundsätzlich kannst du die Punkte exakt treffen, wenn du mindestens so viele degrees hast wie Punkte. Meistens reichen auch weniger.
    2. Es ist im Allgemeinen nicht erstrebenswert das LGS exakt zu lösen. Wie du sagst sind Trainingsdaten in der Regel nicht exakt (d.h. sie enthalten "Noise"). Wenn deine Kurve also exakt deine Punkte schneidet, dann hast du sehr wahrscheinlich massives Overfitting => Deswegen beschränkt man die Flexibiltität des Modells, in dem man einen geringeren Grad verwendet oder man fügt einen Regularizer ein. Least Squares mit Regularizer führt z.B. zu Ridge Regression,
    3. Die Formel bzw. der Ansatz "least squares" beachtet das. Du findest dort wie oben erläutert eben keine exakte Lösung, sondern es handelt sich um ein Optimierungsproblem bei dem du die beste Lösung suchst. Auch diese können natürlich eine geschlossene Formel haben wie hier der Fall. Bei komplexeren Themen kann man diese meistens dann aber nur mit entsprechenden Suchalgorithmen lösen, die je nach Problem auch keine Garantie für Optimalität besitzen.
      Zum Thema noise, kannst du das Problem tatsächlich aber auch äquivalent probabilistisch definieren. Daher angenommen deine Trainingspunkte werden von einer Function f(x,w) erzeugt (die du natürlich nicht kennst), dann kannst du es definieren als y = f(x, w) + \epsilon. Das epsilon ist dabei eine Zufallsvariable, die für die Abweichung vom echten Wert verantwortlich ist. Wenn du die Annahme machst, dass epsilon gaussian verteilt ist und dann versuchst die Conditional Likelihood p(y | X, w, \sigma) zu optimieren in Hinblick auf deine Gewichte w, dann kriegst du die selbe geschlossene Formel raus. Das ist nicht so schwer herzuleiten, aber da ich deinen Mathe Kentnistand nicht kenne, mache ich das mal nicht hier. Das allgemeine Verfahren heißt aber Maximum Likelihood Estimation bzw. dann im Fall von Regression Maximum Likelihood Regression.
      Das wichtige ist aber ja das Ergebnis hier. Da du in beiden Fällen die selbe geschlossene Formel rausbekommst, sind die Ansätze äquivalent. Genauer genommen weißt du jetzt, dass least squares implicit die Annahme macht, dass deine Trainingsdaten gaussian verteilten noise enthalten.

    Ansonsten so ganz generell: Cool, dass du versuchst deine eigenen Algorithmen zu erfinden & umzusetzen. Aber zwei Sachen:

    1. Sag explizit dazu, dass es sich um einen eigenen Algorithmus handelt (oder zumindest einen, von dem du den Namen nicht kennst) und erkläre diesen auch mit Worten oder Formeln. Es ist sehr schwer bei über 100 Zeilen da zu sehen wie dein Algorithmus funktioniert. Vor allem wenn dann auch noch potenziell Fehler drin sind.
    2. Achte nicht darauf dich zu verlaufen. Ich weiß nicht, was genau du bezwecken willst. Aber die existierenden Ansätze sind ziemlich gut. Evtl. lohnt es sich also erstmal die existierenden Ansätze zu lernen und zu verstehen! Das wiederum ermöglichst es dir dann auch, Schwächen in den bisherigen Ansätzen zu erkennen und Lösungen dafür zu entwickeln. Dann besteht vlt. auch eine Chance, dass du tatsächlich etwas neues sinnvolles findest.
    1 1 Antwort
  • ?

    Danke für die Antwort! @Leon0402

    Ja, ich "puzzle" halt gerne ... Aber Zeile 41 bis 57 sieht wirklich schrecklich aus, vielleicht fällt mir dazu noch etwas ein. Aber auch ja, wie immer gilt, das Rad nicht mehrmals erfinden. :s

    0

  • @Leon0402 sagte in Vier ineinander geschachtelte for-Schleifen beschleunigen, Polygone finden:

    Es ist im Allgemeinen nicht erstrebenswert das LGS exakt zu lösen. Wie du sagst sind Trainingsdaten in der Regel nicht exakt (d.h. sie enthalten "Noise"). Wenn deine Kurve also exakt deine Punkte schneidet, dann hast du sehr wahrscheinlich massives Overfitting

    Wo ich das gerade lese, denke ich an die Polynominterpolation und die Vandermonde-Matrix welche hierbei auftritt. Und diese ist schlecht konditioniert.

    0
  • ?

    Ich hab noch ein wenig gefummelt:

    package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class DataFit {
    public static double calcY(final double i, final Double[] d) {
        return d[0] * i * i * i + d[1] * i * i + d[2] * i + d[3];
    }

    public static double calcE(final double[][] xys, final Double[] d) {
        double sum = 0;
        for (double[] xy : xys) {
            sum += Math.abs(calcY(xy[0], d) - xy[1]);
        }
        return sum;
    }

    public static double check(final double bestE, final Double[] best, final ArrayList<Double[]> bests, final double[][] xys) {
        double e = calcE(xys, best);
        if (e < bestE) {
            bests.add(best);
            return e;
        }
        return 10000;
    }

    public static void shrink(final double[][] xys, final ArrayList<Double[]> bests) {
        bests.sort(Comparator.comparingDouble(a -> calcE(xys, a)));
        while (bests.size() > 10) {
            bests.remove(bests.size() - 1);
        }
    }

    public static ArrayList<Double[]> fit1(final double[][] xys, final int limit, final double step, final double[] startValues) {
        int[] starts = new int[startValues.length];
        for (int i = 0; i < starts.length; i++) {
            starts[i] = Math.max(0, (int) Math.round((startValues[i] - 1d / step * (limit / 2d)) * limit));
        }
        ArrayList<Double[]> bests = new ArrayList<>();
        double bestE = 10000;
        for (int i = starts[0]; i <= starts[0] + limit; i++) {
            for (int j = starts[1]; j <= starts[1] + limit; j++) {
                for (int k = starts[2]; k <= starts[2] + limit; k++) {
                    for (int l = starts[3]; l <= starts[3] + limit; l++) {
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, -j / step, -k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, -j / step, -k / step, l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, -j / step, k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, -j / step, k / step, l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, j / step, -k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, j / step, -k / step, l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, j / step, k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{-i / step, j / step, k / step, l / step}, bests, xys));

                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, -j / step, -k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, -j / step, -k / step, l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, -j / step, k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, -j / step, k / step, l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, j / step, -k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, j / step, -k / step, l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, j / step, k / step, -l / step}, bests, xys));
                        bestE = Math.min(bestE, check(bestE, new Double[]{i / step, j / step, k / step, l / step}, bests, xys));

                        if (bests.size() > 20) {
                            shrink(xys, bests);
                        }
                    }
                }
            }
        }
        shrink(xys, bests);
        return bests;
    }

    @SuppressWarnings("UnusedReturnValue")
    public static ArrayList<Double[]> fit2(final double[][] xys) {
        ArrayList<Double[]> bests1 = new ArrayList<>();
        ArrayList<Double[]> bests2 = new ArrayList<>();

        // 0.5, 1.0 and 2.0 divisor = 2.0, 1.0 and 0.5-step width
        for (int i = 1; i <= 4; i *= 2) {
            bests1.addAll(fit1(xys, 50, i / 2d, new double[4]));
        }

        shrink(xys, bests1);

        for (Double[] best : bests1) {
            System.out.println(Arrays.toString(best));
            System.out.println(calcE(xys, best));
        }
        System.out.println();

        // 50 limit and 50 divisor (0.02-step width) = 0.02, 0.04, ..., 1.0
        for (Double[] best : bests1) {
            bests2.addAll(fit1(xys, 50, 50, new double[]{best[0], best[1], best[2], best[3]}));
        }

        shrink(xys, bests2);

        for (Double[] best : bests2) {
            System.out.println(Arrays.toString(best));
            System.out.println(calcE(xys, best));
        }
        System.out.println();

        return bests2;
    }

    public static void main(String[] args) {
        fit2(new double[][]{{0, 4.5}, {4, 43}, {8, 80}, {10, 99}, {12, 100}});
        fit2(new double[][]{{0, 1}, {4, 30}, {8, 49}, {10, 64}, {12, 100}});
    }
}

    (Am besten von unten nach oben lesen).

    Die Ausgabe wäre dann:

    [0.0, -0.5, 14.0, 4.0]
18.5
[0.0, -0.5, 14.0, 3.5]
19.0
[0.0, 0.0, 9.5, 4.0]
19.5
[0.0, 0.0, 9.0, 7.0]
20.5
[0.0, 0.0, 9.0, 7.0]
20.5
[0.0, 0.0, 9.0, 6.5]
21.0
[0.0, 0.0, 9.0, 6.0]
21.5
[0.0, 0.0, 9.0, 6.0]
21.5
[0.0, 0.0, 9.0, 5.5]
22.0
[0.0, 0.0, 9.0, 5.0]
22.5

[-0.04, 0.42, 8.68, 4.5]
6.439999999999998
[-0.04, 0.42, 8.66, 4.5]
6.6000000000000085
[-0.04, 0.42, 8.64, 4.5]
6.799999999999997
[-0.04, 0.42, 8.62, 4.64]
7.140000000000028
[-0.04, 0.42, 8.62, 4.62]
7.1600000000000135
[-0.04, 0.42, 8.62, 4.6]
7.180000000000048
[-0.04, 0.42, 8.62, 4.58]
7.200000000000033
[-0.04, 0.42, 8.62, 4.56]
7.220000000000025
[-0.04, 0.42, 8.62, 4.54]
7.24000000000001
[-0.04, 0.42, 8.62, 4.52]
7.260000000000037

[0.0, 0.5, 2.0, 1.0]
23.0
[0.0, 0.5, 2.0, 0.5]
24.5
[0.0, 0.5, 1.5, 5.0]
26.0
[0.0, 0.5, 1.5, 4.5]
26.5
[0.0, 0.5, 1.5, 4.0]
27.0
[0.0, 0.5, 1.5, 3.5]
27.5
[0.0, 0.5, 1.5, 3.0]
28.0
[0.0, 0.5, 1.5, 2.5]
28.5
[0.0, 0.5, 1.0, 9.0]
29.0
[0.0, 0.5, 1.0, 8.5]
29.5

[0.0, 0.56, 1.52, 1.0]
22.27999999999998
[0.0, 0.56, 1.52, 1.0]
22.27999999999998
[0.0, 0.56, 1.52, 0.98]
22.339999999999982
[0.0, 0.56, 1.52, 0.98]
22.339999999999982
[0.0, 0.56, 1.52, 0.96]
22.399999999999977
[0.0, 0.56, 1.52, 0.96]
22.399999999999977
[0.0, 0.56, 1.5, 1.16]
22.399999999999984
[0.0, 0.56, 1.5, 1.14]
22.41999999999998
[0.0, 0.56, 1.5, 1.12]
22.439999999999984
[0.0, 0.56, 1.5, 1.1]
22.45999999999998

    Das heißt, ein Polygon 3. Grades mit den Koeffizienten [-0.04, 0.42, 8.68, 4.5] wäre für die erste Punktemenge "optimal" und ein Polygon 2. Grades mit den Koeffizienten [0.56, 1.52, 1.0] wäre für die zweite Punktemenge "optimal". Gezeichnet hab ich es jetzt nicht extra, aber ich nehme an, dass das stimmt, optimal und minimal (die Koeffizienten betreffend) wäre. Aber belehrt mich gerne eines Besseres ...

    0
Anmelden zum Antworten