Datenstruktur für Repräsentation eines Bins

[mrapp-ke]

Im Rahmen von #226 wird eine Datenstruktur für die Repräsentation eines einzelnen Bins benötigt. Diese Datenstruktur sollte in der Lage sein folgende Informationen zu speichern:

• Die Anzahl der Beispiele, die zu dem Bin gehören
• Den kleinsten Featurewert, der innerhalb der Beispiele im Bin auftritt
• Den größten Featurewert, der innerhalb der Beispiele im Bin auftritt

Die Datenstruktur sollte als struct implementiert werden (vorerst am besten in tuples.h) und könnte z.B. so aussehen:

struct Bin {
    uint32 numExamples;
    float32 minValue;
    float32 maxValue;
};

[LukasEberle]

Ich hab mir dazu schonmal Gedanken gemacht. Die Summe der Werte ist auch noch wichtig, oder?

[michael-rapp]

Ich hab mir dazu schonmal Gedanken gemacht. Die Summe der Werte ist auch noch wichtig, oder?

Du meinst die Summe der Featurewerte der Beispiele im Bin? Ich wüsste nicht wofür wir die brauchen, aber vielleicht übersehe ich etwas?

• Wir brauchen auf jeden Fall den kleinsten und größten Wert um den Threshold von Bedingungen auszurechnen (threshold = vorherigerBin.maxValue + aktuellerBin.minValue, wobei die Bins sortiert sind).

• Die Anzahl Beispiele im Bin ist hilfreich um Bins, die eventuell leer sind ignorieren zu können.

• Und außerdem muss man die Statistiken (also die Gradienten und Hessians) der Beispiele in einem Bin aufsummieren. Das ist aber Teil von Erstellen von Histogrammen auf Basis von Statistiken #228 und so wie es dort geplant ist werden die errechneten Summen in einem Objekt der Klasse AbstractStatistics gespeichert, nicht in der Datenstruktur zur Repräsentation eines Bins über die wir hier sprechen. Letztere wird nur genutzt um über die Bins zu iterieren um die möglichen Bedingungen zu ermitteln.

[LukasEberle]

Zu

wobei die Bins sortiert sind

Müssen wir die Bins dann doch für equal width binning sortieren? Da das max von bin n immer kleiner sein wird als das min von bin n+1, also müssten wir die Threshholds auch ohne das sortieren berechnen können.

Soll ich für die Implementierung dann wieder einen branch von approximate-conditions abzweigen?

[michael-rapp]

Zu

wobei die Bins sortiert sind

Müssen wir die Bins dann doch für equal width binning sortieren? Da das max von bin n immer kleiner sein wird als das min von bin n+1, also müssten wir die Threshholds auch ohne das sortieren berechnen können.

Die Equal-Width und Equal-Frequency-Methoden so wie sie aktuell implementiert sind sorgen schon dafür dass die Bins am Ende sortiert sind. Da müssen wir nichts Zusätzliches machen.

Soll ich für die Implementierung dann wieder einen branch von approximate-conditions abzweigen?

Ja, genau.

[LukasEberle]

Ok ich hatte das falsch verstanden. Die Bins sind sortiert aber bei Equal Width kann es vorkommen, dass die Werte in den Bins nicht sortiert sind, aber das ist ja egal.

[michael-rapp]

Genau